¿Cuál es una buena solución de estructura de datos para un administrador de escena en XNA?

8

Estoy jugando con XNA para un proyecto de juego mío, tuve una exposición previa a OpenGL y trabajé un poco con Ogre, así que estoy tratando de hacer que los mismos conceptos funcionen en XNA.

Específicamente, estoy tratando de agregar a XNA un administrador de escena para manejar transformaciones jerárquicas, eliminación de objetos (quizás incluso oclusión) y clasificación de objetos de transparencia.

Mi plan era construir un administrador de escena de árbol para manejar las transformaciones jerárquicas y la iluminación, y luego usar un Octree para la eliminación de objetos y la clasificación de objetos. El problema es cómo ordenar la geometría para admitir transparencias correctamente. Sé que la clasificación es muy costosa si se realiza por polígono, tan costosa que ni siquiera es administrada por Ogre. Pero las imágenes fijas de Ogre se ven bien.

¿Alguna idea sobre cómo hacerlo y qué estructuras de datos usar y sus capacidades? Sé que la gente alrededor está usando:

  • Octrees
  • Kd-trees (alguien en el foro de GameDev dijo que estos son mucho mejores que Octrees)
  • BSP (que debe manejar el pedido por polígono pero es muy costoso)
  • BVH (pero solo para eliminación de frustum y oclusión)

Gracias

Tunnuz

Tunnuz
fuente

Respuestas:

6

Los octtreos (o incluso solo los cuadrúpedos) y los árboles Kd son buenos esquemas de partición espacial de propósito general, y si su tubería de construcción y / o motor los está generando, encontrará que son útiles de muchas maneras diferentes para optimizar las consultas. / iteraciones. Funcionan subdividiendo un volumen fijo de forma jerárquica, lo que hace que las consultas como la emisión de rayos en su espacio de objetos sean muy baratas de consultar (ideal para verificaciones de colisión).

Las jerarquías de volumen delimitador funcionan de una manera ligeramente diferente (agregan los volúmenes de los objetos en el árbol en lugar de subdividir espacios), y son una forma simple de recortar cosas innecesarias para que no se repitan. Pero debido a que BVH no impone restricciones sobre cómo se relacionan dos nodos hermanos, no es un buen esquema para determinar el orden de representación o para consultas de colisión arbitrarias.

Los sistemas BSP son buenos cuando subdivide el mundo en función de polígonos individuales, pero para objetos más grandes, un enfoque basado en el volumen tiene más sentido.

Sin embargo, sobre todo, vale la pena señalar que ninguno de estos sistemas es perfecto para determinar el orden de procesamiento para la transparencia, incluso el enfoque BSP. Siempre será posible construir geometría que rompa su algoritmo, a menos que pueda subdividir polígonos sobre la marcha. Lo más probable es que esté buscando una solución de "mejor esfuerzo", donde la geometría se puede ordenar correctamente en la mayoría de los casos; y el equipo de arte puede subdividir los modelos para cualquiera de los casos que no funcionan (porque los modelos / polígonos son anormalmente grandes, largos o auto intersectables). Los modelos / nodos más pequeños siempre son mucho más fáciles de clasificar 'correctamente', pero se paga por los gastos generales de iteración.

Kd-trees y Oct / quad-trees son buenas soluciones de propósito general, para las cuales se puede escribir una implementación amigable para la plataforma, pero al final tendrá que equilibrar la profundidad / complejidad de su árbol de partición espacial contra el costo de iterarlo, y la sobrecarga por modelo (es decir, dibujar el costo de la llamada). Si está apuntando a XNA, le recomiendo que mantenga un nivel simple y alto, y si hay problemas de clasificación con parte del contenido, entonces considere cambiar el contenido antes de intentar mejorar su motor hasta que pueda hacer frente a él; los retornos disminuyen muy rápidamente después de que se implementa la clasificación de renderizado más básica.

MrCranky
fuente
He leído que incluso las técnicas de pelado de profundidad para manejar la clasificación por fragmento a menudo obtienen buenos resultados. ¿Crees que esto es factible en un motor de juego pequeño? ¿Los juegos AAA usan estas técnicas?
tunnuz
¿Qué crees que es mejor / más fácil de implementar entre Kd-trees y Octrees?
tunnuz
Me sorprendería mucho si ya no hubiera una implementación de C # para ambos: es el tipo de cosas donde la carne (la subdivisión y la consulta) es la misma para todas las implementaciones, pero los bits interesantes (cómo iterar / consultar / asociar elementos con los nodos) puede variar. Oct / quad-trees son, en mi opinión, conceptualmente más simples, pero como se ha señalado, los kd-trees son más eficientes en una variedad de formas. Probablemente iría a kd-tree solo porque si puedes hacer eso, puedes hacer oct-trees (pero lo contrario no es necesariamente cierto).
MrCranky
1
En cuanto a la clasificación por fragmento: sin saber nada sobre su motor es difícil de decir, pero se siente como una optimización prematura. Sí, los juegos AAA pueden usar esas técnicas, pero también barajarán más objetos de los que un motor XNA podrá manejar, por lo que requieren técnicas de optimización más extremas para aprovecharlo al máximo. Mi consejo siempre sería lograr que los conceptos básicos (clasificación de transparencias) se realicen de manera sólida, y si encuentra que el rendimiento no está a la altura, entonces hágalo todo y haga una clasificación más fina. Lo más probable es que algo más limitará el rendimiento primero.
MrCranky
1
En realidad, hay desarrolladores AAA que se saltan el uso del árbol de BV, ya que lo hacen con fuerza bruta y al mismo tiempo se aseguran de que realmente utilices la mayoría de los ciclos de reloj de manera eficiente (sin errores de caché LHS / L2 + L1, etc.) proporciona un rendimiento lo suficientemente bueno. Es sorprendente la cantidad de pruebas que puede realizar con un sistema bien diseñado.
Simon
3

McCranky cubrió asombrosamente todas las estructuras de datos que mencionó, sin embargo, veo que no ha considerado los R-Trees. El conjunto de conocimientos sobre esas estructuras es enorme, y son muy adecuados para consultas de rango espacial (la mayor parte del trabajo ha sido realizado por teóricos y profesionales de bases de datos) en los últimos 30 años. Recientemente, Sebastian Sylvain de Rare ha impartido un curso sobre GDC sobre por qué también funcionan para juegos (especialmente en consolas con procesadores en orden). Puede obtener más información en su pdf: http://www.gdcvault.com/play/1012452/R-Trees-Adapting-out-of

Una implementación ingenua y simple es bastante fácil, y la estructura básica le da mucho margen de mejora (mejor gestión de heurística de división, oportunidades de captación previa, búsqueda paralela, etc.).

Caballero rojo
fuente
2

La respuesta depende en gran medida de la cantidad de modelos que planea utilizar. Realmente no he trabajado con este tipo de cosas para XNA, pero si usa AABB para las pruebas y no tiene demasiados modelos, podría ser lo suficientemente bueno con una prueba de fuerza bruta. Quizás incluso tirarlo en un hilo. No estoy seguro de cómo / si hay optimizaciones SSE / VMX que se pueden usar para C #, pero si logra obtener los AABB linealmente en la memoria (para que no obtenga errores de caché para la CPU), debería poder superar una gran cantidad de pruebas en muy poco tiempo.

Simón
fuente