JavaScript

Juan Mellado, 24 Mayo, 2011 - 17:07

Los dos primeros pasos para localizar cuadriláteros candidatos que puedan contener marcadores son: convertir la imagen original a escala de grises, y crear una nueva imagen desenfocada. El primer paso tiene la finalidad de simplificar la cantidad de información a procesar, ya que en realidad los colores no son significativos para el proceso. El segundo paso se realiza con el objetivo de eliminar ruidos, aunque en realidad es sólo una parte de un proceso posterior que se explicará más adelante.

Escala de grises (Grayscale)
GrayscaleEl proceso de conversión de una imagen en color a otra en escala de grises es bastante conocido, todo un clásico dentro del mundillo del procesamiento de imágenes por ordenador. Consiste en recorrer todos los pixels de la imagen, y para cada pixel de forma individual multiplicar sus componente RGB (rojo, verde y azul), cuyos valores oscilan entre 0 y 255, por unos coeficientes y sumarlos.

Los componentes RGB originales del pixel se sustituyen por el valor resultante de esa suma. Los tres componentes con el mismo valor, para lograr así el efecto de escala de grises, ya que cuando los tres componentes tienen un mismo valor lo que se obtiene es un tono gris, excepto en los extremos, donde (0, 0, 0) es negro y (255, 255, 255) es blanco.

Los coeficientes que se utilizan normalmente son 0.299 para el rojo (R), 0.587 para el verde (G), y 0.114 para el azul (B). Si se suman los tres coeficientes se observa que el total vale 1 (= 0.299 + 0.587 + 0.114), lo que garantiza que el valor resultante de la suma de los productos por los componentes originales del pixel será un valor comprendido también entre 0 y 255.

En JavaScript se puede acceder a las imágenes a través del canvas 2D introducido con HTML5. La función "getImageData" devuelve un objeto "ImageData" que contiene un array que proporciona acceso directo a los pixels. Es un array plano que empieza con los componentes RGBA del primer pixel en las posiciones 0, 1, 2 y 3, continúa con los componentes RGBA del segundo pixel en las posiciones 4, 5, 6 y 7, y así sucesivamente. En nuestro caso concreto el componente A (alpha), utilizado para las transparencias, puede ignorarse tranquilamente, ya que no tiene sentido considerarlo para las imágenes típicas obtenidas de una webcam.

En la práctica, el proceso de conversión suele adquirir un aspecto similar al siguiente:

dst[j] = src[i] * 0.299 + src[i + 1] * 0.587 + src[i + 2] * 0.114;

Aunque es muy sencillo, hay un par de cosas a considerar. El primero es que no necesitamos realmente generar una nueva imagen con todos sus componentes RGBA, ya que no es algo que se vaya a mostrar por pantalla, excepto quizás para labores de depuración. Sólo necesitamos un componente de los cuatro, por lo que la cantidad de información a procesar se reduce al 25% de su tamaño original. El segundo punto a considerar es que este proceso hay que realizarlo para cada imagen, y que será más lento cuanto mayor sea la imagen. Una posible solución es utilizar imágenes más pequeñas a las originales proporcionadas por la webcam. Otras soluciones a estudiar son tratar de optimizar el cálculo precalculando los productos en una tabla, o incluso ejecutarlo mediante un shader utilizando WebGL. Pero hablar de estas cosas en este punto es cometer un error de "optimización temprana".

Desenfoque (Gaussian Blur)
Gaussian BlurEste segundo proceso, el de desenfoque utilizando un filtro gaussiano, es otro clásico. Buscando información me encontré una página que me gustó mucho por la gran cantidad de técnicas y efectos que aborda, y lo bien que están expuestos. Con un particular sentido del humor además.

Aplicar un filtro sobre una imagen normalmente consiste en recorrer todos los pixels de la imagen, y para cada pixel de forma individual aplicar una operación que genere un nuevo valor para el pixel. En nuestro caso concreto, para conseguir difuminar la imagen de forma coherente, lo que se utiliza como base para calcular el nuevo valor para cada pixel son los pixels más cercanos que tiene a su alrededor. Es decir, si tenemos un pixel negro rodeado de pixels blancos, lo que se quiere obtener es un nuevo pixel gris que difumine la imagen, eliminando ese "ruido" que representa el pixel negro aislado.

