Discussion :

[acx01b]

Bonjour,
j'ai feuilleté un peu des manuels et sources de moteurs physiques et je n'ai pas l'impression que contrairement à ce qu'ils affichent, les calculs de collisions soient vraiment continus

je me pose donc la question: existe-il une librairie (pas forcément super rapide) qui fasse des vrais calculs de collisions ?

pour Havok et Ageia Physx je n'ai pas réussi à me renseigner,ils parlent de collisions continues mais je les soupçonne très fortement d'utiliser des vitesses linéaire et de rotation constantes pour leur détection de collision : où sont passées les forces dans le calcul ?

bullets

Bullet TODO list
Improving documentation
Cleanup demos
Integrate Jan Bender's one-shot contact manifold generation
Character Control + demo (just like the raycasting this is based on the Continuous Collision Detection)
COLLADA Physics debug snapshot support
Maya Physics plugin (based on an older Nima version)
Continuous collision detection in the physics loop
Finish Multi SAP broadphase
Add Featherstone constraint solver
etc.
--> Continuous collision detection in the physics loop ça me parait pas très clair, ils utilisent les CCD ou pas ???

--> par ailleurs j'ai cherché dans les sources, où est la fonction ContinuousCollisionSphereSphere ?

Newton: pareil pas de vraie fonction de collision continue

NewtonMaterialSetContinuousCollisionMode

Remarks
continue collision mode does not prevent rigid bodies from interpenetration instead it prevent bodies from passing trough each others by extrapolating contact points when the bodies normal contact calculation determine the bodies are not colliding.

interpenetration, extrapolation => ça n'a pas l'air vraiment continu tout ça

for performance reason the bodies angular velocities is only use on the broad face of the collision, but not on the contact calculation.

--> ok donc il ne respecte pas les lois de la physique

Tokamak
Collision Detection Build within Tokamak is a very efficient collision
detection module. Currently, Tokamak provides collision detection
for primitives (box, sphere, capsule), combination of primitives, and
arbitrary static triangle mesh.
--> ok ils ne prétendent même pas utiliser de détection continue

ODE
dans http://www.ode.org/ode-latest-userguide.html
--> je ne trouve pas trace du mot continuous

donc si j'ai bien compris il n'y a pas de respect de la physique dans tous ces moteurs, détection discrète ou interpolée, non prise en compte de la rotation dans l'interpolation ...

si vous cherchez comme moi plus de renseignements je pense qu'il y a à partir de ce lien pas mal d'informations à trouver:
http://bulletphysics.com/Bullet/phpB...c.php?f=4&t=20

Renaud

[Kujara]

Completement normal.

Les detection de collision en continu, c'est assez inexploitable pour un moteur physique de qualité industrielle. Les approximations actuelles ( timestep & co), sont suffisemment precises pour du jeu video, tout en etant immensemment plus rapide.

Tu peux chercher du coté des moteurs physiques pour simulation, ou moteurs physiques non temps réel, eux disposent d'algos d'une precision plus elevée, au prix d'un temps de calcul largement pire.

Tu peux aussi chercher du coté d'un truc etrange : les collisions en 4 dimensions. C'est une technique assez ardue a mettre en place donc c'est sous utilisée mais c'est probablement la plus precise de toutes.

[acx01b]

salut je cherche mais je ne trouve pas ... !

[deadalnix]

Tu peux aussi chercher du coté d'un truc etrange : les collisions en 4 dimensions. C'est une technique assez ardue a mettre en place donc c'est sous utilisée mais c'est probablement la plus precise de toutes.

Deterrage : qu'est ce que c'est que ca oO

[Rafy]

