GithubThis page is at least 10 years old !
Rotozoom
En cours d'écriture...
Exemple:
L'idée du rotozoom est d'obtenir un effet de texture 2D qui tourne et s'élargit ou se rétrécit à l'infini.
C'est un effet qui demande un rendu pixel par pixel mais les opérations pour chaque pixel sont simples.
Les ingrédients sont les suivants:
- Un accès bitmap brut au framebuffer.
- Une table de cosinus.
- Un vecteur. Quelques octets de RAM, concrètement.
- Optionellement, une petite texture 2D si la machine le permet.
Le mot "vecteur" peut faire peur aux nuls en maths mais n'ayez crainte, expliqué simplement c'est juste une paire de valeurs qui vont indiquer un angle et une distance. L'angle va correspondre à celui de la rotation que l'on veut appliquer à la texture. La distance correspondra au "zoom".
Le vecteur
A chaque nouvelle image à afficher, il faut calculer les valeurs du vecteur afin d'animer l'effet.
Comme les affichages sont quasiment tous basés sur des coordonnées cartésiennes (X et Y, ou lignes et colonnes de pixels), on souhaite plutôt avoir un vecteur qui représente un décalage (delta) en X et Y plutôt qu'en angle et distance (coordonnées polaires).
Pour convertir l'angle de rotation et le zoom en deltas, il faut faire une conversion polaire vers cartésien grâce a la table de cosinus.
Avec a l'angle, z le zoom, dx le delta horizontal et dy le delta vertical
:
dx = cos(a) * z
dy = sin(a) * z
A noter qu'il n'est pas nécessaire d'avoir deux tables distinctes pour cosinus et sinus. On peut utiliser la table de cosinus avec un décalage d'un quart de sa taille (en arrière, donc négatif) pour obtenir le sinus. Par exemple, pour une table de 256 valeurs et a sur 8 bits:
dx = cos_table[a] * z
dy = cos_table[a - 64] * z
Les deltas n'ont besoin d'être obtenus qu'une fois par image, ça ne demande donc vraiment que peu de temps comparé au reste.
Ce vecteur (la paire de deltas) peut maintenant être utilisé pour faire le rendu du rotozoom à partir de la texture.
Une ligne
Pour remplir chaque pixel du framebuffer, on pioche un pixel de la texture. Le framebuffer est typiquement rempli de gauche à droite, de haut en bas. La position du pixel à lire dans la texture est donnée par une accumulation du vecteur.
Étape par étape, ca donne ceci:
Pour le premier pixel du framebuffer (x=0, y=0), on va commencer à un point A (0,0) dans la texture. Ce qui correspond aussi à son pixel haut-gauche. Un pixel de rendu.
En ajoutant le vecteur, on obtient les coordonnées du point B, qui est la position du prochain pixel.
En continuant d'ajouter le vecteur à chaque fois, on remplit une ligne horizontale entière du framebuffer.
Par exemple si nos deltas sont dx=2 et dy=1, on aurait un vecteur (2, 1) qui indiquerait d'avancer 2 pixels à droite et 1 pixel en bas.
A noter qu'il est important de faire "warper" les coordonnées qui se trouveraient en dehors de la texture, pour donner l'impression que la texture est infinie.
Ici les flèches noires représentent le vecteur, les pointillés gris représentent le warp. Comme E serait hors de la texture, à droite, on le fait revenir par la gauche. C'est une opération simple (AND logique) si on choisit une texture avec des dimensions en puissances de 2, ici 8x8 pixels.
La ligne ABCDEFGH sous la texture représente la ligne du framebuffer dont on vient de faire le rendu.
Plusieurs lignes
Pour passer à la ligne suivante du framebuffer (en dessous), il faut repartir du point A initial (0,0) mais ajouter le vecteur perpendiculaire pour obtenir un nouveau A.
Les valeurs du vecteur perpendiculaire sont très simple à obtenir, il suffit d'intervertir les deltas et inverser le signe de dy. Le vecteur perpendiculaire serait ici (-dy, dx) donc (-1, 2).
Comme le nouveau point A serait en dehors de la texture, à gauche, on le fait revenir par la droite.
En vert le vecteur perpendiculaire et le warp qu'il engendre. En violet, le "chemin" pour la nouvelle ligne.
A chaque nouvelle ligne, il faut partir du A précédent et ajouter le vecteur perpendiculaire, puis faire le rendu de la ligne. Répéter toutes ces opérations pour remplir le framebuffer en entier. Encore un exemple pour la troisième ligne:
Au final, on a fait l'équivalent de ceci:
Dans cet exemple, notre framebuffer (qui est de la même taille que la texture: peu judicieux), ressemblerait à ceci:
On pourrait croire au bug, mais c'est bien le rendu final de notre texture, tournée, et réduite. Avec une si basse résolution il est difficile de distinguer quoi que ce soit...
Cet algo peut se tester avec du papier quadrillé. Voici deux astuces pour vérifier qu'on ne se plante pas:
- Si on ajoute encore une fois le vecteur après le dernier point d'une ligne (H ici), on doit retomber sur le point A de la ligne.
- Pareil pour le point A initial: après avoir fait toutes les lignes, si on ajoute encore une fois le vecteur perpendiculaire, on doit retomber sur le tout premier point A de l'image en cours.
Précision numérique
Importante: Les deltas du vecteur doivent avoir une résolution assez grande, au risque d'avoir un rotozoom qui "saute" ! Des valeurs 8 bits ne vont pas donner beaucoup de marge pour rendre un effet fluide. Des valeurs 16bits à virgule fixe (8.8) conviennent très bien.
Par exemple, si on utilise de vraies unités de matheux:
a = 1.2 (radians)
z = 2
dx = cos(a) * z =
0.362 * 2 = 0.724
dy = sin(a) * z =
0.932 * 2 = 1.864
Si la table de cosinus donne des valeurs 8 bits entre -128 et +127 au lieu de -1 et 1:
dx = cos_table[a] * z =
46 * 2 = 92
dy = sin_table[a] * z =
119 * 2 = 238
Pour obtenir la position du pixel dans la texture il suffit de diviser la position accumulée par 128. Cela permet de "mettre de coté" la précision, sans la perdre.
Exemple de vecteurs qui font des trucs spéciaux:
- (0,0): pixel texture en haut à gauche répété partout (zoom infini).
- (1,0): copie sans transformation de la texture.
- (-1,0): copie avec flip sur X.
On peut obtenir des effets funky si par exemple on décide d'ajuster le vecteur pendant qu'on fait le rendu, afin d'obtenir des "chemins" sinueux ou courbés.
C'est des canvas HTML, la source JS est visible ;)
Changer le centre de rotation
Avoir le centre de rotation en haut a gauche de l'écran n'est pas forcement voulu, esthétiquement.
Heureusement, le changer ne demande qu'une opération en plus par image.
Instinctivement, on pourrait se dire qu'il suffit de commencer avec un point A a une position autre que (0, 0) dans la texture, mais cela n'aura pour effet que de déplacer la texture (utile pour un éventuel scrolling, cela dit).
Pour déplacer le centre de rotation, il faut "l'anticiper" en utilisant le vecteur, mais cette fois ci à l'envers.
Imaginez devoir filmer tout le tour d'une pomme: vous pouvez tenir la pomme en l'air et la faire tourner devant une camera fixe.
Imaginez devoir filmer tout le tour d'une statue: ça risque d'être plus simple de faire tourner la camera autour de la statue.
Pour faire au plus simple, l'algo ne change pas, seules les valeurs initiales de U et V changent selon le vecteur. C'est la toute la différence avec les deux valeurs fixes auxquelles on pouvait penser: il faut que les valeurs dépendent du vecteur, et donc de l'angle et du zoom, et donc de l'animation.
Précédent centre de rotation en bleu, en commençant le rendu avec U = 0, V = 0.
En utilisant l'opposé du vecteur et du vecteur perpendiculaire, on peut "rembobiner" la position pour trouver le nouveau point de départ (les nouveaux U et V).
Si on veut que le centre de rotation soit le centre de l'écran, alors il faudra utiliser largeur/2 fois le vecteur opposé, et hauteur/2 fois le vecteur perpendiculaire opposé.
Par exemple pour un écran de 160x120 pixels, il faudra ajouter 80 fois l'opposé du vecteur, et 60 fois l'opposé du vecteur perpendiculaire.
Ici, le vecteur est toujours (2, 1), son opposé (en gris) est (-2, -1).
Le vecteur perpendiculaire est toujours (-1, 2), son opposé (en vert clair) est (1, -2).
Visuellement, il suffit d'inverser le sens des flèches.
Le centre de rotation est toujours en bleu, mais le nouveau point de départ est maintenant en jaune. Avec ces nouvelles valeurs initiales de U et V, on peut maintenant reprendre l'algo exactement comme avant. Ne pas oublier de recalculer les U et V initiaux a chaque image !
Ici le point bleu ne semble pas bien centré au milieu de la "grille" de vecteurs car la résolution n'est que de 8x8 pixels. Comme c'est des nombres paires et entiers, j'ai choisi un centre à (4, 4). Avec une résolution plus grande, le fait d'être décalé d'un pixel ne se remarque pas.
Avec l'animation, le point jaune (la "camera") ici tournerait autour du point bleu (la statue).
Pas de texture ?
Pas assez de mémoire pour stocker une texture ? Pas assez de temps pour y accéder ? Un damier ne coûte quasiment rien !
pixel = (u ^ v) & 128
