bspmanager.cpp

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

			}
			delete t;
		}
	}
	
	return target;
}

void CBspManager::CreateHeadPortals( CBspNode* node )
{
	CBspNode::CPortal *portal[6];
	D3DXPLANE plane;

	m_outsideNode.m_bIsLeaf = TRUE;
	m_outsideNode.m_bIsSolid = TRUE;
	m_outsideNode.m_pPortals = NULL;
/*
	for( int i = 0; i < 6 ; i++ )
	{
		portal[i] = new CBspNode::CPortal();
	}
	portal[0]->m_plane = D3DXPLANE( 1, 0, 0, 100 );
	portal[1]->m_plane = D3DXPLANE( 0, 0, 1, 100 );
	portal[2]->m_plane = D3DXPLANE( -1, 0, 0, 100 );
	portal[3]->m_plane = D3DXPLANE( 0, 0, -1, 100 );
	portal[4]->m_plane = D3DXPLANE( 0, -1, 0, 100 );
	portal[5]->m_plane = D3DXPLANE( 0, 1, 0, 100 );

	for( i = 0 ; i < 6 ; i++ )
	{
		portal[i]->m_pWinding = BaseWindingForPlane( &portal[i]->m_plane );
		portal[i]->AddPortalToNodes( node, &m_outsideNode );
	}
*/	

//near front side (o)
	portal[0] = new CBspNode::CPortal();
	portal[0]->m_pWinding = new CWinding();
	portal[0]->m_pWinding->vPoint[0] = D3DXVECTOR3( m_vMin.x - SIDE_SPACE, m_vMax.y + SIDE_SPACE, m_vMin.z - SIDE_SPACE );
	portal[0]->m_pWinding->vPoint[1] = D3DXVECTOR3( m_vMin.x - SIDE_SPACE, m_vMin.y - SIDE_SPACE, m_vMin.z - SIDE_SPACE );
	portal[0]->m_pWinding->vPoint[2] = D3DXVECTOR3( m_vMax.x + SIDE_SPACE, m_vMin.y - SIDE_SPACE, m_vMin.z - SIDE_SPACE );
	portal[0]->m_pWinding->vPoint[3] = D3DXVECTOR3( m_vMax.x + SIDE_SPACE, m_vMax.y + SIDE_SPACE, m_vMin.z - SIDE_SPACE );
	portal[0]->m_pWinding->n = 4;
	D3DXPlaneFromPoints( &plane, &portal[0]->m_pWinding->vPoint[0], &portal[0]->m_pWinding->vPoint[1], &portal[0]->m_pWinding->vPoint[2]);
	portal[0]->m_plane = plane;
	portal[0]->AddPortalToNodes( node, &m_outsideNode );

//far front side (o)
	portal[1] = new CBspNode::CPortal();
	portal[1]->m_pWinding = new CWinding();
	portal[1]->m_pWinding->vPoint[0] = D3DXVECTOR3( m_vMin.x - SIDE_SPACE, m_vMin.y - SIDE_SPACE, m_vMax.z + SIDE_SPACE );
	portal[1]->m_pWinding->vPoint[1] = D3DXVECTOR3( m_vMin.x - SIDE_SPACE, m_vMax.y + SIDE_SPACE, m_vMax.z + SIDE_SPACE );
	portal[1]->m_pWinding->vPoint[2] = D3DXVECTOR3( m_vMax.x + SIDE_SPACE, m_vMax.y + SIDE_SPACE, m_vMax.z + SIDE_SPACE );
	portal[1]->m_pWinding->vPoint[3] = D3DXVECTOR3( m_vMax.x + SIDE_SPACE, m_vMin.y - SIDE_SPACE, m_vMax.z + SIDE_SPACE );
	portal[1]->m_pWinding->n = 4;
	D3DXPlaneFromPoints( &plane, &portal[1]->m_pWinding->vPoint[0], &portal[1]->m_pWinding->vPoint[1],&portal[1]->m_pWinding->vPoint[2]);
	portal[1]->m_plane = plane;
	portal[1]->AddPortalToNodes( node, &m_outsideNode );

//left side(o)
	portal[2] = new CBspNode::CPortal();
	portal[2]->m_pWinding = new CWinding();
	portal[2]->m_pWinding->vPoint[0] = D3DXVECTOR3( m_vMin.x - SIDE_SPACE, m_vMin.y - SIDE_SPACE, m_vMin.z - SIDE_SPACE );
	portal[2]->m_pWinding->vPoint[1] = D3DXVECTOR3( m_vMin.x - SIDE_SPACE, m_vMax.y + SIDE_SPACE, m_vMin.z - SIDE_SPACE );
	portal[2]->m_pWinding->vPoint[2] = D3DXVECTOR3( m_vMin.x - SIDE_SPACE, m_vMax.y + SIDE_SPACE, m_vMax.z + SIDE_SPACE );
	portal[2]->m_pWinding->vPoint[3] = D3DXVECTOR3( m_vMin.x - SIDE_SPACE, m_vMin.y - SIDE_SPACE, m_vMax.z + SIDE_SPACE );
	portal[2]->m_pWinding->n = 4;
	D3DXPlaneFromPoints( &plane, &portal[2]->m_pWinding->vPoint[0], &portal[2]->m_pWinding->vPoint[1],&portal[2]->m_pWinding->vPoint[2]);
	portal[2]->m_plane = plane;
	portal[2]->AddPortalToNodes( node, &m_outsideNode );

//right side(o)
	portal[3] = new CBspNode::CPortal();
	portal[3]->m_pWinding = new CWinding();
	portal[3]->m_pWinding->vPoint[0] = D3DXVECTOR3( m_vMax.x + SIDE_SPACE, m_vMin.y - SIDE_SPACE, m_vMin.z - SIDE_SPACE );
	portal[3]->m_pWinding->vPoint[1] = D3DXVECTOR3( m_vMax.x + SIDE_SPACE, m_vMin.y - SIDE_SPACE, m_vMax.z + SIDE_SPACE );
	portal[3]->m_pWinding->vPoint[2] = D3DXVECTOR3( m_vMax.x + SIDE_SPACE, m_vMax.y + SIDE_SPACE, m_vMax.z + SIDE_SPACE );
	portal[3]->m_pWinding->vPoint[3] = D3DXVECTOR3( m_vMax.x + SIDE_SPACE, m_vMax.y + SIDE_SPACE, m_vMin.z - SIDE_SPACE );
	portal[3]->m_pWinding->n = 4;
	D3DXPlaneFromPoints( &plane, &portal[3]->m_pWinding->vPoint[0], &portal[3]->m_pWinding->vPoint[1],&portal[3]->m_pWinding->vPoint[2]);
	portal[3]->m_plane = plane;
	portal[3]->AddPortalToNodes( node, &m_outsideNode );

//up side(o)
	portal[4] = new CBspNode::CPortal();
	portal[4]->m_pWinding = new CWinding();
	portal[4]->m_pWinding->vPoint[0] = D3DXVECTOR3( m_vMax.x + SIDE_SPACE, m_vMax.y + SIDE_SPACE, m_vMin.z - SIDE_SPACE );
	portal[4]->m_pWinding->vPoint[1] = D3DXVECTOR3( m_vMax.x + SIDE_SPACE, m_vMax.y + SIDE_SPACE, m_vMax.z + SIDE_SPACE );
	portal[4]->m_pWinding->vPoint[2] = D3DXVECTOR3( m_vMin.x - SIDE_SPACE, m_vMax.y + SIDE_SPACE, m_vMax.z + SIDE_SPACE );
	portal[4]->m_pWinding->vPoint[3] = D3DXVECTOR3( m_vMin.x - SIDE_SPACE, m_vMax.y + SIDE_SPACE, m_vMin.z - SIDE_SPACE );
	portal[4]->m_pWinding->n = 4;
	D3DXPlaneFromPoints( &plane, &portal[4]->m_pWinding->vPoint[0], &portal[4]->m_pWinding->vPoint[1],&portal[4]->m_pWinding->vPoint[2]);
	portal[4]->m_plane = plane;
	portal[4]->AddPortalToNodes( node, &m_outsideNode );

//down side(o)
	portal[5] = new CBspNode::CPortal();
	portal[5]->m_pWinding = new CWinding();
	portal[5]->m_pWinding->vPoint[0] = D3DXVECTOR3( m_vMin.x - SIDE_SPACE, m_vMin.y - SIDE_SPACE, m_vMin.z - SIDE_SPACE );
	portal[5]->m_pWinding->vPoint[1] = D3DXVECTOR3( m_vMin.x - SIDE_SPACE, m_vMin.y - SIDE_SPACE, m_vMax.z + SIDE_SPACE );
	portal[5]->m_pWinding->vPoint[2] = D3DXVECTOR3( m_vMax.x + SIDE_SPACE, m_vMin.y - SIDE_SPACE, m_vMax.z + SIDE_SPACE );
	portal[5]->m_pWinding->vPoint[3] = D3DXVECTOR3( m_vMax.x + SIDE_SPACE, m_vMin.y - SIDE_SPACE, m_vMin.z - SIDE_SPACE );
	portal[5]->m_pWinding->n = 4;
	D3DXPlaneFromPoints( &plane, &portal[5]->m_pWinding->vPoint[0], &portal[5]->m_pWinding->vPoint[1],&portal[5]->m_pWinding->vPoint[2]);
	portal[5]->m_plane = plane;
	portal[5]->AddPortalToNodes( node, &m_outsideNode );
}

