portal.cpp

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

#include <stdio.h>
#include "portal.h"

void CPortalBuilder::BuildPortals(_CBSPTree *t) {
	tree = t;
	CreateHeadPortals();
	tree->tree->Traverse(this);
	g_CLog.Log(LOG_SYSTEM, "%4d portals created.", portals.GetNum());
}

void CPortalBuilder::RemovePortalReference(_CBSPNode *n, int portal) {
	for(int i=0; i<n->portals.GetNum(); i++) {
		if(n->portals[i] == portal) {
			n->portals.Remove(i);
			break;
		}
	}
}

// the *i suffix stands for index
// FIXME: This is hard stuff
void CPortalBuilder::SplitNodePortals(_CBSPSplitNode *node) {
	for(int i=0; i<node->portals.GetNum(); i++) {
		int			portal_i = node->portals[i];
		sPortal*	portal = &portals[portal_i];

		int			other_side = (portal->nodes[0] == node);
		_CBSPNode*	other_node = portal->nodes[other_side];	//	other node this portals connects to

		// reuse portal slot as np[P_BACK]
		int			newp_i[] = { portals.TailAlloc(1), portal_i };
		// allocation might have invalidated portal
		portal = &portals[portal_i];

		sPortal*	new_portals[] = { &portals[ newp_i[0] ], portal };
		bool		tiny_portal[2];

		RemovePortalReference(other_node, portal_i);

		new_portals[P_BACK]->winding.SplitWinding(
													new_portals[P_FRONT]->winding,
													tree->srcMap->GetPlane(node->plane)
													);

		new_portals[P_FRONT]->plane = portal->plane;

		
		for(int j=0; j<2; j++) {
			tiny_portal[j] = new_portals[j]->winding.Tiny();
		}

#if 1 // More efficient allocation
		if(tiny_portal[P_FRONT]) {
			// discard front portal
			portals.SetNum(portals.GetNum() - 1);
#if _DEBUG
			if(tiny_portal[P_BACK]) {
				g_CLog.Log(LOG_SYSTEM, "SplitNodePortals: BUG - 2 Tiny portals.");
			}
#endif
		} else if(tiny_portal[P_BACK]) {
			// write front portal in place of back portal
			new_portals[P_BACK]->winding.GetPoints()->Swap(*new_portals[P_FRONT]->winding.GetPoints());
			new_portals[P_FRONT] = new_portals[P_BACK];
			newp_i[P_FRONT] = newp_i[P_BACK];
			portals.SetNum(portals.GetNum() - 1);
		}
#endif

		for(int j=0; j<2; j++) {
			if(tiny_portal[j])
				continue;

			new_portals[j]->nodes[!other_side] = node->children[j];
			new_portals[j]->nodes[other_side] = other_node;

			node->children[j]->portals.Append( newp_i[j] );
			other_node->portals.Append(newp_i[j]);
		}
	}
	node->portals.Clear();
}

void CPortalBuilder::CreateNodePortal(_CBSPSplitNode *n) {
	int			portal_i;
	sPortal		*p;

	portal_i = portals.TailAlloc(1);
	p = &portals[portal_i];

	p->plane = n->plane;
	p->winding.CreateBaseWinding( tree->srcMap->GetPlane( p->plane ) );
	p->nodes[0] = n->children[0];
	p->nodes[1] = n->children[1];

	for(int i=0; i<n->portals.GetNum(); i++) {
		sPortal *p2 = &portals[n->portals[i]];
		sPlane	*plane = tree->srcMap->GetPlane( p2->plane );

		if(p2->nodes[P_FRONT] == n)
			p->winding.ChopWinding( plane );
		else
			p->winding.ChopWinding( &reverse4(plane) );
	}

	n->children[P_FRONT]->portals.Append(portal_i);
	n->children[P_BACK]->portals.Append(portal_i);
}


void CPortalBuilder::CreateHeadPortals() {

	vec4 points[] = {	vec4(tree->min.x, tree->min.y, tree->min.z),	// 0
						vec4(tree->max.x, tree->min.y, tree->min.z),	// 1
						vec4(tree->max.x, tree->max.y, tree->min.z),	// 2
						vec4(tree->min.x, tree->max.y, tree->min.z),	// 3

						vec4(tree->min.x, tree->min.y, tree->max.z),	// 4
						vec4(tree->max.x, tree->min.y, tree->max.z),	// 5
						vec4(tree->max.x, tree->max.y, tree->max.z),	// 6
						vec4(tree->min.x, tree->max.y, tree->max.z) };// 7

	const int ppoints[6][4] = {	{0, 1, 2, 3},	// far
								{4, 5, 6, 7},	// near
								{0, 1, 5, 4},	// bottom
								{3, 2, 6, 7},	// top
								{0, 3, 7, 4},	// left
								{1, 2, 6, 5} };	// right

	sPlane planes[6] = {	vec4( 0.0f,  0.0f,  1.0f, -tree->min.z),
							vec4( 0.0f,  0.0f, -1.0f,  tree->max.z),
							vec4( 0.0f,  1.0f,  0.0f, -tree->min.y),
							vec4( 0.0f, -1.0f,  0.0f,  tree->max.y),
							vec4( 1.0f,  0.0f,  0.0f, -tree->min.x),
							vec4(-1.0f,  0.0f,  0.0f,  tree->max.x)	};

	portals.Clear();
	portals.TailAlloc(6);

	for(int i=0; i<6; i++) {
		portals[i].nodes[P_FRONT] = tree->tree;
		portals[i].nodes[P_BACK] = &outside;
		portals[i].plane = tree->srcMap->AddPlane(planes[i]);

		portals[i].winding.GetPoints()->TailAlloc(4);

		vec4 *data = portals[i].winding.GetPoints()->GetData();

		for(int j=0; j<4; j++) {
			data[j] = points[ ppoints[i][j] ];
		}

		tree->tree->portals.Append(i);
		outside.portals.Append(i);
	}
}

