공간 채움 곡선

1. 개요[편집]

공간 채움 곡선 Space-Filling Curve
정의	구간을 정사각형(정육면체) 위로 보내는 연속 전사 사상
시초	페아노(1890) · 힐베르트(1891)
실무 3대장	힐베르트 · 모턴(Z-order) · 페아노
핵심 성질	국소성 보존 — 가까운 인덱스는 가까운 좌표
힐베르트 규칙성	$d$차원에서 $1/d$-횔더 연속
주 용도	병렬 분할 · AMR 정렬 · 캐시 지역성 · 다차원 색인

1차원과 2차원의 원소 개수가 같다는 것은 칸토어가 증명했고, 그걸 연속적으로 해 보이겠다고 나선 것이 페아노와 힐베르트다. 100년 뒤 그 곡선으로 슈퍼컴퓨터의 격자를 나누게 될 줄은 아무도 몰랐다.

공간 채움 곡선(space-filling curve, SFC)은 1차원 구간 $[0,1]$을 $d$차원 정육면체 $[0,1]^d$ 위로 보내는 연속인 전사 사상, 그리고 실무에서는 그 유한 근사로 얻어지는 격자 셀의 1차원 나열 순서를 가리킨다. 셀에 번호를 매기는 방법은 무수히 많지만, SFC가 특별한 이유는 단 하나다 — 인덱스가 가까우면 좌표도 가깝다. 이 성질 하나로 다차원 데이터를 1차원 배열·정렬·구간 자르기라는 값싼 도구로 다룰 수 있게 된다.

역사적 맥락도 짚어 둘 만하다. 칸토어(1878)가 $[0,1]$과 $[0,1]^2$ 사이의 전단사를 만들어 “차원이 개수를 결정하지 않는다”를 보이자, 네토(1879)가 연속인 전단사는 존재할 수 없음을 증명했다. 남은 가능성은 “연속이되 단사가 아닌” 경우뿐이었고, 페아노(1890)가 그것을 실제로 구성해 냈다. 그래서 모든 공간 채움 곡선은 필연적으로 자기 자신과 만난다(적어도 셀 수 없이 많은 점에서 값이 겹친다). 실무에서 쓰는 유한 레벨 이산 버전은 다행히 격자 셀과 정수 인덱스 사이의 전단사라 이 병리를 볼 일이 없다.¹

2. 페아노와 힐베르트 — 재귀적 구성[편집]

힐베르트 곡선(1891)이 가장 널리 쓰인다. 구성은 재귀 한 줄이다.

1. 정사각형을 4등분한다.
2. 구간 $[0,1]$을 4등분해 각 부분구간을 하나의 부사각형에 대응시킨다.
3. 각 부사각형 안에서 같은 곡선을 회전·반사시켜 다시 그린다. 이때 이웃한 부사각형의 끝점과 시작점이 맞닿도록 방향을 고른다.

3번의 방향 맞추기가 힐베르트의 전부다. 이 조건 덕분에 레벨 $n$ 근사에서 연속한 두 인덱스의 셀은 언제나 변을 공유한다. 즉 곡선을 따라 한 칸 나아가면 격자에서도 정확히 한 칸 움직인다. 회전·반사를 관리해야 하니 각 레벨에서 현재 방향 상태를 들고 다녀야 하고, 이것이 뒤에 나올 인코딩 비용의 원인이다.

페아노 곡선(1890)은 3진법 버전이다. 정사각형을 9등분하고 뱀처럼 왕복하며 채운다. 힐베르트보다 먼저 나왔고 구성도 단순하지만, 컴퓨터가 2의 거듭제곱을 좋아하는 탓에 실무에서는 힐베르트에 밀렸다.

$d$차원으로 올라가면 $2^d$개의 부입방체를 방향 맞춰 순회해야 한다. 3차원 힐베르트 곡선의 방향 상태는 24가지이며(정육면체의 회전군 크기), 그래서 3D 구현은 대개 24-상태 전이표를 굽는다. 게다가 3차원 이상에서는 “힐베르트 곡선”이 유일하지 않다 — 조건을 만족하는 서로 다른 순회가 여럿 있어서, 라이브러리마다 인덱스가 다를 수 있다는 함정이 있다.

3. 모턴(Z-order) 곡선[편집]

모턴 곡선(Morton order, Z-order curve)은 방향 맞추기를 아예 포기한 대신 인코딩을 극단적으로 싸게 만든 곡선이다. 1966년 IBM의 가이 모턴이 지리 데이터베이스의 파일 배열 기법으로 제안했다.

정의는 비트 인터리빙 한 줄이다. 좌표 $(x, y)$의 이진 표현이 $x = x_{n-1}\cdots x_0$, $y = y_{n-1}\cdots y_0$일 때

$$m(x,y) = x_{n-1}\,y_{n-1}\,x_{n-2}\,y_{n-2}\cdots x_0\,y_0$$

로 비트를 번갈아 끼운다. 3차원이면 세 좌표의 비트를 셋씩 번갈아 끼우면 된다. 곡선 모양이 ‘Z’자를 재귀적으로 이어 붙인 것처럼 생겨서 Z-order라는 이름이 붙었다.

대가는 이음매다. 각 ‘Z’의 마지막 셀에서 다음 ‘Z’의 첫 셀로 넘어갈 때 좌표가 크게 점프한다. 하필 그 점프의 크기가 계층 레벨에 비례해서, 최상위 레벨의 이음매는 도메인을 통째로 가로지른다. 힐베르트가 “한 칸씩” 움직이는 것과 대조적이다.

그럼에도 모턴이 널리 쓰이는 이유는 세 가지다.

• 인코딩이 사실상 공짜다. 매직 넘버 곱셈·시프트 몇 줄, 혹은 x86의 PDEP 명령 하나면 끝난다.
• 정렬이 싸다. 키가 정수이므로 기수 정렬이 그대로 먹힌다. GPU에서 수백만 개 키를 정렬하는 것이 기수 정렬 한 번이다.
• 트리 구조를 접두사로 읽을 수 있다. 모턴 키의 상위 $2k$비트는 레벨 $k$ 조상 노드의 키다. 즉 옥트리 노드를 키 하나로 표현하고, 형제는 연속 구간을 차지하며, 조상-자손 관계는 접두사 비교로 판정된다. 포인터 없는 선형 옥트리가 여기서 나온다.

세 번째 성질은 힐베르트도 갖고 있다(계층 중첩 구조는 같으므로). 다만 모턴은 그 대응이 순수 비트 연산이라 실무 코드가 압도적으로 단순해진다.

4. 국소성은 얼마나 보존되는가[편집]

“국소성 보존”에는 방향이 둘 있고, 둘의 사정이 전혀 다르다.

순방향(인덱스 → 좌표) 은 보증이 강하다. 힐베르트 사상 $h : [0,1] \to [0,1]^d$는

$$\|h(s) - h(t)\| \le C\,|s - t|^{1/d}$$

를 만족한다. 즉 $1/d$-횔더 연속이고, 이 지수는 개선할 수 없다.² 인덱스 구간을 하나 잘라 내면 그 상은 반드시 부피에 비례해 “뭉쳐” 있다는 뜻이라, 인덱스를 $k$등분하면 자동으로 공간적으로 콤팩트한 $k$조각이 나온다는 병렬 분할의 근거가 바로 이 부등식이다.

역방향(좌표 → 인덱스) 은 보증이 없다. 어떤 SFC도 인접한 두 셀의 인덱스가 항상 가깝게 만들 수는 없다 — 유한 격자에서 각 셀은 이웃이 $2d$개인데 인덱스 축에서 인접한 자리는 두 개뿐이므로 비둘기집으로 반드시 멀어지는 쌍이 생긴다. 그래서 실무의 관심사는 최악이 아니라 평균이고, 이 기준에서 힐베르트가 모턴을 이긴다. 격자 위의 직사각형 질의를 SFC 인덱스 구간들로 덮을 때 필요한 구간(클러스터) 개수가 힐베르트 쪽이 유의미하게 적다는 것이 정량 분석으로 확인돼 있다.³

정리하면 이렇다.

곡선	인접 인덱스의 좌표 거리	인코딩 비용	실무 강점
힐베르트	항상 격자 한 칸	레벨마다 상태 전이	국소성 최상, 분할·색인 품질
모턴(Z)	대개 한 칸, 이음매에서 점프	비트 인터리빙 한 번	압도적으로 쌈, 기수 정렬·GPU 친화
페아노	항상 격자 한 칸	3진 전개 필요	3의 거듭제곱 격자, 역사적 의의

여기가 이 주제의 유일한 진짜 트레이드오프다. 힐베르트는 잘 뭉치고 비싸며, 모턴은 덜 뭉치고 싸다. 키를 한 번 굽고 오래 쓰는 정적 색인이라면 힐베르트가 낫고, 매 프레임 수백만 개를 다시 굽는 GPU 트리 빌드라면 모턴이 이긴다. 반복 계산이 키 계산을 압도하는 CFD 재분할 같은 경우에는 인코딩 비용이 어차피 노이즈라 힐베르트를 쓰는 것이 정석이다.

5. 응용[편집]

병렬 분할. 셀 중심 좌표로 SFC 키를 계산하고 정렬한 뒤, 셀 가중치의 누적합을 기준으로 $k$등분한다. 이게 전부다. METIS 같은 다단계 그래프 분할보다 절단 품질은 확실히 나쁘지만 — 대신,

• 비용이 정렬 한 번($O(n\log n)$, 기수 정렬이면 사실상 선형)이라 압도적으로 빠르고,
• 격자가 국소적으로 바뀌어도 키 순서는 그대로라 재분할이 증분적이며,
• 조각 경계가 이전 스텝과 비슷하게 유지돼 데이터 이주량이 작다.

