What''s the best way to find out if a triangle is within the boundries of a cube, such as in an octree calculation? Doing normal line/box intersection on each of the triangle''s edges doesnt seem to work unless at least one of the edge''s two points are in the box. So it wouldnt work if the line just cut through one of the cube''s faces.

Check the vertices. If all are in the box, the triangle is entirely within the box. If some, but not all are in the box, it''s partially in the box. If none are in the box, it''s outside the box.

(THINK OUTSIDE THE BOX!)

Well that would work except for one thing. All the points can exist outside the cube and yet the polygon can still intersect the cube with an edge..

[edited by - TheJakub on July 31, 2003 10:22:44 PM]

Well then why can''t you do the face-line intersection? If a line passes through two faces and neither of its vertices are in the box, the line still passes through the faces. The only way I could see a problem would be if you only checked for face-line intersection and all the vertices were in the box. Can''t you just check if all the vertices are in the box, and if not, check if any of the edges of the triangle intersect the faces of the box?

Actually yeah that sounds like a good idea, I guess I just didnt think about taking it that extra step. Thanks.

[edited by - TheJakub on July 31, 2003 10:56:12 PM]

I just realized that there will still be a problem if your triangle is big enough to completely enclose the cube without the triangle edges intersecting any of the cube sides.

You might fix this by doing plane-plane intersections instead of line-plane intersections, assuming you can correctly limit the range of the plane's triangle for possible intersection.

Edit Again: You'd only need to check the triangle plane intersections with 4 of the cube's planes, omitting any two oppsite faces of the cube.

(deleted another idea that wouldn't have worked)

[edited by - Geoff the Medio on August 1, 2003 9:18:52 PM]

OK, that makes a lot of sense actually. I''m thinking about creating a library now to help me with every type of intersection for good measure, I''m sure it''ll be worth it in the end. Thanks for the help, and I''ll be sure to give you an update with my progress.

there is a simple, fast and solid algorithm to detect intersections between a cube and a triangle. Look for Separation axis algorithm, and especially, in the Rapid Collision Detection Library source code. That stuff can be simplified for xis aligned bounding boxes

Cube (C) = convex
Triangle (T) = convex

So T and C do not intersect iff there is a separating plane. If the closest facets (0d, 1d or 2d) are :

a) face(C) and vert(T)
Then the separating plane is just plane( face(C) ). Which is the simple triangle bbox / versus box test. (a1) Each vert inside C <=> T inside. (a2) All verts outside the same plane( face(C) ) => T outside. Else bboxes intersect, continue. You can use bitfields and logical operations to see quickly if (a2) happens.

b) vert(C) and face(T). Use the nearest vertex trick by checking the signs of the triangle normal. So that''s one dot product only. Check the sign of the plane distance to the nearest vertex.

c) vert(C) and edge(T). The trick here is that you can consider the edges as small quads (thus faces) if you give your triangle a infinitesimal thickness.
Make some cross products and you''ll get the "normals" to these edges. Thus it''s like b) again.

d) edge(C) and edge(T). The most tricky one that ppl often forget. You proved it again here Simple : As the BBox is axis aligned, project the problem on each of the three planes : (x,y) (y,z) and (z,x). 4 edges become vertices. So it''s basically the same as the whole 3D algo but more simple.

If all the previous test have failed, it means the triangle is not fully inside nor outside. So it''s of course intersecting the box.

Else the algo is complete and exact coz :
face(C) and face(T) is covered by a).
face(C) and edge(T) is covered by a).
vert(C) and vert(T) is covered by a)
edge(C) and face(T) is covered by d)
edge(C) and vert(T) is covered by d)

Charles B: Does that algorithm regonize the case where the cube is bisected by the triangle's face, and none of the triangle's edges intersect a face or meet an edge or vertex of the cube?

Edit: speling

[edited by - Geoff the Medio on August 1, 2003 9:23:44 PM]