text: import AxisAlignedBoundingBox from './AxisAlignedBoundingBox.js';
  import BoundingSphere from './BoundingSphere.js';
  import Cartesian2 from './Cartesian2.js';
  import Cartesian3 from './Cartesian3.js';
  import defaultValue from './defaultValue.js';
  import defined from './defined.js';
  import DeveloperError from './DeveloperError.js';
  import Ellipsoid from './Ellipsoid.js';
  import EllipsoidalOccluder from './EllipsoidalOccluder.js';
  import freezeObject from './freezeObject.js';
  import CesiumMath from './Math.js';
  import Matrix4 from './Matrix4.js';
  import OrientedBoundingBox from './OrientedBoundingBox.js';
  import Rectangle from './Rectangle.js';
  import TerrainEncoding from './TerrainEncoding.js';
  import Transforms from './Transforms.js';
  import WebMercatorProjection from './WebMercatorProjection.js';
  
      /**
       * Contains functions to create a mesh from a heightmap image.
       *
       * @exports HeightmapTessellator
       *
       * @private
       */
      var HeightmapTessellator = {};
  
      /**
       * The default structure of a heightmap, as given to {@link HeightmapTessellator.computeVertices}.
       *
       * @constant
       */
      HeightmapTessellator.DEFAULT_STRUCTURE = freezeObject({
          heightScale : 1.0,
          heightOffset : 0.0,
          elementsPerHeight : 1,
          stride : 1,
          elementMultiplier : 256.0,
          isBigEndian : false
      });
  
      var cartesian3Scratch = new Cartesian3();
      var matrix4Scratch = new Matrix4();
      var minimumScratch = new Cartesian3();
      var maximumScratch = new Cartesian3();
  
      /**
       * Fills an array of vertices from a heightmap image.
       *
       * @param {Object} options Object with the following properties:
       * @param {TypedArray} options.heightmap The heightmap to tessellate.
       * @param {Number} options.width The width of the heightmap, in height samples.
       * @param {Number} options.height The height of the heightmap, in height samples.
       * @param {Number} options.skirtHeight The height of skirts to drape at the edges of the heightmap.
       * @param {Rectangle} options.nativeRectangle A rectangle in the native coordinates of the heightmap's projection.  For
       *                 a heightmap with a geographic projection, this is degrees.  For the web mercator
       *                 projection, this is meters.
       * @param {Number} [options.exaggeration=1.0] The scale used to exaggerate the terrain.
       * @param {Rectangle} [options.rectangle] The rectangle covered by the heightmap, in geodetic coordinates with north, south, east and
       *                 west properties in radians.  Either rectangle or nativeRectangle must be provided.  If both
       *                 are provided, they're assumed to be consistent.
       * @param {Boolean} [options.isGeographic=true] True if the heightmap uses a {@link GeographicProjection}, or false if it uses
       *                  a {@link WebMercatorProjection}.
       * @param {Cartesian3} [options.relativeToCenter=Cartesian3.ZERO] The positions will be computed as <code>Cartesian3.subtract(worldPosition, relativeToCenter)</code>.
       * @param {Ellipsoid} [options.ellipsoid=Ellipsoid.WGS84] The ellipsoid to which the heightmap applies.
       * @param {Object} [options.structure] An object describing the structure of the height data.
       * @param {Number} [options.structure.heightScale=1.0] The factor by which to multiply height samples in order to obtain
       *                 the height above the heightOffset, in meters.  The heightOffset is added to the resulting
       *                 height after multiplying by the scale.
       * @param {Number} [options.structure.heightOffset=0.0] The offset to add to the scaled height to obtain the final
       *                 height in meters.  The offset is added after the height sample is multiplied by the
       *                 heightScale.
       * @param {Number} [options.structure.elementsPerHeight=1] The number of elements in the buffer that make up a single height
       *                 sample.  This is usually 1, indicating that each element is a separate height sample.  If
       *                 it is greater than 1, that number of elements together form the height sample, which is
       *                 computed according to the structure.elementMultiplier and structure.isBigEndian properties.
       * @param {Number} [options.structure.stride=1] The number of elements to skip to get from the first element of
       *                 one height to the first element of the next height.
       * @param {Number} [options.structure.elementMultiplier=256.0] The multiplier used to compute the height value when the
       *                 stride property is greater than 1.  For example, if the stride is 4 and the strideMultiplier
       *                 is 256, the height is computed as follows:
       *                 `height = buffer[index] + buffer[index + 1] * 256 + buffer[index + 2] * 256 * 256 + buffer[index + 3] * 256 * 256 * 256`
       *                 This is assuming that the isBigEndian property is false.  If it is true, the order of the
       *                 elements is reversed.
       * @param {Number} [options.structure.lowestEncodedHeight] The lowest value that can be stored in the height buffer.  Any heights that are lower
       *                 than this value after encoding with the `heightScale` and `heightOffset` are clamped to this value.  For example, if the height
       *                 buffer is a `Uint16Array`, this value should be 0 because a `Uint16Array` cannot store negative numbers.  If this parameter is
       *                 not specified, no minimum value is enforced.
       * @param {Number} [options.structure.highestEncodedHeight] The highest value that can be stored in the height buffer.  Any heights that are higher
       *                 than this value after encoding with the `heightScale` and `heightOffset` are clamped to this value.  For example, if the height
       *                 buffer is a `Uint16Array`, this value should be `256 * 256 - 1` or 65535 because a `Uint16Array` cannot store numbers larger
       *                 than 65535.  If this parameter is not specified, no maximum value is enforced.
       * @param {Boolean} [options.structure.isBigEndian=false] Indicates endianness of the elements in the buffer when the
       *                  stride property is greater than 1.  If this property is false, the first element is the
       *                  low-order element.  If it is true, the first element is the high-order element.
       *
       * @example
       * var width = 5;
       * var height = 5;
       * var statistics = Cesium.HeightmapTessellator.computeVertices({
       *     heightmap : [1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0],
       *     width : width,
       *     height : height,
       *     skirtHeight : 0.0,
       *     nativeRectangle : {
       *         west : 10.0,
       *         east : 20.0,
       *         south : 30.0,
       *         north : 40.0
       *     }
       * });
       *
       * var encoding = statistics.encoding;
       * var position = encoding.decodePosition(statistics.vertices, index * encoding.getStride());
       */
      HeightmapTessellator.computeVertices = function(options) {
          //>>includeStart('debug', pragmas.debug);
          if (!defined(options) || !defined(options.heightmap)) {
              throw new DeveloperError('options.heightmap is required.');
          }
          if (!defined(options.width) || !defined(options.height)) {
              throw new DeveloperError('options.width and options.height are required.');
          }
          if (!defined(options.nativeRectangle)) {
              throw new DeveloperError('options.nativeRectangle is required.');
          }
          if (!defined(options.skirtHeight)) {
              throw new DeveloperError('options.skirtHeight is required.');
          }
          //>>includeEnd('debug');
  
          // This function tends to be a performance hotspot for terrain rendering,
          // so it employs a lot of inlining and unrolling as an optimization.
          // In particular, the functionality of Ellipsoid.cartographicToCartesian
          // is inlined.
  
          var cos = Math.cos;
          var sin = Math.sin;
          var sqrt = Math.sqrt;
          var atan = Math.atan;
          var exp = Math.exp;
          var piOverTwo = CesiumMath.PI_OVER_TWO;
          var toRadians = CesiumMath.toRadians;
  
          var heightmap = options.heightmap;
          var width = options.width;
          var height = options.height;
          var skirtHeight = options.skirtHeight;
  
          var isGeographic = defaultValue(options.isGeographic, true);
          var ellipsoid = defaultValue(options.ellipsoid, Ellipsoid.WGS84);
  
          var oneOverGlobeSemimajorAxis = 1.0 / ellipsoid.maximumRadius;
  
          var nativeRectangle = options.nativeRectangle;
  
          var geographicWest;
          var geographicSouth;
          var geographicEast;
          var geographicNorth;
  
          var rectangle = options.rectangle;
          if (!defined(rectangle)) {
              if (isGeographic) {
                  geographicWest = toRadians(nativeRectangle.west);
                  geographicSouth = toRadians(nativeRectangle.south);
                  geographicEast = toRadians(nativeRectangle.east);
                  geographicNorth = toRadians(nativeRectangle.north);
              } else {
                  geographicWest = nativeRectangle.west * oneOverGlobeSemimajorAxis;
                  geographicSouth = piOverTwo - (2.0 * atan(exp(-nativeRectangle.south * oneOverGlobeSemimajorAxis)));
                  geographicEast = nativeRectangle.east * oneOverGlobeSemimajorAxis;
                  geographicNorth = piOverTwo - (2.0 * atan(exp(-nativeRectangle.north * oneOverGlobeSemimajorAxis)));
              }
          } else {
              geographicWest = rectangle.west;
              geographicSouth = rectangle.south;
              geographicEast = rectangle.east;
              geographicNorth = rectangle.north;
          }
  
          var relativeToCenter = options.relativeToCenter;
          var hasRelativeToCenter = defined(relativeToCenter);
          relativeToCenter = hasRelativeToCenter ? relativeToCenter : Cartesian3.ZERO;
          var exaggeration = defaultValue(options.exaggeration, 1.0);
          var includeWebMercatorT = defaultValue(options.includeWebMercatorT, false);
  
          var structure = defaultValue(options.structure, HeightmapTessellator.DEFAULT_STRUCTURE);
          var heightScale = defaultValue(structure.heightScale, HeightmapTessellator.DEFAULT_STRUCTURE.heightScale);
          var heightOffset = defaultValue(structure.heightOffset, HeightmapTessellator.DEFAULT_STRUCTURE.heightOffset);
          var elementsPerHeight = defaultValue(structure.elementsPerHeight, HeightmapTessellator.DEFAULT_STRUCTURE.elementsPerHeight);
          var stride = defaultValue(structure.stride, HeightmapTessellator.DEFAULT_STRUCTURE.stride);
          var elementMultiplier = defaultValue(structure.elementMultiplier, HeightmapTessellator.DEFAULT_STRUCTURE.elementMultiplier);
          var isBigEndian = defaultValue(structure.isBigEndian, HeightmapTessellator.DEFAULT_STRUCTURE.isBigEndian);
  
          var rectangleWidth = Rectangle.computeWidth(nativeRectangle);
          var rectangleHeight = Rectangle.computeHeight(nativeRectangle);
  
          var granularityX = rectangleWidth / (width - 1);
          var granularityY = rectangleHeight / (height - 1);
  
          if (!isGeographic) {
              rectangleWidth *= oneOverGlobeSemimajorAxis;
              rectangleHeight *= oneOverGlobeSemimajorAxis;
          }
  
          var radiiSquared = ellipsoid.radiiSquared;
          var radiiSquaredX = radiiSquared.x;
          var radiiSquaredY = radiiSquared.y;
          var radiiSquaredZ = radiiSquared.z;
  
          var minimumHeight = 65536.0;
          var maximumHeight = -65536.0;
  
          var fromENU = Transforms.eastNorthUpToFixedFrame(relativeToCenter, ellipsoid);
          var toENU = Matrix4.inverseTransformation(fromENU, matrix4Scratch);
  
          var southMercatorY;
          var oneOverMercatorHeight;
          if (includeWebMercatorT) {
              southMercatorY = WebMercatorProjection.geodeticLatitudeToMercatorAngle(geographicSouth);
              oneOverMercatorHeight = 1.0 / (WebMercatorProjection.geodeticLatitudeToMercatorAngle(geographicNorth) - southMercatorY);
          }
  
          var minimum = minimumScratch;
          minimum.x = Number.POSITIVE_INFINITY;
          minimum.y = Number.POSITIVE_INFINITY;
          minimum.z = Number.POSITIVE_INFINITY;
  
          var maximum = maximumScratch;
          maximum.x = Number.NEGATIVE_INFINITY;
          maximum.y = Number.NEGATIVE_INFINITY;
          maximum.z = Number.NEGATIVE_INFINITY;
  
          var hMin = Number.POSITIVE_INFINITY;
  
          var arrayWidth = width + (skirtHeight > 0.0 ? 2 : 0);
          var arrayHeight = height + (skirtHeight > 0.0 ? 2 : 0);
          var size = arrayWidth * arrayHeight;
          var positions = new Array(size);
          var heights = new Array(size);
          var uvs = new Array(size);
          var webMercatorTs = includeWebMercatorT ? new Array(size) : [];
  
          var startRow = 0;
          var endRow = height;
          var startCol = 0;
          var endCol = width;
  
          if (skirtHeight > 0.0) {
              --startRow;
              ++endRow;
              --startCol;
              ++endCol;
          }
  
          var index = 0;
  
          for (var rowIndex = startRow; rowIndex < endRow; ++rowIndex) {
              var row = rowIndex;
              if (row < 0) {
                  row = 0;
              }
              if (row >= height) {
                  row = height - 1;
              }
  
              var latitude = nativeRectangle.north - granularityY * row;
  
              if (!isGeographic) {
                  latitude = piOverTwo - (2.0 * atan(exp(-latitude * oneOverGlobeSemimajorAxis)));
              } else {
                  latitude = toRadians(latitude);
              }
  
              var cosLatitude = cos(latitude);
              var nZ = sin(latitude);
              var kZ = radiiSquaredZ * nZ;
  
              var v = (latitude - geographicSouth) / (geographicNorth - geographicSouth);
              v = CesiumMath.clamp(v, 0.0, 1.0);
  
              var webMercatorT;
              if (includeWebMercatorT) {
                  webMercatorT = (WebMercatorProjection.geodeticLatitudeToMercatorAngle(latitude) - southMercatorY) * oneOverMercatorHeight;
              }
  
              for (var colIndex = startCol; colIndex < endCol; ++colIndex) {
                  var col = colIndex;
                  if (col < 0) {
                      col = 0;
                  }
                  if (col >= width) {
                      col = width - 1;
                  }
  
                  var longitude = nativeRectangle.west + granularityX * col;
  
                  if (!isGeographic) {
                      longitude = longitude * oneOverGlobeSemimajorAxis;
                  } else {
                      longitude = toRadians(longitude);
                  }
  
                  var terrainOffset = row * (width * stride) + col * stride;
  
                  var heightSample;
                  if (elementsPerHeight === 1) {
                      heightSample = heightmap[terrainOffset];
                  } else {
                      heightSample = 0;
  
                      var elementOffset;
                      if (isBigEndian) {
                          for (elementOffset = 0; elementOffset < elementsPerHeight; ++elementOffset) {
                              heightSample = (heightSample * elementMultiplier) + heightmap[terrainOffset + elementOffset];
                          }
                      } else {
                          for (elementOffset = elementsPerHeight - 1; elementOffset >= 0; --elementOffset) {
                              heightSample = (heightSample * elementMultiplier) + heightmap[terrainOffset + elementOffset];
                          }
                      }
                  }
  
                  heightSample = (heightSample * heightScale + heightOffset) * exaggeration;
  
                  var u = (longitude - geographicWest) / (geographicEast - geographicWest);
                  u = CesiumMath.clamp(u, 0.0, 1.0);
                  uvs[index] = new Cartesian2(u, v);
  
                  maximumHeight = Math.max(maximumHeight, heightSample);
                  minimumHeight = Math.min(minimumHeight, heightSample);
  
                  if (colIndex !== col || rowIndex !== row) {
                      var percentage = 0.00001;
                      if (colIndex < 0) {
                          longitude -= percentage * rectangleWidth;
                      } else {
                          longitude += percentage * rectangleWidth;
                      }
                      if (rowIndex < 0) {
                          latitude += percentage * rectangleHeight;
                      } else {
                          latitude -= percentage * rectangleHeight;
                      }
  
                      cosLatitude = cos(latitude);
                      nZ = sin(latitude);
                      kZ = radiiSquaredZ * nZ;
                      heightSample -= skirtHeight;
                  }
  
                  var nX = cosLatitude * cos(longitude);
                  var nY = cosLatitude * sin(longitude);
  
                  var kX = radiiSquaredX * nX;
                  var kY = radiiSquaredY * nY;
  
                  var gamma = sqrt((kX * nX) + (kY * nY) + (kZ * nZ));
                  var oneOverGamma = 1.0 / gamma;
  
                  var rSurfaceX = kX * oneOverGamma;
                  var rSurfaceY = kY * oneOverGamma;
                  var rSurfaceZ = kZ * oneOverGamma;
  
                  var position = new Cartesian3();
                  position.x = rSurfaceX + nX * heightSample;
                  position.y = rSurfaceY + nY * heightSample;
                  position.z = rSurfaceZ + nZ * heightSample;
  
                  positions[index] = position;
                  heights[index] = heightSample;
  
                  if (includeWebMercatorT) {
                      webMercatorTs[index] = webMercatorT;
                  }
  
                  index++;
  
                  Matrix4.multiplyByPoint(toENU, position, cartesian3Scratch);
  
                  Cartesian3.minimumByComponent(cartesian3Scratch, minimum, minimum);
                  Cartesian3.maximumByComponent(cartesian3Scratch, maximum, maximum);
                  hMin = Math.min(hMin, heightSample);
              }
          }
  
          var boundingSphere3D = BoundingSphere.fromPoints(positions);
          var orientedBoundingBox;
          if (defined(rectangle) && rectangle.width < CesiumMath.PI_OVER_TWO + CesiumMath.EPSILON5) {
              // Here, rectangle.width < pi/2, and rectangle.height < pi
              // (though it would still work with rectangle.width up to pi)
              orientedBoundingBox = OrientedBoundingBox.fromRectangle(rectangle, minimumHeight, maximumHeight, ellipsoid);
          }
  
          var occludeePointInScaledSpace;
          if (hasRelativeToCenter) {
              var occluder = new EllipsoidalOccluder(ellipsoid);
              occludeePointInScaledSpace = occluder.computeHorizonCullingPoint(relativeToCenter, positions);
          }
  
          var aaBox = new AxisAlignedBoundingBox(minimum, maximum, relativeToCenter);
          var encoding = new TerrainEncoding(aaBox, hMin, maximumHeight, fromENU, false, includeWebMercatorT);
          var vertices = new Float32Array(size * encoding.getStride());
  
          var bufferIndex = 0;
          for (var j = 0; j < size; ++j) {
              bufferIndex = encoding.encode(vertices, bufferIndex, positions[j], uvs[j], heights[j], undefined, webMercatorTs[j]);
          }
  
          var westIndicesSouthToNorth;
          var southIndicesEastToWest;
          var eastIndicesNorthToSouth;
          var northIndicesWestToEast;
  
          if (skirtHeight > 0.0) {
              northIndicesWestToEast = [];
              southIndicesEastToWest = [];
              for (var i1 = 0; i1 < width; ++i1) {
                  northIndicesWestToEast.push(arrayWidth + 1 + i1);
                  southIndicesEastToWest.push(arrayWidth * (arrayHeight - 1) - 2 - i1);
              }
  
              westIndicesSouthToNorth = [];
              eastIndicesNorthToSouth = [];
              for (var i2 = 0; i2 < height; ++i2) {
                  eastIndicesNorthToSouth.push((i2 + 1) * arrayWidth + width);
                  westIndicesSouthToNorth.push((height - i2) * arrayWidth + 1);
              }
          } else {
              northIndicesWestToEast = [];
              southIndicesEastToWest = [];
              for (var i3 = 0; i3 < width; ++i3) {
                  northIndicesWestToEast.push(i3);
                  southIndicesEastToWest.push(width * height - 1 - i3);
              }
  
              westIndicesSouthToNorth = [];
              eastIndicesNorthToSouth = [];
              for (var i4 = 0; i4 < height; ++i4) {
                  eastIndicesNorthToSouth.push((i4 + 1) * width - 1);
                  westIndicesSouthToNorth.push((height - i4 - 1) * width );
              }
          }
  
          return {
              vertices : vertices,
              maximumHeight : maximumHeight,
              minimumHeight : minimumHeight,
              encoding : encoding,
              boundingSphere3D : boundingSphere3D,
              orientedBoundingBox : orientedBoundingBox,
              occludeePointInScaledSpace : occludeePointInScaledSpace,
              westIndicesSouthToNorth : westIndicesSouthToNorth,
              southIndicesEastToWest : southIndicesEastToWest,
              eastIndicesNorthToSouth : eastIndicesNorthToSouth,
              northIndicesWestToEast : northIndicesWestToEast
          };
      };
  export default HeightmapTessellator;
  