/////////////////////////////////////////////////////////////////////////
//
// Bezier_lib.as - v1.2 - 19/05/02
// Timothee Groleau
//
// The purpose of this file is mainly to provide a function drawCubicBezier
// for the MovieClip prototype to approximate a cubic Bezier curve
// from the quadratic curveTo of the Flash drawing API
//
// By doing so, several useful functions are created to calculate cubic
// bezier points and derivative. Other Bezier functions can be added to
// the _global.Bezier object, like quadratic or quartic function as necessary.
//
// Also a few functions are added to the Math object to handle 2D line equations
//
/////////////////////////////////////////////////////////////////////////

/////////////////////////////////////////////////////////////////////////
//
// Add a few line functions to the Math object
//
/////////////////////////////////////////////////////////////////////////

// Gets a line equation as two properties (a,b) such that (y = a*x + b) for any x
// or a unique c property such that (x = c) for all y
// The function takes two points as parameter, P0 and P1 containing two properties x and y
Math.getLine = function(P0, P1) {
	var l = {};
	var x0 = P0.x;
	var y0 = P0.y;
	var x1 = P1.x;
	var y1 = P1.y;
	
	if (x0 == x1) {
		if (y0 == y1) {
			// P0 and P1 are same point, return null
			l = null;
		} else {
			// Otherwise, the line is a vertical line
			l.c = x0;
		}
	} else {
		l.a = (y0 - y1) / (x0 - x1);
		l.b = y0 - (l.a * x0);
	}
	
	// returns the line object
	return l;
}
	
// Gets a line equation as two properties (a,b) such that (y = a*x + b) for any x
// or a unique c property such that (x = c) for all y
// The function takes two parameters, a point P0 (x,y) through which the line passes
// and a direction vector v0 (x,y)
Math.getLine2 = function(P0, v0) {
	var l = {};
	var x0 = P0.x;
	var vx0 = v0.x;
	
	if (vx0 == 0) {
		// the line is vertical
		l.c = x0
	} else {
		l.a = v0.y / vx0;
		l.b = P0.y - (l.a * x0);
	}
	
	// returns the line object
	return l;
}
	
// return a point (x,y) that is the intersection of two lines
// a line is defined either by a and b parameters such that (y = a*x + b) for any x
// or a single parameter c such that (x = c) for all y
Math.getLineCross = function(l0, l1) {
	// Make sure both line exists
	if ((l0 == null) || (l1 == null)) return null;

	// define local variables
	var a0 = l0.a;
	var b0 = l0.b;
	var c0 = l0.c;
	var a1 = l1.a;
	var b1 = l1.b;
	var c1 = l1.c;
	var u;

	// checks whether both lines are vertical
	if ((c0 == undefined) && (c1 == undefined)) {

		// lines are not verticals but parallel, intersection does not exist
		if (a0 == a1) return null; 

		// calculate common x value.
		u = (b1 - b0) / (a0 - a1);		
		
		// return the new Point
		return {x: u, y: (a0*u + b0)}

	} else {

		if (c0 != undefined) {
			if (c1 != undefined) {
				// both lines vertical, intersection does not exist
				return null;
			} else {
				// return the point on l1 with x = c0
				return {x: c0, y: (a1*c0 + b1)};
			}

		} else if (c1 != undefined) {
			// no need to test c0 as it was tested above
			// return the point on l0 with x = c1
			return {x: c1, y: (a0*c1 + b0)};
		}
	}
}


// return the distance between two points
Math.distance = function(P0, P1) {
	var dx = P0.x - P1.x;
	var dy = P0.y - P1.y;
	
	return Math.sqrt(dx*dx + dy*dy);
}


// return the middle of a segment define by two points
Math.getMiddle = function(P0, P1) {
	return {x: ((P0.x + P1.x) / 2), y: ((P0.y + P1.y) / 2)};
}


// return a point on a segment [P0, P1] which distance from P0
// is ratio of the length [P0, P1]
Math.getPointOnSegment = function(P0, P1, ratio) {
	return {x: (P0.x + ((P1.x - P0.x) * ratio)), y: (P0.y + ((P1.y - P0.y) * ratio))};
}



/////////////////////////////////////////////////////////////////////////
//
// Create a global Bezier Object to handle the various functions needed
//
/////////////////////////////////////////////////////////////////////////

