Insights
AI가 자동으로 큐레이션·번역·정리하는 기술 동향 피드입니다.
지도 폴리곤 삼각분할에 사용되는 알고리즘을 귀 자르기(ear clipping) 기반으로 교체하여 성능을 혁신적으로 개선했습니다. 기존 제약 Delaunay 방식 대비 처리 시간이 대폭 단축되었으며, 이는 특히 대규모 지도를 렌더링하는 데 필수적인 최적화 기법입니다.
AI 자동 생성 콘텐츠
본 콘텐츠는 GeekNews의 원문을 AI가 자동으로 요약·번역·분석한 것입니다. 원 저작권은 원저작자에게 있으며, 정확한 내용은 반드시 원문을 확인해 주세요.
원문 바로가기GPU로 지도 영역을 채우려면 건물, 공원, 주차장 등의
폴리곤을 삼각형으로 분할해야 함- 바르샤바 Śródmieście의 예시 구역은 폴리곤 331개, 꼭짓점 5,151개로 구성되며 삼각형 4,514개가 됨
바르샤바 주변 Masovian Voivodeship 오프라인 지도의
줌 레벨 13에는 폴리곤 3,740,425개가 있음- M4 Pro 단일 코어에서 기존 제약 Delaunay 삼각분할기는 전체 처리에 2.93초가 걸림
귀 자르기 구현을 아이디어별 커밋으로 재구성하고 동일한 데이터로 각 단계를 측정함
Delaunay 삼각분할은 각 삼각형의 외접원 안에 다른 점이 없도록 구성하며, 같은 점 집합의 삼각분할 중 최소 각도를 최대화함- 인접 삼각형의 공유 변을 뒤집는 국소 수정으로 조건을 복구함
제약 Delaunay에서는 원래 폴리곤의 변을 반드시 유지하므로, 일부 변은 외접원 조건에 따라 뒤집을 수 없음
기존 구현은 꼭짓점을 하나씩 삽입하고, 해당 점이 들어갈 삼각형을 찾아 분할한 뒤 주변 변을 뒤집음
폴리곤 경계도 강제로 삽입하고, 마지막에 폴리곤 내부이면서 구멍 바깥인 삼각형만 남김
좋은 모양의 삼각형은
보간과 시뮬레이션에는 중요하지만, 단색 채우기에서는 가늘고 긴 삼각형도 GPU가 정확하게 채움- 전체의 거의 절반인 180만 개는 꼭짓점이 4개 이하임
삼각형은 분할이 필요 없고 볼록 사각형은 두 삼각형이면 되지만, 기존 코드는 매번 구조를 새로 만들며 이들에만 419ms를 사용함
**귀(ear)**는 연속한 꼭짓점a
,b
,c
에서b
가 볼록하고, 삼각형abc
안으로 폴리곤의 다른 부분이 들어오지 않는 모서리임- 귀 하나를 잘라내면 꼭짓점이 하나 줄어듦
n개의 단순 폴리곤을n − 2
개 삼각형으로 분할할 수 있음
a,b
,c
와 정확히 같은 좌표의 점은 예외이며, 구멍을 연결한 경계에서 흔히 발생함 - 바르샤바 건물 예시로 귀를 차례로 잘라내는 과정을 확인할 수 있음
대상 데이터의
구멍 있는 폴리곤 11,345개는 구멍과 바깥 경계를 다리로 이어 하나의 닫힌 경계로 만듦- 다리를 양방향으로 한 번씩 지나고 구멍은 바깥 경계와 반대 방향으로 순회하므로 면적은 변하지 않음
다리 선택에는 David Eberly의 귀 자르기 문서의 방법을 사용함
구멍의 가장 오른쪽 꼭짓점
m
에서 오른쪽으로 광선을 쏘고, 처음 만나는 변의 교점I
와 더 오른쪽 끝점P
를 찾음 - 삼각형
m, I, P
안에 경계 꼭짓점이 없으면m
과P
를 연결함 - 내부에 오목 꼭짓점이 있으면 광선과 이루는 각도가 가장 작은 것을 연결 대상으로 선택함
오른쪽 구멍부터 연결해 왼쪽 구멍이 이미 경계에 편입된 구멍과 연결될 수 있게 함
구멍의 가장 오른쪽 꼭짓점
정수 타일 격자에는 추가 예외 처리가 필요함- 광선이 격자선을 따라 꼭짓점을 통과하는 경우를 교차 검사에서 올바르게 처리해야 하며, 초기 구현에는 이 부분의 오류가 있었음
안뜰이 바깥 경계와 한 꼭짓점에서 접하면 별도 다리 없이 공유 꼭짓점에서 두 경계를 합침
모든 경계를 순회하며 귀를 찾고 삼각형마다 인덱스 세 개를 쓰는
기본 구현은 1,119ms로, Delaunay보다 약 2.6배 빨랐음- 다만 꼭짓점이 257개 이상인 1,123개 폴리곤에서는 199ms로, Delaunay의 90ms보다 느렸음
귀 하나를 검사할 때 수백 개 꼭짓점을 훑고 이를 수백 번 반복하므로 비용이 꼭짓점 수의 제곱에 비례해 커짐
볼록 모서리의 삼각형을 막는 점이 있다면 그 안에는 반드시
**오목 꼭짓점(reflex vertex)**도 있으므로, 검사 대상을 오목 꼭짓점 목록으로 제한함- 이웃 귀를 자르면서 볼록해진 꼭짓점은 목록에서 제거함
볼록 꼭짓점이 오목하게 바뀌지는 않으므로 목록은 계속 줄어듦
귀 검사 2,810만 회가 확인하는 점은 3억 5,300만 개에서 1억 8,500만 개로 줄고, 전체 시간은
882ms가 됨 - 건물에는 오목 꼭짓점이 많아 절감에 한계가 있으며, 예시 건물은 꼭짓점 27개 중 15개가 오목함
작은 폴리곤에서는 목록 구성 비용 때문에 처리 시간이 34ms에서 54ms로 늘어남
볼록 폴리곤은 모든 모서리가 귀이므로 귀 검사를 생략함- 모든 모서리가 왼쪽으로 꺾인다는 조건만으로는 중심을 두 번 도는 별 모양 경계를 배제하지 못함
삼각형 스트립은 처음 두 인덱스 이후 새 인덱스 하나마다 삼각형 하나를 추가하므로, 삼각형마다 인덱스 세 개를 기록할 필요가 없음- 볼록 경계는 양쪽 끝을 지그재그로 선택해 하나의 스트립으로 만들 수 있음
일반 경계도 귀를 자른 뒤 양쪽 이웃을 번갈아 우선 검사하고, 다음 모서리가 귀가 아닐 때 스트립을 끝냄
스트립 출력으로
삼각형 2,150만 개에 필요한 인덱스가 6,450만 개에서 3,580만 개로 줄어듦- 스트립 종료 때 실패하는 검사도 생겨 귀 검사 횟수는 2,370만 회에서 2,500만 회로 늘어남
그래도 전체 시간은
762ms, 가장 큰 폴리곤 집단은 146ms에서 103ms로 줄어듦
오목 꼭짓점이
32개를 초과하면 경계 상자의 긴 축을 따라 버킷당 약 두 개씩 분류함- 귀 삼각형이 걸치는 버킷만 검사하고, 오목 꼭짓점이 절반 제거되면 인덱스를 재구축함
검사한 점은 1억 8,100만 개에서 1억 100만 개로 감소함
꼭짓점 257개 이상 집단은 103ms에서 57ms로 줄고, 전체 시간은
697ms가 됨
기존 검사는 삼각형 내부의 오목 꼭짓점을 처음 찾으면 즉시 종료하지만, 대부분은 내부 점이 없어
조기 종료의 이득이 없음- 대신 점마다 세 번의 비교 분기를 CPU가 예측해야 함
첫 번째 순회에서
분기 없이 내부 점 수를 계산하고, 0이면 바로 귀로 판정함- 세 외적 값의 최솟값이 0 이상이면 닫힌 삼각형 내부에 해당함
내부 점이 있을 때만 기존 정밀 검사를 실행해 삼각형 모서리와 좌표가 같은 예외를 걸러냄
버킷 경로는 경계 상자 검사 결과를 점 64개씩 비트 마스크에 담음
전체 시간은
519ms, 꼭짓점 33~256개 집단은 327ms에서 216ms로 줄어듦
오목 꼭짓점이 32개 이하인 목록에도
비트 마스크를 적용해 첫 순회에서 발견한 점만 정밀 검사함- 내부 점을 세는 대신 해당 비트를 켜고, 설정된 비트를 하나씩 처리함
읽는 점 수는 1억 2,800만 개에서 1억 2,000만 개로 감소함
공개된 최종 구현은
489ms로, 동일 데이터의 Delaunay 대비 약 6배 빨랐음
격자 반올림은 단순 폴리곤을 깨뜨릴 수 있어 Meisters 정리의 전제가 성립하지 않을 수 있음- Warszawa Śródmieście 역 경계는 지도 파일의 18cm 격자에서도 꼭짓점 154개 중 31개가 이웃과 합쳐짐
더 거친 격자에서는 경계가 자기 자신과 접해 귀가 하나도 없어질 수 있으며, 격자를 더 거칠게 했을 때 다시 분할되는 경우도 있음
한 바퀴를 돌아도 귀를 찾지 못하면
면적이 없는 모서리를 제거하고 다시 시도하며, 그래도 실패하면 기존 Delaunay 코드로 처리함- 이전에 생성한 Masovian 지도에서는 76개 폴리곤이 이 경로로 넘어감
지도 생성기는 현재 GEOS의
**스냅 라운딩(snap rounding)**으로 최종 격자에 맞추고 귀 자르기 가능 여부를 검사함 - 새 지도 빌드에서는 폴리곤 273개를 수정했으며, 파일의 모든 폴리곤을 귀 자르기로 처리할 수 있었음
구멍이 많은 폴리곤도 Delaunay가 유리함- 다리를 찾을 때마다 전체 경계를 훑으므로 구멍 수만큼 반복 스캔이 필요함
세계 지도의 구멍 11,675개짜리 폴리곤은 귀 자르기에 606ms, Delaunay에 17ms가 걸림
엔진은 구멍이 128개 이상이면 Delaunay로 보내며, Masovian 데이터에서는 두 개가 해당함
라이브러리는 귀가 소진되거나, 생성한 삼각형의 면적이 맞지 않거나,
링이 128개를 초과할 때 링 경계를 제약 조건으로 삼는 Delaunay 경로를 사용함- C++의
run()
과 JavaScript의lastStatus()
로 처리 경로를 확인할 수 있음 - 세계 지도 타일의 폴리곤 56,472개에서는 earstrip이
459ms, earcut.hpp가2,892ms를 기록함 - 귀 자르기로 정확히 처리할 수 없는 줌 레벨 13 폴리곤에서 짝홀 채우기(even-odd fill)와 다른 픽셀 비율은 평균 earcut 31%, earstrip 0.15%였음
비교 대상은 MapLibre와 Mapbox GL이 사용하는 earcut의
earcut.hpp 3.2.4와 earcut.js 3.2.4임- 동일 C++ 엔진을 WebAssembly로 실행하는 웹 렌더러를 개발하면서 양쪽 C++ 구현의 WebAssembly 성능도 비교함
분리한 earstrip은 테스트 데이터 580만 개 폴리곤에서 엔진과 정확히 같은 스트립을 출력함
각 WebAssembly 빌드는 줌 레벨 13과 9의 440만 개 폴리곤에서 해당 네이티브 빌드와 정확히 같은 삼각형을 출력함
아래 결과는
줌 레벨 13의 374만 개 폴리곤, 단일 스레드, 7회 중 최선의 시간임- V8은 Node, JavaScriptCore는 Bun에서 실행함
npm 비교의 earcut 열은 earcut.js이며, 나머지 earcut 열은 C++ 또는 이를 컴파일한 WebAssembly임
| 실행 방식 | earstrip | earcut |
|---|---|---|
| 네이티브 C++ | 489ms | 557ms |
| WebAssembly 내부 루프, V8 / JSC | 601 / 566ms | 930 / 843ms |
| 폴리곤마다 JS에서 WebAssembly 호출, V8 / JSC | 688 / 688ms | 1,007 / 950ms |
| npm 패키지, 폴리곤별 호출, V8 / JSC | 766 / 807ms | 1,103 / 1,290ms |
| npm 직접 호출, 전체 폴리곤 일괄 처리, V8 / JSC | 635 / 619ms | 해당 없음 |
earcut 호환 호출은 JavaScript 숫자 좌표를 받고 매번 새 삼각형 인덱스 배열을 반환함- earcut.js 대비 V8에서 1.4배, JavaScriptCore에서 1.6배 빨랐음
직접 일괄 호출은 폴리곤을 모듈 메모리에 직접 넣고 WebGL 2 또는 WebGPU용 스트립 인덱스 버퍼 하나를 받아 이러한 비용을 피함- earcut.js 대비 V8에서 1.7배, JavaScriptCore에서 2.1배 빨랐음
earcut도
오목 꼭짓점만 귀를 막을 수 있다는 성질을 활용하지만, 별도 목록을 유지하지 않고 경계 상자와 삼각형 검사를 통과한 각 점에 마지막으로 적용함- 꼭짓점이 80개를 넘으면 z-order로 연결하고 삼각형 경계 상자에 해당하는 구간만 검사하며, 이는 earstrip의 버킷과 유사한 역할을 함
반면 볼록 폴리곤 단축 경로, 스트립 출력, 분기 없는 개수 계산은 없으며 삼각형당 인덱스 세 개를 쓰고 첫 내부 점에서 검사를 종료함
earstrip GitHub 저장소는
단일 C++ 헤더와 벤치마크용 폴리곤 및 측정 코드를 제공함- npm 패키지는 earcut과 같은 인수를 받는 WebAssembly 빌드를 제공함
라이선스는 earcut과 동일한
ISC임