Interpolated Bezier Curves demo

[cragwolf]

Let's say your graphics library has the ability to draw cubic Bezier curves (specified with the usual 4 control points). But what you want to do is draw a smooth curve through any number of points. You can draw a Bezier curve between the first 2 points, another Bezier curve between the next 2 points, and so on, but the trick is in working out the values of the two interior control points between each 2 points so as to make each Bezier curve smoothly join with its neighbouring Bezier curves. It's a tricky mathematical problem (at least for someone as mathematically naive as myself).

I have written a small demo which allows you to specify a bunch of points on the screen, and as each point is added, a Bezier curve is drawn, the end result being a smooth curve through the points you have specified. I can see this being useful in games, maybe you want a smooth path for some purpose (like a racetrack). I know there are other (maybe easier) methods for creating smooth paths between points, but I wanted to utilise the Bezier drawing capability of my graphics library (OpenGL in this case). Here is a screenshot:

http://www.ludicity.org/images/bezierss.png

I wrote the program with Free Pascal (using JEDI-SDL headers), and you compile it with:

fpc -Mobjfpc bezier.pp

When you run the program, hit the F1 key to get help (there's a bunch of options). I have tested it under Linux, but it should work under Windows (I hope!) Here is the source download (98 KB):

http://www.ludicity.org/files/bezier.tar.gz

[chronozphere]

Looks good. :)

I'm not really into lazarus/FPC yet but I have them installed. When I tried to open the *.pp file, Lazarus told me it couldn't be read. :o

[jdarling]

I'll have to take a look and see if there is a difference in how your doing it and how I did it in my little test http://eonclash.com/ViewProduct.php?ProductID=25

Always nice to have two to compare :)

PS: I've done work on that since (allowing you to move points) that I still need to upload :)

[User137]

Hi, just showing a different approach to the curve (called "catmull rom" actually but looks identical to yours). The function takes 4 parameters which are 4 vertices that form the curve. You want to draw the curve between points 2 and 3 while the end points 1 and 4 "lead the curve". If end point 1 equal to 2 or point 4 to 3, those simply show going straight to that direction.

These functions are capable of doing that in 1,2 and 3 dimensions. (You get the idea though even if wanted to add 4th dimension ::) )
type
TVector2f = record x,y: single; end;
TVector3f = record x,y,z: single; end;
PVector2f = ^TVector2f;
PVector3f = ^TVector3f;

function CatmullCalc(const p0,p1,p2,p3,t: single): single;
begin
result:=0.5*( 2*p1+(p2-p0)*t +
(2*p0-5*p1+4*p2-p3)*t*t +
(3*p1-p0-3*p2+p3)*t*t*t );
end;

function Catmull2f(const a,b,c,d: PVector2f; const delta: single): TVector2f;
begin
result.x:=CatmullCalc(a.x, b.x, c.x, d.x, delta);
result.y:=CatmullCalc(a.y, b.y, c.y, d.y, delta);
end;

procedure Catmull3f(res: PVector3f; const a,b,c,d: PVector3f; const delta: single);
begin
res^.x:=CatmullCalc(a.x, b.x, c.x, d.x, delta);
res^.y:=CatmullCalc(a.y, b.y, c.y, d.y, delta);
res^.z:=CatmullCalc(a.z, b.z, c.z, d.z, delta);
end;
Feel free to bring out a more optimal solution, i'm already passing vector pointers x_X

[cragwolf]

Looks good. :)

I'm not really into lazarus/FPC yet but I have them installed. When I tried to open the *.pp file, Lazarus told me it couldn't be read. :o

I don't have Lazarus installed; I just use FPC from the command line. Let me go install Lazarus now.

* * * *

OK I installed it. What you need to do is run Lazarus, and then choose "Project | New Project from File" from menu, choose my "bezier.pp" file in the file dialog, and then choose "Custom Program" from the resulting list, and then you should be able to run my program in Lazarus. At least, this worked for me with FPC 2.2.4, Lazarus 0.9.26.2, on Linux.

If you get any errors during compile, then this is probably because you haven't set up JEDI-SDL properly, or because you're running on Windows and I haven't tested on Windows yet.

[cragwolf]

I'll have to take a look and see if there is a difference in how your doing it and how I did it in my little test http://eonclash.com/ViewProduct.php?ProductID=25

