6 replies to this topic

[Gregory]

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

[Reedbeta]

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

[Gregory]

Thank you!
Gregory

[paul_nicholls]

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

I got it from http://www.pascalgam...hp?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
You can read about catmull-rom splines here:
http://www.mvps.org/...ticles/catmull/

I hope this helps :)
cheers,
Paul

[paul_nicholls]

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

[paul_nicholls]

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

cheers,
Paul

[Twigl]

Thank you Paul,

I have already saved the whole thread for further using!