Fast Collision Detection between Massive Models using Dynamic Simplification

Yoon, Sung-Eui; Salomon, Brian; Lin, Ming; Manocha, Dinesh

Fast Collision Detection between Massive Models using Dynamic Simplification

Files

139-150.pdf (2.05 MB)

Date

2004

Authors

Yoon, Sung-Eui
Salomon, Brian
Lin, Ming
Manocha, Dinesh

Publisher

The Eurographics Association

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). The 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 regions, but never misses any 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.

        @inproceedings{:10.2312/SGP/SGP04/139-150
,
booktitle = {Symposium on Geometry Processing
},
editor = {Roberto Scopigno and Denis Zorin
},
title = {{Fast Collision Detection between Massive Models using Dynamic Simplification
}},
author = {Yoon, Sung-Eui and 
Salomon, Brian and 
Lin, Ming and 
Manocha, Dinesh
},
year = {2004
},
publisher = {The Eurographics Association
},
ISSN = {1727-8384
},
ISBN = {3-905673-13-4
},
DOI = {/10.2312/SGP/SGP04/139-150
}
}