User Tag List

Results 1 to 6 of 6

Thread: Bezier Curve Spliner / de Casteljau's algorithm

  1. #1
    Clicker Multimedia Fusion 2SWF Export Module

    Join Date
    Sep 2006
    Posts
    1,537
    Mentioned
    1 Post(s)
    Tagged
    0 Thread(s)

    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:


    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.


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



    Attached files Attached files

  2. #2
    Clicker Multimedia Fusion 2SWF Export Module

    Join Date
    Sep 2006
    Posts
    1,537
    Mentioned
    1 Post(s)
    Tagged
    0 Thread(s)

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

  3. #3
    Clicker Multimedia Fusion 2SWF Export Module

    Join Date
    Sep 2006
    Posts
    1,537
    Mentioned
    1 Post(s)
    Tagged
    0 Thread(s)

    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

  4. #4
    Clicker Multimedia Fusion 2 DeveloperSWF Export Module

    Join Date
    Aug 2006
    Posts
    2,335
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    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.

  5. #5
    Clicker Multimedia Fusion 2SWF Export Module

    Join Date
    Sep 2006
    Posts
    1,537
    Mentioned
    1 Post(s)
    Tagged
    0 Thread(s)

    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.

  6. #6
    Clicker Multimedia Fusion 2
    Retriever2's Avatar
    Join Date
    Jun 2006
    Location
    United States
    Posts
    502
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

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

    Thanks for sharing

Similar Threads

  1. Counter Bezier curve effect
    By Sevennemesis in forum Multimedia Fusion 2 - Technical Support
    Replies: 2
    Last Post: 16th December 2012, 07:59 PM
  2. Curve movement
    By King_Cool in forum Multimedia Fusion 2 - Technical Support
    Replies: 1
    Last Post: 2nd December 2012, 05:11 AM
  3. Bezier curve movement in Flash
    By arthurh in forum SWF/Flash Export Module Version 2.0
    Replies: 4
    Last Post: 10th February 2012, 07:39 AM
  4. Bezier Curve
    By kornelijepetak in forum Released Extensions
    Replies: 1
    Last Post: 26th December 2010, 12:40 AM
  5. Bezier Curve
    By kornelijepetak in forum Extension Development
    Replies: 25
    Last Post: 10th May 2008, 05:45 AM

Posting Permissions

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