Redrawing the frustum huge drain on CPU?
Author
I'm currently designing a frustum class and i noticed that the recommendation from Dion Picco is to redraw the frustum every time the modelview matrix or the projection matrix changes. Isn't that going to be an absolutely tremendous drain on the cpu?
Say I have two spaceships rotating. That would mean I'd have to redraw the frustum every time I do a rotation (twice in one loop). Currently, my class to cull has to do the following:
1) Multiply the modelview and projection matrices
2) Set the frustum matrix to the product of above
3) Extract planes from that matrix
4) Finally cull
However, it seems to me that steps 1-3 would take infinitely more time than the supposed bottleneck, step 4. I am missing something? In my mind it seems like it would cost more to call glTranslatef than to render another spaceship in this case.
Hi,
You don't have to use the model matrix. In my frustum culling class, I only consider view * projection matrices. So I recompute the planes only when one of these 2 matrices change.
Then, each model keep an AABB up to date, and I use this AABB to cull my model. Updating the AABB of each model (only when the model matrix change of course) each frame is not too expensive.
One thing that might works (never tested, and not good enough in math to say if it can works on not) : don't recalc the AABB for each model, but at culling time, transform the planes by the inverse of the model matrix. I use a similar approach with ray picking and it works fine. But I don't know if it would work with planes.
You don't have to use the model matrix. In my frustum culling class, I only consider view * projection matrices. So I recompute the planes only when one of these 2 matrices change.
Then, each model keep an AABB up to date, and I use this AABB to cull my model. Updating the AABB of each model (only when the model matrix change of course) each frame is not too expensive.
One thing that might works (never tested, and not good enough in math to say if it can works on not) : don't recalc the AABB for each model, but at culling time, transform the planes by the inverse of the model matrix. I use a similar approach with ray picking and it works fine. But I don't know if it would work with planes.
um, unless im missing something HUGE here, you're missing something small....
steps 1,2,3 are O(1) in the number of objects you're culling.
step 4 is O(n) in the number of objects you're culling.
if you actually have some objects, the cost of 1,2,3 is negligible...
steps 1,2,3 are O(1) in the number of objects you're culling.
step 4 is O(n) in the number of objects you're culling.
if you actually have some objects, the cost of 1,2,3 is negligible...
You're missing something ^^ He uses the MODEL matrix which is unique for each model. So it's not O(1) but O(n) for 1, 2, 3 and 4. The question is : what is the fastest between :
1) setting the model * view * projection for each model, extract frustum planes, then cull, all of this for each model.
2) set view * projection, extract the planes ONCE, recalc AABB of the models, and cull each one.
3) set view * projection, extract the planes ONCE, cull each model, multiplying the planes by the inverse model matrix. (I don't know if this one works)
1) setting the model * view * projection for each model, extract frustum planes, then cull, all of this for each model.
2) set view * projection, extract the planes ONCE, recalc AABB of the models, and cull each one.
3) set view * projection, extract the planes ONCE, cull each model, multiplying the planes by the inverse model matrix. (I don't know if this one works)
Author
Big O is misleading. Using the modelview matrix, You're still going to have to be calling a function with a lot of operations *constantly*. That's going to slow things down a lot. I think paic is onto something, though. I'll consider using view instead.
Author
Also, Paic brings up another good point. I see a lot of discussions about frustum methods and the pros/cons, but does anyone have a definite answer on the fastest way to do frustum culling? I'd like to know that.
Hi again.
Well, I guess the best method depends on your scene. My frustum implementation use only AABB so that I can optimize a lot the planes tests (in the worst case, I only have 6 dot product and a few bit operations to do, which is really quick) So in my case, I use view * projection, and keep the models' AABBs up to date. But as said, it depend on your scene and your needs.
Also one other thing to speed up culling is to create a scene hierarchy. For example, take a space game. You have solar systems which include a lot of planets, and each planet can have many satelites attached to it, etc.
So, what to do is create a hierarchical scene tree like this one :
Then, recursively update the AABB of your tree. For example, update the satelite 11 and 12. Then update the AABB of planet 1 which include the planet itself PLUS the 2 AABBs of the satelites ! And the solarSystem AABB will include all the AABB of the planets.
When you do that, the culling will be more efficient, because if a planet is not visible, you won't see the satelite, and you don't even have to test them !! So, instead of looping through your list of object and testing each one, you will take the hierarchy into account to avoid testing stuff that don't need to.
Well, I guess the best method depends on your scene. My frustum implementation use only AABB so that I can optimize a lot the planes tests (in the worst case, I only have 6 dot product and a few bit operations to do, which is really quick) So in my case, I use view * projection, and keep the models' AABBs up to date. But as said, it depend on your scene and your needs.
Also one other thing to speed up culling is to create a scene hierarchy. For example, take a space game. You have solar systems which include a lot of planets, and each planet can have many satelites attached to it, etc.
So, what to do is create a hierarchical scene tree like this one :
solarSystem |--- planet 1 | |--- satelite 11 | |--- satelite 12 |--- planet 2 |--- planet 3 |--- satelite 31 |--- satelite 32Then, recursively update the AABB of your tree. For example, update the satelite 11 and 12. Then update the AABB of planet 1 which include the planet itself PLUS the 2 AABBs of the satelites ! And the solarSystem AABB will include all the AABB of the planets.
When you do that, the culling will be more efficient, because if a planet is not visible, you won't see the satelite, and you don't even have to test them !! So, instead of looping through your list of object and testing each one, you will take the hierarchy into account to avoid testing stuff that don't need to.
I don't see any problem. A modern CPU can do millions of those operations per second. And I don't expect you've got that many objects.
So just implement it one way or another without bothering too much about performance yet. Once your application is close to finished you can do some profiling to look for the real bottlenecks. If culling is one, you can improve the algorithm and even do low-level optimizations if necessary. But it's very premature to worry about that right now.
Anyway, purely theoretically, one of the fastest ways to do it is:
- Compute the smallest bounding spheres (once per object)
- Compute the frustum planes in world space (once per frame)
- Transform center of bounding spheres to world space (once per object per frame)
- Perform very simple sphere/plane cull tests
The only disadvantage is that spheres are not optimal. But culling tests are only an approximation anyway and most effective for objects far outside the frustum. So spheres work fine in practice.
But anyway, don't worry about optimizations before you've got a completely working application. I've seen many projects never being finished because too much time was spend on optimizations that were not necessary and made the design too complicated.
So just implement it one way or another without bothering too much about performance yet. Once your application is close to finished you can do some profiling to look for the real bottlenecks. If culling is one, you can improve the algorithm and even do low-level optimizations if necessary. But it's very premature to worry about that right now.
Anyway, purely theoretically, one of the fastest ways to do it is:
- Compute the smallest bounding spheres (once per object)
- Compute the frustum planes in world space (once per frame)
- Transform center of bounding spheres to world space (once per object per frame)
- Perform very simple sphere/plane cull tests
The only disadvantage is that spheres are not optimal. But culling tests are only an approximation anyway and most effective for objects far outside the frustum. So spheres work fine in practice.
But anyway, don't worry about optimizations before you've got a completely working application. I've seen many projects never being finished because too much time was spend on optimizations that were not necessary and made the design too complicated.
I think there is a difference between code optimisation and having a good plan about how to do the frustum culling. I totally agree it is nonsense to optimize every tiny bit before there is an app that can show whether it´s too slow or not and where the bottlenecks are, but that wouldn´t keep me from thinking about such things like frustum culling beforehand, since I´d say it coudl definitely help speed coding up to have a nice idea about how I want to implement it and it´s much nicer to have thought about it beforehand, implementing it and seeing it work than implementing frustum culling and afterwise seeing you obviously chose a method that doesn´t suit your app´s needs. Still I´d do the fine-tuning afterwards, but a rough sketch is never a bad idea.
Furthermore, sure, current CPUs are hell-of-a-lot faster than they were 10 years ago, but we´re also demanding hell-of-a-lot more from them.... CPUs got faster, frame-rates stayed (nearly) the same ;)
Furthermore, sure, current CPUs are hell-of-a-lot faster than they were 10 years ago, but we´re also demanding hell-of-a-lot more from them.... CPUs got faster, frame-rates stayed (nearly) the same ;)
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
