Engineering & Tech

3D 빈 패킹(Bin Packing)의 악몽, 수학과 GPU로 해결한 이야기

물류 효율화의 난제인 3D 빈 패킹 문제를 FFT(고속 푸리에 변환)와 GPU 연산을 활용해 해결한 경험을 공유합니다. psacking 라이브러리 활용법과 트러블슈팅 수록.

김영태

테크리드

안녕하세요. 풀링포레스트 테크리드 김영태입니다.

물류나 커머스 도메인에서 일해보신 분들이라면 한 번쯤 '공기 배송'이라는 말을 들어보셨을 겁니다. 상자는 거대한데 막상 열어보면 작은 물건 하나만 덩그러니 들어있는 상황, 혹은 트럭 적재 공간이 꽉 찼다고 시스템은 말하는데 실제로는 빈 공간이 숭숭 뚫려 있는 상황 말이죠. 저희 팀 역시 물류 효율화를 고민하면서 이 '적재 최적화(Bin Packing)' 문제 때문에 꽤나 골머리를 앓았습니다.

솔직히 고백하자면, 처음에는 만만하게 봤습니다. "그냥 테트리스 하듯이 빈 공간 찾아서 넣으면 되는 거 아니야?"라고 생각했었죠. 하지만 현실의 물건들은 정사각형 블록이 아니었습니다. 'ㄱ'자 모양의 부품, 둥근 원통형 용기, 기하학적인 장식품들이 쏟아져 들어오자 기존의 단순한 휴리스틱 알고리즘들은 속수무책이었습니다. 계산 시간은 오래 걸리는데 정작 적재 효율(Density)은 50%를 넘기기 힘들었으니까요.

막막했던 차에, SIGGRAPH 2023에 발표된 흥미로운 논문 하나를 구현한 오픈소스 라이브러리를 발견했습니다. 바로 psacking이라는 라이브러리입니다. 오늘은 이 라이브러리를 테스트하며 겪은 경험과 배운 점을 공유하려 합니다.

왜 기존 방식은 실패했나?

일반적인 3D 패킹 알고리즘은 물체를 다각형(Polygon)의 집합으로 봅니다. 물건 A와 물건 B가 겹치는지 확인하려면 수많은 삼각형끼리의 교차 검사를 수행해야 합니다. 물건이 복잡해질수록 연산량은 기하급수적으로 늘어납니다.

그래서 보통은 물체를 단순한 육면체(Bounding Box)로 가정하고 계산합니다. 여기서 문제가 발생합니다. 'ㄱ'자 모양의 물건을 육면체로 감싸버리면, 그 안의 빈 공간은 영원히 활용할 수 없는 데드 스페이스가 되어버립니다. 저희가 겪은 비효율의 원인이 바로 여기 있었습니다.

수학적 접근: 충돌 감지를 신호 처리로 풀다

이 라이브러리가 채택한 'Spectral Packing' 방식은 접근법이 완전히 다릅니다. 물체를 기하학적 도형이 아니라, 3차원 공간상의 복셀(Voxel, 3D 픽셀) 데이터로 변환합니다. 그리고 이 복셀 데이터 간의 충돌 여부를 FFT(고속 푸리에 변환)를 이용해 계산합니다.

쉽게 설명하면, 물체의 배치를 마치 '신호(Signal)'처럼 처리하는 것입니다. FFT를 사용하면 두 신호(물체)가 겹치는 지점을 수학적으로 매우 빠르게 찾아낼 수 있습니다. 복잡한 다각형 연산 대신, 행렬 연산으로 문제를 치환해버린 것이죠. 덕분에 GPU의 병렬 처리 능력을 극한으로 활용할 수 있게 됩니다.

코드로 보는 3D 패킹

백문이 불여일견, 실제 코드를 한번 보시죠. 이 라이브러리는 Python API를 제공해서 사용하기가 꽤 직관적입니다.

from spectral_packer import BinPacker
import numpy as np

