文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > Multi-level Partition of Unity Implicits图形学
侵权投诉

Multi-level Partition of Unity Implicits图形学

multi-level 思想在图形分割的应用的应用

andNielson[1980](seealso[Renka1988]),wherepolynomiallo-calapproximationsQi(x)are used incombinationwith“inverse-distance”singularweightswi(x)forinterpolationpurposes.GivenasetofscatteredpointsPequippedwithnormalsN,weapproximatethesigneddistancefunctionf(x)fromP.Incontrasttotheapproachesmentionedabove,weintroduceanadaptivepro-cedureforgeneratingthesubdivisionandproblem-speci capprox-imationsets.First,weuseanoctree-basedadaptivespacesubdivi-sionof .Thisallowsustocontroltheerroroftheapproximationwhileadaptingthecomplexityoftherepresentationtothecomplex-ityoftheshape(seeSection3).Second,weusepiecewisequadraticfunctionsresultingfromBooleanoperationsfortheaccuraterepre-sentationofsharpfeatures.Theclassi cationoflocalshapesandappropriateapproximationsetsarediscussedinSection4.

ForapproximationpurposesweusethequadraticB-splineb(t)togenerateweightfunctions

3x ci(3)wi(x)=b

2Ri

Multi-level Partition of Unity Implicits图形学

Figure2:Left:adaptivesubdivisioncoupledwithleast-squares tting.Right:

Multi-level Partition of Unity Implicits图形学

enlarg-

Multi-level Partition of Unity Implicits图形学

ing

Multi-level Partition of Unity Implicits图形学

thesphericaldomainforthelocalapproximationtomakeitmorerobust.

centeredatciandhavingasphericalsupportofradiusRi.

IfaninterpolationofPisrequired,weusetheinverse-distancesingularweights[FrankeandNielson1980;Renka1988]

2 Ri x ci+aifa>0,where(a)+=(4)wi(x)=0otherwiseRix ci

Figure3:Left:asetofpointsequippedwithnormals.Middle:thecircles(2Dballs)

correspondingtotheadaptivesubdivisionareshownhereat50%oftheirrealsize.Right:thedistancefunctionisreconstructed,andthezerolevelsetislocatedbetweentheyellowandgreenbands.

3AdaptiveOctree-basedApproximation

ThealgorithmforconstructinganMPUimplicitisdrivenbyre-peatedsubdivisionoftheregionofspacethatisoccupiedbytheinputsetofpoints.First,thepointsinParerescaledsothatanaxis-alignedboundingcubehasaunit-lengthmaindiagonal.Wethenapplyanadaptiveoctree-basedsubdivisiontotheboundingcube.Consideracubiccellthatwasgeneratedduringthesubdivi-sionprocess,andletcbethecenteranddthelengthofthemaindiagonalofthecell.

Wede nethesupportradiusRfortheweightfunction(3)forthecelltobeproportionaltoitsdiagonal:

R=αd.(5)

Wetypicallyuseα=0.75.Alargervalueforαyieldsbetter(smoother)interpolationandapproximationresultsattheexpenseofcomputationtime.Timecomplexityisroughlyquadraticinα.Figure11illustratestheeffectofα,especiallyfortheaccurateap-proximationofthedistancefunctionawayfromthezerolevelset.Foreachcellgeneratedduringthesubdivisionprocess,alocalshapefunctionQ(x)isbuiltusingaleast-squares ttingprocedure,asshownintheleftdrawingofFigure2.

Sometimes(especiallyifthedensityofPisnotuniform)theballofradiusRforacelldoesnotcontainenoughpointsforarobustestimationofQ(x).IfthenumberofpointsislessthanNmin(inour

implementationwesetNmin=15),aballwithincreasedradiusR

isdeterminedthatcontainsatleastNminpoints.Thisisdoneby

=RandtheniteratingstartingwithR

=R +λRR(6)

untiltheballcontainstheminimumnumberofpoints(inourim-plementationwesetλ=0.1).Nowthepointsenclosedbytheball

areusedtoestimatealocalshapefunctionQ(x),asofradiusR

demonstratedintherightdrawingofFigure2.

Weuseakd-treepartitioningforef cientsolvingoftheserangesearchingproblems.

IftheballaroundanoctreecellwithinitialradiusR=αdisempty,anapproximationofthedistancefunctioniscomputedasexplainedaboveanditwillnotbesubdividedfurther.Otherwise,alocalmax-normapproximationerrorisestimatedaccordingtotheTaubindistance[Taubin1991]

ε=max|Qpi| Qpi .(7)

Multi-level Partition of Unity Implicits图形学

|pi c|<R

Ifεisgreaterthanauser-speci edthresholdε0,thecellissubdi-videdandthe ttingprocessisperformedforthechildcells.

Figure3demonstrateshowouradaptivesubdivisionschemeworksin2D.

ThefollowingpseudocodedescribesarecursiveprocedureforassemblinganMPUapproximationatpointxwithprecisionε0.

MPUapprox(x,ε0)EvaluateMPUapprox(x,ε0)

SwQ=Sw=0;

root->MPUapprox(x,ε0);returnSwQ/Sw;

if(|x ci|>Ri)thenreturn;if(Qiisnotcreatedyet)thenCreateQiandcomputeεi;if(εi>ε0)then

if(Nochilds)thenCreatechilds;foreachchild

child->MPUapprox(x,ε0);else

SwQ=SwQ+wi(x) Qi(x);Sw=Sw+wi(x);

Here,SwandSwQdenote∑wi(x)and∑Qi(x)wi(x),respectively,seeEqs.1and2.

Thisprocedureiseasytoimplement.Wehopethatthiswillmakeourapproachanditsimplementationaccessibletoawiderangeofusers.

Notethatweabandonthelocalapproximationsthatarecon-structedatthenon-leafcellsoftheoctree.ThisallowsustousedifferentlocalapproximationsofthedistancefunctionfarfromPandneartoP,aswellasspeci csharpfeatureapproximations,withoutcompensatingfortheeffectsofcoarseapproximations.In-heritingcoarseapproximationswouldalsorequireustocounteractalreadygeneratedzero-setsinemptyballs.Inaddition,avoidingcoarseapproximationssavesmemoryandresultsinfasterevalua-tionoftheimplicitfunction.

4EstimatingLocalShapeFunctions

Ourlocal ttingstrategydependsonthenumberofpointsintheballofagivencellandthedistributionofnormalsofthosepoints.Atagivencellweusethemostappropriateoneofthesethreelocalapproximations:

(a)ageneral3Dquadric,

(b)abivariatequadraticpolynomialinlocalcoordinates,(c)apiecewisequadricsurfacethat tsanedgeoracorner.Roughlyspeaking,(a)isusedtoapproximatelargerpartsofthesurface,whichcouldbeunboundedorcontainmorethanonesheet,(b)isusedtoapproximatealocalsmoothpatch,and(c)isemployed

上一页第3页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email