Drawing isometric boxes in the correct order

In an isometric display, it can be tricky to draw boxes of various sizes in the correct order to keep them appropriately in front of or behind one another. The figure below shows an example. The blue box should be drawn first, then green, then red.

Figure 1: The boxes on the left are not drawn in the correct order, whereas the boxes on the right are drawn correctly.

We will explore a simple solution for determining the correct order to draw a given set of boxes. But first, we must define what we mean by boxes.

What do we mean by boxes?

We define boxes as axis-aligned and non-intersecting rectangular prisms. Take a look at the above Figure 1 again. Each box is parallel to the x, y, and z axis (i.e. axis-aligned). Also, note that the boxes are next to each other but do not intersect.

Determine if boxes overlap on screen.

First of all, if two boxes do not overlap on the screen, then we do not have to worry about which one is drawn first. This is the first test we must perform, which we explore in this section.

Figure 2: No overlap on the left; overlap on the right. (Note: we are talking about overlap on screen, not intersection in space.)

The silhouettes of the 3D boxes become 2D hexagons in the isometric view, as seen below. We use the outline of these silhouettes to test for overlap.

Figure 3: The box silhouettes in an isometric view are simple hexagons. Note that their sides are always parallel to the vertical and two diagonal axes.

We take advantage of the fact that the hexagon sides are always parallel to some axis. This allows us to easily determine if the hexagons overlap by checking for intersection of their regions on each axis. We add an h (horizontal) axis to help.

The red and blue boxes do not overlap on the h axis, therefore they do not overlap. The green and blue boxes do overlap since their region on every axis overlap.

Now that we have outlined our concept for determining if two boxes overlap on the screen, we will fill in the details necessary for implementing it.

The act of flattening the 3D box into a 2D hexagon involves getting rid of the Z coordinate. Notice that increasing a point's Z coordinate by 1 is the same as incrementing both X and Y coordinates by 1. Thus, we can add Z to both X and Y and drop Z completely. Shown below is the source code for a function that performs this conversion.

// Convert a 3D space position to a 2D isometric position.
function spaceToIso(spacePos) {

    // New XY position simply adds Z to X and Y.
    var isoX = spacePos.x + spacePos.z;
    var isoY = spacePos.y + spacePos.z;

    return {
        x: isoX,
        y: isoY,

        // Compute horizontal distance from origin.
        h: (isoX - isoY) * Math.cos(Math.PI/6),

        // Compute vertical distance from origin.
        v: (isoX + isoY) / 2;
    };
}

And finally, after determining the bounds of each hexagon, we can determine if they overlap by using the source code below.

function doHexagonsOverlap(hex1, hex2) {
    // Hexagons overlap if and only if all axis regions overlap.
    return (

        // test if x regions intersect.
        !(hex1.xmin >= hex2.xmax || hex2.xmin >= hex1.xmax) &&

        // test if y regions intersect.
        !(hex1.ymin >= hex2.ymax || hex2.ymin >= hex1.ymax) &&

        // test if h regions intersect.
        !(hex1.hmin >= hex2.hmax || hex2.hmin >= hex1.hmax));
}

Now that we have determined if two boxes overlap on the screen, we can begin exploring how to determine which box is in front of the other.

Determine which box is in front.

Recall that our boxes do not intersect each other. we can visualize their separation as a thin plane between them (see Figure 5 below). After identifying this plane, we can determine which box is in front by selecting the one on the correct side of this plane.

Figure 5: A pair of blocks can be separated in one of three ways shown here. The dark glass illustrates this separation.

We can find this plane of separation by looking at each axis individually. In particular, we look for an axis which has non-intersecting box ranges (see Figure 6 below).

Figure 6: On the left, the blocks are separated on the y-axis. On the right, the blocks are separated on the x-axis. (The z-axis is omitted for simplicity.)

