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

[maisvendoo]

Теорема сформулирована, а где доказательство?

[Ztare]

Понимаю что речь про универсальную формулу, но все же — для паралелепипедов разве нет более простой формулы рассчета коллизии без умножений и пересчетов проекций?
PS: Было бы интересно почитать про оптимизации позволяющие сравнивать меньше коллизий на сцене.

[slupoke]

По поводу собственной интерпретации согласен. Моей целью было рассказать о данной теореме с точки зрения применения ее для обнаружения столкновений реальных физических твердых тел, а не углубляясь глубоко в теорию. Мне кажется, что теорема у меня достаточно достоверно звучит в контексте твердых тел. Не могли бы, привести контрпример?

[Sdima1357]

Все проще.
1 При пересечении выпуклых многогранников — хотя бы одна из точек одного многогранника, внутри другого.
Для параллелепипедов
а. Принимаем первый параллелепипед за единичный куб в начале координат. Проверяем попадает ли какая либо вершина второго куба внутрь [01][01][01];
б. Меняем кубы местами. Повторяем.
Затраты: две инверсии матрицы, 16 умножений 3-вектора на матрицу.

[slupoke]

При пересечении выпуклых многогранников — хотя бы одна из точек одного многогранника, внутри другого

Это не единственное условие, при котором происходит пересечение. Пример.

[Sdima1357]

Хм, точно… И с пирамидами тоже. Впрочем можно добавить проверку пересечения граней ребрами, что тоже недорого(для кубов). Или проверить линию соединяющую центры тяжести на пересечение с гранями

[Sdima1357]

del

[Sdima1357]

Герман Минковски
«Separating Axis Theorem»
programmerart.weebly.com/separating-axis-theorem.html

[VaalKIA]

Хотья и прочёл по диагонали, но меня насторожили несколько моментов: «существет ось», подразумевает именно существование, а не ось праллельную координатным осям или граням/плоскостям объектов.
Соотвественно, для двумерного случая, мы должны условно «проверить» все проекции касательных к кругу, с бесконечно малым шагом. Для трёхмерного случая, надо будет делать это дважды: сначала плоскости к сфере, а потом касательные к кругу вокруг двумерной проекции.
Не увидел в 3 и 4 актах, почему бесконечности заменены на какие-то оси кандидаты их будет достаточно.

Как справляется ваш алгоритм с таким случаем?

[slupoke]

Совершенно верно, если объекты не пересекаются, то существует разделяющая ось. Ее нужно найти, и она не зависит от пространственных координат. В 1 акте сказано, в каких множествах ее можно найти:

Свойство. Потенциальная разделяющая ось будет находиться в следующих множествах:

• Нормы плоскостей каждого куба(красные)
• Векторное произведение ребер кубов {[x,y]: x∈X, y∈Y}

   где X — ребра первого куба (зеленые), а Y — второго (синие).

мы должны условно «проверить» все проекции касательных к кругу, с бесконечно малым шагом. Для трёхмерного случая, надо будет делать это дважды: сначала плоскости к сфере, а потом касательные к кругу вокруг двумерной проекции.

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

Не увидел в 3 и 4 актах, почему бесконечности заменены на какие-то оси кандидаты их будет достаточно.

О бесконечностях речь и не шла, оси кандидаты — это как раз те потенциальные разделяющие оси, которые мы нашли, и среди них существует(если объекты не пересекаются) сама разделяющая ось, проекции объектов на которую не пересекаются.

Как справляется ваш алгоритм с таким случаем?

Алгоритм мне не принадлежит, как и сама теорема, я лишь описал реализацию.
В данном примере разделяющая ось будет нормалью.

[VaalKIA]

Я понял идею: для выпуклых тел, если посмотреть вдоль каждой грани, то если тела не пересекаются, обязательно будет такой вид, что тела будут лежать по разные стороны. Собственно, это базовая математика для выпухлых тел, но вместо того, что бы работать в объёме вы упращаете до работы с проекциями, где вместо перебора всего и вся, можно использовать простые min, max. Но на мой взгляд, дважды проецировать будет более затратно, чем просто проверить лежат ли все вершины по другую сторону от плоскости проверяемой грани.
Либо же я вас не понял, и у вас по прежнему есть магичекий способ выбрать кандидатов, а не по количеству граней (почему бесконечное количество разделяемых осей можно сократить до количества граней тел я только что написал, чего нет в вашей статье).

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



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

[slupoke]

почему на иллюстрациях разделяющие оси не параллельны граням.

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

[VaalKIA]

Векторное произведение, это перпендикуляр к плоскости множимых векторов, то есть аналог нормали, только нормаль, она нормирована в еденицу.

А, так вы три вектора множите, а что мы делаем с огранённым шаром и какой геометрический смысл это несёт?

[slupoke]

Верно, но у нас векторное произведение [x,y], в котором X и Y разные множества(посмотрите внимательно).
Т.е. x — ребро первого куба, а y — второго

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

[VaalKIA]

Ещё 4 раза перечитал всю статью и я нашёл это:

Свойство. Потенциальная разделяющая ось будет находиться в следующих множествах:

Нормы плоскостей каждого куба(красные)
Векторное произведение ребер кубов,

где X — ребра первого куба (зеленые), а Y — второго (синие).

Не будем заострять внимание на том, что пункта два…

Вы серьёзно?! Да я выкинул весь этот обзац сразу как только понял, что это частный случай не имеющий никакого отношения к габаритным размерам (что могло бы помочь сократить количество кандидатов), либо к общей теории.
Даже не думал искать объяснение (в одно предложение на всю статью, Карл!) среди этой дичи для первоклашек:

Нормы плоскостей каждого куба(красные)
Векторное произведение ребер кубов
Координаты центра куба
Размеры куба (высота, ширина, глубина)
Кватернион куба

Для меня невероятно тяжело было объяснить как это работает

А вы и не объясняете.

Моей целью было поделиться своим опытом в решение задач связанных с определением пересечений двух выпуклых объектов. А так же доступно и понятно рассказать о данной теореме.

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

[slupoke]

Не будем заострять внимание на том, что пункта два…

Это причем?

Вы серьёзно?! Да я выкинул весь этот обзац сразу как только понял, что это частный случай не имеющий никакого отношения к габаритным размерам (что могло бы помочь сократить количество кандидатов), либо к общей теории.

Я с самого начало указал, что будут рассматриваться случай с кубами, но идея с более полигональными объектами будет сохранена. При работе с геометрическими примитивами и реализацией для них частные случаи, получается более оптимизированный код, если для каждого объекта применять общий метод.

Моё личное мнение: вы сделали всё, что бы увести читателя в сторону и не объяснить ничего, кроме того, что вы сами умете писать программы и делать какие-то вычисления: картинки ничего не имеющие с реальностью, нелепая терминология, куски кода вместо объяснений, какие-то частные примеры примитивнейших вещей до которых нельзя опускаться если говоришь о теории.

Здесь много теории? Статья была написано в практическом стиле, в начале я привел ссылку на википедию, где можно познакомиться с доказательствами теоремы и углубиться в теорию.

[VaalKIA]

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

В самом начале, вы указали, что будете рассказывать о: «Обнаружение столкновений и теорема о разделяющей оси», но раз речь только о кубах, то я снимаю всю конструктивную критику.