binarytree.cpp

来自「ＲＢＦ平台」· C++ 代码 · 共 232 行

#include "stdafx.h"
#include "BinaryTree.h"


//The implementation of class BSTreeCell
BSTreeCell::BSTreeCell()
{

}

BSTreeCell::BSTreeCell(BSTree * tree, unsigned char nlevel, PointSet * localpset, char fromw,
					   float * lowvtx, float *highvtx)
{
	_tree = tree;
	_leaf = true;
	_fromwhere = fromw;
	_nodelevel = nlevel + 1;
	_localpset = localpset;
	for(int i = 0; i < 3; i++){
		_low[i] = lowvtx[i];
		_high[i] = highvtx[i];
	}

	_leftTree = NULL;
	_rightTree = NULL;
	_coeffalpha = NULL;
	_offsurfpoint = NULL;
}

BSTreeCell::~BSTreeCell()
{
	if(!_leaf){
		delete _leftTree;
		delete _rightTree;
	}
	if(_coeffalpha != NULL)
		delete[] _coeffalpha;
	if(_offsurfpoint != NULL)
		delete[] _offsurfpoint;
}

bool BSTreeCell::insert()
{
	int npls1 = 0;
	int _start, _end;
	float minv[3], maxv[3];
	_start = 0;
	_end = _localpset->_pointN;
	//_localpset->bound(min, max, _start, _end);

	int leafN = 0;  //nl 
	leafN = _localpset->_pointN;
	
	if(leafN > TLEAF)
	{
		int i1,i2;
		int tempi1;
		float n0;

		n0 = float(leafN * OVERLAPQ);
		//clamp n0 to [Tmin, Tmax]
		if( n0 > TMAX)
			n0 = TMAX;
		if( n0 < TMIN)
			n0 = TMIN;

		npls1 = (int)ceil( (n0 + leafN)/2 );
		
		tempi1 = npls1;
		if(_leftTree == NULL)
			i1 = _start + npls1;        //left half
		else
			i1 = npls1; 
		i2 = leafN - tempi1;  //right half

		if(_high[0] - _low[0] > _high[1] - _low[1]){
			_s_axis = 0;     //along x
			_middle = 0.5f*(_high[0] + _low[0]);
		}
		else{
			_s_axis = 1;      //along y
			_middle = 0.5f*(_high[1] + _low[1]);
		}
		if(_high[2] - _low[2] > _high[_s_axis] - _low[_s_axis]){
			_s_axis = 2;      //along z
			_middle = 0.5f*(_high[2] + _low[2]);
		}	

		//sort the pointset 
		_localpset->QuickSort(_s_axis, _start, _end - 1);	

		_leaf = false;

		//left child
		PointSet * leftlocpset = new PointSet;
		leftlocpset->setPointSize(i1);
		for(int i = 0; i < i1; i++)
		{
			leftlocpset->setPoint(i, _localpset->_point[i][0],
				                     _localpset->_point[i][1],
									 _localpset->_point[i][2]);
			leftlocpset->setNormal(i, _localpset->_normal[i][0],
				                      _localpset->_normal[i][1],
									  _localpset->_normal[i][2]);
		}
		//determining the diagonal vertex of bounding box of left child
		float tmpmin[3],tmpmax[3];
		leftlocpset->bound(tmpmin,tmpmax);

		minv[0] = _low[0]; minv[1] = _low[1]; minv[2] = _low[2];
		switch(_s_axis)
		{
			case 0:
				maxv[0] = tmpmax[0];
				maxv[1] = _high[1]; maxv[2] = _high[2];
				break;
			case 1:
				maxv[0] = _high[0];
				maxv[1] = tmpmax[1]; maxv[2] = _high[2];
				break;
			case 2:
				maxv[0] = _high[0];
				maxv[1] = _high[1]; maxv[2] = tmpmax[2];
				break;

		}
		_leftTree = new BSTreeCell(_tree, _nodelevel, leftlocpset, 'l',minv,maxv);

		//right child
		PointSet * rightlocpset = new PointSet;
		rightlocpset->setPointSize(_end - i2);
		for(i = i2; i < _end; i++)
		{
			rightlocpset->setPoint(i - i2, _localpset->_point[i][0],
				                              _localpset->_point[i][1],
											  _localpset->_point[i][2]);
			rightlocpset->setNormal(i - i2, _localpset->_normal[i][0],
				                               _localpset->_normal[i][1],
											   _localpset->_normal[i][2]);
		}
		//determining the diagonal vertex of bounding box of right child
		rightlocpset->bound(tmpmin,tmpmax);

		switch(_s_axis)
		{
			case 0:
				minv[0] = tmpmin[0];
				minv[1] = _low[1]; minv[2] = _low[2];
				break;
			case 1:
				minv[0] = _low[0];
				minv[1] = tmpmin[1]; minv[2] = _low[2];
				break;
			case 2:
				minv[0] = _low[0];
				minv[1] = _low[1]; minv[2] = tmpmin[2];
				break;

		}
		maxv[0] = _high[0]; maxv[1] = _high[1]; maxv[2] = _high[2];

		_rightTree = new BSTreeCell(_tree, _nodelevel, rightlocpset, 'r',minv,maxv);
		

	}

	return true;
}

void BSTreeCell::build()
{
	if(insert()){
		if(_leftTree != NULL){
			_leftTree->build();
		}
		if(_rightTree != NULL){
			_rightTree->build();
		}
	}
}
bool BSTreeCell::isInbtcell(float x, float y, float z)
{

	float minbx[3],maxbx[3];
	this->_localpset->bound(minbx,maxbx);

	if(x < minbx[0] || y < minbx[1] || z < minbx[2] ||
	   x > maxbx[0] || y > maxbx[1] || z > maxbx[2])
	   return false;
	else
		return true;

}

//********************************The implementation of BSTreeCell*************************//

BSTree::BSTree(PointSet* ps){
	_ps = ps;
	
	//int N = ps->_pointN;
	float minx[3],maxx[3];
	ps->bound(minx,maxx);
	minx[0] -= 0.5f; minx[1] -= 0.5f; minx[2] -= 0.5f;
	maxx[0] += 0.5f; maxx[1] += 0.5f; maxx[2] += 0.5f;

	_root = new BSTreeCell(this, -1, _ps, 't',minx,maxx);

	//Entry point
	_root->build();
}

BSTree::~BSTree(){
	delete _root;
	//delete[] _index_list;
}

unsigned char BSTree::GetTreeLevel(BSTreeCell * treecell)
{
	if(treecell->_leaf)
		return treecell->_nodelevel;
	else
	{
		unsigned char nlv;
		nlv = GetTreeLevel(treecell->_leftTree);
		nlv = GetTreeLevel(treecell->_rightTree);
		
		return nlv;
	}
}