/**
* Copyright bradsedito ( http://wonderfl.net/user/bradsedito )
* MIT License ( http://www.opensource.org/licenses/mit-license.php )
* Downloaded from: http://wonderfl.net/c/dwp7
*/
package
{
import flash.display.*;
import flash.events.*;
import flash.geom.*;
public class ConvexHull extends Sprite
{
public var validFaces:Vector.<Face>;
public var visibleFaces:Vector.<Face>;
public var tmpFaces:Vector.<Face>;
/*
* performs a convexhull in 3D
* @param points the Vector3D cloud
* @return a series of indices to create the faces of the hull
*/
public function ConvexHull():void
{
addEventListener( Event.ENTER_FRAME, loop);
function loop( event:Event ):void
{
//var validFaces:Vector.<Face>;
//var visibleFaces:Vector.<Face>;
//var tmpFaces:Vector.<Face>;
}
}
public function process( points:Vector.<Vector3D> ):Vector.<int>
{
if ( points.length < 3 )
{
return null;
}
//local copy of the point set
//vertices = .concat();
Face.points = points;
//calculates the first convex tetrahedron
//creates a face with the first 3 vertices
var face:Face = new Face( 0, 1, 2 );
//this is the center of the tetrahedron, all face should point outwards:
//they should not be visible to the centroid
var v:Vector3D = centroid( points, 3, face );
if ( face.isVisible( v ) ) face.flip();
var face0:Face = new Face( 3, face.i0, face.i1 );
if ( face0.isVisible( v ) ) face0.flip();
var face1:Face = new Face( 3, face.i1, face.i2 );
if ( face1.isVisible( v ) ) face1.flip();
var face2:Face = new Face( 3, face.i2, face.i0 );
if ( face2.isVisible( v ) ) face2.flip();
//store the tetrahedron faces in the valid faces list
validFaces = Vector.<Face>( [ face, face0, face1, face2 ] );
visibleFaces = new Vector.<Face>();
tmpFaces = new Vector.<Face>();
//so as we have a convex tetrahedron, we can skip the first 4 points
for ( var i:int = 4; i < points.length; i++ )
{
//for each avaiable vertices
v = points[ i ];
//checks the point's visibility from all faces
visibleFaces.length = 0;
for each( face in validFaces )
{
if ( face.isVisible( v ) )
{
visibleFaces.push( face );
}
}
var validFaces:Vector.<Face>;
var visibleFaces:Vector.<Face>;
var tmpFaces:Vector.<Face>;
//the vertex is not visible : it is inside the convex hull, keep on
if ( visibleFaces.length == 0 )
{
continue;
}
//the vertex is outside the convex hull
//delete all visible faces from the valid List
for each ( face in visibleFaces )
{
validFaces.splice( validFaces.indexOf( face ), 1 );
}
//special case : only one face is visible
//it's ok to create 3 faces directly for they won't enclose any other point
if ( visibleFaces.length == 1 )
{
face = visibleFaces[ 0 ];
validFaces.push( new Face( i, face.i0, face.i1 ) );
validFaces.push( new Face( i, face.i1, face.i2 ) );
validFaces.push( new Face( i, face.i2, face.i0 ) );
continue;
}
//creates all possible new faces from the visibleFaces
tmpFaces.length = 0;
for each( face in visibleFaces )
{
tmpFaces.push( new Face( i, face.i0, face.i1 ) );
tmpFaces.push( new Face( i, face.i1, face.i2 ) );
tmpFaces.push( new Face( i, face.i2, face.i0 ) );
}
var other:Face;
for each( face in tmpFaces )
{
//search if there is a point in front of the face :
//this means the face doesn't belong to the convex hull
search : for each( other in tmpFaces )
{
if ( face != other )
{
if ( face.isVisible( other.centroid ) )
{
face = null;
break search;
}
}
}
//the face has no point in front of it
if ( face != null ) validFaces.push( face );
}
}
var result:Vector.<int> = new Vector.<int>();
for each( face in validFaces )
{
result.push( face.i0, face.i1, face.i2 );
}
return result;
}
private function centroid( points:Vector.<Vector3D>, index:int, face:Face ):Vector3D
{
var p:Vector3D = points[ index ];
var p0:Vector3D = points[ face.i0 ];
var p1:Vector3D = points[ face.i1 ];
var p2:Vector3D = points[ face.i2 ];
return new Vector3D( ( p.x + p0.x + p1.x + p2.x ) / 4, ( p.y + p0.y + p1.y + p2.y ) / 4, ( p.z + p0.z + p1.z + p2.z ) / 4 );
}
}
}
import flash.geom.Vector3D;
class Face
{
static public var points:Vector.<Vector3D>;
public var i0:int, i1:int, i2:int;
public var a:Number, b:Number, c:Number, d:Number;
public function Face( i0:int, i1:int, i2:int )
{
this.i0 = i0;
this.i1 = i1;
this.i2 = i2;
computePlane();
}
private function computePlane():void
{
var v1:Vector3D = points[ i0 ];
var v2:Vector3D = points[ i1 ];
var v3:Vector3D = points[ i2 ];
a = v1.y * (v2.z - v3.z) + v2.y * (v3.z - v1.z) + v3.y * (v1.z - v2.z);
b = v1.z * (v2.x - v3.x) + v2.z * (v3.x - v1.x) + v3.z * (v1.x - v2.x);
c = v1.x * (v2.y - v3.y) + v2.x * (v3.y - v1.y) + v3.x * (v1.y - v2.y);
d = -( v1.x * ( v2.y * v3.z - v3.y * v2.z ) + v2.x * (v3.y * v1.z - v1.y * v3.z) + v3.x * (v1.y * v2.z - v2.y * v1.z) );
}
public function isVisible( p:Vector3D ):Boolean
{
return ( a * p.x + b * p.y + c * p.z + d ) > 0;
}
public function get centroid( ):Vector3D
{
var p0:Vector3D = points[ i0 ];
var p1:Vector3D = points[ i1 ];
var p2:Vector3D = points[ i2 ];
return new Vector3D( ( p0.x + p1.x + p2.x ) / 3, ( p0.y + p1.y + p2.y ) / 3, ( p0.z + p1.z + p2.z ) / 3 );
}
public function flip():void
{
var t:int = i0;
i0 = i1;
i1 = t;
computePlane();
}
}
