A three-dimensional algorithm using two-dimensional slice data for building multiple parts in layered manufacturing

In a rapid prototyping process, the time required to build multiple prototy pe parts can be reduced by building several parts simultaneously in a work volume. Interactive arrangement of the multiple parts, called three-dimensi onal nesting, is a tedious process and does not guarantee the optimal place ment of all the parts. The three-dimensional nesting is well known as a pro blem requiring intense computation. Thus, an efficient algorithm to solve t his problem is still under investigation. This paper presumes that the thre e-dimensional packing problem can be simplified into a set of two-dimension al irregular polygon nesting problems for each layer to take advantage of t he characteristic of a rapid prototyping process, i.e. the process eventual ly uses two-dimensional slicing data of the STL file. The proposed algorith m uses a no-fit polygon (NFP) to calculate the allowable locations of each slice of a part such that it does not overlap other existing slices in the same z level. Then the allowable position of the part with respect to other parts already located in a work volume can be determined by obtaining the union of all NFPs that are obtained from each slice of the part. Additional ly, a genetic algorithm is used to try and determine the various orders of the placement of the part and the various orientations of each part for eff icient packing. Various orientations of a part are examined by rotating it about the normal vector of the slice in finite angles and by inversion. The proposed algorithm can be applied to a rapid prototyping process that does not use support structures.