정확 술어

1. 개요[편집]

정확 술어 Exact Geometric Predicates
대표 술어	orient2d / orient3d · incircle / insphere
요구 사항	값이 아니라 부호만 정확하면 된다
실패 증상	비볼록 껍질 · 위상 모순 · 무한 루프 · 크래시
표준 해법	적응 정밀도 필터(Shewchuk 1997) · 구간 필터 · 정수/유리 산술
퇴화 처리	무한소 섭동(Simulation of Simplicity, 1990)
패러다임	EGC — 좌표는 근사, 분기는 정확

정확 술어는 기하 알고리즘의 분기 판정에 쓰이는 부호 함수를 반올림 오차와 무관하게 항상 옳은 부호로 계산하도록 구현한 것이다. 계산기하학의 알고리즘은 좌표를 계산해서 쓰는 게 아니라 좌표에 대한 몇 가지 질문 — “이 세 점은 좌회전인가 우회전인가”, “이 점은 저 세 점이 이루는 원 안인가 밖인가” — 의 참/거짓 답만으로 자료구조를 조립한다. 그래서 필요한 정밀도는 오직 부호 하나이며, 반대로 그 부호가 하나라도 틀리면 결과가 “조금 부정확한” 것이 아니라 자료구조가 논리적으로 모순이 된다.

이 차이가 정확 술어를 수치해석의 다른 분야와 갈라놓는다. 선형계에서는 잔차 $10^{-12}$ 면 훌륭한 해다. 하지만 볼록 껍질 코드에서는 $10^{-30}$ 짜리 행렬식의 부호가 뒤집히는 순간, 스택이 비어 있는데 pop 을 하거나, 껍질이 자기 자신과 교차하거나, 플립 루프가 영원히 끝나지 않는다. 오차가 작다는 것과 판정이 옳다는 것은 다른 명제다.

2. 두 개의 술어[편집]

계산기하 코드의 절대다수는 두 술어 위에 서 있다. 방향 판정:

$$\mathrm{orient2d}(a,b,c) = \operatorname{sign} \begin{vmatrix} b_x - a_x & b_y - a_y \\ c_x - a_x & c_y - a_y \end{vmatrix}$$

부호가 양이면 $a \to b \to c$ 가 좌회전(반시계), 음이면 우회전, 0이면 공선이다. 3차원 버전 $\mathrm{orient3d}$ 는 $3\times3$ 행렬식으로 “점이 평면의 위인가 아래인가”를 답한다.

내접원 판정:

$$\mathrm{incircle}(a,b,c,d) = \operatorname{sign} \begin{vmatrix} a_x - d_x & a_y - d_y & (a_x-d_x)^2 + (a_y-d_y)^2 \\ b_x - d_x & b_y - d_y & (b_x-d_x)^2 + (b_y-d_y)^2 \\ c_x - d_x & c_y - d_y & (c_x-d_x)^2 + (c_y-d_y)^2 \end{vmatrix}$$

반시계 순인 $a,b,c$ 의 외접원 안에 $d$ 가 있으면 양수다. 이 하나가 들로네 삼각분할 전체를 굴린다. 3차원 대응물 $\mathrm{insphere}$ 는 $4\times4$ 행렬식이고, 리프팅 관점에서는 인서클이 곧 한 차원 높은 방향 판정이라는 사실이 볼록 껍질 문서에 정리되어 있다.

필요한 정밀도는 계산해 볼 수 있다. 좌표가 $b$ 비트 정수라면 차 항은 $b+1$ 비트, 2×2 행렬식은 $2b+3$ 비트가 필요하다. double 의 가수가 53비트이므로 좌표가 대략 $2^{25}$ 미만의 정수면 $\mathrm{orient2d}$ 는 부동소수점으로도 정확하다. 반면 인서클은 세 항의 곱이 들어가 $4b+8$ 비트쯤을 요구하므로, 정확성이 보장되는 좌표 범위가 $2^{11}$ 남짓으로 확 줄어든다. 즉 “정수 좌표만 쓰면 안전하다”는 통념은 술어마다 유효 범위가 다르다는 점에서 절반만 맞다.

