Category Archives: graphics algorithms

Slow Line Drawing

By Zevan | March 12, 2009
CLICK HERE TO COPY
Actionscript:
  1. var canvas:BitmapData = Bitmap(addChild(new Bitmap(new BitmapData(400, 400, false, 0x000000)))).bitmapData;
  2.  
  3. function line(x1:Number, y1:Number, x2:Number, y2:Number, res:int=10):void{
  4.     var dx:Number = x2 - x1;
  5.     var dy:Number = y2 - y1;
  6.     var dist:Number = Math.sqrt((dx * dx) + (dy * dy));
  7.     var step:Number = 1 / (dist / res);
  8.     for (var i:Number = 0; i<=1; i+= step){
  9.         // lerp : a  + (b - a) * f
  10.         canvas.setPixel(x1 + dx * i, y1 + dy * i, 0xFFFFFF);
  11.     }
  12. }
  13.  
  14. addEventListener(Event.ENTER_FRAME, onLoop);
  15. function onLoop(evt:Event):void {
  16.    canvas.fillRect(canvas.rect, 0x000000);
  17.   line(100 , 100, mouseX, mouseY,1);
  18.   line(100 + 50, 100, mouseX+ 50, mouseY,5);
  19. }

Yesterday I posted an implementation of the Bresenham Line Algorithm. Today I'm posting a comparatively slow way to draw a line with setPixel(). This snippet uses lerp and the Pythagorean theorem. It works nicely for small numbers of lines, its easy to draw dotted lines with it and its easy to explain. In a real app where you needed to use setPixel() to draw a line you should use one of the fast algorithms like Wu or Bresenham.

I didn't originally write this snippet to use set pixel... a few weeks ago I wrote something very similar to calculate a set of x y coords between two given points. In the program I used it in speed wasn't an issue (as I only needed to run the function one time). I've needed this kind of function many times before in games and small apps...

This was the original:

CLICK HERE TO COPY
Actionscript:
  1. function calculatePoints(x1:Number, y1:Number, x2:Number, y2:Number, res:int=10):Array{
  2.     var points:Array = new Array();
  3.     var dx:Number = x2 - x1;
  4.     var dy:Number = y2 - y1;
  5.     var dist:Number = Math.sqrt((dx * dx) + (dy * dy));
  6.     var step:Number = 1 / (dist / res);
  7.     for (var i:Number = 0; i<=1; i+= step){
  8.         points.push(new Point(x1 + dx * i, y1 + dy * i));
  9.     }
  10.     return points;
  11. }
  12.  
  13. trace(calculatePoints(0,0,100,0,10));
  14. /* outputs:
  15. (x=0, y=0),(x=10, y=0),(x=20, y=0),(x=30.000000000000004, y=0),(x=40, y=0),(x=50, y=0),(x=60, y=0),(x=70, y=0),(x=80, y=0),(x=89.99999999999999, y=0),(x=99.99999999999999, y=0)
  16. */

...and another version to allow you to specify the number of points to calculate rather than the pixel interval at which they should be calculated:

CLICK HERE TO COPY
Actionscript:
  1. function calculatePoints(x1:Number, y1:Number, x2:Number, y2:Number, pointNum:int=10):Array{
  2.     var points:Array = new Array();
  3.     var step:Number = 1 / (pointNum + 1);
  4.     for (var i:Number = 0; i<=1; i+= step){
  5.         points.push(new Point(x1 + (x2 - x1) * i, y1 + (y2 - y1) * i));
  6.     }
  7.     return points;
  8. }
  9.  
  10. trace(calculatePoints(0,30,30,0,1));
  11. /* outputs:
  12. (x=0, y=30),(x=15, y=15),(x=30, y=0)
  13. */

This last version isn't perfect, sometimes the pointNum will be off by 1, I may fix that in a future post.

Also posted in Math, misc, pixel manipulation, setPixel | Tagged , | Leave a comment

Bresenham line

