glfrustum.cpp

体现了lod(level of detail)算法 包括网格细分,空间层次

#include "glFrustum.h"


//////////////////////////////////////////////////////////////////////
// Construction / destruction
//////////////////////////////////////////////////////////////////////
CFrustum::CFrustum()
{}

CFrustum::~CFrustum()
{}


void CFrustum::UpdateFrustum()									// Extracts The Current View Frustum Plane Equations
{
	float	proj[16];									// For Grabbing The PROJECTION Matrix
	float	modl[16];									// For Grabbing The MODELVIEW Matrix
	float	clip[16];									// Result Of Concatenating PROJECTION and MODELVIEW
	float	t;											// Temporary Work Variable
	
	glGetFloatv( GL_PROJECTION_MATRIX, proj );			// Grab The Current PROJECTION Matrix
	glGetFloatv( GL_MODELVIEW_MATRIX, modl );			// Grab The Current MODELVIEW Matrix

	// Concatenate (Multiply) The Two Matricies
	clip[ 0] = modl[ 0] * proj[ 0] + modl[ 1] * proj[ 4] + modl[ 2] * proj[ 8] + modl[ 3] * proj[12];
	clip[ 1] = modl[ 0] * proj[ 1] + modl[ 1] * proj[ 5] + modl[ 2] * proj[ 9] + modl[ 3] * proj[13];
	clip[ 2] = modl[ 0] * proj[ 2] + modl[ 1] * proj[ 6] + modl[ 2] * proj[10] + modl[ 3] * proj[14];
	clip[ 3] = modl[ 0] * proj[ 3] + modl[ 1] * proj[ 7] + modl[ 2] * proj[11] + modl[ 3] * proj[15];

	clip[ 4] = modl[ 4] * proj[ 0] + modl[ 5] * proj[ 4] + modl[ 6] * proj[ 8] + modl[ 7] * proj[12];
	clip[ 5] = modl[ 4] * proj[ 1] + modl[ 5] * proj[ 5] + modl[ 6] * proj[ 9] + modl[ 7] * proj[13];
	clip[ 6] = modl[ 4] * proj[ 2] + modl[ 5] * proj[ 6] + modl[ 6] * proj[10] + modl[ 7] * proj[14];
	clip[ 7] = modl[ 4] * proj[ 3] + modl[ 5] * proj[ 7] + modl[ 6] * proj[11] + modl[ 7] * proj[15];

	clip[ 8] = modl[ 8] * proj[ 0] + modl[ 9] * proj[ 4] + modl[10] * proj[ 8] + modl[11] * proj[12];
	clip[ 9] = modl[ 8] * proj[ 1] + modl[ 9] * proj[ 5] + modl[10] * proj[ 9] + modl[11] * proj[13];
	clip[10] = modl[ 8] * proj[ 2] + modl[ 9] * proj[ 6] + modl[10] * proj[10] + modl[11] * proj[14];
	clip[11] = modl[ 8] * proj[ 3] + modl[ 9] * proj[ 7] + modl[10] * proj[11] + modl[11] * proj[15];

	clip[12] = modl[12] * proj[ 0] + modl[13] * proj[ 4] + modl[14] * proj[ 8] + modl[15] * proj[12];
	clip[13] = modl[12] * proj[ 1] + modl[13] * proj[ 5] + modl[14] * proj[ 9] + modl[15] * proj[13];
	clip[14] = modl[12] * proj[ 2] + modl[13] * proj[ 6] + modl[14] * proj[10] + modl[15] * proj[14];
	clip[15] = modl[12] * proj[ 3] + modl[13] * proj[ 7] + modl[14] * proj[11] + modl[15] * proj[15];


	// Extract the RIGHT clipping plane
	frustum[0][0] = clip[ 3] - clip[ 0];
	frustum[0][1] = clip[ 7] - clip[ 4];
	frustum[0][2] = clip[11] - clip[ 8];
	frustum[0][3] = clip[15] - clip[12];

	// Normalize it
	t = (float) sqrt( frustum[0][0] * frustum[0][0] + frustum[0][1] * frustum[0][1] + frustum[0][2] * frustum[0][2] );
	frustum[0][0] /= t;
	frustum[0][1] /= t;
	frustum[0][2] /= t;
	frustum[0][3] /= t;


	// Extract the LEFT clipping plane
	frustum[1][0] = clip[ 3] + clip[ 0];
	frustum[1][1] = clip[ 7] + clip[ 4];
	frustum[1][2] = clip[11] + clip[ 8];
	frustum[1][3] = clip[15] + clip[12];

	// Normalize it
	t = (float) sqrt( frustum[1][0] * frustum[1][0] + frustum[1][1] * frustum[1][1] + frustum[1][2] * frustum[1][2] );
	frustum[1][0] /= t;
	frustum[1][1] /= t;
	frustum[1][2] /= t;
	frustum[1][3] /= t;


	// Extract the BOTTOM clipping plane
	frustum[2][0] = clip[ 3] + clip[ 1];
	frustum[2][1] = clip[ 7] + clip[ 5];
	frustum[2][2] = clip[11] + clip[ 9];
	frustum[2][3] = clip[15] + clip[13];

	// Normalize it
	t = (float) sqrt( frustum[2][0] * frustum[2][0] + frustum[2][1] * frustum[2][1] + frustum[2][2] * frustum[2][2] );
	frustum[2][0] /= t;
	frustum[2][1] /= t;
	frustum[2][2] /= t;
	frustum[2][3] /= t;


	// Extract the TOP clipping plane
	frustum[3][0] = clip[ 3] - clip[ 1];
	frustum[3][1] = clip[ 7] - clip[ 5];
	frustum[3][2] = clip[11] - clip[ 9];
	frustum[3][3] = clip[15] - clip[13];

	// Normalize it
	t = (float) sqrt( frustum[3][0] * frustum[3][0] + frustum[3][1] * frustum[3][1] + frustum[3][2] * frustum[3][2] );
	frustum[3][0] /= t;
	frustum[3][1] /= t;
	frustum[3][2] /= t;
	frustum[3][3] /= t;


	// Extract the FAR clipping plane
	frustum[4][0] = clip[ 3] - clip[ 2];
	frustum[4][1] = clip[ 7] - clip[ 6];
	frustum[4][2] = clip[11] - clip[10];
	frustum[4][3] = clip[15] - clip[14];

	// Normalize it
	t = (float) sqrt( frustum[4][0] * frustum[4][0] + frustum[4][1] * frustum[4][1] + frustum[4][2] * frustum[4][2] );
	frustum[4][0] /= t;
	frustum[4][1] /= t;
	frustum[4][2] /= t;
	frustum[4][3] /= t;


	// Extract the NEAR clipping plane.  This is last on purpose (see pointinfrustum() for reason)
	frustum[5][0] = clip[ 3] + clip[ 2];
	frustum[5][1] = clip[ 7] + clip[ 6];
	frustum[5][2] = clip[11] + clip[10];
	frustum[5][3] = clip[15] + clip[14];

	// Normalize it
	t = (float) sqrt( frustum[5][0] * frustum[5][0] + frustum[5][1] * frustum[5][1] + frustum[5][2] * frustum[5][2] );
	frustum[5][0] /= t;
	frustum[5][1] /= t;
	frustum[5][2] /= t;
	frustum[5][3] /= t; 
}


bool CFrustum::Polygon2(vec3 p1, vec3 p2, vec3 p3)
{
	int i;
	for (i = 0; i<6; i++)
	{
		if (frustum[i][0]*p1[0]+frustum[i][1]*p1[1]+frustum[i][2]*p1[2]+frustum[i][3]>0)
			continue;
		if (frustum[i][0]*p2[0]+frustum[i][1]*p2[1]+frustum[i][2]*p2[2]+frustum[i][3]>0)
			continue;
		if (frustum[i][0]*p3[0]+frustum[i][1]*p3[1]+frustum[i][2]*p3[2]+frustum[i][3]>0)
			continue;

		return false;
	}
	return true;
}

bool CFrustum::PointInFrustum( float x, float y, float z )
{
	int i;

	for( i = 0; i < 6; i++ )
		if(frustum[i][0]*x + frustum[i][1]*y + frustum[i][2]*z + frustum[i][3] <= 0 )
			return false;
	return true;

}

bool CFrustum::PolygonInFrustum(BBOX *b)
{
	unsigned int i;//CurPlane
	for (i = 0; i<6; i++)
	{
	if (frustum[i][0]*b->min_center[0]+frustum[i][1]*b->min_center[1]+frustum[i][2]*b->min_center[2]+frustum[i][3]>0)
		continue;
	if (frustum[i][0]*b->min_apex[0]+frustum[i][1]*b->min_apex[1]+frustum[i][2]*b->min_apex[2]+frustum[i][3]>0)
		continue;
	if (frustum[i][0]*b->min_right[0]+frustum[i][1]*b->min_right[1]+frustum[i][2]*b->min_right[2]+frustum[i][3]>0)
		continue;
	if (frustum[i][0]*b->min_left[0]+frustum[i][1]*b->min_left[1]+frustum[i][2]*b->min_left[2]+frustum[i][3]>0)
		continue;
		
	if (frustum[i][0]*b->max_center[0]+frustum[i][1]*b->max_center[1]+frustum[i][2]*b->max_center[2]+frustum[i][3]>0)
		continue;
	if (frustum[i][0]*b->max_apex[0]+frustum[i][1]*b->max_apex[1]+frustum[i][2]*b->max_apex[2]+frustum[i][3]>0)
		continue;
	if (frustum[i][0]*b->max_right[0]+frustum[i][1]*b->max_right[1]+frustum[i][2]*b->max_right[2]+frustum[i][3]>0)
		continue;
	if (frustum[i][0]*b->max_left[0]+frustum[i][1]*b->max_left[1]+frustum[i][2]*b->max_left[2]+frustum[i][3]>0)
		continue;
	
	return false;
	}
	return true;
}


