brush.cpp

BSP地形系统和光照贴图的技术详解

// Brush.cpp: implementation of the CBrush class.
//
//////////////////////////////////////////////////////////////////////

#include "d3dfont.h"
#include "Brush.h"

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CBrush::CBrush()
{
	m_pFaceList			= NULL;
	m_nTotalPlane		= 0;
	m_nFaceCount		= 0;
	m_nTotalPlane		= 0;
	m_nVertexCount		= 0;
	m_pTriangleIndex	= NULL;
	m_pVertex			= NULL;
	m_szName[0]			= '\0';
	m_pNext				= NULL;
	m_pPrev				= NULL;
	m_bUnited			= FALSE;

	m_nTCount			= 0;
	m_pTVtx				= NULL;

	m_nTFCount			= 0;
	m_pTIndex			= NULL;
	m_nTexture			= 0;
}

CBrush::~CBrush()
{
	if( m_pFaceList )
	{
		CFace * curr = NULL, * next = NULL;
		for(curr = m_pFaceList; curr ; curr = next)
		{
			next = curr->m_pNext;
			delete curr;
		}
	}
/*
	if( m_pNext )
	{
		m_pNext->Destroy();
	}
*/
}

//打开max 文件使用的时候，创建 brush时，使用的函数.
BOOL CBrush::InitBrush()
{
	for( int i = 0; i < m_nFaceCount ; i++ )
	{
		CFace *f = CFace::CreateFace();
		BSPVERTEX* ver = new BSPVERTEX[3];
		ver[0] = m_pVertex[m_pTriangleIndex[i]._0];
		ver[1] = m_pVertex[m_pTriangleIndex[i]._1];
		ver[2] = m_pVertex[m_pTriangleIndex[i]._2];
		
		ver[0].u = m_pTVtx[m_pTIndex[i]._0].x;
		ver[0].v = m_pTVtx[m_pTIndex[i]._0].z;
		ver[1].u = m_pTVtx[m_pTIndex[i]._1].x;
		ver[1].v = m_pTVtx[m_pTIndex[i]._1].z;
		ver[2].u = m_pTVtx[m_pTIndex[i]._2].x;
		ver[2].v = m_pTVtx[m_pTIndex[i]._2].z;

		f->m_vList = ver;
		f->m_nNum = 3;
		f->m_nTexture = m_nTexture;

		D3DXPLANE plane;
		D3DXPlaneFromPoints( &plane, &ver[0].pos, &ver[1].pos, &ver[2].pos );
		int res = FindSamePlane( plane );
		if( res == -1 )
		{
			m_Planes[m_nTotalPlane] = plane;
			f->m_nPlane = m_nTotalPlane++;
		}
		else
			f->m_nPlane = res;

		f->AddNext( m_pFaceList );
		m_pFaceList = f;
	}
	delete[] m_pVertex;
	delete[] m_pTriangleIndex;

	delete[] m_pTVtx;
	delete[] m_pTIndex;
	return TRUE;
}

BOOL CBrush::Create( D3DXVECTOR3 *pList, int n )
{
	/*
	for( int i = 0 ; i < n/3 ; i++ )
	{
		CFace* f = CFace::CreateFace();
		f->m_vList = &pList[i*3];
		f->m_nNum = 3;
		D3DXPLANE plane;
		D3DXPlaneFromPoints( &plane, &pList[i*3], &pList[i*3+1], &pList[i*3+2]);
		int res = FindSamePlane( plane );
		if( res == -1 )
		{
			m_Planes[m_nTotalPlane] = plane;
			f->m_nPlane = m_nTotalPlane++;
		}
		else
			f->m_nPlane = res;

		f->AddNext( m_pFaceList );
		m_pFaceList = f;
	}
	*/
	return TRUE;
}

BOOL CBrush::Create( CFace * pList )
{
	CFace * f = NULL;
	int nCount = 0;
	for( f = pList ; f ; f = f->m_pNext, nCount++ )
	{
		D3DXPLANE plane;
		D3DXPlaneFromPoints( &plane, &f->m_vList[0].pos, &f->m_vList[1].pos, &f->m_vList[2].pos );
		int res = FindSamePlane( plane );
		if( res == -1 )
		{
			m_Planes[m_nTotalPlane] = plane;
			f->m_nPlane = m_nTotalPlane++;
		}
		else
			f->m_nPlane = res;
	}
	m_pFaceList = pList;
	m_nFaceCount = nCount;
	return TRUE;
}

