Generalized Matryoshka: Computational Design of Nesting Objects. (14th August 2017)

• Record Type: Journal Article
• Authors: Jacobson, Alec
• Is Part Of: Computer graphics forum. Volume 36:Number 5(2017)
• Page Start: 27
• Page End: 35
• Publication Date: 2017-08-14
• Subjects: Computer graphics -- Periodicals; 006.605
• DOI: 10.1111/cgf.13242
• Languages: English
• ISSNs: 0167-7055

Abstract

Abstract: This paper generalizes the self‐similar nesting of Matryoshka dolls ("Russian nesting dolls") to arbitrary solid objects. We introduce the problem of finding the largest scale replica of an object that nests inside itself. Not only should the nesting object fit inside the larger copy without interpenetration, but also it should be possible to cut the larger copy in two and remove the smaller object without collisions. We present a GPU‐accelerated evaluation of nesting feasibility. This test can be conducted at interactive rates, providing feedback during manual design. Further, we may optimize for some or all of the nesting degrees of freedom (e.g., rigid motion of smaller object, cut orientation) to maximize the smaller object's scale while maintaining a feasible nesting. Our formulation and tools robustly handle imperfect geometric representations and generalize to the nesting of dissimilar objects in one another. We explore a variety of applications to aesthetic and functional shape design.