bool CFrustum::LineInFrustum(float A[3], float B[3])
{
	float fa, fb;
	unsigned int i;

	for (i = 0; i<6; i++)
	{
		fa=frustum[i][0]*A[0] + frustum[i][1]*A[1] + frustum[i][2]*A[2] + frustum[i][3];
		fb=frustum[i][0]*B[0] + frustum[i][1]*B[1] + frustum[i][2]*B[2] + frustum[i][3];
		
		if(fa*fb < 0) return true;
	}
		return false;
}

bool CFrustum::TriangleInFrustum(float A[3], float B[3], float C[3])
{
	float fa, fb, fc;
	unsigned int i;

	for (i = 0; i<6; i++)
	{
		fa=frustum[i][0]*A[0] + frustum[i][1]*A[1] + frustum[i][2]*A[2] + frustum[i][3];
		fb=frustum[i][0]*B[0] + frustum[i][1]*B[1] + frustum[i][2]*B[2] + frustum[i][3];
		if(fa*fb < 0) return true;

		fb=frustum[i][0]*B[0] + frustum[i][1]*B[1] + frustum[i][2]*B[2] + frustum[i][3];
		fc=frustum[i][0]*C[0] + frustum[i][1]*C[1] + frustum[i][2]*C[2] + frustum[i][3];
		if(fb*fc < 0) return true;

		fc=frustum[i][0]*C[0] + frustum[i][1]*C[1] + frustum[i][2]*C[2] + frustum[i][3];
		fa=frustum[i][0]*A[0] + frustum[i][1]*A[1] + frustum[i][2]*A[2] + frustum[i][3];
		if(fc*fa < 0) return true;
	}

	return false;
}

bool CFrustum::RightParallelepipedInFrustum(float Min[3], float Max[3])
{
	////////////////////////////////////////////////////////////////////////
	// Return true when the right parallelpiped intersects with the view
	// Frustum. The parameter fSize has to be the width of the cube divided by two
	////////////////////////////////////////////////////////////////////////

	unsigned int i;//CurPlane

	for (i = 0; i<6; i++)
	{
		if (frustum[i][0]*Min[0]+frustum[i][1]*Max[1]+frustum[i][2]*Min[2]+frustum[i][3]>0)
			continue;
		if (frustum[i][0]*Min[0]+frustum[i][1]*Max[1]+frustum[i][2]*Max[2]+frustum[i][3]>0)
			continue;
		if (frustum[i][0]*Max[0]+frustum[i][1]*Max[1]+frustum[i][2]*Max[2]+frustum[i][3]>0)
			continue;
		if (frustum[i][0]*Max[0]+frustum[i][1]*Max[1]+frustum[i][2]*Min[2]+frustum[i][3]>0)
			continue;
		if (frustum[i][0]*Max[0]+frustum[i][1]*Min[1]+frustum[i][2]*Min[2]+frustum[i][3]>0)
			continue;
		if (frustum[i][0]*Max[0]+frustum[i][1]*Min[1]+frustum[i][2]*Max[2]+frustum[i][3]>0)
			continue;
		if (frustum[i][0]*Min[0]+frustum[i][1]*Min[1]+frustum[i][2]*Max[2]+frustum[i][3]>0)
			continue;
		if (frustum[i][0]*Min[0]+frustum[i][1]*Min[1]+frustum[i][2]*Min[2]+frustum[i][3]>0)
			continue;

		return false;
	}
	return true;
}

