Jump to content
  • Advertisement
Sign in to follow this  
Frongo

Find point on quadratic bezier at given distance

This topic is 2597 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

Hey guys,

My problem is somewhat unique and I'm not really sure how to solve it in a non-iterative fashion:

1 - Given a starting point, ending point, and one control point for a bezier curve in 2D space, I need to find a point on the curve that is exactly at a given distance from the starting point of the curve.
2 - If there are multiple candidates (I believe there can be 2 at the most), I need to figure out which one comes first when walking through the path.

[attachment=5914:bezier distance.jpg]

Share this post


Link to post
Share on other sites
Advertisement
Let the Bezier control points be [font="CourierNew, monospace"](x0, y0), (x1, y1), (x2, y2). W[/font][font="CourierNew, monospace"]e wish to find the intersection of points that are a distance r[/font][font="CourierNew, monospace"] from (x0, y0).[/font][font="CourierNew, monospace"] In other words, the intersection of the circle (x - x0)^2 + (y - y0)^2 = r^2 [/font][font="CourierNew, monospace"]with the curve ((1 - t)^2 * x0 + 2(1 - t)t * x1 + t^2 * x2, [/font][font="CourierNew, monospace"](1 - t)^2 * y0 + 2(1 - t)t * y1 + t^2 * y2), 0 <= t <= 1.[/font][font="CourierNew, monospace"]
[/font]
[font="CourierNew, monospace"]Substituting this in,[/font][font="CourierNew, monospace"]
[/font]
[font="CourierNew, monospace"]([/font][font="CourierNew, monospace"](1 - t)^2 * x0 + 2(1 - t)t * x1 + t^2 * x2 - x0)^2 + ([/font][font="CourierNew, monospace"](1 - t)^2 * y0 + 2(1 - t)t * y1 + t^2 * y2 - y0)^2 = r^2[/font]
[font="CourierNew, monospace"]
[/font]
[font="CourierNew, monospace"]Solving for t will give you a quartic, (The 0 <= t <= 1 constraint actually means there are at most three valid solutions I believe, although I'm not sure if there is an easier way to solve such a special case) -- you can solve the quartic exactly although this is probably not a great idea.[/font] Much easier would be to apply newtons method etc.

Share this post


Link to post
Share on other sites
Ahh, I was hoping to avoid that quartic but I guess this is the only way to do it. Unfortunately that would be too expensive to implement in our particular project so I've come up with another (less math intensive) solution for the greater problem.

I now know where to come for my math questions/problems.

Thanks

Share this post


Link to post
Share on other sites
You could do a brute force method. Bezier subdivision is faster than using quartic equations and fairly easy to code. You would have to test the distance for each new point, but the Manhattan distance should get you a close enough candidate to do further testing.

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!