スラブ法

コンピュータグラフィックスにおいて、スラブ法は、軸平行境界ボックス（AABB）におけるレイボックス交差問題を解くために使用されるアルゴリズムであり、光線とボックスの交点を求める。分岐のない実装を可能にする効率的な性質のため、コンピュータグラフィックスアプリケーションで広く使用されている。^{[ 1 ] [ 2 ]}

アルゴリズム

このアルゴリズムの背後にある考え方は、光線をボックスの6つの面を含む平面で切り取るというものです。平行な平面の各ペアはスラブ（板）を定義し、ボックスに含まれる体積は3つのスラブの交差です。したがって、ボックス内の光線の部分（もしあれば、光線が実際にボックスと交差している場合）は、3つのスラブのそれぞれに含まれる光線の部分の交差によって与えられます。^{[ 3 ]}

3次元AABBは、2つの3次元の要素と、各次元に沿ったボックスの下限と上限を表す要素で表すことができます。原点と方向を持つ直線上の点は、媒介変数を用いて次のように表現できます 。${\displaystyle {\boldsymbol {l}}=(l_{0},l_{1},l_{2})}$ ${\displaystyle {\boldsymbol {h}}=(h_{0},h_{1},h_{2})}$ ${\displaystyle {\boldsymbol {p}}(t)=(p_{0}(t),p_{1}(t),p_{2}(t))}$ ${\displaystyle {\boldsymbol {o}}=(o_{0},o_{1},o_{2})}$ ${\displaystyle {\boldsymbol {r}}=(r_{0},r_{1},r_{2})}$

${\displaystyle {\boldsymbol {p}}(t)={\boldsymbol {o}}+t{\boldsymbol {r}}}$ 。

すべての交差が存在すると仮定すると、すなわち を解くと${\displaystyle r_{i}\neq 0\;\forall i}$ ${\displaystyle t}$

${\displaystyle t={\frac {{\boldsymbol {p}}-{\boldsymbol {o}}}{\boldsymbol {r}}}}$

したがって、光線と- 番目の座標軸に直交する 2 つの平面との 2 つの交点は次のように表される。 ${\displaystyle i}$

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

-番目のスラブ内の線分の近い極値と遠い極値は次のように与えられる。 ${\displaystyle i}$

${\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}}}$

このような結果の線分はボックスの内側にあるため、交差が存在するのは の場合のみである。^{[ 4 ]}の符号は交差が光線の原点の前方で発生するか後方で発生するかを決定する。これは、カメラ前方での交差のみが関心対象となるレイキャスティングなどのアプリケーションで興味深い。したがって、2つの交点は次のように与えられる。 ${\displaystyle t^{\text{近い}}\leq t^{\text{遠い}}}$ ${\displaystyle t^{\text{close}}}$

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

上の式は、 、つまり光線がどの座標軸にも平行でない場合にのみ、実数値変数に対して適切に定義されますが、光線の原点自体が境界ボックスの面の 1 つにない限り、軸に平行な光線を扱うために、アルゴリズムを拡張実数演算 ( IEEE 754で実装されているものなど) に適用することができます。このような演算では、光線に平行な平面との交点はまたはで与えられ、アルゴリズムは期待どおりに動作します。原点が境界ボックスの面にある場合、 の場合もあり、これは未定義です (IEEE 754 ではNaNで表されます)。しかし、IEEE 754-2008のminNum関数とmaxNum関数^{[ 5 ]}の実装では、NaNを欠損値として扱い、明確に定義された値とNaNを比較する際には常に明確に定義された値を返すため、^{[ 6 ]}、このようなコーナーケースにも対応できます。コーナーケースに対処するための別のアプローチは、ゼロ除算を完全に回避することです。これは、ゼロの逆数を任意の大きな定数に置き換えることで実現できます。^{[ 4 ]}${\displaystyle r_{i}\neq 0\;\forall i}$ ${\displaystyle t=+\infty }$ ${\displaystyle t=-\infty}$ ${\displaystyle i}$ ${\displaystyle t_{i}={\frac {0}{0}}}$

参考文献

1. シャーリー、ウォルド＆マース 2021 .
2. Majercik et al. 2018 .
3. ケイ・カジヤ 1986、272頁。
4. ケイ＆カジヤ 1986、p. 273.
5. たとえば、 C99のfminとfmax。
6. IEEE標準委員会 2008 .

出典

• IEEE標準委員会 (2008).浮動小数点演算に関するIEEE標準：754-2008 . ワシントンD.C.: IEEEコンピュータ協会.
• Kay, Timothy L.; Kajiya, James T. (1986).複雑なシーンのレイトレーシング. ACM SIGGRAPH コンピュータグラフィックス. 第20巻. ダラス. pp.  269– 278.
• マジェルシック, アレクサンダー; クラッシン, シリル; シャーリー, ピーター; マクガイア, モーガン (2018). 「レイボックス交差アルゴリズムと効率的な動的ボクセルレンダリング」.コンピュータグラフィックス技術ジャーナル. 7 (3): 66– 81.
• シャーリー、ピーター、ウォルド、アダム・マース (2021). 「光線軸に沿った境界ボックスの交差」.レイトレーシングの宝石 II . カリフォルニア州バークレー: Apress.

外部リンク

• バーンズ、タヴィアン (2022年7月27日). 「高速で分岐のないレイ/バウンディングボックス交差、パート3：境界」 . 2023年7月22日時点のオリジナルよりアーカイブ。