QuadtreePrimitive.js

import Cartesian3 from "../Core/Cartesian3.js";
import Cartographic from "../Core/Cartographic.js";
import defaultValue from "../Core/defaultValue.js";
import defined from "../Core/defined.js";
import DeveloperError from "../Core/DeveloperError.js";
import Event from "../Core/Event.js";
import getTimestamp from "../Core/getTimestamp.js";
import CesiumMath from "../Core/Math.js";
import Matrix4 from "../Core/Matrix4.js";
import OrthographicFrustum from "../Core/OrthographicFrustum.js";
import OrthographicOffCenterFrustum from "../Core/OrthographicOffCenterFrustum.js";
import Ray from "../Core/Ray.js";
import Rectangle from "../Core/Rectangle.js";
import Visibility from "../Core/Visibility.js";
import QuadtreeOccluders from "./QuadtreeOccluders.js";
import QuadtreeTile from "./QuadtreeTile.js";
import QuadtreeTileLoadState from "./QuadtreeTileLoadState.js";
import SceneMode from "./SceneMode.js";
import TileReplacementQueue from "./TileReplacementQueue.js";
import TileSelectionResult from "./TileSelectionResult.js";

/**
 * Renders massive sets of data by utilizing level-of-detail and culling.  The globe surface is divided into
 * a quadtree of tiles with large, low-detail tiles at the root and small, high-detail tiles at the leaves.
 * The set of tiles to render is selected by projecting an estimate of the geometric error in a tile onto
 * the screen to estimate screen-space error, in pixels, which must be below a user-specified threshold.
 * The actual content of the tiles is arbitrary and is specified using a {@link QuadtreeTileProvider}.
 *
 * @alias QuadtreePrimitive
 * @constructor
 * @private
 *
 * @param {QuadtreeTileProvider} options.tileProvider The tile provider that loads, renders, and estimates
 *        the distance to individual tiles.
 * @param {Number} [options.maximumScreenSpaceError=2] The maximum screen-space error, in pixels, that is allowed.
 *        A higher maximum error will render fewer tiles and improve performance, while a lower
 *        value will improve visual quality.
 * @param {Number} [options.tileCacheSize=100] The maximum number of tiles that will be retained in the tile cache.
 *        Note that tiles will never be unloaded if they were used for rendering the last
 *        frame, so the actual number of resident tiles may be higher.  The value of
 *        this property will not affect visual quality.
 */
function QuadtreePrimitive(options) {
  //>>includeStart('debug', pragmas.debug);
  if (!defined(options) || !defined(options.tileProvider)) {
    throw new DeveloperError("options.tileProvider is required.");
  }
  if (defined(options.tileProvider.quadtree)) {
    throw new DeveloperError(
      "A QuadtreeTileProvider can only be used with a single QuadtreePrimitive"
    );
  }
  //>>includeEnd('debug');

  this._tileProvider = options.tileProvider;
  this._tileProvider.quadtree = this;

  this._debug = {
    enableDebugOutput: false,

    maxDepth: 0,
    maxDepthVisited: 0,
    tilesVisited: 0,
    tilesCulled: 0,
    tilesRendered: 0,
    tilesWaitingForChildren: 0,

    lastMaxDepth: -1,
    lastMaxDepthVisited: -1,
    lastTilesVisited: -1,
    lastTilesCulled: -1,
    lastTilesRendered: -1,
    lastTilesWaitingForChildren: -1,

    suspendLodUpdate: false,
  };

  var tilingScheme = this._tileProvider.tilingScheme;
  var ellipsoid = tilingScheme.ellipsoid;

  this._tilesToRender = [];
  this._tileLoadQueueHigh = []; // high priority tiles are preventing refinement
  this._tileLoadQueueMedium = []; // medium priority tiles are being rendered
  this._tileLoadQueueLow = []; // low priority tiles were refined past or are non-visible parts of quads.
  this._tileReplacementQueue = new TileReplacementQueue();
  this._levelZeroTiles = undefined;
  this._loadQueueTimeSlice = 5.0;
  this._tilesInvalidated = false;

  this._addHeightCallbacks = [];
  this._removeHeightCallbacks = [];

  this._tileToUpdateHeights = [];
  this._lastTileIndex = 0;
  this._updateHeightsTimeSlice = 2.0;

  // If a culled tile contains _cameraPositionCartographic or _cameraReferenceFrameOriginCartographic, it will be marked
  // TileSelectionResult.CULLED_BUT_NEEDED and added to the list of tiles to update heights,
  // even though it is not rendered.
  // These are updated each frame in `selectTilesForRendering`.
  this._cameraPositionCartographic = undefined;
  this._cameraReferenceFrameOriginCartographic = undefined;

  /**
   * Gets or sets the maximum screen-space error, in pixels, that is allowed.
   * A higher maximum error will render fewer tiles and improve performance, while a lower
   * value will improve visual quality.
   * @type {Number}
   * @default 2
   */
  this.maximumScreenSpaceError = defaultValue(
    options.maximumScreenSpaceError,
    2
  );

  /**
   * Gets or sets the maximum number of tiles that will be retained in the tile cache.
   * Note that tiles will never be unloaded if they were used for rendering the last
   * frame, so the actual number of resident tiles may be higher.  The value of
   * this property will not affect visual quality.
   * @type {Number}
   * @default 100
   */
  this.tileCacheSize = defaultValue(options.tileCacheSize, 100);

  /**
   * Gets or sets the number of loading descendant tiles that is considered "too many".
   * If a tile has too many loading descendants, that tile will be loaded and rendered before any of
   * its descendants are loaded and rendered. This means more feedback for the user that something
   * is happening at the cost of a longer overall load time. Setting this to 0 will cause each
   * tile level to be loaded successively, significantly increasing load time. Setting it to a large
   * number (e.g. 1000) will minimize the number of tiles that are loaded but tend to make
   * detail appear all at once after a long wait.
   * @type {Number}
   * @default 20
   */
  this.loadingDescendantLimit = 20;

  /**
   * Gets or sets a value indicating whether the ancestors of rendered tiles should be preloaded.
   * Setting this to true optimizes the zoom-out experience and provides more detail in
   * newly-exposed areas when panning. The down side is that it requires loading more tiles.
   * @type {Boolean}
   * @default true
   */
  this.preloadAncestors = true;

  /**
   * Gets or sets a value indicating whether the siblings of rendered tiles should be preloaded.
   * Setting this to true causes tiles with the same parent as a rendered tile to be loaded, even
   * if they are culled. Setting this to true may provide a better panning experience at the
   * cost of loading more tiles.
   * @type {Boolean}
   * @default false
   */
  this.preloadSiblings = false;

  this._occluders = new QuadtreeOccluders({
    ellipsoid: ellipsoid,
  });

  this._tileLoadProgressEvent = new Event();
  this._lastTileLoadQueueLength = 0;

  this._lastSelectionFrameNumber = undefined;
}

