Quel est l'état de l'art du partitionnement spatial pour les jeux? [fermé]

Je connais les arbres BSP, Octrees et Portal qui étaient utilisés depuis longtemps. Mais les jeux modernes utilisent toujours ces systèmes ou utilisent-ils de nouvelles choses?

Si c'est possible avec des avantages et des inconvénients, envisagez le rendu et la détection des collisions.

Oui, le moteur Unreal 3, par exemple, utilise toujours un BSP - principalement parce qu'il est utilisé pendant le processus CSG. Doom3 / id tech 4 utilise des portails, et je pense avoir lu quelque chose que id Tech 5 est de retour dans les arbres BSP. Il y a aussi des jeux qui utilisent des octrees. Dans le jeu, ma compréhension est que UE3 est passé à une approche plus dynamique avec des requêtes d'occlusion, mais je serais surpris s'ils n'utilisent pas le BSP pour au moins déterminer les maillages statiques en vue. D'autres jeux peuvent simplement utiliser le tri sélectif de la vue (Civilization par exemple.) Cela dépend vraiment du type de jeu que vous regardez.

La raison pour laquelle les BSP et les trucs sont toujours là est parce que vous ne pouvez pas faire beaucoup mieux. Si vous avez une géométrie statique, un BSP est idéal si vous le construisez correctement. Cependant, cela nécessite que vous écriviez un générateur BSP, ce qui est délicat (mais cela peut arriver gratuitement si votre solution CSG en utilise un!). coût mais ne nécessitent pas de prétraitement (coûteux) des niveaux. C'est un compromis que certains jeux sont prêts à faire (Crytek, par exemple, veut que tout s'exécute en temps réel, donc ils ne passent pas de temps de traitement pour créer une structure d'accélération statique.) D'autres approches d'exécution sont par exemple la rastérisation logicielle sur le CPU et effectuer des requêtes d'occlusion sur le CPU (ceci est utilisé par le moteur Frostbite.)

Pour une approche vraiment moderne, regardez Umbra , qui est un middleware pour les requêtes de visibilité. Si vous recherchez un peu sur le Web, vous devriez trouver une partie de la thèse de maîtrise qui décrit les débuts d'Umbra.

Bottom line: Que vous souhaitiez utiliser un BSP / Octree / no AS dépendra fortement du type de jeu que vous souhaitez créer. Si vos niveaux sont principalement statiques, vous devriez en profiter et créer une structure d'accélération statique. Si tout est dynamique, il faut bien sûr une autre approche.

Pour la détection de collision, je voudrais jeter un œil à Bullet et PhysX et à leurs algorithmes de détection de collision. Mais mon sentiment est que les solutions physiques sont moins liées à la visibilité qu'auparavant - une solution physique pourrait vouloir utiliser un BVH basé sur un GPU, dans ce cas, il n'y a pas beaucoup de sens à essayer de l'utiliser pour des requêtes de visibilité.

Honnêtement, je ne sais pas quels moteurs de nouvelle génération utilisent de nos jours, mais je vais vous dire ce que je sais. Il est facile de se confondre entre une optimisation et la structure de données utilisée pour aider à cette optimisation. Cependant, toutes les choses mentionnées ci-dessous sont des optimisations, mais je soulignerai lesquelles sont spécifiquement des structures de données.

BSP : Data Structure - Pour détecter l'intersection entre des objets dynamiques en mouvement et la géométrie du monde statique. Utilisé pour la détection de collision et le rendu de la géométrie correctement sans zbuffer, mais il n'est plus utilisé pour le rendu car nous avons maintenant suffisamment de mémoire pour le tampon az. Ils sont techniquement générés légèrement différemment, mais toujours considérés comme le même type d'arbre. Nécessite un prétraitement.

Octree ou Kd-Tree : structure de données - utilisé pour déterminer quels objets se trouvent dans la même "cellule" ou zone pour éviter d'effectuer une vérification n ^ 2 sur tous les objets dynamiques.

Ce ne sont pas les seuls, mais ils sont probablement les plus courants. Il existe également de nombreuses optimisations qui permettent au moteur d'éviter le rendu de la géométrie en général. Mais ce qui suit élimine simplement la géométrie, et c'est généralement tout ce pour quoi il est utilisé:

Portails : Pas techniquement une structure de données, mais nécessite une spéciale pour effectuer l'abattage. Utilisé pour la suppression de la visibilité de la géométrie du monde et de la géométrie d'objet dynamique à partir de la vue. Nécessite un prétraitement pour diviser le monde en zones, je pense. Mais je ne l'ai pas réellement implémenté, donc je ne sais pas.

Élimination de l'occlusion : Optimisation - utilisée pour l'élimination de la visibilité de tout ce que vous voulez, probablement des objets dynamiques.

Élimination régulière des fenêtres : optimisation - élimine les objets qui ne sont pas visibles par la caméra.

Plus d'élimination des fenêtres : optimisation - L'élimination régulière des fenêtres peut être encore optimisée en utilisant un octree. Vous pouvez supprimer des cellules entières de l'octree qui se trouvent derrière la caméra ou non à sa vue. Cela inclut des parcelles de terrain (si vous êtes à l'extérieur). Tout ce qui n'est pas abattu par l'octree, vous effectuez un "abattage régulier des fenêtres". Ensuite, tout ce qui reste, vous le restituez.

Élimination de la face arrière : optimisation - élimination de la géométrie à l'opposé de la caméra pour éviter la pixellisation. Généralement effectué dans le matériel si l'état de rendu est correctement défini.

Structures de données de cas particuliers:

Arbres AABB ou arbres Sphère : Ce sont des types de structures de données de cas particulier. Ils transforment une forme concave en convexe. Par exemple, un personnage avec des os est techniquement concave. Il le décompose en petits morceaux convexes. Peut être utilisé comme une optimisation pour la détection de collision, l'élimination de la visibilité des objets dynamiques (généralement) et facilite les tests d'intersection, car il est convexe. Ceux-ci iraient à l'intérieur, disons, d'un octree car ce sont généralement des objets dynamiques. Ceux-ci pourraient également être utilisés pour aider à l'optimisation de l'élimination des occlusions.

Il n'y a aucune raison pour laquelle vous devez utiliser une seule structure pour tout représenter (comme un graphique de scène). À mon avis, il serait préférable d'utiliser différentes structures de données pour différentes tâches au lieu d'essayer d'utiliser une arborescence à usage général quelconque. Par exemple, le moteur sur lequel je travaille actuellement, je prévois d'implémenter une combinaison d'arbre BSP / Octree / AABB avec les optimisations suivantes: élimination d'occlusion, fenêtre d'affichage et, bien sûr, élimination de face arrière. Cela signifie que j'aurai un arbre bsp, un octree et probablement plusieurs arbres aabb dans cet octree.

La sélection des meilleures structures de données et algorithmes / optimisations est probablement la chose la plus importante et la plus avantageuse que vous puissiez faire pour votre moteur.