After thinking about searching in my new L_Bezier, I think I’ll try a different storage scheme. Summary article, infinite painful detail left out.
We have various kinds of paths that our vehicles follow, including
The mover code wants to think in terms of distance traveled vs time, meters per second kind of thing. That’s easy in the 0.5 meter case, take the distance you want, divide by 0.5, and there’s the subscript of the points you need, interpolate and all good.
But Bezier curves don’t understand distance, so we have to search back and forth to find the distance we want, resulting in evaluating the Bezier multiple times in every timer cycle. It would be nice to do something more efficient.
The current trial solution is the L_Bezier object, standing for “linearized bezier”. Simply, the L_Bezier represents a collection of points at varying distance from each other, making up a straight line segment path (a polyline) that approximates the original Bezier well.
We can ask an L_Bezier for point_at_distance(d), and it will produce the interpolated point along the polyline segment that contains distance d: just what we need.
In the preceding article, I implemented L_Bezier using a sort of fence-post data structure of alternating points and lengths:
p1--l1--p2---l2---p3-l3-p4----l4-----p5
I’ve found this alternating structure hard to build, and it is no easier to process for looking up the info we need. So the new plan is to store the lengths separately, and to start the length array with a 0 value, which I think will make searching easier.
The L_Bezier will now keep two arrays, one of the lengths of its segments, and the other the consecutive points of the polyline that makes it up.
_lengths 0 p1-p0 p2-p1 p3-p2
_points p0 p1 p2 p3
So when we find the index of the length we desire, the far point is under the index and the near point is in the previous cell.
The L_Bezier class is pretty simple:
L_Bezier = class()
function L_Bezier:init(beziers)
self.length = 0
self._lengths = {}
self._points = {}
self.ready = false
for _, b in beziers do
self:_add(b.p0)
self:_add(b.p1)
self:_add(b.p2)
-- self:_add(b.p3)
end
self:_add(beziers[#beziers].p3)
end
function L_Bezier:_add(point)
local len
local n = #self._points
if n == 0 then
len = 0
else
len = point:dist(self._points[n])
end
self.length += len
table.insert(self._lengths, len)
table.insert(self._points, point)
end
function L_Bezier:find_distance(d)
local remaining_distance = d
for i, len in self._lengths do
if remaining_distance < len then
return i, remaining_distance
end
remaining_distance -= len
end
return nil
end
function L_Bezier:point_at_distance(d)
local idx, remaining_distance = self:find_distance(d)
local p0 = self._points[idx-1]
local p1 = self._points[idx]
local len = self._lengths[idx]
local frac = remaining_distance/self._lengths[idx]
result = p0*(1 - frac) + p1*frac
return result
end
function L_Bezier:dump()
s = ''
for i,len in self._lengths do
s = s .. tostring(len) .. ' '
end
print(s)
s = ''
for i, pt in self._points do
s = s .. tostring(pt) .. ' '
end
print(s)
end
I have a few tests for it. I have seen them break so often that I am sure they suffice to show that it works as intended. Here they are:
function Tests:test_l_bezier()
local b = self:sample_bezier()
local l_bezier = b:linearized(0)
local lengths = l_bezier._lengths
local points = l_bezier._points
self:assert_equals(lengths[1], 0)
self:assert_nearly_equal(lengths[2], 141.42, .01)
self:assert_equals(points[1], b.p0)
self:assert_equals(points[4], b.p3)
end
function Tests:test_l_bezier_find()
local b = self:sample_bezier()
local lb = b:linearized(3)
local first_len = lb._lengths[2]
local index = lb:find_distance(first_len / 2)
self:assert_equals(index, 2)
end
function Tests:test_l_bezier_interpolation()
local b = self:sample_bezier()
local lb = b:linearized(0)
-- lb:dump()
local sqrtby2 = 100*math.sqrt(2) / 2
pt = lb:point_at_distance(lb.length/2)
self:assert_nearly_equal(pt.x, 550, 0.01, "x")
self:assert_nearly_equal(pt.y, 500, 0.01, "y")
end
function Tests:test_l_bezier_vs_bezier()
local pt
local bpt
local b = self:sample_bezier()
local lb = b:linearized(3)
pt = lb:point_at_distance(0)
bpt = b:at(0)
local idx, d = lb:find_distance(0)
self:assert_nearly_equal(pt.x, bpt.x, 0.01, "zero x")
self:assert_nearly_equal(pt.y, bpt.y, 0.01, "zero y")
local len = lb.length
pt = lb:point_at_distance(len/2)
bpt = b:at(1/2)
self:assert_nearly_equal(pt.x, bpt.x, 0.01, "x")
self:assert_nearly_equal(pt.y, bpt.y, 0.01, "y")
end
test_l_bezier just checks some hand-calculated values in the output. First test I wrote, basically.test_l_bezier_find tests the find_distance method, the one that does the search of the lists to find which segment we need. That basically worked properly, as intended.test_l_bezier_interpolation was an early test to be sure that the interpolation between points worked. It failed sometimes, and was actually the one that served to find the final problem.test_l_bezier_vs_bezier compares a couple of results from the original Bezier and the linearized one. I intended it as a sort of final acceptance test and expected it to work. It did not, and led to the trouble that you’ll see below if you are foolish enough to read past my recommended stopping point.I had a terrible time yesterday, and nearly again today, and I’ve decided to erase all that painful detail from the article. Not a pretty sight, me thrashing like a fish on the line.
I am now quite confident (0.95) that the linearized method on Bezier returns an L_Bezier instance that correctly represents the line segments of a series of small Beziers that add up to the original Bezier.
And I’m pretty confident (0.85+) that the point_at_distance of L_Bezier does the correct interpolation to find the point part-way along the correctly-chosen segment. In short, I think it works.
The trouble I had was all in the point_at_distance method, the one that does the interpolation. If I had figured out a way to test that function directly, I might have seen right away all the ways it wasn’t working, and found the one that works much sooner.
That should be possible. I’ll make a note to try it as an exercise. The general rule is that tests should b very close to the tiny thing you’re interested in, rather than checking remote values that will be right if the tiny thing works.
I could be right; I could be wrong. I’ll try, and find out.
Today wasn’t so bad, though I did kind of debug around for a while. I did develop a handy testing trick that I’ll perhaps write up later.
I think the L_Bezier idea is a decent one, supporting a variable-length linear segmentation of a Bezier. I had great difficulty making it work, but it seems pretty simple and perhaps can be more so. We’ll see, in due time.
Further work will include the rotation info that we need, not just the position info. Should be straightforward, but rotations are the work of the devil, so there’s always something.
For now, we’ve got what we set out to get. All’s well that ends, innit?
Safe paths!