A Topological Compa ison o Su ace
Ex ac ion Algo i hms
C. And´uja , P. B une , M. Fai ´en, I. Na azo, A. Vinacua
Modeling, Visualiza ion, In e ac ion and Vi ual Reali y G oup
So wa e Depa men
Uni e si a Poli `ecnica de Ca alunya, Ba celona, Spain.
{anduja , pe e, m ai en, isabel, al a }@lsi.upc.edu 1
Abs ac
In many applica ion a eas, i is use ul o con e he disc e e in o ma ion s o ed in
he nodes o a egula g id in o a con inuous bounda y model. Isosu ace ex ac ion
algo i hms di e on how he disc e e in o ma ion in he g id is gene a ed, on wha
in o ma ion does he g id s o e and on he p ope ies o he ou pu su ace. Recen
algo i hms o e di e en solu ions o he disambigua ion p oblem and o con ol-
ling he inal opology. Based on a numbe o p ope ies o he g id’s g ey cells and
o he econs uc ion algo i hms, a cha ac e iza ion o se e al su ace ex ac ion
s a egies is p oposed. The classi ica ion p esen ed shows he inhe en limi a ions
o he di e en algo i hms conce ning global opology con ol and econs uc ion
o local ea u es like hin po ions o he olume and almos non-mani old egions.
These limi a ions can be obse ed and a e illus a ed wi h some p ac ical examples.
We e iew in ligh o his classi ica ion some o he ele an pape s in he li e a u e,
and see ha hey clus e in some a eas o he p oposed hie a chy, making a case o
whe e i migh be mo e in e es ing o ocus in u u e esea ch.
Key wo ds: Su ace ex ac ion, Ma ching Cubes algo i hm, opologically
consis en isosu aces, ec angula g ids, disc e e olume models, opology
op imiza ion.
1 In oduc ion
In many applica ions olumes a e ep esen ed by a disc e e olume model,
some imes because ha is he way in which da a ha e been ga he ed (medical
1Wo k pa ially suppo ed by he TIN2004-08065-C02-01 o he spanish go e n-
men (MEC) and FEDER unding.
P ep in submi ed o Else ie Science 5 Decembe 2005
applica ions, nume ical simula ion esul s), some imes as an in e media e ep-
esen a ion o help in achie ing some objec i e (model epa a ion, cha ac e
sculp ing, simpli ica ion). In his con ex , i is o en necessa y o eco e om
his olume in o ma ion a su ace ep esen ing he bounda y o (a po ion
o ) he olume. I is his su ace-ex ac ion p oblem ha we ocus on in his
pape .
When he olume model is buil om a solid model, i may con ain bina y
in o ma ion (an in-ou classi ica ion o e e y e ex in a g id), o i may con-
sis o a sampling o a scala ield (a he same e ices), o example a signed
dis ance ield. Mo e in o ma ion can be s o ed, like He mi e da a, exac in e -
sec ion poin s, o he ac ha he olume en e s ( h ough a ace, o example)
in o a cell, bu hese a e seldom e ec i ely used in he li e a u e o eco e
he bounda y o he olume.
The ex ac ed su ace is gene ally modeled wi h a iangle mesh M. The clas-
sical algo i hm o achie e his — he o iginal Ma ching Cubes— da es back o
[1]. This o iginal algo i hm was soon seen o p esen inconsis encies in some
con igu a ions (see [2]), and much o he wo k done on his algo i hm he e-
a e has cen e ed on a oiding such inconsis encies. Di e en solu ions o his
p oblem, howe e , na u ally yield di e en opologies o he esul ing su ace.
These di e ences a ise in a eas whe e a dimension o he olume is compa able
o he scale o he disc e iza ion, ei he hin shee s o olume o hin ubula
po ions.
In his pape we p opose a way o classi y hese algo i hms depending on he
na u e o he cells hey examine, and some p ope ies o he su aces hey
p oduce. We e iew in ligh o his classi ica ion some o he ele an pape s
in he li e a u e, and see ha hey clus e in some a eas o he p oposed
hie a chy, making a case o whe e i migh be mo e in e es ing o ocus in
u u e esea ch.
To his end, we will s a by e iewing some o he ele an p e ious wo k in
sec ion 2, o help mo i a e he de ini ions on which we base ou classi ica ion,
in oduced in sec ion 3. In sec ion 4 we discuss b ie ly how di e en algo i hms
beha e ega ding he opology o he esul ing su ace, and hen show in sec-
ion 5 how di e en algo i hms beha e in econs uc ing some sui ably chosen
es models, in acco dance wi h he discussion in he p e ious sec ions.
2 Su ace ex ac ion algo i hms
Su ace ex ac ion algo i hms di e on how he g id in o ma ion is ob ained,
on how i is ep esen ed in he disc e e model, and on how he su ace is econ-
2
s uc ed. Mos algo i hms a e only using in o ma ion on g id e ices. Bu e -
ex alues can be ob ained by a simple sampling o he o iginal model/ ield [3]
o by analyzing he solid olume in he e ex neighbo hood [4,5].
Mul iple a ia ions o he o iginal Ma ching Cubes algo i hm [1] gi e di e -
en solu ions o he su ace ex ac ion p oblem. Howe e , mos echniques a e
based on local c i e ia and canno o e a di ec con ol o opological p ope -
ies o he ex ac ed mesh. As i s no ed by Du s [2], he o iginal Ma ching
Cubes algo i hm [1] may p oduce su aces wi h holes due o opologically
inconsis en decisions on he econs uc ion o ambiguous aces, whe e inde-
penden local decisions in he wo adjacen cubes may lead o wo di e en
su ace econs uc ions in hei common ace.
Disambigua ion echniques epo ed so a ha e ocused on wo majo con-
ce ns: opological consis ency, i.e. p oducing closed su aces by p ope cube
polygonaliza ion, and opological co ec ness, i.e. ex ac ing a su ace ai h ul
o he geome y o he eal su ace.
Inconsis ency o ambiguous aces (see igu e 1) appea s when adjacen cubes
ha sha e such a ace ake di e en local decisions (cases c and d in Figu e 1)
on he econs uc ion o he su ace wi hin he ambiguous ace. Consis ency
can be sol ed by jus conside ing he inside/ou side node classi ica ion, e-
ga dless o he ac ual da a alues. A i s solu ion o he consis ency p oblem
was gi en by p e e ed pola i y me hods. These algo i hms decide how o slash
ambiguous aces o a cell using a uni o m c i e ion: always join black nodes
o always join whi e nodes. This decision can be implemen ed ei he algo i h-
mically [6] o by using a lookup able [7]. All hese echniques a e gene ally
simple o implemen al hough hey gene a e a bi a y opologies.
   
Fig. 1. Unambiguous aces (a, b) gene a ing a single edge o he iangula mesh
and he wo possible choices o edges in an ambiguous ace (c, d).
Techniques add essing he opological co ec ness p oblem in e he p ope
polygonaliza ion o an ambiguous cube by analyzing i s ac ual da a alues.
These me hods a e equi ed o p o ide di e en polygonaliza ion schemes o
each ambiguous cube, [8,9]. Ini ial me hods only a emp ed o ensu e he
co ec ness o he e u ned su ace on he bounda y o ambiguous aces. The
analysis was based on ace cen e esampling [10,11], bilinea in e pola ion [12]
o g adien disambigua ion [13].
3
Ini ial disambigua ion echniques [14,12] we e ying only o disambigua e
wi hin g id aces. Nielson and Hamann [12] p oposed a s a egy based on he
saddle poin alue o he bilinea in e polan o dic a e he edge connec ions on
an ambiguous ace: he connec ion is made so as o sepa a e he saddle poin
om e ices o opposi e sign. This gi es a solu ion which is opologically co -
ec in e ms o he bilinea in e polan on he ace. In a simila way, Pasko e
al. [14] we e also aking he disambigua ion decision om he posi ion o he
cen e o he hype bolic ace o he ilinea in e polan on he ambiguous
ace. Mon ani e al. [15] used a simple-en y lookup able o sol ing he con-
sis ency p oblem, including an ex a con igu a ion o he complemen a y case
in se e al con igu a ions (3, 6, 7) o he classical Ma ching Cubes algo i hm.
This lookup able was also used in [16] o g ids wi h boolean in o ma ion. In
his case, e ices a he middle o he g id edges we e conside ed and a inal
ace me ging pos -p ocess was p oposed o educing he ace complexi y o
he ou pu model.
Te ahed a decomposi ion echniques [3,17] spli each cube in o i e o six
e ahed a, which always exhibi an unambiguous polygonaliza ion. Gueziec
e al. [18] di ide each cubic cell in o i e e ahed a. The i s ou e ahed a
a e cen e ed on ou al e na ing e ices o he cell and spli hei neighbo
aces h ough hei diagonal. The las e ahed on ills he cen al hole in
he cubic cell. Consis ency h ough g id aces is ensu ed by using al e na ing
subdi isions: he subdi ision in a pa icula cell is always symme ical o he
subdi ision in any o i s neighbo cells. The esul ing opology is o ced by
his al e na ing subdi ision and depends on he subdi ision choice a he i s
cell o he g id. Pascucci [19] p oposes an algo i hm o isosu acing a scala
ield de ined in a e ahed al g id. His implemen a ion is howe e es ic ed o
he case o egula g ids (no necessa ily ec ilinea ). In ec ilinea g ids, he
scheme leads o he same e ahed al decomposi ion as in [18].
Some me hods a emp o es ima e opology also inside he ambiguous cubes
ei he by using c i ical poin analysis [20] o ilinea in e pola ion. Isosu ace
ex ac ion algo i hms based on ilinea in e pola ion add ess he opological
co ec ness by imposing he local opology o he local ilinea in e polan
inside e e y g id cubic cell. Na a ajan [21] and Che nyae [22] independen ly
ecognized ha , besides he ace ambigui ies, he e a e addi ional ambigui ies
in he ep esen a ion o he ilinea in e polan in he in e io o he cube. In
he case o a cell wi h wo diagonally-opposi e black e ices, he su ace may
be in wo sepa a e pieces o he e may be a single unnel piece, opologically
equi alen o a cylinde (see igu e 2). Na a ajan used he alue o he body
saddle poin (whe e all h ee i s pa ial de i a i es o he ilinea in e polan
a e ze o) o disc imina e he wo cases. Ma eye [23] also discussed he in-
e io ambigui y p oblem, esol ing he ambiguous cases by conside ing he
beha io o he ilinea unc ion along he cell diagonals. Cignoni e al. [24]
designed a new mul i-en y lookup able (exhaus i e lookup able, ELUT) us-
4
ing he Na a ajan app oach, which p o ides, o each cell con igu a ion and
o each combina ion o he alues o he saddle poin s o he ambiguous aces
and/o o he body saddle poin , he co ec isosu ace pa ch con ained in
he cell. They include a inal mesh e inemen in o de o ensu e ha he i-
angula ed su ace will ha e he same opology as he ilinea in e polan in
he cell. An e icien and obus implemen a ion o he Che nyae me hod is
p esen ed in [25]. This algo i hm gua an ees a inal wo mani old su ace using
a ba e y o op imized es s and an ex ended Che nyae lookup able. This
sequence o pape s ha a emp o gua an ee econs uc ions wi h he local
opology o he ilinea in e polan inside e e y g id cell culmina es wi h he
wo pape s om Nielson [26] and Lopes and B odlie [27]. These wo pa allel
pape s p esen well- ounded and obus econs uc ion algo i hms based on
he analysis o ace and body saddle poin s and gi e exhaus i e cha ac e iza-
ions o he possible cases.









Fig. 2. The wo possible opologies a ising om an X-cube.
Among he algo i hms ha use ex a in o ma ion apa om alues a he
g id e ices we can ci e he Ex ended Ma ching Cubes scheme om Kobbel
e al. [28]. Kobbel ep esen s a ec o dis ance ield by s o ing h ee scala
alues a each g id poin . In addi ion, a local es ima ion o he su ace no -
mal ec o is s o ed a he g id e ices. The ec o dis ance ield is in ac
ep esen ing he exac loca ion o he su ace in e sec ions wi h he g id edges
(wi h a maximum o one in e sec ion pe edge). Edge and e ex ea u es can
be de ec ed and econs uc ed by de ec ing ea u e cells and inse ing an ap-
p op ia e poin in hem. The Dual Con ou ing algo i hm [29] econs uc s he
su ace om He mi e da a: he inpu alues a e he in e sec ion poin s and
no mal ec o s o he in e sec ions su ace wi h he g id edges (maximum o
one in e sec ion). The algo i hm uses a quad a ic e o me ic o compu e
a new poin inside each o he ou cells a ound each black-whi e g id edge
and gene a es a quad connec ing hese ou new poin s. The algo i hm is able
o eco e sha p ea u es o he ini ial solid. Va adhan e al. [30] e ec i ely
compu e up o wo in e sec ions on each edge o he g id. They hen p oceed
wi h an adap a ion o he Dual Con ou ing algo i hm, esul ing in a scheme
ha is able o e ec i ely eco e some hin ea u es o he o iginal. In [31]
hey complemen his p oposal wi h a cha ac e iza ion o cells whe e he algo-
5

i hm is able o econs uc he exac opology o he o iginal, and p opose an
adap i e subdi ision scheme ha e ines he g id locally un il all cells sa is y
ha c i e ion. The app oach in [32] is a a ia ion o Ma ching Cubes and Dual
Con ou ing, also equi ing He mi e da a. A Quad ic E o Me ics econs uc-
ion is pe o med a each ambiguous ace o a pa icula g id cell, compu ing
a new isosu ace poin in he ace. In he las s ep, he su ace inside he cell
is econs uc ed.
The olume-based app oach om Anduja e al. [33,34] uses he ini ial geom-
e y inside he cell o de ec g ey cells con aining pa s o he ini ial objec
su ace. The algo i hm pe o ms an addi ional subdi ision o he cells and
compu es i s e ex signs using he 26-adjacen cells. Resul ing subcell con ig-
u a ions a e gua an eed o be unambiguous. This app oach allows he econ-
s uc ion o hin pa s o he objec and ensu es a olume-Hausdo dis ance
condi ion be ween he ini ial and he econs uc ed objec .
A di e en app oach o sol ing he opological co ec ness p oblem is p e-
sen ed in [35]. In his case, he op imiza ion o he o e all opological p op-
e ies is achie ed h ough a global app oach. The con ol o he opological
beha io will be discussed in Sec ion 4.
3 Disc e e olume ep esen a ions: de ini ions and p ope ies
Le us assume ha Vis a bounded closed olume in
R
3and ha Sis he
bounda y o V. Le us also assume ha we ha e a ec angula uni o m g id R
wi h cubical cells cwi h sides o leng h `. The elemen s o Ra e i s cells c(R),
he g id e ices (R) and he cell aces and edges, (R) and e(R). We shall
always conside hese componen s as closed se s; hus, he edges include bo h
endpoin s, he aces include hei edges, and he cells include all six aces.
The e o e, o example, he cells c(R) do no cons i u e a pa i ion o R.
De ini ion 1 Whi e and black cells
A cell co Rwill be called whi e i he se in e sec ion be ween cand Vis
he oid se . A cell co Rwill be called black i he se in e sec ion be ween c
and Vis he same cell c.
Ve ices o Rcan also be classi ied as whi e o black in a simila way: The
classi ica ion o a whi e e ex is ou V , while black e ices can be inV o
onV . Edges eand aces o Rcan be classi ied in a simila way as cells.
Cells o Rno being whi e o black will be called g ey cells. G ey cells ha e a
non-null in e sec ion wi h S. G ey cells can be o ou di e en ypes:
6
De ini ion 2 G ey-0 cells (G0cells)
A g ey cell co Ris in G0i he numbe o i s whi e e ices is g ea e han
ze o and less han eigh . In o he wo ds, G0cells ha e a non-uni o m se o
e ices: some o hei eigh e ices a e whi e while some o he e ices a e
black.
De ini ion 3 G ey-1 cells (G1cells)
A g ey cell co Ris in G1i he e exis s some edge eo csuch ha he
in e sec ion be ween eand Sis no null.
De ini ion 4 G ey-2 cells (G2cells)
A g ey cell co Ris in G2i he e exis s some ace o csuch ha he
in e sec ion be ween and Sis no null.
De ini ion 5 G ey-3 cells (G3cells)
A g ey cell co Ris in G3i he in e sec ion be ween cand Sis no null.
No ice ha e e y cell in c(R) is ei he whi e, black, o belongs o G3. This
again is no a pa i ion, as a black cell whose bounda y has a non- oid in e -
sec ion wi h S=∂V is also in G3.
Abusing language we speak o Gkcells e e ing o cells in Gk. We will u he
abuse language by saying ha a su ace ex ac ion algo i hm is a Gkalgo i hm
i i ope a es by compu ing Gkcells. In all cases i will be clea by he con ex
o which o hese we e e . No ice ha when applied o algo i hms, his clas-
si ica ion e e s o he inpu , o a leas he pa o he inpu he algo i hm is
in e es ed in. Conce ning he ou pu , we also de ine:
De ini ion 6 k− econs uc ion algo i hms
We will say ha a su ace econs uc ion algo i hm is a k- econs uc ion i
he ou pu su ace is comple ely con ained in ∪c∈Gkcand he ou pu olume
in e sec s all he cells in Gk.
3.1 P ope ies
F om hese de ini ions alone, a se ies o use ul p ope ies can be shown. We will
lis hem he e, and la e apply hem in he analysis o he di e se algo i hms
ha ha e been p oposed in he li e a u e.
Fi s , i is i ially seen ha he Gk o m a hie a chy:
7
P ope y 1 Fo each k∈ {0,1,2},Gk⊂Gk+1
I a cell is in G0, i has an edge wi h di e ing classi ica ions a he e ices.
Because o Bolzano’s heo em, he bounda y mus in e sec ha edge a leas
once, hence he cell is in G1. The es o he inclusions ollow om he ac ha
we conside all elemen s closed, hence in e sec ing an edge implies in e sec ing
he aces ha sha e i , and in e sec ing a ace implies in e sec ing he cells
ha sha e i .
I a cell is in G3 G2, hen i mus con ain an isola ed po ion o Vin i s
in e io . The e o e G3can only di e om G2i Vcon ains connec ed com-
ponen s o olume less han `3. The con e se o his is ob iously no ue, as
an a bi a yly small connec ed componen may con ain a e ex o R, bu he
p e ious ob ious ema k implies ha
P ope y 2 Fo any olume V, he e is an ε∈
R
such ha i `<ε=⇒
G3(V) = G2(V)
since Vis bounded and closed, and hence compac .
Ob iously, Gkalgo i hms wi h k < 3 will miss hese small po ions, and will
no be able o o e a comple e econs uc ion unless `is chosen su icien ly
small. Howe e G3may also miss some o hese small po ions i hey do no
gua an ee a 3- econs uc ion.
The di e ences be ween o he se s in he g ey hie a chy canno be so easily
cha ac e ized. Cells in G2 G1a e cells ha con ain a po ion o he olume
ha en e s and exi s h ough aces o cells, wi hou dis u bing any edges.
The e o e hey a e hin po ions o V. Tipically hese oxels a e popula ed
by pipe-like po ions o he olume, bu his need no be so. Gi en a ce ain
ec angula g id R, conside he olume ob ained o illing i up comple ely
( aking he union o all he cells in R), and hen sub ac ing a bi a ily small
cylinde s wi h he edges o axes. The esul is a solid Vwhose olume is
a bi a ily close o ha o R, ye all he cells o Ra e in G2bu no in G1.
A simila case is G1 G0, whe e we can conside V=∪c∈c(R)c ∪ ∈ (R)B ,
whe e B deno es a small open ball cen e ed a he e ex .
These a e ex eme bu un eal examples in p ac ice. We will show howe e
wi h examples o which ex en he p oblem is no so dis an om p ac ical
econs uc ion p oblems.
Finally, no ice ha 3- econs uc ions gua an ee a bound on he Hausdo
dis ance be ween S=∂V and he esul o he econs uc ion:
P ope y 3 Gi en a olume V, and a 3- econs uc ion V0using a g id wi h
8
cell-size `, hen
Haus(V, V 0)≤q(3)`
No ice ha V0in e sec s all he cells in G3, and he e is a po ion o S, and
hence o V, in each cell o G3. Fu he mo e each poin on Vis ei he in a
black cell o in some cell in G3, and a 3- econs uc ion mus p oduce a olume
ha in e sec s ha cell. Since wo poin s in a cell canno be u he han he
s a ed bound, he p ope y ollows immedia ely.
This desi able p ope y, howe e , is no gua an eed o any o he econs uc-
ion le el, as we ha e seen ha in gene al G3 Gk6=∅ o k < 3, and po ions
on cells in G3 Gkmay lie a bi a ily a om he algo i hm’s ou pu su ace.
4 Topological p ope ies o isosu aces
The objec i e o his sec ion is o cha ac e ize he su ace ex ac ion algo-
i hms e iewed in Sec ion 2 by using he p ope ies de ined in he p e ious
Sec ion. A special ema k will be done on discussing he opological p ope ies
o he su aces ha hey econs uc , wi hou conside ing he inal applica ion
desc ibed in he pape s whe e hey a e p esen ed.
4.1 0- econs uc ion algo i hms
Mos o he e iewed algo i hms [6,7,15,17–19,28,32,35] a e a ia ions o he
o iginal Ma ching Cubes algo i hm [1]. They ha e a se o common cha ac-
e is ics: The inpu in o ma ion is he classi ica ion o he g id e ices wi h
espec o he olume ( hey only de ec G0cells), he ou pu su ace is a i-
angle mesh econs uc ed locally o each G0cell. Each iangle o he inal
mesh belongs o a unique cell, and he ou pu su ace S0in e sec s only once
each black-whi e edge o he g id. These p ope ies gua an ee ha he ou pu
su ace s abs all G0cells, so all hese algo i hms a e 0− econs uc ions.
The main di e ence among he o me algo i hms lies in he me hod hey use
o pe o m he local econs uc ion o he iangle mesh M. The e a e wo
decisions o conside : he selec ion o he local opology o Min a cell and
he iangula ion o he esul ing connec ed componen s (shee s) in such a
way ha i has no impac on he selec ed opology. [35] shows ha he only
MC con igu a ions gi ing choices o con ol he local opology a e hose ha
co espond o cells ha ing ambigui y aces (also called X- aces, see Figu e 1),
9
las wo igu es a e gene a ed by [35] using wo di e en op imiza ion s a e-
gies. S a egy used o Figu e 5(e) minimizes he numbe o solid componen s,
while Figu e 5( ) shows he esul o adop ing he oposi e s a egy and i is
he only one eco e ing he ini ial wo shells.
The disc e iza ion o he model in Figu e 6(a) p esen s abundan ambigu-
ous aces and cells. This example shows clea ly how he al e na ing me hods
(Figu e 6(b)) a bi a ily join o sepa a e po ions o he model. The ilinea
app oaches (Figu e 6(c)) ailed o econs uc diagonals. Figu e 6(d) clea ly
shows how he dual con ou ing algo i hm c ea es non-mani old e ices and
edges. Using he same wo s a egies as in Figu e 5, [35] yields he solu ions in
Figu es 6(e) and 6( ). No e ha he opology o Figu e 6(e) exac ly ma ches
he o iginal model.
6 Conclusions
Isosu ace ex ac ion algo i hms di e on how he disc e e in o ma ion in he
g id is gene a ed, on wha in o ma ion does he g id s o e and on he p ope -
ies o he ou pu su ace. Recen algo i hms o e di e en solu ions o he
disambigua ion p oblem and o con olling he inal opology.
Based on a numbe o p ope ies o he g id g ey cells and o he econs uc ion
algo i hms, a cha ac e iza ion o se e al su ace ex ac ion algo i hms has been
p oposed. The classi ica ion in Table 1 p esen s he inhe en limi a ions o
he di e en algo i hms conce ning global opology con ol and econs uc ion
o local ea u es like hin po ions o he olume and almos non-mani old
egions. These limi a ions ha e been obse ed and discussed in some p ac ical
examples.
Mos o he algo i hms discussed a e o ype G0and only p esen local opol-
ogy con ol. Non-global opology con ol usually leads o some a bi a y inal
opology which will no ul ill he use equi emen s and/o a ge s. Gkalgo-
i hms wi h k > 0 a e sca ce. In some cases, e en i He mi e da a a e s o ed in
g id edges, he algo i hms emain G0because hey ope a e by compu ing G0
cells and do no conside g id edges wi h mul iple su ace in e sec ions (wi h
he sole excep ion o [30]). As obse ed in P ope y 2, Gkalgo i hms wi h
k < 3 will miss small po ions o he olume unless he g id edge size is chosen
su icien ly small.
A po en ial line o u u e wo k is he de elopmen o new wo-mani old su ace
ex ac ion algo i hms wi h he 3- econs uc ion p ope y and/o global opol-
ogy con ol o he ou pu su ace. As s a ed in P ope y 3, 3- econs uc ion
schemes exhibi a bounded Hausdo dis ance p ope y ha gua an ee a sim-
16

(a) O iginal model (b) Al e na ing e ahediza ion
(c) T ilinea disambigua ion (d) Dual Con ou ing
(e) Minimizing componen s ( ) Maximizing componen s
Fig. 5. Di e en esul s om di e en G0algo i hms. The model has been gene a ed
wi h i e oc ee subdi ision le els.
ila i y be ween he ini ial olume and he econs uc ed one.
17
(a) O iginal model (b) Al e na ing e ahed iza ion
(c) T ilinea disambigua ion (d) Dual Con ou ing
(e) Minimizing componen s ( ) Maximizing componen s
Fig. 6. Di e en esul s om di e en G0algo i hms. The model has been gene a ed
wi h ou oc ee subdi ision le els.
Re e ences
[1] W. Lo ensen, H. Cline, Ma ching cubes: A high esolu ion 3D su ace
cons uc ion algo i hm, Compu e G aphics 21 (4) (1987) 163–169.
18
[2] M. J. D¨u s , Le e s: Addi ional e e ence o ma ching cubes, Compu e
G aphics 22 (2) (1988) 72–73.
[3] G. Nielson, T. Foley, B. Hamann, D. Lane, Visualizing and modeling sca e ed
mul i a ia e da a, IEEE Compu e G aphics and Applica ions 11 (3) (1991)
47–55.
[4] T. He, L. Hong, A. E. Kau man, A. Va shney, S. W. Wang, Voxel based objec
simpli ica ion, in: IEEE Visualiza ion, 1995, pp. 296–303.
[5] T. He, L. Hong, A. Va shney, S. W. Wang, Con olled opology simpli ica ion,
IEEE T ansac ions on Visualiza ion and Compu e G aphics 2 (2) (1996) 171–
184.
[6] J. Bloomen hal, An implici su ace polygonize , in: P. S. Heckbe (Ed.),
G aphics Gems IV, Academic P ess, 1994, pp. 324–349.
[7] J.-O. Lachaud, Topologically de ined iso-su aces, in: P oc. 6 h Disc e e
Geome y o Compu e Image y (DGCI’96), Lyon, F ance, Sp inge -Ve lag,
Be lin, 1996, pp. 245–256.
[8] P. Ning, J. Bloomen hal, An e alua ion o implici su ace ile s, IEEE
Compu e G aphics and Applica ions 13 (6) (1993) 33–41.
[9] S. Hill, J. C. Robe s, Su ace models and he esolu ion o n-dimensional cell
ambigui y, in: A. W. Pae h (Ed.), G aphics Gems V, Academic P ess, 1995, pp.
98–106.
[10] A. Wallin, Cons uc ing isosu aces om c da a, IEEE Compu e G aphics and
Applica ions 11 (6) (1991) 28–33.
[11] G. Wy ill, C. McPhee e s, B. Wy ill, Da a s uc u es o so objec s, The
Visual Compu e 2 (4) (1986) 227–234.
[12] G. Nielson, B. Hamann, The asymp o ic decide : Resol ing he ambigui y in
ma ching cubes, in: P oc. o IEEE Visualiza ion 91, 1991, pp. 83–91.
[13] J. Wilhelms, A. V. Gelde , Topological conside a ions in isosu ace gene a ion,
Compu e G aphics 24 (5) (1990) 79–86.
[14] A. A. Pasko, V. V. Pilyugin, Geome ic modelling in he analysis o i a ia e
unc ions, Compu e s & G aphics 12 (3-4).
[15] C. Mon ani, R. Sca eni, R. Scopigno, A modi ied look-up able o implici
disambigua ion o ma ching cubes, The Visual Compu e 10 (6) (1994) 353–
355.
[16] C. Mon ani, R. Sca eni, , R. Scopigno, Disc e ized ma ching cubes, in: IEEE
Visualiza ion, 1994, pp. 281–287.
[17] C. Zahl en, Piecewise linea app oxima ion o iso alued su aces, in: F. H. Pos ,
A. J. S. Hin (Eds.), Ad ances in Scien i ic Visualiza ion, Sp inge -Ve lag, 1992,
pp. 105–118.
19
[18] A. Gueziec, R. Hummel, Exploi ing iangula ed su ace ex ac ion using
e ahed al decomposi ion, IEEE T ansac ions on Visualiza ion and Compu e
G aphics 1 (4) (1995) 328–342.
[19] V. Pascucci, Isosu ace compu a ion made simple: Ha dwa e accele a ion,
adap i e e inemen and e ahed al s ipping, in: EG-TVCG Symposium on
Visualiza ion, 2004.
[20] B. T. S ande , J. C. Ha , Gua an eeing he opology o an implici su ace
polygoniza ion o in e ac i e modeling, Compu e G aphics (SIGGRAPH 97
P oceedings) 31 (1) (1997) 279–286.
[21] B. K. Na a ajan, On gene a ing opologically consis en isosu aces om
uni o m samples, Visual Compu e 11 (1) (1994) 52–62.
[22] E. Che nyae , Ma ching cubes 33:
Cons uc ion o opologically co ec isosu aces, Tech. Rep. CN/95-17, CERN,
h p://wwwin o.ce n.ch/asdoc/psdi /mc.ps.gz (1995).
[23] S. Ma eye , App oxima ion o isosu ace in he ma ching cube: Ambigui y
p oblem, in: IEEE Visualiza ion, 1994, pp. 288–292.
[24] P. Cignoni, F. Gano elli, C. Mon ani, R. Scopigno, Recons uc ion o
opologically co ec and adap i e ilinea isosu aces, Compu e s and
G aphics 24 (3) (2000) 399–418.
[25] T. Lewine , H. Lopes, A. W. Viei a, G. Ta a es, E icien implemen a ion o
ma ching cubes’ cases wi h opological gua an ees, Jou nal o G aphics Tools
8 (2).
[26] G. Nielson, On ma ching cubes, IEEE T ansac ions on Visualiza ion and
Compu e G aphics 9 (3) (2003) 283–297.
[27] A. Lopes, K. B odlie, Imp o ing he obus ness and accu acy o he ma ching
cubes algo i hm o isosu acing, IEEE T ansac ions on Visualiza ion and
Compu e G aphics 9 (1) (2003) 16–29.
[28] L. P. Kobbel , M. Bo sch, U. Schwanecke, H. P. Seidel, Fea u e sensi i e su ace
ex ac ion om olume da a, ACM Compu e G aphics (Sigg aph 2001) (2001)
57–66.
[29] T. Ju, F. Losasso, S. Schae e , J. Wa en, Dual coun ou ing o he mi e da a,
ACM T ansac ions on G aphics 21 (3) (2002) 339–346, p oc o Sigg aph’02.
[30] G. Va adhan, S. K ishnan, Y. Kim, D. Manocha, Fea u e-sensi i e subdi ision
and isosu ace ecos uc ion, in: IEEE Visualiza ion, 2003, pp. 99–106.
[31] G. Va adhan, S. K ishnan, T. S i am, D. Manocha, Topology p ese ing su ace
ex ac ion using adap i e subdi ision, in: Symposium on Geome y P ocessing,
2004, pp. 241–250.
[32] C.-C. Ho, F.-C. Wu, B.-Y. Chen, Y.-Y. Chuang, M. Ouhyoung, Cubical
ma ching squa es: Adap i e ea u e p ese ing su ace ex ac ion om olume
da a, Compu e G aphics Fo um (Eu og aphics 2005) 24 (3) (2005) 537–546.
20
[33] C. Anduja , P. B une , D. Ayala, Topology- educing simpli ica ion h ough
disc e e models, ACM T ansac ions on G aphics 20 (6) (2002) 88–105.
[34] C. Anduja , M. Fai ´en, P. B une , V. Cebollada, Ad ances in Mul i esolu ion o
Geome ic Modelling, Sp inge -Ve lag, 2005, Ch. Simpli ica ion o Topologically
Complex Assemblies, pp. 339–352, iSBN 3-540-21462-3.
[35] C. Anduja , P. B une , A. Chica, J. Rossignac, I. Na azo, A. Vinacua,
Op imizing he opological and combina ional complexi y o isosu aces,
Compu e -Aided Design 37 (8) (2005) 847–857.
21