Unreal Engine의 Foliage와 HISM, 그리고 자료구조·알고리즘의 연관성

Unreal Engine의 Foliage와 HISM, 그리고 자료구조·알고리즘의 연관성

1. 오늘 학습한 내용

오늘은 언리얼 엔진에서 많은 나무, 풀, 바위 등의 오브젝트를 배치할 때 사용하는 Foliage와 HISM(Hierarchical Instanced Static Mesh)에 대해 학습했다.

처음에는 Foliage와 HISM을 단순히 여러 개의 Static Mesh를 효율적으로 배치하기 위한 언리얼 엔진의 기능이라고 생각했다.

하지만 내용을 학습하면서 Foliage와 HISM이 자료구조와 알고리즘에서 배운 개념들과 연결된다는 것을 알게 되었다.

특히 다음과 같은 개념들과 연관되어 있었다.

• 배열(Array)
• 인스턴스(Instance)
• 공간 분할(Spatial Partitioning)
• 계층 구조(Hierarchy)
• 트리(Tree)
• 탐색(Search)
• 정렬 및 그룹화
• 시간 복잡도
• 메모리와 CPU/GPU 작업량 최적화
• 컬링(Culling)

즉, 자료구조와 알고리즘은 단순히 코딩 테스트를 위한 개념이 아니라 실제 게임 엔진에서 대량의 데이터를 효율적으로 처리하고 성능을 최적화하는 데에도 사용되는 중요한 개념이라는 것을 알게 되었다.

---

2. Foliage란?

언리얼 엔진의 Foliage는 나무, 풀, 바위 등의 오브젝트를 넓은 공간에 대량으로 배치하기 위한 시스템이다.

예를 들어 일반적인 방법으로 나무 1,000개를 배치한다고 생각해보면 각각의 나무를 서로 독립적인 Actor로 만들어 배치할 수 있다.

Tree Actor 1
Tree Actor 2
Tree Actor 3
...
Tree Actor 1000

이렇게 되면 화면에 나무가 1,000개 존재하는 것뿐만 아니라 엔진에서도 많은 오브젝트를 각각 관리해야 한다.

따라서 같은 Static Mesh를 대량으로 배치해야 하는 상황에서는 각각을 독립적인 Actor로 관리하는 것보다 Instancing이라는 개념을 사용하는 것이 중요하다.

---

3. Instance란?

Instance는 같은 Static Mesh를 여러 번 사용하면서 각각의 위치, 회전, 크기 등의 정보만 다르게 저장하는 방식이다.

예를 들어 하나의 나무 Mesh가 있다고 가정한다.

Tree Mesh

이 Mesh를 1,000번 복제해서 각각 별도의 Mesh 데이터를 만드는 것이 아니라 하나의 Mesh를 공유하고 각각의 Instance에 Transform 등의 정보를 저장할 수 있다.

Tree Mesh
 ├─ Instance 0 → 위치 A
 ├─ Instance 1 → 위치 B
 ├─ Instance 2 → 위치 C
 ├─ ...
 └─ Instance 999 → 위치 Z

자료구조 관점에서 보면 하나의 Mesh 데이터를 공유하면서 여러 Instance의 데이터를 관리하는 구조라고 볼 수 있다.

이 과정에서 여러 Instance의 정보를 저장하고 관리하기 위해 배열과 같은 자료구조의 개념이 연결된다.

---

4. HISM이란?

HISM은 Hierarchical Instanced Static Mesh의 약자이다.

기본적인 Instanced Static Mesh의 개념에 Hierarchy, 즉 계층 구조를 추가한 방식이다.

많은 Instance가 존재할 때 모든 Instance를 하나씩 검사하는 것은 비효율적일 수 있다.

예를 들어 나무가 10,000개 있다고 가정한다.

Tree 1
Tree 2
Tree 3
...
Tree 10000

카메라에서 실제로 보이는 나무를 찾기 위해 매번 10,000개의 Instance를 전부 검사한다면 상당히 많은 작업이 필요하다.

HISM은 Instance들을 공간적으로 묶고 계층적으로 관리하여 필요한 영역을 효율적으로 검사할 수 있도록 한다.

여기에서 Hierarchy와 Tree 자료구조의 개념이 연결된다.

---

5. HISM과 Tree 자료구조

자료구조에서 계층 구조를 표현하는 대표적인 자료구조가 Tree이다.

예를 들어 공간을 계층적으로 나눈다면 다음과 같은 구조로 생각할 수 있다.

                 전체 공간
                /        \
             영역 A       영역 B
            /    \       /    \
          A1      A2    B1     B2
         / \      / \   / \    / \
        ...      ...  ...     ...

전체 공간을 여러 영역으로 나누고 그 영역을 다시 작은 영역으로 나누는 방식이다.

이렇게 계층적으로 나누어 놓으면 특정 영역에 있는 데이터를 찾을 때 전체 데이터를 전부 확인할 필요가 없다.

예를 들어 카메라가 A 영역에 있다면 다음과 같이 탐색 범위를 줄일 수 있다.

전체 공간
   ↓
영역 A
   ↓
A1
   ↓
필요한 Instance

즉, 계층 구조를 이용해서 탐색해야 할 범위를 줄이는 것이 핵심이다.

---

6. HISM과 탐색 알고리즘

이 부분에서 자료구조와 알고리즘에서 공부했던 탐색(Search)과 연결된다.

가장 단순한 탐색 방법 중 하나는 선형 탐색이다.

for (int i = 0; i < 10000; i++)
{
    // 각각의 Instance 검사
}

Instance가 N개라면 최악의 경우 모든 Instance를 검사해야 하기 때문에 작업량은 O(N)이 된다.

N = 10,000

→ 최대 10,000개의 Instance 검사

하지만 공간을 계층적으로 나누어 관리하면 불필요한 영역을 먼저 제외하고 필요한 영역을 중심으로 탐색할 수 있다.

개념적으로 다음과 같은 과정이다.

전체 Instance
      ↓
공간 분할
      ↓
관련 없는 영역 제거
      ↓
관심 영역 탐색
      ↓
필요한 Instance 검사

따라서 단순하게 모든 Instance를 순차적으로 검사하는 것보다 실제로 검사해야 하는 데이터의 양을 크게 줄일 수 있다.

다만 실제 HISM의 내부 동작을 단순하게 O(log N)이라고 단정해서는 안 된다.

중요한 것은 HISM이 트리 기반의 계층적 공간 분할을 통해 탐색 범위를 줄이고 불필요한 작업을 제거한다는 알고리즘적인 사고방식이다.

---

7. Culling과 알고리즘

게임에서 중요한 개념 중 하나가 Culling이다.

Culling은 현재 카메라에서 볼 필요가 없는 오브젝트를 렌더링 대상에서 제외하는 과정이다.

예를 들어 나무가 10,000개 존재하지만 현재 카메라에서 실제로 필요한 나무가 500개라고 가정한다.

전체 Instance = 10,000

화면에 필요한 Instance = 500

10,000개의 나무를 전부 렌더링할 필요가 없다.

10,000개
   ↓
Culling
   ↓
필요한 500개

따라서 Culling을 효율적으로 수행하기 위해서는 어떤 오브젝트가 현재 화면에 필요한지 빠르게 판단할 수 있어야 한다.

이 과정에서 공간 정보를 활용하면 카메라와 관계없는 영역을 빠르게 제외할 수 있다.

결국 Culling 역시 단순히 렌더링 기능으로만 볼 것이 아니라,

자료구조
   +
공간 분할
   +
탐색 알고리즘
   ↓
필요한 데이터만 처리

라는 관점에서 이해할 수 있다.

---

8. 공간 분할(Spatial Partitioning)

게임에서 오브젝트의 수가 많아지면 모든 오브젝트를 한꺼번에 관리하는 것은 비효율적이다.

그래서 공간을 여러 영역으로 나누어 관리하는 Spatial Partitioning이라는 개념을 사용한다.

예를 들어 맵을 다음과 같이 나눌 수 있다.

+---------+---------+
| Zone A  | Zone B  |
|         |         |
+---------+---------+
| Zone C  | Zone D  |
|         |         |
+---------+---------+

카메라가 Zone A에 있다면 Zone D에 있는 나무까지 동일한 방식으로 검사할 필요가 없을 수 있다.

따라서

공간 분할
   ↓
탐색 범위 감소
   ↓
불필요한 검사 감소
   ↓
렌더링 및 CPU 작업 감소

라는 흐름으로 연결된다.

자료구조와 알고리즘에서 배운 탐색 범위를 줄이는 것과 같은 최적화 사고방식이다.

---

9. Foliage와 HISM의 관계

Foliage와 HISM은 완전히 동일한 개념은 아니다.

