Me gustaría poder representar una gran población de pequeños objetos que se mueven independientemente en tiempo real. Pueden moverse como un enjambre, pero sus posiciones relativas no serán coherentes: su posición puede cambiar arbitrariamente dentro de un enjambre y los enjambres pueden romperse y reformarse en cualquier punto.
¿Qué enfoque para construir una jerarquía de volumen límite se adaptaría mejor a esta situación? ¿Una forma de mantener una jerarquía que es subóptima pero lo suficientemente buena, que solo requiere una actualización parcial de cada cuadro? ¿O hay una forma de construir una jerarquía desde cero en cada cuadro que sea lo suficientemente rápido para una animación fluida?
El número de objetos será demasiado grande para representarlo sin una jerarquía, pero por la misma razón espero que la construcción de la jerarquía lleve mucho tiempo.
Siguiendo el comentario de John Calsbeek, si mi centrarse en delimitar las jerarquías de volumen está mal orientado, y hay un mejor enfoque de partición de espacio para esta situación, por favor responda en consecuencia. Estoy buscando algo que pueda lidiar con lo que describo, incluyendo cualquier cosa en la que no haya pensado.
Comentarios
- ¿Está restringiendo intencionalmente la pregunta sobre las jerarquías de volumen delimitador, o está abierto a otras formas de particionamiento espacial?
- @JohnCalsbeek I ‘ he editado para aclarar – gracias por señalar mi restricción inadvertida.
- Considere tratar un » enjambre » como una sola unidad, cuando los enjambres se fusionen; fusionarlos en un solo enjambre, cuando un solitario se aleja demasiado, se convierte en un » enjambre » de uno. Esto funciona mejor si los enjambres tienden a ser cohesivos y los solitarios tienden a ser raros. Hay muchas formas interesantes de jugar con el » enjambre es una sola unidad » como permitir que los miembros cambien de enjambre solo cuando están en contacto entre sí, la lista sigue y sigue.
Respuesta
Considere utilizar hash espacial, especialmente si sus objetos tienen un tamaño similar.
Básicamente, divida su mundo en celdas de cuadrícula de tamaño uniforme (2D y 3D son posibilidades válidas dependiendo de la cantidad de movimiento vertical). En cada actualización, asigne su objeto a cada contenedor que se superponga; si las celdas tienen un tamaño decente en relación con los objetos, la mayoría de los objetos deberían terminar en un solo contenedor.
Cada contenedor se inserta en una tabla hash, siendo la clave las coordenadas del contenedor. (También puede pensar en ella como una tabla hash con varios valores para la misma clave e insertar un objeto una vez por cada celda que se superpone).
No hay jerarquía para reconstruir en este esquema, lo que lo hace muy adecuado para escenas dinámicas. Aún puede probar las dimensiones de la celda contra el tronco o contra los oclusores en un nivel aproximado y descartar muchos objetos a la vez. Además, es más fácil administrar esta estructura de manera incremental: puede mantener la tabla hash igual de un marco a otro y solo mover objetos de un contenedor a otro cuando cruzan el límite de una celda.
Respuesta
Puede intentar simplemente hacer que los volúmenes delimitadores sean un poco más grandes de lo necesario para que los objetos no crucen sus límites en cada movimiento, pero de nuevo, tendría que reconstruir la estructura de vez en cuando de todos modos.
O, existe una jerarquía de intervalo delimitado que intenta abordar precisamente esto escenario.
O bien, el artículo de Ingo Wald, Solomon Boulos y Peter Shirley titulado Ray Tracing Deformable Scenes Using Dynamic Bounding Volume Hierarchies podría de interés.
Respuesta
Me gustaría agregar una perspectiva práctica a esto.
Vamos me prefacio que estoy operando con información limitada aquí:
- No sé cómo cualquier objeto con el que esté tratando.
- No sé exactamente para qué se utiliza su estructura de aceleración. ¿Eliminación de Frustum? ¿Trazado de rayos? ¿Detección de colisiones entre objetos en el BVH?
De ahora en adelante, supongo que estás hablando de un frustum sacrificando algunos miles de objetos.
La cantidad de objetos será demasiado grande para renderizar sin una jerarquía, pero por la misma razón espero que la construcción de la jerarquía lleve mucho tiempo.
Yo diría que si tienes que visitar cada objeto en cada fotograma para calcular un BVH, eliminarlos directamente y sin un BVH es en realidad más rápido. Esto, por supuesto, depende de su implementación de selección de frustum. Los volúmenes delimitadores de todos los objetos deben almacenarse de forma contigua en la memoria. Esto da como resultado una utilización más eficiente de la memoria caché de la CPU y permite una mayor optimización mediante instrucciones SIMD. DICE tiene una presentación completa sobre este tema: Culling the Battlefield: Data Oriented Design in Practice
La presentación también menciona la aceleración de la selección selectiva aún más, usando una cuadrícula simple.
Dado que asumo que la mayoría de las bases de código 3D / simulación / juego ya tienen algún tipo de Clase BVH y no sé qué tan crítico es para usted obtener el MEJOR rendimiento de selección, me gustaría presentar algunos argumentos para seguir con un BVH:
Dependiendo del método que use, construir un BVH puede ser rápido y simple.
Mi implementación actual de un BVH binario (cada nodo solo puede tener cero o dos hijos y cada nodo hoja solo almacena un elemento) que está diseñado para tarda alrededor de 0,18 ms para 1137 objetos en un único subproceso de un i7-5960X a 3,89 GHz . Estoy seguro de que puede ser más rápido. La construcción se realiza sin reasignar la memoria en el proceso (esto duplicó el rendimiento de la construcción).
Si bien SAH puede generar el mejor BVH, lleva mucho tiempo. SAH es bueno para cosas que puede calcular previamente, como mallas de colisión. En tiempo de ejecución, puede colocar las mallas de colisión en un BVH que sea más adecuado para la construcción en tiempo real.
Un enfoque de construcción BVH rápido y simple (el que yo «que estoy usando actualmente) es ordenar todos los objetos en un eje (por ejemplo, el eje más largo del AABB principal) y dividir la colección en el medio.
Para acelerar aún más las cosas, calcule los AABB del nodo DESPUÉS de construir el árbol, combinando los dos AABB del nodo secundario de un nodo principal. Esto evita la iteración a través de todos los objetos (otra aceleración 2x). Sin embargo, esto solo es posible si su criterio de división no depende del AABB del padre.