Scene Graph & Spatial Data Structures

1. Overview

씬 그래프 및 공간 데이터 구조(Scene Graph & Spatial Data Structures, SDS)는 가상 공간에 흩어진 방대한 수치의 물리 개체들을 논리적인 트리 구조와 기하학적인 분할 수법으로 체계화하는 '공간 정보 거버넌스'입니다.

학습자는 부모-자식 관계를 통해 상대적 물리 좌표를 상속하는 씬 그래프의 수리적 수순과, 수만 개의 개체 중 화면에 보이는 것만을 빠르게 골라내는 공간 분할(Spatial Partitioning) 기술을 배옵니다. 특히, 고차원 검색 속도를 $O(N)$에서 $O(log N)$으로 단축시키는 **쿼드트리(Quad-tree)**와 **옥트리(Octree)**의 수치 연산 역학을 익힙니다. 이를 통해 정교한 3D 월드를 하드웨어 사양 한계 속에서도 끊김 없이 렌더링하는 하이엔드 아키텍처 역량을 확보합니다.

2. Scope & Boundaries

In-Scope

• Hierarchy Transformation Math: 로컬-월드-카메라 좌표계를 전이시키는 행렬 스택 물리
• Spatial Partitioning Mechanics: Quad-tree(2D), Octree(3D), BSP(용적 분할) 수리 모델
• Visibility Culling Logic: 시야 원추(Frustum) 및 차폐(Occlusion) 정보를 활용한 수리적 거부
• Bounding Volume Mechanics: 복잡한 기하체를 단순한 물리 구(Sphere)나 박스(AABB)로 근사
• Broad-phase Detection: 물리 충돌 후보군을 수리적으로 빠르게 압축하는 공간 필터링

Out-of-Scope

• 일반적인 관계형 데이터베이스의 인덱싱 알고리즘 (06-01-XX 영역에서 분담)
• GIS(지리정보시스템)의 전지구적 좌표 수치 변환 (측량학 영역)

Boundaries

• SDS vs. Linear Lists: 단순 배열이 '순차적 수리 접근'에 집중한다면, SDS는 '공간적 근접도 기반의 기하학적 수리 인덱싱'이라는 차별화된 물리 검색 모델에 집중하여 구분합니다.

3. Counterexample

• 단순히 "폴더처럼 정리하기"라 설명하는 것은 SDS 학습이 아닙니다. 왜 부모 개체의 수리적 회전 행렬이 자식 개체의 월드 물리 좌표를 기하급수적으로 복잡하게 만드는지 증명할 수 있어야 하며, **평면 분할(BSP)**의 수리적 결합 수순이 잘못되었을 때 발생하는 물리적 '깜빡임($Z$-$fighting$)'이나 탐색 성능 저하를 논증하지 못한다면 공간 아키텍처의 본질을 이해하지 못한 것입니다.

4. Prerequisites

• Data Structures & Algorithms (Basic): 04-XX-XX의 트리(Tree) 및 그래프 탐색 기초 이해가 필수입니다.
• Linear Algebra (Recommended): 04-XX-XX의 동차 좌표계($Homogeneous$ $Coordinates$) 행렬 연산 이해가 권합됩니다.

5. Learning Map

1. Coordinate Inheritance: 부모-자식 간의 물리적 위계가 수리적으로 어떻게 전달(Update)되는지 이해합니다.
2. Visual Pruning: 방대한 수치의 객체 중 물리적으로 불필요한 영역을 수리적으로 도려내는(Culling) 법을 배웁니다.
3. Spatial Indexing: 무질서한 공간 좌표를 수리적인 격자나 트리로 색인하여 물리적 검색 속도를 극대화합니다.
4. Infinite World Governance: 수백만 개의 개체가 존재하는 하이엔드 오픈월드의 수리적 일관성을 물리 완성합니다.

6. Learning Topics

Basic

Core: 씬 그래프와 변환 계층 (Transformation Hierarchy)

• Why to Learn: 수만 개의 부품이 결합된 로봇과 같은 복잡한 물리 개체의 수리적 통합 제어를 위해서입니다.
• What to Learn:
  • Local vs World Space: 각 개체의 독자적 수치와 세계 공통 물리 수치
  • Transform Parent-Child: 부모 행렬 수치가 자식에게 수치적으로 곱해지는 수순
  • Scene Updates: 매 프레임마다 계층 수치를 갱신하는 재귀적 물리 루프
• How to Learn:
  • 부모 개체를 수리적으로 회전시켰을 때, 멀리 떨어진 자식 개체의 물리 궤적이 어떻게 호를 그리는지 실습
  • Transform Stack 구조를 직접 구현하여, 하부 노드들의 수리적 명세를 물리 관리하는 실험
• Implement: 트리 구조를 따라 월드 변환 행렬을 수리 산출하는 기초 Hierarchical_Transform_Agent

Recommended

Core: 가시성 정보와 컬링 (Visibility Logic)

