Making a smooth path from an irregular number of x,y points to simulate handwriting

Question

I am trying to make a 'brush' tool in AS3 (pure, not Flex) which simulates handwriting, making strokes to be smooth instead of cornered. Then, the trace must be reduced to cubic bezier curves which can be dragged and deformed, affecting the previously drawn path (like the illustrator's pen tool).

I'm tracking the mouse movement to get a set of points to draw the path. As far as I know, I need to do a B-Spline path using that set of points. Then I should reduce it to cubic bezier curves (adding the the 'pen tool' functionality to the path).

I have already developed the pen tool, using an algorithm which reduces Cubic Beziers to Quadratic Beziers (and then using the Flash curveTo function). But I have no idea how to create a B-Spline (or another simplification), an then reduce it to Bezier curves.

Do you know any way to accomplish this?

Answer 1

There is an algorithm in a c library that does what you are asking: http://tog.acm.org/resources/GraphicsGems/gems/FitCurves.c

This is a rather complex algorithm that simplifies your geometry by converting a list of many points into a list of a few close fitting bezier curves, essentially turning scribbles into very smooth curves. It has an adjustable amount of slack, and works by finding the fewest amount of bezier curves that fit your set of points within a certain slack. So the higher you set the slack of the algorithm, the smoother (but potentially less accurate) your writing gets.

Answer 2

not sure if you specifically need beziers, but this catmull-rom spline tool is pretty great: http://www.motiondraw.com/md/as_samples/t/CatmullRomSpline/tween.html

Answer 3

I used this function one time.

    public function multicurve(g: Graphics, args: Array, closed: Boolean): void {           
            var mid: Array = args.slice();  //make dublicate
            var i: uint;
            var point: Point;
            var nextPoint: Point;
            var numPoints: uint = mid.length;

            if (numPoints == 2) {
                g.moveTo(mid[0].x, mid[0].y);
                g.lineTo(mid[1].x, mid[1].y);
                return;
            }

            var Xpoint: Array = new Array();
            var Ypoint: Array = new Array();
            for (i = 1; i < numPoints - 2; i++) {
                point = mid[i];
                nextPoint = mid[i+1];
                Xpoint[i] = 0.5*(nextPoint.x + point.x);
                Ypoint[i] = 0.5*(nextPoint.y + point.y);
            }
            if (closed) {
                Xpoint[0] = 0.5*(mid[1].x + mid[0].x);
                Ypoint[0] = 0.5*(mid[1].y + mid[0].y);
                Xpoint[i] = 0.5*(mid[i+1].x + mid[i].x);
                Ypoint[i] = 0.5*(mid[i+1].y + mid[i].y);
                Xpoint[i+1] = 0.5*(mid[i+1].x + mid[0].x);
                Ypoint[i+1] = 0.5*(mid[i+1].y + mid[0].y);
                mid.push(new Point(mid[0].x, mid[0].y));
                Xpoint[i+2] = Xpoint[0];
                Ypoint[i+2] = Ypoint[0];
            } else {
                Xpoint[0] = mid[0].x;
                Ypoint[0] = mid[0].y;
                Xpoint[i] = mid[i+1].x;
                Ypoint[i] = mid[i+1].y;
                mid.pop();
                numPoints--;
            }
            g.moveTo(Xpoint[0], Ypoint[0]);
            for (i = 1; i < numPoints; i++) {
                point = mid[i];
                g.curveTo(point.x, point.y, Xpoint[i], Ypoint[i]);
            }
            if (closed) {
                g.curveTo(mid[0].x, mid[0].y, Xpoint[i], Ypoint[i]);
            }
        }

Answer 4

The jhotdraw is an opensource project in Java for drawing. It converts free hand drawings into cubic bezier curves. The source is available - download and translate. Don't get scared at the size of the project : you need only a couple of classes namely:

org.jhotdraw.geom.Bezier
org.jhotdraw.geom.BezierPath
org.jhotdraw.geom.Geom

While translating start by changing all the collection declarations to Arrays (use vectors if you are targeting only FP10 users). I've some regexes that you might find useful in the conversion - I can post them if you want.

---

Here is a list of regexes that you might find useful. In each pair, paste the first one into search text area and second one into replace area, check the regex check box and use Find and Replace buttons. Don't use Replace All - none of these are guaranteed to be foolproof.

Replace all int/double name declarations with var name:Number

\b(double|int)\s+(\w+)\b

var $2:Number

Replace all Point2D.Double name declarations with var name:Point

\bPoint2D\.Double\s+(\w+)\b

var $1:Point

Replace all int/double name declarations in function signatures with name:Number

\(([^)]*)\b(?:double|int)\s+(\w+)\b([^)]*?)\)

