Visual Computer manuscript No. (will be inserted by the editor) Convex Contouring of Volume

ConvexContouringofVolumetricData

TaoJu1,ScottSchaefer1,JoeWarren1

DepartmentofComputerScience,RiceUniversity

Thedateofreceiptandacceptancewillbeinsertedbytheeditor

AbstractInthispaperwepresentafast,table-drivenisosurfaceextractiontechniqueonvolumetricdata.Un-likeMarchingCubesorothercell-basedalgorithms,theproposedpolygonizationgeneratesconvexnegativespaceinsideindividualcells,enablingfastcollisiondetectiononthetriangulatedisosurface.Inourimplementation,weareabletoperformover2millionpointclassifica-tionspersecond.Thealgorithmisdrivenbyanauto-maticallyconstructedlook-uptablethatstorescompactdecisiontreesbysignconfigurations.Thedecisiontreesdeterminetriangulationsdynamicallybyvaluesatcellcorners.Usingthesametechnique,wecanperformfast,crack-freemulti-resolutioncontouringonnestedgridsofvolumetricdata.Themethodcanalsobeextendedtoex-tractisosurfacesonarbitraryconvex,space-fillingpoly-hedra.

Theseoperationsareoftenreferredtoascollisiondetec-tions.

Traditionally,contouringalgorithmsconsiderthedatavolumeinuniformcubicalcellsandpolygonizeisosur-facesineachnon-emptycell,i.e.,cellsthatareinter-sectedbytheisosurface.Bydoingso,theentirenega-tivespaceisdecomposedintosub-spaceswithinindivid-ualcells.Assumingthatthenegativespacemodelsfreespace,checkingwhetherapointliesinsidethefreespacecanbegreatlyacceleratedifthenegativesub-spaceisconvexwithintheenclosingcell.Notethatthispoint-classificationisthefundamentaloperationforcomputingcollisiondetectionwithotherconvexobjects.Forexam-ple,anedgeliesinthefreespaceifforeachcellitpassesthrough,bothendpointsofthelinesegmentwithinthatcelllieinthecell’snegativespace(figure1left).Thisobservationisnottrueifthenegativespacewithinthecellisnon-convex(figure1right).

Keyword:contour,polygonization,implicitmodeling

1Introduction

Recentadvancesinhardwaretechnologyof3Dscanningandsensoringhasbroughtaboutthegenerationoflarge-scalevolumetricdatasuchasMRIscans,CTscansandgeologicalimages.Acommonapproachtovisualizethesevolumedatasetsistorepresentthedataasimplicitfunc-tionsandconstructpolygonalapproximationsofisosur-faces,i.e.locusofpointswithsomegivenfunctionvalue.Thisprocessisoftenreferredtoascontouring.Thecon-touredsurfacepartitionsthewholevolumeintonegativespace(locusofpointswithlowerfunctionvalues)andpositivespace(locusofpointswithhigherfunctionval-ues).Inmanyinteractiveapplications,suchascomputergamingandreal-worldsimulations,navigationiscon-finedtothenegativespace,thereforefastoperationsforcheckingthesideofthemainsubject(e.g.thenavigator)withrespecttothecontouredsurfacebecomescritical.

Fig.1Edgeclassificationinasignedsquarewithtwodif-ferentcontours.Thedashedlinesindicatethecontours,thegrayareasrepresentnegativespace,andthedarkgraylineistheedgetobechecked.

Themostwidelyusedcell-basedalgorithmistheMarch-ingCubes(MC)algorithmintroducedbyLorensenandCline[7].MCgeneratestrianglesonisosurfaceswithineachcellbasedonapre-computedtableofpositive/negativepatterns(referredtoassignconfigurationshereafter)

2TaoJuetal.

Fig.2TriangulationsfromtheMarchingCubes’look-uptable.Negativecornersarecoloredblack.ofcellcorners.MCbecamepopularforitsfastpolygo-nizationandeasyimplementationduetoitstable-drivenmechanism.However,forsomesignconfigurations,MCdoesnotproducepolygonizationsthatareconsistentintopologywithneighboringcells,andthusresultinsurfacediscontinuities[4].Thisdrawbackhassparkledextensiveresearchondis-ambiguationsolutions[1],[4],[5],[10]andstrategiestogeneratetopologicallycorrectpolygonizations[9].Althoughthesesolutionsgeneratetopologicallyconsistentisosurfaces,theresultingnega-tivespaceinsideeachcellissometimesdisconnected,andthusnotconvex.

Inthispaper,weproposeafasttable-drivencell-basedcontouringmethodthatgeneratetopologicallyconsis-tentcontours,whilepreservingconvexityofthenega-tivespacewithineachcell.Thealgorithmdependsonacompositelook-uptablethatassociateseachsigncon-figurationwithacompactdecisiontreefordynamictri-angulationofisosurfacepatches.Thereasonfortheuseofadecisiontreeisthattheactualtriangulationde-pendsnotonlyonthesigns,butalsoonthemagnitudeofcornervalues.Thedecisiontreesarepre-computedtoensureaminimalnumberoftestsindeterminingeachtriangulation.

