Bsp tree octree alguna buena idea para cargar un mapa muy grande :D

[alberizo]

Wow, que bien suena esto de tener un espacio para videojuegos aquí, en Stratos no me deja crear un nuevo mensaje y es que llevo un par de años (en ratos libres eh sino ya habría desistido) intentando solucionar este problema, y es que tengo un modelo bastante grande de una ciudad y el motor que uso no soporta nada de árboles binarios, así que, me lo tengo que trabajar de alguna manera, las texturas también son grandes, porque necesito que tenga mucho detalle.

El caso que no consigo entender del todo los bsptres que era mi idea, así que, me las estoy ingeniando de alguna manera para cargar el mapa x sectores, pero sigo muy perdió, ahora lo tengo que cargue cada manzana si entra en el rango de visión de la cámara, pero entra dentro cada manzana individualmente (es decir, que al estar exportado cada manzana en un archivo independiente pues solo comprueba esa manzana, y si tiene alguna manzana x delante no la tiene en cuenta, con lo cual todas las manzanas que estén delante de mis narices, las carga, no me vale está solución, tengo algunas funciones para comprobar las intersecciones de linea-plano, pero me resulta algo complicado pami), el caso que también tenía pensado que cargue cada manzana (estoy pensando en exportar x fachadas, en vez x manzanas, pero esto va a ser muy engorroso de exportar, ya que manzanas son unas 30, y si le ponemos 50 fachadas x manzana, son 1500 manzanas, y una a una exportando es un coñazo, y como tenga que cambiar algo, esta es mi última posibilidad, cuando cargo el modelo, lo cargo sin textura para que sea más rápido, y las voy cargando en tiempo de ejecución, pero sigo muy perdió, no sé muy bien cómo hacerlo, si alguien sabe cómo solucionar mi problema estaría muy agradesio y sino pues lo tendré que hacer x fachadas.

Gracias anticip? S y saludos.

[HalfVector]

Nosotros nos tenemos que poner ahora con el sistema de visibilidad y el particionamiento para después poder generar la información necesaria para que los personajes controlados por la inteligencia artificial tengan conciencia del mapa y sepan cómo moverse por? L.

Como sistemas de particionamiento para la visibilidad de una ciudad podrías utilizar un Octre si la altura de la ciudad es grande y compleja (muchos polígonos que valen la pena ser descartados) o un quadtre si no te importa que se rendericen las zonas altas de la ciudad (porque tal vez sean pocos polígonos).

Evidentemente con un Octre o quadtre descartarías de forma rápida las zonas que no estuvieran dentro del frustum, pero, por ejemplo, se seguirán renderizando los edificios/objetos que estuvieran detrás de otros edificios, incluso estando los primeros totalmente ocultos por los últimos. En tal caso, se podría utilizar alguna técnica de oclusión junto con el quadtre/Octre. Una opción es utilizar las Occlusion queries que ofrecen las aceleradoras desde hace algún tiempo. Otra es utilizar algún algoritmo por software como pueda ser el hom (hierarchical Occlusion maps).

Hay más opciones. Por ejemplo, puedes utilizar portales y anti-portales. Si tienes la ciudad dividida en sectores, puedes crear portales en las conexiones entre cada uno de estos sectores. Estos portales conectan dos sectores. Entonces si estas en el sector 1 y dentro del frustum hay un portal, miras ese portal a que sector apunta (pongamos por caso el 3). Entonces creas un nuevo frustum en base a dicho portal y empiezas a recorrer todos los objetos del sectores 3 y sólo renderizas aquellos que están dentro de dicho frustum, es decir, todos aquellos objetos que se ven desde el portal. En fin, estoy describiendo muy básicamente el sistema estándar de portales. Luego tienes los anti-portales que como su nombre indica es justamente lo contrario a los portales. En este caso, los objetos que se vean a través del anti-portal, no se renderizar? N. Por ejemplo, puedes poner antiportales en los lados de los edificios. De esta forma podría descartar los objetos que hubieran detrás. Es una especie de oclusión.

En realidad, hay muchas posibilidades. Puedes mezlar distintos algoritmos de visibilidad para conseguir el mejor sistema para tu problema. Lo mejor es que busques más documentación sobre las cosas que te he dicho. Por ejemplo, tienes un paper titulado Occlusion queries made useful y había otro, que documentaba un sistema de visibilidad llamado dpvs y no encuentro ahora mismo, que hablaba sobre un montón de sistemas de visibilidad, tanto estáticos como dinámicos. La página web es ? Sta (busca dpvs: an Occlusion culling system for massive dynamic environments). Saludos.

[HalfVector]

Evidentemente otro truco que se viene utilizando prácticamente desde que los juegos 3d existen, es poner el far plane de la cámara lo más cerca posible. Con eso conseguirás descartar más objetos. Evidentemente el efecto colateral es que los objetos apareciendo/desaparecerán delante de tus narices conforme te acercas/alejas. Para evitar esto se suele activar la niebla, de forma que a la distancia en que los objetos empiezan a desaparecer no se vea nada, por lo que ese efecto molesto desaparecerá saludos.

[alberizo]

Cuando puse este mensaje, el primero que me vino a la cabeza fuiste tu half, gracias por la información, intentaré exarle un vistazo cuando sake algo de tiempo, la página tiene muy buena pinta, con esto del vertex Shader se hacen cosas impresionantes, tengo ganas de actualizarme de gráfica y probar vuestro motor, que quizás sería una opción para mí proyecto (para un organismo oficial) lo único que tendría que aprender c# aunque viniendo vagamente de pascal-div2-c-C++ no tendré problemas ¿verdad?
En cuanto a lo que comentaste de hom, me ha dado que pensar, hay alguna librería para hacer esto? (es que yo no soy programador básicamente y cuando me viene un problema de tal calibre se me viene el mundo encima y no me importa tener que tirar de librerías).

Los tipos de árboles binarios, más o menos los conocía, pero como toda la documentación que hay es en inglés, pues más problemas PAL bote, en cosas tan especificas me pierdo enseguida. Los portales los use en crystal space, y creo que serían más fáciles de implementar que un Octre, mirare esa posibilidad, de momento he encontrado a un conocido que se ha ofrecido para ver que puede hacer. Muchas gracias half, si conoces alguna buena página de esto en español te lo agradecería, aunque fuese algo básico, pero por lo menos para tener conocimiento de los tírminos específicos en español.

[HalfVector]

Tengo ganas de actualizarme de gráfica y probar vuestro motor, que quizás sería una opción para mí proyecto.

Como he dicho antes, ahora estamos con el tema de la visibilidad, así que, por ahora no es una opción para manejar niveles de cierta complejidad, ya que se renderizarían muchas cosas innecesariamente.

Lo único que tendría que aprender c# aunque viniendo vagamente de pascal-div2-c-C++ no tendré problemas ¿verdad?

Si sabes algo de C++ no debería costarte demasiado empezar a hacer cosas en c#.

En cuanto a lo que comentaste de hom, me ha dado que pensar, hay alguna librería para hacer esto?

La única librería que conozco que puede manejar escenarios grandes de forma dinámica es renderware dpvs e hybrid dpvs (la sección de productos parece estar caída ahora mismo). Pero no parece que ninguna de ellas sea gratu? Ta, al menos para uso comercial.

Los portales los use en crystal space, y creo que serían más fáciles de implementar que un Octre, mirare esa posibilidad, de momento he encontrado a un conocido que se ha ofrecido para ver que puede hacer.

Si tienes una herramienta que te particione el espacio en sectores y te genere los portales, después el render no es excesivamente complicado. El problema es ese, generar los datos necesarios, es decir, los sectores y los portales. Evidentemente puedes hacerlo a mano, pero es una faena bastante gorda. En cambio el Octre es más sencillo de generar. En cualquier caso, podría ser algo como la imagen que adjunto. Los rectángulos de colores son sectores (los blancos son edificios, pero también serían sectores) y las líneas rojas serían los portales. Evidentemente esto sólo vale si la ciudad es así de ortogonal, de lo contrario la cosa sería bastante chunga en el caso de tener que hacerlo a mano.

Otra forma de hacerlo sería utilizar el Octre y anti-portales. Así, recorrerías los nodos del Octre e irías descartando los nodos que estuvieran fuera del frustum. Entonces imagínate que en uno de los nodos te encuentras un antiportal. Lo que haces es crear un nuevo frustum en base a dicho anti-portal y todo lo que está dentro de ese anti-portal no se renderizaría. Como dije en el anterior mensaje, estos antiportales podrían estar en zonas cuyas posibilidades de ocluir a otros nodos del árbol fueran altas. Está claro que los laterales de los edificios serían una buena opción. Evidentemente esto te lo digo tal cómo se me está ocurriendo ahora mismo, pero ni siquiera sí si alguien ha utilizado esta mezcla de octres y anti-portales. Así que tampoco sí con que problemas te podrías encontrar.

Si conoces alguna buena página de esto en español te lo agradecería, aunque fuese algo básico, pero por lo menos para tener conocimiento de los tírminos específicos en español.

Sobre temas de particionamiento y visibilidad en castellano sólo conozco la de uno de los compañeros de Stratos. Puedes ver algunos tutoriales, aqué. Puedes mirarte? Estos dos:
determinar que hay en el campo de visión (frustum culling).
particionando el espacio con un Octre.

Lo cierto es que es complicado encontrar cosas en castellano. No sí si habrá algo de portales y de sistemas de oclusión lo veo aún más complicado.

En fin, como ves yo te doy ideas para que puedas seguir buscando alternativas, lo difícil corre a tu cargo. Saludos.

[alberizo]

/*----------- Soy un negado -*/.
pues nada half, debe ser que soy un negado o que me falta un peldaño para poder seguir, sigo sin saber cómo coger los escenarios binarios, creo que una cosa que me sacaría bastante de dudas y que tú dices que es la complicación, es el particionar el escenario.

Cansado de no enterarme de los BSP y octres y portales, me he cambiado de motor, pero sigo en las mismas, estaba optando x entrar de lleno con Ogre, pero estoy igual que con mi antiguo motor, como los uso.
/*---------- Scene manager de Ogre -*/.

En concreto en Ogre tiene, estoy viendo ahora mismo la Api de Ogre, vamos a ver, tiene una clase scenemanager y dos clases que heredan de ella bspscenemanager y octrescenemanager, bien pongamos que me decanto x Octre (los BSP han quedado un poco obsoletos ¿no?) pues eso, tiene el método:
Addoctrenode (octrenode*, Octre* Octre, int depth = 0).
/*--------- Nodos -*/.

Posiblemente ni hayas utilizado Ogre, pero supongo que, será generico en cualquier motor.

Un octrenode, bien es un clase, pero como viene definida? Y Octre otra clase, pero me pasa lo mismo, mi problema creo que están en los nodos. Los nodos donde los creo, cuando exporto la escena con el 3ds Max? Entonces necesito crearme mi propio exportador ¿no? O tendría que trabajar el cargar el mapa y dinámicamente crear nodos que solo existen en tiempo de ejecución.

Es que, aun no tengo muy claro el término nodo. A ver hago este ejemplo.

A ver, cada círculo seria un nodo ¿no? Y puedo definir seguir ampliando la profundidad hasta que yo quiera, ¿no? Cada nodo que propiedades tendría? Un identificador único supongo, y quien es su padre ¿no?
Y cuando llegamos a los nodos últimos almacenarán los polígonos de la escena, si? Uy como sea así, creo que me estoy respondiendo a mí mismo.

De momento esto, luego si esto es así, tendría que saber la pregunta que te hice, hago mi escenario, lo exporto en el formato que quiera, me creo una aplicación que lo carge, y luego lo exporto en mí propio formato en el que almaceno la información de los nodos y los polígonos claro, es así? Y luego en mí aplicación simplemente tendría que abrir este archivo e ir buscando nodos, y representando los polígonos. Pero bueno esto es otro tema con el que te daré el coñazo si me lo permites, lo siento half, soy un pesado, lo sé, solo soy un ignorante con ganas de aprender y sin nadie a las espaldas que me diga que voy bien, de sobra sabrás que la programación x autodidacta es una locura, y más cuando no ponen en los motores documentación. Saludos y gracias de ante mano.

[HalfVector]

En concreto en Ogre tiene, estoy viendo ahora mismo la Api de Ogre, vamos a ver, tiene una clase scenemanager y dos clases que heredan de ella bspscenemanager y octrescenemanager, bien pongamos que me decanto x Octre (los BSP han quedado un poco obsoletos ¿no?

Los BSP aún tiene sus usos, aunque para visibilidad yo creo que sí que están obsoletos. Pero, por ejemplo, acabo de terminar el núcleo del sistema de particionamiento espacial de nuestro motor. Está basado en portales/sectores para los interiores (para los exteriores me imagino que nos decantaremos por un Octre con algún sistema de oclusión) y una de las cosas que he hecho es crear un árbol BSP del nivel. Con ese árbol BSP se puede saber en qué sector esta la cámara, se pueden recortar volúmenes de sombra o, por ejemplo, también se pueden recortar los decals. Los decals son los típicos polígonos que se utilizan para trabajo cosas en las paredes. Por ejemplo, la mancha que deja un misil al impactar con la pared. Imagina que ese polígono sobresale por una esquina del mapa. Está claro que hay que recortarlo para quitar la parte que queda flotando. Pues eso, un BSP está bien para esas cosas. Para operación CSG son una maravilla.

En cualquier caso, para los exteriores los árboles BSP+pvs o los portales, no suelen ser una buena solución. Lo mejor es un Octre, sí.

/*--------- Nodos -*/.

Posiblemente ni hayas utilizado Ogre, pero supongo que, será genérico en cualquier motor.

Un octrenode, bien es un clase, pero como viene definida? Y Octre otra clase, pero me pasa lo mismo, mi problema creo que están en los nodos. Los nodos donde los creo, cuando exporto la escena con el 3ds Max? Entonces necesito crearme mi propio exportador ¿no? O tendría que trabajar el cargar el mapa y dinámicamente crear nodos que solo existen en tiempo de ejecución.

Pues no, no he utilizado el Ogre, pero efectivamente un Octre es un Octre en todas partes y las bases deben ser las mismas. Los nodos del Octre los puedes crear donde quieras. O bien te creas tu propio exporter y al exportar la escena generas el Octre y lo escribes en un archivo, o bien te creas una aplicación aparte que cargue la geometría contenida en un 3ds/obj/ase/etc y de ahí generas el Octre y los guardas en disco o bien generas el Octre cada vez que inicies el mapa. Evidentemente, lo mejor para reducir tiempos de carga es guardar el Octre en disco.

Es que, aun no tengo muy claro el término nodo. A ver hago este ejemplo: .

A ver, cada círculo seria un nodo ¿no? Y puedo definir seguir ampliando la profundidad hasta que yo quiera, ¿no? Cada nodo que propiedades tendría? Un identificador único supongo, y quien es su padre ¿no?
Y cuando llegamos a los nodos últimos almacenarian los polígonos de la escena, si? Uy como sea así, creo que me estoy respondiendo a mí mismo.

Ante todo he de decir que nunca he implementado un Octre (ya me llegara la hora) por lo que todo lo que te digo es de cosas que he ido leyendo a lo largo del tiempo.

Un nodo de un Octre contiene básicamente un puntero al nodo padre y un puntero a los hijos (que serán 8 hijos ya que el Octre se subdivide en 8 partes cada vez). Los nodos terminales (hojas), además, contienen polígonos.

Como explicar esto en 3d es algo complicado, lo explico en la versión 2d del Octre que es el quadtre. Mientras un Octre subdivide cada vez en 8 cubos, un quadtre subdivide cada vez en 4 rectángulos iguales.

Así que imagina que tenemos la siguiente escena:


Lo primero que hay que hacer es calcular el rectángulo que contiene todos los triángulos. Algo como esto:


Eso es el nodo raíz y a partir de ahí iremos subdividiendo hasta que se cumplan ciertas premisas. Normalmente, la subdivisión de un nodo se detiene cuando en su interior hay un número mínimo de polígonos. O también cuando el rectángulo tiene unas dimensiones mínimas.

Así que el siguiente paso es subdividir en 4 rectángulos iguales el nodo raíz. Recuerda que estamos hablando de un quadtre. En un Octre sería 8 cubos. La subdividir por primera vez tenemos esto:


Como todos los nodos tienen más polígonos que el número mínimo que especifiquemos, volvemos a subdividir cada nodo en otros 4 rectángulos de iguales dimensiones:


Ahora vemos que hay algunos nodos que tienen muy pocos polígonos en su interior, por lo que esos nodos no serán subdivididos. Ese nodo se denomina hoja y es la que contiene polígonos. Tras una nueva subdivisión, éste sería el resultado:


Como puedes ver, los nodos 1.4, 2.3, 2.4, 3.4 y 4.1 han dejado de subdividirse. El resto se ha vuelto a subdividir. En esa misma imagen puedes ver la estructura en árbol del nodo 1. No he puesto el resto porque era una locura.

Evidentemente, muchos de esos nodos volverán a subdividirse, mientras que otros contendran el número mínimo de polígonos y se detendran.

Hay una cosa a tener en cuenta y es el eterno dilema de si particionar los polígonos o no. Como es de esperar, habrán nodos que contendran parcialmente determinados polígonos. Hay dos opciones. O se parten dichos polígonos en dos y se manda cada mitad a su nodo correspondiente o bien el polígono completo se deja en ambos nodos. Evidentemente, a la hora de renderizar, hay que evitar renderizar dicho polígono dos veces. Para ello, a tu estructura de polígonos le puedes meter una propiedad frame. Entonces cuando vayas recorriendo el Octre para renderizar, para cada polígono, compruebas si la propiedad frame es igual al frame actual. Si no lo es, le asignas el frame actual a la propiedad frame y mandas el polígono a renderizar. De lo contrario, si el número de frame es igual, significa que ese polígono ya se ha mandado a renderizar, por lo que no hay que mandarlo otra vez.

Sobre si es conveniente o no partir los polígonos, yo prefiero no dividirlos ya que de lo contrario puedes acabar con un montón de splits y el número de polígonos de la escena pueden llegar a multiplicarse. Saludos.

[alberizo]

Wow tío como te lo curras, muchas gracias, no sabes lo que me a ayudado. Le daré vueltas, y primero intentaré implementar un algoritmo en 2d tal y como me as exup esto, y luego a dar el paso al 3d.

Muchas gracias.

[dryaner]

Vaya, me ha venido de perlas la explicación, porque estoy programando en Ogre (o intentándolo) y no sabía claramente que era un Octre, pensaba que era un formato de conversión de polígonos, pero especifico para Ogre y veo que es una cosa mucho más genérica.

Por cierto Halfvector te lo curras mucho, menos mal que no lo has tocado nunca que sino que habrías hecho. Saludos.

[HalfVector]

Es que hay tantas cosas que aprender y tan poco tiempo para implementarlas. Entonces de muchas de ellas conozco la teoría, pero en la mayoría de casos no las he implementado. En realidad, en temas de visibilidad sólo he implementado bsps y portales.

Pero bueno, si aun así logro aclarar algo a alguien, pues encantado. Saludos.

[davidnr]

Puedes utilizar un axis-aligned BSP. Sería como un Octre adaptativo, pero en vez de hacer adaptativo sólo el nivel de subdivisión, también se hace adaptativo el tamaño de las cajas en cada nivel del árbol, es decir, en lugar de dividir los nodos de 8 en 8 se subdividen por la mitad en un eje. El eje puedes calcularlo cambiándolo a medida que bajas por el árbol, x, nivel 1 eje x, nivel 2 eje y, nivel 3 ejez, nivel 4 otra vez el eje x. Una mejora es calcular en cada nivel en que dimensión interesa poner el plano de manera que, separe mejor los espacios vacíos de los ocupados. En Raytracing (que es donde lo he utilizado) se ha demostrado que es la estructura de datos óptima para la determinación de la visibilidad. Y en raster a primera vista yo creo que particiona el espacio de manera más eficiente que un Octre. ¿alguien con más experiencia puede decirme si estoy en lo correcto?
En realidad, un a-bsp es un caso concreto de los kd-tres. La diferencia consiste en que en los kd-tres el plano de partición de cada nodo no está necesariamente en el centro de la caja, sino que se calcula de manera que, particione el espacio de forma óptima. aquí tienes un documento sobre cómo generar kd-tres óptimos para Raytracing, supongo que, los principios serán también aplicables a raster.

No sé si se habrá entendido algo de todo este galimatías, si hay alguien realmente interesado puedo trabajarme un par de diagramas, explicando por que yo creo que es mejor que el Octre.