A Fast Method for Local Penetration Depth Computation

Stephane Redon and Ming C. Lin

Department of Computer Science
University of North Carolina at Chapel Hill

Two polyhedral bunnies (48,000 triangles each) intersect. Our algorithm clusters the intersection segments into a single intersection curve (left, highlighted in the center part), and determines the corresponding penetration direction and depth, which allows to separate the bunnies (right), in less than three milliseconds.

Abstract

This paper presents a fast method for determining an approximation of the local penetration information for intersecting polyhedral models. As opposed to most techniques, this algorithm requires no specific knowledge of the object's geometry or topology, or any pre-processing computations. In order to achieve real-time performance even for complex, nonconvex models, we decouple the computation of the local penetration directions from the computation of the corresponding local penetration depths: for any pair of intersecting objects, we partition the penetrating zones into coherent regions, and we determine for each of these regions a local penetration direction. Then, for each of these regions, we estimate a local penetration depth in the previously computed penetration direction. This method has been implemented and tested on a 2.0 GHz Pentium PC with a NVIDIA GeForce FX 5900 graphics card with AGP 4x and 768MB of RAM. The examples indicate that a meaningful local penetration information can be computed for complex models and challenging intersection scenarios within a few milliseconds.

      Download paper
      Download appendix


Authors' pages:
      Stephane Redon
      Ming C. Lin

Examples

Three penetration depth scenarios. (a) Even in case of a complex intersection scenario, our algorithm determines a satisfying partitioning of the intersection segments, and the corresponding local penetration information. (b) Holes in the base of the bunnies (left) lead to open intersection curves appropriately detected by our algorithm (center), still allowing to precisely separate the objects (right). (c) Two dragon models (300,000 triangles each) intersect (left). Our algorithm clusters 1,491 intersection segments in a single curve (center) and determines a penetration information which allows to precisely separate the objects (right), in 9.5 milliseconds.

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.

Last revision : October 17, 2005