Organización Dinámica De Escenas

[Topper]

 Agradecería vuestra opinión sobre qué algoritmos son los más usados para la manipulación de escenas dinámicas para occlussion culling, collision detection, etc.

He visto por ahí alguno interesante como 'loose octrees'  :huh: , o incluso utilizar los bsp, pero me gustaría contrastar algo más con la experiencia de cada uno.

Saludos y gracias.

[CoLSoN2]

 Supongo que todo depende de las características de tu escena: usará terrenos? interiores? combinación de ambos? cualquier información adicional será de agradecer :P

[raistlin]

 Saludos:

El arbol BSP (Binary Split Partitioning) a diferencia del Octree y el QuadTree, pueden partir el espacio con planos no alineados a los ejes coordenados, es decir que se pueden usar planos en cualquier direccion. En este sentido los arboles Octales y Quadricos son una especializacion del BSP (el BSP es mas general que ambos). Por este motivo el BSP si es usado en Exteriores y tambien en Interiores. Si quieres usarlo para exteriores solo tienes que elegir planos alineados con los ejes coordenados y si lo deseas para interiores los planos son tomados de los poligonos estructurales.

En los BSP puedes mezclar escenas de interiores con exteriores facilmente. En todo caso para efectos de programacion la unica diferencia de un interior con un Landscape seria que no es necesario calcular PVS para el Landscape. Por lo demas las escenas mixtas son completamente normales y validas en un BSP.

El Octree es mas facil de programar que el BSP, tal vez esa sea la razon de que es mas usado, pero en realidad un BSP es mas poderoso, por muchas razones:

- Facil calculo de Portales y convex Hull: para path finding
- Acelera el Ray Tracing (para misiles o trayectorias y para calculos de Radiosidad)
- Collision Detection
- Facil y rapido Culling (BackfaceCulling y Frustum Culling)
- Adecuado para efectos en tiempo real ya que permite seleccionar los nodos en una esfera de influencia (Efectos de Luz, RealTime LigthMapping, Volumetric Fog)
- Back to Front Render: lo que permite calcular trasparencia y alphas sin esfuerzo.
- Constructive Solid Geometry (para hacer operaciones booleanas entre objetos cerrados)

El BSP puede ser usado como Octree o como Quadtree. Por su versatilidad es usado en casi todos los motores 3D de interiores y exteriores.

A mi manera de ver los BSP tienen pocas desventajas, la mas importante de ellas puede ser que solo sirven para estructuras y objetos estaticos (no es bueno con objetos dinamicos)

[Topper]

 

A mi manera de ver los BSP tienen pocas desventajas, la mas importante de ellas puede ser que solo sirven para estructuras y objetos estaticos (no es bueno con objetos dinamicos)

A eso voy Raistlin... lo que me interesa es más bien la escena dinámica que la estática (por el tema de realizar culling y colisión para el scenegraph genérico que estoy intentando hacer), y me imagino que en un bsp habría que reconstruirlo cada vez que un objeto cambia de lado del plano de partición, del mismo modo que en un octree habría que reconstruir buena parte de él si el objeto cambia del bounding box del nodo en el que se encuentra.  :ph34r:

Googleando he visto también algo sobre sphere trees para escenas dinámicas. A ver si encuentro un buen paper sobre él y me aclaro acerca de sus posibilidades.


Gracias de todos modos por la info.  ;)

[zupervaca]

 lo mejor para escenas dinamicas son los bsp, pero tienes que darte cuenta que lo movible son objetos y no parte del decorado, con esos objetos tienes que hacer colisiones contra mallas, lo mejor para que te hagas una idea de lo que diga es que te bajes el "quark army knife" que es un editor del quake3 y hagas que una pared se mueva y veras todo el efecto  ;)  

[Topper]

 Al hilo del post, y siguiendo con el tema de colisiones y culling: en juegos tipo RTS, las unidades (de soldados, etc.) se suelen tomar como un todo (un bounding box que alberga todos los miembros de dicha unidad) o por el contrario se gestiona cada miembro aparte?  :blink:

[raistlin]

 normalmente tienes una cGestoraDeUnidades que agrupa a cada cBicho que tengas creado.

Asi puedes permitirte crear formaciones, que si un bicho ha sido seleccionado el resto de su formacion aparezca tambien seleccionado, que si atacan a una de su grupo el resto la cubra, etc..

Piensa en POO:

COLEGIO -> CLASE -> ALUMNO
MUNDO -> ESCUADRON -> UNIDAD

es bueno tener una clase/objeto abstraida de lo que son las unidades, porque si un dia el objeto del marine que lleva el control de sus camaradas es destruido, que haces para seguir teniendo esa info? se la pasas a otro marine? eso no es nada recomendable, y ningun juego lo hace.

[zupervaca]

 aprovecho el post para preguntar como hace la mayoria de la gente para este caso:

· una luz proyecto sombra sobre un objeto no visible en pantalla pero resulta que la sombra que proyecto si deberia estarlo

· otro ejemplo seria con octree, resulta que uno de los nodos del octree no se tiene que renderizar, pero hay un objeto dentro de este que proyecta sombra sobre un nodo que si esta visible

[BeRSeRKeR]

 Así de buenas a primeras se me ocurre que si el tipo de luz es omni o spot, si hay sombra significa que el volumen de la luz también llega hasta ese punto por lo que estaría dentro del frustum de la cámara. Si eso es así habría que procesar esa luz y todo objeto que haya dentro de su volumen. Otra cosa serían las direccionales que en teoría no tienen ningún tipo de volumen.

Sólo es una idea.

Saludos.

[zupervaca]

 pero si hacemos eso tendriamos que calcular la proyeccion de la sombra aunque no estuviera visible, me explico otra vez por si acaso no lo hago bien:

· un octree tiene un nodo A y este a su vez tiene un nodo B no visible a su derecha que contiene en su interior un modelo 3d y una luz, esta luz proyecta una sombra que coincide que se proyecta sobre el nodo B y sobre el nodo A, pero al no estar visible el nodo B no se deberia calcular ni pintar nada relacionado con el


si calculamos las proyecciones de B no estando visible tenemos que pensar que el octree tiene mas nodos y muchos modelos 3d con lo que perderiamos muchos ciclos de cpu calculando proyecciones lo mas seguro innecesarias

ademas tenemos que pensar que unos nodos bien calculados de un octree no tienen que ser del mismo tamaño todos con lo que no podemos hacer que se calculen las sombras de los nodos mas cercanos a los visibles

podriamos calcular las dimensiones de las sombras usando el "bounding-box" del objeto y proyectando cuatro vertices para saber si la sombra esta o no esta visible, pero tendriamos que hacerlo a todos los objetos de todos los nodos igualmente, cosa que comeria mucha velocidad

pd: no estoy haciendo ningun proyecto ni nada, pero es algo que siempre he tenido en mente y ahora que las sombras empiezan a ser algo mas normal y no un simple pegote en el suelo la gente se encontrara con este problema lo mas seguro y puede que cuando compre tarjeta u ordenador nuevo yo tambien  :D  

[AK47]

 Saludos
Creo que el asunto de los objetos dinamicos se puede gestionar con los Loose octree o quadtrees. Yo tambien tengo que mirar estos metodos para mis cosillas.

[senior wapo]

 Sobre el tema del hilo: Un octree o un arbol RBtree con códigos Morton como clave de ordenación. No es ni de lejos tan eficiente como un algoitmo especializado (lease BSP para geometría estática) pero es que un problema tan genérico no da para más. Concreta más el tipo de escenario.


Sobre las sombras:
Si es un escenario de geometría estática, puedes preprocesar el nivel y crear un PVS (no necesariamente con un arbol BSP). Si el PVS indica que la luz está en un nodo no visible desde un nodo presente en pantalla, entonces su luz no ilumina la escena. La ventaja es que solo tienes que recalcularlo cuando la cámara cambia de nodo del mapa (coherencia temporal).

Además puedes mantener las luces móviles en una estructura espacial independiente y hacer culling más preciso de sus volumenes de luz, es decir, tener aparte un árbol/loquesea solo para luces. Recorres la estructura recolectando luces que interectan con el frustum y las combinas con la información del PVS.

Lo que vengo a decir es que la base de datos espacial de una escena no ha de ser necesariamente una sola estructura para todo, puedes tener un BSP para las colisiones con la geometría estática, grafos de "sectores" con portales para el render,  octrees/matrices para entidades o lo que sea...

[Topper]

 Buenas. Gracias a todos por vuestras aportaciones.

Veo que no he dejado claro el post en un punto: El SceneGraph. El caso es que estoy implementando (o al menos intentando  :P ) un SceneGraph, que lógicamente deberá tener posibilidad de gestionar entornos outdoor/indoor de geometría tanto estática como dinámica.

El mayor problema que tengo es en la organización de nodos (que permitan traslación, por ejemplo) del SceneGraph. Al no tener posición fija en el escenario, los algoritmos que he revisado normalmente no son buenos para este tipo de situaciones (bsp, octrees...) debido a que hay que reconstruirlos constantemente. Algunos de ellos necesitan una reconstrucción total y no lo veo muy recomendable para una aplicación 3D en tiempo real. Quizá me equivoque pero... :ph34r:

Pienso que la misma organización que tenga (hablando de objetos que cambian de posición) para un entorno outdoor, podría ser utilizada también para un Indoor, a sabiendas que objetos móviles que están en una escena indoor también lo están en una outdoor al mismo tiempo y podría utilizar la misma organización de datos para las dos escenas a la vez.

Pues eso, que si no me he aclarao lo intento explicar de nuevo  (nooo)

Saludetes pa tooos