Frustum Culling

Frustum Culling - 1.0.0

Ian Mallett (geometrian)

Tags:

Description

In 3D graphics, one often has a huge amount of polygons to push around. To lighten the load, if some of the polygons are not visible on screen, we don't try to draw them. This makes intuitive sense, but it is not built-in in OpenGL. This is called "Frustum Culling", probably because it is FRUSTRATING to implement. In my demo, the screen, (representing a landscape from top view), is divided into quads, (representing Display Lists each containing 8192 triangles. Use the arrow keys with shift to move and turn. All this took me longer than you'd think it should to do; the solution is actually quite simple, but hard to figure out. I included the source so you can edit the resolution, (NumberOfQuads [per side]), the viewing angle, (CameraViewAngle), and a few other things. Have fun!

Links

Home Page: http://geometrian.com/programming/index.php

Screenshot

click to view original size

Releases

Frustum Culling - 2.0.0 - Jan 28, 2008
Frustum Culling - 1.0.0 - Jan 20, 2008

Pygame.org account Comments

If you wish to leave a comment with your pygame.org account, please sign in first.

January 28, 2008 12:38pm - Ian Mallett - nickname: (geometrian)
Yep. One can do that. Set NumberOfQuads (line 14) to something smaller.
January 28, 2008 12:49am - Jordan Trudgett - nickname: (tgfcoder)
If the depth of field culling takes so long, why not reduce the resolution it works at? It probably wont be as efficient, but say if you checked part of a matrix of 10x10 squares (the centre point of each block) and gave that a distance value, it would still work pretty fast (cutting down the number of python trig functions needed exponentially?) I'm not sure exactly how I might go around implementing some optimisation like that since I haven't read the code, but just a thought :P
January 28, 2008 12:18am - Ian Mallett - nickname: (geometrian)
Version 2.0.0 released! Now has depth of field culling! In this program, the depth of field is color coded, and so is essentially useless. However, the same code can be used to render lower polygon landscape sections in the background, slashing render time. The code for this is actually quite simple.
January 27, 2008 9:42pm - Ian Mallett - nickname: (geometrian)
I'll remember that. I'm working on a version of this that has a better algorithm and shows varying resolutions at various depths of field.
January 26, 2008 6:19am - Jordan Trudgett - nickname: (tgfcoder)
Oh, that you mispelled 'Frustum'. I did say that it was tedious to have spaces in names though. Usually makes tab completion difficult.
January 25, 2008 2:29pm - Ian Mallett - nickname: (geometrian)
Is the mistake that I put a space in, (I'll try to remember next time) or that I mispelled 'Frustum'? I could have used radians, which would make the code go faster, but even though I completely understand radians, I am more comfortable in degrees.
January 25, 2008 2:05am - Jordan Trudgett - nickname: (tgfcoder) - 3/5
Your .py file is Frustrum Culling.py -- sounds like a mistake I would make =P Oh, and it's annoying to have spaces in names under UNIX (which is why SourceForge differentiates project names from "Unix" names: ones without funny chars like spaces.) Fun to play around with! It seems a bit of an annoyance that your code uses degrees, then converts to radians for the math trig. Can't you use radians straight off? 180 deg = PI rad A good maths example nonetheless :)
January 23, 2008 3:18am - Luca Fabbri - nickname: (keul)
Ok, I looked more at the source and now I understand... thanks for answer!
January 21, 2008 9:08pm - pymike - nickname: (pymike)
This is pretty cool! Fun to play around with.
January 20, 2008 11:06am - Ian Mallett - nickname: (geometrian)
Opps... Link fixed. This is more of an example. It shows how to find which sections of a map to draw. in this example, each red/green square represents a display list (a precompiled series of polygons on the GPU). In an OpenGL program, instead of drawing them like I have here, for each green square, I would draw the appropriate display list. Imagining this as an OpenGL program (it's not) lets you see from an outsider's perspective which parts of the landscape are being drawn. Again, the computer only has to draw the green sections, not the red, saving time.
January 20, 2008 9:44am - Luca Fabbri - nickname: (keul)
I'm sorry, but I'm note sure what you have published here. Is this some sort of alghoritm that someone can use to get the effect you decribe? Is this "only" an example or is some sort of library (in this case I think you can add this to you tags! This can be very useful to all!).
January 20, 2008 6:19am - Paul Davey - nickname: (technomancer)
link on download page is not working!!!!
January 20, 2008 2:44am - Ian Mallett - nickname: (geometrian)
Version 1.0.0 released!