octree frustrum

Fd80f81596aa1cf809ceb1c2077e190b
0
rouncer 103 Aug 01, 2011 at 15:08

basicly im taking the 4 corners of the screen producing vectors, then making frustrum planes for the 4 sides of the screen, then
then a do a dot coord check with the 8 corners of the box, if all the points are outside any frustrum plane testing all 4 planes then its not in the frustrum.
unfortunately its rejecting too much, what have i got wrong?

ignore vecin and vecout, thats just my crappy wrapper i wrote terribly.

bool in_frustrum=true;
 
 PLANE fplane[4];
 
 VEC corner[4];
 VEC orig,dir;
 inverse_project(view,proj,-1,1,orig,dir);
 corner[0]=vecout(vecin(orig)+vecin(dir));
 inverse_project(view,proj,1,1,orig,dir);
 corner[1]=vecout(vecin(orig)+vecin(dir));
 inverse_project(view,proj,1,-1,orig,dir);
 corner[2]=vecout(vecin(orig)+vecin(dir));
 inverse_project(view,proj,-1,-1,orig,dir);
 corner[3]=vecout(vecin(orig)+vecin(dir));
 
 fplane[0]=XMPlaneFromPoints(vecin(orig),vecin(corner[0]),vecin(corner[1]));
 fplane[1]=XMPlaneFromPoints(vecin(orig),vecin(corner[1]),vecin(corner[2]));
 fplane[2]=XMPlaneFromPoints(vecin(orig),vecin(corner[2]),vecin(corner[3]));
 fplane[3]=XMPlaneFromPoints(vecin(orig),vecin(corner[3]),vecin(corner[0]));
 
 int i;
 for(i=0;i<4;i++)
 {
  bool inside=false;
  if(vecout(XMPlaneDotCoord(fplane[i],vecin(VEC(pos.x,pos.y,pos.z)))).x<0) inside=true;
  if(vecout(XMPlaneDotCoord(fplane[i],vecin(VEC(pos.x+size,pos.y,pos.z)))).x<0) inside=true;
  if(vecout(XMPlaneDotCoord(fplane[i],vecin(VEC(pos.x+size,pos.y+size,pos.z)))).x<0) inside=true;
  if(vecout(XMPlaneDotCoord(fplane[i],vecin(VEC(pos.x,pos.y+size,pos.z+size)))).x<0) inside=true;
  if(vecout(XMPlaneDotCoord(fplane[i],vecin(VEC(pos.x+size,pos.y,pos.z+size)))).x<0) inside=true;
  if(vecout(XMPlaneDotCoord(fplane[i],vecin(VEC(pos.x+size,pos.y+size,pos.z+size)))).x<0) inside=true;
  if(vecout(XMPlaneDotCoord(fplane[i],vecin(VEC(pos.x,pos.y+size,pos.z+size)))).x<0) inside=true;
  if(inside==false) in_frustrum=false;
 }

11 Replies

Please log in or register to post a reply.

Ceee4d1295c32a0c1c08a9eae8c9459d
0
v71 105 Aug 01, 2011 at 15:32

From a mathematical point of view it looks ok, i think the problem is in the logic
unrolling the loop might help

test first box to check if it is inside the frustum
second
..
eigth

if All of them are outside then the cube is outside
if All of them are inside, the cube is inside

if all of 8 points are not inside or outside then ,the cube is intersecting the frustum

so you have to flag each box’s points and then do a check on the status of all those flags, i think you exit with a false too early from the for cycle.

Fd80f81596aa1cf809ceb1c2077e190b
0
rouncer 103 Aug 01, 2011 at 15:55

hey thanks for the quick reply.

i tried what you said, but it didnt work, all it did was basicly turn the culling off completely… but… i worked out the problem anyway.

thanks for hinting about the actual idea being fine, you are right i dictated exactly what you should do, i wasnt actually sure tho.

the problem is if you count the points im checking its 7 not 8 :) yes, thats why.

works now.

oh yeh i mean “frusTUM” :) hehe

Fe8a5d0ee91f9db7f5b82b8fd4a4e1e6
0
JarkkoL 102 Aug 02, 2011 at 09:24

@rouncer

basicly im taking the 4 corners of the screen producing vectors, then making frustrum planes for the 4 sides of the screen, then
then a do a dot coord check with the 8 corners of the box, if all the points are outside any frustrum plane testing all 4 planes then its not in the frustrum.
unfortunately its rejecting too much, what have i got wrong?

