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

Multi-level Partition of Unity Implicits图形学

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

ornegative(outside)awayfromthedatapoints.Theapproximatenormalsofthepointsareusedtodistinguishthisinside/outsideori-entationlocally.Iftheshapefunctionapproximationisnotaccurateenough(doesn’tmatchthepointswell),thecellissubdividedandtheprocedureisrepeateduntilacertainaccuracyisachieved.Fig-ure1showshowtheoctree-levelsadaptaccordingtotherelationbetweenlocalshapecomplexityanddesiredaccuracy.Inlocationsnearthecommonboundaryoftwoormorecells,theshapefunc-tionsareblendedtogetheraccordingtoweightsfromthepartitionofunityfunctions.Theglobalimplicitfunctionofthesurfaceisgivenbythispartitionofunityblendingofthelocalshapeapproxi-mationsattheoctreeleafs.

MPUimplicitsareconceptuallysimple,easytoimplement,andarecapableofprovidingafast,accurate,andadaptivereconstruc-tionsofcomplexshapesfromscatteredpointdatacontainingmil-lionsofpoints.Thecomplexityoftheapproachisoutputsensi-tiveinthesensethatthecreationtimeandmemoryconsumptiondependonthecomplexityofthereconstructedshaperatherthanthenumberofdatapoints.SinceMPUimplicitscandeliverhigh-accuracyshapeapproximations,function-basedoperationssuchasshapeblending,offsets,deformationsandCSGcaneasilybeap-plied.Allofthesesameoperationscanbeperformedfordatathatwasoriginallyinaparametricorpolygonalformsimplybycon-vertingtheseshapedescriptionstotheMPUrepresentation.Previouswork.Implicitshaperepresentationsareattractivebe-causetheyallowacomplexshapetobedescribedbyonefor-mula,theyunifysurfaceandvolumemodeling,andseveralcom-plexshapeeditingoperationsareeasytoperformonsuchmodels[Bloomenthaletal.1997].Ontheotherhand,traditionalpureim-plicitsurfacemodelingtechniqueslacklocalshapecontrol.Thisdrawbackhasbecomeespeciallynoticeablewiththedevelopmentofmodernshapeacquisitiontechniquesthatcangeneratedatasetsconsistingofthousands,millions,orevenbillionsofpoints(see,e.g.,[Levoyetal.2000]).Themainadvantagesofusingimplicitsforshapereconstructionfromscattereddataaredatarepairingcapa-bilitiesandopportunitiestoedittheresultingobjectsusingstandardimplicitmodelingoperations.

MostimplicitshapereconstructionsfrompointsetsarebasedonBlinn’sideaofblendinglocalimplicitprimitives[Blinn1982].Muraki[1991]usesalinearcombinationofGaussianblobsto tanimplicitsurfacetoapointset.Hoppeetal.[1992]locallyes-timatethesigneddistancefunctionasthedistancetothetangentplaneoftheclosestpoint.Limetal.[1995]useblendedunionofspheresforimplicitreconstructionofsolidsfromscattereddata.Theyobtainaninitialcon gurationofspheresfromtheDelaunaytetrahedralizationandanonlinearoptimizationisthenapplied.Ba-jajetal.[1995]andBernardinietal.[1999]combinealgebraic ttingwithpointdatatriangulationbyadaptiveα-shapes[Edels-brunnerandM¨ucke1994].AvolumetricapproachofCurlessandLevoy[1996]introducedforshapereconstructionfromrangescansisbasedonestimatingthedistancefunctionfromareconstructedmodel.Savchenkoetal.[1995],Carretal.[2001],andTurkandO’Brien[2002]usegloballysupportedradialbasisfunctions(RBFs)whileMorseetal.[2001],Kojekineetal.[2003],andOhtakeetal.[2003]employcompactlysupportedRBFstorecon-structsmoothsurfacesfrompointclouddata.Itseemsthatthestate-of-the-artinconstructingimplicitfunctionsfromlargesetsofscat-teredpointsareRBF-basedmethods[Carretal.2001;Dinhetal.2002;TurkandO’Brien2002].WhileRBF-basedmethodsarees-peciallyusefulfortherepairofincompletedata,theyfaceseriousdif cultiesinaccuratereconstructionofsharpfeatures[Dinhetal.2001],mayrequireauserinterventionlikechoosinganappropriatecarriersolid[Kojekineetal.2003],andcangenerateextrazero-levelsets[Ohtakeetal.2003].Inaddition,sinceRBFsolutionsareglobalinnature,processingmillionsofpointsseemstobebeyondthecapabilitiesofmostpresentdayPCs.

Thelevelsetmethod[ZhaoandOsher2002]isanothergoodcan-didateforreconstructingthesigneddistancefunction.However,itscurrentimplementationbecomesexpensiveintimeandmemoryifhighaccuracyreconstructionisrequired(althoughthismightbeim-provedifadaptivegridsareused).Projection-basedapproachestoshapeapproximation[Alexaetal.2001;Fleishmanetal.2003]havetheadvantagethattheyarelocal(i.e.independentofthenumberofdatapoints)anddirectlyyieldapointonthesurface.However,theprojectionsteprequiresthesolutionofanon-linearmovingleastsquaresproblem,whichmakesmostpracticalshapeoperationsex-pensive.

Ourapproachcanbeseenasablendofseveralknowntechniquesthat,together,resultinanattractivemethodforreconstructinganimplicitfunction.OnecommonRBFtechniqueisto rstdividethedatadomainintoseveralcellssothatthedataisbrokenintomanageablepieces[Beatsonetal.2000;SchabackandWendland2000;Iske2001;IskeandLevesley2002;Wendland2002].Asaparticularmethodfordomaindecomposition,thepartitionofunityapproach(PU)ofFrankeandNielson[1980]hasbeenusedasageneralFEMmethodincomputationalmechanics[BabuˇskaandOsborn1994]andrecentlyhasbecomepopularbecauseitavoidsthetopologicaloverheadofconstructingamesh[BabuˇskaandMe-lenk1997;GriebelandSchweitzer2000;GriebelandSchweitzer2002].Ourstrategyforavoidingextrazerolevelsetsisreminiscentof[MooreandWarren1991;Warren1992],whereanadaptiveandrecursivevolumetricsubdivisionwasused.OnecouldviewourMPUrepresentationsasbeingsimilartoadaptivelysampleddis-tance elds[Friskenetal.2000],withthedifferencethattheMPUapproachusescontinuousratherthansampledfunctions.

Whenusedwithanappropriatechoiceoflocalshapeapprox-imations,ourapproachhasthefollowingattractivefeatures:theabilitytocreatehighqualityimplicitsurfacesfromverylargepointdatasets,theaccuratereconstructionofsharpfeatures,andfastandeasylocalshapeaccess.

2PartitionofUnityApproach

Thepartitionofunityapproachistypicallyusedtointegratelo-callyde nedapproximantsintoaglobalapproximation.Importantpropertiessuchasthemaximumerrorandconvergenceorderareinheritedfromthelocalbehavior.Thebasicideaofthepartitionofunityapproachistobreakthedatadomainintoseveralpieces,approximatethedataineachsubdomainseparately,andthenblendthelocalsolutionstogetherusingsmooth,localweightsthatsumuptooneeverywhereonthedomain.

Morespeci cally,consideraboundeddomain inaEuclideanspace(wewillworkin3D)andasetofnonnegativecompactlysupportedfunctions{ i}suchthat

∑i i≡1on .

Letusassociatea local approximationsetoffunctionsViwitheachsubdomainsupp i.Nowanapproximationofafunctionf(x)de nedon isgivenby

whereQi∈Vi.

Givenasetofnonnegativecompactlysupportedfunctions{wi(x)}suchthat

suppwi,

i

f(x)≈∑i i(x)Qi(x),

(1)

partitionofunityfunctions{ i}canbegeneratedby

i(x)=

wi(x)

.

∑j=1wj(x)

(2)

ApproximationbymeansofEqs.1and2constitutesthecoreof

thepartitionofunity niteelementmethods[BabuˇskaandOsborn1994].TheyresembletheModi edShepard’smethodofFranke

上一页第2页

你可能喜欢

热门文档

相关文档

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