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

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

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

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

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

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

находим проекции обоих выпуклых объектов на всех "кандидатов"

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

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

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

#collision detection, #SAT

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

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

Mega
Постоялец

#1
11:53, 11 июня 2009

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

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

Chipmunk
Постоялец

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

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

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

Suslik
Модератор

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

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

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