광선 추적

섬네일|흰색 표면에 있는 반사 색상 구의 반복적 광선 추적은 얕은 피사계 심도, "영역" 광원 및 분산 상호 반사의 효과를 보여준다. (2008년경)
**광선 추적** 또는 **레이 트레이싱**(ray tracing)은 3차원 컴퓨터 그래픽스에서 다양한 렌더링 알고리즘에서 디지털 이미지를 생성하는 데 사용되는 광선 전달을 모델링하는 기술이다.

계산 시간과 시각적 충실도의 스펙트럼에서 광선 투사, 재귀적 광선 추적, 분산 광선 추적, 광자 매핑 및 경로 추적과 같은 광선 추적 기반 렌더링 기술은 일반적으로 스캔라인 렌더링 방법보다 느리지만 충실도가 더 높다. 따라서 광선 추적은 처음에 정지 컴퓨터 생성 이미지 및 영화 및 텔레비전 시각 효과(VFX)와 같이 렌더링에 상대적으로 오랜 시간이 걸리는 것이 허용되는 응용 프로그램에 배포되었지만, 각 필름 프레임을 렌더링하는 데 속도가 중요한 실시간 응용 프로그램인 비디오 게임에는 덜 적합했다.

그러나 2018년부터 실시간 레이 트레이싱을 위한 하드웨어 가속이 새로운 상용 그래픽 카드에 표준화되었고, 그래픽 API도 이에 따라 개발자들이 게임 및 기타 실시간 응용 프로그램에서 프레임 렌더링 시간에 미치는 영향을 줄이면서 하이브리드 레이 트레이싱 및 래스터화 기반 렌더링을 사용할 수 있게 되었다.

광선 추적은 광학 효과를 다양하게 시뮬레이션할 수 있다. 예를 들어 반사, 굴절, 부드러운 그림자, 빛 산란, 피사계 심도, 모션 블러, 코스틱, 앰비언트 어클루전 및 분산 (광학) 현상(색수차 등)이 있다. 또한 음파를 광파와 유사하게 추적하는 데 사용할 수 있어 사실적인 잔향과 메아리를 렌더링함으로써 비디오 게임에서 더욱 몰입감 있는 사운드 디자인을 위한 실행 가능한 옵션이 된다. 실제로 거의 선형적인 움직임을 가진 물리적 파동 또는 입자 현상은 광선 추적으로 시뮬레이션될 수 있다.

도메인 전체에서 빛을 샘플링하는 광선 추적 기반 렌더링 기술은 광선을 생성하거나 디노이징 기술을 사용한다.

## 역사
섬네일|"비스듬히 누운 여인의 원근 드로잉을 그리는 제도사", 알브레히트 뒤러 작, 1532년경 작품으로 추정되며, 한 남자가 격자 구조를 사용하여 이미지를 만드는 모습을 보여준다. 이 독일 르네상스 예술가는 이 기술을 처음으로 설명한 것으로 알려져 있다.
섬네일|제이콥 드 카이저의 발명품을 묘사한 뒤러의 목판화. 드 카이저의 장치에서 화가의 시점은 벽에 박힌 아이 훅으로 고정되었다. 이것은 실크 끈으로 연결되어, 앞쪽에 뾰족한 수직 요소와 뒤쪽에 들여다보는 구멍이 있는 총신 조준기와 같은 기구에 연결되었다. 화가는 대상을 조준하고 유리에 윤곽을 그렸으며, 올바른 시야각을 유지하기 위해 눈을 끈에 맞춰 정렬했다.

광선 추적의 개념은 빠르면 16세기에 알브레히트 뒤러에 의해 설명되었으며, 그는 이 발명의 공로를 인정받고 있다.
뒤러는 3차원 장면을 이미지 평면에 투사하는 여러 기술을 설명했다. 이 중 일부는 오늘날 래스터화에서와 같이 선택된 기하학적 형상을 이미지 평면에 투사한다. 다른 일부는 광선 추적에서와 같이 주어진 광선을 따라 어떤 기하학적 형상이 보이는지를 결정한다.

컴퓨터를 사용하여 음영 처리된 그림을 생성하기 위한 광선 추적은 1968년 아서 아펠에 의해 처음 시도되었다. 아펠은 각 이미지 지점에서 카메라에 가장 가까운 표면을 결정하는 주 시야(primary visibility)를 위해 광선 추적을 사용했다. 각 음영 처리할 지점을 통해 장면에 광선을 추적하여 보이는 표면을 식별했다. 광선에 의해 교차된 가장 가까운 표면이 보이는 표면이었다. 이 비재귀적인 광선 추적 기반 렌더링 알고리즘은 오늘날 "광선 투사"라고 불린다. 그의 알고리즘은 각 음영 처리되는 지점으로부터 광원으로 보조 광선을 추적하여 그 지점이 그림자에 있는지 여부를 결정했다.

나중에 1971년, MAGI (Mathematical Applications Group, Inc.)의 골드슈타인과 나겔은 "3-D 시각 시뮬레이션"을 발표했으며, 여기서 광선 추적은 입체의 음영 처리된 그림을 만드는 데 사용되었다. 광선-표면 교차점에서 그들은 표면 법선을 계산하고, 광원의 위치를 알아내어 화면의 픽셀 밝기를 계산했다. 그들의 출판물은 메릴랜드 대학의 16mm 카메라가 장착된 디스플레이 하드웨어를 사용하여 만든 짧은 (30초) 영화를 묘사한다. 이 영화는 헬리콥터와 단순한 지상 총포대를 보여주었다. 헬리콥터는 회전, 이륙, 착륙 등 일련의 기동을 수행하도록 프로그래밍되었고, 결국 격추되어 추락했다. CDC 6600 컴퓨터가 사용되었다. MAGI는 1974년에 MAGI/SynthaVision Sampler라는 애니메이션 비디오를 제작했다.