El proceso consiste es definir un tamaño de ventana, por ejemplo de 3x3 pixels, a cada celda de esta ventana asignarle un coeficiente numérico, y mover la ventana por encima de cada pixel de la imagen original de forma individual, multiplicando los coeficientes de la ventana por los valores de los pixels que cubre cada una de las celdas.

Lógicamente la gracia de todo esto está en los coeficientes que se utilicen. Para una ventana de 3x3 (= 9 celdas), si se utilizara un valor de 1/9 en cada celda se obtendría una nueva imagen donde cada pixel sería la media ponderada de todos sus pixels vecinos inmediatos (incluido el mismo). No obstante, parece lógico pensar que unos mejores coeficientes serían aquellos que dieran más importancia al pixel original, y fueran decrementado la importancia a medida que se fueran alejando de él. Y eso es precisamente lo que persigue el "Gaussian Blur", lo que consigue usando unos coeficientes que se calculan con la siguiente fórmula:

(1 / (2 * PI * sigma^2) ) * e^( -(x^2 + y^2) / (2 * sigma^2) )

Donde x e y son la distancia al pixel original, y sigma la desviación típica de la distribución gaussiana.

¿Asustado? ¡Bienvenido al club! No obstante, en la práctica resulta que no hay por que preocuparse por entender nada de esto. Como ya comenté en el artículo anterior, estoy siguiendo el código de ArUco para tratar de portarlo a JavaScript, y para obtener los coeficientes de la ventana, que técnicamente recibe el nombre de "kernel", se utiliza la función getGaussianKernel de OpenCV. Mirando en la documentación y el código fuente se ve que en realidad implementa una fórmula un poco distinta a la original, y que además, para ventanas de tamaño 3x3, 5x5 y 7x7 tiene unos valores precalculados.

Como ArUco utiliza una ventana fija de 7x7, entonces siempre utiliza los mismos coeficientes:

[0.03125, 0.109375, 0.21875, 0.28125, 0.21875, 0.109375, 0.03125]

De igual forma que en el proceso de conversión a escala de grises, se verifica que la suma de los coeficientes es igual a 1. Y como se observa los coeficientes centrales tienen mucho más peso que los de los extremos. Y aunque sólo he puesto una fila, en la práctica ha de verse como una matriz de 7x7 con los coeficientes distribuidos de manera uniforme alrededor del elemento central. Pero como se verá inmediatamente, el resto de coeficientes no son importantes.

Implementar el filtro resulta sencillo, pero muy lento, ya que por cada pixel hay que realizar 49 (= 7*7) multiplicaciones. No obstante, el filtro tiene una característica particular. Es un filtro "separable", lo que quiere decir que se puede aplicar en un primer paso en horizontal, multiplicando cada pixel sólo por la fila central de la ventana, y al resultado de ese primer paso aplicarle el filtro en vertical, multiplicando cada pixel nuevamente sólo por la fila central. De esta forma se reduce a 14 (= 7*2) multiplicaciones por pixel. Lo que de todas formas sigue siendo bastante trabajo para JavaScript dependiendo del tamaño de la imagen que se utilice. Sería interesante en un futuro probar con otro tipo de filtros, e incluso tratar de implementarlo en un shader mediante WebGL.

Por último, comentar que el filtro plantea un problema de implementación en los bordes, donde la ventana abarca pixels que no existen, y que se ha resuelto duplicando los pixels de los bordes para cubrir la ventana. Aunque existen otras estrategias posibles.

Actualizado 19/03/2012: Actualmente js-aruco implementa un Stack Box Blur que resulta más eficiente que el Gaussian Blur.

Realidad Aumentada
1. Introducción
2. Escala de grises (Grayscale & Gaussian Blur)
3. Umbralización (Adaptive Thresholding)
4. Detección de contornos (Suzuki)
5. Aproximación a polígonos (Douglas-Peucker)
6. Transformación de perspectiva (Homography & Otsu)
7. Detección de marcadores
8. js-aruco: Realidad Aumentada en JavaScript

