Arbitrary degree Bezier curves in 17 lines of lua

[scythe]

https://gist.github.com/1049155

http://en.wikipedia.org/wiki/Bezier_curve -- http://en.wikipedia.org/wiki/de_Casteljau's_algorithm

Inspired by ]this animation[, which describes the process more clearly and succinctly than I do here. You can see the levels of the "tree" in the animation -- the black lines are the first level, the green curves are the second, the blue ones are the third, and the final red curve is the goal.

The basic idea is that there is a tree (don't worry about where it came from) describing the bounding curves of the desired Bezier curve, and successive levels of the tree are constructed by interpolation between curves on the previous level. reductor is a metatable describing the way in which the levels of the tree relate to each other, basically, it says how to get a new level of the tree when you don't know what that level should contain, and it describes a two-dimensional array, so that when the tree is indexed you get an array of the bounding curves as defined in de Casteljau's algorithm, and when that array is indexed you get a specific bounding curve -- the k-th bounding curve on the j-th level is a Bezier curve between the k-th, k+1-th, ..., k+j-1-th control points, so that the first bounding curve on the highest level (where you see the indexing [#points][1]) is the Bezier curve between all of the control points, which is what we desire. From there, we need only define how two curves are interpolated (the usual way -- t varies from 0 to 1 as the interpolating curve moves from near-the-first to near-the-second), and this is put in as the indexing function (the way in which an element of an array is determined when that element is not defined) of the array-of-curves (i.e. not the tree, but each level of the tree), so that the tree, when asked for a level, gives an empty array with an indexing function which refers back to the previous levels of the tree, allowing it to be constructed entirely ad hoc from the lowest level, which is just the control points of the Bezier curve.

(I use the term "tree" loosely here. Obviously it is not a tree, but I don't know what to call it.)

Anywho, it was fun to write. It spits out a Lua function which takes t from 0 to 1 and returns that point's x and y coordinates along the Bezier curve, so, say, if you were to graph a hundred points for t between 0 and 1, it would trace the Bezier curve.

Code: Select all

--[[a parametric function describing the Bezier curve determined by given control points,
which takes t from 0 to 1 and returns the x, y of the corresponding point on the Bezier curve]]
function bezier(xv, yv)
        local reductor = {__index = function(self, ind)
                return setmetatable({tree = self, level = ind}, {__index = function(curves, ind)
                        return function(t)
                                        local x1, y1 = curves.tree[curves.level-1][ind](t)
                                        local x2, y2 = curves.tree[curves.level-1][ind+1](t)
                                        return x1 + (x2 - x1) * t, y1 + (y2 - y1) * t
                                end
                        end})
                end
        }
        local points = {}
        for i = 1, #xv do
                points[i] = function(t) return xv[i], yv[i] end
        end
        return setmetatable({points}, reductor)[#points][1]
end

On another note: I need to learn a new language. Any recommendations?

[atomizer]

Nice algorithm and nice challenge. Don't know lua myself, so I golfed it down to 9 (still readable) lines in javascript - https://gist.github.com/1049745. Features arbitrary amount of dimensions and linear memory usage.
So, uh, my recommendation should be obvious.