Обнаружение столкновения точка-треугольник в 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

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

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) );
}

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

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

Answer 5

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

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

Разумное ли это решение?