Abstract and Contents

We describe an approach for interactive collision detection and proximity computations on massive models composed of millions of geometric primitives. We address issues related to interactive data access and processing in a large geometric database, which may not fit into main memory of typical desktop workstations or computers. We present a new algorithm using overlap graphs for localizing the "regions of interest" within a massive model, thereby reducing runtime memory requirements. The overlap graph is computed off-line, pre-processed using graph partitioning algorithms, and modified on the fly as needed. At run time, we traverse localized sub-graphs to check the corresponding geometry for proximity and pre-fetch geometry and auxiliary data structures. To perform interactive proximity queries, we use bounding-volume hierarchies and take advantage of spatial and temporal coherence. Based on the proposed algorithms, we have developed a system called IMMPACT and used it for interaction with a CAD model of a power plant consisting of over 15 million triangles. We are able to perform a number of proximity queries in real-time on such a model.

This research is documented in "Partitioning and Handling Massive Models for Interactive Collision Detection", a paper submitted to Eurographics 1999. Images and video footage documenting IMMPACT, the system described in the paper, are available below. The paper itself (gzipped Postscript, 416K) can be downloaded as well.

Images

Model Pictures

These images show interesting portions of the power plant model.

	Environments such as this, with dense, complex geometry to either side of a narrow path, are difficult to handle when testing for clearance.
	A group of pipes farther up in the power plant near the 45th floor. These pipes are a single object in the original model.

Avatar Pictures

To simulate testing for clearance and maintenance accessibility, we allow the user to move an articulated avatar through the model.

	Valves near the walkways of the power plant are meant to be accessible to engineers.
	The avatar near a valve, testing for proximity and accessibility.
	The avatar touching the valve above.
	This pipe array, with its non-axis-aligned geometry, is a difficult case for the axis-aligned bounding boxes which work well for the rest of the model.

Other Object Pictures

These scenes show sample objects being used for proximity tests.

Proximity test performed with a proximity threshold of 10mm.	Same test with a threshold of 300mm.
Same test, with a threshold of 500mm.	Same test, with a threshold of 1 meter.
	A wrench is being tested against a group of pipes. The entire array of yellow pipes was a single object in the original model; here, we have subdivided it into several smaller objects.

---