Vtyjkyuk

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:

$$
hatx(t) = 3(b-a)(1-t)^2t + 3(c-a)(1-t)t^2+(d-a)t^3
$$

and then further scaled by $frac13(b-a)$ (not a useful step in general, but definitely useful here due to the monotonic condition) to yield:

$$
frachatx(t)3(b-a) = (1-t)^2t + fracc-ab-a(1-t)t^2+fracd-a3(b-a)t^3
$$

Which, by substituting $u=fracc-ab-a$ and $v=fracd-a3(b-a)$, gives the fairly easy to read:

$$
frachatx(t)3(b-a) = (v-u+1)t^3 + (u-2)t^2 + t
$$

And so far so good, $hatx(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=frac13(b-a)$, $p=(v-u+1)$ and $q=u-2$ gives:

$$
chatx(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]2p

-
\
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

- fracq3 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?

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.