December 27, 2013

Generating Bézier Curves

A Bézier curve is a directed path defined by a ordered set of reference points.   It starts at the first point and ends at the last point.  It rarely passes through any of the intermediate points, which instead act as attractors that warp the curve in their direction as the curve passes by them.

For details about this class of curves and several dynamic visualizations, I refer you to the article at this location

This position along a Bézier curve is specified by an independent variable in the range [0,1].  The value '0' is the start of the curve, the value '1' is the end of the curve.

One method of calculating a series of points along a Bézier curve is to use polynomial functions of this variable with coefficients that are linear in the positions of the reference points.  The down side of this method is that you need a different polynomial whenever you change the number of reference points.

My preferred method is recursive (note 1).  Given the ordered list of reference points 'list posList = [ .. vectors...];' and the independent variable 'float s;' in the range [0,1], the calculation proceeds as follows (note 2):

vector getBezierPos( float s ) {
   // This method uses the direct progressive linear interpolation definition
   // of an n-th order bezier, instead of the clumbersome formulae.
   list q = posList;
   integer nq;
   while ( (nq=llGetListLength(q)) > 1 ) {
        list q2 = [];
        integer k; for ( k=1; k < nq; k++ ) {

            vector p1 = llList2Vector(q,k-1);
            vector p2 = llList2Vector(q,k);
            q2 += (1-s)* p1 + s * p2;
        q = q2;
    return llList2Vector(q,0);

In the Wikipedia reference, find the dynamic visualization that demonstrates the construction of a Bezier curve as a progression of linear interpolations.  My implementation of getBezierPos() exactly follows that demonstration.

To elucidate the selection of values of 's', I will add here the function which rezzes prims along the Bézier curve.

integer nDot = 20;
string dotName = "dot";

generateBezierDots() {
    // The Bézier parameters is a variable in the range [0,1].  Divide this
    // interval into nDot segments. Rez dots at the mid point of these segments.
    float step = 0;
    if ( nDot > 0 )  step = 1.0 / nDot;

    integer k; for ( k=1; k <= nDot; k++ ) {
        vector p = getBezierPos( step * (k - 0.5) );
        llRezObject(dotName, p, ZERO_VECTOR, ZERO_ROTATION, 0 );

In my full implementation (note 3) of this script, I use llSensor() to find a series of reference markers.  The sensor() event makes note of the positions and descriptions of these prims, the description fields of the markers are used to sort the data, and the ordered position are stored in posList.


Note 1
Purists will note that I did not strictly use a recursive function.  Ultra purists will complain that said function should have been tail recursive.  I will leave it to them to post the pure implementation on their blogs and let them cope with a stack usage that that is quadratic in the number of reference points and with LSL not supporting tail recursion.

Note 2
If you want a vector tangent to the curve, in getBezierPos() catch the value"p2-p1" when nq is 2. 

Note 3
If you would like a copy of my full implementation, come to my vast land empire of 512 m-sq and pick up a copy from my vendor titled "Simple Bezier Curve".  You will get a combo object (mod/copy/trans, including scripts) that includes 4 green reference markers.  Rez this and touch the blue sphere.  Voila, 20 pink dots rezzed along the curve. 

Move the reference markers around and touch the blue sphere again.  Delete reference markers or shift copy more reference markers as you wish, however, make sure they all have distinct descriptions that will order them as you wish.

The vendor is here: