<!DOCTYPE html><htmllang="en-US"><head><metacharset="UTF-8"><metahttp-equiv="X-UA-Compatible"content="IE=Edge"><title>Splines - </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>Splines</title><metaname="generator"content="Jekyll v4.2.0"/><metaproperty="og:title"content="Splines"/><metaproperty="og:locale"content="en_US"/><metaname="twitter:card"content="summary"/><metaproperty="twitter:title"content="Splines"/><script type="application/ld+json">{"headline":"Splines","@type":"WebPage","url":"/animation/splines","@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 active"><ahref="/animation/splines"class="nav-list-link active">Splines</a></li><liclass="nav-list-item "><ahref="/animation/skeleton_kinematics"class="nav-list-link">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>Splines</span></li></ol></nav><divid="main-content"class="main-content"role="main"><h1id="spline-interpolation"><ahref="#spline-interpolation"class="anchor-heading"aria-labelledby="spline-interpolation"><svgviewBox="0 0 16 16"aria-hidden="true"><usexlink:href="#svg-link"></use></svg></a> Spline Interpolation </h1><p>As we discussed in class, data points in time can be interpolated by constructing an approximating piecewise polynomial or spline. In this assignment you will implement a particular kind of spline, called a Catmull-Rom spline. A Catmull-Rom spline is a piecewise cubic spline defined purely in terms of the points it interpolates. It is a popular choice in real animation systems, because the animator does not need to define additional data like tangents, etc. (However, your code may still need to numerically evaluate these tangents after the fact; more on this point later.) All of the methods relevant to spline interpolation can be found in <codeclass="language-plaintext highlighter-rouge">spline.h</code> with implementations in <codeclass="language-plaintext highlighter-rouge">spline.inl</code>.</p><h3id="task-1a---hermite-curve-over-the-unit-interval"><ahref="#task-1a---hermite-curve-over-the-unit-interval"class="anchor-heading"aria-labelledby="task-1a---hermite-curve-over-the-unit-interval"><svgviewBox="0 0 16 16"aria-hidden="true"><usexlink:href="#svg-link"></use></svg></a> Task 1a - Hermite Curve over the Unit Interval </h3><p>Recall that a cubic polynomial is a function of the form:</p><center><imgsrc="task1_media/0000.png"style="height:30px"/></center><p>where <imgsrc="task1_media/0001.png"style="height:24px"/>, and <imgsrc="task1_media/0002.png"style="height:20px"/> are fixed coefficients. However, there are many different ways of specifying a cubic polynomial. In particular, rather than specifying the coefficients directly, we can specify the endpoints and tangents we wish to interpolate. This construction is called the “Hermite form” of the polynomial. In particular, the Hermite form is given by</p><center><imgsrc="task1_media/0003.png"style="height:28px"/></center><p>where <imgsrc="task1_media/0004.png"style="height:16px"/> are endpoint positions, <imgsrc="task1_media/0005.png"style="height:16px"/> are endpoint tangents, and <imgsrc="task1_media/0006.png"style="height:24px"/> are the Hermite bases</p><center><imgsrc="task1_media/0007.png"style="height:30px"/><br/></center><center><imgsrc="task1_media/0008.png"style="height:30px"/><br/></center><center><imgsrc="task1_media/0009.png"style="height:30px"/><br/></center><center><imgsrc="task1_media/0010.png"style="height:30px"/><br/></center><p>Your first task is to implement the method <codeclass="language-plaintext highlighter-rouge">Spline::cubic_unit_spline()</code>, which evaluates a spline defined over the time interval <imgsrc="task1_media/0011.png"style="height:24px"/> given a pair of endpoints and tangents at endpoints.</p><p>Your basic strategy for implementing this routine should be:</p><ul><li>Evaluate the time, its square, and its cube (for readability, you may want to make a local copy).</li><li>Using these values, as well as the position and tangent values, compute the four basis functions <imgsrc="task1_media/0012.png"style="height:20px"/><imgsrc="task1_media/0013.png"style="height:20px"/> of a cubic polynomial in Hermite form.</li><li>Finally, combine the endpoint and tangent data using the evaluated bases, and return the result.</li></ul><p>Notice that this function is templated on a type T. In C++, a templated class can operate on data of a variable type. In the case of a spline, for instance, we want to be able to interpolate all sorts of data: angles, vectors, colors, etc. So it wouldn’t make sense to rewrite our spline class once for each of these types; instead, we use templates. In terms of implementation, your code will look no different than if you were operating on a basic type (e.g., doubles). However, the compiler will complain if you try to interpolate a type for which interpolation doesn’t make sense! For instance, if you tried to interpolate <codeclass="language-plaintext highlighter-rouge">Skeleton</code> objects, the compiler would likely complain that there is no definition for the sum of two skeletons (via a + operator). In general, our spline interpolation will only make sense for data that comes from a vector space, since we need to add T values and take scalar multiples.</p><h3id="task-1b-evaluation-of-a-catmull-rom-spline"><ahref="#task-1b-evaluation-of-a-catmull-rom-spline"class="anchor-heading"aria-labelledby="task-1b-evaluation-of-a-catmull-rom-spline"><svgviewBox="0 0 16 16"aria-hidden="true"><usexlink:href="#svg-link"></use></svg></a> Task 1B: Evaluation of a Catmull-Rom spline </h3><p>The routine from part 1A just defines the interpolated spline between two points, but in general we will want smooth splines between a long sequence of points. You will now use your solution from part 1A to implement the method <codeclass="language-plaintext highlighter-rouge">Spline::at()</code> which evaluates a general Catmull-Romspline at the specified time in a sequence of points (called “knots”). Since we now know how to interpolate a pair of endpoints and tangents, the only task remaining is to find the interval closest to the query time, and evaluate its endpoints and tangents.</p><p>The basic idea behind Catmull-Rom is that for a given time t, we first find the four closest knots at times</p><center><imgsrc="task1_media/0014.png"style="height:20px"/></center><p>We then use t1 and t2 as the endpoints of our cubic “piece,” and for tangents we use the values</p><center><imgsrc="task1_media/0015.png"style="height:24px"/><br/></center><center><imgsrc="task1_media/0016.png"style="height:24px"/><br/></center><p>In other words, a reasonable guess for the tangent is given by the difference between neighboring points. (See the Wikipedia and our course slides for more details.)</p><center><imgsrc="task1_media/spline_diagram.jpg"style="height:240px"/><br/></center><p>This scheme works great if we have two well-defined knots on either side of the query time t. But what happens if we get a query time near the beginning or end of the spline? Or what if the spline contains fewer than four knots? We still have to somehow come up with a reasonable definition for the positions and tangents of the curve at these times. For this assignment, your Catmull-Rom spline interpolation should satisfy the following properties:</p><ul><li>If there are no knots at all in the spline, interpolation should return the default value for the interpolated type. This value can be computed by simply calling the constructor for the type: T(). For instance, if the spline is interpolating Vector3D objects, then the default value will be <imgsrc="task1_media/0017.png"style="height:20px"/>.</li><li>If there is only one knot in the spline, interpolation should always return the value of that knot (independent of the time). In other words, we simply have a constant interpolant.</li><li>If the query time is less than or equal to the initial knot, return the initial knot’s value.</li><li>If the query time is greater than or equal to the final knot, return the final knot’s value.</li></ul><p>Once we have two or more knots, interpolation can be handled using general-purpose code. In particular, we can adopt the following “mirroring” strategy to obtain the four knots used in our computation:</p><ul><li>Any query time between the first and last knot will have at least one knot “to the left” <imgsrc="task1_media/0018.png"style="height:22px"/> and one “to the right” <imgsrc="task1_media/0019.png"style="height:22px"/>.</li><li>Suppose we don’t have a knot “two to the left” <imgsrc="task1_media/0020.png"style="height:22px"/>. Then we will define a “virtual” knot <imgsrc="task1_media/0021.png"style="height:22px"/>. In other words, we will “mirror” the difference be observe between <imgsrc="task1_media/0022.png"style="height:22px"/> and <imgsrc="task1_media/0023.png"style="height:22px"/> to the other side of <imgsrc="task1_media/0024.png"style="height:22px"/>.</li><li>Likewise, if we don’t have a knot “two to the right” <imgsrc="task1_media/0025.png"style="height:22px"/>), then we will “mirror” the difference to get a “virtual” knot <imgsrc="task1_media/0026.png"style="height:22px"/>.</li><li>At this point, we have four valid knot values (whether “real” or “virtual”), and can compute our tangents and positions as usual.</li><li>These values are then handed off to our subroutine that computes cubic interpolation over the unit interval.</li></ul><center><imgsrc="task1_media/evaluate_catmull_rom_spline.png"style="height:300px"/><br/></center><p>An important thing to keep in mind is that <codeclass="language-plaintext highlighter-rouge">Spline::cubic_unit_spline()</code> assumes that the time value t is between 0 and 1, whereas the distance between two knots on our Catmull-Rom spline can be arbitrary. Therefore, when calling this subroutine you will have to normalize t such that it is between 0 and 1, i.e., you will have to divide by the length of the current interval over which you are interpolating. You should think very carefully about how this normalization affects the value computed by the subroutine, in comparison to the values we want to return. A transformation is necessary for both the tangents that you feed in to specify the unit spline.</p><p>Internally, a Spline object stores its data in an STL map that maps knot times to knot values. A nice thing about an STL map is that it automatically keeps knots in sorted order. Therefore, we can quickly access the knot closest to a given time using the method <codeclass="language-plaintext highlighter-rouge">map::upper_bound()</code>, which returns an iterator to knot with the smallest time greater than the given query time (you can find out more about this method via online documentation for the Standard Template Library).</p><h3id="using-the-splines"><ahref="#using-the-splines"class="anchor-heading"aria-labelledby="using-the-splines"><svgviewBox="0 0 16 16"aria-hidden="true"><usexlink:href="#svg-link"></use></svg></a> Using the splines </h3><p>Once you have implemented the functions in <codeclass="language-plaintext highlighter-rouge">spline.cpp</code>, you should be able to make simple animations by translating, rotating or scaling the mesh in the scene. The main idea is to:</p><ul><li>create an initial keyframe by clicking at a point on the white timeline at the bottom of the screen</li><li>specify the initial location/orientation/scale of your mesh using the controls provided</li><li>create more keyframes with different mesh locations/orientations/scales and watch the splines smoothly interpolate the movement of your mesh!</li></ul><center><imgsrc="task1_media/animate_cow.gif"/></center></div></div><divclass="search-overlay"></div></div></body></html>
