Home > Degrafa > Bezier Y at X Algorithm

Bezier Y at X Algorithm

October 15, 2009

A few requests for the algorithm behind the Bezier y-at-x and x-at-y methods have been received.  The code is self-contained in the com.degrafa.geometry.AdvancedQuadraticBezier and AdvancedCubicBezier classes.  Both classes accept control points in their constructors and use classes from com.degrafa.utilities.math .  The latter classes are independent from any internal Degrafa architecture.  So, people who maintain their own Bezier class libraries have a path to include the y-at-x and x-at-y capability.

Finding the y-coordinates at a given x or the x-coordinates at a given y is an exercise in root-finding.  Suppose the Bezier curve is B(t) which is quadratic or cubic in t.  For the cubic Bezier, the vector equation for the curve produces two scalar equations, one for the x-coordinates and one for the y-coordinates, i.e.

Bx(t) = c0x + c1xt + c2xt2 + c3xt3

By(t) = c0y + c1yt + c2yt2 + c3yt3

For the y-at-x case, the required y-coordinates are found at the t-parameters corresponding to the intersection of B(t) with the vertical line x = a, or

c0x + c1xt + c2xt2 + c3xt3 – a = 0

The problem reduces to one of finding roots of a cubic polynomial. This starts by finding one root.  Synthetic division is used to factor out the single root leaving a quadratic polynomial.  The two possible roots of that polynomial are found with the venerable quadratic formula.  Only roots in [0,1] are valid solutions to the y-at-x problem.  The roots (values of t) are used to compute the y-coordinates using the equation for By(t).  With a quadratic Bezier, roots are found directly with the quadratic formula.

The x-at-y problem is similar in that the required x-coordinates are the intersection of B(t) with the horizontal line y = a.  There is one degenerate case where the Bezier curve is a segment of a horizontal or vertical line and the single parameter describing the line is the input value.  For example, a cubic Bezier curve is the line x = a and the y-coordinates for x = a are desired.  Theoretically, there are an infinite number.  The Degrafa code does not currently handle this case.  Some argue that no values should be returned while otheres argue that perhaps t = 0, t = 1/2 and t = 1 should be returned.

Given the rarity of this case actually occurring, the argument is postponed in lieu of more important developments.  Tomorrow, I’ll post some code from the demos.

Categories: Degrafa Tags: , , ,
  1. JT
    October 15, 2009 at 10:46 am

    How do you compute the initial root?

    • October 15, 2009 at 1:02 pm

      First, use bisection to either show that no root exists in [0,1] or get a better bound on one root. Then, use any root finder (I use Jack Crenshaw’s TWBRF) with the new bounds.

      regards,

      – jim

  2. Rothrock
    October 28, 2009 at 12:36 pm

    Thank you so much for this. I’ve been trying to understand this for a long time. I’m working on the simpler quadratic beziers in flash and I think this finally helped me to get it.

    I still don’t understand the cubics and TWBRF, but baby steps…

  1. No trackbacks yet.
Comments are closed.
%d bloggers like this: