Quake式BSP(3)

副題：Portal列挙

■前回までの反省

唐突ですが、前回までの反省をしてみたいと思います。その前に言い訳。

この3D補講ってやつは、私の勉強と共に進めているもんで、誤りや説明不充分な点が非常に多いんです。実際にコードかじったり、追ったりしていると、後悔することしきりです。前回までのおかしな点を上げてみましょう。

まず、むやみにSolidだと言い過ぎました。Solidかどうかは、あとで決まることで、実際には、Emptyであるリーフも当然あるんですよね。属するポリゴンが無いからSolidなんてのは嘘です。まぁ、このあたり今後もうやむやになると思うので、あまり気にしないようにして下さい。前回までのSolidの利点は変わりありません。Solidの決定の仕方という問題は残りますけど。

次に、くだらない喩え話が長すぎました（笑）まぁ、それが功を奏して気づかれなかったかもしれませんが、こんなくだりがありましたね。「部屋に一歩入るまでは玄関側の壁は見えない」という感じの話です。間違ってないです。間違ってないんですけど、今回から行うPVSの作成では、対象はリーフであって、ポリゴンじゃ無い。つまりその部屋が見えると判断された時点で、部屋に属するポリゴンは全て可視対象になっている、ということですね。

そんなことわかってるよ、と言われるかもしれませんが、このあたり、ちょっとPVSに対する評価の違いになってくると思うんです。実際にやってみると、PVSで可視と判断されるリーフって実に多いんです。見えないものは不可視になるんでなくて、見える可能性のあるものは全て可視であると判断される、という表現になるでしょうか。わかりにくいですね。言いかえれば、すごい広いマップであるとかであれば、全体から比べて可視と判断されるものは少ないんですが、小規模なマップであれば、下手すれば全部見えることになる。効果０ってことです。

例えば、2DRPGですごく広いマップを組んでいたとしましょう。メモリに全部持っちゃうなんてとても出来ないから、部分にわけて、その部分マップの境界付近に来たときに、隣、もしくは隣接するマップを新しく読み込む。わかり易いし、素直な作戦です。

PVSって、それを自動化するような感じでしょうか。隣接するものを可視対象とする。そのことによって、その他の大部分が結果的に見えない、見えなくてもかまわない、とする。

また余談が長くなりました。でも、今回の話に関係あるんですよ。キーワードは、「隣接」です。

■Portalってなんだ

前回、Portalは扉口であるといった話をしました。例えば、部屋のドア、立派なPortalですね。では、これをプログラム的に見ればどうなるのかという話に進みましょう。

まず、これがどのように空間内で表現出来るか、です。簡単ですね。平面で、なおかつ領域が有限なもの、つまりはポリゴンです。ポリゴンでドアは表現することが出来ます。

次に、このドアの特性を見てみましょう。壁のなす平面上に乗っているのに気づきますね。また、床や天井を突き抜けてはいません。部屋の壁の一部になっています。また、このドアをあけると、隣接する部屋が眼に入ります。

部屋、Convexな空間、つまりはセルリーフです。BSPを思い出しながら上記の特性を考えて見ましょうか。

　　　　　　｜
■■■■■■■
　　　　　　■
　　　　　　■■■■■■
　　　　　　‖
　部屋Ａ　　‖　部屋Ｂ
　　　　　　‖
　　　　　　■■■■■■
　　　　　　■
■■■■■■■
　　　　　　｜

また変な図を書いてみました。ここで二重線の部分がドア、Portalです。

特性その１「壁の為す平面上に乗っている」に関して考えて見ましょう。この壁平面はなんでしょうか。もちろん前回までに散々言っていた、分断平面ですね。つまり、Portalは、分断平面上に乗っているということが言えます。

特性その２「床や天井を突き抜けない」は何を表しているのでしょうか。これは、Portalは同じ部屋に属する壁にクリッピングされている有限の領域であることを示しています。上記の図では、部屋Ｂを構成する壁によってクリップされていますね。

特性その３「隣接する部屋が眼に入る」のは簡単にわかります。部屋Ａと部屋Ｂに隣接しています。これは必須条件ですね。逆に言うと、違う２つのリーフに接続していないものはPortalとは呼ばない。というのも言えると思います。

なんとなく上記の特性を利用すると、Portalを作成することが出来そうです。やってみましょう。

