IL PROBLEMA SSI NELLA MODELLAZIONE SOLIDACON SUPERFICI NURBS
Nota di GIULIO CASCIOLA, SERENA MORIGI 
Presentata da ILIO GALLIGANI, Accademico Corrispondente Residente
nella seduta del 22 Febbraio 1995

Sommario

Abstract. This note presents a modi ed version of the marching method
proposed in [1], for NURBS surface/surface intersection.
The balance between robustness and eciency, an open question in SSI algorithms, is resolved by a clear trick. Sperimental analysis on the set oftolerances which control robustness, accuracy and eciency shows a good
behaviour of our proposal.

1. Introduzione

I piu moderni sistemi di modellazione solida permettono di progettare, visualizzare
ed analizzare al calcolatore oggetti complessi de niti, mediante rappresentazione
boundary, da super ci sculturate (o a forma libera) prima di passare alla fase diproduzione.
Uno dei problemi di ricerca nel progettare tali sistemi di modellazione solida e quellodi estendere il dominio geometrico da super ci piane a tratti e quadriche a super ci
a forma libera. In questo senso le curve e super ci NURBS (Non Uniform Rational
B-Splines) sono a tutt'oggi lo strumento piu idoneo per risolvere tale problema senza
dover costruire un sistema ibrido; infatti essendo una generalizzazione delle spline
hanno tutte le possibilita per generare una grande varieta di forme ed essendo dellerazionali possono rappresentare esattamente le coniche e le quadriche.
Uno dei maggiori problemi computazionali nel progettare i sistemi di modellazione aforma libera consiste nella dicolta di risolvere i problemi di intersezione fra super ci(problema SSI).
 Questa ricerca e statananziata dal CNR-Italy, Contratto n.94.00132.CT01

1

Il problema SSI

G. Casciola, S. Morigi

L'intersezione e l'operazione base per e ettuare operazioni Booleane come unione,
di erenza e intersezione, che servono nella fase di modellazione di oggetti complessi
costruiti a partire da semplici primitive.
In letteratura sono presenti molte proposte per il problema SSI [1, 2, 8]. Indipendentemente dall'approccio usato un buon algoritmo deve soddisfare tre proprieta:accuratezza, robustezza ed ecienza.
La curva di intersezione calcolata deve essere una buona approssimazione, nella
tolleranza richiesta, della vera curva di intersezione.
L'algoritmo non deve essere soggetto a fallimenti e deve trovare tutte le porzioni diuna curva di intersezione che puo essere formata da piu rami disgiunti.
Per la maggior parte delle applicazioni, l'algoritmo deve essere eciente cosi daconsentire una interazione in tempo reale fra il progettista ed il sistema.
Queste richieste presentano un serio dilemma. Un algoritmo robusto ed accurato puoessere molto lento, mentre un algoritmo eciente puo fallire in certi casi. Nessuno
degli algoritmi noti in letteratura soddisfa tutte e tre queste proprieta. Anche un
algoritmo sia di uso pratico si devono introdurre signi cativi compromessi fra le sue
proprieta.
In questo lavoro si vuole presentare una versione modi cata della proposta di Barnhill ed altri [1] per l'intersezione di super ci in forma parametrica, per l'intersezione
di super ci NURBS.
Il compromesso robustezza-ecienza viene qui risolto introducendo un particolare
accorgimento nell'algoritmo che garantisce la massima robustezza senza perdere inecienza a fronte di una piccola limitazione di applicabilita del metodo.

2. Super ci NURBS trimmate

Una super cie spline relativa ad una partizione non uniforme di nodi del dominio
U  V = [0; 1]  [0; 1] puo essere de nita come prodotto tensoriale di funzioni spline
e rappresentata danXH mXK
cij Ni;n (u)Nj;m(v)s(u; v) =++i=1 j =1

dove Ni;n (u) e Nj;m(v) sono le B-spline Normalizzate di ordine n ed m rispettivamente de nite sui vettori dei nodi:(0; :::; 0; un ; :::; un H ; 1; :::; 1)+1+(0; :::; 0; vm ; :::; vm K ; 1; :::; 1):+1+

con nodi agli estremi aventi molteplicita n ed m rispettivamente.

Il problema SSI

G. Casciola, S. Morigi

Una super cie NURBS viene de nita come il rapporto fra super ci spline appartenenti allo stesso spazio prodotto tensoriale; una super cie NURBS in forma parametrica e data nella forma seguente:
Pn H Pm K w P N (u)N (v)(1)
r(u; v) = Pi n H Pj m K wij Nij i;n(u)N j;m(v)ij i;nj;mijdove i wij sono numeri reali positivi detti pesi, e i Pij punti 3D di controllo che
de niscono una griglia detta di controllo.
Nonostante sia ottenuta a partire da super ci prodotto tensoriale, una super cie
NURBS non e una super cie prodotto tensoriale.
Introducendo le funzioni B-spline razionali normalizzate
wij Ni;n(u)Nj;m(v)Ri;n j;m(u; v) = Pn H P
m K w N (u)N (v )ij i;n
j;m
i
j
+
=1
+
=1

;

+
=1

+
=1

+
=1

+
=1

la (1) puo essere scritta nella forma:r(u; v) =

+K
nX
+H m
X

i=1 j =1

wij Pij Ri;n j;m (u; v);

