------------------------------------------------------------------------------
 ZSort マイクロコードの 2nd Pass (Drawing) 仕様

						Jul 23, 1997
						開発 3 部  安本 吉孝
------------------------------------------------------------------------------

● 3 角形タイプの考察

  N64 でサポートしている 3 角形の描画機能は, Z Buffer, Smooth Shading,
Texture Mapping である. 

  ここでは 隠面消去処理に ZSort 法を使用するため Z Buffer 計算は使用し
ない.

  Smooth Shading についても Smooth Shading と Texture Mapping が共に 
OFF の場合は応用範囲が狭いこと, Smooth Shading 処理なしで Texture
Mapping 処理のみを行なう場合の処理量が Smooth Shading と Texture
Mapping 処理の両方に行なう場合の処理量とあまり変化は無いこと, また 
Smooth Shading 処理を OFF にした場合, FOG 処理が正常に行なわれなくなる
ことを考え合わせ, Smooth Shading を常に ON にすることにする.

  よって, この場合での有効な描画タイプは以下の 2 通りとなる.

  (a) Smooth Shading...あり, z buffer...なし, Texture Mapping...なし
  (b) Smooth Shading...あり, z buffer...なし, Texture Mapping...あり

  各タイプの 3 角形の描画に必要な頂点データは以下のようになる.


(a) Smooth Shaded Triangle (32 Bytes/Tri)

	V0 ( X0,Y0, R0,G0,B0,A0 )
	V1 ( X1,Y1, R1,G1,B1,A1 )
	V2 ( X2,Y2, R2,G2,B2,A2 )

		+-----------+-----------+
		|    Hdr    |  RDP cmd  |
		+-----+-----+--+--+--+--+
	Vtx 0	|  X  |  Y  |R |G |B |A |
		+-----+-----+--+--+--+--+
	Vtx 1	|  X  |  Y  |R |G |B |A |
		+-----+-----+--+--+--+--+
	Vtx 2	|  X  |  Y  |R |G |B |A |
		+-----+-----+--+--+--+--+

(b) Smooth Shaded Textured Triangle (56+n Bytes/Tri)

	V0 ( X0,Y0, R0,G0,B0,A0, S0,T0, invWi0,invWf0 )
	V1 ( X1,Y1, R1,G1,B1,A1, S1,T1, invWi1,invWf1 )
	V2 ( X2,Y2, R2,G2,B2,A2, S2,T2, invWi2,invWf2 )

		+-----------+-----------+------
		|    Hdr    |  RDP cmd  | ......
		+-----+-----+--+--+--+--+-----+-----+-----+-----+
	Vtx 0	|  X  |  Y  |R |G |B |A |  S  |  T  |invWi|invWf|
		+-----+-----+--+--+--+--+-----+-----+-----+-----+
	Vtx 1	|  X  |  Y  |R |G |B |A |  S  |  T  |invWi|invWf|
		+-----+-----+--+--+--+--+-----+-----+-----+-----+
	Vtx 2	|  X  |  Y  |R |G |B |A |  S  |  T  |invWi|invWf|
		+-----+-----+--+--+--+--+-----+-----+-----+-----+


-----------------------------------------------------------------------------
● 3 角形データの保持形式

  3 角形データを以下の様に保持することを考える.


(a) 3 角形データと頂点データをひとまとめにする(逐次リンク)

	Tri Param に次の 3 角形データへのポインタを持つ.

	+---------+---------+---------+---------+
	|Tri Param|  Vtx 0  |  Vtx 1  |  Vtx 2  |
	+---------+---------+---------+---------+
	  |
	+---------+---------+---------+---------+
	|    :    |    :    |    :    |    :    |
	+---------+---------+---------+---------+
          |
	+---------+---------+---------+---------+
	|    :    |    :    |    :    |    :    |
	+---------+---------+---------+---------+

	最も簡単な形式
	データを途中で追加するのが簡単.
	逆方向への走査が難しいため, バイナリサーチなどが使えない.
	無駄のない DMA ロードのためには Tri Param に次の 3 角形データ
	へのポインタと 3 角形のデータサイズを仕込んでおく必要があるが, 
	これは双方向にリンクを張らないと難しい.
	ただしバイナリサーチに関しては CPU 側で管理ブロックを用意する
	などすることでなんとか出来る面が大きい.