3. 어떻게 깨지는가[편집]

부호 오류의 결과는 놀랄 만큼 극적이다. 케트너·멜호른·피옹·시라·얍(2008)은 평범해 보이는 입력으로 표준 껍질 알고리즘들이 어떻게 무너지는지를 그림과 함께 정리했다.¹ 전형적인 증상은 셋이다.

• 비볼록 껍질. 거의 공선인 점들에서 방향 판정이 뒤집히면 증분 껍질 알고리즘이 안쪽으로 꺾인 정점을 남긴다. 출력은 “볼록 껍질”이라는 이름을 달고 있지만 실제로는 오목하다. 이걸 그대로 GJK 알고리즘에 넣으면 지지 함수가 거짓말을 하고, 심플렉스가 원점을 감싸지 못해 충돌 판정이 깜빡인다.
• 점이 밖으로 새는 껍질. 입력 점 중 일부가 결과 다각형 바깥에 남는다. 껍질의 정의 자체가 위배되므로 이후 단계의 모든 가정이 무너진다.
• 무한 루프와 크래시. 그레이엄 스캔은 “우회전이면 pop” 을 반복하는데, 판정이 비일관적이면 이미 빈 스택에서 pop 을 시도한다. 로슨 플립 기반 들로네는 삼각형 A와 B가 서로를 “내 원 안에 있다”고 판정하면 두 삼각형을 영원히 주고받는다. 비종료는 부동소수점 오차의 정상적 귀결이다.

여기서 초보자가 반드시 한 번은 시도하는 잘못된 처방이 톨러런스다. $|\det| < \varepsilon$ 이면 0으로 취급하자는 것인데, 이러면 “거의 같다”가 추이적이지 않아진다. $a \sim b$, $b \sim c$ 인데 $a \not\sim c$ 인 배치를 만들기는 쉽고, 그 순간 알고리즘이 가정하는 전순서가 깨져 같은 종류의 재앙이 다시 발생한다. 게다가 $\varepsilon$ 값은 좌표 스케일에 의존하므로, 미터 단위로 잘 돌던 코드가 밀리미터 단위 데이터에서 죽는다.

4. 적응 정밀도 필터[편집]

정답은 부호를 확실히 알 때까지만 정밀도를 올리는 것이다. 셔척(J. R. Shewchuk, 1997)의 구현이 사실상의 표준이 됐다.²

핵심 도구는 오차 없는 변환이다. IEEE 754 반올림 아래에서 두 부동소수점 수의 합과 곱은 각각 두 개의 부동소수점 수로 정확히 쪼갤 수 있다.

$$a + b = s + e, \qquad s = \mathrm{fl}(a+b), \quad e = (a+b) - s$$

여기서 $e$ 도 부동소수점 수로 정확히 표현된다는 것이 Two-Sum(커누스)·Fast-Two-Sum(데커)의 내용이고, 곱셈에도 Two-Product 대응물이 있다(FMA 명령이 있으면 한 줄이다). 이렇게 얻은 “겹치지 않는 부동소수점 수들의 열”을 확장(expansion)이라 부르고, 그 합이 값을 정확히 표현한다. 즉 다중정밀도 라이브러리 없이 double 배열만으로 임의 정밀 산술이 된다.

그 위에 적응이 얹힌다.

1. 1단계 — 순진한 계산 + 정적 오차 상계. 그냥 double 로 행렬식을 계산하고, 동시에 항들의 크기로부터 오차 상계 $\Delta$ 를 값싸게 추정한다. $|A| > \Delta$ 면 부호가 확정이므로 즉시 반환한다.
2. 2단계 이후 — 정밀도를 단계적으로 올린다. 애매하면 앞 단계의 중간 결과를 버리지 않고 재활용해 보정항을 더한 더 정확한 근사를 만들고, 다시 오차 상계와 비교한다.
3. 마지막 단계 — 완전 정확 계산. 확장 산술로 행렬식을 끝까지 전개한다.

실측에서 무작위 입력의 99% 이상이 1단계에서 끝난다. 그래서 평균 비용은 순진한 구현의 몇 십 퍼센트 오버헤드 수준이고, 최악의 경우에만 수십 배를 낸다. 거의 공짜로 항상 옳은 부호를 얻는다는 것이 이 설계의 요점이다.

변주도 흔하다. 좌표 범위를 미리 알면 오차 상계를 컴파일 타임에 상수로 굳히는 정적 필터가 가장 싸고, 범위를 모르면 구간 산술로 상하한을 함께 굴리는 동적 필터를 쓴다. 구간이 0을 포함할 때만 정확 산술로 내려간다. CGAL의 Filtered_kernel 이 이 조합을 커널 템플릿 인자로 노출한 것이고, 들로네 삼각분할 도구 Triangle 과 사면체 격자기 TetGen 은 셔척의 술어를 그대로 링크해 쓴다.

5. 술어는 싸고 구성은 비싸다[편집]

정확 술어만으로 모든 문제가 해결되지는 않는다. 판정(predicate)은 입력 좌표에서 부호 하나를 뽑는 일이라 비트 폭이 유한하지만, 구성(construction) — 두 선분의 교점 좌표를 실제로 만들어 다음 단계 입력으로 넘기는 일 — 은 사정이 다르다.

$b$ 비트 유리수 좌표로 표현된 두 선분의 교점은 분자·분모가 $2b$ 비트급인 유리수가 된다. 그 교점들로 다시 선분을 만들어 또 교차시키면 비트 폭이 곱절로 불어난다. 불리언 연산을 몇 단계 겹치는 CAD·GIS 파이프라인에서 이 누적이 곧바로 성능 붕괴로 이어진다. 그래서 실무 대책은 두 갈래다.

• 스냅 라운딩. 구성된 좌표를 격자에 강제로 스냅해 비트 폭을 되돌린다. 대신 스냅이 위상을 바꿀 수 있어(선분이 반대편으로 넘어가거나 다각형이 뒤집힌다) 위상 보존형 스냅 라운딩이 따로 연구된다.
• 지연 평가. 좌표를 “이렇게 만들어진 값”이라는 식 트리로 들고 있다가, 부호가 필요할 때만 필요한 만큼 전개한다. Core Library 계열의 대수적 수(algebraic number) 커널이 이 방식이다.

얍(C. Yap) 등이 정리한 EGC(Exact Geometric Computation) 패러다임의 한 줄 요약이 여기서 나온다 — 좌표는 근사해도 좋지만, 알고리즘의 모든 분기는 정확해야 한다. 화면에 그려지는 점의 위치가 $10^{-9}$ 틀린 것은 아무도 모르지만, 그 점이 다각형 안인지 밖인지가 틀리면 프로그램이 죽는다.

6. 무한소 섭동 — 퇴화를 없애는 쪽[편집]

정확 술어는 “부호가 0인 경우”를 정확히 알아낼 뿐, 그 경우 무엇을 할지는 알려주지 않는다. 공선인 세 점, 한 원 위의 네 점, 같은 $x$ 좌표를 가진 두 점 같은 퇴화는 여전히 남는다. 이걸 분기로 다 처리하면 코드가 세 배가 된다.

무한소 섭동(Simulation of Simplicity, 에델스브루너-뮈케 1990)은 반대 방향으로 간다. 각 입력 좌표에 서로 비교 불가능할 만큼 크기 차이가 나는 상징적 무한소를 더한다.

$$x_{i,j} \ \longmapsto\ x_{i,j} + \varepsilon^{\,2^{i}\!/\,\delta^{\,j}} \qquad (\varepsilon \to 0^{+})$$

