Simplificación de mallas de triángulos Autor: Miguel Pasenau Director: Carlos Andújar ( LSI, FIB) Centre Internacional de Mètodes Numèrics en Enginyeria

Índice • Introducción • Aplicación – Plataforma – Algoritmos

• Resultados – Modelos – Tiempos, escalabilidad

• Trabajo en curso • Conclusiones 28 Septiembre 2011 / 2

Índice • Introducción • Aplicación – Plataforma – Algoritmos

• Resultados – Modelos – Tiempos, escalabilidad

• Trabajo en curso • Conclusiones 28 Septiembre 2011 / 3

Motivación • • • •

Modelos escaneados de alta resolución Simulaciones con 10^9 elementos Interacción en tiempo real Plataformas comunes

28 Septiembre 2011 / 4

Objetivos • • • • • •

Desarrollar algoritmo de simplificación Nivel de detalle seleccionable Rápido Eficiente en memoria Multiplataforma Robusto

28 Septiembre 2011 / 5

Etapas • • • • •

Estudio del arte Desarrollo aplicación de ensayo Implementación primera versión Ampliación y mejoras Análisis de resultados

28 Septiembre 2011 / 6

Índice • Introducción • Aplicación – Plataforma – Algoritmos

• Resultados – Modelos – Tiempos, escalabilidad

• Trabajo en curso • Conclusiones 28 Septiembre 2011 / 7

Plataforma • Desarrollado en C ++, OpenMP y OpenGL • Usando FLTK 1.3.x ( incluye GLUT)

28 Septiembre 2011 / 8

Algoritmo de DeCoro y Tatarchuk 2007 • Full grid, simplificación uniforme de grupos vértices • Algoritmo de tres pasos: – Paso 1: crear mapa de QEF a partir de la malla – Paso 2: encontrar el representante óptimo para cada celda – Paso 3: simplificación de malla, colapsando vértices de cada celda en su representante

• Utiliza el error cuadrático de Garland y Heckbert 1997 28 Septiembre 2011 / 9

Algoritmo de DeCoro 2007 • Paso 1: para cada nodo de cada triángulo, acumular sus coordenadas y la QEF del triángulo en su celda QEF QEF QEF QEF QEF QEF QEF QEF accQEF accQEF accQEF accQEF accQEF accQEF accQEF accQEF QEF QEF QEF QEF QEF QEF QEF QEF QEFacc QEFacc QEFacc QEFacc QEFacc QEFacc QEFacc QEFacc accQEF accQEF accQEF accQEF accQEF accQEF accQEF accQEF accQEF accQEF accQEF accQEF accQEF accQEF accQEF accQEF QEF QEF QEF QEF QEF QEF QEF acc acc acc acc acc acc acc QEF QEF accQEF accQEF accQEF accQEF accQEF accQEFaccQEF QEFacc QEFacc QEF accQEF QEF QEF QEF QEF QEF QEFacc QEFacc QEFacc QEFacc QEFacc QEFaccQEF accQEFacc accQEF QEFacc QEFacc QEFacc QEFacc QEFacc QEFacc QEF accQEF accQEF accQEF acc acc acc acc acc acc QEF QEF accQEF accQEF accQEF accQEF accQEFacc accQEF QEFacc QEFacc QEF QEF QEF QEF QEF QEF QEF accQEF acc acc acc acc acc acc acc acc QEF QEF accQEF accQEF accQEF accQEF accQEF accQEF accQEFacc accQEF QEF QEF QEF QEF QEF QEF QEF QEF acc acc acc acc acc acc acc acc acc QEF accQEF accQEF accQEF accQEF accQEF accQEFacc accQEF accQEF acc accQEF QEF QEF QEF QEF QEF QEF QEF QEF acc acc acc acc acc acc acc acc QEF QEF accQEF accQEF accQEF accQEF accQEF accQEF accQEF accQEF QEFacc QEFacc QEF accQEF QEF QEF QEF QEF QEF QEF acc QEFacc QEFacc QEFacc QEFacc QEFacc QEFacc accQEF accQEF acc acc acc acc acc acc acc QEF QEF QEF QEF QEF QEF QEF QEF QEF acc acc QEFacc QEFacc QEFacc QEFacc QEFacc QEFacc QEFacc QEFaccQEFacc acc QEFacc QEFacc QEFacc QEFacc QEFacc QEF QEF QEFacc QEFacc accQEF acc QEFacc QEFacc QEFacc QEFacc QEFacc QEFacc QEFacc QEFacc QEF QEF acc acc QEF accQEF accQEFacc QEFacc QEFacc QEFacc QEFacc QEFacc acc acc QEF accQEFacc QEFacc QEFacc QEFacc QEFacc QEFacc accQEF accQEF acc acc acc acc acc acc accQEF QEF QEF QEF QEF QEF QEF QEF QEF acc acc acc acc acc acc acc acc QEF QEF accQEF accQEF accQEF accQEF accQEF accQEF accQEF accQEF QEFacc QEFacc QEF accQEF QEF QEF QEF QEF QEF QEF acc QEFacc QEFacc QEFacc QEFacc QEFacc QEFacc accQEF accQEF acc acc acc acc acc acc acc QEF QEF QEF QEF QEF QEF QEF QEF QEF acc acc QEFacc QEFacc QEFacc QEFacc QEFacc QEFacc QEFacc QEFaccQEFacc acc QEFacc QEFacc QEFacc QEFacc QEFacc QEF QEF QEFacc QEFacc accQEF acc QEFacc QEFacc QEFacc QEFacc QEFacc QEFacc QEFacc QEFacc QEF QEF acc acc QEF accQEF accQEFacc QEFacc QEFacc QEFacc QEFacc QEFacc acc acc QEF accQEFacc QEFacc QEFacc QEFacc QEFacc QEFacc accQEF accQEF acc acc acc acc acc acc accQEF QEF QEF QEF QEF QEF QEF QEF QEF acc acc acc acc acc acc acc acc QEF accQEF accQEF accQEF accQEF accQEF accQEF accQEF accQEF QEFacc QEF QEF QEF QEF QEF QEFaccQEF accQEF QEFacc QEFacc QEFacc QEFacc QEFacc QEFacc accQEFacc accQEF acc acc acc acc acc acc acc QEF accQEF accQEF accQEF accQEF accQEF accQEF accQEFacc accQEFacc accQEF accQEF accQEF accQEF accQEF accQEF accQEF accQEF accQEF accQEF accQEF accQEF accQEF accQEF accQEF accQEF accQEF accQEF accQEF accQEF accQEF accQEF accQEF acc acc acc acc acc acc acc acc accQEF accQEF accQEF accQEF accQEF accQEF accQEF accQEF accQEF accQEF accQEF accQEF accQEF accQEF accQEF accQEF acc acc acc acc acc acc acc acc

