bspbrush.cpp

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

#include "bspbrush.h"

void CBSPFaceClipper::VisitLeaf(_CBSPLeafNode *leaf) {
	if(!(leaf->flags & NODE_REACHABLE))
		return;

	leaf->faces.Append(targetFace);
		
	if(addToHull) {
		targetFace->winding.AddWindingToConvexHull(&clipFace->winding, clipFace->GetPlane());
	}
	return;
}

void CBSPFaceClipper::VisitNodeBegin(_CBSPSplitNode *node) {
	sPlane*			plane = g_curMap->GetPlane(node->plane);
	_CBSPFace		front;
	_CBSPFace		*faces[2] = {&front,clipFace};

	faces[P_BACK]->Split(faces[P_FRONT], plane);

	for(int i=0; i<2; i++) {
		if(!faces[i]->winding.Empty()) {
			clipFace = faces[i];
			node->children[i]->Visit(this);
		}
	}
}

void _CBSPBrush::BuildBrush(CMapBrush *mapBrush) {
	int	nsides = mapBrush->sides.GetNum();

	faces.Reserve( nsides );
	faces.TailAlloc( nsides );

	for(int i=0; i<nsides; i++) {
		faces[i] = new _CBSPFace;
		_CBSPFace	*face = faces[i];		

		face->winding.CreateBaseWinding(mapBrush->sides[i].GetPlane());

		for(int j=0; j<nsides; j++) {
			if(i!=j) {
				face->winding.ChopWinding(mapBrush->sides[j].GetPlane());
			}
		}
		face->brushSide = &mapBrush->sides[i];
	}
}


// brushes touching the plane are added only to the side they are on
void _CBSPBrush::SplitBrush(_CBSPBrush *front, sPlane *plane) {

	if(front->faces.GetNum())
		front->faces.Clear();

	float dmin = WORLD_SIZE;
	float dmax = -WORLD_SIZE;

	// check if brush is entirely on one side
	for(int i = 0; i < faces.GetNum(); i++) {
		CAlignedVec<vec4> *p = faces[i]->winding.GetPoints();

		for(int j = 0; j < p->GetNum(); j++) {
			float d = plane->dot(p->GetElemNoBCheck(j));
			
			if(d < dmin)
				dmin = d;
			if(d > dmax)
				dmax = d;
		}
	}

	if(dmin > -EPSILON) {
		front->faces.Swap(faces);
		return;
	} else if(dmax < EPSILON) {
		return;
	}

	// split the brush
	CVector<_CBSPFace*> all_faces;
	all_faces.Swap(faces);

	for(int i = 0; i < all_faces.GetNum(); i++) {

		int s[3] = {0,0,0};
		CAlignedVec<vec4> *p = all_faces[i]->winding.GetPoints();

		for(int j = 0; j < p->GetNum(); j++)
			s[ plane->side(p->GetElemNoBCheck(j)) ] ++;

		if(s[P_FRONT] && !s[P_BACK]) {
			front->faces.Append(all_faces[i]);
			continue;
		}

		if(!s[P_FRONT] && s[P_BACK]) {
			faces.Append(all_faces[i]);
			continue;
		}
		
		// face is split
		_CBSPFace*	b = faces[faces.Append(all_faces[i])];
		front->faces.TailAlloc() = new _CBSPFace;
		_CBSPFace*	f = front->faces.Tail();

		b->Split(f, plane);
	}
}

void _CBSPBrush::ClipSides(_CBSPTree *tree) {

	for(int i=0; i< faces.GetNum(); i++) {
		_CBSPFace*	f = faces[i];

		f->AddFaceRefencesToNodes(tree, true); 

		if(f->winding.Empty()) {
			faces.Remove(i);
			delete f;
		}
	}
}

int _CBSPFace::Emit(CBSP *bsp) {
	CAlignedVec<vec4> *p = winding.GetPoints();
	int r = bsp->surfaces.TailAlloc(1);
	sBSPSurface *surf = &bsp->surfaces[r];

	surf->shaderNum = bsp->shadersHash.AddElem(*brushSide->GetShader());
	surf->fogNum = -1;
	surf->surfaceType = kPlanar;
	surf->numVerts = p->GetNum();
	surf->firstVert =  bsp->vertices.TailAlloc(surf->numVerts);
	surf->numIndexes = 3*(p->GetNum()-2);
	surf->firstIndex = bsp->vertexIndicies.TailAlloc(surf->numIndexes);
	surf->lightmapNum = 0;
	surf->normal = reverse4(brushSide->GetPlane());
	surf->patchSize.x = 0;
	surf->patchSize.y = 0;

	
	for(int i=0; i<p->GetNum(); i++) {
		sBSPVertex*	vert = &bsp->vertices[surf->firstVert+i];
		vec4&		pos = p->GetElemNoBCheck(i);

		vert->pos = pos;
		vert->tex_coord = brushSide->TransformTexCoord(pos);
		vert->normal = surf->normal;
		vert->color[0] = 255;
		vert->color[1] = 255;
		vert->color[2] = 255;
		vert->color[3] = 255;
	}
	
	int ci = 0;
	int *idx = &bsp->vertexIndicies[surf->firstIndex];

	for(int i=1; i<p->GetNum() - 1; i++) {
		idx[ci++] = 0;
		idx[ci++] = i;
		idx[ci++] = i + 1;
	}
	return r;
}

_CBSPBrush&	_CBSPBrush::operator=(_CBSPBrush& b) {
	faces.Clear();
	faces.TailAlloc(b.faces.GetNum());

	for(int i=0; i<b.faces.GetNum(); i++){
		faces[i] = new _CBSPFace(*b.faces[i]);
	}
	return *this;
}

// NOTE: Quake 3 compatibility issue 2 (in readme.txt)
int _CBSPBrush::Emit(CBSP *bsp) {
	int r = bsp->brushes.TailAlloc(1);
	sBSPBrush *brush = &bsp->brushes[r];

	brush->firstSide = bsp->brushSides.TailAlloc(faces.GetNum());
	brush->shaderNum = bsp->shadersHash.AddElem(*faces[0]->brushSide->GetShader());

	sBSPBrushSide *sides = &bsp->brushSides[brush->firstSide];
	int	lastValid = 0;

	for(int i=0; i<faces.GetNum(); i++) {
		sides[i].plane = bsp->planesHash.AddElem(reverse4(faces[i]->brushSide->GetPlane()));
		sides[i].shaderNum = bsp->shadersHash.AddElem(*faces[i]->brushSide->GetShader());

		if(!faces[i]->winding.Empty())
			lastValid = i;
	}

	brush->numSides = lastValid + 1;

	return r;
}

void CBSPBrushFilter::VisitLeaf(_CBSPLeafNode *leaf) {
	if(!(leaf->flags & NODE_OPAQUE)) {
		leaf->flags |= NODE_OPAQUE;
		nLeafs++;
	}
	leaf->brushes.Append(target);
	delete clipBrush;
}

void CBSPBrushFilter::VisitNodeBegin(_CBSPSplitNode *node) {

	_CBSPBrush *brushes[2] = {new _CBSPBrush, clipBrush};

	brushes[P_BACK]->SplitBrush( brushes[P_FRONT], g_curMap->GetPlane(node->plane));

	for(int i=0; i<2; i++) {
		if(brushes[i]->faces.GetNum()) {
			clipBrush = brushes[i];
			node->children[i]->Visit(this);
		} else {
			delete brushes[i];
		}
	}
}