Doomエンジンのソースコード分析：レンダリング

デザイナー画面からプレーヤー画面まで

マップは、レベルデザイナーがDoom Editor（DoomED）を使用して2Dで開発しました。 LINEDEFSはクローズドセクター（ソースコードのSECTORS）を記述し、3次元（高さ）はセクターごとに示されていました。 Doom E1M1の最初のレベルは次のようになります。







マップでの作業が完了したら、バイナリスペースパーティショニング（BSP）メソッドを使用してマップを切り取ります。 LINEDEFが再帰的に選択され、その平面が割線平面になりました。 つまり、凸のサブセクターのみが残るまで（コード内のSSECTOR）、LINEDEFはセグメントに分割されました（SEGS）。



興味深い事実： DoomEDとiBSPは両方とも... NextStepワークステーションのObjective-Cで書かれています。 15年後、ほぼ同じオペレーティングシステムの同じ言語がモバイルデバイスでゲームを実行します！ [約。 Per。：2010年、DoomはiPhoneで登場しました]私はウェブ考古学者として少し働いて、なんとかidbspのソースコードを見つけました。 一見の価値があります 。



以下は、第1レベルのマップの再帰的な分割の例です。



再帰レベル1







選択した壁が割線平面（赤）に変わり、青でマークされます。 切断面は、BSPツリーのバランスを取り、作成されるSEGSの数を制限するように選択されました。 緑色の境界矩形は、後でマップフラグメント全体を破棄するために使用されました。



再帰レベル2（右部分空間のみ）







その結果、SECTORSセクターはコンベックスサブセクター（SSECTORSと表記）に分割され、LINEDEFSはセグメント（SEGSと表記）に分割されました。

全体的な作業プロセス

メインレンダリングメソッド（ R_RenderPlayerView



）は次のようになります。

 void R_RenderPlayerView (player_t* player) { [..] R_RenderBSPNode (numnodes-1); R_DrawPlanes (); R_DrawMasked (); }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ここでは4つの操作が実行されます。

• R_RenderBSPNode
  
  
  
  ：マップ上のすべてのサブセクターは、BSPツリーを使用してソートされます。 大きなフラグメントは、境界の長方形を使用して破棄されます（前の画像では緑色で表示されています）。
• R_RenderBSPNode
  
  
  
  ：可視SEGSセグメントは、ルックアップテーブルを介して画面に投影され、クリッピング配列を使用してトリミングされます。 壁はピクセルの列として描画されます。 列のサイズはプレーヤーの視点からの距離によって決まり、Y列の位置から高さはプレーヤーに接続されます。 壁のベースとトップは、飛行機の平面を作成します。 これらの構造は、床と天井のレンダリングに使用されます（フラットコードで呼び出されます）。
• R_DrawPlanes
  
  
  
  ： R_DrawPlanes
  
  
  
  プレーンは、ピクセルの列からピクセルの行に変換され、画面にレンダリングされます。
• R_DrawMasked
  
  
  
  ：「オブジェクト」（敵、オブジェクト、透明な壁）をR_DrawMasked
  
  
  
  ます。

バイナリスペース分割の並べ替え

E1M1（最初のDoomカード）とBSPの2つの例は次のようになります。

 //        //   ax + by + c = 0  //    = (a,b) //   (    A  B): normal = (-1,0) c = 3500 //  A (  A   A1  A2): normal = (1,0) c = -2500 //  B (  B   B1  B2): normal = (-0.24,0.94) c = -650 //     (x,y)  //        .
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

BSPツリーの走査は常にルートノードから開始され、両方のサブスペースをソートします。 再帰は両方の子ノードに対して実行されます。



例1：プレイヤー（緑色の点）は、ポイントp =（2300,1900）から窓を覗きます：

 //   = ( 2300, 1900 ) // R_RenderBSPNode     AB (-x + 3500 = 0): -2300 + 3500 = 1200  , ,      . (A ,  B). //  R_RenderBSPNode        :   A1/A2  B1/B2. // R_RenderBSPNode   A1/A2 (x - 2500 = 0): 2300 - 2500 = -200  ,        . (A1 ,  A2). // R_RenderBSPNode   B1/B2 (-0.24x +0.97y - 650 = 0): -0.24 * 2300 + 0.97 * 1900- 650 = 641  ,       . (B1 ,  B2). :        : { A1, A2, B1, B2 }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

例2：プレイヤー（緑色の点）は、p =（5040、2400）の秘密のバルコニーから見えます：

 //   = ( 5040, 2400 ) // R_RenderBSPNode     AB (-x + 3500 = 0): -5040 + 3500 = -1540  ,        . (B ,  A). //  R_RenderBSPNode        :   A1/A2  B1/B2. // R_RenderBSPNode   B1/B2 (-0.24x +0.97y - 650 = 0): -0.24 * 5040 + 0.97 * 2400 - 650 = 468  ,       . (B1 ,  B2). // R_RenderBSPNode   A1/A2 (x - 2500 = 0): 5040 - 2500 = 2540  ,       . (A2 ,  A1). :        : { B1, B2, A2, A1 }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

