MARTINI/RTIN 알고리즘 이해

MARTINI/RTIN 알고리즘 구조

역자의 말: 이 문서는 지형 렌더링 최적화를 위해 널리 사용되는 MARTINI 및 RTIN(Right-Triangulated Irregular Networks) 알고리즘의 핵심 원리를 다루고 있습니다. 이 알고리즘은 고해상도 하이트맵(Heightmap) 데이터를 기반으로 지형의 굴곡이 심한 곳은 작은 직각 삼각형으로 재귀적으로 분할하여 디테일을 살리고, 평탄한 곳은 큰 삼각형으로 유지하여 전체적인 폴리곤 수를 획기적으로 줄이는 동적 레벨 오브 디테일(LOD) 기법입니다. 실시간 그래픽스 및 모바일 환경에서 지형 렌더링 성능을 극대화하는 데 매우 유용한 방식이므로, 게임 엔진이나 렌더링 파이프라인에 적용하기 전 해당 알고리즘의 계층적 분할 구조를 직관적으로 이해하는 데 도움이 되길 바랍니다.

---

1. 시작하며: 왜 지형을 최적화해야 할까요?

먼저 2019년 중국 거인 네트워크에서 오픈월드 게임을 개발할 때 작업 했던 흔적들을 봅시다. 중국 회사들은 대부분 연말 실적 브리핑을 해야합니다. 그때 작성 했던 예전 PPT 문서의 일부입니다.

지형(Terrain)을 렌더링할 때 가장 무식하고(?) 단순한 방법은 모든 면을 똑같은 크기의 촘촘한 삼각형 덩어리(균일 그리드)로 만드는 것입니다. 하지만 이렇게 하면 아무것도 없는 밋밋한 평지에도 불필요하게 많은 폴리곤이 들어가게 됩니다. 반대로 폴리곤을 극단적으로 줄이려고 마음대로 점을 찍어서 연결하면, 지형의 품질은 좋겠지만 연산이 너무 느려지고 지형 덩어리끼리 이어붙일 때 틈새가 벌어지기 십상입니다.

2019년 당시에는 모바일 게임에서 터레인 자체를 사용하기에는 부담스러웠던 시절이기에 대부분의 회사들이 메시 터레인으로 변환 하여 사용해 왔습니다. 터레인의 픽셀애러를 10 이상으로 설정 할 경우 드로우콜 방어는 되지만 실루엣이 처참하게 뭉개져버리기 때문에 아트팀에서 인가 할 수 없는 상황이기도 했습니다.

이 두 가지 문제점을 완벽하게 해결해 주는 마법 같은 방법이 바로 RTIN(Right-Triangulated Irregular Network), 그리고 이를 더 쉽게 쓸 수 있게 만든 MARTINI 알고리즘입니다.

처음 적용을 했기 때문에 레퍼런스로 Polygon Cruncher SDK 를 참조 하여 유니티 플러그인인 Terrain2Mesh 를 수정했습니다. 이후 신동네트워크에서도 동일하게 작업 됬습니다.

2. 핵심 원리: '수직 에러'란 무엇일까?

이 알고리즘의 목표는 아주 단순합니다. "울퉁불퉁한 곳엔 폴리곤을 많이, 평평한 곳엔 폴리곤을 적게 쓰자!" 입니다.

그렇다면 컴퓨터는 어디가 울퉁불퉁한지 어떻게 알 수 있을까요? 여기서 '수직 에러(Vertical Error)'라는 개념이 등장합니다.

수직 에러의 개념

위 이미지를 보면 이해가 쉽습니다.

원래의 울퉁불퉁한 땅(초록색 선)을 크고 단순한 폴리곤(파란색 선)으로 덮었다고 상상해 보세요. 이때, 가짜 폴리곤과 실제 땅 높이의 차이를 '수직 에러'라고 부릅니다.

• 평지: 크고 단순한 폴리곤으로 덮어도 실제 땅과의 높이 차이가 거의 없습니다. (에러가 작음 → 큰 삼각형 유지)
• 절벽, 산맥: 큰 폴리곤으로 덮으면 실제 땅과의 높이 차이가 큽니다. (에러가 큼 → 더 작은 삼각형으로 쪼갬)

보충 설명: 삼각형은 어떻게 쪼개질까?

