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
tionedbytheminimalgeodesicdistancewindows,i.e.whenthequeueisempty.Thepseudocodeal-gorithmispresentedbelowandallnecessarycom-putationsareexplainedinmoredetailinthenextsections.
Algorithm1ExactGeodesicFieldPQueue.add(sourceWs)repeatcurW=PQueue.popFront()newWs=propagate(curW)
newWs+=saddleAndBoundaryWs(curW)newWs=intersect(newWs,oldWs)PQueue.add(newWs)untilqueue.empty()
3.2Circularwindowpropagation
Inthenextsectionwewillde neasecondtype
ofwindows,sofromnowonwindowsoriginatingfrompointsourcesarecalledcircularwindows.ThestartingpointforapropagationisdepictedinFigure2(b).Givenawindowwthecorrespondingedge01isalignedtothex-axisofthelocalcoordinatesystemwiththeorigininp0.Eachwindowisde-scribedbyasixtuple(b0,b1,d0,d1,σ,τ)withσrepresentingtheoptionalconstantoffsetbetweenapseudosourceandarealsource.Thebinary agτdeterminesonwhichsideofthex-axistheun-foldedpseudosourceslies(symbolizedinpicturesbythearc).Thewindowextentsareencodedinb0andb1whichareintherange[0..|01].Duetothefactthatthedistancesd0andd1ofthewindowendpointsfromthepseudosourceareknowntheun-foldedpositionscanbereconstructedviacirclein-tersection.
s1x=(bd2 d20+b1+012
bb)1 0sy
=
1τ
d20 (cx b0)
2Usingthelocalcoordinatesofp3whicharecom-putedanalogouslytosthenewwindowsarefound
by2Drayintersection.Therearedifferentconstel-lationswhichcanleadtoone,twoorthree(onsad-dlepoints)newwindows.
3.3Circularwindowintersection
Iftwowindowsoverlapandoneprovidesasmallerdistanceeverywheretheotherissimplyclippedagainstit.Ifbothareminimalinpartoftheover-lappinginterval,bothrangesareclippedtothepointwherebothdistancefunctionsareequal.Noticethatclippedwindowshavetobereinsertedintothequeuebecausetheirprioritycanchange.Usingtheunfoldedpseudosourcesfromtheprevioussectionthedistancefunctiondcofanarbitrarypoint(px,0)intheintervalofawindowcaneasilybeformulated.Duetothefactthatsisnotnecessarilyarealsource(e.g.saddlesinducepseudosources)thedistanceσfromalltraversedpseudosourcestotherealsourcemustbeadded.
dc(px)=
(px sx)2+s2y+σ(1)
Tryingto ndtheintersectionoftwosuchdis-tancefunctions,namelydc1(px)=dc2(px)the
computationendsupasthesolutionofaquadraticequationAp2x+Bpx+C=0.Inthiscasethereisexactlyonesolutionintheoverlappingintervalandthecoef cientsofthepolynomialare
A=α2 β2
B=γα+2s1xβ2C=1γ2
|s1|2β2α=s4
1x s0xβ=σ1 σ0
γ
=
|s0|2 |s1|2 β2
4Generalizationtoarbitrarysources
Ourgoalistogeneralizetheoriginalgeodesicdis-tancecomputationalgorithmfromisolatedpointstopolygonalcurvesonthesurface.Inaplanarcon g-urationtheEuclideandistancefunctiontoapolyg-onalcurvefallsintoseveralsegments.Insomeseg-mentsthedistancefunctionis,again,thesquarerootofaquadraticfunction.Thosesegmentscorrespondtotheverticesofthepolygon.Inothersegments,thedistancefunctionisjustlinear.Thesesegmentscorrespondtotheedgesofthepolygon.SeeFigure1foranexample.
Goingfromtheplanetoapiecewiseplanartrian-glemesh,wecanstillpropagatethedistancefunc-tionfromonetriangletoitsneighborsbystoring
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 ...
热门文档