c++ - Culling techniques for rendering lots of cubes

Question

I am working on a personal learning project to make a Minecraft clone. It is working very well aside from one thing. Similar to Minecraft, my terrain has lots of cubes stacked on the Y so you can dig down. Although I do frustum culling, this still means that I uselessly draw all the layers of cubes below me. The cubes are X, Y and Z ordered (although only in 1 direction, so its not technically Z ordered to the camera). I basically from the player's position only add pointers to cubes around the player. I then do frustum culling against these. I do not do oct tree subdivision. I thought of simply not rendering the layers below the player, except this does not work if the player looks down into a hole. Given this, how could I avoid rendering cubes below me that I cannot see, or also cubes that are hidden by other cubes.

Thanks

void CCubeGame::SetPlayerPosition()
{
PlayerPosition.x = Camera.x / 3;
PlayerPosition.y = ((Camera.y - 2.9) / 3) - 1;
PlayerPosition.z = Camera.z / 3;
}

void CCubeGame::SetCollids()
{

SetPlayerPosition();

int xamount = 70;
int zamount = 70;
int yamount = 17;

int xamountd = xamount * 2;
int zamountd = zamount * 2;
int yamountd = yamount * 2;
PlayerPosition.x -= xamount;

PlayerPosition.y -= yamount;

PlayerPosition.z -= zamount;


collids.clear();
CBox* tmp;

    for(int i = 0; i < xamountd; ++i)
    {
        for(int j = yamountd; j > 0; --j)
        {
            for(int k = zamountd; k > 0; --k)
            {

                tmp = GetCube(PlayerPosition.x + i, PlayerPosition.y + j, PlayerPosition.z + k);



                if(tmp != 0)
                {
                    if(frustum.sphereInFrustum(tmp->center,25) != NULL)
                    {
                        collids.push_back(tmp);
                    }
                }

            }
        }

}

Answer 1

Here is what I've learned while writing my own clone:

1. Don't just dump every cube into OpenGL, but also don't worry about doing all of the visibility pruning yourself. As another answer stated, check all 6 faces to see if they are fully occluded by an adjacent block. Only render faces that could be visible. This roughly reduces your face count from a cubic term (a volume of cubes n*n*n) to a squared term (surface of only about n*n).
2. OpenGL can do view frustrum culling much faster than you can. Once you have rendered all of your surface faces into a display list or VBO, just send the entire blob to OpenGL. If you break your geometry into slices (or what Minecraft calls chunks) you might avoid drawing the chunks you can easily determine are behind the camera.
3. Render your entire geometry into a display list (or lists) and redraw that each time. This is an easy step to take if you're using immediate mode because you just wrap your existing code in glNewList/glEndList and redraw with glCallList. Reducing the OpenGL call count (per frame) will have a vastly bigger impact than reducing the total volume of polygons to render.
4. Once you see how much longer it takes to generate the display lists than to draw them, you'll start thinking about how to put the updates into a thread. This is where conversion to VBOs pays off: The thread renders into plain old arrays (adding 3 floats to an array instead of calling glVertex3f, for example) and then the GL thread only has to load those into the card with glBufferSubData. You win twice: The code can run in a thread, and it can "draw" a point with 3 array writes instead of 3 function calls.

Other things I've noticed:

VBOs and display lists have very similar performance. It's quite possible that a given OpenGL implementation uses a VBO internally to store a display list. I skipped right by vertex arrays (a sort of client-side VBO) so I'm not sure about those. Use the ARB extension version of VBOs instead of the GL 1.5 standard because the Intel drivers only implement the extension (despite claiming to support 1.5) and the nvidia and ATI drivers don't care.

Texture atlases rule. If you are using one texture per face, look at how atlases work.

If you want to see my code, find me on github.