The article is devoted to algorithms developed for solving the problem of placement orthogonal polyhedrons of arbitrary dimension into a container. To describe all free areas of a container of complex geometric shape is applied the developed model of potential containers. Algorithms for constructing orthogonal polyhedrons and their subsequent placement are presented. The decomposition algorithm intended to reduce the number of orthogonal objects forming an orthogonal polyhedron is described in detail. The proposed placement algorithm is based on the application of intersection operations to obtain the areas of permissible placement of each considered object of complex geometric shape. Examples of packing sets of orthogonal polyhedrons and voxelized objects into containers of various geometric shapes are given. The effectiveness of application of all proposed algorithms is presented on an example of solving practical problems of rational placement of objects produced by 3D printing technology. The achieved layouts exceed the results obtained by the Sinter module of the software Materialise Magics both in speed and density.
The problem of packing objects of irregular geometric shape has a large number of
practical applications in various fields, including cutting of industrial materials, layout
of spaces (spaces of aircraft, ships and etc.), covering problems, modeling the
microstructure of materials, active electronically scanned arrays generation and other
relevant problems [
The use of polygonal modeling in describing the geometric shape of objects
requires the subsequent use of time-consuming algorithms for nonlinear programming
when solving the problem of placing these objects using the hodograph of a vector
function of dense placement [
We will consider the problem of placement orthogonal polyhedrons in the general
D -dimensional case. A container is specified in the form of D -dimensional
parallelepiped with the dimensions W 1;W 2;;W D (the superscript in formulas means the
number of the coordinate axis) as well as specified a set of n orthogonal polyhedrons
Oi , i 1,, n, each of which consists of mi orthogonal objects in the form of D
dimensional
parallelepipeds
oi,k , k 1,, mi
with
the
dimensions
wi1,k ; wi2,k ;; wiD,k , the position of which relative to each other is specified using
vectors zi1,k ; zi2,k ;; ziD,k containing the coordinates of orthogonal objects in the local
coordinate system associated with each orthogonal polyhedron Oi . In the particular
case, when all orthogonal polyhedrons consist of only one orthogonal object
mi = 1 i 1,, n, the considered problem will be reduced to the classic D
dimensional orthogonal packing problem [
Representation of Objects and Description of a Packing Set-theoretic Operations for Working with Orthogonal Polyhedrons To work with orthogonal polyhedron of arbitrary dimension, the set-theoretic operations of addition and intersection were implemented. When performing operation of addition of orthogonal objects, the following sets of objects are used: A – the initial set of objects, A+ – set of objects to which the addition operation is applied, B – an intermediate set of objects, C – the resulting set of orthogonal objects. The size of a set of objects is indicated as A (for a set A ).
The operation of addition orthogonal objects (Figure 1) includes the following steps. 1. Place all objects from the set A into the set A+ . Create sets B = , C = . 2. Sort the set A+ in descending order of volumes (areas) of objects. 3. Include the first object o1 A+ in the set C .
Solving the Problem of Packing Objects of Complex Geometric Shape into a Container… 3 4. For each current object ok A+ (k = 2 A+ ) check for overlapping with the object o1 . If the objects do not overlap each other, then place the current object ok in the set B ; otherwise, perform the cutting off procedure for all objects, and then place the obtained objects in the set B .
5. Clear the set A+ . If the set B , then move all the objects from the set B to the set A+ , and then go to step 2.
(a) new orthogonal polyhedron, the points of which occupy a space that belongs simultaneously to two original orthogonal polyhedrons (Figure 2).
(a)
(b)
(b)
To describe a packing is used the developed model of potential containers [
of p1h ; ph2 ;; phd −1; xhd + phd − xid − wid ; phd +1;; phD located at D points with coordinates x1h ; xh2 ;; xhd −1; xid + wid ; xhd +1;; xhD produced under the following conditions: xid + wid xhd and xid + wid xhd + phd d 1,, D.
D potential containers with the dimensions
Figure 3 presents all new potential containers (gray) which are formed in a threedimensional potential container after placing an orthogonal object inside it. Sid = max (zid,k + wid,k ) , d 1,, D, k 1,, mi .
To update a set of potential containers after placing an orthogonal polyhedron Oi at the point X i1, X i2 ,, X iD of a D -dimensional container, the free spaces of which are described by a set of potential containers 0 , the following algorithm is performed.
Step 1. Create a set 0 0 of potential containers h : d 1,, D: xhd X id + Sid , where Si1, Si2 ,, SiD denotes the overall dimensions of a D -dimensional parallelepiped bounding the orthogonal polyhedron Oi :
Step 2. Place an orthogonal polyhedron Oi in the specified position X i1, X i2 ,, X iD of a new identical empty container, as a result of which a set of
Solving the Problem of Packing Objects of Complex Geometric Shape into a Container… 5 potential containers will be formed in it. Placement of the orthogonal polyhedron is performed by sequentially placing of all its orthogonal objects oi,k , k 1,, mi .
Step 3. Apply the intersection operation to sets of potential containers 0 and to get a set of potential containers 0 = 0 that describes all free spaces of the original container in the area of the placed orthogonal polyhedron Oi . During the intersection operation, each set of potential containers is considered as an orthogonal polyhedron, consisting of orthogonal objects whose parameters coincide with the parameters of the corresponding potential containers.
Step 4. Replace in the set 0 all potential containers that are also in the set 0 with potential containers from the set .
0 2.3 Decomposition of Orthogonal Polyhedron To reduce the number of orthogonal objects forming an orthogonal polyhedron, a decomposition algorithm has been developed. The algorithm provides the decomposition of a D -dimensional orthogonal polyhedron V into a set of large orthogonal objects includes steps 1–6.
Step 1. Create an empty D -dimensional orthogonal container 1 with the overall dimensions W11,W12 ,,W1D matching the dimensions of a D -dimensional parallelepiped bounding the original orthogonal polyhedron V (W1d = S d , d 1,, D, where S d is the length of the packing measured along the axis d .
Step 2. Place the orthogonal polyhedron V into container 1.
As a result in the container 1, a set of potential containers 1 with the overall dimensions w1k1 , wk21 ,, wkD1 , k1 1 located at points p1k1 , pk21 ,, pkD1 will be formed. The set of potential containers 1 describes the space of container 1, which does not belong to the placed orthogonal polyhedron V .
Step 3. Create an empty D -dimensional orthogonal container 2 with the overall dimensions that match the overall dimensions of the container 1 (W2d = W1d , d 1,, D).
Step 4. Place in the container 2 a set of D -dimensional orthogonal objects with parameters matching the parameters of potential containers from the container 1 (when placing objects, their mutual overlap is allowing): xid = pkd1 and wid = wkd1 d 1,, D, i = 1 1 . As a result in the container 2, a set of potential containers 2 with the overall dimensions w1k2 , wk22 ,, wkD2 , k2 2 , located at points p1k2 , pk22 ,, pkD2 , will be formed. The set 2 describes the space of container 2, which belongs to the orthogonal polyhedron V .
Step 5. Create a D -dimensional orthogonal polyhedron V , consisting of orthogonal objects with parameters matching the parameters of potential containers from the container 2: zid = pkd2 and wid = wkd2 d 1,, D, i = 1 2 , so the orthogonal polyhedron V will contain the set of all orthogonal objects into which it can be decomposed.
Step 6. Apply the addition operation to all orthogonal objects that are part of the orthogonal polyhedron V . As a result, an orthogonal polyhedron O will be obtained, consisting of the largest orthogonal objects that do not overlap each other.
Examples of decomposition of two-dimensional and three-dimensional orthogonal polyhedrons are presented in Figure 4.
To speed up the decomposition of a voxelized object, it is proposed to use a twostage algorithm. At the first stage, the fast algorithm of objects clustering described below is applied, after which the developed decomposition algorithm is applied to the resulting orthogonal polyhedron.
(a) wi1,k + wi1, j , wi2,k + wi2, j ,, wiD,k + wiD,j located at a point 1 , zi2,k ,, ziD,k under the zi,k conditions zid, j = zid, k , wid, j = wid, k
d d and zid, j = zid,k + wid,k . Replace in the orthogonal polyhedron Oi the objects oi,k and oi, j with the object o . If there are no objects oi,k and oi, j satisfying the above conditions in the orthogonal polyhedron Oi , then go to step 3, otherwise repeat step 2.
Step 3. Set d := d +1 . If d D then go to step 2. (a) Solving the Problem of Packing Objects of Complex Geometric Shape into a Container… 7
Start Select the first PC in the container
as the current PC
Is it possible to place OP Oi entirely in the current PC?
Is it possible to place the first object from OP Oi in the current PC? yes
A yes no no no B yes
Were checked all existing potential
containers? B
Select the next PC as the current PC
Create OP Ui,1, describing the area of possible placement of the first object inside the current PC k: 2, mi, 1 Define a set of PCs {P} in which an object oi,k can be placed Solving the Problem of Packing Objects of Complex Geometric Shape into a Container… 9 (c) To convert a container represented in the form of a D -dimensional parallelepiped into an orthogonal polyhedron, it is proposed to place a set of fictitious orthogonal objects in it that are combined into one orthogonal polyhedron of geometric constraints. Figure 8 shows a set of constraints that transform a rectangular container into an ellipse, as well as the result of packing various objects into it.
Examples of placement of orthogonal objects and orthogonal polyhedrons inside containers of complex geometric shapes are presented in Figure 9.
(a) (b) The developed algorithm for packing orthogonal polyhedrons was applied to solve practical problems of rational placement of objects produced by 3D printing.
Solving the problem of optimizing the layout of objects is of great importance in additive technologies, since it can significantly reduce the consumption of material, reduce the time spent on preparing the layout of objects inside the platform (container) of a 3D printer, as well as the time spent on their direct manufacture. The use of denser layouts additionally leads to a reduction in energy costs in the process of manufacturing objects, and also reduces the equipment depreciation used.
At present, the richest functionality for solving the problems of additive
manufacturing is provided by the software Materialise Magics (Materialise NV, Lovaine,
Belgium), which is used by the world's leading manufacturers of equipment for 3D
printing [
We consider a three-dimensional container with the following parameters: length:
340 mm, width: 340 mm, height: 620 mm, the gap from the bottom of the container is
9 mm, the gap from the side faces of the container is 10 mm, minimum distance
between placed objects is 6 mm. Objects can be rotated by multiples of 90 when
placed. Figure 10 (a) shows the best solution obtained by the Sinter module of the
software Materialise Magics, version 23.0.1.19 (packing height: 318.0 mm, solution
time: 300 seconds). The packing consists of 100 objects of 8 different types specified
in STL format. To solve this problem, using the developed placement algorithm, all
objects were voxelized and decomposed. Figure 10 (b) presents the denser placement
of orthogonal polyhedrons found by the developed software Packer [
Solving the Problem of Packing Objects of Complex Geometric Shape into a Container… 11 Using the developed model of potential containers to describe the free spaces inside a container, it is possible to obtain the best area for placing irregular objects inside geometrically complex containers. This model allows switch from use the timeconsuming nonlinear programming methods (which are applied for placing objects specified by polygonal modeling, the practical application of which is limited only by the small size of the problem) to methods developed for placing voxelized objects.
Unlike decomposition algorithms developed by other authors [
The practical application of the developed algorithms is demonstrated by the example of solution the layout problem of objects produced by 3D printing. The found solution exceeds the best solution obtained by the software Materialise Magics both in terms of speed and packing dense.