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

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

27 голосов
/ 18 августа 2011

Учитывая 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
}

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

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

1 Ответ

25 голосов
/ 20 августа 2011

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

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

enter image description here

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

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

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

...