void CBspManager::VectorMA (D3DXVECTOR3 & va, double scale, D3DXVECTOR3 & vb, D3DXVECTOR3 & vc)
{
	vc.x = va.x + scale*vb.x;
	vc.y = va.y + scale*vb.y;
	vc.z = va.z + scale*vb.z;
}
void CBspManager::VectorScale (D3DXVECTOR3 & v, double scale, D3DXVECTOR3 & out)
{
	out.x = v.x * scale;
	out.y = v.y * scale;
	out.z = v.z * scale;
}

void CBspManager::PortalizeWorld()
{
	CreateHeadPortals( m_pBspRoot );
	CutNodePortals( m_pBspRoot );
	RemovePortalsLinkedSolidLeaf( m_pBspRoot );
}

void CBspManager::RemovePortalsLinkedSolidLeaf( CBspNode * node )
{
	CBspNode::CPortal	*p, *nextp;
	if( !node->m_bIsLeaf )
	{
		RemovePortalsLinkedSolidLeaf ( node->m_pFront );
		RemovePortalsLinkedSolidLeaf ( node->m_pBack );	
	}
	
	for (p=node->m_pPortals ; p ; p=nextp)
	{
		if (p->m_pNode[0] == node)
			nextp = p->m_pNext[0];
		else
			nextp = p->m_pNext[1];

		if( p->m_pNode[1]->m_bIsSolid || p->m_pNode[0]->m_bIsSolid )
		{
			p->m_bRender = FALSE;
		}
	}
}