Object.defineProperties(QuadtreePrimitive.prototype, {
  /**
   * Gets the provider of {@link QuadtreeTile} instances for this quadtree.
   * @type {QuadtreeTile}
   * @memberof QuadtreePrimitive.prototype
   */
  tileProvider: {
    get: function () {
      return this._tileProvider;
    },
  },
  /**
   * Gets an event that's raised when the length of the tile load queue has changed since the last render frame.  When the load queue is empty,
   * all terrain and imagery for the current view have been loaded.  The event passes the new length of the tile load queue.
   *
   * @memberof QuadtreePrimitive.prototype
   * @type {Event}
   */
  tileLoadProgressEvent: {
    get: function () {
      return this._tileLoadProgressEvent;
    },
  },

  occluders: {
    get: function () {
      return this._occluders;
    },
  },
});

/**
 * Invalidates and frees all the tiles in the quadtree.  The tiles must be reloaded
 * before they can be displayed.
 *
 * @memberof QuadtreePrimitive
 */
QuadtreePrimitive.prototype.invalidateAllTiles = function () {
  this._tilesInvalidated = true;
};

function invalidateAllTiles(primitive) {
  // Clear the replacement queue
  var replacementQueue = primitive._tileReplacementQueue;
  replacementQueue.head = undefined;
  replacementQueue.tail = undefined;
  replacementQueue.count = 0;

  clearTileLoadQueue(primitive);

  // Free and recreate the level zero tiles.
  var levelZeroTiles = primitive._levelZeroTiles;
  if (defined(levelZeroTiles)) {
    for (var i = 0; i < levelZeroTiles.length; ++i) {
      var tile = levelZeroTiles[i];
      var customData = tile.customData;
      var customDataLength = customData.length;

      for (var j = 0; j < customDataLength; ++j) {
        var data = customData[j];
        data.level = 0;
        primitive._addHeightCallbacks.push(data);
      }

      levelZeroTiles[i].freeResources();
    }
  }

  primitive._levelZeroTiles = undefined;

  primitive._tileProvider.cancelReprojections();
}

/**
 * Invokes a specified function for each {@link QuadtreeTile} that is partially
 * or completely loaded.
 *
 * @param {Function} tileFunction The function to invoke for each loaded tile.  The
 *        function is passed a reference to the tile as its only parameter.
 */
QuadtreePrimitive.prototype.forEachLoadedTile = function (tileFunction) {
  var tile = this._tileReplacementQueue.head;
  while (defined(tile)) {
    if (tile.state !== QuadtreeTileLoadState.START) {
      tileFunction(tile);
    }
    tile = tile.replacementNext;
  }
};

/**
 * Invokes a specified function for each {@link QuadtreeTile} that was rendered
 * in the most recent frame.
 *
 * @param {Function} tileFunction The function to invoke for each rendered tile.  The
 *        function is passed a reference to the tile as its only parameter.
 */
QuadtreePrimitive.prototype.forEachRenderedTile = function (tileFunction) {
  var tilesRendered = this._tilesToRender;
  for (var i = 0, len = tilesRendered.length; i < len; ++i) {
    tileFunction(tilesRendered[i]);
  }
};

/**
 * Calls the callback when a new tile is rendered that contains the given cartographic. The only parameter
 * is the cartesian position on the tile.
 *
 * @param {Cartographic} cartographic The cartographic position.
 * @param {Function} callback The function to be called when a new tile is loaded containing cartographic.
 * @returns {Function} The function to remove this callback from the quadtree.
 */
QuadtreePrimitive.prototype.updateHeight = function (cartographic, callback) {
  var primitive = this;
  var object = {
    positionOnEllipsoidSurface: undefined,
    positionCartographic: cartographic,
    level: -1,
    callback: callback,
  };

  object.removeFunc = function () {
    var addedCallbacks = primitive._addHeightCallbacks;
    var length = addedCallbacks.length;
    for (var i = 0; i < length; ++i) {
      if (addedCallbacks[i] === object) {
        addedCallbacks.splice(i, 1);
        break;
      }
    }
    primitive._removeHeightCallbacks.push(object);
  };

  primitive._addHeightCallbacks.push(object);
  return object.removeFunc;
};

/**
 * Updates the tile provider imagery and continues to process the tile load queue.
 * @private
 */
QuadtreePrimitive.prototype.update = function (frameState) {
  if (defined(this._tileProvider.update)) {
    this._tileProvider.update(frameState);
  }
};

function clearTileLoadQueue(primitive) {
  var debug = primitive._debug;
  debug.maxDepth = 0;
  debug.maxDepthVisited = 0;
  debug.tilesVisited = 0;
  debug.tilesCulled = 0;
  debug.tilesRendered = 0;
  debug.tilesWaitingForChildren = 0;

  primitive._tileLoadQueueHigh.length = 0;
  primitive._tileLoadQueueMedium.length = 0;
  primitive._tileLoadQueueLow.length = 0;
}

/**
 * Initializes values for a new render frame and prepare the tile load queue.
 * @private
 */
QuadtreePrimitive.prototype.beginFrame = function (frameState) {
  var passes = frameState.passes;
  if (!passes.render) {
    return;
  }

  if (this._tilesInvalidated) {
    invalidateAllTiles(this);
    this._tilesInvalidated = false;
  }

  // Gets commands for any texture re-projections
  this._tileProvider.initialize(frameState);

  clearTileLoadQueue(this);

  if (this._debug.suspendLodUpdate) {
    return;
  }

  this._tileReplacementQueue.markStartOfRenderFrame();
};

/**
 * Selects new tiles to load based on the frame state and creates render commands.
 * @private
 */
QuadtreePrimitive.prototype.render = function (frameState) {
  var passes = frameState.passes;
  var tileProvider = this._tileProvider;

  if (passes.render) {
    tileProvider.beginUpdate(frameState);

    selectTilesForRendering(this, frameState);
    createRenderCommandsForSelectedTiles(this, frameState);

    tileProvider.endUpdate(frameState);
  }

  if (passes.pick && this._tilesToRender.length > 0) {
    tileProvider.updateForPick(frameState);
  }
};

/**
 * Checks if the load queue length has changed since the last time we raised a queue change event - if so, raises
 * a new change event at the end of the render cycle.
 * @private
 */
function updateTileLoadProgress(primitive, frameState) {
  var currentLoadQueueLength =
    primitive._tileLoadQueueHigh.length +
    primitive._tileLoadQueueMedium.length +
    primitive._tileLoadQueueLow.length;

  if (
    currentLoadQueueLength !== primitive._lastTileLoadQueueLength ||
    primitive._tilesInvalidated
  ) {
    frameState.afterRender.push(
      Event.prototype.raiseEvent.bind(
        primitive._tileLoadProgressEvent,
        currentLoadQueueLength
      )
    );
    primitive._lastTileLoadQueueLength = currentLoadQueueLength;
  }

  var debug = primitive._debug;
  if (debug.enableDebugOutput && !debug.suspendLodUpdate) {
    debug.maxDepth = primitive._tilesToRender.reduce(function (max, tile) {
      return Math.max(max, tile.level);
    }, -1);
    debug.tilesRendered = primitive._tilesToRender.length;

    if (
      debug.tilesVisited !== debug.lastTilesVisited ||
      debug.tilesRendered !== debug.lastTilesRendered ||
      debug.tilesCulled !== debug.lastTilesCulled ||
      debug.maxDepth !== debug.lastMaxDepth ||
      debug.tilesWaitingForChildren !== debug.lastTilesWaitingForChildren ||
      debug.maxDepthVisited !== debug.lastMaxDepthVisited
    ) {
      console.log(
        "Visited " +
          debug.tilesVisited +
          ", Rendered: " +
          debug.tilesRendered +
          ", Culled: " +
          debug.tilesCulled +
          ", Max Depth Rendered: " +
          debug.maxDepth +
          ", Max Depth Visited: " +
          debug.maxDepthVisited +
          ", Waiting for children: " +
          debug.tilesWaitingForChildren
      );

      debug.lastTilesVisited = debug.tilesVisited;
      debug.lastTilesRendered = debug.tilesRendered;
      debug.lastTilesCulled = debug.tilesCulled;
      debug.lastMaxDepth = debug.maxDepth;
      debug.lastTilesWaitingForChildren = debug.tilesWaitingForChildren;
      debug.lastMaxDepthVisited = debug.maxDepthVisited;
    }
  }
}

/**
 * Updates terrain heights.
 * @private
 */
QuadtreePrimitive.prototype.endFrame = function (frameState) {
  var passes = frameState.passes;
  if (!passes.render || frameState.mode === SceneMode.MORPHING) {
    // Only process the load queue for a single pass.
    // Don't process the load queue or update heights during the morph flights.
    return;
  }

  // Load/create resources for terrain and imagery. Prepare texture re-projections for the next frame.
  processTileLoadQueue(this, frameState);
  updateHeights(this, frameState);
  updateTileLoadProgress(this, frameState);
};

/**
 * Returns true if this object was destroyed; otherwise, false.
 * <br /><br />
 * If this object was destroyed, it should not be used; calling any function other than
 * <code>isDestroyed</code> will result in a {@link DeveloperError} exception.
 *
 * @memberof QuadtreePrimitive
 *
 * @returns {Boolean} True if this object was destroyed; otherwise, false.
 *
 * @see QuadtreePrimitive#destroy
 */
QuadtreePrimitive.prototype.isDestroyed = function () {
  return false;
};

/**
 * Destroys the WebGL resources held by this object.  Destroying an object allows for deterministic
 * release of WebGL resources, instead of relying on the garbage collector to destroy this object.
 * <br /><br />
 * Once an object is destroyed, it should not be used; calling any function other than
 * <code>isDestroyed</code> will result in a {@link DeveloperError} exception.  Therefore,
 * assign the return value (<code>undefined</code>) to the object as done in the example.
 *
 * @memberof QuadtreePrimitive
 *
 * @exception {DeveloperError} This object was destroyed, i.e., destroy() was called.
 *
 *
 * @example
 * primitive = primitive && primitive.destroy();
 *
 * @see QuadtreePrimitive#isDestroyed
 */
QuadtreePrimitive.prototype.destroy = function () {
  this._tileProvider = this._tileProvider && this._tileProvider.destroy();
};

var comparisonPoint;
var centerScratch = new Cartographic();
function compareDistanceToPoint(a, b) {
  var center = Rectangle.center(a.rectangle, centerScratch);
  var alon = center.longitude - comparisonPoint.longitude;
  var alat = center.latitude - comparisonPoint.latitude;

  center = Rectangle.center(b.rectangle, centerScratch);
  var blon = center.longitude - comparisonPoint.longitude;
  var blat = center.latitude - comparisonPoint.latitude;

  return alon * alon + alat * alat - (blon * blon + blat * blat);
}

var cameraOriginScratch = new Cartesian3();
var rootTraversalDetails = [];

function selectTilesForRendering(primitive, frameState) {
  var debug = primitive._debug;
  if (debug.suspendLodUpdate) {
    return;
  }

  // Clear the render list.
  var tilesToRender = primitive._tilesToRender;
  tilesToRender.length = 0;

  // We can't render anything before the level zero tiles exist.
  var i;
  var tileProvider = primitive._tileProvider;
  if (!defined(primitive._levelZeroTiles)) {
    if (tileProvider.ready) {
      var tilingScheme = tileProvider.tilingScheme;
      primitive._levelZeroTiles = QuadtreeTile.createLevelZeroTiles(
        tilingScheme
      );
      var numberOfRootTiles = primitive._levelZeroTiles.length;
      if (rootTraversalDetails.length < numberOfRootTiles) {
        rootTraversalDetails = new Array(numberOfRootTiles);
        for (i = 0; i < numberOfRootTiles; ++i) {
          if (rootTraversalDetails[i] === undefined) {
            rootTraversalDetails[i] = new TraversalDetails();
          }
        }
      }
    } else {
      // Nothing to do until the provider is ready.
      return;
    }
  }

  primitive._occluders.ellipsoid.cameraPosition = frameState.camera.positionWC;

  var tile;
  var levelZeroTiles = primitive._levelZeroTiles;
  var occluders = levelZeroTiles.length > 1 ? primitive._occluders : undefined;

  // Sort the level zero tiles by the distance from the center to the camera.
  // The level zero tiles aren't necessarily a nice neat quad, so we can't use the
  // quadtree ordering we use elsewhere in the tree
  comparisonPoint = frameState.camera.positionCartographic;
  levelZeroTiles.sort(compareDistanceToPoint);

  var customDataAdded = primitive._addHeightCallbacks;
  var customDataRemoved = primitive._removeHeightCallbacks;
  var frameNumber = frameState.frameNumber;

  var len;
  if (customDataAdded.length > 0 || customDataRemoved.length > 0) {
    for (i = 0, len = levelZeroTiles.length; i < len; ++i) {
      tile = levelZeroTiles[i];
      tile._updateCustomData(frameNumber, customDataAdded, customDataRemoved);
    }

    customDataAdded.length = 0;
    customDataRemoved.length = 0;
  }

  var camera = frameState.camera;

  primitive._cameraPositionCartographic = camera.positionCartographic;
  var cameraFrameOrigin = Matrix4.getTranslation(
    camera.transform,
    cameraOriginScratch
  );
  primitive._cameraReferenceFrameOriginCartographic = primitive.tileProvider.tilingScheme.ellipsoid.cartesianToCartographic(
    cameraFrameOrigin,
    primitive._cameraReferenceFrameOriginCartographic
  );

  // Traverse in depth-first, near-to-far order.
  for (i = 0, len = levelZeroTiles.length; i < len; ++i) {
    tile = levelZeroTiles[i];
    primitive._tileReplacementQueue.markTileRendered(tile);
    if (!tile.renderable) {
      queueTileLoad(primitive, primitive._tileLoadQueueHigh, tile, frameState);
      ++debug.tilesWaitingForChildren;
    } else {
      visitIfVisible(
        primitive,
        tile,
        tileProvider,
        frameState,
        occluders,
        false,
        rootTraversalDetails[i]
      );
    }
  }

  primitive._lastSelectionFrameNumber = frameNumber;
}

