광선 순회

광선 순회는 눈에서 화면의 한 점을 지나 쏜 직선인 광선이 장면에서 처음 맞는 물체를 찾아 줍니다. 물체를 담은 상자 트리를 위에서부터 내려가며 광선이 지나는 상자만 엽니다. 빗나간 상자와 이미 찾은 물체보다 먼 상자는 열지 않고 건너뜁니다. 화면의 점마다 광선을 쏘아 색을 정하는 그리기 방식인 레이 트레이싱에서는 점마다 이 절차가 한 번씩 돕니다.

상세

이 절은 광선과 가속 구조를 먼저 풀고, 광선 순회가 무엇을 받아 무엇을 내놓는지 봅니다. 그다음 상자 트리를 내려가는 차례와, 열지 않아도 되는 상자를 고르는 두 규칙을 봅니다.

두 규칙은 상자 일곱 개로 된 작은 트리 하나로 따라가 봅니다. 그 뒤로는 그림자 광선, 두 층으로 나뉜 트리, 순회 도중 끼어드는 프로그램, 전용 회로, 비용, 격자 순회, 순회가 필요 없을 때를 차례로 봅니다.

광선과 가속 구조

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

입체 모델은 작은 삼각형을 수천에서 수만 개 이어 붙여 만듭니다. 그래서 광선이 무엇에 맞았는지는 결국 어느 삼각형에 맞았는지를 묻는 일이 됩니다.

광선이 삼각형과 겹치는지 따지는 계산이 교차 판정입니다. 삼각형 하나마다 이 계산을 한 번씩 합니다.

교차 판정에서 광선이 삼각형과 겹친다고 나오면 그것을 적중이라고 합니다. 광선 하나가 여러 삼각형에 적중할 수 있고, 그중 가장 가까운 것이 그 점에 보이는 물체입니다.

광선 하나마다 장면의 삼각형을 전부 맞대 볼 수도 있습니다. 하지만 화면 한 장에 광선이 수백만 개입니다. 광선마다 삼각형 수십만 개를 맞대 보면 화면 한 장도 제때 못 그립니다.

그래서 삼각형들을 미리 상자에 나눠 담아 둡니다. 물체를 빈틈없이 감싸는 가장 작은 상자가 경계 상자입니다. 광선이 상자를 빗나가면 그 안의 삼각형도 전부 빗나갑니다.

상자들을 다시 큰 상자로 묶어 겹겹이 쌓으면 트리가 됩니다. 이 문서에서는 큰 상자 하나가 자식 상자 둘을 품는 트리로 설명합니다. 이 상자 트리가 BVH(Bounding Volume Hierarchy, 경계 볼륨 계층)입니다.

트리의 맨 끝 마디를 잎이라고 합니다. 잎에는 삼각형이 몇 개씩 담깁니다.

이처럼 광선이 맞는 물체를 빨리 찾으려고 미리 지어 둔 구조를 통틀어 가속 구조라고 합니다. 데이터베이스 테이블에 거는 인덱스와 같은 일을 장면에 해 줍니다. 광선 순회는 이 인덱스를 타고 내려가는 검색입니다.

넣는 것과 나오는 것

광선 순회에 넣는 것은 둘입니다. 광선 하나와 그 장면의 가속 구조입니다.

광선은 출발점 하나와 방향 하나로 정해집니다. 광선 위의 한 점은 출발점에서 방향을 따라 거리 t 만큼 간 곳입니다. 그래서 「무엇에 맞았나」는 「t 가 가장 작은 적중이 무엇인가」로 바꿔 물을 수 있습니다.

광선에는 찾을 범위가 붙어 다닙니다. t 가 t_min 과 t_max 사이인 적중만 셉니다. t_max 는 처음에 무한대입니다. 순회 도중 적중을 찾을 때마다 줄어듭니다.

광선은 눈에서만 쏘지 않습니다. 물체 표면의 한 점에서 빛 쪽으로 다시 쏘기도 합니다. 그 점이 그늘인지 알아보려는 것으로, 뒤의 그림자 광선 소절에서 다룹니다.

