Poligonizzazione e Visualizzazione di Superfici Implicite

  
 
SAMUELE CATTABRIGA POLIGONIZZAZIONE E VISUALIZZAZIONE DI SUPERFICI IMPLICITE 
 
 
 
 
 4 
naturali complessi, ha però permesso col passare degli anni la 
creazione di simulazioni computerizzate che hanno favorito 
previsione e analisi di problemi associati a sistemi di calcolo 
precedentemente non risolubili con facilità o funzioni di particolare 
interesse che in un primo momento richiedevano anni e anni di 
osservazione matematica. 
Uno specifico settore dell'informatica, nato e cresciuto a partire da 
ambienti di ricerca di analisi e calcolo numerico, si occupa nel 
dettaglio dello studio attraverso metodi di rappresentatazione grafica 
delle caratteristiche principali delle applicazioni delle teorie 
matematiche e, nella fattispecie, si interessa dello studio di funzioni e 
di equazioni particolari tramite la visualizzazione computerizzata 
delle figure geometriche associate, siano esse curve o superfici, e del 
loro interessante comportamento in alcuni situazioni ben definite 
strutturalmente. Questa disciplina, nata come molte altre in scenari 
universitari, trova molti sviluppi in applicazioni pratiche, da quelle 
militari (ad esempio nello studio di superfici esistenti nella realtà o 
nella visualizzazione di traiettorie) a quelle civili (si pensi 
all'applicazione in ambito industriale), tanto che essa stessa è 
divenuta con gli anni un settore indipendente, capace di sviluppare 
un importante influsso anche nella rappresentazione di realtà 
computerizzate perfino destinate al solo utilizzo ludico o 
dell'intrattenimento.  
In questa trattazione ci occuperemo in particolare di studiare queste 
curve e superfici rappresentabili tramite calcolatori elettronici e la 
loro visualizzazione. 
Nel capitolo 1 vedremo i principi che regolano la modellazione e la 
visualizzazione su elaboratore elettronico; nel capitolo 2 
focalizzeremo la nostra attenzione sulle curve e le superfici definibili 
in modo implicito e sulle loro caratteristiche e problematiche; nel 
capitolo 3 analizzeremo quindi alcune tipologie di metodi di 
rappresentazione esistenti, con un riferimento specifico ad un 
efficiente algoritmo di poligonizzazione studiato e implementato 
negli ultimi vent'anni da Bloomenthal e dai suoi collaboratori per la 
rappresentazione di superfici implicite in tempo reale. 
  
 
SAMUELE CATTABRIGA POLIGONIZZAZIONE E VISUALIZZAZIONE DI SUPERFICI IMPLICITE 
 
 
 
 
 5
Per quanto riguarda la visualizzazione di superfici poligonizzate, nel 
capitolo 4 si fara’ luce sulle strutture di ottimizzazione per la 
gestione ed il salvataggio dei dati inerenti alle operazioni effettuabili 
dai poligonizzatori; nel capitolo 5 mostreremo una delle librerie piu’ 
utilizzate per la resa grafica (OpenGL); nei capitoli 6 e 7 si vedranno 
uno sviluppo possibile per l’implementazione dell’algoritmo di 
Bloomenthal e alcune superfici studiabili grazie ad esso. 
  
 
SAMUELE CATTABRIGA POLIGONIZZAZIONE E VISUALIZZAZIONE DI SUPERFICI IMPLICITE 
 
 
 
 
 7
CAPITOLO 1: 
MODELLAZIONE E VISUALIZZAZIONE 
DI CURVE E SUPERFICI 
 
 
 
 
 
 
 
1.1. Il procedimento: modellazione e visualizzazione 
Sia che ci si trovi in un contesto bidimensionale, sia che il nostro 
ambiente di partenza sia espresso tramite coordinate tridimensionali, 
esso si ispira al modello di base fornito dalla nostra esperienza nella 
realtà a noi circostante. Il processo che ci permette di raffigurare un 
oggetto in due o tre dimensioni tramite elaboratore elettronico si basa 
perciò su un primo passaggio che si occupa di estrapolare le 
informazioni sul modello che lo costituisce e di ricostruire il modello 
stesso, indipendentemente dalle scelte di visualizzazione in cui esso 
verrà poi mostrato. Successivamente, una volta ricostituite le 
caratteristiche dell'oggetto scelto (sia esso una curva o una superficie, 
o solido), si può selezionare con oculatezza la tipologia di resa 
visuale che ci permetterà di poter vedere sullo schermo del computer 
ciò che abbiamo ricostituito durante la prima fase. Questo 
procedimento appena enunciato evidenzia una sequenza costante per 
qualunque rappresentazione grafica su un calcolatore, nei due punti 
di modellazione e visualizzazione, perfettamente esaminabili e 
trattabili separatamente seppure strettamente collegati; è sempre 
possibile, infatti, costruire visualizzazioni differenti di oggetti 
essendo in possesso di uno o più modelli a priori definiti, così come 
ci si può permettere di studiare le numerose possibilità di costruzione 
  
 
SAMUELE CATTABRIGA POLIGONIZZAZIONE E VISUALIZZAZIONE DI SUPERFICI IMPLICITE 
 
 
 
 
 8 
