Find whether two triangles intersect or not in 3D

I've written code for exactly this problem, but at the moment I cannot find it :-/. [Used in a paper: "On reconstruction of polyhedra from slices," Int. J. Comput. Geom. & Appl., 6(1) 1996: 103-112.] However, it is easy enough to describe.

First, you need robust code to decide if a point is above, below, or on the plane determined by one triangle. See, e.g., the code described in Computational Geometry in C, for this low-level task (which amounts to computing the signed volume of a tetrahedron), and others following; or in many other equivalent sources. If all three points of one triangle are to one side of the other, the intersection is empty.

Let vertex $a$ of triangle $\triangle abc$ be above triangle $t'=\triangle a'b'c'$ and $b$ and $c$ below. (I'll ignore the "on" cases for simplicity, but of course you must deal with them carefully.) If $t$ and $t'$ intersect, then it must be that an edge of one intersects the other; this is the key observation (also made by anon in another answer). So either $ab \cap t'$ or $ac \cap t'$ is nonempty, or the analogous conditions with the role of the triangles reversed.

Checking these conditions requires (again robust) code to determine if a segment intersects a triangle. This can be computed by solving simultaneously a parametric equation for the segment and the plane containing $\triangle t'$, obtaining the point $p$ of intersection, and determining if $p$ falls within $\triangle t'$. The latter is a separate and easy task.

So the whole can be accomplished by a number of confined, controlled, elementary computations.

I haven't had time to check the other answers in detail, so this may be equivalent... but the standard method of doing this is by the "separating axis theorem", which basically says that two convex objects are separated if there exists an axis so that the projections of the objects onto the axis do not overlap.

In the case of two triangles this amounts to just a couple of cross products, dot products and interval checks, which can be done very efficiently. A quick Google search turned up this:

http://www.geometrictools.com/Documentation/MethodOfSeparatingAxes.pdf