Cuándo usar particionamiento de espacio binario, Quadtree, Octree?

Question

Recientemente he aprendido sobre los árboles de particionamiento de espacio binario y su aplicación a gráficos 3D y detección de colisión. También he examinado brevemente el material relacionado con quadtrees y octrees. ¿Cuándo usarías quadtrees sobre bsp trees, o viceversa? ¿Son intercambiables? Me sentiría satisfecho si tuviera suficiente información para completar una tabla como esta:

  | BSP | Quadtree | Octree 
------------+----------------+------- 
Situation A | X |   | 
Situation B |  |  X | 
Situation C |  |   | X 

¿Qué son A, B y C?

Answer 1

No hay una respuesta clara a su pregunta. Depende totalmente de cómo se organicen sus datos.

Algo a tener en cuenta:

Quadtrees funcionan mejor para los datos que se encuentran en su mayoría en dos dimensiones como un mapa-renderizado en sistemas de navegación. En este caso, es más rápido que octrees porque se adapta mejor a la geometría y mantiene pequeñas las estructuras de los nodos.

Los octrees y BVHs (Jerarquías de volumen delimitador) se benefician si los datos son tridimensionales. También funciona muy bien si tus entidades geométricas están agrupadas en un espacio tridimensional. (Consulte Octree vs BVH)

La ventaja de Oc y Quadtrees es que puede dejar de generar árboles en cualquier momento que desee. Si desea representar gráficos utilizando un acelerador de gráficos, solo puede generar árboles en un nivel de objeto y enviar cada objeto en una única llamada de arrastrar a la API de gráficos. Esto realiza mucho mejor que enviar triángulos individuales (algo que tienes que hacer si usas BSP-Trees en toda su extensión).

BSP-Trees son realmente un caso especial. Funcionan muy bien en 2D y 3D, pero generar buenos BSP-Trees es una forma de arte en sí misma. BSP-Trees tiene el inconveniente de que puede tener que dividir su geometría en piezas más pequeñas. Esto puede aumentar el recuento total de polígonos de su conjunto de datos. Son agradables para renderizar, pero son mucho mejores para la detección de colisiones y el trazado de rayos.

Una propiedad agradable de los BSP-trees es que descomponen una sopa de polígono en una estructura que se puede representar perfectamente hacia atrás (y viceversa) desde cualquier posición de la cámara sin hacer un tipo real. El orden de cada punto de vista es parte de la estructura de datos y se realiza durante la compilación de BSP-Tree.

Esa, por cierto, es la razón por la que fueron tan populares hace 10 años. Quake los utilizó porque permitía que el rasterizador de motor/software gráfico no utilizara un z-buffer costoso.

Todos los árboles mencionados son solo familias de árboles. Hay octrees sueltos, árboles híbridos de árboles kd y muchas otras estructuras relacionadas también.

Answer 2

No tengo mucha experiencia con BSP, pero puedo decir que debes ir con octrees sobre quadtrees cuando la escena que estás renderizando es alta. Es decir, la altura es más de la mitad del ancho y la profundidad, una regla general. En general, los octrees no representarán un gran costo sobre los quadtrees y tienen el potencial de acelerar un poco las cosas. YMMV.

Answer 3

Por lo general, estas cosas no tienen una respuesta clara. Sugeriría que A, B y C son el resultado de una función del tamaño de tu espacio y la cantidad de cosas que estás diferenciando.

Answer 4

Un BSP es mejor para un espacio más pequeño y más simple con el que solo desee realizar la oclusión. Si quieres todas las intersecciones para un rayo determinado, deberás actualizar a un quad/octree.

En cuanto a quadtree vs. octree, ¿de qué dimensiones te preocupas mucho? Dos dimensiones significan un quadtree, cuatro un octree. Como se dijo, como quadtree puede funcionar en tres espacios, pero si desea que cada dimensión reciba un tratamiento adecuado, un octree es el camino a seguir.

Answer 5

Un BSP es el mejor para entornos urbanos.

Un Quadtree es mejor para cuando se utiliza un mapa de altura de terreno, etc.

Un octárbol es mejor para cuando tenga grumos de la geometría en el espacio 3D, tales como un sistema solar.

Answer 6

Los BSP son una buena opción para acelerar la detección de colisiones, dependiendo del sabor que use. Son particularmente rápidos en pruebas de puntos y líneas o rayos, algo menos rápidos y un poco más complicados para cosas con volumen.

En cuanto a su uso en gráficos, BSP son bastante obsoletos. Los octrees funcionan bien para cosas como la eliminación de visibilidad bruta, al igual que los árboles AABB.

Answer 7

La mayor diferencia práctica entre BSP-Trees y otros tipos de árboles 3d es que BSP-Trees puede ser más óptimo pero solo funciona en geometría estática. Esto se debe a que los árboles BSP generalmente son muy lentos de construir, a menudo demoran horas o días en un nivel típico de juego urbano estático. Las dos razones principales por las que los BSP-Trees tardan más en construirse son (a) utilizan planos de división no alineados con el eje, que tardan más en encontrarlos óptimamente, y (b) subdividen la geometría en los límites del eje, asegurando que no haya objetos cruzar planos divididos.

Otros tipos de árboles 3d (Octrees, Quadtrees, kd-tree, Bounding-Volume-Hierarchy) utilizan volúmenes delimitadores alineados con los ejes, y los volúmenes (opcionalmente) se pueden superponer, por lo que los objetos contenidos no necesitan ser cortado en los límites de volumen. Ambos hacen que los árboles sean menos óptimos que los árboles BSP, pero más rápidos de construir y más fáciles de cambiar para los objetos dinámicos.

Extrapolando estos factores en situaciones ... áreas

al aire libre suelen utilizar representaciones basadas en tierra de altura sobre el terreno, ya sea heightmaps simples o técnicas de geo-mapeo MIP más complejos como ROAM. El suelo en sí mismo no participa en la división del espacio en 3D, solo los objetos colocados en el suelo.

Los mundos con muchas instancias de geometría más simple y similar (casas, árboles, asteroides, etc.) a menudo usarán un árbol que no sea BSP (como BVH), porque poner la geometría en un árbol BSP significaría duplicar y dividir la geometría de detalle para cada instancia.

Por el contrario, una gran malla estática personalizada sin instancias, como una escena urbana o un entorno interior complejo, normalmente utilizará un BSP-Tree para un mejor rendimiento en tiempo de ejecución. El hecho de que BSP-Tree divide la geometría en los límites de los nodos es útil para el rendimiento de la representación, ya que los nodos BSP se pueden utilizar como lotes de representación de triángulos preorganizados. El BSP-Tree también se puede optimizar para la oclusión, evitando la necesidad de dibujar porciones del BSP-Tree que se sabe están detrás de otra geometría.

Véase también: Octree vs BVH, Bounding Volume Hierarchy Tutorial, BSP Tutorial.