Прямая и инверсная кинематика - это два разных способа вращения суставов в цепи. Из них более простым и требующим меньших вычислительных затрат является прямая кинематика (Forward Kinematics - FK), но при этом она лишена многих интуитивно по­ нятных возможностей управления, которыми обладает инверсная кинематика (Inverse Kinematics - IK), обеспечивающая вращение суставов по цепи.

В случае прямой кинематики каждый сустав просто поворачивается вручную, как это было сделано в предыдущем разделе с примером скелета. При повороте корневого суста­ ва цепи (например, плечевого сустава) вращательное движение передается по цепи сус­ тавов дальше вниз и перемещает все дочерние суставы. На рис. 8.9 представлена создан­ ная в предыдущем разделе структура руки с повернутым суставом плеча. Хотя создать такое движение относительно несложно и в Майя просто рассчитать его, для располо­ женных ниже по цепи суставов оно недостаточно точное. Если, например, необходимо прикоснуться запястьем к другому объекту, то сначала необходимо повернуть плечо, по­ том локоть, а потом, возможно, настроить поворот обоих суставов так, чтобы в точности

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

В то же время инверсная кинематика намного более сложная математически, но вместе с тем предусматривает точную регулировку суставов конечностей и, когда остальная часть иерархии уже установлена, помогает управлять движением этих суставов. В инверсной ки­ нематике движение сустава конечности (на самом деле управляющего положением сустава маркера (handle)) приводит к повороту суставов вверх по цепи, поэтому движение распро­ страняется по цепи в обратном (backward), или инверсном (inverse), направлении.

Инверсная кинематика использует маркеры инверсной кинематики (IK handle), или просто маркеры IK, и решатели инверсной кинематики (IK solver), или просто решатели IK. Маркер инверсной кинематики проходит по суставам, на которые распространяется его влияние, эти суставы называют цепью управляемой инверсной кинематикой (IK chain), и сквозь эту же цепь проходит линия маркера (handle wire). Управляющий вектор (handle vector) выходит из начального сустава и заканчивается в конечном, в ко­ тором располагается конечный исполнительный элемент (end effector). После добавления решателя IK в рассмотренную в предыдущем примере цепь суставов можно будет ани- мировать простым перемещением сустава запястья. При этом плечо и локоть будут вра­ щаться так, чтобы вся рука двигалась правильно, как показано на рис. 8.10.

Рис. 8.9. Прямая кинематика: при Рис. 8.10. Перемещение цепи сус- повороте сустава, старшего в тавов с помощью перемещения ко- иерархии, перемещается вся цепь печного исполнительного элемента суставов маркера инверсной кинематики

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

тава, но суставов в ней может быть и больше, особенно если используется маркер инверс­ ной кинематики сплайна (IK Spline handle), который управляет лежащими в его основе суставами с помощью кривой. Среди реализованных в Maya решателей инверсной кине­ матики можно выделить четыре (и соответствующие типы инверсной кинематики): ре­ шатель ikrP для расчета инверсной кинематики вращения плоскости (IK rotat e Plane), решатель ikSC для расчета инверсной кинематики простой цепи (IK Single Chain), реша­ тель ikSpline для расчета инверсной кинематики сплайна (IK Spline) и решатель ikSpring для расчета инверсной кинематики пружины (IK Spring). Каждый тип реша­ теля IK имеет собственный тип маркера IK.

Урок адаптирован под версию 3ds max 2009.

Инверсная кинематика является основой, на которой строится персонажная анимация. Она работает совсем не так, как работает прямая кинематика - потомки приводят в движение родительские объекты. Потомок, который вызывает трансформации других объектов по законам инверсной кинематики, называется либо эффектором (Effector), если он расположен в середине иерархической цепочки, либо конечным эффектором (EndEffector), если он является конечным объектом данной цепочки. Через эффектор осуществляется манипулирование всей иерархической цепочкой. При этом трансформация конечного эффектора обеспечивает трансформацию всех объектов иерархической цепи по законам инверсной кинематики, а трансформация просто эффектора приводит к тому, что положение объектов, стоящих по иерархии ниже его, меняется по законам прямой кинематики, а объектов с более высокой иерархией - по законам инверсной кинематики.

