Lors de l'utilisation d'un octree pour la détection de collision dans un jeu, l'arbre doit-il être reconstruit à chaque image ou existe-t-il un meilleur moyen de supposer que la moitié des objets se déplacent dans un cadre?Faut-il reconstruire un octree à chaque image?
Si la scène change à chaque image, vous devez refaire l'arborescence.
Si vous avez beaucoup de géométrie statique dans vos scènes, envisagez de créer des octrees séparés. Vous pourriez également exprimer la même idée en ayant des nœuds feuilles plus complexes qui font la différence entre la géométrie statique et non statique.
Ligne de fond: ne régénérez que ce dont vous avez besoin.
Si vous avez des données très dynamiques qui déplacent toutes les images et qui doivent encore accélérer la détection des collisions, je recommande d'utiliser une grille 3D fixe. 2 dimensions équivalentes:
Il peut aussi doubler dans une liste libre pour permettre le transfert à temps constant, comme ceci (en utilisant l'indice next soit comme un index pour l'élément suivant dans la même cellule de la grille ou le prochain élément libre pour faire sauter de la pile libre si elle a été supprimée):
Un autre exemple:
Maintenant en 3 dimensions, cela peut sembler nécessiter une mémoire explosive. Cependant, l'astuce consiste à faire en sorte que chaque cellule stocke un index 32 bits dans un tableau et serve essentiellement de liste d'index à liaison unique. Cela réduit la taille de chaque cellule à 32 bits. Maintenant, si vous stockez une grille 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 des index 32 bits (pas d'allocation de mémoire/désallocation pour transférer des éléments d'un ensemble de cellules à d'autres). C'est tout le temps constant et ne nécessite pas de rééquilibrer les arbres ou de diviser les octants qui deviennent trop de monde ou quelque chose comme ça.
Vous pouvez également utiliser une hiérarchie de grilles (cela peut ressembler à un octree mais différent). Ce que je veux dire par là, c'est que vous pourriez avoir une grille grossière pour des objets maillés entiers dans votre scène. Ensuite, chaque objet maillé peut stocker une grille grossière, disons 10x10x10, pour chacune de ses parties. Puis chaque partie stocke une fine grille ou octree pour chacun de ses polygones. Cela permet des maillages non-organiques qui sont, par exemple, rigides avec des pièces qui tournent comme un robot pour éviter de mettre à jour la fine grille/octree de polygones et de mettre à jour sa propre grille grossière et la grille grossière des objets il commence à faire 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 ex. L'octree que je garderais pour vos éléments/parties complètement statiques qui n'ont jamais besoin d'être mis à jour par image et j'utiliserais un joli octree, éparpillé avec peut-être un post-traitement pour un accès mémoire cache-amical. Vous disposez d'un peu plus de temps pour accélérer les recherches dans ceux-ci 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.
Si la scène change à chaque image, vous devez mettre à jour l'arborescence. Il n'est pas toujours nécessaire de "refaire" l'arbre entier. Ma propre implémentation peut être mise à jour si nécessaire lorsque des objets se déplacent.La météo que vous pouvez faire ou non dépend de la façon dont vous l'appliquez. – phkahler
redo == mise à jour; Je les considère comme synonymes. Mais votre point de vue est correct - c'est presque comme si vous aviez besoin d'un drapeau sale pour marquer les pièces qui ont changé. – duffymo