섬네일|right|1976년 칼텍에서 제작된 플립북 영화또 다른 초기 광선 투사 사례는 1976년에 스콧 로스(Scott Roth)가 캘리포니아 공과대학교에서 밥 스프롤의 컴퓨터 그래픽스 강좌에서 플립북 애니메이션을 만들었을 때였다. 스캔된 페이지는 첨부된 이미지에서 비디오로 표시된다. 로스의 컴퓨터 프로그램은 광선이 이웃과 다른 제한된 평면과 교차하는 경우 픽셀 위치에 모서리 지점을 표시했다. 물론 광선은 공간에서 여러 평면과 교차할 수 있지만, 카메라에 가장 가까운 표면 지점만 보이는 것으로 표시되었다. 이 플랫폼은 DEC PDP-10, 텍트로닉스 스토리지 튜브 디스플레이, 그리고 열 감지지에 디스플레이 이미지를 생성하는 프린터였다. 로스는 이 프레임워크를 확장하고, 컴퓨터 그래픽스 및 솔리드 모델링의 맥락에서 광선 투사라는 용어를 도입했으며, 1982년 GM 연구소에 근무하면서 자신의 작업을 발표했다.

터너 위티드는 거울 반사 및 투명 객체를 통한 굴절에 대한 재귀적 광선 추적을 처음으로 보여주었으며, 고체의 굴절률에 의해 결정되는 각도를 사용했고, 공간 위신호 제거를 위해 광선 추적을 사용했다. 위티드는 또한 광선 추적된 그림자를 보여주었다. 그는 1979년 벨 연구소의 엔지니어로 근무하면서 The Compleat Angler라는 재귀적 광선 추적 영화를 제작했다. 위티드의 깊이 재귀적인 광선 추적 알고리즘은 렌더링을 주로 표면 가시성 결정의 문제에서 광선 전달의 문제로 재구성했다. 그의 논문은 분산 광선 추적 및 최종적으로 편향되지 않은 경로 추적을 포함한 후속 작업의 시리즈에 영감을 주었으며, 이는 렌더링 방정식 프레임워크를 제공하여 컴퓨터 생성 이미지가 현실에 충실하도록 만들었다.

수십 년 동안 컴퓨터 생성 이미지를 사용하는 주요 영화에서 글로벌 일루미네이션은 추가 조명으로 근사화되었다. 광선 추적 기반 렌더링은 물리 기반 광선 전달을 가능하게 하여 결국 이를 변화시켰다. 경로 추적을 사용하여 완전히 렌더링된 초기 장편 영화에는 몬스터 하우스, 하늘에서 음식이 내린다면 (2009), 및 몬스터 대학교 (2013)가 포함된다.

## 알고리즘 개요
right|섬네일|300px|광선 추적 알고리즘은 장면에 광선을 확장하고 표면에 반사시킨 다음 광원을 향해 픽셀의 색상 값을 근사화하여 이미지를 구축한다.
left|섬네일|300px|한 픽셀에 대한 광선 추적 알고리즘 그림 (첫 번째 반사까지)
광선 추적은 광선 투사 또는 스캔라인 렌더링 기술보다 더 사실적인 방식으로 3차원 컴퓨터 그래픽스 환경에서 시각적 이미지를 생성하는 방법을 설명한다. 이 방법은 가상의 눈에서 가상 화면의 각 화소를 통해 경로를 추적하고, 그를 통해 보이는 물체의 색상을 계산함으로써 작동한다.

광선 추적에서 장면은 프로그래머나 시각 예술가(일반적으로 중간 도구를 사용)에 의해 수학적으로 설명된다. 장면은 디지털 사진과 같은 수단을 통해 캡처된 이미지 및 모델의 데이터를 통합할 수도 있다.

일반적으로 각 광선은 장면의 모든 객체 중 일부와의 교차 여부를 테스트해야 한다. 가장 가까운 객체가 식별되면, 알고리즘은 교차점에서 들어오는 빛을 추정하고, 객체의 재료 속성을 조사하며, 이 정보를 결합하여 픽셀의 최종 색상을 계산한다. 특정 조명 알고리즘 및 반사성 또는 반투명 재료는 더 많은 광선을 장면에 다시 투사해야 할 수도 있다.

처음에는 카메라를 향하는 것이 아니라 카메라에서 멀리 광선을 보내는 것이 직관적이지 않거나 "역방향"처럼 보일 수 있지만(실제 빛이 현실에서 하는 것처럼), 그렇게 하는 것이 훨씬 더 효율적이다. 주어진 광원에서 나오는 압도적인 대다수의 광선은 시청자의 눈에 직접 들어오지 않으므로, "정방향" 시뮬레이션은 기록되지 않는 광선 경로에 엄청난 양의 계산을 낭비할 수 있다.

따라서 광선 추적에서 사용되는 단축키는 주어진 광선이 뷰 프레임과 교차한다고 전제하는 것이다. 최대 반사 횟수에 도달하거나 광선이 교차 없이 특정 거리를 이동한 후에는 광선은 더 이상 이동하지 않고 픽셀의 값이 업데이트된다.

### 직사각형 뷰포트를 위한 광선 계산
입력으로 우리는 (계산에서 벡터 정규화 및 벡터곱을 사용한다):

* E \in \mathbb{R^3} 눈 위치
* T \in \mathbb{R^3} 대상 위치
* \theta \in [0,\pi]  시야 - 인간의 경우 \approx \pi/2 \text{ rad}= 90^\circ로 가정할 수 있다.
* m,k \in \mathbb{N} 뷰포트 수직 및 수평 방향의 정사각형 픽셀 수
* i,j  \in \mathbb{N}, 1\leq i\leq k \land 1\leq j\leq m  실제 픽셀 수
* \vec v \in \mathbb{R^3} 위아래를 나타내는 수직 벡터, 보통 \vec v = [0,1,0] - 뷰포트 회전을 결정하는 롤 구성 요소 C (회전축이 ET 단면인 곳)

708px|픽셀, 눈 E, 대상 T, 뷰포트 중심 C가 있는 뷰포트 스키마