Juan Mellado, 23 Mayo, 2011 - 18:04

Realidad AumentadaLas aplicaciones de Realidad Aumentada se han convertido en algo corriente hoy en día, sobre todo por el hecho de que prácticamente todos los dispositivos electrónicos que salen al mercado tienen algún tipo de cámara y cierta capacidad de proceso. Las demostraciones con esta tecnología suelen ser muy llamativas, y hacía tiempo que me picaba la curiosidad por conocer el detalle de la cadena completa de pasos concretos que se habían de seguir para hacerlas funcionar.

Al final he dedicado estas últimas semanas a leer un montón de documentación, mirar bastante código, y he acabado desarrollando una pequeña librería en JavaScript que casi implementa un sistema de Realidad Aumentada completo. Y digo "casi" porque me he encontrado con dos problemas que he dejado abiertos para resolverlos más adelante, el primero por una cuestión de índole puramente técnica, y el segundo por falta de talento. Pero vayamos por partes.

Me he centrado en la idea de averiguar como funciona un sistema ya implementado, en vez de estar reinventado la rueda. Quería que no fuese un sistema muy grande, ya que a medida que las aplicaciones empiezan a crecer puede resultar difícil entender su filosofía de funcionamiento, sobre todo cuando no se ha trabajado en la elaboración de las mismas. De hecho, a mi a veces me gusta descargarme las versiones más antiguas de los repositorios públicos en vez de las más recientes.

Otro requisito que quería que cumpliese el sistema es que utilizara los clásicos "marcadores", que son esas tarjetas tan características que llevan dibujadas algún motivo en blanco y negro. Y aunque por lo que he podido leer hay bastante interés en la Realidad Aumentada sin marcadores, a mi eso de las "tarjetitas" me llamó mucho la atención en su día y era algo que antes o después sabía que acabaría abordando, y esta era mi oportunidad.

ArUcoFinalmente he optado por ArUco, una librería bastante pequeña y con un código bastante fácil de seguir, ya que prácticamente todo el grueso del proceso está desarrollado en una única función. Un código con un estilo muy "académico" en realidad, y yo me entiendo cuando digo esto. Como curiosidad, comentar que es un desarrollo del grupo de investigación "Aplicaciones de la Visión Artificial" (AVA) de la Universidad de Córdoba (UCO). De aquí al lado, vamos. [La imagen está cogida de su web]

La librería es de código abierto, bajo licencia BSD, y está escrita originalmente en C++ apoyándose en OpenCV, una librería esta última con mucha solera y toda una referencia dentro del mundo de los desarrollos de todo tipo de aplicaciones de visión artificial. Después de haberme pasado unas cuantas horas buceando por su código he llegado a apreciar la cantidad enorme de trabajo que han debido invertir en ella.

Lo que más me enganchó de ArUco fue que entendí bastante bien la sencilla descripción que dan en la web acerca del funcionamiento de la misma. Sobre todo acerca del proceso de detección de los marcadores. Es la parte más "algorítmica", así que supongo que por eso me sentí más cómodo con ella y me animó a ir implementando paso a paso mi propia versión de la librería.

A grandes rasgos, he acabado dividiendo el proceso en cuatro bloques:

1) Captura de vídeo
Estoy trabajando con un PC de sobremesa, y lo lógico sería capturar vídeo desde una webcam, pero resulta que a día de hoy eso es algo que no se puede hacer de forma nativa en un navegador utilizando única y exclusivamente JavaScript. Aunque se puede hacer desde Flash, por ejemplo. Y de hecho, una de las librerías más populares para la creación de aplicaciones de Realidad Aumentada es una conversión a Flash de otra librería escrita originalmente en C.