В качестве примера откройте файл Table_ lamp3-1. max . Иерархическая цепь объектов здесь уже создана. Чтобы ее увидеть, выполните команду Select by Name и в окне Select from Scene разверните структуру объекта. В данном случае конечным эффектором иерархической цепочки является самый нижний в иерархии объект Reflector.

Установите режим инверсной кинематики. Для этого на панели Hierarchy (Иерархия) откройте закладку IK (Инверсная кинематика) и щелкните кнопкой Interactive IK (Интерактивная инверсная кинематика). Выделите объект Support и переместите его в сторону. Вместе с ним точно так же переместятся и все остальные объекты. Теперь выделите, например, объект Lever02 и переместите его в любую сторону. Его перемещение вызовет изменение положения всех остальных объектов, включая объект Support, являющийся самым высшим в иерархии. При этом положение объектов, стоящих по иерархии ниже перемещаемого объекта (в данном случае это объекты Hinge03, Lever03, Reflector), будет меняться по законам прямой кинематики, а объектов с более высокой иерархией (Hinge02, Lever01, Hinge01, Support) - по законам инверсной кинематики.

Обратите внимание, что при перемещении рычага Lever02 положение и ориентация всех объектов меняются непредсказуемым образом. Это связано с тем, что по умолчанию для объектов, управляемых посредством эффектора, допустимы любые варианты перемещения и вращения, хотя на практике они могут трансформироваться только каким-либо определенным образом. При инверсной кинематике эти проблемы регулируются на закладке IK панели Hierarchy с помощью параметров, задаваемых в свитках Sliding Joints (Скользящие соединения) и Rotational Joints (Вращательные соединения).

Кроме того, можно определить в системе объект, который будет играть роль ограничителя. Terminator (Ограничитель) - это последний объект системы инверсной кинематики, начиная с верхнего уровня, который не подвергается влиянию при движении дочернего объекта. Для определения ограничителя достаточно выделить объект и в свитке Object Parameters (Параметры объекта) установить для него флажок Terminator .

Выделите объект Hinge01, перейдите на вкладку Hierarchy (Иерархия) | IK (Инверсная кинематика) и включите команду Interactive IK (Интерактивная инверсная кинематика). В свитке Object Parameters (Параметры объекта) установите флажок для Terminator . Передвиньте объект Lever02 в любую сторону. При этом объект Hinge01 и его родительский объект Support останутся неподвижными (рис. 1.1).

Рис. 1.1. Шарнир Hinge01 определен в качестве ограничителя

Продолжение урока вы можете найти в книге Горелика А.Г. « «.


Перевод осуществил Pavel A. Chuvanov, участник проекта Almighty.

Кинематика - есть процесс вычисление позиции в пространстве для конца взаимосвязанной структуры при заданных углах поворота всех шарнирных точек (Joints). Это легко осуществляется, если есть только одно решение. Инверсная кинематика делает обратное. Для данной конечной точки вычисляются необходимые углы поворота шарниров таким образом, чтобы удалось достичь этой конечной точки. При этом могут возникнуть трудности, если есть много или бесконечно много решений.

Данный процесс чрезвычайно полезен в робототехнике. Например, вы захотели, чтобы рука робота потянулась и взяла объект. Если программа знает местоположение объекта относительно плечевого сустава, то ей достаточно расчитать углы поворота шарниров чтобы достичь объекта. Также инверсная кинематика полезна в 3D играх. Возьмем для примера дракона с очень длинной шеей. Дракон должен реалистично изогнуть шею и слопать игрока стоящего на полу. Или игрок захотел поднять с пола некий объект или нажать на кнопку. Пользователь увидит на экране как игрок потянется и коснется объекта, вместо того чтобы просто махнуть рукой где-то вблизи объекта (как например в Alone In The Dark).

В предыдущем уроке мы ознакомились с методом прямой кинематики, при котором иерархические связи передаются от предков к потомкам. Это приводит к тому, что дочерние объекты частично или полностью наследуют поведение родительских объектов и при этом сами никакого влияния на них не оказывают. Подобный тип иерархического связывания позволяет легко анимировать объекты, состоящие из большого числа элементов, при условии, что всем элементам объекта назначаются одинаковые трансформации. Однако он не поможет, когда перемещение одного элемента должно оказывать влияние на все прочие элементы, связанные внутри сложного объекта, с учетом их положения в иерархической цепочке, а также свойств. Такое поведение имитируется посредством инверсной, или, как часто говорят, обратной, кинематики (Inverse Kinematics), простые примеры использования которой мы и рассмотрим в данном уроке.

Теоретические аспекты

Понятие инверсной кинематики

Инверсная кинематика отличается от прямой иным принципом наследования. Если при прямой кинематике трансформация потомков определяется трансформацией их предков, то при инверсной - потомки приводят в движение родительские объекты, то есть программа рассчитывает положение и ориентацию родительских объектов, исходя из положения и ориентации трансформируемого потомка. Потомок, который вызывает трансформации других объектов по законам инверсной кинематики, называется либо эффектором (Effector ), если он расположен в середине отдельной иерархической ветви, либо конечным эффектором (End Effector ), если является конечным объектом данной ветви. Через эффектор осуществляется манипулирование всей иерархической цепочкой. При этом трансформация конечного эффектора обеспечивает трансформацию всех объектов иерархической ветви по законам инверсной кинематики, а трансформация просто эффектора приводит к тому, что положение объектов, стоящих по иерархии ниже его, меняется по законам прямой кинематики, а объектов с более высокой иерархией - по законам инверсной кинематики.

Чтобы убедиться в этом, создайте простую сцену со своеобразной булавой, смоделированной из примитива Hedra , десяти торусов и цилиндра со скошенными основаниями (рис. 1). Свяжите объекты инструментом Select and Link (Выделить и связать), двигаясь в направлении от объекта Hedra 01 к объекту ChamferCyl 01 - в итоге цилиндр окажется Root-объектом (рис. 2). Выделите цилиндр и переместите его влево - вместе с ним переместятся и все остальные объекты, являющиеся по отношению к нему дочерними. Тогда как передвижение одного из расположенных в середине цепочки торусов приведет к перемещению лишь дочерних по отношению к нему объектов цепочки, а объекты, расположенные выше его по иерархии, останутся на месте (рис. 3). Вернитесь к исходному положению объектов и активируйте режим инверсной кинематики, открыв на панели Hierarchy закладку IK и щелкнув на кнопке Interactive IK , которая должна подсветиться (рис. 4). Сохраните рабочую сцену в файл и повторите те же самые операции с перемещением цилиндра и торуса - перемещение первого объекта даст те же самые результаты, что и ранее, а вот изменение положения торуса приведет к соответствующим изменениям положения всех остальных (а не только дочерних по отношению к нему) элементов, включая Root-объект (рис. 5). При этом положение объектов, стоящих по иерархии ниже перемещаемого торуса (в данном случае он играет роль просто эффектора), будет меняться по законам прямой кинематики, а объектов с более высокой иерархией - по законам инверсной кинематики.

Управление вращением и перемещением объектов

Вернитесь к сохраненной рабочей сцене, выделите объект Hedra 01 и поперемещайте его, наблюдая за всеми объектами иерархической цепи, и вы убедитесь в полном отсутствии контроля над ними, так как положение и ориентация последних меняются самым непредсказуемым образом (рис. 6). Это связано с тем, что по умолчанию для управляемых посредством эффектора объектов допустимы любые варианты перемещения и вращения. На практике же чаще всего связанные объекты могут трансформироваться только каким-то определенным образом, а значит, все другие варианты трансформаций для них запрещены.

Данный аспект при обратной кинематике регулируется в первую очередь посредством Joint-параметров, позволяющих определить, относительно каких осей и в каких пределах может вращаться (Rotational Joint s ) и/или перемещаться (Sliding Joint s ) тот или иной дочерний объект относительно родительского. Иными словами, Joint-параметры задают характер трансформации связи (или, как часто говорят, сочленения либо сустава) между дочерним и родительским объектами. Настраиваются данные параметры на закладке IK панели Hierarchy , однако по умолчанию там доступны лишь параметры, отвечающие за ограничение вращения объектов иерархической цепочки (Rotational Joint s ). Возможность управления объектами посредством параметров Sliding Joint s появится только после назначения им специализированного IK-контроллера. Последнее осуществляется через меню Animation =>IK Solvers (Анимация=>IK-решения), предусматривающее присваивание объектам одного из следующих IK-контроллеров:

  • HI Solver (History Independent Solver ) - исторически независимый контроллер (считается самым универсальным для персонажной анимации);
  • HD Solver (History Dependent Solver ) - исторически зависимый контроллер;
  • IK Limb Solver - контроллер для анимации конечностей (рассчитан только на два объекта иерархической цепи);
  • Spline IK Solver - сплайновый контроллер.

