bsptree.h

国外网游源码....除工具源码缺少之外,其余程序都全...至于,什么游戏,因为国内还没有,所以找不到测试

// BspTree.h: interface for the CBspTree class.
//
//////////////////////////////////////////////////////////////////////

#if !defined(AFX_BSPTREE_H__DD6D73C1_D131_4452_AEE6_BE2981BF306E__INCLUDED_)
#define AFX_BSPTREE_H__DD6D73C1_D131_4452_AEE6_BE2981BF306E__INCLUDED_

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000

#define Z_EPSILON		0.0001f

#define BSP_EPSILON		Z_EPSILON
#define BSP_BOGUS		99999

#define IS_IN_RANGE(value,r0,r1) (( ((r0) <= (value)) && ((value) <= (r1)) ) ? 1 : 0)

struct TRIINDEX
{
	WORD _0, _1, _2;
};

//enum LOCATION { FRONT, BACK, ON, SPLIT };

class CClassifyByPlane
{
public:
	enum LOCATION { FRONT, BACK, ON, SPLIT };
	static LOCATION WhereIsVertex( D3DXPLANE* pPlane, D3DXVECTOR3* pV )
	{
		float d;
		d = D3DXPlaneDotCoord( pPlane, pV );
		if( d > BSP_EPSILON ) return CClassifyByPlane::FRONT;
		if( d < -BSP_EPSILON ) return CClassifyByPlane::BACK ;
		
		return CClassifyByPlane::ON;
	}

//	static LOCATION WhereIsFace( D3DXPLANE* pPlane, D3DXVECTOR3* pV, int nVertCount )
//	LOCATION WhereIsFace( D3DXPLANE* pPlane, D3DXVECTOR3* pV, int nVertCount )
//	{
//		int f = 0, b = 0, o = 0;
//		float d;
//		for( int i = 0 ; i < nVertCount ; i++ )
//		{
//			d = D3DXPlaneDotCoord( pPlane, &((pV+i)->p) );
//			if( d > BSP_EPSILON ) f++;
//			else
//			if( d < -BSP_EPSILON ) b++;
//			else
//			{ f++; b++; o++; }
//		}
//		
//		if( o == nVertCount ) return CClassifyByPlane::ON;
//		if( f == nVertCount ) return CClassifyByPlane::FRONT;
//		if( b == nVertCount ) return CClassifyByPlane::BACK;
//		
//		return CClassifyByPlane::SPLIT;

//		if( o == nVertCount ) return ON;
//		if( f == nVertCount ) return FRONT;
//		if( b == nVertCount ) return BACK;
//		
//		return SPLIT;
//	}

	static LOCATION WhereIsFace( D3DXPLANE* pPlane, D3DXVECTOR3* pV, int nVertCount )
	{
		int f = 0, b = 0, o = 0;
		float d;
//		static int f, b, o;
//		static float d;
//		f = 0, b = 0, o = 0;
		for( int i = 0 ; i < nVertCount ; i++ )
		{
			d = D3DXPlaneDotCoord( pPlane, (pV+i) );
			if( d > BSP_EPSILON ) f++;
			else if( d < -BSP_EPSILON ) b++;
			else { f++; b++; o++; }
		}
		
		if( f == nVertCount ) return CClassifyByPlane::FRONT;
		if( b == nVertCount ) return CClassifyByPlane::BACK;
		if( o == nVertCount ) return CClassifyByPlane::ON;
		
		return CClassifyByPlane::SPLIT;
	}

	static LOCATION WhereIsPolygon( D3DXPLANE* pPlane, D3DXVECTOR3* pV0 )
	{
		return WhereIsFace( pPlane, pV0, 3 );
	}
};

class CBspFace
{
public:
	CBspFace();
	~CBspFace()	{ Destroy(); }

	BOOL			MakePlane( D3DXVECTOR3* pV, int n );
	void			AddTail( CBspFace* p ) { if( m_pNext ) m_pNext->AddTail( p ); else m_pNext = p; }
	void			AddNext( CBspFace* p ) { m_pNext = p; }
	CBspFace*		GetNext() { return m_pNext; }
	D3DXVECTOR3*	GetVerts() { return m_pVerts; }
	DWORD			GetVertCount() { return m_nVertCount; }
	BOOL			GetUsed() { return m_bUsed; }
	void			SetUsed( BOOL b ) { m_bUsed = b; }
	D3DXPLANE*		GetPlane() { return &m_plane; }

private:
	void			Destroy();

private:
	CBspFace*		m_pNext;
	BOOL			m_bUsed;
	D3DXVECTOR3*	m_pVerts;
	DWORD			m_nVertCount;
	D3DXPLANE		m_plane;
};

