I want to render a cube-mesh (a.k.a. Minecraft-style) world. If I render each existing cube it will eat up FPS pretty quickly. How can I optimize it? I understand that the point is to not render invisible meshes (faces?) but my problem is to find out what is invisible and what isn't.
3 Answers
You'll have good use of a isSolidAt(x,y,z)
function. This will be useful for not only the action you want to preform, but other things such as collision checking.
Basically you want to iterate through your cubes and check which faces will be hidden. You know they're hidden when the adjacent cube is solid. For example some pseudo code:
Verticies[] verticesToDraw
for(x = 0 to x = chunkXMax)
for(y = 0 to y = chunkYMax)
for(z = 0 to z = chunkZMax)
if(!isSolidAt(x+1,y,z))
verticesToDraw += AddXPlusFace(x,y,z)
if(!isSolidAt(x-1,y,z))
verticesToDraw += AddXMinusFace(x,y,z)
if(!isSolidAt(x,y+1,z))
verticesToDraw += AddYPlusFace(x,y,z)
//and so on for the rest of the faces
Buffer(verticesToDraw)
Of course you'll be more detailed. You can also keep track of the faces in a separate array, perhaps using a byte with bit positions 0 through 5 indicating whether a face is set or not.
Eventually you'll probably want to improve upon this with special checks for "short cubes", transparent but solid cubes and so on.
EDIT
I've updated the code to show that you run this on a per chunk basis. This only address the issue of faces that are invisible because they are adjacent to a solid cube. Sending the vertices for all the cubes and "letting the GPU do the culling" would be a bad idea. I assume you may know that already since you asked this question. The above code is only run when the chunk is dirty, as in, something has changed. It's not to be run every frame.
You'll see significant performance improvements with the above change. I know because I've gone through the process before. You may also find performance improvements with spacial partitioning, but the improvements are unlikely to be as significant as drastically reducing the number of vertices sent to the GPU (as you will do when you implement the above).
-
\$\begingroup\$ (x+1, y, z), (x-1, y, z), (x, y+1, z), (x, y-1, z), (x, y, z+1), (x, y, z-1). The six faces you'll need btw :) \$\endgroup\$ May 3, 2012 at 20:15
-
\$\begingroup\$ Thanks Gustavo, I figured the point was made with the pattern I displayed, but you've got all the bases covered now. \$\endgroup\$– HouseMay 3, 2012 at 20:24
-
\$\begingroup\$ This is really quite bad. It's O(N) in the size of the whole world. That will take forever to run- it would be faster to submit the lot to the GPU and let it do the cullin. \$\endgroup\$– DeadMGMay 3, 2012 at 20:43
-
\$\begingroup\$ This is just an example and it only addresses faces that are invisible because they are "face to face", not faces that are hidden from view because of non-adjacent geometry. Clearly you'd want to use the above on the selected chunks you want to update. Sending all the vertices for all the cubes in the world would be far worse than only adding the vertices for the faces that are visible. \$\endgroup\$– HouseMay 3, 2012 at 20:53
-
\$\begingroup\$ @DeadMG This is executed only once. Not on the game loop. You execute it to generate the mesh from the cube data and done. you just generate it again if you need to update some area, this can be easily done with chunking. \$\endgroup\$ May 3, 2012 at 20:53
There are two problems to this:
- Eliminate entire cubes to avoid rendering them.
- Eliminate invisible faces
As for #1, you need to take a look at space partitioning algorithms. They divide up space into smaller subspaces in order to make searches faster (in your case, you're searching for every cube that collides with your view frustum).
Since most things you have are static, and also cubes, an easy suggestion for you would be the Octree.
As for #2: I'm pretty sure that's not going to be a problem. Not drawing faces that you can't see with cubes usually equals not drawing faces that don't face towards you. The process of this is called backface culling and is usually done by the graphics card.
So the only really limiting factor for #2 could be bandwidth consumption on the way to your graphics card. But I really doubt that's the case, since your world is static and thus only needs to be sent to the graphics card whenever something in the terrain changes, which will not be very often. Even if you sent everything you need to draw over once every frame, this will most likely be no bottleneck as long as you batch everything together in a reasonable manner (faces with same textures, etc). However, if this really turns out to be a bottleneck, you should search the internet for software backface culling algorithms. Here's an example.
A simple octree should be a fine enough algorithm for this- it can achieve this in O(log(N)). In addition, you have an advantage in that you can prove which cubes are visible and which aren't in easy time.
Let's say that you start off with a totally flat map. You know in advance that only the top level of cubes are visible, since all the ones below it are concealed. Then when the player removes a cube, you know in advance which cubes are now visible. When the player adds a cube, it's easy to test if the cubes near it have been blocked from view. This is because each cube can only affect the potential visibility of the six cubes on it's primary faces. Thus, it's trivial to exploit the temporal coherency of the map to prove which cubes are visible and which aren't in a very short period of time. If you use terrain generation or static maps, then simply apply this logic when your algorithms apply each change.
This will easily provide you with a small count of visible cubes, and frustum culling with an octree should do the rest.
Backface culling on the GPU is more than sufficient for eliminating invisible faces.
-
\$\begingroup\$ try sending 256x256x256 cubes to the GPU and see if it is fine. It's 16.777.216 cubes, on the worst case you get 12 bytes per vertice and 4 vertices per quad, 48 bytes per quad. 6 faces per cube, 48 * 6 = 288 bytes per cube. Now let's see: 4,5GB, Do you have this GPU RAM free at your home? \$\endgroup\$ May 3, 2012 at 20:56
-
\$\begingroup\$ @Gustavo: It's not going to be anywhere near that once you apply frustum culling and the visibility opts I described. At most, you're talking about 256*256- if the player can view the whole world at once, in which case consider LOD optimizations. It'll almost certainly be much, much less. \$\endgroup\$– DeadMGMay 4, 2012 at 17:59
-
\$\begingroup\$ Well, so why dont you generate a mesh with just the visible faces as Byte56 mentioned then you apply these LOD techniques? it seems crazyness apply all this in a huge amount of cubes. \$\endgroup\$ May 4, 2012 at 18:04