Inserción de objetos dinámicos en OCTREES

[ALBSIM]

                                Hola, tengo un OCTREE con los datos estáticos de la escena, pero a la hora de insertar y mover objetos dinámicos, tengo que recaculcar en qué nodos se encuentran, tanto si son nodos hojas como en los nodos internos (ya que si ub bodo que no es hoja se encuentra completamente contenido en el interior de FRUSTUM, lo mando renderizar sin seguir visitando a sus hijos). Mi prugunta es la siguiente:
  ¿Qué método es el mas efectivo para realizar estos cálculos? Ya que si comienzo desde el nodo raíz, visitando recursivamente todos sus hijos hasta llegar a los nodos hojas, el algoritmo serñia muy costoso.
  ¿Hay algún algoritmo mas eficiente? E visto por ahí que se puede aprovechar el hecho de que los hijos tienen lados de longitud igual a la mitad de la de los del padre, y que sus centros se encuentran a:

                     CENTRO DEL PADRE +- LADO DEL PADRE/2

por cada coord. X,Y,Z.

  Si tenéis algo de cód. fuente o pseudocódigo mandármelo por favor.                                

[ALBSIM]

                                Perdón, creo que es:

CENTRO DEL PADRE +- LADO DEL PADRE/4

Y lo siento por escribir tan mal, soy un inútil del teclado                                

[CordayUK]

                                creo que meter objetos dinamicos en el octree no es muy buena idea ya que como bien dices hay que recrear el octree constantemente, no muy recomendable vamos :-?

que tipos de objetos dinamicos te refieres? mallas dinamicas como agua etc?? o objetos que solo cambian de posicion como coches, naves etc...?

porque no tener un puntero al nodo del octree en el objeto dinamico y solo actualizas este puntero? o tener un array de punteros a objetos dinamicos en cada nodo del octree?

asi puedes saber en que nodo se encuentra un objeto dinamico y aplicarle frustum culling o lo que sea....                                

[ALBSIM]

                                Si, tienes razón, yo me refiero a actualizar dicho array de punteros, es decir, si un objeto cambia de pos. su array de punt. a nodos en los que se encuentra ya no será el mismo, pero el problema es calcular todos los nodos en los que se encuentra para marcarlos con los nuevos punteros que formarán parte del array.
  Por último ¿Qué diferencia hay entre mallas dinámicas y obj. que cambian de pos? Yo los trataría de igual manera con una AABB lo suficientemente grande para que englobara los distintos cambios (frames de animación, deformaciones del agua...) y con esta AABB realizaría las comparaciones con los nodos del OCTREE                                

[CordayUK]

                                no he implementado todavia esto nunca :) pero se me ocurre hacerlo de la siguiente manera:

cada objeto dinamico SOLO puede estar en un nodo, con esto te evitas un monton de problemas. cada vez que mueves el objeto  averiguas en que nodo se encuentra el centro del bounding de dicho objeto. y anades a ese nodo un puntero al objeto, (y eliminas del nodo en el que estaba antes la referencia al objeto, ya que se ha movido)

Pero como los Bounding son bastantes grandes y lo mas probable es que un objeto este fisicamente en dos nodos. tendrias que chequear despues para cada nodo que tenga algun puntero objetos dinamicos si este objeto entra dentro o no del frustum.....y para las colisiones lo mismo.

alguno se le ocurre otra forma???

quizas puedes crear otro octree, con divisiones mucho mas grandes (mas grande que el mayor bounding box que tengas en la escena), pero que no contenga informacion sobre los vertices del terreno, solo maximos y minimos, este octree no dibujaria el terreno pero te valdria para clasificar rapidamente los objeteos dinamicos, no?                                

[ALBSIM]

                                Si, pero si el objeto está asociado a un solo nodo mas grande que su volumen acotante (AABB,OBB,etc.) Puede ocurrir que, por ejemplo, un objeto muy pequeño se encuentre ocupando la mitad de un lado del nodo raíz, y en vez de ocupar tan sólo un par de nodos pequeños, como queremos englobarlo dentro de un solo nodo, estaría asociado al nodo raíz y por lo tanto a la hora de testear colisiones lo deberíamos hacer con todos los objetos tanto estáticos como dinámicos del mundo, y si luego no lo seguimos asociando recursivamente a todos sus hijos, sólo renderizaríamos el objeto el la situación de que el nodo raíz entero fuera visible:

----|-----|-----|-----
|     |    ooo     |      |
|     |    ooo     |      |
|----|-----|-----|-----|
|     |      |       |      |
-------------------------
|     |      |       |      |
-------------------------
|     |      |       |      |
----|-----|-----|------

  No se si me entiendes, la verdad es que el dibujito es una jena (se supone que es un quadtree con un objeto insertado representado por os).
  Por otro lado, si asociamos al objeto sólo el nodo en el que se encuentra el centro de su AABB, y la AABB ocupa otros nodos, no calcularíamos las colisiones con estos otros nodos, y si alguno de éstos fuera visible, pero el que contiene el centro de la AABB no, no renderizaríamos el objeto (joder que lío)
  Ya se que me explico muy mal, pero espero que alguian consiga entender esta sarta de tonterías que acabo de escribir                                

