Abstract-Defining-Point-Set-Surfaces

DefiningPoint-SetSurfacesNinaAmenta∗UniversityofCaliforniaatDavisYongJooKil†UniversityofCaliforniaatDavisAbstractTheMLSsurface[Levin2003],usedformodelingandrenderingwithpointclouds,wasoriginallydefinedalgorithmicallyastheout-putofaparticularmeshlessconstruction.Wegiveanewexplicitdefinitionintermsofthecriticalpointsofanenergyfunctiononlinesdeterminedbyavectorfield.Thisdefinitionrevealsconnec-tionstoresearchincomputervisionandcomputationaltopology.VariantsoftheMLSsurfacecanbecreatedbyvaryingthevectorfieldandtheenergyfunction.Asanexample,wedefineasimi-larsurfacedeterminedbyacloudofsurfels(pointsequippedwithnormals),ratherthanpoints.WealsoobservethatsomeproceduresdescribedintheliteraturetotakepointsinspaceontotheMLSsurfacefailtodoso,andwedescribeasimpleiterativeprocedurewhichdoes.1IntroductionBecauseofimprovedtechnologiesforcapturingpointsfromthesurfacesofrealobjectsandbecauseimprovementsingraphicshard-warenowallowustohandlelargenumbersofprimitives,modelingsurfaceswithcloudsofpointsisbecomingfeasible.Thisisin-teresting,sinceconstructingmeshesandmaintainingthemthroughdeformationsrequiresalotofcomputation.Itisusefultobeabletodefineatwo-dimensionalsurfaceimpliedbyapointcloud.Suchpoint-setsurfacesareusedforinterpolation,shading,meshingandsoon.DavidLevin’sMLSsurface[Levin2003]hasprovedtobeaveryusefulexampleofapoint-setsurface.LevindefinedtheMLSsur-faceasthestationarypointsofamapf,sothatxbelongstotheMLSsurfaceexactlywhenf(x)=x.Thisdefinitionisusefulbutitdoesnotgivemuchinsightintothepropertiesofthesurface.InSection2wegiveamoreexplicitdefinitionoftheMLSsur-face,basedonanenergyfunctioneandanvectorfieldn.Changingeandnproduceothersimilarsurfaces;wecallthemall,includingtheMLSsurface,extremalsurfaces.AswediscussinSection4,extremalsurfacesarenotnew.ThenameisadoptedfromMedioniandco-authors[2000],whousedthemforsurfaceextractionfromverynoisypointclouds,amongotherapplicationsincomputervision.TheirdefinitionhastobeextendedslightlyinordertoincludetheMLSsurface,buttheideaisessentiallythesame.EdelsbrunnerandHarer[toappear]haverecentlydescribedJacobisurfaces,whicharealsocloselyrelatedandwhichhavestrongermathematicalproperties.AdamsonandAlexa[2003a]describeanimplicitsurfacewhichisauseful“relative”oftheMLSsurface.Thisraisesthequestionof∗SupportedbyNSFACI-0325934,CCR-0098169,andCCR-0093378.e-mail:[e-mail]†SupportedbyNSFCCR-0093378.e-mail:[e-mail]5,thereisanimplicitsurfacecontainingeveryextremalsurface,includingtheMLSsurface.Thiscanbequiteuseful,particularlyfordefiningnormalsprecisely.Figure1:Anexampleofanextremalpoint-setsurfacewhichtakessurfels,ratherthanpointsasinput.Thesparseandnon-uniformlydistributedsetofweightedsurfelsontheleftimpliesthesurfaceontheright.Asanexampleofanotherextremalsurfaceconstruction,wedescribeinSection7apoint-setsurfaceforsurfels,inputpointsequippedwithnormals.Normalsareavailablewhenconvertingamodelfromameshorimplicitsurfacetoapointcloud,andtheyaregenerallycomputedaspartoftheprocessofcleaninguppointcloudsproducedbylaserrangescannersorother3Dcapturetech-nologies.Figure1showsanexampleofourpoint-setsurfaceforsurfels.MLSsurfaceshavebeenusedwidelyinthelastfewyears.Theseminalgraphicspaper[Alexaetal.2003]usingtheMLSsurfaceforpoint-setmodelingandrenderingwasfollowedbyworkonpro-gressiveMLSsurfaces[Fleishmanetal.2003],ray-tracing[Adam-sonandAlexa2003b],andsurfacereconstruction[Xieetal.2003;Mederosetal.2003].TheMLSsurfaceisusedinseveralfeaturesofPointShop3D,anexcellentopen-sourcepoint-cloudmanipula-tiontool[Zwickeretal.2002;Paulyetal.2003].WehaveusedPointShopasourimplementationplatform.Thesepapersdescribetwoslightlydifferentproceduresfortak-ingapointxintheneighborhoodofthepointcloudontotheMLSsurface,onewhichfirstappearedinanearlier,widelycirculatedmanuscriptversionofLevin’spaper,andamoreefficient“linear”versionusedinPointShop.NeitherprocedureactuallyproducesapointoftheMLSsurface.Wegiveasimpleprocedurewhichdoes,togetherwithashortproof,inSection6,andwediscussthethe-oreticalproblemswiththeearlierproceduresinAppendixA.ThefinalversionofLevin’spaperontheMLSsurface[Levin2003](currentlyavailableonhisWebsite)containsanewprojectionpro-cedure,differentfromours,whichalsoproducespointsonthesur-face.2SurfacedefinitionWebeginwiththenow-standarddefinitionoftheMLSsurface,givenintheearlymanuscriptofLevin’spaperandusedinava-rietyofcontextsasmentionedabove.TheMLSsurfaceforapointcloudP⊆IR3isdefinedasthesetofstationarypointsofacertainfunctionf:IR3→IR3.Anoptionalpolynomialfittingstep,whichweomithere,canbeappliedafterthemapf.artHx=r+taFigure2:TheMLSenergyfunctioneMLS(~a,t)sumsuptheweighteddistancesfromthefixedinputpointsinPtotheplanewithnormal~athroughthepointx=r+~at.Theweightonaninputpointpi∈P,denotedherebyitsshadeofgrey,isafunctionofthedistancefrompitox.GivenaninputpointcloudPandapointrinaneighborhoodofP,theenergyoftheplanewithnormal~apassingthroughthepointx=r+t~a,wheretisthedistancefromptotheplane,isdefinedtobe:eMLS(~a,t)=∑pi∈P(h~a,pii−h~a,p+t~ai)2θ(p+t~a,pi)wheretheweigh