(b) 3 角形データと頂点データをひとまとめにする(管理ブロック)

	3 角形データへのポインタを配列にしておいて, それを参照し
	次の 3 角形データを取得する	

	+-----+	     +---------+---------+---------+---------+
	|Tri 0|----->|Tri Param|  Vtx 0  |  Vtx 1  |  Vtx 2  |
	+-----+	     +---------+---------+---------+---------+
	|Tri 1|----->|Tri Param|  Vtx 0  |  Vtx 1  |  Vtx 2  |
	+-----+	     +---------+---------+---------+---------+
	|Tri 2|----->|Tri Param|  Vtx 0  |  Vtx 1  |  Vtx 2  |
	+-----+      +---------+---------+---------+---------+

	前後の 3 角形の走査が簡単.
	バイナリサーチが簡単にできる.
	データのマージは難しい.
	Tri n データに 3 角形のデータサイズを仕込むことで適度な大きさの
	DMA 転送処理を行なうことが可能.


(c) 3 角形データと頂点データを別にする場合

	+---------+          +---------+
	|Tri Param|-----+--->|  Vtx 0  |
	+---------+     |    +---------+
	|    :    |     +--->|  Vtx 1  |
	+---------+     |    +---------+
	|    :    |     +--->|  Vtx 2  |
	+---------+          +---------+
	|    :    |          |    :    |
	+---------+          +---------+

	DMA 回数がやたら増える.
	共有する頂点データを使い回せるので RAM 使用量が減る.


DMA 回数        		c > b > a
RAM 使用量   			b > a > c
Sort し難さ			b = c < a
RunTime での無駄な DMA 転送量	b = c <= a

---
仕組みが簡単なので (a) での実装を行なう.

          +-----------+-----------+
Tri Param |    Hdr    |  RDP cmd  |
          +-----------+-----------+

	  Tri Param はこの時点で物理アドレスに変換しておく.
	このため Hdr/RDP cmd の上位 8 bit は 0 となる.
	また DMA アライメントより下位 3 bit も 0 となる.

	    31     24 23                             3 2  0
	    +--------+--------------------------------+---+
	Hdr |00000000|                                |000|
	    +--------+--------------------------------+---+

	    31     24 23                             3 2  0
	RDP +--------+--------------------------------+---+
	cmd |00000000|                                |000|
	    +--------+--------------------------------+---+

	  3 角形の描画ごとにテクスチャをロードしたりその他のパラメータ
	を設定するわけにもいかないため, RDPcmd の値をチェックすること
	によって, 前回の 3 角形の描画における設定値と今回の描画の設定
	値が同じなら, 今回の設定を省くことが可能となる. 

	  このため実際は 32-8-3=21bits 分のデータとなる.
	Tri Param は 64bits あるから 3 つ分のポインタを保持することが
	できる. これを応用して, Hdr + RDPcmd1 + RDPcmd2 という構成を取
	ることが可能である. 

	  RDPcmd を 2 つ定義できるのは CI テクスチャ処理に有効である.
	一方でテクスチャの設定を行ない, もう一方でパレットの設定(変更)
	を行なうことができるのである.

	  3 つポインタで 63bit 使用した場合, 残りの 1bit に 3 角形の描
	画タイプデータを保持することになる. この場合の終端コードをどう
	するか, また, Texture Rectangle による描画を混ぜる場合はどうす
	るかを解決する必要がある. この解決には場当たり的な処理を行なわ
	ねばならない.

	  また実際の処理において, この RDPcmd を 2 つ使用することでど
	の程度のゲインを得ることが出来るかは未知数である. 
	実際 RDPcmd で時間がかかる処理は, テクスチャおよび TLUT の 
	Load 処理である. 他のパレットの切り替え処理はそれほどコストが
	かかる処理ではない. よって, Load 系のコマンドの発行を減らすた
	めにこの 2 つの RDPcmd が有効であるかどうかを吟味する必要があ
	る.
	
	  考えられるのは, テクスチャと TLUT のロードを分割することであ
	る. この場合有効であろう. BG 面においてそれほど色数を使用しな
	いことはあり, BG 全部で 256 色で収まることが良くあるからである. 
	(Super Donkey Kong からの類推)

	  ただし, Hdr を CPU 側で設定させるために, 複雑な bit フォーマッ
	トを使うことは望ましくないので, なるべく 32bit 幅を使用したい.
	この前提の元に RDPcmd を複数用意するためには, Tri Param のサイ
	ズを 64bits より大きくする必要がある. DMA の 8 bytes のアライ
	ンを考えると, テクスチャありの 3 角形の描画において, データサ
	イズを 8 bytes 増やす必要がある. この場合, RDPcmd を 3 つまで
	設定できる.

	  ここで, 常に RDPcmd が 3 つ必要ではないので, 1 か 3 かを選択
	できるようにするかどうかを考える.
	
	  テクスチャなしの場合, グローバル RDP status を変更するだけで
	良いため, RDPcmd は 1 つで十分である. テクスチャありの場合, グ
	ローバル RDP status と Texture のロード処理, および TLUT のロー
	ド処理と 3 つ分の RDPcmd があれば, かなりの処理をカバーできる.
	
	  RDPcmd が 1 か 3 かのフラグのパース処理のオーバーヘッドを考
	えると, テクスチャなしのときは 1, テクスチャありのときは 3 と
	固定したほうか実装が楽になり, また固定にしてもそれほど不都合が
	起こるとは考えにくいため, 固定にする方が有利である.


