I have a parametric cubic spline which I need to draw in graphics. I am restricted to using a set of lines to draw this, and for performance reasons I need as few lines as possible. So I need an adaptive sampling scheme with small steps in high curvature intervals and large steps in straight intervals.
I found a description for adaptive stepsize in the Runge-Kutta-Fehlberg method which matches my requirements in a sense, but the use case is too different to make use of it.
In essence, I need the spacings between N number of points along a parametric spline which minimizes the error between a linearly interpolated curve between those points and the spline from which those points originate.
Update: The spline may contain many knots in straight segments, so it is necessary to drop original points.
Finding the optimal spacing of N points that minimizes the error to the original spline might not be your best shot in achieving the best rendering performance as the computation cost for finding the optimal spacing of these N points might be too high and you will be better off to simply sample $2N$ points uniformly.
If you really would like to use an adapative sampling scheme, here is what I would suggest. This is not the same as finding the optimal spacing of N points to minimize the error to the original spline. Instead, this algorithm will find out a linear approximation of the spline where the error is smaller than a predefined value.
1) Suppose the parametric cubic spline is defined over knot values $(0,t_1,t_2,....,1)$ where we have a cubic polynomial curve in between each two knot values. We also define a tolerance $\varepsilon$ representing the maximum deviation between the parametric cubic spline and the linear approximation
2) For $i$-th cubic polynomial segment (where t $\in [t_i,t_{i+1}]$), convert it into cubic Bezier form. Namely, find the 4 control points $P_0, P_1, P_2$ and $P_3$ with $P_0=C(t_i)$ and $P_3=C(t_{i+1})$.
3) Compute distances $d_1$ and $d_2$, which are the vertical distance from $P_1$ and $P_2$ to the line defined by $P_0$ and $P_3$. If both $d_1$ and $d_2$ are not greater than $\varepsilon$, then you only need to draw a single line segment from $P_0$ to $P_3$ for this cubic segment. Add $t_i$ and $t_{i+1}$ to your parameter array and proceed to the next cubic polynomial segment.
4) If either $d_1$ or $d_2$ is greater than $\varepsilon$, then split the Bezier curve at $u=0.5$ (where $u$ is the parameter of the cubic Bezier curve) using de Castljau algorithm and repeat step 3 for the two Bezier curves. Add $t=0.5(t_i+ t_{i+1})$ to the parameter array.
5) After finish processing all cubic polynomial segments, sort the parameter array in ascending order.
The advantage of this algorithm is that the final number of points in the linear approximation depends on how large the $\varepsilon$ you choose. If users had zoomed in very close to the spline, you can use a smaller $\varepsilon$ value to draw the spline in details. But if users is far away from the spline, then you can use a large $\varepsilon$ value, which will lead to fewer points for the linear approximation.