경로 추적

오른쪽|섬네일|350픽셀|경로 추적을 사용하여 렌더링된 이미지로, 이 기술의 주목할 만한 특징을 보여준다

**경로 추적** 또는 **패스 트레이싱**(path tracing)은 컴퓨터 그래픽스에서 물체, 복셀, 그리고 참여 매개체와 빛이 상호작용하는 방식을 시뮬레이션하여 현실적인 (물리적으로 타당한) 이미지를 생성하는 렌더링 알고리즘이다.

이 광선 추적 기술은 몬테카를로 방법을 사용하여 글로벌 일루미네이션을 정확하게 모델링하고, 다양한 표면 특성을 시뮬레이션하며, 사진기 시스템에서 관찰 가능한 다양한 효과를 포착한다. 예를 들어 렌즈의 광학 특성 (예: 피사계 심도 및 보케) 또는 셔터 속도의 영향 (예: 모션 블러 및 노출) 등이 있다. 물리 기반 렌더링과 빛 전달 모델을 통합함으로써 사실적인 결과를 얻을 수 있지만, 상당한 컴퓨팅 성능이 필요하다. 특히 복잡한 장면에서는 VRAM/RAM 용량 및 메모리 대역폭으로 인해 성능이 제한되는 경우가 많으며, 실용적인 사용을 위해 노이즈 제거 기술이 필요하다. 또한 GIGO 원칙이 적용된다. 즉, 부정확한 장면 데이터, 낮은 품질의 기하학적 모델, 낮은 품질의 재질, 또는 잘못된 렌더링 설정은 렌더링 정밀도에 관계없이 최종 출력에 부정적인 영향을 미칠 수 있다.

정확성, 편향되지 않은 특성, 그리고 알고리즘적 단순성 덕분에 경로 추적은 다른 렌더링 알고리즘의 품질을 테스트할 때 참조 이미지를 생성하는 데 일반적으로 사용된다. 근본적으로 이 알고리즘은 물체 표면의 한 지점에 도달하는 빛을 적분한다. 이 조도는 표면 반사 함수(BRDF)에 의해 수정되어 카메라에서 볼 때 최종 이미지에 기여하는 빛의 양을 결정한다. 이 적분 과정은 출력 이미지의 모든 화소에 대해 반복되어 각 화소의 상세한 평가를 보장한다. 화소당 샘플(spp) 수는 최종 렌더링의 세부 수준과 품질을 결정하며, 일반적으로 샘플 수가 많을수록 이미지 선명도가 향상된다. 렌더링 성능은 종종 초당 메가 샘플(Ms/sec)로 측정되며, 이는 초당 처리할 수 있는 수백만 개의 샘플 수를 반영하여 렌더링 속도에 직접적인 영향을 미친다. 양방향 경로 추적 및 메트로폴리스 빛 전달과 같은 경로 추적의 여러 변형이 개발되어 다양한 유형의 장면에서 효율성을 향상시키고 노이즈를 줄이며 수렴 속도를 높인다.

## 역사

렌더링 방정식과 컴퓨터 그래픽스에서의 사용은 1986년 제임스 카지야에 의해 발표되었다. 경로 추적은 당시 렌더링 방정식의 적분에 대한 수치적 해법을 찾는 알고리즘으로 소개되었다. 10년 후 라포르튠은 양방향 경로 추적을 포함한 많은 개선 사항을 제안했다.

어려운 장면에서 성능을 향상시키기 위해 이전에 찾은 경로를 변형하는 방법인 메트로폴리스 빛 전달은 1997년 에릭 비치와 레오니다스 기바스에 의해 소개되었다.

최근에는 CPU와 GPU가 이미지를 더 빠르게 렌더링할 수 있을 정도로 강력해져 경로 추적 알고리즘에 대한 관심이 더 넓게 퍼졌다. 팀 퍼셀은 2002년 GPU에서 실행되는 첫 번째 글로벌 일루미네이션 알고리즘을 발표했다. 2009년 2월, 엔비디아의 오스틴 로비슨은 GPU에서 실행되는 상용 경로 추적의 첫 번째 구현을 시연했고, 2009년 8월 블라디미르 코일라조프의 구현과 같은 다른 구현들이 뒤따랐다. 이는 CUDA와 OpenCL과 같은 GPGPU 프로그래밍 툴킷과 OptiX와 같은 GPU 광선 추적 SDK의 발전으로 가능해졌다.

경로 추적은 영화 산업에서 중요한 역할을 해왔다. 이전 영화들은 CG 시각 효과와 애니메이션을 제작하기 위해 스캔라인 렌더링에 의존했다. 1998년, 블루 스카이 스튜디오는 자사의 독자적인 CGI 스튜디오 경로 추적 렌더러를 사용하여 아카데미상 수상 단편 영화 버니를 렌더링했으며, 여기에는 부드러운 그림자와 간접 조명 효과가 특징이었다. 소니 픽처스 이미지워크스의 몬스터 하우스는 2006년에 상용 아놀드 렌더러를 사용하여 전적으로 경로 추적으로 렌더링된 첫 번째 장편 애니메이션 영화였다. 또한 월트 디즈니 애니메이션 스튜디오는 2014년 빅 히어로 제작 이후 자사의 최적화된 경로 추적기인 하이페리온(Hyperion)을 사용해왔다. 픽사 애니메이션 스튜디오도 상용 렌더맨 렌더러에 경로 추적을 채택했다.

## 설명

카지야의 렌더링 방정식은 광학의 세 가지 특정 원칙을 따른다. 글로벌 일루미네이션 원칙, 등가 원칙(반사된 빛은 방출된 빛과 동일하다), 그리고 방향 원칙(반사된 빛과 산란된 빛은 방향을 갖는다).

실제 세계에서 물체와 표면은 빛을 반사하기 때문에 보인다. 이 반사된 빛은 차례로 다른 물체를 비춘다. 이 간단한 관찰에서 두 가지 원칙이 뒤따른다.

**I.** 주어진 실내 장면에서 방 안의 모든 물체는 다른 모든 물체에 조명을 기여해야 한다.

**II.** 둘째, 광원에서 방출된 조명과 표면에서 반사된 조명 사이에는 구분이 없다.

1984년에 발명된 상당히 다른 방법인 라디오서티는 두 원칙 모두에 충실했다. 그러나 라디오서티는 표면에 떨어지는 총 조도를 표면을 떠나는 균일한 휘도와 관련시켰다. 이는 모든 표면이 람베르트, 또는 "완벽하게 확산된" 상태가 되도록 강제했다. 라디오서티가 도입될 때 많은 주목을 받았지만, 완벽하게 확산된 표면은 실제 세계에 존재하지 않는다. 표면에서 산란은 입사 방향과 출사 방향 모두에 의존한다는 사실은 양방향반사도분포함수 (BRDF)의 핵심 원칙이다. 이 방향 의존성은 1990년대 내내 중요한 아이디어의 발표로 이어진 연구의 초점이었는데, 방향을 고려하는 것은 데스크톱 컴퓨터에서 계산 시간을 급격히 증가시키는 대가를 항상 치렀기 때문이다. 원칙 III이 뒤따른다.

**III.** 표면에서 나오는 조명은 들어오는 조명의 입사 방향과 샘플링되는 출사 방향의 어떤 함수인 특정 방향으로 산란되어야 한다.

카지야의 방정식은 이 세 가지 원칙을 완전하게 요약한 것이며, 방정식의 해를 근사하는 경로 추적은 구현에서 이 원칙에 충실하다. 카지야의 방정식의 초점이 아닌 다른 광학 원칙들이 있으며, 따라서 알고리즘에 의해 종종 어렵거나 잘못 시뮬레이션된다. 경로 추적은 세 가지 원칙에 포함되지 않은 광학 현상으로 인해 혼란을 겪는다. 예를 들어,

* 밝고 선명한 코스틱; 방사휘도는 공간의 조도 밀도에 비례한다.
* 서브서피스 스캐터링; 위 원칙 III의 위반이다.
* 색수차, 형광, 훈색; 빛은 주파수 스펙트럼이다.

## 알고리즘

다음 의사코드는 순진한 경로 추적을 수행하는 절차이다. TracePath 함수는 가속 경로만 고려되는 픽셀의 단일 샘플을 계산한다.


```c
Color TracePath(Ray ray, count depth) {
  if (depth >= MaxDepth) {
    return Black;  // Bounced enough times.
  }

  ray.FindNearestObject();
  if (ray.hitSomething == false) {
    return Black;  // Nothing was hit.
  }

  Material material = ray.thingHit->material;
  Color emittance = material.emittance;

  // Pick a random direction from here and keep going.
  Ray newRay;
  newRay.origin = ray.pointWhereObjWasHit;

  // This is NOT a cosine-weighted distribution!
  newRay.direction = RandomUnitVectorInHemisphereOf(ray.normalWhereObjWasHit);

  // Probability of the newRay
  const float p = 1 / (2 * PI);

  // Compute the BRDF for this ray (assuming Lambertian reflection)
  float cos_theta = DotProduct(newRay.direction, ray.normalWhereObjWasHit);
  Color BRDF = material.reflectance / PI;

  // Recursively trace reflected light sources.
  Color incoming = TracePath(newRay, depth + 1);

  // Apply the Rendering Equation here.
  return emittance + (BRDF * incoming * cos_theta / p);
}

void Render(Image finalImage, count numSamples) {
  foreach (pixel in finalImage) {
    foreach (i in numSamples) {
      Ray r = camera.generateRay(pixel);
      pixel.color += TracePath(r, 0);
    }
    pixel.color /= numSamples;  // Average samples.
  }
}
```


