Árbol AABB

Árbol AABB es Árbol de Cajas Acotadas Alineadas por los Ejes (AABB por sus siglas en idioma inglés, Axis Aligned Bounding Boxes) es una estructura de datos de subdivisión espacial y un conjunto de algoritmos usados principalmente para realizar intersecciones y calcular distancias de forma eficiente en objetos geométricos en 3D con un número finito de puntos. El conjunto objetos geométricos almacenados en la estructura de datos pueden usados para la detección de intersecciones, las intersecciones computacionales y distancias. Las consultas de intersecciones pueden ser de cualquier tipo siempre y cuando la clase cuente con los constructores requeridos. Las consultas sobre distancia solo se pueden expresar en función de un punto seleccionado. Ejemplos de intersecciones capaces de detectar son las producidas por objetos lineales (rayos, rectas, segmentos) con conjuntos de triángulos u otros objetos planos en el espacio. Ejemplo de las averiguaciones por distancia consiste en encontrar el punto más cercano a otro punto anteriormente prefijado en un conjunto de triángulos.

Historia

Camille Wormser y Pierre Alliez comenzaron a trabajar en una estructura de datos para la detección eficiente de colisión en 2007. El diseño genérico para la implementación de ambas consultas, por distancia y por intersección, así como las consultas genéricas y primitivas fue desarrollado por Camille Wormser. En 2009, Pierre Alliez, Stéphane Tayeb y Camille Wormser hicieron la implementación CGAL, con la ayuda de Laurent Rineau para optimizar la construcción del árbol.

Detalles de Implementación

El árbol AABB es construido a partir de un conjunto inicial de elementos (puntos, triángulos, polígonos, etc.). Este conjunto es ordenado a lo largo del mayor de los ejes de coordenada de esta caja. Los elementos del conjunto inicial son separados en dos subconjuntos iguales o al menos balanceados (Nota: el árbol AABB no tiene que ser necesariamente binario). Este método es aplicado recursivamente hasta llegar al caso base. Se suelen tomar varios casos bases, el tamaño de las cajas, la cantidad de subdivisiones, pero generalmente se usa la cantidad de elementos en una caja; aunque también se pueden combinar varios de estos casos bases.

Comparación con el Árbol kd

El árbol AABB se comporta generalmente de manera similar a un árbol k-dimensional (kd tree), pero existen varias diferencias entre ellos. Los árboles AABB no necesariamente son binarios y las unión de los nodos hijos puede ser más pequeña que el nodo su nodo padre; además, las particiones de los nodos hijo no siempre son disjuntas, ya que cuando un frontera de una caja atraviesa un elemento este elemento es ubicado las particiones de ambos hijos (en el árbol kd este elemento sería dividido y separado entre ambos hijos).

Enlaces externos

• CGAL 4.7 - 3D Fast Intersection and Distance Computation (AABB Tree)[1].