Something I'd like to share with all of you: simple frustum culling

I've been working on some simple frustum culling for a little while and now it finally works. I'm going to describe the algorithm and then a code snippet. What it 'actually' does right now is test whether or not an object's position is inside or outside a cone with the specified number of degres as its radius. It's good for amateur projects because its still useful, but extremely easy to understand.

I would just like to specify a difference between frustum culling and frustum clipping: I asked the people at gamedev and they said that OpenGL automatically does frustum clipping for you after calling glFrustum. However it still takes time for your hardware to determine if the objects passed to it are inside or outside the view frustum. That is why it is important to do culling, which means you determine if an object is visible in software and don't even pass it to GL. With that said and done, here is my simple method (and it works!)

Using the equation (Mr. Wizard told me this equation)
costheta = DotProduct(A, B) / ||A|| * ||B||
A and B are vectors, ||A|| denotes the magnitude of , the DotProduct is the sum of the products of the components of the vectors
1) Get a vector from the object's position to the camera's position
2) Normalize it
3) Get just the view component of your View vector (View - Position)
4) Because your View and Normalized (View - Player.CamPos) vectors already have a length of 1, you can boil down the equation to just:
costheta = DotProduct(A, B)
5) Use arcsine function to get the number of radians between the two vectors
6) Optional step: convert to degrees for readability (which is what I did)
7) If the degrees between these two vectors is greater than the radius of your cone, then it isn't visible.

Here is my IsVisible() function, if it returns false, the object doesn't get drawn

Code:

bool GameEntity::IsVisible() { Vector ObjectToCamera; ObjectToCamera = Position - Player1->CamPos; ObjectToCamera.Normalize(); float CosTheta = DotProduct(ObjectToCamera, (Player1->View - Player1->Position));// / (ObjectToCamera.GetLength() * (Player1->View - Player1->Position).GetLength()); float Degrees = acosf(CosTheta); Degrees = RadiansToDegrees(Degrees); if(Degrees > 50) { return false; }

It's definitely not perfect, but it works for me for right now. I wanted to share that with other beginners so they could use it or something like it in their projects (in the time being until doing real frustum culling).

I decided to include this beast in action. I have the executable in one zip, and the game data files in another. simple unzip the executable in a folder, and then extract everything in the game files.zip into the same folder (an extra folder called Textures will also be placed into that directory; that's the way it should be)

executable:

game files:

FOR OGL:

Code:

// once a frame, before drawing after setting view matrix stuff 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 = 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; return; } 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; } // assumes the point is in frustum float dPointInFrustum( float x, float y, float z ) { return frustum[5][0] * x + frustum[5][1] * y + frustum[5][2] * z + frustum[5][3]; } float dSphereInFrustum( 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; } bool SphereInFrustum( 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; } bool CubeInFrustum( float x, float y, float z, float size ) { int p; for( p = 0; p < 6; p++ ) { if( frustum[p][0] * (x - size) + frustum[p][1] * (y - size) + frustum[p][2] * (z - size) + frustum[p][3] > 0 ) continue; if( frustum[p][0] * (x + size) + frustum[p][1] * (y - size) + frustum[p][2] * (z - size) + frustum[p][3] > 0 ) continue; if( frustum[p][0] * (x - size) + frustum[p][1] * (y + size) + frustum[p][2] * (z - size) + frustum[p][3] > 0 ) continue; if( frustum[p][0] * (x + size) + frustum[p][1] * (y + size) + frustum[p][2] * (z - size) + frustum[p][3] > 0 ) continue; if( frustum[p][0] * (x - size) + frustum[p][1] * (y - size) + frustum[p][2] * (z + size) + frustum[p][3] > 0 ) continue; if( frustum[p][0] * (x + size) + frustum[p][1] * (y - size) + frustum[p][2] * (z + size) + frustum[p][3] > 0 ) continue; if( frustum[p][0] * (x - size) + frustum[p][1] * (y + size) + frustum[p][2] * (z + size) + frustum[p][3] > 0 ) continue; if( frustum[p][0] * (x + size) + frustum[p][1] * (y + size) + frustum[p][2] * (z + size) + frustum[p][3] > 0 ) continue; return false; } return true; } int pSphereInFrustum( float x, float y, float z, float radius ) { int p; int c = 0; 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; if( d > radius ) c++; } return (c == 6) ? 2 : 1; } int pCubeInFrustum( float x, float y, float z, float size ) { int p; int c; int c2 = 0; for( p = 0; p < 6; p++ ) { c = 0; if( frustum[p][0] * (x - size) + frustum[p][1] * (y - size) + frustum[p][2] * (z - size) + frustum[p][3] > 0 ) c++; if( frustum[p][0] * (x + size) + frustum[p][1] * (y - size) + frustum[p][2] * (z - size) + frustum[p][3] > 0 ) c++; if( frustum[p][0] * (x - size) + frustum[p][1] * (y + size) + frustum[p][2] * (z - size) + frustum[p][3] > 0 ) c++; if( frustum[p][0] * (x + size) + frustum[p][1] * (y + size) + frustum[p][2] * (z - size) + frustum[p][3] > 0 ) c++; if( frustum[p][0] * (x - size) + frustum[p][1] * (y - size) + frustum[p][2] * (z + size) + frustum[p][3] > 0 ) c++; if( frustum[p][0] * (x + size) + frustum[p][1] * (y - size) + frustum[p][2] * (z + size) + frustum[p][3] > 0 ) c++; if( frustum[p][0] * (x - size) + frustum[p][1] * (y + size) + frustum[p][2] * (z + size) + frustum[p][3] > 0 ) c++; if( frustum[p][0] * (x + size) + frustum[p][1] * (y + size) + frustum[p][2] * (z + size) + frustum[p][3] > 0 ) c++; if( c == 0 ) return 0; if( c == 8 ) c2++; } return (c2 == 6) ? 2 : 1; } bool PolygonInFrustum( int numpoints, sVERTEX* pointlist ) { int f, p; for( f = 0; f < 6; f++ ) { for( p = 0; p < numpoints; p++ ) { if( frustum[f][0] * pointlist[p].X + frustum[f][1] * pointlist[p].Y + frustum[f][2] * pointlist[p].Z + frustum[f][3] > 0 ) break; } if( p == numpoints ) return false; } return true; }

On a side note:
I would LOVE to cull your frustum.

yeah uhh goten I've read GT's tutorial (I know that isn't GT's tutorial taken verbatum, but it's all of the same functionality) but the point of my method is to avoid all of that if you are still beginning with 3d programming (as I am). If you downloaded mine you'd see it works quite well for the most part, although not as accurate as real frustum culling, but the effectiveness to easiness ratio is better :)

to tell you the truth though it's been a long time since I've looked at this, real frustum culling doesn't seem as bad as I once thought. Hmm...

uhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh

What I posted is incredibly simple.

It takes very little effort.

I'm going to say its easier and more effective then what you posted even.

Why?

Becuase if you copy and paste that into your game, the type in the ExtractFrustum() in your draw function. Its ready to use.
Simply call what ever function you want. If you have a terrain in an array of some sort:

Code:

ExtractFrustum(); // for( int r = 0; r < m_rows-1; r++ ){ for( int c = 0; c < m_cols-1; c++ ) { bool drawTriangle = false; if( (PointInFrustum( m_vertices[r][c].X, m_vertices[r][c].Y, m_vertices[r][c].Z )) && (dPointInFrustum(m_vertices[r][c].X, m_vertices[r][c].Y, m_vertices[r][c].Z) <= m_maxDist)) drawTriangle = true; if( (PointInFrustum( m_vertices[r][c+1].X, m_vertices[r][c+1].Y, m_vertices[r][c+1].Z )) && (dPointInFrustum(m_vertices[r][c+1].X, m_vertices[r][c+1].Y, m_vertices[r][c+1].Z) <= m_maxDist)) drawTriangle = true; if( (PointInFrustum( m_vertices[r+1][c].X, m_vertices[r+1][c].Y, m_vertices[r+1][c].Z )) && (dPointInFrustum(m_vertices[r+1][c].X, m_vertices[r+1][c].Y, m_vertices[r+1][c].Z) <= m_maxDist)) drawTriangle = true; if( (PointInFrustum( m_vertices[r+1][c+1].X, m_vertices[r+1][c+1].Y, m_vertices[r+1][c+1].Z )) && (dPointInFrustum(m_vertices[r+1][c+1].X, m_vertices[r+1][c+1].Y, m_vertices[r+1][c+1].Z) <= m_maxDist)) drawTriangle = true; if( drawTriangle ) { glBegin(); glVertex3f( m_vertices[r][c].X, m_vertices[r][c].Y, m_vertices[r][c].Z);// Top glVertex3f( m_vertices[r][c+1].X, m_vertices[r][c+1].Y, m_vertices[r][c+1].Z);// Bottom Right glVertex3f( m_vertices[r+1][c].X, m_vertices[r+1][c].Y, m_vertices[r+1][c].Z);// Bottom Left glVertex3f( m_vertices[r][c+1].X, m_vertices[r][c+1].Y, m_vertices[r][c+1].Z);// Top glVertex3f( m_vertices[r+1][c].X, m_vertices[r+1][c].Y, m_vertices[r+1][c].Z);// Bottom Right glVertex3f( m_vertices[r+1][c+1].X, m_vertices[r+1][c+1].Y, m_vertices[r+1][c+1].Z);// Bottom Left glEnd(); } } }

Seems simple to me. :)

Quote:

Becuase if you copy and paste that into your game

That's where I stopped reading your post...I cut and paste as little as possible, the only thing I'm using right now is NeHe's basecode and the GT's equations for rotation about an arbitrary axis (the ones I had really should've worked anyway, but I tried to get mine working for a month to no avail, so I had to use thiers in order to move on). I always try to understand everything as much as possible, and then I write it myself. If I just cut and paste I dont' feel like I"ve learned a damn thing, and I don't feel like the software I wrote is mine thus reducing the level of satisfaction I have about it. That's where I stand, I seriously don't like cutting and pasting, it really makes me angry even. If you do that then your 'elite 3d game engine' is really only a collage of other people's (people like me) hard work.

EDIT: I'm not trying to be a dick but that really makes me upset. i liked the way I did it because I haven't seen anyone else do it that way. I was hoping someone would at least congradulate me for trying something new :( oh well

EDIT1: It also seems to me you should supply a label just before the if(drawtriangle) part of the function, because if any vertex is in the frustum then you don't need to check it against the other frustum planes, you can go right to drawing. Right? It would skip unnecessary code (and those are pretty big functions)

Code:

ExtractFrustum(); // for( int r = 0; r < m_rows-1; r++ ){ for( int c = 0; c < m_cols-1; c++ ) { bool drawTriangle = true; if( (PointInFrustum( m_vertices[r][c].X, m_vertices[r][c].Y, m_vertices[r][c].Z )) && (dPointInFrustum(m_vertices[r][c].X, m_vertices[r][c].Y, m_vertices[r][c].Z) <= m_maxDist)) goto draw; if( (PointInFrustum( m_vertices[r][c+1].X, m_vertices[r][c+1].Y, m_vertices[r][c+1].Z )) && (dPointInFrustum(m_vertices[r][c+1].X, m_vertices[r][c+1].Y, m_vertices[r][c+1].Z) <= m_maxDist)) goto draw; if( (PointInFrustum( m_vertices[r+1][c].X, m_vertices[r+1][c].Y, m_vertices[r+1][c].Z )) && (dPointInFrustum(m_vertices[r+1][c].X, m_vertices[r+1][c].Y, m_vertices[r+1][c].Z) <= m_maxDist)) goto draw; if( (PointInFrustum( m_vertices[r+1][c+1].X, m_vertices[r+1][c+1].Y, m_vertices[r+1][c+1].Z )) && (dPointInFrustum(m_vertices[r+1][c+1].X, m_vertices[r+1][c+1].Y, m_vertices[r+1][c+1].Z) <= m_maxDist)) goto draw; drawtriangle = false; draw: if( drawTriangle ) { glBegin(); glVertex3f( m_vertices[r][c].X, m_vertices[r][c].Y, m_vertices[r][c].Z);// Top glVertex3f( m_vertices[r][c+1].X, m_vertices[r][c+1].Y, m_vertices[r][c+1].Z);// Bottom Right glVertex3f( m_vertices[r+1][c].X, m_vertices[r+1][c].Y, m_vertices[r+1][c].Z);// Bottom Left glVertex3f( m_vertices[r][c+1].X, m_vertices[r][c+1].Y, m_vertices[r][c+1].Z);// Top glVertex3f( m_vertices[r+1][c].X, m_vertices[r+1][c].Y, m_vertices[r+1][c].Z);// Bottom Right glVertex3f( m_vertices[r+1][c+1].X, m_vertices[r+1][c+1].Y, m_vertices[r+1][c+1].Z);// Bottom Left glEnd(); } } }

Quote:

Originally posted by Silvercord
That's where I stopped reading your post...I cut and paste as little as possible, the only thing I'm using right now is NeHe's basecode and the GT's equations for rotation about an arbitrary axis (the ones I had really should've worked anyway, but I tried to get mine working for a month to no avail, so I had to use thiers in order to move on).

I dont care if you cut and paste or type everything out. Whats the difference between using the code I posted and the one You posted? Either way they would be using something they might not understand.

I posted a resource. That is all.

EDIT1: Lol im not going to insert any lables or goto's into my code. The else's of the if statements got erased when I edited it in this post box to simply it.

it's not just a matter of cutting and pasting and typing everything out. It's a matter of understanding things. I have no clue if you understand the plane equation and why it is the way it is. I'm just assuming you do, but I'm not using that code until I know the nuts and bolts of what's going on.

I understand the math of these equations. Im in a high level math course where we do matrix equations, dot products and vector work for warm ups. I typed the text from GT's tutorial directly into my demo, and I did it nto for the purpose of "understanding" but for the purpose of memory. Typing something yourself rarely induces understanding, it mainly induces memory for later use.

On a side note, is it a little hypocritical at least to refuse to accept what I have posted when you have posted your own code? How well did you explain the maths behind your code.

Im not just talking about the frustum part itself, but everything related. Including your camera code. Did you explain the view matrixs of cameras? Did you explain the complex math behind it?

My code is smaller, and is unreliant on a bunch of other code. Therefor the collective damage of a newbie who is using it with out understanding it is far smaller then a newbie who uses yours with out understaing!!!

So hah. Logic wins, again!

(it should be realized my posts are all in a light hearted manner. And should not be taken offense to.)

Mine seems incredibly straight forward. I guess I assumed knowledge of a lot of things without realizing it, although I still dont' think I did anything that is as complicated as plane equations, or as messy or arduous as needing to extract the view frustum (it's just a lot, not necessarily complicated). You're a high level math student, I'm not, but a lot things can be done in an easy way many times (there isn't necessarily a whole lot of complicated math going on behind the scenes). For example, you could use the aribrary axis rotation equations (rotating just the perpendicular component and then adding in the perpendicualr compnent, Pcos + (A X P)sin + A(A.P) (1 - cos). If they're already perpendicular I think it can be boiled down to P - (A.P)cos), or you can just combine the X and Y rotatoin matrices and completely skip the arbitrary axis rotation equations. then it comes down to being able to derive the 3d rotation matrices, but I think you get my drift? Oh well, no one seems to care that I came up with something that is at least somewhat new and original.

EDIT: and I mean, come on, I specifically said "this is how you can do it without frustum culling" and what is the first thing anyone has to post (instead of asking me questions or commenting on what I did), the frustum culling routines that I specifically avoided...