bspmanager.cpp

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

	m_billboard.v[1].pos = D3DXVECTOR3( 2, 2, 0 );
	m_billboard.v[1].u = 1.f;
	m_billboard.v[1].v = 0.f;

	m_billboard.v[2].pos = D3DXVECTOR3( 2, -2, 0 );
	m_billboard.v[2].u = 1.f;
	m_billboard.v[2].v = 1.f;

	m_billboard.v[3].pos = D3DXVECTOR3( -2, -2, 0 );
	m_billboard.v[3].u = 0.f;
	m_billboard.v[3].v = 1.f;

	D3DXCreateTextureFromFile( pd3dDevice, "texture\\billboardlight.tga", &m_billboard.t );
	
	LoadThings( pd3dDevice );
	ParseMaxFile( szFileName );
	SetTexture( pd3dDevice );
	InitBrushs();
	CSGBuild();

	CBspNode* b = new CBspNode();
	b->m_pFaceList = m_pCSGBrushs->m_pFaceList;
	m_pCSGBrushs->m_pFaceList = NULL;
	

	m_pBspRoot = b;
	SubDivide( m_pBspRoot );
	
	PortalizeWorld();
	ClearOutsideFace();
	FreeAllPortals( m_pBspRoot );

	delete m_pBspRoot;

	m_pBspRoot = new CBspNode();
	m_pBspRoot->m_pFaceList = m_pNewFaceRoot;

	CreateLightMap( pd3dDevice );

	SubDivide( m_pBspRoot );
	PortalizeWorld();

	SetPortals();
	
	TryPVS();

	
	
	delete[] m_pBrushs;
	delete m_pCSGBrushs;
	m_pBrushs = NULL;
	m_pCSGBrushs = NULL;
	return b;
}

void CBspManager::SetPortals()
{
	SetValidPortals( m_pBspRoot );
	m_ppPortals = new CBspNode::CPortal*[m_nPortalCnt*2];
	m_nPortalCnt = 0;
	LinkPortals( m_pBspRoot );

	int count = 0;

	for( int i = 0 ; i < m_nPortalCnt ; i++ )
	{
		if( m_ppPortals[i]->m_pNode[1]->m_pPortals != m_ppPortals[i] )
		{
			BOOL check = FALSE;
			CBspNode::CPortal* portal = m_ppPortals[i]->m_pNode[1]->m_pPortals, *prev = NULL;
			for( ; portal ; portal = portal->m_pNext[0] )
			{
				prev = portal;
				if( portal == m_ppPortals[i] )
				{
					check = TRUE;
					break;
				}
			}
			if( !check )
			{
				portal = new CBspNode::CPortal();
				portal->m_pNode[0] = m_ppPortals[i]->m_pNode[1];
				portal->m_pNode[1] = m_ppPortals[i]->m_pNode[0];
				CWinding* w = new CWinding();
				w->n = m_ppPortals[i]->m_pWinding->n;
				for( int j = 0 ; j < w->n; j++ )
					w->vPoint[j] = m_ppPortals[i]->m_pWinding->vPoint[w->n-1-j];
				portal->m_pWinding = w;

				portal->m_plane = D3DXPLANE( 0.f - m_ppPortals[i]->m_plane.a, 
											 0.f - m_ppPortals[i]->m_plane.b,
											 0.f - m_ppPortals[i]->m_plane.c,
											 -m_ppPortals[i]->m_plane.d );
				
				if( prev )
					prev->m_pNext[0] = portal;
				else
					m_ppPortals[i]->m_pNode[1]->m_pPortals = portal;
				m_ppPortals[m_nPortalCnt+count] = portal;
				count++;
			}
		}
	}
	m_nPortalCnt = m_nPortalCnt + count;
}

CBspNode* CBspManager::GetLeafIncludeWinding( CWinding* winding, BOOL bFront )
{
	return NULL;
}

