Forked from:: yamat1011's forked from: forked from: flash on 2011-3-14

Voronoi 3D

三次元ボロノイ分割

half edge構造の勉強に、Frederik Vanhoutte氏のコードを参考にしつつFlashに書きなおしてみました。 http://www.wblut.com/2009/05/04/snippets-ii/

// ちょろっとバグフィックス
// ついでにkey pressでボロノイの更新をストップできるようにしました

itr0510

forked:15
favorite:52
lines:644
license : MIT License
modified : 2011-03-22 22:18:12

Embed: Tweet

// forked from yamat1011's forked from: forked from: flash on 2011-3-14
// forked from yamat1011's forked from: flash on 2011-3-14
// forked from yamat1011's flash on 2011-3-14

// Frederik Vanhoutte氏のコードを参考にしています > http://www.wblut.com/2009/05/04/snippets-ii/
// ちょろっとバグフィックス
// ついでにkey pressでボロノイの更新をストップできるようにしました
 
package
{
    import flash.display.*;
    import flash.events.*;
    import flash.geom.*;
    import flash.utils.*;
    
    import net.hires.debug.Stats;
    
    [SWF(backgroundColor="#000000")]
    
    public class voronoi3D extends Sprite
    {
        private var center  :Point;
        private var proj    :PerspectiveProjection;
        private var projMat :Matrix3D;
        private var mat     :Matrix3D;
        private var viewport:Shape;
        private var degX    :Number = 0;
        private var degY    :Number = 0;
        
        private var sites   :Vector.<Vector3D>;
        private var vel     :Vector.<Vector3D>;
        
        private var CELL_NUM  :int    = 5;
        private var MAX_VEL      :Number = 1.0;
        private var HALF_WIDTH :Number= 100;
        private var HALF_HEIGHT:Number= 100;
        private var HALF_DEPTH :Number= 100;
        
        private var container:Mesh;
        private var voronoiCells:Vector.<Mesh> = new Vector.<Mesh>();;
        
        private var update:Boolean = true; 
        
        public  function voronoi3D()
        {
            stage.frameRate = 30;
            stage.align     = StageAlign.TOP_LEFT;
            stage.scaleMode = StageScaleMode.NO_SCALE;
            stage.quality   = StageQuality.BEST;
            
            init();
        }
        
        private function init():void
        {
            center  = new Point(stage.stageWidth / 2,stage.stageHeight / 2);
            mat     = new Matrix3D();
            
            proj    = new PerspectiveProjection();
            proj.fieldOfView      = 70;
            proj.projectionCenter = center;
            projMat               = proj.toMatrix3D();
            
            viewport   = new Shape();
            viewport.x = center.x;
            viewport.y = center.y;
            viewport.z = 0;
            addChild(viewport);
            
            createCells();
            createContainer();
            createVoronoi();
            
            var stats:Stats = new Stats();
            stats.x = stats.y = 10;
            addChild(stats);
            
            stage.addEventListener(Event.ENTER_FRAME,    onEnterFrame );
            stage.addEventListener(Event.RESIZE,         onStageResize);
            stage.addEventListener(MouseEvent.MOUSE_DOWN,onMouseDown  );
            stage.addEventListener(KeyboardEvent.KEY_DOWN,onKeyDown   );
        }
        
        private function createCells():void
        {
            sites = new Vector.<Vector3D>();
            vel   = new Vector.<Vector3D>();
            for(var i:int=0;i<CELL_NUM;i++){
                var c:Vector3D = new Vector3D(
                    Math.random() * HALF_WIDTH *2- HALF_WIDTH,
                    Math.random() * HALF_HEIGHT*2- HALF_HEIGHT,
                    Math.random() * HALF_DEPTH *2- HALF_DEPTH
                );
                sites.push(c);
                
                var v:Vector3D = new Vector3D(Math.random()-0.5,Math.random()-0.5,Math.random()-0.5);
                v.normalize();
                v.scaleBy(MAX_VEL);
                vel.push(v);
            }
        }
        
        private function createContainer():void
        {
            var tmpVertices:Vector.<Vector3D> = new <Vector3D>[
                new Vector3D( HALF_WIDTH, HALF_HEIGHT, HALF_DEPTH),
                new Vector3D(-HALF_WIDTH, HALF_HEIGHT, HALF_DEPTH),
                new Vector3D(-HALF_WIDTH, HALF_HEIGHT,-HALF_DEPTH),
                new Vector3D( HALF_WIDTH, HALF_HEIGHT,-HALF_DEPTH),
                new Vector3D( HALF_WIDTH,-HALF_HEIGHT, HALF_DEPTH),
                new Vector3D(-HALF_WIDTH,-HALF_HEIGHT, HALF_DEPTH),
                new Vector3D(-HALF_WIDTH,-HALF_HEIGHT,-HALF_DEPTH),
                new Vector3D( HALF_WIDTH,-HALF_HEIGHT,-HALF_DEPTH)
            ];
            
            var tmpFacesIndex:Vector.< Vector.<int> > = new < Vector.<int> >[
                new <int>[0,1,2,3],
                new <int>[1,0,4,5],
                new <int>[0,3,7,4],
                new <int>[2,1,5,6],
                new <int>[5,4,7,6],
                new <int>[3,2,6,7]                
            ];
            
            container = new Mesh();        
            container.buildMesh(tmpVertices,tmpFacesIndex);
        }
        
        private function createVoronoi():void
        {    
            for(var i:int = 0;i < sites.length; i++){
                voronoiCells[i] = container.get();
            }
            
            for(i=0;i<sites.length;i++){
                for(var j:int=0;j<sites.length;j++){
                    if(i!=j){
                        var n:Vector3D = sites[i].subtract(sites[j]);
                        n.normalize();
                        var o:Vector3D = sites[i].add(sites[j]);
                        o.scaleBy(0.5);
                        var p:Plane = new Plane(o,n);
                        voronoiCells[i].splitMesh(p,sites[i]);
                    }
                }
            }
            
                        
        }
        
        private function onEnterFrame(event:Event):void
        {
            updateMatrix();
            if(update){
                updateCells();
                createVoronoi();
            }
            render();
        }
        
        private function render():void
        {
            var g:Graphics = viewport.graphics;
            g.clear();
            g.lineStyle(1,0xFF0066,1);
            
            //draw sites/////////////////////////////
            for(var i:int=0;i<sites.length;i++)
            {
                var c:Vector3D = Utils3D.projectVector(mat,sites[i]);
                g.moveTo(c.x+4,c.y  );
                g.lineTo(c.x-4,c.y  );
                g.moveTo(c.x  ,c.y-4);
                g.lineTo(c.x  ,c.y+4);
            }
                        
            //draw voronoi mesh//////////////////////////
            for(i=0;i<sites.length;i++)
            {
                var edgeNum:int = voronoiCells[i].edges.length;
                for(var j:int=0;j<edgeNum;j++){
                    var e:Edge      = voronoiCells[i].edges[j];
                    var p0:Vector3D = Utils3D.projectVector(mat,e.halfEdge.vert);
                    var p1:Vector3D = Utils3D.projectVector(mat,e.halfEdge.pair.vert);
                    g.moveTo(p0.x,p0.y);
                    g.lineTo(p1.x,p1.y);
                }
            }
        }
        
        private function updateMatrix():void
        {
            degY -= (center.x - mouseX) /50;
            degX += (center.y - mouseY) /50;
            mat.identity();
            mat.appendRotation(degY,Vector3D.Y_AXIS);
            mat.appendRotation(degX,Vector3D.X_AXIS);
            mat.appendTranslation(0, 0, 300);
            mat.append(projMat);
        }
        
        private function updateCells():void
        {
            for(var i:int=0;i<sites.length;i++){
                //sites[i] = sites[i].add(vel[i]);
                sites[i].x += vel[i].x;
                sites[i].y += vel[i].y;
                sites[i].z += vel[i].z;
                if(sites[i].x < -HALF_WIDTH){
                    sites[i].x =-HALF_WIDTH*2 - sites[i].x; 
                    vel[i].x *=-1;
                }
                if(sites[i].y < -HALF_HEIGHT){
                    sites[i].y =-HALF_HEIGHT*2 - sites[i].y; 
                    vel[i].y *=-1;
                }
                if(sites[i].z < -HALF_DEPTH){
                    sites[i].z =-HALF_DEPTH*2 - sites[i].z; 
                    vel[i].z *=-1;
                }
                if(sites[i].x >  HALF_WIDTH){
                    sites[i].x = HALF_WIDTH*2 - sites[i].x; 
                    vel[i].x *=-1;
                }
                if(sites[i].y >  HALF_HEIGHT){
                    sites[i].y = HALF_HEIGHT*2 - sites[i].y; 
                    vel[i].y *=-1;
                }
                if(sites[i].z >  HALF_DEPTH){
                    sites[i].z = HALF_DEPTH*2 - sites[i].z;
                    vel[i].z *=-1;
                }
            }
        }
        
        private function onMouseDown(event:MouseEvent):void
        {
            var c:Vector3D = new Vector3D(
                Math.random() * HALF_WIDTH *2- HALF_WIDTH,
                Math.random() * HALF_HEIGHT*2- HALF_HEIGHT,
                Math.random() * HALF_DEPTH *2- HALF_DEPTH
            );
            sites.push(c);
            
            var v:Vector3D = new Vector3D(
                Math.random()-0.5,
                Math.random()-0.5,
                Math.random()-0.5
            );
            v.normalize();
            v.scaleBy(MAX_VEL);
            vel.push(v);
            
            if(!update)createVoronoi();
        }
        
        private function onKeyDown(event:KeyboardEvent):void
        {
            update = !update;
        }
        
        private function onStageResize(event:Event):void
        {
            center.x = viewport.x = stage.stageWidth / 2;
            center.y = viewport.y = stage.stageHeight/ 2;
        }
    }
}

///////////////////////////////////////////////////////////////////////////////////////
// class Mesh
///////////////////////////////////////////////////////////////////////////////////////
import flash.geom.*;

class Mesh
{
    public var vertices :Vector.<Vertex>;
    public var faces    :Vector.<Face>;
    public var halfEdges:Vector.<HalfEdge>;
    public var edges    :Vector.<Edge>;
    
    public function Mesh()
    {
        vertices = new Vector.<Vertex>();
        faces    = new Vector.<Face>();
        halfEdges= new Vector.<HalfEdge>();
        edges    = new Vector.<Edge>();
    }
    
    public function buildMesh(simpleVertices:Vector.<Vector3D>,faceIndex:Vector.< Vector.<int> >):void
    {
        vertices = new Vector.<Vertex>();
        faces    = new Vector.<Face>();
        halfEdges= new Vector.<HalfEdge>();
        edges    = new Vector.<Edge>();
        
        for(var i:int=0;i<simpleVertices.length;i++){
            vertices.push(new Vertex(simpleVertices[i].x, simpleVertices[i].y, simpleVertices[i].z, i));
        }
        
        for(i=0;i<faceIndex.length;i++){
            var faceEdges:Vector.<HalfEdge> = new Vector.<HalfEdge>();
            var hef:Face = new Face();
            faces.push(hef);
            for(var j:int=0;j<faceIndex[i].length;j++){
                var he:HalfEdge = new HalfEdge();
                faceEdges.push(he);
                he.face = hef;
                if (hef.halfEdge==null) hef.halfEdge=he;
                he.vert = vertices[faceIndex[i][j]];
                if(he.vert.halfEdge==null) he.vert.halfEdge=he; 
            }
            cycleHalfEdges(faceEdges,false);    
            halfEdges = halfEdges.concat(faceEdges);
        }
        
        pairHalfEdges(halfEdges);
        createEdges(halfEdges,edges);
        reindex();
    }
    
    public function get():Mesh
    {
        var result:Mesh = new Mesh();
        reindex();
        var i:int = 0;
        for(i=0;i<vertices.length;i++){
            result.vertices.push(vertices[i].get());
        }
        for(i=0;i<faces.length;i++){
            result.faces.push(new Face());
        }
        for(i=0;i<halfEdges.length;i++){
            result.halfEdges.push(new HalfEdge());
        }
        for(i=0;i<edges.length;i++){
            result.edges.push(new Edge());
        }
        
        for(i=0;i<vertices.length;i++){
            var sv:Vertex = vertices[i];
            var tv:Vertex = result.vertices[i];
            tv.halfEdge=result.halfEdges[sv.halfEdge.id];
        }
        for(i=0;i<faces.length;i++){
            var sf:Face = faces[i];
            var tf:Face = result.faces[i];
            tf.id=i;
            tf.halfEdge=result.halfEdges[sf.halfEdge.id];
        }
        for(i=0;i<edges.length;i++){
            var se:Edge = edges[i];
            var te:Edge = result.edges[i];
            te.halfEdge = result.halfEdges[se.halfEdge.id];
            te.id=i;
        }
        for(i=0;i<halfEdges.length;i++){
            var she:HalfEdge = halfEdges[i];
            var the:HalfEdge = result.halfEdges[i];
            the.pair = result.halfEdges[she.pair.id];
            the.next = result.halfEdges[she.next.id];
            the.prev = result.halfEdges[she.prev.id];
            the.vert = result.vertices[she.vert.id];
            the.face = result.faces[she.face.id];
            the.edge = result.edges[she.edge.id];
            the.id=i;
        }
        return result;
    }
    
    public function getDual():Mesh
    {
        var result:Mesh = new Mesh();
        reindex();
        var f:Face;
        var he:HalfEdge;
        for(var i:int=0;i<faces.length;i++){
            f  = faces[i];
            he = f.halfEdge;
            var faceCenter:Vector3D = new Vector3D();
            var n:int       = 0;
            do{
                faceCenter = faceCenter.add(he.vert);
                he=he.next;
                n++;
            }while(he!=f.halfEdge);
            faceCenter.scaleBy(1/n);
            result.vertices.push(new Vertex(faceCenter.x,faceCenter.y,faceCenter.z,i));
        }
        
        for(i=0;i<vertices.length;i++){
            var v:Vertex   = vertices[i];
            he = v.halfEdge;
            f  = he.face;
            
            var faceHalfEdges:Vector.<HalfEdge> = new Vector.<HalfEdge>();
            var nf:Face                         = new Face();
            result.faces.push(nf);
            
            do{
                var hen:HalfEdge = new HalfEdge();
                faceHalfEdges.push(hen);
                hen.face=nf;
                hen.vert=result.vertices[f.id];
                if(hen.vert.halfEdge==null) hen.vert.halfEdge=hen;
                if (nf.halfEdge==null) nf.halfEdge=hen;
                he=he.pair.next;
                f=he.face;
            } while(he!=v.halfEdge);
            cycleHalfEdges(faceHalfEdges,false);    
            result.halfEdges = result.halfEdges.concat(faceHalfEdges);
            
        }
        result.pairHalfEdges(result.halfEdges);
        result.createEdges(result.halfEdges,result.edges);
        result.reindex();
        
        return result;
    }
    
    public function cycleHalfEdges(halfEdges:Vector.<HalfEdge>, reverse:Boolean):void
    {   
        var he:HalfEdge;
        var n:int = halfEdges.length;
        if(!reverse){
            he      = halfEdges[0];
            he.next = halfEdges[1];
            he.prev = halfEdges[n-1];
            for(var i:int=1;i<n-1;i++){
                he      = halfEdges[i];
                he.next = halfEdges[i+1];
                he.prev = halfEdges[i-1];//                    
            }
            he      = halfEdges[n-1];
            he.next = halfEdges[0];
            he.prev = halfEdges[n-2];
        } else {
            he      = halfEdges[0];
            he.prev = halfEdges[1];
            he.next = halfEdges[n-1];
            for(var j:int=1;j<n-1;j++){
                he      = halfEdges[j];
                he.prev = halfEdges[j+1];
                he.next = halfEdges[j-1];                    
            }
            he      = halfEdges[n-1];
            he.prev = halfEdges[0];
            he.next = halfEdges[n-2];
        } 
    }
    
    public function pairHalfEdges(halfEdges:Vector.<HalfEdge>):void
    {
        var n:int = halfEdges.length;
        for(var i:int=0;i<n;i++){
            var he:HalfEdge = halfEdges[i];
            if(he.pair==null){
                for(var j:int=0;j<n;j++){
                    if(i!=j){
                        var he2:HalfEdge = halfEdges[j];
                        if((he2.pair==null)&&(he.vert==he2.next.vert)&&(he2.vert==he.next.vert)){
                            he.pair=he2;
                            he2.pair=he;
                            break;              
                        }
                    }
                }
            }
        }
    }
    
    public function createEdges(halfEdges:Vector.<HalfEdge>, target:Vector.<Edge>):void
    {
        var n:int = halfEdges.length;
        for(var i:int=0;i<n;i++){
            var he:HalfEdge = halfEdges[i];
            for(var j:int=0;j<n;j++){
                if(i!=j){
                    var he2:HalfEdge = halfEdges[j];
                    if(he.pair==he2){
                        var e:Edge = new Edge();
                        e.halfEdge = he;
                        target.push(e);
                        he.edge    = e;
                        he2.edge   = e;
                        break;
                    }
                }
            }
        }
    }
    
    public function reindex():void
    {
        var i:int;
        for(i=0;i<vertices.length;i++){
            vertices[i].id = i;
        }
        for(i=0;i<faces.length;i++){
            faces[i].id = i;
        }
        for(i=0;i<halfEdges.length;i++){
            halfEdges[i].id = i;
        }
        for(i=0;i<edges.length;i++){
            edges[i].id = i;
        }
    }
    
    public function retrieveSplitEdges(p:Plane):Vector.<SplitEdge>
    {
        var splitEdges:Vector.<SplitEdge> = new Vector.<SplitEdge>();
        for(var i:int=0;i<edges.length;i++){
            var edge:Edge = edges[i];
            var intersection:Vector3D = p.intersection(edge);
            if(intersection!=null) splitEdges.push(new SplitEdge(edge,intersection));
        }
        return splitEdges;
    }
    
    public function splitMesh(p:Plane,center:Vector3D):void
    {
        var centerSide:int = p.side(center);
        if(centerSide!=0){
            var newVertices:Vector.<Vertex>    = new Vector.<Vertex>();
            var newFaces:Vector.<Face>         = new Vector.<Face>();
            var newHalfEdges:Vector.<HalfEdge> = new Vector.<HalfEdge>();
            var newEdges:Vector.<Edge>         = new Vector.<Edge>();
            
            var splitEdges:Vector.<SplitEdge>  = retrieveSplitEdges(p);
            
            var sides:Vector.<int> = new Vector.<int>(vertices.length,true);
            var i:int=0;
            
            //　すべての頂点が平面に対し表か裏かを調べる
            for(i=0;i<vertices.length;i++){
                var v:Vertex = vertices[i];
                sides[i] = p.side(v);
            }
            
            for(i=0;i<faces.length;i++){
                var face:Face         = faces[i];
                var halfEdge:HalfEdge = face.halfEdge;
                // 母点側の頂点を入れる配列
                var newFaceVertices1:Vector.<Vertex>    = new Vector.<Vertex>();
                // 母点とは反対側の頂点を入れる配列
                //var newFaceVertices2:Vector.<Vertex>    = new Vector.<Vertex>();
                
                do{
                    // 母点側の頂点を追加
                    if(sides[halfEdge.vert.id]*centerSide>=0){
                        newFaceVertices1.push(halfEdge.vert); 
                    }
                    // 母点とは反対側の頂点を追加 使わない
                    //if(sides[halfEdge.vert.id]*centerSide<=0){
                    //    newFaceVertices2.push(halfEdge.vert); 
                    //}
                    
                    // すべての辺を走査し、平面と交差する辺の交点を
                    //　newFaceVertices1、newFaceVertices2に追加
                    for(var j:int=0;j<splitEdges.length;j++){
                        var se:SplitEdge = splitEdges[j];
                        if(halfEdge.edge==se.edge){
                            // 交点を追加
                            newFaceVertices1.push(se.splitVertex);
                            //newFaceVertices2.push(se.splitVertex);
                            break;
                        }
                    }
                    halfEdge = halfEdge.next;
                } while(halfEdge!=face.halfEdge);
                
                // 母点側の配列に新しい頂点が三つ以上ある時、面をつくり、
                //　面に関する情報をデータ構造に追加
                if(newFaceVertices1.length>2){
                    var newFace:Face = new Face();
                    newFaces.push(newFace);
                    var faceEdges:Vector.<HalfEdge> = new Vector.<HalfEdge>();
                    for(j=0;j<newFaceVertices1.length;j++){
                        v = newFaceVertices1[j];
                        if(newVertices.indexOf(v)==-1) newVertices.push(v);//
                        var newHalfEdge:HalfEdge = new HalfEdge();
                        faceEdges.push(newHalfEdge);
                        newHalfEdge.vert=v;
                        v.halfEdge=newHalfEdge;
                        newHalfEdge.face=newFace;
                        if(newFace.halfEdge==null) newFace.halfEdge=newHalfEdge;
                    }
                    cycleHalfEdges(faceEdges,false);
                    newHalfEdges = newHalfEdges.concat(faceEdges);                         
                }
            }
            
            var n:int=newHalfEdges.length;
            pairHalfEdges(newHalfEdges);
            createEdges(newHalfEdges,newEdges);
            
            var unpairedEdges:Vector.<HalfEdge> = new Vector.<HalfEdge>();
            for(i=0;i<n;i++){
                var he:HalfEdge = newHalfEdges[i];
                if(he.pair==null) unpairedEdges.push(he);
            }
            
            if(unpairedEdges.length>0){
                var cutFace:Face = new Face(); 
                faceEdges        = new Vector.<HalfEdge>();  
                he               = unpairedEdges[0];
                var hen:HalfEdge = he;
                
                do{
                    hen=he.next.pair.next;        //
                    while(unpairedEdges.indexOf(hen)==-1) hen=hen.pair.next;
                    var newhe:HalfEdge =new HalfEdge(); //
                    faceEdges.push(newhe);
                    if(cutFace.halfEdge==null) cutFace.halfEdge=newhe;
                    newhe.vert=hen.vert;
                    newhe.pair=he;
                    he.pair=newhe;
                    var e:Edge = new Edge(); //
                    e.halfEdge=newhe;
                    he.edge=e;
                    newhe.edge=e;
                    newEdges.push(e);
                    newhe.face=cutFace;
                    he=hen;
                } while(hen!=unpairedEdges[0]);
                
                cycleHalfEdges(faceEdges, true);
                newHalfEdges = newHalfEdges.concat(faceEdges); 
                newFaces.push(cutFace);
            }              
            
            // 更新
            vertices = newVertices;
            faces    = newFaces;
            halfEdges= newHalfEdges;
            edges    = newEdges;
            reindex();
            ///////////////////////////////////////
        }
    }
}

///////////////////////////////////////////////////////////////////////////////////////
// class Vertex
///////////////////////////////////////////////////////////////////////////////////////
import flash.geom.Vector3D;

class Vertex extends Vector3D
{
    public var id:int;
    public var halfEdge:HalfEdge;
    
    public function Vertex(x:Number,y:Number,z:Number, id:int)
    {
        super(x,y,z);
        this.id = id;
    }
    
    // clone
    public function get():Vertex
    {
        return new Vertex(x,y,z,id);
    }
}

///////////////////////////////////////////////////////////////////////////////////////
// class Edge
///////////////////////////////////////////////////////////////////////////////////////
class Edge
{
    public var id:int;
    public var halfEdge:HalfEdge;
}

///////////////////////////////////////////////////////////////////////////////////////
// class HalfEdge
///////////////////////////////////////////////////////////////////////////////////////
class HalfEdge
{
    public var id   :int;
    public var vert :Vertex;
    public var pair :HalfEdge;
    public var face :Face;
    public var next :HalfEdge;
    public var prev :HalfEdge;
    public var edge :Edge;
}

///////////////////////////////////////////////////////////////////////////////////////
// class Face
///////////////////////////////////////////////////////////////////////////////////////
class Face
{
    public var id:int;
    public var halfEdge:HalfEdge;
}

///////////////////////////////////////////////////////////////////////////////////////
// class Plane
///////////////////////////////////////////////////////////////////////////////////////
import flash.geom.Vector3D;

class Plane
{
    public var A:Number;
    public var B:Number;
    public var C:Number;
    public var D:Number;

// AX + BY + CZ + D = 0
    public function Plane(p0:Vector3D,p1:Vector3D,p2:Vector3D = null)
    {
        var norm:Vector3D;
        if(p2 == null){
            norm = p1.clone();
            norm.normalize();
            A = norm.x;
            B = norm.y;
            C = norm.z;
            D = -A*p0.x-B*p0.y-C*p0.z;
        } else {
            A=p0.y*(p1.z-p2.z)+p1.y*(p2.z-p0.z)+p2.y*(p0.z-p1.z);
            B=p0.z*(p1.x-p2.x)+p1.z*(p2.x-p0.x)+p2.z*(p0.x-p1.x);
            C=p0.x*(p1.y-p2.y)+p1.x*(p2.y-p0.y)+p2.x*(p0.y-p1.y);
            norm = new Vector3D(A,B,C);
            norm.normalize();
            A=norm.x;
            B=norm.y;
            C=norm.z;
            D=-A*p0.x-B*p0.y-C*p0.z;
        }
    }
    
    public function flipNormal():void
    {
        A*=-1;
        B*=-1;
        C*=-1;
        D*=-1;
    }
    
    public function side(p:Vector3D):int 
    {
        var tmp:Number = A*p.x+B*p.y+C*p.z+D;
        if(tmp<-0.001)     return -1;
        else if(tmp>0.001) return  1;
        else               return  0;
    }
    
    //Paul Bourke, http://local.wasp.uwa.edu.au/~pbourke/geometry/planeline/
    public function intersection(e:Edge):Vector3D
    {
        var p0:Vector3D = e.halfEdge.vert;
        var p1:Vector3D = e.halfEdge.pair.vert;
        var denom:Number= this.A*(p0.x-p1.x)+
                          this.B*(p0.y-p1.y)+
                          this.C*(p0.z-p1.z);
        if ((denom<0.001)&&(denom>-0.001)) return null;
        var u:Number = (this.A*p0.x + this.B*p0.y + this.C*p0.z + this.D)/denom;
        if ((u<0.00)||(u>1.0)) return null;
        return new Vector3D(p0.x+u*(p1.x-p0.x),p0.y+u*(p1.y-p0.y),p0.z+u*(p1.z-p0.z));
    }
}

///////////////////////////////////////////////////////////////////////////////////////
// class SplitEdge
///////////////////////////////////////////////////////////////////////////////////////
import flash.geom.Vector3D;
class SplitEdge
{
    public var edge       :Edge;
    public var splitVertex:Vertex;
    
    public function SplitEdge(e:Edge = null, p:Vector3D = null)
    {
        if(e!=null) edge        = e;
        if(p!=null) splitVertex = new Vertex(p.x,p.y,p.z,0);
    }
}

Code Fullscreen

Preview Fullscreen