0
$\begingroup$

I'm having some trouble deriving the function $t(x)$, given a Bezier curve with $x(t) = a(1-t)^3 + 3b(1-t)^2t + 3c(1-t)t^2+dt^3$ for its $x$ component, with further restriction that all coefficients are strictly monotonically increasing, so we know that $a<b<c<d$.

I first observed that Bezier curves are invariant to affine transforms, so the function $x(t)$ can be simplified by translating by $-a$ to get rid of the $(1-t)^3$ term:

$$ \hat{x}(t) = 3(b-a)(1-t)^2t + 3(c-a)(1-t)t^2+(d-a)t^3 $$

and then further scaled by $\frac{1}{3(b-a)}$ (not a useful step in general, but definitely useful here due to the monotonic condition) to yield:

$$ \frac{\hat{x}(t)}{3(b-a)} = (1-t)^2t + \frac{c-a}{b-a}(1-t)t^2+\frac{d-a}{3(b-a)}t^3 $$

Which, by substituting $u=\frac{c-a}{b-a}$ and $v=\frac{d-a}{3(b-a)}$, gives the fairly easy to read:

$$ \frac{\hat{x}(t)}{3(b-a)} = (v-u+1)t^3 + (u-2)t^2 + t $$

And so far so good, $\hat{x}(t)$ is a symbolic value, $3(b-a)$ is a positive constant for any curve ($a<b \implies b-a>0$), and a second substitution with $c=\frac{1}{3(b-a)}$, $p=(v-u+1)$ and $q=u-2$ gives:

$$ c\hat{x}(t) = pt^3 + qt^2 + t $$

so I figured I'd rewrite this as:

$$ pt^3 + qt^2 + t - cx = 0 $$

and then apply the Cubic Formula to find the roots. Given the context I'm evaluating this for (a monotonic parametric curve with an implied y=f(x) form) I should only need to care about the real, which computational software tells me should be:

$$ \frac{ \sqrt[3]{ \sqrt{(27 p^2 c x + 9 p q - 2q^3)^2 + 4(3 p - q^2)^3} + 27 p^2 c x + 9 p q - 2q^3 } }{ 3 \sqrt[3]{2}p } - \\ \frac{ \sqrt[3]{2}(3 p - q^2) }{ 3 p \sqrt[3]{ \sqrt{(27 p^2 c x + 9 p q - 2q^3)^2 + 4(3 p - q^2)^3} + 27 p^2 c x + 9 p q - 2q^3 } } - \frac{q}{3 p} $$

And while an unwieldy looking formula, it has loads of repeating parts, so I tried implementing this formula in a regular programming language rather than Mathematica/Sage/etc. but the values for $t(x)$ that come rolling out of this are impressively wrong, in the sense that the term under the square root can end up a negative number (which shouldn't even be possible given the shape of the curve?) and causing the result to be undefined. Even when this is not the case, I'm getting negative values for $t(x)$ which seems only marginally less wrong, but still most certainly wrong...

Where am I going wrong, and how do I correct that misstep?

$\endgroup$
0

1 Answer 1

1
$\begingroup$

Clearly you can convert the curve equation from Bezier-Bernstein form to "power" or "Taylor" form. In other words, you can calculate $p, q, r, s$ such that $$ a(1-t)^3 + 3b(1-t)^2t + 3c(1-t)t^2+dt^3 = pt^3 + qt^2 +rt + s $$ Then, you can just throw the problem to your favorite cubic polynomial solver. It's better to use an existing one, written by an expert, rather than writing your own, because there are some nasty numerical problems. There is some good stuff here.

Since your cubic is strictly monotone, you know that there is at most one real root in the interval $[0,1]$, and you can bracket it. This means that appropriate numerical methods (like Newton-Raphson with bracketing) will work reliably. See the Numerical Recipes book for code. Numerical methods will be slower than the cubic formula, but the answers will probably be more accurate.

For a thorough discussion of root-finding, with special emphasis on Bezier curves, take a look at this document.

$\endgroup$
8
  • $\begingroup$ here's the twist, I am that expert =_=... I have apparently been the oppose of awake, because I have a perfectly fine cubic root finder already implemented, and completely forgot to just rewrite to power form. I actually came back to this post to give this same answer msyelf as it's what I just did and it works absolutely fine. Still, upvote and checkmark for you. (trans4mind.com/personal_development/mathematics/polynomials/… was a good writeup I used at the time I implemented my root finder) $\endgroup$ Commented Aug 19, 2018 at 18:49
  • $\begingroup$ I thought newtons method was needed anyway because of the cube root in the cubic formula. Why is the cubic formula faster than newtons method? $\endgroup$
    – Oppenede
    Commented Aug 20, 2018 at 12:01
  • $\begingroup$ "Faster" is not particularly the relevant part here. Cubic (and even quartic) root finding can be done symbolically, so if you want absolute speed, say for computer graphics purposes, don't even bother: build a LUT, binary search through that, and then lerp the value you actually need. You'll be a little bit wrong but no one's going to care from one frame to the next. For less of an error but still fast, by all means use newton-raphson, but if you have the cycles to spare, cubic root finding gives you the actual answer. No guess work, no iterative error reduction, just "the answer". $\endgroup$ Commented Aug 21, 2018 at 4:34
  • $\begingroup$ I'd say that the cubic and quartic formulae, implemented in floating-point arithmetic, are less likely to give you "the answer" than (properly written) iterative methods. Round-off occurs, and occasionally it's very significant. Root-finding formulae are vastly over-rated, IMO. A lot of people can't even code the quadratic formula properly. $\endgroup$
    – bubba
    Commented Aug 21, 2018 at 7:04
  • $\begingroup$ @Oppenede: "Why is the cubic formula faster". This issue is studied in gruesome detail in the reference cited in the last line of my answer. $\endgroup$
    – bubba
    Commented Aug 21, 2018 at 7:05

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .