Flexible Spline Framework - in progress

[HiGreg]

I finally have some consistent results from my work on splines. I’ve created what can be described as a Spline Framework. With it, I can create a wide variety of polynomial-based splines. This includes

• Cubic Bezier Spline
• Cubic Hermite Spline
• Cubic B-Spline
• Cubic Tensioned B-Spline (with tension parameter)
• Cubic Beta Spline (with beta1 and beta2 parameters)
• Cubic Catmull-Rom Spline (with tension parameter)

Babylon.js Playground

This demo shows

• Hermite: Teal
• Bezier: Red
• B-Spline: Blue
• Tensioned B-Spline (tension varies Blue to Black)
• Catmull-Rom (tension varies Green to Yellow)

Any of these splines can be created in 1, 2, or 3 dimensions (or more) from the same code. Output can be in any form desired with very little temporary memory allocated by using JavaScript generators instead of creating large temporary arrays.

I’m still working on making it easy to use, but it’s coming along well.

[Deltakosh]

Excellent dude! This is cool!

[HiGreg]

Here’s an update to see how fast the calculations are.

Babylon.js Playground

Each point moves along it’s own CatmullRom Spline (tension=1) updated each render frame.

And on every frame, all twelve spline meshes are updated using the new points.

Inside the Spline class, I split up the point calculation and the matrix setup. The setup matrices only need to be recalculated when the “t” parameter exceeds 1. When that happens, a new random point is added to the spline’s input points and the first point is shifted off.

[HiGreg]

Babylon.js Playground

An update with buttons to modify

• number of control points
• number of tesselation points, and
• open/closed

This is showing off only

• Cubic CatmullRom with tension parameter
• Cubic Tensioned BSpline
• Cubic BSpline (without tension)

All points are constantly moving in 3d space and each spline is regenerated every frame.

The points are each moving along a randomly generated CatmullRom spline.

[HiGreg]

A pretty big update, but still working out the interface/API to the Spline class.

Babylon.js Playground

A lot of sliders to change parameters. Consider this a proof of concept.

• Cubic Beta Spline (parameters of Bias and Tension)
• Cubic Catmull-Rom Spline (red with Tension and Alpha)
• Cubic M-Spline (white with parameters of Closeness, Parallelness, Geometricity, Tension, Direction)
• Cubic B-Spline
• Cubic Catmull-Rom Spline (with Tension shown green to yellow)
• Cubic Tensioned B-Spline (shown blue to black)

M-Spline has five separate parameters (“A Five-Parameter Family of G1 Local Splines”, “this family includes all the C0, G1 translation invariant cubic matrix splines.”) and can also generate parameterized Tensioned B-Spline, Cardinal Spline, and Tau Spline.

See “Families of Local Matrix Splines” (PDF) by Tom Duff (aka “M-Splines”) Technical Memo No. 104 21 Dec 1983.

[HiGreg]

Babylon.js Playground

(edit: added “show points”)

Another update, this time there are

• controls for show/hide splines
• added cardinal, tau, and delta splines (which are subsets of M-Splines)
• labels for show/hide also indicate the relevant sliders (by initial letter) for that spline.
• added “stop”

I’m still reviewing the implementations for accuracy. They are not fully optimized, but seem to function well.

Updated API is not yet fully implemented by all splines.

[ntech]

This will be nice

[regna]

Amazing work!

[HiGreg]

Babylon.js Playground

I’ve figured out a lot of math and how to fit it in the Spline Framework. Particularly CatmullRom with alpha and tension, and Hermite1stDerivative. Both have been implemented with matrix operations.

I also have functions that outputs an EasingFunction (untested so far).

GetEasingFunction(SplineName, params, inputPoints)

Here’s the document I’m working on

class Spline

Provides a set of common Splines and allows the creation of new polynomial splines.

For most splines, you will need only GetSpline and either genCubicPoints or genSegment.

GetSpline(SplineName,params,emit,consume)

This is the primary method of creating a spline. The spline name is a string, params is an object,
and emit & consume provide flexibility for specifying points (explained below).
Current splines:

• Bezier,
• CubicBezier,
• QuadraticBezier,
• CubicCatmullRom,
• CubicHermite,
• CubicHermite1stDerivative,
• CubicB,
• CubicBeta01,
• CubicBeta,
• CubicM,
• CubicCardinal,
• CubicTau,
• CubicDelta

