NeoFT構想/内部仕様案/10

NeoFT構想/内部仕様案

風景（地形＋構造物）描画アルゴリズム †

• 投稿者: c477?
• 優先順位: 普通
• 状態: 提案
• カテゴリー: グラフィック・音響
• 投稿日: 2009-11-04 (水) 13:12:41

メッセージ †

地形と構造物（乗り物なども含む）の描画アルゴリズムについて考察する。

基本方針として、無駄なスプライト描画を減らしてパフォーマンスを維持するものとし、多少手間を掛けてでも無駄か否かの判定を描画前に行うべきと考える。
実装においては、ビューの段階的拡大と４方回転が必要なことを考慮しなくてはならない。
拡大や回転に伴うマップ座標から画面上のピクセル座標への変換は、描画部分のコアに直接埋め込まず、必ず特定の座標変換オブジェクトを介して行うものとする。

基本概念 †

可視領域（描画範囲） †

通常、マップは一度に画面に収まりきるほど小さくはない。
そのため、地形のどの範囲が描画されるのか、どの構造物が描画されるのか、判定しなくてはならない。
FreeTrainでは、マップデータは三次元のボクセル配列であり、特に「高さ」方向はほとんどの場合10ボクセル程度しかないので、地表上の可視エリア＋マップ高さ分を全判定しても、パフォーマンス上さほど問題はなかった。
NeoFTでは、三次元ボクセル配列を持たず、地表パターンは急な断崖絶壁も許容するため、描画対象物は整数型の最小値〜最大値までの高さをとり得る。

右の図のように画面上で手前から奥に向かって地形が下っている場合、最悪マップ領域の端まで検索しなくてはならないことになる。
全ての地表グリッド、全ての構造物に対していちいち可視判定するのは、さすがにパフォーマンスに大きく影響するだろうと思われるため、どこかで切り捨てる必要がある。
そこで、FreeTrain風に地表（海抜０ｍ）上の可視エリア＋若干の高さ分の拡張エリアを描画範囲と決め、その内部のみを描画するものとする。

従って、地形によっては、手前（画面下方）や奥（画面上方）で描画範囲が途切れてしまうこともあり得るが、やむを得ない仕様とする。

描画順序と重なり †

当たり前の話だが、スプライトを描画する際には、奥にあるものから順に描画していかないと、前後関係が上手く描画できない。
一方で、あるスプライトがその上に描画されるスプライトで完全に隠れてしまうなら、後ろのスプライトの描画を省くことでパフォーマンスを向上できる。
しかしながら、その為には手前にあるスプライトから順に描画範囲を計算しなくてはならない。

右の図で斜線部分は本来描画しなくても済む範囲である。
FreeTrainでは基本的に描画範囲に含まれるものは全て、例え手前のスプライトで隠れるものであっても奥にあるものから順に描画していた。
FreeTrainにおいて平地と山がちな地形とでは、描画速度が極端に異なるのもこのためと思われる。

この問題を改善するために、NeoFTでは大きく二段階の手順を踏む。
まず手前のスプライトから順に描画範囲を計算してスタックに積む。このとき、完全に隠れるスプライトは取り除くことができる。
次に、スタックから順に取り出して描画する（奥にあるスプライトから描画することになる）。

描画範囲内での描画順（前後判定） †

前項では奥にあるもの、手前にあるものと簡単に述べたが、実のところそれほど単純な問題ではない。
なぜなら、構造物は複数ボクセルにまたがる「サイズ」を持つことができ、どのように相互の前後関係を評価すればよいのか、が問題になるためである。

評価方法が適切でないと、描画したときに重なり方がおかしくなってしまう。
一例として、1x10x1のような長いのような構造物の横腹に1x1x1の構造物が並ぶようなケースを考えてみていただきたい。

FreeTrainでは、この問題の対策として複数ボクセルにまたがる画像を、ボクセル単位で分割してスプライトの配列として保持して解決しようとしていた（下図）。

しかし、厳密にはボクセル単位とはいえ、クォータービューで見るボクセルの外形である横長の菱形ではなく、その菱形に外接する（画像上の）矩形として分割しているだけであるため、描画がおかしく見えるケースもあった。加えて、外接矩形同士の重なり部分は二重描画されるため、ボクセル単位で無駄に描画される部分が増えることになる。
図の例では、重複部分と省略部分の面積は等価だが、「高さ」を持つ建物などでは重複部分の比率が増える。そうでない場合でも、スプライト描画関数のオーバーヘッドを考えれば、分割描画より一括描画の方が効率面で有利なのは間違いない。
また、スプライトのアニメーションが可能となるよう拡張しようとした場合に、かなり面倒な修正が必要になることが判った。

詳細設計 †

主なクラスと役割（暫定） †

MapViewDrawerクラス

Controlとの連携部分 DirectDrawサーフェスへの描画、 また外部namespaceから利用するためのAPIを備える

TerrainMapImplクラス

地形データを保持

ViewObjectListクラス

地形以外の構造物などの描画対象物リスト
各物体の回転後の３Ｄ座標を元に、描画順序にソートする機能を持つ。

SceneBuilderクラス

描画順序などややこしい計算を考える中枢

CoordinationUtilクラス

座標計算ユーティリティ
回転と拡大を考慮した３Ｄ座標とユーザ視点の３Ｄ座標との相互変換、および画面二次元座標と３Ｄ空間座標との相互変換
このクラス自体は抽象クラス。無駄な条件分岐を避けるため、４方回転毎に個別の実態クラスを定義して使い分ける。

GroundOccupationMapクラス

