Computing control points for bezier curves
Author
Hello,
I did a search on this but didn''t find much... I''ve got A* pathfinding working and it appears bezier curves are a good bet for smoothing out the paths to they look nicer. The problem is I''m not sure how the control points should be generated... A* only gives me the "waypoints" (or endpoints) for the path. Can anyone shed some light on this?
Scott
If you really want some nice, smooth curves, interpolate your points using natural cubic splines. They''re more complex and take longer to construct, but yield nicer curves.
If the speed problem is an issue (i.e. you need to be constantly reconstructing the curve on the fly, and there are tons of waypoints), there''s an algorithm to generate a piecewise cubic Bezier curve with C2 continuity at the joints. That''s basically the answer to your question of how to choose the best control points. I can probably find a link somewhere that has the algorithm if you want it. Hmm... now that I think of it though, that algorithm may have been just as expensive as the algorithm to construct the natural cubic spline going through the waypoints.
Googling for either of these curve types will get you tons of info.
If the speed problem is an issue (i.e. you need to be constantly reconstructing the curve on the fly, and there are tons of waypoints), there''s an algorithm to generate a piecewise cubic Bezier curve with C2 continuity at the joints. That''s basically the answer to your question of how to choose the best control points. I can probably find a link somewhere that has the algorithm if you want it. Hmm... now that I think of it though, that algorithm may have been just as expensive as the algorithm to construct the natural cubic spline going through the waypoints.
Googling for either of these curve types will get you tons of info.
Author
Fantastic, thanks a lot for the suggestion. Natural cubic splines appear to be exactly what I''m looking for...
Another approach is to use Catmull-Rom splines. The problem there is that you don''t have enough information to compute cubic subcurves at each end, but you can approximate them with quadratics and still get a smooth result.
Catmull-Rom splines are just a restricted form of piecewise cubic Bezier curves. It''s basically the same method that he was originally considering.
I only mentioned Catmull-Rom because you don''t need to do a matrix inversion every time you change your points, so it should be cheaper. You plug them into the same formula and away you go. However, the curve shape you get won''t be C2 continuous, so the result won''t be as "smooth". So it''s not quite the same method as the second one you mentioned.
As been mentioned, you are better stick to lower-degree curve, because if you have 5+ points for your path, the curve will ''generalize'' itself - the nature of Bezier curve.
If you''re interested, I''ve implemented an algorithm that can give you a Bezier curve of any degree (any number of points). You can find it on my page (link below).
Good luck.
" Do we need us? "
If you''re interested, I''ve implemented an algorithm that can give you a Bezier curve of any degree (any number of points). You can find it on my page (link below).
Good luck.
" Do we need us? "
Author
Since the D3DX library has built-in support for Catmull-Rom splines I played around with them a little bit... the problem seems to be not only deciding on the right type of spline to use, but also modifying my path data before I create the spline. Just creating a spline out of the data I get from my A* algorithm isn''t producing very good results... I''m going to try changing the distance between the endpoints and also modify my path to remove any right angles (in an attempt to smooth it out a little). Anybody have any other suggestions for making the path seem more life-like?
The curves come out looking pretty crappy, huh? You might want to go ahead and try natural cubic splines. You should be able to find code to construct a natural cubic spline somewhere (it''s more complicated than a Catmull-Rom spline). It generates a different kind of curve that has a higher order of continuity, and thus may look more natual. Then again, it might not fix anything. Maybe if you post screenshots of what the generated Catmull-Rom spline looks like, we could better determine the nature of the problem.
Author
It''s not realy that the curves come out looking crappy, the result just isn''t quite what I intended at this point. I''m using A* to plot a path for my character through my world. The character will then walk along the path to get to the destination. The problem is that the data I''m creating the curves with (the coordinates from A*) aren''t producing curves that look like the path a person would walk to get from A to B. I was wondering if anybody knew any tips/tricks for generating a path/spline that looks more realistic.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
