Warping cubes: better triangles from marching cubes

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).