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
2Previouswork
Inthispaperweaddresstwoelementarymeshoper-ations,geodesicdistancecomputationandadaptivere nement.
Dijkstra’salgorithmforcomputingshortestpathsalongedgescanbeusedasanapproximationforthegeodesic eld.Lanthieretal.[3]improvedtheinitialpoorresultsbyaddingmanyextraedgestothemesh.
KimmelandSethian[4]adaptedthefastmarchingmethodtocomputecloserapproximationsofgeodesicdistances.Onwell-shapedinputmeshesthismethodperformsverygood,butinthecaseofobtuseanglesorneedletrianglesevenimprovedupdaterulesandspecialhandlingasproposedbe-fore[5,6,7]canleadtolargeerrors.Fastmarchingalgorithmsareabletoapproximatethegeodesicdistance eldinducedbypolygonalsources,butthequalitystronglydependsonthemeshstructurenearthemedialaxis,whichistypicallynotsuitedtorepresentthegeodesic eld,asweshowinthispaper.
ThemostfamousexactalgorithmwasdevelopedbyMitchelletal.[2]in1987andthe rstpracticalimplementationwasproposedeighteenyearslaterbySurazhskyetal.[1].TheyshowedthattheworstcasecomplexityofO(n2logn)isquitepessimisticandinpracticetheaverageisclosetoO(n1.5)whichmakesthealgorithmpracticalforcommonmodelcomplexities.Detailsofthisalgorithmarepresentedinthenextsection.Theyalsointroduceamergingoperationtodesignanapproximationalgorithmwithguaranteederrorbounds.Liuetal.[8]studiedarobustimplementationstrategywhichhandlesalldegeneratecasesthatoccurinrealworlddata.Inthispaperwewillgeneralizethisexactandapproximatealgorithmfrompointsourcestoarbitrarysourcepolygons.
Inthecontextofadaptivemeshre nementtwocommontechniques,triangulations[10][11]and√namelyred-green-leadtoregular√structuresandpreservethetrianglequal-ity.
iscomposedofone-to-threetrianglesplitsandedge ipswhichchangesnotonlythetessellationbutalsothegeometry(andhencethegeodesicdistance eld)ofatrianglemeshandisthusnotsuitedforourapplication.

x

(a)(b)
Figure2:(a)Startingonthepointsourcesa(shaded)pencilofraysispropagatedthroughthreeunfoldedtrianglesalongofstraightlines.Eachwin-dowishighlightedbyanarcwhichisalwaysontheedgesidepointingtothesource.(b)Anedgealignedtwodimensionalcoordinatesystemisusedtocomputenewwindowswhichareinducedfromwindoww.
Atthecoreofred-green-triangulationsistheone-to-fourtrianglesplit.Redandgreentagsareusedtopreserveconsistency.There nementconservestheoriginalgeometryandcouldbeintegratedintoourframework.Howeverforourapplicationasimplerandmorelocalre nementispossiblewhichweproposeinsection6.
3Theexactgeodesicalgorithm
Sinceouralgorithmisanextensionof[1]webrie yexplainthebasicprinciplesandtheresultingbasealgorithm.
Intheplane,thegeodesicdistancecoincideswiththeEuclideandistance.Hence,withrespecttoanisolatedpoint,itisthesquarerootofaquadraticfunction.Onatrianglemesh,i.e.onapiecewiseplanarsurface,thegeodesicdistancewithrespecttoapointturnsouttobeapiecewisefunctionwhereineachsegmentthedistanceisgivenbythesquarerootofaquadraticfunctionplusanoptionalconstantoffset.Thisoffsethastobeintroducedtoproperlyhandlesaddlepointsonthesurface.Thecentralideaofthealgorithm[1]istoprop-agateexactdistanceinformationfromonetriangletoitsneighborswithaDijkstra-typealgorithm.Thekeyobservationisthatitissuf cienttostorethepiecewisedistancefunctionontheedgesofthetri-
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 ...
热门文档