Carnegie Mellon University

A manufacturer, who produces different sizes of regular 3D objects, purchased a machine that cuts connected carton surfaces and forms a square box when folded. The customer specifies the sizes of the objects in his order ; the manufacturer feeds the information to specific machines to produce the objects. The new machine needs to have the three dimensions of the box to be able to form it. In order to form the box and decrease the cost, a program code is required to determine the dimensions of the box suitable for each object.

One approach to the solution of the problem is to find the minimum size of the square box that fits each object. This will certainly minimize the cost, but will also be a very expensive task and time consuming. This approach is beyond the scope of the project.
Another approach is to find the square box that fits each object in a way that decreases the size of the box. If we find the maximum plain surface of an object and assume that the object will rest on it on the box base, the scope of the problem will narrow to become finding the other five boundaries of the object that will determine the size of the square box.
 

The only difference between the previous approach and the current one is that the previous approach suggests that only the face of the largest area can rest on the box base, whereas the current approach suggests that any one of  the faces can rest on the box base.
 
The algorithm of finding the box of the minimum size:
 

• Read the file that contains the data representing the vertices and the faces of an object.
• Save the coordinates of all vertices.
• Save the indices of all vertices forming each face.
• For the first face:
a - Suppose that this face of the object will rest on the box base. Find the longest edge of this face.
b - Find the normal vector of the plane that contains the face.
c - Slide the plane as a slicer to determine the upper and the lower boundaries of the object. The upper and the lower boundaries determine the height of the box.
1 > Use one of the vertices of the longest edge as a starting point for the first slicer plane.
2 > If the plane intersects with any of the object edges, then the slicer did not reach the boundary of the object.
3 > Slide the slicer plane upward by (+h).
4 > Repeat steps 2 and 3 until there is no intersection.
5 > Repeat steps 1, 2, 3, and by sliding the slicer plane downward by (-h).
6 > The height of the box equals to the number of slides which was performed upward and downward times (h).
d - Find the normal vector of a plane such that the plane contains the longest edge and is perpendicular to the plane mentioned in step b.
e - Repeat step c to find the length of the box.
f - Find the normal vector of a plane such that the plane passes through one of the vertices of the longest edge, the plane is perpendicular to the plane mentioned in step b, and the plane is perpendicular to the plane mentioned in step d.
g - Repeat step c to find the width of the box.
h - Calculate the volume of the box (height*length*width).
• Repeat steps a to h for the rest of the faces and find the volume of the box every time.
• The box of the smallest volume determines the dimensions of the box and the face of the object that will rest on the box base.