Данные контроллеры не только открывают доступ к параметрам Sliding Joint s , но и обеспечивают еще массу возможностей благодаря тому, что преобразуют обычные иерархические последовательности в так называемые цепи инверсной кинематики (IK Chain ), которые представляют собой невизуализируемые объекты управления, упрощающие управление элементами иерархии по законам инверсной кинематики. Внешне в окнах проекций IK-цепи выглядят как ряд перекрестий и линий, соединяющих начало и окончание конкретной IK-цепи. Выбираются данные элементы обычным образом (щелчком по перекрестию или инструментом Select by Name ), а вот редактируются не через панель Modify (как прочие объекты), а через панель Motion . Независимо от типа контроллера IK-цепи создаются одинаково: выбирается первый элемент предполагаемой цепи, затем ему назначается IK-контроллер и указывается последний элемент цепочки. Различие между IK-контроллерами заключается в использовании при расчетах IK-решений разных методов преобразования IK-цепочек.

Чтобы убедиться в том, что IK-цепи упрощают управление элементами иерархии, создайте упрощенную модель ноги (бедро и голень со стопой) - рис. 7. Свяжите их в иерархическую цепочку, начиная данный процесс снизу, чтобы в итоге в роли Root-объекта оказался верхний цилиндр (то есть бедро). Включите режим инверсной кинематики и попробуйте переместить ступню влево - результат окажется совсем не таким, какой можно наблюдать при ходьбе, поскольку даже при небольшом перемещении повороты cуставов будут слишком велики (рис. 8). А теперь создайте дополнительный фиктивный объект в верхней части бедра и включите его в иерархию в качестве Root-объекта. Выделите Dummy-объект и назначьте цепи контроллер HI Solver , применив команду Animation =>IK Solvers =>HI Solver и указав в качестве конечного эффектора ступню, - при выполнении данного действия за курсором мыши будет тянуться пунктирная линия (рис. 9). Это приведет к созданию цепи инверсной кинематики с IK-контроллером, о чем будет свидетельствовать появление линии, простирающейся от вершины бедра к ступне, и перекрестия (это так называемый целевой объект IK Goal ) в опорной точке эффектора (рис. 10). Если вы подвигаете перекрестие, то увидите, что нога перемещается, сгибается и поворачивается таким образом, что опорная точка ступни всегда находится в центре крестика, но сама ступня не перемещается относительно голени (рис. 11). Попробуйте анимировать подобное движение, щелкнув на кнопке Auto Key , активировав 50-й кадр, перетащив перекрестие немного назад, а затем, в 100-м кадре, вернув его в исходное положение и выключив режим автоматического создания ключей. Проиграйте анимацию, и вы увидите предельно упрощенную имитацию ходьбы (рис. 12). Конечно, до настоящей ходьбы еще далеко, но мы пока ограничимся этим и вернемся к данному вопросу в одном из ближайших уроков, когда будем говорить о построении иерархии с применением Bones .

Вернемся к сохраненной на диске рабочей сцене с булавой и попробуем немного поэкспериментировать с настройкой Joint-параметров. Выделите Root-объект, из меню Animation =>IK Solvers (Анимация=>IK-решения) выберите команду HD Solver и укажите мышью конечный эффектор (то есть объект Hedra 01). Выделите объект Hedra 01, вновь переместите его в одно из направлений и убедитесь, что результат окажется гораздо более реалистичным (рис. 13). Выделите объект ChamferCyl 01 и откройте закладку IK панели Hierarchy . По умолчанию для него у параметров Sliding Joint s отключены флажки Active в отношении всех трех осей и включены для параметров Rotational Joint s (рис. 14). Это означает, что данный объект может вращаться произвольным образом, но для него запрещены перемещения относительно любой из осей. Для примера отмените ограничение на скольжение относительно оси Z , включив флажок Active в разделе Z Axis , - после этого положение и ориентация объекта ChamferCyl 01 при перемещениях конечного эффектора станут совсем иными (рис. 15 и 16); верните ограничение. Обратите внимание, что даже при установленном ограничении на скольжение некоторое смещение объекта ChamferCyl 01 все же имеет место, так как ограничения устанавливаются не непосредственно на объекты, а на их сочленения друг с другом (Joint ), то есть на суставы (если провести аналогию с конечностью человека). Попробуйте также установить ограничения на вращение объекта ChamferCyl 01 в отношении всех трех осей, что позволит добиться жесткой фиксации положения и ориентации данного объекта, в то время как все прочие элементы IK-цепи по-прежнему будут полностью свободны от каких-либо ограничений на вращение и скольжение (рис. 17).

