6. ビューイングパイプラインと描画パイプライン

第5章では、モデリング変換、ビュー変換、投影変換という部品を1つずつ作りました。
此の章では其れらを1本のベルトコンベアに並べ、1つの頂点をモデルファイルからピクセル（画素）まで、全ての停留所で実際の数値を使って運びます。
其の後、画面に収まらない物がどうなるか（クリッピングとカリング）、GPUが1フレームを描く為に通る段階、そして線分・円・多角形をピクセルに変える古典的なアルゴリズムを見ていきます。

何故此れが大事なのでしょうか？
スマホのゲームからCADのビューアーまで、全てのリアルタイムレンダラーは正に此のパイプラインを中心に作られています。
何かがおかしくなった時（三角形が消える、絵が上下逆になる、2つの三角形の境目がちらつく）、どの段階が何をしているかを知っていなければ原因を見つける事が出来ません。
検定対策としては、此の章は分野2の2つのシラバス項目、ビューイングパイプラインと描画パイプラインを扱い、クリッピング、カリング、ラスタライズも含みます。

6.1 2つのパイプライン

パイプラインとは、或る段階の出力が次の段階の入力になる、組み立てラインの様な段階の列です。
CGでは2つのパイプラインが出てきますが、其れらは同じ処理を2つの角度から見た物です：

パイプライン	答える問い	主な内容
ビューイングパイプライン	点はどの座標系を通って画面に届くか？	モデリング変換・ビュー変換・投影変換、クリッピング、透視除算、ビューポート変換
描画パイプライン	三角形を完成した画像にする為に、ハードウェアはどんな仕事をするか？	頂点処理、プリミティブアセンブリ、クリッピング、ラスタライズ、フラグメント処理、テスト、フレームバッファ

ビューイングパイプラインは数学、つまり座標変換の列です。
描画パイプラインは其れを実行する機械であり、更に幾何の後に来る全ての事、つまり三角形がどのピクセルを覆い、其のピクセルが何色になるかを決める事も含みます。
描画パイプラインの前半（ジオメトリ処理）が正にビューイングパイプラインなので、其処から始めましょう。

6.2 ビューイングパイプラインを1頂点ずつ

次の図が全体の流れです。
箱は座標系、矢印は操作で、右側の数値は此れから追いかける1つの頂点の物です。

モデリング座標系からスクリーン座標系までのビューイングパイプラインと、各座標系での1つの頂点の座標

此れらの空間の殆どは線型代数の第11章で出てきましたし、投影行列は線型代数の第12章で導出しました。
此処ではもう一度導出はしません。
此の節の主題は、各停留所の順番と意味です：

モデリング座標系（ローカル座標系）、ワールド座標系、カメラ座標系（視点座標系）：第5章の通り、モデル自身の空間、シーン共通の空間、そして視点が原点で−Z方向を見る空間です。
クリップ座標系：投影直後の4次元の同次座標で、まだ何も割っていません。
正規化デバイス座標系（NDC）：wで割った後の座標で、見える物は全て決まった立方体に収まります。
スクリーン座標系（デバイス座標系）：実際のウィンドウのピクセルです。

其の間の操作は、モデリング変換、ビュー変換（視野変換）、投影変換、クリッピング、透視除算、そしてビューポート変換です。

設定

モデルは角が±1にある立方体で、其の角 $\mathbf{p}_{\text{obj}} = (1, 1, 1)$ を追いかけます。
シーンの設定は次の通りです：

モデリング変換：立方体をY軸周りに90°回し、其の後 $(1, 1, -1)$ に移動します。 $\mathbf{M} = \mathbf{T}(1, 1, -1)\,\mathbf{R}_y(90\degree)$ です。
カメラ：視点 $\mathbf{e} = (-2, 1, 0)$ 、注視点 $(1, 1, -4)$ 、上方向 $(0, 1, 0)$ です。
投影：透視投影（OpenGLの規約）、縦の視野角90°、アスペクト比4/3、前方クリップ面 $n = 1$ 、後方クリップ面 $f = 11$ です。
ウィンドウ：800×600ピクセルです。

段階1：モデリング変換（モデリング座標系 → ワールド座標系）

$\cos 90\degree = 0$ 、 $\sin 90\degree = 1$ なので、 $\mathbf{R}_y(90\degree)$ は $(x, y, z)$ を $(z, y, -x)$ に移します：

\mathbf{R}_y(90\degree)\,(1, 1, 1) = (1, 1, -1)

次に平行移動で $(1, 1, -1)$ を足します：

\mathbf{p}_{\text{world}} = (1 + 1,\; 1 + 1,\; -1 - 1) = (2, 2, -2)

段階2：ビュー変換（ワールド座標系 → カメラ座標系）

第5章のlookAtの作り方でカメラの軸が求まります。
前方向は注視点から視点を引いた $(3, 0, -4)$ で、長さは5なので、 $\mathbf{f} = (0.6, 0, -0.8)$ です。
右方向は $\mathbf{f} \times \mathbf{up}$ を正規化した $\mathbf{r} = (0.8, 0, 0.6)$ 、本当の上方向は $\mathbf{u} = \mathbf{r} \times \mathbf{f} = (0, 1, 0)$ です。
点のカメラ座標は、視点から見て「どれだけ右か、どれだけ上か、どれだけ後ろか」で、此れは $\mathbf{p} - \mathbf{e} = (2, 2, -2) - (-2, 1, 0) = (4, 1, -2)$ との3つの内積です：

x_c = \mathbf{r} \cdot (4, 1, -2) = 3.2 + 0 - 1.2 = 2

y_c = \mathbf{u} \cdot (4, 1, -2) = 1

z_c = -\mathbf{f} \cdot (4, 1, -2) = -(2.4 + 0 + 1.6) = -4

従って $\mathbf{p}_{\text{cam}} = (2, 1, -4)$ です。
カメラから見て右に2、上に1、前に4です（前はzが負の向きです）。

段階3：投影変換（カメラ座標系 → クリップ座標系）

$c = 1/\tan 45\degree = 1$ 、アスペクト比 $a = 4/3$ なので、線型代数の第12章のOpenGLの透視投影行列の要素は $c/a = 0.75$ 、 $c = 1$ 、 $-\frac{f+n}{f-n} = -\frac{12}{10} = -1.2$ 、 $-\frac{2fn}{f-n} = -\frac{22}{10} = -2.2$ です：

\mathbf{P} = \begin{bmatrix} 0.75 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & -1.2 & -2.2 \\ 0 & 0 & -1 & 0 \end{bmatrix}

x = 0.75 \cdot 2 = 1.5, \quad y = 1 \cdot 1 = 1, \quad z = -1.2 \cdot (-4) - 2.2 = 2.6, \quad w = -(-4) = 4

\mathbf{p}_{\text{clip}} = (1.5, 1, 2.6, 4)

wがカメラの前方への距離になっている事に注目して下さい。
まだ何も割っていません。
其れこそがクリップ座標の要点です。

段階4：クリッピング

クリップ座標での視体積は、単に次の範囲です：

-w \le x \le w, \qquad -w \le y \le w, \qquad -w \le z \le w

此の点では1.5、1、2.6が全て−4と4の間にあるので、内側にあり、生き残ります。
（範囲外の物がどうなるかは6.3節の主題です。）

段階5：透視除算（クリップ座標系 → NDC）

x、y、zをwで割ります：

\mathbf{p}_{\text{ndc}} = \left(\frac{1.5}{4}, \frac{1}{4}, \frac{2.6}{4}\right) = (0.375, 0.25, 0.65)

OpenGLのNDCでは、見える物は全て3軸とも−1から1の立方体に収まり、yは上向きです。
此の点は中心より少し右、少し上で、かなり奥にあります。

段階6：ビューポート変換（NDC → スクリーン座標系）

ビューポートとは、ウィンドウの中で描画する長方形の事です。
位置 $(x_0, y_0)$ 、大きさ $W \times H$ のビューポートで、画像ファイルの様にピクセルの行を上から数える場合は次の様になります：

x_s = x_0 + \frac{x_{\text{ndc}} + 1}{2}\,W, \qquad y_s = y_0 + \frac{1 - y_{\text{ndc}}}{2}\,H

此れは第4章の2次元のウィンドウ・ビューポート変換で、ウィンドウを−1から1の正方形に固定し、y軸を反転した物です。
$x_0 = y_0 = 0$ 、 $W = 800$ 、 $H = 600$ とすると：

x_s = \frac{1.375}{2} \cdot 800 = 550, \qquad y_s = \frac{0.75}{2} \cdot 600 = 225

深度は−1〜1から深度バッファの0〜1に移ります： $\frac{0.65 + 1}{2} = 0.825$ です。
従って、此の角はピクセル $(550, 225)$ 、深度0.825に着地します。