t_min 은 0 보다 조금 큰 값으로 둡니다. 표면에서 다시 쏜 광선은 부동소수점 계산 오차 때문에 출발한 그 표면에 곧바로 다시 맞을 수 있습니다. t_min 이 이런 가짜 적중을 걸러 냅니다.

나오는 것은 가장 가까운 적중 하나입니다. 어느 삼각형에 맞았는지와 거리 t 가 담깁니다. 범위 안에 적중이 없으면 「없음」이 나옵니다. 하늘처럼 아무것도 없는 쪽으로 쏜 광선이 그렇습니다.

보통의 트리 순회와 다른 점

순회는 트리의 마디를 정해진 차례로 찾아가는 일입니다. 디렉터리 트리를 훑거나 중첩된 JSON(JavaScript Object Notation) 문서를 재귀로 펼치는 일이 트리 순회입니다. 보통의 트리 순회는 마디를 하나도 빠짐없이 들릅니다.

광선 순회는 광선이 지나는 상자만 들릅니다. 빗나간 상자 아래의 마디는 하나도 안 봅니다. B-tree 인덱스를 타고 내려갈 때 찾는 키가 없는 가지를 안 여는 것과 같습니다.

내려가는 차례는 깊이 우선 탐색입니다. 한 가지를 잎까지 먼저 내려간 뒤 돌아와 다음 가지를 봅니다. 아직 안 연 상자는 스택에 쌓아 둡니다.

순회 한 바퀴

이 소절은 순회를 파이썬 꼴의 짧은 코드로 적어 봅니다. 스택이 빌 때까지 상자를 하나씩 꺼내 보는 고리입니다.

코드에 나오는 함수 둘을 먼저 풉니다. enter 는 광선이 상자에 들어가는 거리 t 를 돌려줍니다. 빗나가면 None 을 돌려줍니다. far_to_near 는 광선이 들어가는 자식 상자만 골라 먼 것부터 늘어놓습니다.

def traverse(ray, root):
  best = None              # 아직 못 찾음
  stack = [root]
  while stack:
    node = stack.pop()
    t = enter(ray, node.box)
    if t is None:          # 상자를 빗나감
      continue
    if t > ray.t_max:      # 찾은 것보다 멂
      continue
    if node.is_leaf:
      for tri in node.tris:
        hit = intersect(ray, tri)
        if hit and hit.t < ray.t_max:
          best = hit
          ray.t_max = hit.t  # 범위를 좁힘
    else:
      kids = far_to_near(ray, node)
      stack.extend(kids)   # 가까운 쪽이 위
  return best

꺼낸 상자는 세 갈래 가운데 하나로 갑니다. 빗나갔거나 이미 찾은 적중보다 멀면 버립니다. 잎이면 그 안의 삼각형을 교차 판정합니다. 잎이 아닌 속 마디면 자식을 스택에 넣습니다.

스택은 마지막에 넣은 것이 먼저 나옵니다. 그래서 먼 자식부터 넣으면 가까운 자식이 먼저 열립니다.

가까운 상자부터 열기

광선이 두 자식 상자를 다 지나면 둘 다 열어 봐야 합니다. 상자끼리 겹칠 수 있기 때문입니다. 한쪽에서 적중을 찾아도 다른 쪽에 더 가까운 적중이 있을 수 있습니다.

둘 중 무엇을 먼저 열지는 광선이 상자에 들어가는 거리로 정합니다. 가까운 상자가 먼저입니다. 가까운 상자에서 적중을 먼저 찾을 가능성이 큽니다. 그 적중이 다음 규칙을 움직입니다.

찾은 적중보다 먼 상자 건너뛰기

적중을 하나 찾으면 t_max 를 그 거리로 줄입니다. 그 뒤로 꺼낸 상자가 t_max 보다 먼 곳에서 시작하면 열지 않습니다. 그 상자 안의 어떤 적중도 이미 찾은 것보다 멀기 때문입니다.

가까운 적중을 일찍 찾을수록 이 규칙이 더 많은 상자를 건너뜁니다. 앞 소절의 「가까운 상자부터」가 이 규칙과 짝을 이룹니다.

