alberizo

Woww, q bien suena esto de tener un espacio para videojuegos aki, en stratos no me deja crear un nuevo post y es q llevo un par de a?os (en ratos libres ehhh sino ya habria desistido :P) intentando solucionar este problemilla, y es que tengo un modelo bastante grande de una ciudad y el motor q uso no soporta nada de arboles binarios, asi q me lo tengo q currar de alguna manera, las texturas tb son grandecitas, xq necesito q tenga muxo detalle.
El caso q no consigo entender del todo los BSPtrees q era mi idea, asi q me las estoy ingeniando de alguna manera para cargar el mapa x sectores, pero sigo mu perdio, ahora lo tengo q carge cada manzana si entra en el rango de vision de la camara, pero entra dentro cada manzana individualmente (es decir, q 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 q esten delante de mis narices, las carga, no me vale esta solucion, tengo algunas funciones para comprobar las intersecciones de linea-plano, pero me resulta algo complikao pami), el caso q tb tenia pensado q carge cada manzana (estoy pensando en exportar x fachadas, en vez x manzanas, pero esto va a ser muyyyyyyyyyy engorroso de exportar, ya q 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 q cambiar algo ......... esta es mi ultima posibilidad.
Cuando cargo el modelo, lo cargo sin textura para q sea mas rapido, y las voy cargando en tiempo de ejecucion.... pero sigo mu perdio, no se mu bien como hacerlo........ si alguien sabe como solucionar mi problemilla estaria mu agradesio :D y sino pues lo tendre q hacer x fachadas
Grasias 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 IA 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 octree si la altura de la ciudad es grande y compleja (muchos pol?gonos que valen la pena ser descartados) o un quadtree si no te importa que se rendericen las zonas altas de la ciudad (porque tal vez sean pocos pol?gonos).

Evidentemente con un octree o quadtree descartar?as de forma r?pida las zonas que no estuvieran dentro del frustum, pero por ejemplo se seguir?an 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 quadtree/octree. 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 est?s en el sector 1 y dentro del frustum hay un portal, miras ese portal a qu? 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 post, el primero q me vino a la cabeza fuistes tu Half, gracias x la informacion, intentare exarle un vistazo cuando sake algo de tiempo, la pagina tiene muy buena pinta, con esto del vertex shader se hacen cosas impresionates!! tengo ganas de actualizarme de grafica y probar vuestro motor, q quizas seria una opcion para mi proyecto (para un organismo oficial :D) lo unico q tendria q aprender C# aunq viniendo vagamente de Pascal-Div2-C-C++ no tendre problemas verdad?
En cuanto a lo q comentastes de HOM, me ha dado q pensar, hay alguna libreria para hacer esto?? (esq yo no soy programador basicamente y cuando me viene un problema de tal calibre se me viene el mundo encima y no me importa tener q tirar de librerias)
Los tipos de arboles binarios, m?s o menos los conocia, pero como toda la documentacion q hay es en ingles, pues mas problemas pal bote, en cosas tan especificas me pierdo enseguida. Los portales los use en Crystal Space, y creo q serian m?s faciles de implementar q un octree, mirare esa posibilidad, de momento he encontrado a un conocido q se a ofrecido para ver q puede hacer.
Muxas gracias Half, si conoces alguna buena pagina de esto en espa?ol te lo agradeceria, aunq fuese algo basico, pero x lo menos para tener conocimiento de los t?rminos especificos en espa?ol.

__________________

HalfVector

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.

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

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.

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 octree 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 octree y anti-portales. As?, recorrer?as los nodos del octree 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 arbol fueran altas. Est? claro que los laterales de los edificios ser?an una buena opci?n. Evidentemente esto te lo digo tal como se me est? ocurriendo ahora mismo, pero ni siquiera s? si alguien ha utilizado esta mezcla de octrees y anti-portales. As? que tampoco s? con qu? problemas te podr?as encontrar.

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 ?stos dos:

Determinar que hay en el campo de visi?n (Frustum Culling)
Particionando el espacio con un Octree

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 f?n, como ves yo te doy ideas para que puedas seguir buscando alternativas, lo dif?cil corre a tu cargo... jeje

Saludos.

Miniatura de Adjuntos

 

alberizo

/*----------- SOY UN NEGAO ----------------*/
Pues nada half, debe ser q soy un negao o q me falta un peldaño para poder seguir, sigo sin saber como coger los escenarios binarios, creo q una cosa q me sacaria bastante de dudas y q tu dices q es la complicacion, es el particionar el escenario.
Cansado de no enterarme de los bsp y octrees y portales, me he cambiado de motor, pero sigo en las mismas, estaba optando x entrar de lleno con Ogre, pero estoy igual q con mi antiguo motor, como los uso.

/*---------- SCENE MANAGER DE OGRE --------------*/
En concreto en Ogre tiene ............. hmmm estoy viendo ahora mismo la API de ogre, vamos a ver, tiene una clase SceneManager y dos clases q heredan de ella BSPSceneManager y OctreeSceneManager, bien pongamos q me decanto x Octree (los bsp han quedado un poco obsoletos no?) pues eso, tiene el metodo:

addOctreeNode (OctreeNode*, Octree* octree, int depth = 0)

/*--------- NODOS ----------------------*/
Posiblemente ni allas utilizado Ogre, pero supongo q será generico en cualkier motor,
un OctreeNode, bien es un clase, pero como viene definida? y Octree otra clase pero me pasa lo mismo, mi problema creo q estan en los nodos. Los nodos donde los creo, cuando exporto la escena con el max? entonces necesito crearme mi propio exportador no? o tendria q currame el cargar el mapa y dinámicamente crear nodos q solo existen en tiempo de ejecucion,
es q aun no tengo muy claro el término nodo. A ver hago este ejemplo:
screen.width-255) {this.width=screen.width-255;this.alt='Full View';}" border=0>