void CBspManager::LinkPortals( CBspNode* node )
{
	CBspNode::CPortal	*p, *nextp, *portals = NULL, * copy = NULL;
	int side = 0;

	if ( !node->m_bIsLeaf )
	{
		LinkPortals ( node->m_pFront );
		LinkPortals ( node->m_pBack );
	}
	
	if( node->m_bIsLeaf )
		for (p=node->m_pPortals ; p ; p=nextp)
		{
			if (p->m_pNode[0] == node)
				side = 0;
			else
				side = 1;
			nextp = p->m_pNext[side];

			m_ppPortals[m_nPortalCnt++] = p;
		}
}

void CBspManager::SetValidPortals( CBspNode * node )
{
	CBspNode::CPortal	*p, *nextp, *portals = NULL, * copy = NULL;
	int side = 0;

	if ( !node->m_bIsLeaf )
	{
		SetValidPortals ( node->m_pFront );
		SetValidPortals ( node->m_pBack );
	}
	
	for (p=node->m_pPortals ; p ; p=nextp)
	{
		if (p->m_pNode[0] == node)
			side = 0;
		else
			side = 1;

		nextp = p->m_pNext[side];
		
		if( p->m_bRender )
		{
			m_nPortalCnt++;
			copy = new CBspNode::CPortal();
			copy->m_plane = p->m_plane;
			copy->m_pNode[0] = p->m_pNode[0];
			copy->m_pNode[1] = p->m_pNode[1];
			copy->m_pWinding = new CWinding();
			copy->m_pWinding->n = p->m_pWinding->n;
			for( int i = 0 ; i < copy->m_pWinding->n ; i++ )
			{
				copy->m_pWinding->vPoint[i] = p->m_pWinding->vPoint[i];
			}
			
			if( portals )
			{
				if ( portals->m_pNode[0] == node )
					side = 0;
				else
					side = 1;
				copy->m_pNext[side] = portals;
				portals = copy;
			}
			else
			{
				copy->m_pNext[0] = portals;
				copy->m_pNext[1] = portals;
				portals = copy;
			}
		}
	}
	if( node->m_bIsLeaf )
	{
		FreeAllPortals( node );

		node->m_pPortals = portals;
	}
}

void CBspManager::SubDivide(CBspNode *pRoot)
{
	pRoot->m_pTXData = m_pTXData;

	CBspNode * front_node = NULL;
	CBspNode * back_node = NULL;

	CFace* bestface = FindBestSplitter( pRoot->m_pFaceList );
	
	if ( bestface == NULL )
	{
		MakeLeaf( pRoot );
		return;
	}

	pRoot->m_plane = m_pCSGBrushs->m_Planes[bestface->m_nPlane];	

	CFace * fr = NULL;
	CFace * bk = NULL;
	
	GetSortedFaceList ( &m_pCSGBrushs->m_Planes[bestface->m_nPlane] , pRoot->m_pFaceList, &fr , &bk );
	int i_fr = SizeOfFace(fr);
	int i_bk = SizeOfFace(bk);

	if ( bk )
	{
		back_node = new CBspNode();
		back_node->SetFaceList( bk );
		pRoot->SetBackNode( back_node );
		SubDivide( pRoot->m_pBack );
	}
	else
	{
		back_node = new CBspNode();
		back_node->SetFaceList( NULL );
		back_node->m_bIsSolid = TRUE;
		back_node->m_bIsLeaf = TRUE;
		pRoot->SetBackNode( back_node );
	}

	if ( fr )
	{
		front_node = new CBspNode();
		front_node->SetFaceList( fr );
		pRoot->SetFrontNode( front_node );
		SubDivide( pRoot->m_pFront );
	}

}

