esi di Laurea - polito.it · 2006-09-18 · ti da quelli italiani, questa esp erienza mi ha anc he...

POLITECNICO DI TORINO

Facolt�a di IngegneriaCorso di Laurea in Ingegneria Informatica

Tesi di Laurea

Sviluppo di un algoritmoadattativo per la poligonizzazione

di super�ci implicite

Relatore:prof. Aldo Laurentini

Candidato:Andrea Bottino

Ottobre 1995

A Claudia

Indice

1 Introduzione 5

2 L'algoritmo Shrinkwrap 10

2.1 Approssimazione della super�cie : : : : : : : : : : : : : : : : : : : : 10

2.1.1 Cos'�e una super�cie accettabile : : : : : : : : : : : : : : : : : 12

2.1.2 Stima dell'errore in caso di curvatura monotona : : : : : : : : 12

2.1.3 Stima dell'errore nel caso generale : : : : : : : : : : : : : : : 12

2.2 Un algoritmo per arrivare ad una struttura triangolare accettabile : : 14

2.3 Come ottenere dei vertici sulla super�cie : : : : : : : : : : : : : : : : 15

2.4 Come ottenere una super�cie chiusa : : : : : : : : : : : : : : : : : : 17

2.5 Come ottenere una tassellatura accettabile : : : : : : : : : : : : : : : 18

2.6 L'algoritmo : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 19

2.7 Risultati ottenibili : : : : : : : : : : : : : : : : : : : : : : : : : : : : 22

3 Limiti dell'algoritmo 24

3.1 Cos'�e un punto critico : : : : : : : : : : : : : : : : : : : : : : : : : : 25

3.2 Comportamento della struttura triangolare : : : : : : : : : : : : : : : 27

3.3 Validit�a dei lemmi : : : : : : : : : : : : : : : : : : : : : : : : : : : : 29

4 Singolarit�a e super�ci 31

4.1 Come si possono trovare i punti critici : : : : : : : : : : : : : : : : : 31

4.2 Piani di simmetria della super�cie : : : : : : : : : : : : : : : : : : : 34

4.3 Avvicinandosi al punto critico : : : : : : : : : : : : : : : : : : : : : : 37

5 Super�ci di separazione 39

2

Indice

5.1 Cosa fare delle corde rosse : : : : : : : : : : : : : : : : : : : : : : : : 39

5.2 Caratteristiche dell'insieme T : : : : : : : : : : : : : : : : : : : : : : 43

5.3 Come stabilire il tipo delle super�ci di separazione : : : : : : : : : : 44

6 Come ricostruire una struttura corretta 46

6.1 Distribuzioni con un solo punto critico : : : : : : : : : : : : : : : : : 46

6.1.1 Il piano separatore : : : : : : : : : : : : : : : : : : : : : : : : 47

6.1.2 Ricostruire una rottura : : : : : : : : : : : : : : : : : : : : : 47

6.1.3 Ricostruire un buco : : : : : : : : : : : : : : : : : : : : : : : 49

6.2 Distribuzioni con pi�u punti critici : : : : : : : : : : : : : : : : : : : : 50

6.2.1 Alcune de�nizioni : : : : : : : : : : : : : : : : : : : : : : : : 51

6.2.2 Ricostruire l'intera struttura : : : : : : : : : : : : : : : : : : 52

7 L'algoritmo modi�cato 54

7.1 Il nuovo algoritmo : : : : : : : : : : : : : : : : : : : : : : : : : : : : 54

7.2 Analisi dei risultati : : : : : : : : : : : : : : : : : : : : : : : : : : : : 58

7.3 Conclusioni : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 59

7.4 Ulteriori sviluppi della ricerca : : : : : : : : : : : : : : : : : : : : : : 61

A How to shrinkwrap a saddle point 62

A.1 Introduction : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 62

A.2 Critical points : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 64

A.2.1 How the region around a critical point behaves : : : : : : : : 65

A.3 The surface : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 67

A.3.1 What is happening to the surface : : : : : : : : : : : : : : : : 68

A.3.2 How to detect red edges : : : : : : : : : : : : : : : : : : : : : 70

A.4 Fixing the topology : : : : : : : : : : : : : : : : : : : : : : : : : : : 74

A.4.1 Is it a �ssure or is it a hole? : : : : : : : : : : : : : : : : : : : 76

A.4.2 How to �x the topology : : : : : : : : : : : : : : : : : : : : : 79

A.5 Dealing with complex topologies : : : : : : : : : : : : : : : : : : : : 84

A.5.1 Some de�nitions : : : : : : : : : : : : : : : : : : : : : : : : : 84

A.5.2 How to proceed : : : : : : : : : : : : : : : : : : : : : : : : : 85

3

Indice

A.6 Evaluations : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 87

A.7 Conclusion : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 88

A.8 Acknowledgments : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 88

4

1

Introduzione

Il lavoro svolto in questa tesi �e stato realizzato presso l'Universit�a Tecnica di Ein-dhoven (Technische Universiteit Eindhoven), in Olanda e si inquadra nell'ambito delprogetto ERASMUS, progetto �nalizzato allo scambio di studenti fra Universit�a ap-partenenti agli stati della Comunit�a Europea. Oltre agli stimoli o�erti dal confrontocon una mentalit�a e un modo di vivere di�erenti da quelli italiani, questa esperienzami ha anche o�erto la possibilit�a di essere inserito in un gruppo di lavoro a�ata-to, il Technische Toepassingen Group, sempre disponibile nell'aiutarmi a superare iproblemi derivanti dall'inserimento in un ambiente nuovo.

Una parte della tesi, scritta in inglese, comprende il documento di ricerca depo-sitato presso la stessa universit�a. L'introduzione e gli altri capitoli scritti in italianoservono per descrivere le basi di partenza di questo lavoro, e per introdurre detta-gliatamente alcuni punti trattati velocemente per necessit�a di brevit�a nella stesuradel documento stesso.

Questo lavoro si basa su un algoritmo comparso in [Overveld 93], chiamato Shrin-kwrap, per la costruzione di una poligonizzazione adattativa di super�ci implicite chegodono di particolari propriet�a. Lo scopo di questa tesi �e di proporre una modi�cae un ampliamento dell'algoritmo in grado di trattare indistintamente qualsiasi tipodi super�cie implicita.

Le super�ci utilizzate nel seguito sono de�nite come super�ci equipotenziali di uncampo scalare generato da uno scheletro di base. Le super�ci equipotenziali sono unaimportante classe di super�ci implicite e assumono un ruolo signi�cativo nel campodella gra�ca al computer per la modellazione, l'animazione e la visualizzazione. Allostesso tempo, diverse super�ci di un certo interesse nel campo della pura matematica,della �sica e della chimica sono super�ci equipotenziali; si consideri, ad esempio, ladistribuzione di tensione in una parte meccanica oppure la distribuzione di pressionein un uido contenuto in un recipiente.

5