void CBspManager::FreeAllPortals (CBspNode *node)
{
	CBspNode::CPortal	*p, *nextp, *prev = NULL;
	
	if ( !node->m_bIsLeaf )
	{
		FreeAllPortals ( node->m_pFront );
		FreeAllPortals ( node->m_pBack );
	}
	
	for (p=node->m_pPortals ; p ; p=nextp)
	{
		if (p->m_pNode[0] == node)
			nextp = p->m_pNext[0];
		else
			nextp = p->m_pNext[1];

		p->RemovePortalFromNode ( p->m_pNode[0]);
		p->RemovePortalFromNode ( p->m_pNode[1]);
		delete p->m_pWinding;
		p->m_pWinding = NULL;
		delete p;
	}
	node->m_pPortals = NULL;
}

BOOL CBspManager::RenderPortal( LPDIRECT3DDEVICE8 pd3dDevice, CD3DFont * pFont )
{
/*
	pd3dDevice->SetVertexShader( D3DFVF_BSPVERTEX );
	pd3dDevice->SetStreamSource( 0, NULL, 0 );
	pd3dDevice->SetIndices( NULL, 0 );
	pd3dDevice->SetRenderState(D3DRS_FILLMODE, D3DFILL_SOLID);
	pd3dDevice->SetRenderState(D3DRS_CULLMODE, D3DCULL_NONE );
	
	for( int i = 7; i < m_nPortalCnt ; i++ )
	{
		if( pFont )
		{
			D3DXMATRIX	mW, mV, mP, mO;
			pd3dDevice->GetTransform( D3DTS_WORLD, &mW );
			pd3dDevice->GetTransform( D3DTS_VIEW, &mV );
			pd3dDevice->GetTransform( D3DTS_PROJECTION, &mP );
			mO = mW * mV * mP;
			float x, y, z;
			x = ( m_ppPortals[i]->m_pWinding->vPoint[0].x + m_ppPortals[i]->m_pWinding->vPoint[1].x
				+ m_ppPortals[i]->m_pWinding->vPoint[2].x + m_ppPortals[i]->m_pWinding->vPoint[3].x ) / 4;
			y = ( m_ppPortals[i]->m_pWinding->vPoint[0].y + m_ppPortals[i]->m_pWinding->vPoint[1].y
				+ m_ppPortals[i]->m_pWinding->vPoint[2].y + m_ppPortals[i]->m_pWinding->vPoint[3].y ) / 4;
			z = ( m_ppPortals[i]->m_pWinding->vPoint[0].z + m_ppPortals[i]->m_pWinding->vPoint[1].z
				+ m_ppPortals[i]->m_pWinding->vPoint[2].z + m_ppPortals[i]->m_pWinding->vPoint[3].z ) / 4;

			D3DXVECTOR3 vI = D3DXVECTOR3( x, y, z );
			D3DXVECTOR3 vO;
			D3DXVec3TransformCoord( &vO, &vI, &mO );
			char	str[16];
			wsprintf( str, "( %d )", i );
			pFont->DrawText(400.0f * (vO.x+1.0f), 600 - 300.0f * (vO.y+1.0f), 0xff000000, str );
		}
		else
			pd3dDevice->DrawPrimitiveUP( D3DPT_TRIANGLEFAN, 2, m_ppPortals[i]->m_pWinding->vPoint ,sizeof( D3DXVECTOR3 ));
	}
*/

	typedef struct tagVTX
	{
		D3DXVECTOR3	p;
		DWORD		diffuse;
	} VTX;

	pd3dDevice->SetVertexShader( D3DFVF_XYZ|D3DFVF_DIFFUSE );
	pd3dDevice->SetStreamSource( 0, NULL, 0 );
	pd3dDevice->SetIndices( NULL, 0 );
	pd3dDevice->SetRenderState( D3DRS_ALPHABLENDENABLE, TRUE);
	pd3dDevice->SetRenderState( D3DRS_SRCBLEND, D3DBLEND_SRCALPHA);
	pd3dDevice->SetRenderState( D3DRS_DESTBLEND, D3DBLEND_ONE );
	pd3dDevice->SetTexture( 0, NULL );
	pd3dDevice->SetRenderState(D3DRS_FILLMODE, D3DFILL_SOLID);
	pd3dDevice->SetRenderState(D3DRS_CULLMODE, D3DCULL_CCW);

	for( int i = 0 ; i < m_nPortalCnt ; i++ )
	{
		VTX		vtx[8];
		for( int j = 0 ; j < m_ppPortals[i]->m_pWinding->n ; j++ )
		{
			vtx[j].p = m_ppPortals[i]->m_pWinding->vPoint[j];
			vtx[j].diffuse = 0x40ff0000;
		}
		pd3dDevice->DrawPrimitiveUP( D3DPT_TRIANGLEFAN, 2, vtx, sizeof( VTX ) );
	}

    pd3dDevice->SetTextureStageState( 0, D3DTSS_COLOROP,   D3DTOP_MODULATE );
    pd3dDevice->SetTextureStageState( 0, D3DTSS_COLORARG1, D3DTA_TEXTURE );
    pd3dDevice->SetTextureStageState( 0, D3DTSS_COLORARG2, D3DTA_DIFFUSE );
	pd3dDevice->SetRenderState( D3DRS_ALPHABLENDENABLE, FALSE );
	return TRUE;
}