Le super ci cosi de nite rappresentano uno schema bidirezionale di curve 3D NURBS;
se infatti si ssa uno dei parametri, per esempio u 2 [0; 1], allora permettendo av di variare in [0; 1] si ottiene una sezione della super cie che altro non e che una
curva 3D NURBS, cioemXKc(v) = r(u ; v) = Qj (u )Rj;m(v)
0

+

0

j =1

0

I Qj (u ) sono gli m + K punti di controllo 3D per la curva c(v) [5].
Si de nisce trimmed surface la restrizione di r(u; v) ad un sottodominio D  U 
V , dello spazio parametrico, chiamato trimming region. Il dominio D e de nito
come l'insieme di regioni di U  V limitate da rami di curve chiuse orientate e nonintersecantesi, dette trimming curve.
0

3. Solidi NURBS

Seguendo la rappresentazione boundary di un solido, si puo de nire solido primitivo
ogni solido avente come boundary una sola super cie NURBS che banalmente deveessere chiusa per dividere lo spazio in due parti una delle quali limitata.
Tra i solidi primitivi che rispondono a questa de nizione si trovano per esempio
sfere, tori, super ci chiuse di rotazione e super ci chiuse a forma libera.

Il problema SSI

G. Casciola, S. Morigi

I solidi primitivi possono poi essere composti mediante operazioni booleane, qualiintersezione, unione e di erenza, per dar luogo ad un solido composto.
Il costo e le dicolta incontrate nella combinazione booleana di solidi primitivi
a forma libera sono state in parte superate grazie all'introduzione delle trimmed
surface che permettono una rappresentazione completa del boundary di un solido
attraverso l'unione di super ci ristrette ad opportuni domini. Il boundary di unsolido composto S e quindi[kbS = ri(Di )i=1dove Di e la trimming region associata alla super cie ri
Il boundary del solido composto e nuovamente una super cie chiusa.
Dati due solidi A e B de niti dalle rispettive super ci di Sbordo, il Tproblema dellacomposizione consiste nel determinare i bordi dei solidi b(A B ), b(A B ) e b(A B )a partire da[h[kbA = ri(Di ) e bB = sj (Ej )
i=1

j =1

dove ri ed sj sono trimmed surface de nite sulle trimming region Di e Ej .
Alla base di tali operazioni vi e l'intersezione fra trimmed surface che risulta unproblema molto complicato; seguendo le proposte di [4] e [6] tale problema puo essere
riformulato eseguendo l'intersezione solo tra le super ci non trimmate (de nite cioesull'intero dominio parametrico).

4. Il problema SSI

Tra i diversi metodi proposti in letteratura per la risoluzione del problema SSI,
i metodi geometrico e numerico sono da considerarsi le tecniche che presentano
maggior interesse da un punto di vista computazionale. Il metodo geometrico, robusto ma lento, e basato sulla decomposizione ricorsiva del problema in problemi
piu semplici no alla risoluzione di intersezioni di sottosuper ci elementari (triangolo/piano). Mentre alla base del metodo numerico e la generazione di una sequenza
di starting point, almeno uno per ogni ramo di curva di intersezione, dai quali risalire
alle curve richieste che saranno poi raccordate nella fase di ordinamento. L'approccio
numerico si avvale di tecniche iterative, e veloce ma meno adabile.
Nell'ottica di trarre vantaggio dalla robustezza del metodo geometrico e nel contempo mantenere l'ecienza del metodo numerico, nasce il metodo ibrido. Tecnichegeometriche vengono utilizzate per localizzare gli starting point che sono poi ranati
mediante tecniche numeriche no ad ottenere le esatte curve di intersezione.

Il problema SSI

G. Casciola, S. Morigi

Seguendo la proposta di Barnhill ed altri [1], si vuole mettere a punto un algoritmo ibrido che si avvalga delle potenzialita delle super ci NURBS per ottenere
signi cativi risultati.
Il risultato dell'intersezione di due super ci puo essere: 1) un insieme vuoto, 2)
un insieme di punti, 3) un insieme di curve, 4) un insieme di super ci o 5) una
combinazione di 2), 3) e 4).
Due super ci sono dette essere in posizione generale se la loro intersezione e di tipo
1) o 3). L'algoritmo proposto nel presente lavoro tratta solo super ci in posizione
generale che vengono approssimate da curve lineari a tratti su domini parametrici.
Per determinare un giusto compromesso tra accuratezza, robustezza ed ecienza, si
prendono in considerazione i seguenti parametri di tolleranza:
1. Same Point Tolerance (SPT): se due punti 3D sono ad una distanza inferiore ad
SPT allora sono da considerarsi un unico punto;
2. Search Re nement Tolerance (SRT): regola la qualita della suddivisione adattiva
della super cie;
3. Curve Re nement Tolerance (CRT): se due punti appartenenti ad una curva diintersezione sono ad una distanza inferiore a CRT, il segmento che li unisce e preso
come approssimazione del tratto di curva che li separa.
Prima di passare ad una descrizione dettagliata dell'algoritmo se ne illustrano brevemente le quattro fasi principali. La prima fase (Generazione griglia adattiva) consiste nella approssimazione di ciascuna delle super ci mediante una griglia adattiva
di curve isoparametriche approssimate da lineari a tratti seguendo la tolleranza SRT.
Da una tale grigliatura si puo ottenere banalmente una triangolarizzazione della super cie. Nella seconda fase (Generazione starting point) si utilizzano intersezioni
elementari (segmento di una super cie/triangolo dell'altra) per ottenere almeno uno
starting point per ciascuna curva di intersezione. A partire da questi punti il passo
successivo (Generazione curve di intersezione) si propone di determinare gli altri
punti sulle varie curve di intersezione. Nella fase conclusiva (Ordinamento) si procede al raccordo dei rami di curva trovati no alla determinazione delle curve diintersezione 3D.

5. Generazione griglia adattiva

Per poter ricondurre il problema SSI ad un insieme di intersezioni fra triangoli esegmenti, si devono approssimare le due super ci curve con triangoli piani. Questo
si ottiene mediante un procedimento ricorsivo che, a partire da un insieme di curveisoparametriche (in genere tre) in entrambe le direzioni u e v, suddivide ogni tratto
di curva nel punto medio, nel caso la distanza tra il tratto di curva in esame e ilsegmento sotteso superi la tolleranza SRT. Dalla grigliatura rettangolare ottenuta
si passa facilmente ad una triangolarizzazione inserendo le diagonali. Per rendere
meno onerosa questa fase si sono sfruttate alcune caratteristiche delle curve NURBS.

Il problema SSI

G. Casciola, S. Morigi

Il problema del controllo della linearita di un tratto di curva NURBS rispetto ad
una tolleranza SRT, si puo infatti ricondurre, per la proprieta del guscio convesso
di cui godono le curve NURBS, ad un piu semplice test sulla distanza massima tra i
punti di controllo ed il segmento rettilineo congiungente gli estremi. Per poter riapplicare il test sulla distanza massima ai singoli tratti di curva si sfrutta la possibilitadi suddividere una curva in due curve NURBS su intervalli parametrici adiacenti
utilizzando la tecnica della knot-insertion per inserire nel punto medio un nodo u^(o v^) di molteplicita pari all'ordine della spline. Il procedimento iterato porta alla
convergenza del poligono di controllo alla curva.

6. Generazione Starting Point

Alla fase di approssimazione lineare delle super ci segue la ricerca dei punti diintersezione iniziali detti starting point dai quali partire, nella fase successiva, per
determinare le curve di intersezione di cui fanno parte. Una prima approssimazione
degli starting point si calcola dalle intersezioni tra le approssimazioni delle curveisoparametriche della prima super cie e la approssimazione bivariata lineare a trattidella seconda super cie. Se l'intersezione non e vuota si ottiene un punto che, in
generale, non appartiene ad alcuna delle super ci poiche generato dall'intersezionedelle loro approssimazioni. I due valori nei domini parametrici relativi al punto
trovato, individuano due punti, uno su ciascuna super cie, vicini ad un vero punto diintersezione. Quest'ultimo e calcolato con l'ausilio del metodo iterativo di NewtonRaphson a partire dai due punti nei domini che vanno a costituire l'iterato iniziale.
Il metodo risolve il sistema di tre equazioni non lineari in quattro incogniter (u; v) r (s; t) = 0
2

1

(2)

dove viene ssata l'incognita relativa alla linea parametrica in esame.
Se il metodo non converge si suddividono ulteriormente entrambe le approssimazioni
considerate per migliorare l'iterato iniziale e si riapplica il procedimento nche, o
non si ha piu l'intersezione, o si ottiene la convergenza ad uno starting point; questopuo poi essere trascurato se risulta contenuto in una curva gia trovata. Per trovare
tutti gli starting point e necessario considerare le intersezioni con tutte le linee
isoparametriche della prima super cie quindi scambiare i ruoli delle due super ci.
La fase di generazione degli starting point e la fase piu onerosa dell'algoritmo; cio e
dovuto in particolare alle numerose intersezioni segmento/triangolo la maggior partedelle quali non hanno successo. Per contenere il numero delle mancate intersezioni
e necessario eliminare a priori le coppie segmento/triangolo che non presentano
intersezione.
Un primo test di esclusione suggerito e adottato in questa implementazione e basato
sull'utilizzo di bounding box, costruite facilmente a partire dai punti di controllodelle intere super ci, per individuare, se esiste, una bounding box di intersezione e

Il problema SSI

G. Casciola, S. Morigi

considerare solo quei segmenti che hanno almeno uno degli estremi in essa.
Un secondo test, basato sulle bounding box delle coppie segmento/triangolo, evita
inutili intersezioni nel caso di bounding box disgiunte.
Un nuovo ed ulteriore accorgimento e dato dall'eliminazione delle coppie segmento/
triangolo (primo dominio/secondo dominio) se il segmento e attraversato da una
curva di intersezione gia trovata e il triangolo e quello che ha permesso di calcolare
lo starting point. Vengono eliminati inoltre i segmenti costituenti il triangolo qualora
accoppiati a triangoli nel primo dominio attraversati da una curva. Quest'ultimo' ltro' impone pero l'aggiunta di una ipotesi sulle curve di intersezione per mantenere la robustezza dell'algoritmo. Condizione necessaria per trovare tutti i rami
di una curva e che ognuno di questi si di erenzi dagli altri in almeno un dominio
parametrico, per almeno un segmento attraversato; in questo modo sara possibile
trovare un altro starting point su quella curva. Il problema di perdita di un ramo puoessere risolto diminuendo la tolleranza SRT per ottenere una approssimazione piuaccurata. Come si fara vedere nel seguito una piccola tolleranza SRT non comporta,
grazie a quest'ultimo accorgimento, un aggravio dal punto di vista computazionale
mentre risulta essenziale per la robustezza del metodo.

7. Generazione curve di intersezione

Trovato uno starting point, si costruisce per passi la curva di intersezione a cuiquesto appartiene. Si cerca inizialmente una stima del punto successivo che viene poiranata per determinare un vero punto di intersezione; quindi si rana il segmento
che unisce i due punti no a raggiungere una distanza CRT tra due punti consecutivi
ed in ne si ottimizza il risultato.
Cominciamo col determinare un nuovo punto sulla curva; chiameremo il punto corrente sulla curva di intersezione P e consideriamo un vettore V nella direzione
tangenziale alla curva di intersezione per ottenere un punto P .
Nel caso generale, V si puo determinare intersecando i piani tangenti alle due super ci in P e scalando questo vettore per essere di lunghezza proporzionale a CRT.
Poi, mediante inversione dello Jacobiano in P , si ottengono i punti corrispondenti
di P nel dominio parametrico di ciascuna super cie (s ; t ; u ; v ). Si useranno
questi punti nei domini come iterati iniziali per un procedimento iterativo super cie/super cie che cerca di trovare un punto vero di intersezione.
La routine iterativa super cie/super cie risolve le tre equazioni non lineari (2) nelle
quattro incognite s; t; u; v. Si puo utilizzare la forma linearizzata di (2), che puoessere interpretata geometricamente come l'intersezione fra il piano tangente ad rin (s ; t ) e il piano tangente ad r in (u ; v ). Il successivo iterato viene scelto comeil punto medio M delle proiezioni ortogonali A di r (s ; t ) e B di r (u ; v ) su
questa linea di intersezione (vedi Figura 1).
Invertendo nuovamente lo Jacobiano al precedente iterato si ottiene il nuovo ite0

1

0

0

1

1

1

1

1

1

1

1

2

2

1

1

1

1

1

1

1

2

1

1

Il problema SSI

G. Casciola, S. Morigi

Curva di intersezione(s1,t1)r(s1,t1)(s2,t2)

1

B1

M2

Dominio di r1

A1

r1
r12
(u1,v1)r (u1,v1 )2(u2,v2)

Dominio di r2

Figura 1: Signi cato geometrico del metodo
rato (s ; t ; u ; v ) su ciascun dominio (si rimanda all'Appendice per la descrizione
matematica di queste fasi).
Una volta trovata una nuova vera intersezione, chiamiamola ancora P , si considera
l'intervallo fra P e P . Se questo segmento e piu lungo di CRT si rana ed ottimizza
l'approssimazione alla curva di intersezione.
L'algoritmo termina la ricerca di ulteriori punti sulla curva di intersezione per uno
dei seguenti motivi:
1. la curva incontra un bordo o incontra se stessa;
2. la curva incontra un punto nale di una curva precedentemente trovata;
3. la fase iterativa non ha trovato un punto successivo;
4. la curva incontra una intersezione fra una linea isoparametrica ed una curva
precedentemente trovata.
Al termine di questa fase si ottiene una lista dei rami di curve 3D trovati e relative
coordinate parametriche nei rispettivi domini, che verranno ordinati e raccordati
nella fase successiva.
Durante la fase di tracciamento della curva puo capitare che il punto di intersezione trovato si trovi fuori dal dominio parametrico. E' necessario in questo casoseguire una strategia di estrapolazione dei punti sul bordo. Questi punti infatti
risultano fondamentali per e ettuare operazioni booleane fra le super ci intersecate. L'estrapolazione determina un punto sul bordo del dominio parametrico comel'intersezione fra la retta congiungente l'ultimo e il penultimo dei punti della curva
e la linea isoparametrica di bordo. Dai due punti trovati, uno su ciascuna super2

2

2

2

1

0

1

Il problema SSI

G. Casciola, S. Morigi

cie, si ricerca il vero punto sulla curva di intersezione mediante la procedura di
Newton-Raphson (curva/super cie). Il successo del procedimento e strettamente
legato alla tolleranza CRT poiche l'andamento della curva e stimato attraverso la
retta congiungente gli ultimi punti trovati.

8. Ordinamento

Trovati tutti i rami di curva si procede al loro ordinamento e raccordo al ne diottenere curve chiuse.
L'algoritmo considera rami di curve nello spazio, facendo coincidere in 3D, attraverso
le funzioni corrispondenti alle due super ci, i rami di intersezione trovati sui diversi
domini parametrici.
La connessione di due rami di curva avviene quando i due estremi sono a distanzaminore di CRT nello spazio o quando gli estremi si trovano su bordi opposti nel
dominio parametrico. Un punto isolato non e considerato curva chiusa ed e cosi
raccordato ad un vicino ramo di curva.

9. Analisi sperimentale delle tolleranze SRT e CRT

Gli esempi presentati vogliono essere un'analisi dei parametri di tolleranza SRT e
CRT che in uenzano le proprieta di robustezza, accuratezza e velocita dell' algoritmo. Obiettivo della sperimentazione e ettuata e quindi quanti care il concetto dicompromesso tra queste proprieta, in termini dei valori da associare ai due parametri
per ottenerlo grazie anche all'introduzione di opportuni accorgimenti implementativi.
Le super ci test utilizzate provengono dalla modellazione solida e sono tutte boundary di solidi primitivi, come de nito nel paragrafo 3. Vengono prese in considerazione
intersezioni fra super ci sculturate, fra super ci naturali (quadriche e tori) e fra sculturate e naturali. Le Figure 2-8 mostrano le intersezioni test (vengono riportate anche quelle nascoste), le super ci che le generano (rappresentate con eliminazione delleparti nascoste) e le curve di intersezione nei rispettivi domini parametrici insiemealla grigliatura ottenuta con l'SRT utilizzato (i segmenti di griglia attraversati dalle
curve sono stati cancellati seguendo la tecnica dei segmenti annullati introdotta).
La Figura 9 mostra il risultato dell'algoritmo per un problema di intersezione fra piusuper ci. I tempi presentati sono relativi alle quattro fasi precedentemente descritte
e sono rilevati in millesecondi. L'elaborazione e stata realizzata su una workstation
Silicon Graphics IRIS Indigo XZ.
La tolleranza SRT guida la suddivisione adattiva della super cie controllando laqualita dell'approssimazione lineare iniziale e in uenzando di conseguenza il numero
di intersezioni per la ricerca di starting point sulla curva di intersezione. L'SRT deveessere quindi tale da garantire almeno uno starting point per ogni ramo di curvaanche la successiva fase di tracciamento della curva possa aver successo. La scelta

