brush.cpp

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

			front++;
			back++;
			on++;
		}
	}
   
	if (on == num)
		return SIDE_ON;
	else if (front == num)
		return SIDE_FRONT;
	else if (back == num)
		return SIDE_BACK;
	else
		return SIDE_SPLIT;
}

int CBrush::ClassifyPoint( D3DXPLANE * plane, D3DXVECTOR3 * v )
{
	float res = D3DXPlaneDotCoord( plane, v);
	if( res > EPSILON )
		return SIDE_FRONT;
	else if( res < -EPSILON )
		return SIDE_BACK;
	else 
		return SIDE_ON;
}

void CBrush::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 SIDE_FRONT:
			vFrontList[wFrontCnt++] = vFirst;
			break;
		case SIDE_BACK:
			vBackList[wBackCnt++] = vFirst;
			break;
		case SIDE_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 == SIDE_ON )
		{
			vBackList[wBackCnt++] = f->m_vList[wCurrentVec];
			vFrontList[wFrontCnt++] = f->m_vList[wCurrentVec];
		}
		else
		{
			if( IntersectLine( &vIntersectPoint, *plane, vPointA, vPointB ))
			{
				if( result == SIDE_FRONT )
				{
					vBackList[wBackCnt++] = vIntersectPoint;
					vFrontList[wFrontCnt++] = vIntersectPoint;
					if( wCurrentVec )
						vFrontList[wFrontCnt++] = f->m_vList[wCurrentVec];
				}
				if( result == SIDE_BACK )
				{
					vFrontList[wFrontCnt++] = vIntersectPoint;
					vBackList[wBackCnt++] = vIntersectPoint;
					if( wCurrentVec )
						vBackList[wBackCnt++] = f->m_vList[wCurrentVec];
				}
			}// end - if( IntersectLine() )
			else
			{
				if( result == SIDE_FRONT )
				{
					if( wCurrentVec )
						vFrontList[wFrontCnt++] = f->m_vList[wCurrentVec];
				}
				if( result == SIDE_BACK )
				{
					if( wCurrentVec )
						vBackList[wBackCnt++] = f->m_vList[wCurrentVec];
				}
			}// end - else( IntersectLine() )
		}// end - else( result == SIDE_ON )
	}// end - for(;;)
	
	if( wFrontCnt == wBackCnt )
	{
		frontList = CFace::CreateFace();
		BSPVERTEX* tmp1 = new BSPVERTEX[3];
		tmp1[0] = vFrontList[0];
		tmp1[1] = vFrontList[1];
		tmp1[2] = vFrontList[2];
		frontList->SetVertexList( tmp1 );
		frontList->m_nNum = 3;
		frontList->m_nTexture = f->m_nTexture;

		backList = CFace::CreateFace();
		BSPVERTEX* tmp2 = new BSPVERTEX[3];
		tmp2[0] = vBackList[0];
		tmp2[1] = vBackList[1];
		tmp2[2] = vBackList[2];
		backList->SetVertexList( tmp2 );
		backList->m_nNum = 3;
		backList->m_nTexture = f->m_nTexture;
	}
	else if( wFrontCnt > wBackCnt )
	{
		frontList = CFace::CreateFace();
		BSPVERTEX* tmp1 = new BSPVERTEX[3];
		tmp1[0] = vFrontList[0];
		tmp1[1] = vFrontList[1];
		tmp1[2] = vFrontList[2];
		frontList->SetVertexList( tmp1 );
		frontList->m_nNum = 3;
		frontList->m_nTexture = f->m_nTexture;

		CFace * next = CFace::CreateFace();
		BSPVERTEX* tmp2 = new BSPVERTEX[3];
		tmp2[0] = vFrontList[0];
		tmp2[1] = vFrontList[2];
		tmp2[2] = vFrontList[3];
		next->SetVertexList( tmp2 );
		next->m_nNum = 3;
		next->m_nTexture = f->m_nTexture;

		frontList->AddNext( next );

		backList = CFace::CreateFace();
		BSPVERTEX* tmp3 = new BSPVERTEX[3];
		tmp3[0] = vBackList[0];
		tmp3[1] = vBackList[1];
		tmp3[2] = vBackList[2];
		backList->SetVertexList( tmp3 );
		backList->m_nNum = 3;
		backList->m_nTexture;
	}
	else if( wBackCnt > wFrontCnt )
	{
		backList = CFace::CreateFace();
		BSPVERTEX* tmp1 = new BSPVERTEX[3];
		tmp1[0] = vBackList[0];
		tmp1[1] = vBackList[1];
		tmp1[2] = vBackList[2];
		backList->SetVertexList( tmp1 );
		backList->m_nNum = 3;
		backList->m_nTexture = f->m_nTexture;

		CFace * next = CFace::CreateFace();
		BSPVERTEX* tmp2 = new BSPVERTEX[3];
		tmp2[0] = vBackList[0];
		tmp2[1] = vBackList[2];
		tmp2[2] = vBackList[3];
		next->SetVertexList( tmp2 );
		next->m_nNum = 3;
		next->m_nTexture = f->m_nTexture;

		backList->AddNext( next );

		frontList = CFace::CreateFace();
		BSPVERTEX* tmp3 = new BSPVERTEX[3];
		tmp3[0] = vFrontList[0];
		tmp3[1] = vFrontList[1];
		tmp3[2] = vFrontList[2];
		frontList->SetVertexList( tmp3 );
		frontList->m_nNum = 3;
		frontList->m_nTexture = f->m_nTexture;
	}

	*a = frontList;
	*b = backList;
}

