Collisions de cubes

[Temporaire]

Bonjour,

Comment peut on faire pour savoir si 2 cubes dans un espace 3D sont en collisions ?
On a comme entrées, les coordonées des sommets des 2 cubes.

Merci pour l'aide

[Ben314]

Salut,
Perso, j'aurais tendance à faire un changement de repère de façon à ce qu'un des deux cubes soit (dans le nouveau repère) [0,1]^3 puis à calculer les coordonnées des sommets du deuxième cube dans ce repère et enfin à regarder si certaines faces du 2em cube rencontrent les faces du premier.
Il y a peut être un peu plus simple (mais attention, les cubes peuvent se rencontrer sans qu'aucun des points du premier ne soit à l'intérieur du deuxième, ni le contraire)

[pascal16]

on peut commencer comme le dit Ben pour normaliser le problème.

ensuite ou directement calculer le centre du 2ieme cube
écrire les équations des 6 faces du second cube.
En vérifiant les coordonnées du centre, le signe te donne le signe des points à l'intérieur du cube.
Un point à l'intérieur du cube a les 6 signes identiques à celui du centre (tu peux inventer une fonction signature)
Si un des sommet du premier cube a le signe 'intérieur' pour les 6 faces du second cube, il est à l'intérieur.

[chan79]

Avec la norme "infini", les boules de l'espace ont des formes cubiques
A voir peut-être ... ?

[Ben314]

J'ai l'impression que ça (proche des théorèmes de Helly et de Carathéodory) c'est vrai :

Si et sont deux enveloppes convexes dans un espace affine de dimension qui s'intersectent alors il alors il existe et tels que et que les enveloppes convexes et s'intersectent.

Si c'est effectivement vrai (je regarderais si j'ai le temps...), ça signifierais que deux cubes de s'intersectent, si et seulement si l'un des sommets d'un des cubes est contenu dans l'autre (p=1, q=4 ou le contraire) ou bien l'une des arrêtes d'un des cubes coupe une face de l'autre (p=2, q=3 ou le contraire).

Numériquement parlant, ça conduit à résoudre un certain nombre de systèmes linéaires 3x3 puis a regarder ou est situé l'unique solution.

[Temporaire]

Ok,
Je pense que je vais suivre la technique présenté dans ce document :
https://www.geometrictools.com/Document ... ection.pdf

[fatal_error]

hello,

de ce que j'ai partiellement vu (https://developer.mozilla.org/en-US/doc ... _detection), ca dépend de comien de cubes tu as.
Apparemment, si t'as genre pleeein de cubes, alors peu importe leur "rotation", tu crees un cube englobant aligné sur Oxyz pour accélérer la comparaison.

Si t'as un seul cube, je pense qu'une bete comparaison brute force suffit..
pour toutes les lignes du cube, on regarde si elle intersecte une face de l'autre cube (12(arretes)*12(faces)* 2(un cube puis l'autre))=288
ce qui se fait normalement assez immédiatement.

Tu peux toujours optimiser l'affaire et considérer les sphères (pour comparer avec la distance centre centre vu que présumément la plus part du temps les cubes seront trop loins...)

[Temporaire]

Ah oui en effet je pourrais faire en brute force ça serais plus simple.

Mais dans ce cas là comment fait on pour savoir si une arête traverse une face ? Sachant que je possède en entrée uniquement les sommets des cubes.

[Ben314]

Comme déjà dit çi dessus, c'est un simple système linéaire à résoudre :
Si l'arrête s'est [AB] et la face c'est (CDEF) alors tu résous le système 3x3 et l'arrête coupe la face ssi à la fois et sont dans [0,1].

Après, comme le dit Fatal, je pense que tu as intérêt à commencer par calculer la distance de centre à centre entre les deux cubes vu que si elle est suffisamment grande [resp. suffisamment petite] tu est certain sans calculs supplémentaires que les cubes sont disjoints [resp. qu'il se coupent]. Et tu ne cherche les intersections Arrêtes/Faces que si cette distance est dans une certaine fourchette qui ne permet pas de conclure.

[Temporaire]

Je n'est pas trop compris le système a résoudre. Car la on a une ligne et 3 inconnue.

[Ben314]

Holala... mal barré là...
Tu as certes une seule équation, mais c'est une équation entre points/vecteurs de R^3 donc c'est un système de 3 équations (réelles).

[Temporaire]

Est ce que tu pourrais expliquer comment tu as trouvé cette équation ou alors tes sources pour que je puisse comprendre pourquoi on doit résoudre cette équation ?

[fatal_error]

On note les deux cubes ABCDEFGH et IJKLMNOP
on s'intéresse à une arête du cube ABCDEFGH, mettons: [AB]
on s'intéresse à une face du cube IJKLMNOP, mettons (IJKL)

si [AB] intersecte (IJKL), en un point P, alors on a
(1): (idem P appartient à la droite (AB) et si 0<=a<=1, P appartient au segment [AB])
(2)(relation de Chasles..):

(2) en particulier P est un point du plan (IJKL) donc est combi linéaire de et
idem il existe b et c des nombres tq (2.1): avec b et c positifs <= 1
<=1 parce que sinon, le point P "sortirait" du plan (IJKL).

en injectant (2.1) dans (2) il vient
(2.2):

Puis en injectant (2.2) dans (1) on retombe sur l'eq de ben:
(1.2):
où il faut trouver a,b, et c (on a trois eq vu que c'est des vecteurs 3D. une eq sur x, une eq sur y et une eq sur z)
Si on trouve a, b, c qui sont tous compris entre 0 et 1, ca veut dire que le point P appartient bien à [AB] (le segment et pas la droite) et est bien compris dans la face (IJKL) (à l'intérieur et non dans son "prolongement"), auquel cas on a montré que [AB] intersecte (IJKL)

[Temporaire]

Ok c'est compris, merci pour l'explication