De la ponctualité des bus,
de la sécurité des réseaux
et de la bêtise des masses
ou

" LA GRANDE SAGA DE LA 3D - PARTIE II "

 

Certains jours, rien ne colle. Vous vous couchez trop tard à cause d'un programme résolument buggé, et le matin vous n'obéis- sez pas à votre réveil qui sonne sans prévenir. Bien sûr, ce sont ces jours là où le bus qui vous laisse habituellement attendre au froid plusieurs minutes de trop, choisi d'arriver exceptionnellement à l'heure, vous laissant en plan sans espoir d'arriver avant la fin du cours de physique.

Encore insouciant, vous décidez d'en profiter pour passer le reste de votre matinée sur réseau... Mais là, lorsque vous vous loggez, vous constatez que votre compte s'est fait hacker par un petit rigolo qui a changé le pass.

A ce stade, vous commencez à réaliser qu'il vaut mieux mettre un terme à cette journée déplorable.

Fâché contre le bus, vous rentrez en train. Grave erreur : dès que vous posez un pied à la gare vous vous retrouvez face à une foule hostile et houleuse, se bousculant vers l'unique guichet qui délivre le coupon mensuel de carte orange.

On est le premier du mois, et c'est la "journée officielle de lutte contre le sida". Il vous faudra donc supporter en plus la vision d'empaffés arborant fièrement leur ridicule petit ruban rouge. (Nd Reporter : Cette dernière phrase n'engage que son auteur)

De retour chez vous, vous décidez de vous changer les idées en allant quérir un magazine traitant de "création sur PC" dont vous attendiez la sortie avec impatience. Rien du prix prohibitif ni de la conversation interminable entre deux clientes ne vous font reconsidérer votre voeux. Vous vous débarrasserez toutefois du-dit torchon dans la première poubelle sur le chemin qui vous reconduit chez vous...

C'est à la fin de ces journées-ci que l'on puise la motivation nécessaire à la programmation d'un monde virtuel. Ou à l'écriture d'un article traitant de 3D...

 

MAITRISER L'ESPACE

Dans cette partie, nous allons voir comment déterminer les positions des objets 3D. Nous verrons dans une autre partie comment représenter une scène 3D à l'écran.

 

Les objets

La première chose à faire est de nous fixer une limite pour les coordonnées. J'ai choisi de limiter les coordonnées à 16 bits, nous travaillerons donc dans un espace cubique fermé de 65536 positions de côté. Dans cet espace, nous n'utiliserons que des repérages cartésiens (x,y,z). Les coordonnées seront toujours signées.

Un objet 3D est caractérisé par sa forme et sa position.

La forme d'un objet est définie grâce à des faces plates, et ce même sur des ordinateurs très puissants. Une face est donc définie par les coordonnées de ses sommets. Ces coordonnées sont exprimées par rapport au centre de l'objet.

La position de l'objet dans l'espace est déterminée d'une part par les coordonnées du centre de l'objet et d'autre part par l'orientation dans l'espace de l'objet. On utilisera donc un vecteur de translation (dX, dY, dZ), et trois angles de rotation (a,b,c).

Notez qu'ici le terme "centre de l'objet" désigne le centre de rotation de l'objet.

 

Description des objets

Déterminer les positions des objets, c'est déterminer les coordonnées de chacun des sommets des faces de chacun des objets. Or, très souvent, plusieurs faces ont un sommet commun. Pour ne pas recalculer plusieurs fois les mêmes coordonnées, nous travaillerons avec des points. Les faces ne sont donc plus alors qu'une liste de numéros de points plutôt qu'une liste de coordonnées (x,y,z).

Voici l'exemple d'un cube d'arrête 200 dont le centre (de rotation) se trouve à l'intersection de ses diagonales :

      nombre de face : 6
      nombre de points : 8

      coordonnées des points :

             Point #0 :  x = -100    y = -100    z = -100
             Point #1 :  x =  100    y = -100    z = -100
             Point #2 :  x =  100    y =  100    z = -100
             Point #3 :  x = -100    y =  100    z = -100
             Point #4 :  x =  100    y = -100    z =  100
             Point #5 :  x = -100    y = -100    z =  100
             Point #6 :  x = -100    y =  100    z =  100
             Point #7 :  x =  100    y =  100    z =  100

      faces :

             Nombre de sommets       No des points-sommets

                    4                     0, 1, 2, 3
                    4                     1, 4, 7, 2
                    4                     4, 5, 6, 7
                    4                     5, 0, 3, 6
                    4                     5, 4, 1, 0
                    4                     3, 2, 7, 6


      Représentation :

                              #6             #7
                               +-------------+
                          #3 / |        #2 / |
                           +-------------+   |
                           |   |         |   |
                           |   |         |   |
                           | #5À---------+---+#4
                           | /           | /
                           +-------------+
                          #0            #1

Vous remarquerez que les numéros des points sont toujours donnés de manière à décrire la face dans un sens précis (dans le sens trigonométrique lorsqu'on regarde la face, dans mon exemple).

 

Calculs de rotation

Un tout petit peu de mathématiques...

Prenons un point P dans un plan (2D). Vous devez savoir que les coordonnées de ce point sont, si a est l'angle entre [Ox] et [OP] :

	xP = R * Cos a
        yP = R * Sin a

Sachant cela, cherchons les coordonnées du point M qui serait un point tel que distance(OP)=distance(OM) et l'angle (OP;OM) soit connu d'avance (en fait, le point M n'est rien d'autre que le point P qui aurait tourné autours de O d'un angle (OP;OM)). Appelons ß l'angle (OP;OM). Les coordonnées de M sont donc :

	xM = R * Cos (a+ß)
        yM = R * Sin (a+ß)

A condition de savoir les deux formules suivantes :

        Cos (a+b) = Cos(a)*Cos(b) - Sin(a)*Sin(b)
        Sin (a+b) = Sin(a)*Cos(b) + Sin(b)*Cos(a)

... On peut déduire que :

        xM = R*Cos(a)*Cos(ß) - R*Sin(a)*Sin(ß)
        yM = R*Sin(a)*Cos(ß) + R*Sin(ß)*Cos(a)

Mais, oh ! Miracle des Mathématiques, on retrouve dans ces expressions barbares les coordonnées de P, et on en déduit sans plus tarder le résultat final :

        xM = xP*Cos(ß) - yP*Sin(ß)
        yM = yP*Cos(ß) + xP*Sin(ß)

Et voilà, ça y est, on sait faire tourner un point quelconque autours de l'origine O en 2D. Par exemple, pour faire tourner le point A(8,12) de 63 degrés autours de O, on applique la formule précédente et on trouve B(-7,12.6).

Bon, mais nous ne sommes pas dans un simple plan, mais dans l'espace.

Pas de problèmes, on n'a qu'à tout simplement faire tourner les points autours de différents axes : on utilise la formule pour faire tourner le point dans le plan perpendiculaire au premier axe, puis on refait tourner le résultat dans le plan perpendiculaire au deuxième axe, et si l'on veux être encore plus méticuleux, on recommence avec le troisième axe... Voici le détail des calculs :

	(x,y,z) : coordonnées originales du point dans l'espace

        Ax, Ay, Az : les trois angles de rotations autours des axes
                     [Ox), [Oy) et [Oz)

             Après rotation autours de l'axe [Oy] :

        x1 = x*Cos(Ay) - z*Sin(Ay)
        z1 = z*Cos(Ay) + x*Sin(Ay)
        y1 = y (inchangé)

             Après rotation autours de l'axe [Ox] :

        x2 = x1 (inchangé)
        z2 = z1*Cos(Ax) - y1*Sin(Ax)
        y2 = y1*Cos(Ax) + z1*Sin(Ax)

             Après rotation autours de l'axe [Oz] :

        x3 = x2*Cos(Az) - y2*Sin(Az)
        y3 = y2*Cos(Az) + x2*Sin(Az)
        z3 = z2 (inchangé)

             Au final :


        x3 = (x*Cos(Ay)-z*Sin(Ay))*Cos(Az)
                -(y*Cos(Ax)+(z*Cos(Ay)+x*Sin(Ay))*Sin(Ax))*Sin(Az)

        y3= (y*Cos(Ax)+(z*Cos(Ay)+x*Sin(Ay))*Sin(Ax))*Cos(Az)
                +(x*Cos(Ay)-z*Sin(Ay))*Sin(Az)

        z3= (z*Cos(Ay)+x*Sin(Ay))*Cos(Ax)-y*Sin(Ax)

             Soit :

        x3 = un+truc-immense/qui*(prend+des+heures)/a^calculer
        y3 = lui-aussi+la/vache*c'est-fous^non!
        z3 = putaing*pour-Z*c'est/(a-peine)*(plus+simple)!

Autant dire que si on devait faire ce calcul pour chaque point, on ne tournerait pas bien vite...

Heureusement, il est possible de factoriser ces expressions pour obtenir quelque chose du style :

	x'=(Ax + Dy + Gz)
        y'=(Bx + Ey + Hz)
        z'=(Cx + Fy + Iz)

... Où A, B, C, D, E, F, G, H et I sont des fonctions dépendant uniquement des trois angles de rotation, et que l'on peut donc ne calculer qu'une seule fois pour tous les points d'un repère.

Dans ma routine de rotation, les valeurs de ces fonctions sont :

	A :=  cos  az * cos ay
        B :=  cos aX * sin az - sin aX * sin ay * cos az
        C :=  cos aX * sin aY * cos aZ  + sin aX * sin az
        D := -cos aY * sin az ;
        E := sin aX * sin ay * sin az + cos aX * cos az
        F := sin aX * cos aZ - cos aX * sin aY * sin aZ
        G := -sin aY
        H := -sin aX * cos ay
        I := cos aX * cos aY

(il est possible d'optimiser le calcul de ces constantes, mais cela ne changerait pas grand chose ... ) (Note : Un grand "Merci" à BEN au passage pour ces calculs )

Ces valeurs ne sont pas celles que vous obtiendriez si vous factorisiez les expressions de x3,y3 et z3 que j'ai calculées plus haut car à l'époque où j'ai écrit ces routines je ne m'était jamais amusé à recalculer toutes ces formules, et comme le résultat final dépend de l'ordre des axes, il m'aurait fallut un gros paquet de chance pour retomber dessus du premier coup.

Quant à ré-écrire mes routines... Hum ! Vous voyez d'où viennent ces formules, c'est le principal... :-)

 

REPRESENTATION GRAPHIQUE

Maintenant que nous connaissons les coordonnées de tous nos objets, il va falloir en donner un représentation crédible à l'écran.

 

Projection 3D -> 2D

Pour représenter chacune des faces de tous les objets à l'écran, il nous faut non pas les coordonnées 3D des sommets des faces, mais plutôt les coordonnées 2D de ces sommets à l'écran.

Ici encore, il y a plusieurs méthodes pour obtenir ces coordonnées. Celle que nous allons voir est la plus simple et la plus utilisée : elle consiste à projeter les points sur un plan situé devant le point d'observation (le plan de l'écran). Cette méthode est du reste la même que celle utilisée dans une chambre noire, sauf qu'ici le plan-écran sera placé devant le point d'observation (le diaphragme), ceci afin d'avoir une image droite.

               M (dans l'espace)
              x------\            +-----------+
                      \------\    |           |
         -------------------- \---O----\ ---- | ----  (Horizontale)
                                  |     \-----x  M'(Image)
                                  +-----------+
            O = Point d'observation           À Plan-écran (image inversée)

                          CHAMBRE NOIRE




                    M (dans l'espace)
       distance    x------\   |M'(Image)
        X ou Y             \--x---\
              ----------------|--- \---O ---------  (Horizontale)
                              |
                              |          O = Point d'observation

                              À Plan-écran (image droite)

                   <---- distance Z --->


                         PROJECTION 3D

Ces schémas 2D sont à répéter dans les deux directions X et Y pour obtenir les coordonnées (Xe,Ye) du point à l'écran. On voit donc immédiatement que :

	Xe = X * d/Z
        Ye = Y * d/Z

Dans ces formules, (X,Y,Z) sont les coordonnées de M dans l'espace, et d est la distance entre O et le plan-écran. On sera bien avisé de choisir une puissance de 2 pour d.

Réflexe lorsque l'on voit un tel calcul : quand dépassera t-on les 16 bits possibles pour le résultat ? Cela dépend de la position du point dans l'espace.

Pour commencer, tout point situé dans le demi-espace arrière ne devra pas être pris en compte. On voit aussi que tout point situé après le plan de l'écran (Z>d) sera projetable. De même pour les points entre O et le plan de l'écran (Z<d) pour lesquels |X|<Z et |Y|<Z (tous les points situés dans la pyramide de sommet O et de base le plan-écran). Il ne reste donc plus à exclure que les points situés avant le plan-écran (Z<d) qui n'appartiennent pas à cette pyramide (|X|>Z ou |Y|>Z).

De plus, il sera prudent d'exclure les points dont la coordonnée Z est inférieure à Zmin tel que d>Zmin>0, ceci afin de se préserver d'un dépassement de division ou d'un résultat grotesque, dûs à une perte de précision dans les calculs.

De plus, il peut être pratique de fixer une distance limite Zmax à laquelle les faces ne seront plus visibles (tout comme il est intéressant de choisir la description de l'objet en fonction de son éloignement, du plus grossier au plus net).

Résumons les conditions que devront satisfaire nos points pour être projetés :

	(Zmin<Z<Zmax) et ((Z>d) ou ((|X|<Z) et (|Y|<Z))

Une face dont un des sommets ne vérifie pas une de ces trois règles ne sera pas traitée. Cette méthode est un rien barbare, mais c'est une méthode simple et efficace. Son principal défaut est qu'elle ne permet pas d'afficher une face dont une partie se trouve derrière le point d'observation et une autre devant. Dans le cas d'un mur par exemple, nous serons obligés de diviser le mur en plusieurs faces plus petites.

 

Figurations d'une face

Ca y est, nous avons les coordonnées 2D des sommets d'une face, et il nous faut maintenant tracer une représentation de cette face.

Dans la 3D, la partie graphique est la partie qui varie le plus d'un programme à un autre. D'une part, les faces peuvent être représentées de nombreuses façons différentes : lignes, polygones monochromes, polygones avec texture (dégradés de couleurs, méthode de Phong, de Gouraud, etc...), polygones avec image bitmap mappée... D'autre part, on pourra trouver plusieurs moyens de réaliser chacun de ces effets.

Il y a aussi, basiquement, deux méthodes différentes pour animer : Soit on affiche les faces directement à l'écran, soit on affiche tout dans un buffer en RAM et on transfert vers l'écran lorsque l'image est complète. La première méthode est souvent avantageuse. Il est parfois aussi possible de faire ce que l'on appelle du delta-filling, à savoir n'afficher que les différences entre deux images successives.

 

Tracer un polygone

Tracer un polygône est quelque chose de théoriquement simple, mais qui peut s'avérer moins simple dans la pratique si on a oublié de prévoir les nombreux cas particuliers qui peuvent se présenter.

Le principe est de parcourir le polygône dans le sens vertical en traçant à chaque ligne le segment du polygône. Prenons le cas simple d'un triangle (hum, si si, c'est bien un triangle) :


                                        A
                         .            #             .
          Scanning  |    .          #####           .
          vertical  |    .        #########         .
                    |    .      #############       .
                    |    ->   #########--------    <-
                    |       ---------------------
                    |    B         ----------------
                    |                    ------------
                                                -------  C

On partira du point le plus haut du triangle, soit A. Puis on se déplacera à chaque ligne sur les segments [AB] à gauche et [AC] à droite. Nous verrons tout à l'heure une méthode pour calculer les coordonnées X de ces deux droites après chaque incrémentation de Y.

Arrivé à la hauteur du point B, il faudra modifier les paramètres de la droite de gauche pour ne plus descendre le long de [AB] mais le long de [BC]. Arrivé à C, le triangle est tracé.

Trois remarques :

Cas particuliers à prendre en considération :

 

Test de visibilité

Dans un objet convexe on a le plus souvent à faire à des faces qui seront toujours vues que d'un seul côté. On détermine donc pour chaque face de l'objet si elle doit être affichée ou non.

Pour cela, on pourra utiliser un vecteur normal à la face. Le plus simple est de déterminer l'orientation de la face grâce au signe du ðZ de ce vecteur. Toute la difficulté réside alors dans le calcul du ðZ.

On pourrait par exemple calculer un point supplémentaire pour chaque face qui sera l'extrémité du vecteur ramené à un sommet, mais cette méthode est à proscrire du fait de son manque de précision si la face n'est pas centrée - en effet, l'effet de perspective peut rendre visible une face qui à un ðZ nul ou très légèrement négatif si cette face est décalée du centre.

Une meilleurs méthode est de calculer à chaque fois le vecteur normal du polygône projeté (en utilisant les coordonnées 2D). Ainsi la perspective n'intervient pas et le résultat est-il plus précis. Le calcul comporte deux multiplications :

Soit 3 points A, B et C qui se suivent dans une face (et qui sont donc dans un ordre précis), on peut calculer le produit vectoriel BA^BC (BA et BC sont des vecteurs) =

	(Xa-Xb)*(Yc-Yb) - (Xc-Xb)*(Ya-Yb)
Selon le signe de ce produit vectoriel, les trois points tournerons dans le sens trigonométrique ou pas.

 

CONCLUSION

Et vlan ! 570 lignes de théorie pure, et pas la moindre routine. NiarkNiark, débrouillez-vous avec ça ! Je pense que dans cet article, il y a à peu près tout ce qu'il faut comprendre pour coder une animation 3D. A vous d'assimiler, de tester, de râler parce que ça ne marche pas, d'expérimenter les "DIVISION PAR ZERO - YOU STUPID CODER !" et autres "DEPASSEMENT DE DIVISION ! - REBOOT NOW BEFORE EXPLOSION !", de pleurer, de vous arracher les cheveux, d'envoyer votre PC par la fenêtre, et finalement d'attendre tranquillement le Rep6 pour y trouver le premier source de 3d.

Alala, c'est pas encore pour demain votre monde virtuel, votre super Ferrari virtuelle, votre Claudia Schiffer virtuelle, votre abonnement au Rep virtuel, la tournée virtuelle d'AC/DC dans votre patelin, etc...

Héhé.

Mais non, je blaaââââAAAAAAaaague, c'est facile la 3d !

Virtuellement vôtre,

 

Rixed