Category Archives: Math

Low Precision Sine and Cosine

By Zevan | March 21, 2009

Actionscript:

var t:Number=0, cos:Number, sin:Number;
 
var canvas:BitmapData = new BitmapData(400,400,false, 0x000000);
addChild(new Bitmap(canvas));
 
var shape:Shape = new Shape();
with(shape.graphics) beginFill(0x568338, .2), drawCircle(0,0,10);
 
addEventListener(Event.ENTER_FRAME, onLoop);
function onLoop(evt:Event):void {
    
         t += .1;
        // -- low precision sine/cosine
        //always wrap input angle to -PI..PI
        if (t <-3.14159265){
            t += 6.28318531;
        }else{
        if (t>  3.14159265)
            t -= 6.28318531;
        }
        
        //compute sine
        if (t <0){
            sin = 1.27323954 * t + .405284735 * t * t;
        }else{
            sin = 1.27323954 * t - 0.405284735 * t * t;
        }
        
        //compute cosine: sin(t + PI/2) = cos(t)
        t += 1.57079632;
        if (t>  3.14159265){
            t -= 6.28318531;
        }
        
        if (t <0){
            cos = 1.27323954 * t + 0.405284735 * t * t
        }else{
            cos = 1.27323954 * t - 0.405284735 * t * t;
        }
        t -= 1.57079632;
        
        // move the shape
        shape.x = 200 + 100 * cos;
        shape.y = 200 + 100 * sin;
        
        // draw to the canvas
        canvas.draw(shape, shape.transform.matrix);
}

This snippet draws a circle using low precision sine and cosine... you'll notice that its not a perfect looking circle:

Back in January I saw this blog post by Michael Baczynski over at http://lab.polygonal.de/. The blog post describes a technique for fast sine and cosine approximation - (I highly recommend giving it a read - very fun stuff).

It's worth noting that there is a higher precision sine and cosine that will likely draw a better looking circle but will be about half as fast. According to the original post ... the low precision technique is approximately 14x faster than using Math.cos()/Math.sin().

There some other really great posts over at polygonal go check them out.

Also posted in motion | Tagged actionscrpt, flash | 2 Comments

Bezier Intersections (not a snippet)

By Zevan | March 15, 2009

CLICK HERE TO COPY

Actionscript:

var resolution:Number = .03;
var pointNum:int = Math.ceil(1 / resolution);
 
var bezA:Array = new Array();
populateArray(bezA);
var a:Sprite = dot(100, 200);
var b:Sprite = dot(200, 100);
var c:Sprite = dot(300, 200);
 
var bezB:Array = new Array();
populateArray(bezB);
var d:Sprite = dot(300, 100, 0xCCCC00);
var e:Sprite = dot(120, 130, 0xCCCC00);
var f:Sprite = dot(200, 300, 0xCCCC00);
 
addEventListener(Event.ENTER_FRAME, onLoop);
function onLoop(evt:Event):void {
      with(graphics){
          clear();
          lineStyle(0, 0x000000);
       
          // calc and draw bezier points
          drawBezier(bezA, a, b, c);
          drawBezier(bezB, d, e, f);
          
          // calc collisions
          var intersections:Array = calculateIntersection(bezA, bezB);
          
           // draw collisions
           beginFill(0xFF0000);
           if (intersections.length> 0){
                for (var i:int = 0; i<intersections.length; i++){
                    drawCircle(intersections[i].x, intersections[i].y, 3);
                }
           }
           endFill();
     }
}
 
function populateArray(a:Array):void {
    for (var i:int = 0; i<pointNum; i++){
        a.push(new Point());
    }
}
 
function drawBezier(bez:Array, a:Sprite, b:Sprite, c:Sprite):void{
     with(graphics){
         bezier(bez, a.x, a.y, b.x, b.y, c.x, c.y);
         var leng:Number = bez.length; 
         moveTo(bez[0].x, bez[0].y);
         for (var i:int = 1; i<leng; i++){
             lineTo(bez[i].x, bez[i].y);
         }
     }
}
 
