Fast Cutting of Cage Based Deformation with Walk on Spheres

摘要

While cages provide a powerful reduction model to simulate elastic deformations, interactive real-time cutting of cages has been a longstanding challenge. Traditional solvers require costly volumetric re-meshing and global matrix updates after each modification. For a mesh-free harmonic weight computation using walk on spheres (WoS), we make a key observation: only a small fraction of walks (5-10%) is invalidated by the local cut in most practical cases. We propose a novel reuse pipeline to efficiently update only weights subject to a topological modification. Our approach leverages walk on spheres as an output sensitive and mesh-free Monte Carlo method for solving Laplacian equations, to enable localized updates of harmonic weights. By identifying and reusing unaffected walks, we minimize our re-walking updates. Our method achieves speedups of 10 × -40 × while being statistically identical to a complete WoS weight recomputation. This enables a real time simulation of interactive cutting on complex 2D and 3D cages, and is easily generalizable to other local cage editing operations.