Il problema SSI

G. Casciola, S. Morigi

Figura 2: Intersezione fra cubo (SRT=0.12) e sfera (SRT=0.12) con CRT=0.01. A
sinistra dominio cubo, a destra dominio sfera

Figura 3: Intersezione fra una super cie a forma libera (SRT=0.12) e una sfera(SRT=0.12); CRT=0.01. A sinistra dominio della super cie a forma libera, a destra
dominio della sfera.

Il problema SSI

G. Casciola, S. Morigi

Figura 4: Intersezione fra super ci a forma libera (entrambe con SRT=0.02);
CRT=0.02. A sinistra dominio della super cie in basso, a destra dominio dellasuper cie in alto.

Figura 5: Intersezione fra toro (SRT=0.03) e cilindro (SRT=0.03) con CRT=0.01.
A sinistra dominio toro, a destra dominio cilindro.

Il problema SSI

G. Casciola, S. Morigi

Figura 6: Intersezione fra toro (SRT=0.02) e cilindro (SRT=0.02) con CRT=0.01.
A sinistra dominio toro, a destra dominio cilindro.

Figura 7: Intersezione fra toro (SRT=0.12) e cilindro (SRT=0.12) con CRT=0.01.
A sinistra dominio toro, a destra dominio cilindro.

Il problema SSI

