© P. Chelishchev and K. Sørby, published by EDP Sciences, 2020

1 Introduction

In various applications, it can be useful to circumscribe a given set of three-dimension coordinate points by an ideal shape rectangular parallelepiped. It was suggested by Dupuis [1] to use the term cuboid when referring to a rectangular parallelepiped. However, in the literature of the computational geometry, the term box is commonly associated with the rectangular parallelepiped. In this text, we use the term side for the bounding box face. This term may be also used while referring to the physical cuboid object side. The term face is mainly used for the inscribed convex polyhedron faces, which are the product of 3D convex hull operation. All six sides (faces) of the box are rectangles and each side is parallel with the opposite side and orthogonal with the other four adjacent sides. These four adjacent sides comprise a “closed loop”. For example, the Top side has a “closed loop” of adjacent sides that consists of: Front, Left, Right, and Back. The opposite, Bottom side has the same “closed loop” of adjacent sides as the Top side.

An estimation of the minimal volume bounding box (MVBB) often includes an estimation of the minimal area bounding rectangle (MABR). Both problems are commonly used in computer graphics (e.g. collision detection, optimal layout detection etc.), image processing, medicine (e.g. brachytherapy), metrology, automatic tariffing in goods-traffic and many other applications. Together with other association criteria (e.g. minimum zone, least squares), the minimum volume criterion can be applied for estimation of the flatness deviation of mechanical parts in industry [2]. Depending on an application, the MVBB algorithm may be optimized either for computation time or for measurement accuracy.

Based on the proposals of Shamos [3], Freeman and Shapira [4], Toussaint presented an elegant unambiguous MABR solution in [5]. This exact solution of the MABR problem has O(n ²) computing time with the use of the rotating caliper algorithm for n-point set in ℝ ², and O(n) time with the use of two pairs of rotating calipers orthogonal to each other. A number of approximation algorithms and heuristic alternatives are suggested to solve the two-dimension problem. Among them, the searching algorithms based on the R-tree data structures [6–8] and the principle components [9,10].

The most exact solution of the MVBB problem for n-point set in ℝ ³ with computation time O(n ³) was provided by O'Rourke [11], which remains the state-of-the-art so far. Alternative approximation algorithms have been developed to reduce the computation time. Bespamyatnikh and Segal [12] suggested an efficient O(n ²) approximation algorithm. A search based on Powell's quadratic convergent method was proposed by Lahanas et al. [13]. Later, Barequet and Har-Peled [14] presented an approximating algorithm with O(n + 1/ϵ ^4.5) computation time, and a simplified version with O(nlogn + n/ϵ ³), where 0 < ϵ ≤ 1. Recently, Dimitrov et al. developed a faster algorithm based on the discrete and the continuous versions of principal component analysis (PCA) [10,15]. The continuous version guarantees a constant approximation factor but it is still limited by O(nlogn) − time required for computation of a convex hull. The commonly used solutions for MABR and MVBB are based on the convex hull operation [3,16], in order to reduce the number of considered points and avoid redundant computation.

Some approximation algorithms may provide a large systematic error. The majority of approaches presented above are mainly focused on reducing the computation time, but at the expense of accuracy. In this paper, we consider calculation of the minimum bounding box on reference standards used for calibration of dimensional measuring systems; hence, the accuracy must be ensured. The elegant approach provided by O'Rourke is the accurate solution, but it does not take into account some metrological issues related to the discrete point measurement with CMM, which are discussed below.

The physical edges (denoted by 1 in Fig. 1a) of the cuboid object are typically not measured and there is always a distance between the edges and the measured points. As a result, there is an intermediate space between the measured points on all pairs of the adjacent sides (e.g. side 2 and side 3, side 3 and side 4 in Fig. 1a) of the cuboid object. This intermediate space is transformed into a large number of the convex polyhedron faces after appliance of the convex hull operation. Such newly constructed faces provide acute angles and look similar to “chamfer” faces (denoted by 5 in Fig. 1b). These faces cut off the physical cuboid object and they will lead to unnecessary computation in the O'Rourke algorithm. Obviously, these “chamfer” faces cannot be a part of the minimum bounding box solution and these faces should be excluded from the algorithm.