By Zevan | March 11, 2009
CLICK HERE TO COPY
Actionscript:
  1. var canvas:BitmapData = Bitmap(addChild(new Bitmap(new BitmapData(400,400, false, 0x000000)))).bitmapData;
  2.  
  3. drawLine(10,10,100,90, 0xFF0000);
  4. drawLine(100,90,60,80, 0xFF0000);
  5. drawLine(100,90,95,60, 0xFF0000);
  6.    
  7. for (var i:int = 0; i<100; i+=1){
  8.     drawLine(i *4, 100 + i, 200, 390);
  9. }
  10. // code ported from here:
  11. // http://www.edepot.com/linebenchmark.html
  12. function drawLine(x1:int, y1:int, x2:int, y2:int, col:uint = 0xFFFFFF){
  13.     var x:int, y:int;
  14.     var dx:int, dy:int;
  15.     var incx:int , incy:int
  16.     var balance:int;
  17.  
  18.     if (x2>= x1){
  19.         dx = x2 - x1;
  20.         incx = 1;
  21.     }else{
  22.         dx = x1 - x2;
  23.         incx = -1;
  24.     }
  25.  
  26.     if (y2>= y1){
  27.         dy = y2 - y1;
  28.         incy = 1;
  29.     }else{
  30.         dy = y1 - y2;
  31.         incy = -1;
  32.     }
  33.  
  34.     x = x1;
  35.     y = y1;
  36.  
  37.     if (dx>= dy){
  38.         dy <<= 1;
  39.         balance = dy - dx;
  40.         dx <<= 1;
  41.  
  42.         while (x != x2){
  43.             canvas.setPixel(x, y, col);
  44.             if (balance>= 0){
  45.                 y += incy;
  46.                 balance -= dx;
  47.             }
  48.             balance += dy;
  49.             x += incx;
  50.         }
  51.         canvas.setPixel(x, y, col);
  52.     }else{
  53.         dx <<= 1;
  54.         balance = dx - dy;
  55.         dy <<= 1;
  56.  
  57.         while (y != y2){
  58.             canvas.setPixel(x, y, col);
  59.             if (balance>= 0){
  60.                 x += incx;
  61.                 balance -= dy;
  62.             }
  63.             balance += dx;
  64.             y += incy;
  65.         }
  66.         canvas.setPixel(x, y, col);
  67.     }
  68. }

This snippet shows Brensenham's line drawing algorithm. I ported this implementation from here... all the line algorithms in that link are easy to port to actionscript. I've messed with them all at some point.

Tomorrow I'm going to post a super slow line drawing algorithm... so I figured I'd post a fast line drawing algorithm today.

Also posted in BitmapData, setPixel | Tagged , | Leave a comment

(HSV HSB) to RGB

By Zevan | February 16, 2009
CLICK HERE TO COPY
Actionscript:
  1. [SWF(width=720,height=360,backgroundColor=0x000000,frameRate=30)]
  2.  
  3. // ported from here:
  4. //http://www.cs.rit.edu/~ncs/color/t_convert.html
  5.  
  6. function hsv(h:Number, s:Number, v:Number):Array{
  7.     var r:Number, g:Number, b:Number;
  8.     var i:int;
  9.     var f:Number, p:Number, q:Number, t:Number;
  10.      
  11.     if (s == 0){
  12.         r = g = b = v;
  13.         return [Math.round(r * 255), Math.round(g * 255), Math.round(b * 255)];
  14.     }
  15.    
  16.     h /= 60;
  17.     i  = Math.floor(h);
  18.     f = h - i;
  19.     p = v *  (1 - s);
  20.     q = v * (1 - s * f);
  21.     t = v * (1 - s * (1 - f));
  22.    
  23.     switch( i ) {
  24.         case 0:
  25.             r = v;
  26.             g = t;
  27.             b = p;
  28.             break;
  29.         case 1:
  30.             r = q;
  31.             g = v;
  32.             b = p;
  33.             break;
  34.         case 2:
  35.             r = p;
  36.             g = v;
  37.             b = t;
  38.             break;
  39.         case 3:
  40.             r = p;
  41.             g = q;
  42.             b = v;
  43.             break;
  44.         case 4:
  45.             r = t;
  46.             g = p;
  47.             b = v;
  48.             break;
  49.         default:        // case 5:
  50.             r = v;
  51.             g = p;
  52.             b = q;
  53.             break;
  54.     }
  55.     return [Math.round(r * 255), Math.round(g * 255), Math.round(b * 255)];
  56. }
  57.  
  58.  
  59. //
  60. //  -- test it out by drawing a few things
  61. //
  62.  
  63. var canvas:BitmapData = new BitmapData(720, 360, false, 0x000000);
  64.  
  65. addChild(new Bitmap(canvas));
  66.  
  67. canvas.lock();
  68. var size:int = canvas.width * canvas.height;
  69. var xp:int, yp:int, c:Array, i:int;
  70.  
  71. for (i = 0; i<size; i++){
  72.     xp = i % 360;
  73.     yp = i / 360;
  74.     c =  hsv(xp, 1, yp / 360);
  75.     canvas.setPixel(xp, yp, c[0] <<16 | c[1] <<8 | c[2]);
  76. }
  77.  
  78. var dx:Number, dy:Number, dist:Number, ang:Number;
  79.  
  80. for (i = 0; i<size; i++){
  81.     xp = i % 360;
  82.     yp = i / 360;
  83.     dx = xp - 180;
  84.     dy = yp - 180;
  85.     dist = 1 - Math.sqrt((dx * dx) + (dy * dy)) / 360;
  86.     ang = Math.atan2(dy, dx) / Math.PI * 180;
  87.     if (ang <0){
  88.         ang += 360;
  89.     }
  90.     c =  hsv(ang, 1, dist);
  91.     canvas.setPixel(360 + xp, yp, c[0] <<16 | c[1] <<8 | c[2]);
  92. }
  93. canvas.unlock();