di strutture che compongano gli oggetti sapendo di disporre sin 
dall'inizio di un contesto e una serie di parametri per la scena in cui 
essi saranno sicuramente visualizzati.  
1.2. Cenni sulla modellazione  
Generalmente, pensando ai concetti espressi tramite parole come 
"modello" e "modellazione" nell'ambito non prettamente legati alla 
grafica per computer, viene subito in mente una stretta relazione di 
questi con la definizione di qualche schematismo che sia espressione 
di un'approssimazione della struttura che si sta per prendere in 
esame, più o meno definito in base alle tipologie di studi che su di 
essa si vorranno effettuare. Tale concezione viene adottata anche nel 
caso dello studio grafico di curve, superfici e di altri oggetti tramite 
elaboratore, mediante la definizione di una serie di regole 
geometriche che andranno a costruire le basi del nostro modello di 
gestione, bidimensionale o tridimensionale. 
Esistono differenti possibilità quindi, a seconda delle scelte 
effettuate, per definire le strutture di rappresentazione di oggetti, e 
possiamo sintetizzarle in base a due problemi cruciali: la scelta del 
sistema di coordinate e quella dell'orientamento del sistema. 
Abbiamo infatti due modi comuni di rappresentare gli oggetti, uno 
basato su coordinate di tipo cartesiano (fig. 1a) e l'altro riferito a 
coordinate polari o sferiche (a seconda che l'ambiente sia definito in 
due o tre dimensioni) (fig. 1b).  
 
  
 
SAMUELE CATTABRIGA POLIGONIZZAZIONE E VISUALIZZAZIONE DI SUPERFICI IMPLICITE 
 
 
 
 
 9
 
 
 
Se ci basiamo su una scelta per un sistema di tipo cartesiano, si 
prevede l'esistenza di punti identificati come coppie o triple di 
coordinate, nella fattispecie [x, y] oppure [x, y, z], ciascuna delle 
quali fornisce rispettivamente la distanza di ogni punto dagli assi X e 
Fig. 1b 
Punto espresso tramite 
coordinate polari (2D) o 
sferiche (3D) 
2D 3D
P = (D, θ) P=(D, θ, φ) 
φ
θ
x
y y
x 
z
D
Fig. 1a 
Punto espresso tramite 
coordinate cartesiane 
P = (x, y) P=(x, y, z) 
x 
z
y
x
y 
  
 
SAMUELE CATTABRIGA POLIGONIZZAZIONE E VISUALIZZAZIONE DI SUPERFICI IMPLICITE 
 
 
 
 
 10 
Y o dai piani YZ, XZ, XY. In un sistema a coordinate sferiche, 
invece, ogni punto è individuato tramite la coppia [D, θ] o la tripla 
[D, θ, φ], dove D indica la distanza OP del punto P dall'origine, θ è 
l'angolo tra la direzione positiva dell'asse X e il segmento OP (o la 
sua proiezione OP' sul piano XY, se OP è definito nelle tre 
dimensioni), e φ l'eventuale angolo esistente tra il segmento e la 
direzione positiva dell'asse delle Z. Come si può notare, è possibile 
definire delle trasformazioni che ci permettono di ottenere le 
coordinate in un sistema a partire da quelle espresse nell'altro; perciò 
nel caso si abbiano coordinate polari o sferiche è sufficiente 
effettuare le seguenti conversioni 
 