In this paper, we deal with the minimum bounding box problem for physical objects with an actual shape close to the perfectly rectangular bounding box. The proposed algorithms for estimation of MVBB take into account the effect of the “chamfer” faces. The most accurate algorithm searches for the minimum solution according to the conditions defined by two theorems related to the MABR and the MVBB problems presented in Section 2. A detailed overview of the three conventional geometrical algorithms suggested by the author are given in Section 3. Implementation of the methods is presented in Section 4 with description of the experimental setup and computational results.

Fig. 1 An example of the metrological issue: (a) a cuboid object with CMM measured points; (b) an example of the convex polyhedron with the chamfer faces after convex-hull operation; 1–edges; 2–left side; 3–top side; 4–front side; 5–“chamfer” polyhedron faces; 6–ordinary polyhedron faces.

2 Theoretical background

The solution of the three-dimension MVBB problem involves the two-dimension case. After the orientation of one side of the bounding box is locked in the MVBB algorithm, all points are projected onto the xy-plane, and the orientations of other adjacent sides of the bounding box can be found by the MABR algorithm as the two-dimension problem.

2.1 Minimum-area bounding rectangle

The earliest known solution of the MABR problem was presented by Freeman and Shapira [4]. They presented the following theorem, which is the basis for minimum bounding rectangle algorithms: The rectangle of minimum area enclosing a convex polygon has a side collinear with one of the edges of the polygon.

The MABR solution is based on the 2D convex hull operation [3], which is applied as the first step. In the second step, we search for the minimum-area bounding rectangle circumscribing the convex polygon constructed by the convex hull algorithm in the first step. The theorem mentioned above limits the number of bounding rectangles that are candidates for the minimum-area bounding rectangle.

2.2 Minimum-volume bounding box

The second theorem presented here was formulated and proved for the MVBB problem by O'Rourke [11]: A box of minimal volume circumscribing a convex polyhedron must have at least two adjacent sides flush with edges of the polyhedron.

It is not necessary that one of the sides of the bounding box is coplanar with one of the faces of the convex polyhedron. In fact, the bounding box with minimal volume circumscribing a regular tetrahedron has all six sides coplanar with the tetrahedron edges without flushing with any tetrahedron faces (Fig. 2a).

However, in practise (to be shown in the experimental part, Sect. 4.2), the minimal solution may also correspond to the case when one or more sides of the bounding box are coplanar with faces of the convex polyhedron. An example, where each side of the bounding box is coplanar with face of the polyhedron (Model B) is shown in Figure 2b. The vertex coordinates of this convex polyhedron are given as the Model B in Table 1. The Model B was derived from the reference Model A. The Model A is based on a regular cube with edge length 1 and chamfers with distances 0.1 × 0.1 (normalized units). So that each side of the Model A is given by five points. There is one point in the middle of a face, and there are four points in the corners of the face. The modified coordinates of Model B and Model C relative to the Model A are marked by bold text in Table 1. Figure 2c shows the other example, where two adjacent sides of MVBB are coplanar only with two edges 1 and 2 of the convex polyhedron. Optimization curves for the minimum volume versus an orientation angle between a bounding box side and a face of the Model C are illustrated in Figure 3. The relationship of the minimal volume versus the orientation angle of the Models may appear either linear (Fig. 3a) or nonlinear (Fig. 3b). The beginning of both curves corresponds to the volume where one side of the bounding box is coplanar with the polyhedron face. The end of the curves corresponds to the volume where the same side of the bounding box is coplanar with its adjacent polyhedron face. The other points on the curves correspond to the volume for orientation angles where one side of the bounding box coincides with the polyhedron edge.