아이디어는 각 뷰포트 픽셀의 중심 P_{ij}의 위치를 찾는 것이다. 이를 통해 눈 E를 통과하여 해당 픽셀을 통과하는 선을 찾고, 최종적으로 점 E와 벡터 \vec R_{ij} = P_{ij} -E  (또는 그 정규화 \vec r_{ij})로 설명되는 광선을 얻을 수 있다. 먼저 왼쪽 아래 뷰포트 픽셀 P_{1m}의 좌표를 찾아야 하고, 픽셀 크기를 곱한 뷰포트와 평행한 방향(벡터 \vec b_n, \vec v_n)을 따라 이동하여 다음 픽셀을 찾아야 한다. 아래에는 눈과 뷰포트 사이의 거리 d를 포함하는 공식을 제시한다. 그러나 이 값은 광선 정규화 \vec r_{ij} 중에 줄어들 것이다 (따라서 d=1로 받아들이고 계산에서 제거하는 것이 좋다).

사전 계산: 벡터 \vec t와 뷰포트에 평행한 벡터 \vec b, \vec v를 찾아 정규화한다 (위 그림에 모두 표시됨).

:
\vec t = T-E, \qquad \vec b = \vec t\times \vec v


:
\vec t_n = \frac{\vec t}, \qquad
\vec b_n = \frac{\vec b}, \qquad
\vec v_n = \vec t_n\times \vec b_n


뷰포트 중심 C=E+\vec t_nd임을 유의하고, 다음으로 종횡비 \frac{m-1}{k-1}의 역수를 포함하여 뷰포트 크기 h_x, h_y를 2로 나눈 값을 계산한다.

:
g_x=\frac{h_x}{2} =d \tan \frac{\theta}{2}, \qquad  g_y =\frac{h_y}{2} = g_x \frac{m-1}{k-1}


그리고 다음으로 뷰포트에 평행한 방향(\vec b,\vec v)을 따라 다음 픽셀 이동 벡터 q_x, q_y와 왼쪽 아래 픽셀 중심 p_{1m}을 계산한다.

:
\vec q_x = \frac{2g_x}{k-1}\vec b_n, \qquad
\vec q_y = \frac{2g_y}{m-1}\vec v_n, \qquad
\vec p_{1m} = \vec t_n d - g_x\vec b_n - g_y\vec v_n


계산: P_{ij} = E + \vec p_{ij}이고 광선 \vec R_{ij} = P_{ij} -E = \vec p_{ij}이므로

:
\vec p_{ij} = \vec p_{1m} + \vec q_x(i-1) + \vec q_y(j-1)

:
\vec r_{ij} = \frac{\vec R_{ij}} = \frac{\vec p_{ij}}


## 광선 추적 컴퓨터 알고리즘 및 그 기원에 대한 자세한 설명

### 자연에서 일어나는 일 (간략화)

자연에서는 광원이 빛줄기를 방출하고, 이 빛줄기는 결국 진행을 방해하는 표면에 도달한다. 이 "광선"은 동일한 경로를 따라 이동하는 광자 흐름으로 생각할 수 있다. 완벽한 진공 상태에서는 이 광선이 직선이 된다(상대론적 효과는 무시). 이 광선에는 네 가지 중 어떤 조합이든 발생할 수 있다: 흡광, 반사, 굴절 및 형광. 표면은 광선 일부를 흡수하여 반사되거나 굴절된 빛의 강도 손실을 초래할 수 있다. 또한 광선 전체 또는 일부를 하나 이상의 방향으로 반사할 수도 있다. 표면이 투명하거나 투명한 속성을 가지고 있다면, 빛줄기의 일부를 다른 방향으로 자체적으로 굴절시키면서 가시광선의 일부(또는 전부)를 흡수한다(그리고 색상을 변경할 수 있다). 덜 일반적이지만, 표면은 빛의 일부를 흡수하여 무작위 방향으로 더 긴 파장 색상으로 형광 발광할 수도 있지만, 대부분의 렌더링 응용 프로그램에서는 무시할 수 있을 만큼 드물다. 흡수, 반사, 굴절, 형광 사이에서 들어오는 모든 빛은 설명되어야 하며, 그 이상은 안 된다. 예를 들어, 표면은 들어오는 광선의 66%를 반사하고 50%를 굴절시킬 수 없는데, 이는 둘을 합치면 116%가 되기 때문이다. 여기서 반사되거나 굴절된 광선은 다른 표면에 부딪힐 수 있으며, 그 흡수, 굴절, 반사 및 형광 특성이 들어오는 광선의 진행에 다시 영향을 미친다. 이 광선 중 일부는 우리의 눈을 강타하는 방식으로 이동하여 장면을 보게 하고 최종 렌더링된 이미지에 기여한다.

### 광선 투사 알고리즘

재귀적 광선 추적의 전신인 광선 투사의 기본 아이디어는 눈에서 픽셀당 하나의 광선을 추적하고, 그 광선 경로를 막는 가장 가까운 객체를 찾는 것이다. 이미지를 각 사각형이 픽셀인 방충망으로 생각해보자. 이것이 눈이 그 픽셀을 통해 보는 객체이다. 이 알고리즘은 재료 속성과 장면의 조명 효과를 사용하여 이 객체의 셰이딩을 결정할 수 있다. 표면이 빛을 향하면 빛이 그 표면에 도달하고 막히거나 그림자에 가려지지 않는다는 단순화된 가정이 이루어진다. 표면의 음영은 전통적인 3D 컴퓨터 그래픽스 음영 모델을 사용하여 계산된다. 광선 투사가 이전 스캔라인 알고리즘보다 제공하는 중요한 장점 중 하나는 원뿔이나 구 (기하학)와 같은 비평면 표면과 입체를 쉽게 처리할 수 있다는 점이다. 수학적 표면이 광선과 교차할 수 있다면 광선 투사를 사용하여 렌더링할 수 있다. 솔리드 모델링 기술을 사용하여 정교한 객체를 생성하고 쉽게 렌더링할 수 있다.

### 볼륨 광선 투사 알고리즘

볼륨 광선 투사 방식에서는 각 광선이 추적되어 광선을 따라 색상 및 밀도를 샘플링한 다음 최종 픽셀 색상으로 결합할 수 있다.
이것은 객체를 명시적인 표면(예: 삼각형)으로 쉽게 나타낼 수 없을 때, 예를 들어 구름이나 3D 의료 스캔을 렌더링할 때 자주 사용된다.