Looks like you're calculating it manually, while I'm relying on OpenGL evaluators to do it for me. And you're drawing a single Bezier curve, while I'm drawing a number of Bezier curves and making sure they join up smoothly. Good idea to let users move the points; I don't do that currently because I'm a little bit scared of solving (possibly large) simultaneous equations for every movement of the mouse! :-[

[cragwolf]

Hi, just showing a different approach to the curve (called "catmull rom" actually but looks identical to yours).

Nice. That's how I'd do it if I wanted to join a bunch of points with a smooth curve. But I wanted to see if I could do it with Bezier curves, which aren't really designed for that purpose. But sometimes you can turn a screwdriver into a hammer. ;)

[noeska]

and another aproach:


//cubic bezier line ( (1-i)^3*pa+3*i(1-i)^2*pb+3*i^2*(1-i)*pc+i^3*pd )
procedure TPath.DrawCSpline( AFrom, ATo, AFromControlPoint, AToControlPoint: TPoint );
var
di, i : Double;
p1, p2: TPoint;
begin
di := 1.0 / FSplinePrecision;
i := di;
p2 := AFrom;
while i <=1.0 do
begin
if i-di/2 > 1.0-di then
i := 1.0;
p1 := p2;
p2.x := power(i,3)*(ATo.x+3*(AFromControlPoint.x-AToControlPoint.x)-AFrom.x)
+ 3* power(i,2)*(AFrom.x-2*AFromControlPoint.x+AToControlPoint.x)
+ 3* i*(AFromControlPoint.x-AFrom.x)+AFrom.x;
p2.y := power(i,3)*(ATo.y+3*(AFromControlPoint.y-AToControlPoint.y)-AFrom.y)
+ 3* power(i,2)*(AFrom.y-2*AFromControlPoint.y+AToControlPoint.y)
+ 3* i*(AFromControlPoint.y-AFrom.y)+AFrom.y;
if not EqualPoints( p1, p2 ) then
NewStroke( p1, p2 ); //line
i := i + di;
end;

NewStroke( p2, ATo);
end;


//quadratic bezier line ( (1-i)^2*pa+2*i(1-i)*pb+i^2*pc )
procedure TPath.DrawQSpline( AFrom, ATo, AControlPoint: TPoint );
var di, i: double;
p1,p2: TPoint;
begin
di := 1.0 / FSplinePrecision;
i := di;
p2 := AFrom;
while i<=1.0 do
begin
if i-di/2 > 1.0-di then
i := 1.0;
p1 := p2;
p2.X := (AFrom.X-2*AControlPoint.X+ATo.X)*sqr(i) + (2*AControlPoint.X-2*AFrom.X)*i + AFrom.X;
p2.Y := (AFrom.Y-2*AControlPoint.Y+ATo.Y)*sqr(i) + (2*AControlPoint.Y-2*AFrom.Y)*i + AFrom.Y;
if not EqualPoints( p1, p2 ) then
NewStroke( p1, p2 ); //line
i := i + di;
end;
//pc := p2; ?

NewStroke( p2, ATo);
end;



Btw your versions seem to be more optimized then mine.

And here is the compete unit: http://thuis.vanderhoning.net/svn_glvg/trunk/
It is a svg /vector graphincs rendere for opengl in progress.

E.g. it can do this:

// http://commons.wikimedia.org/wiki/File:Cat_drawing.svg
mypath := 'M 380.76986,379.21038 C 380.76986,439.81681 324.84665,489.00463 255.94126,489.00463';
mypath := mypath + ' C 187.03587,489.00463 131.11266,439.81681 131.11266,379.21038 C 131.11266';
mypath := mypath + ',348.90716 118.81375,247.16173 141.40773,227.28897 C 152.70472,217.35259 192.4347';
mypath := mypath + ',283.60703 207.36733,278.0487 C 222.29995,272.49036 238.71492,269.41612 255.94126,269.41612';
mypath := mypath + ' C 273.16761,269.41612 289.58257,272.49036 304.51519,278.0487 C 319.44781,283.60703 357.30068';
mypath := mypath + ',223.95676 368.59767,233.89313 C 391.19165,253.76589 380.76986,348.90716 380.76986,379.21038 z';

[JernejL]

Why does everyone want to draw splines? in 99.9% of cases in games you want to have a object traveling along a spline, but it would need to be highly efficient spline evalutor to do that at runtime with a lot of objects.

[NecroDOME]

I want to draw a spline and extrude some 3D models over it! (However, I already have my spline-calculations in place, only need to draw the 3D model)

Drawing a spline can also be useful in an editor to see what the actual movement of an object is.

[User137]

Would be very interesting to use bezier idea in a 3D modelling tool.. increasing polygons of existing objects in smooth way or making new object entirely with control points. Problem is it can become slow or complicated when interpolating neighbour triangles/polygons.

But something i did use the idea for is frame animation for 3D object. It looks better than "hard cornered" interpolation even though low frame count can result in model bending in unnatural ways.

[noeska]

My interest in them is to be able to use a drawing program like inkscape ( http://www.inkscape.org/ ) to create a gui for a game. Or draw vector graphic sprites, and use them as real vector shapes in the game.
That way the gui / sprite is resolution indepenend. e.g. it should not matter if the sceen is 1024x768 or 1280x1024 pixels. If you convert drawings to bitmaps first you get blocky results at higher resolutions(monitors)

And the most intersting things you draw with inkscape use splines as it as splines are part of the svg standard.

Also i dont draw the splines directly i triangulate the shape the multiple splines define first into a (3d) mesh and render that instead. E.g. i should be able to export that mesh to an .obj or milkshape ascii file (but then it would become partly resolution depened as on higher resolution you might see lines that make the spline.
So i keep the original vector shape as long as possibe and triangulate on loading the gui/level.

Also i use splines for paths in my 3D Adventure Studio project. And in the editor i need to visualize them.

Besides round shapes are nicer to look at then square or angled ones. So you have to invest in splines. But i am open for alternatives though.

[jdarling]

Why does everyone want to draw splines? in 99.9% of cases in games you want to have a object traveling along a spline, but it would need to be highly efficient spline evalutor to do that at runtime with a lot of objects.


Well, actually, I was researching it a while back just for kicks. Now I'm looking back into it for my boat design software. Splines are easy for users to interact with and with the way I'm handling them calculating distance along them is made easy (just sum the distance for each point group).

[paul_nicholls]

Hi, just showing a different approach to the curve (called "catmull rom" actually but looks identical to yours). The function takes 4 parameters which are 4 vertices that form the curve. You want to draw the curve between points 2 and 3 while the end points 1 and 4 "lead the curve". If end point 1 equal to 2 or point 4 to 3, those simply show going straight to that direction.

These functions are capable of doing that in 1,2 and 3 dimensions. (You get the idea though even if wanted to add 4th dimension ::) )
type
TVector2f = record x,y: single; end;
TVector3f = record x,y,z: single; end;
PVector2f = ^TVector2f;
PVector3f = ^TVector3f;

function CatmullCalc(const p0,p1,p2,p3,t: single): single;
begin
result:=0.5*( 2*p1+(p2-p0)*t +
(2*p0-5*p1+4*p2-p3)*t*t +
(3*p1-p0-3*p2+p3)*t*t*t );
end;

function Catmull2f(const a,b,c,d: PVector2f; const delta: single): TVector2f;
begin
result.x:=CatmullCalc(a.x, b.x, c.x, d.x, delta);
result.y:=CatmullCalc(a.y, b.y, c.y, d.y, delta);
end;

procedure Catmull3f(res: PVector3f; const a,b,c,d: PVector3f; const delta: single);
begin
res^.x:=CatmullCalc(a.x, b.x, c.x, d.x, delta);
res^.y:=CatmullCalc(a.y, b.y, c.y, d.y, delta);
res^.z:=CatmullCalc(a.z, b.z, c.z, d.z, delta);
end;
Feel free to bring out a more optimal solution, i'm already passing vector pointers x_X


Pretty neat :)

Just for fun, I rewrote it slightly to add some interface consistency, and to optimise it a bit :)

