inmensia

Un vídeo de Hangar en acción.

Demo online:
http://inmensia.com/files/hangar/flight-gallery/index.html

Hoy he liberado los fuentes del último proyecto en JavaScript en el que he estado trabajando. Es un visor de modelos 3D almacenados en formato AC3D (.ac) que utiliza WebGL para renderizar. He estado utilizando modelos de aviones de FlightGear para probarlo, así que he decidido llamarlo Hangar.

He creado una pequeña página web con cuatro modelos escogidos de prueba. Tiene implementado un controlador a modo de trackball que permite rotar y ampliar los modelos utilizando el botón izquierda y la rueda del ratón. Necesita un navegador moderno como las últimas versiones de Chrome o Firefox para funcionar (Y no, IE 9 no es un navegador moderno)

El formato AC3D lo utilizan algunos programas como FlightGear, un simulador aéreo de código abierto, o Torcs, un simulador de conducción deportiva también de código abierto. Es un formato de texto plano que originalmente creó un programa de modelado 3D llamado, lógicamente, AC3D.

Mi idea era hacer algo sencillo, pero al final he acabado incorporando un montón de esas pequeñas características que pasan desapercibidas cuando funcionan bien.

AC3D
Los ficheros .ac tienen dos partes, la primera es una lista de materiales y la segunda una lista de objetos. Los materiales incluyen los típicos atributos para ambiente, emisiva, difusa, especular, brillo y transparencia. Los objetos son agrupaciones de entidades que reciben el nombre de superficies, aunque en realidad, además de polígonos, también pueden ser líneas simples o cerradas (el último punto se une con el primero). A mi me interesaban sólo los polígonos, pero al final he añadido soporte para representar las líneas también.

Los objetos están definidos de una manera jerárquica, de forma que un objeto puede tener hijos. Además, cada objeto tiene una matriz de rotación y un vector de rotación que aplica a sí mismo y a todos su hijos, por lo que hay que ir calculando la transformación resultante a medida que se baja por el árbol de descendencias.

Teselación
Debido a que para renderizar con WebGL es mejor tener las superficies divididas en triángulos, he implementado una versión en JavaScript de un algoritmo de teselación que soporta tanto polígonos convexos como cóncavos. Funcionó bastante bien casi a la primera, aunque haciendo pruebas detecté un problema con el orden en que devolvía los índices con modelos que tenían definidas las caras con los vértices en el sentido de la agujas del reloj, y que afortunadamente puede solucionar fácilmente. Me gustaría escribir en el futuro un post individual sobre este tema en particular.

Me he encontrado con modelos de todo tipo y definidos de casi cualquier forma. Al final he decidido ignorar los polígonos degenerados. Es decir, polígonos con menos de tres vértices, polígonos con coordenadas colineales, polígonos con vértices no contenidos dentro de un único plano, polígonos con aristas que se cruzan, ...

Normales
El formato del fichero no incluye normales, por lo que se calculan online mediante JavaScript. Por una parte la normal a cada superficie, para los sombreados planos. Y por otra parte la normal a cada vértice, para los sombreados más realistas.

La normal a un vértice concreto se calcula como la suma de todas las normales de todas las caras que comparten dicho vértice. Aunque a este respecto el fichero incorpora un parámetro por objeto llamado "crease". Este parámetro es un ángulo, y sirve para generar lo que habitualmente se conocen como bordes duros (hard edges). Si el ángulo que forman la normal de una cara y su vecina supera dicho parámetro entonces esa normal vecina no se tiene en cuenta para calcular la normal en el vértice compartido.

SGI
Bastantes modelos en formato AC3D utilizan texturas en formato SGI. Un formato antiguo que no soportan directamente los navegadores actuales. Una solución era transformar las texturas a .png, pero después de leer la especificación del formato me decidí a implementar también un lector de este tipo de imágenes en JavaScript, ya que el método de compresión que utilizan es un simple RLE. ¡Un proyecto dentro de otro proyecto!

Mi implementación soporta .sgi, .rgba, .rgb, .ra y .bw. Es decir, todas las combinaciones posibles, aunque he ignorado deliberadamente algunas características de la especificación, como la posibilidad de usar paletas de colores o escoger entre 8 ó 16 bits por canal. En la práctica todas las imágenes acaban siendo de cuatro canales y con 8 bits por canal en el clásico formato RGBA.

Loader
Para agilizar la carga y proceso de las texturas, que son binarias al contrario que los modelos que son de texto, he utilizado una de las nuevas características del objeto XMLHttpRequest de HTML5 que permite descargar un fichero directamente a un ArrayBuffer.

Muy útil.

