Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
"rough" - sample a few points, and form an interpolating polynomial from them. –  J. M. Nov 8 '12 at 13:22
    
J.M, good idea! What is the simplest and fastest way of, say, 3-point polynomial interpolation (t=0, t=0.5, t=1)? –  Mourner Nov 8 '12 at 14:16
    
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. –  J. M. Nov 8 '12 at 14:20
    
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: wolfr.am/YQBwbK –  Mourner Nov 8 '12 at 14:44
    
Tried 4-point Lagrange interpolant ($t=0, 0.33, 0.66$) and it goes out of hand too... wolfr.am/STLA24 –  Mourner Nov 8 '12 at 15:08
show 3 more comments

5 Answers

up vote 3 down vote accepted

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

share|improve this answer
    
Looks awesome! I'll try that, thank you very much! –  Mourner Nov 9 '12 at 9:47
add comment

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 :)

share|improve this answer
    
Hmm, I don't know what to do next with this :) –  Mourner Nov 8 '12 at 17:05
    
1. Interpolate with some step between points. –  Oleg Shanyuk Nov 24 '12 at 22:18
    
2. Precalculate. Oh. I see answer with matrix. This is it! –  Oleg Shanyuk Nov 24 '12 at 22:19
add comment

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.

share|improve this answer
    
Nice approximation! How did y13 come up? –  user1551 Nov 9 '12 at 1:41
1  
k=1/3 is solvable explicitly :) –  fedja Nov 9 '12 at 1:52
    
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... –  Mourner Nov 9 '12 at 9:46
    
Sure, but let me know first if this works for you or it is too slow or imprecise :). –  fedja Nov 9 '12 at 13:39
    
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. –  Mourner Nov 9 '12 at 14:06
show 1 more comment

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

share|improve this answer
    
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. –  Mourner Nov 8 '12 at 17:31
    
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. –  user1551 Nov 8 '12 at 17:43
    
Oops, I meant $y(0)=0,y(1)=1,y'(0)=1/k$ and $y'(1)=0$. –  user1551 Nov 8 '12 at 17:54
    
Hmm, sounds like a really great idea! Thanks, I'll try that. –  Mourner Nov 8 '12 at 20:36
    
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$: wolfr.am/SFW2a8 –  Mourner Nov 8 '12 at 21:11
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.