Modellare1

Daniele Marini

Sintesi e analisi

Dalla forma geometrica all’immagine

dall’immagine alla forma geometrica

Problema direttoe

problema inverso

Quale schema di rappresentazione

• per il rendering di forme statiche?• per il rendering di forme animate o dinamiche?• oggetti rigidi o flessibili o malleabili?• forme per la codifica?• Quali tipi di forma: semplici e geometriche o complesse come una testa?

NON ESISTE LO SCHEMA UNICO UNIVERSALE

Modello

Descrive il metodo o lo schema di rappresentazioneutilizzato nella sintesi di immagini. I principali:

• mesh o griglia poligonale• poliedri• patch parametriche (bicubiche ..)• CSG (geometria solida costruttiva)• suddivisione spaziale (voxel)• implicite: x2 + y2 + z2 = r2

Oggetto di studio del CAD

Elementi base

Quadrilatero (o triangolo)

Patch parametrica

CSG

voxel quadrica

Poliedri

Vertici, spigoli, facce, oggetti

Semplice, a volte costoso, problemi di precisione eaccuratezza, dipende dalla curvatura, può essereautomatizzato (tastatori 3d, luce strutturata, o con algoritmi - es. sweep -trascinamento)

Con sistemi automatici si generano molti triangoli: problema della decimazione dei triangoli

Importanza della struttura dati:struttura di un disegno piano

Struttura di una scena

Procedimenti costruttivi:estrusione e rotazione

Rotazione

Funzioni di Bernstein blending functions

€

Cx (t0) = P0xB0(t0) + P1xB1(t0) + P2xB2(t0) + P3xB3(t0)

Costruire una curva di Bezier

Vincoli di continuita’ agli estremi del poligono

Superfici parametriche:Bezier

Patch bicubiche parametriche

P(u,v) = i j Ci,j Bi(u)Bj(v)

Ci,j sono 16 punti di controllo

u, v sono parametri reali in (0,1)

P è un polinomio bi cubico

Valutare la superficie parametrica

• Valutazione diretta• Algoritmi progressivi: De Casteljou -

interpolazione lineare progressiva, es: parabola

€

b01(t) = (1− t)bo + tb1

b11(t) = (1− t)b1 + tb2

b02(t) = (1− t)b0

1(t) + tb11(t) = (1− t)2bo + 2t(1− t)b1 + t 2b2

b0

b1

b2

b01

b11

b02

NURBS• Non Uniform Rational B Splines: si considerano i

pesi wi

• se i pesi sono tutti =1 si hanno le curve di Bezier

€

P( t) = CiBi(t)i =0

3

∑

€

P( t) =w0C0B0(t)+ w1C1B1( t)+ w2C2B2(t)+ w3C3B3( t)

w0B0(t)+ w1B1( t)+ w2B2(t)+ w3B3( t)=

wiCiBi(t)i =0

3

∑

wiBi(t)i =0

3

∑

Curve parametriche per interpolazione

• Spline cubiche

• Funzioni di Hermite:

€

P( t) = C0 C1 C2 C3[ ]

1 −3 3 −1

0 3 −6 3

0 0 3 −3

0 0 0 1

⎡

⎣

⎢ ⎢ ⎢ ⎢

⎤

⎦

⎥ ⎥ ⎥ ⎥

t0 = 1

t1

t2

t3

⎡

⎣

⎢ ⎢ ⎢ ⎢

⎤

⎦

⎥ ⎥ ⎥ ⎥

Mesh con curve parametriche

Lofting

• Data una curva parametrica bicubica, con c0, c1, c2, c3 punti di controllo:

P(u) = c0 u3 + c1 u2 + c2 u + c3

• Essa rappresenti la sezione trasversale di una forma da trascinare per costruire un poliedro, generando altre sezioni trasversali a intervalli determinati. • Lungo la sezione vanno individuati i vertici che verranno collegati da un profilo all’altro per creare un poliedro.• E’ necessario definire un sistema di riferimento chiamato “frame” per definire l’orientamento di ogni faccia del poliedro.

Costruzione per trascinamento lungo curve parametriche