Renderer
Como modelo de iluminación he utilizado una versión propia basada en el clásico de Phong con algunas modificaciones. Como los colores se me saturaban bastante debido a como están definidos por lo general los materiales he utilizado el valor de las texturas para ponderar la suma de emisiva, ambiente y difusa. De igual forma, para evitar los brillos exagerados he tomado sólo un 30% de la reflexión especular. Es más un modelo de prueba y error buscando un resultado agradable a la vista que uno realista. Es uno de mis puntos flacos.

El formato AC3D permite incluir luces en los modelos, pero las he ignorado a la hora de renderizar, utilizando en cambio una luz fija estática direccional sin factores de atenuación. Mi idea era representar modelos de objetos independientes, no escenas completas, por lo que no he encontrado sentido en incluirlas. Aparte de que acabado no fiándome de los modelos, con materiales un tanto extraños a mi parecer.

Para minimizar los cambios de estado de la tarjeta gráfica he agrupado todos los polígonos por programa, material, tipo, y todo lo que se me ha ocurrido. Por ello, a diferencia de otros proyectos anteriores, he decidido utilizar drawArrays en vez de drawElements para mi comodidad, aunque fuera a costa de repetir información al no utilizar índices.

Transparencias
Las transparencias han sido un dolor como de costumbre. Al final me he ceñido al guión. Primera pasada para los objetos opacos, con el blending desactivado. Segunda pasada para los objetos transparentes, con el blending activado y la escritura al depth buffer desactivada. Lo único que no he hecho es ordenar en profundidad, no me ha hecho falta en ninguna de las pruebas que he realizado.

Lo que me duele es que se supone, repito "se supone", que los materiales incluyen un atributo para indicar si tienen algún tipo de transparencia. Desgraciadamente esto no ocurre así en la práctica. Al final cuando algún modelo no se visualizaba correctamente, abría el fichero, localizaba el material y lo cambiaba a mano.

Esto es algo que en general creo que tendría que revisar con el objetivo de entender la manera en que interpretan los materiales programas como FligthGear o Torcs aprovechándome del hecho de que son de código abierto.

Autofit
Uno de los inconvenientes de hacer un visor genérico es que cada modelo viene posicionado y orientado según decidió su autor. Con centrarlos en el eje de coordenadas y alejarse una distancia prudencial prefijada no es suficiente, ya que depende del tamaño de cada modelo en particular. Para solventar este problema he implementado un auto-ajuste a la pantalla de los modelos basados en el tamaño de su bounding box.

De esto también me gustaría escribir un post individual en el futuro, ya que he encontrado distintas soluciones en Internet y no me he quedado del todo satisfecho con la que yo mismo he implementado.

TrackBall
Una vez dibujados los modelos lo lógico es poder interactuar con ellos. Ya había implementado anteriormente un simple controlador, cuando hice la demo de js-openctm, pero era un fake, así que esta vez he implementado un algoritmo de trackball de verdad. No quiero acordarme de las horas que habré perdido por culpa de esto. No es que no viera la solución, ¡es que no veía el problema!.

Resumiendo
¿Mucho tiempo invertido? Sí. ¿Suficiente? ¡Nunca!.

Una aproximación más práctica al problema hubiera sido utilizar un motor 3D ya existente, como el popular Three.js, y limitarme a hacer un conversor del formato .ac a algún formato que acepte el motor. Pero claro, ¡me hubiera perdido la parte más divertida!

Buscando información acerca de métodos de tracking (seguimiento) de objetos en tiempo real, me he encontrado que hay toda una teoría desarrollada para la detección de regiones dentro de una imagen que parezcan corresponder a piel humana. Hay muchas técnicas, pero las más sencillas parecen ser curiosamente las que mejor funcionan. Y básicamente consisten en convertir los pixeles originales desde RGB a otro espacio donde sea más fácil estudiarlos.

Al final he acabado montado mi pequeño "laboratorio" en JavaScript para comprobar una de estas teorías, concretamente la explicada en este paper que realiza el estudio de los pixels en el espacio de color YCbCr. Para ello he escrito un conversor de RGB a YCbCr utilizando las siguientes fórmulas propuestas en el documento:

Las fórmulas admiten un valor RGB dentro del rango [0, 1] y generan su equivalente YCbCr en el rango [0, 255]. La idea clave es que dentro de dicho espacio el color correspondiente a la piel humana se encuentra dentro del rango [80, 120] para la componente Cb y [133, 173] para la componente Cr. La componente Y simplemente es ignorada. ¡Veamos si es cierto!

