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

Changsoo Je^1,2 Min Tang¹ Youngeun Lee¹
Minkyoung Lee¹ Young J. Kim¹

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.

Video

(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

Ewha Technical Report CSE-TR-2010-02

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

Source Codes

Benchmarking Scenarios

Related Links