Пересекая разницу Минковского от источника в направлении, как мне найти лицо, которое я пересекаю?

Question

В основном у меня есть набор вершин на корпусе разности Минковского двух многогранников.Я хочу найти расстояние от источника до корпуса в каком-то произвольном заданном направлении.Вот быстрый 2D набросок:

Итак, проблема в том, чтобы найти, какую треугольную грань / плоскость будет пересекать луч.Как только у меня есть эта плоскость, я просто делаю тест пересечения линии / плоскости.Моя проблема - найти правильное лицо / плоскость.Есть идеи?Есть ли какой-нибудь набор тестов точечного продукта / перекрестного продукта / тройного продукта, который я могу сделать, чтобы определить это?Или это сложнее, чем это?

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

Answer 1

Проецируйте многогранник в направлении луча, и ваша задача уменьшится до 2D, и найдите, какой треугольник охватывает начало координат. Чтобы проверить один треугольник, подумайте, идет ли данный направленный отрезок (AB) по часовой стрелке или против часовой стрелки относительно начала координат. Это легко определить с помощью простого теста для нескольких продуктов: против часовой стрелки, если A x ( B - A )> 0.

Если все три стороны треугольника имеют одинаковый смысл (по часовой стрелке или против часовой стрелки), тогда треугольник охватывает начало координат, и это то лицо, которое вам нужно.

EDIT:
Поскольку ваш многогранник является оболочкой, он выпуклый, а поскольку он выпуклый, вы можете эффективно обыскивать поверхность. Вы можете пройтись по краям очень простым способом «идти в гору / вниз», чтобы найти две вершины, самые дальние вдоль луча в любом направлении. Затем, после того, как вы спроецируете poyhedron, вы можете начать с этих двух точек и сделать аналогичное восхождение к началу координат. Это будет O (sqrt (n)) .