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.

[zenux]

1), 2) Oups, je me suis trompé pour la définition du triangle, il faut bien trois points et pas un seul .
Ma structure actuelle ne met permet pas de trouver les triangles adjacents facilements. Pour savoir si deux sommets sont les mêmes: il suffit des comparer leur valeurs X, Y et Z.
Mais de toute façon, je ne pense pas qu'il est nécessaire de connaitre les triangles adjacents pour l'algo.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
struct Vector3{
 float X, Y, Z;
}
 
struct Triangle{
  Vector3 sommets[3];
  Vector3 normal;
}
 
struct FormConvex{
  std::list<Triangle> triangles;
}
 
struct BBox{
 Vector3 min, max;
}

3) C'est un bête conteneur. Disons la std::list du C++ ou un tableau de triangles si vous préférez.
4) Je ne suis pas sûr de comprendre. C'est impossible de définir une bbox avec seulement un vecteur. Une bbox peut être définit soit par 2 points: un min et un max. Soit par 1 points et 1 vecteur qui fait la diagonale.
5) Pour avoir qq chose qui représente mon parallélipipède. Oui, il n'y a qu'une bbox.
6) J'ai mis un attribut 'normal' dans ma class Triangle car j'ai déjà dû la calculer pour un autre algo. Si la normale est nécessaire à l'algo et bien tant mieux, sinon tant pis.

[Invité]

Donc, ce que vous appelez Vector3 est un Point.
La normale d'un triangle est un vecteur, et non un point.
Si le vecteur est glissant, il est défini par ses composantes, dans le cas de la normale d'un triangle, pour être vraiment utile, il vaut mieux connaitre son origine. Mais naturellement on peut l'appliquer au centre de gravité du triangle.
Pour la liste de sommets, d'abord, il y a un problème d'occupation mémoire. Comme un sommet appartient à 6 triangles, l'information est répétée 6 fois.
Concernant la comparaison des X Y et Z. En général, la comparaison de flottant avec '==' n'est pas bonne. Il y a eu une longue discussion à ce sujet dernièrement. Puisque votre forme est définie par des triangles, il me parait très important de connaitre les 3 voisins d'un triangle. Si vous ne faites pas cela vous allez très vite être bloqué. Et même, il faut adopter une sens conventionnel.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// triangle 3D
typedef struct DlyTRIANGLE  // un triangle
{
	int NumCoul;	//  de 1 à 4 si rensiegné
                        //nécessaire pour le traitement des 4 couleurs
	Point3D *p1,*p2,*p3;		//Pointeurs sur les sommets
	DlyTRIANGLE *t1,*t2,*t3;	//pointeurs vers les voisins
	TPointLong centre;	//centre defini comme la structure, mais en 2d donc le z ne sert a rien
	long rayon; //rayon du cercle circonscrit au triangle calculé avec DistUB
        bool MajTri(DlyTRIANGLE *anc, DlyTRIANGLE *nouv);
        bool IsAppTri(TPointLong plu, bool strict=true);
        bool AttribLaCoul(int NumCoul);
        bool IsLimite(); // return true s'il est en limite de zone
        bool DiagFausse(DlyTRIANGLE *Tr2, Point3D *Pc1, Point3D *Pc2);
        float DetZtr(TPointLong plu);
        DlyTRIANGLE(){p1=p2=p3=NULL;
                      t1=t2=t3=NULL;
                      rayon=MAXLONG; // sert de test de validité
                      CbrUtilise=MAXFLOAT;
                      NumCoul=0;}
        void CentreR()
        {
          centre= Centre3Points(p1,p2,p3,false);
          rayon=DistUB(centre,p1->XY());
        }
}DlyTriangle;
typedef DlyTriangle* ptrDlyTr;

Pour info, voila ma structure Triangle. Mais c'est un exemple, pas forcément un modèle.
Pour la BBox, naturellement il faut 2 points, mais pourquoi faire une structure?

Code :

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

1
2
3
4
5
6
7
8
struct POINT3D
{
  float X;
  float Y;
  float Z;
};
  POINT3D BBoxMin;  
  POINT3D BBoxMax; // suffit largement, et c'est plus clair

De la même façon, il est inutile de créer une struct FormConvex.

