Meilleur algorithme efficace pour la détection de collision entre les objets

Je suis confus. Bien de ne pas confondre, donc, bien que ne souhaitant pas faire les 6 programmes de test pour voir quel algorithme est le meilleur. J'ai donc pensé que je pourrais demander à mon expert amis ici AFIN de me donner l'avantage de leur expérience.

Le scénario est une scène 3d avec potentiellement une grande surface par rapport à la taille des objets à l'intérieur. Il y a potentiellement des milliers d'objets dans la scène. Les objets varient en taille de dixièmes d'une unité jusqu'à 10 unités, mais pas plus grand (ou plus petit). Les objets ont tendance à être regroupés, mais ces clusters peuvent potentiellement apparaître n'importe où dans la scène. Tous les objets sont dynamique et en mouvement. Les Clusters ont tendance à se déplacer ensemble, mais quand ils font leurs vitesses ne peut pas être le même tout le temps. Il y a aussi la géométrie statique à prendre en compte. Bien qu'il existe un grand nombre d'objets dynamiques, il y a aussi quelques objets statiques dans la scène (les objets statiques, ont tendance à être d'un ou deux ordres de grandeur plus grand que les objets dynamiques).

Maintenant, ce que je veux, c'est une des données spatiales de la structure pour l'exercice efficace de détection de collision pour tous les éléments de la scène. Ce serait formidable si l'algorithme est également pris en charge la visibilité de requête trop, pour le pipeline de rendu. Par souci de simplicité, supposons que la détection de collision est ici large de phase (c'est à dire tous les objets dynamiques sont tout simplement parfait sphères).

Donc, dans ma recherche, je peux utiliser l'un des:

(1) de l'Octree
(2) En Vrac De L'Octree
(3) Linéaire de l'Octree (+ loose)
(4) KD Tree
(5) BSP Tree
(6) le Hachage

Jusqu'à présent (6) est le seul que j'ai essayé. C'est en fait tout à fait superbe en termes de vitesse (8192 éléments de collision vérifié en moins de 1ms sur mon système) si les objets de la scène sont, en moyenne, répartis de façon égale. C'est pas un bon algorithme si tous les objets d'obtenir couped dans une zone plus petite, qui, je suppose, est possible.

Quelqu'un aperçu de laquelle utiliser, ou tout trucs que je peux employer pour accélérer les choses? Je pense que quoi qu'il arrive je peux juste utiliser un arbre BSP pour la géométrie statique. Je suppose que la dynamique de "sphères" est ce qui me préoccupe le plus ici. Note: pas de CUDA, c'est CPU :p.

Grâce

EDIT: Ok, merci pour Floris, j'ai trouvé plus d'informations sur l'AABB Arbres. Il y a une vieille discussion sur GameDev ici: http://www.gamedev.net/topic/308665-aabb-tree---wheres-the-poly-o_o/. Ressemble à un bon compromis.

Final EDIT: a Décidé de ne pas réinventer la roue. Il est possible que la puce de la physique de la bibliothèque va faire tout cela pour moi (il a AABB arbre, probablement, très bien optimisé trop).

  • Vous pouvez probablement passer KD-tree pour les scènes dynamiques. KD tree de travail sur la statique des ensembles de données, vous devez reconstruire l'ensemble de la (sous -) arbre chaque fois qu'un seul élément déplacé
  • Oui, il a regardé comme il était trop intensive à l'utilisation dans des scènes dynamiques.
InformationsquelleAutor Robinson | 2011-08-18
  1. 19

    Grande question.

    En gros, vous avez un complexe de compromis entre:

    1. Vitesse d'un système complet de détection de collision de la phase
    2. Surcharge de mise à jour et le maintien de la structure de données que les objets se déplacent autour de

    La mauvaise nouvelle est qu'il n'y a pas de réponse "parfaite" pour cette raison, cela va vraiment dépendre de beaucoup de différents facteurs propres à votre situation. Bsp, par exemple, sont blisteringly rapide pour 1. quand ils sont pré-calculés avec beaucoup de statique de la géométrie plane, ce qui explique pourquoi ils ont été si répandue dans le début des jeux FPS.

    Mon estimation personnelle est qu'un lâche AABB (Axe Aligné Boîte Englobante) de l'arbre avec un nombre raisonnable d'objets (de 5 à 10?) dans chaque niveau du bas de la boîte englobante sera probablement mieux dans votre cas. Raisons:

    • Vous avez tout à fait un grand /éparses de l'espace avec des groupes d'objets. AABB les arbres ont tendance à être bon pour cela, comme vous pouvez le couper beaucoup de niveaux qui vous serait autrement nécessaire.
    • Vous êtes en supposant des sphères parfaites. Sphère au sphère tests de collision sont très bon marché, de sorte que vous pouvez facilement se permettre de faire 10-45 tests pour chaque niveau du bas-nœud. Fondamentalement, N^2 est très bien pour de petites valeurs de N 🙂
    • Alignement de l'axe du fait de la mise à jour de l'arbre est beaucoup plus simple et l'intersection des tests beaucoup moins cher que la plupart des alternatives. Puisque vous êtes en supposant que grossièrement sphérique objets, je ne pense pas que vous allez gagner beaucoup de orientée vers les boîtes englobantes (qui ne vraiment vous donner un avantage si vous avez beaucoup de long/mince formes drôle d'angles).
    • En permettant à l'boîtes englobantes à être lâche et contiennent un nombre raisonnable d'objets, vous réduisez le risque que le mouvement de tout objet individuel va le prendre à l'extérieur de l'AABB limites. Sauf si cela se produit, vous n'avez pas besoin de mettre à jour l'arborescence. Cela permettra d'économiser que vous beaucoup de l'arbre de temps de mise à jour. Quand ça arrive, d'étendre la limite avec un peu de marge de sorte que vous n'avez pas immédiatement ré-étendre à nouveau la prochaine frame - rappelez-vous que la plupart des mouvement tend à continuer dans la même direction pour quelques images!

    Désolé pour le légèrement laineux réponse, mais j'espère que cela vous donne quelques idées utiles /les choses de considérer!

    InformationsquelleAutor mikera
  2. 5

    De nombreux moteurs de physique utiliser un AABBTree (Axe aligné Boîte Englobante de l'Arbre), Il divise un objet de plus en plus petits morceaux. Vous pouvez obtenir une très bonne détection de collision par l'utilisation de cet algo. Cet arbre ressemble un peu à un Octree.

    Un OOBBTree (Orienté Boîte Englobante) serait que c'est mieux de contre-partie.

    • Assurez-vous. C'est un cadre de volume de la hiérarchie, et probablement beaucoup mieux pour fine intersection de test. Je recherchais des idées pour une large phase (c'est à dire personne déplacement des sphères/particules) de détection. - Mon erreur... je vais regarder dans ce peu plus. Le premier exemple que j'ai trouvé sur le web de cette apparaissait comme s'il était en train de faire à grain fin de collision, mais il y a plus, je vais regarder dans un mo.
    InformationsquelleAutor Floris