• Viernes 29 de Marzo de 2024, 16:50

Autor Tema:  Una Pregunta Sobre Los Bsp Tree  (Leído 1621 veces)

luzop

  • Nuevo Miembro
  • *
  • Mensajes: 16
    • Ver Perfil
    • http://www.mycgiserver.com/~luisopazo
Una Pregunta Sobre Los Bsp Tree
« en: Lunes 12 de Julio de 2004, 06:08 »
0
Hola.

He leido algunos articulos, visto algunos algortimos, he implementado algunas
cosas relacionadas con estos árboles.

En algunos me dice:
(al momento de la creación)
-Si un triángulo intersecta el plano, "cortar" este, y añadir los triangulos resultantes
  en el nodo correspondiente.

-Otro version me dice:
 Si un triángulo intersecta el plano, añadir a ambos nodos.

-Segun un libro que me llego hace poco, otra version es trabajar con "Objetos" , en  ves de triángulo por  triángulo.


Yo, según un artículo que encontre, almaceno en las hojas del árbol conjuntos convexos, o en su defecto, termino cuando se alcanza  algún número mínimo de
triángulos por cada hoja.


Mi duda es:
Para realizar detección de colision cámara-mundo(estático), cual es el algortimo
que debo usar.??

Yo he hecho pruebas con árboles OBB/elipoide(camara), BSP/elipoide(camara)
y funciona, pero me gustaría saber cual es la manera correcta.

gracias.

BlackWind

  • Miembro activo
  • **
  • Mensajes: 89
    • Ver Perfil
Re: Una Pregunta Sobre Los Bsp Tree
« Respuesta #1 en: Lunes 12 de Julio de 2004, 06:25 »
0
mmm... aun no llego a ese tema..
pero puedes checarte la pagina de gametutorials.com
 en la seccion de opengl, ahi vienen varios tutos sobre los bsp trees

Ruben3d

  • Miembro HIPER activo
  • ****
  • Mensajes: 710
  • Nacionalidad: es
    • Ver Perfil
    • Web personal
Re: Una Pregunta Sobre Los Bsp Tree
« Respuesta #2 en: Lunes 12 de Julio de 2004, 12:41 »
0
Hola.

En teoría, en cada hoja del árbol sólo puede haber conjuntos convexos de triángulos, para que se pueda pintar sin necesidad de Z-Buffer.

Durante la generación del árbol lo correcto es, si un triángulo es atravesado por el plano de partición espacial, partirlo y enviar cada parte al nodo que corresponda.

Si en la escena tienes objetos (imagina un adorno en una habitación) puedes computar en qué hoja del árbol estaría y pintarlo tras pintar esa hoja (gracias al back-face removal no va a ser tapado por un polígono de esa misma hoja). Si el objeto no se va a mover (es estático) podrías simplemente haber añadido sus polígonos al conjunto de polígonos del escenario y haber generado el árbol con él, pero esto es lento a la hora de comprobar colisiones.

Si no creas el árbol de esta manera te verás obligado a utilizar el Z-Buffer, ya que se pierde la propiedad de que todos los triángulos se pintan en orden de más lejano a más cercano (si estás usando una aceleradora gráfica puedes hacer la vista gorda, ya que el Z-Buffer por hardware es muy rápido).

Con respecto a las colisiones, te recomiendo que las realices empleando el árbol BSP, que ya lo tienes creado. Como has mencionado, calcula colisiones elipsoide/triángulo para cada triángulo y contra cada bounding box de cada objeto del nodo actual y para cada nodo en el PVS del actual (si no has calculado el PVS de cada hoja tras generar el árbol BSP no sé a qué esperas!).

Aqui tienes un par de enlaces que explican esto:
Binary Space Partitioning Trees FAQ
Binary Space Partitioning Trees and Polygon Removal in Real Time 3D Rendering

Espero que con esto te haya aclarado tus dudas.

Un saludo.

Ruben3d

luzop

  • Nuevo Miembro
  • *
  • Mensajes: 16
    • Ver Perfil
    • http://www.mycgiserver.com/~luisopazo
Re: Una Pregunta Sobre Los Bsp Tree
« Respuesta #3 en: Lunes 12 de Julio de 2004, 19:20 »
0
Bueno, solo llevo unos meses en esto de la programación en 3D, y me he
dedicado mas que nada a temas intersección entre objetos (empujar obstáculos,
 subir escaleras , no "atravesar" muros, etc), y algunas simulaciones de cuerpos
 rígidos (david baraff), proyectiles, puertas ..etc.

Asi que cuando me hablan de PVS, Portals, ...etc quedo pillo :blink:.
En parte por que no tengo mucha documentación (facil de leer) al respecto.
Lo más que he hecho para aumentar los FPS es "frustum culling" contra un
árbol OBB ó con un Octree.  

En todo caso, voy a guardar esta explicación para cuando
termine de investigar sobre colisiones  :)


Gracias.

Ruben3d

  • Miembro HIPER activo
  • ****
  • Mensajes: 710
  • Nacionalidad: es
    • Ver Perfil
    • Web personal
Re: Una Pregunta Sobre Los Bsp Tree
« Respuesta #4 en: Lunes 12 de Julio de 2004, 22:29 »
0
La mayor parte de la gente suele empezar por la determinación de visibilidad y dejar para después la física, ya que las optimizaciones de lo uno sirven para lo otro.

El PVS es el Potential Visible Set de cada hoja el árbol, es decir, el conjunto de hojas que pueden ser vistas desde cada una. Esto lo tienes bastante bien explicado en el segundo link que te he puesto.

Un saludo.

Ruben3d