Discussion :

[zenux]

Bonjour,

J'ai deux formes géométriques en 3D:
- Parallélépipède rectangle aligné sur les 3 axes X,Y,Z et définit par 2 points: Pmin(X, Y, Z) et Pmax(X, Y, Z). Aussi appellé 'axis-aligned bounding box'.
- Une forme géométrique convexe définit par une liste de triangles. Chaque triangle possède une normale qui permet de définir la direction du triangle. La direction de toutes les normales sont vers l'extérieur de la forme géométrique convexe.

Ma question: comment savoir si mon parallélépipède rectangle se trouvent soit:
- en partie ou totalement dans ma forme géométrique convexe (pas de distinction necessaire entre les deux).
- ou se trouve en dehors dans ma forme géométrique convexe.

Info: je cherche l'algo le plus rapide et pas forcément le plus beau

Merci d'avance.

[math_lab]

Si ta box est toujours plus petite que ton mesh, tu peux juste regarder si au moins un sommet se trouve a l'interieur de l'objet. Le test est assez simple: pour chaque sommet de la boite, tu parcours tous les triangles de l'objet et tu regardes de quel coté il se trouve (il suffit de regarder le dot product entre la normale et un vecteur partant du triangle et allant vers le sommet a tester). Si un de ces tests te dit que le point se trouve du coté exterieur d'un triangle, vu que ton objet est convexe, tu peux etre sur que le point n'appartient pas a ton objet.

Vu que tu n'as pas besoin de savoir si ta boundinx box est completement a l'interieur, tu peux arreter le test quand tu trouves un point a l'interieur. Cet algo est pas forcement le plus beau ou le plus rapide, mais c'est le plus simple a ma connaissance.

[Nebulix]

Le plus rapide à programmer ou le plus rapide à l'execution ?
Dans le 2e cas c'est que tu as besoin de l'appeler souvent. Qu'est-ce qui varie d'un appel à l'autre ?

[math_lab]

La vitesse d'execution est liée au nombre de polygones. Si tu as plusieurs millions de polygones dans ton mesh, ca risque d'etre assez lent... La bonne nouvelle, c'est qu'il suffit d'avoir un test qui echoue (point du coté externe du triangle) pour pouvoir rejetter le point de la bounding box. En gros, savoir si la bounding box est au moins en partie dedans est super rapide, savoir si elle est en dehors ou si elle englobe le mesh (pas moyen de les distinguer) est aussi rapide, et savoir si la box est completement a l'interieur peut etre lent.

[Invité]

Je pense qu'une première étape dans ce type de test est de calculer les min et max de la forme géométrique. Si ces deux box ne sont pas sécantes (test immédiat) il n'existe aucune intersection.
Je suppose que votre forme géométrique est du vrai 3D, c'est à dire que la notion de verticale n'existe pas et que les dimension extérieures de l'objet sont du même ordre, cad la plus petite différence entre min et max d'une coordonnée est supérieure à 10% de la plus grande différence suivant une autre direction.

En fait, je ne chercherais pas à savoir si un triangle est sécant ou intérieur au parallélépipède, mais je m'intéresserait uniquement aux sommets. Si on trouve un sommet intérieur ET un sommet extérieur, les deux formes sont sécantes. ( dans tous les autres cas, elle sont disjointes --> FAUX).
Si le test précédent est négatif, si tous les sommets de triangles sont intérieurs, alors l'objet est entièrement contenu dans le parallélépipède. Sinon, il faut vérifier qu'aucun triangle ne coupe le parallélépipède. Le pense que la solution est de vérifier les intersections des côtés des triangles avec les projections du parallélépipède sur ses 3 plans.
Mais naturellement, sous toutes réserves.

[zenux]

Merci pour vos réponses.

@Nebulix & math_lab: Je cherche un algo rapide à l'éxécution (pas de problème si c'est long à programmer). Mon mesh ne contient pas des millions de triangles mais j'ai besoin d'éxécuter l'algo plusieurs fois par seconde.

@math_lab: Ton algo me parait bien mais j'ai oublié de préciser un "petit" détail: la bounding box peut être plus grande (ou plus petite) que la forme convexe. Je ne trouve pas d'algo simple/rapide pour se genre de situation.

Merci d'avance.

[zenux]

Up. Personne n'a une idée ?