Fig. 2 Examples of convex polyhedrons: (a) a regular tetrahedron with edge length circumscribed by minimal box with edge length 1; (b) convex polyhedron related to Model B; (c) convex polyhedron related to Model C; 1–the edge is flush with the Top side; 2–the edge is flush with the Left side.

Fig. 3 The optimization functions of volume versus orientation angle between two faces (Model C): (a) around the edge 2 on the Left side (small angle); (b) around the edge 1 on the Top side (large angle).

3 Computation methods

In the following sections, three methods for finding the Minimum Volume Bounding Box (MVBB) are considered. The methods are denoted as the “side-” method (MVBBS), the “face-” method (MVBBF) and the “edges-” method (MVBBE). All three methods differ from each other by accuracy, complexity and hence the computation time.

All the three methods utilizes the MABR algorithm [4]. Two of the methods (“face-”, “edges-”) include the specific data pre-processing algorithm (Sect. 3.3), which distinguishes these methods from other known methods. Only the MVBBE method completely satisfies to both theorems given in Sections 2.1 and 2.2, and therefore it can be used as the reference for the other alternative methods.

3.1 The minimum area bounding rectangle (MABR) algorithm

The MABR algorithm is based on 2D convex hull operation [3]. After a convex polygon P is constructed, the angles θ _i between the polygon edges and the x-axis are calculated as follows:(1)where atan 2 is the four-quadrant tangent inverse function. The polygon vertices (p ₁, p ₂, … , p _n ) are rotated in such way that the first convex polygon edge e ₁ is parallel with the x-axis. Then at least three other points p _i with extreme (x, y) coordinates are defined − two in orthogonal direction to the x-axis (y _max,  y _min), and another two coordinates in orthogonal direction to the y-axis (x _min,  x _max). The polygon vertices continues rotating with angle −θ _i in clockwise direction from one edge e _i to another e _i+1 until all polygon edges are checked. The two-dimension rotation matrix is a follows:(2)

A new rectangle area A _i is calculated for each rotation. The corresponding rectangle length L _i  = x _max − x _min and width W _i  = y _max − y _min are updated, when a new minimum area A _min = L _i  ⋅ W _i is obtained. An example of the MABR is shown in Figure 4. One of the edges of the polygon is collinear with one of the sides of the bounding rectangle. The algorithm also checks whether the solution is unique or not.

Fig. 4 The MABR of a convex polygon based on 2D point set.

3.2 The minimum volume bounding box side (MVBBS) Method

This MVBBS approximation method is well known and often used in practice. It is fast and straightforward, based on an assumption that the test object has one perfectly flat side e.g. Bottom, which is aligned with the support surface (Z _min). Such assumption allows a substantial simplification, both the measurement procedure and the computation procedure. However, because of the assumption of one perfectly flat side, the estimated minimal volume by this method can be not accurate. Groen et al. [17] developed an operational automatic system for measurement of parcels and suitcases on a conveyor belt based on this principle. The flowchart of the MVBBS method is illustrated in Figure 5.

The principle of this method is to define the height as H _min = Z _max − Z _min and the smallest area A _min of the bounding rectangle for the xy-projection of all measured points. As long as we consider a single 2D projection of the convex polyhedron, then the MABR algorithm (Sect. 3.1) is applied only once.

Fig. 5 The flowchart of the MVBBS method with the MABR algorithm.

3.3 Data pre-processing

In this paper, we focus on solving the minimum bounding box problem for physical objects that are rectangular objects close to the perfectly shaped bounding box. The measurement points of each side of the objects are given as six sets of points: Front, Back, Right, Left, Top and Bottom. The data set of each side is a n × 3 matrix containing x- y- and z-coordinates for the n number of points.