2つ補足します。
OpenGL自身のウィンドウ座標は原点が左下でyが上向きなので、OpenGLは此の点を $y = \frac{1.25}{2} \cdot 600 = 375$ と呼びます。
同じピクセルを反対側の端から数えているだけです。
又、Vulkanの規約（NDCのyは下向き、zは0〜1）では投影行列が少し違い、 $\mathbf{p}_{\text{clip}} = (1.5, -1, 3.3, 4)$ 、NDCは $(0.375, -0.25, 0.825)$ になります。
同じピクセルで、嬉しい事に深度バッファの値も全く同じ0.825です。

実際には

実際のプログラムでは、段階1〜3を頂点シェーダーが計算し（普通は1つの積 $\mathbf{P}\mathbf{V}\mathbf{M}$ を右から左に適用します）、クリップ座標を出力します。
段階4〜6は頂点シェーダーの後で固定のハードウェアが行うので、wでの除算を自分で書く事はありません。
線型代数シリーズのヘッダーlinalg.hhを使って、CPUで全行程を辿ってみます。
手計算の確認に便利です：

#include <cstdio>
#include "linalg.hh"

int main() {
  const float pi = 3.14159265f;
  Mat4 model = translate({1, 1, -1}) * rotateY(pi / 2);
  Mat4 view = lookAt({-2, 1, 0}, {1, 1, -4}, {0, 1, 0});
  Mat4 proj = perspectiveGl(pi / 2, 4.0f / 3.0f, 1.0f, 11.0f);
  const float width = 800, height = 600;

  Vec4 object{1, 1, 1, 1};
  Vec4 world = model * object;
  Vec4 camera = view * world;
  Vec4 clip = proj * camera;
  printf("world  (%g, %g, %g)\n", world.x, world.y, world.z);
  printf("camera (%g, %g, %g)\n", camera.x, camera.y, camera.z);
  printf("clip   (%g, %g, %g, %g)\n", clip.x, clip.y, clip.z, clip.w);

  // clipping test: inside the view volume when -w <= x, y, z <= w
  bool inside = -clip.w <= clip.x && clip.x <= clip.w && -clip.w <= clip.y && clip.y <= clip.w &&
                -clip.w <= clip.z && clip.z <= clip.w;
  printf("inside the view volume: %s\n", inside ? "yes" : "no");

  // perspective division -> NDC
  float nx = clip.x / clip.w, ny = clip.y / clip.w, nz = clip.z / clip.w;
  printf("NDC    (%g, %g, %g)\n", nx, ny, nz);

  // viewport transform (pixel y grows downwards) and the depth stored in the depth buffer
  float px = (nx + 1) * 0.5f * width;
  float py = (1 - ny) * 0.5f * height;
  float depth = (nz + 1) * 0.5f;
  printf("pixel  (%g, %g), depth %g\n", px, py, depth);
  return 0;
}

world  (2, 2, -2)
camera (2, 1, -4)
clip   (1.5, 1, 2.6, 4)
inside the view volume: yes
NDC    (0.375, 0.25, 0.65)
pixel  (550, 225), depth 0.825

シェーダー側はOpenGLシリーズの第8章で自分で書く事になります。

6.3 クリッピング

クリッピングは、線分や多角形のうち視体積の外にある部分を切り取る処理です。
必要な理由は3つあります：

仕事量。 ウィンドウの外のピクセルは存在しないので、其れをラスタライズしても意味がありません。
カメラの後ろでの正しさ。 視点より後ろの点は $w \le 0$ です。負のwで割ると点が鏡写しで前に来てしまい、 $w = 0$ ならゼロ除算になります。
深度の範囲。 前方クリップ面より手前や後方クリップ面より奥の物は、深度バッファの範囲外の深度値になってしまいます。

先ず長方形に対する古典的な2次元のアルゴリズム（検定の定番です）を見て、其の後同じ考え方がクリップ空間でどう働くかを見ます。

コーエン・サザーランドの線分クリッピング

コーエン・サザーランドのアルゴリズムは、各端点にウィンドウのどちら側にあるかを示す4ビットの領域コード（アウトコード）を付けます。
ウィンドウ $x_{\text{min}} \le x \le x_{\text{max}}$ 、 $y_{\text{min}} \le y \le y_{\text{max}}$ に対して、此処ではビットの順番を上・下・右・左（TBRL）とします：

ビット	値	立つ条件
上	1000	$y > y_{\text{max}}$
下	0100	$y < y_{\text{min}}$
右	0010	$x > x_{\text{max}}$
左	0001	$x < x_{\text{min}}$

ウィンドウの4辺を延長すると平面は9つの領域に分かれ、同じ領域の点は全て同じコードを持ちます：

ウィンドウ0 0から8 6の周りの9つの領域コードと、ウィンドウにクリップされる線分AB

端点のコードが $c_A$ と $c_B$ の線分に対して：

$c_A \;\text{OR}\; c_B = 0000$ なら、両端点とも内側です。線分全体を自明に採用します。
$c_A \;\text{AND}\; c_B \ne 0000$ なら、両端点が同じ側の外にあります（例えば両方とも上辺より上）。線分はウィンドウに届かないので自明に棄却します。
其れ以外なら、外側にある端点を1つ選び、其のコードが示す辺との交点に移し、コードを計算し直して1に戻ります。

手順1と2はビット演算だけで済み、普通のシーンでは殆どの線分が交点を計算せずに其処で決まる、というのが此のアルゴリズムの良い所です。

計算例。 ウィンドウ $[0, 8] \times [0, 6]$ 、線分は $A(-1, 1)$ から $B(11, 7)$ です。
線分の方向は $(12, 6)$ なので、傾きは $0.5$ です。

コード：Aはウィンドウの左なので $c_A = 0001$ 、Bは右上なので $c_B = 1010$ です。
ORは1011でゼロではないので自明な採用は無く、ANDは0000なので自明な棄却も無しです。
Aは外側で、コードは左を示します。 $x = 0$ との交点は $y = 1 + 0.5 \cdot (0 - (-1)) = 1.5$ です。Aは $(0, 1.5)$ 、コード0000になります。
B（1010）がある為まだ決まらないので、Bをクリップします。コードはまず上を示します。 $y = 6$ との交点は $x = -1 + \frac{6 - 1}{0.5} = 9$ です。Bは $(9, 6)$ になりますが、新しいコードは0010で、まだウィンドウの右です。
Bをもう一度、 $x = 8$ でクリップします： $y = 1 + 0.5 \cdot (8 - (-1)) = 5.5$ です。Bは $(8, 5.5)$ 、コード0000になります。
両方のコードが0000なので、 $(0, 1.5)$ – $(8, 5.5)$ を採用します。

$(9, 6)$ を経由した手順が、何故此のアルゴリズムがループするのかを示しています。
1回の交点計算で、別の外側の領域に着地する事があるのです。
C++では次の様になります：

enum : int { LEFT = 1, RIGHT = 2, BOTTOM = 4, TOP = 8 };

struct Rect {
  float xmin, ymin, xmax, ymax;
};

int outcode(Vec2 p, const Rect &r) {
  int code = 0;
  if (p.x < r.xmin) code |= LEFT;
  else if (p.x > r.xmax) code |= RIGHT;
  if (p.y < r.ymin) code |= BOTTOM;
  else if (p.y > r.ymax) code |= TOP;
  return code;
}

// Cohen-Sutherland: clips the segment a-b to the rectangle r.
// Returns false when nothing of the segment is left.
bool clipLine(Vec2 &a, Vec2 &b, const Rect &r) {
  int ca = outcode(a, r), cb = outcode(b, r);
  while (true) {
    if ((ca | cb) == 0) return true;  // both inside: accept
    if ((ca & cb) != 0) return false; // both outside on the same side: reject
    int c = ca ? ca : cb;             // pick an endpoint that is outside
    Vec2 p;
    if (c & TOP) {
      p = {a.x + (b.x - a.x) * (r.ymax - a.y) / (b.y - a.y), r.ymax};
    } else if (c & BOTTOM) {
      p = {a.x + (b.x - a.x) * (r.ymin - a.y) / (b.y - a.y), r.ymin};
    } else if (c & RIGHT) {
      p = {r.xmax, a.y + (b.y - a.y) * (r.xmax - a.x) / (b.x - a.x)};
    } else {
      p = {r.xmin, a.y + (b.y - a.y) * (r.xmin - a.x) / (b.x - a.x)};
    }
    if (c == ca) {
      a = p;
      ca = outcode(a, r);
    } else {
      b = p;
      cb = outcode(b, r);
    }
  }
}