Según he podido averiguar, dentro del estándar HTML5 están trabajando en exponer la función "getUserMedia" en JavaScript, que dará acceso a la webcam y cualquier otro tipo de dispositivo de vídeo o audio conectado al PC (tras la correspondiente autorización por parte del usuario). Pero todavía falta un tiempo para que los navegadores la implementen, así que he dejado aparcado de momento este tema del vídeo y me he centrado en procesar imágenes estáticas individuales.

2) Extracción de candidatos
Esta parte es sobre la que más tiempo he invertido. Para explicarla en pocas palabras bastaría con decir que consiste en analizar una imagen a la busca de cuadriláteros. Para explicarla con un poco más de detalle hay que explayarse en el cómo y porqué se realizan los siguientes procesos:
- Conversión a escala de grises (Grayscale)
- Eliminación de ruidos (Gaussian Blur)
- Umbralización (Adaptive Thresholding)
- Extracción de contornos (Suzuki)
- Aproximación a polígonos (Douglas-Peucker)
- Transformación de perspectiva (Homography)
- Umbralización (Otsu)

Mi idea es detallar estos pasos en artículos posteriores, sobre todo para que me sirvan como recordatorio a mi mismo.

3) Identificación de marcadores
Un vez extraídos una serie de cuadriláteros candidatos hay que averiguar si alguno de ellos es un marcador. Para ello se comprueba uno a uno si contienen una imagen válida reconocible como marcador.

En el caso de ArUco, no se utiliza una imagen libre cualquiera, sino un código binario dibujado en forma de una matriz de cuadrados de 7x7. Un 1 se representa con un cuadrado negro y un 0 con un cuadrado blanco. Intuitivamente debería resultar evidente que este tipo de códigos son más fáciles de identificar que una imagen libre cualquiera, además de que permiten añadir de una forma bastante natural bits de paridad para la comprobación de errores. De hecho, ArUco trata los marcadores que es capaz de identificar como un código Hamming, aunque bastante modificado para sus propósitos concretos.

Una vez entendida esta parte no me ha llamado tanto la atención, y he hecho un "port" casi directo del original a JavaScript. De hecho, cuando haga una limpieza de mi código, me gustaría tratar este proceso de forma independiente, como una función que se pase como parámetro, que admita un cuadrilátero candidato, y que decida si lo reconoce o no como marcador.

4) Traslación a tres dimensiones
Una vez identificado un marcador, lo más normal es calcular a continuación la posición que ocupa en el espacio con respecto a la cámara. O lo que es igual, la posición de la cámara con respecto al marcador. De esta forma se puede hacer eso tan característico de dibujar un modelo 3D sobre el marcador, consiguiendo además que se gire, acerque o aleje según se mueva el marcado o la cámara.

El problema es que esto no es algo inmediato. De hecho, el cálculo a realizar depende de las características físicas concretas de la cámara que se esté utilizando, pues hay toda una serie de parámetros intrínsecos como son el centro óptico real del sensor, las distancias focales en cada de unos de los ejes, y los factores de distorsión radial. Y esos parámetros, o se conocen, o es necesario obligar al usuario a que los obtenga de antemano de forma manual mediante algún programa que implemente un proceso de calibración.

Yo me había hecho la idea de que esto era más automático, pero parece que no. Esto de los parámetros y el proceso de calibración me ha matado bastante. Y de hecho no tengo ningún reparo es decir que además toda la matemática implicada ha conseguido liarme y no he conseguido sacar nada en claro. Se ha convertido en mi particular "pons asinorum".

Después de rebuscar entre un montón de documentación y unas cuantas implementaciones he decidido que este problema es lo bastante grande por si mismo para mi como para sacarlo aparte y tratarlo como una "mini-librería" con entidad propia. Trataré de retomarlo más adelante.

Para terminar, me gustaría dejar que claro que lo que describo en esta serie de artículos es una forma concreta de implementar las bases de un sistema de Realidad Aumentada. Pero no es ni mucho menos la única forma de hacerlo, ni probablemente la más eficiente. ArUco es un desarrollo totalmente ajeno a mi, pero cualquier error o imprecisión sobre ella en estos artículos son sólo atribuibles a mi persona.