a ver, cada circulito seria un nodo no? y puedo definir seguir ampliando la profundidad hasta que yo quiera, no? cada nodo q propiedades tendria? un identificador unico supongo, y quien es su padre no?
y cuando llegamos a los nodos últimos almacenarian los polígonos de la escena, si? uyyy como sea asi, creo q me estoy respondiendo a mi mismo
De momento esto, luego si esto es asi, tendria q saber la pregunta q te hize, hago mi escenario, lo exporto en el formato que quiera, me creo una aplicación que lo carge, y luego lo exporto en mi propio formato en el q almaceno la informacion de los nodos y los poligonos claro, es asi? y luego en mi aplicación simplemente tendria q abrir este archivo e ir buscando nodos, y representando los poligonos. Pero bueno esto es otro tema con el q te dare el coñazo si me lo permites , lo siento Half, soy un pesao, lo se, solo soy un ignorante con ganas de aprender y sin nadie a las espaldas q me diga q voy bien, de sobra sabras q la programacion x autodidacta es una locura, y más cuando no ponen en los motores documentación grrrrrrrrr
Saludos y gracias de ante mano.

__________________

HalfVector

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 octree con algún sistema de oclusión) y una de las cosas que he hecho es crear un arbol BSP del nivel. Con ese arbol BSP se puede saber en qué sector está 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 proyectar 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 operaciones CSG son una maravilla. :P

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

Pues no, no he utilizado el Ogre pero efectivamente un octree es un octree en todas partes y las bases deben ser las mismas. Los nodos del octree los puedes crear donde quieras. O bien te creas tu propio exporter y al exportar la escena generas el octree 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 octree y los guardas en disco o bien generas el octree cada vez que inicies el mapa. Evidentemente, lo mejor para reducir tiempos de carga es guardar el octree en disco.

Ante todo he de decir que nunca he implementado un octree (ya me llegará 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 octree contiene básicamente un puntero al nodo padre y un puntero a los hijos (que serán 8 hijos ya que el octree 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 octree que es el quadtree. Mientras un octree subdivide cada vez en 8 cubos, un quadtree 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 raiz 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 quadtree. En un octree 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 arbol del nodo 1. No he puesto el resto porque era una locura.

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

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 contendrán 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 octree 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.

Miniatura de Adjuntos

       

 

alberizo

Woww tio como te lo curras, muxisimas gracias, no sabes lo que me ha ayudado
Le dare vueltas, y primero intentaré implementar un algoritmo en 2D tal y como me as exupesto, y luego a dar el paso al 3D.

¡¡¡ Muxas gracias !!!

__________________

dryaner

wauuuuu, me ha venido de perlas la explicacion, porque estoy programando en ogre(o intentandolo) y no sabia claramente que era un octree, pensaba que era un formato de conversion de poligonos pero especifico para ogre y veo que es una cosa mucho mas generica.

por cierto HalfVector te lo curras mucho, menos mal que no lo has tocado nunca que sino que habrias hecho.

saludos.

__________________
un juego echo por y para los jugadores-->www.proyecto-x.net

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 aún asi logro aclarar algo a alguien, pues encantado.

Saludos.

davidnr

Puedes utilizar un Axis-Aligned BSP. Sería como un octree adaptativo, pero en vez de hacer adaptativo sólo el nivel de subdivision, también se hace adaptativo el tamaño de las cajas en cada nivel del arbol, es decir, en lugar de dividir los nodos de 8 en 8 se subdividen por la mitad en un eje. El eje puedes calcularlo cambiandolo a medida que bajas por el arbol, x. ej 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 qué dimensión interesa poner el plano de manera que separe mejor los espacios vacios 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 octree. ¿Alguien con más experiencia puede decirme si estoy en lo correcto?

En realidad un AA-BSP es un caso concreto de los kd-trees. La diferencia consiste en que en los kd-trees 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-trees óptimos para raytracing, supongo que los principios serán también aplicables a raster.

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