Qbit Mexhico BlogLo que hacemos y pensamos se escribe aqui

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

         La actualización del entorno de escritorio GNOME 3.4, fue  lanzado el dia 28 de marzo , por la gente del proyecto GNOME.

GNOME 3.4 fue liberado después de  seis meses de desarrollo de su versión 3.2, con bastantes mejoras en diversas áreas, así como nuevas características y traducciones actualizadas.

Los principales objetivos de GNOME 3.4 fue mejorar los menús de aplicaciones  y acciones, para mejorar los paneles de Wacom y la Red, para volver a agregar alto contraste  y los temas de accesibilidad, y para mejorar la aplicación de los documentos.

GNOME Boxes es una nueva aplicación que ahora es parte del entorno de escritorio GNOME 3.4, permitiendo a los usuarios acceder a otros sistemas informáticos o imágenes virtuales.

Aspectos destacados de GNOME 3.4:

Documentos:

• Se ha quitado la barra lateral
• Nueva interfaz de búsqueda
• Se han añadido las colecciones
• Soporte para la impresión de documentos
• Menú  de aplicaciones

Contactos:

• Se ha añadido nueva barra lateral y el diseño de panel de contacto
• Se ha añadido un diálogo de una nueva conexión
• Añadido menú de aplicaciones
• Se ha añadido un nuevo selector de avatar

Boxes:

• Permite ver y acceder a máquinas remotas
• Permite ver y acceder a máquinas virtuales a distancia
• Posibilidad de instalaciones automatizadas completamente de Fedora  Linux, Windows 7 y Windows XP
• Capacidad para eliminar, publicar y cargar máquinas virtuales
• Posibilidad de conectarse a pantallas remotas utilizando VNC o SPICE

 Epiphany:

• Soporte para WebKitGTK + 1,8
• Nueva barra de herramientas de diseño
• Añadido menú de aplicaciones

Compartir y Disfrutar

C++ es mi lenguaje favorito. Por eso ademas de escribir en el quiero escribir sobre el, una forma de hacerlo es escribir sobre Patrones de diseño, que como seguramente ya sabes son formas de escribir código para resolver algún problema que se presenta con regularidad. Estos problemas son de desarrollo de software y no de algo aplicable directamente.

Es decir a veces el hecho de programar es por si mismo un problema, aqui es donde tienen utilidad los patrones de diseño. Veamos el primer ejemplo:

Seguro te haz topado con el siguiente problema, imagina que debes crear una clase que guarde en un archivo o en una base de datos lo que el sistema va haciendo, una especie de log, hay que tener cuidado de no instanciar mas de una vez la clase porque no queremos a dos objetos accesando a la vez al mismo archivo o BD, digamos que se ve mas o menos asi:

class log {
	public:
	log()
	{
		// Aqui abrimos el archivo o abrimos la conexion a la DB
	}
 
	virtual ~log()
	{
	}
 
	void Add(string Linea)
	{
		// Aqui almacenamos el texto en el archivo o la DB
	}
};

Tenemos muchas opciones para usarlo, por ejemplo podemos crear una variable global asi:

log MiLog;

en nuestro primer archivo digamos main.cpp y en cada archivo y clase que vallamos creando ponemos un:

extern log MiLog;

lo cual le indica al compilador que no valla a crear una nueva instancia de nuestro objeto MiLog, en lugar de ello use la primera instancia que se creo. Mmmm, funciona pero la variables globales no son muy bonitas, y son difíciles de mantener.

Tambien podríamos arrastrar la referencia a la variable por todos lados, pasándola como parámetro en cada función que vallamos creando, o como una propiedad de todas las clases que vallamos creando. Algo asi como:

void main (void) {
	log * MiLog = new log();
 
	MiFucion(5, "hola", MiLog);
 
	miclase MiClase(3.14, MiLog);
	MiClase.miMetodo(3);
 
}
 
int MiFucion (int Parametro1, string Parametro2, log * Milog) {
	MiLog->Add("Guarda este texto");
}
 
class miClase {
private:
	float Propiedad1;
	log * MiLog;
public:
	miClase(float Propiedad1, log * MiLog) {
		this->Propiedad1 = Propiedad1;
		this->MiLog = MiLog;
	}
 
	void miMetodo(int Parametro1) {
		MiLog->Add("Guarda este texto");
	}
}

Funciona, pero como ves hay que poner la referencia en todos lados, en cada clase y funcion en donde queramos ocupar nuestro log.

Otra forma de hacerlo es creando un Singleton. Un Singleton es una clase que:

• Solo puede instanciarse una vez.
• Solo tiene un punto de acceso a ella.

Es decir si nuestra clase log fuera un Singleton, solo se intanciaria una vez, con lo que  una y solo una instancia del objeto podría acceder a nuestro archivo o DB y ademas tendriamos un solo punto de acceso a ella, como si fuera una variable global, la cual no tenemos que arrastrar o pasar como parámetro cada vez.

