3
\$\begingroup\$

I'm trying to create a screensaver, so strictly speaking this isn't for developing a game, but the subjects discussed on this SE site are a better match than any of the other sites, and I think the answer to my problem will be of value to game developers facing the same issue.

I'm trying to render an isometric grid of bricks, using 2D graphics to represent a 3D grid of bricks.

The algorithm I'm using is rendering them in the wrong order so that bricks are appearing as if they're on top of bricks which they're actually behind. For example:

render order bug 1

The white, black, and blue bricks should be rendering behind the long red brick. In terms of render order, they should be drawn before the red brick, but because the red brick is 1 step lower along the Z axis, it gets rendered first.

All of the bricks are aligned to integer coordinates. The "flat" bricks are 1 unit tall, and the "regular" bricks are 3 units tall.

The code I've got so far is:

    for (int i = 0; i < world.getDimension().z; i++) {
        for (int j = world.getDimension().y - 1; j >= 0; j--) {
            for (int k = 0; k < world.getDimension().x; k++) {
                BrickInstance brick = world.getBrickGrid().get(k, j, i);
                if (brick != null && !brick.hasBeenProcessed()) {
                    try {
                        BrickRenderer renderer = getBrickRenderer(brick);
                        renderer.setBrick(brick);
                        renderer.setGraphicsOffset(xOffset, yOffset);
                        renderer.drawBrick(gfx);
                    } catch (InstantiationException | IllegalAccessException e) {
                        e.printStackTrace();
                    }
                }
            }
        }
    }

So it loops along z, y, and x axes to determine render order, and the first time it encounters a brick in the grid, it renders the brick and marks it as done.

I also tried swapping the x and z axes:

    for (int i = 0; i < world.getDimension().x; i++) {
        for (int j = world.getDimension().y - 1; j >= 0; j--) {
            for (int k = 0; k < world.getDimension().z; k++) {
                BrickInstance brick = world.getBrickGrid().get(i, j, k);
                ...

This seems to help at first, but the same problem occurs, a little less obviously:

render order bug 2

Here the 1x4x1 green brick is sitting on the 1x1x1 blue brick, but it renders behind it instead of on top of it.

What order should I be rendering these elements so that they overlap correctly? What should my algorithm look like, either in code or pseudo-code or plain English?


Github link (I linked to the specific commit, so 6 months from now it should still link to the right version)

\$\endgroup\$
  • 1
    \$\begingroup\$ you will always (!) run into z-sorting issues when you use non-uniform assets (objects bigger than just 1 tile). you can either go full 3D or slice up you objects into multiple 1-tile big objects and sort each individually. (not more time for a full answer, sry) \$\endgroup\$ – ScrambledRK Aug 1 '15 at 6:48
3
\$\begingroup\$

What is the problem?

Generally speaking, you want to do a topological sorting, where the nodes are your bricks and the edges mean "is this node behind that other node" relationship.

So all you need to do in order to sort anything anywhere is to decide on "is behind" relationship.

It seems that your code treats bricks as uniform objects in a grid, meaning a single brick should always fit dimensions of a single tile. But your picture shows that some of your bricks are non-uniform, they can have different volume spanning several tiles. Can you imagine an "is behind" relationship to sort the following configuration of such bricks in your world?

sorting hell

If you can, congratulations :-) (seriously though, thing is that any "is behind" relationship will not be transitive in your world).

Suggested solution

So, like ScrambledRK said, it would be best to represent your bigger-than-a-tile bricks as a combination of smaller bricks taking a tile each. Tile size should be equal to the smallest possible brick size. Then you can use a simple "farthest from origin" sorting function: the further up the screen the object is, the earlier it should be drawn. In your case sorting is not really needed (yet?), so it would be sufficient to use any of these render strategies.

Bonus round

If you dislike suggested approach for some reason, I guess it also possible to emulate 3D in 2D by giving your cubes volume. In other words, turn them into axis-aligned bounding boxes and sort using boxes bounds. So in topological sort you would compare the pseudo-3d bounds of bricks with each other for "is behind" relationship, like

bool is_B_behind_A = (B.Bounds.Min.X < A.Bounds.Max.X && B.Bounds.Min.Y < A.Bounds.Max.Y && B.Bounds.Min.Z < A.Bounds.Max.Z) .

Naive implementation is easy to code, but would be very slow, so some kind of spatial partitioning is a must. But seriously, at this point it would be much easier to ditch 2D for 3D with 'free' depth buffer sorting, since your bricks are fully opaque.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.