CWinding* CBspManager::BaseWindingForPlane( D3DXPLANE *p )
{
	int				i, x;
	float			max, v;
	D3DXVECTOR3		org, vright, vup, normal;
	CWinding		*w;

	vup = D3DXVECTOR3( 0, 0, 0 );
	normal = D3DXVECTOR3( p->a, p->b, p->c );
// find the major axis
	
	max = -BSP_BOGUS;
	x = -1;

	v = fabs( p->a );
	if (v > max)
	{
		x = 0;
		max = v;
	}

	v = fabs( p->b );
	if( v > max )
	{
		x = 1;
		max = v;
	}

	v = fabs( p->c );
	if( v > max )
	{
		x = 2;
		max = v;
	}

	switch (x)
	{
	case 0:
	case 1:
		vup.z = 1;
		break;		
	case 2:
		vup.x = 1;
		break;		
	}

	v = D3DXVec3Dot ( &vup, &normal);
	VectorMA (vup, -v, normal, vup);
	D3DXVec3Normalize( &vup, &vup );
		
	VectorScale ( normal, -(p->d), org);
	
	D3DXVec3Cross( &vright, &normal, &vup );
	
	VectorScale (vup, 8192, vup);
	VectorScale (vright, 8192, vright);

// project a really big	axis aligned box onto the plane
	w = new CWinding();
	
//	VectorSubtract (org, vright, w->points[0]);
	w->vPoint[0] = org - vright;
//	VectorAdd (w->points[0], vup, w->points[0]);
	w->vPoint[0] = w->vPoint[0] + vup;
	
//	VectorAdd (org, vright, w->points[1]);
	w->vPoint[1] = org + vright;
//	VectorAdd (w->points[1], vup, w->points[1]);
	w->vPoint[1] = w->vPoint[1] + vup;
	
//	VectorAdd (org, vright, w->points[2]);
	w->vPoint[2] = org + vright;
//	VectorSubtract (w->points[2], vup, w->points[2]);
	w->vPoint[2] = w->vPoint[2] - vup;
	
//	VectorSubtract (org, vright, w->points[3]);
	w->vPoint[3] = org - vright;
//	VectorSubtract (w->points[3], vup, w->points[3]);
	w->vPoint[3] = w->vPoint[3] - vup;
	
	w->n = 4;
	
	return w;
}

