How can I improve rendering speeds of a Voxel/Minecraft type game?

Question

I'm writing my own clone of Minecraft (also written in Java). It works great right now. With a viewing distance of 40 meters I can easily hit 60 FPS on my MacBook Pro 8,1. (Intel i5 + Intel HD Graphics 3000). But if I put the viewing distance on 70 meters, I only reach 15-25 FPS. In the real Minecraft, I can put the viewing disntance on far (= 256m) without a problem. So my question is what should I do to make my game better?

The optimisations I implemented:

• Only keep local chunks in memory (depending on the player's viewing distance)
• Frustum culling (First on the chunks, then on the blocks)
• Only drawing really visible faces of the blocks
• Using lists per chunk that contain the visible blocks. Chunks that become visible will add itself to this list. If they become invisible, they are automatically removed from this list. Blocks become (in)visible by building or destroying a neighbour block.
• Using lists per chunk that contain the updating blocks. Same mechanism as the visible block lists.
• Use nearly no new statements inside the game loop. (My game runs about 20 seconds until the Garbage Collector is invoked)
• I'm using OpenGL call lists at the moment. (glNewList(), glEndList(), glCallList()) for each side of a kind of block.

Currently I'm even not using any sort of lighting system. I heard already about VBO's. But I don't know exactly what it is. However, I'll do some research about them. Will they improve performance? Before implementing VBO's, I want to try to use glCallLists() and pass a list of call lists. Instead using thousand times glCallList(). (I want to try this, because I think that the real MineCraft doesn't use VBO's. Correct?)

Are there other tricks to improve performance?

VisualVM profiling showed me this (profiling for only 33 frames, with a viewing distance of 70 meters):

Profiling with 40 meters (246 frames):

Note: I'm synchronising a lot of methods and code blocks, because I'm generating chunks in another thread. I think that acquiring a lock for an object is a performance issue when doing this much in a game loop (of course, I'm talking about the time when there is only the game loop and no new chunks are generated). Is this right?

Edit: After removing some synchronised blocks and some other little improvements. The performance is already much better. Here are my new profiling results with 70 meters:

I think it is pretty clear that selectVisibleBlocks is the issue here.

Thanks in advance!
Martijn

Update: After some extra improvements (like using for loops in stead of for each, buffering variables outside loops, etc...), I now can run viewing distance 60 pretty good.

I think I'm going to implement VBO's as soon as possible.

PS: All source code is available on GitHub:
https://github.com/mcourteaux/CraftMania

Answer 1

You mention doing frustum culling on individual blocks — try throwing that out. Most rendering chunks should be either entirely visible or entirely invisible.

Minecraft only rebuilds a display list/vertex buffer (I don't know which it uses) when a block is modified in a given chunk, and so do I. If you're modifying the display list whenever the view changes, you're not getting the benefit of display lists.

Also, you appear to be using world-height chunks. Note that Minecraft uses cubical 16×16×16 chunks for its display lists, unlike for load and save. If you do that, there's even less reason to frustum cull individual chunks.

(Note: I have not examined the code of Minecraft. All of this information is either hearsay or my own conclusions from observing Minecraft's rendering as I play.)

---

More general advice:

Remember that your rendering executes on two processors: CPU and GPU. When your frame rate is insufficient, then one or the other is the limiting resource — your program is either CPU-bound or GPU-bound (assuming it isn't swapping or having scheduling problems).

If your program is running at 100% CPU (and doesn't have an unbounded other task to complete), then your CPU is doing too much work. You should try to simplify its task (e.g. do less culling) in exchange for having the GPU do more. I strongly suspect this is your problem, given your description.

On the other hand, if the GPU is the limit (sadly, there aren't usually convenient 0%-100% load monitors) then you should think about how to send it less data, or require it to fill fewer pixels.

Answer 2

What's calling Vec3f.set so much? If you're building what you want to render from scratch each frame then that's definitely where you'd want to start to speed it up. I'm not much of an OpenGL user and I don't know much about how Minecraft renders, but it seems that the math functions you using are killing you right now (just look how much time you spend in them and the number of times they get called - death by a thousand cuts calling them).

Ideally your world would be segmented up such that you can group stuff to render together, building Vertex Buffer Objects and re-using them across multiple frames. You'd only need to modify a VBO if the world it represents changes somehow (like the user edits it). You can then create/destroy VBO's for what you're representing as it comes into range of being visible to keep memory consumption down, you'd only take the hit as the VBO was created rather than every frame.

If the "invocation" count is correct in your profile, you're calling an awful lot of things an awful lot of times. (10 million calls to Vec3f.set... ouch!)

Answer 3

My description (from my own experimentation) here is applicable:

For voxel rendering, what is more efficient: pre-made VBO or a geometry shader?

Minecraft and your code likely uses the fixed function pipeline; my own efforts have been with GLSL but the gist is generally applicable, I feel:

(From memory) I made a frustum that was a half-block bigger than the screen frustum. I then tested the center-points of each chunk (minecraft has 16*16*128 blocks).

The faces in each has spans in an element-array VBO (many faces from chunks share the same VBO until it is 'full'; think like malloc; those with the same texture in the same VBO where possible) and the vertex indices for the north faces, south faces and so on are adjacent rather than mixed. When I draw, I do a glDrawRangeElements for the north faces, with the normal already projected and normalized, in a uniform. Then I do the south faces and so on, so the normals are not in any VBO. For each chunk, I only have to emit the faces that will be visible - only those in the center of the screen need to draw left and right sides, for example; this is simple GL_CULL_FACE at an application level.

The biggest speedup, iirc, was culling interior faces when polygonizing each chunk.

Also important is texture-atlas management and sorting faces by texture and putting the faces with the same texture in the same vbo as those from other chunks. You want to avoid too many texture changes and sorting the faces by texture and so on minimizes the number of spans in the glDrawRangeElements. Merging adjacent same-tile faces into bigger rectangles was also a big deal. I talk about merging in the other answer cited above.

Obviously you only polygonize those chunks that have ever been visible, you may discard those chunks that haven't been visible for a long time, and you re-polygonize chunks that are edited (as this is a rare occurrence compared to rendering them).

Answer 4

Where are all your comparisons (BlockDistanceComparator) coming from? If it's from a sort function, could that be replaced with a radix sort (which is asymptotically faster, and not comparison based)?

Looking at your timings, even if the sorting itself isn't that bad, your relativeToOrigin function is being called twice for each compare function; all of that data should be computed once. It should be faster to sort an auxiliary structure e.g.

struct DistanceIndexPair
{
    float m_distanceSquaredFromOrigin;
    int m_index;
};

and then in pseudoCode

// for i = 0..numBlocks
//     distanceIndexPairs[i].m_distanceSquaredFromOrigin = ...;
///    distanceIndexPairs[i].m_index = i;
// sort distanceIndexPairs
// for i = 0..numBlocks
//    sortedBlock[i] = unsortedBlocks[ distanceIndexPairs.m_index ]

Sorry if that's not a valid Java struct (I haven't touched Java since undergrad) but hopefully you get the idea.

Answer 5

Yeah use VBOs and CULL facing, but that goes for pretty much every game. What you want to do is only render the cube if it is visible to the player, AND if the blocks are touching in a specific way (let's say a chunk that you cannot see because it's underground) you add the vertices of the blocks and make it almost like a "bigger block", or in your case- a chunk. This is called greedy meshing and it drastically increases performance. I am developing a game (voxel-based) and it uses a greedy meshing algorithm.

Instead of rendering everything like this:

It renders it like this:

The downside to this is that you have to do more calculations per chunk on the initial world build, or if the player removes/adds a block.

pretty much any type of voxel engine needs this for good performance.

What it does is checks to see if the block face is touching another block face, and if so: only render as one (or zero) block face(s). It is an expensive touch when you are rendering chunks really fast.

public void greedyMesh(int p, BlockData[][][] blockData){
        boolean[][][][] mask = new boolean[blockData.length][blockData[0].length][blockData[0][0].length][6];

    for(int side=0; side<6; side++){
        for(int x=0; x<blockData.length; x++){
            for(int y=0; y<blockData[0].length; y++){
                for(int z=0; z<blockData[0][0].length; z++){
                    if(data[x][y][z] > Material.AIR && !mask[x][y][z][side] && blockData[x][y][z].faces[side]){
                        if(side == 0 || side == 1){
                            int width = 0;
                            int height = 0;
                            loop:
                            for(int i=y; i<blockData[0].length; i++){
                                if(i == y){
                                    for(int j=z; j<blockData[0][0].length; j++){
                                        if(!mask[x][i][j][side] && blockData[x][i][j].id == blockData[x][y][z].id && blockData[x][i][j].faces[side]){
                                            width++;
                                        }else{
                                            break;
                                        }
                                    }
                                }else{
                                    for(int j=0; j<width; j++){
                                        if(mask[x][i][z+j][side] || blockData[x][i][z+j].id != blockData[x][y][z].id || !blockData[x][i][z+j].faces[side]){
                                            break loop;
                                        }
                                    }
                                }
                                height++;
                            }
                            for(int i=0; i<height; i++){
                                for(int j=0; j<width; j++){
                                    mask[x][y+i][z+j][side] = true;
                                }
                            }

                            if(side == 0)
                                meshes.get(p).add(new Mesh(new VoxelVector3i(x+1, y, z), new VoxelVector3i(x+1, y+height, z+width), new VoxelVector3i(1, 0, 0), Material.getColor(data[x][y][z])));
                            else
                                meshes.get(p).add(new Mesh(new VoxelVector3i(x, y, z+width), new VoxelVector3i(x, y+height, z), new VoxelVector3i(-1, 0, 0), Material.getColor(data[x][y][z])));
                        }else if(side == 2 || side == 3){
                            int width = 0;
                            int height = 0;
                            loop:
                            for(int i=x; i<blockData.length; i++){
                                if(i == x){
                                    for(int j=z; j<blockData[0][0].length; j++){
                                        if(!mask[i][y][j][side] && blockData[i][y][j].id == blockData[x][y][z].id && blockData[i][y][j].faces[side]){
                                            width++;
                                        }else{
                                            break;
                                        }
                                    }
                                }else{
                                    for(int j=0; j<width; j++){
                                        if(mask[i][y][z+j][side] || blockData[i][y][z+j].id != blockData[x][y][z].id || !blockData[i][y][z+j].faces[side]){
                                            break loop;
                                        }
                                    }
                                }
                                height++;
                            }
                            for(int i=0; i<height; i++){
                                for(int j=0; j<width; j++){
                                    mask[x+i][y][z+j][side] = true;
                                }
                            }

                            if(side == 2)
                                meshes.get(p).add(new Mesh(new VoxelVector3i(x, y+1, z+width), new VoxelVector3i(x+height, y+1, z), new VoxelVector3i(0, 1, 0), Material.getColor(data[x][y][z])));
                            else
                                meshes.get(p).add(new Mesh(new VoxelVector3i(x+height, y, z+width), new VoxelVector3i(x, y, z), new VoxelVector3i(0, -1, 0), Material.getColor(data[x][y][z])));
                        }else if(side == 4 || side == 5){
                            int width = 0;
                            int height = 0;
                            loop:
                            for(int i=x; i<blockData.length; i++){
                                if(i == x){
                                    for(int j=y; j<blockData[0].length; j++){
                                        if(!mask[i][j][z][side] && blockData[i][j][z].id == blockData[x][y][z].id && blockData[i][j][z].faces[side]){
                                            width++;
                                        }else{
                                            break;
                                        }
                                    }
                                }else{
                                    for(int j=0; j<width; j++){
                                        if(mask[i][y+j][z][side] || blockData[i][y+j][z].id != blockData[x][y][z].id || !blockData[i][y+j][z].faces[side]){
                                            break loop;
                                        }
                                    }
                                }
                                height++;
                            }
                            for(int i=0; i<height; i++){
                                for(int j=0; j<width; j++){
                                    mask[x+i][y+j][z][side] = true;
                                }
                            }

                            if(side == 4)
                                meshes.get(p).add(new Mesh(new VoxelVector3i(x+height, y, z+1), new VoxelVector3i(x, y+width, z+1), new VoxelVector3i(0, 0, 1), Material.getColor(data[x][y][z])));
                            else
                                meshes.get(p).add(new Mesh(new VoxelVector3i(x, y, z), new VoxelVector3i(x+height, y+width, z), new VoxelVector3i(0, 0, -1), Material.getColor(data[x][y][z])));
                        }
                    }
                }
            }
        }
    }
}

Answer 6

It would seem that your code is drowning in objects and function calls. Gauging the numbers, it doesn't seem like there is any in-lining happening.

You could try to find a different Java environment, or simply mess with the settings of the one you have, but a plain and simple way of making your code, not fast, but a good deal less slow is at least internally in Vec3f to stop coding OOO*. Make every method self containing, don't call any of the other methods just to perform some menial task.

Edit: While there is overhead all over the place it would seem that ordering the blocks before rendering is the worst performance eater. Is that really necessary? If so you should probably start out by going through a loop and calculate each blocks distance to origin, and then sort by that.

*Overly Object Oriented

Answer 7

You could also try to break down Math operations down to bitwise operators. If you have 128 / 16, try to make a bitwise operator: 128 << 4. This will help a lot with your problems. Don't try to make things run at full speed. Make your game update at a rate of 60 or something, and even break that down for other things, but you would have to do destroying and or placing voxels or you would have to make a todo-list, which would bring down your fps. You could do an update rate of about 20 for entities. And something like 10 for world updates and or generation.