xoctree.cpp

VC++ DEMO, used for the beginners and the amour

#include "HEADERS.H"
#include "FRUSTUM.H"
#include "XOCTREE.H"
#include "3DMATH.H"

USING NAMESPACE CGE::CULLING;
USING NAMESPACE CGE::MATHIN3D;

VOID XOCTREE::SetSceneDimensions(LPD3DXMESH SceneMesh,D3DXVECTOR3 vMin,D3DXVECTOR3 vMax)
{
	DWORD * Attributes = NULL;
	USHORT * IndexPtr = NULL;

	if ( SceneMesh == NULL ) return;
	m_OddSceneMesh = SceneMesh;

	m_OddSceneMesh->LockIndexBuffer(D3DLOCK_READONLY, (BYTE**)&IndexPtr);
	m_OddSceneMesh->LockAttributeBuffer(D3DLOCK_READONLY, &Attributes);
	m_vTriangles.resize( m_OddSceneMesh->GetNumFaces() );

	for(LONG i = 0;i< m_OddSceneMesh->GetNumFaces();i++) 
	{
		m_vTriangles[i].m_nVertIndices[0] = *IndexPtr++;
		m_vTriangles[i].m_nVertIndices[1] = *IndexPtr++;
		m_vTriangles[i].m_nVertIndices[2] = *IndexPtr++;
		m_vTriangles[i].m_nMarshalID = Attributes[i];
		m_vMarshals[Attributes[i]].m_NumOfTri++;
	}

	FLOAT MaxX = (FLOAT)max(fabsf(vMin.x), fabsf(vMax.x));
	FLOAT MaxY = (FLOAT)max(fabsf(vMin.y), fabsf(vMax.y));
	FLOAT MaxZ = (FLOAT)max(fabsf(vMin.z), fabsf(vMax.z));
	m_fSceneDimension = max(MaxX,max(MaxY,MaxZ))*2;
	m_OddSceneMesh->UnlockIndexBuffer();
	m_OddSceneMesh->UnlockAttributeBuffer();
	
	m_OddSceneMesh->LockVertexBuffer(0,(BYTE**)&m_vbOfMesh);
	m_OddSceneMesh->UnlockVertexBuffer();

	m_vsOfMesh = D3DXGetFVFVertexSize(m_OddSceneMesh->GetFVF());
}

VOID XOCTREE::CreateSceneNode(XOCTREE::Node * pNode,D3DXVECTOR3 vCenter, FLOAT fDimension)
{
	if ( !pNode ) return;
	// Store node coordinates and size
	LONG Amount = 0;

	pNode->m_vCenter = vCenter;
	pNode->m_fCubeSize = fDimension;

	// See if there are any polygons in the node
	if( !( Amount = CalculateTriangle(vCenter, fDimension) ) )
		return;
	
	// Split node if size > maximum and too many polygons
	if(fDimension > m_fMaxNodeSize && Amount > m_nMaxTriangles) 
	{
		pNode->m_bSubDivided = TRUE;
		for ( int i = 0; i < 8; ++i)
		{
			if ( CalculateTriangle( GetNewNodeCenter(vCenter,fDimension,i),fDimension/2) > 0 )
			{
				pNode->m_pChildNode[i] = new XOCTREE::Node;
				CreateSceneNode(pNode->m_pChildNode[i],GetNewNodeCenter(vCenter,fDimension,i),fDimension/2);
			}
		}
	}
	else
	{
		AssignTrianglesToNode(pNode,Amount);
	}
}

VOID XOCTREE::AssignTrianglesToNode(XOCTREE::Node * pNode,LONG Amount)
{
	if ( !pNode ) return;
	for ( LONG i = 0 ; i < m_vTriangles.size(); ++i)
	{
		if ( IsTriangleInside(&m_vTriangles[i],pNode->m_vCenter,pNode->m_fCubeSize) == TRUE )
		{
			pNode->m_vTriangles.push_back(&m_vTriangles[i]);
		}
	}
}

