Journal
ACM TRANSACTIONS ON GRAPHICS
Volume 36, Issue 6, Pages -Publisher
ASSOC COMPUTING MACHINERY
DOI: 10.1145/3130800.3130831
Keywords
Computational Geometry; Dissection
Categories
Funding
- National Science Foundation [1565978]
- Office of the Vice Provost for Research and Strategic Initiatives
- Singapore MOE [MOE2016-T2-2-154]
- National Heritage Board of Singapore
- SUTD Digital Manufacturing and Design (DManD) Centre
- National Research Foundation (NRF) of Singapore
- NRF under IDM Futures Funding Initiative and Virtual Singapore [NRF2015VSG-AA3DCM001-014]
Ask authors/readers for more resources
A geometric dissection is a set of pieces which can be assembled in different ways to form distinct shapes. Dissections are used as recreational puzzles because it is striking when a single set of pieces can construct highly different forms. Existing techniques for creating dissections find pieces that reconstruct two input shapes exactly. Unfortunately, these methods only support simple, abstract shapes because an excessive number of pieces may be needed to reconstruct more complex, naturalistic shapes. We introduce a dissection design technique that supports such shapes by requiring that the pieces reconstruct the shapes only approximately. We find that, in most cases, a small number of pieces suffices to tightly approximate the input shapes. We frame the search for a viable dissection as a combinatorial optimization problem, where the goal is to search for the best approximation to the input shapes using a given number of pieces. We find a lower bound on the tightness of the approximation for a partial dissection solution, which allows us to prune the search space and makes the problem tractable. We demonstrate our approach on several challenging examples, showing that it can create dissections between shapes of significantly greater complexity than those supported by previous techniques.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available