가속 구조

가속 구조는 광선이 어느 물체에 맞는지 빨리 찾게 해 줍니다. 장면의 물체들을 상자에 나눠 담아 둡니다. 광선이 빗나간 상자는 그 안을 보지 않고 건너뜁니다. 레이 트레이싱으로 화면을 그리려면 먼저 이 구조를 지어 둬야 합니다.

쉽고 빠른 이해

레이 트레이싱은 화면의 점마다 눈에서 직선을 쏘아 그 점의 색을 정합니다. 이 직선이 광선입니다.

가속 구조는 광선이 맞을 물체를 빨리 골라 주는 장면의 인덱스입니다. 데이터베이스 테이블에 거는 인덱스와 같은 일을 장면에 해 줍니다.

없으면 광선 하나마다 장면의 삼각형을 전부 하나씩 맞대 봐야 합니다. 화면 한 장에 광선이 수백만 개라 그렇게는 못 그립니다.

어떻게 도나:

1. 그리기 전에 물체마다 상자를 씌웁니다. 상자들을 더 큰 상자로 묶어 트리로 쌓습니다
2. 광선을 쏘면 맨 바깥 상자부터 맞는지 봅니다
3. 빗나간 상자는 안을 건너뜁니다. 맞은 상자만 따라 내려가 마지막에 삼각형 몇 개만 맞대 봅니다

대가가 있습니다. 짓는 데 시간과 메모리가 듭니다. 물체가 움직이면 다시 짓거나 상자 크기를 다시 재야 합니다.

물체가 몇 개뿐이면 하나씩 맞대 보는 편이 더 쌉니다. 광선을 쏘지 않는 보통 그리기 방식에는 필요 없습니다.

상세

이 절은 가속 구조가 왜 필요한지, 상자를 어떻게 쌓는지, 광선이 그 상자들을 어떻게 따라 내려가는지를 봅니다. 그다음 그래픽 카드를 다루는 프로그래밍 도구들이 이 구조를 두 층으로 나눠 다루는 방식과 지을 때 치르는 비용을 봅니다.

의자 열 개와 공 하나가 놓인 방을 줄곧 예로 씁니다.

광선 하나가 따지는 횟수

레이 트레이싱은 눈에서 화면의 점 하나를 지나는 직선을 쏘아 그 점의 색을 정하는 그리기 방식입니다. 이 직선을 광선이라고 부릅니다. 광선이 처음 맞은 물체의 색이 그 점에 칠해집니다.

입체 모델은 대개 작은 삼각형을 수천에서 수만 개 이어 붙여 만듭니다. 그래서 광선이 무엇에 맞았는지 알려면 광선과 삼각형이 겹치는지를 따져야 합니다. 이 계산을 교차 판정이라고 부릅니다.

교차 판정 한 번은 가볍습니다. 문제는 횟수입니다. 화면이 가로 1920 점, 세로 1080 점이면 광선이 약 207만 개입니다. 장면에 삼각형이 100만 개 있다고 해 봅시다. 광선마다 전부 맞대 본다면 한 장에 약 2조 번을 따져야 합니다.

반사와 그림자를 보려고 광선을 더 쏘면 횟수는 그만큼 또 늘어납니다. 삼각형을 하나도 빠짐없이 맞대 보는 방식으로는 화면 한 장도 제때 못 그립니다.

장면에 거는 인덱스

인덱스 없는 테이블에서 조건에 맞는 행을 찾으려면 모든 행을 읽어야 합니다. 인덱스를 걸어 두면 트리를 몇 단계만 내려가 원하는 행에 닿습니다.

가속 구조는 장면에 거는 인덱스입니다. 광선 하나가 모든 삼각형을 맞대 보는 대신, 맞을 수 있는 삼각형 몇 개만 골라냅니다.

인덱스와 닮은 점이 하나 더 있습니다. 미리 지어 둬야 합니다. 데이터가 바뀌면 같이 고쳐야 합니다.

상자로 감싸기

물체를 곧장 맞대 보는 대신 먼저 상자로 감쌉니다. 물체를 빈틈없이 품는 가장 작은 상자를 경계 상자라고 부릅니다. 광선이 상자를 빗나가면 그 안의 물체도 반드시 빗나갑니다.

상자는 대개 모서리가 x · y · z 축과 나란한 것을 씁니다. 이런 상자를 AABB(Axis-Aligned Bounding Box, 축 정렬 경계 상자)라고 부릅니다. 축과 나란하면 상자를 꼭짓점 두 개로 적을 수 있습니다. x · y · z 좌표가 모두 가장 작은 꼭짓점과, 모두 가장 큰 꼭짓점입니다. 광선이 상자를 지나는지도 비교 몇 번으로 가립니다.