[ALBSIM]

                                Vale, el dibujito no ha salido como yo esperaba, no le hagais ni caso, a la hora de escribir el mensaje se mostraba de otra forma                                

[ethernet]

intentalo con

q te queda el texto como estaba originalmente.

saludos

[_Grey]

                                No deberias mezclar el decorado estatico con los "personajes" que se van moviendo, para estos, deberias de calcular si son visibles al frustum de forma individual.

Saludos.                                

[ALBSIM]

                                Pero entonces ¿Cómo realizo los test de colisiones con el decorado si no se en qué nodos se encuentran los objetos móviles? Si tengo a los objetos dinámicos asociados con los nodos donde se encuentran, el nº de test de colisiones disminuye.                                

[_Grey]

                                El tema de las colisiones y la visibilidad es distinto, si lo que quieres es hacelerar los calculos de colisiones usando el octree que ya tienes para calcular las partes visibles, para calcular las colisiones de solamente los poligonos de ese nodo, me temo que tendras que aplicar tu primera idea con la que empiezas el post,buscar en el arbol el nodo en el que esta el personaje, ni mas ni menos, esto para calcular colisiones con el decorado, respecto a calcularlas con otros objetos dinamicos(otros personajes), yo lo haria pasando del octree, a no ser que el mundo sea TAN GRANDE y con TANTOS PERSONAJES,pero si quieres "asociar" esos objetos dinamicos con los nodos del octree, me temo que no te queda mas remedio, que hacer como dices, de visitar el nodo padre y ir visitando el resto..................                                

[ALBSIM]

                                Entonces ¿qué estrategia me aconsejais para realizar la detección de colisiones entre un objeto móvil y el mundo o entre dos objetos móviles?, es una tarea muy lenta y quiero utilizar un buen algoritmo que suprima el mayor número de test de colisión redundantes.
Gracias por tu respuesta, pero tío me has desanimao mazo  :( .
Estoy pensando en pasar de los OCTREES y liarme con SPHERE TREES o AABB TREES (joder a reescribir la mayor parte del código), ya que según tengo entendido son estructuras muy útiles para manejar mundos dinámicos, porque la inserción y borrado de elementos es muy eficaz
¿Estoy en lo cierto o acabo de soltar una parida de las mías?
¿Qué estructura es la mas apropiada para manejar un gran numero de objetos móviles?
¿Y qué me decís de loa árboles BSP para este tema? (creo que no son los mas adecuados, pero soy un ignorante y por eso hago tantas preguntas)                                

[_Grey]

                                Para el objeto movil y el mundo, puede estar muy bien ver en que nodo esta el objeto movil y calcular las colisiones solo con los poligonos de ese nodo, es posible que el objeto movil sea algo grande y caigo en un par de nodos o asi, y eso es algo que tendras que vigilar.
Para colisiones entre objetos moviles lo haria de forma directa, si tu mundo es tan grande y con muchos objetos quizas estaria bien distribuirlos por los nodos del octree como me pareces que inatentabas decir, pero dudo que no te sirva la metodologia que defiendo para este caso.

Lo de los AABB, no es mas que tratar a los objetos como cubos con lo que los calculos para detectar colisiones son muy rapidos, pero hasta ahora no he visto que los llamen AABB TREES............ lo que no quiere decir que la idea no pueda ser muy interesante..........

Respecto a los de las SPHERES TREES (??), creo que te intentas referir a un metodo muy similar al AABB pero en lugar de tratar los objetos como cubos, lo trata como esferas, lo cual lo hace ahun mas rapido....... pero tampoco los e oido nunco nombrar como SPHERE TREES.....

Para calcular las colisiones de un gran numero de objetos moviles, como pregustas, lo mejor seria usar los AABB o el metodo de las eferas.

Sobre los BSP, me tendre que matener al margen......... :oops:                                

[ALBSIM]

                                Los Sphere trees son tratados en un articulo del "Game programming gems 2" y creo que leí algo de los AABB trees en flipcode                                

[Findeton]

                                Y qué tal si en cada nodo de un octree metes una variable que sirva como puntero a objetos dinámicos, de manera que testees el nodo más pequeño que pueda contener el volumen que asignas a el objeto dinámico en cuestión cada vez q se mueve.

Es decir, en vez de calcular si un objeto dinámico está dentro de un nodo y si lo está, ver si está en sus subnodos y sucesivamente... porqué no testear mediante volúmenes? , ver si el volumen que ocupa el objeto dinámico (ya sea tratado como AABB, o como esfera, o como quieras) está dentro del primer nodo, y si lo está, ver si está en alguno de sus subnodos, pero esta vez, si está en varios subnodos, no atañirlo a los subnodos, si no está en ningún subnodo, atañirlo a ese nodo, y si sólo está en un subnodo, empezar todo el proceso de testeo pero con ese nodo.

No sé si me entendéis, yo no es que sea todavía un experto en estos temas, pero creo que es una solución al menos. Lo malo esque aunque te quita el problema de cuando está en varios subnodos, luego vas a tener que testear las colisiones con todos los polígonos de los dichosos subnodos. Sin embargo me sigue pareciendo un buén método, que hace que las cosas parezcan menos liosas, y creo que debe de ser un método eficaz para las técnicas de view frustrum, cosa importante.