Определение факта пересечения 3D треугольников

Есть 2 треугольника заданные тремя пространственными координатами (x,y,z) Допустим у нас есть подозрение по их пересечению треугольников (образующие кубы пересекаются).
Вопрос: как определить факт пересечения этих треугольников. Поясню. Мне не нужно знать в каком отрезке они пересекаются, и даже не нужно знать одну из точек пересечения. Меня интересует "быстрый" алгоритм поиска факта пересечения, т.е. true или false
З.Ы.: Искал в интернете, есть алгоритмы нахождения пересечения, а факта нет. И существуют ли вообще упращенные алгоритмы?
З.Ы.: Кое что нашёл. Есть сайт RealTimeRendering, Там есть метод Fast Triangle-Triangle Intersection test by Tomas Möller. Пока изучаю его. Подозреваю, что есть более быстрые алгоритмы.

Ответ

После поисков по просторам итернетов я нашел оптимальный способ описанный Томасом Моллером. Написал код под C# для данного алгоритма.
public bool PointInTriangle2D(float[][] t, float[] p) { bool inside = false; int j = 2; // = 3 - 1 for (int i = 0; i < 3; i++) { if ((t[i][1] < p[1] && t[j][1] >= p[1] || t[j][1] < p[1] && t[i][1] >= p[1]) && (t[i][0] + (p[1] - t[i][1]) / (t[j][1] - t[i][1]) * (t[j][0] - t[i][0]) < p[0])) inside = !inside; j = i; } return inside; }
public bool Moller1997b(Vertex[] V0, Vertex[] V1) { return Moller1997b(new Vertex[2][] { V0, V1 }); }
public bool Moller1997b(Vertex[][] V) { float[][] dv = new float[2][]; int[][] sign = new int[2][]; float[][] pv = new float[2][]; float[][] t = new float[2][]; float[][] triange2D = new float[3][]; float[] point2D = new float[2]; for (int j = 0; j < 3; ++j) triange2D[j] = new float[2]; for (int j = 0; j < 2; ++j) { dv[j] = new float[3]; sign[j] = new int[3]; pv[j] = new float[3]; t[j] = new float[2]; }
//Находим вектор-нормаль ко второму треугольнику Vertex N1 = (V[1][1] - V[1][0]).VectorProduct(V[1][2] - V[1][0]); //и коэфициент плоскости второго треугольника float d1 = -N1.ScalarProduct(V[1][0]); //Уровнение плоскости второго треугольника будет выглядеть //π2 : N2*X+d2=0, где X-любая точка плоскости (одна из точек v2) //Но нам это в данной задаче не важно //Проверяем с какой стороны плоскости лежат точки первого треугольника for (int i = 0; i < 3; ++i) { dv[0][i] = N1.ScalarProduct(V[0][i]) + d1; sign[0][i] = Math.Abs(dv[0][i]) > epsilant ? Math.Sign(dv[0][i]) : 0; } //Треугольник 0 не пересекается с плоскостью другого треугольника if (sign[0][0].Equals(sign[0][1]) && sign[0][1].Equals(sign[0][2]) && !sign[0][0].Equals(0)) return false; //Треугольники в одной плоскости //Как показала практика такие случаи оооочень большая редкость if (sign[0][0].Equals(sign[0][1]) && sign[0][1].Equals(sign[0][2]) && sign[0][0].Equals(0)) { //Теперь выберем на какую плоскость (xy, yz, xz) спроецируем треугольники float aNX = Math.Abs(N1.X); float aNY = Math.Abs(N1.Y); float aNZ = Math.Abs(N1.Z); float maxN = Math.Max(aNX, Math.Max(aNY, aNZ)); //Какую компоненту будем игнорить int ignoreIndex = (aNX.Equals(maxN)) ? 0 : (aNY.Equals(maxN)) ? 1 : 2; //Какие компоненты будем использовать для 2D координат int iX = ignoreIndex == 0 ? 2 : 0; int iY = ignoreIndex == 1 ? 2 : 1; //Проверка принадлежности хотябы одной точки треугольника 0 треугольнику 1 //http://ru.stackoverflow.com/questions/464787/Точка-внутри-многоугольника for (int p = 0; p < 3; ++p) { for (int i = 0; i < 3; ++i) { triange2D[i][0] = V[1][i][iX]; triange2D[i][1] = V[1][i][iY]; } point2D[0] = V[0][p][iX]; point2D[1] = V[0][p][iY]; if (PointInTriangle2D(triange2D, point2D)) return true; } //или центр масс второго треугольника 1 попадает в треугольник 0. Заодно включает //вопрос совподения (или очень близкого к совпадению) трех точек одного треугольника и трех точек другого треугольника for (int i = 0; i < 3; ++i) { triange2D[i][0] = V[0][i][iX]; triange2D[i][1] = V[0][i][iY]; } point2D[0] = (V[1][0][iX] + V[1][1][iX] + V[1][2][iX]) / 3f; point2D[1] = (V[1][0][iY] + V[1][1][iY] + V[1][2][iY]) / 3f; if (PointInTriangle2D(triange2D, point2D)) return true; return false; } Vertex N0 = (V[0][1] - V[0][0]).VectorProduct(V[0][2] - V[0][0]); float d0 = -N0.ScalarProduct(V[0][0]); for (int i = 0; i < 3; ++i) { dv[1][i] = N0.ScalarProduct(V[1][i]) + d0; sign[1][i] = Math.Abs(dv[1][i]) > epsilant ? Math.Sign(dv[1][i]) : 0; } //Треугольник 1 не пересекается с плоскостью другого треугольника if (sign[1][0].Equals(sign[1][1]) && sign[1][1].Equals(sign[1][2]) && !sign[1][0].Equals(0)) return false; //Треугольники на разных плоскостях Vertex D = N0.VectorProduct(N1); float aDX = Math.Abs(D.X); float aDY = Math.Abs(D.Y); float aDZ = Math.Abs(D.Z); float maxD = Math.Max(aDX, Math.Max(aDY, aDZ)); int Tindex = (aDX.Equals(maxD)) ? 0 : (aDY.Equals(maxD)) ? 1 : 2; for (int j = 0; j < 2; ++j) { //l и r это индексы точек находящихся по одну из сторон плоскости j int c = 1, l = 0, r = 2; if (sign[j][0].Equals(sign[j][1])) { c = 2; r = 0; l = 1; } else if (sign[j][1].Equals(sign[j][2])) { c = 0; r = 2; l = 1; } //Иначе оставляем без изменений for (int i = 0; i < 3; ++i) pv[j][i] = pv[j][i] = V[j][i][Tindex];//D.ScalarProduct(V[j][i]); //pv[j][i] = V[j][i][Tindex]; t[j][0] = pv[j][l] + (pv[j][c] - pv[j][l]) * dv[j][l] / (dv[j][l] - dv[j][c]); t[j][1] = pv[j][r] + (pv[j][c] - pv[j][r]) * dv[j][r] / (dv[j][r] - dv[j][c]); if (t[j][0] > t[j][1]) { float _t = t[j][0]; t[j][0] = t[j][1]; t[j][1] = _t; } } return (t[0][0] < t[1][1]) && (t[0][1] > t[1][0]); }
где ScalarProduct и VectorProduct это векторные и скалярные произведения соответственно
public float ScalarProduct(Vertex rhs) { return X * rhs.X + Y * rhs.Y + Z * rhs.Z; }
public Vertex VectorProduct(Vertex rhs) { return new Vertex((Y * rhs.Z) - (Z * rhs.Y), (Z * rhs.X) - (X * rhs.Z), (X * rhs.Y) - (Y * rhs.X)); }