source: other-projects/playing-in-the-street/summer-2013/trunk/Playing-in-the-Street-WPF/Content/Web/mrdoob-three.js-4862f5f/src/extras/core/Shape.js@ 28897

/**
 * @author zz85 / http://www.lab4games.net/zz85/blog
 * Defines a 2d shape plane using paths.
 **/

// STEP 1 Create a path.
// STEP 2 Turn path into shape.
// STEP 3 ExtrudeGeometry takes in Shape/Shapes
// STEP 3a - Extract points from each shape, turn to vertices
// STEP 3b - Triangulate each shape, add faces.

THREE.Shape = function () {

    THREE.Path.apply( this, arguments );
    this.holes = [];

};

THREE.Shape.prototype = Object.create( THREE.Path.prototype );

// Convenience method to return ExtrudeGeometry

THREE.Shape.prototype.extrude = function ( options ) {

    var extruded = new THREE.ExtrudeGeometry( this, options );
    return extruded;

};

// Convenience method to return ShapeGeometry

THREE.Shape.prototype.makeGeometry = function ( options ) {

    var geometry = new THREE.ShapeGeometry( this, options );
    return geometry;

};

// Get points of holes

THREE.Shape.prototype.getPointsHoles = function ( divisions ) {

    var i, il = this.holes.length, holesPts = [];

    for ( i = 0; i < il; i ++ ) {

        holesPts[ i ] = this.holes[ i ].getTransformedPoints( divisions, this.bends );

    }

    return holesPts;

};

// Get points of holes (spaced by regular distance)

THREE.Shape.prototype.getSpacedPointsHoles = function ( divisions ) {

    var i, il = this.holes.length, holesPts = [];

    for ( i = 0; i < il; i ++ ) {

        holesPts[ i ] = this.holes[ i ].getTransformedSpacedPoints( divisions, this.bends );

    }

    return holesPts;

};


// Get points of shape and holes (keypoints based on segments parameter)

THREE.Shape.prototype.extractAllPoints = function ( divisions ) {

    return {

        shape: this.getTransformedPoints( divisions ),
        holes: this.getPointsHoles( divisions )

    };

};

THREE.Shape.prototype.extractPoints = function ( divisions ) {

    if (this.useSpacedPoints) {
        return this.extractAllSpacedPoints(divisions);
    }

    return this.extractAllPoints(divisions);

};

//
// THREE.Shape.prototype.extractAllPointsWithBend = function ( divisions, bend ) {
//
//  return {
//
//      shape: this.transform( bend, divisions ),
//      holes: this.getPointsHoles( divisions, bend )
//
//  };
//
// };

// Get points of shape and holes (spaced by regular distance)

THREE.Shape.prototype.extractAllSpacedPoints = function ( divisions ) {

    return {

        shape: this.getTransformedSpacedPoints( divisions ),
        holes: this.getSpacedPointsHoles( divisions )

    };

};

/**************************************************************
 *  Utils
 **************************************************************/

THREE.Shape.Utils = {

    /*
        contour - array of vector2 for contour
        holes   - array of array of vector2
    */

    removeHoles: function ( contour, holes ) {

        var shape = contour.concat(); // work on this shape
        var allpoints = shape.concat();

        /* For each isolated shape, find the closest points and break to the hole to allow triangulation */


        var prevShapeVert, nextShapeVert,
            prevHoleVert, nextHoleVert,
            holeIndex, shapeIndex,
            shapeId, shapeGroup,
            h, h2,
            hole, shortest, d,
            p, pts1, pts2,
            tmpShape1, tmpShape2,
            tmpHole1, tmpHole2,
            verts = [];

        for ( h = 0; h < holes.length; h ++ ) {

            hole = holes[ h ];

            /*
            shapeholes[ h ].concat(); // preserves original
            holes.push( hole );
            */

            Array.prototype.push.apply( allpoints, hole );

            shortest = Number.POSITIVE_INFINITY;


            // Find the shortest pair of pts between shape and hole

            // Note: Actually, I'm not sure now if we could optimize this to be faster than O(m*n)
            // Using distanceToSquared() intead of distanceTo() should speed a little
            // since running square roots operations are reduced.

            for ( h2 = 0; h2 < hole.length; h2 ++ ) {

                pts1 = hole[ h2 ];
                var dist = [];

                for ( p = 0; p < shape.length; p++ ) {

                    pts2 = shape[ p ];
                    d = pts1.distanceToSquared( pts2 );
                    dist.push( d );

                    if ( d < shortest ) {

                        shortest = d;
                        holeIndex = h2;
                        shapeIndex = p;

                    }

                }

            }

            //console.log("shortest", shortest, dist);

            prevShapeVert = ( shapeIndex - 1 ) >= 0 ? shapeIndex - 1 : shape.length - 1;
            prevHoleVert = ( holeIndex - 1 ) >= 0 ? holeIndex - 1 : hole.length - 1;

            var areaapts = [

                hole[ holeIndex ],
                shape[ shapeIndex ],
                shape[ prevShapeVert ]

            ];

            var areaa = THREE.FontUtils.Triangulate.area( areaapts );

            var areabpts = [

                hole[ holeIndex ],
                hole[ prevHoleVert ],
                shape[ shapeIndex ]

            ];

            var areab = THREE.FontUtils.Triangulate.area( areabpts );

            var shapeOffset = 1;
            var holeOffset = -1;

            var oldShapeIndex = shapeIndex, oldHoleIndex = holeIndex;
            shapeIndex += shapeOffset;
            holeIndex += holeOffset;

            if ( shapeIndex < 0 ) { shapeIndex += shape.length;  }
            shapeIndex %= shape.length;

            if ( holeIndex < 0 ) { holeIndex += hole.length;  }
            holeIndex %= hole.length;

            prevShapeVert = ( shapeIndex - 1 ) >= 0 ? shapeIndex - 1 : shape.length - 1;
            prevHoleVert = ( holeIndex - 1 ) >= 0 ? holeIndex - 1 : hole.length - 1;

            areaapts = [

                hole[ holeIndex ],
                shape[ shapeIndex ],
                shape[ prevShapeVert ]

            ];

            var areaa2 = THREE.FontUtils.Triangulate.area( areaapts );

            areabpts = [

                hole[ holeIndex ],
                hole[ prevHoleVert ],
                shape[ shapeIndex ]

            ];

            var areab2 = THREE.FontUtils.Triangulate.area( areabpts );
            //console.log(areaa,areab ,areaa2,areab2, ( areaa + areab ),  ( areaa2 + areab2 ));

            if ( ( areaa + areab ) > ( areaa2 + areab2 ) ) {

                // In case areas are not correct.
                //console.log("USE THIS");

                shapeIndex = oldShapeIndex;
                holeIndex = oldHoleIndex ;

                if ( shapeIndex < 0 ) { shapeIndex += shape.length;  }
                shapeIndex %= shape.length;

                if ( holeIndex < 0 ) { holeIndex += hole.length;  }
                holeIndex %= hole.length;

                prevShapeVert = ( shapeIndex - 1 ) >= 0 ? shapeIndex - 1 : shape.length - 1;
                prevHoleVert = ( holeIndex - 1 ) >= 0 ? holeIndex - 1 : hole.length - 1;

            } else {

                //console.log("USE THAT ")

            }

            tmpShape1 = shape.slice( 0, shapeIndex );
            tmpShape2 = shape.slice( shapeIndex );
            tmpHole1 = hole.slice( holeIndex );
            tmpHole2 = hole.slice( 0, holeIndex );

            // Should check orders here again?

            var trianglea = [

                hole[ holeIndex ],
                shape[ shapeIndex ],
                shape[ prevShapeVert ]

            ];

            var triangleb = [

                hole[ holeIndex ] ,
                hole[ prevHoleVert ],
                shape[ shapeIndex ]

            ];

            verts.push( trianglea );
            verts.push( triangleb );

            shape = tmpShape1.concat( tmpHole1 ).concat( tmpHole2 ).concat( tmpShape2 );

        }

        return {

            shape:shape,        /* shape with no holes */
            isolatedPts: verts, /* isolated faces */
            allpoints: allpoints

        }


    },

    triangulateShape: function ( contour, holes ) {

        var shapeWithoutHoles = THREE.Shape.Utils.removeHoles( contour, holes );

        var shape = shapeWithoutHoles.shape,
            allpoints = shapeWithoutHoles.allpoints,
            isolatedPts = shapeWithoutHoles.isolatedPts;

        var triangles = THREE.FontUtils.Triangulate( shape, false ); // True returns indices for points of spooled shape

        // To maintain reference to old shape, one must match coordinates, or offset the indices from original arrays. It's probably easier to do the first.

        //console.log( "triangles",triangles, triangles.length );
        //console.log( "allpoints",allpoints, allpoints.length );

        var i, il, f, face,
            key, index,
            allPointsMap = {},
            isolatedPointsMap = {};

        // prepare all points map

        for ( i = 0, il = allpoints.length; i < il; i ++ ) {

            key = allpoints[ i ].x + ":" + allpoints[ i ].y;

            if ( allPointsMap[ key ] !== undefined ) {

                console.log( "Duplicate point", key );

            }

            allPointsMap[ key ] = i;

        }

        // check all face vertices against all points map

        for ( i = 0, il = triangles.length; i < il; i ++ ) {

            face = triangles[ i ];

            for ( f = 0; f < 3; f ++ ) {

                key = face[ f ].x + ":" + face[ f ].y;

                index = allPointsMap[ key ];

                if ( index !== undefined ) {

                    face[ f ] = index;

                }

            }

        }

        // check isolated points vertices against all points map

        for ( i = 0, il = isolatedPts.length; i < il; i ++ ) {

            face = isolatedPts[ i ];

            for ( f = 0; f < 3; f ++ ) {

                key = face[ f ].x + ":" + face[ f ].y;

                index = allPointsMap[ key ];

                if ( index !== undefined ) {

                    face[ f ] = index;

                }

            }

        }

        return triangles.concat( isolatedPts );

    }, // end triangulate shapes

    /*
    triangulate2 : function( pts, holes ) {

        // For use with Poly2Tri.js

        var allpts = pts.concat();
        var shape = [];
        for (var p in pts) {
            shape.push(new js.poly2tri.Point(pts[p].x, pts[p].y));
        }

        var swctx = new js.poly2tri.SweepContext(shape);

        for (var h in holes) {
            var aHole = holes[h];
            var newHole = []
            for (i in aHole) {
                newHole.push(new js.poly2tri.Point(aHole[i].x, aHole[i].y));
                allpts.push(aHole[i]);
            }
            swctx.AddHole(newHole);
        }

        var find;
        var findIndexForPt = function (pt) {
            find = new THREE.Vector2(pt.x, pt.y);
            var p;
            for (p=0, pl = allpts.length; p<pl; p++) {
                if (allpts[p].equals(find)) return p;
            }
            return -1;
        };

        // triangulate
        js.poly2tri.sweep.Triangulate(swctx);

        var triangles =  swctx.GetTriangles();
        var tr ;
        var facesPts = [];
        for (var t in triangles) {
            tr =  triangles[t];
            facesPts.push([
                findIndexForPt(tr.GetPoint(0)),
                findIndexForPt(tr.GetPoint(1)),
                findIndexForPt(tr.GetPoint(2))
                    ]);
        }


    //  console.log(facesPts);
    //  console.log("triangles", triangles.length, triangles);

        // Returns array of faces with 3 element each
    return facesPts;
    },
*/

    isClockWise: function ( pts ) {

        return THREE.FontUtils.Triangulate.area( pts ) < 0;

    },

    // Bezier Curves formulas obtained from
    // http://en.wikipedia.org/wiki/B%C3%A9zier_curve

    // Quad Bezier Functions

    b2p0: function ( t, p ) {

        var k = 1 - t;
        return k * k * p;

    },

    b2p1: function ( t, p ) {

        return 2 * ( 1 - t ) * t * p;

    },

    b2p2: function ( t, p ) {

        return t * t * p;

    },

    b2: function ( t, p0, p1, p2 ) {

        return this.b2p0( t, p0 ) + this.b2p1( t, p1 ) + this.b2p2( t, p2 );

    },

    // Cubic Bezier Functions

    b3p0: function ( t, p ) {

        var k = 1 - t;
        return k * k * k * p;

    },

    b3p1: function ( t, p ) {

        var k = 1 - t;
        return 3 * k * k * t * p;

    },

    b3p2: function ( t, p ) {

        var k = 1 - t;
        return 3 * k * t * t * p;

    },

    b3p3: function ( t, p ) {

        return t * t * t * p;

    },

    b3: function ( t, p0, p1, p2, p3 ) {

        return this.b3p0( t, p0 ) + this.b3p1( t, p1 ) + this.b3p2( t, p2 ) +  this.b3p3( t, p3 );

    }

};