Обнаружение столкновений в 3D: выпуклая оболочка против выпуклой оболочки, требуется положение и нормаль

Игровые движки обычно моделируют во времени серию дискретных шагов. Как следствие, система столкновений может попасть в сложные (дорогостоящие в вычислительном отношении) случаи из-за взаимопроникновения (ваш случай) или когда вещи движутся быстро - туннелирование, когда A находится с одной стороны от B на шаге N и полностью с другой стороны от B. на шаге N + 1. Это еще труднее, если вам нужно иметь дело с многотельным контактом, непрерывным контактом, невыпуклым, шарнирным или мягким предметом. Ой! мы моделируем весь мир.

Вы хотите сделать "игровую физику" и использовать приближения, чтобы выкупить частоту кадров ... В конце концов, вы можете скрыть много ошибок с помощью кучи дыма или световых вспышек. :-)

Существует класс алгоритмов, которые явно учитывают смоделированное время, чтобы помочь системе столкновений. Есть много способов реализовать систему «непрерывного обнаружения столкновений». Вы можете начать здесь, но сначала вы должны внимательно прочитать, прежде чем переходить к написанию кода. К счастью, о столкновениях написано много. вот хорошее место для начала https://docs.unity3d.com/Manual/ContinuousCollisionDetection.html https://pybullet.org/Bullet/phpBB3/viewtopic.php?t=20

Вот одна предлагаемая эвристика, которая может работать в вашей существующей системе ... Этот эвристический метод может работать в игре, подобной Astroids 3D, где объекты свободно плавают в пространстве. Этого может быть достаточно для того, что вам нужно.

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

Предположим, вы обнаружили потенциальное столкновение между объектами A и B в момент времени = текущий.

Для time = previous предположим, что A и B не контактируют.

Вычислите ближайшие точки на поверхностях A и B, соответственно, в time = prev, используя предыдущие векторы состояния A и B. (closestA, closestB).

Отрезок линии (closestA, closestB) будет иметь ненулевую длину в момент time = previous. Вы можете просто использовать closestB для своей позиции и normal, но это будет иметь некоторую ошибку, пропорциональную длине отрезка линии.

Так что выполните двоичный поиск по времени и минимизируйте ошибку, найдя время, когда A сколь угодно близко к B. На каждом этапе поиска уменьшайте размер шага поиска вдвое. 0,5, 0,25, 0,125 ... до тех пор, пока длина (closestA, closestB) не станет ниже порога ошибки, или вы откажетесь.

Это должно дать вам приемлемое приблизительное решение для простых случаев ...

Кроме того, вы сказали, что используете теорему об оси разделения в качестве «первой проверки». На самом деле для меня это звучит дорого, если это действительно «первая проверка».

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

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

Кроме того, тест сфера-сфера является очень быстрым предварительным тестом, чтобы увидеть, перекрываются ли даже ограничивающая сфера двух выпуклых объектов.

Я бы сделал это:

1. определения

   пусть есть 2 триангулированные трехмерные выпуклые оболочки A,B. Каждый из них определил центр pc и список точек поверхности p0,p1,p2,... и список треугольников t0,t1,t2,.... Каждый треугольник должен был также вычислить его нормальное n0,n1,n2,... указывающее направление.

2. вычислить максимальное значение внутренней точки попадания q

   поэтому давайте проверим, попадает ли A в B., просто переберите все точки A.p[i] и запомните самую внутреннюю точку, которая находится внутри B и ближайшая к B.pc (если их больше одной). Это предполагает, что ваша симуляция имеет достаточно малый временной шаг dt, поэтому интерполированные позиции не пропускают попаданий ... В противном случае необходимо использовать другой подход.

3. вычислить смещение d

   для этого нам нужно знать направление движения A относительно B. что можно вычислить так:

   dir = (A.pc-B.pc) - (A'.pc-B'.pc)
   

   где A'.pc,B'.pc - позиции с последней итерации ... Вот изображение в относительных термах (поскольку B будет стоять на месте):

   

   Теперь, чтобы вычислить смещение, просто нарисуйте луч из q с направлением -dir и проверьте, в какой треугольник B попал. Точка пересечения q' - это ваша хит-точка, которую вы ищете. Смещение:

    d = q'-q
   

   это то, что нужно перевести A, чтобы просто касаться B, а не пересекаться.

   Отсюда вы можете вычислить отражение r, поскольку треугольник попадания B имеет свою нормаль:

   

   так что теперь просто переведите A на r, чтобы ваш A имел положение после отражения (чтобы время не терялось во время удара) ... Также по размеру d и относительной скорости между A,B вы можете оценить время удара и добавить трение при ударе. уменьшив скорость и r. Не забудьте также отразить скорость A. Вы также можете сделать физику удара на B.

   q' и d также могут использоваться для создания вращающего момента на обоих A,B, однако моделирование трехмерных вращений очень сложно и обычно просто имитируется углами Эйлера ... Я понимаю, что твердое тело может иметь любое количество вращений, а не только 3. ... но некоторые из них объединяются или отменяются, поэтому для имитации этого потребуется динамический список задействованных вращений, которые было бы медленно и сложно реализовать поверх него.

Взгляни на:

• Столкновение конуса с прямоугольником

Вы можете найти мою реализацию point внутри convex_mesh теста и многое другое, даже _38 _... В более новой версии этого я реализовал еще больше примитивов и выпуклый_hull, но не могу опубликовать его, поскольку он увеличивается до 35 КБ, что передается 30 КБ предел уже.

Чтобы ускорить тестирование, вы также можете добавить описанную сферу к каждому convex_hull и проверить, пересекаются ли они, прежде чем тестировать сам convex_hull ... Вы знаете, что расстояние по перпендикуляру между линейными путями A, B должно быть меньше A.r+B.r ... превращаясь в простое проверка ближайшей точки линии / линии, которая также реализована по ссылке выше.