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

Question

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

Answer 1

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

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

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

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

Answer 2

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

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

---

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

1. Определить ребро как вектор, начиная с одной вершины, идущей к другой.Обратите внимание на длину L края.
2. Определите отрезки плоскости с помощью вершины, нормали, базиса в плоскости и положения остальных вершин в этом базисе.
3. Найдите пересечение прямой и плоскости .В обычной формулировке вы сможете получить как длину вдоль линии, так и координаты в плоскости пересечения на основе, которую вы выбрали .
4. Пересечение должно быть прямойкак длина [0,L], и должна лежать внутри фигуры в плоскости.Эта последняя часть немного сложнее, но имеет хорошо известное общее решение .

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

Answer 3

Предположим, у одного из ваших шестигранников 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. Качественно это все равно, что смотреть на тень каждого шестигранника на оси абсцисс. Если они не перекрываются, многогранники не могут сталкиваться.

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

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