1 { Introduzione

Recentemente un interesse crescente verso le super�ci implicite pu�o essere riscon-trato nel campo del disegno geometrico assistito al calcolatore (CAGD, ComputerAided Geometric Design). La ragione di ci�o �e data dal fatto che alcuni problemi nelprocesso di modellazione geometrica possono essere risolti solo con sforzi notevoliutilizzando super�ci in rappresentazione parametrica, mentre gli stessi possono es-sere risolti in maniera relativamente semplice utilizzando la forma implicita. Tipiciproblemi di questo genere sono, ad esempio, la costruzione di super�ci di fusione(blending surfaces) che uniscano due o pi�u super�ci date, oppure la costruzione diuna super�cie di o�set rispetto ad una super�cie data.

Contrariamente all'interesse dimostrato e confrontata con l'abbondanza di lette-ratura sulle super�ci parametriche, sono ancora relativamente pochi gli studi sullesuper�ci in forma implicita. Gli articoli citati qui di seguito costituiscono una sum-ma dei lavori disponibili, al momento, sull'argomento.

In [Schmidt 93] la super�cie implicita �e de�nita come l'insieme dei valori per cui�e nulla la funzione f : R3 ! R, dove la funzione f pu�o essere polinomiale, trascen-dentale oppure pu�o essere de�nita in maniera procedurale, con l'unica richiesta dicontinuit�a per f . Lo svantaggio maggiore che introduce questo metodo �e la di�colt�adi controllare la forma della super�cie, in quanto gli e�etti generati dai parametrinon sono in genere intuibili.

In [Wyvill 86] viene descritto un approccio per modellare, visualizzare e animarei cosiddetti soft objects, oggetti o insiemi di oggetti rappresentati da un campo sca-lare. In pratica la super�cie che de�nisce l'oggetto �e una super�cie isopotenziale delcampo stesso (cio�e la regione dello spazio in cui la funzione che de�nisce il campoha valore costante) ed �e generata a partire da un insieme di funzioni elementari cheagiscono localmente, rendendone pi�u intuitivo l'utilizzo rispetto a funzioni algebri-che. Approcci simili si possono trovare in [Blinn 82] e [Bloomenthal 90]. Witkin,in [Witkin 94], propone invece un sistema a particelle per generare e controllaresuper�ci implicite in movimento. Tali particelle vengono legate alle super�ci attra-verso semplici regole e il comportamento del sistema �e determinato dalle equazionidi�erenziali che speci�cano il movimento dell'insieme di particelle.

Uno svantaggio signi�cativo della rappresentazione di super�ci in modo implicito�e dato dal fatto che in genere �e abbastanza di�cile visualizzarle e ombreggiarle.Questa di�colt�a �e uno dei pi�u grandi ostacoli che limitano l'utilizzo della formaimplicita rispetto a quella parametrica. I metodi utilizzati per la visualizzazione sonoprincipalmente due: il primo �e quello di utilizzare il ray tracing ([H�olmstrom 89]),una tecnica che permette di produrre immagini fotorealistiche; tuttavia, trovarel'intersezione di un raggio con una super�cie implicita �e spesso un compito arduo, ela quantit�a notevole di calcoli richiesti ne pone restrizioni all'uso. In pi�u il risultato�nale che si ottiene �e costituito solamente da un insieme di punti i cui attributidipendono dalla particolare vista scelta; cambiando il punto di visione bisogna rifare

6

1 { Introduzione

tutti i calcoli, ed �e quindi impensabile utilizzare il ray tracing in applicazioni realtime.

Il secondo metodo consiste nella conversione delle super�ci implicite in strutturepoligonali che la approssimino e che possano successivamente essere ombreggiate;un ulteriore vantaggio di questa tecnica �e quello di poter disporre di una comple-ta approssimazione in tre dimensioni della super�cie implicita, che permetta cos�idi avere velocemente viste da posizioni arbitrarie senza la necessit�a di risolvere lafunzione implicita tutte le volte. In pi�u �e possibile applicare alla struttura creatadiverse tecniche di post-processing, come ad esempio lo smoothing ([Cohen 94]), chegenera una struttura regolare a partire da un insieme di poligoni irregolari, o lafree form deformation ([Sederberg 86]), che permette di deformare oggetti sia local-mente che globalmente. In seguito si far�a riferimento a questa tecnica col terminepoligonizzazione ([Bloomenthal 87]).

L'idea di base di tutte le tecniche di poligonizzazione esistenti �e una suddivisioneappropriata dello spazio in analisi, mediante una griglia uniforme di elementi cubicio tetraedrici. La funzione viene campionata nei vertici degli elementi di base el'approssimazione poligonale viene generata a partire dagli elementi i cui vertici nonsono tutti interni o tutti esterni alla super�cie. Questo metodo comporta diversisvantaggi. In primo luogo si introduce una divisione dello spazio piuttosto che unatassellatura della super�cie da poligonalizzare. Specialmente nel caso di animazioni,questo pu�o causare e�etti ondulatori sulla super�cie in movimento rispetto allagriglia di riferimento, che �e �ssa nello spazio. In pi�u, se questa �e troppo larga,alcune piccole peculiarit�a della super�cie possono non essere evidenziate.

In secondo luogo questi algoritmi creano una incoerenza tra il numero di trian-goli generati e la complessit�a della super�cie da approssimare: la stessa densit�a difaccette viene infatti usata per regioni ad elevata curvatura e per parti della su-per�cie relativamente piatte, dando origine complessivamente ad un gran numerodi faccette. Per rendere il processo di poligonizzazione pi�u e�ciente, Bloomenthal([Bloomenthal 88]) descrive un metodo adattativo che utilizza un octree, una strut-tura ad albero di grado otto. La radice dell'albero si riferisce in genere all'interovolume e punta ad altri otto nodi, corrispondenti alle parti in cui esso �e stato diviso.Ognuno di questi otto nodi pu�o quindi puntare ad altri otto sottonodi relativi alleotto parti di ogni sottovolume. Per rendere adattativa la poligonizzazione, la sud-divisione dei sottovolumi si basa sulla curvatura della super�cie da approssimare.Questa tecnica riduce e�ettivamente il numero di poligoni generati, ma pu�o esseresfruttata pienamente solo se la regione piatta cade interamente in un ottante. Lamaggior parte di questi metodi, inoltre, assume implicitamente che la super�cie inesame sia regolare, oppure che il processo di suddivisione possa essere spinto ad unpunto tale da consentire di avere una intersezione non ambigua con la super�cie.

7

1 { Introduzione

In [Schmidt 93] viene mostrato come in alcuni casi queste assunzioni non siano va-lide, e viene proposta un'estensione del lavoro di Bloomenthal in grado di trattaresingolarit�a della super�cie.

Un ultimo limite di queste tecniche �e dato dal fatto che la super�cie creata nondispone di un proprio sistema di coordinate, il che rende abbastanza di�cile, adesempio, l'applicazione a tali strutture di una texture mapping.

L'algoritmo Shrinkwrap introduce un di�erente approccio al problema. Le super-�ci implicite vengono de�nite come super�ci equipotenziali generate da uno scheletrodi base che ha lo scopo di modellare gli "oggetti" di interesse, cio�e le super�ci iso-potenziali stesse. Tale scheletro �e composto da una serie di elementi, ad ognunodei quali �e associata una funzione di campo fi. La super�cie S �e de�nita dall'in-sieme di punti p 2 R3 che soddisfano f(p) = 1, dove f �e data dalla somma dellefunzioni di campo degli elementi che compongono lo scheletro. Tali elementi posso-no essere rappresentati da diverse entit�a geometriche (punti, linee, super�ci, ecc...),anche se nel seguito della trattazione verranno considerate come primitive solo ipunti. L'algoritmo genera una struttura approssimante triangolare che �e adattativaal comportamento locale della super�cie piuttosto che essere imposta a priori da unasuddivisione dello spazio, nel senso che la lunghezza dei lati dei triangoli componen-ti la struttura varia secondo la curvatura locale della super�cie sottostante; quindi,parti della super�cie relativamente piatte saranno costituite da triangoli pi�u larghirispetto a regioni ad elevata curvatura. Come ulteriore vantaggio, risulta abbastanzasemplice assegnare alla struttura creata un sistema di coordinate proprio.

L'idea di base di questo algoritmo �e abbastanza semplice. Invece di costruiredirettamente una approssimazione per la super�cie �nale f(p) = 1 si pu�o partireda una super�cie ad un potenziale pi�u basso. Successivamente si procede per passiattraverso potenziali via via crescenti �no ad arrivare alla con�gurazione �nale,adattando la struttura alle super�ci intermedie. Quando, al crescere del potenziale,cresce anche la curvatura della super�cie, le regioni corrispondenti saranno composteda un numero maggiore di faccette.

Questo algoritmo impone per�o una importante limitazione data dal fatto chenon pu�o trattare con tutti i tipi di super�ci. Infatti a causa del metodo utilizzato,super�ci contenenti singolarit�a non sono approssimabili, o, per essere pi�u precisi,non sono trattabili con�gurazioni dello scheletro di base che introducano punti criticiall'interno del campo di potenziale.

Partendo dall'algoritmo di base presentato in [Overveld 93] e analizzando in mo-do pi�u dettagliato i casi in cui non �e applicabile, verr�a proposto un nuovo algoritmoin grado di poligonizzare super�ci isopotenziali aventi caratteristiche diverse; inol-tre tale modi�ca mantiene intatta la �loso�a di base dell'algoritmo originario. Il

8

1 { Introduzione

capitolo 2 introduce l'algoritmo Shrinkwrap; il capitolo 3 descrive pi�u speci�cata-mente i problemi di tale algoritmo e i casi in cui si presentano; nel capitolo 7.1vengono presentate le modi�che apportate all'algoritmo originale. Nel capitolo 7.3vengono tratte le conclusioni �nali, e, in�ne, l'appendice A contiene il documento diricerca conclusivo di questo lavoro, rilasciato alla Technische Universiteit Eindhoven(Olanda).

9

2

L'algoritmo Shrinkwrap

Presentiamo ora l'algoritmo iniziale, che produce una poligonizzazione di una su-per�cie implicita isopotenziale, de�nita da un insieme di elementi di base. Contra-riamente agli approcci precedenti, basati su una struttura a griglia, la locazione deipunti della struttura approssimante �e arbitraria e i triangoli che la compongono sonodi dimensioni e forme di�erenti secondo la curvatura della super�cie sottostante. Inpi�u �e possibile determinare il grado di accuratezza di tale approssimazione. Nei capi-toli seguenti viene brevemente introdotto l'algoritmo Shrinkwrap; nel paragrafo x2.1vengono introdotti dei prerequisiti matematici necessari per l'esposizione dell'algo-ritmo; il paragrafo x2.6 presenta l'algoritmo vero e proprio, mentre nel capitolo x2.7viene presentata una breve analisi quantitativa dei risultati ottenuti.

2.1 Approssimazione della super�cie

Prima di introdurre i concetti che sono alla base dell'algoritmo �e necessario fare dueosservazioni.

In primo luogo, costruendo una tassellatura adattativa per la super�cie, il para-metro pi�u ovvio come indicatore della risoluzione della tassellatura �e la curvaturalocale della super�cie. In molti casi una misura di questa curvatura locale (la cur-vatura Gaussiana) pu�o essere calcolata analiticamente. Quando per�o la super�cieviene approssimata da un certo insieme di campioni connessi da una qualche strut-tura, l'interpretazione da dare al valore della curvatura nei punti considerati non �edel tutto chiara. Per esempio, la super�cie potrebbe avere una elevata curvaturatra due campioni adiacenti ma, se fosse piatta in un intorno dei medesimi, potrem-mo non accorgercene e la struttura creata potrebbe non rispecchiare fedelmente lecaratteristiche della super�cie sottostante.

10

2 { L'algoritmo Shrinkwrap

Per permettere all'algoritmo di essere il pi�u generale possibile, invece della cur-vatura Gaussiana (che �e un attributo della super�cie che vogliamo approssimare),vengono utilizzati dei parametri della struttura generata e successivamente vengonodedotte delle stime sulla deviazione massima tra la super�cie e la struttura stessa.

Una seconda osservazione riguarda le primitive usate per la tassellatura. Lascelta migliore, per diversi motivi, sembra essere quella di utilizzare primitive trian-golari: un triangolo ha il minor numero possibile di gradi di libert�a (9 coordinatedei vertici), �e sempre convesso e giace sempre su un piano. Perci�o si pu�o intro-durre una struttura triangolare in cui ogni triangolo approssimi una sezione dellasuper�cie globale. Come conseguenza, l'analisi dell'errore implica l'uso della geo-metria di�erenziale delle super�ci; per aggirare alcune delle di�colt�a tecniche chequesta introduce le corde verranno considerate come approssimazioni di curve sullasuper�cie equipotenziale. Questo signi�ca che l'approssimazione della struttura sar�acostituita da una struttura triangolare, ma l'analisi dell'errore verr�a e�ettuata suilati dei triangoli, cio�e le corde, invece che sui triangoli stessi.

Considerando queste due osservazioni, possiamo enunciare una serie di concettidi base; �, � and Lmax sono parametri reali usati per caratterizzare l'algoritmo.

� la super�cie �e de�nita da f(r) = 0, dove r 2 R3.

� una corda �e una quadrupla (a;b;na;nb) 2 R3 � R3 � R3 � R3, dove f(a) =f(b) = 0, na = rf(a) e nb = rf(b).

� la super�cie �e detta accettabile se e solo se per ogni corda della super�cie6 (na;nb) � �ja� bj, dove 6 (p;q) �e l'angolo tra p e q.

� una corda �e accettabile solo se 6 (na;nb) � � e ja� bj � Lmax

� un triangolo, composto da tre corde, �e chiamato accettabile solo se tutte e trele corde sono accettabili.

L'algoritmo cerca di costruire una struttura composta da triangoli accettabili.Di seguito vengono introdotti alcuni lemmi utilizzati per la stima dell'errore dellatassellatura come approssimazione della super�cie. In questi lemmi viene fatto usodella cosiddetta approssimazione di curva piana, che assume che, per ogni corda,le normali na e nb e la stessa corda siano coplanari. In questo modo una cordaintroduce un segmento di curva piana, p(t) situata nella super�cie f(r) = 0 tra ipunti a e b, perpendicolare in questi punti rispettivamente a na e nb. La curva pianaintrodotta viene chiamata l'ombra della corda perch�e pu�o essere vista come l'ombragenerata dalla corda sulla super�cie se illuminata da una sorgente luminosa postasul piano a cui appartengono la corda e le normali nei suoi estremi. Si assume chela corda sia parametrizzata dalla sua lunghezza d'arco.

11


Piuttosto che derivare asserzioni sulla massima deviazione tra punti della strut-tura triangolare e punti della super�cie implicita, si possono derivare asserzioni sullamassima deviazione tra le corde della struttura e le loro ombre. In questo modo leombre servono da concetto intermedio tra la tassellatura e la super�cie equipoten-ziale.

2.1.1 Cos'�e una super�cie accettabile

Per la prova dei seguenti lemmi si prega il lettore di fare riferimento a ([Overveld 93]).Il primo lemma collega la propriet�a di accettabilit�a di una super�cie con la massimacurvatura dell'ombra di una qualsiasi corda.

Lemma 1 In una super�cie accettabile, la curvatura j�p(t)j per ogni ombra di cordap(t) �e sempre minore o uguale a �

2.1.2 Stima dell'errore in caso di curvatura monotona

Assumendo che per una data corda la sua ombra abbia una curvatura monotona(cio�e che sia dappertutto 6 ( _p;�p) = ��=2, o, per dirlo diversamente, che la corda ela sua ombra formino una regione convessa), il lemma 2 fornisce un limite superioreper la deviazione relativa tra una corda e la sua ombra.

Lemma 2 Nel caso una corda abbia un'ombra monotona, la deviazione relativamassima �e 1

2 tan�

2 :

Si noti che questo risultato vale indipendentemente dal valore di � e che, aldiminuire di �, la deviazione massima sar�a sempre pi�u piccola.

2.1.3 Stima dell'errore nel caso generale

Innanzitutto bisogna far notare che la deviazione relativa massima pu�o essere illi-mitata nel caso di super�ci autointersecanti, come si pu�o vedere in �g. 2.1a. Sela super�cie non �e autointersecante (e questo �e il caso delle super�ci equipotenzialiche stiamo trattando), la deviazione massima �e illimitata solo se la curva ha unatangente che �e perpendicolare alla corda, come mostrato in �gura 2.1b. Si pu�o di-mostrare che, dato un valore massimo � per la curvatura di un'ombra di corda, sipu�o determinare una lunghezza massima Lmax per la corda, in modo tale che, setutte le corde sono accettabili rispetto a Lmax, non si presentino situazioni in cui latangente �e perpendicolare alla corda e quindi non ci siano deviazioni illimitate.

12


(a) (b)

A AA B

BBBA n nnn

Figura 2.1. Errore illimitato nel caso di super�ci autointersecanti (a) e nel casodi super�ci non autointersecanti (b).

Lemma 3 Se Lmax � 2�(1 � sin�=2), non ci sono deviazioni illimitate.

Il lemma 4 d�a un limite superiore per la deviazione relativa massima nel caso diuna corda di lunghezza minore di Lmax.

Lemma 4 Nel caso di una super�cie non autointersecante, la deviazione relativa

tra una corda e la sua ombra �e minore o uguale a1+cos(�

2)�p3

1�sin(�2)

Riassumendo i risultati dei lemmi introdotti precedentemente, abbiamo:

� data la super�cie equipotenziale che vogliamo poligonizzare, determiniamo ilparametro �;

� utilizzando il lemma 2 calcoliamo un valore di � che assicuri una data tolleranzarelativa in regioni monotone della super�cie;

� il lemma 3 ci permette quindi di calcolare un Lmax che eviti il veri�carsi dierrori non limitati;

� dato � il lemma 4 fornisce un limite superiore all'errore in qualsiasi punto dellasuper�cie.

13


2.2 Un algoritmo per arrivare ad una struttura

triangolare accettabile

Una carica puntiforme �e una tupla (R;�) dove R �e un punto in R3 e � �e la sua carica.Il potenziale dovuto a questa carica nel punto r �e

f(r) =�

jr �Rj (2.1)

La super�cie equipotenziale al valore di potenziale 1 �e l'insieme dei punti r taliche

1 =�

jr �Rjoppure

fr 2 R3jjr �Rj = �g

in altre parole �e una sfera centrata in R di raggio �. Una distribuzione di cariche �eun insieme di N cariche puntiformi (�e possibile comunque generalizzare utilizzandoaltri tipi di primitive come linee, triangoli, quadrilateri, ecc: : : )

f(Ri;�i) 2 R3 �Rji = 0 � � �N � 1g

Per un insieme di cariche distribuite nello spazio, la super�cie equipotenziale �e datada

fr 2 R3jXi

�ijr �Rij = 1g

Le super�ci equipotenziali possono avere forme abbastanza complicate. Nel capito-lo 2.1 abbiamo ricavato dei criteri per stabilire se un insieme di corde approssimasu�cientemente una super�cie. Rimane da discutere:

� come ottenere dei vertici sulla super�cie.

� come garantire che venga generata una super�cie chiusa.

� come garantire che questa super�cie sia approssimata soltanto da corde accet-tabili.

Dopo aver introdotto questi punti nei paragra� x2.3, x2.4, x2.5, nella sezione x2.6viene presentato l'algoritmo completo.

14


2.3 Come ottenere dei vertici sulla super�cie

La tavola A.1 rappresenta una sezione bidimensionale di una distribuzione di cariche;i colori indicano il valore del potenziale nei vari punti. Osserviamo che le super�ciequipotenziali

fr 2 R3jXi

�ijr �Rij = V0g

con V0 < 1 (cio�e le super�ci che passano dal viola al giallo) hanno una forma che�e meno avviluppata, mentre le super�ci equipotenziali con V0 > 1 lo sono di pi�u.Il caso estremo della prima situazione �e V0 = 0, che produce una sfera di raggioin�nito.

Guardiamo pi�u attentamente la relazione tra V0 e la massima curvatura dellasuper�cie equipotenziale. La curvatura della super�cie si pu�o calcolare come unamatrice C, di�erenziando due volte la funzione f(r):

C = r : rf(r) =Xi

�ijr �Rij5Ai

dove

Ai =

0B@jr �Rij2 � 3Ti;xx �3Ti;yx �3Ti;zx

�3Ti;xy jr �Rij2 � 3Ti;yy �3Ti;zy�3Ti;xz �3Ti;yz jr �Rij2 � 3Ti;zz

1CA

e ad esempio

Ti;xx = (r:x�Ri:x)(r:x�Ri:x)

Essendo jr�Rij2 = Ti;xx+Ti;yy+Ti;zz, nessun elemento di Ai �e in valore assolutopi�u grande di 3jr �Rij2 e quindi ogni elemento c di C �e limitato da

jcj � 3Xi

�ijr �Rij3 (2.2)

Considerando un punto r sulla super�cie a potenziale V0, si ha

Xi

�ijr �Rij = V0

Se tutti i �i sono non negativi, per tutti gli i abbiamo

jr �Rij > �iV0

15


Utilizzando questo risultato in (2.2) otteniamo:

jcj � 3Xi

�i(�i=V0)3

oppure

jcj � 3V 30

Xi

1

�2i

Quindi, la curvatura massima della super�cie si riduce drasticamente se si riduceV0, e come conseguenza anche � si riduce.

Da questa osservazione si pu�o trarre il seguente procedimento per ottenere deivertici sulla super�cie determinata da V0 = 1. Per prima cosa bisogna trovaredei vertici su una super�cie equipotenziale ad un valore piccolo rispetto a V0. Dalmomento che quest'ultima super�cie ha dappertutto una curvatura molto minore,questo dovrebbe essere relativamente facile. Successivamente si pu�o incrementare inpiccoli passi V0 �no al valore V0 = 1, spostare i vertici sulle super�ci isopotenzialiintermedie e, se necessario, modi�care l'insieme delle corde in modo da mantenereuna struttura poligonale costituita da sole corde accettabili. Se gli incrementi diV0 sono abbastanza contenuti, lo sono, di conseguenza, anche gli incrementi dellacurvatura massima e ogni passo successivo dovrebbe risultare abbastanza semplice.

In pi�u, utilizzando questo approccio a passi, possiamo utilizzare una espansionedi Taylor troncata al primo ordine per calcolare la nuova posizione di un verticequando il valore di V0 viene incrementato di una quantit�a �V . Si assuma che rsia sulla super�cie f(r) = V0, e quindi sia f(r) = V0; stiamo cercando una nuovaposizione, r + �, tale che

f(r + �) = V0 +�V

Una espansione di Taylor attorno a � = 0 d�a:

f(r + �) = f(r) + � � rf(r) +O(j�j2) = V0 +�V

oppure considerando che f(r) = V0

�V = � � rf(r)

Questo per�o non ci dice in che direzione debba essere preso �. Una scelta ragionevolepu�o essere

� = �rf(r)

16


che d�a come risultato:

� =�V

rf(r) � rf(r)

La nuova posizione �e quindi data da:

r +�Vrf(r)

rf(r) � rf(r) (2.3)

2.4 Come ottenere una super�cie chiusa

La pi�u semplice struttura chiusa costituita da poligoni consiste in un tetraedro,composto da 4 vertici, 4 triangoli e 6 corde. Come alternativa pu�o essere usato unottaedro, che ha 6 vertici, 8 triangoli e 12 corde. Nel caso che una o pi�u delle cordenon siano accettabili, devono essere divise. La �gura 2.2 mostra come un triangolopossa essere diviso in triangoli pi�u piccoli. Nel caso della divisione di due cordesono possibili due alternative: nel caso jMAB �Cj < jMBC �Aj la nuova corda sar�aMAB � C, altrimenti sar�a MBC �A.

C

AC

A MB

M

C

M

A MB

M

C

BA

A MB

M

C

A

C

B

M

A

M

C

M

BM

A MB

M

C

AB

AC BC

BC

BC

AB AB

BC

BC

BC

AB

BC

AB

M

Figura 2.2. Lo schema di suddivisione dei triangoli.

17


Lo schema di suddivisione pu�o essere utilizzato per assegnare coordinate di su-per�cie a tutti i nuovo vertici creati. Supponendo che ai 4 o 6 vertici originali sianostate assegnate delle coordinate super�ciali, le coordinate super�ciali che devonoessere assegnate ad un nuovo vertice m possono essere de�nite come la media dellecoordinate super�ciali dei due vertici estremi dell'arco in cui m viene generato.

2.5 Come ottenere una tassellatura accettabile

Dalla de�nizione di corda accettabile sappiamo che il modo migliore per rimediaread una corda non accettabile �e quello di dividerla, generando un nuovo vertice che sitrovi sulla super�cie equipotenziale. Un modo semplice per e�ettuare tale operazio-ne �e illustrato nelle �gure 2.3a-d. La corda di partenza �e A�B1 in �gura 2.3a; M1 �eil punto medio della corda A�B1. Le curve punteggiate rappresentano la direzionedel gradiente del campo vicino alla super�cie equipotenziale. Se spostiamo il puntoM1 secondo l'equazione (2.3), arriviamo in M 0

1, come indicato dalla linea tratteg-giata. Bisogna notare che in genere M 0

1 non si trover�a esattamente sulla super�cie,dal momento che si utilizza solamente una approssimazione lineare per f(r). Peravvicinare il punto alla super�cie, bisogna iterare (2.3) �no a che non lo si possaconsiderare su�cientemente vicino; la corda B1 �M 0

1 sar�a molto probabilmente ac-cettabile, anche perch�e �e molto pi�u piccola del necessario, mentre molto di�cilmentelo sar�a M 0

1�A. Perci�o, come illustrato in �gura 2.3b, dobbiamo ripetere il processosulla corda A�B2. Alla �ne otterremo un gran numero di piccole corde super ue,come illustrato in �gura 2.3d. La principale causa di questo comportamento �e dovu-ta al fatto che vengono tratte informazioni sulla geometria e sui gradienti del campodai punti M1, M2, ecc: : : , che possono essere lontani dalla super�cie. Questo pu�ocausare una lenta convergenza e la creazione di molte piccole corde non necessarie.

Una strategia pi�u e�ciente deve utilizzare informazioni pi�u a�dabili, cio�e in-formazioni derivanti da punti che si trovino gi�a sulla super�cie. Nella �gura 2.4ala con�gurazione �e identica a quella in �gura 2.3a. Tramite le normali nei puntiestremi, �e possibile approssimare l'ombra della curva con una curva di Bezier p(t),dove t �e la parametrizzazione d'arco. Tale curva passa per gli estremi A e B dellacorda ed �e ivi perpendicolare alle normali nA e nB. Prendendo come punto M1 ilpunto medio parametrico di p(t), cio�e p(1=2), e iterando (2.3), otteniamo un puntoM che �e verosimilmente pi�u vicino alla super�cie equipotenziale del punto M1 in�gura 2.3a; quindi, anche il gradiente calcolato in M �e verosimilmente pi�u adeguatoper ottenere corde accettabili del gradiente calcolato in M1. In questo caso M �Bpu�o gi�a essere considerata accettabile, mentre la corda A�C (come nell'esempio in�gura 2.4b) pu�o aver bisogno di una ulteriore suddivisione.

18


n n

1

2

3

3

M’4

4M

(a) (b)

(c) (d)

n n

1

2

3

M’

M3

3

n n

1

2

M

M’

2

2

n nM

M’1

11A B

A B

AA B

B

B

A

A

B

BB

B

B

AA B

B

BB

Figura 2.3. Costruzione di un nuovo vertice ripetendo la suddivisione di una cordanon accettabile e spostando il nuovo vertice lungo il gradiente del campo.

n n

1

n

M’

M

(a) (b)

AA

C

C

B

B

n n

1

M’

M

B

B

AA

Figura 2.4. Costruzione di un nuovo vertice de�nito come il punto medio para-metrico della curva passante per A e B e ivi tangente, rispettivamente, a nA e

nB.

2.6 L'algoritmo

Seguendo la notazione introdotta nelle sezioni precedenti, siamo ora in grado discrivere l'algoritmo completo. I vertici sono de�niti come quadruple (r;E;V;d) 2R3 � R3 � R � R3); l'attributo r �e la posizione; E �e il gradiente rf(r); V �e il

19


valore del potenziale f(r), e d �e il vettore di spostamento che deve essere applicatoa questo vertice.

Le corde contengono due riferimenti ai vertici negli estremi, e due riferimentiai due triangoli adiacenti. In pi�u una corda ha associato un valore booleano n perindicare se �e accettabile.

La di�erenza di potenziale�V �e una frazione del potenziale �nale V0, ad esempio�V = V0=10, e per V0 sar�a usato il valore V0 = 1. Usando queste convenzioni,l'interpretazione della carica � �e semplicemente "il raggio della sfera equipotenzialese � fosse l'unica carica della distribuzione".

L'insieme di vertici di partenza �e costituito dai vertici dell'oggetto iniziale (untetraedro o un ottaedro); si assume che esso sia su�cientemente grande da essereesterno alla intera super�cie equipotenziale per il valore iniziale 1=10. Tutti i verticiv hanno inizialmente v:V = 0, v:E punta radialmente verso l'interno, e v:d =v:E=(v:E � v:E).

In prima approssimazione, l'algoritmo (in pseudo-Pascal) ha la seguente strut-tura:

beginV0:=0;while V0 < 1.0 dobegin

V0:=V0+DeltaV;S1;f tutti i vertici sono sulla super�cie; per ogni vertice v abbiamov.V=f(v.r)v.E=grad f(v.r)v.d=(V0-v.V)*v.E=(v.E�v.E)g

S2;f tutti i vertici sono sulla super�cie; per ogni vertice v abbiamov.V=f(v.r)v.E=grad f(v.r)v.d=(V0-v.V)*v.E=(v.E�v.E)

tutte le corde sono accettabiligend;f tutti i vertici sono sulla super�cie;tutte le corde sono accettabili e V0=1.0g

end;

dove S1 �e:

20


for tutti i vertici v dorepeat

v.r:=v.r+v.d;v.V:=f(v.r);v.E:=grad f(v.r);v.d:=(V0-v.V)*v.E=(v.E�v.E);

until jv.dj <Epsilon;

e S2 �e:

azzerare l'etichetta di tutti i triangolifor tutte le corde c dobegin

c.n := "c non e` accettabile"f per decidere l'accettabilita` o meno di una corda, usare e1.E e e2.Ecome direzioni delle normali in e1.r e e2.r per gli estremi e1 ed e2 della corda g

end;while ci sono corde non accettabili dobegin

for tutte le corde c con c.n := true dobegin

creare un nuovo vertice w per la corda c, come spiegato in x2.5;spostare w sulla super�cie come in S1;etichettare i due triangoli adiacenti ad e;creare due nuove corde per i frammenti di c, c1 e c2;c1.n := "c1 non e` accettabile"c2.n := "c2 non e` accettabile"rimuovere la corda c;

end;f tutte le corde inizialmente non accettabilisono state divise, ma nuove corde non accettabili possono essere state create gfor tutti i triangoli etichettati t dobegin

dividere t come spiegato nella sezione x2.5;creare 2,3 o 4 nuovi triangoli;for tutte le nuove corde generate ci do ci.n := "ci non e` accettabile";rimuovere il triangolo t;f tutti i triangoli delimitati inizialmente da corde non accettabili sono stati divisi,ma nuove corde non accettabili possono essere state generate g

end;

21


end;

2.7 Risultati ottenibili

Una breve analisi dei risultati ottenibili con questo algoritmo, pu�o essere e�ettua-ta tenendo conto del seguente fatto: un algoritmo di poligonizzazione come quellopresentato, deve valutare una funzione implicita per un certo numero di punti nellospazio; l'e�cienza di questo algoritmo, cos�i come quella di altri algoritmi simili, di-pende dal numero di queste valutazioni di funzioni implicite (IFE, Implicit FunctionEvaluations) mediate sul numero di triangoli generati (IFE Per Triangle - IFEPT).

L'algoritmo introdotto nel paragrafo precedente, �e stato implementato. Dall'a-nalisi dei risultati ottenibili, si ricava che l'e�cienza del metodo non �e fortementein uenzato dal numero di iterazioni utilizzate per raggiungere la super�cie �nale.Ad esempio, presa una istanza campione che permette di disegnare un pinguino, ilnumero ottimo di iterazioni �e stato valutato in 7, che d�a come risultato in terminidi IFEPTS 7,06. Se utilizzassimo un numero di iterazioni maggiore, ad esempio 11,otterremmo 8,38 valutazioni per triangolo; solo e�ettuando un numero di iterazionimolto pi�u grande (ad esempio 30) si avrebbe una sensibile riduzione dell'e�cienza(circa 20,75 valutazioni per triangolo). La qualit�a del risultato �nale, comunque, non�e assolutamente alterata dal numero di iterazioni e�ettuata non appena l'algoritmoconverge.

Le tavole B.1 e B.2 illustrano due esempi dei risultati producibili. La primatavola mostra un pinguino insieme alla struttura triangolare �nale; qui l'adattativit�adell'algoritmo �e chiaramente visibile. Il collo e la parte interna delle gambe, adesempio, sono composte quasi esclusivamente da triangoli molto sottili, mentre nellaparte sferica della testa ne troviamo di pi�u aperti. Nelle regioni di maggior curvaturainoltre, la struttura triangolare ha una risoluzione pi�u elevata. L'aspetto �nale delpinguino �e sicuramente un p�o naif, ma il tocco artistico �e una variabile di�cilmentequantizzabile in termini matematici.

La tavola B.2 mostra il comportamento della struttura in relazione ad una su-per�cie quasi piatta: i triangoli che la compongono sono uniformemente distribuitie quasi equilateri.

I vantaggi che o�re questo algoritmo sono per�o limitati dal fatto che non permettedi poligonizzare qualsiasi tipo di super�cie isopotenziale. Infatti esso si basa sullapremessa che le super�ci in analisi non siano autointersecanti; purtroppo non �esempre possibile assicurare che questa condizione sia veri�cata.

Occorre quindi capire quando e perch�e si presentano situazioni di tale genere e

22


in che modo occorre modi�care l'algoritmo originale per tenerne conto. Questi temisaranno a�rontati nei successivi capitoli.

23

3

Limiti dell'algoritmo

Come gi�a accennato in precedenza nell'introduzione e nel capitolo x2, l'algoritmoShrinkwrap, a causa del metodo utilizzato per costruire una poligonizzazione adat-tativa, �e in grado di operare solo con un sottoinsieme limitato di super�ci implicite.Le super�ci analizzate sono infatti de�nite come super�ci di livello di un camposcalare, generato da un insieme di elementi di base; per costruire una tassellaturadella super�cie isopotenziale scelta, avente un potenziale V0, si parte da un oggettoiniziale che "avvolge" una super�cie ad un valore molto minore di V0 e si procedea passi spostando i vertici su super�ci a potenziali maggiori, suddividendo per ognipasso le corde e i triangoli non accettabili secondo le speci�che del paragrafo x2.5.Questo procedimento si basa per�o sulla premessa che le super�ci in analisi non sianoautointersecanti; tale assunzione deve essere veri�cata sia per le super�ci �nali siaper quelle intermedie utilizzate dall'algoritmo.

I problemi sorgono nei casi in cui la distribuzione delle cariche introduca dei punticritici all'interno del campo di potenziale, a causa dei quali le super�ci equipotenzialicambiano, al crescere del valore del potenziale, le loro caratteristiche geometriche etopologiche. E' possibile, ad esempio, che una singola super�cie si scinda in due opi�u super�ci separate oppure che una super�cie aumenti il suo ordine di connessione(cio�e si generi un vero e proprio buco al suo interno). Se si veri�ca questa possibi-lit�a, occorre modi�care la struttura approssimante generata in modo da mantenerlacoerente con le nuove caratteristiche assunte dalla super�cie isopotenziale; l'ogget-to di partenza, un tetraedro o un ottaedro, �e infatti una singola super�cie chiusasemplicemente connessa.

Se non si e�ettua questa operazione, una parte della struttura diventa irrime-diabilmente non accettabile nel proseguimento del processo. Ogni suddivisione ditriangoli e corde non accettabili dar�a luogo nuovamente ad un insieme di triangoli ecorde non accettabili, bloccando l'algoritmo.

24

3 { Limiti dell'algoritmo

Inoltre i cambiamenti delle super�ci isopotenziali passano attraverso super�ciautointersecanti, che rappresentano il punto di contatto tra le diverse con�gurazioni.Da questo deriva che alcune delle assunzioni fatte nel capitolo x2 non sono pi�u valide;ad esempio, si pu�o veri�care una deviazione relativa illimitata anche se le cordehanno tutte una lunghezza minore di Lmax (si veda la �gura 2.1).

Nei prossimi paragra� cercheremo di introdurre pi�u approfonditamente il pro-blema. Nel paragrafo x3.1 verr�a de�nito cos'�e un punto critico, quali sono le suecaratteristiche e quali sono i possibili cambianti della super�cie; il paragrafo x3.2spiegher�a come si comporta la struttura creata dall'algoritmo, mentre nel paragra-fo x3.3 si spiegher�a in quali casi si possono considerare validi i lemmi utilizzatidall'algoritmo.

3.1 Cos'�e un punto critico

Un punto critico, o punto singolare, di una funzione implicita f(r) = 0, r 2 R3, �eun punto r0 in cui il gradiente della funzione �e nullo, cio�e

rf(r0) = 0 (3.1)

e

det(Jr0) 6= 0

dove J �e il Jacobiano di rf(r) ([Artley 65]).Si osservi come esempio la �gura 3.1. Il punto critico generato dalla con�gura-

zione di cariche si trova nell'origine. Le due cariche hanno lo stesso valore di � esono disposte lungo l'asse z simmetricamente rispetto all'origine, per cui i contributidelle due sorgenti al gradiente nell'origine si annullano. La �gura 3.1a mostra comeappaiono nel piano yz le super�ci equipotenziali generate dalla distribuzione; l'an-damento delle linee di usso �e rappresentato in �gura 3.1b. Un insieme di linee di usso si interseca nel punto critico, ma in questo punto super�cie equipotenziale elinee di usso non si intersecano ad angolo retto: questa caratteristica �e peculiare delcomportamento di un punto critico e non si veri�ca in nessun altro punto del camposcalare. Come si pu�o notare, la super�cie isopotenziale che passa per il punto critico�e autointersecante ed �e l'unica con tale propriet�a. Per ottenere una rappresentazionetridimensionale di entrambi i diagrammi, li si pu�o ruotare attorno all'asse z.

I tipi di cambiamenti determinati nelle super�ci equipotenziali da punti criticisono essenzialmente riconducibili a due casi. Il primo �e quello dato da con�gurazio-ni simili a quella mostrata in �gura 3.1; inizialmente abbiamo una unica super�cie

25


ρ+

ρ+

Superfici equipotenziali(a)

Direzione delle linee di flusso(b)

y y

zz

Figura 3.1. Super�ci equipotenziali e linee di usso sul piano yz per due caricheequivalenti.

equipotenziale che, riducendosi all'aumentare del potenziale, si spezza in due di-stinte super�ci. Nel punto critico la super�cie si concentra in un unico punto Unarappresentazione tridimensionale di tali super�ci si pu�o trovare nelle tavole D.1-6.

Un caso diverso �e quello in cui si crea un "buco" nella super�cie. Si consideri adesempio la �gura 3.2, in cui �e mostrato un toro a densit�a di carica uniforme; anchein questo caso il punto critico �e situato nell'origine (la somma di tutti i contributial gradiente �e nulla). Se facciamo una sezione dello spazio lungo il piano yz, lacon�gurazione delle super�ci equipotenziali e delle linee di usso �e simile a quellaillustrata in �g 3.1. In questo caso, per�o, se vogliamo ottenere una rappresentazionetridimensionale, bisogna e�ettuare una rotazione dei due diagrammi lungo l'asse y.La super�cie si concentra nel punto critico ma ora, invece di avere due super�cidistinte, quando il valore di potenziale supera quello del punto critico all'internodella super�cie si forma un buco, e questa incrementa il suo ordine di connessione(tavole E.1-7).

Possiamo quindi associare un "tipo" ad ogni punto critico a seconda del com-portamento che determina nella super�cie critica, cio�e una singolarit�a pu�o essere unbuco oppure una rottura.

L'insieme delle corde non pu�o adattarsi ai cambiamenti della super�cie ma deveessere necessariamente modi�cato. Occorre prima capire cosa succede in un intornodel punto critico.

26


z

y

x

d

d

d

d

Figura 3.2. Toro a densit�a di carica uniforme posizionato sul piano y = 0.

3.2 Comportamento della struttura triangolare

Dopo aver analizzato qual'�e il comportamento delle super�ci reali nell'intorno di unpunto critico, dobbiamo vedere cosa succede alla tassellatura creata dall'algoritmoin corrispondenza dei cambiamenti topologici della super�cie sottostante.

Secondo le de�nizioni del capitolo x2, la super�cie �e approssimata da un insiemedi triangoli i cui lati introducono sulla super�cie una serie di curve piane, le ombredelle corde. Per la determinazione di tali curve si utilizza l'approssimazione di curvapiana introdotta nel paragrafo x2.1. Chiamiamo per semplicit�a valore critico il valoredel potenziale del punto critico e super�cie critica la super�cie corrispondente a talepotenziale.

Consideriamo ora una con�gurazione di cariche che introduca nel campo unpunto critico; si prenda ad esempio quella di �gura 3.1. Le curve a potenzialecrescente ottenute dall'intersezione delle super�ci isopotenziali con un piano passanteper il punto critico e per le due cariche sono mostrate nelle �gure 3.3, 3.4 e 3.5. Ilcomportamento di tali intersezioni, come gi�a mostrato nel paragrafo x3.1, �e ugualeper entrambi i tipi di punti critici. Sia V0 il potenziale della super�cie e Vc ilvalore critico. Analizziamo il comportamento della corda A�B (appartenente allastruttura) al crescere di V0.

La super�cie di �gura 3.3 ha un potenziale minore del valore critico; gli estremiA e B della corda disegnata si trovano sulla super�cie equipotenziale e la corda

27


A B

Figura 3.3. Super�cie equipotenziale per V0 < Vc

approssima correttamente una curva di super�cie.

A B

Figura 3.4. Super�cie equipotenziale per V0 = Vc

Incrementando il valore di V0 �no a Vc si raggiunge la super�cie critica, mostratain �gura 3.4, che passa per il punto critico ed �e autointersecante. I vertici A eB della corda di partenza, supponendo che essa sia accettabile e che quindi nonvenga divisa, vengono spostati sulla nuova super�cie. A � B rappresenta ancoral'approssimazione di una curva sulla super�cie.

In �gura 3.5 �e invece rappresentata una super�cie ad un valore appena maggioredel valore critico; la super�cie si �e spezzata in due super�ci distinte oppure haincrementato il suo ordine di connessione. I punti A e B si trovano sulla super�ciema la corda non �e pi�u coerente in quanto non approssima nessuna curva: la super�cievera e propria, infatti, �e "sparita" da sotto la corda nel processo di contrazione. Allostesso modo, anche i triangoli di cui la corda fa parte non approssimano pi�u nessunaregione della super�cie. La super�cie isopotenziale ha cambiato le sue propriet�ageometriche mentre la struttura approssimante non �e stata in grado di adeguarsi.

28


A B

Figura 3.5. Super�cie equipotenziale per V0 > Vc

Occorre far notare che la corda A�B pu�o ancora essere accettabile e in generelo �e, in particolare quando il potenziale della super�cie �e su�cientemente vicino alvalore critico. Questo perch�e i criteri di accettabilit�a si basano sui valori limite di �e �; la super�cie di �g 3.5 ha in realt�a caratteristiche particolari. Questa situazionesar�a trattata nel paragrafo x3.3.

3.3 Validit�a dei lemmi

Data la possibilit�a che si generino super�ci autointersecanti, vengono a cadere moltedelle considerazioni di base fatte nel capitolo 2 durante la presentazione dell'algo-ritmo. Per mantenerne intatta la struttura e la �loso�a di fondo, occorre per�oconsiderare validi i lemmi 3 e 4. Il lemma 3 stabilisce la lunghezza massima che pu�oassumere una corda in funzione di � e � a�nch�e non si veri�chino deviazioni illimi-tate mentre il lemma 4 fornisce un limite superiore per l'errore di approssimazionein qualsiasi punto della super�cie.

Occorre fare due importanti considerazioni. In primo luogo, come si vede in �gu-ra 3.4 la super�cie equipotenziale pu�o essere autointersecante; facendo riferimentoalla �gura 2.1(a), questo signi�ca che la deviazione tra la corda e la sua ombranon �e limitata. Possiamo per�o considerare il seguente fatto: l'oggetto iniziale �e unastruttura chiusa che avvolge "esternamente" la super�cie ad un potenziale piccolorispetto al valore �nale; vertici e archi sono ripetutamente spostati su super�ci apotenziali crescenti, assicurando che ad ogni passo la struttura creata sia compostasolo da corde e triangoli accettabili. Se la super�cie iniziale non �e autointersecante(e possiamo garantire che questa condizione sia sempre veri�cata, riducendone incaso di necessit�a il potenziale) si pu�o a�ermare intuitivamente che non si veri�canodeviazioni illimitate tra corde e super�ci. Infatti, dal momento che le corde sono

29


inizialmente esterne alla super�cie e le diverse super�ci sono su�cientemente vicine,non si veri�cano casi in cui una corda diventi interna.

In secondo luogo, nel punto critico la curvatura della super�cie diventa moltoelevata, al limite in�nita. Il parametro � dell'algoritmo rappresenta la massima cur-vatura della super�cie equipotenziale. Il valore scelto per tale parametro permettedi determinare con precisione l'errore della approssimazione costruita ma, scegliendoun � superiore al massimo valore di curvatura che si pu�o determinare nel processodi contrazione della super�cie, si possono ottenere dei criteri di accettabilit�a tropporestrittivi; il valore di Lmax per la super�cie critica, ad esempio, sarebbe (al limite)nullo o comunque estremamente piccolo, determinando nella struttura una elevatadensit�a di triangoli. Per ovviare a questo problema possiamo considerare che insuper�ci a potenziali leggermente superiori del valore critico (ad esempio Vc + �c)la curvatura �e elevata solo in un intorno ristretto del punto critico mentre altrove �elimitata da un valore massimo � che rispetti le caratteristiche descritte nel capito-lo 2 (cio�e, quando le super�ci si riducono all'aumentare del potenziale, si riduce incorrispondenza anche il raggio di curvatura).

Questo signi�ca che nell'intorno speci�cato del punto critico le relazioni intro-dotte non sono pi�u valide; possono quindi risultare accettabili alcune corde (comead esempio la corda A � B in �gura 3.5), che in realt�a non sottendono nessunacurva di super�cie; per queste curve, inoltre, la tangente all'ombra �e perpendicolarealla corda. Questa situazione si veri�ca per�o solo ad un potenziale maggiore delvalore critico; �no a quel punto le assunzioni fatte si possono ritenere valide. Allostesso tempo i lemmi 3 e 4 continuano a valere per tutte le corde che e�ettivamentesottendono una curva di super�cie anche quando la struttura non �e pi�u corretta.

Rimane quindi da discutere:

� come localizzare i punti critici introdotti dalla distribuzione di cariche;

� come assicurare che venga generata una super�cie accettabile ad un potenzialemaggiore del valore critico;

� come identi�care la parte della struttura da eliminare.

Dopo aver introdotto questi punti nei paragra� x4.1, x4.3 e x??, nel capitolo x5verr�a spiegato come si pu�o ricostruire una struttura corretta.

30

4

Singolarit�a e super�ci

Nel capitolo precedente abbiamo dato una de�nizione di singolarit�a, spiegando qualicaratteristiche determina nello spazio circostante. In particolare, le super�ci equipo-tenziali cambiano propriet�a geometriche e topologiche quando il loro valore supera ilpotenziale del punto critico. Questo determina la comparsa nella struttura di cordenon appartenenti alla super�cie, che quindi devono essere eliminate.

E' necessario perci�o conoscere il potenziale (e quindi la posizione) delle eventualisingolarit�a del campo introdotte dall'insieme di cariche che de�nisce la super�cie.Utilizzando un metodo di ricerca per passi (il metodo di Newton-Raphson), �e pos-sibile trovare le radici del gradiente del potenziale partendo da vertici appartenentialla struttura. Inoltre per ricostruire correttamente la super�cie �e necessario ave-re ulteriori informazioni sulla super�cie reale, informazioni che si possono ricavaretramite una approssimazione della funzione di campo nell'intorno della singolarit�a.

Si pu�o quindi enunciare in prima approssimazione una struttura de�nitiva del-l'algoritmo che consideri tutti i problemi enunciati �no ad ora. L'obbiettivo �nale�e quello di evidenziare e rimuovere l'insieme di corde della struttura triangolare chenon f�a parte della super�cie isopotenziale e che dovr�a essere sostituito in modo chela struttura risulti corretta. Il paragrafo x?? introduce un possibile metodo per lamarcatura di tale insieme.

4.1 Come si possono trovare i punti critici

Data una distribuzione di cariche, �e necessario calcolare se essa genera dei punticritici al suo interno. La ricerca di questi punti non pu�o per�o essere e�ettuata inmaniera esaustiva nello spazio; infatti il costo dovuto a questa operazione ne rende-rebbe impraticabile l'applicazione a distribuzioni molto complesse e, anche nei casipi�u semplici, comporterebbe una drastica limitazione dell'e�cienza dell'algoritmo.

31

4 { Singolarit�a e super�ci

Un metodo pi�u e�cace utilizza le caratteristiche della funzione stessa.

La funzione f(r) de�nita come

f(r) =Xi

�ijr �Rij

�e una funzione continua e ha derivata continua. Questo implica che in un intornodel punto critico, il gradiente della funzione tende, con continuit�a, al valore zero.

Il metodo di Newton-Raphson fornisce un modo molto e�ciente per trovarele radici di una funzione se si dispone di una ipotesi di partenza su�cientementebuona; altrimenti, diverge in maniera altrettanto spettacolare: questo fatto fornisceuna indicazione, anche se non ne �e una prova, del fatto che in un intorno del puntoprescelto non si trova nessuna radice dell'equazione.

Nel caso generale, indichiamo con x il generico punto di partenza scelto e con Fl'insieme delle N funzioni che devono essere azzerate nelle variabili xi;i = 1 � � �N :

Fi(x1;x2; : : : ;xN) = 0 i = 1;2; : : : N

Nell'intorno di x ogni funzione Fi pu�o essere espansa con una serie di Taylor

Fi(x+ �x) = Fi(x) +NXj=1

@Fi@xj

�xj +O(�x2)

che si pu�o scrivere, considerando l'insieme di tutte le funzioni, come

F(x+ �x) = F(x) + �x � J+O(�x2)

dove J �e il Jacobiano di F, cio�e la matrice formata dalle derivate parziali @[email protected] i termini di ordine superiore e ponendo F(x+ �x) = 0, otteniamo uninsieme di equazioni lineari che ci permettono di avvicinare l'argomento alla radicedella funzione

�x � J = �F

Le correzioni devono essere in�ne aggiunte al vettore di partenza:

xn+1 = xn + �x (4.1)

iterando (4.1) �no alla convergenza, dove

�x = �F � J�1

32


([Press 86-2]). Nel caso particolare, siamo interessati a trovare le radici di rf , percui la formula (4.1) diventa:

xn+1 = xn �rf(xn) � J�1 (4.2)

dove J �e il Jacobiano di rf . Dei buoni candidati come punti iniziali, potrebberoessere i vertici appartenenti ad una super�cie su�cientemente vicina ad un puntocritico in un suo intorno prestabilito. Infatti l'intersezione tra tale intorno e lasuper�cie �e una regione di minimo della lunghezza del gradiente. Per costruirequesto intorno, per�o, dovremmo sapere in partenza dove si trova il punto critico,e lo stessa osservazione si pu�o fare per la veri�ca di una condizione di su�cientevicinanza tra la super�cie e il punto stesso.

Sfruttando l'approccio a passi dell'algoritmo, si pu�o fare un discorso di�eren-te. Ad ogni passo si pu�o costruire un insieme S di vertici componenti la strutturacreata da utilizzare come punti di partenza per l'applicazione del metodo di Newton-Raphson. Non potendo disporre di ulteriori informazioni, il criterio di appartenenzaall'insieme S sar�a determinato dalla lunghezza del gradiente nel vertice; si pu�o quin-di determinare un valore soglia �n per il quale, detto V l'insieme dei vertici dellastruttura, si abbia:

S = fv 2 V jjrf(v)j < �ng

Il valore di �n scelto deve essere tale da mantenere contenuta la dimensione di S,ma non troppo piccolo per evitare di escludere punti che potrebbero dare dei buonirisultati. Per determinarlo si pu�o operare essenzialmente in due modi:

� de�nire �n come un parametro iniziale;

� calcolare �n in base alle caratteristiche dell'insieme dei vertici della super�cie.

Il primo metodo �e sicuramente il pi�u semplice, ma non �e per niente essibile: illimite pu�o infatti diventare troppo piccolo o troppo grande, determinando insiemivuoti o comprendenti tutti i vertici. Ricalcolando �n per ogni super�cie si pu�ostabilire a priori la dimensione di S, oppure fare in modo che la sua dimensione siauna determinata percentuale della dimensione dell'insieme V dei vertici di partenza.

Siccome i livelli di potenziale sono tali per cui le super�ci successive non sono maitroppo distanti una dall'altra, questo metodo ha un'ottima probabilit�a di convergereverso i punti critici prima che il potenziale abbia superato il valore critico e quindiprima di dover intervenire sulla struttura.

33


4.2 Piani di simmetria della super�cie

Conoscendo la posizione del punto critico, �e possibile determinare una approssima-zione della super�cie reale nelle sue vicinanze. Se facciamo una espansione di Taylorin un intorno del punto critico, indicato con c, i termini lineari si annullano (per lade�nizione stessa di punto critico), per cui otteniamo:

f(c+ x) = f(c) +1

2

Xi

Xj

@2f

@xi@xjxixj + h:o:t:

Sia J la matrice formata dagli elementi @2f=@xi@xj; per il teorema di Schwartz,J �e simmetrica reale e quindi si pu�o dimostrare che gli autovalori della matrice, equindi anche gli autovettori corrispondenti, sono reali e, siccome c �e un punto critico,Jc ha sia autovalori positivi che negativi. Inoltre, esiste una base ortonormale di Jformata da autovettori.

Possiamo e�ettuare un cambio di coordinate, considerando il punto c come nuo-va origine e gli autovettori di J come direzioni degli assi di un nuovo sistema dicoordinate x0, y0 e z0. Scartando i termini di ordine superiore, la super�cie equipo-tenziale pu�o essere approssimata, in un intorno del punto critico, con una quadrica.Possiamo avere due casi distinti. Se la matrice ha un autovalore negativo, abbiamo

f(x0;y0;z0) = f(0) +x02

a2+y02

b2� z02

d2

La super�cie f(x0;y0;z0) = f(0) + � per � > 0 interseca il piano z = 0 in un'ellisse;nel caso � = 0 il piano z = 0 �e tangente alla super�cie f(x0;y0;z0) = f(0), mentre lasuper�cie f(x0;y0;z0) = f(0) �e separata in due met�a dal piano z = 0 nel caso in cui� < 0.

Se invece la matrice J ha due autovalori negativi, otteniamo

f(x0;y0;z0) = f(0) � x02

a2� y02

b2+z02

d2

In questo caso la transizione, all'aumentare di �, �e da un'ellisse a due super�ciseparate.

Le super�ci nei due casi di�erenti per un � positivo (e quindi per un potenzia-le maggiore del valore critico) sono rappresentate in �gura 4.1. Nella �gura 4.1ail punto critico genera un buco all'interno della super�cie equipotenziale; questa,nell'intorno del punto critico, pu�o essere approssimata come un iperboloide ad unafalda. Nel caso in cui la super�cie subisca una frattura (�gura 4.1b) nell'intornodel punto critico si pu�o approssimare con un iperboloide a due falde. I segni degli

34


z

y

x

O

z

x

y

(a) (b)

Figura 4.1.

autovalori sono stati assegnati in modo arbitrario, in modo che, in entrambi i casi,il piano z = 0 sia tangente al cono di transizione tra le due con�gurazioni.

Gli autovettori di J, quindi, si possono considerare come i vettori perpendicolariai piani di simmetria della super�cie equipotenziale nelle vicinanze del punto critico epossono essere associati al punto critico stesso. Vedremo nei capitoli successivi comequesta informazione sia necessaria per il processo di ricostruzione di una strutturacorretta.

Potrebbe anche veri�carsi il caso in cui, invece di un punto critico, si generi una"linea critica"; questa situazione si veri�ca, ad esempio, quando si hanno due lineeparallele in�nitamente lunghe oppure un cilindro cavo in�nito. In questo caso unodegli autovalori �e nullo. L'approssimazione fornita, tuttavia, ci pu�o ancora dareinformazioni utili sul comportamento della super�cie. Nel caso di due autovaloripositivi otteniamo

f(x0;y0;z0) = f(0) +x02

a2+y02

b2

La super�cie f(x0;y0;z0) = f(0) + � per � < 0 �e un'ellisse immaginaria, per � = 0si ottiene una linea (nel caso in esempio l'asse z) mentre per � > 0 si ottiene uncilindro ellittico (�gura 4.2).

Nel caso di autovalori di segno diverso otteniamo

f(x0;y0;z0) = f(0) +x02

a2� y02

b2

35


ε=0

ε>0

x

O

y

z

Figura 4.2.

In questo caso la super�cie di transizione (per � = 0) �e costituita da due pianiintersecanti lungo l'asse z, e si ha un passaggio tra due cilindri iperbolici simmetricirispetto ai piani intersecanti (�gura 4.3).

x

y

O

z

ε<0ε=0ε>0

Figura 4.3.

36


Si potrebbe ancora considerare il caso di due autovalori nulli, ma anche la pos-sibilit�a di averne uno �e comunque solo teorica; non �e pensabile infatti di avere, adesempio, due linee in�nitamente lunghe. Nei casi pratici quindi, questa possibilit�apu�o essere scartata; rimane da considerare il fatto che, in questo caso, l'approssima-zione della super�cie dovrebbe tenere conto anche dei termini di grado pi�u elevato.

4.3 Avvicinandosi al punto critico

A questo punto possiamo enunciare in modo generale come sia possibile modi�carel'algoritmo. I cambiamenti apportati non cambiano la �loso�a di base dell'algoritmooriginario, n�e il suo modo di procedere; in questo modo, per una super�cie de�nitada un insieme di cariche che non generi punti critici, il risultato �nale �e identico aquello che si otterrebbe con la precedente versione. Supponiamo per il momento chevi sia al massimo una singolarit�a nel campo; successivamente vedremo cosa succedequando queste sono in numero maggiore.

L'algoritmo Shrinkwrap procede a passi verso la costruzione della super�cie �nalesemplicemente spostando vertici da una super�cie a quella successiva e dividendocorde e triangoli non accettabili quando necessario. Esiste quindi un insieme divalori del potenziale a cui la super�cie viene "ricomposta" e controllata; questoinsieme viene determinato dal valore iniziale, da quello del potenziale che si vuoleraggiungere e dal numero di passi in cui questo processo deve avvenire.

Abbiamo visto nel paragrafo x3.2 come i cambiamenti delle propriet�a della su-per�cie si veri�chino per potenziali maggiori del valore critico. Il valore critico �e ilpotenziale del punto critico: nel paragrafo x4.1 abbiamo presentato un metodo cheprocede in parallelo al processo di costruzione della tassellatura e che permette dicalcolare la posizione nello spazio del punto critico. Conoscendone la posizione �esu�ciente applicare ad esso la funzione f per calcolare il valore critico. Tenendoconto di ci�o si pu�o procedere nel seguente modo:

1. dati il valore iniziale e �nale del potenziale e il numero delle iterazioni dae�ettuare, si costruisce una lista contenente l'insieme dei livelli di potenzialeattraverso cui deve passare la super�cie.

2. quando una super�cie isopotenziale �e stata raggiunta, si costruisce l'insieme Sdi vertici per un �n appropriato e si applica ai vertici che ne fanno parte il me-todo di Newton-Raphson. Se si trovano dei punti in cui si annulla il gradiente(al cui potenziale si ha una super�cie autointersecante), si modi�ca l'insiemedei valori di potenziale in modo da aggiungerne uno che sia superiore al valo-re critico, ma che sia su�cientemente piccolo da permettere di costruire unatassellatura accettabile (come spiegato nel paragrafo x3.2). Questo valore pu�o

37


essere marcato come "corrispondente ad un punto critico". Le informazionirelative al punto critico (posizione e assi di simmetria della super�cie) vengonomemorizzati in una tabella per essere utilizzati successivamente.

3. quando si raggiunge un valore corrispondente ad un punto critico si deve modi-�care la topologia della struttura creata perch�e assuma le stesse caratteristichedella super�cie sottostante.

38

5

Super�ci di separazione

L'introduzione del concetto di corda rossa permette di identi�care la parte dellastruttura da rimuovere. Vedremo ora pi�u dettagliatamente quali sono le sue carat-teristiche in funzione dei di�erenti tipi di punti critici presenti.

5.1 Cosa fare delle corde rosse

Partiamo da una struttura approssimante la super�cie ad un valore Vc + �c (doveVc �e il valore critico e �c > 0) a cui sia stata applicata una marcatura corretta.Come abbiamo visto nel capitolo 4.3, tale marcatura determina un insieme di archichiamati corde rosse e un insieme di triangoli, detti triangoli rossi, aventi almeno unlato marcato.

A partire dall'insieme di triangoli rossi �e possibile costruire un sottoinsieme T divertici, chiamati rev (REd triangles Vertices).

De�nizione 5.1 Un vertice della struttura appartiene a T se �e un vertice di untriangolo rosso.

Tra gli elementi di T �e possibile de�nire una relazione di vicinato.

De�nizione 5.2 Due rev si dicono vicini se esiste una corda che li connette chenon �e marcata come rossa.

Siccome nella struttura esiste al pi�u una corda che connette due vertici, si ricavache due rev non sono vicini se sono uniti da una corda rossa.

In �gura 5.1 gli archi tratteggiati rappresentato gli archi marcati, mentre i trian-goli rossi sono ombreggiati. Dalla de�nizione si ricava che i vertici A, B, C, D e E

39

5 { Super�ci di separazione

S

A

B

C

D

E

P

Q

R

Figura 5.1. Relazioni di vicinato tra rev

sono rev ma non lo sono P , Q, R e S; siccome gli archi C �D e D � E non sonomarcati, D ha come vicini C ed E ma C non �e vicino di E. Lo stesso discorso valeper A e B che sono vicini; non esistono altre relazioni di vicinato siccome tutti glialtri archi che connettono due rev sono marcati.

Dall'insieme T si possono ricavare due sottoinsiemi (T1 e T2) caratterizzati dalfatto che un qualsiasi rev appartenente ad un sottoinsieme non ha nessuna relazio-ne di vicinato con rev appartenenti all'altro sottoinsieme. Elementi di uno stessoinsieme possono invece essere legati tra loro.

Osserviamo la �gura 5.2; i punti evidenziati rappresentano, nelle diverse situazio-ni che si possono presentare, gli elementi di T , mentre le linee tratteggiate indicano lecorde marcate. Supponiamo di rimuovere queste corde: la super�cie risultante non�e pi�u chiusa e i rev determinano i bordi del taglio che ne ha causato l'apertura. Essisono gli unici vertici della super�cie a�acciati verso lo spazio aperto e, come si pu�ovedere, sono divisi in due gruppi distinti che determinano, insieme agli archi che de�-niscono le relazioni di vicinato, due super�ci che d'ora in avanti chiameremo super�cidi separazione. Facendo riferimento al paragrafo 4.2, le super�ci di separazione sipossono vedere come le intersezioni delle regioni de�nite da f(x0;y0;z0) � f(0) + �c(�c > 0) con due piani di equazione z = k e z = �k, cio�e le super�ci in neretto di�gura 5.3. Nelle tavole C.1 e C.2 sono riportate le strutture costruite dall'algoritmonel caso di un buco e di una rottura.

Queste super�ci sono pressoch�e identiche, mentre la super�cie isopotenziale haun comportamento diverso a seconda del tipo di singolarit�a. Il piano z = 0 dividelo spazio in due regioni ognuna delle quali contiene interamente una sola super�ciedi separazione e sar�a indicato come il piano separatore. Nel caso pi�u generale,l'equazione di tale piano �e de�nita dagli assi di simmetria associati al punto critico.

A partire dai sottoinsiemi di rev �e possibile capire in maniera semplice qual'�e iltipo della super�cie di separazione; �e importante per�o che gli insiemi Ti godano diuna particolare propriet�a.

40


Revs

Archi rossi

Figura 5.2.

De�nizione 5.3 Un sottoinsieme Ti di T si dice corretto se tutti i suoi componentihanno esattamente due vicini rev.

Quello che potremmo aspettarci �e che, data la struttura triangolare, i sottoinsie-mi di T siano sempre corretti. Purtroppo non capita sempre cos�i; �e possibile infattiche si veri�chino casi simili a quello illustrato in �gura 5.4, in cui un arco fa partedella struttura corretta ma emerge dal bordo della super�cie di separazione. L'arcoA non e' marcato; il rev numero 1 ha 3 vicini (�e infatti connesso con altri tre rev

41


x

(b)

z

y

x

O

z

y

(a)

Figura 5.3.

attraverso archi non marcati), mentre il rev numero 2 ha un solo vicino (cio�e il ver-tice 1). Questa situazione pu�o capitare, ad esempio, quando la distribuzione dellecariche �e fortemente asimmetrica; la lunghezza delle corde emergenti �e in generemolto ridotta.

Se uno o pi�u dei sottoinsiemi di T non �e corretto, modi�cando l'insieme dellecorde rosse �e possibile cambiare le caratteristiche di T e dei suoi sottoinsiemi nelmodo seguente:

� per ogni rev con un solo vicino marcare come rosso la corda che li connette;

� per ogni rev con pi�u di due vicini, marcare come rossi tutti gli archi che loconnettono con rev aventi solo un vicino.

Il vantaggio di avere dei sottoinsiemi corretti �e che unendo i rev tra di loronell'ordine stabilito dalle relazioni di vicinato, si forma una curva chiusa (la frontieradella super�cie di separazione de�nita dal sottoinsieme); percorrendo le relazioni divicinato tra rev del sottoinsieme si pu�o eseguire un ciclo tra tutti gli elementi delsottoinsieme stesso.

42


1A

2

Figura 5.4.

5.2 Caratteristiche dell'insieme T

Nelle di�erenti con�gurazioni i sottoinsiemi di T assumono caratteristiche diverseche possono essere sfruttate per stabilire il tipo delle super�ci di separazione.

Quando si veri�ca una rottura, i vertici appartenenti a super�ci di separazionediverse sono connessi tra di loro solamente da una serie di corde rosse. I rev ap-partenenti a ciascun sottoinsieme di T possono essere collegati tra di loro solamenteda relazioni di vicinato; nessun altro tipo di collegamento �e permesso. Una cordarossa, quindi, pu�o collegare solamente due rev appartenenti a due sottoinsiemi di-versi. Le super�ci de�nite dai sottoinsiemi T1 e T2 sono interne alla struttura creata(�gura 5.5).

Quando si veri�ca un buco, invece, i due bordi della rottura non hanno nessuntipo di interconnessione diretta. Due rev di sottoinsiemi di�erenti possono esserecollegati solo attraverso una catena di archi. Invece rev appartenenti allo stesso

43


Superficie equipotenziale

Archi rossi connettono solo

revs appartenenti a sottoinsiemi

differenti

la superficie definita da un sottoinsieme

e’ interna alla struttura creata

Figura 5.5.

sottoinsieme possono essere connessi o da una relazione di vicinato, o da una cordarossa. Le super�ci de�nite da T1 e T2 sono parte integrante della struttura creata(�gura 5.6)

5.3 Come stabilire il tipo delle super�ci di sepa-

razione

Prendiamo un qualunque rev A appartenente ad un sottoinsieme Ti che sia anche unestremo di una corda rossa; chiamiamoB l'estremo opposto della stessa corda. Sup-poniamo che B appartenga ad un sottoinsieme Tj di T ; questa condizione potrebbenon essere veri�cata se i sottoinsiemi di partenza di T non sono corretti: infatti du-rante il processo di allargamento, alcuni vertici possono rimanere isolati (cio�e avereconnessioni con altri vertici solo attraverso corde rosse) e quindi non appartenere anessun sottoinsieme di T . Nel caso il vertice B sia isolato, basta prendere, se esiste,un'altra corda rossa che abbia come estremoA, oppure cambiare vertice di partenza.

Come spiegato in precedenza, dal momento cheA eB sono connessi da una cordarossa ed entrambi appartengono ad un sottoinsieme di T , nel caso di una rottura A e

44


Le superfici definite dai sottoinsiemi

di T fanno parte della struttura creata

superficie equipotenziale

due revs appartenenti a sottoinsiemi

diversi non hanno una connessione diretta

Figura 5.6.

B appartengono a due sottoinsiemi di�erenti, cio�e i 6= j, mentre nel caso di un bucoA e B appartengono allo stesso sottoinsieme (i = j). In questo modo un semplicecontrollo sul sottoinsieme di appartenenza di due vertici ci permette di stabilire iltipo del punto critico, il tipo della super�cie di separazione de�nita dal sottoinsiemeTi e quindi la modalit�a con cui andr�a ricostruita la struttura.

Il metodo implementato �e leggermente diverso: invece di dividere T in sottoinsie-mi e poi stabilirne il tipo, assegniamo un tipo al sottoinsieme mentre lo costruiamo.Preso un arco rosso e chiamati A e B i suoi estremi (assicurandosi che nessuno deidue sia isolato) possiamo visitare i vicini di B. Eseguiamo un ciclo tra i rev delsottoinsieme partendo da B; siano P0;P1::::Pj;:::B i vertici visitati. Se uno dei Pi �eA, allora A e B appartengono allo stesso sottoinsieme di T (per de�nizione, relazionidi vicinato possono esistere solo tra elementi dello stesso sottoinsieme) e il tipo dellasuper�cie di separazione �e un buco. Se invece non incontriamo A, allora A e Bappartengono a due sottoinsiemi diversi, che de�niscono le super�ci di separazionedi una rottura.

45

6

Come ricostruire una struttura

corretta

Nel capitolo precedente abbiamo visto come isolare la parte della struttura che deveessere rimossa, come creare un insieme di vertici chiamati rev e come dividerlo insottoinsiemi costituenti i bordi delle super�ci di separazione della struttura. Ab-biamo anche individuato come riconoscere, partendo da tali sottoinsiemi, il tipo disingolarit�a che si presenta nella super�cie.

Dobbiamo ora analizzare come �e possibile riadattare la tassellatura generata alcomportamento reale della struttura, osservando in principio il caso pi�u semplicein cui la distribuzione delle cariche genera un solo punto critico al suo interno, esuccessivamente il caso generale.

6.1 Distribuzioni con un solo punto critico

Avendo stabilito il tipo delle super�ci di separazione, sappiamo in che modo dob-biamo agire per avere una struttura che rispecchi fedelmente le propriet�a della su-per�cie. Prima di e�ettuare questa operazione, per�o, �e necessario rimuovere tutti itriangoli marcati come rossi, le corde rosse e tutti i vertici isolati generati duranteil processo di allargamento dell'insieme T . Questi ultimi sono collegati con altrivertici solamente attraverso corde rosse, e sono quindi attorniati solo da triangolimarcati che verranno eliminati nel corso del processo di rimozione. Tali vertici, purappartenendo a T , non appartengono a nessun sottoinsieme di T . Devono inoltreessere eliminati tutti i riferimenti a corde, triangoli e vertici obsoleti .

Quello che otteniamo alla �ne del processo �e una struttura aperta che deve esserechiusa a partire dalle super�ci di separazione de�nite dai sottoinsiemi di T .

46

6 { Come ricostruire una struttura corretta

6.1.1 Il piano separatore

Per il processo di ricostruzione della struttura �e necessario conoscere l'equazione delpiano di separazione tra le super�ci de�nite dai sottoinsiemi di T . Questo risultaabbastanza semplice per le considerazioni fatte nel paragrafo x4.2, in quanto ad ognipunto critico abbiamo associato gli assi di simmetria della super�cie nei dintorni delpunto critico. Riferendosi alle �gure 4.1.a-b, il piano separatore �e de�nita dall'auto-vettore corrispondente all'autovalore avente un segno diverso dagli altri (nell'esempiocitato, il piano separatore �e per entrambe le con�gurazioni il piano z = 0).

6.1.2 Ricostruire una rottura

Ogni sottoinsieme rappresenta il con�ne di una struttura aperta che deve esserechiusa con una calotta. I rev appartenenti a un sottoinsieme devono quindi essereconnessi solamente con rev appartenenti allo stesso sottoinsieme, oppure con nuovivertici generati, che per�o costituiscano globalmente una regione chiusa.

Il metodo pi�u semplice per e�ettuare questa operazione �e quello seguente:

1. calcolare il centro del sottoinsieme (Ci =P

vj2Tivj

ndove n = jTij )

2. spostarlo sulla super�cie equipotenziale iterando (2.3)

3. unire tutti i rev del sottoinsieme con Ci.

C

T i

i

Figura 6.1.

47


Il risultato di questa operazione �e mostrato in �gura 6.1; il vantaggio di questometodo �e che viene generato un numero ridotto di triangoli. Infatti se la dimensionedel sottoinsieme �e n vengono generati n nuovi triangoli e 1 nuovo vertice. Creare ilminimo numero di triangoli possibile non �e in genere una buona soluzione; infattibuona parte delle nuove corde introdotte risulta non essere accettabile. In questomodo invece ci si assicura che il punto Ci si trovi sulla super�cie equipotenziale e chele nuove corde introdotte siano pi�u verosimilmente accettabili. Il grosso svantaggio�e invece che il centro del sottoinsiemi risulti avere almeno n vicini. Questo fatto pu�orivelarsi negativo per l'applicazione di alcune tecniche di post-processing quando ndiventa elevato.

Si consideri ad esempio la tecnica del rilassamento. Essa consiste inizialmentenell'applicare ad un vertice un vettore di spostamento, determinato come la di�eren-za di posizione tra il vertice stesso il centroide dei suoi vicini, e quindi nel muoverela nuova posizione ottenuta sulla super�cie; il centroide �e il centro dell'insieme for-mato dai vicini del vertice in questione considerato come un poligono a n lati. Pertutti i vertici della super�cie vengono calcolati i vettori di spostamento ideali, esuccessivamente vengono aggiunti (interamente o solo in parte) ai vertici originari.

Lo scopo di questa tecnica �e quello di far assumere ai vertici una distribuzioneil pi�u uniforme possibile sulla super�cie. Applicata al vertice Ci non ne cambia laposizione in quanto tale vertice �e stato costruito proprio come centro dell'insiemeformato dai suoi vicini. Inoltre l'aspetto della super�cie attorno al vertice creatolascia molto a desiderare, perch�e la super�cie forma una punta.

Per ovviare a questo problema e per introdurre un'insieme di corde che seguapi�u dolcemente il pro�lo della super�cie si pu�o procedere nel modo seguente: ilcentro del sottoinsieme viene calcolato come nel caso precedente, ma ora tra Ci e ilsottoinsieme stesso viene creato uno strato intermedio di vertici. La dimensione diquesto livello intermedio deve essere tale che, alla �ne del processo di connessione, isuoi componenti e il centro del sottoinsieme abbiano all'incirca lo stesso numero divicini. Questo passo pu�o essere cos�i sintetizzato:

1. Stabilire un numero d'ordine per i rev appartenenti al sottoinsieme Ti (ad esempiosi prenda un qualsiasi rev del sottoinsieme e gli si assegni l'indice 0, si scelga poiun verso di percorrenza, orario o antiorario, e si assegni un indice crescente adogni nuovo rev incontrato �no al raggiungimento del vertice di partenza). SiaL l'insieme composto dai vertici appartenete al livello intermedio da costruire.Inizialmente L �e vuoto.

2. per ogni rev del sottoinsieme avente un indice multiplo dijqjTij

k

calcolare il punto medio del segmento che unisce il vertice e Ci; sia v il nuovovertice creato (oppure sia v il punto medio parametrico della curva di Bezier

48


passante per il vertice e per Ci e ivi tangente alle rispettive normali).

spostare v sulla super�cie e aggiungerlo a L.

Per unire Ti e L si pu�o seguire il procedimento che verr�a utilizzato nel paragra-fo x6.1.3, mentre Ci pu�o essere collegato con tutti i vertici di L.

Figura 6.2.

Se poniamo n = jTij e m =ln=jqjTij

km, vengono creati m+ 1 vertici e n+ 2m

triangoli. Il centro del sottoinsieme avr�a m vicini mentre ogni vertice del livellointermedio ne avr�a, in media,m+3. In �gura 6.2 si pu�o vedere il risultato ottenibilein un caso molto semplice in cui jTij = 6 e m = 3.

6.1.3 Ricostruire un buco

In questo caso il problema �e pi�u complicato. La parte di super�cie che deve esserecostruita �e una "striscia" compresa tra i due sottoinsiemi di T ; per costruirla, i revdi un sottoinsieme devono essere connessi solamente con rev dell'altro sottoinsieme,e gli archi di connessione non devono attraversare il buco. In termini matematici,questo signi�ca che gli estremi A e B della corda devono appartenere alla stessaregione de�nita dal piano perpendicolare alla proiezione del vettore A � C (doveC �e il punto critico) sul piano separatore; in altri termini il prodotto scalare tra le

49


B

A

C

Figura 6.3.

proiezioni sul piano separatore dei vettori A�C e B�C non deve essere minore dizero (�gura 6.3).

Innanzitutto, bisogna prendere due vertici di partenza dai due sottoinsiemi; sianov1 2 T1 e v2 2 T2 i due vertici aventi la minima distanza tra di loro. Per il processodi triangolarizzazione del nastro occorrono ora due distanze d1 e d2:

� d1=distanza tra v1 e v+2 (dove v+2 �e il vicino di v2 in senso orario)

� d2=distanza tra v2 e v+1 (dove v+1 �e il vicino di v1 in senso orario).

L'arco corrispondente alla distanza minore �e ripetutamente aggiunta alla struttu-ra di connessione, �no a quando il nastro triangolare non �e chiuso. Se i sottoinsiemidi partenza hanno jT1j+ jT2j = n otteniamo n nuovi triangoli (�gura 6.4).

6.2 Distribuzioni con pi�u punti critici

La soluzione discussa nel paragrafo x6.1 funziona bene nei casi semplici ma nonpermette assolutamente di trattare topologie pi�u complicate. Non �e di�cile, infat-ti, costruire delle distribuzioni di cariche in cui compaia un numero di singolarit�aarbitrario, nonch�e casi in cui pi�u punti critici abbiano lo stesso potenziale. Quattrocariche equivalenti poste nei vertici di un quadrato, ad esempio, generano quattrosingolarit�a equipotenziali sui lati del quadrato e una quinta nel centro dello stesso.

Bisogna quindi de�nire nuovi attributi da associare ai punti critici e ai sottoin-siemi di T che permettano al processo di ricostruzione della struttura di essere il pi�ugenerale possibile.

50


T

T

1

2

Figura 6.4. jT1j = 5;jT2j = 4; la striscia �e composta da 9 triangoli

6.2.1 Alcune de�nizioni

Prima di spiegare come sia possibile trattare distribuzioni pi�u complesse, �e oppor-tuno introdurre alcune de�nizioni che saranno necessarie in seguito.

De�nizione 6.1 Un punto critico si dice attivo quando il valore della super�cieequipotenziale V0 corrisponde al potenziale del punto critico stesso, cio�e (per quantospiegato in x4.3) V0 = Vc + �c, dove Vc �e il valore critico.

I punti critici possono, quindi, non essere tutti attivi allo stesso istante. In pi�u,data l'introduzione da parte della distribuzione di cariche di un numero arbitrario dipunti critici, l'insieme T risulta essere diviso in un numero arbitrario di sottoinsiemi.Inoltre in precedenza la singolarit�a presente era unica e tali sottoinsiemi si riferivanoimplicitamente ad essa; ora �e necessario che ogni sottoinsieme abbia un esplicitoriferimento ad un punto critico.

De�nizione 6.2 Un sottoinsieme Ti di T e un punto critico Pj sono collegati se Pj�e il punto appartenente all`insieme dei punti critici introdotti dalla distribuzione dicariche che ha la distanza minore dal centro del sottoinsieme.

51


A questo punto occorre fare una precisazione. A causa di approssimazioni dicalcolo, i vertici non giacciono mai esattamente sulla super�cie equipotenziale; que-sto pu�o introdurre perturbazioni nel processo di marcatura delle corde che possonoportare a marcare come rosse delle corde che appartengono ancora alla super�cie,generando dei sottoinsiemi di T corretti ma che non devono essere rimossi dallastruttura. Un arco marcato come rosso introduce infatti un sottoinsieme correttocomposto da 4 rev (i vertici dei due triangoli adiacenti alla corda). Questa possibilit�apu�o veri�carsi nei casi in cui due singolarit�a, in regioni diverse della spazio, abbianoun potenziale molto simile: anche nel caso in cui la marcatura relativa a quella apotenziale maggiore sia corretta, abbiamo inserito un apposito valore di potenzialein cui deve essere analizzata. Bisogna quindi che anche i sottoinsiemi di T abbianoun attributo di attivazione:

De�nizione 6.3 Un sottoinsieme Ti di T �e attivo al potenziale V0 se lo �e il puntocritico Pj a cui Ti �e collegato.

Un altro problema, �e quello di collegare tra loro le due super�ci di separazionerelative ad un buco. Infatti, mentre i sottoinsiemi corrispondenti a delle rotture pos-sono essere connessi singolarmente, quelli corrispondenti ad un buco devono essereaccoppiati. Due sottoinsiemi de�niscono le super�ci di separazione di un buco se so-no collegate allo stesso punto critico e il prodotto scalare tra i vettori che connettonoil punto critico e i centri dei due sottoinsiemi �e minore di zero.

6.2.2 Ricostruire l'intera struttura

Prima di tutto abbiamo bisogno delle seguenti strutture dati:

� una lista dei valori di potenziale per la costruzione della super�cie equipoten-ziale �nale;

� una lista (inizialmente vuota) che conterr�a gli eventuali punti critici de�nitidalla distribuzione di cariche;

� una lista contenente gli elementi di T ;

� una lista di elementi contenenti le caratteristiche dei sottoinsiemi di T ;

L'insiemedei punti critici viene aggiornato dall'applicazione del metodo di Newton-Raphson. Una volta che tale metodo converge dobbiamo:

� calcolare gli assi di simmetria della super�cie corrispondente al valore critico;

52


� inserire i dati relativi al punto critico nella tabella relativa;

� modi�care l'insieme dei valori di potenziale.

Quando viene raggiunto un punto critico occorre:

� costruire l'insieme T ;

� dividerlo in sottoinsiemi;

� collegare ogni sottoinsieme ad un punto critico;

� stabilire l'attributo di attivazione per ogni sottoinsieme;

� collegare tra di loro i sottoinsiemi relativi a dei buchi;

� eliminare i triangoli e le corde rosse aventi un estremo appartenente ad unsottoinsieme attivo, e tutti i vertici isolati connessi attraverso un arco rossoad un sottoinsieme attivo;

� per tutti i sottoinsiemi attivi, ricostruire la struttura a seconda del loro tipocome spiegato nei paragra� x6.1.2 e x6.1.3.

53

7

L'algoritmo modi�cato

Dopo aver introdotto i concetti di corde rosse, triangoli rossi, rev, siamo ora ingrado di scrivere l'algoritmo completo. Questo verr�a presentato nel paragrafo x7.1;nel paragrafo x7.2 verranno presentati i risultati ottenibili con il nuovo algoritmocomparati con quelli della precedente versione.

7.1 Il nuovo algoritmo

Riprendendo la notazione introdotta nel paragrafo x2.6, i vertici sono de�niti comequadruple (r;E;V;d) 2 R3 � R3 � R � R3); l'attributo r �e la posizione; E �e ilgradiente rf(r); V �e il valore del potenziale f(r), e d �e il vettore di spostamentoche deve essere applicato a questo vertice. P �e l'insieme dei valori di potenziale;la funzione next estrae da P il prossimo passo da valutare. Ogni suo componenteha come attributi (V;cp), dove V �e il valore di potenziale e cp speci�ca se il valore�e collegato ad un punto critico. T �e l'insieme dei rev e i sottoinsiemi sono de�niticome tuple (t;a;lc) dove t �e il tipo del sottoinsieme, a �e l'attributo di attivazione elc �e un riferimento alla lista collegata nel caso il tipo sia un buco. L'insieme C �el'insieme contenente i punti critici; questi sono de�niti come vertici ma hanno in pi�uun riferimento ad una matrice M contenente i versori degli assi di simmetria dellasuper�cie nell'intorno del punto critico stesso.

La funzione insert provvede ad inserire un elemento nell'insieme speci�cato. Nelcaso tale insieme sia P , insert provvede anche a modi�carne gli altri elementi. Comespeci�cato nel paragrafo x4.3, inserendo un valore v:V dobbiamo eliminare tutti ivalori presenti in un intervallo de�nito di v:V aventi attributo cp = 0, ponendoneuno al limite inferiore di tale intervallo. Questo elemento pu�o essere ottenuto au-mentando leggermente il potenziale di un elemento gi�a presente o, se questo non �epossibile, inserendone uno nuovo.

54

7 { L'algoritmo modi�cato

La di�erenza di potenziale tra una super�cie e la successiva �e inizialmente de�nitacome una frazione del potenziale �nale V0 (con V0 = 1), ad esempio V0n10; se ladistribuzione delle cariche introduce dei punti critici questa di�erenza pu�o variare.Inizialmente P contiene tutti i valori frazionari de�niti di V0.

Nuovamente l'insieme di vertici di partenza �e costituito dai vertici dell'oggettoiniziale (un tetraedro o un ottaedro); si assume che sia su�cientemente grande daessere esterno alla intera super�cie equipotenziale anche per il valore iniziale 1n10.Tutti i vertici v hanno inizialmente v:V = 0, v:E punta radialmente verso l'interno,e v:d = v:E=v:E � v:E.

beginP=insieme dei passi di potenziale iniziali;f inizialmente tutti i componenti di P hanno l'attributo cp=0 gV0:=0;while P6= f;gbegin

V0:=next(P);S1;f tutti i vertici sono sulla super�cie; per ogni vertice v abbiamov.V=V(v.r)v.E=grad V(v.r)v.d=(V0-v.V)*v.E=v.E� v.Eg

S2;f tutti i vertici sono sulla super�cie; per ogni vertice v abbiamov.V=V(v.r)v.E=grad V(v.r)v.d=(V0-v.V)*v.E=v.E� v.E

tutte le corde sono accettabiligS3;f eventuali punti critici in vicinanza dei vertici della super�ciesono stati trovati; l'insieme P e' stato modi�cato gif V0.cp=1 then S4;f tutte le corde e i triangoli della struttura sonocoerenti con la super�cie da approssimare g

end;f tutti i vertici sono sulla super�cie;tutte le corde sono accettabili e V0=1.0g

end;

dove S1 �e:

55


for tutti i vertici v dorepeat

v.r:=v.r+v.d;v.V:=V(v.r);v.E:=grad V(v.r);v.d:=(V0-v.V)*v.E=v.E� v.E;

until jv.dj <Epsilon;

e S2 �e:

azzerare l'etichetta di tutti i triangolifor tutte le corde c dobegin

c.n := "c non e' accettabile"f per decidere l'accettabilita' o meno di una corda, usare e1.E e e2.Ecome direzioni delle normali in e1.r e e2.r per gli estremi e1 ed e2 della corda g

end;while ci sono corde non accettabili dobegin

for tutte le corde c con c.n := true dobegin

creare un nuovo vertice w per la corda c, come spiegato in x2.5;spostare w sulla super�cie come in S1;etichettare i due triangoli adiacenti ad e;creare due nuove corde per i frammenti di c, c1 e c2;c1.n := "c1 non e' accettabile"c2.n := "c2 non e' accettabile"rimuovere la corda c;

end;f tutte le corde inizialmente non accettabilisono state divise, ma nuove corde non accettabili possono essere state create gfor tutti i triangoli etichettati t dobegin

dividere t come spiegato nella sezione x2.5;creare 2,3 o 4 nuovi triangoli;for tutte le nuove corde generate ci do ci.n := "ci non e' accettabile";rimuovere il triangolo t;f tutti i triangoli delimitati inizialmente da corde non accettabili sono stati divisi,ma nuove corde non accettabili possono essere state generate g

end;

56


end;

come nel paragrafo 2.6. S3 �e:

calcolare la soglia �n;for tutti i vertici v con jv.Ej < �n dobegin

applicare Newton-Raphson a x0=v;if il metodo converge thenbegin

b=xn;f b ha gli stessi attributi di un vertice gif b non e' presente in C thenbegin

insert(b.V+�c,P);f l'insieme P e' stato modi�cato gassociare a b gli assi di simmetria della super�cie nel suo intorno;insert(b,C);

end;else if b.cp=0 then b.cp=1;

end;end;

e in�ne S4 provvede a ricostruire la struttura:

marcare le corde della struttura;costruire l'insieme T ;dividere T in sottoinsiemi;for tutti i sottoinsiemi Q di T dobegin

Q.a="il sottoinsieme e' attivo"Q.t="tipo del sottoinsieme"

for tutti i sottoinsiemi S attivi dobegin

if Q.t=rottura then ricostruisci rottura(Q);if Q.t=buco thenbegin

Q1=Q.lc;ricostruisci buco(Q,Q1);

57


Q1.a=0;end;

end;

7.2 Analisi dei risultati

Un'analisi quantitativa del sovraccarico introdotto dalle nuove caratteristiche non�e semplice, in quanto non pu�o essere e�ettuato nessun confronto sulle stesse di-stribuzioni di cariche in ingresso rispetto al vecchio Shrinkwrap; o,per essere pi�uprecisi, distribuzioni non contenenti punti critici possono essere confrontate, ma ilcosto introdotto dal processo di marcatura e di ricostruzione della struttura �e unapeculiarit�a della nuova versione dell'algoritmo. Dobbiamo quindi accontentarci dicalcolare l'aumento medio in termini di IFEPT (Implicit Functions Evaluated PerTriangle), anche se i risultati non sono ancora del tutto confrontabili, in quanto ilnumero di IFEPT dipende anche dal numero di passi utilizzati per raggiungere lasuper�cie �nale; a causa della presenza di punti critici e quindi della necessit�a dicambiare tale insieme di valori e spesso di aumentarne la dimensione, il numero dipassi utilizzato per calcolare i dati presenti in tabella 7.1 �e in genere 9, contro i 7(il numero ottimo) utilizzati in [Overveld 93]. Per comparare i risultati possiamorapportare i dati ottenuti al numero di passi ottimo.

Il sovraccarico in termini computazionali �e principalmente dovuto alle iterazionidel metodo di Newton-Raphson. E' possibile calcolare tale sovraccarico ricalcolandoi costi totali evitando di applicare tale processo; registrando su un �le tutti i datirelativi ai punti critici generati dalla distribuzione di cariche, il processo di costru-zione della super�cie equipotenziale �nale pu�o essere applicato una seconda voltadisponendo in partenza di tutti i dati necessari. Nella tabella 7.1 sono presentati irisultati completi. Nella prima colonna vi �e il nome simbolico associato all'insiemedi cariche, mentre nella seconda colonna �e rappresentato il numero �nale di triangoliche compongono la struttura approssimante. La parte restante della tabella �e divisain due parti: la prima conteggia il numero totale di funzioni implicite calcolate,mentre la seconda non considera il costo aggiuntivo dovuto al metodo di Newton-Raphson. In�ne nell'ultima colonna vi �e la di�erenza in percentuale tra i valori diIFEPT calcolati nei due casi.

Per quanto riguarda le istanze utilizzate per estrarre i risultati presentati, essegenerano quasi tutte un solo punto critico, tranne 4points che �e costituita da 4 caricheequivalenti posizionate sui lati di un quadrato e 1line-2points contenente una linea edue cariche puntiformi di carica diversa e posizionate asimmetricamente nello spazio.La prima istanza genera un punto critico nel centro del quadrato e, ad un potenziale

58


Istanza Triangoli Newt.on IFEPT Newt.o� IFEPT Di�erenza

4lines 746 7668 10.28 6582 8.82 -14.20 %1torus 458 5230 11.42 4475 9.77 -14.44 %4points 2366 43618 18.44 32035 13.54 -26.57 %2triangles 640 11875 18.55 8107 12.67 -32.80 %2points 1204 26152 21.72 16679 13.85 -36.22 %1line-1point 606 14267 23.54 6969 11.50 -48.85 %

Tabella 7.1.

maggiore, quattro punti critici equipotenziali sui lati del triangolo mentre la secondagenera due punti critici a potenziali diversi, ed �e stata utilizzata per ricavare deisottoinsiemi di rev non corretti. Alcune di queste istanze sono rappresentate nelletavole a colori in appendice (1torus: tavole E.1-7; 2points: tavole D.1-6).

Calcolando il risultato medio ottenibile con la precedente versione di Shrin-kwrap si ricava che, nel caso ottimo, IFEPT ' 8:31. Applicando un numerodi iterazioni pari a quelle utilizzate per ricavare i dati della tabella 7.1, si ottie-ne IFEPT ' 9:86, cio�e un peggioramento di circa il 18.7%. Ora otteniamoIFEPT ' 17:32 (+108.42%) e IFEPT ' 11:69 (+40.67%) senza considerareil costo dovuto al metodo di Newton-Raphson. Ricalcolando i risultati in termi-ni di numero ottimo di passi ottimo si ottiene rispettivamente IFEPT ' 14:55(+75.08%) e IFEPT ' 9:85 (+18.52%) e 14.55.

Come si pu�o notare dall'analisi dei risultati, il numero di computazioni dovuteal metodo di Newton-Raphson penalizza notevolmente le prestazioni. Tale numerodipende principalmente dalla dimensione dell'insieme S di vertici di partenza. Ridu-cendo tale dimensione, si riduce anche, di conseguenza, il sovraccarico generato. Lasoluzione implementata �e forse costosa, ma ha il vantaggio di essere molto robusta,nel senso che riesce a trattare tutte le con�gurazioni in ingresso indipendentementedalla loro complessit�a.

Al contrario, i processi di marcatura delle corde e di ricostruzione della strut-tura in uiscono in modo minore sul costo totale �nale anche quando devono essereapplicati pi�u volte (ad esempio si vedano nella tabella i casi delle istanze 4points e1line-2points).

7.3 Conclusioni

L'algoritmo presentato nel capitolo 7.1 permette di generare una struttura poligo-nale che approssimi una super�cie implicita. Tale processo, noto con il terminedi poligonizzazione, permette di ovviare ad alcuni degli inconvenienti riscontrabili

59


nell'utilizzo di super�ci implicite; tale approssimazione, ad esempio, ne sempli�ca ilproblema della visualizzazione, permettendo di ombreggiarla rapidamente e di avereviste da posizioni arbitrarie senza dover risolvere ogni volta la funzione che la de�-nisce. Le super�ci in esame sono super�ci di livello di un campo scalare, de�nito daun insieme di elementi di base, che costituiscono lo "scheletro" della super�cie.

La tassellatura della super�cie viene costruita a passi attraverso potenziali via viacrescenti �no a raggiungere la super�cie �nale, adattandola ad ogni passo alla super-�cie intermedia. La struttura triangolare risultante �e adattativa al comportamentolocale della super�cie piuttosto che essere imposta a priori da una suddivisione dellospazio, nel senso che la lunghezza dei lati dei triangoli componenti la struttura variasecondo la curvatura locale della super�cie sottostante. In questo modo super�cirelativamente piatte daranno luogo ad una tassellatura costituita da triangoli pi�ugrandi e, generalmente, equilateri, mentre super�ci con una curvatura pi�u elevatagenereranno triangoli pi�u sottili e di dimensioni minori.

Se la distribuzione di cariche introduce singolarit�a nel campo, le super�ci pos-sono andare incontro a cambiamenti geometrici e topologici, o scindendosi in pi�usuper�ci separate o incrementando il proprio ordine di connessione; occorre quindimodi�care la struttura generata dall'algoritmo (che inizialmente �e una singola su-per�cie chiusa semplicemente connessa) perch�e assuma le stesse caratteristiche dellasuper�cie equipotenziale.

Abbiamo visto un semplicemetodo che ci permette di conoscere l'esatta posizionedei punti critici presenti; conoscendone la posizione, possiamo calcolarne il potenzialee, portando dolcemente la struttura creata al valore del punto critico, isolare gliinsiemi di corde e triangoli che non sono pi�u coerenti con la super�cie, rimuoverlie ricostruire nuovi insiemi corretti. In questo modo ogni super�cie equipotenziale�nale diventa triangolarizzabile a partire da una struttura iniziale molto semplice.

La struttura �nale o�re diversi vantaggi, che possono essere riassunti come segue:

� la struttura �e adattativa al comportamento locale della super�cie;

� le normali nei vertici sono calcolate come sottoprodotto del metodo di ricercae non comportano quindi la necessit�a di ulteriori e pi�u pesanti computazioni;

� la struttura creata pu�o essere facilmente equipaggiata con un proprio sistemadi coordinate;

� la super�cie equipotenziale �nale non deve godere di particolari propriet�a.

Uno svantaggio delle nuove caratteristiche introdotte �e che determinano unariduzione dell'e�cienza in termini di IFEPT. L'algoritmo �e stato implementato inC in ambiente XGL su una workstation Sun Sparc 10 dotata di hardware gra�co.

60


Le tavole a colori presentate sono state generate per mezzo di due diversi toolsdi shading, Polygons e Viper, progettati e realizzati da Kees van Overveld incollaborazione con alcuni studenti della Technische Universiteit Eindhoven.

7.4 Ulteriori sviluppi della ricerca

Uno dei punti che la corrente implementazione non �e ancora in grado di trattare�e rappresentato dalla possibilit�a di avere un buco con pi�u di due super�ci di se-parazione. Come per il relativo caso di una rottura, non �e complicato de�nire uninsieme di primitive che determini tale situazione. Tuttavia, anche se non si �e rite-nuto necessario ampliare il presente lavoro, �e abbastanza facile fronteggiare questaevenienza disponendo delle strutture dati presentate. Stabilito quindi che si possapresentare questa situazione, �e su�ciente inserire i relativi riferimenti negli elementigi�a presenti. Il problema pi�u signi�cativo �e quello di ricostruire la struttura corret-tamente; a questo proposito ci viene in aiuto un articolo, [Bink 94], che tratta dellaricostruzione di super�ci tridimensionali (anch'esse de�nibili come super�ci implici-te) attraverso informazioni volumetriche. Questo �e un problema di grande interessesopratutto in campo medico, dove si cerca di ricostruire la struttura di organi odi ossa a partire da una serie di campioni derivanti da analisi (raggi X, TAC, ...).Uno dei casi trattati in questo articolo riguarda proprio il problema di collegare traloro pi�u "contorni" (cio�e quelle che in questa tesi sono state indicate come super�cidi separazione) in modo da costruire una super�cie unica; la soluzione proposta �efacilmente adattabile all'algoritmo Shrinkwrap.

Un grosso miglioramento delle prestazioni e delle potenzialit�a dell'algoritmo sar�aottenibile quando tutto il programma, correntemente implementato in C, sar�a con-vertito in C++ per entrare a far parte di un sistema gra�co ad oggetti chiamatoGBOB (Graphics Box Of Bricks) sviluppato dai ricercatori del Technische Toepas-singen Group dell'universit�a di Eindhoven.

In questo sistema una super�cie o un insieme di super�ci sono de�nite comeun unico oggetto su cui �e possibile applicare una serie di metodi, alcuni dei qualipermettono di "ra�nare" la struttura triangolare eliminando triangoli non necessari.Nel processo di contrazione pu�o infatti veri�carsi che in alcune regioni,dove cio�e si �everi�cato un buco o una rottura, la curvatura diminuisca; l'insieme di triangoli chede�niscono tale regione pu�o quindi essere ridotto ad un nuovo insieme di dimensioniminori, pur mantenendo una struttura corretta e accettabile. In queste modo lastruttura �nale �e pi�u semplice e ne risulta anche pi�u rapida l'elaborazione.

Inoltre, diverse applicazioni possono interagire sullo stesso oggetto, permettendoeventualmente di utilizzare Shinkwrap in maniera pi�u essibile all'interno di questosistema.

61

Appendice A

How to shrinkwrap a saddle point

A.1 Introduction

Equi-potential surfaces are an important class of implicit surfaces. They play asigni�cant role in computer visualization and several of the surfaces that are ofinterest in pure mathematics, physics, or chemistry are equi-potential surfaces.

In order to visualize equi-potential surfaces, ray tracing is a reasonable technique,although it is an arduous task to compute points on the equi-potential surface, whichoften imposes restraints on its application.

An alternative to ray tracing is the conversion of the surface into a polygonalmesh, that can be rendered afterwards and that o�ers other inherent advantages(such as fast viewing from arbitrary directions and applications of post-processingtechniques).

In [Overveld 93] an algorithm is presented (referred to as Shrinkwrap) for poly-gonizing an iso-potential surface de�ned by a set of skeletal elements. The algorithmgenerates a triangular mesh that is adaptive to the local behaviour of the surface,in the sense that the lengths of the sides of the triangles in the mesh vary with thelocal curvature of the underlying surface. A disadvantage of this algorithm is thatit can only cope with a single closed surface without holes. This means that any�nal con�guration made up of more separate surfaces cannot be tesselated by thealgorithm, and as well any con�guration containing holes (e.g. the case of a torus).

The Shrinkwrap algorithm has been implemented in a program calledWsoid byKees van Overveld and the Computer Graphics Group of the Eindhoven Universityof Technology. This paper presents a possible solution to the problem of dealingwith the change in topology occurring in the critical points of the potential �eld.

In the following sections we explain what is a critical point, how to detect criticalpoints in the space and how reshape the structure created in order to keep an

62

A { How to shrinkwrap a saddle point

acceptable surface and an acceptable triangular mesh (please refer to [Overveld 93]for all the de�nitions of chord, acceptable chord, acceptable triangle and acceptablesurface).

In the Appendix, some general assumption are speci�ed and some informationsabout the implementation are given.

63


A.2 Critical points

A critical point P0, or singular point, of an implicit function in three variables, asthe case of the scalar potential �eld we're dealing with, is a point with the followingcharacteristics:

� the gradient of the potential �eld in the point is zero. That means:

rf(P0) = 0 (A.1)

det(JP0) 6= 0 (A.2)

where J is the Jacobian of rf .� one set of �eld lines intersect at the singular point, but equipotential surfacesand �eld lines do not intersect at a right angle. ([Artley 65]).

ρ+

ρ+

(a) (b)

y y

zz

Equipotential surfaces Flow lines direction

Figura A.1. Equipotential surfaces and ow lines on the yz plane for two equiv-alent point sources.

Figure A.1a indicates the manner in which equipotential surfaces appear in theyz plane for two equal point sources. One set of equipotential lines intersects atthe origin. The ow or direction lines of the �eld are indicated in �gure A.1b. Thediagram in �gures A.1 depict the �eld in one plane. The three-dimensional �eld canbe visualized by rotating the individual diagram in �gure A.1 about their respective

64


z axes. The set of ow lines which meet at the singular point leave the singularpoint to form a plane sheet of ow in the z = 0 plane in three dimension.

An iso-potential surface at a value of the critical point is in a limit situation.When the iso-value changes, the iso-surface in the vicinity of a critical point changestopologically and geometrically. What can happen to the surface is that it can splitinto two new surfaces (as in the case of two charges) or it can increase the order ofconnectivity (as in the case of a torus).

A.2.1 How the region around a critical point behaves

Equation A.1 can be used to characterize a region of the space close to a criticalpoint. Since the �eld is de�ned as:

f(r) =Xi

�ijr �Rij (A.3)

the potential function has a continuous derivative. This means that in a regionof space close enough to P0, the gradient length is approaching zero. From thisobservation, we can derive a method to �nd the position of the critical points in the�eld.

We can consider a set of points of the iso-potential surface with the characteristicof having a gradient length locally minimal.

De�nition A.2.1 For a given �n, S is the set of vertices v of the polygonal meshwith jrfvj < �n

This set can be made arbitrarely large by choosing a greater value of �, and itselements can be taken as starting points for a Newton-Raphson method to �nd thecritical points. This method gives a very e�cient means of converging to a root, ifthere is a su�ciently good initial guess. It can also spectacularly fail to converge,indicating (though not proving) that no root exists nearby. The set S as de�nedbefore can be considered as a good initial guess. Newton-Raphson method tries toreach the roots of an equation by adjusting the argument, iterating the followingformula:

xn+1 = xn �rf(xn) � J�1 (A.4)

(see [Mizr 82] and [Press 86-1])

where J is the Jacobian of rf and x0 2 S. This process is stopped when wereach a point xn that satis�es rf(xn) = 0 within oating point accuracy, or when

65


the process itself diverges. The results we can obtain with this method are ratherprecise; in fact, if di�erent points on the surface converge to the same critical point,the di�erences in the value of potential and in position of this points are close to0.01%.

Evaluating the eigenvectors of the Jacobian in the critical point, we can introducethere a basis of perpendicular vectors (the vectors perpendicular to the planes ofsymmetry of the iso-surface in the region around the critical point). They allow usto �nd a cutting plane, that is the separating plane between the splitting surfacesgenerated by the critical point ([Press 86-2]). The de�nition of this plane is essentialfor the process of �xing the topology (see xA.4.2).

If we expand the potential function around a critical point c the linear terms arezeroed; we obtain:

f(c+ x) = f(c) +1

2

Xi

Xj

@2f

@xi@xjxixj + h:o:t:

The matrix of the partial derivatives (J) is the Jacobian of rf ; for the theoremof Schwartz, J is real and symmetric; so, its eigenvectors and the correspondingeigenvalues are real. Since c is a critical point, J(c) has both positive and negativeeigenvalues; furthermore, an orthogonal base of eigenvectors of J exists.

Now if we take c as origin and the eigenvectors of J as direction of the axes of anew coordinate system x0, y0 and z0, we get

f(x0;y0;z0) = f(0) +x02

a2+y02

b2� z02

d2

The surface f(x0;y0;z0) = f(0)+� intersects the plane z = 0 in an ellips (if � > 0); theplane z = 0 is tangent to the surface f(x0;y0;z0) = f(0), and the surface f(x0;y0;z0) =f(0) is separated in two halves by the plane z = 0.

If the matrix J has two negative eigenvalues, we get

f(x0;y0;z0) = f(0) � x02

a2� y02

b2+z02

d2

In this case the transition is from two halves into one surface.

The surfaces in the two di�erent cases are shown in �gure A.2. The positive andnegative values of the eigenvalues are such that the plane z = 0 is the cutting planefor both con�gurations.

66


z

y

x

O

z

x

y

(a) (b)

Figura A.2.

A.3 The surface

As stated above, we can �nd where a critical point is. Knowing its position in thespace, we can easily compute the value of the �eld in this point.

This is important because knowing it, we can change the number and the valueof the iso-values that de�ne the intermediate surfaces, in order to have a smoothapproach to the point in which there will be a topological change in the surface.The procedure followed is:

1. when the shrink wrap algorithm starts, the beginning and ending values ofthe iso-value and the number of steps we have to iterate are given. A dynami-cally linked list is created to record the di�erent iso-values of the approachingmethod.

2. when an iso-potential surface has been created, we calculate the set S for asuitable � and apply the Newton method to the points belonging to it. If acritical point is reached, �rst of all we check if it corresponds to a critical pointwe had already found. Otherwise we store information about it in a criticalpoint table, and we reorganize the list of the iso-values so to have a smoothapproach to the potential value of the critical point (for which the iso-potentialsurface has to change its topological structure) and a smooth leave from it.An iso-value entry immediately after the value of the critical point is insertedtoo, and this entry is marked as related to a critical point. The reasons fordoing this are explained in xA.3.1.

3. when an entry is marked as being related to a critical point, what we have todo is just change the topology in order to break the surface or to make a holein it (see section xA.4 and following).

67


Let's look more carefully at what is happening to the surface and how the polygonmesh created by the algorithm behaves when the potential value corresponds to acritical point.

A.3.1 What is happening to the surface

As explained in xA.2.1, there is a substantial di�erence of the topology between twoiso-potential surfaces immediately before and immediately after the critical point.What we have to do now is to understand what is happening, and to act in sucha way to follow the events. This means making a �ssure or a hole in the structureand recreating a closed manifold with a correct topology. But how to do this?

Let's call for short critical value the value of the potential at the critical point.According to xA.3, the list of the iso-values of the potential close to the criticalvalue (where Vc is the critical value and Vi is the entry related to the critical point)is organized in this way:

� Vi�1 = Vc�SECURITY V ALUE. The surface 1 corresponding to Vi�1 is farenough from the critical value and it doesn't have any peculiarity (�g A.3).

� Vi = Vc + �c, where �c is arbitrarely small but greater than zero. The surfacehas already changed properties, but it is very close in the space to the criticalpoint (�g A.4 shows the surface for Vi = Vc).

� Vi+1 = Vc + SECURITY V ALUE. The surface is far from the critical point.The security value allows the new topology to stabilize 2 (�g A.5).

Since the shrink wrap algorithm moves vertices from one iso-potential surfaceto the next, immediately after the critical value, there are some edges connectingpoints belonging to the surface, but these edges are not properly part of the surface,because the surface has "disappeared" beneath them (e.g consider the edge A�Bin �g A.5). This behaviour is due to the high curvature of the isosurface in theneighbourhood of the critical point. This curvature is much higher than the oneof the �nal surface, althought outside this region the curvature is still less than �,where � is the value of the maximal curvature of the surface to tile; this is the reasonwhy these edges contradict lemma 3.

1The surfaces drawn here in �gures A.3 to A.5 are intersections of the iso-surface with a plane

passing through the critical point and parallel to the cutting plane normal. These surfaces are

irrespective to the kind of the critical point.2for further details see xA.4 and followings

68


A B

Figura A.3. Iso-potential surface for V0 < Vc

A B

Figura A.4. Iso-potential surface for V0 = Vc

A B

Figura A.5. Iso-potential surface for V0 > Vc

69


Let's call these edges red edges3. So the red edges set is the set composed by allthe edges of the structure surrounding the critical point after the critical value. Inthe same way we can build a set composed by red triangles.

De�nition A.3.1 A red triangle is a triangle of the mesh in which at least one ofits edges is red (see �g A.6).

o

o

o

oo

Red edge

Normal edge

Red triangleo

Figura A.6.

A.3.2 How to detect red edges

What we need now is a mathematical condition to detect red edges. From lemma4 in [Overveld 93, page 9] we know that, in the case of an acceptable chord, themaximal relative deviation between a chord and its shadow is:

E � 1 + cos(�2 )�

p3

1 � sin(�2 )(A.5)

where � is a real-valued parameter that states the acceptability of a chord (� isthe maximal angle achievable between the gradients in the extremes of the chord toconsider the chord acceptable).

However, we cannot properly use this lemma, since we don't know if there is anyshadow underneath the chord. What we can say is:

3A more accurate de�nition of red edge will be given in the next section.

70


if there is any shadow beneath a chord the maximal relative deviation between achord and its shadow is less than E.

Another problem is that lemma 4 holds only for non-self-intersecting surfaces;instead, our attention is really focused on self-intersecting surfaces. Anyhow, we canconsider valid this lemma making the following consideration: the starting structureis a thetraedron or an icosaedron wrapping the equipotential surface at a very lowpotential; vertices and edges are repeteadely shifted on higher potential surfacesuntil the �nal one is reached. So, a con�guration like the one shown in �gure A.7ais not reachable, because the approximating structure is always wrapping externallythe real iso-potential surface.

(a) (b)

A AA B

BBBA n nnn

Figura A.7. Unbounded error for self-intersecting surfaces (a) and for non-self-intersecting surfaces (b).

Intuitively, the method we want to follow in the labeling process is the following:

� as shown in �gure A.5, the surface at a value Vc+ � is made up of two di�erentsurfaces or contains a hole; the chords "hanging" between the two surfaces(like the chord A�B) are not approximating any part of the surface;

� in this situation, the region of space underneath the candidate red edges hasa potential lower than the iso-value; in particular the location correspondingto the point at maximal distance away from the chord in a case of a non-self-intersecting surface has a potential lower than the iso-value;

What we can do now, is calculate the potential of the location speci�ed byequation (A.5) and confront it with V0 (the iso-value): if it is greater or equal V0,the point falls on or inside the equipotential surface (that means also that a surfacebeyond this edge exists), otherwise the edge falls in the case of the previous items.

71


Named C the point at maximal distance away from the chord, there are severalway to compute its potential.

A �rst way to proceed is to calculate the value of the potential in C by meansof a simple �rst order Taylor expansion (see �g. A.8)

C

Lower potential

Higher potentialA BM

S

Figura A.8. A chord and its shadow when the distance chord-shadow is maximal

M is the middle point of A�B, and �S is the vector from M to the maximaldistance point (C), and j�Sj = E � jA�Bj. So:

f(C) = f(M) + (rf(M);�S) + h:o:t: (A.6)

where h.o.t. are:

h:o:t: =1

2(�S;r(�S;rf)) + (Oj�Sj3) (A.7)

(�S;r(�S;rf)) can be considered neglectable in comparison with (rf(M);�S).To give an upper bound for the expression of equation (A.6) we can call �V themaximal value of the dot product between rf and �S:

�V = jrf j � j�Sj (A.8)

and so

f(C) � f(M) +�V (A.9)

We can consider that f(M)+�V gives an upper bound for the real value of thepotential in C (it is possible to show that we can consider it as a valid approxima-tion).

Now we have to distinguish between two cases:

72


� underneath the chord there is a surface. Point C falls inside the iso-potentialsurface and so f(C) � V0, where V0 is the value of the actual iso-potentialsurface.

� underneath the chord there is no surface. All the points beneath the chord ABhave a potential lower than or equal to the critical value, that is lower thanV0. Hence f(C) < V0.

If the condition f(C) � f(M) +�V < V0 is satis�ed, the edge AB is labeled asred. Instead, the condition f(M) +�V � V0 is not enaugh to assure that point Cis inside the isosurface.

We can calculate the exact position of C. Using the plane curve assumption([Overveld 93, page 5]), this point falls on the line perpendicular to A�B passingthrough M , in the same half-plane of rf(A) and rf(B) with respect to the linepassing through A and B and at a distance E � jA � Bj from M . Knowing theposition of C we can calculate the value of the �eld there (see �gure A.9)

B

M

C

AΠ

Figura A.9. Calculating C using the plane curve assumption

To avoid waste of resources and of computation time, the process of labelingedges is started only when we need it, that is when the mesh we are computingcorresponds to the potential in a critical point.

73


A.4 Fixing the topology

After we have found a set D of red edges we can derive from it a set of vertices,called rev vertices (REd triangle Vertices). T is the set of rev vertices.

De�nition A.4.1 A vertex v belongs to T if v is a vertex of a red triangle.

We can de�ne a neighbourhood relation between rev vertices

De�nition A.4.2 v1 2 T and v2 2 T are rev-neighbours if there exists an edgeconnecting v1 and v2 which is not a red edge (�g A.10).

A

B

E

D

C

Red edge

Normal edge

A and B are rev-neighbours and so C and D but not B and C

A,B,C,D are revs, but not E

Figura A.10.

Removing red edges from the mesh, vertices facing empty space are the verticesbelonging to T . From these vertices we can derive two subsets of rev (T1 and T2)that have no rev-neighbourhood relations between them.

One can think about these two subsets as the border of the splitting surfaces(just as the rim of a glass) and they contain the points from which start to build anew closed manifold (see �gure A.11).

De�nition A.4.3 A subset Ti of T is correct if every vertex in Ti has exactly tworev-neighbours.

What we could expect now is that all the revs have two rev-neighbours. Thisproperty results from the triangular tessalation of the surface. Unfortunately, wedon't always get this behaviour. One "unlucky" case is, for example, when you have

74


Revs

Red edges

Figura A.11.

a very asymmetrical distribution of the charges in the space. What one can obtainis a situation like the one shown in �g A.12; this is caused by having very shortedges that are still part of the surface, but are in the middle of the red edges area.

Anyway, by means of adding or removing edges from D, it is possible to havetwo subsets of T that are correct. A simple way to enlarge T is the following:

75


Charge primitivesRed edges

Edge A is still part of the surface

rev nr. 1 has three rev-neighbours

1A

2

rev nr. 2 has only one rev-neigh.

Figura A.12.

� If a rev v has only one rev-neighbour, we can label the edge connecting it withits neighbour as red.

� If a rev v has more than two rev-neighbours, we can label as red the edgesconnecting it with other revs having only one or more than two rev-neighbours.If none of its neighbours satisfy this condition, we can label as red all the edgesconnecting v with its rev-neighbours (we couldn't �nd an intuition as to thegeometrical con�guration corresponding to this case).

The aim of this process is to obtain two subsets that form a closed surface in thespace (with order of connection one), and a neighbour chain of the revs belongingto the subset that forms a closed loop. This is essential to understand which kindof singularity we have (a �ssure or a hole).

A.4.1 Is it a �ssure or is it a hole?

There is a very easy way to understand which kind of singularity we have. If wealready have T1 and T2 subsets that are correct, we can have two di�erent cases.

When a �ssure occurs, the two borders of the �ssure are connected together onlyby a series of red edges, but revs belonging to the same subset (T1 or T2) can only

76


have rev-neighbourhood relations and no other kind of connections between them;so we can't have any red edge connecting v1;v2 2 Ti. A red edge can only connecttwo revs belonging to di�erent subsets. The surfaces de�ned by T1 and T2 are insidethe iso-potential surface created (see �gure A.13):

red edges can only connect

revs belonging to different

subsets

surface defined by a subset of T

Iso potential surface

created

is inside the isopotential surface

Figura A.13.

When the singularity is a hole, T1 and T2 represent again the two borders of the�ssure, but this time they do not have any kind of connection between them. Revsbelonging to the same subset can be connected together either via a red edge or viaa rev-neighbourhood relation.

A red edge can only connect two revs belonging to the same subset. The surfacesde�ned by T1 and T2 are through and through part of the isopotential surface created(see �gure A.14):

Now we can take any rev A that is a vertex of a red edge; B is the other vertexof the same edge. As explained above, since A and B are connected via a red edge,in the case of a �ssure A and B belong to two di�erent subsets, whereas in the caseof a hole A and B belong to the same subset; so, just by checking to which subsetA and B belong we can know what kind of critical point we have.

77


iso potential surface

surfaces defined by the subsets

of T are part of the iso potentialconnections

subsets have no direct

two revs of different

surface created

Figura A.14.

The method implemented is a little bit di�erent. Instead of dividing T intosubsets and then checking the kind of each subset, we assign a kind to the subsetwhile we are building it. So, taken a red edge and named its vertices A and B, wecan start a loop for the neighbours of B. Named P0 the vertex B and P1 one of itsneighbours, the loop is performed by moving from P0 to P1, P2; : : : ; Pn. If we meetA, then A and B belong to the same subset, because rev-neighbourhood relationscan exist by de�nition only between revs belonging to the same subset, and we haveto deal with a hole. Instead if we end the loop returning to B without having metA, then A and B belong to di�erent subsets (that is, we have a �ssure; one face ofthe �ssure is the subset containing A and the other is the subset containing B).

78


A.4.2 How to �x the topology

Now we know whether we have to make a hole or to �ssure the surface. Even nowwe have two di�erent way to proceed. One thing in common for the two methods,is that before creating a new topology, we have to destroy the old one. That is,we have to remove red edges, red triangles, and all the revs that become isolatedbecause of the removal of all the surrounding triangles. These revs are due to theenlargement process and they are surrounded only by red edges; so, they properlybelong to neither of the constructed subsets of T , although they do belong to T (e.g.see vertex A in �g. A.15).

B

T

T

A is a rev but it doesn’t belong

to any of the subsets of T. Edge AB

has been labelled as red during the enlargement

process (see also fig 9).

2

1

A

Figura A.15.

Fixing a �ssure

For every border we have to connect together revs belonging to the same subset.The easiest way to do it is:

79


1. calculate the center of the border (Ci =P

vj2Tivj

nwhere n = jTij )

2. shift it on the iso-potential surface

3. connect all the vertices of the border with it

We will obtain n new triangles and 1 new vertex (�g. A.16).

C

T i

i

Figura A.16.

This method produces a low number of new triangles but sometimes producesvery stretched ones, especially when the �ssure occurs in a point of high curvature.This means that in this part of the surface there is a very high density of triangles,that results in having a vertex, the center of the border, connected with a lot ofsurrounding vertices (a little hedgehog in the mesh). This vertex has a strongpredominance as respect to its neighbours, and some operations, such as relaxation,are ine�ective when applied to it.

To overcome this disadvantage when jTij exceeds a chosen value we can use adi�erent �xing method, which consists in building a sublayer in between the centerof the subset and the rev neighbours chain. The dimension of this sublayer shouldbe such that, at the end of the �xing process, both its member and the center ofthe subset will have almost the same number of neighbours (that results in havingalmost the same number of surrounding triangles for these vertices). This can bedone in the following way:

1. Set an order relation between the revs of the subset (e.g. take a rev and assignto it the order number 0. Choose one of its neighbours and assign to it the ordernumber 1. Following the loop in this direction assign an increasing order numberto every rev you meet). L is the set of rev belonging to the sublayer. Initially L=;.

80


2. Compute a step factor STEP =jqjTij

k

3. For every rev of the subset having an index i multiple of STEP do:

calculate the mean point between i and the center of the subset; call this vertexv.

shift v on the iso-surface. L=L+v.

The sublayer and the neighbours chain can be connected following the sameprocedure explained in xA.4.2; the sublayer and the subset center can be connectedas explained in the previous part of this section.

Figura A.17.

If n = jTij and m =ln=jq

jTijkm, then we will obtain 1 + m new vertices and

n + 2m new triangles. In �gure A.17 is shown a very simple case in which jTij = 6and m = 3. The mean number of neighbours for each vertex of L is m + 3, whilefor the center of Ti is m.

81


Fixing a hole

Fixing a hole when the rain gets inand stop my mind from wandering

where it will goLennon & McCartney

Now the situation is a little more di�cult. We have to connect revs belonging toT1 only with revs of T2 (see �g A.14). Then the connecting edges should not crossthe hole, otherwise we will only build up a di�erent mess.

What "do not cross the hole" means in mathematical terms is that the twoextremes of the connecting edges (named A and B) must lie in the same half spacede�ned by the plane perpendicular to the projection of the vector A� C or B � C(where C is the critical point) on the cutting plane. A simpler de�nition is that thedot product between the projections of A � C and B � C on the separating planemust be positive (see �g A.18).

B

A

C

Figura A.18.

The main idea of the criterion is to try to connect revs following the sameorientation in the neighbourhood chain of the two subsets. Since the two subsetscan have di�erent dimensions, we try to link a rev with the nearest rev chosen inthe neighbourhood. We can proceed as follows:

1. look for a starting point. Here we look for two vertices belonging to two di�erentsubsets that have minimal distance and that are not crossing the hole. Whenwe �nd them we also choose the orientation to follow in the neighbourhood loop(clockwise or counterclockwise).

82


2. connect the two vertices together; I and J are the starting revs, NEXTI and NEXTJare their neighbours in the orientation chosen in step nr. 1.

3. a and b are the distances between this vertices as shown in �g. A.19

I NEXT_I

J NEXT_J

a

b

Figura A.19.

if a=min(a,b), connect I and NEXTJ. Then let J=NEXTJ and NEXTJ=nextneighbour of NEXTJ. Go to step 4

else, connect J and NEXTI. Then let I=NEXTI and NEXTI=next neighbour ofNEXTI. Go to step 4

4. if both I and J are equal to their starting value, exit. Else go to step 3

If jT1j+ jT2j = n, we will obtain n new triangles (�g. A.20).

T

T

1

2

Figura A.20. jT1j = 5;jT2j = 4. 9 new triangles

83


A.5 Dealing with complex topologies

The method described in the previous paragraphs works very well, but it is a littlebit too simple. If it's designed in this poor way, it just can deal with only onecritical point at the same time, but the topology can be arbitrarely complicated.Consider for instance four point charges on the vertices of a square, all having thesame charge value. At a certain potential there are four �ssures (one for every edgeof the square) at the same time.

So we have to �nd a new organization of the data base, that is able to managethese situations.

A.5.1 Some de�nitions

Let us start by some de�nitions.

De�nition A.5.1 A critical point is active when the value of the iso-potentialsurface we're creating is corresponding to the value of its own potential, that is (asexplained in xA.3.1) V0 = Vc + �, where V0 is the iso-value and Vc is the potentialvalue of the critical point

Now that we consider the case of having more than one critical point at thesame time, T should not be split into two subsets only, but into a greater number ofsubsets depending on the number of the active critical points. So, we have to relatecritical points and subsets.

De�nition A.5.2 A subset Ti is related to a critical point Pj that is the criticalpoint closest to the center of the rev-neighbours chain of the subset.

First thing we have to remark is that it is possible, because of approximationsin the computation and because of the fact that vertices are never exactly on theiso-potential surface, that some edges are labeled as red whereas they're still part ofthe iso-potential surface. That is more likely when you get really close to a saddlepoint, but the potential value you're computing is related to a second critical point,that is somewhere else in the space.

De�nition A.5.3 A subset Ti of T is active if it is related to a critical point thatis active.

Another problem is that we have to �nd a way to link borders; to link the twofaces of a �ssure is trivial since they are connected by a red edge. More complicated

84


is the case of two sides of a hole, because there isn't any kind of connection betweenthem.Two hole faces are faces of the same hole if they relate to the same criticalpoint and the dot product between the vectors connecting critical point and centersof the subsets is less than zero.

A.5.2 How to proceed

We can proceed in the following way. First of all we build up all the followingstructures:

1. we store all the information about the critical points we have found in a table.So we know where they are and what their potential value is.

2. when a critical value is reached, we build a table of revs, in which we record:

- information about the point (position, potential value, neighbour vertices,etc: : : )

- the number of the rev-neighbours and the connecting edges

- the index of the subset of T it belongs to

3. a table of subsets of T to store:

- cardinality of Ti

- which critical points it relates to (that is the critical point closest to thecenter of the rev-neighbours chain)

- which kind of border it is (if it is a face of a �ssure or a part of a hole)

- a ag to know if the subset is active

- the subset Tj which Ti relates to

When we reach a critical value:

� rev table is build up

� T is divided into subset as explained before and to every subset is assigned atype (�ssure or hole)

� Every rev is labelled with the index i of the subset it belongs to or with �1 ifit doesn't belong to any subset, and every subset is related to a critical point

� Active attribute is set for all T subsets

85


� for all the active subsets:

Subsets are linked

all red triangles revs of the active lists belong to are removed

all isolated revs are removed

structure is �xed as explained before

86


A.6 Evaluations

A quantitative analysis of the overload introduced by the new features is not straight-forward, since no comparison can be made on the same instances with the earlierShrinkwrap. So one must be satis�ed with computing the mean increase in termsof IFEPTs (Implicit Functions Evaluated Per Triangle). The results are not yetcomparable because the number of IFEPTs depends on the number of iterationsdone; in [Overveld 93] this number is 7 (the optimal number) and here it is usually9, so a rescaling of the results is due.

The overload introduced is mostly due to the iterations of the Newton-Raphsonmethod. However it is possible to run Wsoid avoiding this process: the programautomatically records informations about critical points on a �le and restartingthe process we will have all the necessary information on them without needs ofany computation. In the table nr. A.1 we show a comparison between these twomethods.

Instance Triangles Newt.on IFEPTs Newt.o� IFEPTs Di�erence

4lines 746 7668 10.28 6582 8.82 -14.20 %1torus 458 5230 11.42 4475 9.77 -14.44 %4points 2366 43618 18.44 32035 13.54 -26.57 %2triangles 640 11875 18.55 8107 12.67 -32.80 %2points 1204 26152 21.72 16679 13.85 -36.22 %1line-1point 606 14267 23.54 6969 11.50 -48.85 %

Tabella A.1.

The old Shrinkwrap gives an IFEPT ' 8:31; now we have IFEPT ' 11:69(+40.67%) when Newton computation is o� and IFEPT ' 17:32 (+108.42%)when it is on. Rescaling the results we obtain, respectively, 9.85 (+18.52%) and14.55 (+75.08%).

The instances used to build table A.1 contains usually only one critical pointexcept 4points that consists of four equal point sources on the vertices of a squareand that creates one hole in the center of the square and four �ssures on the edgesof the same.

Two observations shall be made. First, the instances in the three starting linesall generate holes; their "economicity" is due to the fact that an hole usually givesrise to a much lower number of red edges as regards of a �ssure. Second, the numberof computation of the Newton-Raphson method penalize considerably the perfor-mances. This number depends mainly form the dimension of the set S; reducingthis dimension, that is a parameter of the program, the overload introduced is con-sequently reduced. The default threshold for S is maybe expansive, but has the

87


advantage of being able to deal with any input instances, irrespective of its com-plexity.

A.7 Conclusion

We present an improvement of the Shrinkwrap algorithm. Now almost every kindof �nal iso-potential surface can be polygonized (see Appendix) even if we have tochange the topology of the starting surface (the original tetrahedron).

All new features respect the basic philosophy of the primary Shrinkwrap, andthey can be made "transparent" to the user, since the list of the iso-valuess used toreach the �nal surface is automatically changed in order to take care of the criticalpoints introduced by the instances.

A disadvantage still to solve is that it is not possible to �x a hole with more thantwo splitting surfaces.

A.8 Acknowledgments

I would like to thank the people who made this work possible: Kees van Overveldand Wim Nuij. Without their help I would still be digging into problems. Thanksfor being always very friendly, available and patient. A lot of thanks also to allthe members of the Computer Graphics Group that I stressed asking every kind ofinformation. The biggest thank is anyway for Claudia, for all the support she gaveme and for being close to me during this period.

88

Bibliogra�a

[Artley 65] J. Artley,Fields and con�guration, Holt, Rinehart and Winston,pages 192-205, 1965.

[Bink 94] A.J. Bink, E.H. Hautus, C.W.A.M. van Overveld. Visualizing vol-umetric data: an automatic solution to the branching problem.Technical University Eindhoven, internal report, 1994.

[Blinn 82] James Blinn. A generalization of algebraic surface drawing. ACMTransactions on graphics, 1:235, 1982.

[Bloomenthal 87] Jules Bloomenthal. Boundary representation of implicit surfaces.Res. Rep. CSL-87-2, Xerox PARC.

[Bloomenthal 88] Jules Bloomenthal. Polygonisation of Implicit Surfaces. ComputerAided Geometric Design, (5):341-355, 1988.

[Bloomenthal 90] Jules Bloomenthal, Brian Wyvill. Interactive techniques for im-plicit modeling. Proceedings of the SIGGRAPH '90. In ComputerGraphics 24, 4, pp 109-116.

[Cohen 94] Daniel Cohen, Arie Kaufman, Yingxing Wang. Generating asmooth voxel-based from an irregular polygon mesh. The VisualComputer (1994) 10:295-305.

[H�olmstrom 89] H�olmstrom L, Laakko T, M�antyla: M, Rekola P. Ray tracing ofboundary models with implicit blend surfaces. In: Stra�er W. Sei-del HP (eds) Theory and practice of geometric modeling. Springer,Berlin Heidelberg New York, pages 252-271.

[Mizr 82] Abe Mizrami and M. Sullivan, Calculus and analytical geometry,Wadsworth Publishing Company, 1982.

[Press 86-1] W.H. Press, B.P. Flannery, S.A. Teukolsky, W.T. Vetterling, Nu-merical Recipes, Cambridge UniversityPress, pages 270-273, 1986.

89

Bibliogra�a

[Press 86-2] W.H. Press, B.P. Flannery, S.A. Teukolsky, W.T. Vetterling, Nu-merical Recipes, Cambridge UniversityPress, pages 335-380, 1986.

[Schmidt 93] Michael F.W. Schmidt.Cutting cubes; visualizing implicit surfacesby adaptative polygonization. The Visual Computer (1993) 10:101-115.

[Sederberg 86] Thomas W. Sederberg, Scott R. Parry. Free-form deformation ofsolid geometric models. Proceedings of the SIGGRAPH '86. InComputer Graphics 20, 4, pp 151-160.

[Overveld 93] C.W.A.M van Overveld and Brian Wywill Shrinkwrap: an adap-tative algorithm for polygonizing an implicit surface, The Univer-sity of Calgary, Department of computer science, Research ReportNo. 93/514/19, March 1993.

[Witkin 94] Andrew P.Witkin, Paul S.Heckbert. Using particles to sample andcontrol implicit surfaces. Proceedings of the SIGGRAPH "94. InComputer Graphics 20, pp 269-277.

[Wyvill 86] Geo� Wyvill, Craig McPheeters, Brian Wyvill Data structure forsoft objects. The Visual Computer (1986) 2:227-234.

90

esi di Laurea - polito.it · 2006-09-18 · ti da quelli italiani, questa esp erienza mi ha anc he...

Documents

Transcript of esi di Laurea - polito.it · 2006-09-18 · ti da quelli italiani, questa esp erienza mi ha anc he...