2D    3D 
 
per ottenere coordinate cartesiane. Viceversa 
 
 
2D    3D 
 
ci permette di ottenere una parametrizzazione polare o sferica a 
partire da un sistema cartesiano [1 - 2]. 
La scelta dell'orientamento del sistema riguarda invece la decisione 
su quale ordine dei versori degli assi considerare per la formulazione 
del modello. In particolare, si definisce destrorso un sistema 
orientato in modo che le prime due/tre dita della mano destra si 
sovrappongano agli assi X, Y (e Z), con angoli considerati positivi 
x = D cosθ
y = Dsenθ
⎧ 
⎨ 
⎩ 
x = D cosϕ cosθ
y = Dcos ϕ sen θ
z = Dsen ϕ
⎧ 
⎨ 
⎪ 
⎩ 
⎪ 
D = (x
2
+ y
2
)
θ = arccos(x / D)
⎧ 
⎨ 
⎪ 
⎩ 
⎪ 
D = (x
2
+ y
2
+ z
2
)
θ = arctg(y / x)
ϕ = arccos(z / D)
⎧ 
⎨ 
⎪ 
⎪ 
⎩ 
⎪ 
⎪ 
  
 
SAMUELE CATTABRIGA POLIGONIZZAZIONE E VISUALIZZAZIONE DI SUPERFICI IMPLICITE 
 
 
 
 
 11
solo se in senso antiorario; si definisce, al contrario, sinistrorso se 
avviene lo stesso rispetto alle prime due/tre dita della mano sinistra, 
considerando perciò positivi gli angoli orientati in senso orario.  
Nella computer graphics, per convenzione, vengono utilizzati sistemi 
destrorsi, principalmente di tipo cartesiano, ma possono inoltre 
essere aggiunte ulteriori informazioni, al fine di determinare il 
modello con maggiore precisione. La struttura B-Rep (Boundary 
Representation) di un oggetto tridimensionale, ad esempio, organizza 
le informazioni di base in una descrizione della composizione 
dell'oggetto, costituita da una lista dei vertici in coordinate cartesiane 
3D, una tabella dei lati (ognuno identificato dai vertici che ne sono 
estremi) e una tabella delle facce, di cui ne memorizza tutti i dati 
relativi. Come si nota, questa scelta, molto frequente, riduce gli  
oggetti ad un insieme di specifiche che, di fatto, andranno a 
comporre un modello poligonale dell'oggetto o degli oggetti 
esaminati. A partire da questa tipologia strutturale, si sono sviluppate 
numerose tecnologie (e tuttora nella ricerca è stato definito più di un 
settore specifico che se ne occupa); la più diffusa, che è base di 
formati più semplici, come quelli contenuti nei files .m, o più 
complessi, come il formato dati contenuto nei files Alias/Wavefront 
.obj, viene denominata VFE, da Vertex-Face-Edge: è implementata 
tramite tabelle che ad ogni vertice associano coordinate, ad ogni lato 
o segmento i propri vertici estremi e ad ogni faccia i lati che la 
compongono, similmente alla specifica B-rep generica (anche se, in 
questo caso, puo’ bastare la descrizione dei vertici e delle facce per 
ricomporre l’intero modello) [2]. 
Un ulteriore tipologia di strutture per la modellazione, chiamata CSG 
(Constructive Solid Geometry), prevede una descrizione basata sulla 
composizione a partire da solidi esistenti, mediante operazioni per lo 
più di estrapolazione o fusione, strutturate in un albero di 
scomposizione con radice nel solido composto e foglie associate ai 
solidi primitivi. Su di esso poi il modello fornirà un algoritmo per 
l’efficienza nella composizione, che attraversa l’albero dalle foglie 
alla radice, in un meccanismo depth-first. Alberi dalle caratteristiche 
molto simili possono venire ripresi o utilizzati separatamente anche 
in fase di rappresentazione, nella gestione di griglie poligonali, per