의자 하나가 삼각형 수천 개로 되어 있어도 상자는 하나입니다. 광선이 의자 상자를 빗나가면 삼각형 수천 개를 검사 한 번으로 건너뜁니다.

상자 안에 상자를 넣는 트리

상자 하나로는 모자랍니다. 장면 전체를 감싼 상자는 거의 모든 광선이 맞기 때문입니다. 그래서 상자를 겹겹이 쌓습니다.

먼저 장면의 물체들을 두 무리로 가르고 무리마다 상자를 새로 씌웁니다. 각 무리를 다시 둘로 가릅니다. 상자 하나에 삼각형이 몇 개만 남을 때까지 이 일을 되풀이합니다.

이렇게 쌓은 상자의 트리를 BVH(Bounding Volume Hierarchy, 경계 볼륨 계층)라고 부릅니다. 경계 볼륨은 경계 상자처럼 물체를 감싸는 도형을 넓게 이르는 말입니다. 그래픽 카드의 레이 트레이싱은 대개 BVH 를 가속 구조로 씁니다.

의자 열 개와 공 하나가 놓인 방이면 위쪽 세 층은 이렇게 생깁니다.

flowchart TD
    R["방 전체 상자"]
    R --> A["왼쪽 무리 상자 · 의자 1~5"]
    R --> B["오른쪽 무리 상자 · 의자 6~10 · 공"]
    A --> A1["의자 1~2 상자"]
    A --> A2["의자 3~5 상자"]
    B --> B1["의자 6~8 상자"]
    B --> B2["의자 9~10 · 공 상자"]

그림 아래로도 층이 이어집니다. 의자 하나의 상자가 다시 등받이 · 다리 같은 부분의 상자로 나뉩니다. 맨 아래 상자에는 삼각형이 몇 개씩 담깁니다. 트리의 맨 끝 마디를 잎이라고 부릅니다.

광선이 트리를 따라 내려가는 길

이 소절은 광선 하나가 위 트리를 어떻게 내려가는지 봅니다. 광선이 공을 향해 날아간다고 해 봅시다.

flowchart TD
    R["방 전체 상자 · 맞음"] --> A["왼쪽 무리 상자 · 빗나감"]
    R --> B["오른쪽 무리 상자 · 맞음"]
    A --> AS["의자 1~5 전부 건너뜀"]
    B --> B1["의자 6~8 상자 · 빗나감"]
    B --> B2["의자 9~10 · 공 상자 · 맞음"]
    B1 --> BS["의자 6~8 전부 건너뜀"]
    B2 --> T["그 아래 상자를 더 내려가 삼각형 몇 개만 맞대 본다"]

방 전체 상자는 맞습니다. 왼쪽 무리 상자는 빗나가므로 의자 다섯 개의 삼각형을 하나도 안 봅니다. 오른쪽 무리 안에서도 의자 6~8 상자를 빗나가 세 개를 더 건너뜁니다.

광선이 삼각형과 겹치는 것을 적중이라고 부릅니다. 한 광선에 적중이 여럿이면 눈에서 가장 가까운 것이 그 점에 보이는 물체입니다.

맞은 상자가 둘이면 둘 다 내려가 봐야 합니다. 상자끼리 겹칠 수 있기 때문입니다. 한쪽 상자에서 적중을 찾아도, 다른 쪽 상자에 더 가까운 적중이 있을 수 있습니다.

둘 다 맞았을 때는 광선이 출발한 곳에서 가까운 상자부터 봅니다. 가까운 상자에서 적중을 먼저 찾을 가능성이 크기 때문입니다.

적중을 하나 찾으면 내려갈 상자가 줄어듭니다. 광선이 상자에 닿는 지점이 이미 찾은 적중보다 멀면 그 상자는 들어가 보지 않아도 됩니다. 그 안의 어떤 적중도 이미 찾은 것보다 멀기 때문입니다.

트리를 끝까지 내려가며 이렇게 상자를 고르는 과정을 광선 순회라고 부릅니다. 순회가 끝나면 남은 적중 가운데 가장 가까운 것이 그 광선의 답입니다.

레이 트레이싱을 지원하는 그래픽 카드는 대개 광선 순회를 맡는 전용 회로를 갖고 있습니다. 상자 트리를 따라 내려가는 일과 삼각형 교차 판정을 이 회로가 합니다.

복잡도

이 소절은 가속 구조를 짓고 쓰는 데 드는 비용을 물체 수에 견줘 봅니다. O(n) 은 비용이 물체 수 n 에 비례해 늘어난다는 뜻입니다. O(log n) 은 물체가 두 배가 될 때 비용이 한 단계씩만 늘어난다는 뜻입니다.

이 소절의 n 은 트리에 담는 물체 수입니다. 삼각형을 하나씩 담는 트리라면 삼각형 수가 곧 n 입니다.

물체를 반씩 나누면 트리의 높이는 약 log₂ n 입니다. 삼각형 100만 개면 스무 층 안팎입니다. 잘 지은 트리에서 광선 하나는 층마다 상자 몇 개만 보므로 찾는 비용이 대개 log n 에 비례합니다.

최악은 상자가 서로 크게 겹칠 때입니다. 길고 가는 물체가 장면을 비스듬히 가로지르면 그 물체의 상자가 장면 대부분을 덮습니다. 그러면 광선이 여러 갈래를 함께 내려가야 합니다. 끝내 n 개를 거의 다 보게 됩니다.

표의 「상자 다시 재기」는 물체가 움직였을 때 쓰는 방법입니다. 아래 「트리를 짓는 법과 고치는 법」 소절에서 풉니다.

다른 모양의 가속 구조

BVH 는 물체를 무리로 나눕니다. 물체 대신 공간을 나누는 가속 구조도 있습니다. 무엇을 나누는지로 견주면 이렇습니다.

공간을 나누면 칸끼리 겹치지 않습니다. 대신 물체 하나가 여러 칸에 걸칠 수 있습니다. 물체를 나누면 물체는 한 무리에만 듭니다. 대신 무리의 상자끼리 겹칠 수 있습니다.

두 층으로 나눈 가속 구조

그래픽 카드의 계산 칩을 GPU(Graphics Processing Unit, 그래픽 처리 장치)라고 부릅니다. 프로그램이 GPU 에 일을 시킬 때 쓰는 약속을 API(Application Programming Interface, 응용 프로그램 인터페이스)라고 부릅니다.

GPU 용 API 가운데 Vulkan과 Direct3D 12는 레이 트레이싱 기능을 갖고 있습니다. Vulkan 은 여러 운영체제에서 두루 쓰는 API 입니다. Direct3D 12 는 마이크로소프트가 만든 API 입니다. 둘 다 가속 구조를 두 층으로 나눠 짓게 합니다.

아래층은 물체 하나의 모양을 담습니다. 의자 모델의 삼각형들로 지은 BVH 가 여기에 듭니다. 이 층을 BLAS(Bottom-Level Acceleration Structure, 하위 수준 가속 구조)라고 부릅니다.

아래층은 물체를 원점에 둔 좌표로 짓습니다. 의자를 방 안 어디에 놓을지는 아래층이 모릅니다. 놓는 곳은 위층이 정합니다.

위층은 아래층 구조들을 장면 어디에 어떻게 놓을지를 담습니다. 이 층을 TLAS(Top-Level Acceleration Structure, 상위 수준 가속 구조)라고 부릅니다.

위층의 항목 하나를 인스턴스라고 부릅니다. 인스턴스는 어느 아래층 구조를 쓸지를 가리킵니다. 그 구조를 옮기고 돌리고 늘릴 변환 행렬도 함께 담습니다.

flowchart TD
    subgraph TOP["위층 TLAS · 어디에 놓나"]
        C1["인스턴스 · 의자 1"]
        C2["인스턴스 · 의자 2"]
        CR["인스턴스 · 의자 3 … 의자 10 · 하나씩 여덟 개"]
        BP["인스턴스 · 공"]
    end
    subgraph BOT["아래층 BLAS · 물체 하나의 모양"]
        CM["의자 모양 BVH"]
        BM["공 모양 BVH"]
    end
    C1 --> CM
    C2 --> CM
    CR --> CM
    BP --> BM

그림은 의자 3~10 의 인스턴스 여덟 개를 한 칸으로 줄여 그렸습니다. 의자 열 개를 놓아도 아래층의 의자 모양은 하나입니다. 모양을 한 번만 담으므로 의자를 더 놓아도 아래층은 커지지 않습니다.

광선은 위층 트리를 먼저 내려갑니다. 인스턴스에 닿으면 아래층으로 넘어가기 전에 광선을 물체의 좌표로 옮겨야 합니다. 아래층은 물체를 원점에 둔 좌표로 지어 두었기 때문입니다.

인스턴스의 변환 행렬은 물체를 원점에서 방 안으로 옮깁니다. 광선은 그 반대 방향으로 옮깁니다. 그러면 광선과 물체가 같은 좌표 위에 놓입니다. 그 상태로 아래층 트리를 내려갑니다.

두 층으로 나누면 움직임을 싸게 처리할 수 있습니다. 의자를 옮기면 위층 인스턴스의 행렬만 바꿉니다. 그리고 위층만 다시 짓습니다. 위층 항목은 물체 수만큼이라 삼각형 수보다 훨씬 적습니다.

트리를 짓는 법과 고치는 법

이 소절은 가속 구조를 지을 때 고르는 것과, 물체가 움직였을 때 고치는 두 방법을 봅니다.

트리의 질은 무리를 어디서 가르는지로 정해집니다. 상자의 겉넓이가 클수록 광선이 그 상자에 맞을 가능성이 큽니다. 그래서 두 무리의 상자 겉넓이와 안에 든 삼각형 수를 견줘 가를 곳을 고르는 방법을 흔히 씁니다.

이 방법을 SAH(Surface Area Heuristic, 표면적 휴리스틱)라고 부릅니다. 가를 곳을 꼼꼼히 고를수록 짓기는 느려집니다. 대신 찾기는 빨라집니다.

API 는 지을 때 어느 쪽을 바랄지 고르게 합니다. 빨리 찾는 트리를 원하면 짓기에 시간을 더 씁니다. 빨리 지어야 하면 찾는 데 시간이 조금 더 드는 트리를 받아들입니다.

물체가 움직이면 가속 구조도 고쳐야 합니다. 방법은 둘입니다. 「다시 짓기」는 트리를 처음부터 새로 짓는 것입니다. 「상자 다시 재기」는 트리 모양은 두고 상자 크기만 다시 재는 것입니다.

상자 다시 재기는 빠릅니다. 대신 물체들이 처음 놓인 곳에서 멀리 흩어지면 상자가 커지고 서로 겹칩니다. 그러면 광선이 내려갈 갈래가 늘어 찾기가 느려집니다. 그래서 상자를 다시 재며 쓰다가 가끔 다시 짓습니다.

캐릭터가 팔다리를 움직이듯 물체의 모양 자체가 바뀌면 그 물체의 아래층을 다시 짓거나 상자를 다시 잽니다. 의자를 옮기듯 모양은 그대로이고 놓인 곳만 바뀌면 아래층은 손대지 않습니다. 위층만 다시 짓습니다.

API 에서 가속 구조를 짓는 순서

앱이 API 로 가속 구조를 짓는 일은 세 단계입니다. 먼저 필요한 메모리 크기를 묻습니다. 그 크기만큼 버퍼를 잡습니다. 마지막으로 짓기 명령을 GPU 에 보냅니다.

크기를 먼저 묻는 까닭은 API 에서 가속 구조의 속이 안 보이기 때문입니다. 앱은 삼각형과 인스턴스만 넘깁니다. 트리를 어떤 모양으로 지을지는 GPU 의 드라이버가 정합니다. 모양을 모르는 앱은 크기도 모릅니다.

드라이버는 프로그램의 명령을 칩이 알아듣는 꼴로 바꿔 주는 소프트웨어입니다. GPU 를 만든 회사마다 칩의 회로가 달라 잘 맞는 트리 모양도 다릅니다. 그래서 모양을 드라이버에 맡깁니다.

버퍼는 GPU 메모리에 잡은 데이터 덩어리입니다. 다 지은 트리는 앱이 잡아 둔 버퍼에 담깁니다.

짓기 명령은 커맨드 버퍼에 담아 보냅니다. 커맨드 버퍼는 GPU 에 시킬 명령을 모아 한꺼번에 넘기는 목록입니다. 앱은 명령을 하나씩 보내지 않고 이 목록에 모아 둡니다.

세 단계를 앱 · 드라이버 · GPU 가 나눠 맡으면 이렇습니다.

sequenceDiagram
    participant 앱
    participant 드라이버
    participant GPU
    앱->>드라이버: 삼각형 수와 짓는 방식을 알리고 크기를 묻는다
    드라이버-->>앱: 필요한 메모리 크기를 알려 준다
    Note over 앱: 그 크기만큼 버퍼를 잡는다
    앱->>GPU: 짓기 명령을 커맨드 버퍼에 담아 보낸다
    GPU->>GPU: 버퍼 안에 트리를 짓는다

