Archived

This topic is now archived and is closed to further replies.

Dodzilla

Computing control points for bezier curves

Recommended Posts

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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Catmull-Rom splines are just a restricted form of piecewise cubic Bezier curves. It''s basically the same method that he was originally considering.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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? "


Ionware Productions - Games and Game Tools Development

Share this post


Link to post
Share on other sites
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?

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Here are two suggestions.

1) Try natural cubic splines. They approximate the minimum energy curve passing through the control points, and thus could be described as the "optimal" path one would take to move through the points. No need to write code for it just yet, though. Play around with this java applet. Put a few points down, and see if the natural cubic spline passing through the points looks reasonable to you. Make sure to change the curve type from "Polynomial" to "Cubic Spline".

2) If a person were walking along and had to go through a certain set of points, he''d probably just travel in something very, very close to a straight line from point to point. The only difference is that he likely wouldn''t instantaneously change direction, as happens with linear interpolation through a set of points. Rather, he''d arc very slightly as he approached each point.

If I remember correctly, a Catmull-Rom spline is a unique curve, i.e. other than specifying the control points, you can''t modify it. So Catmull-Rom splines probably won''t get the job done here. I suggest looking into Kochanek-Bartels curves (sometimes called TCB splines). With these curves, there are four ways to control the curve: you specify the control points (which will be your path waypoints), and also specify the tension, continuity, and bias (hence TCB spline) at each point. Keep the default parameters for bias and continuity, but make the tension at each point very high. This will result in a tightening of the curve at each control point. The end result should be that the curve closely resembles linear interpolation, except that it has slightly smoothed edges at each control point, which I think is exactly what you want.

Kochanek-Bartels curves are essentially a generalization of Catmull-Rom splines, and are a weaker form of a Hermite curve (Catmull-Rom < Kochanek-Bartels < Hermite = Piecewise Cubic Bezier). This page has a useful document on Kochanek-Bartels curves (in the "Curves and Mesh Representations" section), and source code can be found at that site as well.

Good luck.

Share this post


Link to post
Share on other sites
@sthomas

How can you say that splines give better curves than bezier? They are just two different types of curves with different properties, neither is better than the other.

Personally i''ve used peicewise cubic bezier curves and that works fine for my needs. In this case i would assume it would also be adequate, note that for all of these curves you will not be able to analytically calculate the length of the curves, i.e. you won''t be able to get a constant velocity if you use it directly for movement.

Here are some links for you:

http://astronomy.swin.edu.au/~pbourke/curves/bezier/
http://astronomy.swin.edu.au/~pbourke/curves/bezier/cubicbezier.html
http://astronomy.swin.edu.au/~pbourke/curves/spline/

Share this post


Link to post
Share on other sites
You might also try looking at steering behaviors, which might give you a more natural look. See Craig Reynolds'' page for a description and Java applet example.

Share this post


Link to post
Share on other sites
quote:
Original post by SpaceDude
@sthomas

How can you say that splines give better curves than bezier? They are just two different types of curves with different properties, neither is better than the other.



Well it really depends on the application of course. In general though, I think natural cubic splines tend to result in nicer curves than piecewise cubic Bezier curves, for two reasons:

1) Natural cubic splines approximate the minimum energy curve passing through the control points. Minimum energy = minimum curvature = good.

2) Natural cubic splines have C2 continuity at each control point, whereas piecewise cubic Bezier curves only have C1 continuity at each joint.

They''re not going to solve the original poster''s problem, though. He probably needs an AI-specific solution or something.

Share this post


Link to post
Share on other sites
Personally I would make a straight line between nodes and then just round the corners. I would do that with simply bevelling it, but you could use a bezier or spline. Just to give a mental image imagine you plot all the nodes and draw a cricle around each. Then you draw a line from circle to circle rather than node to node. You can stick beziers in their connecting the line segments, but I would just use a circle, i.e. bevel the corners.

Share this post


Link to post
Share on other sites
Thanks for all the suggestions guys, I''m gonna check out the steering behavior stuff, it looks very interesting. From what I saw in that little Java Applet it looks like the steering might provide the results I''m looking for... strange coincidence that gamedev.net was just running the poll about the OpenSteer library, I''ll have to download it.

Share this post


Link to post
Share on other sites
quote:
Original post by sthomas
1) Natural cubic splines approximate the minimum energy curve passing through the control points. Minimum energy = minimum curvature = good.



Curves don''t have energy, so what do you mean by minimum energy curve?

Share this post


Link to post
Share on other sites
I believe the idea of a spline having energy comes from the origins of splines which is a straight flexible strip of metal forced through the "nodes". The least amount of energy required to force it through all those nodes is to apply no force other than at the nodes.

Share this post


Link to post
Share on other sites
quote:
Original post by SpaceDude
quote:
Original post by sthomas
1) Natural cubic splines approximate the minimum energy curve passing through the control points. Minimum energy = minimum curvature = good.



Curves don''t have energy, so what do you mean by minimum energy curve?


Here, by "energy", I''m referring to what''s sometimes called the "bending energy" of the curve. It''s defined as the integral of k^2*ds over the curve, where k = curvature and ds = arc length. The lower the bending energy, the less work you have to do to move a particle along the path. Natural cubic splines approximately minimize this bending energy, under the constraint that all the control points are interpolated. Any numerical analysis text should describe this in much greater detail.

Share this post


Link to post
Share on other sites