Rect window{0, 0, 8, 6}と上の線分では、outcodeは1と10（2進数で0001と1010）を返し、clipLineはaを $(0, 1.5)$ 、bを $(8, 5.5)$ にします。
$(9, 1)$ から $(12, 5)$ への線分（両方ともコード0010）は即座に棄却されます。

リャン・バースキーのアルゴリズム（概要）

リャン・バースキーのアルゴリズムは、線分を $0 \le t \le 1$ の $\mathbf{p}(t) = \mathbf{p}_0 + t\,(\mathbf{p}_1 - \mathbf{p}_0)$ と書き、4辺其れぞれについて直線が其の辺を横切るパラメータtを計算します。
$\Delta x = x_1 - x_0$ 、 $\Delta y = y_1 - y_0$ とすると、「ウィンドウの内側」を表す4つの不等式は全て $p_k\,t \le q_k$ の形になります：

辺	$p_k$	$q_k$
左	$-\Delta x$	$x_0 - x_{\text{min}}$
右	$\Delta x$	$x_{\text{max}} - x_0$
下	$-\Delta y$	$y_0 - y_{\text{min}}$
上	$\Delta y$	$y_{\text{max}} - y_0$

$p_k < 0$ の辺では直線は $t = q_k / p_k$ で其の辺から入り、 $p_k > 0$ の辺では出ます。
見える部分は、入るtの最大値（0以上）から出るtの最小値（1以下）までで、其の区間が空なら何も見えません。
此の線分では $\Delta x = 12$ 、 $\Delta y = 6$ です。
入る値は $\frac{-1}{-12} = \frac{1}{12}$ （左）と $\frac{1}{-6} = -\frac{1}{6}$ （下）、出る値は $\frac{9}{12} = \frac{3}{4}$ （右）と $\frac{5}{6}$ （上）です。
従ってtは $\max(0, \frac{1}{12}, -\frac{1}{6}) = \frac{1}{12}$ から $\min(1, \frac{3}{4}, \frac{5}{6}) = \frac{3}{4}$ までで、再び $(0, 1.5)$ と $(8, 5.5)$ が得られます。
ループは無く、除算も高々4回です。

サザーランド・ホッジマンの多角形クリッピング

多角形のクリッピングは、辺を1本ずつクリップするだけでは済みません。
結果も閉じた多角形でなければならず、多角形がウィンドウから出て戻ってくる所では、ウィンドウの境界の一部が新しい辺になるからです。
サザーランド・ホッジマンのアルゴリズムは簡単な工夫で此れを解決します。
多角形全体を1本の辺（1つの半平面）に対してクリップし、其の結果を次の辺に渡すのです。
1つの半平面に対しては、多角形を一周しながら、前の頂点 $S$ から今の頂点 $P$ への各辺を見ます：

$S$	$P$	出力
内	内	$P$
内	外	交点 $I$
外	外	無し
外	内	交点 $I$ 、次に $P$

計算例。 再びウィンドウ $[0, 8] \times [0, 6]$ で、三角形 $A(2, 1)$ 、 $B(11, 4)$ 、 $C(5, 7)$ を左・右・下・上の順にクリップします。

三角形ABC、x 8以下でクリップした結果、y 6以下でクリップした最終的な五角形

左（ $x \ge 0$ ）：3つの頂点は全て内側なので、リストはA、B、Cの儘です。
右（ $x \le 8$ ）：辺C→Aは内→内なのでAを出力します。辺A→Bは内→外です。AB上で $t = \frac{8 - 2}{11 - 2} = \frac{2}{3}$ 、 $y = 1 + \frac{2}{3} \cdot 3 = 3$ なので、 $(8, 3)$ を出力します。辺B→Cは外→内です。BC上で $t = \frac{11 - 8}{11 - 5} = 0.5$ 、 $y = 4 + 0.5 \cdot 3 = 5.5$ なので、 $(8, 5.5)$ を出力し、次にCを出力します。新しいリストは $(2, 1), (8, 3), (8, 5.5), (5, 7)$ の四角形です。
下（ $y \ge 0$ ）：全て内側なので変わりません。
上（ $y \le 6$ ）：辺C→Aは外→内で、交差はCから $t = \frac{7 - 6}{7 - 1} = \frac{1}{6}$ の所、 $x = 5 - \frac{1}{6} \cdot 3 = 4.5$ です。 $(4.5, 6)$ を出力し、次にAを出力します。辺A→(8, 3)と(8, 3)→(8, 5.5)は内→内なので、 $(8, 3)$ と $(8, 5.5)$ を出力します。辺(8, 5.5)→Cは内→外で、交差は $t = \frac{6 - 5.5}{7 - 5.5} = \frac{1}{3}$ 、 $x = 8 - \frac{1}{3} \cdot 3 = 7$ なので、 $(7, 6)$ を出力します。

結果は五角形 $(4.5, 6), (2, 1), (8, 3), (8, 5.5), (7, 6)$ です。
三角形を入れて頂点が5つ出てきましたが、此れは普通の事です。
ウィンドウの各辺は頂点を1つ増やす事が出来ます。
サザーランド・ホッジマン法は、凸のクリッピング領域に対してならどんな多角形にも使えます。
但し凹多角形では、ウィンドウの境界に沿って幅ゼロの「橋」の辺が結果に残る事があります。
ラスタライザーには其れは何も描かない辺ですが、其れを避ける別のアルゴリズム（ワイラー・アサートン法等）もあります。

同次座標のクリップ空間でのクリッピング

GPUは透視除算の前、クリップ座標で、6つの平面 $-w \le x \le w$ 、 $-w \le y \le w$ 、 $-w \le z \le w$ （Vulkanでは $0 \le z \le w$ ）に対してクリップします。
此れらも4次元の平面なので、サザーランド・ホッジマン法が其の儘使えます。
「左の平面の内側」は $x + w \ge 0$ 、「前方クリップ面の内側」は $z + w \ge 0$ で、交点のパラメータは此れらの符号付きの値の比で求まります。

何故除算の前なのでしょうか？
先程の頂点P（カメラ座標 $(2, 1, -4)$ ）から、カメラの後ろにある点Q（カメラ座標 $(0, 0, 2)$ ）への線分を見てみましょう：

カメラの前のPから後ろのQへの線分を上から見た図。前方クリップ面の点1, −1でクリップされる

クリップ座標ではPが $(1.5, 1, 2.6, 4)$ 、Qが $(0, 0, -4.6, -2)$ です。
Qは $w = -2$ で、視点の後ろにあります。
先に割ってしまうとQは $(0, 0, 2.3)$ 、つまり画面の中心になり、ラスタライザーはPの位置 $(0.375, 0.25)$ から中心に向かって線を引いてしまいます。
しかし本当の線分は、カメラから見ると中心から離れる方向に進み、前方クリップ面で視界から出ていきます。

前方クリップ面でクリップすれば正しくなります。
符号付きの値 $z + w$ は、Pが $2.6 + 4 = 6.6$ 、Qが $-4.6 + (-2) = -6.6$ なので、交差は次の所です：

t = \frac{6.6}{6.6 - (-6.6)} = 0.5, \qquad \mathbf{I} = \mathbf{P} + 0.5\,(\mathbf{Q} - \mathbf{P}) = (0.75, 0.5, -1, 1)

$w = 1$ で割るとNDCは $(0.75, 0.5, -1)$ です。
深度−1は丁度前方クリップ面で、見える線分は $(0.375, 0.25)$ から外向きに $(0.75, 0.5)$ まで伸びます。
確認として、投影行列は線型なので、カメラ空間でも同じ $t = 0.5$ が使えます。
$(2, 1, -4)$ と $(0, 0, 2)$ の中点は $(1, 0.5, -1)$ で、前方クリップ面 $z = -n = -1$ の上にあります。
前方クリップ面でクリップした後は、残る全ての頂点が $w \ge n > 0$ なので、除算は常に安全です。

実際には、多くのGPUが本当にクリップするのは前方（と後方）クリップ面だけです。
xとyについては大きな「ガードバンド」を使い、ビューポートの外のピクセルをラスタライザーが単に飛ばします。
新しい頂点を作るより安上がりで、画面上の結果は同じです。

6.4 カリング

クリッピングはプリミティブを切ります。
カリングは、コストが掛かる前にプリミティブや物体を丸ごと捨てます。

背面除去

今の立方体の様な閉じた物体では、カメラに背を向けた面は、カメラの方を向いた面の後ろに必ず隠れます。
背面除去（バックフェースカリング）は其れらを飛ばし、閉じたメッシュの三角形のおよそ半分を取り除きます。
法線が視点から離れる方向を向いている面が背面です。
面の法線 $\mathbf{n}$ 、面上の点 $\mathbf{p}$ 、視点 $\mathbf{e}$ に対して：