int CBrush::FindSamePlane(D3DXPLANE &plane)
{
	for( int i = 0 ; i < m_nTotalPlane ; i++ )
	{
		if( ComparePlane( m_Planes[i], plane ) )
			return i;
	}
	return -1;
}

BOOL CBrush::ComparePlane(D3DXPLANE &a, D3DXPLANE &b)
{
	if( a.a == b.a && a.b == b.b && a.c == b.c && a.d == b.d )
		return TRUE;
	return FALSE;
}

BOOL CBrush::Render( LPDIRECT3DDEVICE8 pd3dDevice, CD3DFont* pFont )
{
	CFace * f = NULL;
	for( f = m_pFaceList ; f ; f = f->m_pNext )
	{
		if( pFont )
		{
			for( int i = 0; i < f->m_nNum ; i++ )
			{
				D3DXMATRIX	mW, mV, mP, mO;
				pd3dDevice->GetTransform( D3DTS_WORLD, &mW );
				pd3dDevice->GetTransform( D3DTS_VIEW, &mV );
				pd3dDevice->GetTransform( D3DTS_PROJECTION, &mP );
				mO = mW * mV * mP;
				D3DXVECTOR3 vI = f->m_vList[i].pos;
				D3DXVECTOR3 vO;
				D3DXVec3TransformCoord( &vO, &vI, &mO );
				char	str[16];
				wsprintf( str, "( %d, %d, %d )", (int)f->m_vList[i].pos.x, (int)f->m_vList[i].pos.y,(int)f->m_vList[i].pos.z );
				pFont->DrawText(400.0f * (vO.x+1.0f), 600 - 300.0f * (vO.y+1.0f), 0xff000000, str );
			}
		}
		pd3dDevice->DrawPrimitiveUP( D3DPT_TRIANGLELIST, 1, f->m_vList, sizeof( BSPVERTEX )  );
	}

	if( pFont )
	{
		char s[16];
		wsprintf( s, "NUMBER OF FACE : %d", SizeOfFace( m_pFaceList ) );
		pFont->DrawText( 400, 10, 0xff000000, s );
	}

	if( m_pNext )
		m_pNext->Render( pd3dDevice, pFont );

	return TRUE;
}


CBrush* CBrush::Subtraction(CBrush *pB)
{
	CFace * bk_root = NULL;
	CFace * f = NULL, *front = NULL, *back = NULL, *pNext = NULL, *pCurr;
	int plane_split[10] = { -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 }, num_split = 0;
	
	f = pB->m_pFaceList;
	for( pCurr = f ; pCurr ; pCurr = f )
	{
		f = f->m_pNext;
		for( int i = 0 ; i < m_nTotalPlane ; i++ )
		{
			front = NULL;
			back = NULL;
			BOOL bSplit = FALSE;
			DivideFrontBack( m_Planes[i], pCurr, &front, &back, bSplit, FALSE, NULL );
			if( back )
			{
				if( bSplit )
				{
					BOOL bSearch = FALSE;
					for( int j = 0 ; j < num_split ; j++ )
					{
						if( plane_split[j] == i )
						{
							bSearch = TRUE;
							break;
						}
					}
					if( !bSearch )
					{
						plane_split[num_split++] = i;
					}
				}
				if( back->m_pNext )
					back->m_pNext->AddNext( bk_root );
				else
					back->AddNext( bk_root );
				bk_root = back;
			}
		}
	}

	int i_fr = SizeOfFace( bk_root );
	if( bk_root )
	{
		SplitContactFace( plane_split, num_split, &bk_root, pB );
		
		CBrush * pNew = new CBrush();
		pNew->Create( bk_root );
		return pNew;
	}

	return NULL;
}

//现有的 Union
CBrush* CBrush::operator + ( CBrush &pB )
{
	CFace * fr_root = NULL;
	CFace * f = NULL, *front = NULL, *back = NULL, *pNext = NULL, *pCurr;
	int plane_split[10] = { -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 }, num_split = 0;
	
	f = pB.m_pFaceList;
	for( pCurr = f ; pCurr ; pCurr = f )
	{
		f = f->m_pNext;
		for( int i = 0 ; i < m_nTotalPlane ; i++ )
		{
			front = NULL;
			back = NULL;
			BOOL bSplit = FALSE;
			DivideFrontBack( m_Planes[i], pCurr, &front, &back, bSplit, TRUE, NULL );

			if( bSplit )
			{
				BOOL bSearch = FALSE;
				for( int j = 0 ; j < num_split ; j++ )
				{
					if( plane_split[j] == i )
					{
						bSearch = TRUE;
						break;
					}
				}
				if( !bSearch )
				{
					plane_split[num_split++] = i;
				}
			}
			
			if( front )
			{
				//删除solid面的face.. 由于在倒∟形的BRUSH，solid的场所存在face 
				//必须制作为solid的BRUSH..
				
				if( front->m_pNext )
					front->m_pNext->AddNext( fr_root );
				else
					front->AddNext( fr_root );
				fr_root = front;
			}
		}
	}

	int i_fr = SizeOfFace( fr_root );
	if( fr_root )
	{
		SplitContactFace( plane_split, num_split, &fr_root, &pB );
		
		CBrush * pNew = new CBrush();
		pNew->Create( fr_root );
		return pNew;
	}
	return NULL;
}

//在brush2中删除进入内部的 brush1的 face. 
BOOL CBrush::DeleteInsideFace(CBrush &brush1, CBrush &brush2)
{
	CFace * new_root = NULL;
	CFace * face = NULL, *face1 = brush2.m_pFaceList;
	int nSplit[32], nCnt = 0;


	for( face = brush1.m_pFaceList; face ; face = face->m_pNext )
	{
		for( int i = 0 ; i < brush2.m_nTotalPlane ; i++ )
		{
			CFace * fr = NULL, * bk = NULL;
			if( TrySplit( &brush2, i, face, fr, bk ) )
			{
				face->m_bDelete = TRUE;
				for( CFace * f = fr ; f->m_pNext ; f = f->m_pNext )
					;
				f->m_pNext = new_root;
				new_root = fr;

				for( f = bk ; f->m_pNext ; f = f->m_pNext )
					;
				f->m_pNext = new_root;
				new_root = bk;

				nSplit[nCnt++] = i;
			}
		}
	}

	if( new_root )
	{
		CFace * curr = NULL;
		for( curr = brush1.m_pFaceList ; curr->m_pNext ; curr = curr->m_pNext )
			;
		curr->m_pNext = new_root;
		brush1.Create( brush1.m_pFaceList );
	}
	
	DeleteBackFace( brush2.m_Planes, brush2.m_nTotalPlane, brush1.m_pFaceList );
	
	return TRUE;
}

BOOL CBrush::DeleteBackFace(D3DXPLANE * planes, int num, CFace * &pList)
{
	CFace * curr = NULL;
	int res = 0, back = 0;
	for( curr = pList ; curr ; curr = curr->m_pNext )
	{
		back = 0;
		for( int i = 0 ; i < num ; i++ )
		{
			res = Classify( &planes[i], curr->m_vList, curr->m_nNum );
			switch( res )
			{
				case SIDE_ON:
				case SIDE_BACK:
					back++;
					break;
			}
		}
		if( back == num )
			curr->m_bDelete = TRUE;
	}
	return TRUE;
}


BOOL CBrush::TrySplit( CBrush* brush, int num, CFace * &f, CFace* &fr, CFace* &bk )
{
	BOOL bCheck = FALSE;
	CFace * curr = NULL;
	int res = Classify( &brush->m_Planes[num], f->m_vList, f->m_nNum );

	switch( res )
	{
		case SIDE_ON:
		case SIDE_FRONT:
		case SIDE_BACK:
			break;
		case SIDE_SPLIT:
			for( curr = brush->m_pFaceList ; curr ; curr = curr->m_pNext )
			{
				if( curr->m_nPlane == num )
				{
					if( IsColliedTriangles( f, curr ) )
					{
						bCheck = TRUE;
						break;
					}
				}
			}
			if( !bCheck )
				return FALSE;

			CFace * front = NULL, * back = NULL, * tmp = NULL;
			Split( &brush->m_Planes[num], f, &front, &back );
			
			if( !front && !back )
				break;
			f->m_bDelete = TRUE;

			fr = front;
			bk = back;
			return TRUE;
	}	

	return FALSE;
}

