Z-Order Curve

GPU가 텍스처 메모리에 이미지 데이터를 저장할 때는 일렬로 나열된 형태가 아니라 Z-Order Curve 형태를 사용한다. 이러한 이유는 인접 픽셀의 색을 가져올 때 (캐시 메모리의) hit rate를 높이기 위해서이다.
이러한 Z-Order Curve 형태로 변환하는 프로세서를 Texture Swizzling이라고 부른다. 그래픽 프로세서가 이미지를 읽는 방식에 더 적합하도록 이미지의 필셀 순서를 재조정 하는 프로세서이다.
다만 특정 그래픽카드(예: Nvidia GTX OOOO)가 내부적으로 어떤 자료구조를 사용하는 지는 제조사가 결정한다.

Z-Order Curve는 또한 다차원 데이터를 하나의 차원으로 매핑하면서 데이터 포인트의 지역성을 유지한다. 지역성이 잃는다를 예를 들자면, 2D to 1D로 변환할 때 공간에 대한 정보가 깨진다고 한다. 하지만 Z-Curve를 하면 공간의 정보를 유지하면서 일렬로 매핑할 수 있다.

Z-Order Curve를 Morton Code라고도 부른다.

그림 출처 : https://en.wikipedia.org/wiki/Z-order_curve

#include <stdio.h>
static const unsigned int B[] = { 0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF };
static const unsigned int S[] = { 1, 2, 4, 8 };
unsigned int zorder2D(unsigned x, unsigned y) {

    x = (x | (x << S[3])) & B[3];
    x = (x | (x << S[2])) & B[2];
    x = (x | (x << S[1])) & B[1];
    x = (x | (x << S[0])) & B[0];

    y = (y | (y << S[3])) & B[3];
    y = (y | (y << S[2])) & B[2];
    y = (y | (y << S[1])) & B[1];
    y = (y | (y << S[0])) & B[0];
    return x | (y << 1);
}

int main()
{
    const unsigned nx = 8, ny = 8;
    unsigned res[ny][nx];

    for (unsigned y = 0; y < ny; y++) {
        for (unsigned x = 0; x < nx; x++) {
            res[y][x] = zorder2D(x, y);
            printf("yx=%d %d z=%d\n", y, x, res[y][x]);
        }
    }
    for (unsigned y = 0; y < ny; y++) {
        for (unsigned x = 0; x < nx; x++) {
            printf("%-4d", res[y][x]);
        }
        printf("\n");
    }
    return 0;
}

Code 출처 : http://graphics.stanford.edu/~seander/bithacks.html