| Índice
I - Introducción.
II - La partición
del espacio aplicada a los juegos
III - Octree
IV - Acerca del ejemplo
- Mi Octree
V - Acerca del ejemplo
- Mi forma de dibujar el Octree
VI- Descargar el
ejemplo.
VII- Enlaces de
interés.
I - Introducción
La partición del espacio consiste en dividir el espacio de forma
recursiva. ¿Y esto para que sirve?, te preguntaras. Pues te lo explicaré
con un sencillo ejemplo;
Imagínate que quieres saber donde vive una persona. Tienes dos formas
de averiguar donde vive. Una consiste en ir casa por casa y preguntar
si allí vive esa persona. La otra consiste en dividir el espacio de
forma recursiva; primero dividimos el mundo en países, después en
provincias, luego en comarcas, en ciudades... etc. Así para localizar
la casa de esa persona, primero deberemos de saber en que país esta
la casa, después deberemos de saber en que provincia... etc.
En el primer método deberemos de hacer tantas comprobaciones como
casas hay en el mundo. En el segundo método deberemos de hacer "solo"
estas comprobaciones:
- Comprobar uno por uno todos los países hasta encontrar en que
país esta la casa que buscamos.
- Comprobar uno por uno todas las provincias del país en el que
se encuentra la casa, hasta encontrar en que provincia esta la casa.
- Comprobar una por una todas las comarcas de la provincia en la
que esta la casa hasta encontrar la comarca en la que esta la casa.
- etc...
En el primer caso el número de comprobaciones es muy superior al
segundo caso.
Así pues, la partición del espacio nos permite localizar las cosas
en un numero menor de comprobaciones.
II - La partición del espacio aplicada a los juegos
La partición del espacio aplicada a los juegos tiene el mismo objetivo
que en la vida real; permitir localizar cosas con un menor número
de comprobaciones.
Aunque existen varios usos para la partición del espacio, en los juegos
3D hay dos usos básicos: dibujar menos polígonos, y para reducir el
numero de polígonos a comprobar en las colisiones.
Puesto que tenemos el espacio dividido en zonas, podemos dibujar solo
aquellas zonas que están dentro del frustum.
Del mismo modo, si queremos comprobar colisiones, podemos realizar
las comprobaciones solo contra los polígonos de las zonas en las que
transcurre la acción.
Existen varios métodos de partición del espacio para juegos 3D:
BSPs (Binary Space Partitioning), Octrees, Quadtrees, KD-Trees, Portals
(Portales),...
Cada método tiene sus ventajas y sus inconvenientes. El ejemplo que
acompaña este artículo usa un Octree.
El ejemplo viene acompañado de un escenario de ejemplo en
formato X. Aunque se trata de un "terreno", los octree son
útiles para cualquier tipo de escenario. Existen métodos
de partición específicos para ciertos tipos de escenario (y
que no aceptan o no son recomendables para otros tipos de escenario).
Así por ejemplo, los quadtrees se suelen usar
para particionár terrenos, los portales se usan para
entornos cerrados (edificios),...
III - Octree
Imagínate un escenario 3D. Ahora pon ese escenario dentro de un cubo.
Ese cubo es el universo. :)
Ahora lo que hacemos es partir ese cubo por la mitad en sus 3 ejes;
con lo cual tenemos 8 cubitos del mismo tamaño. Cogemos cada uno de
esos cubitos y le hacemos lo mismo que al cubo original; lo dividimos
en 8 microcubitos. Y así vamos dividiendo hasta que nos cansemos.
Al final cogemos y guardamos una lista asignada a cada uno de los
microcubitos que tenemos, con los polígonos que se encuentran dentro
de cada microcubito.
Ahora imaginemos que queremos saber que polígonos hay cerca de la
cámara. Muy sencillo: comprobamos si la cámara se encuentra dentro
del cubo que habíamos llamado universo. Si se encuentra dentro, buscamos
la cámara dentro de cada cubito hasta encontrar en que cubito se encuentra.
Cuando hemos localizado en que cubito se encuentra, buscamos en
sus microcubitos hasta localizar en cual de ellos se encuentra
la cámara. Con unas pocas comprobaciones, tenenos el microcubito en
el que se encuentra la cámara. Y recordemos que ese microcubito tiene
una lista de los polígonos que hay dentro de él. Así que ya tenemos
una lista con los polígonos que hay cerca de la cámara!!!
A esta forma de división del espacio se la conoce como Octree.
Oct - porque de cada cubo padre obtenemos 8 cubos hijos. Y
-tree porque es un árbol jerárquico.
IV - Acerca del ejemplo - Mi Octree
La unit octree.pas permite crear un octree independientemente
del API grafico que estemos usando (es decir, independientemente de
si estamos usando DirectX, OpenGL, etc..) y de si la primitiva esta
indexeada o no. Esto se consigue gracias a que los triangulos se le
envian a la función octBuild mediante una función
callback (TOctGetTri) que debes de escribir. La función
octBuild llamará a tu función callback
cada vez que necesite que le proporciones un triangulo en concreto.
Cada nodo del octree contiene la siguiente información:
- Para navegar el arbol de forma jerarquica (father, sonID,
child) o de forma secuencial (prev, next).
- Dimensiones del cubo y su centro (aabb, center, size).
- Si se encuentra dividido (splited),es decir, si
tiene cubos hijos). En caso de que NO se encuentre dividido (nodo
terminal), también tiene una lista (itemData, itemCnt)
con las caras que se encuentran dentro (total o parcialmente) del
nodo.
- Los valores usrTagA, usrDataA, usrSizeA, ... no
tienen valores asignados. Su fin es que puedas almacenar en ellos
la información que quieras. La unit octrPV
almacena en esos valores datos necesarios para renderizar el
octree.
V - Acerca del ejemplo - Mi forma de dibujar el Octree
Para dibujar el octree uso una primitiva no indexeada y numerosas llamadas
a ProcessVertices. Así que no resulta un método recomendable
para las modernas tarjetas 3D que soportan transformación e iluminación
por Hardware (TnL HAL). De hecho el ejemplo esta diseñado para
mi vieja Voodoo Banshee, y es a ese tipo de tarjetas (HAL sin multitextura)
al que más partido le saca mi sístema de dibujado.
El proceso para crear los datos necesarios para dibujar el octree
es el siguiente:
- Primero hay que convertir el escenario en una primitiva no indexeada
(de esto se encarga la unit dx8noidx.pas.)
- Después creo el octree. (octBuild)
- octPV_Build se encarga de:
- Reordenar los triangulos de la primitiva no indexeada. El
criterio de ordenación es por Nodo (cubo del octree dentro
del cual se encuentra el triangulo) y por Subset (Material).
En el caso de los triangulos que se encuentren dentro de varios
nodos|cubos (shared tris), se les asigna el Nodo -1, así
que al ordenar los triangulos, todos los triangulos "shared"
(o compartidos) se encuentran al principio del vertex buffer
y ordenados por subset (material).
- Se crean buffers adicionales (usrDataA, usrDataB)
en los nodos del octree, que contienen la información
necesaria para poder localizar los poligonos que pertenecen
al nodo en cuestión. En usrDataA se almacena
la información para los triangulos que se encuentran
totalmente dentro del nodo (non shared), y en usrDataB
se encuentra la información para los triangulos compartidos
(shared).
- Finalmente la función crea un VertexBuffer de vertices
procesados. En este vertex buffer se almacenaran los vertices
que hayan sido procesados por ProcessVertices al llamar a la
función octPV_Process.
- Una vez creado los datos para dibujar el octree (mediante la función
octPV_Build ), se llama a la función octPV_Process,
la cual procesa (mediante ProcessVertices)
todos los triangulos que se encuentran dentro de los nodos que se
encuentran dentro del frustum. Una vez los triangulos han sido procesados,
se puede llamar a octPV_Render, para que dibuje los
triangulos.
- Podemos llamar a octPV_Render, varias veces (para
hacer multapasada por ejemplo) sin tener que llamar a (octPV_Process)
siempre y cuando la posición y dirección de la camara
no cambie.
En resumen,ctPV_Process procesa los triangulos que
hay en los nodos que hay dentro del frustum, y los guarda de forma
secuencial en un vertex buffer. Esos triangulos han sido transformados
(pasados del espacio 3D a 2D) e iluminados. Si la camara no cambia
de posición, esos poligonos son los mismos que hay que dibujar
en cada frame, así que no es necesario procesar el octree.
ctPV_Render simplemente envia esos poligonos ya transformados
a la tarjeta 3D.
La opción "Always Process Octree" del ejemplo, lo
que hace es llamar a ctPV_Process en cada frame, aunque
la camara no cambie.
VI- Descargar el ejemplo.
Descargar el ejemplo.
Para compilar este ejemplo necesitaras las
cabeceras de DirectX 8.0 para Delphi de Delphi-Jedi y el Delphi
4 o superior. La libreria D3DX8ab.dll se encuentra junto estas cabeceras.
VII - Enlaces de interes.
|
Para dibujar el octree uso una primitiva no indexeada y numerosas llamadas
a ProcessVertices. Así que no resulta un método recomendable
para las modernas tarjetas 3D que soportan transformación e iluminación
por Hardware (TnL HAL). De hecho el ejemplo esta diseñado para
mi vieja Voodoo Banshee, y es a ese tipo de tarjetas (HAL sin multitextura)
al que más partido le saca mi sístema de dibujado.
