«A GRAPH GRAMMAR BASED APPROACH TO 3D PRINT AND ASSEMBLE FURNITURE Sulabh Gupta and Rahul Rai Design Analytics Research and Technology (DART) Lab, ...»
A GRAPH GRAMMAR BASED APPROACH TO 3D PRINT AND ASSEMBLE
Sulabh Gupta and Rahul Rai
Design Analytics Research and Technology (DART) Lab,
Department of Mechanical and Aerospace Engineering,
University at Buffalo-SUNY, Buffalo-NY, 14260
A Plethora of user generated 3D models are available online. With rapid proliferation and
diffusion of additive manufacturing machines in households, it has now become possible to download these virtual objects and print them out as physical parts. Although printing small size parts (within print volume of low cost 3D printers) is relatively an easy task, additive fabrication of large size parts (part volumes greater than print volume of low cost 3D printer) remains a challenging task for novice 3D printer users. In this paper the authors present a computational pipeline to 3D print large size 3D models that can be easily downloaded from online websites.
The pipeline essentially enables decomposition of large objects into smaller parts that can be 3D printed and then assembled. To assemble the printed parts a three-pronged approach is outlined.
First, an interface based on graph grammar rules has been developed to generate assembly instructions. Second, an interactive segmentation of the desired 3D model is carried out using a Segmentation Guide Interface (SGI). SGI has been developed to assist a user to carry out component to sub-component segmentation. Third, we have also developed an interface that aids a user in printing small size pieces that can be printed in print volume of a commercial 3D printer (such as Makerbot®) and then assembled to create components that are too large to be printed in print volumes of low cost 3D printers. We demonstrate the efficacy of developed pipeline by creating assembly instructions for multiple large sized 3D table models available online.
Introduction The rapid development in 3D printing field has resulted in the beginning of a new era in personal fabrication. 3D printers are easy to use and are capable of printing almost any 3D CAD model. The widespread availability of 3D CAD models online has further stimulated personal fabrication. For example, online repositories have far more varieties of virtual furniture models than real ones in your nearby furniture store.
Our goal is to enable individual users to 3D print their favorite 3D models by leveraging online shape repositories. In personal fabrication domain 3D printing until now has mostly been used for printing objects for trivial use or showpieces. In order to achieve large scale acceptance 3D printers should break free from their stereotypical personal fabrication use and print objects that have more practical utility. It has been observed that the maximum size of an object that a domestically affordable 3D printer can fabricate in one pass (the printing volume) is limited by practical considerations. This problem has curbed the large scale adoption of low cost 3D printers. Larger objects must therefore be printed as multiple separate parts and assembled.
In this paper, we outline a computational pipeline to 3D print large size 3D models available online. Using the computational pipeline a user can semantically segment the 3D model into its component parts. Once the segmentation is completed the user is provided guidance in slicing the individual components into primitive shapes (sub components) which can be printed in the limited build volume of commercially available 3D printers. The pipeline provides basic information to a user such as the number of sub-components required for each component, the shape of each sub-component and how to assemble the sub-components once they are printed.
Additionally, we have developed a graph grammar based technique to generate assembly instructions. The generated assembly instruction joins components using off-the-shelf connectors found in furniture assembly domain.
Our key contributions are:
(1) We outline a computational pipeline that guides a user to 3D print large parts in commercially available 3D printers by segmenting them into smaller and printable sizes.
(2) We have developed a set of new graph grammar rules that can be used for generating assembly instructions to assemble furniture like tables.
We demonstrate the validity of our computational pipeline by generating assembly instruction of 3D models of IKEA-style tables downloaded from Google 3DWarehouse, Princeton Shape Benchmark, and Polantis. All our test models have arbitrary topology and structure. None of the 3D table models have the geometry or connector information needed for fabricating them.
Related Work In the present section, three key areas related to the presented research namely (1) 3D printing (2) Graph Grammar, and (3) Mesh segmentation are briefly reviewed.
3D Printing With the advancement of 3D printing we are witnessing the first stages of manufacturing democratization. It is believed that individual users will play a role in designing and creating their own products in the future [Gross 2007, Landay 2009]. Users can readily build their own customized products like plush toys [Mori, et.al 2007], chairs [Luo, et.al 2012], furniture [Lau, et al. 2011], garments [Umetani et al. 2011], Burr puzzles [Xin et al. 2011], and planar sections [McCrae et al. 2011, Hildebrand et al. 2012]. The current trend portends to revolutionize design and fabrication and could possibly give rise to a new class of creators and products [Mota, 2011].
We aim to propel this trend further. While the professional and higher end 3D machines are capable of producing large complex objects, the personal and less costly 3D printers are constrained by their print size and cost. The limited print volume of affordable 3D printers is the main cause of their limited usage. Efforts are been made to overcome these barriers.
Luo et.al,  has developed a new method called “chopper”. Chopper can be used to chop a given large objects into smaller pieces. These smaller pieces can be printed in 3D printers and assembled to create a large object. This method automatically generates male and female connectors on the cut surfaces. Once the object is printed, the user can assemble the parts without any assembly instructions. This method focuses on printing showpieces and the connectors generated do not provide much structural rigidity to the printed parts. In the computational pipeline outlined in this paper, a set of assembly instructions are generated to guide the user in assembling the 3D printed parts. The connectors used to assemble the parts are off-the-shelf connectors and the placement of these connectors provides structural rigidity to the final assembled part.
Lau et.al,  developed a graph grammar technique to create assembly instructions for virtual furniture models. In their work, the end user has the ability to use the assembly instructions to build furniture models with standard tools and wooden materials. In the presented work, we guide the user to segment the 3D model into small parts. These segmented parts can be 3D printed in the limited build volume of low cost 3D printers. We then use graph grammar rules to generate assembly instructions for the printed models. The user can have little to no experience of working with tools.
Graph Grammar Graph grammars have found applications in various fields such as concurrent systems, engineering, programming languages, and biology. It has been used to develop methods for understanding and modelling new architecture [Stiny 1980], cities [Parish, et.al 2001], buildings [Muller, et.al 2006] and details of facades [Wonka, et.al 2003]. Coffee maker grammar was one of first examples of using grammars for product design [Agarwal, et.al 1998]. Their grammar described a language that generates a large class of coffee makers. Shea et.al,  presented a parametric shape grammar for the design of truss structures that uses recursive annealing techniques for topology optimization. Other engineering applications include lathe grammar [Brown, et.al 1997], grammar for machine design [Schmidt, et.al 1995], grammars for mechanical clocks [Starling, et.al 2003] and gear trains in [Starling, et.al 2005]. One of the interesting implementations of graph grammars is in the area of function-based design [Sridharan, et.al 2004]. In more recent applications graph grammar has been used to develop new design concepts to represent different topologies, configurations or shapes within a single search space [Rai, et.al 2011]. Lau et.al,  have used graph grammar techniques to generate assembly instructions for shelves, cabinets, and tables to build with standard wooden materials.
We have developed graph grammar rules for generating assembly instructions for printing large size 3D printed objects. The novelty of our work is in the fact that a novice user can use our pipeline to easily assemble the 3D printed parts.
Mesh Segmentation In our work we segment the 3d model manually into its component parts. This is enabled through mesh segmentation techniques. Mesh segmentation techniques can be based on curvature and geodesic distances [Mangan, et.al 1999], dihedral angles [Shlafman, et.al 2002], Planarity and normal direction [Coheh-Stiner, et.al 2004, Attene, et al 2006], and Slippage [Gelfand, et.al 2004]. These attributes are sensitive to local surface features and to pose changes.
Therefore, these techniques are not suitable for segmenting the same object in different poses.
Topology-based approaches like spectral analysis [Liu, et.al 2004], average geodesic distance (AGD) [Hilaga, et.al 2001] and Reeb-graphs [Attene, et.al 2003] can be used for mesh segmentation of object in different poses. Nevertheless, they are vulnerable to topological and connectivity changes and do not distinguish well between shape differences.
In our work we use Shape Diameter Function (SDF). The Shape-Diameter Function (SDF) is a scalar function defined on the mesh surface. It expresses a measure of the diameter of the object's volume in the neighborhood of each point on the surface. Using the SDF one can easily segment 3D models and perform part-retrieval [Shapira, et.al 2008].
Figure 1: Flowchart showing different steps of computational pipeline for printing and assembling parts bigger than the print volume of 3D printers.
(Figure 1) illustrates the overall framework of the developed pipeline. The pipeline can accept 3D CAD models as input in any one of the following two ways: (1) A 3D CAD model created using CAD software like SolidWorks, CATIA, or PRO-E, or (2) A 3D CAD model obtained from online repositories such as Google Warehouse, Princeton Shape Benchmark, and Polantis.
The Semantic Segmentation Interface (SSI) is used to segment the inputted 3D CAD models into component parts. Each segmented part is saved individually. The SSI is based on SDF [Shapira, et.al 2008]. In order to carry out Semantic Segmentation using SDF vertex and face information is required. As a result it has to be ensured that the CAD model is in.obj format. If the input 3D model is not in.obj format then MeshLab software can be used to convert the 3D CAD file into the required (.obj) format.
GraphSynth (a graph grammar software) is used to create assembly instructions to assemble the segmented parts. For assembly instruction generation we have developed twentyfour rule graph grammar that defines different ways to assemble tables (Table 1). By simply executing different combinations of grammar rules, assembly instructions for a variety of tables can be generated. A user skilled in wood working can use the instructions generated by GraphSynth to make the object using wood and simple fasteners.
In our proposed approach it has been assumed that a user has little or no experience with wood working tools. As a result our computational pipeline enables a not-so-skilled user to 3D print the parts. 3D printers require the input files to be in.stl format as a result the segmented components that are in.obj format have to be converted to.stl format..obj to.stl format conversion can also be carried out using MeshLab. In case segmented 3D components do not fit in the build volume of the 3D printer they are further segmented. We further segment the components into sub-components using slicing software called netfabb Basic.
The printed sub-components are assembled to create components. The components are then assembled to create the overall object by using the assembly instructions generated by graph grammar interface. The tool components and the associated methods are described in detail in the following sub-sections.
Semantic Segmentation Interface (SSI)
Figure 2: (a) Semantic Segmentation Interface, (b) Semantic segmentation carried out by drawing a boundary around the part to be segmented, (c) Segmented table top, (d) The segmented table into its constituent parts There is lack of assembly information in the 3D models available online and most of the 3D models are stored as a single part. The Semantic Segmentation Interface (SSI) is used to semantically segment 3D CAD models into component parts (Figure 2a). SSI is based on a volume-based shape-function called the shape-diameter function (SDF). The SDF is a scalar function deﬁned on the mesh surface. In essence it represents a measure of the diameter of the object’s volume in the neighborhood of each point on the surface [Shapira et al 2008]. In order to carry out Semantic Segmentation using SDF, vertex and face information is required. As a result it has to be ensured that the input 3D CAD model is in.obj format. If the inputted 3D CAD model is not in.obj format then MeshLab can be used to convert it into.obj format. User through interaction with SSI segments the 3D CAD model by drawing a box around the part (Figure 2b).
The user can also select different colors to color segmented parts in different colors. This helps in differentiating different segmented parts. Each part can then be exported separately.
Graph Grammar for generating assembly instructions
Graph grammars are comprised of rules for manipulating nodes and arcs within a graph.
In our computational pipeline the graph grammar rules specify a formal language for generating assembly instructions from an initial user defined graph (seed graph). The development of these rules encapsulates a set of valid operations that can be used to assemble different parts of a table.