Octree

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.

Ejemplo de una escena dentro de un octree.

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/

Compartir y Disfrutar

Seguramente algunos de ustedes han visto algunas “etiquetas” ubicadas en la parte superior de algunos de los métodos o clases, principalmente cuando están implementando  algún Framework,  cuya funcionalidad de dichas “etiquetas”  es  es agregar cierto comportamiento de la clase dentro del framework.

Para mi sorpresa, dichas “etiquetas” no era lo que pensaba. A mi entender, son constructores de alguna clase que hereda de Attribute.

Veamos un ejemplo. Comencemos creando una clase “MyGridColumnAttribute”

Crear Clase tipo Attribute

[AttributeUsage(AttributeTargets.Property)]
public class MyGridColumnAttribute: Attribute
{
 
  private string _headerText;
  private bool _isHidden;
 
  public string HeaderText
  {
    get { return _headerText; }
    set { _headerText = value; }
  }
 
  public bool IsHidden
  {
    get { return _isHidden; }
    set { _isHidden = value; }
  }
 
  public PagingGridAttribute(string headerText, bool isHidden)
  {
    _headerText = headerText;
    _isHidden = isHidden;
  }
}

Un Par de Reglas

1. En la parte superior de la declaración de la clase se encuentra el atributo “[AttributeUsage(AttributeTargets.Property)]” la cual indica en que parte de la clases pueden ser implementado  ”MyGridColumnAttribute”. Para mas referencias diríjanse a la página de Microsoft.
2. El nombre de la clase debe de terminar con  Attribute (MyGridColumnAttribute).

 Utilizar la Clase Attribute

Ahora, es tiempo de utilizar nuestra recién creada clase. Para esto, debemos crear otra clase que llamaremos MyCustomDataSource:

public class MyCustomDataSource
{
  private string _firstName, _lastName, _nickName, _password;
 
  [MyGridColumnAttribute("Nombre", true)]
  public string FirstNombre
  {
    get{ return _firstName; }
    set{ _firstName = value; }
  }
 
  [MyGridColumnAttribute("Apellido", true)]
  public string LastName
  {
    get{ return _lastName; }
    set{ _lastName = value; }
  }
 
  [MyGridColumnAttribute("Clave", true)]
  public string NickName
  {
    get{ return _nickName; }
    set{ _nickName = value; }
  }
 
  [MyGridColumnAttribute("Contraseña", true)]
  public string Password
  {
    get{ return _password; }
    set{ _password = value; }
  }
}

Para aquellos que gusten cooperar con la causa, el siguiente paso es crear un componente que utilice “MyCustomDataSource” y lo muestre en alguna página Web.

Compartir y Disfrutar