import Check from "./Check.js";
|
import defined from "./defined.js";
|
import DeveloperError from "./DeveloperError.js";
|
|
/**
|
* Morton Order (aka Z-Order Curve) helper functions.
|
* @see {@link https://en.wikipedia.org/wiki/Z-order_curve}
|
*
|
* @namespace MortonOrder
|
* @private
|
*/
|
var MortonOrder = {};
|
|
/**
|
* Inserts one 0 bit of spacing between a number's bits. This is the opposite of removeOneSpacing.
|
*
|
* Example:
|
* input: 6
|
* input (binary): 110
|
* output (binary): 10100
|
* ^ ^ (added)
|
* output: 20
|
*
|
* @private
|
* @param {Number} v A 16-bit unsigned integer.
|
* @returns {Number} A 32-bit unsigned integer.
|
* @see {@link https://fgiesen.wordpress.com/2009/12/13/decoding-morton-codes/}
|
* @private
|
*/
|
function insertOneSpacing(v) {
|
v = (v ^ (v << 8)) & 0x00ff00ff;
|
v = (v ^ (v << 4)) & 0x0f0f0f0f;
|
v = (v ^ (v << 2)) & 0x33333333;
|
v = (v ^ (v << 1)) & 0x55555555;
|
return v;
|
}
|
|
/**
|
* Inserts two 0 bits of spacing between a number's bits. This is the opposite of removeTwoSpacing.
|
*
|
* Example:
|
* input: 6
|
* input (binary): 110
|
* output (binary): 1001000
|
* ^^ ^^ (added)
|
* output: 72
|
*
|
* @private
|
* @param {Number} v A 10-bit unsigned integer.
|
* @returns {Number} A 30-bit unsigned integer.
|
* @see {@link https://fgiesen.wordpress.com/2009/12/13/decoding-morton-codes/}
|
*/
|
function insertTwoSpacing(v) {
|
v = (v ^ (v << 16)) & 0x030000ff;
|
v = (v ^ (v << 8)) & 0x0300f00f;
|
v = (v ^ (v << 4)) & 0x030c30c3;
|
v = (v ^ (v << 2)) & 0x09249249;
|
return v;
|
}
|
|
/**
|
* Removes one bit of spacing between bits. This is the opposite of insertOneSpacing.
|
*
|
* Example:
|
* input: 20
|
* input (binary): 10100
|
* ^ ^ (removed)
|
* output (binary): 110
|
* output: 6
|
*
|
* @private
|
* @param {Number} v A 32-bit unsigned integer.
|
* @returns {Number} A 16-bit unsigned integer.
|
* @see {@link https://fgiesen.wordpress.com/2009/12/13/decoding-morton-codes/}
|
*/
|
function removeOneSpacing(v) {
|
v &= 0x55555555;
|
v = (v ^ (v >> 1)) & 0x33333333;
|
v = (v ^ (v >> 2)) & 0x0f0f0f0f;
|
v = (v ^ (v >> 4)) & 0x00ff00ff;
|
v = (v ^ (v >> 8)) & 0x0000ffff;
|
return v;
|
}
|
|
/**
|
* Removes two bits of spacing between bits. This is the opposite of insertTwoSpacing.
|
*
|
* Example:
|
* input: 72
|
* input (binary): 1001000
|
* ^^ ^^ (removed)
|
* output (binary): 110
|
* output: 6
|
*
|
* @private
|
* @param {Number} v A 30-bit unsigned integer.
|
* @returns {Number} A 10-bit unsigned integer.
|
* @see {@link https://fgiesen.wordpress.com/2009/12/13/decoding-morton-codes/}
|
*/
|
function removeTwoSpacing(v) {
|
v &= 0x09249249;
|
v = (v ^ (v >> 2)) & 0x030c30c3;
|
v = (v ^ (v >> 4)) & 0x0300f00f;
|
v = (v ^ (v >> 8)) & 0xff0000ff;
|
v = (v ^ (v >> 16)) & 0x000003ff;
|
return v;
|
}
|
|
/**
|
* Computes the Morton index from 2D coordinates. This is equivalent to interleaving their bits.
|
* The inputs must be 16-bit unsigned integers (resulting in 32-bit Morton index) due to 32-bit bitwise operator limitation in JavaScript.
|
*
|
* @param {Number} x The X coordinate in the range [0, (2^16)-1].
|
* @param {Number} y The Y coordinate in the range [0, (2^16)-1].
|
* @returns {Number} The Morton index.
|
* @private
|
*/
|
MortonOrder.encode2D = function (x, y) {
|
//>>includeStart('debug', pragmas.debug);
|
Check.typeOf.number("x", x);
|
Check.typeOf.number("y", y);
|
if (x < 0 || x > 65535 || y < 0 || y > 65535) {
|
throw new DeveloperError("inputs must be 16-bit unsigned integers");
|
}
|
//>>includeEnd('debug');
|
|
// Note: JavaScript bitwise operations return signed 32-bit integers, so the
|
// final result needs to be reintepreted as an unsigned integer using >>> 0.
|
// This is not needed for encode3D because the result is guaranteed to be at most
|
// 30 bits and thus will always be interpreted as an unsigned value.
|
return (insertOneSpacing(x) | (insertOneSpacing(y) << 1)) >>> 0;
|
};
|
|
/**
|
* Computes the 2D coordinates from a Morton index. This is equivalent to deinterleaving their bits.
|
* The input must be a 32-bit unsigned integer (resulting in 16 bits per coordinate) due to 32-bit bitwise operator limitation in JavaScript.
|
*
|
* @param {Number} mortonIndex The Morton index in the range [0, (2^32)-1].
|
* @param {Number[]} [result] The array onto which to store the result.
|
* @returns {Number[]} An array containing the 2D coordinates correspoding to the Morton index.
|
* @private
|
*/
|
MortonOrder.decode2D = function (mortonIndex, result) {
|
//>>includeStart('debug', pragmas.debug);
|
Check.typeOf.number("mortonIndex", mortonIndex);
|
if (mortonIndex < 0 || mortonIndex > 4294967295) {
|
throw new DeveloperError("input must be a 32-bit unsigned integer");
|
}
|
//>>includeEnd('debug');
|
|
if (!defined(result)) {
|
result = new Array(2);
|
}
|
|
result[0] = removeOneSpacing(mortonIndex);
|
result[1] = removeOneSpacing(mortonIndex >> 1);
|
return result;
|
};
|
|
/**
|
* Computes the Morton index from 3D coordinates. This is equivalent to interleaving their bits.
|
* The inputs must be 10-bit unsigned integers (resulting in 30-bit Morton index) due to 32-bit bitwise operator limitation in JavaScript.
|
*
|
* @param {Number} x The X coordinate in the range [0, (2^10)-1].
|
* @param {Number} y The Y coordinate in the range [0, (2^10)-1].
|
* @param {Number} z The Z coordinate in the range [0, (2^10)-1].
|
* @returns {Number} The Morton index.
|
* @private
|
*/
|
MortonOrder.encode3D = function (x, y, z) {
|
//>>includeStart('debug', pragmas.debug);
|
Check.typeOf.number("x", x);
|
Check.typeOf.number("y", y);
|
Check.typeOf.number("z", z);
|
if (x < 0 || x > 1023 || y < 0 || y > 1023 || z < 0 || z > 1023) {
|
throw new DeveloperError("inputs must be 10-bit unsigned integers");
|
}
|
//>>includeEnd('debug');
|
|
return (
|
insertTwoSpacing(x) |
|
(insertTwoSpacing(y) << 1) |
|
(insertTwoSpacing(z) << 2)
|
);
|
};
|
|
/**
|
* Computes the 3D coordinates from a Morton index. This is equivalent to deinterleaving their bits.
|
* The input must be a 30-bit unsigned integer (resulting in 10 bits per coordinate) due to 32-bit bitwise operator limitation in JavaScript.
|
*
|
* @param {Number} mortonIndex The Morton index in the range [0, (2^30)-1].
|
* @param {Number[]} [result] The array onto which to store the result.
|
* @returns {Number[]} An array containing the 3D coordinates corresponding to the Morton index.
|
* @private
|
*/
|
MortonOrder.decode3D = function (mortonIndex, result) {
|
//>>includeStart('debug', pragmas.debug);
|
Check.typeOf.number("mortonIndex", mortonIndex);
|
if (mortonIndex < 0 || mortonIndex > 1073741823) {
|
throw new DeveloperError("input must be a 30-bit unsigned integer");
|
}
|
//>>includeEnd('debug');
|
|
if (!defined(result)) {
|
result = new Array(3);
|
}
|
|
result[0] = removeTwoSpacing(mortonIndex);
|
result[1] = removeTwoSpacing(mortonIndex >> 1);
|
result[2] = removeTwoSpacing(mortonIndex >> 2);
|
return result;
|
};
|
|
export default MortonOrder;
|
