5 replies to this topic

[rouncer]

Whats the general way someone with an octree and a view frustrum (consisting of planes) tests if an axis aligned cube is inside the frustrum.

At the moment ive quickly written a corner testing algorythm, which tests the 8 corners with what side of the planes they are on, but if the octree node is large enough the frustrum could be contained within it, but the corners would all be tested as outside - and im kinda stuck.

Whats the solution?

thanks...

[poita]

To check if its outside, you don't check whether each vertex is outside, you check whether all vertices are on the wrong side of one plane.

This does lead to some false positives when the box is outside, but no single axis separates all vertices, but this is very rare, only happening at the edges of the frustum with large objects. Even then, many of those cases can be dispatched by doing a sphere test first.

[edit]

See: http://www.flipcode....m_Culling.shtml

[rouncer]

Thanks poita. I never would have guessed that.

[.oisyn]

You don't even have to test all 8 verts, you only need to test two opposing verts (the ones that extent farthest in the direction of the plane's normal). If you store the box using a center vector and an extents vector, just take the component absolute of the normal of the plane and dot that with the extents, call this x. Furthermore dot the (non-absolute) normal with the centre of the box, call this c. The box projected on the plane's axis is from c-x to c+x. But for a frustum test you're only interested in the smallest value (c-x), which you have to compare to the plane's distace to the origin (usually -d).

A further optimization can be made by the fact that lots of boxes have the same 'x' value as their size is the same, so you're left with a single dotproduct per box.

poita said:

Even then, many of those cases can be dispatched by doing a sphere test first.

Actually, for octree usecases, most false positives come from boxes lying near a frustum's edge. Casting a sphere around the box doesn't help in this case. If you are GPU limited and can spare some CPU cycles, it might be feasible to do a full SAT test by precalculating some support planes using the frustum's edges and the unit axes (as all boxes in the octree are axis aligned)

[poita]

Hmm yeah, you're right. I kind of wrote that without thinking about it :)

[rouncer]

you gotta ask what axis separation is every now and again.