Непрерывное обнаружение столкновений в 3D для двух выпуклых многогранников

Question

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

1. Входные данные: выпуклый многогранник, определенный как набор точек одного объекта A и направление его движения.
2. Входные данные: выпуклый многогранник, определенный как наборточки второго объекта B
3. Рассчитать сумму Минковского двух наборов точек C, |C| = |A| * |B|
4. Рассчитать триангулированную выпуклую оболочку C (используя QuickHull)
5. Пересечение линии с треугольниками выпуклой оболочки и сохранение минимального и максимального расстояния вдоль линии.

Это все работает, но медленно.Особенно шаг для вычисления триангулированной выпуклой оболочки.

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

Answer 1

Решено по теореме оси разделения:

1. Входные данные: выпуклые объемы столкновений как уравнения точек и плоскостей
2. Для каждой плоскости в обоих объемах столкновений рассчитайте shift вдоль движениянаправление, когда каждая плоскость становится плоскостью разделения (все вершины другого объема столкновения находятся перед плоскостью).
3. Рассчитать интервал shift, когда плоскости разделения не существует.Это можно сделать на месте, отслеживая минимальные и максимальные значения.

По сравнению с исходным решением:

• Теоретическая сложность снижена с O(N log N) до O(N), где N = |C| = |A| * |B|
• Работает на месте - без выделения памяти