Sign in to follow this  
FFMG

Remain on track between points

Recommended Posts

Hi, I have a number of points on a path that I want my vehicles to follow, (to an end point). But the vehicles do not always start/apear at the beginning of the path, (or even anywhere near the path), they can join at any point. Image Hosted by MyPict.eu In the example above, the vehicle X, Y and Z need to fly toward B, C and D respectively to 'rejoin' the path. At first I thought it was a matter of distance, (rejoin the nearest point), but as in the case of 'Y' or 'Z' this would not work. What would be the easiest way of knowing what the 'next' point should be for the vehicle to aim in order to rejoin the path? Thanks FFMG

Share this post


Link to post
Share on other sites
Here is a relatively straightward way to determine the 'next' waypoint on the path given the vehicle's current position:

- Find the closest point on the path to the vehicle position
- Determine which path segment this closest point lies on
- The next waypoint is the second endpoint of this segment

The easiest way to find the closest point on the path would be to find the closest point on each path segment, and then choose the closest of these (this process will also tell you to which segment the next waypoint belongs).

Let me know if you need further info.

Share this post


Link to post
Share on other sites
You could also calculate the direction to the closest point on the path and take the dot product with the direction the next point on the path (the one after the closest). If the dot product is positive, go to the closest point, if it is negative (or 0) go to the next point.

In your example:

XA dot XB would be negative -> go to B
YB dot YC would be 0 (more or less) -> go to C
ZC dot ZD would be positive -> go to C

Share this post


Link to post
Share on other sites
Quote:
Original post by jyk
Here is a relatively straightward way to determine the 'next' waypoint on the path given the vehicle's current position:

- Find the closest point on the path to the vehicle position
- Determine which path segment this closest point lies on
- The next waypoint is the second endpoint of this segment

The easiest way to find the closest point on the path would be to find the closest point on each path segment, and then choose the closest of these (this process will also tell you to which segment the next waypoint belongs).

Let me know if you need further info.


Thanks, I just want to make sure I understand.
In the case of 'X', (in my example).

It looks like X is closer to A.
A is part of the A->B segment
So the vehicle must travel toward 'B'

This seems to make sense.

What would be the best way 'calculate/compute' what segment a point lies on?

Because, in the case 'Z', the nearest point is 'C'. But how do I know that the segment is B->C and not C->D and that I should be travelling toward 'D'?

FFMG

Share this post


Link to post
Share on other sites
Quote:
Original post by Lord_Evil
You could also calculate the direction to the closest point on the path and take the dot product with the direction the next point on the path (the one after the closest). If the dot product is positive, go to the closest point, if it is negative (or 0) go to the next point.

In your example:

XA dot XB would be negative -> go to B
YB dot YC would be 0 (more or less) -> go to C
ZC dot ZD would be positive -> go to C


Thanks for that, unfortunately I am not that familiar with the dot notation.

How would I do a dot product?

FFMG

Share this post


Link to post
Share on other sites
Find the minimum distance between the point and line. The math is easy and there are lots of explanations (eg: this one, just make sure to follow the second note). Do this for every line segment in your path, as jyk described, and the one with the smallest distance is the segment you are closest to. Then just proceed towards the end point of the line. You only need to know which line, not which vertex, the point is closest to.

Edit: Maybe you should Google dot product - I know there's plenty of information out there for it.

Share this post


Link to post
Share on other sites
Quote:
Original post by Ezbez
Find the minimum distance between the point and line. The math is easy and there are lots of explanations (eg: this one, just make sure to follow the second note). Do this for every line segment in your path, as jyk described, and the one with the smallest distance is the segment you are closest to. Then just proceed towards the end point of the line. You only need to know which line, not which vertex, the point is closest to.


Thanks for the info, I'll try and come up with a function to get me the next point to head to.

I mis-understood, I thought I had to find the nearest distance to a point, not to a line, it makes more sense now.

Quote:
Original post by Ezbez
Edit: Maybe you should Google dot product - I know there's plenty of information out there for it.


Ok, ok, maybe I asked for that.

FFMG

Share this post


Link to post
Share on other sites
nearest point on a segment, to a point, plus the distanced squared.

Quote:


float pointSegmentDistance(const Vector& point, const Vector& start, const Vector& end, Vector& closestPointOnSegment)
{
Vector edge = (end - start);
Vector delta = (point - start);

float edge_length_squared = edge.dotProduct(edge);
float edge_project = delta.dotProduct(edge);

float t = edge_project / edge_length_squared;
if(t < 0.0f) t = 0.0f;
else if(t > 1.0f) t = 1.0f;

closestPointOnSegment = start + edge * t;

Vector distance = (closestPointOnSegment - point);

float distance_squared = distance.dotProduct(distance);

return distance_squared;
}



so in the end, you just pick the edge with the smallest distance, and the closest point on edge could be, for example, the point to aim at to rejoin the track.

Share this post


Link to post
Share on other sites
It's somewhat late here, so sorry if this is incohesive. I think a bezier curve might work well with this problem! Wiki Article with a good explanation

If you work with them for a bit, bezier curves really are not too hard to implement. Judging by your picture, a 3rd or 4th order curve would be the way to go!

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