VOID XOCTREE::NodeInScene(LPDIRECT3DDEVICE8 device,LPFRUSTUM Frustum,FLOAT fZDistance)
{
	D3DXMATRIX Matrix;
	FRUSTUM vFrustum;
	
	if(device == NULL || m_ParentNode == NULL || !m_vTriangles.size())
		return;
	
	if((Frustum) == NULL)
	{
		vFrustum.CalculateFrustum(device,fZDistance);
		Frustum = &vFrustum;
	}
	
	D3DXMatrixIdentity(&Matrix);
	device->SetTransform(D3DTS_WORLD, &Matrix);
	
	for(LONG i=0;i<m_vMarshals.size();i++) 
	{
		m_vMarshals[i].m_pVB->Lock(0,0,(BYTE**)&m_vMarshals[i].m_vbOfVB,0);
		m_vMarshals[i].m_NumOfTriToDraw = 0;
	}
	
	m_nDrawnTime = timeGetTime();
	
	CullNode(Frustum,m_ParentNode);
	
	for(i=0;i<m_vMarshals.size();i++) 
	{
		m_vMarshals[i].m_pVB->Unlock();
		
		if(m_vMarshals[i].m_NumOfTriToDraw) 
		{
			device->SetMaterial(&m_vMaterials[i]);
			device->SetTexture(0, m_vTextures[i]);
			device->SetStreamSource(0,m_vMarshals[i].m_pVB,m_vsOfMesh);
			device->SetVertexShader(m_OddSceneMesh->GetFVF());
			device->DrawPrimitive(D3DPT_TRIANGLELIST,0,m_vMarshals[i].m_NumOfTriToDraw);
		}
	}
}

VOID XOCTREE::CullNode(LPFRUSTUM Frustum,XOCTREE::Node * pNode)
{
	if ( !pNode ) return;

	if ( pNode->m_bSubDivided )
	{
		CullNode(Frustum,pNode->m_pChildNode[0]);
		CullNode(Frustum,pNode->m_pChildNode[1]);
		CullNode(Frustum,pNode->m_pChildNode[2]);
		CullNode(Frustum,pNode->m_pChildNode[3]);
		CullNode(Frustum,pNode->m_pChildNode[4]);
		CullNode(Frustum,pNode->m_pChildNode[5]);
		CullNode(Frustum,pNode->m_pChildNode[6]);
		CullNode(Frustum,pNode->m_pChildNode[7]);
	}
	else if ( Frustum->CheckCube(pNode->m_vCenter.x,pNode->m_vCenter.y,pNode->m_vCenter.z,pNode->m_fCubeSize/2) == TRUE )
	{
		LONG nMarshalID = 0;
		if(pNode->m_vTriangles.size() != 0)
		{
			for(LONG i=0;i<pNode->m_vTriangles.size();i++) 
			{				
				if(pNode->m_vTriangles[i]->m_nLastDrawnTime != m_nDrawnTime && (nMarshalID = pNode->m_vTriangles[i]->m_nMarshalID) < m_vMarshals.size())
				{
					if(m_vMaterials[nMarshalID].Diffuse.a != 0.0f) 
					{
						memcpy(m_vMarshals[nMarshalID].m_vbOfVB, &m_vbOfMesh[m_vsOfMesh * pNode->m_vTriangles[i]->m_nVertIndices[0]], m_vsOfMesh);
						m_vMarshals[nMarshalID].m_vbOfVB += m_vsOfMesh;

						memcpy(m_vMarshals[nMarshalID].m_vbOfVB, &m_vbOfMesh[m_vsOfMesh * pNode->m_vTriangles[i]->m_nVertIndices[1]], m_vsOfMesh);
						m_vMarshals[nMarshalID].m_vbOfVB += m_vsOfMesh;

						memcpy(m_vMarshals[nMarshalID].m_vbOfVB, &m_vbOfMesh[m_vsOfMesh * pNode->m_vTriangles[i]->m_nVertIndices[2]], m_vsOfMesh);
						m_vMarshals[nMarshalID].m_vbOfVB += m_vsOfMesh;

						m_vMarshals[nMarshalID].m_NumOfTriToDraw++;
					}
					pNode->m_vTriangles[i]->m_nLastDrawnTime = m_nDrawnTime;
				}
			}
		}
	}
}