Thistechniquecanbeextendedwithoutdifficultytomulti-resolutioncontouring.Inmostmulti-resolutionapproaches,directapplicationofthecell-basedcontour-ingalgorithmtoagridofnon-uniformcellscanresultinsurfacecracks,i.e.discontinuitybetweeniso-surfacesgeneratedfromneighboringcellsatdifferentresolutions.Variousmulti-resolutionframeworkshavebeenproposedforcontouringonnon-uniformgrids[3],[8],[11],[12],[14],yettheyinvolvespecialcrack-patchingstrategies.Bloomenthal[2]proposesanadaptivecontouringmethodwhichrequiresrun-timefacetracingtomaintaincon-sistentcontoursforneighboringcells.Weshowthatbyconstructinglook-uptablesfortransitioncellsusingtheabovealgorithms,thesametable-drivencontouringmethodcanbeappliedtonon-uniformdatatogeneratecrack-freeisosurfaces.

Theremainderofthispaperisorganizedasfollows.Afterreviewingthetable-drivenMarchingCubesalgrorithm,wepresenttheconvexcontouringalgorithmonuniformgrids.Thenweexplaintheautomaticconstructionoflook-uptablesinmoredetail.Nextweextendthepro-

posedtechniquetonon-uniformgridstoproducecrack-freecontoursurfaces.Weconcludebydiscussingotherpossibleextensionsandapplications.

2MarchingCubesandLook-upTables

MarchingCubesisapopularalgorithmforextractingapolygonalcontourfromvolumetricdatasampledonauniform3Dgrid.Foreachcellonthegrid,theedgesintersectedwiththeiso-surfacearedetectedfromsignsatcellcorners.Thealgorithmthenformstrianglesbyconnectingintersectionsonthoseedges(referredtoasedgeintersectionshereafter).Tospeeduptheprocess,itusesalook-uptablethatestablishestriangulationsforeachsignconfiguration.Sincethereare8cornersinacell,thelook-uptablecontains256entries,fourofwhichareshowninfigure2.

Usingthelook-uptable,theMarchingCubesalgorithmcontoursacellintwosteps:

1.Lookupthetriangulationinthetablebythesignconfiguration,

2.Foreachtriangle,computetheexactlocationofeachvertex(edgeintersection)fromvaluesatthecellcor-nersbylinearinterpolation.TheMarchingCubesalgorithmisfastbecauseitusesta-blelook-uptobuildpolygonalcontours.Unfortunately,thecontouredsurfacegeneratedbytheoriginallook-uptablein[7]maycontainholes,sincethetriangularcon-tourwithineachcellisnotalwaysconsistentwiththatoftheneighboringcells(figure3).

Althoughthisproblemwasfixedinlaterwork,itre-vealsanotherdrawbackofmanuallycreatedtables.TheentriesintheMarchingCubes’look-uptablearecon-structedbyidentifying15topologicallydistinctsigncon-figurationsandtriangulatingeachcasebyhand.Thelackofautomationmakesitsusceptibletoerrorsanddiffi-culttoadapttootherpolyhedrons.Asweshallsee,thelook-uptablesusedinconvexcontouringareconstructedalgorithmicallybasedonthetopologyandgeometryofgivenpolyhedrons,andthereforeminimizespossibleer-rors.

ConvexContouringofVolumetricDataFig.3TwoadjacentcellscontouredusingtheMarchingCubesalgorithmthatproduceaninconsistenttopology.

3ConvexContouringUsingLook-upTablesThegoalofconvexcontouringistoextractpolygonalcontoursthatencloseconvexnegativespaceswithineachcell.Inthissection,wewillintroducetheconceptofcon-vexcontoursanddescribetheproposedpolygonizationtechniquebasedonapre-computedlook-uptable.Ex-amplesofconvexcontouringwillbepresentedtogetherwithperformancecomparisonwiththeMarchingCubesalgorithm.

3.1Convexcontour

Assumingthattheunderlyingimplicitfunctionistrilin-earinsideeachcell,theconvexhullofthenegativespaceinacellistheconvexhullofallnegativecellcornersandedgeintersections.Theconvexcontouristhepartofthisconvexhullthatliesinteriortothecell.In2D,forexam-ple,theconvexcontourconsistsofinteriorlinesegmentsconnectingedgeintersections(i.e.,dashedlinesinfig-ure1left).In3D,theconvexcontourconsistsofinteriortriangleswhoseverticesareedgeintersections(figure4left).Togetherwiththetrianglesthatfillthenegativeregionsoncellfaces(figure4right),theyconstitutetheconvexhullofthenegativespaceinsidethecell.

Fig.4Convexcontourontheconvexhullofthenegativespace.

Notethattheconvexcontourinacellisoutlinedbylinearconvexcontoursonthefacesofthecell(high-lightedinfigure4).Sincethelinearconvexcontourina

3

