Particionamiento Del Espacio

[tiutiu]

 Bueno, ya que el otro thread sobre scenegraphs no ha tenido exito, voy a ver si en este me llegan mas opiniones para decidir.
Al final he optado por tener una lista de objetos (prototipos) cargados en memoria, como un manager de recursos. Esto me permite tener instancias de los mismos para crear las vistas de la escena.
Una de esas vistas es la espacial, en la que tengo la organizacion jerarquica de las instancias en la escena.

Ahora tengo que decidir que estructuras usar para particionar el espacio y organizar la geometria.
Voy a separar la geometria en dos tipos: estatica, para geometria que no se mueve (no tiene nada que ver con animacion) y dinamica, para geometria que se mueve por la escena. Creo que tienen que estar separadas en diferentes estructuras, ya que tenerlo todo junto tiene bastantes inconvenientes.
Mi pregunta es, ¿que tipo de estructuras usais/usariais para cada tipo? La geometria estatica no necesita una ED optima en cuanto añadir/quitar nodos, simplemente ofrecer buen rendimiento al visitarla para culling o colisiones. La geometria dinamica necesita un poco mas de trabajo, puesto que cuando se mueve un objeto hay que recalcular la jerarquia de volumenes o incluso volver a añadir el objeto en el arbol para resituarlo en un espacio en el que quepa mejor. ¿Sugerencias?

[AK47]

 Saludos
Yo para la geometría estática uso un quadtree (para la escena en general), y pienso usar también los KD-Tree (para los pueblos que tendre sobre el terreno, es decir, para hacer culling de los edificios y objetos voluminosos).
En cuanto a objetos dinámicos pienso usar algo así como un KD-Tree dinámico a base de boundig spheres, recalculando las relaciones cuando se muevan los objetos. Esto último todavía no lo he implementado, así que no puedo darte consejos ni ideas  :ph34r:  

