토폴로지의 덮개 공간과 보편 덮개를 시각적으로 설명하고, Super Mario 64의 ‘평행 우주’ 글리치 및 이중 도넛의 보편 덮개에서 나타나는 쌍곡 기하와의 연결을 다룬다.
덮개 공간은 토폴로지에서의 기본 개념이다. 전형적인 예시 몇 가지는 이전 글에서 볼 수 있다.
정의 1 위상공간 의 덮개 공간(covering space) 이란, 위상공간 와 연속인 전사 사상 의 쌍으로서 다음을 만족하는 것이다: 모든 점 에 대해, 의 어떤 열린 근방 가 존재하여 가 어떤 이산 집합 ( 를 위의 fiber라고 부른다)에 대해 와 위상동형이고, 를 의 각 연결 성분에 제한하면 로의 위상동형이 된다.
Note
정의 2 위상공간 과 사이의 위상동형(homeomorphism) 이란 전단사 사상 로서 와 그 역함수 가 모두 연속인 것을 말한다. 명시적으로는:
이러한 가 존재하면 와 는 위상동형 이라고 하며, 로 쓴다.
위상동형은 정확히 위상공간과 연속사상의 범주에서의 동형사상(isomorphism) 이다.
도넛과 커피잔 사이의 위상동형 예시
덮개 공간을 설명하는 전형적인 예시
정의 3 위상공간 의 보편 덮개(universal cover) 란, 의 덮개 공간 중에서 단일연결(simply connected)인 것, 즉 자명하지 않은 루프가 없는 것을 말한다. 보편 덮개는 위상동형을 제외하면 유일하며, 의 덮개 공간들의 범주에서 “보편적” 대상 역할을 한다.
채워진 토러스(도넛)는 3-다양체로서 와 위상동형이다. 여기서 는 2차원 원판이다. 도넛에서 원으로의 변형 수축(deformation retract)이 존재하므로, 도넛의 기본군은 이다.
그런데 이런 말들이 대체 무슨 뜻일까? 도넛의 보편 덮개를 시각화해 보자. 다음과 같은 작은 세계에 사는 Bob부터 시작하자:
Bob의 세계
Bob이 정지 표지판을 지나 도로를 따라 운전하면, 결국 출발했던 같은 지점으로 돌아오게 된다. 하지만 잔디 위로 걸어가거나 하늘로 점프하려고 하면 보이지 않는 벽에 부딪힌다. 이동할 수 있는 방법은 도로뿐이고, 도로는 자기 자신으로 다시 이어진다.
위상적으로 Bob의 세계는 도넛이며, 도로는 도넛의 구멍을 한 바퀴 도는 루프다. 이를 늘려서(걱정 마라, Bob에게 해가 되지 않는다. Bob은 아예 눈치채지도 못한다!) 펼치면 다음과 같은 그림이 된다:
늘어난 Bob의 세계
이런 종류의 세계는 비디오 게임에서 자주 나타나며, 특히 이 글에서 설명할 아이디어들은 Super Mario 64 커뮤니티에서 게임을 “해킹”하여 다양한 스피드런 목표를 달성하는 데 사용된 것으로 유명하다:
(여기서 유명한 “하지만 먼저, 우리는 평행 우주에 대해 이야기해야 합니다”라는 문구가 나온다. SM64 커뮤니티에서 덮개 공간은 “평행 우주”로 알려져 있다.) 의도적이든(예: Pacman) 의도치 않든(예: Super Mario 64에서 floating point 수를 short int로 캐스팅하는 과정 때문에), 충분히 오래 직선으로 걸으면 결국 같은 지점으로 돌아오게 되는 경우가 흔하다.
하지만 SM64의 경우 이 부동소수점 산술의 영향은 충돌 판정 코드에만 있고 렌더링 엔진에는 없다. 따라서 SM64의 “평행 우주”들 사이에는 실제로 차이가 있다. 특히 Mario가 다른 평행 우주로 이동하면, 동일한 충돌들이 계속 감지되지만, 렌더링에서는 텅 빈 공간에 떠 있는 것처럼 보이게 된다. 이것을 Bob의 세계에도 반영할 수 있다:
Bob의 세계를 두 배, 세 배, 네 배, …로 복제해 서로 위로 쌓는다고 가정하자. 각 복제가 “얕은(shallow)” 복제, 즉 기본 영역(fundamental domain) (원래 세계)에서의 각 움직임이 복제본들에 그대로 거울처럼 반영되는 방식이라면, Bob은 전혀 눈치채지 못할 것이다. 이 경우 우리는 Bob의 세계의 덮개 공간을 얻게 되며, 원래 세계가 바탕 공간(base space)이 된다.
Bob의 세계를 1번 쌓은 모습
Bob의 세계를 2번 쌓은 모습
Bob의 세계를 3번 쌓은 모습
이제 SM64에서도 똑같이 한다고 상상해 볼 수 있다. 다만 그 경우에는 지형은 복제본들에 대해 렌더링하지 않고, Mario 자신만 렌더링하게 될 것이다.
이 복제들을 계속 쌓아 올리면 다음과 같은 그림을 얻게 된다:
Bob의 세계를 4번 쌓은 모습
Bob의 세계를 5번 쌓은 모습
Bob의 세계를 5번 쌓은 모습
Bob의 세계를 5번 쌓은 모습
Bob의 세계를 번 쌓은 모습
무한히 쌓인 세계 는 단일연결이고 Bob의 세계 를 덮으므로(위의 보편 덮개의 정의 참고), Bob의 세계의 보편 덮개 이다.
Caution
나는 가끔 지면 텍스처를 바꾸었고 모든 이미지를 다시 렌더링하기가 귀찮아서, 이미지들 사이의 이 불일치를 양해해 달라.
Super Mario 64의 맵[^1]에 대한 보편 덮개는 사실 Bismuth가 영상 “Super Mario 64 Tool-assisted speedrun world record explained”에서 설명하는 내용이다. SM64의 세계들, 더 정확히 말하면 Super Mario 64의 맵들은 모두 와 위상동형이다(즉 거의 동일하다는 뜻이며, 위상동형의 정의 참고). 는 3차원 토러스로, 세 개의 원의 곱이다. 영상의 이 짧은 클립을 보자:
Warning
Super Mario 64의 맵은 위치를 여전히 IEEE‑754 32bit floating point 수로만 저장하므로, 이것은 충돌 판정 공간(이는 short int를 사용함)의 보편 덮개가 아니라 단지 어떤 덮개 공간일 뿐이다. 아래에서 더 설명하겠다.
Your browser does not support the video tag. (Video by Bismuth) Super Mario 64의 세계는 대략 3차원 토러스 이다. Mario의 위치는 float로 저장되지만, 충돌 판정을 위해 short로 캐스팅되므로, 충돌 판정에서는 와 사이의 값들만 서로 다른 위치로 실제로 감지된다. 따라서 Mario의 위치 감지는 에서 계산되고, 그의 실제 위치는 에서 계산된다. 여기서는 Nintendo 64의 IEEE‑754 부동소수점 산술 때문에 여전히 mod를 취해야 한다.
float에서 short로의 캐스팅은 수축 과 그 단면(section) 를 낳는데, 는 를 로 올려(lift) 주며, 이는 SM64 스피드런에서 이용된다. 특히 는 의 덮개 공간이며 fiber가 인데, 이는 Mario가 한 “평행 우주”에서 다음으로 전이하는 모든 점들의 집합이다.
SM64에서는 이 덮개 공간 구조를 이용하여 다른 글리치인 “backwards longjump”를 통해 Mario에게 매우 큰 속도 ( 에서 Mario 위치에서의 접벡터)를 부여한다. 그 다음 지수 사상(exponential map)을 사용해 에 대해 지오데식 를 따라 Mario를 이동시킨다. 하지만 하드웨어 한계 때문에, 충돌 판정에서는 이 지오데식의 연속이 아니라 어떤 에 대해 이산적인 단계 만 실제로 계산된다. 이것이 Lie 군의 지수 사상과 어떻게 관련되는지에 대해서는 내 이전 글에서 더 볼 수 있다. 이 글 전체에서 SM64의 Lie 군은 위치 에서 단위원을 갖는다고 가정하겠다.
Mario의 위치 와 속도 를 신중히 선택함으로써, SM64 커뮤니티는 충돌 판정 기준에서 원하는 위치들 (어떤 문에 도달하기, 별을 수집하기 등)에 도달할 수 있었다. 이를 위해 SM64가 실제 계산에서 어떤 를 사용하는지 확인한 다음, 어떤 에 대해 가 되도록 선택하고, 다른 모든 에 대해서는 가 ( 같은 리셋을 유발하는) 부정적 결과의 충돌 판정을 일으키지 않는 위치가 되도록 했다.
Bismuth의 영상에 나온, 올바른 를 고르는 개략도
이전 예시에서는 자기 자신으로 되돌아오는 길이 하나뿐인 공간을 고려했다. 도로를 몇 번 돌아야 “같은” 점(또는 다른 복제본에서의 동치인 점)으로 돌아오는지를 이 “감김수(winding number)” 트릭으로 부호화할 수 있다:
Bob이 목줄을 한 개에게 “Snoopy”라는 이름의 개를 데리고 있고, Bob은 가만히 서 있는 동안 개가 도로를 따라 걷는다고 하자. 개가 도로를 한 번 따라가서 Bob에게 돌아오면, 목줄이 그의 공간의 구멍 주위를 감게 된다. 즉, 이를 풀기 위해 Bob은 구멍 주위를 한 번 걸어야 한다.
사실 목줄이 구멍을 몇 번 감는지 세면, Snoopy가 Bob의 세계의 어느 복제본에 있는지도 부호화할 수 있다.
Snoopy가 할 수 있는 이 “구멍 주위로 목줄을 감기” 동작은 바탕 공간(Bob의 공간) 위에서의 의 군 작용이다: 각 정수 에 대해 Snoopy는 목줄을 구멍에 번 감을 수 있고, 는 Snoopy가 구멍을 시계 방향으로 번 돈 뒤 반시계 방향으로 번 도는 것에 해당한다.
Note
정의 4 (정의: 기본군) 를 위상공간, 를 기준점이라고 하자. 에 기반한 루프(loop) 란 연속사상 로서 를 만족하는 것이다. 두 루프 가 에 대한 상대적 호모토피(homotopic relative to ) ( 로 씀)라고 하는 것은, 연속사상 가 존재하여 모든 에 대해 를 만족하는 것을 말한다. 이는 동치관계이며, 의 동치류를 로 표기한다.
기준점 에서의 의 기본군(fundamental group) 은 에 이어 붙이기(concatenation) 의 군 연산을 준 것이다: 항등원은 상수 루프 의 동치류이고, 의 역원은 이며 여기서 이다.
가 경로 연결(path-connected)이라면, 의 동형류는 기준점 의 선택에 무관하므로, 간단히 라고 쓴다.
Bob의 세계에서 보이지 않는 벽을 실제 벽(예를 들어 가로등)으로 생각하면 다음과 같은 그림이 된다:
Snoopy가 구멍/가로등 주위에 번 얽힌 모습
Snoopy가 구멍/가로등 주위에 번 얽힌 모습
Snoopy가 구멍/가로등 주위에 번 얽힌 모습
Snoopy가 구멍/가로등 주위에 번 얽힌 모습
즉, Bob의 공간에서 선 하나를 제거하면 보편 덮개에서 무한() 개의 복제본이 생긴다. 그렇다면 선을 두 개 제거하면 어떻게 될까?
선 두 개를 제거한 세계. 이제 목줄이 얽힐 수 있는 방법이 두 가지(빨강과 파랑)이며, “그 모든 조합”이 있다(이 공간의 기본군 생성자가 두 개 있다는 뜻)
토러스와, 도로를 따라 벽을 통과하면 Bob이 반대편으로 “텔레포트”되던 세계에서 했던 것처럼, 이 세계도 다시 “펼쳐” 보자. 이 황량한 세계에 작은 집과 물을 두어 Bob이 살기 좋은 곳을 만들어 보겠다:
Your browser does not support the video tag. 선 두 개를 제거한 공간(Bob의 집)을 이중 도넛으로 펼치기.
Your browser does not support the video tag. 위 펼침의 또 다른 시점(물은 변환을 깜빡한 것 같다).
Warning
이것은 Super Mario 64가 일어나는 공간이 아니다! SM64는 공간 (3차원 토러스)이다. 이 공간은 상자 안에, 왼쪽에서 오른쪽으로, 위에서 아래로, 바닥에서 천장으로 통하는 포털을 만들어 얻을 수 있는데, 이는 앞서의 Bob의 로드트립 세계였다!
이 이중 도넛 세계에서는 기본군이 두 생성자를 갖는 자유군이 된다:
그리고 이 공간의 보편 덮개를 만들면 다음과 같은 쌍곡 공간을 얻는다(바탕 공간/“평행 우주”의 복제본들을 축소해 두었음을 주의). 쌍곡 공간은 유클리드 평면에 들어맞지 않기 때문이다:
이중 도넛의 보편 덮개는 쌍곡 공간이다
이중 도넛의 보편 덮개는 쌍곡 공간인데, 여기서는 xy 평면만 줄이고 높이는 줄이지 않았다
Definition: Hyperbolic Space
-차원 쌍곡 공간(hyperbolic space) 은 (등거리변환까지) 유일한 단일연결이고 완비인 리만 다양체로서, 단면 곡률(sectional curvature)이 상수 인 것이다.
이를 구체화하는 표준 모형이 두 가지 있다:
Poincaré half-space model. 열린 위쪽 반공간 에, 좌표 접벡터들에 대한 성분이 인 리만 계량을 준다. 지오데식은 경계 초평면 에 수직인 반원(또는 반직선)이다.
Poincaré disk model. 열린 단위 공 에 계량 를 준다. 이 모형은 등각(conformal) 이다: 곡선 사이의 각이 유클리드에서의 각과 같다.
각 점 에는, 주어진 국소좌표(즉 기저 )에서 에서의 접벡터 (편미분으로 쓴다)가 있다. 모음 는 의 기저를 이룬다.
매끄러운 다양체 위의 리만 계량(Riemannian metric) 은, 에 따라 매끄럽게 변하는 내적들의 족 으로서 각 가 대칭이고 양의 정부호가 되게 하는 것이다. 국소좌표에서 계량은 기저 접벡터들에 대한 값들로 완전히 결정된다: 이며, 행렬 는 모든 점에서 양의 정부호이다. 그러면 접벡터 의 길이는 이다.
2차원 Poincaré half-space 모형에서 계량을 좌표 접벡터 에 대해 평가하면 가 된다. 즉 좌표 접벡터들은 서로 직교하고 각각의 길이는 이며, 가 경계 에 가까워질수록 0으로 줄어든다. 이것이 경계 근처에서 공간이 “무한히 커지는” 이유다.
사람들은 흔히 이 계량들을 꼴로 쓰는데, 여기서 각 는 코벡터(covector) (1-형식), 즉 쌍대공간 의 원소이다. 유한차원 벡터공간에서는 그 공간과 쌍대 사이에 표준적인 동형이 있다: 의 좌표 기저 가 주어지면, 의 유일한 쌍대 기저(dual basis) 가 로 정의된다. 이는 동형들 로 확장된다. 이 동일시 아래에서, 위의 쌍선형형식 는 대칭 텐서 로 표현되며, 이는 접벡터 쌍에 대해 로 작용하여 앞에서의 내적 을 정확히 복원한다. 따라서 두 서술은 동일한 정보를 담는다;
이 때문에 2차원 Poincaré half-space 모형에 대해 다음과 같이도 쓸 수 있다:
유클리드 기하와의 핵심 차이는 반지름 인 원의 둘레가 이고, 부피가 다항식적이 아니라 지수적으로 증가한다는 점이다:
Reddit에서 Bartfeels24가 이 질문을 했다(아래 참고). 아직도 왜? 인지 궁금하다면, 다음은 내 답변이다:
SM64에서는 위치가 세 개의 float로 이루어진 튜플로 저장된다. 하지만 Nintendo의 어떤 프로그래머는 충돌 판정에서는 short int로 캐스팅해도 괜찮을 거라고 생각했다(솔직히 완전히 타당한 생각이다. 애초에 Mario가 맵 밖으로 나가도록 의도된 적은 없으니까).
하지만 float를 short int로 캐스팅하면 암묵적으로 mod 연산이 계산된다(사실 튜플의 각 float에 대해 mod 65536이다).
이 작은 실수는 악용될 수 있다. 예를 들어 Mario가 레벨을 끝내기 위해 별을 먹고 싶다고 하자. 별에 어느 정도 가까이 위치해야 하지만, 충돌 판정에서는 mod 65536을 취한 뒤의 위치만 사용된다. 또 다른 익스플로잇을 사용하면 Mario에게 엄청난 속도를 얻게 해 물리 엔진이 벽을 뚫고 지나가게 할 수 있다. 그러나 큰 속도에는 맵을 벗어나는(Out of bounds) 대가가 따른다. 그래서 mod 연산을 이용해, 별과의 충돌 판정을 여전히 강제로 발생시키는 것이다.
이 기법은 더 깊은 뿌리를 갖는다. 잘못된 자료형을 선택하거나, 주의 없이 캐스팅하면 공격에 취약해진다. 어떤 데이터 구조를 다른 구조로 캐스팅하면서 정보를 “제거”한다면, 이런 공격이 일어날 수 있다:
예를 들어, 어떤 은행이 내부적으로는 돈을 임의의 부동소수점 수로 처리하지만, 이체 시에는 소수점 둘째 자리(센트)까지 반올림한 값만 청구한다고 하자. 당신이 다른 계좌로 0.009€를 이체하면, 그 계좌는 0.009€를 받지만 당신 계좌에는 0.00€가 청구된다. 현실 세계에서의 무한 돈 글리치.
하지만 이런 일은 더 일반적으로도 벌어진다. 어떤 처리를 위해 더 작은 자료형으로 “캐스팅”(수축)한 뒤에 연산을 수행할 때마다, 이런 문제가 발생할 수 있다.