D3DXVECTOR3 XOCTREE::GetNewNodeCenter(D3DXVECTOR3 vCenter, FLOAT fDimension, INT nodeID)
{	
	D3DXVECTOR3 vNodeCenter(0, 0, 0);
	D3DXVECTOR3 vCtr = vCenter;
	
	switch(nodeID)							
	{
	case TOP_LEFT_FRONT:
		vNodeCenter = D3DXVECTOR3(vCtr.x - fDimension/4, vCtr.y + fDimension/4, vCtr.z + fDimension/4);
		break;
		
	case TOP_LEFT_BACK:
		vNodeCenter = D3DXVECTOR3(vCtr.x - fDimension/4, vCtr.y + fDimension/4, vCtr.z - fDimension/4);
		break;
		
	case TOP_RIGHT_BACK:
		vNodeCenter = D3DXVECTOR3(vCtr.x + fDimension/4, vCtr.y + fDimension/4, vCtr.z - fDimension/4);
		break;
		
	case TOP_RIGHT_FRONT:
		vNodeCenter = D3DXVECTOR3(vCtr.x + fDimension/4, vCtr.y + fDimension/4, vCtr.z + fDimension/4);
		break;
		
	case BOTTOM_LEFT_FRONT:
		vNodeCenter = D3DXVECTOR3(vCtr.x - fDimension/4, vCtr.y - fDimension/4, vCtr.z + fDimension/4);
		break;
		
	case BOTTOM_LEFT_BACK:
		vNodeCenter = D3DXVECTOR3(vCtr.x - fDimension/4, vCtr.y - fDimension/4, vCtr.z - fDimension/4);
		break;
		
	case BOTTOM_RIGHT_BACK:
		vNodeCenter = D3DXVECTOR3(vCtr.x + fDimension/4, vCtr.y - fDimension/4, vCtr.z - fDimension/4);
		break;
		
	case BOTTOM_RIGHT_FRONT:
		vNodeCenter = D3DXVECTOR3(vCtr.x + fDimension/4, vCtr.y - fDimension/4, vCtr.z + fDimension/4);
		break;
	}
	return vNodeCenter;
}

LONG XOCTREE::CalculateTriangle(D3DXVECTOR3 vCenter, FLOAT fDimension)
{
	LONG i, Amount;
	if(!m_vTriangles.size())
		return 0;
	Amount = 0;
	for(i=0;i<m_vTriangles.size();i++)
	{
		if(IsTriangleInside(&m_vTriangles[i],vCenter,fDimension) == TRUE)
			Amount++;
	}
	
	return Amount;
}

BOOL XOCTREE::IsTriangleInside(XOCTREE::Triangle *pTriangle, D3DXVECTOR3 vCenter, FLOAT fDimension)
{
	FLOAT  XMin, XMax, YMin, YMax, ZMin, ZMax;
	D3DXVECTOR3 * tvp[3];
	
	tvp[0] = (D3DXVECTOR3*)&m_vbOfMesh[m_vsOfMesh * pTriangle->m_nVertIndices[0]];
	tvp[1] = (D3DXVECTOR3*)&m_vbOfMesh[m_vsOfMesh * pTriangle->m_nVertIndices[1]];
	tvp[2] = (D3DXVECTOR3*)&m_vbOfMesh[m_vsOfMesh * pTriangle->m_nVertIndices[2]];
	
	XMin = min(tvp[0]->x, min(tvp[1]->x, tvp[2]->x));
	XMax = max(tvp[0]->x, max(tvp[1]->x, tvp[2]->x));
	
	if(XMax < (vCenter.x - fDimension / 2.0f)) return FALSE;
	if(XMin > (vCenter.x + fDimension / 2.0f)) return FALSE;
	
	
    YMin = min(tvp[0]->y, min(tvp[1]->y, tvp[2]->y));
    YMax = max(tvp[0]->y, max(tvp[1]->y, tvp[2]->y));

    if(YMax < (vCenter.y - fDimension / 2.0f)) return FALSE;
    if(YMin > (vCenter.y + fDimension / 2.0f)) return FALSE;
	
	ZMin = min(tvp[0]->z, min(tvp[1]->z, tvp[2]->z));
	ZMax = max(tvp[0]->z, max(tvp[1]->z, tvp[2]->z));

	if(ZMax < (vCenter.z - fDimension / 2.0f)) return FALSE;
	if(ZMin > (vCenter.z + fDimension / 2.0f)) return FALSE;
	
	return TRUE;
}

