Point-треугольник Столкновение обнаружение в 3D

Question

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

• исходной точке (х, у, г),
• искомой точки (х», у ', z') после применения сил.
• Два треугольника (A, B, C) и (B, C, D), которые разделяют края до н.э.

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

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.

• Использование теста менее чем равно не поможет; это неточность в пересечении луча и самолета, это проблема.

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

Вот некоторые подлинные решения:

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

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

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

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

Answer 2

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

Answer 3

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

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

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

Answer 4

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

Мое текущее решение заключается в добавлении небольшого количества толчка к краевому тесту. В основном, когда каждый треугольник тестируется, его края выталкиваются на очень небольшое количество, чтобы противодействовать ошибке в плавающей запятой. Аналогично тестированию, если результат вычисления с плавающей запятой меньше 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)); 
} 

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

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