Discussion :

[Nebulix]

Autant pour moi, j'ai oublié le cas où un coin de bbox pénétrait légèrement un triangle.
Il faudra tester que les sommets de bbox sont ou non à l'intérieur de la forme.

[zenux]

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

Parfois oui, parfois non: tout est possible.

Donc si j'ai bien compris, l'algo est le suivant:
1. On test si un point de la forme convexe se trouve dans une des bbox. Si c'est le cas: return INSIDE.
2. Je découpe ma bbox en plusieurs bbox de taille inférieur au plus petit triangle de la forme convexe. On test si un point d'une bbox se trouve dans la forme convexe. Si c'est le cas: return INSIDE.
3. return OUTSIDE.

Pas très performant comme test (surtout si mon plus petit triangle est très petit). N'y a t-il pas moyen de faire mieux ?
Si à la place d'une bbox, j'ai une sphere qui englobe cette bbox: est-ce qu'il y a moyen de faire beaucoup mieux ?

Merci d'avance.

[Nebulix]

En maths, il faut être précis si on veut arriver à un résultat. Ta phrase "On test si un point de la forme convexe (fc) se trouve dans une des bbox." ne veut rien dire mathématiquement , on ne peut tester que les sommets des triangles.
IL y a deux autres possibilités (sauf si je me trompe):
1)Un coin de bbox peut être dans fc. C'est le + difficile à tester. J'espérais pouvoir l'éviter mais je me trompais.
2) les solides s'intersectent sans qu'aucun des sommets de l'un ne soit dans l'autre. C'est dans ce cas que la division des triangles est utile.

Avec une sphère, le calcul devient analytique et trivial.

[zenux]

Ok, merci, j'ai bien compris l'algo et je pense qu'il fonctionne dans toutes les situations

Mais je ne suis vraiment pas satisfait de cet algo niveau performance. En effet, la division des triangles risque de faire chuter les performances énormément !
Si quelqu'un à une meilleure idée, je suis preneur.

[Nebulix]

Je viens de trouver un contre-exemple !
à suivre

[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.

[zenux]

Bonjour,

Pour info, j'ai trouvé la solution: c'est algorithme GJK. Il permet de tester si deux formes convexes sont en collision et si on le souhaite on peux déterminer la distance entre les deux convexes. Ce n'est surement pas le plus simple algortihme à comprendre mais il me semble très performant.

Vidéo (en anglais): http://mollyrocket.com/849
Code source: https://mollyrocket.com/forums/viewtopic.php?t=797