2Dsquareisuniquelydeterminedgiventhesignsatthe4corners(allowingmovementoftheedgeintersectionsalongtheedges),thepolygonalconvexcontoursfromneighboring3Dcellsalwayssharethesamelinearcon-touronthecommonface.Henceconvexcontoursalwaysformtopologicallyconsistentisosurfaces.

Infigure5,weshowtheconvexcontoursforthesamecellsfromfigure2.Incomparison,weobservethattheconvexcontouralwaysenclosesaconnected,convexneg-ativespacewithinthecell,whereasthecontourfromtheMarchingCubesalgorithmdoesnot.Notethataconvexcontourissometimescomposedofmultipleconnectedcomponents,asshownintherightmostcelloffigure5.Eachoftheseconnectedpieceofthecontouriscalledapatch,whichmaycontainmultipleholes(suchasthecenterleftcellinfigure5).Eachholeonthepatchissurroundedbyaringoflinearconvexcontoursthatcanbedetectedbythesignsatthecorners.Hencealook-uptableforpatchboundariescanbeconstructedautomat-icallyforeachsignconfiguration.

3.2TriangulationandDecisiontrees

Unfortunately,althoughtheboundaryofthepatchesontheconvexcontourisuniqueforeachsignconfiguration,theactualpolygonizationisnot.Infact,differentscalarvaluesatcellcorners,whichdeterminethelocationofedgeintersections,maymodifytheshapeoftheconvexhullandresultindifferenttriangulationoftheconvexcontour.Asillustratedinfigure6,twocellsthatsharethesamesignconfiguration,butwithdifferentscalarsatcellcorners,resultindifferenttriangulatedconvexcontours.

Fig.6Triangulationincellswithdifferentscalarvaluesatcorners.Edgeintersectionsareindictedbygraydots.

Todeterminethecorrecttriangulationbasedonthelo-cationofedgeintersections,onecouldapplyafull-scaleconvex-hullalgorithmtocomputetheconvexhullofthenegativespace.However,suchalgorithmsaretoogen-eralforourpurposes,sincewewantonlythepartofthisconvexhullthatliesinteriortothecell.Instead,wecantakeadvantageofthefactthatthetopologyoftheboundaryisknownforeachpatchontheconvexcontour.Infact,wecanconstructasetSofallpossibletriangu-lationsforeachpatch.Forexample,figure6showsthe

4TaoJuetal.

Fig.5Convexcontoursincellswithdifferentsignconfiguration.onlytwopossibletriangulationsfortheconvexcontourofthatsignconfiguration,sincethecontourcontainsasin-gle4-sidedpatch.AccordingtoEuler’spolygondivision

problem[6],thereare(2n−4)!

(n−1)!(n−2)!waystotriangulatean−sidedpatchinton−2triangles.Infact,thissizeofScanbefurtherreducedifwerealizethattheverticesofthesetrianglesarerestrictedtofixedcelledges,hencesometriangulationswillneverappearontheconvexhullofnegativespace.Wewilldiscussthisprocessindetailwhenwedescribehowthelook-uptableisconstructed.Nowwecanthinkofthetriangulationproblemasthefollowing:giventheexactlocationsoftheedgeinter-sections,chooseanappropriatetriangulationfromSsothatthetrianglessatisfytheconvexhullproperty(i.e.,alledgeintersectionsandnegativecornerslieononesideofthetriangle).Henceweneedafastmethodtodiffer-entiatethecorrecttriangulationfromothersbylookingattheedgeintersections.Assumingthattrianglesontheconvexcontourfaceinsidetheconvexhullofthenega-tivespace,wecandothisbythefollowing4-pointtest:givenfourdistinctedgeintersectionsV1,V2,V3,V4,ifV4liesonthefront-facingsideofthetriangle(V1,V2,V3),thentheinvertedtriangle(V1,V3,V2)doesnotbelongtotheconvexcontour(figure7left).Similarly,triangles(V1,V2,V4),(V2,V3,V4)and(V3,V1,V4)donotsatisfytheconvexhullproperty.Otherwise,bysymmetry,weclaimthattriangles(V1,V2,V3),(V1,V4,V2),(V2,V4,V3)and(V1,V3,V4)donotlieontheconvexcontour(figure7right).Notethatifallverticeslieonthesameplane,eitherchoicecanbemade.

V4V3V3V1V2V1V2V4

Fig.7Four-pointtestwithverticesV1,V2,V3,V4.

Each4-pointtestontheedgeintersectionsrulesoutthosefromthesetSofallpossibletriangulationsthatcontainanyofthefourback-facingtriangles.Sinceanytwotriangulationsdifferatleastinthetrianglessharedbyoneoftheboundaryedge,thecorrecttriangulationcanbedistinguishedfromeveryothertriangulationinS

throughappropriate4-pointtests.Forbestperformance,adecisiontreecanbebuilttodistinguisheachtriangula-tionthroughaminimalsetoftests.Anexampleofsuchadecisiontreeisshowninfigure8fora5-sidedpatch.Ateachnode,theremainingtriangulationsareshownandthe4-pointtestisrepresentedbyindicesofthefourvertices(theorderisshownatthetopleftcorner).Ifthefourthvertexliesonthefront-facingsideofthetriangleformedbythefirstthreevertices(inorder),wetaketheleftbranch.Otherwise,wefollowtherightbranch.Theprocessstopsataleafnode,whereasingletriangulationisleft.