Рис. 14. Первоначальный вид свитков SlidingJoints и RotationalJoints для объекта ChamferCyl 01

Настройка пределов ограничений

Помимо включения/выключения ограничений на скольжение и вращение в свитках Sliding Joint s и Rotational Joints можно регулировать то, насколько допустимо перемещение или вращение относительно той или иной оси, то есть устанавливать пределы ограничений. Реализуется это посредством установки флажка Limited (Ограничение) и определения значений пределов вращения в полях From и To («От» и «До»). Наша рабочая сцена не очень подходит для экспериментов с ограничениями пределов скольжения и вращения, поэтому создайте новую сцену из трех цилиндров разного диаметра, размещенных друг на друге так, чтобы вверху был цилиндр самого большого радиуса (он должен оказаться в начале координат), а внизу - самого малого (рис. 18). Высота всех цилиндров одинакова и равна 30. Свяжите их в иерархическую цепочку, начиная данный процесс сверху так, чтобы в итоге в роли Root-объекта оказался нижний цилиндр (рис. 19).

Выделите нижний цилиндр и назначьте цепи контроллер HI Solver , применив команду Animation =>IK Solvers =>HI Solver и указав в качестве конечного эффектора верхний цилиндр. Выделите верхний цилиндр и на закладке IK панели Hierarchy в свитке Rotational Joints удалите флажки Active для всех трех осей, а в свитке Sliding Joint s включите флажок Active для оси Z . Аналогичную операцию проведите в отношении среднего цилиндра, а для нижнего цилиндра запретите вообще все виды Joint s-трансформаций. После этого попробуйте подвигать верхний цилиндр вверх и вниз - после установленных для него разрешений он будет перемещаться относительно оси Z (рис. 20) и без каких-либо ограничений может двигаться вверх и вниз бесконечно далеко. Теперь настроим для цилиндров пределы ограничений для их перемещения вдоль оси Z , чтобы верхний цилиндр вначале полностью погружался в средний, а затем средний - в нижний. То есть в итоге должна получиться некая имитация складной трубы (например, подзорной). Легче всего подобрать соответствующие ограничения с визуальным контролем пределов, что возможно при увеличении и уменьшении мышью при нажатой клавише Ctrl соответствующих значений в полях, расположенных справа от полей ввода (пока без включения флажка Limited ). В этом случае текущее состояние цилиндров будет сразу же отображаться в активном окне проекций. Выделите верхний цилиндр и таким способом (то есть изменяя параметры при нажатой клавише Ctrl) убедитесь, что его исходное положение (то есть когда он занимает свое первоначальное положение) соответствует значению From , равному 30, а конечное (когда данный цилиндр полностью погрузился в нижний цилиндр) - значению To , равному 0. Аналогичным образом подберите значения ограничений для среднего цилиндра, которые для поставленной задачи окажутся точно такими же. Включите соответствующие флажки Limited (рис. 21), и вы увидите, что при перемещении верхнего цилиндра наша «подзорная труба» действительно будет складываться задуманным образом (рис. 22). Сохраните рабочую сцену в файл. Анимируйте перемещение цилиндров: активируйте режим автоматической генерации ключей, перетащите ползунок на последний кадр, переместите верхний цилиндр так, чтобы он полностью погрузился в нижний, и отключите режим автоматической генерации ключей. Сохраните сцену в файл (позже он нам потребуется).

Рис. 21. Окончательный вид свитка SlidingJoints для верхнего и среднего цилиндров

