Max -> Bsp

[BeRSeRKeR]

 Hola.

Estoy haciendo algunas cosillas con el sistema de particionamiento BSP. Seguramente os preguntaréis para qué demonios hacer uso de un BSP a estas alturas. Se supone que el BSP había muerto ya, ¿no?. :D

Bueno, la verdad es que creo que el BSP puede ser útil hoy día para ciertas cosas. Por ejemplo, imaginad el típico manchurrón de sangre que se queda marcado en la pared (decals). Es muy posible que el polígono con la textura de sangre sobresalga por alguna esquina. En una escena sin ningún tipo de coherencia geométrica, recortar dicho polígono creo que es bastante costoso en términos de tiempo (tendríamos que recorrer todos los triángulos de la escena y ver si están dentro del radio del decal y si es así, ver si cada uno de ellos intersecta con él). Con un arbol BSP no tendríamos más que ir recorriendo los nodos anteriores de la hoja donde se encuentra el decal e ir viendo si cada nodo intersecta con el decal. Si eso ocurre, se hace un split del decal y se elimina la parte que queda en la parte frontal del nodo.

Otra cosa de la que se podría beneficiar de un arbol BSP es la IA. Para un nivel como los que podemos ver en los quakes, doom3, y unreals, tenemos que las hojas del arbol forman un convex hull, es decir, podemos movernos de un punto a otro en linea recta sin preocuparnos de colisionar con nada (a no ser que sea un objeto dinámico que haya por ahí enmedio). Además, estos convex hulls forman areas que se podrían utilizar para calcular las rutas para los personajes controlados por la IA. Otra ventaja es que llevar a cabo el LoS (line of sight) es bastante rápido.

Pero ahora vienen mis dudas. ¿Pensáis que es buena idea calcular el BSP a partir de triángulos en lugar de polígonos?. Imaginad esta situación:



En la figura 1A tenemos el caso de utilizar triángulos. Tenemos dos triángulos que van a ser divididos por la línea roja. En la figura 1B podéis ver el resultado de la partición.  En negro tenéis las nuevas aristas que se han creado en la triangulación de los polígonos resultantes. Tras la partición, se han creado un total de 6 triángulos.

Ahora veamos el caso de utilizar un polígono (en este caso un "quad"). En la figura 2A tenemos el polígono y la línea que lo dividirá en dos polígonos. En la figura 2B vemos el resultado tras la partición. Como veis, tras la triangulación de los dos polígonos obtenemos un total de 4 triángulos, es decir, 2 menos de los que obtuvimos en el caso de utilizar triángulos. Ahora pensad esto mismo pero en el caso de existir unos cuantos cientos de miles de triángulos. ¿Cuántos triángulos podrían llegar a generarse tras la partición del espacio?.

Así que una cuestión queda en el aire. En el caso de utilizar triángulos, ¿es buena idea particionar o simplemente metemos el polígono que debería ser particionado en el nodo frontal y en el trasero del splitting node?. De esta forma el número de triángulos permanecerá igual y sólo tendremos que asegurarnos de sólo renderizar dichos triángulos una sóla vez. Evidentemente, una desventaja de ésto es que podrían haber polígonos muy grandes que procesarían pixel shaders (que podrían ser bastante costosos) sin ninguna necesidad.

Por lo tanto otra cuestión salta a la palestra. ¿Creeis que MAX/Maya/Blender/XSI/XXX son buenas herramientas para crear mapas que cumplan con los requisitos a la hora de generar un arbol BSP?. Aunque bien es cierto que al menos en MAX podríamos exportar el escenario a base de polígonos en lugar de triángulos pero aún quedaría el tema de los leaks o la geometría ilegal. Por ejemplo nodos cuyo nodo trasero apuntase a una zona vacía (transitable).

Bueno, a ver qué pensáis.

Gracias.

[senior wapo]

 Yo usaría polígonos en lugar de triángulos a menos que necesites disponer para algo de los bordes internos entre los triángulos que componian el polígono original. A mí no se me ocurre ninguna utilidad.

