티스토리 뷰

개발 노트

전 세계 3D 공간 정보를 관리하는 자료구조 – Implicit Tiling, Z-Order, Bitstream, Subtree 설계/구현

시뮬레이션 프로그래머 2025. 7. 20. 00:52

 
이 글은 3D Tiles Specification – Implicit Tiling (Cesium)을 3D GIS 엔진에 직접 적용하는 과정에서 마주친 문제들을 어떻게 해결했는지에 대한 경험을 정리한 글입니다.
 
깃허브 시각화 링크

들어가기에 앞서

안녕하세요. 이번 글에서는 전 세계 수조 개에 달하는 3D 공간 정보를 어떻게 효율적으로 관리하고 스트리밍할 수 있을까?라는 문제의식에서 출발하여, Implicit Tiling 기반의 공간 데이터 구조에 대해 소개하고자 합니다.
 
기존 3D GIS 엔진은 보통 모델을 '그리는 것'에는 특화되어 있었지만,
정작 그 모델들을 데이터베이스처럼 체계적으로 관리하거나, 위치 기반으로 탐색하는 데에는 한계가 있었습니다.

예를 들어, "서울대입구역 8번 출구 스타벅스"의 정확한 경위도 좌표를 알아야 한다고 가정해 봅시다.
이 정보를 얻기 위한 방식은 크게 두 가지가 있습니다.

  1. 카메라를 직접 해당 위치로 이동해 모델을 클릭하여 메타 정보를 확인하는 방식
  2. 모델 메타 데이터를 별도로 관리하고 질의(Query)하여 직접 검색하는 방식

기존 방식은 1번만 지원했습니다. 왜냐하면 기존에는 3D 모델을 '화면에 잘 그리는 것'에만 초점을 맞추어 설계되어,
3D 모델을 데이터베이스처럼 활용할 수 있는 구조(=인덱스, 조회 체계)가 부재했기 때문입니다.
(기존 방식의 구조는 다음 섹션에서 더 자세히 다룹니다.)
 
결국, 수많은 3D 모델이 '그림'처럼 존재할 뿐,
"이 모델이 어느 지역에 있고, 어떤 유형인지"를 체계적으로 추출하거나 분석하는 것은 불가능했습니다.
 
문제점 요약:

  • 시각 의존성: 데이터를 찾기 위해선 반드시 화면을 통해 모델을 '보고' '클릭'해야 했습니다. 만약 찾아야 할 모델이 수백, 수천만 개라면, 일일이 눈으로 찾아다니는 것은 사실상 불가능에 가깝습니다.
  • 수동 탐색의 한계: 특정 지역의 모든 스타벅스 모델을 찾거나, 특정 종류의 건물을 한꺼번에 분석해야 하는 경우, 일일이 카메라를 움직여 클릭하는 것은 현실성이 없습니다. 이는 자동화된 데이터 분석이나 대규모 공간 질의(쿼리)가 불가능합니다.
  • 데이터의 고립: 모델이 화면에 렌더링되지 않으면, 그 모델의 존재 자체를 데이터 차원에서 알 수 없었습니다. 마치 종이에 그림만 그려져 있고, 그 그림 속 사물의 위치를 지도로 연결해주는 정보가 없는 것과 같았습니다.

 
그래서 저는 다음과 같은 목표를 실현하고자 했습니다.

  • 3D 모델을 정확한 공간 정보 기반으로 탐색/분석 가능한 데이터로 만들자
  • 대규모 3D 모델 데이터를 랜덤 액세스가 가능한 구조로 바꾸자
  • 무엇보다도 전 세계 수십억~수조 개 3D 모델을 효율적으로 관리할 수 있는 자료구조를 설계하자

이번 글에서는 이를 실현하기 위해 어떤 개념(Implicit Tiling, Z-Order, Bitstream, Subtree 등)을 적용했는지,
그 과정에서 어떤 문제에 부딪혔고 어떻게 해결했는지를 사례 중심으로 공유드리겠습니다.

목차

  1. 기존 3D GIS 엔진의 동작 방식과 한계점
    1.1. 기존 3D 엔진 데이터 처리 파이프라인 (Explicit Tiling)
    1.2 Explicit Tiling의 주요 문제점
  2. 개선 방식: Implicit Tiling = '지구를 미리 그리드 분할'과 '모델 배치'
  3. 설계 과정의 고민과 해결: 지구 전체를 하나의 통일된 그리드로
    3.1. 그리드 분할 범위에 대한 고민: 대한민국 vs 동적 범위 vs 지구 전체
    3.2. 타일 식별 방식: {Level},{X},{Y} 구조
    3.3. 정밀도와 성능의 트레이드오프: RTC 좌표계와 쿼드트리 21레벨 분할
  4. 확장성과 정밀함을 선택한 결과: 수조 개의 타일, 그러나 데이터는 희소했다
  5. 수조 개의 타일을 관리하는 방법:  Z-Order 기반 비트맵 자료구조, 서브트리(Subtree)
    5.1. 지구 전체를 1차원 비트맵으로 표현하기: Z-Order와 Availability Bitstream
    5.2. Z-Order 기반 Bitstream의 한계: 지구 전체를 1개의 비트스트림으로 관리할 수는 없다
    5.3. 희소 데이터 관리 방법: 서브트리(Subtree)
  6. 요약
  7. 참고 자료 및 관련 포스팅

1. 기존 3D GIS 엔진의 동작 방식과 한계점: Explicit Tiling의 한계

기존 3D GIS 엔진은 공간 정보를 '그림'처럼 다루며 렌더링에 집중했습니다.

1.1. 기존 3D 엔진 데이터 처리 파이프라인 (Explicit Tiling)

기존 3D 엔진은 다음과 같은 파이프라인을 따릅니다.

 

  1. 텍스처 병합 (Texture Merging): 3D 모델에 사용될 여러 이미지 에셋(asset)을 하나의 이미지 팩으로 병합합니다.
    예시: '서울대입구역 스타벅스' 건물의 벽면, 지붕, 간판 등에 사용될 여러 이미지 파일(예: starbucks_wall.png,
    starbucks_roof.jpg)을 하나의 큰 이미지 파일(starbucks_pack.atlas)로 합치는 과정입니다.

  2. 모델 원점 계산: 하나의 텍스쳐팩을 이루는 이미지들의 레코드를 이용해 텍스쳐팩의 원점과 바운딩 볼륨을 구합니다.

  3. 3D 모델 생성 (Geometry + Texture): 병합된 텍스처와 3D 모델의 기하 정보(Geometry), 위치(경위도, 고도), 크기(바운딩 볼륨) 정보를 결합하여 최종 3D 모델을 생성합니다.
    예시: starbucks_pack.atlas 이미지와 스타벅스 건물의 3차원 형태 정보(정점, 면 등)를 결합하여 '서울대입구역 스타벅스' 3D 모델(starbucks_seoul_building.gltf 또는 .b3dm 등)을 생성합니다.
    이 모델은 지구상의 특정 X, Y, Z 좌표(예: 위도 37.481, 경도 126.953, 고도 50m)에 위치하며, 건물의 가로·세로·높이(Bounding Volume) 등의 정보도 함께 가집니다.

  4. 타일셋 JSON 파일 생성 (explicit_tileset.json): 생성된 3D 모델들은공간적 분포(위치, 바운딩 볼륨)를 기준으로 쿼드트리(Quadtree) 또는 옥트리(Octree) 형태의 explicit_tileset.json 파일을 생성합니다. 이 파일의 각 노드는 특정 공간 영역을 담당하며, 해당 영역에 포함된 3D 모델들의 메타 정보(파일 경로, 바운딩 볼륨 등)를 명시적으로(Explicitly) 기록합니다.
  • explicit_tileset.json의 역할: 존재하는 3D 모델들의 바운딩 볼륨을 기준으로 공간을 재귀적으로 분할하고, 각 분할된 공간(타일)에 어떤 3D 모델이 있는지와 해당 모델의 파일 경로 및 최소한의 공간 정보(바운딩 볼륨) 를 기록하는 '모델 중심의 공간 지도' 역할을 합니다.
    즉, 클라이언트(웹 브라우저 등)는 이 tileset.json 파일을 기반으로 현재 카메라 뷰에 맞는 타일을 탐색하고, 필요한 3D 모델 데이터를 로드합니다. 특히, 이 타일셋의 루트 노드는 모든 3D 모델을 포함하는 최소 바운딩 박스를 기준으로 설정됩니다.
    예를 들어, 모델이 관악구에만 존재할 경우, 루트는 해당 관악구만 포함하는 바운딩 박스가 될 수 있습니다.
  • explicit_tileset.json 예시:
{
  "root": {
    "boundingVolume": { "region": "[관악구]" },
    "children": [
      { // 레벨 1: 신림동/봉천동 등
        "boundingVolume": { "region": "[신림동/봉천동 등 동 단위]" },
        "children": [
          { // 레벨 2: 특정 블록/구역
            "boundingVolume": { "region": "[특정 블록/구역]" },
            "children": [
              { // 레벨 3: 서울대입구역 8번 출구 스타벅스 모델
                "content": { "uri": "models/seouldae_starbucks.b3dm" },
                "boundingVolume": { "region": "[126.945, 37.475, 126.965, 37.490, 0, 200]" }
              }
            ]
          }
        ]
      }
    ]
  }
}

 
이렇게 JSON 파일에 분할 된 각각의 공간을 하나의 '타일'이라고 합니다.

