No, not Pigs in Space, curves. I plan to do some Bezier experiments in Aditi, leading to some motion experiments, distance approximations, who knows what all. Certainly I don’t.
For reasons, I’m interested in moving things along curves. In particular, today I plan to try a cubic Bezier curve, mostly to see how to process such things in SLua.
Presently I have just two tests running, from a couple of days ago:
function Tests:test_bezier()
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)
self:assert_equals(b:at(0), p0)
self:assert_equals(b:at(1), p3)
local b05 = b:at(0.5)
self:assert_nearly_equal(b05.x, 550, 1)
self:assert_nearly_equal(b05.y, 475, 1)
end
function Tests:test_len()
local p0 = vector(0, 0, 0)
local p1 = vector(100, 0, 0)
local p2 = vector(200, 0, 0)
local p3 = vector(300, 0, 0)
local b = Bezier(p0, p1, p2, p3)
local len = b:compute_length()
self:assert_nearly_equal(len, 300, 1)
end
The first one gives me confidence that my basic calculation is probably correct. I say probably because it looks credible but I have not hand-calculated the expected values, in particular the Y value.
The second one is a dead-straight bezier and we correctly compute its length as 300. For the record here is the Bezier class:
Bezier = class()
function Bezier:init(p0, p1, p2, p3)
self.p0 = p0
self.p1 = p1
self.p2 = p2
self.p3 = p3
self.p1mp0 = self.p1 - self.p0
self.p2mp1 = self.p2 - self.p1
self.p3mp2 = self.p3 - self.p2
end
function Bezier:at(t)
local q0 = self.p1mp0*t + self.p0
local q1 = self.p2mp1*t + self.p1
local q2 = self.p3mp2*t + self.p2
local r0 = (q1-q0)*t + q0
local r1 = (q2-q1)*t + q1
return (r1-r0)*t + r0
end
function Bezier:compute_length()
local v0 = self.p0
local total = 0
local v1
local t
local max = 100
for i = 2,max do
t = i/max
v1 = self:at(t)
d = vector.magnitude(v1 - v0)
total = total + d
v0 = v1
end
return total
end
The length calculation is very brute force, we calculate 100 points along the curve and sum the distances between them. I just hacked that together a couple of days ago and I don’t like it. Shouldn’t the initial t in the loop be 1, not 2? Let’s work on that, and reason carefully. What I’d like to do is to come up with a compute_length that doesn’t do so many calculations if they’re not necessary.
I want to specify the number of intervals to sum up. Standard fence-post problem, if we want n intervals, we need n+1 points.
I’m not sure how to test what follows. Maybe by the time I explain it I’ll know. I propose to have a method that estimates the length of the curve using equally-spaced t values, ranging from one upward. I propose to compute my desired estimate by iterating that method, giving it intervals 1, 2, 4, 8, and so on, until the answer from the largest so far is sufficiently close to the previous answer, suggesting that the intervals are small enough. (It actually suggests that the previous interval was small enough. Interesting.)
I’ll use my initial bezier for the test, and if need be, I have a separate Lua program on my iPad that I can use to get an independent value of the length.
I’m going to just change the existing code and then see how to set up a reasonable test.
function Bezier:compute_length(intervals)
local v0 = self.p0
local total = 0
local v1
local t
local max = intervals
for i = 1,max do
t = i/max
v1 = self:at(t)
d = vector.magnitude(v1 - v0)
total = total + d
v0 = v1
end
return total
end
I accept an intervals value and use it, and iterate 1 through intervals. Since I also compute the value at p0, that gives me a full n intervals, n+1 points. And since I compute t=i/max, I’m sure that I end with t = 1, so I have spanned the whole curve. Now let’s do a test to check some estimates:
function Tests:test_intervals()
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 length = 0
for i, interval in ipairs({1, 2, 4, 8, 16, 32, 64}) do
local new_length = b:compute_length(interval)
local diff = math.abs(new_length - length)
local pct = 100*diff/new_length
local m = string.format("%3d %6.2fm %6.2ferr(m) %5.2f%%", interval, new_length, diff, pct)
print(m)
length = new_length
end
This gives me a nice report:
1 300.00m 300.00err(m) 100.00%
2 335.41m 35.41err(m) 10.56%
4 342.12m 6.71err(m) 1.96%
8 343.78m 1.67err(m) 0.49%
16 344.20m 0.42err(m) 0.12%
32 344.30m 0.10err(m) 0.03%
64 344.33m 0.03err(m) 0.01%
I’ll see if I can gin up a picture of that curve for you, but it’s pretty deep, and we are down below one percent error with only 8 probes, with an error of 1 2/3 meters out of nearly 350.
Our traveling beziers are rarely even ten meters, so with 8 probes we’re maybe 5cm out. Probably less, because trains don’t usually make very sharp turns.
Let’s convert that printing test to an actual test, perhaps like this:
function Tests:test_interval_8_within_one_percent()
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 l128 = b:compute_length(128)
local l8 = b:compute_length(8)
local diff = math.abs(l128-l8)
local percent_diff = 100*diff/l128
self:assert_nearly_equal(percent_diff, 0, 0.20)
end
That passes. I reduced the final percent—that’s 0.2%, not 2%—until just before it failed. The actual percentage error is less than 0.17%. That’ll do, pig, that’ll do.
There’s more to do, lots more, but this will do for the morning, I’ve got things to eat and drink.
Until next time, safe paths!