G. Casciola, S. Morigi

Figura 8: Intersezione fra cubo (SRT=0.01) e sfera (SRT=0.01) con CRT=0.003. A
sinistra dominio cubo, a destra dominio sfera.

Figura 9: Intersezione multipla fra tre super ci a forma libera (SRT=0.12) e una
sfera (SRT=0.12); CRT=0.01.

Il problema SSI

G. Casciola, S. Morigi

di CRT, in ne, in uenzando il numero di punti per ramo di curva determina il
successo e l'ecienza della fase di tracing.
Allo stato dell'arte non esiste alcun metodo per calcolare a priori l'esatta combinazione di entrambi i parametri che possa rispondere contemporaneamente allerichieste di ecienza, robustezza e accuratezza, ne esiste una stima degli stessi che
possa garantire anche solo il ritrovamento di tutte le soluzioni.
Poiche i due parametri in analisi, pur essendo dipendenti l'uno dall' altro, in uenzano
fasi diverse dell'algoritmo, si e preferito prenderli in considerazione separatamente
mantenendone costante uno e considerando variazioni dell'altro a partire da una
opportuna stima iniziale. La tolleranza SPT rimane invece costante ad un valorepari a 1.0e-5.

9.1. Analisi della tolleranza SRT

L'impossibilita di avere un parametro SRT che assicuri il ritrovamento di tutti irami di curva in ogni situazione spinge alla ricerca di una stima consistente con lesuper ci in oggetto, ma poco costosa in termini computazionali. Poiche il parametro
SRT deve variare in funzione della dimensione della super cie, nell'implementazione
da noi realizzata si usa un valore pari ad 1/10 del raggio della sfera contenente ilpoliedro di controllo della super cie che deriva dalla considerazione di prendere comeriferimento una super cie sferica. Queste stime iniziali per SRT si sono dimostratesperimentalmente valide in quanto segnano, nella maggioranza dei casi, la soglia
massima oltre la quale non si riescono piu a determinare tutti gli starting point
necessari per ritrovare tutti i rami di curva. Nei casi in cui una particolare curvatura delle super ci o la loro posizione relativa siano tali da portare all'insuccesso
della stima iniziale, puo essere necessario ridurre l'SRT no ad 1/10 della stima
iniziale eseguendo una serie di tentativi intermedi. Trattando solo super ci chiuse einfatti possibile veri care l'insuccesso dell'algoritmo e innescare di conseguenza una
procedura iterativa automatica basata sul parametro SRT.
Come gia in precedenza rimarcato un piccolo SRT porta ad alti costi delle fasi disuddivisione adattiva e ricerca degli starting point. Per superare questo problema epoter quindi volutamente spingere sull'SRT senza preoccuparsi del peggioramentodella prestazioni, sono stati introdotti degli accorgimenti per ottimizzare l'algoritmo.
L'ottimizzazione ha permesso di eliminare il calcolo degli starting point super ui
tramite il meccanismo dei segmenti annullati, il controllo preliminare mediantebounding box della super cie di intersezione e bounding box delle intersezioni elementari segmento/triangolo. Si puo quindi diminuire il valore di SRT ottenendo suddivisioni piu ranate senza che questo comporti un decadimento delle prestazioni.
I risultati in Tabella 1 e 2 relativi agli esempi in Figura 2 e 3, evidenziano l'aumentodel costo delle fasi di splitting e ricerca starting point in relazione al tempo totaledell'algoritmo al variare del parametro SRT dal valore consigliato ad 1/10 delloIl problema SSI