Sobre meter los polígonos enteros o dividirlos, va a depender de uso que le des al BSP y los algoritmos que luego trabajen con la información de la geométria, ¿ no ?
De todas formas siempre puedes elegir guardar en memoria tanto el poligono original, como los subpoligonos resultantes de las divisiones (con una referencia cada uno al polígono original y metiendo en el BSP solo los subpoligonos). Para operaciones cuyo coste sea proporcional la número de polígonos usas la referencia al polígono original (colisiones y distancias) y para operaciones cuyo coste sea proporcional a la extensión usas los subpolígonos.

¿Creeis que MAX/Maya/Blender/XSI/XXX son buenas herramientas para crear mapas que cumplan con los requisitos a la hora de generar un arbol BSP?. [...] aún quedaría el tema de los leaks o la geometría ilegal

¿ Es absolutamente necesario que no haya leaks, que las "hojas" definan espacios convexos y que definan el espacio sólido/vacio ? Porque tan BSP es uno que lo cumple como uno que agrupa sopas de poligonos (relativamente agrupados) a los lados de los planos de separación (y no requiere mallas especiales). Pierdes usos para el BSP,  si, pero para decals y colisiones valdría, creo yo. En lugar de usar los split planes para fragmentar el decal,  usas el BSP para consultar que poligonos tocan el BB del decal y luego calculas polígono a polígono.

Ya me dirás que te parece.

[BeRSeRKeR]

 

Yo usaría polígonos en lugar de triángulos a menos que necesites disponer para algo de los bordes internos entre los triángulos que componian el polígono original. A mí no se me ocurre ninguna utilidad.

Sí, realmente lo mejor es mandar polígonos en vez de triángulos. Lo de los triángulos lo decía por si en algún momento utilizamos otra herramienta de modelado que sólo exporte triángulos. En principio con MAX tenemos la posibilidad de exportar los polígonos.

Sobre meter los polígonos enteros o dividirlos, va a depender de uso que le des al BSP y los algoritmos que luego trabajen con la información de la geométria, ¿ no ?

La verdad es que aún no hemos decidido para qué cosas se utilizará el BSP. Sí pensé que vendría bien para el tema de los decals, o la IA. Para las colisiones utilizamos Newton que crea su propia estructura espacial.

¿ Es absolutamente necesario que no haya leaks, que las "hojas" definan espacios convexos y que definan el espacio sólido/vacio ? Porque tan BSP es uno que lo cumple como uno que agrupa sopas de poligonos (relativamente agrupados) a los lados de los planos de separación (y no requiere mallas especiales). Pierdes usos para el BSP,  si, pero para decals y colisiones valdría, creo yo. En lugar de usar los split planes para fragmentar el decal,  usas el BSP para consultar que poligonos tocan el BB del decal y luego calculas polígono a polígono.

La verdad es que estaba pensando en un BSP de tipo "solid-leaf" en lugar de "solid-node" que me imagino que es a lo que te refieres. El tema de los leaks creo que no sería un problema en el caso de no calcular el PVS pero aún estamos tanteando distintos métodos para la visibilidad, por lo que no tenemos muy claro lo que vamos a hacer. La idea es poder tener interiores y exteriores de foma sencilla y que cada uno sea administrado con su propio sistema de visibilidad. Así que había pensado en algo como portales para interiores y octree con algún sistema de oclusión para exteriores. Esa es otra de las razones por las que había pensado en un BSP ya que se podría utilizar para calcular los sectores (las hojas del arbol serían los sectores). Lo que pasa es que también está el tema de si generar los portales automáticamente o especificarlos a mano. Si se hace automáticamente el número de portales puede llegar a ser demasiado alto mientras que si se hace a mano, tendría que ver cómo calcular el BSP en base a eso. Me imagino que los portales se utilizarían como splitting planes. Pero vamos, ahora mismo no lo tengo claro.

En fin, como ves aún estamos en proceso de recogida de datos para al final poder tomar la mejor decisión posible. :)

Gracias.

[er_willy]

 
Con triangulos te ahorrarias crear exportadores/utilidades especiales y no habria problemas a la hora de crear niveles sin geometria ilegal, a los diseñadores de niveles los pondrias la mar de contentos (y se de que hablo).



bsp power  (ole)