Intro to Computer Graphics - Snowboarder Animation
What is it?
This animation of a snowboarder traveling down a mountain is my final project for Professor Hanocka's Intro to Computer Graphics class. My submission attained a perfect score with additional extra credit, was ranked in the top 10 submissions for the class, and received a special prize from Pixar.
While the animation itself is pretty decent, the truly impressive part of this project is the crazy set of computer graphics algorithms in the backend. I highly recommend you continue reading this page and check out my code to learn more!
What is the goal of this project?
For the final project for Intro to Computer Graphics, we were given an incredibly broad prompt: create a 10 second animation.
However, along with this prompt came some additional stipulations.
First, our animation must be generated entirely through a Python script using the Blender Python API.
Second, our animation's Python implementation must include at least 1 point worth of computer graphics algorithms. For reference, the assignment sheet for this project listed a number of graphics algorithms with varying point totals between 0.5 and 2 corresponding to the difficulty in implementation of each algorithm. If a student implements more than 1 point worth of algorithms, the extra points count towards extra credit.
What did I do?
For this project, I opted to animate the motion of a snowboarder using 2 sets of algorithms.
First, I implemented a bunch of different splines to control the snowboarder's motion. These splines include B-Splines, Bezier Splines, Hermite Splines, Cardinal Splines, and Catmull-Rom Splines.
Second, I implemented Least Square Conformal Mapping (LSCM) to create UV maps for various meshes. Also, to help use this algorithm, I implemented a system based on Blender's "seams" system so users can manually modify their meshes to give them disc topology, which is necessary in order for LSCM to work. I used this algorithm to texture the snowboard with a fun picture of the Pixar lamp.
Splines - 0.5 points
Splines are piecewise parametric curves created from inputted control points.
All of my code for the various splines I implemented can be found in the file interpolation.py in the GitHub repository linked at the bottom of this page.
When classifying splines, the following properties are usually considered:
Interpolation - whether the curve passes through all of the control points, only some of them, or none of them at all.
Locality - whether a change in one area of the spline will affect the entire spline or only some small region around that area.
Non-local splines are incredibly annoying to use, so I opted to implement only local splines. If you want to learn more about non-local splines, check out Natural Splines!
Geometric Continuity (G Continuity) - whether the directions of the tangent vectors are continuous at every point in the curve.
For example, a G2 continuous spline would have the first and second derivatives have continuous directions, though the magnitudes of tangent vectors may not be continuous.
Parametric Continuity (C Continuity) - whether the magnitude and direction of the tangent vectors are continuous at every point in the curve.
For example, a C2 continuous spline would have the first and second derivatives have continuous magnitudes and directions.
By this definition, parametric continuity implies geometric continuity, so for every natural number n, a Cn continuous spline is necessarily also Gn continuous.
Additionally, by this definition, for any natural number n, a C(n+1) continuous spline is necessarily also Cn continuous. Same applies for a G(n+1) continuous spline and Gn continuity.
Control - how many factors the user can change in a given segment of the spline.
This is typically represented through "Degrees of Freedom," but that terminology is a bit confusing in my opinion, so I will not use that here and I will instead describe what factors users can use to tweak these curves.
Ease of use - a more subjective classification concerning how much information users need to provide in order to use the spline.
This classification is typically at odds with Control, as more ways to modify spline curves typically come at the cost of the spline requiring more information.
A B-Spline is a spline that generates an incredibly smooth curve loosely based on inputted control points, though without passing through these points.
B-Splines have the following properties:
This is the primary drawback of B-Splines!
Moving a control point only affects the section of the curve near that control point.
Really nice, smooth curves!
The curve is solely guided by the control points in a manner reminiscent of the control points pulling on the curve. This pseudo-interpolation is the only control users get.
Somewhat easy to use
Simply supply the control points, and a beautifully smooth curve will generate guided by these points!
The lack of interpolation can make these splines a bit annoying to use, however, as you can never definitively tell which points the spline will go through.
Bezier Splines allow users to define curves via a mixture of interpolation and non-interpolation points. The curve will always pass through the interpolation points, while the curve will only receive guidance from the non-interpolation points.
This mixture of interpolation and non-interpolation points gives users a ton of control over the curves generated by Bezier Splines, which is why these splines are the most popular splines in computer animation.
For this reason, I used Bezier Splines to guide the path of the snowboarder, as the snowboard needs to hit certain keyframe positions, but it also needs to travel along the mountain without passing through the ground. The increased control of Bezier Splines allowed me to guide the snowboarder around the mountain in a way that did not permit the snowboarder to pass through the floor.
In the backend, these splines are implemented via De Casteljau's algorithm, which is really cool! This algorithm uses chained linear interpolations between adjacent pairs of control points to guide the curve and influence it by an equal amount with each non-interpolation point.
Bezier Splines have the following properties:
Some control points act as interpolation points while others only guide the curve. The ratio of interpolation to non-interpolation points is guided by the degree of the curve. Typically, Bezier Splines are used with a degree of 3, meaning there are 2 non-interpolation points between every pair of interpolation points.
Changes to non-interpolation points only affect the curve segment between the 2 nearest interpolation points.
Changes to interpolation points only affect the previous and current curve segments (if such segments exist, which is always the case except at the start and end of the curve).
Only C0 continuity is guaranteed, though it is reasonably easy to impose at least C1 continuity for a degree 3 Bezier Spline by restricting the first of the 2 non-interpolation points between every 2 interpolation points.
Lots of control
The interpolation points allow users to choose exactly what points they want their curve to cover.
The non-interpolation points allow users to further guide their curves to shape them as they would like.
Simple but tedious to usesp
While it's nice to have the extra control of non-interpolation points, providing 2 extra points of information for every given interpolation point (assuming degree 3) is a substantial increase in work.
Hermite Splines allow users to specify control positions and first derivatives to create curves that move into guided positions using guided directions.
In the backend, Hermite Splines are actually just degree 3 Bezier Splines, though with a different interface. Instead of directly specifying the non-interpolation points of Bezier Splines, those points are determined automatically based on the first derivatives.
Hermite Splines have the following properties:
Interpolates between all control points
Lots of control, same as Bezier Splines.
Easy to use on paper but difficult in practice
While, in theory, these splines should be very simple to use, as users get to specify exactly how they want the curve to flow at specific points, in practice, people often struggle to classify the first derivative, making these curves challenging to use.
As a result, these curves are more helpful to use in the backend of other more simple splines.
Cardinal and Catmull-Rom Splines
Cardinal and Catmull-Rom Splines are Hermite Splines where the first derivatives are automatically determined from the positions of the previous and next control points, providing less control but easier usage.
Cardinal Splines provide some additional control through a tension parameter that is constant throughout the entire curve.
Catmull-Rom Splines are Cardinal Splines with 0 tension when the control points are uniformly distributed along the parameter space (evenly spaced t-values).
Because these splines allow you to create curves by only specifying control points, they are incredibly easy to use, which is why I opted to use them to move the camera, spin the camera, and spin the snowboarder in the animation.
Cardinal and Catmull-Rom Splines have the following properties:
Interpolated between all control points
Cardinal Splines only offer control through the positions of the control points and the global tension parameter.
Catmull-Rom Splines only offer control through the positions of the control points.
Really easy to use
Users just need to specify the control points (and the tension for a Cardinal Spline), and the rest of the curve will generate automatically.
One caveat of this is that since the first derivatives at each control point are determined in the backend by the previous and next control points, the first and last control points will be excluded since there is not enough information to set their first derivatives. Users need to remember that the first and last control points only guide the curve and are not interpolated like the other points.
Least Square Conformal Mapping (LSCM) - 2 points
LSCM is a common method of producing a UV map for a mesh.
A UV map is a way of mapping the 3D vertices of a mesh to a 2D plane. Mapping vertices in this manner allows for a bunch of really useful things, such as texture mapping and bump mapping.
This specific method of creating a UV map is special in that, as the name suggests, it produces conformal, or angle-preserving, maps.
One caveat of LSCM is that it only works when the mesh is wholly connected and has a disc topology. If the mesh does not have a disc topology, the algorithm will map every point onto the same line. If the mesh is not connected (meaning there are different parts of the mesh that can be separated), the equation at the end of the algorithm will not have a solution.
To help with the disc topology issue, I implemented Seams, which allow users to manually divide individual edges that are between 2 halfedges into 2 separate edges, one for each halfedge (in my implementation, meshes use the halfedge data structure). However, I only learned about the connectivity issue right before the project deadline, so I did not have time to implement a solution for that. Theoretically, however, users can manually split their meshes into connected disc segments and run this algorithm on each segment to create a UV map for any mesh, provided the user uses Seams to reduce each segment to a disc topology. In fact, that is the method I used to create the UV map for the snowboard. The top and bottom halves of the snowboard each called this algorithm separately as their own meshes and the resulting UV maps were spliced together horizontally to create a UV map for the entire snowboard.