PresentationDemo Outline Introduction to Mesh Fitt

MeshFittingToPointsMichaelPaoneAndrewYuenCMPT469April18,2005Presentation/DemoOutline
IntroductiontoMeshFittingtoPoints
GeneralApproachandImplementationDetails
Demo
LimitationsandPossibleFutureImprovements
UnexploredQuestions
ErrorPlots
ReferencesWhatisMeshFittingtoPoints?
Input
PointCloud
Anunorganizedcollectionofpoints
ConnectivityMesh
Aconnectedtrianglemesh
Wedon’tknoworignorethegeometryofthevertices
Essentiallyaplanargraph
Anchorpoints
AsubsetoftheverticesintheConnectivityMesh
Eachanchorpointis“fixed”toacorrespondingpointinthePointCloud
Fixingcanbea“soft”constraintWhatisMeshFittingtoPoints?
Output
CompletegeometryforConnectivityMesh
Wewouldlikethenewgeometryfortheconnectivitymeshtobedefinedsothattheconnectivitymeshfits,asbestaspossible,thepointcloud.
OtherDesiredAttributesfornewgeometry
Fairdistributionofvertices
Smooth
CanbecomputedefficientlyWhyMeshFittingtoPoints?
Atypicalapplication
PointCloudobtainedfromlaserranges
ConnectivityMesh
Containsastoredgenericmodelforthetypeofobjectbeingscanned
Knowledgeassociatedwithcertainfeaturesofthemesh
Eg.Distancebetweentwoverticesofinterest
Anchorpoints
storedwithconnectivitymesh
correspondencetopointcloudestablishedbyauser/expert
CompleteGeometryallowstheknowledgetobetransformedfortheparticularobjectbeingscannedApproach:Overview
Twostageapproach1.Usetheanchorpointstodistributeverticesintheconnectivitymeshtogetthegeometry“close”
LeastSquaresMeshes2.Makeadjustmentstovertexgeometrytobetterfitthepointcloudlocally
ProjectconnectivitymeshverticesontolocalneighbourhoodofpointcloudLeastSquaresMeshes[Sorkineetal.2004]LeastSquaresMeshes“LeastSquaresMeshes:mesheswithaprescribedconnectivitythatapproximateasetofcontrolpointsinaleast-squaressense.”LeastSquares(LS)Meshes
ComputinganLSmeshfromtheconnectivitymeshwithsparseanchorverticesinvolvesminimizingtheleastsquareserrorinasystemoflinearconstraints:0=-

=-BFLBAxx ==otherwiseif01iijsjFmninnixBnisi+££ =-if0if0()()otherwisedegand,ifif011iiijdiEjijidL=Î= -=Wheresiisthei-thanchorpointLSMeshes
Thefirstsetofnconstraintsspecifiesthatthecomponent-wisedistancebetweeneachvertexandthecentroidofitsneighboursshouldbezero.()()otherwisedegand,ifif011iiijdiEjijidL=Î= -=0=xLLSMeshes
Thesecondsetofmconstraintsspecifiesthatthecomponent-wisedistancebetweeneachanchorvertexintheconnectivitymeshanditsassociatedpointinthepointcloudshouldbezero. ==otherwiseif01iijsjF=-10mssxxF
xWheresiisthei-thanchorpointLSMeshes:SolutionTheleastsquaresminimizationofthefollowingsystem:BAAATT=xisequivalenttosolvingthefollowinglinearsystem:0=-

=-BFLBAxxWesolvethatsystemusingadirectmethodinvolvingmatrixmultiplications,factorizations,andfrontandbacksubstitutions.TheseareimplementedusingATLASifpossible,butusing“textbook”algorithmsotherwise.Example-Camel100ControlVerticesExample-Camel2000ControlVerticesStage2:MakingLocalAdjustments
Theverticesoftheconnectivitymeshhavebeendistributedinsuchawayastomakethemsufficientlyclosetothepointcloud
TheverticesintheLSmeshmustbeprojectedontosurfacesrepresentingnearbyneighbourhoodsinthepointcloud.
Tofindtheassociatedneighbourhoodforavertexvintheconnectivitymesh,wefind:
Apointpinthepointcloudsuchthatpisthenearestpointinthepointcloudtov.
Theneighbourhoodofpinthepointcloud.AssociatedNeighbourhoodofv
Tofindtheassociatedneighbourhoodforavertexvintheconnectivitymesh,wefind:
Apointpinthepointcloudsuchthatpisthenearestpointinthepointcloudtov.
Currentimplementationisbrute-forcesearch.
Performsquicklyenoughformoderately-sizedmeshes.
Theneighbourhoodofpinthepointcloud.
Anyalgorithmwhichprovidesaneighbourhoodofpwilldo.
Eg.K-Nearest-NeighboursProjectionSurfaceforv
Wehavemanyoptionsforfindingaprojectionsurfaceapproximatingtheneighbourhoodofv
ChoiceforImplementation
Findthebest-fitplanetotheunweightedneighbourhoodofv
How?
PCABest-fitplane
Fixtheplanetothecentroidoftheneighbourhood
UsePCAtocomputethenormalvector
Compute3x3covariancematrixusingstandard“textbook”algorithm
ComputeeigenvectorsandeigenvaluesofcovariancematrixusingVTKroutine
Theeigenvectorofthecovariancematrixcorrespondingtothesmallesteigenvalue
Finally,wemakeouradjustmentbyprojectingvontotheplane.DEMOLimitationsofCurrentImplementation
Scalability
IncomputingtheLSMesh,wemustcomputethematrixproductATAwhereAisan(n+m)xnmatrixwherenisthenumberofverticesintheconnectivitymesh,andmisthenumberofanchorpoints
TheoptimizedmatrixmultiplicationCBLASroutineprovidedwithATLASunfortunatelyproducesinaccurateresults
Ourimplementationusesa“textbook”algorithmthatcomputesinreasonabletimeformesheswithatmost~1000vertices
Solution:UseanoptimizedalgorithmformatrixmultiplicationLimitationsofCurrentImplementation
SeparationofModels
Oursoftwareusesonemeshmodeltoextractaconnectivitymeshandtopopulatethepointcloud.
Thispreventsthefittingofstoredmeshestoarbitrarypointclouds.
Improvingthisfirstrequiressomemethod(possiblyexpert/user-guided)fordeterminingtheanchorpointsintheconnectivitymeshmodelandtheassociatedpointsinthepointcloud.
ThismodificationalsorequiresthatanefficientK-NearestNeighboursalgo