Math for Game Developers - Frustum Culling 

Math doesn't go out of date! :)

+Neil Roy Why don't you try a dot product? Take a vector to the object and dot it with the view vector. If it's bigger than cos of the field of view, you must be out of the field of view. Make sure to normalize them before you dot them.

Jorge Rodriguez Because I am still new to this level of math. I know what normalizing is, I know what a vector is etc... I am still getting used to exactly what a "dot product" even is! LOL ;) It must be nice to think in math like that. but I am getting there. But I took a note of what you just suggested and I will see what i can do. I did manage to get it working somewhat so progress is being made... albeit slowly. I don't give up easily. :) In fact, I was laying in bed trying to sleep and my brain was still on all of this. LOL

+Neil Roy I solve problems by sleeping on them all the time, it's a good method. It helps your brain get used to new things that you're learning.

lol i saw you on making games with ben

Yeah, I loved Ben's tutorials, very well done! I did manage to implement a sort of hack of this Frustum Culling on a 3D game I am playing with. It's not a true 3D frustum as I do not take into account your pitch, but in the game you won't be looking up or down so it doesn't matter. But I did manage to get it working and it really sped up my 3D game big time! I still want to work on implementing true Frustum Culling code, but what I have gets the job done for now. Next on my todo list is Occlusion culling I think it is called (eliminating polygons that are not facing the camera?), which should be easier, just test the polygon's normal and if it faces away from the camera, don't draw it. Should speed things up more. The biggest problem I see with most of these sort of tutorials is they almost never get into organizing your 3D data, which is vital. I have learned a lot of very BAD habits from poorly written tutorials over the years. This is why Ben's were so good, because he avoided the bad habits and though some of what he taught was rather involved, it was the right way to do it (except how he almost never used constructors and destructor's properly, that bugged me and I rewrote his code to use them properly on my system). HOW you store your 3D data is VERY important! You need to be able to examine individual polygons so you can check their position, whether or not to draw them, collision etc. when y ou have tutorials which use things like opengl triangle strips, that seems okay, but in reality is is garbage and useless to use. You need to store polygone individually. Usually you should store your vertices and a separate index list that make up all the polygons which you can then use to optimize for speed, collision etc. Almost none of the online tutorials cover this sort of data organization. I imagine most people give up when they realize their code cannot be used to detect collisions etc and they have to unlearn a lot. Anyhow... rambling again. ;)

Photoshop.

Jorge Rodriguez Thank you :]

+Kevin Meisenbacher Thank you.

@@JorgeVinoRodriguez hmm. Was that a compliment?

@@arunparolikkal4674 after 5 years? Yeah...

...unless sorting on the CPU will be more expensive than overdraw. As with any performance issue, one should profile the application first to see what the performance characteristics are and approach the most serious ones first, resolving them in the way that makes the most sense for that particular problem. :)

In this case d is given as part of the problem, the frustum is created in another part of the code and right now we're only using it to solve the problem. If you want to create the plane yourself then you'll have to use the plane formula, ax + by + cz = d, there's your d. If you have a point (x', y', z') and a plane normal (a, b, c) and you want to find the corresponding plane formula, then you do a(x-x') + b(y-y') + c(z-z') = 0, and simplify to get it in ax + by + cz = d form. I think I may cover this stuff in another video, I don't quite remember.

Absolutely, and the math ends up being much the same or even a bit easier.

Very good questions. d is not just distance, it's signed distance. That means that its absolute value is the distance, and its sign depends on which side of the line it is. You understand correctly, d is negative below the plane and positive above. You can calculate d by setting up and solving a system of linear equations. I'll try to explain it here, hopefully it makes sense only with text. If not, try drawing a picture. Let's say you have a point x0 and two linearly independent vectors (v0 v1) that define a plane. Then your plane is the set of all points x0 + a0 * v0 + a1 * v1, where a0 and a1 are any real number. The normal of the plane is n = (v0 x v1) / |v0 x v1| (x is the cross product, and I divide by magnitude to make sure that it's unit length.) Then there's some scalar multiple of n that will span from the origin to the plane, ie x0 + a0 * v0 + a1 * v1 = d * n. Since x0 v0 and v1 are vectors with 3 components, this is a series of 3 linear equations and you can solve for the 3 unknowns, a0 a1 and d. Since d is the number of unit-length normal vectors that separate the plane from the origin, d is the signed distance. If you need a picture to go with this, email me: bs.vino@gmail.com You're not a troll at all, in fact you're asking excellent questions and I hope you'll continue to do so! I'm happy to answer questions about any of my videos, so keep them coming :)

Okay, I tried drawing what you said and it makes a lot more sense now, thanks! If anyone else is also interested, here is the picture: imgur.com/a/JlY2V I also tried to calculate a0, a1, d from what I drew and it worked fine. I have a much better understanding now. Note, I made a mistake when drawing and I have drawn n in the opposite direction; it should actually be pointing towards the origin, not away from it. My bad. But other than that, it should all be correct.

Nice work!

+Rutger De Maeyer C++

That assumes the camera is at the origin. If you want to transform all objects to camera space you could do it this way. Also it will get you a conical Frustum and not a rectangular Frustum.

oh ok that seems right, thanks!

One thing, when you develope games, you usally use a game engine or do everything from scratch?

DarkDrakman Depends on what I'm making. I've done both.

Jorge Rodriguez In the end though, the camera is always at the origin. In OpenGL, the caamera is always looking down negative z. Camera models that let you treat the camera as a movable thing are just extra math, but the camera is always at the center.

SoulGuitarMetal Not covered in this video, sorry. It's on my list to make a video about that.

+Jorge “Vino” Rodriguez +1 for this please :D I think I see what's going on here, but.. well.. it's late and i need sleep

Actually, I just found this paper - which gets into the detail of the procedure. Quite handy for anyone that is looking. gamedevs.org/uploads/fast-extraction-viewing-frustum-planes-from-world-view-projection-matrix.pdf

+SoulGuitarMetal I was going to do a video on it but after reviewing it I don't think it's terribly educational to learn how it's done, it's just some simple calculation and manipulation. But Mr. Kane linked a pdf that does it (also in the description) and you can try reading the sample code and to figure out how it's done. It's actually all pretty straightforward.

+Jorge Rodriguez (Vino) Yeah the code works fine but I have a hard time viewing how it works which sometimes is more important to me than just get it working. Particularly the part where it states that the extracted planes are an axis-aligned box or "untransformed' viewing frustum. "If vertex v' is inside this box, then the untransformed vertex v is inside the 'untransformed' viewing frustum". So we are not working with a frustum at all...? I don't get it.