Arboles octales

7/25/2019 Arboles octales

1/15

rboles Octales

Resumen:

Con la creciente predominancia de los grficos computarizados as como el aumento de la calidad visualde los mismos, ha incrementado la demanda de procesamiento y el requerimiento en hardware para ellos,debido a esto la tecnologa visual se ha visto impulsada ha desarrollar nuevas tcnicas para acelerar ymeorar la calidad de los grficos mediante algoritmos y estructuras de datos baando el costo de

procesamiento de los mismos!

"n propuesta para al desarrollo de estas tecnologas emergentes son las estructuras de datos espaciales,dentro de las cuales se encuentran los #ctrees $%rboles #ctales& las cuales proponen una nueva forma deordenar el espacio as como una forma interesante al problema de la resoluci'n de colores y su

consiguiente procesamiento!

(os #ctrees son una estructura de datos de tipo rbol, la cual su principal caracterstica es que cada nodoapunta a ocho nodos hios, donde cada una de las ramas no necesariamente se encuentran balanceadasuna respecto a la otra, es decir la altura de una rama puede diferir en uno o ms niveles de la otra!Considerando que e)isten diversas aplicaciones para los #ctrees sus caractersticas generales variaran

para cada uno de estos!

*l ocultamiento de obetos + dentro de una determinada vista $-rustrum& es una de las diversasaplicaciones para los #ctrees, a este mtodo se le llama -rustrum Culling, el cual consiste en abarcar elespacio en un cubo y subdividirlo en ocho regiones proporcionales, en algunos casos, de manera que loscubos que se encuentran dentro de nuestra vista son aquellos que contienen a los obetos que serngraficados, de tal manera que estos cubos sern subdivididos de nuevo en ocho nuevas regiones hasta que

se alcance cierto limite determinado!

ebido a la funcionalidad de los #ctrees para guardar obetos + en regiones adyacentes se le puede usarpara la detecci'n de colisiones entre obetos en un espacio arbitrario con lmites definidos, realizando lasconsultas de una forma ms eficiente al consultar solo por los obetos colindantes!

#tra aplicaci'n de estos rboles es la Cuantizacion de colores donde se transforma una imagen de muchoscolores $ +. bits, ./bits& a una imagen de menos colores $0 bits&, usando a los arboles octrees por sufacilidad para guardar datos de tres dimensiones $en este caso colores Roo, 1erde, 2zul&

*l creciente avance tecnol'gico implica que las soluciones que sirven para resolver ciertos problemas hoynecesitan ser replanteadas para resolver los problemas que emergen con las nuevas tecnologas,

resaltando que soluciones tan verstiles como esta se transforman y remodelan para resolver losproblemas del ma3ana!

4 5 4


2/15

2bstract:

6ith the growing predominance of the computerized graphics as the visual quality, has increased too thedemand for processing and the hardware requirements for it, due this, the visual technology its seems to

be stimulated to development new techniques, in order to accelerate and improve the quality of graphicsbetween algorithms and data structures lowering the processing cost of itself!

2 proposal for the development these emergent technologies are the spatial data structures, within it is the#ctrees $#ctal trees& that propose a new form of straighten up the space as an interesting way to solve the

problem of the color resolution and its subsequent process!

7he #ctrees is a tree data structure, which its main characteristic is that every node points to eightchildren nodes, where each branch or bush will not necessarily be balanced respect the other ones, thismeans that the height of one branch could defer in one or more levels form the other! Considering of thee)istence of many applications for the #ctrees their general characteristic will vary for each one of these!

7he + obects concealment between a determined view $-rustrum& is one of the diverse applications for

the #ctrees, this method is called -rustrum Culling, which consist to embrace all the space in a certaincube and subdivide it in eight proportional regions, in some cases, therefore the cubes that reside in ourview are the ones who contain the obects that will be drawn, in that case this cubes will be subdivided ineight new regions until it reach a determined limit!

ue the functionality of the #ctrees to store + obects in adacent regions it can be used for collisiondetection between obects in an arbitrary space with defined boundaries, performing the queries in a moreefficient way consulting only in the contiguous obects!

2nother application of these trees is the Color 8uantization where it transform a picture of many colors$+. bits, ./ bits& to an image of less colors $0 bits&, using #ctrees due its facility to store tridimensionaldata$in these case red, green and blue colors&!

7he increasing technological advance implies that the solutions that serve to solve certain actual problemsneed to be restated in order to solve the emerging problems that surge with the new technologies,concluding that the versatile solutions li9e these transforms an remodel itself in order to solve tomorrow

problems!

4 4


3/15

7abla de Contenidos

!4 ;ntroducci'n

+!4 2plicaci'n de los #ctrees


4/15

1.-Introduccin

"n #ctree es una estructura de datos errquica usualmente usada para la representaci'n de imgenes!en+! *l #ctree codifica imgenes en tres dimensiones colocando subsecciones del grafico en unaestructura tipo rbol parecida a un rbol binario! 2unque a diferencia de un rbol binario donde cada nodotiene dos hios, en un #ctree cada nodo tiene hasta ocho hios! Cada nodo almacena una parte particulardel grafico!

(os #ctrees operan mediante la descomposici'n recursiva del espacio! =ientras que e)isten una serie de#ctrees especializados, el tipo mas comun es el conocido como los A#ctrees CubicosB! *n tales arboles elgrafico que ha de ser codificado y almacenado es dividido en ocho cubos! Cada cubo ser asrepresentado en un nodo del rbol! (a raiz del #ctree representa toda la imagen + almacenada mientrasque cada una de sus ocho hios representaran un octavo de la imagen! *ste proceso continuaraH cadacuadrante representado por los hios de la raz sera subdividido a su vez en ocho subcubos representandoa los ocho nietos de la raiz! *ste proceso continuara hasta que la regi'n que esta siendo almacenada sea

tan simple que pueda ser almacenada totalmente en un nodo! 2lgunas veces esto significa quecontinuaremos subdividiendo la imagen hasta que cada vo)el individual sea almacenado en algIn nodohoa! #tras veces una region mas grande que un vo)el es suficientemente homogenea que puede serrepresentada en un nodo hoa sin necesidad de mayor descomposici'n!"na propiedad interesante de los #ctrees es que soportan un tipo de compresi'n de datos! 2l Jotransgredir cierto nivel de la estructura de datos, es posible filtrar los detalles optando por una imagenligeramente menos precisa pero mucho mas peque3a!

2.-Marco Terico

"na propuesta para al desarrollo de las tecnologas de grficos es el uso de las estructuras de datosespaciales, dentro de las cuales se encuentran los #ctrees $%rboles #ctales& las cuales proponen unanueva forma de ordenar el espacio contenindolo en cubos que se dividen recursivamente hasta llegar acierto limite!

2.1.-Definiciones Previas

2.1.1.-El Voxel

?e llama 1#K*( o elemento de volumen a la representaci'n mnima de un obeto en +!, *l mas comInes el cubo, entre mas peque3o se meora la representaci'n!

?in embargo, cada elemento 1o)el puede ser descrito en trminos de sus equinas almacenando solamentelas coordenadas de cada esquina de cada cubo, codificndolas en un arreglo o matriz + de datosbinarios! *l arreglo nos representa la e)istencia del cubo, dentro del modelo, de tal manera que, elelemento a tratar ser si se encuentra dentro del modelo, sino seria cero, es decir, no pertenece!

