A Structured Polygon Model in Cosideration of Shade and Shadow and its Real-time Rendering

光の照射状況を考慮した階層型ポリゴンデータの リアルタイムレンダリング

A Structured Polygon Model in Cosideration of Shade and Shadow and its Real-time Rendering

情報工学専攻 田島 知明

Tomoaki TAJIMA 1

本論文では多数のポリゴンが存在する情景を，影を表 現し，かつ，リアルタイム性を保持する手法を提案する．

影領域中のポリゴンは暗く表現され，詳細形状を確認で きないことが一般的であることに着目する．提案手法で は，主成分分析を用いて，ポリゴンモデルを階層化するこ とで，各階層に含まれる集合が影領域に含まれるか，否 かを一括判定し，影領域に対して効率的に詳細度制御を 行う．本手法の効果をシミュレーションで検証した結果，

形状を定義するポリゴンが密集し，かつ，影領域がまと まっている情景に特に有効であることが示された．

2

現在幅広く利用されているコンピュータ・グラフィック ス(CG：Computer Graphics)技術の中で，リアルタイ ムレンダリングは，3次元ゲームや仮想現実などのリア ルタイムシミュレーションを必要とする分野で不可欠な 存在である．それらの分野では，形状のより精密な表現，

ならびに，情景のより写実的な表現に関する要求水準が 高まっている．前者を達成するためには，ポリゴンを細 かく定義し，より多数のポリゴンによる形状表現が有効 である．また，後者を達成するためには，他の物体に光 が遮蔽される現象の影(shadow)などを表現することが 有効である．影を表現するため，シャドウマップ法と呼 ばれる手法[1]が提案されているが，影を付加しない場合 に比べ，計算量は倍増する．また，計算量はポリゴン数 に比例して増大するため，多数の物体が存在する情景に 対して，リアルタイム性の確保が困難である．

そこで，本論文では多数のポリゴンが存在する情景を，

影を表現し，かつ，リアルタイム性を維持する手法の構 築を目的とする．このために本論文では，影領域中のポ リゴンは暗く表現され，詳細形状を確認できないことが 一般的であることに着目する．そこで，主成分分析を用 いてポリゴンを階層化することで，各階層に含まれる集 合が影領域に含まれるか，否かを一括判定する手法を提 案する．本手法により，リアルタイムレンダリングと影 の適切な表現を両立させる．

3

本論文では主成分分析を用いて，形状を定義するポリ ゴン集合を階層化し，各階層で点集合，点集合の重心，面 集合，面集合を包含する球(外包球)を保持する．また影 領域判定の際，遮蔽物体を球で近似する（内包球）．それ らを用いて，影領域，ならびに背面消去領域の判定を行 う．ここで影領域は，階層と遮蔽物体との位置関係を比 較することで行う．影領域と判定された場合，詳細度制 御を行い，ポリゴン数を削減する．以下詳細を述べる．

3.1

まず，ポリゴンモデルを階層化するために一度ポリゴ ンを削減し，モデルを簡略化する．簡略後の点それぞれ に，簡略化の際，影響を受ける面（簡略する際の頂点分 割により，除去される面とその隣接する面）を保持する．

また頂点分割前の二つの頂点を保持する．次に，簡略後 の点すべてを一つの点集合とし，位置ベクトルに対する 主成分分析を行う．これにより，点集合から主軸(主成分 ベクトル)を求め，主軸と垂直でデータ点の中心を通る平 面により，点集合を分割する．ここで点集合を分割する 際，同時に点集合から，点それぞれに保持されている面 を一つの集合にし，階層に格納する．分割された点集合 を下位階層とし，以降同様に分割を行う．具体的には，各 分割操作において，次の処理を行う．

1. 各階層に保持されている点集合を入力とし，主成 分分析を行い，点集合の重心と主成分ベクトルを 求める．

2. 計算された主成分ベクトルに垂直で，かつ重心を 通る平面により，階層の点集合を分割する．

3. 分割される点集合を親，分割して生成された点集 合を子とする二分木構造を生成する．

4. 分割された面集合から外包球を求め，それと重心，

点集合，面集合を保持する．

この操作を点集合が1個の点になるまで繰り返す．

3.2

影領域判定を行う際，各階層の重心を光源を視点とし た座標系(以下，光源座標系)に変換する．次に，各階層 の重心を光源座標系に変換した点をvAとし，外包球の半 径の見かけの大きさをrAとする．また，遮蔽物体の重心 を光源座標系に変換した点をvBとし，また内包球の半径 の見かけの大きさをrBとする．vAとvBの距離をdと する(図1)．ここで，内包球は，遮蔽物体の重心から，物 体を構成する面の中で，最も近い面の重心との距離の大 きさを半径とする．このため，影領域判定の際，影でな い領域も影と判定される誤判定を防止する．d < rB−rA

