Комментарии 25
Алгоритм основан на теореме о разделяющей оси. Для 3D случая это разделяющая плоскость.
Определение будет такое: если между двумя фигурами существует плоскость (для 2D прямая), относительно которой фигуры лежат по разные стороны, то такие фигуры не пересекаются.
В теореме о разделяющей оси идёт речь про выпуклые фигуры. В статье это всплывает мельком в середине.
А что если сталкивать тетраэдры их основаниями? Алгоритм сработает?
Ведь нормали все в разные стороны, а коллизия проекций будет хорошо видна только в одной плоскости.
Проекция в виде отрезка детектируется?
Ведь нормали все в разные стороны, а коллизия проекций будет хорошо видна только в одной плоскости.
Проекция в виде отрезка детектируется?
Сработает, ведь мы строим проекции на плоскость, нормаль которой перпендикулярна нормали стороны. Смотрите на картинку с кубами, ситуация в принципе аналогичная.
А как вы выбираете перпендикулярную плоскость? Ведь их там всё небо в попугаях бесконечное множество
Беру первую попавшуюся. Я строю плоскость по нормали, а потом меняю направление Y и Z осей. (Z в данном случае нормаль плоскости)
// Берем перпендикулярную плоскость.
plane.swapZY();
Тогда для двух тетраэдров, сталкивающихся серединами рёбер, вы можете не найти нужной плоскости. Там удачных плоскостей (перпендикулярных как единственной разделяющей плоскости, так и какой-нибудь грани тетраэдра) всего 8.
Не могу себе представить случая когда фигуры пересекаются, и при этом не пересекают сторон. А если стороны пересекаются, то мы найдем пересечение.
Возьмите два тетраэдра.
Вершины первого: (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).
Можно проверить, что проекции тетраэдров на каждую из плоскостей, перпендикулярную одному из этих векторов, будут пересекаться.
Вершины первого: (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).
Можно проверить, что проекции тетраэдров на каждую из плоскостей, перпендикулярную одному из этих векторов, будут пересекаться.
Чтобы было понятно, я тут картинку нарисовал.
Я разобрался в авторском алгоритме выбора перпендкулярной плоскости.
То есть почти всегда перпендикулярная плоскость выбирается с нормалью (-y, x, 0). Так что для приведённого примера всё хорошо, и я поспешил нарисовать к нему картинку. Но стоит повернуть тетраэдры неудачно, как проблема снова возникает.
// 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). Так что для приведённого примера всё хорошо, и я поспешил нарисовать к нему картинку. Но стоит повернуть тетраэдры неудачно, как проблема снова возникает.
Не учтен случай, когда фигуры сталкиваются вершинами. Для этого в 2D к качестве разделяющей можно взять нормаль к прямой, проходящей через центры масс обеих фигур, в 3D — по тому же принципу.
Что будет с торами, продетыми один в другой?
Также не до конца понятно зачем нужен поиск минимальной оболочки, если изначально теорема справедлива для выпуклых тел, а любая проекция (как и сечение) выпуклого тела всегда выпукла.
Вообще, метод разделяющей оси в трёхмерном случае предполагает поиск оси, а не плоскости =) Если существует разделяющая плоскость, то проекция двух многогранников на нормаль к ней даст непересекающиеся отрезки (проверка непересечения в одномерном случае сильно проще). Количество претендентов на нормаль такой плоскости конечно: это нормали граней исходных многогранников + попарные векторные произведения сторон одного на сторону другого. Наконец, существуют эвристики, как найти эту нормаль эффективно.
Вообще, метод разделяющей оси в трёхмерном случае предполагает поиск оси, а не плоскости =) Если существует разделяющая плоскость, то проекция двух многогранников на нормаль к ней даст непересекающиеся отрезки (проверка непересечения в одномерном случае сильно проще). Количество претендентов на нормаль такой плоскости конечно: это нормали граней исходных многогранников + попарные векторные произведения сторон одного на сторону другого. Наконец, существуют эвристики, как найти эту нормаль эффективно.
Количество претендентов на нормаль такой плоскости конечно: это нормали граней исходных многогранников + попарные векторные произведения сторон одного на сторону другого
Тогда уж ещё плюс векторы, соединяющие вершины разных многогранников… Хотя нет, там сложнее.
Минимальная оболочка нужна была что бы найти правильные нормали сторон проекций многогранников. Далее которые я использую для проверки проекций на пересечение. Так как после поиска проекции (не МВО) я получаю какой то набор точек, и глядя на него непонятно как искать разделяющую ось.
Как я понял вы предлагаете увеличить кол-во плоскостей на которых следует проверять пересечения (Решение проблемы с тетраэдрами). При этом отказаться от промежуточного действия — построения проекций на плоскость. Вместо этого строить проекции сразу на нормаль проверяемой плоскости.
Единственное не понял что значит попарные векторные произведения сторон одного на сторону другого.
Огромное спасибо за комментарии.
Вообще, метод разделяющей оси в трёхмерном случае предполагает поиск оси, а не плоскости =) Если существует разделяющая плоскость, то проекция двух многогранников на нормаль к ней даст непересекающиеся отрезки (проверка непересечения в одномерном случае сильно проще). Количество претендентов на нормаль такой плоскости конечно: это нормали граней исходных многогранников + попарные векторные произведения сторон одного на сторону другого. Наконец, существуют эвристики, как найти эту нормаль эффективно.
Как я понял вы предлагаете увеличить кол-во плоскостей на которых следует проверять пересечения (Решение проблемы с тетраэдрами). При этом отказаться от промежуточного действия — построения проекций на плоскость. Вместо этого строить проекции сразу на нормаль проверяемой плоскости.
Единственное не понял что значит попарные векторные произведения сторон одного на сторону другого.
Огромное спасибо за комментарии.
Попарные векторные произведения — это когда берётся ребро одного многогранника, ребро другого, и строится прямая, перпендикулярная им обоим. Проверяются проекции на эту прямую. Повторить для всех пар рёбер.
Количество прямых, на которые идут проекции, окажется F1+F2+E1*E2, а общая сложность алгоритма — (F1+F2+E1*E2)*(V1+V2). Думаю, что это гораздо дешевле, чем возиться с двумерными проекциями.
Количество прямых, на которые идут проекции, окажется F1+F2+E1*E2, а общая сложность алгоритма — (F1+F2+E1*E2)*(V1+V2). Думаю, что это гораздо дешевле, чем возиться с двумерными проекциями.
Я неточно выразился. Если U и V – множество рёбер одного и второго многранников соответственно, то все произведения u×v, где u∈U, а v∈V. В примере с тетраэдрами, два наиболее близких ребра дадут плоскость, которая им параллельна и которая разделяет тетраэдры.
> Ищем проекции моделей на плоскость.
Разделяющая ось всегда одномерная (т.е. линия), даже для 3D, поэтому проецировать надо на линию, а не на плоскость en.wikipedia.org/wiki/Hyperplane_separation_theorem#Use_in_collision_detection
Разделяющая ось всегда одномерная (т.е. линия), даже для 3D, поэтому проецировать надо на линию, а не на плоскость en.wikipedia.org/wiki/Hyperplane_separation_theorem#Use_in_collision_detection
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Обработка столкновений с алгоритмом и реализацией