Suivez-nous sur X
|
|
|
0,
A,
B,
C,
D,
E,
F,
G,
H,
I,
J,
K,
L,
M,
N,
O,
P,
Q,
R,
S,
T,
U,
V,
W,
X,
Y,
Z,
ALL
|
|
0,
A,
B,
C,
D,
E,
F,
G,
H,
I,
J,
K,
L,
M,
N,
O,
P,
Q,
R,
S,
T,
U,
V,
W,
X,
Y,
Z
|
|
0,
A,
B,
C,
D,
E,
F,
G,
H,
I,
J,
K,
L,
M,
N,
O,
P,
Q,
R,
S,
T,
U,
V,
W,
X,
Y,
Z
|
|
A propos d'Obligement
|
|
David Brunet
|
|
|
|
Programmation : C - Graphismes 3D en C (notion d'opacité)
(Article écrit par Pascal Amiable et extrait d'Amiga News Tech - octobre 1990)
|
|
La plupart des applications en infographie nécessitent l'affichage d'objets tridimensionnels avec un degré de
réalisme assez élevé. Jusqu'à maintenant nous avons réussi à afficher l'objet sous la forme d'un squelette
filaire. Cette représentation, comme vous l'avez sans doute remarqué, devient vite ambiguë dès que l'objet est
complexe et autorise le plus souvent, plusieurs interprétations possibles de la même entité (Fig. 1).
Pour remédier à ce problème, nous allons essayer de donner à ces objets filiformes une notion d'opacité des
faces afin de les considérer comme des volumes à part entière. Pour ce faire, on utilise la méthode d'élimination
des parties cachées.
Représentation interne d'un volume
Pour représenter un volume composé de faces opaques, la modélisation à base de tableaux, de points et de
lignes ne suffit plus, il faut également modéliser les faces. Une face d'un objet est une région plane et
finie limitée par des segments de droite (exemple : un polygone). Comme le but de cet article est de
vous proposer un exemple simple de fonction d'élimination de parties cachées, nous allons apporter une
contrainte supplémentaire à ces faces, elles seront triangulaires (Fig. 2). Cela signifie que tout objet
devra être décomposé en facettes triangulaires. Une facette triangulaire sera définie dans un premier
temps par la liste de ces sommets.
On part d'un sommet arbitraire et on passe au suivant dans le sens trigonométrique (anti-horaire) et ainsi de
suite pour les trois sommets. Pour la pyramide de la figure 2, on obtient la liste des faces suivantes.
- Nombre de faces : 6.
- Face 1 : 0 2 1.
- Face 2 : 0 3 2.
- Face 3 : 0 4 2.
- Face 4 : 0 1 4.
- Face 5 : 4 3 2.
- Face 6 : 4 2 1.
C'est ce que contiendra le fichier "Face.dat".
De plus, la connaissance du plan associé à chaque face est nécessaire pour l'élimination de parties
cachées, il faudra stocker les coefficients du plan pour chaque face. Un plan est défini par
l'équation ax+by+cz=h. Nous allons donc stocker en plus des numéros des sommets A, B, C, les
coefficients a, b, c, h du plan (Fig. 3).
Ce genre de tableau hétérogène (trois entiers (short) et quatre coefficients (float))
se représente très facilement en C à l'aide d'un tableau de structure.
struct {short A,B,C;
float a,b,c,h;
}Face [100] /*pour 100 faces*/
|
Pour l'élimination des parties cachées, nous avons besoin des coordonnées Xs, Ys, et Zs
des différents sommets après changement de repère par rapport à un observateur E ou R
représente la distance entre l'observateur et l'origine de la scène alpha et teta les
angles suivant X et Y entre la direction de vision et l'axe Z du repère absolu (Fig. 4).
- Xs = -X*sin(alpha) + Y*cos(alpha)
- Ys = X*sin(teta)*cos(alpha) + Y*sin(teta)*sin(alpha) + Z*cos(teta)
- Zs = -X*cos(teta)*cos(alpha) - Y*cos(teta)*sin(alpha) + Z*sin(teta) +R
Le tableau de sommets sera représenté en C par :
Que nous manque-t-il désormais ?
Les coefficients des plans associés aux faces bien sûr, et ils se calculent. Voici les
formules :
- a = YA*(ZB-ZC) - YB*(ZA-ZC) + YC*(ZA-ZB)
- b = -(XA*(ZB-ZC) - XB*(ZA-ZC) + XC*(ZA-ZB))
- c = XA*(YB-YC) - XB*(YA-YC) + XC*(YA-YB)
- h = a*XA + b*YA + c*ZA
Élimination des contours cachés
C'est là que les choses sérieuses commencent. Nous allons développer un algorithme qui
ne trace que la partie visible d'un segment de droite dénommé PQ. Cet algorithme consiste à
déterminer pour chaque facette triangulaire ABC si celle-ci cache entièrement PQ ou
seulement une partie de ce segment. Nous connaissons les coordonnées des cinq
sommets A,B,C,P,Q, les coefficients de l'équation du plan a,b,c,h et le point d'observation E.
Considérons la pyramide infinie de sommet E et passant par les côtés AB, BC et CA (Fig. 5).
Tout point de PQ situé dans la pyramide et derrière ABC est caché les autres sont visibles.
Dans la figure 5, PQ coupe la pyramide en I et J on voit bien que le tronçon IJ est invisible.
Pour tester cette invisibilité potentielle, une série de tests est nécessaire.
Test 1
Si les deux Points P et Q sont positionnés devant ou dans le plan ABC, alors PQ est visible
entièrement. Ceci n'a lieu que si :
Test 2
Si la droite PQ se trouve à l'extérieur de la pyramide, alors PQ est apparent. Comment faire ?
Soit le plan EPQ d'équation : dx+ey+fz=g.
- d = YP.ZQ - YQ.ZP
- e = ZP.XQ - ZQ.XP
- f = XP.YQ - XQ.YP
On remplace (x,y,z) dans l'équation du plan par les coordonnées de A, B et C.
- ga = dxa+eya+fza
- gb = dxb+eyb+fzb
- gc = dxc+eyc+fzc
Si ga, gb et gc sont de même signe, PQ est à l'extérieur de la pyramide.
Note : il se peut que l'un des trois coefficients soit nul (PQ passant par un des points A,B,C).
Pour résoudre ce cas particulier, on modifie le test supplémentaire.
Pour chaque point A,B,C, si g<0, alors somme = somme - 1, et si g>0, alors somme = somme + 1.
Si la valeur absolue (somme) >2, PQ est extérieur.
Test 3
Dans le cas où PQ n'est pas extérieur à la pyramide, il faut déterminer s'il est entièrement contenu
dans la pyramide ou non. Pour ce faire, il faut déterminer l'intersection (lorsqu'elle existe) de
PQ avec les plans EAB, EBC et EAC. Prenons le cas EAB (c'est pareil pour les autres plans) :
soit A1x+A2y+A3z = 0, l'équation ramenée à 0 du plan EAB.
- A1 = YA*ZB - YB*ZA
- A2 = XB*ZA - XA*ZB
- A3 = XA*YB - XB*YA
Soit B1x+B2y+B3z = 0, l'équation ramenée à 0 du plan EPQ.
- B1 = YP*ZQ - YQ*ZP
- B2 = XQ*ZP - XP*ZQ
- B3 = XP*YQ - XQ*YP
PQ et EAB possède un point commun si 0 <= lambda <= 1 et 0 <=mu<= 1.
On effectue le même test pour EBC et EAC : on obtient donc 3 lambda et 3 mu.
On recherchera également les Lamdamin et Lambdamax qui satisfont au test ci-dessus.
Test 4
Si aucun des deux points P et Q n'est à l'extérieur de la pyramide (et que les trois premiers
tests ont échoués), alors PQ est entièrement caché par la face.
Test 5
Si un point I intersection de PQ avec la pyramide se trouve devant ABC, alors PQ est apparent.
Soit les coefficients :
- R1 = XQ-XP
- R2 = YQ-YP
- R3 = ZQ-ZP
- Xmin = XP+Lambdamin*R1
- Ymin = YP+Lambdamin*R2
- Zmin = ZP+Lambdamin*R3
Si (a*Xmin+b*Ymin+c*Zmin < h), alors PQ est visible.
- Xmax = XP+Lambdamax*R1
- Ymax = YP+Lambdamax*R2
- Zmax = ZP+Lambdamax*R3
Si (a*Xmax+b*Ymax+c*Zmax < h), alors PQ est visible.
Test 6
A ne réaliser que si PQ coupe la pyramide derrière le triangle. C'est-à-dire si le test 5
a échoué ; cas où I=J.
Si P est hors de la pyramide, alors PI est apparent.
Si Q est hors de la pyramide, alors JQ est apparent.
Une fois ces tests réalisés, on trace ou non PQ, PI, JQ et le tour est joué. On fait cela
pour chaque segment et chaque face et l'élimination des parties cachées est réalisée.
Conclusion
Cet article représente donc une approche algorithmique permettant de résoudre le problème de
l'élimination des parties cachées. Il existe bien d'autres méthodes pour éliminer les faces
cachées (méthode du tampon de profondeur (Z-buffer), algorithme de Warnock, etc.)
celle-ci ayant le mérite d'être assez simple à programmer. Je vous laisse donc un mois pour
essayer d'écrire le programme correspondant à cet algorithme, je vous donnerai une solution
possible le mois prochain.
|