BOOL CBrush::SplitContactFace( int *pPlane, int nPlane, CFace** pList, CBrush * pBrush )
{
	CFace * cface = NULL;
	if( nPlane <= 0 )
		return FALSE;

	CFace * fr_root = NULL, * fr = NULL, * bk = NULL;

	for( int i = 0; i < nPlane ; i++ )
	{
		cface = NULL;
		for( cface = m_pFaceList ; cface ; cface = cface->m_pNext )
		{
			if( cface->m_nPlane == pPlane[i] )
			{
				for( int n = 0 ; n < pBrush->m_nTotalPlane ; n++ )
				{
					fr = NULL;
					bk = NULL;
					//Union函数丽的 DivideFrontBack函数第五参数是为了确认是否分割
					//而添加的参数.
					//如果是TRUE，在dividefrontback函数内，cface检查 
					//冲突状态.检查m_collision..
					BOOL bTmp = TRUE;
					DivideFrontBack( pBrush->m_Planes[n], cface, &fr, &bk, bTmp, TRUE, pBrush );
					if( fr )
					{
						if( fr->m_pNext )
							fr->m_pNext->AddNext( fr_root );
						else
							fr->AddNext( fr_root );
						fr_root = fr;
					}
				}
			}
			else
			{
				BOOL bCheck = FALSE;
				for( int cnt = 0 ; cnt < nPlane ; cnt++ )
				{
					if( cface->m_nPlane == pPlane[cnt] )
						bCheck = TRUE;
				}

				if( cface && !bCheck )
				{
					CFace * new_face = CFace::CreateFace();
					FaceCopy( cface, new_face );
					new_face->AddNext( fr_root );
					fr_root = new_face;
				}
			}
		}
	}
	
	CFace * tail = NULL;
	for( tail = fr_root ; tail->m_pNext ; tail = tail->m_pNext )
		;
	tail->AddNext( *pList );
	*pList = fr_root;
	return TRUE;
}

//如果值写入pBrush，在SplitContactFace中调用.
//如果NULL写入pBrush，在Union中调用第一个函数