작은 트리로 따라가기

이 소절은 상자 일곱 개짜리 트리에 광선 하나를 쏴서 앞의 코드를 한 줄씩 따라갑니다. 그림의 숫자는 광선이 그 상자에 들어가는 거리입니다.

flowchart TD
    R["루트 · 거리 1"]
    R --> A["왼쪽 상자 · 거리 2"]
    R --> B["오른쪽 상자 · 거리 5"]
    A --> A1["잎 1 · 거리 3 · 삼각형 적중 거리 4"]
    A --> A2["잎 2 · 빗나감"]
    B --> B1["잎 3"]
    B --> B2["잎 4"]

광선은 루트와 왼쪽 상자, 오른쪽 상자를 다 지납니다. 왼쪽 상자 아래에서는 잎 1 만 지납니다. 잎 1 의 삼각형 하나에 거리 4 에서 맞습니다. 잎 3 과 잎 4 에는 거리를 적지 않았습니다. 순회가 끝날 때까지 둘 다 열리지 않기 때문입니다.

아래 표는 스택에서 상자를 꺼낼 때마다 무슨 일이 일어나는지 적은 것입니다. 스택 칸은 오른쪽 끝이 다음에 꺼낼 상자입니다.

스택이 비어 순회가 끝납니다. 잎 1 의 삼각형이 답입니다. 잎 넷 가운데 삼각형을 맞대 본 잎은 잎 1 하나뿐입니다. 오른쪽 상자를 먼저 열었다면 그 아래에서 광선이 지나는 잎을 다 열어 본 뒤에야 왼쪽으로 왔을 것입니다.

아무 적중이나 하나면 되는 광선

그림자 광선은 물체 표면의 한 점에서 빛을 향해 쏘는 광선입니다. 빛까지 가는 길에 무엇이든 하나 걸리면 그 점은 그늘입니다. 어느 것이 가장 가까운지는 묻지 않습니다.

그래서 그림자 광선은 첫 적중에서 순회를 멈춥니다. 같은 트리를 써도 가장 가까운 적중을 찾는 광선보다 대개 빨리 끝납니다.

그림자 광선의 t_max 는 빛까지의 거리로 둡니다. 빛 너머에 있는 물체는 그늘을 만들지 않기 때문입니다.

두 층 트리를 지나는 순회

같은 나무 모델을 숲에 천 그루 심는 장면을 생각해 봅시다. 나무마다 삼각형을 새로 담으면 메모리가 천 배로 듭니다. 그래서 모델 하나의 트리는 한 벌만 짓습니다. 그 모델을 놓는 위치만 천 개 적어 둡니다.

그래픽 카드에서 광선을 쏘게 해 주는 프로그래밍 도구들은 가속 구조를 이렇게 두 층으로 나눕니다. 모델 하나의 삼각형을 담은 아래층이 BLAS(Bottom-Level Acceleration Structure, 하위 가속 구조)입니다. 모델을 놓은 위치들을 담은 위층이 TLAS(Top-Level Acceleration Structure, 상위 가속 구조)입니다.

TLAS 의 잎 하나가 인스턴스입니다. 인스턴스는 어느 BLAS 를 쓸지와, 그것을 장면 어디에 어떤 방향으로 놓을지를 담습니다. 나무 천 그루라면 인스턴스가 천 개이고 BLAS 는 한 벌입니다.

놓는 위치와 방향은 변환 행렬 하나로 적습니다. 변환 행렬은 좌표를 옮기고 돌리고 키우는 계산을 숫자 표 하나로 묶은 것입니다.

모델의 좌표는 그 모델을 만들 때 쓴 모델 자신의 기준 좌표입니다. 나무 모델의 삼각형은 장면 어디에 심든 이 좌표로 한 벌만 적혀 있습니다. 그래서 BLAS 를 보려면 광선을 장면의 좌표에서 그 모델의 좌표로 옮겨야 합니다.

