In this paper, we accelerate self-collision detection (SCD) for a deforming triangle mesh by exploiting the idea that a mesh cannot self collide unless it deforms enough. Unlike prior work on subspace self-collision culling which is restricted to low-rank deformation subspaces, our energy-based approach supports arbitrary mesh deformations while still being fast. Given a bounding volume hierarchy (BVH) for a triangle mesh, we precompute Energy-based Self-Collision Culling (ESCC) certificates on bounding-volume-related sub-meshes which indicate the amount of deformation energy required for it to self collide. After updating energy values at runtime, many bounding-volume self-collision queries can be culled using the ESCC certificates. We propose an affine-frame Laplacian-based energy definition which sports a highly optimized certificate preprocess, and fast runtime energy evaluation. The latter is performed hierarchically to amortize Laplacian energy and affine-frame estimation computations. ESCC supports both discrete and continuous SCD with detailed and nonsmooth geometry. We demonstrate significant culling on various examples, with SCD speed-ups up to 26X.

• Paper (21M)
• Supplemental Video [high quality (175M)]

Changxi Zheng and Doug L. James, Energy-based Self-Collision Culling for Arbitrary Mesh Deformations, ACM Transaction on Graphics (SIGGRAPH 2012), 31(4), August, 2012.

We release our animation data used in this project under GNU GPL license. You can download them from the following links. The data include the animation frames (as .obj files) and our connected bounding volume hierarchies.

• the flowing cloth (163M)
• a monkey falling on the ground (381M)
• a squishy ball (6.0G)

• The National Science Foundation (HCC-0905506)
• The Alfred P. Sloan Foundation
• The John Simon Guggenheim Memorial Foundation
• Intel (ISTC-VC)
• Pixar Animation Studio
• Autodesk
• Mitsuba Renderer