\mathbf{n} \cdot (\mathbf{e} - \mathbf{p}) \le 0 \quad \Rightarrow \quad \text{背面}

使うのは面から視点への方向 $\mathbf{e} - \mathbf{p}$ で、1つの固定した視線方向ではない事に注意して下さい。
透視投影のカメラでは、面ごとに少しずつ違う方向から見ているからです。

カメラ空間（視点が原点）での計算例です。
三角形 $A(0, 0, -5)$ 、 $B(2, 0, -5)$ 、 $C(0, 2, -5)$ の法線は $(B - A) \times (C - A) = (2, 0, 0) \times (0, 2, 0) = (0, 0, 4)$ で、カメラの方を向いています。
$\mathbf{n} \cdot (\mathbf{e} - A) = (0, 0, 4) \cdot (0, 0, 5) = 20 > 0$ なので表面です。
同じ頂点をA、C、Bの順に並べると法線は $(0, 0, -4)$ に反転し、内積は−20になって背面になります。

其の為、三角形の頂点の順番（巻き順）が大事なのです。
GPUは此の判定を投影の後、スクリーン空間で行います。
表面の頂点は画面上で反時計回りに並び（OpenGLの既定値、glFrontFace(GL_CCW)）、三角形の符号付き面積の符号で判定します。
其の符号付き面積は6.9節でエッジ関数を使って計算します。
規約でyを反転すると（例えばVulkanのyが下向きのNDC）、全ての三角形の画面上の巻き順も反転するので、表面の設定を合わせないとモデル全体が消えてしまいます。
背面除去は完全な隠面消去ではありません。
凹んだ部分のある物体や複数の物体では、表面同士が互いを隠す事があり、其れは第10章の主題です。

視錐台カリング

視錐台カリングは、見える筈の無い物体を丸ごと飛ばします。
三角形を1つずつ調べるのは遅過ぎるので、各物体に球や箱の様な単純なバウンディングボリュームを持たせ、其れだけを視錐台の6つの平面と比べます。
中心 $\mathbf{c}$ （カメラ座標）、半径 $r$ の球と、視点を通る4つの側面の1つ（内向きの単位法線 $\mathbf{n}$ ）では、符号付き距離は $d = \mathbf{n} \cdot \mathbf{c}$ です（前方・後方クリップ面は視点を通らないので定数が加わり、例えば前方クリップ面では $-c_z - n$ です）：

$d < -r$ ：此の平面の完全に外側なので、物体をカリングします。
6つ全ての平面で $d \ge r$ ：完全に内側で、クリッピングは全く要りません。
其れ以外：物体は描画され、其の三角形は普段通りクリップされます。

視錐台を上から見た図。内側の球、右の平面の外の球、左の平面を跨ぐ球

6.2節のカメラ（縦の視野角90°、アスペクト比4/3）での計算例です。
距離 $d$ での視界の半分の幅は $\frac{4}{3}d$ なので、上から見た右の平面は $x = \frac{4}{3}(-z)$ 、つまり $3x + 4z = 0$ です。
其の内向きの単位法線は $\mathbf{n} = (-0.6, 0, -0.8)$ です。
カメラ座標 $(10, 0, -6)$ にある半径1の球では：

d = -0.6 \cdot 10 - 0.8 \cdot (-6) = -6 + 4.8 = -1.2 < -1

完全に外側なので、其の（もしかすると数千個の）三角形はGPUに届きません。
ゲームエンジンは更に、バウンディングボリュームを階層（バウンディングボリューム階層やシーンツリー）にまとめ、1回の判定で建物1つを中身ごとカリング出来る様にしています。

検定のポイント

順番：モデリング変換 → ビュー変換 → 投影変換 → クリッピング → 透視除算 → ビューポート変換。クリッピングは除算の前です。
クリップ空間での判定： $-w \le x, y, z \le w$ なら内側。カメラの後ろの点は $w \le 0$ です。
コーエン・サザーランド法：OR = 0000なら採用、AND ≠ 0000なら棄却、其れ以外は交点を求めて繰り返し。AND = 0000でも線分が見えるとは限りません。
サザーランド・ホッジマン法は1辺ずつクリップし、出力の頂点数は入力より多くなる事があります。
背面除去は法線（又は巻き順）を使い、完全な隠面消去ではありません。

6.5 GPUの描画パイプライン

次は機械の方です。
GPUが描画命令ごとに実行する段階を、順番に並べると次の様になります：

頂点データからフレームバッファまでのGPUの描画パイプライン。プログラム可能な段階と固定機能の段階

頂点データ：モデルの位置、法線、色、テクスチャ座標で、GPUのメモリにあります。
頂点処理：頂点シェーダーが頂点ごとに1回実行し、クリップ座標と、次に渡す値（法線、色等）を出力します。昔のレンダラーでは頂点ごとのライティングも此処で行っていました。
プリミティブアセンブリ：インデックスのリストに従って頂点をプリミティブ（普通は三角形）にまとめます。
視体積に対するクリッピング（6.3節）。
透視除算とビューポート変換（6.2節）。
スクリーン空間の三角形の巻き順による背面除去（6.4節）。
ラスタライズ：各三角形が覆うピクセルを求め、其々に補間した値を持つフラグメントを作ります（6.6〜6.9節）。
フラグメント（ピクセル）処理：フラグメントシェーダー（Direct3Dではピクセルシェーダー）が、テクスチャやライティングを使って各フラグメントの色を計算します。
フラグメントごとのテスト：シザーテスト（長方形の内側か？）、ステンシルテスト（ピクセルごとのマスクと比べる）、深度テスト（Zテスト：既に書かれている物より手前か？）。不合格のフラグメントは捨てられます。
ブレンディング：フラグメントの色と既に書かれている色を合成します。半透明（アルファブレンディング）に使います。
フレームバッファ：画像を保持するメモリです。

ビューポート変換までの段階をジオメトリ処理、残りをピクセル処理（ラスタ処理）と呼びます。
シェーダーが深度を変更しない場合、多くのGPUは深度テストをフラグメントシェーダーの前に移し（「アーリーZ」）、隠れるフラグメントはシェーディングすらしません。
結果は同じです。
深度テストはZバッファ法そのもので、第10章で説明します。

フレームバッファ

フレームバッファは、同じ大きさの複数の画像から成ります：

カラーバッファ：絵そのもので、普通はチャンネルごとに8ビット（RGBA）です。
深度バッファ（Zバッファ）：ピクセルごとに1つの深度値です。
ステンシルバッファ：ピクセルごとの小さな整数で、マスクや輪郭線に使います。

大きさはすぐに膨らみます。
1ピクセル4バイトの1920×1080のカラーバッファは $1920 \cdot 1080 \cdot 4 = 8\,294\,400$ バイト、約7.9 MiBで、典型的な24ビット深度と8ビットステンシルのバッファも同じだけ使います。

ダブルバッファと垂直同期

GPUがモニターに表示中の画像に直接描くと、描きかけのフレームが見えてしまいます。
ダブルバッファは2つのカラーバッファを使います。
フロントバッファを表示している間にGPUはバックバッファに描き、フレームが完成したら2つを入れ替えます。
モニターは画像を上から下へ1行ずつ読み、其れを毎回のリフレッシュで繰り返します。
其の読み出しの途中で入れ替えが起こると、画面の上半分は古いフレーム、下半分は新しいフレームになり、境目が見えます。
此れをテアリングと呼びます。
垂直同期（V-sync）は、モニターが1回のリフレッシュを終える（垂直帰線期間）まで入れ替えを待たせます。
60 Hzなら1フレームに使えるのは $\frac{1000}{60} \approx 16.7$ msです。
代償もあります。
1フレームに20 ms掛かると1回のリフレッシュに間に合わず、33.3 ms後に表示されるので、単純なダブルバッファではフレームレートが60から一気に30に落ちます。
トリプルバッファ（2つ目のバックバッファでGPUが作業を続けられる）や可変リフレッシュレートのディスプレイが此れを和らげます。

固定機能とプログラマブルシェーダー

初期のグラフィックスAPI（OpenGL 1.x、バージョン7までのDirect3D）では、全ての段階が固定機能でした。
光源の位置や霧の色の様なパラメータを設定出来るだけで、残りはハードウェア内蔵の式が処理しました。
2000年代の初めに頂点とピクセルの段階がプログラマブルになりました。
Direct3D 8（2000年）が頂点シェーダーとピクセルシェーダーを導入し、OpenGL 2.0（2004年）がGLSLをもたらしました。
現代のコアAPI（OpenGLのコアプロファイル、Vulkan、Direct3D 10以降）には、固定機能の頂点やピクセルの段階はもう全く無く、少なくとも頂点シェーダーを、色を書き込むならフラグメントシェーダーも書かなければなりません。
クリッピング、ラスタライズ、テスト、ブレンディングは今でも固定です（ブレンディングは設定は出来ますがプログラムは出来ません）。
単純で、極めて速くなければならないからです。
GPUとリアルタイムシステムは第17章で詳しく見ます。
又、GLSLシリーズとOpenGLシリーズでは、此れらの段階を自分でプログラムします。

