source: code/trunk/src/bullet/BulletCollision/Gimpact/gim_box_set.cpp @ 2877

/*
-----------------------------------------------------------------------------
This source file is part of GIMPACT Library.

For the latest info, see http://gimpact.sourceforge.net/

Copyright (c) 2006 Francisco Leon Najera. C.C. 80087371.
email: projectileman@yahoo.com

 This library is free software; you can redistribute it and/or
 modify it under the terms of EITHER:
   (1) The GNU Lesser General Public License as published by the Free
       Software Foundation; either version 2.1 of the License, or (at
       your option) any later version. The text of the GNU Lesser
       General Public License is included with this library in the
       file GIMPACT-LICENSE-LGPL.TXT.
   (2) The BSD-style license that is included with this library in
       the file GIMPACT-LICENSE-BSD.TXT.
   (3) The zlib/libpng license that is included with this library in
       the file GIMPACT-LICENSE-ZLIB.TXT.

 This library is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the files
 GIMPACT-LICENSE-LGPL.TXT, GIMPACT-LICENSE-ZLIB.TXT and GIMPACT-LICENSE-BSD.TXT for more details.

-----------------------------------------------------------------------------
*/


#include "gim_box_set.h"


GUINT GIM_BOX_TREE::_calc_splitting_axis(
        gim_array<GIM_AABB_DATA> & primitive_boxes, GUINT startIndex,  GUINT endIndex)
{
        GUINT i;

        btVector3 means(btScalar(0.),btScalar(0.),btScalar(0.));
        btVector3 variance(btScalar(0.),btScalar(0.),btScalar(0.));
        GUINT numIndices = endIndex-startIndex;

        for (i=startIndex;i<endIndex;i++)
        {
                btVector3 center = btScalar(0.5)*(primitive_boxes[i].m_bound.m_max +
                                         primitive_boxes[i].m_bound.m_min);
                means+=center;
        }
        means *= (btScalar(1.)/(btScalar)numIndices);

        for (i=startIndex;i<endIndex;i++)
        {
                btVector3 center = btScalar(0.5)*(primitive_boxes[i].m_bound.m_max +
                                         primitive_boxes[i].m_bound.m_min);
                btVector3 diff2 = center-means;
                diff2 = diff2 * diff2;
                variance += diff2;
        }
        variance *= (btScalar(1.)/      ((btScalar)numIndices-1)        );

        return variance.maxAxis();
}


GUINT GIM_BOX_TREE::_sort_and_calc_splitting_index(
        gim_array<GIM_AABB_DATA> & primitive_boxes, GUINT startIndex,
        GUINT endIndex, GUINT splitAxis)
{
        GUINT i;
        GUINT splitIndex =startIndex;
        GUINT numIndices = endIndex - startIndex;

        // average of centers
        btScalar splitValue = 0.0f;
        for (i=startIndex;i<endIndex;i++)
        {
                splitValue+= 0.5f*(primitive_boxes[i].m_bound.m_max[splitAxis] +
                                         primitive_boxes[i].m_bound.m_min[splitAxis]);
        }
        splitValue /= (btScalar)numIndices;

        //sort leafNodes so all values larger then splitValue comes first, and smaller values start from 'splitIndex'.
        for (i=startIndex;i<endIndex;i++)
        {
                btScalar center = 0.5f*(primitive_boxes[i].m_bound.m_max[splitAxis] +
                                         primitive_boxes[i].m_bound.m_min[splitAxis]);
                if (center > splitValue)
                {
                        //swap
                        primitive_boxes.swap(i,splitIndex);
                        splitIndex++;
                }
        }

        //if the splitIndex causes unbalanced trees, fix this by using the center in between startIndex and endIndex
        //otherwise the tree-building might fail due to stack-overflows in certain cases.
        //unbalanced1 is unsafe: it can cause stack overflows
        //bool unbalanced1 = ((splitIndex==startIndex) || (splitIndex == (endIndex-1)));

        //unbalanced2 should work too: always use center (perfect balanced trees)
        //bool unbalanced2 = true;

        //this should be safe too:
        GUINT rangeBalancedIndices = numIndices/3;
        bool unbalanced = ((splitIndex<=(startIndex+rangeBalancedIndices)) || (splitIndex >=(endIndex-1-rangeBalancedIndices)));

        if (unbalanced)
        {
                splitIndex = startIndex+ (numIndices>>1);
        }

        bool unbal = (splitIndex==startIndex) || (splitIndex == (endIndex));
        btAssert(!unbal);

        return splitIndex;
}


void GIM_BOX_TREE::_build_sub_tree(gim_array<GIM_AABB_DATA> & primitive_boxes, GUINT startIndex,  GUINT endIndex)
{
        GUINT current_index = m_num_nodes++;

        btAssert((endIndex-startIndex)>0);

        if((endIndex-startIndex) == 1) //we got a leaf
        {               
                m_node_array[current_index].m_left = 0;
                m_node_array[current_index].m_right = 0;
                m_node_array[current_index].m_escapeIndex = 0;

                m_node_array[current_index].m_bound = primitive_boxes[startIndex].m_bound;
                m_node_array[current_index].m_data = primitive_boxes[startIndex].m_data;
                return;
        }

        //configure inner node

        GUINT splitIndex;

        //calc this node bounding box
        m_node_array[current_index].m_bound.invalidate();       
        for (splitIndex=startIndex;splitIndex<endIndex;splitIndex++)
        {
                m_node_array[current_index].m_bound.merge(primitive_boxes[splitIndex].m_bound);
        }

        //calculate Best Splitting Axis and where to split it. Sort the incoming 'leafNodes' array within range 'startIndex/endIndex'.

        //split axis
        splitIndex = _calc_splitting_axis(primitive_boxes,startIndex,endIndex);

        splitIndex = _sort_and_calc_splitting_index(
                        primitive_boxes,startIndex,endIndex,splitIndex);

        //configure this inner node : the left node index
        m_node_array[current_index].m_left = m_num_nodes;
        //build left child tree
        _build_sub_tree(primitive_boxes, startIndex, splitIndex );

        //configure this inner node : the right node index
        m_node_array[current_index].m_right = m_num_nodes;

        //build right child tree
        _build_sub_tree(primitive_boxes, splitIndex ,endIndex);

        //configure this inner node : the escape index
        m_node_array[current_index].m_escapeIndex  = m_num_nodes - current_index;
}

//! stackless build tree
void GIM_BOX_TREE::build_tree(
        gim_array<GIM_AABB_DATA> & primitive_boxes)
{
        // initialize node count to 0
        m_num_nodes = 0;
        // allocate nodes
        m_node_array.resize(primitive_boxes.size()*2);
        
        _build_sub_tree(primitive_boxes, 0, primitive_boxes.size());
}