Combinar Espacialidad Con Jerarquía

[eduwushu]

 Hola buenos dias tengo q escribir porque estoy hecho un lio acerca del uso de estructuras espaciales como los octrees o quadtrees en una escena y su integración en el grafo de manejo de la misma.
El grafo representa una jerarquía de nodos que se usa segun tengo entendido para relacionar jerárquicamente una serie de entidades que cargamos en la escena para que por ejemplo si movemos un nodo bicicleta por la escena se muevan los nodos hijos ruedas con ella sin indicarlo explícimtamente lo que veo una ventaja provechosa. También serviría esto para ,por ejemplo, hacer el culling de objetos de forma más eficiente y ta,bién la detección de colisión u sando bounding volumes en cada uno de los nodos.
Ahora bien, he oído también las ventajas que supone el uso de una estructura de organización espacial en la escena. Dividimos la escena en regiones espaciales de tal forma que si por ejemplo el frustum de visión no "toca" determinadas regiones, éstas y todos los polígonos que se encuentran dentro de ellas se pueden descartar para el dibujado. De esta manera eliminamos de entrada grandes porciones de escena para el dibujado y mejoramos el rendimiento. Ahora bien, ¿cómo combinar el establecimiento de una jerarquía entre los objetos con su organización espacial en la ecena? ambas cosas son totalmente independientes.
Me surgen muchas dudas con el uso de estructuras espaciales. Si metemos en nuestra escena un octree para manejarla sería necesario tratar a nivel de polígonos cada uno d elos objetos cargados en la escena para repartir esos polígonos entre las distintas celdas en q se ha dividido la escena. Sin embargo a nosotros lo que nos interesa es manejar la escena a nivel de entidades: no queremos saber que medio personaje esta en una celda espacial y la otra media en otra solo debemos de preocuparnos acerca del personaje no es asi?
¿Cómo integrara entonces en el grafo de escena todo esto?
Y ya no dig nada si encima me pongo  pensar en si sería posible manejar ciertas entidades de gran tamaño de una escena con sus propios octrees. Por ejemplo tener en la escena un terreno manejado por un quadtree y un  castillo manejado por un octree y luego unpoblado manejado por otro octree.... etc
Alguien puede aconsejarme? Por cierto , me he leido ya los libros de H.Eberley de Game Engine Architecture y también de Game Engine Design y no se si es que me he saltado algo pero no me han aclarado mucho en este aspecto
¿Alguna idea por favor? (nooo)  

[senior wapo]

 Normalmente, las estructuras espaciales son nodos de la escena también. Todo lo que está contenido en ellas son hijos del nodo que representa al octree/quadtree, que a su vez es un hijo más de otra entidad. Cuando al recorrer el arbol de escena te toca dibujar dicha entidad simplemente dibujas sus nodos hijos utilizando los mecanismos que proporciona la estructura.

Ojo, que tu arbol de escena no limita su contenido necesariamente a cosas visibles.

Cada nodo de tu escena, sea del tipo que sea (malla poligonal, octree, quadtree, billboard) debe ser responsable de dibujarse a si mismo y de ordenar a sus hijos que se dibujen. Cada nodo que transformas es responsable de transformarse a si mismo y de informar de dicha transformación a sus hijos para que hagan lo propio si usan coordenadas globales en vez de locales. La manera en que se gestiona internamente por cada nodo dependerá del tipo de nodo que sea. Cada hijo que mueves ha de notificar a su padre (y este al suyo si procede) por si necesita actualizar sus estructuras internas. Si el nodo padre es una malla, pues se limitará a actualizar su bounding box, pero si es, por ejemplo, un octree, pues tal vez moverá al hijo a otro nodo, recalculará volumenes y planos, etc...

Dibujar o transformar una escena debe limitarse a darle la orden al nodo raiz, que recursivamente propagará la orden a sus hijos.

Todo eso, asumiendo que buscas un grafo de escena universal, porque a mi no me importaría tener código con casos especiales y demás si eso genera más velocidad.