213451,2,3,42,3,4,52,3,5,12,4,5,13,4,5,1Fig.8Adecisiontreeusing4-pointtestfor5-sidedpatches.

SincetheconstructionofdecisiontreesisbasedontheoriginalsetS,theycanbepre-computedandoptimizedforeverypatchineachsignconfiguration.Asweshallsee,themaximumdepthofallthesedecisiontreesis5andtheaveragetreedepthis1.88.Inotherwords,thecorrecttriangulationoftheconvexcontourinacubiccellcanbedeterminedbyperformingamaximumof5point-facetrialsontheedgeintersections,andonaveragenomorethan2trials.

3.3Thelook-uptable

Thelook-uptablecontains256entries,oneforeachsignconfigurationofacubiccell.Ineachentry,thelook-uptablestoresthedecisiontreescomputedforeachpatch

ConvexContouringofVolumetricData5

Fig.9Twoscreenshotsofareal-timenavigationapplicationusingaconvexlycontouredterrain.

bytraversingthenodesinthedecisiontreesinpre-order.Eachnon-leafnodecontainsa4-pointtest,andeachleafnodestoresatriangulation.Theedgeintersectionsin4-pointtestsandtriangulationsarerepresentedbyindicesoftheedgesonwhichtheylie.Twoexampleentriesinthistableareshownintable1,withtheircorrespond-ingsignconfigurationsandedgeindexingdrawnontheright.

thenegativespaceinsideeachnon-emptycellisconvex,collisiondetectioncanbelocalizedintocellsandthere-forebecomeindependentofthegridsize.Figure9showstwoscreenshotsofareal-timenavigationprograminwhichthemovementoftheviewerisconfinedwithinthenegativespace.Theterrainisaniso-surfaceconstructedusingconvexcontouringona256cubicgrid.Onacon-sumerlevelPCmachine(dual1.5GHzprocessorswith2.5Gmemory),weachievedover2millionpointclassifi-cationspersecond.

Aswementionedbefore,theaveragenumberoftestsusedtodeterminetriangulationforeachpatchislessthan2.Hencewecanperformconvexcontouringonvol-umetricdatawithspeedcomparabletotheMarchingCubesalgorithm.Intable2,theperformanceofcon-vexcontouringiscomparedwiththatoftheMarchingCubesforcontouringtheterraininfigure9ondiffer-entgridsizes.Wealsocomparedtheaveragenumberoftrianglesgeneratedineachcellinbothmethods.Noticethatconvexcontouringgeneratesonaverageonlyabout2%moretrianglesthantheMarchingCubesalgorithm.Theseextratrianglesareneededtopreservetheconvex-ityofthenegativespace.

3.4Contouringbytablelook-ups

IncomparisonwiththeMarchingCubesalgorithm,con-vexcontouringextractsthepolygonalcontourinacellintwosteps:

1.Lookupthedecisiontrees(oneforeachpatch)inthetablebythesignsatthecellcorners,

2.Foreachdecisiontree,perform4-pointtestsonspec-ifiededgeintersectionsuntilarrivingatasingletri-angulation.

GridSize128325635123

Avg.TrianglesFig.10Convexcontouringonvolumetricdata.

MarchingCubes125ms781ms2109ms3.181ConvexContouring141ms907ms2437ms3.257Table2ComparisonoftotalcontouringtimeandaveragenumberoftrianglespercellinconvexcontouringandtheMarchingCubes.

Infigure10,twosetsofvolumetricdatageneratedbyscan-conversionofpolygonalmodelsarecontouredus-ingthenewmethod.Observethattheedgesonthesur-facearemanifoldandthecontouriscrack-less.Since

6

IndexTableEntryCellConfiguration457132471

32

6910869108

1112TaoJuetal.

171

{1,9,12,7}→4-pointtest

{{1,9,7},{9,12,7}}→Triangulation{{1,9,12},{1,12,7}}

125

{1,3,6,12}→4-pointtestinparentnode{1,12,10,2}→4-pointtestinleftchild

{{1,3,12},{1,12,2},{3,6,12},{12,10,2}}{{1,3,12},{1,12,10},{1,10,2},{3,6,12}}{1,12,10,2}→4-pointtestinrightchild{{1,3,6},{1,6,12},{1,12,2},{12,10,2}}{{1,3,6},{1,6,12},{1,12,10},{1,10,2}}

5

1112Table1Twoexampleentriesinthelook-uptable.Eachentryisalistoftriangulations(eachstoredasalistoftriangles)and4-pointtests(eachstoredbytheindicesofthevertices)traversedfromthedecisiontreeinpre-roder.