void CBspManager::CutNodePortals( CBspNode *node )
{
	D3DXPLANE			* plane, clipplane;
	CBspNode			* f = NULL, *b = NULL, *other_node = NULL;
	CBspNode::CPortal	* p = NULL, *new_portal = NULL, *next_portal = NULL;
	CWinding			* w = NULL, *frontwinding = NULL, *backwinding = NULL;
	int					side;

	if( node->m_bIsLeaf )
		return;

	plane = &node->m_plane;

	f = node->m_pFront;
	b = node->m_pBack;

	new_portal = new CBspNode::CPortal();
	new_portal->m_plane = node->m_plane;
	
	w = BaseWindingForPlane( &new_portal->m_plane );
	side = 0;

	D3DXVECTOR3 origin = D3DXVECTOR3( 0, 0, 0 );

	for( p = node->m_pPortals ; p ; p = p->m_pNext[side] )
	{
		clipplane = p->m_plane;
		
		//p的 front_node和 node相同的话 
		if (p->m_pNode[0] == node)
			side = 0;

		//如果p的 back_node和 node相同，改变 plane的方向，将 side转为 1(back)..
		//其理由为：计算 partition plane的 back的时候，进行转动计算..
		else if (p->m_pNode[1] == node)
		{
			D3DXVECTOR3 normal = D3DXVECTOR3( clipplane.a, clipplane.b, clipplane.c );
			clipplane.d = -clipplane.d;

			normal = origin - normal;
			clipplane.a = normal.x;
			clipplane.b = normal.y;
			clipplane.c = normal.z;
			
			side = 1;
		}
		else
			;//error

		w = ClipWinding (w, &clipplane, true);
		if (!w)
		{
			printf ("WARNING: CutNodePortals_r:new portal was clipped away\n");
			break;
		}
	}

	if (w)
	{
	// if the plane was not clipped on all sides, there was an error
		new_portal->m_pWinding = w;	
		new_portal->AddPortalToNodes ( f, b );
	}

//
// partition the portals
//
	for (p = node->m_pPortals ; p ; p = next_portal)	
	{
		if (p->m_pNode[0] == node)
			side = 0;
		else if (p->m_pNode[1] == node)
			side = 1;
		else
			;//error
		next_portal = p->m_pNext[side];

		other_node = p->m_pNode[!side];
		p->RemovePortalFromNode( p->m_pNode[0] );
		p->RemovePortalFromNode( p->m_pNode[1] );

//
// cut the portal into two portals, one on each side of the cut plane
//
		DivideWinding (p->m_pWinding, plane, &frontwinding, &backwinding);
		
		if (!frontwinding)
		{
			if (side == 0)
				p->AddPortalToNodes ( b, other_node);
			else
				p->AddPortalToNodes ( other_node, b);
			continue;
		}
		if (!backwinding)
		{
			if (side == 0)
				p->AddPortalToNodes ( f, other_node);
			else
				p->AddPortalToNodes ( other_node, f);
			continue;
		}
		
	// the winding is split
		new_portal = new CBspNode::CPortal ();
		*new_portal = *p;
		new_portal->m_pWinding = backwinding;
		delete p->m_pWinding;
		p->m_pWinding = frontwinding;

		if (side == 0)
		{
			p->AddPortalToNodes ( f, other_node );
			new_portal->AddPortalToNodes ( b, other_node );
		}
		else
		{
			p->AddPortalToNodes ( other_node, f );
			new_portal->AddPortalToNodes ( other_node, b );
		}
	}
	
	CutNodePortals (f);	
	CutNodePortals (b);
}

