Script:Bézier curves

From Spherical
Revision as of 20:32, 16 March 2013 by Apollolux (talk | contribs) (The Source Code: fill)
Jump to: navigation, search

Bézier curves is a custom script written by NeoLogiX. It is a script that ultimately takes four points and draws a Bézier curve. A later update which has not yet been posted stores the points on the line into a sorted array for future use, i.e. a curved path to make an object travel.

Download and Usage

Getting Started

The source code to generate the curve is at the bottom of this page. Simply copy and paste into the script file of your choice and include it.

API

Object NPoint(int x, int y)
a VERY necessary object for convenience in this code. You COULD write this code using separate variables for each point's x and y, but it would look very messy.
NPoint midpoint(NPoint p1, NPoint p2)
returns the midpoint of two NPoints as an NPoint.
Array killseqduppts(Array arr)
returns an array of NPoints with sequential duplicates removed.
Array BezierLine(NPoint p1, NPoint p2, NPoint p3, NPoint p4, Color col, bool dot, int num)
blits the actual Bézier curve on the screen. p2 is the control point for p1, p3 is the control point for p4, col is the color of the line, dot determines whether the curve is a solid curve or a dotted line curve, and num is an extra level of infinite recursion protection; returns the line as an array of NPoints as well.

About Bézier Curves

There are a number of sources on the subject of Bézier curves, way too many for me to remember or list, so I'll point you to Bézier curve's Wikipedia entry and you can go from there. The short of it is a Bézier curve (at least, for the purposes of this script) is a curved line recursively generated by two endpoints, each with a control point, using "de Casteljau's algorithm" to split a curve into two separate curves and eventually connect the dots.

The Curve Process

Here's the mathematical procedure used by this script to draw the curve:

  • Take two endpoints, p1 & p4, and two control points, p2 for p1 & p3 for p4.
  • Find the midpoints of three connecting lines (L12, L34, L23).
  • Connect the midpoints of L12 & L34 to L23's midpoint to make lines L123 & L234.
  • Connect the midpoints of those two lines to make line Q.
  • Find the midpoint of Q, which will be the vertex point of the active curve.
  • Recursively repeat the previous steps using the resulting point Q as the p4 of the resulting p1 side & as the p1 of the resulting p4 side.

Parameter num is an added measure against the possibility of a "too much recursion" error. Once num is less than or equal to zero, the recursion stops and starts returning control back to the calling function. Alternatively, one could use num to determine the level of detail in the curve's final line (works for both solid curves and dotted curves).

The Source Code

The NPoint object:

function NPoint(x,y) {
	if (!this instanceof NPoint) return new NPoint(x,y);
	this.x = (!isNaN(x))?x:0;
	this.y = (!isNaN(y))?y:0;
	this.toString = function() {return "N["+this.x+","+this.y+"]";}
}

The midpoint function:

function midpoint(p1, p2) { return new NPoint(p1.x+(p2.x-p1.x)*.5, p1.y+(p2.y-p1.y)*.5); }

The function to remove duplicate points in the path returned by the curve:

/**
 * Kill sequential duplicate points
 * @param {Array} arr Array of NPoints
 * @type Array
 * @returns An array of NPoint objects with sequential duplicates removed
 */
function killseqduppts(arr) {
	if (arr.length==0) return [];
	var ret = []; ret.push(arr[0]);
	var i = 0; while (++i<arr.length) { if (arr[i].x!=arr[i-1].x && arr[i].y!=arr[i-1].y) ret.push(arr[i]); }
	return ret;
}

The BezierLine function to draw the actual curve:

/*
 * Optimize against calling the Math object every time
 */
var ABS = Math.abs;
 
/**
 * Draw a curve
 * @param {NPoint} p1 The first endpoint
 * @param {NPoint} p2 The first control point
 * @param {NPoint} p3 The second control point
 * @param {NPoint} p4 The second endpoint
 * @param {Color} col The curve's color
 * @param {boolean} dot Whether to draw a dotted or solid line
 * @param {int} num A maximum level of recursion, -1 if allowed to let distance determine line detail
 * @type Array
 * @returns An array of the drawn points in line order
 */
function BezierLine(p1, p2, p3, p4, col, dot, num) {
	var bpts = [], bzl = arguments.callee;	// bzl is so the code can be copied to ImageBezier without changing much
	var left = false, right = false;
	var m12 = new midpoint(p1,p2);
	var m34 = new midpoint(p3,p4);
	var m23 = new midpoint(p2,p3);
	var m123 = new midpoint(m12,m23);
	var m234 = new midpoint(m23,m34);
	var q = new midpoint(m123,m234);
	var m1a = new midpoint(p1,m12);
	var mb4 = new midpoint(m34,p4);
	// recurse the "left"
	if (num==0 || (parseInt(ABS(p1.x-p2.x))==0 && parseInt(ABS(p1.y-p2.y))==0)) {
		if (dot) Point(p1.x,p1.y, col);
		else Line(p1.x,p1.y, p2.x,p2.y, col);
		left = true;
		bpts.push(new NPoint(round(p1.x,1), round(p1.y,1)));
	}
	else bpts = bpts.concat(bzl(p1, m12, m123, q, col, dot, num-1));
	// recurse the "right"
	if (num==0||(parseInt(ABS(p4.x-p3.x))==0&&parseInt(ABS(p4.y-p3.y))==0)) {
		if (dot) Point(p4.x,p4.y, col);
		else Line(p4.x,p4.y, p3.x,p3.y, col);
		right = true;
		bpts.push(new NPoint(round(p4.x,1), round(p4.y,1)));
	}
	else bpts = bpts.concat(bzl(q, m234, m34, p4, col, dot, num-1));
	return killseqduppts(bpts);
}

Notes

Disclaimer

References