BSP Tree - Code Sample

/*
Recursively searches though the BSP tree and lists all contained objects within the specified volume.
Returns the number of objects found.
If out is not null, out will be a full list of all found objects.
volume is the volume in which all found objects must occur.
eyePos is the position of the camera, used for occluders.
*/
template< class Type >
int BSPTree<Type>::Division::Search(std::list<const Division*>* out, const Frustum& volume, const Vector& eyePos) const
{
    //Is this a division or a content?
    if (plane != 0)
    {
        bool checkGreater, checkLesser;
        int found = 0;
        
        //Does this block the view (occluder)
        if (!blocksView)
        {
            //Determine the relationship between the volume and this plane
            Frustum::Direction t = volume.isInside(*plane);
            
            //The plane divides the volume, check both
            if (t == Frustum::DIR_Inside)
            {
                checkGreater = true;
                checkLesser = true;
            }
            //The plane is on one side of the volume...check only that side
            else if (t == Frustum::DIR_Behind)
            {
                checkGreater = false;
                checkLesser = true;
            }
            else if (t == Frustum::DIR_Front)
            {
                checkGreater = true;
                checkLesser = false;
            }
        }
        else
        {
            //Determine the relationship between the plane and this camera position
            Plane::Direction t = plane->pointInFront(eyePos);
            
            //The eye is on the plane
            if (t == Plane::DIR_Equal)
            {
                checkGreater = true;
                checkLesser = true;
            }
            
            //The eye is on one side of the volume...check only that side
            else if (t == Plane::DIR_Behind)
            {
                checkGreater = false;
                checkLesser = true;
            }
            else if (t == Plane::DIR_Front)
            {
                checkGreater = true;
                checkLesser = false;
            }
        }
        
        //Recursively check the greater side
        if (checkGreater)
            if (Greater != 0)
                found += Greater->Search(out, volume, eyePos);
        
        //Recursively check the lesser side
        if (checkLesser)
            if (Lesser != 0)
                found += Lesser->Search(out, volume, eyePos);
        
        return found;
    }
    //This division contains a single object
    else if (borders != 0)
    {
        //Check to see if the object is at least partially inside the volume
        if (volume.isInside(*borders, location, scale))
        {
            //The object
            out->push_back(this);
            return 1;
        }
    }
    
    //This division is empty or the contained object is not inside the volume
    return 0;
}