■Portalを作る

次のような葉式BSPがあるとします。また、主な分断平面も表してあります。表記上はその他の壁（分断平面）を省略して、セルのみとしていますが、もちろん前回までと同様に、全ての壁に対して分断平面は設けられています。ただ、他のいずれも互いに分断しない凸形空間になっている為、表記を簡略化しました。

　　■■■■■■■
　　■　　　　　■
　　■　　　　　■
　　■　　Ａ　　■
　　■　　　　　■
　　■　　　　　■　↑　　　　　　　　　＋―�@―＋
――■■■　■■■――�@　　　　　　　　｜　　　｜
　　　　■　■　　　　　　　　　　　　　Ａ　＋―�A―＋
　　　　■　■　　　　　　　　　　　　　　　｜　　　｜
　　　　■Ｂ■　　　　｜　　　　　　　　　　Ｂ　＋―�B―＋
　　　　■　■　　　　■■■■■　　　　　　　　｜　　　｜
　　　　■　■■■■■■　　　■　　　　　　　　Ｃ　　　Ｄ
　　　　■　　　Ｃ　　　　Ｄ　■
　　　　■■■■■■■■　　　■
　　　　　　｜　　　　■■■■■
　　　　　←｜　　　←｜
　　　　　　�A　　　　�B

さて、ここからが問題なんです。いくつものアプローチのしかたがあるんですけど、ここは、本家本元、John Carmack 式、つまりは Quake式でやってみましょう。一見全体が見渡しにくいきらいがありますけど。

まずは、大外ノード(Outside Node)。区切りとなるノードを考えます。これは、全ての壁要素を含む、バウンディングボックスのようなものを考えていただければ間違いないでしょう。そして、その直方体の各面を構成するポリゴンを考えます。以下の図のようになります。

＝＝＝＝＝＝＝＝＝＝ａ＝＝＝＝＝＝＝＝＝
‖　　　　　　　　　↓　　　　　　　　‖
‖　　■■■■■■■　　　　　　　　　‖
‖　　■　　　　　■　　　　　　　　　‖
‖　　■　　　　　■　　　　　　　　　‖
‖　　■　　Ａ　　■　　　　　　　　　‖　　　　外　　　　　　　　�@：ａｂｃｄ
‖　　■　　　　　■　　　　　　　　　‖　　　　｜　　　　　　　　�A：
‖　　■　　　　　■　↑　　　　　　　‖　　＋―�@―＋　　　　　　�B：
‖――■■■　■■■――�@　　　　　　‖　　｜　　　｜　　　　　　Ａ：
‖　　　　■　■　　　　　　　　　　　‖　　Ａ　＋―�A―＋　　　　Ｂ：
ｂ→　　　■　■　　　　　　　　　　←ｃ　　　　｜　　　｜　　　　Ｃ：
‖　　　　■Ｂ■　　　　｜　　　　　　‖　　　　Ｂ　＋―�B―＋　　Ｄ：
‖　　　　■　■　　　　■■■■■　　‖　　　　　　｜　　　｜
‖　　　　■　■■■■■■　　　■　　‖　　　　　　Ｃ　　　Ｄ
‖　　　　■　　　Ｃ　　　　Ｄ　■　　‖
‖　　　　■■■■■■■■　　　■　　‖
‖　　　　　　｜　　　　■■■■■　　‖　ａ（�@、外）
‖　　　　　←｜　　　←｜　　　　　　‖　ｂ（�@、外）
‖　　　　　　�A　　↑　�B　　　　　　‖　ｃ（�@、外）
＝＝＝＝＝＝＝＝＝＝ｄ＝＝＝＝＝＝＝＝＝　ｄ（�@、外）

ここで作った、ａｂｃｄは、Portalの一種、つまり、セルとセルをつなぐポリゴンです。つなぐ片方はすぐにわかりますね。大外ノードが片方です。もう片方はというと……。まだ未定です。�@というしかありません。

この４つのPortalを、ヘッドノード、つまり、分断面�@の属するノードに突っ込みます。ここまでが、上図になります。ちなみに、表記の「：」の部分は、Portalの属しているノードを表し、「（前、後）」の部分は、つないでいるノードを表しています。

