Обнаружение столкновений Точка-Треугольник в 3D

Question

Как мне исправить ошибку с плавающей запятой в следующем физическом моделировании:

• Исходная точка (x, y, z),
• Желаемая точка (x', y', z') после приложения усилий.
• Два треугольника (A, B, C) и (B, C, D), которые имеют общее ребро BC

Я использую этот метод для обнаружения столкновений:

For each Triangle
    If the original point is in front of the current triangle, and the desired point is behind the desired triangle:
        Calculate the intersection point of the ray (original-desired) and the plane (triangle's normal).
        If the intersection point is inside the triangle edges (!)
            Respond to the collision.
        End If
    End If
Next Triangle

Проблема, с которой я сталкиваюсь, заключается в том, что иногда точка попадает в серую область математики с плавающей запятой, где она находится настолько близко к линии BC, что ей не удается столкнуться ни с одним из треугольников, хотя технически она всегда должна сталкиваться с одним или другим, поскольку они имеют общее ребро.Когда это происходит, точка проходит прямо между двумя треугольниками, разделяющими ребра.Я пометил одну строку кода символом (!) потому что я верю, что именно там мне следует что-то изменить.

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

Я специально использую скалярное произведение и нормали треугольника для всего моего фронтального тестирования.

Answer 1

Это неизбежная проблема при съемке одного луча по некоторой геометрии с ребрами и вершинами.Удивительно, как при физическом моделировании, кажется, выявляются малейшие числовые неточности!

Некоторые объяснения и решения, предложенные другими респондентами, не сработают.В частности:

• Числовая неточность действительно может привести к тому, что луч "провалится сквозь щель".Проблема в том, что мы пересекаем луч с плоскостью ABC (получая, скажем, точку P), прежде чем проводить тестирование по прямой BC.Затем мы пересекаем луч с плоскостью BCD (получая, скажем, точку Q), прежде чем проводить тестирование по прямой BC.P и Q оба представлены ближайшим приближением с плавающей запятой;нет никаких оснований ожидать, что они точно лежат на плоскостях, на которых они должны лежать, и поэтому есть все шансы, что вы можете иметь как P слева от BC, так и Q справа от BC.

• Использование теста "меньше или равнее" не поможет;проблема в неточности пересечения луча и плоскости.

• Квадратные корни - это не проблема;вы можете выполнить все необходимые вычисления, используя точечные произведения и деление с плавающей запятой.

Вот несколько подлинных решений:

• Для выпуклых сеток вы можете просто протестировать все плоскости и игнорировать ребра и вершины, как вы говорите (таким образом, полностью избегая проблемы).

• Не пересекайте луч с каждым треугольником по очереди.Вместо этого используйте скалярное тройное произведение.(Этот метод выполняет точно такую же последовательность вычислений для луча и ребра BC при рассмотрении каждого треугольника, гарантируя, что любая числовая неточность, по крайней мере, согласована между двумя треугольниками.)

• Для невыпуклых сеток придайте ребрам и вершинам некоторую ширину.То есть поместите небольшую сферу в каждую вершину сетки и тонкий цилиндр вдоль каждого края сетки.Пересеките луч с этими сферами и цилиндрами, а также с треугольниками.Эти дополнительные геометрические фигуры останавливают луч, проходящий через ребра и вершины сетки.

Позвольте мне настоятельно рекомендовать вам эту книгу Обнаружение столкновений в режиме реального времени автор: Кристер Эриксон.На страницах 446-448 обсуждается именно эта проблема, а на страницах 184-188 объясняется подход скалярного тройного произведения к пересечению луча с треугольником.

Answer 2

Похоже, вы не включаете тестирование, если оно находится НА краю (вы пишете "Внутри краев треугольника").Попробуйте изменить код на "меньше или равно" (внутри или перекрывающийся).

Answer 3

Я нахожу несколько маловероятным, что ваш луч попадет точно между треугольниками таким образом, чтобы вступила в силу точность с плавающей запятой.Вы абсолютно уверены, что это действительно проблема?

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

Это, по крайней мере, позволит вам проверить, действительно ли проблема заключается в ошибке с плавающей запятой или в чем-то более вероятном.

Answer 4

@Заявление:Я действительно уже использую сравнение "больше или равно" в своем коде, спасибо за предложение.+1

Мое текущее решение состоит в том, чтобы добавить небольшое количество подталкивания к тесту edge.В основном, когда тестируется каждый треугольник, его края выталкиваются на очень малую величину, чтобы нейтрализовать ошибку с плавающей запятой.Что-то вроде тестирования, если результат вычисления с плавающей запятой меньше 0,01, а не проверки на равенство нулю.

Является ли это разумным решением?

Answer 5

Если вы проводите измерения расстояний, следите за квадратными корнями.У них есть отвратительная привычка выбрасывать половина о вашей точности.Если вы сложите несколько таких вычислений вместе, у вас могут быстро возникнуть большие проблемы.Вот функция расстояния, которую я использовал.

double Distance(double x0, double y0, double x1, double y1)
{
  double a, b, dx, dy;

  dx = abs(x1 - x0);
  dy = abs(y1 - y0);

  a = max(dx, dy));
  if (a == 0)
    return 0;
  b = min(dx, dy);

  return a * sqrt( 1 + (b*b) / (a*a) );
}

Поскольку последняя операция не является квадратным корнем, вы больше не теряете точность.

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