En cuanto a dividir un objeto en grupos de poligonos según cruza nodos de un octree, tampoco es necesario si no quieres. Puedes limitarte a ponerle en los dos nodos a la vez (pero con distinto bounding box recortado al nodo)  y a la hora de dibujar poner una marca (por ejemplo el número de frame) y asi detectar si ya lo has encontrado antes en este frame y no tienes que dibujarlo de nuevo en este frame. Dependerá del tipo de escena y objetos que uses, claro.

[eduwushu]

 a ver hay una cosa q no entiendo q tu me has dicho. Suponte que cada objeto cargado en la escena es una entidad q entre sus propiedades tiene la malla que estamos utilizando para ese objeto. Bien para empezar cual es el criterio que sigues para construir el octree?? Cada nodo tiene que tener ocho nodos hijos pero cuando dejas de descomponer en nodos hijos? muchos autores te dicen que pares de dividir un nodo en hijos cuando el numero d epoligonos dentro de ese nodo sea menor que un cierto número que se considera aceptable. Pero ahi ya estamos trabajando a nivel de poligonos.
O suponte esto otro. Suponte que tenemos un objeto en la escena que es un castillo. Ese castillo es geometría estática y es un único modelo mu grande de muchos polígonos y abarca pues un buen cacho de la escena y por lo tanto una gran cantidad de nodos del octree. Estará referenciado en todos ellos por tanto. De todas formas el castillo es una entidad demasiado grande como para ser renderizada de golpe siempre.
Intuyo que a lo mejor ahí es responsabilidad del modelador de la escena el no hacer ese tipo de objetos gigantescos para que el rendimiento no haga chof, estoy en lo correcto? es q es unpoco lioso todo esto.
Aun asi nos queda el problema de cuantos niveles hacer del octree y qué criterio seguir puesto que entonces tendrias que meterte en la malla de cada objeto eintersectarla con los planos del cubo que representa el nodo y ver cuantos poligonos caen en cad cubo del octree.... si metes mas objetos ademas habría que reconstruir el octree otra vez... lo que me parece muy costoso.

[BeRSeRKeR]

 No estoy muy puesto en el tema pero me imagino que lo que se tiende a hacer es que lo que es la escena estática (el castillo, el terreno, etc) sea una sopa de polígonos que no diferencia las entidades, es decir, da igual si unos polígonos forman un castillo u otros forman un terreno, todo está mezclado. Luego tendrías los modelos que puedan ser dinámicos que sí se tratarían como entidades separadas, con sus propiedades únicas como por ejemplo la matriz de transformación necesaria para posicionar/orientar/escalar dicha entidad en el mundo 3D.

Saludos.

[zupervaca]

 Pasate por esta web, esta en español, explican y dan un codigo de como trabajar con octrees, suerte.

[BeRSeRKeR]

 

Pasate por esta web, esta en español, explican y dan un codigo de como trabajar con octrees, suerte.

Anda, el autor de ese artículo me suena de algo (de hecho es su página web)... jeje

[eduwushu]

 no estoy muy seguro de eso que me dices. Por ejemplo Eberly en su libro (lo nombro porque ya me lo han recomendado miles de veces) trata absolutamente todos los objetos del mundo como entidades separadas que luego pueden tener geometría asociada.
Por ejemplo tendrá un nodo edificio, que es un nodo de agrupacion del que cuelgan la habitacion uno y la habitacion 2 de las que cuelgan nodos que representan los objetos de esas habitaciones.
Eso es geometría estática y sin embargo los ha modelado como entidades separadas.
Además por ejemplo en el Lineage 2 si lo conoces he estado haciendo ciertas pruebas para ver si me aclaraban como el motor que usa este juego lleva a cabo la oclusión y la distribucin espacial ( como ves estoy un poco desesperao) me ponía contra una pared muy pegado y giraba la camara de tal forma que llega un momento que puedes ver lo que hay al otro lado de la pared (quizás un pequeño bug?) y ver también queé es lo que se ha ocultado y lo que permanece. Lo cierto es que por ejemplo una casa que debería estar al otro lado no es dibujada por el motor y es acasa evidentemente forma parte de la geometría estática mientras que otros elementos como la continuación de la pared al otro lado si están dibujados(quizás porque forma parte todo de la misma entidad?) así que esa casa debe estar tratándose como una entidad separada con posibilidad de ocultarse según la situación lo requiera (en este caso por oclusion debido a la pared)
De todas formas si trataras toda la geometría estática  como una sopa d epoligonos...¿si por ejemplo quieres quitar los poligonos correspondientes a una casa como lo harías? como sabes cuales son los poligonos que pertenecian a esa casa que cargaste en el escenario si estan en la sop aque mencionas?

