Fast Collision Detection between Massive Models using Dynamic Simplification

by Sung-Eui Yoon, Brian Salomon, Ming Lin, and Dinesh Manocha.

Realtime captured video of dynamic simulation and navigation

(You can download QuickTime from QuickTime)

Figure 1: Collision Example. This image sequence shows discrete positions from our dynamic simulation using our system. The 28M-triangle Lucy model falls on and then off the 1.7M-triangle turbine-blade model and the response is computed using impulse-based simulation. In this simulation the collision detection took an average of 18ms per timestep. The error bound was set to be 0.04% of the width of the Lucy.

Abstract: We present a novel approach for collision detection between large models composed of tens of millions of polygons. Each model is represented as a clustered hierarchy of progressive meshes (CHPM). CHPM is a dual hierarchy of the original model; it serves both as a multiresolution representation of the original model, as well as a bounding volume hierarchy. We use the cluster hierarchy of a CHPM to perform coarse-grained selective refinement and the progressive meshes for fine-grained local refinement. We present a novel conservative error metric to perform collision queries based on the multiresolution representation. We use this error metric to perform dynamic simplification for collision detection. Our approach is conservative in that it may overestimate the set of colliding triangles, but never misses collisions. Furthermore, we are able to generate these hierarchies and perform collision queries using out-of-core techniques on all triangulated models. We have applied our algorithm to perform conservative collision detection between massive CAD and scanned models, consisting of millions of triangles at interactive rates on a commodity PC.

Figure 2: CHPM Hierarchy. We represented the scene as a clustered hierarchy of progressive meshes (CHPM). The CHPM serves as a dual hierarchy: an LOD hierarchy for conservative errorbounded collision and as a bounding volume hierarchy for collision culling. Each cluster contains a progressive mesh and a bounding volume that encloses all geometry in its subtree.


Paper: Fast Collision Detection between Massive Models using Dynamic Simplification , To appear in the Proceeding of the Eurographics Symposium on Geometry Processing, 2004

Related Links

Quick-VDR: Interactive View-Dependent Rendering of Massive Models

UNC Walkthru Group

CB #3175, Department of Computer Science
University of North Carolina
Chapel Hill, NC 27599-3175