Actualmente estoy programando una funcionalidad para el nuevo sistema de navegación 3D que hemos estado desarrollando ya por algunos años para un cliente. La funcionalidad que requiere el navegador 3D es realizar una búsqueda de objetos en la escena y desplazar la cámara de la posición actual a una posición cercana al objeto buscado, la cámara tiene que desplazarse por un espacio tridimensional y esquivar en su trayectoria a los objetos que se encuentren entre la posición de origen y la posición final, para hacer esto se requiere de una secuencia de pasos o sea de un algoritmo para calcular el mejor camino hacia la posición final. El algoritmo que utilice en la versión anterior y volveré a utilizar se llama “A*” o Algoritmo de búsqueda A estrella.
Este algoritmo “Evalúa los nodos combinando g(n), el coste para alcanzar el nodo, y h*(n), el coste estimado de ir al nodo objetivo: f*(n) = g(n) + h*(n)” .
Aqui hay muy buena información sobre A*:
http://www.policyalmanac.org/games/articulo1.htm
http://poiritem.wordpress.com/2010/01/14/6-5-2-busqueda-heuristica-algoritmo-a/
http://es.wikipedia.org/wiki/Algoritmo_de_b%C3%BAsqueda_A*
http://en.wikipedia.org/wiki/A*_search_algorithm
Lo interesante es que para el navegador 3D adapte el algoritmo para hacer las búsquedas en un espacio tridimensional, en la mayoria de los ejemplos solo se utiliza para espacios en 2D.
El primer paso es dividir el área de búsqueda en una rejilla cuadrada, donde cada cuadro representa un nodo y cada nodo tiene un estado que se puede marcar como transitable o intransitable, y sirve de entrada al algoritmo para calcular la ruta. En el caso del espacio tridimensional utilice un cubo para envolver toda la escena y se subdividió en cubos mas pequeños, luego los cubos que contenían vertices de algún objeto en la escena fueron marcados como cubos o nodos no transitables, de esta manera la camara solo podría moverse por las zonas que no estuvieran ocupadas por algún objeto en la escena.
En la versión anterior el cálculo se hizo recorriendo “todos los nodos” del volumen para verificar cuales eran los nodos intransitables, este cálculo se hacia con una aplicación de procesos distribuidos y tardaba un tiempo considerable para obtener la lista de nodos.
Para esta nueva versión del navegador 3D utilizaré una mejor manera para agilizar la búsqueda de nodos intransitables, y esta es utilizando un Octree. Y Que es un Octree???.
“Un Octree es una estructura de datos en la cual cada nodo interno tiene exactamente 8 hijos. Las estructuras octree se usan mayormente para particionar un espacio tridimensional, dividiéndolo recursivamente en ocho octantes” [1]
“Gráficamente podemos visualizar a un octree como un cubo perfecto que representa al nodo raíz el cual encierra toda la geometría de la escena. Cada nodo está subdividido en ocho cubos más pequeños que representan a sus nodos hijo los cuales son llamados octantes. Cada uno de estos cubos también es subdividido en otros ocho octantes cada uno y así sucesivamente hasta llegar a una condición de término a la que tipicamente se llega en el momento en que los octantes son de cierto tamaño o cuando no llegan a contener un cierto número mínimo de polígonos” [2]
“El primer nodo del árbol, la raiz, es un cubo. Cada nodo tiene ocho hijos o no tiene hijos. Los ocho hijos forman una subdivisión regular de 2x2x2 en el nodo padre. Un nodo con hijos es llamado nodo interno. Un nodo sin hijos es llamado hoja.” [3]
Algunos usos comunes de los octrees son:
Indexación espacial.
Detección de colisiones en tres dimesiones
Mapeado de texturas [3]
Análisis de elementos finitos
Determinación de cara oculta (View Frustrum culling) [2] (aqui hay una excelente explicación de la aplicación de octrees para el manejo de caras ocultas)
La idea de utilizar un octree para encontrar los nodos intransitables es para aprovechar la estructura y definición del octree para hacer un menor número de comparaciones al evaluar si un cubo o nodo en la malla esta ocupado o colisiona con un objeto de la escena, los nodos del octree que envuelvan a los objetos de la escena seran los nodos no transitables.
Mas información sobre octrees :
Hieralchical Spatial Data Structures
Hanan Samet 1989
http://www.cs.umd.edu/~hjs/pubs/SametSSD89.pdf
Referencias :
[1] http://es.wikipedia.org/wiki/Octree
[2] Tesis profesional Desarrollo de un motor gráfico para el recorrido de mundos tridimensionales :
Ricardo Hermina Téllez:
http://catarina.udlap.mx/u_dl_a/tales/documentos/lis/hermida_t_r/capitulo_4.html
[3] http://http.developer.nvidia.com/GPUGems2/gpugems2_chapter37.html
Imagenes :
http://www-lehre.informatik.uni-osnabrueck.de/~vcprakt/kolloquium00/html/octree.html
http://www.gamedev.net/topic/589587-optimizing-collision-detection-of-player-and-map-with-some-data-structures/
