[Flash 10+]

September 2014

Marching squares experiment

An implementation of marching squares algorithm.


With this configuration the search is performed counter-clockwise

note : You don’t have to handle state 0 (no pix) and 15 (4 pix) if you start searching on an non-alpha pixel that lie on the perimeter.

package utils
{
import flash.display.BitmapData;
import flash.geom.Point;

public final class MarchingSquares
{
// --
static public function bitmap(data:BitmapData, initialX:int, initialY:int):Vector.
{
const E:Point = new Point(1, 0);
const N:Point = new Point(0, -1);
const W:Point = new Point(-1, 0);
const S:Point = new Point(0, 1);

// to inline
function value(x:int, y:int):int
{
var sum:int = 0;
if (data.getPixel32(x - 1, y - 1) >> 24)
sum |= 1;
if (data.getPixel32(x, y - 1) >> 24)
sum |= 2;
if (data.getPixel32(x - 1, y) >> 24)
sum |= 4;
if (data.getPixel32(x, y) >> 24)
sum |= 8;
return sum;
}

var initialValue:int = value(initialX, initialY);
if (initialValue == 0 || initialValue == 15)
{
throw new ArgumentError("(" + initialX + ", " + initialY + ") point do not lie on the perimeter.");
}

var perimeter:Vector. = new Vector.();

var x:int = initialX;
var y:int = initialY;
var previous:Point = null;

var direction:Point;
do
{
switch (value(x, y))
{
case 1:
direction = N;
break;
case 2:
direction = E;
break;
case 3:
direction = E;
break;
case 4:
direction = W;
break;
case 5:
direction = N;
break;
case 6:
direction = previous == N ? W : E;
break;
case 7:
direction = E;
break;
case 8:
direction = S;
break;
case 9:
direction = previous == E ? N : S;
break;
case 10:
direction = S;
break;
case 11:
direction = S;
break;
case 12:
direction = W;
break;
case 13:
direction = N;
break;
case 14:
direction = W;
break;
default:
throw new Error("MarchingSquares::perimeter::default");
break;
}
x += direction.x;
y += direction.y;
perimeter.push(new Point(x, y));
previous = direction;
} while (x != initialX || y != initialY);

return perimeter;
}

}
}

To be sure to stay on the permimeter I give the first point using this method

function getFirstNonTransparentPixel(bmd:BitmapData, startX:uint=0):void
{
var hit_rect:Rectangle = new Rectangle(0, 0, bmd.width, 1);
var p:Point = new Point();

for ( hit_rect.y = start_y; hit_rect.y < bmd.height; hit_rect.y++ )
{
if (bmd.hitTest(p, 0x01, hit_rect))
{
var hit_bmd:BitmapData = new BitmapData(bmd.width, 1, true, 0);
hit_bmd.copyPixels(bmd, hit_rect, p);

return hit_rect.topLeft.add(hit_bmd.getColorBoundsRect(0xFF000000, 0, false).topLeft);

}
}
return null;
}

Then marching squares algorithm run on each frame of the animation.

* * *
Personal achievement :)
I can reproduce one of the old school “State of the art” effect