Doom engine
Doomは、バイナリ空間分割(BSP)と呼ばれるシステムを利用している。ツールを使用して、事前にステージのBSPデータを生成する。このプロセスは大きなステージではかなり時間がかかる場合があるため、Doomでは壁を移動することはできない。ドアとリフトは上下に動くが、どれも横には動かない。
レベルはバイナリツリーに分割される。ツリー内の各位置はステージの特定の領域を表す「ノード」である(ルートノードはステージ全体を表す)。ツリーの各分岐には、ノードの領域を2つのサブノードに分割する分割線がある。同時に、この分割線はlinedefを「seg」と呼ばれるラインセグメントに分割する。
ツリーの葉には凸多角形があり、ステージをさらに分割する必要はない。これらの凸多角形はサブセクター(または「Sセクター」)と呼ばれ、特定のセクターにバインドされる。各サブセクターには、関連するsegのリストがある。
BSPシステムは、サブセクターをレンダリングに適した順序に並べ替える。アルゴリズムはかなり単純である:
ルートノードから開始する。
このノードの子ノードを再帰的に描画する。カメラに最も近い子ノードは、スキャンラインアルゴリズムを使用して最初に描画される。これは、カメラがノードの分割線のどちら側にあるかを見ることで分かる。
サブセクターに達したら、そのサブセクターを描画する。
ピクセルの列全体が満たされる(つまり、これ以上隙間が残らなくなる)と、プロセスは完了する。この順序付けにより、表示されていないオブジェクトの描画に時間を費やすことがなくなり、その結果、速度のペナルティなしにマップを非常に大きくすることができる。