Bonjour,

J’essaye actuellement de développer un moteur physique 3d simple : 90 % de sa tache constitue à chercher de collision entre des points mobiles indépendants avec un modèle 3d complexe défini par un *.obj.
La méthode que j’utilise en ce moment est plutôt imprécise car j'ai du mal à déterminer quelle est la face la plus proche d'un point de l'espace.

Le modèle 3d compte environ 10 000 points.

J'ai essayé avec du V-cliping mais mon modèle est non-convexe, ça ne marche donc pas.

Avez vous une idée de librairie(java si possible ou c++) ou d’algorithme qui pourrait détecter la collision entre un objet non-convexe et un point ou une manière non-approximative de décomposer cette objet en un ensemble d'objet convexe. Je n'ai pas forcément besoin de quelque chose de très performant mais cela doit rester précis

P-1, il y a plein de techniques. Une classique consiste a faire des bounding box a tes objets pour arrive a decider rapidement si deux objets peuvent etre en collisions. Si leur bounding box ne s'intersectent pas alors clairement il n'y a pas de collision.

Une autre methode consiste a utiliser un decoupage de l'espace en cube. Tu place chaque point (ou face) de tes objet dans le cube ou ils sont. Ca te permet de detecter rapidement quelles faces sont dans le meme cube et ainsi, tu n'a besoin de verifier que ces collisions la.

Si tu rends ta decomposition de l'espace recursive, c'est ce que l'on appelle oct-tree decomposition.

Peux tu nous en dire plus sur ton probleme?

pas de bounding box ou de cube ici, en fait le système pourrait
être comparé à celui d'une heigh map dans un str sauf qu'ici là map est un mesh fermé et que les unités peuvent faire le tour. Un peu comme on se déplace sur une planète.

Tu peux essayer de prévoir chaque collision possible ..

... Je suis pas sure que ce soit sérieux comme réponse mais à tout hasard, je t'explique pourquoi ça ne me parait pas réalisable.

Étant donné que sur une face, on peut faire environ 360*90 collision différente en ne prenant en compte que l'angle et pas la position et avec une précision d 1° ( et c'est assez grossier) que mon modèle doit compter environ 5000 faces, ce qui est une estimation assez basse, on obtient au minimum 360*90*5000= 162000000 collisions différentes sans traiter vraiment la position du point d’impact et avec un précision plutôt grossière. En plus, une fois qu'elle sont calculer, il reste à soire laquelle utiliser au bon moment, est donc je n'ai pas avancé du tout.

Mais merci pour ton intérêt à mon problème.

"Mais ton problème c'est que les objet rentrent parfois dans le mesh complexe? Tu peut utiliser les normales des triangles pour déterminer si l'objet est rentré a l'interieur du mesh, eventuellement."

Se baser sur les normales des facettes ça ne marche que pour les objets convexes.

Une solution que je propose pour savoir si un point appartient bien à un maillage non convexe, c'est de remplir les "renfoncements" du maillage non convexe avec des objets virtuels convexes. Une fois les renfoncements comblés, on obtient un nouvel objet, convexe, qui est composé du maillage non-convexe initial et de tous les objets qui ont permis de combler les renfoncements. Le problème est alors plus simple : on teste si ce nouvel objet contient le point, si oui alors on teste qu'il n'appartienne pas à un des sous-objets convexes qui ont permis de remplir les renfoncements.

Illustration :

1ère image : un polygone non convexe
2ème image : on crée un second polygone convexe (en rouge) pour former un tout qui est convexe
3ème image : le point vert appartient à ce tout et n'appartient pas au polygone rouge, donc il appartient au polygone noir
4ème image : le point vert appartient bien au tout, mais appartient également au polygone en rouge, donc il n'appartient pas au polygone noir.

quid d'une decomposition d'objet non convexe en ensemble d'objet convexe?

Je plussoie godrik, je vois 2 solutions pour trier les faces selon un point en mouvement :

- mettre le mesh dans un octree, c'est pas trop dur comme algo mais ça peut ensuite ne pas être très performant si le point parcourt une grande distance.

- découper le mesh en formes convexes, ce qui permettrait par ex de les placer dans un arbre BSP (c'est super performant mais plus difficile comme algo), et là on n'a même plus à tester les collisions sur les triangles mais seulement sur leur plan.

Merci pour vos réponses, la décomposition me parasitait aussi assez intéressante car je dispose déjà d'une librairie pour traiter ce genre d'objets.
Je n'ai par contre pas encore de moyen pour décomposer mon mesh se ce n'est de prendre mon couteau blender et de tout faire "à la main".
Je sais qu'il existe quelque systèmes qui peuvent produire cette décomposition comme la librairie HACD mais je n'ai pas encor réussi à savoir à quel niveau d’approximation il faut s'attendre de sa part( le "A" signifie aproximate) ni même aucune documentation consistante.
Hors j'ai besoin que le modèle physique soit assez proche du modèle visuel pour que le joueur puisse un minimum anticiper le résultat des collisions.

Si quelqu'un à de la doc sur cette librairie ou une autre, je lui serait très reconnaissant de m'en faire part.

Hello,

tu peux essayer OZCollide :
www.tsarevitch/ozcollide

basée sur une approche en AABB tree.
La librairie est en licence LGPL et documentée.

Bien que le sujet soit un peu vieux, merci pour l'info Igor

Il semble y avoir un problème sur le lien.

My bad. Je devais être fatigué
www.tsarevitch.org/ozcollide/

J'avais juste oublié le ".org"

"Ray Tracing" en te basant sur ton vecteur vitesse, ça te retourne le point de collision ainsi que l'objet testé.

C'est le plus bas niveau de collision que tu peux avoir.

Collision pas physique hein.
Bon visiblement tu ne maîtrises absolument rien au sujet (sweep'n'prune, cohérence temporelle, optimisation mémoire des arbres, radix, serializer, ...). Bref inutile de perdre son temps.

Restons courtois merci