Let’s begin to create the data structure that represents a linearized Bezier curve. It’s a lot like the thing called “polyline”.
As all here surely know, a typical line segment, often called just a line, is represented by two points, one at each end: {p1, p2} kind of thing. It is common, in computer graphics, to represent a series of line segments that are connected end to end by a polyline, such as {p1, p2, p3, p4}, which represents the path p1 to p2, p2 to p3, p3 to p4.
p1---p2------p3----p4
Theory says, and experiment has confirmed, that while the lines between the original control points of a typical Bezier may not look much like the resulting curve, splitting the Bezier results in a much better fit. For our purposes, it appears that splitting into 8 Beziers making up the curve will give a good-enough fit. If not, sixteen surely will.
So today, let’s provide a new method on Bezier that returns a polyline based on N splits. Note that one split will result in two new Beziers, two splits results in four, and three splits results in eight Beziers. Eight Beziers will give us 32 points, but seven of those are duplicated at each join, so, if my calculation is correct, we can expect 25 points in our polyline.
We have a method split on Bezier already, returning two Beziers that draw the same curve as the original input one.
I think what I’d like to have, and I could be wrong here, is a method, oh, partition that takes N and partitions the Bezier N times and returns, therefore, 2^N Beziers. Let’s try that. Here’s my test:
function Tests:test_partition()
local p0 = vector(400, 400, 0)
local p1 = vector(500, 500, 0)
local p2 = vector(600, 500, 0)
local p3 = vector(700, 400, 0)
local b = Bezier(p0, p1, p2, p3)
local p1
p1 = b:partition(1)
self:assert_equals(#p1, 2)
p1 = b:partition(2)
self:assert_equals(#p1, 4)
p1 = b:partition(3)
self:assert_equals(#p1, 8)
end
Maybe we’ll write a test to assure ourselves that the resulting Beziers add up to the original, but we’re going to use split and we have already tested that it works in that regard. Let’s try to write partition. I was planning to make it recursive but let’s try a loop instead.
Hmm. It’s not coming to me quite how to do this. OK, how about this: we posit a function that takes an array of beziers, and returns an array containing each bezier from the original, split into two. Then partition should be:
function Bezier:partition(n)
local result = {self}
for i = 1, n do
result = self:split_array(result)
end
return result
end
Now we just need split_array. That should be easy enough:
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
I expect my test to run. Let’s find out why I’m wrong.
Error: /Users/ron/Desktop/repo/test.lua:451:
attempt to index number with 'split'. Tests:test_partition
Oh, forgot the index on the loop. Python thinking, no good in Lua. Try, also fixing the typo for with comma in the second assert.
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
And we are green. Should we test to be sure that these beziers add up to be the original? I think it would be wise, because, after all, they could easily be in the wrong order and That Would Be Bad.
OK, let’s do some arithmetic. There are 8 new Beziers, each indexed from 0 to 1 on t. Our original, supposedly tracing the same curve, goes from 0 to 1 also. So when we are checking our new Bezier #2, we should trace the new one from 1/8 to 2/8 and so on. Or looking at it the other way, if we trace the original from 0 to 1, we should use our first new one from 0 to 1/8, then the second, and so on.
I’m going to write a couple of new helper functions to compare them. Here’s the one that works:
function Tests:verify_vectors(check, original)
self:assert_nearly_equal(check.x, original.x, 0.001)
self:assert_nearly_equal(check.y, original.y, 0.001)
self:assert_nearly_equal(check.z, original.z, 0.001)
end
I know that works because I used it in this test:
function Tests:test_split()
local p0 = vector(400, 400, 0)
local p1 = vector(500, 500, 0)
local p2 = vector(600, 500, 0)
local p3 = vector(700, 400, 0)
local b = Bezier(p0, p1, p2, p3)
local b1, b2 = b:split()
local p_unsplit, p_split
for t = 0, 1, 0.01 do
p_unsplit = b:at(t)
if t < 0.5 then
p_split = b1:at(t*2)
else
p_split = b2:at((t-0.5)*2)
end
self:assert_nearly_equal(p_unsplit.x, p_split.x, 0.001)
self:assert_nearly_equal(p_unsplit.y, p_split.y, 0.001)
self:assert_nearly_equal(p_unsplit.z, p_split.z, 0.001)
self:verify_vectors(p_unsplit, p_split)
end
end
My second test has unknown flaws, I think because it is not indexing correctly, so I’ll do it again from scratch.
function Tests:verify(bezier, batch)
for i, check in batch do
for t = 0, 1, 1/8 do
local t_big = (i-1)*1/8 + t/8
local check_point = check:at(t)
local true_point = bezier:at(t_big)
self:verify_vectors(check_point, true_point)
end
end
end
The t_big calculation is weird but I’ll try to explain. The most telling point, however, is that the tests pass, so we know that the partition is good, in the right order, and all that jazz.
The t_big goes like this. We have eight partitions. So as one of the partitions iterates from 0 to 1, the larger one will move only 1/8 as far. And it should start at 0 for the first partition, 1/8 for the second, and so on. Thus:
local t_big = (i-1)*1/8 + t/8
We have a partition method that produces two-to-the-N sub-Beziers given an input Bezier. A wonderful place to stop.
I added two new functions to the Tests class:
function Tests:verify(bezier, batch)
for i, check in batch do
for t = 0, 1, 1/8 do
local t_big = (i-1)*1/8 + t/8
local check_point = check:at(t)
local true_point = bezier:at(t_big)
self:verify_vectors(check_point, true_point)
end
end
function Tests:verify_vectors(check, original)
self:assert_nearly_equal(check.x, original.x, 0.001)
self:assert_nearly_equal(check.y, original.y, 0.001)
self:assert_nearly_equal(check.z, original.z, 0.001)
end
I don’t know that we’ll add those permanently to the framework, but they were useful to me in this session. A lesson here is that it is easy to add a method to the framework, temporarily or permanently. The downside to permanent addition is that it takes up more code. On the other hand, the verify_vectors one will probably come in handy fairly often, so we might keep that one.
But it’s perfectly OK to add a method for one’s own purposes as well, though of course one has to be careful not to smush one of the existing methods. I wouldn’t suggest going around adding methods to system classes … but done carefully, we can make it work and possibly make it useful enough to justify the risks.
Anyway, now we have a convenient set of Beziers that add up to a larger one we’re given. Since our larger plan is to use the Bezier’s points to make a polyline, we’re probably a good ways along to getting what we need.
The current partition method is convenient for the Bezier object to perform, but it may not be quite what we need when we get all the way to whatever structure we want the movers to deal with. If that’s the case—and I think it may well be—we’ll reallocate responsibilities across the code we have then.
When a subordinate object needs to provide support for an object higher up the food chain, often the subordinate’s API has been created without understanding the caller’s needs. That’s why so many library APIs just aren’t quite what you want. We’ll try to avoid that mistake, and since we have time to change things, I think we’ll do fine.
Anyway, one more day, one more useful thing.
The tests! I had a concrete test to check, first that we got the right number of Beziers in our partition, and then finally that they were in the right order and value to add up to the original.
I love my tests. They show me that things work, and they help me find things that don’t. Yum, tasty!
Safe paths!