import CesiumMath from "../Core/Math.js";
|
import Check from "../Core/Check.js";
|
import DeveloperError from "../Core/DeveloperError.js";
|
import MortonOrder from "../Core/MortonOrder.js";
|
import ImplicitSubdivisionScheme from "./ImplicitSubdivisionScheme.js";
|
|
/**
|
* The coordinates for a tile in an implicit tileset. The coordinates
|
* are (level, x, y) for quadtrees or (level, x, y, z) for octrees.
|
* <p>
|
* Level numbers are 0-indexed and typically start at the root of the implicit
|
* tileset (the tile with the <code>3DTILES_implicit_tiling</code> extension).
|
* This object can also represent the relative offset from one set of coordinates
|
* to another. See {@link ImplicitTileCoordinates#getOffsetCoordinates}. The term
|
* local coordinates refers to coordinates that are relative to the root of a
|
* subtree and the term global coordinates refers to coordinates relative to the
|
* root of an implicit tileset.
|
* </p>
|
* <p>
|
* For box bounding volumes, x, y, z increase along the +x, +y, and +z
|
* directions defined by the half axes.
|
* </p>
|
* <p>
|
* For region bounding volumes, x increases in the +longitude direction, y
|
* increases in the +latitude direction, and z increases in the +height
|
* direction.
|
* </p>
|
* <p>
|
* Care must be taken when converting between implicit coordinates and Morton
|
* indices because there is a 16-bit limit on {@link MortonOrder#encode2D} and
|
* a 10-bit limit on {@link MortonOrder#encode3D}. Typically these conversions
|
* should be done on local coordinates, not global coordinates, and the maximum
|
* number of levels in the subtree should be 15 for quadtree and 9 for octree (to
|
* account for the extra level needed by child subtree coordinates).
|
* </p>
|
*
|
* @alias ImplicitTileCoordinates
|
* @constructor
|
*
|
* @param {Object} options An object with the following properties:
|
* @param {ImplicitSubdivisionScheme} options.subdivisionScheme Whether the coordinates are for a quadtree or octree
|
* @param {Number} options.subtreeLevels The number of distinct levels within the coordinate's subtree
|
* @param {Number} options.level The level of a tile relative to the tile with the extension
|
* @param {Number} options.x The x coordinate of the tile
|
* @param {Number} options.y The y coordinate of the tile
|
* @param {Number} [options.z] The z coordinate of the tile. Only required when options.subdivisionScheme is ImplicitSubdivisionScheme.OCTREE
|
* @private
|
* @experimental This feature is using part of the 3D Tiles spec that is not final and is subject to change without Cesium's standard deprecation policy.
|
*/
|
export default function ImplicitTileCoordinates(options) {
|
//>>includeStart('debug', pragmas.debug);
|
Check.typeOf.string("options.subdivisionScheme", options.subdivisionScheme);
|
Check.typeOf.number("options.subtreeLevels", options.subtreeLevels);
|
Check.typeOf.number("options.level", options.level);
|
Check.typeOf.number("options.x", options.x);
|
Check.typeOf.number("options.y", options.y);
|
if (options.subdivisionScheme === ImplicitSubdivisionScheme.OCTREE) {
|
Check.typeOf.number("options.z", options.z);
|
}
|
// Check for values that are negative
|
if (options.level < 0) {
|
throw new DeveloperError("level must be non-negative");
|
}
|
if (options.x < 0) {
|
throw new DeveloperError("x must be non-negative");
|
}
|
if (options.y < 0) {
|
throw new DeveloperError("y must be non-negative");
|
}
|
if (options.subdivisionScheme === ImplicitSubdivisionScheme.OCTREE) {
|
if (options.z < 0) {
|
throw new DeveloperError("z must be non-negative");
|
}
|
}
|
|
// Check for values that are too large
|
var dimensionAtLevel = 1 << options.level;
|
if (options.x >= dimensionAtLevel) {
|
throw new DeveloperError("x is out of range");
|
}
|
if (options.y >= dimensionAtLevel) {
|
throw new DeveloperError("y is out of range");
|
}
|
if (options.subdivisionScheme === ImplicitSubdivisionScheme.OCTREE) {
|
if (options.z >= dimensionAtLevel) {
|
throw new DeveloperError("z is out of range");
|
}
|
}
|
//>>includeEnd('debug');
|
|
/**
|
* Whether the tileset is a quadtree or octree
|
*
|
* @type {ImplicitSubdivisionScheme}
|
* @readonly
|
* @private
|
*/
|
this.subdivisionScheme = options.subdivisionScheme;
|
|
/**
|
* The number of distinct levels within the coordinate's subtree
|
*
|
* @type {Number}
|
* @readonly
|
* @private
|
*/
|
this.subtreeLevels = options.subtreeLevels;
|
|
/**
|
* Level of this tile, relative to the tile with the
|
* <code>3DTILES_implicit_tiling</code> extension. Level numbers start at 0.
|
*
|
* @type {Number}
|
* @readonly
|
* @private
|
*/
|
this.level = options.level;
|
|
/**
|
* X coordinate of this tile
|
*
|
* @type {Number}
|
* @readonly
|
* @private
|
*/
|
this.x = options.x;
|
|
/**
|
* Y coordinate of this tile
|
*
|
* @type {Number}
|
* @readonly
|
* @private
|
*/
|
this.y = options.y;
|
|
/**
|
* Z coordinate of this tile. Only defined for octrees.
|
*
|
* @type {Number|undefined}
|
* @readonly
|
* @private
|
*/
|
this.z = undefined;
|
if (options.subdivisionScheme === ImplicitSubdivisionScheme.OCTREE) {
|
this.z = options.z;
|
}
|
}
|
|
Object.defineProperties(ImplicitTileCoordinates.prototype, {
|
/**
|
* An index in the range of [0, branchingFactor) that indicates
|
* which child of the parent cell these coordinates correspond to.
|
* This can be viewed as a morton index within the parent tile.
|
* <p>
|
* This is the last 3 bits of the morton index of the tile, but it can
|
* be computed more directly by concatenating the bits [z0] y0 x0
|
* </p>
|
*
|
* @type {Number}
|
* @readonly
|
* @private
|
*/
|
childIndex: {
|
get: function () {
|
var childIndex = 0;
|
childIndex |= this.x & 1;
|
childIndex |= (this.y & 1) << 1;
|
if (this.subdivisionScheme === ImplicitSubdivisionScheme.OCTREE) {
|
childIndex |= (this.z & 1) << 2;
|
}
|
|
return childIndex;
|
},
|
},
|
|
/**
|
* Get the Morton index for this tile within the current level by interleaving
|
* the bits of the x, y and z coordinates.
|
*
|
* @type {Number}
|
* @readonly
|
* @private
|
*/
|
mortonIndex: {
|
get: function () {
|
if (this.subdivisionScheme === ImplicitSubdivisionScheme.OCTREE) {
|
return MortonOrder.encode3D(this.x, this.y, this.z);
|
}
|
return MortonOrder.encode2D(this.x, this.y);
|
},
|
},
|
|
/**
|
* Get the tile index by adding the Morton index to the level offset
|
*
|
* @type {Number}
|
* @readonly
|
* @private
|
*/
|
tileIndex: {
|
get: function () {
|
var levelOffset =
|
this.subdivisionScheme === ImplicitSubdivisionScheme.OCTREE
|
? // (8^N - 1) / (8-1)
|
((1 << (3 * this.level)) - 1) / 7
|
: // (4^N - 1) / (4-1)
|
((1 << (2 * this.level)) - 1) / 3;
|
|
var mortonIndex = this.mortonIndex;
|
return levelOffset + mortonIndex;
|
},
|
},
|
});
|
|
/**
|
* Check that the two coordinates are compatible
|
* @param {ImplicitTileCoordinates} a
|
* @param {ImplicitTileCoordinates} b
|
* @private
|
*/
|
function checkMatchingSubtreeShape(a, b) {
|
if (a.subdivisionScheme !== b.subdivisionScheme) {
|
throw new DeveloperError("coordinates must have same subdivisionScheme");
|
}
|
if (a.subtreeLevels !== b.subtreeLevels) {
|
throw new DeveloperError("coordinates must have same subtreeLevels");
|
}
|
}
|
|
/**
|
* Compute the coordinates of a tile deeper in the tree with a (level, x, y, [z]) relative offset.
|
*
|
* @param {ImplicitTileCoordinates} offsetCoordinates The offset from the ancestor
|
* @returns {ImplicitTileCoordinates} The coordinates of the descendant
|
* @private
|
*/
|
ImplicitTileCoordinates.prototype.getDescendantCoordinates = function (
|
offsetCoordinates
|
) {
|
//>>includeStart('debug', pragmas.debug);
|
Check.typeOf.object("offsetCoordinates", offsetCoordinates);
|
checkMatchingSubtreeShape(this, offsetCoordinates);
|
//>>includeEnd('debug');
|
|
var descendantLevel = this.level + offsetCoordinates.level;
|
var descendantX = (this.x << offsetCoordinates.level) + offsetCoordinates.x;
|
var descendantY = (this.y << offsetCoordinates.level) + offsetCoordinates.y;
|
|
if (this.subdivisionScheme === ImplicitSubdivisionScheme.OCTREE) {
|
var descendantZ = (this.z << offsetCoordinates.level) + offsetCoordinates.z;
|
|
return new ImplicitTileCoordinates({
|
subdivisionScheme: this.subdivisionScheme,
|
subtreeLevels: this.subtreeLevels,
|
level: descendantLevel,
|
x: descendantX,
|
y: descendantY,
|
z: descendantZ,
|
});
|
}
|
|
// Quadtree
|
return new ImplicitTileCoordinates({
|
subdivisionScheme: this.subdivisionScheme,
|
subtreeLevels: this.subtreeLevels,
|
level: descendantLevel,
|
x: descendantX,
|
y: descendantY,
|
});
|
};
|
|
/**
|
* Compute the coordinates of a tile higher up in the tree by going up a number of levels.
|
*
|
* @param {Number} offsetLevels The number of levels to go up in the tree
|
* @returns {ImplicitTileCoordinates} The coordinates of the ancestor
|
* @private
|
*/
|
ImplicitTileCoordinates.prototype.getAncestorCoordinates = function (
|
offsetLevels
|
) {
|
//>>includeStart('debug', pragmas.debug);
|
Check.typeOf.number("offsetLevels", offsetLevels);
|
if (offsetLevels < 0) {
|
throw new DeveloperError("offsetLevels must be non-negative");
|
}
|
if (offsetLevels > this.level) {
|
throw new DeveloperError("ancestor cannot be above the tileset root");
|
}
|
//>>includeEnd('debug');
|
|
var divisor = 1 << offsetLevels;
|
var ancestorLevel = this.level - offsetLevels;
|
var ancestorX = Math.floor(this.x / divisor);
|
var ancestorY = Math.floor(this.y / divisor);
|
|
if (this.subdivisionScheme === ImplicitSubdivisionScheme.OCTREE) {
|
var ancestorZ = Math.floor(this.z / divisor);
|
|
return new ImplicitTileCoordinates({
|
subdivisionScheme: this.subdivisionScheme,
|
subtreeLevels: this.subtreeLevels,
|
level: ancestorLevel,
|
x: ancestorX,
|
y: ancestorY,
|
z: ancestorZ,
|
});
|
}
|
|
// Quadtree
|
return new ImplicitTileCoordinates({
|
subdivisionScheme: this.subdivisionScheme,
|
subtreeLevels: this.subtreeLevels,
|
level: ancestorLevel,
|
x: ancestorX,
|
y: ancestorY,
|
});
|
};
|
|
/**
|
* Compute the (level, x, y, [z]) offset to a descendant
|
*
|
* @param {ImplicitTileCoordinates} descendantCoordinates The descendant coordinates
|
* @returns {ImplicitTileCoordinates} The offset between the ancestor and the descendant
|
*/
|
ImplicitTileCoordinates.prototype.getOffsetCoordinates = function (
|
descendantCoordinates
|
) {
|
//>>includeStart('debug', pragmas.debug);
|
Check.typeOf.object("descendantCoordinates", descendantCoordinates);
|
if (
|
!this.isEqual(descendantCoordinates) &&
|
!this.isAncestor(descendantCoordinates)
|
) {
|
throw new DeveloperError("this is not an ancestor of descendant");
|
}
|
checkMatchingSubtreeShape(this, descendantCoordinates);
|
//>>includeEnd('debug');
|
|
var offsetLevel = descendantCoordinates.level - this.level;
|
var dimensionAtOffsetLevel = 1 << offsetLevel;
|
|
var offsetX = descendantCoordinates.x % dimensionAtOffsetLevel;
|
var offsetY = descendantCoordinates.y % dimensionAtOffsetLevel;
|
|
if (this.subdivisionScheme === ImplicitSubdivisionScheme.OCTREE) {
|
var offsetZ = descendantCoordinates.z % dimensionAtOffsetLevel;
|
|
return new ImplicitTileCoordinates({
|
subdivisionScheme: this.subdivisionScheme,
|
subtreeLevels: this.subtreeLevels,
|
level: offsetLevel,
|
x: offsetX,
|
y: offsetY,
|
z: offsetZ,
|
});
|
}
|
|
// Quadtree
|
return new ImplicitTileCoordinates({
|
subdivisionScheme: this.subdivisionScheme,
|
subtreeLevels: this.subtreeLevels,
|
level: offsetLevel,
|
x: offsetX,
|
y: offsetY,
|
});
|
};
|
|
/**
|
* Given the morton index of the child, compute the coordinates of the child.
|
* This is a special case of {@link ImplicitTileCoordinates#getDescendantCoordinates}.
|
*
|
* @param {Number} childIndex The morton index of the child tile relative to its parent
|
* @returns {ImplicitTileCoordinates} The tile coordinates of the child
|
* @private
|
*/
|
ImplicitTileCoordinates.prototype.getChildCoordinates = function (childIndex) {
|
//>>includeStart('debug', pragmas.debug);
|
Check.typeOf.number("childIndex", childIndex);
|
var branchingFactor = ImplicitSubdivisionScheme.getBranchingFactor(
|
this.subdivisionScheme
|
);
|
if (childIndex < 0 || branchingFactor <= childIndex) {
|
throw new DeveloperError(
|
"childIndex must be at least 0 and less than " + branchingFactor
|
);
|
}
|
//>>includeEnd('debug');
|
|
var level = this.level + 1;
|
var x = 2 * this.x + (childIndex % 2);
|
var y = 2 * this.y + (Math.floor(childIndex / 2) % 2);
|
|
if (this.subdivisionScheme === ImplicitSubdivisionScheme.OCTREE) {
|
var z = 2 * this.z + (Math.floor(childIndex / 4) % 2);
|
return new ImplicitTileCoordinates({
|
subdivisionScheme: this.subdivisionScheme,
|
subtreeLevels: this.subtreeLevels,
|
level: level,
|
x: x,
|
y: y,
|
z: z,
|
});
|
}
|
|
// Quadtree
|
return new ImplicitTileCoordinates({
|
subdivisionScheme: this.subdivisionScheme,
|
subtreeLevels: this.subtreeLevels,
|
level: level,
|
x: x,
|
y: y,
|
});
|
};
|
|
/**
|
* Get the coordinates of the subtree that contains this tile. If the tile is
|
* the root of the subtree, the root of the subtree is returned.
|
*
|
* @returns {ImplicitTileCoordinates} The subtree that contains this tile
|
* @private
|
*/
|
ImplicitTileCoordinates.prototype.getSubtreeCoordinates = function () {
|
return this.getAncestorCoordinates(this.level % this.subtreeLevels);
|
};
|
|
/**
|
* Get the coordinates of the parent subtree that contains this tile
|
*
|
* @returns {ImplicitTileCoordinates} The parent subtree that contains this tile
|
* @private
|
*/
|
ImplicitTileCoordinates.prototype.getParentSubtreeCoordinates = function () {
|
return this.getAncestorCoordinates(
|
(this.level % this.subtreeLevels) + this.subtreeLevels
|
);
|
};
|
|
/**
|
* Returns whether this tile is an ancestor of another tile
|
*
|
* @param {ImplicitTileCoordinates} descendantCoordinates the descendant coordinates
|
* @returns {Boolean} <code>true</code> if this tile is an ancestor of the other tile
|
* @private
|
*/
|
ImplicitTileCoordinates.prototype.isAncestor = function (
|
descendantCoordinates
|
) {
|
//>>includeStart('debug', pragmas.debug);
|
Check.typeOf.object("descendantCoordinates", descendantCoordinates);
|
checkMatchingSubtreeShape(this, descendantCoordinates);
|
//>>includeEnd('debug');
|
|
var levelDifference = descendantCoordinates.level - this.level;
|
if (levelDifference <= 0) {
|
return false;
|
}
|
|
var ancestorX = descendantCoordinates.x >> levelDifference;
|
var ancestorY = descendantCoordinates.y >> levelDifference;
|
var isAncestorX = this.x === ancestorX;
|
var isAncestorY = this.y === ancestorY;
|
|
if (this.subdivisionScheme === ImplicitSubdivisionScheme.OCTREE) {
|
var ancestorZ = descendantCoordinates.z >> levelDifference;
|
var isAncestorZ = this.z === ancestorZ;
|
return isAncestorX && isAncestorY && isAncestorZ;
|
}
|
|
// Quadtree
|
return isAncestorX && isAncestorY;
|
};
|
|
/**
|
* Returns whether the provided coordinates are equal to this coordinate
|
*
|
* @param {ImplicitTileCoordinates} otherCoordinates the other coordinates
|
* @returns {Boolean} <code>true</code> if the coordinates are equal
|
* @private
|
*/
|
ImplicitTileCoordinates.prototype.isEqual = function (otherCoordinates) {
|
//>>includeStart('debug', pragmas.debug);
|
Check.typeOf.object("otherCoordinates", otherCoordinates);
|
//>>includeEnd('debug');
|
|
return (
|
this.subdivisionScheme === otherCoordinates.subdivisionScheme &&
|
this.subtreeLevels === otherCoordinates.subtreeLevels &&
|
this.level === otherCoordinates.level &&
|
this.x === otherCoordinates.x &&
|
this.y === otherCoordinates.y &&
|
(this.subdivisionScheme === ImplicitSubdivisionScheme.OCTREE
|
? this.z === otherCoordinates.z
|
: true)
|
);
|
};
|
|
/**
|
* Returns whether this tile is the root of the implicit tileset
|
*
|
* @returns {Boolean} <code>true</code> if this tile is the root
|
* @private
|
*/
|
ImplicitTileCoordinates.prototype.isImplicitTilesetRoot = function () {
|
return this.level === 0;
|
};
|
|
/**
|
* Returns whether this tile is the root of the subtree
|
*
|
* @returns {Boolean} <code>true</code> if this tile is the root of the subtree
|
* @private
|
*/
|
ImplicitTileCoordinates.prototype.isSubtreeRoot = function () {
|
return this.level % this.subtreeLevels === 0;
|
};
|
|
/**
|
* Returns whether this tile is on the last row of tiles in the subtree
|
*
|
* @returns {Boolean} <code>true</code> if this tile is on the last row of tiles in the subtree
|
* @private
|
*/
|
ImplicitTileCoordinates.prototype.isBottomOfSubtree = function () {
|
return this.level % this.subtreeLevels === this.subtreeLevels - 1;
|
};
|
|
/**
|
* Get a dictionary of values for templating into an implicit template URI.
|
*
|
* @returns {Object} An object suitable for use with {@link Resource#getDerivedResource}
|
* @private
|
*/
|
ImplicitTileCoordinates.prototype.getTemplateValues = function () {
|
var values = {
|
level: this.level,
|
x: this.x,
|
y: this.y,
|
};
|
if (this.subdivisionScheme === ImplicitSubdivisionScheme.OCTREE) {
|
values.z = this.z;
|
}
|
|
return values;
|
};
|
|
var scratchCoordinatesArray = [0, 0, 0];
|
|
/**
|
* Given a level number, morton index, and whether the tileset is an
|
* octree/quadtree, compute the (level, x, y, [z]) coordinates
|
*
|
* @param {ImplicitSubdivisionScheme} subdivisionScheme Whether the coordinates are for a quadtree or octree
|
* @param {Number} subtreeLevels The number of distinct levels within the coordinate's subtree
|
* @param {Number} level The level of the tree
|
* @param {Number} mortonIndex The morton index of the tile.
|
* @returns {ImplicitTileCoordinates} The coordinates of the tile with the given Morton index
|
* @private
|
*/
|
ImplicitTileCoordinates.fromMortonIndex = function (
|
subdivisionScheme,
|
subtreeLevels,
|
level,
|
mortonIndex
|
) {
|
var coordinatesArray;
|
if (subdivisionScheme === ImplicitSubdivisionScheme.OCTREE) {
|
coordinatesArray = MortonOrder.decode3D(
|
mortonIndex,
|
scratchCoordinatesArray
|
);
|
return new ImplicitTileCoordinates({
|
subdivisionScheme: subdivisionScheme,
|
subtreeLevels: subtreeLevels,
|
level: level,
|
x: coordinatesArray[0],
|
y: coordinatesArray[1],
|
z: coordinatesArray[2],
|
});
|
}
|
|
coordinatesArray = MortonOrder.decode2D(mortonIndex, scratchCoordinatesArray);
|
return new ImplicitTileCoordinates({
|
subdivisionScheme: subdivisionScheme,
|
subtreeLevels: subtreeLevels,
|
level: level,
|
x: coordinatesArray[0],
|
y: coordinatesArray[1],
|
});
|
};
|
|
/**
|
* Given a tile index and whether the tileset is an octree/quadtree, compute
|
* the (level, x, y, [z]) coordinates
|
*
|
* @param {ImplicitSubdivisionScheme} subdivisionScheme Whether the coordinates are for a quadtree or octree
|
* @param {Number} subtreeLevels The number of distinct levels within the coordinate's subtree
|
* @param {Number} tileIndex The tile's index
|
* @returns {ImplicitTileCoordinates} The coordinates of the tile with the given tile index
|
* @private
|
*/
|
ImplicitTileCoordinates.fromTileIndex = function (
|
subdivisionScheme,
|
subtreeLevels,
|
tileIndex
|
) {
|
var level;
|
var levelOffset;
|
var mortonIndex;
|
|
if (subdivisionScheme === ImplicitSubdivisionScheme.OCTREE) {
|
// Node count up to octree level: (8^L - 1) / (8-1)
|
// (8^L - 1) / (8-1) <= X < (8^(L+1) - 1) / (8-1)
|
// 8^L <= (7x + 1) < 8^(L+1)
|
// L <= log8(7x + 1) < L + 1
|
// L = floor(log8(7x + 1))
|
// L = floor(log2(7x + 1) / log2(8))
|
// L = floor(log2(7x + 1) / 3)
|
level = Math.floor(CesiumMath.log2(7 * tileIndex + 1) / 3);
|
levelOffset = ((1 << (3 * level)) - 1) / 7;
|
mortonIndex = tileIndex - levelOffset;
|
} else {
|
// Node count up to quadtree level: (4^L - 1) / (4-1)
|
// (4^L - 1) / (4-1) <= X < (4^(L+1) - 1) / (4-1)
|
// 4^L <= (3x + 1) < 4^(L+1)
|
// L <= log4(3x + 1) < L + 1
|
// L = floor(log4(3x + 1))
|
// L = floor(log2(3x + 1) / log2(4))
|
// L = floor(log2(3x + 1) / 2)
|
level = Math.floor(CesiumMath.log2(3 * tileIndex + 1) / 2);
|
levelOffset = ((1 << (2 * level)) - 1) / 3;
|
mortonIndex = tileIndex - levelOffset;
|
}
|
|
return ImplicitTileCoordinates.fromMortonIndex(
|
subdivisionScheme,
|
subtreeLevels,
|
level,
|
mortonIndex
|
);
|
};
|
