74
\$\begingroup\$

I found Minecraft's marvelous large worlds extremely slow to navigate, even with a quad core and meaty graphics card.

I assume Minecraft's slowness comes from:

  • Java, as spatial partitioning and memory management are faster in native C++.
  • Weak world partitioning.

I could be wrong on both assumptions. However, this got me thinking about the best way to manage large voxel worlds. As it is a true 3D world, where a block can exist in any part of the world, it is basically a big 3D array [x][y][z], where each block in the world has a type (i.e BlockType.Empty = 0, BlockType.Dirt = 1, etc.)

I assume that to make this sort of world perform well, you would need to:

  • Use a tree of some variety (oct/kd/bsp) to split all the cubes out; it seems like an oct/kd would be the better option, as you can just partition on a per cube level not a per triangle level.
  • Use some algorithm to work out which blocks can currently be seen, as blocks closer to the user could obfuscate the blocks behind, making it pointless to render them.
  • Keep the block object themselves lightweight, so it is quick to add and remove them from the trees.

I guess there is no right answer to this, but I would be interested to see peoples' opinions on the subject. How would you improve performance in a large voxel-based world?

\$\endgroup\$
14
  • 12
  • 2
    \$\begingroup\$ So what are you actually asking? Are you asking for good approaches to managing large worlds, or feedback on your particular approach, or opinions on the subject of managing large worlds? \$\endgroup\$ May 31, 2011 at 9:35
  • 1
    \$\begingroup\$ Good stuff so far, it is more about what is the most common common approach to these sort of things. I am not specifically after feedback on my approach as all I have proposed is what I would logically expect to happen. I just wanted more information on the subject really and there wasn't too much coming up after a couple of searches. I guess my question is not just about rendering performance but about how to manage such a large volume of data... such as chunking the areas etc \$\endgroup\$ May 31, 2011 at 12:23
  • 2
    \$\begingroup\$ So be clear and add a question to your post so we know what question we're answering. ;) \$\endgroup\$ May 31, 2011 at 12:58
  • 3
    \$\begingroup\$ What do you mean by "extremely slow to navigate"? There's definitely some slow down when the game generates new terrain, but after that, minecraft tends to handle terrain pretty well. \$\endgroup\$
    – thedaian
    May 31, 2011 at 13:32

6 Answers 6

112
\$\begingroup\$

Voxel Engine Rocks

Voxel Engine Grass

With regards to Java vs C++, I've written a voxel engine in both (C++ version shown above). I've also been writing voxel engines since 2004 (when they were not vogue). :) I can say with little hesitation that C++ performance is far superior (but it is also more difficult to code). Its less about the computational speed, and more about memory management. Hands down, when you are allocating/deallocating as much data as whats in a voxel world, C(++) is the language to beat. However, you should think about your goal. If performance is your highest priority, go with C++. If you just want to write a game without bleeding-edge performance, Java is definitely acceptable (as evidenced by Minecraft). There are many trivial/edge cases, but in general you can expect Java to run about 1.75-2.0 times slower than (well written) C++. You can see a poorly optimized, older version of my engine in action here (EDIT: newer version here). While chunk generation might seem slow, keep in mind it is generating 3D voronoi diagrams volumetrically, calculating surface normals, lighting, AO, and shadows on the CPU with brute-force methods. I have tried out various techniques and I can get about 100x faster chunk generation using various caching and instancing techniques.

To answer the rest of your question, there are many things you can do to improve performance.

  1. Caching. Wherever you can, you should compute data once. For example, I bake the lighting into the scene. It could use dynamic lighting (in screen space, as a post-process), but baking in the lighting means that I don't have to pass in the normals for the triangles, which means....
  2. Pass as little data to the video card as possible. One thing people tend to forget is that the more data you pass to the GPU, the more time it takes. I pass in a single color and a vertex position. If I want to do day/night cycles, I can just do color grading, or I can recompute the scene as the sun gradually changes.

  3. Since passing data to the GPU is so expensive, it is possible to write an engine in software which is faster in some respects. The advantage of software is that it can do all kinds of data manipulation / memory access that simply is not possible on a GPU.

  4. Play with the batch size. If you are using a GPU, performance can vary dramatically based on how big each vertex array you pass is. Accordingly, play around with the size of the chunks (if you use chunks). I've found that 64x64x64 chunks work pretty well. No matter what, keep your chunks cubic (no rectangular prisms). This will make coding and various operations (like transformations) easier, and in some cases, more performant. If you only store one value for the length of every dimension, keep in mind thats two less registers that get swapped around during compute.

  5. Consider display lists (for OpenGL). Even though they are the "old" way, they can be faster. You must bake a display list into a variable...if you call display list creation operations in realtime, it will be ungodly slow. How is a display list faster? It only updates the state, vs per-vertex attributes. This means I can pass up to six faces, then one color (vs a color for each vertex of the voxel). If you are using GL_QUADS and cubic voxels, this could save up to 20 bytes (160 bits) per voxel! (15 bytes with no alpha, although usually you want to keep things 4-byte aligned.)

  6. I use a brute-force method of rendering "chunks", or pages of data, which is a common technique. Unlike octrees, it is much easier/faster to read/process the data, although much less memory friendly (however, these days you can get 64 gigabytes of memory for $200-$300)...not that the average user has that. Obviously, you cannot allocate one huge array for the whole world (a 1024x1024x1024 set of voxels is 4 gigabytes of memory, assuming a 32-bit int is used per voxel). So you alloc/dealloc many small array, based on their proximity to the viewer. You can also alloc the data, get the necessary display list, then dump the data to save memory. I think the ideal combo might be to use a hybrid approach of octrees and arrays -- store the data in an array when doing procedural generation of the world, lighting, etc, then keep the octree around for collision detection and other less expensive tasks.

  7. Render near to far...a pixel clipped is time saved. The gpu will toss a pixel if it does not pass the depth buffer test.

  8. Render only chunks/pages in the viewport (self explanatory). Even if the gpu knows how to clips polgyons outside of the viewport, passing this data still takes time. I don't know what the most efficient structure for this would be ("shamefully," I have never written a BSP tree), but even a simple raycast on a per chunk basis might improve performance, and obviously testing against the viewing frustum would save time.

  9. Obvious info, but for the newbies: remove every single polygon that is not on the surface -- i.e. if a voxel consists of six faces, remove the faces that never get rendered (are touching another voxel).

  10. As a general rule of everything you do in programming: CACHE LOCALITY! If you can keep things cache-local (even for a small amount of time, it will make an enormous difference. This means keeping your data congruent (in the same memory region), and not switching areas of memory to process too often. So, ideally, work on one chunk per thread, and keep that memory exclusive to the thread. This does not just apply to the CPU cache. Think of the cache hierarchy like this (slowest to fastest): network (cloud/database/etc) -> hard drive (get a SSD if you don't already have one), ram (get tripple channel or greater RAM if you don't already have it), CPU Cache(s), registers. Try to keep your data on the latter end, and not swap it more than you have to.

  11. Threading. Do it. Voxel worlds are well suited for threading, as each part can be calculated (mostly) independently of others...I saw literally a near-4x improvement (on a 4 core, 8 thread Core i7) in procedural world generation when I wrote the routines for threading.

  12. Do not use char/byte data types. Or shorts. Your average consumer will have a modern AMD or Intel processor (as will you, probably). These processors do not have 8 bit registers. They calculate bytes by putting them into a 32 bit slot, then converting them back (maybe) in memory. Your compiler may do all sorts of voodoo, but using a 32 or 64 bit number is going to give you the most predictable (and fastest) results. Likewise, a "bool" value does not take 1 bit; the compiler will often use a full 32 bits for a bool. It may be tempting to do certain types of compression on your data. For example, you could store 8 voxels as a single number (2^8 = 256 combinations) if they were all the same type/color. However, you have to think about the ramifications of this - it might save a good deal of memory, but it can also hinder performance, even with a small decompression time, because even that small amount of extra time scales cubically with the size of your world. Imagine calculating a raycast; for every step of the raycast, you would have to run the decompression algorithm (unless you come up with a smart way of generalizing the calculation for 8 voxels in one ray step).

  13. As Jose Chavez mentions, the flyweight design pattern can be useful. Just as you would use a bitmap to represent a tile in a 2D game, you can build your world out of several 3D tile (or block) types. The downside to this is repetition of textures, but you can ameliorate this by using variance textures that fit together. As a rule of thumb, you want to utilize instancing wherever you can.

  14. Avoid vertex and pixel processing in the shader when outputting the geometry. In a voxel engine you will inevitably have many triangles, so even a simple pixel shader can reduce your render time greatly. Its better to render to a buffer, then do you pixel shader as a post-process. If you can't do that, try to do calculations in your vertex shader. Other calculations should be baked into the vertex data where possible. Additional passes become very expensive if you must re-render all the geometry (such as shadow mapping or environment mapping). Sometimes it is better to give up a dynamic scene in favor of richer details. If your game has modifiable scenes (i.e. destructible terrain) you can always recompute the scene as things are destroyed. The recompilation is not expensive and should take under a second. You can also do things to delay the user and calculate a recomputed environment behind the scenes (i.e. chip away at a block until you are ready to exchange it with new geometry).

  15. Unwind your loops and keep arrays flat! Don't do this:

    for (i = 0; i < chunkLength; i++) {
     for (j = 0; j < chunkLength; j++) {
      for (k = 0; k < chunkLength; k++) {
       MyData[i][j][k] = newVal;
      }
     }
    }
    //Instead, do this:
    for (i = 0; i < chunkLengthCubed; i++) {
     //figure out x, y, z index of chunk using modulus and div operators on i
     //myData should have chunkLengthCubed number of indices, obviously
     myData[i] = newVal;
    }
    

    EDIT: Through more extensive testing, I have found this can be wrong. Use the case that works best for your scenario. Generally, arrays should be flat, but using multi-index loops can often be faster depending on the case

EDIT 2: when using multi-index loops, best to loop int the z, y, x order rather than the other way around. Your compiler might optimize this, but I would be surprised if it did. This maximizes efficiency in memory access and locality.

for (k < 0; k < volumePitch; k++) {
    for (j = 0; j < volumePitch; j++) {
        for (i = 0; i < volumePitch; i++) {
            myIndex = k*volumePitch*volumePitch + j*volumePitch + i;
        }
    }
}
  1. Sometimes you have to make assumptions, generalizations, and sacrifices. The best one you can make is to assume that most of your world is completely static, and only changes every couple thousand frames. For the animated parts of the world, those can be done in a separate pass. Also assume most of your world is completely opaque. Transparent objects can be rendered in a separate pass. Assume that textures only vary every x units, or that objects can only be placed in x increments. Assume a fixed world size...as tempting as an infinite world is, it can lead to unpredictable system requirements. For example, to simplify the voronoi pattern generation in the rocks above, I assumed that every voronoi center point lied in a uniform grid, with a slight offset (in other words, implied geometric hashing). Assume a world that does not wrap (has edges). This can simplify many complexities introduced by a wrapping coordinate system, at minimal cost to user experience.

You can read more about my implementations at my site

\$\endgroup\$
10
  • 9
    \$\begingroup\$ +1. Nice touch including pictures at the top as an incentive to read essay. Now that I've read the essay I can say they weren't needed and it was worth it. ;) \$\endgroup\$ Jun 15, 2012 at 9:00
  • \$\begingroup\$ Thanks -- a picture is worth a thousand words, as they say. :) Aside from making my wall of text less intimidating, I wanted to give readers an idea of how many voxels one could render at a reasonable rate using the described techniques. \$\endgroup\$ Jun 15, 2012 at 10:07
  • 14
    \$\begingroup\$ I still wish SE would allow to favorite specific answers. \$\endgroup\$ Jun 15, 2012 at 10:36
  • 2
    \$\begingroup\$ @PatrickMoriarty #15 is a pretty common trick. Assuming that your compiler does not make this optimization (it may unroll your loop, but it probably will not compact a multidimensional array). You want to keep all your data in the same contiguous memory space, for caching. A multidimensional array can (potentially) be allocated across many spaces, as it is an array of pointers. As for unrolling the loop, think of what the compiled code looks like. In order for the least register and cache swaps, you want to produce the fewest vars/instructions. Which do you think compiles into more? \$\endgroup\$ Jun 21, 2012 at 18:52
  • 3
    \$\begingroup\$ While some of the points here are good, especially with respect to caching, threading, and minimizing GPU transfer, some of it is terribly inaccurate. 5: ALWAYS use VBOs/VAOs instead of display lists. 6: More RAM just needs more bandwidth. With leads to 12: The EXACT opposite is true for modern memory, for which every byte saved increases the chances of fitting more data into cache. 14: In Minecraft, there are more vertices than pixels (all those distant cubes), so move computation TO the pixel shader, not FROM it, preferably with deferred shading. \$\endgroup\$
    – user41442
    Mar 2, 2015 at 18:54
7
\$\begingroup\$

There are a lot of things that Minecraft could be doing more efficiently. For example, Minecraft loads entire vertical pillars of about 16x16 tiles and renders them. I feel that it is very inefficient to send and render that many tiles needlessly. But I don't feel like choice of language is an important one.

Java can be quite fast but for something this data-oriented, C++ does have a large advantage with significantly less overhead for accessing arrays and working within bytes. On the flip side, it is much easier to perform threading across all platforms in Java. Unless you plan to utilize OpenMP or OpenCL, you won't find that convenience in C++.

My ideal system would be a slightly more complex hierarchy.

Tile is a single unit, likely around 4 bytes to keep information such as material type and lighting.

Segment would be a 32x32x32 block of tiles.

  1. Flags would be set for each of the six sides, if that entire side is solid blocks. That would allow the renderer to occlude segments behind that segment. Minecraft currently does not appear to perform occlusion testing. But there was mention of having hardware occlusion culling available which can be costly but better than rendering massive amounts of polygons on low-end cards.
  2. Segments would only be loaded into memory during activity (players, NPCs, water physics, tree growth, etcetera). Otherwise they would be sent directly still compressed from disk to clients.

Sectors would be a 16x16x8 block of segments.

  1. Sectors would track the highest segment for each vertical column so that segments higher than that can quickly be determined empty.
  2. It would also track the bottom occluded segment, so that every segment that needs to be rendered from the surface could be quickly grabbed.
  3. Sectors would also track the next time each segment needs to be updated (water physics, tree growth, etcetera). This way loading in each sector would be enough to keep the world alive and only loading in segments long enough to complete their tasks.
  4. All entity positions would be tracked relative to the Sector. This would prevent the floating-point errors present in Minecraft when travelling very far from the map center.

World would be an infinite map of sectors.

  1. The world would be responsible for managing sectors and their next updates.
  2. The world would preemptively send segments to players along their potential paths. Minecraft reactively sends segments that the client requests, inciting a delay.
\$\endgroup\$
2
  • \$\begingroup\$ I generally like this idea, but how would you, internally, map the sectors of the World? \$\endgroup\$
    – Clashsoft
    Apr 28, 2015 at 13:24
  • \$\begingroup\$ While an array would be the best solution for Tiles in Segment and Segments in Sector, Sectors in World would need something different to allow for an infinite map size. My suggestion would be to use a hash table (pseudo Dictionary<Vector2i, Sector>), using XY coordinates for the hash. Then the World can simply look up a sector at given coordinates. \$\endgroup\$
    – Josh Brown
    Apr 29, 2015 at 15:30
5
\$\begingroup\$

Minecraft is pretty quick, even on my 2-core. Java does not seem to be a limiting factor, here, although there is a bit of server lag. Local games seem to do better, so I'm going to assume some inefficiencies, there.

As to your question, Notch (Minecraft author) has blogged at some length about the technology. In particular, the world is stored in "chunks" (you sometimes see these, especially when one is missing as the world hasn't filled in, yet.), so the first optimization is to decide if a chunk can be seen or not.

Within a chunk, as you have guessed, the app has to decide if a block can be seen or not, based on whether or not is is obscured by other blocks.

Note, too, that there are block FACES, which can be assumed not-seen, by virtue of either being obscured (i.e., another block covers the face) or by which direction the camera is pointing (if the camera faces North, you can't see the North face of ANY blocks!)

Common techniques would also include not keeping separate block objects but, rather, a "chunk" of block types, with a single prototype block for each one, along with some minimal set of data to describe how this block may be custom. For example, there aren't any custom granite blocks (that I know), but water has data to tell how deep it is along each side-face, from which one can calculate its direction of flow.

Your question isn't clear if you're looking to optimize render speed, data size or what. Clarification there would be helpful.

\$\endgroup\$
3
  • 4
    \$\begingroup\$ "clumps" are usually named chunks. \$\endgroup\$
    – Marco
    Jun 14, 2012 at 18:22
  • \$\begingroup\$ Good catch (+1); answer updated. (Was doing for memory originally, and forgot the right word.) \$\endgroup\$
    – Olie
    Jun 14, 2012 at 21:47
  • \$\begingroup\$ The inefficiencies you refer to is also known as "the network", which never quite acts the same way twice, even with the same end points communicating. \$\endgroup\$
    – Edwin Buck
    Jun 21, 2012 at 18:16
4
\$\begingroup\$

Here's just a few words of general info and advice, which I can give as an, um, overly experienced Minecraft modder (which may at least partly give you some guidance.)

The reason Minecraft is slow has a LOT to do with some questionable, low-level design decisions-- for example, every time a block is referenced by positioning, the game validates the coordinates with about 7 if statements to ensure it's not out of bounds. Furthermore, there's no way to grab a 'chunk' (a 16x16x256 unit of blocks the game works with) then reference blocks in it directly, in order to bypass cache lookups and, erm, silly validation issues (iow, each block reference also involves a chunk lookup, among other things.) In my mod, I created a way to grab and change the array of blocks directly, which boosted massive dungeon generation from unplayably laggy to unnoticeably fast.

EDIT: Removed claim that declaring variables at a different scope resulted in performance gains, this doesn't actually appear to be the case. I believe at the time that I conflated this result with something else I was experimenting with (specifically, removing casts between doubles and floats in explosion related code by consolidating to doubles... understandably, this had a huge impact!)

Also, though it's not the area I spend a lot of time in, most of the performance choke in Minecraft is an issue with the rendering (about 75% of game time is dedicated to it on my system). Obviously you don't care so much if the concern is supporting more players in multiplayer (server doesn't render anything), but it matters to the extent of everyone's machines being able to even play.

So whatever language you choose, try to get very intimate with the implementation/low level details, because even one little detail in a project such as this could make all the difference (one example for me in C++ was "Can the compiler statically inline function pointers?" Yes it can! Made an incredible difference in one of the projects I was working on, since I had less code and the advantage of inlining.)

I really dislike that answer because it makes high-level design difficult, but it's the painful truth if performance is a concern. Hope you found this helpful!

Also, Gavin's answer covers some details I didn't want to reiterate (and much more! He's clearly more knowledgeable on the subject than I am), and I agree with him for the most part. I'll have to experiment with his comment regarding processors and shorter variable sizes, I've never heard of that-- I'd like to prove to myself that it's true!

\$\endgroup\$
2
\$\begingroup\$

The thing is to think about how you would first of all load the data. If you stream your map data into memory when needed, there is abivously a natural limit to what you can render, this is already a rendering performance upgrade.

What you do with this data is then up to you. For GFX performance, you can then use Clipping to clip hidden objects, objects that are too small to be visible, etc.

If you are then just looking for Graphics Performance techniques I'm sure you can find mountains of stuff on the net.

\$\endgroup\$
1
\$\begingroup\$

Something to look at is the Flyweight design pattern. I believe most of the answers here reference this design pattern in one way or another.

While I don't know the exact method Minecraft is using to minimize memory for each block type, this is a possible avenue to use in your game. The idea is to have only one object, like a prototype object, that holds information about all the blocks. The only difference would be the location of each block.

But even location can be minimized: if you know a block of land is of one type, why not store the dimensions of that land as one giant block, with one set of location data?

Obviously the only way to know is to start implementing your own, and do some memory tests for performance. Let us know how it goes!

\$\endgroup\$

You must log in to answer this question.

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