Criterio para construir un octree...

[kuo]

Buenas a todos... Estoy empesando a hacer un pequeño proyecto...Se trata de un pequeño programita para mi tesis sobre representacion 3D y masomenos tendre que construir un buen algoritmo para administrar las geometrias que tenga en el entorno...Bueno segun lo que hasta ahora e leido he considerado que un octree seria muy conveniente para manejar la disposicion de los objetos en el espacio...Ademas de poder lidiar con culling, Frustum...ya saben

Bueno segun he leido entiendo que el octree Guarda en cada Hoja la geometria deacuerdo a un criterio...

Bueno mi problema es que no se cual es el criterio que se tiene en cuenta para colocar un solido en alguno de los nodos del octree...

Por ejemplo si hay un solo solido en el entorno me imagino que ese estara en la raiz del octree...y luego cuando se agregue un segundo solido al entorno que hago???...comparo su volumen y posicion con respecto al nodo anterior por ejemplo o que debo hacer para hubicarlo dentro del octee....

la verdad es que he imaginado algunos algoritmos pero no se si estare en lo correcto...

Bueno no se si podrian ayudarme tal ves describiendo los pasos que debo hacer para agregar un nuevo solido al octree...Se los gradeceria un monton... :D

Haaa...oigan alguien sabe como pongo una imagen en mi perfil...tengo probleas por que no me permite cargar una img desde mi pc...alguien sabe como se hace??? :?:

[blackwind]

hola,

supon que esta es tu escena:


El octree dividide la escena en 8 nodos. Y cada nodo se puede ir subdividiendo en 8 nodos a su vez.

El octree solo crea nodos donde existen poligonos. Entonces si tienes una escena muy grande y lo dividides varias veces, se van a ir creando subnodos solamente donde estan poligonos.
Asi:


esa es la base.

si te interesa un tutorial mas detallao, dime y te puedo mandar uno. Pero esta en ingles...

saludos,

[XÑA]

La gran duda siempre está en si el Octree tiene que ir a nivel de polígonos o a nivel de mesh. Porque si es a nivel de polígonos, luego para dibujarlo tienes que procesar la lista de una forma muy diferente a si es a nivel de mesh. Por ejemplo, un terreno es dado a recortar a nivel de polígono, pero una ciudad, es más dado a recortar a nivel de mesh. Y otro problema añadido es que al recortar a nivel de polígono, repetirás polígonos que cruzan dos ramas, por lo que o lo tratas a nivel de clipping, o dibujas dos veces el polígono, o gestionas esa repetición.

[blackwind]

Y otro problema añadido es que al recortar a nivel de polígono, repetirás polígonos que cruzan dos ramas, por lo que o lo tratas a nivel de clipping, o dibujas dos veces el polígono, o gestionas esa repetición.

Puedes meter los triangulos dentro de un nodo dependiendo algun criterio (si esta mas de la mitad de un lado que de otro, si tiene mas de tantos puntos, etc), y a la hora de combinarlo con otra tecnica como el frustum culling, eso no deberia de ser un problema.

Pero si tienes razon, dependiendo mucho del juego, es como sabras si te conviene trabajar a nivel de mesh o no

[kuo]

Esta bien...  8)
Si entiendo la parte en que cuando el mesh es demasiado grande debo considerarla en varios nodos... pero lo que realmente quiero saber es como se empiesa a guardar cada objeto en cada Voxel (nodo) y saber si tal ves el tamaño del voxel es predefinido antes de guardar cualquier objeto o su tamaño se establece a la hora de analizar cada objeto
...y que pasaria con el siguiente objeto...

Bueno pienso quien alla hecho esto antes me imagino que almenos debe tener una serie de pasos generalizados no...?? :?:

Simplemente quiero un pequeño algoritmo para que me de una idea... y ya yo analizando lo podre ajustar a mis necesidades...

Les agradeceria un monton que me respondieran... :wink:

[senior wapo]

Creo que no sabes bien lo que es un octree. Te lo explico.

Un octree no es una jerarquía de cajas, sino una jerarquía de planos de separación.

El octree divide el espacio alrededor de un punto en 8 partes. No te lo imagines como voxels porque no son cajas cerradas. En un octree NO existe el concepto de tamaño de voxel, no son voxels, no representan volúmenes sino clasificación delante/detrás de un plano (3 en realidad)...

Un nodo del octree es un punto y tres planos que pasan por él, de dimensiones infinitas.

Los tres planos producen 8 espacios limitados por los planos pero que en direción contraria son infinitos.

Un nodo NO es más pequeño que su padre, porque ambos son infinitos. Mirando un nodo cualquiera del octree no puedes conocer su "volumen", porque dependerá de quienes sean sus padres y además un nodo no es un volumen sino unos "bordes" de separación ente volúmenes.

Un nodo se representa por la posición x,y,z donde se cruzan sus 3 planos, su centro, no se guarda más información. Un nodo del octree es un punto y de él se imagina uno 8 subespacios según una regla cualquiera.

La regla más común es que los 3 planos de separación sean paralelos a x,y,z formando ángulos de 90 grados entre sí. Tan octree es ése como uno cuyos planos estén inclinados al azar entre sí. Lo importante es que definan 8 subespacios al cruzarse.

