リアルタイムで3D迷路を表示する その４

長いつまらん話ですがｗ、これで終わりです。

面に色をつける話です。実際には色というよりは明るさの話です。
まずはゲーム画面で面の明るさを見てください。

 真正面にある面は明るい

 斜めになった面は暗い

 遠くにある面ほど暗い

諧調にあまり差がなくてわかりにくいですね。もっと極端に暗くなるようにした方が良いかもしれません。

それはともかく、このゲームは車のヘッドライトで壁が照らされているイメージです。
なので真正面にあるものは明るく、斜めになると少し暗くなり、遠くのものほど暗くなる、という見え方になるようにしています。

これには面の裏表判定で計算した内積の値を流用します。
視点からのベクトルと面の法線ベクトルとの内積は面の向きによってこのように変わります。

表を向いている面なので内積値はマイナスになります。なので絶対値で考えますが、正面では１．０、斜めを向くとこれが小さくなっていき、視線ベクトルに対して９０度横を向くと０．０となります。
（内積値が０の面は裏面と判断するので描画しませんが）
この０．０～１．０の内積値をそのまま面の明るさのファクターにしてやります。
（フラットシェーディング）

ただしこの方法だと面単位で明るさが変わるので面と面の境目で色が異なりちょっと不自然ではあります。
面の頂点の法線ベクトル毎に計算して面の内部でも色をなめらかに変化させればきれいな表示になります（グローシェーディング）が、当然計算時間がかかりますし、何より１つの div (の border) の中で色を変化させることはできません。

一応参考までにフラットシェーディングとグローシェーディングの見え方の違いを、他所からパチってきた画像で紹介しておきます。

左が面の法線ベクトルだけで計算したフラットシェーディング、
右が面の各頂点の法線ベクトルで計算したグローシェーディングです。
どちらもポリゴン数は同じです。


それはともかくとして、内積を使えば視線ベクトルに対して斜めになればなるほど暗くなるという表現ができることがお分かりかと思います。

次に遠い面ほど暗くなるですが 、実はこれもまったく同じロジックです。面の遠近によって何か処理をしているわけではありません。
下図を見てもらえばわかるように、遠い面は内積値（絶対値）が小さくなるのです。

というわけで面の裏表判断に使った内積値を流用することで余分な計算することなしに面の明るさを変更するためのファクターを得ています。




と、ここまで書いて、やっぱり遠くの面はより暗い方がヘッドライトで照らしてる感があっていいなと思い直しました。
やってみた結果がこれです。

内積に加え、面までの距離も考慮しました。
面までの距離は div の z-index として算出済ですので計算に負荷はかかっていません。


以上で長かった３Ｄ迷路の話は終了です。
お疲れ様でしたｗ

リアルタイムで3D迷路を表示する その３

隠面消去の話です。
視点から見て裏を向いている面は描画する必要がないので除外します。
前回の図で水色の面が表を向いている面、黒いのが裏を向いている面です。

面の裏表を判断するために各面にはあらかじめ法線ベクトルを設定しておきます。
（実行時に計算で求めても良いですが、その分処理が遅くなるのでデータとしてあらかじめ持たせておきます）
そうしておいて面が表を向いているか裏を向いているか判断するのですが、それには内積の計算を行います。

ベクトルの内積 dot はこんな式で求まります。

dot = u1 * u2 + v1 * v2 + w1 * w2

ここで (u1, v1, w1) と (u2, v2, w2) はそれぞれのベクトルの X, Y, Z 方向の成分です。
このゲームでは２次元で計算してオッケーなので、 v1 * v2 の計算は不要です（どちらも 0 なので)。

この内積の値は２ベクトルの関係によってこんな風になります。

ですので、面の裏表の判定は面の法線ベクトルとＺ軸（視線方向）との内積で判断できます。

つまり内積がマイナスの値であればこっちを向いている（表の面）ということです。
内積がプラスであった場合にはそれ以上の処理はしないようにします。

これで視錘台の内側でかつこちらを向いている面だけが集まりました。
これを描画するのですが、視点から見て近い面が遠い面を隠さないといけません。単にここまでで集めた面を描画しただけだと面の前後関係が正しくないので３Ｄ迷路に見えません。

面の前後関係が正しい表示

面の前後関係が正しくない表示

