jump floodingアルゴリズムを用いたボロノイ図の生成

by Nao_u
jump floodingアルゴリズムを用いたボロノイ図の生成 
制御点をドラッグで移動 
http://www.comp.nus.edu.sg/~tants/jfa/rong-guodong-phd-thesis.pdf 
点の数が増えても処理負荷が変わらず、GPU実装が容易なアルゴリズム 
ソフトシャドウにも応用可能 
作成中・・・もうちょっと境界が綺麗に出るようにしたい。 
距離をb成分に8ビットで保持しているため、斜めの距離判定で誤差が累積するのが原因? 
♥10 | Line 173 | Modified 2009-12-19 16:43:35 | MIT License
play

ActionScript3 source code

/**
 * Copyright Nao_u ( http://wonderfl.net/user/Nao_u )
 * MIT License ( http://www.opensource.org/licenses/mit-license.php )
 * Downloaded from: http://wonderfl.net/c/cRKy
 */

// forked from Nao_u's jump floodingアルゴリズムを用いたボロノイ図の生成 
//    
// jump floodingアルゴリズムを用いたボロノイ図の生成 
// 
// 制御点をドラッグで移動 
// 
// http://www.comp.nus.edu.sg/~tants/jfa/rong-guodong-phd-thesis.pdf 
// 点の数が増えても処理負荷が変わらず、GPU実装が容易なアルゴリズム 
// ソフトシャドウにも応用可能 
// 
// 作成中・・・もうちょっと境界が綺麗に出るようにしたい。 
// 距離をb成分に8ビットで保持しているため、斜めの距離判定で誤差が累積するのが原因? 
// 
//   
package {       
    import flash.display.Sprite;       
    import flash.events.*;       
    [SWF(width="465", height="465", backgroundColor="0xFFFFFF", frameRate="15")]  
          
    public class FlashTest extends Sprite {       
        public function FlashTest() {       
            Main = this;       
            initialize();       
            stage.addEventListener(Event.ENTER_FRAME,update);        
        }       
    }       
}           
     
import flash.display.Sprite;        
import flash.events.*  
import flash.text.TextField;       
import flash.geom.*;  
import flash.utils.getTimer;  
var Main:Sprite;       
var SCREEN_W:Number = 465;  
var SCREEN_H:Number = 465;  
var Text:TextField      
var Text2:TextField      

var Tex:ProcTex;  
var BITMAP_W:int = 128;  
var BITMAP_H:int = 128;  
var Pnt:Vector.<ControlPoint> = new Vector.<ControlPoint>;  

// 初期化 
function initialize():void{       
    Tex = new ProcTex( BITMAP_W, BITMAP_H );  
    Tex.Bmp.x = 0;  
    Tex.Bmp.y = 0;  
      
    Text = new TextField();       
    Text.text = "生成中...";     
    Text.autoSize = "left";  
    Main.addChild(Text);        

    Text2 = new TextField();       
    Text2.text = "";     
    Text2.autoSize = "left";  
    Text2.y = 16;  
    Main.addChild(Text2);        

    // 制御点の設置 
    Pnt[0] = new ControlPoint( new Point(SCREEN_W/2-70, SCREEN_H/2+40) );  
    Pnt[1] = new ControlPoint( new Point(SCREEN_W/2-150,   SCREEN_H/2-120) );  
    Pnt[2] = new ControlPoint( new Point(SCREEN_W/2+0,   SCREEN_H/2-50) );  
    Pnt[3] = new ControlPoint( new Point(SCREEN_W/2+140,   SCREEN_H/2-130) );  
    Pnt[4] = new ControlPoint( new Point(SCREEN_W/2+100,   SCREEN_H/2+120) );  
    Pnt[5] = new ControlPoint( new Point(SCREEN_W/2-140,   SCREEN_H/2+140) );  
    Pnt[6] = new ControlPoint( new Point(SCREEN_W/2+10,    SCREEN_H/2+180) );  
    Pnt[7] = new ControlPoint( new Point(SCREEN_W/2-40,    SCREEN_H/2-180) );  
    Pnt[8] = new ControlPoint( new Point(SCREEN_W/2-140,    SCREEN_H/2-10) );  
    Pnt[9] = new ControlPoint( new Point(SCREEN_W/2+140,    SCREEN_H/2-10) );  
}  

