Foros - Stratos

 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)  

 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.

 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.

 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.

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

 

Cita de: zupervacaPasate 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

 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

 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.

 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...).

CitarSuponte 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

 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.

 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

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

CitarY 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)  

 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:

CitarGeneral, 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..?

 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

 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

 El problema es que considerar "hacer un motor" como una meta, sin tener en cuenta que es sólamente una pieza más de una aplicación, suele ser un error. Precisamente porque quizá no te has planteado para qué vas usar el motor, no sabes por donde empezar. Si tu meta fuese hacer una versión simplificada del Quake, sabráis por donde tirar. Si quisieses hacer un RTS, tambien tendrias una idea de lo que hace falta. Ahora.. "hacer un motor".. es algo difuso, ya que puede ser tan simple, complicado, específico o general como uno quiera.

Mi consejo es que te marques un objetivo más concreto.

 entonces lo que me quieres decir es que si tuviera en mente un tipo de juego o aplicación que darle al motor tendría más clara la formaen que quiero hacer las cosas?realmente yo cuando pienso en cómo debería hacerlo estoy pensando en juegos comerciales como ya he dicho y pienso en si la forma en que estoy concibiendo el disñeo permitiría hcer untipo de juego similar pr siempe me surge algo que no termina de encajar y que me impide diseñar el sistema de manejao de escema de una vez.
De todas formas si concreto cual sería el consejo que me darías para comenzar el desarrollo? desde el punto de vista de tu experiencia por donde deberia comenzar? (por lo menos para tenerme a algo a lo que agarrarme)
Se que muchos del foro estais haciendo tambíén proyectos similares asi que si teneis algun consjillo siempre sera bienvenido o contame vuestra experiencia personal. Gracias y enhorabuena por el foro este que hay gente mu maja

 Lo que quiere decir ZaelSiuS es que no existen motores que vayan bien con todos los juegos, cada juego tiene unas necesidades, sabiendo que juego o aplicacion quieres hacer sabras que necesidades debe cubrir tu motor.

 por lo tanto lo que tengo q tomar es una decision acerca de cómo debería hacer las cosas y manejar la geometría en mimotor sabiendo esto no? hombre más o menos de lo que he intentado informarme es de como lo ha hecho las distintas personas que se han embarcado en algo de esto como yo para ver posibilidades y aprender de errores de otros pero comohabeis visto pues no he conseguido llegar a mmuchas conclusiones. Si sabeis donde podria ver con claridad como lo han hecho ciertas personas su manejo propio pues guay sino intentaré tomar una decisión por mí mismo y de esta forma ve´re hasta donde puedo llegar.
Por lo tanto hasta ahora tengo dos podsibilidades segun lo que he entendido:

          +Bien podria elegir manejar como entidades la geometria estática (con todo lo que ello supondria y su dificultad)
          +Bien podria considerar es ageometría como una ristra de polígonos que manejo con un octree

Luego deberia de ver como hacer la oclusion y deteccion de colision en cada caso etc etc o qué características debería incluir según lo que quiera para el tipo de escenas que tenga que manejar con el motor ¿cierto?

 

Cita de: eduwushupor lo tanto lo que tengo q tomar es una decision acerca de cómo debería hacer las cosas y manejar la geometría en mimotor sabiendo esto no?

A no ser que te pase como a mí que prefiero programar motores antes que juegos, porque realmente lo que me gusta más es desarrollar efectos y demás "pijaditas". En ese caso no te hace falta ningún sistema de visibilidad salvo, tal vez,  algo tan simple como el frustum culling. Aunque crear sistemas de determinación de visibilidad también tiene su gracia. :D

Saludos.

 Bien he estado pensando en el tipo de escenas que me gustaría estar manejando y con ello intentar pensar qué es lo que más me convendría hacer y aquí dejo unas reflexiones para que opineis:

Bueno supongamos entonces que vamos a hacer un manejo de la geometría estática base como si se tratara de un conjunto de polígonos que podemos dividir según el uso de texturas que hace cada uno de ellos en subconjuntos y que podemos además distribuirlos en los nodos de un octree que utilizamos para el manejo de la escena.
Sin embargo un escenario no solo se va a componer de geometría inmóvil totalmente. Supongamos así por ejemplo una rueda de noria, puertas,ascensores,pasarelas que se mueven... etc
La probabilidad de encontrar un gran numero de items de este tipo en una escena es elevada correcto? Como deberiamos llevar a cabo el control de este tipo de elemntos?? No son los elementos dinámicos más problemáticos como por ejemplo un personaje o un enemigo dentro del escenario que tienen "libertad total de movimiento" por el espacio del escenario.Están localizados en zonas concretas del mundo con movimientos más o menos limitados. Sin embargo estos ya no podemos considerarlos dentro de una sopa d epolígonos puesto que será necesario su manejo individual y su movimiento.
Sin embargo si pensamos en incluirlos en el grafo de escena que por ejemplo podriamos estar usando para los personajes dinámicos la mayoría de ellos como cada una de la spuertas no estarán ligadas a nada, y colgarán directamente del nodo raíz del grafo provocando así que tengamos un grafo extremadamente plano que casi estaríamos utilizando a modo de lista. De tal forma que para comprobar por ejemplo colisiones de nuestro personaje rincipal con el entorno comprobaríamos la colisión con lo spolígonos del nodo del octree en el que nos encontramos y además tendríamos que comprobar la colisión con cada uno de este tipo de objetos puesto que no los tenemos localizados espacialmente. Sin embargo si supieramos que ciertas puertas estan localizadas dentro de un edificio concreto en una habitación concreta sólo las tendríamos en cuenta cuando el personaje estuviera proximo a dicha habitacion no se si me entendeis y por lo tanto conseguimos eliminar gran cantidad de comprobaciones con otro elementos dinámicos que puede que se encuentren muy alejados de donde se encuentra realmente nuestro personaje y que por lo tanto serían inutiles. En parte esta ahi donde veo la necesidad de tratar de alguna manera la geometría estatica no como un todo compacto sino como algo jerárquico que pueda llegar a aorganizarse espacialmente: sabemos que tenemos en la geometría estatica un espacio abierto que pueden ser unos jardines donde tenemos varias torres. En dichas torres hay unas pasarelas que tienen posiblidad d emoverse si se acciona un mecanismo o palanca del escenario. El espacio del jardín y las torrees son geometría estática pura que según me habéis dicho podríamos manejar con una ristra de polígonos perfectamente... que alegría que alboroto (ole) .Bien,tenemos también ahoralas pasarelas que están en extremos opuestos del jardín y por tanto separadas espacialmente y que son entidades que podríamos llamar pseudodinámicas (tienen posibilidad de moverse pero en un espectro reducido) de tal manera dispuestas que si estamos colisionando con una es imposible colisionar con la otra por ejemplo. Sin embargo si las ponemos en el grafo como son independientes tendríamos que hacer la comprobación contra las dos aun sabiendo que no podenos colisionar con las dos a la vez, este problema se deriva de no tener ninguna forma de localizarlas espacialmente.

¿Existiría la posibilidad de además asociar esas entidades semidinamicas a los nodos del octree junto con los poligonos de la geometría estatica para localizarlos espacialmente y evitar hacer comprobaciones así con todos ellos?¿Qué opinais o qué tipo de soluciones se os ocurren?

PD : espero no estar dando mucho la tabarra  auque no se vosotros pero yo asi toy aprendiendo mucho jejeje (ole) , muchas asias

 Otro ejemplo que se me acaba de ocurrir: ¿Qué pasa si quieres aplicar LOD a un elemento de la geometría estática como por ejemplo podría ser una estatua? Ahí ya no puedes si se cargó en la escena como un conjunto d polígonos sin más puesto que tendrías que buscar aquellos polígonos que pertenecían a esa estatua y sustituirlos por otros polígonos que siguen representándola pero que son menos cantidad.