При желании соединение объектов можно сделать более плавным, включив для соответствующих Joints-ограничений флажок Ease (данная возможность часто применяется для анимации «мягких» моделей). Для примера осуществите это для верхнего и среднего цилиндров (рис. 23). После этого эффект перемещения цилиндров при анимации станет более мягким, так как средний цилиндр будет начинать движение не при достижении верхним цилиндром своего нижнего предела, а чуть раньше.

  • Перевод
  • Recovery Mode

Что такое «Инверсная кинематика»?

Задачей инверсной кинематики является поиск такого набора конфигураций сочленений, который обеспечил бы максимально мягкое, быстрое и точное движение к заданным точкам. Однако, множество существующих ныне методов страдают от таких недостатков как высокая вычислительная сложность и неестественность результирующих поз. В этой статье описан новый (вероятно, на момент написания статьи - 2010 г. ) эвристический метод под названием «Метод прямого и обратного следования» (Forward and Backward Reaching Inverse Kinematics , далее просто FABRIK),
FABRIK избегает использования вращений и матриц в пользу непосредственного получения точки на прямой. Благораря этому, дело обходится всего несколькими итерациями, имеет низкую стоимость вычислений и визуально естественную позу в результате. FABRIK так-же без проблем справляется с наложением ограничений а так-же использованием нескольких цепей и/или конечных точек. Именно об этом методе этот пост.

Прошу отнестись с пониманием к этой выжимке, потому-что оригинал довольно большой, имеет много воды, уместных и неуместных повторений и отстранений от темы, а так-же сравнений с другими алгоритмами. Этим я решил все-таки пренебречь, поэтому, тут содержится лишь малая часть текста, которая, однако, отражает суть - прим. перев.

1. Искусственная модель тела

Система из множества твёрдых тел состоит из набора твёрдых тел, называемых узлами, соединёнными вместе рёбрами. Все рёбра являются компонентами, связанными с движением: они ограничивают перемещения в пределах некоторого угла относительно соседних рёбер. Моделирование виртуального тела важно для вычисления позы человека. Модель с правильно расставленными ограничениями позволит получить набор правильных поз, что даст возможность получить более реалистичное движение. Большинство моделей подразумевают твёрдость частей тела, хотя это просто примерное приближение к реальности.
Скелет обычно смоделирован в виде иерархии твёрдых сегментов соединённых рёбрами, каждое из которых задано такими свойствами как длинна, форма, обьём и масса. Манипулятор, на манер робо-руки или анимированного персонажа, смоделиован как цепь, собранная из твёрдых узлов, сопряженных друг с другом рёбрами. Каждое перемещение и/или вращение кости с индексом i влияет на все последующие элементы цепи. Цепь можно формализовать следующим образом: всякий узел без дочерних элементов следует величать конечной точкой; для каждой конечной точки цепь может быть сформирована движением обратно по скелету, от родителя к родителю до тех пор, пока не будет встречен корневой узел цепи (начало цепи). По определению, в задаче IK предполагается статичность корневого узла. Однако, методы обычно справляются с перемещением корня.

Алгоритм полного цикла алгоритма FABRIK (псевдокод, первый элемент массива под индексом 1)

Исходные данные: массив позиций узлов p[i] с i = 1...n, целевая позиция t и значения дистанций между сопряжёнными узлами. d[i] = | p - p[i] | for i = 1, ... , n-1 Выходные данные: Новые позиции p[i], i = 1...n //Дистанция между корнем и целью dist = | p - t | //Проверяем достижимость цели if dist > d + d + ... + d { //цель недостижима for i = 1, ..., n-1 do { //Найдем дистанцию r[i] между целью t и узлом p[i] r[i] = | t - p[i] | lambda[i] = d[i] / r[i] //Находим новую позицию узла p[i] p = (1 - lambda[i]) * p[i] + lambda[i] * t } } else { //Дель достижима; т.о. b будет новой позицией узла p b = p //Проверяем, не выше ли дистанция между конечным узлом p[n] и //целевой позицией t значения терпимости (tolerance) DIFa = | p[n] - t | while DIFa > tol do { //Этап 1: прямое следование //Устанавливаем конечный узел p[n] в качестве цели (вероятно, имелось ввиду "ставим на позицию цели" - прим. перев.) p[n] = t for i=n -1 , ..., 1 do { //Получаем расстояние r[i] между узлом p[i] и новой позицией p r[i] = | p - p[i] | lambda[i] = d[i] / r[i] //Вычисляем новую позицию узла p[i] p[i] = (1 - lambda[i]) * p + lambda[i] * p[i] } //Этап 2: обратное следование //Устанавливаем корневому элементу p начальную позицию p[i] = b for i=1 ,..., n - 1 do { //Получаем дистанцию r[i] между узлом p и позицией p[i] r[i] = | p - p[i] | lambda[i] = d[i] / r[i] //Получаем новую позицию p[i] p = (1-lambda[i]) * p[i] + lambda[i] * p } DIFa = | p[n] - t | } }

