GLQuake - Frustum Plane Extraction

[mh]

This is an alternative to Quake's R_SetFrustum function. It's not necessarily better or faster, but it does give the exact frustum as defined by the current modelview and projection matrixes, which can be useful if you ever decide to mangle them (see for example my alternative underwater warp code: viewtopic.php?t=2617). Otherwise it gives the same results as R_SetFrustum, and for all practical purposes is no different.

Assumptions: (1) both the modelview and projection matrixes are available in float arrays. Use glGetFloatv on them if not. (2) You have a function that will multiply two matrixes together and store the result in a third (called something like "GL_MultiplyMatrix"). Look on Google for sample code if you don't.

No other changes are needed aside from removing the call to R_SetFrustum and inserting a call to this one somewhere after you call to R_SetupGL.

Code: Select all

void R_ExtractFrustum (void)
{
    int i;
    float r_mvp_matrix[16];

    // get the frustum from the actual matrixes that were used
    GL_MultiplyMatrix (r_mvp_matrix, r_world_matrix, r_projection_matrix);

    // right
    frustum[0].normal[0] = r_mvp_matrix[3] - r_mvp_matrix[0];
    frustum[0].normal[1] = r_mvp_matrix[7] - r_mvp_matrix[4];
    frustum[0].normal[2] = r_mvp_matrix[11] - r_mvp_matrix[8];

    // left
    frustum[1].normal[0] = r_mvp_matrix[3] + r_mvp_matrix[0];
    frustum[1].normal[1] = r_mvp_matrix[7] + r_mvp_matrix[4];
    frustum[1].normal[2] = r_mvp_matrix[11] + r_mvp_matrix[8];

    // bottom
    frustum[2].normal[0] = r_mvp_matrix[3] + r_mvp_matrix[1];
    frustum[2].normal[1] = r_mvp_matrix[7] + r_mvp_matrix[5];
    frustum[2].normal[2] = r_mvp_matrix[11] + r_mvp_matrix[9];

    // top
    frustum[3].normal[0] = r_mvp_matrix[3] - r_mvp_matrix[1];
    frustum[3].normal[1] = r_mvp_matrix[7] - r_mvp_matrix[5];
    frustum[3].normal[2] = r_mvp_matrix[11] - r_mvp_matrix[9];

    for (i = 0; i < 4; i++)
    {
        VectorNormalize (frustum[i].normal);

        frustum[i].type = PLANE_ANYZ;
        frustum[i].dist = DotProduct (r_origin, frustum[i].normal);
        frustum[i].signbits = SignbitsForPlane (&frustum[i]);
    }
}

[revelator]

nice

i remember i seen this function somewhere GL_MultiplyMatrix but for the life of me i cant remember where. do you have the code for it somewhere ?

[mh]

Here's one possible version:

Code: Select all

// note - param order reversed to be the same as D3D...
float *GL_MultiplyMatrix (float *out, float *m2, float *m1)
{
    float tmp[16];

    // do it this way because either of m1 or m2 might be the same as out...
    tmp[0]  = m1[0] * m2[0] + m1[4] * m2[1] + m1[8] * m2[2] + m1[12] * m2[3];
    tmp[1]  = m1[1] * m2[0] + m1[5] * m2[1] + m1[9] * m2[2] + m1[13] * m2[3];
    tmp[2]  = m1[2] * m2[0] + m1[6] * m2[1] + m1[10] * m2[2] + m1[14] * m2[3];
    tmp[3]  = m1[3] * m2[0] + m1[7] * m2[1] + m1[11] * m2[2] + m1[15] * m2[3];

    tmp[4]  = m1[0] * m2[4] + m1[4] * m2[5] + m1[8] * m2[6] + m1[12] * m2[7];
    tmp[5]  = m1[1] * m2[4] + m1[5] * m2[5] + m1[9] * m2[6] + m1[13] * m2[7];
    tmp[6]  = m1[2] * m2[4] + m1[6] * m2[5] + m1[10] * m2[6] + m1[14] * m2[7];
    tmp[7]  = m1[3] * m2[4] + m1[7] * m2[5] + m1[11] * m2[6] + m1[15] * m2[7];

    tmp[8]  = m1[0] * m2[8] + m1[4] * m2[9] + m1[8] * m2[10] + m1[12] * m2[11];
    tmp[9]  = m1[1] * m2[8] + m1[5] * m2[9] + m1[9] * m2[10] + m1[13] * m2[11];
    tmp[10] = m1[2] * m2[8] + m1[6] * m2[9] + m1[10] * m2[10] + m1[14] * m2[11];
    tmp[11] = m1[3] * m2[8] + m1[7] * m2[9] + m1[11] * m2[10] + m1[15] * m2[11];

    tmp[12] = m1[0] * m2[12] + m1[4] * m2[13] + m1[8] * m2[14] + m1[12] * m2[15];
    tmp[13] = m1[1] * m2[12] + m1[5] * m2[13] + m1[9] * m2[14] + m1[13] * m2[15];
    tmp[14] = m1[2] * m2[12] + m1[6] * m2[13] + m1[10] * m2[14] + m1[14] * m2[15];
    tmp[15] = m1[3] * m2[12] + m1[7] * m2[13] + m1[11] * m2[14] + m1[15] * m2[15];

    out[0] = tmp[0]; out[1] = tmp[1]; out[2] = tmp[2]; out[3] = tmp[3];
    out[4] = tmp[4]; out[5] = tmp[5]; out[6] = tmp[6]; out[7] = tmp[7];
    out[8] = tmp[8]; out[9] = tmp[9]; out[10] = tmp[10]; out[11] = tmp[11];
    out[12] = tmp[12]; out[13] = tmp[13]; out[14] = tmp[14]; out[15] = tmp[15];

    return out;
}

You'll more commonly see it in a loop though, something like this:

Code: Select all

void D3D_MultMatrix (D3DMATRIX *matrixout, D3DMATRIX *matrix1, D3DMATRIX *matrix2)
{
    // because one of the input matrixes is allowed in d3dx to be the same as the output
    // we initially multiply into a temp copy
    D3DMATRIX matrixtmp;

    for (int i = 0; i < 4; i++)
    {
        for (int j = 0; j < 4; j++)
        {
            matrixtmp.m[i][j] = matrix1->m[i][0] * matrix2->m[0][j] +
                                matrix1->m[i][1] * matrix2->m[1][j] +
                                matrix1->m[i][2] * matrix2->m[2][j] +
                                matrix1->m[i][3] * matrix2->m[3][j];
        }
    }

    memcpy (matrixout, &matrixtmp, sizeof (D3DMATRIX));
}

[revelator]

i did something like this but will try yours

Code: Select all

void GL_MultiplyMatrix(float a[16], float b[16], float result[16])
{
   int      i, j;
   float   sum;

   for (i=0; i<4; i++)
   {
        sum = 0;

       for (j=0; j<4; j++)
      {
         sum += a[i] * b[j];
        }
        result[i] = sum;
    }
}

allthough i get a rather weird effect if i use the global matrixes.

[revelator]

small refinement

Code: Select all

void R_ExtractFrustum (void)
{
    int     i;
   float   proj[16];
   float   modl[16];
   float   clip[16];

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

    // right
    frustum[0].normal[0] = clip[3] - clip[0];
    frustum[0].normal[1] = clip[7] - clip[4];
    frustum[0].normal[2] = clip[11] - clip[8];

    // left
    frustum[1].normal[0] = clip[3] + clip[0];
    frustum[1].normal[1] = clip[7] + clip[4];
    frustum[1].normal[2] = clip[11] + clip[8];

    // bottom
    frustum[2].normal[0] = clip[3] + clip[1];
    frustum[2].normal[1] = clip[7] + clip[5];
    frustum[2].normal[2] = clip[11] + clip[9];

    // top
    frustum[3].normal[0] = clip[3] - clip[1];
    frustum[3].normal[1] = clip[7] - clip[5];
    frustum[3].normal[2] = clip[11] - clip[9];

    for (i = 0; i < 4; i++)
    {
        Normalize (frustum[i].normal);

        frustum[i].type = PLANE_ANYZ;
        frustum[i].dist = DotProduct (r_origin, frustum[i].normal);
        frustum[i].signbits = R_SignbitsForPlane (&frustum[i]);
    }
}