셰이더에 가속 구조 넘기기

다 지은 가속 구조는 셰이더에 넘깁니다. 셰이더는 GPU 에서 도는 작은 프로그램입니다. 광선을 쏘고 맞은 물체의 색을 정하는 일도 셰이더가 합니다.

셰이더는 디스크립터로 가속 구조를 받습니다. 디스크립터는 셰이더가 읽을 데이터가 GPU 메모리 어디에 있는지 알려 주는 짧은 기록입니다.

디스크립터에는 그것이 가리키는 데이터의 종류가 붙습니다. 이 종류를 디스크립터 타입이라고 부릅니다. 가속 구조를 넘기는 디스크립터 타입이 따로 있습니다.

두 API 가 부르는 이름

지금까지 본 짓기와 넘기기를 두 API 는 이런 이름으로 부릅니다.

Vulkan 은 가속 구조를 따로 된 객체로 다룹니다. Direct3D 12 는 버퍼 안의 한 영역을 가속 구조로 씁니다.

애플 기기의 그래픽스 API 인 Metal도 MTLAccelerationStructure 라는 이름으로 같은 것을 둡니다.

쓸 때와 안 쓸 때

광선을 쏘는 방식은 둘입니다. 하나는 레이 트레이싱 파이프라인입니다. 광선이 맞았을 때와 빗나갔을 때 돌릴 셰이더를 미리 묶어 두면, GPU 가 광선의 결과에 맞는 셰이더를 불러 줍니다.

다른 하나는 레이 쿼리입니다. 셰이더 안에서 광선을 쏘아 답을 곧바로 받습니다. 어느 쪽이든 가속 구조가 있어야 합니다. 두 방식 모두 광선을 쏘는 명령에 가속 구조를 함께 넘깁니다.

가속 구조는 대개 게임 엔진이 안쪽에서 짓고 고칩니다. 그래서 엔진을 쓰는 개발자가 손으로 지을 일은 드뭅니다.

상자를 겹겹이 쌓는 생각은 광선 말고도 씁니다. 물리 계산에서 부딪힐 만한 물체 쌍을 먼저 추리는 충돌 감지가 같은 상자 트리를 씁니다. 지도 서비스가 공간 검색에 쓰는 R-트리도 경계 상자를 겹겹이 쌓은 트리입니다.

물체가 몇 개뿐이면 가속 구조가 값을 못 합니다. 짓는 비용이 하나하나 맞대 보는 비용보다 커집니다.

물체를 하나씩 화면에 눌러 찍어 칠하는 래스터화는 가속 구조를 쓰지 않습니다. 화면을 래스터화로만 그린다면 가속 구조를 지을 까닭이 없습니다.

관련 항목

가속 구조가 속하는 상위 분류

자료구조 · 트리 · 공간 인덱스 · 레이 트레이싱 · 그래픽스

가속 구조를 이루는 구성 요소

BVH · BLAS · TLAS · 인스턴스 · 경계 상자 · AABB · 변환 행렬 · 삼각형 메시

가속 구조를 대신하는 공간 분할 구조

k-d 트리 · 옥트리 · 균일 격자 · BSP 트리 · 공간 분할

가속 구조를 짓고 고치는 방법

SAH · BVH 갱신 · 가속 구조 압축 · 스크래치 버퍼 · LBVH

가속 구조를 따라 광선을 찾는 단계

광선 순회 · 광선 교차 판정 · 최근접 적중 셰이더 · 임의 적중 셰이더 · 교차 셰이더

가속 구조를 쓰는 파이프라인과 셰이더

레이 트레이싱 파이프라인 · 레이 쿼리 · 광선 생성 셰이더 · 셰이더 바인딩 테이블 · 셰이더

가속 구조를 셰이더에 넘기는 자원

디스크립터 · 디스크립터 타입 · 디스크립터 세트 · 버퍼 · 커맨드 버퍼 · 디바이스 드라이버

가속 구조를 제공하는 그래픽스 API

Vulkan · Vulkan 확장 · Direct3D 12 · DXR · Metal · GPU

같은 상자 트리를 쓰는 계산

충돌 감지 · 브로드 페이즈 · 절두체 컬링 · 최근접 이웃 탐색 · R-트리

가속 구조와 맞세워지는 그리기 방식

래스터화 · Z 버퍼 알고리즘 · 패스 트레이싱 · 소프트웨어 레이 트레이싱