Fast Cutting of Cage Based Deformation with Walk on Spheres

Abstract

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 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 a local cut in most practical cases. We propose a reuse pipeline that efficiently updates only the weights affected by topological modifications. Our approach leverages WoS as an output-sensitive, mesh-free Monte Carlo method for solving Laplacian equations, enabling localized harmonic-weight updates. By identifying and reusing unaffected walks, we minimize re-walking work and preserve statistical accuracy. Our method achieves 10x-40x speedups while remaining statistically identical to full WoS recomputation. This enables real-time interactive cutting on complex 2D and 3D cages, and readily generalizes to other local cage editing operations.

Video

@inproceedings{saeed2026woscut,
	title     = {Fast Cutting of Cage Based Deformation with Walk on Spheres},
	author    = {Saeed, Hossam and Lambiri, Michael and Schneider, Teseo and Nowrouzezahrai, Derek and Kry, Paul G.},
	booktitle = {ACM SIGGRAPH 2026 Conference Papers},
	year      = {2026},
	doi       = {10.1145/3799902.3811051},
	url       = {https://doi.org/10.1145/3799902.3811051}
}