commit 765d4712d38454484fc1c49f71928d5cd34e994b
parent fcef40d165201c431679cf739fe8d38586bc35e9
Author: vaplv <vaplv@free.fr>
Date: Mon, 11 Jan 2021 12:20:42 +0100
Add and test the 3D morton encoding/decoding
Diffstat:
4 files changed, 154 insertions(+), 0 deletions(-)
diff --git a/cmake/CMakeLists.txt b/cmake/CMakeLists.txt
@@ -230,6 +230,7 @@ if(NOT NO_TEST)
new_test(test_math ${MATH_LIB})
new_test(test_mem_allocator rsys)
new_test(test_misc)
+ new_test(test_morton)
new_test(test_quaternion rsys)
new_test(test_ref)
new_test(test_signal rsys)
diff --git a/src/morton.h b/src/morton.h
@@ -0,0 +1,65 @@
+/* Copyright (C) 2013-2020 Vincent Forest (vaplv@free.fr)
+ *
+ * The RSys library is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU Lesser General Public License as published
+ * by the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * The RSys library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public License
+ * along with the RSys library. If not, see <http://www.gnu.org/licenses/>. */
+
+#ifndef MORTON_H
+#define MORTON_H
+
+#include "rsys.h"
+
+static INLINE uint64_t
+morton3D_encode_u21(const uint32_t u21)
+{
+ uint64_t u64 = u21 & ((1<<21) - 1);
+ ASSERT(u21 <= ((1 << 21) - 1));
+ u64 = (u64 | (u64 << 32)) & 0xFFFF00000000FFFF;
+ u64 = (u64 | (u64 << 16)) & 0x00FF0000FF0000FF;
+ u64 = (u64 | (u64 << 8)) & 0xF00F00F00F00F00F;
+ u64 = (u64 | (u64 << 4)) & 0x30C30C30C30C30C3;
+ u64 = (u64 | (u64 << 2)) & 0x9249249249249249;
+ return u64;
+}
+
+static INLINE uint32_t
+morton3D_decode_u21(const uint64_t u64)
+{
+ uint64_t tmp = (u64 & 0x9249249249249249);
+ tmp = (tmp | (tmp >> 2)) & 0x30C30C30C30C30C3;
+ tmp = (tmp | (tmp >> 4)) & 0xF00F00F00F00F00F;
+ tmp = (tmp | (tmp >> 8)) & 0x00FF0000FF0000FF;
+ tmp = (tmp | (tmp >> 16)) & 0xFFFF00000000FFFF;
+ tmp = (tmp | (tmp >> 32)) & 0x00000000FFFFFFFF;
+ ASSERT(tmp <= ((1<<21)-1));
+ return (uint32_t)tmp;
+}
+
+static INLINE uint64_t
+morton_xyz_encode_u21(const uint32_t xyz[3])
+{
+ return (morton3D_encode_u21(xyz[0]) << 2)
+ | (morton3D_encode_u21(xyz[1]) << 1)
+ | (morton3D_encode_u21(xyz[2]) << 0);
+}
+
+static INLINE void
+morton_xyz_decode_u21(const uint64_t code, uint32_t xyz[3])
+{
+ ASSERT(xyz && code < ((1ull << 63)-1));
+ xyz[0] = (uint32_t)morton3D_decode_u21(code >> 2);
+ xyz[1] = (uint32_t)morton3D_decode_u21(code >> 1);
+ xyz[2] = (uint32_t)morton3D_decode_u21(code >> 0);
+}
+
+#endif /* MORTON_H */
+
diff --git a/src/rsys.h b/src/rsys.h
@@ -366,6 +366,11 @@ typedef int res_T;
#endif
#define BIT(Num) (1 << (Num))
+#define BIT_I32(Num) ((int32_t)1 << (Num))
+#define BIT_I64(Num) ((int64_t)1 << (Num))
+#define BIT_U32(Num) ((uint32_t)1 << (Num))
+#define BIT_U64(Num) ((uint64_t)1 << (Num))
+
#define CONCAT__(A, B) A ## B
#define CONCAT(A, B) CONCAT__(A, B)
#define SPLIT2(A) (A)[0], (A)[1]
diff --git a/src/test_morton.c b/src/test_morton.c
@@ -0,0 +1,83 @@
+/* Copyright (C) 2013-2020 Vincent Forest (vaplv@free.fr)
+ *
+ * The RSys library is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU Lesser General Public License as published
+ * by the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * The RSys library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public License
+ * along with the RSys library. If not, see <http://www.gnu.org/licenses/>. */
+
+#include "math.h"
+#include "morton.h"
+
+#include <stdlib.h>
+
+static INLINE uint32_t
+rand_u21()
+{
+ return (uint32_t)(rand() & (BIT(21)-1));
+}
+
+static INLINE uint64_t
+encode_u21(uint32_t u21)
+{
+ uint64_t mcode = 0;
+ uint32_t i;
+ for(i = (uint32_t)round_up_pow2(u21); i != 0; i >>= 1) {
+ if(i <= u21) {
+ mcode |= morton3D_encode_u21(i);
+ u21 -= i;
+ }
+ }
+ return mcode;
+}
+
+int
+main(int argc, char** argv)
+{
+ int bit = 0;
+ int i = 0;
+ (void)argc, (void)argv;
+
+ FOR_EACH(bit, 0, 21) {
+ CHK(morton3D_encode_u21(BIT_U32(bit)) == BIT_U64(3*bit));
+ CHK(morton3D_decode_u21(BIT_U64(3*bit)) == BIT_U32(bit));
+ }
+
+ FOR_EACH(i, 0, 10000) {
+ const uint32_t u21 = rand_u21();
+ const uint64_t u64 = morton3D_encode_u21(u21);
+ CHK(u64 == encode_u21(u21));
+ CHK(u21 == morton3D_decode_u21(u64));
+ }
+
+ FOR_EACH(i, 0, 10000) {
+ uint32_t xyz[3];
+ uint32_t xyz2[3];
+ uint64_t xyz_mcode[3];
+ uint64_t mcode;
+
+ xyz[0] = rand_u21();
+ xyz[1] = rand_u21();
+ xyz[2] = rand_u21();
+ mcode = morton_xyz_encode_u21(xyz);
+
+ xyz_mcode[0] = morton3D_encode_u21(xyz[0]);
+ xyz_mcode[1] = morton3D_encode_u21(xyz[1]);
+ xyz_mcode[2] = morton3D_encode_u21(xyz[2]);
+ CHK(mcode == ((xyz_mcode[0]<<2) | (xyz_mcode[1]<<1) | (xyz_mcode[2]<<0)));
+
+ morton_xyz_decode_u21(mcode, xyz2);
+ CHK(xyz[0] = xyz2[0]);
+ CHK(xyz[1] = xyz2[1]);
+ CHK(xyz[2] = xyz2[2]);
+ }
+
+ return 0;
+}