BOOL CBrush::IntersectLine( BSPVERTEX* vOut, D3DXPLANE &plane, BSPVERTEX &vA, BSPVERTEX &vB )
{
	int res = ClassifyPoint( &plane, &vA.pos );
	if( res == SIDE_ON )
		return FALSE;
	res = ClassifyPoint( &plane, &vB.pos );
	if( res == SIDE_ON )
		return FALSE;
	
	D3DXVECTOR3 n( plane.a, plane.b, plane.c );
	float lineLength = D3DXVec3Dot( &(vB.pos - vA.pos), &n );
	if( fabsf( lineLength ) < 0.0001 )
		return FALSE;

	float aDot = D3DXVec3Dot( &vA.pos, &n );
	float bDot = D3DXVec3Dot( &vB.pos, &n );
	float scale = ( -(plane.d) - aDot ) / ( bDot - aDot );

	if( scale < 0.0f )
		return FALSE;
	if( scale > 1.0f )
		return FALSE;

	(*vOut).pos = vA.pos + ( scale * ( vB.pos - vA.pos ) );

//texture 谅钎 ..
	float deltaU = vB.u - vA.u;
	float deltaV = vB.v - vA.v;
	(*vOut).u = vA.u + deltaU*scale;
	(*vOut).v = vA.v + deltaV*scale;
	return TRUE;
}

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