In order to reduce the number of points for further computation, the 3D convex hull operation is applied. The input of the convex hull operation are the point coordinates from the six sets of points jointed together as illustrated in Figure 6. The output from the convex hull operation is a matrix with m rows. Each row of the matrix is a convex polyhedron face ϕ _i defined by its vertices. The vertices are given as indices that refer to the input data to the convex hull operation.

Some of the faces of the polyhedron described by will have vertices from two or three sides of the physical object. For example, the measured points from the Top side may be combined with measured points from the Front side into common faces, or “chamfer” faces between the sides. When defining the minimum bounding box in measurement and calibration of rectangular objects, these combined faces and their edges will not contribute to the solution, and they should not be used in the permutation part of the algorithm.

Two data structures are constructed from the output matrix by the pre-processing algorithm. The first structure represents six matrices S ^F , S ^B , S ^R , S ^L , S ^T , S ^M of face vertices v _i,j separated according to the reference object sides (Front, Back,…Bottom) without common faces (Fig. 6, denoted by I); the second is a data matrix P _k,4 with x- y- and z-coordinates for face vertices (Fig. 6, denoted by II).

Fig. 6 The flowchart of the data pre-processing with the output of two data structures I and II.

3.4 The minimum volume bounding box face (MVBBF) method

The MVBBF method developed by the author is more accurate than the MVBBS method, but it is still an approximation version. The flowchart of the algorithm of MVBBF method is shown in Figure 7.

The theorem presented in Section 2.2 does not provide an upper limit for how many edges that can be coplanar with one side of the bounding box, and then we may assume that one side is coplanar with more than one edge. It is a well-known fact that two distinct but intersecting lines uniquely determine a plane. Hereby, if a side is coplanar with two edges then it is coplanar with a face of the convex polyhedron. Obviously, one side of the bounding box cannot be coplanar with more than one face of the convex polyhedron. The second adjacent bounding box side must flush with at least one edge or face of the convex polyhedron.

In order to compensate the computation complexity of the MVBBF method, first we apply the data pre-processing (Sect. 3.3). Then, the MVBBF algorithm searches through the six matrices S ^F , S ^B , ...S ^M associated with sides of the measured object and checks all faces within each sample. When a side and the first face ϕ of the polyhedron are chosen, three vertices v _1,1, v _1,2, v _1,3 of the face are defined. Two vectors e ₁ {a ₁, b ₁, c ₁} ,    e ₂ {a ₂, b ₂, c ₂} are constructed based on the three given points P ₁(x ₁, y ₁, z ₁),  P ₂(x ₂, y ₂, z ₂),  P ₃(x ₃, y ₃, z ₃), Figure 8. The cross product of the two vectors in ℝ ³ is a new vector n , which is perpendicular to both given vectors [18], and this vector n is a normal vector to the face ϕ:(3)

Then coordinates of the normal vector n  {A, B, C} can be found as the minors of the matrix in (3) as following:(4)

In order to combine the polyhedron face ϕ with an associated bounding box side (e.g. xy-plane), we need to align the normal vector n with positive z-axis, Figure 8. The first step is to move the vector n to the origin by using a translation matrix M with the row vector coordinates of the point P ₁(x ₁, y ₁, z ₁) [19]:(5)

which gives us a vector n ₀. The projections n _α ,  n _β of the vector n ₀ on planes yz (x=0) and zx (y=0) respectively (Fig. 8), give us two angles α and β:(6) (7)

Then a rotation matrix R _x (α) with the angle α for rotating counterclockwise around x-axis can be written:(8)

A rotation matrix R _y (β) with the angle β for rotating clockwise around y-axis can be expressed in the following way:(9)

The final transformation matrix T _ϕ to combine the polyhedron face ϕ with xy-plane as the bounding box side will be as follows (equivalent to alignment of n with z-axis):(10)

The transformed face ϕ and normal vector n are denoted as ϕ ′ and n  ′ in Figure 8. In order to rotate the convex polyhedron, the transformation matrix T _ϕ is applied to the matrix P _k,4 (Fig. 6, denoted by II) of the unique polyhedron vertices.

