35
\$\begingroup\$

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):

enter image description here

Profiling with 40 meters (246 frames):

enter image description here

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:

enter image description here

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

\$\endgroup\$
9
  • 2
    \$\begingroup\$ Can you give us a profile shot at 40m so we can see what might be scaling up faster than another? \$\endgroup\$
    – James
    Jan 19, 2012 at 20:39
  • \$\begingroup\$ Maybe too specified, but if you consider, is just asking techniques of how to speedup a 3D game, sound interesting. But the title may scare ppl. \$\endgroup\$ Jan 19, 2012 at 20:45
  • \$\begingroup\$ @Gtoknu: What do you suggest as title? \$\endgroup\$ Jan 19, 2012 at 20:51
  • 6
    \$\begingroup\$ Depending on who you ask, some people would say that Minecraft really isn't that fast, either. \$\endgroup\$
    – thedaian
    Jan 19, 2012 at 20:51
  • \$\begingroup\$ I think something like "Which techniques can speed up a 3D game" should be a lot better. Think of something, but try not to use the word "best" or try to compare to some other game. We can't tell exactly what they use on some games. \$\endgroup\$ Jan 19, 2012 at 21:04

7 Answers 7

15
\$\begingroup\$

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.

\$\endgroup\$
3
  • 2
    \$\begingroup\$ Great reference, your research on it mentioned on your wiki was very helpful to me! +1 \$\endgroup\$ Apr 17, 2012 at 5:47
  • \$\begingroup\$ @OP: only render visible faces (not blocks). A pathological but monotonic 16x16x16 chunk will have nearly 800 visible faces, while the contained blocks will have 24,000 visible faces. Once you've done that, Kevin's answer contains the next most important improvements. \$\endgroup\$
    – AndrewS
    Jul 29, 2014 at 17:54
  • \$\begingroup\$ @KevinReid There are some programs to help with performance debugging. AMD GPU PerfStudio for example tells you if its CPU or GPU bound and on GPU what component is the bound(texture vs fragment vs vertex, etc) And I am sure Nvidia has something similar too. \$\endgroup\$
    – akaltar
    Jul 7, 2015 at 10:02
3
\$\begingroup\$

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!)

\$\endgroup\$
1
  • \$\begingroup\$ I use this method for tons of things. It simply sets the three values for the vector. This is much better than allocating each time a new object. \$\endgroup\$ Jan 19, 2012 at 22:07
2
\$\begingroup\$

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).

\$\endgroup\$
2
  • \$\begingroup\$ I like the idea of your frustum optimisation. But aren't you mixing up the terms "block" and "chunk" in your explanation? \$\endgroup\$ Jan 20, 2012 at 22:55
  • \$\begingroup\$ probably yes. A chunk of blocks is a block of blocks in English. \$\endgroup\$
    – Will
    Jan 21, 2012 at 15:02
1
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ I find this amusing. Java doesn't have structs. Well, there is something called like that in the Java world but it has to do with databases, not the same thing at all. They can create a final class with public members, I guess that works. \$\endgroup\$
    – Theraot
    May 18, 2017 at 11:32
1
\$\begingroup\$

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:

render

It renders it like this:

render2

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])));
                        }
                    }
                }
            }
        }
    }
}
\$\endgroup\$
2
  • 1
    \$\begingroup\$ And is it worth it? It seems like an LOD system would be more appropriate. \$\endgroup\$
    – House
    Jun 5, 2017 at 22:45
  • \$\begingroup\$ I have actually implemented this into my voxel game and was very surprised to find that it does not improve performance in my game at all, furthermore, having greedy meshing might even slow down my game, specifically because of the texture tiling in the shader and re-generating of chunks for lightmap changes. \$\endgroup\$
    – X Builder
    Apr 20 at 0:39
0
\$\begingroup\$

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

\$\endgroup\$
3
  • \$\begingroup\$ Yep, you'll save memory, but lose CPU! So OOO is not too good in realtime games. \$\endgroup\$ Jan 20, 2012 at 0:00
  • \$\begingroup\$ As soon as you start profiling (and not just sampling), any inlining that the JVM normally does vanishes. It's kind of like quantum theory, can't measure something without chaning the outcome :p \$\endgroup\$
    – Michael
    Jan 20, 2012 at 0:28
  • \$\begingroup\$ @Gtoknu That is not universally true, at some level of OOO the function calls start to take up more memory than inline code would. I'd say there is a good part of the code in question that is around the break even point for memory. \$\endgroup\$ Jan 20, 2012 at 0:36
0
\$\begingroup\$

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.

\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .