понедельник, 14 марта 2011 г.

Барицентрическая система

     Вот копия одной моей старенькой статьи, по игровой физике, точнее по геометрии. Эта версия немного переделана. В статье используются примеры на C# с использованием классов XNA: Vector2, Vector3, Vector4  и Matrix.

     Если перед нами стоит задача рассчитать движение тела, то сперва мы должны задать вопрос о размерах тела, т.к. многие задачи решаются очень просто, благодаря лишь тому, что мы можем не учитывать размер тел в силу его малости. Иначе решение может оказаться крайне сложным. Если в задаче размер тела можно не учитывать, то мы должны воспользоваться этой прекрасной возможность.
     В игре мы можем пренебрегать размерами так называемых "частиц". Частицы - это много малюсеньких обычно треугольников которые имитируют частицы пыли, дыма, огня, брызг и.т.п. издалека группа таких частиц может выглядеть соответственно как облако пыли, клубы дыма, всполохи огня, брызги... Существует целая наука о том как создавать такие эффекты.
     Геометрически мы можем рассматривать отдельные частицы как точки (материальные точки). Материальные точки отличаются от обычных точек тем, что они тела. Так обычная точка может быть просто местом сбора юнитов на карте RTS, или временным вектором хранящим координаты пересечения некоторых линий. А материальная точка - это уже материальная вещь.(Хотя сам игровой мир не очень то материален, но я не буду развозить философию на эту тему). В большинстве случаев материальная точка должна инкапсулировать в себя помимо координат ещё массу и скорость. Так если масса это количество вещества, то в случае материальной точки всё вещество сосредоточенно в этой точке.
     В итоге мы можем рассматривать тело в виде материальной точки лишь в некоторых задачах. Но может так получится, что сложную задачу возможно разбить на несколько мелких задач, некоторые из которых решаются без учёта размера тела. Тогда нам полезно будет представлять тело то в виде материальной точки, а то в виде какой-то формы.
     Представьте как резиновая точка ударяется об стену и отскакивает обратно, а теперь представьте как резиновый мячик ударяется об стену. Будет ли разница? В принципе они будут двигаться одинаково. Но если мы просто возьмём шарик и забудем про его размеры, то он будет сталкиваться как точка, а его поверхность зачастую будет проходить сквозь стены. Эту проблему можно решить если разбить задачу на три

1) Расчёт движения мячика
2) Обнаружение столкновения мячика со стенами
3) Расчёт взаимодействия мячика со стеной

     Заметим что только во втором пункте нам нужно учитывать размер и форму мячика, а в первом и третьем мы можем считать его материальной точкой. Значит полезно всегда иметь ввиду две модели тела одновременно. Остаётся только вопрос: "где нам нужно выбрать такую точку для тела?" Очевидно что в центре тела!
     Это не совсем так. Когда мы захотим учесть вращение тела, могут появится проблемы, если мы не правильно её выберем. Я говорил ранее, что в материальной точке сосредоточенна вся масса тела. Поэтому для тела мы должны выбирать такую точку, в которой эквивалентно поместилась бы вся масса. Короче такой точкой является центр масс или центр тяжести*. Как рассчитать центр тяжести?
     Возьмём некоторое большое тело и мысленно разрежем его на мелкие части, например молекулы. Каждую молекулу в силу малости можем считать материальной точкой. Рассмотрим две молекулы. Пусть положение молекулы <1> определяется вектором V1, а молекулы <2> вектором V2. Тогда вектор центра тяжести для этих двух молекул считается по формуле:

Center = (V1 + V2 ) / 2;


     Т.е. это как раз середина между ними. Но если молекулы обладают разными массами M1 и M2, то центр тяжести должен находится чуть ближе к более тяжёлой молекуле и считается по формуле с учётом массы:

Center = (V1 * M1 + V2 * M2) / (M1 + M2);

     Теперь мы можем рассматривать эти две молекулы как материальную точку с массой MC = M1 + M2 и вектором положения Center. Если взять ещё молекулу <3> с массой M3 и вектором положения V3. Тогда центр для молекулы и материальной точке двух молекул.

Center2 = (Center * MC + V3 * M3) / (MC + M3);

     Это по сути центр масс для всех трёх молекул. Если подставить в эту формулу формулу расчёта вектора Center и массы M3, то получим:

Center2 = (V1 * M1 + V2 * M2 + V3 * M3) / (M1 + M2 + M3);

     Продолжая рассуждения аналогичным образом мы приходим к общей формуле:

