3d - Cuándo usar Partición de espacio binario, Quadtree, Octree?
space-partitioning (7)
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, los BSP son bastante obsoletos. Los octrees funcionan bien para cosas como la eliminación de visibilidad bruta, al igual que los árboles AABB.
Recientemente aprendí sobre árboles binarios de particionamiento de espacio 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?
No tengo mucha experiencia con BSP, pero puedo decir que deberías 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.
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.
Un BSP es mejor para entornos urbanos.
Un Quadtree es mejor para cuando usas un mapa de altura para el terreno, etc.
Un octárbol es mejor para cuando tienes grupos de geometría en el espacio 3D, como un sistema solar.
Un BSP es mejor para un espacio más pequeño y más simple con el que solo desea 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 el tratamiento adecuado, un octree es el camino a seguir.
No hay una respuesta clara a tu pregunta. Depende totalmente de cómo se organicen sus datos.
Algo para tener en cuenta:
Los Quadtrees funcionan mejor para datos que en su mayoría son bidimensionales, como la representación de mapas en los 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 los BVH (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. (ver Octree vs BVH )
El beneficio de Oc y Quadtrees es que puedes dejar de generar árboles cuando lo desees. 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 funciona mucho mejor que enviar triángulos individuales (algo que tienes que hacer si usas BSP-Trees en toda su extensión).
BSP-Trees es 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 buena propiedad de los BSP-trees es que descomponen una sopa de polígono en una estructura que puede ser perfectamente representada hacia atrás (y viceversa) desde cualquier posición de la cámara sin hacer una clasificación 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.
Eso, 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.
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) usan 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 ningún objeto cruce planos divididos.
Otros tipos de árboles 3d (Octrees, Quadtrees, kd-tree, Bounding-Volume-Hierarchy) utilizan volúmenes delimitadores alineados con el eje, y los volúmenes (opcionalmente) se pueden solapar, por lo que los objetos contenidos no necesitan ser cortados 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 en situaciones ...
Las áreas al aire libre generalmente utilizan representaciones de terreno basadas en el campo de altura, ya sea en mapas de altura simples o en técnicas de mapeo geo-mip más complejas 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 colocar la geometría en un árbol BSP significaría duplicar y dividir el árbol. 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.
Ver también: Octree vs BVH , Tutorial de jerarquización del volumen delimitador , Tutorial de BSP .