creo que estoy dejando escapar algo por alto que no me doy cuenta

[zupervaca]

 Tal vez tu estes interesado mas en otro sistema, el clasico de jerarquias, en el cual mediate bounding boxes realizas oclusiones, este sistema es muy dinamico y rapido, pero implica un curro bestial para los grafistas, este sistema se suele usar mucho en personajes y objetos movibles, pero para el tema de decorados estaticos que lo importante es pintar lo necesario, comprobar las colisiones minimas y que sea rapido lo mejor son bsp, octrees, etc. Tambien puedes utilizar un octree y luego tener los objetos separados como entidades, pero realmente un decorado siempre son poligonos sueltos, solo tienes que ver el bsp que se usa en el quake3 por ejemplo que estan ordenados para realizar el render rapidisimamente, pero que realmente no tienes la manera de saber si un poligono es una tuveria o un bater, y la verdad... ¿para que saberlo? la manera de saber que es cada cosa o lo clasico, como debe sonar al disparar o caminar sobre ella, es mediante el material o textura del poligono.

[senior wapo]

 Hombre, lo de no dividir los polígonos era un apunte aparte, si te lía, pasa del tema. Pero vamos, el tema es que una estructura espacial (quadtree/octree/matriz/etc...)  puede tanto contener una malla particionada como contener distintas mallas móviles. Al ser móviles, el nodo que las aloja puede ser diferente según se muevan por el espacio.

El tema es, que aparentemente, tienes asociado en la cabeza que un octree contiene polígonos. No es así necesariamente. Puede contener entidades: puntos, esferas, cualquier cosa con posición espacial. Un octree es una estructura de clasificación espacial.

Imagínate que en tu mundo virtual quieres encontrar cuantos objetos están iluminados por una luz omnidirecional (un globo de luz) de radio 10 metros situado en la posición (4,9,1). Quien dice luz, dice radio de explosión de una bomba para dañarlos. Metes en un octree los centros (y radios) de tus objetos (con un identificador de objeto para que leugo sepas a que se refiere), y luego le preguntas al octree que objetos están dentro del radio de influencia: es decir, que nodos tocan dicha esfera, y en cada nodo que lo haga compruebas cada objeto metido. Fijate que dicho octree no guarda poligonos, solo centros y volumenes.

El criterio de división de nodos lo pones tú. Lo calculas comparando el coste de buscar en el octree con el coste de usar una entidad individual. Si usar la entidad implica dibujarla tardando 100 milisegundos de media, y recorrer un nodo del octree te cuesta 20 milisegundos, librandote de usar (dibujar) la mitad de sus entidades, pues te rentará más tener pocos objetos por nodo. Si comparar un nodo del octree te costase 70ms pues te rentaría más acceder a pocos nodos, es decir, tener muchos objetos por nodo. Lo más facil es "adivinar" ese equilibrio de antemano, ya sea manualmente o en función de alguna estadística automática al crear el octree (número estimado de texturas, o poligonos, etc...).

Suponte que tenemos un objeto en la escena que es un castillo. Ese castillo es geometría estática y es un único modelo mu grande de muchos polígonos y abarca pues un buen cacho de la escena y por lo tanto una gran cantidad de nodos del octree. Estará referenciado en todos ellos por tanto