面の前後関係もいろいろ計算すると求まり、そうやって隠れた面を描画しないことで処理の向上に繋がる場合もありますが、ブラウザの場合は div を余分に表示するくらいは問題なく、それよりも隠れた面を表示しないように計算する方がコストが高いです。

なので、隠れた面を描画対象からはずすことはせずに、HTMLの機能で遠くにある面は遠くに、近くにある面は近くに表示するようにします。
つまり z-index の値で制御します。

このように視点から面b (Back Clipping Plane)までの距離から各面までの距離を引き算したものを div の z-index に設定してやります。

これで面が正しい順序で表示されるようになりました。
次回は面に色をつける話です。

リアルタイムで3D迷路を表示する その２

視錘台の内外判定の話です。

まず面aよりも手前にあるかどうかですが、これは視点から見て図形までの距離が面aまでの距離D1 よりも小さければ手前にあると判定します。
同様に面bよりも遠くにあるかは面bまでの距離 D2 よりも大きいかどうかで判定します。

図形までの距離が D1 よりも大きく D2 よりも小さければ画角の範囲にあるかを見ます。
図形の頂点毎の計算になりますが、図で P1 は視点からの距離でZ方向(奥行き)に Lz1 、X 方向(横)に Lx1 の位置にあります。
簡単のために画角が９０度だとすると、Lx1 < Lz1 であれば P1 は画角の範囲内であることになります。 P2 では Lx2 > Lz2 なので画角の範囲外であることになります。

前回説明した通り、頂点の内１つでも画角の範囲にあれば描画しますので、４点全て調べなくても途中で範囲内であると判断することもあるので、多少はスピードアップに繋がっているかもしれません。

このように判定はとても簡単なのですが、視点が原点で視線方向がZ軸であるという条件でなければ使えません。つまり、全ての図形の頂点座標をまず変換する必要があります。
表示せずに捨ててしまう図形の座標値まで変換するのは無駄なので、変換前に捨てられるものがあれば捨てるべきです。

このゲームで表示するのは全て同一サイズの直方体ですから、マス目として考えることができます。

このようなマップであった場合、下図にあるようにグレーで塗ったマス目は座標変換前に捨ててしまいます。

４５度右を向いた場合であれば下図のグレー部分を先に捨てます。

実際にはこんなきれいな角度でなく、たとえば１３度なんて角度の時もあるので話はもう少しややこしいのですが、ともかくこんな風に座標変換前に捨てられるものは捨ててしまうという考えをしています。


これで、直方体毎に描画するものを抽出できたわけですが、今度は１つの直方体について個々の面を描画するかどうかを判断します。

上の図で水色の部分は描画しますが、裏側の黒の部分は描画しません。
また手前にある面の陰になっている面は描画されません。
いわゆる隠面消去の処理が必要です。これについては次の回で。

リアルタイムで3D迷路を表示する

リアルタイムで３Ｄ迷路を表示するためにはなんとかして計算の回数を減らす必要があるのですが、ここではそのテクニック(?)を紹介します。

まず、div の border を使って台形を表示する、てのがこの３Ｄ迷路の大元になってます。これについては過去ログ参照ということでまた解説することはしませんが、 div を使うことでブラウザでも高速にポリゴンらしきものを表示することができます。

とはいえ、それを表示するためにいっぱい計算していたのでは遅いので、いろいろとごまかしながら計算をガンガンはしょります。

以下はゲームのメインスクリーンですが、画面中央に赤で水平線を引きました。これに注目。

この線を境に図形は上下で対称になっています。
つまり、上半分で計算したものはそのまま反転して下半分の表示に使っているわけです。
本来四角形を３Ｄ→２Ｄ投影する場合には４頂点すべてを計算しなければなりませんが、このように表示することで２頂点だけの計算で済ませています。

さらに壁の高さはすべて同じ、すなわちＹ座標は一定です。これはＹ座標を０(ゼロ)にして計算していることと同じで、実際に計算するのは横方向（Ｘ）と奥行き方向（Ｚ）だけになります。つまり３Ｄの計算ではなく２Ｄの計算で済んでしまうということです。
軸が１本無いことで削減できる計算量は相当なものになります。
（表示する際のＹ座標の値は奥行きＺの値の比例で表されます。要するに奥にあるものはＺの値に応じて値を小さくするだけです。）