모든 샘플은 평균되어 출력 색상을 얻는다. 법선의 반구에서 항상 무작위 광선을 샘플링하는 이 방법은 완벽하게 확산된 표면에만 잘 작동한다는 점에 유의해야 한다. 다른 재질의 경우 일반적으로 중요도 샘플링, 즉 BRDF 분포에 따라 새로운 광선을 확률적으로 선택해야 한다. 예를 들어, 완벽하게 반사되는(거울) 재질은 위의 방법으로 작동하지 않는다. 이는 복사휘도가 반사될 수 있는 유일한 광선인 올바른 반사된 광선이 될 확률이 0이기 때문이다. 이러한 상황에서는 몬테카를로 적분에 따라 샘플링 방식의 확률 밀도 함수로 반사율을 나누어야 한다(위의 순진한 경우에는 특정 샘플링 방식이 없으므로 PDF는 \frac{1}{2\pi}이 된다).

에너지 보존을 보장하기 위해 고려해야 할 다른 사항들이 있다. 특히 순진한 경우 확산 BRDF의 반사율은 \frac{1}{\pi}를 초과해서는 안 된다. 그렇지 않으면 물체가 받는 빛보다 더 많은 빛을 반사한다(그러나 이는 사용된 샘플링 방식에 따라 다르며 정확하게 하기가 어려울 수 있다).

## 양방향 경로 추적

적분을 샘플링하는 것은 다음 두 가지 별개의 접근 방식 중 하나로 수행할 수 있다.
* **역방향 경로 추적**은 카메라에서 시작하여 장면 주변을 반사하며 광원에 도달할 때까지 경로를 생성한다. 빛이 실제로 이동하는 방향과 반대 방향으로 카메라에서 시작하여 광원 쪽으로 이동하기 때문에 "역방향"이라고 한다. 모든 광학 시스템은 가역적이므로 동일한 결과를 생성한다.
* **광선 추적**(또는 **순방향 경로 추적**)은 광원에서 시작하여 장면 주변을 반사하며 카메라에 도달할 때까지 경로를 생성한다.

두 경우 모두 분산을 줄이기 위해 '다음 이벤트 추정'이라는 기술을 사용할 수 있다. 이 기술은 경로가 우연히 도달하기를 기다리는 대신 중요한 특징('광선 추적'의 경우 카메라, '역방향 경로 추적'의 경우 광원)을 직접 샘플링하는 방식으로 작동한다. 이 기술은 일반적으로 효과적이지만, 반사 또는 거의 반사되는 BRDF가 있을 때는 덜 유용해진다. '역방향 경로 추적'의 경우 확산 표면과 상호 작용한 다음 반사 표면에서 반사되어 광원에 도달하는 코스틱 경로에 대해 높은 분산을 생성한다. '다음 이벤트 추정'은 이 반사 상호 작용이 중간에 있기 때문에 확산 표면에서 직접 이러한 경로를 샘플링하는 데 사용할 수 없다. 마찬가지로 빛이 반사될 수 있는 방향이 하나뿐이기 때문에 반사 표면에서 경로를 샘플링하는 데 사용할 수 없다. '광선 추적'은 경로가 카메라에 도달하기 전에 반사 표면과 상호 작용할 때 유사한 문제가 발생한다. 이러한 상황이 훨씬 더 흔하고 노이즈가 심하거나 완전히 검은색인 유리 물체가 시각적으로 매우 방해가 되기 때문에 실제로는 '역방향 경로 추적'만이 단방향 경로 추적에 사용되는 유일한 방법이다.

양방향 경로 추적은 두 가지 접근 방식을 결합하고 단일 방법보다 낮은 분산을 생성할 수 있는 알고리즘을 제공한다. 각 샘플에 대해 광원에서 하나, 카메라에서 하나씩 두 개의 경로가 독립적으로 추적된다. 이는 하나의 경로의 각 정점을 다른 경로의 모든 정점에 직접 연결할 수 있는 일련의 가능한 샘플링 전략을 생성한다. 원래의 '광선 추적' 및 '역방향 경로 추적' 알고리즘은 모두 이러한 전략의 특수한 경우이다. '광선 추적'의 경우 카메라 경로의 정점을 광선 경로의 첫 번째 정점에 직접 연결하는 것이다. '역방향 경로 추적'의 경우 광선 경로의 정점을 카메라 경로의 첫 번째 정점에 연결하는 것이다. 또한 중간 정점이 연결되는 완전히 새로운 여러 샘플링 전략이 있다. 다중 중요도 샘플링을 사용하여 이러한 모든 샘플링 전략에 가중치를 부여하면 각 샘플에 더 많은 작업이 필요하더라도 단방향 경로 추적보다 더 빠르게 수렴할 수 있는 새로운 샘플러가 생성된다. 이는 코스틱 또는 주로 간접 조명으로 조명되는 장면에 특히 효과적이다.

