The Algorithm Design Manual
About the Book
Programming Challenges

The Stony Brook Algorithm Repository

Steven Skiena
Stony Brook University
Dept. of Computer Science

V-CLIP - Collision detection algorithm for polyhedral objects

The Voronoi Clip, or, V-Clip , algorithm is a low-level collision detection algorithm for polyhedral objects. The V-Clip library is a C++ implementation of this algorithm, with facilities for constructing and manipulating geometries. The source code is freely distributed for educational, research and non-profit purposes. Permission to use the library in commercial products may be obtained from MERL - A Mitsubishi Electric Research Lab, 201 Broadway, Cambridge, MA 02139.

The major design goals of V-Clip were robustness and efficiency. The implementation works well even in the presence of geometric degeneracies and contains no floating point tolerances for the user to tune. It compares favorably to other algorithms from and efficiency standpoint (see the tech report for details). In typical applications V-Clip computes the closest points between objects in almost constant time.

V-Clip operates on polyhedral objects which may be nonconvex or even disconnected. It returns the closest points between objects and the distances between them. If the objects penetrate, it returns a penetration depth. V-Clip requires the application to specify nonconvex or disconnected objects as hierarchies of convex pieces. When called on disjoint nonconvex objects,V-Clip returns a lower bound on the actual distance between the objects.

  • Download Files (local site)
  • Merl's site for V-CLIP

    Problem Links

    Intersection Detection (9)

    This page last modified on 2008-07-10 .