Collison 3D
Résolu
cppdupdup34
Messages postés
212
Date d'inscription
dimanche 29 juin 2003
Statut
Membre
Dernière intervention
13 mai 2006
-
19 août 2005 à 14:04
cppdupdup34 Messages postés 212 Date d'inscription dimanche 29 juin 2003 Statut Membre Dernière intervention 13 mai 2006 - 23 août 2005 à 12:46
cppdupdup34 Messages postés 212 Date d'inscription dimanche 29 juin 2003 Statut Membre Dernière intervention 13 mai 2006 - 23 août 2005 à 12:46
13 réponses
neodelphi
Messages postés
442
Date d'inscription
jeudi 4 avril 2002
Statut
Membre
Dernière intervention
11 août 2008
22 août 2005 à 19:04
22 août 2005 à 19:04
Bonne question, je vais t'éclairer:
dans ce que j'ai dit je n'ai pas fait d'erreur, ce qu'il faut savoir, c'est qu'avant qu'il y ai collision, il n'y en avait pas (on ignorera les contacts permanent, ou le point n'entre pas dans le volume mais reste "appuyé dessus"). A l'étape précédente donc tu n'avait pas de collision, tu avait donc trouvé un plan séparant le point du volume. Lorsque tu détecte une collision, tu reprend le plan précédent pour savoir la surface de collision, car il y a de forte chance qu'il s'agisse de ce plan.
Ce que je te conseille maintenant c'est de prendre une feuille et un crayon, et de simuler ton bazar en cherchant vite fait le plan toi meme, tu te rendra compte très vite de l'interet de la cohérence temporelle. Tu verra également que ce n'est pas tout le temps vrai, que pour certains cas (sur les coins de ton volume) le plan n'est pas le bon, mais suffit quand meme pour donner un look réaliste.
neodelphi
dans ce que j'ai dit je n'ai pas fait d'erreur, ce qu'il faut savoir, c'est qu'avant qu'il y ai collision, il n'y en avait pas (on ignorera les contacts permanent, ou le point n'entre pas dans le volume mais reste "appuyé dessus"). A l'étape précédente donc tu n'avait pas de collision, tu avait donc trouvé un plan séparant le point du volume. Lorsque tu détecte une collision, tu reprend le plan précédent pour savoir la surface de collision, car il y a de forte chance qu'il s'agisse de ce plan.
Ce que je te conseille maintenant c'est de prendre une feuille et un crayon, et de simuler ton bazar en cherchant vite fait le plan toi meme, tu te rendra compte très vite de l'interet de la cohérence temporelle. Tu verra également que ce n'est pas tout le temps vrai, que pour certains cas (sur les coins de ton volume) le plan n'est pas le bon, mais suffit quand meme pour donner un look réaliste.
neodelphi
cppdupdup34
Messages postés
212
Date d'inscription
dimanche 29 juin 2003
Statut
Membre
Dernière intervention
13 mai 2006
19 août 2005 à 14:10
19 août 2005 à 14:10
voila une tite image
cppDupDup34
cppDupDup34
luhtor
Messages postés
2023
Date d'inscription
mardi 24 septembre 2002
Statut
Membre
Dernière intervention
28 juillet 2008
6
19 août 2005 à 15:25
19 août 2005 à 15:25
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
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
luhtor
Messages postés
2023
Date d'inscription
mardi 24 septembre 2002
Statut
Membre
Dernière intervention
28 juillet 2008
6
19 août 2005 à 15:51
19 août 2005 à 15:51
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...
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...
Vous n’avez pas trouvé la réponse que vous recherchez ?
Posez votre question
neodelphi
Messages postés
442
Date d'inscription
jeudi 4 avril 2002
Statut
Membre
Dernière intervention
11 août 2008
19 août 2005 à 16:04
19 août 2005 à 16:04
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
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
cppdupdup34
Messages postés
212
Date d'inscription
dimanche 29 juin 2003
Statut
Membre
Dernière intervention
13 mai 2006
19 août 2005 à 16:20
19 août 2005 à 16:20
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
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
luhtor
Messages postés
2023
Date d'inscription
mardi 24 septembre 2002
Statut
Membre
Dernière intervention
28 juillet 2008
6
19 août 2005 à 17:46
19 août 2005 à 17:46
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.
d'intersection est lourd également, donc je vois pas l'utilité de
chercher ton plan de séparation.
neodelphi
Messages postés
442
Date d'inscription
jeudi 4 avril 2002
Statut
Membre
Dernière intervention
11 août 2008
19 août 2005 à 23:42
19 août 2005 à 23:42
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
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
luhtor
Messages postés
2023
Date d'inscription
mardi 24 septembre 2002
Statut
Membre
Dernière intervention
28 juillet 2008
6
20 août 2005 à 12:15
20 août 2005 à 12:15
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.
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.
neodelphi
Messages postés
442
Date d'inscription
jeudi 4 avril 2002
Statut
Membre
Dernière intervention
11 août 2008
20 août 2005 à 16:03
20 août 2005 à 16:03
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
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
cppdupdup34
Messages postés
212
Date d'inscription
dimanche 29 juin 2003
Statut
Membre
Dernière intervention
13 mai 2006
21 août 2005 à 01:18
21 août 2005 à 01:18
merci !
alors ben ... y a plus qu'a !!
cppDupDup34
alors ben ... y a plus qu'a !!
cppDupDup34
cppdupdup34
Messages postés
212
Date d'inscription
dimanche 29 juin 2003
Statut
Membre
Dernière intervention
13 mai 2006
21 août 2005 à 23:13
21 août 2005 à 23:13
en fait je suis plus tout a fait sur de comprendre,
neodelphi, tu ecris:
"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."
donc on est daccord sur un point, avec cette methode, si il y a collision, je n'ai pas de plan !!
dans un autre message tu as ecris
"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."
... quel plan etant donné que dans le cas d'une collision, je n'ai pas trouvé de plan?
c'est sans doute moi mais je pige rien du tout
cppDupDup34
neodelphi, tu ecris:
"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."
donc on est daccord sur un point, avec cette methode, si il y a collision, je n'ai pas de plan !!
dans un autre message tu as ecris
"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."
... quel plan etant donné que dans le cas d'une collision, je n'ai pas trouvé de plan?
c'est sans doute moi mais je pige rien du tout
cppDupDup34
cppdupdup34
Messages postés
212
Date d'inscription
dimanche 29 juin 2003
Statut
Membre
Dernière intervention
13 mai 2006
23 août 2005 à 12:46
23 août 2005 à 12:46
c'est cool la reponse me convient!
merci bien
a+
cppDupDup34
merci bien
a+
cppDupDup34
