• SUDDIVISIONE CAGD LOOP

La presente tesi affronta lo studio di una particolare classe di metodi iterativi, detti schemi di suddivisione, utilizzati principalmente in computer graphics per la modellazione e la manipolazione di curve e superfici a partire da un insieme discreto di dati.

L'origine di tali metodi è attribuita allo studio di problemi geometrici di smussamento degli spigoli di una superficie poliedrica, talvolta chiamati ``wood carver algorithms'' (algoritmi dell'intagliatore) in quanto le ripetute operazioni di smussamento ricordano le fasi di intaglio e levigazione caratteristiche della lavorazione artigianale del legno.

Attualmente essi rappresentano uno degli strumenti matematici indispensabili nell'ambito della Computer Aided Geometric Design (CAGD), ossia di quella branca delle scienze applicate che si occupa della ricerca di metodi matematici e di tecnologie software per l'elaborazione assistita dal calcolatore di oggetti geometrici, quali appunto curve, superfici e volumi, che costituiscono gli elementi di base per la rappresentazione di un qualsiasi oggetto tridimensionale.

Gli schemi di suddivisione sono determinati da poche semplici regole lineari che, usate ripetutamente, permettono di generare forme ed oggetti ``regolari'' a partire da una loro rappresentazione ``grossolana''.

Formalmente sono definiti da una successione di operatori lineari,
$\{\mathcal{S}_{\mathbf{a}^{(k)}} :\ell^\infty{(\mathbb{Z}^s)}\to\ell^\infty{(\mathbb{Z}^s)}\}_{k\geq0}$, dette regole di raffinamento, della forma
\[(\mathcal{S}_{\mathbf{a}^{(k)}} \mathbf{f})_\alpha =\sum_{\beta\in\mathbb{Z}^s } {a}_{\alpha-2\beta}^{(k)} f_\beta, \quad \bb f=\{f_\beta\}_{\beta\in\mathbb{Z}^s }\in \ell^\infty{(\mathbb{Z}^s)},\,\, k\in\mathbb{N}\]
dove $\{\mathbf{a}^{(k)}\}_{k\geq0}$ \`e una successione di elementi di $\ell^\infty{(\mathbb{Z}^s)}$: $\mathbf{a}^{(k)}=\{{a}_{\gamma}^{(k)}\}_{\gamma\in\mathbb{Z}^s}$.
Sono metodi computazionalmente efficienti, piuttosto facili da implementare e soprattutto permettono di definire curve e superfici con un certo grado di regolarità.
Malgrado la semplicità degli algoritmi in sé, però, l'analisi della convergenza della sequenza
$\{\mathbf{f}^{(k)}\}_{k>0}$, con
$\mathbf{f}^{(k)}=\mathcal{S}_{\mathbf{a}^{(k-1)}} \cdots\mathcal{S}_{\mathbf{a}^{(0)}}\mathbf{f}^{(0)}$ ed $\mathbf{f}^{(0)}\in\ell^\infty{(\mathbb{Z}^s)}$,
può rivelarsi anche molto complessa. Ci sono ovviamente delle eccezioni: una scelta opportuna delle regole utilizzate nella fase di raffinamento consente una analisi esaustiva della convergenza e della regolarità della superficie limite.

Nella tesi è stato approfondito lo studio della convergenza e della regolarità delle funzioni limite, ponendo particolare attenzione al caso stazionario.
È stato analizzato nel dettaglio il caso univariato e bivariato, dove, grazie ad un formalismo basato sulle serie formali di Laurent, è possibile fornire delle condizioni necessarie e sufficienti di convergenza di facile verificabilità. I risultati ottenuti sono stati riletti in chiave matriciale per tenere vivo il legame con l'aspetto pratico ed implementativo degli schemi.

Si è inoltre fornita una breve panoramica dei più importanti schemi univariati e bivariati presenti in letteratura, trattando, in particolare, lo studio dell'algoritmo di Chaikin e dello schema di Loop, per i quali è stata anche curata un'implementazione in ambiente Matlab.

Lo schema di Loop, infine, è stato applicato a reti iniziali di diversa natura (reti aperte, chiuse, regolari e non regolari), permettendoci di apprezzare le potenzialità degli algoritmi di suddivisione e il loro utilizzo nell'ambito della modellazione grafica.