지수를 이렇게 설계하면 어떤 부분집합도 우연히 상쇄되지 않아, 섭동된 입력은 확률 1이 아니라 확정적으로 일반 위치가 된다. 술어의 행렬식은 $\varepsilon$ 에 대한 다항식이 되고, 그 부호는 0이 아닌 최저차 계수의 부호로 정해진다. 실제 구현은 $\varepsilon$ 을 다루지 않고 미리 계산된 계수 순서를 따라 몇 개의 부분 행렬식을 순서대로 검사하는 짧은 표로 끝난다.

대가도 분명하다. 섭동은 답의 의미를 바꾼다. 껍질 모서리 위에 정확히 놓인 점은 일관되게 안쪽 또는 바깥쪽 하나로 결정되고, 정확히 한 원 위의 네 점으로 이루어진 정사각형은 두 삼각형으로 갈리되 어느 대각선일지는 섭동 규칙이 정한다. “수학적으로 무모순인 답”과 “사용자가 기대한 답”이 다를 수 있으므로, 퇴화 자체가 의미를 갖는 응용(CAD 의 접선 조건, 정확히 맞물리는 폴리곤 경계)에서는 섭동 대신 퇴화를 명시적으로 다루는 쪽이 옳다.

7. 실무 선택지 정리[편집]

전략	비용	언제
순진한 double	1배	절대 안 됨. 시연용 코드에만
톨러런스 비교	1배	추이성이 깨져 더 나쁨. 금지
정적 필터 + 확장 산술	평균 1.2~2배	사실상 기본값(Shewchuk)
구간 필터 + 유리수 폴백	평균 2~5배	좌표 범위를 모를 때(CGAL)
정수 산술 전면 사용	1~3배	좌표를 격자에 스냅할 수 있을 때
임의 정밀도 유리수 전면 사용	10~100배	구성이 깊게 중첩되는 CAD 커널

정수 산술이 가능하다면 그게 가장 마음 편하다. 게임의 격자 스냅 좌표, 반도체 마스크 레이아웃, 정수 픽셀 좌표에서 도는 수학적 형태학 계열 처리가 그런 경우다. 문제는 대부분의 실측·설계 데이터가 처음부터 부동소수점이고, 정수로 옮기는 순간 스냅 오차가 다시 위상을 흔든다는 것이다.³

8. 관련 문서[편집]

• 계산기하학 · 볼록 껍질 · 들로네 삼각분할 · 보로노이 다이어그램
• 부동소수점 연산 · 조건수 · 구간 산술
• 볼록 분해 · 민코프스키 합 · GJK 알고리즘
• 메시 생성 · 충돌 감지 · CGAL

9. Footnotes[편집]

1. Kettner, Mehlhorn, Pion, Schirra, Yap (2008), Classroom Examples of Robustness Problems in Geometric Computations. 논문의 진짜 무서운 점은 반례가 특별히 악의적이지 않다는 것이다. 좌표 몇 개를 평범하게 고른 열 몇 개짜리 입력에서 교과서 알고리즘이 그냥 틀린 답을 뱉는다. 계산기하 입문자에게 예방접종으로 권해지는 이유. ↩

2. Shewchuk (1997), Adaptive Precision Floating-Point Arithmetic and Fast Robust Geometric Predicates, Discrete & Computational Geometry 18. 저자가 학위 과정 부산물로 내놓은 C 코드 predicates.c 는 지금도 전 세계 메시 생성기·삼각분할 코드에 거의 원문 그대로 복사되어 있다. 파일 하나가 30년째 한 분야의 하부구조로 굴러가는, 대학원생의 로망 같은 사례. ↩

3. “부호만 맞으면 된다”는 말이 주는 안도감은 오래가지 않는다. 술어는 확실히 부호만 필요하지만, 그 술어들의 답이 서로 모순되지 않아야 알고리즘이 돈다. 실제로 정확 술어를 넣고도 죽는 코드의 상당수는 술어가 아니라 그 위에서 구성된 좌표가 부정확한 경우다. 정확함은 전염되지 않는다 — 한 군데만 근사해도 파이프라인 전체가 근사가 된다. ↩