¿Cuál es el estado del arte en Particionamiento espacial para juegos? [cerrado]

Sé sobre árboles BSP, octrees y portal que se utilizaron durante mucho tiempo. ¿Pero los juegos modernos todavía usan estos sistemas o están usando cosas nuevas?

Si es posible con pros y contras, considere la posibilidad de renderizar y detectar colisiones.

Sí, el Unreal engine 3, por ejemplo, todavía usa un BSP, principalmente porque se usa durante el proceso CSG. Doom3 / id tech 4 usa portales, y creo que he leído algo que id Tech 5 ha vuelto a los árboles BSP. Hay algunos juegos que también usan octrees. En el juego, entiendo que UE3 se movió a un enfoque más dinámico con consultas de oclusión, pero me sorprendería si no usan el BSP para al menos determinar qué mallas estáticas están a la vista. Otros juegos pueden usar el sacrificio de vista-frustum (Civilization, por ejemplo). Realmente depende del tipo de juego que busques.

La razón por la que los BSP y otras cosas siguen existiendo es porque no puedes hacerlo mucho mejor. Si tiene geometría estática, un BSP es excelente si lo construye correctamente. Sin embargo, requiere que escriba un creador de BSP, lo cual es complicado (¡pero podría suceder de forma gratuita si su solución CSG usa uno!) Los octrees y las soluciones más dinámicas (como confiar en consultas de oclusión para todo) son más simples de implementar, tienen un mayor tiempo de ejecución costo pero no requiere preprocesamiento (costoso) de los niveles. Esa es una compensación que algunos juegos están dispuestos a hacer (Crytek, por ejemplo, quiere que todo se ejecute en tiempo real, por lo que no pasan tiempo de procesamiento para construir una estructura de aceleración estática). Otros enfoques de tiempo de ejecución son, por ejemplo, la rasterización del software en la CPU y realizar consultas de oclusión en la CPU (esto es utilizado por el motor Frostbite).

Para un enfoque realmente moderno, mire Umbra , que es un middleware para consultas de visibilidad. Si busca un poco en la web, debería encontrar algunas de las tesis de maestría que describen los inicios de Umbra.

En pocas palabras: si desea utilizar un BSP / Octree / no AS dependerá en gran medida del tipo de juego que desee crear. Si sus niveles son mayormente estáticos, debe aprovechar eso y construir una estructura de aceleración estática. Si todo es dinámico, necesita, por supuesto, otro enfoque.

Para la detección de colisión, echaría un vistazo a Bullet y PhysX y sus algoritmos de detección de colisión. Pero tengo la sensación de que las soluciones físicas están menos ligadas a la visibilidad de lo que solían estar: una solución física podría querer usar un BVH basado en GPU, en ese caso, no tiene mucho sentido tratar de usar eso para consultas de visibilidad.

Sinceramente, no sé qué motores de próxima generación están utilizando en estos días, pero les diré lo que sí sé. Es fácil confundirse entre una optimización y la estructura de datos utilizada para ayudar en esa optimización. Sin embargo, todas las cosas mencionadas a continuación son para optimizaciones, pero señalaré cuáles son estructuras de datos específicamente.

BSP : Estructura de datos: para detectar la intersección entre los objetos dinámicos en movimiento y la geometría estática del mundo. Solía ​​usarse tanto para la detección de colisiones como para la representación de la geometría correctamente sin un zbuffer, pero ya no se usa para renderizar ya que tenemos suficiente memoria para el búfer az hoy en día. Sin embargo, técnicamente se generan de manera ligeramente diferente, pero aún se consideran el mismo tipo de árbol. Requiere preprocesamiento.

Octree o Kd-Tree : Estructura de datos: se usa para determinar qué objetos están en la misma "celda" o área para evitar hacer una comprobación n ^ 2 en todos los objetos dinámicos.

Estos no son los únicos, pero probablemente sean los más comunes. También hay muchas optimizaciones que permiten que el motor evite renderizar la geometría en general. Pero lo siguiente simplemente elimina la geometría, y eso es generalmente para lo que se usa:

Portales : técnicamente no es una estructura de datos, pero requiere una estructura especial para hacer el sacrificio. Se utiliza para seleccionar la visibilidad de la geometría mundial y la geometría dinámica de los objetos desde la vista. Requiere preprocesamiento para dividir el mundo en áreas, creo. Pero en realidad no he implementado esto, así que no lo sé.

Eliminación de oclusión : optimización: se utiliza para la eliminación de visibilidad para lo que desee, probablemente objetos dinámicos.

Selección regular de Viewport : Optimización: elimina objetos que no están en la vista de la cámara.

Más selección de vistas : Optimización: la selección regular de vistas se puede optimizar aún más mediante el uso de un octree. Puede eliminar celdas enteras del octree que están detrás de la cámara o no a la vista. Esto incluye parches de terreno (si está afuera). Lo que no sea seleccionado por el octree, realizaría un "sacrificio de viewport regular". Entonces, lo que queda, se renderizaría.

Selección posterior : optimización: elimina la geometría de la cámara para evitar la rasterización. Por lo general, se realiza en hardware si el estado de representación está configurado correctamente.

Estructuras de datos de casos especiales:

Árboles AABB o árboles Esfera : son estructuras de datos de casos especiales. Convierten una forma cóncava en una convexa. Por ejemplo, un personaje con huesos es técnicamente cóncavo. Lo divide en pedazos convexos más pequeños. Se puede utilizar como una optimización para la detección de colisiones, la eliminación de visibilidad de objetos dinámicos (por lo general) y facilita la realización de pruebas de intersección ya que es convexo. Estos irían dentro de say, un octree ya que generalmente son objetos dinámicos. Estos también podrían usarse para ayudar con la optimización de la eliminación de oclusiones.

No hay ninguna razón por la que tenga que usar una sola estructura para representar todo (como un gráfico de escena). En mi opinión, sería mejor usar diferentes estructuras de datos para diferentes tareas en lugar de intentar usar un árbol de propósito general de algún tipo. Por ejemplo, en el motor en el que estoy trabajando actualmente, planeo implementar una combinación de árbol BSP / Octree / AABB con las siguientes optimizaciones: eliminación de oclusión, ventana gráfica y, por supuesto, eliminación de superficie posterior. Esto significa que tendré un árbol bsp, un octree y probablemente varios árboles aabb dentro de ese octree.

La selección de las mejores estructuras de datos y algoritmos / optimizaciones es probablemente la cosa más grande y más beneficiosa que puede hacer por su motor.