visibility.cpp

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

#include "visibility.h"

CVisCalc::CVisCalc() {
	threads.Init(true);
}

CVisCalc::~CVisCalc() {
	threads.ShutDown();

	for(int i=0; i<portals.GetNum()/2; i++) {
		delete portals[i].winding;
	}
}

bool CVisCalc::LoadBSP(char* fn) {
	FILE *fp = fopen(fn, "rb");
	if(!fp) {
		g_CLog.Log(LOG_SYSTEM, LOG_FILE_NOT_FOUND, fn);
		return R_FAIL;
	}

	sBSPHeader header;
	fread(&header, sizeof(sBSPHeader), 1, fp);
	fclose(fp);

	if(header.ID != BSP_ID.iBSP_ID) {
		g_CLog.Log(LOG_SYSTEM, "File %s is not a valid BSP File.", fn);
		return R_FAIL;
	}
	
	if(header.version != BSP_VER) {
		g_CLog.Log(LOG_SYSTEM, "File %s is wrong version - expected %d, got %d.", fn, BSP_VER, header.version);
		return R_FAIL;
	}

	if(header.lumps[kVisData].length) {
		g_CLog.Log(LOG_SYSTEM, "BSP file already contains visibility information.");
	}

	clusters.TailAlloc(header.lumps[kLeafs].length / sizeof(sBSPLeaf));

	// Read portals
	filename = fn;
	filename.RemoveExtension();
	filename.Append(".prt", 4);

	fp = fopen(filename.GetData(), "rb");

	if(!fp) {
		g_CLog.Log(LOG_SYSTEM, LOG_FILE_NOT_FOUND, filename.GetData());
		return R_FAIL;
	}

	sPortalHeader ph;

	fread(&ph, sizeof(sPortalHeader), 1, fp);

	if(ph.magic[0] != 'B' ||
		ph.magic[1] != 'P' ||
		ph.magic[2] != 'R' ||
		ph.magic[3] != 'T' ||
		ph.version != 0) {
		g_CLog.Log(LOG_SYSTEM, "File %s is not a valid binary portal file.", filename.GetData());
		fclose(fp);
		return false;
	}

	portals.TailAlloc(2*ph.numPortals);

	g_CLog.Log(LOG_SYSTEM, "Reading %d portals from %s.", ph.numPortals, filename.GetData());

	for(int i=0; i<ph.numPortals; i++) {
		sPInfo		pInfo;
		sVisPortal*	portal = &portals[i];

		// read in cluster info
		fread(&pInfo, sizeof(sPInfo), 1, fp);

		portal->cluster = pInfo.cluster[0];
		portal->otherCluster = pInfo.cluster[1];

		// add portal reference to cluster
		clusters[portal->cluster].portals.Append(i);

		portal->winding = new CWinding;

		CAlignedVec<vec4> *points = portal->winding->GetPoints();

		points->Reserve(pInfo.numPoints);
		points->TailAlloc(pInfo.numPoints);

		for(unsigned int j=0; j<pInfo.numPoints; j++) {
			fread(&((*points)[j]), 3*sizeof(float), 1, fp);
			(*points)[j].w = 1.0f;
		}

		vec4 v1 = (*points)[1] - (*points)[0];
		vec4 v2 = (*points)[2] - (*points)[0];
		portal->plane = v2.cross3D(v1);
		portal->plane.normalize();
		portal->plane.w = -portal->plane.dot((*points)[0]);
	}

	fclose(fp);

	// Store also reversed portals as the second half of the portals vector
	for(int i=0; i<ph.numPortals; i++) {
		int dst_i = i + ph.numPortals;
		sVisPortal*	srcPortal = &portals[i];
		sVisPortal*	dstPortal = &portals[dst_i];

		dstPortal->cluster = srcPortal->otherCluster;
		dstPortal->otherCluster = srcPortal->cluster;

		clusters[dstPortal->cluster].portals.Append(dst_i);

		dstPortal->winding = srcPortal->winding;

		dstPortal->plane = reverse4(&srcPortal->plane);
	}

	filename = fn;

	return R_OK;
}