¿Ves? es que segun voy pensando voy encontrando cosas que me rompen el esquema anterior que tenía planificado.

 Yo dividiria entre geometria estatica de la fase (paredes, suelo, escaleras, etc) y entidades estaticas del mismo. Lo de trabajar a nivel de poligonos se haria en la fase, todo lo demas serian entidades. Es decir, en este nodo del octree (o quadtree) tengo estos poligonos y tambien estas entidades. Como no todas las entidades van a estar en un unico nodo, puedes usar los "trucos" que se han comentado anteriormente, como asignarle el numero de frame o un booleano de "procesado", para ver si ya esta en la lista de dibujado o no. Para las entidades dinamicas puedes usar otra estructura, por comentar otra idea.

Tambien quiero comentar que, aparte de pensar para que tipo de juego sera el motor, hay que pensar en como se creara el contenido: puedes hacer el motor del Quake, pero si hacer fases para el (poner entidades, identificar portales, etc etc) es mucho trabajo, pues el motor, por muy bueno que sea, ya no vale tanto (siempre desde la perspectiva de un pequeño grupo de desarrollo, si eres Square y tienes 250 empleados/esclavos es otra historia :D)

 de todas maneras estoy pensando que también será necesario identificar donde se encuentran espacialmente las entidades dinámicas porque a pesar de ser dinámicas tenemos que saber en qué región espacial se encuentran para eliminarlas cuando sea necesario.
He entrado en una página muy curiosa que es la página de desarrolladores de valve y he estado viendo como se estructuran las esceas en el source engine. Por lo que me he podido enterrar no tratan la geometría de la escea como un buffer de polígonos extragrande que luego dsitribuyen sino que dividen la geometría en distintos tipos: por unlado tenemos objetos inmoviles de la escena, geometría estática pura de la escena que además creo que se subdivide en trozos más pequeños cada uno como si fuera una entidad (como si el escenario se contruyera a partir d piezas como unpuzzle), objetos dinamicos, objetos ragdoll para personajes....etc
Cad vez que veo algo nuevo me lio más jajajaja en fin estoy unpoco perdido

 
Yo también creo que es lo mejor eso, lo mismo que tenias pensado, pero a nivel de entidades, no de polígonos. Aquellos objetos que sean demasiado grandes como un edificio, murallas, o un terreno, la divides en partes manejables.

En cuanto a los dinámicos, si consideras que en la jerarquía del escenario tendrás objetos padre que serán comprobados por primera vez, no veo ningún problema en considerar a las objetos animados también como padres, estos a su vez pueden tener asociados otros objetos más pequeños, como armas o herramientas, o incluso otros objetos animados.

Puedes pensar que el coste de comprobar tantos objetos animados puede ser grande, pero yo creo que puede ser igual o menor que el tener que asignar continuamente el objeto a la parte de la escena correspondiente.

No se, es una idea a ver si podemos aclaramos un poco más esto, yo en tu lugar lo simplificaría todo un poco más, creo que estás metiéndote en cosas demasiado avanzadas, y en las que hay que tener todo muy claro, tener una cierta experiencia, para resolver la cantidad de problemas que pueden surgir.

Aún así están bien estos hilos, como dices se aprenden cosas.

 A ver, yo de esto la verdad es que no tengo mucha idea ...
Los nodos de particion espacial podrian ser:

+ (en caso de exteriores)Entidad escenario: un octree (o quadtree p.e. para terrenos) para tu geometria estatica. La información de los nodos hojas serian los poligonos o primitivas de polys que forman la geometria. Debes saber que esto te puede servir para varias cosas: si calculas el/los nodo/s (del octree/quadtree) donde estaria un objeto mobil puedes reducir todas las colisiones a comprobaciones con los poligonos(o trozos de ellos) que contienen el/los nodo/s. Si recorres ordenadamente (no digo que sea facil) los nodos respecto al punto de observación puedes elegir "ocluders" y dibujar en un orden correcto, evitando, al menos, la comprobación de z-buffer(aunque puede que si que te interese guardar el valor z-buff del pixel dibujado) y permitiendo pequeñas aprox. a los LOD. Un culling rápido y efectivo es casi trivial con este sistema.

