Quake Engine code review : Rendition (4/4)の和訳をしてみる

#Quake Engine code review : Rendition (4/4)

Quakeレンダラは、最初の開発中に最も多くの作業をしたモジュールです。 これは、Michael Abrashの本とJohn Carmackの.planファイルによって広範囲に記述されています。

[Architecture section](http://qiita.com/UnagiHuman/items/cf30a55bbb6b604fdb94)
[Network section](http://qiita.com/UnagiHuman/items/2806ac5f2e51c6a5b3be)
[Prediction section](http://qiita.com/UnagiHuman/items/5ef6d1eb7c8672779561) 
Rendition section (本記事)

#Rendition

シーンのレンダリングプロセスはマップのBSPを中心に行われていきます。 Wikipediaの[バイナリ空間分割](https://ja.wikipedia.org/wiki/%E3%83%90%E3%82%A4%E3%83%8A%E3%83%AA%E7%A9%BA%E9%96%93%E5%88%86%E5%89%B2)を紹介しておきます。 一言で言えば、Quakeマップはすごく前処理されています。 ボリュームは次の図のように再帰的にスライスされます。

![image.png](https://qiita-image-store.s3.amazonaws.com/0/116884/e51f6612-832c-a3e7-43cc-f95450586d0e.png)

このプロセスでは、葉のようなBSPが生成されます（ルールは、既存のポリゴンを分割プランとして選択し、より少ないポリゴンを分割するスプリッタを選択することです）。 BSPが生成された後、各リーフについて、PVS（Potentially Visible Set）が計算される。 例として、leaf4は潜在的にleaf7と9を見ることができます：

![image.png](https://qiita-image-store.s3.amazonaws.com/0/116884/3add971e-1bc6-332e-30fb-f3a83328d3ad.png)

このリーフの結果として得られるPVSは、ビットベクトルとして格納されます。

| Leaf Id| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11| 12| 13| 14|  15| 16|
|:-------|--:|--:|--:|--:|--:|--:|--:|--:|--:|--:|--:|--:|--:|--:|--:|--:|
| PVS for leaf 4| 0| 0 |0 |1 |0 |0 |1 |0 |1 |0 |0 |0 |0 |0 |0 |0 |

これにより、1996年のPCではグローバルなPVSサイズが約5Mbになりました。したがって、PVSはデルタ長圧縮によって圧縮されます。

|Compressed PVS for leaf 4|	3|	2|	1|	7|
|:-------|--:|--:|--:|--:|

The Run-length encoded PVSは、1の間の0の数のみを含む。 非常に効率的な圧縮技術のようには見えないかもしれませんが、非常に限られた目に見えるleafと組み合わせた高いleaf数（32767）は、PVS全体のサイズを20kBに下げます。

#Pre-processing in action
あらかじめ計算されたBPSとPVSが装備されているため、エンジンのMap作成ルーチンは単純に次のようになりました。

1. カメラがどのLeafに位置しているかを判断するには、BSPをトラバースします。
2. このLeafのPVSを取得して解凍し、PVSを繰り返し、BSPにLeafをマークします。
3. BSPを遠くに横切る
4. ノードがマークされていない場合は、それをスキップします。
5. Camera Frustrumに対してNode Boundary Boxをテストします。
6. 現在のLeafをrendition listに追加する

注：BSPは複数回使用されます。例：アクティブなライトごとにマップを遠くに歩き、マップのポリゴンにタグを付けます。
注2：ソフトウェア演出では、BSPは遠くまで歩いている。

#Code analysis
The rendition codeは以下のように要約できます：

```
SCR_UpdateScreen 											
{
		GL_BeginRendering
		SCR_SetUpToDrawConsole
		V_RenderView
		|		R_Clear
		|		R_RenderScene
		|		|		R_SetupFrame
		|		|				Mod_PointInLeaf
		|		|		R_SetFrustum
		|		|		R_SetupGL
		|		|		R_MarkLeaves
		|		|		|		Mod_LeafPVS
		|		|		|				Mod_DecompressVis
		|		|		R_DrawWorld
		|		|		|		R_RecursiveWorldNode
		|		|		|		DrawTextureChains
		|		|		|		|		R_RenderBrushPoly
		|		|		|		|			DrawGLPoly
		|		|		|		R_BlendLightmaps
		|		|		S_ExtraUpdate
		|		|		R_DrawEntitiesOnList
		|		|		GL_DisableMultitexture
		|		|		R_RenderDlights
		|		|		R_DrawParticles
		|		R_DrawViewModel
		|			R_DrawAliasModel
		|		R_DrawWaterSurfaces
		|		R_PolyBlend
		GL_Set2D
		SCR_TileClear
		V_UpdatePalette
		GL_EndRendering
}
```
##SCR_UpdateScreen
Calls：
1. GL_BeginRendering（後でR_SetupGLで使用される変数（glx、gly、glwidth、glheight）を設定してviewPortと投影行列を設定する）
2. SCR_SetUpToDrawConsole（コンソールの高さを決める：これはなぜ2Dの部分ではないのですか？）
3. V_RenderView（レンダー3Dシーン）
4. GL_Set2D（オルソ投影（2D）に切り替える）
5. SCR_TileClear
6. オプションで2Dのもの、コンソール、FPSメトリックなどをたくさん描画します。
7. V_UpdatePalette（名前はソフトウェアレンダラーに合わせています。これは、OpenGLの場合、受信したダメージやアクティブボーナスなどに応じてブレンディングモードを設定します。 値はv_blendに格納されます。
8. GL_EndRendering（バッファをスワップ（ダブルバッファリング）!!）

##V_RenderView
Calls:
1. V_CalcRefdef（申し訳ありませんが何なのかわかりませんでした）
2. R_PushDlights効果があるすべてのライトがあるポリゴンにマークを付けます（注意を参照）
3. R_RenderView


注意：

R_PushDlightsは再帰的メソッド（R_MarkLights）を呼び出します。 BSPはライトの影響を受けるポリゴンを（intビットベクトルを使用して）マークするためにBSPを使用し、BSPは遠くまで（ライトのPOVから）動作しています。 このメソッドは、ライトがアクティブで、範囲内にあるかどうかをチェックします。 R_MarkLightsメソッドは、マイケル・アブラシュがdirect application of distance point-planの記事"Frames of Reference"（dist = DotProduct（light-> origin、splitplane-> normal） - splitplane-> dist;）を直接適用しているので、特に注目に値する。

##R_RenderView
Calls:

1. R_Clear（必要なものだけをクリアするGL_COLOR_BUFFER_BITやGL_DEPTH_BUFFER_BIT）
2. R_RenderScene
3. R_DrawViewModel（レンダリングプレーヤーモデルはspectatorモードです）
4. R_DrawWaterSurfaces（水を描画するにはGL_BEND / GL_MODULATEモードに切り替え、ワーピングはgl_warp.cのsinとcosのルックアップテーブルで行います）
5. R_PolyBlend（V_UpdatePaletteに設定された値をv_blend経由で画面全体にブレンドします。これは、ダメージ（赤色）、水中またはボーナスブースト効果のときに表示されます）

##R_RenderScene
Calls:

1. R_SetupFrame（カメラがあるBSPリーフを取得し、変数 "r_viewleaf"に格納）
2. R_SetFrustum（mplane_t frustum [4]を設定します。
3. R_SetupGL（GL_PROJECTION、GL_MODELVIEWの設定、ビューポートとglCullFace側、Y軸とZ軸をQuake z軸として回転させ、x軸をOpenGLで切り替える）
4. R_MarkLeaves
5. R_DrawWorld
6. S_ExtraUpdate（マウスの位置をリセットし、サウンドの問題を処理する）
7. R_DrawEntitiesOnList（自己説明）
8. GL_DisableMultitexture（Idem）
9. R_RenderDlights（ライトバブル、ライトエフェクト）
10. R_DrawParticles（爆発、火、静的など）

##R_SetupFrame

次の行に注目してください。
r_viewleaf = Mod_PointInLeaf（r_origin、cl.worldmodel）;
これは、Quakeエンジンがカメラが現在BSPに配置されているleaf/ノードを取得する場所です。

Mod_PointInLeafはmodel.cにあり、BSPを実行します（BSPルートはmodel-> nodesにあります）。

###すべてのノードについて

1. ノードがスペースをさらに分割していない場合は、leafであり、したがって現在のノード位置として返されます。
2. そうでなければ、BSP分割平面が現在の位置に対してテストされ（単純なドットプロダクトを介してBSPツリーが訪問される通常の方法です）、一致する子が訪問されます。

##R_MarkLeaves
BSP（R_SetupFrameで取得）、Lookup（Mod_LeafPVS）、およびPotential Visible Set（PVS。）の解凍（Mod_DecompressVis）でカメラ位置を保持する変数r_viewleaf
次に、ビットベクトルを反復し、BSPのPotentialy可視ノードに：node-> visframe = r_visframecountをマークします。

##R_DrawWorld
Calls:
1. R_RecursiveWorldNode（BSPの世界を先頭に戻し、先にマークされていないノード（R_MarkLeaves経由）をスキップし、cl.worldmodel-> textures [] - > texturechainリストに適切なポリゴンを設定します）。
2. DrawTextureChains（テクスチャチェーンに格納されたポリゴンのリストを描画する：cl.worldmodel-> textures []を繰り返します。この方法では、1つのマテリアルにつき1つのスイッチしかありません。
3. R_BlendLightmaps（フレームバッファ内のライトマップをブレンドするために使用される2番目のパス）

注意：

この部分は、おそらく "アートの始まり"と考えられていた時点で、OpenGLの悪名高い "即時モード"を使用します。

R_RecursiveWorldNodeは、サーフェスカリングのほとんどが実行されている場所です。 次の場合、ノードは破棄されます。

1. 内容はSolidです。
2. LeafはPVS（ノード - > visframe！= r_visframecount）でマークされていませんでした。
3. leafはfrustrumクリッピングに失敗します。

#MDL format
MDLフォーマットは固定フレームのセットです。Quakeエンジンは頂点の位置を補間してアニメーションを滑らかにしません（フレームレートを上げてもアニメーションが良く見えるわけではありません）。

#Some elegant things 
エレガントなリーフマーキング

レンダリングされるBSPのリーフをマークする単純なアプローチは、boolean isMarkedVisibleを各フレームの前に使用することです。

1. booleanをすべてfalseに設定します。
2. PVSを繰り返し、可視のleafをtrueに設定します。
3. その後、if（leave.isMarkedVisible）を指定してテストを終了します。

この代わりに、Quakeエンジンはフレームレンダリングされた（r_visframecount変数）の数をカウントするために整数を使用します。 これにより、ステップ1を完全にスキップすることができます。

1. PVSを繰り返し、目に見えるleafを設定します。leafframe = r_visframecount
2. その後、if（leaf.visframe == r_visframecount）を指定してテストを終了します。

再帰回避

BSPを捜査し、現在の位置を取得するために、素早くダーティな再帰を行うのではなく、R_SetupFrameにあります：whileループが使用されています。

```
node = model->nodes;

	while (1)

	{

		if (node->contents < 0)

			return (mleaf_t *)node;

		plane = node->plane;

		d = DotProduct (p,plane->normal) - plane->dist;

		if (d > 0)

			node = node->children[0];

		else

			node = node->children[1];

	}
```

###Minimize texture switchs
OpenGLでは、（glBindTexture（GL_TEXTURE_2D、id））経由のテクスチャのスイッチが非常にコストがかかります。 スイッチ番号を最小にするために、rendition用にマークされたすべてのポリゴンは、ポリゴンのテクスチャマテリアルにインデックスされた配列チェーンに格納されます。

cl.worldmodel->テクスチャ[textureId] - >テクスチャチェーン[]

カリングが行われると、テクスチャチェーンが順番に描画されます。このようにN個のテクスチャスイッチがあり、Nはテクスチャの総数です。

```
int i;
for ( i = 0; i < cl.worldmodel->textures_num ; i ++)
      DrawTextureChains(i);
```