Hay muchas formas de hacer un Singleton, sobre todo en C++.

La que mas me gusta es la siguiente, veamos el código:

class log {
public:
	static log * instance()
	{
		static log * Yo = NULL;
		if (Yo == NULL) {
			Yo = new log();
		}
		return Yo;
	}
 
	virtual ~log()
	{
 
	}
private:
	log()
	{
		// Aqui abrimos el archivo o abrimos la conexion a la DB
	}
};

Lo primero que hay que notar es como el constructor es privado, por lo que no podemos crear una instancia del objeto. Solo el mismo puede instanciarse . Luego hay que ver que hemos creado el metodo estatico intance() que retorna un apuntador de tipo log. Dentro hay una variable estática llamada Yo que, si recordamos como funcionan las variables estáticas, nos damos cuanta de que solo se crea una vez y el valor no se pierde. La primera vez Yo vale NULL y la instanciamos por primera vez, pero el resto de las veces Yo ya esta instanciada.

Nuestra clase Singleton se usa asi:

log::instance()->Add("Guarda este texto");

Tomando el ejemplo anterior se veria asi:

void main (void) {
 
	MiFucion(5, "hola");
 
	miclase MiClase(3.14);
	MiClase.miMetodo(3);
 
}
 
int MiFucion (int Parametro1, string Parametro2, log * Milog) {
	log::instance()->Add("Guarda este texto");
}
 
class miClase {
	private:
	float Propiedad1;
public:
	miClase(float Propiedad1, log * MiLog) {
	this->Propiedad1 = Propiedad1;
}
 
	void miMetodo(int Parametro1) {
		log::instance()->Add("Guarda este texto");
	}
}

¿Apoco no es mas padre que una variable global? O que andar llevando la referencia por todo el código. El Singleton en uno de los patrones mas utilizados y como comentaba hay muchas formas de hacerlos. No solo en C++ sino tambien en otros lenguajes. Dale un vistazo a la Wiki.

Compartir y Disfrutar

           A medida de que el poder del hombre ejerce control sobre la naturaleza, el medio ambiente que lo rodea se ve cada ves mas deteriorado, ya que el comportamiento que lo condujo a comunicarse por medio del lenguaje, y posteriormente formar su cultura le permitió adaptar al medio ambiente para su supervivencia, ya que “el hombre lo adapta según sus necesidades, pero para cubrir estas necesidades el ser humano no contemplo las conciencias del desarrollo industrial“, ya que este desarrollo lleva consigo crecimiento económico, pero por otro lado la perdida de los ecosistemas ya que donde antes era un área verde ahora es zona industrial.

En este pots se identificaran las causas y consecuencias de los desechos tecnológicos, que se están incrementando por el mundo globalizado en el que nos encontramos.

En la actualidad, la era de la tecnología y los avances tecnológicos especializados como computadores, celulares, teléfonos inalámbricos, aparatos para alcances medicinales y deportivos, televisores con alta definición, reproductores de música y de video; son los que logran el desarrollo humano de forma integral, posibilitando una mejor calidad de vida, logrando avances científicos y técnicos en la agricultura, medicina, arquitectura y otras ciencias que tienen como requisito la tecnología para desarrollarse.

Las TIC tienen gran marketing ya que hacen  posible la promoción de la publicidad en toda la sociedad, estas por medio de la televisión, la radio, la prensa realizan un impacto masivo para que a las personas les lleguen de una forma más directa el deseo de consumir cada día mas productos tecnológicos, convirtiéndolos dependientes de la vida cotidiana.

Pero ninguna de las campañas publicitarias o educativas realizadas por las industrias y el gobierno, aluden al hecho que al adquirir tecnología el consumidor esta en la obligación de obtener conocimientos técnicos para saberlos utilizar en una actividad específica y ambientales para saberlos reciclar; en el conocimiento técnico hay gran diversidad de instituciones y formas para aprenderlo, pero en el conocimiento ambiental no se ha creado conciencia para entender que es importante contribuir al medio ambiente, ya que esto es un beneficio para la sociedad.

 Consecuencias:

• Las personas utilizan los basureros comunes para arrojar estos peligrosos desperdicios, así se van contaminado los ríos y el medio ambiente, surgiendo graves enfermedades, afectando de una manera global la calidad de vida de todos los habitantes del mundo.

• Las TIC contribuyen al incremento de la contaminación con los desechos tecnológicos, pero a la vez pueden ser utilizadas para disminuir el impacto que tienen en el medio ambiente, reduciendo las emisiones de CO2, el consumo de energía, entre otros procedimientos que pueden realizar.

“El problema de la contaminación por los desechos tecnológicos es fundamentalmente la falta de conocimientos y el manejo inadecuado que los seres humanos han tenido con los aparatos tecnológicos,un mundo al que solo le interesa el desarrollo de nuevas innovaciones, pero quien no se preocupa por la calidad de vida que pueda tener a largo plazo si se sigue creciendo los problemas en el medio ambiente”

Compartir y Disfrutar