Hey guys, I have developed an interest in 3d "pixel" games such as

">Minecraft, Infiniminer, Fez, and

">3D dot game hero's. For the lazy, here is a screenshot of Minecraft (great game btw): Lets say I wanted to create a world similar to the one above. If the world is 256x256x128 (length x height x height) cubes/voxels that means I have 8,388,608 cubes to worry about. Clearly I wont be able to get away with drawing all of the cubes/voxels even with instancing. Frustum culling will help a lot but even then I need to reduce the draw calls far more. Occlusion culling could be fairly expensive too if i don't use an octree like structure. How should I go about storing and drawing the world? If you guys have any advice or know of material I could read up on please let me know. Also, if anyone knows how Minecraft does it I would love to hear from you. Thanks! [Edited by - arriu on April 27, 2010 10:48:25 AM]

You don't have to render all the cubes in the map. In fact, the majority of the cubes will represent "air". It shouldn't also be too difficult to create and update a mesh which represent the boundary of your objects.

Thanks for the reply,

In the screenshot that I posted above only the "tip of the iceberg" is visible. You can drill your way far below the sea-level. But lets say only 30% of the map is covered at any time, that is still a lot (about 3 million on a 256x256x128 map).

Also, creating a single mesh wont work. As you can see many of the voxels are transparent (trees and water).

Quote:Original post by Rubicon
Right off the cuff, I'd consider scan converting this in a shader.

If you have a load of textures for each height slice, you could do it all without any geometry at all. The texure load could be manageable as you can pile a lot of them into a texture atlas as being world maps they're not meant to be tileable.

So you're suggestion is to store every cube in a large texture atlas and then generate all of the geometry with vertex texture fetch in the vertex shader? A texture of (256x128)x(256x128) would be huge. How do I add new blocks or remove them? Reading back a texture of that size is way too expensive. I would have to draw onto the texture... Seems like it might work but I am not sure that this is a good idea if I am planning to run this on an Xbox 360. Let me know if I understood correctly.

Also, I had a look through the developer blog for Minecraft and found this:

Quote:
* Cull backfaces. This is done per-chunk, so it has to be very forgiving, but it cuts out about 40% of all terrain quads. It works by dividing each chunk into six display lists, one per face, and only rendering the lists that are facing the player.

Does this mean that he stores the cubes in chunks and then has 6 lists for each chunk? Then when he needs to draw the scene, he draws everything as billboards?

Quote:
* Join adjacent strips of the same texture. If there's a rock next to a rock, why render two quads? Well, because I use a texture atlas, that's why. But by turning the atlas from a 16x16 grid to a 1x256 grid, I can repeat along u to make strips of the same texture. On a newly generated map, the average strip length is just over 2 tiles, so this cuts out 50% of all quads.

I cannot figure out how the game has time to look for adjacent quads?!

While your world may be defined by voxels, you don't actually need to think in voxels when doing the rendering. Looking at the minecraft image you provided, if you didn't know that it was made up of cubes, you'd think it was the easiest thing in the world to draw. There's really not that much geometry there once you collapse all the cubes into flat tiled faces, as Rubicon says.

For example, think of a 10x4x20 hill in the map. This object is completely filled, with grass cubes on top and the rest as dirt. How many faces do you really need to render this? The naive solution is just to render it as cubes, which yields 10x4x20x12=4800 faces. A better optimization is only to render the cubes on the outside of the hill, since the ones on the inside are completely obstructed anyways. But even better is to think in terms of outside faces only. If your textures tile, you can render this entire hill in only 12 faces. TWELVE. You just need to write a function that goes through your voxel map, determines which cube faces are actually visible to the player, and then collapses them into larger faces. You can then keep the voxel map around for physics and player collisions and such, but use the collapsed face lists for doing the actual rendering. It would fly.

And if you're worried about not being able to atlas your textures since they need to repeat, don't be. So long as you make sure to concatenate all faces of a given material into a single draw call, any performance hit from the extra texture state changes will probably be dwarfed by the savings in geometry memory and pixel overdraw.

Thanks guys! I can't believe I didn't think of it as meshes sooner =)

Also, I just pushed the camera through a wall in Minecraft and took these screen shots (they support your proposed solution):

I worked on it a bit last night and here is what I have:



I still need to come up with a fast way to reduce the number of quads. At the moment I am only merging in one direction.