   Triangle/Frustum Intersection Using SAT
  I'm fairly new to using SAT.  I think I understand the general principle, but in practice I'm not sure if I'm using it right (I think I might be overcalculating things).So I'm testing collision between a triangle and frustum.  This is for doing a box selection in a tool, and using bounding volumes for the models isn't accurate enough for my purposes.My basic algorithm looks like this:foreach Normal n in axisNormals  foreach Vert v in triangle    pos = dot(n,v)    min1 = min(min1, pos)    max2 = max(max1, pos) foreach Vert v in frustumCorners    pos = dot(n,v)    min2 = min(min2, pos)    max2 = max(max2, pos)    if (min1 > max2 || max1 < min2) return false   return trueThe question I have is what exactly axisNormals should contain when testing against a Frustum and a Triangle.  My understanding is that if I were dealing with two arbitrary convex meshes, axisNormals would be the normal of each triangle.  However, since a triangle isn't a convex mesh per se, this doesn't quite work.Right now axisNormals contains the normal of each plane in the frustum as well as:The triangle normalA vector perpendicular to each edgeA vector for each edgeAre all of these vectors needed?  Or can I get away with dropping the vector for each edge?  It seems like there are instances where projecting along that vector is necessary for finding potential axes.  Are any other vectors needed?  What's more, do I need to include the negative of each of these vectors?  I'm thinking no - it should produce the same results - but I could be missing something.   
  the algo look correct, you just need a set of axes to test against.Usually, the axes, when referring to an arbitrary convex object (triangle, box, pyramid, frustum, triangle) are.-> each face normals-> the cross product of every edge on A against every edge on Bby 'edge', you dont need to consider edges that are parallel to each other (in a box, instead of 12 edges, you reduce it to three, as 4 edges would share the same direction). same for faces. for boxes, you only need to consider three faces (instead of 6).in a frustum, you would have.5 faces6 edgesin atriangle you would have1 face3 edgesthe axes you would need to test against aretestAxis(triangle.normal).testAxis(frustum.nearplane.normal).testAxis(frustum.leftplane.normal).testAxis(frustum.rightplane.normal).testAxis(frustum.topplane.normal).testAxis(frustum.bottomplane.normal).testAxis((triangle.vertex[1] - triangle.vertex[0]).crossProduct(frustum.nearplane.vertex[0] - frustum.nearplane.vertex[1])).testAxis((triangle.vertex[1] - triangle.vertex[0]).crossProduct(frustum.nearplane.vertex[0] - frustum.nearplane.vertex[3])).testAxis((triangle.vertex[1] - triangle.vertex[0]).crossProduct(frustum.nearplane.vertex[0] - frustum.farplane.vertex[0])).testAxis((triangle.vertex[1] - triangle.vertex[0]).crossProduct(frustum.nearplane.vertex[1] - frustum.farplane.vertex[1])).testAxis((triangle.vertex[1] - triangle.vertex[0]).crossProduct(frustum.nearplane.vertex[2] - frustum.farplane.vertex[2])).testAxis((triangle.vertex[1] - triangle.vertex[0]).crossProduct(frustum.nearplane.vertex[3] - frustum.farplane.vertex[3])).testAxis((triangle.vertex[2] - triangle.vertex[1]).crossProduct(frustum.nearplane.vertex[0] - frustum.nearplane.vertex[1])).testAxis((triangle.vertex[2] - triangle.vertex[1]).crossProduct(frustum.nearplane.vertex[0] - frustum.nearplane.vertex[3])).testAxis((triangle.vertex[2] - triangle.vertex[1]).crossProduct(frustum.nearplane.vertex[0] - frustum.farplane.vertex[0])).testAxis((triangle.vertex[2] - triangle.vertex[1]).crossProduct(frustum.nearplane.vertex[1] - frustum.farplane.vertex[1])).testAxis((triangle.vertex[2] - triangle.vertex[1]).crossProduct(frustum.nearplane.vertex[2] - frustum.farplane.vertex[2])).testAxis((triangle.vertex[2] - triangle.vertex[1]).crossProduct(frustum.nearplane.vertex[3] - frustum.farplane.vertex[3])).testAxis((triangle.vertex[0] - triangle.vertex[2]).crossProduct(frustum.nearplane.vertex[0] - frustum.nearplane.vertex[1])).testAxis((triangle.vertex[0] - triangle.vertex[2]).crossProduct(frustum.nearplane.vertex[0] - frustum.nearplane.vertex[3])).testAxis((triangle.vertex[0] - triangle.vertex[2]).crossProduct(frustum.nearplane.vertex[0] - frustum.farplane.vertex[0])).testAxis((triangle.vertex[0] - triangle.vertex[2]).crossProduct(frustum.nearplane.vertex[1] - frustum.farplane.vertex[1])).testAxis((triangle.vertex[0] - triangle.vertex[2]).crossProduct(frustum.nearplane.vertex[2] - frustum.farplane.vertex[2])).testAxis((triangle.vertex[0] - triangle.vertex[2]).crossProduct(frustum.nearplane.vertex[3] - frustum.farplane.vertex[3])).;  you also have to be careful with degenerate axes (axis with length zero), say when a triangle edge is parallel to a frustum edge, the cross product of the two will be a zero-length vector. either use a tolerance in the test, or always pass the test is the axis length square is below a tolerance.if (min1 > max2+1.0E-8f || max1 < min2-1.0E-8f) return falseor...axisLengthSquared = axis.dotProduct(axis);if(axisLengthSquared < 1.0E-6f) return trueAlso, each of the SAT algorithm (box-box, triangle-box, triangle-frustum) benefits from optimisations. Dave Eberly and Christer Ericcson have optimised versions for each tests I believe. In the end, it's a bucket load less maths to perform and is much faster than the exhaustive SAT algorithm. But if performance is not the issue, a generic implementation will be plenty fast enough.And of course, that algo van be extended easily for bounding-box vs frustums, and so on. Triangle-triangle test has a special case that you may need to consider, when the two triangles are coplanar (then you need a version similar to a 2D test), but for volumes, there is no such requirements.[Edited by - oliii on May 15, 2009 10:16:09 AM];  the bottom line is, you need the cross product of edges, not the direction edges, or a perpendicular vector to an edge (which in 3D, would be an infinite set).The SAT test grows quite quickly if you apply it to complex volumes with many faces and edges (convex hulls).   