That’s not the correct logic for the frustum check: Even when all the corners of the box are outside the frustum, the box can still intersect the frustum. For proper Frustum-Box check you could use separating axis theorem.

Cheers, Jarkko

340bf64ac6abda6e40f7e860279823cb
0
_oisyn 101 Aug 02, 2011 at 10:45

You should not check whether the points are inside the frustum, you should check whether all points are on the outside of a single plane of the frustum. This is basically the separating axis test without testing the frustum against the box’ planes and the edge tests. Only testing the frustum planes will have some false positives (but no false negatives such as you are having now). Incorporating the other two tests will give you 100% accurate results.

Fe8a5d0ee91f9db7f5b82b8fd4a4e1e6
0
JarkkoL 102 Aug 02, 2011 at 11:22

If you are not after 100% accuracy, a better way is to expand the frustum planes by the radius of the box (i.e. the distance from the box center to a corner, or better yet use tightly fit bounding sphere) and test if the center point of the box is within the extended frustum. That will give you far less false positives.

For objects which pass the test you can do more precise check with the SAT-test to gain 100% accuracy, e.g. test if all points of a box are within the original frustum and if not test with SAT for potential rejection.

Cheers, Jarkko

Fd80f81596aa1cf809ceb1c2077e190b
0
rouncer 103 Aug 02, 2011 at 13:40

thanks for help, guys!

340bf64ac6abda6e40f7e860279823cb
0
_oisyn 101 Aug 02, 2011 at 13:44

You could do a sphere test, but essentially you’ll only need to test 1 box vertex per plane anyway - the one that is extreme in the opposite direction of the plane normal (assuming outward pointing plane normals).

If you work with axis aligned bounding boxes and you store them with a center and an extents vector, you can simply calculate the distance by:
dot(plane.normal, box.center) - dot(abs(plane.normal), box.extents)

If you have an oriented bounding box stored with a center vector and 3 extent vectors (for x, y and z), you can calculate the distance by:
dot(plane.normal, box.center) - abs(dot(plane.normal, box.extentX)) - abs(dot(plane.normal), box.extentY) - abs(dot(plane.normal, box.extentZ)

Fe8a5d0ee91f9db7f5b82b8fd4a4e1e6
0
JarkkoL 102 Aug 02, 2011 at 14:41

It’s not really a matter of performance of the test, but that testing the box against a frustum as you suggested gives large number of false positives. Essentially every object in the world that intersects an infinite frustum plane is considered visible by your algorithm. It’s also slower than testing the center of the bounding box against the extended frustum.

Edit: ok, I think I misunderstood what you suggested, i.e. check all the planes always if the box is completely outside any of the planes. In that case the number of false positives is about the same as with sphere test. I thought you meant that if a box intersect any of the planes you mark it visible.

Cheers, Jarkko

340bf64ac6abda6e40f7e860279823cb
0
_oisyn 101 Aug 02, 2011 at 14:49

@JarkkoL

but that testing the box against a frustum as you suggested gives large number of false positives.

I’m sorry but that’s nonsense :P. By creating a sphere around the box, you essentially add extra cases to the number of false positives.

Essentially every object in the world that intersects an infinite frustum plane is considered visible by your algorithm.

This is not true. Only those boxes that are (partly) behind of *all* frustum planes will contain false positives, but your method using the sphere will have exactly the same outcome in those cases.

It’s also slower than testing the center of the bounding box against the extended frustum.

Yes, but more exact, especially in the case of elongated boxes.

Fe8a5d0ee91f9db7f5b82b8fd4a4e1e6
0
JarkkoL 102 Aug 02, 2011 at 15:07

@.oisyn

I’m sorry but that’s nonsense :)

Now that I know what you mean, I agree ;)@.oisyn

By creating a sphere around the box, you essentially add extra cases to the number of false positives

Yes, which is why you should prefer tightly fit spheres instead. Depends on the object which creates more false positives. At this level of precision I would choose the more efficient algorithm and use SAT to cull out the border cases.

Cheers, Jarkko

340bf64ac6abda6e40f7e860279823cb
0
_oisyn 101 Aug 02, 2011 at 15:13

@JarkkoL

Yes, which is why you should prefer tightly fit spheres instead.

I just realized you’re talking about spheres tightly fit around the mesh, not around the box itself. Then yes, you have a point :)

So much for clear communication :P