function bezier(bez:Array, x1:Number, y1:Number, x2:Number, y2:Number, x3:Number, y3:Number):void {
            var b:Number, a2:Number, ab2:Number, b2:Number;
            var pnt:Point;
            var inc:int = 0;
            for (var a:Number = 0; a <=1; a+=resolution) {
                b= 1 - a;
                a2 = a * a;
                ab2 = a * b * 2;
                b2 = b * b;
                pnt = bez[inc];
                pnt.x = a2 * x1 + ab2 * x2  + b2 * x3;
                pnt.y = a2 * y1 + ab2 * y2 + b2 * y3;      
                inc++;
            }
}
 
function calculateIntersection(bezA:Array, bezB:Array):Array {
    var intersections:Array = new Array();
    var ip:Point;
    var aLength:int = bezA.length;
    var bLength:int = bezB.length;
    var p1:Point, p2:Point, p3:Point, p4:Point;
    
    // compare all line segments and check for 
    // intersections
    for (var i:int = 1; i<aLength; i++){
        p1 = bezA[i - 1];
        p2 = bezA[i];
        for (var j:int = 1; j<bLength; j++){
            p3 = bezB[j - 1];
            p4 = bezB[j];
            ip = intersection(p1, p2, p3, p4);
            if (ip){
                intersections.push(ip.clone());
            }
        }
    }
    return intersections;
}
 
var ip:Point = new Point();
 
function intersection(p1:Point, p2:Point, p3:Point, p4:Point):Point {
     
    var nx:Number, ny:Number, dn:Number;
    var x4_x3:Number = p4.x - p3.x;
    var pre2:Number = p4.y - p3.y;
    var pre3:Number = p2.x - p1.x;
    var pre4:Number = p2.y - p1.y;
    var pre5:Number = p1.y - p3.y;
    var pre6:Number = p1.x - p3.x;
    
    nx = x4_x3 * pre5 - pre2 * pre6;
    ny = pre3 * pre5 - pre4 * pre6;
    dn = pre2 * pre3 - x4_x3 * pre4;
    
    if (dn == 0){
        return null
    }
    nx /= dn;
    ny /= dn;
    // has intersection
    if(nx>= 0 && nx <= 1 && ny>= 0 && ny <= 1){
        ny = p1.y + nx * pre4;
        nx = p1.x + nx * pre3;
        ip.x = nx;
        ip.y = ny;
    }else{
         return null;
    }
    return ip
}
 
// draggable dot
function dot(xp:Number, yp:Number, col:uint = 0x507399, noDrag:Boolean = false):Sprite {
    var s:Sprite = Sprite(addChild(new Sprite));
    s.x = xp;
    s.y = yp;
    with(s.graphics) beginFill(col), drawCircle(0,0,5);
    if (!noDrag){
        s.buttonMode = true;
       s.addEventListener(MouseEvent.MOUSE_DOWN, onDrag);
    }
    return s;
}
function onDrag(evt:MouseEvent):void {
    evt.currentTarget.startDrag()
}
 
stage.addEventListener(MouseEvent.MOUSE_UP, onUp);
function onUp(evt:MouseEvent):void{
    stopDrag();
}

This is not a snippet, but it uses some functions that could be considered snippets on their own. Take a look at the swf here:

Bezier Intersection Demo

This demo show a brute force method for getting the coordinates of all intersections between two given quadtratic bezier curves. The approach is pretty simple, each bezier is actually made up of a series of line segments. The resolution variable determines how many line segments make up one bezier curve. By default I use a resolution of 0.03 (~34 lines)... the higher the resolution decimal value, the fewer the number of line segments. I then use a slight variation on yesterdays line segment intersection function to test all existing line segments for intersections.

This is a brute for approach with lots of room for improvement. But in the scenario that you only need to check a few bezier curves for intersection this approach works quite nicely. I don't recommend this approach if your trying to create a complex vector drawing tool with boolean vector operations etc...

It's easy to get an idea of the different approaches to this problem with a little googling. One example I found is from Graphics Gems:

http://tog.acm.org/GraphicsGems/gemsiv/curve_isect/

it's been awhile, but I believe this website also contains information related to this topic:

http://algorithmist.wordpress.com/

Also posted in bezier | Tagged actionscript, flash | Leave a comment

Line Intersection Part 2 (optimized)

By Zevan | March 14, 2009

CLICK HERE TO COPY

Actionscript:

// optimized line to line intersection test:
// from wikipedia: http://en.wikipedia.org/wiki/Line-line_intersection
// and http://local.wasp.uwa.edu.au/~pbourke/geometry/lineline2d/
var ip:Point = new Point();
 
function intersection(p1:Sprite, p2:Sprite, p3:Sprite, p4:Sprite):Point {
    var nx:Number, ny:Number, dn:Number;
    var x4_x3:Number = p4.x - p3.x;
    var y4_y3:Number = p4.y - p3.y;
    var x2_x1:Number = p2.x - p1.x;
    var y2_y1:Number = p2.y - p1.y;
    var x1_x3:Number = p1.x - p3.x;
    var y1_y3:Number = p1.y - p3.y;
    
    nx = x4_x3 * y1_y3 - y4_y3 * x1_x3;
    ny = x2_x1 * y1_y3 - y2_y1 * x1_x3;
    dn = y4_y3 * x2_x1 - x4_x3 * y2_y1;
    
    nx /= dn;
    ny /= dn;
    
    // has intersection
    if(nx>= 0 && nx <= 1 && ny>= 0 && ny <= 1){
        ny = p1.y + nx * y2_y1;
        nx = p1.x + nx * x2_x1;
        ip.x = nx;
        ip.y = ny;
    }else{
        // no intersection
        ip.x = ip.y = -1000;
    }
    return ip
}
 
 
//
// test out the function:
//
 
stage.frameRate = 30;
var a:Sprite = dot();
a.x = a.y = 100;
 
var b:Sprite = dot();
b.x = b.y = 200;
 
var c:Sprite = dot();
c.x = 200
c.y = 100;
 
var d:Sprite = dot();
d.x = 100
d.y = 200;
 
var inter:Sprite = dot(0xFF0000,true);
 
addEventListener(Event.ENTER_FRAME, onLoop);
function onLoop(evt:Event):void {
    var p:Point = intersection(a, b, c, d);
    inter.x = p.x;
    inter.y = p.y
    
    with(graphics){
        clear();
        lineStyle(0,0x000000);
        moveTo(a.x, a.y);
        lineTo(b.x, b.y);
        moveTo(c.x, c.y);
        lineTo(d.x,d.y);
    }
}
 
// draggable dot
function dot(col:uint = 0x507399, noDrag:Boolean = false):Sprite {
    var s:Sprite = Sprite(addChild(new Sprite));
    with(s.graphics) beginFill(col), drawCircle(0,0,5);
    if (!noDrag){
        s.buttonMode = true;
       s.addEventListener(MouseEvent.MOUSE_DOWN, onDrag);
    }
    return s;
}
function onDrag(evt:MouseEvent):void {
    evt.currentTarget.startDrag()
}
 
stage.addEventListener(MouseEvent.MOUSE_UP, onUp);
function onUp(evt:MouseEvent):void{
    stopDrag();
}

This is a significantly optimized version of yesterdays post. The function intersection() takes four sprites as its arguments. The four arguments could be considered starting points and ending points for two line segments.

The bottleneck in yesterdays post looked something like this;

nx = (p1.x * p2.y - p1.y * p2.x) * (p3.x - p4.x) - (p1.x - p2.x) * (p3.x * p4.y - p3.y * p4.x);
dn = (p1.x - p2.x) * (p3.y - p4.y) - (p1.y - p2.y) * (p3.x - p4.x);
ny = (p1.x * p2.y - p1.y * p2.x) * (p3.y - p4.y) - (p1.y - p2.y) * (p3.x * p4.y - p3.y * p4.x);
return new Point(nx /dn, ny / dn);

nx and ny are the numerators for two fractions both with dn as their denominator.... after taking a look at this page:

http://local.wasp.uwa.edu.au/~pbourke/geometry/lineline2d/

We can simplify things a bit before we start wrapping repetitive math operations up in variables:

CLICK HERE TO COPY

Actionscript:

nx = (p4.x - p3.x) * (p1.y - p3.y) - (p4.y - p3.y) * (p1.x - p3.x);
// ny = (p2.x - p1.x) * (p1.y - p3.y) - (p2.y - p1.y) * (p1.x - p3.x);
dn = (p4.y - p3.y) * (p2.x - p1.x) - (p4.x - p3.x) * (p2.y - p1.y);
nx /= dn;
// ny /= dn
ny = p1.y + nx * (p2.y - p1.y);
nx = p1.x + nx * (p2.x - p1.x);
return new Point(nx, ny);

It's important to note here that if we didn't intend to calculate line segments we could exclude the initial calculation of ny.

At this point we're ready to get rid of duplicate math operations by wrapping them in variables. In this case this only includes subtraction:

CLICK HERE TO COPY

Actionscript:

var x4_x3:Number=p4.x-p3.x;
var y4_y3:Number=p4.y-p3.y;
var x2_x1:Number=p2.x-p1.x;
var y2_y1:Number=p2.y-p1.y;
var x1_x3:Number=p1.x-p3.x;
var y1_y3:Number=p1.y-p3.y;
 
nx=x4_x3*y1_y3-y4_y3*x1_x3;
ny=x2_x1*y1_y3-y2_y1*x1_x3;
dn=y4_y3*x2_x1-x4_x3*y2_y1;
 
nx/=dn;
ny/=dn;
 
ny=p1.y+nx*y2_y1;
nx=p1.x+nx*x2_x1;
 
return new Point(nx, ny);

After wrapping repetitive math into variables the only optimization left to be made is related to the instantiation of a new Point(). Instantiation of objects is an expensive process, so it's better to define the point once outside of the intersection() function definition.

In the end our function looks like this:

CLICK HERE TO COPY

Actionscript:

var ip:Point = new Point();
 
function intersection(p1:Sprite, p2:Sprite, p3:Sprite, p4:Sprite):Point {
    var nx:Number, ny:Number, dn:Number;
    var x4_x3:Number = p4.x - p3.x;
    var pre2:Number = p4.y - p3.y;
    var pre3:Number = p2.x - p1.x;
    var pre4:Number = p2.y - p1.y;
    var pre5:Number = p1.y - p3.y;
    var pre6:Number = p1.x - p3.x;
    nx = x4_x3 * pre5 - pre2 * pre6;
    ny = pre3 * pre5 - pre4 * pre6;
    dn = pre2 * pre3 - x4_x3 * pre4;
    nx /= dn;
    ny /= dn;
    // has intersection
    if(nx>= 0 && nx <= 1 && ny>= 0 && ny <= 1){
        ny = p1.y + nx * pre4;
        nx = p1.x + nx * pre3;
        ip.x = nx;
        ip.y = ny;
    }else{
        // no intersection
        ip.x = ip.y = -1000;
    }
    return ip
}

The final version contains a conditional that checks the end values of nx and ny, if they are between 0 and 1 then we know that there is an intersection between the segments.

Note: Optimized code usually breaks some best practices... as best practices are usually geared toward code flexibility and readability... and not speed.

Also posted in misc | Tagged actionscript, flash | Leave a comment

Line Intersection Part 1 (unoptimized)

By Zevan | March 13, 2009

CLICK HERE TO COPY

Actionscript:

// completely unoptimized line to line intersection test:
// from wikipedia: http://en.wikipedia.org/wiki/Line-line_intersection
function intersection(p1:Sprite, p2:Sprite, p3:Sprite, p4:Sprite):Point {
    var nx:Number, ny:Number, dn:Number;
    nx = (p1.x * p2.y - p1.y * p2.x) * (p3.x - p4.x) - (p1.x - p2.x) * (p3.x * p4.y - p3.y * p4.x);
    dn = (p1.x - p2.x) * (p3.y - p4.y) - (p1.y - p2.y) * (p3.x - p4.x);
    ny = (p1.x * p2.y - p1.y * p2.x) * (p3.y - p4.y) - (p1.y - p2.y) * (p3.x * p4.y - p3.y * p4.x);
    return new Point(nx / dn, ny / dn);
}
 