G. Casciola, S. Morigi

SRT

TEMPI (msec)
GRIGLIA
Splitting St:Point Tracing Sorting Totale
0:12
60
40
2180
120 2400 9  17 9  5
0:10
60
40
2180
120 2400 9  17 9  5
0:08
60
40
2180
120 2400 9  17 9  5
0:06
60
50
2290
120 2520 9  17 11  5
0:04
130
120
2340
130 2400 13  25 11  5
0:02
260
170
2280
130 2840 17  33 13  5
0:012
280
200
2380
130 2990 17  33 15  5Tabella 1: andamento dei tempi al variare del parametro SRT (super ci in Figura2); CRT=0.01.
4000

3500

3000

2500
tempo
(msec)

2000

1500

1000
TOTALETRACING500

SORTING0
SPLITTING
ST POINTTOLLERANZA SRTFigura 10: gra co dei tempi di Tabella 1
stesso. L'andamento e messo in risalto dal gra co in Figura 10 relativo alla Tabella
1.
La prima delle ottimizzazioni menzionate puo creare problemi nel caso ci siano curve
di intersezione che passano piu volte per lo stesso segmento. Il problema della perdita
del ramo puo essere risolto abbassando l'SRT in modo da avere una grigliaturapiu ne. Il carico di lavoro che ne consegue e illustrato nella Tabella 3 relativa
all'intersezione di Figura 4 che presenta questo caso limite di curve ravvicinate.
Per come e stata realizzata la suddivisione in griglie adattive delle super ci, il forzare
SRT verso valori molto piccoli puo presentare problemi numerici nel caso in cui la super cie sia lineare. Negli esempi di Figura 5, 6 e 7 infatti, il cilindro tende ad essere
grigliato eccessivamente in una direzione rispetto all'altra, con conseguente determinazione di triangoli 3D stretti e lunghi. Questo porta a problemi di intersezione
segmento-triangolo mal condizionati che potrebbero essere superati gestendo sepa-Il problema SSI

