Dealing with occlusion in an isometric sandbox game

Question

Imagine a 3D sandbox game like Minecraft with third-person isometric graphics. If the camera only moves in two dimensions, and doesn't rotate, then a large portion of the world will always be occluded e.g. caves, areas behind mountains and buildings, etc. Obviously this isn't acceptable.

I'm trying to figure out how such a game could deal with this issue while preserving certain properties: the world must be entirely buildable/destructible and must extend in some manner along all three axes. Other than that, nothing is off the table.

I can't think of any simple culling algorithm that wouldn't either leave too much occluded or needlessly cull things. Which features are visible where seems to be a very high level design issue. If you are underground, you don't want to see the ground above you at all. But some small objects you probably never want culled, even when standing behind them.

And it's not at all clear what you would want to do with medium-sized objects, like buildings... perhaps make them translucent when the player walks behind them. But how would such objects be classified? And how would you distinguish the outside of the building from the inside? You probably don't want the inside of buildings to become visible when you walk behind them.

If the player can place objects anywhere, what happens if they place an object behind an occluder? Is it now impossible to interact with this object without destroying the thing in front of it, even when the player is standing right next to it? What about important features on back-facing surfaces? Are they never rendered at all?

It seems to me that isometry is just not capable of practically representing arbitrary three dimensional architecture, which suggests that the game needs to be designed in such a way that arbitrary architecture can't be built. Rather, it needs to be constrained to some kind of 2.5D model, where occluded things simply cannot exist. But how could a world like that feel consistent and logical to the player while they dig and build in it?

Answer 1

Deciding which criterion to start with

I'd say the reason you're asking the question in the way you have (i.e. not a single question but many smaller ones), is because you have various explicit requirements that you have not reconciled: culling what should be culled, not culling what shouldn't be culled, and using alpha where you need foreground objects to not obscure key gameplay objects in the midfield. I guess you're less-than-willing to start down a path that might not fit your exact requirements. But sometimes, experimentation is the only way to get rolling. Choose to implement ONE of these. To start with, draw EVERYTHING, just allow overdraw for now -- given a limited world height, even heavy overdraw should not grind your FPS too badly (unless you're writing in ActionScript or JavaScript, and the overdraw is major), because you're looking toward the ground, not toward some far horizon. Even so, I provide a solution for isometric occlusion culling below. Anyway, from drawing everything, you will find that it's much easier to simply move toward achieving your other two criterion. You need a base to experiment with.

Foreground alpha

I assume you don't want the player to be hidden behind walls. How about enemies? Items? Controls (including ones situated on back-facing walls)? I'll have to assume all, for the purposes of responding.

Whatever is directly between your ortho camera and any gameplay-critical entities, must be made transparent OR culled completely from the view.

For walls near to your player, simply make surface voxels transparent (never consider non-surface voxels for rendering). You need to determine the silhouette of the entire clump that would occlude, and render it only as a silhouette at a single alpha (say 10%). If you were to simply treat each voxel as being at a given alpha, their transparencies might combine to be so opaque so that you would hardly see the critical entities beyond them.

You furthermore mentioned the insides of buildings, which could equally be seen as other rooms (if eg. your game was in a dungeon environment). The best way to deal with this is to keep a list of bounding boxes describing other rooms, and use these for additional zone-based culling. This could be the same as, or separate from, your level chunks. I would recommend it be separate as chunks should ideally be based on a uniform grid in order to keep processing times uniform regardless of where in the world you are. Using non-uniform bounding boxes can mess with this.

Culling what is definitely occluded by opaque objects

Consider a standard isometric engine. Occlusion is often not explicitly handled, because the degree of occlusion is minimal enough in most cases that we can afford to ignore it. In your case, however, it is necessary to know what not to draw. This is a perfect application of the reverse painter's algorithm. Determine the lines of voxel "bases" closest to the lower edge of your screen. In each such "tile" along this line, there exists a column of voxels. Draw each voxel in this column, from the base point near the bottom of the screen, upwards. Proceed to the next row above it, and repeat, till you've drawn all rows in the scene. As for knowing what NOT to draw, this image represents the tile base positions on your screen (the bottoms of all voxels at sea level):

* * * * * * *
 * * * * * *
* * * * * * *
 * * * * * *  <- Second last row
* * * * * * * <- Baseline row

Do you see how the second last row's voxel bases are offset from the baseline's? Every second row's tile centre lies exactly between the next and previous line's x-centres? Same thing, with graphics:

Because of this, the first (leftmost) tile column in the second-from-last line is only occluded if the first AND second tile columns in the baseline BOTH exceed the height of the column that lies behind/between them. If they are equal, then you won't see the sides of the voxel behind, but you will see it's top -- so it will still need to be drawn. If less than both, it is completely occluded.

This solution will not entirely eliminate overdraw (since you still need to draw a whole column even if only one of the two in front of it is occluding it), but it certainly will make a major difference. For complete elimination of overdraw at a per-pixel level, see below.

Dealing with overhangs / floating voxels shouldn't be too hard to figure out given the above.

Answer 2

I have considered this problem myself and the only solution I have been able to come up with is to allow rotating the camera (or more technically correct, the map).

This will let you see the player/items that are in range (by removing anything that is blocking your observer line of sight), and it also lets you interact with any item even if you are deep underground, because the things that are between you as the observer and the player is removed, so if you want to interact with any of the blank stuff, you just rotate the camera, and make the other side transparent instead.

I've thought of how to make this as unnoticeable (hassle-free) as possible, and one or two hotkeys near the wasd keys may be appropriate (C or V rotates the map 90 degrees, and as a result the wasd keys change orientation, but this is not noticeable, because "up" is still "up", even though internally the direction is a different one.)