Logo Search packages:      
Sourcecode: egoboo version File versions  Download package

Frustum.c

//***********************************************************************//
//                   //
//  - "Talk to me like I'm a 3 year old!" Programming Lessons -   //
//                                                                       //
//  $Author:  DigiBen  digiben@gametutorials.com    //
//                   //
//  $Program:  Frustum Culling          //
//                   //
//  $Description: Demonstrates checking if shapes are in view   //
//                   //
//  $Date:   8/28/01            //
//                   //
//***********************************************************************//
#include "Frustum.h"
#include <SDL_opengl.h>
#include <math.h>

// We create an enum of the sides so we don't have to call each side 0 or 1.
// This way it makes it more understandable and readable when dealing with frustum sides.
typedef enum frustum_side_e
{
  RIGHT = 0,  // The RIGHT side of the frustum
  LEFT = 1,  // The LEFT  side of the frustum
  BOTTOM = 2,  // The BOTTOM side of the frustum
  TOP  = 3,  // The TOP side of the frustum
  BACK = 4,  // The BACK side of the frustum
  FRONT = 5   // The FRONT side of the frustum
} FrustumSide;

// Like above, instead of saying a number for the ABC and D of the plane, we
// want to be more descriptive.
typedef enum plane_data_t
{
  A = 0,    // The X value of the plane's normal
  B = 1,    // The Y value of the plane's normal
  C = 2,    // The Z value of the plane's normal
  D = 3    // The distance the plane is from the origin
} PlaneData;


Frustum gFrustum;


///////////////////////////////// NORMALIZE PLANE \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*
/////
///// This normalizes a plane (A side) from a given frustum.
/////
///////////////////////////////// NORMALIZE PLANE \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*

void NormalizePlane( Frustum *pf, FrustumSide side )
{
  // Here we calculate the magnitude of the normal to the plane (point A B C)
  // Remember that (A, B, C) is that same thing as the normal's (X, Y, Z).
  // To calculate magnitude you use the equation:  magnitude = sqrt( x^2 + y^2 + z^2)
  float magnitude = ( float ) sqrt( pf->planes[side][A] * pf->planes[side][A] +
                                    pf->planes[side][B] * pf->planes[side][B] +
                                    pf->planes[side][C] * pf->planes[side][C] );

  // Then we divide the plane's values by it's magnitude.
  // This makes it easier to work with.
  pf->planes[side][A] /= magnitude;
  pf->planes[side][B] /= magnitude;
  pf->planes[side][C] /= magnitude;
  pf->planes[side][D] /= magnitude;
};

///////////////////////////////// CALCULATE FRUSTUM \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*
/////
///// This extracts our frustum from the projection and modelview matrix.
/////
///////////////////////////////// CALCULATE FRUSTUM \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*

