11 replies to this topic

[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?


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;
 }
 

[v71]

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.

[rouncer]

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

[JarkkoL]

rouncer said:

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

[.oisyn]

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.

[JarkkoL]

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

[rouncer]

thanks for help, guys!

[.oisyn]

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)

[JarkkoL]

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

[.oisyn]

JarkkoL said:

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

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

Quote

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.

Quote

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.

[JarkkoL]

.oisyn said:

I'm sorry but that's nonsense :)

Now that I know what you mean, I agree ;)

.oisyn said:

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

[.oisyn]

JarkkoL said:

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