PolyDepth: Real-time Penetration Depth Computation
using Iterative Contact-Space Projection

Changsoo Je 1,2       Min Tang1     Youngeun Lee1     
Minkyoung Lee
1      Young J. Kim1

1-Ewha Womans University, Seoul, Korea

 2-Korea Institute of Patent Information, Seoul, Korea



Ewha Technical Report CSE-TR-2010-02

ACM Transactions on Graphics* , 31(3), Jan 2012 (to be presented in SIGGRAPH 2012)

Source Codes


[Abstract]  We present a real-time algorithm that finds the penetration depth (PD) between general polygonal models based on iterative and local optimization techniques. Given an in-collision configuration of an object in configuration space, we find an initial collision-free configuration. We project this configuration on to a local contact space using a variant of continuous collision detection algorithm and construct a linear convex cone around the projected configuration. We then formulate a new projection of the in-collision configuration on to the convex cone as a linear complementarity problem (LCP), which we solve using a type of Gauss-Seidel iterative algorithm. We repeat this procedure until a locally optimal PD is obtained. Our algorithm can process complicated models consisting of tens of thousands triangles at interactive rates.




(Download 103M)


Benchmarking Scenarios

Benchmarking models with triangle counts. Top row: Buddha (10k), Bunny1 (1k), Bunny2 (40k), Cup (1k), Distorted-torus (1.33k), Dragon (174k), Golf-club (105k) Bottom row: Grate1 (0.54k), Grate2 (0.94k), Santa (152k), Spoon (1.34k), Torus (2k), and Torusknot (3K).



The complexities of these models range from 0.54k to 174k triangles, and their topologies contain many holes and self-intersections (i.e. polygon-soups). We constructed a number of benchmarking scenarios for these models, including random configurations, predefined sequences, and collisions within a rigid-body dynamics simulation.



PolyDepth Performance in
a Random Configuration Scenario

Model Time (msec) No. of Contacts No. of Iterations
Torusknot 5.53 4.84 2.81
Buddha 6.23 5.04 1.92
Bunny2 7.55 8.25 2.16
Dragon 12.76 11.92 2.29




PolyDepth Performance in
a Predefined Path Scenario

Model Time (msec) No. of Contacts No. of Iterations
Spoon and Cup 0.96 4.49 1.02
Buddha 3.50 5.07 1.29
Dragon 5.84 10.32 1.45



PolyDepth Performance in
a Dynamics Scenario

Model Global PD (msec) Local PD (msce) Total (msec)
Torus 3.13 1.04 4.17
Bunny2 5.43 1.78 7.21
Golf-club 4.87 1.67 6.54
Santa 9.14 2.90 12.04

Related Links







Copyright 2010 Computer Graphics Laboratory
Dept of Computer Science & Engineering
Ewha Womans University, Seoul, Korea
Last update: July 23, 2010