Given a box made up of vertices B0 through B7 and a point P how do i check if P lies inside the box?

Make a plane out of every face, using its four vertices and its normal (pointing out), and check if the point is "inside" by checking if Ax + By + Cz + D < 0.

There are faster ways, but conceptually, this is the simplest.

Cédric

I did the above method and got it working however i am using a much much simpler (and faster) method. I simply perform a 2D style check on the point :

if ( (p.x > box.p1 && p.x < box.p2) &&
(p.y > box.p3 && p.y < box.p4) &&
(p.z > box.p5 && p.z < box.p6) ) return TRUE;

now i know this method is not perfect because the box may rotate and then the funtion will return true even when the point isn''t in the box however this method is far far far faster than constructing planes etc and I only use this test as a triggor for my per polygon ray / triangle intersection tests. Is there anything wrong with doing things this way? Does anyone else do it?

You were right in your saying that the point will appear to be inside the box when it is outside, or outside the box when it is inside, if the box is rotated. Since you have 8 points, I assume you expect the box to be rotated. An extension of the plane method would be to compute planes at load-time, and simply rotate/transform the planes if the box moves. A) this would produce completely accurate results, with no if, ands or buts, and B) this is pretty fast (not as fast as yours, but still fast). Therefore, its a tradeoff between speed and accuracy, and the bigger the box, the bigger the error''s gonna be if the box rotates... Anyway, if you use the moving planes technique, I recommend putting P in the box object coords (e.g. the center of the box is the origin and the box is always oriented a certain way). This way, you don''t rotate the planes, but rotate the point, which, I assume, though don''t hold me to it, is faster.

Chris Pergrossi
< ctoan >
My Realm

I think you need to be more worried about it returning false when the point is actually in the box. If your box rotates at all, I don''t think you''ll have much success with that even as a rough boundary check. You''re probably better off using a rootles radius check from the middle of the box with the radius set to be the longest vertex distance from the centre.

This isn''t really my field though, so don''t take it as gospel. I''m sure there are several good references on this check out there on the Web.


mwtb

It should never return false if the point is in the box because if the box is rotated then the 8 vertices that make up the box are sorted so as to not cross over. I am pretty sure that this will always return true if the point is inside (feel free to prove me wrong). The thing is if you assume 60FPS then your doing 60 * 6 (sides) ray / plane intersection tests per second per object which is gonna get very expensive whereas with my method you may end up doing a complete model tri check more than you really need to but you cut down a hell of a lot of processing overall.

I just get the feeling that some wise guy is gonna pull this all apart though cause its not done this way in any books i''ve read but i really can''t see a big downside.

You didn''t mention anything about sorting. Mind-reading isn''t my area either and your code example referenced fixed vertex positions.

If you search through the vertices and compare the point with the largest and smallest vertex positions in the entire box (in other words, you compute the axis-aligned box that will contain the rotated box) then your check will work. You still may well be better off using a rootless radius check though, because then you wouldn''t have to search through your vertices every time as the rotation becomes irrelevant. Depends on how fast or slow the search is and how generally efficient each check is at avoiding your expensive test when your program is doing what it normally does.

mwtb

One faster way of doing it is to move the point from world space to box space, and then doing exactly your test.

Your method, from what I can see, won''t always return true if the point is inside. Make a Google search for Axis-Aligned Bounding Boxes (AABB). If your box ban be rotated, you should use a much larger box, whose sides have length 2 * sqrt((a/2)² + (b/2)² + (c/2)²)

where a, b and c are the sides of your box.

You should also look for a bounding sphere test.

Cédric