// 更新 
function update(e :Event):void{       
    var time:int = getTimer();   
         
    Tex.draw();  

    var endTime:int = getTimer() - time;  
    Text.text = " 生成時間:" + endTime + "[ms]";     
}    

import flash.display.Bitmap;   
import flash.display.BitmapData;   

// テクスチャ生成クラス 
class ProcTex{  
    public var BmpData:BitmapData;   
    public var TmpBmpData:BitmapData;   
    public var Bmp:Bitmap;  
    public var Width:int;  
    public var Height:int;  

    public function ProcTex( w:int, h:int ){  
        Width = w;  
        Height = h;  
        BmpData = new BitmapData(Width, Height, false, 0xffffff);   
        TmpBmpData = new BitmapData(Width, Height, false, 0xffffff);   
        Bmp = new Bitmap(BmpData);   
        Bmp.x = 0.0;  
        Bmp.y = 0.0;  
        Bmp.scaleX = 7.25*0.5;  
        Bmp.scaleY = 7.25*0.5;  
        Main.addChild(Bmp);        
    }  

    public function draw():void{  
        drawBmpData( BmpData );  
    }  

    public function drawBmpData( bmpData:BitmapData ):void{  
        var col:int;  
        var dx:Number = 0.990 / Width;  
        var dy:Number = 0.990 / Height;  
        bmpData.lock();   
         
        // 全体を 距離 = 0xff でクリア 
        for( var x:int=0; x<Width; x++ ){   
            for( var y:int=0; y<Height; y++ ){   
                var s:Number = (x / Width)  - dx;  
                var t:Number = (y / Height) - dy;  
                col = 0xff;    // 青成分に距離を入れておく 
                bmpData.setPixel(x, y, col);   
            }  
        }   

        // 基準点を描画 
        bmpData.setPixel( Pnt[0].Sp.x/7.2*2, Pnt[0].Sp.y/7.2*2, 0x00ff00);   
        bmpData.setPixel( Pnt[1].Sp.x/7.2*2, Pnt[1].Sp.y/7.2*2, 0xff0000);   
        bmpData.setPixel( Pnt[2].Sp.x/7.2*2, Pnt[2].Sp.y/7.2*2, 0x8f8f00);   
        bmpData.setPixel( Pnt[3].Sp.x/7.2*2, Pnt[3].Sp.y/7.2*2, 0x8f3f00);   
        bmpData.setPixel( Pnt[4].Sp.x/7.2*2, Pnt[4].Sp.y/7.2*2, 0xf0f000);   
        bmpData.setPixel( Pnt[5].Sp.x/7.2*2, Pnt[5].Sp.y/7.2*2, 0xff8f00);   
        bmpData.setPixel( Pnt[6].Sp.x/7.2*2, Pnt[6].Sp.y/7.2*2, 0x3f8f00);   
        bmpData.setPixel( Pnt[7].Sp.x/7.2*2, Pnt[7].Sp.y/7.2*2, 0x80c000);   
        bmpData.setPixel( Pnt[8].Sp.x/7.2*2, Pnt[8].Sp.y/7.2*2, 0x804000);   
        bmpData.setPixel( Pnt[9].Sp.x/7.2*2, Pnt[9].Sp.y/7.2*2, 0x40c000);   
        bmpData.unlock();   

        // jumpFlood処理を大きいほうから順番に行う 
        jumpFlood( bmpData, 1 );    // 最初に一回、幅1で実行するとちょっと綺麗になる? 
        jumpFlood( bmpData, 64 ); 
        jumpFlood( bmpData, 32 ); 
        jumpFlood( bmpData, 16 ); 
        jumpFlood( bmpData, 8 ); 
        jumpFlood( bmpData, 4 ); 
        jumpFlood( bmpData, 2 ); 
        jumpFlood( bmpData, 1 ); 
        jumpFlood( bmpData, 1 );    // 最後にもう一回、幅1で実行するとちょっと綺麗になる? 
    }  

