Spherical linear interpolation, or SLERP, is widely used in computer graphis 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.
|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%.