The problem of optimizing the life cycle of complex three-dimensional objects in small-scale production is considered. Additive technologies and optimization algorithms for the placement of three-dimensional objects are considered as technologies to solve this problem. Using the multilevel synthesis method can significantly reduce the time for prototyping new products. It should be noted that since several independent parts can be manufactured at the same time, this problem belongs to the class of optimization geometric modelling problems, namely, the problem of three-dimensional irregular placement. An algorithmic solution is proposed for the most complex task - placing 3D objects in a container. The results of the analysis of the effectiveness of the proposed algorithms are discussed.
An analysis of the stages of the life cycle of complex products in various industries shows that many of them are associated with the solution of optimization problems of placement. Finding the optimal or close solution allows you to significantly reduce the consumption of various resources and lower the cost of production. Such tasks are important from the point of view of saving resources, but difficult to make decisions.
On the other hand, the advent of additive technologies and their application for rapid prototyping and manufacturing of volumetric parts made a real revolution in high-tech industries, which are characterized by single or small-scale production: nuclear, aerospace, aviation, instrumentation, etc.
The use of layered synthesis technologies has led to the emergence of new methods for producing
synthesis models and synthesis forms, which made it possible to drastically reduce the time to create
new products [
There is a set of three-dimensional objects T = {T1, T2, …, Tn}, i = 1, n presented in STL format, where Ti = {T1, T2, …, Tm} is an array of triangles that represent the figure.
Each triangle is represented in the form Tri (A, B, C), where A, B, C are the vertices of the triangle with coordinates (x, y, z).
The packing area R is a three-dimensional figure in the form of a rectangular parallelepiped R = {L,
Ti T , Tj T , Ti Tj = , i = 1, n, j = 1, n, i j, Ti T , Ti R = Ti , i = 1, n, i.e., no two objects intersect each other, and all objects are located inside the placement area R.
It is required for objects Ti , i = 1, n to find a package with such a set of placement parameters U so that the density of packed objects in the placement area R is maximum (1) (T (U )) =
→ max, n V (Ti (U )) i=1
V (R)
where V(R) = L*W*H is the volume R, which depends on the height of the packing area H, and V(Ti) is
the volume of the object Ti.
3. The basic principles of constructing dense packaging based on a discrete-logical
representation of information (voxel)
An analysis of the methods for solving this problem allows us to draw the following conclusion: in the
process of development, these methods underwent the following chain of changes in the operations on
which they are built: “floating-point operations” [
The peculiarity of using the last of the above is that only logical operations with “0” and “1” are needed to determine the non-intersection of geometric objects.
The main idea of this approach is to simulate the dense motion of objects, i.e. building No-Fit
Various implementation options are possible based on a discrete-logical representation of
information (voxel) and chain coding [
Each shape Tk consists of a starting point P0 and a vector Pathk = {V1,...,Vm},i = 1, m describing the surface of the shape. The nodes in the vector are stored as
where • N is the number of the voxel, determining its place in the vector, • Nprev is the reference to the number of the parent voxel from which the voxel is built, • direct is the direction in which the voxel is located relative to the parent.
Further details of the approach presented earlier in [
• Conversion of objects from a given set into a discrete-logical space into a voxel matrix by the
RASTERIZATION() procedure. • Formation of a voxel vector by the procedure SET_VECTOR().
• Sorting shapes T = {T1, T2, …, Tn}. Internal procedure: • For each object Ti , i = 1, n from the list T:
figures by the NFP() procedure.
several similar points, select a point with a minimum vector length ( x, y) .
4.1. Converting objects to discrete logical space RASTERIZATION () Figure 1 shows the initial (polygonal) representation of the object. The final (voxel) representation of the object is presented in figure 2.
For intermediate storage, we select a three-dimensional DataR array. Iinitially the array is filled with zeros.
1. Rasterize the sides of the polygon A, B, C according to the Bresenham’s line algorithm into an array of points.
AB = {AB1, …, ABn}, BC = {BC1, …, BCm},
AC = {AC1, …, ACp}.
2. Divide the resulting arrays into groups G = {G1, …, Gr}. In each group Gi, all voxels have the same z coordinate, ab AB, abj , z = i, j [1, n] , Gi = bc BC , bc j , z = i, j [1, m] , i = 1, r,
ac AC, ac j , z = i, j [1, p] respectively, are in the same plane (figure 3).
ABn B …
ABi BC1 … А
BCm
AC1 ACi …
ACp C
G1 Gi Gr 3. For each of the obtained groups G, depending on the number of voxels: • One voxel in figure 2 on the plane G1: the voxel is entered into the DataR array: the place in the array corresponding to the coordinates of the voxel is marked as 1. • Two voxels in figure 2 on the plane Gi: based on 2 voxels, a segment is constructed that is also rasterized into n voxels; the corresponding n places in the DataR array are marked as 1. • Three voxels and more: depending on how many voxels are included in group G from each of the sides AB, BC and CA, the following situations are possible: o All voxels are from one side. These voxels make up a segment; places corresponding to these voxels in the DataR array are marked as 1. o Voxels are from two sides. In the plane there are points forming two segments. We connect the corresponding ends of the segments. The resulting figure is a flat quadrangle, which is divided into two flat triangles. Triangles are rasterized by the rasterization algorithm of a flat triangle. o Voxels are from three sides. In the plane there are points from three segments and two of them are connected. We connect, as in figure 3, the ends of the corresponding segments. Then it is necessary to rasterize the resulting flat shape similarly to the previous step. A special case of this stage is that all the point of all segments is in one group, which means that the entire triangle lies in one horizontal plane. 4.2. Building a voxel vector based on a three-dimensional matrix SET_VECTOR () Building a voxel vector consists of the following main steps.
1. Set the seed voxel Vcurrent (0, -1, -1). 2. Mark the place Pcurrent in the DataR space as passed. 3. Enter Vcurrent (Ncurrent, Nprev, direct) into the vector Path.
5. Select the first free direction v F (Vcurrent), i = 0,5 , redefine Vcurrent =(Ncurrent +1, Ncurrent, i), go i to step 2.
6. If there is no free direction for the shift vi F (Vcurrent), i = 0,5 , select the previous node in the Path array as the current node: Vcurrent =Path[Nprev], move the current position to the direct direction back: Pcurrent = Pcurrent – Pcurrent . Go to step 4. 4.3. Placement of object T0 in placement area PUT_BEGIN () Placement of object T0 consists of the following steps.
1. For all already packed objects T’ = {T1, … , Tn}, their maximum height hmax = max( h(Ti )) i = 1, n is selected; h(Ti) = max(Pj, z), j = 1, m where {P1, …, Pm} are the coordinates of the voxel points that make up the object Ti.
2. The entry point Pbegin(0, 0, hmax + hT (T0 )) is selected.
The process of building NFP placed object consists of the following steps.
1. For each of the packed objects Ti{T0...Tm}, where m is the number of packed objects, the NFP of the placed object T is constructed relative to T’i in the packing area R LIST_CONSTRACTION (T, T’i).
2. In each of these NFP Vi {Vi0 ...Vim} some nodes ViVi are selected.
m 3. Resulting NFP is Vresult = i=0Vi . 4.5. Building NFP of two objects LIST_CONSTRACTION (T1, T2) using the "right hand" method. The process of building NFP of two objects consists of the following steps.
1. Set the seed node Vcurrent at the starting point Pcurrent = P0.
2. Check the free neighboring nodes (figure 5). If the nodes in all directions of the shift are free, then we shift the node Vcurrent in the 0th direction until at least one of the directions is occupied. 3. Mark the place Pcurrent in the placement area as occupied. 4. Enter Vcurrent (Ncurrent, Nprev, direct) into the list vector Path. appropriate order.
6. Select the first free direction v F (Vcurrent) , transfer the object to the vector of this direction.
i At the same time, so that the object does not come off the surface when moving to the 0th ("right") direction, the priority shift directions are turned so that the 0th direction is in place of the first (by priority) inaccessible. Go to step 3.
7. If there is no free direction for the shift V F (Vcurrent) , select the previous node in the Path i array: Vcurrent =Path[Nprev] as the current node, move the current position to the direct direction backward: Pcurrent = Pcurrent − v3 . Go to step 4.
Obstacles 5. Analysis of the dense packing algorithm efficiency To analyze the efficiency of the developed methods for placing three-dimensional objects in a container, a series of computational experiments was performed.
As input data, we used data placed in open databases, as well as data presented in articles by
leading researchers in the field of analysis of algorithms for placing three-dimensional objects in a
container [
Sets of 20, 30, and 40 polyhedra of two, three, and four of each type were used. Objects were packaged in a container with a base size of 30 × 35 units. The packaging efficiency was estimated by the packing density parameter (%).
Table 1 presents the sets of three-dimensional objects and the results of solving the dense allocation
problem. The algorithms used were:
• First local minimum (FLM) [
The results of analysis of the dense packing algorithms efficiency show that the best packing density is provided by: • GRASP + Local Search (LS) algorithm (24.47%) for 20 objects; • Simple Heuristic (Voxel representation) algorithm (24.09%) for 30 objects; • First Fit (FF) + Local Search (LS) (25.61%) for 40 objects.
The packing density of the objects obtained by the voxel-based representation is slightly lower, since a simplified optimization procedure algorithm was used. Despite this, it should be noted the high efficiency of the method, because with certain accuracy parameters, it allows you to pack objects faster. The main advantages of the voxel approach are the correctness of the solution, that is, small changes in the source data do not lead to changes in the results, as well as the speed and reliability of the basic logical operations.
The paper considers an approach to solving the problem of packing complex three-dimensional objects in a parallelepiped container based on the use of a discrete-logical (voxel) representation of information, which allows one to obtain results that are different in time and accuracy of calculation.
Analysis of the dense packing algorithms efficiency shows the best packing density (average 24.72%) provided by GRASP + Local Search (LS) algorithm, Simple Heuristic (SH) algorithm and