function queueTileLoad(primitive, queue, tile, frameState) {
  if (!tile.needsLoading) {
    return;
  }

  if (primitive.tileProvider.computeTileLoadPriority !== undefined) {
    tile._loadPriority = primitive.tileProvider.computeTileLoadPriority(
      tile,
      frameState
    );
  }
  queue.push(tile);
}

/**
 * Tracks details of traversing a tile while selecting tiles for rendering.
 * @alias TraversalDetails
 * @constructor
 * @private
 */
function TraversalDetails() {
  /**
   * True if all selected (i.e. not culled or refined) tiles in this tile's subtree
   * are renderable. If the subtree is renderable, we'll render it; no drama.
   */
  this.allAreRenderable = true;

  /**
   * True if any tiles in this tile's subtree were rendered last frame. If any
   * were, we must render the subtree rather than this tile, because rendering
   * this tile would cause detail to vanish that was visible last frame, and
   * that's no good.
   */
  this.anyWereRenderedLastFrame = false;

  /**
   * Counts the number of selected tiles in this tile's subtree that are
   * not yet ready to be rendered because they need more loading. Note that
   * this value will _not_ necessarily be zero when
   * {@link TraversalDetails#allAreRenderable} is true, for subtle reasons.
   * When {@link TraversalDetails#allAreRenderable} and
   * {@link TraversalDetails#anyWereRenderedLastFrame} are both false, we
   * will render this tile instead of any tiles in its subtree and
   * the `allAreRenderable` value for this tile will reflect only whether _this_
   * tile is renderable. The `notYetRenderableCount` value, however, will still
   * reflect the total number of tiles that we are waiting on, including the
   * ones that we're not rendering. `notYetRenderableCount` is only reset
   * when a subtree is removed from the render queue because the
   * `notYetRenderableCount` exceeds the
   * {@link QuadtreePrimitive#loadingDescendantLimit}.
   */
  this.notYetRenderableCount = 0;
}

function TraversalQuadDetails() {
  this.southwest = new TraversalDetails();
  this.southeast = new TraversalDetails();
  this.northwest = new TraversalDetails();
  this.northeast = new TraversalDetails();
}

TraversalQuadDetails.prototype.combine = function (result) {
  var southwest = this.southwest;
  var southeast = this.southeast;
  var northwest = this.northwest;
  var northeast = this.northeast;

  result.allAreRenderable =
    southwest.allAreRenderable &&
    southeast.allAreRenderable &&
    northwest.allAreRenderable &&
    northeast.allAreRenderable;
  result.anyWereRenderedLastFrame =
    southwest.anyWereRenderedLastFrame ||
    southeast.anyWereRenderedLastFrame ||
    northwest.anyWereRenderedLastFrame ||
    northeast.anyWereRenderedLastFrame;
  result.notYetRenderableCount =
    southwest.notYetRenderableCount +
    southeast.notYetRenderableCount +
    northwest.notYetRenderableCount +
    northeast.notYetRenderableCount;
};

var traversalQuadsByLevel = new Array(31); // level 30 tiles are ~2cm wide at the equator, should be good enough.
for (var i = 0; i < traversalQuadsByLevel.length; ++i) {
  traversalQuadsByLevel[i] = new TraversalQuadDetails();
}

/**
 * Visits a tile for possible rendering. When we call this function with a tile:
 *
 *    * the tile has been determined to be visible (possibly based on a bounding volume that is not very tight-fitting)
 *    * its parent tile does _not_ meet the SSE (unless ancestorMeetsSse=true, see comments below)
 *    * the tile may or may not be renderable
 *
 * @private
 *
 * @param {Primitive} primitive The QuadtreePrimitive.
 * @param {FrameState} frameState The frame state.
 * @param {QuadtreeTile} tile The tile to visit
 * @param {Boolean} ancestorMeetsSse True if a tile higher in the tile tree already met the SSE and we're refining further only
 *                  to maintain detail while that higher tile loads.
 * @param {TraversalDetails} traveralDetails On return, populated with details of how the traversal of this tile went.
 */
function visitTile(
  primitive,
  frameState,
  tile,
  ancestorMeetsSse,
  traversalDetails
) {
  var debug = primitive._debug;

  ++debug.tilesVisited;

  primitive._tileReplacementQueue.markTileRendered(tile);
  tile._updateCustomData(frameState.frameNumber);

  if (tile.level > debug.maxDepthVisited) {
    debug.maxDepthVisited = tile.level;
  }

  var meetsSse =
    screenSpaceError(primitive, frameState, tile) <
    primitive.maximumScreenSpaceError;

  var southwestChild = tile.southwestChild;
  var southeastChild = tile.southeastChild;
  var northwestChild = tile.northwestChild;
  var northeastChild = tile.northeastChild;

  var lastFrame = primitive._lastSelectionFrameNumber;
  var lastFrameSelectionResult =
    tile._lastSelectionResultFrame === lastFrame
      ? tile._lastSelectionResult
      : TileSelectionResult.NONE;

  var tileProvider = primitive.tileProvider;

  if (meetsSse || ancestorMeetsSse) {
    // This tile (or an ancestor) is the one we want to render this frame, but we'll do different things depending
    // on the state of this tile and on what we did _last_ frame.

    // We can render it if _any_ of the following are true:
    // 1. We rendered it (or kicked it) last frame.
    // 2. This tile was culled last frame, or it wasn't even visited because an ancestor was culled.
    // 3. The tile is completely done loading.
    // 4. a) Terrain is ready, and
    //    b) All necessary imagery is ready. Necessary imagery is imagery that was rendered with this tile
    //       or any descendants last frame. Such imagery is required because rendering this tile without
    //       it would cause detail to disappear.
    //
    // Determining condition 4 is more expensive, so we check the others first.
    //
    // Note that even if we decide to render a tile here, it may later get "kicked" in favor of an ancestor.

    var oneRenderedLastFrame =
      TileSelectionResult.originalResult(lastFrameSelectionResult) ===
      TileSelectionResult.RENDERED;
    var twoCulledOrNotVisited =
      TileSelectionResult.originalResult(lastFrameSelectionResult) ===
        TileSelectionResult.CULLED ||
      lastFrameSelectionResult === TileSelectionResult.NONE;
    var threeCompletelyLoaded = tile.state === QuadtreeTileLoadState.DONE;

    var renderable =
      oneRenderedLastFrame || twoCulledOrNotVisited || threeCompletelyLoaded;

    if (!renderable) {
      // Check the more expensive condition 4 above. This requires details of the thing
      // we're rendering (e.g. the globe surface), so delegate it to the tile provider.
      if (defined(tileProvider.canRenderWithoutLosingDetail)) {
        renderable = tileProvider.canRenderWithoutLosingDetail(tile);
      }
    }

    if (renderable) {
      // Only load this tile if it (not just an ancestor) meets the SSE.
      if (meetsSse) {
        queueTileLoad(
          primitive,
          primitive._tileLoadQueueMedium,
          tile,
          frameState
        );
      }
      addTileToRenderList(primitive, tile);

      traversalDetails.allAreRenderable = tile.renderable;
      traversalDetails.anyWereRenderedLastFrame =
        lastFrameSelectionResult === TileSelectionResult.RENDERED;
      traversalDetails.notYetRenderableCount = tile.renderable ? 0 : 1;

      tile._lastSelectionResultFrame = frameState.frameNumber;
      tile._lastSelectionResult = TileSelectionResult.RENDERED;

      if (!traversalDetails.anyWereRenderedLastFrame) {
        // Tile is newly-rendered this frame, so update its heights.
        primitive._tileToUpdateHeights.push(tile);
      }

      return;
    }

    // Otherwise, we can't render this tile (or its fill) because doing so would cause detail to disappear
    // that was visible last frame. Instead, keep rendering any still-visible descendants that were rendered
    // last frame and render fills for newly-visible descendants. E.g. if we were rendering level 15 last
    // frame but this frame we want level 14 and the closest renderable level <= 14 is 0, rendering level
    // zero would be pretty jarring so instead we keep rendering level 15 even though its SSE is better
    // than required. So fall through to continue traversal...
    ancestorMeetsSse = true;

    // Load this blocker tile with high priority, but only if this tile (not just an ancestor) meets the SSE.
    if (meetsSse) {
      queueTileLoad(primitive, primitive._tileLoadQueueHigh, tile, frameState);
    }
  }

  if (tileProvider.canRefine(tile)) {
    var allAreUpsampled =
      southwestChild.upsampledFromParent &&
      southeastChild.upsampledFromParent &&
      northwestChild.upsampledFromParent &&
      northeastChild.upsampledFromParent;

    if (allAreUpsampled) {
      // No point in rendering the children because they're all upsampled.  Render this tile instead.
      addTileToRenderList(primitive, tile);

      // Rendered tile that's not waiting on children loads with medium priority.
      queueTileLoad(
        primitive,
        primitive._tileLoadQueueMedium,
        tile,
        frameState
      );

      // Make sure we don't unload the children and forget they're upsampled.
      primitive._tileReplacementQueue.markTileRendered(southwestChild);
      primitive._tileReplacementQueue.markTileRendered(southeastChild);
      primitive._tileReplacementQueue.markTileRendered(northwestChild);
      primitive._tileReplacementQueue.markTileRendered(northeastChild);

      traversalDetails.allAreRenderable = tile.renderable;
      traversalDetails.anyWereRenderedLastFrame =
        lastFrameSelectionResult === TileSelectionResult.RENDERED;
      traversalDetails.notYetRenderableCount = tile.renderable ? 0 : 1;

      tile._lastSelectionResultFrame = frameState.frameNumber;
      tile._lastSelectionResult = TileSelectionResult.RENDERED;

      if (!traversalDetails.anyWereRenderedLastFrame) {
        // Tile is newly-rendered this frame, so update its heights.
        primitive._tileToUpdateHeights.push(tile);
      }

      return;
    }

    // SSE is not good enough, so refine.
    tile._lastSelectionResultFrame = frameState.frameNumber;
    tile._lastSelectionResult = TileSelectionResult.REFINED;

    var firstRenderedDescendantIndex = primitive._tilesToRender.length;
    var loadIndexLow = primitive._tileLoadQueueLow.length;
    var loadIndexMedium = primitive._tileLoadQueueMedium.length;
    var loadIndexHigh = primitive._tileLoadQueueHigh.length;
    var tilesToUpdateHeightsIndex = primitive._tileToUpdateHeights.length;

    // No need to add the children to the load queue because they'll be added (if necessary) when they're visited.
    visitVisibleChildrenNearToFar(
      primitive,
      southwestChild,
      southeastChild,
      northwestChild,
      northeastChild,
      frameState,
      ancestorMeetsSse,
      traversalDetails
    );

    // If no descendant tiles were added to the render list by the function above, it means they were all
    // culled even though this tile was deemed visible. That's pretty common.

    if (firstRenderedDescendantIndex !== primitive._tilesToRender.length) {
      // At least one descendant tile was added to the render list.
      // The traversalDetails tell us what happened while visiting the children.

      var allAreRenderable = traversalDetails.allAreRenderable;
      var anyWereRenderedLastFrame = traversalDetails.anyWereRenderedLastFrame;
      var notYetRenderableCount = traversalDetails.notYetRenderableCount;
      var queuedForLoad = false;

      if (!allAreRenderable && !anyWereRenderedLastFrame) {
        // Some of our descendants aren't ready to render yet, and none were rendered last frame,
        // so kick them all out of the render list and render this tile instead. Continue to load them though!

        // Mark the rendered descendants and their ancestors - up to this tile - as kicked.
        var renderList = primitive._tilesToRender;
        for (var i = firstRenderedDescendantIndex; i < renderList.length; ++i) {
          var workTile = renderList[i];
          while (
            workTile !== undefined &&
            workTile._lastSelectionResult !== TileSelectionResult.KICKED &&
            workTile !== tile
          ) {
            workTile._lastSelectionResult = TileSelectionResult.kick(
              workTile._lastSelectionResult
            );
            workTile = workTile.parent;
          }
        }

        // Remove all descendants from the render list and add this tile.
        primitive._tilesToRender.length = firstRenderedDescendantIndex;
        primitive._tileToUpdateHeights.length = tilesToUpdateHeightsIndex;
        addTileToRenderList(primitive, tile);

        tile._lastSelectionResult = TileSelectionResult.RENDERED;

        // If we're waiting on heaps of descendants, the above will take too long. So in that case,
        // load this tile INSTEAD of loading any of the descendants, and tell the up-level we're only waiting
        // on this tile. Keep doing this until we actually manage to render this tile.
        var wasRenderedLastFrame =
          lastFrameSelectionResult === TileSelectionResult.RENDERED;
        if (
          !wasRenderedLastFrame &&
          notYetRenderableCount > primitive.loadingDescendantLimit
        ) {
          // Remove all descendants from the load queues.
          primitive._tileLoadQueueLow.length = loadIndexLow;
          primitive._tileLoadQueueMedium.length = loadIndexMedium;
          primitive._tileLoadQueueHigh.length = loadIndexHigh;
          queueTileLoad(
            primitive,
            primitive._tileLoadQueueMedium,
            tile,
            frameState
          );
          traversalDetails.notYetRenderableCount = tile.renderable ? 0 : 1;
          queuedForLoad = true;
        }

        traversalDetails.allAreRenderable = tile.renderable;
        traversalDetails.anyWereRenderedLastFrame = wasRenderedLastFrame;

        if (!wasRenderedLastFrame) {
          // Tile is newly-rendered this frame, so update its heights.
          primitive._tileToUpdateHeights.push(tile);
        }

        ++debug.tilesWaitingForChildren;
      }

      if (primitive.preloadAncestors && !queuedForLoad) {
        queueTileLoad(primitive, primitive._tileLoadQueueLow, tile, frameState);
      }
    }

    return;
  }

  tile._lastSelectionResultFrame = frameState.frameNumber;
  tile._lastSelectionResult = TileSelectionResult.RENDERED;

  // We'd like to refine but can't because we have no availability data for this tile's children,
  // so we have no idea if refinining would involve a load or an upsample. We'll have to finish
  // loading this tile first in order to find that out, so load this refinement blocker with
  // high priority.
  addTileToRenderList(primitive, tile);
  queueTileLoad(primitive, primitive._tileLoadQueueHigh, tile, frameState);

  traversalDetails.allAreRenderable = tile.renderable;
  traversalDetails.anyWereRenderedLastFrame =
    lastFrameSelectionResult === TileSelectionResult.RENDERED;
  traversalDetails.notYetRenderableCount = tile.renderable ? 0 : 1;
}

function visitVisibleChildrenNearToFar(
  primitive,
  southwest,
  southeast,
  northwest,
  northeast,
  frameState,
  ancestorMeetsSse,
  traversalDetails
) {
  var cameraPosition = frameState.camera.positionCartographic;
  var tileProvider = primitive._tileProvider;
  var occluders = primitive._occluders;

  var quadDetails = traversalQuadsByLevel[southwest.level];
  var southwestDetails = quadDetails.southwest;
  var southeastDetails = quadDetails.southeast;
  var northwestDetails = quadDetails.northwest;
  var northeastDetails = quadDetails.northeast;

  if (cameraPosition.longitude < southwest.rectangle.east) {
    if (cameraPosition.latitude < southwest.rectangle.north) {
      // Camera in southwest quadrant
      visitIfVisible(
        primitive,
        southwest,
        tileProvider,
        frameState,
        occluders,
        ancestorMeetsSse,
        southwestDetails
      );
      visitIfVisible(
        primitive,
        southeast,
        tileProvider,
        frameState,
        occluders,
        ancestorMeetsSse,
        southeastDetails
      );
      visitIfVisible(
        primitive,
        northwest,
        tileProvider,
        frameState,
        occluders,
        ancestorMeetsSse,
        northwestDetails
      );
      visitIfVisible(
        primitive,
        northeast,
        tileProvider,
        frameState,
        occluders,
        ancestorMeetsSse,
        northeastDetails
      );
    } else {
      // Camera in northwest quadrant
      visitIfVisible(
        primitive,
        northwest,
        tileProvider,
        frameState,
        occluders,
        ancestorMeetsSse,
        northwestDetails
      );
      visitIfVisible(
        primitive,
        southwest,
        tileProvider,
        frameState,
        occluders,
        ancestorMeetsSse,
        southwestDetails
      );
      visitIfVisible(
        primitive,
        northeast,
        tileProvider,
        frameState,
        occluders,
        ancestorMeetsSse,
        northeastDetails
      );
      visitIfVisible(
        primitive,
        southeast,
        tileProvider,
        frameState,
        occluders,
        ancestorMeetsSse,
        southeastDetails
      );
    }
  } else if (cameraPosition.latitude < southwest.rectangle.north) {
    // Camera southeast quadrant
    visitIfVisible(
      primitive,
      southeast,
      tileProvider,
      frameState,
      occluders,
      ancestorMeetsSse,
      southeastDetails
    );
    visitIfVisible(
      primitive,
      southwest,
      tileProvider,
      frameState,
      occluders,
      ancestorMeetsSse,
      southwestDetails
    );
    visitIfVisible(
      primitive,
      northeast,
      tileProvider,
      frameState,
      occluders,
      ancestorMeetsSse,
      northeastDetails
    );
    visitIfVisible(
      primitive,
      northwest,
      tileProvider,
      frameState,
      occluders,
      ancestorMeetsSse,
      northwestDetails
    );
  } else {
    // Camera in northeast quadrant
    visitIfVisible(
      primitive,
      northeast,
      tileProvider,
      frameState,
      occluders,
      ancestorMeetsSse,
      northeastDetails
    );
    visitIfVisible(
      primitive,
      northwest,
      tileProvider,
      frameState,
      occluders,
      ancestorMeetsSse,
      northwestDetails
    );
    visitIfVisible(
      primitive,
      southeast,
      tileProvider,
      frameState,
      occluders,
      ancestorMeetsSse,
      southeastDetails
    );
    visitIfVisible(
      primitive,
      southwest,
      tileProvider,
      frameState,
      occluders,
      ancestorMeetsSse,
      southwestDetails
    );
  }

  quadDetails.combine(traversalDetails);
}