BOOL XOCTREE::CollisionDetection(D3DXVECTOR3 &vStartPos, D3DXVECTOR3 vRadiusVector, D3DXVECTOR3 vVelocity, FLOAT fStaticFriction, FLOAT fFriction)
{
	BOOL bHit = FALSE;
	D3DXVECTOR3 vVel;
	FLOAT xScale = 1.0f/vRadiusVector.x;
	FLOAT yScale = 1.0f/vRadiusVector.y;
	FLOAT zScale = 1.0f/vRadiusVector.z;

	D3DXVECTOR3 vScale(xScale, yScale, zScale);

	if (NULL == m_ParentNode||m_OddSceneMesh == NULL)
		return FALSE;

	Scale3DVector(vStartPos, xScale, yScale, zScale);
	if ( D3DXVec3Length(&vVelocity) > fStaticFriction)
	{
		Scale3DVector(vVelocity, xScale, yScale, zScale);
		while (CollisionInScene(vStartPos, vScale, vVelocity))
		{	
			bHit = TRUE;
			vVel = vVelocity;
			Scale3DVector(vVel, vRadiusVector.x, vRadiusVector.y, vRadiusVector.z);
			if (D3DXVec3Length(&vVel) <= fStaticFriction)
				break;
			vVelocity *= (1.0f - fFriction);
		}
	}

	Scale3DVector(vStartPos, vRadiusVector.x, vRadiusVector.y, vRadiusVector.z);
	return bHit;
}

BOOL XOCTREE::CollisionInScene(D3DXVECTOR3 &vStartPos, D3DXVECTOR3 vScale, D3DXVECTOR3 &vVelocity)
{
#define EPSILON (0.01f)
	
	BOOL bHit = FALSE;
	DWORD i = 0;
	FLOAT fDistToTravel = D3DXVec3Length(&vVelocity), fDist;
	D3DXVECTOR3 vEndPos,v1, v2, v3, v4, vNormal, vDirection;
	D3DXVECTOR3 vSphereHitPoint, vPlaneHitPoint, vPolygonHitPoint;
	
	BOOL bCollisionFound = FALSE;
	FLOAT fNearestDist = -1.0f;
	D3DXVECTOR3 vNearestHitPoint;
	D3DXVECTOR3 vNearestPolygonHitPoint;
	
	std::vector <XOCTREE::Triangle*>list;
	
	vEndPos = vStartPos + vVelocity;
	D3DXVec3Normalize(&vDirection, &vVelocity);
	if (fDistToTravel <= EPSILON)
		return FALSE;
	
	SearchPotentialCollisions(m_ParentNode, vStartPos, vEndPos, vScale, list);
	
	if (list.size() == 0)
	{
		vStartPos += vVelocity;
		return FALSE;
	}
	
	for (i = 0; i < list.size(); i++)
	{
		XOCTREE::Triangle *pTriangle = list[i];
		
		v1 = *((D3DXVECTOR3 *)(m_vbOfMesh + m_vsOfMesh * pTriangle->m_nVertIndices[0]));
		v2 = *((D3DXVECTOR3 *)(m_vbOfMesh + m_vsOfMesh * pTriangle->m_nVertIndices[1]));
		v3 = *((D3DXVECTOR3 *)(m_vbOfMesh + m_vsOfMesh * pTriangle->m_nVertIndices[2]));

		Scale3DVector(v1, vScale.x, vScale.y, vScale.z);
		Scale3DVector(v2, vScale.x, vScale.y, vScale.z);
		Scale3DVector(v3, vScale.x, vScale.y, vScale.z);
		
		D3DXVec3Cross(&vNormal, &(v2 - v1), &(v3 - v1));
		D3DXVec3Normalize(&vNormal, &vNormal);
		
		
		fDist = PlaneIntersectRay(v1, vNormal, vStartPos, vDirection);
		if (fDist < 0.0f)
			continue;
		
		if (fDist <= 1.0f)
		{
			vPlaneHitPoint = vStartPos - vNormal * fDist;
			
		}else
		{
			vSphereHitPoint = vStartPos - vNormal;
			FLOAT d = PlaneIntersectRay(v1, vNormal, vSphereHitPoint, vDirection);
			
			if (d < 0)
				continue;
			vPlaneHitPoint = vSphereHitPoint + vDirection * d;
		}
		
		vPolygonHitPoint = vPlaneHitPoint;
		if (!IsPointInTriangle(v1, v2, v3, vPolygonHitPoint))
		{
			vPolygonHitPoint = NearestPointOnTriangle(v1, v2, v3, vPolygonHitPoint);
		}
		FLOAT t = SphereIntersectRay(vStartPos, 1.0f, vPolygonHitPoint, -vDirection);
		if ((t >= 0.0f && t <= fDistToTravel) )
		{
			if (!bCollisionFound || t <= fNearestDist)
			{
				fNearestDist = t;
				vNearestHitPoint = vPolygonHitPoint - t * vDirection;
				vNearestPolygonHitPoint = vPolygonHitPoint;
				bCollisionFound = TRUE;
			}
		}
	}
	
	if (!bCollisionFound)
	{
		vStartPos += vVelocity;
		return FALSE;
	}
	
	vStartPos += (fNearestDist - EPSILON ) * vDirection;
	vEndPos = vNearestPolygonHitPoint + vDirection * (fDistToTravel - fNearestDist);
	D3DXVECTOR3 vSlidePlaneOrigin = vNearestPolygonHitPoint;
	D3DXVECTOR3 vSlidePlaneNormal = vNearestPolygonHitPoint - vStartPos;
	D3DXVec3Normalize(&vSlidePlaneNormal, &vSlidePlaneNormal);
	
	vEndPos += vSlidePlaneNormal * PlaneIntersectRay(vSlidePlaneOrigin, vSlidePlaneNormal, vEndPos,vSlidePlaneNormal );
	vVelocity = (vEndPos - vNearestPolygonHitPoint);
	CollisionInScene(vStartPos,vScale,vVelocity);
	return TRUE;
	
}