void CVisCalc::SaveBSP() {
	FILE *fp = fopen(filename.GetData(), "r+b");
	if(fp) {
		g_CLog.Log(LOG_SYSTEM, "Saving to %s.", filename.GetData());
	} else {
		g_CLog.Log(LOG_SYSTEM, "Couldn't open %s for writing.", filename.GetData());
		return;
	}
	
	sBSPHeader header;
	sBSPVisibilityHeader visHeader;

	visHeader.numClusters = clusters.GetNum();
	visHeader.bytesPerCluster = ((clusters.GetNum() + 7) & ~7) >> 3;

	fread(&header, sizeof(sBSPHeader), 1, fp);

	int visLen = visHeader.numClusters * visHeader.bytesPerCluster + sizeof(sBSPVisibilityHeader);

	// If file has visibility info already
	if(header.lumps[kVisData].length != visLen) {
		if(header.lumps[kVisData].length != 0) {
			g_CLog.Log(LOG_SYSTEM, "Found unusable space reserved for visibility.\nFor optimal results, recompile the .map file again.");
		}
		fseek(fp, 0, SEEK_END);
		header.lumps[kVisData].offset = ftell(fp);
		rewind(fp);

		header.lumps[kVisData].length = visLen;
		fwrite(&header, sizeof(sBSPHeader), 1, fp);
	}

	fseek(fp, header.lumps[kVisData].offset, SEEK_SET);
	fwrite(&visHeader, sizeof(sBSPVisibilityHeader), 1, fp);

	for(int i=0; i<clusters.GetNum(); i++)
		fwrite(clusters[i].visibility.GetData(), visHeader.bytesPerCluster, 1, fp);
	
	fclose(fp);
}


static inline void Pass1Redirector(int p, void *visCalc) {
	((CVisCalc*)visCalc)->Pass1(p);
}

static inline void Pass2Redirector(int p, void *visCalc) {
	((CVisCalc*)visCalc)->Pass2(p);
}

static inline void Pass3Redirector(int p, void *visCalc) {
	((CVisCalc*)visCalc)->Pass3(p);
}

// Compute final cluster visibility
static inline void Pass4Redirector(int c, void *visCalc) {
	((CVisCalc*)visCalc)->Pass4(c);
}

void CVisCalc::DoVis() {
	if(!clusters.GetNum()) {
		g_CLog.Log(LOG_SYSTEM, "DoVis: No clusters on map %s.", filename.GetData());
		return;
	}

#if 1 // Multithread
	g_CLog.Log(LOG_SYSTEM, "Allocation and infront Precomputation...");
	// The bitstrings are hell for cache coherence, but this seems to have little effect
	threads.RunOn(Pass1Redirector, this, 0, portals.GetNum());
	threads.WaitThreads();

	g_CLog.Log(LOG_SYSTEM, "Basic Flood...");
	threads.RunOn(Pass2Redirector, this, 0, portals.GetNum());
	threads.WaitThreads();

	g_CLog.Log(LOG_SYSTEM, "Visibility Flow...");
	threads.RunOn(Pass3Redirector, this, 0, portals.GetNum());
	threads.WaitThreads();

	g_CLog.Log(LOG_SYSTEM, "Cluster Visibility...");
	threads.RunOn(Pass4Redirector, this, 0, clusters.GetNum());
	threads.WaitThreads();
#else
	for(int i=0; i<portals.GetNum(); i++)
		Pass1(i);

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

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

	for(int i=0; i<clusters.GetNum(); i++)
		Pass4(i);
#endif
}

// *****   PASS 1    *****

void CVisCalc::ComputeInfront(sVisPortal *portal) {
	for(int i=0; i<portals.GetNum(); i++) {
		int sides[3];
		portals[i].winding->OnSide(&portal->plane, sides);

		portal->vInfront.SetCond(i, (bool)sides[P_FRONT]);
	}
}

void CVisCalc::Pass1(int ip) {
	sVisPortal *portal = &portals[ip];

	// Init the bitstrings
	portal->vInfront.Init(portals.GetNum());
	portal->vFlood.Init(portals.GetNum());
	portal->vVisible.Init(portals.GetNum());

	ComputeInfront(portal);
};

// *****   PASS 2    *****

void CVisCalc::FrontFlood(CStack<sVisPortal*>&  sInFront, int ic) {
	sCluster *cluster = &clusters[ic];
	
	for(int i=0; i<cluster->portals.GetNum(); i++) {
		int			j;
		int			iportal = cluster->portals[i];
		sVisPortal*	portal = &portals[iportal];
		sVisPortal*	srcPortal = sInFront[0];
		
		if(srcPortal->vFlood.Test( iportal ))
			continue;

		for(j=0; j<sInFront.GetNum(); j++) {
			if(!sInFront[j]->vInfront.Test(iportal))
				break;
		}

		if(j != sInFront.GetNum())
			continue;

		srcPortal->vFlood.Set( iportal );

		sInFront.Push( &portal );

		FrontFlood(sInFront, portal->otherCluster);

		sInFront.Pop();
	}
}

void CVisCalc::Pass2(int ip) {
	CStack<sVisPortal*>	sInFront;
	sVisPortal*			portal = &portals[ip];

	portal->vFlood.Set(ip);

	sInFront.Push(&portal);

	FrontFlood(sInFront, portal->otherCluster);

	// Infront data is no longer needed
	// Note: pass 1 bitstrings are reused in pass 3
	//portal->vInfront.Clear(portals.GetNum());
};

// *****   PASS 3    *****

inline int CVisCalc::MirrorPortalIndex(int i) {
	int halfN = portals.GetNum()>>1;
	return (i < halfN)? i+halfN : i-halfN;
}

