Finding points on a bezier curve based on distance from another point

So I have a开发者_开发百科 3D cubic bezier curve and a start point found anywhere along the curve and need to find a second point further down the curve that is a specific worldspace distance (not arclength distance) away from the first point.

Another issue would be if the second point reached the end of the curve and still wasn't at the desired worldspace distance, in which case I would want it to continue along the tangent until the distance was reached.

Any ideas?

Alas, I don't know any closed-form equation giving you the point(s) you want. Perhaps the simplest technique to approximate that point is to recursively chop the Bezier curve up into 2 smaller Bezier curves using de Casteljau's algorithm. The recursion bottoms out when either (a) all the bounding points for the curve are all either too close or too far from the given point, or (b) all the bounding points for the curve are "close enough" to being equal to the desired distance (perhaps they all fit inside the same pixel).

I'm pretty sure the maximum number of points on a given Bezier curve that are a given linear distance from some given point is 4 points. (This can happen when the given Bezier curve has a self-intersection).

EDIT:

Perhaps I should read the entire question before jumping in with a response, yes? The standard "four-points" Bezier curve segment can be seen as one piece of an infinitely long cubic curve. There may be a bend or loop or cusp at one location, but sufficiently far away from that sharp curve the path flattens out to close to 2 straight rays, each of which points in some arbitrary direction. Alas, the above solution only finds points that are on the short Bezier curve segment. I'm assuming you want the point(s) along that infinitely long cubic curve that are the given distance away from the given point, even if they are not on the short Bezier curve segment.

== de Casteljau in reverse ==

You could run (recursive midpoint) de Casteljau's algorithm in reverse, generating a new four-point Bezier curve "double" the size of the last at every iteration, until you got one big enough to include the desired point(s). (When all 4 initial points are "too close" to the given point, then doubling is guaranteed to eventually produce a curve segment with the start point "too close", the end point "too far", and then you can use the above algorithm to converge on a point that is the desired distance away from the given point). This approach relies only on addition, subtraction, multiplication by two, and averaging, so in principle it should be relatively numerically robust. (It never actually evaluates the cubic formula at any location t).

== zero-finding ==

You could convert from the four-point representation to the cubic polynomial representation, and use any root-finding algorithm to converge on one of the desired points. Newton's method should work pretty good, since short pieces of a Bezier curve are nearly straight. Could we adapt the Newton's method equations from Finding the Minimum Distance Between a Point and a Cubic Spline to this problem? I'll use the bisection algorithm for simplicity in description, even though that runs slower than Newton's method.

As always, a cubic Bezier curve segment can be described as

B(t) = (1-t)^3 * P0 + 3*(1-t)^2*t*P1 + 3*(1-t)*t^2*P2 + t^3*P3.

(Unfortunately, this equation is not always numerically robust -- that's why many people use recursive halving using de Casteljau's algorithm instead).

I'm assuming you have (or can find) the t_given value for your given point,

x_given = B(t_given).x
y_given = B(t_given).y

The distance between your given point and some other point along the curve is given by Pythagorean theorem,

distance2(t) = ( x_given - B(t).x )^2 + ( y_given - B(t).y )^2.
distance(t) = sqrt(distance2(t)).

The point(s) you are looking for are at the zeros of the function

given_distance2 = given_distance^2.
f(t) = distance2(t) - given_distance2.

Assuming that the given distance is not zero, and the given point has a t_given < 1, the bisection algorithm would run something like

left = t_given
right = 1 // the endpoint of the given Bezier curve segment
while( distance2(right) < given_distance2 ){
    right = right*2
}

At this point, the t_left is closer to the given point than the desired distance, and t_right is further away than the desired distance (or perhaps exactly equal). Since we have one point too close, and another point too far, the bisection algorithm should work.

while( (abs(f(right) is too big) AND (abs(left - right) is too big) ){
    // find midpoint
    midpoint = (t_left + t_right)/2

Next we check: does the first segment left...midpoint contain the zero, or midpoint...right ?

    if( f(left)*f(midpoint) < 0 ) then
        // throw away right half
        right = midpoint
    else
        // throw away left half
        left = midpoint
}

return( right )

At this point, the "right" value is the value of t, and B(right) is the corresponding point, such that the distance from that point to the original given point is (approximately) the given distance.

Your problem statement needs a touch more refinement. Specifically you are under-constrained when asking for some point B that is N units away from starting point A. There could be multiple points that are N distance from A.

That aside what is stopping you from sampling your curve at set intervals along the curve and then calculating a linear distance back to A. It isn't optimal but it would work. To handle multiple points N distance away you'll have to come up with a rule. Might be as simple as first point found.