BOOL CBrush::IsColliedBrushs(CBrush *pb)
{
	CFace * brush1 = NULL, * brush2 = NULL;
	int res = 0;

	for( brush2 = pb->m_pFaceList ; brush2 ; brush2 = brush2->m_pNext )
	{
		for( int j = 0 ; j < brush2->m_nNum ; j++ )
		{
			res = 0;
			for( int i = 0 ; i < m_nTotalPlane ; i++ )
			{
				switch( ClassifyPoint( &m_Planes[i], &brush2->m_vList[j].pos ) )
				{
					case SIDE_ON:
					case SIDE_BACK:
						res++;
						break;
				}
			}
			if( res == m_nTotalPlane )
				return TRUE;
		}
	}


	for( brush1 = m_pFaceList ; brush1 ; brush1 = brush1->m_pNext )
	{
		for( int j = 0 ; j < brush1->m_nNum ; j++ )
		{
			res = 0;
			for( int i = 0 ; i < pb->m_nTotalPlane ; i++ )
			{
				switch( ClassifyPoint( &pb->m_Planes[i], &brush1->m_vList[j].pos ) )
				{
					case SIDE_ON:
					case SIDE_BACK:
						res++;
						break;
				}
			}
			if( res == pb->m_nTotalPlane )
				return TRUE;
		}
	}

	for( brush1 = m_pFaceList ; brush1 ; brush1 = brush1->m_pNext )
	{
		for( brush2 = pb->m_pFaceList ; brush2 ; brush2 = brush2->m_pNext )
		{
			if( IsColliedTriangles( brush1, brush2 ) )
			{
				return TRUE;
			}
		}
	}
	return FALSE;
}

//以第一个 brush的 face(f1)为基准，检查第二个 brush的 face(f2)是否冲突.
BOOL CBrush::IsColliedTriangles(CFace* f1, CFace* f2)
{
	BSPVERTEX a[3], b[3];
	a[0] = f1->m_vList[0];
	a[1] = f1->m_vList[1];
	a[2] = f1->m_vList[2];

	b[0] = f2->m_vList[0];
	b[1] = f2->m_vList[1];
	b[2] = f2->m_vList[2];

	D3DXPLANE planeA, planeB;
	D3DXPlaneFromPoints( &planeA, &a[0].pos, &a[1].pos, &a[2].pos );
	D3DXPlaneFromPoints( &planeB, &b[0].pos, &b[1].pos, &b[2].pos );

	BSPVERTEX vPointA, vPointB, vIntersectPoint;
	WORD wCnt, wCurrentVec;
	float a1, b1, a2, b2, a3, b3, a4, b4;	//二维坐标
	int nEx = 2 ;							//0为 x坐标, 1为 y坐标, 2为 z坐标 除外.

// 以第一个三角形（平面）为基准
	if( (a[1].pos.x - a[0].pos.x == 0) && (a[2].pos.x - a[0].pos.x == 0) )			//x坐标 除外
	{	
		a1 = a[0].pos.y;
		b1 = a[0].pos.z;

		a2 = a[1].pos.y;
		b2 = a[1].pos.z;

		a3 = a[2].pos.y;
		b3 = a[2].pos.z;

		nEx = 0;
	}
	else if( (a[1].pos.y - a[0].pos.y == 0) && (a[2].pos.y - a[0].pos.y == 0) )	//y坐标 除外
	{
		a1 = a[0].pos.x;
		b1 = a[0].pos.z;

		a2 = a[1].pos.x;
		b2 = a[1].pos.z;

		a3 = a[2].pos.x;
		b3 = a[2].pos.z;

		nEx = 1;
	}
	else	//z坐标 除外
	{
		a1 = a[0].pos.x;
		b1 = a[0].pos.y;

		a2 = a[1].pos.x;
		b2 = a[1].pos.y;

		a3 = a[2].pos.x;
		b3 = a[2].pos.y;

		nEx = 2;
	}

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

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

		if( IntersectLine( &vIntersectPoint, planeA, vPointA, vPointB ))
		{
			if( nEx == 0 )
			{
				a4 = vIntersectPoint.pos.y;
				b4 = vIntersectPoint.pos.z;
			}
			else if( nEx == 1 )
			{
				a4 = vIntersectPoint.pos.x;
				b4 = vIntersectPoint.pos.z;
			}
			else
			{
				a4 = vIntersectPoint.pos.x;
				b4 = vIntersectPoint.pos.y;
			}

//planeA.. 也就是第一个三角形的平面
			
			if( IsInsideTriangle( a1, b1, a2, b2, a3, b3, a4, b4, TRUE ) )
			{
				return TRUE;
			}
		}
	}
	