_global.Bezier = new Object();

// Return the bezier location at t based on the 4 parameters
// c0, c1, c2, c3 are respectively the position of the four bezier controls (1D)
Bezier.getCubicPt = function(c0, c1, c2, c3, t) {
	var ts = t*t;
	var g = 3 * (c1 - c0);
	var b = (3 * (c2 - c1)) - g;
	var a = c3 - c0 - b - g;
	return ( a*ts*t + b*ts + g*t + c0 );
}

// Return the value of the derivative of the cubic bezier at t
// c0, c1, c2, c3 are respectively the position of the four bezier controls (1D)
Bezier.getCubicDerivative = function(c0, c1, c2, c3, t) {
	var g = 3 * (c1 - c0);
	var b = (3 * (c2 - c1)) - g;
	var a = c3 - c0 - b - g;
	return ( 3*a*t*t + 2*b*t + g );
}

// returns a tangent object of a cubic Bezier curve at t
// A tangent object comprises two properties, P and l
// P is a point with two propertiesx and y
// l is a line with two properties a and b
Bezier.getCubicTgt = function(P0, P1, P2, P3, t) {

	// calculates the position of the cubic bezier at t
	var P = {};
	P.x = Bezier.getCubicPt(P0.x, P1.x, P2.x, P3.x, t);
	P.y = Bezier.getCubicPt(P0.y, P1.y, P2.y, P3.y, t);
	
	// calculates the tangent values of the cubic bezier at t
	var V = {};
	V.x = Bezier.getCubicDerivative(P0.x, P1.x, P2.x, P3.x, t);
	V.y = Bezier.getCubicDerivative(P0.y, P1.y, P2.y, P3.y, t);

	// calculates the line equation for the tangent at t
	var l = Math.getLine2(P, V);
	
	// return the Point/Tangent object 
	var o = {};
	o.P = P;
	o.l = l;
	
	return o;
}





/////////////////////////////////////////////////////////////////////////
//
// Draw a cubic Bezier as a Spline approximation
// (Very fast processing, but clearly far from the true cubic bezier)
//
/////////////////////////////////////////////////////////////////////////

// This function draws a approximation of a cubic bezier curve
// It is very fast but does not look quite the real one
MovieClip.prototype.drawCubicBezier_spline = function(P0, P1, P2, P3) {

	// calculates middle point of the two control points segment
	var midP_x = (P1.x + P2.x) / 2;
	var midP_y = (P1.y + P2.y) / 2;
	
	// draw fake cubic bezier curve lines (in two parts)
	this.curveTo(P1.x, P1.y, midP_x, midP_y);
	this.curveTo(P2.x, P2.y, P3.x, P3.y);
}



/////////////////////////////////////////////////////////////////////////
//
// Add a draw cubic bezier curve to the MovieClip prototype
//
/////////////////////////////////////////////////////////////////////////

// this function recursively slice down a cubic Bezier segment to avoid parallel tangents
// the function returns the number of sub segment used to draw the current segment
MovieClip.prototype.sliceCubicBezierSegment = function(P0, P1, P2, P3, u1, u2, Tu1, Tu2, recurs) {

	// prevents infinite recursion (no more than 10 levels)
	// if 10 levels are reached the latest subsegment is 
	// approximated with a line (no quadratic curve). It should be good enough.
	if (recurs > 10) {
		var P = Tu2.P;
		this.lineTo(P.x, P.y);
		return 1;
	}

	// recursion level is OK, process current segment
	var ctrlPt = Math.getLineCross(Tu1.l, Tu2.l);
	var d = 0;
	
	// A control point is considered misplaced if its distance from one of the anchor is greater 
	// than the distance between the two anchors.
	if (	(ctrlPt == null) || 
			(Math.distance(Tu1.P, ctrlPt) > (d = Math.distance(Tu1.P, Tu2.P))) ||
			(Math.distance(Tu2.P, ctrlPt) > d) ) {

		// total for this subsegment starts at 0			
		var tot = 0;

		// If the Control Point is misplaced, slice the segment more
		var uMid = (u1 + u2) / 2;
		var TuMid = Bezier.getCubicTgt(P0, P1, P2, P3, uMid);
		tot += this.sliceCubicBezierSegment(P0, P1, P2, P3, u1, uMid, Tu1, TuMid, recurs+1);
		tot += this.sliceCubicBezierSegment(P0, P1, P2, P3, uMid, u2, TuMid, Tu2, recurs+1);
		
		// return number of sub segments in this segment
		return tot;

	} else {
		// if everything is OK draw curve
		var P = Tu2.P;
		this.curveTo(ctrlPt.x, ctrlPt.y, P.x, P.y);
		return 1;
	}
}

