# Anyone can bash two lines together...

This topic is 4939 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## 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 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 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 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 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 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 on other sites
Quote:
 Original post by WyrframeI 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 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 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 on other sites
Diagram from above post:
A---------------B-----------------				  \C     Y       ____________________/   /  \     /  /    \   /X        Z

1. 1
2. 2
JoeJ
20
3. 3
frob
18
4. 4
5. 5

• 10
• 10
• 12
• 13
• 9
• ### Forum Statistics

• Total Topics
632200
• Total Posts
3004741

×