次にノード�@に注目します。まず、分断面�@に乗る、大きなポリゴンを新しく作ります。バウンディングボックスのサイズを越える大きさのポリゴンを作れば間違いはないでしょう。そうして出来たポリゴンを、現在のノード、つまり�@に属しているPortalで、クリップします。ａｂｃｄですね。

ここからちょっと迷いやすくなります。そうして出来た�@に沿う新しいPortal（そう、Portalなんですよ）を、自分の前子ノードと後子ノードに突っ込んでやります。ここまでで、こうなります。

＝＝＝＝＝＝＝＝＝＝ａ＝＝＝＝＝＝＝＝＝
‖　　　　　　　　　↓　　　　　　　　‖
‖　　■■■■■■■　　　　　　　　　‖
‖　　■　　　　　■　　　　　　　　　‖
‖　　■　　　　　■　　　　　　　　　‖
‖　　■　　Ａ　　■　　　　　　　　　‖　　　　外　　　　　　　　�@：ａｂｃｄ
‖　　■　　　　　■　　　　　　　　　‖　　　　｜　　　　　　　　�A：ｅ
‖　　■　　　　　■↑　　　　　　　　‖　　＋―�@―＋　　　　　　�B：
‖＝＝＝＝＝＝＝＝＝ｅ＝＝＝＝＝＝＝＝‖　　｜　　　｜　　　　　　Ａ：ｅ
‖　　　　■　■　　　　　　　　　　　‖　　Ａ　＋―�A―＋　　　　Ｂ：
ｂ→　　　■　■　　　　　　　　　　←ｃ　　　　｜　　　｜　　　　Ｃ：
‖　　　　■Ｂ■　　　　｜　　　　　　‖　　　　Ｂ　＋―�B―＋　　Ｄ：
‖　　　　■　■　　　　■■■■■　　‖　　　　　　｜　　　｜
‖　　　　■　■■■■■■　　　■　　‖　　　　　　Ｃ　　　Ｄ
‖　　　　■　　　Ｃ　　　　Ｄ　■　　‖
‖　　　　■■■■■■■■　　　■　　‖　ａ（�@、外）
‖　　　　　　｜　　　　■■■■■　　‖　ｂ（�@、外）
‖　　　　　←｜　　　←｜　　　　　　‖　ｃ（�@、外）
‖　　　　　　�A　　↑　�B　　　　　　‖　ｄ（�@、外）
＝＝＝＝＝＝＝＝＝＝ｄ＝＝＝＝＝＝＝＝＝　ｅ（Ａ、�A）

わかりにくいですか？今は、ノード�@に注目をしていることを忘れないで下さいね。図の右部の変化にも注目してくださいね。

次に、今属しているノードのPortal達を、この新しいPortal（ｅ）で判別（classify)します。前にあるか、後ろにあるか。または、BSPの時の壁のように分割されるか、です。そして、分けたものを、前ノードと子ノードに振り分けて与えてやります。この場合だと、Ａか�Aですね。また、その時、Portalのつないでいるノード情報も変更してやりましょう。また、図に変更が加わります。見てください。

＝＝＝＝＝＝＝＝＝＝ａ＝＝＝＝＝＝＝＝＝
‖　　　　　　　　　↓　　　　　　　　‖
‖　　■■■■■■■　　　　　　　　　‖
‖　　■　　　　　■　　　　　　　　　‖
ｆ→　■　　　　　■　　　　　　　　←ｇ
‖　　■　　Ａ　　■　　　　　　　　　‖　　　　外　　　　　　　　�@：
‖　　■　　　　　■　　　　　　　　　‖　　　　｜　　　　　　　　�A：ｄｅｈｉ
‖　　■　　　　　■↑　　　　　　　　‖　　＋―�@―＋　　　　　　�B：
＝＝＝＝＝＝＝＝＝＝ｅ＝＝＝＝＝＝＝＝＝　　｜　　　｜　　　　　　Ａ：ａｅｆｇ
‖　　　　■　■　　　　　　　　　　　‖　　Ａ　＋―�A―＋　　　　Ｂ：
‖　　　　■　■　　　　　　　　　　　‖　　　　｜　　　｜　　　　Ｃ：
‖　　　　■Ｂ■　　　　｜　　　　　　‖　　　　Ｂ　＋―�B―＋　　Ｄ：
‖　　　　■　■　　　　■■■■■　　‖　　　　　　｜　　　｜
ｈ→　　　■　■■■■■■　　　■　←ｉ　　　　　　Ｃ　　　Ｄ
‖　　　　■　　　Ｃ　　　　Ｄ　■　　‖　
‖　　　　■■■■■■■■　　　■　　‖　ａ（Ａ、外）　ｇ（Ａ、外）
‖　　　　　　｜　　　　■■■■■　　‖　ｄ（�A、外）　ｈ（�A、外）
‖　　　　　←｜　　　←｜　　　　　　‖　ｅ（Ａ、�A）　ｉ（�A、外）
‖　　　　　　�A　　↑　�B　　　　　　‖　ｆ（Ａ、外）
＝＝＝＝＝＝＝＝＝＝ｄ＝＝＝＝＝＝＝＝＝　

さて、これで、ノード�@に注目するのは終わりました。次に注目するのは、ノード�Aです。手順を再確認しましょう。

手順１：分断面に相当するポリゴンを作り、現在属するノードの全てのPortalでクリップする。そして出来あがった新しいPortalを、両方の子ノードに送る。

手順２：新しいPortalによって、現在属するノードの全てのPortalを分類し、前ノードと子ノードに送る。

意外とシンプルですね。�Aノードに注目してやってみましょう。

�Aの平面に沿って大きなポリゴンを作る。属する他のPortal（ｄｅｈｉ）でクリップする。それを両方の子ノードに送る。

新しく出来たPortal(ｊ）を用いて、属しているPortal全てを分類し、両子ノードに振り分ける。

ここまででこうです。

＝＝＝＝＝＝＝＝＝＝ａ＝＝＝＝＝＝＝＝＝
‖　　　　　　　　　↓　　　　　　　　‖
‖　　■■■■■■■　　　　　　　　　‖
‖　　■　　　　　■　　　　　　　　　‖
ｆ→　■　　　　　■　　　　　　　　←ｇ
‖　　■　　Ａ　　■　　　　　　　　　‖　　　　外　　　　　　　　�@：
‖　　■　　　　　■　　　　　　　　　‖　　　　｜　　　　　　　　�A：
‖　↑■　　　　　■　  　　↑　　　　‖　　＋―�@―＋　　　　　　�B：ｉｊｌｎ
＝＝ｋ＝＝＝＝‖＝＝＝＝＝＝ｌ＝＝＝＝＝　　｜　　　｜　　　　　　Ａ：ａｆｇｋｌ
‖　　　　■　‖　　　　　　　　　　　‖　　Ａ　＋―�A―＋　　　　Ｂ：ｈｊｋｍ
‖　　　　■　‖　　　　　　　　　　　‖　　　　｜　　　｜　　　　Ｃ：
‖　　　　■Ｂ‖　　　　｜　　　　　　‖　　　　Ｂ　＋―�B―＋　　Ｄ：
‖　　　　■　‖　　　　■■■■■　　‖　　　　　　｜　　　｜
ｈ→　　　■　‖■■■■■　　　■　←ｉ　　　　　　Ｃ　　　Ｄ
‖　　　　■←ｊ　Ｃ　　　　Ｄ　■　　‖　
‖　　　　■■‖■■■■■　　　■　　‖　ａ（Ａ、外）　ｊ（Ｂ、�B）　
‖　　　　　　‖　　　　■■■■■　　‖　ｆ（Ａ、外）　ｋ（Ａ、Ｂ）
‖　　　　　←‖　　　←｜　　　　　　‖　ｇ（Ａ、外）　ｌ（Ａ、�B）
‖　　↑　　　‖　　　　�B　↑　　　　‖　ｈ（Ｂ、外）　ｍ（Ｂ、外）
＝＝＝ｍ＝＝＝‖＝＝＝＝＝＝ｎ＝＝＝＝＝　ｉ（�B、外）　ｎ（�B、外）

注意すべきなのは、Portal（ｅ）が分断されて、ｋとｌに分けられていることですね。もちろん、Ａに属していたｅも�Aに属していたｅも同じ物なので、結果的にＡに属していたPortalも分断されたように見えるかも知れません。ここらへんは実装の時に、頭が痛くなるでしょうね。でも、落ち着いて考えれば大丈夫でしょう。右側下の、Portalが分断しているノード一覧を見てください、

ｅ（Ａ、�A） → ｋ（Ａ、Ｂ） ＋ ｌ（Ａ、�B）

�Aが、Ｂと�Bにわかれただけです。ツリー構造の推移そのままですね。

で、�Bにも注目して、がんがん進みましょう。えいや、でこんな図になります。

＝＝＝＝＝＝＝＝＝＝ａ＝＝＝＝＝＝＝＝＝
‖　　　　　　　　　↓　　　　　　　　‖
‖　　■■■■■■■　　　　　　　　　‖
‖　　■　　　　　■　　　　　　　　　‖
ｆ→　■　　　　　■　　　　　　　　←ｇ
‖　　■　　Ａ　　■　　　　　　　　　‖　　　　外　　　　　　　　�@：
‖　　■　　　　　■　　　　　　　　　‖　　　　｜　　　　　　　　�A：
‖　↑■　　　　　■↑  　　　　↑　　‖　　＋―�@―＋　　　　　　�B：
＝＝ｋ＝＝＝＝‖＝＝ｐ＝‖＝＝＝ｑ＝＝＝　　｜　　　｜　　　　　　Ａ：ａｆｇｋｐｑ
‖　　　　■　‖　　　　‖　　　　　　‖　　Ａ　＋―�A―＋　　　　Ｂ：ｈｊｋｍ
‖　　　　■　‖　　　　‖　　　　　　‖　　　　｜　　　｜　　　　Ｃ：ｊｏｐｒ
‖　　　　■Ｂ‖　　　　‖　　　　　　‖　　　　Ｂ　＋―�B―＋　　Ｄ：ｉｏｑｓ
‖　　　　■　‖　　　　‖■■■■　　‖　　　　　　｜　　　｜
ｈ→　　　■　‖■■■■‖　　　■　←ｉ　　　　　　Ｃ　　　Ｄ
‖　　　　■←ｊ　Ｃ　←ｏ　Ｄ　■　　‖　
‖　　　　■■‖■■■■‖　　　■　　‖　ａ（Ａ、外）　ｊ（Ｂ、Ｃ）　ｑ（Ａ、Ｄ）　
‖　　　　　　‖　　　　‖■■■■　　‖　ｆ（Ａ、外）　ｋ（Ａ、Ｂ）　ｒ（Ｃ、外）
‖　　　　　←‖　　　←‖　　　　　　‖　ｇ（Ａ、外）　ｍ（Ｂ、外）　ｓ（Ｄ、外）
‖　　↑　　　‖　　↑　‖　　　↑　　‖　ｈ（Ｂ、外）　ｏ（Ｃ、Ｄ）
＝＝＝ｍ＝＝＝‖＝＝ｒ＝‖＝＝＝ｓ＝＝＝　ｉ（Ｄ、外）　ｐ（Ａ、Ｃ）

さて、見事に全てのリーフ（大外ノード含む）にPortalを割り振ることが出来ました。右側下の分断セル一覧には、単なるノードは含まれず、リーフのみになりました。また、この時点で、右側上図右のPortal一覧を見てみると、それぞれのセルが実はPortalで区切られている事が一目瞭然です。

で、今まで、順に�@、�A、�Bと注目するノードを見てきたわけですが、これはノードのトラバーサル（探索）順だったんですね。ですんで、古典的BSPの際に出てきたような再帰のロジックに基づいてコーディングすることが出来ます。いやはや、再帰の強力さ、身をもって知った感じがします。長いですよね。この節。

■しかしまだまだこんなものじゃない

いやなこと思い出してしまいました。最初のBSP、かなり省略した形だと言っていましたよね。これを省略なしでやらなければ、本当のPortalの説明に入れない。うーん、やるか。

＝＝＝‖＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
‖　　‖　　　　　　ｅ　　　　　　　　‖
‖　　＝＝＝＝＝＝‖＝＝＝＝＝＝＝＝＝＝
‖　　‖　　　　　‖　　　　　　　　　‖
‖ｅ　‖　　　　　‖　　　　　　　　　‖
‖　　‖　　Ａ　　‖　　　　ｅ　　　　‖
‖　　‖　　　　　‖　　　　　　　　　‖
‖　　‖　　　　　‖　  　　　　　　　‖
＝＝＝‖＝‖＝‖＝‖＝＝‖＝＝＝＝＝＝＝
‖　　　　‖　‖　　　　‖　　　　　　‖
‖　　　　‖　‖　ｅ　　‖　　ｅ　　　‖
‖　　　　‖Ｂ‖　　　　‖　　　　　　‖
‖　　　　‖　‖　　　　＝＝＝＝‖＝＝＝
‖　　　　‖　＝＝＝＝＝＝　　　‖　　‖
‖　ｅ　　‖　‖　Ｃ　　‖　Ｄ　‖　ｅ‖
‖　　　　＝＝＝＝＝＝＝＝　　　‖　　‖
‖　　　　‖　‖　　　　＝＝＝＝‖＝＝＝
‖　　　　‖ｅ‖　ｅ　　‖　　　　　　‖
‖　　　　‖　‖　　　　‖　　　ｅ　　‖
＝＝＝＝＝‖＝‖＝＝＝＝‖＝＝＝＝＝＝＝

うわ、おかしくなりそうだ！ここにいたって、全ての壁が全てPortalになってしまいました。また、表記の中で、ｅと書いてあるところは、壁を持っていないリーフ、つまりEmptyなリーフです。

まず、これらのPortalのなかで、本当に行き来できるPortal、つまり、両側が同じ属性を持つもの以外を無くしましょう。簡単ですね。Portalは２つのセルを結んでいるので、それらを比較していけば済みます。

そうすると、このようになります。

＝＝＝‖＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
‖　　‖　　　　　　ｅ　　　　　　　　‖
‖　　■■■■■■■＝＝＝＝＝＝＝＝＝＝
‖　　■　　　　　■　　　　　　　　　‖
‖ｅ　■　　　　　■　　　　　　　　　‖
‖　　■　　Ａ　　■　　　　ｅ　　　　‖
‖　　■　　　　　■　　　　　　　　　‖
‖　　■　　　　　■　  　　　　　　　‖
＝＝＝■■■＝■■■＝＝‖＝＝＝＝＝＝＝
‖　　　　■　■　　　　‖　　　　　　‖
‖　　　　■　■　ｅ　　‖　　ｅ　　　‖
‖　　　　■Ｂ■　　　　‖　　　　　　‖
‖　　　　■　■　　　　■■■■■＝＝＝
‖　　　　■　■■■■■■　　　■　　‖
‖　ｅ　　■　‖　Ｃ　　‖　Ｄ　■　ｅ‖
‖　　　　■■■■■■■■　　　■　　‖
‖　　　　‖　‖　　　　■■■■■＝＝＝
‖　　　　‖ｅ‖　ｅ　　‖　　　　　　‖
‖　　　　‖　‖　　　　‖　　　ｅ　　‖
＝＝＝＝＝‖＝‖＝＝＝＝‖＝＝＝＝＝＝＝

素晴らしいですね。次に、大外をSolidであるとして、外につながるリーフを、Solidにしていきましょう。また、SolidとつながるPortalを持つリーフも、Solidにしましょう。下図、★がそうです。

＝＝＝‖＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
‖＃＃‖＃＃＃＃＃＃Ｓ＃＃＃＃＃＃＃＃‖
‖＃＃■■■■■■■＝＝＝＝＝＝＝＝＝＝
‖＃＃■　　　　　■＃＃＃＃＃＃＃＃＃‖
‖Ｓ＃■　　　　　■＃＃＃＃＃＃＃＃＃‖
‖＃＃■　　Ａ　　■＃＃＃＃Ｓ＃＃＃＃‖
‖＃＃■　　　　　■＃＃＃＃＃＃＃＃＃‖
‖＃＃■　　　　　■＃＃＃＃＃＃＃＃＃‖
＝＝＝■■■＝■■■＝＝‖＝＝＝＝＝＝＝
‖＃＃＃＃■　■＃＃＃＃‖＃＃＃＃＃＃‖
‖＃＃＃＃■　■＃＃★＃‖＃＃Ｓ＃＃＃‖
‖＃＃＃＃■Ｂ■＃＃＃＃‖＃＃＃＃＃＃‖
‖＃＃＃＃■　■＃＃＃＃■■■■■＝＝＝
‖＃＃＃＃■　■■■■■■　　　■＃＃‖
‖＃Ｓ＃＃■　‖　Ｃ　　‖　Ｄ　■＃Ｓ‖
‖＃＃＃＃■■■■■■■■　　　■＃＃‖
‖＃＃＃＃‖＃‖＃＃＃＃■■■■■＝＝＝
‖＃＃＃＃‖Ｓ‖＃Ｓ＃＃‖＃＃＃＃＃＃‖
‖＃＃＃＃‖＃‖＃＃＃＃‖＃＃＃Ｓ＃＃‖
＝＝＝＝＝‖＝‖＝＝＝＝‖＝＝＝＝＝＝＝

で、最後に、どちらか一つでも、SolidにつながるPortalを除去します。すると、こうなります。

＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃
＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃
＃＃＃■■■■■■■＃＃＃＃＃＃＃＃＃＃
＃＃＃■　　　　　■＃＃＃＃＃＃＃＃＃＃
＃＃＃■　　　　　■＃＃＃＃＃＃＃＃＃＃　　　�@（Ａ、Ｂ）
＃＃＃■　　Ａ　　■＃＃＃＃＃＃＃＃＃＃　　　�A（Ｂ、Ｃ）
＃＃＃■　　　　　■＃＃＃＃＃＃＃＃＃＃　　　�B（Ｃ、Ｄ） 
＃＃＃■　　�@　　■＃＃＃＃＃＃＃＃＃＃
＃＃＃■■■＝■■■＃＃＃＃＃＃＃＃＃＃
＃＃＃＃＃■　■＃＃＃＃＃＃＃＃＃＃＃＃
＃＃＃＃＃■　■＃＃＃＃＃＃＃＃＃＃＃＃
＃＃＃＃＃■Ｂ■＃＃＃＃＃＃＃＃＃＃＃＃
＃＃＃＃＃■　■＃＃＃＃■■■■■＃＃＃
＃＃＃＃＃■　■■■■■■　　　■＃＃＃
＃＃＃＃＃■�A‖　Ｃ　�B‖　Ｄ　■＃＃＃
＃＃＃＃＃■■■■■■■■　　　■＃＃＃
＃＃＃＃＃＃＃＃＃＃＃＃■■■■■＃＃＃
＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃
＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃
＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃

どうですか？見事に、３つのPortalが残りました。しかも、形を残しただけでなく、どのセルとどのセル隣接しているかという情報まで残っています。完璧ですね。

これが、Portal列挙(Portal Enum)という段階です。雰囲気はつかめたでしょうか？

■回りくどいのは訳がある

ところで、以前、リーク(leak,漏れ）のことを説明するとお約束しましたね。今回、最後のほうになって、Emptyだとか、Solidだとか回りくどくなったのはそのせいです。下図を見てください。

＝＝＝＝＝＝＝＝＝＝＝　＝＝‖＝＝‖＝＝＝＝＝
‖　｜ｅ　｜　　　　‖　‖　‖ｅ　　　　　　‖ 
‖　■■■■　　　　‖　‖　■■■‖　　　　‖
‖　■　　■　　　　‖　‖　■　　‖　　　　‖　
‖ｅ■Ａ　■Ｂ　　　‖　‖ｅ■Ａ　‖Ｂ　　　‖
‖―■■■■■■■―‖　‖＝‖＝＝■■■■  ＝
‖　｜　　■　　　　‖　‖　　　　■　　　　‖
‖　｜　　■　　　　‖　‖　　　　■　　　　‖
‖ｅ｜Ｃ　｜ｅ　　　‖　‖ｅ　Ｃ　　ｅ　　　‖
＝＝＝＝＝＝＝＝＝＝＝　＝＝‖＝＝‖＝＝＝＝＝

左側が、最初のＢＳＰの形、右側が今回の最後の手順で異種のセルをつなぐPortalを無くしたところです。

少し気をつけて見ていただきたいんですがＢとＣは、ポリゴンを持っているので、Emptyではありません、ですんで、ＡとＢ、ＢとＣの間のPortalは生き残り、eとＢやeとＣの間のPortalは除去されてしまいました。

ここで、次の手順、外のSolidと結果的に繋がるリーフをSolidとして埋めると、

＝＝‖＝＝‖＝＝＝＝＝
‖＃‖＃＃＃＃＃＃＃‖ 
‖＃■■■‖＃＃＃＃‖
‖＃■＃＃‖＃＃＃＃‖　
‖＃■Ａ＃‖Ｂ＃＃＃‖
‖＝‖＝＝■■■■＃＝
‖＃＃＃＃■＃＃＃＃‖
‖＃＃＃＃■＃＃＃＃‖
‖＃＃Ｃ＃＃＃＃＃＃‖
＝＝‖＝＝‖＝＝＝＝＝

さて、なんだか面白くないことが置きました。最後に、Solidに隣接するPortalを除去すると、

＃＃＃＃＃＃＃＃＃＃＃
＃＃＃＃＃＃＃＃＃＃＃
＃＃■■■■＃＃＃＃＃
＃＃■＃＃■＃＃＃＃＃　
＃＃■Ａ＃■Ｂ＃＃＃＃
＃＃■■■■■■■＃＃
＃＃＃＃＃■＃＃＃＃＃
＃＃＃＃＃■＃＃＃＃＃
＃＃＃Ｃ＃＃＃＃＃＃＃
＃＃＃＃＃＃＃＃＃＃＃

やな感じです。全部Solidになりました。ここで、もし、部屋の中を示す地点（例えば、プレイヤーのスタート地点）が属するセルがＡだったらどうでしょうか？始まったとたん壁の中ですね。即死です。Ｍａｌｏｒです。

こんな時は、リーク、つまり、漏れがあるとして、駄目なことにします。そのために、外側をまじめに塗りつぶしたりしてるんです。

ただ、利点もあります。（いや、利点の方が大きいかも）例えば、上記の例がこんなだったとすると、

＝＝＝＝＝＝＝＝＝＝＝
‖　｜ｅ　｜　｜　　‖
‖　■■■■　｜　　‖
‖　■　　■　｜　　‖
‖ｅ■Ａ　■ｅ｜Ｂ　‖
‖―■■■■―■■■‖
‖　｜　　｜　■　　‖
‖　｜　　｜　■　　‖
‖ｅ｜ｅ　｜ｅ｜Ｃ　‖
＝＝＝＝＝＝＝＝＝＝＝

塗りつぶすと、こんな風になります。

＃＃＃＃＃＃＃＃＃＃＃
＃＃＃＃＃＃＃＃＃＃＃
＃＃■■■■＃＃＃＃＃
＃＃■　　■＃＃＃＃＃
＃＃■Ａ　■＃＃Ｂ＃＃
＃＃■■■■＃■■■＃
＃＃＃＃＃＃＃■＃＃＃
＃＃＃＃＃＃＃■＃＃＃
＃＃＃＃＃＃＃＃Ｃ＃＃
＃＃＃＃＃＃＃＃＃＃＃

どうですか？Ａは生き残って、最初から怪しかったＢとＣはいなくなりました。そして、Quakeでは、この外側に行ってしまった壁、ポリゴンを無くして、Ａのように生き残ったセルに属するポリゴンだけで、ＢＳＰのレベルから作り直しています。確かに、ポリゴンが減れば、もっと気の利いたＢＳＰが作れるかもしれませんからね。

なにより、Quakeともなれば、一般のユーザーでもレベルを作ったりするわけですし、専用デザイナーに無理な注文（制約）をつけながらマップデザインをさせるというのも懐の狭い了見ですよね。ですんで、プログラム上で二重三重のチェックや最適化をしているんでしょうか。

■難関を一つ越えた

さぁ、これで、Portalという名のポリゴンの集まりが手に入りました。あとは、PVSに移るだけですね。

今いるセルから見える可能性のあるセルは一体どれなのか。その鍵はPortalが握っています。扉を開けて、外の世界に眼を向けてみることにしましょうか。

■サンプルコード(1999/01/11追加)

話だけでは説得力が無いので（笑）サンプルコードを作ってみました。

サンプルバイナリ(36.9KB)

サンプルソース(19.3KB)

ここまでで出てきた話、BSP生成とPortal列挙までのサンプルです。mybsp.cppがBSP生成、myportal.cppがPortal列挙を行っています。ソースをリコンパイルされて、ステップ実行をされると面白いかもしれません。

<戻る>

devilman/team-UJI 1998/12/05 Updated 1999/01/11