CWinding * CBspManager::ClipWinding (CWinding *in, D3DXPLANE *split, boolean keepon)
{
	float		dists[MAX_POINTS_ON_WINDING];
	int			sides[MAX_POINTS_ON_WINDING];
	int			counts[3];
	float		dot;
	int			i, j;
	D3DXVECTOR3	p1, p2;
	D3DXVECTOR3	mid;
	CWinding	*neww = NULL;
	int			maxpts;
	
	counts[0] = counts[1] = counts[2] = 0;

// determine sides for each point
	for (i=0 ; i<in->n ; i++)
	{
		D3DXVECTOR3 normal = D3DXVECTOR3( split->a, split->b, split->c );
		dot = D3DXVec3Dot( &in->vPoint[i], &normal );
		dot = dot + split->d;
		dists[i] = dot;
		if (dot > EPSILON)
			sides[i] = SIDE_FRONT;
		else if (dot < -EPSILON)
			sides[i] = SIDE_BACK;
		else
			sides[i] = SIDE_ON;
	
		counts[sides[i]]++;
	}
	sides[i] = sides[0];
	dists[i] = dists[0];
	
	if (keepon && !counts[0] && !counts[1])
		return in;
		
	if (!counts[0])
	{
		delete in;
		return NULL;
	}
	if (!counts[1])
		return in;
	
	maxpts = in->n+4;	// can't use counts[0]+2 because
								// of fp grouping errors
	neww = new CWinding();
		
	for (i=0 ; i<in->n ; i++)
	{
		p1 = in->vPoint[i];
		
		if (sides[i] == SIDE_ON)
		{
			VectorCopy (p1, neww->vPoint[neww->n]);
			neww->n++;
			continue;
		}
	
		if (sides[i] == SIDE_FRONT)
		{
			VectorCopy (p1, neww->vPoint[neww->n]);
			neww->n++;
		}
		
		if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
			continue;
			
		// generate a split point
		p2 = in->vPoint[(i+1)%in->n];
		
		dot = dists[i] / (dists[i]-dists[i+1]);

		// avoid round off error when possible