collison 3D

voila j'ai un petit souci dans mes detections de collision.
le test de collision entre un point et un pavé orienté n'importe comment dans l'espace s'effectue sans souci.

le probleme que j'essaye de resoudre c'est de connaitre la face par laquelle je suis rentré dans le cube en ne connaissant que la position a l'instant (t) et a l'instant (t-1)

une solution c'est:
de trouver le point d'intersection entre les plans et la droite engendree par le vecteur v = pos(t) - pos(t-1) passant par pos(t)
puis de calculer la longueur algebrique entre le point pos(t-1) et le point d'intersection.

la longeur algebrique la plus courte et positive entre les 6 faces sera la bonne.
mais bon ca fait beaucoup de calculs...

si vous aviez une idee, je suis preneur
cppDupDup34

voila une tite image

cppDupDup34

Calculer un point d'intersection, c'est jamais bon en calcul.

Pour éliminer 3 faces sur 6: vecteur T = pos(t) - centre_du_cube.
si le produit scalaire de T par un vecteur normal d'une des faces du cube est négatif, alors l'objet est de l'autre coté de cette face, et ne peut donc pas rentrer en collision avec cette face.

Pour la suite:
Ca peut etre rapide, mais il faudrait plusieurs élement en mémoire.
L'idée c'est de voir dans quel volume engendré par une face du cube et son vecteur normal, l'objet se trouve.

Deja, tu connais l'orientation de ton cube, donc tu peux avoir la matrice de changement de base, entre les coordonnées 3d, et une base liée a ton cube. (une base orthonormale sympathique, telle que ses vecteurs soient normaux aux faces)

si M c'est la matrice de transfert des coordonnées 3d à la base du cube. et M' l'inverse (sa transposée puisque M est une matrice de rotation) (en passant, M s'obtient facilement et la méthode est rapide si ton cube bouge pas, s'il bouge, faut faire 3 calcul matriciel en plus).

Si O est le centre du cube, soit vecteur P = Pos(t) - O, donc P est le vecteur allant du centre du cube à ton objet. alors P ' = M ' x P, c'est les coordonnées de ton objet dans la base du cube.
Et la c'est fini. Tout dépend comment tu as choisis la base. Mais tu compares les coordonnées avec les demi coté de ton pavé (ou cube). Ca permet de savoir quel est la face en question parmi les 3 qui restaient.

Donc en résumé, ca donne:
6 produits scalaires.
1 calcul matriciel.
2 comparaisons.

Si ta des questions :)
j'essais de faire une image

suite:
Je sais pas comment tu fais ton test de collision, si tu détectes une collision, il faut donc seulement effectuer la deuxième partie du test (produit matriciel et test de comparaison).

Mais je sais pas comment on insère une image donc...

Si tu cherche à faire un moteur physique en 3d il faut détecter les collisions entre ton point et ton volume d'une autre façon:

le meilleur moyen de savoir si ton point est entré en collision est de chercher un plan séparant tout les points de ton volume d'un coté et ton point seul de l'autre. Pour trouver ce plan il faut tester tout les plans qui sont les faces de ton volume à l'aide du produit vectoriel. Si tu trouve ce plan c'est que ton point seul n'est pas dans le volume, il n'y a pas de collision. Si en revanche tu ne trouve pas de plan, c'est qu'il y a collision, et la la méthode de l'intersection plan/droite va te servir.

Avec la méthode des plans tu peut optimiser ton programme grace à la cohérence temporelle: lorsque tu cherche le plan de séparation entre le point seul et les points de ton volume tu commence par regarder si le plan qui les séparait à l'étape précédente les sépare toujours. Si oui, c'est pas la pein d'aller plus loin il n'y a pas de collision. Sinon bah tu peu tester tout les plans comme au début, ou alors si tu veut la jouer pro utiliser les diagrammes de Voronoy: méthode qui consiste à tester les faces à proximité de la face de l'étape précédente en priorité (toujours grace à la cohérence temporelle).

Petite précision: ces méthodes s'appliquent à des volumes convexes, pour des volumes concaves ça se corse.

neodelphi

si j'ai bien compris ca donne ca:

les faces 1, 2 , 5 eliminées car produit scalaire positif
restent 4, 6 et 3

pour le second test par contre j'ai pas pigé l'histoire des demi volumes
j'utilise bien les matrices pour connaitre la position relative de mon point par rapport au cube et ainsi tester s'il est a l'interieur ou non mais j'ai du mal a voir comment cela permet d'eliminer deux autres faces

neodelphi --> "Pour trouver ce plan il faut tester tout les plans qui sont les faces de ton volume à l'aide du produit vectoriel"
la je comprends pas quel est le test correspondant au produit vectoriel je dois faire le produit entre koi et koi ?

merci pour votre aide

cppDupDup34

Le produit vectoriel est lourd en calcul et le calcul d'un point d'intersection est lourd également, donc je vois pas l'utilité de chercher ton plan de séparation.

Chercher un plan de séparation est ce qu'il y a de plus courant grace aux méthodes d'optimisation avec la cohérence temporelle, on le retrouve dans beaucoup de moteurs physiques actuels. 

Euh finalement c'est pas avec le produit vectoriel mais le produit scalaire je croit. Tu prend une face de ton volume, un triangle en général, tu applique un produit vectoriel entre deux cotés du triangle pour calculer la normale à la surface. Ensuite tu fait le produit scalaire entre cette normale et le vecteur qui part d'un point du triangle au point que tu teste. En fonction du signe de ce produit scalaire tu est capable de déterminer de quel coté de la face ton point est. Comme tu a un solide convexe, tout les points de ton solide sont du meme coté du triangle, donc si le point est de l'autre coté, tu as trouvé un plan de séparation.

De plus un produit vectoriel n'est pas lourd du tout a effectuer, c'est juste des additions et des multiplication. Ce qui est lourd c'est chercher le point d'intersection entre un plan et une droite à cause des divisions et des tests de colinéarité, c'est pour ça qu'il faut le faire que si tu est sur qu'il y a collision.

neodelphi

Bas un produit vectoriel, c'est quand meme 12 multiplications. Mais si ca règle le problème du facteur temporelle c'est pas mal. Car ce que je proposais ne fonctionne que si le fps est élevé.

Mais le problème posé, n'était pas déterminé s'il y a collision, mais quelle face est touchée.

Ouai mais avant de chercher quelle face est touchée, faut savoir si il y a collision...
De plus, une fois que tu sais qu'il y a collision, grace à la cohérence temporelle la face touchée est à 95% le plus souvent le plan de séparation de l'étape précédente. Donc si tu veut un truc super rapide, tu calcul pas la face touchée car tu as 95% de chance que ce soit le plan de séparation précédent. Les rares cas où ce n'est pas vrai c'est lorsque le point entre en collision presque sur un sommet du volume. Si ton moteur physique tourne bien, on n'y verra que du feu.

Ce qu'il faut avoir en tête quand on réalise un moteur physique pour jeux videos, c'est qu'il ne faut pas faire comme dans la réalité: un moteur physique de jeux videos se doit de paraître réaliste, et je dit bien paraître ! Il faut laisser tomber toutes les exception, et s'arranger pour que ça rende bien (d'où la prise du plan de séparation précédent, plan qui parait réaliste).

Si tu est physicien il faut que tu oubli la physique un moment pour faire ton moteur car sinon tu deviendrai maboul, une vrai simulation est tellement compliquée à mettre en place qu'elle serait bien trop lente pour les jeux videos...

neodelphi