Science, Faculty of
Computer Science, Department of
DSpace
UBCV
Kim, Nam Hee
Master of Science - MSc
University of British Columbia
Animated motions should be simple to direct while also being plausible. The work presented in this thesis develops a trajectory optimization system that takes as input a sequence of crudely-specified keyframes as motion sketches and produces a physically simulated, as-plausible-as-possible motion as output. We propose a novel control parameterization scheme for trajectory optimization, compactly incorporating keyframe timing, internal actions, and external assistive force modulations as auxiliary variables to realize desired motion sketches. Our method allows for emergent behaviours between keyframes, does not require advance knowledge of contacts or exact motion timing, supports the creation of physically-impossible motions, and allows for near-interactive motion creation. The use of a shooting method allows for the use of any black-box simulator. We present results for a variety of 2D and 3D motions, motion sketches that have sparse and dense keyframes, and both physically-feasible and physically-infeasible motions. We evaluate our control parameterization scheme against other recent methods that incorporate external assistive forces.
Directable Physics-BasedCharacter AnimationbyNam Hee KimB.Sc., e University of British Columbia, 2019A THESIS SUBMITTED IN PARTIAL FULFILLMENT OFTHE REQUIREMENTS FOR THE DEGREE OFMASTER OF SCIENCEinTHE FACULTY OF GRADUATE AND POSTDOCTORAL STUDIES(Computer Science)THE UNIVERSITY OF BRITISH COLUMBIA(Vancouver)April 2021© Nam Hee Kim, 2021e following individuals certify that they have read, and recommend to the Fac-ulty of Graduate and Postdoctoral Studies for acceptance, the thesis entitled:Directable Physics-Based Character Animationsubmied by Nam Hee Kim in partial fulllment of the requirements for thedegree of Master of Science in Computer Science.Examining Committee:Michiel van de Panne, Professor, Department of Computer Science, UBCSupervisorDinesh K. Pai, Professor, Department of Computer Science, UBCSupervisory Commiee MemberiiAbstractAnimated motions should be simple to direct while also being plausible. e workpresented in this thesis develops a trajectory optimization system that takes as in-put a sequence of crudely-specied keyframes as motion sketches and producesa physically simulated, as-plausible-as-possible motion as output. We propose anovel control parameterization scheme for trajectory optimization, compactly in-corporating keyframe timing, internal actions, and external assistive force mod-ulations as auxiliary variables to realize desired motion sketches. Our methodallows for emergent behaviours between keyframes, does not require advanceknowledge of contacts or exact motion timing, supports the creation of physically-impossible motions, and allows for near-interactive motion creation. e use ofa shooting method allows for the use of any black-box simulator. We present re-sults for a variety of 2D and 3D motions, motion sketches that have sparse anddense keyframes, and both physically-feasible and physically-infeasible motions.We evaluate our control parameterization scheme against other recent methodsthat incorporate external assistive forces.iiiLay SummaryTraditional character animation involves keyframing and interpolation, whichcombine to produce a movement according to the artist’s vision. Meanwhile,modern computer animation techniques such as physics simulation and numer-ical optimization have shown great promise towards producing expressive androbust character movements. However, current methods in character animationresearch do not cater to production-level scenarios where the artist’s sketchesare used as a blueprint for a character’s overall motions in a scene. In the workpresented in this thesis, we bridge the gap between physics-based character ani-mation and artist-directed animation workows by developing an intelligent in-terpolation system that leverages physics simulation and numerical optimization.Our method produces visually pleasing movements that track the artist’s inputkeyframes as closely as possible while also remaining as physically feasible aspossible.ivPrefaceChapters 4, 5, 6, and 7 are based on work conducted in UBC’s Motion Control andCharacter Animation Lab by Nam Hee Kim, Hung Yu (Ben) Ling, Zhaoming Xie,and Professor Michiel van de Panne. A version of this work was submied anony-mously to ACM SIGGRAPH 2021 [21]. As the rst author, I contributed holisti-cally to all aspects of this work, ranging from primitive experiments, data collec-tion, environment design, paper writing, and video material preparation. Morespecically for developing the system presented in this thesis, I explored primitivesolutions using external assistive forces, designed a derivative-free optimizationpipeline using CMA-ES, designed characters, generated various 2D and 3D ani-mation results, and improved the user interface. Hung Yu (Ben) Ling prototypedthe user interface, designed and evaluated the horizon curriculum method, andimproved the soware to achieve a signicant speedup in computation. Zhaom-ing Xie generated qualitative results and helped in writing the paper. Michiel vande Panne provided overall supervision and helped in writing the paper.vTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiLay Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viList of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiiList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ixList of Supplementary Material . . . . . . . . . . . . . . . . . . . . . . xiiiAcknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiv1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2 esis Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52.1 Character Animation . . . . . . . . . . . . . . . . . . . . . . . . . 52.2 Physics-based Character Animation . . . . . . . . . . . . . . . . . 72.3 Optimal Control . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82.3.1 State-Indexed Control . . . . . . . . . . . . . . . . . . . . 92.3.2 Time-Indexed Control . . . . . . . . . . . . . . . . . . . . 92.4 Trajectory Optimization Problem . . . . . . . . . . . . . . . . . . 102.4.1 Keyframing and Spacetime Constraints . . . . . . . . . . 112.4.2 So Constraints . . . . . . . . . . . . . . . . . . . . . . . 122.4.3 Action Regularization . . . . . . . . . . . . . . . . . . . . 122.5 Trajectory Optimization Solvers . . . . . . . . . . . . . . . . . . . 132.5.1 Gradient-Based Methods . . . . . . . . . . . . . . . . . . 132.5.2 Derivative-Free Methods . . . . . . . . . . . . . . . . . . 13vi2.6 Assistive Forces . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142.6.1 Root-Force-and-Torque . . . . . . . . . . . . . . . . . . . 152.6.2 Keypoint-Spring Model . . . . . . . . . . . . . . . . . . . 152.6.3 Modulation of Assistive Forces . . . . . . . . . . . . . . . 152.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183.1 Controllers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193.2 Trajectory Optimization . . . . . . . . . . . . . . . . . . . . . . . 194 Motion Sketch Optimization . . . . . . . . . . . . . . . . . . . . . . 224.1 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224.2 Shooting with Time-Anchored Action Pieces . . . . . . . . . . . . 234.3 External Assists with Springs and Dampers . . . . . . . . . . . . 244.4 Keyframe Timing . . . . . . . . . . . . . . . . . . . . . . . . . . . 254.5 Cost Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254.6 Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 264.7 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 275 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 295.1 Animated Characters . . . . . . . . . . . . . . . . . . . . . . . . . 295.2 Emergent Behaviors . . . . . . . . . . . . . . . . . . . . . . . . . 305.3 Impossible Motions . . . . . . . . . . . . . . . . . . . . . . . . . . 345.4 Contact-Rich Movements . . . . . . . . . . . . . . . . . . . . . . 345.5 3D Motions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 355.6 Table of Hyper-parameters . . . . . . . . . . . . . . . . . . . . . . 356 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 376.1 Importance of Compact Parameterization of Assistive Forces . . . 376.2 Trade-o: Keyframe Tracking and Assist Use . . . . . . . . . . . 416.3 Evaluation of Horizon Curriculum . . . . . . . . . . . . . . . . . 426.4 Sensitivity to Population Size . . . . . . . . . . . . . . . . . . . . 446.5 Do Assistive Forces Help? . . . . . . . . . . . . . . . . . . . . . . 456.6 Tracking Assist Over Time . . . . . . . . . . . . . . . . . . . . . . 466.7 User Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 476.8 Limitations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 477 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53viiList of Tables5.1 e table of hyper-parameters for the motions appearing in thispaper and the supplementary video. . . . . . . . . . . . . . . . . . 366.1 Evaluation of Horizon Curriculum. Each value shows the meanand standard deviation of ve independent optimization runs withdierent random seeds. e Time columns are the overall opti-mization wall-clock time in seconds. e Cost columns show thescaled (×10−2) objective function values when optimization iscompleted. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 436.2 Eects of CMA-ES population size on nal objective function val-ues. Time and cost are reported the same way as Table 6.1. . . . . 43viiiList of Figures1.1 A 3D character landing from a jump. . . . . . . . . . . . . . . . . 21.2 e work in this thesis enables capturing human intent as keyframesand incorporates them into physics-based character animation.Le : input keyframes sketchig a jumping motion of the Luxocharacter. Right: optimized motion where the Luxo characterclambers onto the box. . . . . . . . . . . . . . . . . . . . . . . . . 22.1 A diagram highlighting the distinctions among frame-by-frameanimation, kinematic interpolation, and actuated physics-basedanimation. Top: In frame-by-frame animation, artists meticu-lously produce the conguration for each frame to create the il-lusion of movement in both 2D and 3D seings. Middle: Kine-matic interpolation provides primitive automations by populatingintermediate poses based on sparser hand-craed input. Bottom:Physics-based character animation uses actuations to produce astate trajectory which is converted to visual artifacts. . . . . . . . 62.2 A simple control loop between a controller and a simulator inphysics-based character animation. e character controller ob-serves the state of the environment xt at timestep t and producesactuations ut, which is used by the simulator to animate the char-acter. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72.3 Top: state-indexed (closed-loop) control loop. Bottom: time-indexed (open-loop) control loop. . . . . . . . . . . . . . . . . . . 92.4 A visual explanation of time-indexed trajectory optimization. Le :three dierent trajectories with a shared initial state, visualizedas state sequences. Right: action sequences corresponding to thethree trajectories. Best viewed in colour. . . . . . . . . . . . . . . 10ix2.5 A visual explanation of trajectory optimization with spacetime con-straints. Le : three dierent trajectories that are subject to space-time equality constraints specied by keyframes shown as greypoints. Right: action sequences corresponding to the three tra-jectories. Best viewed in colour. . . . . . . . . . . . . . . . . . . . 112.6 An example usage of assistive force and torque applied at the Luxocharacter’s root, in conjunction with internal actuations. . . . . . 152.7 An illustration of the keypoint-spring model, which computes as-sistive forces based on the displacement between the referencestate and the current state of the character. . . . . . . . . . . . . . 164.1 A high-level overview of our optimization pipeline, the optimiza-tion parameters Φ, and their interpolation. ey correspond tothe per-timestep residual PD target ∆θt, assistive force modula-tion βt, and the keyframe timings, ∆tk. . . . . . . . . . . . . . . . 244.2 A diagram depicting the forward simulation procedure of our sys-tem, taking the current character state qt to the next state qt+1.Both joint actuation and external assistive forces are used to takea forward step. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274.3 An abstract view of our trajectory optimization setup. We uselinear interpolation to produce a reference trajectory based on theinput sequence of keyframe poses. We apply external assistiveforces to help the character track the reference trajectory. eoptimized motion is a consequence of minimizing the discrepancybetween the output trajectory and the input keyframes. . . . . . . 285.1 Representative gures of the animated characters. From le toright: Luxo2D, Desk2D, Folk2D, and Boxy. . . . . . . . . . . . . . . 305.2 An example of generating diverse motions from a single set ofsparse horizontal displacement keyframes. . . . . . . . . . . . . . 315.3 Folk2D walk cycle and vault motions specied with dense keyframes. 325.4 Examples of physically impossible keyframes and motions. . . . . 335.5 Our method can generate highly dynamic motions and 3D mo-tions. e lemost column shows the keyframes for each motion.e optimized trajectories are shown from le to right in each row. 336.1 Comparison of performance between global β and time-indexedβ. Each point represents a solution. Ideal solutions (small assist,small error) reside on the boom-le corner. . . . . . . . . . . . . 38x6.2 e “jump-hop” scenario where the character performs both easyand physically impossible motions. . . . . . . . . . . . . . . . . . 396.3 A side-by-side comparison of the character performing the “jump-hop” task (keyframes shown in Figure 6.2) according to dierentexternal assist parameters. Le : optimized with time-indexed βapproach. (d=47) Right: optimized with global β approach. (d=36) 406.4 e “high box jump” scenario requiring a signicant amount ofexternal assist to produce the desired motion. . . . . . . . . . . . 416.5 A side-by-side comparison of the character performing the “highbox jump” task (keyframes shown in Figure 6.4) according to dif-ferent external assist parameters. Le : optimized with Tβ ap-proach. (d=44) Right: optimized with RFT approach. (d=64) . . . 426.6 Comparison of performance across 7 dierent values of regular-ization strength λβ . Each point represents a solution. Ideal solu-tions (small assist, small error) reside on the boom-le corner. . 446.7 e “low box jump” scenario that is dicult but possible to pro-duce the desired motion without external assist. . . . . . . . . . . 456.8 A side-by-side comparison of the character performing the “lowbox jump” task (keyframes shown in Figure 6.7) according to dif-ferent regularization strengths. Le : optimized with λβ = 1e3.Right: optimized with λβ = 1e − 3. Note the emergent backipwhich helps the character stay on a physically-based trajectorybut completely ignores an intermediate keyframe. . . . . . . . . . 466.9 Comparison of optimized trajectories with and without assist dur-ing training. Training with assist yields a more stable trajectory,even with assistive forces disabled at run-time. Note the 6.9b tra-jectory performs a partial rotation and unstable landing. . . . . . 476.10 Evolution of assistive force usage during optimization, as mea-sured by the average β2t used throughout the motion. During theoptimization iterations, our system initially explores larger valuesof βt and then gradually decreases reliance on assistive force. . . 486.11 is example shows the amount of assistive forces used to performan impossible long jump by Folk. In the nal optimized motion,only a signicant amount of assist is used right before the ightphase. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49xi6.12 e full view of the control panel of our user interface. 1: keyframesare displayed as tabs that can be added and removed. 2: keyframecongurations, such as root position, orientation, joint angles,and keyframe weights can be manipulated with sliders and buonmodules. 3: CMA congurations are exposed to the user, includ-ing action lengths, time-to-arrival ranges, penalty weights, andcomputation budget parameters. 4: the user can display optimizedmotions as well as reference motions induced by input keyframes. 50xiiList of Supplementary Material1. Supplementary video: Motion Sketch Optimizaion(ACM SIGGRAPH 2021 anonymous submission video).xiiiAcknowledgementsI would not be where I am today without the unwavering support and trust frommy family, who made a lot of sacrice in order to help me pursue my studiesabroad for over a decade now. Although COVID-19 restrictions have put us evenfurther apart as of this writing, their thoughts and prayers for me are closer tomy heart than ever. Mom, Dad, Mee Gang, Tae Min, I miss you all.I would like to thank my colleagues and mentors at the Motion Control andCharacter Animation (MOCCA) Lab. My time at MOCCA taught me that genuinemoments of fun, curiosity, and laughter are signs of doing things right. Specialthanks go to Zhaoming Xie and Hung Yu (Ben) Ling, who collaborated with meon multiple projects and stayed very patient with me.I am forever indebted to my research supervisor Professor Michiel van dePanne. A fellow believer in wholeheartedness, Michiel taught me much more thanjust topics in computer science. I deeply appreciate every kind word of armationand encouragement Michiel gave me throughout my studies.I am thankful to my reviewer Professor Dinesh K. Pai for his insightful andkind comments on my work. I would also like to thank the anonymous SIG-GRAPH reviewers who helped improve the quality of the work presented in thisthesis.Finally, I would like to dedicate this work to my most wonderful wife Jenny–we married in August 2020, shortly before the conception of my thesis projectand aer 6 star-crossed years of dating across 5 cities, 3 countries, and 2 con-tinents. Jenny has been extremely supportive, empathetic, and accepting of methroughout the highs and lows during my studies, all while dealing with her ownstudies for her MSN program at UBC. Jenny also contributed to my work with herbeautiful artwork and helped create an amazing voiceover for the supplementaryvideo.xivChapter 1Introduction1.1 MotivationHow do we incorporate the human creator’s intent into a physics-based characteranimation workow? Computer animation has become a critical component ofdigital entertainment, comprising a wide array of applications in animated lms,video games, virtual and augmented reality (VR/AR), and more. As these applica-tions revolve around the interactions with and between virtual characters, makingcharacters move in believable and pleasant ways is an essential challenge for ev-ery animated environment. However, creating high-quality character movementsframe-by-frame is extremely dicult and hence calls for automation techniquesthat augment human creators’ capabilities. As such, modern character animationresearch studies a variety of automation techniques for bringing virtual charactersto life with minimal human intervention.Physics-based techniques are among the solutions that automate and regu-larize character movements to produce physically feasible motions. For instance,consider animating a complex character jumping and landing (Figure 1.1). istask can be labour-intensive if the user must manually animate physical eectssuch as contact, collision, and follow-through. Delegating this work to a physicsengine, on the other hand, can automate most of the laborious work and producevisually pleasing results at the cost of additional computation.In physics-based seings, character movements are driven by actuations, whichare forces generated by the articial motors or muscles equipped to the character.Intelligent synthesis of actuated character movements has been a long-standingand active research area in articial intelligence (AI). While signicant progress ismade on designing ecient learning algorithms for animating simulated charac-ters, the diculty in incorporating human directives into the animation processpresents a signicant boleneck in terms of the usability of these methods. Assuch, the adoption of actuated physics-based character animation is limited, de-spite its research history spanning over 30 years.Current state-of-the-art tools for user-directed character animation do notlearn actuated trajectories, require extensive reference motion data, or enableonly run-time controls such as game controller input. e particular transfor-1Figure 1.1: A 3D character landing from a jump.Figure 1.2: e work in this thesis enables capturing human intent as keyframesand incorporates them into physics-based character animation. Le : inputkeyframes sketchig a jumping motion of the Luxo character. Right: optimizedmotion where the Luxo character clambers onto the box.mation from crude input keyframes into plausible and emergent behaviours hasremained dicult, mainly due to the existing methods’ inability to relax the con-straints on physical feasibility. For example, the user may envision a characterperforming an impossibly high jumping motion while staying as physically plau-sible as possible. How do we allow for this in physics-based character anima-tion? Without further modications, searching for purely-physical motions willconstrain the trajectory optimization problem excessively. As such, user intentmust be completely compatible with physics, which signicantly limits expres-sivity. Moreover, trajectory optimization is subject to the well-known curse ofdimensionality, where the search space grows exponentially with respect to thedimensions of the parameters. Maintaining computational feasibility, therefore,requires an intentional control parameterization scheme that can compactly rep-2resent expressive motions.Making physics-based character animation directable is a nontrivial and mul-tifaceted challenge involving many design questions. How do we parse and rep-resent user intent? How do we connect user intent to the simulation? How dowe measure the goodness of the produced solution? What kind of techniques andmodications are necessary to ensure the feasibility of solutions, given a limitedcompute budget? In more than 30 years of computer animation research history,many approaches have emerged to answer these questions.1 In an aempt toaddress these questions, we oer our novel combination of well-established tech-niques borrowed from the rich character animation research history, includingkeyframing, spacetime constraints, the shooting method with black-box simula-tion, external assistive forces, and derivative-free optimization.In this thesis, we present a system that produces actuated trajectories thattrack sparse and crudely-specied keyframes. In so doing, the system is com-patible with traditional keyframe-based animation workows while incorporat-ing physical constraints and regularizations to oer benets beyond simple in-betweening techniques. Figure 1.2 showcases an example use case of our work,where the user’s directive is captured as keyframes.1.2 esis Overviewe work presented in this thesis explores the use of derivative-free trajectoryoptimization for incorporating user intent into a physics-based character anima-tion workow. Given an input sequence of keyframes, our method nds an as-physically-feasible-as-possible motion that tracks the keyframes while allowingfor external assistive forces. To this end, we propose a novel control parameter-ization scheme that leverages mass-spring forces and modulates the forces as aone-dimensional action along with character actuations.e rest of this thesis is structured as follows: in Chapter 2, we build a for-mal description of the problem of dynamic character animation, formulate a cor-responding trajectory optimization problem, and introduce sampling-based opti-mization strategies. In Chapter 3, we provide an overview of related work in char-acter animation and trajectory optimization. In Chapter 4, we detail our methodthat leverages modulated external assistive forces and simultaneously optimizesactions, assist modulations, and keyframe timing. In Chapter 5, we introducethe characters used in our experiments and show resulting animations,2 oering1Chapter 3 introduces related work in more detail.2Please refer to the supplementary video for animated results: https://sites.google.com/view/motion-sketch-optimization3comments on our system’s performance on various scenarios including emergentbehaviours, impossible motions, contact-rich movements, and 3D motions. InChapter 6, we analyze and discuss the importance of our contributions includingthe compact parameterization scheme, horizon curriculum, and external assistiveforces. Finally, in Chapter 7, we summarize our ndings and describe possibleavenues for future work.4Chapter 2BackgroundOur goal is to incorporate user intent into physics-based character animation tofacilitate motion design. In this section, we introduce core concepts pertaining tothis goal, assuming that the reader has minimal familiarity with character anima-tion and trajectory optimization. We rst oer a formal description of physics-based character animation as a control problem and introduce trajectory opti-mization as a framework for solving it. en we introduce relevant numericaloptimization methods that can output optimized trajectories.2.1 Character AnimationAn animation is a sequence of images presented in quick succession to create anillusion of movement. For this illusion of movement to occur, the consecutive im-ages should display spatial and temporal continuity. More formally, an animationis a playback of the sequence of T + 1 images3 I0...T = I0, I1, · · · , IT . Whilethese images are typically hand-craed in illustrated animation work (e.g. clas-sic Disney lms and Japanese anime), in computer animation, these images arerendered artifacts of underlying congurations of objects. Congurations are nu-merical entities that describe the necessary information for rendering an object’svisual state. For simplicity, we assume that a conguration and an image havea unique correspondence–hence, the same animation is adequately characterizedby the sequence of T + 1 congurations: q0...T = q0, q1, · · · , qT .Specically for character animation, a conguration describes the pose of thecharacter. In rigid body models, poses are characterized by two entities: (1) thespecications of the character’s body in its rest pose and (2) the deformation tothe rest pose at the given timesteps. Practically, pose deformation at timestep t isgiven in terms of the character’s displacement from the originχt as well as its jointangles θt. Given this, we use the terms pose and conguration interchangeably.For kinematic character animation, the pose sequence q0...T is manipulatedframe-by-frame by an animator, in such a way that a consecutive pair of poses3Instead of T , we use T + 1 to simply notation. is is especially convenient when the initialvalue, e.g. q0, is involved.5frame-by-framekinematic interpolationactuationFigure 2.1: A diagram highlighting the distinctions among frame-by-frame an-imation, kinematic interpolation, and actuated physics-based animation. Top:In frame-by-frame animation, artists meticulously produce the conguration foreach frame to create the illusion of movement in both 2D and 3D seings. Middle:Kinematic interpolation provides primitive automations by populating intermedi-ate poses based on sparser hand-craed input. Bottom: Physics-based characteranimation uses actuations to produce a state trajectory which is converted to vi-sual artifacts.6SimulatorControllerFigure 2.2: A simple control loop between a controller and a simulator in physics-based character animation. e character controller observes the state of the en-vironment xt at timestep t and produces actuations ut, which is used by the sim-ulator to animate the character.qt and qt+1 appears to be spatially and temporally continuous as part of a largertrajectory. e animated trajectories need to be physically sensible, i.e. observeeveryday physical phenomena (e.g. gravity, action-reaction, etc.). e classic 12Principles of Animation [44] further describes techniques to enhance the illusionof life in pose sequences.As creating and editing animations frame-by-frame is taxing, interpolationis oen used to reduce the workload. An animator can specify the character’scongurations corresponding to a few canonical frames (called keyframes) andinterpolate between them to automatically generate frames in between. However,the quality of interpolated animation depends heavily on the density and qualityof input keyframes as well as the timing of each keyframe.2.2 Physics-based Character AnimationFor physics-based character animation, the pose sequence q0...T is part of a statetrajectory of the simulated physical environment. In this case, simulated physicallaws govern the evolution of the state of the world over time (i.e. dynamics),including that of the character pose. When the dynamics completely governsthe movement of the character’s body, the body is merely a ragdoll, or a chainof links held together by the joints. On the contrary, in actuated animation, thecharacter’s joints are equipped with virtual motors, and these motors drive themovement of the character by generating forces (called actions or actuations) thatmove its chain of bodies. For example, a walking bipedal motion is a consequenceof applying appropriate torques to legs, arms, and torso, precisely coordinated inorder to propel the character’s body by pushing against the ground plane.Actions in actuated rigid body models are typically represented by the torquesapplied at the character’s joints, which generate rotational velocities that drive theevolution of joint angles. More formally, we introduce a sequence of T + 1 ac-7tions: u0...T = u0, u1, · · · , uT that govern the development of the state sequencex0...T = x0, x1, · · · , xT where a state xt captures the necessary information todescribe how applying the action ut and observing physical laws aect the evo-lution of the trajectory. is notion is oen represented by a forward dynamicsfunction F , which imposes an equality constraint xt+1 = F (xt, ut) on the statetrajectory x0...T . In the framework of the Markovian dynamics, states describethe pose and velocity of each object in the environment. In our case, at a giventimestep t, the character’s pose qt (root position and angles of joints), as well asthe velocity thereof q˙t (root velocity and rotational velocities of joints), constitutethe character’s state xt. e observed pose sequence q0...T is then the consequenceof the state trajectory x0...T .In summary, whereas kinematic character animation involves directly inter-acting with the pose sequence q0...T , physics-based character animation involvescontrolling the character and inuencing the pose sequence as a result. Figure 2.1summarizes the dierence across the three approaches introduced so far. Physics-based character animation hence introduces a trade-o between interactabilityand automation: spatial and temporal continuity is automatically incorporated aseach state is a direct consequence of the previous state, but one can no longerdirectly manipulate the character’s congurations. e task at hand is then tond the action sequence u0...T that drives the character’s state trajectory x0...T incompliance with the forward dynamics of the environment F and that satisesthe animator’s intent. We have thus characterized the physics-based characteranimation as an instance of the control problem.2.3 Optimal ControlOptimal control methods provide a numerical framework for solving the controlproblem for physics-based character animation. Namely, one may associate a costfunction with respect to the trajectory resulting from applying an action sequence.Conventionally, the cost function takes the form:J(x0...T , u0...T ) =T∑t=0l(xt, ut) (2.1)where l(xt, ut) is a generic loss function associated with state xt and action ut attimestep t. Here, we will assume that the cost function is separable by timestep,although that is not always the case. e construction of cost function J is an im-portant design question: intuitively, the character’s state trajectory should followthe user’s intent, and the actions should be well-behaved. Given a well-speciedcost, the optimized trajectory that minimizes the cost will achieve the desired8Controller SimulatorOptimizer SimulatorFigure 2.3: Top: state-indexed (closed-loop) control loop. Bottom: time-indexed(open-loop) control loop.properties, while an ill-specied cost may produce undesired results. Approachesto optimal control can be broadly categorized into state-indexed control and time-indexed control, which are described next, as well as in Figure 2.3.2.3.1 State-Indexed ControlIn state-indexed control, also known as closed-loop control, action is a function ofstate. e controller generates each action ut based on the input state xt, and inmany cases, the system is considered homogeneous and thus the timestep t is notconsidered as an explicit input. State-indexed control involves a policy functionthat maps states to actions, i.e.ut = pi(xt) (2.2)where pi : X → U is a learned policy that computes appropriate actions for thecharacter’s state at any given time. e main objective of state-indexed controlis then to nd the function pi that minimizes the specied cost. Reinforcementlearning is a framework for state-indexed control that uses machine learning tond the policy pi. e main advantage of state-indexed control is its expressivityand the ability to react to physical perturbations, independent of time-index.2.3.2 Time-Indexed ControlIn time-indexed control, also known as open-loop control, action is a function oftime. e actions u0...T are generated without explicitly referencing the state ofthe character at each timestep. In this case, the main objective is to nd the actionsequence u0...T ∈ UT+1 that minimizes the specied cost.9state space timeactionFigure 2.4: A visual explanation of time-indexed trajectory optimization. Le :three dierent trajectories with a shared initial state, visualized as state sequences.Right: action sequences corresponding to the three trajectories. Best viewed incolour.2.4 Trajectory Optimization ProblemGiven the optimal control framework for solving physics-based character anima-tion, let us further shape the optimization problem. Given that our goal is toachieve user-directed physics-based character animation, the optimization prob-lem should incorporate both simulation and user intent. Introducing physicalsimulation into the optimization is a maer of imposing the aforementioned for-ward dynamics equality constraint xt+1 = F (xt, ut) on the space of trajectories.Figure 2.4 presents a visual explanation of this search problem. More formally,the optimization problem now takes the form:minimize J(x0...T , u0...T ) =T∑t=0l(xt, ut) (2.3)subject toxt+1 = F (xt, ut)e free parameters of this optimization problem can be actions u0...T (calledshooting) or both states x0...T and actions u0...T (called collocation). Dependingon whether we formulate the problem as shooting or collocation, dierent strate-gies become viable for physics-based character animation. e involvement of theforward dynamics function F also gives rise to dierent design choices, such aswhether to use simulation to abstract away dynamics (called black-box dynamics)or to incorporate closed-form dynamics. In this work, we will be searching over10state space timeactionFigure 2.5: A visual explanation of trajectory optimization with spacetime con-straints. Le : three dierent trajectories that are subject to spacetime equalityconstraints specied by keyframes shown as grey points. Right: action sequencescorresponding to the three trajectories. Best viewed in colour.the space of actions by combining fast physics simulation and sampling, hence wewill be exclusively describing black-box shooting methods. For further details onthe design choices associated with trajectory optimization, please refer to [20].2.4.1 Keyframing and Spacetime ConstraintsEquation 2.3 incorporates control and dynamics into the optimization problem.We will now bring user intent into the picture. In this work, user intent is primar-ily specied in the form of keyframes. Keyframes are user-craed congurationsof the character that the animated output is to display at some point. For example,the user may specify a keyframe showing the Luxo character hanging mid-air tocapture an intent to make the character jump.Incorporating keyframes into physics-based character animation is a long-studied problem, inaugurated by Witkin and Kass’s seminal work on spacetimeconstraints [48]. Simply put, spacetime constraints are additional equality con-straints introduced to the optimization problem based on keyframes. Figure 2.5illustrates this modied trajectory optimization problem by including keyframesinto the state space. More formally, suppose that the user denesK+1 keyframesxˆ0...K = xˆ0, xˆ1, · · · , xˆK , sketching out the intended poses of the character overtime. ese keyframes are typically to be satised at input keyframe timing,which we express as a sequence of integer-valued timesteps t0, t1, · · · , tK . erst and last keyframes are treated as boundary constraints, meaning the initialstate x0 = xˆ0 and the nal state xT = xˆK . Equivalently, the rst and last timingsare always t0 = 0 and tK = T . With the spacetime constraints, the optimization11problem then takes the form:minimize J(x0...T , u0...T ) =T∑t=0l(xt, ut) (2.4)subject toxt+1 = F (xt, ut)xtk = xˆk for k ∈ 0, 1, · · · ,K.2.4.2 So ConstraintsIn our approach thus far, one of the main drawbacks is that the input keyframes,aside from the initial state, are not guaranteed to be satisable. e user is giventhe freedom to sketch desired motions without considering complex physical con-straints, and to this end, we convert the spacetime constraints into so constraintsby incorporating regularization terms into the cost function. More formally, werestructure the cost function J such that the minimization of J includes the errorbetween keyframes and states visited at corresponding points in time, i.e.minimize J(x0...T , u0...T ) =T∑t=0l(xt, ut) + λK∑k=0||xtk − xˆk|| (2.5)subject toxt+1 = F (xt, ut).e second term of J is the keyframe error, which corresponds to the equal-ity constraint xtk = xˆk in Equation 2.4, and λ is the regularization weight thatcontrols the priority given to minimizing the keyframe error.2.4.3 Action RegularizationAs alluded in Section 2.3, the design of the per-timestep loss function l(xt, ut)plays a critical role in trajectory optimization. In our case, our goal of trackingkeyframes is expressed as a so spacetime constraint, and the per-timestep loss lwill capture secondary desiderata that pertain to nding feasible actions and gen-erating visually plausible results. To this end, we introduce action regularizationas a component of l, which penalizes for actions that require high control eort.Assuming that the magnitude of an action ut is proportional to the amount ofcontrol eort required, incorporating the magnitude of ut, e.g.l(xt, ut) = ||ut||2 (2.6)12and minimizing the sum of l(xt, ut) over the horizon of T timesteps will con-strain the solutions towards smaller actions.2.5 Trajectory Optimization SolversGiven the trajectory optimization problem with spacetime constraints in Equa-tion 2.4, an optimization strategy is now required to produce optimized motions.Assuming that such a strategy can reliably return an optimal control u∗0...T =u∗0, u∗1, · · · , u∗T that minimizes the cost function J , the desired trajectory is recon-structed by forward-simulating from x0 = xˆ0 and computing xt+1 = F (xt, u∗t )for t = 0, 1, · · · , T .2.5.1 Gradient-Based MethodsSome of the most popular strategies for trajectory optimization using collocationinclude non-linear programming solvers (e.g. IPOPT [46], SNOPT [9]), whichtreat Equation 2.4 as constrained optimization with non-linear constraints. eseapproaches, however, require contact and collision information to be known inadvance, perform poorly on non-convex cost landscapes, and are complex to im-plement. Alternatively, state-indexed controller learning methods such as model-based reinforcement learning are also widely used. In this work, however, weemploy time-indexed trajectory optimization with derivative-free and sampling-based strategies in favour of fast convergence, ease of implementation, support ofblack-box dynamics, and robustness to non-convexity and motion discontinuities.2.5.2 Derivative-Free MethodsDerivative-free methods, as the name suggests, do not require an explicit compu-tation of gradients. Within derivative-free optimization techniques, we focus onsampling-based methods, which rely on sampling candidate solutions and evalu-ating each solution against the cost function. To handle the constraints, we ab-stract away the dynamics using simulation and use so constraints as in Equa-tion 2.5. In our case, the space of length-T + 1 action sequences is searched. Apopular application of sampling-based methods in online trajectory optimization,i.e. trajectory optimization performed at run-time, is model predictive control(MPC). In MPC, the optimal control u∗0...T is learned but only the rst action u∗0 isused for the particular timestep. In this work, the entirety of u∗0...T is used withoutre-optimizing at each timestep.13Cross-Entropy Methode cross-entropy method (CEM) is an adaptive importance sampling procedure,originally proposed by Rubinstein and Davidson [41]. CEM can be viewed as aniterative evolution strategy that repeats a quartet procedure of sampling, evalua-tion, ltering, and density estimation to evolve the sampler towards the vicinity ofa local minimum in the cost landscape. An elegant description of CEM is providedin [36], a modied version of which is replicated in Algorithm 1.Algorithm 1: Cross Entropy Method (CEM) for Trajectory Optimiza-tion1 Parameters:2 N : number of samples; K : size of elite-set;3 σinit: initial standard deviation; C : number of iterations;4 J : dimension of action; T + 1: number of timesteps;5 µ← zeros in RJ×(T+1) ;6 σ← constant vector in RJ×(T+1) with values σinit;7 for i = 1, 2, · · · , C do8 samples← N samples from N(µ, diag(σ2));9 costs← cost function f(x) for x in samples;10 elite-set← best K samples according to costs;11 µ, σ← t Gaussian distribution to elite-set;12 end13 return u∗0...T ← µCovariance Matrix Adaptation with Evolution StrategyCovariance matrix adaption with evolution strategy (CMA-ES) [17] is similar toCEM in that sampling, evaluation, ltering, and density estimation are used toevolve the sampler towards a local minimum. While CEM uses independent Gaus-sian distribution along each parameter (hence a diagonal covariance matrix), CMA-ES updates the full covariance matrix at each iteration and involves more sophis-ticated updates for the sampler due to the explicit selection and recombinationsteps. e algorithmic details are provided in [15].2.6 Assistive ForcesWithin the physically simulated environment, one can programmatically exertexternal forces onto objects without explicit collision. Assistive forces are external14Figure 2.6: An example usage of assistive force and torque applied at the Luxocharacter’s root, in conjunction with internal actuations.forces introduced to help the character perform the given task. For example, ifwe want the character to stand upright, we may introduce a force pulling thecharacter by its head. e use of external assistive forces is a well-establishedtrick in physics-based character animation.2.6.1 Root-Force-and-TorqueA simple and straightforward approach to implementing assistive forces is tonudge the character’s root with a force and a torque to help achieve a desired mo-tion. Figure 2.6 shows Luxo standing upright by combining internal actuations utalong with root-force fext and root-torque τext.2.6.2 Keypoint-Spring ModelWhile the root-force-and-torque approach provides a simple implementation ofassistive forces, in the presence of reference motion, we can introduce a morestructured way to guide the character’s motion via external forces. Figure 2.7demonstrates a keypoint-spring model approach to generate an array of externalforces at each timestep, based on the displacement between the reference stateand the current state of the character.2.6.3 Modulation of Assistive Forcese fundamental trade-o between the complexity of external forces and thetractability of optimization calls for a critical question: how do we compactly pa-rameterize external forces? For example, to nd the optimal root force and roottorque, we may treat fext and τext as free parameters to be optimized along withinternal actuations, and apply the learned force and torque constantly across all15Figure 2.7: An illustration of the keypoint-spring model, which computes assistiveforces based on the displacement between the reference state and the current stateof the character.timesteps. However, complex tasks will likely need a variation of the forces overtime and therefore the constant fext and τext values may not provide enough help.On the other hand, learning the root-force and root-torque per timestep, i.e. fext,tand τext,t may be appropriate for complex tasks, but this increases the dimension-ality of parameters, which can make optimization less tractable.Given a structured computation of external forces like the keypoint-springmodel introduced in Section 2.6.2, we may utilize a modulation-based approach.Intuitively, if we have reference motion and determine the array of external forcesbased on displacements, we do not need to learn to generate forces from scratchlike the previous approaches. We can instead learn how much the charactershould rely on the external forces at each timestep, i.e. learn to modulate. Moreformally, we can introduce a scalar parameter per timestep, i.e. βt ∈ [0, 1], whereβ = 0 signies no reliance and β = 1 signies maximum reliance on the exter-nal assist. is introduces fewer parameters while allowing for more expressivepaerns of external assists, achieving a compact parameterization that is bothsuciently complex and computationally tractable.162.7 Summaryus far, we have introduced the prerequisite concepts for developing an opti-mization system that incorporates keyframes into physics-based character anima-tion workow. We formulated this problem as a time-indexed control problem,namely trajectory optimization with so spacetime constraints, and proposed touse derivative-free optimization and incorporate external assistive forces to solvethe control problem. In the following chapters, we will rst review related workin the eld of motion control and trajectory optimization. en, we present ourMotion Sketch Optimization method, which utilizes CMA-ES and assistive forces,along with various technical adjustments to achieve our goal.17Chapter 3Related Worke generation of movement is commonly cast as an optimization problem, in-volving the known physics, the applied control actions, and an objective functionfor the motion. One possible solution involves computing a controller or controlpolicy, which computes the control actions as a function of the state and thereforecan dynamically react to changes in the environment. An alternative approach isto perform trajectory optimization, which computes the best motion trajectoryforward from a xed initial state, typically for some xed time horizon. Whilewe review related work for both of these approaches, we emphasize trajectoryoptimization methods as our work belongs to this laer category.Motion generation methods can be classied according to many aributes.Physics can be treated as a hard constraint, or as a so constraint. Relatedly, ex-ternal helper forces can be allowed (or not), either as a temporary measure duringoptimization or also as part of the nal motion. e motions can be passive andreactive, where the applied control exhibits no anticipation, or active, where thecontrol exhibits anticipation and planning. e equations of motion that imple-ment the physics can be fully accessible, allowing for analytic dierentiation, canbe approximated using models, or can be treated in a black-box manner. Con-tacts and their related discontinuities can be problematic for many optimizationmethods which can be addressed in various ways. e contacts and their tim-ing can be pre-specied as constraints, they can be smoothed over time to makethem dierentiable, they can be smoothly introduced via continuation methods,or they can be treated as a black-box phenomena. Motions can be authored viaabstract objectives, e.g. move the center of mass to the right at a given height, ormore concretely via keyframe poses and keyframe timing. e optimization canbe strictly gradient-based, making the solution more prone to local minima, orcan explicitly leverage stochastic exploration to facilitate the discovery of a vari-ety of emergent behaviors. e optimization can be carried out using simplieddynamics, e.g. physics-based motion of the main body, or using the full dynam-ics. Lastly, the optimization can be an oine process, a real-time online process,or something in between. is is critical, as it determines how an animator caniterate with the system.183.1 ControllersControllers for physics-based motions are oen authored with the help of mo-tion capture data, which can be treated as an imitation objective. is has a longhistory in many reference-motion tracking controllers, and has recently seen sig-nicant adoption in deep reinforcement learning (RL) based approaches. Learnedcontrol policies can either be specic to a given reference motion [34, 35] or beconditioned on a near-future window of the upcoming reference motion [5, 7, 33,49]. Motion control trained on motion capture data can also be abstracted intolearned latent variable representations which can then be reused in new wayseven in the absence of an input reference motion, e.g., [29]. ere has been lilework that shows how keyframes can be used to directly author controllers, al-though various approaches can be made to imitate suitably-keyframed motions.Human coaching hints can also be leveraged [10]. Training deep RL controllers toproduce high-quality motions based on non-imitation objectives takes extra careand aention, e.g. using a curriculum that may use external assistance duringtraining, e.g. [45, 51].e use of moderate external assistance has been explored in the design ofmotion-tracking controllers, with these having the benet of not requiring anyoine learning and being readily adaptable to new motions. World-space jointcontrol, together with moderate external torque control of the root link is intro-duced in [50], and is shown to provide surprisingly reasonable adaptations to newcircumstances such as terrain changes during locomotion. A related approach isdemonstrated for use in lm production [6]. e general approach of allowing fora degree of external assistance is made more adaptable in [23], where a quadraticprogramming problem is solved at every timestep in order to allow for beer re-sponse and local anticipation of the next frame of the reference motion. Roboticscontrollers can also be designed to leverage external assistance as needed [27].e perceptual impact of physics violations has been explored in some detail foranimation, e.g., [4, 40].3.2 Trajectory OptimizationSince the original work on spacetime constraints [48], a rich variation of methodshave been proposed towards making trajectory optimization approaches moreexible and practical. e complexities to be overcome are manifold: handlingof contacts and contact timing, access to equations of motion vs. black-box sim-ulation, scalability to full-body dynamics; complex optimization landscapes, andfragile behavior in the face of ill-posed or infeasible problems. Multiple eorts19introduce the use of simplied models to produce a beer-conditioned, simplerproblem, e.g., [19, 22, 24, 32]. is is most oen based on a centroidal dynamicsmodel, where the movement can be well-characterized at any point in time bythe center of mass position, an overall orientation, and the total linear and angu-lar momentum. Contact timings are oen assumed to be known in advance, areoptimized as a separate phase, or are introduced with a motion-phase structure.Simplied models can also be leveraged in editing motion capture data via mo-mentum and force edits [42]. is leverages a trajectory optimization techniquebased on normalized dynamics and knowledge of contacts and inverse dynamics.A related model is the PhysIK system [38], which allows for physically-plausiblekeyframing by extending inverse kinematics-based keyframes to include center-of-mass and intertia handles in a 2D seing. e keyframes fully specify the con-tact congurations and there is no optimization involved.Trajectory optimization methods that have access to the equations of motionand derivatives have the opportunity to be uniquely ecient, although they needto circumvent the challenges posed by contact discontinuities. One approach isto have a derivative-free outer loop optimization that denes the contact modes,wrapped around an inner-loop trajectory optimization using the now-known con-tact structure [47]. An alternate treatment of the hybrid contact optimizationproblem uses sequential quadratic programming and includes contact forces asoptimization parameters [37]. Intermediate optimization phases that relax theconstraints are found to be important for avoiding problematic local minima. Tra-jectory optimization through contact discontinuities can be tackled using numer-ical dierentiation and smoothed contact dynamics, with further measures takento achieve greater computational eciency [14]. is method can adjust foot-step contacts and timings, and is demonstrated in the context of tracking existingreference motions. Short-horizon trajectory optimization problems are shown tobe solved at near-interactive rates using an iterative linear quadratic Gaussian(iLQG) method [43], together with nite-dierence derivatives, suitable contactapproximations, and update regularization. Solutions to trajectory optimizationfor multi-contact seings continue to improve with dedicated packages such asCrocoddyl [28] for humanoid robotics.Forward dynamics simulations oer an alternative approach to trajectory op-timization, via shooting methods. ey can leverage black-box simulations andcan avoid many of the issues related to discontinuities, as long as they can be sim-ulated. Sample-based solutions for contact-rich motions have been shown to be afeasible solution for motion-capture imitation tasks [26] and online short-horizontrajectory optimization solutions for tasks dened by locomotion and balance ob-jectives [11, 39]. Derivative-free optimization methods such as covariance-matrixadaptation (CMA) have been used oine to compute optimized motion trajecto-20ries for a variety of highly dynamic motions, e.g., [2, 3]. It is further possible tooptimize for a diverse range of motions for given tasks [1]. Many of the issuesrelated to derivative-free motion optimization methods are documented in therelated works cited above, as well as elsewhere [30].Our work is one of few to span the spectrum of keyframe-based motions, fromphysically-feasible to physically-infeasible. is is enabled by the particular formof relaxation of the physics contraints that we use, as achieved by a point-to-point correspondence-based pull towards the possibly-crude reference trajectory,which can be modulated over time, and over solution iterations, by the optimiza-tion procedure itself.21Chapter 4Motion Sketch Optimizatione core components of our proposed method are: (1) the use of external as-sist realized via forces that pull a character towards its corresponding keyframe-interpolated pose; (2) a framework that simultaneously optimizes actions, externalassist modulations, and keyframe timing; and (3) a cost function that expressesso constraints with respect to the importance of each keyframe and that reg-ularizes actions, external assist used, and keyframe timing. Figure 4.1 providesa high-level overview of our system, including the simulation, the optimization,and the free parameters of the optimization. Figure 4.2 shows how the externalforces are integrated into the simulation.4.1 NotationIn this section, we describe our method in a 2D seing to keep the notation com-pact. However, our system implements the straightforward 3D generalization ofthe method.We begin with a rigid-body character equipped with J joints. In 2D seings,J is equal to the size of the character’s action space, since all joints must onlyrotate along a single axis. To animate this character, the user denes a sequenceof K + 1 keyframes4 qˆ = {qˆ0, qˆ1, · · · , qˆK} that roughly sketches the desiredcharacter poses over time. A pose q ∈ Q = RJ+2+1 consists of the global positionx ∈ R2, orientation ψ ∈ [−pi, pi), and joint angles θ ∈ RJ . Note that jointvelocities are not included in the keyframe denition.As usual with trajectory optimization using spacetime constraints, the taskof our system is to output a trajectory q = {q0, q1, · · · , qT } over the horizon ofT + 1 timesteps, such that the sequence of input keyframes qˆ is realized over thecourse of the trajectory.In spacetime constraint seings, the timing of each keyframe can be specied;for example, one can specify for keyframe qˆk to be realized at timestep tk, suchthat the output trajectory satises qtk = qˆk. We assume that keyframes also4We elect to use K + 1 instead of K to simplify notation. Similarly, our horizon is T + 1 stepsinstead of T steps.22describe the desired start and end states, meaning q0 = qˆ0 and qT = qˆK .A linearly-interpolated trajectory qˆ0,1,··· ,T = {qˆ0, qˆ1, · · · , qˆT } given speci-ed keyframes will have qˆtk = qˆk as required andqˆt =(tk+1 − t)qˆtk + (t− tk)qˆtk+1tk+1 − tk (4.1)for tk < t < tk+1. Figure 4.1 illustrates this interpolation strategy.To make the motion look physically plausible, an animator oen needs tospend signicant eort designing a dense set of keyframes carefully. Instead ofcraing a dense set of high-quality keyframes, trajectory optimization can be usedto generate physically feasible trajectory:minimize J(Q,U) =T∑t=0l(qt, ut)subject to qt+1, q˙t+1 = f(qt, ut, q˙t)qtk = qk for k ∈ 0, 1, · · · ,Kq˙0 = 0where u ∈ U is the actuation from the set of actuators aached on the joints of thecharacters, l : Q×U → R is a user dened cost function and f : Q× TQ×U →Q× TQ describes the physical laws the characters will follow to evolve the state.Keyframe timing can also be optimized by introducing tk as decision variables.4.2 Shooting with Time-Anchored Action PiecesWe use a derivative-free optimization method based on shooting. e internalactions, ∆θt, form a key part of the optimization, and consists of values for eachjoint, sampled at regular time intervals, δt, for a total of na = 1 + Tδt values perjoint. ese are then linearly interpolated to yield a continuous function ∆θ(t), asshown in Figure 4.1. We use position-derivative (PD) control to compute internalactuation torques for the character. e actions, ∆θt ∈ [−pi, pi)J then specifyresidual PD target angles. At each timestep t, torques are computed asτt = kAp (θˆt + ∆θt − θt)− kAd θ˙t, (4.2)where kAp and kAd are joint PD gains for the PD controller and θ and θ˙ are the jointangles and joint velocities of the simulated character.23Figure 4.1: A high-level overview of our optimization pipeline, the optimizationparameters Φ, and their interpolation. ey correspond to the per-timestep resid-ual PD target ∆θt, assistive force modulation βt, and the keyframe timings, ∆tk.4.3 External Assists with Springs and DampersWe introduce keypoints to our characters. A keypoint is a point in the character’sbody parts (usually at the center of mass of a constituent link) with a spring-damper pair aached such that an amount of pushing/pulling force is appliedat each simulation timestep. is external force is proportional to the distancebetween the current position and the reference position of the keypoint in worldCartesian coordinates. With the assistive forces applied to its keypoints, a charac-ter can be animated without any internal actuation like a ragdoll, loosely trackingthe linearly interpolated reference trajectory.More formally, we use a set of N keypoint positions, depending on the char-acter, [p0, p1, · · · , pN−1] where pi ∈ R2. ese can be computed from a pose qvia forward kinematics. e external force fi,t ∈ R2 for keypoint i at timestep t iscomputed as a result of simulating a spring-damper system based on the distancebetween reference keypoint position pˆi,t ∈ R2 and current keypoint positionpi,t ∈ R2:fi,t = kLp (pˆi,t − pi,t)− kLd p˙i,t, (4.3)where kLp and kLd are linear spring and damper stiness coecients respectively.ese constants are set proportional to the mass of the link the keypoint belongsto in order to prevent uneven momentum from toppling the character or causing24unnecessary spring oscillations. During each timestep, we compute the spring-damper force for each keypoint of the character and apply all of the external forcesft ∈ R2N together, along with joint torques τt ∈ RJ of the character. We notethat using only linear springs may be subject to degenerate cases when it comesto ambiguous rotations of body parts. However, using residual PD target anglessuch as in Section 4.2 takes body rotations into account, which in practice preventssuch degeneracy.We introduce a scalar βt ∈ [0, 1], the assistive force coecient that modulatesthe magnitude of the assistive forces as a form of action. Similar to actions, theyare anchored in time and we optimize for β = [β0, βδt , · · · , β(na−1)δt ], whereβt is piecewise constant for each corresponding time interval, δt, as shown inFigure 4.1.4.4 Keyframe TimingIt is oen dicult and tedious to dene the exact timing for every keyframe, as isrequired by spacetime constraint methods. In our framework, keyframe timingsare optional parameters which can either be dened by the artist or optimized bythe system. Our method automatically nds the most suitable keyframe timingfor a given interval if it is not specied.More formally, we introduce variables ∆t = [∆t1,∆t2, · · · ,∆tK ] where werefer to each entry ∆tk as the time-to-arrival. ese time-to-arrival values rep-resent the time between the k − 1th and kth keyframes, i.e. tk = tk−1 + ∆tk.e rst keyframe timing is dened to be t0 = 0 and we set the character’s ini-tial pose to match the rst keyframe. By default, the user can provide lower andupper bounds for ∆tk to limit the search space. When designing more delicatekeyframe motions, the user can optionally provide a precise time-to-arrival valuefor each individual keyframe interval.4.5 Cost FunctionOur trajectory optimization problem is set up to allow for exible motions basedon a sparse set of keyframes that act as so spacetime constraints. at is, insteadof explicitly constraining the solution set, we use weighted keyframe errors topenalize for actions that deviate character trajectory from the input keyframes qˆ.We also introduce penalty terms associated with parameters to achieve the fol-lowing desiderata: rst, excessive assists should be avoided to prevent completelynon-physical motions; next, character action should have moderate magnitude25lest the resulting action might be unnatural; nally, excessively loose keyframetiming should be avoided.More formally, we associate weight wk ∈ [0, 1] for every keyframe such thatthe importance of each keyframe can be taken into account. For example, the usermay wish to set the rst keyframe’s weight w0 to 0, given that q0 = qˆ0 is alwaystrue since we initialize our character at the rst keyframe. Our free variables forthe optimization are Φ = {∆θ,β,∆t} and the nal cost function expressing theaforementioned desiderata is wrien as follows:J(Φ) = J(∆θ,β,∆t) =K∑k=0wk||qˆk − qtk ||2+ λβT∑t=0||βt||2+ λ∆θT∑t=0||∆θt||2+ λ∆tK∑k=1||∆tk||2 (4.4)e rst term is the keyframe error. e second term regularizes the externalassist. e third term regularizes large actions so as to discourage rapid change.Finally, the last term regularizes the keyframe timing. λβ , λ∆θ , and λ∆t are non-negative penalty weights corresponding to the regularization terms.4.6 OptimizationWe use a derivative-free continuous optimization method, covariance matrix adap-tation (CMA-ES). To facilitate a more interactive motion design process, we fur-ther introduce a horizon-based curriculum. is allows for immediate displayof initial results, with updates being shown as the optimization proceeds. In thiscurriculum, the trajectory optimization is performed in stages with growing num-ber of keyframes. e rst stage consists of the initial and the second keyframe,i.e. the rst keyframe interval. e physics simulation is terminated when thetiming corresponding to the second keyframe has been reached. At this point,the rst optimized motion segment is ready to be displayed to the user.e curriculum advances to the next stage when the CMA-ES variance dropsbelow a predened threshold. e threshold is a hyper-parameter which we setto be one-fourth of the initial variance in all of our experiments. Intuitively, once26Figure 4.2: A diagram depicting the forward simulation procedure of our system,taking the current character state qt to the next state qt+1. Both joint actuationand external assistive forces are used to take a forward step.the variance converges to a small value, it is unlikely to discover a signicantlybeer motion in the current optimization round. In the new curriculum stage,we set the optimization parameters associated with the previous stages to have alower variance. is is to ensure that the optimizer builds on top of the existingsolution found in the previous stage. e entire optimization process is completedwhen the nal keyframe is covered by the curriculum.4.7 ImplementationWe use PyBullet [8] to simulate the physical interactions between the charac-ters and the environment. e exible programming interface of PyBullet allowscharacter keyframes to be dynamically added and removed at run-time. We alsodesigned a simple graphical user interface which allows artists to quickly adjustkeyframes and trajectory optimization parameters. Section 6.7 discusses the fea-tures of this interface in more details. We use a publicly available implementationof CMA-ES [15, 16] for optimization.27Figure 4.3: An abstract view of our trajectory optimization setup. We use linearinterpolation to produce a reference trajectory based on the input sequence ofkeyframe poses. We apply external assistive forces to help the character track thereference trajectory. e optimized motion is a consequence of minimizing thediscrepancy between the output trajectory and the input keyframes.28Chapter 5ResultsIn this section, we present a selected set of keyframes and resulting motions inorder to demonstrate emergent behaviors, both physical and infeasible motions,and contact-rich movements. Please refer to the supplementary video5 for visualdemonstrations of the optimized motions described in this section, as well as ad-ditional trajectories.5.1 Animated CharactersWe prepare four rigid-body characters to demonstrate the robustness and capacityof the optimized motions. Our method generalizes across 2D and 3D characters.In this section, we describe three 2D characters and one 3D character. eir rep-resentative gures are shown in Figure 5.1.Luxo2De classic 2D Luxo is a 6-DoF character equipped with neck, hip, and knee joints.e primary locomotion mode for the Luxo character is hopping.Desk2De desk character is a biped with a wide base of support capable of sidewayscrab-like jumps and locomotion.Folk2De 2D humanoid character is equipped with the typical number of joints as 3Dhumanoid seings, with all rotations constrained to the sagial plane, hence onlyusing y-axis rotation.5https://sites.google.com/view/motion-sketch-optimization29Figure 5.1: Representative gures of the animated characters. From le to right:Luxo2D, Desk2D, Folk2D, and Boxy.Boxy: A 3D BipedBoxy is a simplied 3D humanoid biped character with a cubic torso. We constrainthe motion of all limb joints to the sagial plane, while allowing for abdominalrotation into both the sagial and the horizontal planes.5.2 Emergent BehaviorsGiven crude and sparse keyframes, our trajectory optimization method is capa-ble of generating compatible motions. Since sparse keyframes specify an under-constrained optimization problem, the optimized solutions can be imaginative anddiverse. In many cases, these motions contain complex contact paerns, whichcan be dicult to nd for existing keyframe-based methods without meticulouskeyframe design.In Figure 5.2, the input is a set of sparse horizontal displacement keyframesfor Luxo2D. e result of optimization is a diverse set of emergent and naturalbehaviors. Additional variations can be synthesized by adjusting the time-to-arrival and assist penalty parameters. ese motions are shown in Figure 5.2d-5.2f. A smaller time-to-arrival generally promotes faster motions and a largerassist penalty encourages more natural motions. e forward roll strategy in Fig-ure 5.2e demonstrates the exibility of our method in handling complex contactpaerns. Figure 5.3a-5.3c show another example of emergent behavior. In thesecond variation, Folk discovers the strategy of using the vaulting platform as aintermediate foothold, in order to perform a more balanced landing.Our method also extends to dense-keyframe setups. When necessary, thisallows artists to provide additional keyframes to precisely control the characterbehavior during particular motion segments. Figure 5.3 shows a six-keyframewalk cycle for the Folk character over a medium sized block. rough this exam-ple, we note that our method is capable of generating trajectories which track the30(a) Input: Sparse horizontaldisplacement(b) Output: Single large hop(c) Output: Large + small hop (d) Output: Two medium hops(e) Output: Forward roll (f) Output: Small + large hopFigure 5.2: An example of generating diverse motions from a single set of sparsehorizontal displacement keyframes.31(a) Input: Vault (b) Output: One-shot vault(c) Output: Stops on the platform to do a more balanced landing(d) Input: Walk cycle (e) Output: Reference keyframes aretracked closelyFigure 5.3: Folk2D walk cycle and vault motions specied with dense keyframes.32(a) Input: Luxo2D and Desk2D jumpingover SIGGRAPH leers(b) Output: Optimized trajectoriesFigure 5.4: Examples of physically impossible keyframes and motions.(a) Folk2D Wall Flip(b) Desk2D Wall Jump(c) Boxy Supine Getup(d) Boxy Rotate Back Flip(e) Boxy Sit Down on SIGGRAPH LeersFigure 5.5: Our method can generate highly dynamic motions and 3D motions.e lemost column shows the keyframes for each motion. e optimized trajec-tories are shown from le to right in each row.33carefully designed input keyframe sequences.5.3 Impossible MotionsArtists oen require animated characters to perform motions exaggerated beyondthe limitations of physical laws. is is particularly challenging for existing opti-mization methods which are oen designed to synthesize physically feasible mo-tions. In contrast, in addition to physically feasible motions, our method is ableto generate trajectories that are not entirely physical. Although these impossiblemotions can only be performed under the assistance of external forces, the overallmotion quality remains reasonable due to the regularization eecct of the assistpenalty in the objective function. Figure 5.4 shows Luxo2D and Desk2D jumpingover obstacles beyond their physical capabilities. For physically feasible motions,we observe that our framework generally produces motions that are not overlydependent on the external assistive forces. In some cases, the optimized trajec-tories are not impacted at all when we disable the assistive forces at run-time.chapter 6 discusses the dierence between impossible and physically feasible mo-tions in more detail.5.4 Contact-Rich MovementsWe are able to generate highly dynamic motions using our framework. We syn-thesized various wall ip and wall jump trajectories using few keyframes. Fig-ure 5.5a and 5.5b are two examples of complex movements. Note that in Fig-ure 5.5a, we intentionally placed the second keyframe with partial overlap withthe wall. Despite this, the output trajectory is a clean collision as a result of thephysics simulation. Figure 5.5b shows an example where the Desk2D character isable to use the mini-footholds to escape the connement of the walls. ese mo-tions typically require meticulous ne-tuning in traditional kinematic keyframeanimations. In contrast, our method seamlessly integrates physical interactionswith the environment into the optimization process. Furthermore, our methodalso compares favorably against methods that learn physically-based controllers.For these complex movements, straightforward application of reward-based rein-forcement learning can produce unnatural motions, or fail entirely in the absenceof reward engineering.345.5 3D MotionsWe also synthesize numerous motions for 3D characters. Even with relativelyfew keyframes, we can generate various geing-up, siing-down, and ippingmotions for Boxy, as shown in Figure 5.5. ese motions contain an additionalyaw-rotation parameter as part of the keyframe specication, which allows thecharacter to navigate in the xy-plane. Note that this is not the same as fully-parameterized 3D motions, which would allow roll-rotations along with pitchand yaw. Please refer to the supplementary video for visual demonstrations ofadditional motions.5.6 Table of Hyper-parametersIn Table 5.1 we provide a table of hyper-parameters used for generating our re-sults. Tuning these hyper-parameters is a straightforward process, where wechange the values a lile at a time and observe the quality of generated motions.We nd the number of action pieces, the range of allowed time-to-arrival values,and the regularization weight for external assist modulation to play signicantroles in generating visually pleasing results.35Table 5.1: e table of hyper-parameters for the motions appearing in this paperand the supplementary video.Motion # action pieces min. ∆t max. ∆t λβLuxo reverse somersault 10 5 40 1e+2.00Luxo clamber 10 10 60 1e+0.25Luxo jump-hop 10 5 30 1e+2.00Luxo high box jump 10 5 45 1e+3.00Luxo wall ip 10 10 30 1e+2.00Luxo cli-walk 30 15 40 1e+1.00Luxo cli-jump 13 10 30 1e+0.20Desk cli-walk 20 5 40 1e+0.85Desk cli-jump 13 5 30 1e+1.50Desk wall jump 10 15 30 1e+0.65Folk forward roll 10 15 30 1e+0.50Folk backward roll 14 15 40 1e-1.00Folk long jump 12 5 35 1e+1.00Folk parkour 16 5 25 1e-0.50Folk wall ip 10 10 55 1e+1.75Folk valut 13 5 30 1e+1.50Folk handstand 15 10 45 1e+0.70Boxy supine getup 10 30 65 1e-2.00Boxy prone getup 10 40 60 1e-3.00Boxy wall ip 10 10 30 1e+1.00Boxy backtumble 10 10 30 1e-2.00Boxy turn-and-ip 15 5 40 1e-1.00Boxy high jump 13 5 20 1e+0.00Boxy walk and sit 20 15 30 1e-2.0036Chapter 6DiscussionOur method is thus able to produce visually pleasing motions based on inputkeyframes, which achieves the goal of incorporating user directives into physics-based character animation. In this chapter, we analyze the signicance and limi-tations of the components of our system.6.1 Importance of Compact Parameterization ofAssistive ForcesTo assess the importance of our novel control parameterization scheme, we presentquantitative and qualitative analyses of results comparing our approach with otherbaselines. We design three approaches in total:• Time-indexed β with spring-damper system (ours, Tβ): use piecewiseconstant β as described in Chapter 4.• Global β with spring-damper system (Gβ): use the same spring-damperassistive forces based on linearly interpolated reference motion. However,instead of modulating the inuence of external forces, apply a constant βvalue throughout the motion.• Time-indexed root-force-and-torque (RFT): use external force and torqueon character’s root, independent of reference motion.In the following subsections, we show that (1) our Tβ approach is sucientlyexpressive for scenarios that require both physically feasible and infeasible mo-tions, which Gβ does not handle well, and (2) the structure and compactness ofour Tβ approach avoids the curse of dimensionality, which RFT cannot avoid.Time-Indexed β vs. Global βTo showcase the benets of our Tβ approach, we show that our scheme can handlephysically feasible and infeasible motions appearing in the same task. Intuitively,choosing a constant reliance on the assistive forces can lead to excessive use of370.04 0.06 0.08 0.10 0.12Mean 0.0200.0250.0300.0350.0400.0450.050Keyframe ErrorKeyframe Error vs. Mean by Control Parameterization SchemeMotion: Luxo Jump-HopTime-Indexed (d=46)Global (d=37)Figure 6.1: Comparison of performance between global β and time-indexed β.Each point represents a solution. Ideal solutions (small assist, small error) resideon the boom-le corner.assist in easy motions or insucient use of assist in dicult motions. Since weaim to create a system that is agnostic to the physical feasibility of input motionsketch, the control parameters must be suciently expressive to handle thesescenarios.e test case depicted in Figure 6.2 captures an example use case where theartist species an impossible high-jump motion and an easy forward-hopping mo-tion appearing together. We use our system to produce optimized motions withtuned hyper-parameters such as assist regularization weight λβ and the range ofTTA values. Once tuned, these hyper-parameters are xed across the two param-eterization schemes. For each approach, we obtain 100 independent convergedsolutions using the compute budget of 15,000 samples, and then we examine theresulting keyframe errors as well as the magnitude of β.Figure 6.1 highlights how the performance of our system diers based onwhether Tβ or Gβ is used. Figure 6.3 compares the optimized motions side-by-38Figure 6.2: e “jump-hop” scenario where the character performs both easy andphysically impossible motions.side. We observe that the Tβ approach yields solutions that succeed in achievinglower keyframe errors while keeping the use of external assist moderate. On theother hand, learning a global β yields either high keyframe errors due to insu-cient use of assist during the dicult motion or excessive use of assist to drive thekeyframe errors low. However, we note that the reduction in parameter dimen-sionality for the Gβ approach tends to yield high-quality actions, which synergizewell with the external assistive forces to an extent. As seen in the right-hand sideof Figure 6.3, the character produces a plausible jumping motion for the initialhigh jump, although it fails to produce good actions for the later hopping motion,due to the excessive use of external assist. On the other hand, the le-hand sideof Figure 6.3 shows the character relying mostly on external assist for the highjump, refraining from producing internal torques, which is expected since actionsare regularized. e character produces a plausible hopping motion aerwards,being able to suppress the use of external assist when not necessary.Time-Indexed β vs. Time-Indexed Root-Force-and-TorqueA naı¨ve-yet-straightforward alternative to using our control parameterization schemeis to treat external forces as parameters to be directly optimized. Namely, we mayintroduce time-indexed forces fext,t and torques τext,t to be applied at the char-acter’s root node, following the same piece-wise constant approach as β shown39Figure 6.3: A side-by-side comparison of the character performing the “jump-hop”task (keyframes shown in Figure 6.2) according to dierent external assist param-eters. Le : optimized with time-indexed β approach. (d=47) Right: optimizedwith global β approach. (d=36)in Figure 4.1. However, this approach drastically increases the parameter dimen-sionality. For the 2D case, time-indexed forces fext,t ∈ R2 and torques τext,t ∈ Rincur three parameters, as opposed to one parameter associated with each time-indexed βt ∈ [0, 1].Given the same compute budget of 15,000 samples, the time-indexed root-force-and-torque approach struggles to perform on tasks requiring a signicantamount of external assist. We use a high box jump task in Figure 6.4 to demon-strate this. Again, we use our system to produce optimized motions aer tuningthe hyper-parameters. is time, we tune the regularization weight λβ separatelyto take into account the scale dierences in the two parameterization schemes.In Figure 6.5, we provide a side-by-side comparison of the optimized motions.e parameter dimensionality diers by 20, making the search space for optimalcontrol much larger for the RFT approach. e motion on the right-hand sideshows an example case of a bad local minimum encountered when using the RFTapproach, which happens frequently among converged solutions. On the other40Figure 6.4: e “high box jump” scenario requiring a signicant amount of exter-nal assist to produce the desired motion.hand, the le-hand side shows an example of a good local minimum encounteredwhen using the Tβ approach, yielding an emergent solution of using a somersaultmotion to synergize with the spring-damper forces.6.2 Trade-o: Keyframe Tracking and Assist UseAs with most optimization problems involving regularization, there is a trade-o between keyframe tracking performance and the amount of external assistused, induced by the choice of regularization strength λβ as appears in Equa-tion 4.4. Intuitively, larger values of λβ discourage the use of external assistiveforces and thus encourages more physically-based solutions to emerge, whichmay have worse keyframe tracking performance when the specied motion isdicult. Smaller values of λβ , on the other hand, may result in solutions that relycompletely on external assist, which makes the result visually unappealing dueto ragdoll-like behaviors.is trade-o is visualized in Figure 6.6, where varying levels of λβ result insolutions lying on dierent parts of the plot, implicitly forming a trade-o frontier.For this experiment, for each value of λβ , we budget 15,000 samples per run andobtain 5 independent runs of CMA-ES using our time-indexed β approach. We usea simple box jump motion (see Figure 6.7) that is dicult but possible to perform41Figure 6.5: A side-by-side comparison of the character performing the “high boxjump” task (keyframes shown in Figure 6.4) according to dierent external assistparameters. Le : optimized with Tβ approach. (d=44) Right: optimized withRFT approach. (d=64)without external assist. Figure 6.8 shows that a high λβ results in physically-based motions incurring high keyframe error while a low λβ results in passiveand ragdoll-like motions incurring low keyframe errors.6.3 Evaluation of Horizon CurriculumWe evaluate the eect of horizon curriculum on the optimization time and ob-jective function cost at convergence. For experiments with horizon curriculumdisabled, we set the initial curriculum stage to span all keyframes. Table 6.1 sum-marizes the result. A caveat is that a lower objective function value is not alwaysindicative of beer motion. For example, we nd the quality of wall ip motionsfor values 8.9× 10−2 and 3.6× 10−2 to be visually similar.e horizon curriculum serves to reduce the perceived latency of the optimiza-tion process by immediately having short-horizon results to display. However,this can sometimes come at the cost of slowing the overall optimization. In some42Table 6.1: Evaluation of Horizon Curriculum. Each value shows the mean andstandard deviation of ve independent optimization runs with dierent randomseeds. e Time columns are the overall optimization wall-clock time in seconds.e Cost columns show the scaled (×10−2) objective function values when opti-mization is completed.Curriculum No CurriculumTime (s) Cost Time (s) CostLuxo Back Flip 17.9± 4.1 0.9± 0.2 27.6± 4.1 0.8± 0.4Desk Wall Jump 112.8± 8.9 7.5± 0.4 54.2± 4.6 5.3± 0.4Folk Wall Flip 78.3± 3.1 8.9± 2.5 101.1± 16.5 3.6± 0.3Boxy Jump 50.8± 7.2 3.0± 1.1 74.0± 22.9 2.7± 0.5Table 6.2: Eects of CMA-ES population size on nal objective function values.Time and cost are reported the same way as Table 6.1.Population Size P=8 P=16 P=32 P=48Luxo Back FlipTime (s) 9.4± 0.8 8.0± 0.6 11.9± 0.9 17.9± 4.1Cost 5.9± 1.7 3.1± 1.6 2.1± 1.0 0.9± 0.2Folk Wall FlipTime (s) 58.8± 2.9 54.1± 4.7 63.0± 2.8 78.3± 3.1Cost 18.3± 5.0 13.3± 3.5 9.9± 2.4 8.9± 2.5430.0 0.1 0.2 0.3 0.4Mean 0.0010.0020.0030.0040.005Keyframe ErrorKeyframe Error vs. Mean by External Force Regularization StrengthMotion: Luxo Box JumpValue of 0.0010.010.11.010.0100.01000.0Figure 6.6: Comparison of performance across 7 dierent values of regularizationstrength λβ . Each point represents a solution. Ideal solutions (small assist, smallerror) reside on the boom-le corner.cases, such as Desk2D wall jump, we nd that horizon curriculum can degrade theconvergence speed when the optimized motions are complex. is behavior is ex-pected since the growing horizon approach of the curriculum means that earlieroptimization stages cannot consider the impact of later keyframes. Consequentlythe earlier solutions may fall in local minima, and thus need to be re-optimizedas new keyframes become available. For simpler motions, the total optimizationtimes are comparable between training with and without horizon curriculum. Inthe case of Luxo2D back ip and Boxy jump, the optimization time with horizoncurriculum is on average faster than training without curriculum.6.4 Sensitivity to Population Sizee optimized motions can exhibit some sensitivity to the population size of CMA-ES. In general, evolution strategies tend to nd beer solutions when using larger44Figure 6.7: e “low box jump” scenario that is dicult but possible to producethe desired motion without external assist.populations. A larger population size alleviates the problem of local minima bymaintaining a more diverse set of individuals throughout the optimization pro-cess. We observe this phenomenon in motion sketch optimization, as shown in Ta-ble 6.2. Since the experiments were performed on a 24-core machine, we expectthe optimization time to be at a minimum when population size is equal to 24. Wealso note that beer solutions are achieved at convergence with a larger popula-tion size. In the back ip and wall ip examples, the dierence in motion qualitybetween P = 8 and P = 48 is noticeable. Using lower population size is morelikely to produce motions with incomplete rotations, which inhibit the charactersfrom performing a stable landing. us, when considering the trade-o betweenoptimization time and motion quality, we set the population size to 48 for all ourexperiments.6.5 Do Assistive Forces Help?It is clear that external assistive forces are required for the characters to performimpossible motions. However, assistive forces may also help with optimizationeven when the keyframes are physically feasible, due to forces in eect acting asa temporary constraint-relaxation method that may speed the optimization. Inour experiments, we consistently nd that using assistive forces leads to higher45Figure 6.8: A side-by-side comparison of the character performing the “low boxjump” task (keyframes shown in Figure 6.7) according to dierent regularizationstrengths. Le : optimized with λβ = 1e3. Right: optimized with λβ = 1e − 3.Note the emergent backip which helps the character stay on a physically-basedtrajectory but completely ignores an intermediate keyframe.quality results than the alternative, given equal amount of compute budget. Fig-ure 6.9 compares two trajectories of the same back ip motion optimized with andwithout assistive forces. In the case where high assist penalty (λβ = 103) is used,the result is a full back ip rotation with a stable landing, even when assistiveforces are disabled at run-time. In contrast, motion optimized without assistiveforces is incapable of performing a stable landing.6.6 Tracking Assist Over TimeSince every optimization parameter has an initial mean value of zero, our systemstarts the optimization iterations assuming that the assistive force coecients areclose to zero, i.e. β ≈ 0. However, as shown in Figure 6.10, the optimizer tends toexplore higher values of assistive force coecients in the beginning and leverageassistive forces for nding viable solution modes. Aer some iterations, the re-liance on assistive force is gradually reduced and eventually converges to a xedvalue depending on the cost function penalty λβ . We believe this exploration be-havior is analogous to a learning curriculum, similar to [51], and may explain thediscrepancy observed in Figure 6.9.We also track the usage of assistive forces within a single roll-out episode fora long jump motion, shown in Figure 6.11. e time period with the highest assis-tive forces corresponds to the motion segment that demands the most unphysical46(a) Motion optimized with high assistpenalty and replayed without assist(b) Motion optimized without assistFigure 6.9: Comparison of optimized trajectories with and without assist duringtraining. Training with assist yields a more stable trajectory, even with assistiveforces disabled at run-time. Note the 6.9b trajectory performs a partial rotationand unstable landing.accelerations. is observation is also aligned with our intuition.6.7 User InterfaceOur user interface prototype is built to enable rapid prototyping of user-directedphysics-based character animation, borrowing from traditional keyframing-basedanimation workow. Instead of kinematic interpolation, we oer the capability tolaunch an optimization job based on the parameters specied by the control panel.Figure 6.12 shows the full view of our DearPyGui-based control panel, which isused in conjunction with the display of the simulation environment.Please refer to the supplementary video for demonstrations of the graphicaluser interface.6.8 LimitationsWhile we have made signicant progress, our work still has unsolved issues. esystem requires some experience in order to be able to quickly debug motionsthat do not behave as rst intended. e optimized results can be sensitive tovarious hyperparameters, such as the CMA-ES population size and the assistiveforce penalty. We have yet to show that the method could scale to complex 3Dhuman movements. e current system is not yet fully interactive. We do not yetdemonstrate long duration keyframe sequences, although we expect that these470 50 100 150 200CMA Iteration0.0000.0250.0500.0750.1000.1250.1500.175Best Average 2 t In MotionEvolution of Assist Force Usage During Optimizationfor Luxo Somersault without Horizon Curriculum=1=10=100=1000Figure 6.10: Evolution of assistive force usage during optimization, as measuredby the average β2t used throughout the motion. During the optimization iter-ations, our system initially explores larger values of βt and then gradually de-creases reliance on assistive force.could be eciently achieved using a windowed optimization. e current choicesfor dening motion trajectories need to be adapted for modeling cyclic motions.48(a) Input keyframes for an impossible long jump(b) Progression of optimized βt values over time and snapshots of optimized motioncorresponding to each value.Figure 6.11: is example shows the amount of assistive forces used to performan impossible long jump by Folk. In the nal optimized motion, only a signicantamount of assist is used right before the ight phase.491234Figure 6.12: e full view of the control panel of our user interface. 1: keyframesare displayed as tabs that can be added and removed. 2: keyframe congurations,such as root position, orientation, joint angles, and keyframe weights can be ma-nipulated with sliders and buon modules. 3: CMA congurations are exposedto the user, including action lengths, time-to-arrival ranges, penalty weights, andcomputation budget parameters. 4: the user can display optimized motions aswell as reference motions induced by input keyframes.50Chapter 7ConclusionsWe have presented a method for generating as-plausible-as-possible motions fromcrude keyframe inputs using motion sketch optimization. Our method provides anovel combination of internal actuations, external assistive forces, and black-boxsimulation, which successfully tackles the transformation from crude keyframesto motions that are “alive”. We believe that the character animation communitywill nd the work to be exciting and that the simplicity of the method will facili-tate its adoption.Our framework unies the motion synthesis process of both physically-feasibleand artistically-exaggerated motions for rigid-body characters using external as-sistive forces that can be modulated over time. By using a suitably-craed ob-jective function, our system collectively optimizes internal actions, external as-sists, and keyframe timings to produce compatible trajectories for a simple inputkeyframe sequence. We applied motion sketch optimization to four distinct char-acters on a wide variety of motions. In many cases, our system produces natu-ral motions and emergent behaviours from sparse keyframe inputs. e methodeectively subsumes physics-as-a-hard-constraint and rag-doll trajectory track-ing as special cases at opposite ends of the assistive spectrum. For the case ofphysically-feasible motions, the introduction of assistive forces oen acts as use-ful temporary constraint relaxation methods, allowing for faster optimization.We have shown that our compact control parameterization scheme is su-ciently expressive to handle both physically feasible and infeasible motions ap-pearing in the same motion sketch, helping our system stay agnostic to the phys-ical feasibility of the input keyframes. Our parameterization approach furtherhelps combat the curse of dimensionality, thus improving sample-eciency ofCMA-ES and reducing encounters with local minima.Many avenues exist for future work. We envision partial keyframing to bea straightforward yet highly rewarding extension. For example, one may x theheight and pose of a keyframe but otherwise leave its location free to be optimized.More exible motions will emerge, although at the cost of increased dimension-ality of parameters. We also envision opportunities for data-driven methods toimprove performance, e.g. using a supervised model as a caching mechanismto allow for re-use and warm-starts for optimization. Meanwhile, dierentiable51physics (e.g. [18]), GPU-accelerated simulators (e.g. [31]), and sampling and par-ticle lter-based optimization (e.g. [13]) all show promise towards scaling opti-mization for more complex character morphologies and movements. Other im-provements include multi-resolution optimization; understanding the benets ofhigher-order interpolants, if any; and an improved user interface.Finally, by considering state-indexed control methods as an orthogonal direc-tion, we may bridge the gap between trajectory optimization and closed-loop con-trol for directable physics-based character animation. Success in these tasks willhelp combine the strengths of motion sketch-driven techniques with the benetsof RL-based techniques (e.g. real-time inference and robustness to perturbations).52Bibliography[1] Shailen Agrawal, Shuo Shen, and Michiel van de Panne. Diverse motion vari-ations for physics-based character animation. In Proceedings of the 12th ACMSIGGRAPH/Eurographics Symposium on Computer Animation, pages 37–44,2013.[2] Mazen Al Borno, Martin De Lasa, and Aaron Hertzmann. Trajectory opti-mization for full-body movements with complex contacts. IEEE transactionson visualization and computer graphics, 19(8):1405–1414, 2012.[3] Mazen Al Borno, Michiel van de Panne, and Eugene Fiume. Domain of at-traction expansion for physics-based character control. ACM Transactionson Graphics (TOG), 36(2):1–11, 2017.[4] Ronen Barzel, John R Hughes, and Daniel N Wood. Plausible motion simu-lation for computer graphics animation. In Computer Animation and Simu-lation’96, pages 183–197. Springer, 1996.[5] Kevin Bergamin, Simon Clavet, Daniel Holden, and James Richard Forbes.Drecon: data-driven responsive control of physics-based characters. ACMTransactions on Graphics (TOG), 38(6):1–11, 2019.[6] Danny Chapman, Tim Daoust, Andras Ormos, and Joseph Lewis. Weight-shi: Accelerating animation at framestore with physics. In ACM SIG-GRAPH/Eurographics Symposium on Computer Animation, showcase proceed-ings, pages 1–2. 2020.[7] Nuapong Chentanez, Mahias Mu¨ller, Miles Macklin, Viktor Makoviy-chuk, and Stefan Jeschke. Physics-based motion capture imitation with deepreinforcement learning. In Proceedings of the 11th Annual International Con-ference on Motion, Interaction, and Games, pages 1–10, 2018.[8] Erwin Coumans and Yunfei Bai. Pybullet, a python module for physics sim-ulation for games, robotics and machine learning. http://pybullet.org, 2016–2020.53[9] Philip E Gill, Walter Murray, and Michael A Saunders. Snopt: An sqp algo-rithm for large-scale constrained optimization. SIAM review, 47(1):99–131,2005.[10] Sehoon Ha and C Karen Liu. Iterative training of dynamic skills inspired byhuman coaching techniques. ACM Transactions on Graphics (TOG), 34(1):1–11, 2014.[11] Peru Ha¨ma¨la¨inen, Sebastian Eriksson, Esa Tanskanen, Ville Kyrki, andJaakko Lehtinen. Online motion synthesis using sequential monte carlo.ACM Transactions on Graphics (TOG), 33(4):1–12, 2014.[12] Peru Ha¨ma¨la¨inen, Joose Rajama¨ki, and C Karen Liu. Online control ofsimulated humanoids using particle belief propagation. ACM Transactionson Graphics (TOG), 34(4):1–13, 2015.[13] Peru Ha¨ma¨la¨inen, Joose Rajama¨ki, and C. Karen Liu. Online control ofsimulated humanoids using particle belief propagation. ACM Trans. Graph.,34(4), July 2015.[14] Daseong Han, Haegwang Eom, Junyong Noh, and Joseph S Shin. Data-guided model predictive control based on smoothed contact dynamics. InComputer Graphics Forum, volume 35, pages 533–543. Wiley Online Library,2016.[15] Nikolaus Hansen. e cma evolution strategy: A tutorial. arXiv preprintarXiv:1604.00772, 2016.[16] Nikolaus Hansen, Youhei Akimoto, yoshihikoueno, Dimo Brockho, andMahew Chan. Cma-es/pycma: r3.0.3, April 2020.[17] Nikolaus Hansen and Andreas Ostermeier. Completely derandomized self-adaptation in evolution strategies. Evolutionary computation, 9(2):159–195,2001.[18] Eric Heiden, David Millard, Hejia Zhang, and Gaurav S Sukhatme. Interac-tive dierentiable simulation. arXiv preprint arXiv:1905.10706, 2019.[19] Sumit Jain, Yuting Ye, and C Karen Liu. Optimization-based interactive mo-tion synthesis. ACM Transactions on Graphics (TOG), 28(1):1–12, 2009.[20] Mahew Kelly. An introduction to trajectory optimization: How to do yourown direct collocation. SIAM Review, 59(4):849–904, 2017.54[21] Nam Hee Kim, Hung Yu Ling, Zhaoming Xie, and Michiel van de Panne.Motion sketch optimization. In Proc. ACM SIGGRAPH 2021, 2021.[22] Taesoo Kwon, Yoonsang Lee, and Michiel Van De Panne. Fast and exiblemultilegged locomotion using learned centroidal dynamics. ACM Transac-tions on Graphics (TOG), 39(4):46–1, 2020.[23] Sergey Levine and Jovan Popovic´. Physically plausible simulation for char-acter animation. In Proceedings of the 11th ACM SIGGRAPH/EurographicsSymposium on Computer Animation, pages 221–230, 2012.[24] C Karen Liu and Zoran Popovic´. Synthesis of complex dynamic charac-ter motion from simple animations. ACM Transactions on Graphics (TOG),21(3):408–416, 2002.[25] Libin Liu, KangKang Yin, and Baining Guo. Improving sampling-based mo-tion control. In Computer Graphics Forum, volume 34, pages 415–423. WileyOnline Library, 2015.[26] Libin Liu, KangKang Yin, Michiel van de Panne, Tianjia Shao, and WeiweiXu. Sampling-based contact-rich motion control. In ACM SIGGRAPH 2010papers, pages 1–10. 2010.[27] Azumi Maekawa, Ryuma Niiyama, and Shunji Yamanaka. Pseudo-locomotion design with a quadrotor-assisted biped robot. In 2018 IEEE Inter-national Conference on Robotics and Biomimetics (ROBIO), pages 2462–2466.IEEE, 2018.[28] Carlos Mastalli, Rohan Budhiraja, Wolfgang Merkt, Guilhem Saurel, BilalHammoud, Maximilien Naveau, Justin Carpentier, Ludovic Righei, SethuVijayakumar, and Nicolas Mansard. Crocoddyl: An ecient and versatileframework for multi-contact optimal control. In 2020 IEEE International Con-ference on Robotics and Automation (ICRA), pages 2536–2542. IEEE, 2020.[29] Josh Merel, Saran Tunyasuvunakool, Arun Ahuja, Yuval Tassa, LeonardHasenclever, Vu Pham, Tom Erez, Greg Wayne, and Nicolas Heess. Catch &carry: reusable neural controllers for vision-guided whole-body tasks. ACMTransactions on Graphics (TOG), 39(4):39–1, 2020.[30] Christian Kurtz Miller. Derivative-free motion optimization for animatedcharacters. PhD thesis, University of Texas at Austin, 2016.55[31] Filipe Figueredo Monteiro, Andre Luiz Buarque Vieira, Joa˜o MarceloXavier Nata´rio Teixeira, Veronica Teichrieb, et al. Simulating real robotsin virtual environments using nvidia’s isaac sdk. In Anais Estendidos do XXISimpo´sio de Realidade Virtual e Aumentada, pages 47–48. SBC, 2019.[32] Igor Mordatch, Emanuel Todorov, and Zoran Popovic´. Discovery of com-plex behaviors through contact-invariant optimization. ACM Transactionson Graphics (TOG), 31(4):1–8, 2012.[33] Soohwan Park, Hoseok Ryu, Seyoung Lee, Sunmin Lee, and Jehee Lee.Learning predict-and-simulate policies from unorganized human motiondata. ACM Transactions on Graphics (TOG), 38(6):1–11, 2019.[34] Xue Bin Peng, Pieter Abbeel, Sergey Levine, and Michiel van de Panne.Deepmimic: Example-guided deep reinforcement learning of physics-basedcharacter skills. ACM Transactions on Graphics (TOG), 37(4):1–14, 2018.[35] Xue Bin Peng, Glen Berseth, KangKang Yin, and Michiel Van De Panne.Deeploco: Dynamic locomotion skills using hierarchical deep reinforcementlearning. ACM Transactions on Graphics (TOG), 36(4):1–13, 2017.[36] Cristina Pinneri, Shambhuraj Sawant, Sebastian Blaes, Jan Achterhold, Jo-erg Stueckler, Michal Rolinek, and Georg Martius. Sample-ecient cross-entropy method for real-time planning. arXiv preprint arXiv:2008.06389,2020.[37] Michael Posa, Cecilia Cantu, and Russ Tedrake. A direct method for trajec-tory optimization of rigid bodies through contact. e International Journalof Robotics Research, 33(1):69–81, 2014.[38] Amir H Rabbani and Paul G Kry. Physik: Physically plausible and intuitivekeyframing. In Graphics Interface, pages 153–161, 2016.[39] Joose Rajama¨ki and Peru Ha¨ma¨la¨inen. Continuous control monte carlo treesearch informed by multiple experts. IEEE transactions on visualization andcomputer graphics, 25(8):2540–2553, 2018.[40] Paul SA Reitsma and Nancy S Pollard. Perceptual metrics for character an-imation: sensitivity to errors in ballistic motion. In ACM SIGGRAPH 2003Papers, pages 537–542. 2003.[41] Reuven Rubinstein. e cross-entropy method for combinatorial and con-tinuous optimization. Methodology and computing in applied probability,1(2):127–190, 1999.56[42] Kwang Won Sok, Katsu Yamane, Jehee Lee, and Jessica Hodgins. Edit-ing dynamic human motions via momentum and force. In Proceedings ofthe 2010 ACM SIGGRAPH/Eurographics Symposium on Computer animation,pages 11–20, 2010.[43] Yuval Tassa, Tom Erez, and Emanuel Todorov. Synthesis and stabilization ofcomplex behaviors through online trajectory optimization. In 2012 IEEE/RSJInternational Conference on Intelligent Robots and Systems, pages 4906–4913.IEEE, 2012.[44] Frank omas, Ollie Johnston, and Frank omas. e illusion of life: Disneyanimation. Hyperion New York, 1995.[45] Michiel van de Panne and Alexis Lamouret. Guided optimization for bal-anced locomotion. In Computer Animation and Simulation’95, pages 165–177.Springer, 1995.[46] Andreas Wa¨chter and Lorenz T Biegler. On the implementation of aninterior-point lter line-search algorithm for large-scale nonlinear program-ming. Mathematical programming, 106(1):25–57, 2006.[47] Kevin Wampler and Zoran Popovic´. Optimal gait and form for animal loco-motion. ACM Transactions on Graphics (TOG), 28(3):1–8, 2009.[48] Andrew Witkin and Michael Kass. Spacetime constraints. ACM SiggraphComputer Graphics, 22(4):159–168, 1988.[49] Jungdam Won, Deepak Gopinath, and Jessica Hodgins. A scalable approachto control diverse behaviors for physically simulated characters. ACM Trans-actions on Graphics (TOG), 39(4):33–1, 2020.[50] Pawel Wrotek, Odest Chadwicke Jenkins, and Morgan McGuire. Dynamo:dynamic, data-driven character control with adjustable balance. In Proceed-ings of the 2006 ACM SIGGRAPH symposium on Videogames, pages 61–70,2006.[51] Wenhao Yu, Greg Turk, and C Karen Liu. Learning symmetric and low-energy locomotion. ACM Transactions on Graphics (TOG), 37(4):1–12, 2018.57
Thesis/Dissertation
eng
Computer Science
Vancouver : University of British Columbia Library
Attribution-NonCommercial-NoDerivatives 4.0 International
Graduate
Directable physics-based character animation
Text
Moving Image