レイキャスティング

レイキャスティングは、3D CAD/CAMにおけるソリッドモデリングと画像レンダリングの基礎となる手法です。これは基本的に、コンピュータグラフィックスにおけるレイトレーシングと同じで、カメラの焦点からカメラセンサーの各ピクセルを通過する仮想光線を「キャスト」または「トレース」することで、3Dシーン内で光線に沿って何が見えるかを決定します。

「レイキャスティング」という用語は、スコット・ロスが1978年から1980年にかけてゼネラルモーターズ研究所に在籍していた際に導入されました。彼の論文「ソリッドモデリングのためのレイキャスティング」^{[ 1 ]}では、ブロックや円柱などのプリミティブソリッドを、集合演算子の和集合（+）、交差（&）、差集合（−）を使用して組み合わせることで、モデル化されたソリッドオブジェクトを記述しています。ソリッドモデリングにこれらの二項演算子を使用するという一般的なアイデアは、主にロチェスター大学のVoelckerとRequichaの幾何モデリンググループによるものです。^{[ 2 ]}^{[ 3 ]}

レイキャスティング（およびレイトレーシング）が登場する以前は、コンピュータグラフィックスアルゴリズムは、3Dワールドからサーフェスやエッジ（線など）をイメージプレーンに投影し、そこで可視性ロジックを適用する必要がありました。ワールドからイメージプレーンへの投影は、3D同次座標系変換であり、3D投影、アフィン変換、または射影変換（ホモグラフィ）とも呼ばれます。このように画像をレンダリングすることは、隠面/エッジ除去では困難です。さらに、曲面のシルエットは明示的に解く必要がありますが、レイキャスティングでは暗黙的に得られる副産物であるため、ビューが変わるたびに明示的に解く必要はありません。

レイキャスティングは、線が線に変換されるため、3D オブジェクトやシーンの画像レンダリングを大幅に簡素化します。そのため、3D シーンの曲面エッジや曲面を 2D 画像平面に投影する代わりに、変換された線 (レイ) がシーン内のオブジェクトと交差します。同次座標変換は 4×4 行列で表されます。この数学的手法は、コンピュータグラフィックスや幾何モデリングでよく使われます。^{[ 4 ]}変換には、3 つの軸を中心とした回転、軸に沿った独立したスケーリング、3D での平行移動、さらには傾斜も含まれます。変換は、行列演算によって簡単に連結できます。4×4 行列で使用する場合、点は $[X 、 Y 、 Z 、 1]で表され、方向ベクトルは$ $[D x 、 D y 、 D z 、 0]$ で表されます。(4 番目の項は平行移動を表し、方向ベクトルには適用されません。)

コンセプト

レイキャスティングは、レイトレーシングの幾何学的アルゴリズムを使用する多くのコンピュータグラフィックスレンダリングアルゴリズムの中で最も基本的なものです。レイトレーシングベースのレンダリングアルゴリズムは、画像順に動作し、3 次元シーンを 2 次元画像にレンダリングします。観察者の目から幾何学的レイがトレースされ、レイの方向から観察者に向かってくる光 (放射輝度) をサンプリングします。レイキャスティングの高速性とシンプルさは、レイが当たった点に入射する放射輝度をサンプリングする追加のレイを再帰的にトレースすることなく、光の色を計算することによって実現されます。これにより、反射、屈折、または影の自然な減衰を正確にレンダリングすることは不可能になりますが、テクスチャマップなどの創造的な使用により、これらの要素はある程度擬似的に表現できます。計算速度が速いため、レイキャスティングは初期のリアルタイム 3D ビデオゲームで便利なレンダリング方法となりました。

