最適化というのはとどまるところを知らない。
コードを書いてからその速度を検証するようなタイプの最適化は、私も随分やったもんだが、最近は年をとったせいか、とみにそういうガリガリやるやりかたがおっくうになって、頭で考える時間が長くなる。実装・検証が二の次になってる。イカン。イカンね。年寄りは。
さて、今日も今日とてLandscapeの話になるのだが、昨日よりさらに突っ込んだ話をしたいと思う。
察しのいい読者ならお気づきの通り、今回は頭でしか考えていないので、コードは全くない。
まぁこれもちと、面白いテーマかもしれないので、暇つぶしによんでみていただきたい。
|
|
たこ焼き屋
はぬま〜ん
営業中
|
さて、昨日のPrejudiceで、どうやらトータルとしては一番効率がよさそうだとアタリはつけたものの実装はしてないスキャンコンバージョン方式での視野に入る頂点(面倒臭いので、以後は「可視頂点」とでも呼ぶことにしようか)をみつける方法について、まずは補足しよう。
スキャンコンバージョン法というのは、基本的に二次元のコンベックス・ポリゴン(凸多角形)を塗りつぶし描画するためのアルゴリズムだ。
図では、白く半透明表示されている三角形を、たとえば塗りつぶすとする。実は、その塗りつぶした部分にある頂点のほぼすべてが、まるまる全部、可視頂点になるのだ。
ここで、戸惑う方がいるかもしれないので補足すると、昨日示したコード(直線方程式による比較法)では、厳密には三角形にはなっていなかった。あれは、あくまでも直線の条件を共有する頂点であり、無限遠まで表示してしまうことになる。
しかし、現実に必要なのは、無限遠のものではなく、近傍の頂点データだ。どのみち、遠過ぎるものは如何に巨大でも見えないという３Ｄの暗黙の法則によって、ある程度以上離れたデータは必要なくなる。もっといえば却って邪魔なのである。
この邪魔ものを、スキャンコンバージョンはいとも簡単に排除してくれる。いや、むしろスキャンコンバージョンの場合は、邪魔物がなければ絶対に可視頂点を計算できないのである(言うまでもないが有限面積の凸多角形でなければこのアルゴリズムは使えないので当然だ)。
|
|
スキャンコンバージョン法はおそらく優れた可視頂点判定メソッドである。
しかし、オーバーヘッドが完全に払底されるわけではない。
|
|
私は昨日、前フレームで作成した情報を再利用することで高速な可視頂点判定を行う方法について提案した。
ここでもう少しそれを補足すると、図のような場合、黄色で示されるベクトルが前フレームの視野座標系であり、緑色で示されるベクトルが、新しい(描画すべき)視野座標系である。
このとき、この三角形に含まれる頂点すべてを再検査するのは馬鹿げている。
この例の場合、可視頂点算出に際して本当に必要なのは、薄い紫色で示した部分を修正することだけだ。
この手法について、昨日は象限毎に比較判定を行えばいいと言った。私としては、それは間違いではないと考えている。
しかし、これと同等のことが、スキャンコンバージョン法を使ってもできるのではないか。否、頂点が多くなればなるほど、総当たりで比較するのはどのみち不利である。
繰り返しになるが、スキャンコンバージョン法なら、無駄な頂点比較を極力押さえることができる。
この例は回転の場合だけを論じている。
それでは平行移動する場合はどうだろうか。
|
|
すると途端に問題は複雑化し、限られた三角形を求めればいいというわけにはいかなくなる。
しかし考え様によっては、これは意欲的なチャレンジであるとも言える。
図で言うと、黄色から緑に移動した場合、(a)と(c)の部分に関してなんらかの修正処置が必要ということになる。
先ほどの例では、あくまで回転半径にあるものしか「象限が同じだが可視でないもの」にカテゴリされていないので、移動に関してそのようなリストは全くの役立たずということになる。
だが、好意的に考えれば、視野座標系が「前方へ」平行移動した場合は、必ず(a)の部分は台形になる、と捉えることができる(無論、これには任意の回転が伴っているはずだから図から受ける印象ほど簡単な作業ではなくなるが)。
また、(c)の形も決定する。
ここまで決定してしまえば、「条件(1) 前方にしか移動しない」「条件(2) 左右にしか旋回しない」タイプのものであれば最適なアルゴリズムを見つけ出せるかもしれない。
が、いかんせん面倒過ぎる。
あ、それに今思ったけど、さっきの回転の図は間違ってる(どこか間違っているかは宿題にしよう/がーん)。
ということは、やっぱり大人しくスキャンコンバージョンを使うのがベストなのか。
うーむ。つまらん結末。
|
|