Octárbol

Un octree es una estructura de datos en forma de árbol en la que cada nodo interno tiene exactamente ocho hijos . Los octrees se utilizan con mayor frecuencia para particionar un espacio tridimensional subdividándolo recursivamente en ocho octantes . Los octrees son el análogo tridimensional de los quadtrees . La palabra se deriva de oct (raíz griega que significa "ocho") + tree . Los octrees se utilizan a menudo en gráficos 3D y motores de juegos 3D .

Cada nodo de un octree subdivide el espacio que representa en ocho octantes . En un octree de región de puntos (PR), el nodo almacena un punto tridimensional explícito , que es el "centro" de la subdivisión de ese nodo; el punto define una de las esquinas de cada uno de los ocho hijos. En un octree basado en matrices (MX), el punto de subdivisión es implícitamente el centro del espacio que representa el nodo. El nodo raíz de un octree PR puede representar un espacio infinito; el nodo raíz de un octree MX debe representar un espacio limitado finito para que los centros implícitos estén bien definidos. Tenga en cuenta que los octrees no son lo mismo que los árboles k -d : los árboles k -d se dividen a lo largo de una dimensión y los octrees se dividen alrededor de un punto. Además, los árboles k -d siempre son binarios, lo que no es el caso de los octrees. Al utilizar una búsqueda en profundidad, se deben recorrer los nodos y solo se deben ver las superficies requeridas.

El uso de octrees para gráficos de computadora en 3D fue iniciado por Donald Meagher en el Instituto Politécnico Rensselaer , descrito en un informe de 1980 "Codificación de octree: una nueva técnica para la representación, manipulación y visualización de objetos 3D arbitrarios por computadora", ^[1] para el cual posee una patente de 1995 (con fecha de prioridad de 1984 ) "Generación de imágenes de alta velocidad de objetos sólidos complejos utilizando codificación de octree" ^[2]

• Nivel de detalle de la representación en gráficos por ordenador en 3D ^[3]
• Indexación espacial
• Búsqueda del vecino más cercano ^[4]
• Detección eficiente de colisiones en tres dimensiones
• Ver el descarte del tronco truncado
• Método multipolar rápido
• Cuadrícula no estructurada
• Análisis de elementos finitos
• Octárbol de vóxeles dispersos ^[5]
• Estimación del estado ^[6]
• Estimación de conjuntos ^[7]

El algoritmo de cuantificación de color octree, inventado por Gervautz y Purgathofer en 1988, codifica los datos de color de la imagen como un octree de hasta nueve niveles de profundidad. Los octrees se utilizan porque y hay tres componentes de color en el sistema RGB . El índice de nodo desde el que se ramifica en el nivel superior se determina mediante una fórmula que utiliza los bits más significativos de los componentes de color rojo, verde y azul, por ejemplo, 4r + 2g + b. El siguiente nivel inferior utiliza la siguiente significación de bit, y así sucesivamente. A veces se ignoran los bits menos significativos para reducir el tamaño del árbol.${\displaystyle 2^{3}=8}$

El algoritmo es muy eficiente en el uso de la memoria porque el tamaño del árbol puede ser limitado. El nivel inferior del octree consta de nodos de hoja que acumulan datos de color no representados en el árbol; estos nodos contienen inicialmente bits individuales. Si se ingresan en el octree muchos más colores de la paleta que el número deseado, su tamaño se puede reducir continuamente buscando un nodo de nivel inferior y promediando sus datos de bits en un nodo de hoja, podando parte del árbol. Una vez que se completa el muestreo, explorar todas las rutas en el árbol hasta los nodos de hoja, tomando nota de los bits a lo largo del camino, dará como resultado aproximadamente la cantidad requerida de colores.

El esquema de algoritmo recursivo de ejemplo que se muestra a continuación ( sintaxis de MATLAB ) descompone una matriz de puntos tridimensionales en contenedores de estilo octree. La implementación comienza con un solo contenedor que rodea todos los puntos dados, que luego se subdivide recursivamente en sus 8 regiones de octree. La recursión se detiene cuando se cumple una condición de salida determinada. Algunos ejemplos de tales condiciones de salida (que se muestran en el código a continuación) son:

• Cuando un contenedor contiene menos de un número determinado de puntos
• Cuando un contenedor alcanza un tamaño o volumen mínimo en función de la longitud de sus bordes
• Cuando la recursión ha alcanzado un número máximo de subdivisiones

