Virtual woodwork: Making toys from geometric models

Shape idealization techniques provide a simplified description of a geometric model. Idealized descriptions are useful for recognition, animation, and other applications, providing a compact and efficient alternative to manipulating the complete model. Often idealized models are visually interesting in their own right and provide an appealing artistic impression of the models. We describe an algorithm for automatic generation of idealized bead figures from recognizable 3D models (animals, humans, etc.). The bead figures approximate the model by a set of cylindrical shapes threaded onto a skeleton of the model. As such, they provide volumetric shape information in addition to the skeleton. The bead figures can be used by applications requiring a simple and compact description of the shapes. They also provide a visually appealing, toy-like description which can be used in artistic applications. The input models are given as 3D triangulated meshes. A bead figure is generated using the skeleton of the model, often referred to as the "stick figure". The skeleton reflects the structure of the original mesh and its features, using a small number of edges. Once the skeleton is computed, beads are threaded onto it to create the final model. Computation of a compact and concise skeleton which captures the features of the model is crucial for realistic bead figure generation. The figure making process involves voxelization of the model; computation of the 3D Euclidean distance transform (DT); extraction of the skeleton from the DT data (combined with the model's curvature information); and threading the beads over the skeleton. In addition to the generation of the beaded figures, our work also introduces a novel skeleton construction algorithm. The algorithm has several advantages over existing methods and may be used in other applications which utilize skeletons.