BOOL CBrush::DivideFrontBack(D3DXPLANE &plane, CFace *f, CFace **fr, CFace **bk, BOOL &bSplit, BOOL bIsUnion, CBrush* pBrush )
{
	CFace * nf = CFace::CreateFace();
	FaceCopy( f, nf );
	int res = Classify( &plane, nf->m_vList, nf->m_nNum );

//	相对面的Normal相反的情况..(相互附贴)使用的参数
	D3DXVECTOR3 plane_normal( plane.a, plane.b, plane.c );
	D3DXVECTOR3 vBA, vCA;
	D3DXVECTOR3 vCross, face_normal;

	float dot = 0;


	switch( res )
	{
		case SIDE_ON:
			if( bIsUnion )
			{
/*
				nf->AddNext( *bk );
				*bk = nf;
		%Union的情况下，由于没有必要，为了防止 memory leak..
*/
				delete nf;
			}
			else
			{
				nf->AddNext( *fr );
				*fr = nf;
			}

//	相对面的Normal相反的情况..(相互附贴)
//	将TRUEb代入Split参数，以后计算时需要
			vBA = f->m_vList[1].pos - f->m_vList[0].pos;
			vCA = f->m_vList[2].pos - f->m_vList[0].pos;
			D3DXVec3Cross( &vCross, &vBA, &vCA );
			D3DXVec3Normalize( &face_normal, &vCross );
			
			dot = D3DXVec3Dot( &plane_normal, &face_normal );
			
			if( dot < 0 )
				bSplit = TRUE;

			break;
		case SIDE_FRONT:
			nf->AddNext( *fr );
			*fr = nf;
			break;
		case SIDE_BACK:
			if( bIsUnion )
			{
/*
		%Union的情况下，由于没有必要，为了防止 memory leak..
				nf->AddNext( *bk );
				*bk = nf;
		%%% memory leak 规瘤甫 困秦 %%%
*/
				delete nf;
			}
			break;
		case SIDE_SPLIT:
			CFace * front = NULL, * back = NULL, * pFace = NULL;
//bSplit代入 TRUE，通过 f或者复制的 nf检查是否有冲突状态..
//如果不是冲突状态，清除nf，返回 FALSE.
			if( bSplit )
			{
				if( !nf->m_bCollision )
				{
					nf->AddNext( *fr );
					*fr = nf;
					return FALSE;
				}
				else
				{
					delete nf;
				}
			}
///////////// 防止memory leak  /////////
//清除的理由: split 时，没有使用复制件nf，直接使用 f分割
//分割面生成了新的 face，复制件就不需要了.
			else
			{
				delete nf;
			}

//具有brush的 face中，检查相同平面上的face和对象face两个三角形是否处于
//冲突状态，如果不是冲突，删除nf，返回 FALSE.
//如果冲突，将face的主参数 m_bCollision设为 TRUE， 
//进行split.
			BOOL bColl = FALSE;
			if( pBrush == NULL )
			{
				for( pFace = m_pFaceList ; pFace ; pFace = pFace->m_pNext )
				{
					if( m_Planes[pFace->m_nPlane] == plane )
					{
	//f具有一个cface，由于被coding，就没有制作for的必要了.
						if( IsColliedTriangles( pFace, f ) )
						{
							pFace->m_bCollision = TRUE;
							f->m_bCollision = TRUE;
							bColl = TRUE;
						}
					}
				}
				if( !bColl )
				{
					return FALSE;
				}
			}// end if( pBrush == NULL ) Union的情况下，只在第一种情况下使用.

			Split( &plane, f, &front, &back );
			if( !front && !back )
				break;
			if( front->m_pNext )
			{
				if( bIsUnion )
				{
					front->m_pNext->AddNext( *fr );
					*fr = front;
				}
				else
				{
					front->m_pNext->AddNext( *bk );
					*bk = front;
				}
			}
			else 
			{
				if( bIsUnion )
				{
					front->AddNext( *fr );
					*fr = front;
				}
				else
				{
					front->AddNext( *bk );
					*bk = front;
				}
			}
			if( back->m_pNext )
			{
				if( bIsUnion )
				{
/*
		%Union的情况下，由于没有必要，为了防止 memory leak..
					back->m_pNext->AddNext( *bk );
					*bk = back;
*/
					delete back->m_pNext;
					delete back;
				}
				else
				{
					back->m_pNext->AddNext( *fr );
					*fr = back;
				}
			}
			else
			{
				if( bIsUnion )
				{
/*
		%Union的情况下，由于没有必要，为了防止 memory leak..
					back->AddNext( *bk );
					*bk = back;
*/
					delete back;
				}
				else
				{
					back->AddNext( *fr );
					*fr = back;
				}
			}
			bSplit = TRUE;
			break;
	}	
	return TRUE;
}

BOOL CBrush::FaceCopy(CFace *pOrig, CFace *pCopy)
{
	pCopy->m_nNum = pOrig->m_nNum;
	pCopy->m_bCollision = pOrig->m_bCollision;
	BSPVERTEX * copy = new BSPVERTEX[pOrig->m_nNum];
	for( int i = 0; i < pOrig->m_nNum ; i++ )
	{
		copy[i] = pOrig->m_vList[i];
	}
	pCopy->m_vList = copy;
	pCopy->m_nTexture = pOrig->m_nTexture;
	pCopy->m_nLightMap = pOrig->m_nLightMap;
	return TRUE;
}

int CBrush::Classify( D3DXPLANE *plane, BSPVERTEX *v, int num )
{
	int front = 0, back = 0, on = 0;
	float res = 0;

	for (int cnt = 0; cnt < num; cnt++)
	{
		res = D3DXPlaneDotCoord( plane, &v[cnt].pos );

		if ( res > EPSILON )
			front++;
		else if ( res < -EPSILON )
			back++;
		else
		{