función [binDepths, binParents, binCorners, pointBins] = OcTree ( puntos ) binDepths = [ 0 ] % Inicializa una matriz de profundidades de bin con este único bin de nivel base binParents = [ 0 ] % Este bin de nivel base no es un hijo de otros bins binCorners = [ min ( points ) max ( points )] % Rodea todos los puntos en el espacio XYZ pointBins (:) = 1 % Inicialmente, todos los puntos se asignan a este primer bin divide ( 1 ) % Comienza a dividir este primer bin              función dividir ( binNo ) % Si este contenedor cumple alguna condición de salida, no lo divida más. binPointCount = nnz ( pointBins == binNo ) binEdgeLengths = binCorners ( binNo , 1 : 3 ) - binCorners ( binNo , 4 : 6 ) binDepth = binDepths ( binNo ) exitConditionsMet = binPointCount < valor || min ( binEdgeLengths ) < valor || binDepth > valor si exitConditionsMet return ; % Salir de la función recursiva fin                         % De lo contrario, divide este bin en 8 nuevos sub-bins con un nuevo punto de división newDiv = ( binCorners ( binNo , 1 : 3 ) + binCorners ( binNo , 4 : 6 )) / 2 para i = 1 : 8 newBinNo = length ( binDepths ) + 1 binDepths ( newBinNo ) = binDepths ( binNo ) + 1 binParents ( newBinNo ) = binNo binCorners ( newBinNo ) = [ uno de los 8 pares de newDiv con minCorner o maxCorner ] oldBinMask = pointBins == binNo % Calcula qué puntos en pointBins == binNo pertenecen ahora a newBinNo pointBins ( newBinMask ) = newBinNo % Divide recursivamente este bin recién creado divide ( newBinNo ) end                                                 

Tomando la lista completa de colores de una imagen RGB de 24 bits como entrada puntual para la implementación de la descomposición de puntos de Octree descrita anteriormente, el siguiente ejemplo muestra los resultados de la cuantificación de color de Octree. La primera imagen es la original (532818 colores distintos), mientras que la segunda es la imagen cuantificada (184 colores distintos) utilizando la descomposición de Octree, con cada píxel asignado al color en el centro del contenedor de Octree en el que cae. Alternativamente, los colores finales podrían elegirse en el centroide de todos los colores en cada contenedor de Octree, sin embargo, este cálculo adicional tiene muy poco efecto en el resultado visual. ^[8]

% Leer la imagen RGB original Img = imread ( 'IMG_9980.CR2' ); % Extraer píxeles como tripletes de puntos RGB pts = reshape ( Img , [], 3 ); % Crear un objeto de descomposición OcTree utilizando una capacidad de bin de destino OT = OcTree ( pts , 'BinCapacity' , ceil (( size ( pts , 1 ) / 256 ) * 7 )); % Encontrar qué bins son "nodos de hoja" en el objeto octree leafs = find ( ~ ismember ( 1 : OT . BinCount , OT . BinParents ) & ... ismember ( 1 : OT . BinCount , OT . PointBins )); % Encuentra la ubicación RGB central de cada bin de hojas binCents = mean ( reshape ( OT . BinBoundaries ( leafs ,:), [], 3 , 2 ), 3 ); % Crea una nueva imagen "indexada" con un mapa de color ImgIdx = zeros ( size ( Img , 1 ), size ( Img , 2 )); for i = 1 : length ( leafs ) pxNos = find ( OT . PointBins == leafs ( i )); ImgIdx ( pxNos ) = i ; end ImgMap = binCents / 255 ; % Convierte colores de 8 bits a valores RGB de MATLAB % Muestra la imagen original de 532818 colores y la imagen resultante de 184 colores figure subplot ( 1 , 2 , 1 ), imshow ( Img ) title ( sprintf ( 'Imagen en color original de %d' ,                                                     tamaño ( único ( pts , 'filas' ), ​​1 ))) subparcela ( 1 , 2 , 2 ), imshow ( ImgIdx , ImgMap ) título ( sprintf ( 'Imagen en color %d cuantificada en octree' , tamaño ( ImgMap , 1 )))       

• Partición del espacio binario
• Jerarquía de intervalos delimitadores
• Cube 2: Sauerbraten , un motor de juego 3D en el que la geometría se basa casi en su totalidad en octrees
• id Tech 6 es un motor de juego 3D que utiliza vóxeles almacenados en octrees.
• Irrlicht Engine , compatible con nodos de escena octree
• El problema de la medida de Klee
• Octárbol lineal
• OGRE , tiene una implementación del administrador de escenas octree
• Subpavimentación
• Vóxel
• Árbol cuaternario

Wikimedia Commons alberga una categoría multimedia sobre Octrees .

• Revista de cuantificación de Octree en sistemas Microsoft
• Cuantificación de color mediante octrees en Dr. Dobb's
• Descripción general de la cuantificación de color de Octree
• Sojan Lal, P.; Unnikrishnan, A.; Poulose Jacob, K. (1998). "Implementación paralela del algoritmo de generación de octtree". Actas de la Conferencia Internacional sobre Procesamiento de Imágenes de 1998. ICIP98 (Cat. N.° 98CB36269) . Vol. 3. págs. 1005–1009. doi :10.1109/ICIP.1998.727419. ISBN 0-8186-8821-1.S2CID 195863788  .
• Generación de octrees a partir de escaneos de trama con pérdida de información reducida, P. Sojan Lal, A Unnikrishnan, K Poulose Jacob, IASTED International conference VIIP 2001 [1] ^{[ enlace muerto permanente ‍ ]}
• Octárboles paralelos para aplicaciones de elementos finitos
• Vídeo: Uso de un octree en la estimación de estados