## 성능

섬네일|오른쪽|픽셀당 샘플 수가 증가함에 따라 노이즈가 감소한다. 왼쪽 위는 픽셀당 1개의 샘플을 보여주고, 왼쪽에서 오른쪽으로 각 사각형마다 두 배로 증가한다.

경로 추적기는 지속적으로 이미지의 화소를 샘플링한다. 이미지는 픽셀당 몇 개의 샘플, 아마도 100개만으로도 인식할 수 있게 된다. 그러나 이미지가 "수렴"하고 허용 가능한 수준으로 노이즈를 줄이려면 대부분의 이미지에 대해 일반적으로 약 5000개의 샘플이 필요하며, 병리학적 경우에는 훨씬 더 많은 샘플이 필요하다. 노이즈는 특히 애니메이션에서 문제가 되며, 원치 않는 "필름 그레인" 품질의 무작위 반점을 제공한다.

경로 추적에서 핵심적인 성능 병목은 광선을 캐스팅하는 복잡한 기하학적 계산이다. 중요도 샘플링은 표면 지점에서 나가는 휘도에 올바르게 수렴하면서도 장면을 통해 더 적은 광선을 캐스팅하도록 동기화된 기술이다. 이는 어쨌든 휘도가 더 높았을 방향으로 더 많은 광선을 캐스팅함으로써 수행된다. 특정 방향으로 캐스팅된 광선의 밀도가 해당 방향의 기여도 강도와 일치하면 결과는 동일하지만 실제로 캐스팅된 광선은 훨씬 적다. 중요도 샘플링은 광선 밀도를 람베르트의 코사인 법칙과 일치시키는 데 사용되며 BRDF와도 일치시키는 데 사용된다.

메트로폴리스 빛 전달은 더 적은 샘플로 더 낮은 노이즈 이미지를 생성할 수 있다. 이 알고리즘은 빛이 이상한 복도나 작은 구멍을 통과하여 카메라가 보고 있는 장면의 부분에 도달해야 하는 장면에서 더 빠른 수렴을 얻기 위해 만들어졌다. 또한 코스틱이 있는 병리학적 상황을 올바르게 렌더링하는 데에도 유망함을 보여주었다. 무작위 경로를 생성하는 대신 기존 경로의 약간의 변형으로 새로운 샘플링 경로가 생성된다. 이런 의미에서 이 알고리즘은 광원에서 카메라까지의 성공적인 경로를 "기억"한다.

## 산란 분포 함수
섬네일|오른쪽|산란 분포 함수

표면의 반사 속성(양, 방향, 색상)은 BRDF를 사용하여 모델링된다. 투과된 빛(물체를 통과하는 빛)에 해당하는 것은 BSDF이다. 경로 추적기는 복잡하고 신중하게 모델링되거나 측정된 분포 함수를 완전히 활용할 수 있으며, 이는 물체의 외관("재질", "텍스처", 또는 컴퓨터 그래픽스 용어로 "셰이딩")을 제어한다.

## 같이 보기
* 아놀드 (소프트웨어)
* 블렌더 (소프트웨어) – 경로 추적 GPU 가속 렌더링 엔진인 **Cycles**가 통합된 3D 프로그램
* 옥테인 렌더
* 픽사 렌더맨
* 럭스 코어 렌더러

## 각주

# 
# Lafortune, E, Mathematical Models and Monte Carlo Algorithms for Physically Based Rendering, (PhD thesis), 1996.
# Purcell, T J; Buck, I; Mark, W; and Hanrahan, P, "Ray Tracing on Programmable Graphics Hardware", *Proc. SIGGRAPH 2002*, 703 – 712. See also Purcell, T, Ray tracing on a stream processor (PhD thesis), 2004.
# Robison, Austin, "Interactive Ray Tracing on the GPU and NVIRT Overview", slide 37, I3D 2009.
# Vray demo; Other examples include Octane Render, Arion, and Luxrender.
# 
# Veach, E., and Guibas, L. J. Metropolis light transport. In SIGGRAPH’97 (August 1997), pp.&nbsp;65–76.
# SmallPt is an educational path tracer by Kevin Beason. It uses 99 lines of C++ (including scene description). This page has a good set of examples of noise resulting from this technique.

분류:3차원 렌더링