procedural generation - How can I optimise a Minecraft-esque voxel world?

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?