gdalgorithms-list

[Algorithms] View Frustum Culling

[Tim J. <ti...@gn...>]

What is the best method for coarse bounding box frustum culling?

From what I can gather you either use axis aligned bound boxes (AABBs) =
or oriented bounding boxes (OBBs), with OBBs having the advantage of =
tighter fitting but need extra computations for the culling process. =
Also which culling method is best, perspective transform the BB and the =
view frustum to the perspective coordinate system (which with AABBs can =
result in testing two AABBs which is just 6 comparisons, however you =
have to transform all 8 vertices of the AABB) or testing the BB against =
the 6 planes of the view frustum (which seems much simpler and =
straightforward if that is all that is needed.)

So is comparing AABBs against the frustum planes the best way to go and =
is it just find the equations and test the vertices or is there some =
more transforming needed in there?

Also what are the extra steps needed to use OBBs instead?

And finally a nice easy question, what is the right way to get the 6 =
equations of the planes if you happen to have an OpenGL matrix?

Any help would be great
thanks,

Tim.

[Algorithms] View Frustum Culling

[<SHA...@ao...>]

Hi,

I've ported most of my 3D engine to DX8 from DX7 and have come to the point 
where I am going to cull octree nodes against the viewing frustum.

I was using the ComputeSphereVisibility helper function but we all know this 
has been removed :)

I can't quite see how the new Box&Sphere Probe against Ray tests can be used 
to achieve what I want, maybe someone could explain?

What would be the easiest ( if not too slow ) way to do this.

If have 2 main plans

1a) Create a sphere around the frustum and do sphere/sphere tests as a coarse 
cull
1b) then do either cone/sphere or 6 frustum planes/sphere tests 

2) Possibly put AABB vertices in a VB and check the clip flags after 
transformation?

Not even sure if 2 is possible or how to test the clip flags?? 

Regards,

John.

Re: [Algorithms] View Frustum Culling

[gl <gl...@nt...>]

As for a DX way of doing it, you can ProcessVertices() your bounding box (as
you suggest), and use GetClipStatus() to get the flags - never tried it
though.
--
gl

----- Original Message -----
From: SHA...@ao...
To: gda...@li...
Sent: Monday, January 22, 2001 3:49 PM
Subject: [Algorithms] View Frustum Culling


Hi,

I've ported most of my 3D engine to DX8 from DX7 and have come to the point
where I am going to cull octree nodes against the viewing frustum.

I was using the ComputeSphereVisibility helper function but we all know this
has been removed :)

I can't quite see how the new Box&Sphere Probe against Ray tests can be used
to achieve what I want, maybe someone could explain?

What would be the easiest ( if not too slow ) way to do this.

If have 2 main plans

1a) Create a sphere around the frustum and do sphere/sphere tests as a
coarse
cull
1b) then do either cone/sphere or 6 frustum planes/sphere tests

2) Possibly put AABB vertices in a VB and check the clip flags after
transformation?

Not even sure if 2 is possible or how to test the clip flags??

Regards,

John.

Re: [Algorithms] View Frustum Culling

[Dave E. <eb...@ma...>]

From: Tim Johnston 

> What is the best method for coarse bounding box frustum culling?

"Best" depends on your application.  There are always
tradeoffs to be considered.

> From what I can gather you either use axis aligned bound
> boxes (AABBs) or oriented bounding boxes (OBBs), with
> OBBs having the advantage of tighter fitting but need extra
> computations for the culling process. Also which culling
> method is best, perspective transform the BB and the view
> frustum to the perspective coordinate system (which with
> AABBs can result in testing two AABBs which is just 6
> comparisons, however you have to transform all 8 vertices
> of the AABB) or testing the BB against the 6 planes of the
> view frustum (which seems much simpler and
> straightforward if that is all that is needed.)

Testing for intersection between box and frustum a plane
at a time is fast, but not conclusive.  You have the situation
where a box is not determined to be completely outside
any plane, but the box does not intersect the frustum.  It
takes more time to determine the actual relationship between
box and frustum.  This is one of the tradeoffs you need to
decide on.  Plane-at-a-time is a fast test for no-intersection,
but you might send a few objects to the renderer only to be
clip-culled or rejected by z-buffer tests a pixel at a time.  The
full test is slower, but you never send objects outside the
frustum to the renderer.  Therefore in computing costs for
the culling methods, you need more than just a cost
comparison of the intersection routines.

> Also what are the extra steps needed to use OBBs instead?

Code and document for culling OBBs against frustum is at
my web site, MgcIntersection.html page.

--
Dave Eberly
eb...@ma...
http://www.magic-software.com

Re: [Algorithms] View Frustum Culling

[Stephen J B. <sj...@li...>]

On Thu, 7 Sep 2000, Tim Johnston wrote:

> What is the best method for coarse bounding box frustum culling?
 
Use bounding spheres instead?   :-)

    http://web2.airmail.net/sjbaker1/frustcull.html

> From what I can gather you either use axis aligned bound boxes
> (AABBs) or oriented bounding boxes (OBBs), with OBBs having the
> advantage of tighter fitting but need extra computations for the
> culling process.

I'm a fan of poorly fitting shapes and more efficient culling -
if you can cull more efficiently, you can cull to a finer level
which makes up for the poorer fit of the bounding volume to the
shape.

However, opinions are split - between spheres (which don't have
to be axis-aligned), AABBs and OBBs.   All three can work well
for some applications and not so well for others.

> Also which culling method is best, perspective
> transform the BB and the view frustum to the perspective coordinate
> system (which with AABBs can result in testing two AABBs which is just
> 6 comparisons, however you have to transform all 8 vertices of the
> AABB) or testing the BB against the 6 planes of the view frustum (which
> seems much simpler and straightforward if that is all that is needed.)

It depends on the application - I prefer to transform the object into
the eye coordinates - but not do the perspective transform (which would
make the frustum into a cube) because:

  * For spheres, you don't want to do a perspective transform because
    then they are non-spherical - and that's A Bad Thing.

  * If the object passes the test, you'll need it's eye coordinates
    anyway - so the work isn't all lost.

You could also choose to transform the frustum into the coordinate
system of your objects - that's better if a lot of objects are
sharing the same coordinate space.

> So is comparing AABBs against the frustum planes the best way to go...

I think that there is no single 'best' approach if you know
nothing about the nature of the application and its models.
If you know something about the application then maybe you
can find a good reason to go on particular way.

----
Science being insufficient - neither ancient protein species deficient.

Steve Baker                      (817)619-2657 (Vox/Vox-Mail)
L3Com/Link Simulation & Training (817)619-2466 (Fax)
Work: sj...@li...           http://www.link.com
Home: sjb...@ai...       http://web2.airmail.net/sjbaker1

RE: [Algorithms] View Frustum Culling

[Brian M. <bma...@ra...>]

>> Use bounding spheres instead?   :-)

Drifting off topic a bit here, but it may be worth looking at swept sphere
volumes for this. The OBB people have a paper on them where they discuss the
pro's and con's from a proximity and collision point of view. Certainly
could be worth supporting line swept spheres or rectangle swept spheres as
an finer bounding volume for the frustrum culling. I think that they are
worth thinking about in places where you would use OBB's.

-Brian.