Fast Bezier curve generator (any degree)

M

Mooner01

Guest
GM Version: 2.3.0
Target Platform: ALL
Download: N/A
Links: Formula for Bezier curve, My source code (may drift), Vectors, Vector valued functions, Combinations, Pascal's Triangle and Combinations

Summary:
A fast bezier curve generator. Takes any amount of focus points and returns a list of points on the curve.

Tutorial:
Hello! This is the code that I wrote that quickly generates a bezier curve of any degree. The main function is the bezier function. The foci argument is a two dimensional array of the focus points in order: for example, foci=[[0, 0], [1, 1], [0, 1]] would make the function generate a bezier curve with focus points (0, 0), (1, 1), and (0, 1). Sharpness is the amount of line segments that the algorithm will generate: for example, if sharpness is 3, then the function will return a list of 4 points. The return is a list of points on the curve, in the same format as the foci argument. If you're just interested in the code, follow the github link above. Otherwise, here is a quick rundown:

First, check out the first link. It has the explicit definition of a bezier curve. I included a screenshot below for easy access. It's a lot of notation, so let's break it down. Note that 0 <= t <= 1 for this formula
1598812920622.png
First, B(t). This is a mathematical function like any other, and the bold letter means that it's a vector-valued function. A vector in this case represents an (x, y) point on the plane. If you're not familiar with vectors, check out the third link above. If you're not familiar with VVFs, check out the fourth link above. Basically, it means that it takes in a vector (in this case P_i) and returns a new vector for each value of t.

Now let's go across the equals sign and check out the next fun symbol, the summation sign. This is also known as a capital sigma, or as that funny looking E thing. Essentially, it means "Sum from i = 0 to i = n". It's very similar to a for loop, so it may be helpful to think of it that way. In this case, n is the amount of focus points that are given for the curve.

Next, the weird parentheses. This is a combination operation, it's the same saying as nCi, or n choose i. You may be familiar with this if you've taken a statistics or probability class before. If you're not familiar with them, check out the fifth link above.

Finally, we're in the home stretch. The next two statements are simple exponents and P_i is the ith focus given.