4AutomaticConstructionofLook-upTablesInthissection,wewillreviewthetableconstructionpro-cessinmoredetail.Foragivensignconfiguration,wefirstdetectthepatchboundariesasagroupofringsoflinearcontours.Then,foreachpatch,weconstructthesetofallpossibletriangulationsthatcouldtakeplaceontheconvexhullofthenegativespace.Finally,anopti-maldecisiontreeisbuiltforeverypatchdetectedonthecontour.Thelook-uptablecanbefoundonthewebathttp://www.cs.rice.edu/jutao/research/contourtables/.

Fig.11Facetracingofasinglering.Solidarrowsrepresentlinearcontoursalreadybuilt,anddashedarrowsindicatethetracingroute.

4.1Detectionofpatchboundaries

Apatchontheconvexcontourinacubiccellisboundedbylinearconvexcontoursoncellfaces.Theselinearcon-toursformsingleormultipleringsthatsurroundthe”holes”ofthepatch.Sincethelinearconvexcontoursareuniqueoneachcellfaceforagivensignconfigura-tion,asingleringcanbeconstructedusingthefollowingtracingstrategy:startingfromacelledgethatexhibitsasignchange(whereanedgeintersectionisexpected)andfacingthepositiveend,lookforthenextedgewithasignchangebyturningcounter-clockwiseonthefaceboundary.Repeatthesearchprocessuntilitreturnstothestartingedge,whenaclosedringisformed(seefigure11).

Noticethatface-tracingproducesorientedlinearconvexcontoursoneachcellface.Eachlinearcontouronthecellfaceisdirectedsothatthenegativeregiononthatfaceliestoitsleftwhenlookingfromoutside.There-forethetrianglesontheconvexcontourofthecellthatsharetheselinearcontourswillfacetowardsthenega-tivespace.Theorientationoftheringsareimportantfor

determiningthesetofpossibletriangulationsthatsharethesamepatchboundary.

Similartracingtechniqueshavebeendescribedbynu-merousauthorsin[2],[9],[13],inwhichconvexityofthenegativeregiononeachcellfaceispreserved.Thesealgo-rithmsconstructasingleringforeachpatchboundary.However,theproblemremainsonhowtogroupmultipleringstoformtheboundaryofamultiple-genuspatch(suchasthecenterleftcellinfigure5).Althoughsuchpatchesariseinonly4casesamong256signconfigura-tions,theymayappearmuchmoreofteninothernon-cubiccells(suchastransitioncellsinmulti-resolutiongrids,seeSection6).Weneedtobeabletoidentifythesecasesautomaticallyfromthesignconfigurationandgrouptheringsappropriately.

Bydefinition,apatchisacontinuouspieceonthecon-vexhullofnegativespace.Henceitalsoprojectsontoacontinuouspieceofregionsonthecellfaces.Theseregionsarepositiveareasthatsurroundpositivecor-

ConvexContouringofVolumetricDatanersconnectedbycelledges.Thereforetheboundaryofeachpatchontheconvexcontourisolatesagroupofpositivecornersthatareinter-connectedbycelledges.Thepreviousface-tracingalgorithmcouldbemodifiedsothatringsconstructedaroundasameedge-connectedcomponentofpositivecornersaregroupedtoformtheboundaryofasinglepatch.Thisruleisdemonstratedinfigure12.Inthetopleftcell,tworingsoflinearcontoursformtheboundaryoftwopatches,duetothepresenceoftwoisolatedpositivecorners.Inthetoprightcell,wherethereisonlyoneedge-connectedcomponentofpositivecorners,thetworingsaregroupedtoformthebound-aryofasinglecylinder-likepatch.Theconnectivityofthepositivecornersinthesetwocellsareillustratedatthebottomoffigure12.Incontrast,face-tracingwithoutring-groupingwouldgivethesameresultinbothcells,thusviolatingtheconvexhullpropertyinthesecondcell.

Fig.12Top:Groupingofringsoflinearcontours(high-lighted)toformboundariesofpatches.Positivecornersarecoloredgray.Bottom:Connectivitygraphofpositivecorners

4.2Pre-triangulationofConvexContour

Thesetofpossibletriangulationsforapatchwithanorientedboundarytopologycanbeenumeratedbyre-cursivealgorithms.However,thisoftenresultsinredun-danttriangulationsthatneverappearontheconvexcon-tour.Forexample,thegenus-2patchinthecenterleftcellinfigure5canbetriangulatedinonlyonewayontheconvexhullofthenegativespace,regardlessofthemagnitudesofscalarvaluesatthecorners.Incontrast,brute-forceenumerationwouldreturn21possibletrian-gulationsforanarbitrarygenus-2patchwithtwotrian-gularholes.Thekeyobservationisthat,thepatchesontheconvexcontourarenotarbitrarypatches,theirver-tices(edgeintersections)arerestrictedtofixededgeson

7

