Обработка столкновений с алгоритмом и реализацией

[@p53]

Алгоритм основан на теореме о разделяющей оси. Для 3D случая это разделяющая плоскость.
Определение будет такое: если между двумя фигурами существует плоскость (для 2D прямая), относительно которой фигуры лежат по разные стороны, то такие фигуры не пересекаются.

В теореме о разделяющей оси идёт речь про выпуклые фигуры. В статье это всплывает мельком в середине.

[@Allen]

А что если сталкивать тетраэдры их основаниями? Алгоритм сработает?
Ведь нормали все в разные стороны, а коллизия проекций будет хорошо видна только в одной плоскости.
Проекция в виде отрезка детектируется?

[@Nirvano]

Сработает, ведь мы строим проекции на плоскость, нормаль которой перпендикулярна нормали стороны. Смотрите на картинку с кубами, ситуация в принципе аналогичная.

[@Allen]

А как вы выбираете перпендикулярную плоскость? Ведь их там всё небо в попугаях бесконечное множество

[@Nirvano]

Беру первую попавшуюся. Я строю плоскость по нормали, а потом меняю направление Y и Z осей. (Z в данном случае нормаль плоскости)

    // Берем перпендикулярную плоскость.
    plane.swapZY();

[@Mrrl]

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

[@Nirvano]

Не могу себе представить случая когда фигуры пересекаются, и при этом не пересекают сторон. А если стороны пересекаются, то мы найдем пересечение.

[@Mrrl]

Возьмите два тетраэдра.
Вершины первого: (0,-1,-1), (0,1,-1), (-1,0,0), (1,0,0)
Вершины второго: (0,-1,0.1), (0,1,0.1), (-1,0,1.1), (1,0,1.1)
Они не пересекаются. Нормали к граням каждого из них (с точностью до коэффициента) — (0,1,1), (0,-1,1), (1,0,1), (-1,0,1).
Если я правильно понял ваш алгоритм выбора перпендикулярной плоскости, то для этих векторов он выдаст их же, но в другом порядке (опять же с точностью до коэффициента): (0,-1,1), (0,1,1), (-1,0,1), (1,0,1).
Можно проверить, что проекции тетраэдров на каждую из плоскостей, перпендикулярную одному из этих векторов, будут пересекаться.

[@p53]

Чтобы было понятно, я тут картинку нарисовал.

[@p53]

Я разобрался в авторском алгоритме выбора перпендкулярной плоскости.

// from Vector3.orthogonal
setFrom(-y, x, 0);

// from Plane.setFrom
zAxis.setFrom(normal); // = (x, y, z)
xAxis.setFrom(normal);
xAxis.orthogonal();    // = (-y, x, 0)

// from Plane.swapZY -- странное название
Vector3 temp = xAxis;
xAxis = zAxis;
zAxis = temp;          // = (-y, x, 0)

То есть почти всегда перпендикулярная плоскость выбирается с нормалью (-y, x, 0). Так что для приведённого примера всё хорошо, и я поспешил нарисовать к нему картинку. Но стоит повернуть тетраэдры неудачно, как проблема снова возникает.

[@Mrrl]

Да, я слишком поверил названию :(

[@Nirvano]

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

Метод, конечно, очень интересно называется)

[@mbait]

Не учтен случай, когда фигуры сталкиваются вершинами. Для этого в 2D к качестве разделяющей можно взять нормаль к прямой, проходящей через центры масс обеих фигур, в 3D — по тому же принципу.

[@Nirvano]

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

[@mbait]

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

[@Stas911]

Что будет с торами, продетыми один в другой?

[@Nirvano]

Алгоритм работает только с выпуклыми моделями. Тор к ним не относится. Что бы работать с не выпуклыми фигурами их можно разбивать на выпуклые.

[@p53]

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

Вообще, метод разделяющей оси в трёхмерном случае предполагает поиск оси, а не плоскости =) Если существует разделяющая плоскость, то проекция двух многогранников на нормаль к ней даст непересекающиеся отрезки (проверка непересечения в одномерном случае сильно проще). Количество претендентов на нормаль такой плоскости конечно: это нормали граней исходных многогранников + попарные векторные произведения сторон одного на сторону другого. Наконец, существуют эвристики, как найти эту нормаль эффективно.

[@Mrrl]

Количество претендентов на нормаль такой плоскости конечно: это нормали граней исходных многогранников + попарные векторные произведения сторон одного на сторону другого

Тогда уж ещё плюс векторы, соединяющие вершины разных многогранников… Хотя нет, там сложнее.

[@Mrrl]

Да, я неправ — граней и пар рёбер хватает.

[@Nirvano]

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

Вообще, метод разделяющей оси в трёхмерном случае предполагает поиск оси, а не плоскости =) Если существует разделяющая плоскость, то проекция двух многогранников на нормаль к ней даст непересекающиеся отрезки (проверка непересечения в одномерном случае сильно проще). Количество претендентов на нормаль такой плоскости конечно: это нормали граней исходных многогранников + попарные векторные произведения сторон одного на сторону другого. Наконец, существуют эвристики, как найти эту нормаль эффективно.

Как я понял вы предлагаете увеличить кол-во плоскостей на которых следует проверять пересечения (Решение проблемы с тетраэдрами). При этом отказаться от промежуточного действия — построения проекций на плоскость. Вместо этого строить проекции сразу на нормаль проверяемой плоскости.

Единственное не понял что значит попарные векторные произведения сторон одного на сторону другого.

Огромное спасибо за комментарии.

[@Mrrl]

Попарные векторные произведения — это когда берётся ребро одного многогранника, ребро другого, и строится прямая, перпендикулярная им обоим. Проверяются проекции на эту прямую. Повторить для всех пар рёбер.
Количество прямых, на которые идут проекции, окажется F1+F2+E1*E2, а общая сложность алгоритма — (F1+F2+E1*E2)*(V1+V2). Думаю, что это гораздо дешевле, чем возиться с двумерными проекциями.

[@p53]

Я неточно выразился. Если U и V – множество рёбер одного и второго многранников соответственно, то все произведения u×v, где u∈U, а v∈V. В примере с тетраэдрами, два наиболее близких ребра дадут плоскость, которая им параллельна и которая разделяет тетраэдры.

[@Mrrl]

В общем, грани суммы Минковского.

[@1vanK]

> Ищем проекции моделей на плоскость.

Разделяющая ось всегда одномерная (т.е. линия), даже для 3D, поэтому проецировать надо на линию, а не на плоскость en.wikipedia.org/wiki/Hyperplane_separation_theorem#Use_in_collision_detection