Un octárbol es una estructura de datos de árbol en la que cada nodo interno tiene exactamente ocho hijos . Octrees son los más utilizados para dividir un espacio tridimensional por recursivamente subdividir en ocho octantes. Los octrees son el análogo tridimensional de los quadtrees . El nombre se forma a partir de oct + tree , pero tenga en cuenta que normalmente se escribe " octree " con solo una "t". Los octrees se utilizan a menudo en gráficos 3D y motores de juegos 3D .
Para representación espacial
Cada nodo de un octárbol subdivide el espacio que representa en ocho octantes . En un octárbol de región de puntos (PR), el nodo almacena un punto tridimensional explícito , que es el "centro" de la subdivisión para ese nodo; el punto define una de las esquinas para cada uno de los ocho niños. En un octárbol 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 octárbol PR puede representar un espacio infinito; el nodo raíz de un octárbol MX debe representar un espacio limitado finito para que los centros implícitos estén bien definidos. Tenga en cuenta que los octárboles no son lo mismo que los árboles k -d : los árboles k -d se dividen a lo largo de una dimensión y los octárboles se dividen alrededor de un punto. Además, los árboles k -d son siempre binarios, lo que no es el caso de los octárboles. Al utilizar una búsqueda en profundidad, se deben atravesar los nodos y solo se deben ver las superficies requeridas.
Historia
El uso de octárboles para gráficos por computadora en 3D fue iniciado por Donald Meagher en el Instituto Politécnico de Rensselaer , descrito en un informe de 1980 "Codificación de octárboles: una nueva técnica para la representación, manipulación y visualización de objetos arbitrarios en 3-D por computadora", [1] por la que posee una patente de 1995 (con una fecha de prioridad de 1984 ) "Generación de imágenes de alta velocidad de objetos sólidos complejos usando codificación octree" [2]
Usos comunes
- Nivel de representación de detalle en gráficos por ordenador en 3D [3]
- Indexación espacial
- Búsqueda de vecino más cercano [4]
- Detección de colisiones eficiente en tres dimensiones
- Ver selección de frustum
- Método rápido multipolar
- Cuadrícula no estructurada
- Análisis de elementos finitos
- Octárbol de vóxeles dispersos [5]
- Estimación estatal [6]
- Establecer estimación [7]
Aplicación a la cuantificación del color
El algoritmo de cuantificación de color de octárbol , inventado por Gervautz y Purgathofer en 1988, codifica los datos de color de la imagen como un octárbol de hasta nueve niveles de profundidad. Los octrees se utilizan porquey 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 usa el siguiente bit de significancia, y así sucesivamente. A veces se ignoran los bits menos significativos para reducir el tamaño del árbol.
El algoritmo es muy eficiente en memoria porque el tamaño del árbol puede ser limitado. El nivel inferior del octárbol consta de nodos de hojas que acumulan datos de color no representados en el árbol; estos nodos contienen inicialmente bits únicos. Si se ingresa mucho más del número deseado de colores de paleta en el octárbol, 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, la exploración de todas las rutas en el árbol hasta los nodos de las hojas, tomando nota de los bits a lo largo del camino, producirá aproximadamente el número requerido de colores.
Implementación para descomposición puntual
El esquema de algoritmo recursivo de ejemplo a continuación ( sintaxis de MATLAB ) descompone una matriz de puntos tridimensionales en bins de estilo octárbol. La implementación comienza con un solo contenedor que rodea todos los puntos dados, que luego se subdivide recursivamente en sus 8 regiones de octárbol. La recursividad se detiene cuando se cumple una condición de salida determinada. 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 según la longitud de sus bordes
- Cuando la recursividad ha alcanzado un número máximo de subdivisiones
function [binDepths, binParents, binCorners, pointBins] = OcTree ( puntos ) binDepths = [ 0 ] % Inicialice una matriz de profundidades de contenedor con este contenedor de nivel base único binParents = [ 0 ] % Este contenedor de nivel básico no es un elemento secundario de otros contenedores binCorners = [ min ( puntos ) max ( puntos )] % 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 contenedor 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 volver ; % Salir de la función recursiva final % De lo contrario, divida este bin en 8 nuevos subbins con un nuevo punto de divisiónnewDiv = ( binCorners ( binNo , 1 : 3 ) + binCorners ( binNo , 4 : 6 )) / 2 para i = 1 : 8 newBinNo = longitud ( binDepths ) + 1 binDepths ( newBinNo ) = binDepths ( binNo ) + 1 binParents ( newBinNo ) = binNo binCorners ( newBinNo ) = [ uno de los 8 pares de la newDiv con minCorner o maxCorner ] oldBinMask = pointBins == binNo % Calcular qué puntos en pointBins == binNo ahora pertenecen a newBinNo pointBins ( newBinMask ) = newBinNo % Dividir de forma recursiva este contenedor recién creado dividir ( newBinNo )final
Ejemplo de cuantificación de color
Tomando la lista completa de colores de una imagen RGB de 24 bits como entrada de punto para la implementación de descomposición de puntos de octárbol descrita anteriormente, el siguiente ejemplo muestra los resultados de la cuantificación de color de octárbol. La primera imagen es la original (532818 colores distintos), mientras que la segunda es la imagen cuantificada (184 colores distintos) usando descomposición de octárbol, con cada píxel asignado el color en el centro del bin de octárbol en el que cae. Alternativamente, los colores finales podrían elegirse en el centroide de todos los colores en cada contenedor de octárbol, sin embargo, este cálculo adicional tiene muy poco efecto en el resultado visual. [8]
% Leer la imagen RGB originalImg = imread ( 'IMG_9980.CR2' ); % Extraer píxeles como tripletes de puntos RGBpts = remodelar ( Img , [], 3 ); % Crear objeto de descomposición OcTree usando una capacidad de contenedor de destinoOT = OcTree ( pts , 'BinCapacity' , ceil (( tamaño ( pts , 1 ) / 256 ) * 7 )); % Encuentra qué contenedores son "nodos hoja" en el objeto octárbolhojas = encontrar ( ~ ismember ( 1 : OT . BinCount , OT . BinParents ) & ... ismember ( 1 : OT . BinCount , OT . PointBins ));% Encuentre la ubicación RGB central de cada contenedor de hojasbinCents = mean ( remodelar ( OT . BinBo limits ( leafs , :) , [], 3 , 2 ), 3 ); % Crea una nueva imagen "indexada" con un mapa de coloresImgIdx = ceros ( tamaño ( Img , 1 ), tamaño ( Img , 2 )); para i = 1 : longitud ( hojas ) pxNos = encontrar ( OT . PointBins == hojas ( i )); ImgIdx ( pxNos ) = i ; finalImgMap = binCents / 255 ; % Convertir color de 8 bits a valores rgb de MATLAB % Muestra la imagen original de 532818 colores y la imagen resultante de 184 colores. figurasubtrama ( 1 , 2 , 1 ), imshow ( Img ) title ( sprintf ( 'Imagen en color% d original' , tamaño ( único ( pts , 'filas' ), 1 ))) subtrama ( 1 , 2 , 2 ), imshow ( ImgIdx , ImgMap ) title ( sprintf ( 'Imagen en color% d cuantificada en octárbol ' , tamaño ( ImgMap , 1 )))
Ver también
- Partición de espacio binario
- Jerarquía de intervalo delimitador
- Cube 2: Sauerbraten , un motor de juegos 3D en el que la geometría se basa casi en su totalidad en octrees
- id Tech 6 es un motor de juegos 3D que utiliza vóxeles almacenados en octrees
- Irrlicht Engine , admite nodos de escena de octárbol
- Problema de medida de Klee
- Octree lineal
- OGRE , tiene una implementación de administrador de escena octree
- Subpavimentado
- Voxel
- Quadtree
Referencias
- ^ Meagher, Donald (octubre de 1980). "Codificación de octárbol: una nueva técnica para la representación, manipulación y visualización de objetos arbitrarios 3-D por computadora". Instituto Politécnico Rensselaer (Informe técnico IPL-TR-80-111).
- ^ Meagher, Donald. "Generación de imágenes de alta velocidad de objetos sólidos complejos usando codificación octree" . USPO . Consultado el 20 de septiembre de 2012 .
- ^ David P. Luebke (2003). Nivel de detalle para gráficos 3D . Morgan Kaufmann. ISBN 978-1-55860-838-2.
- ^ Elseberg, Jan y col. " Comparación de estrategias e implementaciones de búsqueda de vecinos más cercanos para un registro de formas eficiente ". Revista de ingeniería de software para robótica 3.1 (2012): 2-12.
- ^ Akenine-Mo ̈ller, Tomas; Haines, Eric; Hoffman, Naty (6 de agosto de 2018). Renderizado en tiempo real, cuarta edición . Prensa CRC. ISBN 978-1-351-81615-1.
- ^ Henning Eberhardt, Vesa Klumpp, Uwe D. Hanebeck, Árboles de densidad para una estimación de estado no lineal eficiente , Actas de la XIII Conferencia Internacional sobre fusión de información, Edimburgo, Reino Unido, julio de 2010.
- ^ V. Drevelle, L. Jaulin y B. Zerr, Caracterización garantizada del espacio explorado de un robot móvil mediante el uso de subpavimentos , NOLCOS 2013.
- ^ Bloomberg, Dan S. "Cuantización de color usando octrees". , 4 de septiembre de 2008. Recuperado el 12 de diciembre de 2014.
enlaces externos
- Cuantificación de octárbol en Microsoft Systems Journal
- Cuantización de color usando octrees en Dr. Dobb's
- Cuantización de color usando octrees en el código fuente del Dr. Dobb [ enlace muerto permanente ]
- Descripción general de la cuantificación de color de octárbol
- Implementación paralela del algoritmo de generación de octtree, P. Sojan Lal, A Unnikrishnan, K Poulose Jacob, ICIP 1997, IEEE Digital Library
- Generación de octrees a partir de escaneo 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 ]
- Octreos paralelos para aplicaciones de elementos finitos
- Video: uso de un octárbol en la estimación de estados