Press n or j to go to the next uncovered block, b, p or k for the previous block.
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 | 1x 1624x 1624x 1624x 1624x 1624x 4761x 4761x 4761x 4761x 4761x 548x 548x 548x 548x 548x 548x 540x 540x 540x 540x 540x 540x 1x 818x 817x 816x 4x 812x 1x 277x 276x 2x 274x 12x 274x 274x 274x 1x 1596x 1595x 1594x 1593x 6x 1587x 1x 183x 182x 2x 180x 13x 180x 180x 180x 180x | 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
*/
const 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;
|