bonjour,

je me prend la tête depuis quelques jours sur un problème un peu galère.
soit 2 triangles dans l'espace, qui ne s'intersectent pas.
on observe la scène depuis une vue de dessus (isométrique !)

j'aimerais déterminer lequel de mes 2 triangles doit être dessiné en premier.

pour le moment, je ne fais que comparer la distance de leur centre de gravité par rapport au point de vue mais c'est clairement insuffisant pour beaucoup de cas.
est ce que quelqu'un a une idée pour déterminer de manière précise si un triangle se trouve devant un autre ? (je répète : les triangles ne se croisent pas !)

merci

Salut,

Pourquoi distance avec l'isobarycentre ? Quel est l'intérêt de privilégier ce point plutôt qu'un autre point ?

Ce que tu peux faire, c'est calculer la distance par rapport au plan formé par ton triangle (si les trois points ne sont pas alignés).
Ce calcul peut passer par le calcul du point d'intersection de la droite perpendiculaire au plan et le plan, ou directement grâce à une formule :

Citation

Pour une équation de ton plan <math>\(ax+by+cz+d=0\)</math>, la distance entre un point <math>\((x',y',z')\)</math> et ton plan est : <math>\(\frac{|ax'+by'+cz'+d|}{\sqrt{a^2+b^2+c^2}}\)</math>

Après il faut trouver ces coefficients bien sûr. N'oublie pas que tu veux juste comparer des distances, donc tu peux tout simplement calculer <math>\(\frac{(ax'+by'+cz'+d)^2}{a^2+b^2+c^2}\)</math>.

Edit : Pour trouver les coefficients, il faut trouver un vecteur normal au plan, comme on fait avec des droites en 2D. Pour un triangle ABC, le produit vectoriel de <math>\(\vec{AB}\)</math> et <math>\(\vec{AC}\)</math> ferait l'affaire si je ne me trompe pas.

quel rapport entre la distance au plan et l'ordre pour dessiner les triangles ?

Si un triangle se trouve "au dessus" d'un autre, son dessin va "surpasser" le dessin de l'autre, non ?

Sauf que d'après ce que j'ai compris, les plans des triangles ne sont pas parallèles au plan de l'écran...

Mais pourquoi n'utilise tu pas openGL pour afficher tes triangles?

Sinon :
http://en.wikipedia.org/wiki/Z-buffering

non justement :
il y a de nombreux cas ou un triangle se trouve a la fois de chaque coté du plan de l'autre

ca fait un bon moment que je me penche sur ce problème et j'envisage des solutions qui fonctionnent, mais qui sont bien trop complexes et couteuses.

en fait, pour expliquer le pourquoi du comment, j'ai un morceau de programme qui dessine un objet 3D selon une vue iso (en l'occurrence, suivant l'axe z). l'objet est définit comme une surface polyédrique fermée sans auto-intersections, et dont les faces sont des triangles.
l'algo consiste a récupérer dans une liste (de type vector) la totalité des triangles visibles, puis de les classer de façon a les dessiner dans un ordre cohérent.
dans un souci de performance, les triangles sont classés par rapport a leur centre de gravité, ce qui donne un résultat relativement satisfaisant dans la majeure partie des cas. mais si les triangles de l'objet dessiné sont de taille trop variable, ca devient vraiment moche.

Je cherche donc une nouvelle règle de comparaison, qui soit plus juste, même si elle sera nécessairement moins rapide.
Pour toutes les questions que vous pouvez vous poser sur les choix de ma méthode (pourquoi pas utiliser directX ou openGL ou encore CGAL), je vous répondrais que je n'ai pas besoin d'une vue 3D temps réel (pas de contrainte de temps extrême), et que je ne tiens pas a utiliser une usine a gaz pour une fonction dont la réponse est booléenne.

en étudiant le problème (depuis un bon moment déjà), j'ai compris qu'il était impossible de les classer en ne tenant compte que de leur plans. j'ai des cas ou les barycentres et les normales aux triangles sont identiques, alors que la priorité d'affichage doit être différente.

