Understanding the Spiro Spline

Question

My name's Wray. This is my first time here.

Firstly, I like curves. I've been keeping a pet project for a long time that would implement a delightful new curve-interpolation algorithm named the Spiro Spline. The details of the Spiro are laid out in Raph Levein's PHD paper, "From Spiral to Spline: Optimal Techniques in Interactive Curve Design". Have a look at that first.

My problem is that I am a programmer and not a mathematician. Almost all my experience with math is algebraic (with loops). I've tried reading the paper a bunch of times but I'm flunking at understanding what's going on.

How can I get started on understanding what Levein is doing? (This question is open-ended and I apologize for that) I'm not as interested in the later parts of the paper where the spiro curves are converted to bezier curves. I'm just trying to understand his spiro function.

$$ spiro({ k }_{ 0 },{ k }_{ 1 },{ k }_{ 2 },{ k }_{ 3 })=\int _{ -0.5 }^{ 0.5 }{ { e }^{ i({ k }_{ 0 }s+\frac { 1 }{ 2 } { k }_{ 1 }{ s }^{ 2 }+\frac { 1 }{ 6 } { k }_{ 2 }{ s }^{ 3 }+\frac { 1 }{ 24 } { k }_{ 3 }{ s }^{ 4 }) } } $$

I'm not sure what $k$ is or why it has four sub-components. My best guess is that ${ k }_{ 1 }$ and ${ k }_{ 2 }$ are two nodes between which the curve in question lies, while ${ k }_{ 0 }$ and ${ k }_{ 3 }$ rest beyond those? My logic breaks down for a set of only two or three points.

I recognize the integral symbol, but I didn't learn about it in school. Moreover, I'm concerned that they don't translate well to programming languages. I've showed the paper to a few people that know this sort of stuff. They say things like "Oh, he's just using a bunch of pre-computed constants." What does that mean?

I do understand the concept of a function. For example, a Bezier/Casteljau spline takes multiple $(x,y)$ coordinates, a variable $t$ from $0$ to $1$ and returns a new $(x,y)$ coordinate that will be along that curve. Making the curve show up on the screen is as simple as running the function a bunch of times for $0$, $0.1$, $0.2$, ... $1$ and connecting the dots.

If I had bounty to hand out on math.stack, I totally would. I've been trying at this for a long time on my own. Any help, suggestions, links to tutorials, or anything else are welcomed and much appreciated. :)

---

Update 1 year later: I had a chance to meet Raph Levien in person. We geeked out about this and it was amazing. Funny enough, I'm still not quite sure I understand it all, but I did join Khan Academy and I'm determined to make sense of it this year.

Answer 1

If you're a programmer, not a mathematician, you'd probably be better off reading the code, rather then the thesis. He provides both Python and Javascript versions.

But, to answer your question about the integral ...

Right after that equation, he explains what $k_0,k_1,k_2,k_3$ are. They are the curvature and its first three derivatives at the mid-point of the curve. More specifically, $k_0$ is the curvature at the mid-point, $k_1$ is the derivative of curvature with respect to arclength, $k_2$ is the second derivative of curvature with respect to arclength, and so on. He says that figuring out the shape of the desired curve requires calculation of this integral. Informally, if we know about curvature, and how fast it's changing, we should be able to determine the shape of the curve, right (though it's not easy). There are some worked examples later in chapter 8.

This is the most general form of the "spiral" curves the thesis considers. One important special case is when curvature is a linear function of arclength ($k_3=k_2=0$). This gives you the Euler spirals that are covered in chapter 6.

You might say that defining a curve by giving curvature derivatives at its mid-point is a pretty strange approach, and I'd tend to agree. This choice is just to make the subsequent math work out more nicely, it seems. These curvature values aren't used in the user interface -- they are just for computational purposes.

If you don't have much mathematical background, maybe you should start with a simpler approach to curve design. There are several much simpler approaches that give very nice results. One example is John Hobby's approach, which is discussed in section 4.7 of Levien's thesis.

Answer 2

Visited this answer and would like to share my understanding of it.

The first thing is that there is a common representation of a curve (applies to but not limited to splines) as $\theta(s)$, a.k.a. imagine if you walk along the curve for a distance of $s$ (here $s$ is called the longitudinal distance), $\theta(s)$ will be the angle you are facing.

Here are some examples

1. $\theta(s)=0$ is a straight line parallel to the x-axis.
2. $\theta(s)=\frac{\pi}{4}$ is a straight line pointing to the 45 degree angle
3. $\theta(s)=\frac{s}{r}$ is a circle with radius $r$

Now, what is the curvature at the point $s$? Remember curvature is the rate of the changes in angle along the curve, which is just $\dot{\theta}(s)$.

In the above examples:

1. $\dot{\theta}(s) = 0$, consistent with our intuition as the curvature of the straight line is zero.
2. Similarly, the curvature is $\dot{\theta}(s)=0$ because it is a straight line.
3. For the circle the curvature $\dot{\theta}(s) = \frac{1}{r}$. The curvature of the circle is a constant, and that is intuitively why the inverse of the curvature is called the radius of the curvature for a general curve.

The next question is about how to get the 2D coordinates of the curve given $\theta(s)$, assuming the start point (i.e. at $s=0$) is $(0, 0)$. Note that (informally) we can interpret $\theta(s)$ as at the point $s$ if you go along the curve you will move towards the direction $\theta(s)$ with a very small distance $\mathrm{d}s$, and therefore the vector (complex) form of the movement is $[\cos(\theta(s)) + i \sin(\theta(s))] \cdot \mathrm{d}s = e^{i\theta(s)} \mathrm{d}s$. Therefore it follows that by integrating along the curve from $0$ to $s$ we get the point on the curve we are at, by $\int_0^{s} e^{i\theta(s)}\mathrm{d}s$.

Now let's look back on the spiro equation. Apparently in that integral,

$\theta(s) = k_0 s + \frac{k_1}{2}s^2 + \frac{k_2}{6} s^3 + \frac{k_3}{24} s^4$

Note that here $s=0$ is the mid point. And by taking the derivatives of $\theta(s)$ we have

1. $\dot{\theta}(s=0) = k_1$
2. $\ddot{\theta}(s=0) = k_2$

and so on. Which can be directly translated as at the mid point ($s=0$), $k_1$ is the curvature, $k_2$ is the derivative of the curvature, and so on.