This is one of those things I've been meaning to play with for awhile. The above demos a function called hsv() which takes 3 arguments: angle (0-360), saturation(0-1) and value(0-1). The function returns an array of rgb values each with a range of (0-255).

There's some room for optimization here, but for clarity I left as is. Even just playing with HSV (also know as HSB) for a few minutes, I see some interesting potential for dynamically generating color palettes for generative style experiments.

I looked around for the most elegant looking code snippet to port in order to write this... I eventually stumbled upon this great resource.

If you test the above on your timeline it will generate this image:

I usually only post one snippet a day... not sure why I decided to post two today.

Also posted in BitmapData, color, pixel manipulation, setPixel | Tagged , , | 6 Comments

Animate Along Bezier Curve

By Zevan | January 27, 2009
CLICK HERE TO COPY
Actionscript:
  1. var circle:Shape = Shape(addChild(new Shape));
  2. with(circle.graphics) beginFill(0x000000), drawCircle(0,0,5);
  3.  
  4. var bezierPoint:Point = new Point();
  5. function bezier(a:Number, x1:Number, y1:Number, x2:Number, y2:Number, x3:Number, y3:Number):void {
  6.         var b:Number =1-a;
  7.         var pre1:Number=a*a;
  8.         var pre2:Number=2*a*b;
  9.         var pre3:Number=b*b;
  10.         bezierPoint.x = pre1*x1 + pre2*x2  + pre3*x3;
  11.         bezierPoint.y = pre1*y1 + pre2*y2 + pre3*y3;
  12. }
  13.  
  14. var inc:Number = 0;
  15. var theta:Number = 0;
  16.  
  17. addEventListener(Event.ENTER_FRAME, onLoop);
  18. function onLoop(evt:Event):void {
  19.    
  20.      graphics.clear();
  21.      graphics.lineStyle(0,0xFF0000);
  22.      graphics.moveTo(200,200);
  23.      graphics.curveTo(mouseX, mouseY, 400, 200);
  24.  
  25.     theta+= .05;
  26.     inc = .5 + .5*Math.sin(theta);
  27.  
  28.     bezier(inc, 200, 200, mouseX, mouseY, 400, 200);
  29.     circle.x = bezierPoint.x;
  30.     circle.y = bezierPoint.y;
  31. }

The above animates a circle along a quadratic bezier curve. This snippet was written in response to a question spurned by some of the recent bezier posts. I used Math.sin() to animate the circle but you could just as easily use modulus... simply replace lines 25-26 with the following:

CLICK HERE TO COPY
Actionscript:
  1. inc += .03;
  2. inc %= 1;

Also posted in Graphics, bezier, motion | Tagged , | 3 Comments