2D Физика для игр - Separate Axis Theorem - Вектор сдвига

Как и обещал продолжаю перевод серии статей про игровую физику. Сегодня я напишу как получить вектор сдвига и разьединить 2 столкнувшихся многоугольника.


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


Итак, дано: 2 столкнувшихся многоугольника
Задача: Разьединить 2 многоугольника, причём минимальным сдвигом.


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




Для решения данной задачи может быть применён описанный ранее метод, только немного доработанный. Мы будем возвращать глубину проникновения и вектор, указывающий в какую сторону следует сдвинуть полигоны, чтобы они перестали пересекаться. Подобная комбинация называется MTD ( Minimum Translation Distance ), или минимальное расстояние сдвига.

Вычислять MTD можно в процессе вычисления отделяющей оси.

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

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

Получив вектор сдвига мы можем легко отделить 2 обьекта:

A.position+=MTD*0.5f;
B.position-=MTD*0.5f;

Код проверки пересечения с нахождением MTD:

/// <summary>
        /// Проверяет на пересечение 2-х полигонов
        /// </summary>
        /// <param name="a">Первый многоугольник</param>
        /// <param name="b">Второй многоугольник</param>
        /// <returns></returns>
        public static bool Intersect(Polygon a, Polygon b,out Vector2 pushV)
        {
            pushV = Vector2.Zero;
            //Если один из многоугольников пустой - то не пересекаются
            if (a == null || b == null)
                return false;

            Vector2 pushAxis=Vector2.Zero;
            float mindepth = float.MaxValue;

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

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

            //Проходим по всем сторонам первого многоугольника и используем их как ось
            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, ref xAxis, offset, out depth))
                    return false;
                else
                {
                    //Находим ось по которой будем брать ось сдвига как ось минимального сдвига
                    if (depth < mindepth)
                    {
                        pushAxis = xAxis;
                        mindepth = depth;
                    }
                }
            }

            //Если пока не нашли нужной оси - проходим по всем сторонам второго многоугольника
            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, ref xAxis, offset, out depth))
                    return false;
                else
                {
                        //Ищем ось сдвига
                        if (depth < mindepth)
                        {
                            pushAxis = xAxis;
                            mindepth = depth;
                        }
                }
            }

            //Вычисляем вектор сдвига
            pushV = pushAxis;
            mindepth /= pushV.Length();

            //Нормируем вектор сдвига и умножаем на длину пересечения
            pushV.Normalize();
            pushV *= (mindepth*1.01f);

            //Если вектор сдвига указывает в неправильно направлении - отражаем его
            if (Vector2.Dot(pushV, offset) < 0)
                pushV = Vector2.Negate(pushV);

            //Если ни одна из осей не нашла не пересекающихся проекций, то очевидно по теореме
            //многоугольники пересекаются - возвращаем тру.
            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,ref Vector2 xAxis, Vector2 offset,out float depth)
        {
            depth = 0;
            
            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 || d1 > 0)
                return false;
            else
            {
                depth = Math.Min(Math.Abs(d0), Math.Abs(d1));
                Trace.WriteLine(depth);
                return true;
            }
        }

Исходные файлы:

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