6.6 線分のラスタライズ：DDAとブレゼンハム

ラスタライズはスキャン変換（走査変換）とも呼ばれ、座標で記述された図形をピクセルの集まりに変換する処理です。
古典的なアルゴリズムは全て、同じ問いになるべく安く答えます。
理想の図形に一番近いピクセルはどれか、という問いです。
座標について一言。
線分と円のアルゴリズムでは古典的な規約に従い、ピクセル $(x, y)$ を整数座標の点 $(x, y)$ として扱います。
端点はピクセルの中心に乗ります。
多角形と三角形の塗り潰し（6.8節と6.9節）ではGPUの規約に切り替え、ピクセル $(i, j)$ は $(i, j)$ から $(i + 1, j + 1)$ の正方形、中心は $(i + 0.5, j + 0.5)$ とします。
どちらも、方眼紙やOpenGLのウィンドウ座標と同じくyは上向きです。

DDA

$(x_0, y_0)$ から $(x_1, y_1)$ への、傾き $m = \frac{\Delta y}{\Delta x}$ が0と1の間の線分を考えます。
此の時xの方がyより速く変わるので、各列に丁度1ピクセルを描きます。
DDA（ディジタル微分解析器）はxを1ずつ、yをmずつ進め、丸めます：

y_{k+1} = y_k + m, \qquad \text{ピクセル } (x_k, \operatorname{round}(y_k))

$(1, 1)$ から $(11, 5)$ への線分では $m = \frac{4}{10} = 0.4$ で、yの値は1、1.4、1.8、2.2、2.6、3.0、3.4、3.8、4.2、4.6、5.0、丸めると1、1、2、2、3、3、3、4、4、5、5です。
此れでも動きますが、ピクセルごとに浮動小数点の加算と丸めが必要で、0.4（2進数では正確に表せません）を繰り返し足すので、長い線分では誤差が少しずつ溜まります。

ブレゼンハムのアルゴリズム

ブレゼンハムのアルゴリズムは、整数の加算だけで同じピクセルを求めます。
今ピクセル $(x_k, y_k)$ を描いたとします。
次の列は $x_k + 1$ で、候補は真右のE $(x_k + 1, y_k)$ と右上のNE $(x_k + 1, y_k + 1)$ の2つだけです。
其の列での理想の直線の高さは $y = m(x_k + 1) + b$ です。
2つの候補までの距離は

d_{\text{lower}} = y - y_k = m(x_k + 1) + b - y_k, \qquad d_{\text{upper}} = (y_k + 1) - y

で、差が正の時に丁度NEの方が近くなります：

d_{\text{lower}} - d_{\text{upper}} = 2m(x_k + 1) - 2y_k + 2b - 1

傾き $m = \frac{\Delta y}{\Delta x}$ は分数なので、 $\Delta x$ （正なので符号は変わりません）を掛け、其の結果を判定変数と呼びます：

p_k = \Delta x\,(d_{\text{lower}} - d_{\text{upper}}) = 2\Delta y\,x_k - 2\Delta x\,y_k + \text{定数}

残るのは整数だけです。
更に良い事に、 $p_k$ を毎回一から計算する必要はありません。
1列進むとxは1増え、yは0か1増えるので

p_{k+1} = p_k + 2\Delta y - 2\Delta x\,(y_{k+1} - y_k)

で、最初のピクセルが丁度直線上にある事を使うと、初期値は

p_0 = 2\Delta y - \Delta x

です。
アルゴリズム全体は次の通りです：

$p_k \ge 0$ なら：NEに進み（ $y$ + 1）、 $2(\Delta y - \Delta x)$ を足します。
$p_k < 0$ なら：Eに進み、 $2\Delta y$ を足します。

（ $p_k = 0$ の時は直線が2つのピクセルの丁度中間を通るので、どちらを選んでも構いません。此処ではNEにします。）

$(1, 1)$ から $(11, 5)$ への計算例です。
$\Delta x = 10$ 、 $\Delta y = 4$ なので $p_0 = 8 - 10 = -2$ 、Eの時は8を、NEの時は−12を足します。

x	y	$p$	判定
1	1	−2	E：−2 + 8 = 6
2	1	6	NE：6 − 12 = −6
3	2	−6	E：−6 + 8 = 2
4	2	2	NE：2 − 12 = −10
5	3	−10	E：−10 + 8 = −2
6	3	−2	E：−2 + 8 = 6
7	3	6	NE：6 − 12 = −6
8	4	−6	E：−6 + 8 = 2
9	4	2	NE：2 − 12 = −10
10	5	−10	E：−10 + 8 = −2
11	5	−2	（終点）

ピクセルの格子上の1, 1から11, 5へのブレゼンハムの線分と、各列の判定変数

ピクセルはDDAと全く同じで、整数の計算には溜まる丸め誤差が無いので、最後のピクセルは丁度 $(11, 5)$ で終わります。

#include <cstdio>

// Bresenham's line algorithm for 0 <= dy <= dx (slope between 0 and 1).
// plot(x, y) sets one pixel.
template <class Plot>
void bresenham(int x0, int y0, int x1, int y1, Plot plot) {
  int dx = x1 - x0, dy = y1 - y0;
  int d = 2 * dy - dx; // the decision variable
  int y = y0;
  for (int x = x0; x <= x1; ++x) {
    plot(x, y);
    if (d >= 0) {
      ++y; // the upper pixel (NE) was closer
      d += 2 * (dy - dx);
    } else {
      d += 2 * dy; // the lower pixel (E) was closer
    }
  }
}

int main() {
  bresenham(1, 1, 11, 5, [](int x, int y) { printf("(%d, %d) ", x, y); });
  printf("\n");
  return 0;
}

(1, 1) (2, 1) (3, 2) (4, 2) (5, 3) (6, 3) (7, 3) (8, 4) (9, 4) (10, 5) (11, 5)

残りの7つの八分円も、対称性を使って同じコードで描けます。
$\left| \Delta y \right| > \left| \Delta x \right|$ （急な線分）ならxとyの役割を入れ替えてyに沿って進み、線分が左向きなら2つの端点を入れ替え、下向きならyを+1ではなく−1ずつ進めます。

6.7 中点アルゴリズムによる円の描画

円は8回対称です。
原点を中心とする円の上に $(x, y)$ があれば、 $(\pm x, \pm y)$ と $(\pm y, \pm x)$ も円の上にあります。
従って計算するのは8分の1、つまり $(0, r)$ から右へ $x = y$ まで進む、傾きが0と−1の間の弧だけで、各ピクセルを残りの7つの八分円に映せば済みます。

此の弧ではxは常に1ずつ増え、yは其の儘か1減るかのどちらかです。
中点アルゴリズムは、2つの候補の中間の点 $(x_k + 1, y_k - \frac{1}{2})$ を、円の関数

F(x, y) = x^2 + y^2 - r^2

で調べて決めます。
此の関数は円の内側で負、外側で正です。
中点が内側（ $F < 0$ ）なら円は其の上を通るのでyを其の儘にし、そうでなければ1つ下がります。
$p_k = F(x_k + 1, y_k - \frac{1}{2})$ として2乗を展開すると、整数の更新式が得られます：

$p_k < 0$ なら：yは其の儘、 $p_{k+1} = p_k + 2x_{k+1} + 1$
其れ以外なら： $y_{k+1} = y_k - 1$ 、 $p_{k+1} = p_k + 2x_{k+1} + 1 - 2y_{k+1}$

初期値は $p_0 = F(1, r - \frac{1}{2}) = \frac{5}{4} - r$ で、此れを $1 - r$ に丸めます（更新は全て整数で、pは符号しか使わないので、4分の1の差が判定を変える事はありません）。

$r = 8$ 、 $p_0 = -7$ の計算例です：

x	y	$p$	次
0	8	−7	yは其の儘：−7 + 2 · 1 + 1 = −4
1	8	−4	yは其の儘：−4 + 2 · 2 + 1 = 1
2	8	1	下がる：1 + 2 · 3 + 1 − 2 · 7 = −6
3	7	−6	yは其の儘：−6 + 2 · 4 + 1 = 3
4	7	3	下がる：3 + 2 · 5 + 1 − 2 · 6 = 2
5	6	2	次は(6, 5)でx = yを越えるので終了

