Culling techniques for rendering lots of cubes

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);
                    }
                }

            }
        }

}

c++ c algorithm rendering

Edit Report

Only keep track of the cubes describing your surface. You can do this by a simple data-structure where each cube keeps references to it's neighbors. On any modern graphic card it shouldn't be a problem to push all those triangles. Render from back to front. Also only render cubes closer then a specific distance to the viewer. The "world" could start with a huge "cube-of-cubes", the outer shells of a cube, made by cubes. If someone digs down, you have the check if the neighbor locations already contains cubes or not, if not you create those cubes and link them in.

Example: Digging down one flat surface: Remove cube that's positioned where the digging is done, add 9 new cubes underneath (But check if those positions are already in use, in case use those), link together the surface but linking the new cubes to the neighbor cubes of the one removed.

So: For a world containing 1000x1000x1000 cubes you would get: 1000*1000*2+998*999*4 = 5988008 instead of 1000*1000*1000 = 1000000000, or a factor 167 less number of cubes.

Of course you shouldn't draw all those cubes, start with simple distance to viewer to do a sub select.

You could also go into grouping 8 cubes(groups) together as 1 group, and then continue like that until on the top level you have just one cube-group (oct-tree already mentioned). This tree can be used to ray-trace what part of the world you need to draw and not draw. If a group contains references to 8 other cubes-groups, those behind is not shown. With behind in this would be those cube-groups that does not intersect or lay outside of a ray-traced cone starting from the user and passes just by the edge of the group used for testing. (Bad description, but I hope you would get some hints anyhow on what could be done for optimization). This would likely not be needed on todays graphics cards anyhow.

Good luck with your project.

answered 2010-10-18T13:01:26.253

Culling techniques for rendering lots of cubes

1 Answer

Your Answer