[Haddd]

 Nosotros desarrollamos un sistema de portales y un sistema de Octrees. Pero lo hemos desechado todo, nos proponemos utilizar sistemas de oclusión. Pero no hay nada todavía :(  

[tiutiu]

 Culling.
Supongo que usare un quadtree para objetos estaticos, ya me dio buenos resultados con un renderer de terrenos que hice hace tiempo, aunque tampoco probe otras estructuras para poder comparar :rolleyes:
Para objetos dinamicos creo que optare por un loose quadtree, aunque tengo que investigar mas sobre como funciona exactamente la (re)insercion o relocalizacion de los objetos al moverse. ¿Alguien lo sabe?
Basicamente el culling no necesita tanta optimizacion, puesto que solo se trata de comparar con el frustum y obtener un set de objetos visibles para animarlos/dibujarlos.

Colisiones.
Aqui ya hay que tener un poco mas de cuidado, puesto que el numero de tests es mucho mayor que para el culling. Tengo entendido que un kD-tree resulta realmente efectivo cuando hay muchos objetos (mas de mil) entre los que buscar. Para testear objetos dinamicos vs. estaticos puede ser una buena opcion. Sino se puede usar igualmente un quadtree.
Por otro lado, he estado mirando el metodo Sweep-and-Prune (SAP) usando un radix sort mejorado y me ha parecido genial. Este nos puede servir para buscar posibles colisiones entre objetos dinamicos.

Mirando en los foros de Gamedev he visto que hay quien separa los objetos dinamicos en 2 categorias mas aprovechando la coherencia espacial: dinamicos estacionarios y completamente dinamicos. Una puerta seria un ejemplo del primer tipo, ya que tiene el movimiento restringido. Un personaje seria del segundo tipo, ya que su movimiento no tiene limites (hasta cierto punto, claro). No se hata que punto resulta beneficioso hacer esta separacion :huh:  

[ajmendoza]

 Ahora mismo estoy haciendo un editor de terrenos grandecitos y para la representación por ahora utilizo Quadtree con occlusión dinamico a base de pantallas. Digo que por ahora porque no se si mantendré el quadtree (ya que el terreno se divide en zonas) o yo que se, como estoy aprendiendo nada está demasiado optimizado y mas tarde o mas temprano tendré q reescribirlo con los conceptos claritos.

Aun así, tengo que decir que no demasiado mal xD

[tiutiu]

Nosotros desarrollamos un sistema de portales y un sistema de Octrees. Pero lo hemos desechado todo, nos proponemos utilizar sistemas de oclusión. Pero no hay nada todavía :(

¿Y no podeis usar ambos sistemas y que se complementen? No creo que este reñido hacer una pasada por software para obtener una lista de objetos potencialmente visibles y luego otra de occlusion queries por hardware (o por software usando HOMs o alguna otra solucion).

Por cierto, estoy hablando principalmente de escenas de exteriores, nada de interiores. Aunque por otro lado, en interiores se estan desechando los BSPs (estilo quake y similares) a no ser en hardware 'antiguo', en favor de los octrees, ABTs o kD-trees.

[BeRSeRKeR]

 El sistema de portales lo quitamos de enmedio porque nos parecía demasiado restrictivo a la hora de dar libertad al grafista. El octree no recuerdo muy bien por qué se descartó.

Luego hice varias pruebas iniciales de occlusion culling utilizando HOMs y funcionaba pero aún quedaban muchas cosas por implementar como por ejemplo adquirir el mejor set de occluders.

De todas formas no sé hasta que punto sería ideal utilizar HOM en lugar de occlusion queries. Hay que tener en cuenta que si bien la generación del HOM es por hardware, luego la determinación de la visibilidad es por software (si no malinterpreté el algoritmo). :lol:

Saludos.

[tiutiu]

 Si, hasta donde yo se, los HOM son una solucion software. Solo se deberia usar si no se dispone de occlusion queries por hardware. Aunque tampoco habria que abusar de ellas para no sobrecargar la GPU.
¿No usais culling para obtener un set de objetos potencialmente visibles? Si es asi (deberia), ¿que estructura espacial usais para obtenerlo?

[BeRSeRKeR]

 Ahora mismo lo que tenemos es una jerarquía de bboxes que utilizamos para hacer el frustum culling y descartar geometría más rápidamente pero de todas formas eso dependerá de la profundidad de la jerarquía y por ahora la profundidad sólo suele ser de uno (utilizamos escenas muy simples donde no existen, por lo general, asociación padre/hijo) por lo que no hay demasiado beneficio en eso.

Saludos.

[er_willy]

 sin querer ser repetitivo  ¿cual es el objetivo del motor?
por que creo que normalmente es la pregunta que te hace decidir con mas facilidad.

[Haddd]

 El objetivo del motor es estar desarrollando un motor.  :blink:  Ahora sabemos muchísimo más que hace un año, cuando empezó, y es gracias al hecho de hacer un motor.

En el momento que se haga público...ya veremos que ocurre...No se cual será el objetivo... :huh:  

[tiutiu]

Ahora mismo lo que tenemos es una jerarquía de bboxes que utilizamos para hacer el frustum culling y descartar geometría más rápidamente pero de todas formas eso dependerá de la profundidad de la jerarquía y por ahora la profundidad sólo suele ser de uno (utilizamos escenas muy simples donde no existen, por lo general, asociación padre/hijo) por lo que no hay demasiado beneficio en eso.

Hummm, no confundas jerarquia semantica o logica con particionamiento espacial. Un quadtree te divide el espacio, no tiene que ser una BVH del scenegraph logico de la escena. Pero bueno, vosotros sabeis mejor que yo como son vuestras escenas :P

er_willy, no se por quien iba la pregunta, pero te respondo por si acaso. Es un motor para un juego de accion/plataformas (no demasiadas plataformas) simple en 3d, con escenas de exteriores. Mas que nada es para aprender y tener una base solida para futuros proyectos. Seguramente lo mismo que Haddd y berserker, aunque no pretendo hacer tantas cosas, querria terminarlo en menos de 6 meses :D

[BeRSeRKeR]

 No si nostros no tenemos particionamiento del espacio desde que descartamos los portales y los octrees. Eso lo dejamos para la próxima versión.

Saludos.

[raistlin]

 El tipo de juego que se haga dice mucho del sistema de oclusión a elegir. Yo pensaba que un octree es el más genérico, ¿existe algo mejor que funcione en cualquier tipo de escena (interiores/exteriores)?

[tiutiu]

 El mas generico suele ser el octree, o loose octree para objetos dinamicos. Os recomiendo la lectura de este thread en GameDev.

Luego esta el ABT, Adaptive Binary Tree, creo que Yann L habla un poco de él en ese thread. Es un arbol binario que elige el plano de particionamiento en funcion de unas heuristicas (funciones a minimizar) y permite guardar objetos dinamicos.
Aqui hay unos threads sobre ABTs para el que le interese:
ABT questions: construction and use
ABTrees questions
ABTs, relaxing them and other questions

Por cierto, de cada dia estoy mas seguro de que lo mejor es tener varias representaciones de los objetos de la escena, una para cada tarea: culling, colisiones y estados de render (aun se pueden añadir mas). Para el que le interese, esta pagina sobre scenegraphs esta muy bien.