2
$\begingroup$

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

  • 0
    Well, you did say "rough"... anyway, you might want to look at Hermite interpolation; try matching derivatives as well as points to capture the shape of your curve better.2012-11-08

5 Answers 5

3

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.). Function approximation when k=0.25

  • 0
    how did you get the values for the matrix of c, and how did you get the values for x1, x2, x3?2018-12-14
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 :)

  • 0
    2. Precalculate. Oh. I see answer with matrix. This is it!2012-11-24
2

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.

  • 0
    ---as I used Wolfram Alpha for plotting,--- My advice would be to get some decent graphic program that's out there for free. I personally like Asymptote, but it is not the only game in town :).2012-11-09
1

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$.

  • 0
    OK, tried the cubic function. It produces quite a close result but unfortunately with a part of the curve above 1. Example for $k=0.25$: http://wolfr.am/SFW2a82012-11-08
1

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.

  • 0
    `1.75194` is even better2018-12-14