V-Clip Collision Detection Library
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.
Background & Objective: 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.
Technical Discussion: 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.
|V-Clip: Fast and Robust Polyhedral Collision Detection|
Research Area: Graphics
Modification Date: July 7, 2008