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 divididos no se dan explícitamente, sino implícitamente, mediante alguna función de división recursiva definida en los hiperrectángulos que pertenecen a los nodos del árbol . El plano de división de cada nodo interno se coloca en un plano de cuadrícula de la cuadrícula subyacente, dividiendo la cuadrícula del nodo en dos subcuadrículas.
Nomenclatura y referencias
Los términos " árbol k -d mínimo / máximo " y " árbol k -d implícito " a veces se confunden. Esto se debe a que la primera publicación que usó el término " árbol k -d implícito " [1] en realidad usó árboles k -d mínimo / máximo explícitos , pero se refirió a ellos como " árboles k -d implícitos " para indicar que pueden usarse para traza de rayos implícitamente dadas superficies iso. Sin embargo, esta publicación también usó árboles k -d delgados que son un subconjunto de los árboles k -d implícitos con la restricción de que solo se pueden construir sobre hiperrectángulos enteros con longitudes laterales que son potencias de dos. Los árboles k -d implícitos como se definen aquí se han introducido recientemente, con aplicaciones en gráficos por computadora. [2] [3] Como es posible asignar atributos a implícita k nodos del árbol -d, uno puede referirse a un implícito k árbol -d que tiene valores mín / máx asignados a sus nodos como un "implícita min / max k - d árbol ".
Construcción
Los árboles k -d implícitos generalmente no se construyen explícitamente. Al acceder a un nodo, su orientación y posición del plano de división se evalúan utilizando la función de división específica que define el árbol. Diferentes funciones de división pueden resultar en diferentes árboles para la misma cuadrícula subyacente.
Funciones de división
Las funciones de división pueden adaptarse a propósitos especiales. Debajo de dos especificaciones de clases especiales de función de división.
- Las funciones de división no degeneradas no permiten la creación de nodos degenerados (nodos cuyo volumen de 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. Su implícita correspondiente k -d árboles son no degenerados implícita k árboles -d .
- Las funciones de división completas son funciones de división no degeneradas cuyos correspondientes nodos hoja implícitos del árbol k -d 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 la mediana de la cuadrícula . Crea árboles k -d implícitos bastante equilibrados mediante el uso de hiperrectángulos enteros k -dimensionales hyprec [2] [k] pertenecientes 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 celda de cuadrícula única y, por lo tanto, no se subdivide ni 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 p correspondiente se coloca 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 de división p :
p = roundDown ((hyprec [0] [o] + hyprec [1] [o]) / 2)
Asignar atributos a nodos de árbol k -d implícitos
Una ventaja de los árboles k -d implícitos es que las orientaciones y posiciones de su plano dividido no necesitan almacenarse explícitamente.
Pero algunas aplicaciones requieren además de las orientaciones y posiciones del plano dividido, más atributos en los nodos internos del árbol. Estos atributos pueden ser, por ejemplo, bits únicos o valores escalares únicos, definiendo si las subcuadrículas que pertenecen 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 correcto y asignar cada nodo interno del árbol a un elemento único en esa matriz asignada.
La cantidad de celdas de la cuadrícula en la cuadrícula es igual al volumen del hiperrectángulo entero que pertenece a la cuadrícula. Como un árbol k -d implícito completo tiene un nodo interno menos que las celdas de la cuadrícula, se sabe de antemano cuántos atributos deben almacenarse. La relación " Volumen del hiperrectángulo entero con los 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 la matriz asignada. El algoritmo correspondiente se da en C-pseudocódigo debajo.
// Asignar atributos a los nodos internos de un árbol kd implícito completo// crea un integer help hyperrectangle 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 la matriz 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 { // evalúa la orientación del plano dividido o y su posición p usando el función dividida completa subyacente int o , p ; completeSplittingFunction ( hyprec , & o , & p ); // evalúa los hiperrectángulos enteros de los niños 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 ; // evalúa la ubicación de la memoria de los niños a_l y a_r attr * a_l = a + 1 ; attr * a_r = a + vol ( hyprec_l ); // evaluar de forma recursiva los atributos de los niños y c_l c_r attr c_l = implicitKdTreeAttributes ( hyprec_l , a_l ); atributo c_r = implícitoKdTreeAttributes ( hyprec_r , a_r ); // fusiona los atributos de los niños con el atributo actual c attr c = merge ( c_l , c_r ); // almacena el atributo actual y lo devuelve a [ 0 ] = c ; return c ; } // El nodo actual es un nodo hoja. Devuelve el atributo que pertenece al atributo de retorno de celda de cuadrícula correspondiente ( hyprec ); }
Vale la pena mencionar que este algoritmo funciona para todas las cuadrículas rectilíneas. El hiperrectángulo entero correspondiente no necesariamente tiene que tener longitudes laterales que sean potencias de dos.
Aplicaciones
Implícito max- k árboles -d se utilizan para la fundición de rayos isosuperficies / MIP ( proyección de intensidad máxima ). El atributo asignado a cada nodo interno es el valor escalar máximo dado en la subcuadrícula que pertenece al nodo. Los nodos no se atraviesan si sus valores escalares son más pequeños que el isovalor / intensidad máxima actual buscada a lo largo del rayo. Los bajos requisitos de almacenamiento del árbol d max k implícito y la complejidad de visualización favorable de la proyección de rayos permiten emitir rayos (e incluso cambiar la isosuperficie para) campos escalares muy grandes a velocidades de fotogramas interactivas en PC comerciales. De manera similar, se puede usar un árbol kd mínimo / máximo implícito para evaluar de manera eficiente consultas como la línea de visión del terreno . [4]
Complejidad
Dado un árbol k -d implícito que se extiende sobre una cuadrícula k -dimensional con n celdas de cuadrícula.
- Asignar atributos a los nodos del árbol requiere hora.
- Almacenar atributos en los nodos requiere memoria.
- Ray casting iso-superficies / MIP un campo escalar subyacente utilizando el árbol máximo k -d implícito correspondiente toma aproximadamente hora.
Ver también
Referencias
- ^ Ingo Wald, Heiko Friedrich, Gerd Marmitt, Philipp Slusallek y Hans-Peter Seidel "Trazado de rayos isosuperficiales más rápido usando árboles KD implícitos" Transacciones IEEE sobre visualización y gráficos por computadora (2005)
- ^ Matthias Groß, Carsten Lojewski, Martin Bertram y Hans Hagen "Árboles k -dimplícitos rápidos: trazado de rayos isosuperficiales acelerado y proyección de máxima intensidad para campos escalares grandes" CGIM07: Actas de imágenes y gráficos por computadora (2007) 67-74
- ^ Matthias Groß (PhD, 2009) Hacia aplicaciones científicas para la fundición de rayos interactiva
- ^ Bernardt Duvenhage "Uso de un árbol KD mínimo / máximo implícito para realizar cálculos de línea de vista de terreno eficiente" en "Actas de la 6ª Conferencia Internacional sobre gráficos por computadora, realidad virtual, visualización e interacción en África", 2009.