타일(Tiles)이란? 
타일은 공간을 규칙적으로 잘게 나눈 최소 단위의 사각형 또는 입체 그리드입니다.
3D GIS 엔진에서는 공간 데이터를 효율적으로 관리하기 위해 지구를 일정한 크기의 타일(그리드 셀)로 쪼갭니다.

2차원 타일: 경도, 위도 (x, y)
3차원 타일: 경도, 위도, 고도 (x, y, z)

각 타일은  어떤 3D 모델이 이 공간에 존재하는지를 알 수 있는 기준점이 됩니다.
타일을 2차원으로 표현하면 쿼드트리, 3차원으로 표현하면 옥트리로 구현할 수 있습니다.

 

1.2 Explicit Tiling의 주요 문제점

이러한 Explicit Tiling의 Tileset.Json은 다음과 같은 치명적인 한계와 문제점들을 내포하고 있었습니다.

1) 데이터의 비구조성

tileset.json에 저장된 데이터는 '어디에 그림을 그릴지'만 알려주는 단순한 참조 정보였습니다. 각 3D 모델은 개별적인 메타 정보를 가졌지만, 이를 활용하여 다른 모델과의 관계성을 파악하거나 복합적인 공간 분석을 수행하는 것은 사실상 불가능했습니다.

  • 예시: '특정 건물로부터 반경 100m 이내의 모든 편의점 찾기'와 같은 공간 분석이 불가능한 구조

2) 비효율적인 강제 순차 탐색 (랜덤 액세스 불가)

[ 루트 (관악구) ]
        │
        ▼
[ 레벨 1: 신림동/봉천동 등 ]
        │
        ▼
[ 레벨 2: 특정 블록/구역 ]
        │
        ▼
[ 레벨 3: 서울대입구역 8번 출구 스타벅스 모델 ]

사용자의 카메라 뷰가 1cm만 움직이거나 각도를 조금만 돌려도, 웹 브라우저의 JS 엔진은 tileset.json 파일의 쿼드트리 최상위 루트부터 매번 반복적으로 순차 탐색을 시작해야 합니다. 이는 파일 시스템 기반의 계층적 탐색을 의미하며, 원하는 정보에 랜덤 접근을 하고 싶어도 구조상 강제로 순차 접근이 이루어지게 하여, 탐색 속도와 렌더링 성능 모두를 저하시켰습니다.

  • 예시: 서울대입구역 스타벅스 모델을 찾기 위해 tileset.json의 루트부터 시작하여 관련된 자식 JSON 파일들을 네트워크를 통해 순차적으로 다운로드하고 파싱하며 (위 예시에서는 '대한민국 전체' → '서울 지역' → '관악구' → '신림동/봉천동 등 동 단위' → '특정 블록/구역' 등으로 이어지는 JSON 파일들의 탐색), 원하는 모델이 포함된 최하위 JSON 파일에 도달해야 했습니다.
    이처럼 계층이 깊어질수록 불필요한 네트워크 통신과 파싱 오버헤드가 기하급수적으로 증가했습니다.

3) 부분 수정 불가능

전국 또는 특정 대규모 지역의 데이터를 한 번 빌드하는 데만 수십 시간이 소요되었으며, 모델 개수가 많아질수록 빌드 시간은 선형 또는 그 이상으로 증가했습니다. 완성된 결과물은 수백 GB에서 최대 1TB에 달하는 대용량 파일로 생성되고, 배포 및 저장 과정에서도 상당한 시간과 비용이 발생합니다.

  • 하지만 서울대입구역 스타벅스 건물 하나만 수정하더라도 관련 JSON 파일 및 모델 데이터를 처음부터 전부 다시 빌드하고 재배포해야 했습니다. 특정 이미지 텍스처에 오류가 발생해도 해당 부분만 수정하여 재배포하는 것이 불가능했으며, 문제가 발생할 때마다 전체 재빌드가 강제되었습니다. (혹은 수정한 부분을 사람이 수동적으로 수정)

결과적으로 데이터 유지보수, 오류 수정, 신규 데이터 반영 속도가 극도로 저하되는 비효율적인 구조였습니다.
 

Explicit Tiling 문제점 정리

문제 구분 상세 내용
데이터의 비구조성 - explicit_tileset.json은 '어디에 그림을 그릴지'만 저장하는 참조 정보에 불과
- 각 3D 모델은 자신의 위치·크기 정보는 가지고 있으나, 다른 모델과의 공간적 연관성이나 관계를 활용할 수 없는 구조
- 공간 관계 분석 불가 (예: 반경 100m 내 편의점 찾기 불가능)
- 속성 기반 검색 불가 (예: '스타벅스' 또는 '이름이 바나나로 시작하는 건물' 검색 불가)
비효율적 탐색 - 카메라 뷰가 1cm만 이동해도 매번 쿼드트리 최상위 루트부터 순차 탐색 필요
- 탐색 경로 과도한 중복 (지구 → 아시아 북동부 → 동아시아 → 대한민국 → 서울 → 관악구 → 건물 위치)
- 랜덤 접근 불가, 매번 쿼드트리 루트부터 순차 탐색으로인한 속도·렌더링 성능 저하
부분 수정 불가능 - 전국 데이터를 전체 재빌드해야만 수정 반영 가능
- 부분 빌드, 부분 교체, 부분 재배포 불가
- 빌드 소요 시간: 수십 시간
- 빌드 파일 크기: 수백 GB ~ 1TB
- 데이터 유지보수, 오류 수정, 신규 반영 속도 극심하게 저하

 

2. 개선 방식: Implicit Tiling = '지구를 미리 그리드 분할'과 '모델 배치'

Implcit Tiling 시각화 코드

 
기존 3D GIS 엔진은 3D 공간 데이터를 3D 모델로 만든 후, 해당 모델들의 정보(Geometry + Bounding Volume)를 가지고 일정한 사이즈(예: 100m) 단위로 묶어 쿼드트리 JSON 파일에 명시적으로 저장하고 탐색하는 구조였습니다.
 
예를 들어, "특정 지역을 기준으로 1km 이내에 존재하는 카페"를 찾으려면 어땠을까요? 기존 방식은 100m 단위로 분할된 쿼드트리에서 시작해, 그 조상 노드인 400m, 1600m 레벨 등을 거쳐야 했습니다. 결국 1km 반경 내의 모든 타일을 찾아내기 위해, 1600m 쿼드로 분할된 자식들 중 1000m보다 작은 모든 타일을 일일이 탐색하고 그 안에 있는 모델들을 확인해야 하는 비효율적인 과정을 거쳤습니다. 이는 넓은 지역을 검색할수록 기하급수적으로 탐색해야 할 타일과 JSON 파일의 수가 늘어나는 문제로 이어졌습니다.
 
이러한 한계를 극복하기 위해 저는 Z-Order 기반의 1차원 데이터 정렬과 비트맵 자료구조를 설계하고 구현했습니다.

(좌): 기존 방식 (Explicit Tiling), (우): 개선된 방식 (Implicit Tiling)

