Voronoi Scissors: Approximate Dissection of 2D Shapes with Continuous Optimization

Abstract

The dissection of planar shapes into a common set of reusable pieces is a classical problem, with connections to geometry processing, fabrication, and design. Despite its long-standing interest, the problem remains challenging due to the interplay of geometric constraints and combinatorial complexity. Existing approaches are limited to exact dissection of simple polygonal shapes, or can only handle a small number of pieces and introduce significant distortion when performing approximate dissection of more complex shapes. We present a fully automatic method for dissecting two-dimensional shapes into a shared set of pieces that can be rearranged to approximate multiple target configurations. Our approach formulates the problem as a hybrid optimization pipeline. We first perform a continuous optimization based on a Voronoi-driven decomposition to generate an initial partition. This is followed by a global optimization step that determines a consistent rearrangement of pieces while enforcing structural constraints required for valid, rigid, and non-overlapping assemblies. The final refinement stage refines the solution to best approximate the input shapes. Our method guarantees that all pieces admit rigid, non-overlapping rearrangements. Moreover, our pieces are more compact and yield less distortion than the ones obtained by prior work. We demonstrate the generality of our approach across novel dissection scenarios, including multi-shape rearrangements, shapes with complex topology, and reuse-driven settings where a fixed source shape is partitioned to approximate a target.

Nobuyuki Umetani

Associate Professor

My research interests include interactive smart engineering design tool using physics simulation and machine learning.