How to draw a continuous curved line from 3 given points at a time

Question

I am trying to draw a continuous curved line in flash. There are many methods but none of the ones I have found so far quite fit my requirements. First of all, I want to use the flash graphic api's curveTo() method. I DO NOT want to simulate a curve with hundreds of calls to lineTo() per curved line segment. It is my experience and understanding that line segments are processor heavy. Flash's quadratic bezier curve should take less CPU power. Please challenge this assumption if you think I am wrong.

I also do not want to use a pre-made method that takes the entire line as an argument (eg mx.charts.chartClasses.GraphicsUtilities.drawPolyline()). The reason is that I will need to modify the logic eventually to add decorations to the line I am drawing, so I need something I understand at its lowest level.

I have currently created a method that will draw a curve given 3 points, using the mid-point method found here.

Here is a picture:

The problem is that the lines do not actually curve through the "real" points of the line (the gray circles). Is there a way using the power of math that I can adjust the control point so that the curve will actually pass through the "real" point? Given only the current point and its prev/next point as arguments? The code to duplicate the above picture follows. It would be great if I could modify it to meet this requirement (note the exception for first and last point).

package {
  import flash.display.Shape;
  import flash.display.Sprite;
  import flash.display.Stage;
  import flash.geom.Point;

  [SWF(width="200",height="200")]
  public class TestCurves extends Sprite {
    public function TestCurves() {
      stage.scaleMode = "noScale";
      var points:Array = [
        new Point(10, 10), 
        new Point(80, 80), 
        new Point(80, 160), 
        new Point(20, 160), 
        new Point(20, 200),
        new Point(200, 100)
      ];

      graphics.lineStyle(2, 0xFF0000);

      var point:Point = points[0];
      var nextPoint:Point = points[1];

      SplineMethod.drawSpline(graphics, point, null, nextPoint);

      var prevPoint:Point = point;

      var n:int = points.length;
      var i:int;
      for (i = 2; i < n + 1; i++) {
        point = nextPoint;
        nextPoint = points[i]; //will eval to null when i == n

        SplineMethod.drawSpline(graphics, point, prevPoint, nextPoint);

        prevPoint = point;
      }

      //straight lines and vertices for comparison
      graphics.lineStyle(2, 0xC0C0C0, 0.5);
      graphics.drawCircle(points[0].x, points[0].y, 4);
      for (i = 1; i < n; i++) {
        graphics.moveTo(points[i - 1].x, points[i - 1].y);
        graphics.lineTo(points[i].x, points[i].y);
        graphics.drawCircle(points[i].x, points[i].y, 4);
      }

    }
  }
}
import flash.display.Graphics;
import flash.geom.Point;

internal class SplineMethod {
  public static function drawSpline(target:Graphics, p:Point, prev:Point=null, next:Point=null):void {
    if (!prev && !next) {
      return; //cannot draw a 1-dimensional line, ie a line requires at least two points
    }

    var mPrev:Point; //mid-point of the previous point and the target point
    var mNext:Point; //mid-point of the next point and the target point

    if (prev) {
      mPrev = new Point((p.x + prev.x) / 2, (p.y + prev.y) / 2);
    }
    if (next) {
      mNext = new Point((p.x + next.x) / 2, (p.y + next.y) / 2);
      if (!prev) {
        //This is the first line point, only draw to the next point's mid-point
        target.moveTo(p.x, p.y);
        target.lineTo(mNext.x, mNext.y);
        return;
      }
    } else {
      //This is the last line point, finish drawing from the previous mid-point
      target.moveTo(mPrev.x, mPrev.y);
      target.lineTo(p.x, p.y);
      return;
    }
    //draw from mid-point to mid-point with the target point being the control point.
    //Note, the line will unfortunately not pass through the actual vertex... I want to solve this
    target.moveTo(mPrev.x, mPrev.y);
    target.curveTo(p.x, p.y, mNext.x, mNext.y);
  }
}

Later I will be adding arrows and things to the draw method.

Modulation

Ok, to get the desired effect, it is starting to look like I may need at least 4 points at any given time for my draw method. Correct me if I am wrong. So far, I am just using mid-point calculations; no trig yet. – Modulation

There is a spline drawing package for flex: degrafa.org/docs – Modulation

+1 for the lucid writing style ! – Algernon

Answer 1

Ok, the Catmull-Rom spline suggestion is a good one but not exactly what I am looking for. The example from the link provided was a good starting point, but a bit inflexible. I have taken it and modified my original source code to use it. I am posting this as an answer because I think it is more modular and easier to understand than Zevan's blog post (no offense Zevan!). The following code will display the following image:

Here is the code:

    package {
        import flash.display.Shape;
        import flash.display.Sprite;
        import flash.display.Stage;
        import flash.geom.Point;

        [SWF(width="300",height="300")]
        public class TestCurves extends Sprite {
            public function TestCurves() {
                stage.scaleMode = "noScale";

                //draw a helpful grid
                graphics.lineStyle(1, 0xC0C0C0, 0.5);
                for (var x:int = 0; x <= 300; x += 10) {
                    graphics.moveTo(x, 0);
                    graphics.lineTo(x, 300);
                    graphics.moveTo(0, x);
                    graphics.lineTo(300, x);
                }

                var points:Array = [
                    new Point(40, 20), 
                    new Point(120, 80), 
                    new Point(120, 160), 
                    new Point(60, 160), 
                    new Point(60, 200), 
                    new Point(240, 150), 
                    new Point(230, 220), 
                    new Point(230, 280)
                ];

                SplineMethod.setResolution(5);

                graphics.lineStyle(2, 0xF00000);
                graphics.moveTo(points[0].x, points[0].y);

                var n:int = points.length;
                var i:int;

                for (i = 0; i < n - 1; i++) {
                    SplineMethod.drawSpline(
                        graphics, 
                        points[i], //segment start
                        points[i + 1], //segment end
                        points[i - 1], //previous point (may be null)
                        points[i + 2] //next point (may be null)
                    );
                }

                //straight lines and vertices for comparison
                graphics.lineStyle(2, 0x808080, 0.5);
                graphics.drawCircle(points[0].x, points[0].y, 4);
                for (i = 1; i < n; i++) {
                    graphics.moveTo(points[i - 1].x, points[i - 1].y);
                    graphics.lineTo(points[i].x, points[i].y);
                    graphics.drawCircle(points[i].x, points[i].y, 4);
                }
            }
        }
    }
    import flash.display.Graphics;
    import flash.geom.Point;

    internal class SplineMethod {

        //default setting will just draw a straight line
        private static var hermiteValues:Array = [0, 0, 1, 0];

        public static function setResolution(value:int):void {
            var resolution:Number = 1 / value;
            hermiteValues = [];
            for (var t:Number = resolution; t <= 1; t += resolution) {
                var h00:Number = (1 + 2 * t) * (1 - t) * (1 - t);
                var h10:Number = t  * (1 - t) * (1 - t);
                var h01:Number = t * t * (3 - 2 * t);
                var h11:Number = t * t * (t - 1);
                hermiteValues.push(h00, h10, h01, h11);
            }
        }

        public static function drawSpline(target:Graphics, segmentStart:Point, segmentEnd:Point, prevSegmentEnd:Point=null, nextSegmentStart:Point=null):void {
            if (!prevSegmentEnd) {
                prevSegmentEnd = segmentStart;
            }
            if (!nextSegmentStart) {
                nextSegmentStart = segmentEnd;
            }

            var m1:Point = new Point((segmentEnd.x - prevSegmentEnd.x) / 2, (segmentEnd.y - prevSegmentEnd.y) / 2);
            var m2:Point = new Point((nextSegmentStart.x - segmentStart.x) / 2, (nextSegmentStart.y - segmentStart.y) / 2);

            var n:int = hermiteValues.length;
            for (var i:int = 0; i < n; i += 4) {
                var h00:Number = hermiteValues[i];
                var h10:Number = hermiteValues[i + 1];
                var h01:Number = hermiteValues[i + 2];
                var h11:Number = hermiteValues[i + 3];

                var px:Number = h00 * segmentStart.x + h10 * m1.x + h01 * segmentEnd.x + h11 * m2.x;
                var py:Number = h00 * segmentStart.y + h10 * m1.y + h01 * segmentEnd.y + h11 * m2.y;

                target.lineTo(px, py);
            }
        }
    }

This is not a perfect solution. But unfortunately, I cannot piece together how to accomplish what I want using curveTo(). Note that GraphicsUtilities.drawPolyLine() does accomplish what I am attempting to do--the problem there is that it is inflexible and I cannot parse the code (more importantly, it doesn't appear to properly draw acute angles--correct me if I am wrong). If anyone can provide any insight, please post. For now, the above is my answer.

Modulation

Note: a performance increase might be gained from using Vector instead of Array for the Hermite Function values--very important for me. – Modulation

Answer 2

I think you're looking for a Catmull-Rom spline. I've googled an AS3 implementation for you but haven't tried it so use at your own discretion:

http://actionsnippet.com/?p=1031

Pompea

that's my blog post - so I can confirm that the method on that page should work +1 you just need to replace the pixel drawing code with a graphics class lineTo/moveTo and you should be good to go – Millwright

Very nice. But if I understand it correctly, it fails one of my conditions. Which is that I not draw multiple straight line segments to simulate a curve. If I have a performance problem, the only solution would be to lower the curve resolution which would make it more like a series of straight lines. That is why I need to draw curves with flash's curveTo() method. – Modulation

PS, don't think that I am ungrateful. I really like the method. But for my current problem I am doubtful that it is a good fit. – Modulation

Answer 3

I code this, I think it may help:

SWF: http://dl.dropbox.com/u/2283327/stackoverflow/SplineTest.swf

Code: http://dl.dropbox.com/u/2283327/stackoverflow/SplineTest.as

I left a lot of comments on the code. I wish it helps!

Here is the theory behind the code:

A and C are the first and last point, B is the "control point" in AS3 you can draw the curve like this:

graphics.moveTo(A.x, A.y);
graphics.curveTo(B.x, B.y, C.x, C.y);

Now, D is the mid-point of the vector AC. And the mid-point of DB is the mid-point of the curve. Now what I did in the code was to move B exactly to D+DB*2 so, if you draw the curve using that point as control point, the mid-point of the curve will be B.

PS: Sorry for my poor Enlgish

Seasonal

Thanks, but this does not simulate a spline over several arbitrary points. Please refer to GraphicsUtilities.drawPolyLine() for an example of what I am trying to accomplish. – Modulation