Frustum Culling!

Started by
2 comments, last by sirSolarius 20 years, 3 months ago
I'm having some serious issues with my frustum culling... it's culling objects that should be on the screen (and whose drawn bounding spheres ARE on screen!!). Please take a look: Frustum class:

Frustum::Frustum()
{
	getFrustum();
}

Frustum::~Frustum()
{
}

void Frustum::getFrustum()
{
   float   proj[16];
   float   modl[16];
   float   clip[16];
   float   t;

   /* Get the current PROJECTION matrix from OpenGL */
   glGetFloatv( GL_PROJECTION_MATRIX, proj );

   /* Get the current MODELVIEW matrix from OpenGL */
   glGetFloatv( GL_MODELVIEW_MATRIX, modl );

   /* Combine the two matrices (multiply projection by modelview) */
   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 numbers for the RIGHT 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 the result */
   t = 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 numbers for the LEFT 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 the result */
   t = 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 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 the result */
   t = 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 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 the result */
   t = 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 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 the result */
   t = 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 plane */
   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 the result */
   t = 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;
}

int Frustum::sphereInFrustum(float x, float y, float z, float radius )
{
	ofstream logger("frustumLog.txt", ios::app);
	logger << "Checking sphere at (" << x << ", " << y << ", " << z << ") with radius: " << radius << endl;;
	int p;
   float d;
   int planesCleared=0;

   for( p = 0; p < 6; p++ )
   {
      d = frustum[p][0] * x + frustum[p][1] * y + frustum[p][2] * z + 
		  frustum[p][3];
      if( d <= -radius )
	  {
		logger << "Failed on plane " << p << " @ distance " << d << endl;
		logger.close();
		  return 0;
	  }
	  if (d>=radius)
	  {
		  planesCleared++;
	  }
   }
   if(planesCleared==6)
   {
	   logger << "Cleared all planes!" << endl;
	   logger.close();
	   return 2;
   }
   else
   {
	   logger.close();
	   return 1;
   }
   
}


The box class:
   
void Box::calcBounding()
{
	if(length >= height && length >= width)
		boundingRadius=length;
	else if(height >= length && height >= width)
		boundingRadius=height;
	else
		boundingRadius=width;

}


The linked list of scene objects (ie drawing code):
   
void ObjectList::drawObjects(Camera *cam)
{
	Object* current=head;
	int x =0;
	glInitNames();
	glPushName(0);
	while(current !=NULL)
	{
		// Draw the bounding sphere

			glLoadIdentity();
			cam->draw();
			glColor4f(1.0f,1.0f,0.0f,0.8f);	// Full Brightness, 50% Alpha ( NEW )

			glEnable(GL_BLEND);			// Turn Blending On

			glDisable(GL_DEPTH_TEST);
			glTranslatef(current->getX(), current->getY(), current->getZ());
			auxSolidSphere(current->getBoundingRadius());
			glDisable(GL_BLEND);			// Turn Blending On

			glEnable(GL_DEPTH_TEST);
			glColor4f(1.0f,1.0f,1.0f,1.0f);
		// End bounding sphere


		if(cam->viewFrust.sphereInFrustum(current->getX(), current->getY(), current->getZ(), 
			current->getBoundingRadius()) !=0 )
		{
			x++;
			glLoadIdentity();
			glPushMatrix();
			(*cam).draw();		// Set the viewpoint

			glLoadName(x);
		
			(*current).draw();	// Draw the object

			glPopMatrix();
		}
		current=(*current).getNext();	// Move to the next object

	}
}


And last but not least, the actual engine code:
   
//init         

Box *boxer=new Box(2.0f, 2.0f, 2.0f);
boxer->setColors(0.0f, 1.0f, 0.0f);
	lister.setHead(boxer);
	Box *boxest = new Box(0.5f, 0.5f, 0.5f);
	boxest->setColors(1.0f, 0.0f, 1.0f);
         boxest->move(-3.0f, 3.0f, 1.0f);
	lister.addItem(boxest);


And the output that I get when running the program and constantly moving around:
   
Checking sphere at (0, 0, 0) with radius: 2
Checking sphere at (-3, 3, 1) with radius: 0.5
Checking sphere at (0, 0, 0) with radius: 2
Checking sphere at (-3, 3, 1) with radius: 0.5
Failed on plane 1 @ distance -2.62611
Checking sphere at (0, 0, 0) with radius: 2
Checking sphere at (-3, 3, 1) with radius: 0.5
Failed on plane 1 @ distance -2.62611
Checking sphere at (0, 0, 0) with radius: 2
Checking sphere at (-3, 3, 1) with radius: 0.5
Failed on plane 1 @ distance -2.62611
Checking sphere at (0, 0, 0) with radius: 2
Checking sphere at (-3, 3, 1) with radius: 0.5
Failed on plane 1 @ distance -2.62611
//Repeat pattern of last three lines until EOF

I'm so confused!! Any help is greatly appreciated! Edit: I can see both drawn bounding spheres during the entire run of the program [edited by - sirSolarius on January 18, 2004 2:41:13 PM]
Advertisement
If that code is from Mark Morley, I can tell you that the original code works. (And if so, you should give credit in your code to its source.)
Ok, I *think* I know the problem. I think it has something to do with my camera rotation... that the X, Y, Z points need to be rotated by the camera rotation before comparing them with the view frustrum.

How could I go about doing that with an (x,y,z) point and an (x,y,z) rotation? Or will the frustrum extration do that for me?

Edit: for clarification, I'm basing this theory on the fact that any object placed at (0,0,0) is not culled.

[edited by - sirSolarius on January 18, 2004 12:22:48 AM]
hmm.. without looking to closely.. you are extracting all those planes AFTER setting your view (glulookat or whatever) and the coords you are testing with are in woorld coordinates and not local?
f@dzhttp://festini.device-zero.de

This topic is closed to new replies.

Advertisement