bspconv.h

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

#pragma once

// This file contains declarations for the BSP tree structures and other misc.
// classes that are too small to be given their own .cpp :)

// FIXME: Too messy!

#include "bsp.h"

#include "map.h"
#include "brush.h"
#include "math.h"
#include "vector.h"
#include "vector.h"
#include "memalloc.h"
#include "log.h"

// BSP Tree

#define	NODE_REACHABLE	BIT(0)
#define NODE_OPAQUE		BIT(1)

enum {
	T_SPLITNODE,
	T_LEAF,
	T_HEADNODE
};

__interface IBSPTreeVisitor;
class _CBSPBrush;
class _CBSPFace;
class _CBSPLeafNode;
class CBSPTreeDeallocator;

class _CBSPNode : public CMemObj {
public:
	// visitor
	virtual void	Traverse(IBSPTreeVisitor *v) = 0;
	virtual void	Visit(IBSPTreeVisitor *v) = 0;
	virtual int		GetType() = 0;

	vec4			min;
	vec4			max;

	// Per node data used by various algorithms
	CVector<int>	faces;
	CVector<int>	portals;
	CVector<int>	brushes;
};

class _CBSPTree : public _CBSPNode {
public:
						~_CBSPTree();
	void				Traverse(IBSPTreeVisitor *v);
	void				Visit(IBSPTreeVisitor *v);
	int					GetType() { return T_HEADNODE; }

	bool				BuildBSP(CMapLoader* map);
	_CBSPNode*			AllocTree();
	_CBSPLeafNode*		FindLeaf(vec4 *pos);

	_CBSPNode*			tree;

	CVector<_CBSPBrush*> brushes;
	CVector<_CBSPFace*> faces;

	CMapLoader*			srcMap;
};

class _CBSPSplitNode : public _CBSPNode {
public:
	void				Traverse(IBSPTreeVisitor *v);
	void				Visit(IBSPTreeVisitor *v);
	int					GetType() { return T_SPLITNODE; }

	_CBSPNode*			children[2];
	int					plane;
};

class _CBSPFace;

class _CBSPLeafNode : public _CBSPNode {
public:
						_CBSPLeafNode() : flags(0) {}

	void				Traverse(IBSPTreeVisitor *v);
	void				Visit(IBSPTreeVisitor *v);
	int					GetType() { return T_LEAF; }

	int					flags;
	int					cluster;

	CVector<_CBSPBrush*>	brushes;

	CVector<_CBSPFace*>	faces;
};

// Visitor
__interface IBSPTreeVisitor {
	void VisitNodeBegin(_CBSPSplitNode *n);
	void VisitNodeEnd(_CBSPSplitNode *n);
	void VisitLeaf(_CBSPLeafNode *l);
};

inline void _CBSPTree::Traverse(IBSPTreeVisitor *v) {
	tree->Traverse(v);
}

inline void _CBSPTree::Visit(IBSPTreeVisitor *v) {
	tree->Visit(v);
}

class CBSPLeafLocator : public IBSPTreeVisitor {
public:
	void			VisitNodeBegin(_CBSPSplitNode *n);
	void			VisitNodeEnd(_CBSPSplitNode *n) {};
	void			VisitLeaf(_CBSPLeafNode *l);

	_CBSPLeafNode*	Locate(_CBSPTree *tree, vec4* pos);
private:
	vec4*			pos;
	_CBSPLeafNode*	ret;
};

inline void CBSPLeafLocator::VisitNodeBegin(_CBSPSplitNode *n) {
	sPlane*	plane = g_curMap->GetPlane(n->plane);
	n->children[ pos->side2(*plane) ]->Visit(this);
}

inline void CBSPLeafLocator::VisitLeaf(_CBSPLeafNode *l) {
	ret = l;
}

inline _CBSPLeafNode* CBSPLeafLocator::Locate(_CBSPTree *tree, vec4* p) {
	pos = p;
	tree->tree->Visit(this);
	return ret;
}

inline _CBSPLeafNode* _CBSPTree::FindLeaf(vec4 *pos) {
	CBSPLeafLocator ll;
	return ll.Locate(this, pos);
}


inline _CBSPNode* _CBSPTree::AllocTree() {
	tree = new _CBSPSplitNode;
	return tree;
}
inline void _CBSPSplitNode::Traverse(IBSPTreeVisitor *v) {
	v->VisitNodeBegin(this);
	children[0]->Traverse(v);
	children[1]->Traverse(v);
	v->VisitNodeEnd(this);
}

inline void _CBSPSplitNode::Visit(IBSPTreeVisitor *v) {
	v->VisitNodeBegin(this);
}

inline void _CBSPLeafNode::Traverse(IBSPTreeVisitor *v) {
	v->VisitLeaf(this);
}

inline void _CBSPLeafNode::Visit(IBSPTreeVisitor *v) {
	v->VisitLeaf(this);
}

class CBSPFilter {
public:
	void	FilterBrushesAndMarkOpaqueNodes(_CBSPTree *tree);
	bool	FilterFacesAndMarkLeaves(_CBSPTree *tree, bool doFilter);
};

#include <map>

class CBSPEmitter : public IBSPTreeVisitor {
public:
	void VisitNodeBegin(_CBSPSplitNode *n);
	void VisitNodeEnd(_CBSPSplitNode *n) {};
	void VisitLeaf(_CBSPLeafNode *l);

	void EmitWorldEntity(CBSP* bsp, _CBSPTree* tree);
	void EmitEntity(_CBSPLeafNode* leaf);
	void Finish();
private:
	int			AllocLeafSurface(_CBSPFace *face);
	int			AllocLeafBrush(_CBSPBrush *brush);

	struct index {
		index() { i = -1; }
		index(int index) { i = index; }
		index operator=(int index) { i = index; return *this; }
		operator int() {return i;}
		
		int i;
	};

	std::map<_CBSPFace*, index>		faceIndices;
	std::map<_CBSPBrush*, index>	brushIndices;

	CBSP*		bsp;
	_CBSPTree*	tree;

	// intercall parameters:
	int			child;
	int			parent;
};

class CBSPTreeDeallocator : public IBSPTreeVisitor {
public:
	// visitor interface
	void			VisitNodeBegin(_CBSPSplitNode *n) {};
	void			VisitNodeEnd(_CBSPSplitNode *n);
	void			VisitLeaf(_CBSPLeafNode *l){};

	void			Deallocate(_CBSPTree *tree);
};

inline void CBSPTreeDeallocator::Deallocate(_CBSPTree *tree) {
	tree->tree->Traverse(this);
	delete tree->tree;
}

inline void CBSPTreeDeallocator::VisitNodeEnd(_CBSPSplitNode *n) {
	delete n->children[0];
	delete n->children[1];
}

_CBSPLeafNode *CreateSubmodel(CMapEntity* entity);
bool CompileMap(CBSP *bsp, CMapLoader *map);