« 元気玉の成れの果て | トップページ | Beyond the Dead Center »

2010年8月13日 (金)プログラマー的処理を減らすための数学

おはようございます。本日の当番、プログラマーの大川です。

プレッシャーに押し潰されそうになる「プログラマー的デザイン表現」8回目!…と、言いたいところですが、
今回遂に!ネタが尽きてしまいました。いや、あるにはあるんですが、モデリングが間に合いませんでした(泣)
申し訳ございませぬ。

とはいえ、ここまでやってきてプログラミング以外のネタを話す訳にはいかないので、
今回は同じプログラマーであるK.Y君のお題を横取りして「処理を減らすための数学」をやってみようかと思います。
K.Y君、すまぬ。

さて、具体的にどんな数学かと言いますと、そこは従来のお題である「グラフィックス」における
処理負荷軽減の為の数学となります。今回は「カリング」についてお話します。

通常、ゲームシーンにはありとあらゆるオブジェクトが置かれています。
キャラクターであったり、アイテムといったものですね。

これら無数に置かれるオブジェクトを描画する場合、明らかに見えないと判っているオブジェクトに関しては
事前段階で極力排除しておく(つまり描画しない)必要があります。

何故かって…?
そりゃ無駄な処理を省く為です!

それを行う処理が今回紹介する「カリング」です。
とはいっても、カリングにも色々種類があるので、今回は3つ紹介します。

まず最も基本的な方法が「視錐台カリング」です。
視錐台とは、3D空間上において、実際に画面に表示される領域を定義したもので、カメラ位置と向き、画角等から
算出します。算出された視錐台は6つの平面(±XYZ)で構成されます。

この6つの各平面の内側にオブジェクトが存在する場合、そのオブジェクトは表示領域内にあります。
下図に示すように、ある平面と交差状態にある場合でも「一部は表示されている」という事が判ります。

※平面における内外判定については、数学系のサイトを探せば幾らでも出てきますので、ここでは割愛します。
 また、今回の図は便宜上、全て二次元で書かれていますが、実際には三次元で処理します。


2010_0812_01

次に「ポータルカリング」です。
ポータルとは、その名の通り「出入り口」の事です。ここでは、ある場所から他の場所を見ることが出来る
「可視領域」の事を指します。え?意味不明????では、下図をご覧下さい。

2010_0812_02

ポータルを利用したカリングを行うには、まずグラフ管理による空間分割が必要です。
A⇔B、B⇔Cといった具合です。各空間を繋ぐ赤色で示された領域、これがポータルとなります。
今回、ABCはオブジェクトではなく、空間を定義しています。

まず、視点位置から現在居る空間(この場合だとA)を割り出します。これは簡単ですね。
当然、空間Aは見えている状態です。

次にAと隣接しているポータルに対して視錐台判定を行います。
ここで重要なのは、空間に対してではなく、ポータルのみ判定する、という事です。

視錐台判定でこのポータルが見えるのであれば(この場合、A⇔Bのポータル)、その先のB空間も見えている、
という事になります。さて、ここで計算が入ります。ここで検出したポータル領域に沿って視錐台を再計算します。
すると新しく生成された視錐台(黄色)は、最初のポータル領域分を加味した形状になります。

この視錐台を使用して、次にB空間と繋がっているB⇔Cポータルとの可視判定を行います。
図でも判るように、新しい視錐台ではB⇔Cポータルは見えません。
つまり、この視点からではCの空間は見えない(つまり描画しなくて良い)という事が判ります。

このケースでは、各空間を繋ぐポータルは1つだけですが、複数ある場合は再帰的に判定を行います。

このポータルカリングですが、インドア環境のシーンでよく使われます。
インドア環境だと大抵の場合において「扉」や「窓」が配置されますので、それをポータルとして定義します。
但し、前述したように隣接状態を定義するデータが別途必要になるので、お手軽に使える、というものではありません。

最後に「オクルージョンカリング」を紹介します。
ポータルカリングと比べて原理は簡単、その割には使える処理かと思います。

言葉の意味ですが、オクルージョンとは「遮蔽」の事で、ここでは遮蔽物を利用したカリング処理の事を指します。
これも図で説明したほうが早いので、まずは下図をご覧下さい。

2010_0812_03

見れば判るかと思いますが、視点の先にAというオブジェクトがある場合、BはAに「遮蔽」されていて
見ることは出来ません。このAを遮蔽物(オクルーダー)として定義し、Bに対する遮蔽判定を行ってみます。

まず、視点から見えているオクルーダーのポリゴンを平面として定義します。次に、見えているポリゴンの各頂点と
視点位置から平面を生成します。結果、黄色で示された平面の集合体が出来上がります。

ここまで来れば、後は簡単。視錐台判定の応用で、各平面とオブジェクトの位置関係を判定するだけです。
視錐台カリングでは「全て内側で表示有り」ですが、この場合では「全て内側で表示無し」となります。
判定基準と平面の数が異なる以外、視錐台カリングと処理体系は同じです。

あ、ちなみにA自身は無視します。

オクルージョンカリングは「パーテーション」のように配置するだけです。ポータルカリングのようなグラフ管理も
必要ありません。置きたいところに置くだけでカリング処理が可能なので、活用出来る幅は大きいかと思います。

ということで、今回は苦し紛れの数学講座になってしまいました(汗)
いや、案外役に立つのでは、と思いつつ、後は本家のK.Y君に引き継ぎたいと思います。

K.Y君、よろしく。

follow us in feedly
result = encodeURIComponent( "http://www.accessgames-blog.com/blog/2010/08/post-da2b.html" );document.write( "result = " , result );&media=https%3A%2F%2Ffarm8.staticflickr.com%2F7027%2F6851755809_df5b2051c9_z.jpg&description=Next%20stop%3A%20Pinterest">

| | コメント (0) | トラックバック (0)

« 元気玉の成れの果て | トップページ | Beyond the Dead Center »

プログラマー」カテゴリの記事

コメント

コメントを書く



(ウェブ上には掲載しません)


コメントは記事投稿者が公開するまで表示されません。



トラックバック


この記事へのトラックバック一覧です: プログラマー的処理を減らすための数学:

« 元気玉の成れの果て | トップページ | Beyond the Dead Center »