Actualizado 19/03/2012: Actualmente js-aruco implementa un Coplanar POSIT que permite obtener la pose de los marcadores en tres dimensiones a partir de sus proyecciones en dos dimensiones.

Realidad Aumentada
1. Introducción
2. Escala de grises (Grayscale & Gaussian Blur)
3. Umbralización (Adaptive Thresholding)
4. Detección de contornos (Suzuki)
5. Aproximación a polígonos (Douglas-Peucker)
6. Transformación de perspectiva (Homography & Otsu)
7. Detección de marcadores
8. js-aruco: Realidad Aumentada en JavaScript

Juan Mellado, 23 Abril, 2011 - 12:19

Sigo analizando el rendimiento de js-openctm y tratando de ver donde puedo recortar un poco de tiempo de proceso. Después de realizar las optimizaciones obvias para reducir la cantidad y complejidad del código que se ejecuta dentro de los bucles más largos, he llegado al punto en que no encuentro forma de ganar una forma substancial de ciclos de reloj sólo y exclusivamente a base de realizar cambios en el código. Y es que definitivamente: ¡necesito un JavaScript ninja en mi vida!

El verdadero caballo de batalla es sin duda el proceso de descompresión, pero eso es harina de otro costal. En lo que me estoy centrado es en las funciones que tardan más, y más concretamente en la que se encarga de restaurar las normales. Si está leyendo este blog he de suponer que sabe lo que es una normal, pero por si las dudas, una imagen vale más que mil palabras. O al menos eso dicen.

WebGL - Drawing normals

En la primera imagen puede verse un render del dragón de Standford que he hecho dibujando las normales en cada vértice. Las normales son vectores que salen perpendiculares a la superficie, por lo que parece como si al modelo le hubiese salido pelo. En la segunda imagen he puesto una ampliación de la cola, que parece un cactus.

WebGL - Drawing normalsEl problema con las normales en OpenCTM es que resulta muy costoso restaurarlas, hay que hacer un montón de raíces cuadradas para calcular longitudes y normalizar vectores, y la función Math.sqrt es una total y absoluta "JavaScript perfomance killer". Sobre todo para modelos con millones de polígonos.

Además, analizando más en detalle el proceso. Resulta que hay algunas operaciones un poco discutibles. Por ejemplo, para restaurar las normales que vienen dentro de un fichero, el primer paso que se realiza es: ¡calcular las normales!. A ver si me explico. En el fichero vienen unas normales, pero no son las definitivas, sino que están almacenadas de forma relativa a las normales "nominales" del modelo. Así que para restaurarlas, primero hay que calcular esas normales "nominales". Siendo la normal "nominal" de un vértice la suma de todas las normales de las caras que comparten dicho vértice. Es decir, ¡las normales tal y como se han calculado toda la vida!.

La pregunta del millón es: si de todas formas se tienen que calcular las normales, ¿para qué queremos las del fichero? Pues la única explicación es que las normales que vengan en un fichero no tienen porque ser las mismas que las calculadas de la forma habitual. Para verificar este punto he tenido que ir depurando paso a paso un fichero concreto de ejemplo (en formato MG2, que no tiene porque almacenar con una precisión 1:1) y viendo los valores que obtenía por un procedimiento y otro. Y efectivamente, se obtienen valores distintos.

Por lo que a mi respecta, para mis propósitos concretos, no tiene sentido almacenar las normales en los ficheros. Sólo sirve para aumentar el tamaño de los ficheros y el tiempo necesario para descomprimirlos y procesarlos. Es mucho más rápido calcular las normales en el cliente. Además, el proceso que utiliza OpenCTM no es del todo eficiente. En un primer bucle calcula las normales que comparten un mismo vértice. Y en un segundo bucle las normaliza dividiéndolas por su longitud (raíz cuadrada al canto). El problema es que en el primer bucle también normaliza (otra raíz cuadrada al canto), cuando esto no es estricta y necesariamente necesario hacerlo. Y para rematar la faena, el proceso de restauración posterior implica realizar una nueva raíz cuadrada para cada normal.

