Wa ping Cubes: Be e T iangles om Ma ching Cubes
LeeAnn Tzeng a,1
aDa mou h College, 6211 Sudiko Labo a o y, Hano e , NH 03755
Key wo ds: iangula ion, isosu ace econs uc ion, Ma ching Cubes
1. In oduc ion
The Ma ching Cubes algo i hm [6] o ex ac -
ing a iangula ion o an isosu ace o a unc ion
de ined o e a h ee-dimensional space is amous
h oughou g aphics. Howe e , he iangles c e-
a ed by Ma ching Cubes a e o en qui e skinny.
These hin iangles can c ea e a i ac s in com-
pu e ende ing, and make he su ace iangu-
la ion unsui able o olume ende ing. To a oid
hese a i ac s in ende ing, hin iangles need o
be elimina ed om he iangula ion c ea ed by
he Ma ching Cubes algo i hm.
The mos basic o m o Ma ching Cubes places a
g id o e he egion con aining he unc ion whose
isosu ace we wish o ex ac . The unc ion is e al-
ua ed a he e ices o his g id (I will call hese
he “co ne s” o he cubes o a oid con usion wi h
he e ices o he esul ing iangula ion), and
each co ne is labelled as being posi i e o nega-
i e. Based on he pa e n o labels, each cube is
iangula ed ia a lookup able ( o speed). The
esul is a iangula ion ha has e ices on he
edges o he cubes whe e he isosu ace in e sec s
he edge. [8]
2. Wa ping and Collapsing
My algo i hm modi ies Ma ching Cubes by
adding a “wa ping” phase o he o iginal algo-
i hm. This phase migh be e be called he
“collapsing” phase, as will become clea sho ly
( hough i could be desc ibed as “wa ping” he
Email add ess: l [email protected] mou h.edu (LeeAnn
Tzeng).
1Suppo ed on a Na ional Science Founda ion G adua e
Fellowship.
iangula ion). The wa ping he e should no be
con used wi h Oc - ee Wa ping, which is isually
simila bu ac ually e y di e en [7]. This p ocess
o wa ping o collapsing is based on he obse a-
ion ha skinny iangles ake one o wo o ms.
The i s kind o skinny iangle is e y all, wi h a
iny base. This kind has one sha p angle a he op.
The o he kind o skinny iangle has an ex emely
sho al i ude and a e y long base. (Fig. 1) My
app oach a acks each o hese p oblems di ec ly.
Fig. 1. Two kinds o skinny iangles.
2.1. Sho edges
A sho edge occu s when he isosu ace in e -
sec s a cube e y close o he cube’s co ne . Each
endpoin o he sho edge lies on one o he cube’s
edges close o ha co ne . A nai e i s hough is
o pull he co ne away om he sho edge, c ea -
ing a dis o ed cube ha leng hens he sho edge.
Howe e , e en in 2D, i is easy o see how his
migh cause addi ional p oblems in adjacen cubes.
(Fig. 2)
Fig. 2. In 2D, pulling he co ne s can c ea e mo e sho
edges in neighbo ing cubes.
Ins ead, I choose o mo e he co ne on o he
sho edge. This emo es he sho edge al oge he
20 h EWCG Se ille, Spain (2004)
20 h Eu opean Wo kshop on Compu a ional Geome y
by eplacing i s wo endpoin s, each a e ex in
he iangula ion, wi h a single e ex. This wa ps
he cubes in a mo e unila e ally bene icial way: I
elimina e a sho edge bu do no sho en any o he
edges. In ac , mo e o en han no , he emaining
edges a e ac ually leng hened. One can easily see
how his echnique migh also be seen as collapsing
he sho edge in o a single e ex. (Fig. 3 and 4)
Fig. 3. Wa ping on o he sho edge in 2D. This can also
be seen as collapsing he sho edge in o a e ex.
Fig. 4. Collapsing he sho edge in 3D. The wo long edges
me ge oge he in o one edge. The op endpoin s ays he
same, and he bo om endpoin is he new collapsed e ex.
A quick men al expe imen shows ha he bes
place o which o mo e he co ne is he midpoin
o he sho edge. Ideally, he wa ped iangula ion
s ays as close o he known isosu ace as possible.
The midpoin o he sho edge a oids e e ge ing
oo a away om he known isosu ace, since i
minimizes how a each endpoin has o mo e o
achie e a collapsed edge. (Fig. 5)
Fig. 5. Collapsing o he sho edge’s midpoin minimizes
he dis ance om he known poin s o he isosu ace.
One ob ious ques ion is wha o do i he e a e
wo o mo e sho edges a he same co ne . I he e
a e wo sho edges a he same co ne , bu no a
hi d, hen he wo sho edges mus be in neigh-
bo ing cubes. I choose o collapse he wo edges
in o hei sha ed e ex. This is be e han col-
lapsing i s one and hen he o he sho edge bo h
because i keeps he esul ing e ex on he known
isosu ace, and because i minimizes how a each
o he neighbo ing non-sho edges has o mo e.
(Fig. 6)
Fig. 6. Collapsing wo adjacen sho edges in o hei com-
mon e ex.
I he e a e h ee sho edges a he same co ne ,
hen we ha e a small iangle ha is likely o be
well-shaped (by Delaunay s anda ds). In his case,
all h ee edges a e collapsed in o a single e ex.
This looks like sh inking he small iangle in o
a e ex. Since he iangle is so small, any poin
wi hin he iangle is a easonable candida e o he
inal e ex, so I am cu en ly using he incen e
simply because i is gua an eed o be inside he
iangle. (Fig. 7)
Fig. 7. Collapsing a small iangle in o i s incen e .
This concep is ex ended as edges a e added.
The e can be a o al o wel e sho edges a one
co ne , which implies a “bubble” in he iangula-
ion. I his bubble is comple ely disconnec ed om
he es o he iangula ion, hen all o i s ian-
gles will be nicely shaped, so he e will no be any
ende ing a i ac s. I he bubble is in e nal, hen
o he pu poses o ende ing, we can igno e he
bubble comple ely. I he bubble has o he edges
ex ending om i s e ices, one can collapse all o
i s edges collec i ely in o he incen e o he oc a-
hed on de ined by he wel e edges. This lea es a
e ex wi h any ou side edges now coming in o i .
Fo any gi en numbe o sho edges a one co -
ne , I always choose o collapse he cen e mos
Ma ch 25-26, 2004 Se ille (Spain)
piece a ha co ne i s . Fou edges o ces he i h,
which is wo adjacen iangles sha ing a common
edge. I collapse he common edge i s , lea ing wo
sho edges mee ing a he new collapes e ex. I
hen ea i as a wo-edge adjacen pai . A six h
edge o ces eigh edges, and he cen e mos piece
is a e ex a he “peak” o he esul ing py amid.
Since he cen e mos piece is al eady a e ex, I col-
lapse all o he edges di ec ly in o he peak e ex.
A nin h edge o ces a o al o wel e edges which
has al eady been men ioned abo e.
2.2. Sho al i udes
The o he kind o hin iangle is in some
ways much mo e insidious. The wide-base, sho -
al i ude iangle does no necessa ily ha e an
ob ious sho edge o collapse, and he collapsing
p ocedu e has mo e po en ially dange ous conse-
quences. In isola ion, i seems a he innocuous.
The iangle can simply be collapsed along i s
sho al i ude, esul ing in an edge. (Fig. 8) This
al i ude is he sho es dis ance ha his iangle
can be la ened, hus again minimizing how a
he collapsed iangula ion s ays om he known
isosu ace.
Fig. 8. The iangle is la ened on o i s longes edge.
Wi hin a iangula ion, howe e , his collapse
c ea es an ex a e ex and equi es he addi ion o
a new edge o he iangula ion. (Fig. 9) Whe eas
he sho -edge collapse a oids e e sho ening a
emaining edge, he sho -al i ude collapse cu s a
longe edge in wo. This new edge has he po en ial
o c ea e a new hin iangle whe e he e was no
one be o e.
Fig. 9. The collapsed al i ude esul s in a new e ex along
he long edge and a new edge on he opposi e side.
I is wo h no ing ha he e is only one way
o ge a sho -al i ude iangle om he o iginal
Ma ching Cubes. In pa icula , e e y iangle gen-
e a ed by Ma ching Cubes is con ained wi hin a
cube, so he possible iangle con igu a ions come
om he Ma ching Cubes lis . To ge a sho -
al i ude iangle, he wo sho e edges mus lie
“ac oss an edge o he cube”, meaning ha each
edge lies in a ace o he cube, and he wo aces
ha e an edge in common. (See Fig. 10) The e ex
o he iangle ha is an endpoin o he sho
al i ude lies on he edge ha is sha ed by he wo
aces o he cube. The wo sho e edges o he
iangle each ex end o an adjacen edge o he
cube espec i ely, and he dis ance along each o
he cube edges whe e he iangle’s edge ends is
e y small.
Fig. 10. A sho -al i ude iangle and he i e edges whe e
he opposi e e x may lie.
This means ha he iangle on he o he side o
he sho -al i ude iangle’s long edge can only ake
on a speci ic ange o shapes. The opposi e e ex
can be in one o wo ela i e loca ions. Conside he
wo aces ac oss which he wo sho e edges o he
iangle lie. All se en o he edges bounding hose
wo aces a e no possible loca ions o he oppo-
si e e ex. This lea es i e edges on which he op-
posi e e ex may lie. O hese i e, ou gi e e y
simila iangle possibili ies, and hen he e is he
i h. The i h edge is he edge ha sha es bo h
endpoin s wi h o he edges in his collec ion. All
i e o hese possible edges yield he same wo s -
case iangle. This iangle can yield one sho -
al i ude iangle, bu ha iangle can hen be e-
sol ed by collapsing ha iangle’s sho es edge
in he manne desc ibed in he p e ious sec ion.
This wo ks because he only way o ge ano he
bad sho -al i ude iangle is o ha e a e y sho
edge esul ing om he i s al i ude-collapse. Fu -
he , he collapse o sho edges can no gene a e
a sho -al i ude iangle, so his ends he p ocess.
The e is one si ua ion om he Ma ching Cubes
33 se o possible iangula ions ha allows o he
sho -al i ude iangle o lie comple ely wi hin one
ace o he cube [3]. In he cases whe e his occu s,
he e is always a ou h e ex on he emaining
edge o ha cube ace, and his ou h e ex com-
ple es he iangle on he o he side o he sho -
al i ude iangle’s longes edge. This opposi e-side
20 h Eu opean Wo kshop on Compu a ional Geome y
iangle is, a wo s , be e han he wo s -case i-
angle om he egula Ma ching Cubes iangula-
ion. This iangle can hus be handled he same
way as desc ibed abo e.
2.3. Sho edges be o e sho al i udes
I is impo an o collapse he sho edges i s ,
be o e collapsing he al i udes. Once he al i udes
ha e been collapsed, ano he (much smalle ) pass
o sho -edge-collapsing emo es any new sho
edges le behind by he al i ude collapses. The
eason o his o de is o a oid c ea ing an un-
necessa y new sho edge when he sho al i ude
is collapsed on o he longes edge. The longes
edge is b oken in o wo, and a sho edge in he
s a ing iangle will cause he long edge o be
b oken in o one e y sho edge and one eason-
ably long edge. This new sho edge is unwan ed.
I he sho edges a e no collapsed i s , his kind
o sho -edge c ea ion has he po en ial o u n
in o a se ies o such sho edges appea ing. By
collapsing he sho edges i s , he p obabili y o
hese se ies a ising du ing he al i ude collapse is
g ea ly educed, and he ew newly c ea ed sho
edges can be handled quickly a e wa ds.
3. Resul s and Conclusions
Wi hou loss o gene ali y, I ea he g id size
as 1, and de ine ε o be he minimum accep able
edge leng h as a ac ion o he g id size. I de ine
η o be he minimum accep able al i ude, also as
a ac ion o he g id size. On he i s pass, edges
ha a e sho e han εa e collapsed. Once he
sho edges ha e been add essed, I ind all iangles
wi h al i ude smalle han ηand collapse hose.
Ano he quick pass h ough ge s id o any newly
c ea ed sho edges. Le Bbe he ci cum adius- o-
sho es -edge a io o a iangle. Then i I choose
ε= 0.4 and η= 0.35, hen B≤1.5.
The ou een cube con igu a ions de ined by he
Ma ching Cubes algo i hm can be educed o six
based on combina ions, and each o hese has a
wo s -case iangle. Fo abou hal o hese cases,
i is su icien o ha e η= 0.25, bu he e a e a
ew cases ha ha e pa icula ly unwieldy po en ial
iangles, and hese equi e ha η= 0.35. Since
he sho es edge leng h is se by ε, he esul ing
bound on Bdi ec ly implies a nice uppe bound
on he ci cum adius o he iangles.
Quali y bounds on iangula ions in isosu ace
ex ac ion a e s ill ela i ely a e. While a g ea
deal o quali y analysis has been done on mesh-
gene a ion and iangula ion algo i hms o known
su aces and poin -se s, he e has been ema kably
li le analysis on he quali y o he iangula ions
gene a ed by isosu ace-ex ac ion algo i hms,
whe e he su ace is no known a p io i. A ali and
Lachaud gi e an algo i hm ha locally cons uc s
an isosu ace ha is Delaunay con o ming [2] [1],
hus gi ing some sense o iangula ion quali y,
bu e en Delaunay iangula ions o en s ill con-
ain he skinny iangles ha can cause ha oc in
ende ing con ex s. I ha e p esen ed an isosu ace
ex ac ion algo i hm ha espec s a gua an ee o
quali y in e ms o ci cum adius- o-sho es -edge
a io, an inc easingly popula measu e o mesh
and iangula ion quali y.
Re e ences
[1] D. A ali, J.-O. Lachaud, Cons uc ing Iso-Su aces
Sa is ying he Delaunay Cons ain . Applica ion o he
Skele on Compu a ion., P oc. 10 h In l. Con . on Image
Analysis and P ocessing (Venice, I aly, 1999) 382–387.
[2] D. A ali, J.-O. Lachaud, Delaunay Con o ming Iso-
su ace, Skele on Ex ac ion and Noise Remo al, Comp.
Geome y: Theo y and Applica ions 19 (2001) 175–189.
[3] E.V. Che nyae , Ma ching Cubes 33: Cons uc ion o
Topologically Co ec Isosu aces, CERN Repo CN-
95-17 (1995).
[4] P. C ossno, E. Angel, Isosu ace Ex ac ion Using
Pa icle Sys ems, IEEE Visualiza ion (1997) 495–498.
[5] K. Ho mann, U. Labsik, M. Meis e , G. G eine ,
Hie a chical Ex ac ion o Iso-Su aces wi h Semi-
Regula Meshes, P oc. 7 h ACM Symposium on Solid
Modeling and Applica ions (Saa b ¨ucken, Ge many,
2002) 53–58.
[6] W. E. Lo ensen, H. E. Cline, Ma ching Cubes: A
High Resolu ion 3D Su ace Cons uc ion Algo i hm,
Compu e G aphics 21:4 (July 1987) 163–169.
[7] S. A. Mi chell, S. A. Va asis, Quali y Mesh Gene a ion
in Highe Dimensions, SIAM Jou nal on Compu ing
29:4 (2000) 1334–1370.
[8] J. Sha man, The Ma ching Cubes Algo i hm,
h p://www.exa lop.o g/docs/ma chcubes/ind.h ml.
(2003).
[9] G. Va adhan, S. K ishnan, Y. J. Kim, D.
Manocha, Fea u e-Sensi i e Subdi ision and Iso-
Su ace Recons uc ion, o appea in P oc. IEEE
Visualiza ion (2003).