G. Casciola, S. Morigi

SRT

TEMPI (msec)
GRIGLIA
Splitting St:Point Tracing Sorting Totale
0:12
80
30
720
60
890 5  11 9  17
0:10
80
30
730
60
890 5  12 9  17
0:08
80
40
720
60
900 5  13 9  17
0:06
100
40
730
60
930 5  17 9  17
0:04
140
90
740
60 1030 9  23 9  17
0:02
360
460
750
50 1620 9  29 17  33
0:012
750
620
780
70 2220 9  40 17  33
Tabella 2: andamento dei tempi al variare del parametro SRT (super ci in Figura3); CRT=0.01.

SRT

TEMPI (msec)
GRIGLIA
Splitting St:Point Tracing Sorting Totale
0:1
110
110
170
10
400 7  17 9  17
0:05
100
140
160
10
410 8  17 12  17
0:02
500
1170
360
30 2060 14  33 19  33
Tabella 3: Comportamento dell'algoritmo al variare del parametro SRT (super ci in
Figura 4): con SRT=0.1 e SRT=0.05 trova solo una delle due curve di intersezione,
con SRT=0.02 le trova entrambe; CRT=0.02.

Il problema SSI

G. Casciola, S. Morigi

CRT

TEMPI
PUNTI
Splitting St:Point Tracing Sorting Totale
0:011
80
30
720
50
880
1141
0:010
80
40
740
60
910
1254
0:008
80
30
900
80 1090
1582
0:006
80
30
1170
60 1340
2120
0:004
80
20
1730
160 1990
3194
Tabella 4: andamento dei tempi al variare del parametro CRT (super ci in Figura3); gia con CRT=0.011 vengono trovate tutte le curve di intersezione; SRT=0.12.
ratamente la grigliatura nelle due direzioni, o evitando di diminuire troppo l'SRT
nei casi di super ci lineari.

9.2. Analisi della tolleranza CRT

E' possibile guidare la qualita delle curve di intersezione per bilanciare accuratezza
ed ecienza, sia tramite la tolleranza SRT, in uendo percio sulla approssimazione
lineare e il numero di starting point da cui partire, sia mediante la tolleranza CRT
al ne di limitare il numero di punti nella fase di tracciamento della curva. Al
diminuire di questa tolleranza si ottiene una approssimazione piu ranata dellacurva, poiche si trova un maggior numero di punti di intersezione a scapito dell'ecienza dell' algoritmo. Un metodo per ottenere buone tolleranze e calcolarle inmodo inversamente proporzionale alla massima curvatura della super cie, valore
spesso non noto. Al diminuire di questo valore le tolleranze dovrebbero decresceree viceversa. In questa implementazione si e optato per una stima di CRT che
consentisse di mantenere curve di intersezione rettilinee di al piu 100 punti. A tal
ne si e stimato il valore di CRT iniziale come 1/100 della lunghezza della diagonaledel parallelepipedo intersezione.
Il parametro SRT negli esempi che seguono e quello suggerito come stima iniziale.
Mantenendo percio l'SRT a valori appena sucienti a trovare uno starting point perogni ramo di curva, e necessario forzare il parametro CRT a valori piccoli anche
non abbandoni il tracing del ramo poiche non avrebbe piu altri punti sul ramo
stesso da cui ripartire. Ci si e chiesto quindi quanto costa il dover spingere il CRT
dal valore consigliato a valori pari ad un decimo del CRT iniziale. I valori riportati
in Tabella 4 relativi al test in Figura 3 mettono in evidenza come l'utilizzare una
tolleranza CRT piu o meno piccola, che agisce sul tempo di tracing, in uenzi iltempo complessivo proporzionalmente al numero di punti trovati. L'andamento eriportato gra camente in Figura 11.
L'utilizzo di tolleranze CRT piu spinte e talvolta motivato anche dal desiderio di ottenere un'approssimazione piu precisa ed accurata della curva. L'accuratezza, ai ni

