Войти
ПрограммированиеТермины

Separating Axis Theorem (Теорема о разделяющей оси)

На основе теоремы о разделяющих осях построено большинство алгоритмов, используемых в Narrowphase, позволяющих не только определить, пересекаются ли два тела(выпуклые геометрии), но и найти нормаль и глубину проникновения.

Separating Axis Theorem для двух выпуклых объектов можно сформулировать так: два выпуклых объекта пересекаются тогда и только тогда, когда существует плоскость(для двумерного случая - прямая), такая, что одна геометрия лежит по одну ей сторону, а другая - по другую.

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

То есть алгоритм для определения глубины и направления пересечения двух выпуклых объектов можно сформулировать так:

  • составляем список "потенциальных" разделяющих осей, состоящий из нормалей всех треугольников, и векторным произведением всех рёбер
  • находим проекции обоих выпуклых объектов на всех "кандидатов"
  • находим ту ось, на которой проекции пересекаются по наименьшему отрезку(если есть ось, на которой проекции не пересекаются вообще, то и геометрии не пересекаются)
  • направление разделяющей оси есть направление проникновения, а длина отрезка пересечения проекций есть глубина.
  • Что такое Separating Axis Theorem (Теорема о разделяющей оси)?

    #collision detection, #SAT

    9 февраля 2008 (Обновление: 24 сен 2014)

    Комментарии [21]

    Страницы: 1 2 Следующая »
    #1
    11:53, 11 июня 2009

    >Separating Axis Theorem для двух выпуклых объектов можно сформулировать так: два выпуклых объекта пересекаются тогда и только тогда, когда существует плоскость(для двумерного случая - прямая), такая, что одна геометрия лежит по одну ей сторону, а другая - по другую.

    есть мнение, что это неверно. прямая х=0 разеляет два круга радиусами 1, лежащих на оси х на расстоянии 3 от начала координат. при этом, очевидно, эти круги не пересекаются.

    #2
    13:31, 11 июня 2009

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

    Равносильно существованию плоскости (прямой), которая разделяет объекты.

    #3
    4:44, 18 июня 2009

    Спасибо, исправил.

    Прошло более 14 лет
    #4
    6:06, 16 сен 2023

    Для двух непересекающихся отрезков, лежащих на одной прямой на плоскости, это неверно, потенциальная разделяющая ось одна - нормаль к прямой, но проекции на нее совпадают - одна точка

    #5
    (Правка: 9:26) 9:23, 16 сен 2023

    1Man1

    для двух выпуклых объектов

    > Для двух непересекающихся отрезков
    найди отличия. И да для двух не пересекающихся отрезков существует такая плоскость/прямая проекция на которую даст не пересекающие отрезки. С чего ты решил что если существует такая плоскость/прямая на которой проекции пересекаются, то не существует обратной?

    #6
    (Правка: 17:33) 17:24, 16 сен 2023

    Aroch
    > найди отличия
    Отрезок выпуклый по определению, к твоему сведению

    > для двух не пересекающихся отрезков существует такая плоскость/прямая проекция на которую даст не пересекающие отрезки
    Ясное дело. Речь о том, что во всех туториалах предлагают в качестве разделяющих осей проверять только нормали к граням для 2D

    > С чего ты решил что если существует такая плоскость/прямая на которой проекции пересекаются, то не существует обратной?
    Для пересекающихся обьектов такой прямой не существует

    #7
    (Правка: 8:51) 8:46, 17 сен 2023

    1Man1
    > Отрезок выпуклый по определению, к твоему сведению
    в контексте статьи он не является выпуклым объектом, к стандартному определению о отсутствии внутренних пересечений отрезков для любых комбинаций с вершинами, нужно добавлять способность задать объект строго определенным конечным количеством плоскостей/прямых. И очевидно что ни точки, ни отрезки, ни круги, сферы и подобные объекты не имеет смысла рассматривать в общем случае и поиск подходящей плоскости/прямой может быть затратней чем альтернативные решения. Для отрезков таких прямых не так и много кстати, сами отрезки и их нормали. Но частное решение для отрезков скорее всего будет быстрее.
    > Ясное дело. Речь о том, что во всех туториалах предлагают в качестве
    > разделяющих осей проверять только нормали к граням для 2D
    потому что их конечное количество.
    > Для пересекающихся обьектов такой прямой не существует
    а для не пересекающихся существует, и твоё утверждение что:

    Для двух непересекающихся отрезков, лежащих на одной прямой на плоскости, это неверно

    ложно.

    #8
    9:13, 17 сен 2023

    Суслик вернись.

    #9
    (Правка: 16:47) 16:18, 17 сен 2023

    Aroch
    > к стандартному определению о отсутствии внутренних пересечений отрезков для любых комбинаций с вершинами, нужно добавлять способность задать объект строго определенным конечным количеством плоскостей/прямых
    Теорема Минковского о разделяющей оси сформулированна для любых выпуклых фигур.
    Выпуклый многоугольник же можно представить как пересечение наборов полуплоскостей, заданных ур-ями (p,n)<=d, к отрезку это также относится

    > потому что их конечное количество
    Глупости, надо проверить все оси, которые могут быть разделяющими

    > ложно
    Истинно, единственная нормаль не является разделяющей осью
    А ты не соображаешь в геометрии и читаешь плохо

    #10
    2:04, 18 сен 2023

    1Man1
    > Теорема Минковского о разделяющей оси сформулированна для любых выпуклых фигур.
    и я тебе уже объяснил что в практическом смысле она проигрывает специальным решениям для ряда фигур для которых количество ограничивающих плоскостей может быть бесконечное количество.
    > к отрезку это также относится
    вот и задай его этими плоскостями а не единственной нормалью, если ты еще не осознал что нормаль не задает отрезок.
    > Глупости, надо проверить все оси, которые могут быть разделяющими
    давай проверяй для сферы все оси, желаю удачи с этим.
    > Истинно, единственная нормаль не является разделяющей осью
    причем тут единственная нормаль? У отрезков нормалей две (вторая с противоположным знаком), а разделяющих осей и того больше.
    > А ты не соображаешь в геометрии и читаешь плохо
    предлагаю тебе это повторить стоя перед зеркалом.

    + Показать
    #11
    19:06, 18 сен 2023

    Aroch
    > и я тебе уже объяснил что в практическом смысле она проигрывает специальным решениям для ряда фигур
    Нифига ты не "обьяснил", не ври, сам ничего не знаешь, а туда же лезешь. Я привел отрезки, как контпример к теореме, вроде понятно написал, но обязательно найдется нечитатель, пытающийся прицепиться к словам

    > вот и задай его этими плоскостями
    Полуплоскостями, неуч, - легко:
    Система
    (p,n)<=d
    (p,-n)<=-d
    задает прямую, добавив еще 2 полуплоскости с прямыми, проходящими через концы, - получим отрезок.
    Также можно взять узкий треугольник, устремив его толщину к 0, в пределе получим отрезок, нормали сторон стремятся к нормали к отрезку

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

    > У отрезков нормалей две
    Лол, две противоположных вектора задают одну и ту же прямую

    > предлагаю тебе это повторить стоя перед зеркалом.
    Иди подмойся, гомонитарий

    #12
    22:19, 18 сен 2023

    1Man1
    > добавив еще 2 полуплоскости с прямыми, проходящими через концы, - получим отрезок
    Вот нормали к этим полуплоскостям и будут разделяющими осями.
    Т. е. для объектов, заданных как пересечение полуплоскостей, теорема работает.

    > для этого надо перебрать все возможные кандидаты.
    Тебя =A=L=X= покусал? Перебрать бесконечное количество объектов невозможно, логика так не работает.
    В математике все доказательства содержат исключительно конечное количество шагов.

    #13
    (Правка: 8:39) 8:32, 19 сен 2023

    }:+()___ [Smile]
    > Перебрать бесконечное количество объектов невозможно
    От тебя не ждал таких заявлений. Прикажешь отменить интегрирование, дифференцирование, счисление рядов и пределов, мат индукцию, в общем всю математику?
    Мда, походу после ухода Суслика форум глупеет 😂

    > Вот нормали к этим полуплоскостям и будут разделяющими осями
    А я думаю, что нет, можно построить пример и для многоугольников ненулевой площади.
    Я шел с другой стороны - ближайшими двумя точками двух многоугольников могут быть:
    1. Вершина и основание перпендикуляра из нее на сторону другого многоуг - тогда разделяющая ось = нормаль
    2. Две вершины - в этом случае разделяющая ось - например перпендикуляр к линии между ними, и причем тут тогда нормали? В инете программистишки копируют друг у друга бездоказательную лажу

    #14
    10:42, 19 сен 2023

    1Man1
    > задает прямую, добавив еще 2 полуплоскости с прямыми, проходящими через концы,
    > - получим отрезок.
    ну и почему ты их не используешь? И что тебе не понятно на моем рисунке? О чем ты еще споришь? Как в такой ситуации можно продолжать спорить, когда тебя тыкают носом что вот <censored> смотри сюда, видишь проекции не пересекаются?

    + Показать
    Страницы: 1 2 Следующая »
    ПрограммированиеТермины