Bin Packing 이론과 2D 사각형 패킹 알고리즘
텍스처 아틀라스의 가장 밑단에 있는 알고리즘. UV island를 어떻게 작은 텍스처에 빈틈없이 욱여넣는가 — 이 문제의 정식 이름이 2D Rectangle Bin Packing이다.
핵심 요약
| 구분 | 내용 |
|---|---|
| 📖 정의 | 크기가 정해진 아이템들을 용량 고정 빈(bin)에 모두 담되, 빈의 수(또는 사용 면적)를 최소화하는 조합 최적화 문제 |
| 💡 핵심 | NP-hard 문제 → 휴리스틱·근사 알고리즘 사용. 텍스처 아틀라스에서는 MaxRects-BSSF가 사실상 표준 |
| 🎯 대상 | 텍스처 아틀라스, 스프라이트 시트, 폰트 글리프 캐시, LOD 텍스처 재패킹을 다루는 개발자 |
| ⚠️ 주의 | Power-of-Two 크기 제약, padding/bleeding, 회전 허용 여부가 결과 품질을 좌우한다 |
문서 탐색
목차
- Bin Packing 정의
- 1D Bin Packing 알고리즘
- 2D Rectangle Packing — Strip vs Bin
- Shelf 알고리즘
- Guillotine 알고리즘
- MaxRects 알고리즘
- Skyline 알고리즘
- Floor-Ceiling 알고리즘
- 알고리즘 성능 비교
- Texture Atlas 특화 고려사항
- 알고리즘 선택 가이드
Bin Packing 정의
수학적 정의 (Combinatorial Optimization)
입력
아이템 집합 I = {i₁, i₂, …, iₙ}
각 아이템의 크기 s(iₖ) ∈ (0, 1]
빈의 용량 = 1
목표
모든 아이템을 빈에 담되, 사용하는 빈의 수 B 를 최소화
제약
각 빈에 담긴 아이템 크기의 합 ≤ 1
문제 형태
| 형태 | 질문 |
|---|---|
| Decision Problem | ”k개의 빈으로 모두 담을 수 있는가?” — NP-complete |
| Optimization Problem | ”최소 몇 개의 빈이 필요한가?” — NP-hard |
NP-hard 증명 개요
Partition Problem(집합을 두 부분으로 합이 같게 분할)이 NP-complete이고, 이를 Bin Packing으로 환원할 수 있다.
Partition → Bin Packing 환원: “용량 = 전체 합의 절반인 빈 2개에 분할 가능한가?”
따라서 P=NP가 아닌 한 다항 시간 최적해는 존재하지 않으며, 실무에서는 근사 알고리즘 또는 휴리스틱을 사용한다.
차원별 비교
| 구분 | 정의 | 자유도 | 대표 응용 |
|---|---|---|---|
| 1D | 길이를 가진 아이템을 용량 C 빈에 담기 | 1 (크기) | 파일 서버 배치, 트럭 적재 |
| 2D | 사각형 아이템을 W×H 빈에 담기 | 2 (너비, 높이) | 텍스처 아틀라스, 판재 절단 |
| 3D | 직육면체 아이템을 W×H×D 빈에 담기 | 3 (W, H, D) | 컨테이너 적재, 팔레타이징 |
3D는 회전 자유도까지 더하면 6자유도가 된다.
오프라인 vs 온라인
| 구분 | 특징 | 대표 알고리즘 | 사용 사례 |
|---|---|---|---|
| 오프라인 (Offline) | 모든 아이템을 사전에 알고 있음 → 정렬 가능 | FFD, BFD, MaxRects | 텍스처 아틀라스 빌드 |
| 온라인 (Online) | 아이템이 순차 도착, 미래 미지 | First Fit, Skyline BL | 실시간 폰트 캐시, 메모리 할당 |
오프라인에서는 아이템을 내림차순 정렬하고 시작하는 것만으로 성능이 크게 향상된다.
1D Bin Packing 알고리즘
2D로 가기 전에 1D 클래식 알고리즘을 짚고 넘어간다. 핵심 사고방식이 동일하다.
| 알고리즘 | 방식 | 점근 근사비 | 시간복잡도 |
|---|---|---|---|
| Next Fit (NF) | 현재 빈에 안 들어가면 새 빈으로 | 2 · OPT | O(n) |
| First Fit (FF) | 첫 번째로 들어가는 빈에 배치 | 1.7 · OPT | O(n log n) |
| Best Fit (BF) | 남은 공간이 가장 작은 빈에 배치 | 1.7 · OPT | O(n log n) |
| First Fit Decreasing (FFD) | 내림차순 정렬 → FF | 11/9 · OPT + 6/9 ≈ 1.222 | O(n log n) |
| Best Fit Decreasing (BFD) | 내림차순 정렬 → BF | 11/9 · OPT (점근) | O(n log n) |
FFD 작동 예시
아이템 크기: [0.5, 0.5, 0.4, 0.4, 0.3, 0.3, 0.2, 0.2]
빈 용량: 1.0
FFD 정렬 후: [0.5, 0.5, 0.4, 0.4, 0.3, 0.3, 0.2, 0.2] (이미 정렬됨)
빈 1: [0.5, 0.4] 합 0.9, 남은 0.1
빈 2: [0.5, 0.4] 합 0.9, 남은 0.1
빈 3: [0.3, 0.3, 0.2, 0.2] 합 1.0, 남은 0.0
결과: 3개 빈 (OPT = 3, 빈 용량 합 = 2.8)
FFD의 타이트 바운드
FFD(I) ≤ 11/9 · OPT(I) + 6/9는 2007년 Springer 논문에서 공식 증명됐다.
2D Rectangle Packing — Strip vs Bin
2D 패킹은 두 가지 변형이 있다.
| 변형 | 정의 | 목표 |
|---|---|---|
| Strip Packing (SPP) | 너비 W 고정, 높이 무한대인 스트립에 사각형 배치 | 사용 높이 최소화 |
| Bin Packing (BPP) | W×H 빈 여러 개에 사각형 배치 | 빈의 수 최소화 |
텍스처 아틀라스는 보통 “정해진 크기(예: 2048×2048)에 최대한 욱여넣기” 형태이므로 BPP에 가깝지만, 알고리즘 자체는 두 변형 모두 비슷하게 적용된다.
둘 다 NP-hard다. SPP의 결정 문제도, BPP의 결정 문제도 NP-complete다.
Shelf 알고리즘
빈을 **수평 행(shelf)**으로 나누어 사각형을 순서대로 채운다. 가장 단순한 접근법.
NFDH (Next Fit Decreasing Height)
입력: 높이 기준 내림차순 정렬된 사각형들
┌──────────────────────────────┐
│[A:80×60][B:70×55][C:50×55] │ ← Shelf 1 (높이 60, 가장 큰 키)
├──────────────────────────────┤
│[D:90×40][E:60×40][F:40×40] │ ← Shelf 2 (높이 40)
├──────────────────────────────┤
│[G:30×20][H:25×20] │ ← Shelf 3 (높이 20)
└──────────────────────────────┘
규칙: 현재 선반에 안 들어가면 무조건 새 선반 생성
근사비: 2 · OPT (strip packing 기준)
FFDH (First Fit Decreasing Height)
현재 선반에 안 들어가면 → 기존 선반 중 처음으로 들어가는 선반 탐색 → 없으면 새 선반.
BFDH (Best Fit Decreasing Height)
들어갈 수 있는 선반 중 남은 너비가 가장 작은 선반에 배치 (낭비 공간 최소화).
| 알고리즘 | 공간 효율 | 속도 | 구현 난이도 |
|---|---|---|---|
| NFDH | 낮음 | O(n) | 매우 쉬움 |
| FFDH | 중간 | O(n²) | 쉬움 |
| BFDH | 중간-높음 | O(n log n) | 쉬움 |
단점: 선반의 높이가 가장 큰 아이템에 의해 결정되므로, 작은 아이템이 많을 때 낭비 공간이 크다.
Guillotine 알고리즘
빈을 기요틴(도마 자르듯) 직선 절단으로 재귀 분할한다. 사각형을 배치할 때마다 남은 공간을 두 개의 직사각형으로 쪼갠다.
초기 빈:
┌────────────────────────┐
│ │
│ 빈 (W×H) │
│ │
└────────────────────────┘
사각형 A (w×h) 배치 후 — 수직 분할(vertical split):
┌──────┬─────────────────┐
│ A │ │
│(w×h) │ Right (W-w × h)│
├──────┴─────────────────┤ ← 수평 분할선
│ Bottom (W × H-h) │
└────────────────────────┘
또는 수평 분할(horizontal split):
┌──────┬─────────────────┐
│ A │ Right (W-w × h)│
│(w×h) ├─────────────────┤
│ │ │
├──────┘ Bottom │
│ (w × H-h) │
└────────────────────────┘
Guillotine 분할 선택 휴리스틱
| 이름 | 분할 방향 선택 방식 |
|---|---|
| Short Axis Split (SAS) | 더 짧은 남은 변을 따라 분할 |
| Long Axis Split (LAS) | 더 긴 남은 변을 따라 분할 |
| Short Leftover Axis | 남는 공간의 짧은 쪽 기준 분할 |
| Long Leftover Axis | 남는 공간의 긴 쪽 기준 분할 |
- 장점: 구현 단순, 빠름, 메모리 효율적
- 단점: 기요틴 선이 가로막아 실제 사용 가능한 빈 공간보다 활용도가 떨어질 수 있음
MaxRects 알고리즘
Jukka Jylänki, “A Thousand Ways to Pack the Bin” (2010)에서 소개. 현재 가장 널리 쓰이는 2D 사각형 패킹 알고리즘. TexturePacker 등 상용 도구의 핵심.
핵심 아이디어 — Maximal Free Rectangle
배치된 사각형 주변에 남은 공간을 **여러 개의 최대 자유 직사각형(maximal free rectangle)**으로 관리한다.
사각형 배치 전 (빈 전체가 하나의 자유 영역):
┌────────────────────────┐
│ │
│ Free Rectangle F0 │
│ │
└────────────────────────┘
A(w×h) 배치 후 — 자유 직사각형 집합 갱신:
┌──────┬─────────────────┐
│ A │ │
│ │ F1 │ ← A 오른쪽
│ ├─────────────────┤
├──────┤ │
│ F2 │ F3 │ ← A 아래 + 그 외
│ │ │
└──────┴─────────────────┘
MaxRects는 겹치거나 포함되는 자유 직사각형을 제거하고
"확장 불가능한(maximal)" 자유 직사각형들만 유지한다.
Guillotine과의 차이: 자유 영역이 분할선에 구애받지 않고 최대 크기의 직사각형으로 관리된다. 배치된 아이템이 여러 자유 영역에 걸쳐도 가능하다.
MaxRects 배치 휴리스틱
| 이름 | 약자 | 선택 기준 |
|---|---|---|
| Best Short Side Fit | BSSF | 배치 후 남은 짧은 변이 최소인 자유 사각형 선택 |
| Best Long Side Fit | BLSF | 배치 후 남은 긴 변이 최소인 자유 사각형 선택 |
| Best Area Fit | BAF | 배치 가능한 자유 사각형 중 면적이 가장 작은 것 |
| Bottom-Left | BL | 가장 아래쪽, 그 다음 왼쪽 위치 |
| Contact Point | CP | 기존 사각형/벽과의 접촉 길이가 최대인 위치 |
Jylänki의 벤치마크 결론: BSSF와 BAF의 조합이 대부분의 경우 가장 높은 공간 활용률을 달성한다.
MaxRects 동작 흐름
1. 빈 전체를 하나의 MaxRect으로 초기화
2. 다음 배치할 사각형 선택 (보통 면적 내림차순)
3. 모든 MaxRect에 대해 휴리스틱 점수 계산
4. 최적 MaxRect에 사각형 배치
5. 이 사각형과 겹치는 모든 MaxRect 분할
- 겹치는 MaxRect R 을 최대 4개의 새 MaxRect으로 분할
6. 다른 MaxRect에 포함된 MaxRect 제거 (포함 관계 정리)
7. 모든 사각형이 배치될 때까지 2번으로 반복
| 항목 | 값 |
|---|---|
| 시간복잡도 | O(n² × |FreeRects|) — 실제로는 FreeRects가 작아 빠름 |
| 공간 활용률 | 상용 도구 기준 90% 이상 |
| 구현 복잡도 | 중상 |
Skyline 알고리즘
빈의 현재 채워진 상태를 **스카이라인(최상단 윤곽선)**으로만 추적한다. stb_rect_pack(C 라이브러리)가 채택한 알고리즘.
초기 상태 (바닥이 스카이라인):
높이
0 ──────────────────── (스카이라인)
0 10 20 30 40 50 너비
A(20×30) 배치 후:
높이
30 ████████
0 ████████──────────── (스카이라인)
0 10 20 30 40 50
B(15×20) 배치 후 — 스카이라인이 가장 낮은 위치에 배치:
높이
30 ████████
20 ██████
0 ██████████████────── (스카이라인)
0 10 20 30 40 50
데이터 구조
스카이라인 = 세그먼트 배열
[ (x=0, h=30, width=20),
(x=20, h=20, width=15),
(x=35, h=0, width=15) ]
다음 사각형 배치:
- 스카이라인의 각 세그먼트를 후보 위치로 시험
- Fit 검사: 너비 확장 시 높이 초과 없는지 확인
- Bottom-Left 선택: 가장 낮은 y, 그 다음 왼쪽 x
- 장점: 메모리 효율, MaxRects보다 빠름
- 단점: 스카이라인 뒤에 갇힌 빈 공간 복구 불가 (Wastemap으로 보완 가능)
Floor-Ceiling 알고리즘
선반 알고리즘의 변형. 선반의 **상단(ceiling)**과 **하단(floor)**을 모두 활용해 빈 공간을 위아래로 채운다.
Floor 방향 (아래→위): [A][B][C]
Ceiling 방향 (위→아래): [D][E]
─────────────────────────────────
공간 낭비: Floor / Ceiling이 만나는 중간 공백만
Shelf보다 효율적이지만 MaxRects보다 성능이 낮고 구현이 복잡해, 현재는 잘 쓰이지 않는다.
알고리즘 성능 비교
| 알고리즘 | 공간 활용률 | 속도 | 구현 복잡도 | 권장 사용 케이스 |
|---|---|---|---|---|
| Shelf (NFDH) | 낮음 (~60%) | 매우 빠름 | 매우 낮음 | 프로토타입, 실시간 온라인 |
| Shelf (FFDH/BFDH) | 중간 (~70%) | 빠름 | 낮음 | 간단한 스프라이트 시트 |
| Guillotine | 중간-높음 (~80%) | 빠름 | 낮음 | 메모리 제한 환경 |
| Skyline (BL) | 높음 (~85%) | 중간 | 중간 | 실시간 폰트 캐시(stb_rect_pack) |
| MaxRects (BSSF/BAF) | 매우 높음 (~92%) | 중간 | 높음 | 텍스처 아틀라스 최적화 |
| Korf Exact | 100% (최적) | 매우 느림 (지수) | 매우 높음 | 소규모 완벽 패킹 (학술) |
Texture Atlas 특화 고려사항
1. 회전 허용 (Rotation)
90도 회전을 허용하면 공간 활용률이 평균 2~5% 향상된다.
회전 적용 예:
원본 [100×30]이 빈 공간 [35×110]에 매칭 불가
→ 회전 후 [30×100] → 매칭 가능
회전 사용 시 GPU 텍스처 좌표(UV) 변환이 필요하며, 일부 압축 포맷(BC/ETC 타일 정렬)에서 추가 처리가 필요하다.
2. Power-of-Two (POT) 제약
구형 GPU 및 일부 압축 포맷(DXT/BCn, ETC, ASTC)은 아틀라스 전체 해상도가 2의 거듭제곱이어야 한다.
허용: 256×256, 512×512, 1024×512, 2048×2048
비허용: 300×200, 1000×1000 (NPOT)
패킹 알고리즘은 내부적으로 아틀라스 크기를 2의 거듭제곱 단계로 올리면서 최소 낭비 크기를 선택한다.
3. Padding / Bleed / Gutter
┌───────────────────────────────────┐
│ (아틀라스 경계) │
│ ┌─────────────────────────────┐ │
│ │ │ │ ← border padding (margin)
│ │ ┌───────────┐ ─ ─ ─ ─ ─ │ │
│ │ │ Bleed/ │ gutter │ │
│ │ │ Padding │──────────── │ │
│ │ │ (2~4px) │ │ │
│ │ └───────────┘ │ │
│ │ UV Island (실제 텍스처) │ │
│ └─────────────────────────────┘ │
└───────────────────────────────────┘
| 용어 | 역할 |
|---|---|
padding | 인접 텍셀 간 최소 간격 (일반적으로 2~8px) |
bleed | UV 경계 픽셀을 바깥으로 복제 → 밉맵·필터링 시 아티팩트 방지 |
gutter | padding + bleed 전체 여백. 권고: gutter = 2 × padding |
자세한 차이는 Bleed 절 참고.
4. 비사각형 패킹 (UV Island / Polygon Packing)
UV island는 삼각형·다각형 형태이므로, 사각형 패킹을 적용하려면 AABB(Axis-Aligned Bounding Box) 또는 **OBB(Oriented Bounding Box)**로 감싼다.
1. UV Island 추출
3D 메시 → UV 언래핑 → Island들 = {I₁, I₂, …}
2. 각 Island의 AABB 계산
Island → 최소 외접 직사각형 → 사각형 패킹 적용
3. 사각형 패킹 수행 (MaxRects 등)
4. Island 재배치 + UV 좌표 변환
UV_new = (UV_old − bbox_min) / bbox_size × island_uv_size + island_uv_offset
5. 미사용 삼각형 면적 낭비 존재 (사각형 내부지만 island가 차지하지 않는 빈 공간)
→ 고급 도구(UVPackmaster)는 임의 각도 회전 + 볼록 껍질 기반 패킹으로 낭비 감소
알고리즘 선택 가이드
3D / glTF 워크플로 알고리즘 선택 트리
사각형 수 < 50개?
├── YES → Guillotine (빠르고 충분)
└── NO ↓
실시간 생성 필요? (게임 런타임 글리프 캐시 등)
├── YES → Skyline BL (stb_rect_pack 사용)
└── NO ↓
최고 공간 효율 필요? (오프라인 아틀라스 빌드)
├── YES → MaxRects BSSF 또는 BAF
└── 중간 정도면 → FFDH Shelf
회전 허용?
├── YES → MaxRects + rotation flag
└── NO → MaxRects without rotation
Power-of-Two 제약?
└── 알고리즘 외부에서 아틀라스 크기를 PoT로 올림
(빈 크기를 128 → 256 → 512 → … 으로 단계별 시도 후 최소 선택)
핵심 정리
1D Bin Packing 2D Rectangle Packing
─────────────── ─────────────────────
NP-hard (결정 NP-complete) NP-hard (더 복잡)
FF / BF: ~1.7 근사비 Shelf: ~1.7 근사비
FFD / BFD: 11/9 ≈ 1.222 근사비 MaxRects: 실질 92%+ 효율
오프라인 최선 = FFD 오프라인 최선 = MaxRects BSSF
온라인 최선 = First Fit 온라인 최선 = Skyline BL
텍스처 아틀라스 파이프라인:
UV Island 추출 → AABB 계산 → MaxRects 패킹
→ Padding/Bleed 적용 → PoT 크기 조정 → KTX2/Basis 압축
문서 탐색
참고 자료
- A Thousand Ways to Pack the Bin — Jukka Jylänki (2010) — MaxRects 원전
- juj/RectangleBinPack GitHub — Jylänki 공식 구현
- Two-dimensional packing problems: A survey — Lodi/Martello/Vigo (2002) — 2D 패킹 서베이
- Optimal Rectangle Packing — Korf (ICAPS 2003) — 완벽 패킹의 학술적 기준
- First-fit-decreasing bin packing — Wikipedia
- FFD Tight Bound Proof — Springer (2007)
- MaxRects 알고리즘 해설 — secnot/rectpack DeepWiki
- Skyline Algorithm 구현 — jvernay.fr
- stb_rect_pack.h (Skyline BL 구현)
- Strip packing problem — Wikipedia