Il problema SSI

G. Casciola, S. Morigi

2000
1800
1600
1400
1200
tempo
1000
(msec)
800
600
400
TOTALE200

TRACINGSORTING0

ST POINTSPLITTING

tolleranza CRT

Figura 11: gra co dei tempi di Tabella 4

CRT

TEMPI
Splitting St:Point Tracing Sorting Totale
0:02
740
380
870
40 2010
0:01
740
330
1390
50 2500
0:009
740
410
1430
60 2630
0:007
740
400
1710
80 2920
0:005
740
320
2140
100 3300
0:003
740
310
3540
170 4740
Tabella 5: andamento dei tempi al variare del parametro CRT (super ci in Figura8); SRT=0.01.
della modellazione solida, e ottenuta inoltre mediante il ranamento in prossimita
dei bordi del dominio parametrico per avere curve che delimitano zone chiuse.
Sebbene la convergenza quadratica del metodo sia garantita solo per super ci diclasse C (vedi Appendice), l'algoritmo e stato proposto per super ci almeno C .
L'esempio seguente, illustrato in Figura 8, mostra come, per opportune scelte dei
parametri SRT e CRT, l'algoritmo sia in grado di trattare correttamente anche
super ci che siano solo di classe G . L'esempio permette di osservare il comportamento dell'algoritmo in presenza di super ci con spigoli vivi. I risultati ottenuti(vedi Tabella 5) evidenziano come in questo caso un SRT molto piccolo (0.01) sia
condizione necessaria per trovare almeno uno starting point per ogni ramo G , poiche
il tracing fallisce in presenza di singolarita, e come sia necessario un CRT sucientemente piccolo per raggiungere gli spigoli vivi nella fase di tracing. Ovviamente lascelta di tali parametri porta ad un aumento sensibile del costo computazionale.
2

1

0

1

Il problema SSI

G. Casciola, S. Morigi

10. Conclusioni

In questo lavoro viene presentata una versione modi cata dell'algoritmo di Barnhill
ed altri [1] per l'intersezione di super ci NURBS. La particolarizzazione a tale classedi super ci ha permesso una serie di ottimizzazioni e accorgimenti che portano ad unbuon compromesso robustezza-ecienza. Sono allo studio di erenti tecniche per lafase di splitting e generazione starting point nonche una generalizzazione a super cisolo G . Un altro obiettivo futuro e la realizzazione di un sistema prototipo perla costruzione di solidi da primitive NURBS mediante operazioni booleane basato
sull'algoritmo presentato.
0

Riferimenti[1] Barnhill R.E.,Farin G.,Jordan M. e Piper B.R., (1987) Surface/surface intersection, Computer Aided Geometric Design, 4,3-16[2] Barnhill R.E. e Kersey S.N., (1990) A marching method for parametric surface/surface intersection, Computer Aided Geometric Design, 7, 257-280[3] Casale M.S., (1987) Free form solid modeling with trimmed patch, IEEE Computer Graphics and Applications, Jan., 33-43[4] Casale M.S. e Borrow J.E., (1989) A set operation algorithm for sculptured
solids modeled with trimmed patches, Computer Aided Geometric Design, 6,
235-247[5] Casciola G., (1989) Rappresentazione di oggetti a forma libera, Workshop CNRGNIM Conoscenza per Immagini[6] Casciola G. e Quaquarelli B., (1990) Primitive solide, operazioni Booleane e
NURBS, Atti del convegno ICO-GRAPHICS[7] Faux I.D. e Pratt M.J., (1979) Computational Geometry for Design and Manufacture, Ellis Horwood, Chichest U.K.
[8] Houghton E.G., Emnet R.F., Factor J.D. e Sabharwal C.L., (1985) Implementation of a divide and conquer method for intersection of parametric surface,Computer Aided Geometric Design, 2, 173-183[9] Mullenheim G., (1990) Convergence of a surface/surface intersection algorithm,
Computer Aided Geometric Design, 7, 415-423

AppendiceIl problema SSI

G. Casciola, S. Morigi

Siano f e g due super ci parametriche rispettivamente de nite dalle funzioni vettoriali:

f : D = [ua; ub]  [va; vb] ! R
1

3

g : D = [sa; sb]  [ta; tb] ! R32

di erenziabili almeno no alla derivata prima.
Siano (u ; v ) 2 D e (s ; t ) 2 D i punti iniziali del metodo, che si propone
di generare due successioni f(u ; v )g2N , f(s ; t )g2N che convergano ai punti(u; v) e (s; t) con f (u; v) = g(s; t).
Siano Jf (u; v) e Jg(s; t) le matrici Jacobiane di f e g. Dai due iterati iniziali(u ; v ) 2 D e (s ; t ) 2 D si de niscono le linearizzazioni  di f e di g mediantesviluppo di Taylor!
uu(u; v) = f (u ; v ) + Jf (u ; v ) v v
0