가장 큰 변화는 데이터를 다루는 방식에 있습니다.

  • 기존 방식 (Explicit Tiling): 모델들이 먼저 존재하고, 그 모델들의 바운딩 볼륨(모델이 차지하는 공간)을 기준으로 100m(Leaf Tile, 이후에는 쿼드트리로 병합되므로 200x200, 400x400, 800x800m 와 같은 형태의 그리드로 병합됨)와 같은 특정 크기의 구역(타일)들을 임의로 만들고, 해당하는 구역(타일)에 모델들을 병합하여 배치했습니다. 즉, 데이터가 먼저 생성된 후에 그 데이터에 맞춰 지도를 만드는 개념입니다.
  • 개선 방식 (Implicit Tiling): 3D 모델 데이터를 기반으로 JSON 파일을 만드는 것이 아니라, 먼저 지구(또는 한국) 전체를 바둑판처럼 균일한 그리드 형태로 분할합니다. 그리고 3D 모델이 생성되면, 그 모델의 경위도(위도, 경도) 좌표를 가지고 미리 정의된 그리드(타일)에 3D 모델을 배치하는 방식입니다. 이는 지도가 먼저 만들어진 후 데이터가 그 지도 안으로 들어가는 개념입니다.

이렇게 미리 규칙을 정의해 놓았기 때문에, 특정 3D 모델의 경위도(위도, 경도)와 고도를 이 규칙에 적용하면 해당 모델이 어떤 타일에 속해 있는지 즉시 알아낼 수 있습니다

구분 기존 방식 (Explicit Tiling) 개선 방식 (Implicit Tiling)
타일 생성 방식 모델 바운딩 박스 기준 동적 생성 지구 전체 균일 분할
데이터 배치 데이터 생성 후 타일에 병합 미리 정의된 타일에 자동 배치
구조 특징 데이터(3D 모델)에 맞춰 지도(타일)를 만든다 지도(타일)에 데이터(3D 모델)를 배치한다

 

3. 설계 과정의 고민과 해결: 지구 전체를 하나의 통일된 그리드로

3D 공간 데이터를 단순히 '그림'에서 '데이터'로 전환하기 위한 새로운 구조를 설계하면서, 가장 먼저 마주한 근본적인 고민은 '공간을 어떻게 효율적이고 확장성 있게 분할할 것인가?' 였습니다.
대한민국만 분할할 것인가, 아시아 지역만 분할할 것인가, 아니면 지구 전체를 분할할 것인가?
그리고 몇 미터 단위까지 세분화할 것인가?

 

3.1. 그리드 분할 범위에 대한 고민: 대한민국 vs. 지구 전체 vs. 동적 범위

대한민국부터 그리드 분할 (6레벨 부터 분할) / 3D 모델이 있는 지역만 동적 그리드 분할 (3D 모델이 있는 특정 지역 분할) / 지구 전체를 그리드 분할

  • 선택지 1: 대한민국부터 그리드로 분할하는 경우
    • 장점: 초기 연산량이 적고, 트리의 깊이(depth)가 상대적으로 얕아집니다.
    • 단점: 하지만 이는 확장성 문제를 야기합니다. 만약 프로젝트 범위가 대한민국을 넘어 사우디아라비아의 네옴시티처럼 광범위한 지역이나 전 세계로 확장된다면, 기존 시스템을 처음부터 재설계하거나 여러 개의 독립적인 시스템을 관리해야 하는 비효율이 발생합니다.
  • 선택지 2: 3D 모델이 있는 특정 지역만 동적으로 그리드로 분할하는 경우
    • 장점: 필요한 지역만 효율적으로 관리할 수 있어 불필요한 연산을 줄일 수 있습니다.
    • 단점: 여러 지역을 동시에 다루거나, 지역 간의 연속적인 데이터 흐름이 필요한 경우, 각 동적 범위 간의 경계면 처리가 복잡해지고 통합적인 공간 관리가 어렵습니다. 결국 여러 개의 독립적인 그리드를 관리해야 하는 문제에 직면할 수 있습니다.
  • 선택지 3: 지구 전체를 그리드로 분할하는 경우
    • 장점: 이전의 선택지보다 훨씬 좋은 확장성을 제공합니다. 어떤 지역의 데이터가 추가되더라도 유연하게 통합 관리할 수 있으며, 글로벌 서비스로의 발전 가능성을 열어줍니다.
    • 단점 (우려): 부동소수점(Floating-point) 연산 오차. 지구 전체를 커버하는 매우 정밀한 좌표를 다룰 때 부동소수점 연산에서 정밀도 손실이 발생할 수 있다는 우려가 있었습니다. 지구의 모든 좌표를 하나의 절대적인 원점에서 계산하면 미세한 오차가 누적되어 정밀도에 문제가 생길 수 있기 때문입니다.

      지구를 다룰 때의 부동 소수점 연산 오차와 관련된 내용은 다음 글에서 확인할 수 있습니다.
      [블로그] 지구를 부동 소수점으로 표현하는 방법

최종적으로 미래의 확장성과 데이터의 범용성을 최우선으로 고려하여, 지구 전체를 하나의 통일된 그리드로 분할하는 방식을 선택했습니다.
(부동 소수점 연산 오차에 대한 해결 방식도 있었습니다. > RTC Center 아래에서 설명)

3.2. 타일 식별 방식: {Level},{X},{Y} 구조

지구를 쿼드트리 형태로 분할했다면, 이제 각 타일을 어떻게 유일하게 식별할 것인가가 중요해집니다. 각 타일을 {Level},{X},{Y} 형태로 정의하여 사용합니다.

  • Level (레벨): 쿼드트리의 깊이를 나타냅니다. 레벨 0은 지구 전체를 의미하고, 레벨이 깊어질수록 타일의 크기는 작아지고 그 수는 4^{level} 형태로 늘어납니다 (예: 레벨 1은 4개의 타일, 레벨 2는 16개의 타일).
    옥트리인 경우에는 8^{level} 형태 (예: 레벨1은 8개의 타일, 레벨2는 64개의 타일)
  • X (경도 인덱스): 해당 레벨 타일 그리드에서 가로(경도) 방향 위치를 나타내는 인덱스입니다.
  • Y (위도 인덱스): 해당 레벨 타일 그리드에서  세로(위도) 방향 위치를 나타내는 인덱스입니다.

예시: {0}.{0}.{0}은 지구 전체를 의미하는 최상위 타일이며, {1}.{0}.{0}은 레벨 1의 특정 사분면 타일을, {20}.{1234567}.{7654321}은 지구상에서 매우 작고 특정적인 30cm~60cm 크기의 타일을 고유하게 지칭합니다.
이렇게 미리 정의된 {Level},{X},{Y} 규칙을 이용하면, 어떤 3D 모델의 경위도(위도, 경도)와 고도 좌표만 주어지면 해당 모델이 어떤 레벨에서 어떤 타일에 속해 있는지 즉시 알아낼 수 있습니다.

예시

  • 레벨이 15인 경우: 15.123.456
  • 레벨이 16인경우: 16.245.912
  • 레벨이 0인 경우: 0.0.0

 
이는 기존 explicit_tileset.json처럼 모델 데이터를 만들고나서 타일을 정의하는 것과는 달리
타일이 모델보다 먼저 존재하고, 그 타일 안으로 모델을 배치하는 개념이기 때문입니다.

3.3. 정밀도와 성능의 균형: RTC 좌표계와 21레벨 분할

지구 전체를 단일 그리드로 분할하는 방식은 확장성이라는 장점을 가져다주었지만,
동시에 부동소수점 정밀도 문제와 깊어진 쿼드트리 구조에 따른 성능 저하라는 두 가지 중요한 기술적 난관이 있었습니다.
이 문제를 다음과 같은 방식으로 해결했습니다.