Al seleccionar una imagen del desplegable de abajo se muestra tal cual arriba a la izquierda. En los cuadros inferiores se dibujan los histogramas calculados para las componentes Cb (en azul) y Cr (en rojo). Las zonas destacadas en amarillo son los rangos que se corresponden teóricamente a la piel humana. Y la imagen superior derecha es el resultado de filtrar la imagen original dejando pasar sólo los pixels que se encuentran dentro de los rangos que corresponden a la piel humana.

Después de probar con una serie de imágenes he dejado tres fotografías de caras a modo de referencia. La de Lucy Liu corresponde a un caso bastante claro donde está bastante diferenciado del fondo y el algoritmo hace un buen trabajo. La de Nicole Kidman se complica un poco, ya que el pelo tiene una tonalidad tan clara que no se distingue de la piel. Y por último la de Whoopi Goldberg, que se corresponde al caso en que el algoritmo se confunde debido al color que tiene la ropa que lleva puesta.

El programa permite cambiar los rangos haciendo click sobre los histogramas para desplazar los valores mínimos y máximos. Por ejemplo, para la foto de Whoopi, si se aumenta un poco el mínimo del histograma de la componente Cb (azul) entonces el algoritmo ya no detecta la ropa como piel. De igual forma, jugando un poco con los rangos es posible eliminar la mayor parte del pelo de la foto de la Kidman. Reconozco que el control con el ratón es un poco complicado, la idea es que se modifica el límite más cercano a donde se hace el click.

Otra posibilidad que ofrece el programa es seleccionar una región dentro de la imagen original para ver los histogramas de esa región en concreto. Por defecto está seleccionada la imagen entera, pero haciendo click sobre ella se puede definir una región rectangular. La idea es poder ver como se distribuyen los valores para una región en concreto con más detalle para tener un mejor criterio a la hora de modificar los rangos. Lo ideal es seleccionar una región que incluya sólo piel, con brillos y sombras, y ajustar los mínimos y máximos de los histogramas obtenidos. Pulsando escape se restaura la composición original.

Resumiendo un poco, está claro que el criterio es válido en términos generales, pero hay mucha probabilidad de falsos positivos en función de la condiciones del entorno en que se pruebe. Los pixels aislados no representan un problema, ya que normalmente se eliminarán aplicando una operación morfológica del tipo erode. Y de igual forma los huecos se rellenarán con una operación dilate.

Para mejorar el proceso de detección en general hay que aplicar más criterios, y así lo hacen generalmente las técnicas propuestas, normalmente el estudio de la imagen en algún espacio de color, como el YCbCr o el HSV por ejemplo, es sólo la primera parte del proceso. Algunas técnicas más elaboradas utilizan una imagen de referencia, a modo de calibración del sistema, con la que se construyen unos umbrales de referencia. Otros sistemas, sobre todo cuando se trata de procesar vídeo en vez de imágenes estáticas, ajustan los umbrales del los histogramas de forma dinámica en función de la variación que se va produciendo en las imágenes que se van sucediendo.

En otro orden de cosas, buscando más información por la red, he encontrado fórmulas de conversión de RGB a YCbCr más sencillas que las propuestas en el paper. Por ejemplo las siguientes:

Estas fórmulas tienen además la ventaja de que los valores de entrada RGB están dentro del rango [0, 255] en vez de [0, 1].

Los defectos de convexidad son importantes en la medida que se corresponden con ciertos puntos que caracterizan un determinado contorno. El ejemplo más clásico es el de una mano. Si se calcula la envolvente convexa que engloba el contorno de una mano y sobre ella se marcan los puntos que se separan más de dicha envolvente, para cada segmento de la misma, estos puntos se corresponderán con el nacimiento de los dedos, es decir, donde dejan la palma. Estos puntos son los defectos de convexidad, y permiten determinar de una forma muy sencilla algunas características concretas, como por ejemplo el número de dedos que tiene levantados la mano.

Siguiendo la implementación de la función cvConvexityDefects de OpenCV he creado un pequeño programa en JavaScript que calcula los defectos de convexidad. Para hacerlo un poco más atractivo visualmente le he dado forma de un pequeño generador automático de constelaciones.

El programa genera varios puntos al azar asegurándose de que forman un polígono simple, o dicho de otra forma, que no se cruzan sus líneas. A continuación calcula la envolvente convexa. Y por último los defectos de convexidad.

La zona azul claro corresponde al área cubierta por la envolvente convexa. Los puntos blancos con doble círculo son los que se encuentran sobre el borde de la envolvente, el resto está dentro de ella. Los puntos amarillos son los defectos de convexidad, es decir, los puntos más alejados para cada segmento de la envolvente.

Un experimento rápido y un poco tonto con js-aruco usando las sombras como marcadores de realidad aumentada.

Demo online:
www.inmensia.com/files/aruco/debug/debug.html