Трехмерное обнаружение столкновений: выпуклый корпус против выпуклого корпуса, нужно положение и нормальное

Я хочу знать приблизительную трехмерную позицию и трехмерную нормаль места столкновения между двумя трехмерными выпуклыми оболочками (A против B).

Процессор в скобках показывает относительное время процессора, необходимое в моей готовой программе.

Часть 1: Ранний выход (CPU 1%)

На первом этапе я использую очень дешевый алгоритм - теорема об отделении.
Например, я использую 15 осей для 2 кубов. (В реальных случаях формы являются более сложными.)
Если существует хотя бы одна ось, которая может разделяться, return "no-collide".
В противном случае сделайте следующую часть.

Часть 2: вершина против объема (процессор 10%)

Проверьте каждую вершину A - находится ли она внутри B
Проверьте каждую вершину B - находится ли она внутри A

Часть 3: Край против Края (ЦП> 20%)

Есть странный случай, например, https://gamedev.stackexchange.com/info/75437/collision-detection-3d-rectangles-using-sat. Я украл изображение оттуда: -

Таким образом, мне также нужен край против края.

Для каждой пары ребер A & B (12 * 12 = 144 пар) найдите ближайшую точку на ребре A напротив ребра B Проверьте, находится ли вершина внутри B
(наоборот) Для каждой пары ребер B & A проверьте, находится ли такая вершина внутри A

Вау, это много вычислений.
Однако это еще не конец.

проблема

Сообщаемая позиция столкновения не так точна (слева: текущее, справа: желание): -

Чтобы решить эту проблему, я подумал о создании новой выпуклой формы = A intersect B
Существует несколько бесплатных библиотек C++ (например, OpenMesh), но я думаю, что это слишком дорого для процессора.
Обратите внимание, что мне не нужно, чтобы это было точно правильно.
Он также иногда сообщает, что неправильно нормально (слева: текущее, справа: желание): -

^ Эта проблема может быть решена путем добавления проверки ребра (A) и грани (B), но это сделает обнаружение всех столкновений еще более дорогим.

Вопрос

Похоже, что распространенные алгоритмы в интернете (из которых я копирую) распознают только микрофункцию.
ИМХО, алгоритм вершин-объем/ребро-кромка фокусируется на топологии, а не на том факте, что обе фигуры являются сплошными объемами.

Какой алгоритм является более точным (1-й приоритет) и, возможно, дешевле?
Мой подход может быть неправильным на уровне фундамента.

Чтобы ускорить процесс, я уже провел некоторое сокращение, например, выбрал только пару ребер A и B, которые расположены близко друг к другу.

Рекомендации :-

Алгоритмы обнаружения столкновений между выпуклыми полигонами произвольного размера проверяют только наличие столкновения.
https://pybullet.org/Bullet/BulletFull/btBoxBoxDetector_8cpp_source.html: вдохновляющий полный код обнаружения коробок и коробок в библиотеке Bullet Physics - это трудно понять.
https://math.stackexchange.com/info/397413/determine-direction-of-minimum-overlap-of-convex-polygons Математический вопрос без ответа, который очень похож на этот.

Изменить (10 дней спустя)

Теперь я могу найти все пересекающиеся выпуклые точки (выпуклые изображены в виде розового треугольника/прямоугольника): -

Вот как я нахожу нормальное.

Для каждой разделяющей оси (все = 15 осей) я проецирую выпуклый розовый цвет на ось.
Ось, которая дает кратчайший диапазон проекционных расстояний, должна быть направлением нормали.

Мое вышеупомянутое предположение часто верно (например, слева), но иногда неправильно (например, справа).
Как улучшить это CPU-дешево?

Ответ 1

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

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

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

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

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

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

Если время = предыдущее, предположим, что А и В не соприкасаются.

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

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

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

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

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

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

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

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