bool CFrustum::SphereInFrustum(float fPoint[3], float fRadius)
{
	////////////////////////////////////////////////////////////////////////
	// Return true when the sphere is inside the view Frustum. This is
	// the case when it is never further behind a any plane than its radius
	////////////////////////////////////////////////////////////////////////

	unsigned int iCurPlane;

	for (iCurPlane = 0; iCurPlane<6; iCurPlane++)
	{
		if (frustum[iCurPlane][0] * fPoint[0] + frustum[iCurPlane][1] * 
			fPoint[1] + frustum[iCurPlane][2] * fPoint[2] + frustum[iCurPlane][3] <= -fRadius)
		{
			return false;
		}
	}

   return true;
}

bool CFrustum::CubeInFrustum(float fPoint[], float fSize)
{
	////////////////////////////////////////////////////////////////////////
	// Return true when the cube intersects with the view Frustum. The
	// parameter fSize has to be the width of the cube divided by two
	////////////////////////////////////////////////////////////////////////

	unsigned int iCurPlane;

	for (iCurPlane = 0; iCurPlane<6; iCurPlane++)
	{
		if (frustum[iCurPlane][0] * (fPoint[0] - fSize) + frustum[iCurPlane][1] *
			(fPoint[1] - fSize) + frustum[iCurPlane][2] * (fPoint[2] - fSize) + 
			frustum[iCurPlane][3] > 0)
			continue;
		if (frustum[iCurPlane][0] * (fPoint[0] + fSize) + frustum[iCurPlane][1] * 
			(fPoint[1] - fSize) + frustum[iCurPlane][2] * (fPoint[2] - fSize) + 
			frustum[iCurPlane][3] > 0)
			continue;
		if (frustum[iCurPlane][0] * (fPoint[0] - fSize) + frustum[iCurPlane][1] * 
			(fPoint[1] + fSize) + frustum[iCurPlane][2] * (fPoint[2] - fSize) + 
			frustum[iCurPlane][3] > 0)
			continue;
		if (frustum[iCurPlane][0] * (fPoint[0] + fSize) + frustum[iCurPlane][1] * 
			(fPoint[1] + fSize) + frustum[iCurPlane][2] * (fPoint[2] - fSize) + 
			frustum[iCurPlane][3] > 0)
			continue;
		if (frustum[iCurPlane][0] * (fPoint[0] - fSize) + frustum[iCurPlane][1] * 
			(fPoint[1] - fSize) + frustum[iCurPlane][2] * (fPoint[2] + fSize) + 
			frustum[iCurPlane][3] > 0)
			continue;
		if (frustum[iCurPlane][0] * (fPoint[0] + fSize) + frustum[iCurPlane][1] * 
			(fPoint[1] - fSize) + frustum[iCurPlane][2] * (fPoint[2] + fSize) + 
			frustum[iCurPlane][3] > 0)
			continue;
		if (frustum[iCurPlane][0] * (fPoint[0] - fSize) + frustum[iCurPlane][1] * 
			(fPoint[1] + fSize) + frustum[iCurPlane][2] * (fPoint[2] + fSize) + 
			frustum[iCurPlane][3] > 0)
			continue;
		if (frustum[iCurPlane][0] * (fPoint[0] + fSize) + frustum[iCurPlane][1] * 
			(fPoint[1] + fSize) + frustum[iCurPlane][2] * (fPoint[2] + fSize) + 
			frustum[iCurPlane][3] > 0)
			continue;

		return false;
	}

	return true;
}

