V-Clip

V-Clip: fast and robust polyhedral collision detection. This article presents the Voronoi-clip, or V-Clip, collision detection alogrithm for polyhedral objects specified by a boundary representation. V-Clip tracks the closest pair of features between convex polyhedra, using an approach reminiscent of the Lin-Canny closest features algorithm. V-Clip is an improvement over the latter in several respects. Coding complexity is reduced, and robustness is significantly improved; the implementation has no numerical tolerances and does not exhibit cycling problems. The algorithm also handles penetrating polyhedra, and can therefore be used to detect collisions between nonvconvex polyhedra described as hierarchies of convex pieces. The article presents the theoretical principles of V-Clip, and gives a pseudocode description of the algorithm. It also documents various test that compare V-Clip, Lin-Canny, and the Enhanced GJK algorithm, a simplex-based algorithm that is widely used for the same application. The results show V-Clip to be a strong contender in this field, comparing favorably with the other algorithms in most of the tests, in term of both performance and robustness.


References in zbMATH (referenced in 11 articles )

Showing results 1 to 11 of 11.
Sorted by year (citations)

  1. Wilke, Daniel N.; Govender, N.; Pizette, Patrick; Abriak, N. -e.: Computing with non-convex polyhedra on the GPU (2017)
  2. Lim, Keng-Wit; Krabbenhoft, Kristian; Andrade, José E.: A contact dynamics approach to the granular element method (2014)
  3. Kiel, Stefan; Luther, Wolfram; Dyllong, Eva: Verified distance computation between non-convex superquadrics using hierarchical space decomposition structures (2013) ioport
  4. Dyllong, Eva; Kiel, Stefan: A comparison of verified distance computation between implicit objects using different arithmetics for range enclosure (2012)
  5. Alonso-Marroquín, Fernando; Wang, Yucang: An efficient algorithm for granular dynamics simulations with complex-shaped objects (2009)
  6. Fares, Charbel; Hamam, Yskandar: Optimisation-based proximity queries and penetration depth computation (2009) ioport
  7. Velić, Mirko; May, Dave; Moresi, Louis: A fast robust algorithm for computing discrete Voronoi diagrams (2009)
  8. Li, C. F.; Feng, Y. T.; Owen, D. R. J.: SMB: Collision detection based on temporal coherence (2006)
  9. Yang, Chenglei; Qi, Meng; Meng, Xiangxu; Li, Xueqing; Wang, Jiaye: A new fast algorithm for computing the distance between two disjoint convex polygons based on Voronoi diagram (2006)
  10. Buss, Samuel R.: Collision detection with relative screw motion (2005) ioport
  11. Mirtich, Brian: V-Clip. fast and robust polyhedral collision detection. (1998) ioport