ボロノイってみた forked from: 画像フラクタル分割を WebCam に適用
画像フラクタル分割を WebCam に適用
@author YOSHIDA, Akio (Aquioux)
/**
* Copyright fumix ( http://wonderfl.net/user/fumix )
* MIT License ( http://www.opensource.org/licenses/mit-license.php )
* Downloaded from: http://wonderfl.net/c/cjMX
*/
// forked from Aquioux's 画像フラクタル分割を WebCam に適用
package {
import flash.display.Sprite;
import flash.events.Event;
/**
* 画像フラクタル分割を WebCam に適用
* @author YOSHIDA, Akio (Aquioux)
*/
[SWF(width = "465", height = "465", frameRate = "60", backgroundColor = "#000000")]
public class VoronoiVideo extends Sprite {
public function VoronoiVideo() {
Wonderfl.capture_delay(15);
// Model を生成
try {
var model : Model = new Model(stage);
} catch (err : Error) {
trace(err.message);
}
model.setEffector(new Effector(stage.stageWidth, stage.stageHeight));
// View を生成
var view : View = new View(model);
addChild(view);
// ユーザインタラクションはないので Controller は存在しない。
// 開始
model.start();
}
}
}
import flash.display.Sprite;
import flash.display.BitmapData;
import flash.display.Stage;
import flash.events.Event;
import flash.events.EventDispatcher;
import flash.media.Camera;
import flash.media.Video;
/**
* Web Camera の映像にエフェクトをかける（MVC の Model）
* エフェクトロジックは effector クラスとして外部で定義する
* @author YOSHIDA, Akio (Aquioux)
*/
class Model extends EventDispatcher {
// --------------------------------------------------
// View へ渡すデータ（プロパティ）
// --------------------------------------------------
/**
* 加工済みのカメラ画像
*/
private var _data : BitmapData;
public function get data() : BitmapData {
return _data;
}
// --------------------------------------------------
// データアクセサー（外部からデータを取得する）
// --------------------------------------------------
/**
* カメラエフェクタ
* @param effector カメラエフェクター
*/
private var effector : AbstractEffector; // カメラエフェクタ
public function setEffector(effector : AbstractEffector) : void {
this.effector = effector;
}
// --------------------------------------------------
// 外部との通信をおこなうメソッド
// --------------------------------------------------
/**
* 対 View 用メソッド
* このメソッドの終了時にイベントを発行するので、View との通信手段となる
* @private
*/
private function update() : void {
_data = effector.applyEffect(video);
dispatchEvent(new Event(Event.CHANGE));
}
// --------------------------------------------------
// その他のメソッド
// --------------------------------------------------
/**
* コンストラクタ
* コンストラクタの引数はステージとする。各種データはアクセサーによって取り込むものとする
* @param stage ステージ
*/
private var stage : Stage;
// カメラが表示するサイズ
private var cameraWidth : uint;
private var cameraHeight : uint;
// カメラ
private var camera : Camera;
private var video : Video;
public function Model(stage : Stage) {
this.stage = stage;
cameraWidth = stage.stageWidth;
cameraHeight = stage.stageHeight;
// カメラ
camera = Camera.getCamera();
if (camera != null) {
// camera のセットアップ
camera.setMode(cameraWidth, cameraHeight, stage.frameRate);
// video のセットアップ
video = new Video(cameraWidth, cameraHeight);
video.attachCamera(camera);
} else {
throw new Error("カメラがありません。");
}
}
/**
* 処理開始
* Event.ENTER_FRAME を使う場合、このメソッドを設定する。
* Controller から通知されるイベントだけで処理する場合、このメソッドは不要。
*/
public function start() : void {
stage.addEventListener(Event.ENTER_FRAME, enterFrameHandler);
}
/**
* イベントハンドラ
* @private
*/
private function enterFrameHandler(event : Event) : void {
update();
}
}
import flash.display.Bitmap;
import flash.events.Event;
/**
* Web Camera のスクリーン（MVC の View）
* @author YOSHIDA, Akio (Aquioux)
*/
class View extends Bitmap {
/**
* コンストラクタ
* @param model Model
*/
private var model : Model;
public function View(model : Model) {
this.model = model;
this.model.addEventListener(Event.CHANGE, changeHandler);
}
/**
* Model との通信手段
* @param event 発生したイベント
*/
private function changeHandler(event : Event) : void {
// Model からデータを受け取り、視覚化
this.bitmapData = model.data;
}
}
import flash.display.BitmapData;
import flash.display.IBitmapDrawable;
import flash.geom.Point;
import flash.geom.Rectangle;
/**
* ウェブカメラエフェクト用抽象クラス
* @author YOSHIDA, Akio
*/
class AbstractEffector {
protected var _raw : BitmapData; // ウェブカメラの生映像の bitmapData
// BitmapData 操作時に使う各種変数
protected const ZERO_POINT : Point = new Point(0, 0);
protected var _rect : Rectangle;
public function AbstractEffector(width : Number, height : Number) {
_raw = new BitmapData(width, height);
_rect = new Rectangle(0, 0, width, height);
}
// 効果適用
public function applyEffect(data : IBitmapDrawable) : BitmapData {
_raw.draw(data);
return effect(_raw);
}
// 効果処理
// サブクラスで定義
protected function effect(raw : BitmapData) : BitmapData {
return null;
}
}
import flash.display.BitmapData;
import flash.filters.ColorMatrixFilter;
import flash.geom.Point;
import flash.geom.Rectangle;
/**
* Web Camera Effector
* フラクタル分割
* @author YOSHIDA, Akio (Aquioux)
*/
class Effector extends AbstractEffector {
private const THRESHOLD : Number = 25; // 閾値
private const LIMIT_OF_MINIMUN : uint = 8; // 分割サイズ最小値
private var _colorBitmapData : BitmapData; // 読込画像の BitmapData
private var _grayBitmapData : BitmapData; // グレイスケール化した BitmapData
private var _canvasBitmapData : BitmapData;
private var _histVector : Vector.<Vector.<Number>>; // BitmapData.histogram() の返り値として共用する
private var _numOfPixel : uint; // Rectangle 内のピクセル数として共用する
private var _fortune : Fortune; //Fortuneアルゴリズム用クラス
private var _points : Vector.<Number2>; //voronoi母点群
private var _canvas : Sprite;
public function Effector(width : Number, height : Number) {
super(width, height);
_colorBitmapData = new BitmapData(width, height);
_grayBitmapData = new BitmapData(width, height);
_canvasBitmapData = new BitmapData(width, height);
_canvas = new Sprite();
_fortune = new Fortune();
_points = new Vector.<Number2>();
}
override protected function effect(value : BitmapData) : BitmapData {
_colorBitmapData = value;
_grayBitmapData = _colorBitmapData.clone();
_canvasBitmapData = _colorBitmapData.clone();
grayscale(_grayBitmapData);
// 再帰処理の開始
_rect = new Rectangle(0, 0, _colorBitmapData.width, _colorBitmapData.height);
_canvasBitmapData.fillRect(_rect, 0xFF000000); // 表示用 BitmapData の初期化
_points = new Vector.<Number2>();
divideCheck(_rect);
//ボロノイ辺の描画
_fortune.points = _points;
var segments : Vector.<Number2> = _fortune.compute();
_canvas.graphics.clear();
_canvas.graphics.lineStyle(1, 0x111111, 0.5);
for(var i : uint = 0;i < segments.length;i += 2) {
var start : Number2 = segments[i];
var end : Number2 = segments[i + 1];
_canvas.graphics.moveTo(start.x, start.y);
_canvas.graphics.lineTo(end.x, end.y);
}
_canvasBitmapData.draw(_canvas);
//ボロノイ母点の描画
for(i = 0;i < _points.length;i++) {
_canvasBitmapData.floodFill(_points[i].x, _points[i].y, _points[i].color);
}
return _canvasBitmapData;
}
// 再帰処理
private function divideCheck(rect : Rectangle) : void {
// Rectangle を共用変数に格納（以下、getStandardDeviation, getAverageColor では _rect を使用する）
_rect = rect;
// 現在のチェック対象矩形の縦または横の長さが指定より小さい場合、再帰を停止させる
var isDivide : Boolean = (_rect.width <= LIMIT_OF_MINIMUN && _rect.height <= LIMIT_OF_MINIMUN) ? false : true;
// 再帰判定
if (isDivide) {
var deviation : Number = getStandardDeviation();
if (deviation > THRESHOLD) {
// 標準偏差が指定より大きい場合、2分木再帰を続行
var halfWidth : Number = _rect.width / 2;
var halfHeight : Number = _rect.height / 2;
var left : Number = _rect.x;
var top : Number = _rect.y;
var center : Number = left + halfWidth;
var middle : Number = top + halfHeight;
// 2分木再帰
if(rect.width > rect.height) {
divideCheck(new Rectangle(left, top, halfWidth, rect.height));
divideCheck(new Rectangle(center, top, halfWidth, rect.height));
} else {
divideCheck(new Rectangle(left, top, rect.width, halfHeight));
divideCheck(new Rectangle(left, middle, rect.width, halfHeight));
}
} else {
// 標準偏差が指定より小さい場合、再帰を停止し、描画をおこなう
draw();
}
} else {
draw();
}
}
// 対象 BitmapData の指定矩形範囲の標準偏差を求める（グレイスケール bitmapData を使用）
private function getStandardDeviation() : Number {
_numOfPixel = _rect.width * _rect.height; // 走査範囲のピクセル数
_histVector = _grayBitmapData.histogram(_rect); // 走査範囲のヒストグラム
var vector : Vector.<Number> = _histVector[0]; // グレイスケールなので一つだけで処理
var sum : Number = 0; // 累積用変数
// 輝度の平均を求める
for (var i : int = 0;i < 256;i++) {
sum += vector[i] * i;
}
var average : Number = sum / _numOfPixel;
// 平均との差の二乗を累積
var diff : Number;
sum = 0;
for (i = 0;i < 256;i++) {
diff = i - average;
sum += diff * diff * vector[i];
}
return Math.sqrt(sum / _numOfPixel);
}
// キャンバスに描画
private function draw() : void {
// var rect : Rectangle = new Rectangle(_rect.x + 0.5, _rect.y + 0.5, _rect.width - 1, _rect.height - 1);
// _canvasBitmapData.fillRect(rect, getAverageColor());
var _point : Number2 = new Number2();
_point.x = _rect.x + _rect.width / 2 + Math.random();
_point.y = _rect.y + _rect.height / 2;
_point.color = getAverageColor();
_points.push(_point);
}
// 対象 BitmapData の指定矩形範囲の平均色を求める（カラー bitmapData を使用）
private function getAverageColor() : uint {
_numOfPixel = _rect.width * _rect.height; // 走査範囲のピクセル数
_histVector = _colorBitmapData.histogram(_rect);// 走査範囲のヒストグラム
var sumVector : Vector.<Number> = new Vector.<Number>(3, true); // 累積用変数格納 Vector
// r, g, b それぞれの平均値を求める
for (var i : int = 0;i < 256;i++) {
for (var j : int = 0;j < 3;j++) {
sumVector[j] += _histVector[j][i] * i;
}
}
var r : uint = sumVector[0] / _numOfPixel;
var g : uint = sumVector[1] / _numOfPixel;
var b : uint = sumVector[2] / _numOfPixel;
// Math.min(value, 0xFF)
// http://www.be-interactive.org/index.php?itemid=519
r = (r | (((r & 0xFFFFFF00) + 0x7FFFFFFF) >> 31)) & 0xFF;
g = (g | (((g & 0xFFFFFF00) + 0x7FFFFFFF) >> 31)) & 0xFF;
b = (b | (((b & 0xFFFFFF00) + 0x7FFFFFFF) >> 31)) & 0xFF;
return 0xFF << 24 | r << 16 | g << 8 | b;
}
// グレイスケール
// Foundation ActionScript 3.0 Image Effects(P106)
// http://www.amazon.co.jp/gp/product/1430218711?ie=UTF8&tag=laxcomplex-22
// （NTSC 系加重平均）
private function grayscale(bitmapData : BitmapData) : void {
var matrix : Array = [0.3, 0.59, 0.11, 0, 0,
0.3, 0.59, 0.11, 0, 0,
0.3, 0.59, 0.11, 0, 0,
0, 0, 0, 1, 0];
bitmapData.applyFilter(bitmapData, bitmapData.rect, new Point(), new ColorMatrixFilter(matrix));
}
}
/*
* Fortune's algorithm
* http://blog.controul.com/2009/05/speedy-voronoi-diagrams-in-as3flash/
* オリジナルは上記blogからダウンロードして見てください！
* はっきりいって全然わからないのでなにやってるのかどなたか解説を！
*/
class Fortune {
// voronoi図の母点となる点群
public var points : Vector.<Number2>;
// Bounding box.
private var x0 : Number;
// Root of the frontline and next arc to be removed.
private var root : Arc;
private var next : Arc;
// Reusable objects and pools.
private var o : Number2 = new Number2;
private static var arcPoolD : Arc;
/**
* 与えられた母点からvoronoi頂点群を返します.
* @return A vector or vertices in pairs, describing segments ready for drawing.
*/
public function compute() : Vector.<Number2> {
// Clear the output.
var out : Vector.<Number2> = new Vector.<Number2>,
len : int = 0;
// Clear the state.
root = null;
next = null;
// Read the pools.
var key : * ,
arcPool : Arc = arcPoolD;
// Vars:
var i : int,
j : int,
w : Number,
x : Number,
a : Arc,
b : Arc,
z : Number2,
p : Number2 = points[ 0 ],
points : Vector.<Number2> = points,
n : int = points.length,
// Circle events check inlined.
circle : Boolean,
eventX : Number,
c : Arc,
d : Arc,
aa : Number2,
bb : Number2,
cc : Number2,
A : Number,
B : Number,
C : Number,
D : Number,
E : Number,
F : Number,
G : Number;
// 与えられた母点をx軸でソート
///// Currently insertion sort. Quicksort?
w = points[ 0 ].x;
for ( i = 1;i < n;i++ ) {
p = points[ i ];
// Insertion sort.
x = p.x;
if ( x < w ) {
j = i;
while ( ( j > 0 ) && ( points[ int(j - 1) ].x > x ) ) {
points[ j ] = points[ int(j - 1) ];
j--;
}
points[ j ] = p;
}
else
w = x;
}
// Get x bounds.
x0 = points[ 0 ].x;
// Process.
i = 0;
p = points[ 0 ];
x = p.x;
//多分母点群でループ
for ( ;; ) {
// Check circle events. /////////////////////////
if ( a ) {
// Check for arc a.
circle = false;
if ( a.prev && a.next ) {
aa = a.prev.p,
bb = a.p,
cc = a.next.p;
// Algorithm from O'Rourke 2ed p. 189.
A = bb.x - aa.x,
B = bb.y - aa.y,
C = cc.x - aa.x,
D = cc.y - aa.y;
// Check that bc is a "right turn" from ab.
if ( A * D - C * B <= 0 ) {
E = A * ( aa.x + bb.x ) + B * ( aa.y + bb.y ),
F = C * ( aa.x + cc.x ) + D * ( aa.y + cc.y ),
G = 2 * ( A * ( cc.y - bb.y ) - B * ( cc.x - bb.x ) );
// Check for colinearity.
// if ( G > 0.000000001 || G < -0.000000001 )
if ( G ) {
// Point o is the center of the circle.
o.x = ( D * E - B * F ) / G;
o.y = ( A * F - C * E ) / G;
// o.x plus radius equals max x coordinate.
A = aa.x - o.x;
B = aa.y - o.y;
eventX = o.x + Math.sqrt(A * A + B * B);
if ( eventX >= w ) circle = true;
}
}
}
// Remove from queue.
if ( a.right )
a.right.left = a.left;
if ( a.left )
a.left.right = a.right;
if ( a == next )
next = a.right;
// Record event.
if ( circle ) {
a.endX = eventX;
if ( a.endP ) {
a.endP.x = o.x;
a.endP.y = o.y;
} else {
a.endP = o;
o = new Number2;
}
d = next;
if ( !d ) {
next = a;
}
else for ( ;; ) {
if ( d.endX >= eventX ) {
a.left = d.left;
if ( d.left ) d.left.right = a;
if ( next == d ) next = a;
a.right = d;
d.left = a;
break;
}
if ( !d.right ) {
d.right = a;
a.left = d;
a.right = null;
break;
}
d = d.right;
}
} else {
a.endX = NaN;
a.endP = null;
a.left = null;
a.right = null;
}
// Push next arc to check.
if ( b ) {
a = b;
b = null;
continue;
}
if ( c ) {
a = c;
c = null;
continue;
}
a = null;
}
//////////////////////////////////////////////////
//
if ( next && next.endX <= x ) {
//
// Handle next circle event.
// Get the next event from the queue. ///////////
a = next;
next = a.right;
if ( next )
next.left = null;
a.right = null;
// Remove the associated arc from the front.
if ( a.prev ) {
a.prev.next = a.next;
a.prev.v1 = a.endP;
}
if ( a.next ) {
a.next.prev = a.prev;
a.next.v0 = a.endP;
}
if ( a.v0 ) {
out[ len++ ] = a.v0;
a.v0 = null;
out[ len++ ] = a.endP;
}
if ( a.v1 ) {
out[ len++ ] = a.v1;
a.v1 = null;
out[ len++ ] = a.endP;
}
// Keep a ref for collection.
d = a;
// Recheck circle events on either side of p:
w = a.endX;
if ( a.prev ) {
b = a.prev;
a = a.next;
} else {
a = a.next;
b = null;
}
c = null;
// Collect.
d.v0 = null;
d.v1 = null;
d.p = null;
d.prev = null;
d.endX = NaN;
d.endP = null;
d.next = arcPool;
arcPool = d;
//////////////////////////////////////////////////
//
} else {
if ( !p ) break;
//
// Handle next site event. //////////////////////
if ( !root ) {
if ( arcPool ) {
root = arcPool;
arcPool = arcPool.next;
root.next = null;
}
else
root = new Arc;
root.p = p;
} else {
z = new Number2;
// Find the first arc with a point below p,
// and start searching for the intersection around it.
a = root.next;
if ( a ) {
while ( a.next ) {
a = a.next;
if ( a.p.y >= p.y ) break;
}
// Find the intersecting curve.
intersection(a.prev.p, a.p, p.x, z);
if ( z.y <= p.y ) {
// Search for the intersection to the south of i.
while ( a.next ) {
a = a.next;
intersection(a.prev.p, a.p, p.x, z);
if ( z.y >= p.y ) {
a = a.prev;
break;
}
}
} else {
// Search for the intersection above i.
a = a.prev;
while ( a.prev ) {
a = a.prev;
intersection(a.p, a.next.p, p.x, z);
if ( z.y <= p.y ) {
a = a.next;
break;
}
}
}
}
else
a = root;
// New parabola will intersect arc a. Duplicate a.
if ( a.next ) {
if ( arcPool ) {
b = arcPool;
arcPool = arcPool.next;
b.next = null;
}
else
b = new Arc;
b.p = a.p;
b.prev = a;
b.next = a.next;
a.next.prev = b;
a.next = b;
} else {
if ( arcPool ) {
b = arcPool;
arcPool = arcPool.next;
b.next = null;
}
else
b = new Arc;
b.p = a.p;
b.prev = a;
a.next = b;
}
a.next.v1 = a.v1;
// Find the point of intersection.
z.y = p.y;
z.x = ( a.p.x * a.p.x + ( a.p.y - p.y ) * ( a.p.y - p.y ) - p.x * p.x ) / ( 2 * a.p.x - 2 * p.x );
// Add p between i and i->next.
if ( arcPool ) {
b = arcPool;
arcPool = arcPool.next;
b.next = null;
}
else
b = new Arc;
b.p = p;
b.prev = a;
b.next = a.next;
a.next.prev = b;
a.next = b;
a = a.next; // Now a points to the new arc.
a.prev.v1 = z;
a.next.v0 = z;
a.v0 = z;
a.v1 = z;
// Check for new circle events around the new arc:
b = a.next;
a = a.prev;
c = null;
w = p.x;
}
//////////////////////////////////////////////////
//
i++;
if ( i >= n ) {
p = null;
x = Number.MAX_VALUE;
} else {
p = points[ i ];
x = p.x;
}
}
}
// Store the pools.
arcPoolD = arcPool;
//
//
// Return the result ready for drawing.
return out;
}
/**
* Where do two parabolas intersect?
* @param p0 A Number2 object describing the site for the first parabola.
* @param p1 A Number2 object describing the site for the second parabola.
* @param l The location of the sweep line.
* @param res A Number2 object in which to store the intersection.
* @return The point of intersection.
*/
public function intersection( p0 : Number2, p1 : Number2, l : Number, res : Number2 ) : Number2 {
var p : Number2 = p0,
ll : Number = l * l;
if ( p0.x == p1.x )
res.y = ( p0.y + p1.y ) / 2;
else if ( p1.x == l )
res.y = p1.y;
else if ( p0.x == l ) {
res.y = p0.y;
p = p1;
} else {
// Use the quadratic formula.
var z0 : Number = 0.5 / ( p0.x - l ); // 1 / ( 2*(p0.x - l) )
var z1 : Number = 0.5 / ( p1.x - l ); // 1 / ( 2*(p1.x - l) )
var a : Number = z0 - z1;
var b : Number = -2 * ( p0.y * z0 - p1.y * z1 );
var c : Number = ( p0.y * p0.y + p0.x * p0.x - ll ) * z0 - ( p1.y * p1.y + p1.x * p1.x - ll ) * z1;
res.y = ( -b - Math.sqrt(b * b - 4 * a * c) ) / ( 2 * a );
}
// Plug back into one of the parabola equations.
res.x = ( p.x * p.x + ( p.y - res.y ) * ( p.y - res.y ) - ll ) / ( 2 * p.x - 2 * l );
return res;
}
}
class Arc {
public var p : Number2;
public var next : Arc;
public var prev : Arc;
public var v0 : Number2;
public var v1 : Number2;
// Circle event data :
public var left : Arc;
public var right : Arc;
public var endX : Number;
public var endP : Number2;
}
class Number2 {
public var x : Number;
public var y : Number;
//速度
public var vx : Number;
public var vy : Number;
public var next : Number2;
public var color:uint;
}