… for searching. Today I want to explore some ideas for searching path objects. That capability is central to the operation of our vehicles. No truly new code, just thinking and some new tests.
Most Valkyrie Transport vehicles follow a defined path. This might be a roller coaster rail, train or tram tracks, or a path in the woods. Their paths are defined in various ways. SLRR trains search out SLRR guides and compute paths between them. Coasters have a path built in, defined as a series of points pre-computed along a twisting curve created in Blender. Our commercial trams use guides similar to SLRR. And so on.
One fundamental problem for all these vehicles is to transform a distance along the path into the position and rotation in the world that corresponds to that position, to which the vehicle then moves. Increment distance, get new position, move. Repeat.
So the problem comes down to coming up with a function that, given distance along the full path, returns the information needed to reposition the vehicle, typically position and rotation. Or, actually, to come up with a number of such functions, dealing with the various kinds of information we can garner from the world, such as guides, or from stored information such as the shape of a coaster. Today, I plan to work on that problem.
I’m starting with an assumption that is somewhat important, at least for now:
There are alternatives to this assumption, of course. We could, for example, decide that some paths—or all paths—would be represented by cubic Bezier curves. But if we made that assumption, we would have a difficult problem converting distance to a point, because Bezier curves do not have a closed expression for finding a point at a given distance away: it comes down to searching.
So, instead, the assumption above implies that we will convert any Bezier or similar curve into a series of straight segments that fit the path well. Then we’ll fly that path, which will look just as good and be far less costly in script time.
The equal-length assumption is significant. If all the segments are equal length, then to find the one at distance d, we can divide d by the segment length, and that will be the index in an array for the corresponding segment. Equal length segments are kind of the ideal case for solving our problem, but for now, we’ll be assuming that we can’t always get what we want. If the segments are not of equal length, we’ll have to search an array to find the one we need. This will still be faster than computing lots of Bezier points.
We (I) need to learn good ways of representing these segments in a table and searching that table. The situation will look something like this:
P1---l1---P2-l2-P3----l3----P4--l4--P5
It’s a typical fence-post situation, with n segments and n+1 posts. We would prefer to store as little information as possible, of course, but maybe what would be really convenient might be a list like this:
{ {P1, l1, P2}, {P2, l2, P3}, {P3, l3, P4}, {P4, l4, P5}}
With that list and a little messing about, we could wind up with the two P values we need, plus the fraction of the way along the line we are, so that we can interpolate.
In a number of prior articles1, we have experimented with this problem / solution, and the current test file includes a few concepts that apply. I’ll re-educate myself on where we stand.
There is an object Waypoint with this definition:
Waypoint = class()
function Waypoint:init(min_d, max_d, min_t, max_t)
self.min_d = min_d
self.max_d = max_d
self.min_t = min_t
self.max_t = max_t
self.length = max_d - min_d
self.delta_t = max_t - min_t
end
The object knows the minimum and maximum distance along the curve that it covers, and the minimum and maximum t-value corresponding to those distances. It can answer whether it contains a given distance, and can evaluate that distance to return an interpolated t-value. With this object, we would return to evaluate the Bezier one more time once we find the right Waypoint and compute the t-value.
There is an object Multipath:
Multipath = class()
function Multipath:init()
self.paths = {}
self.length = 0
end
This object builds up a table of entries with a low distance value, a high distance value, and a path, which is unprocessed by the Multipath but is presumably something that defines the path over that distance range.
There is an object D_Bezier:
D_Bezier = class()
function D_Bezier:init(bezier)
self.bezier = bezier
self.waypoints = self:make_waypoints(4)
end
This object translates from a distance value to a point on the Bezier that it contains. It does so by creating Waypoints and using them. So you can take a Bezier, embed it in a D_Bezier, and thereafter interrogate it by distance and get back a point.
This is all good stuff, stepping stones on the way to what we will really want. We don’t know yet what we really want. Each step gives us information and insight. Then we take another step. Soon enough we find ourselves in a better place.
I find myself wanting to take this code apart, use part of it directly, use part of it for inspiration, and build new things on top of it. Right now I’m just in a file called test on my Mac, so I think I’ll just set myself free. There’s a copy of all this code saved somewhere.
For now, I think we’ll just continue to add things to this one program, keeping things like Waypoints even though we are working to get rid of them. There’s still good meat on those bones.
I began merging some good code from Codea Lua with the code on my Mac, which is from SLua, and I diverted into doing that merge correctly. I’ve added some features and tests for Bezier, including the code to split a Bezier in half, tested thus:
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)
end
end
The test got a bit gnarly because my nearly-equal method doesn’t handle table / vector comparisons, so I had to break out the values. With that done, the two split beziers compute the same values as one would expect. I was sure that was correct, because on the iPad I can see the result but a test is better.
I also had two different at methods and picked the simpler. So far both are in there with one commented out and the test comparing them commented out as well. I need to get this stuff into Git somehow.
I added the estimate_length function, which is nearly as accurate as actually computing the length the hard way. I think we will not use either one but they are good to know about so I’ll leave them in for now,
I think the thinking above was good and I’ll save it as a historical document, but it has not yet resulted in any more useful code. I did get some good tests and possibly useful imported functions. Now I need a rest before the afternoon SL session.
Safe paths!
List to be placed here soon. ↩