SceneBuilderが使用
描画対象範囲の判定および、構造物の描画順序を考える際の作業領域

構造物の表示順 †

構造物の配置領域を(x1,y1,z1)-(x2,y2,z2)とし、x1<x2,y1<y2,z1<z2とする。 座標は回転後の３Ｄ空間のものとする。

1. Aのy2がBのy1以下であれば、AはBより手前にある（事実）
2. Aのx2がBのx1以下であれば、AはBより手前にある（事実）
3. Aのy1がBのy2以上であれば、AはBより奥にある（事実）
4. Aのx1がBのx2以上であれば、AはBより奥にある（事実）

上記のいずれでもない場合、領域が交差していると考えられ、 明確な前後関係は決められないため、以下の基準を用いる

1. AとBでz2に違いがあればz2が大きい（背が高い）方を手前とする（仕様）
2. AとBのz2が等しい場合、y1が小さい方を手前とする（仕様）
3. AとBのz2とy1がともに等しい場合、x1が小さい方を手前とする（仕様）
4. 上記いずれでもない場合、後で追加された方が手前となる（仕様）

OccupationMap（占有状況地図）の準備 †

OccupationMapは、マップ平面上でどこに構造物が配置されるかをマークする 手前から順に以下のようにして占有地図にマークする。

1. ViewObjectListを表示順に並び替える
2. リストから手前から奥の順に構造物を取り出す。
   
3. [i]番目の要素の配置領域の(x1,y1)〜(x2-1,y2)にあたる部分を、値=[i-n]で埋める
   （ここで[n]はリストの全要素数） ※かならず負の値であり、手前にあるものほど小さな値で埋められる
4. 再度リストから手前から奥の順に構造物を取り出し、 占有地図上の各構造物の配置領域(x2-1,y1)の値を調べる。
   1. [i]番目の要素(x2-1,y1)の値がゼロ（非占有）なら何もせず次の要素へ
   2. [i]番目の要素(x2-1,y1)の値が正の値[j]なら、[i]番目の要素のNextObjectに[j]番目の構造物を指定
   3. [i]番目の要素(x2-1,y1)の値が非ゼロなら、占有地図上の(x2-1,y1)の値を[i+1]で上書き

マップ上の構造物に対して、占有地図上のマーキングは右図の様になる。
正負の符号の使い分けの意味は、描画順計算で説明する。

構造物と地表の描画順 †

手前にあるものから先にスタックしていき、奥に行くほど後でスタックする （描画時は逆順で取り出され、奥にあるものから描画していく。）

1. 一次走査方向は左上方向（３Ｄ・Ｙ軸正方向）、二次走査方向は右方向（２Ｄ・Ｘ軸正方向）
2. 以下の手順で二次走査の起点となるマップ座標を決定する。
   1. ３Ｄ座標(0,0,0)が描画範囲に含まれるならば、これを起点とする
   2. 描画範囲の２Ｄ左下座標に相当する３Ｄ座標(X',Y',0)がマップ範囲内に存在すれば、これを基点とする
      （※そうでない場合２Ｄ左下はマップ座標外であることを意味する）
   3. 左下３Ｄ座標について(X'>=0 かつ Y'<0)である場合、(X'-Y',0,0)を基点とする
      （Ｙ座標が０になるまで画面上方にシフト）
   4. 左下３Ｄ座標について(X'>=0 かつ Y'>=0)である場合、(X'+Y'-Ymax,Ymax-Y',0)を基点とする
      （Ｙ座標のマップ上端にあたるまで画面右にシフト、ただしY'>Ymaxならマップ外）
   5. 左下３Ｄ座標について(Y'<X'<0)である場合、(X'-min(X',Y'),-min(X',Y'),0)を基点とする
      （マップ下端にあたるまで画面上方にシフト）
   6. 左下３Ｄ座標について(X'<0 かつ Y'>=0)である場合、描画右下３Ｄ座標(X",Y",0)を取得し、以下の手順で基点を決定する
      1. 右下３Ｄ座標について(X"<0)である場合、(0,Y"-X",0)を基点とする（※右下座標基準）
         （マップ端にあたるまで画面右＆上方にシフト）
      2. 右下３Ｄ座標について(X">=0)である場合、(0,Y'-X',0)を基点とする（※左下座標基準）
         （マップ端にあたるまで画面右方にシフト）
3. 一次走査方向にマップを走査し地表・崖のスプライトをスタック
4. 以下の条件になるまで一次走査を続ける
   1. 描画対象範囲外に出る
   2. 占有マップの当該箇所がゼロでない

      構造物などがない場合	占有地図に構造物がマークされている場合

5. 占有マップの正の値[j]によって一次走査が停止した場合、次の処理を行う
   1. ViewObjectListの[j-1]番目の要素のスプライトをスタック
   2. ViewObjectListの[j-1]番目の要素の配置領域(x1,y1,z1)-(x2,y2,z2)を取得
   3. 配置領域の(x1,y1)〜(x2-1,y2)間の各座標を起点として一次方向への走査を行う
6. 一次走査が終了したら、二次走査方向に走査し、次の起点を選択して一次走査を行う ３Ｄ座標(X,Y,*)の次の起点の選択は以下の基準で選ぶ
   1. (X+1,Y-1,*)が描画範囲外（かつマップ範囲外）でなければ次の起点とする
   2. (X+1,Y,*)が描画範囲外（かつマップ範囲外）でなければ次の起点とする
   3. (X+1,Y+1,*)が描画範囲外（かつマップ範囲外）でなければ次の起点とする
   4. 上記いずれにも当てはまらない場合、二次走査は完了とする

---

お名前: