Morton Code

모턴 코드(Morton Code)는

3차원 또는 고차원 좌표 데이터를 1차원으로 변환하여 효율적으로 관리하기 위한 방법입니다. 이를 Z-order curve라고도 부르며, 공간 분할에서 자주 사용됩니다. Morton Code는 각 좌표의 비트를 교차(interleave)하여 1차원으로 배열합니다.

각 차원의 좌표 값에서 비트를 하나씩 순서대로 꺼내어 합칩니다. 예를 들어, 3D 좌표 (x, y, z)라면, 각 차원의 비트를 교차하여 하나의 값으로 결합합니다.

#include <stdint.h>
#include <limits.h>
using namespace std;

// method to seperate bits from a given integer 3 positions apart
inline uint64_t splitBy3(unsigned int a)
{
	uint64_t x = a & 0x1fffff; // we only look at the first 21 bits
	x = (x | x << 32) & 0x1f00000000ffff; // shift left 32 bits, OR with self, and 00011111000000000000000000000000000000001111111111111111
	x = (x | x << 16) & 0x1f0000ff0000ff; // shift left 32 bits, OR with self, and 00011111000000000000000011111111000000000000000011111111
	x = (x | x << 8) & 0x100f00f00f00f00f; // shift left 32 bits, OR with self, and 0001000000001111000000001111000000001111000000001111000000000000
	x = (x | x << 4) & 0x10c30c30c30c30c3; // shift left 32 bits, OR with self, and 0001000011000011000011000011000011000011000011000011000100000000
	x = (x | x << 2) & 0x1249249249249249;
	return x;
}

inline uint64_t mortonEncode_magicbits(unsigned int x, unsigned int y, unsigned int z)
{
	uint64_t answer = 0;
	answer |= splitBy3(x) | splitBy3(y) << 1 | splitBy3(z) << 2;
	return answer;
}

Morton Code는 3D 공간에서 가까운 점들이 1D에서 가능한 한 근접한 값으로 매핑되도록 설계되어 있어 공간에서 가까운 객체를 효율적으로 검색할 수 있습니다.
특히 공간 분할 알고리즘(Spatial Partitioning)에서 3D 데이터를 효율적으로 관리하는 데 사용됩니다.

 

소스 및 관련 내용 출처:https://www.forceflow.be/2013/10/07/morton-encodingdecoding-through-bit-interleaving-implementations/