ROTATIONS EN CASCADE

 

Dans l'animation d'une scène 3D, on est souvent amené à effectuer des rotations en cascade des objets. En effet, d'une image à l'autre les objets bougent et on passe son temps à recalculer la position des points.

Pour effectuer plusieurs rotations en cascade, on peut envisager trois méthodes a priori équivalentes :

  1. on part de la position actuelle des points, on leur applique les transformations calculées pour obtenir la nouvelle position. Cette dernière sert de point de départ pour obtenir la position d'après et ainsi de suite.
  2. la position des points est immuables. On calcule pour chaque scène les nouvelles matrices de rotations en partant des précédentes et en les multipliant par la transformation à faire.
  3. la position des points est immuable et on calcule pour chaque scène une nouvelle matrice de rotation après avoir mis à jour les angles qui servent à la construire.

A première vue, ces trois méthodes doivent donner les mêmes résultats. Mais c'est sans compter avec un des problèmes majeurs qui guette le programmeur scientifique : l'erreur de calcul.

Non pas qu'une de ces méthodes soit erronnée, mais l'ordinateur calcule faux. Ou plus exactement, on ne lui donne pas les moyens de calculer juste.

Dans le 1er cas, on part de la position obtenue pour calculer la suivante. La difficulté vient du fait que la position obtenue est bien souvent composée d'entiers pour des raisons pratiques : on applique la matrice de rotation (et un éventuel vecteur translation) en travaillant en virgule fixe.
Le résultat obtenu est tronqué (ou arrondi, la différence est ténue) stocké et sert de point de départ pour la rotation suivante. En conséquence, la position stockée n'est pas exactement la position réelle des points. Une erreur de 1 n'est pas grand chose à la première rotation ... mais ça s'accumule. Et au bout d'un moment, l'objet ne ressemble plus vraiment à ce qu'il était initialement.

Dans la seconde méthode, c'est pire... La matrice de rotation est recalculée en la multipliant par la précédente. Là aussi on commet des erreurs de troncature, qui sont d'autant plus graves qu'elles s'accumulent sur la matrice elle-même : pour que l'objet une fois roté reste identique à lui-même, la matrice de rotation doit respecter un certain nombre de propriétés; en particulier sa norme doit être égale à 1 (sans quoi la taille de l'objet change) et être orthogonale (sans quoi l'objet se déforme).
Conclusion, là aussi au bout de quelques rotations l'objet ne ressemble plus que vaguement à ce qu'il était au début. En pratique, la déformation dans cette méthode est plus importante que dans la précédente.

Dans la 3ème méthode, il n'y a d'erreur de troncature que si la mise à jour des angles se fait en utilisant des nombres qui ne peuvent pas être représentés exactement par l'ordinateur. En général donc, on ne commet pas d'erreur.
Comme on recalcule la nouvelle matrice de rotation à chaque fois uniquement en partant des nouveaux angles, il n'y a pas d'accumulation d'erreurs à ce niveau et au pire, l'objet n'est pas roté des bons angles mais c'est tout. il ne se déforme pas. C'est donc la solution à utiliser.

En pratique, on a pas toujours le choix et on doit parfois utiliser les méthodes 1 ou 2.

Dans la méthode 1 on ne peut pas faire grand chose ... on subit la déformation des objets et on s'arrange pour que le nombre de rotations reste faible.

Dans la méthode 2, on remet la matrice en forme toutes les quelques rotations (toutes les 12 par exemple). Cette remise en forme est une renormalisation (pour la forcer à avoir une norme égale à 1) et une orthogonalisation. C'est couteux en temps de calcul....

Plutôt que de faire tout le calcul de rotation pour passer d'une image à une autre, il y a aussi la solution d'interpoler la rotation : on calcule un point d'arrivée lointain et les différentes images de la séquence seront obtenues en interpolant les points.

La première idée qui vient à l'esprit pour faire cela est l'interpolation linéaire du 1er ordre :

On part du point P, il sera transformé en un point Q par la rotation. Si on doit réaliser cette rotation en n étapes, les différents points A(i) de la séquence seront :

            A(i) = (1-i/n)*P + i/n*Q soit
            A(i) = P + i/n*(Q-P)

Ce résulat peut se mettre sous une forme réccurente :

            A(i+1) = A(i) + (Q-P)/n

Le calcul du nouveau point se réduit donc à 3 additions.

Le défaut est que le chemin suivit par le point A(i) n'est pas vraiment (et c'est le moins qu'on puisse dire) celui d'une rotation. Si les angles sont grand, et donc P et Q très éloignés, ça va ressembler plus à du morphing qu'à une rotation. Mais si les angles sont assez petits, c'est une solution qui mérite d'être envisagée.

Bon, voilà c'est tout pour cette fois.

 

Pour aller plus loin, je vous conseille les ouvrages suivants :

J.D. Foley, A. Van Dam, S.K. Feiner, J.F.Hugues, "Computer Graphics : Principles and Practice", Addison-Wesley, 1990

D.F. Rogers, J.A. Adams, "Mathematical Elements for Computer Graphics", Mc Graw Hill, 1990

D.E. Knuth, "The Art of Computer Programming : Seminumerical Algorithms", Addison-Wesley, 1981

 

Pierre Larbier, Buc le 29/11/1995