Premium
Generalized Matryoshka: Computational Design of Nesting Objects
Author(s) -
Jacobson Alec
Publication year - 2017
Publication title -
computer graphics forum
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.578
H-Index - 120
eISSN - 1467-8659
pISSN - 0167-7055
DOI - 10.1111/cgf.13242
Subject(s) - nesting (process) , computer science , object (grammar) , replica , scale (ratio) , variety (cybernetics) , orientation (vector space) , distributed computing , theoretical computer science , computer graphics (images) , artificial intelligence , mathematics , geometry , geography , materials science , cartography , archaeology , metallurgy
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.