VOID XOCTREE::SearchPotentialCollisions(XOCTREE::Node *pNode, const D3DXVECTOR3 & vStartPos, const D3DXVECTOR3 &vEndPos,const D3DXVECTOR3 &vScale, std::vector<XOCTREE::Triangle *> &list)
{
	LONG i = 0;
	D3DXVECTOR3  v1, v2, v3;
	
	if (NULL == pNode)	return;
	
	if ( pNode->m_bSubDivided )
	{
		for (i = 0; i < 8; i++)
		{
			SearchPotentialCollisions(pNode->m_pChildNode[i], vStartPos, vEndPos, vScale, list);
		}
	}
	else
	{
		
		D3DXVECTOR3 vBox = pNode->m_vCenter;
		FLOAT fSize = pNode->m_fCubeSize;
		
		for (i = 0; i < pNode->m_vTriangles.size(); i++)
		{
			
			v1 = *((D3DXVECTOR3 *)(m_vbOfMesh + m_vsOfMesh * pNode->m_vTriangles[i]->m_nVertIndices[0]));
			v2 = *((D3DXVECTOR3 *)(m_vbOfMesh + m_vsOfMesh * pNode->m_vTriangles[i]->m_nVertIndices[1]));
			v3 = *((D3DXVECTOR3 *)(m_vbOfMesh + m_vsOfMesh * pNode->m_vTriangles[i]->m_nVertIndices[2]));
			
			Scale3DVector(v1, vScale.x, vScale.y, vScale.z);
			Scale3DVector(v2, vScale.x, vScale.y, vScale.z);
			Scale3DVector(v3, vScale.x, vScale.y, vScale.z);
			
			FLOAT fBorder = 2.0f;
			FLOAT xMax = max(vStartPos.x,vEndPos.x) + fBorder;
			FLOAT xMin = min(vStartPos.x,vEndPos.x) - fBorder;
			FLOAT yMax = max(vStartPos.y,vEndPos.y) + fBorder;
			FLOAT yMin = min(vStartPos.y,vEndPos.y) - fBorder;
			FLOAT zMax = max(vStartPos.z,vEndPos.z) + fBorder;
			FLOAT zMin = min(vStartPos.z,vEndPos.z) - fBorder;
			D3DXVECTOR3 vCenter(xMin + (xMax - xMin)/2.0f, yMin + (yMax - yMin)/2.0f, zMin + (zMax - zMin)/2.0f);
			if (IsPolygonInBox(v1, v2, v3, vCenter, (xMax - xMin)/2.0f, (yMax - yMin)/2.0f,	(zMax - zMin)/2.0f) )
			{
				list.push_back(pNode->m_vTriangles[i]);
			}
		}	
	}
}