Transform 2d spline function f(t) into f(x)

Question

So I've got a special case set of cubic splines, whose 2d control points will always result in a curve that will never cross itself in the x axis. That is, the curves look like they could be a simple polynomial function such that y=f(x). I want to efficiently create an array of y coordinates along the spline that correspond to evenly-spaced x coordinates running the length of the spline segment.

I want to efficiently find the y coordinates along the spline where, for instance, x=0.0, x=0.1, x=0.2, etc., or approached another way, effectively transform the f_x,y(t) style function into an f(x) function.

I'm currently using a 4x4 constant matrix and four 2d control points to describe the spline, using matrix constants for either Hermite or Catmull-Rom splines, and plugging them into a cubic function of t going from 0 to 1.

Given the matrix and the control points, what's the best way to obtain these y values over the x axis?

EDIT: I should add that an approximation good enough to draw is sufficient.

Mushro

The simplest method I've found so far is just taking a sampling of points from the curve at regular intervals of t, then interpolating between those along the x-axis to collect the f(x) values. This looks OK most of the time, but occasionally misses details, because it's hard to know where the sharp corners are located; increasing sampling frequency helps, but is not exactly efficient nor satisfying. I'm sure there's a clever way that's both computationally efficient and doesn't lose the details. – Mushro

@vervellop, with the edited question, your current approach might be the best answer, so I suggest you post it as an answer, so you can eventually accept it if nothing better turns up. And users can upvote it if they consider it a good / appropriate solution to this problem. – Cuff

There might be a contradiction in your question: the original question asks for evenly spaced x coordinates, whereas the edit requires a solution suitable for drawing. In the presence of pronounced cusps, an evenly spaced sampling will probably be unable to capture these cusps. So I suggest you leave the question as it originally was, as that is what the answers refer to. You might want to ask a new question about the drawing problem, preferrably giving details on what exactly you try to achieve, i.e. why simply drawing the 2D spline isn't enough. – Cuff

Ah yes, to clarify: the output of this module is a list of y positions for evenly spaced x coordinates (much like amplitude samples of a continuous signal). The goal here is to just generate these f(x) points, since we don't do the drawing. Obviously any details finer than the 'sampling frequency' will be lost using this method - that's OK. Their quality need only be "good enough for drawing", but shouldn't miss any important features of the curve. Ideally it would only have to evaluate the curve no more than ~N times to generate N points (less would be better though). – Mushro

Answer 1

Your question states that you want evenly spaces x coordinates, and approximate solutions are all right. So I propose the following algorithm:

• Decide on the grid points you want, e.g. one every 0.1 x units.
• Start with l = 0 and r = 1.
• Compute f_x(l) and f_x(r) and consider the interval denoted by these endpoints.
  • If the interval is sufficiently small and contains exactly one grid point, use the central parameter t=(l+r)/2 as a good approximation for this grid point, and return that as a one-element list.
  • If there is at least one grid point in that interval, split it in two using (l+r)/2 as the splitting point, and concatenate the resulting lists from both computations.
  • If there is no grid point in the interval, then skip the current branch of the computation, returning an empty list.

This will zoom in on the grid points, bisecting the parameter space in each step, and will come up with suitable parameters for all your grid points.

Cuff

This is a bisection method (link), one of many root finding methods. Check wikipedia for the strengths and weaknesses of algorithms which may work better (or worse) for similar problems. – Larrigan

Answer 2

Often people will use a root finding technique (like Newton's Method) if an numerical approximation is good enough.

Larrigan

Answer 3

Well, you could solve your f_x(t)=x for t. That would be a cubic equation; ugly but still possible to solve explicitely. If your spline is as you describe it, then two of the solutions will be conjugate complex, so the only remaining one is the one to take. Use that to compute y=f_y(t). I doubt you can accompish anything easier if you want exact solutions.

You can use the general formula from Wikipedia to compute the solution of the cubic equation.

Cuff

Thanks that's helpful. Indeed, I looked at the solutions for t and they're pretty ugly. Certainly uglier than anything I'd want to compute in large quantity. I've added that an approximation (suitable for drawing the curve as an f(x) function) is sufficient. – Mushro

@vercellop, I posted a link which gives you a formula to solve a cubic equation. – Cuff