¿Cuándo utilizar la partición del espacio binario, Quadtree, Octree?

Question

Recientemente aprendí sobre los árboles de partición de espacios binarios y su aplicación a gráficos 3D y detección de colisiones.También he examinado brevemente material relacionado con quadtrees y octrees.¿Cuándo usarías quadtrees en lugar de árboles bsp, o viceversa?¿Son intercambiables?Estarí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 completamente de cómo estén organizados sus datos.

Algo para tener en cuenta:

Los Quadtrees funcionan mejor para datos que son en su mayoría bidimensionales, como la representación de mapas en los sistemas de navegación.En este caso es más rápido que los octrees porque se adapta mejor a la geometría y mantiene pequeñas las estructuras de los nodos.

Los octárboles y BVH (jerarquías de volumen delimitadores) se benefician si los datos son tridimensionales.También funciona muy bien si tus entidades geométricas están agrupadas en un espacio 3D.(ver Octree y BVH)

El beneficio de Oc- y Quadtrees es que puedes dejar de generar árboles en cualquier momento que desees.Si desea representar gráficos utilizando un acelerador de gráficos, le permite simplemente generar árboles a nivel de objeto y enviar cada objeto en una única llamada de dibujo 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).

Los árboles BSP son realmente un caso especial.Funcionan muy, muy bien en 2D y 3D, pero generar buenos árboles BSP es una forma de arte en sí misma.Los árboles BSP tienen el inconveniente de que es posible que tengas que dividir tu geometría en partes más pequeñas.Esto puede aumentar el recuento general de polígonos de su conjunto de datos.Son buenos para renderizar, pero son mucho mejores para la detección de colisiones y el trazado de rayos.

Una buena propiedad de los árboles BSP es que descomponen una sopa de polígonos en una estructura que se puede representar perfectamente de atrás hacia adelante (y viceversa) desde cualquier posición de la cámara sin realizar una clasificación real.El orden desde cada punto de vista es parte de la estructura de datos y se realiza durante la compilación del árbol BSP.

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

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

Answer 2

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 estático geometría.Esto se debe a que los BSP-Trees son generalmente muy lentos de construir, y a menudo tardan horas o días para 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 los ejes, que tardan más en encontrar de manera óptima, y ​​(b) subdividen la geometría en los límites de los ejes, asegurando que ningún objeto cruce los planos de división.

Otros tipos de árboles 3D (Octrees, Quadtrees, kd-tree, Bounding-Volume-Hierarchy) utilizan volúmenes delimitadores alineados con ejes y se permite (opcionalmente) que los volúmenes se superpongan, por lo que no es necesario cortar los objetos contenidos en el volumen. límites.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 objetos dinámicos.

Extrapolando estos factores a situaciones...

Las áreas al aire libre suelen utilizar representaciones del suelo basadas en campos de altura, ya sean mapas de altura simples o técnicas de mapeo geo-mip más complejas como ROAM.El suelo en sí no participa en la partición del espacio 3D, sólo 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 un BVH), porque poner la geometría en un árbol BSP significaría duplicar y dividir el Geometría detallada 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 árbol BSP para mejorar el rendimiento del tiempo de ejecución.El hecho de que BSP-Tree divida la geometría en los límites de los nodos es útil para el rendimiento de renderizado, porque los nodos BSP se pueden usar como lotes de renderizado de triángulos preorganizados.El BSP-Tree también se puede optimizar para la oclusión, evitando la necesidad de dibujar partes del BSP-Tree que se sabe que están detrás de otra geometría.

Ver también: Octree y BVH, Tutorial de jerarquía de volúmenes delimitadores, Tutorial BSP.

Answer 3

Un BSP es mejor para entornos urbanos.

Un Quadtree es mejor cuando usas un mapa de altura para el terreno, etc.

Un Octtree es mejor cuando tienes grupos de geometría en el espacio 3D, como un sistema solar.

Answer 4

Los BSP son una buena opción para acelerar la detección de colisiones, según el tipo que utilice.Son particularmente rápidos en pruebas de puntos, 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, los BSP están bastante obsoletos.Los octárboles funcionan bien para cosas como la selección de visibilidad bruta, al igual que los árboles AABB.

Answer 5

No tengo mucha experiencia con BSP, pero puedo decir que debes usar octrees en lugar de 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 pequeña regla general.Generalmente, los octrees no suponen un coste enorme en comparación con los quadtrees y tienen el potencial de acelerar las cosas un poco.YMMV.

Answer 6

Generalmente estas cosas no tienen una respuesta clara.Sugeriría que A, B y C sean el resultado de una función del tamaño de su espacio y la cantidad de cosas que está diferenciando.

Answer 7

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

En cuanto a quadtree vs.octree: ¿cuántas dimensiones te importan mucho?Dos dimensiones significan un árbol cuádruple, cuatro un ocárbol.Como se indicó, un árbol cuádruple puede funcionar en tres espacios, pero si desea que cada dimensión reciba el tratamiento adecuado, un ocárbol es el camino a seguir.