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

  • 1
    "rough" - sample a few points, and form an interpolating polynomial from them.2012-11-08
  • 0
    J.M, good idea! What is the simplest and fastest way of, say, 3-point polynomial interpolation (t=0, t=0.5, t=1)?2012-11-08
  • 0
    If it's just three points, you should be able to easily write down the Lagrange interpolant. On the other hand, a cubic (which would require four points) would have more flexibility, since a cubic can display inflexion points, while a quadratic cannot.2012-11-08
  • 0
    OK, I tried a 3-point Lagrange interpolant but the problem is that it produces curves where $y$ goes above $1$, see sample for $k = 0.25$ here: http://wolfr.am/YQBwbK2012-11-08
  • 0
    Tried 4-point Lagrange interpolant ($t=0, 0.33, 0.66$) and it goes out of hand too... http://wolfr.am/STLA242012-11-08
  • 0
    Of course, you should try shifting your interpolation points around; there's no reason to insist on, say, equispaced points...2012-11-08
  • 0
    That's true, but because the approximation needs to be programmatic (depending on k), that means there's no guarantee that any chosen set of points will produce a proper curve for the given k.2012-11-08
  • 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
    Looks awesome! I'll try that, thank you very much!2012-11-09
  • 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
    Hmm, I don't know what to do next with this :)2012-11-08
  • 0
    1. Interpolate with some step between points.2012-11-24
  • 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
    Nice approximation! How did y13 come up?2012-11-09
  • 1
    k=1/3 is solvable explicitly :)2012-11-09
  • 0
    Wow, that's some serious magic to me! Could you explain a little how did you come up with this? Sorry for a dumb question, I'm not very strong in Math...2012-11-09
  • 0
    Sure, but let me know first if this works for you or it is too slow or imprecise :).2012-11-09
  • 0
    OK, I'll try it! Not as easy to check as I used Wolfram Alpha for plotting, and it seems it doesn't support functions with several steps like this.2012-11-09
  • 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
    Yep, cubic spline seems too complicated for my needs... I tried to interpolate through several points using quadratic function (using Lagrange interpolating polynomial), but no luck - see the comments to my question above.2012-11-08
  • 0
    But you can use a cubic function, which is a special case of cubic spline and is much simpler to derive. I mean, try $y=ax^3+bx^2+cx+d$. Since you have $y(0)=0,y(1)=1,y'(0)=0$ and $y'(1)=1/k$, the coefficients $a,b,c,d$ can be solved easily. It's just four linear equations with four unknowns. Conceptually you only need to invert a 4x4 matrix.2012-11-08
  • 0
    Oops, I meant $y(0)=0,y(1)=1,y'(0)=1/k$ and $y'(1)=0$.2012-11-08
  • 0
    Hmm, sounds like a really great idea! Thanks, I'll try that.2012-11-08
  • 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
    This equation is really amazing. `1-(1-x)^1.75` is super close to sine2018-12-14
  • 0
    `1.75194` is even better2018-12-14