[Tutorial][AS3] Delaunay triangulation effect

[Flash 9+]

September 2016

Delaunay triangulation effect

Original image

Result

Click on the image below (Flash) to generate new variations

The idea comes from overwatch title screen

Test project

package
{
import flash.display.Bitmap;
import flash.display.BitmapData;
import flash.display.BlendMode;
import flash.display.Shape;
import flash.display.Sprite;
import flash.events.Event;
import flash.events.MouseEvent;
import flash.geom.ColorTransform;
import flash.geom.Point;
import flash.net.LocalConnection;

public class Main extends Sprite
{
[Embed(source = "asset/map960.png")]
private const MapClass:Class;

private const WIDTH:uint = 960;
private const HEIGHT:uint = 477;
private var result:Bitmap;

public function Main()
{
if (stage) init();
else addEventListener(Event.ADDED_TO_STAGE, init);
}

private function init(e:Event = null):void
{
removeEventListener(Event.ADDED_TO_STAGE, init);

// entry point
stage.addEventListener(MouseEvent.CLICK, onClickStage);

onClickStage();
}

private function onClickStage(e:MouseEvent = null):void
{
if (result)
{
removeChild(result);
result.bitmapData.dispose;
result = null;

forceGC();
}
result = DelaunayEffect(new MapClass() as Bitmap);
addChild(result);
}

/**
* return the bitmap with a new effect applyied on it
* @param	pBitmap
* @return
*/
private function DelaunayEffect(pBitmap:Bitmap, nbPoints:int = 96):Bitmap
{
// create the main container
var container:Sprite = new Sprite();
var bitmap:Bitmap = pBitmap;
container.addChild(bitmap);

// create random Point in space
var sh:Shape = new Shape();
var pts:Vector.<point> = new Vector.<point>;
for (var i:int = 0; i &lt; nbPoints; i++)
{
pts.push(new Point(Math.random() * WIDTH, Math.random() * HEIGHT));
}
pts.push(new Point(0, 0));
pts.push(new Point(WIDTH, 0));
pts.push(new Point(WIDTH, HEIGHT));
pts.push(new Point(0, HEIGHT));</point></point>

// triangulate and overlay
var dl:Delaunay = new Delaunay();
dl.render(sh.graphics, pts, dl.compute(pts));
container.addChild(sh);
sh.blendMode = BlendMode.OVERLAY;

// store the result
var dat:BitmapData = new BitmapData(WIDTH, HEIGHT, false, 0x0);
dat.draw(container);

// add some noise
var noiseDat:BitmapData = new BitmapData(WIDTH, HEIGHT, true, 0x0);
noiseDat.noise(0, 192, 255, 0, true);
dat.draw(noiseDat, null, new ColorTransform(1, 1, 1, 1 / 3, 0, 0, 0, 0), BlendMode.MULTIPLY);
noiseDat.dispose();
noiseDat = null;
container = null;

// clean
bitmap.bitmapData.dispose();
bitmap.bitmapData = dat;

return bitmap;
}

private function forceGC():void
{
try
{
new LocalConnection().connect('foo');
new LocalConnection().connect('foo');
}
catch (e:*)
{
}
}

}

}

package
{
import flash.display.Graphics;
import flash.geom.Point;

public class Delaunay
{
static public var EPSILON:Number = Number.MIN_VALUE;
static public var SUPER_TRIANGLE_RADIUS:Number = 1000000000;
private var indices:Vector.<int>;
private var circles:Vector.<Number>;

public function compute(points:Vector.<Point>):Vector.<int>
{
var nv:int = points.length;
if (nv < 3) return null;
var d:Number = SUPER_TRIANGLE_RADIUS;
points.push(new Point(0, -d), new Point(d, d), new Point(-d, d));
indices = Vector.<int>([points.length - 3, points.length - 2, points.length - 1]);
circles = Vector.<Number>([0, 0, d]);
var edgeIds:Vector.<int> = new Vector.<int>();
var i:int, j:int, k:int, id0:int, id1:int, id2:int;
for (i = 0; i < nv; i++)
{
for (j = 0; j < indices.length; j += 3)
{
if (circles[j + 2] > EPSILON && circleContains(j, points[i]))
{
id0 = indices[j];
id1 = indices[j + 1];
id2 = indices[j + 2];
edgeIds.push(id0, id1, id1, id2, id2, id0);
indices.splice(j, 3);
circles.splice(j, 3);
j -= 3;
}
}
for (j = 0; j < edgeIds.length; j += 2)
{
for (k = j + 2; k < edgeIds.length; k += 2)
{
if ((edgeIds[j] == edgeIds[k] && edgeIds[j + 1] == edgeIds[k + 1]) || (edgeIds[j + 1] == edgeIds[k] && edgeIds[j] == edgeIds[k + 1]))
{
edgeIds.splice(k, 2);
edgeIds.splice(j, 2);
j -= 2;
k -= 2;
if (j < 0) break;
if (k < 0) break;
}
}
}
for (j = 0; j < edgeIds.length; j += 2)
{
indices.push(edgeIds[j], edgeIds[j + 1], i);
computeCircle(points, edgeIds[j], edgeIds[j + 1], i);
}
edgeIds.length = 0;

}
id0 = points.length - 3;
id1 = points.length - 2;
id2 = points.length - 1;
for (i = 0; i < indices.length; i += 3)
{
if (indices[i] == id0 || indices[i] == id1 || indices[i] == id2 || indices[i + 1] == id0 || indices[i + 1] == id1 || indices[i + 1] == id2 || indices[i + 2] == id0 || indices[i + 2] == id1 || indices[i + 2] == id2)
{
indices.splice(i, 3);
i -= 3;
continue;
}
}
points.pop();
points.pop();
points.pop();
return indices;
}

private function circleContains(circleId:int, p:Point):Boolean
{
var dx:Number = circles[circleId] - p.x;
var dy:Number = circles[circleId + 1] - p.y;
return circles[circleId + 2] > dx * dx + dy * dy;
}

private function computeCircle(points:Vector.<Point>, id0:int, id1:int, id2:int):void
{
var p0:Point = points[id0];
var p1:Point = points[id1];
var p2:Point = points[id2];
var A:Number = p1.x - p0.x;
var B:Number = p1.y - p0.y;
var C:Number = p2.x - p0.x;
var D:Number = p2.y - p0.y;
var E:Number = A * (p0.x + p1.x) + B * (p0.y + p1.y);
var F:Number = C * (p0.x + p2.x) + D * (p0.y + p2.y);
var G:Number = 2.0 * (A * (p2.y - p1.y) - B * (p2.x - p1.x));
var x:Number = (D * E - B * F) / G;
circles.push(x);
var y:Number = (A * F - C * E) / G;
circles.push(y);
x -= p0.x;
y -= p0.y;
circles.push(x * x + y * y);
}

public function render(graphics:Graphics, points:Vector.<Point>, indices:Vector.<int>):void
{
var shades:Array = [0x333333, 0x666666, 0x777777, 0x888888, 0x999999, 0xAAAAAA];
var nbShades:int = shades.length;

var id0:uint, id1:uint, id2:uint;
for (var i:int = 0; i < indices.length; i += 3)
{
id0 = indices[i];
id1 = indices[i + 1];
id2 = indices[i + 2];
graphics.beginFill(shades[int(Math.random() * nbShades)], 1);
graphics.moveTo(points[id0].x, points[id0].y);
graphics.lineTo(points[id1].x, points[id1].y);
graphics.lineTo(points[id2].x, points[id2].y);
graphics.lineTo(points[id0].x, points[id0].y);
}
}
}

}