次にクリッピングです。これは見えない部分をカットするということです。プログラムは馬鹿正直ですから実際には見えていないものでも０で割るとかいう事態が起こらない限りまじめに計算します。
その結果本来視角の外にあるものでも表示しようとしてワケのわからない図形がお目見えすることになります（たとえば本来真後ろにある図形をまじめに計算すると虚像が出現します）。
もちろん見えるべきでないものを計算する時間がもったいないですから、見えるものだけを計算すべきです。

下は他所からちょいと拝借してきた３Ｄクリッピングの図です。

原点が視点、Ｚ方向が視線の向きです。角θ（シータ）は画角です。これが小さいと望遠、大きいと広角になります。面aはフロントクリッピングプレーンと言い、これより手前のものは表示されません。面bはバッククリッピングプレーンと言い、これより向こうにあるものは表示されません。
通常面aは画面の表示領域と一致しています。つまりこの面に投影された図形がそのまま画面に表示される図形となります。
全体としてグレーの四角錘台（視錘台といいます）の内側にあるものだけが面aに投影されるように、視錘台の外にあるものを排除する作業を行うことになります。

ここで、ただ単に排除するだけなら良いのですが、図形をこの視錘台の６面で切ることになる場合もあります。たとえば直線の２端点P1とP2のうち片方が視錘台の内側、もう片方が外側だと、この直線を切らないといけません。また、P1P2の両方が視錘台の外だけれども線の中央部分は視錘台の中ということもありますので、線を２箇所で切るなんてことも必要になります。

このように図形をちょん切ることをクリッピングと呼ぶわけですが、 線ならまだしも面を切ると切り方によって三角形になったり五角形になったりして div では表現できませんし、そもそも切るロジックが面倒くさすぎてクラクラしますｗ　当然処理時間は無茶苦茶に長くなります。

そこで今回のゲームではこのちょん切るという作業は一切行っていません。
単に視錘台の外なら表示しない。少しでも視錘台の中に入っているなら全部表示、ということをしています。

当然視錘台の外にあるものを表示すると変なものが表示されたりしますので、いくつか手を打っています。

手その１：面aの外周より外側に描画しないよう、面aに相当する div に対して overflow:hidden を設定する。
→実際にはゲームのメインスクリーンの外側にも描画してしまっているのですが、HTMLの機能でそれを表示しないようにしています。

手その２：視点よりも後ろにあるものを表示しないよう、視点と面aの距離を十分に取る。
→視点よりも後ろにあるものを描画すると虚像が現れます。図形の頂点全てが視錘台の外にあれば表示しないロジックなので、面aにある頂点を置いたときに、そこからもっとも視点側にある頂点がそれでも視点よりも奥に（Zの正方向に）あれば虚像になりません（それよりもポリゴンが手前に来ると全頂点が視錘台の外になるので表示されない）
このゲームでは表示する図形は全て同じ大きさの直方体なので、その対角線よりも長い距離が視点と面aの間にあれば良いことになります。

字でずらずら書いても分かりにくいので図示します。上（Y軸の正方向）から見下ろしたと思ってください。

 上の方で３次元ではなく２次元で計算していると書きましたが、 実際この図のような平面で考えた計算を行っています。

ゲームメインスクリーンの overflow : hidden をはずすとこんな風になりますｗ

では、どうやって視錘台の内外を判定するのかですが、長くなったので、それは次回に。

マップ作成ツール

今度のゲームの１面分のマップデータは 90 x 90 の予定です。
さすがにこれを方眼紙に書いてから数値化して打ち込むというのは無理なのでツールを作りました。
javascript では無理なのでコンパイラ(C++)です。

まず迷路データを 90 x 90 の画像として作ります。黒以外のところが壁になります。

これをツールの画面にドロップします。

そうするとこのように数値化したテキストが作成されます。ついでにクリップボードにもコピーしてあるので、ソースにペタリとペーストすればおっけー。

ちなみに今回ここに貼った迷路の画像はこのブログ用に描いたいい加減なものですので、やらないようにｗ

こんな面もアリかもしれないｗｗｗ

IE8での処理速度が向上

FF がどうにも途中で考え事するようで表示がカクっと止まってしまうので更なる高速化を図りました。

結果、FF ではなく IE8 が遊べる速度になりましたｗ
FF は依然考え事なさります^^;;;

スクリーンショット貼っても何も伝わりませんし、前回とほとんど変わらない画像ですけどｗｗｗ
ちなみに今回やったことは、「掛け算の回数を減らす」です。