Structure for Bezier curves

Posted Tuesday, 4 March, 2008 - 19:36 by georgwaechter in

Hello,

in my private math library i have structures for calculating bezier curves. I think this could be useful for OpenTK too, or? Within my personal projekt i use these structures to calculate and draw bezier curves with OpenGL.

I have one structure for quadric bezier curves, one structure for cubic bezier curves and one struct for bezier curves with any count of anchor points.

georg

‹ OpenTK.Input.Key Numeric Keypad Enter? Fullscreen bug ›

Comments

Mar 04
 19:56:39
Re: Structure for Bezier curves
posted by Inertia

This would be interesting for sure, but does it use the OpenTK.Math structs? What do the command parameters and return look like?

Mar 04
 20:20:55
Re: Structure for Bezier curves
posted by the Fiddler

OpenTK.Math consists almost entirely of use contributions, and enhancements are always welcome. This would be an especially welcome addition, as this part of GLU doesn't fit well the managed world.

Can you post a few usage examples?

Mar 04
 21:31:03
Re: Structure for Bezier curves
posted by georgwaechter

at the moment it does not use the OpenTK.Math structs, but of course i'll change this.

usage for example:

BezierCurveCubic bezier = new BezierCurveCubic();

// setup anchor points and control points
bezier.StartAnchor = new Vector2D(0.0f, 0.0f);
bezier.EndAnchor = new Vector2D(10.0f, 10.0f);
bezier.FirstControlPoint = new Vector2D(3.0f, 8.0f);
bezier.SecondControlPoint = new Vector2D(7.0f, 2.0f);

Vector2D oldPoint = bezier.StartAnchor;
Vector2D point = new Vector2D();

// calculate 100 points on the curve
for (float t = 0.0f; t <= 1.0f; t += 0.01f)
{
        point = bezier.CalculatePoint(t);

        // draw with opengl a line from oldPoint to point
        oldPoint = point;
}

// calculate length of curve with a precision of 0.01f (100 steps)
float length = bezier.CalculateLength(0.01f);

The structure BezierCurveQuadric has only one control point and the generic structure BezierCurve has a list of all points (where the first and the last point are the anchor points).

Additionally my structures have a field Parallel which enables you to calculate the prallel curve of a bezier curve. Example:

BezierCurveCubic bezier2 = bezier; // bezier from above

bezier2.Parallel = 5.0f;
bezier.Parallel = -5.0f;

// drawing both curves results in a smooth track

Greetings

Georg

Mar 04
 22:42:35
Re: Structure for Bezier curves
posted by Inertia

Interesting API, I was kinda expecting something like
static Vec3[] GetBezierCubicPath(Vec3 Start, Vec3 Control1, Vec3 Control2, Vec3 End, uint steps);
Your approach is way more flexible though, and it should be trivial to port it to use OpenTK.Math's Vector3 struct :)

Mar 05
 16:19:33
Re: Structure for Bezier curves
posted by georgwaechter

Ok, so i'll start working on a Patch that adds theses threes structures to the repository. Is the code already going into the next release or will it be integrated later?

Ah and by the way i add one or two functions to the OpenTK.Math.Functions class for calculating binomial coefficents (that is needed for the bezier calculations).

I saw that in the trunk there are now double versions of structures like Vector3. So i'm wondering ...
1) will Vector3 keep its name or will it be renamed to Vector3f (would be very reasonable)
2) is thare already code inside OpenTK that uses OpenTK.Math structures actively? Or is it more or less a 'give-away' to the users of OpenTK so that they get a math library for free?

I think the best would be to have one generic structure Vector3<float>, that would allow us to reduce code size. Additionally it would be cool to define an alias Vector3f for Vector3<float>, but sadly that does not work with C#.

And if we don't use generic version ... should the bezier structures go with floats or doubles (at the moment i use floats)?

georg

Mar 05
 16:35:00
Re: Structure for Bezier curves
posted by the Fiddler

1) They'll stay Vector3. No need to add clutter to the default codepath (if you need double versions you'll have to call them explicitly).
2) Two parts rely on OpenTK.Math: OpenGL/OpenAL (overloads) and OpenTK.Fonts. 0.9.1 and later versions will ship with an OpenTK.Utilities.dll (shorthand: TKU), and some utilities will be moved there (OpenTK.Fonts, for example). Since Bezier curves rely on the core OpenTK.dll and not vice versa, they belong to TKU.

There is an advantage in being in TKU: there's more time to add features. If you get the patch ready by next week, beziers will be in 0.9.1 - I'd be more reluctant to add functionality to the core late in the release cycle. :)

Regarding generics, this was decided against in the past. The base OpenTK.Math structures (vectors, matrices, quaternions) should be as lightweight as possible. Generics would reduce the neccessary code at the expense of execution speed (relevant discussion) - and since the bulk of the code is already written, there's little point to rewrite everything at this point :)

It's probably best to target the float version first, as that's the most useful one. We can always add the double version in the future when/if it becomes necessary. Also, TKU classes do not need to be lightweight (how many bezier curves are you going to pass around per frame?) Generics are allowed there - the only limitation is to avoid generating garbage, if at all possible.

Mar 05
 17:22:32
