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

Multi-level Partition of Unity Implicits图形学

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

Multi-level Partition of Unity Implicits图形学

Multi-level Partition of Unity Implicits图形学

Multi-level Partition of Unity Implicits图形学

Figure5:Left:Testingwhetheranauxiliarypointqcanbeusedtoobtainareliableestimateofthesigneddistancefunction.Thegreenqisreliable,butthemagentaqisnot.Right:Detectionofsharpfeaturesisdonebyclusteringofpointnormals.

Figure4:Left: ttingabivariatequadraticpolynomial.Right:local tofageneralquadric;auxiliarypointslocatedatthecellcenterandcornersareusedinordertoachieveanaccurateapproximationofthedistancefunction.

toreconstructsharpfeatures.Actually(c)consistsofanumberoftests(anedgetestandcornertests)inordertodeterminethetypeofapproximationsurfacethatshouldbeused.

Afewsimpletestsareperformedtoselectfromamongthethreetypesoflocalshapefunctions.Iftherearemorethan2Nminpointsinthelocalball,weuseafunctionoftype(a)or(b).Anaveragenormaldirectioniscomputedforthepointsandifthemaximumdeviationofnormalstotheaverageismorethanπ/2thenwe twith(a),otherwiseweusetype(b).Iftherearefewerthan2Nminpointsassociatedwithacell,moredetailedchecksaremadetoseeifanedgeorcornerispresent,anddetailsofthisaregivenbelow.Whydon’twelookforsharpfeatureswhentherearemorethan2Nminpoints?Becausethesharpfeaturedetectionaddscomputa-tionalcomplexityandtheoctreesubdivisionproceduretakescareofthis,anyway.Shouldthesurfaceactuallycontainacorneroredgenearsuchacell,thenthequality-of- tmeasure(7)willcausethecelltobedivided,andthesharpfeaturewillbe tbyoneormorechildcells.

Inthefollowingsub-sectionswewilldescribeeachofthethreelocalshapefunctionsinmoredetail.Thenotationweuseinthesesectionsisasfollows.LetcbethecenterofasubdivisioncubiccellwherewewanttoconstructalocalshapefunctionQ(x).WedenotebyP thepointsofPthatareinsidetheballofthecell.Letnbeaunitnormalvectorassignedtoc.ThisnormalniscomputedfromthenormalizedweightedarithmeticmeanofthenormalsofP takenwiththeweightsde nedby(3).LetθbethemaximalanglebetweennandthenormalsN assignedtothepointsofP .(a)Local tofageneralquadric.If

|P |>2Nminandθ≥π/2

a3Dquadraticsurfaceis tted.Usuallythiscorrespondstoasit-uationsketchedintherightdrawingofFigure4.Alocalshapefunctionisgivenby

Q(x)=xTAx+bTx+c(8)

whereAisasymmetric3×3matrix,bisavectorofthreecompo-nents,andcisascalar.Inordertodetermine theunknownsA,b,andcwemakeuseofauxiliarypointsqitohelporientthelocalshapefunction.Thesepointsarechosenasthecornersandthecen-terofthesubdivisioncell,asdemonstratedintherightpictureofFigure4.

Eachauxiliarypointqistestedforwhetheritcanbeusedtoobtainareliableestimateofthesigneddistancefunction.Foreachq,itssixnearestneighborsp(1),p(2),...,p(6)fromP arefoundandthescalarproducts

(i)(i)n·q p,i=1,2,...,6,(9)arecomputed.Ifnotallthescalarproductshavethesamesign,

qisremovedfromthesetofauxiliarypoints.ThegeometricideabehindthistestisexplainedbytheleftdrawingofFigure5.

Ifthesetofremainingauxiliarypointsisempty,thecellissub-divided.

Foreachremainingauxiliarypointq,anaveragedistanced,thearithmeticmeanofthescalarproducts(9),iscomputed

16(i) (i).(10)

Multi-level Partition of Unity Implicits图形学

d=∑n·q p

6i=1

wheremisthenumberofremainingpointsq.

|P |>2Nmin

and

Finallytheunknownsin(8)arefoundbyminimizing

1m 1

∑wpiQ(pi)2+∑Q(qi) di2,

mi=1∑wpip∈P

i

(11)

(b)Local tofabivariatequadraticpolynomial.If

θ<π/2

abivariatequadraticpolynomialislocally tted.Letusintroduce

localcoordinates(u,v,w)withtheoriginofcoordinatesatcsuchthattheplane(u,v)isorthogonaltonandthepositivedirectionofwcoincideswiththedirectionofn.Aquadraticshapefunctionatcisgivenby

22

Q(x)=w Au+2Buv+Cv+Du+Ev+F,(12)where(v,u,w)arethecoordinatesofxinthenewcoordinatesys-tem.Theunknowncoef cientsA,B,C,D,E,andFaredetermined

byminimizing

w(13)∑piQ(pi)2.

pi∈P

TheleftdrawingofFigure4illustratesthegeometricideabehind

local ttingofabivariatequadraticpolynomial.

(c)Localapproximationofedgesandcorners.Thequadraticfunctions(12)and(8)consideredabovearenotcapableofaccuratelycapturingsharpedgesandcorners.Iftherearejustafewpointsassociatedwithacell(|P |≤2Nmin),wetryto tapiecewisequadraticfunctioninsteadofaquadraticapproximation.WeperformautomaticrecognitionofedgesandcornersusingasimplebuteffectiveprocedureproposedbyKobbeltetal.[2001].Theideaisbasedonclusteringofnormals,asdemonstratedbytherightdrawingofFigure5.

Following[Kobbeltetal.2001]weassumethatthesurfacehasasharpfeatureif

mini,jni·nj<0.9.(14)If(14)isnotsatis ed,wegoto(b)andlocalbivariatepolyno-mial(12)is ttedtoP .Otherwisewecheckwhetherthedetected

featureisacorner.Weconsidern3=n1×n2,thenormalvectortotheplanedeterminedbythenormalsn1andn2enclosingthemaximalangle.Ifthedeviationofthenormalsnifromtheplaneis

suf cientlylarge

(15)maxi ni·n3 >0.7

thefeatureisrecognizedasacorner.

If(14)issatis edand(15)isnot,weexpectthesurfacetohave

anedgeandsubdividethesetofnormalsniintotwoclustersaccordingtotheirangleswithn1andn2(twosphericalVoronoi

andP ,P =subsetscorrespondington1andn2).DenotebyP12

∪P ,twosubsetscorrespondingtotheclustersofthenormals.P12

andNowthequadratic tprocedureisappliedseparatelytoP1

andanon-smoothlocalshapefunctionapproximationP isP2

constructedviathemax/minBooleanoperationsofRicci[1973].If(14)and(15)aresatis ed,wesubdivideN intothreesets.

andN areconstructedasabove.NextwecheckwhetherFirstN1 2

n·n < n·n andaddpointptothethirdclusterifthein-1,2

i

3

i

i

equalityissatis ed.

上一页第4页

你可能喜欢

热门文档

相关文档

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