PresentationDemo Outline Introduction to Mesh Fitt

cat奶粉
1 ℃
2020-03-29

整理文档很辛苦，赏杯茶钱您下走！

还剩 ... 页未读，继续阅读 >>

免费阅读已结束，点击下载阅读编辑剩下 ... 页

阅读已结束，您可以下载文档离线阅读编辑

资源描述

MeshFittingToPointsMichaelPaoneAndrewYuenCMPT469April18,2005Presentation/DemoOutlineIntroductiontoMeshFittingtoPointsGeneralApproachandImplementationDetailsDemoLimitationsandPossibleFutureImprovementsUnexploredQuestionsErrorPlotsReferencesWhatisMeshFittingtoPoints?InputPointCloudAnunorganizedcollectionofpointsConnectivityMeshAconnectedtrianglemeshWedon’tknoworignorethegeometryoftheverticesEssentiallyaplanargraphAnchorpointsAsubsetoftheverticesintheConnectivityMeshEachanchorpointis“fixed”toacorrespondingpointinthePointCloudFixingcanbea“soft”constraintWhatisMeshFittingtoPoints?OutputCompletegeometryforConnectivityMeshWewouldlikethenewgeometryfortheconnectivitymeshtobedefinedsothattheconnectivitymeshfits,asbestaspossible,thepointcloud.OtherDesiredAttributesfornewgeometryFairdistributionofverticesSmoothCanbecomputedefficientlyWhyMeshFittingtoPoints?AtypicalapplicationPointCloudobtainedfromlaserrangesConnectivityMeshContainsastoredgenericmodelforthetypeofobjectbeingscannedKnowledgeassociatedwithcertainfeaturesofthemeshEg.DistancebetweentwoverticesofinterestAnchorpointsstoredwithconnectivitymeshcorrespondencetopointcloudestablishedbyauser/expertCompleteGeometryallowstheknowledgetobetransformedfortheparticularobjectbeingscannedApproach:OverviewTwostageapproach1.Usetheanchorpointstodistributeverticesintheconnectivitymeshtogetthegeometry“close”LeastSquaresMeshes2.MakeadjustmentstovertexgeometrytobetterfitthepointcloudlocallyProjectconnectivitymeshverticesontolocalneighbourhoodofpointcloudLeastSquaresMeshes[Sorkineetal.2004]LeastSquaresMeshes“LeastSquaresMeshes:mesheswithaprescribedconnectivitythatapproximateasetofcontrolpointsinaleast-squaressense.”LeastSquares(LS)MeshesComputinganLSmeshfromtheconnectivitymeshwithsparseanchorverticesinvolvesminimizingtheleastsquareserrorinasystemoflinearconstraints:0=-=-BFLBAxx ==otherwiseif01iijsjFmninnixBnisi+££ =-if0if0()()otherwisedegand,ifif011iiijdiEjijidL=Î= -=Wheresiisthei-thanchorpointLSMeshesThefirstsetofnconstraintsspecifiesthatthecomponent-wisedistancebetweeneachvertexandthecentroidofitsneighboursshouldbezero.()()otherwisedegand,ifif011iiijdiEjijidL=Î= -=0=xLLSMeshesThesecondsetofmconstraintsspecifiesthatthecomponent-wisedistancebetweeneachanchorvertexintheconnectivitymeshanditsassociatedpointinthepointcloudshouldbezero. ==otherwiseif01iijsjF=-10mssxxFxWheresiisthei-thanchorpointLSMeshes:SolutionTheleastsquaresminimizationofthefollowingsystem:BAAATT=xisequivalenttosolvingthefollowinglinearsystem:0=-=-BFLBAxxWesolvethatsystemusingadirectmethodinvolvingmatrixmultiplications,factorizations,andfrontandbacksubstitutions.TheseareimplementedusingATLASifpossible,butusing“textbook”algorithmsotherwise.Example-Camel100ControlVerticesExample-Camel2000ControlVerticesStage2:MakingLocalAdjustmentsTheverticesoftheconnectivitymeshhavebeendistributedinsuchawayastomakethemsufficientlyclosetothepointcloudTheverticesintheLSmeshmustbeprojectedontosurfacesrepresentingnearbyneighbourhoodsinthepointcloud.Tofindtheassociatedneighbourhoodforavertexvintheconnectivitymesh,wefind:Apointpinthepointcloudsuchthatpisthenearestpointinthepointcloudtov.Theneighbourhoodofpinthepointcloud.AssociatedNeighbourhoodofvTofindtheassociatedneighbourhoodforavertexvintheconnectivitymesh,wefind:Apointpinthepointcloudsuchthatpisthenearestpointinthepointcloudtov.Currentimplementationisbrute-forcesearch.Performsquicklyenoughformoderately-sizedmeshes.Theneighbourhoodofpinthepointcloud.Anyalgorithmwhichprovidesaneighbourhoodofpwilldo.Eg.K-Nearest-NeighboursProjectionSurfaceforvWehavemanyoptionsforfindingaprojectionsurfaceapproximatingtheneighbourhoodofvChoiceforImplementationFindthebest-fitplanetotheunweightedneighbourhoodofvHow?PCABest-fitplaneFixtheplanetothecentroidoftheneighbourhoodUsePCAtocomputethenormalvectorCompute3x3covariancematrixusingstandard“textbook”algorithmComputeeigenvectorsandeigenvaluesofcovariancematrixusingVTKroutineTheeigenvectorofthecovariancematrixcorrespondingtothesmallesteigenvalueFinally,wemakeouradjustmentbyprojectingvontotheplane.DEMOLimitationsofCurrentImplementationScalabilityIncomputingtheLSMesh,wemustcomputethematrixproductATAwhereAisan(n+m)xnmatrixwherenisthenumberofverticesintheconnectivitymesh,andmisthenumberofanchorpointsTheoptimizedmatrixmultiplicationCBLASroutineprovidedwithATLASunfortunatelyproducesinaccurateresultsOurimplementationusesa“textbook”algorithmthatcomputesinreasonabletimeformesheswithatmost~1000verticesSolution:UseanoptimizedalgorithmformatrixmultiplicationLimitationsofCurrentImplementationSeparationofModelsOursoftwareusesonemeshmodeltoextractaconnectivitymeshandtopopulatethepointcloud.Thispreventsthefittingofstoredmeshestoarbitrarypointclouds.Improvingthisfirstrequiressomemethod(possiblyexpert/user-guided)fordeterminingtheanchorpointsintheconnectivitymeshmodelandtheassociatedpointsinthepointcloud.ThismodificationalsorequiresthatanefficientK-NearestNeighboursalgo