//
// test out the function:
//
 
stage.frameRate = 30;
var a:Sprite = dot();
a.x = a.y = 100;
 
var b:Sprite = dot();
b.x = b.y = 200;
 
var c:Sprite = dot();
c.x = 200
c.y = 100;
 
var d:Sprite = dot();
d.x = 100
d.y = 200;
 
var inter:Sprite = dot(0xFF0000,true);
 
addEventListener(Event.ENTER_FRAME, onLoop);
function onLoop(evt:Event):void {
    var p:Point = intersection(a, b, c, d);
    inter.x = p.x;
    inter.y = p.y
    
    with(graphics){
        clear();
        lineStyle(0,0x000000);
        moveTo(a.x, a.y);
        lineTo(b.x, b.y);
        moveTo(c.x, c.y);
        lineTo(d.x,d.y);
    }
}
 
// draggable dot
function dot(col:uint = 0x507399, noDrag:Boolean = false):Sprite {
    var s:Sprite = Sprite(addChild(new Sprite));
    with(s.graphics) beginFill(col), drawCircle(0,0,5);
    if (!noDrag){
        s.buttonMode = true;
       s.addEventListener(MouseEvent.MOUSE_DOWN, onDrag);
    }
    return s;
}
function onDrag(evt:MouseEvent):void {
    evt.currentTarget.startDrag()
}
 
stage.addEventListener(MouseEvent.MOUSE_UP, onUp);
function onUp(evt:MouseEvent):void{
    stopDrag();
}

This snippet shows the first step toward a usable line to line intersection test. While this demo is fully functional, there is some room for optimization within the intersection() function itself...

From Equations to Code

When I go directly from an equation to code I like to try to make the code resemble the equation... test to make sure it works and then add optimizations. I do this to keep things clear for myself and also so that I have a step by step process to show my students.

The optimizations and additional features that I'll add to this function tomorrow will make it look very different from the original equation from wikipedia. Some things that I'll do:

1) tweak the equation to use fewer operators (it has 12 multiplications right now)
2) wrap duplicate mathmatical operations in variables
3) add the ability to test for line segments rather than infinite lines
4) move any object instantiation outside the function
etc...

Also posted in misc | Tagged actionscript, flash | Leave a comment

Search
ActionSnippet is on Twitter
Pages
- about
- all posts
- QuickBox2D
- warning
Recent Posts
Categories
- 3D
- Announcements
- arrays
- associative arrays
- bezier
- binary
- BitmapData
- Box2D
- color
- Data Structures
- Dictionary
- display list
- DisplayObject
- dynamic
- es6
- Events
- external data
- functions
- glsl
- Graphics
- graphics algorithms
- html5
- instantiation
- javascript
- keys
- links
- Loader
- Math
- matrix
- misc
- motion
- MovieClip
- Number
- Object
- one-liners
- OOP
- Operators
- pixel manipulation
- projects
- properties
- QuickBox2D
- Quiz
- random
- return values
- setPixel
- sortOn
- string manipulation
- strings
- svg
- TextField
- timeline
- UI
- Uncategorized
- variables
- Vector
- Video
- webgl
- XML
Archives
- November 2024
- July 2024
- June 2024
- December 2018
- October 2018
- August 2018
- July 2018
- July 2012
- June 2012
- August 2011
- January 2011
- July 2010
- June 2010
- May 2010
- April 2010
- March 2010
- February 2010
- January 2010
- December 2009
- November 2009
- October 2009
- September 2009
- August 2009
- July 2009
- June 2009
- May 2009
- April 2009
- March 2009
- February 2009
- January 2009
- December 2008
- November 2008
- October 2008
- 0

RSS Feeds
- All posts
- All comments

Category Archives: Math

Low Precision Sine and Cosine

Bezier Intersections (not a snippet)

Line Intersection Part 2 (optimized)

Line Intersection Part 1 (unoptimized)

From Equations to Code

Search

Pages

Recent Posts

Categories

Archives

RSS Feeds