void CPortalBuilder::MarkNodeReachability() {
	nLeafs = 0;
	CVector<CMapEntity> *me = tree->srcMap->GetEntities();
	CString key("origin", false);

	for(int i=1; i<me->GetNum(); i++) {
		CMapEntity*	entity = &me->GetElemNoBCheck(i);
		CString*	s_origin = entity->GetValue(key);
		vec4		origin;

		if(!s_origin)
			continue;

		s_origin->ToFloat(origin.data, 3);
		origin.w = 1.0f;

		FloodReachability(tree->FindLeaf(&origin));
	}
	g_CLog.Log(LOG_SYSTEM, "%4d reachable leafs.", nLeafs);
}

void CPortalBuilder::FloodReachability(_CBSPLeafNode *leaf) {
#if 0
	if(leaf->flags & NODE_REACHABLE)
		return;

	if(leaf->flags & NODE_OPAQUE) {
		return;
	}
#else
	// Currently there are 2 flags only
	if(leaf->flags)
		return;
#endif

	leaf->flags |= NODE_REACHABLE;

	// Number visible clusters
	leaf->cluster = nLeafs;

	nLeafs++;

	for(int i=0; i<leaf->portals.GetNum(); i++) {
		sPortal*		portal = &portals[ leaf->portals[i] ];
		int				other_side = (portal->nodes[0] == leaf);
		_CBSPLeafNode*	other_leaf = (_CBSPLeafNode*)portal->nodes[other_side];

		FloodReachability( other_leaf );
	}
}

bool CPortalBuilder::IsMapClosed() {
	return !(outside.flags & NODE_REACHABLE);
}

void CPortalBuilder::SaveToFile(char *filename) {
	FILE *fp = fopen(filename, "wb");
	if(fp) {
		g_CLog.Log(LOG_SYSTEM, "Saving Portals to %s.", filename);
	} else {
		g_CLog.Log(LOG_SYSTEM, "Couldn't open %s for writing.", filename);
		return;
	}

#ifdef BINARY_PORTAL_FILE
	sPortalHeader ph;
	ph.magic[0] = 'B';
	ph.magic[1] = 'P';
	ph.magic[2] = 'R';
	ph.magic[3] = 'T';
	ph.version = 0;
	fwrite(&ph, sizeof(sPortalHeader), 1, fp);
#else
	fwrite("TPRT\nNUMB", 9, 1, fp);
#endif

	int nVisPortals = 0;

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

		_CBSPLeafNode *leafs[2];
		leafs[0] = (_CBSPLeafNode*)portals[i].nodes[0];
		leafs[1] = (_CBSPLeafNode*)portals[i].nodes[1];
		if(leafs[0]->flags & NODE_OPAQUE || leafs[1]->flags & NODE_OPAQUE)
			continue;

		nVisPortals++;

		CAlignedVec<vec4> *p = portals[i].winding.GetPoints();

#ifdef BINARY_PORTAL_FILE
		sPInfo pinfo;
		pinfo.cluster[0] = leafs[0]->cluster;
		pinfo.cluster[1] = leafs[1]->cluster;
		pinfo.numPoints = p->GetNum();

		fwrite(&pinfo, sizeof(sPInfo), 1, fp);
#else
		fprintf(fp, "\n%2d %2d %2d", leafs[0]->cluster, leafs[1]->cluster, p->GetNum());
#endif

		for(int j=0; j<p->GetNum(); j++) {
			vec4 *v = &p->GetElemNoBCheck(j);

#ifdef BINARY_PORTAL_FILE
			fwrite(v, 3*sizeof(float), 1, fp);
#else
			fprintf(fp, " (%.2f %.2f %.2f)", v->x, v->y, v->z);
#endif
		}
	}

#ifdef BINARY_PORTAL_FILE
	fseek(fp, offsetof(sPortalHeader, numPortals), SEEK_SET);
	fwrite(&nVisPortals, sizeof(int), 1, fp);
#else
	fseek(fp, 5, SEEK_SET);
	fprintf(fp, "%4d", nVisPortals);
#endif

	fclose(fp);
}

void CNodeBoundsCalc::VisitLeaf(_CBSPLeafNode *n) {
	n->min = vec4( WORLD_SIZE,  WORLD_SIZE,  WORLD_SIZE);
	n->max = vec4(-WORLD_SIZE, -WORLD_SIZE, -WORLD_SIZE);

	if(!n->flags & NODE_REACHABLE)
		return;

	for(int i=0; i<n->portals.GetNum(); i++) {
		CAlignedVec<vec4> *p = portals->GetElemNoBCheck( n->portals[i] ).winding.GetPoints();

		for(int j=0; j<p->GetNum(); j++) {
			n->min.minSelf( p->GetElemNoBCheck(j) );
			n->max.maxSelf( p->GetElemNoBCheck(j) );
		}
	}
	//vec4 dif = n->max - n->min;
	//float volume = dif.x*dif.y*dif.z;
}

void CNodeBoundsCalc::VisitNodeEnd(_CBSPSplitNode *n) {
	n->min = min4( n->children[0]->min, n->children[1]->min );
	n->max = max4( n->children[0]->max, n->children[1]->max );
}