Rough y(x) approximation for simplified Cubic Bezier curve

Question

I need to get a very rough (and fast) $y(x)$ approximation of a simplified Cubic Bezier curve to use in my animation code, where there's only one control variable:

$$ P_0 = (0, 0)\\ P_1 = (0, 0)\\ P_2 = (k, 1)\\ P_3 = (1, 1)\\ $$

The curve looks like this: http://cubic-bezier.com/#0,0,.25,1 (here $k = 0.25$)

With these control points, I get the following parametric Cubic Bezier equation (with $t = 0..1$):

$$ x(t) = 3k (1-t) t^2 + t^3\\ y(t) = 3 (1-t) t^2 + t^3 $$

Or, in other representation:

\begin{aligned} x(t) = (1 - 3k) t^3 + 3k t^2\\ y(t) = -2 t^3 + 3 t^2 \end{aligned}

How do I get a very very rough and simple $y(x)$ approximation for the given $k$ (0..1 too)? Solving the system is too difficult, and binary search is not suitable here because it's too slow. I've been banging my head around this for quite some time... Any ideas?

update: the approximation needs to be done in such way so that the curve is convex, like on the example, and starting/ending angles are approximately the same. Tried 3-point and 4-point Lagrange interpolating polynomials with no luck (see comments)...

update 2: discovered De Casteljau's algorithm, but it still seems too complex and slow for my needs. I need a really rough approximation within the constraints, and visually it looks simple, but on practice...

Answer 1

Another approach. Let $$ \mathbf{x} = (x_1,\ x_2,\ x_3) = (0.1,\ 0.5,\ 0.9) $$ and define the following polynomials: \begin{align} \theta_1(k) &= c_{11}k^4 + c_{12}k^3 + c_{13}k^2 + c_{14}k + 1,\\ \theta_2(k) &= c_{21}k^4 + c_{22}k^3 + c_{23}k^2 + c_{24}k + 1,\\ \theta_3(k) &= c_{31}k^4 + c_{32}k^3 + c_{33}k^2 + c_{34}k + 1, \end{align} where $c$ is the following matrix: $$ \begin{bmatrix} 0.16321393821380 & -1.14859165394532 & 2.51140325233548 & -2.52602553660396\\ 0.26949508735386 & 0.09905839089292 & -0.89714007482260 & -0.47141340342418\\ -2.08424569212321 & 1.94150558704136 & -0.87990952487339 & 0.02264962995523 \end{bmatrix}. $$ Now, given $k\in[0,1]$, fit a parabola to the points $(x_i, \theta_i(k)),\ i=1,2,3$. That is, let $$ \Theta(x) = \frac{(x-x_2)(x-x_3)}{(x_1-x_2)(x_1-x_3)}\theta_1(k) + \frac{(x-x_1)(x-x_3)}{(x_2-x_1)(x_2-x_3)}\theta_2(k) + \frac{(x-x_1)(x-x_2)}{(x_3-x_1)(x_3-x_2)}\theta_3(k). $$ Then $y$ as a function of $x$ is approximated by $$ y = \Theta(x) (-2x + 3x^{2/3}) + (1-\Theta(x)) x. $$ Below is the fitted function when $k=0.25$ (blue = true y, red = approx.).

Answer 2

Did you try to optimise it firs? $$ x(t)=3k(1−t)t2+t3\\ y(t)=3(1−t)t2+t3 $$ means you do:

$$ a = t^{2}\\ b = at\\ c = 3(1-k)a $$

so

$$ x(t) = kc+b\\ y(t) = c+b $$

you can go deeper :)

Answer 3

What about a clamped cubic spline with three knots and two slopes? The three knots are \begin{align} \left(x(0),y(0)\right)&=(0,0),\\ \left(x(0.5),y(0.5)\right)&=\left(\frac{3k+1}{8},\frac12\right)\\ \left(x(1),y(1)\right)&=(1,1). \end{align} And the slopes can be derived from \begin{align} \frac{dx}{dt}&=(1-3k)3t^2 + 6kt=3(1-k)t^2+6kt(1-t^2)\ge0,\\ \frac{dy}{dt}&=-6t^2+6t. \end{align} So $x(t)$ is monotonic increasing function in $t$ and the two tangent directions are given by: \begin{align} \left.\frac{dy}{dx}\right|_{x=0} &= \frac1k,\\ \left.\frac{dy}{dx}\right|_{x=1} &= 0. \end{align} See this, for instance, for how to construct a clamped cubic spline given the knots and tangent directions. If cubic splines are too complicated, you may try a quadratic spline, or even interpolate $y(x)$ using the single quadratic function that passes through $(x(0),y(0)),(x(0.5),y(0.5))$ and $(x(1),y(1))$. At any rate, note that your interpolant is not only a function in $x$, but also a function in $k$.

Answer 4

OK, I came up with a very rough approximation using simple Penner's equations:

$$ y(x) = 1 - (1 - x)^{1/max(k,0.2)} $$

Not sure if it's the best way but it seems to be working OK.

Answer 5

How about this one:

real F(real x)
{
real y0=3*exp(2/3*log(x))-2*x, y13=3*x-2*x*sqrt(x), y1=x;
if(k<1/3)
{
real w=3*k; w-=(5.5*x*(1-x)-1)*w*(1-w);
return w*y13+(1-w)*y0;
}
else
{
real w=(3*k-1)/2; w-=(2*x-1+3*w*x^12)*w*(1-w);
return w*y1+(1-w)*y13;
}
}

I admit that exponents and logarithms are a bit slow but, perhaps, the precision is reasonable.