Unformatted text preview:

Copyright © CISST ERC, 2000Engineering Research Center for Computer Integrated Surgical Systems and TechnologyFinding point-pairs• Given an a, find a corresponding b on the surface.• Then one approach would be to search every possible triangle or surface point and then take the closest point.• The key is to find a more efficient way to do thisCopyright © CISST ERC, 2000Engineering Research Center for Computer Integrated Surgical Systems and TechnologyFind Closest Point from Dense Cloud• Basic approach is to divide space into regions. Suppose that we have one point bk* that is a possible match for a point ak. The distance ∆*=|| bk* - ak|| obviously acts as an upperbound on the distance of the closest point to the surface.• Given a region R containing many possible points bj, if we can compute a lower bound ∆Lon the distance from a to any point in R, then we need only consider points inside R if ∆L< ∆*.Copyright © CISST ERC, 2000Engineering Research Center for Computer Integrated Surgical Systems and TechnologyFind Closest Point from Dense Cloud• There are many ways to implement this idea– Simply partitioning space into many buckets– Octrees, KD trees, covariance trees, etc.Copyright © CISST ERC, 2000Engineering Research Center for Computer Integrated Surgical Systems and TechnologyApproaches to closest triangle finding1. (Simplest) Construct linear list of triangles and search sequentially for closest triangle to each point.2. (Only slightly harder) Construct bounding spheres around each triangle and use these to reduce the number of careful checks required.3. (Faster if have lots of points) Construct hierarchical data structure to speed search.4. (Better but harder) Rotate each level of the tree to align with data.Copyright © CISST ERC, 2000Engineering Research Center for Computer Integrated Surgical Systems and TechnologyFindClosestPoint(a,[p,q,r])Many approaches. One is to solve the system()()in a least squares sense for and . Then compute()()If 0, 0, 1, then lies within the triangleand is the closest poλµλµλµλµλµ−≈ − + −=+ − + −≥≥+≤ap qp rpcp qp rpcint. Otherwise, you need to find a point on the border of the trianglepqracHint: For efficiency, work out the least squares problem explicitly. You will have to solve a 2 x 2 linear system for λ, µCopyright © CISST ERC, 2000Engineering Research Center for Computer Integrated Surgical Systems and TechnologyFinding closest point on trianglepqrABCDEFGcNoNoNoGProjectOnSegment(c,r,p)NoNoYesFrYesNoYesEProjectOnSegment(c,q,r)YesNoNoDqYesYesNoCProjectOnSegment(c,p,q)NoYesNoBpNoYesYesAClosest pointλ+µ>1µ<0λ<0RegionCopyright © CISST ERC, 2000Engineering Research Center for Computer Integrated Surgical Systems and TechnologyProjectOnSegment(c,p,q)()()()()*(0,(,1))**()Max Minλλλλ−•−=−•−==+ −cp qpqp qpcp qppqcc*Copyright © CISST ERC, 2000Engineering Research Center for Computer Integrated Surgical Systems and TechnologyBounding SphereabcqSuppose you have a point and are trying to findthe closest triangle ( , , ) to . If you havealready found a triangle ( , , ) with a point on it, when do you need to check carefullkkkjjj jpabc pabc rGGGGGGGGGky for some triangle ?Answer: if is the center of a sphere ofradius enclosing ( , , ), thenyou only need to check carefully if.kkkkkk jkrρρ−−<−qabcpq pGGGGGG GCopyright © CISST ERC, 2000Engineering Research Center for Computer Integrated Surgical Systems and TechnologyBounding Sphereabcq()()()()()()()()()()()()Assume edge ( , ) is the longest.Then the center of the sphere will obey0Simple approach: Try / 2.If inequality holds, then−⋅−=−⋅−−⋅−≤−⋅−−×−⋅−==+abqbq bq aq aqcq cq aq aqba ca qaqabGGGGGGGGGGGGG GG GG GGGGGGGGGGG done. Else solve the system as three equalities to get . The radius = .ρ−qqaGGGCopyright © CISST ERC, 2000Engineering Research Center for Computer Integrated Surgical Systems and TechnologyHierarchical cellular decompositionsCopyright © CISST ERC, 2000Engineering Research Center for Computer Integrated Surgical Systems and TechnologyHierarchical cellular decompositionsCopyright © CISST ERC, 2000Engineering Research Center for Computer Integrated Surgical Systems and TechnologyConstructing tree of bounding spheresclass BoundingSphere {public:Vec3 Center; // Coordinates of centerdouble Radius; // radius of sphereThing* Object; // some reference to the thing// bounded};Copyright © CISST ERC, 2000Engineering Research Center for Computer Integrated Surgical Systems and TechnologyConstructing octree of bounding spheresclass BoundingBoxTreeNode {Vec3 Center; // splitting pointVec3 UB; // corners of box Vec3 LB;int HaveSubtrees;int nSpheres;double MaxRadius; // maximum radius of sphere in boxBoundingBoxTreeNode* SubTrees[2][2][2];BoundingSphere** Spheres;::BoundingBoxTreeNode(BoundingSphere** BS, int nS);ConstructSubtrees();void FindClosestPoint(Vec3 v, double& bound, Vec3& closest);};Copyright © CISST ERC, 2000Engineering Research Center for Computer Integrated Surgical Systems and TechnologyConstructing octree of bounding spheresBoundingBoxTreeNode(BoundingSphere** BS, int nS){ Spheres = BS; nSpheres = nS;Center = Centroid(Spheres, nSpheres);MaxRadius = FindMaxRadius(Spheres,nSpheres);UB = FindMaxCoordinates(Spheres,nSpheres);LB = FindMinCoordinates(Spheres,nSpheres);ConstructSubtrees();};Copyright © CISST ERC, 2000Engineering Research Center for Computer Integrated Surgical Systems and TechnologyConstructing octree of bounding spheresConstructSubtrees(){ if (nSpheres<= minCount || length(UB-LB)<=minDiag) { HaveSubtrees=0; return; };HaveSubtrees = 1;int nnn,npn,npp,nnp,pnn,ppn,ppp,pnp; // number of spheres in each subtreeSplitSort(Center, Spheres, nnn,npn,npp,nnp,pnn,ppn,ppp,pnp);Subtrees[0][0][0] = BoundingBoxTree(Spheres[0],nnn);Subtrees[0][1][0] = BoundingBoxTree(Spheres[nnn],npn);Subtrees[0][1][1] = BoundingBoxTree(Spheres[nnn+npn],npp);::}Copyright © CISST ERC, 2000Engineering Research Center for Computer Integrated Surgical Systems and TechnologyConstructing octree of bounding spheresSplitSort(Vec3 SplittingPoint, BoundingSphere** Spheres, int& nnn, int& npn, … ,int& pnp){ // reorder Spheres(…) into eight buckets according to // comparison of coordinates of Sphere(k)->Center // with coordinates of splitting point. E.g., first bucket has// Sphere(k)->Center.x < SplittingPoint.x//


View Full Document

Johns Hopkins EN 600 445 - Finding point-pairS

Download Finding point-pairS
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Finding point-pairS and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Finding point-pairS 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?