Page 1: A curve review

CS559 Spring 2021 Sample Solution - Workbook 6

Written by CS559 course staff

You can try out the example solutions here. The interesting code is on page 3.

Workbook 5 and the lectures introduced the key ideas of curves. On this page, we’re going to review some of the main ideas, and will have a little bit of practice to help make sure you understand the concepts for use on the train.

Outline of Curve Topics

The main points in the workbooks / lectures about curves:

  1. The idea of curves, and their basic definitions.
  2. The idea of parametric representations - where we describe curves as a function of a free parameter.
  3. The idea of tangents and, more generally, the derivatives of curves.
  4. The idea of continuity, where we talk about how curve pieces connect to make bigger curves.
  5. The idea of splines or piecewise polynomial representations, which are the most common way we represent curves in computer graphics.
  6. The idea of using cubic polynomials for the curve pieces, which is the most common thing we do in computer graphics.
  7. The idea of using Hermite interpolation to give easy control over cubics by specifying the beginning and end of each segment.
  8. The idea of using cardinal interpolation to give easy control over Hermite interpolation by computing the derivatives from the point positions. Catmull-Rom splines are an important special case.
  9. The reasons why we prefer to do interpolation by using a piecewise polynomial (like a cardinal spline), rather than fewer higher-order pieces. (this was emphasized more in the book and lecture)
  10. The reasons why we often prefer approximating curves to interpolation, to give us better control of a curve shape.
  11. The nice properties of Bézier curves that make them a very popular choice in graphics applications.
  12. The geometric derivation of Bézier with the DeCastlejau construction which provides us with intuitions for how the curves work, but also practical algorithms.
  13. The specific form of Bézier Cubics, which resemble Hermit cubics and are very common in graphics applications.
  14. The Basis Functions of Bézier curves, which provide a way to evaluate the curves and a sense of the mathematical elegance.
  15. How Bézier curves are applied in the APIs we use.
  16. The idea of arc length parameterizations of curves, where the length of the curve is used for parameterization, allowing for the parameter to have a more direct connection to location.

These are all important, and it’s a lot, so some practice may be worthwhile.

Drawing Cardinal Splines

Cardinal splines are very useful, but they are not built into the Web APIs. This isn’t a problem because it is easy to convert Cardinal segments to Bézier segments, and APIs can draw Béziers well.

To practice that, here is a Cardinal Spline to draw. In this figure there are 5 points to connect with a Cardinal spline - we’ve drawn line segments between the points rather than Cardinals. Replace the line segments with Cardinal splines, so that the picture is $C(1)$. Use Catmull-Rom splines (cardinals with t=0, or s=0.5).

There are two catches here:

  1. Canvas doesn’t have Cardinal Splines - you must convert each Cardinal segment to a Bezier segment. You need to replace each of the lineTo commands in 06-01-01.js with a bezierCurveTo command, and compute the positions of the control points.
  2. The spline is “looped” - the last point connects to the first. This means when you need to get the “next” point after the last point, you go around the loop.

Edit 06-01-01.js to do this exercise - you shouldn’t need to change 06-01-01.html.

Observe how the the cardinal spline does not fit within the original “control polygon”. You will have Bézier control points outside of the original cardinal control polygon - since the Bézier curve does stay inside of its control polygon.

Bézier Curve Algorithms

We discussed both algebraic ways to compute Bézier curves (the blending function polynomials), and geometric approaches.

Using the blending functions may be easier/faster for computing values in a program. I find it easier to use DeCastlejau when I have to compute things by hand. The DeCastlejau algorithm is useful when we need to split curves, and it has the advantage that it provides us with the tangents as part of the computation process.

To practice with using the DeCastlejau algorithm, take the curve in this figure 06-01-02.svg and split it into three parts with even parameter amounts (e.g., u=1/3 and 2/3). Take the one curve in the picture, and replace it with 3 curves that are different colors (make the first one red, the second one green, and the third blue) - that are geometrically the same curve. We need to make separate curves because in SVG we haven’t learned to make a single curve that is three colors. (even if you know how to do that, don’t - we will check that your result has 3 separate path statements).

for_students/06-01-02.svg

Round numbers to integers (when you do the computations, you will get 1/3rds).

Arc-Length Parameterizations

Arc length parameterizations are a tricky concept.

Consider what “arc length” is (before we get to parameterization): it is the length along the curve. Imagine if you wrap a tape measure along the curve to measure how “long it is”; or you straighten out the curve to measure how long it is.

Given the idea of arc-length, you can think about its connection to parameterizations. Normally, we think about the length of the whole curve. But, given a curve $\mathbf{f}(u)$, we could consider the “first part of the curve starting at 0 and going to $u$”, and create a new function $a(u)$ which is the arc length of that curve. Every parameter value $u$ corresponds to some distance $a(u)$.

Arc length parameterization reverses this process: we use the distance along the curve as the parameter. We specify the distance $s$ (the arc length parameter), and compute the “regular parameter” from this using the inverse of the $a$ function above, $u=a^{-1}(s).$ Because this function changes from one parameterization to another, we call it a reparameterization. You could imagine a new “curve function” $\mathbf{f_s}(s)=\mathbf{f}(a^{-1}(u))$ that is an arc length parameterization of the original $\mathbf{f}$ - it’s the same curve, except with an arc length parameter.

You should notice that doing arc length parameterization (or reparameterization) requires not just finding the arc length function $a(u)$, but its inverse. Computing the arc length is hard enough - it requires solving an integral to compute the length, which usually cannot be done analytically. In practice, we usually estimate $a(u)$ using numerical techniques, and estimate it’s inverse using numerical techniques.

Why use arc length parameterization?

It may be best to think in terms of the “pen” as a moving object. With a regular parameterization, the curve may speed up and slow down. With an arc-length parameterization, the “speed” (the magnitude of the velocity) is constant.

Consider a simple example: a cubic $\mathbf{f}(u)=[u,u^2]$. The 1st derivative of this curve (tangent, or velocity if we think about the curve as the pen moving along the curve) is $\mathbf{f'}(u)=[1,2u]$. At the beginning of the curve the velocity is [1,0], at the end it is [1,1]. The pen “sped up” as it moves along the curve.

Another way to think about it: if we take uniform steps in $u$, the steps we take in the world will be differently sized. Here’s a simple example, taking 10 steps along $u$ (0, .1, etc) and drawing this curve. (see 06-01-03.html and 06-01-03.js). Notice how the steps towards the end are longer than the steps at the beginning.

An arc length parameterization would trace the same curve, but with even steps. The way to think about it is a way to change parameters - we make $s$ (the arc length parameter) move in even steps, and compute the corresponding $u$ values. We just need to come up with a reparameterization function $u=g(s)$ that does this. We can think of $s$ as being distance along the curve (hence the name arc-length parameterization).

In general, these functions are hard to derive analytically - we need to use numerical approximations. Even for this really simple parabola, the arc-length is a complicated function. In Workbook 5, we looked at how to compute a table of approximate arclengths to approximate $s$ (distance along the curve) from $u$. Given the table, we can use lookups and interpolation to find the inverse.

On to the Train!

Next: The Train: Intro

Page 1 Rubric (20 points total)
Points (20):
Box 06-01-01
10 pt
Make a cardinal spline through the points
Box 06-01-02
10 pt
Split the Bezier