1つを本当の円と比べてみましょう。
$x = 4$ での正確な高さは $\sqrt{64 - 16} \approx 6.93$ で、丸めると7、選んだピクセルと一致します。

半径8の中点アルゴリズムの円。最初の八分円を計算し、残りの7つは鏡映で求める

黄色のピクセルが計算した6つで、オレンジ色は其の鏡像です。

6.8 スキャンライン法による多角形の塗り潰し

多角形を塗り潰すには全てのピクセルを多角形と比べても良いのですが、もっと賢い古典的な方法があります。
スキャンライン法です。
画像を1行（スキャンライン）ずつ、ピクセルの中心の高さ $y = j + 0.5$ で処理します。
各スキャンラインで、多角形の辺と交わる所を求め、其のx座標を並べ替え、2つずつ組にして其の間を塗ります。
1番目から2番目の交点まで、3番目から4番目まで、という具合です。
此れが偶奇規則（パリティ規則）です。
点から右へ伸ばした半直線が境界と奇数回交われば、其の点は内側です。

スキャンライン法で塗り潰した凹多角形と、スキャンラインy = 5.5の4つの交点

計算例。 多角形 $(1, 1), (11, 1), (11, 8), (6, 4), (1, 8)$ は、上にV字の切れ込みがあります。
スキャンライン $y = 5.5$ は4本の辺と交わります：

左の辺 $x = 1$ と右の辺 $x = 11$
$(6, 4)$ から $(1, 8)$ への辺：yが1増えるとxは $\frac{5}{4} = 1.25$ 減るので、 $x = 6 - 1.25 \cdot (5.5 - 4) = 4.125$
$(6, 4)$ から $(11, 8)$ への辺： $x = 6 + 1.25 \cdot 1.5 = 7.875$

並べ替えると1、4.125、7.875、11です。
組 $[1, 4.125)$ と $[7.875, 11)$ を塗ります。
ピクセルの中心1.5、2.5、3.5が1つ目の区間に、8.5、9.5、10.5が2つ目の区間に入るので、此の行はピクセル1、2、3と8、9、10になります。
ピクセル4〜7（中心4.5〜7.5）は切れ込みの中です。

エッジテーブルとアクティブエッジリスト

毎回全ての交点を一から計算するのは無駄です。
古典的な実装は2つのリストを持ちます：

エッジテーブル（辺リスト）：水平でない全ての辺を下端 $y_{\text{min}}$ の順に並べた物で、 $y_{\text{max}}$ 、 $y_{\text{min}}$ でのx、そして $\frac{1}{m} = \frac{\Delta x}{\Delta y}$ を持ちます。水平な辺はスキャンラインと交わらないので除きます。
アクティブエッジリスト：今のスキャンラインと交わる辺と、其々の現在のxです。

各スキャンラインでは、此処から始まる辺をエッジテーブルからアクティブリストに移し、終わった辺を取り除き、xで並べ替えて組を塗り、次のスキャンラインの為に全てのxに $\frac{1}{m}$ を足します。
此の例では、2本の斜めの辺が $y = 4$ で $x = 6$ 、 $\frac{1}{m} = -1.25$ と $+1.25$ としてアクティブになります。
交点はスキャンラインごとに1.25ずつ外側に移動し、 $y = 4.5$ で5.375と6.625、 $y = 5.5$ で4.125と7.875、 $y = 6.5$ で2.875と9.125、 $y = 7.5$ で1.625と10.375になります。
全ての行を数えると50ピクセルで、多角形の面積（座標の公式でも50です）と丁度同じです。
一般にはピクセル数は面積に近いだけで、等しいとは限りません。

スキャンライン上の頂点

スキャンラインが丁度頂点を通ったらどうなるでしょうか？
其処では2本の辺が出会うので、交点を2回数えるか1回数えるかを正しく決めないと、偶奇が崩れます。
標準的な規則では、各辺を半開区間にします。
辺はスキャンラインyで $y_{\text{min}} \le y < y_{\text{max}}$ の時だけ数えます。
一方の辺が下から来てもう一方が上に続く頂点では、丁度1本だけが数えられ、偶奇が1回変わります。
正しい結果です。
山の頂点（両方の辺が頂点より下）ではどちらも数えず、谷の頂点（両方の辺が上）では両方を数えます。
どちらも偶奇は変わらず、此れも正しい結果です。
スキャンラインが其処で多角形に触れているだけだからです。
整数の頂点をピクセルの中心（ $j + 0.5$ ）でサンプリングすれば此の場合は起きませんが、任意の頂点の為には此の規則が必要です。

偶奇規則と非ゼロ回転数規則

単純な多角形では2つの規則は一致しますが、一筆書きの星の様な自己交差する多角形では一致しません。
非ゼロ回転数規則は、各交差を辺の向きによって+1又は−1と数え、合計がゼロでなければ内側とします。
星の中心では境界が2回巻いているので、偶奇規則では穴が開き、非ゼロ回転数規則では塗られます：

星形の多角形を偶奇規則でラスタライズすると中心が空き、非ゼロ回転数規則では中心も塗られる

どちらの画像も、全てのピクセルの中心から右へ半直線を伸ばして計算した物です。
ベクタ形式では選ぶ事が出来ます。
SVGとPDFには丁度此の2つの選択肢を持つ塗り潰し規則の設定があります。
全く別の系統としてシードフィルもあります。
既に描かれた輪郭の内側の1ピクセルから始めて隣へ広げていく、ペイントソフトのバケツツールの様な方法で、幾何ではなくピクセルで塗ります。

6.9 エッジ関数による三角形のラスタライズ

GPUがラスタライズするのは三角形だけで、並べ替えたリストを使うスキャンライン法は使いません。
代わりにエッジ関数を使います。
全てのピクセルで同じ単純な式を使うので、何千もの並列なユニットに向いているからです。

エッジ関数

$\mathbf{a}$ から $\mathbf{b}$ への向きのある辺と点 $\mathbf{p}$ に対して：

E_{ab}(\mathbf{p}) = (b_x - a_x)(p_y - a_y) - (b_y - a_y)(p_x - a_x)

此れは外積 $(\mathbf{b} - \mathbf{a}) \times (\mathbf{p} - \mathbf{a})$ のz成分（線型代数の第5章）なので、 $\mathbf{p}$ が辺の左にあれば正、右にあれば負、直線上ならゼロです。
反時計回り（yは上向き）に並べた三角形A、B、Cでは、内側は3辺全ての左にあります：

\mathbf{p} \text{ が内側} \iff E_{AB}(\mathbf{p}) \ge 0,\; E_{BC}(\mathbf{p}) \ge 0,\; E_{CA}(\mathbf{p}) \ge 0

ラスタライザーは三角形のバウンディングボックス内のピクセルを順に回り、各ピクセルの中心を判定します。
1ピクセル右に動くと $E_{ab}$ は定数 $-(b_y - a_y)$ だけ変わるので、最初のピクセルの後は1回の判定が加算3回で済みます。
そして $E_{AB}(C)$ は三角形の符号付き面積の2倍で、反時計回りなら正、時計回りなら負です。
此れが6.4節の背面除去の判定です。

計算例。 三角形 $A(1, 1)$ 、 $B(9, 1)$ 、 $C(3, 7)$ です。
$E_{AB}(C) = 8 \cdot 6 - 0 \cdot 2 = 48 > 0$ なので反時計回り、表向きで、面積は24です。
ピクセルの中心 $\mathbf{p} = (4.5, 2.5)$ を判定します：

E_{BC}(\mathbf{p}) = (3 - 9)(2.5 - 1) - (7 - 1)(4.5 - 9) = -9 + 27 = 18

E_{CA}(\mathbf{p}) = (1 - 3)(2.5 - 7) - (1 - 7)(4.5 - 3) = 9 + 9 = 18

E_{AB}(\mathbf{p}) = (9 - 1)(2.5 - 1) - (1 - 1)(4.5 - 1) = 12

全て正なので、此のピクセルは覆われています。
一方、中心 $(8.5, 4.5)$ では $E_{BC} = (-6)(3.5) - 6 \cdot (-0.5) = -18$ となり、BCの右側、つまり外側です。

ピクセルの格子上の三角形ABC。覆われたピクセルを重心座標で補間した色で塗り、点pを示す

トップレフトルール

