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...
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.
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).
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... :-)
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.
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.
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 :
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.
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