function containsNeededPosition(primitive, tile) {
  var rectangle = tile.rectangle;
  return (
    (defined(primitive._cameraPositionCartographic) &&
      Rectangle.contains(rectangle, primitive._cameraPositionCartographic)) ||
    (defined(primitive._cameraReferenceFrameOriginCartographic) &&
      Rectangle.contains(
        rectangle,
        primitive._cameraReferenceFrameOriginCartographic
      ))
  );
}

function visitIfVisible(
  primitive,
  tile,
  tileProvider,
  frameState,
  occluders,
  ancestorMeetsSse,
  traversalDetails
) {
  if (
    tileProvider.computeTileVisibility(tile, frameState, occluders) !==
    Visibility.NONE
  ) {
    return visitTile(
      primitive,
      frameState,
      tile,
      ancestorMeetsSse,
      traversalDetails
    );
  }

  ++primitive._debug.tilesCulled;
  primitive._tileReplacementQueue.markTileRendered(tile);

  traversalDetails.allAreRenderable = true;
  traversalDetails.anyWereRenderedLastFrame = false;
  traversalDetails.notYetRenderableCount = 0;

  if (containsNeededPosition(primitive, tile)) {
    // Load the tile(s) that contains the camera's position and
    // the origin of its reference frame with medium priority.
    // But we only need to load until the terrain is available, no need to load imagery.
    if (!defined(tile.data) || !defined(tile.data.vertexArray)) {
      queueTileLoad(
        primitive,
        primitive._tileLoadQueueMedium,
        tile,
        frameState
      );
    }

    var lastFrame = primitive._lastSelectionFrameNumber;
    var lastFrameSelectionResult =
      tile._lastSelectionResultFrame === lastFrame
        ? tile._lastSelectionResult
        : TileSelectionResult.NONE;
    if (
      lastFrameSelectionResult !== TileSelectionResult.CULLED_BUT_NEEDED &&
      lastFrameSelectionResult !== TileSelectionResult.RENDERED
    ) {
      primitive._tileToUpdateHeights.push(tile);
    }

    tile._lastSelectionResult = TileSelectionResult.CULLED_BUT_NEEDED;
  } else if (primitive.preloadSiblings || tile.level === 0) {
    // Load culled level zero tiles with low priority.
    // For all other levels, only load culled tiles if preloadSiblings is enabled.
    queueTileLoad(primitive, primitive._tileLoadQueueLow, tile, frameState);
    tile._lastSelectionResult = TileSelectionResult.CULLED;
  } else {
    tile._lastSelectionResult = TileSelectionResult.CULLED;
  }

  tile._lastSelectionResultFrame = frameState.frameNumber;
}

function screenSpaceError(primitive, frameState, tile) {
  if (
    frameState.mode === SceneMode.SCENE2D ||
    frameState.camera.frustum instanceof OrthographicFrustum ||
    frameState.camera.frustum instanceof OrthographicOffCenterFrustum
  ) {
    return screenSpaceError2D(primitive, frameState, tile);
  }

  var maxGeometricError = primitive._tileProvider.getLevelMaximumGeometricError(
    tile.level
  );

  var distance = tile._distance;
  var height = frameState.context.drawingBufferHeight;
  var sseDenominator = frameState.camera.frustum.sseDenominator;

  var error = (maxGeometricError * height) / (distance * sseDenominator);

  if (frameState.fog.enabled) {
    error -=
      CesiumMath.fog(distance, frameState.fog.density) * frameState.fog.sse;
  }

  error /= frameState.pixelRatio;

  return error;
}

function screenSpaceError2D(primitive, frameState, tile) {
  var camera = frameState.camera;
  var frustum = camera.frustum;
  if (defined(frustum._offCenterFrustum)) {
    frustum = frustum._offCenterFrustum;
  }

  var context = frameState.context;
  var width = context.drawingBufferWidth;
  var height = context.drawingBufferHeight;

  var maxGeometricError = primitive._tileProvider.getLevelMaximumGeometricError(
    tile.level
  );
  var pixelSize =
    Math.max(frustum.top - frustum.bottom, frustum.right - frustum.left) /
    Math.max(width, height);
  var error = maxGeometricError / pixelSize;

  if (frameState.fog.enabled && frameState.mode !== SceneMode.SCENE2D) {
    error -=
      CesiumMath.fog(tile._distance, frameState.fog.density) *
      frameState.fog.sse;
  }

  error /= frameState.pixelRatio;

  return error;
}

function addTileToRenderList(primitive, tile) {
  primitive._tilesToRender.push(tile);
}

function processTileLoadQueue(primitive, frameState) {
  var tileLoadQueueHigh = primitive._tileLoadQueueHigh;
  var tileLoadQueueMedium = primitive._tileLoadQueueMedium;
  var tileLoadQueueLow = primitive._tileLoadQueueLow;

  if (
    tileLoadQueueHigh.length === 0 &&
    tileLoadQueueMedium.length === 0 &&
    tileLoadQueueLow.length === 0
  ) {
    return;
  }

  // Remove any tiles that were not used this frame beyond the number
  // we're allowed to keep.
  primitive._tileReplacementQueue.trimTiles(primitive.tileCacheSize);

  var endTime = getTimestamp() + primitive._loadQueueTimeSlice;
  var tileProvider = primitive._tileProvider;

  var didSomeLoading = processSinglePriorityLoadQueue(
    primitive,
    frameState,
    tileProvider,
    endTime,
    tileLoadQueueHigh,
    false
  );
  didSomeLoading = processSinglePriorityLoadQueue(
    primitive,
    frameState,
    tileProvider,
    endTime,
    tileLoadQueueMedium,
    didSomeLoading
  );
  processSinglePriorityLoadQueue(
    primitive,
    frameState,
    tileProvider,
    endTime,
    tileLoadQueueLow,
    didSomeLoading
  );
}

function sortByLoadPriority(a, b) {
  return a._loadPriority - b._loadPriority;
}