MainCenter = (V1 * M1 + V2 * M2 + V3 * M3 + V4 * M4 + ....) / (M1 + M2 + M3 + M4...);

     Эта формула позволяет легко посчитать положение центра масс для любого количества материальных точек. Другая проблема в том, что у нас в игре тело состоит не из молекул. Игровые тела обычно цельные, и такая формула неудобна. В таких случаях суммирование заменяют интегрированием. Но заморачиваться на этом не стоит. Очевидно что для симметричных тел центр тяжести находится в центре, потому что для каждой молекулы в таком теле найдётся другая симметрично расположенная такой же массы, и для таких пар центр масс будет в центре значит и суммарный тоже в центре. Если же у вас есть несимметричное тело, то тоже не стоит заморачиваться, можно выбрать центр тяжести на глаз ведь принцип его рачёта понятен. Зачем же тогда я выводил эту формулу, если всё равно всё можно делать на глаз?
     Автомобиль обычно имеет центр тяжести не посередине а смещённый вперёд в сторону тяжёлого двигателя. В таком случае мы можем взять сначала центр тяжести автомобиля без двигателя, и отдельно центр тяжести двигателя. а потом найти их общий центр тяжести. Это интересно, ведь заменяя в машине двигатель, можно получать разные центры масс и от этого будет зависеть поведение машины на дороге, т.к. центр масс влияет на вращение. (Так обычный кручёный мяч будет лететь нормально, а кручёный мяч со смещённым центром тяжести будет болтаться в полёте. В данной статье я не рассматриваю этот момент а просто рассказываю как находить центр масс).
     Так формула для расчёта центра масс оказалась достаточно полезной. Но Архимед выжал из неё ещё больше пользы. Эта формула открыла путь для целого метода исследования в различных разделах физики и математики. Этот метод называется барицентрическим. "Бари" - тяжёлый(греч.), "Барицентр" - центр тяжести.
     Пусть у нас есть две материальные точки по имени "Рак" и "Щука" одна с координатами (0 , 0), а другая (10 , 0) массой по 1кг каждая. Очевидно, что центр тяжести для них находится посередине (0, 5).


float Масса_Рака = 1;
float Масса_Щуки = 1;
Vector2 Рак = new Vector2(0 ,0);
Vector2 Щука = new Vector2(10,0);
Vector2 Baricenter = (Рак * Масса_Рака + Щука * Масса_Щуки) / (Масса_Рака + Масса_Щуки);

     Если увеличить массу Щуки до 3кг, центр тяжести сместится в сторону Щуки и станет (0, 7.5). Если ещё увеличить до 7кг то центр масс сместится в точку (0, 8.75). Если бы мы делали то де самое с Раком то центр тяжести смещался бы в его сторону. Когда масса первой точки станет равна нулю - то центр тяжести полностью совпадёт со второй точкой и наоборот. Это похоже на игру в перетягивание каната, и эта игра станет интереснее если к ней присоединится третий игрок.



float Масса_Лебедя = 1;
Vector2 Лебедь = new Vector2(5 ,5);
Vector2 Baricenter = (Рак * Масса_Рака + Щука * Масса_Щуки + Лебедь * Масса_Лебедя) / (Масса_Рака + Масса_Щуки + Масса_Лебедя);

     Теперь воз будет находится где-то внутри треугольника. Если их массы по килограмму то центр тяжести будет приблизительно (5, 1.66). Видно что третья точка влияет на его положение вдоль Y. Пробуя различные комбинации масс мы можем добиться расположения центра тяжести в любой точке в этом треугольнике, причём для разных комбинаций масс мы будем получать разные точки. Стоит однако заметить, что комбинации (1,1,1) и (5,5,5) равносильны, и вообще равносильны все комбинации с одинаковым процентным соотношением масс. Поэтому смысл имеют не сами массы, а их доля от общей массы. Это называется нормированные массы.
     Так имея три базовые точки, и задавая для них массы мы можем задавать четвёртую точку в пространстве. т.е. мы получили новую систему координат. Она называется Барицентрической системой координат. И мы можем задать в ней вектор.