Foliage는 언리얼 엔진에서 많은 식생 오브젝트를 배치하고 관리하기 위한 시스템이고, HISM은 동일한 Static Mesh의 많은 Instance를 효율적으로 렌더링하고 관리하기 위한 인스턴싱 컴포넌트의 한 종류이다.

개념적으로 보면 다음과 같이 연결할 수 있다.

Foliage
   ↓
대량의 식생 배치 및 관리
   ↓
Instance 기반 처리
   ↓
HISM 등의 인스턴싱 방식 활용

따라서 Foliage를 학습하면서 HISM을 함께 이해하면 왜 수많은 나무와 풀을 배치해도 일반 Actor를 수천 개 배치하는 것과 다른 방식으로 처리할 수 있는지 이해하는 데 도움이 된다.

---

10. 일반 Actor와 Instance 방식의 차이

예를 들어 나무 1,000개를 배치한다고 가정한다.

일반적인 Actor 방식에서는 다음처럼 각각의 Actor가 존재한다.

Actor
 └─ Tree

Actor
 └─ Tree

Actor
 └─ Tree

...

반면 Instance 방식에서는 다음과 같이 하나의 Tree Mesh를 공유하면서 여러 Instance의 Transform 등을 관리할 수 있다.

하나의 Tree Mesh
       +
Instance Transform 배열
       ↓
여러 개의 나무

여기에서 자료구조의 Array 개념이 연결된다.

개념적으로는 다음과 같이 생각할 수 있다.

Instances[0]
Instances[1]
Instances[2]
...
Instances[N]

각 Instance의 위치, 회전, 크기 등의 데이터를 관리하는 구조이다.

---

11. 자료구조를 공부하는 이유

자료구조를 공부하면서 배운 내용들은 처음에는 게임 개발과 크게 관련이 없어 보일 수 있다.

하지만 실제 게임 엔진에서는 다양한 자료구조를 사용하여 수많은 데이터를 관리해야 한다.

예를 들어,

Array
 ↓
Instance 데이터 관리

Tree
 ↓
계층 구조 관리

Spatial Partitioning
 ↓
공간을 나누어 관리

Search
 ↓
필요한 오브젝트 탐색

Algorithm
 ↓
탐색 및 컬링을 효율적으로 수행

과 같이 연결할 수 있다.

결국 게임 엔진은 매우 많은 데이터를 빠르게 처리해야 하기 때문에 어떤 자료구조를 사용하고 어떤 알고리즘으로 데이터를 처리하는지가 성능에 큰 영향을 줄 수 있다.

---

12. 시간 복잡도 관점에서 생각하기

예를 들어 게임 월드에 Instance가 100개 있다고 가정한다.

N = 100

모든 Instance를 확인하는 방식이라면 작업량은 O(N)이다.

Instance가 10,000개가 되면 확인해야 할 데이터도 크게 증가한다.

100
 ↓
1,000
 ↓
10,000
 ↓
100,000

따라서 데이터가 증가할수록 어떻게 탐색 범위를 줄일 것인가가 중요해진다.

이때 Tree나 Spatial Partitioning 등의 구조를 사용하면 모든 데이터를 직접 검사하지 않고 필요한 부분을 중심으로 탐색할 수 있다.

이것이 자료구조와 알고리즘을 공부할 때 시간 복잡도를 중요하게 배우는 이유와 연결된다.

---

13. 이것이 게임 최적화와 연결되는 이유

게임에서는 단순히 오브젝트의 개수만 중요한 것이 아니다.

오브젝트가 많아지면 다음과 같은 여러 작업이 발생할 수 있다.

오브젝트 관리
      ↓
위치 확인
      ↓
카메라와의 관계 확인
      ↓
컬링
      ↓
렌더링 준비
      ↓
GPU 작업

오브젝트가 많아질수록 이 과정에서 발생하는 비용도 증가할 수 있다.

따라서

많은 데이터
   ↓
효율적인 자료구조
   ↓
효율적인 탐색 알고리즘
   ↓
불필요한 작업 제거
   ↓
게임 성능 향상

이라는 흐름으로 이해할 수 있다.

---

14. 실제 게임 상황에 적용해보기

예를 들어 게임 맵에 나무가 20,000개 있다고 가정한다.

비효율적인 방식은 단순하게 모든 나무를 대상으로 작업하는 것이다.

나무 20,000개
     ↓
전부 검사
     ↓
전부 처리
     ↓
전부 렌더링

반면 인스턴싱과 공간 분할, 컬링 등을 이용하면 다음과 같은 방향으로 처리할 수 있다.

