階層的円筒レイキャスト法

本手法では交点計算の回数が多くなるため，まず，交点の計算に，高速な計算法として知 られるM¨ollerらの方法[M¨oller and Trumbore 1997]を用いる．なお，C言語のソースコー ドなども彼らの論文内に示されているので参照されたい．

3.3.1 光線の発射点と発射方向

ここでは著者による光線の分岐のさせ方について説明する．階層的に光線追跡を行う際，

光線は前回求まった交点の中点から 垂直方向 に放たれるものとする（図3.3 (b)参照）．

しかし，３次元で考えた場合，直線に対して垂直な方向は，この直線を法線とする平面上の すべての方向となる．このため，図3.3 (a)のように水平方向に対しても垂直という拘束条 件が必要となる．

しかし，２回目以降の光線追跡では交点の配置はこのようなグリッド状にはならないため，

もう少し一般的な求め方を考える必要がある．また，分割を行う方向も，図3.4のように，水 平方向(a)，垂直方向(b)，対角方向(c)の３方向を考える必要がある．

(a) (b) (c) (d)

図3.4: 分割方向．(a)前回得られた交点．(b)垂直方向への分割．(c)水平方向への分割．(d)対角方向への分割

3.3. 階層的円筒レイキャスト法 27

光線の発射点と発射方向の求め方を説明するが，まず対角方向を求めた後に，水平方向と 垂直方向を求めていく．図3.5と図3.6はこの手順を示したものである．

まず，対角方向の発射点と発射方向を次の手順で求める（図3.5参照）．

• ^{発射点： ４つの交点の 平均点 *1を発射点とする．}

• 発射方向：この平均点と交点により４つの三角形の面を張ることができるので，各三 角形の法線を求め，この法線を平均したベクトルの方向を発射方向とする．

次に，水平方向と垂直方向の発射点と発射方向を求める（図3.6参照）．手順は両方向と も同じであるため，ここでは垂直方向の求め方を示す．

• 発射点： ２つの交点の 中点 を発射点とする．

• ^{発射方向：}対角方向の処理で得られた発射点を２点加える（交点線分の両側の２点）．

交点と加えた発射点を用いて２枚^*2の三角形の面を張ることができるので，各三角形の 法線を求め，この法線を平均したベクトルの方向を発射方向とする．

(a) (b) (c) (d)

x z y

N

図3.5: 対角方向への分割．まず，前回得られた交点を考え(a)，その平均点を発射点とする(b)．次に，交点と 求めた平均点を用いて三角形を作成し(c)，これらの三角形の法線の平均を発射方向とする(d)．

3.3.2 発射点とモデルの位置関係による発射方向の変更

光線の発射方向に関しては更に条件をつける必要があり，新たな発射点が円筒から見てモ デルの内側にあるか外側にあるかで，次のように発射方向を変える必要がある．

• 発射点がモデル内部の場合： 法線方向と順方向に光線を放つ．

• 発射点がモデル外部の場合： 法線方向と逆方向に光線を放つ．

*14つの点であるので，ここでは中点，すなわち，線分上の中央の点という言葉を避けた

*2４枚ではなく２枚なのは，発射点としてとった中点が交点を結んだ直線上に存在するため，図3.6 (c)の場合，水平方向に は折り目が生じないためである．

28 第3章 オクルージョン領域の復元を目的とした階層的円筒レイキャスト法

(a) (b) (d) (e)

x z y

N

(c)

図3.6: 水平・垂直方向への分割．まず，前回得られた交点を考え(a)，その平均点を発射点とする(b)．次に，法 線を求めるが，このままでは三角形を作成できないため，対角方向への分割の際に求めた平均点を2点加え(c)， この平均点と交点を用いて三角形を作成し(d)，これらの三角形の法線の平均を発射方向とする(e)．

図3.7は交点がモデルの形状に収束する様子を表したものであり，(a)は上述した条件に従っ て光線を発射したもの，(b)はこれとは逆の操作を行ったものである．この図から分かるよ うに，発射方向が正しくない場合は復元される形状が破綻することになる．

3.3.2.1 発射位置の判断方法

発射点がモデルの内部にあるかどうかは，発射点を通る円筒軸から円筒面までの線分とモ デルとの交差回数で判断できる．図3.8はこれを示したものであり，図中(b)のように発射 点がモデル外部にある場合は，円筒面から発射点までのモデルとの交点数が偶数となる．一 方，図中(c)のように発射点がモデル内部にある場合は，交点数が奇数となる．

以上の手順を繰り返すことで，オクルージョン領域を捕捉することができる．

3.3. 階層的円筒レイキャスト法 29

(a)

図3.7: 発射点とモデルの位置関係による光線の発射方向の変更．(a)モデル外部のときは法線方向に，内部のと きは法線とは逆方向に発射した場合．(b) (a)とは全く逆方向に発射した場合

cylinder

1 2

1

(a) (b) (c)

1 1

2 2

3

model

ray

図3.8: 発射点がモデルの外部にあるか内部にあるかの判定法．(a)のモデルの外部と内部にある２点の発射点に 向けて，円筒面から光線を垂直に放った場合，(b)のように発射点がモデル外部の場合は，光線は発射点に到達 するまでにモデル表面と 偶数 回交差する．一方，(c)の発射点がモデル内部にある場合には，この交差回数は

奇数 となる．

30 第3章 オクルージョン領域の復元を目的とした階層的円筒レイキャスト法