Fastest way to obtain the parametric value t of a bezier curve, for a given set x coordinates.

Question

The problem is the following:

Having a bezier curve B(t) we have coordinate x from the curve, and we need to obtain the y values from it, hence we need to compute the t values.

What is the fastest way to obtain the parametric value t of a bezier curve (not necessarily cubic).

Since I'm doing a realtime application it is necessary that the calculation is as fast and efficient as possible. So if you referred the method is much appreciated.

Answer 1

Solution used

Newton's method was the preferred method to finding the parametric values. The speed of the calculations are averaged at .0004 seconds in matlab wich is very practical. This is due to 2 things:

• The bezier curve is already restricted to be an ordered set in x and y. Since of this restrictions it converges quite fast

• The real time calculations uses the previews roots for the method the new curve, hence they are quite close thus helping in the convergence.

Thanks for the help.

Answer 2

What you asking about is called "inversion". If you look in these notes by Tom Sederberg, you will find some techniques for inversion of polynomial and rational curves, based on the use of resultants. Specifically, on page 200, you will find a formula for doing "inversion" of a cubic curve written in Bezier form, and there's a nice worked example on page 201. This is exactly what you need.

The calculation is very fast. For a cubic curve, the inversion formula gives $t$ as the ratio of two linear functions of $x$ and $y$. You can construct this formula once (for a given curve). Then, for any given $(x,y)$ value, you can calculate the corresponding $t$ with at most 8 multiplies, 8 adds, and two divisions.