($1$2:Number$3)

Replace all Point2D.Double name declarations in function signatures with name:Point

\(([^)]*)\b(?:Point2D\.Double)\s+(\w+)\b([^)]*?)\) 

($1$2:Point$3)

Before changing method signatures, make sure all methods are static:

(public|private)\s+(?!static)

Replace method signatures to AS format

(public|private)\s+static\s+(\w+)\s+(\w+)\s*\(([^)]*)\)

$1 static function $3($4):$2

Replace ArrayList.get(index) with array[index] //Warning: fails for list.get(list.size() - 1)

(\w+)\.get\(([^)]+)\)

$1[$2]

//avoid the () failure 

(\w+)\.get\(([^)]*(?:\([^)]*\))[^)]*)\)

$1[$2]

Replace ArrayList.set(index, element) with array[index] = element //Warning: fails for list.set(i, list.size())

(\w+)\.set\(([^,]+)\s*,\s*([^)]+)\)

$1[$2] = $3


/*the above regex successfully made the following replacement*/

cleaned.set(cleaned.size() - 1, digitizedPoints[digitizedPoints.size() - 1])

cleaned[cleaned.size() - 1] = digitizedPoints[digitizedPoints.size() - 1]

Replace arraylist.add(object) with array.push(object)

//would fail if object contains ')'
//add(index, object) should be done with splice

(\w+)\.add\(([^)]+)\)

$1.push($2)

//too many failures - fail safe version - 
//still fails for nested parenthesis  list.add(new Point(a.first(), a.last())) 
//- only three such cases - the effort to match parenthesis wouldn't be worth it
//works for list.add(new Point(3, 4)) - there were many similar cases

(\w+)\.add\(([^)]*(?:\([^)]*\))[^)]*)\)

$1.push($2)

Replace method signatures to AS format (non static methods)

(public|private)\s+(?!function)(\w+)\s+(\w+)\s*\(([^)]*)\)

$1 function $3($4):$2

Replace all int/double/point/boolean name declarations in function signatures with name:type

\(([^)]*)\b(\w+)\s+(\w+)\b([^)]*?)\)

($1$3:$2$4)

Replace all variable declarations in its own line with an = to AS format

^(\s+)(\w+)\s+(\w+)\s*=\s*(.+?)\s*;(\s*)$

$1var $3:$2 = $4;$5

change placing of braces.

^(\t)(\s*)([^\n]+)\{\s*(\n)\s+

$1$2$3$4$1$2{$4$1$2

change } else into } \n else

^([ \t]+)}[ \t]*else\b([^\n]*)(\n)

$1}$3$1else$2$3

Replace 4 variable declarations in a single line to AS in different lines

^(\t+)(\w+)\s+(\w+)\s*,\s*(\w+)\s*,\s*(\w+)\s*,\s*(\w+)\s*;[ \t]*(\n)

$1var $3:$2;$7$1var $4:$2;$7$1var $5:$2;$7$1var $6:$2;$7

Replace array declarations

^(\s+)\w+\[\]\s*(\w+)\b

$1 var $2:Array

Remove () casting - AS compiler doesn't like them

(?:\(\w+\)\s*)([^ ,*+;/)><=\-])

$1

Replace max etc into Math.max - AS doesn't have static imports

(?<!Math\.)\b(max|min|abs|sqrt|PI|cos|sin|atan2)\(

Math.$1(