3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What do you know? The control points? The equations that correlate the parameter with the coördinate? It would be helpful to know what you are working with, or at least a sample. $\endgroup$ – Senex Ægypti Parvi Jun 21 '14 at 0:48
  • $\begingroup$ It is a graphical interface in matlab. We need to get a specific Y coordinates for a given X coordinates, hence we need the parameter t values. The control points are updated as the user drags the point. You know the points, hence you know the bezier equation. This Y values are important for further calculation (other calculation not regarding the curve). $\endgroup$ – Jesus Galarza Jun 23 '14 at 13:30
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I read the paper but inversion gives me a function t(x,y). What is required it to obtain t for a particular x. Hence this makes a function of t(x,y) not useful since it is still a function of y. Maybe I'm seeing the wrong angle at this article. Any more insight is appreciated. $\endgroup$ – Jesus Galarza Jun 23 '14 at 21:44
  • $\begingroup$ Yes, inversion gives you the $t$ value corresponding to given $(x,y)$ values. Your question confused me because you wrote $\mathbf{x}$, and I interpreted this as $\mathbf{x} = (x,y)$ $\endgroup$ – bubba Jun 24 '14 at 13:51
  • $\begingroup$ Sure no problem, right now I'm using Newton's method (since I know the derivate before hand) yet I don't know if there is another faster method that achives convergence (e. g. Brent's method, etc.) or something similar to inversion but with just on dependant variable. $\endgroup$ – Jesus Galarza Jun 25 '14 at 15:04
  • $\begingroup$ I don't know anything analogous to inversion that would help. Your problem is essentially root finding. Newton-Raphson or the secant method are good. In principle, you would expect to get better/faster results by using some method that's specific to polynomials, but that has not been my experience in practice. $\endgroup$ – bubba Jun 26 '14 at 12:33
  • $\begingroup$ Yes, Newton's method was useful handling the roots at .0004 seconds in matlab wich is very practical. This is due to 2 things, the bezier curve is already restricted because it is an ordered set in x and y. Since of this restrictions it converges quite fast, and also, when doing the real time calculations de previous roots are used for the new curve, hence they are quite close thus helping in the convergence. $\endgroup$ – Jesus Galarza Jul 1 '14 at 16:43
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.