Olvidaba comentar una de las prácticas que más me ha gustado (y costado) del primer cuatrimestre. El trabajo era totalmente libre, pero tenía que ser algo sobre multirresolución, así que varios alumnos decidimos experimentar con algoritmos de multirresolución. Yo, en particular, con colapso de facetas y de aristas.
El algoritmo que desarrollé calcula el área media de todas las facetas de la malla, y colapsa todas aquellas facetas cuya área sea menor que el doble del valor del área media. Pero tiene un gran inconveniente: sólo sirve para mallas en las que sus facetas estén agrupadas de 4 en 4 de la siguiente forma:
Para mallas de este estilo, obtenemos los resultados deseados:
Pero habría que extender el algoritmo para mallas con facetas agrupadas de diferentes formas:
El algoritmo que desarrollé selecciona la menor arista de la malla, elimina uno de sus vértices, junto con todos los triángulos que lo contienen y retriangula el agujero; todos los triángulos que contenían el vértice eliminado pasan a contener el otro vértice de la arista colapsada:
Crea una segunda malla (malla simplificada que se va construyendo a partir de la original). Encuentra la arista más corta, selecciona el vértice a a eliminar y guarda en una lista todos sus vértices vecinos menos el vértice b que lo va a reemplazar. Elimina los vértices repetidos de la lista y los ordena de forma que cada uno sea vecino del anterior (formando el borde del agujero). Añade los nuevos triángulos (que taparían el agujero), formados por el vértice b y todos los pares de vértices consecutivos de la lista, así como todos los triángulos que no contienen el vértice a eliminado. Añade todos los vértices y elimina los no referenciados (el vértice a).
Da buenos resultados, pero es poco eficiente (tiene alto coste computacional):
Implementé un segundo algoritmo de colapso de aristas, mucho más eficiente. Funciona para cualquier número de iteraciones y para cualquier malla. Selecciona la arista a colapsar (según el criterio de selección elegido), formada por los vértices
a y
b. Para cada triángulo
t: Si
t contiene a
a y a
b, se elimina el triángulo
t. Si
t contiene a
a pero no a
b, sustituye
a por
b en el triángulo
t.
Comparando distintos criterios de selección de arista:
Por último, desarrollé un tercer algoritmo de colapso de aristas más eficiente (a la tercera va la vencida), que tarda menos tiempo en simplificar una malla. Crea una lista de aristas a colapsar de una sola vez en lugar de colapsar una arista en cada iteración. Calcula el área media de todos los triángulos de la malla, y selecciona para colapsar toda arista que sea la menor de las aristas de cada triángulo que tenga menor área que el área media. Puede simplificar mallas mucho mayores mucho más rápido.