Functions

*genSegment( tesselation,inputPoints,emitFirstPoint,emit,consume)

Generate ouput points for a single segment of the spline. Called by genCubicPoints, and calls setTessellationMatrix and then genPoint repeatedly.

*genCubicPoints(tesselation,points,closed=false,clampStart=true,clampEnd=true)

Generate output points for a sequence of piecewise segments. For Bezier and Hermite, use genSegment only.

setTessellationMatrix(inputPoints,consume) - set input points

Generate a new tesselation matrix for a new segment. Automatically called from genCubicPoints but can be called on its own.

getPoint(t,emit)

Calculate a new point with already defined tesselation matrix.

setBasisMatrix(splineString,...parameters) - change spline type and/or parameters

Update the basis matrix with new parameters (or a new spline)

constructor(squareMatrixPointsColFirst,emit,consume)

If you know the exact basis matrix, you can use the constructor. Using GetSpline to obtain a pre-defined spline is preferred.

EmitVector3, ConsumeVector3 (and \*Array(default), \*Vector2, \*Scalar, \*Color3, and \*Color4)

Useful for defining the input and output as Vector3 when calling the GetSpline or the constructor. Can be overridden in any function that accepts emit or consume. Other pre-defined emit and consume functions are provided for values: Scalar, Vector2, Color3, Color4

About

Spline class creates generic polynomial splines that use the form:

Monomial Basis * Geometric Matrix * Control Points

The creation of a spline occurs in two steps, much like Curve3 splines which use CreateX() then .getPoints(). In contrast, Spline uses GetSpline() and genSegment(). Input points (and tesselation/nbPoints) are provided to genSegment(tesselation,inputPoints) rather than the constructor.

This provides a convenient separation of the calculation required to generate the points and minimizes the creation of Vector3 point arrays. Instead, the calculated matrices are retained in the instance in two steps. As mentioned, the general form of the Spline is:

Monomial Basis * Geometric Matrix * Control Points

Note that the Geometric Matrix is sometimes referred to as the spline basis.

The constructor calculates and retains the Geometric Matrix based on the spline type and spline parameters, such as tension or beta. Then genSegment(tesselation,inputPoints) calculates and retains

Geometric Matrix * Control Points as *tesselationMatrix*.

Finally, t sweeps from zero to one, and each tesselation step calculates the Monomial Basis from the value of t and generates each point from Monomial Basis * this.tesselationMatrix.

Evaluation of a Spline segment

A spline segment is evaluated with a number of control points equal to the Order of the spline. A Cubic spline (order 4) has four points needed for evaluation of a segment. For most splines (with the notable exceptions of Bezier and Hermite) only the segment between the second and third point is calculated as the value of t is swept from zero to one.

Sequence of control points

A sequence of control points is specified to genCubicPoints. Nominally, the sequence is divided into a “rolling” group of points of size equal to the order of the spline. For a cubic spline, each group of four points is evaluated as a spline segment evaluated between the second and third point. The group is shifted by one point and repeated until all points are included in a group.

The arguments “closed,” “clampStart,” and “clampEnd” control how the first and last points are treated. Without closed or clamped, the first and last segments are not calculated.

Flexibility

Several aspects of this Spline class provide a lot of flexibility in the creation of splines and the the input and output of “points”.

Internal point format

The internal representation of points, and the nominal input and output point format is as an Array of numbers. Calculations use a flexible Matrix class.

Input point format

individual points are expected as an array, and can be of any dimension (typically, 1, 2, 3, or 4 numbers). However, a function can be specified (“consume”) and is used to convert each point provided into an Array (or TypedArray). consume() can be specified in the constructor or each time genSegment() is called.

Output point format

the ouput format is nominally an array, as well, that is the same length, and thus the same dimension, as the input points. The user can specify a function “emit” to convert each point from an array to any format desired.

Point Format Conversion

as a useful example, EmitConsumeVector3 is provided which will convert to and from Vector3 objects.

EmitConsumeVector3 = [(a)=> new BABYLON.Vector3(a[0],a[1],a[2]), (v)=>v.asArray()]

The full set of supplied format conversions is: Array(default), Vector3, Vector2, Scalar, Color3, and Color4

EmitVector3, ConsumeVector3, EmitVector2, ConsumeVector2, EmitScalar, ConsumeScalar, EmitColor3, ConsumeColor3, EmitColor4, ConsumeColor4