    public function jumpFlood( bmpData:BitmapData, w:int ):void{  
        TmpBmpData = bmpData.clone(); 

        var p0:int, p1:int, p2:int, p3:int, p5:int, p6:int, p7:int, p8:int; 
        var base:int, col:int, baseDist:int, d:int; 
        var w2:int = w * 1.4142; 
        bmpData.lock();   
        for( var x:int=0; x<Width; x++ ){   
            for( var y:int=0; y<Height; y++ ){   
                col = base = TmpBmpData.getPixel( x, y );  
                 
                // 周囲8方向の指定された距離だけ離れたピクセルを拾ってくる 
                   p0 = TmpBmpData.getPixel( x-w, y-w );  
                p1 = TmpBmpData.getPixel( x  , y-w );  
                p2 = TmpBmpData.getPixel( x+w, y-w );  
                p3 = TmpBmpData.getPixel( x-w, y   );  
                p5 = TmpBmpData.getPixel( x+w, y   );  
                p6 = TmpBmpData.getPixel( x-w, y+w ); 
                p7 = TmpBmpData.getPixel( x  , y+w ); 
                p8 = TmpBmpData.getPixel( x+w, y+w ); 
                 
                baseDist = base & 0xff; 
                d = w; 
                // 拾った中でもっとも基準点からの距離が小さいピクセルを自分のピクセルにコピー 
                   if( p0 != 0 && (p0&0xff) < baseDist ) { col = p0; baseDist = (p0&0xff); d = w2; } 
                if( p1 != 0 && (p1&0xff) < baseDist ) { col = p1; baseDist = (p1&0xff); }                 
                if( p2 != 0 && (p2&0xff) < baseDist ) { col = p2; baseDist = (p2&0xff); d = w2; }                 
                if( p3 != 0 && (p3&0xff) < baseDist ) { col = p3; baseDist = (p3&0xff); }                 
                if( p5 != 0 && (p5&0xff) < baseDist ) { col = p5; baseDist = (p5&0xff); }                 
                if( p6 != 0 && (p6&0xff) < baseDist ) { col = p6; baseDist = (p6&0xff); d = w2; }                 
                if( p7 != 0 && (p7&0xff) < baseDist ) { col = p7; baseDist = (p7&0xff); }                 
                if( p8 != 0 && (p8&0xff) < baseDist ) { col = p8; baseDist = (p8&0xff); d = w2; }                 
                 
                // 距離を更新                 
                   if( col != 0xff && col != base ) col += d; 
                bmpData.setPixel(x, y, col);   
            }  
        }   
    } 
}  

// 制御点マーカークラス 
class ControlPoint{   
    public var Sp:Sprite;   
    public var isEnable:Boolean = false;  
    public var Pos:Point;  
    public function ControlPoint( p:Point ){   
        Sp=new Sprite();     
        Pos = p;   
        Sp.x = Pos.x;   
        Sp.y = Pos.y;  
        setEnable( true );  
        Main.stage.addChild(Sp);    

        Sp.addEventListener(MouseEvent.MOUSE_UP,   function (event:MouseEvent):void{ Sp.stopDrag(); });   
        Sp.addEventListener(MouseEvent.MOUSE_DOWN, function (event:MouseEvent):void{ if( isEnable ) Sp.startDrag(); });       
    }   

    public function setEnable( flg:Boolean ):void{      
        if( flg == true && isEnable == false ){  
            Sp.graphics.clear();  
            Sp.graphics.lineStyle(1.4,0x000000);         
            Sp.graphics.beginFill(0xe0d000,1);     
            Sp.graphics.drawCircle(0,0,8.0);     
            Sp.graphics.endFill();     
        }else if( flg == false && isEnable == true ){  
            Sp.graphics.clear();  
        }  
        isEnable = flg;  
    }  
}   

Forked