type
PVector1f = ^single;

PVector2f = ^TVector2f;
TVector2f = record
x,y: single;
end;

PVector3f = ^TVector3f;
TVector3f = record
x,y,z: single;
end;

procedure CatmullRom1f(const p0,p1,p2,p3: PVector1f; const t: single; const p: PVector1f);
var
tt : single;
ttt: single;
begin
tt := t * t;
ttt := tt * t;
p^ := 0.5 * (2*p1^+(p2^-p0^)*t + (2*p0^-5*p1^+4*p2^-p3^)*tt + (3*p1^-p0^-3*p2^+p3^)*ttt);
end;

procedure CatmullRom2f(const p0,p1,p2,p3: PVector2f; const t: single; const p: PVector2f);
var
tt : single;
ttt: single;
begin
tt := t * t;
ttt := tt * t;

p^.x := 0.5 * (2*p1^.x+(p2^.x-p0^.x)*t + (2*p0^.x-5*p1^.x+4*p2^.x-p3^.x)*tt + (3*p1^.x-p0^.x-3*p2^.x+p3^.x)*ttt);
p^.y := 0.5 * (2*p1^.y+(p2^.y-p0^.y)*t + (2*p0^.y-5*p1^.y+4*p2^.y-p3^.y)*tt + (3*p1^.y-p0^.y-3*p2^.y+p3^.y)*ttt);
end;