(a) Head/Texture Rectangle (16 Bytes/Obj)

		+-----------+-----------+-----------+-----------+
		|    Hdr    | RDP cmd 1 | RDP cmd 2 | RDP cmd 3 |
		+-----------+-----------+-----------+-----------+
	
	初期設定, 画面のクリア, TextureRectangle 等の描画に使用する.
	RDPcmd のみでの描画を行なう.


(b) Smooth Shaded Triangle (32 Bytes/Tri)

	V0 ( X0,Y0, R0,G0,B0,A0 )
	V1 ( X1,Y1, R1,G1,B1,A1 )
	V2 ( X2,Y2, R2,G2,B2,A2 )

		+-----------+-----------+
		|    Hdr    | RDP cmd 1 |
		+-----+-----+--+--+--+--+
	Vtx 0	|  X  |  Y  |R |G |B |A |
		+-----+-----+--+--+--+--+
	Vtx 1	|  X  |  Y  |R |G |B |A |
		+-----+-----+--+--+--+--+
	Vtx 2	|  X  |  Y  |R |G |B |A |
		+-----+-----+--+--+--+--+


(c) Smooth Shaded Textured Triangle (64 Bytes/Tri)

	V0 ( X0,Y0, R0,G0,B0,A0, S0,T0, invWi0,invWf0 )
	V1 ( X1,Y1, R1,G1,B1,A1, S1,T1, invWi1,invWf1 )
	V2 ( X2,Y2, R2,G2,B2,A2, S2,T2, invWi2,invWf2 )

		+-----------+-----------+-----------+-----------+
		|    Hdr    | RDP cmd 1 | RDP cmd 2 | RDP cmd 3 |
		+-----+-----+--+--+--+--+-----+-----+-----+-----+
	Vtx 0	|  X  |  Y  |R |G |B |A |  S  |  T  |invWi|invWf|
		+-----+-----+--+--+--+--+-----+-----+-----+-----+
	Vtx 1	|  X  |  Y  |R |G |B |A |  S  |  T  |invWi|invWf|
		+-----+-----+--+--+--+--+-----+-----+-----+-----+
	Vtx 2	|  X  |  Y  |R |G |B |A |  S  |  T  |invWi|invWf|
		+-----+-----+--+--+--+--+-----+-----+-----+-----+


-----------------------------------------------------------------------------
● 使用するメモリ量に関する考察.

	  上記の仕様では 1つの 3 角形について 32/64 Bytes のエリアを必
	要とするが, これはメモリの使用効率から考えるとあまり良くない.
	  通常 3 角形を使用するのと同じくらいに 4 角形を使用する場面は
	多いので, 4 角形の描画をサポートすることでメモリの消費量を軽減
	させることを考える.

	  (b),(c) にそれぞれ 1 頂点分のデータを追加することで, 4 角形
	データとする. このとき Vtx 0-1-2 と Vtx 1-2-3 からなる 3 角形
	2 個を描画する.

	  動的分割処理は RSP ではサポートしないので, 必要ならば CPU 側
	で処理する.
	