BSPツリーを使用すると、プレーヤーの位置に関係なく、マップ上のどこからでも一定の速度でSEGSをソートできます。 これに対する価格は、各プレーンに対して1つの乗算演算と1つの加算演算です。 さらに、バウンディングボックスによるテストのため、マップの大部分が破棄されます。



注：すぐにはわかりませんが、BSPはプレーヤーの周りのすべてのSEGSセグメントを、たとえ彼が見ていないものであってもソートします。 BSPを使用する場合、可視性のピラミッドに沿ってクリッピングを使用する必要があります。

壁

BSP壁（SEGS）を近くから遠くに並べ替えると、最も近い256の壁のみがレンダリングされます。 各SEGSの2つの頂点は2つの角度に変換されます（プレーヤーの位置を基準にして）。



注： 1993年には、最も強力な486DXマシンにのみFPU（浮動小数点数用のコプロセッサー）が搭載されていたため、Doomエンジンはint



数のみで機能するバイナリ角度測定（BAM）を使用してすべての角度を計算し、 float



形式はほとんど使用されませんでした。 同じ理由で、整数の精度を超える精度は、固定コンマ付きのバイナリ16.16形式であるfixed_t



を使用して達成されました（これについては、 こちらとこちらをご覧ください ）。



角度に変換した後、ルックアップテーブル（ viewangletox



）を使用して、画面空間のX座標を取得しました。 BAMはint



で実行されたため、8 KBのルックアップテーブルに収まるように、右に19ビットのシフトを使用して、最初にコーナーを32ビットから13ビットにスケーリングしました。



次に、クリッピング配列に従って壁をトリミングしました（ solidsegs



。一部の記事では、Doomエンジンのリンクリストについて言及していますが、使用されていないようです）。 トリミング後、残りのスペースは補間され、ピクセル列としてレンダリングされました。ピクセル列の高さとY座標は、それぞれSEGSセクターの高さとプレーヤーの視点からの距離に基づいていました。



クリッピングサーフェスに関する注意：不可視サーフェスのクリッピングは、 angle2-angle1 > 180



を使用して行われました。 スコープ内の壁のみがレンダリングされました。







注：すべての壁が単一のテクスチャで構成されているわけではありません。 壁には、下部のテクスチャ、上部のテクスチャ、および中程度のテクスチャ（透明または半透明）があります。 下のビデオからわかるように、ウィンドウのシミュレーションには便利でした。「ウィンドウ」は、実際には高床で平均的なテクスチャがないセクターです。





興味深い事実：壁は垂直の列としてレンダリングされたため、壁のテクスチャは左に90度回転したメモリに保存されました。 このトリックにより、中央処理装置の事前キャッシュ機能を完全に利用することが可能になりました。RAMからウォールテクセルを読み取るプロセスは、各側に8つの隣接テクセルでCPUキャッシュを事前に設定しました。 後続の読み取りデータは既にRAMキャッシュにあったため、読み取りレイテンシの大幅な削減が達成されました。 メモリ内のデータの事前キャッシュと整列の詳細については、「The Art of Assembly Language programming」（セクション3.2.4キャッシュメモリ）を参照してください。

平らな表面（床と天井）、または悪名高い飛行機

壁の列をレンダリングするとき、画面スペースの上下の座標を使用して、「平面」、画面スペース内のエリア（必ずしも水平に連続している必要はありません）を生成しました。 これは、Doomエンジンでvisplane_tが宣言される方法です。

 // //    visplane? // typedef struct { fixed_t height; int picnum; int lightlevel; int minx; int maxx; byte top[SCREENWIDTH]; byte bottom[SCREENWIDTH]; } visplane_t;
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

構造の最初の部分には、「マテリアル」に関する情報（ height, picnum, lightlevel



）がheight, picnum, lightlevel



ます。 最後の4つのメンバーは、画面スペースのカバレッジエリアを定義します。



2つのサブセクターが同じマテリアル（高さ、テクスチャ、および光レベル）を持っている場合、Doomエンジンはそれらを結合しようとしましたが、visplante_t構造の制限により、これは常に可能ではありませんでした。



画面の幅全体に対して、visplaneはピクセルの列の位置を保存できます（visplaneは壁を画面に投影することで取得されるため、ピクセル列として作成されます）。



以下は、初期画面の3つの基本的な飛行機です。







緑の面は特に興味深いものですvisplane_t



が不連続な（水平方向のみの）領域をvisplane_t



