Sign in to follow this  
dvdr

frustum culling with octrees

Recommended Posts

Hello! I'm trying to use octrees to implement frustum culling for my c++/opengl game. First of all, I divide the space and I get the correct cubes of the octree. Then I need to determine which cubes are inside the view. To do that, I extract the planes of the frustum:
void extractPlanes()
{
	float mv[4][4];
	float p[4][4];
	float pi[16], mvi[16], res[4][4];
	int i, j;

	glGetFloatv(GL_MODELVIEW_MATRIX, mvi);
	glGetFloatv(GL_PROJECTION_MATRIX, pi);

	//Transpose both matrices MODELVIEW & PROJECTION
	int k = 0;
	for(j=0;j<4;j++)
	{
		for(i=0;i<4;i++)
		{
			p[i][j] = pi[k];
			mv[i][j] = mvi[k];
			res[i][j] = 0;
			k++;
		}
		
	}

	//Multiply the 2 matrix MODELVIEW * PROJECTION
	for(i=0;i<4;i++)
	{
		for(j=0;j<4;j++)
		{ 
			for(k=0;k<4;k++)
				res[i][j]+= mv[i][k]*p[k][j];
		}
	} 

	//Find the planes
	//Left
	planes[0][0] = res[3][0] + res[0][0];
	planes[0][1] = res[3][1] + res[0][1];
	planes[0][2] = res[3][2] + res[0][2];
	planes[0][3] = res[3][3] + res[0][3];
	normPlane(0);

	//Right
	planes[1][0] = res[3][0] - res[0][0];
	planes[1][1] = res[3][1] - res[0][1];
	planes[1][2] = res[3][2] - res[0][2];
	planes[1][3] = res[3][3] - res[0][3];
	normPlane(1);

	//Bottom
	planes[2][0] = res[3][0] + res[1][0];
	planes[2][1] = res[3][1] + res[1][1];
	planes[2][2] = res[3][2] + res[1][2];
	planes[2][3] = res[3][3] + res[1][3];
	normPlane(2);

	//Top
	planes[3][0] = res[3][0] - res[1][0];
	planes[3][1] = res[3][1] - res[1][1];
	planes[3][2] = res[3][2] - res[1][2];
	planes[3][3] = res[3][3] - res[1][3];
	normPlane(3);

	//Near
	planes[4][0] = res[3][0] + res[2][0];
	planes[4][1] = res[3][1] + res[2][1];
	planes[4][2] = res[3][2] + res[2][2];
	planes[4][3] = res[3][3] + res[2][3];
	normPlane(4);

	//Far
	planes[5][0] = res[3][0] - res[2][0];
	planes[5][1] = res[3][1] - res[2][1];
	planes[5][2] = res[3][2] - res[2][2];
	planes[5][3] = res[3][3] - res[2][3];
	normPlane(5);
	
}

Then for each cube of the octree, I try to determine if any of its vertices is inside the frustum view:
bool cubeInFrustum(V* v)
{
	int i,j,count;

	for(i=0;i<6;i++)
	{
		count = 8;
		for(j=0;j<8;j++)
		{
			//If this point is outside this plane
			if((planes[i][0]*v[j].x+planes[i][1]*v[j].y+planes[i][2]*v[j].z+planes[i][3]) < 0)
				count--;
		}
		//If the 8 points are outside the plane
		if(count == 0)
			return false;
	}
	return true;
}

Unfortunately, I don't get the expected results. Does anyone see something wrong? Thank you!

Share this post


Link to post
Share on other sites
What are the expected/unexpected results?

Also, your algorithm might not work quite as expected because it doesn't cater for the case where you can have all vertices of the cube outside the frustrum but still be able to see it because one of its faces intersects it.

Share this post


Link to post
Share on other sites
Quote:
Also, your algorithm might not work quite as expected because it doesn't cater for the case where you can have all vertices of the cube outside the frustrum but still be able to see it because one of its faces intersects it.
I'm not sure that's the case. From looking at the code it looks like the box is culled if all eight vertices fall behind one of the frustum planes, in which case there shouldn't be any false negatives. (There are more direct ways to perform the AABB-plane test than checking all eight corners individually, but the 'eight corners' test should work.)

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this