BASIC

Author Topic: Frustum checking code  (Read 2038 times)

Offline bigsofty

  • Community Developer
  • Prof. Inline
  • ******
  • Posts: 2510
    • View Profile
Frustum checking code
« on: 2012-Aug-27 »
Here is some code for checking if you have a point or bounding sphere within your viewing frustum(on your screen). Most just return a boolean but IsSphereInFrustum2() returns the distance it is from your screen too.

Code: GLBasic [Select]
INLINE
typedef unsigned int    GLenum;
typedef float           GLfloat;

#define GL_PROJECTION_MATRIX                    0x0BA7
#define GL_MODELVIEW_MATRIX                     0x0BA6
} extern "C" { void __stdcall glGetFloatv( GLenum pname , GLfloat *params );; }; namespace __GLBASIC__ {

float frustum[6][4];

void ExtractFrustum()
{
   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 = SQR( 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 = SQR( 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 = SQR( 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 = SQR( 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 = SQR( 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 = SQR( 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 PointInFrustum( float x, float y, float z )
{
   int p;

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

bool SphereInFrustum1( float x, float y, float z, float radius )
{
   int p;

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

float SphereInFrustum2( float x, float y, float z, float radius )
{
   int p;
   float d;

   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 )
         return 0;
   }
   return d + radius;
}
ENDINLINE

FUNCTION CalcFrustum:
        INLINE
                ExtractFrustum();
        ENDINLINE
ENDFUNCTION

FUNCTION IsPointInFrustum%: x#,y#,z#
        INLINE
                return PointInFrustum( x,y,z );
        ENDINLINE
ENDFUNCTION

FUNCTION IsSphereInFrustum1%: x#,y#,z#,r#
        INLINE
                return SphereInFrustum1( x,y,z,r );
        ENDINLINE
ENDFUNCTION

FUNCTION IsSphereInFrustum2#: x#,y#,z#,r#
        INLINE
                return SphereInFrustum2( x,y,z,r );
        ENDINLINE
ENDFUNCTION

Just paste this into your project and it should work. I should say, that appart from a quick compile for errors this is untested.

There are 4 functions above...
   FUNCTION CalcFrustum:
   FUNCTION IsPointInFrustum%: x#,y#,z#
   FUNCTION IsSphereInFrustum1%: x#,y#,z#,r#
   FUNCTION IsSphereInFrustum2#: x#,y#,z#,r#


This is the main frustum calculation routine.
CalcFrustum()

Call this once per game loop to update the frustum calculation.


These are the test routines.
IsPointInFrustum()

Returns True if a point in within the frustum.

IsSphereInFrustum1()

Returns True is a sphere with radius of 'r#' is within the frustum.

IsSphereInFrustum2()

Returns False if your sphere is not within frustum, else it returns the distance from the front plane to the sphere. Handy for LoD calculations for example.


These are now tested and it seems fine.
« Last Edit: 2012-Aug-29 by bigsofty »
Cheers,

Ian.

“It is practically impossible to teach good programming style to students that have had prior exposure to BASIC.  As potential programmers, they are mentally mutilated beyond hope of regeneration.”
(E. W. Dijkstra)

Offline bigsofty

  • Community Developer
  • Prof. Inline
  • ******
  • Posts: 2510
    • View Profile
Re: Frustum checking code
« Reply #1 on: 2012-Aug-29 »
Whoops, I just noticed that the end of the first message said that it would not compile(now edited) but it did. Serves me right for just lazily copying text from the old thread where it was broken.  :S
« Last Edit: 2012-Aug-29 by bigsofty »
Cheers,

Ian.

“It is practically impossible to teach good programming style to students that have had prior exposure to BASIC.  As potential programmers, they are mentally mutilated beyond hope of regeneration.”
(E. W. Dijkstra)

Offline kanonet

  • Administrator
  • Prof. Inline
  • *******
  • Posts: 1142
    • View Profile
    • My GLBasic code archiv
Re: Frustum checking code
« Reply #2 on: 2012-Aug-30 »
Did you write a test project to see if the frustum calculation is correct? I would like to play with this but i have no time to write my own, so it would be nice if you could send me your test project, thank you.
Lenovo Thinkpad T430u: Intel i5-3317U, 8GB DDR3, NVidia GeForce 620M, Micron RealSSD C400 @Win7 x64

Offline bigsofty

  • Community Developer
  • Prof. Inline
  • ******
  • Posts: 2510
    • View Profile
Re: Frustum checking code
« Reply #3 on: 2012-Aug-30 »
TBH Christoph, I just I inserted the code into my game engine. Added a CalcFrustum() in my main loop directly after the camera transform. Then created a sphere mesh, with a certain radius. Then proceeded to rotate the camera around the meshes separate axises and then also I rotated the mesh around the camera frustum too. The code seemed to work as expected, detecting the mesh entering or leaving the frustum accurately. The only proviso is that I don't use the GL import code here as I import gl.h directly into my inlined C, to do this you woul need the extra GLBasic C header pack and extra link directives. So I added the quick GL import code so that anyone could use the code, irregardless of their setup.
Cheers,

Ian.

“It is practically impossible to teach good programming style to students that have had prior exposure to BASIC.  As potential programmers, they are mentally mutilated beyond hope of regeneration.”
(E. W. Dijkstra)