섬네일|SDF 광선 행진 알고리즘 시각화
### SDF 광선 행진 알고리즘

SDF 광선 행진(또는 구체 추적)에서는 각 광선이 여러 단계로 추적되어 광선과 부호화 거리 함수(SDF)에 의해 정의된 표면 사이의 교차점을 근사화한다. SDF는 표면의 어떤 부분도 놓치지 않고 가능한 한 큰 단계를 밟을 수 있도록 각 반복마다 평가된다. 표면에 충분히 가까운 지점에 도달하면 추가 반복을 중단하기 위해 임계값이 사용된다. 이 방법은 종종 3D 프랙탈 렌더링에 사용된다.

### 재귀적 광선 추적 알고리즘
right|섬네일|300px|광선 추적은 사진과 같은 이미지를 만들 수 있다.
[right|섬네일|300px|높은 사실성 외에도 광선 추적은 [피사계 심도와 조리개 모양(이 경우 육각형)으로 인한 카메라 효과를 시뮬레이션할 수 있다.]]
[right|섬네일|300px|"광선"이 반사되거나 튕길 수 있는 횟수와 표면을 만날 때마다 어떻게 영향을 받는지 소프트웨어 설정으로 제어한다. 이 이미지에서는 각 광선이 최대 16번 반사되도록 허용되었다. 따라서 이 구체에서는 여러 번 "반사된 반사"를 볼 수 있다. ([코발트 (CAD 프로그램)|코발트로 생성된 이미지.)]]
[right|섬네일|300px|"광선"이 만들 수 있는 [굴절 횟수와 빛의 투과를 허용하는 표면을 만날 때마다 어떻게 영향을 받는지 소프트웨어 설정으로 제어한다. 여기서는 각 광선이 최대 9번 굴절되거나 반사되도록("깊이") 설정되었다. 프레넬 반사가 사용되었고 코스틱이 보인다. (V-레이로 생성된 이미지.)]]

이전 알고리즘은 광선이 객체에 부딪힐 때까지 눈에서 장면으로 광선을 추적했지만, 더 많은 광선을 재귀적으로 추적하지 않고 광선 색상을 결정했다. 재귀적 광선 추적은 그 과정을 계속한다. 광선이 표면에 부딪히면 반사, 굴절 및 그림자 때문에 추가 광선이 투사될 수 있다.
* 반사 광선은 거울 반사 방향으로 추적된다. 이 광선과 교차하는 가장 가까운 객체가 반사에서 보일 것이다.
* 투명한 재료를 통과하는 굴절 광선은 유사하게 작동하며, 굴절 광선이 재료로 들어가거나 나올 수 있다는 추가 사항이 있다. 터너 위티드는 투명한 고체를 통과하는 광선에 대한 수학적 논리를 확장하여 굴절 효과를 포함했다.
* 그림자 광선은 각 광원을 향해 추적된다. 표면과 광원 사이에 불투명한 객체가 발견되면 표면은 그림자 안에 있고 광원은 그것을 비추지 않는다.
이러한 재귀적 광선은 광선 추적 이미지에 더 많은 사실감을 더한다.

### 다른 렌더링 방법보다 우위
광선 추적 기반 렌더링의 인기는 래스터화와 같은 다른 렌더링 방법이 기하학적 형태의 사실적인 시뮬레이션에 더 중점을 두는 것과 비교하여, 광선 전달의 사실적인 시뮬레이션에 기반을 둔다는 점에서 비롯된다. 다른 알고리즘으로는 시뮬레이션하기 어려운 반사 및 그림자와 같은 효과는 광선 추적 알고리즘의 자연스러운 결과이다. 각 광선의 계산적 독립성 덕분에 광선 추적은 기본적인 수준의 병렬화에 적합하지만, 광선 경로의 발산으로 인해 실제로는 병렬화에서 높은 활용도를 달성하기가 상당히 어렵다.

### 단점
광선 추적의 심각한 단점은 성능이다(장면 복잡도 대 화면 픽셀 수에 따라 이론적으로는 기존 스캔라인 렌더링보다 빠를 수 있지만). 2010년대 후반까지, 실시간 광선 추적은 사소하지 않은 작업에는 소비자 하드웨어에서 보통 불가능하다고 여겨졌다. 스캔라인 알고리즘 및 기타 알고리즘은 데이터 일관성을 사용하여 픽셀 간에 계산을 공유하는 반면, 광선 추적은 일반적으로 각 시점 광선을 별도로 처리하여 프로세스를 새로 시작한다. 그러나 이러한 분리는 공간 위신호 제거를 수행하고 필요한 곳에서 이미지 품질을 향상시키기 위해 필요한 만큼 더 많은 광선을 쏠 수 있는 기능과 같은 다른 이점을 제공한다.

위티드 스타일의 재귀적 광선 추적은 상호 반사 및 굴절과 같은 광학 효과를 처리하지만, 일반적으로 포토리얼리스틱하지는 않다. 렌더링 방정식이 완전히 평가될 때 향상된 사실성이 나타나는데, 이 방정식은 개념적으로 광선 흐름의 모든 물리적 효과를 포함하기 때문이다. 그러나 이는 필요한 컴퓨팅 자원과 기하학적 및 재료 모델링 충실도의 한계를 고려할 때 실행 불가능하다. 경로 추적은 렌더링 방정식을 평가하는 알고리즘으로, 실제 조명의 더 높은 충실도 시뮬레이션을 제공한다.

### 광선의 장면 탐색 방향 역전
눈에서 광원까지 광선을 쏘아 이미지를 렌더링하는 과정을 때로는 역방향 광선 추적이라고 부르는데, 이는 광자가 실제로 이동하는 방향과 반대이기 때문이다. 그러나 이 용어에는 혼란이 있다. 초기 광선 추적은 항상 눈에서 이루어졌으며, 제임스 아르보와 같은 초기 연구자들은 역방향 광선 추적이라는 용어를 광원에서 광선을 쏘아 결과를 수집하는 것을 의미하는 데 사용했다. 따라서 눈 기반 광선 추적과 광원 기반 광선 추적을 구별하는 것이 더 명확하다.

