Energy-based Self-Collision Culling for Arbitrary Mesh Deformations

Figure 1: A squishy ball with 820 tentacles and over 1 million triangles, squishes and bounces on the ground, inducing numerous small interpenetrations. Our Energy-based Self-Collision Culling (ESCC) method accelerates self-collision detection (SCD) for arbitrarily deforming triangle meshes, such as this mesh animated using Oriented Particles [Müller and Chentanez 2011]. We observe an 11.5 × speedup over an optimized AABB-Tree SCD implementation on this challenging example. 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 observe significant culling on many examples, with SCD speed-ups up to 26×. Links: DL PDF WEB