0
$\begingroup$

Given an $y$-coordinate and the three control points of a quadratic Bezier curve, can you calculate $~t~$ in the following way ?:

$ y_{p0} - y + 2(y_{p1} - y_{p0})t + (y_{p0} - 2y_{p1} + y_{p2})t^2 = 0 $

$a = (y_{p0} - 2y_{p1} + y_{p2})$

$b = 2(y_{p1} - y_{p0})$

$c = y_{p0} - y$

Use quadratic formula to find $t$

(I believe it should, but I'm trying to use this method to rasterize $2$D Bezier-triangles and I'm failing and can't find why. I'm mostly asking if it's possible in theory or not, because if there is something wrong in the implementation I should be the first person to find it as I'm most familiar with my code, while I would not be able to find my mistake if the math behind my algorithm is flawed in the first place.)

Thank you for your answer.

$\endgroup$
  • $\begingroup$ Welcome to Math.SE. Take the opportunity to take the tour, if you haven't done it already. See also some tips on how to ask and on formatting help and write down equations using LaTeX / MathJax. Can you please edit your equations to improve readability? $\endgroup$ – Ertxiem - reinstate Monica Jul 1 '19 at 19:21
  • $\begingroup$ What “abc-formula?” If you mean the quadratic formula, then what are you going to do when you get two solutions, which you will unless the parabola has a vertical axis? $\endgroup$ – amd Jul 1 '19 at 21:50
  • $\begingroup$ Incidentally, a common way to plot Bézier curves is to recursively subdivide them until the resulting arcs are sufficiently close to straight line segments. $\endgroup$ – amd Jul 1 '19 at 21:54
  • $\begingroup$ @amd Yes, with abc-formula I meant quadratic formula, I guess I translated it wrong, thanks for the info. :) I wanted to gather all t between (0, 1) for a certain row of pixels (position y), then calculate the corresponding x, sort them and fill the pixels between each consecutive pair of boundary values. As the triangles are closed figures, this would only fail in the rare case when the quadratic formula return only one value, in which case I would simply omit that value. $\endgroup$ – rvvermeulen Jul 2 '19 at 10:29
  • $\begingroup$ I'm aware of the Casteljau algorithm, but I'm trying to implement a direct algabraic algorithm because I want to see if I can make it faster. $\endgroup$ – rvvermeulen Jul 2 '19 at 10:31
1
$\begingroup$

It is possible to find $t$ for a given $x$ or $y$ value in a quadratic bezier curve.

The quadratic bezier formula $$ y = y_1 + (1-t)^2(y_0-y_1) + t^2(y_2-y_1) $$ can be magically rearranged to $$ t = \frac{(y_{0} - y_{1}) \pm \sqrt{y y_{0} - 2 y y_{1} + y y_{2} - y_{0} y_{2} + y_{1}^{2}}}{y_{0} - 2 y_{1} + y_{2}} $$

This looks very similar to your solution when your $a, b, c$ values are substituted in the quadratic formula.

Here are the key aspects for traversal:

  • Boundary values for the loop should be selected carefully. If traversing by $y$, values should range from lowest and highest of the three control points.
  • In $t$ formula, square root part becomes imaginary when curve does not touch or go through the given $y$. (Beyond the curvature towards second node point when it is higher or lower than other node points, for instance).
  • There's a $\pm$ in the formula, so it yields two $t$ values for your set of control points and for every $y$ value. Either of the points may or may not fall on the curve segment. You should validate the results by checking range ($ 0 \leq t \leq 1 $) or by substituting in the first formula.
  • Finally, this method is unusable when the divisor becomes zero for the given set of control points. In such cases, traverse on other dimension ($x$) or switch to a root-finding method such as Newton's method.
$\endgroup$
  • $\begingroup$ A range check along is insufficient unless you know that the parabola’s axis parallels the $y$-axis. $\endgroup$ – amd Jul 5 '19 at 21:44
  • $\begingroup$ @amd Right. I added note about dealing with iteration points falling outside the vertex, where it results in complex numbers. In other cases, I believe a range check on $t$ and/or validating against the bezier formula are sufficient. $\endgroup$ – ananth.p Jul 6 '19 at 6:04

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.