Rational circular arc interpolation

Vectorspace GA
1

One neat thing that as far as I can tell is not very well known is that we can interpolate between three complex numbers a, m, b lying on a circular arc (m for midpoint) using the rational expression:

z(t) = \dfrac{(b - m)a\tilde{t} + (m - a)bt} {(b - m)\tilde{t} + (m - a)t}

Where we let \tilde{t} = 1 - t for convenience.

In computer graphics language (where “lerp” means linear interpolation):

z(t) = \dfrac{\operatorname{lerp}((b - m)a, (m - a)b, t)} {\operatorname{lerp}(b - m, m - a, t)}

This can be extended to arbitrary Euclidean vectors a, m, b, using GA for multiplication/inverses, but since the terms might not commute, we need to put the denominator q(t) = (b - m)\tilde{t} + (m - a)t separately into the middle of each term:

x(t) = (b - m)q(t)^{-1} a \tilde{t} + (m - a)q(t)^{-1} b t

Or asymmetrically,

x(t) = a + (m - a)q(t)^{-1} (b - a) t

This is computationally cheap (no trig! only one division per point), and while it is not arclength-uniform (except in the case where b - m = m - a, where it reduces to linear interpolation), if m is the midpoint on the desired circular arc between a and b then it behaves very nicely, especially when the arc is small. If a and b and the arc (e.g. via another point on it, or the circle center) are known, then the midpoint m can be computed with just one square root.

If someone really needs approximately arclength-linear interpolation for some reason, the function can be pre-composed with a very cheap rational approximation of tangent accurate to 5 digits:

\tan{\left(\tfrac{1}{2}\pi x\right)} \approx x \left(-0.0187108(1 - x^2) + 0.31583526 + 1.27365776 \frac{1}{1 - x^2}\right)

I’d love to hear if anyone knew the above, or if there has been any past literature about it. The only somewhat similar thing I can find is the obscure never-cited conference paper Xuexiang Li & Junxiao Xue (2014) “Circular Arc Representation based on Parametric Complex Functions”, LEMCS 2014, proposing it for use in CNC machining.

1 Like
2

I might add, for practical computation with vector values we can save work by first defining u = m - a, v = b - m, h = b - a, and then expressing our interpolating function as:

x(t) = a + \dfrac{t}{\operatorname{lerp}(v, u, t)^2}\operatorname{lerp}(uvh, u^2h, t)

The per-point runtime cost here is 2 vector lerps, 1 dot product, 1 scalar division, 1 scalar–vector multiplication, and 1 vector addition.

Or if dealing with general invertible multivectors, using the reverse (and writing |a|^2 = aa^\dagger):

x(t) = a + \dfrac{t}{|\operatorname{lerp}(v, u, t)|^2}\operatorname{lerp}(uv^\dagger h, |u|^2h, t)
1 Like
3

Perhaps related, I stumbled upon the idea that instead of using lerp(t, a, b) = a + (b-a)*t, you could ‘bump’ all of the operators and use exp_lerp(t, a, b) = a * (b/a)^t to get a rotational, instead of linear, interpolation. This was a leap that helped me to understand the relationship between lie groups and lie algebras, which are similarly related by upgrading or downgrading the operators to move between a curved space of destinations and a linear space of directions.