After the coordinate transformation is completed, all newly transformed points are projected into the xy-plane. Then the MABR algorithm (Sect. 3.1) is applied for these projected points. It defines an orientation of the “close-loop” of adjacent sides (Sect. 1) and, hence the estimation of width W _k and length L _k of the minimum bounding box. The height H _k is defined as a difference between maximum and minimum z-values: Z _max − Z _min. Thus, the volume is: V _k  = H _k  ⋅ W _k  ⋅ L _k .

The described procedure is repeated for each face of the chosen matrix and for all six matrices (S ^F , S ^B , ...S ^M ). The minimum volume V _k is calculated in each iteration. After all iterations are completed, the smallest value V _min is chosen as the solution.

Fig. 7 The flowchart of the MVBBF method.

Fig. 8 Coordinate transformation of an arbitrary polyhedron face.

3.5 the minimum volume bounding box edge (MVBBE) method

The third method corresponds to the conditions of the theorems presented in Section 2.2 and therefore this is the most accurate method, which guarantees the global minimum solution. However, the algorithm is more complex and hence slower than two previous methods. In this case, the data pre-process (Sect. 3.3) becomes the crucial part of the algorithm due to a significant reduction of unnecessary computation of the “chamfer” faces and corresponding edges of the convex polyhedron. The MVBBE algorithm is shown in Figure 9.

The MVBBE method is applied after the 3D convex hull operation and the data pre-process are completed. As before, we use six matrices (S ^F ,   S ^B , ...S ^M ) associated with the cuboid reference object sides as the output of the data pre-processing algorithm (Fig. 6, denoted by I). The algorithm checks for each pair of faces with common edges. Since such pair of two faces with their vertices ϕ ₁ [v _1,1, v _1,2, v _1,3] ,  ϕ ₂ [v _2,1, v _2,2, v _2,3] are found, it gives us the four non-collinear points P ₀(x ₀, y ₀, z ₀), P ₁(x ₁, y ₁, z ₁), P ₂(x ₂, y ₂, z ₂),P ₃(x ₃, y ₃, z ₃) and three non-collinear vectors corresponding to the polyhedron edges e ₁ {x ₁ − x ₀,  y ₁ − y ₀,  z ₁ − z ₀}, e ₂ {x ₂ − x ₀,  y ₂ − y ₀,  z ₂ − z ₀} and e ₃ {x ₃ − x ₀,  y ₃ − y ₀,  z ₃ − z ₀} or as a simplified form e ₁ {a ₁,  b ₁,  c ₁}, e ₂ {a ₂,  b ₂,  c ₂} and e ₃ {a ₃,  b ₃,  c ₃} respectively, (Fig. 10).

Thus, the plane corresponding to the face ϕ ₁ can be defined by the two non-collinear vectors e ₂,   e ₁ in the following parametric form:(11)and similarly by e ₁, e ₃ for the face ϕ ₂:(12)

The angle θ between the faces ϕ ₁ and ϕ ₂ is the angle between the normal vectors n  {A, B, C} ,   n ₂ {A ₂, B ₂, C ₂} [18]:(13)where A, B, C, A ₂, B ₂, C ₂ are three corresponding minors of matrix (11) and (12), which can be calculated by using of equation (4).

In order to find the minimum volume solution, the polyhedron points P _k,4 need to be rotated around the common edge e ₁ to the angle θ, from the face ϕ ₁ to the face ϕ ₂. A one-degree step is used for each iteration, but at least three iterations are applied if the angle θ is less than 2°.

