buildbsp.cpp

3D游戏开发需要用到BSP树来经行场景渲染的管理。本代码包含完整的BSP及文件生成实现

#include "buildbsp.h"
#include "bspbrush.h"


bool CBSPBuilder::BuildTree(_CBSPTree *t) {
	tree = t;

	if(!ExtractMapData())
		return R_FAIL;

	nLeafs = 0;

	InitTree();

	tree->Traverse(this);

	// Chopped up faces are not needed any more
	faces.Clear();

	g_CLog.Log(LOG_SYSTEM, "%4d leafs on tree.", nLeafs);
	return R_OK;
}

void CBSPBuilder::RebuildTree() {
	CBSPReachableExtractor re;

	re.ExtractReachableAndDeallocate(tree);

	g_CLog.Log(LOG_SYSTEM, "%4d faces on tree", tree->faces.GetNum());

	faces.SetNum(tree->faces.GetNum());

	for(int i=0; i<faces.GetNum(); i++) {
		faces[i] = *tree->faces[i];
	}

	nLeafs = 0;

	InitTree();
	tree->Traverse(this);

	// Chopped up faces are not needed any more
	faces.Clear();

	g_CLog.Log(LOG_SYSTEM, "%4d leafs on tree.", nLeafs);
}


bool CBSPBuilder::ExtractMapData() {
	if(!tree->srcMap->GetEntities()->GetNum()) {
		g_CLog.Log(LOG_SYSTEM, "Map has no entities");
		return R_FAIL;
	}

	CVector<CMapBrush> *mapBrushes = tree->srcMap->GetEntities()->GetElemNoBCheck(0).GetBrushes();

	if (!mapBrushes->GetNum()) {
		g_CLog.Log(LOG_SYSTEM, "Worldspawn has no geometry");
		return R_FAIL;
	}

	tree->brushes.TailAlloc(mapBrushes->GetNum());
	tree->faces.Reserve(mapBrushes->GetNum() * 8);
	faces.Reserve(mapBrushes->GetNum() * 8);

	for(int i=0; i<mapBrushes->GetNum(); i++) {
		tree->brushes[i] = new _CBSPBrush;
		_CBSPBrush *brush = tree->brushes[i];

		brush->BuildBrush( &mapBrushes->GetElemNoBCheck(i) );

		tree->faces.Append( brush->faces );

		for(int j=0; j<brush->faces.GetNum(); j++) {
			// get a local copy of all faces
			faces.Append( *brush->faces[j] );
		}
	}

	g_CLog.Log(LOG_SYSTEM, "%4d brushes from map.", tree->brushes.GetNum());
	g_CLog.Log(LOG_SYSTEM, "%4d faces from map.", faces.GetNum());

	return R_OK;
}

void CBSPBuilder::CalcInitialTreeBounds() {

	tree->min = vec4( WORLD_SIZE,  WORLD_SIZE,  WORLD_SIZE);
	tree->max = vec4(-WORLD_SIZE, -WORLD_SIZE, -WORLD_SIZE);
	
	for(int i=0; i<faces.GetNum(); i++) {
		CAlignedVec<vec4> *p = faces[ i ].winding.GetPoints();

		for(int j=0; j<p->GetNum(); j++) {
			tree->min.minSelf( p->GetElemNoBCheck(j) );
			tree->max.maxSelf( p->GetElemNoBCheck(j) );
		}
	}
}

void CBSPBuilder::InitTree() {
	_CBSPNode *node = tree->AllocTree();

	node->faces.SetNum(faces.GetNum());

	for(int i=0; i<faces.GetNum(); i++)
		node->faces[i] = i;

	CalcInitialTreeBounds();
}

void CBSPBuilder::PickSplitPlane(_CBSPSplitNode *n) {
	int			bestSplit = 0;
	float		bestVal = 0.0f;
	const int*	ifaces = n->faces.GetData();
	const int	numFaces = n->faces.GetNum();

	float invFaceNum = 1.0f / (float)numFaces;

	
	for(int i=0; i<numFaces; i++) {
		int			sides[4] = {0,0,-1,0};
		_CBSPFace	*face = &faces[ ifaces[i] ];

		sPlane *splitPlane = face->brushSide->GetPlane();

		for(int j=0; j<numFaces; j++) {
			sides[ faces[ ifaces[j] ].winding.OnSide(splitPlane) ] ++;
		}

		float ratio = 0.0f;
		if(sides[P_FRONT] > sides[P_BACK])
			ratio = (float)sides[P_BACK] / (float)sides[P_FRONT];
		else if(sides[P_FRONT] < sides[P_BACK])
			ratio = (float)sides[P_FRONT] / (float)sides[P_BACK];

		float splitFactor = (float)sides[P_CROSS] * invFaceNum;

		float val = ratio / (1.0f + splitFactor);
		
		if(face->brushSide->GetShader()->surfaceFlags & SURF_HINT)
			val += 0.1f;

		if(val > bestVal) {
			bestVal = val;
			bestSplit = i;
		}
	}
	n->plane = faces[ ifaces[bestSplit] ].brushSide->GetIPlane();
}

// O(n^2)
void CBSPBuilder::CreateSplitNode(_CBSPSplitNode *n) {
	CVector<int>	childFaceList[2];
	sPlane*			splitPlane;
	int*			ifaces = n->faces.GetData();
	int				numFaces = n->faces.GetNum();

	PickSplitPlane(n);

	splitPlane = g_curMap->GetPlane(n->plane);
	
	for(int i = 0; i < numFaces; i++) {

		int			iface = ifaces[i];
		int			side = faces[ iface ].winding.OnSide(splitPlane);

		switch(side) {
			case P_FRONT:
				childFaceList[P_FRONT].Append( iface );
				break;
			case P_BACK:
				childFaceList[P_BACK].Append( iface );
				break;
			case P_ON:
				break;
			case P_CROSS:
				int front = faces.TailAlloc(1);
				faces[ front ].brushSide = faces[ iface ].brushSide;
				faces[ iface ].winding.SplitWinding(faces[front].winding, splitPlane);

				childFaceList[P_FRONT].Append( front );
				childFaceList[P_BACK].Append( iface );
				break;
		}
	}

	n->faces.Clear();

	for(int i=0; i<2; i++) {
		if(childFaceList[i].GetNum()) {
			n->children[i] = new _CBSPSplitNode;
			n->children[i]->faces.Swap( childFaceList[i] );
		} else {
			nLeafs++;
			n->children[i] = new _CBSPLeafNode;
		}			
	}
}

void CBSPReachableExtractor::VisitLeaf(_CBSPLeafNode *l) {
	if(l->flags & NODE_REACHABLE) {
		faces.Append(l->faces);
#if _DEBUG
	} else {
		if(l->faces.GetNum()) {
			g_CLog.Log(LOG_SYSTEM, "BUG: Not reachable leaf has faces!");
			for(int i=0; i<l->faces.GetNum(); i++) {
				l->faces[i]->winding.GetPoints()->Clear();
			}
		}
#endif
	}
}

void CBSPReachableExtractor::ExtractReachableAndDeallocate(_CBSPTree *tree) {
	tree->Traverse(this);
	delete tree->tree;

	tree->faces.Clear();

	// remove duplicate faces
	for(int i=0; i<faces.GetNum(); i++) {
		int j;
		_CBSPFace *face = faces[i];

		for(j=i+1; j<faces.GetNum(); j++) {
			if(face == faces[j]) {
				break;
			}
		}
		if(j == faces.GetNum())
			tree->faces.Append(face);
	}
	faces.Clear();
}