Chapper: Carvable Hull-and-Pack for Subtractive Manufacturing

Tightly cutting raw materials into a set of carvable objects, known as the stock cutting problem, is a necessary step in subtractive manufacturing. This problem can be framed as a 3D irregular object packing task, aiming to fit as many objects as possible within a predefined container. While previous packing algorithms can generate dense, non-overlapping, and even disassemblable configurations, they cannot satisfy carvable constraints. This paper introduces the carvable hull-and-pack problem, which integrates irregular object packing with subtractive manufacturing. This problem is more challenging than general 3D packing, as it requires ensuring the carvability of each object and generate the disassembly sequence. To address this, we first define a novel geometric hull, called carving hull , which accounts for both the object's shape and the cutter accessibility, constrained by the real-time distribution of surrounding objects. Then we present Chapper , an effective solution to co-optimize carving hull packing and the planning of disassembly sequence to maximize space utilization while preserving the carvable constraints. Given a raw material and a list of generic 3D objects, our algorithm starts with densely packing each object into the material with a pre-computed placement order, while simultaneously maintaining a valid disassembly sequence. We solve the complex object-to-object and cutter-to-object collisions by leveraging a discrete voxel representation. The carvability of each object is also guaranteed in the packing process, where we define a novel carvable metric to determine whether each object is carvable or not. Based on the packing result and the disassembly sequence, we propose a clipped Voronoi-based volume decomposition method to generate the actual carving hull for each object and finally create feasible cutting tool paths on the carving hulls. Our approach effectively packs CAD and freeform datasets, exhibiting a unique space utilization rate performance compared to the alternative baseline.