so far it seems to work and it doesnt rely on the extra utility function. might be totally wrong though

[mh]

that looks good to me.

[revelator]

goodie

mh stamp of aproval feel free to use

[mh]

It would be cleaner (and less scary looking!) to do the multiplication in a loop though.

[revelator]

check gonna look at it later

[revelator]

btw a similar function existed in tenebrae allthough it was only used

for shadow volumes.

could be great if some of this made it into a tutorial of sorts for shadow volumes, as planar shadows are (to be frank) rather outdated

i do have some old code for volume generation. its a bit messy and lacks any form of clipping so shadows are all over the place (even through walls) also its horribly inefficient because of quakes multitude of lights.

[r00k]

qfusion has some fast planar shadows that clip, using a shader.
Shadow mapping seems to be popular now a days instead.

[revelator]

might try and nipple on it

hmm oups btw i had my doubt it would be as simple as just replacing those two functions and i ran headfirst into a bug it seems.

torches !

first of everything seemed normal but alas i soon discovered that torches went missing all of the sudden strange thing i can see the smoke and even stranger i can sometimes make them reapear if i back of a bit

hope to find a solution any ideas are welcome.

i did have to modify this bugger some

Code: Select all

/*
=============
R_SetupGL
=============
*/
void R_SetupGL (void)
{
   // glx and gly will always be 0 and 0
   // glwidth and glheight are the resolution we're rendering at
   glViewport (glx, gly, glwidth, glheight);

   glMatrixMode (GL_PROJECTION);
   glLoadIdentity ();

    GL_SetPerspective (r_refdef.fov_x, r_refdef.fov_y);

   glMatrixMode (GL_MODELVIEW);
   glLoadIdentity ();

   // put Z going up and Y going deep
   glRotatef (-90,  1, 0, 0);
   glRotatef (90,  0, 0, 1);

   // set the view according to where the player actually is in the map!!!
   glRotatef (-r_refdef.viewangles[2], 1, 0, 0);
   glRotatef (-r_refdef.viewangles[0], 0, 1, 0);
   glRotatef (-r_refdef.viewangles[1], 0, 0, 1);

   glTranslatef (-r_refdef.vieworg[0], -r_refdef.vieworg[1], -r_refdef.vieworg[2]);

   // set drawing parms
   if (gl_cull.value)
   {
      glEnable (GL_CULL_FACE);
      glCullFace (GL_FRONT);
   }
   else
   {
      glDisable (GL_CULL_FACE);
   }
   glDisable(GL_BLEND);
   glDisable(GL_ALPHA_TEST);
   glEnable(GL_DEPTH_TEST);
   glEnable (GL_TEXTURE_2D);

   // save out a copy of the modelview matrix (used in shadows).
   glGetFloatv (GL_MODELVIEW_MATRIX, cl_entities[0].mvievmatrix);

   // save out a copy of the projection matrix (used for waterwarp).
   glGetFloatv (GL_PROJECTION_MATRIX, cl_entities[0].pjectmatrix);
}


old one used this for fov_x
// keep the correct screen aspect at all times
aspect = (float) glwidth / (float) glheight;

maybe i should try with the old calculation ?

[mh]

Hmmmm. I've a working example of it here which you might want to check and compare with.

FTE also does the same by the way, but that's a bit more of a radical departure from the original source code.

[Spike]

per entity projection matrix? :o

glRotate/glTranslate/glMultMatrix were depricated in gl3/gles, so I personally avoid them if I can.

[mh]

It's a common fallacy that having hardware T&L means that they're hardware accelerated too. They're not and never were. It's only the final multiplication of position by MVP that is, so there's no reason whatsoever why you can't always do your transform calculations in software and in your own app.

http://www.opengl.org/wiki/FAQ#glTransl ... 2C_glScale