Grid de 8 x 8 x 8 para acumular: QEF y vértices de la celda 28 Septiembre 2011 / 10

Algoritmo de DeCoro 2007 • Paso 2: representante óptimo de la celda: – Invertir QEF – Verificar si está en la celda – Si no, usar el centroide de los vértices QEF acc QEF acc QEF acc QEF acc QEF acc QEF acc QEF acc QEF acc

QEF acc QEF acc QEF acc QEF acc QEF acc QEF acc QEF acc QEF acc

QEF acc QEF acc QEF acc QEF acc QEF acc QEF acc QEF acc QEF acc

QEF acc QEF acc QEF acc QEF acc QEF acc QEF acc QEF acc QEF acc

QEF acc QEF acc QEF acc QEF acc QEF acc QEF acc QEF acc QEF acc

QEF acc QEF acc QEF acc QEF acc QEF acc QEF acc QEF acc QEF acc

QEF acc QEF acc QEF acc QEF acc QEF acc QEF acc QEF acc QEF acc

QEF acc QEF acc QEF acc QEF acc QEF acc QEF acc QEF acc QEF acc

Representante óptimo

28 Septiembre 2011 / 11

Algoritmo de DeCoro 2007 • Paso 3: para cada triángulo – Obtener las celdas ( cluster_id) de sus vértices – Si no colapsa: • Sustituir vértices por representante óptimo • Guardar triángulo Mapa Qef + Acc Grid de 9 x 9 x 9

28 Septiembre 2011 / 12

Algoritmo de DeCoro 2007 • Paso 3: para cada triángulo – Obtener las celdas de sus vértices – Si colapsa en línea: • Sustituir vértices por representante óptimo • Guardar línea Mapa Qef + Acc Grid de 9 x 9 x 9

28 Septiembre 2011 / 13

Mejoras introducidas • Recuperación de líneas

Grid de 19 x 19 x 19

28 Septiembre 2011 / 14

Mejoras introducidas • • • •

Restricción del representante a la celda Recuperación de líneas Triángulos y líneas únicas Corrección de normales

28 Septiembre 2011 / 15

Calidad y resolución • Full grid hasta 2563 = 1,1 GB

28 Septiembre 2011 / 16

Calidad y resolución • Ocupación según resolución de la malla poligonal del modelo Lucy

grid 1283 2563 5123 1.0243 2.0483 4.0963

Celdas ocupadas y memoria ( 72 bytes = qef + acc + opt) MBytes # celdas % / total MBytes 144 23 k 1% 1,5 1.152 91 k 0,5 % 6 9.216 351 k 0,3 % 24 72 G 1,3 M 0,1 % 90 572 G 4,6 M 0,05 % 313 4.608 G 10 M 0,02 % 706 28 Septiembre 2011 / 17

Hash espacial Alcántara et al. 2009 • Primer nivel: repartir en buckets de