Source: Core/IntersectionTests.js

  1. /*global define*/
  2. define([
  3.         './Cartesian3',
  4.         './Cartographic',
  5.         './defaultValue',
  6.         './defined',
  7.         './DeveloperError',
  8.         './Math',
  9.         './Matrix3',
  10.         './QuadraticRealPolynomial',
  11.         './QuarticRealPolynomial',
  12.         './Ray'
  13.     ], function(
  14.         Cartesian3,
  15.         Cartographic,
  16.         defaultValue,
  17.         defined,
  18.         DeveloperError,
  19.         CesiumMath,
  20.         Matrix3,
  21.         QuadraticRealPolynomial,
  22.         QuarticRealPolynomial,
  23.         Ray) {
  24.     'use strict';
  26.     /**
  27.      * Functions for computing the intersection between geometries such as rays, planes, triangles, and ellipsoids.
  28.      *
  29.      * @exports IntersectionTests
  30.      */
  31.     var IntersectionTests = {};
  33.     /**
  34.      * Computes the intersection of a ray and a plane.
  35.      *
  36.      * @param {Ray} ray The ray.
  37.      * @param {Plane} plane The plane.
  38.      * @param {Cartesian3} [result] The object onto which to store the result.
  39.      * @returns {Cartesian3} The intersection point or undefined if there is no intersections.
  40.      */
  41.     IntersectionTests.rayPlane = function(ray, plane, result) {
  42.         //>>includeStart('debug', pragmas.debug);
  43.         if (!defined(ray)) {
  44.             throw new DeveloperError('ray is required.');
  45.         }
  46.         if (!defined(plane)) {
  47.             throw new DeveloperError('plane is required.');
  48.         }
  49.         //>>includeEnd('debug');
  51.         if (!defined(result)) {
  52.             result = new Cartesian3();
  53.         }
  55.         var origin = ray.origin;
  56.         var direction = ray.direction;
  57.         var normal = plane.normal;
  58.         var denominator = Cartesian3.dot(normal, direction);
  60.         if (Math.abs(denominator) < CesiumMath.EPSILON15) {
  61.             // Ray is parallel to plane.  The ray may be in the polygon's plane.
  62.             return undefined;
  63.         }
  65.         var t = (-plane.distance - Cartesian3.dot(normal, origin)) / denominator;
  67.         if (t < 0) {
  68.             return undefined;
  69.         }
  71.         result = Cartesian3.multiplyByScalar(direction, t, result);
  72.         return Cartesian3.add(origin, result, result);
  73.     };
  75.     var scratchEdge0 = new Cartesian3();
  76.     var scratchEdge1 = new Cartesian3();
  77.     var scratchPVec = new Cartesian3();
  78.     var scratchTVec = new Cartesian3();
  79.     var scratchQVec = new Cartesian3();
  81.     /**
  82.      * Computes the intersection of a ray and a triangle as a parametric distance along the input ray.
  83.      * @memberof IntersectionTests
  84.      *
  85.      * @param {Ray} ray The ray.
  86.      * @param {Cartesian3} p0 The first vertex of the triangle.
  87.      * @param {Cartesian3} p1 The second vertex of the triangle.
  88.      * @param {Cartesian3} p2 The third vertex of the triangle.
  89.      * @param {Boolean} [cullBackFaces=false] If <code>true</code>, will only compute an intersection with the front face of the triangle
  90.      *                  and return undefined for intersections with the back face.
  91.      * @returns {Number} The intersection as a parametric distance along the ray, or undefined if there is no intersection.
  92.      */
  93.     IntersectionTests.rayTriangleParametric  = function(ray, p0, p1, p2, cullBackFaces) {
  94.         //>>includeStart('debug', pragmas.debug);
  95.         if (!defined(ray)) {
  96.             throw new DeveloperError('ray is required.');
  97.         }
  98.         if (!defined(p0)) {
  99.             throw new DeveloperError('p0 is required.');
  100.         }
  101.         if (!defined(p1)) {
  102.             throw new DeveloperError('p1 is required.');
  103.         }
  104.         if (!defined(p2)) {
  105.             throw new DeveloperError('p2 is required.');
  106.         }
  107.         //>>includeEnd('debug');
  109.         cullBackFaces = defaultValue(cullBackFaces, false);
  111.         var origin = ray.origin;
  112.         var direction = ray.direction;
  114.         var edge0 = Cartesian3.subtract(p1, p0, scratchEdge0);
  115.         var edge1 = Cartesian3.subtract(p2, p0, scratchEdge1);
  117.         var p = Cartesian3.cross(direction, edge1, scratchPVec);
  118.         var det = Cartesian3.dot(edge0, p);
  120.         var tvec;
  121.         var q;
  123.         var u;
  124.         var v;
  125.         var t;
  127.         if (cullBackFaces) {
  128.             if (det < CesiumMath.EPSILON6) {
  129.                 return undefined;
  130.             }
  132.             tvec = Cartesian3.subtract(origin, p0, scratchTVec);
  133.             u = Cartesian3.dot(tvec, p);
  134.             if (u < 0.0 || u > det) {
  135.                 return undefined;
  136.             }
  138.             q = Cartesian3.cross(tvec, edge0, scratchQVec);
  140.             v = Cartesian3.dot(direction, q);
  141.             if (v < 0.0 || u + v > det) {
  142.                 return undefined;
  143.             }
  145.             t = Cartesian3.dot(edge1, q) / det;
  146.         } else {
  147.             if (Math.abs(det) < CesiumMath.EPSILON6) {
  148.                 return undefined;
  149.             }
  150.             var invDet = 1.0 / det;
  152.             tvec = Cartesian3.subtract(origin, p0, scratchTVec);
  153.             u = Cartesian3.dot(tvec, p) * invDet;
  154.             if (u < 0.0 || u > 1.0) {
  155.                 return undefined;
  156.             }
  158.             q = Cartesian3.cross(tvec, edge0, scratchQVec);
  160.             v = Cartesian3.dot(direction, q) * invDet;
  161.             if (v < 0.0 || u + v > 1.0) {
  162.                 return undefined;
  163.             }
  165.             t = Cartesian3.dot(edge1, q) * invDet;
  166.         }
  168.         return t;
  169.     };
  171.     /**
  172.      * Computes the intersection of a ray and a triangle as a Cartesian3 coordinate.
  173.      * @memberof IntersectionTests
  174.      *
  175.      * @param {Ray} ray The ray.
  176.      * @param {Cartesian3} p0 The first vertex of the triangle.
  177.      * @param {Cartesian3} p1 The second vertex of the triangle.
  178.      * @param {Cartesian3} p2 The third vertex of the triangle.
  179.      * @param {Boolean} [cullBackFaces=false] If <code>true</code>, will only compute an intersection with the front face of the triangle
  180.      *                  and return undefined for intersections with the back face.
  181.      * @param {Cartesian3} [result] The <code>Cartesian3</code> onto which to store the result.
  182.      * @returns {Cartesian3} The intersection point or undefined if there is no intersections.
  183.      */
  184.     IntersectionTests.rayTriangle = function(ray, p0, p1, p2, cullBackFaces, result) {
  185.         var t = IntersectionTests.rayTriangleParametric(ray, p0, p1, p2, cullBackFaces);
  186.         if (!defined(t) || t < 0.0) {
  187.             return undefined;
  188.         }
  190.         if (!defined(result)) {
  191.             result = new Cartesian3();
  192.         }
  194.         Cartesian3.multiplyByScalar(ray.direction, t, result);
  195.         return Cartesian3.add(ray.origin, result, result);
  196.     };
  198.     var scratchLineSegmentTriangleRay = new Ray();
  200.     /**
  201.      * Computes the intersection of a line segment and a triangle.
  202.      * @memberof IntersectionTests
  203.      *
  204.      * @param {Cartesian3} v0 The an end point of the line segment.
  205.      * @param {Cartesian3} v1 The other end point of the line segment.
  206.      * @param {Cartesian3} p0 The first vertex of the triangle.
  207.      * @param {Cartesian3} p1 The second vertex of the triangle.
  208.      * @param {Cartesian3} p2 The third vertex of the triangle.
  209.      * @param {Boolean} [cullBackFaces=false] If <code>true</code>, will only compute an intersection with the front face of the triangle
  210.      *                  and return undefined for intersections with the back face.
  211.      * @param {Cartesian3} [result] The <code>Cartesian3</code> onto which to store the result.
  212.      * @returns {Cartesian3} The intersection point or undefined if there is no intersections.
  213.      */
  214.     IntersectionTests.lineSegmentTriangle = function(v0, v1, p0, p1, p2, cullBackFaces, result) {
  215.         //>>includeStart('debug', pragmas.debug);
  216.         if (!defined(v0)) {
  217.             throw new DeveloperError('v0 is required.');
  218.         }
  219.         if (!defined(v1)) {
  220.             throw new DeveloperError('v1 is required.');
  221.         }
  222.         if (!defined(p0)) {
  223.             throw new DeveloperError('p0 is required.');
  224.         }
  225.         if (!defined(p1)) {
  226.             throw new DeveloperError('p1 is required.');
  227.         }
  228.         if (!defined(p2)) {
  229.             throw new DeveloperError('p2 is required.');
  230.         }
  231.         //>>includeEnd('debug');
  233.         var ray = scratchLineSegmentTriangleRay;
  234.         Cartesian3.clone(v0, ray.origin);
  235.         Cartesian3.subtract(v1, v0, ray.direction);
  236.         Cartesian3.normalize(ray.direction, ray.direction);
  238.         var t = IntersectionTests.rayTriangleParametric(ray, p0, p1, p2, cullBackFaces);
  239.         if (!defined(t) || t < 0.0 || t > Cartesian3.distance(v0, v1)) {
  240.             return undefined;
  241.         }
  243.         if (!defined(result)) {
  244.             result = new Cartesian3();
  245.         }
  247.         Cartesian3.multiplyByScalar(ray.direction, t, result);
  248.         return Cartesian3.add(ray.origin, result, result);
  249.     };
  251.     function solveQuadratic(a, b, c, result) {
  252.         var det = b * b - 4.0 * a * c;
  253.         if (det < 0.0) {
  254.             return undefined;
  255.         } else if (det > 0.0) {
  256.             var denom = 1.0 / (2.0 * a);
  257.             var disc = Math.sqrt(det);
  258.             var root0 = (-b + disc) * denom;
  259.             var root1 = (-b - disc) * denom;
  261.             if (root0 < root1) {
  262.                 result.root0 = root0;
  263.                 result.root1 = root1;
  264.             } else {
  265.                 result.root0 = root1;
  266.                 result.root1 = root0;
  267.             }
  269.             return result;
  270.         }
  272.         var root = -b / (2.0 * a);
  273.         if (root === 0.0) {
  274.             return undefined;
  275.         }
  277.         result.root0 = result.root1 = root;
  278.         return result;
  279.     }
  281.     var raySphereRoots = {
  282.         root0 : 0.0,
  283.         root1 : 0.0
  284.     };
  286.     function raySphere(ray, sphere, result) {
  287.         if (!defined(result)) {
  288.             result = {};
  289.         }
  291.         var origin = ray.origin;
  292.         var direction = ray.direction;
  294.         var center = sphere.center;
  295.         var radiusSquared = sphere.radius * sphere.radius;
  297.         var diff = Cartesian3.subtract(origin, center, scratchPVec);
  299.         var a = Cartesian3.dot(direction, direction);
  300.         var b = 2.0 * Cartesian3.dot(direction, diff);
  301.         var c = Cartesian3.magnitudeSquared(diff) - radiusSquared;
  303.         var roots = solveQuadratic(a, b, c, raySphereRoots);
  304.         if (!defined(roots)) {
  305.             return undefined;
  306.         }
  308.         result.start = roots.root0;
  309.         result.stop = roots.root1;
  310.         return result;
  311.     }
  313.     /**
  314.      * Computes the intersection points of a ray with a sphere.
  315.      * @memberof IntersectionTests
  316.      *
  317.      * @param {Ray} ray The ray.
  318.      * @param {BoundingSphere} sphere The sphere.
  319.      * @param {Object} [result] The result onto which to store the result.
  320.      * @returns {Object} An object with the first (<code>start</code>) and the second (<code>stop</code>) intersection scalars for points along the ray or undefined if there are no intersections.
  321.      */
  322.     IntersectionTests.raySphere = function(ray, sphere, result) {
  323.         //>>includeStart('debug', pragmas.debug);
  324.         if (!defined(ray)) {
  325.             throw new DeveloperError('ray is required.');
  326.         }
  327.         if (!defined(sphere)) {
  328.             throw new DeveloperError('sphere is required.');
  329.         }
  330.         //>>includeEnd('debug');
  332.         result = raySphere(ray, sphere, result);
  333.         if (!defined(result) || result.stop < 0.0) {
  334.             return undefined;
  335.         }
  337.         result.start = Math.max(result.start, 0.0);
  338.         return result;
  339.     };
  341.     var scratchLineSegmentRay = new Ray();
  343.     /**
  344.      * Computes the intersection points of a line segment with a sphere.
  345.      * @memberof IntersectionTests
  346.      *
  347.      * @param {Cartesian3} p0 An end point of the line segment.
  348.      * @param {Cartesian3} p1 The other end point of the line segment.
  349.      * @param {BoundingSphere} sphere The sphere.
  350.      * @param {Object} [result] The result onto which to store the result.
  351.      * @returns {Object} An object with the first (<code>start</code>) and the second (<code>stop</code>) intersection scalars for points along the line segment or undefined if there are no intersections.
  352.      */
  353.     IntersectionTests.lineSegmentSphere = function(p0, p1, sphere, result) {
  354.         //>>includeStart('debug', pragmas.debug);
  355.         if (!defined(p0)) {
  356.             throw new DeveloperError('p0 is required.');
  357.         }
  358.         if (!defined(p1)) {
  359.             throw new DeveloperError('p1 is required.');
  360.         }
  361.         if (!defined(sphere)) {
  362.             throw new DeveloperError('sphere is required.');
  363.         }
  364.         //>>includeEnd('debug');
  366.         var ray = scratchLineSegmentRay;
  367.         Cartesian3.clone(p0, ray.origin);
  368.         var direction = Cartesian3.subtract(p1, p0, ray.direction);
  370.         var maxT = Cartesian3.magnitude(direction);
  371.         Cartesian3.normalize(direction, direction);
  373.         result = raySphere(ray, sphere, result);
  374.         if (!defined(result) || result.stop < 0.0 || result.start > maxT) {
  375.             return undefined;
  376.         }
  378.         result.start = Math.max(result.start, 0.0);
  379.         result.stop = Math.min(result.stop, maxT);
  380.         return result;
  381.     };
  383.     var scratchQ = new Cartesian3();
  384.     var scratchW = new Cartesian3();
  386.     /**
  387.      * Computes the intersection points of a ray with an ellipsoid.
  388.      *
  389.      * @param {Ray} ray The ray.
  390.      * @param {Ellipsoid} ellipsoid The ellipsoid.
  391.      * @returns {Object} An object with the first (<code>start</code>) and the second (<code>stop</code>) intersection scalars for points along the ray or undefined if there are no intersections.
  392.      */
  393.     IntersectionTests.rayEllipsoid = function(ray, ellipsoid) {
  394.         //>>includeStart('debug', pragmas.debug);
  395.         if (!defined(ray)) {
  396.             throw new DeveloperError('ray is required.');
  397.         }
  398.         if (!defined(ellipsoid)) {
  399.             throw new DeveloperError('ellipsoid is required.');
  400.         }
  401.         //>>includeEnd('debug');
  403.         var inverseRadii = ellipsoid.oneOverRadii;
  404.         var q = Cartesian3.multiplyComponents(inverseRadii, ray.origin, scratchQ);
  405.         var w = Cartesian3.multiplyComponents(inverseRadii, ray.direction, scratchW);
  407.         var q2 = Cartesian3.magnitudeSquared(q);
  408.         var qw = Cartesian3.dot(q, w);
  410.         var difference, w2, product, discriminant, temp;
  412.         if (q2 > 1.0) {
  413.             // Outside ellipsoid.
  414.             if (qw >= 0.0) {
  415.                 // Looking outward or tangent (0 intersections).
  416.                 return undefined;
  417.             }
  419.             // qw < 0.0.
  420.             var qw2 = qw * qw;
  421.             difference = q2 - 1.0; // Positively valued.
  422.             w2 = Cartesian3.magnitudeSquared(w);
  423.             product = w2 * difference;
  425.             if (qw2 < product) {
  426.                 // Imaginary roots (0 intersections).
  427.                 return undefined;
  428.             } else if (qw2 > product) {
  429.                 // Distinct roots (2 intersections).
  430.                 discriminant = qw * qw - product;
  431.                 temp = -qw + Math.sqrt(discriminant); // Avoid cancellation.
  432.                 var root0 = temp / w2;
  433.                 var root1 = difference / temp;
  434.                 if (root0 < root1) {
  435.                     return {
  436.                         start : root0,
  437.                         stop : root1
  438.                     };
  439.                 }
  441.                 return {
  442.                     start : root1,
  443.                     stop : root0
  444.                 };
  445.             } else {
  446.                 // qw2 == product.  Repeated roots (2 intersections).
  447.                 var root = Math.sqrt(difference / w2);
  448.                 return {
  449.                     start : root,
  450.                     stop : root
  451.                 };
  452.             }
  453.         } else if (q2 < 1.0) {
  454.             // Inside ellipsoid (2 intersections).
  455.             difference = q2 - 1.0; // Negatively valued.
  456.             w2 = Cartesian3.magnitudeSquared(w);
  457.             product = w2 * difference; // Negatively valued.
  459.             discriminant = qw * qw - product;
  460.             temp = -qw + Math.sqrt(discriminant); // Positively valued.
  461.             return {
  462.                 start : 0.0,
  463.                 stop : temp / w2
  464.             };
  465.         } else {
  466.             // q2 == 1.0. On ellipsoid.
  467.             if (qw < 0.0) {
  468.                 // Looking inward.
  469.                 w2 = Cartesian3.magnitudeSquared(w);
  470.                 return {
  471.                     start : 0.0,
  472.                     stop : -qw / w2
  473.                 };
  474.             }
  476.             // qw >= 0.0.  Looking outward or tangent.
  477.             return undefined;
  478.         }
  479.     };
  481.     function addWithCancellationCheck(left, right, tolerance) {
  482.         var difference = left + right;
  483.         if ((CesiumMath.sign(left) !== CesiumMath.sign(right)) &&
  484.                 Math.abs(difference / Math.max(Math.abs(left), Math.abs(right))) < tolerance) {
  485.             return 0.0;
  486.         }
  488.         return difference;
  489.     }
  491.     function quadraticVectorExpression(A, b, c, x, w) {
  492.         var xSquared = x * x;
  493.         var wSquared = w * w;
  495.         var l2 = (A[Matrix3.COLUMN1ROW1] - A[Matrix3.COLUMN2ROW2]) * wSquared;
  496.         var l1 = w * (x * addWithCancellationCheck(A[Matrix3.COLUMN1ROW0], A[Matrix3.COLUMN0ROW1], CesiumMath.EPSILON15) + b.y);
  497.         var l0 = (A[Matrix3.COLUMN0ROW0] * xSquared + A[Matrix3.COLUMN2ROW2] * wSquared) + x * b.x + c;
  499.         var r1 = wSquared * addWithCancellationCheck(A[Matrix3.COLUMN2ROW1], A[Matrix3.COLUMN1ROW2], CesiumMath.EPSILON15);
  500.         var r0 = w * (x * addWithCancellationCheck(A[Matrix3.COLUMN2ROW0], A[Matrix3.COLUMN0ROW2]) + b.z);
  502.         var cosines;
  503.         var solutions = [];
  504.         if (r0 === 0.0 && r1 === 0.0) {
  505.             cosines = QuadraticRealPolynomial.computeRealRoots(l2, l1, l0);
  506.             if (cosines.length === 0) {
  507.                 return solutions;
  508.             }
  510.             var cosine0 = cosines[0];
  511.             var sine0 = Math.sqrt(Math.max(1.0 - cosine0 * cosine0, 0.0));
  512.             solutions.push(new Cartesian3(x, w * cosine0, w * -sine0));
  513.             solutions.push(new Cartesian3(x, w * cosine0, w * sine0));
  515.             if (cosines.length === 2) {
  516.                 var cosine1 = cosines[1];
  517.                 var sine1 = Math.sqrt(Math.max(1.0 - cosine1 * cosine1, 0.0));
  518.                 solutions.push(new Cartesian3(x, w * cosine1, w * -sine1));
  519.                 solutions.push(new Cartesian3(x, w * cosine1, w * sine1));
  520.             }
  522.             return solutions;
  523.         }
  525.         var r0Squared = r0 * r0;
  526.         var r1Squared = r1 * r1;
  527.         var l2Squared = l2 * l2;
  528.         var r0r1 = r0 * r1;
  530.         var c4 = l2Squared + r1Squared;
  531.         var c3 = 2.0 * (l1 * l2 + r0r1);
  532.         var c2 = 2.0 * l0 * l2 + l1 * l1 - r1Squared + r0Squared;
  533.         var c1 = 2.0 * (l0 * l1 - r0r1);
  534.         var c0 = l0 * l0 - r0Squared;
  536.         if (c4 === 0.0 && c3 === 0.0 && c2 === 0.0 && c1 === 0.0) {
  537.             return solutions;
  538.         }
  540.         cosines = QuarticRealPolynomial.computeRealRoots(c4, c3, c2, c1, c0);
  541.         var length = cosines.length;
  542.         if (length === 0) {
  543.             return solutions;
  544.         }
  546.         for ( var i = 0; i < length; ++i) {
  547.             var cosine = cosines[i];
  548.             var cosineSquared = cosine * cosine;
  549.             var sineSquared = Math.max(1.0 - cosineSquared, 0.0);
  550.             var sine = Math.sqrt(sineSquared);
  552.             //var left = l2 * cosineSquared + l1 * cosine + l0;
  553.             var left;
  554.             if (CesiumMath.sign(l2) === CesiumMath.sign(l0)) {
  555.                 left = addWithCancellationCheck(l2 * cosineSquared + l0, l1 * cosine, CesiumMath.EPSILON12);
  556.             } else if (CesiumMath.sign(l0) === CesiumMath.sign(l1 * cosine)) {
  557.                 left = addWithCancellationCheck(l2 * cosineSquared, l1 * cosine + l0, CesiumMath.EPSILON12);
  558.             } else {
  559.                 left = addWithCancellationCheck(l2 * cosineSquared + l1 * cosine, l0, CesiumMath.EPSILON12);
  560.             }
  562.             var right = addWithCancellationCheck(r1 * cosine, r0, CesiumMath.EPSILON15);
  563.             var product = left * right;
  565.             if (product < 0.0) {
  566.                 solutions.push(new Cartesian3(x, w * cosine, w * sine));
  567.             } else if (product > 0.0) {
  568.                 solutions.push(new Cartesian3(x, w * cosine, w * -sine));
  569.             } else if (sine !== 0.0) {
  570.                 solutions.push(new Cartesian3(x, w * cosine, w * -sine));
  571.                 solutions.push(new Cartesian3(x, w * cosine, w * sine));
  572.                 ++i;
  573.             } else {
  574.                 solutions.push(new Cartesian3(x, w * cosine, w * sine));
  575.             }
  576.         }
  578.         return solutions;
  579.     }
  581.     var firstAxisScratch = new Cartesian3();
  582.     var secondAxisScratch = new Cartesian3();
  583.     var thirdAxisScratch = new Cartesian3();
  584.     var referenceScratch = new Cartesian3();
  585.     var bCart = new Cartesian3();
  586.     var bScratch = new Matrix3();
  587.     var btScratch = new Matrix3();
  588.     var diScratch = new Matrix3();
  589.     var dScratch = new Matrix3();
  590.     var cScratch = new Matrix3();
  591.     var tempMatrix = new Matrix3();
  592.     var aScratch = new Matrix3();
  593.     var sScratch = new Cartesian3();
  594.     var closestScratch = new Cartesian3();
  595.     var surfPointScratch = new Cartographic();
  597.     /**
  598.      * Provides the point along the ray which is nearest to the ellipsoid.
  599.      *
  600.      * @param {Ray} ray The ray.
  601.      * @param {Ellipsoid} ellipsoid The ellipsoid.
  602.      * @returns {Cartesian3} The nearest planetodetic point on the ray.
  603.      */
  604.     IntersectionTests.grazingAltitudeLocation = function(ray, ellipsoid) {
  605.         //>>includeStart('debug', pragmas.debug);
  606.         if (!defined(ray)) {
  607.             throw new DeveloperError('ray is required.');
  608.         }
  609.         if (!defined(ellipsoid)) {
  610.             throw new DeveloperError('ellipsoid is required.');
  611.         }
  612.         //>>includeEnd('debug');
  614.         var position = ray.origin;
  615.         var direction = ray.direction;
  617.         if (!Cartesian3.equals(position, Cartesian3.ZERO)) {
  618.             var normal = ellipsoid.geodeticSurfaceNormal(position, firstAxisScratch);
  619.             if (Cartesian3.dot(direction, normal) >= 0.0) { // The location provided is the closest point in altitude
  620.                 return position;
  621.             }
  622.         }
  624.         var intersects = defined(this.rayEllipsoid(ray, ellipsoid));
  626.         // Compute the scaled direction vector.
  627.         var f = ellipsoid.transformPositionToScaledSpace(direction, firstAxisScratch);
  629.         // Constructs a basis from the unit scaled direction vector. Construct its rotation and transpose.
  630.         var firstAxis = Cartesian3.normalize(f, f);
  631.         var reference = Cartesian3.mostOrthogonalAxis(f, referenceScratch);
  632.         var secondAxis = Cartesian3.normalize(Cartesian3.cross(reference, firstAxis, secondAxisScratch), secondAxisScratch);
  633.         var thirdAxis  = Cartesian3.normalize(Cartesian3.cross(firstAxis, secondAxis, thirdAxisScratch), thirdAxisScratch);
  634.         var B = bScratch;
  635.         B[0] = firstAxis.x;
  636.         B[1] = firstAxis.y;
  637.         B[2] = firstAxis.z;
  638.         B[3] = secondAxis.x;
  639.         B[4] = secondAxis.y;
  640.         B[5] = secondAxis.z;
  641.         B[6] = thirdAxis.x;
  642.         B[7] = thirdAxis.y;
  643.         B[8] = thirdAxis.z;
  645.         var B_T = Matrix3.transpose(B, btScratch);
  647.         // Get the scaling matrix and its inverse.
  648.         var D_I = Matrix3.fromScale(ellipsoid.radii, diScratch);
  649.         var D = Matrix3.fromScale(ellipsoid.oneOverRadii, dScratch);
  651.         var C = cScratch;
  652.         C[0] = 0.0;
  653.         C[1] = -direction.z;
  654.         C[2] = direction.y;
  655.         C[3] = direction.z;
  656.         C[4] = 0.0;
  657.         C[5] = -direction.x;
  658.         C[6] = -direction.y;
  659.         C[7] = direction.x;
  660.         C[8] = 0.0;
  662.         var temp = Matrix3.multiply(Matrix3.multiply(B_T, D, tempMatrix), C, tempMatrix);
  663.         var A = Matrix3.multiply(Matrix3.multiply(temp, D_I, aScratch), B, aScratch);
  664.         var b = Matrix3.multiplyByVector(temp, position, bCart);
  666.         // Solve for the solutions to the expression in standard form:
  667.         var solutions = quadraticVectorExpression(A, Cartesian3.negate(b, firstAxisScratch), 0.0, 0.0, 1.0);
  669.         var s;
  670.         var altitude;
  671.         var length = solutions.length;
  672.         if (length > 0) {
  673.             var closest = Cartesian3.clone(Cartesian3.ZERO, closestScratch);
  674.             var maximumValue = Number.NEGATIVE_INFINITY;
  676.             for ( var i = 0; i < length; ++i) {
  677.                 s = Matrix3.multiplyByVector(D_I, Matrix3.multiplyByVector(B, solutions[i], sScratch), sScratch);
  678.                 var v = Cartesian3.normalize(Cartesian3.subtract(s, position, referenceScratch), referenceScratch);
  679.                 var dotProduct = Cartesian3.dot(v, direction);
  681.                 if (dotProduct > maximumValue) {
  682.                     maximumValue = dotProduct;
  683.                     closest = Cartesian3.clone(s, closest);
  684.                 }
  685.             }
  687.             var surfacePoint = ellipsoid.cartesianToCartographic(closest, surfPointScratch);
  688.             maximumValue = CesiumMath.clamp(maximumValue, 0.0, 1.0);
  689.             altitude = Cartesian3.magnitude(Cartesian3.subtract(closest, position, referenceScratch)) * Math.sqrt(1.0 - maximumValue * maximumValue);
  690.             altitude = intersects ? -altitude : altitude;
  691.             surfacePoint.height = altitude;
  692.             return ellipsoid.cartographicToCartesian(surfacePoint, new Cartesian3());
  693.         }
  695.         return undefined;
  696.     };
  698.     var lineSegmentPlaneDifference = new Cartesian3();
  700.     /**
  701.      * Computes the intersection of a line segment and a plane.
  702.      *
  703.      * @param {Cartesian3} endPoint0 An end point of the line segment.
  704.      * @param {Cartesian3} endPoint1 The other end point of the line segment.
  705.      * @param {Plane} plane The plane.
  706.      * @param {Cartesian3} [result] The object onto which to store the result.
  707.      * @returns {Cartesian3} The intersection point or undefined if there is no intersection.
  708.      *
  709.      * @example
  710.      * var origin = Cesium.Cartesian3.fromDegrees(-75.59777, 40.03883);
  711.      * var normal = ellipsoid.geodeticSurfaceNormal(origin);
  712.      * var plane = Cesium.Plane.fromPointNormal(origin, normal);
  713.      *
  714.      * var p0 = new Cesium.Cartesian3(...);
  715.      * var p1 = new Cesium.Cartesian3(...);
  716.      *
  717.      * // find the intersection of the line segment from p0 to p1 and the tangent plane at origin.
  718.      * var intersection = Cesium.IntersectionTests.lineSegmentPlane(p0, p1, plane);
  719.      */
  720.     IntersectionTests.lineSegmentPlane = function(endPoint0, endPoint1, plane, result) {
  721.         //>>includeStart('debug', pragmas.debug);
  722.         if (!defined(endPoint0)) {
  723.             throw new DeveloperError('endPoint0 is required.');
  724.         }
  725.         if (!defined(endPoint1)) {
  726.             throw new DeveloperError('endPoint1 is required.');
  727.         }
  728.         if (!defined(plane)) {
  729.             throw new DeveloperError('plane is required.');
  730.         }
  731.         //>>includeEnd('debug');
  733.         if (!defined(result)) {
  734.             result = new Cartesian3();
  735.         }
  737.         var difference = Cartesian3.subtract(endPoint1, endPoint0, lineSegmentPlaneDifference);
  738.         var normal = plane.normal;
  739.         var nDotDiff = Cartesian3.dot(normal, difference);
  741.         // check if the segment and plane are parallel
  742.         if (Math.abs(nDotDiff) < CesiumMath.EPSILON6) {
  743.             return undefined;
  744.         }
  746.         var nDotP0 = Cartesian3.dot(normal, endPoint0);
  747.         var t = -(plane.distance + nDotP0) / nDotDiff;
  749.         // intersection only if t is in [0, 1]
  750.         if (t < 0.0 || t > 1.0) {
  751.             return undefined;
  752.         }
  754.         // intersection is endPoint0 + t * (endPoint1 - endPoint0)
  755.         Cartesian3.multiplyByScalar(difference, t, result);
  756.         Cartesian3.add(endPoint0, result, result);
  757.         return result;
  758.     };
  760.     /**
  761.      * Computes the intersection of a triangle and a plane
  762.      *
  763.      * @param {Cartesian3} p0 First point of the triangle
  764.      * @param {Cartesian3} p1 Second point of the triangle
  765.      * @param {Cartesian3} p2 Third point of the triangle
  766.      * @param {Plane} plane Intersection plane
  767.      * @returns {Object} An object with properties <code>positions</code> and <code>indices</code>, which are arrays that represent three triangles that do not cross the plane. (Undefined if no intersection exists)
  768.      *
  769.      * @example
  770.      * var origin = Cesium.Cartesian3.fromDegrees(-75.59777, 40.03883);
  771.      * var normal = ellipsoid.geodeticSurfaceNormal(origin);
  772.      * var plane = Cesium.Plane.fromPointNormal(origin, normal);
  773.      *
  774.      * var p0 = new Cesium.Cartesian3(...);
  775.      * var p1 = new Cesium.Cartesian3(...);
  776.      * var p2 = new Cesium.Cartesian3(...);
  777.      *
  778.      * // convert the triangle composed of points (p0, p1, p2) to three triangles that don't cross the plane
  779.      * var triangles = Cesium.IntersectionTests.trianglePlaneIntersection(p0, p1, p2, plane);
  780.      */
  781.     IntersectionTests.trianglePlaneIntersection = function(p0, p1, p2, plane) {
  782.         //>>includeStart('debug', pragmas.debug);
  783.         if ((!defined(p0)) ||
  784.             (!defined(p1)) ||
  785.             (!defined(p2)) ||
  786.             (!defined(plane))) {
  787.             throw new DeveloperError('p0, p1, p2, and plane are required.');
  788.         }
  789.         //>>includeEnd('debug');
  791.         var planeNormal = plane.normal;
  792.         var planeD = plane.distance;
  793.         var p0Behind = (Cartesian3.dot(planeNormal, p0) + planeD) < 0.0;
  794.         var p1Behind = (Cartesian3.dot(planeNormal, p1) + planeD) < 0.0;
  795.         var p2Behind = (Cartesian3.dot(planeNormal, p2) + planeD) < 0.0;
  796.         // Given these dots products, the calls to lineSegmentPlaneIntersection
  797.         // always have defined results.
  799.         var numBehind = 0;
  800.         numBehind += p0Behind ? 1 : 0;
  801.         numBehind += p1Behind ? 1 : 0;
  802.         numBehind += p2Behind ? 1 : 0;
  804.         var u1, u2;
  805.         if (numBehind === 1 || numBehind === 2) {
  806.             u1 = new Cartesian3();
  807.             u2 = new Cartesian3();
  808.         }
  810.         if (numBehind === 1) {
  811.             if (p0Behind) {
  812.                 IntersectionTests.lineSegmentPlane(p0, p1, plane, u1);
  813.                 IntersectionTests.lineSegmentPlane(p0, p2, plane, u2);
  815.                 return {
  816.                     positions : [p0, p1, p2, u1, u2 ],
  817.                     indices : [
  818.                         // Behind
  819.                         0, 3, 4,
  821.                         // In front
  822.                         1, 2, 4,
  823.                         1, 4, 3
  824.                     ]
  825.                 };
  826.             } else if (p1Behind) {
  827.                 IntersectionTests.lineSegmentPlane(p1, p2, plane, u1);
  828.                 IntersectionTests.lineSegmentPlane(p1, p0, plane, u2);
  830.                 return {
  831.                     positions : [p0, p1, p2, u1, u2 ],
  832.                     indices : [
  833.                         // Behind
  834.                         1, 3, 4,
  836.                         // In front
  837.                         2, 0, 4,
  838.                         2, 4, 3
  839.                     ]
  840.                 };
  841.             } else if (p2Behind) {
  842.                 IntersectionTests.lineSegmentPlane(p2, p0, plane, u1);
  843.                 IntersectionTests.lineSegmentPlane(p2, p1, plane, u2);
  845.                 return {
  846.                     positions : [p0, p1, p2, u1, u2 ],
  847.                     indices : [
  848.                         // Behind
  849.                         2, 3, 4,
  851.                         // In front
  852.                         0, 1, 4,
  853.                         0, 4, 3
  854.                     ]
  855.                 };
  856.             }
  857.         } else if (numBehind === 2) {
  858.             if (!p0Behind) {
  859.                 IntersectionTests.lineSegmentPlane(p1, p0, plane, u1);
  860.                 IntersectionTests.lineSegmentPlane(p2, p0, plane, u2);
  862.                 return {
  863.                     positions : [p0, p1, p2, u1, u2 ],
  864.                     indices : [
  865.                         // Behind
  866.                         1, 2, 4,
  867.                         1, 4, 3,
  869.                         // In front
  870.                         0, 3, 4
  871.                     ]
  872.                 };
  873.             } else if (!p1Behind) {
  874.                 IntersectionTests.lineSegmentPlane(p2, p1, plane, u1);
  875.                 IntersectionTests.lineSegmentPlane(p0, p1, plane, u2);
  877.                 return {
  878.                     positions : [p0, p1, p2, u1, u2 ],
  879.                     indices : [
  880.                         // Behind
  881.                         2, 0, 4,
  882.                         2, 4, 3,
  884.                         // In front
  885.                         1, 3, 4
  886.                     ]
  887.                 };
  888.             } else if (!p2Behind) {
  889.                 IntersectionTests.lineSegmentPlane(p0, p2, plane, u1);
  890.                 IntersectionTests.lineSegmentPlane(p1, p2, plane, u2);
  892.                 return {
  893.                     positions : [p0, p1, p2, u1, u2 ],
  894.                     indices : [
  895.                         // Behind
  896.                         0, 1, 4,
  897.                         0, 4, 3,
  899.                         // In front
  900.                         2, 3, 4
  901.                     ]
  902.                 };
  903.             }
  904.         }
  906.         // if numBehind is 3, the triangle is completely behind the plane;
  907.         // otherwise, it is completely in front (numBehind is 0).
  908.         return undefined;
  909.     };
  911.     return IntersectionTests;
  912. });