<!DOCTYPE html><htmllang="en-US"><head><metacharset="UTF-8"><metahttp-equiv="X-UA-Compatible"content="IE=Edge"><title>Skeleton Kinematics - </title><linkrel="shortcut icon"href="/favicon.ico"type="image/x-icon"><linkrel="stylesheet"href="/assets/css/just-the-docs-default.css"><script type="text/javascript"src="/assets/js/vendor/lunr.min.js"></script><script type="text/javascript"src="/assets/js/just-the-docs.js"></script><metaname="viewport"content="width=device-width, initial-scale=1"><!-- Begin Jekyll SEO tag v2.7.1 --><title>Skeleton Kinematics</title><metaname="generator"content="Jekyll v4.2.0"/><metaproperty="og:title"content="Skeleton Kinematics"/><metaproperty="og:locale"content="en_US"/><metaname="twitter:card"content="summary"/><metaproperty="twitter:title"content="Skeleton Kinematics"/><script type="application/ld+json">{"headline":"Skeleton Kinematics","@type":"WebPage","url":"/animation/skeleton_kinematics","@context":"https://schema.org"}</script><!-- End Jekyll SEO tag --></head><body><svgxmlns="http://www.w3.org/2000/svg"style="display: none;"><symbolid="svg-link"viewBox="0 0 24 24"><title>Link</title><svgxmlns="http://www.w3.org/2000/svg"width="24"height="24"viewBox="0 0 24 24"fill="none"stroke="currentColor"stroke-width="2"stroke-linecap="round"stroke-linejoin="round"class="feather feather-link"><pathd="M10 13a5 5 0 0 0 7.54.54l3-3a5 5 0 0 0-7.07-7.07l-1.72 1.71"></path><pathd="M14 11a5 5 0 0 0-7.54-.54l-3 3a5 5 0 0 0 7.07 7.07l1.71-1.71"></path></svg></symbol><symbolid="svg-search"viewBox="0 0 24 24"><title>Search</title><svgxmlns="http://www.w3.org/2000/svg"width="24"height="24"viewBox="0 0 24 24"fill="none"stroke="currentColor"stroke-width="2"stroke-linecap="round"stroke-linejoin="round"class="feather feather-search"><circlecx="11"cy="11"r="8"></circle><linex1="21"y1="21"x2="16.65"y2="16.65"></line></svg></symbol><symbolid="svg-menu"viewBox="0 0 24 24"><title>Menu</title><svgxmlns="http://www.w3.org/2000/svg"width="24"height="24"viewBox="0 0 24 24"fill="none"stroke="currentColor"stroke-width="2"stroke-linecap="round"stroke-linejoin="round"class="feather feather-menu"><linex1="3"y1="12"x2="21"y2="12"></line><linex1="3"y1="6"x2="21"y2="6"></line><linex1="3"y1="18"x2="21"y2="18"></line></svg></symbol><symbolid="svg-arrow-right"viewBox="0 0 24 24"><title>Expand</title><svgxmlns="http://www.w3.org/2000/svg"width="24"height="24"viewBox="0 0 24 24"fill="none"stroke="currentColor"stroke-width="2"stroke-linecap="round"stroke-linejoin="round"class="feather feather-chevron-right"><polylinepoints="9 18 15 12 9 6"></polyline></svg></symbol><symbolid="svg-doc"viewBox="0 0 24 24"><title>Document</title><svgxmlns="http://www.w3.org/2000/svg"width="24"height="24"viewBox="0 0 24 24"fill="none"stroke="currentColor"stroke-width="2"stroke-linecap="round"stroke-linejoin="round"class="feather feather-file"><pathd="M13 2H6a2 2 0 0 0-2 2v16a2 2 0 0 0 2 2h12a2 2 0 0 0 2-2V9z"></path><polylinepoints="13 2 13 9 20 9"></polyline></svg></symbol></svg><divclass="side-bar"><divclass="site-header"><ahref="/"class="site-title lh-tight"></a><ahref="#"id="menu-button"class="site-button"><svgviewBox="0 0 24 24"class="icon"><usexlink:href="#svg-menu"></use></svg></a></div><navrole="navigation"aria-label="Main"id="site-nav"class="site-nav"><ulclass="nav-list"><liclass="nav-list-item"><ahref="/"class="nav-list-link">Home</a></li><liclass="nav-list-item"><ahref="/git/"class="nav-list-link">GitHub Setup</a></li><liclass="nav-list-item"><ahref="/build/"class="nav-list-link">Building Scotty3D</a></li><liclass="nav-list-item"><ahref="#"class="nav-list-expander"><svgviewBox="0 0 24 24"><usexlink:href="#svg-arrow-right"></use></svg></a><ahref="/guide/"class="nav-list-link">User Guide</a><ulclass="nav-list "><liclass="nav-list-item "><ahref="/guide/animate_mode/"class="nav-list-link">Animate</a></li><liclass="nav-list-item "><ahref="/guide/layout_mode/"class="nav-list-link">Layout</a></li><liclass="nav-list-item "><ahref="/guide/model_mode/"class="nav-list-link">Model</a></li><liclass="nav-list-item "><ahref="/guide/render_mode/"class="nav-list-link">Render</a></li><liclass="nav-list-item "><ahref="/guide/rigging_mode/"class="nav-list-link">Rig</a></li><liclass="nav-list-item "><ahref="/guide/simulate_mode/"class="nav-list-link">Simulate</a></li></ul></li><liclass="nav-list-item"><ahref="#"class="nav-list-expander"><svgviewBox="0 0 24 24"><usexlink:href="#svg-arrow-right"></use></svg></a><ahref="/meshedit/"class="nav-list-link">A2: MeshEdit</a><ulclass="nav-list "><liclass="nav-list-item "><ahref="/meshedit/halfedge"class="nav-list-link">Halfedge Mesh</a></li><liclass="nav-list-item "><ahref="#"class="nav-list-expander"><svgviewBox="0 0 24 24"><usexlink:href="#svg-arrow-right"></use></svg></a><ahref="/meshedit/local/"class="nav-list-link">Local Operations</a><ulclass="nav-list"><liclass="nav-list-item "><ahref="/meshedit/local/edge_flip"class="nav-list-link">Edge Flip Tutorial</a></li><liclass="nav-list-item "><ahref="/meshedit/local/bevel/"class="nav-list-link">Bevelling</a></li></ul></li><liclass="nav-list-item "><ahref="#"class="nav-list-expander"><svgviewBox="0 0 24 24"><usexlink:href="#svg-arrow-right"></use></svg></a><ahref="/meshedit/global/"class="nav-list-link">Global Operations</a><ulclass="nav-list"><liclass="nav-list-item "><ahref="/meshedit/global/catmull/"class="nav-list-link">Catmull-Clark Subdivision</a></li><liclass="nav-list-item "><ahref="/meshedit/global/remesh/"class="nav-list-link">Isotropic Remeshing</a></li><liclass="nav-list-item "><ahref="/meshedit/global/linear/"class="nav-list-link">Linear Subdivision</a></li><liclass="nav-list-item "><ahref="/meshedit/global/loop/"class="nav-list-link">Loop Subdivision</a></li><liclass="nav-list-item "><ahref="/meshedit/global/simplify/"class="nav-list-link">Simplification</a></li><liclass="nav-list-item "><ahref="/meshedit/global/triangulate/"class="nav-list-link">Triangulation</a></li></ul></li></ul></li><liclass="nav-list-item"><ahref="#"class="nav-list-expander"><svgviewBox="0 0 24 24"><usexlink:href="#svg-arrow-right"></use></svg></a><ahref="/pathtracer/"class="nav-list-link">A3: Pathtracer</a><ulclass="nav-list "><liclass="nav-list-item "><ahref="/pathtracer/camera_rays"class="nav-list-link">(Task 1) Camera Rays</a></li><liclass="nav-list-item "><ahref="#"class="nav-list-expander"><svgviewBox="0 0 24 24"><usexlink:href="#svg-arrow-right"></use></svg></a><ahref="/pathtracer/intersecting_objects"class="nav-list-link">(Task 2) Intersections</a><ulclass="nav-list"><liclass="nav-list-item "><ahref="/pathtracer/ray_triangle_intersection"class="nav-list-link">Ray Triangle Intersection</a></li><liclass="nav-list-item "><ahref="/pathtracer/ray_sphere_intersection"class="nav-list-link">Ray Sphere Intersection</a></li></ul></li><liclass="nav-list-item "><ahref="/pathtracer/bounding_volume_hierarchy"class="nav-list-link">(Task 3) BVH</a></li><liclass="nav-list-item "><ahref="/pathtracer/shadow_rays"class="nav-list-link">(Task 4) Shadow Rays</a></li><liclass="nav-list-item "><ahref="/pathtracer/path_tracing"class="nav-list-link">(Task 5) Path Tracing</a></li><liclass="nav-list-item "><ahref="#"class="nav-list-expander"><svgviewBox="0 0 24 24"><usexlink:href="#svg-arrow-right"></use></svg></a><ahref="/pathtracer/materials"class="nav-list-link">(Task 6) Materials</a><ulclass="nav-list"><liclass="nav-list-item "><ahref="/pathtracer/dielectrics_and_transmission"class="nav-list-link">Dielectrics and Transmission</a></li></ul></li><liclass="nav-list-item "><ahref="#"class="nav-list-expander"><svgviewBox="0 0 24 24"><usexlink:href="#svg-arrow-right"></use></svg></a><ahref="/pathtracer/environment_lighting"class="nav-list-link">(Task 7) Environment Lighting</a><ulclass="nav-list"><liclass="nav-list-item "><ahref="/pathtracer/importance_sampling"class="nav-list-link">Environment Light Importance Sampling</a></li></ul></li><liclass="nav-list-item "><ahref="/pathtracer/visualization_of_normals"class="nav-list-link">Visualization of normals</a></li></ul></li><liclass="nav-list-item active"><ahref="#"class="nav-list-expander"><svgviewBox="0 0 24 24"><usexlink:href="#svg-arrow-right"></use></svg></a><ahref="/animation/"class="nav-list-link">A4: Animation</a><ulclass="nav-list "><liclass="nav-list-item "><ahref="/animation/splines"class="nav-list-link">Splines</a></li><liclass="nav-list-item active"><ahref="/animation/skeleton_kinematics"class="nav-list-link active">Skeleton Kinematics</a></li><liclass="nav-list-item "><ahref="/animation/skinning"class="nav-list-link">Skinning</a></li><liclass="nav-list-item "><ahref="/animation/particles"class="nav-list-link">Particles</a></li></ul></li></ul></nav><footerclass="site-footer"> This site uses <ahref="https://github.com/pmarsceill/just-the-docs">Just the Docs</a>, a documentation theme for Jekyll. </footer></div><divclass="main"id="top"><divid="main-header"class="main-header"><divclass="search"><divclass="search-input-wrap"><inputtype="text"id="search-input"class="search-input"tabindex="0"placeholder="Search "aria-label="Search "autocomplete="off"><labelfor="search-input"class="search-label"><svgviewBox="0 0 24 24"class="search-icon"><usexlink:href="#svg-search"></use></svg></label></div><divid="search-results"class="search-results"></div></div></div><divid="main-content-wrap"class="main-content-wrap"><navaria-label="Breadcrumb"class="breadcrumb-nav"><olclass="breadcrumb-nav-list"><liclass="breadcrumb-nav-list-item"><ahref="/animation/">A4: Animation</a></li><liclass="breadcrumb-nav-list-item"><span>Skeleton Kinematics</span></li></ol></nav><divid="main-content"class="main-content"role="main"><h1id="skeleton-kinematics"><ahref="#skeleton-kinematics"class="anchor-heading"aria-labelledby="skeleton-kinematics"><svgviewBox="0 0 16 16"aria-hidden="true"><usexlink:href="#svg-link"></use></svg></a> Skeleton Kinematics </h1><p>A <codeclass="language-plaintext highlighter-rouge">Skeleton</code>(defined in <codeclass="language-plaintext highlighter-rouge">scene/skeleton.h</code>) is what we use to drive our animation. You can think of them like the set of bones we have in our own bodies and joints that connect these bones. For convenience, we have merged the bones and joints into the <codeclass="language-plaintext highlighter-rouge">Joint</code> class which holds the orientation of the joint relative to its parent as euler angle in its <codeclass="language-plaintext highlighter-rouge">pose</code>, and <codeclass="language-plaintext highlighter-rouge">extent</code> representing the direction and length of the bone with respect to its parent <codeclass="language-plaintext highlighter-rouge">Joint</code>. Each <codeclass="language-plaintext highlighter-rouge">Mesh</code> has an associated <codeclass="language-plaintext highlighter-rouge">Skeleton</code> class which holds a rooted tree of <codeclass="language-plaintext highlighter-rouge">Joint</code>s, where each <codeclass="language-plaintext highlighter-rouge">Joint</code> can have an arbitrary number of children.</p><p>All of our joints are ball <codeclass="language-plaintext highlighter-rouge">Joint</code>s which have a set of 3 rotations around the <imgsrc="task2_media/0027.png"style="height:14px"/>, <imgsrc="task2_media/0028.png"style="height: 16px"/>, and <imgsrc="task2_media/0029.png"style="height: 16px"/> axes, called <em>Euler angles</em>. Whenever you deal with angles in this way, a fixed order of operations must be enforced, otherwise the same set of angles will not represent the same rotation. In order to get the full rotational transformation matrix, <imgsrc="task2_media/0030.png"style="height:16px"/>, we can create individual rotation matrices around the <imgsrc="task2_media/0031.png"style="height:16px"/>, <imgsrc="task2_media/0032.png"style="height:16px"/>, and <imgsrc="task2_media/0033.png"style="height:16px"/> axes, which we call <imgsrc="task2_media/0034.png"style="height:20px"/>, <imgsrc="task2_media/0035.png"style="height:20px"/>, and <imgsrc="task2_media/0036.png"style="height:20px"/> respectively. The particular order of operations that we adopted for this assignment is that <imgsrc="task2_media/0037.png"style="height:20px"/>.</p><h3id="forward-kinematics"><ahref="#forward-kinematics"class="anchor-heading"aria-labelledby="forward-kinematics"><svgviewBox="0 0 16 16"aria-hidden="true"><usexlink:href="#svg-link"></use></svg></a> Forward Kinematics </h3><p><em>Note: These diagrams are in 2D for visual clarity, but we will work with a 3D kinematic skeleton.</em></p><p>When a joint’s parent is rotated, that transformation should be propagated down to all of its children. In the diagram below, <imgsrc="task2_media/0038.png"style="height:18px"/> is the parent of <imgsrc="task2_media/0039.png"style="height:18px"/> and <imgsrc="task2_media/0040.png"style="height:18px"/> is the parent of <imgsrc="task2_media/0041.png"style="height:18px"/>. When a translation of <imgsrc="task2_media/0042.png"style="height:18px"/> and rotation of <imgsrc="task2_media/0043.png"style="height:18px"/> is applied to <imgsrc="task2_media/0044.png"style="height:18px"/>, all of the descendants are affected by this transformation as well. Then, <imgsrc="task2_media/0045.png"style="height:18px"/> is rotated by <imgsrc="task2_media/0046.png"style="height:18px"/> which affects itself and <imgsrc="task2_media/0047.png"style="height:18px"/>. Finally, when rotation of <imgsrc="task2_media/0048.png"style="height:18px"/> is applied to <imgsrc="task2_media/0049.png"style="height:18px"/>, it only affects itself because it has no children.</p><center><imgsrc="task2_media/forward_kinematic_diagram.jpg"style="height:480px"/></center><p>You need to implement these routines in <codeclass="language-plaintext highlighter-rouge">student/skeleton.cpp</code> for forward kinematics.</p><ul><li><codeclass="language-plaintext highlighter-rouge">Joint::joint_to_bind</code> Rreturn a matrix transforming points in the space of this joint to points in mesh space in bind position up to the base of this joint (end of its parent joint). You should traverse upwards from this joint’s parent all the way up to the root joint and accumulate their transformations.</li><li><codeclass="language-plaintext highlighter-rouge">Joint::joint_to_posed</code> Return a matrix transforming points in the space of this joint to points in mesh space, taking into account joint poses. Again, you should traverse upwards from this joint’s parent to the root joint.</li><li><codeclass="language-plaintext highlighter-rouge">Skeleton::end_of</code> Returns the end position of the joint in world coordinate frame, and you should take into account the base position of the skeleton (<codeclass="language-plaintext highlighter-rouge">Skeleton::base_pos</code>).</li><li><codeclass="language-plaintext highlighter-rouge">Skeleton::posed_end_of</code> Returns the end position of the joint in world coordinate frame with poses, and you should take into account <codeclass="language-plaintext highlighter-rouge">Skeleton::base_pos</code>.</li><li><codeclass="language-plaintext highlighter-rouge">Skeleton::joint_to_bind</code> Rreturn a matrix transforming points in the space of this joint to points in mesh space in bind position but with the base position of the skeleton taken in to account. Hint: use some function that you have implemented wisely!</li><li><codeclass="language-plaintext highlighter-rouge">Skeleton::joint_to_posed</code> Return a matrix transforming points in the space of this joint to points in mesh space, taking into account joint poses but with the base position of the skeleton taken in to account. Hint: use some function that you have implemented wisely!</li></ul><p>Once you have implemented these basic kinematics, you should be able to define skeletons, set their positions at a collection of keyframes, and watch the skeleton smoothly interpolate the motion (see the <ahref="../guide/animate.md">user guide</a> for an explanation of the interface). The gif below shows a very hasty demo defining a few joints and interpolating their motion.</p><center><imgsrc="task2_media/gif1.gif"/></center><center><imgsrc="task2_media/gif2.gif"/></center><p>Note that the skeleton does not yet influence the geometry of the cube in this scene – that will come in Task 3!</p><h3id="task-2b---inverse-kinematics"><ahref="#task-2b---inverse-kinematics"class="anchor-heading"aria-labelledby="task-2b---inverse-kinematics"><svgviewBox="0 0 16 16"aria-hidden="true"><usexlink:href="#svg-link"></use></svg></a> Task 2b - Inverse Kinematics </h3><h3id="single-target-ik"><ahref="#single-target-ik"class="anchor-heading"aria-labelledby="single-target-ik"><svgviewBox="0 0 16 16"aria-hidden="true"><usexlink:href="#svg-link"></use></svg></a> Single Target IK </h3><p>Now that we have a logical way to move joints around, we can implement Inverse Kinematics, which will move the joints around in order to reach a target point. There are a few different ways we can do this, but for this assignment we’ll implement an iterative method called gradient descent in order to find the minimum of a function. For a function <imgsrc="task2_media/0050.png"style="height:18px"/>, we’ll have the update scheme:</p><center><imgsrc="task2_media/0051.png"style="height:26px"/></center><p>Where <imgsrc="task2_media/0052.png"style="height:14px"/> is a small timestep. For this task, we’ll be using gradient descent to find the minimum of the cost function:</p><center><imgsrc="task2_media/0053.png"style="height:50px"/></center><p>Where <imgsrc="task2_media/0054.png"style="height:24px"/> is the position in world space of the target joint, and <imgsrc="task2_media/0055.png"style="height:18px"/> is the position in world space of the target point. More specifically, we’ll be using a technique called Jacobian Transpose, which relies on the assumption:</p><center><imgsrc="task2_media/0056.png"style="height:30px"/></center><p>Where:</p><ul><li><imgsrc="task2_media/0057.png"style="height:20px"/> (n x 1) is the function <imgsrc="task2_media/0058.png"style="height:22px"/>, where <imgsrc="task2_media/0059.png"style="height:22px"/> is the angle of joint <imgsrc="task2_media/0060.png"style="height:18px"/> around the axis of rotation</li><li><imgsrc="task2_media/0061.png"style="height:16px"/> is a constant</li><li><imgsrc="task2_media/0062.png"style="height:22px"/> (3 x n) is the Jacobian of <imgsrc="task2_media/0063.png"style="height:18px"/></li></ul><p>Note that here <imgsrc="task2_media/0064.png"style="height:14px"/> refers to the number of joints in the skeleton. Although in reality this can be reduced to just the number of joints between the target joint and the root, inclusive, because all joints not on that path should stay where they are, so their columns in <imgsrc="task2_media/0065.png"style="height:20px"/> will be 0. So <imgsrc="task2_media/0066.png"style="height:14px"/> can just be the number of joints between the target and the root, inclusive. Additionally note that since this will get multiplied by <imgsrc="task2_media/0067.png"style="height:16px"/> anyways, you can ignore the value of <imgsrc="task2_media/0068.png"style="height:14px"/>, and just consider the timestep as <imgsrc="task2_media/0069.png"style="height:16px"/>.</p><p>Now we just need a way to calcluate the Jacobian of <imgsrc="task2_media/0070.png"style="height:16px"/>. For this, we can use the fact that:</p><center><imgsrc="task2_media/0071.png"style="height:34px"/></center><p>Where:</p><ul><li><imgsrc="task2_media/0072.png"style="height:24px"/> is the <imgsrc="task2_media/0073.png"style="height:24px"/> column of <imgsrc="task2_media/0074.png"style="height:24px"/></li><li><imgsrc="task2_media/0075.png"style="height:24px"/> is the axis of rotation</li><li><imgsrc="task2_media/0076.png"style="height:24px"/> is the vector from the base of joint <imgsrc="task2_media/0077.png"style="height:24px"/> to the end point of the target joint</li></ul><p>For a more in-depth derivation of Jacobian transpose (and a look into other inverse kinematics algorithms), please check out <ahref="https://web.archive.org/web/20190501035728/https://autorob.org/lectures/autorob_11_ik_jacobian.pdf">this presentation</a>. (Pages 45-56 in particular)</p><p>Now, all of this will work for updating the angle along a single axis, but we have 3 axes to deal with. Luckily, extending it to 3 dimensions isn’t very difficult, we just need to update the angle along each axis independently.</p><h3id="multi-target"><ahref="#multi-target"class="anchor-heading"aria-labelledby="multi-target"><svgviewBox="0 0 16 16"aria-hidden="true"><usexlink:href="#svg-link"></use></svg></a> Multi-Target </h3><p>We’ll extend this so we can have multiple targets, which will then use the function to minimize:</p><center><imgsrc="task2_media/0078.png"/></center><p>which is a simple extension actually. Since each term is independent and added together, we can get the gradient of this new cost function just by summing the gradients of each of the constituent cost functions!</p><p>You should implement multi-target IK, which will take a <codeclass="language-plaintext highlighter-rouge">vector</code> of <codeclass="language-plaintext highlighter-rouge">IK_Handle*</code>s called <codeclass="language-plaintext highlighter-rouge">active_handles</code> which stores the information a target point for a joint. See <codeclass="language-plaintext highlighter-rouge">scene/skeleton.h</code> for the definition of <codeclass="language-plaintext highlighter-rouge">IK_Handle</code> structure.</p><p>In order to implement this, you should update <codeclass="language-plaintext highlighter-rouge">Joint::compute_gradient</code> and <codeclass="language-plaintext highlighter-rouge">Skeleton::step_ik</code>. <codeclass="language-plaintext highlighter-rouge">Joint::compute_gradient</code> should calculate the gradient of <imgsrc="task2_media/0079.png"style="height:18px"/> in the x,y, and z directions, and add them to <codeclass="language-plaintext highlighter-rouge">Joint::angle_gradient</code> for all relevant joints. <codeclass="language-plaintext highlighter-rouge">Skeleton::step_ik</code> should actually do the gradient descent calculations and update the <codeclass="language-plaintext highlighter-rouge">pose</code> of each joint. In this function, you should probably use a very small timestep, but do several iterations (say, 10s to 100s) of gradient descent in order to speed things up. For even faster and better results, you can also implement a variable timestep instead of just using a fixed one. Note also that the root joint should never be updated.</p><p>A key thing for this part is to <em>remember what coordinate frame you’re in</em>, because if you calculate the gradients in the wrong coordinate frame or use the axis of rotation in the wrong coordinate frame your answers will come out very wrong!</p><h3id="using-your-ik"><ahref="#using-your-ik"class="anchor-heading"aria-labelledby="using-your-ik"><svgviewBox="0 0 16 16"aria-hidden="true"><usexlink:href="#svg-link"></use></svg></a> Using your IK! </h3><p>Once you have IK implemented, you should be able to create a series of joints, and get a particular joint to move to the desired final position you have selected.</p></div></div><divclass="search-overlay"></div></div></body></html>