flowchart TD
    subgraph T["TLAS · 장면 전체"]
        TR["TLAS 루트"] --> I1["인스턴스 · 나무 1번"]
        TR --> I2["인스턴스 · 나무 2번"]
    end
    subgraph BL["BLAS · 나무 모델 한 벌"]
        BR["BLAS 루트"] --> L["잎 · 삼각형 몇 개"]
    end
    I1 -->|"광선을 모델 좌표로 옮겨 내려감"| BR
    I2 -->|"광선을 모델 좌표로 옮겨 내려감"| BR

순회는 TLAS 에서 시작합니다. 잎인 인스턴스에 닿으면 광선을 그 모델의 좌표로 옮깁니다. 변환 행렬의 역행렬을 광선의 출발점과 방향에 곱하면 옮겨집니다. 그런 다음 BLAS 를 위에서부터 같은 방식으로 내려갑니다.

물체를 장면 쪽으로 옮기지 않고 광선을 물체 쪽으로 옮기는 데는 까닭이 있습니다. 옮길 것이 광선 하나뿐이라 삼각형 수천 개를 옮기는 것보다 쌉니다. BLAS 를 다 보고 나면 광선을 원래 좌표로 되돌려 TLAS 의 다음 상자로 돌아갑니다.

찾은 적중보다 먼 상자를 건너뛰는 규칙은 두 층에 걸쳐 이어집니다. 나무 1번에서 거리 4 의 적중을 찾았다면, 그보다 멀리 있는 나무 2번의 BLAS 는 열지 않습니다.

순회 도중 끼어드는 프로그램

셰이더는 그래픽 카드에서 도는 작은 프로그램입니다. 순회 자체는 정해진 절차입니다. 다만 몇 군데에서 개발자가 쓴 셰이더를 불러 판단을 맡길 수 있습니다.

첫째는 임의 적중 셰이더입니다. 나뭇잎 모델은 삼각형 하나에 잎 그림을 붙이고 잎 바깥을 투명하게 둡니다. 광선이 그 투명한 부분에 맞으면 적중으로 치면 안 됩니다. 임의 적중 셰이더가 이런 적중을 받아들일지 버릴지 정합니다.

둘째는 교차 셰이더입니다. 공처럼 삼각형이 아닌 모양은 교차 판정을 개발자가 직접 써야 합니다. 순회가 그 모양의 상자에 닿으면 교차 셰이더를 불러 적중 거리를 받습니다.

순회가 끝나면 결과에 따라 셰이더가 하나 더 불립니다. 적중이 있으면 최근접 적중 셰이더가 그 점의 색을 정합니다. 없으면 미스 셰이더가 하늘색 같은 배경을 돌려줍니다.

순회를 맡는 전용 회로

그래픽 카드의 계산 칩을 GPU(Graphics Processing Unit, 그래픽 처리 장치)라고 합니다. 레이 트레이싱을 지원하는 GPU 는 대개 광선 순회 전용 회로를 둡니다. 상자를 고르며 트리를 내려가는 일과 삼각형 교차 판정을 이 회로가 맡습니다. 셰이더는 광선을 넘기고 결과만 받습니다.

전용 회로가 없는 GPU 에서는 앞의 고리를 셰이더 코드로 직접 돌립니다. 이것을 소프트웨어 레이 트레이싱이라고 합니다. 같은 일을 범용 계산으로 하므로 대개 더 느립니다.

복잡도

이 소절은 광선 하나를 순회하는 비용을 삼각형 수에 견줘 봅니다. O(n) 은 비용이 삼각형 수 n 에 비례해 는다는 뜻입니다. O(log n) 은 삼각형이 두 배가 될 때 비용이 한 단계씩만 는다는 뜻입니다.

상자를 반씩 갈라 지은 트리의 높이는 약 log₂ n 입니다. 삼각형 100만 개면 스무 층 안팎입니다. 상자가 덜 겹치게 잘 지은 트리에서는 광선이 층마다 상자 몇 개만 엽니다. 그래서 평균 비용이 log n 에 비례합니다.

