Difference between revisions of "Script:Bézier curves"

Revision as of 20:37, 16 March 2013

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

I decided to make this function because (at the time) Sphere had no built-in curve function (which would be a whole lot quicker than the JavaScript method this code presents). The original forum post also contains code to not only draw a solid or dotted line made of an image, but also draw a solid or dotted curve made of an image.

Disclaimer

This code, as well as the linked ImageBezier code, is provided for free use, especially in the creation of Sphere applets. If you can translate this code to work in web Javascript, I'd definitely like to know about it! I'm quite sure these functions can be used for more than just line drawing and graphing. One thing I can think of is the dynamic generation of HP values in a level-up curve...

I, Alex Rosario aka NeoLogiX, reserve the right to modify any and all code submitted with regards to these Bézier curve functions for any and all reasons whatsoever, though there is a 99.9999999% chance I will credit you for submitting the function and/or optimization. You are free to edit and/or improve these functions as you see fit, as long as you let me know you're doing it. I would love to hear about what these curves can be used for in your games!

NOTE: During the original development of this script, there was an unofficial build of Sphere that contains built-in functions for drawing Bézier curve primitives. These functions were eventually included in a later official build of Sphere. If you have access to these built-in functions please use those instead of the scripted Bézier line functions, though there does not yet exist a built-in equivalent to ImageBezier. - Neo

References

• Point()
• Line()
• Math.abs()
• (original Spherical Forums post regarding Bézier curves lost to the sands of time ;_; )