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.
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.).
fuente
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.
fuente