Optimized rendering of a cube mesh world

Question

I want to render a cube-mesh (a.k.a. Minecraft-style) world. If I render each existing cube it will eat up FPS pretty quickly. How can I optimize it? I understand that the point is to not render invisible meshes (faces?) but my problem is to find out what is invisible and what isn't.

Answer 1

You'll have good use of a isSolidAt(x,y,z) function. This will be useful for not only the action you want to preform, but other things such as collision checking.

Basically you want to iterate through your cubes and check which faces will be hidden. You know they're hidden when the adjacent cube is solid. For example some pseudo code:

Verticies[] verticesToDraw
for(x = 0 to x = chunkXMax)
    for(y = 0 to y = chunkYMax)
        for(z = 0 to z = chunkZMax) 
            if(!isSolidAt(x+1,y,z))
                verticesToDraw += AddXPlusFace(x,y,z)
            if(!isSolidAt(x-1,y,z))
                verticesToDraw += AddXMinusFace(x,y,z)
            if(!isSolidAt(x,y+1,z))
                verticesToDraw += AddYPlusFace(x,y,z)
            //and so on for the rest of the faces
Buffer(verticesToDraw)

Of course you'll be more detailed. You can also keep track of the faces in a separate array, perhaps using a byte with bit positions 0 through 5 indicating whether a face is set or not.

Eventually you'll probably want to improve upon this with special checks for "short cubes", transparent but solid cubes and so on.

EDIT

I've updated the code to show that you run this on a per chunk basis. This only address the issue of faces that are invisible because they are adjacent to a solid cube. Sending the vertices for all the cubes and "letting the GPU do the culling" would be a bad idea. I assume you may know that already since you asked this question. The above code is only run when the chunk is dirty, as in, something has changed. It's not to be run every frame.

You'll see significant performance improvements with the above change. I know because I've gone through the process before. You may also find performance improvements with spacial partitioning, but the improvements are unlikely to be as significant as drastically reducing the number of vertices sent to the GPU (as you will do when you implement the above).

Answer 2

There are two problems to this:

1. Eliminate entire cubes to avoid rendering them.
2. Eliminate invisible faces

As for #1, you need to take a look at space partitioning algorithms. They divide up space into smaller subspaces in order to make searches faster (in your case, you're searching for every cube that collides with your view frustum).

Since most things you have are static, and also cubes, an easy suggestion for you would be the Octree.

As for #2: I'm pretty sure that's not going to be a problem. Not drawing faces that you can't see with cubes usually equals not drawing faces that don't face towards you. The process of this is called backface culling and is usually done by the graphics card.

So the only really limiting factor for #2 could be bandwidth consumption on the way to your graphics card. But I really doubt that's the case, since your world is static and thus only needs to be sent to the graphics card whenever something in the terrain changes, which will not be very often. Even if you sent everything you need to draw over once every frame, this will most likely be no bottleneck as long as you batch everything together in a reasonable manner (faces with same textures, etc). However, if this really turns out to be a bottleneck, you should search the internet for software backface culling algorithms. Here's an example.

Answer 3

A simple octree should be a fine enough algorithm for this- it can achieve this in O(log(N)). In addition, you have an advantage in that you can prove which cubes are visible and which aren't in easy time.

Let's say that you start off with a totally flat map. You know in advance that only the top level of cubes are visible, since all the ones below it are concealed. Then when the player removes a cube, you know in advance which cubes are now visible. When the player adds a cube, it's easy to test if the cubes near it have been blocked from view. This is because each cube can only affect the potential visibility of the six cubes on it's primary faces. Thus, it's trivial to exploit the temporal coherency of the map to prove which cubes are visible and which aren't in a very short period of time. If you use terrain generation or static maps, then simply apply this logic when your algorithms apply each change.

This will easily provide you with a small count of visible cubes, and frustum culling with an octree should do the rest.

Backface culling on the GPU is more than sufficient for eliminating invisible faces.