직접 조명은 일반적으로 눈 기반 광선 추적을 사용하여 가장 잘 샘플링되지만, 특정 간접 효과는 광원에서 생성된 광선의 이점을 얻을 수 있다. 코스틱은 넓은 반사 영역에서 좁은 (거의) 확산 표면 영역으로 빛이 집중되어 발생하는 밝은 패턴이다. 광선이 광원에서 반사 객체로 직접 투사되어 눈까지 경로를 추적하는 알고리즘은 이 현상을 더 잘 샘플링할 것이다. 눈 기반 광선과 광원 기반 광선의 이러한 통합은 종종 양방향 경로 추적으로 표현되는데, 이 방식에서는 눈과 광원 모두에서 경로가 추적되고, 일정 길이 후에 연결 광선에 의해 경로가 연결된다.

광자 매핑은 광원 기반 및 눈 기반 광선 추적을 모두 사용하는 또 다른 방법이다. 초기 단계에서는 에너지를 가진 광자가 광원에서 광선을 따라 추적되어 3차원 공간의 복사속 추정치(즉, 광자 지도 자체)를 계산한다. 다음 단계에서는 광선이 눈에서 장면으로 추적되어 보이는 표면을 결정하고, 광자 지도를 사용하여 보이는 표면 지점의 조명을 추정한다. 광자 매핑의 장점은 통계적 편향을 대가로 광자의 상당한 재사용을 달성하여 계산을 줄일 수 있다는 점이다.

광선이 매우 좁은 구멍을 통과하여 장면을 비추거나(밝게 조명된 방으로 이어지는 문이 약간 열려 있는 어두운 방을 생각해보자), 대부분의 지점이 광원에 대한 직접적인 시야를 가지고 있지 않은 장면(천장으로 향하는 조명 기구나 토치에르와 같은)에서 추가적인 문제가 발생한다. 이러한 경우, 경로 중 매우 작은 부분만이 에너지를 전달할 것이다. 메트로폴리스 광선 전달은 경로 공간에 대한 무작위 탐색으로 시작하여 에너지를 가진 경로가 발견되면 이 정보를 사용하여 근처의 광선 공간을 탐색하는 방법이다.

[섬네일|"눈"(및 이미지 평면을 통해)에서 두 [확산 표면에 부딪힌 후 광원까지 재귀적으로 생성된 광선 경로를 보여주는 이미지]]
오른쪽 이미지는 위 알고리즘을 사용하여 카메라(또는 눈)에서 광원까지 재귀적으로 생성된 광선 경로의 간단한 예를 보여준다. 확산 표면은 모든 방향으로 빛을 반사한다.

먼저, 눈에서 광선이 생성되어 픽셀을 통과하여 장면으로 추적되고, 확산 표면에 부딪힌다. 그 표면에서 알고리즘은 재귀적으로 반사 광선을 생성하고, 이는 장면을 통해 추적되어 다른 확산 표면에 부딪힌다. 마지막으로, 또 다른 반사 광선이 생성되어 장면을 통해 추적되고, 광원에 부딪혀 흡수된다. 이제 픽셀의 색상은 첫 번째 및 두 번째 확산 표면의 색상과 광원에서 방출되는 빛의 색상에 따라 달라진다. 예를 들어, 광원이 흰색 빛을 방출하고 두 확산 표면이 파란색이었다면, 결과 픽셀의 색상은 파란색이 된다.

### 예시
[섬네일|[세잎매듭, 매개변수 방정식으로 생성되고 파이썬으로 광선 추적됨.]]

광선 추적에 관련된 원리를 시연하기 위해, 광선과 구 (기하학) 사이의 교차점을 어떻게 찾을 것인지 고려해 보자. 이것은 단지 선-구 교차점과 그 다음에 계산되는 픽셀의 색상을 결정하는 수학적인 과정일 뿐이다. 물론 광선 추적의 일반적인 과정에는 훨씬 더 많은 것이 있지만, 이것은 사용되는 알고리즘의 한 예시를 보여준다.

벡터 표기법에서 중심이 \mathbf c이고 반지름이 r인 구의 방정식은 다음과 같다.

:\left\Vert \mathbf x - \mathbf c \right\Vert^2=r^2.

점 \mathbf s에서 방향 \mathbf d를 가진 광선(여기서 \mathbf d는 단위 벡터임) 위의 임의의 점은 다음과 같이 쓸 수 있다.

:\mathbf x=\mathbf s+t\mathbf d,

여기서  t는 \mathbf x와 \mathbf s 사이의 거리이다. 우리 문제에서는 \mathbf c, r, \mathbf s (예: 광원의 위치) 및 \mathbf d를 알고 있으며,  t를 찾아야 한다. 따라서 \mathbf x를 대입하면 다음과 같다.

:\left\Vert\mathbf{s}+t\mathbf{d}-\mathbf{c}\right\Vert^{2}=r^2.

간단히 \mathbf{v}\ \stackrel{\mathrm{def}}{=}\  \mathbf{s}-\mathbf{c}라고 하면,

:\left\Vert\mathbf{v}+t\mathbf{d}\right\Vert^{2}=r^{2}

:\mathbf{v}^2+t^2\mathbf{d}^2+2\mathbf{v}\cdot t\mathbf{d}=r^2

:(\mathbf{d}^2)t^2+(2\mathbf{v}\cdot\mathbf{d})t+(\mathbf{v}^2-r^2)=0.

d가 단위 벡터임을 알면 다음과 같은 사소한 단순화를 할 수 있다.

:t^2+(2\mathbf{v}\cdot\mathbf{d})t+(\mathbf{v}^2-r^2)=0.

이 이차 방정식의 해는 다음과 같다.
:t=\frac{-(2\mathbf{v}\cdot\mathbf{d})\pm\sqrt{(2\mathbf{v}\cdot\mathbf{d})^2-4(\mathbf{v}^2-r^2)}}{2}=-(\mathbf{v}\cdot\mathbf{d})\pm\sqrt{(\mathbf{v}\cdot\mathbf{d})^2-(\mathbf{v}^2-r^2)}.

