Webcam/include/framework/bih/bih_build.cpp

/* -----------------------------------------------------------------------------
	GSFramework
	Copyright 2001-2013 Emmanuel Julien. All Rights Reserved.
----------------------------------------------------------------------------- */


		#include <float.h>
		#include "bih/bih.h"
		#include "timing/benchmark.h"
		#include "log/log.h"

		using namespace GS;
		using namespace GS::BIH;


//-----------------------------------------------------------------------------
static void			HalveMinMax(MinMax &minmax, int n, bool trim_max)
{
	if	(trim_max)
			minmax.mx[n] = (minmax.mn[n] + minmax.mx[n]) * 0.5f;
	else	minmax.mn[n] = (minmax.mn[n] + minmax.mx[n]) * 0.5f;
}
//-----------------------------------------------------------------------------

//-----------------------------------------------------------------------------
void				Tree::MakeNodeLeaf(Node *node, uint count, uint *p_sarray, MinMax * /*varray*/)
{
	leaf_count++;
	node->axis = Math::AxisNone;
	node->p = (void *)p_sarray;
	node->count = count;
}
void				Tree::DoNodeSplit(MinMax &minmax, uint count, uint *sarray, MinMax *varray, uint &pivot, Node *node, uint &split_axis)
{
	// Determine split axis.
	Vector4 dt = minmax.mx - minmax.mn;

	if	((dt.x > dt.y) && (dt.x > dt.z))
		split_axis = 0;
	else if	((dt.y > dt.x) && (dt.y > dt.z))
		split_axis = 1;
	else
		split_axis = 2;

	float split_coord = (minmax.mn[split_axis] + minmax.mx[split_axis]) * 0.5f;

	// Fill split arrays.
	float extends[2];
	uint high = count;

	//--------------------------------------------------------------------------
	#define	__INDICE_SWAP__(LO, HI)	{ uint swp = sarray[LO]; sarray[LO] = sarray[HI]; sarray[HI] = swp; }
	//--------------------------------------------------------------------------
	#define	__GET_EXTENDS__(I, S)	{ extends[0] = varray[sarray[I]].mn[S]; extends[1] = varray[sarray[I]].mx[S]; }

	pivot = 0;
	while (pivot < high)
	{
		__GET_EXTENDS__(pivot, split_axis)
		if	((extends[1] - split_coord) > (split_coord - extends[0]))
		{	// max
			__INDICE_SWAP__(pivot, high - 1)
			high--;
		}
		else
		{	// min
			__INDICE_SWAP__(0, pivot)
			pivot++;
		}
	}

	// Node extends.
	node->split[0] = -FLT_MAX;

	uint n;
	for	(n = 0; n < pivot; ++n)
	{
		__GET_EXTENDS__(n, split_axis)
		if	(extends[1] > node->split[0])
			node->split[0] = extends[1] + 0.0001f;
	}
	node->split[1] = FLT_MAX;
	for	(; n < count; ++n)
	{
		__GET_EXTENDS__(n, split_axis)
		if	(extends[0] < node->split[1])
			node->split[1] = extends[0] - 0.0001f;
	}
}
bool				Tree::Split(MinMax &l_minmax, uint count, uint *p_sarray, MinMax *varray, Node *node, uint dpth)
{
	if	((count <= min_leaf_vcount) || (dpth == 64))
	{
		if	(dpth > depth)
			depth = dpth;
		MakeNodeLeaf(node, count, p_sarray, varray);
	}
	else
	{
		// Split node.
		uint pivot, split_axis;
		DoNodeSplit(l_minmax, count, p_sarray, varray, pivot, node, split_axis);

		// Distribute to children.
		node_count += 2;
		Node *children = new Node[2];
		if	(!children)
			__ERR__(__LOG_E__ << "Failed to allocate BIH node children.\n", false)
		node->axis = (char)split_axis;
		node->p = (void *)children;

		MinMax minmax_child = l_minmax;
		HalveMinMax(minmax_child, split_axis, true);
		Split(minmax_child, pivot, p_sarray, varray, &children[0], dpth + 1);
		minmax_child = l_minmax;
		HalveMinMax(minmax_child, split_axis, false);
		Split(minmax_child, count - pivot, &p_sarray[pivot], varray, &children[1], dpth + 1);
	}
	return true;
}
//-----------------------------------------------------------------------------

//-----------------------------------------------------------------------------
bool				Tree::Build(uint count, MinMax *varray)
{
	Benchmark build_bench(true);

	if	(!count)
		return false;

	// Initialize split array.
	if	(!sarray.Allocate(count))
		__ERR__(__LOG_E__ << "Failed to allocate BIH indice array.\n", false)

	uint n;
	for	(n = 0; n < count; ++n)
		sarray[n] = n;

	// Get volume set bounding coordinates.
	minmax = varray[0];
	for	(n = 1; n < count; ++n)
		minmax.Grow(varray[n]);
	minmax.mn -= 0.0001f;
	minmax.mx += 0.0001f;

	// Split.
	leaf_count = 0;
	node_count = 1;
	depth = 0;

	if	(!(root = new Node))
		__ERR__(__LOG_E__ << "Failed to allocate BIH root node.\n", false)

	bool success = Split(minmax, count, sarray, varray, root, 0);

	build_bench.Stop();
//	__LOG__ << "Done in " << build_bench.GetLastStepMs() << "ms. " << node_count << " nodes, " << leaf_count << " leaves, depth = " << depth << ".\n";
	return success;
}
//-----------------------------------------------------------------------------