+ los objetos estaticos? -->Entidad objetos_escenario: otro octree, esta vez con nodos entidades, que referencien a los nodos objetos que contienen su geometria(si tienes 8 mesas iguales, es tonteria tener 8 vece definida la misma geometria, recuerda que son grafos son aciclicos). Sirve para lo mismo pero con objetos entidades.

+ objeto estatico interior: puedes utilizar bsps de distintos tipos, portales, etc. si quieres unos interiores optimizados(PVS, colisiones rapidas, etc...). En teoria podrias colocar un interior como un objeto más de del octree de objetos estaticos, siempre que controles bien como se verá desde "fuera" ese objeto(claramente deberias colocar una puerta para entrar/salir).

+ objetos estaticos "grandes": entidad que se pareceria, y mucho, al octree gastado para la geometria de escenario. Puedes dividir la geometria de tu objeto en otro octree que encierre solo tu objeto.

+ objetos dinamicos: yo utilizaria un kd-tree o adaptative octree. Cuesta aprender e implementar más cosas, pero seguro que se notaria en el rendimiento. Si quieres tener herencia debes contemplar que los objetos hojas deberian ser los nodos padres, no hijos sueltos. SI por ejemplo un personaje está en una subdivision pero su mano, con el arma esta en la contigua, (esta es mi opinión personal) yo colocaria una entidad padre(personaje) en las dos subdivisiones. Al dibujar debes saber que aunque veas las dos subdivisiones, solo debes dibujar una vez la entidad.

****** Ahora yo recorreria el grafo: --> si encontramos:

+ ESCENARIO EXTERIOR --> formado por octree ---> adelante, dibujalo.

+ Nodo CGS (transformaciones afines), nodo control, nodo LOD, --> ejecuta y continua con los hijos (en caso de LOD p.e. selecciona el tipo de entidad, etc.)

+ Nodo geometria ---> dibuja

+ Nodo octree para objetos --> (solo se me ocurre esto!!!!) puede que estos tengan diferentes materiales, etc. Podrias construirte un (mini grafo) asociando conjuntos de objetos que se determinan visibles o potencialmente visibles que compartan materiales y texturas para no tener que ir cambiando el estado constantemente (suponiendo que cada entidad que tenga hijos comparta materiales y texturas con ellos, solo incluye la entidad padre en el grafo) . Luego recorres este grafo y cada entidad se dibujará (si la entidad tiene hijos, estos se recorrerán, aplicando las diferente transf. hasta llegar a los nodos hojas y dibujarlos: como ves, si lo estudias y planificas, podrias tener jerarquias de objetos mobiles que estén referenciados en un arbol de partición).

**** Con las colisiones yo haria 3/4 de lo mismo: mirar que colisiones con geometria puedes tener mediante el octree para reducir calculos con poligonos no alcanzables desde tu subdivisión, y repetirlo en el arbol de objetos dinamicos y estaticos. Deberias integrar tu sitema de detección de colisiones o tener formas de obtener las estructuras de datos de los arboles de subdivision espacial desde tu modulo de fisicas o loqueseaquequierashacer.



BUffff... no se si te he aclarado algo. La verdad es que creo que podria ser bastante general y medianamente rapido, de todas formas hay cosas que me las he imaginado yo, no sé si hay formas mejor de hacerlo  :huh:

Puede que tb haya soltado alguna barbaridad, si es así, y alguien puede corregirme, que por favor lo haga y así a ver si aprendo un poquito yo tb. Lo unico seguro es que esto tiene que implicar un curro de 3 pares de c*j*n*s!!!!

Bueno ... animo, suerte y paciencia.
Salu2

Casi edit: a veces he puesto subdivisión y queria decir partición, que esto no te "ralle" más todavia.