procedure CatmullRom3f(const p0,p1,p2,p3: PVector3f; const t: single; const p: PVector3f);
var
tt : single;
ttt: single;
begin
tt := t * t;
ttt := tt * t;

p^.x := 0.5 * (2*p1^.x+(p2^.x-p0^.x)*t + (2*p0^.x-5*p1^.x+4*p2^.x-p3^.x)*tt + (3*p1^.x-p0^.x-3*p2^.x+p3^.x)*ttt);
p^.y := 0.5 * (2*p1^.y+(p2^.y-p0^.y)*t + (2*p0^.y-5*p1^.y+4*p2^.y-p3^.y)*tt + (3*p1^.y-p0^.y-3*p2^.y+p3^.y)*ttt);
p^.z := 0.5 * (2*p1^.z+(p2^.z-p0^.z)*t + (2*p0^.z-5*p1^.z+4*p2^.z-p3^.z)*tt + (3*p1^.z-p0^.z-3*p2^.z+p3^.z)*ttt);
end;


cheers,
Paul

[paul_nicholls]

I'll have to take a look and see if there is a difference in how your doing it and how I did it in my little test http://eonclash.com/ViewProduct.php?ProductID=25

Looks like you're calculating it manually, while I'm relying on OpenGL evaluators to do it for me. And you're drawing a single Bezier curve, while I'm drawing a number of Bezier curves and making sure they join up smoothly. Good idea to let users move the points; I don't do that currently because I'm a little bit scared of solving (possibly large) simultaneous equations for every movement of the mouse! :-[


Hi gragwolf,
If you look at this site:

http://local.wasp.uwa.edu.au/~pbourke/geometry/bezier/cubicbezier.html

specifically the FAQ section near the bottom, it shows ways of calculating the control points for piece-wise bezier curves without solving simultaneous equations :)

cheers,
Paul

[cragwolf]

Hi gragwolf,
If you look at this site:

http://local.wasp.uwa.edu.au/~pbourke/geometry/bezier/cubicbezier.html

specifically the FAQ section near the bottom, it shows ways of calculating the control points for piece-wise bezier curves without solving simultaneous equations :)

That's cool, thanks. I often go to that site for graphics algorithms, but I must have missed this article somehow.

[paul_nicholls]

Hi gragwolf,
If you look at this site:

http://local.wasp.uwa.edu.au/~pbourke/geometry/bezier/cubicbezier.html

specifically the FAQ section near the bottom, it shows ways of calculating the control points for piece-wise bezier curves without solving simultaneous equations :)

That's cool, thanks. I often go to that site for graphics algorithms, but I must have missed this article somehow.


No worries, and yeah, it was hard to find that article from the menu on that site :)

BTW, here are a couple of more gems ;)

http://local.wasp.uwa.edu.au/~pbourke/miscellaneous/interpolation/
http://www.blackpawn.com/texts/splines/

Actually, the blackpawn site has quite a few neat articles (http://www.blackpawn.com/texts/default.html) :)

cheers,
Paul

[User137]

Just for fun, I rewrote it slightly to add some interface consistency, and to optimise it a bit :)

I dare claim that CatmullRom1f() would be more optimal if it didn't use variables tt,ttt :) However they reduce 9 multiplications in CatmullRom3f().

Yes those are also more consistent, my libs aren't always like that ::) Catmull3f used to be function too until i needed to make it much faster for realtime 3D graphics.

[paul_nicholls]

Hi all, if you are curious, I helped a user over on www.DevMaster.net (http://www.DevMaster.net) who was wanting to use splines to smooth between points...

I used the catmull-rom code from this thread in that thread along with some code snippets of an example project that does random points and draws a complete open/closed piece-wise c-spline curves between them :)

http://www.devmaster.net/forums/showthread.php?p=69427

So if you still weren't sure how to use catmull-rom splines, especially closed curves, go and take a look ;)

http://img199.imageshack.us/img199/2274/catmullromclosed.png
http://img241.imageshack.us/img241/8276/catmullromopened.png

cheers,
Paul

[cragwolf]

Nice work.

[paul_nicholls]

Nice work.


Thanks :)

I do have to say thanks to people from here too ;)

cheers,
Paul