void Frustum_CalculateFrustum( Frustum *pf, float proj[], float modl[] )
{
  float clip[16];        // This will hold the clipping planes

  if ( NULL == proj || NULL == modl ) return;

  // store a copy of the projection matrix
  glMatrixMode( GL_PROJECTION );
  glPushMatrix();
  glLoadMatrixf( proj );

  // multiply the matrices
  glMultMatrixf( modl );

  // grab the matrix and place it in the matrix clip
  glGetFloatv( GL_PROJECTION_MATRIX, clip );

  // restore the old projection matrix
  glPopMatrix();

  // set the matrix mode to GL_MODELVIEW
  glMatrixMode( GL_MODELVIEW );

  //// glGetFloatv() is used to extract information about our OpenGL world.
  //// Below, we pass in GL_PROJECTION_MATRIX to abstract our projection matrix.
  //// It then stores the matrix into an array of [16].
  //glGetFloatv( GL_PROJECTION_MATRIX, proj );

  //// By passing in GL_MODELVIEW_MATRIX, we can abstract our model view matrix.
  //// This also stores it in an array of [16].
  //glGetFloatv( GL_MODELVIEW_MATRIX, modl );

  //// Now that we have our modelview and projection matrix, if we combine these 2 matrices,
  //// it will give us our clipping planes.  To combine 2 matrices, we multiply them.

  //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];

  // Now we actually want to get the sides of the frustum.  To do this we take
  // the clipping planes we received above and extract the sides from them.

  // This will extract the RIGHT side of the frustum
  pf->planes[RIGHT][A] = clip[ 3] - clip[ 0];
  pf->planes[RIGHT][B] = clip[ 7] - clip[ 4];
  pf->planes[RIGHT][C] = clip[11] - clip[ 8];
  pf->planes[RIGHT][D] = clip[15] - clip[12];

  // Now that we have a normal (A,B,C) and a distance (D) to the plane,
  // we want to normalize that normal and distance.

  // Normalize the RIGHT side
  NormalizePlane( pf, RIGHT );

  // This will extract the LEFT side of the frustum
  pf->planes[LEFT][A] = clip[ 3] + clip[ 0];
  pf->planes[LEFT][B] = clip[ 7] + clip[ 4];
  pf->planes[LEFT][C] = clip[11] + clip[ 8];
  pf->planes[LEFT][D] = clip[15] + clip[12];

  // Normalize the LEFT side
  NormalizePlane( pf, LEFT );

  // This will extract the BOTTOM side of the frustum
  pf->planes[BOTTOM][A] = clip[ 3] + clip[ 1];
  pf->planes[BOTTOM][B] = clip[ 7] + clip[ 5];
  pf->planes[BOTTOM][C] = clip[11] + clip[ 9];
  pf->planes[BOTTOM][D] = clip[15] + clip[13];

  // Normalize the BOTTOM side
  NormalizePlane( pf, BOTTOM );

  // This will extract the TOP side of the frustum
  pf->planes[TOP][A] = clip[ 3] - clip[ 1];
  pf->planes[TOP][B] = clip[ 7] - clip[ 5];
  pf->planes[TOP][C] = clip[11] - clip[ 9];
  pf->planes[TOP][D] = clip[15] - clip[13];

  // Normalize the TOP side
  NormalizePlane( pf, TOP );

  // This will extract the BACK side of the frustum
  pf->planes[BACK][A] = clip[ 3] - clip[ 2];
  pf->planes[BACK][B] = clip[ 7] - clip[ 6];
  pf->planes[BACK][C] = clip[11] - clip[10];
  pf->planes[BACK][D] = clip[15] - clip[14];

  // Normalize the BACK side
  NormalizePlane( pf, BACK );

  // This will extract the FRONT side of the frustum
  pf->planes[FRONT][A] = clip[ 3] + clip[ 2];
  pf->planes[FRONT][B] = clip[ 7] + clip[ 6];
  pf->planes[FRONT][C] = clip[11] + clip[10];
  pf->planes[FRONT][D] = clip[15] + clip[14];

  // Normalize the FRONT side
  NormalizePlane( pf, FRONT );
}

// The code below will allow us to make checks within the frustum.  For example,
// if we want to see if a point, a sphere, or a cube lies inside of the frustum.
// Because all of our planes point INWARDS (The normals are all pointing inside the frustum)
// we then can assume that if a point is in FRONT of all of the planes, it's inside.

///////////////////////////////// POINT IN FRUSTUM \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*
/////
///// This determines if a point is inside of the frustum
/////
///////////////////////////////// POINT IN FRUSTUM \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*

bool_t Frustum_PointInFrustum( Frustum *pf, float pos[] )
{
  // If you remember the plane equation (A*pos[0] + B*pos[1] + C*pos[2] + D = 0), then the rest
  // of this code should be quite obvious and easy to figure out yourself.
  // In case don't know the plane equation, it might be a good idea to look
  // at our Plane Collision tutorial at www.GameTutorials.com in OpenGL Tutorials.
  // I will briefly go over it here.  (A,B,C) is the (X,Y,Z) of the normal to the plane.
  // They are the same thing... but just called ABC because you don't want to say:
  // (pos[0]*pos[0] + pos[1]*pos[1] + pos[2]*pos[2] + d = 0).  That would be wrong, so they substitute them.
  // the (pos[0], pos[1], pos[2]) in the equation is the point that you are testing.  The D is
  // The distance the plane is from the origin.  The equation ends with "= 0" because
  // that is btrue when the point (pos[0], pos[1], pos[2]) is ON the plane.  When the point is NOT on
  // the plane, it is either a negative number (the point is behind the plane) or a
  // positive number (the point is in front of the plane).  We want to check if the point
  // is in front of the plane, so all we have to do is go through each point and make
  // sure the plane equation goes out to a positive number on each side of the frustum.
  // The result (be it positive or negative) is the distance the point is front the plane.

  int i;

  if ( NULL == pos ) return bfalse;

  // Go through all the sides of the frustum
  for ( i = 0; i < 6; i++ )
  {
    // Calculate the plane equation and check if the point is behind a side of the frustum
    if ( pf->planes[i][A] * pos[0] + pf->planes[i][B] * pos[1] + pf->planes[i][C] * pos[2] + pf->planes[i][D] <= 0 )
    {
      // The point was behind a side, so it ISN'T in the frustum
      return bfalse;
    }
  }

  // The point was inside of the frustum (In front of ALL the sides of the frustum)
  return btrue;
}


///////////////////////////////// SPHERE IN FRUSTUM \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*
/////
///// This determines if a sphere is inside of our frustum by it's center and radius.
/////
///////////////////////////////// SPHERE IN FRUSTUM \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*