Estará referenciada en el nodo que la contenga totalmente, no en sus hijos que lo contienen parcialmente. Pero no me refería a eso. Meter una entidad entera en un nodo es válido para personajes no para estructuras grandes. En estructuras grandes haces lo mismo, pero por submallas o incluso polígonos, ya que no se suelen mover. De hecho la implementación típica de octree la suele usar mucha gente a nivel poligonal, solo quería dejar claro que no es la única via. Una pared larguísima (1 polígono) estaría en muchos nodos, pero los escalones de una escalera muy alejada no estará en los mismos nodos.

De todas formas, la estructura espacial más optima dependerá del hardware objetivo y de la naturaleza de los datos. Si por ejemplo, dibujas por software o con tarjetas viejas que mandan toda la geometría cada frame (no hay vertex buffers), pues te renta mucho tener estructuras de gran granularidad poligonal, porque el coste es lineal al numero de poligonos (la diferencia entre enviar 100 poligonos individuales y enviarlos de una tacada es pequeña o nula <= software). La estructura más habitual es un BSP.
Si tu objetivo es hardware más moderno, usas estructuras de baja granularidad poligonal y alta coherencia espacial y temporal, porque el coste de enviar 100 polígonos individuales es bastante superior al coste de enviar 100 poligonos de una tacada. En estos casos es más rentable usar portales y dividir la escena estática en bloques relacionados (por ejemplo, dividir en  habitaciones). Las entidades, casi,casi, las envias enteras al módulo de render.

Hablo a nivel de geometría, ignorando el "detallito" de los cambios de estado (coste por cambiar el tipo de iluminación,material, etc... ).


Creo que te he liado más :D

[marcode]

 Creo que a veces te convendría en lugar de "eliminar" objetos, clasificarlos para que se dibujen de atrás hacia adelante, en especial para muros y objetos que no sean muy complejos en cuanto al número de vértices. De esta forma, solo se pintarán las partes visibles, y no te saldrán algunos fallos.

Y lo de tratar todo como una sopa de polígonos no creo que sea buena idea, yo usaría diferentes métodos según se trate de terreno, construcciones, habitaciones, objetos estáticos, dinámicos, etc.

[eduwushu]

 mmmmm jajajaja si quizás unpoquito más. El tema es que quizás no tengo yo demasiado claro como se hace en la actualidad esto de la geometría estática. Intento pensar en cómo en uno d elos juegos comerciales que conozco pueden estar usandose las técnicas que voy viendo(soy un tio práctico jjaa) y quizás me lío más. El caso es que me encuentro con ciertas contradicciones.
Me dices que en un octree podemos encontrarns a nivel de poligonos y también podríamos introducir entidades ¿pero podemos estar usando ambas técnicas al vez?
El caso es q yo en motores como por ejemplo ogre3d no he visto nada que me indique que la geometría estática es cargada de golpe como un pegote de poligonos. En ogre el uso es muy directo : tu creas una entidad a la que le das un nombre por ejemplo Edificio y luego a esa entidad le asocias una representación que será la malla del edificio con todas sus propiedades. Luego además tienes distintos tipos de managers de escena : basados en un octree, en un arbol bsp... el caso es que todo en la escena se maneja como una entidad, no existe separación de lo que es dinámico y lo que es estático. Esto es lo que me confunde puesto que lo veo en una gran cantidad de articulos y libros es esto mismo. Existen entidades y ya está luego no se como puñetas se están manejando.
Yo he llegado a la conclusión que me estáis diciendo (creo) que es mejor manejar por un lado geometría estática que no cambia y por otro la geometría dinámica. Otra cosa es luego cómo este organizada esa geometría estática.
Podemos hacer que en un fuchero no svenga como una ristra de polígonos que cargamos y distribuimos en nuestro octree, o supongo que sería posible que viniera esa geometría dividida en entidades.¿ Porqué hacer esto? Pue por ejemplo para beneficiarnos del culling de oclusión (aunque supongo que también podría hacerse si tenemos polígonos sueltos). Ya que si tenemos un cierto numero de objetos dentro del frustum que hemos determinado puede que ciertos objetos esten ocluidos por entidades que hemos elegido como oclusoras por ejemplo.
Si tenemos entidades en geometría estática podemos también beneficiarnos de lo que es también la agrupación: definiremos el castillo como tres entidades tipo torre una entidad muralla una entidad foso y otra entidada fortaleza ( o quizás esto no es necesario si ya lo estamos tratando como polígonos repartidos en nodos del octree y es justo lo que estoy pasando por alto??)
Quizás no es tan necesario que la geometria estática este dividida en entidades y tengamos que saber a que entidad pertenece cada una... quizás eso es cosa del editor de escenas el permitirnos editar una escena a nivel de entidades para luego transformar lo hecho en una ristra de polígonos cierto? a lo mejor es lo que estaba confundiendo
¿qué opinais?
PD:Gracias por vuestras respuestas

