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.

[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 )
[pascal]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;[/pascal]
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.

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:

[pascal]
//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;

[/pascal]

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:
[pascal]
// 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';

[/pascal]

[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.