レイとの交差判定

June 15, 2014

始めに

レイトレを始めるには、どのようなレンダリングアルゴリズムを使うとしても、まずはレイと何らかの幾何形状との交差判定処理を書かなくてはなりません。ここでは最も基本的な幾何形状である球、平面、三角形に対するレイとの交差判定と、交差があった場合のその位置と法線を得る方法についてまとめます。

レイ

レイトレーシングでの交差判定は「レイ vs 何か」という形で行われます。レイ(Ray:光線)は、開始位置と方向を持つ半直線として表現されます。光が何らかの原因でどこかの点で発生し、その後何かに当たるまで直進し続けることからも納得しやすい表現だと思います。

レイの開始位置を$o$、方向を$d$、さらに開始位置からどれだけ$d$方向に進んだかを表す量tを使って次のようにレイ上の点は表現されます。

レイとの交差判定は対象の幾何形状とこの式を連立したものを解くという形になります。またレイは前回の交差位置から再度射出されるというケースが多いですが、通常数値は有限精度しか持てないことから射出した表面に再度衝突したと誤って判定されることがあります。これを防ぐために、$t$の値は0からではなくそれよりもほんの少しだけ大きな値に設定するのが定石です。

またdは必ずしも正規化されているとは限りません。ワールド座標系と別にローカル座標系が設定できるようなシステムの場合、ローカル座標系での交差判定をワールド座標系からローカル座標系への変換が$d$に掛かったまま計算しておけば、tの値は最初からワールド座標で計算したときと同じ値になるので、ローカル座標系で正規化してしまった場合に比べて計算を省略できます。ただワールド座標系しか持たないようなシンプルなシステムであれば、正規化されていると考えて問題ないと思います。

陰関数表現ができる幾何形状に対する交差位置と法線

ある幾何形状上の点$p$を次のように表現できる場合があります。

このような関数を陰関数と呼びます。この$p$がもしレイの線上に存在するなら次のようになるはずです。

このtが実数解を持つことがそのままレイとその幾何形状が交差を持つことを意味します。

次に法線について考えてみます。法線はこの陰関数の勾配となることが知られています。

簡単に説明します。陰関数$f(p)$のある方向$l$への方向微分は、勾配を使って次のように表現できます。

ここで$l$は実は$p$での接平面に沿ったベクトルであったことが判明したとします。そうすると$\cfrac{ \partial f(p) }{ \partial l }$は0となります。つまり次のようになります。

ということになります。通常は$grad~f(p)$が常に0であることはないので、$l$(接平面上のベクトル)に対して垂直であれば上の式が成立することになり、そのようなものは法線に他なりません。ということで$grad~f(p)$は法線ベクトルだったということがわかります。

ということでこの陰関数が表現する表面の法線が欲しい場合は勾配を求めます。

$ n = grad~f(p) = \biggl( \cfrac{\partial f(p)}{\partial x}, \cfrac{\partial f(p)}{\partial y}, \cfrac{\partial f(p)}{\partial z} \biggr) $

レイトレでは法線は単位ベクトルを使うので、最後にこれを正規化して終わりです。陰関数を持つ形状に関しては、これらの方法を使っていきます。

球とレイ

レイトレーシングと聞くと真っ先に思い浮かべられるのは、完全鏡面の球が描画された画像ではないでしょうか。幾何形状としてもっとも単純で、交差判定もとても単純なものなので、レイトレのプログラムを組む場合に真っ先に実装されるものだと思います。

半径$r$を持ち中心が原点にある球を考えます。その表面は次のような陰関数で表現することができます。

これに最初のレイの式を入れてみます。

この式をtに関して展開すると次のような普通の二次方程式の形になります。

A,B,Cはそれぞれ次のようになります。

これを解いた結果からtは次の二通りが求まります。中学生で習う二次方程式の解の公式そのままです。

二次方程式が実数解を持つか否かは$B^2-4AC$の部分の正負できまります。正であれば$t_0$、$t_1$ともに実数解を二つの解を持つことになり、0であれば重解で解を一つだけ持つことになり、負であれば実数解を持たないことになります。それぞれ「レイが球を串刺しにしている状態」、「球のキワをレイがかすった状態」、「球との交差はない状態」を表しています。また解がある場合でも、それがレイの"後ろ"、つまり前述した最小のt値を下回った場合は有効な解ではないので捨て去られます。

レイのパラメーター$t$が見つかれば、それをレイの式に入れればそのまま交差の位置となります。

次にその点での法線を計算します。法線は陰関数の勾配なので次のようになります。

これを正規化したものが法線になります。座標がそのまま法線方向になることは直感的にも正しいかと思います。

平面とレイ

球ができたら床と壁が欲しいところです。これでコーネルボックスが作れるようになります。平面を原点を通り$n$を向いたものとして考えます。これの陰関数は次のようになります。

$p$は平面上の点です。球と同じようにレイの式を入れると次のようになります。

これをtに関して変形すると次のようになります。

同様に、法線も勾配から次のように求めることが出来ます。

(ちょっとバカバカしいですが)平面全体の法線と、交差した位置での法線は同じであることがわかりました。

三角形とレイ

球と平面だけでもレイトレっぽいシーンは作れますが、自作のメッシュのモデルを表示したい場合などは三角形との交差がとれなくてはなりいけません。三角形はこれまでの面と違い陰関数で表現できるものではないので改めて考える必要があります。

三角形は、平面の一部を切り取ったものと考えることができます。レイと平面は同時に二箇所で交差することは無いので、交差位置が平面上に見つかった場合、それが三角形の内部にあるかないかを判定すればいいことになります。ここでその内部にあるかの否かの判定は三角形の重心座標系を使って行います。重心座標$(u,v)$のそれぞれの成分が$[0,1]$かつ、それらの和が$[0,1]$となっていれば良いわけです。またこのUV値は頂点法線からシェーディング用法線を算出するときのように、頂点のプロパティを補間するために流用できます。このアルゴリズムはMöller–Trumbore intersection algorithmと呼ばれています。事前計算無しのレイ対三角形の交差判定では早い部類と言われています。

デモ

マウスドラッグでカメラを回転
マウスホイールでズームイン、ズームアウト
rayでレイの数を増減
objectTypeで交差判定対象を変更
resetでレイとオブジェクトの回転を再設定

最後に

早足でレイといくつかのプリミティブとの交差について解説しました。しかし触れていないことが沢山有ります。

「全部原点に置いて考えていたけれど、適当な場所に置かれていた場合はどうするの？」
「他のプリミティブ形状はどうするの？」
「プリミティブを部分的に切り取ったような形状はどうするの?」
「偏微分成分が必要になってきたけど、どうやってとるの？」

このあたりは各自調べるということでお願いします!! \
# 昨年の参加者のコードを眺めるといいかもしれません。