매 스텝 재분할해야 하는 적응 격자 세분화나 입자 코드에서는 이 세 가지가 절단 품질의 손해를 덮고도 남는다. p4est, Dendro, PARAMESH 같은 AMR 프레임워크가 SFC를 기본 분할기로 쓰고, Zoltan은 아예 HSFC(Hilbert SFC) 분할기를 별도 옵션으로 들고 있다. 어느 쪽이 이기는지는 결국 재분할 빈도가 정한다 — 자세한 계산은 부하 분산 참고.

AMR 격자의 선형화. 세분화된 옥트리를 포인터 트리로 들고 다니는 대신, 리프 셀의 모턴 키만 정렬된 배열로 유지한다. 이웃 탐색은 키 산술 + 이진 탐색이고, 2:1 균형 조건(이웃 레벨 차이 ≤ 1)도 키 연산으로 강제할 수 있다. 분산 환경에서 트리를 프로세스 간에 쪼개는 문제가 배열을 자르는 문제로 환원된다는 점이 핵심 이득이다.

캐시 지역성. 비구조 격자의 셀·절점 번호를 SFC 순으로 다시 매기면 희소행렬 벡터 곱의 메모리 접근이 크게 개선된다. 원래 번호가 메시 생성기가 뱉은 순서라면 이웃끼리 메모리 상 수백 MB 떨어져 있을 수 있는데, SFC 재번호화는 그것을 캐시 라인 안으로 끌어당긴다. 조밀 행렬 쪽에서는 행 우선·열 우선 대신 모턴 순 레이아웃으로 저장해 블록 크기 조정 없이 캐시 계층 전체에 재귀적으로 맞아떨어지게 하는 기법이 있다. GPU 텍스처가 내부적으로 모턴 순(스위즐링)으로 저장되는 것도 같은 이유다.

트리 구축과 N체. 고속 다중극자법이나 배럿-헛류 트리 코드는 입자를 모턴 정렬하는 것만으로 옥트리를 얻는다. GPU 실시간 레이 트레이싱의 LBVH도 삼각형 중심의 모턴 키를 정렬한 뒤 인접 키의 공통 접두사 길이로 계층을 세우는 방식이고, 이 덕에 BVH 전체를 밀리초 단위로 다시 지을 수 있다. 공간 분할 자료구조의 동적 재구축 이야기가 여기와 맞물린다.

다차원 색인. 데이터베이스에서 B-트리는 1차원 키만 다루는데, 좌표를 SFC 키로 접으면 그대로 다차원 범위 질의에 쓸 수 있다. Z-order를 쓰는 UB-트리, 문자열로 인코딩한 지오해시, 힐베르트 곡선을 쓰는 Google S2가 대표적이다. 범위 질의가 여러 개의 키 구간으로 쪼개진다는 것이 이 방식의 근본 비용이고, 그래서 클러스터 개수가 적은 힐베르트가 색인 쪽에서 특히 대접받는다.

6. 관련 문서[편집]

• 그래프 분할 · METIS · 부하 분산 · 커니핸-린 알고리즘
• 적응 격자 세분화 · 격자 · 메시 생성
• 공간 분할 자료구조 · 옥트리 · BVH · 레이 트레이싱
• 고속 다중극자법 · SPH · 분자동역학
• 희소행렬 · 병렬 컴퓨팅 · GPU 컴퓨팅 · 기수 정렬
• 프랙탈 · 외판원 문제

7. Footnotes[편집]

1. 곡선이 자기와 만난다는 사실은 그림을 그려 보면 은근히 불편하다. 레벨을 올릴수록 선이 촘촘해지다가 극한에서 정사각형 전체가 되는데, 그 극한 대상은 여전히 “구간의 연속상”이므로 선이라 불러야 한다. 위상수학이 직관에 시비를 거는 대표 사례이자, 하우스도르프 차원 2짜리 곡선이라는 프랙탈 예시로도 자주 인용된다. ↩

2. 지수가 $1/d$보다 클 수 없는 이유는 부피 논증이다. 길이 $\ell$짜리 인덱스 구간의 상은 부피 $\ell$을 차지해야 하므로 지름이 최소 $\ell^{1/d}$ 규모다. 즉 힐베르트 곡선은 이 종류의 규칙성에서 최적이고, 더 나은 곡선을 찾겠다는 시도는 상수 $C$를 깎는 싸움일 뿐이다. ↩

3. Moon, Jagadish, Faloutsos & Saltz (2001), IEEE TKDE. “힐베르트가 Z-order보다 낫다”는 통념에 실제 상수를 붙여 준 논문이다. 물론 실무에서 곡선을 바꾸는 결정은 이 상수보다 “인코딩 함수를 다시 짜야 하나”에 훨씬 크게 좌우된다. ↩