の場合，その階層のポリゴン集合は影領域内と判断し，詳 細度制御を行い，その階層以下のポリゴンを削減する．一

方で，d > rB+rAの場合，光照射領域内であると判断

する．またどちらの条件も満たさない場合，条件を満た すまで，階層を下げて，同様の判定を行う．最下層でも 条件を満たさない場合，階層のポリゴン集合は可視領域 とする．ここで，可視領域とは影でない，かつ背面でな い領域を指す．

提案手法は，影領域に含まれるポリゴン集合をできるだ け上位階層で判定することで，処理の効率化を図る．こ のため，影領域がまとまりをもつ場合に効果的である．

図1: 影領域判定

3.3

視点からの距離によって，可視領域に含まれるポリゴ ンの詳細度を変更する．その際，投影面の大きさを球で 近似する．その大きさの範囲（以下，基準範囲と呼ぶ）で の物体の大きさによって，詳細度を決定する．視点から 物体までの距離が大きく，物体が小さく見えるほど，詳 細度を下げる．ここで，r1：外包球の半径，r2：物体位置 における基準範囲の断面の半径，S1：外包球の断面積，S2

：物体位置における基準範囲の断面積とする（図2）．

r1 ≥r2となる場合は，投影面に占める物体の割合が 高く，重要性が高いと判断し詳細に表示する．r1< r2と なる場合，式(1)により物体の基準範囲に占める割合を

図2: 距離による詳細度制御

求め，その値が小さくなるほど重要性が低くなると判断 し，簡略化して表示する．

S1

S2

= r²₁π r²₂π =r₁²

r₂² (1)

以上より，視点からの距離による物体の詳細度R(0< R <

1)を次式で決定する．

R=





1 (r1≥r2)

r²₁

r²₂ (r1< r2) (2)

3.4

影領域が視点から近い場合に詳細度を低減させると，画 質を下げる可能性がある．そのため，影領域の詳細度変更 と距離による詳細度変更を組み合わせる．このとき，本研 究では色彩心理を利用して，影を色として扱う．同じ距離 にある物体でも，物体の色によっては，実際よりも大きく 見えたり(膨張色)，小さく見えたりする(収縮色)[2]．一 般に，収縮色は黒のような明度の低い色だとされている．

例えば，黒地の上の白い丸と，白地の上の同じ直径をも つ黒い丸を同時に見る．その際，後者は前者より約5分 の1ほど小さく見えるとされている[3]．したがって，本 論文では，影領域のポリゴン数を，面積が可視領域であっ た場合の0.8倍とするために，式(1)に係数k(k= 0.8) を乗じる．

S1

S2

=k·r²1π

r²₂π =k·r²1

r²₂ (3)

したがって，詳細度Rは以下で定められる．

R=





1 (r1≥r2) k·^r_r¹²2

2

(r1< r2) (4)

3.5

Pmaxを階層に格納されている全ポリゴン数，Pminを 予め定める簡略後の最小ポリゴン数とする．以上の議論 に基づき，まず視点からの距離，影による詳細度Rを求 め，その値に応じて各階層のポリゴン数をポリゴン数P を次式で決定する．

P = R(Pmax−Pmin) +Pmin (5)

以下に本手法の特徴を示す．

• 影領域による詳細度制御を適用することで，情景 に応じて，適切なポリゴン数で表現できる．

• ポリゴンモデルを階層化することで，冗長な判定 回数を省略でき，効率的に判定できる．

4

4.1

提案手法をOpenGLを用いて実装したシステム上で，

Stanford bunny（ポリゴン数69451）[4]を対象として，

検証した．実験では，提案手法を適用した場合，適用し ない場合について比較する．なお，影を発生させるため，

情景中に平行光源を1個，ならびに遮蔽物体（直方体）を 1個配置する．図3に対象物体と遮蔽物体の位置関係を示 す．この情景に対する視点を固定し，対象物体と遮蔽物 体との距離を変化させた．まず，対象物体を視点からの 距離15.0の地点に固定する．その上で，遮蔽物体を−x 軸方向に0.05ずつ 移動させる操作をx=−5.0まで200 回行い，1フレームの処理時間を計測した．表1にシミュ レーション環境を示す．

図3: 物体と遮蔽物体の位置関係

表1: シミュレーション環境

CPU Pentium4 3.0GHz