A certain alignment may be done to simplify the rotation of the polyhedron around the edge. First, xy-plane is made flush with the face ϕ ₁ by alignment of the normal vector n with z-axis. The same technique is applied as it was described in Section 3.4. The vector n moves to the origin by the translation matrix M(x ₀, y ₀, z ₀) in (5), rotate counterclockwise with angle α around x-axis by using the rotation matrix R _x (α) in (8), and clockwise with angle β around y-axis by using the rotation matrix R _y (β) in (9). The next, the common edge e ₁ is aligned with x-axis by following rotation matrix R _z (γ) around z -axis with angle, for clockwise (the example in Figure 10 has positive γ-counterclockwise):(14)

Thus, a full transformation matrix T _e for alignment of normal vector n with z-axis and the polyhedron edge e ₁ with x-axis, can be written in this way:(15)

A result of transformation of the two faces ϕ ₁,   ϕ ₂ into ϕ ₁ ′,   ϕ ₂ ′ and the edge e ₁ into e  ′ ₁ is shown in Figure 10.

The alignments of the face ϕ ₁ ′ with xy-plane, and the edge e  ′ ₁ with x-axis provide a transformed edge denoted as e  ′ ₁ (Fig. 10). Then, the rotation of all points P _k,4 around the edge e  ′ ₁ with one-degree step angle dθ = π/180° can be proceeded by using the rotation matrix R _x (dθ) given earlier in equation (8). After each rotation step, newly transformed points are projected into xy-plane and the MABR algorithm (Sect. 3.1) is applied for the projected points to estimate the width W _k and the length L _k of the minimum bounding box. The height H _k is defined as a difference between maximum and minimum Z _max − Z _minvalues. Finally, the volume of the bounding box is: V _k  = H _k  ⋅ W _k  ⋅ L _k .

The above procedure is carried out for each common edge of all six matrices S ^F , S ^B , ...S ^M (Fig. 6, denoted by I). The volume V _k is calculated in each rotation step, and the smallest volume V _min is the solution.

Fig. 9 The flowchart of the MVBBE method.

Fig. 10 Coordinate transformation of two arbitrary polyhedron faces ϕ 1, ϕ 2 with the common edge e 1.

4 Implementation

The algorithms described in the previous sections are developed and implemented in MATLAB^® programming environment based on CMM measurement data. The measurements have been performed in a Leitz PMM-C-600 CMM with an analogue probe. The PC-DMIS software was utilized for operation of the CMM.

4.1 Experiment setup

For the experimental tests, we have used a cuboid object with the following nominal dimensions (the true values are unknown): length 210 mm, width 140 mm, and height 120 mm. The test object is shown in Figure 11. The measured data is arranged into separated data samples according to the cuboid sides: Front, Back, Right, Left, Top and Bottom. Each sample is a n × 3 matrix with three columns and n-rows of xyz-coordinates corresponding to the n-measured points as shown in Figure 6. We have used a uniform distribution of measured points with 15 mm distance between the points. The total number of the measured points is N = 650.

In order to get complete measurements of all six sides of the test object in a common coordinate system, we have measured the object in two setups. The measurements of the two setups have been combined by using common alignment points in the two setups.

Fig. 11 CMM measurement of the test object.

5 Results and discussion

The collected date is further exported to a MATLAB code as an input for the developed algorithms. The first MVBBS method can be applied straightforward on the data − no data pre-process is required. We consider only the Bottom side as a support side. For the other two methods, we apply the data pre-process algorithm after the 3D convex hull operation. The result of the convex hull operation for measured data is shown in Figure 12. There are 166 faces combined together into one convex polyhedron and 88 faces after applying of the data pre-process algorithm (almost 50% of calculations were reduced). The computation results of all three methods are tabulated in Table 2 (the results are rounded to 1e–3).

The MVBBS method provides a significant overestimation of the volume V _S of the bounding box relative to the other two methods: ΔV = V _S  − V _E  = 951.959 mm³. Meanwhile, there is no difference between estimated volumes from the MVBBF and the MVBBE methods. A possible reason for such coincidence may be a small form deviation and as a result, small angles between polyhedron faces.