이 방정식을 풀어 얻은 두 개의 t 값은 \mathbf s+t\mathbf d가 광선이 구와 교차하는 두 점이다.

음수 값은 광선 위에 있지 않고, 대신 반대 반직선(즉, \mathbf s에서 반대 방향으로 시작하는 반직선)에 놓인다.

제곱근 안의 양( 판별식)이 음수이면 광선은 구와 교차하지 않는다.

이제 양의 해가 적어도 하나 있다고 가정하고, t를 최소값이라고 하자. 또한, 구가 광선과 교차하는 장면에서 가장 가까운 객체이며 반사 재료로 만들어졌다고 가정하자. 빛 광선이 어느 방향으로 반사되는지 찾아야 한다. 반사 법칙에 따르면 반사각은 입사 광선과 구의 법선 사이의 입사각과 같고 반대이다.

구의 법선은 단순히 다음과 같다.

:\mathbf n=\frac{\mathbf y- \mathbf c}{\left\Vert\mathbf y- \mathbf c\right\Vert},

여기서 \mathbf y=\mathbf s+t\mathbf d는 이전에 찾은 교차점이다. 반사 방향은 \mathbf n에 대한 \mathbf d의 반사로 찾을 수 있으며, 이는 다음과 같다.

: \mathbf r = \mathbf d - 2(\mathbf n \cdot \mathbf d ) \mathbf n.

따라서 반사된 광선은 다음 방정식을 가진다.

: \mathbf x = \mathbf y  + u \mathbf r. \, 

이제 우리는 이 광선과 우리의 시야의 교차점을 계산하여 반사된 빛 광선이 도달할 픽셀을 얻기만 하면 된다. 마지막으로, 이 픽셀은 원래 광원의 색상과 구체의 색상이 반사에 의해 어떻게 결합되는지를 고려하여 적절한 색상으로 설정된다.

## 적응형 깊이 제어
적응형 깊이 제어는 렌더러가 계산된 강도가 특정 임계값보다 낮아지면 반사/전송 광선 생성을 중단하는 것을 의미한다. 항상 최대 깊이가 설정되어 있어야 하며, 그렇지 않으면 프로그램은 무한한 수의 광선을 생성할 것이다. 그러나 표면이 고반사성이 아니라면 최대 깊이까지 갈 필요는 항상 없다. 이를 테스트하기 위해 광선 추적기는 광선이 추적될 때 전역 및 반사 계수의 곱을 계산하고 유지해야 한다.

예시: 일련의 표면에 대해 Kr = 0.5라고 하자. 그러면 첫 번째 표면에서 최대 기여도는 0.5이고, 두 번째 반사에서는 0.5 × 0.5 = 0.25, 세 번째는 0.25 × 0.5 = 0.125, 네 번째는 0.125 × 0.5 = 0.0625, 다섯 번째는 0.0625 × 0.5 = 0.03125 등이다. 또한 1/D2와 같은 거리 감쇠 계수를 구현할 수 있으며, 이는 또한 강도 기여도를 감소시킬 것이다.

전송된 광선의 경우 유사한 작업을 수행할 수 있지만, 이 경우 객체를 통과하는 이동 거리가 훨씬 더 빠른 강도 감소를 유발할 것이다. 이에 대한 예시로 Hall & Greenberg는 매우 반사적인 장면에서도 최대 깊이 15를 사용하여 평균 광선 트리 깊이가 1.7이 된다는 것을 발견했다.

## 경계 볼륨
객체 그룹을 바운딩 볼륨 계층 구조(BVH) 세트로 묶으면 광선 추적에 필요한 계산량이 줄어든다. 투사된 광선은 먼저 바운딩 볼륨과의 교차점을 테스트한 다음, 교차점이 있으면 광선이 객체에 부딪힐 때까지 볼륨을 재귀적으로 나눈다. 최상의 바운딩 볼륨 유형은 기본 객체 또는 객체의 모양에 따라 결정된다. 예를 들어, 객체가 길고 얇으면 구는 상자에 비해 주로 빈 공간을 포함한다. 상자는 또한 계층적 바운딩 볼륨을 생성하기 쉽다.

이러한 계층적 시스템을 사용하면 (신중하게 수행된다고 가정할 때) 교차 계산 시간이 객체 수에 대한 선형 의존성에서 선형과 로그 의존성 사이의 값으로 변경된다는 점에 유의해야 한다. 이는 완벽한 경우 각 교차 테스트가 가능성을 두 배로 나누어 이진 트리 유형 구조를 생성하기 때문이다. 아래에서 논의할 공간 분할 방법은 이를 달성하려고 한다. 또한, 이 가속 구조는 광선 추적 계산을 출력 민감하게 만든다. 즉, 광선 교차 계산의 복잡성은 (단순히) 장면에 있는 객체 수뿐만 아니라 광선과 실제로 교차하는 객체 수에 따라 달라진다.

Kay & Kajiya는 계층적 경계 볼륨에 대한 원하는 속성 목록을 제공한다.

* 서브트리는 서로 가까이 있는 객체를 포함해야 하며, 트리의 아래로 내려갈수록 객체는 더 가까워야 한다.
* 각 노드의 볼륨은 최소화되어야 한다.
* 모든 경계 볼륨의 볼륨 합계는 최소화되어야 한다.
* 루트에 가까운 노드에 더 많은 주의를 기울여야 하는데, 루트 근처의 가지를 가지치기하면 트리의 아래쪽 가지보다 더 많은 잠재적 객체를 제거하기 때문이다.
* 계층 구조를 구축하는 데 드는 시간은 이를 사용하여 절약되는 시간보다 훨씬 적어야 한다.

## 인터랙티브 광선 추적