Once I figure out Quaternion splines, I’ll add that to the list.

Generators

The advantage of using generators vs arrays to create output points is not needing to store output points in temporary arrays. When an array of output points is needed, the user can use […genCubicPoints()] to do so. When emit is a=>new BABYLON.Vector3(…a), […genCubicPoints()] will result in an array of Vector3 points. Further, new BABYLON.Curve3([…genCubicPoints()]) results in a Curve3 object.

However, an intermediate array can be eliminated if the output is written directly to a VertexBuffer using a simple for…of loop. Similarly, writing directly to a thinInstance Matrix buffer is possible, again, without creating large and temporary array storage.

Flexible Matrix Calculations

In the most common case, the matrix sizes are

Monomial Basis * Geometric Matrix * Control Points => 1x4 * 4x4 * 4x3

This represents a Cubic Spline (defined by square Geometric Matrix) and four three-dimensional Control Points. The Geometric Matrix size is defined by the spline “order”, and the Control Points size is defined by the user (e.g. 2d or 3d points) and is mirrored in the output point dimension. Generically,

Output Point = Monomial Basis * Geometric Matrix * Control Points => 
    1 x Dimension = 1 x Order  *  Order x Order  *  Order x Dimension

Because the Spline class uses a flexible Matrix class for calculations, it can support any Order spline and any Dimension point. Internal to the Matrix class, a Float32Array is used for storage.

Monomial Basis

Nominally, the Monomial Basis is a function of “t” and is a matrix of size 1xOrder consisting of t raised to increasing powers starting with power zero.

Monomial Basis => [t^0, t^1, t^2, t^3, t^4,...] up to one minus the spline order.

For a Cubic Spline, Order is 4 and the Monomial Basis is [0, t, t*t, t*t*t]

For each step in evaluating the spline, t is uniformly swept from 0 to 1, resulting in a number of points (specified by the tesselation parameter to genSegment) that define line segments along the spline curve.

Parameterization

Parameterization refers to a modification in the step size of t. In general, a uniform step in t does not result in a uniform distance of the resulting spline curve (called “arc length”).

A uniform arc length with a given uniform step in t is called arc-length parameterization. There is not a deterministic general solution to creating a uniform arc-length parameterization of a spline, and is not yet available in the Spline class.

Alpha

Another application of Parameterization is implememting the parameter “alpha” for a Catmull-Rom Spline. The difference between Chordal, Centripital, and Uniform Catmull-Rom Spline is the value for alpha.

Application of “alpha” for a Catmull-Rom Spline requires a parameterization of t that includes the distance between control points. A convenient place in the Spline class to capture this parameterization is when the spline segment is defined with new input points supplied to genSegment.

[HiGreg]

In my continuing work and research on Splines, it seemed useful to write a tutorial on Splines to explain how and why splines are used, and identify where to use which types. Here is the introduction.

Note that it currently conflicts with the definition of “Basis” above. I’ll be renaming some of the Spline methods as a result.

Introduction

If you prefer a video format that introduces splines, I can’t recommend enough the videos from Freya Holmér: The Beauty of Bézier Curves (25 minutes) and The Continuity of Splines (74 minutes). The videos cover the terminology, application, and derivation material below in an entertaining and very informative way.

It is useful to define a series of points and draw a path that connects those points. In the simplest case, one can draw a line between each pair of points. But the connection at each point is sharp and forms an angle. Mathematically, the tangent of the “curve” abruptly changes. Splines have been useful for decades in making curves from a series of points, where the abrupt changes are smoothed out. Further, the application of polynomial splines has been well studied and applied to useful effect with computational efficiency.

A mathematical, polynomial Spline is a sequence of Curves with each curve defined by a set of points and a set of polynomial equations. Curves, such as the classic curve types Bezier, Hermite, and Catmull-Rom, are joined end-to-end to form (usually, and usefully) a continuous Spline. Each curve type is defined by a set of polynomial equations that are created by applying one or more continuity constraints at the points between curves, that is, where two curves meet.

Understanding the constraints defined by each curve type and applied to the curve’s joints with adjacent curves, along with the parameters each type of curve provides for controlling the curve’s path through the joints, will lead toward two different areas of understanding:

1. applications where each curve type best applies, and
2. the math behind the creation of each curve and in joining those curves into a spline.