(J'amène une peltée moi aussi)
Jamais entendu parlé des collisions en 4 dimensions.... ardue comment ? précise comment ?

[LeGreg]

Ben c'est simple :
Imaginons deux objets représentés par leur bounding box:
Une intersection peut se faire en 2d (X et Y) ou 3D (X,Y,Z). On dit qu'il y a "collision" lorsque les deux bounding boxes s'interpénètrent à une date t0.

Seul problème c'est une intersection instantanée. C'est à dire que si on travaille non pas sur une date instantanée (parfois ça sert ceci dit) mais sur un intervalle de temps comme souvent dans le jeu vidéo, il faut soit:

- faire les calculs d'intersection de manière répétée, donc à t0, t0+dt, etc. Si l'on veut que la simulation soit précise il faut que dt soit le plus petit possible. En gros si dt est trop gros et que les deux objets s'intersectent au moment t0+dt/2 mais ni à t0 ni à t0+dt, alors on rate le fait qu'il y ait eu une intersection. Par exemple, la balle traverse le mur parce que on a calculé l'intersection juste avant qu'elle touche le mur et sa trajectoire calculée l'a amenée juste derrière le mur à l'instant t0+dt d'après.

Si on ne peut plus trop jouer sur dt, on travaille à limiter la vélocité instantanée (distance que peut parcourir un objet) et on joue sur la taille de la bounding box. Un algo conservatif serait : une bounding box suffisamment grosse pour que à vitesse donnée et timestep donné on n'ait que des faux positifs sur l'intersection et aucun faux négatifs.

"Faux positif" veut dire qu'on a détecté une intersection sur la bounding box alors que l'objet contenu n'intersecte pas. Parfois dans les jeux vidéo le faux positif peut passer pour une approximation suffisante qui est meilleure que l'alternative (personnage qui passe à travers les murs/sols). Et qui permet d'épargner des coûts de calculs. Pour éviter les faux positifs on peut toujours affiner les calculs et donc considérer la manière "rapide" comme un pré-filtrage des collisions pour apppliquer ensuite une simulation plus précise.

- Plutot que de choisir une taille de bounding box conservative on peut choisir de travailler non pas sur une bounding box statique, mais sur un sweeping volume (volume de balayage). Celui-ci est toujours en 2D (X,Y) ou 3D (X,Y,Z), mais le volume choisi est allongée en tenant compte de la trajectoire de l'objet entre [t0, t0+dt[. Un exemple tout simple est le choix d'une sphère englobante pour les objets, sphère qui est une bounding box statique. La forme du sweeping volume correspondant est donc la "capsule" ou un cylindre avec les extrémités arrondies. De même si la boite englobante statique était un parallélépipède, alors la forme du sweeping volume correspondant sera un polyèdre allongé selon v.dt (vitesse * intervalle de temps).

L'idée du sweeping volume est que l'objet va être entièrement contenu dans ce volume dans l'intervalle de temps considéré. Donc pour déterminer si deux objets s'intersectent dans cet intervalle on peut faire un calcul d'intersection (statique) sur les deux sweeping volumes.

On voit donc que le sweeping volume est une proposition qui peut-être beaucoup plus intéressante en terme de calculs si l'on arrive à facilement faire le calcul d'intersection des sweeping volume correspondants parce qu'il n'y aura pas de limitation sur la vélocité ou sur l'intervalle de temps considéré. Il n'y aura que des faux positifs et aucun faux négatifs.

Seul problème, on ne sait pas quel était le point de contact des deux objets (ou même de la boite englobante statique), ni à quelle date "précise" l'intersection a eu lieu. Et cela peut rajouter des faux positifs si la distance couverte est importante (deux objets peuvent occuper le même volume mais l'un après l'autre sans jamais s'intersecter en réalité). Cela ne doit donc pas forcément remplacer le calcul d'intersection plus précis si la précision de la simulation est nécessaire.

- Imaginons cette fois-ci que l'on ne travaille plus uniquement sur la position dans l'espace mais on considère l'évolution des objets dans les trois dimensions (X,Y,T) ou quatre dimensions (X,Y,Z,T).

Il existe aussi un sweeping volume dans ces quatre dimensions. C'est le volume qui contient l'objet à chaque instant t+dt. On peut donc faire un calcul d'intersection sur ces sweeping volume dans l'espace-temps pour déterminer si il y a une intersection ou pas.

Et l'ajout de la dimension supplémentaire est importante, parce qu'elle supprime l'ambiguïté du sweeping volume en trois dimensions dont on a parlé précédemment sur la date de l'intersection. En prenant le point de contact avec la coordonnée T minimale, on connait donc la date précise du premier contact. Ensuite en faisant une projection/coupe à cette date du volume englobant, on peut donc facilement trouver le ou les points de contact sur le volume.

Bien entendu la date et le point de contact n'est précise que si la boite englobante et son interpolation selon T est précise. Si l'on choisit des approximations grossières pour ces deux entités (on réduit tout à des cylindres, capsules ou des boites parallélépipédiques), alors le résultat n'a pas forcément plus de valeur que le volume de balayage dans l'espace en terme de faux positifs et de date de premier contact. C'est pour ça que c'est plus utilisé dans la "simulation dure".

LeGreg