실시간으로 수십억 개의 복셀 렌더링하는 알고리즘 이해하기

복셀의 개념과 활용

복셀은 3D 공간을 작은 단위로 나누는 큐브 형태의 데이터로, 2D 픽셀의 확장판입니다. 각 복셀에는 간단히 "비어 있음/채워짐" 같은 1비트 정보부터, 다양한 재질 정보를 담을 수도 있어요. 복셀 구조는 변환하지 않고 직접 그릴 수 있다는 장점이 있습니다.

복셀 데이터를 효율적으로 저장하는 방법

3차원 좌표의 복셀 데이터를 1차원 배열에 저장하려면 적절한 좌표 변환 공식이 필요합니다. 이를 통해 메모리 활용을 극대화할 수 있는데, 예를 들어 하나의 3D 좌표 (x,y,z)를 배열 인덱스로 변환해 복셀을 저장하게 됩니다. 공간의 인접한 복셀을 메모리상에 가까이 배치하면 성능이 올라갑니다.

카메라에서 복셀을 보는 원리: 레이의 정의

복셀 렌더링에서는 각 화면 픽셀마다 "레이"라는 가상의 선을 보내 복셀에 닿는지 판별합니다. 레이는 시작점(Origin)과 방향(Direction)으로 정의되며, 방향의 크기는 꼭 1일 필요는 없습니다.

복셀을 따라가는 레이 트래버설의 핵심

레이(선)가 공간 속을 지나면서 만나는 복셀을 순서대로 확인하는 과정이 바로 레이 트래버설입니다. 목표는 화면 각 픽셀의 레이가 부딪히는 복셀을 빠르게 찾는 것입니다. 가장 단순한 방식은 아주 작은 간격씩 레이를 진행시켜 확인하는 건데, 이는 복셀을 놓칠 수도 있고 속도가 매우 느려 비효율적입니다.

Ray-AABB 교차 알고리즘 이해하기

복셀들이 모여 있는 공간(그리드)은 직육면체(AABB)로 둘러싸여 있습니다. 레이가 이 영역 안에 들어가는 첫 위치를 찾으려면 수학적으로 레이와 AABB의 교차 여부, 그리고 진입·탈출 지점을 계산해야 해요. 이때 "슬랩(slabs) 방법"이 많이 사용됩니다.

속도 향상을 끌어내는 똑똑한 레이 이동 방법

보다 빠른 복셀 탐색을 위해, Amanatides & Woo의 알고리즘을 사용합니다. 이 방식에서는 레이가 다음에 만날 축(Plane)을 미리 계산해서, 가장 빨리 닿는 축 방향으로 복셀 좌표를 한 번에 이동시킵니다. 이렇게 하면 불필요한 연산 없이 필요한 복셀만 순서대로 확인할 수 있어 매우 빠릅니다.

GPU로 대량의 복셀을 실시간 렌더링하기

GPU의 컴퓨트 셰이더 기능을 활용해 각 화면 픽셀에 대해 독립적으로 레이 트래버설을 실행하면, 복셀 수십억 개도 실시간으로 렌더링할 수 있습니다. Stanford Bunny 모델과 같은 복잡한 3D 데이터를 복셀로 변환해 적용할 수 있죠.

복셀 데이터 구조 개선으로 FPS 10배 올리기

복셀을 배열로 저장할 때, 단순히 1차원으로 펼치면 성능이 낮아집니다. Z오더(Z-order curve)라는 방식을 쓰면 공간상 가까운 복셀이 메모리에서도 가까워지고, 캐시 적중률이 올라가 GPU 연산이 훨씬 빨라집니다. 이를 실제 3D 텍스처(이미지)로 GPU에 저장하면 한층 더 최적화되어 초당 프레임(FPS)이 10배 늘어나는 결과를 얻을 수 있습니다.

앞으로의 발전 방향

복셀 렌더링은 아직도 개선할 점이 많습니다. 예를 들어, 공간 전체가 비어있는 부분은 한 번에 통과하는 "스파스 볼 옥트리(Sparse Voxel Octree)" 구조를 적용하거나, 데이터 압축으로 메모리 사용을 줄여 더 많은 복셀을 다룰 수 있습니다. 이런 고급 주제는 이후 심화된 내용에서 더 깊이 탐구할 수 있습니다.

출처 및 참고 :