Un élément très important, votre forme est du vrai 3D ou du 2D avec un Z.
En matière de performances, c'est pas du tout le même chose.

Quand on fait des tests très répétitifs, par exemple la position relative d'une forme 3D et d'un parallélépipède, il est très important de faire d'abord les tests qui sont rapides et ont une forte probabilité d'être concluants. Par exemple, statistiquement, le parallélépipède est petit ou grand par rapport à la forme? Autrement dit, il faut faire l'algorithme en fonction des données les plus probables.

Il y a un point qui a été peu évoqué : pourquoi est-ce important (c'est dans les hypothèses) que la forme soit convexe? D'ailleurs, ce point m'étonne un peu, dans quel type d'application une forme 3D est toujours convexe ?

[zenux]

Donc, ce que vous appelez Vector3 est un Point.
La normale d'un triangle est un vecteur, et non un point.

Ma classe Vector3 fait double emploi: soit elle réprésente un point, soit un vecteur ça dépend du context. Si cela pose problème, il suffit de créer deux classes identiques

Si le vecteur est glissant, il est défini par ses composantes, dans le cas de la normale d'un triangle, pour être vraiment utile, il vaut mieux connaitre son origine. Mais naturellement on peut l'appliquer au centre de gravité du triangle.

L'origine de ma normal: c'est le centre de gravité.

Pour la liste de sommets, d'abord, il y a un problème d'occupation mémoire. Comme un sommet appartient à 6 triangles, l'information est répétée 6 fois. Concernant la comparaison des X Y et Z. En général, la comparaison de flottant avec '==' n'est pas bonne. Il y a eu une longue discussion à ce sujet dernièrement.

Pourquoi un sommet appartiendrais à 6 triangles ? Il peux très bien appartenir à 3 triangles ou jusqu'a une infinitée de triangles !
L'occupation mémoire ne me dérange pas, c'est loin d'être dramatique dans mon cas.
Pour la comparaison de float: c'est tjs OK dans mon cas: donc pas de soucis de ce côté là et ce n'est pas vraiment le sujet.

Puisque votre forme est définie par des triangles, il me parait très important de connaitre les 3 voisins d'un triangle. Si vous ne faites pas cela vous allez très vite être bloqué. Et même, il faut adopter une sens conventionnel.

Pour l'instant, j'en ai pas besoin. Si il y a en a besoin pour déterminer si deux formes sont sécantes, je m'arangerai pour avoir une autre structure.

Il y a un point qui a été peu évoqué : pourquoi est-ce important (c'est dans les hypothèses) que la forme soit convexe? D'ailleurs, ce point m'étonne un peu, dans quel type d'application une forme 3D est toujours convexe ?

C'est pas une question d'importance: ma forme est convexe et c'est comme ça.
Mon type d'application: c'est de la programmation 3D mais on s'écarte du sujet.
Voici l'explication: http://http.developer.nvidia.com/GPU...gems_ch15.html (voir 'Shadows for Lights Outside a Frustum').

[Invité]

Bonjour,

Ma classe Vector3 fait double emploi: soit elle réprésente un point, soit un vecteur ça dépend du context. Si cela pose problème, il suffit de créer deux classes identiques

Ca ne coutera pas plus cher de différencier les points des vecteurs. J'y vois 3 avantages
1- le code sera compréhensible
2- une classe étant normalement faite pour définir un objet, les fonctions de cet objet n'ont aucun rapport selon que c'est un point ou un vecteur.
3- la définition des différents éléments du programme aura été réfléchie, et non "pondue" à la demande.

Pourquoi un sommet appartiendrais à 6 triangles ? Il peux très bien appartenir à 3 triangles ou jusqu'a une infinitée de triangles !

Naturellement, il s'agit de 6 triangles EN MOYENNE . J'avais bien pris soin de le préciser la première fois que j'en ai parlé.

L'occupation mémoire ne me dérange pas, c'est loin d'être dramatique dans mon cas.

Oui, mais ce qui vous a manifestement échappé, c'est qu'il y a aussi 6 fois plus de calculs à faire

Pour la comparaison de float: c'est tjs OK dans mon cas: donc pas de soucis de ce côté là et ce n'est pas vraiment le sujet.

Je suppose qu'à un moment du calcul, vous allez faire quelque-chose comme :

Code :

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

1
2
3
4
5
float rap;
  if (x1 != x2) 
    rap = (y1-y2)/(x1-x2);
  else
    ...

et tant-pis pour vous si (x1-x2) est égal à zéro.

Pour l'instant, j'en ai pas besoin. Si il y a en a besoin pour déterminer si deux formes sont sécantes, je m'arangerai pour avoir une autre structure.

Traduction : rajouter une verrue

C'est pas une question d'importance: ma forme est convexe et c'est comme ça.

Oh si, c'est très important : dans le cas d'une forme convexe, le plan défini par l'un quelconque des triangles ne coupe aucun autre triangle.

[zenux]

Naturellement, il s'agit de 6 triangles EN MOYENNE . J'avais bien pris soin de le préciser la première fois que j'en ai parlé.

Quel calcule faites-vous pour trouver 6 de moyenne ? Ca n'a aucun sens, la moyenne dépend du contexte/population !

Oui, mais ce qui vous a manifestement échappé, c'est qu'il y a aussi 6 fois plus de calculs à faire

Non, ça ne m'échappe pas et je suis tout à fait au courrant que je devrais encore améliorer ça.

...et tant-pis pour vous si (x1-x2) est égal à zéro.

Non ce n'est pas ce que j'ai dit. J'ai juste dit qu'il était possible de comparer 2 sommets avec '==' et que je suis sûr à 100% que ça retourne 'true' si les 2 sommets sont les mêmes.

Oh si, c'est très important : dans le cas d'une forme convexe, le plan défini par l'un quelconque des triangles ne coupe aucun autre triangle.

Ok, j'ai du mal comprendre votre question précédente. Ce que je peux dire: ma forme est convexe et il n'en sera pas autrement.

Après tout ça, j'ai l'impression de ne pas vraiment avancer sur mon problème d'origine
Pour l'instant, l'algo le plus rapide que j'ai trouvé est le suivant:

1) Tester les min et les max pour chaque axe (X, Y et Z). Si le test est faux, je retourne 'false' car on est sûr que le bbox n'est pas dans la forme convexe.
2) Tester si un ou plusieurs points de la forme convexe sont à l'intérieur du bbox. Si oui: la bbox est à l'intérieur de la forme convexe, je retourne 'true'.
3) Tester si un ou plusieurs point du bbox est à l'intérieur de la forme convexe. Si oui: la bbox est à l'intérieur de la forme convexe, je retourne 'true'. Si non: return 'false'.

