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

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

  • Исходная точка (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, что не может столкнуться ни с одним из треугольников, хотя технически она всегда должна сталкиваться с тем или другим, поскольку у них есть общее преимущество. Когда это происходит, точка проходит прямо между двумя треугольниками, разделяющими ребра. Я пометил одну строку кода знаком (!), потому что считаю, что именно здесь мне следует внести изменения.

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

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


3d math collision-detection
person Martin    schedule 19.09.2008    source источник

Ответы (5)


arrow_upward
10
arrow_downward

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

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

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

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

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

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

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

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

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

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

person Gareth Rees    schedule 18.02.2009

arrow_upward
2
arrow_downward

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

person Statement    schedule 19.09.2008
comment
Это хороший момент, хотя в арифметике с плавающей запятой вряд ли можно когда-либо рассчитывать. - person shoosh; 19.09.2008

arrow_upward
1
arrow_downward

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

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

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

person shoosh    schedule 19.09.2008

arrow_upward
0
arrow_downward

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

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

Это разумное решение?

person Martin    schedule 19.09.2008
comment
да. Это обычная практика, по крайней мере, так меня учили мои наставники, добавлять точность и терпимость (я не могу вспомнить, как он это называл). Если это решит вашу проблему и не приведет к появлению новых ошибок, тогда действуйте. - person Statement; 19.09.2008
comment
Единственная ошибка, которую я могу предвидеть, заключается в следующем: если я иду вверх по холму, когда я достигну вершины, я буду идти по расширенному треугольнику (или плавать невидимо) на очень небольшое расстояние (надеюсь, невидимое для пользователя), прежде чем я перейти к другому треугольнику. - person Martin; 19.09.2008
comment
Это зависит от того, как вы обращаетесь с экструзией. Представьте, что вся площадь треугольника покрыта сферами. Эта сфера - это расстояние от каждой стороны / грани, с которой вы выдавливаете свою геометрию. Это не будет проблемой со связанными вместе гранями, если экструзия одинакова на каждом треугольнике. - person Statement; 19.09.2008

arrow_upward
0
arrow_downward

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

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

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

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

person user4891    schedule 03.10.2008
comment
как последняя операция не квадратный корень q? sqrt () - person Lucas; 16.02.2009
comment
Последняя операция - умножение на a. - person user4891; 16.02.2009
comment
Вы все равно теряете точность, это распространение ошибки по Гауссу. - person Svante; 19.02.2009