Finding point-pairsFind Closest Point from Dense CloudSlide 3Approaches to closest triangle findingFindClosestPoint(a,[p,q,r])Finding closest point on triangleProjectOnSegment(c,p,q)Bounding SphereSlide 9Hierarchical cellular decompositionsSlide 11Constructing tree of bounding spheresConstructing octree of bounding spheresSlide 14Slide 15Slide 16Searching an octree of bounding spheresSlide 18Slide 19Copyright © 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 upper bound 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 L on 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 triangle and is the closest pol ml ml ml m l m- � - + -= + - + -� � + �a p q p r pc p q p r pcint. 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 trianglepqrABCDEFGRegion<0 <0 +>1Closest pointA Yes Yes No pB No Yes No ProjectOnSe gment(c,p,q)C No Yes Yes qD No No Yes ProjectOnSegment( c,q,r)E Yes No Yes rF Yes No No ProjectOnSegment( c,r,p)G No No No cCopyright © CISST ERC, 2000Engineering Research Center for Computer Integrated Surgical Systems and TechnologyProjectOnSegment(c,p,q)( ) ( )( ) ( )* (0, ( ,1))* * ( )Max Minll ll- � -=- � -== + -c p q pq p q pc p q ppqcc*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 carefullk k kj j j jpa b c pa b c rrrr r rrr r rky for some triangle ?Answer: if is the center of a sphere ofradius enclosing ( , , ), thenyou only need to check carefully if.kk k kk k jkrrr- - < -qa b cp q prrr rr r rCopyright © 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- - = - -- - � - -- � - - == +a bqb q b q a q a qc q c q a q a qb a c a q aq a brrrr rr r r r r rg gr r r r r r r rg grr r r r rgrr r done. Else solve the system as three equalities to get . The radius = .r -qq arr rCopyright © 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 point Vec3 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 subtree SplitSort(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] =