// Draws a cubic bezier point approximation, P0 and P3 are the anchor points
// P1 and P2 are the handle points
// nSegments denotes how many quadratic bezier segments will be used to
// approximate the cubic bezier (default is 4);
MovieClip.prototype.drawCubicBezier = function(P0, P1, P2, P3, nSegment) {
	
	//define the local variables
	var curP; // holds the current Point
	var nextP; // holds the next Point
	var ctrlP; // holds the current control Point
	var curT; // holds the current Tangent object
	var nextT; // holds the next Tangent object
	var total = 0; // holds the number of slices used
	
	// make sure nSegment is within range (also create a default in the process)
	if (nSegment < 2) nSegment = 4;

	// get the time Step from nSegment
	var tStep = 1 / nSegment;
	
	// get the first tangent Object
	curT = new Object();
	curT.P = P0;
	curT.l = Math.getLine(P0, P1);
	
	// move to the first point
	// this.moveTo(P0.x, P0.y);

	// get tangent Objects for all intermediate segments and draw the segments
	for (var i=1; i<=nSegment; i++) {

		// get Tangent Object for next point
		nextT = Bezier.getCubicTgt(P0, P1, P2, P3, i*tStep);

		// get segment data for the current segment
		total += this.sliceCubicBezierSegment(P0, P1, P2, P3, (i-1)*tStep, i*tStep, curT, nextT, 0)
		
		// prepare for next round
		curT = nextT;
	}
	
	return total;
}



/////////////////////////////////////////////////////////////////////////
//
// Add a drawCubicBezier2 to the movieClip prototype based on a MidPoint 
// simplified version of the midPoint algorithm by Helen Triolo
//
/////////////////////////////////////////////////////////////////////////

// This function will trace a cubic approximation of the cubic Bezier
// It will calculate a serie of [control point/Destination point] which 
// will be used to draw quadratic Bezier starting from P0
MovieClip.prototype.drawCubicBezier2 = function(P0, P1, P2, P3) {

	// calculates the useful base points
	var PA = Math.getPointOnSegment(P0, P1, 3/4);
	var PB = Math.getPointOnSegment(P3, P2, 3/4);
	
	// get 1/16 of the [P3, P0] segment
	var dx = (P3.x - P0.x)/16;
	var dy = (P3.y - P0.y)/16;
	
	// calculates control point 1
	var Pc_1 = Math.getPointOnSegment(P0, P1, 3/8);
	
	// calculates control point 2
	var Pc_2 = Math.getPointOnSegment(PA, PB, 3/8);
	Pc_2.x -= dx;
	Pc_2.y -= dy;
	
	// calculates control point 3
	var Pc_3 = Math.getPointOnSegment(PB, PA, 3/8);
	Pc_3.x += dx;
	Pc_3.y += dy;
	
	// calculates control point 4
	var Pc_4 = Math.getPointOnSegment(P3, P2, 3/8);
	
	// calculates the 3 anchor points
	var Pa_1 = Math.getMiddle(Pc_1, Pc_2);
	var Pa_2 = Math.getMiddle(PA, PB);
	var Pa_3 = Math.getMiddle(Pc_3, Pc_4);

	// draw the four quadratic subsegments
	this.curveTo(Pc_1.x, Pc_1.y, Pa_1.x, Pa_1.y);
	this.curveTo(Pc_2.x, Pc_2.y, Pa_2.x, Pa_2.y);
	this.curveTo(Pc_3.x, Pc_3.y, Pa_3.x, Pa_3.y);
	this.curveTo(Pc_4.x, Pc_4.y, P3.x, P3.y);
}

// hide and protect the two new functions in the MovieClip prototype
ASSetPropFlags(MovieClip.prototype, ["drawCubicBezier_spline", "drawCubicBezier", "sliceCubicBezierSegment", "drawCubicBezier2"], 7);