Occorre anche definire come suddividere in intervallila sezione: • la divisione di u in intervalli uguali può produrrequadrangoli non uniformi, • si sceglie la parametrizzazione rispetto alla lunghezza degli archi: se la curvatura è elevatasi avranno più poliedri rispetto a tratti con curvatura bassa.

Per definire il “frame” - frame di Frenet:

l’origine è un punto campione P , si definiscono 3 vettoriT, N, B con T vettore unitario tangente alla curva in P:

T = V / |V| e V =3au2+ 2bu + c derivata della curva

N = K/ |K| dove K = V x A x V/ |V| e A derivata secondadella curva (A = 6au + 2b)

B = T x N

Oggetti complessi composti da molte patch si creanocon tecniche di interpolazione di punti campione,imponendo continuità tra le varie “patch”.

La continuità imitata al primo ordine garantiscel’assenza di “buchi”, ma dà luogo a superfici con“spigoli” indesiderati. Si impongono continuitàdella derivata prima e secondo.

Decimazione dei triangoli

• Perche’ triangoli

• Come decimare? – Ridurre i triangoli in

regioni “piatte”– Preservare l’aspetto

• Stimare la curvatura:

€

Δf

Δu,Δf

Δv

Metodo di Schroeder• Determinare gli spigoli “rilevanti per

l’aspetto”: vanno tenuti• Classificare i vertici:

1. Punti interni generici2. Punti comuni a triangoli con T connessione3. Punti del contorno4. Punti di uno spigolo rilevante per l’aspetto5. Punti comunia 3 o piu’ spigoli rilevanti per

l’aspetto (punti vertice)

Punti interni genericiSi possono eliminare se il gradiente e’ inferiore a una soglia

Punti comuni a triangoli con T connessioneNon si possono eliminare

Punti del contornoSi possono eliminare se la distanza dalla retta congiungente I vertici

adiacenti e’ inferiore a una sogliaPunti di uno spigolo rilevante per l’aspetto

Si possono eliminare se la distanza dalla retta congiungente I vertici adiacenti e’ inferiore a una soglia

Punti comunia 3 o piu’ spigoli rilevanti per l’aspetto (punti vertice)

Non si possono eliminare

Triangolazione

• Triangolazione di Delaunay e diagrammi di Voronoi

Partizione del piano in

celle t.c. tutti i punti di

una cella sono piu’

vicini al vertice

generatore della cella

di ogni altro punto

Algoritmo di Sibson

• Data una coppia di tirangoli adiacenti, si esamina e si scambiano se un vertice e’ interno al cerchio circoscritto:

Un esempio

Solidi primitivi

CSG

Albero CSG

Esempio CSG

La modellazione solida richiede specificheinformazioni per individuare sottospazi e per determinare se un punto appartiene a un semispazio.

In ogni caso si tratta di definire semispazi e applicareoperazioni insiemistiche per aggregare semispazi.

Un semispazio algebrico è definito come:

( ){ }H x y z p x y z= ≤, , | ( , , ) 0

e p(x,y,z) è un polinomio reale con coefficienti reali

Schemi di rappresentazione per la modellazione solida:

• CSG• Boundary representation (Brep)• suddivisione spaziale• superfici mediali

ciascuno schema deve permettere di risolvere il problemadell’appartenenza di un punto al semispazio individuatodal solido

Con lo schema CSG si possono ottenere forme assaicomplesse applicando tecniche di “sweep”

Nello schema Brep un solido è rappresentato da unasuperficie delimitata da facce spigoli e vertici. Glielementi di una rappresentazione Brep possonointersecarsi solo lungo spigoli o vertici descrittinella struttura. Operatori booleani possono essereapplicati anche a uno schema Brep.

Gli schemi Brep si dividono in due grandi classi:

manifold Brepnon manifold Brep

manifold (varietà lineari) ammettono spigoli comunia due sole facce e vertici comuni a più spigoli raccolti in un conoide

non manifold ammettono un numero pari qualsiasidi facce comuni a uno spigolo, si distingue internoed esterno

Formula di Eulerosenza buchi

V - E + F = 2