An extra test was applied for estimation of MVBB for the cuboid object with the same nominal dimensions but with larger flatness deviations. The computation results are given in Table 3.

The second test demonstrates the difference between MVBBF and MVBBE methods. The following difference can be observed from Table 3: ΔV = V _F  − V _E = 8.675 mm³, where V _F is the solution of the MVBBF method and V _E is the solution of the MVBBE method.

In order to verify the proposed approaches, the developed methods were applied on Model B and Model C, which are illustrated in Figure 2b,c. The vertex coordinates of the theoretical models are given in Table 1. The computation results for estimation of MVBB based on the developed methods for Model B and Model C are given in Table 4 (the results are rounded to 1e–4).

It can be observed a difference between the solutions for MVBBS, MVBBF and MVBBE methods for Model C. The MVBBE method provides the smallest solution for Model C. The results for Model B and for all three methods are equal.

The MVBBE method may provide the minimal solution and yet, it includes all solutions of the MVBBF method and therefor it is more reliable and accurate.

Fig. 12 The result of the 3D convex hull operation.

6 Conclusion

Three methods have been proposed and demonstrated in this work for estimation of the minimum volume of bounding box with the proposed data pre-process algorithm for the metrological applications. The first two methods are based on a number of assumptions allowing decreasing of a computation time but often with overestimated results. The minimal and the most optimal solution is provided by the MVBBE method. Furthermore, the solution of the MVBBE method is based on theorems presented in this paper (Sects. 2.1 and 2.2) and hence, its estimation is the most accurate. Relying on type of dimensional measurement system, different methods may be applicable while the MVBBE method should utilize as the reference.

However, the MVBBE method includes a large number of an additional calculation. The proposed pre-process data algorithm (Sect. 3.3) based on the specific metrological conditions (described in Sect. 1) allows a significant reduction of the computation (about 50%) preserving the initial accuracy at the same time. Thus, the MVBBE method should be used for those metrological tasks, where the accuracy is the critical factor, particularly when a large geometry form deviation is expected. The principles outlined in this work could also improve the functionality of operation software for the measuring systems.

Acknowledgments

The authors wish to thank Dr. Christoph A. Thieme, NTNU, Trondheim, for valuable advices and comments. The authors acknowledge the financial support of the Research Council of Norway, Grant No. 235315.

References

All Tables

All Figures

	Fig. 1 An example of the metrological issue: (a) a cuboid object with CMM measured points; (b) an example of the convex polyhedron with the chamfer faces after convex-hull operation; 1–edges; 2–left side; 3–top side; 4–front side; 5–“chamfer” polyhedron faces; 6–ordinary polyhedron faces.
In the text

	Fig. 2 Examples of convex polyhedrons: (a) a regular tetrahedron with edge length circumscribed by minimal box with edge length 1; (b) convex polyhedron related to Model B; (c) convex polyhedron related to Model C; 1–the edge is flush with the Top side; 2–the edge is flush with the Left side.
In the text

	Fig. 3 The optimization functions of volume versus orientation angle between two faces (Model C): (a) around the edge 2 on the Left side (small angle); (b) around the edge 1 on the Top side (large angle).
In the text

	Fig. 4 The MABR of a convex polygon based on 2D point set.
In the text

	Fig. 5 The flowchart of the MVBBS method with the MABR algorithm.
In the text

	Fig. 6 The flowchart of the data pre-processing with the output of two data structures I and II.
In the text

	Fig. 7 The flowchart of the MVBBF method.
In the text

	Fig. 8 Coordinate transformation of an arbitrary polyhedron face.
In the text

	Fig. 9 The flowchart of the MVBBE method.
In the text

	Fig. 10 Coordinate transformation of two arbitrary polyhedron faces ϕ 1, ϕ 2 with the common edge e 1.
In the text

	Fig. 11 CMM measurement of the test object.
In the text

	Fig. 12 The result of the 3D convex hull operation.
In the text