メモリ 1GB

ハードディスク 200GB ビデオカード GeForce 6600 GT

OS Windows XP Home Edition

4.2

全視点における情景における処理時間の平均値を表2 に示す．表2より，提案手法がポリゴンモデルを削減し，

かつ，描画時間を短縮できることを確認できる．また，詳 細度変更・判定時間は0.009秒であることから，描画時 間に影響を与えていない，さらに，描画時間も0.0702秒 であるため，影表現された多数のポリゴンからなるモデ ルを描画可能である．

図4より，遮蔽物体の位置と処理後のポリゴン数，な らびに影領域の判定回数の関係を図4に示す．ここで，

−4.0≤x≤4.0のとき，対象物体が影に含まれ，−4.0≤ x≤ −2.0，2.0≤x≤4.0のとき，部分的に含まれてい る．図4より，対象物体に生じる影の範囲に応じてポリゴ ン数が減少するのがわかる．特に，−2.0< x <2.0は対 象物体全体が影に覆われてる場合であり，最もポリゴン数 が減少している．これにより，情景に応じて，適切なポリ ゴン数で表現されているのがわかる．次に図4より，判定 回数に注目する．対象物体に部分的に影が生じていると き，判定回数は増大している．しかし，−4.0≤x≤ −2.0， 2.0≤x≤4.0の平均判定時間は0.002秒であり，描画時 間に影響を与えていない．また−2.0< x <2.0のとき，

判定回数は1回である．これは最上階層で影と判定され たため，下位階層の判定が省略されることに起因する．し たがって，ポリゴンモデルの階層化により，冗長な計算 を省略できることがわかる．そして，−5.0≤x <−4.0，

4.0< x≤5.0は対象物体に影が生じていない範囲であ

る．このときも判定回数は1回であり，平均判定時間は

0.00075秒である．これにより，遮蔽物体により影が生じ

ない場合でも，本手法の影領域判定処理は描画時間に影 響を及ぼさないことが確認できる．

次に図5，図6に実行画像を示す．また，図7に図5， 図6の差分画像を示す．ここで，輝度差が大きいほど，白 く表示し，輝度差があったピクセルを含む領域を赤の楕 円で囲んでいる．図5，図6を見ると，オリジナル画像と 提案手法を用いた画像に見かけ上，差はない．また，図7 より，大きい輝度差をもつピクセルが見た目に与える影 響が少ないことがわかる．これにより，見かけの精度が 維持されていることがわかる．

表2: 実験の実行結果

提案手法なし 提案手法 平均ポリゴン数[個] 69451 39207 詳細度変更・ − 0.009 判定処理[s/frame]

描画処理[s/frame] 0.090 0.0505

合計[s/frame] 0.098 0.0702

図4: ポリゴン数と判定回数の関係

図5: オリジナル画像

図6: 提案手法画像

図7: 差分画像

5

本論文では，主成分分析を用いてポリゴンモデルを階 層化し，効率的な影領域判定と詳細度制御を行うことで，

リアルタイムレンダリングと影表現を両立させる手法を 提案した．本論文では，ポリゴンモデルを対象とし，写 実性の高い情景をリアルタイムで表現できた．提案手法 は，上位階層から順次判定を行うことで，効率化を実現 した．このため，形状を定義するポリゴンが密集し，か つ，影領域がまとまっている情景に特に有効と考えられ る．今後の課題としては，より複雑な光照射，遮蔽物体 状況への適用などが挙げられる．

謝辞

本研究を通じ，懇切丁寧な御指導，御鞭撻，及び多く の御支援を賜りました，中央大学理工学部情報工学科 牧 野光則助教授に深く感謝致します．

参考文献

[1] 床井研究室：http://marina.sys.wakayama-u.ac.jp/

[2] 山脇 惠子，“図解雑学 よくわかる色彩心理”，ナツ メ社，2005.

[3] I．D．アルタモーノフ，“目の錯覚 映像時代におけ るその積極的役割”，綜合科学出版，1972． [4] Stanford Computer Graphics Laboratory：

http://www-graphics.stanford.edu/

[5] H. Hoppe, “Progressive meshes”, ACM SIG- GRAPH ’96, pp.99-108, 1996.

[6] 金井 崇, “表示・編集・圧縮のための多重解像度表現技 術”,情報処理学会誌, Vol. 41, No.10, pp.1108-1112, 2000．

関連発表

田島知明, 牧野光則, “階層型ポリゴンデータを用いた影 の詳細度制御”,電子情報通信学会マルチメディア・仮想 環境基礎研究会，(2008.3.22予定).