인터랙티브 레이 트레이서의 첫 구현은 1982년 오사카 대학 공학부에서 오무라 코이치, 시라카와 이사오 교수와 카와타 토루 교수 및 50명의 학생이 구축한 LINKS-1 컴퓨터 그래픽 시스템이었다. 이것은 고속 레이 트레이싱을 사용하는 3차원 컴퓨터 그래픽스를 위한 514개의 마이크로프로세서(Zilog Z8001 257개와 iAPX 86 257개)를 갖춘 대규모 병렬 처리 컴퓨터 시스템이었다. 정보처리학회에 따르면: "3D 이미지 렌더링의 핵심은 주어진 시점, 광원 및 객체 위치로부터 렌더링된 표면을 구성하는 각 픽셀의 휘도를 계산하는 것입니다. LINKS-1 시스템은 레이 트레이싱을 사용하여 각 픽셀을 독립적으로 병렬 처리할 수 있는 이미지 렌더링 방법론을 실현하기 위해 개발되었습니다. 고속 이미지 렌더링을 위한 새로운 소프트웨어 방법론을 개발함으로써 LINKS-1은 매우 사실적인 이미지를 빠르게 렌더링할 수 있었습니다." 이 시스템은 컴퓨터 그래픽만으로 완전히 만들어진 초기 3D 천체투영관과 같은 우주 비디오를 만드는 데 사용되었다. 이 비디오는 1985년 쓰쿠바시 국제 박람회의 후지쯔 전시관에서 발표되었다. 이것은 1982년 에반스 & 서덜랜드 Digistar에 이어 두 번째 시스템이었다. LINKS-1은 설계자들에 의해 1984년 세계에서 가장 강력한 컴퓨터라고 주장되었다.

다음으로 인터랙티브 광선 추적기이자 "실시간"으로 명명된 최초의 광선 추적기는 2005년 SIGGRAPH 컴퓨터 그래픽스 컨퍼런스에서 BRL-CAD 솔리드 모델링 시스템을 위해 마이크 무스가 1986년에 개발한 REMRT/RT 도구로 인정받았다. 1987년 USENIX에서 처음 발표된 BRL-CAD 광선 추적기는 병렬 네트워크 분산 광선 추적 시스템의 초기 구현으로, 초당 여러 프레임의 렌더링 성능을 달성했다. 이러한 성능은 BRL-CAD의 고도로 최적화되었지만 플랫폼 독립적인 LIBRT 광선 추적 엔진과 상용 네트워크를 통한 여러 공유 메모리 병렬 시스템에서 솔리드 암묵적 CSG 형상을 사용하여 달성되었다. REMRT/RT 도구를 포함한 BRL-CAD의 광선 추적기는 오늘날에도 오픈 소스 소프트웨어로 계속 사용되고 개발되고 있다.

그 이후로 스탠드얼론 데스크톱 환경에서 다양한 목적을 위해 실시간 속도로 광선 추적을 구현하려는 상당한 노력과 연구가 진행되어 왔다. 이러한 목적에는 데모씬 제작, 비디오 게임, 이미지 렌더링과 같은 인터랙티브 3D 그래픽스 응용 프로그램이 포함된다. 일부 실시간 소프트웨어 3D 엔진은 1990년대 후반부터 아마추어 데모 프로그래머에 의해 개발되었다.

1999년 유타 대학교의 스티븐 파커(Steven Parker)가 이끄는 팀은 1999년 인터랙티브 3D 그래픽스 심포지엄에서 인터랙티브 광선 추적을 시연했다. 그들은 3천5백만 개 구체 모델을 512 x 512 픽셀 해상도로 렌더링했으며, 60개의 CPU에서 초당 약 15프레임으로 실행되었다.

오픈 RT 프로젝트에는 광선 추적을 위한 고도로 최적화된 소프트웨어 코어와 OpenGL과 유사한 API가 포함되어 있어 인터랙티브 3D 그래픽스에 대한 현재의 래스터화 기반 접근 방식에 대한 대안을 제공한다. 광선 추적 하드웨어, 예를 들어 자를란트 대학교의 스벤 웁(Sven Woop)이 개발한 실험적인 광선 처리 장치는 광선 추적의 계산 집약적인 작업 중 일부를 가속화하도록 설계되었다.

섬네일|퀘이크 워즈: 광선 추적

비디오 게임이 실시간으로 그래픽을 광선 추적할 수 있다는 아이디어는 2000년대 후반에 미디어의 주목을 받았다. 그 당시 다니엘 폴(Daniel Pohl)이라는 연구원이 그래픽 교수 필립 슬루살렉(Philipp Slusallek)의 지도와 독일의 에를랑겐 대학교 및 자를란트 대학교와의 협력을 통해 퀘이크 III와 퀘이크 IV에 자신이 직접 프로그래밍한 게임 엔진을 장착했고, 자를란트 대학교는 이를 세빗 2007에서 시연했다. 자를란트의 후원자였던 인텔은 폴을 고용하고 자사 프로세서의 코어 수를 늘리는 것을 정당화한다고 보았던 광선 추적 그래픽 전용 연구 프로그램을 시작할 정도로 감명받았다. 2008년 6월 12일, 인텔은 퀘이크 워즈: 광선 추적(Quake Wars: Ray Traced)이라는 제목의 에너미 테리토리: 퀘이크 워즈 특별 버전을 시연했으며, 이는 광선 추적을 렌더링에 사용하여 기본 HD(720p) 해상도로 실행되었다. ETQW는 16코어(4소켓, 4코어) 제온 타이거턴 시스템에서 2.93GHz로 실행되어 초당 14~29프레임으로 작동했다.

2009년 SIGGRAPH에서 엔비디아는 엔비디아 GPU용 실시간 광선 추적을 위한 무료 API인 OptiX를 발표했다. 이 API는 광선 추적 파이프라인 내에 7개의 프로그래밍 가능한 진입점을 노출하여 사용자 지정 카메라, 광선-원시 교차, 셰이더, 그림자 등을 허용한다. 이러한 유연성은 양방향 경로 추적, 메트로폴리스 광선 전달 및 꼬리 재귀로 구현할 수 없는 기타 많은 렌더링 알고리즘을 가능하게 한다. OptiX 기반 렌더러는 오토데스크 Arnold, 어도비 애프터 이펙츠, Bunkspeed Shot, 오토데스크 마야, 3ds 맥스 및 기타 많은 렌더러에서 사용된다.