2.FABRIK - новое эвристическое решение задачи IK

В этой части предоставляется суть метода FABRIK. Он использует позиции, уже рассчитанные в режимах прямого и обратного следования. FABRIK достигает минимизации ошибки путём единоразовой подстройки угла каждого узла. Т.е. происходит обход всей цепи, начиная с последнего узла, с подстройкой угла каждого обойдённого узла, после чего, происходит обход цепи уже в обратном направлении. Этот метод, в отличие от преобразования вращений, обращает задачу поиска позиции узла в задачу поиска точки на прямой; следовательно, можно сэкономить время и уменьшить количество вычислений. Предположим что множество p,…, p[n] является множеством позиций узлов манипулятора. Также, предположим что p является корневым узлом и p[n] является конечным узлом, т.о. для простоты оставим один конечный узел. Цель представлена позицией t и начальной базовой позицией b . Метод FABRIK представлен в листинге выше и графической интерпретации полного цикла на рисунке слева, с одной целевой точкой и четырьмя узлами в цепи. Рассмотрим полный цикл алгоритма на рисунке:
  • a - Начальные позиции манипулятора и цели.
  • b - Двигаем конечный узел p к цели.
  • c - Обнаруживаем позицию p" p" и p , на дистанции d от точки p" .
  • d - Повторяем для всех узлов.
  • e - Вторая стадия алгоритма: передвигаем корневой элемент с позиции p" на его начальную позицию.
  • f - Повторяем для всех узлов, но на этот раз начинаем с базы и двигаемся к конечному узлу. Алгоритм повторяется до тех пор, пока позиция конечного элемента не приблизится к цели на достаточное расстояние.

Более подробно:
Сначала считаются позиции между узлами (массив d ), после чего идёт проверка, достижима ли целевая точка; считается расстояние между корневым узлом и целью (dist ), и если эта дистанция меньше общей суммы дистанций между узлами, то цель достижима, иначе нет. Если цель достижима, полный цикл ограничивается двумя этапами. На первом этапе, алгоритм оценивает начальную позицию каждого узла, начиная с конечного элемента p[n] двигаясь к базе манипулятора p . Таким образом, позволим целевой позиции быть позицией конечного узла, p"[n] = t . Получим прямую l , лежащую на точках p и p"[n] . Новая позиция узла с индексом n-1 , p" , лежит на этой линии на дистанции d от p"[n] . Аналогично, новая позиция узла с индексом n-2 , p" , может быть вычислена используя прямую l , лежащую на точках p и p" на дистанции d от p" . Алгоритм повторяется до тех пор, пока все не будут посчитаны новые позиции для всех узлов, включая конечный. В случаях, когда корневой элемент перемещается на необходимую позицию, FABRIK срабатывает как было описано, с тем лишь отличием, что новая позиция p"" корневого узла будет желаемой позицией, а не начальной.
После одной полной итерации, почти во всех случаях (по наблюдениям) конечный узел приблизится к цели. Процедура повторется необходимое количество раз, до тех пор, пока конечный узел не ляжет на позицию цели или не приблизится к ней на допустимую дистанцию. Реализация метода FABRIK без введения ограничителей сойдётся на любой целевой точке/цепи, если цель достижима. Однако, если цель находится дальше достанции, на которую может вытянуться цепь, необходимо прерывающее условие, которое сравнит прошлую и текущую позицию конечного узла, и которое прекратит выполнение алгоритма если смещение конечного узла будет меньше некоторого значения (эпсилона). Так-же, в особых случаях, алгоритм прерывается по истечению некоторого числа итераций (впрочем, пока-что такая ситуация не была встречена).
Для более быстрого результата и решения в несколько итераций, возможна оптимизация с применением Конформной Геометрической Алгебры (Conformal Geometric Algebra, далее CGA); CGA имеет преимущество на базовых фигурах, такие как сферы, прямые, плоскости и окружности, достаточно просто отображаемые алгебраическими обьектами. Поэтому, поиск позиции узла, находящегося между двумя известными узлами, может быть выражен пересечением двух сфер с центрами на соответствующих этим узлам позициям, и радиусом, равным расстоянию между позициям искомого узла и имеющимися; новая позиция узла будет лежать на ближайшей точке окружности, сформированной пересечением двух сфер. Другая простая оптимизация заключается в прямом построении прямой в направлении цели, когда последняя недоступна.

