earcut보다 빠르게: 지도 폴리곤 374만 개를 489ms에 삼각분할하기

AI 요약

지도 렌더러는 건물과 공원 같은 폴리곤을 GPU가 그릴 삼각형으로 바꿔야 합니다. Globus는 기존 constrained Delaunay triangulation이 마조비에츠키에 지역 지도 데이터 374만 개를 처리하는 데 M4 Pro 한 코어에서 2.93초 걸리자, 귀 자르기(ear clipping)를 적용해 earstrip 라이브러리로 공개했습니다. C++ 헤더 하나와 WebAssembly 기반 npm 패키지로 제공하며 ISC 라이선스를 사용합니다.

Delaunay에서 귀 자르기로

Constrained Delaunay는 폴리곤 경계를 삼각형 변으로 유지하면서 점을 하나씩 삽입하고, 원의 조건에 맞지 않는 변을 뒤집어 삼각분할합니다. 삼각형 모양이 균형 잡히는 장점이 있지만, 단색으로 채우는 지도 폴리곤에서는 그 품질이 꼭 필요하지 않습니다. 마조비에츠키에 데이터 중 약 180만 개는 꼭짓점이 네 개 이하였고, 기존 구현은 이 간단한 폴리곤에도 삼각분할을 새로 계산했습니다.

귀 자르기는 오목하지 않은 꼭짓점 중 삼각형 내부에 다른 경계점이 없는 곳을 찾아 삼각형 하나를 떼어냅니다. 단순 폴리곤에는 항상 자를 수 있는 귀가 있어 반복하면 삼각형으로 나뉩니다. 구멍은 각 구멍의 꼭짓점과 바깥 경계를 잇는 다리로 연결해 하나의 경계 고리로 만듭니다. 다리가 다른 경계와 겹치지 않도록 오른쪽으로 광선을 쏘아 후보를 찾습니다. 지도 데이터에서는 격자선에 놓인 점이나 바깥 경계와 한 점에서 맞닿은 구멍도 별도로 처리해야 합니다.

귀 검사를 줄이는 최적화

처음 구현은 각 귀 후보마다 나머지 경계점을 모두 검사합니다. 이 방식으로도 374만 폴리곤을 1.12초에 처리했지만, 꼭짓점이 257개 이상인 가장 큰 1,123개 폴리곤에서는 199ms가 걸렸습니다. 검사량이 폴리곤 크기의 제곱에 따라 커지기 때문입니다.

첫 최적화는 귀를 막을 수 있는 점을 오목한 꼭짓점, 즉 움푹 들어간 점으로 한정합니다. 전체 점 대신 오목점만 검사해 점 검사 횟수를 3억 5,300만 회에서 1억 8,500만 회로 줄였습니다. 다만 작은 폴리곤에서는 오목점 목록을 만드는 비용이 절감분보다 커졌습니다. 오목점이 없는 볼록 폴리곤은 모든 꼭짓점이 귀이므로 별도 검사 없이 처리하고, 삼각형과 사각형도 바로 지름길로 넘깁니다.

다음으로 삼각형마다 인덱스 세 개를 쓰는 대신, 이어지는 삼각형을 표현하는 triangle strip을 만듭니다. 귀를 잘라낸 양쪽 이웃을 번갈아 이어 붙여 한 스트립을 늘리고, 다음 귀가 아닌 지점에서 새 스트립을 시작합니다. 삼각형 2,150만 개를 표현하는 인덱스 수가 6,450만 개에서 3,580만 개로 줄었습니다.

오목점이 많은 큰 폴리곤에서는 점들을 경계 상자의 긴 축을 따라 버킷에 나눕니다. 귀 검사 때 삼각형과 겹치는 버킷만 확인하고, 오목점이 절반 이상 사라지면 인덱스를 다시 만듭니다. 이어서 분기문 없이 삼각형 안의 오목점 수를 세고, 실제로 안에 점이 있을 때만 정확한 검사를 합니다. 첫 검사에서 확인한 점의 위치를 비트 마스크에 기록해 재검사 대상도 줄입니다. 이 단계까지 적용한 구현이 공개된 earstrip입니다.

예외 처리와 비교 결과

지도 좌표를 정수 격자에 맞추면 서로 다른 꼭짓점이 같은 위치에 놓이거나 경계가 자기 자신과 교차할 수 있습니다. 귀를 찾지 못하면 면적이 없는 꼭짓점을 제거해 다시 시도하고, 그래도 실패하면 해당 폴리곤에 constrained Delaunay를 사용합니다. 구멍이 128개 이상인 폴리곤도 Delaunay로 보냅니다. 원문은 이런 예외로 기존 마조비에츠키에 데이터에서 76개 폴리곤이 대체 알고리즘을 썼다고 설명합니다. 생성기에서 GEOS snap rounding으로 경계를 정리한 새 데이터에서는 귀 자르기가 모든 폴리곤을 처리했다고 덧붙입니다.

같은 374만 폴리곤 벤치마크에서 최종 C++ 구현은 489ms, earcut.hpp는 557ms였습니다. WebAssembly 내부에서 처리할 때 V8 기준 earstrip은 601ms, earcut은 930ms입니다. JavaScript에서 폴리곤별로 호출하는 npm 패키지 비교에서는 V8 기준 earstrip 766ms, earcut.js 1,103ms였고, 모든 폴리곤을 한 번에 전달하는 직접 호출은 earstrip이 635ms였습니다. 좌표 복사와 호출 경계 비용도 전체 성능에 영향을 줍니다. 저자는 5,647만 개의 세계 지도 타일 폴리곤 비교에서도 earstrip 459ms, earcut.hpp 2,892ms를 보고했습니다.

