Программирование игр, создание игрового движка, OpenGL, DirectX, физика, форум
GameDev.ru / Программирование / Термины / Separating Axis Theorem (Теорема о разделяющей оси)

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

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

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

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

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

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

    9 февраля 2008

    #collision detection, #SAT


    Обновление: 24 сентября 2014

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

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

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

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

    SuslikМодераторwww18 июня 20094:44#3
    Спасибо, исправил.

    / Форум / Программирование игр

    Тема в архиве.

    2001—2018 © GameDev.ru — Разработка игр