Reading AssignmentsSlide 2Methods for General ModelsHierarchical RepresentationsBVH vs. Spatial PartitioningSlide 6Slide 7Slide 8Spatial Data Structures & SubdivisionUniform Spatial SubdivisionOctreesBounding Volume HierarchiesType of Bounding VolumesBVH-Based Collision DetectionCollision Detection using BVHEvaluating Bounding Volume HierarchiesDesigning Bounding Volume HierarchiesObservationsTrade-off in Choosing BV’sBuilding HierarchiesSphere-TreesMethods for Building Sphere-Treesk-DOP’sChoices of k-dops in 3DBuilding Trees of k-dopsBuilding an OBBTreeBuilding an OBB TreeSlide 28Slide 29Slide 30Slide 31Slide 32Slide 33Slide 34Building an OBB Tree: FittingFitting OBBsSlide 37Slide 38Slide 39Slide 40Slide 41Slide 42Slide 43Slide 44Slide 45Building an OBB Tree: SummaryTree TraversalSlide 48Slide 49Slide 50Separating Axis TheoremSlide 52Implications of TheoremOBB Overlap Test: An Axis TestOBB Overlap Test: Axis Test DetailsSlide 56OBB Overlap TestSlide 58OBB Overlap Tests: ComparisonParallel Close ProximityParallel Close Proximity: ConvergenceSlide 62Slide 63Slide 64Slide 65Slide 66Slide 67Performance: Overlap TestsOBBs asymptotically outperform AABBs and spheresExample: AABB’s vs. OBB’sImplementation: RAPIDHybrid Hierarchy of Swept Sphere VolumesSwept Sphere Volumes (S-topes)SSV FittingOverlap TestHybrid BVH’s Based on SSVsPQP: ImplementationUNC Chapel HillM. C. LinReading AssignmentsEvaluation of Collision Detection Methods for Virtual Reality Fly-Throughs, by Held, Klosowski and Mitchell, Proc. of Canadian Conf. on Computational Geometry 1995. Efficient collision detection using bounding volume hierarchies of k-dops, by J. Klosowski, M. Held, J. S. B. Mitchell, H. Sowizral, and K. Zikan, IEEE Trans. on Visualization and Computer Graphics, 4(1):21--37, 1998. Collision Detection between Geometric Models: A Survey , by M. Lin and S. Gottschalk, Proc. of IMA Conference on Mathematics of Surfaces 1998.UNC Chapel HillM. C. LinReading AssignmentsOBB-Tree: A Hierarchical Structure for Rapid Interference Detection, by S. Gottschalk, M. Lin and D. Manocha, Proc. of ACM Siggraph, 1996. Rapid and Accurate Contact Determination between Spline Models using ShellTrees, by S. Krishnan, M. Gopi, M. Lin, D. Manocha and A. Pattekar, Proc. of Eurographics 1998. Fast Proximity Queries with Swept Sphere Volumes , by Eric Larsen, Stefan Gottschalk, Ming C. Lin, Dinesh Manocha, Technical report TR99-018, UNC-CH, CS Dept, 1999. (Part of the paper in Proc. of IEEE ICRA’2000)UNC Chapel HillM. C. LinMethods for General ModelsDecompose into convex pieces, and take minimum over all pairs of pieces:–Optimal (minimal) model decomposition is NP-hard. –Approximation algorithms exist for closed solids, but what about a list of triangles?Collection of triangles/polygons:–n*m pairs of triangles - brute force expensive–Hierarchical representations used to accelerate minimum findingUNC Chapel HillM. C. LinHierarchical RepresentationsTwo Common Types:–Bounding volume hierarchies – trees of spheres, ellipses, cubes, axis-aligned bounding boxes (AABBs), oriented bounding boxes (OBBs), K-dop, SSV, etc.–Spatial decomposition - BSP, K-d trees, octrees, MSP tree, R-trees, grids/cells, space-time bounds, etc. Do very well in “rejection tests”, when objects are far apart Performance may slow down, when the two objects are in close proximity and can have multiple contactsUNC Chapel HillM. C. LinBVH vs. Spatial PartitioningBVH: SP:- Object centric - Space centric- Spatial redundancy - Object redundancyUNC Chapel HillM. C. LinBVH vs. Spatial PartitioningBVH: SP:- Object centric - Space centric- Spatial redundancy - Object redundancyUNC Chapel HillM. C. LinBVH vs. Spatial PartitioningBVH: SP:- Object centric - Space centric- Spatial redundancy - Object redundancyUNC Chapel HillM. C. LinBVH vs. Spatial PartitioningBVH: SP:- Object centric - Space centric- Spatial redundancy - Object redundancyUNC Chapel HillM. C. LinSpatial Data Structures & SubdivisionMany others…… (see the lecture notes)Uniform Spatial SubQuadtree/Octreekd-treeBSP-treeUNC Chapel HillM. C. LinUniform Spatial SubdivisionDecompose the objects (the entire simulated environment) into identical cells arranged in a fixed, regular grids (equal size boxes or voxels)To represent an object, only need to decide which cells are occupied. To perform collision detection, check if any cell is occupied by two object Storage: to represent an object at resolution of n voxels per dimension requires upto n3 cells Accuracy: solids can only be “approximated”UNC Chapel HillM. C. LinOctreesQuadtree is derived by subdividing a 2D-plane in both dimensions to form quadrants Octrees are a 3D-extension of quadtreeUse divide-and-conquer Reduce storage requirements (in comparison to grids/voxels)UNC Chapel HillM. C. LinBounding Volume HierarchiesModel Hierarchy: –each node has a simple volume that bounds a set of triangles –children contain volumes that each bound a different portion of the parent’s triangles –The leaves of the hierarchy usually contain individual trianglesA binary bounding volume hierarchy:UNC Chapel HillM. C. LinType of Bounding VolumesSpheresEllipsoidsAxis-Aligned Bounding Boxes (AABB)Oriented Bounding Boxes (OBBs)Convex Hullsk-Discrete Orientation Polytopes (k-dop)Spherical Shells Swept-Sphere Volumes (SSVs)–Point Swetp Spheres (PSS)–Line Swept Spheres (LSS)–Rectangle Swept Spheres (RSS)–Triangle Swept Spheres (TSS)UNC Chapel HillM. C. LinBVH-Based Collision DetectionUNC Chapel HillM. C. LinCollision Detection using BVH1. Check for collision between two parent nodes (starting from the roots of two given trees) 2. If there is no interference between two parents, 3. Then stop and report “no collision”4. Else All children of one parent node are checked against all children of the other node5. If there is a collision between the children6. Then If at leave nodes7. Then report “collision”8. Else go to Step 49. Else stop and report “no collision”UNC Chapel HillM. C. LinEvaluating Bounding Volume Hierarchies  Cost Function: F = Nu x Cu + Nbv x Cbv + Np x CpF: total cost function for interference detectionNu: no. of bounding volumes updated Cu: cost of updating a bounding volume,Nbv: no. of bounding volume pair overlap