Analizando lo que hace el proceso de restauración he conseguido reordenar el código para hacerlo más eficiente, detectando algunos casos especiales que he podido aislar en su propio flujo de ejecución de forma independiente. Un 30% de reducción de tiempo de proceso en general, que no está nada mal. No obstante, el cuello de botella sigue siendo el cálculo de las normales "nominales", que además no puedo modificar, ya que si lo hago se producen desviaciones con respecto a los valores que obtiene el SDK.

Así que al final, lo dicho: "No guardar las normales en el fichero, es mejor calcularlas online".

Temas: JavaScript
Juan Mellado, 22 Abril, 2011 - 16:23

Buscando alguna forma de mejorar el rendimiento de js-lzma se me ha ocurrido probar con un "minificador". Originalmente estos programas se utilizaban para ofuscar el código, pero a medida que las librerías escritas en JavaScript fueron creciendo se empezó a apreciar el trabajo que hacían reduciendo el tamaño final de los ficheros que los clientes tenían que descargarse desde el servidor. Hoy en día además tienen el valor añadido de que son capaces de evaluar el código y generar una nueva versión más óptima "en algunos casos".

He probado con el Closure Compiler, pero más allá de la reducción del código, y una ligera optimización debido a la reducción del nombre de los literales, no he visto ninguna gran mejoría en el apartado de rendimiento. Es más, confrontando el código original contra el minificado tan poco he visto cambios significativos. Eliminación de paréntesis innecesarios, alguna sentencia cambiada para aprovechar características particulares de JavaScript, y poco más. Tampoco esperaba milagros, ni aun siendo hoy Viernes Santo.

El tamaño del código se reduce hasta prácticamente un 50%, lo que está bastante bien. Así que en líneas generales se puede decir que el minificador hace realmente bien su trabajo. No obstante, antes de utilizar este tipo de herramientas es conveniente leerse la documentación. El principal problema es que a veces eliminan más código de la cuenta o no son capaces de compilar el código original por algún tipo de dependencia.

Por ejemplo, las interfaces públicas pueden llegar a desaparecer si no tenemos cuidado, ya que el minificador cambia el nombre a todos los objetos. En mi caso concreto, la librería se expone a través de una variable "LZMA", y para conseguir que se conserve ese nombre he tenido que añadirlo de forma explícita con la siguiente declaración:

window["LZMA"] = LZMA;

El minificador no cambia nunca el nombre de las propiedades a las que se accede por su nombre, por lo que el resultado final de la minificación es algo parecido a lo siguiente:

window.LZMA = g;

Siendo "g" (o cualquier otro) el nombre minificado de LZMA.

Otro punto a tener en cuenta son las interfaces de los objetos que no están declaradas dentro del propio código que se está minificando. Por ejemplo, en la librería se están utilizando objetos de tipo "stream" de los que se esperan que tengan implementados los métodos "readByte" y "writeByte". Eso no puede saberlo el minificador, por lo que genera un error al intentar compilar el código. Una solución sencilla es volver a cambiar el código de forma parecida al caso anterior.

Este código:

stream.writeByte(...);

Hay que cambiarlo por este otro:

stream["writeByte"](...);

De forma que en el código minificado se respeta el nombre de los métodos originales:

h.writeByte(...);

Resumiendo, útil para las liberaciones finales, pero hay que manejarlo con tiento.

Juan Mellado, 21 Abril, 2011 - 18:00

WebGL tiene una limitación en la función DrawElements por la que sólo se pueden utilizar buffers de 8 o 16 bits para los índices. Lo que implica que es necesario cortar las mallas con muchos vértices para poder representarlas. Ya tenía noticias de esta limitación, pero la verdad es que hasta ahora no me había importado demasiado. Me ha empezado a dar problemas en unas pruebas que estoy haciendo con js-openctm y ficheros con mallas muy densas.

WebGL - Split mesh Estoy haciendo pruebas con mallas de más de 1 millón de triángulos, y el problema es que cuando los índices superan el límite de 65.535 ya no se representan correctamente. La solución obvia es dividir la lista de índices en varias sublistas, ajustar los valores de las sublistas al rango 0-65.535, y realizar una llamada a DrawElements para cada sublista en vez de una sola con la lista original.