[eduwushu]

 podrias aclarame un poco marcode como harias eso a lo que te refieres?

Y lo de tratar todo como una sopa de polígonos no creo que sea buena idea, yo usaría diferentes métodos según se trate de terreno, construcciones, habitaciones, objetos estáticos, dinámicos, etc.

¿Cómo propondrías hacerlo tu? cualquier opinion sera bienvenida de verdad ( siempre y cuando tengas ganas de onerla jejejeje) (ole)  

[Zaelsius]

 Eduwushu, tampoco te calientes demasiado la cabeza :P . Cada tipo de juego y hardware objetivo se beneficiarán mejor de una clase de organización espacial diferente.. no hay ningun método general "definitivo".

Respecto al Lineage II, está basado en Unreal Engine 2.0. En Devmaster.net encontramos esto respecto al "scene management" en UE2:

General, BSP, Portals, Occlusion Culling, PVS, LOD:
• DSG (dynamic scene graph) is a natural extension of portal technology. A dynamic scene graph consists of a root node, corresponding to the player's immediate surroundings, and a hierarchical tree of child nodes.
• Enhanced portal-based visibility system includes "antiportal" occluders, supported as two dimensional sheets or three dimensional volumes, to cull objects or portals within a zone.

De todas maneras, desconozco si los desarrolladores del juego habrán hecho alguna modificación o extensión al motor acerca del manejo de escenas  :ph34r:

Por cierto, ¿en qué andas metido? Algun juego, motor..?

[eduwushu]

 Pues veras jejeje mi istoria es unpoco desgraciada. Quiero hacer como proyecto de fin de carrera un pequeño motor gráfico que pueda presentar y lo cierto es que llevo desde el año pasao y me he leido ya bastantes libros acerca del tema , artículos, tesis acerca de programación gráfica, foros... un largo etcetera.
El caso es que con todo lo que he leido ninguno de los profesores del departamento d einformática tiene ni puñetera idea acerca del tema de gráficos y menos de engines y su funcionamiento por lo tanto nadie puede aconsejarme y me he quedado atascao ...¡¡antes de empezar!!! lo cierto es que cuando quiero comenzar a elaborara el proyecto y ponerme manos a la obra no arranco porque no se que punto de partida tomar. Que´ria empezar con el sistema de manejo de escena (así que recopilé toda la información qu tengo acerca de grafos de escena ,estructuras espaciales ,arquitectura de escenas...etc) para bueno desde ahí ir ampliando el motor con otras cosas como deteccion de colision, multitexturizado... etc
Pero como vesme encuentro upoco atascado porque no soy capaz d ejuntarlo todo para empezar. Quizás necesite unpequeño empujon o arranque para encarrilar el asunto pero no me llega jajaja y si no lo empiezo ya me voy a quedar sin tiempo
Te gusto mi triste historia? La verdad es q me hubiera gustado ver esto con más calma y tranquilidad y sin tanta presión pero así son las cosas lo que no quiere decir que me haga ilusión conseguir el reto jeje

[eduwushu]

 por cierto... alguna idea que alguien me pueda dar acerca de como empezar??? :P
quizas ara empezar no deba meterme en tantos detalle sy luego pueda ir refinandolo quien sabe auque me gustaria aclarar antes todo esto