Sign in to follow this  
Wyrframe

Anyone can bash two lines together...

Recommended Posts

... I'm trying to bash-together two bezier curves. What I've got is a list of, essentially, travel plans. Plural vehicles travelling at varying velocities are going to be travelling through a physical system. They announce their intended paths as a (now-time, future-time, list-of-bezier-curves) tuple, with the now-time being what time they are issuing the intent at, the future-time being when they expect to be at the end of the list of curves, and then the list of curves they plan to travel. I've got a decent solution (which took Maple 4 minutes to grind out) for determining intersection-or-not of two 3-vertex 2nd-order bezier curves, and I've got an algorithm for breaking curves into subcurves if need be. My question asks about something a little more complex... My current solution only offers saying "these two vehicles might collide at this segment of their plans", and only assuming the two vehicles maintain constant speed over the course of their entire announced plan. I want to allow vehicles to issue a series of 3-vertex bezier curves representing velocity over time, which will match pairwise to the 3-vertex curves representing position over time, which will help me get much more reliable collide-or-not tests, but I'm not sure how to incorporate this into my existing mathematics. Any suggestions? More critically, my current solution seems to offer where the distance between the two curves actually reaches zero, but I'd prefer that vehicles can account for a safety margin of greater than a femtometer from their center of mass. Having already taken the absolute value of the solution, I'm pretty sure I can just add ±(r1+r2) tests onto the existing cases, right?

Share this post


Link to post
Share on other sites
Off the top of my head it seems that you might run into trouble using two different splines for position and for velocity. Recall that velocity is the derivative of position versus time, so the spline for position already implies a velocity function that is probably different from the one that you want to impose on it. But it can be done, I suppose, if s(t) t in [0,1] is your position spline, and your velocity spline is v(t) with v[0] = (0,0) and v[1] = (1,1). Then you just evaluate s(v(t)) the composition to get motion with variable speed along s(t). And to find the minimum distance of two cars with their speeds s1 and s2, and their velocities v1 and v2, you can find the minimum of G(t) = d(s1(v1(t)),s2(v2(t))) where d is the distance function. You might do something like look for extrema by solving G'(t)=0, or however you like to do it.

C.

Share this post


Link to post
Share on other sites
Clarification; the path curves do not make any statement about time at the moment; they are functions purely over physical space, not temporal. All the paths describe is a probable locus of position. Provided with the paths is the projected end time, which implies a constant and uniform velocity over the path. At current, I can find the estimated location at any time inside the [now,projected-end] range assuming constant velocity.

What I want to do is add the velocity curve so that given a time in the [now,future] range, I can find projected position anywhere along the path after accounting for varying speeds.

For instance, imagine one car is travelling a straight line at low speed, and another is zigging back and forth in a sine wave around this line at steadily increasing (but not linearly) speed.

In the current system, only the average velocity of the second car can be considered, which might lead to no projected collisions, when in fact the second car will T-bone the first on its third oscillation. I'm trying to improve on this.

The objective, by the way, is to make a general-purpose tactical path-planning and resolution system for automated or assisting systems of various kinds, like automating cars in a closed system, or assisting air-traffic control.

Share this post


Link to post
Share on other sites
doesnt seem too hard...

find all spatial intersectionpoints of the paths. if as you claim you have them parametrized by arclength, you can use the standard equations of motion to solve for the time of arrival at this point ie x=1/2at*t+v*t

Share this post


Link to post
Share on other sites
Except they aren't parameterized by arclength... they are parameterized by percentage along arc. My arc-chopping algorithm can make the endpoints of two curves line up, so that they begin and end at the same moments of time, but that doesn't solve the variable-speed problem. Also, intersection isn't good enough; I need closest approach, mainly because vehicles are of non-zero size, but also because 3D space is also a possible environment.

I could add time as an extra dimension of locus into the path information, so that in a 2-space environment each vertex will be (X,Y,T), which seems to solve a couple problems, including resolving path and velocity into a single curve. Now I just need a better way to find closest approach, because analyzing a function for its minimum at run-time is right out of the question, unless it can be done algebraicly. Any suggestions or references?

Share this post


Link to post
Share on other sites
Further revelation; no, adding time as a dimension of the path does not solve any problems, and in fact adds on. When testing for closest-approach, it has to be at equal times. My cutting algorithm solves this. If I let time be a direction, I might start finding closest-approaches where the two paths do indeed come near to touching, but at thouroughly separate times. Not acceptable.

However, I think I can solve the variable-speed problem. I can still cut two arcs to be coincident in time-span; given a decent approximation of the length of the curves, I can just chop it up into acceptably small time-spans, and thus approximate varying velocity. This revelation came as a result of meditating on real-world vehicles' ability to accurately control velocity, only acceleration. Since acceleration over spans of 1/2-seconds is only a miniscule distance off from linear, this should be fine.

If I get any other show-stopping problems, I'll be back.

Share this post


Link to post
Share on other sites
Quote:
Original post by Wyrframe
I could add time as an extra dimension of locus into the path information, so that in a 2-space environment each vertex will be (X,Y,T), which seems to solve a couple problems, including resolving path and velocity into a single curve. Now I just need a better way to find closest approach, because analyzing a function for its minimum at run-time is right out of the question, unless it can be done algebraicly. Any suggestions or references?

hmmm. my gut feeling says me its actually the algebraic solutions that you can safely forget about for a problem of this complexity.

if you want to check two piecewise paths against eachother:

iterate trough them simulaniously, comparing pieces of the path that should be covered in an overlapping timeinterval. do an early rejection test between the boundingboxes of the splines enlarged by the radius of the object moving along it. otherwise, iteratively step along the splines varying time to see if an intersection can occur or not. any clever rootfinding scheme may be used here.

simple, and i dont think it will get much faster. not in terms of timecomplexity (linear with time you check ahead), and closed-form solutions will probably only be slower.

that said, i dont think youd want to be doing this on a per-frame-per-object basis. dont recalculate if you dont have to.

Share this post


Link to post
Share on other sites
You could also try using dichotomy and bounding rectangles: it's fairly easy to compute a bounding rectangle for a portion of the curve between t1 and t2. Check if two bounding rectangles are colliding (4 comparisons), then compute two new bounding rectangles for each curve (using a new point at (t1+t2)/2 for instance), and do the additional 2 checks recursively. Whenever two checks fail, there won't be collision. Whenever two small enough rectangles collide (you can define "small" yourself) there is a collision.

Share this post


Link to post
Share on other sites
why don't you store the time taken to move along each segment, then recurse through cumulating the time, and test if the segments with the same amount of cumulative time, intersect.
e.g
A---------------B-----------------
\C
Y ____________________/
/ \ /
/ \ /
X Z

P1 is ABC, and P2 is XYZC

calculate AB, BC, XY, YZ, ZC

if(XY <= AB <= YZ) and (node Y intersects AB) then exclude path.

its very crude, but the accuracy can be improved by splitting the curve up into smaller and smaller segments.

Share this post


Link to post
Share on other sites
"per-object-per-frame"... while this will initially be simulated, a major goal is for it to be realizable as a distributed system of individual vehicles, each resolving and announcing their own projected paths. Picture like real cars, except instead of only gleaning information from looking at another vehicle's position, direction and velocity, and the status of its turn signals, we can analyze its position, direction, velocity, and what it plans to do over the next 10 seconds.

On iteratively seeking out closest-approach, that is a nice idea, but not feasable over the kinds of scales we're talking about. If iteration steps are over time-span, I might get collisions in the gaps in-between. If iteration steps are over distance, I might get an obscenely high number of points to test. An arc might be half a second and a quarter-meter long, or it might be a half-hour and fourty thousand meters long, depending on the environment, the vehicles being evaluated, and the time-spans involved.

Share this post


Link to post
Share on other sites
Quote:
Original post by Wyrframe
"per-object-per-frame"... while this will initially be simulated, a major goal is for it to be realizable as a distributed system of individual vehicles, each resolving and announcing their own projected paths. Picture like real cars, except instead of only gleaning information from looking at another vehicle's position, direction and velocity, and the status of its turn signals, we can analyze its position, direction, velocity, and what it plans to do over the next 10 seconds.

ten seconds isnt too much, i thought you were talking about much more.

Quote:

On iteratively seeking out closest-approach, that is a nice idea, but not feasable over the kinds of scales we're talking about. If iteration steps are over time-span, I might get collisions in the gaps in-between. If iteration steps are over distance, I might get an obscenely high number of points to test. An arc might be half a second and a quarter-meter long, or it might be a half-hour and fourty thousand meters long, depending on the environment, the vehicles being evaluated, and the time-spans involved.

if your rootfinding algorithm sucks, yes.

iterating trough all pieces of the path x seconds away from the vehicle is something you need to do anyway, right? and its of no speed consequence at all, assuming the pieces of your path are not .0001 second in length, were taking about a handfull of spline vs spline checks.

efficient and robust numerical rootfinding between two low-degree splines isnt very easy, but its very doable.

Share this post


Link to post
Share on other sites
Ten seconds isn't much, but it is the low end of the planning distance for vehicles in a compact urban environment (ie cities). Open highways and near uncontrolled intersections will likely have a two-minute planning range. Airplanes would have ten- to fourty-minute planning ranges.

What kinds of techniques would I use to find the closest approaches? And any references or examples?

I made this topic because I couldn't find curve-curve closest-approach tests on google, just curve-curve intersection and curve-ray closest-approach.

Share this post


Link to post
Share on other sites
one way to do numerical rootfinding:

say your path is constructed out of quadratic pieces. the equation we need to solve is of the form |path1(distance(t)) - path2(distance(t))| = radius1 + radius2.

its not hard to see this equation can at most have 4 roots in case distance is a linear function of t. in case distance is quadratic with t (constant acceleration), path will evaluate to a 4th order, and the solution will have 8 roots at max. we are however talking here about HIGHLY hypothetical situations.

either way, evaluation the above formula at a couple of points, fit a polynomal trough them, and try and find its first root (a well documented subject). if you fit an 8th order polynomal, youre guaranteed to find all roots as long as your polynomal is a good approximation, but it most probably is. however, im quite sure fitting a quadratic and solving that with the ABC formula will work just fine unless you start pushing your algorithm into these unlikely scenarios.

well there are tons of methods to solve the above equation. another decent and simple method is to just sample the path at intervals < radius. its slow though for objects with small radius compared to their pathlength.

i think it would be wise to specify first how accurate it NEEDS to be precisely, and pick your method based on that, because one thing is for sure: youre not going to reach infinite precision without infinite processing power. everything is going to be an approximation, the question being: is it acceptable. i think the only way to find out is to try different methods. im certainly not able to give you a conclusive answer as to what is the best method.

one note btw: i dont think cars plan more than a few seconds ahead, and drivers certainly only take into account a very limited projection of other drivers.

anyway solving these equatios isnt going to be the hard part of this rather ambitious project youve undertaken. its going to be one massive headache, i can assure you that.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this