Алгоритм Фезерстоуна
Алгоритм, вычисляющий динамику цепочки сочленённых тел за линейное время — и причина, по которой у некоторых рэгдоллов руки не отваливаются от плеч.
Рой Фезерстоун опубликовал Articulated Body Algorithm в 1983 году, имея в виду роботов-манипуляторов. Наивное решение для сочленённого тела строит и обращает матрицу масс, что стоит O(n³) по числу суставов; Фезерстоун получает тот же ответ за O(n), пройдя по цепочке туда и обратно. Тела описываются в редуцированных координатах — углами суставов, а не свободными положениями, — поэтому соединения по построению не могут разойтись.
Большинство игровых движков иначе симулирует рэгдоллы как свободные твёрдые тела, удерживаемые связями: это дёшево, но под нагрузкой «растягивается». Сочленения PhysX и btMultiBody в Bullet построены на алгоритме Фезерстоуна именно ради того, чтобы этого избежать.