En la primera imagen de las tres que acompañan este post se puede ver el famoso "Happy Buda" de Standford, con 1.087.716 triángulos para ser exactos, tal cual lo estoy renderizando con WebGL en el navegador, y justo a su lado el mismo modelo, pero con un color distinto aplicado a cada una de las submallas que he tenido que generar para poder representarlo.

Cambiar la lista de índices originales no me parece algo trivial, ya que puede implicar tener que reorganizar los vértices, normales, y todos los demás atributos de la malla, con el consiguiente gasto de tiempo y reserva de memoria intermedia. E incluso en el peor de los casos puede que sea necesario duplicar vértices, ya que pueden darse situaciones en las que un triángulo tenga un vértice al principio de la lista y otro al final, y duplicar sea la solución más efectiva.

WebGL - Split meshMirando algunas implementaciones por ahí, he visto que algunos optan por cortar a saco, sin mucho miramiento, sin tener en cuenta los casos especiales y, para mi sorpresa, ¡les funciona!. El truco está en aprovechar la "coherencia" espacial de los modelos, en la distribución que normalmente tienen los triángulos dentro de la malla.

En la segunda imagen, con el Buda de perfil, se aprecia claramente porque no hay ningún problema en cortar la lista sin prestar atención a nada más para este modelo en particular. Todas las submallas contienen triángulos que están conectados unos con otros dentro de regiones muy claramente acotadas del espacio. En este caso, como los cortes de un sandwich helado.

Con los modelos propios, o con los que se puede suponer como estará organizada la malla, se pueden tomar este tipo de decisiones tan drásticas. Pero si se intenta hacer un visor genérico entonces si que sería conveniente buscar la forma correcta de hacer las subdivisiones.

Un hombre sabio dijo una vez que "los algoritmos son para la gente que no sabe comprar módulos de memoria", y yo no tengo palabras para explicar cuanta verdad encuentro en ello. Bueno, vale, la verdad es que eso de hacer algoritmos se me da muy mal y esa frase me sirve de consuelo. Incluso en esta era de Internet en la que se puede encontrar todo tipo de papers y código, me cuesta elaborar un algoritmo que me deje satisfecho. Y lo que es peor, que deje "satisfecho" al problema.

WebGL - Split meshAl final, he decidido seguir la corriente y olvidarme de los casos difíciles y cortar la malla con un sencillo procedimiento que no consume apenas tiempo y evita tener que reservar memoria adicional ni mover cosas de un lado a otro. Básicamente lo que hago es recorrer secuencialmente la lista de índices buscando un mínimo y un máximo, cuando la diferencia entre esos dos valores es mayor que 65.535 entonces guardo la posición en la que empecé a buscar, el número de elementos que llevo recorridos, el mínimo encontrado, y vuelvo a empezar la búsqueda desde el punto en que me encuentro repitiendo este sencillo proceso hasta haber recorrido toda la lista.

Al final lo que obtengo como salida del proceso anterior es un array con tres valores para cada una de las submallas. A saber, la posición del primer índice de la submalla, el número de índices de la submalla, y el valor a restar a cada índice de la submalla para dejarlos en el rango 0-65.535. El valor a restar evidentemente es ese valor mínimo encontrado en cada iteración para cada submalla.

De esta manera se puede seguir realizando una única llamada a createBuffer para crear cada uno de los tipos de buffers (índices, vértices, normales, ...), como hasta ahora. Y lo que cambia es que se debe realizar una llamada a bindBuffer/vertexAttribPointer/drawElements para cada submalla, indicando en vertexAttribPointer un offset que apunte a ese valor mínimo encontrado para cada submalla.

En la tercera imagen se puede ver un modelo con 1.448.269 triángulos, sin textura, sólo colores por vértice, creado por la empresa Cyberware con el detalle de las submallas. Como se observa, el algoritmo propuesto también funciona con este modelo por el mismo motivo que el anterior, pero para otro tipo de disposición de mallas no está garantizado que vaya a hacerlo.