How to do face removal in a unit-cube world a la Minecraft?

Question

Important note: This question is NOT about geometry culling (frustrum culling, back face culling, occlusion culling or any of their friends.) This question is about geometry elimination at set-up time, long before we get to culling and rendering.

In a unit-cube rendered world (a la MineCraft), I'm trying to find algorithms for how to remove from my list of geometry faces that can't possibly be seen from any angle, no matter where the camera is.

For example, imagine 2 squares:

+----+      +----+
|    |      |    |
|    |      |    |
+----+      +----+

clearly there are 8 visible sides (4 on each square.) Now I move the squares together, vis:

+----+----+
|         |
|         |
+----+----+

Rather than having 8 sides, now I only have 6! The two that are touching in the middle can't be seen, no matter where the camera is placed, nor what angle it is facing. (The squares are textured differently, so we can't call it 4 sides.)

(The same thing works in 3D with cubes, but 12 faces (6 per cube) become 10 as the 2 touching are eliminated.)

My question is: what are some algorithms that help me to recognize these hidden faces? (I'm happy to do my own Googling, but I don't even know what this is called!) In particular, I'm looking for something that handles hollow spots in the middle -- spots which COULD be visible if you were in there but, because they're surrounded by geometry, you can't see them.

For example:

+----+----+----+----+
|                   |
|                   |
+    +----+         +
|    |    |         |
|    | A  |         |
+    +----+         +
|                   |
|                   |
+----+----+----+----+

In this case, one might think there 18 "visible" sides but, because we know for a fact that the camera is outside of the geometry, the 4 sides in square "A" aren't visible.

To further complicate things, I'm hoping to find an algorithm that can make quick updates if a block is added or removed (again, a la MineCraft.)

Thanks!

Answer 1

The first part of your question is really quite simple. For each cube, if it is directly adjacent to another cube, you remove the face it shares with that cube.

This is not something that should be a performance issue (outside of the cost of modifying and uploading the changed vertex data), since you will only recompute this when a block is placed or removed. The effects of placing and removing a block are quite local; it will only affect the 6 neighboring cubes and itself, so it shouldn't be a problem. You also don't need any specialized data structures, other than the obvious ones you need to handle a cube-based environment.

The initial cost of building the terrain may be something, but that's a one-time cost that you can live with. Factor it into your loading time. If you're doing a lot of placements and removals in the space of a frame, it could be an issue.

The more difficult issue is removing sealed interiors. My suggestion: it's not worth it. By trying to remove sealed interiors, placing or removing a block becomes a non-local operation. You would probably get more performance by spending time optimizing your batch count (use texture atlases/arrays where possible) and your vertex data.

To remove sealed interiors, you need to be able to detect interiors. And therefore, you will need to maintain a bidirectional graph of adjacent faces. For each face, it will have four adjacent faces. Faces that were culled because it was between two adjacent cubes (heretofore referred to as "dead faces") should not be part of the graph.

When a cube is placed, you must update the adjacency information for the face graph. Dead faces need to be removed. The adjacency for live faces after placement needs to incorporate the new faces that were added due to the new block that was placed. The algorithm to do this should be fairly straightforward if you sit down and map out the possibilities. For example, if you have this square:

  A
+++++
+   +
+   + B
+   +
+++++

The faces A and B are adjacent. If you place a new block, you change the adjacency:

     +++++
     +   +
   C +   +
     +   +
  A  +++++
+++++  D
+   +
+   + B
+   +
+++++

A is now adjacent to C and B adjacent to D.

When a cube is removed, you must again update the adjacency information for the face graph. Essentially, you have to reverse the previous operation.

The point of this adjacency graph is this: if all of the non-dead faces are connected in the graph, then exactly one cycle of the graph will be visible; all other graph cycles will not be visible. A cycle of the graph being a group of faces that are all connected to one another, either directly or indirectly.

The big question is this: how do you find the visible cycle? The following algorithm assumes that blocks are placed/removed by an entity. This means that at least one face of any block that is placed is visible. It also means that any dead faces that become live by removing a block are visible.

When you place a block, you may create one or more new cycles of faces. To detect this, you first find all of the non-dead faces (the ones that aren't directly adjacent to something) that you have created by placing the block. At least one of these will be visible; find that face.

Then, for every other non-dead face on the new block, use an A* (A-star) graph search to find that face. A* is a priority-queue-based graph search algorithm. In this case, the "distance" for the algorithm is the distance between the square that the current face is on and the square that the visible face is on.

If the A* cannot find the face, then you know that every face that you searched through (you should probably store them in a buffer as you test them) is part of a non-visible cycle and can therefore be culled. You should mark these faces as being non-visible for later reference.

Removing a block is much easier. When you're removing a block, at least one face of the block must be visible (see the assumption above). Therefore, if the block to be removed had some non-visible faces, every face in a cycle including those non-visible faces must become visible. So before removing the block, check it for any non-visible faces. If there are any, use a depth-first search to find all of the faces in that cycle, and put them in a buffer. Once you remove the block, all of those faces now become visible.

Now, if you're able to teleport blocks, things become more complex. When you place a block, there is the chance that none of that block's faces are visible. So what you need to do is find a face somewhere in the world that is visible. Then do your A* searching towards that face as normal. It would be good if the visible face were somewhere nearby, so the search didn't have to go too far.

With removal, what you have to do is find all of the non-visible face cycles adjacent to the block. Then you need to find that one visible face as before. Then you remove the block and search those cycles with A* to see if they can find the visible face. Those cycles that can are visible. Those cycles that cannot are not visible.

Also, you need to have a special case for removing a block that had no live faces (ie: is fully embedded in other blocks). This creates a 6-face cycle that is non-visible.

Perhaps now you see why it's probably not worth the effort? Honestly, unless you have actual profiling data in hand that shows that you need this, I strongly advise you not to pursue that. You will likely be making more work than necessary, as well as potentially spending a lot of time on something irrelevant.

Now, I wrote this post off the cuff; I thought of the simplest algorithm I could that would work. I have not researched possible improvements to this algorithm, like preemptively finding block placements that could create interiors, or finding blocks that if removed would make an interior visible. So I freely admit that this algorithm is pretty brute force. But finding a better one will require some effort, so again, unless you have profiling data in had saying that you need to do this to achieve the performance you want, I advise against it.