図のピンクの丸を見て下さい。
其れらのピクセルの中心は、 $E_{BC} = 0$ となる辺BCの丁度上にあります。
別の三角形が其の辺を共有していると（例えば四角形を作る2つの三角形）、「≥ 0」の判定では両方が其のピクセルを取り、ピクセルが2回描かれます（半透明では間違った結果になります）。
両方で「> 0」にすると、どちらも描かず、隙間が出来ます。
其の為、実際のAPIのラスタライズ規則では、共有する辺の上のピクセルの中心は2つの三角形の丁度一方に属さなければなりません。
例えばOpenGLの仕様は正に此れを定めています。
Direct3Dは其の具体的な決め方をトップレフトルールとして定義しています。
辺の丁度上にある中心は、其の辺が上辺（完全に水平で、三角形が其の下にある）か左辺（三角形の左側にある）の時だけ覆われる、という規則です。
yが上向きの反時計回りの三角形では、左辺は下向きに進む辺（ $\Delta y < 0$ ）です。
此の三角形ではCAが下向きなので、CA上の中心 $(1.5, 2.5)$ と $(2.5, 5.5)$ は覆われ、BCは上向きなので、BC上の6つの中心は隣の三角形に任せます。
其の結果が図の22個の色付きのピクセルです。

重心座標による補間

ラスタライズでは、各フラグメントに頂点からの値（色、テクスチャ座標、深度）も与えなければなりません。
其れは3つのエッジ関数からタダで得られます。
全体の $E_{AB}(C)$ で割るのです：

\lambda_A = \frac{E_{BC}(\mathbf{p})}{E_{AB}(C)}, \qquad \lambda_B = \frac{E_{CA}(\mathbf{p})}{E_{AB}(C)}, \qquad \lambda_C = \frac{E_{AB}(\mathbf{p})}{E_{AB}(C)}

此れが $\mathbf{p}$ の重心座標です。
其々は、頂点の向かい側にある小さな三角形の面積を全体の面積で割った物です（図の破線が三角形を此の3つの部分に分けています）。
三角形の内側では負にならず、合計は1で、Aでは丁度 $\lambda_A = 1$ です。
頂点の値 $v$ は次の様に補間されます：

v(\mathbf{p}) = \lambda_A v_A + \lambda_B v_B + \lambda_C v_C

此のピクセルでは $\lambda_A = \frac{18}{48} = 0.375$ 、 $\lambda_B = \frac{18}{48} = 0.375$ 、 $\lambda_C = \frac{12}{48} = 0.25$ で、 $0.375 + 0.375 + 0.25 = 1$ です。
Aを赤 $(1, 0, 0)$ 、Bを緑 $(0, 1, 0)$ 、Cを青 $(0, 0, 1)$ にすると、ピクセルの色は $(0.375, 0.375, 0.25)$ のオリーブ色になり、図の其のマスの色と丁度一致します。
深度テストの為の深度も、同じ重みで補間します。

トップレフトルール付きのラスタライザーです。
覆われたピクセル（一番上の行から）と、此のピクセルの重みを表示します：

#include <cstdio>
#include "linalg.hh"

// Edge function: positive when p is to the left of the directed edge a -> b (y up).
float edgeFunction(Vec2 a, Vec2 b, Vec2 p) {
  return (b.x - a.x) * (p.y - a.y) - (b.y - a.y) * (p.x - a.x);
}

// Top-left rule for a counter-clockwise triangle with y up:
// a left edge goes down, a top edge is horizontal and goes left.
bool isTopLeft(Vec2 a, Vec2 b) {
  return b.y < a.y || (b.y == a.y && b.x < a.x);
}

bool covers(float e, Vec2 a, Vec2 b) {
  return e > 0 || (e == 0 && isTopLeft(a, b));
}

int main() {
  Vec2 a{1, 1}, b{9, 1}, c{3, 7}; // counter-clockwise, y up
  float area2 = edgeFunction(a, b, c); // twice the area
  const int width = 10, height = 8;
  for (int y = height - 1; y >= 0; --y) { // print the top row first
    for (int x = 0; x < width; ++x) {
      Vec2 p{x + 0.5f, y + 0.5f}; // the pixel center
      float e0 = edgeFunction(b, c, p), e1 = edgeFunction(c, a, p), e2 = edgeFunction(a, b, p);
      bool in = covers(e0, b, c) && covers(e1, c, a) && covers(e2, a, b);
      putchar(in ? '#' : '.');
    }
    putchar('\n');
  }
  // barycentric coordinates of one pixel center
  Vec2 p{4.5f, 2.5f};
  float la = edgeFunction(b, c, p) / area2;
  float lb = edgeFunction(c, a, p) / area2;
  float lc = edgeFunction(a, b, p) / area2;
  printf("lambda = (%g, %g, %g)\n", la, lb, lc);
  return 0;
}

..........
..........
..##......
..###.....
..####....
.######...
.#######..
..........
lambda = (0.375, 0.375, 0.25)

パースペクティブコレクト補間

1つ落とし穴があります。
上の重みは画面上で測った物です。
透視投影では、画面上の等しい歩幅は3次元の三角形上の等しい歩幅ではありません（遠い部分が縮んでいます）。
其の為、画面空間の重みでテクスチャ座標を補間すると、テクスチャが揺れたり曲がったりします。
其の対策がパースペクティブコレクト補間（透視補正補間）で、 $\frac{v}{w}$ と $\frac{1}{w}$ を画面上で線型に補間し、ピクセルごとに両者を割ります。
GPUは全てのvarying変数に対して此れを自動で行います。
NDCの深度は例外で、画面上の位置のアフィン関数なので其の儘線型に補間出来ます。
此れがZバッファ法が上手く働く理由の1つです。
詳しい導出は第2部で行います。

パイプラインの中のアンチエイリアシング

ピクセルの中心だけを判定するのは点サンプリングなので、三角形の辺には第2章で見たジャギーが出ます。
対策はサンプルを増やす事です。
スーパーサンプリングは1ピクセルに複数の点を判定して其々をシェーディングし、MSAA（マルチサンプルアンチエイリアシング）は複数の点で覆われ具合を判定しつつ、フラグメントシェーダーはピクセルごとに1回だけ実行します。
此れらは第2部で扱い、OpenGLシリーズでは自分でMSAAを有効にします。

検定のポイント

ブレゼンハムのアルゴリズムは整数の加算だけを使います。判定変数は $2\Delta y - \Delta x$ から始まり、 $2\Delta y$ （E）又は $2(\Delta y - \Delta x)$ （NE）ずつ増えます。DDAは浮動小数点と丸めが必要です。
中点アルゴリズムによる円は、八分円を1つだけ計算し、8通りに映します。
スキャンライン法：交点をxで並べ替え、2つずつ組にして塗ります（偶奇規則）。辺はyについて半開区間とし、水平な辺は除きます。
偶奇規則と非ゼロ回転数規則が異なるのは、自己交差する多角形だけです。
エッジ関数：3つ全てが同じ符号なら内側。其の比が重心座標で、合計は1です。

6.10 まとめ

ビューイングパイプライン：モデリング座標系 →（モデリング変換）→ ワールド座標系 →（ビュー変換）→ カメラ座標系 →（投影変換）→ クリップ座標系 → クリッピング →（透視除算）→ NDC →（ビューポート変換）→ スクリーン座標系。
カメラの後ろの点は $w \le 0$ になるので、クリッピングは除算の前に、クリップ空間で $-w \le x, y, z \le w$ に対して行います。
コーエン・サザーランド法は4ビットの領域コードで素早く採用（OR = 0）と棄却（AND ≠ 0）を行い、リャン・バースキー法は直線のパラメータtを使い、サザーランド・ホッジマン法は多角形をウィンドウの辺1本ずつクリップします。
背面除去は法線が視点から離れる向きの面を捨て（画面上では巻き順で判定）、視錐台カリングはバウンディングボリュームが視錐台の平面の外にある物体を捨てます。
GPUの描画パイプライン：頂点シェーダー、プリミティブアセンブリ、クリッピング、除算とビューポート変換、カリング、ラスタライズ、フラグメントシェーダー、テスト（シザー・ステンシル・深度）、ブレンディング、フレームバッファ。
ダブルバッファは描きかけのフレームを隠し、垂直同期は垂直帰線期間に入れ替えてテアリングを防ぎます。
DDAは傾きずつ進めて丸め、ブレゼンハム法は整数の判定変数でEとNEを選び、中点アルゴリズムは同じ事を円の八分円に対して行います。
スキャンライン法は辺との交点を並べ替えて組ごとに塗り、GPUはエッジ関数でピクセルの中心を判定し、共有する辺ではトップレフトルールを使い、重心座標で補間します。

6.11 用語

