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;
