libGDX – Iterating a Catmull-Rom Spline by fixed units

If you want a well defined curve Catmull-Rom is your go-to spline. It’s being used very often in graphics so I was glad to see that libGDX (a cross-platform game development library) has built-in support for it. But if you want to do some more advanced calculations you can easily run into problems.

out of the box iteration with libgdx

The most basic operation you’ll ever do with a spline is iterating over its points. Let’s look at rendering as an example:

path = new CatmullRomSpline<>(controlPoints, false); //false means non-continuous; bad design right there

for (float t = 0f; t <= 1f; t+= precision ) {
 Vector2 point = new Vector2();
 path.valueAt(point, t);
 shapeRenderer.circle(point.x, point.y, height);
}

In the above code we’re rendering small circles on the path of the spline (a dotted line) using libGDX’s CatmullRomSpline API.

Questions is: how do we choose the precision? Essentially it will determine the number of points rendered, therefore the smoothness of the spline but it also highly affects performace. It should obviously correlate with how long or pointed the spline is.

As length is fairly trivial and supported by the API we set up a small demo using something along the lines of:

int precisionOverLength = 5;
float length = path.approxLength(numberOfSamples);
precision = precisionOverLength / length;

Where precision over length determines your relative precision. Assuming length is in pixels: 1 would mean 1 point per pixel (very precise), 5 is 1 point per 5 pixels (less precise).

Let’s see the result:

Capture3

The big dots – in case you’re not familiar with Catmull-Rom splines – are the control points allowing you to shape the curve as it will always pass over those points. The actual curve is calculated from these points using a mathematical equation. Another term I must define is a span. A span is the section of the spline between two control points – this one has seven.

Did you notice the density in spans 3 and 4? Despite our efforts to achieve universal precision in these spans the precision is way higher than expected. The reason is that the number of points we’ll calculate on the spline is divided equally between spans. A shorter span therefore will have a higher density of points, a higher precision.

the upside

In many cases (and especially when rendering) this is helpful as sharp changes in direction in a small area could cause our spline to be fragmented. Having lots of points in these areas will make them smoother.

the downside

It will take as much time to compute a small area as to compute a large one even if that area is very simple and would not warrant a higher precision. Having no control over this may lead to performance issues.

You can’t guarantee a fixed or minimal density of points during iteration. This lack of guaranteed precision is most painful if you’re working with approximations and margins of error.

Imagine you’re looking for a specific point (e.g. one third) or an intersection of your spline. It has one very long and many short spans. If you want to be precise on the long span you’ll end up spending the unnecessarily big efforts on the shorter spans. And there’s still no guarantee that you’ll find what you’re looking for within the margin of error.

iteration by fixed units

Luckily for us there’s another method provided by the API where you can iterate only points of a specific span. This way we can move our precision calculation to the level of spans and bypass the equal point division between spans.

This will require quite some additional logic to keep track of where we are in the spline and what precision we should use in each span.

the result

SinglePointSplineIterator iterator = new SinglePointSplineIterator(path);
SplinePoint splinePoint;

while ((splinePoint = iterator.getNext()) != null) {
    shapeRenderer.circle(splinePoint.point.x, splinePoint.point.y, height);
}

Capture4

The code (alongside with other Catmull-Rom utilities) is available on GitHub. There’s an XFlatSpline class using the iterator (here’s why) and a desktop demo where you can try it for yourself. As a QoL improvement there’re separate single– and double point iterators available as in many cases you’ll need the current and previous points as well during iteration.

Finally a side-by-side comparison:

capture

Leave a Reply

Your email address will not be published. Required fields are marked *