0
101 Aug 09, 2009 at 05:49

Hi,

It might sound naive, but I cannot find any direct code to compute interpolating points for a parametric curve.

Suppose I have a coarse mesh of points along a circle and I would like to smooth my drawing by interpolating in between with, for example 10 “fine points” in between every coarse point. Something like Excel smooth drawing.

Can anyone suggest a code (C,C++,Java,FORTRAN). I know it exists but I simply cannot find it. All it is a function that takes a series if coarse points (parameterized through t) (x(t),y(t)), or (x,y,z) and returns a new set of points on a fine mesh. The user would have a choice of setting the granularity of the fine mesh.

Thank you
Gregory

#### 6 Replies

0
167 Aug 09, 2009 at 07:53

Google for Catmull-Rom splines; those should do what you want.

0
101 Aug 09, 2009 at 14:37

Thank you!
Gregory

0
101 Aug 13, 2009 at 06:02

Hi Gregory,
I have some Catmull-Rom spline code, but it is in Object Pascal (Delphi).

I got it from http://www.pascalgamedevelopment.com/forum/index.php?topic=5833.0 and modified slightly to optimise and also make the interface more consistent between functions.

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);
begin
p^  := 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;

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;


It has 1, 2 and 3 dimension version of the same routine.

To use just plug in 4 of your coarse points, along with some interpolation values (between 0.0 and 1.0).

Where:
p1 and p2 are two of your coarse points you want to iterate smoothly between.
p0 is the point before p1.
p3 is the point after p2.

If p0 or p3 is outside the list of points then you have to special case stuff depending on whether the curve is open or closed…

I am trying to get some sample code together so you can see it working…

Edit

http://www.mvps.org/directx/articles/catmull/

I hope this helps :)
cheers,
Paul

0
101 Aug 13, 2009 at 12:09

I have managed to whip up a small project that shows how to do the Catmull-Rom interpolation :)

It only does 2d splines, but is easily extended to 3d if you want…

closed splines

open splines

I will post the code snippits here so you can learn from them…

I have a form with a checkbox on it for opening/closing the spline.

The form contains a dynamic array of my coarse spline points and some helper functions for when I draw the spline.

TForm1 = class(TForm)
CheckBox_CurveIsClosed: TCheckBox;
procedure FormCreate(Sender: TObject);
procedure FormPaint(Sender: TObject);
procedure CheckBox_CurveIsClosedClick(Sender: TObject);
procedure FormResize(Sender: TObject);
private
{ Private declarations }
MyPoints : Array Of TVector2f;
Function  GetPoint(const Index : Integer) : TVector2f;
Function  GetPreviousPoint(const Index : Integer; const p1,p2 : PVector2f) : TVector2f;
Function  GetNextPoint(const Index : Integer; const p1,p2 : PVector2f) : TVector2f;
Procedure DrawCatmullRomSpline(const p0,p1,p2,p3 : PVector2f; const SplineSegments : Integer);
public
{ Public declarations }
end;


I first create the array of points like so:

Const
cMaxPoints = 5;

procedure TForm1.FormCreate(Sender: TObject);
Var
i : Integer;
begin
RandSeed := 321;
SetLength(MyPoints,cMaxPoints);
For i := 0 To cMaxPoints - 1 Do
Begin
MyPoints[i].X := Random(ClientWidth  - 40) + 40;
MyPoints[i].Y := Random(ClientHeight - 40) + 40;
End;
end;


I draw the spline using SplineSegments number of lines between the coarse points:

Procedure TForm1.DrawCatmullRomSpline(const p0,p1,p2,p3 : PVector2f; const SplineSegments : Integer);
Var
n : Integer;
t : Single;
p : TVector2f;
Begin
For n := 0 To SplineSegments Do
Begin
t := n / SplineSegments; // 0.0 to 1.0)
// return p by interpolating between p1 and p2 using t and being influenced by p0 & p3
CatmullRom2f(p0,p1,p2,p3,t,@p);
If n = 0 Then
Canvas.MoveTo(Trunc(p.x),Trunc(p.y))
Else
Canvas.LineTo(Trunc(p.x),Trunc(p.y));
End;
End;


I draw the splines between the points in the paint method like so:

procedure TForm1.FormPaint(Sender: TObject);
Const
cSplineSegments = 10;
Var
i           : Integer;
i0,i1,i2,i3 : Integer;
p0,p1,p2,p3 : TVector2f;
begin
Canvas.Brush.Color := clWhite;
Canvas.FillRect(ClientRect);
Canvas.Pen.Color := clBlack;
If CheckBox_CurveIsClosed.Checked Then
Begin
For i := 0 To cMaxPoints - 1 Do
Begin
i0 := i - 1;  // index of point prior to curve to interpolate
i1 := i + 0;  // index of start point of curve to interpolate
i2 := i + 1;  // index of end point of curve to interpolate
i3 := i + 2;  // index of point after curve to interpolate

p0 := GetPoint(i0);
p1 := GetPoint(i1);
p2 := GetPoint(i2);
p3 := GetPoint(i3);

DrawCatmullRomSpline(@p0,@p1,@p2,@p3,cSplineSegments);
End
End
Else
Begin
For i := 0 To cMaxPoints - 2 Do
Begin
i0 := i - 1;  // index of point prior to curve to interpolate
i1 := i + 0;  // index of start point of curve to interpolate
i2 := i + 1;  // index of end point of curve to interpolate
i3 := i + 2;  // index of point after curve to interpolate

p1 := MyPoints[i1];
p2 := MyPoints[i2];
p0 := GetPreviousPoint(i0,@p1,@p2);
p3 := GetNextPoint    (i3,@p1,@p2);

DrawCatmullRomSpline(@p0,@p1,@p2,@p3,cSplineSegments);
End;
End;
Canvas.Pen.Color  := clRed;
Canvas.Font.Color := clRed;
For i := 0 To cMaxPoints - 1 Do
Begin
Canvas.TextOut(Trunc(MyPoints[i].X-4),Trunc(MyPoints[i].y-4),IntToStr(i));
End;
end;


The other helper routines used are here:

Function WrapValue(n,l,h : Integer) : Integer;
Begin
If (n < l) Then
n := h - ((l - n) - 1)
Else
If (n > h) Then
n := l + ((n - h) - 1);
Result := n;
End;

Function  TForm1.GetPoint(const Index : Integer) : TVector2f;
Begin
Result := MyPoints[WrapValue(Index,0,cMaxPoints - 1)];
End;

Function  TForm1.GetPreviousPoint(const Index : Integer; const p1,p2 : PVector2f) : TVector2f;
Begin
If Index >= 0 Then
// point prior to first curve segment point (p1) is in range so get point
Result := MyPoints[Index]
Else
Begin
// make up a point before p1, but in line with (p2 - p1) vector
Result.X := p1^.X - (p2^.X - p1^.X);
Result.Y := p1^.Y - (p2^.Y - p1^.Y);
End;
End;

Function  TForm1.GetNextPoint(const Index : Integer; const p1,p2 : PVector2f) : TVector2f;
Begin
If Index <= cMaxPoints - 1 Then
// point after second curve segment point (p2) is in range so get point
Result := MyPoints[Index]
Else
Begin
// make up a point after p2, but in line with (p2 - p1) vector
Result.X := p2.X + (p2.X - p1.X);
Result.Y := p2.Y + (p2.Y - p1.Y);
End;
End;


I hope this clears things up for you, enjoy :)

cheers,
Paul

0
101 Aug 18, 2009 at 11:38

I’m curious as to if anyone found this info helpful? ;)

cheers,
Paul

0
101 Aug 18, 2009 at 14:10

Thank you Paul,