thecell.Thesespacialrestrictionslimitthenumberofpossibletriangulationsthatcouldoccurontheconvexcontour.Forfastpolygonizationatrun-time,wehopetopre-triangulateeachpatchasmuchaspossibleduringtableconstruction,basedonlyonthesignconfiguration.Bytheconvexhullproperty,thehalf-spaceonthefront-facingsideofatriangleontheconvexcontourmustcon-tain(orpartiallycontain)everyothercelledgethatex-hibitsasignchange.Notethatthethreeverticesofthetrianglecanmoveonlyalongthreefixedcelledges,thishalf-spaceisalwayscontainedintheunionofthehalf-spacesformedwhenthethreeverticesareattheendsoftheircelledges.Hencewehaveawaytoidentifytrianglesthatwillnotappearontheconvexcontour:giventhreecelledges(C1,C2),(C3,C4)and(C5,C6)(Ciarecellcor-ners),constructbordertriangles,i.e.,trianglesformedbyoneendofeachedgeinorder(suchas(C1,C3,C5)).Ifthereisanedgeonthecellexhibitingasignchangethatliescompletelytothebackofallnon-degeneratebordertriangles,anytrianglewhoseverticesbelongtothesethreeedges(inorder)willnotlieontheconvexcon-tour.Thisideaisillustratedinfigure13.Thehighlightedcelledgeontheleftexhibitsasignchange,andliestothebackofallthebordertrianglesconstructedfromthethreedashededges(E1,E2,E3).Hencethedashedtrian-gleformedbyintersectionsonthoseedgesneverappearsontheconvexcontour.Incontrast,thehighlightedcelledgeontherightliespartiallytothefrontofatleastoneofthebordertrianglesformedbytheedges(E1,E2,E3),hencethedashedtrianglemayexistinthetriangulationoftheconvexcontour.

E1

E1

E3

E2

E2

E3

Fig.13Identifyingtrianglesthatdonotlieontheconvexcontour.

Byeliminatingtriangulationsthatcontaintheseineli-gibletriangles,wecantrimdownthespaceofpossibletriangulations.Forexample,thenumberofremainingtriangulationsforthefirstthreecellsinfigure5arere-spectively4,1and4.

4.3Constructionofdecisiontrees

Evenafterpre-triangulation,somepatchesstillhavemanypotentialtriangulationsontheconvexhullofthenega-tivespace.Tospeedupthepolygonizationatrun-time,

8wecanpre-computeasetof4-pointtestsontheverticesofthepatch(edgeintersections)todistinguishbetweentheremainingtriangulations.Thesetestscanbeorga-nizedinadecisiontreestructure,introducedinthelastsection.Differentsetsoftestsresultindifferentlyshapeddecisiontrees.Toobtainoptimalperformance,weimple-mentasearchalgorithmthatlooksfortheoptimalsetofteststhatproducesadecisiontreewiththesmall-estdepth.Sinceeachofthetwooutcomesofasingletesteliminatesanon-intersectingsubsetoftheremain-ingtriangulations,theminimaldepthofthecorrespond-ingdecisiontreeislowerboundedbylog2N,whereNisthetotalnumberoftriangulations.Forexample,thedepthofanoptimizeddecisiontreeforapatchoflength4,5and6are1,3and5respectively.Furthercomputa-tionrevealsthatthemaximumlengthofapatch(whichcannotbepre-triangulated)inacubiccellis6;henceanypatchcanbetriangulatedwithin5point-facetrialsontheflybywalkingdownthepre-computeddecisiontree.Onaverage,however,itonlytakes1.88teststode-terminethetriangulationofapatch,duetoinfrequentoccurrenceoflargepatchesandthereducedtriangula-tionspaceasaresultofpre-triangulation.

5Multi-resolutionConvexContouring

Involumevisualization,thenumberofpolygonsgener-atedbyuniformcontouringeasilyexceedsthecapacityofmodernhardware.Forreal-timeapplications,itisoftenadvantageoustodisplaythegeometryatdifferentlev-elsofdetaildependingonthedistancefromtheviewer.Thistechniquehastheadvantagethatitspeedsuptherenderingprocesswithoutsacrificingmuchvisualaccu-racy.Byusingaview-dependentapproach,thegridiscontouredatdifferentresolutionsdependingonthedis-tancefromthenavigator.Inparticular,wecancreateaseriesofnestedboundingboxescenteredattheviewer,withthegridresolutiondecreasingbyafactorof2.A2Dexampleofthismulti-resolutionframeworkisshowninfigure14left,inwhichacircleiscontouredusingcellgridattwodifferentresolutions.Whenthecoarsecellsatthetopmeetthefinecellsatthebottom,thecon-tourinthecoarsecellsneedtobeconsistentwiththecontourfromtheneighboringfinecellsonthecommonedges.Wecallthesecoarsecellstransitioncells,whichareadjacenttocellsatafinerresolution.A2Dtransitioncellthushasfivecornersandfiveedges,asshowninthemiddleoffigure14.Byconnectingedgeintersectionsoneachcelledge,thetransitioncellscanbecontouredinawaysimilartoaregular4-cornercell,yieldingconsistentcontourswiththeadjacentfinecells.Someofthecon-touredexampleareshowninfigure14right.Noticethattheconvexityofthenegativeregionisstillpreservedineachtransitioncell.

TaoJuetal.