Re: Structure for Bezier curves
posted by georgwaechter

Ok ... i will keep the bezier structs non-generic and let them use floats.

"how many bezier curves are you going to pass around per frame?"

not so many .. sometimes zero and sometimes 20, but anyway i put the geometry - when possible - into a precomputed vertex array or a vertex buffer object.

georg

Mar 05
 21:44:32
Re: Structure for Bezier curves
posted by georgwaechter

So ... the patch is ready ... i used the current source code out of the subversion repository to create the patch.

Changes:

* Added BezierCurve structure for bezier curves with as many points as you want
* Added BezierCurveQuadric structure with two anchor points and one control point
* Added BezierCurveCubic structure with two anchor points and two control points
* Added two functions to Functions.cs for calculating the factorial of a number and for calculating the binomial coefficient
* Added the property 'Perpendicular' to Vector2 and Vector2d for creating a vector that is perpendicular to the current one (the cross product in two dimensions)

Additionally I added a license header to my files and added my name.

Here is the patch: http://trackplanner.de/files/BezierPatch.patch

feel free to 'criticize' my code :-)

georg

Mar 05
 22:36:00
Re: Structure for Bezier curves
posted by the Fiddler

Good work! I skimmed through the code and it looks solid enough, will test more thoroughly tomorrow.

You asked for suggestions: ;)

  1. Replace the public BezierCurve(List<Vector2> points) constructor with public BezierCurve(IEnumerable<Vector2> points). The more general the interface, the better: IEnumerable or IList allow the user to pass a Vector2[], while List doesn't.
  2. Store the points into a Vector2[] instead of List<Vector2>. Since you don't actually Add or Remove elements, there is no need to create a new generic list.
  3. Foreach loops can be more efficient than for-loops, by skipping bound checking. You can also concatenate the two loops in e.g. private Vector2 CalculatePointOfDerivative(float t) for a nice speed gain (hope I parsed the code correctly! :) )
    foreach (Vector2 v in Points)
    {
        r.X += ...
        r.Y += ...
    }
  4. Check for null references in the constructors:
    if (points == null)
        throw new ArgumentNullException("points", "Must point to a valid list of Vector2 structures.");

Small changes, but they'll help make the code more robust and efficient. :)

Mar 06
 14:21:14
Re: Structure for Bezier curves
posted by georgwaechter

Thanks.

1) yes, that makes sense
2) the property 'Points' is public, so you can access/add/remove points from outside. In my project i need this functionality, because i must manipulate curves during runtime. And the performance difference between lists and arrays is imo not so large, especcialy when using enumerators (foreach).
3) Yes you're completely right. I don't not whether i merged the two loops not myself.
4) Ok.

i'll make the changes at home

Mar 06
 16:21:00
Re: Structure for Bezier curves
posted by the Fiddler

Nice, thanks :)

2) Makes sense. I'd suggest a pattern like this, though:

private List<Vector2> points = new List<Vector2>();

/// <summary>Gets the points of this curve.</summary>
/// <remarks>The first point and the last points represent the anchor points.</remarks>
public IList<Vector2> Points
{
    get { return (IList<Vector2>)points; }
}

The main reason is that this helps keep the internal state consistent. If the user was able to say curve.Points = null, you'd have to guard against null references every time you used the property.

This still allows you to add and remove points:

Vector2 point = new Vector2();
BezierCurve curve = new BezierCurve();
curve.Points.Add(point);    // works
curve.Points.Clear();
curve.Points = null;        // error

What do you think?

Mar 06
 17:39:09
Re: Structure for Bezier curves
posted by georgwaechter

In reality i anyway should check for null in all functions, because a line like
private List<Vector2> points = new List<Vector2>();
is not allowed within structures. An alternative would be to switch to a class ...

1) using IEnumerable now implies, that we have to copy the specified list always ... but thats no real problem

Mar 06
 17:54:00
Re: Structure for Bezier curves
posted by the Fiddler

No need, just make sure points are always initialized in the constructor.

1) True. I think it's good design to always copy though, because it avoids nasty surprises:

List<Vector2> points = new List<Vector2>();
points.Add(new Vector2());
points.Add(new Vector2());

BezierCurve curve = new BezierCurve(points);
points.Clear();
Console.WriteLine(curve.Points.Length.ToString());
// If the constructor does not copy, curve.Points.Length is now 0.
// An outside change has influenced the internals of BezierCurve,
// which is dangerous. No such problems if the constructor always copies.

Mar 06
 20:20:34
Re: Structure for Bezier curves
posted by georgwaechter

Ok i made all changes. But there is yet the theoretical chance of null-reference-exceptions, because anybody could call the default ctor of the struct, that initializes all fields to 0 or null.

BezierCurve b = new BezierCurve();
b.Points.Add(new Vector2()); // exception

For that reason i added a setter for the property Points:

set { if (value != null) points = value; }

Additionally i made a few performance optimizations within the loops to reduce redundant calculations.

Here is the patch: http://trackplanner.de/files/BezierPatch.patch

Mar 06
 20:35:36
Re: Structure for Bezier curves
posted by the Fiddler

Thanks, I've applied it to my working copy and it looks good, I'll play with it a bit and commit it.