// 以第二个三角形为基准
	if( (b[1].pos.x - b[0].pos.x == 0) && (b[2].pos.x - b[0].pos.x == 0) )			//x坐标 除外
	{	
		a1 = b[0].pos.y;
		b1 = b[0].pos.z;

		a2 = b[1].pos.y;
		b2 = b[1].pos.z;

		a3 = b[2].pos.y;
		b3 = b[2].pos.z;

		nEx = 0;
	}
	else if( (b[1].pos.y - b[0].pos.y == 0) && (b[2].pos.y - b[0].pos.y == 0) )	//y坐标 除外
	{
		a1 = b[0].pos.x;
		b1 = b[0].pos.z;

		a2 = b[1].pos.x;
		b2 = b[1].pos.z;

		a3 = b[2].pos.x;
		b3 = b[2].pos.z;

		nEx = 1;
	}
	else	//z坐标 除外
	{
		a1 = b[0].pos.x;
		b1 = b[0].pos.y;

		a2 = b[1].pos.x;
		b2 = b[1].pos.y;

		a3 = b[2].pos.x;
		b3 = b[2].pos.y;

		nEx = 2;
	}


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

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

		if( IntersectLine( &vIntersectPoint, planeB, vPointA, vPointB ))
		{
			if( nEx == 0 )
			{
				a4 = vIntersectPoint.pos.y;
				b4 = vIntersectPoint.pos.z;
			}
			else if( nEx == 1 )
			{
				a4 = vIntersectPoint.pos.x;
				b4 = vIntersectPoint.pos.z;
			}
			else
			{
				a4 = vIntersectPoint.pos.x;
				b4 = vIntersectPoint.pos.y;
			}

			if( IsInsideTriangle( a1, b1, a2, b2, a3, b3, a4, b4, TRUE ) )
			{
				return TRUE;
			}
		}
	}
	
	return FALSE;
}

