Árbol k -d implícito

Construcción y almacenamiento de un árbol d implícito de k máximo en 2D mediante la función de división de mediana de la cuadrícula. Cada celda de la cuadrícula rectilínea tiene asignado un valor escalar, desde el más bajo (azul brillante) hasta el más alto (rojo brillante). El consumo de memoria de la cuadrícula se indica en la línea inferior. El consumo de memoria predefinido del árbol d implícito de k máximo requiere un valor escalar menor. El almacenamiento de los valores máximos de los nodos se indica en la línea superior.

Un árbol k -d implícito es un árbol k -d definido implícitamente sobre una cuadrícula rectilínea . Las posiciones y orientaciones de sus planos de división no se especifican explícitamente, sino implícitamente mediante una función de división recursiva definida sobre los hiperrectángulos que pertenecen a los nodos del árbol . El plano de división de cada nodo interno se sitúa sobre un plano de la cuadrícula subyacente, dividiendo la cuadrícula del nodo en dos subcuadrículas.

Nomenclatura y referencias

Los términos " árbol k -d min/max " y " árbol k -d implícito" a veces se confunden. Esto se debe a que la primera publicación que utilizó el término " árbol k -d implícito" ^{[ 1 ]} en realidad utilizó árboles k -d min/max explícitos, pero se refirió a ellos como " árboles k -d implícitos" para indicar que podían usarse para trazar rayos implícitamente sobre superficies iso dadas. Sin embargo, esta publicación también utilizó árboles k -d delgados, que son un subconjunto de los árboles k -d implícitos con la restricción de que solo pueden construirse sobre hiperrectángulos enteros con longitudes de lado que son potencias de dos. En la década de 2000, se introdujeron los árboles k -d implícitos tal como se definen aquí, con aplicaciones en gráficos por computadora. ^{[ 2 ]}^{[ 3 ]} Dado que es posible asignar atributos a los nodos de un árbol k -d implícito, se puede hacer referencia a un árbol k -d implícito que tiene valores min/max asignados a sus nodos como un " árbol k -d min/max implícito".

Construcción

Los árboles k -d implícitos generalmente no se construyen explícitamente. Al acceder a un nodo, la orientación y la posición de su plano de división se evalúan mediante la función de división específica que define el árbol. Diferentes funciones de división pueden generar árboles distintos para la misma cuadrícula subyacente.

Funciones de división

Las funciones de división pueden adaptarse a propósitos especiales. A continuación se detallan dos especificaciones de clases especiales de funciones de división.

Las funciones de división no degeneradas no permiten la creación de nodos degenerados (nodos cuyo volumen del hiperrectángulo entero correspondiente es igual a cero). Sus correspondientes árboles k- d implícitos son árboles binarios completos , que tienen para n nodos hoja n - 1 nodos internos. Sus correspondientes árboles k -d implícitos son árboles k -d implícitos no degenerados .
Las funciones de división completas son funciones de división no degeneradas cuyos nodos hoja del árbol k -d implícito correspondiente son celdas de cuadrícula individuales, de modo que tienen un nodo interno menos que la cantidad de celdas de cuadrícula dadas en la cuadrícula. Los árboles k -d implícitos correspondientes son árboles k -d implícitos completos .

Una función de división completa es, por ejemplo, la función de división de mediana de cuadrícula . Crea árboles k -d implícitos bastante equilibrados mediante el uso de hiperrectángulos enteros k -dimensionales hyprec[2][k] que pertenecen a cada nodo del árbol k -d implícito. Los hiperrectángulos definen qué celdas de la cuadrícula rectilínea pertenecen a su nodo correspondiente. Si el volumen de este hiperrectángulo es igual a uno, el nodo correspondiente es una sola celda de la cuadrícula y, por lo tanto, no se subdivide más y se marca como nodo hoja. De lo contrario, la extensión más larga del hiperrectángulo se elige como orientación o . El plano de división correspondiente p se posiciona en el plano de la cuadrícula que está más cerca de la mediana de la cuadrícula del hiperrectángulo a lo largo de esa orientación.

Orientación del plano dividido o :

o = min{argmax(i = 1 ... k : (hyprec[1][i] - hyprec[0][i]))}

Posición del plano dividido p :

p = redondearHaciaAbajo((hiprec[0][o] + hiprec[1][o]) / 2)

Asignación de atributos a nodos de árbol k -d implícitos

Una ventaja de los árboles k -d implícitos es que no es necesario almacenar explícitamente las orientaciones y posiciones de su plano de división.

Sin embargo, algunas aplicaciones requieren, además de las orientaciones y posiciones del plano dividido, atributos adicionales en los nodos internos del árbol. Estos atributos pueden ser, por ejemplo, bits individuales o valores escalares individuales que definen si las subcuadrículas pertenecientes a los nodos son de interés o no. Para árboles k -d implícitos completos, es posible preasignar una matriz de atributos del tamaño adecuado y asignar a cada nodo interno del árbol un elemento único en dicha matriz.

La cantidad de celdas en la cuadrícula es igual al volumen del hiperrectángulo entero que pertenece a ella. Dado que un árbol k -d implícito completo tiene un nodo interno menos que celdas, se conoce de antemano cuántos atributos deben almacenarse. La relación " Volumen del hiperrectángulo entero a nodos internos " define, junto con la función de división completa, una fórmula recursiva que asigna a cada plano de división un elemento único en el arreglo asignado. El algoritmo correspondiente se presenta a continuación en pseudocódigo C.

