 # Thread: Bezier Curve Spliner / de Casteljau's algorithm

1. ## Bezier Curve Spliner / de Casteljau's algorithm

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:

-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

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

-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. Code:
```--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;

bezXArray[bezTotal] = x;
bezYArray[bezTotal] = y;
bezTotal = bezTotal + 1;
end

bezXArray[bezTotal] = bezXArray[bezTotal-1];
bezYArray[bezTotal] = bezYArray[bezTotal-1];
bezXArray[bezTotal-1] = x;
bezYArray[bezTotal-1] = y;
bezTotal = bezTotal + 1;
end

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, bezYTemp;
end

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

function initBezierMove(dist)
bezStep=0;
d = math.sqrt(math.pow(bezXArray[bezTotal-1]-bezXArray,2)+math.pow(bezYArray[bezTotal-1]-bezYArray,2));
bezEstDist=dist;
bezEstIncr=dist/d;
bezRatio=1;
bezX=bezXArray;
bezY=bezYArray;
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```  Reply With Quote

2. ## Re: Bezier Curve / de Casteljau's algorithm - (XLua)

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

3. ## Re: Bezier Curve / de Casteljau's algorithm - (XLua)

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  Reply With Quote

4. ## Re: Bezier Curve / de Casteljau's algorithm - (XLua)

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.  Reply With Quote

5. ## Re: Bezier Curve / de Casteljau's algorithm - (XLua)

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.  Reply With Quote

6. ## Re: Bezier Curve / de Casteljau's algorithm - (XLua)

Thanks for sharing   Reply With Quote

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•