float Sum = Масса_Рака + Масса_Щуки + Масса_Лебедя;
Vector3 BaricentricVector = new Vector3(Масса_Рака / Sum, Масса_Щуки / Sum, Масса_Лебедя / Sum);


     Подобно тому, как при помощи матриц мы можем переходить из одной декартовой системы координат в другую, так же мы при помощи трёх векторов можем переходить из барицентрической системы в декартовую и обратно. Причём переход обратно сделать легко он делается по выведенной нами формуле. Например барицентрический вектор (0.25 ,0.25 , 0.5) в декартовой системе соответствует вектору (5, 2.5). Но переход из декартовой в барицентрическую не так прост, но о нём чуть позже.
     Барицентрические координаты непривычны для обычных людей. Они интересны нам потому, как обладают некоторыми замечательными свойствами. Если мы положим Массу_Лебедя равной ноль, то воз будет находится на прямой между Раком и Щукой, а если Массу_Рака установим равной ноль, то воз будет находится на прямой соединяющей Лебедя и Щуку, и аналогично с Щукой. Если мы сделаем Лебедю отрицательную массу, то воз будет находится вне треугольника причём за стороной треугольника напротив Лебедя. Рак и Щука - аналогично. Значит с помощью отрицательных масс мы можем задать не только координаты точек внутри треугольника, но и вне.
     Тогда допустим у нас есть треугольник из трёх точек, и ещё одна произвольная точка. И мы хотим знать находится ли эта точка в треугольнике? Нам нужно лишь перевести координаты этой точки в барицентрическую систему этого треугольника и сравнить полученные координаты с нулём. Если все они больше нуля то точка лежит в треугольнике, если хоть одна координата меньше то не лежит. И ещё так можно проверить по какую именно сторону от треугольника лежит точка, и лежит ли она на какой-либо из сторон треугольника. Если точка попадает в треугольник то можно узнать к какой из вершин или сторон она ближе. Или даже расстояние до сторон. Вот я перечислил некоторые основные возможности. А пользоваться ими будем в следующих статьях, здесь же рассмотрим переход в барицентрическую систему и создадим класс отвечающий за это.
     Сперва хочу обратить внимание, что для построения барицентрической системы в плоскости нужно три точки, ни больше ни меньше. При этом они не должны лежать на одной прямой. Барицентрическую систему можно построить и в 3D, для этого нужны 4точки, не лежащие в одной плоскости. В 2D под тремя точками подразумевается треугольник, в 3D под четырьмя точками подразумевается тетраэдр. Теперь напишем переход из барицентрической системы в декартовую для 2D, это равносильно расчёту центру масс:

C = V1 * m1 + V2 * m2 + V3 * m3;

     Делить на сумму масс не нужно т.к. массы отнормированны(уже поделены). Это уравнение дано в векторном виде, перепишем его отдельно по координатам:

C.x = V1.x * m1 + V2.x * m2 + V3.x * m3;
C.y = V1.y * m1 + V2.y * m2 + V3.y * m3;


     Пусть у нас заданна в декартовой системе точка С и треугольник V1-V2-V3, Осталось только узнать какие же массы нужно положить в вершины треугольника, чтобы их центр масс лежал в точку C. Способ решения и будет способом перевода в барицентрическую систему.
     Во первых заметим, что массы должны быть нормированными т.е. в долях. Значит сумма всех масс: m1 + m2 + m3 = 1; Тогда одну из масс можно выразить из других. m1 = 1 - m2 - m3; Таким образом задача упростилась ведь найти нужно только две неизвестные величины, а третья считается их них:

C.x = V1.x * (1 - m2 - m3) + V2.x * m2 + V3.x * m3;
C.y = V1.y * (1 - m2 - m3) + V2.y * m2 + V3.y * m3;


Отсюда получаем:

C.x = V1.x + (V2.x - V1.x) * m2 + (V3.x - V1.x)* m3;
C.y = V1.y + (V2.y - V1.y) * m2 + (V3.y - V1.y)* m3;


И ещё:

(C.x - V1.x) = (V2.x - V1.x) * m2 + (V3.x - V1.x)* m3;
(C.y - V1.y) = (V2.y - V1.y) * m2 + (V3.y - V1.y)* m3;


Получилась обычная система уравнений вида:

a = b * x + c * y;
d = e * x + f * y;


     Где a,b,c,d,e,f - известные числа. Такая система легко решается путём сложения и вычитания уравнений. Но есть опасность что некоторые из чисел a,b,c,d,e,f это нужно проверять и выбирать путь решения. Но я лучше решу её методом Крамера который не требует такой проверки и он очень универсален, мы также применим его для 3D. В тонкости метода вникать не буду, и не буду объяснять что такое матрица и определитель. Узнайте об этом в учебнике по линейной алгебре. Если Вы действительно хотели бы это узнать то лучше прочитайте об этом сейчас т.к. далее я предоставляю возможность закрепить полученное новое знание на неплохом примере. Это универсальное знание может Вам пригодится, например если Вы захотите делать сплайны или кривые Безье и вообще много где, линейная алгебра самая частопригождающаяся часть математики на мой взгляд. Если знать не хотите то тупо скопируйте мой код.

    //Класс включает вершины треугольника V1, V2, V3
    //Он позволяет преобразовывать вектор из декартовых
    //в барицентрические координаты
    //и обратно
    class Baricentric2D
    {
        public Vector2 V1, V2, V3; //Базисные точки, вершины треугольника

        /// <summary>
        /// Конструктор барицентрического класса
        /// </summary>
        /// <param name="V1">Первая вершина базисного треугольника</param>
        /// <param name="V2">Вторая вершина базисного треугольника</param>
        /// <param name="V3">Третья вершина базисного треугольника</param>
        public Baricentric2D(Vector2 V1, Vector2 V2, Vector2 V3)
        {
            this.V1 = V1;
            this.V2 = V2;
            this.V3 = V3;
        }

        /// <summary>
        /// Трансформирует декартовый вектор в барицентрический
        /// </summary>
        /// <param name="Value">Вектор координаты которой преобразовываются</param>
        /// <returns>Преобразованный вектор</returns>
        public Vector3 Transformation(Vector2 Value)
        {
            float m1, m2, m3; //результативные массы

            float MainDet, Det; //Переменные для хранения детерминанты(определителя)

            //Матрица размером 2x3
            float M11, M12, M13;
            float M21, M22, M23;

            //Заполнение матрицы коэффициентами уравнений
            //(Только вот столбец ответов первый, а не последний)
            //(C.x - V1.x) = (V2.x - V1.x) * m2 + (V3.x - V1.x) * m3;
            //(C.y - V1.y) = (V2.y - V1.y) * m2 + (V3.y - V1.y) * m3;
            M11 = (Value.X - V1.X); M12 = (V2.X - V1.X); M13 = (V3.X - V1.X);
            M21 = (Value.Y - V1.Y); M22 = (V2.Y - V1.Y); M23 = (V3.Y - V1.Y);

            //Главный определитель
            MainDet = M12 * M23 - M22 * M13;

            //Определитель для массы m2
            Det = M11 * M23 - M21 * M13;
            //Значение массы m2
            m2 = Det / MainDet;

            //Определитель для массы m3
            Det = M12 * M21 - M11 * M22;
            //Значение массы m3
            m3 = Det / MainDet;

            //Масса m1
            m1 = 1 - m2 - m3;

            //результат
            return new Vector3(m1, m2, m3);
        }

        /// <summary>
        /// Обратное преобразование
        /// по сути нахождение центра масс треугольника
        /// </summary>
        /// <param name="m1">Масса первой вершины</param>
        /// <param name="m2">Масса второй вершины</param>
        /// <param name="m3">Масса третьей вершины</param>
        /// <returns>Вектор в декартовой системе координат</returns>
        public Vector2 ReTransformation(float m1, float m2, float m3)
        {
            return (this.V1 * m1 + this.V2 * m2 + this.V3 * m3) / (m1 + m2 + m3);
        }
    }


     Стоит заметить, что метод обратного преобразования адаптирован принимать любые массы не обязательно нормированные.
     Решим теперь эту задачу в 3D. Для этого нужно решить систему уравнений:

(C.x - V1.x) = (V2.x - V1.x) * m2 + (V3.x - V1.x)* m3 + (V4.x - V1.x) * m4;
(C.y - V1.y) = (V2.y - V1.y) * m2 + (V3.y - V1.y)* m3 + (V4.x - V1.x) * m4;
(C.z - V1.z) = (V2.z - V1.z) * m2 + (V3.z - V1.z)* m3 + (V4.z - V1.z) * m4;


   //Класс включает вершины тетраэдра V1, V2, V3
    //Он позволяет преобразовывать вектор из декартовых
    //в барицентрические координаты
    //и обратно
    class Baricentric3D
    {
        public Vector3 V1, V2, V3, V4; //Базисные точки, вершины тетраэдра

        /// <summary>
        /// Конструктор барицентрического класса
        /// </summary>
        /// <param name="V1">Первая вершина базисного тетраэдра</param>
        /// <param name="V2">Вторая вершина базисного тетраэдра</param>
        /// <param name="V3">Третья вершина базисного тетраэдра</param>
        /// <param name="V4">Четвёртая вершина базисного тетраэдра</param>
        public Baricentric3D(Vector3 V1, Vector3 V2, Vector3 V3, Vector3 V4)
        {
            this.V1 = V1;
            this.V2 = V2;
            this.V3 = V3;
            this.V4 = V4;
        }

        /// <summary>
        /// Трансформирует декартовый вектор в барицентрический
        /// </summary>
        /// <param name="Value">Вектор координаты которой преобразовываются</param>
        /// <returns>Преобразованный вектор</returns>
        public Vector4 Transformation(Vector3 Value)
        {
            float m1, m2, m3, m4; //результативные массы

            float MainDet, Det; //Переменные для хранения детерминанты(определителя)

            //Матрица размером 4x4, но используется лишь как 3х4
            //Сразу заполняется коэффицентами уравнений
            //(Только вот столбец ответов первый, а не последний)
            //(C.x - V1.x) = (V2.x - V1.x) * m2 + (V3.x - V1.x) * m3 + (V4.x - V1.x) * m4;
            //(C.y - V1.y) = (V2.y - V1.y) * m2 + (V3.y - V1.y) * m3 + (V4.x - V1.x) * m4;
            //(C.z - V1.z) = (V2.z - V1.z) * m2 + (V3.z - V1.z) * m3 + (V4.z - V1.z) * m4;
            Matrix Mx = new Matrix(
                V2.X - V1.X, V3.X - V1.X, V4.X - V1.X, Value.X - V1.X,
                V2.Y - V1.Y, V3.Y - V1.Y, V4.Y - V1.Y, Value.Y - V1.Y,
                V2.Z - V1.Z, V3.Z - V1.Z, V4.Z - V1.Z, Value.Z - V1.Z,
                0, 0, 0, 0
                );

            //Главный определитель
            MainDet =
                Mx.M11 * Mx.M22 * Mx.M33 +
                Mx.M12 * Mx.M23 * Mx.M31 +
                Mx.M13 * Mx.M21 * Mx.M32 -
                Mx.M13 * Mx.M22 * Mx.M31 -
                Mx.M12 * Mx.M21 * Mx.M33 -
                Mx.M11 * Mx.M23 * Mx.M32;

            //Определитель для массы m2
            Det =
                Mx.M14 * Mx.M22 * Mx.M33 +
                Mx.M12 * Mx.M23 * Mx.M34 +
                Mx.M13 * Mx.M24 * Mx.M32 -
                Mx.M13 * Mx.M22 * Mx.M34 -
                Mx.M12 * Mx.M24 * Mx.M33 -   
                Mx.M14 * Mx.M23 * Mx.M32;
            //Значение массы m2
            m2 = Det / MainDet;

            //Определитель для массы m3
            Det =
                Mx.M11 * Mx.M24 * Mx.M33 +
                Mx.M14 * Mx.M23 * Mx.M31 +
                Mx.M13 * Mx.M21 * Mx.M34 -
                Mx.M13 * Mx.M24 * Mx.M31 -
                Mx.M14 * Mx.M21 * Mx.M33 -
                Mx.M11 * Mx.M23 * Mx.M34;
            //Значение массы m3
            m3 = Det / MainDet;

            //Определитель для массы m4
            Det =
                Mx.M11 * Mx.M22 * Mx.M34 +
                Mx.M12 * Mx.M24 * Mx.M31 +
                Mx.M14 * Mx.M21 * Mx.M32 -
                Mx.M14 * Mx.M22 * Mx.M31 -
                Mx.M12 * Mx.M21 * Mx.M34 -
                Mx.M11 * Mx.M24 * Mx.M32;
            //Значение массы m4
            m4 = Det / MainDet;

            //Значение массы m1
            m1 = 1 - m2 - m3 - m4;

            //результат
            return new Vector4(m1, m2, m3, m4);
        }

        /// <summary>
        /// Обратное преобразование
        /// по сути нахождение центра масс тетраэдра
        /// </summary>
        /// <param name="m1">Масса первой вершины</param>
        /// <param name="m2">Масса второй вершины</param>
        /// <param name="m3">Масса третьей вершины</param>
        /// <param name="m4">Масса четвёртой вершины</param>
        /// <returns>Вектор в декартовой системе координат</returns>
        public Vector3 ReTransformation(float m1, float m2, float m3, float m4)
        {
            return (this.V1 * m1 + this.V2 * m2 + this.V3 * m3 + this.V4 * m4) / (m1 + m2 + m3 + m4);
        }
    }


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


     В 3D системе всё аналогичн, только вместо треугольника тетраэдр, а вместо сторон грани. Я надеюсь позже найду время подумать над этим и найти какие-нибудь интересные особенности барицентрической системы и интересные приёмчики. А пока всё. Хотя можете ещё почитать про трилинейную систему координат.

Комментариев нет:

Отправить комментарий