슬래브법

컴퓨터 그래픽스에서 슬라브 방법은 축 정렬 경계 상자(AAB)의 경우, 즉 광선과 상자 사이의 교차점을 결정하는 데 사용되는 알고리즘입니다.분기 없는 구현을 가능하게 하는 효율적인 특성 때문에 컴퓨터 그래픽 응용 프로그램에서 널리 사용됩니다.^[1][2]

알고리즘.

알고리즘 뒤에 있는 아이디어는 상자의 6개 면을 포함하는 평면으로 광선을 자르는 것입니다.각 평행 평면 쌍은 슬래브를 정의하며 상자에 들어 있는 부피는 세 슬래브의 교차점입니다.따라서 상자 내의 광선 부분(있는 경우 광선이 상자와 효과적으로 교차한다고 가정할 때)은 세 개의 슬래브 내의 광선 부분의 교차점에 의해 제공됩니다.^[3]

3차원 AABB는 각 차원을 따라 상자의 하한과 상한을 나타내는 $l$ =${\displaystyle }$(${\displaystyle {}_{}}$ ${\displaystyle 0_{}}$ ${\displaystyle {}_{}}$ 1$,$ l $2$) {\displaystyle {\boldsymbol {l}}=(l_{0}, l_{1}, l_{2}) 및 h = (h 0, h 1, h 2) {\displaystyle {\boldsymbol {h}}=(h_{0}, h_{1}, h_{2}}의 3배수로 표현할 수 있습니다.A point ${\displaystyle {\boldsymbol {p}}(t)=(p_{0}(t),p_{1}(t),p_{2}(t))}$ along a ray with origin ${\displaystyle {\boldsymbol {o}}=(o_{0},o_{1},o_{2})}$ and direction ${\displaystyle {\boldsymbol {r}}=(r_{0},r_{1},$$r_{2}}$은(는) 매개 변수 형식으로 다음과 같이 나타낼 수 있습니다$$.

${\displaystyle \mathit{p}(t)}$ = o$$+ $tr$ {\displaystyle {\bold 기호 {p}${\displaystyle \mathit{\}}}$(t) = {\bold 기호 {o} + t{\bold 기호 {r}}.

${\displaystyle {모든}_{}}$ $교차점,$ 즉 ≠ 0 ∀ i${\displaystyle$r_{i}\$neq$0\;\forall i}이(가) $존재$한다고 가정할 때$, t$ {\displaystyle t}에 대한 해결은 다음을 제공합니다.

${\displaystyle t={\frac {{\bold 기호 {p}}-{\bold 기호 {o}}{\bold 기호 {r}}}$

$따라서{\displaystyle }$ i ${\displaystyle i}$ -th$$ 좌표축에 직교하는 두 평면을 갖는 광선의 두 교차점은 다음과 같이 주어집니다.

${\displaystyle {\begin{aligned}t_{i}^{\text{low}}&={\frac {l_{i}-o_{i}}{r_{i}}\text{high}}&={\frac {h_{i}-o_{i}}{r_{i}}}.\end{aligned}}$

$i{\displaystyle }$ ${\displaystyle i}$ -th$$ 슬래브 내 세그먼트의 근접 및 극단은 다음과 같이 제공됩니다.

${\displaystyle {\begin{aligned}t_{i}^{\text{close}&=\min \left\{t_{i}^{\text{low}}, t_{i}^{\text{high}}\right\}\t_{i}^{\text{far}}&=\max \left\{t_{i}^{\text{low}}, t_{i}^{\text{high}}\right\}\end{aligned}}$

그리고 이 모든 세그먼트들의 교차점은

${\displaystyle {\begin{aligned}t^{\text{close}}&=\max_{i}\left\{t_{i}^{\text{close}}\right\}\t^{text{far}&=\min_{i}\left\{t_{i}^{\text{far}\right\}.\end{aligned}}$

이러한 결과 세그먼트는 상자 안에 있으므로, $t{\displaystyle {}^{}}$ ${\displaystyle {\text{close}}^{}}$ ${\displaystyle {}^{}}$ t ${\displaystyle {\text{far}}^{}}$ ${\$인 경우에만 교집합이 존재합니다$.$^[4]$t{\displaystyle {}^{}}$ {\$displaystyle t^{\text${close$}}$의 부호는 교차점이 광선의 원점 앞 또는 뒤에서 발생하는지를 결정합니다$$. 이는 카메라 앞의 교차점만 관심을 가지는 광선 캐스팅과 같은 응용 분야에서 흥미로울 수 있습니다.따라서 두 교차점은 다음과 같이 지정됩니다.

${\displaystyle {\begin{aligned}{\bold 기호 {p}}^{\text{close}&={\bold 기호 {o}}+t^{\text{close}}{\bold 기호 {r}}\{\text{far}}&={\bold 기호 {o}+t^{\text{far}}{\bold 기호 {r}}.\end{aligned}}$

${\displaystyle {위}_{}}$의 식은 ${\displaystyle \mathrm{ri}}$ ≠ $0이 i {\displaystyle$ r_{$i$neq 0\;\forall i}인 경우에만 실제 값 변수에 대해 잘 정의되지만, 즉 광선이 어떤 좌표 축에도 평행하지 않은 경우 알고리즘은 축에 평행한 광선을 처리하기 위해 확장된 실수 산술(IEEE 754에 의해 구현된 것과 같은)에 적용될 수 있습니다.광선 자체의 기원이 경계 상자의 면들 중 하나에 있지 않는 한.이러한 산술에서 광선에 평행한 평면과의 교차점은 $t$ = +${\displaystyle }$∞ {\$displaystyle$ $t$=$+\$infty} 또는 t = - ∞ {\displaystyle t=-\infty}로 주어지며 알고리즘은 여전히 예상대로 작동합니다.원점이 경계 상자의 면에 있는 경우 $일부$ i ${\displaystyle i}$의 경우 ${\displaystyle ti}$ =$${\displaystyle t_${i$}= {\frac {0}{0}}이(는 IEEE 754에서 NaN으로 표시됨) 발생합니다.그러나 IEEE 754-2008의 구현 minNum과 maxNum 함수는^[5] NaN을 결측값으로 처리하며 잘 정의된 값과 NaN을 비교할 때 항상 잘 정의된 값을 반환하므로 이러한 코너 케이스도 처리할 수 있습니다.^[6]코너 케이스를 처리하기 위한 대안적인 접근법은 0의 역수를 큰 임의의 상수로 대체함으로써 달성할 수 있는 0에 의한 분할을 완전히 피하는 것입니다.^[4]

참고문헌

원천

• IEEE Standards Committee (2008). IEEE standard for floating-point arithmetic: 754-2008. Washington, DC: IEEE Computer Society.
• Kay, Timothy L.; Kajiya, James T. (1986). Ray tracing complex scenes. ACM SIGGRAPH computer graphics. Vol. 20. Dallas. pp. 269–278.
• Majercik, Alexander; Crassin, Cyril; Shirley, Peter; McGuire, Morgan (2018). "A Ray-Box Intersection Algorithm and Efficient Dynamic Voxel Rendering". Journal of Computer Graphics Techniques (JCGT). 7 (3): 66–81.
• Shirley, Peter; Wald, Ingo; Marrs, Adam (2021). "Ray Axis-Aligned Bounding Box Intersection". Ray Tracing Gems II. Berkeley, CA: Apress.

외부 링크

• Barnes, Travian (27 July 2022). "Fast, Branchless Ray/Bounding Box Intersections, Part 3: Boundaries". Archived from the original on 2023-07-22.