When fitting 3d cuboids into a box, how to find the order of drawing (in a 2D projection) so that the cuboids don't appear to overlap?

Question

I am working on a 3D packing algorithm (MIT-licensed). The box and the cuboids it contains are displayed as a 2D projection. The order of drawing the cuboids (now represented as polygons) is important: a cuboid placed at the back of the box must not be drawn after the cuboids in the front row. I am currently using order by(cuboid.X + cuboid.Y + cuboid.Z) and it works around 99% of the time, but not always. Some aberrations do ocurr, as depicted below. I have tried multiplying the coordinates, and order by X then by Y then by z, and other combinations. Adding the coordinates is the one that gave the best result. Can someone enlighten me?

Answer 1

Here's the fundamental problem that you face:

The order in which two given cuboids must be drawn may depend on the other cuboids in the packing.

For example, suppose we have one tall, narrow cuboid in the front left corner and a second tall, narrow cuboid in the back right corner, and that both cuboids occupy the full height of the box. If you have a third cuboid that touches the front and back sides of the box and is wide enough to touch both of the first two cuboids, the front left cuboid must be drawn first. But if the third cuboid touches the left and right sides of the box as well as touching the first two cuboids, the second cuboid must be drawn first.

This means that the usual procedures for sorting lists, which assume that you can look at any two elements and immediately say which one should be earlier in the final list, simply will not work here.

But you can define a partial ordering on the cuboids. The partial ordering you need relies on a function that has three possible return values for any two cuboids $A$ and $B$:

• cuboid $A$ must be drawn before cuboid $B$;
• cuboid $B$ must be drawn before cuboid $A$; or
• the cuboids can be drawn in either order.

In computer graphics, the "painter's algorithm" sorts polygons this way. You might be able to adapt a similar idea to sorting cuboids (possibly with some simplifications since your cuboids are axis-aligned) ... assuming, that is, that you can find an accurate reference that provides or describes the algorithm.

---

Perhaps we can derive our own simplified painter's algorithm for this specialized type of scene.

Each cuboid is plotted as a hexagon. The projection shown in the question makes things relatively easy since most of the edges of the hexagon are plotted parallel to the horizontal and vertical axes of the viewing plane.

To compare any two cuboids to see whether one is behind the other, first take the bounding boxes of each hexagon on which the cuboids are projected. If the bounding boxes overlap, find out whether the projection of the upper left front (or rear) corner of one cuboid is projected below the line on which the lower right $z$-parallel edge of the other cuboid is plotted. (The projected corner can be below any part of the infinitely extended line, not just below the projection of the edge itself.) If the corner is below the line, the hexagons do not overlap.

If the hexagons do not overlap, the order between the two cuboids is unconstrained.

If the hexagons overlap, you might try a function like this: \begin{align} \newcommand{\c}{\mathit{cuboid\,}} \newcommand{\or}{\mathbf{\ or\ }} \newcommand{\return}{\mathbf{\ return\ }} &\mathbf{isordered}(\c_1, \c_2): \\ &\quad \return(\!\begin{array}[t]{l} \c_1.\mathrm{Xmax}\leq\c_2.\mathrm{Xmin} \\ \or \c_1.\mathrm{Ymax}\leq\c_2.\mathrm{Ymin} \\ \or \c_1.\mathrm{Zmax}\leq\c_2.\mathrm{Zmin})\end{array} \end{align}

Assuming that no cuboids actually overlap (which your packing algorithm should have guaranteed), any two cuboids will satisfy either $\mathbf{isordered}(\c_1, \c_2)$ or $\mathbf{isordered}(\c_2, \c_1).$

Given the orientation of the projection shown in the question, if $\mathbf{isordered}(\c_1, \c_2)$ is true then you want to plot $\c_1$ first, because it is obscured by $\c_2.$

---

I think the algorithm above gives a partial order, but you still have to apply it in order to find the order in which to plot the cuboids.

One possibly algorithm (probably not the most efficient) is to consider the list of cuboids that have not yet been plotted. (Initially, this is all the cuboids.) For each cuboid in this list, consider this the "selected" cuboid and compare it with each other cuboid in the list. If you get to the end of the list and every comparison says that the "selected" cuboid is plotted first or it doesn't matter, plot the "selected" cuboid and remove it from the list. Otherwise (that is, if the "selected" cuboid obscures any other cuboid), try the next "selected" cuboid.

Since the geometry of the problem makes it impossible for there to be a cycle of cuboids obscuring each other, if you iterate through the entire list this way you will eventually find a cuboid that you plot. Now the list is shorter. Iterate through the list again, plotting another cuboid, Repeat until the list is empty.

Technically, the partial ordering relationship defined by $\mathbf{isordered}$ also defines a directed acyclic graph with a cuboid at each node of the graph. This can be converted into a sorted list that is consistent with the partial order. I think the list also could be created by an insertion sort (inserting each cuboid immediately after the last cuboid it obscures) without constructing the graph. But these are all merely possible optimizations.

Answer 2

You could try ordering by how far the cube is along an axis directly towards/away from the camera. Working out what that axis is depends on the particulars of your orthographic projection.

Let $(a,b,c)$ be a vector pointing directly towards or away from the camera. Then you should order by $ax+by+cz$.

If you have trouble figuring out this vector, try drawing a bunch of tiny boxes at $(ka,kb,kc)$ for an assortment of values of $k$ and then adjust $a,b$, and $c$ until the boxes line up.