최악은 상자끼리 크게 겹칠 때입니다. 길고 가는 물체가 장면을 비스듬히 가로지르면 그 물체의 상자가 장면 대부분을 덮습니다. 그러면 이 큰 상자가 다른 상자 대부분과 겹칩니다.

겹친 두 상자는 광선이 둘 다 지나기 쉽습니다. 앞의 「가까운 상자부터 열기」에서 본 대로 그때는 두 자식을 다 열어야 합니다. 층마다 이런 일이 생기면 끝내 잎을 거의 다 열게 됩니다.

메모리는 스택이 씁니다. 깊이 우선으로 내려가므로 스택에는 트리 높이에 비례하는 수의 상자만 쌓입니다. 다만 GPU 는 광선 수백만 개를 한꺼번에 돌리므로 광선마다 드는 이 스택이 모이면 작지 않습니다.

격자를 따라가는 순회

상자 트리만 순회 대상인 것은 아닙니다. 공간을 같은 크기의 칸으로 나눈 균일 격자도 가속 구조로 씁니다. 칸마다 그 칸에 걸친 삼각형 목록을 담아 둡니다.

격자에서는 광선이 지나는 칸을 출발점에서 가까운 차례로 하나씩 밟아 갑니다. 다음 칸은 x · y · z 가운데 어느 축의 칸 경계를 먼저 넘는지 견줘서 정합니다.

삼각형 하나가 여러 칸에 걸칠 수 있습니다. 그래서 지금 칸의 목록에 든 삼각형이라도 적중점은 지금 칸 밖에 놓일 수 있습니다.

칸을 가까운 차례로 밟으므로, 적중점이 지금 칸 안에 놓이면 그것이 곧 답입니다. 적중점이 지금 칸 밖에 놓이면 바로 답으로 정하지 않습니다. 그 사이의 칸에 더 가까운 적중이 있을 수 있어서, 적중점이 든 칸에 닿았을 때 다시 따집니다.

물체가 장면에 고르게 퍼져 있으면 빈 칸이 적어 격자가 빨리 돕니다. 넓은 빈 공간에 작은 물체가 몰려 있으면 빈 칸을 오래 밟아야 합니다. 그래서 GPU 의 레이 트레이싱은 대개 상자 트리를 씁니다.

광선 순회가 필요 없을 때

물체를 하나씩 화면에 눌러 찍어 칠하는 래스터화는 광선을 쏘지 않습니다. 화면을 래스터화로만 그리면 광선 순회가 돌 일이 없습니다.

물체가 몇 개뿐인 장면에서도 순회가 값을 못 합니다. 트리를 짓는 비용이 삼각형을 전부 맞대 보는 비용보다 커집니다. 그럴 때는 트리 없이 하나씩 다 맞대 봅니다.

관련 항목

광선 순회가 속하는 상위 분류

레이 트레이싱 · 트리 순회 · 깊이 우선 탐색 · 그래픽스 · 렌더링

광선 순회가 따라 내려가는 자료구조

가속 구조 · BVH · BLAS · TLAS · 인스턴스 · k-d 트리 · 옥트리 · 균일 격자

광선 순회가 한 걸음마다 하는 계산

광선 교차 판정 · 슬랩 테스트 · 경계 상자 · AABB · 변환 행렬 · 역행렬

광선 순회 도중과 끝에 불리는 셰이더

임의 적중 셰이더 · 교차 셰이더 · 최근접 적중 셰이더 · 미스 셰이더 · 광선 생성 셰이더

광선 순회로 답을 찾는 광선 종류

주 광선 · 그림자 광선 · 반사 광선 · 패스 트레이싱 · 앰비언트 오클루전

광선 순회 비용을 줄이는 기법

SAH · 짧은 스택 · 스택 없는 순회 · 광선 패킷 · 광선 정렬

광선 순회를 돌리는 하드웨어와 파이프라인

GPU · 레이 트레이싱 파이프라인 · 레이 쿼리 · 소프트웨어 레이 트레이싱 · Vulkan · Direct3D 12 · DXR

광선 순회와 맞세워지는 그리기 방식

래스터화 · Z 버퍼 알고리즘 · 절두체 컬링 · 깊이 테스트