Bezier Curve Spliner / de Casteljau's algorithm

[Pixelthief]

This is a very simple Lua file that can be used in XLua to calculate bezier curves quite easily in MMF2- this is handy for graphical effects and smooth movements. If you're interested in how bezier curves work check here:
http://en.wikipedia.org/wiki/B%C3%A9zier_curve
And this is merely an implementation of de Casteljau's algorithm:
http://en.wikipedia.org/wiki/De_Casteljau's_algorithm


In addition, this can normalize any generic bezier curve to find equidistant points to generate a constant velocity movement along this path. This is particularly handy in games, as camera controls and unit movements often want to follow a visually pleasing path (bezier curve) but don't want to move with pseudo-NDA acceleration.



It has the following controls:

function addBezierNode(x,y)
-When invoked, this adds a node to the bezier curve. This should be used for the first and last nodes, done before adding any helper nodes- or just add each in order. The X/Y parameters are the position for this node

function addBezierHelper(x,y)
-This adds a node second to the last on the chain. This is useful if you want to declare your endpoints first with addBezierNode, and then add any amount of helper nodes in order without changing the endpoints.

function adjustBezierNode(x,y,index)
-this modifies the node at the given index. Keep in mind this is a 0-based index, and helper nodes are inserted out-of-order at second to the last when used. Your start will always be at 0, endpoint at (# of nodes - 1)

function clearBezierNodes()
-this resets the list of nodes.


function calculateBezier(t)
-This returns the position along the curve at timestep t. T should be given as a floating decimal [0,1]. Please note that you'll need to use XLua's "Pass float" instead of "Pass integer" for this input. The position is then returned via a DoCall, set to function "ReturnBezier". Its return parameters are the X and Y position in that order.

function initBezierMove(dist)
-This initializes and resets the integrated bezier movement, starting at the first node and incrementing by roughly 'dist' pixels each step.

function incrBezierMove()
-This moves the index ahead by approximately the initialized amount of pixels a single time, and generates a callback returning the X & Y position on the curve at the current timestep. In other words, this moves X pixels along the line.

function fullBezierMove()
-This iterates through the entire curve, generating one callback for each node at roughly X pixels apart, where X was initialized. It will automatically halt when it reaches the end of the curve.

Feel free to use this for whatever purposes you want without credit! Or if you want, credit de Casteljau. Please note that this is a recursive algorithm with O(N^2) time complexity, so while it is quite fast with 5 nodes or so, you can easily break your program if you try any silly curves.

In addition- the bezier curve integration feature is NOT a closed solution 'quick method' as no such solution exists. As such, it is very processing intensive, and I would recommend moderation in its use! For reference invoke the O(N^2) de Casteljau's algorithm twice per node, making it O(N^3)! And using N square roots, for what thats worth.

--Constants:
bezMin=0.001;
--The higher this is set, the faster worst case performance
--The lower this is set, the more accurate the average

--Variables:
bezXArray={};
bezYArray={};
bezXTemp={};
bezYTemp={};
bezTotal=0;
bezStep=0;
bezEstIncr=0;
bezEstDist=0;
bezRatio=0;
bezX=0;
bezY=0;
bezFlag=false;


function addBezierNode(x,y)
 bezXArray[bezTotal] = x;
 bezYArray[bezTotal] = y;
 bezTotal = bezTotal + 1;
end

function addBezierHelper(x,y)
 bezXArray[bezTotal] = bezXArray[bezTotal-1];
 bezYArray[bezTotal] = bezYArray[bezTotal-1];
 bezXArray[bezTotal-1] = x;
 bezYArray[bezTotal-1] = y;
 bezTotal = bezTotal + 1;
end

function adjustBezierNode(x,y,index)
 bezXArray[index] = x;
 bezYArray[index] = y;
end

function clearBezierNodes()
 bezXArray={};
 bezYArray={};
 bezXTemp={};
 bezYTemp={};
 bezTotal=0;
end

function retBezier(t)
for i=0,bezTotal-1 do
 bezXTemp[i] = bezXArray[i];
 bezYTemp[i] = bezYArray[i];
end
for j=1,bezTotal-1 do
 for k=0,bezTotal - j - 1 do
  bezXTemp[k] = (1-t) * bezXTemp[k] + t * bezXTemp[k+1];
  bezYTemp[k] = (1-t) * bezYTemp[k] + t * bezYTemp[k+1];
 end
end
return bezXTemp[0], bezYTemp[0];
end

function calculateBezier(t)
 DoCall("ReturnBezier", retBezier(t));
end

function initBezierMove(dist)
 bezStep=0;
 d = math.sqrt(math.pow(bezXArray[bezTotal-1]-bezXArray[0],2)+math.pow(bezYArray[bezTotal-1]-bezYArray[0],2));
 bezEstDist=dist;
 bezEstIncr=dist/d;
 bezRatio=1;
 bezX=bezXArray[0];
 bezY=bezYArray[0];
 bezFlag=false;
end

function bezierMove()
 xtest, ytest = retBezier(bezStep+bezEstIncr);
 d = math.sqrt(math.pow(xtest-bezX,2)+math.pow(ytest-bezY,2));
 bezEstIncr = (bezEstDist / d) * bezEstIncr;
 bezRatio = bezEstDist / d;
 bezStep = math.min(bezStep + math.max(bezEstIncr,bezMin),1);
 bezX, bezY = retBezier(bezStep);
 if bezStep >= 1 then
  bezFlag=true;
  DoCall("EndBezierMove");
 end
 return bezX, bezY;
end

function incrBezierMove()
 DoCall("ReturnBezier",bezierMove());
end

function fullBezierMove()
 for i=0,math.floor(1/bezMin) do
  DoCall("ReturnBezier",bezierMove());
  if bezFlag then
   break;
  end
 end
end

[Pixelthief]

Whoa theres a lua scripting forum, I am completely oblivious
Anyone do a favor and move this >.>

[Pixelthief]

Thanks!
I've updated the files to include a slightly more accurate and faster algorithm- it has about 20% of the average standard deviation across data sets I tested

[Atom]

Nice script, i tested the earlier version before this thread got moved so i will test this new version soon also.

I guess if you did direction and node points you can move like a image editor would have this would get a lot more complex. This is still nice even without that though, thanks for the example/Lua Script.

---

By the way you are not the only one to have missed the sub forums here, over on TDC there is a new 3D project and it seems a load of people have never noticed the OpenGL forum or even the extensions either. Since there is a few coding sub forums now maybe it might be better to have a main Scripting/Coding forum and then -

dotNet Scripting, Lua Scripting, Python Scripting, Shader Development (HLSL), OpenGL and AS3 action scripting (when released) moved there as it would be clearer to people where all the coding sub forums are then.

[Pixelthief]

It would be a good idea, I'll remember to mention it to clubby

Aye image editing is sort of what this is good for. I'm using it in my current project to create custom path movements in the level editor that you can attach to objects. Sort of recreating what clickteam already did with some extra bells and whistles. But I figured, as long as I'm making it, someone else whos stumped by "constant speed bezier curves" might want it.

[Retriever2]

Thanks for sharing