As3 Function for extrapolating points on a spline curve or Hermite Curve similar to keframe interpolation?
I was hoping someone could help me working out some advanced data reformatting. What I'm hoping for is a function where I can input a value along with an array of key positions like so:
function remap(percentage:Number, keypoints:Array) { ...
The array would start with the minimum and end with the maximum point, with nested key points along the way. For example, I would input something like remap(0.25, [0:0,80:50,100:100] ) and the function would 'imagine' a spline curve graph from (0,0)-(100,100) with a key point of (80,50), then return the y value that is 25% along that graph.
Hopefully that's clear... Any ideas?
The equation for the Hermite Curve is this:
(via Wikipedia)
Where p(t) is the point on the curve at t (percent 0.0 to 1.0)
- p0 is the first control point
- m0 is the first anchor point
- p1 is the second control point
- m1 is the second anchor point
So, the equation in ActionScript 3.0 would be something like this:
/*
* Computes x,y values for a given traversal of a Hermite Curve
* @param t:Number - a normalized value (0.0 to 1.0) describing path traversal
* @param points:Array - an array contining the 4 points describing the curve (P0,T0,P1,T1 - always in this order)
* Anchor points are relative to they're control points
*/
private function hermite(t:Number,points:Array):Point{
var result:Point = new Point();
result.x = (2 * Math.pow(t,3) - 3 * t * t + 1) * points[0].x+
(Math.pow(t,3) - 2 * t * t + t) * points[1].x +
(- 2 * Math.pow(t,3) + 3*t*t) * points[2].x +
( Math.pow(t,3) - t*t) * points[3].x;
result.y = (2 * Math.pow(t,3) - 3 * t * t + 1) * points[0].y+
(Math.pow(t,3) - 2 * t * t + t) * points[1].y +
(- 2 * Math.pow(t,3) + 3*t*t) * points[2].y +
( Math.pow(t,3) - t*t) * points[3].y;
return result;
}
Notice the equation is used twice: once for each component/dimension of a point: x,y in this case.
Here's a basic demo:
/**
* Copyright George.Profenza ( http://wonderfl.net/user/George.Profenza )
* MIT License ( http://www.opensource.org/licenses/mit-license.php )
* Downloaded from: http://wonderfl.net/c/pTgv
*/
package {
import flash.display.Sprite;
import flash.events.Event;
import flash.events.MouseEvent;
import flash.geom.Point;
/**
* @author George Profenza
*/
public class BasicHermite extends Sprite {
private var percent:Number = 0;
private var P0:Point = new Point(10,90);//1st control pt
private var T0:Point = new Point(300,200);//1st anchor pt - NOTE! The anchors are relative to the controls
private var P1:Point = new Point(400,90);//2nd control pt
private var T1:Point = new Point(-100,400);//2nd control pt
private var points:Array = [P0,T0,P1,T1];
private var pointAtPercent:Point;
public function BasicHermite() {
init();
}
private function init():void{
stage.doubleClickEnabled = true;
stage.addEventListener(MouseEvent.DOUBLE_CLICK, reset);
reset();
}
private function reset(event : MouseEvent = null) : void {
P1.x = 200 + Math.random() * 200;//randomize a wee bit
T1.x = Math.random() * 200 - 100;
graphics.clear();
percent = 0;
this.addEventListener(Event.ENTER_FRAME, draw);
}
private function draw(event : Event) : void {
pointAtPercent = hermite(percent, points);//compute point
if(percent == 0) graphics.moveTo(pointAtPercent.x,pointAtPercent.y);//draw
graphics.lineStyle(5,0x009900,percent);
graphics.lineTo(pointAtPercent.x,pointAtPercent.y);
percent += .015;//update percentage of traversal along curve
if(percent >= 1) removeEventListener(Event.ENTER_FRAME, draw);//done
}
/*
* Computes x,y values for a given traversal of a Hermite Curve
* @param t:Number - a normalized value (0.0 to 1.0) describing path traversal
* @param points:Array - an array contining the 4 points describing the curve (P0,T0,P1,T1 - always in this order)
* Anchor points are relative to they're control points
*/
private function hermite(t:Number,points:Array):Point{
var result:Point = new Point();
result.x = (2 * Math.pow(t,3) - 3 * t * t + 1) * points[0].x+
(Math.pow(t,3) - 2 * t * t + t) * points[1].x +
(- 2 * Math.pow(t,3) + 3*t*t) * points[2].x +
( Math.pow(t,3) - t*t) * points[3].x;
result.y = (2 * Math.pow(t,3) - 3 * t * t + 1) * points[0].y+
(Math.pow(t,3) - 2 * t * t + t) * points[1].y +
(- 2 * Math.pow(t,3) + 3*t*t) * points[2].y +
( Math.pow(t,3) - t*t) * points[3].y;
return result;
}
}
}
Still, I am a bit concerned because you're example mentions 3 points (2 control points and one anchor point).
Cubic Curves(Hermite/Catmull-Rom/etc.) have 2 control points and 2 anchor points (equations at power of 3 - cubic)
If you only need one control point, you need to use a Quadratic Curve:
(Image from Adobe Actionscript 3 Documentation)
Cubic Curve:
Quadratic Curve:
(Animations from Wikipedia)
The Quadratic Equation is this:
Which would translate to:
private function quad(t:Number,p:Array):Point{
var result:Point = new Point();
var oneMinusTSq:Number = (1-t) * (1-t);
var TSq:Number = t*t;
result.x = oneMinusTSq*p[0].x+2*(1-t)*t*p[1].x+TSq*p[2].x;
result.y = oneMinusTSq*p[0].y+2*(1-t)*t*p[1].y+TSq*p[2].y;
return result;
}
And a bit of test code:
package {
import flash.display.Sprite;
import flash.events.Event;
import flash.events.MouseEvent;
import flash.geom.Point;
/**
* @author george
*/
public class BasicQuad extends Sprite {
private var p0:Point = new Point(0,0);
private var p1:Point = new Point(80,50);
private var p2:Point = new Point(100,100);
private var pts:Array = [p0,p1,p2];
private var t:Number = 0;
private var pt : Point;
public function BasicQuad() {
init();
}
private function init():void{
stage.doubleClickEnabled = true;
stage.addEventListener(MouseEvent.DOUBLE_CLICK, reset);
reset();
}
private function reset(event : MouseEvent = null) : void {
graphics.clear();
graphics.lineStyle(3,0x009900,.5);
t = 0;
this.addEventListener(Event.ENTER_FRAME, draw);
}
private function draw(event : Event) : void {
trace(t,pt);
pt = quad(t, pts);
if(t == 0) graphics.moveTo(pt.x,pt.y);//draw
graphics.lineTo(pt.x,pt.y);
t+= 0.015;
if(t >= 1) removeEventListener(Event.ENTER_FRAME, draw);//done
}
private function quad(t:Number,p:Array):Point{
var result:Point = new Point();
var oneMinusTSq:Number = (1-t) * (1-t);
var TSq:Number = t*t;
result.x = oneMinusTSq*p[0].x+2*(1-t)*t*p[1].x+TSq*p[2].x;
result.y = oneMinusTSq*p[0].y+2*(1-t)*t*p[1].y+TSq*p[2].y;
return result;
}
}
}
Also, am not clear what you mean by
advanced data reformatting
The code snippets are the formulas written as code, but there are other ways to compute this.
A quadratic Bézier curve is the path traced by the function B(t), given points P0, P1, and P2,
We need to go from P0 to P1 and from P1 to P2. Since you're looking for a Flash/ActionScript solution, we can take advantage of the Point's interpolate() method. So we interpolate between P0 and P1 to get let's say P01 then from P1 to P2 to get P12 and the interpolation through all 3 points will be the interpolation between P01 and P12:
function quadLerp(t:Number,p:Array):Point {
var p1:Point = Point.interpolate(p[1], p[0], t);
var p2:Point = Point.interpolate(p[2], p[1], t);
return Point.interpolate(p2, p1, t);
}
The code looks a bit backwards from what I wrote above because of how the actionscript interpolation is implemented: "The level of interpolation between the two points. Indicates where the new point will be, along the line between pt1 and pt2. If f=1, pt1 is returned; if f=0, pt2 is returned."
UPDATE
Further confused:
In reference to your question: my example actually mentions 3 control points and 0 anchor points
are you trying to simply get the y value of the current x along a series of lines (multiple points, 0 anchor points...straight lines) ?
Remember I dont need the graph itself - I just need a point on it Simply walk on a straight line graph/jagged line(no curves whatsoever) ?
If, so, you can do something like this:
- Loop through all the points of your path and find the line for the current x value (this will be the line for which the start x position is smaller than the given x and the end x position of the line is larger than the given x position)
- Calculate the ratio between the x distance from the start of the line to the given x and the whole line (end.x-start.x)
- Use this ratio to divide the current line 'height' (difference between end.y and start.y) and offset it by the start.y, taking advantage of similar triangles, according to Thales' Theorem
Here's a quick sketch to illustrate the idea:
Imagine a right angled triangle where the current line is the hypothenuse(ABC). Now imagine a vertical line from your mouse cursor splitting that triangle into two similar triangle(OO'). The small triangle has the same angles as the large one and it's sides are proportional. You use the ratio between AO and AB to divide AC by and obtain the length of OO' (the y position on the line for that x).
Here's the function:
private function getYforX(x:Number,pts:Vector.<Point>):Number{
var numPts:int = pts.length;
for (var i : int = 1; i < numPts; i++) {
if(x > pts[i-1].x && x < pts[i].x) {//find the line on which the cursor lies
t = (x-pts[i-1].x)/(pts[i].x-pts[i-1].x);//ratio between the x distance from the start of the line to mouseX and the whole line (end.x-start.x)
return pts[i-1].y + ((pts[i].y-pts[i-1].y) * t);//Thales similar triangles version, cheaper version of Point.interpolate(pts[i], pts[i-1], t).y;
}
}
return -1;
}
And a quick demo:
package {
import flash.events.*;
import flash.display.*;
import flash.geom.Point;
public class LerpPoints extends Sprite {
private var path:Shape = new Shape();
private var cursor:Shape = new Shape();
private var numPts:int = 11;
private var pts:Vector.<Point> = new Vector.<Point>(numPts,true);
private var t:Number = 0;
public function LerpPoints() {
init();
}
private function init():void{
cursor.graphics.lineStyle(10,0x009900);
cursor.graphics.drawCircle(-3, -3, 3);
cursor.graphics.lineStyle(1,0x000099);
cursor.graphics.moveTo(0, -stage.stageHeight);
cursor.graphics.lineTo(0, stage.stageHeight);
reset();
addChild(path);addChild(cursor);
addEventListener(Event.ENTER_FRAME, update);
stage.addEventListener(MouseEvent.MOUSE_DOWN, reset);
}
private function reset(event:Event = null):void{
path.graphics.clear();
for (var i : int = 0; i < numPts; i++) {
pts[i] = new Point(i*55,Math.random() * 200);//generate points
path.graphics.lineStyle(3,0);
if(i == 0) path.graphics.moveTo(pts[0].x,pts[0].y);//draw path
path.graphics.lineTo(pts[i].x,pts[i].y);
if(i > 0){//right angled triangles
path.graphics.lineStyle(1,0x990000);
path.graphics.lineTo(pts[i-1].x,pts[i].y);
path.graphics.lineTo(pts[i-1].x,pts[i-1].y);
path.graphics.moveTo(pts[i].x,pts[i].y);
}
}
}
private function update(event:Event):void{
cursor.x = mouseX;
cursor.y = getYforX(mouseX, pts);
}
private function getYforX(x:Number,pts:Vector.<Point>):Number{
var numPts:int = pts.length;
for (var i : int = 1; i < numPts; i++) {
if(x > pts[i-1].x && x < pts[i].x) {//find the line on which the cursor lies
t = (x-pts[i-1].x)/(pts[i].x-pts[i-1].x);//ratio between the x distance from the start of the line to mouseX and the whole line (end.x-start.x)
return pts[i-1].y + ((pts[i].y-pts[i-1].y) * t);//Thales similar triangles version, cheaper version of Point.interpolate(pts[i], pts[i-1], t).y;
}
}
return -1;
}
}
}
Note that this works if the x values in your points array are in sorted ascending (e.g. your path goes only left to right)
A dirty hack that comes mind is to loop through the pairs of points and store Y values in a lookup table. The number of loops woud be the 'line detail'
Then again, this confuses me:
just need to to asses an array of points (not just 2) and ideally spline curve them rather than simply joining the dots So you have multiple points, but where does the spline come in, since you mentioned 0 anchor points ?
HTH