Обнаружение столкновений между двумя общими гексаэдрами

Question

У меня есть шесть шестигранных твердых тел. Единственная гарантия состоит в том, что каждый из них имеет 8 вершин3f (вершины с компонентами x, y и z). Учитывая это, как я могу узнать, сталкиваются ли они?

Answer 1

Кажется, я слишком тупой, чтобы уйти.

Рассмотрите это. Если любой край твердого тела 1 пересекает любую грань твердого тела 2, у вас есть столкновение. Это не совсем полно, потому что есть случай, когда один из них полностью содержится в другом, который вы можете проверить, определив, находится ли центр либо в другом.

---

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

1. Определить край как вектор, начиная с одной вершины, переходящей в другую. Обратите внимание на длину, L, края.
2. Определите плоские отрезки вершиной, нормальным, плоским основанием и положением оставшихся вершин в этом базисе.
3. Find the intersection of the line and the plane. В обычной формулировке вы сможете получить как длину вдоль линии, так и координаты плоскости пересечения в базе, которую вы выбрали.
4. Пересечение должно иметь длину [0,L] и должно лежать внутри фигуры в плоскости. Эта последняя часть немного сложнее, но имеет a well known general solution.

Это будет работать. Для красноречия я предпочитаю R..'s solution. Если вам нужна скорость ... ну, вам просто нужно попробовать их и посмотреть.

Answer 2

Предположим, что один из ваших гексаэдров H1 имеет вершины (x_1, y_1, z_1), (x_2, y_2, z_2), .... Найдите максимум и минимум в каждой координате: x_min = min(x_1, x_2, ...), x_max = max(x_1, x_2,...) и так далее. Сделайте то же самое для другого гексаэдра H2.

Если интервал [x_min(H1), x_max(H1)] и интервал [x_min(H2), x_max(H2)] не пересекаются (то есть, либо x_max(H1) < x_min(H2) или x_max(H2) < x_min(H1)), то шестигранники не может возможно столкнуться. Повторите это для координат y и z. Качественно это похоже на тень каждого гексаэдра на оси х. Если они не перекрываются, многогранники не могут столкнуться.

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

Метод грубой силы, чтобы проверить, пересекает ли край лицо ... Сначала вы найдете пересечение линии, определяемой ребром, с плоскостью, определяемой гранью (см., Например, wikipedia). Затем вы должны проверить, действительно ли эта точка находится на краю и на лице. Край легок - просто посмотрите, находятся ли координаты между координатами двух вершин, определяющих ребро. Лицо сложнее, особенно без каких-либо гарантий, что он выпуклый. В общем случае вам нужно будет просто увидеть, какая сторона полуплоскостей определяется каждым краем, на котором он включен. Если он находится на внутренней полуплоскости для всех, он находится внутри лица. У меня, к сожалению, нет времени на то, чтобы набирать все сейчас, но я уверен, что поисковая система может помочь вам там. Но, конечно, это все грубая сила, и может быть лучший способ. (И dmckee указывает на специальный случай, который это не обрабатывает)

Answer 3

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

Не обязательно является оптимальным, но, очевидно, правильно, основываясь на constructive solid geometry:

1. представляют собой два твердых частиц друг как пересечение 6 полупространствами. Заметим, что это зависит от выпуклости, но не более того, и распространяется на твердые тела с большей стороны. Моим предпочтительным представлением для полупространств является выбор точки на каждой поверхности (например, вершины) и вектора нормалей, направленного наружу, на эту поверхность.
2. Пересечение двух твердых тел путем обработки всех 12 полупространств в качестве определяющих полупространств для нового твердого тела. (Этот шаг является чисто концептуальным и может не включать какой-либо фактический код.)
3. Вычислить представление поверхности/края нового твердого тела и проверить, что он не пуст. Один из подходов к этому состоит в том, чтобы изначально заполнить ваше представление поверхности/края одной поверхностью для каждого из 12 полупространств с краями вне границ 2 твердых тел, а затем пересечь их ребра с каждым из оставшихся 11 полупространств.

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