int CFrustum::CubeLocation(float fPoint[], float fSize)
{
	////////////////////////////////////////////////////////////////////////
	// Return FULL_OUTSIDE, PARTIAL_INSIDE or FULL_INSIDE. The parameter
	// fSize has to be the width of the cube divided by two
	////////////////////////////////////////////////////////////////////////

	unsigned int iCurPlane;
	int iCount1;
	int iCount2 = 0;

	for (iCurPlane = 0; iCurPlane<6; iCurPlane++)
	{
		iCount1 = 0;

		if (frustum[iCurPlane][0] * (fPoint[0] - fSize) + frustum[iCurPlane][1] * 
			(fPoint[1] - fSize) + frustum[iCurPlane][2] * (fPoint[2] - fSize) + 
			frustum[iCurPlane][3] > 0)
			iCount1++;
		if (frustum[iCurPlane][0] * (fPoint[0] + fSize) + frustum[iCurPlane][1] * 
			(fPoint[1] - fSize) + frustum[iCurPlane][2] * (fPoint[2] - fSize) + 
			frustum[iCurPlane][3] > 0)
			iCount1++;
		if (frustum[iCurPlane][0] * (fPoint[0] - fSize) + frustum[iCurPlane][1] * 
			(fPoint[1] + fSize) + frustum[iCurPlane][2] * (fPoint[2] - fSize) + 
			frustum[iCurPlane][3] > 0)
			iCount1++;
		if (frustum[iCurPlane][0] * (fPoint[0] + fSize) + frustum[iCurPlane][1] * 
			(fPoint[1] + fSize) + frustum[iCurPlane][2] * (fPoint[2] - fSize) + 
			frustum[iCurPlane][3] > 0)
			iCount1++;
		if (frustum[iCurPlane][0] * (fPoint[0] - fSize) + frustum[iCurPlane][1] * 
			(fPoint[1] - fSize) + frustum[iCurPlane][2] * (fPoint[2] + fSize) + 
			frustum[iCurPlane][3] > 0)
			iCount1++;
		if (frustum[iCurPlane][0] * (fPoint[0] + fSize) + frustum[iCurPlane][1] * 
			(fPoint[1] - fSize) + frustum[iCurPlane][2] * (fPoint[2] + fSize) + 
			frustum[iCurPlane][3] > 0)
			iCount1++;
		if (frustum[iCurPlane][0] * (fPoint[0] - fSize) + frustum[iCurPlane][1] * 
			(fPoint[1] + fSize) + frustum[iCurPlane][2] * (fPoint[2] + fSize) + 
			frustum[iCurPlane][3] > 0)
			iCount1++;
		if (frustum[iCurPlane][0] * (fPoint[0] + fSize) + frustum[iCurPlane][1] * 
			(fPoint[1] + fSize) + frustum[iCurPlane][2] * (fPoint[2] + fSize) + 
			frustum[iCurPlane][3] > 0)
			iCount1++;

	    if (iCount1 == 0)
			return FULL_OUTSIDE;

		if (iCount1 == 8)
			iCount2++;
   }

   return (iCount2 == 6) ? FULL_INSIDE : PARTIAL_INSIDE;
}

int CFrustum::SphereLocation(float fPoint[3], float fRadius)
{
	////////////////////////////////////////////////////////////////////////
	// Return FULL_OUTSIDE, PARTIAL_INSIDE or FULL_INSIDE to indicate the
	// position of the sphere
	////////////////////////////////////////////////////////////////////////

	unsigned int iCurPlane;
	int iCount = 0;
	float fDistance;

	for (iCurPlane=0; iCurPlane<6; iCurPlane++)
	{
		fDistance = frustum[iCurPlane][0] * fPoint[0] + frustum[iCurPlane][1] *
			fPoint[1] + frustum[iCurPlane][2] * fPoint[2] + frustum[iCurPlane][3];

		if (fDistance <= -fRadius)
			return FULL_OUTSIDE;

		if (fDistance > fRadius)
			iCount++;
   }

   return (iCount == 6) ? FULL_INSIDE : PARTIAL_INSIDE;
}