# octree cube view frustrum

5 replies to this topic

### #1rouncer

Senior Member

• Members
• 2725 posts

Posted 25 October 2009 - 12:16 PM

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...
you used to be able to fit a game on a disk, then you used to be able to fit a game on a cd, then you used to be able to fit a game on a dvd, now you can barely fit one on your harddrive.

### #2poita

Senior Member

• Members
• 322 posts

Posted 25 October 2009 - 01:15 PM

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.

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

### #3rouncer

Senior Member

• Members
• 2725 posts

Posted 25 October 2009 - 01:36 PM

Thanks poita. I never would have guessed that.
you used to be able to fit a game on a disk, then you used to be able to fit a game on a cd, then you used to be able to fit a game on a dvd, now you can barely fit one on your harddrive.

### #4.oisyn

DevMaster Staff

• Moderators
• 1842 posts

Posted 25 October 2009 - 03:32 PM

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)
-
Currently working on: the 3D engine for Tomb Raider.

### #5poita

Senior Member

• Members
• 322 posts

Posted 25 October 2009 - 04:03 PM

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

### #6rouncer

Senior Member

• Members
• 2725 posts

Posted 26 October 2009 - 04:02 AM

you gotta ask what axis separation is every now and again.
you used to be able to fit a game on a disk, then you used to be able to fit a game on a cd, then you used to be able to fit a game on a dvd, now you can barely fit one on your harddrive.

#### 1 user(s) are reading this topic

0 members, 1 guests, 0 anonymous users