inmensia

En mis últimos proyectos he venido utilizando gl-matrix, una librería escrita en JavaScript para operar con vectores, matrices y quaterniones. Es obra de Brandon Jones, un ingeniero que trabaja para el área de móviles de Motorola (no hace mucho adquirida por Google), conocido por su trabajo con WebGL, sobre todo por algunas demos de carga de ficheros, ya sean de modelos independientes o escenarios completos.

Empecé a utilizar la librería por la inercia de haberme basado en código copiado directamente de learningwebgl.com, que es la versión para WebGL de los clásicos tutoriales de NeHe para OpenGL. Y si bien me pareció una buena idea al principio, ahora ya no lo tengo tan claro.

Para realizar un par de operaciones con matrices, que es lo único que se necesita habitualmente para renderizar algo por pantalla, pues la verdad es que casi cualquier cosa sirve, incluida gl-matrix. Pero cuando se trata de realizar algo más elaborado enseguida se tropieza uno con ciertos aspectos de diseño de la librería que resultan bastante molestos.

La motivación principal de la librería es permitir trabajar con vectores, matrices o quaterniones utilizando el tipo Array clásico de JavaScript, o el más reciente ArrayBuffer si está disponible en el navegador, e incluso mezclarlos indistintivamente. Y sobre todo poder acceder a los elementos individuales de los arrays utilizando la notación clásica de corchetes con el propósito de aumentar el rendimiento al eliminar cualquier tipo de acceso intermedio y ser lo más transparente posible en su uso. El inconveniente es que para conseguir sus propósitos obliga a pagar un precio un tanto alto.

Veamos un código de ejemplo clásico para sumar dos vectores:

Lo que uno espera es a = b + c, pero lo que realmente ocurre es c = a + b. Resulta un poco confuso, pero consultando la documentación se aclara que es algo intencionado, y que por diseño el resultado se suele dejar por lo general en el último parámetro pasado a todas las funciones de la librería.

El inconveniente de esta solución es que dificulta la lectura del código si no se conoce la librería, resulta muy poco intuitivo. E incluso después de haber trabajado con ella es complicado, ya que también se dice en la documentación que el último parámetro de la función es opcional, por lo que el siguiente código es válido:

Lo que uno espera ahora es resultado = a + b, pero lo que realmente ocurre es a += b. Es decir, ahora recibe el resultado el primer parámetro y no el último. Una misma función que hace dos cosas distintas no suele ser buena idea, quizás lo mejor en este caso sería haber hecho dos funciones distintas, una para cada caso en particular en vez de basar su funcionamiento en la existencia o no de un tercer parámetro.

Incluso es posible escribir el mismo código de una tercera manera:

Lo que uno espera ahora intuitivamente es a = b + a, pero lo que se obtiene es a = a + b. El resultado final en este caso es el mismo porque la suma de vectores es conmutativa, pero para otro tipo de operaciones, como la multiplicación de matrices por ejemplo, que no es generalmente conmutativa, no se tendría el resultado esperado.

Un problema más derivado de este diseño puede verse en el siguiente código donde se intenta concatenar dos operaciones:

Lo que uno espera es resultado = a + b + c. Y es lo que se obtiene, pero tiene el feo efecto lateral de que el valor original del vector a se pierde. La forma correcta de escribir la expresión anterior sin perder ningún valor es introduciendo una nueva variable:

Pero realmente esa nueva variable es un artificio que la librería nos obliga a introducir, a nuestro programa no le aporta nada, y además dificulta la escritura de operaciones concatenadas como se observa en el siguiente código donde se han añadido la declaración de las variables necesarias:

Lo que uno espera es que el código anterior funcione, pero lo que ocurre ahora es que se produce un error en tiempo de ejecución. Y es que la librería espera además que la variable que almacena el resultado intermedio le llegue inicializada desde el cliente igual que el resto:

La clave está en que la librería evita crear cualquier tipo de objeto intermedio con el propósito de optimizar su rendimiento, delegando en el cliente la responsabilidad de instanciar la cantidad mínima necesaria de objetos intermedios que realmente necesite para el cálculo que pretende realizar. El problema es que a pesar de esto no consigue su objetivo, y no resulta más optima que otras librerías equivalentes según los tests de rendimiento.

Por otra parte, a estas alturas supongo que más de uno ya se habrá percatado por la nomenclatura de que la librería no crea ningún tipo de objeto a la manera clásica, con sus atributos y métodos, sino que más bien todos los métodos son expuestos públicamente de manera "estática", lo que obliga a escribir una y otra vez el tipo de los datos con los que se trabaja (vec3 en los ejemplos).

Esta última característica concreta del diseño lo utilizan bastantes librerías, pero tiene dos inconvenientes. El primero es que obliga a saber el tipo de la variable con la que se está trabajando en todo momento, en vez favorecer la abstracción y centrarse en la operación en vez del tipo de los operadores. Y el segundo es que si desea cambiar de tipo, para pasar de tres a cuatro dimensiones por ejemplo, entonces hay que realizar la sustitución en todo el código en vez de tan sólo en la declaración.

¡Demasiadas cosas en las que pensar para hacer una simple suma de vectores!

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!

PlayN es una librería multiplataforma de Google para desarrollar juegos. El nombre viene de "... for N>=4 platforms", aunque a día de hoy más bien es "N>=3", ya que sólo compila para Java, HTML5 y Android. La cuarta plataforma que faltaría es Flash, que está desarrollada, pero actualmente no funciona.

En la Google I/O del año pasado la presentaron con el nombre de "ForPlay":

Con el nuevo nombre de la librería hicieron hace poco una nueva presentación, entrando más en detalle con un ejemplo más concreto explicando como portaron "Angry Birds" a HTML5. No está colgada en YouTube, pero el vídeo y las diapositivas se pueden ver (no muy bien) en Angry Birds on HTML5. Para los que tengan curiosidad, el juego está online y se puede jugar en http://chrome.angrybirds.com/.

Respecto a la librería, comentar que está montada sobre GWT, por lo que el código se escribe en Java. Y a través de Eclipse, con los plugins correspondientes, se genera el código para la plataforma destino preferida. Ofrece una abstracción del bucle principal habitual de un juego, leyendo la entrada del usuario, actualizando el mundo y renderizándolo. Además de dar soporte para los componentes básicos, como gráficos, sonidos, red, física (Box2D embebido), gestión de recursos, ...

El proyecto está en desarrollo todavía, es ambicioso, y GWT no ha acabado de terminar de cuajar entre el gran público. En cualquier caso la idea no es mala. Pero es lo de siempre, un mismo código que pueda ejecutarse en todas partes.

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].