지도 앱이 건물 하나를 그릴 때 생기는 일
카카오맵이나 구글 지도를 확대하면 건물, 공원, 호수 같은 면(polygon)이 한꺼번에 그려지잖아요. 그런데 사실 GPU는 '다각형'을 그릴 줄 몰라요. GPU가 아는 도형은 기본적으로 삼각형밖에 없거든요. 그래서 지도 엔진은 화면에 그리기 전에 모든 폴리곤을 삼각형 여러 개로 쪼개야 하는데, 이 작업을 삼각분할(triangulation)이라고 불러요.
지도 렌더링 소프트웨어를 만드는 Globus 쪽 블로그에 흥미로운 글이 올라왔어요. 지도 폴리곤 370만 개를 489ms 만에 삼각분할했고, 업계 표준처럼 쓰이는 earcut보다 빠르다는 내용이에요. 계산해 보면 폴리곤 하나에 약 132나노초, 1초에 750만 개 넘게 처리하는 속도예요. 지도 타일을 받는 즉시 그려야 하는 웹 지도에서는 꽤 의미 있는 숫자거든요.
earcut이 뭐길래 기준이 될까
earcut은 Mapbox가 만든 자바스크립트 삼각분할 라이브러리예요. Mapbox GL JS, MapLibre 같은 웹 지도 엔진에서 핵심 역할을 해 왔고, C++, Rust, Go 등으로도 옮겨져서 '지도 폴리곤 삼각분할 = earcut'이라고 해도 될 정도예요.
이름처럼 귀 자르기(ear clipping) 알고리즘을 써요. 이게 뭐냐면, 다각형에서 귀처럼 튀어나온 꼭짓점을 하나 찾아서 양옆 이웃과 함께 삼각형으로 잘라내는 방식이에요. 조건이 하나 있는데, 그 삼각형이 볼록해야 하고 안쪽에 다른 꼭짓점이 없어야 해요. 귀를 하나 자를 때마다 꼭짓점이 하나씩 줄고, 삼각형 하나만 남을 때까지 반복하면 끝나요. n각형을 자르면 항상 n-2개의 삼각형이 나와요.
방식이 단순한 만큼 최악의 경우 O(n²)까지 느려질 수 있는데, earcut은 z-order curve 해싱이라는 기법으로 이걸 줄여요. 2차원 좌표를 1차원 값으로 바꿔서 근처에 있는 점들만 빠르게 검사하는 방법이에요. 도서관에서 책을 찾을 때 서가 전체를 뒤지지 않고 분류번호로 해당 칸만 보는 것과 비슷해요. 구멍(hole)이 있는 폴리곤은 구멍을 바깥 테두리와 '다리'로 이어서 하나의 다각형처럼 다루고요.
재밌는 점은 earcut이 완벽한 정확성보다 속도와 실용성을 택했다고 스스로 밝힌 라이브러리라는 거예요. 꼬인 폴리곤이나 겹치는 점처럼 지저분한 데이터가 들어와도 그럴듯한 결과를 내도록 설계됐어요. 지도 데이터는 원래 지저분하니까 현실적인 선택이죠.
어디서 더 빨라질 수 있을까
구체적인 구현은 원문을 보시는 게 좋아요. 여기서는 이런 최적화가 보통 어디서 속도를 얻는지 정리해 볼게요. 지도 데이터의 특징을 알면 힌트가 보이거든요.
지도 폴리곤의 대부분은 건물이에요. 건물은 보통 꼭짓점이 4~10개 정도인 단순한 모양이고요. 그러니까 370만 개 중 대부분이 작고 단순한 다각형이에요. 이럴 때는 알고리즘의 시간 복잡도보다 폴리곤 하나를 처리할 때마다 드는 고정 비용이 훨씬 중요해져요.
- 메모리 할당: earcut의 JS 구현은 꼭짓점마다 연결 리스트 노드 객체를 만들어요. 폴리곤이 수백만 개면 객체 수천만 개가 생겼다 사라지면서 가비지 컬렉터가 바빠지죠. 미리 잡아 둔 TypedArray를 재사용하면 이 비용이 크게 줄어요.
- 특수 케이스 처리: 볼록 다각형이면 귀를 찾을 필요 없이 한 점에서 부채꼴로 이어 주면(fan triangulation) O(n)에 끝나요. 사각형 건물이라면 삼각형 두 개면 되고요.
- 데이터 배치: 좌표를 객체가 아니라 연속된 배열에 두면 CPU 캐시를 더 잘 활용할 수 있어요.
- 병렬화: 폴리곤끼리는 서로 영향을 주지 않으니 Web Worker나 스레드로 나눠 처리하기 좋아요.
업계 흐름에서 보면
삼각분할 라이브러리는 크게 두 갈래예요. 하나는 earcut처럼 빠르지만 근사적인 쪽이고, 다른 하나는 libtess2(OpenGL GLU 테셀레이터 계열), poly2tri, CDT(Constrained Delaunay Triangulation)처럼 정확하고 견고하지만 무거운 쪽이에요. 들로네 계열은 가늘고 긴 삼각형을 피해서 품질 좋은 메시를 만들기 때문에 지형 렌더링이나 시뮬레이션에 유리해요. 반면 웹 지도처럼 빨리 그리는 게 가장 중요한 곳에서는 earcut이 이겨 왔죠.
이번 글은 earcut이 강한 영역에서도 아직 더 짜낼 여지가 있다는 걸 보여 줘요. Cesium, deck.gl, MapLibre 같은 3D·웹 지도 엔진이 건물 수백만 개를 한 화면에 올리는 쪽으로 가고 있어서, 이런 작은 최적화가 체감 성능을 좌우하게 돼요.
한국 개발자에게 주는 시사점
국내에서도 디지털 트윈, 브이월드(V-World) 같은 공간정보 플랫폼, 스마트시티 프로젝트가 활발하잖아요. 서울 건물만 해도 수십만 동이고 전국으로 넓히면 수백만 건이 돼요. 이런 데이터를 웹에서 3D로 띄우고 있다면 타일을 불러올 때 삼각분할이 병목인지 한번 프로파일링해 볼 만해요.
지도 개발자가 아니어도 배울 점이 있어요. “내 데이터의 분포를 알면 범용 알고리즘을 이길 수 있다”는 거예요. 범용 라이브러리는 어떤 입력이 와도 처리하도록 만들어지지만, 실제 데이터의 90%가 단순한 경우라면 그 경로만 빠르게 만들어도 큰 이득을 볼 수 있거든요.
마무리
GPU는 삼각형만 그릴 줄 알기 때문에 지도 엔진의 속도는 결국 폴리곤을 얼마나 빨리 잘 자르느냐에 달려 있어요. 이번 사례는 데이터 특성을 파고들면 표준 라이브러리도 넘어설 수 있다는 걸 보여 줘요.
범용 라이브러리 대신 내 데이터에 맞춘 특수 경로를 직접 만들어서 성능을 크게 올려 본 경험이 있으신가요? 그때 유지보수 부담과 성능 이득 사이에서 어떻게 판단하셨는지 궁금해요.
🔗 출처: Hacker News