In3D,atransitioncellbetweentworesolutionsiseitheradjacenttotwofinecellsonanedge,oradjacenttofourfinecellsonaface(seefigure15left).Thesetwotypesofcellscanberegardedasconvexpolyhedronswith9corners(figure15center)and13corners(figure15right)respectively.

Sincethepreviousdiscussiononregularcellsappliestoanyconvexpolyhedron,wecanalsobuildlook-upta-blesandperformconvexcontouringonthesetransitioncells.Inthisway,crack-freesurfacescanbecontouredonnestedgridswithinthesameframeworkasuniformcontouring.

5.1Convexcontoursintransitioncells

Asinaregularcell,theconvexcontourinsideatran-sitioncellisoutlinedbythelinearcontoursonthecellfaces.Sincethelinearconvexcontourisuniqueoneachfaceforagivensignconfiguration,theboundaryofpatchesontheconvexcontourcanbepre-computedusingtheproposedface-tracingalgorithm.Atthetopoffigure16,theorientedboundariesofpatchesindifferenttransitioncellsaredetectedanddrawnasdashedarrows.Sincecon-vexcontoursfromneighboringcellsinamulti-resolutiongridalwayssharethesamelinearcontouronthecom-monfaceastheirboundaries,topologicalconsistencyispreservedeverywhereonthecontouredsurface.

Fig.16Patchboundaries(top)andtriangulation(bottom)inthreetransitioncells.

Bypre-computingoptimaldecisiontreesforeachpatch,thetriangulationcanbedeterminedbyapplyingsucces-sive4-pointtestsontheedgeintersections.Atthebot-tomoffigure16,patchesdetectedfromthecellsonthetoparetriangulatedontheconvexhullofthenegativespace.However,duetothepresenceoffourco-planarfacesona13-cornercell,thisconvexhullcoulddegener-ateontoaplane(figure17left).Todeterminethecorrecttriangulationoftheconvexcontouronthedegenerateconvexhull,weintroduceanoutwardperturbationto

ConvexContouringofVolumetricData9

Fig.14Acirclecontouredona2Dmulti-resolutiongrid(left),consistingofregularcellsandtransitioncells(middle).Examplecontoursinatransitioncellareshownontheright.Positivecornersarecoloredgray,andnegativecornersarecoloredblack.

Fig.15Transitioncellsonnestedgrids:9-cornercell(inthemiddle)with6facesand13-cornercell(ontheright)with9faces.Theirpositionsinthenestedgridsareillustratedontheleft.

Fig.17Perturbingcellcornersonco-planarfaces.Thepatchboundaryisoutlinedbyhighlightedlines.

thecellcornersoftheco-planarfacessothattheynolongerlieonthesameplane(figure17right).Sincetheperturbationsaresmallandperpendiculartotheplanethatcontainsthosefaces,thetrianglesonthedegenerateconvexhullstillformsaconvexhullafterperturbation.Thereforethe4-pointtestsonedgeintersectionsthatalllieonthatplanewillinsteadbeappliedtothenewedgeintersectionscomputedfromtheperturbedcellcorners.Sincethefinaltriangulationdeterminedbytheseteststakeplaceontheunperturbedgeometry,thepatchesarestillboundedbythelinearcontoursoncellfacesandtopologicalconsistencyispreserved.

tioncellshavemorecomplicatedtopologythatresultsinlargerpatchesandmorepossibletriangulations.Eachentryinthelook-uptablecorrespondstoasignconfigu-rationatthecellcorners.Forthe9-cornercell,thetableconsistsof29=512entries,andthelook-uptableforthe13-cornercellconsistsof213=8192entries.Eachentrystorescompactdecisiontreesforeachpatchinthesameformatasdescribedintheuniformcase.Theresultingdecisiontreeshavemaximumdepthof5ina9-cornercell,and14ina13-cornercell.Onaverage,however,itonlytakes1.92teststodeterminethetriangulationofapatchina9-cornercell,and4.76testsina13-cornercell.Thelook-uptablescanalsobefoundonthewebathttp://www.cs.rice.edu/jutao/research/contourtables/.5.3Multi-resolutioncontouring

Convexcontouringofacellonanestedgridproceedsinexactlythesamewayasonauniformgrid.Theonlynoticeabledifferencesarethedifferentlook-uptablestousefordifferenttypeofcells,andappropriatepertur-bationstobeappliedwhenthefourpointsinthetestlieontheco-planarfacesonthe13-cornercell.There-forecontouringonuniformandmulti-resolutiongridscanbeimplementedwithinthesameframework.Thepre-computedlook-uptablesguaranteetheconsistencyofthesurface,thereforenocrack-fillingiseverneeded.Infigure18,thesamedragonmodeliscontouredusingdifferentlynestedgrids.Notethatbydecreasingthereso-lutionofthegridasthedistancefromtheviewer(drawn

5.2Look-uptables

Thelook-uptablesareconstructedinthesamewayasforuniformcells,exceptforthefactthatthetransi-

10TaoJuetal.

Fig.18Multi-resolutioncontouringonthedragonat2563resolutionusingdifferentlynestedgrids:uniformgrid(left),two-levelgrids(middle),andthree-levelgrids(right).

asagraysphereinthemiddle)increases,muchfewertrianglesaregeneratedwhilemostofthevisualdetailsarepreservedfromtheviewer’sperspective.Thecorre-spondingcontouringtimeandtotalnumberoftrianglesgeneratedineachexamplearesummarizedintable3.