レイキャスティングの基本的な考え方は、目から発せられる光線をピクセルごとに追跡し、その光線の経路を遮る最も近い物体を見つけることです。画像を網戸に例えると、網戸の各マス目がピクセルになります。これが、目がそのピクセルを通して見る物体です。このアルゴリズムは、シーン内の光源の特性と効果を利用して、この物体の陰影を決定できます。簡略化のために、表面が光源に面している場合、光源はその表面に到達し、遮られたり影になったりしないという仮定が置かれています。表面の陰影は、従来の3Dコンピュータグラフィックスの陰影モデルを使用して計算されます。レイキャスティングが従来の走査線アルゴリズムよりも優れている重要な利点の1つは、円錐や球などの非平面の表面や立体を容易に処理できることです。数学的な表面が光線と交差できる場合、レイキャスティングを使用してレンダリングできます。複雑なオブジェクトは、ソリッドモデリング技術を使用して作成し、簡単にレンダリングできます。

論文「固体モデリングのためのレイキャスティング」の要旨より：^{[ 5 ]}

モデル化された複合ソリッドを視覚化および分析するために、仮想光線がプローブとして照射されます。レイキャスティングはシンプルであるため、信頼性が高く拡張性があります。最も難しい数学的問題は、線と曲面の交点を見つけることです。したがって、平面、二次曲面、トーラス、そしておそらくパラメトリック曲面パッチなどの曲面が、プリミティブソリッドを囲む可能性があります。レイキャスティングの適切性と効率性は、ここで取り上げる問題です。対話型モデリングのための高速な画像生成機能が最大の課題です。

光線とカメラの幾何学は、ここでの全ての幾何学的推論の基礎となります。この図は、画像処理における遠近効果のためのピンホールカメラモデルと、質量分析のためのパラレルカメラモデルを示しています。単純なピンホールカメラモデルは、焦点（または視点）と正方形のピクセルアレイ（またはスクリーン）で構成されます。直進光線はピクセルアレイを通過して焦点とシーンを結び、1ピクセルあたり1本の光線となります。画像を陰影付けするために、光線の強度が測定され、ピクセルとして保存されます。ピクセルの値を決定する反射面は、ピクセルの光線と交差します。

焦点距離（焦点とスクリーン間の距離）が無限大の場合、すべての光線が互いに平行でスクリーンに垂直になるため、その視点は「平行」と呼ばれます。透視図法は画像を作成する上で自然な方法ですが、用途によっては、光線が空間内に均一に分布している必要がある場合もあります。

コンセプトモデル

モデル化の便宜上、カメラの一般的な標準座標系では、スクリーンはX-Y平面上に、シーンは+Z半空間上に、焦点は-Z軸上に位置する。

光線と $は、カメラモデルの3D空間における直線のことです。これは、点ベクトル（X₀、Y₀、Z₀）と方向ベクトル（Dx、Dy$ $、$ Dz）としてパラメータ化された形式で定義するのが最適 $です$ $。この形式では、直線$ 上 $の$ $点$ $は$ $順序付け$ $られ$ $、$ $単一$ $の$ $パラメータ$ tを介してアクセスされます $。t$ $の$ $各$ 値に対して、直線上の対応する点 $（ X 、 Y 、 Z ）が定義されます。$

${\begin{aligned}X&=X_{0}+t\cdot D_{x}\\Y&=Y_{0}+t\cdot D_{y}\\Z&=Z_{0}+t\cdot D_{z}\end{aligned}}$

ベクトルが正規化されている場合、パラメータ $t$ は線に沿った距離を表します。ベクトルは以下の計算で簡単に正規化できます。

