Cajas delimitadas en octrees

9

He visto que los octrees a menudo se usan para cosas como el sacrificio de frustum y la detección de colisiones en 3D. Pero no estoy seguro de cómo funciona el algoritmo. Seguramente todo el principio del octree se rompe cuando intenta usar cuadros delimitadores, porque cualquier cuadro dado podría almacenarse en un nodo, pero en realidad se superpone al espacio representado por otro nodo. Además, no estoy seguro de cómo puede funcionar esto para buscar cuadros delimitadores en lugar de puntos, porque una vez más, podría estar atrapado mirando prácticamente todos los nodos, lo que frustra el propósito.

Entonces, ¿cómo diablos lidian los octrees con cajas delimitadoras?

collision-detection algorithm DeadMG
fuente

Respuestas:

12

Un Octree (3D) usa los mismos conceptos que un Quadtree (2D). Si lee y comprende el artículo de Wikipedia en Quadtrees, debería poder aplicar los mismos conceptos en 3D.

Ambos árboles le permiten usar búsquedas basadas en áreas que pueden reducir en gran medida la cantidad de comparaciones necesarias para determinar qué objetos hay en un área determinada. Esto puede ser útil para el sacrificio visual, o incluso para colisiones, dependiendo de su juego.

El concepto básico es que el espacio-mundo se divide en "cubos": cuadrados para 2D o cubos para 3D. Con un mundo vacío, comienzas con un solo cubo o cubo que cubre todo el mundo. A medida que agrega objetos al mundo, comienza en el nodo raíz y avanza hacia el árbol según la ubicación y el tamaño del objeto. Si el depósito de destino alcanza su capacidad, lo subdivide dividiendo cuadrados en 4 cuadrados más pequeños (Quadtree), o dividiendo cubos en 8 cubos más pequeños (Octree). Cada objeto que agregue al mundo solo se inserta tan profundamente en el árbol como físicamente puede caber completamente dentro de los límites del cubo. Si un objeto no cabe dentro de los límites del depósito actual, debe mover el objeto al depósito principal más pequeño en el que quepa completamente.

Tenga en cuenta que usar Quadtree u Octree es excesivo si no tiene muchos objetos en su mundo. También hay soluciones de código abierto para ambos.

John McDonald
fuente
Creo que él lo sabe. Creo que la confusión es sobre cómo manejar un volumen que no encaja bien en una subdivisión.
ClassicThunder
2
Menciono que "Si un objeto no cabe dentro de los límites, debe almacenarse una capa hacia arriba". Y también parecía que el OP estaba un poco confundido sobre cómo funcionaba Octrees en general, según su segunda oración.
John McDonald
¿No viola la restricción fundamental de los octrees, que solo hay siete o menos en cada nodo?
DeadMG
Quiero decir, si tuviera N objetos que se extendieran a lo largo del límite, entonces estaría mirando O (N) cheques para verificar cada uno de ellos.
DeadMG
@DeadMG, "Oct" como en Ocho (octágono, octano, etc.). Cuando el nodo raíz se divide, tendrá 8 hijos: Norte Este Arriba, Nordeste Abajo, NWU, NWD, SEU, SED, SWU y SWD para un total de 9 nodos incl. la raíz. Si uno de estos nodos secundarios se divide, ese nodo también tendrá 8 subnodos, uno para cada cuadrante como antes, lo que hace un total de 8 + 8 + 1 = 17 nodos. Si todos sus objetos encajan en el límite del nodo raíz y no caben dentro de ninguno de los 8 cuadrantes, sí, será O (N) y tendrá que verificar cada objeto y no podrá guardar ninguno compara, de hecho, tendrá un costo probable.
John McDonald
3

Los n-árboles son el sistema de partición espacial más famoso pero no el único disponible. Hay muchos, muchos otros. Un poco más de información sobre los datos que tiene ayudaría mucho a encontrar la mejor opción. ¿Sus cajas cambian de tamaño o se mueven? ¿Qué tan grandes son? ¿Cuántos hay? ¿Tiene muchas inserciones / extracciones?

Especies desconocidas
fuente