• Create Account

Awesome job so far everyone! Please give us your feedback on how our article efforts are going. We still need more finished articles for our May contest theme: Remake the Classics

# What's out there - Fast Frustum culling

Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

32 replies to this topic

### #21Narf the Mouse  Members   -  Reputation: 305

Like
-2Likes
Like

Posted 22 June 2012 - 05:26 AM

@Krypt0n

ah now I see why you don't need the full 6 transformed and thanks for the link, was the same paper I was talking about.

I think the best bet for me it to stick with spheres for dynamic objects, unless they are really useless shapes, like a lam post (bad example as they don't exactly move much) and then just switch to check the box if the sphere intersects. Then I can avoid the matrix maths unless absolutely necessary.

Static stuff like buildings and houses should deffo use the boxes! Especially if they are more long,tall or wide than squarish.

You only need to check the AABB if the sphere isn't contained in the frustum, but still intersects it.

### #22Krypt0n  Members   -  Reputation: 1385

Like
0Likes
Like

Posted 22 June 2012 - 05:51 AM

You only need to check the AABB if the sphere isn't contained in the frustum, but still intersects it.

the point was, checking AABB is similar speed to checking a sphere. so checking a sphere AND then an AABB makes not really sense.

### #23Narf the Mouse  Members   -  Reputation: 305

Like
-2Likes
Like

Posted 22 June 2012 - 05:57 AM

You only need to check the AABB if the sphere isn't contained in the frustum, but still intersects it.

the point was, checking AABB is similar speed to checking a sphere. so checking a sphere AND then an AABB makes not really sense.

Depends. An AABB generally fits objects better than a sphere.

### #24Krypt0n  Members   -  Reputation: 1385

Like
0Likes
Like

Posted 22 June 2012 - 06:05 AM

Depends. An AABB generally fits objects better than a sphere.

it's not a question of 'fitting' but how many instructions you need to check. I'll sum up the conversation for you

we figured out, it's 6plane-vs-point for Frustum-vs-AABB just like frustum-vs-Sphere.
tighting fitting is the advantage, yes. and if AABB checks are as fast as Sphere, but more accurate, why sphere checks at all?
bwhiting pointed out, for his fully dynamic scenes spheres are faster, as he does not need to recalculate AABBs.

### #25bwhiting  Members   -  Reputation: 404

Like
0Likes
Like

Posted 22 June 2012 - 06:07 AM

You only need to check the AABB if the sphere isn't contained in the frustum, but still intersects it.

the point was, checking AABB is similar speed to checking a sphere. so checking a sphere AND then an AABB makes not really sense.

indeedy, apart from when when one is dealing with dynamic objects?

and @narf only checking the box on an intersection was exactly what I said

edit: I was too slow and pretty much just repeated Krypt0n

Edited by bwhiting, 22 June 2012 - 06:08 AM.

### #26Narf the Mouse  Members   -  Reputation: 305

Like
-2Likes
Like

Posted 22 June 2012 - 06:08 AM

Depends. An AABB generally fits objects better than a sphere.

it's not a question of 'fitting' but how many instructions you need to check. I'll sum up the conversation for you

we figured out, it's 6plane-vs-point for Frustum-vs-AABB just like frustum-vs-Sphere.
tighting fitting is the advantage, yes. and if AABB checks are as fast as Sphere, but more accurate, why sphere checks at all?
bwhiting pointed out, for his fully dynamic scenes spheres are faster, as he does not need to recalculate AABBs.

And I pointed out that spheres on the frustum edge can just recalculate the AABB once, if they need the extra precision.

### #27Narf the Mouse  Members   -  Reputation: 305

Like
0Likes
Like

Posted 22 June 2012 - 06:09 AM

You only need to check the AABB if the sphere isn't contained in the frustum, but still intersects it.

the point was, checking AABB is similar speed to checking a sphere. so checking a sphere AND then an AABB makes not really sense.

indeedy, apart from when when one is dealing with dynamic objects?

and @narf only checking the box on an intersection was exactly what I said

edit: I was too slow and pretty much just repeated Krypt0n

Well, that makes more sense, now.

### #28mhagain  Members   -  Reputation: 3828

Like
0Likes
Like

Posted 22 June 2012 - 07:03 AM

Strikes me that testing 2 bbox points - nearest and farthest - per plane may actually be optimal in many cases.

The logic is that it gives an early-out success case - if one of the points is inside the plane but the other is outside it then the box intersects the plane and you can skip testing against the rest of the planes.

Narf is of course correct below. Can you -1 yourself?

Edited by mhagain, 22 June 2012 - 11:58 AM.

It appears that the gentleman thought C++ was extremely difficult and he was overjoyed that the machine was absorbing it; he understood that good C++ is difficult but the best C++ is well-nigh unintelligible.

### #29Narf the Mouse  Members   -  Reputation: 305

Like
0Likes
Like

Posted 22 June 2012 - 11:19 AM

Strikes me that testing 2 bbox points - nearest and farthest - per plane may actually be optimal in many cases.

The logic is that it gives an early-out success case - if one of the points is inside the plane but the other is outside it then the box intersects the plane and you can skip testing against the rest of the planes.

It's entirely possible for a box to intersect a single plane, yet still not intersect the frustum.

### #30mhagain  Members   -  Reputation: 3828

Like
-1Likes
Like

Posted 22 June 2012 - 11:57 AM

Strikes me that testing 2 bbox points - nearest and farthest - per plane may actually be optimal in many cases.

The logic is that it gives an early-out success case - if one of the points is inside the plane but the other is outside it then the box intersects the plane and you can skip testing against the rest of the planes.

It's entirely possible for a box to intersect a single plane, yet still not intersect the frustum.

Can you -1 yourself? Because roundabout now I feel like doing so.

It appears that the gentleman thought C++ was extremely difficult and he was overjoyed that the machine was absorbing it; he understood that good C++ is difficult but the best C++ is well-nigh unintelligible.

### #31Narf the Mouse  Members   -  Reputation: 305

Like
-1Likes
Like

Posted 22 June 2012 - 12:51 PM

Strikes me that testing 2 bbox points - nearest and farthest - per plane may actually be optimal in many cases.

The logic is that it gives an early-out success case - if one of the points is inside the plane but the other is outside it then the box intersects the plane and you can skip testing against the rest of the planes.

It's entirely possible for a box to intersect a single plane, yet still not intersect the frustum.

Can you -1 yourself? Because roundabout now I feel like doing so.

Hey, I've made my own mistakes in this thread. Don't start that!

### #32InvalidPointer  Members   -  Reputation: 923

Like
0Likes
Like

Posted 22 June 2012 - 09:09 PM

By profiling, the Frustum cull (multithreaded) is the slowest part of my draw call. It's a FrustumAABB check. Ways to speed this up, IMU:

1) FrustumSphere. Upside: 1 point, not 8, to check. Downside: Can include more objects for drawing that aren't actually in-frame. Solution: Secondary AABB check if the bounding sphere only intersects the frustum, not is contained by it.
2) GameDev search turned up old references to "Azimuth/Elevation/Distance"; however, information sources were too old.
3) Some sort of pre-sorting? Octree? Last time I tried that, it was slower, but I had it Frustum-checking the entire hierarchy, instead of auto-adding on containment. Also, my bounding objects may not have been optimized at the time (long story).

Thanks.

It's actually option 4) Dump everything into a flat array and let all the cores have at it. And intelligent design of the underlying data structures, but the parallelization opportunities are what really sealed it.
clb: At the end of 2012, the positions of jupiter, saturn, mercury, and deimos are aligned so as to cause a denormalized flush-to-zero bug when computing earth's gravitational force, slinging it to the sun.

### #33Narf the Mouse  Members   -  Reputation: 305

Like
0Likes
Like

Posted 26 June 2012 - 12:38 PM

By profiling, the Frustum cull (multithreaded) is the slowest part of my draw call. It's a FrustumAABB check. Ways to speed this up, IMU:

1) FrustumSphere. Upside: 1 point, not 8, to check. Downside: Can include more objects for drawing that aren't actually in-frame. Solution: Secondary AABB check if the bounding sphere only intersects the frustum, not is contained by it.
2) GameDev search turned up old references to "Azimuth/Elevation/Distance"; however, information sources were too old.
3) Some sort of pre-sorting? Octree? Last time I tried that, it was slower, but I had it Frustum-checking the entire hierarchy, instead of auto-adding on containment. Also, my bounding objects may not have been optimized at the time (long story).

Thanks.

It's actually option 4) Dump everything into a flat array and let all the cores have at it. And intelligent design of the underlying data structures, but the parallelization opportunities are what really sealed it.

...That's...Pretty much the solution I've got at the moment. Huh.

Well, thanks.

But, uh, how do I refer to you?

Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

PARTNERS