できることを示しています。 列は連続しているため、visplaneはそれを保存できます。 この制限はエンジンに現れます。一部のサブセクターは1つの飛行機を使用してマージおよびレンダリングできますが、それらの間に垂直方向の何かがある場合、マージは不可能です。



以下は、飛行機の断片化を示すスクリーンショットと対応するビデオです。









興味深い事実：厳しく設定された飛行機の制限（ MAXVISPLANES



128）は、ゲームが落ちてDOSに戻ったため、 MAXVISPLANES



にとって大きな頭痛の種でした。 次の2つの問題が発生する可能性があります。

• "R_FindPlane: no more visplanes"
  
  
  
  ：さまざまなマテリアルの飛行機の合計数（高さ、テクスチャ、および光のレベル）が128を超えています。
• R_DrawPlanes: visplane overflow (%i)
  
  
  
  ：飛行機が断片化すると、その数は128を超えました。

なぜ128に制限されるのですか？ レンダリングパイプラインの2つのステージでは、visplanesリストでの検索が必要でした（ R_FindPlane



を使用）。 検索は線形であり、おそらく128を超える数値の場合、コストが高すぎることが判明しました。 Lee Killoughは後に、線形検索をチェーンハッシュテーブルに置き換えることでこの制限を拡張しました。

オブジェクトと透明な壁

すべての固体の壁と「透明な中央のテクスチャ」の壁、および天井と床の表面がレンダリングされた後、「オブジェクト」のみが残ります：敵、樽、弾薬、半透明の壁。 それらは最も遠いものから最も近いものまでレンダリングされますが、壁参照テーブルを使用してスクリーン空間に投影されることはありません。 レンダリングプロセスは、固定のコンマで2進数の16.16を計算することによって実行されます。





注：このビデオは、一部のピクセルを3回再描画する必要がある最悪のシナリオの1つを示しています。

プロファイリング

Mac OS XのインストゥルメントでChocolate Doomをダウンロードすると、プロファイリングを行うことができました。



[iPhoneの]ポートは「バニラ」の運命にほぼ一致しているようです。ほとんどの場合、壁（ R_DrawColumn



）、天井/床（ R_DrawSpan



）、およびオブジェクト（ R_DrawMaskedColumn



）がR_DrawMaskedColumn



ます。 レンダリングに加えて、壁の補間（ R_RenderSegLoop



）および列からピクセルの行への飛行機の変換（ R_RenderSegLoop



）に高いリソースコストがあることに気付きました。 そして最後に、AI（ R_MobjThinker



）にR_MobjThinker



し、BSPツリー（ R_RenderBSPNode



）をバイパスします。







反転したコールツリーを使用すると、ほとんどの作業が実際にBSPツリーの走査、壁のレンダリング、およびvisplaneの生成を伴うことがわかります： R_RenderBSPNode



（2番目の列は費やされた時間の割合です）。

すべて一緒に

そして今、最後に、伝説的な最初の画面を生成するビデオがあり、順番に見ることができます：

• ピクセルの列としての壁、近くから遠くまで
• ピクセル列のような平らな表面、近くから遠くまで
• 遠くから近くまでのアイテム。

興味深い事実

• Doomは線形仮想メモリモデルを備えたNeXTSTEPシステムで開発されたため、id Softwareは当時のほとんどのゲームで使用されていたEMSとXMSを放棄することを決定しました。 代わりに、開発者はDOS / 4Gを使用しました。これは、ソフトウェアがリアルモードオペレーティングシステム（DOS）のプロテクトモードでRAMにアクセスできるようにするメモリエクステンダーです。
• NexTワークステーションは非常に強力であったため、エディター、ゲーム、およびデバッガーを同時に実行できました。 ゲームが十分に安定すると、コードはネットワークを介してPCに送信され、Watcom DOS / x86コンパイラーでコンパイルされました。 DOS / 4Gのおかげで、コードはPCとNeXTの両方で同じメモリモデルで実行されました。
• Masters of Doomの本を補完する興味深いビデオ：
  
  
  
  
  
  
• 多くの詳細は、John Romero（ rome.ro ）およびplanetromero.comのWebサイトで調べることができます。

推奨読書

• 1997年にリリースされた元のソースコードは読みやすいですが、コメントがないか、ほとんどコメントがなく、コンパイルされず、オーディオサブシステムのソースコードがありません（ライセンスの問題のため）。
• チョコレート・ドゥーム ：そうそう！ これは単なるすばらしい移植版であり、SDLに基づいており、ほぼすべてのプラットフォームでbrioを使用してコンパイルできます。 この記事のビデオを生成するためにハッキングしたのはこのポートです。
• マイケル・アブラシュによる本「Graphics Programming Black Book」。 BSPツリーを理解するのに役立ち、インスピレーションの大きな源です。 この男はあなたをアセンブラーに夢中にさせることさえできます。
• Doomのマスター ：Doomの作成に関する詳細が記載されたidソフトウェアストーリー