원문: globus.software / 번역·요약: Trawling

Hacker News 반응

• @swiftcoder — 흥미로운 최적화입니다. 최적화 단계 중 LLM이 제안한 부분과 사람이 도운 부분을 공개할 생각이 있는지 궁금합니다.
  • @entrope — 잘 모르겠지만, 도입부와 각 아이디어마다 커밋을 만들고 같은 370만 폴리곤으로 시간을 쟀다는 문장이 Claude가 쓴 듯합니다. 제 경험으로 Claude Opus 5와 5.5는 최적화 구현을 잘하고 시도할 접근법도 꽤 잘 제안하지만, 요청하기 전에는 느린 실행 시간을 문제로 찾아내는 데 적극적이지 않습니다. 개발할 때 흔히 권하는 방식이기도 합니다.
• @mourner — 안녕하세요, Earcut 작성자입니다. 글과 라이브러리 모두 좋습니다. JavaScript 버전에 가져올 만한 요령이 있는지 살펴보겠습니다. Earcut은 라이브러리 크기를 작게 유지하려고 일부 최적화를 넣지 않았습니다. Mapbox GL JS처럼 대부분의 실제 사용 사례에서는 충분히 빠르며 min/gzip 기준 4.1KB입니다. earstrip의 WebAssembly 크기도 궁금합니다. Mapbox C++는 작은 폴리곤에 earcut.hpp를 쓰고 큰 복잡한 폴리곤에는 단조 분할 기반의 다른 알고리즘을 쓰는 혼합 방식을 사용합니다.
  • @molind — 고맙습니다. 분기 없는 오목점 계산이 earcut보다 빨라지는 데 큰 역할을 했고 WebAssembly 성능에도 크게 기여했습니다. WebAssembly 모듈은 gzip 기준 27KB이고, npm 패키지의 base64 래퍼를 포함하면 약 41KB입니다.
• @Gravityloss — 삼각분할 알고리즘은 잘 모르지만 길고 얇은 삼각형이 생기면 문제가 되나요? 사람이 한다면 더 균형 잡힌 모양을 만들 것 같습니다.
  • @dan00 — 용도에 따라 다릅니다. 여기서 더 균형 잡힌 삼각형을 만들면 꼭짓점 수가 늘어 GPU 메모리와 정점 파이프라인 작업량이 증가합니다. 폴리곤이 대부분 작아서 삼각형을 작게 나눠도 조기 제거 이점은 없습니다.
  • @well_ackshually — 같은 픽셀을 반복해서 덮는 삼각형도 성능 문제입니다. 아주 얇은 삼각형은 성능에 좋지 않고 메모리 비용보다 손해가 클 수 있습니다.
  • @yorwba — 균형 잡힌 삼각형을 만들 때 꼭짓점을 늘릴 필요는 없습니다. 글에서 다룬 방식은 새 꼭짓점을 추가하지 않으며, Delaunay가 다른 방식보다 균형 잡힌 삼각형을 잘 만듭니다. 대신 속도가 느리므로 절충이 필요합니다.
• @morishuz — 제약 Delaunay 삼각분할기 Delaunay32를 만들었습니다. 분할 정복 방식을 쓰는데 이 데이터와 비교하면 어떨지 궁금합니다. 아직 같은 데이터로 벤치마크하지 않았고 현재 API는 서로 맞닿지 않는 단순 고리만 받습니다.
  • @molind — 벤치마크 없는 수치는 쓸모없습니다. 세계 지도 데이터 56,472개 폴리곤에서 earstrip은 453.4ms, Delaunay32는 1,696.9ms였습니다. earstrip은 정확 처리 56,338개, 제약 Delaunay 처리 134개였습니다. Delaunay32는 3,039개를 거부했습니다.
  • @mourner — Delaunay 조건을 만족하는 삼각분할도 큰 장점입니다. earcut.hpp의 refine 기능으로 결과를 Delaunay 방식으로 다듬는 비교도 해보세요. 귀 자르기와 refine을 함께 쓰면 여전히 빠릅니다.
• @mistercow — 왜 Seidel 사다리꼴 분할 같은 O(n log*n) 방식보다 최적화한 귀 자르기가 널리 쓰이는지 궁금합니다. 입력이 복잡해질수록 선형에 가까운 방식이 유리할 텐데, 삼각형 품질 문제인가요?
  • @mourner — 상수 비용과 구현 복잡도가 매우 큽니다. 직접 시도했을 때 일반적인 지도 데이터에서는 Seidel 방식이 더 느리고 견고성도 떨어져 포기했습니다. LLM 기반 검증과 최적화 덕분에 알고리즘 라이브러리 작업이 쉬워졌으니 다시 시도해볼 만할 수도 있습니다.
• @stymaar — 결과에 길고 얇은 삼각형이 많아 보입니다. GPU 래스터라이저에 좋지 않은 최악 사례 아닌가요?
  • @molind — 모바일 GPU는 타일 기반 렌더링을 쓰므로 길고 얇은 삼각형이 더 많은 타일에 닿을 수 있습니다. 그래도 지도 데이터에서는 GPU에서 더 나은 Delaunay 삼각형을 얻는 이점보다 CPU에서 Delaunay를 계산하는 비용이 큽니다. 게임에서는 결과가 다를 수 있습니다.