In this article I explain how to iterate over splines. About splines, this great video by Freya Holmer is a must see, and about the implementation in C of Bezier splines, you can also refer to my previous article here, but the algorithm introduced here works for any type of spline.
Splines are a very convenient way to describe curves in 2D or higher dimensions and are often used in computer graphics. They are easy to implement and compute, and intuitive for a human to manipulate. However it may not be immediate to see how to "walk through" the spline. It has one control parameters \(t\) as input with a known range, but an appropriate value for \(\delta t\), the step of iteration along the curve, can't be set a priori: \(\delta \vec{P}(\delta t)\), the change in position on the curve for a given change of its input argument, varies with \(t\) and the control points of the spline.
A solution consists of computing dynamically \(\delta t\) at each step using dichotomy. The iteration starts with an iteration window of \([0,t_{max}]\), then divides the iteration window in two windows, \([0,\frac{t_{max}}{2}]\) and \([\frac{t_{max}}{2},t_{max}]\), and so on until we reach a window \([t_0,t_1]\) such as a condition is fulfilled over the pair \((\vec{P}(t_0),\vec{P}(t_1))\), where \(\vec{P}(t)\) is the position on the spline at input \(t\). The appropriate condition depends on the purpose of the spline, but considering the rendering of 2D curves in an image as an example, \(D_{Chebyshev}(\vec{P}(t_0),\vec{P}(t_1))\le1\) gives an iteration over each pixel the spline passes through, one pixel step at a time.
Some implementation details must be taken care of. First, the condition must be realisable, otherwise the algorithm gets stuck in an infinite recursion. In the example condition above, it means the spline must be continous. If discontinous splines should be supported too, the condition \((D_{Chebyshev}(\vec{P}(t_0),\vec{P}(t_1))\le1) \cup (|t_0-t_1|\lt\epsilon)\) should be used instead.
Second, I'm speaking of recursion but implementing the algorithm in a recursive fashion makes it inconvenient to use. It would mean the iteration as to occur all in one go, and the action performed at each step would need to be inserted into the recursive function (or passed as an argument). A much more convenient way to implement it is to derecursify and use a list of iteration windows instead. The user can then execute the iteration one step at a time, and use the current position as necessary. The list of iteration windows can be computed only when needed, and windows 'behind' the current position can be discarded, both to ensure a minimum memory footprint. Taking care of splitting first the window with minimal \(t_0\) ensures the spline is iterated from start to finish in correct order.
Then, the algorithm is as follow for a spline divided into a list of segments, \(t\in[0,1]\) over each segment, and using the iteration condition given above:
Edit on 2023/05/10: correction of a bug in SplineIteratorHasEnded(). It returned erroneously true if the first window is closed but not the last one.