CFace* CBspManager::FindBestSplitter( CFace *pList )
{

	CFace *cface = NULL;
	CFace *curr = NULL;
	CFace *best = NULL; // current best plane
	float bscore = BSP_BOGUS;
	float score = BSP_BOGUS;
	int res = 0;

	// no list
	if (!pList)
		return 0;

	for ( cface = pList; cface; cface = cface->m_pNext )
	{
		if ( cface->m_bUsed )
			continue;

		int f = 0, b = 0, s = 0, o = 0;

		for ( curr = pList; curr; curr = curr->m_pNext )      
		{
			// this face has been used as a split plane, don't consider
			if (curr->m_bUsed)
				continue;

			// don't compare cface to cface
			if (curr != cface)
			{
				res = Classify(&m_pCSGBrushs->m_Planes[cface->m_nPlane], curr->m_vList, curr->m_nNum );
				if (res == FACE_FRONT)
					f++;
				else if (res == FACE_BACK)
					b++;
				else if (res == FACE_ON)
					o++;
				else
					s++;
			}
		}

		// calculate a score for the current plane, this can change
		score = (float)((2*s) + abs(f - b) + o); 
//		score = abs(f - b);
		// this plane is better than what we have, make it the best
		if (score && score < bscore) 
		{
			 bscore = score;
			 best = cface;
		}
	}

	return best;
}

//front back区分排列
void CBspManager::GetSortedFaceList( D3DXPLANE *plane, CFace *f, CFace **fr, CFace **bk )
{

	CFace * pFront = NULL, * pBack = NULL, * pNext = NULL;
	CFace * pCurrentFace = NULL;
	if( !f )
	{
		*fr = NULL;
		*bk = NULL;
		return;
	}

	for( pCurrentFace = f ; pCurrentFace ; pCurrentFace = pNext )
	{
		pNext = pCurrentFace->m_pNext;
		D3DXVECTOR3 planeNormal( plane->a, plane->b, plane->c );
		D3DXVECTOR3 currentNormal( m_pCSGBrushs->m_Planes[pCurrentFace->m_nPlane].a,  m_pCSGBrushs->m_Planes[pCurrentFace->m_nPlane].b,  m_pCSGBrushs->m_Planes[pCurrentFace->m_nPlane].c );
		float val;
		int res = Classify( plane, pCurrentFace->m_vList, pCurrentFace->m_nNum );
		switch( res )
		{
			case FACE_FRONT:
				pCurrentFace->AddNext( pFront );
				pFront = pCurrentFace;
				break;

			case FACE_BACK:
				pCurrentFace->AddNext( pBack );
				pBack = pCurrentFace;
				break;

			case FACE_ON:
				pCurrentFace->m_bUsed = TRUE;

				val = D3DXVec3Dot( &planeNormal, &currentNormal );
				if( val >= 0 )
				{
					pCurrentFace->AddNext( pFront );
					pFront = pCurrentFace;
				}
				else
				{
					pCurrentFace->AddNext( pBack );
					pBack = pCurrentFace;
				}
				break;

			case FACE_SPLIT:
				CFace * front = NULL, * back = NULL;
				Split( plane, pCurrentFace, &front, &back );
				if( !front && !back )
					break;
				if( front->m_pNext )
				{
					front->m_pNext->AddNext( pFront );
					pFront = front;
				}
				else 
				{
					front->AddNext( pFront );
					pFront = front;
				}
				if( back->m_pNext )
				{
					back->m_pNext->AddNext( pBack );
					pBack = back;
				}
				else
				{
					back->AddNext( pBack );
					pBack = back;
				}
				break;
		}
	}
	*fr = pFront;
	*bk = pBack;

}

int CBspManager::SizeOfFace ( CFace * pFace )
{
	CFace * temp = pFace;
	int i=0;
	while(temp)
	{
		i++;
		temp = temp->m_pNext;
	}
	return i;
}

int CBspManager::ClassifyPoint( D3DXPLANE * plane, D3DXVECTOR3 * v )
{
	float res = D3DXPlaneDotCoord( plane, v);
	if( res > EPSILON )
		return FACE_FRONT;
	else if( res < -EPSILON )
		return FACE_BACK;
	else if( res < EPSILON && res > -EPSILON )
		return FACE_ON;
	return FACE_SPLIT;
}

