Clothoids: The Ideal Curve

 

It’s funny.  A hundred years ago engineers had a perfectly good, mathematically robust means of drafting curves.  Curvature was easy to control, with specialized spline sets and curve templates (e.g. French curves) that made smooth curved shapes easy to make.

And then Bezier came on the scene, followed by de Boor, and set engineering drafting back to the dark ages.  Modern computers can replicate the robustness and ease of traditional drafting tools, but this wasn’t true at the dawn of CAD in the late 60s.  The need for fast, simple algorithms drove first Bezier, and then de Boor to embrace the idea of polynomial-based splines.

Simple polynomial splines have an enormous number of problems.  They can’t be represented in arc length form.  It is extremely difficult to control their curvature, which is often “wavy.”  But most of all it just doesn’t make sense mathematically to split curves into independent x, y, and z functions.

Traditional drafting understood this.  The wooden splines of old guaranteed curvature continuity in a way that’s very difficult to do with simple polynomials today.  Curve templates were based on the “ideal elastica”, which was alternatively called the clothoid, the Cornu spiral, the Euler spiro, and the French curve (in the art world).

The Ultimate Curve: The Clothoid

FrenchCurve
Example of a polynomial clothoid

A better way to represent splines (and easily handled by modern computers) is to define the type of curvature function you want and integrate backwards.  For example, in civil engineering the three basic shapes are clothoids (whose curvature function is linear), circular arcs (constant curvature) and lines (zero curvature).  Given these constraints, we can design a spline function that can represent all three: the linear interpolation function.

k = c_1(1.0-t) + c_2t

Where c_1, c_2 are constants and t is a point on the curve in parameter space (It’s actually a bit more useful to use a cubic polynomial for curvature, but that’ll come later).

Yes, this one curve can do lines, arcs, and clothoids.  To integrate it in 2D, all we do is plug it into the following formula:

th = \int_0^t k(t) dt

x = \int_0^t sin(th) dt

y = \int_0^t cos(th) dt

Note that th can be integrated analytically, but x and y must be integrated numerically.  This isn’t terribly difficult on modern computers, especially since there’s a pretty easy to trick to integrating any arc-length-parameter plane curve.

So we now have a curve whose curvature starts at c_1 and ends at c_2.  But it isn’t very useful yet.  We need to control the start and end points of the curve.  For that, we just take a page from Raph Levien’s book and simply rotate, scale, and translate our curve to fit between whatever two points we want.

So now we have a function that takes two spatial points, p_1 and p_2, and two curvature points, the point t in parameter space.  It outputs a point along the curve in space, along with the rotation and scaling necessary to fit the curve between its two endpoints.

But this isn’t good enough.  We want to string several of these curves together, and we want to enforce constraints at shared vertices: tangential continuity, curvature continuity, whatever we want.  For basic G2 continuity we have six constraints at the endpoints of each curve segment: the segment must span two points in space, have shared tangents with adjacent curves and shared curvatures.  We’ve eliminated two of these constraints by how we’ve formulated the curve, leaving us with four.  This leads us to Raph Levien’s idea of using a cubic polynomial for our curvature function.  It doesn’t matter what form the polynomial takes; I like to use 1D Beziers myself, but you also use a four-segment piecewise-linear function if you want.

We can represent the cubic like this:

lt(a, b, t) = a(1.0-t) + bt

cubic = lt(lt(lt(c_1, c_2, t), lt(c2, c3, t)), lt(lt(c_2, c_3, t), lt(c3, c4, t)), t)

Which is the “intuitive” form of the Bezier polynomial.  One can also use more traditional Bernstein basis functions to get the same equation:

b(v, n) = binomial(n, v)x^v(1 - x)^(n-v)

cubic = b(0, 3)*x + b(1, 3)*x^2 + b(2, 3)*x^3

Or we could dispense with interpolation formulas entirely and just use a raw cubic:

cubic = c_1 + c_2*x + c_3*x^2 + c_4*x^3

I like the Bezier (Bernstein) form as the curvature at the endpoints is equal to the first and last coefficients.

Numerical Integration

Integrating this curve isn’t terribly difficult.  This is due to a nice property of arc-length parameter curves, where every point in t space is equally spaced from the last.

normal = conjugate(tangent) * k

dx = sin(th) dt

dy = cos(th) dt

d^2x = dy * k

d^2y = -dx * k

Thus, the higher derivatives are all functions of the first derivative the curvature function and its derivatives.  This makes it easy to construct a Taylor approximation.

f(x) = dx * x - \frac{dy * k}{2}x^2

f(y) = dy * x + \frac{dx * k}{2}x^2

Quadrature

However, a simple Taylor approximation will not work.  We need to use it in a quadrature.  For example, we might do something like this bit of python code:

def quadrature(t):
  steps = [some number of steps, e.g. 5]
  s = 0
  ds = t / steps
  x = 0
  y = 0
  
  for i in range(steps):
    k = curvature(s)
    th = [integral of k]
    
    dx = sin(th)
    dy = cos(th)

    x += dx*ds - 0.5*dy*ds*ds
    y += dy*ds + 0.5*dx*ds*ds

    s += ds
  return [x, y]

This might be wrapped in another function, that fits the clothoid between points p1 and p2:

def getpoint(t, p1, p2):
  start = quadrature(0.0)
  end = quadrature(1.0)
  vector = end - start
  
  angle = atan2(vector.y, vector.x)
  scale = length(p1 - p2) / length(vector)

  p = quadrature(t) - start
  p = rotate(p, angle)
  p = scale(p, scale)
  p = p + p1;

  return [p.x, p.y, scale, angle]

 

Practical Splines

Now it’s time to build a spline out of these curves.  To do so we need some way of maintaining continuity of the vertices.  The idea is to build a list of constraints, e.g. tangent constraint, curvature constraint, etc (see page 119 of Raph Levien’s phd thesis).  Then use any non-linear constraint solver to solve them.  The number of parameters in the curvature function should be equal to the maximum number of constraints.

Each constraint outputs an error value.  For example, a tangent constraint would take two segments, and return the angle between the tangents at their shared vertex.  A curvature constraint would return the difference between the curvatures at the vertex (made sure to put the curvature in global space by dividing by the scale that was returned in getpoint).

For a non-linear constraint solver, you can use pretty much anything.  I like to use a modified version of the Geiss-Seidal solver from this game physics paper.  It’s very flexible  and doesn’t require that the number of constraints and parameters perfectly match.  Raph Levien uses a simple Jacobian method of multiplying the parameters by the inverse of the constraint matrix Jacobian.

Results

What you get is a nice, pretty looking spline that’s incredibly versatile.  It’s useful for everything from designing high-speed rail networks to vector graphics to even 2D animation.

bunny

 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s