Современные информационные технологии/1. Компьютерная  инженерия

 

Вяткин С. И., Романюк* О. В., Величко* П. А.

Институт автоматики и электрометрии СО РАН

*Винницкий национальный технический университет

Численный метод для анимации трехмерных объектов

 

Одной из задач компьютерной графики является анимация объектов трехмерной сцены, в  частности, задача инверсной кинематики [1, 2].   

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

Цепь инверсной кинематики – это иерархия, где взаимодействие между объектами осуществляется «снизу вверх», от дочернего объекта к родительскому. Для примера возьмем классическую модель человека - бипод. Если перемещать в пространстве туловище (родительский объект), вместе с ним, как жестко закрепленные, будут перемещаться руки, ноги и голова (дочерние объекты). Это цепь прямой кинематики, где воздействие на родительский объект влияет на его дочерние объекты. Если же в этом биподе реализована цепь обратной кинематики, то перемещение в пространстве дочернего объекта, например, кисти руки, приведёт к перемещению родительских объектов: предплечья, плеча, туловища.

Для алгебраического решения задачи инверсной кинематики, требуется решить уравнение для 2N независимых переменных [3, 4]. Так как размерность матриц составляет элемента, то появляется возможность получить четыре линейно независимых уравнения, что дает возможность найти четыре переменные. На самом же деле хотелось бы иметь решение для произвольного числа переменных, ведь чем больше число задействованных степеней свободы, тем больше объектов может быть в цепочке, тем манипулятор универсальней. Алгебраический способ дает решения для манипуляторов с не более чем шестью степенями свободы.  Возможность найти при четырех линейно независимых уравнениях шесть переменных появляется в связи с тем, что локальные матрицы объектов цепочки в целом сильно разрежены. Это позволяет получить небольшое количество решений, а далее выбрать из них с помощью определенного критерия наиболее приемлемое и разумное. В целом, шесть степеней свободы позволяют создать полноценный трехколенный (манипулятор из трех объектов в цепочке) манипулятор, удовлетворяющий большинству задач роботостроения, где обычно манипуляторы и применяются. Недостатками являются малое количество степеней свободы (не более шести) и сложности с контролем ограничения на степени свободы.

В геометрическом методе, решение в аналитическом виде получается с использованием геометрии цепочки. В работе [5] использованы координатные методы, описанные в [6], для получения аналитического решения манипулятора с семью степенями свободы. Этот метод применим к любому манипулятору с заранее известной геометрией. Недостатками метода можно назвать то, что для его функционирования необходимо знать аналитическое решение для первых трех объектов цепочки, а также то, что геометрический подход применим только для заранее известной геометрии манипулятора [7]. Алгебраический и геометрический методы совместно использованы для получения аналитического решения в [8] для манипулятора с семью степенями свободы.

Суть итерационных методов заключается в том, что решение достигается в ходе итерационного приближения. Основные проблемы, возникающие при этом – это сходимость таких методов. Большая часть итерационных методов основаны на алгоритмах численной минимизации нелинейной функции, но есть и алгоритмы, где используется геометрический подход.

Численные алгоритмы является универсальными в плане способности решить задачу инверсной кинематики для любого количества степеней свободы. Также важным моментом является переход от задачи поиска решения без ограничений на переменные (т.е. на углы вращения) к задаче поиска решения с ограничениями на переменные. Ограничения степени свободы существенны, так как моделируемые объекты, для которых и появилась задача инверсной кинематики, обычно в природе имеют физические ограничения на возможность вращения. Например, алгебраический метод эти ограничения не учитывает, и реализовать ограничения, используя алгебраическое решение затруднительно. Итерационный метод, в силу итерационного приближения к решению, естественным образом дает решение с ограничениями на переменные [9]. Недостатками метода являются сложность вычисления и контроля сходимости.