Uniform13466800269,392219ms

2-level6779711687137,558109ms

3-level241485287750,79247ms

Regularcells9-vertexcells13-vertexcellsTrianglesTime

Table3Comparisonofperformanceofmulti-resolutioncon-touringforthethreeexamplesinfigure18.

Observeintable3thatthemajorityofthecellsinamulti-resolutiongridareregularcells,thereforetheper-formanceofthealgorithmisstilldominatedbyuni-formcontouring.Infact,forinteractiveapplications,onecouldpre-computethecontourofamodelonuniformgridsindifferentresolutions,andonlyprocessthetran-sitioncellsinrealtimeasthepositionofthenestedgridschangewiththeviewer.Inthisway,theusercannavi-gatearoundacomplicatedobjectinaninteractivespeed,asseeninfigure19.Thetabledrivenpatchdetectionandtriangulationprovidesfastcrack-lesscontouringofbothregularcellsandtransitioncells.

Fig.19Multi-resolutioncontouringontheHappyBuddhawithdifferentviewerpositions.

6Conclusion

Inthispaper,wepresentedatable-drivencontouringmethodthatproducestopologicallyconsistentsurfaceswithalocalconvexityproperty.Thepolygonalcontourinsideeachcellenclosesaconvexnegativespace,whichenablesfastcollisiondetectiononthecontouredsur-face.Theconstructionofcontoursisgreatlyacceleratedviatablelook-upoftriangulationfromthesignsandmagnitudesofcornervalues.Wealsoshowedhowthismethodcouldbeusedtoperformcrack-freecontouringonmulti-resolutiongrids.Byconstructinglook-uptables

fortransitioncells,convexcontouringofbothuniformandmulti-resolutiongridscanbeimplementedwithinasingleunifiedframework.Infact,convexcontoursarealsodefinedforarbitraryconvexpolyhedrons,suchassquarepyramidsandtetrahedrons.Hencethesametech-niqueproposedherecanbeusedtoconstructlook-upta-blesformorecomplexshapes.Thelook-uptablesforuni-formcellsandtransitioncellsinmulti-resolutiongridsarealsoavailableontheweb.

References

1.H.H.Baker(1989).BuildingSurfacesofEvolution:TheWeavingWall.InternationalJournalofComputerVi-sion,3:51-71.

2.J.Bloomenthal(1988).PolygonizationofImplicitSur-faces.ComputerAidedGeometricDesign,5:341-355.

ConvexContouringofVolumetricData

3.I.BoadaandI.Navazo(2001).MultiresolutionIsosurfaceFittingusinganOctreebasedSurfaceHierachy.ResearchReportIIiA01-02-RR,InstitutInform‘aticaiAplica-cions,UniversityofGirona.

4.M.J.Duurst(1988).AdditionalReferencetoMarchingCubes.ComputerGraphics,22(2):72-73.

5.A.VanGelderandJ.Wilhelms(1994).TopologicalCon-siderationsinIsosurfaceGeneration.ACMTransactionsonGraphics,13(4):337-375.

6.R.K.Guy(1958).DissectingaPolygonIntoTriangles.BulletinMalayanMath.Society,5:57-60.

7.W.LorensenandH.Cline(1987).MarchingCubes:AHighResolution3DSurfaceConstructionAlgorithm.ComputerGraphics(SIGGRAPH’87),21(4):163-1698.H.MullerandM.Stark(1993).AdaptiveGenerationofSurfacesinVolumeData.TheVisualComputer,9(4):182-199.

9.G.M.NielsonandB.Hamann(1991).TheAsymptoticDecider:ResolvingtheAmbiguityinMarchingCubes.ProceedingsofIEEEVisualization91,83-91.

10.P.NingandJ.Bloomenthal(1993).AnEvaluationofIm-plicitSurfaceTiles.IEEEComputerGraphics&Appli-cations,13(6):33-41.

11.T.Poston,T.T.WongandP.A.Heng(1998).Multires-olutionIsosurfaceExtractionwithAdaptiveSkeletonClimbing.ComputerGraphicsForum,17(3):137-148.12.R.Shekhar,E.Fayyad,R.Yagel,andJ.F.Cornhil

(1996).Octree-basedDecimationofMarchingCubesSurfaces.IEEEVisualization’96:335-344.

13.A.Wallin(1991).ConstructingIsosurfacesfromCT

Data.IEEEComputerGraphicsandApplications,11(6):28-33.

14.R.Westermann,L.Kobbelt,andT.Ertl(1999).Real–

TimeExplorationofRegularVolumeDatabyAdap-tiveReconstructionofIsosurfaces.TheVisualComputer,15:100-111.

11