Having read and experimented a bit with Luau performance, I’m in a refinement frame of mind. Let’s look at the Bezier and its approximation as linear segments.
Let me refresh my mind on the issues around Beziers as we encounter them.
Our vehicle movers move by stepping a small distance every fraction of a second. They have an internal notion of speed, which amounts to a distance to travel each step. Their speed can vary over their course.
Vehicles follow a path. They keep track of the current distance they’ve traveled, and ask the path for the information for the current distance plus the next step they want to take. The information is, basically, a position and direction, so that the vehicle knows where to go and what direction to be pointing.
So a path needs to be able to return information given a distance along itself. But that is difficult with a Bezier path: the Bezier curve cannot easily answer that question other than by some kind of repeated searching. Very slow, tedious, boring, and did I mention slow?
A (cubic) Bezier has four control points, defining three lines between them, and it turns out that the path along the lines is approximately equal to the path along the curve. The approximation is very poor and unsuitable for any but the roughest use.
However. A Bezier can be split rather easily into two end-to-end Beziers. And the control lines for those two Beziers are a much better approximation to the curve. And it turns out that if we split again and again, the resulting eight Beziers are a very good approximation to the curve, at least for the curves we are using.
That discovery led me to create code that can convert a Bezier, which cannot be readily indexed by distance, into a polyline kind of thing which is much more amenable to distance indexing. It’s still a search, but it’s a straightforward and fast one, without all the calculation required to search the Bezier itself.
My mission this morning is to examine the code around the Bezier, its conversion to the polyline, and the searching thereof, to see how small and fast I can make it.
A simple example is this: If we’re going to use this thing, we do not need the ability to compute a point on a Bezier at all, so our code need not include it, saving precious memory.
We’ll begin by reviewing the existing objects. I”ll show relevant code but not necessarily all of it.
Bezier = class()
function Bezier:init(p0, p1, p2, p3)
self.p0 = p0
self.p1 = p1
self.p2 = p2
self.p3 = p3
self.array = {p0,p1,p2,p3}
self:final()
end
The Bezier stores its points in two forms: that’s because in the last article we were comparing the speed of those two schemes.
function Bezier:partition(n)
local result = {self}
for i = 1, n do
result = self:_split_array(result)
end
return result
end
function Bezier:_split_array(beziers)
result = {}
for _, bez in beziers do
local b1, b2 = bez:split()
table.insert(result, b1)
table.insert(result, b2)
end
return result
end
function Bezier:split()
local a = self.p0
local b = self.p1
local c = self.p2
local d = self.p3
local e = (a+b)/2
local f = (b+c)/2
local g = (c+d)/2
local h = (e+f)/2
local j = (f+g)/2
local k = (h+j)/2
return Bezier(a,e,h,k), Bezier(k,j,g,d)
end
The partition method, typically called with parameter 3 for 3 splits, repeatedly processes a list of Beziers, splitting each one. Three splits: eight new Beziers, the number we think we want.
However, we don’t really want Beziers at all, we want what we can make out of them:
PolylinePath = class()
-- contains variable-length linear segments
function PolylinePath:init(polyline)
self._points = polyline
self._lengths, self._length = self:_create_lengths(self._points)
end
-- class methods: do not assign to self
function PolylinePath:from_beziers(bez_array)
return self(self:_create_polyline(bez_array))
end
function PolylinePath:_create_polyline(beziers)
local points = {}
for _, bezier in beziers do
table.insert(points, bezier.p0)
table.insert(points, bezier.p1)
table.insert(points, bezier.p2)
end
local final_point = beziers[#beziers].p3
table.insert(points, final_point)
return points
end
There’s more but this looks like a place to start. The PolylinePath starts from a collection of Bezier instances. It disassembles those instances with a somewhat tricky loop that solves the fence-post problem: given two Beziers with points
p0, p1, p2, p3, q0, q1, q2, q3
It turns out, since the Beziers split up an original one, that p3==q0. We don’t want a zero-length segment in our polyline, so we want our output to be
p0, p1, p2, q0, q1, q2, q3
So we just process the three initial points on each supplied Bezier, and then append in the very last point to finish the job. Tricky but that’s what we need.
It seems to me that it is proper for the Bezier to know how to split itself: that is a Bezier-specific thing. And it seems to me that a proper output for that certainly could be more beziers, but it could just as well be an array of points. The Bezier is responsible for knowing how to get the points, but we can ask it to provide the points in a form we need.
I’m not sure whether we should ask for the version of the points with the duplicates, and remove them elsewhere, or to expect the Bezier to do the job.
In fact, what we’ll do, to learn what we want the code to do and what the code wants to do, is to create a new object, with tests, of course.
I’m building in the bezier_dev.lua file, where all the related things are. The new test feature starts with a hookup:
function _:featureBezierCreatesPolyline()
_:describe("Bezier creates polyline", function()
_:test("hookup", function()
_:expect("oops").is("test was found")
end)
end)
end
That provides the expected failure:
Feature: Bezier creates polyline
Actual: oops, Expected: test was found. Test: 'hookup'.
Bezier creates polyline, 2 Tests: Pass 1, Fail 1, Ignored 0.
I notice that my test counts each call to test plus each assert. Maybe that’s OK. Some rando sent me an email about that in fact. Apparently I have a reader that I didn’t know about. Anyway test is running, now down to work.
function _:featureBezierCreatesPolyline()
_:describe("Bezier creates polyline", function()
_:test("partition step", function()
local points = sample_bezier_points()
local splitter = BezierSplitter(points)
local split = splitter:split()
_:expect(#split).is(7)
end)
end)
end
BezierSplitter = class()
function BezierSplitter:init(array)
self.array = array
end
function BezierSplitter:split()
return self.array
end
That’s enough to fail. Note that I decided I want it to suppress the inner values. I think that’s a wrong decision, so I’ll change the test to expect 8. Why? Because when I split again I don’t want to have to de-fence-post in the split code. Just guessing. Changed to 8, still fails.
Now to do split. We need to take four values and produce 8 similarly to how we do it in Bezier:split:
function Bezier:split()
local a = self.p0
local b = self.p1
local c = self.p2
local d = self.p3
local e = (a+b)/2
local f = (b+c)/2
local g = (c+d)/2
local h = (e+f)/2
local j = (f+g)/2
local k = (h+j)/2
return Bezier(a,e,h,k), Bezier(k,j,g,d)
end
I’ll copy that into my new split and whack it until it succumbs to my will.
function BezierSplitter:split()
local a = self.array[1]
local b = self.array[2]
local c = self.array[3]
local d = self.array[4]
local e = (a+b)/2
local f = (b+c)/2
local g = (c+d)/2
local h = (e+f)/2
local j = (f+g)/2
local k = (h+j)/2
return {a,e,h,k, k,j,g,d}
end
That will surely give me the right number of things. There’s no check for whether they are the correct things. We should think about that and deal with it somehow.
Test passes, of course. However, what we really want is to split the array again and again.
Let’s change the calling sequence to accept the number of splits we want:
function BezierSplitter:split(numberOfSplits)
local a = self.array[1]
local b = self.array[2]
local c = self.array[3]
local d = self.array[4]
local e = (a+b)/2
local f = (b+c)/2
local g = (c+d)/2
local h = (e+f)/2
local j = (f+g)/2
local k = (h+j)/2
return {a,e,h,k, k,j,g,d}
end
And a test for two:
_:test("partition twice", function()
local points = sample_bezier_points()
local splitter = BezierSplitter(points)
local split = splitter:split(2)
_:expect(#split).is(16)
end)
Fails, of course, 8 not 16.
Hmm … how to do this? I think I want to step through my array by fours, producing splits. I think I’ll have to write this to find out how to write it.
I’ll ignore that second test for a bit.
This passes the first test:
function BezierSplitter:split_by_fours(array)
local result = {}
for i = 1, #array, 4 do
local a = array[i]
local b = array[i+1]
local c = array[i+2]
local d = array[i+3]
local e = (a+b)/2
local f = (b+c)/2
local g = (c+d)/2
local h = (e+f)/2
local j = (f+g)/2
local k = (h+j)/2
for p in {a,e,h,k, k,j,g,d} do
table.insert(result, p)
end
end
return result
end
Note: the above for loop is wrong: it does not expect the index, which means ' is the index, which means that the output has the right number of elements but they are all integers. My larger test below finds this.
Now I think I can pass the second. unignore it, make sure it still fails. It does, 8 not 16. Fix split:
function BezierSplitter:split(numberOfSplits)
local array = self.array
for i = 1, numberOfSplits do
array = self:split_by_fours(array)
end
return array
end
Test passes. Test three just for drill:
_:test("partition thrice", function()
local points = sample_bezier_points()
local splitter = BezierSplitter(points)
local split = splitter:split(3)
_:expect(#split).is(32)
end)
Passes. Now let’s try something more robust: we’ll test this output against the original Bezier’s split.
_:test("compare split with original Bezier", function()
local points = sample_bezier_points()
local splitter = BezierSplitter(points)
local split_points = splitter:split(3)
local bez = sample_bezier()
local b_split = bez:partition(3)
local bezier_points = {}
for _, b in b_split do
table.insert(bezier_points, b.p0)
table.insert(bezier_points, b.p1)
table.insert(bezier_points, b.p2)
table.insert(bezier_points, b.p3)
end
_:expect(split_points).is(bezier_points)
end)
After more messing about than I’d like, I find the two(2!) cases where I left off the _ for the index in a for loop. My final code in BezierSplitter is this:
BezierSplitter = class()
function BezierSplitter:init(array)
self.array = array
end
function BezierSplitter:split(numberOfSplits)
local array = self.array
for i = 1, numberOfSplits do
array = self:split_by_fours(array)
end
return array
end
function BezierSplitter:split_by_fours(array)
local result = {}
for i = 1, #array, 4 do
local a = array[i]
local b = array[i+1]
local c = array[i+2]
local d = array[i+3]
local e = (a+b)/2
local f = (b+c)/2
local g = (c+d)/2
local h = (e+f)/2
local j = (f+g)/2
local k = (h+j)/2
for _, p in {a,e,h,k, k,j,g,d} do
table.insert(result, p)
end
end
return result
end
So this split gets the same vectors as the original one in Bezier, which has been checked by drawing pictures and whatever other testing we have for it.
Now I have one more concern, which is that we know we really want a polyline kind of thing with the duplicate points (k, k) above, removed. It seems to me that our BezierSplitter could do that job for us, though we’d have to change all our tests if we just wanted to return the resulting array with extras removed.
Let’s try. I can see two ways to go. One is a final pass over the data removing the extras. The other would be to change the splitting logic to just do it. The first is a bit less efficient. Let’s code it that way first:
_:test("polyline", function()
local points = sample_bezier_points()
local splitter = BezierSplitter(points)
local split_points = splitter:polyline(3)
_:expect(#split_points).is(25)
end)
And the new method:
function BezierSplitter:polyline(numberOfSplits)
local result = {}
local splits = self:split(numberOfSplits)
for i = 1, #splits, 4 do
table.insert(result, splits[i])
table.insert(result, splits[i+1])
table.insert(result, splits[i+2])
end
table.insert(result, splits[#splits])
return result
end
This passes the test. It’s one more method, not a tiny one, and it is one more pass over the data, with one more table creation.
Possibly we can do better, but not today. Today this is nice progress, a little class that doesn’t trouble itself with actually calculating a Bezier at all, just transforming it into a nicer form.
Possibly, we could do it all in one pass, maybe with a clever recursive algorithm. Possibly, if we had that clever recursive algorithm, we could understand it two days later if we had to. Possibly not.
For now, a nice step forward. That’s enough for any day around here.
Safe paths!