3.3.1. 부동소수점 정밀도 문제 해결: RTC (Relative to Center) 중심 좌표계 적용

  • 문제: 컴퓨터에서 부동소수점(float, double)으로 지구 전체를 19m 수준의 정밀한 위치까지 다루려 하면 정밀도 손실(precision loss)이 발생합니다. 특히 이는 렌더링 시 떨림 현상인 지터링(jittering)이나 3D 모델의 위치가 부정확하게 배치될 수 있습니다.
    • 일반적으로 double(64비트)은 float(32비트)보다 훨씬 높은 정밀도를 제공하지만, GPU 연산에서는 float가 압도적으로 유리합니다. float는 double보다 더 적은 메모리를 사용하고, GPU는 병렬 처리에 최적화되어 있어 float 연산이 훨씬 빠릅니다. 따라서 3D 그래픽스에서는 가능한 한 float를 사용하는 것이 성능에 이롭습니다. 하지만 float로는 지구 전체의 광범위한 영역과 미세한 정밀도를 동시에 만족시키기 어렵습니다.
      (실제로 AI 모델을 학습시킬때도 32비트 float을 넘어 24, 16, 8, 2 비트 등으로 최소화하고 양자화 하는것에 많은 노력을 기울이는 것으로 알고 있습니다.)
  • 해결책: RTC (Relative to Center) 중심 좌표계 적용: 이 문제를 극복하기 위해, RTC (Relative to Center) 중심 좌표계 개념을 적용했습니다. 이는 지구의 절대적인 원점(0,0,0)을 기준으로 모든 좌표를 계산하는게 아니라, 현재 카메라가 보고 있는 지역이나 특정 3D 모델의 중심점을 '가상적인 원점'으로 설정하여 모든 주변 좌표를 상대적으로 표현하는 방식입니다.
    • 이를 통해 지구 전체 규모의 좌표를 다루면서도, 카메라 주변의 좁은 공간 내에서는 상대 좌표를 사용하여 float 연산만으로도 높은 정밀도를 유지할 수 있었습니다. 이는 GPU 연산 효율을 극대화하면서도 정밀도 손실을 최소화할 수 있었습니다.

 

3.3.2. 그리드 분할 깊이 결정: 왜 21레벨인가?

RTC 좌표계로 정밀도 문제를 해결한 뒤, 이 그리드를 얼마나 세분화할 것인가를 고민했고, 지구를 최대 21레벨 깊이의 쿼드트리로 분할하기로 결정했습니다.
 

21레벨의 정밀도

21레벨은 지구의 둘레(적도)를 2^20으로 분할하는 것에 해당하며, 지구상에서 타일 크기가 약 가로 38m, 세로 19m 정밀
한 단위까지 공간을 쪼갤 수 있음을 의미합니다.

 
왜 가로는 38m, 세로는 19m로 서로 다른가?

지구 가로:세로 비율 = 2:1

세계 지도에서 타원체 지구(경도 -180~180도, 위도 -90~90도)를 정각도법으로 나누었을때 가로:세로 비율이 2:1 입니다.
그래서 사실 0레벨 타일은 1x1 그리드 형태가 아니라 2x1 그리드 입니다.
 
아래 이미지를 봤을때도 타일의 가로, 세로 크기가 다른 것을 볼 수 있다. (이미지 가로/세로 뒤집어짐)

(21레벨 에서의 타일 크기를 보여줌.)

  • 왜 이렇게까지 세분화했는가?
    • 추후 공간정보 버전관리 시스템 구축 계획: 이 프로젝트가 완료된 후, 공간정보 버전관리 시스템을 구축할 계획이 있었습니다. 타일의 크기가 작을수록, 데이터 변경이 발생했을 때 변경된 부분만 더 세밀하게 탐지하고 관리하며 재배포할 수 있기 때문입니다.
    • 정밀한 데이터 표현: 대부분의 고정밀 3D 공간 모델 데이터(예: BIM, 자율주행을 위한 HD맵)가 요구하는 정밀도를 만족시키면서도, 향후 더 미세한 단위의 데이터(예: 드론 촬영 데이터, 실내 3D 모델)가 추가되더라도 대응할 수 있는 충분한 확장성을 확보하고자 했습니다.
    • 서브트리 레벨과 나누어 떨어지도록: 해당 내용은 뒤에서 다루므로 무시하고 넘어가면 됩니다.

4. 확장성과 정밀함을 선택한 결과: 수조 개의 타일, 그러나 데이터는 희소했다

전국 단위의 3D 모델 데이터를 고정밀로 다루기 위해 지구 전체를 기준으로 최대 21레벨까지 쿼드트리로 분할하는 방식을 선택했습니다. 이 선택은 타일 하나의 공간 범위를 약 19m~38m 수준까지 좁혀, 정밀한 위치 기반의 데이터 관리 및 렌더링을 가능하게 해주었습니다.
 
하지만 이 구조는 쿼드트리 특성상 레벨이 하나 증가할 때마다 타일 수가 4배씩 증가하기 때문에, 20레벨까지 구성할 경우 이론상 지구 전역에 4²⁰ ≈ 1.1조 개의 타일이 존재할 수 있습니다.

대한민국은 지구 면적의 약 0.07%에 불과하므로, 대한민국 기준으로만 봐도 약 7억 7천만 개 이상의 타일이 생성될 수 있습니다.
여기에 LOD(레벨 오브 디테일) 3단계를 적용하면, 최대 12억 개의 타일 콘텐츠 요청이 발생할 수 있습니다.

 

문제: 희소 데이터인데, 타일 요청은 전 영역에 무작정 발생한다 (브로드캐스트)

누군가는 이렇게 생각할 수 있습니다.

"어차피 {level}.{x}.{y}로 타일 위치를 계산해서 요청하면 되는 거 아닌가요?"

 
그러나 이 방식에는 희소 데이터 환경에서 치명적인 비효율이 존재합니다.

  1. 지구 전체를 분할했지만, 실제 3D 모델은 대한민국에만 존재합니다.
  2. 그럼에도 불구하고 렌더링 엔진은 매번 카메라 위치에 따라 타일을 계산하고 {level}.{x}.{y}에 해당하는 3D 모델 요청을 서버에 보냅니다.
  3. 해당 타일에 3D 모델이 있는지 없는지를 서버에 물어보기 전까진 알 수 없습니다.

예시

좌: 한반도 (타일 7레벨), 우: 서울 송파 (타일 20레벨)

예를 들어, 3D 모델이 오직 ‘남한’ 지역에만 존재하고, ‘북한’에는 아무런 데이터가 없다고 가정해봅시다.
하지만 클라이언트는 이런 콘텐츠의 유무를 알 수 없기 때문에, 사용자가 한반도 전체를 바라보는 순간, 남한뿐만 아니라 북한까지 포함한 {level}.{x}.{y}.glb 요청을 모두 서버에 보냅니다.
 
즉, 북한에는 아무 데이터도 없지만, 클라이언트는 서버에 계속해서

“혹시 이 타일에도 모델이 있나요?” 라고 쓸모없는 요청을 반복해서 보내는 상황이 발생하는 것입니다.

 
특히 타일 레벨이 낮은(예: 7레벨) 경우에는 타일 개수가 적어 낭비가 제한적일 수 있지만, 20레벨처럼 타일이 매우 세밀하게 나뉘는 경우, 요청해야 할 타일 수는 기하급수적으로 증가하며, 낭비되는 요청도 그만큼 많아집니다.
 
결과적으로 다음과 같은 문제가 생깁니다.

  • 불필요한 요청 증가 (존재하지 않는 모델에도 요청)
  • 디스크 접근, 네트워크 비용 증가
  • 응답 지연 → 사용자 경험 저하

 

해결책: 타일 존재 여부를 미리 아는 구조

  • 희소한 데이터 환경에서도 유효한 타일만 빠르게 식별할 수 있는 구조
    →  즉, 존재 여부를 미리 알 수 있으면 불필요한 요청 자체를 사전에 차단할 수 있습니다.

다음 장에서는 이 문제를 해결하기 위해 도입한 Z-Order 기반의 비트맵 자료구조와 Subtree 개념을 설명하겠습니다.

5. 수조 개의 타일을 관리하는 방법:  Z-Order 기반 비트맵 자료구조, 서브트리

지구 전체를 21레벨 쿼드트리로 분할한 결과, 총 수조 개에 달하는 타일이 생성되었습니다.
하지만 실제로 콘텐츠가 존재하는 타일은 대한민국 면적에 해당하는 약 12억 개(LOD 3단계 기준) 에 불과했습니다.
 
즉, 대부분의 타일은 비어 있고, 필요한 타일만 빠르게 식별할 수 있는 방법이 필요했습니다.
 
이 문제를 해결하기 위해 Z-Order, Bitstream과 서브트리(Subtree) 개념을 도입했습니다.
 

5.1. 지구 전체를 1차원 비트맵으로 표현하기: Z-Order와 Availability Bitstream

수십억 개의 타일의 존재 여부를 효율적으로 저장하고 탐색하기 위해서는,
2차원(쿼드트리의 X, Y 좌표) 또는 3차원(옥트리의 X, Y, Z 좌표) 공간 정보를 1차원 배열에 매핑하는 방법이 필요했습니다.

 
예를 들어 4×4 그리드(2레벨 쿼드트리)를 생각해봅시다.
16개의 타일 중 단 하나인 (2, 1)에만 콘텐츠가 존재한다고 해도, 이 위치를 단순한 2D 배열로 저장하면 공간적 지역성을 활용하기 어렵고,
전체 타일의 존재 여부를 빠르게 조회하거나 압축해 저장하기에도 비효율적입니다.  

