BSPTreeサンプル

折角なのでBSPTreeの試行錯誤の末を晒してみようと思います。
ちなみにWin32コンソール用に作った上手いこと動くかの確認サンプルです。
プログラムの実行での不具合やその他諸々には責任を取れませんので、勘弁してください。

ゲームプログラミングのためのリアルタイム衝突判定

まずは、BSPNode.hです。

#ifndef __BSPNODE_H__
#define __BSPNODE_H__

// BSPNode.h

#include <vector>


class BSPNode
{
public:
	enum TYPE
	{
		NODE=0, LEAF
	};

	BSPNode*	m_pPositiveNode;
	BSPNode*	m_pNegativeNode;

	int			m_splitNum;

	std::vector<int>	m_numList;

	TYPE		m_type;

	BSPNode() : m_pPositiveNode(0), m_pNegativeNode(0)
	{ }

	// 葉
	BSPNode( std::vector<int> list, int depth )
	: m_numList( list ), m_pPositiveNode(0), m_pNegativeNode(0), m_type( LEAF )
	{ }

	// 節
	BSPNode( std::vector<int> list, BSPNode *positive, BSPNode *negative, int split )
	: m_numList( list ), m_pPositiveNode( positive ), m_pNegativeNode( negative ), m_splitNum( split ), m_type( NODE )
	{ }


	// 全てを消去
	void Clenaup();
};

// BSP-Treeを構築
BSPNode *BuildBSPTree( std::vector<int> list, int depth );
// 分割数を見つける
int FindNum( std::vector<int> list, int depth );


#endif	// __BSP_H__

次に、BSPNode.cppです。

// BSPNode.cpp

#include "BSPNode.h"


// 分割数を見つける
int FindNum( std::vector<int> list, int depth )
{
	int sum = 0;
	int index = (int)list.size();
	for( int i = 0; i < index; ++i )
		sum += list.at(i);

	sum /= index;

	return sum;
}


// BSP-Treeを構築
BSPNode *BuildBSPTree( std::vector<int> list, int depth )
{
	if( list.empty() ) return NULL;

	int numList = (int)list.size();

	// 要素が１なら葉
	const int MIN_LEAF_SIZE = 1;
	if( numList <= MIN_LEAF_SIZE )
		return new BSPNode( list, depth );

	std::vector<int> front, back;

	int div = FindNum( list, depth );
	for( int i = 0; i < numList; ++i )
	{
		if( div < list.at(i) )
			back.push_back( list.at(i) );
		else
			front.push_back( list.at(i) );
	}

	BSPNode *frontNode = BuildBSPTree( front, depth+1 );
	BSPNode *backNode = BuildBSPTree( back, depth+1 );
	
	return new BSPNode( list, frontNode, backNode, div );
}

void BSPNode::Clenaup()
{
	if( m_pPositiveNode )
	{
		m_pPositiveNode->Clenaup();
		delete m_pPositiveNode;
		m_pPositiveNode = 0;
	}
	if( m_pNegativeNode )
	{
		m_pNegativeNode->Clenaup();
		delete m_pNegativeNode;
		m_pNegativeNode = 0;
	}
}

最後に、main.cppです。

// main.cpp

#include "BSPNode.h"
#include <vector>
#include <iostream>

using namespace std;


BSPNode *pRoot = NULL;
int main()
{
	int num[] = { 1, 3, 5, 7, 9, 11, 13, 15 };
	vector<int> elements;
	for( int i = 0; i < 8; ++i )
		elements.push_back( num[i] );

	pRoot = new BSPNode();
	pRoot = BuildBSPTree( elements, 0 );

	BSPNode* root = pRoot;
	int input = 0;
	while( root )
	{
		int size = (int)root->m_numList.size();
		cout << "size : " << size << endl;
		cout << "elements : ";
		for( int i = 0; i < size; ++i )
			cout << root->m_numList.at(i) << " ";
		cout << endl;

		// 入力
		cout << "大きいノード：１　小さいノード：２ > ";
		cin >> input;
		switch( input )
		{
		case 1:
			root = root->m_pNegativeNode;
			break;
		case 2:
			root = root->m_pPositiveNode;
			break;
		default:
			break;
		}
	}

	pRoot->Clenaup();
	if( !pRoot->m_pNegativeNode ) cout << "pRoot->m_pNegativeNode is NULL" << endl;
	if( !pRoot->m_pPositiveNode ) cout << "pRoot->m_pPositiveNode is NULL" << endl;

	delete pRoot;

	return 0;
}

汚いコードですが、どこかで誰かの何かの助けになればと思います。