Okay, let's write some code. The hardest thing to write will be the combination, so let's start there. If you know the formula for combinations, you know it involves a lot of factorials, so let's write a quick factorial function. This isn't very technical and there are many ways to do it, but here is my version:
GML:
// num >= 0
// Returns num!
function factorial(num) {
    var fac = 1;
    for(var n = 2; n <= num; n++) {
        fac *= n;
    }
    return fac;
}
This requires very little explanation. Next, let's use these factorials to generate combinations. I refer to these using Pascal's triangle, because the list of all of the combinations on n is also the nth level of pascal's triangle! Very cool math fact right there. So let's generate a row from Pascal's triangle:
GML:
// Returns a horizontal row from pascal's triangle for coefficient use in bezier curve.
// level 0 = [1]
// level 1 = [1, 1]
// level 2 = [1, 2, 1] and so on
function pascal_vals(level) {}
We will return this as a list, so we need a list to add to. We will also use n! (rather, level!) many times, so let's get that now:
GML:
// Returns a horizontal row from pascal's triangle for coefficient use in bezier curve.
// level 0 = [1]
// level 1 = [1, 1]
// level 2 = [1, 2, 1] and so on
function pascal_vals(level) {
    var vals = [];
    var fac_level = factorial(level)
    return vals;
}
Okay, now we need to iterate across pascal's triangle. That will mean that we will iterate across the range [0, n] (note the inclusivity on both sides). For each iteration k, we will need k! and (level - k)!. Finally, we plug our values into the formula (level!)/(k! * (level - k)!):
GML:
function pascal_vals(level) {
    var vals = [];
    var fac_level = factorial(level);
    for(var k = 0; k <= level; k++) {
        var fac_col = factorial(k);
        var fac_opp = factorial(level - k);
        vals[k] = fac_level / (fac_col * fac_opp);
    }
    return vals;
}
One last operational improvement! If you look at Pascal's triangle, you'll notice that it's symmetrical. For efficiency's sake, that means that once we get past the midpoint we can use values from the already-generated opposite side. Let's add that in:
GML:
function pascal_vals(level) {
    var vals = [];
    var fac_level = factorial(level);
    for(var k = 0; k <= level; k++) {
        if(k <= level / 2) {
            var fac_col = factorial(k);
            var fac_opp = factorial(level - k);
            vals[k] = fac_level / (fac_col * fac_opp);
        } else {
            vals[k] = vals[level - k];
        }
    }
    return vals;
}
Phew. That was a lot of factorials. But do not rest, weary warrior, for now we begin the real trial. Everything else in the Bezier curve formula is pretty easy to write, so let's write it! First, let's see what variables we need to define at the start. We will need a list in which to insert points (this will be returned). We will also need to know how many foci we have (we could use array_length everywhere, but it's better practice to do it at the start and store it). Finally, we will need our list of combinations that we know how to generate. This will be from the level corresponding to the number of foci - 1. Let's implement!
GML:
// foci is a list of px points, sharpness is the integer amount of line segments generated (num points generated - 1).
// Returns a list of points in format [[x1, y1], [x2, y2], ... , [xn, yn]]
function bezier(foci, sharpness){
    var points = [];
    var num_foci = array_length(foci);
    var coeffs = pascal_vals(num_foci - 1);
    return points;
}
Okay, simple enough. Now, we need to take a step back. We're not actually planning on returning the bezier curve. While there are ways to try to do that, like returning a function that evaluates to points along the curve, that's not what I want to do so that's not what we're doing. We are simply returning a list of roughly evenly spaced points along the curve. More specifically, we're returning sharpness + 1 points along the curve, including endpoints. So, for each point, we need to evaluate where the bezier curve will be. Note the for.
GML:
function bezier(foci, sharpness){
    var points = [];
    var num_foci = array_length(foci);
    var coeffs = pascal_vals(num_foci - 1);
    for(var i = 0; i <= sharpness; i++) {}
    return points;
}
Now, for what value of t will we evaluate? Well, in the words of my old math teacher: Keep it simple, stupid! Let's just evenly space our t's along the range [0, 1]. Note in the formula we also need a 1 - t, so let's also store that as u. Finally, let's initialize our point as [0, 0], so we can add to it more easily:
GML:
function bezier(foci, sharpness){
    var points = [];
    var num_foci = array_length(foci);
    var coeffs = pascal_vals(num_foci - 1);
    for(var i = 0; i <= sharpness; i++) {
        var t = i / sharpness;
        var u = 1 - t;
        points[i] = [0, 0];
    }
    return points;
}
And now, the moment you've all been waiting for. The one, the only: The formula! That's right, we finally have all of the information we need to plug our numbers into the big ol formula. Since vector valued functions are cool, we can deal with x and y separately while we're summing. Our process will be simple: iterate across the range [0, num_foci], summing up values from the formula as we go. Let's do it!
GML:
function bezier(foci, sharpness){
    var points = [];
    var num_foci = array_length(foci);
    var coeffs = pascal_vals(num_foci - 1);
    for(var i = 0; i <= sharpness; i++) {
        var t = i / sharpness;
        var u = 1 - t;
        points[i] = [0, 0];
        for(var j = 0; j < num_foci; j++) {
            var coefficient = coeffs[j] * power(t, j) * power(u, num_foci - j - 1);
            points[i][0] += coefficient * foci[j][0];
            points[i][1] += coefficient * foci[j][1];
        }
    }
    return points;
}
And there you have it, folks. My voice definitely shifted over the course of writing this, and I am tired of writing, so I will refrain from further explanation. If you have any questions or comments, feel free to leave reply to this post. Have a good one!
 
Great stuff :)

This will be very helpful with a problem I'm having. Is there any way to set the length of the curve?

I'm trying to animate a spine as it moves, and right now it's just plotting a curved path to an end point using lengthdir etc. I can get it's length, then shrink the end point, replot the path and get it's length after alteration. Repeat until the path is the same length as the original value.

Do you know if that's possible to do without this trial and error process of iteration?

Something like:

1) original angle to "aim" for
2) set path length
3) set number of points to curve (your tutorial is presumably covering what GMS is doing behind the scenes to generate the curve when its not a straight path)

and hey presto! by the magic of formulas you get a path
 
Last edited:
Top