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,
	ViewUtils = require("js/helper-classes/3D/view-utils").ViewUtils,
	Rectangle = require("js/helper-classes/3D/rectangle").Rectangle;

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;
        }
    },

	rectsOverlap:
	{
		value: function( pt, width, height,  elt )
		{
			// only consider rectangles with non-zero area
			if ((width == 0) || (height == 0))  return false;

			// get the mins/maxs of the onput rectangle
			var xMin, xMax, yMin, yMax;
			if (width > 0)  {  xMin = pt[0];   xMax = pt[0] + width;  }
			else  {  xMax = pt[0];  xMin = pt[0] + width;  }
			if (height > 0)  {  yMin = pt[1];   yMax = pt[1] + height;  }
			else  {  yMax = pt[1];  yMin = pt[1] + height;  }

			// get the bounds of the element in global screen space
			var bounds = ViewUtils.getElementViewBounds3D( elt );
			var bounds3D = [];
			for (var i=0;  i<4;  i++)
				bounds3D[i] = ViewUtils.localToGlobal( bounds[i],  elt );

			// get the min/maxs for the element
			var xMinElt = bounds3D[0][0],  xMaxElt = bounds3D[0][0],
				yMinElt = bounds3D[0][1],  yMaxElt = bounds3D[0][1];
			for (var i=1;  i<4;  i++)
			{
				if (bounds3D[i][0] < xMinElt)  xMinElt = bounds3D[i][0];
				else if  (bounds3D[i][0] > xMaxElt)  xMaxElt = bounds3D[i][0];
				if (bounds3D[i][1] < yMinElt)  yMinElt = bounds3D[i][1];
				else if  (bounds3D[i][1] > yMaxElt)  yMaxElt = bounds3D[i][1];
			}

			// test 1.  Overall bounding box test
			if ((xMaxElt < xMin) || (xMinElt > xMax) || (yMaxElt < yMin) || (yMinElt > yMax))
				return false;
			
			// test 2.  See if any of the corners of the element are contained in the rectangle
			var rect = Object.create(Rectangle, {});
			rect.set( pt[0], pt[1], width, height );
			for (var i=0;  i<4;  i++)
			{
				if (rect.contains( bounds3D[i][0], bounds3D[i][1] ))  return true;
			}

			// test 3.  Bounding box tests on individual edges of the element
			for (var i=0;  i<4;  i++)
			{
				var pt0 = bounds3D[i],
					pt1 = bounds3D[(i+1)%4];

				// get the extremes of the edge
				if (pt0[0] < pt1[0])  {  xMinElt = pt0[0];  xMaxElt = pt1[0];  }
				else {  xMaxElt = pt0[0];  xMinElt = pt1[0]; }
				if (pt0[1] < pt1[1])  {  yMinElt = pt0[1];  yMaxElt = pt1[1];  }
				else {  yMaxElt = pt0[1];  yMinElt = pt1[1]; }

				if ((xMaxElt < xMin) || (xMinElt > xMax) || (yMaxElt < yMin) || (yMinElt > yMax))
					continue;
				else
				{
					// intersect the element edge with the 4 sides of the rectangle
					// vertical edges
					var xRect = xMin;
					for (var j=0;  j<2;  j++)
					{
						if ((xMinElt < xRect) && (xMaxElt > xRect))
						{
							var t = (xRect - pt0[0])/(pt1[0] - pt0[0]);
							var y = pt0[1] + t*(pt1[1] - pt0[1]);
							if ((y >= yMin) && (y <= yMax))  return true;
						}
						xRect = xMax;
					}

					// horizontal edges
					var yRect = yMin;
					for (var j=0;  j<2;  j++)
					{
						if ((yMinElt < yRect) && (yMaxElt > yRect))
						{
							var t = (yRect - pt0[1])/(pt1[1] - pt0[1]);
							var x = pt0[0] + t*(pt1[0] - pt0[0]);
							if ((x >= xMin) && (x <= xMax))  return true;
						}
						yRect = yMax;
					}
				}
			}

			// if we get here there is no overlap
			return false;
		}
	},

    ///////////////////////////////////////////////////////////////////////
    // 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