*ntonces escribir un s'lido significara listar todos los cubos que pertenecen al modelo o forman parte deel, pero en el modelado de s'lidos, no se tiene una imagen u obeto inicial, o es muy difcil describir unobeto generalizado a cubitos!

2.2.-La Subdivisin del Esacio

4 + 4


5/15

2l tratar de describir un obeto mediante todos los 1o)el que le pertenecen cuando cada Cubo, puede serdescrito por sus esquinas, se genera grandes lneas de datos, la enumeraci'n completa de los modeloshecha por la descomposici'n tiene muchas ventaas, tales como su simplicidad su generalidad y permitenun gran numero de algoritmos, sin embargo, el consumo de memoria es alto se puede cambiar la divisi'nregular del espacio por algo mas eficiente, una divisi'n adaptativa!

*ste esquema de trabao basado en la subdivisi'n del espacio, se logra por la simple observaci'n de lasreillas descriptivas de la enumeraci'n completa de un espacio +, donde muchas veces un cubo blanco$& tiene como vecinos otros cubos del mismo tipo AB! 2l observar la combinaci'n y codificarla enmodelos de datos comparativamente similares podemos reducir la cantidad por dicha reilla!

(a divisi'n adaptativa tiene una propiedad fundamental en la que el numero de nodos necesarios para larepresentaci'n de un s'lido es proporcional a la rea de su superficie! e aqu que el nImero deelementos es proporcional r.de la resoluci'n r que se utilice, en el otro caso, el tama3o de elementos deun esquema completo es proporcional a r+ !

2.!.-Definicin de "rboles #ctales u $#%T&EES'(os #ctrees son una estructura de datos de tipo rbol, la cual su principal caracterstica es que cada nodoapunta a ocho nodos hios, donde cada una de las ramas no necesariamente se encuentran balanceadasuna respecto a la otra, es decir la altura de una rama puede diferir en uno o ms niveles de la otra!Considerando que e)isten diversas aplicaciones para los #ctrees sus caractersticas generales variaran

para cada uno de estos!

*stos son %rboles son una variaci'n errquica de la enumeraci'n espacial, como resultado de underivado de los quatrees! (os octrees utilizan la divisi'n recursiva del espacio en 0 octantes, por ello elnombre de octree, que son colocados es una estructura l'gica de rbol #ctario $de 0 hoas&!

"sualmente, el arbol es colocado alrededor del origen del sistema de coordenadas con un primer nivel deoctantes que corresponden a los octantes del espacio general, a manera de cuadrantes del sistema decoordenadas!(a idea fundamental es un algoritmo Aivide y 1encersB! "n octree es subdividido en octantes demanera recursiva!

Cada nodo del rbol consiste en un c'digo y ocho apuntadores hacia ocho AhiosB, enumerados del 5 al EH*l c'digo indica si el cubo es negro o blanco , es decir, sus valores son 5 y respectivamente, lo quesignifica , si el c'digo es negro, el espacio representado por el nodo esta lleno, es decir, todo el cubo

pertenece al modelo, el nodo tambin es una AhoaBH la tercera posibilidad es que el nodo sea gris, estoindica parcialmente ocupado o escasamente vaci'H en este ultimo caso, los ocho apuntadores hioscorresponden a la divisi'n regular del padre!

2.(.-Proceso de construccin de un octree

(os modelos hechos en base a un rbol octree de s'lidos con primitivas, tienen un procedimiento declasificaci'n entre la instancia de la primitiva y el nodo selecciona del octree! *ste proceso declasificaci'n debe ser capaz de distinguir entre los casos:

4 *l nodo esta en el e)terior de la primitiva!4 *l nodo esta en el interior de la primitiva!4 *l nodo pertenece parcialmente a la primitiva!

*ste proceso de clasificaci'n es en forma recursivaH al inicio, el primer nodo $raz& es blanco o vaci',estos son los datos iniciales del algoritmo! ?iguiendo el algoritmo, va clasificando cada nodo contra la

primitiva, si el primer o segundo caso aplica, el nodo es marcado como blanco o negro, y la recursionterminaH en caso contrario, el algoritmo procede a marcar el nodo como gris, subdividiendo en ocho

4 / 4


6/15

octantes y llamando recursivamente cada uno de ellos, la subdivisi'n continuara hasta que la resoluci'ndeseada es alcanzada, generalmente se usan de seis a doce niveles!

*l algoritmo de construcci'n de un octree es el siguiente:

=a9eLtree $p, t, depth&

>rimitive MpH NM la primitive a modelar#ctree MtH NM nodo inicial del octree, blanco;nt depthH NMma)ima recursionO

int iHswitch$classify$p, t&&O

case 6P;7*HO

t4Qcode 6P;7*Hbrea9H

Scase G(2CTH

O brea9Hcase R*UH

Sif$depth 5&

t4QcodeR*UHelseO

subdivide$t&Hfor$i5 HiV0 HiWW&ma9eLtree$p, t4QoctXiY, depth 4& H

Sbrea9H

SS

NM clasificar nodo octree contra primitiveclassify $


7/15

! (os nodos n y n. son ambos hoas! *n este caso, el nodo resultante del octree es negro si amboslo son, de otra manera es blanco

.! "no de los nodos es hoa! ?i el nodo hoa es negro, el sub4arbol de la que no es hoa es copiadoal resultado del octree, de otra manera el nodo resultante es blanco!

+! 2mbos no son hoas, entonces el algoritmo debe considerar recursivamente los hios de esos

nodos!

Como los argumentos ya estn presentes su construcci'n no es tomada en cuentaH en la mayora de loscasos la compleidad del algoritmo es proporcional al rbol mas peque3o!

Jo todos los algoritmos pueden ser llevados a una manera transversal, en algunos casos es necesarioconocer a los nodos vecinos, como en los casos de efecto visuales como trasparencas, el acceder a unnodo vecino puede ser complicado y requiere subir un nivel en el rbol o hasta la raz en el peor de loscasos! >ara lo cual se pueden incluir ms apuntadores a ciertas reas del rbol, y requiere un cuidado de

balance en el rbol!

2..- Proiedades de los octrees

=odelo poderoso, los octrees son modelos de representaci'n apro)imada, y pueden ser e)actospara ciertos obetos!

1alidez, no requiere de una conectividad especial, todos los octrees son representaciones validasde algIn s'lido!

Jo ambig[edad y "nicidad, hasta los limites de resoluci'n, todos los octrees no ambiguos,definen un s'lido!

Consistencia, en general el numero de nodos que un octree representa es proporcional al rea delobeto! *n promedio un octree fcilmente puede medir ms de un mill'n de bytes de memoria!

#peraciones cerradas, un octree soporta de algoritmos cerrados para los problemas detranslaci'n, rotaci'n, y operaciones booleanas!

?encillos computacional mente, muchos algoritmos de los octrees toman la forma de transversal,donde las operaciones son relativamente fciles para cada nodo del rbol!

2..-Subdivisin binaria del esacio

"na alternativa, al procesamiento de los octree, es la subdivisi'n de un espacio binario! *sto implica, unenfoque que divide los nodos grises en dos hoas en vez de ocho octantes! (o que los hace mucho ms

peque3o, de esto surge la versi'n lineal de los octrees!2unque el *spacio sea dividido en dos o en ocho como un octree normal, la cantidad de memoriautilizada sigue siendo demasiada, pero menor al utilizada por la enumeraci'n espacial!

(o anterior ha provocado investigaciones para comprimir la representaci'n de rboles, muchasalternativas de representaci'n reemplazan la estructura del rbol por un apuntador libre, una estructura dedatos lineal!

*sta nueva propuesta se le llama octrees lineales!

(as representaciones lineales son suficientes para muchos algoritmos! (as operaciones booleanas enoctrees lineales se hacen al mezclar las dos cadenas de caracteres, lo cual es una operaci'n fcil derealizar!

!.-/licacin de los #ctrees

2unque comInmente los octrees son utilizados para la representaci'n grafica de obetos + no todas susaplicaciones se veran relacionadas con esto, debido la versatilidad de esta estructura de datos las ideas quesurgen en donde aplicar esta estructura particular es bastante amplia, a medida que uno se inmersa en el

concepto de octrees nos daremos cuenta de la funcionalidad de la estructura para la detecci'n de obetos+ y todas las posibles operaciones relacionadas con ella, todo este conunto de tcnicas y estructuras

4 D 4


8/15

aplicada se les llama -rustrum Culling, la cual apunta a la optimizacion y aceleracion del rendering$impresi'n de datos por pantalla en un determinado tiempo&, otra aplicaci'n comun para este tipo deestructura espacial es la cuantizacion de colores la cual toma el concepto de octrees para meorar unaimagen predefinida!

!.1.-T0cnicas de Particionaiento de #ctrees

(os algoritmos de partici'n del espacio mediante octrees son usados para la representaci'n de obetos enambientes +, los cuales son las basicas para la mayoria de sistemas modelado y rendereo de imgenes!*l obetivo primario de dichos algoritmos es reducir el numero de comparaciones requeridas paradeterminar que superficies necesitan ser procesadas para el trazo de rayos, colision de detecciones,determinaci'n de visibilidad, o calculos similares! 2unque usado principalmente en un ambiente esttico,se podr utilizar en ambientes dinmicos con algunas modificaciones! (os #ctrees pueden proveer unasignificante reducci'n en el tiempo necesitado para la clasificaci'n de polgonos en una escena para sue)posici'n apropiada lo que lo hace ideales para aplicaciones como los uegos que consisten

primordialmente en espacios vacos donde los obetos que se encuentran en este muestran largasvariaciones en su tama3o relativo

!.1.1.-rustru %ullin3

Como mencionamos anteriormente un octree es una forma de subdividir el espacio pero cabe resaltar quela tcnica que subdivide el espacio en si se llama frustrum culling, o tambien llamada particionamientodel espacio, la cual permite dibuar o graficar la parte del mundo, nivel o escena que se encuentra ennuestro -rustrum $vista de la camara&! "n eemplo del porque el particionamento del espacio es necesario

se dar si es que creramos un mundo con alrededor de 555,555 polgonos a dibuar! ?i se hiciera unbucle que pasara por cada uno de los polgonos, y se comunique con el tope de nuestros polgonos depersonaes por cuadro, nuestra tasa de muestreo decaera crticamente! 2unque una buena taretaaceleradora de video solucionara el problema, esto restringira a cualquiera que no posea un hardware deaceleraci'n de video de ultima generaci'n! 2 veces, aunque la posesi'n de un buen hardware deaceleraci'n no solucionara el problema, ya que la mayoria de veces la parte de desacelera la resoluci'n esla cantidad de datos que se transmiten a travs del bucle principal! *ntonces no seria optimo que solo segraficaran los polgonos que estn en nuestra vista, bueno esta es la principal optimizacion de los octrees

para este tipo de aplicaciones, ya que brinda una forma rapida de encontrar los polgonos que estan en lavista y solo dibuar esos!

4 E 4


9/15

+!!!!4-uncionamiento

"n octree trabaa en cubos! ;nicialmente! *l octree comienza con un nodo raiz que posee un ee asociadoal cubo que rodea al mundo, nivel o escena! *ntonces se creara un cubo imaginario alrededor de todo elespacio!

2si el nodo raz contendr a todos los vrtices de nuestro mundo! >ero si solo poseyramos el nodo razhara que diburamos todo el mundo, debido a que nuestro obetivo es solo dibuar los obetos que seencuentran en nuestro frustrum spectrum $espectro visual& subdividiremos al nodo raiz en ocho partes $dedonde proviene la denominaci'n #ctree&! *so significa que e)istirn / cubos superiores e inferiores,teniendo en cuenta que cada lnea que conforma al nodo realmente no e)iste, sino que sern una ayuda

para visualizar la esquematizaci'n del octree!

Pemos dividido el mundo en ocho partes en una sola subdivisi'n! *n este punto nos daremos cuenta cuanefectivo seria si tuviramos ., + o / subdivisiones, pero de donde obtendremos la velocidad en quemencionamos anteriormente, supongamos que nuestra camara se encuentra en la mitad de nuestro mundoapuntando a una esquina! ?i vemos las lineas no podremos dar cuenta que solo estamos viendo / de losocho cubos del octree! *stos nodos incluyen dos de los cubos superiores y dos de los inferiores, lo que

significara que solo dibuaremos los nodos almacenados en esos vrtices!

4 0 4


10/15

>ero, como verificamos que nodos estan en nuestra vista\ *sto sera muy simple aplicando -rustrumCulling! >odremos obtener las dimensiones del frustrum y verificar cada cubo que intersecata o que seencuentra en el frustrum de la vista, de tal manera, si un cubo interfecta el frustrum entonces dibuaremosese nodo! Gsicamente, en el eemplo anterior demostramos que hemos reducido la cantidad quenecesitamos dibuar en un @5]! Recordemos que esta solo fue una sola subdivisi'n de nuestro mundo!=ientras mas subdivisiones se realicen mas eficiencia obtendremos de estas, esta claro que no

necesitamos un e)ceso de nodos ya que esto causara una baa de velocidad por toda es recursi'n!

?ubdiviremos un nivel mas, pero esta vez este nivel no producira 0 cubos dentro de los ocho cubosoriginales! (os cubos de la parte superior e inferior de las ocho regiones originales no fueronsubdivididos! *sto nos da una nueva premisa a tener en cuenta en cuanto a los octrees, cada vez quesubdividimos creamos ocho nuevos nodos pero si no e)isten poligonos almacenados en tal area,descartaremos ese nodo, no asignandole memoria a este! =ientras mas subdividamos, mayor ser lacantidad de nodos que le darn forma a nuestro mundo

!.2.-4uanti5acion de %olores

#tro de los usos que se le puede dar a un #ctree es en la cuantizacion de colores!(a cuantizacion de colores se usa cuando se quiere crear una imagen de n colores a partir de otra imagende m colores siendo n menor que m! *l problema es como elegir los n colores que reemplazaran a losotros m colores! *n general esto se hace creando una paleta de colores $ en el caso de querer transformarla imagen a 0 bits, la paleta tendria .@D colores& !

(os colores de la paleta se eligen segIn diferentes criterios! "na forma de elegirlos seria usando losprimeros n colores diferentes de la imagen! 2unque rapida, esta forma creara una imagen ine)acta de laoriginal, con los colores distorsionados!

#tra forma de crear la paleta seria usando los n colores que mas se usan en la paleta, aunque correctapara imgenes con homogeneidad de colores, el problema viene cuando la imagen original contiene unavariedad enorme de colores con lo cual se perdera la calidad en la foto!

4 F 4


11/15

>ara cuantizar los colores se sigue dos pasos& Crear la paleta de colores.& "sar esa paleta para crear la nueva imagen

(a tecnica ahora e)plicada usa a los #ctrees para quantizar lo colores de una forma inteligente!

!.2.1.-#ctrees ara la otii5acion de colores

?upongamos que queremos transformar una imagen de ./ bpp o +. bpp $los ultimos ocho bits detransparencia& a una imagen de 0 bits !*l arbol #ctree tendra una altura de 0 nodos y se procede de lasiguiente manera:

+!.!!!4;nserci'n en el #ctree

&?e toma el primer color de la imagen y se separan los bits en sus tres colores primarios como puedeser el verde, roo, y azul $si estuvieran en otro formato se seguiria un procedimiento parecido&!

?upongamos que el color es $^D/E@D&?e descompondra en los siguientes colores

Roo $5)D/& 55555

1erde $5)E@& 555

2zul $5)D& 555

.&?e toman los bits mas significativos de los colores y se suman haciendo un shift de espacio alverde y de dos espacios al azul! espus se sigue de la misma forma con el siguiente bit mas

significativo

Roo 55555

1erde 555

2zul 555

?e toman los bits mas significativos:

Roo 5 1erde 5 2zul

U se combinan en un numero con la siguiente formula:

Resultado roo _ verdeVV _ azulVV.

55 555 W 555 W 55

onde 55 binario es igual a / en decimal

*l resultado final daria:

Roo 5 5 5 5 5

1erde 5 5 5 2zul 5 5 5

4 5 4


12/15

ResultadoGinario

55 5 5 555 55 55

Resultado / E + D 5 E / .

+& *l resultado indica en cual de los hios nos vamos a posicionar! Como el resultado contiene 0digitos entonces la altura del arbol es de 0 nodos como lo comentamos antes

R*?"(72# /E+D5E/.

*l color quedaria almacenado de esta forma

!.2.2.-%uanti5acion de %olores

Cuando se llega a un nodo hoa este contendra cuatro contadores! "no cuenta las veces que se hallegado a este color! #tro suma los colores roos del color, otro el del verde y del azul!

(a estructura del nodo hoa en CWW puede ser como sigue

struct octreenodeO

unsigned long referencesHunsigned long redHunsigned long greenH

unsigned long blueHstruct octreenode childsX0YHSH

Cada ves que se llega a ese nodo se aumenta el numero de referencias a W, y se suman loscolores

ReferenciaWWHRoo Roo W D/H2zul 2zul W DH

1erde 1erde W E@H

!.2.!.-&educcin de nodos

4 4


13/15

Cuando se llega a cierto limite de nodos hoa $ en nuestro caso .@D colores&, se selecciona el padre decualquier grupo de nodos hios $ en forma aleatoria generalmente& y se itera por todos los hios $sie)isten& sumando las referencias , el contador de roo, el del verde y el azul en el nodo padre!

Codigo en cWW para reduccion de Colores

for $int n 5H nV0H nWW&Oif $currentnode4QchildXnY&

Ocurrentnode4Qreference W currentnode4QchildXnY!referenceHcurrentnode4Qred W currentnode4QchildXnY!redHcurrentnode4Qgreen W currentnode4QchildXnY!greenHcurrentnode4Qblue W currentnode4QchildXnY!blueHNN free the node! 6e don`t need it anymoredelete $currentnode4QchildXnY&currentnode4QchildXnYJ"((HS

S

!.2.(.-%onstru6endo la Paleta

>ara construir la paleta de colores simplemente se recorre por todos los nodos hoas, y para hallar el colorse divide el contador de roo, azul y verde entre el contador de referencia! (uego se concatenan losresultados y se arma el color $ en nuestro caso un RG&!

*l c'digo en CWW para construir la paleta

NN"n (oop de Recorrido de los nodos hiospaletteXinde)Y!red currentnode4Qred N currentnode4QreferenceHpaletteXinde)Y!green currentnode4Qgreen N currentnode4QreferenceH

paletteXinde)Y!blue currentnode4Qblue N currentnode4QreferenceHNN7ermina el recorrido

*emplos

"sando la paleta 6eb?afe "sando >aleta de Colores #ctrees #riginal

4 . 4


14/15

).-%onclusiones

2 travs de todo el trabao nos hemos podido dar cuenta que las estructuras de datos espaciales

dentro de las cuales se encuentran los octrees, son una de las soluciones mas verstiles alproblemas de la relaci'n entre el procesamiento y el hardware necesario para procesar dichasimgenes van en aumento en los Iltimos a3os!

"na de las aplicaciones mas comunes para este tipo de estructura son los uegos de computadoraque se relacionen con ambientes +, as como los procesadores de imgenes! Comomencionamos anteriormente la relaci'n entre el hardware necesario para el procesamiento y lacalidad de imgenes va en aumento da a da, es decir se limita el consumo de ciertos productoso aplicaciones a un conunto e)clusivo de personas que posean un hardware de aceleraci'n devideo de ultima generaci'n, la meora que proponen los octrees es que solo se digitalic losobetos que se encuentren en nuestra vista, siendo una gran ventaa ya que nos se malgastaramemoria, ni recursos en graficar obetos que no necesariamente estn siendo procesados !

(a resoluci'n de imgenes se ve beneficiada debido a que la subdivisi'n de los obetos en sub!4cuadrantes del mismo, nos permite alcanzar la resoluci'n deseada ya que mientras mayor sea elnImero de divisiones hechas al obeto mayor ser la resoluci'n del mismo, permitiendo laoptimizaci'n de la calidad visual del obeto!

(a compleidad del algoritmo para implementar una octree es proporcional a la compleidad dela aplicaci'n en la que se utilice este!

(os #ctrees se pueden utilizar para la cuantizacion de colores debido a su e)celente rendimientoen guardar datos tridimensionales y la habilidad que tenemos para colocar un lmite al nImero denodos hoas!

+.-&ecoendaciones

#ptimizaciones para Culling

"n control de altura ser necesario debido a la recursion en la subdivisi'n ya que se debe detener en cuenta el trabao que realizara el procesador y la memoria vs! la altura del rbol!

?i se desea meorar la calidad visual del culling si se tiene un obeto +d que es atravesado por unnodo cubo se tiene que dividir la imagen para que no se imprima la parte que no se encuentra enel frustrum!

#ptimizaciones para 8uantizacion de Color

"na forma de meorar el uso de la memoria es reduciendo todos los nodos que tengan unareferencia de uno, manteniendo el rbol peque3o y meorando la eficiencia al acortar los tiemposde recorrido

7ambin se puede crear punteros entre nodos hios para meorar la velocidad de recorrido ya quela mayora de tiempo se malgasta en el recorrido desde la raz al rbol

*l rbol todava puede servir para guardar la paleta de colores , una ves recorrido el rbol,cuando se llega al nodo hio se puede guardar el color en el nodo y llegar a el de una manera masrpida que una bIsqueda secuencial entre la paleta

4 + 4


15/15

.-7iblio3raf8a

=aterial de Consulta:

2??2R??#J, "!, 2J =((*R, 7! .555! #ptimized view frustum culling algorithms forbounding bo)es!Journal of Graphics

?"2R?TU, #!, 2J #7?=2J, C! FFF! ynamic scene occlusion culling!IEEETransactions on Visualization and Computer

ZP2J, P!, =2J#CP2, !, P"?#J, 7!, 2J P#-- ;;;, T! *! FFE! 1isibility cullingusing hierarchical occlusion maps! Computer

oshua ?hagam oseph >feiffer, r ! ynamic ;rregular #ctrees! Jew =e)ico ?tate "niversity! CP2C#J =#R*J#,! .555! *studio y 2nalisis de la teoria de la multirresolucion en el

modelado de solidos!

!6eb (in9s: http://www.cs.unc.edu/~geom/SSV/ http:NNwww!gametutorials!com 999.*aasutra.co

4 / 4
http://www.cs.unc.edu/~geom/SSV/http://www.gametutorials.com/http://www.gamasutra.com/http://www.gamasutra.com/http://www.cs.unc.edu/~geom/SSV/http://www.gametutorials.com/http://www.gamasutra.com/

Arboles octales

Documents

Transcript of Arboles octales