${\begin{aligned}{\text{dist}}&={\sqrt {D_{x}^{2}+D_{y}^{2}+D_{z}^{2}}}\\D_{x}^{'}&=D_{x}\ /{\text{ dist}}\\D_{y}^{'}&=D_{y}\ /{\text{ dist}}\\D_{z}^{'}&=D_{z}\ /{\text{ dist}}\end{aligned}}$

オブジェクトの幾何学的定義（各オブジェクトは1つ以上のサーフェスで囲まれている）が与えられた場合、スクリーン上のすべての境界サーフェスと1本の光線の交点を計算した結果は、2つの配列で定義されます。

レイパラメータ:

t [1]、 t [2]、\dots、 t [n]

サーフェスポインタ：

S [1]、 S [2]、\dots、 S [n]

ここで $n$ は光線と表面の交点の数です。光線パラメータの順序付きリスト $t [i]$ は、入射点と出射点を示します。光線は点 $t [1]で固体に入り、$ $t [2]$ で出て、 $t [3]$ で固体に入り、などとなります。点 $t [1]$ はカメラに最も近く、 $t [n]$ は最も遠い点です。

光線パラメータと関連付けられたサーフェスポインタには、交差するサーフェスの情報への固有のアドレスが含まれています。サーフェスは、色、鏡面反射、屈折の有無による透明度、半透明度など、さまざまな特性を持つことができます。サーフェスに関連付けられた固体は、密度などの独自の物理的特性を持つ場合があります。これは、たとえば、オブジェクトが異なる材料の集合体で構成されており、全体の重心や慣性モーメントに関心がある場合に役立ちます。

アプリケーション

レイキャスティングを用いるアルゴリズムには、線画の作成、陰影画像の作成、体積やその他の物理的特性の計算の3種類があります。各アルゴリズムは、カメラモデルが与えられると、画面上のピクセルごとに1本のレイを照射します。体積計算の場合、使用するピクセル画面の解像度は、求める解の精度によって異なります。線画や陰影画像の作成の場合、解像度は画像の品質を決定します。

線画

立体の可視エッジを描画するには、画面上で上から下、左から右に移動するピクセルごとに 1 つの光線を生成します。各光線を評価して可視面 $S [1]$ を特定します。これは、光線と面の交点のソート済みリストの最初の面ポインタです。ピクセル位置 $(X 、 Y)の可視面がピクセル$ $(X - 1、 Y)$ の可視面と異なる場合は、 $(X - ½、 Y)$ を中心とする 1 ピクセル長の垂直線を表示します。同様に、 $(X 、 Y)$ の可視面がピクセル $(X 、 Y - 1 )$ の可視面と異なる場合は、 $(X 、 Y - ½ )$ を中心とする 1 ピクセル長の水平線を表示します。結果として得られる描画は水平エッジと垂直エッジのみで構成され、粗い解像度ではギザギザに見えます。

右側の立体物体の画像は、ロスの光線キャスティングシステムによって生成されました。最適化には、ボックスエンクロージャ、動的境界、およびコヒーレンスが使用されました。各画像について、画面は約100×100（つまり10,000）本の光線密度でサンプリングされ、バイナリサーチによって新しいエッジが検出されました。その後、すべてのエッジに沿って、エッジの両側に1ピクセルずつ追加の光線が照射されました。各画像は、テクトロニクス製管上に780×780の解像度で描画されました。

陰影のある写真

陰影付き画像を作成するには、画面上のピクセルごとに1本の光線を照射します。ただし今回は、各ピクセルで可視面ポインタS[1]を使用して、サーフェスの記述にアクセスします。そこから、可視点 $t [1]$ におけるサーフェス法線を計算します。ピクセルの値、つまり表示可能な光強度は、サーフェス法線と光源からサーフェスへのベクトルによって形成される角度のコサインに比例します。このようにすべてのピクセルを処理すると、シーンのラスタータイプの画像が生成されます。

体積と慣性モーメントの計算

曲面で囲まれた立体の体積（および同様の特性）は、「近似和」積分法によって容易に計算できます。これは、立体を直方体の集合で近似することによって行われます。これは、立体を平行視で「詳細」に撮影することによって実現されます。スクリーンを通して立体に光線を照射すると、立体は体積要素に分割されます。直方体の2つの次元は一定で、スクリーン上の光線の2次元間隔によって定義されます。3つ目の次元は可変で、計算された入射点と出射点によって定義されます。具体的には、スクリーン上の光線間の水平距離と垂直距離が $S$ である場合、各光線によって「検出」される体積は次のようになります。

$S\times S\times {\frac {t[2]-t[1]+t[4]-t[3]+\ldots +t[n]-t[n-1]}{L}}$

ここで、 $L$ は方向ベクトルの長さとして定義されます。（既に正規化されている場合は、1となります。）

$L={\sqrt {D_{x}^{2}+D_{y}^{2}+D_{z}^{2}}}$

それぞれ ${\tfrac {t[i]\ -\ t[i-1]}{L}}$ これは、固体内部にある光線セグメントの長さです。

この図は、レイキャスティングを用いてモデル化された立体の平行六面体を示しています。これは、平行投影カメラモデルの使用例です。

入光・出光分類

この図は、単一の光線が評価される合成木における「+」と「−」を使用した二項演算子の例を示しています。

レイキャスティング手順は、ソリッド構成ツリーの最上位から開始し、再帰的に最下位まで下り、プリミティブソリッドに関してレイを分類し、その後、左サブツリーと右サブツリーの分類を組み合わせてツリーを上に戻ります。

この図は、3つの二項演算子すべてについて、左分類と右分類を組み合わせたものを示しています。

リアルな陰影のある写真

レイキャスティングは、陰影のある画像を作成するための自然なモデリングツールです。GMリサーチラボのスコット・ロスとダニエル・バスによって開発されたグレースケールのレイキャスティングシステムは、1979年頃にラムテックカラーラスタディスプレイ上に画像を生成しました。画像を構成するために、このシステムはユーザーに次のコントロールを提供しました。

ビュー
- 視線方向と位置
- 焦点距離：幅角透視図法から平行まで
- ズーム係数
照明
- 光源の数
- 照明の位置と強度
- オプションで影をつける
- 周囲光と背景光の強度
表面反射率
- 拡散反射率
- %鏡面反射
- 送信率

この図は、2つの点光源による影のあるテーブルの場面を示しています。

リアルな効果をすべて実現するシェーディングアルゴリズムは計算コストが高いものの、比較的単純です。例えば、次の図は、単一の光源から発生する可能性のある追加の光線を示しています。

画像内の単一ピクセルをレンダリングするために、アルゴリズムは焦点から始まる光線を照射し、それが半透明の長方形と光沢のある円と交差することを確認します。次に、その点から、光線と表面の交点における表面法線と対称的に反対方向に、追加の光線を照射して、鏡面反射で何が見えるかを判断します。この光線は不透明な三角形と交差します。最後に、各光線と表面の交点が影になっているかどうかをテストします。「影検出」光線は、光線と表面の交点から光源に向かって照射され、その経路を遮る他の表面があるかどうかを判断します。

ターナー・ウィッテッドは、二次光線と追加の光線を「再帰的光線追跡」と呼んでいます。^{[ 6 ]} [鏡の部屋をレンダリングするにはコストがかかるため、再帰の数を制限するのが賢明です。] ウィッテッドは、透明物の屈折をモデル化するために、可視面の点から固体の屈折率によって決定される角度で二次光線を生成します。二次光線は、鏡面反射光線として処理されます。屈折の公式と図解例については、ウィッテッドの論文を参照してください。

エンクロージャーと効率

レイキャスティングは、問題解決のための総当たり的な手法と言えるでしょう。最小限のアルゴリズムは、その多様な用途と使いやすさを考慮すると非常にシンプルですが、アプリケーションでは通常、多数のレイが照射されます。アニメーション映画の1フレームをレンダリングするために、数百万本のレイが照射されることもあります。コンピュータの処理時間は、画面の解像度と、構成に含まれるプリミティブな立体／表面の数に比例して増加します。

合成ツリー内のソリッドの周囲に最小境界ボックスを使用することで、レイとソリッドの交差を網羅的に検索する処理は、効率的な二分探索に似ています。総当たりアルゴリズムは、レイが明らかにソリッドを外れた場合でも、常にツリー内のすべてのノードを訪問し、レイをプリミティブのローカル座標系に変換し、レイとサーフェスの交差をテストし、分類を結合するため、網羅的な検索を実行します。より高速なアルゴリズムは、「明らかに外れた」ことを検出するため、二分合成ツリーをソリッド合成が占める空間の階層的表現として使用します。ただし、位置、形状、サイズに関するすべての情報は、プリミティブソリッドが存在するツリーの葉に格納されます。ツリーの最上位ノードと中間ノードは、結合演算子のみを指定します。

すべての立体が占める空間を囲みで特徴付けることで、ツリー内のすべてのノードに位置とサイズ情報の抽象的な要約が与えられます。次に、迅速な「光線が囲みと交差する」テストによって、階層構造内の検索がガイドされます。テストがツリーの中間ノードで失敗した場合、光線は複合体の外にあると確実に分類されるため、サブツリーを再帰的にたどってさらに調査する必要はありません。

エンクロージャを使用することによるコスト削減効果を正確に評価することは困難です。なぜなら、それはプリミティブの空間分布（複雑性分布）と構成ツリーの構成に依存するからです。最適な条件は次のとおりです。

原始的な囲いは空間的に重なり合わない
構成ツリーはバランスが取れており、空間的に近いサブソリッドはツリー内でも近くなるように整理されている。

それとは対照的に、最悪の状況は次のとおりです。

すべての原始的な囲いは互いに重なり合っている

以下は、ロス氏のレイキャスティングに関する論文で行われた様々な性能改善点であるが、その後、他の研究者によってさらに大幅な改善がなされている。

早退: ツリー内の複合ノードの演算子が「−」または「&」であり、かつ光線が複合ノードの左側サブソリッドから外れていると分類される場合、光線は右側サブソリッドに対する分類に関係なく、複合ノードから外れていると分類されます。したがって、光線を右側サブソリッドに対して分類することは不要であり、効率性の観点から避けるべきです。
変革: 最初にスクリーンからシーンへの変換とプリミティブのシーンからローカルへの変換を組み合わせ、結果として得られるスクリーンからローカルへの変換をプリミティブのデータ構造に格納することで、レイとサーフェスの交点ごとに1つのレイ変換が不要になります。
再帰: 構成ツリーが深い場合、メモリの割り当てと解放と組み合わせると、再帰処理はコストが高くなる可能性がある。静的配列をスタックとして使用することで、再帰処理をシミュレートできる。
動的境界設定: 立体の可視エッジのみを表示する場合、レイキャスティングアルゴリズムは、レイを動的に制限して検索範囲を絞り込むことができます。つまり、レイがサブ立体と交差することがわかった後、アルゴリズムは画面に最も近い交点を使用して、「レイ交差ボックス」テストの深度制限を狭めることができます。これは、ツリーの最上部から始まる + の部分でのみ機能します。- と & の場合、レイの近くの「in」部分が後で「out」になる可能性があります。
一貫性: 一貫性の原理とは、隣接する2つのピクセルで見える表面は、異なるよりも同じである可能性が高いというものです。コンピュータグラフィックスやビジョンシステムの開発者は、この経験的な真理を効率とパフォーマンスの向上に活用してきました。線画の場合、エッジを含む画像領域は通常、画像全体の領域よりもはるかに小さいため、レイキャスティングは開いた領域ではなく、エッジ周辺に集中させる必要があります。これは、画面をレイで疎にサンプリングし、隣接するレイが異なる見える表面を識別する場合に、バイナリサーチによってエッジを特定することで効果的に実現できます。

アンチエイリアシング

エイリアシングによって生じるギザギザのエッジは、点サンプリング技術の望ましくない効果であり、ラスタ表示アルゴリズムの典型的な問題です。直線または滑らかな曲線のエッジはギザギザに見え、特にアニメーションでは、画像の動きによってエッジがぼやけたり、小さな動くエスカレーターのように見えたりするため、問題となります。また、光線間の間隔よりも小さいシーンの詳細が失われる可能性もあります。線画のギザギザのエッジは、エッジ追跡によって滑らかにすることができます。このようなアルゴリズムの目的は、1ピクセルの精度で画像を描画するために必要な線の数を最小限に抑えることです。その結果、滑らかなエッジが得られます。上記の線画は、この方法で描画されました。

陰影付き画像のギザギザしたエッジをサブピクセル精度で滑らかにするには、エッジに関する情報を得るために追加の光線を照射する必要があります。（一般的なアプローチについては、スーパーサンプリングを参照してください。）エッジは、サーフェスの交差または曲面のプロファイルによって形成されます。上記で説明したようにバイナリサーチで「コヒーレンス」を適用すると、ピクセル $（ X 、 Y ）の可視サーフェスがピクセル$ $（ X +1、 Y ）$ の可視サーフェスと異なる場合、それらの中間点 $（ X +1/2、 Y ）$ に光線を生成し、そこで可視サーフェスを識別できます。サンプル点間の距離はさらに細分化できますが、サーチは深くする必要はありません。ギザギザしたエッジを滑らかにするための主なサーチ深度は、エッジ全体の輝度勾配の関数です。ギザギザしたエッジを滑らかにするためのコストは、次の理由から許容範囲内です。

画像のエッジを含む領域は通常、全体の面積のごく一部であり、
二分探索で投げられる余分な光線は、深さ（エッジを形成する可視プリミティブの深さ）に制限される。

歴史

レイキャスティングの歴史については、「レイトレーシング（グラフィックス）」を参照してください。どちらも本質的には同じ技術を異なる名称で呼んでいるだけです。スコット・ロスは「レイトレーシング」という言葉を知る前に「レイキャスティング」という用語を考案しました。さらに、スコット・ロスがGM研究所でレイキャスティングを開発した時期は、ターナー・ウィッテッドがベル研究所でレイトレーシングの研究を行っていた時期とほぼ同時期でした。

初期のコンピュータゲームにおけるレイキャスティング

レイキャスティングレンダリングを使用したゲームで、高度な技術を用いて複数の高さレベルで床面をレンダリングします。

初期のファーストパーソンゲームでは、レイキャスティングを使用して、画面の水平幅全体にわたって単純な一次元スキャンを使用して、2Dプレイフィールドから3Dワールドを効率的にレンダリングしていました。^{[ 7 ]}初期のファーストパーソンシューティングゲームでは、2Dレイキャスティングを2Dワールドから3D効果を作成するテクニックとして使用していました。ワールドは3Dに見えますが、プレイヤーは上下を見ることができず、せん断歪みのある限られた角度でのみ見ることができます。^{[ 7 ]}^{[ 8 ]} このレンダリングスタイルでは、現代のエンジンの場合のように、フレーム内の各ピクセルに対してレイを発射する必要がありません。ヒットポイントが見つかると、投影歪みがサーフェステクスチャに適用され、結果から垂直列全体がフレームにコピーされます。このレンダリングスタイルでは、実行できるレンダリングの種類にも制限があります。たとえば、深度ソートはできますが、深度バッファリングはできない場合があります。つまり、ポリゴンは互いに完全に前面または背面にある必要があり、部分的に重なったり交差したりすることはできません。

Wolfenstein 3D

ビデオゲーム「Wolfenstein 3D」は、均一な高さの壁と単色の床や天井が接する正方形のグリッドに基づいて構築されています。世界を描画するために、画面ピクセルの各列に対して1本の光線がトレースされ、光線が壁に当たる場所と当たるまでの移動距離に応じて、壁のテクスチャの垂直スライスが選択され、スケーリングされました。^{[ 9 ]}

グリッドベースのレベルを採用した目的は2つあります。1つは、潜在的な衝突箇所がより予測しやすくなるため、光線と壁の衝突をより迅速に検出できること、もう1つは、メモリ使用量を削減できることです。しかし、広いエリアをエンコードするには余分な容量が必要になります。

シャドウキャスター

Raven Softwareのゲーム『ShadowCaster』は、 Wolfensteinをベースにした改良型エンジンを使用しており、床や天井のテクスチャリング、壁の高さの可変機能などが追加されています。

コマンチシリーズ

コマンチゲーム用にNovaLogicが開発したVoxel Spaceエンジンは、画面ピクセルの各列を通して光線をトレースし、各光線をハイトマップ内の点と比較しました。次に、ハイトマップの各要素をピクセルの列に変換し、どの要素が可視であるか（つまり、前面に描画されたピクセルによって遮蔽されていないか）を判断し、テクスチャマップから対応する色で描画しました。^[¹⁰^]