j'ai bien entrevu une solution qui consiste a déterminer si il existe une intersection entre l'un des triangles et une pyramide définie par les 3 points de l'autre triangle et le point de vue (en vue iso, ca nous donne donc une sorte de "demi-prisme")
mais même la, j'ai du mal a imaginer une façon de procéder qui ne m'entraine pas dans des calculs de fou.
aussi, je garde a l'esprit qu'avec cette méthode, je n'ai théoriquement pas besoin de calculer une intersection, mais simplement de déterminer si, oui ou non, il y en a une (ce qui peux considérablement changer la façon de procéder dans certains cas)

tit_toinou : tu me disais "N'oublie pas que tu veux juste comparer des distances"
mais justement, non, je veux déterminer quel triangle doit être dessiné avant l'autre, et on ne peux pas ramener le problème a une comparaison de distance car elle est différente pour chaque point du triangle

Salut,

L'ennui c'est que la notion "ce triangle ci est devant celui là" ne définit pas un ordre sur les triangles. En bref, il est possible qu'un triangle T1 soit devant un triangle T2 qui est devant un triangle T3 qui est devant le premier triangle T1.

Du coup il n'est pas possible dans le cas général de trier les triangles dans un certain ordre et de les dessiner dans cet ordre là. Il y aura toujours certaines configurations qui s'afficherons mal avec une telle méthode. (Après je suis désolé mais je ne suis pas compétent pour pouvoir proposer une meilleure méthode).

j'ai conscience que certains cas sont insolubles (en fait, en pratique, j'ai parfois aussi des intersections entre des triangles ), mais je ne cherche qu'a avoir un résultat plus proche.

je pense avoir une première idée, mais a moitié incomplète :

1 - tout d'abord, projeter les triangles sur le plan de la vue (je l'ai d'office en ne tenant compte que des coordonnées x, y de mes points)
2 - déterminer si les triangles projetés s'intersectent (sur une surface non nulle !).
3 - s'il n'y a pas d'intersection, comparer l'éloignement de leurs barycentre respectifs (FIN)
sinon, déterminer un point quelconque de l'intersection de ces 2 triangles
4 - calculer la coordonnée Z de ce point sur les 2 triangles pour faire la comparaison.

pour l'étape 2, je pense pouvoir m'en sortir sans trop de difficulté en passant par un système de coordonnées barycentriques.
le véritable souci, ca va être a l'étape 3, de trouver rapidement un point appartenant aux deux triangles. l'intersection des 2 triangles pouvant avoir entre 3 et 6 cotés et étant strictement convexe, il "suffirait" de calculer le barycentre de 3 points de cette intersection
bon, je surchauffe un peu trop pour ce soir... j'y réfléchirai demain matin, je serai plus frais

Je me répète, mais pourquoi ne pas utiliser directement openGL pour afficher tes triangles?

j'ai déjà répondu a cette question.
de plus, ca ne résoudra pas mon problème : je ne cherche pas qu'un résultat, je cherche une méthode.

Dans ce cas là tu n'as pas à définir un ordre des triangles !
Pour chaque pixel de ta fenêtre, tu projette une droite entre le point qui représente la caméra et l'angle du pixel concerné de ta fenêtre (en l'occurrence les calculs peuvent se simplifier vu que tu regardes selon un axe).
Donc pour chaque pixel tu as une droite, et tu calcules l'intersection de cette droite avec tous les plans (préalablement calculés à partir des triangles). Et tu prend le triangle dont le point d'intersection est le plus proche du point de la caméra.

Bon ok, c'est peut-être un peu lourd .

Bon, je vais essayer d'expliquer mon idée simplement.

Pour résumer la situation

Tu as deux triangles <math>\(\mathcal{A}\)</math> et <math>\(\mathcal{B}\)</math> dans l'espace, c'est à dire 6 points <math>\(A_1,A_2,A_3,B_1,B_2,B_3\)</math>.
Tu te places le long de l'axe <math>\(z\)</math>, "assez loin" pour ne pas avoir de triangle directement à proximité ou au dessus de toi.
Tu aimerais pouvoir déterminer si le triangle <math>\(\mathcal{A}\)</math> est visuellement au dessus du triangle <math>\(\mathcal{B}\)</math>.

Problème

Comme il a déjà été précisé, il n'est pas possible d'obtenir un ordre total, car il est possible de construire trois triangles <math>\(\mathcal{A},\mathcal{B},\mathcal{C}\)</math> tels que <math>\(\mathcal{A}\)</math> est au dessus de <math>\(\mathcal{B}\)</math>, <math>\(\mathcal{B}\)</math> est au dessus de <math>\(\mathcal{C}\)</math>, et <math>\(\mathcal{C}\)</math> est au dessus de <math>\(\mathcal{A}\)</math>.
Néanmoins, il est impossible de faire ça avec deux triangles ! Donc ça vaut la peine de restreindre le problème à seulement deux triangles dans un premier temps.

La réponse

Je ne te propose pas une réponse booléenne, mais une réponse avec trois valeur possibles:
1. <math>\(\mathcal{A}\)</math> est au dessus de <math>\(\mathcal{B}\)</math>.
2. <math>\(\mathcal{B}\)</math> est au dessus de <math>\(\mathcal{A}\)</math>.
3. Ça n'a pas d'importance (c'est le cas où les deux triangles sont complètement visibles).

La méthode

Tout d'abord, la projection dans un plan orthogonal à l'axe <math>\(z\)</math> est une excellente idée. Ca se fait assez facilement, puisqu'en réalité c'est une projection dans le plan <math>\(oxy\)</math>. Ainsi, tu obtiens deux triangles (éventuellement dégénérés, mais on va dire que ça n'arrive pas dans notre cas) <math>\(\mathcal{A}'\)</math> et <math>\(\mathcal{B}'\)</math>. Tes points <math>\(A_i = (a_{i1},a_{i2},a_{i3})\)</math> et <math>\(B_i = (b_{i1},b_{i2},b_{i3})\)</math> pour <math>\(i \in \{1,2,3\}\)</math> deviennent <math>\(A_i' = (a_{i1},a_{i2})\)</math> et <math>\(B_i' = (b_{i1},b_{i2})\)</math>

Il faut maintenant se demander comment se comportent tes triangles projetés l'un par rapport à l'autre. Il y a 3 cas possibles:
1. Les deux triangles ne se touchent pas
2. Il y a intersection entre les côtés des deux triangles
3. L'un des deux triangles est complètement compris dans l'autre

Deux outils

Pour tester ces différents cas possibles nous aurons besoin de deux outils:
- Vérifier si un point quelconque est contenu à l'intérieur d'un triangle
- Vérifier si deux segments s'intersectent

Voyons le premier: vérifier si un point est contenu à l'intérieur d'un triangle.
Pour l'exemple, nous vérifions si un point <math>\(X = (x,y)\)</math> est contenu dans le triangle <math>\(\mathcal{A}\)</math>.
Pour que ce point soit à l'intérieur du triangle il suffit de vérifier ceci: si je parcours le périmètre du triangle, mon point doit toujours être du même côté (toujours à ma droite ou toujours à ma gauche). Si ce n'est pas le cas, c'est que le point est à l'extérieur du triangle.
Comment vérifier cela ? Avec le produit vectoriel normalisé !
Parcourir le périmètre, c'est choisir les trois points dans l'ordre qu'on veut (<math>\(A_1',A_2',A_3'\)</math>) et parcourir les segment <math>\([A_1',A_2']\)</math> puis, <math>\([A_2',A_3']\)</math>, puis <math>\([A_3',A_1']\)</math>.
On calcule alors les trois produits vectoriels:
<math>\(\overrightarrow{V_1} = \overrightarrow{A_1'A_2'} \times \overrightarrow{A_1'X}\)</math>
<math>\(\overrightarrow{V_2} = \overrightarrow{A_2'A_3'} \times \overrightarrow{A_2'X}\)</math>
<math>\(\overrightarrow{V_3} = \overrightarrow{A_3'A_1'} \times \overrightarrow{A_3'X}\)</math>
Et on les normalise:
<math>\(\overrightarrow{N_1} = \frac{\overrightarrow{V_1}}{||\overrightarrow{V_1}||}\)</math>
<math>\(\overrightarrow{N_2} = \frac{\overrightarrow{V_2}}{||\overrightarrow{V_2}||}\)</math>
<math>\(\overrightarrow{N_3} = \frac{\overrightarrow{V_3}}{||\overrightarrow{V_3}||}\)</math>

Pour les détails de calculs, ça donne (si je me goure pas):
<math>\(\overrightarrow{V_1} = ( 0, 0, (a_{21}-a_{11})(y - a_{12}) - (a_{22} - a_{12})(x - a_{11}))\)</math>
<math>\(\overrightarrow{V_2} = ( 0, 0, (a_{31}-a_{21})(y - a_{22}) - (a_{32} - a_{22})(x - a_{21}))\)</math>
<math>\(\overrightarrow{V_1} = ( 0, 0, (a_{21}-a_{11})(y - a_{32}) - (a_{22} - a_{12})(x - a_{31}))\)</math>
En normalisant, les vecteur <math>\(\overrightarrow{N_1}\)</math>, <math>\(\overrightarrow{N_2}\)</math>, <math>\(\overrightarrow{N_3}\)</math> tu obtiendras des vecteurs <math>\((0,0,1)\)</math> ou <math>\((0,0,-1)\)</math>
Le point est à l'intérieur du triangle si ces trois vecteurs normalisés sont égaux, ce que tu peux encore traduire par
<math>\(signe((a_{21}-a_{11})(y - a_{12}) - (a_{22} - a_{12})(x - a_{11})) = signe((a_{31}-a_{21})(y - a_{22}) - (a_{32} - a_{22})(x - a_{21})) = signe((a_{21}-a_{11})(y - a_{32}) - (a_{22} - a_{12})(x - a_{31}))\)</math>

Le second outil, c'est pouvoir vérifier si deux segments s'intersectent. Nous utiliserons également le produit vectoriel pour faire ça.
En effet, imaginons deux segment <math>\([A,B]\)</math> et <math>\([C,D]\)</math>. Les deux segments s'intersectent uniquement si <math>\(C\)</math> et <math>\(D\)</math> sont de part et d'autre de la droite <math>\(AB\)</math> ET <math>\(A\)</math> et <math>\(B\)</math> sont de part et d'autre de la droite <math>\(CD\)</math>. Nous devons calculer les produits vectoriels normalisés <math>\(\overrightarrow{W_1} = \frac{\overrightarrow{AB} \times \overrightarrow{AC}}{||\overrightarrow{AB} \times \overrightarrow{AC}||}\)</math> et <math>\(\overrightarrow{W_2} = \frac{\overrightarrow{AB} \times \overrightarrow{AD}}{||\overrightarrow{AB} \times \overrightarrow{AD}||}\)</math> et nous assurer qu'ils sont l'opposé l'un de l'autre. Encore une fois ces deux produits seront de la forme <math>\((0,0,1)\)</math> ou <math>\((0,0,-1)\)</math> et nous devons nous assurer d'obtenir <math>\((0,0,1)\)</math> et <math>\((0,0,-1)\)</math>. De même, il faut s'assurer que les deux produits vectoriels <math>\(\overrightarrow{W_3} = \frac{\overrightarrow{CD} \times \overrightarrow{CA}}{||\overrightarrow{CD} \times \overrightarrow{CA}||}\)</math> et <math>\(\overrightarrow{W_4} = \frac{\overrightarrow{CD} \times \overrightarrow{CB}}{||\overrightarrow{CD} \times \overrightarrow{CB}||}\)</math> sont bien opposés.
Je te propose de faire les calculs et je veux bien les relire, mais je ne vais pas les faire pour toi.

A présent, tu as donc deux outils:
- Tester si un point donné est dans un triangle donné
- Tester si deux segments s'intersectent

Détermination de la position sur l'image projetée

Nous pouvons revenir à nos trois possibilités, que je te rappelle:
1. Les deux triangles ne se touchent pas
2. Il y a intersection entre les côtés des deux triangles
3. L'un des deux triangles est complètement compris dans l'autre

Regardons tout d'abord le troisième cas. Pour tester ce cas, il suffit de vérifier si les trois sommets d'un des deux triangles sont tous les trois à l'intérieur de l'autre triangle. Ce qui fait 6 tests en tout. Si tous les sommets sont à l'intérieur alors le triangle est à l'intérieur. Attention, si tous les sommets d'un triangles sont à l'extérieur de l'autre, ça ne signifie PAS que le second triangle est à l'intérieur du premier !!!

Pour le second cas, pour chaque côté du triangle <math>\(\mathcal{A}\)</math> et pour chaque côté du triangle <math>\(\mathcal{B}\)</math> il faut regarder s'ils s'intersectent. Ce qui fait 9 tests en tout. S'il y a au moins une intersection, alors il y a bien intersection entre les triangle (et on retient ce point d'intersection)

Si on n'est dans aucun de ces deux cas, c'est que nous sommes dans le troisième cas où il n'y a pas d'intersection du tout entre les deux triangles.

Analyse des résultats

Maintenant, analysons les résultats obtenus.

Si nous sommes dans le premier cas (un triangle est complètement compris dans l'autre), il suffit de prendre une coordonnée en <math>\((x,y,0)\)</math> qui appartient aux deux triangles projetés (par exemple un sommet du triangle intérieur), et de regarder lequel des deux points est au dessus (en regardant la hauteur sur l'axe <math>\(z\)</math>). Dans ce cas, soit le petit triangle est totalement occulté par le grand, soit le petit triangle vient se dessiner à l'intérieur du grand.

Si nous sommes dans le cas d'une intersection entre les deux triangles, tu as sauvé un point d'intersection. Même travail, tu regardes quel triangle est au dessus à cette coordonnée.

Enfin dans le troisième cas, les triangles ne se recouvrent pas, il n'y a donc rien à faire de particulier: l'ordre d'affichage n'a pas d'importance.

Un nouvel outil

Tu as donc maintenant un nouvel outil qui, lorsque tu lui donnes deux triangles dans l'espace, peut te répondre que l'un est au dessus de l'autre, ou te répondre que ça n'a pas d'intérêt (trois réponses possibles). Cet outil va être utilisé pour la suite.

Comment faire avec plus de deux triangles ?

Il faut commencer par synthétiser toute l'information. Imaginons que tu as <math>\(n\)</math> triangles. Tu crées alors une matrice <math>\(n \times n\)</math> et tu utilise l'outil qu'on vient de créer pour chaque paire de triangle. Attention, ce sera une matrice dont la diagonale n'a pas d'intérêt et dont les données sont dupliquées, inutile de tout calculer deux fois ! Tu auras donc <math>\((n-1) + (n-2) + (n-3) + \dots + 2 + 1 = \frac{n(n-1)}{2}\)</math> utilisations de l'outil que l'on vient de construire.
Dans chacune des cases de la matrice, concernant les triangles i et j, tu indiques par exemple:
-1 si le triangle i est au dessus de j
1 si le triangle j est au dessus de i
0 si ça n'a pas d'importance.

Une fois que tu as cette matrice, tu peux vraiment oublier ta notion de triangle, toute l'information dont tu as besoin est dans la matrice.

Ce que je te propose (mais là je suis moins doué, peut-être que de meilleurs algorithmes existent), c'est de procéder en <math>\(n\)</math> étapes. A chaque étape, tu choisi le triangle qui possède le moins de triangles en dessous de lui (il suffit de lire la ligne ou la colonne et de compter les 1 ou -1 selon le cas). Tu trouveras très souvent plusieurs triangles avec le même nombre d'autres en dessous (souvent 0 d'ailleurs), dans ce cas, parmi ceux-là tu choisi celui qui a le plus de triangles au dessus de lui, s'il y a encore plusieurs candidat, alors choisi celui dont le barycentre est le plus bas.
Une fois que tu as trouvé ce triangle, tu le place dans ta liste ordonnée, tu supprime sa ligne et sa colonne dans la matrice.

Et tu continues ainsi jusqu'à ce que ta matrice soit vide. Tu obtiens ainsi une liste ordonnée qui devrait être pas trop mauvaise pour ton ordre d'affichage.