Workbook 5 - Page 4: Arclength Parameterizations

4: Arc-Length Parameterizations

Arc length parameterization is discussed in Section 15.1.1 of Fundamentals of Computer Graphics - but this is a more intuition based description.

Box 1: Arc-length and non-arc length

We usually like to define our parameterizations such that each piece goes from 0 to 1. But this means that if we move at a constant speed in the parameter, the pen would move at a variable speed. An arc-length parameterization is a parameterization where the pen moves at a constant speed even if the parameter does.

For an example, consider a set of line segments that go around a rectangle. Let the 4 corners be p0, p1, p2 and p3, and let the rectangle be (20,20) to (120,40) (so it is 20 pixels high and 100 pixels wide). The most obvious parameterization has each line segment with a unit parameterization. The top segment would be 0-1, the right segment would be 1-2, the bottom segment would be 2-3, and the left segment will be 3-4. Each segment takes the same amount of "parameter", so if we change u at a constant rate, the pen will be moving 5 times faster in the horizontal segments than in the vertical ones. This is the red dot in the animation. (click the checkbox to start the animation, or scrub with the slider)

The green dot takes the same amount of time (t=0 to 4) to move around the rectangle, but it moves at a constant speed on the screen.

A way to think about it: consider measuring distance along the curve (starting at the zero point). The total curve (the perimeter of the rectangle) is 240 units. We can measure how far we've moved along the curve (from 0 at the start to 240 when we complete the loop). We could use this distance as the parameter (interpreting the parameter as "move this many distance units along the curve"). This is an arc-length parameterization. Because we're measuring distance with the parameter, if we move a certain amount of parameter, we will always move the same amount of distance along the curve.

Of course, we can scale things so that the units of distance match the range we have of the parameter - we can scale the parameter that goes from 0-4 so that each unit of parameter means 60 units of distance. But, the speed remains constant as we go around the rectangle. Each animation step is .05 units of parameter, and goes 3 pixels of distance (60 * .05). This is the same if we're on a long horizontal, or a short vertical. In contrast, using the per-segment parameterization, the speed was 5 pixels per step on the horizontals (100 * .05), and 1 pixel per step on the verticals (20 * .05).

Box 2: Another Arc-Length Example

Here's an even simpler example: a single, straight line segment in 1D. We have two parameterizations: f(u)=u and g(u)=u*u. Since u is in the range 0 to 1, both begin and end in the same place, and sweep out the same set of points (if we took infinitely small steps). With the two functions, the "pen" traces out the same curve (a line), but with different timings.

You should note that f (red dot) is an arc-length parameterization, while g (green dot) is not. F moves at a constant rate (assuming a constant rate for u), and g starts out slowly and speeds up.

The speed of the pen (how fast the dot moves for a given change in the parameter) is determined by the magnitude of the derivative of the position with respect to the parameter. For an arc-length parameterization, this is constant. Note that - so f has the same derivative everywhere, so it meets this definition. In contrast, which depends on u, and therefore changes as we move around the curve.

Box 3: Arc Length Re-Parameterizations

Arc-length parameterizations are often useful, especially when we are doing animation and want to have things move at a constant speed. However, it is usually easier to define curves in a way that is not an arc-length parameterization. We can then get an arc-length parameterization by re-parameterizing, define a function that converts from an arc-length parameterization to the given parameterization.

For example, in box 2, we could define a "reparameterization function" that allows us to convert an arc-length parameterization of the line into the parameterization given by the function g.

For a polyline (a connected set of line segments, as in Box 1), we can implement re-parameterization by building a table. For different values of the parameter (I'll use t as the parameter that goes from 0-4, and u as the parameter that goes from 0-1 for each individual segment), we can compute its distance from the start:

t distance
0 0
1 100
2 120
3 220
4 240

Now, given a distance, we can figure out the appropriate value of t. For example, if we want to know the parameter value for s=170, we can see that it falls between 120 and 220 in the table. Since it's half-way between 120 and 220, we know that it should be half-way between the corresponding t values (since we are doing linear interpolation). So, s=170 corresponds to t=2.5.

This works out easily for line segments, since we know that linear interpolation works (half-way in distance is half-way in parameter space), and that we only need entries in the table for the break points (where we switch segments), since linear interpolation holds between them.

For more complicated, non-linear functions, we can approximate the reparameterization function by sampling: we pick a set of values for t, compute the positions for each of these parameter values (which we can do because we have the parametric function), and then use the polyline connecting these points to approximate the distance. The larger the number of values of t we sample, the better the approximation that we get.

Here's an example for a parabola :

t x y distance (to previous) total distance
0 0 0 N/A 0
.2 20 4 20.4 20.4
.4 40 16 23.3 43.7
.6 60 36 28.3 72.0
.8 80 64 34.4 106.4
1 100 100 41.2 147.6

If we wanted to know where halfway in distance was (s=147.6/2=73.8), we look it up in the table and see that it's between t=.6 and t=.8. Since it is (73.8-72)/(106.4-72)=.052 of the way between rows, we can approximate that as .052*.2 (.2 is the step between rows of t)+.6 = .61.

You'll get to try implementing this to arc-length parameterize the train track when you get to the end of the workbook.

Exercise: Arc Length Parameterize Me!

Function myTri in 4-arclength.js goes around a 5,12,13 right triangle, but not in an arc-length parameterization. That's the red dot. Fill in the function myTriAL that goes around the same triangle, but with an arc length parameterization. You only need to modify myTriAL. You may use other functions defined in the file.

Summary: Arc-Length Parameterization

Hopefully, you now have an intuition for what arc-length parameterization is, so you can read the mathematical definition in the textbook, and implement it for your train (when you get there).

Now, on to Page 5!