В работе [3] описан итерационный метод, использующий геометрический подход, это метод циклического координатного спуска. Метод циклического координатного спуска минимизирует расстояние от конечного эффектора до цели, регулируя каждый совместный угол поочередно. Метод начинает работать с последнего узла в цепочке и работает в обратном направлении, регулируя каждый шарнир на пути. Действие продолжается вверх по цепи по достижении корня цепочки. Затем процесс повторяется, начиная опять с последнего шарнира в цепи. В итоге возможны два случая: конец цепочки достиг цели или же цикл повторился некоторое число раз и оборвался, когда уже невозможно сделать очередной поворот конечного шарнира.  Это означает, что расстояние от базового узла до цели больше суммы всех связей.

          В цепочке могут присутствовать ограничения степеней свободы для индивидуального шарнира, что удерживает его от вращения, которое физически недопустимо для модели. В других методах инверсной кинематики это может достаточно сильно усложнить решение, но в методе циклического координатного спуска, такие ограничения легко вводимы.  Каждый шаг – это поворот шарнира, что  позволяет легко включить ограничения на эти повороты. Достаточно проверить, не вышел ли угол поворота за допустимые границы. Если да, то поворачивается шарнир лишь до предела. Использование ограничений степеней свободы позволяет более гибко манипулировать динамической цепочкой. Данный метод прост для понимания и более легок для реализации, чем численные итерационные методы. Кроме того, он существенно быстрее численных алгоритмов, но при этом есть некоторые требования инверсной кинематики, которые он предоставить не может или же их реализация для такого алгоритма затруднительна. Однако часть параметров (трение сустава, приоритет сустава и т.д.) для настройки динамики цепочки не может быть реализована, или же, реализация их затруднительна.

Смешанные методы могут дополнять друг друга. В частности, в работе [3] использованы два алгоритма минимизации: метод циклического координатного спуска (Cyclic Coordinate Descent - CCD) и Broyden-Fletcher-Shanno (BFS). Метод CCD использовался для нахождения начального значения для BFS алгоритма. Проблема подобных комбинаций алгоритмов заключается в том, что от такого инструмента как инверсная кинематика требуется не просто управление связной цепочкой, но и масса других настраиваемых параметров. Разные алгоритмы предоставляют настройку параметров по-разному, однако, количество поддерживаемых параметров в разных алгоритмах неодинаково. Таким образом, при реализации комбинации алгоритмов возникает проблема корректных настроек и передачи таких параметров в рамках одного процесса поиска решения.

Анализ [3, 10, 11, 12] текущего положения дел в области минимизации нелинейных функций показал, что есть несколько конкурирующих алгоритмов, решающих такие задачи.

Численный алгоритм является универсальным в плане способности решить задачу IK для любого количества DOF. В задаче IK также важным моментом является переход от задачи поиска решения без ограничений на переменные (т.е. на углы вращения) к задаче поиска решения с ограничениями на переменные. Ограничения DOF существенны, так как моделируемые объекты, для которых и появилась задача IK, обычно в природе имеют физические ограничения на возможность вращения. Например, алгебраический метод эти ограничения не учитывает, и реализовать ограничения, используя алгебраическое решение затруднительно. Итерационный метод, в силу итеративного приближения к решению, естественным образом дает решение с ограничениями на переменные. Как указывалось выше, решая задачу, мы преследуем цель максимально приближения  к , однако нам достаточно равенства крайне правого столбцов матриц, которые характеризуют положение в пространстве конечного эффектора и цели, за которой движется цепочка. Из этих соображений мы определяем  нашу целевую функцию как:

 

 

Как можно заметить, она характеризует квадрат расстояния между  желаемым положением конечного объекта и текущим его положением. Из переменных степеней свободы составляем 2N переменных, то есть. Начальным значением этого вектора берем текущие значения задействованных углов во всей IK – цепочке. С помощью алгоритма минимизации нелинейной функции многих переменных, минимизируем функцию  на векторе . Интуитивно понятно, что если объект цель, характеризующийся матрицей , лежит в пределах досягаемости для цепочки объектов, то можно так «расправить» цепочку объектов, варьируя компоненты вектора  (фактически варьируя углы поворота локальных матриц объектов), что в итоге матрица  значения крайне правых столбцови  будут очень близки. Такая задача минимизации нелинейной функции решается итерационно и в рамках этого подхода известно несколько алгоритмов, соревнующихся друг с другом в эффективности. Резюмируем:


.

 

Решение задачи – поиск вектора q, который есть минимум целевой функции.

 

Достоинства

Недостатки

·        Любое количество степеней свободы.

·        Единственное решение

 

·        Большая сложность вычислений, медленно.

·        Трудности  с контролем сходимости.

 

 

Реализация метода была выполнена в виде динамической библиотеки. Далее, в отдельном приложении для теста брались специальные функции, предложенные в книге [13]: расширенная функция Розенброка, расширенная обобщенная функция Пауэла, функция типа спиралевидного желоба и функция Вуда вида.

Точность вычислений IK – функции была принята точность, c которой вычисляется тип float, однако на самом деле этот вопрос требует детального рассмотрения и применения для этих целей алгоритма Хемминга [14]. Ярким примером, насколько важно уметь правильно вычислять производную по конечным разностям, является все та же функция Вуда. К примеру, было экспериментально показано, что вариация такого параметра, как характерная величина переменных typx, используемая при вычислении производных, приводит к 25% увеличению производительности алгоритма по времени. В частности, при  typx = 1 алгоритм работает 74 ms, а в случае typx = 0.6, алгоритм вырабатывает более точное решение за 55 ms. Заметим, что подобное улучшение производительности может быть решающим для режима реального времени. Данный пример показывает, что IK–функция, после своей реализации, так же требует значительных исследований на предмет подбора оптимальных параметров для алгоритма.

Литература

 

1.     Вяткин С. И. Анимация трехмерных объектов/ С. И. Вяткин, А. Н. Романюк, М. П. Поддубецкая // Измерительная и вычислительная техника в технологических процессах, Международный научно-технический журнал, Хмельницкий национальный университет, Украинская технологическая академия (г. Киев), Издатель: Хмельницкий национальный университет, Хмельницкий, 2013, № 1 (42). С. 207–211

2.     Вяткин С. И. Особенности анимации трехмерных объектов/ С. И. Вяткин, А. Н. Романюк  // Моделирование и компьютерная графика, Материалы пятой международной научно - технической конференции 24-27 сентября 2013, Донецк, ДонНТУ, Министерство образования и науки Украины, С. 72-79.

3.     Kwan W. Chin “Closed-form and generalized Inverse Kinematics solutions for animating the human articulated structure”. 1996. [Электронный ресурс]. – Режим доступа:

     http://www.citeulike.org/user/hurricane/article/1370370

4.     Paolo Baerlocher, “Inverse Kinematics Techniques for the interactive posture control of articulated figures”. Dissertation N 2383, Swiss Federal Institute of Technology, Lausanne, EPFL, Switzerland  2001.

5.     Lee, G.C.S. (1982). Robot arm kinematics, dynamics and control. Computer, 15(12), 62-79.

6.     Anon (1992).SEA Mathematical Formulae and Statistical Tables Book. Secondary Education Authority.

7.     Craig, J.J. (1989). Introduction to Robotics: Mechanics and Control. Addison-Wesley.

8.     Sasaki, S. (1995). Feasibility studies of kinematics problems of general serial-link robot manipulators. Robotica, 12, 309-322.

9.     Richard H. Byrd, P. Lu, J.Nocedal and C. Zhu. “A limited memory algorithm for bound constrained optimization”, SIAM Journal on Scientific Programming Computing, 16, 5 pp.1190-1208.1994.

10. Richard H. Byrd, J.Nocedal and R.B.Schnabel, “Representation of quasi-Newton matrices and their use in limited memory methods”, Mathematical Programming 63, 4, 1994, pp.129-156.

11. D.C. Liu and J.Nocedal, “On the limited memory BFGS method for large scale optimization methods”, Mathematical Programming 45 (1989), pp. 503-528.

12. J.Nocedal, “Updating quasi-Newton matrices with limited storage”, Mathematics of Computation 35 (1980), pp. 773-782.

13. Дэннис Дж. Численные методы безусловной оптимизации и решения нелинейных уравнений/ Дж.Дэннис, Р. Шнабель  / 1988.

14. Хемминг Р.В. Численные методы для научных работников и инженеров /  Р. В. Хемминг – М.: Наука, 1972.