Jump to content
  • Advertisement
Sign in to follow this  
johdex

closest point to Hermite curve

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

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi, I'm making a racing game, and am currently working on the track format. I was thinking on using Hermite curves to model the track. I am also planning to implement AI, which would certainly require to know the position of a vehicle on the track, in terms of distance from the starting line and distance from the center of the track. My question is, given a point P and a Hermite curve H, how to compute the point closest to P on H? I have an idea, but I am not sure it works in all cases: Compute tangent at H(0), rotate 90 deg (let's call that H'(0)), check if P is "above". If yes, compute H'(0.5), check again. If yes, compute H'(0.75) otherwise H'(0.25)... until it's "close enough". What do you think?

Share this post


Link to post
Share on other sites
Advertisement
The mathematical solution for computing the distance between a point P and a (differentiable) parametric curve X(t), for t0 <= t <= t1, is the following. The squared distance between P and the point X(t) is the function F(t) = Dot(X(t)-P,X(t)-P). You want to compute the value of t that minimizes F(t) on the interval [t0,t1]. From calculus, the minimum occurs when the derivative F'(t) is zero or at one of the end points of the interval. The derivative is F'(t) = 2*Dot(X(t)-P,X'(t)). Computing t values for F'(t) = 0 is a root-finding problem.

For polynomial curves, F'(t) = 0 is a polynomial equation. If the degree of the curve is n, that is the components of X(t) are polynomials in t of degree n, then X'(t) has degree n-1. This leads to F'(t) being a polynomial of degree 2*n-1. If n = 2, F'(t) has degree 3 and there are closed-form solutions for the roots, although numerical evaluation of these is notoriously nonrobust. For n = 3, F'(t) has degree 5, and there are no closed-form solutions--a mathematical fact, and not an issue of no one has discovered them yet. In this case you have to resort to numerical methods to find the roots.

Numerical methods usually need a "root bounding" stage. This determines subintervals of [t0,t1] on which roots occur. For closest points on curves, this amounts to approximating the curve with a polyline, finding the segment that is closest to P, and then refining the search for the portion of the curve bounded by the segment end points.

At any rate, you might want to consider a different plan for monitoring the position of cars on the track. What you have in mind can be expensive computationally.

Share this post


Link to post
Share on other sites
I would be tempted to use a very simple method guaranteed to work. Your tangent idea sounds like it may work, although I am not certain it would work, or whether a simpler method would be just as good.

A very simple solution is to work out the position of the curve at small intervals and work out the distance from these positions to the point.


for i = 0 to 1 step interval
{
dist = distanceBetween ( H(i), point )
if (dist < min_dist)
store new min_dist and min_position
}

//now you have the minimum distance and position




You can trade accuracy for speed by decreasing the intervals, and also make the search process slightly faster by using dynamic intervals.

Not as accurate, fast, or nice as an exact mathematical solution, but I am certain it will be accurate enough and fast enough for what you want it for. And at the end of the day I have decided it is usually better to be able to get on with the next problem than spend ages on the current one.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!