bool_t Frustum_SphereInFrustum( Frustum *pf, float pos[], float radius )
{
  // Now this function is almost identical to the PointInFrustum(), except we
  // now have to deal with a radius around the point.  The point is the center of
  // the radius.  So, the point might be outside of the frustum, but it doesn't
  // mean that the rest of the sphere is.  It could be half and half.  So instead of
  // checking if it's less than 0, we need to add on the radius to that.  Say the
  // equation produced -2, which means the center of the sphere is the distance of
  // 2 behind the plane.  Well, what if the radius was 5?  The sphere is still inside,
  // so we would say, if(-2 < -5) then we are outside.  In that case it's bfalse,
  // so we are inside of the frustum, but a distance of 3.  This is reflected below.

  int i;

  if ( NULL == pos ) return bfalse;

  // Go through all the sides of the frustum
  for ( i = 0; i < 6; i++ )
  {
    // If the center of the sphere is farther away from the plane than the radius
    if ( pf->planes[i][A] * pos[0] + pf->planes[i][B] * pos[1] + pf->planes[i][C] * pos[2] + pf->planes[i][D] <= -radius )
    {
      // The distance was greater than the radius so the sphere is outside of the frustum
      return bfalse;
    }
  }

  // The sphere was inside of the frustum!
  return btrue;
}


///////////////////////////////// CUBE IN FRUSTUM \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*
/////
///// This determines if a cube is in or around our frustum by it's center and 1/2 it's length
/////
///////////////////////////////// CUBE IN FRUSTUM \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*

bool_t Frustum_CubeInFrustum( Frustum *pf, float pos[], float size )
{
  // This test is a bit more work, but not too much more complicated.
  // Basically, what is going on is, that we are given the center of the cube,
  // and half the length.  Think of it like a radius.  Then we checking each point
  // in the cube and seeing if it is inside the frustum.  If a point is found in front
  // of a side, then we skip to the next side.  If we get to a plane that does NOT have
  // a point in front of it, then it will return bfalse.

  // *Note* - This will sometimes say that a cube is inside the frustum when it isn't.
  // This happens when all the corners of the bounding box are not behind any one plane.
  // This is rare and shouldn't effect the overall rendering speed.

  int i;

  if ( NULL == pos ) return bfalse;

  for ( i = 0; i < 6; i++ )
  {
    if ( pf->planes[i][A] * ( pos[0] - size ) + pf->planes[i][B] * ( pos[1] - size ) + pf->planes[i][C] * ( pos[2] - size ) + pf->planes[i][D] > 0 )
      continue;
    if ( pf->planes[i][A] * ( pos[0] + size ) + pf->planes[i][B] * ( pos[1] - size ) + pf->planes[i][C] * ( pos[2] - size ) + pf->planes[i][D] > 0 )
      continue;
    if ( pf->planes[i][A] * ( pos[0] - size ) + pf->planes[i][B] * ( pos[1] + size ) + pf->planes[i][C] * ( pos[2] - size ) + pf->planes[i][D] > 0 )
      continue;
    if ( pf->planes[i][A] * ( pos[0] + size ) + pf->planes[i][B] * ( pos[1] + size ) + pf->planes[i][C] * ( pos[2] - size ) + pf->planes[i][D] > 0 )
      continue;
    if ( pf->planes[i][A] * ( pos[0] - size ) + pf->planes[i][B] * ( pos[1] - size ) + pf->planes[i][C] * ( pos[2] + size ) + pf->planes[i][D] > 0 )
      continue;
    if ( pf->planes[i][A] * ( pos[0] + size ) + pf->planes[i][B] * ( pos[1] - size ) + pf->planes[i][C] * ( pos[2] + size ) + pf->planes[i][D] > 0 )
      continue;
    if ( pf->planes[i][A] * ( pos[0] - size ) + pf->planes[i][B] * ( pos[1] + size ) + pf->planes[i][C] * ( pos[2] + size ) + pf->planes[i][D] > 0 )
      continue;
    if ( pf->planes[i][A] * ( pos[0] + size ) + pf->planes[i][B] * ( pos[1] + size ) + pf->planes[i][C] * ( pos[2] + size ) + pf->planes[i][D] > 0 )
      continue;

    // If we get here, it isn't in the frustum
    return bfalse;
  }

  return btrue;
}

