next »

[zerooneinfinity]

We are implementing 2D slide on UI for our game and wanted to use a cubic bezier curve.  We're a bit confused about our implementation though.

So we define a cubic bezier curve as:


//Assume p0->p3 are the control points of the bezier curve and t is the percent we've traversed down the curve.
p(x,y) bezierPoint(p0,p1,p2,p3,t)
{
     p(x,y) = ((1-t)^3)*p0 + 3*t*(1-t)^2*p1 + 3*t^2*(1-t)*p2 + t^3*p3;
     return p(x,y);
}

Now we have a loop:

loop
{
   t+=getFrameTime()*speed;
   p(x,y) = bezier(p0,p1,p2,p3,t);
}

Here's where my first question lies.  Originally we were doing something like this:

loop
{
   t+=getFrameTime()*speed;
   p(x,y) = bezier(p0,p1,p2,p3,t);
   
   objPos.x += OriginalPos.x + (DestPos.x - OriginalPos.x)*p(x,y).y
}

However, the motion didn't appear as we thought it would.  Then we realized that we should probably be using the x variable that gets returned when we pass in t to find the actual y value we should be using, like so:

loop
{
   t+=getFrameTime()*speed;
   p(x,y) = bezier(p0,p1,p2,p3,t);
   p1(x,y) = bezier(p0,p1,p2,p3,p(x,y).x);
   objPos.x += OriginalPos.x + (DestPos.x - OriginalPos.x)*p1(x,y).y
}

I believe the second implementation is the correct way, but wanted to run it past some people to make sure I'm not doing something completely boneheaded.

Thanks!

[jgrams]

It seems sort of odd to me...if you're doing it in only one dimension (x) why do you need the polynomial in two dimensions at all? Except maybe to help visualize the curve...

And even if you had the bezier curve code for something else, wouldn't p0.x be the original x and p3.x be the destination x, and then you'd just do:

Code:

loop
{
   t+=getFrameTime()*speed;
   p(x,y) = bezier(p0,p1,p2,p3,t);
   
   objPos.x = p.x;
}

Or am I missing something obvious?

[zerooneinfinity]

Yea I've been thinking about it more.  If I stick with one dimension I can still use the following source -- http://cubic-bezier.com/#0,0,1,1 but I have to stick the control points at the 1/3 and 2/3 point on x axis and then can vary them on the y.  As you can see though, it limits the range of the curve.

Thinking more about the 2D curve t no longer represents the x axis.  And so, I have a time variable x, but no t value.  The only way I can see to solve that is by using Newtons method to approximate.  Guess, a value that t would be given my time x, then see if p(t).x matches my current time variable and then use p(t).y as my scale.

[zerooneinfinity]

Here's the code: It's a really naive way of finding x but it'll do until I find I need to optimize it.

   /* 1D
    * b is coordinate of first control point
    * c is coordinate of second control point
    * t is value between 0 and 1 (percentage through the path)
    */
   inline float bezierPoint(float b, float c, float t)
   {
      const float u = (1-t);
      const float uu = u*u;

      const float tt = t*t;
      const float ttt = tt*t;
      return 3*ttt*uu*b + 3*tt*u*c + ttt;
   }

   /*
    * 2D
    */
   inline f32 bezierPoint(Vector<f32> b, Vector<f32> c, float x)
   {
      Vector<f32> prevPos(-1,-1,-1);

      for(float t = 0; t < 1; t+=0.005)
      {
         const float u = (1-x);
         const float uu = u*u;

         const float xx = x*x;
         const float xxx = xx*x;

         Vector<f32> pos = Vector<f32>(3,3,3)*Vector<f32>(x,x,x)*Vector<f32>(uu,uu,uu)*b
                           + Vector<f32>(3,3,3)*Vector<f32>(xx,xx,xx)*Vector<f32>(u,u,u)*c
                           + Vector<f32>(xxx,xxx,xxx);

         if(prevPos.x() == -1 && prevPos.y() == -1)
         {
            //First point
            prevPos = pos;
         }
         else
         {
            const float prevCloseness = std::abs(prevPos.x() - x);
            const float currentCloseness = std::abs(pos.x() - x);
            if( prevCloseness < currentCloseness )
            {
               //We're done
               return prevPos.y();
            }
            else
            {
               prevPos = pos;
            }
         }
      }

      return prevPos.y();
   }

[jgrams]

Oh, right. I was thinking you could just do x = bezier(t) but then, as you say, it limits the range of the bending that you can get. The Bernstein polynomial (bezier curve) probably isn't really what you want here, but some other form of polynomial interpolation between the points. Off the top of my head I'm not sure exactly how you'd derive that.

But as long as you have something that works...

Code:

inline float bezierPoint(float b, float c, float t)
{
   ...

   return 3*ttt*uu*b + 3*tt*u*c + ttt;
}

Shouldn't that first term be 3*t*uu ??


Edit: Seemed like an interesting little math problem, so I played with it a bit, and it seems like using a cubic polynomial directly will only give you a limited degree of smoothing at the ends: http://www.arestlessmind.org/2014/08/17/cubic/. I assume you could get more with a higher degree polynomial, but I didn't feel like doing the math.

On the off chance that anyone actually cares...if you have x(t) = a*t^3 + b*t^2 + c*t + d, then you have four degrees of freedom. Fixing the two endpoints removes two of those. I removed a third by requiring the initial and final velocities to be equal (to make it symmetrical), which leaves one parameter to play with.

Code:

x0 and x1 are your endpoints
dx = x1 - x0

d = x0
c = dx * ?? (choose a value between zero and one)
b = 3*(dx - c)
a = -2*dx

[Crimsontide]

My suggestion would be to use a 1D catmullrom spline.  In C++ code it looks something like:

Code:

template <typename T> T CMRSpline (const Vector<T,4>& k, T i) {

	const T k0 = static_cast<T>(0.0);
	const T k1 = static_cast<T>(0.5);
	const T k2 = static_cast<T>(1.0);
	const T k3 = static_cast<T>(1.5);
	const T k4 = static_cast<T>(2.0);
	const T k5 = static_cast<T>(2.5);

	// setup matrix
	const Matrix<T,4,4> cmr_matrix(	-k1, k3, -k3, k1,
					k2, -k5, k4, -k1,
					-k1, k0, k1, k0,
					k0, k2, k0, k0 );

	Vector<T,4> c = Mul(cmr_matrix,k);
	return ((c.x*i + c.y)*i + c.z)*i + c.w;
	}

If my understanding is correct (its been a long time since I've played around with this) is that Bezier Curves don't hit their control points, they just come close.  Where-as Catmull-Rom splines hit all their control points.

In your loop you'll want something like:

Code:

t+=getFrameTime()*speed;
objPos.x = OriginalPos.x + (DestPos.x - OriginalPos.x)*CMRSpline(vx,t);
objPos.y = OriginalPos.y + (DestPos.y - OriginalPos.y)*CMRSpline(vy,t);

Notice how its = and not +=.  Also vx would be the x-coordinate of the four control points, and vy would be the y-coordinate of the four control points.

If you want to cap the interpolation, cap the i (which you called t) value like:

Code:

i = min(max(i,0),1);