• Why to Learn: 하드웨어의 수리적 연산 한계를 넘지 않도록, 보이지 않는 물리 개체의 연산을 사전에 차단하기 위함입니다.
• What to Learn:
  • Frustum Culling: 카메라 시야각 수치 밖의 개체를 물리적으로 배제
  • Back-face Culling: 카메라를 등진 수리적 평면의 연산을 물리 억제
  • Occlusion Culling: 다른 개체에 물리적으로 가려진 수리 데이터의 통제
• How to Learn:
  • 화면에 보이는 삼각형 수치와 실제 존재하는 삼각형 수치를 대조하며, 컬링 수율을 수리적으로 계산하는 실습
  • Bounding Box Audit을 통해, 복잡한 물리 메시를 단순한 수치 상자로 감싸는 근사화 수순 훈련
• Implement: 특정 시야 평면 수치와 객체의 충돌 여부를 물리 판별하는 Frustum_Culling_Governor

Practical

Core: 쿼드트리와 옥트리 공간 분할 (Tree Dynamics)

• Why to Learn: 공간을 수리적으로 작게 쪼개어, 인접한 물리 개체들끼리만 수리 연산을 수행하게 만들기 위해서입니다.
• What to Learn:
  • Subdivision Rules: 공간의 밀도 수치에 따라 4개(2D) 또는 8개(3D)로 균등 물리 분할
  • Query Dynamics: 특정 수리 범위 내의 물리 객체들을 $O(log N)$ 속도로 색출
  • Tree Balancing: 객체 이동에 따른 수리적 트리 갱신 물리 연산 비용 최적화
• How to Learn:
  • 10,000명의 수리적 시민이 돌아다니는 도시 공간을 Octree로 분할하고, 인근 시민 검색 속도를 $N^2$ 모델과 물리 대조 실습
  • Depth Limit 조절을 통해, 트리 뎁스 수치와 물리 메모리 점유 수치 사이의 상관관계 분석 훈련
• Implement: 수리 좌표를 입력받아 적절한 공간 노드에 물리 배치하는 Dynamic_Octree_Manager

Advanced

Core: BSP 트리와 전처리 물리 (Static Governance)

• Why to Learn: 정적인 물리 배경(건물 내부 등)의 수리적 깊이 정보를 사전에 계산하여 실시간 렌더링을 하이엔드로 최적화하기 위함입니다.
• What to Learn:
  • Binary Space Partitioning: 하드웨어 평면 수치를 기준으로 공간을 물리 반전 및 분할
  • Potential Visible Set (PVS): 특정 구역에서 물리적으로 보일 가능성이 있는 구역의 수리 데이터베이스
  • Area/Portal Logic: 문($Portal$) 수치에 의한 물리 공간 간의 시야 전이 제어
• How to Learn:
  • 복잡한 실내 수리 던전을 Portal 시스템으로 구축하고, 구역 이동 시 물리 로딩 수치를 최소화하는 기법 실습
  • Static Mesh Baking 과정을 분석하며, 전처리된 수리 결과물이 실시간 물리 성능에 기여하는 수치 입증
• Implement: 공간 연결 정보를 그래프 수치로 관리하여 가시 영역을 물리 추적하는 Portal_Visibility_Tracker

7. Terminology

8. References

Primary

• [P1] CS2023 - Graphics & Interactive Techniques - Scene Management — Academic curricula.
• [Foundations of Game Engine Development, Vol 1: Mathematics] Eric Lengyel — Core SDS math.

Secondary

• [Real-Time Rendering, 4th Ed] Chapter 19: Scene Graphs and Global Illumination.
• [Geometric Data Structures for Computer Graphics] Elmar Eisemann — Deep dive into partitions.

Industry

• [Unity: The Scene Graph & Transform Internals] — Practical implementation rules.
• [Unreal Engine: Spatial Partitioning for Large Worlds] — World Partition & Data Layers physics.

9. Final Checklist

Primary

• '로컬 좌표' 수치가 '부모-자식' 계층을 거쳐 '월드 물리 좌표'로 확정되는 수리 통합 과정을 설명 가능한가? (P1)
• '공간 분할' 수순이 '무차별적 충돌 검사($N^2$)'의 물리적 한계를 수리적으로 어떻게 해결하는지 논증할 수 있는 가? (P1)

Secondary

• '시야 원추 컬링($Frustum$ $Culling$)' 수식에서 외적($Cross$ $product$) 수치가 평면 판별에 기여하는 바를 소통 가능한가?
• Octree의 수리적 '최대 뎁스' 수치가 너무 낮거나 높을 때 각각 발생하는 물리적 성능 저하를 진단할 수 있는 가?

Industry

• 실무 아키텍처 검수 시, 오브젝트 개수 수치에 따른 Update frequency 물리 지연을 수리적으로 최적화할 수 있는 가? (SFIA)
• Static vs Dynamic 공간 거버넌스를 구분하여, 배경 물리와 캐릭터 물리 개체의 수리적 인덱싱 전략을 차별화할 수 있는 가?