(d) Smooth Shaded Quadrangle (40 Bytes/Quad)

	V0 ( X0,Y0, R0,G0,B0,A0 )
	V1 ( X1,Y1, R1,G1,B1,A1 )
	V2 ( X2,Y2, R2,G2,B2,A2 )
	V3 ( X3,Y3, R3,G3,B3,A3 )

		+-----------+-----------+
		|    Hdr    | RDP cmd 1 |
		+-----+-----+--+--+--+--+
	Vtx 0	|  X  |  Y  |R |G |B |A |
		+-----+-----+--+--+--+--+
	Vtx 1	|  X  |  Y  |R |G |B |A |
		+-----+-----+--+--+--+--+
	Vtx 2	|  X  |  Y  |R |G |B |A |
		+-----+-----+--+--+--+--+
	Vtx 3	|  X  |  Y  |R |G |B |A |
		+-----+-----+--+--+--+--+


(e) Smooth Shaded Textured Quadrangle (80 Bytes/Quad)

	V0 ( X0,Y0, R0,G0,B0,A0, S0,T0, invWi0,invWf0 )
	V1 ( X1,Y1, R1,G1,B1,A1, S1,T1, invWi1,invWf1 )
	V2 ( X2,Y2, R2,G2,B2,A2, S2,T2, invWi2,invWf2 )
	V3 ( X3,Y3, R3,G3,B3,A3, S3,T3, invWi3,invWf3 )

		+-----------+-----------+-----------+-----------+
		|    Hdr    | RDP cmd 1 | RDP cmd 2 | RDP cmd 3 |
		+-----+-----+--+--+--+--+-----+-----+-----+-----+
	Vtx 0	|  X  |  Y  |R |G |B |A |  S  |  T  |invWi|invWf|
		+-----+-----+--+--+--+--+-----+-----+-----+-----+
	Vtx 1	|  X  |  Y  |R |G |B |A |  S  |  T  |invWi|invWf|
		+-----+-----+--+--+--+--+-----+-----+-----+-----+
	Vtx 2	|  X  |  Y  |R |G |B |A |  S  |  T  |invWi|invWf|
		+-----+-----+--+--+--+--+-----+-----+-----+-----+
	Vtx 3	|  X  |  Y  |R |G |B |A |  S  |  T  |invWi|invWf|
		+-----+-----+--+--+--+--+-----+-----+-----+-----+
	

-----------------------------------------------------------------------------
● ZObject Type ID

     Hdr のどこかに (a)〜(e) を区別するための Type を設定する必要があ
   る. この Hdr は DMA エンジンのレジスタに代入される. このレジスタは,
   [23:0] が有効であるため, Type は [31:24] に代入するべきであるが,
   CPUでこの Hdr の設定を行なう場合, [31:24] の値にデータを代入するた
   めには 3 命令以上必要とするのに対し, [2:0] の場合は 1 命令で済む.
     逆に RSP がこれをデコードするには, [31:24] のときは 1 命令, [2:0] 
   のときは 2 命令かかる. これを比較し CPU のコストを重視するという意
   味から, [2:0] を使用することにする.

	    31     24 23                             3 2   0
	    +--------+--------------------------------+----+
	Hdr |  Seg   |         Next Primitive         |Type|
	    +--------+--------------------------------+----+

	Type[2:0]	次のプリミティブの Type
			000 = (a)Head/Texture Rect.
			001 = (b)テクスチャなし 3 角形
			010 = (c)テクスチャあり 3 角形
			011 = (d)テクスチャなし 4 角形
			100 = (e)テクスチャあり 4 角形
	Seg		セグメント番号
	NextPrimitive	次のプリミティブへのポインタ(物理アドレス)
			= 0 なら終端


-----------------------------------------------------------------------------
● 処理アルゴリズム

   ZObject の処理手順は以下のような流れとなる. (RDPcmd が 3 つある場合)

	------------------------------------------------
	while( !isYield ) {
	  if (RDPcmd1 != array_RDPcmd[1]){
	    appendGfx(RDPcmd1);
	    array_RDPcmd[1] = RDPcmd1;
	  }
	  if (RDPcmd2 != array_RDPcmd[2]){
	    appendGfx(RDPcmd2);
	    array_RDPcmd[2] = RDPcmd2;
	  }
	  if (RDPcmd3 && RDPcmd3 != array_RDPcmd[3]){
	    appendGfx(RDPcmd3);
	    array_RDPcmd[3] = RDPcmd3;
	  }
	  if (NextPrim) LoadNextPrim(NextPrim, inp);
	  if (type != Header){
	    SetupTriangle;
	  }
	  if (NextPrim == 0) break;
	}
	------------------------------------------------


-----------------------------------------------------------------------------