We present an algorithm for the efficient and accurate computation of geodesic distance fields on triangle meshes. We generalize the algorithm originally proposed by Surazhsky et al. [1]. While the original algorithm is able to compute geodesic distances t
AccurateComputationofGeodesicDistanceFieldsforPolygonalCurves
onTriangleMeshes
DavidBommes,LeifKobbeltComputerGraphicsGroup,RWTHAachenEmail:{bommes,kobbelt}@cs.rwth-aachen.de
Abstract
Wepresentanalgorithmfortheef cientandaccu-ratecomputationofgeodesicdistance eldsontri-anglemeshes.Wegeneralizethealgorithmorig-inallyproposedbySurazhskyetal.[1].Whiletheoriginalalgorithmisabletocomputegeodesicdistancestoisolatedpointsonthemeshonly,ourgeneralizationcanhandlearbitrary,possiblyopen,polygonsonthemeshtode nethezerosetofthedistance eld.Ourextensionsintegratenaturallyintothebasealgorithmandconsequentlymaintainallitsniceproperties.
Formostgeometryprocessingalgorithms,theexactgeodesicdistanceinformationissampledatthemeshverticesandtheresultingpiecewiselin-earinterpolantisusedasanapproximationtothetruedistance eld.Thequalityofthisapproxima-tionstronglydependsonthestructureofthemeshandthelocationofthemedialaxisofthedistance eld.Henceoursecondcontributionisasimpleadaptivere nementscheme,whichinsertsnewver-ticesatcriticallocationsonthemeshsuchthatthe nalpiecewiselinearinterpolantisguaranteedtobeafaithfulapproximationtothetruegeodesicdis-tance eld.
Figure1:Theisolinesofthegeodesicdistance eldwithrespecttotheboundariesofthecarmodelarevisualized.
gationschemestendtobecomenumericallyunsta-bleonnot-so-nicemeshesastheyoftenoccurinpracticalapplications.Moreover,sincetheyusethesamemeshasarepresentationfortheinputgeom-etryaswellasthedistance eld,theprecisionislimitedbythemeshresolution.Surazhskyetal.[1]presentapracticalimplementationofthegeodesicdistancealgorithmofMitchelletal.[2].Thiswasthe rsttimethatanexactgeodesicdistancecom-putationhasbecomeapplicabletoarbitraryinputmeshesofpracticallyrelevantcomplexities.How-ever,inthisalgorithm,thedistancecomputationisinitializedbyoneormoreisolatedpointsonthemeshandthedistanceispropagatedfromthem(inSection3wepresentasummaryofthisalgorithm).Unfortunately,formanypracticalapplicationsthisistoorestricted.Ingeneralonewouldliketobeabletocomputethegeodesicdistancewithrespecttoacurveonthesurface,i.e.,apolygononthemeshsincethisallowsustotakearbitraryboundarycon-ditionsintoaccount.SeeFig.1foranexample.
1Introduction
Thecomputationofgeodesicdistancesonatrianglemeshhasmanyapplicationsingeometryprocess-ing,rangingfromsegmentationandlowdistortionparametrizationtomotionplanningandtoolpathoptimization.Inmostcasesthetruegeodesicdis-tance eldisapproximatedbysomefastmarchingmethodwhichleadstoacceptableresultsonnicelystructuredmeshesandawayfromsingularitiesofthedistancefunction.However,suchsimple

propa-VMV2007
H.P.A.Lensch,B.Rosenhahn,H.-P.Seidel,P.Slusallek,J.Weickert(Editors)
Geodesic Bézier Curves ... 8页 免费 Accurate Computation of ... 暂无...1.2 Notation and Preliminary De?nitions A polygonal line Γ on a triangle...
. . . . On-the-?y curve-skeleton computation...y, both from point clouds and polygonal meshes....Sato. Penalized-distance volumetric skeleton ...
. . . . On-the-?y curve-skeleton computation...y, both from point clouds and polygonal meshes....Sato. Penalized-distance volumetric skeleton ...
热门文档