SplineLibrary
A C++ library created to provide open-source reference implementations of many spline functions, e.g. Natural Splines and Catmull-Rom Splines. It's a challenge to find well-documented and FOSS implementations of these useful tools, and mathematical defintions of these things are really hard to decipher, so my hope is that this library will provide a starting point for others.
A spline is a formula for smoothly transitioning from one data point to the next in a data set. For example, you could create a spline containing ten colors (each stored as R, G, and B values) to create a color gradient that smoothly transitions from one color to the next.
Example
Create a Catmull-Rom Spline with four data points, and compute the interpolated position at T = 0.5
std::vector<QVector2D> splinePoints{
QVector2D( 0, 0),
QVector2D( 5, 0),
QVector2D( 8, 3),
QVector2D( 6, 1),
};
UniformCRSpline<QVector2D> mySpline(splinePoints);
QVector2D interpolatedPosition = mySpline.getPosition(0.5f);
Features
- Interpolation of catmull-rom splines
- Include
spline_library/splines/uniform_cr_spline.h
, create aUniformCRSpline
object, and call itsgetPosition
method. - Several more spline types. See Spline Types for the full list
- Include
- Looping Splines
- Also called "Periodic" or "Cyclic": These splines form a loop, in that the ending connects with the beginning
- Calling getPosition(t) with an out-of-range T value will "wrap around" to the other end of the spline
- To make a looping catmull-rom spline, include
spline_library/splines/uniform_cr_spline.h
and create aLoopingUniformCRSpline
object. - Every spline type has both looping and non-looping variants
- Compute the arc length of a spline
- Call a spline's totalLength() method to find the arc length of the entire spline
- Call a spline's arcLength(a,b) method to find the arc length between two arbitrary T values
- Compute the inverse of a spline
- Given a data point (not necessarily on the spline, or even close to it), what T value brings the spline closest to that data point?
- Create a SplineInverter object and call its findClosestT method
- Computation of the first, second, and third derivatives of the spline
- The first derivative is called the "tangent" - this is how quickly and in what direction the interpolated position is changing, per T
- The second derivative is called the "curvature" - this is how quickly and in what direction the interpolated tangent is changing, per T
- The third derivative is called the "wiggle" - this is how quickly and in what direction the interpolated curvature is changing, per T
Documentation
Glossary - Glossary of important terms for understanding splines.
Spline class API - API documentation of the Spline
base class.
Spline Types - Complete list of all supported spline formulas
Spline Utilities - Documentation of some utility classes for splines.
Project Layout
The root of the repository is a Qt Creator project that demonstrates some uses of the library. The source for the spline code itself is in the "spline_library" directory, and the code to set up the demo is in the "demo" directory.
Usage
Drop the spline_library directory in the root source folder of your project. It's header-only, so from here all you need to do is import it from your own code.
spline_library/spline_inverter.h
and spline_library/arclength.h
depend on Boost's Math module. If you don't want to install Boost, you can safely avoid including these two files - nothing else includes it, and nothing else relies on Boost.
Both the demo and the spline_library code require a fully compliant C++14 compiler.
Demo
Follow these steps to run the demo (Assuming you already have Qt 5.5+ installed and working):
-
Install Boost. On Linux, this is in most package managers. On Mac, it can be installed via homebrew. Otherwise, visit http://www.boost.org/
-
Create a file called
SplineDemo_Include.pri
in the root of the project -
In this file, paste the following, where
/path/to/boost
contains Boost's include files.INCLUDEPATH += "/path/to/boost"
On windows, this might be:
INCLUDEPATH += "C:\Boost\boost_1_60_0"
On Mac, this might be:
INCLUDEPATH += /usr/local/Cellar/boost/1.59.0/include
-
Run qmake on
SplineDemo.pro
to generate a makefile, then build the makefile, and run the compiled executable -
OR, open
SplineDemo.pro
in Qt Creator and press play
License
This code is available under the Simplified BSD License
This project includes the nanoflann library for fast nearest-neighbor queries, which is also available under the Simplified BSD License
To-Do
- Implement "composite splines", ie a spline that is made by combining two or more splines. Current ideas include a "sum spline" where the output for a given T is a sum of all the child spline results at T, and a "concatenation spline" formed simply by starting one spline where the previous leaves off.
- More spline types as I discover them
- Find an actual mathematical definition for the quintic catmull-rom spline. The quintic cubic hermite spline is well-defined, but I basically guessed on how to automatically compute the tangents and curvatures based on the input points for the catmull-rom equivalent.