그래서 2차원 좌표를 1차원 좌표로 변환하기 위해 적용한 개념이 Z-Order Curve입니다.
(Z-Order 개념에 대한 상세 내용은 [Z-Order  개념 포스팅]에서 확인하실 수 있습니다.)

Z-Order [0, 3] 레벨 그리드

Z-Order Curve는 2차원 좌표 (x, y)를 비트 인터리빙(Bit Interleaving) 방식으로 섞어 1차원 순서로 변환하는 방식이며, 이때 생성된 인덱스를 Morton Order라고 합니다.
 
예: 좌표 (4, 1)의 Morton Order 구하기

  • (x=4, y=1)
  • Binary: x=100, y=001
  • Interleaved: y2 x2 y1 x1 y0 x0 = 0 1 0 0 1 0 → 010010 → Morton Order = 18

 
Z-Order 개념을 지구 전체 그리드 분할에 대입 예시

  • 0레벨 (1×1 그리드): 지구 전체
  • 1레벨 (2×2 그리드): 4개 구역으로 분할
  • 2레벨 (4×4 그리드): 16개 타일
  • 3레벨 (8×8 그리드): 64개 타일

 

부모-자식 관계 추적 방법

8x8 그리드에서 Morton Order: 18 (좌표: 4, 1)을 확인해주세요. 이 부분은 각 그리드에서

  • 4x4 그리드에서의 Morton Order: 4 (좌표: 2, 0)
  • 2x2 그리드에서의Morton Order: 1 (좌표: 1, 0)
  • 1x1  그리드에서의 Morton Order: 0 (좌표: 0, 0)

를 의미합니다. 관계가 보이나요? 자식 타일 좌표를 2로 나누면 부모 타일의 좌표를 알 수 있습니다.
 

실제 콘텐츠가 존재하는 타일을 Morton Order로 변경하여 Bitstream으로 나타내보겠습니다.

순서대로 2, 1, 0 레벨의 타일 집합

이제 실제 콘텐츠가 존재하는 타일을 Morton Order로 변환하여 Bitstream으로 나타내는 방법을 살펴보겠습니다.
여기서 초록색 타일은 실제 콘텐츠(예: 3D 모델)가 있는 리프 레벨 타일을,
주황색 타일은 해당 타일 자체에 콘텐츠는 없지만, 그 자식 또는 더 깊은 자식들이 콘텐츠를 가지고 있어 클라이언트가 더 깊게 탐색해야 하는 중간 노드 타일(인덱스 용)을 의미합니다.
 
가장 상세한 레벨(리프 레벨)이 2레벨 그리드라고 가정하고, 2레벨 그리드의 좌표 (2, 1)에만 콘텐츠가 존재한다고 해봅시다.

  1. 콘텐츠 가용성 (Content Availability) Bitstream: 이 비트스트림은 각 타일 자체에 실제 콘텐츠가 존재하는지 여부를 나타냅니다.
    • 2레벨 그리드에서 좌표 (2, 1) 타일에만 콘텐츠가 존재합니다. 즉 2레벨 (2, 1)좌표 Morton Order = 6 위치에 1을 마킹합니다.
    • 예시 (2, 1) 타일만 콘텐츠가 있을 경우:
      • 0레벨: 0
      • 1레벨 : 0000
      • 2레벨: Morton Order 6 (좌표 2,1)에 콘텐츠가 있으므로 0000 0010 0000 0000
    • 결과 Bitstream (콘텐츠 가용성): 0 / 0000 / 0000 0010 0000 0000 (레벨별로 구분)
  2. 타일 가용성 (Tile Availability) Bitstream: 이 비트스트림은 해당 타일 또는 그 자식(더 깊은 레벨의 자식 포함)에 실제 콘텐츠가 존재하여 탐색을 계속해야 하는지 여부를 나타냅니다.
    • 2레벨 그리드의 (2, 1) 타일에 콘텐츠가 있으므로, 이 타일 자체는 '탐색 필요'로 마킹됩니다.
    • 1레벨 그리드에서 (2, 1) 타일의 부모인 (1, 0) 타일은 자식에 콘텐츠가 있으므로 '탐색 필요'로 마킹됩니다.
    • 0레벨 그리드에서 (1, 0) 타일의 부모인 (0, 0) 타일은 자식의 자식에 콘텐츠가 있으므로 '탐색 필요'로 마킹됩니다.
    • 예시 (콘텐츠가 2레벨 (2,1)에만 있을 경우):
      • 0레벨: Morton Order 0 (좌표 0,0)에 자식이 있으므로 1
      • 1레벨: Morton Order 1 (좌표 1,0)에 자식이 있으므로 0100
      • 2레벨: Morton Order 6 (좌표 2,1)에 콘텐츠가 있으므로 0000 0010 0000 0000
    • 결과 Bitstream (타일 가용성): 1 / 0100 / 0000 0010 0000 0000 (레벨별로 구분)

❗ Morton Order 주의점: 계층 누적 오프셋

여기서 주의해야 할 점이 하나 있습니다.
Morton Order 는 레벨별로 독립적으로 계산되지만, Bitstream에서는 모든 레벨의 정보를 하나의 배열에 누적하여 저장합니다.
예를 들어, 2레벨 타일 (2,1)의 Morton Order가 6이라고 하더라도,
Bitstream 상에서의 실제 위치는 0~1레벨에 해당하는 인덱스 총합 이후입니다.

 

레벨 타일 수 4^{Level} 누적 인덱스 범위
0 1 [0]
1 4 [1–4]
2 16 [5–20]
 

즉, 레벨 2의 Morton Order 6은 Bitstream 전체 기준으로 보면 5 (1+4) + 6 = 11입니다.

따라서 각 레벨의 Morton Order를 Bitstream에 직접 사용하는 것이 아니라,
이전 레벨의 타일 개수를 누적한 오프셋 값을 더해서 실제 인덱스를 계산해야 합니다.

 
 

비트스트림을 통한 효율적인 탐색

앞서 설명한 것처럼, Morton Order와 Bitstream을 활용하면 클라이언트는 1차원 비트맵 상의 값을 기준으로 다음과 같은 방식으로 타일 탐색을 수행할 수 있습니다.

  • 타일 가용성 (Tile Availability)
    어떤 비트가 1로 설정되어 있지만 해당 타일에는 콘텐츠가 없다면, 이는 해당 타일의 하위 자식들 중에 콘텐츠가 존재함을 의미합니다.
    이 경우 클라이언트는 해당 타일의 자식 노드들을 더 깊이 탐색하며, 다음 레벨의 타일/콘텐츠 가용성 정보를 기반으로 다시 판단을 이어갑니다.
  • 콘텐츠 가용성 (Content Availability)
    Bitstream 상에서 1로 표시된 위치는 해당 Morton Order에 콘텐츠가 존재함을 의미합니다.
    클라이언트는 이 값을 다시 (level, x, y) 좌표로 디코딩한 뒤, level.x.y.glb와 같은 실제 콘텐츠 파일을 서버에 요청하여 렌더링합니다.

 

필요한 타일만 빠르게 식별할 수 있는 구조 

 

  • 타일 존재 여부의 효율적인 관리
    → 방대한 수의 타일 중 타일/콘텐츠가 존재하는 타일만 Bitstream에 마킹함으로써, 클라이언트가 불필요한 요청을 미리 차단할 수 있도록 합니다.
  • 상하위 관계 기반의 정밀 탐색 흐름 구성
    → 콘텐츠가 존재하는 리프 타일로부터 상위 타일까지 존재 여부가 전파되기 때문에, 클라이언트는 탐색 중간 단계에서도 더 깊이 들어갈지 말지를 정확히 판단할 수 있습니다.

 
 

5.2. Z-Order 기반 Bitstream의 한계: 지구 전체를 1개의 비트스트림으로 관리할 수는 없다

Z-Order 기반 Bitstream 구조는, 타일의 존재 여부를 비트 단위로 마킹하여 클라이언트가 실제로 존재하는 타일만 선택적으로 요청할 수 있도록 만든 효율적인 구조입니다.
 
하지만, 여전히 지구 전체 범위를 하나의 Bitstream으로 표현하려 할 경우 다음과 같은 한계에 부딪히게 됩니다.
 

지구 전체 타일 수 계산 (쿼드트리 깊이 21 기준)

지구 전체를 기준으로 레벨 0부터 20레벨 (리프 레벨)까지 모든 타일을 하나의 Bitstream으로 표현하려 할 경우,

  • a (초항) = 1 (레벨 0의 타일 수)
  • r (공비) = 4 (쿼드트리이므로 각 레벨에서 타일 수가 4배 증가)
  • n (항의 개수) = 21 (0부터 20레벨까지 총 21개)

등비수열의 합 공식에 대입하면

 
즉, 쿼드트리 기준으로 레벨 0~20까지 모든 타일을 Morton Order 기반 Bitstream으로 관리하면 약 1.47조 비트(=183GB)가 필요합니다.  (타일, 콘텐츠 가용성 2개 이므로 183 + 183 = 약 366 GB)

 

희소한 실제 데이터, 그러나 전체 공간은 낭비된다

현실적으로 우리가 관리하는 3D 모델 데이터는 대한민국(지구의 약 0.07%)에만 존재합니다.
즉, 전체 타일 중 대부분은 콘텐츠가 없는 '0' 비트이며, Bitstream의 거의 모든 공간이 불필요한 데이터로 채워지게 됩니다.
이러한 구조는 단순히 메모리 낭비에 그치지 않고

  • 비트스트림 전체를 로딩하거나 전송하는 데 과도한 I/O 비용이 발생하고, (366 GB)
  • 특정 타일을 조회할 때도 전체 배열 범위 안에서 인덱싱해야 하기 때문에 탐색 성능이 크게 저하됩니다. (1.47조 비트 탐색)

 

해결 방향: 필요한 범위만 나눠서 관리한다

이러한 구조적 비효율을 해결하기 위해, 다음 섹션에서는 Bitstream을 하나의 거대한 배열로 관리하지 않고,
쿼드트리 기준으로 일정 단위로 분할하여 관리하는 서브트리(Subtree) 구조를 도입합니다.
 

Subtree는 "특정 타일 영역 단위로 Bitstream을 나누고 필요한 단위만 클라이언트가 요청하는 방식"이며,
이를 통해 메모리 사용을 최소화하고, I/O 및 탐색 범위를 대폭 축소할 수 있게 됩니다.

 

5.3. 희소 데이터 관리 방법: 서브트리(Subtree)

비트스트림은 지구 전체 다차원 타일을 1차원으로 공간 인덱싱 했지만, 지구 전체를 커버하는 거대한 비트맵은 대부분 '0'으로 채워져 메모리를 낭비하고, I/O 및 탐색 성능을 저하시킵니다. 이를 해결하기 위해, 비트스트림을 더 작은 단위의 서브트리(Subtree)로 추상화하여 관리했습니다.
 

서브트리: 거대한 트리를 작은 조각으로 분할

서브트리

서브트리 개념은 전체 쿼드트리(또는 옥트리) 구조를 특정 레벨에서 작은 단위의 하위 트리들로 쪼개어 관리하는 방식입니다.
예시: 전체 21레벨 타일을 7레벨 단위로 분할하여 [0, 7), [7, 14), [14, 21) 레벨 단위로 트리를 분할하여 관리하는 방식
 
이처럼 레벨을 잘라낸 조각들이 각각 독립적으로 타일/콘텐츠/자식 서브트리 존재 여부를 비트스트림으로 관리하는 구조입니다.

  1. 계층적 비트스트림 구조: 서브트리는 전체 타일셋의 루트에서 시작하는 하나의 거대한 비트스트림 대신, 상위 레벨의 서브트리가 존재 여부를 나타내는 비트스트림을 가지고, 그 하위 레벨의 서브트리들이 다시 자신들의 영역 내 타일 존재 여부를 나타내는 비트스트림을 가지는 계층적 구조를 이룹니다.
  2. 효율적인 저장 및 전송: 이 방식의 핵심은 실제 데이터가 존재하는 부분(타일 가용성 = 1)에 대해서만 상세한 비트스트림을 로드한다는 것입니다. 예를 들어, 대한민국 3D 모델을 탐색할 때, 클라이언트는 먼저 대한민국이 포함된 큰 서브트리의 비트스트림만 로드하고, 불필요한 다른 지역의 서브트리는 아예 로드하지 않습니다. 이를 통해 비트스트림의 크기를 극적으로 줄이고, 메모리 낭비를 방지하며, 네트워크 전송 효율을 크게 높일 수 있습니다.
  3. 빠른 탐색 및 접근: 클라이언트가 특정 지점의 데이터를 요청하면, 상위 레벨의 서브트리 비트스트림을 확인하여 해당 영역에 데이터가 있는지 빠르게 판단합니다. 데이터가 있다면 해당 하위 서브트리의 비트스트림을 로드하고 더 깊이 탐색합니다. 이는 마치 거대한 지도를 펼치지 않고도 필요한 지역의 상세 지도를 즉시 펼쳐보는 것과 같습니다. 이러한 선택적 로딩 덕분에 방대한 타일 공간 속에서도 필요한 정보에 빠르게 접근할 수 있게 됩니다.

 

서브트리 레벨(깊이) 설정의 중요성

지구 전체를 21 레벨 쿼드트리로 분할 했을 때, 이 전체 쿼드트리를 몇 레벨 단위의 서브트리로 나눌지는 성능과 관리 효율에 많은 영향을 끼쳤기에, 서브트리 레벨을 몇으로 할 지는 중요한 문제였습니다.
 
따라서 다음 세가지 경우로 분류하여 비교해보겠습니다.

  • 서브트리 레벨이 작을 경우 (예: 3)
  • 서브트리 레벨이 너무 클 경우 (예: 21 - 지구 전체 타일을 포함)
  • 서브트리 레벨이 7인 경우 (최종 선택)

 

서브트리 레벨이 작을 경우 (예: 3)

3레벨 단위의 서브트리 그룹 (깊이 0, 1)

 
서브트리 레벨을 3으로 설정한다는 것은, 0레벨부터 2레벨까지의 타일 집합을 하나의 서브트리로, 3레벨부터 5레벨까지를 다음 서브트리로, 이런 식으로 3레벨 단위로 쪼개어 관리한다는 의미입니다. 21레벨 전체 트리를 이렇게 나누면 총 21 / 3 = 7개의 서브트리 깊이 층이 생깁니다.
 
서브트리당 비트스트림 크기

  • 타일 가용성 비트스트림 길이: 1 + 4 + 16 = 21 비트 
  • 콘텐츠 가용성 비트스트림 길이: 1 + 4 + 16 = 21 비트
  • 자식서브트리 가용성 비트스트림 길이: 4(쿼드트리)^{서브트리 레벨} = 4^3 = 64 비트

생성되는 서브트리 파일 수 (대한민국 기준)

  • 가장 깊은 서브트리의 루트 레벨은 21−3=18 레벨
  • 지구 전체에서 18 레벨에서의  타일 수는 4^18입니다.
  • 대한민국 면적(약 0.07%)을 고려하면, 생성될 수 있는 서브트리 개수는4^18 * 0.07 = 약 4천 8백만개

CRUD 관점

  • 생성/수정 (Create/Update): 특정 타일 변경 시 해당 타일이 속한 작은 서브트리 파일만 업데이트하면 되므로, 개별 수정 작업 자체는 빠를 수 있습니다. 그러나 변경이 잦고 광범위한 경우, 수천만 개의 서브트리 파일을 동시에 수정해야 하므로 전체적인 관리 오버헤드가 매우 커집니다.
  • 읽기/삭제 (Read/Delete): 클라이언트가 데이터를 읽을 때 필요한 서브트리 파일의 크기는 작지만, 너무 많은 서브트리 파일을 개별적으로 요청하고 로드해야 하므로 I/O 요청 횟수가 증가하여 성능 저하를 초래할 수 있습니다. 데이터 구조가 지나치게 파편화되어 전반적인 관리 복잡성도 증가합니다.

서브트리 레벨이 너무 클 경우 (예: 21 - 지구 전체 타일을 포함)

21레벨 단위의 서브트리 그룹

서브트리 레벨을 21로 설정한다는 것은, 지구 전체 0레벨부터 20레벨까지의 모든 타일을 단 하나의 서브트리 파일로 관리한다는 의미입니다.
 
서브트리당 비트스트림 크기

  • 타일 가용성 비트스트림 길이: 1 + 4 + 16 ... + 4^20 = 약 1.47조 비트 = 183GB
  • 콘텐츠 가용성 비트스트림 길이: 1 + 4 + 16 ... + 4^20 = 약 1.47조 비트 = 183GB
  • 자식서브트리 가용성 비트스트림 길이: X (자식이 존재하지않음)

생성되는 서브트리 파일 수 (대한민국 기준)

  • 1개 (전체를 하나의 서브트리로 관리하므로)

CRUD 관점

  • 생성/수정 (Create/Update): 어떤 타일 하나라도 변경되면 약 366 GB에 달하는 거대한 단일 서브트리 파일을 통째로 업데이트해야 합니다. 이는 매우 비효율적이고 오랜 시간이 소요될 수 있습니다.
  • 읽기/삭제 (Read/Delete): 클라이언트가 단 하나의 서브트리 파일만 로드하면 되지만, 이 파일 자체가 너무 커서 초기 로딩 시간이 매우 길어집니다. 특히 대한민국처럼 데이터 분포가 희소한 경우, 로드된 비트스트림의 대부분은 '0' 비트로 채워져 메모리 낭비와 불필요한 데이터 전송이 발생하며, 이는 서브트리 도입의 이점을 충분히 활용할 수 없게 만듭니다.

서브트리 레벨이 7인 경우 (최종 선택)

결과적으로, 전체 트리 레벨이 21일 때, 7과 같은 특정 단위로 서브트리를 나누는 것은 위 두 가지 극단적인 상황(작은 파일 vs. 너무 적은 큰 파일) 사이의 최적점을 찾아내기 위한 고민의 결과였습니다.
 
서브트리 레벨을 7로 설정하면, 전체 21레벨 트리를 21 / 7 = 3개의 주요 서브트리 깊이 층([0, 7), [7, 14), [14, 21))으로 분할하게 됩니다.
 
서브트리당 비트스트림 크기

  • 타일 가용성 비트스트림 길이: 1 + 4 + 16 ... + 4^6 = 5,461 비트
  • 콘텐츠 가용성 비트스트림 길이: 1 + 4 + 16 ... + 4^6 = 5,461 비트
  • 자식서브트리 가용성 비트스트림 길이: 4^7 = 16,384 비트

생성되는 서브트리 파일 수 (대한민국 기준)

  • 가장 깊은 서브트리의 루트 레벨은 21−7 = 14 레벨
  • 지구 전체에서 18 레벨에서의  타일 수는 4^14
  • 대한민국 면적(약 0.07%)을 고려하면, 생성될 수 있는 서브트리 개수는4^14 * 0.07 = 약 18만 8천개

CRUD 관점

  • 18만 개 수준의 적절한 서브트리 파일 개수는 I/O 오버헤드를 관리 가능한 수준으로 유지하며, 각 파일 내 비트스트림 크기가 합리적이어서 로딩 및 메모리 사용 효율성이 높습니다. 특정 타일 수정 시에도 영향받는 서브트리 파일 수가 극단적으로 많거나 적지 않아 효율적인 업데이트가 가능합니다.

세 가지 가용성 비트스트림: 서브트리 관리의 핵심

서브트리 구조 내에서, 각 서브트리는 자체적인 Morton Order 기반 가용성 비트스트림(Availability Bitstream)을 가집니다.

  • 타일 가용성 (Tile Availability) Bitstream:
    • 해당 서브트리 내에서 Morton Order 기준으로 어떤 타일이 존재하는지를 나타냅니다.
    • 이 비트가 1이면 해당 Morton Order의 타일이 실제로 존재하여 접근하거나 다음 레벨로의 탐색을 계속해야 함을 의미합니다. 클라이언트가 불필요하게 존재하지 않는 타일 경로를 탐색하는 것을 방지합니다.
  • 콘텐츠 가용성 (Content Availability) Bitstream:
    • 해당 서브트리 내에서 Morton Order 기준으로 어떤 타일에 실제 3D 모델 콘텐츠가 직접 포함되어 있는지를 나타냅니다. (일반적으로 리프 노드 (+ LOD 레벨) 에 해당)
    • 이 비트가 1이면 클라이언트는 해당 타일의 콘텐츠 파일을 요청하여 렌더링합니다.
  • 자식 서브트리 가용성 (Child Subtree Availability) Bitstream:
    • 이 비트스트림은 해당 서브트리의 자식 서브트리 중 어느 것이 실제로 존재하는지를 나타냅니다.
    • 상위 서브트리가 하위 서브트리로 넘어갈 때, 이 비트스트림을 확인하여 존재하지 않는 자식 서브트리 영역은 아예 탐색을 하지 않도록 합니다. 예를 들어, 대한민국 3D 모델을 로드할 때, 한반도를 벗어난 대양이나 다른 대륙에 해당하는 자식 서브트리는 이 비트스트림에서 '0'으로 마킹되어 있어 클라이언트는 해당 영역을 전혀 고려하지 않고 필요한 지역으로만 빠르게 드릴다운(Drill-down)하여 이동할 수 있습니다. 이는 "불필요한 탐색 (희소 데이터 탐색)" 문제를 해결하여 렌더링 성능을 크게 향상시킵니다.

5.3. 정리 

5.3.1. 비트스트림으로 얻은 이점 (Morton Order 기반의 Availability Bitstream)

항목 도입 전 문제점 비트스트림 도입 후 변화 주요 이점
다차원 →
1차원 인덱싱		 쿼드트리(0~20레벨)를 재귀 순회해야 특정 타일 탐색 가능
시간복잡도: O(첫째항이 1, 공비가 4인, n은 Level 등비수열 합)		 (level, x, y)를 Morton Order로 인코딩하여, 1차원 배열에서 O(1)로 탐색 가능
전체 쿼드트리 순회 없이 level, x, y값을 Morton Order로 인코딩후, 이 값의 타일/콘텐츠 가용성 비트스트림을 확인해 존재 여부를 O(1)로 탐색
메모리 및 디스크 접근 최적화 공간적으로 가까운 타일도 물리적으로 흩어져 있어 I/O 및 캐시 효율 저하 Morton Order에 따라 공간적으로 인접한 타일이 물리적으로도 인접 저장됨 디스크 연속 블록 접근 효율 ↑,
CPU 캐시 적중률 ↑
고밀도 표현 타일 존재 여부를 저장하는 데 많은 JSON/노드 데이터가 필요 타일 존재 여부를 1비트로 압축 지구 전체(0~20레벨, 약 1.1조 타일)를 약 183GB로 표현 가능

 

5.3.2. 서브트리 추상화 도입의 이점

비트스트림은 지구 전체를 1차원으로 인덱싱했으나, 희소 데이터에 비효율적이었습니다.
서브트리 개념을 도입해 비트스트림을 작은 단위로 추상화하여 관리하며, 아래와 같은 이점을 얻었습니다.
 

서브트리 단위 Bitstream 분할 관리

항목 도입 전 문제 서브트리 도입 후 주요 이점
탐색 공간 축소 전체 1.1조 개의 타일을 순회하며 존재 여부 확인 → 연산 자원 낭비 상위 서브트리에서 자식 서브트리 가용성을 판단 → 하위 탐색 생략 가능 - 존재하지 않는 탐색 경로 제거
- 렌더링 속도 개선
- 디스크/네트워크 I/O 최소화
파일 및 캐시 관리 단순화 단일 비트스트림(366GB) 전체를 재생성해야 하며, 부분 수정/캐시가 어려움 각 서브트리를 독립 파일로 관리(S3 객체 또는 로컬 파일)
부분 수정 시 해당 서브트리만 재생성		 - 부분 무효화 및 갱신 가능
- 병렬 처리 용이
- 캐시 범위 최소화 → 캐시 효율성 증가

서브트리 구조는 희소한 3D 공간 데이터에 적합한 계층적 분할 관리 방식입니다. 탐색 범위를 줄이고, 캐시 및 배포 관리에 유리한 구조를 제공하여, 대규모 공간 데이터를 실시간으로 스트리밍하고 유지보수하는 데 핵심적인 역할을 합니다.
 
 

서브트리 적용 전후 비교

