source: GTP/trunk/App/Demos/Vis/FriendlyCulling/src/BvhConstructor.cpp @ 3265

#include "BvhConstructor.h"
#include "Triangle3.h"
#include "SceneEntity.h"
#include "Geometry.h"
#include "gzstream.h"

#include <queue>
#include <stack>
#include <fstream>

#ifdef _CRT_SET
        #define _CRTDBG_MAP_ALLOC
        #include <stdlib.h>
        #include <crtdbg.h>

        // redefine new operator
        #define DEBUG_NEW new(_NORMAL_BLOCK, __FILE__, __LINE__)
        #define new DEBUG_NEW
#endif


using namespace std;


namespace CHCDemoEngine
{

BvhConstructor::BvhConstructor(SceneEntity **entities, 
                                                           int first, 
                                                           int last):
mEntities(entities),
mFirst(first),
mLast(last),
mMaxDepth(10),
mMaxObjects(1),
mNumNodes(0)
{
}


int BvhConstructor::SortTriangles(BvhLeaf *leaf, 
                                           int axis, 
                                           float position
                                           )
{
        int i = leaf->mFirst;
        int j = leaf->mLast;

    while (1)
        {
                //while (mEntities[i]->GetWorldCenter()[axis] < position) ++ i;
                //while (position < mEntities[j]->GetWorldCenter()[axis]) -- j;

                while ((i < leaf->mLast) && (mEntities[i]->GetWorldCenter()[axis] < position)) ++ i;
                while ((j > leaf->mFirst) && (position < mEntities[j]->GetWorldCenter()[axis])) -- j;

                // sorting finished
                if (i >= j) break;

                // swap entities
                swap(mEntities[i], mEntities[j]);
                        
                ++ i;
                -- j;
        }

        return j;
}


int BvhConstructor::SortTrianglesSpatialMedian(BvhLeaf *leaf, 
                                                                                           int axis)
{
        // spatial median
        float m = leaf->GetBox().Center()[axis];
        return SortTriangles(leaf, axis, m);
}


BvhNode *BvhConstructor::SubdivideLeaf(BvhLeaf *leaf, 
                                                                           int parentAxis
                                                                           )
{
        if (TerminationCriteriaMet(leaf))
        {
                if (leaf->CountPrimitives() <= 0)
                        cout << "leaf constructed:" << leaf->mBox << " " << leaf->mFirst << " " << leaf->mLast << endl;
                return leaf;
        }

        //const int axis = (parentAxis + 1) % 3;
        const int axis = leaf->mBox.MajorAxis();
        const int scale = 20;

        // position of the split in the partailly sorted array of triangles
        // corresponding to this leaf
        int split = -1;
        float pos = -1.0f;
        
        // Spatial median subdivision
        split = SortTrianglesSpatialMedian(leaf, axis);
        pos = leaf->mBox.Center()[axis];
        
        if (split == leaf->mLast)
        {
                // no split could be achieved => just halve number of objects
                split = (leaf->mLast + leaf->mFirst) / 2;
                cerr << "no reduction " << leaf->CountPrimitives() << " " << leaf->mFirst << " " << leaf->mLast << endl;
        }

        // create two more nodes
        mNumNodes += 2;
        BvhInterior *parent = new BvhInterior(leaf->GetParent());
        parent->mFirst = leaf->mFirst;
        parent->mLast = leaf->mLast;
        
        parent->mAxis = axis;
        parent->mBox = leaf->mBox;
        parent->mDepth = leaf->mDepth;

        BvhLeaf *front = new BvhLeaf(parent);

        parent->mBack = leaf;
        parent->mFront = front;
                
        // now assign the triangles to the subnodes
        front->mFirst = split + 1;
        front->mLast = leaf->mLast;
        front->mDepth = leaf->mDepth + 1;

        leaf->mLast = split;
        leaf->mDepth = front->mDepth;
        leaf->mParent = parent;
        
        front->mBox = SceneEntity::ComputeBoundingBox(mEntities + front->mFirst, front->CountPrimitives());
        leaf->mBox = SceneEntity::ComputeBoundingBox(mEntities + leaf->mFirst, leaf->CountPrimitives());

        // recursively continue subdivision
        parent->mBack = SubdivideLeaf(static_cast<BvhLeaf *>(parent->mBack), axis);
        parent->mFront = SubdivideLeaf(static_cast<BvhLeaf *>(parent->mFront), axis);
        
        return parent;
}


bool BvhConstructor::TerminationCriteriaMet(BvhLeaf *leaf) const
{
        const bool criteriaMet = 
                (leaf->mDepth > mMaxDepth) ||
                (leaf->CountPrimitives() <= mMaxObjects);

        return criteriaMet;
}


BvhNode *BvhConstructor::Construct(int &numNodes)
{
        BvhNode *root;

        mNumNodes = 1;

        BvhLeaf *l = new BvhLeaf(NULL);
        
        l->mBox = SceneEntity::ComputeBoundingBox(mEntities + mFirst, mFirst - mLast + 1);

        l->mFirst = mFirst;
        l->mLast = mLast;
        l->mArea = l->mBox.SurfaceArea();
        
        cout << "constructing bvh"  << endl;

        root = SubdivideLeaf(l, 0);

        numNodes = mNumNodes;

        return root;
}


}