Si mp lifi ca tio n a nd R efi ne me nt
Pa olo C ig no ni p. ci gn on i@ ist i.cn r.it htt p:/ /vcg .ist i.cn r.it /~ci gn on i
2
A pp ro xim ati ng s ur fa ce s w ith tri an gle me sh es
M an ag in g th e q u an tit y o f g eo m et ry v s t h e q u ali ty o f th e r ep re se n ta ti o n
A ss u m p ti o n s:
Su rf ace s re pre se nte d b y tri an gle me sh es
Accu ra cy of th e a pp ro xi ma tio n i s pro po rt io na l to th e n umb er of tri an gle s
C omp le xi ty of a su rf ace is pro po rt io na l to th e n umb er of tri an gle s
O b je cti ve :
Al w ays pro du ce th e si mp le st me sh th at sa tisf ie s th e a ccu ra cy re qu ire d by th e a pp lica tio n
3
R ed uci ng re nd eri ng co st
Si mp lifyi ng is no t th e o nly w ay to re du ce th e n ee de d n umb er of tri an gle s At re nd eri ng time w e ca n d o: V ie w F ru stu m C u llin g D ra w in g o nly w ha t is in th e vi ew fru st um …
viewfrustum
culling OFFculling ON
4
R ed uci ng C omp le xi ty
… O cc lu sio n /V is ib ility c u llin g D ra w in g o nly w ha t it is pro ba bly vi si ble
è Im p ro ve p er fo rm an ce s, b u t n o t su ffi cie n t fo r v er y l ar g e d ata se ts
Si mp lifi ca tio n
F ro m a co mp uta tio na l Po in t o f vi ew , fi xe d t he si ze of th e so lu tio n f in d t he b es t re pre se nta tio n T he o pti ma l so lu tio n i n i ts ge ne ra l fo rm is N P H ard H eu rist ics w orks w ell (e ve n w ith b ou nd s)
Me tri cs
C omp uti ng th e “d iffe re nce ” be tw ee n t w o me sh es G eo me tri c w ay H au sd orf f Pe rce ptu al W orki ng in Ima ge sp ace Ma ny re nd eri ng s, co mp uti ng th e d iffe re nce , po ssi bly in a h uma n-l ike w ay
7
Ap pe ara nce si mi la rity
D iffe re nce b etw ee n t w o i ma ge s: (t rivi al)
D iffe re nce b etw ee n t w o o bje ct s: In te gra te th e a bo ve o ve r all p ossi ble vi ew s
I
1D I
1,I
2= 1 n
2∑
x∑
yd I
1x ,y , I
2x ,y
8
Ap pro xi ma tio n e rro r
Q ua nti fie s th e n oti on o f “si mi la rity” Tw o ki nd s of si mi la rity: G eo m etr ic s im ila rity (su rf ace d evi ati on ) A p p ea ra n ce s im ila rity (ma te ria l, n orma l… )
G eo me tri c si mi la rity Tw o ma in co mp on en ts: D ist an ce fu nct io n F un ct io n N orm: L
2: a ve ra ge d evi ati on L
inf: ma xi mu m de vi ati on - H au sd orf f d ist an ce
H au sd orf f D ist an ce
Symmetric version:
D
HS
1,S
2= m ax
x∈S1min
y∈S2D x ,y
S
1S
2D S
1,S
2= m ax {D
HS
1,S
2, D
HS
2,S
1}
C omp uti ng H au sd orf D ist an ce In a a pp ro xi ma te w ay Sa mp le a su rf ace Po in ts un ifo rml y dist rib ute d o ve r it F or ea ch p oin t x co mp ute
po in ts usu all y ve ry ne ar to su rf ace , U G w orks w ell , b ett er th an tre es A vg a re u se fu l to o.. . min
y∈S2D x ,y
12
Si mp lifi ca tio n Al go rith ms
Simplification approaches:incremental methods based on local updates mesh decimation [Schroeder et al. `92, ... + others]energy function optimization & progressive meshes [Hoppe et al. `93, Hoppe ‘96, Hoppe ‘97]quadric error metrics [Garland et al. ’97]coplanar facets merging [Hinker et al. `93, Kalvin et al. `96]clustering [Rossignac et al. `93, ... + others]wavelet-based [Eck et al. `95, + others]
volume-based [He+ 95, He+ 96, Andujar+ 02]
13
In cr em en ta l m eth od s ba se d on lo ca l u p d ate s
A ll o f th e m eth o d s s u ch th at : sim pli fic ati on p ro ce ed s as a s eq ue nc e o f s m all ch an ge s of th e me sh (i n a g re ed y w ay) ea ch u pd ate re du ce s m es h s iz e a nd [~ m on oto nic all y] de cr ea se s th e a pp ro xim ati on pre ci si on
D iffe re n t ap p ro ac h es :
mesh decimationenergy function optimizationprogressive meshesquadric error metrics14 … Incremental methods based on local updates ...
L o ca l u p d ate a cti o n s:
ve rt ex re mo va l ed ge co lla pse pre se rve lo ca tio n ne w lo ca tio n
tri an gle co lla pse pre se rve lo ca tio n ne w lo ca tio n
remove vertexremove face No. Faces
n-2
n-2
n-4
In cre me nta l Si mp Me th od
T he co mmo n g re ed y fra me w ork:
While me sh si ze /p re ci si on is sa tisf act ory
select from a priority queue the best element to simplify
Perform simplification modifying the mesh
update priority queue according to the mods;
EG99 Tutorial16
Q ua dri c Erro r Me tri cs
Simplification using Quadric Error Metr ic s
[Garland et al. Sig’97]Based on incremental edge-collapsing
but can also collapse vertex couples which are not connected(topology is not preserved)
17
Erro r H eu rist ics Q ua dri c Erro r fo r Su rf ace s
Let n
Tv + d =0 b e t he e qu ati on re pre se nti ng a plane T he sq ua re d d ist an ce o f a p oin t x fr om th e p la ne is D (x ) = x( nn
T)x + 2d n
Tx + d
2T his dist an ce ca n b e re pre se nte d a s a q ua dri c Q = (A, b ,c ) = (nn
T,d n ,d
2) Q (x )= xA x + 2b
Tx + c
Q ua dri c
T he e rro r is est ima te d b y pro vi din g f or ea ch ve rt ex v a q ua dri c Q
Vre pr es en tin g t he s um of th e a ll t he sq ua re d d ist an ce s fro m th e f ace s in ci de nt in v T he e rro r of co lla psi ng a n e dg e e =(v ,w ) ca n b e eva lu ate d a s Q
W(v).
Af te r th e co lla pse th e q ua dri c of v is up da te d a s follow Q
V= Q
V+ Q
W19
T op olo gy Pre se rva tio n 2-Ma nif old A su rf ace Σ in R
2su ch th at an y po in t o n Σ h as an op en n eig hb or ho od h om eo m or ph ic to a n o pe n d is c or to h alf a n o pe n d isc in R
2A ed ge c oll ap se c an c re ate n on m an ifo ld si tu ati on s
20
To po lo gy Pre se rva tio n
Let Σ b e a 2 si mp lici al co mp le x w ith o u t b o u n d ar y Σ ’ is ob ta in ed b y co lla psi ng th e e dg e e = (ab ) Let Lk ( σ ) be th e se t o f a ll t he fa ce s of th e co -f ace s of σ d isj oin t fro m σ
a
abΣ and Σ ’ a re h ome omo rp hic if f Lk ( a) ∩ Lk ( b) = Lk ( ab )
[Dey 99]21
To po lo gy Pre se rva tio n
Lk (a ) ∩ Lk (b )= {x ,y }= Lk (ab )
Lk (a ) ∩ Lk (b ) ={ x, y,z, zx } { y, z} = Lk (ab ) a
y x
b
a z
y x
b
22
To po lo gy Pre se rva tio n
M es h w ith b ou nd ar y ca n b e m an ag ed b y co ns id er in g a du mmy ve rt ex v
da nd , fo r ea ch b ou nd ary ed ge e a du mmy tri an gle co nn ect in g e with v
dT hin k it w ra pp ed o n t he s ur fa ce of a sp he re
23
La zy he ap
Si su pp on e d i a ve re u no h ea p co n t utt e l e op era zi on i Est ra gg o d a h ea p e a gg io rn o l a me sh tali operazioni invalidano/modificano la mesh e qu in di le p rio rità /va lid ità d i p art e d ell e a zi on i g ià pre se nti n ell o H ea p
La zy H ea p
D ue So lu zi on i Lin k es pli cit i e le m en ti m es h- > he ap e ag gio rn ame nto d ell o st esso La zy up da te Si me tto no n ell o h ea p t utt e l e n uo ve o pe ra zi on i co n l a n uo va p rio rità Q ua nd o si e st ra e u n'o p d all h ea p si co ntro lla ch e si a se mp re va lid a D i ta nto in ta nto g arb ag e co lle ct io n su llo h ea p
V ali dit à co lla sso
Dati O gn i ve rt ice h a u na ma rca te mp ora le : qu an do e ' st ato mo dif ica to l'u ltima vo lta O gn i co lla sso (co pp ia d i ve rt ici ) ha u na ma rca te mp ora le qu an do è st ato in se rito n ell o h ea p U n co lla sso è va lid o se I d ue ve rt ici n on so no st ati ca nce lla ti Il co lla sso e ' st ato me sso n ell o h ea p p iu recentemente della data di ultima modifica dei ve rt ici
28
Si mp lifi ca tio n Al go rith ms
N ot-i ncre me nta l me th od s:
co pla na r fa ce ts me rg in g [H in ke r et al. `9 3, Ka lvi n e t a l. `9 6]
re -t ilin g [T urk `9 2]
cl ust eri ng [R ossi gn ac et al. `9 3, ... + oth ers]
w ave le t-b ase d [Eck et al. `9 5]
vo lu me -b ase d [H e+ 95 , H e+ 96 , An du ja r+ 02]
29
C lu st eri ng
Vertex Clustering [Rossignac, Borrel `93]
de te ct a nd u nif y clu ste rs o f n ea rb y ve rt ice s (d iscre te g rid din g a nd co ord in ate s tru nca tio n) all fa ce s w ith tw o o r th re e ve rt ice s in a cl ust er are re mo ve d do es no t p re se rve to po lo gy (f ace s ma y de ge ne ra te to e dg es, g en us ma y ch an ge ) ap pro xi ma tio n d ep en ds on g rid re so lu tio n
(figure by Rossignac)
30
C lu st eri ng -- Exa mp le s
Si mp lifi ca tio n o f a ta ble la mp ,
IBM 3DInteraction Accelerator10,108 fac et s 1,383 fac et s 474 fac et s 46 fac et s
31
... C lu st eri ng ...
C lu ste rin g - Ev alu ati o n hig h e ffici en cy ve ry si mp le imp le me nta tio n lo w q ua lity ap pro xi ma tio ns do es no t p re se rve to po lo gy erro r is bo un de d b y th e g rid ce ll si ze
R EF IN EMEN T or Su bd ivi si on Su rf ace s
EG99 Tutorial33
Su bd ivi si on Su rf ace s
S ub div is io n d efi ne s a s m oo th c ur ve o r su rf ace a s th e l imi t o f a se qu en ce o f su cce ssi ve re fin eme nts. Si p art e d a u na me sh p oli go na le Si su dd ivi de i p oli go ni ch e l a co mp on go no Smo oth d ell a su pe rf ici e mu ove nd o i ve rt ici
In e ffe tti qu ell o ch e si ve de so no se mp re ap pro x de lle ve re su bd iv su rf ace s
EG99 Tutorial34
EG99 Tutorial35
Ese mp io
G eri 's G ame (1 99 7) Primo esempio non accademico di uso di su bd ivi si on su rf ace s
EG99 Tutorial36
Smo oth ne ss
N on so lo su pe rf ici smo oth V ari ab le sh arp ne ss cre ase s
EG99 Tutorial37
Su bd ivi si on C la ssi fica tio n
EG99 Tutorial38
Su bd ivi si on C la ssi fica tio n
EG99 Tutorial39
Su bd ivi si on
EG99 Tutorial40
D oo Sa bin
Pe r me sh p oli go na li Duale ad ogni vertice corrisponde una nuova fa cci a
EG99 Tutorial41
D oo Sa bin
EG99 Tutorial42
Lo op R efi ne me nt Sch eme
F un zi on a p er me sh tri an go la ri V ert ex in se rt io n O gn i e dg e è d ivi so in d ue e i n uo vi ve rt ici so no rico nn essi p er fo rma re n uo vi tri an go li
EG99 Tutorial43
Lo op Su bd ivi so n
Ap pro ssi ma nte (n on in te rp ola nte ) Continua C 1 su ve rt ici st ra ord in ari (va le nza !=6 ) C 2 e lse w he re
EG99 Tutorial44
Lo op Su bd ivi si on
EG99 Tutorial45
Lo op Su bd ivi si on La sce lta d i B no n è u nica
= 1 k 5/ 8− 3 8 1 4 cos 2 k
2
EG99 Tutorial46
Lo op Bo rd er
EG99 Tutorial47
Bu tte rf ly
In te rp ola nte (n on a pp ro ssi ma nte ) Continua C 0 su ve rt ici st ra ord in ari (va le nza <4 e >7 ) C 1 e lse w he re
EG99 Tutorial48
Bu tte rf ly
EG99 Tutorial49
