GLQuake - Frustum Plane Extraction

Post tutorials on how to do certain tasks within game or engine code here.
mh
Posts: 2292
Joined: Sat Jan 12, 2008 1:38 am

GLQuake - Frustum Plane Extraction

Post by 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: http://forums.inside3d.com/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]);
    }
}
We had the power, we had the space, we had a sense of time and place
We knew the words, we knew the score, we knew what we were fighting for
revelator
Posts: 2621
Joined: Thu Jan 24, 2008 12:04 pm
Location: inside tha debugger

Post by 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
Posts: 2292
Joined: Sat Jan 12, 2008 1:38 am

Post by 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));
}
We had the power, we had the space, we had a sense of time and place
We knew the words, we knew the score, we knew what we were fighting for
revelator
Posts: 2621
Joined: Thu Jan 24, 2008 12:04 pm
Location: inside tha debugger

Post by 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
Posts: 2621
Joined: Thu Jan 24, 2008 12:04 pm
Location: inside tha debugger

Post by 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 :lol:
mh
Posts: 2292
Joined: Sat Jan 12, 2008 1:38 am

Post by mh »

that looks good to me. :D
We had the power, we had the space, we had a sense of time and place
We knew the words, we knew the score, we knew what we were fighting for
revelator
Posts: 2621
Joined: Thu Jan 24, 2008 12:04 pm
Location: inside tha debugger

Post by revelator »

goodie :)

mh stamp of aproval feel free to use :D
mh
Posts: 2292
Joined: Sat Jan 12, 2008 1:38 am

Post by mh »

It would be cleaner (and less scary looking!) to do the multiplication in a loop though. 8)
We had the power, we had the space, we had a sense of time and place
We knew the words, we knew the score, we knew what we were fighting for
revelator
Posts: 2621
Joined: Thu Jan 24, 2008 12:04 pm
Location: inside tha debugger

Post by revelator »

check gonna look at it later ;)
revelator
Posts: 2621
Joined: Thu Jan 24, 2008 12:04 pm
Location: inside tha debugger

Post by 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 :twisted:

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) :lol: also its horribly inefficient because of quakes multitude of lights.
r00k
Posts: 1111
Joined: Sat Nov 13, 2004 10:39 pm

Post by r00k »

qfusion has some fast planar shadows that clip, using a shader.
Shadow mapping seems to be popular now a days instead.
revelator
Posts: 2621
Joined: Thu Jan 24, 2008 12:04 pm
Location: inside tha debugger

Post by 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 :shock:

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
Posts: 2292
Joined: Sat Jan 12, 2008 1:38 am

Post by mh »

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

FTE also does the same by the way, but that's a bit more of a radical departure from the original source code.
We had the power, we had the space, we had a sense of time and place
We knew the words, we knew the score, we knew what we were fighting for
Spike
Posts: 2914
Joined: Fri Nov 05, 2004 3:12 am
Location: UK
Contact:

Post by Spike »

per entity projection matrix? :o

glRotate/glTranslate/glMultMatrix were depricated in gl3/gles, so I personally avoid them if I can.
mh
Posts: 2292
Joined: Sat Jan 12, 2008 1:38 am

Post by 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
We had the power, we had the space, we had a sense of time and place
We knew the words, we knew the score, we knew what we were fighting for
Post Reply