bool_t Frustum_BBoxInFrustum( Frustum *pf, float corner1[], float corner2[] )
{
  int i;

  if ( NULL == corner1 || NULL == corner2 ) return btrue;

  for ( i = 0; i < 6; i++ )
  {
    if ( pf->planes[i][A] * corner1[0] + pf->planes[i][B] * corner1[1] + pf->planes[i][C] * corner1[2] + pf->planes[i][D] > 0 )
      continue;
    if ( pf->planes[i][A] * corner1[0] + pf->planes[i][B] * corner1[1] + pf->planes[i][C] * corner2[2] + pf->planes[i][D] > 0 )
      continue;
    if ( pf->planes[i][A] * corner1[0] + pf->planes[i][B] * corner2[1] + pf->planes[i][C] * corner1[2] + pf->planes[i][D] > 0 )
      continue;
    if ( pf->planes[i][A] * corner1[0] + pf->planes[i][B] * corner2[1] + pf->planes[i][C] * corner2[2] + pf->planes[i][D] > 0 )
      continue;
    if ( pf->planes[i][A] * corner2[0] + pf->planes[i][B] * corner1[1] + pf->planes[i][C] * corner1[2] + pf->planes[i][D] > 0 )
      continue;
    if ( pf->planes[i][A] * corner2[0] + pf->planes[i][B] * corner1[1] + pf->planes[i][C] * corner2[2] + pf->planes[i][D] > 0 )
      continue;
    if ( pf->planes[i][A] * corner2[0] + pf->planes[i][B] * corner2[1] + pf->planes[i][C] * corner1[2] + pf->planes[i][D] > 0 )
      continue;
    if ( pf->planes[i][A] * corner2[0] + pf->planes[i][B] * corner2[1] + pf->planes[i][C] * corner2[2] + pf->planes[i][D] > 0 )
      continue;

    // If we get here, it isn't in the frustum
    return bfalse;
  }

  return btrue;
};


/////////////////////////////////////////////////////////////////////////////////
//
// * QUICK NOTES *
//
// WOZZERS!  That seemed like an incredible amount to look at, but if you break it
// down, it's not.  Frustum culling is a VERY useful thing when it comes to 3D.
// If you want a large world, there is no way you are going to send it down the
// 3D pipeline every frame and let OpenGL take care of it for you.  That would
// give you a 0.001 frame rate.  If you hit '+' and bring the sphere count up to
// 1000, then take off culling, you will see the HUGE difference it makes.
// Also, you wouldn't really be rendering 1000 spheres.  You would most likely
// use the sphere code for larger objects.  Let me explain.  Say you have a bunch
// of objects, well... all you need to do is give the objects a radius, and then
// test that radius against the frustum.  If that sphere is in the frustum, then you
// render that object.  Also, you won't be rendering a high poly sphere so it won't
// be so slow.  This goes for bounding box's too (Cubes).  If you don't want to
// do a cube, it is really easy to convert the code for rectangles.  Just pass in
// a width and height, instead of just a length.  Remember, it's HALF the length of
// the cube, not the full length.  So it would be half the width and height for a rect.
//
// This is a perfect starter for an octree tutorial.  Wrap you head around the concepts
// here and then see if you can apply this to making an octree.  Hopefully we will have
// a tutorial up and running for this subject soon.  Once you have frustum culling,
// the next step is getting space partitioning.  Either it being a BSP tree of an Octree.
//
// Let's go over a brief overview of the things we learned here:
//
// 1) First we need to abstract the frustum from OpenGL.  To do that we need the
//    projection and modelview matrix.  To get the projection matrix we use:
//
//   glGetFloatv( GL_PROJECTION_MATRIX, /* An Array of 16 floats */ );
//    Then, to get the modelview matrix we use:
//
//   glGetFloatv( GL_MODELVIEW_MATRIX, /* An Array of 16 floats */ );
//
//   These 2 functions gives us an array of 16 floats (The matrix).
//
// 2) Next, we need to combine these 2 matrices.  We do that by matrix multiplication.
//
// 3) Now that we have the 2 matrixes combined, we can abstract the sides of the frustum.
//    This will give us the normal and the distance from the plane to the origin (ABC and D).
//
// 4) After abstracting a side, we want to normalize the plane data.  (A B C and D).
//
// 5) Now we have our frustum, and we can check points against it using the plane equation.
//    Once again, the plane equation (A*x + B*y + C*z + D = 0) says that if, point (X,Y,Z)
//    times the normal of the plane (A,B,C), plus the distance of the plane from origin,
//    will equal 0 if the point (X, Y, Z) lies on that plane.  If it is behind the plane
//    it will be a negative distance, if it's in front of the plane (the way the normal is facing)
//    it will be a positive number.
//
//
// If you need more help on the plane equation and why this works, download our
// Ray Plane Intersection Tutorial at www.GameTutorials.com.
//
// That's pretty much it with frustums.  There is a lot more we could talk about, but
// I don't want to complicate this tutorial more than I already have.
//
// I want to thank Mark Morley for his tutorial on frustum culling.  Most of everything I got
// here comes from his teaching.  If you want more in-depth, visit his tutorial at:
//
// http://www.markmorley.com/opengl/frustumculling.html
//
// Good luck!
//
//
// Ben Humphrey (DigiBen)
// Game Programmer
// DigiBen@GameTutorials.com
// Co-Web Host of www.GameTutorials.com
//
//


Generated by  Doxygen 1.6.0   Back to index