2014년, Q-Games와 재팬 스튜디오가 개발한 플레이스테이션 4 비디오 게임 더 투모로우 칠드런의 데모는 Q-Games가 개발한 새로운 조명 기술, 특히 계단식 복셀 원뿔 추적 광선 추적을 시연했으며, 이는 실시간으로 조명을 시뮬레이션하고 스크린 공간 반사 대신 더 사실적인 반사를 사용한다.

엔비디아는 2018년 9월 튜링 아키텍처 기반으로 하드웨어 가속 광선 추적을 지원하는 지포스 RTX 및 쿼드로 RTX GPU를 선보였다. 엔비디아 하드웨어는 "RT 코어"라고 불리는 별도의 기능 블록을 사용한다. 이 유닛은 크기, 지연 시간, 프로세서 코어와의 인터페이스 측면에서 텍스처 유닛과 다소 유사하다. 이 유닛은 BVH 순회, 압축된 BVH 노드 압축 해제, 광선-AABB 교차 테스트 및 광선-삼각형 교차 테스트를 수행한다. 지포스 RTX는 2080 및 2080 Ti 모델 형태로 실시간 광선 추적을 수행할 수 있는 최초의 소비자 지향 그래픽 카드 브랜드가 되었으며, 2018년 11월 일렉트로닉 아츠의 배틀필드 V는 마이크로소프트의 새로운 API인 DirectX Raytracing을 통해 광선 추적 기능을 활용한 첫 번째 게임이 되었다. 이미 OpenCL을 통해 인터랙티브 광선 추적을 제공했던 AMD는 라데온 프로렌더를 통해 2020년 10월 온라인 행사에서 하드웨어 가속 광선 추적을 지원하는 2세대 Navi GPU인 라데온 RX 6000 시리즈를 공개했다. 그 이후로 이러한 방식으로 그래픽을 렌더링하는 게임들이 등장했으며, 이는 하드웨어 개선과 더 많은 API 및 게임 엔진이 이 기술과 호환되도록 노력한 덕분으로 평가된다. 현재 가정용 게임 콘솔은 9세대 콘솔인 플레이스테이션 5, 엑스박스 시리즈 X/S부터 실시간 광선 추적 효과를 위한 전용 광선 추적 하드웨어 구성 요소를 GPU에 구현하고 있다.

2021년 11월 4일, 이미지네이션 테크놀로지는 하드웨어 가속 광선 추적 기능이 있는 IMG CXT GPU를 발표했다. 2022년 1월 18일, 삼성은 하드웨어 가속 광선 추적 기능이 있는 엑시노스 2200 AP SoC를 발표했다. 2022년 6월 28일, Arm은 하드웨어 가속 광선 추적 기능이 있는 Immortalis-G715를 발표했다. 2022년 11월 16일, 퀄컴은 하드웨어 가속 광선 추적 기능이 있는 스냅드래곤 8 Gen 2를 발표했다.

2023년 9월 12일 애플은 아이폰 15 프로 모델에 탑재되는 A17 프로 칩을 시작으로 칩 설계에 하드웨어 가속 광선 추적 기능을 도입했다. 같은 해 후반에 애플은 HW 활성화 광선 추적 지원 기능을 갖춘 M3 프로세서 제품군을 출시했다. 현재 이 기술은 Metal API를 통해 아이폰, 아이패드 및 맥 컴퓨터에서 접근 가능하다. 애플은 전화기에서 이전 소프트웨어 기반 광선 추적보다 최대 4배의 성능 향상을 보고했으며 M3를 M1 칩과 비교했을 때 최대 2.5배 더 빠르다고 보고했다. 하드웨어 구현에는 가속 구조 순회 및 전용 광선-박스 교차점이 포함되며, API는 RayQuery(인라인 광선 추적) 및 RayPipeline 기능을 지원한다.
## 계산 복잡도
광선 추적 문제의 특정 공식에 대해 다양한 복잡도 결과가 입증되었다. 특히, 광선 추적 문제의 결정 버전이 다음과 같이 정의된다면 – 광선의 초기 위치와 방향, 그리고 어떤 고정된 점이 주어졌을 때, 광선이 결국 그 점에 도달하는가, 그러면 참조된 논문은 다음 결과를 증명한다:
* 합리적인 이차 불평등 시스템으로 표현되는 유한한 반사 또는 굴절 객체 집합을 가진 3차원 광학 시스템에서의 광선 추적은 결정 불가능하다.
* 합리적인 선형 불평등 시스템으로 표현되는 유한한 굴절 객체 집합을 가진 3차원 광학 시스템에서의 광선 추적은 결정 불가능하다.
* 유한한 직사각형 반사 또는 굴절 객체 집합을 가진 3차원 광학 시스템에서의 광선 추적은 결정 불가능하다.
* 일부가 비합리적일 수 있는 선형 불평등 시스템으로 표현되는 유한한 반사 또는 부분 반사 객체 집합을 가진 3차원 광학 시스템에서의 광선 추적은 결정 불가능하다.
* 합리적인 선형 불평등 시스템으로 표현되는 유한한 반사 또는 부분 반사 객체 집합을 가진 3차원 광학 시스템에서의 광선 추적은 PSPACE-hard이다.
* 2차원 이상인 모든 차원에서 합리적인 선형 불평등으로 표현되는 평행 및 수직 반사 표면의 유한 집합을 가진 광선 추적은 PSPACE에 속한다.

## 소프트웨어 아키텍처
### 미들웨어
* GPUOpen
* 엔비디아 게임웍스
### API
* 메탈 (API)
* 벌컨 (API)
* DirectX

## 같이 보기

* 글로벌 일루미네이션
* 병렬 컴퓨팅
* 셰이딩
* 정반사
* 테셀레이션
* GPUOpen
* 엔비디아 게임웍스
* 메탈 (API)
* 벌컨 (API)
* DirectX

## 각주

## 외부 링크
* The Compleat Angler (1978)
* Writing a Simple Ray Tracer (scratchapixel) 
* Ray tracing a torus 
* Ray Tracing in One Weekend Book Series

분류:컴퓨터 그래픽스
분류:기하광학
분류:셰이딩