Understanding the application of splines can begin with tracing a path along a single curve. The input that defines a point along that curve is usually represented by the independent scalar variable t. The value t varies with, but not necessarily proportional to, a distance along the curve. It varies between 0 at one end of the curve and 1 at the other end.

Extending this from Curves to Splines, a t value of 1 for one curve is followed by a t value of 0 for the next curve. We can extend this concept to a Spline u value analagous to a Curve’s t value. Consider a Spline to have n Curves numbered 0 to n - 1. In the case of a Uniform spline, as the Spline’s u value varies between 0 and n the whole number corresponds to the curve number and the fractional portion of u corresponds to that Curve’s t value.

Dimension

The (output) path of the curve is most usefully in a 1d, 2d, 3d, or 4d space.
And the space can be defined as positional space, color space, rotational space (e.g. quaternion space), scale space, transparency space, intensity space (in any number of senses including material parameters), or anything, really.

Consider positional space. If we specify a scalar t, we could obtain a scalar output (1d), a Vector2 output (2d), or Vector3 output (3d) by supplying “control points” of the same dimension we’re seeking. We can draw a graph of X, Y points where X=t and Y=output, or simply take the Vector2 or Vector3 ouput as the 2d or 3d point. Each has utility in drawing and animation.

Positional Space, Continuity, and Constraints

For now let’s consider the 2d case and treat t as a variable that we sweep from 0 to 1 to get a two-dimensional ouput. With this formulation, the output represents an X, Y position in 2d space, the derivative of Y with respect to X is the slope of the tangent (or just “tangent”), and the derivative of the tangent is the rate of change of that tangent along that line, also known as its curvature. Notably, the tangent rotated 90 degrees is the normal to the curve.

A Spline is most useful when the end points on sequential curves lie at the same position in space. When this happens, it is called positional continuity, or G0 continuity, referring to Geometric Continuity. The position of the path drawn by the Spline, in this case, does not change going from one Curve in the Spline to the next Curve: it is connected. In some applications, it is useful for the tangent of the spline to also not change when going from one Curve to the next. A Spline with this property of tangent continuity is called G1 continuous, or Geometric Continuity of the first derivative. That is, the first derivative of the position (i.e. the tangent, and notably the normal) is continuous. One step further, a Spline that has a continuous second derivative (i.e. the tangent’s rate of change, its curvature) is G2 continuous. This has implications in the continuity of a reflective surface, because continuous reflection is result of Curvature Continuity, or G2 Continuity. A surface with G2 Continuity is also called a Class A surface.

All of this describes the shape of path drawn, but not specifically the shape, position, or tangent with respect to the value or rate of change of u. Let’s consider the derivative with respect to u.

The derivative of the Spline output with respect to u, when conceptualized as time, is velocity and the derivative of velocity is acceleration. Further derivatives have names in physics. Here’s the complete list out to 6th derivative, though beyond the third derivative (jerk or jolt), there seems to be limited utility: position, velocity (1st derivative), acceleration (2nd), jerk (jolt) (3rd), snap (jounce) (4th), crackle (5th), pop (6th).

The derivatives with respect to time of a Spline used for an object’s position are important in animation, where the Spline output determines the apparant velocity, acceleration, jolt, etc. of the object. Continuity in derivatives with respect to time are referred to by the letter C. Velocity Continuity is C1, Acceleration Continuity is C2, and Jolt Continuity is C3.

It turns out that Cx continuity implies Gx continuity for “regular” curves (i.e. where P’(t) != 0), and derivatives with respect to the Spline’s u are exactly the constraints applied to form the various Spline types, so picking a spline type will also define the minimum Cx continuity while increasing that continuity requires a higher order spline and/or restrictions on picking control points. It also turns out that a Curve’s derivative with respect to t is very straightforward to calculate because of being defined by polynomials.

Spline Characteristics and Use Cases

The major characteristics of splines help define the use cases for which they are best suited.

Uniform Cubic Splines (Degree 3)

Name	Cont.	Tangents	Interp	Local	Use Cases
Bezier	C1	manual	some	no	shapes, fonts, vector graphics
Hermite	C1	explicit	all	yes	animation, physics sim, interpolation
Cardinal	C1	auto	all	yes	animation, path smoothing
B	C2	auto	none	yes	curvature-sensitive, animations (camera)
Natural	C2	auto	all	no	??

