//==============================================================================
//  Octree.h
//  Author: Kurt Miller
//
//  Copyright (C) 2003 Gradient Studios, Inc.  All Rights Reserved.
//==============================================================================
//
//  This class is a simple octree implementation.  Its presented for
//  illustrative purposes, but feel free to use or modify it however you'd like.
//
//==============================================================================

class Octree
{
public:

//==============================================================================
//  Octree::Octree()
//==============================================================================

    Octree()
    {
        for(int i=0; i<8; i++)
        {
            m_children[i] = NULL;
        }
    }

//==============================================================================
//  Octree::~Octree()
//==============================================================================

   ~Octree()
    {
        release();
    }

//==============================================================================
//  Octree::build()
//==============================================================================

    bool build(const std::vector<TriangleData> &tripool, 
               const BoundingBox &nodesize, int maxTriCount)
    {
        // set the node's bounding box;

        m_node = nodesize;

        int tricount = (int)tripool.size();

        // if there are fewer triangles than the threshold value,
        // this node becomes a leaf which stores the triangles;

        if(tricount < maxTriCount)
        {
            for(int i=0; i<tricount; i++)
            {
                m_triangles.push_back(tripool[i]);
            }

            return true;
        }

        // create the child cubes;

        BoundingBox childnodes[8];

        createChildCubes(childnodes);

        std::vector<TriangleData> childtris[8];

        // for each child, generate a list of triangles that
        // intersect the child cube;

        for(int i=0; i<tricount; i++)
        {
            for(int j=0; j<8; j++)
            {
                if(childnodes[j].doesTriangleIntersect(tripool[i]))
                {
                    childtris[j].push_back(tripool[i]);
                }
            }
        }

        // for any children with intersecting triangles, create and
        // recursively build the node;

        for(int i=0; i<8; i++)
        {
            if(childtris[i].size())
            {
                m_children[i] = new(Octree);

                if(m_children[i] == NULL)
                {
                    return false;
                }

                if(!m_children[i]->build(childtris[i], childnodes[i]))
                {
                    return false;
                }
            }
        }

        return true;
    }

//==============================================================================
//  Octree::buildCollisionList()
//==============================================================================

    bool buildCollisionList(std::vector<Triangle*> &tlist, const Sphere &ps)
    {
        // if the bounding sphere does not intersect this node,
        // we can disregard it and all of its children;

        if(!ps.doesBoundingBoxIntersect(m_node))
        {
            return true;
        }

        // if this node is a leaf node with triangles, add the children
        // to the potential collision list;  otherwise recursively check;

        if(m_triangles.size())
        {
            int tsize = (int)m_triangles.size();

            for(int i=0; i<tsize; i++)
            {
                tlist.push_back(m_triangles[i].src());
            }
        }
        else
        {
            for(int i=0; i<8; i++)
            {
                if(m_children[i] != NULL)
                {
                    m_children[i]->buildCollisionList(tlist, ps);
                }
            }
        }

        return true;
    }

//==============================================================================
//  Octree::render()
//==============================================================================

    void render()
    {
        for(int i=0; i<8; i++)
        {
            if(m_children[i] != NULL)
            {
                m_children[i]->render();
            }
        }

        // render only leaf nodes with triangles;

        if(m_triangles.size())
        {
            renderBoundingBox(m_node, COLOR_RGB(255, 255, 255));
        }
    }

//==============================================================================
//  Octree::release()
//==============================================================================

    void release()
    {
        for(int i=0; i<8; i++)
        {
            if(m_children[i] != NULL)
            {
                m_children[i]->release();

                delete(m_children[i]);
                m_children[i] = NULL;
            }
        }

        m_triangles.clear();
    }

private:

//==============================================================================
//  Octree::createChildCubes()
//==============================================================================

    void createChildCubes(BoundingBox *nodes)
    {
        Vector3D center = m_node.calcCenter();

        // top left, near;
        nodes[0].bmin().set(m_node.bmin().x(), center.y(), m_node.bmin().z());
        nodes[0].bmax().set(center.x(), m_node.bmax().y(), center.z());

        // top right, near;
        nodes[1].bmin().set(center.x(), center.y(), m_node.bmin().z());
        nodes[1].bmax().set(m_node.bmax().x(), m_node.bmax().y(), center.z());

        // bottom left, near;
        nodes[2].bmin().set(m_node.bmin().x(), m_node.bmin().y(), m_node.bmin().z());
        nodes[2].bmax().set(center.x(), center.y(), center.z());

        // bottom right, near;
        nodes[3].bmin().set(center.x(), m_node.bmin().y(), m_node.bmin().z());
        nodes[3].bmax().set(m_node.bmax().x(), center.y(), center.z());

        // top left, far;
        nodes[4].bmin().set(m_node.bmin().x(), center.y(), center.z());
        nodes[4].bmax().set(center.x(), m_node.bmax().y(), m_node.bmax().z());

        // top right, far;
        nodes[5].bmin().set(center.x(), center.y(), center.z());
        nodes[5].bmax().set(m_node.bmax().x(), m_node.bmax().y(), m_node.bmax().z());

        // bottom left, far;
        nodes[6].bmin().set(m_node.bmin().x(), m_node.bmin().y(), center.z());
        nodes[6].bmax().set(center.x(), center.y(), m_node.bmax().z());

        // bottom right, far;
        nodes[7].bmin().set(center.x(), m_node.bmin().y(), center.z());
        nodes[7].bmax().set(m_node.bmax().x(), center.y(), m_node.bmax().z());
    }


//==============================================================================
//  private member data;
//==============================================================================

    BoundingBox  m_node;
    Octree      *m_children[8];

    std::vector<TriangleData> m_triangles;
};

//==============================--end-of-file--=================================