English	日本語
viewing pipeline	ビューイングパイプライン
drawing (rendering) pipeline	描画パイプライン
modeling transform	モデリング変換
view transform	ビュー変換（視野変換）
projection transform	投影変換
camera (view) coordinates	カメラ座標系（視点座標系）
clip coordinates	クリップ座標系
perspective division	透視除算
normalized device coordinates (NDC)	正規化デバイス座標系
viewport transform	ビューポート変換
screen (device) coordinates	スクリーン座標系（デバイス座標系）
clipping	クリッピング
outcode	領域コード（アウトコード）
culling	カリング
back-face culling	背面除去（バックフェースカリング）
view-frustum culling	視錐台カリング
bounding volume	バウンディングボリューム
vertex processing	頂点処理
primitive assembly	プリミティブアセンブリ
rasterization, scan conversion	ラスタライズ、スキャン変換
fragment	フラグメント
depth test	深度テスト（Zテスト）
stencil test	ステンシルテスト
blending	ブレンディング
frame buffer	フレームバッファ
double buffering	ダブルバッファ
vertical sync (v-sync)	垂直同期
tearing	テアリング
fixed function	固定機能
programmable shader	プログラマブルシェーダー
Bresenham's algorithm	ブレゼンハムのアルゴリズム
midpoint algorithm	中点アルゴリズム
scanline algorithm	スキャンライン法
edge table, active edge list	エッジテーブル、アクティブエッジリスト
even-odd rule	偶奇規則
nonzero winding rule	非ゼロ回転数規則
edge function	エッジ関数
top-left rule	トップレフトルール
barycentric coordinates	重心座標
perspective-correct interpolation	パースペクティブコレクト補間

6.12 課題

★ モデリング座標の頂点 $(10, 2, -1)$ を、6.2節のパイプライン（同じM、V、P、800×600のウィンドウ）に通して下さい。ワールド座標、カメラ座標、クリップ座標、クリップ判定、NDC、ピクセル、深度バッファの値を求めます。（確認：カメラ座標のzは−1と−11の間になる筈です。）
★ ウィンドウ $[0, 8] \times [0, 6]$ で、 $(-2, 7)$ と $(6, -1)$ の領域コードを求め、其の間の線分をコーエン・サザーランド法でクリップして下さい。途中の全ての点とコードを書き出します。次に、 $(-3, 7)$ から $(2, 9)$ への線分が見えない事を、領域コードだけで示して下さい。
★★ 三角形 $(2, 1)$ 、 $(10, 3)$ 、 $(2, 7)$ をウィンドウ $[0, 8] \times [0, 6]$ に対してサザーランド・ホッジマン法で左・右・下・上の順にクリップし、各段階の後の頂点リストを書いて下さい。結果の頂点は幾つですか？
★★ 三角形 $A(0, 0)$ 、 $B(6, 0)$ 、 $C(0, 6)$ （yは上向き）について、ピクセルの中心 $(1.5, 2.5)$ が内側かをエッジ関数で判定し、重心座標を求め、A、B、Cの深度が0.2、0.8、0.5の時の深度を補間して下さい。次に頂点をA、C、Bの順に並べると符号はどうなり、其れは背面除去にとって何を意味しますか？
★★★ カメラ空間の線分が $(-1, 0, -1)$ から $(3, 0, -3)$ まであり、 $x_{\text{ndc}} = \frac{x}{-z}$ で投影されます。端点が $-1$ と $1$ に着地する事を示し、画面の中点 $x_{\text{ndc}} = 0$ に着地する3次元の点を求めて下さい。其れは3次元の線分の何割の所にあり、画面空間の重みでテクスチャ座標を補間する事について何が分かりますか？

選択問題

問1 ★ 次のうち、ビューイングパイプラインの段階を正しい順番に並べた物はどれか。


あ	モデリング変換 → ビュー変換 → クリッピング → ビューポート変換 → 投影変換 → 透視除算
い	モデリング変換 → 投影変換 → ビュー変換 → クリッピング → 透視除算 → ビューポート変換
う	モデリング変換 → ビュー変換 → 投影変換 → 透視除算 → クリッピング → ビューポート変換
え	ビュー変換 → モデリング変換 → 投影変換 → クリッピング → ビューポート変換 → 透視除算
お	モデリング変換 → ビュー変換 → 投影変換 → クリッピング → 透視除算 → ビューポート変換

問2 ★ コーエン・サザーランドの線分クリッピングでは、線分の各端点に4ビットの領域コードを付ける。次のうち、正しい物はどれか。


あ	2つのコードのビットごとのORが0000でなければ、線分全体がウィンドウの外にある。
い	2つのコードのビットごとのANDが0000なら、線分の少なくとも一部は必ずウィンドウの内側にある。
う	領域コードは、ウィンドウの周りの9つの領域其々に1ビットずつを持つ。
え	2つのコードのビットごとのANDが0000でなければ、線分全体がウィンドウの外にあり、交点を計算せずに棄却出来る。
お	一方の端点のコードが0000なら、其の線分はクリップする必要が無い。

問3 ★★ $(0, 0)$ から $(9, 5)$ への線分をブレゼンハムのアルゴリズム（判定変数が0以上なら上のピクセルに進む）で描く。判定変数の初期値 $p_0$ と、2番目に描かれるピクセルの組として正しい物はどれか。


あ	$p_0 = 19$ 、2番目のピクセル $(1, 1)$
い	$p_0 = 1$ 、2番目のピクセル $(1, 1)$
う	$p_0 = -1$ 、2番目のピクセル $(1, 0)$
え	$p_0 = 1$ 、2番目のピクセル $(1, 0)$
お	$p_0 = -8$ 、2番目のピクセル $(1, 0)$

6.13 実践課題

1つの三角形を、方眼紙の上で此の章の全てに通します。
投影、クリッピング、カリング、塗り潰し、ブレゼンハムの辺、そして補間です。
少なくとも20×16マスの方眼紙、定規、鉛筆、2色のペン、電卓を用意して下さい。

カメラ空間の頂点は $A(-3, -3, -4)$ 、 $B(9, -4.5, -6)$ 、 $C(0, 3, -8)$ です。
投影は縦の視野角90°、アスペクト比1、 $n = 1$ 、 $f = 9$ のOpenGLの透視投影行列（要素は1、1、−1.25、−2.25、−1）で、ウィンドウは原点が左下でyが上向きの16×16ピクセル、 $x_w = 8(x_{\text{ndc}} + 1)$ 、 $y_w = 8(y_{\text{ndc}} + 1)$ です。

投影する。 A、B、Cのクリップ座標を計算し、其々にクリップ判定 $-w \le x, y, z \le w$ を適用して下さい。どの頂点が、どの平面の外にありますか？
割って写す。 3つの頂点全て（外側の頂点も含みます。wが正なので除算は安全です）のNDCとウィンドウ座標を計算して下さい。3つのNDCの深度も書いておきます。
カリングする。 ウィンドウ座標で $E_{AB}(C)$ を計算して下さい。三角形は反時計回り、つまりOpenGLの既定値で表向きですか？
クリップする。 方眼紙に16×16のウィンドウと三角形全体を描きます（三角形は片側にはみ出します）。3つのwが全て正なので、投影した三角形をウィンドウの辺でクリップしても、クリップ空間でクリップした場合と同じ多角形になります。サザーランド・ホッジマン法でクリップし、結果の多角形を書き出して下さい。
塗り潰す。 各スキャンライン $y = j + 0.5$ で、クリップした多角形の辺との交点を計算し、組の間に中心があるピクセルを塗って下さい（偶奇規則）。塗ったピクセルを数え、多角形の面積を座標の公式（靴紐公式）で計算します。2つの数は近い筈です。
辺を描く。 2色目のペンで、AからCへの辺をブレゼンハムのアルゴリズムで描いて下さい。急な線分なのでxとyの役割を入れ替え、yを1ずつ進め、xが其の儘か右に動くかを判定します。全ての判定変数を書き、塗った領域の左の境界のピクセルと比べて下さい。
補間する。 ピクセル $(9, 6)$ （中心 $(9.5, 6.5)$ ）について、ウィンドウ座標でのクリップ前の三角形ABCに対する重心座標を計算して下さい。Aを赤、Bを緑、Cを青として其のピクセルの色を求め、次にNDCの深度を補間して深度バッファの値 $\frac{z_{\text{ndc}} + 1}{2}$ に変換します。

自分で確認する方法：クリップした多角形の全ての頂点はウィンドウの内側か境界上にあります。
重心座標は全て正で、合計は丁度1です。
補間した深度は、頂点の深度の最小値と最大値の間にあります。
手順5のピクセル数と面積の差は数ピクセル程度です。
手順4の追加の確認として、クリップ空間で辺ABが平面 $x = w$ と交わる所（ $x - w$ の符号が変わるパラメータt）を求め、其の点を其のwで割り、画面空間でのクリップと同じウィンドウ上の位置に着地する事を確かめて下さい。
画面上とクリップ空間でのtの値は違うのに、です。

コメント（0）

まだコメントはありません。