function processSinglePriorityLoadQueue(
  primitive,
  frameState,
  tileProvider,
  endTime,
  loadQueue,
  didSomeLoading
) {
  if (tileProvider.computeTileLoadPriority !== undefined) {
    loadQueue.sort(sortByLoadPriority);
  }

  for (
    var i = 0, len = loadQueue.length;
    i < len && (getTimestamp() < endTime || !didSomeLoading);
    ++i
  ) {
    var tile = loadQueue[i];
    primitive._tileReplacementQueue.markTileRendered(tile);
    tileProvider.loadTile(frameState, tile);
    didSomeLoading = true;
  }

  return didSomeLoading;
}

var scratchRay = new Ray();
var scratchCartographic = new Cartographic();
var scratchPosition = new Cartesian3();
var scratchArray = [];

function updateHeights(primitive, frameState) {
  if (!primitive.tileProvider.ready) {
    return;
  }

  var tryNextFrame = scratchArray;
  tryNextFrame.length = 0;
  var tilesToUpdateHeights = primitive._tileToUpdateHeights;
  var terrainProvider = primitive._tileProvider.terrainProvider;

  var startTime = getTimestamp();
  var timeSlice = primitive._updateHeightsTimeSlice;
  var endTime = startTime + timeSlice;

  var mode = frameState.mode;
  var projection = frameState.mapProjection;
  var ellipsoid = primitive.tileProvider.tilingScheme.ellipsoid;
  var i;

  while (tilesToUpdateHeights.length > 0) {
    var tile = tilesToUpdateHeights[0];
    if (!defined(tile.data) || !defined(tile.data.mesh)) {
      // Tile isn't loaded enough yet, so try again next frame if this tile is still
      // being rendered.
      var selectionResult =
        tile._lastSelectionResultFrame === primitive._lastSelectionFrameNumber
          ? tile._lastSelectionResult
          : TileSelectionResult.NONE;
      if (
        selectionResult === TileSelectionResult.RENDERED ||
        selectionResult === TileSelectionResult.CULLED_BUT_NEEDED
      ) {
        tryNextFrame.push(tile);
      }
      tilesToUpdateHeights.shift();
      primitive._lastTileIndex = 0;
      continue;
    }
    var customData = tile.customData;
    var customDataLength = customData.length;

    var timeSliceMax = false;
    for (i = primitive._lastTileIndex; i < customDataLength; ++i) {
      var data = customData[i];

      if (tile.level > data.level) {
        if (!defined(data.positionOnEllipsoidSurface)) {
          // cartesian has to be on the ellipsoid surface for `ellipsoid.geodeticSurfaceNormal`
          data.positionOnEllipsoidSurface = Cartesian3.fromRadians(
            data.positionCartographic.longitude,
            data.positionCartographic.latitude,
            0.0,
            ellipsoid
          );
        }

        if (mode === SceneMode.SCENE3D) {
          var surfaceNormal = ellipsoid.geodeticSurfaceNormal(
            data.positionOnEllipsoidSurface,
            scratchRay.direction
          );

          // compute origin point

          // Try to find the intersection point between the surface normal and z-axis.
          // minimum height (-11500.0) for the terrain set, need to get this information from the terrain provider
          var rayOrigin = ellipsoid.getSurfaceNormalIntersectionWithZAxis(
            data.positionOnEllipsoidSurface,
            11500.0,
            scratchRay.origin
          );

          // Theoretically, not with Earth datums, the intersection point can be outside the ellipsoid
          if (!defined(rayOrigin)) {
            // intersection point is outside the ellipsoid, try other value
            // minimum height (-11500.0) for the terrain set, need to get this information from the terrain provider
            var minimumHeight;
            if (defined(tile.data.tileBoundingRegion)) {
              minimumHeight = tile.data.tileBoundingRegion.minimumHeight;
            }
            var magnitude = Math.min(
              defaultValue(minimumHeight, 0.0),
              -11500.0
            );

            // multiply by the *positive* value of the magnitude
            var vectorToMinimumPoint = Cartesian3.multiplyByScalar(
              surfaceNormal,
              Math.abs(magnitude) + 1,
              scratchPosition
            );
            Cartesian3.subtract(
              data.positionOnEllipsoidSurface,
              vectorToMinimumPoint,
              scratchRay.origin
            );
          }
        } else {
          Cartographic.clone(data.positionCartographic, scratchCartographic);

          // minimum height for the terrain set, need to get this information from the terrain provider
          scratchCartographic.height = -11500.0;
          projection.project(scratchCartographic, scratchPosition);
          Cartesian3.fromElements(
            scratchPosition.z,
            scratchPosition.x,
            scratchPosition.y,
            scratchPosition
          );
          Cartesian3.clone(scratchPosition, scratchRay.origin);
          Cartesian3.clone(Cartesian3.UNIT_X, scratchRay.direction);
        }

        var position = tile.data.pick(
          scratchRay,
          mode,
          projection,
          false,
          scratchPosition
        );
        if (defined(position)) {
          data.callback(position);
          data.level = tile.level;
        }
      } else if (tile.level === data.level) {
        var children = tile.children;
        var childrenLength = children.length;

        var child;
        for (var j = 0; j < childrenLength; ++j) {
          child = children[j];
          if (Rectangle.contains(child.rectangle, data.positionCartographic)) {
            break;
          }
        }

        var tileDataAvailable = terrainProvider.getTileDataAvailable(
          child.x,
          child.y,
          child.level
        );
        var parentTile = tile.parent;
        if (
          (defined(tileDataAvailable) && !tileDataAvailable) ||
          (defined(parentTile) &&
            defined(parentTile.data) &&
            defined(parentTile.data.terrainData) &&
            !parentTile.data.terrainData.isChildAvailable(
              parentTile.x,
              parentTile.y,
              child.x,
              child.y
            ))
        ) {
          data.removeFunc();
        }
      }

      if (getTimestamp() >= endTime) {
        timeSliceMax = true;
        break;
      }
    }

    if (timeSliceMax) {
      primitive._lastTileIndex = i;
      break;
    } else {
      primitive._lastTileIndex = 0;
      tilesToUpdateHeights.shift();
    }
  }
  for (i = 0; i < tryNextFrame.length; i++) {
    tilesToUpdateHeights.push(tryNextFrame[i]);
  }
}

function createRenderCommandsForSelectedTiles(primitive, frameState) {
  var tileProvider = primitive._tileProvider;
  var tilesToRender = primitive._tilesToRender;

  for (var i = 0, len = tilesToRender.length; i < len; ++i) {
    var tile = tilesToRender[i];
    tileProvider.showTileThisFrame(tile, frameState);
  }
}
export default QuadtreePrimitive;