class CBspNode
{
public:
	enum	{ NODETYPE_NODE, NODETYPE_LEAF, NODETYPE_SOLIDLEAF };
	enum	{ NODE_FRONT = 0, NODE_BACK = 1 };

public:
//	class CPortal  
//	{
//	public:
//		CPortal*		m_pNext[2];
//		CBspNode*		m_pNode[2];
//		CWinding*		m_pWinding;
//		D3DXPLANE		m_plane;
//		BOOL			m_bRender;
//		CPortal*		m_visPortals[MAX_PORTALS_ON_LEAF];
//		int				m_nVisCnt;
//		int				m_nFaceCnt;
//		CFace**			m_ppFaceList;
//
//	public:
//		CPortal();
//		virtual ~CPortal();
//
//		void		AddPortalToNodes( CBspNode *front, CBspNode *back );
//		void		Render( LPDIRECT3DDEVICE8 pd3dDevice );
//		void		RemovePortalFromNode ( CBspNode *l );
//	};
private:
	DWORD			m_nNodeType;
	D3DXVECTOR3		m_vMin;
	D3DXVECTOR3		m_vMax;
	D3DXPLANE		m_plane;
	CBspFace*		m_pFaces;
	CBspNode*		m_pNode[2];	// NODE_FRONT:front, NODE_BACK:back
private:
	void			Destroy();
public:
	CBspNode();
	~CBspNode()		{ Destroy(); }

	void			SetFrontNode( CBspNode* pNode ) { m_pNode[NODE_FRONT] = pNode; }
	void			SetBackNode( CBspNode* pNode ) { m_pNode[NODE_BACK] = pNode; }
	CBspNode*		GetFrontNode() { return m_pNode[NODE_FRONT]; }
	CBspNode*		GetBackNode() { return m_pNode[NODE_BACK]; }
	void			SetNodeType( DWORD n ) { m_nNodeType = n; }
	DWORD			GetNodeType() { return m_nNodeType; }

	BOOL			DetectCollision( D3DXVECTOR3* pV );
	BOOL			IsSolid() { return (m_nNodeType == NODETYPE_SOLIDLEAF); }
	BOOL			IsLeaf() { return (m_nNodeType == NODETYPE_LEAF); }
	D3DXVECTOR3*	GetMin() { return &m_vMin; }
	D3DXVECTOR3*	GetMax() { return &m_vMax; }
	D3DXPLANE*		GetPlane() { return &m_plane; }
	CBspFace*		GetFaces() { return m_pFaces; }
	void			SetFaces( CBspFace* p ) { m_pFaces = p; }
//	void			SetFaceList( CBspFace* pFaces ) { m_pFaces = pFaces; }

	void			Render( LPDIRECT3DDEVICE9 pDev );
};

class CBspTree  
{
public:
	CBspTree();
	~CBspTree()	{ Destroy(); }

private:
	BOOL			CompareNormal( D3DXVECTOR3* pvA0, D3DXVECTOR3* pvA1, D3DXVECTOR3* pvA2, 
									D3DXVECTOR3* pvB0, D3DXVECTOR3* pvB1, D3DXVECTOR3* pvB2 );
	BOOL			IntersectLine( D3DXVECTOR3* pvOut, D3DXPLANE* pPlane, D3DXVECTOR3* pvA, D3DXVECTOR3* pvB );
	void			Split( D3DXPLANE* pPlane, CBspFace* pFaces, CBspFace** a , CBspFace** b );
	void			MakeLeaf( CBspNode* pLeaf );
	int				GetFaceNodeCount( CBspFace* pFace );
	void			GetSortedFaceList( D3DXPLANE* pPlane, CBspFace* pFaces, CBspFace** fr , CBspFace** bk );
	CBspFace*		FindBestSplitter( CBspFace* pList );
	void			SubDivide( CBspNode* p );
	BOOL			CreateFaceList();
	void			Destroy();

public:
	void			AddTriangle( const D3DXVECTOR3& v1, const D3DXVECTOR3& v2, const D3DXVECTOR3& v3 );
	void			BuildBspTree();
	BOOL			DetectCollision( D3DXVECTOR3* pV );

private:
	DWORD			m_nVertCount;
	DWORD			m_nFaceCount;
	D3DXVECTOR3*	m_pVerts;
	TRIINDEX*		m_pIndices;
	CBspFace*		m_pRootFace;
	CBspNode*		m_pRootNode;


};

#endif // !defined(AFX_BSPTREE_H__DD6D73C1_D131_4452_AEE6_BE2981BF306E__INCLUDED_)