Lorsque vous utilisez un Octree pour la détection de collision dans une partie, l'arborescence doit-elle être reconstruite chaque cadre ou est-ce qu'il y a une meilleure façon en supposant que la moitié des objets se déplacent dans un cadre?
3 Réponses :
Si la scène change avec chaque image, vous devez refaire l'arbre.
Si la scène change avec chaque image, vous devez mettre à jour l'arbre. Il n'est pas toujours nécessaire de "refaire" l'arbre entier. Ma propre implémentation peut mettre à jour le besoin lorsque des objets se déplacent. Temps que vous pouvez faire cela ou pas dépend de la manière dont vous l'appliquez.
refaire == mise à jour; Je les considère que les synonymes. Mais votre point est correct - c'est presque comme si vous auriez besoin d'un drapeau sale pour marquer des morceaux qui ont changé.
Si vous avez beaucoup de géométrie statique dans vos scènes, envisagez de construire des octrees séparés. Vous pouvez également exprimer la même idée en ayant des nœuds de feuilles plus compliqués qui font la différence entre la géométrie statique et non statique.
Bottom Line: seulement régénérer ce que vous devez.
Si vous avez des données très dynamiques, vous déplacez chaque image et vous devez toujours accélérer la détection de collision, je vous recommande d'utiliser une grille 3D fixe pour cela. Équivalent 2 dimensions:
Il peut également doubler comme une liste libre pour permettre des déménagements de temps constants, comme (en utilisant l'index suivant comme un index à l'élément suivant dans la même cellule de la grille ou le prochain gratuit Élément pour apparaître de la pile libre si elle a été supprimée):
Un autre exemple:
maintenant en 3 dimensions, cela pourrait sembler que cela nécessiterait une mémoire explosive. Cependant, l'astuce consiste à simplement faire de chaque cellule un index 32 bits dans un tableau et servir essentiellement à servir de liste d'index personnellement liée. Cela réduit la taille de chaque cellule jusqu'à 32 bits. Maintenant, si vous stockez une grille de 100x100x100 (1 million de cellules), cela prendrait moins de 4 mégaoctets.
Lorsque des éléments se déplacent, vous pouvez simplement les retirer des cellules qu'ils occupent, les déplacer et les insérer dans les nouvelles cellules. Tout ce que vous avez à faire pour le faire est de manipuler certains indices 32 bits (aucune allocation de mémoire / distribution de la mémoire pour transférer des éléments d'un ensemble de cellules à d'autres). Tout cela est tout à temps constant et ne nécessite pas de rééquilibrage des arbres ni de fractionnement des octes qui deviennent trop encombrés ou quelque chose comme ça.
Vous pouvez également utiliser une hiérarchie de grilles (cela pourrait ressembler à un octree mais différent). Ce que je veux dire par là est que vous pourriez avoir une grille grossière pour des objets en maille entiers dans votre scène. Ensuite, chaque objet maillage pourrait stocker une grille grossière, disons, 10x10x10, pour chacune de ses parties. Ensuite, chaque partie stocke une grille fine ou un octree pour chacun de ses polygones. Cela permet aux mailles non biologiques qui sont, disent, rigides avec des pièces qui tournent simplement comme un robot pour éviter de devoir mettre à jour la grille fine / octree de polygones et simplement mettre à jour sa propre réseau grossier de pièces et la grille grossière des objets du monde lorsque il commence à tourner ses jambes et ses bras, par exemple Seuls les modèles organiques doivent mettre à jour leurs grilles fines lorsqu'elles sont déformées par des os, par exemple
L'OCTREEE Je conserverais pour vos éléments / pièces entièrement statiques qui n'ont jamais besoin d'être mis à jour par image et j'utiliserais un bel octree, clairsemé avec peut-être un post-traitement pour l'accès à la mémoire respectueuse de la cache. Vous avez un peu plus de temps disponible pour accélérer les recherches dans les personnes et minimiser leur utilisation de la mémoire si vous pouvez supposer que l'OCTREE n'a jamais besoin d'être mis à jour une fois qu'il est construit.
J'ai deux questions clarifiantes. Si une entité finit par se chevaucher à deux carreaux / carrés (due à la largeur / hauteur) et se déplace, comment mettez-vous à jour efficacement la position de sa position dans la grille? Deuxièmement, comment pouvez-vous interroger efficacement pour toutes les entités uniques si elles peuvent être stockées dans plusieurs endroits?
C'est assez élaboré. J'ai une réponse ridiculement longue de longue durée sur toutes les possibilités: Stackoverflow.com/questions/41946007/... . Le moyen le plus simple est que vos agents ont une petite gamme en termes de taille, comme si votre plus grand agent n'est pas beaucoup plus grand que votre plus petit agent, vous pouvez utiliser le rayon limité supérieur ou quelque chose à cet effet chaque fois que vous recherchez en collision. agents à un point particulier. Vous développez le rayon de recherche par la taille / rayon de la limite supérieure du plus grand agent ...
... c'est une sorte de solution gobineuse, mais cela peut être très efficace quand il est approprié et c'est naturellement très simple. Lorsque vous faites cela, même si votre agent chevauche plusieurs cellules de la grille, il vous suffit de le traiter comme un point et de le stocker dans une cellule d'une cellule son point central occupe. Une alternative est une structure lâche et dans cette réponse verbose ci-dessus, je donne un exemple de la manière de faire une grille en vrac ainsi qu'un quadtre lâche (qui s'étend facilement à Octree en 3 dimensions). Finally, il suffit de stocker l'agent dans toutes les cellules qui se chevauchent. Si vous faites cela, alors la richesse [...]
[...] est que vous souhaitez utiliser des cellules assez grandes pour que vous n'ayez pas comme un agent géant occupant de 2000 cellules de grille qui serreraient. Un autre est que vous souhaitez stocker un magasin de pointeur de voleur de chose à l'agent - rendez-le aussi léger que possible. Enfin, si vous souhaitez trouver efficacement les entités uniques quand il y a du chevauchement et de la redondance, une solution est de stocker comme un booléen (pourrait être un seul bit) à l'agent. Lorsque vous faites vos questions, n'ajoutez que l'agent à la liste si ce booléen est défini sur False. Si c'est le cas, réglez-le à vrai. Une fois terminé, boucle à travers l'ensemble résultant et set [...]
[...] Ces booléens remontent à FALSE. C'est un type d'astuce bon marché et sale pour trouver des ensembles uniques en temps linéaire (avec des itérations de Dirt-bon marché) sans une recherche de hasch plus coûteuse ou un algorithme linéarithmique impliquant une structure de données d'arborescence pour représenter l'ensemble unique.
Merci beaucoup! Toutes ces réponses aident. J'ai pensé à l'idée booléenne mais j'ai pensé qu'il doit y avoir une meilleure façon. Je crains également que si une autre requête ait commencé avant celle-ci (un appel asynchrone à JavaScript provoquant une deuxième requête), le système booléen ne fonctionnerait pas. À votre santé!
Si les requêtes se produisent de manière asynchrone en parallèle, alors oui, la solution intrusive stockant des booléens / bits directement dans les entités va être problématique (état de race ou goulot d'étranglement). Dans ce cas, j'irais simplement comme un conteneur de jeu rapide comme une bonne et bon marché de table de hachage rapide à construire. Une autre option est si vos données sont accessibles par index et les indices sont assez denses (pas peu répandus) sur une plage non goupée, vous pouvez utiliser un bitset parallèle à la matrice d'entités et éviter de stocker des données intrusivement dans l'entité qui manière.
Dans ce cas, une fois que vous parcourez la 52e entité, vous définissez / marquez le 52ème bit dans ce bitset parallèle et l'annexez à une séquence si le 52ème bit n'était pas déjà défini. Et ce bitset parallèle devient un objet local temporaire que vous pouvez stocker par fil de threer une requête, puis jeter lorsque la requête est terminée pour éviter les données partagées.
Encore une autre option (il existe de nombreuses façons de s'attaquer à cela) consiste à rassembler les doublons dans les requêtes, puis à trier et à supprimer des doublons. Cela pourrait sembler algorithmique brut, mais généralement vos requêtes de collision vont, à condition que la structure de données soit raisonnable, donnez un nombre assez petit de résultats (même avec des doublons jetés dans). Donc, le temps de trier et de filtrer les doublons pourrait être assez trivial ici en fonction du contexte (peut faire avec une passe linéaire avec le tri radix), et ce n'est peut-être pas un tel compromis si vous voulez pouvoir faire plusieurs requêtes dans parallèle.
Mais je suis un peu chaud et remue-méninges un peu en même temps. Je n'ai pas l'habitude de paralleralliser les requêtes de collision. Dans la plupart des contextes, j'ai consacré un seul fil à la détection de collision et à d'autres threads à d'autres tâches. Si vous souhaitez consacrer plus de threads à une détection de collision seulement, je serais probablement plus fortement influencé à utiliser une structure de données en vrac qui n'implique même pas les entrées en double dans la structure de données, quoi que ce soit.