Jade

Lo scopo del processo di decimazione è quello di ridurre la complessità di una mesh in termini di numero di facce e di vertici. Il processo qui proposto è iterativo; ad ogni passo viene scelto un vertice da rimuovere, i triangoli in esso incidenti sono rimossi e il "buco" che essi creano è "coperto" con un nuovo insieme di triangoli. Il processo continua soltanto se l’errore commesso, togliendo il vertice, è minore di una soglia fissata. Il numero di passi dipende, quindi, dal tasso di riduzione che si vuole raggiungere. In figura è rappresentato un parallelepipedo "rastremato" costituito da 282 vertici e 560 facce. Nelle figure successive lo stesso oggetto dopo la riduzione rispettivamente del 70%, 90% e 95% dei suoi vertici.

Sia V l’insieme dei vertici della mesh e F l’insieme delle facce triangolari di cui è formata. Il processo di decimazione determina, ad generico passo i, un nuovo insieme di vertici V⁽ⁱ⁾ e un nuovo insieme di facce F⁽ⁱ⁾:

M(V⁽⁰⁾,F⁽⁰⁾)® M(V⁽¹⁾,F⁽¹⁾) ® M(V⁽²⁾,F⁽²⁾)® M(V⁽³⁾,F⁽³⁾) ® ……

Dove :

V⁽⁰⁾ Ê V⁽¹⁾ Ê V^(2)Ê V^(3)Ê ……

Siano S⁽ⁱ⁾ l’insieme della facce triangolari dell’area da triangolare al passo i e T ^ottima(i) l’insieme delle nuove facce (chiamata triangolazione ottima). Allora vale:

F⁽ⁱ⁾ = F^(i-1) \ S⁽ⁱ⁾ È T ^ottima(i)

In figura è rappresentato un passo di semplificazione consistente nell’eliminazione di un vertice e dei triangoli in esso adiacenti e la relativa ritriangolazione del "buco" (chiamato poligono 3D). Una parte fondamentale del processo di decimazione è l’algoritmo che costruisce la nuova triangolazione; una sua implementazione efficiente determina l’efficienza dell’intero processo.