A Fast Algorithm for Computing SLERP


Spherical linear interpolation, or SLERP, is widely used in computer graphics to interpolate between rotations represented as quaternions. In Cesium, we use it for camera flights and model animations like the dancing reindeer in NORAD Tracks Santa. When there are many animations in a frame, SLERP often shows up on the profiler. It’s not the top bottleneck, but it’s something we’d like to make faster.

Like most SLERP implementations, our original implementation uses acos and two calls to sin. In the paper A Fast and Accurate Algorithm for Computing SLERP, David Eberly shows how to eliminate these trig functions. The key insight is the similarity between a property of Chebyshev polynomials and the coefficients of the quaternions in the SLERP equation. Chebyshev polynomials are solutions to a second-order linear differential equation. By using the power series solution to the equation, we can replace the trigonometric funtions with a series of multiplications and additions, which is where we see an increase in performance.

The paper contains CPU/FPU implementation that shows a 2x performance gain and Intel SSE implementation that shows a 10x performance gain. In our JavaScript port, we saw an almost 2x performance gain in Chrome. The following performance measurements are for four different implementations: the original using the SLERP equation and trig functions, the FPU implementation ported from Eberly’s paper using JavaScript arrays, the same implementation using JavaScript typed arrays, and the same implementation using constants.

Chrome Firefox
Original 0.278 0.231
Fast with JavaScript arrays 0.185 0.219
Fast with typed arrays 0.179 0.230
Fast with constants 0.148 0.158

The measurements were obtained using Performance.now and the units are in microseconds. (To use the high resolution timer in Chrome on Windows, use the --enable-high-resolution-time command line option.)

We chose to use the typed arrays. Though the version using constants instead of arrays is faster, the array version is more readable and easier to understand. The typed array version of the algorithm is slightly slower in Firefox, but we expect they will only get faster in the future.

Testing the new algorithm in an app with a model containing 120 animations that used SQUAD (calls SLERP 3 times) for quaternion splines, the percentage of time spent in SLERP for the frame decreased from 0.52% to 0.33%.

Get started with a Cesium ion account

Sign up for free