Search code examples
data-structures3dpacking

Representation of an arrangement of boxes in 3d

I want to represent the arrangement of multiple 3-dimensional rectangular boxes (maybe within a bigger box...a container). A box is represented by its length, width, height and weight.

The question I now have is, how do i represent the "placement" of these boxes efficiently so i can calculate some properties of the total arrangement:

  • maximum height
  • center of mass
  • total volume
  • ruggedness (How rugged is the overall surface of the built arrangement is. I.e. how many steps and how big the steps within the surface are... the counterpart of a smooth surface)
  • ...

I don't need to render, transform, rotate, display, ... the datastructure efficiently, which most solutions I found try to improve.

Two possible approaches:

The first approach which i thought of was a list with all the boxes and an additional given position (on the x-, y- and z-axis) within the 3d space. From this basic approach I could calculate all properties needed, however it would be quite hard to find a suitable position for a new box. I guess I would have to use another representation for finding a suitable position and then transform this representation to the discribed one.

Another idea was to think of the 3d space as voxels. Placing a box within the space would mean assigning the voxels representing the space the box which makes finding a new place for a box quite easy. Once this structure is built up, calculation of the properties would be fast and simple, however I might lack accuracy when defining too big voxels. Increasing the amount of voxels would slow down the calculation again and would need a lot more memory.

I have looked around for quite some time now, but I can't find a representation which I think fits.

Do you have any other ideas or can you point me to a better solution, or is one of the approaches already a good approach?

Solution

  • Organizing boxes within boxes, especially if you can work in integer space and represent dimensions as voxels, could fit nicely in an Octree.

    https://en.wikipedia.org/wiki/Octree

    Although an octree may be used as a space-dividing scheme for 3D interaction--for example, to quickly find a point in a large cloud of points closest to a 3D ray--you could use an octree as a starting point for organizing your data. It's not quite the best fit for the problem, but it's a nice data structure to know.

    The basic idea:

    1. Start with the overall (x,y,z) cuboid bounds of the space to be divided.
    2. Divide the 3D cuboid into eight child cuboids (eight nodes), each of which occupies half the width, length, and height of the parent box. (Eight nodes, hence "octree." The analogous 2D structure is a quadtree.)
    3. For each node, maintain pointers to its parent and to its eight children.
    4. Iteratively subdivide each node into eight further nodes.
    5. Continue subdividing until the algorithm reaches a pre-defined halting condition, such as a maximum depth, a smallest dimension, or a smallest volume.

    Also see this question: Auto-balancing (or cheaply balanced) 3D datastructure

    You could easily run into memory issues for a tree subdivided too many times. Once you get past 8^5 nodes, for example, you might not like how much memory gets chewed up. One trick for traditional uses of octrees is to introduce a halting condition such that a particular node will not be subdivided if it is empty.

    An octree may not solve your problem, but the space-dividing techniques should come in handy some day if not for this particular problem.

    Also, for an octree the most basic implementation doesn't take into account that an object can span two nodes that belong to different parent nodes. To express this in 2D, imagine that two squares are further subdivided into four squares each: a, b, c, d and e, f, g, h:

    a b  e f