분류 서브트리 적용 전 서브트리 적용 휴
비트스트림 용량 수백 GB ~ 수 TB 수십 ~ 수백 MB (희소성 반영)
탐색 비용 모든 타일 탐색 필요 존재하는 영역의 서브트리만 드릴다운 탐색
초기 로딩 전체 비트스트림 선행 로딩 현재 위치의 서브트리만 동적 로딩 (맨 처음: 0.0.0.subtree)
파일 관리 단일 파일 전체 재생성 필요 → 유지보수/배포 부담 변경된 서브트리만 개별 저장 및 배포 → 캐시 갱신 최소화

서브트리 구조는 희소성과 계층성을 고려한 설계로, 비트스트림의 크기를 줄이고 탐색 효율과 유지보수 편의성을 크게 향상시킵니다.
 

6. 요약

항목 Explicit Tiling (기존 방식) Implicit Tiling (개선 방식)
타일 정의 방식 tileset.json에 명시적으로 모든 타일 정의 {Level}/{X}/{Y} 규칙 기반 식별
탐색 방식 JSON 파싱 기반. 
브라우저가 매번 루트부터 쿼드트리를 순차 탐색
→ O(4^{level}) 수준의 메모리/CPU 부담		 좌표(Lon/Lat/Height)를 {Level}.{X}.{Y}로 변환 후, 
해당 Subtree의 비트스트림만 확인 → O(1) 탐색 가능
희소 데이터 대응 콘텐츠가 없어도 모든 노드를 명시적으로 정의해야 함
→ 저장공간·탐색속도 낭비: O(4^{level})		 콘텐츠가 있는 영역만 서브트리 및 비트스트림 생성
→ 저장공간·탐색속도 효율 향상
파일 구성 요소
(3D 모델 파일 생략)		 tileset.json(여러개)에 전체 계층과 콘텐츠 경로 명시 tileset.json(규칙 정의 JSON 1개) +
여러 개의 subtree (.subtree) 파일로 구성, 
타일은 규칙에 따라 계산된 경로로 접근
파일 크기 (서울 기준) 전체 tileset.json 수십 GB (서울 기준) 기존 방식에 비해 약 26% 감소 (서울 기준)
초기 로딩 비용 수십 MB~수백 MB tileset.json 파싱 1개 규칙 정의 tileset.json + 서브트리 탐색
변경 시 갱신 단위 전체 JSON 갱신 필요 서브트리 단위 갱신 가능 (부분 배포)
랜덤 액세스 불가
파일 트리 순차 탐색 해야함		 가능
{Level}/{X}/{Y} URL로 직접 접근(랜덤 액세스) 가능
캐싱 전략 전체 파일 구조 기반 서브트리 단위 캐싱 최적화
병렬 처리 불가
- tileset.json은 계층적 구조로 상호 참조되어 있어
- 상위 노드가 없으면 하위 노드를 생성할 수 없음
- 전체 tileset 구조를 순차적으로 구성해야 함		 가능
- 각 Subtree는 독립적으로 생성 가능
- 특정 영역, 특정 레벨 단위로 나눠 여러 워커에서 병렬 생성 가능

 
 
3D 공간 데이터를 효율적으로 다루는 시스템을 설계하는 과정에서 가장 큰 고민은 확장성과 성능을 어떻게 동시에 확보할 것인가였습니다.

 

1. 기존 3D GIS 엔진의 한계 – Explicit Tiling

기존 3D GIS 엔진은 tileset.json과 디렉터리 구조 기반의 Explicit Tiling 방식을 사용해 타일 계층을 정의합니다. 하지만 다음과 같은 한계가 있었습니다.

  • 파일 크기 폭발: 수백만 개 타일만 있어도 tileset.json은 수십 GB ~ 수백 GB로 커짐
  • 초기 로딩 지연: JSON 파싱 비용이 커지고, 클라이언트 메모리 사용량도 증가
  • 희소 데이터 비효율: 콘텐츠가 없는 지역도 탐색 대상이 됨 → 네트워크·CPU 낭비

2. 개선 방향 – Implicit Tiling: 규칙 기반 자동 타일링

이 문제를 해결하기 위해, 지구 전체를 균일한 그리드로 미리 나누는 Implicit Tiling 구조를 설계했습니다.

  • 좌표 기반 규칙 분할: {Level}/{X}/{Y}로 타일을 수식으로 식별
  • 명시적인 tileset.json 생략 가능: 클라이언트는 URL 규칙을 통해 타일 요청 가능 (규칙을 정의하는 tileset.json 1개는 필요)
  • 좌표계 RTC + 쿼드트리 21레벨 분할: 약 38m x 19m 정밀도 확보

3. 새로운 과제 – 수조 개의 타일, 어떻게 존재 여부를 인코딩할까?

전 지구를 Level 21까지 쿼드트리로 분할하면 약 1.1조 개 타일이 생성됩니다. 이 중 대부분은 데이터가 없는 빈 타일이므로, 존재 여부만을 표현하는 Availability Bitstream이 필요했습니다.

  • Z-Order (Morton Curve)로 2D 좌표를 1D 비트맵에 매핑
  • 각 타일의 존재 여부를 1비트로 인코딩 → 전체 183GB
  • 콘텐츠 존재 여부까지 포함하면 약 366GB 

❗문제는, 대한민국처럼 극히 일부 영역만 사용하는 경우에도 지구 전체 비트맵(1.1조 개)을 구성해야 한다는 점입니다.
이는 메모리 낭비 + 탐색 성능 저하를 유발합니다.

4. 해법 – Subtree 구조 도입

지구 전체를 하나의 Bitstream으로 표현하는 대신, 서브트리(Subtree) 단위로 쪼갰습니다.

  • 서브트리란? 일정 레벨 깊이(N)를 루트로 하는 하위 타일 트리 단위
  • 예: Level 7 단위로 나누면, 전체 트리는 Level 0 → 7 → 14 순으로 계층화됨.
    • 0레벨 Subtree는 다음 정보를 가짐
      • 하위 0~6레벨 타일/콘텐츠 Availability
      • 하위 Subtree(Level 7 자식)의 존재 여부
    • 7레벨 Subtree는 다음 정보를 가짐
      • 하위 7~13레벨 타일/콘텐츠 Availability
      • 하위 Subtree(Level 14 자식)의 존재 여부
    • 14레벨 Subtree는 다음 정보를 가짐
      • 하위 14~20레벨 타일/콘텐츠 Availability
      • 21레벨 Subtree는 존재하지 않으므로 자식이 없음.
        (= child subtree Availability는 모두 '0'이므로 압축하여 constant = 0 으로 표현)
  • 탐색 구조: Level 0 → Level 7 서브트리 → Level 14 서브트리

5. Subtree가 가져온 3가지 핵심 이점

1. 탐색 효율 향상

  • 탐색 시 불필요한 지역은 아예 서브트리 요청을 생략
  • 예: 사용자가 서울만 탐색 → 제주도 서브트리는 로드하지 않음

2. 파일 및 캐시 관리 유연성

  • 일부 지역만 변경되면 해당 서브트리만 재생성
  • 캐시 무효화 범위도 정밀하게 제어 가능

3. 병렬 처리 및 자동화에 최적화

  • 각 서브트리 단위는 독립적으로 생성 가능 (수정에 용이)
  • 빌드 자동화와 대규모 배포가 쉬워짐

6. 결과 및 확장성

이번 프로젝트를 통해 다음과 같은 요소들을 모두 갖춘 구조를 설계/구현 할 수 있었습니다.

  • 랜덤 액세스가 가능한 타일 주소 체계
  • 정밀한 공간 분할
  • 효율적인 탐색
  • 변경 이력 추적
  • 부분 배포 및 선택적 갱신
  • 유리한 캐싱 구조

이러한 기반 위에, 현재는 Git-Like 공간 정보 버전 관리 시스템을 개발 중입니다.
커밋 단위로 변경된 타일만 정밀하게 추적하고, 필요한 서브트리(타일, 3D 모델)만 선택적으로 다시 빌드할 수 있는 구조로 확장해 나가고 있습니다.

7. 참고 자료 및 관련 포스팅

깃허브 시각화 링크

참고 자료

관련 포스팅

저작자표시 변경금지 (새창열림)

'개발 노트' 카테고리의 다른 글

Redis BGSAVE, OOM 이유: Copy-on-Write, fork()  (5) 2025.06.15
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
TAG more
«   2025/09   »
일 월 화 수 목 금 토
1 2 3 4 5 6
7 8 9 10 11 12 13
14 15 16 17 18 19 20
21 22 23 24 25 26 27
28 29 30
글 보관함