Détection de Collision entre Tétraèdre

[leolio]

Bonjour,

Je suis élève en 1ère année de prépa et je cherche une formule ou un test qui permet de savoir si deux tétraèdres sont enchevétrés l'un dans l'autre ? ou bien à détecter si une face est enchevétrés dans une autre ?

Si quelqu'un sait résoudre cette énigme pour moi, je le remerci par avance.

:we:

[BQss]

Bonjour,

Je suis élève en 1ère année de prépa et je cherche une formule ou un test qui permet de savoir si deux tétraèdres sont enchevétrés l'un dans l'autre ? ou bien à détecter si une face est enchevétrés dans une autre ?

Si quelqu'un sait résoudre cette énigme pour moi, je le remerci par avance.

:we:

Ba l'equation de ton tetraedre dans l'espace, est composé des equations des quatres plans qui la compose(normalement tu as au sein meme d'un plan les condition liant deux variables pour delimiter les contours du triangle).
Si deux plans des deux tetraedres ont la meme equation, c'est que les tetraedres ont une face commune.

[mathelot]

qui permet de savoir si deux tétraèdres sont enchevétrés l'un dans l'autre
:we:

d'intersection non vide..

[mathelot]

qu'est-ce que tu attend comme réponse à tes questions ?
- s'il existe un test pour dire si deux tétraèdres sont d'intersection
non vide ? oui
- comment déterminer ce test ?
par exemple, considérer les tétraèdres comme enveloppes convexes
de leurs quatre sommets, puis exprimer en coordonnées barycentriques
le fait que leur intersection est non vide
- faire les calculs ?
- les programmer ?

[leolio]

Non, je ne cherche pas à savoir si mes tétraèdres ont une face commune ou pas, cela serait trivial et je n aurai donc pas posé la question.

Si un premier tétraèdre est constitué des coordonnées suivantes :

A = (0,0,0)
B = (2,0,0)
C = (1,2,0)
D = (5.1.2)

et le second avec les coordonnées suivantes :

A = (4,0,0)
B = (6,0,0)
C = (5,2,0)
D = (1.1.2)

Je cherche vraiment à déterminer par un test ou une équation que je dois programmer si deux tétraèdres sont enchevétrés l'un dans l'autre, forme inaproprié pour ce que je cherche à faire.

Merci d'avance à celui qui résout cette enigme.

[mathelot]

qu'appelle tu "A et B enchevétrés" ? :
- non vide
-
-

[mathelot]

si l'on programme de façon bourrine:
on considère le 1er tétraèdre ABCD.
avec
idem pour les points B,C,D.
Ensuite, par exemple pour avoir l'équation du plan (ACD)


puis on calcule les coordonnées d'un vecteur normal au plan (ACD):
calcul des coordonnées de vectoriel :



puis équation du plan (ACD):

ensuite on teste le signe de cette application affine évaluée sur les coord. de B:


l' intérieur du tétraèdre est donnée par quatre équations dont la premiere
est donnée par:

le tétraèdre est donnée par quatre équations dont la premiere
est donnée par:

[mathelot]

soit
l'application affine délimite trois régions de l'espace.
Comme il y a 4 applications affines de même forme que
le tétraèdre ABCD détermine régions de l'espace.
exemple d'une région:
et et
Ensuite, on considère un deuxième tétraèdre quelconque EFGH:
il suffit de tester à quelles régions appartient E puis F puis G puis H.
ça fait donc 81^4 cas, soit
43046721 cas à tester au maximum !!

[mathelot]

finalement, ça ne marche pas car les différentes régions ne donnent pas des cas disjoints. Pour l'instant, j'étudie la question pour deux triangles dans le plan, les tétraèdres étant une généralisation des triangles à la dimension 3.

[leolio]

Je te remercie, je creuse aussi la question de mon coté.

:happy2:

[mathelot]

g une solution à proposer:
soient ABCD et EFGH deux tétraèdres quelconques (24 coordonnées).

principe de base: trois cas exclusifs sont possibles:
1) il y a une face de ABCD et une face de EFGH qui s'intersectent
2) ABCD et EFGH sont disjoints
3) l'un est inclu strictement dans l'autre

On va écrire une routine informatique pour tester le cas (1).
accepte en entrée 18 coordonnées, les coordonnées
des six sommets ABC;EFG de deux triangles quelconques.


Lemme: si ABC est un triangle, tout point de son enveloppe convexe est obtenu comme barycentre à coefficients positifs de somme égale à 1, de A,B,C.

la routine teste si deux faces ABC et EFG ont au moins un
point d'intersection:
on écrit donc cinq équations à 6 inconnues a,b,c,u,v,w:





et six inégalités:

[mathelot]

le systeme composé de cinq égalités et six inconnues et six inégalités
s'enrichit de deux nouvelles égalités. En effet
ABC sont coplanaires. Ecrivons l'équation normalisée de leur plan (ABC):

avec
En faisant des combinaisons linéaires d'égalités du système, il vient:

de même, EFG sont coplanaires:
Ecrivons l'équation normalisée de leur plan (EFG):

avec
il vient:

[mathelot]

D'où finalement , un système (S) à 6 inconnues a,b,cu,v,w, 7 égalités et 6 inégalités:

[mathelot]

Les deux premières égalités permettent de se ramener à un système
à 4 inconnues a,b,u,v et cinq équations:
Il ne reste plus qu'à discuter ce système selon la méthode de Cramer.
La routine accepte donc en entrée six points ABC,EFG
formant deux triangles et renvoie:
1 si ABC et EFG ont un point commun
0 si ABC et EFG sont d'intersection vide.
Ensuite; on ecrit un programme principal qui appelle
la routine avec les 16 couples de faces.
ABC et EFG,
ABC et EFH,
ABD et FGH etc..
si la routine renvoie 1, les tétraèdres se chevauchent.
si la routine renvoie tjrs 0, les tétraèdres sont disjoints
ou inclus.
j'évalue ça à 300 lignes de code.

[nabukodonozor]

C’est quoi ca un monologue.....