항상 직각 이등변 삼각형의 '가장 긴 변(빗변)'의 가운데를 쪼개는 방식으로 반씩 줄여나갑니다. 아래 이미지를 보시면 정사각형이 어떻게 잘게 쪼개져 나가는지 직관적으로 이해하실 수 있습니다.

RTIN 알고리즘의 격자 분할 과정 (Level 0 ~ Level 2)

3. 골치 아픈 '틈새(T-Junction)' 문제 해결

아티스트 분들이 지형 최적화(LOD) 툴을 쓰다 보면 가장 스트레스 받는 문제 중 하나가 바로 메쉬가 찢어지는 현상, 즉 'T-Junction'에 의한 크랙(Crack)입니다. 디테일이 높은 영역과 낮은 영역이 만나는 경계선에서 정점(Vertex)의 개수가 맞지 않아 빈 공간이 뻥 뚫려 보이는 현상이죠.

T-Junction과 RTIN 메쉬 비교

하지만 RTIN 알고리즘은 "무조건 가장 긴 변(빗변)의 가운데를 반으로 가른다"는 단순한 수학적 규칙을 가지고 있습니다. 이 규칙 덕분에, 옆에 있는 삼각형이 쪼개지든 말든 모서리가 딱 들어맞게 됩니다. 즉, 아티스트가 후처리로 경계선을 바느질하듯 꿰매거나 가려줄 필요 없이 태생적으로 틈새(Crack)가 생기지 않는 엄청난 장점을 가집니다.

4. 알고리즘은 어떻게 작동하나요? (2단계 과정)

프로그래머들이 이 알고리즘을 좋아하는 이유는 코드가 아주 깔끔하게 두 단계로 나뉘기 때문입니다.

1. 지형 파악하기 (Phase 1): 처음 한 번만 맵 전체를 훑어보면서 "여기는 평지니까 에러 0, 여기는 절벽이니까 에러 100" 이런 식으로 에러 지도를 만듭니다.
2. 카메라 거리에 맞춰 메쉬 뽑아내기 (Phase 2): 유저의 카메라가 산에 가까워지면 허용하는 에러 수치를 낮춰서 폴리곤을 잘게 쪼개고, 멀어지면 에러 수치를 높여서 큼직한 폴리곤으로 렌더링합니다. 이미 1단계에서 지도를 다 만들어 뒀기 때문에 2단계는 순식간에 끝납니다.

5. 아티스트와 테크니컬 아티스트(TA)가 알아두면 좋은 점

• 텍스처 해상도 맞추기: 이 알고리즘은 256, 512, 1024 같은 짝수 해상도보다, 끝자리가 1로 끝나는 해상도(257, 513, 1025)를 좋아합니다. 짝수로 떨어지면 반으로 계속 쪼개다 보면 픽셀이 어긋나기 때문입니다. 보통 엔진 내부에서 가장자리 1픽셀을 자동으로 늘려주지만, 개념을 알고 계시면 좋습니다.
• 모든 형태를 다 만들 순 없습니다: 이 방식은 위에서 아래로 내려다보는 높이 맵(Heightmap)을 기반으로 합니다. 따라서 튀어나온 절벽(Overhang)이나 동굴 안쪽 같은 형태는 이 알고리즘으로 처리할 수 없고, 별도의 일반 프랍 메쉬(Static Mesh)로 덧대어 주어야 합니다.

적용 결과 프리뷰

마무리

요약하자면 RTIN(MARTINI) 알고리즘은 지형의 굴곡에 따라 폴리곤을 똑똑하게 분배하고, 골치 아픈 틈새 찢어짐 현상을 원천 차단하며, 카메라 거리에 따른 최적화를 매우 빠르게 처리하는 훌륭한 기법입니다. 모바일이나 오픈월드 게임의 지형을 다룰 때 왜 이런 구조를 사용하는지 이해하신다면, 프로그래머 및 TA 분들과 소통하실 때 훨씬 큰 도움이 될 것입니다!

더 읽어 볼 것들.

• MARTINI 인터랙티브 노트북: observablehq.com/@mourner/martin-real-time-rtin-terrain-mesh — 알고리즘의 시각화가 압권
• 레퍼런스 구현: github.com/mapbox/martini (JS), pymartini (Python/Cython), martini_rtin (Rust)
• RTINI 시리즈: brodieg.com/2020/01/27/mesh-reduction-1/ — 알고리즘의 "왜"와 "어떻게"를 시각적으로 풀어낸 글