AABB / OBB / Bounding Spheres y sus arboles

[soynegativo]

                                A ver que opinais sobre el coste de implementar estos tipos de estructuras y la calidad del resultados.

Tenemos que un Arbol de Bounding Spheres es muy facil de obtener, (incluso se puede construir en tiempo de ejecución), y es relativamente facil realizar operaciones de colision tanto a posteriori como a priori (antes del momento de colision, obteniendo en que momento se realizara la colision), en contra tiene que una esfera puede no aproximar muy bien un modelo como una espada o como un brazo. (se realizan raices cuadradas en los algoritmos de colisiones)

Los AABB son bastante mas faciles de construir, y el arbol muchismimo mas rapido de reconstruir cuando la jerarquia de objetos cambia, pero aproximan aun peor (si es posible) la geometria de un objeto, y ademas su volumen varia mucho cuando el objeto rota en cualquier eje.El calculo de colisiones es bastante simple tambien. (sin raices cuadradas)

Los OBB son los que mas aproximan la geometria real del objeto y rotan y se mueven junto con ella, sus desventajas son que aunque el calculo de colision a posteriori es relativamente "computable", las colisiones a posteriori son practicamente un infierno, con bastante computacion (sin raices cuadradas).

Alguien opina?


                               

[Emotion]

                                Pues mira, yo opino con lo de los OBB

Son Horribles!! y si no miralo en Metal Gear Solid. cuando apoyas a snake contra una pared muy cerrada respecto al angulo de camara, se ve que snake no esta apoyado, sino que esta separado de la pared, lo cual denota una falta de precision por parte del algoritmo (seguramente por el hecho de que la BB sea demasiado grande).

No obstante, es el mejor metodo que hay, ya que produce el mayor numero de resultados fiables (aunque tiene sus pros y sus contras, es como todo).

Saludos
                               

[Drácula]

                                ¿Qué es un OBB? ¿El Bounding Box del objeto?

Yo conocía las técnicas del arbol de BB o BSpheres.

Yo utilizo los BB. Aunque siempre he pensado que lo mejor sería utilizar un octree también para las colisiones. Sin embargo, no he implementado nada ( ¡siempre me falta tiempo!)
Pero también hay que saber con qué colisionan. En mi primera versión del motor, utilizaba un Quadtree que colisionaba sólo con un segmento. Ahí las colisiones eran muy rápidas. El problema está cuando queremos comprobar las colisiones triángulo a triángulo, que es la única forma de saber si dos objetos colisionan de verdad. Pero ..¿realmente hay que llegar a tal grado de precisión?
                               

[BeRSeRKeR]

                                OBB = oriented bounding box y supongo que con ello se refiere a que no está alineada con los ejes de coordenadas.

Otra técnica de la que he oído hablar es sobre la utilización de elipsoides (los cuales si se pueden adaptar mejor a ciertas geometrías) y para acelerar los calculos posteriores de colisión, se pasa todo a una nueva base para que dicho elipsoide pase a ser una esfera unidad...tal vez si en google pones "unit sphere" y "collision detection" encuentres algo.

Un saludo.
                               

[turrican]

                                En el MDK2 me parece que utilizaban cilindros para las colisiones de los personajes.
Creo que lo lei en gamasutra hace algun tiempo.

Salu2                                

[_Grey]

                                Pues lo de los cilindros parece bastante logico,si tenemos un juego de por ejemplo, futbol podriamos poner un circulo (NO UNA ESFERA) alrededor del personaje , y nos bastaria para que otro personaje no entrara "dentro de el", en un juego como Quake los personajes te pueden venir de arriba, asi que tambien se tendria que controlar en este caso la altura, un metodo facil y rapido.

Saludos.                                

[Emotion]

                                Bastante impreciso lo del cilindro, ya que si tu muñeco se tiene que arrimar a una pared, como no sea con la voluntad... :sonriendo:

Saludos
                               

[soynegativo]

                                Bueno,un bounding Cylinder es un buen objeto mientras no lo rotes, y la verdad es que tiene utilidad solo para englobar a un modelo completo (p.e. MDK2 lo usa para todo el modelo , no para cada una de sus partes).

Luego la colision dinamica (cuando digo colision dinamica me refiero a saber donde colisionaran y cuales seran los puntos de colision) entre dos cilindros que se mueven cuando su orientacion no es 0,1,0 me da hasta escalofrios :sonriendo:

Una cosa que hay que tener en cuenta es las finalidades que tiene el contruir un Bounding loquesea para un modelo, que son:
Resolución rapida de colisiones.
Resolución rapida de visibilidad (contra frustrum o lo que sea).

En ambos casos el usar un bounding (a partir de ahora B) no sirve para asegurarte que un objeto lo ves o colisiona , sino para todo lo contrario, es decir, para eliminar de tu lista de objetos los que no ves o no colisionan, es decir, sirve para descartar, no para asegurar.

Ahora me paro, pienso 30 segundos en el ultimo parrafo y yo llego a la conclusion que el hecho de que un arbol de B esferas es una buena aproximacion del problema, me baso en:

1.- No hay que rotarlas, solo mover el centro a medida que el modelo se mueve
2.- Los datos que hay que guardar de ella son el centro y el radio , 4 float (muy poco)
3.- Los algorimos para calcular sumas de esferas y cosas asi son bastante simples y de codigo bastante rapido
4.- Las colisiones dinamicas tambien son facilmente calculables


Que tal la idea:

- Contruir hibridos AABB con B Spheres:
por ejemplo, tener el modelo completo en un AABB y las partes interiores del modelo como B spheres, asi los descartes de colisiones en primer nivel serian mucho mas rapidas (choque rocket vs modelo completo) y las de segundo y n-esimo nivel mas aproximadas (choque rocket vs cabeza, rocket vs pecho)
y en el caso mas extremo, pues a colisionar triangulos contra triangulos.

                               

[alexglez1]

tambien hay compañias que para lo grar un grado de presision alto crean un quadtree con los OBB o AABB y desechan los nodos que van quedando vacios aunaque claro repito que eso es para un alto grado de presision como en simuladores querugicos por ejemplo pues esto consumiria muchos recurso.

   Alguien conoce algun algun algoritmo para crear en AABB o un OBB bien ajustado al cuerpo que deseamos englobar?????
 
 Saludos