path: root/js/helper-classes/3D/math-utils.js

/* <copyright>
This file contains proprietary software owned by Motorola Mobility, Inc.<br/>
No rights, expressed or implied, whatsoever to this software are provided by Motorola Mobility, Inc. hereunder.<br/>
(c) Copyright 2011 Motorola Mobility, Inc.  All Rights Reserved.
</copyright> */

///////////////////////////////////////////////////////////////////////
// Class Utils
//      Math Utility functions
///////////////////////////////////////////////////////////////////////
var VecUtils = require("js/helper-classes/3D/vec-utils").VecUtils;

var MathUtilsClass = exports.MathUtilsClass = Object.create(Object.prototype, {
    ///////////////////////////////////////////////////////////////////////
    // Instance variables
    ///////////////////////////////////////////////////////////////////////
//    VecUtils: { value: null, writable: true },
    
    EPSILON: { value: 1.e-5, writable: true },

    // these are used in containment tests
    INSIDE: { value: -1, writable: true },
    ON: { value: 0, writable: true },
    OUTSIDE: { value: 1, writable: true },

    PI2: { value: 2*Math.PI, writable: true },
    RAD_TO_DEG: { value: 180/Math.PI, writable: true },
    DEG_TO_RAD: { value: Math.PI/180, writable: true },

    ///////////////////////////////////////////////////////////////////////
    // Property accessors
    ///////////////////////////////////////////////////////////////////////

    ///////////////////////////////////////////////////////////////////////
    // Vector Methods
    ///////////////////////////////////////////////////////////////////////

	vecIntersectPlaneForParam: {
        value: function( pt0, vec, plane )
        {
            // declare the variable to return - undefined when there is no solution
            var param;

            var     a = plane[0],  b = plane[1], c = plane[2], d = plane[3];
            var     dx = vec[0],  dy = vec[1],  dz = vec[2];
            var     x0 = pt0[0],  y0 = pt0[1],  z0 = pt0[2];

            var numerator = -(a*x0 + b*y0 + c*z0 + d);
            var denominator = a*dx + b*dy + c*dz;

            var rtnPt;
            if (this.fpSign(denominator) != 0)
                param = numerator / denominator;

            return param;
        }
    },

	vecMag3: {
        value: function( vec )
        {
            if (vec.length < 3)  return;
            var mag = vec[0]*vec[0] + vec[1]*vec[1] + vec[2]*vec[2];
            mag = Math.sqrt( mag );
            return mag;
        }
    },

	vecMag: {
        value: function( dimen, vec )
        {
            var sum = 0.0;
            for (var i=0;  i<dimen;  i++)
                sum += vec[i]*vec[i];
            return Math.sqrt( sum );
        }
    },

	vecSubtract: {
        value: function( a, b )
        {
            var rtnVec;
            var n = a.length;
            if (b.length < n)  n = b.length;
            if (n > 0)
            {
                rtnVec = Vector.create([0]);
                for (var i=0;  i<n;  i++)
                    rtnVec[i] = a[i] - b[i];
            }

            return rtnVec;
        }
    },

	vecAdd: {
        value: function( a, b )
        {
            var rtnVec;
            var n = a.length;
            if (b.length < n)  n = b.length;
            if (n > 0)
            {
                rtnVec = Vector.create([0]);
                for (var i=0;  i<n;  i++)
                    rtnVec[i] = a[i] + b[i];
            }

            return rtnVec;
        }
    },

	vecDist: {
        value: function( a, b )
        {
            var sum;
            var n = a.length;
            if (b.length < n)  n = b.length;
            if (n > 0)
            {
                var sum = 0.0;
                for (var i=0;  i<n;  i++)
                {
                    var d = a[i] - b[i];
                    sum += d*d;
                }

                sum = Math.sqrt( sum );
            }

            return sum;
        }
    },

    vecIntersectPlane: {
        value: function( pt0, vec, plane )
        {
            // declare the return point.  May be undefined in ill-conditioned cases.
            var rtnPt;

            var t = this.vecIntersectPlaneForParam( pt0, vec, plane );
            if (t != undefined)
            {
                var     x0 = pt0[0],  y0 = pt0[1],  z0 = pt0[2];
                var     dx = vec[0],  dy = vec[1],  dz = vec[2];
                rtnPt = Vector.create( [x0 + t*dx,
                    y0 + t*dy,
                    z0 + t*dz] );
            }

            return rtnPt;
        }
    },

	getPointOnPlane: {
        value: function( plane )
        {
            // abreviate the plane equation
            var a = plane[0],  b = plane[1],  c = plane[2],  d = plane[3];

            var x = 0.0,  y = 0.0,  z = 0.0;
            if ( Math.abs(plane[0]) > Math.abs(plane[1]) )
            {
                if ( Math.abs(plane[0]) > Math.abs(plane[2]) )
                    x = -d/a;
                else
                    z = -d/c;
            }
            else
            {
                if (Math.abs(plane[1]) > Math.abs(plane[2]) )
                    y = -d/b;
                else
                    z = -d/c;
            }

            // get the point on the plane
            return [x, y, z];
        }
    },

	transformPlane: {
        value: function( plane,  mat )
        {
            // we will project a point down one of the coordinate axes to find a point on the plane
            // that point and the normal to the plane will be transformed by the matrix, and the 'd'
            // component of the plane equation will be reset using the new normal and point.

            // find a point on the plane
            var ptOnPlane = this.getPointOnPlane(plane);

            ptOnPlane[3] = 1.0;	// 4 dimen so we can transform it

            // transform the point
            //ptOnPlane = mat.multiply( ptOnPlane );
            ptOnPlane = glmat4.multiplyVec3(mat, ptOnPlane, []);
            plane = this.transformVector( plane, mat );
            plane[3] = -this.dot3(plane, ptOnPlane );

            return plane;
        }
    },

	transformHomogeneousPoint: {
        value: function( srcPt, mat )
        {
            var pt = srcPt.slice(0);
            this.makeDimension4( pt );
            var	x = VecUtils.vecDot(4,  pt, [mat[0], mat[4], mat[ 8], mat[12]] ),
                    y = VecUtils.vecDot(4,  pt, [mat[1], mat[5], mat[ 9], mat[13]] ),
                    z = VecUtils.vecDot(4,  pt, [mat[2], mat[6], mat[10], mat[14]] ),
                    w = VecUtils.vecDot(4,  pt, [mat[3], mat[7], mat[11], mat[15]] );

            return [x, y, z, w];
        }
    },

	applyHomogeneousCoordinate: {
        value: function( hPt )
        {
            var w = hPt[3];
            hPt[0] /= w;
            hPt[1] /= w;
            hPt[2] /= w;
            hPt[3]  = 1;

            return hPt;
        }
    },

	transformAndDivideHomogeneousPoint: {
        value: function( pt, mat )
        {
            return this.applyHomogeneousCoordinate( this.transformHomogeneousPoint(pt, mat) );
        }
    },

	transformPoint: {
        value: function( srcPt, mat )
        {
            var pt = srcPt.slice(0);
            this.makeDimension3( pt );
            var	x = VecUtils.vecDot(3,  pt, [mat[0], mat[4], mat[ 8]] ) + mat[12],
                    y = VecUtils.vecDot(3,  pt, [mat[1], mat[5], mat[ 9]] ) + mat[13],
                    z = VecUtils.vecDot(3,  pt, [mat[2], mat[6], mat[10]] ) + mat[14];

            return [x, y, z];
        }
    },

	transformVector: {
        value: function( vec, mat )
        {
            this.makeDimension3( vec );
            var	x = VecUtils.vecDot(3,  vec, [mat[0], mat[4], mat[ 8]] ),
                    y = VecUtils.vecDot(3,  vec, [mat[1], mat[5], mat[ 9]] ),
                    z = VecUtils.vecDot(3,  vec, [mat[2], mat[6], mat[10]] );

            return [x, y, z];
        }
    },

	interpolateLine3D: {
        value: function( pt0, pt1, t )
        {
            var x0 = pt0[0],  y0 = pt0[1],  z0 = pt0[2],
                    x1 = pt1[0],  y1 = pt1[1],  z1 = pt1[2];
            var pt = Vector.create( [
                x0 + t*(x1 - x0),
                y0 + t*(y1 - y0),
                z0 + t*(z1 - z0)
            ] );

            return pt;
        }
    },


    dot: {
        value: function( v0, v1 )
        {
            var dimen = v0.length;
            if (v1.length < v0.length)  dimen = v1.length;

            var sum = 0.0;
            for (var i=0;  i<dimen;  i++)
                sum += v0[i] * v1[i];

            return sum;
        }
    },

    dot3: {
        value: function( v0, v1 )
        {
            var sum = 0.0;
            if ((v0.length < 3) || (v1.length < 3))  return;
            for (var i=0;  i<3;  i++)
                sum += v0[i] * v1[i];

            return sum;
        }
    },

    dot2: {
        value: function( v0, v1 )
        {
            if ((v0.length < 2) || (v1.length < 2))  return;
            var sum  = v0[0]*v1[0] + v0[1]*v1[1];
            return sum;
        }
    },

    cross: {
        value: function( v0, v1 )
        {
            var rtnVal;
            if ((v0.length == 2) && (v1.length == 2))
                rtnVal = v0[0]*v1[1] - v0[1]*v1[0];
            else if ((v0.length == 3) && (v1.length == 3))
                rtnVal = VecUtils.vecCross(3, v0, v1 );

            return rtnVal;
        }
    },

    negate: {
        value: function( v )
        {
            var dimen = v.length;
            for (var i=0;  i<dimen;  i++)
                v[i] = -v[i];

            return v;
        }
    },

    //returns the intersection point between the two segments (null if no intersection)
    segSegIntersection2D: {
        value: function (seg0Start, seg0End, seg1Start, seg1End, epsilon) {
            //check for parallel segments
            var denom = (seg1End[1] - seg1Start[1]) * (seg0End[0] - seg0Start[0]) - (seg1End[0] - seg1Start[0]) * (seg0End[1] - seg0Start[1]);
            if (Math.abs(denom) <= epsilon) {
                return null; //no intersection reported for segments that are close to parallel or parallel
            }

            //the parameter value of intersection point on seg0
            var paramSeg0 = (seg1End[0] - seg1Start[0]) * (seg0Start[1] - seg1Start[1]) - (seg1End[1] - seg1Start[1]) * (seg0Start[0] - seg1Start[0]);
            paramSeg0 /= denom;

            //the parameter value of intersection point on seg1
            var paramSeg1 = (seg0End[0] - seg0Start[0]) * (seg0Start[1] - seg1Start[1]) - (seg0End[1] - seg0Start[1]) * (seg0Start[0] - seg1Start[0]);
            paramSeg1 /= denom;

            //check whether the parameters are both between 0 and 1
            if (Math.abs(paramSeg0) > 1.0 || Math.abs(paramSeg1) > 1.0) {
                return null; //no intersection unless the the intersection point lies on both segments
            }

            var intPt = Vector.create([seg0Start[0] + paramSeg0 * (seg0End[0] - seg0Start[0]),
                seg0Start[1] + paramSeg0 * (seg0End[1] - seg0Start[1])]);

            return intPt;
        }
    }, //this.segSegIntersection = function (seg0, seg1)

    distPointToRay: {
        value: function (pt, rayOrig, rayDir)
        {
            var rayMagSq = rayDir[0]*rayDir[0] + rayDir[1]*rayDir[1] + rayDir[2]*rayDir[2]; //sq. of the ray direction magnitude (need not be 1)
            //find the projection of pt on ray
            var U = (
                    ( (pt[0] - rayOrig[0] ) * ( rayDir[0]) ) +
                            ( (pt[1] - rayOrig[1] ) * ( rayDir[1]) ) +
                            ( (pt[2] - rayOrig[2] ) * ( rayDir[2]) )
                    ) / ( rayMagSq );

            if( U < 0.0 ) {
                // closest point falls behind rayOrig
                // so return the min. of distance to rayOrig
                return this.vecDist(rayOrig, pt);
            }//if( U < 0.0) {

            var intersection = Vector.create([
                rayOrig[0] + U * (rayDir[0]),
                rayOrig[1] + U * (rayDir[1]),
                rayOrig[2] + U * (rayDir[2])]);

            return this.vecDist(intersection, pt);
        }
    },

    //returns the parameter value of projection of pt on SegP0P1 (param. at P0 is 0, param at P1 is 1)
    paramPointProjectionOnSegment: {
        value: function(pt, segP0, segP1){
            var segMag = this.vecDist(segP0, segP1);

            return (
                    ( (pt[0] - segP0[0] ) * ( segP1[0] - segP0[0]) ) +
                            ( (pt[1] - segP0[1] ) * ( segP1[1] - segP0[1]) ) +
                            ( (pt[2] - segP0[2] ) * ( segP1[2] - segP0[2]) )
            ) / ( segMag * segMag );
        }
    },

    //returns the distance of pt to segment P0P1
    // note the distance is to segment, not to line
    distPointToSegment: {
        value: function (pt, segP0, segP1)
        {
            var U = this.paramPointProjectionOnSegment(pt, segP0, segP1);
            if( U < 0.0 || U > 1.0 ) {
                // closest point does not fall within the segment
                // so return the min. of distance to segment endpoints
                var distToP0 = this.vecDist(segP0, pt);
                var distToP1 = this.vecDist(segP1, pt);

                if (distToP0 < distToP1) {
                    return distToP0;
                } else {
                    return distToP1;
                }
            }//if( U < 0.0 || U > 1.0 ) {

            var intersection = Vector.create([
                segP0[0] + U * (segP1[0] - segP0[0]),
                segP0[1] + U * (segP1[1] - segP0[1]),
                segP0[2] + U * (segP1[2] - segP0[2])]);

            return this.vecDist(intersection, pt);
        }
    },

	nearestPointOnLine2D: {
        value: function( linePt,  lineDir,  pt )
        {
            var vec = this.vecSubtract( pt, linePt );
            var dot = this.dot( lineDir, vec );

            var mag = this.vecMag(2,lineDir);
            if (this.fpSign(mag) == 0)  return;
            var d = dot/mag;
            var dVec = VecUtils.vecNormalize( 2, lineDir, d );
            return this.vecAdd( linePt, dVec );
        }
    },

	parameterizePointOnLine2D: {
        value: function( linePt, lineDir, ptOnLine )
        {
            var t;
            if (Math.abs(lineDir[0]) > Math.abs(lineDir[1]))
            {
                var x1 = linePt[0] + lineDir[0];
                if (this.fpCmp(ptOnLine[0],x1) == 0)
                    t = 1.0;
                else
                    t = (ptOnLine[0] - linePt[0]) / (linePt[0]+lineDir[0] - linePt[0]);
            }
            else
            {
                var y1 = linePt[1] + lineDir[1];
                if (this.fpCmp(ptOnLine[1],y1) == 0)
                    t = 1.0;
                else
                    t = (ptOnLine[1] - linePt[1]) / (linePt[1]+lineDir[1] - linePt[1]);
            }

            return t;
        }
    },

	pointsEqual: {
        value: function( dimen,  a, b )
        {
            if ((a.length < dimen) || (b.length < dimen))
                throw new Error( "dimension error in VecUtils.vecAdd" );

            for (var i=0;  i<dimen;  i++)
            {
                if (this.fpCmp(a[i],b[i]) != 0)  return false;
            }

            return true;
        }
    },

    makeDimension4: {
        value: function( vec )
        {
            var dimen = vec.length;
            if (dimen < 4)
            {
                for (var i=0;  i<3-dimen;  i++)
                    vec.push(0);
                vec.push(1);
            }
            else if (dimen > 4)
            {
                for (var i=0;  i<dimen-4;  i++)
                    vec.pop();
            }

            return vec;
        }
    },

    makeDimension3: {
        value: function( vec )
        {
            var dimen = vec.length;
            if (dimen < 3)
            {
                for (var i=0;  i<3-dimen;  i++)
                    vec.push(0);
            }
            else if (dimen > 3)
            {
                for (var i=0;  i<dimen-3;  i++)
                    vec.pop();
            }

            return vec;
        }
    },

    styleToNumber: {
        value: function( str )
        {
            var index = str.indexOf( "px" );
            if (index >= 0)
                str = str.substr( 0, index );

            var n = Number( str );
            return n;
        }
    },

    ///////////////////////////////////////////////////////////////////////
    // Bezier Methods
    ///////////////////////////////////////////////////////////////////////
	// this function returns the quadratic Bezier approximation to the specified
	// circular arc.  The input can be 2D or 3D, determined by the minimum dimension
	// of the center and start point.
	// includedAngle is in radians, can be positiveor negative
	circularArcToBezier: {
        value: function( ctr_, startPt_, includedAngle )
        {
            var dimen = 3;
            var ctr = ctr_.slice();  MathUtils.makeDimension3( ctr );
            var startPt = startPt_.slice();  MathUtils.makeDimension3( startPt );

            // make sure the start point is good
            var pt = VecUtils.vecSubtract(dimen, startPt, ctr);
            var rad = VecUtils.vecMag(dimen, pt);

            if ((dimen != 3) || (MathUtils.fpSign(rad) <= 0) || (MathUtils.fpSign(includedAngle) == 0))
            {
                if (dimen != 3)  console.log( "MathUtils.circularArcToBezier works for 3 dimensional points only.  Was " + dimen );
                return [ startPt.slice(0), startPt.slice(0), startPt.slice(0) ];
            }

            // determine the number of segments.  45 degree span maximum.
            var nSegs = Math.ceil( Math.abs(includedAngle)/(0.25*Math.PI) );
            if (nSegs <= 0)  return [ startPt.slice(0), startPt.slice(0), startPt.slice(0) ];
            var dAngle = includedAngle/nSegs;

            // determine the length of the center control point from the circle center
            var cs = Math.cos( 0.5*Math.abs(dAngle) ),  sn = Math.sin( 0.5*Math.abs(dAngle) );
            var  c = rad*sn;
            var  h = c*sn/cs;
            var  d = rad*cs + h;

            var rtnPts = [ VecUtils.vecAdd(dimen, pt, ctr) ];
            var rotMat = Matrix.RotationZ( dAngle );
            for ( var i=0;  i<nSegs;  i++)
            {
                // get the next end point
                var pt2 = MathUtils.transformPoint( pt, rotMat );

                // get the next center control point
                var midPt = vec3.add(pt, pt2, []);
                VecUtils.vecScale(dimen, midPt, 0.5);
                midPt = VecUtils.vecNormalize( dimen, midPt, d );

                // save the next segment
                rtnPts.push( VecUtils.vecAdd(dimen, midPt, ctr) );
                rtnPts.push( VecUtils.vecAdd(dimen,   pt2, ctr) );

                // advance for the next segment
                pt = pt2;
            }
            return rtnPts;
        }
    },

    ///////////////////////////////////////////////////////////////////////
    // Polygon Methods
    ///////////////////////////////////////////////////////////////////////
    getPolygonNormal: {
        value: function( n, xPts, yPts, zPts )
        {
            var xNrm = 0.0,  yNrm = 0.0,  zNrm = 0.0;
            for (var i=0;  i<n;  i++)
            {
                var j = (i+1) % n;

                xNrm += (yPts[i] - yPts[j]) * (zPts[i] + zPts[j]);
                yNrm += (zPts[i] - zPts[j]) * (xPts[i] + xPts[j]);
                zNrm += (xPts[i] - xPts[j]) * (yPts[i] + yPts[j]);
            }
            var normal = Vector.create( [xNrm, yNrm, zNrm] );

            // the area of the polygon is the length of the normal
            var area = VecUtils.vecMag(3, normal );
            if (this.fpSign(area) != 0)
                vec3.scale(normal, 1.0/area);

            return normal;
        }
    },

	getNormalFromBounds3D: {
        value: function( b )
        {
            var xNrm = 0.0,  yNrm = 0.0,  zNrm = 0.0;
            for (var i=0;  i<4;  i++)
            {
                var j = (i+1) % 4;

                xNrm += (b[i][1] - b[j][1]) * (b[i][2] + b[j][2]);
                yNrm += (b[i][2] - b[j][2]) * (b[i][0] + b[j][0]);
                zNrm += (b[i][0] - b[j][0]) * (b[i][1] + b[j][1]);
            }
            var normal = Vector.create( [xNrm, yNrm, zNrm] );

            // the area of the polygon is the length of the normal
            var area = VecUtils.vecMag(3, normal );
            if (this.fpSign(area) != 0)
                vec3.scale( normal, 1.0/area );

            return normal;
        }
    },

	getCenterFromBounds: {
        value: function( dimen, bounds )
        {
            var minVals = bounds[0].slice(0),
                    maxVals = bounds[0].slice(0);

            for (var iPt=1;  iPt<4;  iPt++)
            {
                for (var i=0;  i<dimen;  i++)
                {
                    if (bounds[iPt][i] < minVals[i])  minVals[i] = bounds[iPt][i];
                    if (bounds[iPt][i] > maxVals[i])  maxVals[i] = bounds[iPt][i];
                }
            }

            var ctr = VecUtils.vecAdd(dimen, minVals, maxVals);
            VecUtils.vecScale( dimen, ctr, 0.5 );

            return ctr;
        }
    },

    boundaryContainsPoint: {
        value: function( bounds,  targetPt,  backFacing )
        {
            var pt = targetPt.slice(0);
            while (pt.length > 2)  pt.pop();

            // this function returns -1 for inside, 0 for on and 1 for outside.
            // values defined as instance variables above
            var nPts = bounds.length;
            var pt1 = bounds[nPts-1].slice(0);
            while (pt1.length > 2)  pt1.pop();
            for (var i=0;  i<nPts;  i++)
            {
                // get the vector along the edge of the boundary
                var pt0 = pt1;
                pt1 = bounds[i].slice(0);
                while (pt1.length > 2)  pt1.pop();
                var vec0 = VecUtils.vecSubtract(2, pt1, pt0 );
                if (vec0.length == 3)  vec0.pop();

                // get a vector from the target point to pt0
                //var vec1 = pt.subtract( pt0 );
                var vec1 = VecUtils.vecSubtract(2, pt, pt0 );
                if (vec1.length == 3)  vec1.pop();

                // look at the cross product of the 2 vectors
                var cross = VecUtils.vecCross(2, vec0, vec1 );
                var sign = this.fpSign( cross );
                if (sign == 0)
                {
                    //var t = vec1.modulus() / vec0.modulus();
                    var t = VecUtils.vecMag(2, vec1)/VecUtils.vecMag(2, vec0);
                    if ((this.fpSign(t) >= 0) && (this.fpCmp(t,1.0) <= 0))
                        return this.ON;
                    else
                        return this.OUTSIDE;
                }

                if (backFacing)
                {
                    if (this.fpSign(cross) < 0)  return this.OUTSIDE;
                }
                else
                {
                    if (this.fpSign(cross) > 0)  return this.OUTSIDE;
                }
            }

            return this.INSIDE;
        }
    },


    ///////////////////////////////////////////////////////////////////////
    // floating point Methods
    ///////////////////////////////////////////////////////////////////////
    fpSign: {
        value: function( d )
        {
            var sign = 0;
            if (d < -this.EPSILON)      sign = -1;
            else if (d > this.EPSILON)  sign =  1;
            return sign;
        }
    },

    fpCmp: {
        value: function(x,y)
        {
            return this.fpSign( x-y );
        }
    },

    /////////////////////////////////////////////////////////