Manejo de escena con Octree o Quadtree

[ZüNdFoLGe]

Hola, estoy un poco liado con este tema.

He decidido usar una estructura para el manejo de escena, tal como octree o quadtree (he descartado BSP por tema de simplicidad). Entiendo el concepto detras de esto, pero no lo he podido llevar a codigo.

Actualmente en el renderer lo que hago es renderizar cada componente de la escena invocando a su renderer concreto, es decir para cada objeto invoco un metodo render() donde renderizo el conjunto de triangulos correspondiente. Idem para el terreno (aplicando LOD, pero en definitiva se renderiza de manera similar a los objetos).

Como se supone que debo "particionar" estos conjuntos de triangulos para poder renderizar un subconjunto de ellos, dependiendo de donde este ubicada la camara?

Agradezco si alguien me puede aclarar esto, o si tienen algun link con algun ejemplo sencillo de entender.

Gracias de antemano

[XÑA]

Bueno, el quadtree divide el objecto en 4 partes, y luego va diviendo cada parte a asu vez, en 4 partes.
Luego sólo tienes que mirar qué BoundingBoxes ve la cámara y dibujar solo esos 'quads' que se están viendo.

El problema viene en que muchas veces los triángulos están en más de 1 quad, y aquí viene el problemilla, que ya depende de para qué lo necesites, creas una lista de triángulos, o los redibujas, o pasas de triángulos y usas el mesh completo.

[TrOnTxU]

El Quad te viene mejor para terrenos, si tienes ya un buen gestor del terreno, con métodos para descartar la geometria que no ves, no creo que te haga falta.

El tema de las particiones espaciales depende de como lo quieras hacer. El tema es simplificar el coste de comprobación de la visibilidad de un objeto sin tener que comprobarlo contra los planos del frustum de camara (que para una cantidad demasiado grande de objetos en muuu caro).

Yo personalmente trato de manera diferente los objetos estáticos de los dinámicos. La geometria estática corresponderia al "escenario".
Si tienes tu "escenario" como una sola malla (para mi no seria demasiado recomendable) deberias particionarla en "sub-mallas", de igual manera que si estuvieras dibujando "sub-mallas" de un mismo buffer de vertices por que tienes "sub-materiales" (es decir más de un material asociado a un buffer de vertices).
Si quieres que lo haga la construccion del arbol de particion (sea del tipo que sea) tu algoritmo deberia sacar los indices que corresponden a los "trozos" de malla que estas particionando. Aunque en mi opinión seria más conveniente, extraer los vertices (con sus propiedades de uv, etc) y generar nuevos buffers de vertices con las nuevas mallas.

Si quieres gestionar los objetos dinámicos, hay algoritmos un poco más complejos (kd-tree, una modificación del octree que no se como se llama ahora mismo, etc) que te permiten cambiar los objetos de nodos del arbol conforme se mueven, con menor coste que los arboles de particion "tradicionales", aunque y gastaria algun otro tipo de particion, como un "grid" modificable que tampoco recuerdo con exactitud, pero que te puedo decir que esta explicado en un Game Programming Gems (lo siento pero tampoco recuerdo el numero :( ).

Por supuesto, depende de como quieras tener tu scene manager. Si tienes un scene graph "tradicional", puede que todo tu gestor de escena deba de ser un octree, pero tambien puedes poner un octree como "nodo padre" de una serie de mallas u objetos, de manera que al hace el traverse de la escena y encontrar dicho nodo el dibujado de sus "hijos" se haria comprobando la visibilidad con el algoritmo de partición espacial.

No sé si me explico bastante claro, quizás no haya acabado de entender tu pregunta, asi que si te estoy soltando un rollo patatero y no te estoy ayudando dimelo, o concretame las dudas que intentaré ayudarte tanto como me sea posible.

Un saludo, y sigo currando, que con el cierre de la Alpha de aqui unos dias no deberia estar "foreando" ... pero la carne es débil que decia un tio con sotana.

adew