• V = vertici

• E = lati

• F = facce

Schemi a suddivisione spaziale sono:

• mesh - conformi al contorno• BSP tree - non conformi al contorno

Mesh possono essere organizzate in tetraedri,esaedri o altri poliedri - usate nel calcolo adelementi finiti.

Binary Space Partition Trees sono suddivisioniricorsive dello spazio 3D in regioni disgiunte,la radice denota un piano separatore - un esempioè octree

Si possono anche usare griglie rettilinee deformabiliche si conformano al contorno, altrimenti il contornoè approssimato

Rappresentazione a superfici mediali: generalizzanoassi mediali per descrizione di superfici, sono pocoutilizzate:

Formalmente è definito come la chiusura del luogo dei centri di dischi inscritti nel dominio o del luogo dei centri delle sfere massimali inscritte nel dominio. Variando il raggio delle sfere si ottengono dilatazioni dei solidi.

La conversione tra schemi di rappresentazione non è semplice:da CSG a Brep è ben compresa e facile;da Brep a CSG ci sono punti oscuri in particolare perconformare la rappresentazione al contorno;nel caso dei poliedri la conversione Brep -> CSG è analoga alla conversione Brep -> BSP tree.

Ogni sistema di modellazione deve risolvere i problemi:

• intersezione tra superfici• offset di una superficie (luogo di punti a distanza costante da una superficie• blending - superficie smooth tra due superfici• deformazioni locali o globali

Approcci emergenti sono:

Feature based designConstraint based design

Feature based consiste nel definire elementi di forma aventiun significato specifico (slitte, fori, tasche, …)

Modellazione a vincoli significa imporre vincoli numericio geometrici (anche fisici o strutturali) a un modello.La valutazione dei vincoli è assai complessa: il problemapuò essere sovradeterminato (troppi vincoli), sottodeterminato(troppo pochi); in generale si esprimono con sistemi di equazioni.

Suddivisione spaziale

Voxel

Meta balls o soft balls

• simulare forme naturali, soffici, prive di bordi

• rappresentare forme costruite con la creta

• meta balls: simili a gocce d’acqua, quando si avvicinano si uniscono; si possono descrivere con funzioni di potenziale

Ad esempio si immagini di avvolgere con un

drappo una scena fatta di forme geometriche

Esempi di fusione

Modellazione con soft balls

una sfera

soffice cui è

stato sottratto

un cubo

soffice

Primitive soft

• Derivano da superfici equipotenziali, ovvero campi scalari descritti da una funzione f(x,y) dipendente da una distanza d.

• La funzione f(x,y) è implicita!– es: circonferenza:

• forma esplicita parametrica: x(t)=r*cos(t); y(t)=r*sin(t)

• forma implicita: f(x,y)=r*r=x*x+y*y=x2+y2

• risolvere per funzioni implicite è complesso

Primitive soft (cont)

• La forma implicita identifica un lugo di punti, a noi interessa trovare tutti i punti che soddisfano l’equazione, dobbiamo valutarla per prove ed errori

Primitive soft (cont)

• Se abbiamo due o più equazioni implicite possima sommarle, dovremo valutare il campo risultante: in ogni punto dello spazio il campo è il risultato del contributo dei due (o più) campi descritti da ogni singola funzione

Primitive soft (cont) dobbiamo avere:

• una funzione generatrice di un campo, in ogni punto P il campo è funzione della distanza d(P) da un punto dato (es. campo termico, campo di intensità di illuminazione, ...) • una funzione che descrive il “potenziale del campo” f(d(P)). Dà il valore del campo in ogni punto (funzione di un vettore ad argomenti scalari, es: f(P) = (1-d2/R2)2 con d<= R (distanza)• se abbiamo più generatori del campo dobbiamo miscelarne il contributo per valutare il campo di potenziale totale• il campo risultante si rappresenta visualizzando superfici equipotenziali, o iso superfici. Si usa molto marching cubes

La modellazione con funzioni implicite e isosuperfici si presta alla animazione di forme e alla soluzione efficiente della ricerca di collisioni

Esempi di MetaBalls