나무 20,000개
       ↓
공간/계층 구조로 관리
       ↓
카메라와 관계없는 영역 제거
       ↓
필요한 Instance만 처리
       ↓
필요한 것만 렌더링

이처럼 데이터가 많아질수록 단순히 컴퓨터의 성능에 의존하는 것이 아니라 데이터를 어떻게 구성하고 필요한 데이터만 어떻게 찾아낼 것인지가 중요해진다.

---

15. 지금까지 공부한 자료구조와의 연결

앞에서 공부했던 자료구조와 알고리즘도 언리얼 엔진의 여러 시스템과 연결해서 생각할 수 있다.

Array

Instance 데이터나 Actor 목록처럼 순차적으로 데이터를 관리하는 데 사용할 수 있다.

Instances[0]
Instances[1]
Instances[2]
...

Hash

특정 ID나 키를 이용해서 데이터를 빠르게 찾는 데 사용할 수 있다.

ID → Object
이름 → Data

Tree

계층 구조를 표현할 수 있다.

전체
 ├─ 영역 A
 │   ├─ A1
 │   └─ A2
 └─ 영역 B
     ├─ B1
     └─ B2

HISM에서 학습한 계층 구조와 연결해서 생각할 수 있다.

Graph

게임에서는 NavMesh나 경로 탐색처럼 여러 노드와 연결 관계를 표현하는 문제와 연결된다.

A ─ B ─ C
│   │
D ─ E

Heap / Priority Queue

우선순위가 필요한 작업이나 경로 탐색 알고리즘 등과 연결해서 생각할 수 있다.

Search Algorithm

필요한 오브젝트나 데이터를 빠르게 찾기 위한 탐색 문제와 연결된다.

---

16. 이번 학습에서 알게 된 가장 중요한 점

이번 학습을 통해 자료구조와 알고리즘이 실제 게임 개발과 밀접하게 연결되어 있다는 것을 알게 되었다.

Foliage와 HISM을 단순히 언리얼 엔진의 기능으로만 보면

"나무를 많이 배치할 때 사용하는 기능"

정도로 생각할 수 있다.

하지만 내부적인 원리를 자료구조와 알고리즘 관점에서 바라보면,

많은 Instance
      ↓
효율적인 데이터 관리
      ↓
공간 분할
      ↓
계층 구조
      ↓
탐색 범위 감소
      ↓
Culling
      ↓
불필요한 작업 제거
      ↓
성능 최적화

라는 흐름으로 이해할 수 있다.

특히 중요한 것은 데이터가 많아질수록 모든 데이터를 무조건 처리하는 것이 아니라 필요한 데이터만 효율적으로 찾아내는 것이 중요하다는 점이다.

---

17. 최종 정리

오늘 학습한 내용을 정리하면 다음과 같다.

Foliage

→ 나무, 풀, 바위 등의 식생을 대량으로 배치하고 관리하기 위한 언리얼 엔진의 시스템

Instance

→ 동일한 Static Mesh를 공유하면서 여러 개의 Transform 등을 이용해 많은 오브젝트를 표현하는 방식

HISM

→ 많은 Static Mesh Instance를 계층적으로 관리하여 효율적인 컬링과 렌더링을 지원하는 방식

Hierarchy

→ 데이터를 계층적으로 구성하여 필요한 부분을 효율적으로 찾고 불필요한 부분을 제외하기 위한 구조

Tree

→ 계층 구조를 표현하는 대표적인 자료구조

Spatial Partitioning

→ 공간을 여러 영역으로 나누어 탐색해야 할 범위를 줄이는 방법

Culling

→ 현재 렌더링할 필요가 없는 오브젝트를 렌더링 대상에서 제외하는 과정

Search

→ 필요한 데이터를 효율적으로 찾기 위한 알고리즘

결국 오늘 학습의 핵심은 다음과 같이 정리할 수 있다.

게임 엔진은 매우 많은 데이터를 처리해야 하기 때문에 효율적인 자료구조와 알고리즘이 필요하다.

Foliage와 HISM은 대량의 오브젝트를 효율적으로 관리하고 렌더링하기 위해 이러한 최적화 개념이 실제 게임 엔진에서 활용되는 사례라고 볼 수 있다.

자료구조와 알고리즘을 공부하면서 배운 Array, Tree, Search, 시간 복잡도 등의 개념이 단순한 이론이 아니라 실제 언리얼 엔진의 성능과 연결될 수 있다는 점을 확인할 수 있었다.