int CBspManager::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
		{
			front++;
			back++;
			on++;
		}
	}
   
	if (on == num)
		return FACE_ON;
	else if (front == num)
		return FACE_FRONT;
	else if (back == num)
		return FACE_BACK;
	else
		return FACE_SPLIT;
}

void CBspManager::MakeLeaf(CBspNode * leaf)
{
	leaf->m_bIsLeaf = TRUE;
	CFace * faceRoot = leaf->m_pFaceList;
	CFace * tf;
	for ( tf = faceRoot; tf; tf = tf->m_pNext )
	{
		int i;
		for ( i=0; i < tf->m_nNum; i++)
		{
			if ( tf->m_vList[i].pos.x > leaf->m_vMax.x )
				leaf->m_vMax.x = tf->m_vList[i].pos.x;
			if ( tf->m_vList[i].pos.y > leaf->m_vMax.y )
				leaf->m_vMax.y = tf->m_vList[i].pos.y;
			if ( tf->m_vList[i].pos.z > leaf->m_vMax.z )
				leaf->m_vMax.z = tf->m_vList[i].pos.z;


			if ( tf->m_vList[i].pos.x < leaf->m_vMin.x )
				leaf->m_vMin.x = tf->m_vList[i].pos.x;
			if ( tf->m_vList[i].pos.y < leaf->m_vMin.y )
				leaf->m_vMin.y = tf->m_vList[i].pos.y;
			if ( tf->m_vList[i].pos.z < leaf->m_vMin.z )
				leaf->m_vMin.z = tf->m_vList[i].pos.z;

			//为了制作head portal，为了求得世界最小坐标和最大坐标
			if( m_vMin.x > tf->m_vList[i].pos.x )
				m_vMin.x = tf->m_vList[i].pos.x;
			if( m_vMin.y > tf->m_vList[i].pos.y )
				m_vMin.y = tf->m_vList[i].pos.y;
			if( m_vMin.z > tf->m_vList[i].pos.z )
				m_vMin.z = tf->m_vList[i].pos.z;

			if( m_vMax.x < tf->m_vList[i].pos.x )
				m_vMax.x = tf->m_vList[i].pos.x;
			if( m_vMax.y < tf->m_vList[i].pos.y )
				m_vMax.y = tf->m_vList[i].pos.y;
			if( m_vMax.z < tf->m_vList[i].pos.z )
				m_vMax.z = tf->m_vList[i].pos.z;
		}
	}

	
	
}

void CBspManager::Split(D3DXPLANE *plane, CFace *f, CFace **a, CFace **b)
{
	CFace * frontList, * backList;
	BSPVERTEX vFrontList[20], vBackList[20], vFirst;
	BSPVERTEX vIntersectPoint, vPointA, vPointB;
	WORD wFrontCnt = 0, wBackCnt = 0, wCnt = 0, wCurrentVec = 0;

	vFirst = f->m_vList[0];

	switch( ClassifyPoint( plane, &vFirst.pos ))
	{
		case FACE_FRONT:
			vFrontList[wFrontCnt++] = vFirst;
			break;
		case FACE_BACK:
			vBackList[wBackCnt++] = vFirst;
			break;
		case FACE_ON:
			vFrontList[wFrontCnt++] = vFirst;
			vBackList[wBackCnt++] = vFirst;
			break;
		default:
			break;
	}

	for( wCnt = 1 ; wCnt < f->m_nNum + 1; wCnt++ )
	{
		if( wCnt == f->m_nNum )
			wCurrentVec = 0;
		else
			wCurrentVec = wCnt;

		vPointA = f->m_vList[wCnt-1];
		vPointB = f->m_vList[wCurrentVec];

		int result = ClassifyPoint( plane, &vPointB.pos );
		if( result == FACE_ON )
		{
			vBackList[wBackCnt++] = f->m_vList[wCurrentVec];
			vFrontList[wFrontCnt++] = f->m_vList[wCurrentVec];
		}
		else
		{
			if( IntersectLine( &vIntersectPoint, *plane, vPointA, vPointB ))
			{
				if( result == FACE_FRONT )
				{
					vBack