[Invité]

Quel calcule faites-vous pour trouver 6 de moyenne ? Ca n'a aucun sens, la moyenne dépend du contexte/population !

C'est comme ça on n'y peut rien, mais je ne saurais pas le démontrer, là tout de suite, à froid.

Je crois que le mieux pour vous est d'écrire l'algorithme et de le tester.

[Nebulix]

Il est très simple et très rapide de tester si les sommets de ton polyèdre sont dans la bbox (6 comparaisons par sommet).
Le Pb est beaucoup plus complexe si la bbox est suffisamment fine pour pénétrer dans le polyèdre par un triangle sans inclure de sommet , voire de ressortir pareil. La première question est donc : ce cas peut-il se produire ou la bbox est-elle plus grande que tous les triangles ?

[zenux]

Après quelques jours d'absence, me revoila.

ce cas peut-il se produire ou la bbox est-elle plus grande que tous les triangles ?

Oui, toutes les cas peuvent se produire: la bbox peut être plus grand que la forme convexe ou inversement.

J'ai implémenter mon algo que j'ai décrit dans mon dernier commentaire et je viens de remarquer qu'il n'est pas juste. Il ne recouvre pas ce cas: http://img713.imageshack.us/img713/6893/errh.jpg (vue du dessus)
Je suis donc toujours à la recherche d'un algo pour mon problème.

[Nebulix]

Oui, toutes les cas peuvent se produire: la bbox peut être plus grand que la forme convexe ou inversement.

La question exacte est : la plus petite dimension de la bbox est-elle plus grande que le plus grand côté de triangle de la forme ? (on peut affiner ).
Si oui, il suffit de tester si les sommets des triangles sont dans la bbox.
Si non je couperais en deux le "triangle au plus grand côté" par la médiane du plus grand côté le nombre de fois nécessaire pour se ramener à cette condition