Z ordering geometry

Question

I'm making a game that is entirely made of cubes. I notice that when I walk forward it runs lightening fast, but if I rotate the player in the opposite direction, its cripplingly slow. So what I did is ordered based on angle, but I still get some angles that are a bit slow. Here is how I did it:

I basically reverse iterate in certain angles, but how could I make it consistent, so that every angle is lightening fast, some of the straight angles like 88-92, or 178-182 are really slow (overdraw).

Thanks

SetPlayerPosition();


PlayerPosition.x -= 70;

PlayerPosition.y -= 20;

PlayerPosition.z -= 70;


collids.clear();
CBox* tmp;
float offset = -10;
if( Wrap(Camera.roty + offset) > 180 && Wrap(Camera.roty + offset) < 270)
{
    for(int i = 140; i > 0; --i)
    {
        for(int j = 0; j < 40; ++j)
        {
            for(int k = 0; k < 140; ++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);
                    }
                }

            }
        }
    }
}
else if(Wrap(Camera.roty + offset) > 0 && Wrap(Camera.roty + offset) < 90 )
{
    for(int i = 0; i < 140; ++i)
    {
        for(int j = 0; j < 40; ++j)
        {
            for(int k = 140; 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);
                    }
                }

            }
        }
    }
}

else if(Wrap(Camera.roty + offset) > 90 && Wrap(Camera.roty + offset) < 180 )
{
    for(int i = 0; i < 140; ++i)
    {
        for(int j = 0; j < 40; ++j)
        {
            for(int k = 0; k < 140; ++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);
                    }
                }

            }
        }
    }
}
else if (Wrap(Camera.roty + offset) > 270 && Wrap(Camera.roty + offset) < 360)
{
    for(int i = 140; i > 0; --i)
    {
        for(int j = 0; j < 40; ++j)
        {
            for(int k = 140; 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

Yikes.

Without knowing what GetCube is doing, I can't begin to guess how it's affecting your performance, but it's pretty clear why things are slowing down so significantly. You're doing a lot of unnecessary work.

You can eliminate most of your loops simply by taking a different approach: Ignore the angle, and do more simplified tests. For any value of i, j, and k, do nothing if it marks a cube behind the "player." That alone will even out your framerate and simplify your loops. (You don't need four different sets of nested loops!)

Even better, use a spatial graph - something like an octree or kd-tree - to store instances of your cubes (or other objects), and do your intersection tests on nodes of the tree. That way, you can eliminate huge swaths of objects all at once that will never be inside the frustum, and improve performance significantly.