지도 앱의 지형, 게임 캐릭터가 걸어 다니는 내비메시, 3D 스캔으로 만든 모델. 이 모든 것의 밑바닥에는 삼각형이 깔려 있어요. 흩어진 점들을 삼각형으로 잘 이어주는 문제를 '들로네 삼각분할'이라고 하는데요. 최근 이 문제를 32비트 정수 좌표에 한정해서 수학적으로 완전히 정확하게, 게다가 병렬로 푸는 오픈소스 라이브러리 delaunay32가 공개됐어요. 좌표를 정수로 제한한다는 선택 하나가 왜 이렇게 큰 차이를 만드는지, 그 이야기를 해볼게요.
들로네 삼각분할이 뭐냐면요
평면에 점이 잔뜩 찍혀 있을 때, 이 점들을 꼭짓점으로 삼각형들을 만들어서 전체 영역을 빈틈없이 덮는 걸 삼각분할이라고 해요. 그런데 잇는 방법이 수없이 많잖아요. 들로네 조건은 그중에서 "어떤 삼각형의 외접원(세 꼭짓점을 지나는 원) 안에도 다른 점이 들어오지 않게" 잇는 거예요. 이렇게 하면 가늘고 길쭉한 못생긴 삼각형이 최소화되고 균형 잡힌 메시가 나오거든요. 지형 렌더링, 구조 해석 시뮬레이션, 데이터 보간, 그리고 보로노이 다이어그램(들로네와 동전의 양면 관계예요) 계산까지, 계산기하학의 만능 재료죠.
'정확하다'는 게 왜 어려운 문제냐면요
알고리즘 자체는 교과서에 잘 나와 있어요. 진짜 문제는 부동소수점이에요. 들로네 알고리즘은 "이 점이 저 원 안에 있나?" 같은 기하 판정을 수없이 반복하는데, 이 판정의 실체는 행렬식 계산이거든요. float나 double로 계산하면 아주 미세한 반올림 오차가 생기는데, 점이 원 경계에 거의 걸쳐 있는 경우 '안'을 '밖'으로 잘못 판정할 수 있어요. 그러면 알고리즘이 서로 모순된 결정을 내리게 되고, 결과는 무한 루프, 뒤집힌 삼각형, 크래시로 이어져요. 실무에서 "특정 입력에서만 가끔 터지는" 지오메트리 버그의 상당수가 바로 이거예요. 이걸 견고성(robustness) 문제라고 하는데, 계산기하학의 수십 년 묵은 골칫거리거든요. 평소엔 부동소수점으로 빠르게 계산하다가 애매한 경우에만 고정밀 연산으로 넘어가는 Shewchuk의 robust predicates 같은 정교한 기법이 그래서 나온 거예요.
좌표를 int32로 제한하는 묘수
delaunay32의 접근은 발상이 깔끔해요. 좌표를 32비트 정수로 제한하면, 판정에 필요한 행렬식 값이 아무리 커져도 필요한 비트 수가 미리 정해지거든요. 그러면 64비트나 128비트 정수 연산만으로 반올림 없이 항상 정확한 답을 얻을 수 있어요. 근사도, 예외 처리용 폴백도, 오차 허용치(입실론) 튜닝도 필요 없이 모든 판정이 수학적으로 옳은 거죠. 그리고 판정이 결정론적이니까 병렬화에도 유리해요. 부동소수점 병렬 코드는 계산 순서에 따라 결과가 미묘하게 달라질 수 있는데, 정수 연산은 언제 어디서 계산해도 같은 답이 나오니까 멀티코어로 안심하고 일을 쪼갤 수 있거든요.
기존 도구들과 비교하면요
이 분야의 터줏대감은 CGAL이에요. 정확성은 확실하지만 무겁고 라이선스도 신경 써야 하죠. Shewchuk의 Triangle은 가볍고 빠른 고전이고, 자바스크립트 진영에는 delaunator처럼 속도에 올인한 구현도 있어요. delaunay32는 "정확성과 병렬 성능을 둘 다 잡되, 좌표는 정수로 제한한다"는 트레이드오프를 택한 건데요. 사실 게임의 타일 좌표나 지도 서비스의 그리드 좌표처럼 실무 데이터는 애초에 정수이거나 정수로 바꿔도 무방한 경우가 많아서, 이 제약이 생각만큼 크지 않아요.
배워갈 점
당장 내비메시 생성이나 GIS 데이터 처리를 하는 분들에게는 실용적인 선택지가 하나 늘어난 거고요. 그보다 더 큰 교훈은 설계 철학이에요. "실수(float)를 피하면 문제가 쉬워진다"는 것. 돈 계산에 소수점 대신 정수(원 단위)를 쓰는 것처럼, 기하 문제도 입력을 정수 그리드로 스냅하는 순간 수십 년 묵은 견고성 문제가 통째로 사라져요. 문제의 조건을 살짝 좁혀서 어려움 자체를 제거하는 것, 좋은 엔지니어링의 정석이죠.
여러분은 부동소수점 오차 때문에 고생해본 경험 있으신가요? 그때 어떻게 해결하셨는지 궁금하네요.
🔗 출처: Hacker News