In Figure 6 above, we have chosen a coordinate system which make lesser values of x and y to be closer to the camera. Though not shown, the z axis is positive in the up direction, so a greater value makes it closer to the camera.

The following is a javascript function for determining if the first block is in front of the second:

function isBoxInFront(box1, box2) {

    // test for intersection x-axis
    // (lower x value is in front)
    if (box1.xmin >= box2.xmax) { return false; }
    else if (box2.xmin >= box1.xmax) { return true; }

    // test for intersection y-axis
    // (lower y value is in front)
    if (box1.ymin >= box2.ymax) { return false; }
    else if (box2.ymin >= box1.ymax) { return true; }

    // test for intersection z-axis
    // (higher z value is in front)
    if (box1.zmin >= box2.zmax) { return true; }
    else if (box2.zmin >= box1.zmax) { return false; }

}

Draw boxes in the correct order.

In general, a box should not be drawn until all the ones behind it are drawn. Thus, we begin by drawing the boxes that have nothing behind them. Then, we can draw the boxes that are only in front of those that are already drawn. This process continues until all boxes are drawn. (See Figure 4 below for an example.)

Figure 4: (1) Nothing is behind blue, so draw it first. (2) Draw green next since blue was the only one behind it and is already drawn. (3) Then draw red, since both blocks that were behind it have been drawn.

To implement this algorithm, each box must know exactly which boxes are behind it. We have already determined how to do this in the last section. A search must be implemented so that each box has a list of boxes behind it.

You are now armed with everything you need to know to render isometric boxes in the correct order.

A conundrum

It is possible to have a situation seen in the figure below. The aforementioned drawing methods dictate that we first draw the box with nothing behind it, but this example illustrates a case where this cannot be done.

Here are three boxes intertwined in a way such that one is always behind another. This prevents us from drawing a first box.

The figure above cheats by segmenting the orange box into two. This is one method of breaking this type of cycle.

There are formal methods used for detecting such cycles mentioned in the appendix. After detection of a cycle, the blocks in that cycle could be drawn with special clipping regions to respect front boxes or to segment a block or blocks that will break the cycle. These are solutions that I will be exploring and updating this article as my experiments progress.

Appendix

A formal description of the solution

This is a special case of the Painter's Algorithm, which handles occlusion by drawing back-to-front.

For those who are interested, our method for determining if hexagons and boxes are overlapping is a result of the hyperplane separation theorem.

Also, the way in which we determined the drawing order of the boxes is known in graph theory as a topological sort, which is essentially a depth-first search of a directed graph.

You can build a directed graph of the boxes, with directed edges to the boxes that are behind it. Topologically sorting this graph will produce an ordered list of boxes that can be drawn in that exact order.

Mathematicians will recognize this directed graph as a partially ordered set.

Finally, to prevent the aforementioned cycle conundrum, we can use Tarjan's strongly connection components algorithm. After computing these cycles, one could either split a block to prevent a cycle, or to use a clipping region to prevent drawing over any blocks that are supposed to be in front of it.

Alternative Solutions

You may be able to just use Z-buffering, though drawing order is still important for transparent sprites. Also, if all bounding boxes are unit cubes, sorting is much simpler.

Full example of working code

All the diagrams above were created using a simple isometric box renderer written in Javascript, which applies all the techniques described in this article. You can study the fully annotated source code on IsometricBlocks project on GitHub.

Real game examples

How 2.5D Sorting works in River City Ransom: Underground - allowing bounding boxes to intersect by specifying heightmaps within them (summary)
Filmation engine on the ZX Spectrum

Thanks

Thanks to Ted Suzman at buildy for introducing this problem and solution to me. And thanks to adamhayek for further insight on a general solution. And thanks to Slime0 at reddit for pointing out errors in this article by illustrating the cycle example shown in this article, and for illustrating why we cannot deduce relative drawing order between two non-overlapping boxes. Thanks to Mark Nelson for extra context on painter's algorithm and z-buffering.