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




(a)(b)(c)(d)
Figure3:(a)Thegeodesicdistance eldw.r.tpointpiscomputedonacapconsistingoftrianglesA,B,andC.(b)Cuttingalongtheedgeunfoldsthecapisometricallyandenablesthedistancepropagation
intheplanethroughwindowsw1andw2.(c)Thetemporarilypropagatedwindowsv1andv2overlapinthemiddleregion.(d)The nalwindowsv1andv2areproperlycuttorepresentthepiecewisegeodesicdistancealongtheedge.
anglemeshsincethisissuf cientforthepropaga-tionandalsofortheexactevaluationofdistanceseverywhereonthesurface.
Foreachedgeofthemeshthealgorithmmain-tainsalistofsegments,so-calledwindows.Eachwindowde nesthegeodesicdistance eldwithinapencilofrayscoveringbothneighboringtriangles(seeFigure2).Whendistanceinformationisprop-agatedacrossatriangle,the(incoming)windowshavetobemappedtotheoppositeside.Thepropa-gationincludestheproperintersectionofwindows,becauseunliketheplanarcaseonasurfaceprop-agatedwindowscanoverlap.Sincethedistancefunctioniscontinuous,theintersectionrequiresto ndthepointwherethedistancefunctionvaluesinbothwindowsareidentical.
Weillustratetheprocedurewithasimpleexam-ple.ThecapofFigure3(a)consistsofthreeisosce-lestrianglesA,BandC.Nowwewanttocomputethegeodesicdistance eldw.r.tthepointp.SincepiscoplanarwiththetrianglesAandBtheyarecoveredwithapencilofraysemanatingfrompthroughsinglewindowsw1andw2.Topropagatethedistanceinformationthroughw1andw2wecutthecapalongtheedgeconnectingpandqandun-foldthetrianglesisometricallyintotheplane,i.e.alledgelengthsandanglesofthetrianglesarepre-served(see3(b)).Inthissettingpisdoubledintoplandpr.Nowwearereadytopropagatethepen-cilofraysde nedbyw1andw2acrosstriangleCandcreatenewtemporarilyoverlappingwindows v1andv2depictedinFigure3(c).Evaluatingthedistancesinducedbybothpencilsofraysthewin-dowscanbeintersectedandproperlycutto nal
windowsv1andv2(seeFigure3(d))whichcor-rectlyrepresentthecontinuouspiecewisegeodesicdistancefunctionalongtheedge.
Anicefeatureofthiswindowformulationisthatallcomputationscanbeformulatedinlocaltwodi-mensionalcoordinates,i.e.onlythemeshtopologyandscalaredgelengthsarerequired.Theneces-saryconditionforthisedgebasedalgorithmisthatgeodesicpathscanonlypassthroughverticeswithatotalanglegreaterorequalthan2π,i.e.saddlesand atpoints.ThisresultwasprovenbyMitchelletal.in[2].Saddlepointsandconcaveboundarypointsactaspseudosourceswhichgenerateaddi-tionalnewwindowscoveringthegeometricshadowofthelocallyexpandedsurface.
3.1Basealgorithm
At rstallsourcewindowsintheimmediatevicin-ityofsourcepointsarecreatedandpushedintoapriorityqueuepreferringshorterdistances,becausewewanttocomputetheminimalgeodesicdistance.Noticethatingeneraltheresultisindependentofthepropagationorderbutthepriorityqueueen-suresthatwindowsarepropagatedasawavefrontwhichgivesastrongspeedupandmakestheal-gorithmpractical.Workingoffthequeuethecur-rentwindowisalwayspropagatedintothenextun-foldedtriangle,wherenewwindowsarecreated(seeFigure2).Whenthefrontreachessaddleorboundaryverticesnewsourcewindowsareadded.Allnewwindowscanoverlapwithalreadyexist-ingwindowsandmustbeintersectedaccordingly.Thealgorithmterminateswhenalledgesareparti-
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 ...
热门文档