Bug in BoundingFrustum.Contains()?

--Alan---

If i write the following code:
BoundingFrustum f = new BoundingFrustum(new Matrix(1, 2, 3, 4, 5, 6, 7, 8, 9, 8, 7, 6, 5, 4, 3, 2));
Vector3 vector = new Vector3(1,1,1);
BoundingBox box = new BoundingBox(vector, vector);
ContainmenType t;

t = f.Contains(vector);
Console.WriteLine(t);

t = f.Contains(box);
Console.WriteLine(t);

I'd expect both to give the same answer. Either both are contained or both are disjoint. However the Frustum contains the point but the box is disjoint. What's going on

neogir

Your bounding box is defined as zero volume. So it doesn't exist physically but just an program instance. See below:

  BoundingFrustum f = new BoundingFrustum(new Matrix(1, 2, 3, 4, 5, 6, 7, 8, 9, 8, 7, 6, 5, 4, 3, 2));
                Vector3 vector = new Vector3(1, 1, 1);
                Vector3 epsilon  = new Vector3(.000001f, .000001f, .000001f);
                BoundingBox box = new BoundingBox(vector, vector + epsilon);
                ContainmentType t;

                t = f.Contains(vector);
                Console.WriteLine(t);

                t = f.Contains(box);
                Console.WriteLine(t);

--Alan---

Hi,

I know the box has zero volume, thats why i choose it as a test ;) What i thought would've happened is that a box with all corners being at (1,1,1) would be like the point (1,1,1) and so should still count as being contained within the Frustum just like the Vector at (1,1,1) is in the frustum.

Is there any documentation explaining what counts as being "intersecting" or "disjoint" or "contained" I.e. is a box Contained or Intersectin if one of the boxes planes lies exactly on top of one of the Bounding Frustum planes but the rest are inside the Frustum

I cant seem to find useful documentation on that kind of thing.

Thanks.

neogir

Intersecting - both volumes are not equal and have one common point at least ;
Contained    -  both volumes are equal, or the  second volume lies inside the first one;
Disjoint     - all other cases.

--Alan---

That can't be right.

Suppose i have two spheres of radius 10 one centered at 0,0,0 the other centered at 0,0,5. They have the same volume, which by your logic means they are Contained. Yet they most definitely are not contained. They are intersecting. Hence i assume that those definitions arent from official documentation, or i'm misunderstanding something.

The way i look at it is as follows:
Contained: Body A is contained by Body B if all the points of Body A lie inside Body B.
Intersecting: Body A intersects with Body B if one or more points in Body A lie inside Body B *and* one or more points in Body A lie outside of Body B.
Disjoint: Body A is disjoint from Body B if all the points in Body A lie outside of Body B.

By that definition volume is irrelevant. Hence a BoundingBox of volume 0 still should be contained in my Frustum. However this isn't true. I'd like to see official documentation somewhere explaining these kinds of things.

neogir

A bounding box  can be  defined in different manners.  In general, it has a size W x H x D, position and orientation, like any 3D object. 
The "same" or "equal" means that both volumes are equal in size, position  and orientation.

--Alan---

Gotcha, i understand now. I was misunderstanding your use of the word volume. Personally, i think it's wierd that a Point at (1,1,1) is contained but a BoundingBox with corners all at (1,1,1) isn't contained. But i suppose it's one of those things i just have to accept.

Thanks for being patient.

neogir

As to your zeroed bounding volume : all operations with a volume of zero size are discarded by compiler as having no sense at all.

XMas offtop - how to prove that every number is equal to its half.

1) Let A = B.
2) A * A  = A * B
3) A * A - B * B  = A * B - B * B
4) (A - B) * (A + B) = B * (A - B)

after cancelling by (A - B)

5) A + B = B

Just because of it, operations with a zeroed volume box are restricted.

--Alan---

all operations with a volume of zero size are discarded by compiler as having no sense at all.

Well, zero volume can have absolutely nothing to do with it. Check out this code:
http://pastebin.ca/292561

As you can see, deciding whether a bounding box is contained within a frustum depends only on checking that each point in the bounding box is on the correct side of each of the planes of the Frustum. You don't care what the volume (W x D x H) is.

A compiler cannot silently drop code that works on 0 volume BoundingBoxes. How the hell would the compiler know if i *need* that box or not There'd be an exception thrown if i tried to divide by the volume of the box, but that the code would be there and the code would run. Without the extra check for box.Min == box.Max i will (correctly ) decide that the box is actually inside the Frustum as all the corners of the box are inside the frustum.

EDIT: The proof doesn't work because when you divided by (a-b) you divided by zero. Thus invalidating your argument ;)

Jon Watte

It's not enough to test whether there is a single plane that excludes all the vertices. A box that's tilted just outside the corner of a frustum will then be considered "inside" even when it's "outside."

If the test is supposed to be accurate, you need to also test the three major axes of the box, and then the cross product between the three major axes of the box, and the six remaining major axes of the frustum (given that the plane normals are five axes in themselves), giving you a complete Separating Axes Theorem test.

Note that you can't actually test those additional axes for a zero-size box, because it has no "major axes." One implementation of that test would be to revert to a point test. Another, equally valid, implementation would be to just punt and say "not included" because it has zero volume.

neogir

A compiler cannot silently drop code that works on 0 volume BoundingBoxes. How the hell would the compiler know if i *need* that box or not

Sometimes a compiler using to be a clever beast.
You can follow the analogy with an "if (x && y) vs if (x & y)". If in the expression "if (x && y)" x == false then compiler returns false just discarding y. But if the y expression must be evaluated you'd rather use "if (x & y)" instead. In the case of intersection test of the bounding volumes, if one of them has zero value (it is really means it has no boundary), compiler returns Disjoint value. Quite logically.

--Alan---

. In the case of intersection test of the bounding volumes, if one of them has zero value (it is really means it has no boundary), compiler returns Disjoint value. Quite logically.

Not really. That's a runtime decision. The only time in which the compiler could optimise that test would be if X and Y were both hardcoded values. But if they're both hardcoded values, then theres no point in having the if(x && y) statement at all.

It's a runtime decision to decide if Y needs to be evaluted if X is false. Unless you provide specific optimisations for each individual class and for each individual method a compiler cannot tell that my boundingBox is of 0 volume. No compiler has those kinds of optimisations therefore no compiler can do that.

If you don't believe me, take the code. Decompile it and see for yourself that the compiler hasn't optimised away the test (mostly because it's impossible). Be warned that you probably shouldn't decompile MS libraries, so your best bet would be to write your own sample and decompile that.

It's not enough to test whether there is a single plane that excludes all the vertices. A box that's tilted just outside the corner of a frustum will then be considered "inside" even when it's "outside."

Can you provide a testcase for when the code in pastebin that i linked above will fail Thinking about it geometrically, a BoundingBox can only have one or more points outside of the frustum if there is also a corner of the BoundingBox outside of the frustum. There is no way that i can imagine rotating a BoundingBox so that one of its edges would be outside of the frustrum without one of it's corners also being outside of the frustum.

Therefore the implementation above (which is under the MIT/X11 license, so you can look at the code freely) is correct in that it checks each corner of the BoundingBox to see if that corner is inside the frustum.

Checking that a specific corner (Vector3) is inside the frustum is as easy as substituting into the equation:
ax + by + cy + d (equation of a plane) and verifying that the answer is negative when you substitute in your point for X, Y, Z. If point X,Y,Z lies on the negative side of all 6 bounding planes of the frustum, that point is without a doubt inside the frustum. The reason for choosing the negative side is because the normals are pointing outwards.

There should be no need to test the major axes. Unless i'm misunderstanding something (which wouldn't be new ;) ).

Thanks.

Jon Watte

Your pastebin doesn't have that problem, but has another problem: it will reject boxes that actually intersect the frustum.

Consider a box that is bigger than the frustum: all the corners will be outside, but there will be content intersecting.
Also consider a box that is smaller than the frustum, but is tilted such that one edge cuts through the upper corner of the frustum, while keeping all points outside the frustum. This box will also be rejected, but there is content intersecting.

The traditional "quick test" for box/frustum, for culling purposes, is to say that a box may intersect if there is not a single plane that culls away all points. This is conservative, in that it may return some false positives (such I described in the first post), but at least it gives no false negatives. To turn it into an accurate test, instead of a conservative test, you have to add the separating axes as I suggested above.

A good reference for collision and intersection in general is the "real-time collision detection" book by Chriter Ericson. Another good reference is the "magic software" engine by Dave Eberly (and described in most of his books). I suggest you get one of them, and read them carefully, as they go through many of the common pitfalls that come up in computational geometry.

--Alan---

Yup, you're exactly right. I realised yesterday that i never considered the case where the BoundingBox would have all it's corners outside the box yet the line from corner A to corner B cuts through the frustum. I haven't had time to run through the code to update it for this case. It wont be a quick fix though.

I'll definitely take a look at one (or maybe both if money allows) of those books. I've learned a lot :)

Thanks.