// TrimPassage returns in ret the sub-area of dst that is visible from src through mid.
void CVisCalc::TrimPassage(CWinding *src, bool bFilpSrc, CWinding *mid, CWinding *dst, CWinding *ret) {
	CAlignedVec<vec4>&	srcPoints = *(src->GetPoints());
	
	*ret = *dst;

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

		vec4				v1 = srcPoints[(i+1)%srcPoints.GetNum()] - srcPoints[i];
		CAlignedVec<vec4>&	midPoints = *(mid->GetPoints());

		// Find a plane that has all points from src behind and all points from mid in front.
		for(int j=0; j<midPoints.GetNum(); j++) {

			vec4 v2 = midPoints[j] - srcPoints[i];
			sPlane plane = v2.cross3D(v1);

			if(plane.dot(plane) < EPSILON)
				continue;

			plane.normalize();
			plane.w = -plane.dot(srcPoints[i]);

			if(bFilpSrc)
				plane = reverse4(&plane);

			int k;
			for(k=0; k<midPoints.GetNum(); k++) {
				if(plane.side2(midPoints[k]) == P_BACK)
					break;
			}

			if(k != midPoints.GetNum())
				continue;

			ret->ChopWinding(&plane);
			break;
		}
	}
}

int CVisCalc::VisFlow(sVisFlow *vf) {
	sVisPortal* sPortal = vf->sPortal;
	sVisPortal* ePortal = vf->ePortal;
	int			ic = vf->stack.PeekTop()->portal->otherCluster;
	sCluster*	cluster = &clusters[ic];

	vf->visitedClusters.Set(ic);

	for(int j=0; j<cluster->portals.GetNum(); j++) {
		sVisPortal*	portal;
		int			ip = cluster->portals[j];
	
		if(ip == vf->MEPI) {
			return VF_VISIBLE;
		}

		if(!(sPortal->vFlood.Test(ip) && ePortal->vFlood.Test(MirrorPortalIndex(ip))))
			continue;

		portal = &portals[ip];

		if(vf->visitedClusters.Test(portal->otherCluster))
			continue;

		sVisFlowData *lastData = vf->stack.PeekTop();
		sVisFlowData *data = vf->stack.PushPeek();

		TrimPassage(
						sPortal->winding,
						vf->reverseSPW,
						portal->winding,
						&lastData->winding,
						&data->winding
					);

		if(data->winding.Empty()) {
			vf->stack.Pop();
			continue;
		}

		data->portal = portal;

		if(VisFlow(vf) == VF_VISIBLE) {
			// vf->stack.Pop(); // Stack is cleared in Pass3
			return VF_VISIBLE;
		}

		vf->stack.Pop();
	}

	return VF_HIDDEN;
}

// Perform full visibility testing between portal pairs
// A passage is the volume between 2 portals facing each other.
void CVisCalc::Pass3(int ip) {
	
	sVisPortal*		portal = &portals[ip];
	sVisFlow		vf;

	vf.visitedClusters.Init(clusters.GetNum());

	// Check each pair only once
	for(int iop = ip+1; iop<portals.GetNum(); iop++) {
		sVisPortal*		otherPortal = &portals[iop];

		//if(ip == 29 && iop == 39)
		//	int b = 2;

		if(portal->otherCluster == otherPortal->cluster) {
			portal->vVisible.Set(iop);
			otherPortal->vVisible.Set(ip);
			continue;
		}

		// Select only portals that could form a passage
		if(	portal->vFlood.Test( MirrorPortalIndex(iop) ) && 
			otherPortal->vFlood.Test( MirrorPortalIndex(ip) )	) {

			if(portal->otherCluster == otherPortal->otherCluster) {
				portal->vVisible.Set(iop);
				otherPortal->vVisible.Set(ip);
				continue;
			}

			

			vf.sPortal = portal;
			vf.ePortal = otherPortal;
			vf.visitedClusters.Clear();
			vf.stack.Clear();
			vf.MEPI = MirrorPortalIndex(iop);
			vf.reverseSPW = ip > (portals.GetNum()>>1);

			sVisFlowData*	data = vf.stack.PushPeek();
			data->winding = *otherPortal->winding;
			data->portal = portal;

			if(VisFlow(&vf) == VF_VISIBLE) {
				portal->vVisible.Set(iop);
				otherPortal->vVisible.Set(ip);
			}
		}
	}
}

// *****   PASS 4    *****

void CVisCalc::Pass4(int ic) {
	sCluster *cluster = &clusters[ic];

	cluster->visibility.Init(clusters.GetNum());

	for(int i=0; i<cluster->portals.GetNum(); i++) {
		sVisPortal *portal = &portals[cluster->portals[i]];

		for(int j=0; j<portals.GetNum(); j++) {
			if(portal->vVisible.Test(j)) {
				cluster->visibility.Set(portals[j].cluster);
			}
		}
	}
	cluster->visibility.Set(ic);
};