- 上一篇：德语论文中德关系以上海与汉堡的友好关系为例
- 下一篇：对比中德经典城市文化之旅德语论文
3. Formulation of model layout problem
In this work, the SGC model tray is represented as a container with an upper limit. The model layout problem in this research can be described as packing a batch of parts of different sizes into the container (bin). Packing tasks are characterized by the following three objectives:
* fitting models into the specified container;
* avoiding any overlap between models;
* achieving high packing density, in other words, achieving the minimum overall height.
In the present application, the CAD model of each part is represented in STL format. It consists of coordinate information of facet triangles and their corresponding outward pointing normal in a 3D space. Compared to other formats of CAD models, STL format is very straightforward. However, the search would be very time-consuming if the complete information of an STL model is encoded in the algorithm. This is because one simple operation such as ‘rotate’ or ‘move’ means recalculation of the new location of every
triangle facet of a model, and it is very common for a mechanical part to have hundreds and thousands of triangle facets in an STL model. Moreover, these operations are used in thousands of ‘iterations’ during the searching process of SA. Thus the simplification is necessary. Most of the researchers simply envelop a part with a rectangular box because it is easy to implement and keeps the packing algorithm from becoming too complicated [4]. This method was also used in this research. The difference lies in the formulation of objective functions and specific search strategies. The 3D model layout can then be described in the following steps (Fig. 2):
1. Parse STL files of the parts to be manufactured and generate an envelope for each part model.
2. Pack envelopes in a bin according to a specific algorithm. The bin has the same size as that of the maximum manufacturing volume of the Cubital machine.
3. Calculate the updated STL file for each part.
4. Demonstrate the final result of the layout.
Steps 1, 3, and 4 involve techniques in computer graphics and visualization, which are not specifically related to the packing problem and are relatively easier to implement with existing graphic tools. Our focus is on Step 2. The formulation of this problem is critical to establish a proper algorithm.
The bin-packing problem can be represented as an optimization problem in Eq. (1):
where n is the number of models, pi the packing state of a model, p the layout, P the set of all layouts, B the boundary of bin, pi∩pj the overlap between any two models, pi∩B the overlap between a model and a bin, h the overall height of a layout and f the objective function mapping the set P into the set of real numbers.
In this present problem, a layout is a batch of parts satisfying the constraints defined by Eq. (1). The objective function is defined as the overall height of a layout.
The packing state of a model is determined by the location (coordinates) and the orientation of model’s envelope. For each part a ‘local’ coordinate system is defined, the origin of which is the geometric center of its envelope. The bottom-left corner of the container (bin) is defined as the global origin. The coordinates of the geometric center of an envelope determine the location of this envelope in the container. The number of state of model orientation is six as shown in Fig. 3.
The change from one state to another can be realized through one or two rotational operations. The operation ‘rotate’ is to spin an envelope 901 around one axis of its ‘local’ coordinate system. For example, to change the envelope in Fig. 3 from state (a) to state (b), it can be rotated around its x-axis (state (d)) and then rotated around its y-axis. The surfaces of every envelope are always perpendicular or parallel to the orthogonal axis. The state of each envelope pi is represented as