요약
지도 엔진의 삼각분할기 earstrip이 earcut보다 빠르게 폴리곤 370만 개를 489ms에 처리합니다.
지도 엔진 GLMap을 만드는 예브겐 보두노프가 엔진의 삼각분할기(폴리곤을 GPU가 그리는 삼각형으로 쪼개는 코드)를 ISC 라이선스로 공개했습니다. 기존 방식이 너무 느려 귀 자르기(볼록한 꼭짓점을 하나씩 잘라 내는 방법)로 바꾸고, 아이디어마다 시간을 잰 과정을 정리했습니다.
왜 중요한가
- Mapbox GL JS 등이 쓰는 earcut을 네이티브와 브라우저 양쪽에서 앞선 대안이 생겼습니다.
- 최적화를 커밋 하나씩 나눠 같은 데이터로 측정해, 어떤 아이디어가 실제로 효과가 있었는지 수치로 보여 줍니다.
- 코드와 테스트 폴리곤, 벤치마크 환경을 모두 공개해 누구나 직접 비교해 볼 수 있습니다.
핵심 내용
- M4 Pro 코어 하나에서 기존 제약 들로네 삼각분할의 2,931ms가 489ms로 약 6배 빨라졌습니다.
- 네이티브 C++에서는 earcut.hpp(557ms)보다 빨랐고, 세계 지도 데이터에서는 459ms 대 2,892ms로 차이가 컸습니다.
- 효과가 가장 큰 단계는 오목 꼭짓점(귀를 가로막을 수 있는 안쪽으로 꺾인 점)만 검사하기와 분기 없는 개수 세기였습니다.
- WebAssembly에서 earcut.hpp는 67% 느려졌지만 earstrip은 23%만 느려져, npm판은 earcut.js보다 1.7~2.1배 빠릅니다.
- 귀가 바닥나거나 면적이 맞지 않거나 고리가 128개를 넘는 폴리곤은 들로네 방식으로 넘깁니다.
HN 반응
- earcut 저자는 번들 크기 때문에 일부 최적화를 일부러 뺐다고 밝혔고, 작성자는 WASM 모듈이 gzip 기준 27KB라고 답했습니다.
- 길고 가는 삼각형이 GPU에 불리하다는 지적이 이어졌지만, 작성자는 지도에서는 들로네의 CPU 비용이 더 크다고 답했습니다.
삼각분할기의 원조격인 이것도 언급해야 합니다.
https://www.cs.cmu.edu/~quake/triangle.html
저는 이걸(의 닷넷 래퍼를) 써서 지자체 쓰레기 수거 구역을 색깔별로 구분한 둥근 면적 폴리곤을 수년째 만들고 있습니다. 문제없이 잘 돌아가고 빠릅니다.
안녕하세요 Evgen님, Earcut 제작자입니다. 글 잘 읽었고 정말 멋진 라이브러리네요! Earcut JS 버전에 가져다 쓸 만한 요령이 있는지 살펴봐야겠습니다. :)
한 가지 말씀드리면, 라이브러리를 작게 유지해서 번들 크기가 불어나지 않게 하려고 최적화 후보 몇 가지는 일부러 포기했습니다. 대부분의 실용적인 용도(예: Mapbox GL JS)에는 지금도 충분히 빠르고요(min/gz 기준 4.1k). Earstrip의 WASM 빌드는 얼마나 되는지 궁금하네요.
C++ 쪽에서는 Mapbox가 이제 하이브리드 방식을 씁니다. 작은 폴리곤은 earcut.hpp로 처리하고, 크고 복잡한 폴리곤은 단조 분해(monotone decomposition)에 기반한 다른 알고리즘으로 넘깁니다. 이쪽은 알고리즘 복잡도의 상수는 더 크지만 입력 크기에 따른 확장성이 훨씬 좋기 때문입니다.
안녕하세요! Leaflet, earcut을 비롯해 그동안 해 오신 모든 작업에 감사드립니다. 이 아이디어 중 쓸 만한 게 있으면 좋겠습니다. 분기 없는 dent 카운트를 한번 보세요. 저희가 earcut을 앞지를 수 있었던 비결이고, wasm 빌드가 그렇게 빠른 이유의 큰 부분이기도 합니다. wasm 모듈은 gzip 기준 27KB이고, npm 패키지에는 base64 래퍼까지 포함해 약 41KB입니다.
대단하네요. 성능 향상이 인상적입니다!
저는 폴리곤과 구멍을 지원하는 제약 들로네 삼각분할기 Delaunay32의 제작자입니다. 점진적 삽입이 아니라 분할 정복 방식을 써서, 여기 나온 들로네 기준선과 비교하면 어떨지 궁금합니다.
https://github.com/morishuz/delaunay32
아직 이 코퍼스로는 벤치마크를 돌려 보지 못했고, 지금 저희 폴리곤 API는 단순한 링과 서로 닿지 않는 구멍만 받을 수 있습니다. 데이터셋을 공개해 주셔서 감사합니다. 테스트와 비교에 요긴하게 쓰일 것 같아요!
벤치마크 없는 숫자는 쓸모가 없죠. :) 벡터 지도를 생성할 때는 모든 데이터가 유효하도록 보장합니다. 하지만 사용자가 직접 만든 GeoJSON 레이어를 가져오면 온갖 자기 교차가 들어 있을 수 있습니다.
오, 흥미롭네요. 직접 비교를 돌려 주셔서 감사합니다! 이 작업에서는 확실히 earstrip이 유리해 보이네요.
그래도 삼각분할이 들로네 조건을 만족한다는 건 큰 장점입니다! 벤치마크에는 https://github.com/mapbox/earcut.hpp 도 꼭 넣어 보세요. 최근에 earcut 출력을 들로네로 다듬는 refine 함수가 생겼는데, earcut+refine도 여전히 꽤 빠릅니다.
감사합니다, 좋은 제안이네요! earcut에 refine을 더한 비교는 합리적으로 들립니다.
그 사이에 world 데이터셋 벤치마크를 로컬에서 재현해 봤는데, 통과한 입력에서는 폴리곤 검증이 delaunay32 시간의 약 3분의 2를 차지하고 있었습니다.
실제 데이터라면 검증 없이 먼저 삼각분할을 한 다음, 결과가 유효한지 사후에 확인하는 쪽이 보통 더 빠릅니다(삼각형 넓이의 합을 폴리곤 넓이와 비교하기만 하면 됩니다).
귀 자르기에 최적화를 더한 방식이 Seidel의 사다리꼴 방법 같은 것을 제치고 삼각분할의 주류가 된 이유가 오래전부터 궁금했습니다. Seidel 방법은 시간 복잡도가 O(nlog*n)이고 구멍도 자연스럽게 처리합니다. 빅오가 전부는 아니라는 건 알지만, 사실상 선형 대 이차 시간인 데다 시간이 갈수록 더 복잡한 폴리곤을 삼각분할해야 하는 경우가 늘고 있는 것 같거든요.
그냥 삼각형 품질 때문일까요? Seidel 방식은 다루기 까다로운 슬리버 삼각형을 너무 많이 만들어 내나요?
solvespace에서는 단순한 귀 자르기 알고리즘을 쓰는데, O(n*log(n))짜리가 있다면 정말 쓰고 싶습니다.
작고 이해하기 쉬운 건 아직 못 봤어요 ;-) 제가 시도한다면 공간 인덱스를 추가해서 삼각형 안에 뭔가 들어 있는지 확인하는 비용을 O(log(n))으로 만들고, 잘려 나간 귀에 인접한 새 귀를 확인하도록 하겠습니다. 그러면 n*log(n)이 될 텐데, 제가 갖고 있던 공간 인덱스는 3D용이라 어딘가 오래된 HD에 들어 있네요.
상수가 아주 크고 구현이 몹시 복잡합니다. 저도 시도했다가 포기하고 나서 earcut을 만들게 됐습니다(전형적인 지도 데이터에서는 Seidel이 더 느렸고 견고성도 떨어졌습니다). 다시 도전해 볼 만할 수도 있어요. 요즘은 LLM 기반 검증·최적화 루프 덕분에 알고리즘 라이브러리 작업이 훨씬 쉬워졌으니까요.
결과물에 아주 길고 가느다란 삼각형이 많이 보이는데요. 그런 삼각형이 보통 GPU 래스터라이저에는 최악의 경우 아닌가요?
역사적으로 그랬고, 현대적인 모범 사례에 맞춰 최적화된 요즘 시스템에서는 더 그렇습니다. 예를 들어 Unreal Engine의 Nanite는 지오메트리를 삼각형의 계층적 클러스터로 쪼갭니다.
삼각형이 길고 가늘면 화면을 가로질러 늘어나서 Nanite의 계층적 스트리밍과 컬링 시스템을 망가뜨립니다.
길고 가느다란 폴리곤에서는 셰이딩 아티팩트도 생깁니다.
큰 데이터셋에서는 길고 가는 삼각형으로 이루어진 성근 지오메트리와 전통적인 방식보다, 계층적 스트리밍을 쓰는 촘촘한 지오메트리가 성능이 더 좋습니다.
모바일 GPU는 타일 기반 렌더링을 씁니다. 길고 가는 삼각형은 더 많은 타일에 걸치기 때문에 비용이 더 듭니다. 그래서 항상 들로네를 써야 한다고 생각하기 쉽지만, 더 보기 좋은 들로네 삼각형으로 GPU에서 얻는 이득은 CPU에서 들로네에 치르는 시간에 비해 작습니다. 지도 데이터로 시간 프로파일을 직접 재 봤습니다. 게임이라면 그만한 값어치가 있을 수도 있겠지만요.
물론이죠, 병목이 어디 있는지 알아야 합니다. 그래서 애초에 좋은 모델을 만드는 게 최선이고요.
Nanite나 삼각분할은 GPU 병목을 덜어 주지만, 이미 CPU가 한계까지 몰려 있다면 도움이 안 됩니다. 맞는지는 작업 부하에 달려 있습니다.
성능이 좋네요. 삼각형만 봐도 일부는 꽤 작아 보이는데, 렌더링에 문제가 생기지는 않나요?
GeoRust의 오버레이 엔진인 iShape-rust와 비교해서도 벤치마크 결과가 좋은지 궁금합니다.
https://github.com/ishape-rust/ioverlay
엄밀히 같은 조건의 비교는 아닙니다. iOverlay는 집합 연산이나 버퍼링 같은 걸 하는 위상 툴킷에 가깝습니다. 삼각분할과는 꽤 다르죠.
댓글 작성자가 말하려던 건 아마 https://github.com/iShape-Rust/iTriangle 일 겁니다. 자매 라이브러리인데, 삼각분할이 정말 빠릅니다. 특히 입력이 클수록 그렇습니다.
삼각분할 알고리즘은 잘 모르는데, 길고 좁은 삼각형을 고르면 문제가 생기나요? 사람이 한다면 보통 더 "균형 잡힌" 삼각형을 택하려 할 것 같은데요.
용도에 따라 다릅니다.
이 경우 삼각형을 더 균형 있게 만들면 정점 수만 늘어납니다. 그러면 GPU 메모리가 더 필요하고 정점 파이프라인이 할 일도 늘어납니다.
또 폴리곤이 꽤 작아서, 삼각형을 더 잘게 나눈다고 해서 렌더링 초기에 걸러 내는 컬링 이점이 생기는 것도 아닙니다.
더 균형 잡힌 삼각형을 얻으려고 정점 수를 늘릴 필요는 없습니다. 글에 나온 방법 중에 정점을 추가하는 건 없고, 균형 잡힌 삼각형은 들로네 삼각분할이 다른 방법보다 더 잘 만들어 냅니다. 다만 가장 느리기도 해서, 삼각형 품질과 속도 사이에 트레이드오프가 있는 겁니다.
같은 픽셀을 여러 번 덮는 삼각형도 성능 문제입니다. 아주 가느다란 띠 모양은 성능에 좋지 않고, 메모리 비용을 아끼는 것보다 손해가 더 큽니다.
결과 토폴로지가 좀.. 폭력적이지 않나요? 그래도 실제 렌더링에 얼마나 영향을 주는지는 궁금하네요.
어쨌든 멋진 작업이고, 글 자체도 훌륭합니다.
흥미로운 최적화네요. 최적화 단계 중 어느 것은 LLM이 생각해 냈고 어느 것은 사람의 도움이 필요했는지 밝혀 주실 수 있나요?
확실하진 않지만, "This post is about how we got there.\nA GPU fills triangles and nothing else." 같은 문장은 Claude 티가 많이 납니다. "[I created] one commit per idea, and timed every commit on those same 3.7 million polygons, so each section below ends with a number."도 그렇고, "A triangle needs no cutting at all"도 그렇습니다.
제 경험상 Claude Opus 5와 5.5는 최적화 구현은 아주 잘하고, 시도해 볼 접근법을 제안하는 것도 꽤 잘하지만, 런타임이 느리다는 점을 문제로 알아채는 데는 그리 적극적이지 않습니다. 제가 속도를 물어볼 때까지는 단순한 구현으로 가는 경향이 있는데, 개발의 통념과는 확실히 맞아떨어지는 행동이긴 합니다.
흠.
훌륭한 글입니다. 작성자분께 박수를 보냅니다.