c d  g h

    Although "d" and "g" are next to each other, they belong to different parent squares and don't "know" they're neighbors. Since you'll have the min and max coordinates of "d" and "g", though, it's simple enough to calculate if they're neighbors.

    For many of the basic calculations you don't need to represent the 3D boxes as some kind of voxelized 3D space, but for a measure of "ruggedness" a 3D data grid is a good approach.

    If memory weren't an issue, then you could consider a scheme like the following, assuming you only have to deal with a few dozen boxes, and (perhaps weirdly) that boxes could overlap:

    1. Define a 3D array (or equivalent) representing the full volume you require in integer space. This assumes 1 voxel, when full, can represent the exact edge of a box. (More on this assumption later.)
    2. Assign a 32-bit or 64-bit integer to each voxel.
    3. Assign an index from 0 to 31 or 0 to 63 to each box.
    4. For each box, loop through all pixels (x,y,z) in the box.
    5. At each voxel within the box, set the corresponding bit to 1. For example, for 0-based box index 2, set the integer value to ....0100.
    6. Repeat the process for all boxes.
    7. In the loops iterating through the list of boxes, run calculations on the fly so that you don't have to loop through the full 3D space again: keep a running calculation of center of mass; track the min and max points for overall volume; etc.

    After iterating through all the boxes and their dimensions, you'll have a 3D space in which presence/absence is defined in each voxel, and a unique ID is assigned to each box (which likely will prove to be handy).

    If boxes can't overlap because they represent rigid cuboids, or real cardboard boxes, then you can simply assign a box index to each voxel as a decimal value.

    If you define an integer space for the sake of memory but need greater precision, you can use a separate data structure to track precision of just the outermost voxels of the box. So although for some processing it may be sufficient to check whether a voxel is occupied (value > 0), if you need to find edges precisely you could:

    1. (Optional) Use one bit to flag a voxel as an edge voxel, meaning at least one neighbor has the value 0.
    2. For any edge voxel, use the index of the box to refer to the list of box dimensions. For example, if an edge voxel has a bitwise value ...0010, it is occupied by box index 1. Box index 1 could be defined from (201.3, 12.4, 13.8) to (304.6, 75.3, 102.8). From the min/max points and the edge voxel you can determine a precise location.

    With all boxes assigned, you iterate through the list and make the empty voxels more meaningful. For example, each empty voxel could be assigned a value indicating the distance to the closest box. For example, if at empty voxel (x,y,z) if the closest box in any direction is 10 voxels away, you could use a negative integer value -10 (as a decimal). If the closest box is 10 voxels away, then centered at that empty voxel you could pack another box of half-width = 9.

    Depending on memory constraints and your patience, in each empty voxel you could calculate the distance to the closet box in the +x, -x, +y, -y, +z, and -z directions (and maybe other directions).

    Whether your boxes are axis-aligned or not, using a voxelized 3D scheme can make it easy to calculated "ruggedness" or roughness. A simple technique is to imagine that each side of the total volume is a depth map, or a 2D projection in which each "pixel" is the distance to the box. Roughness can then be calculated as follows:

    1. Select a box face (or direction) for which to calculate roughness. Let's say you select the XY face so that Z is pointed into the total volume.
    2. At each XY point, determine the distance from the box face to the first box (if any). Store this value in a 2D array sized to the XY face.
    3. Iterate through all points in this manner.
    4. Estimate roughness as a measure of the volume in whole pixels and the area of the XY face.

    You can calculate roughness in any of several different ways, depending on whether boxes completely fill the space or not. For example, let's say there are a bunch of boxes fill the space as "seen" from the XY side, all within a range of 10 - 20 voxels from the XY face. Just there are standard roughness measures from 2D profiles of surfaces, you can develop any of several roughness measures for a 3D surface:

    • Total range (max - min) of all box distances. This assumes you ignore columns of voxels that are completely empty as viewed from the XY side.
    • Standard deviation of distances.
    • Sum of absolute deviations from the mean distance, divided by the area occupied.

    For the last example, imagine two cases: whatever space is occupied by boxes, all boxes are at a distance D from the XY face of the enclosing volume. This could be a roughness of 0.0 since there is no variation in distance, which is useful if the goal is to (say) place a large planar object on the boxes. If the space between boxes defines "roughness," then you can either perform a simple calculation as described above or approximate some physical characteristic: how much would a cloth warp if placed over the boxes?

    Using a 3D volume makes it easier to think about the problem, and (in my opinion) would be easier to debug. More complicated schemes could work, too. For example, each box could simply be a data structure with pointers to other closest boxes, and these could be arranged in some rather complicated structure. Voxel space requirements may be reduced slightly by replaced cuboid regions of connected empty voxels within single "supervoxels." But neither of those techniques seems like fun to debug.