Quelle est une bonne solution de structure de données pour un gestionnaire de scène dans XNA?

Je joue avec XNA pour un projet de jeu de moi-même, j'avais déjà été exposé à OpenGL et travaillé un peu avec Ogre, donc j'essaie de faire fonctionner les mêmes concepts sur XNA.

Plus précisément, j'essaie d'ajouter à XNA un gestionnaire de scènes pour gérer les transformations hiérarchiques, le tri sélectif (peut-être même l'occlusion) et le tri des objets de transparence.

Mon plan était de construire un gestionnaire de scène d'arbre pour gérer les transformations hiérarchiques et l'éclairage, puis utiliser un Octree pour l'élimination des troncs et le tri des objets. Le problème est de savoir comment effectuer un tri géométrique pour prendre correctement en charge les transparents. Je sais que le tri est très coûteux s'il est effectué par polygone, si cher qu'il n'est même pas géré par Ogre. Mais les images fixes d'Ogre semblent bonnes.

Avez-vous des idées sur la façon de le faire et les structures de données à utiliser et leurs capacités? Je sais que les gens utilisent:

• Octrees
• Kd-trees (quelqu'un sur le forum GameDev a dit que ceux-ci sont bien meilleurs que Octrees)
• BSP (qui devrait gérer la commande par polygone mais qui est très cher)
• BVH (mais uniquement pour l'abattage du tronc et de l'occlusion)

Je vous remercie

Tunnuz

Octtrees (ou même simplement quadtrees) et Kd-trees sont tous deux de bons schémas de partitionnement spatial à usage général, et si votre pipeline de construction et / ou votre moteur les génère, vous les trouverez utiles de toutes sortes de manières différentes pour optimiser les requêtes / itérations. Ils fonctionnent en subdivisant un volume fixe de manière hiérarchique, ce qui rend les requêtes telles que la diffusion de rayons dans votre espace objet très peu coûteuses à interroger (idéal pour les contrôles de collision).

Les hiérarchies de volumes limites fonctionnent d'une manière légèrement différente (elles agrègent les volumes des objets dans l'arborescence plutôt que de sous-diviser les espaces), et sont un moyen simple de supprimer les éléments inutiles de l'itération. Mais parce que BVH n'impose aucune restriction sur la façon dont deux nœuds frères sont liés, ce n'est pas un bon schéma pour déterminer l'ordre de rendu ou pour les requêtes de collision arbitraires.

Les systèmes BSP sont bons lorsque vous subdivisez le monde en fonction de polygones individuels, mais pour les objets plus grands, une approche basée sur le volume est plus logique.

Mais surtout, il convient de noter qu'aucun de ces systèmes n'est parfait pour déterminer l'ordre de rendu pour la transparence, même l'approche BSP. Il sera toujours possible de construire une géométrie qui casse votre algorithme, à moins que vous ne puissiez subdiviser des polygones à la volée. Ce que vous recherchez le plus probablement, c'est une solution «au mieux», où la géométrie peut être commandée correctement dans la majorité des cas; et l'équipe artistique peut subdiviser les modèles pour tous les cas qui ne fonctionnent pas (car le modèle / les polygones sont anormalement grands, longs ou auto-entrecroisés). Les petits modèles / nœuds sont toujours beaucoup plus faciles à trier «correctement», mais vous les payez en termes de frais d'itération.

Les arbres Kd et Oct / Quad sont tous deux de bonnes solutions à usage général, pour lesquelles une implémentation conviviale de la plate-forme peut être écrite, mais à la fin, vous allez devoir équilibrer la profondeur / complexité de votre arbre de partitionnement spatial par rapport au coût de itérer, et les frais généraux par modèle (c'est-à-dire tirer le coût des appels). Si vous ciblez XNA, je vous recommande de le garder simple et de haut niveau, et s'il y a des problèmes de tri avec une partie du contenu, alors envisagez fortement de changer le contenu avant d'essayer d'améliorer votre moteur jusqu'à ce qu'il puisse y faire face; les retours diminuent très rapidement après l'implémentation du tri de rendu le plus basique.

McCranky a couvert étonnamment toutes les structures de données que vous avez mentionnées, mais je vois que vous n'avez pas considéré les R-Trees. Le corpus de connaissances sur ces structures est énorme, et elles sont très adaptées aux requêtes sur la plage spatiale (la plupart des travaux ont été effectués par des théoriciens et des praticiens de bases de données) au cours des 30 dernières années. Récemment, Sebastian Sylvain de Rare a donné un cours sur le GDC sur pourquoi ils travaillent aussi pour les jeux (spécialement sur les consoles avec des processeurs en ordre). Vous pouvez en apprendre plus à partir de son pdf: http://www.gdcvault.com/play/1012452/R-Trees-Adapting-out-of

Une implémentation naïve et simple est assez facile, et la structure de base vous donne beaucoup de place à l'amélioration (meilleure gestion de l'heuristique de fractionnement, opportunités de prélecture, recherche parallèle, etc.).

La réponse dépend fortement de la quantité de modèles que vous prévoyez d'utiliser. Je n'ai pas vraiment travaillé avec ce genre de choses pour XNA, mais si vous utilisez les AABB pour les tests et que vous n'avez pas trop de modèles, vous pourriez être assez bon avec un test de force brute. Peut-être même le jeter sur un fil. Je ne sais pas comment / s'il existe des optimisations SSE / VMX qui peuvent être utilisées pour C #, mais si vous parvenez à obtenir les AABB linéairement en mémoire (afin de ne pas manquer de cache pour le processeur), vous devriez pouvoir pour passer à travers une grande quantité de tests en peu de temps.