// Asignación de atributos a los nodos internos de un árbol kd implícito completo// crea un hiperrectángulo de ayuda entero hyprec (su volumen vol(hyprec) es igual a la cantidad de hojas) int hyprec [ 2 ][ k ] = { { 0 , ..., 0 }, { length_1 , ..., length_k } }; // asigna una vez el array de atributos para todo el árbol kd implícito attr * a = new attr [ volume ( hyprec ) - 1 ];attr implicitKdTreeAttributes ( int hyprec [ 2 ][ k ], attr * a ) { if ( vol ( hyprec ) > 1 ) // el nodo actual es un nodo interno { // evaluar la orientación o del plano dividido y su posición p usando la función de división completa subyacente int o , p ; completeSplittingFunction ( hyprec , & o , & p ); // evaluar los hiperrectángulos enteros de los hijos hyprec_l y hyprec_r int hyprec_l [ 2 ][ k ], hyprec_r [ 2 ][ k ]; hyprec_l = hyprec ; hyprec_l [ 1 ][ o ] = p ; hyprec_r = hyprec ; hyprec_r [ 0 ][ o ] = p ; // evaluar la ubicación de memoria de los hijos a_l y a_r attr * a_l = a + 1 ; attr * a_r = a + vol ( hyprec_l ); // evaluar recursivamente los atributos hijos c_l y c_r attr c_l = implicitKdTreeAttributes ( hyprec_l , a_l ); attr c_r = implicitKdTreeAttributes ( hyprec_r , a_r ); // fusionar los atributos hijos con el atributo actual c attr c = merge ( c_l , c_r ); // almacenar el atributo actual y devolverlo a [ 0 ] = c ; return c ; } // El nodo actual es un nodo hoja. Devolver el atributo perteneciente a la celda de cuadrícula correspondiente return attribute ( hyprec ); }

Cabe mencionar que este algoritmo funciona para todas las cuadrículas rectilíneas. El hiperrectángulo entero correspondiente no tiene por qué tener lados que sean potencias de dos.

Aplicaciones

Los árboles implícitos max- k -d se utilizan para la proyección de rayos sobre isosuperficies /MIP ( proyección de máxima intensidad ). El atributo asignado a cada nodo interno es el valor escalar máximo dado en la subcuadrícula perteneciente al nodo. Los nodos no se recorren si sus valores escalares son menores que el isovalor buscado/la intensidad máxima actual a lo largo del rayo. Los bajos requisitos de almacenamiento del árbol implícito max- k -d y la favorable complejidad de visualización de la proyección de rayos permiten proyectar (e incluso cambiar la isosuperficie para) campos escalares muy grandes a velocidades de fotogramas interactivas en PCs convencionales. De manera similar, se puede utilizar un árbol implícito min/max-k-d para evaluar eficientemente consultas como la línea de visión del terreno . ^{[ 4 ]}

Complejidad

Dado un árbol k -d implícito extendido sobre una cuadrícula k -dimensional con n celdas de cuadrícula.

Asignar atributos a los nodos del árbol requiere $\mathrm {O} (kn)$ tiempo.
Almacenar atributos en los nodos lleva $\mathrm {O} (n)$ memoria.
El trazado de rayos de isosuperficies/MIP de un campo escalar subyacente utilizando el árbol implícito max k -d correspondiente toma aproximadamente $\mathrm {O} (\log(n))$ tiempo.

Véase también

Referencias

↑ Ingo Wald, Heiko Friedrich, Gerd Marmitt, Philipp Slusallek y Hans-Peter Seidel "Trazado de rayos de isosuperficies más rápido mediante árboles KD implícitos" IEEE Transactions on Visualization and Computer Graphics (2005)
↑ Matthias Groß, Carsten Lojewski, Martin Bertram y Hans Hagen " Árboles k -d implícitos rápidos: trazado de rayos de isosuperficie acelerado y proyección de máxima intensidad para campos escalares grandes" CGIM07: Actas de Computer Graphics and Imaging (2007) 67-74
↑ Matthias Groß (PhD, 2009) Hacia aplicaciones científicas para el trazado interactivo de rayos
↑ Bernardt Duvenhage "Uso de un árbol KD implícito Min/Max para realizar cálculos eficientes de línea de visión del terreno" en "Actas de la 6ª Conferencia Internacional sobre Gráficos por Computadora, Realidad Virtual, Visualización e Interacción en África", 2009.

[1] Ingo Wald, Heiko Friedrich, Gerd Marmitt, Philipp Slusallek y Hans-Peter Seidel "Trazado de rayos de isosuperficies más rápido mediante árboles KD implícitos" IEEE Transactions on Visualization and Computer Graphics (2005)

[2] Matthias Groß, Carsten Lojewski, Martin Bertram y Hans Hagen " Árboles k -d implícitos rápidos: trazado de rayos de isosuperficie acelerado y proyección de máxima intensidad para campos escalares grandes" CGIM07: Actas de Computer Graphics and Imaging (2007) 67-74

[3] Matthias Groß (PhD, 2009) Hacia aplicaciones científicas para el trazado interactivo de rayos

[4] Bernardt Duvenhage "Uso de un árbol KD implícito Min/Max para realizar cálculos eficientes de línea de visión del terreno" en "Actas de la 6ª Conferencia Internacional sobre Gráficos por Computadora, Realidad Virtual, Visualización e Interacción en África", 2009.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]