#include "cOctree.h"

cOctree::cOctree()
{
    minBoxWidth = 3;
    for(int i = 0; i < 8; ++i)
        children_[i] = NULL;
}

cOctree::~cOctree()
{
    for(int i = 0; i < 8; ++i)
    {
        if(children_[i] != NULL)
        {
            delete(children_[i]);
            children_[i] = NULL;
        }
    }
    triangles_.clear();
}

bool cOctree::build(const vector<cTriangle*>& tripool, const cBoundingBox& box)
{
    box_ = box;
    int numTriangles = tripool.size();
    
    // if there are fewer triangles than the threshold value,
    // this node becomes a leaf which stores the triangles
    if(numTriangles < maxTrianglePerNode || (box.xmax_ - box.xmin_) < minBoxWidth)
    {
        for(int i = 0; i < numTriangles; ++i)
            triangles_.push_back(tripool[i]);
            
        return true;
    }
    
    // create the child boxes
    cBoundingBox childBoxes[8];
    createChildBoxes(childBoxes);
    
    // for each child, generate a list of triangles intersecting it
    vector<cTriangle*> childTriangles[8];
    for(int i = 0; i < numTriangles; ++i)
    {
        for(int j = 0; j < 8; ++j)
        {
            if(childBoxes[j].triangleIntersects(*tripool[i]))
                childTriangles[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(childTriangles[i].size()) // if size != 0
        {
            children_[i] = new cOctree();

            if(children_[i] == NULL) 
                return false;
            
            if(!children_[i]->build(childTriangles[i], childBoxes[i]))
                return false;
        }
    }

    return true;
}

bool cOctree::buildCollisionList(vector<cTriangle*>& tlist, cBoundingBox& box)
{
    // if the bounding sphere does not intersect this node,
    // we can disregard it and all of its children
    if(!box_.boxIntersectsMe(box) )
        return true;
        
    // if this node is a leaf node with triangles, add the children
    // to the potential collision list.  otherwise recursively check.

    if(triangles_.size()) // if size != 0
    {
        int tsize = (int)triangles_.size();
        //cout << "reached a leaf " << tsize << endl;
        for(int i = 0; i < tsize; ++i)
        {
            if( !triangles_[i]->hasBeenAddedToCollisionList_)
            {
                tlist.push_back(triangles_[i]);
                triangles_[i]->hasBeenAddedToCollisionList_ = true;
            }
        }
    }    
    else
    {
        for(int i = 0; i < 8; ++i)
        {
            if(children_[i] != NULL)
            {	
                //children_[i]->buildCollisionList(tlist, sphereStart, sphereEnd, radius);
                children_[i]->buildCollisionList(tlist, box);
            }
        }
    }
    
    return true;
}

void cOctree::createChildBoxes(cBoundingBox* boxes)
{
    float 	xmin = box_.xmin_, xmax = box_.xmax_,
                ymin = box_.ymin_, ymax = box_.ymax_, 
                zmin = box_.zmin_, zmax = box_.zmax_;
        
    float halfXWidth = (xmax - xmin)/2.0;
    float halfYWidth = (ymax - ymin)/2.0;
    float halfZWidth = (zmax - zmin)/2.0;
    
    boxes[0] = cBoundingBox(xmin, xmin + halfXWidth, 
                            ymin, ymin + halfYWidth,
                            zmin, zmin + halfZWidth);
                        
    boxes[1] = cBoundingBox(xmin + halfXWidth, xmax, 
                            ymin, ymin + halfYWidth,
                            zmin, zmin + halfZWidth);
                        
    boxes[2] = cBoundingBox(xmin + halfXWidth, xmax, 
                            ymin, ymin + halfYWidth,
                            zmin + halfXWidth, zmax);
                        
    boxes[3] = cBoundingBox(xmin, xmin + halfXWidth, 
                            ymin, ymin + halfYWidth,
                            zmin + halfZWidth, zmax);
                        
    boxes[4] = cBoundingBox(xmin, xmin + halfXWidth, 
                            ymin + halfYWidth, ymax,
                            zmin, zmin + halfZWidth);
                        
    boxes[5] = cBoundingBox(xmin + halfXWidth, xmax, 
                            ymin + halfYWidth, ymax,
                            zmin, zmin + halfZWidth);
                        
    boxes[6] = cBoundingBox(xmin + halfXWidth, xmax, 
                            ymin + halfYWidth, ymax,
                            zmin + halfXWidth, zmax);
                        
    boxes[7] = cBoundingBox(xmin, xmin + halfXWidth, 
                            ymin + halfYWidth, ymax,
                            zmin + halfZWidth, zmax);
}

void cOctree::draw()
{
    for(int i=0; i<8; i++)
    {
        if(children_[i] != NULL)
            children_[i]->draw();
    }

    // render only leaf nodes with triangles
    if(triangles_.size()) box_.draw();
}