//即使最后的参数在边界线，也要确认是否在里面 inside.
BOOL CBrush::IsInsideTriangle(float &a1, float &b1, float &a2, float &b2, float &a3, float &b3, float &a4, float &b4, BOOL bContact )
{
	BOOL AB_vert = FALSE, BC_vert = FALSE, CA_vert = FALSE;
	BOOL bUp1 = FALSE, bUp2 = FALSE, bUp3 = FALSE;
	float center_x, center_y;				//三角形的中点.
	float m1, m2, m3, bb1, bb2, bb3;		//三条直线的斜率.
	center_x = center_y = m1 = m2 = m3 = bb1 = bb2 = bb3 = 0.f;

	int inside = 0;

	if( (a2 - a1) != 0 )
	{
		m1 = (b2 - b1)/(a2 - a1);
		bb1 = (b1) - (m1 * a1);
	}
	else if( (a2 - a1) == 0 )
	{
		AB_vert = TRUE;
	}

	if( (a3 - a2) != 0 )
	{
		m2 = (b3 - b2)/(a3 - a2);
		bb2 = (b2) - (m2 * a2);
	}
	else if( (a3 - a2) == 0 )
	{
		BC_vert = TRUE;
	}

	if( (a1 - a3) != 0 )
	{
		m3 = (b1 - b3)/(a1 - a3);
		bb3 = (b3) - (m3 * a3);
	}
	else if( (a1 - a3) == 0 )
	{
		CA_vert = TRUE;
	}

	center_x = (a1+a2+a3)/3;
	center_y = (b1+b2+b3)/3;
	
	if( ( (m1*center_x) + bb1 ) >= center_y )
		bUp1 = TRUE;
	else
		bUp1 = FALSE;

	if( ( (m2*center_x) + bb2 ) >= center_y )
		bUp2 = TRUE;
	else
		bUp2 = FALSE;

	if( ( (m3*center_x) + bb3 ) >= center_y )
		bUp3 = TRUE;
	else
		bUp3 = FALSE;


	if( bContact )		//即使是在边界线，也要确认是否在里面 inside.
	{
	//a->b
		if( AB_vert == TRUE )
		{
			if( (a1 <= a4) && (a1 <= center_x) )
				inside++;
			else if( (a1 >= a4) && (a1 >= center_x) )
				inside++;
		}
		else
		{
			if( bUp1 )
			{
				if( b4 <= ((m1*a4)+bb1) )
					inside++;
			}
			else if( !bUp1 )
			{
				if( b4 >= ((m1*a4)+bb1) )
					inside++;
			}
		}
		
	//b->c
		if( BC_vert == TRUE )
		{
			if( (a2 <= a4) && (a2 <= center_x) )
				inside++;
			else if( (a2 >= a4) && (a2 >= center_x) )
				inside++;
		}
		else
		{
			if( bUp2 )
			{
				if( b4 <= ((m2*a4)+bb2) )
					inside++;
			}
			else if( !bUp2 )
			{
				if( b4 >= ((m2*a4)+bb2) )
					inside++;
			}
		}

	//c->a
		if( CA_vert == TRUE )
		{
			if( (a3 <= a4) && (a3 <= center_x) )
				inside++;
			else if( (a3 >= a4) && (a3 >= center_x) )
				inside++;
		}
		else
		{
			if( bUp3 )
			{
				if( b4 <= ((m3*a4)+bb3) )
					inside++;
			}
			else if( !bUp3 )
			{
				if( b4 >= ((m3*a4)+bb3) )
					inside++;
			}
		}
	}//end if( bContact )  

//位于边界线，却不在里面（inside）的情况
	else
	{
	//a->b
		if( AB_vert == TRUE )
		{
			if( (a1 < a4) && (a1 < center_x) )
				inside++;
			else if( (a1 > a4) && (a1 > center_x) )
				inside++;
		}
		else
		{
			if( bUp1 )
			{
				if( b4 < ((m1*a4)+bb1) )
					inside++;
			}
			else
			{
				if( b4 > ((m1*a4)+bb1) )
					inside++;
			}
		}
		
	//b->c
		if( BC_vert == TRUE )
		{
			if( (a2 < a4) && (a2 < center_x) )
				inside++;
			else if( (a2 > a4) && (a2 > center_x) )
				inside++;
		}
		else
		{
			if( bUp2 )
			{
				if( b4 < ((m2*a4)+bb2) )
					inside++;
			}
			else
			{
				if( b4 > ((m2*a4)+bb2) )
					inside++;
			}
		}

	//c->a
		if( CA_vert == TRUE )
		{
			if( (a3 < a4) && (a3 < center_x) )
				inside++;
			else if( (a3 > a4) && (a3 > center_x) )
				inside++;
		}
		else
		{
			if( bUp3 )
			{
				if( b4 < ((m3*a4)+bb3) )
					inside++;
			}
			else
			{
				if( b4 > ((m3*a4)+bb3) )
					inside++;
			}
		}
	}

	if( inside == 3 )
		return TRUE;
	else
		return FALSE;
}

BOOL CBrush::BrushCopy(CBrush *pOrig, CBrush*  &pCopy)
{
	pCopy = new CBrush();
	CFace * face_head = NULL,* f1 = NULL;

	for( f1 = pOrig->m_pFaceList ; f1 ; f1 = f1->m_pNext )
	{
		CFace * f2 = CFace::CreateFace();
		FaceCopy( f1, f2 );
		f2->m_pNext = face_head;
		face_head = f2;
	}

	pCopy->m_nFaceCount = pOrig->m_nFaceCount;

	pCopy->m_pFaceList = face_head;

	pCopy->m_nTotalPlane = pOrig->m_nTotalPlane;

	for( int i = 0 ; i < pOrig->m_nTotalPlane ; i++ )
	{
		pCopy->m_Planes[i] = pOrig->m_Planes[i];
	}
	return TRUE;
}