Найдите, пересекаются ли два треугольника или нет

Учитывая 2 набора точек

((x1, y1, z1), (x2, y2, z2), (x3, y3, z3)) и

((p1, q1, r1), (p2, q2, r2), (p3, q3, r3)), каждый из которых образует треугольник в трехмерном пространстве.

Как вы узнаете, пересекаются эти треугольники или нет?

Одно очевидное решение этой проблемы - найти уравнение плоскости, образованной каждым треугольником. Если плоскости параллельны, то они не пересекаются.

Далее, выясните уравнение линии, образованное пересечением этих плоскостей, используя нормальные векторы этих плоскостей.

Теперь, если эта линия лежит в обеих треугольных областях, то эти два треугольника пересекаются, иначе нет.

trianglesIntersect(Triangle T1, Triangle T2)
{
   if(trianglesOnParallelPlanes(T1, T2))
   {
      return false
   }
   Line L1 = lineFromPlanes(planeFromTriangle(T1), planeFromTriangle(T2))
   if(lineOnTriangle(T1, L1) AND lineOnTriangle(T2, L1))
   {
      return true
   }
   return false
}

Учитывая, что я знаю, как писать указанные выше функции, какие другие реализации треугольниковIntersect следует учитывать?

Существуют ли более быстрые алгоритмы, которые решают эту проблему?

Ответ 1

Посетите эту таблицу алгоритмов геометрического пересечения, предоставленную realtimerendering.com, посмотрите на запись для пересечений треугольников и треугольников и следуйте рекомендациям, например, Christer Ericson, Обнаружение столкновений в реальном времени, стр. 172. (Книга, которую я рекомендую высоко.)

Основная идея проста. Если два треугольника пересекаются, то либо два ребра одного треугольника пересекаются с другим (левая конфигурация на диаграмме ниже), либо один край каждого треугольника пересекает другую (правая конфигурация).

Итак, выполните шесть тестов пересечения сегментов треугольника и посмотрите, найдена ли какая-либо из этих конфигураций.

Теперь вы спрашиваете, как вы выполняете тест пересечения сегментов/треугольников? Ну, это легко. Посетите эту таблицу алгоритмов геометрического пересечения, посмотрите на запись для пересечения сегментов линии (луча)/треугольника и следуйте ссылкам...

(Важно отметить, что простой тест, описанный выше, неправильно обрабатывает копланарные треугольники. Для многих приложений это не имеет значения: например, при обнаружении столкновения между сетками треугольников копланарные случаи неоднозначны, поэтому неважно, какой результат будет возвращен. Но если ваше приложение является одним из исключений, вам нужно проверить это как особый случай или прочитать в Ericson для некоторых других методов, например, метод разделительной оси или Tomas Möller метод перекрытия интервалов.)