2D Физика для игр - Separate Axis Theorem

Нашёл в интернете очень интересную подборку статей и кода, которая описывает написание физики для игр. Я подумал что было бы полезно перевести серию тех статей и портировать код на XNA. Как для себя, так и для интересующихся игровой физикой.

Первая статья будет посвящена Separete Axis Theorem ( теорема о разделяющей оси )- методу проверки столкновений между многоугольниками. Данный метод является наиболее быстрым на данный момент и используется повсеместно во всех 2D физических библиотеках.

Итак, задача: Нам даны два многугольника в виде массива координат вершин. Необходимо проверить их на пересечение.





Separeta Axis Theorem утверждает, что если два обьекта не пересекаются, то существует прямая которая разделяет эти обьекты, т.е. проекции на нормаль этой прямой не пересекаются.

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

Аналогично происходит с треугольниками, пятиугольниками и т.д.

На данном рисунке мы видим, что проекции на красную ось пересекаются, что не даёт нам возможности утверждать, что треугольники разделены. В то время выбрав в качестве оси нормаль одного из треугольников ( синяя ось) проекции не пересекаются, т.е. треугольники не пересекаются.


Таким образом алгоритм состоит из трёх частей:
1. Поиск оси, которая разделяет многоугольники. (фактически проверка каждой стороны многоугольников)
2. Получение проекций многоугольников на ось.
3. Проверка на пересечение интервалов.

public static bool Intersect(Polygon a, Polygon b)
        {
            //Если один из многоугольников пустой - то не пересекаются
            if (a == null || b == null)
                return false;

            //Вычисляем отступ между многоугольниками для приведения к центру координат
            Vector2 offset = a.Offset - b.Offset;

            //В данной переменной храним ось на которую будет проецировать
            Vector2 xAxis = Vector2.Zero ;

            //Проходим по всем сторонам первого многоугольника и используем их как ось
            for (int j = a.VertexCount-1,i=0; i < a.VertexCount;j=i,i++)
            {
                //Вычисляем вектор стороны многоугольника
                Vector2 E = Vector2.Subtract(a[j], a[i]);
                //Вычисляем вектор нормали к стороне многоугольника
                xAxis = new Vector2(-E.Y, E.X); 

                //Если проекции многоугольников не пересекаются - то по теореме многоугольники не пересекаются
                if (!IntervalIntersect(a, b, xAxis, offset))
                    return false;
            }

            //Если пока не нашли нужной оси - проходим по всем сторонам второго многоугольника
            for (int j = b.VertexCount - 1, i = 0; i < b.VertexCount; j = i, i++)
            {
                //Вычисляем вектор стороны и нормаль
                Vector2 E = Vector2.Subtract(b[j], b[i]);
                xAxis = new Vector2(-E.Y, E.X); //Getting normal vector

                //И проверяем на пересечение проекций
                if (!IntervalIntersect(a, b, xAxis, offset))
                    return false;
            }

            //Если ни одна из осей не нашла не пересекающихся проекций, то очевидно по теореме
            //многоугольники пересекаются - возвращаем тру.
            return true;
        }

Код функций нахождения проэкции и пересечения интервалов:

/// <summary>
        /// Проверяет на пересечение проекций многоугольников
        /// </summary>
        /// <param name="a">Первый многоугольник</param>
        /// <param name="b">Второй многоугольник</param>
        /// <param name="xAxis">Ось проекции</param>
        /// <param name="offset">Отступ</param>
        /// <returns></returns>
        private static bool IntervalIntersect(Polygon a, Polygon b, Vector2 xAxis, Vector2 offset)
        {
            float min0, max0, min1, max1; //проекции на ось первого и второго многоугольника
            GetInterval(a, xAxis, out min0, out max0);

//получаем первую проекцию
            GetInterval(b, xAxis, out min1, out max1);
//получаем вторую проекцию

            float h = Vector2.Dot(offset, xAxis); //получаем проекцию отступа 
            min0 += h; max0 += h; // и добавляем её к первому многоугольнику

            float d0 = min0 - max1; 
            float d1 = min1 - max0;

            //если проекции не пересекаются то минимум первого больше максимума второго или
            //минимум второго больше максимума первого.
            if (d0 > 0.0f || d1 > 0.0f)
                return false;
            else return true;
        }

        /// <summary>
        /// Получает проекцию на ось
        /// </summary>
        /// <param name="a">Многоугольник</param>
        /// <param name="xAxis">Ось</param>
        /// <param name="min0">Начало проекции</param>
        /// <param name="max0">Конец проекции</param>
        private static void GetInterval(Polygon a, Vector2 xAxis, out float min0, out float max0)
        {
            min0 = max0 = Vector2.Dot(a[0],xAxis);
            //Проходимся по всем вершинам и проецируем их на ось
            for (int i = 1; i < a.VertexCount; i++)
            {
                //проецируем вершину на ось
                float dot = Vector2.Dot(a[i], xAxis); 
                //Устанавливаем минимум и максимум
                if (dot < min0)
                    min0 = dot;
                else if (dot > max0)
                    max0 = dot;
            }
        }

Полные исходные коды можно скачать здесь:

https://sites.google.com/site/jackdevolpment/files/physicsTutorial.7z?attredirects=0&d=1

или здесь

https://docs.google.com/leaf?id=0B6h7yaggRA4pNDg1M2Y1ODUtNDYyMC00Yjg2LTlhMWUtMWNlYWNlYTFlNjJl&hl=en

Ссылки на другие ресурсы по SAT:

http://www.metanetsoftware.com/technique/tutorialA.html

http://www.sevenson.com.au/actionscript/sat/

http://www.gamedev.ru/code/terms/SAT

http://noregret.org/tutor/n/collision/