Block Land 2
From DaveWiki
Last Time we tried to render a basic 256x256x256 block world using the simplest possible method and failed wonderfully. In this article we'll explore a few ways we can get usable performance at this size of block world.
Contents |
Simple Approach Critique
Our first attempt was without doubt about the simplest way we can display our block world with Ogre3D. While it worked in theory it has performance issues that make it unusable except for very small world sizes. The main problem is that adding and displaying all blocks through Ogre3D is extremely wasteful. Lets look at a few stats from the world sample that worked:
- World Size = 256x256x10 blocks
- Number of Blocks = 655,360
- Vertexes = 5,242,880
- Triangles = 7,864,320
- Actual Triangles Visible = 141,312 (from example screen shot last time)
- Percent of Triangles Hidden = 98.2%
So for all the work the GPU does, 98% of it is wasted because the triangle is completely hidden by other triangles (or blocks by other blocks). In a real block world there will be many empty blocks that might reduce this inefficiency but for the most part it will remain pretty high.
It is also important to note that this is for a "thin" 10 pixel high world. If we actually managed to display a 256x256x256 world using this technique our actually inefficiency would be 99.998% (100 - 393216/201326592)! In other words, it would be hard to pick a worse method to display our block world in (it's always nice to be good at something I suppose).
Shader/Texture Approach
Doing a search on the Ogre3D forums we find a wonderfully helpful post right up our alley: Rendering many small objects - voxel-like world. The approach used by Kojack in that thread is well beyond my very beginner knowledge of Ogre3D and GPU shaders but seems like it would be the most performant. Rather than actual create cubes in the 3D world for each block there are large planes which are textured using a custom shader that makes it look like the world is made of blocks. Hopefully he will eventually post his source code so I can get a better idea exactly what is involved.
One drawback, if I understand the basic theory, is that this technique requires the world to be made of cubes (but maybe not, I'm just guessing). If we wish to use non-cubes at any point we'll have to look at other options.
Voxel/Block Mesh Combination
The other technique that is mentioned in that forum thread by LBDude is a voxel approach. The details of voxels are similarly complex but if I understand one basic concept is that instead of rendering each individual block in the voxel we combine the blocks into much larger meshes to reduce the inefficiency of displaying a large number of hidden blocks. So, for example, a 512x512x512 voxel model with millions of individual elements might be actually displayed using meshes created by combining 64x64x64 blocks for a total of 512 meshes for the entire model. There are still some inefficiencies with the resulting meshes but much less than what we've seen by trying to display each block individually.
This topic on GameDev.net is a good example of "chunking and merging" of individual blocks into larger meshes. As a simple example let's consider a very small 10x10x10 block sized world with no empty spaces (i.e., completely filled with blocks). If we displayed the individual blocks we would have 1000 blocks or 12,000 triangles to manage which, as shown previously, is terribly wasteful. Instead, let us combine all 1000 blocks into one single mesh. Since the block world is completely filled the resulting mesh will only have its 6 sides showing with each side showing the outer face of 100 blocks resulting in a total of 1,200 triangles. At this scale we've just improved our efficiency by a factor of 10, going from 12,000 to 1,200 triangles by combining the blocks into a single mesh. Now, in practice the block world (or part of the world) will not be completely filled so this will reduce the improvement gain some.
We can also play around with the "chunk" size, the number of blocks we combine into a mesh, and see what that does to our potential efficiency gain:
- 10x10x10 = x10 (12000/1200)
- 16x16x16 = x16 (49152/3072)
- 32x32x32 = x32 (393216/12288)
- 64x64x64 = x64 (3145728/49152)
It is obvious that as our chunk size increases our potential improvement goes right up with it. So, if we took our original 256x256x256 world full of blocks and chunked it into 64x64x64 meshes we would have 64 times fewer triangles to deal with (2 billion to 3 million). Combine that with some other optimizations and our 256x256x256 block world just might be viable.
Chunking
As we discussed in the previous section, "chunking" is the concept of breaking up the world into smaller sections that have all the blocks in them combined into a single mesh. Just this process alone can result in tremendous performance gains depending on the size of the chunk but there are other benefits as well. If we are dealing with a very large and nearly infinite potential world volume we already have to think in chunks as we can't possibly generate everything. All we need to generate and save, in fact, are the areas that the player has visited and of that we only need to display the area immediately surrounding the player's current position. By breaking up the world generation and display into chunks we have a convenient small volume of the overall world to deal with as we need to.
There is also a potential performance optimization by considering chunks that are completely hidden from the player. For example, if you are walking on top of a flat, undisturbed, plain then all the chunks underneath you will be completely hidden. If we can somehow use this we might be able to see another large increase in efficiency (I don't know exactly how or even if this would be useable but it is something to explore later on).
Next Time
NextTime we'll use our new found knowledge of "chunking" to actually try and combine blocks into a single mesh.