Je viens de remarquer que l'algo de math_lab est faux: en effet, tous les points de mon parallélépipède rectangle peuvent être à l'éxtérieur tout en ayant mon parallélépipède qui coupe la forme convexe !

La solution de Pierre Dolez me parait plus complète mais je ne comprends pas bien ceci: "Sinon, il faut vérifier qu'aucun triangle ne coupe le parallélépipède" -> comment faire ça ? De plus, je crois que cet algo ne fonctionne pas si le parallélépipède rectangle est plus grand que la forme convexe.

[souviron34]

ce qu'il veut dire est que le premier test est (relativement) immédiat si tu as les min,max de ta forme convexe..

En 2D, ça donne :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
si ( BBxmax < Formexmin ou BBxmin > Formexmax)
    PAS SECANT
sinon
    si ( BBymax < Formeymin ou BBymin > Formeymax)
        PAS SECANT
    sinon
         calculer pour chaque triangle (éventuellement en ayant éliminé (par moitié, ou autres)
          les intersections
    fin si
fin si

[Invité]

Bonjour Xenus,
Le premier test examine si la forme convexe est entièrement contenue dans la parallélépipède ou entièrement extérieure.
Entièrement contenue si tous les min et max de la forme sont compris dans les min et max de parallélépipède.
Entièrement extérieure si tous les min et max de la forme sont en dehors des min et max de parallélépipède.
Sécants si l'une des condition n'est pas vraie.
Le crois que dans tous les cas on devrait réussir à faire le test avec uniquement des comparaisons sur les 3 plans de projection, et sans aucune opération arithmétique.

Même, je veux bien vous l'écrire, en pseudo-code, en C, en C++, même en PHP, mais il faudrait que vous me décriviez votre structure de départ, c'est à dire, les triangles, le parallélépipède, ce qui bouge etc.

[zenux]

Bonjour,

Merci pour vos réponses.

Entièrement contenue si tous les min et max de la forme sont compris dans les min et max de parallélépipède.

Cette phrase me semble fausse, exemple en 2D qui le prouve: http://img697.imageshack.us/img697/4528/bbox.jpg (désolé pour le dessin, je n'ai pas trouvé l'outil pour tracer des lignes )
Rappel: la forme convexe peut être plus grande que le parallélépipède ou inversément.

- Faire le test de min & max, ça je sais faire.
- Ce que je sais aussi faire: dot product entre la normal du triangle et le le vecteur entre le triangle et un point afin de savoir de quel côté se trouve ce point.
- Le reste, je ne sais pas faire (je ne suis pas très doué en math mais je veux bien apprendre )

Je ne suis pas contre un algo (même très simplifé) en pseudo-code/c/c++ (au choix). Voici ma structure simplifié:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
class Triangle{
  float X, Y, Z;
  Vector3<float> normal;
}
 
class FormConvex{
  list<Triangle> triangles;
}
 
class BBox{
 Vector3<float> min;
 Vector3<float> max;
}

[Invité]

Si j'ai bien compris votre dessin, la "forme" est un grand polygone, le parallélépipède est représenté par un petit rectangle. Je ne vois pas le rapport avec

Citation:
Entièrement contenue si tous les min et max de la forme sont compris dans les min et max de parallélépipède.

Cette description ne me convient pas

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
class Triangle{
  float X, Y, Z;
  Vector3<float> normal;
}
 
class FormConvex{
  list<Triangle> triangles;
}
 
class BBox{
 Vector3<float> min;
 Vector3<float> max;
}

1- un sommet de triangle est utilisé dans environ 6 triangles. Donc il me parait indispensable d'avoir une classe ou une structure Sommet et dans la classe Triangle, la définition des 3 sommets.
Par ailleurs, je ne comprend pas que dans Triangle il n'y ait qu'un seul point (X,Y,Z)
2- je ne connais pas la classe Vector3
3- je ne connais pas la classe list
4- si vecteur3 est un vecteur dans l'espace 3D, comme cela semble être le cas, puisque le triangle possède un vecteur normal, la BBox est parfaitement définie par 1 vecteur 3D qui est la diagonale entre min et max.
5- pourquoi une classe BBox? Y aurait-il plusieurs parallélépipèdes?
6- Je n'aime pas stocker un résultat parmi les membres d'une classe, à moins que ce résultat soit très souvent consulté et long à calculer, par exemple une aire. Dans le cas présent il vaut mieux faire

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

  Vecteur3=Normale();

Enfin, il semblait que vous vouliez un traitement rapide, je ne suis pas sûr que le calcul de l'intersection de la normale au triangle soit une méthode rapide.

[Aleph69]

Bonsoir,

Ma question: comment savoir si mon parallélépipède rectangle se trouvent soit:
- en partie ou totalement dans ma forme géométrique convexe (pas de distinction necessaire entre les deux).
- ou se trouve en dehors dans ma forme géométrique convexe.

C'est un problème standard de géométrie algorithmique.
Tu peux regarder dans cet excellent livre d'introduction (chapitre sur les intersections)

Tu peux aussi regarder cet autre livre (p 275 etc).

Mais si tu débutes en géométrie algorithmique, je te conseille vivement la lecture du premier (bien qu'il ne soit plus trop récent).

[zenux]

- J'ai regardé le premier livre et le chapitre sur l'intersection de convex polygon n'est pas visible
- Le second livre m'a l'air mieux mais pas facile à comprendre (il me semble que les schémas ne sont pas affichés correctements).

Si j'ai bien compris, l'algo en 2D est le suivant:
1. Si une arête de la forme convexe inersect une arête de la bbox: return INTERSECT.
2. Si aucune intersection n'est détecté alors on vérifie si la forme convex est entièrement contenu dans la bbox et inversément.

Pour l'algo en 3D:
1. Il faut faire la projection de mes deux formes sur le plan XY et appliquer l'algo 2D
2. Ensuite, faire la même chose sur le plan YZ.
3. Si il y a intersection sur le plan XY ET YZ: alors il y a intersection entre la forme convexe et la bbox.

Est-ce que cela vous semble correcte ? Est-ce la manière la plus performance ?

[Nebulix]

-
Pour l'algo en 3D:
1. Il faut faire la projection de mes deux formes sur le plan XY et appliquer l'algo 2D
2. Ensuite, faire la même chose sur le plan YZ.
3. Si il y a intersection sur le plan XY ET YZ: alors il y a intersection entre la forme convexe et la bbox.

Est-ce que cela vous semble correcte ? Est-ce la manière la plus performance ?

Cà c'est faux : Si tu approches le coin d'une boîte d'allumettes (coin de bbox) d'un ballon(fc) toutes les projections s'intersecteront sauf celles dans les directions tangentes au ballon .
Du point de vue mathématique, il est redoutablement difficile de considérer tous les cas possibles. Es tu bien sûr de devoir le résoudre en toute généralité ?

[Invité]

Bonjour,
Je viens de relire l'énoncé. On cherche à savoir si la boite est extérieure à la forme convexe. C'est à dire si elle est partiellement, intérieure, entièrement intérieure, elle ne sera pas extérieure. Si la boite "contient la forme" elle ne sera pas non plus extérieure.

Ce qui me parait important est que la forme est convexe. Ceci entraine que chaque triangle détermine une partition de l'espace, limitée par le plan défini par les sommets du triangle, et que l'ensemble des triangles sont d'un même côté du plan.
Il en résulte que si les 8 coins de la boite sont d'un même côté du plan (dans le bon sens) passant par chacun des triangles, la boite est extérieure.
Mais naturellement, on pourra trouver aussi un triangle dont le plan coupe la boite. Donc, il faut trouver le ou les triangles qu'il convient d'étudier.
Une première élimination (pour raison de performances) est préférable, puis il faudra déterminer le test qui servira à calculer le plan à étudier.

[Aleph69]

Bonjour,

comme je l'ai déjà mentionné, il s'agit d'un problème classique.
Il n'est pas nécessaire d'essayer de réinventer la roue.

Concernant les performances, les algorithmes standards sont de complexité linéaire, donc très rapides.

Normalement, en faisant une recherche sur les problèmes d'intersection de polygones/polyèdres convexes, tu devrais rapidement trouver ton bonheur.

Pour démarrer :
http://citeseerx.ist.psu.edu/viewdoc...10.1.1.63.2041,
et les références associées.

Egalement :
http://citeseerx.ist.psu.edu/viewdoc...10.1.1.50.7083

Evidemment, en utilisant une bibliothèque de géométrie algorithmique (computational geometry), tu pourras le faire sans rien y comprendre.