• Cont. - Continuity, the highest level of Parametric Continuity. Implies all lower levels of Cx continuity. Under certain conditions, Parametric Continuity (Cx) implies Geometric Continuity (Gx).
• Tangents - if/how tangents are specified
• Interp - Interpolation, whether line passes through control points
• Local - whether control points affect the entire spline, or only a a few local segments.
• Use Cases - suitability based on Continuity, Tangents, and Interpolation

[HiGreg]

Babylon.js Playground

Simple 2d Cardinal Spline with alpha and tension sliders.

With the right settings, this is a uniform Catmull-Rom Spline, or a Centripital or Chordal Spline.

Any ideas on additional demos? Writing them helps me hone the API and make it more user-friendly.

One of the main things I wanted to accomplish was to not have to generate large temporary arrays. I do this with a (JavaScript) generator and can update a mesh with minimal and efficient code.

In the Playground above, the drawNew() function on line 203 is the result:

function drawNew() {
    const m = meshes[0];
    const vb = m.getVertexBuffer(BABYLON.VertexBuffer.PositionKind);
    const data = vb.getData();
    
    let i = 0;
    splines[0].genCubicPoints(60,points,true,false,false)
       .forEach(n=>{data.set(n,i);i+=3})

    vb.update(data);
}

[ntech]

getting a point along the spline or segment using a distance from last marker. Like using it as a path rail for the camera or an object to follow along.

[HiGreg]

That involves “arc length parameterization.” As I wrote above, “There is not a deterministic general solution to creating a uniform arc-length parameterization of a spline, and is not yet available in the Spline class.”

However, I am looking at ways to implement it across all splines. There is the brute-force method of using a high number of points and measuring each line to determine arc length, them stopping when you get to the desired value. There is also the method of guessing a point, and adjusting the next guess based on that point. Other optimized algorithms involve using the derivative of a spline, which is why I have implemented the derivative function that works for all Splines that use the standard Monomial Basis (which include all the splines so far).

I can implement a brute force method. Thanks for the idea!

[ntech]

You wanted Ideas, so I just gave you the most common use case I could think of off the top of my head.

I’m aware of the issues but you’re doing a good job on it, so ..

[HiGreg]

Babylon.js Playground

Added:

• TCB Spline (tension, continuity, bias aka Kochanek–Bartels Spline)
• Tangents
• Curvature Comb
• Automatic derivative calculation (using spline.derivativeOrder)
• Slider Range changed to -1 → 2

Select Tangent/Comb to toggle
None → Tangent → Comb → None

Starts off showing TCB’s Comb, but Tangent/Comb button affects all displayed splines.

Needed to change the range of sliders because TCB Spline parameters use a different calculation and the relevant range is for tension, continuity, bias is -1 to 1. It was easiest to change all sliders’ range and I chose -1 to 2.

The literature is not entirely consistent on the exact calculation of tension (e.g. in Cardinal Splines). The range is arbitrary, but usually 0-1. More noticably, tension is sometimes used directly as (tension) and sometimes used as (1 - tension). The parameter has opposite effect depending on calculation. Most splines here use tension=0 gives a straight line (which does seem counterintuitive). You’ll notice TCB, which uses (1 - tension), has the opposite effect, that is: 1 is straight (tight?), 0 is loose. I’m considering making them all consistent (and intuitive). TCB, in my opinion, needs to stay the same to match the literature.

There is provision for changing t, c, and b on a per-control-point basis, but is neither tested nor used in this playground. This provisioning, when available, should be usable for all splines. (e.g. Cardinal Spline with different tension per point).

Derivatives used in tangent and comb are integrated into the Spline class, but accessing them is a little complicated. I basically run through generating an output point twice: once for the main curve and again for the derivatives to calculate tangent or comb. It still performs well. When not used (derivativeOrder=0 or undefined) there is minimal effect on performance.

[HiGreg]

Babylon.js Playground

Added quite a few options to Tangent/Comb. Derivatives are calculated within the Spline class, while the additional calculations below are calculated per evaluated point and saved directly to mesh vertex data.

• 10x Unit Tangent
• 10x Unit Normal
• Curvature
• Radius<100
• Speed (on norm)
• Torsion
• Tangent (length=speed)

Interesting visualization, but might have more usefulness in 2d. I wanted to add these calculations to determine how much capability to include in the class itself. The calculations of normal and tangent from first and second derivatives might become useful when generating ribbons or surfaces.