3. Модель с множеством конечных узлов


Как и в случае с одним конечным узлом, алгоритм разбивается на два этапа:
  • Первый этап точно такой-же, только на этот раз начинается от каждого конечного узла с движением внутрь по цепи от этого узла, вплоть до суб-базы (вероятно, суб-базой является узел с несколькими примыкающими к нему рёбрами - прим. перев.). Таким образом, получим столько разных позиций для суб-базы, сколько соединённых с ней конечных узлов у нас имеется. Итоговая же позиция может быть взята как центроид (тобиш, просто среднее арифметическое - прим. перев.) из этих позиций. После этого, выполнение алгоритма продолжается в нормальном режиме, двигаясь от суб-базы до корня. Если суб-базы имеют собственные суб-базы, то по отношению к ним производятся аналогичные действия - так-же составляется список возможных позиций, после чего эта суб-база устанавливается на центроид из всего списка позиций.
  • На втором этапе, обычный алгоритм применяется к каждому узлу, двигаясь всё дальше от корневого узла. При этом, каждая цепь должна быть обработана отдельно вплоть до конечного узла: чем больше суб-баз, тем больше повторений для каждой из них. Процесс повторяется до тех пор, пока конечные узлы не достигнут своей цели или пока не сработает условие прерывания.

4. Ограничители

Ну и наконец, самая вкусная часть этой статьи - рассчёты с применением ограничителей. Нужны они, как уже стоило догадаться, для большего сходства с реальными организмами. Сам же узел, обычно, характеризуется тремя степенями свободы. Вращение узла может быть характеризовано как «простое вращение» (2 степени свободы), которое отражает его конечную позицию, и вращение вокруг собственной оси (1 степень свободы). Таким образом, разделив передвижение узла на две такие фазы, и применив к ним ограничители, можно управлять положением узла. Сами же ограничения можно наложить подобным образом: т.к. алгоритм итеративный, можно применять ограничения вращений на каждой итерации алгоритма. Ограничители, при этом, не повлияют на сходимость алгоритма. Основная же идея применения ограничителей заключается в репозициионировании и переориентации узлов в пределах ограничений.
  • a - Начальные конфигурации манипулятора и цели.
  • b - Двигаем конечный узел p к цели и ориентируем его на неё.
  • c - Обнаруживаем позицию p" , лежащую на линии между позициями p" и p , на дистанции d от точки p" .
  • d - Переориентируем узел на позиции p" таким образом, чтобы он смотрел вдоль ребра, соединяющего p" и p" .
  • e - Вычисление ограничивающего эллипса: разрешённые позиции находятся в затенённом участке. Ни одна из вершин на этом этапе никуда не двигается.
  • f - Узел p перемещается на позицию p^ , который является ближайшей позицией на затенённом эллипсе, удостоверяясь таким образом в том, что новая позиция p^ будет лежать в допустимых пределах.
  • g - Двигаем узел p^ на точку p" , чтобы сохранить длинну ребра.
  • h - Переориентируем p" , чтобы удовлетворить ограниение ориентации.
Эта процедура повторяется для всех узлов, в прямом и обратном порядке, аналогично тому, как в варианте без ограничений осуществлялись перемещения. При этом, ограничение «эллипс», вероятно, является характеристикой ребра, а не узла, т.о. на второй фазе перемещаться на эллипс должен узел p - прим. перев.