# 1. 트레이(적재 공간) 크기 설정 (단위: 복셀)
# 실제 100cm x 100cm x 100cm 공간을 1cm 단위 복셀로 표현한다고 가정
packer = BinPacker(tray_size=(100, 100, 100))

# 2. 테스트용 아이템 생성 (numpy 배열)
# 실제로는 STL 파일을 voxelize_file 메서드로 변환해서 씁니다.
items = [
    np.ones((20, 20, 20), dtype=np.int32), # 20x20x20 박스
    np.ones((10, 50, 10), dtype=np.int32), # 길쭉한 막대 형태
    np.ones((30, 30, 5), dtype=np.int32),  # 납작한 판 형태
]

# 3. 패킹 실행
# 내부적으로 GPU를 사용해 FFT 연산을 수행합니다.
result = packer.pack_voxels(items)

print(f"배치 성공: {result.num_placed} / {len(items)}")
print(f"적재 밀도: {result.density:.1%}")

가장 인상적이었던 건 속도였습니다. 수백 개의 복잡한 STL 파일들을 던져주어도, CUDA가 지원되는 GPU 환경에서는 순식간에 최적의 위치를 찾아냈습니다. 특히 서로 맞물릴 수 있는(Interlocking) 구조의 물체들을 기가 막히게 끼워 맞추는 모습을 보며 "이게 수학의 힘이구나" 싶었습니다.

트러블슈팅: 화려함 뒤의 제약 사항

물론 모든 것이 순탄치만은 않았습니다. 저희 팀의 개발 서버에 이 코드를 올리자마자 에러가 터졌습니다.

RuntimeError: CUDA error: no kernel image is available for execution on the device

알고리즘이 성공적으로 돌아가려면 NVIDIA GPU (Compute Capability 6.0 이상)를 필수적으로 요구합니다. 저희 개발 서버 중 일부는 구형 GPU를 쓰거나 CPU 전용 인스턴스였던 게 문제였습니다.

또한, 복셀 해상도(Resolution) 설정이 중요했습니다. 해상도를 너무 높이면(voxel_resolution=512 이상) 정밀도는 올라가지만, GPU 메모리(VRAM)가 순식간에 동나버리는 OOM(Out Of Memory) 현상을 겪었습니다. 반대로 너무 낮추면 물체의 디테일이 뭉개져서 실제로는 안 들어가는 물건을 들어간다고 판단하는 오류가 생겼습니다.

결국 저희는 다음과 같은 타협점을 찾았습니다.

인프라: GPU 인스턴스(T4 또는 A10G 급)를 배치 작업 시에만 동적으로 띄워서 처리.
해상도: 전체 트레이 크기 대비 적절한 복셀 크기를 계산하여 동적으로 해상도 조절 (보통 128~256 사이).

마치며

개발을 하다 보면 때로는 "이미 있는 라이브러리 가져다 쓰면 되지"라고 쉽게 생각하게 됩니다. 하지만 그 라이브러리의 내부 원리를 모르면, 인프라 제약이나 엣지 케이스에 부딪혔을 때 해결할 방법이 없습니다.

이번 경험을 통해, 단순히 코드를 짜는 것을 넘어 알고리즘이 하드웨어(GPU)와 어떻게 상호작용하는지, 그리고 수학적 모델링(FFT)이 현실의 문제(물류)를 어떻게 해결하는지 이해하는 것이 얼마나 중요한지 뼈저리게 느꼈습니다.

혹시 여러분도 복잡한 형상의 물체를 다루거나, 최적화 문제로 고민하고 계신다면 이 psacking 라이브러리와 그 배경이 된 논문을 한번 살펴보시는 걸 추천합니다. 빡빡한 일정 속에서 마주한 이 우아한 수학적 해결책이, 여러분에게도 시원한 청량감이 되기를 바랍니다.

오늘도 빈틈없이 꽉 찬 하루 보내세요. 감사합니다.