0

0

0

1

0

1

0

0

0

2

2

0

0

0

0

0

0

(s; t) = g(s ; t ) + Jg(s ; t ) st ts
0

con

0 @f1
BB @f@u u0;v0
Jf (u ; v ) = B
B@ @u2 u0;v0
@f3
0

0

(

)

(

)

@u (u0 ;v0 )

0

0

0

0

!

0

0 @g1
1
@f1
@v (u0 ;v0 ) C
BB @g@s (s0;t0)
CC@f2
B@ @s2 (s0;t0)@v (u0 ;v0 ) C Jg (s0; t0 ) = B
A
@f3
@g3
@v (u0 ;v0 )@s (s0 ;t0 )1@g1@t (s0 ;t0 ) CC@g2CA@t (s0 ;t0 ) C@g3@t (s0 ;t0 )Si noti che i vettori sono vettori colonna.
Le linearizzazioni  e descrivono rispettivamente il piano tangente alla super cie
f in (u ; v ) e alla super cie g in (s ; t ).
Nelle ipotesi di continuita del piano tangente la matrice Jacobiana non ha rango
de ciente in quanto il piano tangente e generato dalle sue colonne.
Per ogni coppia di punti (u; v) 2 D e (s; t) 2 D si possono de nire le normali alle
super ci
df (u; v)  df (u; v)n1(u; v) = du
dv
0

0

0

1

0

2

n2 (s; t) = ddsg (s; t)  ddtg (s; t)

Il problema SSI

G. Casciola, S. Morigi

Se entrambi i vettori n1(u ; v ) e n2(s ; t ) sono non nulli e non paralleli allora esiste
una retta di intersezione fra i piani  e . Questa retta viene a sua volta intersecata
da un terzo piano non parallelo per de nire univocamente un nuovo punto 3D P .
In Barnhill ed altri [1] l'iterato successivo viene preso come il punto medio delle
proiezioni dell'iterato precedente sulla retta di intersezione dei due piani tangenti.
Se de niamo n3 = n1  n2 la normale al terzo piano, l'iterato P usato in [1] puoessere valutato da
0 n  f (u ; v ) 1
0 T1
n
1
1
B
B@ n2T C(3)
A P = @ n2  g(s ; t ) CA
0

0

0

0

1

1

1

n3T

n3 

0

0

0

0

f (u0 ;v0 )+g(s0 ;t0)2

Un metodo diretto per ottenere l'intersezione di tre piani e suggerito da Faux e Prattin [7]. Date le tre normali, e de nendo gli elementi del lato destro di (3) come b ,b e b il nuovo punto e
P = b (n2  n3 ) +nb ( n(n3 nn1 ) )+ b (n1  n2 )1
2
3
In Figura 1 e illustrato questo primo passo del metodo.
Per iterare si determinano le preimmagini di P sui domini parametrici risolvendo isistemi:!
!
su(s ; t ) t = P
(u ; v ) v = P
Poiche questi sistemi sono ridondanti possono essere estratti tre sottosistemi 2  2
da ogni sistema e, per quanto detto, almeno uno non sara singolare.
Se (u ; v ) 2 D e (s ; t ) 2 D si puo ripetere il procedimento utilizzando la nuova
coppia di iterati (u ; v ) e (s ; t ).
Sotto determinate ipotesi le successioni ottenute dal metodo convergono e, inoltre,in [9] e stato dimostrato che se le super ci sono C la convergenza e quadratica.
Trovato un punto f (u; v) = g(s; t) sulla curva di intersezione ci si muove lungo
la stessa iterando il metodo con un nuovo iterato iniziale. Si ottiene in questo modo
una successione di punti della curva di intersezione.
Dato un iterato iniziale per trovare un punto di intersezione fra le due super ci sipuo ssare una variabile (diciamo u) dell'equazione
1

2

3

1

1

2

3

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

2

1

1

2

f (u; v) g(s; t) = 0(4)ottenendo e potendo applicare uno schema iterativo di Newton-Raphson al sistema
3  3. Questo metodo e molto meno costoso, ma non e utile per procedere lungo
la curva. Barnhill ed altri [1] suggeriscono questa procedura per calcolare il primo
punto (starting point) della curva di intersezione e nella nostra implementazione

Il problema SSI

G. Casciola, S. Morigi

viene usata anche per determinare i punti delle curve di intersezione sui bordi dei
domini parametrici.
Un'altra possibilita de nita passo costretto, di erisce dal metodo visto nell' impostazione del sistema (4). Viene infatti aggiunta una quarta equazione che de nisce
il cosiddetto passo costretto e rende determinato il sistema:(f (u ; v ) + cE f (ui; vi))E = 0
0

0

dove
f (u ; v ) e il punto corrente sulla curva di intersezione;
E e il versore tangente alla curva di intersezione in f (u ; v ) ;c e la distanza del piano di avanzamento dal punto corrente (proporzionale a CRT);
f (u ; v ) + cE e l'iterato iniziale.
Il signi cato della quarta equazione e quello di ssare la lunghezza del passo lungo
la curva di intersezione. Geometricamente si richiede che il nuovo punto generato
dall'algoritmo non solo appartenga alla curva di intersezione, ma giaccia anche su
di un piano, chiamato piano di avanzamento, distante c dal punto corrente e perpendicolare al vettore tangente alla curva di intersezione in tale punto.
0

0

0

0

0

0