Insertar un objeto en un octree no es más que comparar en cada subespacio del nodo si el objeto invade ese espacio. Si lo invade, lo metes en ese nodo o en sus hijos de existir. Esto lo haces por cada uno de los 8 subespacios de ese nodo.

Cuando hay demasiados objetos en un subespacio lo que haces es elegir un punto cualquiera dentro de ese subespacio y colocar un nodo ahí.
A continuación coges todos los objetos que había en el subespacio original y los vuelves a insertar en el octree, pero por agilizar, lo haces empezando por el nodo que has creado, porque ya sabes de antemano que van a caer ahí.

El punto que eliges para dividir el subespacio conviene que sea uno que reparta más o menos por igual los objetos de ese subespacio entre los 8 nuevos subespacios resultantes.

Ese reparto equitativo no se refiere a número de objetos necesariamente, puede ser por cualquier métrica de coste. Una muy popular es por cantidad de polígonos, y por eso, entre otras razones, la gente a veces trocea los objetos cada vez que los divide un plano. Este proceso trae como consecuencia que cada pseudoobjeto resultante (grupo de polígonos) solo está presente en uno de los 8 subespacios del nodo.

Espero que algo de lo que he puesto te aclare tus dudas.

[kuo]

Oe senior wapo...que buena explicacion del tema... :D

La verdad es que he leido varios tutoriales y ninguno me revelo los misterios(Bueno almenos para mi) que has expuesto...En todos los tutoriales que habia leido graficaban el octree como cubos cerrados...nunca imagine que fuera diferente

Gracias senior wapo por todo tu ayuda me sacado de muchas dudas...Ahora si tengo una idea clara de la particion del espacion con octrees...

Bueno viejo ahora me surge un interrogante...pero mas bien es algo que necesito que me confirmeis... :?:

Segun lo que me has explicado...(de la definicion de octree)

Cuando haga la verificacion del frustum lo logico deberia ser que verifique por cada punto guardado(osea dentro de un nodo del arbol)... si uno o mas de los seis vertices del frustum cae dentro de una de las 8 diviciones del octree no... si es asi ese subespacio es candidato a ser evaluado para ver si un objeto que esta dentro de el cae en el frustum...
bueno segun mi razonamiento pienso que es asi ... o acaso usan una logica distinta o mas rapida... :?:

[kuo]

rectifico lo anterior sobre el frustum...se que la piramide frustum tiene 8 vertices..jeje

[senior wapo]

Efectivamente, si un subespacio contiene parte del fustrum, ese subespacio aparece en pantalla y hay que evaluar sus objetos.

El problema es que no basta con comprobar los vértices del fustrum hay que recortar el poliedro contra los planos y eso es costoso.

Existe un algoritmo muy rápido para saber si un cubo alineado con los ejes x,y,z intersecta a un plano y a que lado queda. Un fustrum es el espacio definido por 6 planos. 4 que pasan por los bordes de la pantalla, el plano lejano y el plano cercano.

Si eres capaz de convertir un subespacio en un cubo puedes usar el algoritmo.
Para cada nodo compruebas cada uno de sus 8 subespacios contra los 6 planos del fustrum, y con eso averiguas si el subespacio está dentro del área visible.
Técnicamente, en  cada nodo, solo necesitas comparar con los 4 planos del fustrum que pasan por los bordes de la pantalla.


Lo que se suele hacer es considerar los subespacios como finitos y según los subdivides guardas sus dimensiones.

Un nodo de este subtipo de octree, además de contener el centro y 8 punteros a nodos, contiene, el centro, 8 punteros a nodos y 8 vectores que representan el tamaño de su subespacio correspondiente.

El algoritmo para comprobar a que lado de un plano queda una caja alineada con los ejes es este:
1. Miras la normal del plano y los signos de sus componentes x,y,z para clasificar en que octante se metería si el origen de la normal fuese el centro de un nodo octree.
2. Eliges la diagonal de la caja que más alineada está con dicha normal.
3. Comparas contra el plano los dos vértices de la caja atravesados por la diagonal. Si ambos están al mismo lado del plano, la caja invade un solo subespacio (lo identificas con el signo del resultado) y si tienen signos contrarios es que la caja invade ambos subespacios.

Para culling te basta con comprobar un solo vértice ya que te interesa que invada el lado visible, no te importa si lo hace entero o en parte.

Código que lo implementa en los fuentes del Quake, la famosa función BoxOnPlaneSide:
http://csourcesearch.net/package/aaquake2/0.1/quake2-3.21/ctf/q_shared.c/function/BoxOnPlaneSide/349,1

[kuo]

Otra ves gracias...senior wapo... :D
Buena explicacion...

Algo muy parecido a lo que describes sobre el frustum lo encontre en http://www.fuzzygamedev.com/?p=215 donde realizan la demostracion matematica de sacar los planos del frustum, para verificar si algun BoundingBox o BoundingSphere esta dentro del frustum...es muy bueno... :)

Ahora se que estoy por el camino correcto...ejejjejje :idea:

Oe senior wapo gracias por tu tiempo... espero que cuando tenga otras dudas me puedas dar una mano :wink: