Scaling method speeds up fixing overlapping rigid bodies in 3d scenes
S4R: Scaling for Rigid-Body Interpenetration Resolution
GraphicsComputational GeometryRobotics
Summary
When 3D objects overlap inside a virtual scene, it causes problems for animations and physics simulations. The authors introduce S4R, a new way to fix these overlaps by shrinking all objects, separating them while small, then gradually restoring their size. This approach breaks a big problem into many smaller, easier steps, making the process faster and more accurate. Their tests show it works well on scenes with thousands of objects and can run efficiently on graphics cards.
What this means in practice
- •For game developers: Quickly fix overlapping 3D objects in complex game scenes to ensure realistic physics and animation.
- •For simulation engineers: Clean up virtual environments with many static objects to prepare accurate inputs for physics-based simulations.
Authors
Zhiyang Dou, Ang Zhao, Chen Peng, Minghao Guo, Haixu Wu, Cheng Lin, Yuan Liu, Junfeng Yao, Xiaohu Guo, Wenping Wang, Wojciech Matusik
Abstract
Rigid-body interpenetration frequently occurs in procedurally assembled and generated scenes and must be removed before downstream applications such as physical simulation. We present S4R (Scaling for Rigid-Body Interpenetration Resolution), a scale-continuation method for static interpenetration repair. S4R first uniformly shrinks each body about a fixed reference center to a small initial scale, at which the layout is penetration-free, and then restores full scale through a sequence of minimum-norm convex contact quadratic programs (QPs) that target the linearized separation margin during continuation. Resolution thereby replaces one deep correction with a sequence of shallow-contact subproblems. A conservative scale-event bound and frozen-witness gap predictions cut the number of exact mesh queries; the continuation then ends with a full-scale evaluator check and bounded tail refinement. We evaluate S4R on Kubric, HY3D-Bench, and Thingi10K using a shared mesh-level evaluator and a unified per-scene timing protocol. In the main comparisons on all three benchmarks, up to N=5000 bodies, S4R reaches zero reported penetration with displacement that stays small and nearly independent of scene size, and at the lowest wall time within each hardware tier among the compared methods. A GPU implementation extends these results to large-scale scenes. Our code and data can be found on our project page: https://frank-zy-dou.github.io/projects/S4R/index.html.