10. 隠面消去とシェーディング

第6章では、三角形をピクセル（画素）まで運びました。
変換し、クリップし、背面を除去し、残った物をラスタライズしました。
でも、2つの問いが残っています。
2つの三角形が同じピクセルに重なった時、どちらが見えるのか？
そして、其のピクセルは何色になるのか？
此の章は其の両方に答えます。

1つ目の問いは隠面消去、つまり他の面に隠れている面を見つける事です。
2つ目はシェーディング、つまり当たっている光、物体の材質、見る方向から、面がどれだけ明るく見えるかを計算する事です。
此の2つが揃って初めて、色の付いた三角形の集まりが立体に見える絵になります。
ゲームエンジンのZバッファとピクセルごとのライティングから、第12章のレイトレーシングで作る映画の1フレームまで、全てのレンダラーが両方を行っています。

検定対策としては、此の章は分野4（レンダリング）の2つのシラバス項目、隠面消去とシェーディングを扱います。
つまり古典的な可視判定のアルゴリズム（奥行きソート法、Zバッファ法、スキャンライン法、レイキャスティング法、BSP法、領域分割法）、光源、反射モデル（環境光、拡散反射、鏡面反射、フォンとブリン・フォン）、シェーディング手法（フラット、グーロー、フォン）、そして半透明です。
影とテクスチャマッピングは第11章、物理ベースの反射（BRDF）、レイトレーシング、大域照明は第12章で扱います。

必要な数学は、線型代数シリーズ第4章の内積と反射の式、線型代数シリーズ第3章の正規化、そして第6章の6.9節のエッジ関数と重心座標です。

10.1 可視性の問題

どんな場面でも見てみて下さい。
机の上のカップは机の一部を隠し、カップの取っ手はカップの一部を隠し、カップの裏側は自分の表側に隠れています。
第3章では、重なり（遮蔽）が最も強い奥行き手がかりの1つだと学びました。
何かが他の物を覆っていれば、其れが手前にあります。
此れを間違えるレンダラーは、レントゲン写真の様な絵や、もっと悪い事に遠くの物が近くの物の上に描かれた絵を作ってしまいます。

此の問題には2つの形があります：

• 隠線消去：ワイヤーフレームの図で、面に隠れる辺の部分を取り除きます。ペンプロッターで描くCADの図の為に最初に解かれた問題です（凸な物体に対するロバーツの方法が1963年、アペルの「定量的不可視性」が1967年）。
• 隠面消去（可視面判定とも言います）：陰影の付いた絵で、ピクセルごとにどの面が見えるかを決めます。

今では殆ど全てがシェーディングされるので、此の章の残りは面の話です。
隠線の図も、面を背景色で塗り、其の上に辺を描けば、どの隠面消去法でも作れます。

物体空間と画像空間

アルゴリズムは2つの系統に分かれます：

• 物体空間法（オブジェクト空間法）は形状其の物を扱います。ポリゴン同士を比べて、どちらが手前かを調べます。結果は正確で解像度に依存しませんが、$n$個のポリゴンでは最大$\frac{n(n-1)}{2}$組を比べる事になります。
• 画像空間法はピクセルごとに働きます。各ピクセルで最も近い面を探します。答えの精度はピクセルの格子までで、コストは（ポリゴンの数）×（其々が覆うピクセル数）に比例し、実際には$n^2$よりずっとゆっくり増えます。

数の感覚を掴む為に：10万個のポリゴンでは約$\frac{100000\cdot 99999}{2}\approx 5\cdot {10}^9$組になりますが、1920×1080の画像のピクセルは約207万個しかありません。
両方を混ぜた方法もあります。
画家のアルゴリズムは物体空間で並べ替え、残りはフレームバッファに任せます。

背面除去だけでは足りない

6.4節では背面除去を学びました。
法線が視点から離れる向きの面、つまり$𝐧\cdot (𝐞-𝐩)\le 0$の面を全て捨てます。
立方体や球の様な凸で閉じた物体が1つだけなら、此れだけで完全な隠面消去になります。
表の面は全て見え、裏の面は全て隠れるからです。
物体が凹んでいたり（カップ、体の前にあるキャラクターの腕）、物体が2つ以上あったりすると、表の面が他の表の面を隠す事があり、以下の方法の何れかが必要になります。
其れでも背面除去は、閉じたメッシュの面のおよそ半分を取り除く安価な最初の一歩として、どの方法とも一緒に使われます。

10.2 奥行きソート法と画家のアルゴリズム

考え方

風景を描く画家は、空から描き始め、次に山、次に木、最後に手前の人物を描きます。
各層が其の後ろにある物を覆います。
画家のアルゴリズムも同じ事をします。
ポリゴンを奥行きで並べ替え、一番遠い物から一番近い物へ、フレームバッファを単純に上書きしながら描きます。
近いポリゴンが最後に描かれるので、其れが一番上に残ります。
奥行きのメモリは全く要りません。

一番単純な形では、各ポリゴンを1つの数（例えば一番遠い頂点や中心）で並べ替えます。
此れは簡単に失敗します。
細長い床のポリゴンは、一番遠い点が其の上に立つ箱より奥にあっても、手前の端は箱より手前にあり得るからです。
其の為、完全な奥行きソート法（ニューウェル、ニューウェル、サンチャ、1972年）は、まず一番遠い奥行きで並べ替え、次に奥行きの範囲が重なる全ての組を調べます。
ポリゴンP（今はQより先に描かれる）は、次の判定の何れかが成功すれば、Qより先の儘で構いません（安い判定から高い判定の順）：

1. 画面上でのPとQのxの範囲が重ならない。
2. yの範囲が重ならない。
3. Pが完全に、Qの平面の（視点から見て）向こう側にある。
4. Qが完全に、Pの平面の手前側にある。
5. 画面上でのPとQの投影が重ならない。

5つ全てが失敗すると、PがQの一部を隠すかもしれないので、アルゴリズムは2つを入れ替えてもう一度判定します。

計算例：平面による判定

判定3と4は、ポリゴンの平面の方程式を使います。
カメラ空間（視点が原点で、−zの方向を見る）で、頂点が$(-2,-1,-4)$、$(2,-1,-8)$、$(0,2,-6)$のポリゴンQを考えます。
3つとも$x+z=-6$を満たすので、Qは次の平面上にあります：

$f_Q$は平面の片側で正、反対側で負になります。
視点では$f_Q(0,0,0)=6>0$なので、正は「視点の側」という意味です。
次に、頂点が$(1,0,-5)$、$(3,1,-5)$、$(2,-1,-6)$のポリゴンPを調べます：

3つとも正です。
Pは完全にQの平面の視点側にあるので、QがPを隠す事は決して無く、安全な順番は「Qが先、Pが後」です。
奥行きの範囲は重なっている事に注意して下さい（Qのzは−8から−4、Pは−6から−5）。
其の為、1つの数で並べ替えるだけでは、此れを安全に決める事は出来ませんでした。

破綻する所：循環と貫通

ポリゴンを丸ごと並べるどんな順番でも解けない配置が2つあります：

• 循環する重なり：PがQの上、QがRの上、そしてRがPの上にあります。どの棒を最後に描いても、其の棒が他の2本を完全に覆ってしまい、間違いになります。
• 貫通：QがPを突き抜けています。交線より上ではQが手前、下ではPが手前です。「Pが先」も「Qが先」も正しくありません。

奥行きソート法は此れらの場合を検出し（2回目の入れ替えが起きるポリゴンは循環の一部です）、片方のポリゴンをもう片方の平面で分割して、各部分を並べられる様にします。
此れで解けますが、ポリゴンの数が増え、判定にも時間が掛かります。

実際の使われ方

画家のアルゴリズムは、並べ替えが安いか避けられない所で今でも現役です：

• 2Dゲーム、UIツールキット、SVGやPDFは決まったレイヤーの順に描きます。此れは正に奥から手前への塗り重ねです。
• 3Dエンジンは半透明の物体を奥から手前へ並べて描きます（10.12節）。Zバッファでは扱えないからです。

10.3 Zバッファ法

考え方

Zバッファ法は並べ替えを完全に諦め、ピクセルごとに別々に可視性を決めます。
カラーバッファの隣に同じ大きさの2枚目の画像、深度バッファ又はZバッファを持ち、各ピクセルに其れまでに描かれた最も近い面の深度を保存します。
此の考えは普通エド・キャットマル（1974年）の物とされますが、ヴォルフガング・シュトラーサーも同じ年の博士論文で同じ考えを述べています。

アルゴリズム：

1. カラーバッファを背景色で、深度バッファを最も遠い深度（深度の範囲が0から1なら1.0）でクリアします。
2. 全てのポリゴンを、どんな順番でも良いのでラスタライズします。覆う各ピクセルで、其のピクセルでのポリゴンの深度$z$を計算します。
3. 深度テスト：$z$が保存されている深度より小さい（近い）なら、ポリゴンの色をカラーバッファに、$z$を深度バッファに書き込みます。そうでなければ何もしません。

全てのポリゴンを描き終わると、各ピクセルには最も近い面の色が残っています。
此れが6.5節のGPUパイプラインの深度テストです。
OpenGLの既定の比較GL_LESSは、正に「小さい方が近い」です。

深度の計算

ピクセルでの深度は、6.9節の重心座標による補間で頂点の深度から求めます：$z={\lambda }_A{z}_A+{\lambda }_B{z}_B+{\lambda }_C{z}_C$。
透視除算の後の深度は画面上の位置のアフィン関数なので（其の為に画面上で線型に補間して良いのでした。6.9節を参照）、三角形の上では平面になります：

其の為、計算は安く済みます。
右に1ピクセル進むと定数$b$を足し、1行上がると$c$を足すだけです。

計算例：互いを貫通する2つの三角形

10×8ピクセルの画面に2つの三角形があります（ピクセルの中心は$(i+0.5,j+0.5)$、yは上向きで、第6章と同じです）：

• 赤：頂点$(0,0)$、$(10,1)$、$(2,8)$、深度0.1、0.9、0.26。深度の平面は$z_R=0.1+0.08x$で、右に行く程奥へ傾いています。
• 青：頂点$(10,0)$、$(10,8)$、$(0,6)$、深度0.3、0.94、0.78。深度の平面は$z_B=0.3+0.08y$で、上に行く程奥へ傾いています。

頂点で平面を確かめられます：$z_R(10,1)=0.1+0.8=0.9$、$z_B(0,6)=0.3+0.48=0.78$。
2つの平面が等しくなるのは$0.1+0.08x=0.3+0.08y$、つまり直線$x=y+2.5$の上です。
其の左では赤が、右では青が手前です。

赤を先に、次に青を描き、2つのピクセルを追い掛けてみましょう。

ピクセル(6, 2)、中心(6.5, 2.5)。
クリアの後、其の深度は1です。
赤が$z_R=0.1+0.08\cdot 6.5=0.62$で覆います。
なので、ピクセルは赤、深度0.62になります。
青が$z_B=0.3+0.08\cdot 2.5=0.5$で覆います。
なので、青、深度0.5になります。

ピクセル(3, 5)、中心(3.5, 5.5)。
赤：なので、赤、深度0.38になります。
青：$z_B=0.3+0.08\cdot 5.5=0.74$は0.38より小さくないので、深度テストに失敗し、ピクセルは赤の儘です。

今度は逆の順番、青を先に描きます。
ピクセル(6, 2)：青が0.5を書き、赤の0.62はテストに失敗します。
青です。
ピクセル(3, 5)：青が0.74を書き、赤の0.38は合格します。
赤です。
結果は同じです。
最終的な深度バッファの値と共に、画面全体を示します：

黄色の枠は、2つの三角形が競合するピクセルです。
其の領域の中の赤と青の境界は、破線$x=y+2.5$に沿った階段になっています。
画家のアルゴリズムを破綻させた貫通を、Zバッファは分割を一切せずに、1ピクセルずつ解決しました。

同じ事を、6.9節のエッジ関数と線型代数シリーズのlinalg.hhヘッダーを使ってC++で書きます。
シーンを両方の順番で描き、フレームバッファを表示します：

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

struct Vertex {
  Vec2 p;  // screen position in pixels (y up)
  float z; // depth: 0 = near plane, 1 = far plane
};

const int W = 10, H = 8;
float depthBuf[H][W]; // the z-buffer
char colorBuf[H][W];  // the frame buffer (one letter per pixel)

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);
}

void clear() {
  for (int y = 0; y < H; ++y) {
    for (int x = 0; x < W; ++x) {
      depthBuf[y][x] = 1.0f; // as far away as possible
      colorBuf[y][x] = '.';  // background
    }
  }
}

// a, b, c counter-clockwise. (The top-left rule of chapter 6 is left out to keep it
// short; it only matters for edges that two triangles share.)
void drawTriangle(Vertex a, Vertex b, Vertex c, char name) {
  float area2 = edgeFunction(a.p, b.p, c.p);
  for (int y = 0; y < H; ++y) {
    for (int x = 0; x < W; ++x) {
      Vec2 p{x + 0.5f, y + 0.5f};
      float la = edgeFunction(b.p, c.p, p) / area2;
      float lb = edgeFunction(c.p, a.p, p) / area2;
      float lc = edgeFunction(a.p, b.p, p) / area2;
      if (la < 0 || lb < 0 || lc < 0) continue; // outside the triangle
      float z = la * a.z + lb * b.z + lc * c.z;  // interpolated depth
      if (z < depthBuf[y][x]) {                  // the depth test
        depthBuf[y][x] = z;
        colorBuf[y][x] = name;
      }
    }
  }
}

void print() {
  for (int y = H - 1; y >= 0; --y) { // top row first
    printf("%.*s\n", W, colorBuf[y]);
  }
}

int main() {
  Vertex r0{{0, 0}, 0.1f}, r1{{10, 1}, 0.9f}, r2{{2, 8}, 0.26f};
  Vertex b0{{10, 0}, 0.3f}, b1{{10, 8}, 0.94f}, b2{{0, 6}, 0.78f};

  clear();
  drawTriangle(r0, r1, r2, 'R');
  drawTriangle(b0, b1, b2, 'B');
  print();
  printf("pixel (6, 2): %c, depth %.2f\n\n", colorBuf[2][6], depthBuf[2][6]);

  clear();
  drawTriangle(b0, b1, b2, 'B'); // the other order
  drawTriangle(r0, r1, r2, 'R');
  print();
  printf("pixel (6, 2): %c, depth %.2f\n", colorBuf[2][6], depthBuf[2][6]);
  return 0;
}

..R....BBB
..RRBBBBBB
.RRRRBBBBB
.RRRRRBBBB
.RRRRRBBBB
.RRRRRBBBB
RRRRRRRBBB
RRRRR....B
pixel (6, 2): B, depth 0.50

..R....BBB
..RRBBBBBB
.RRRRBBBBB
.RRRRRBBBB
.RRRRRBBBB
.RRRRRBBBB
RRRRRRRBBB
RRRRR....B
pixel (6, 2): B, depth 0.50

メモリ

深度バッファは、シーンのポリゴンが幾つあっても、ピクセルごとに1つの値で足ります。
1920×1080で1ピクセル24ビット（3バイト）なら$1920\cdot 1080\cdot 3=6220800$バイト、約5.9 MiBです。
32ビット（32ビット浮動小数点、又は第6章の様に24ビットの深度と8ビットのステンシル）なら8,294,400バイト、約7.9 MiBです。
Zバッファが発明された頃、此れだけのメモリは大きな負担でしたが、今では何でもありません。

精度とZファイティング

第5章では、透視投影の後に保存される深度が距離に対して線型ではない事を見ました。
ニア平面$n$、ファー平面$f$、カメラの前方の距離$d$に対して、0から1の深度バッファに入る値は次の通りです：

（第5章のOpenGLの$z_{\text{ndc}}$に対する$\frac{z_{\text{ndc}}+1}{2}$で、Vulkanの投影でも同じ値になります。）
其の傾きは$\frac{dD}{dd}=\frac{fn}{(f-n)d^2}$なので、保存される値の1段$\mathrm{\Delta }D$は、距離にしておよそ次の幅に当たります：

此れは距離の2乗で大きくなります。
24ビット整数の深度バッファでは$\mathrm{\Delta }D=2^{-24}\approx 5.96\cdot {10}^{-8}$です。
$n=0.1$、$f=1000$（メートル）では：

100 mでは：$5.96\cdot {10}^{-8}\cdot \frac{999.9\cdot {100}^2}{1000\cdot 0.1}=5.96\cdot {10}^{-8}\cdot 99990\approx 0.006$ mです。
$\mathrm{\Delta }d$より近い2つの面は同じ深度値になり、どちらがテストに勝つかがピクセルごと、フレームごとに変わり、互いにちらつきます。
此れがZファイティングで、遠くの道路の上に描かれた路面標示やデカールでよく見られます。
表の2列目は一番安い対策を示しています。
ニア平面を0.1から1に動かすだけで、全ての段が10倍細かくなります。
其の他の対策（「リバースZ」付きの32ビット浮動小数点バッファや、デカール用の小さな深度オフセット）は第2部で扱います。

長所と短所

長所：

• 順番を問わない。 並べ替えは一切不要で、ポリゴンはプログラムが送った順番の儘流し込めます。
• 形を問わない。 貫通するポリゴンや循環して重なるポリゴンもピクセルごとに処理され、曲面など、ピクセルごとの深度付きでラスタライズ出来る物なら何でも扱えます。
• 単純で、メモリが一定。 其の為、全てのGPUに組み込まれています。

短所：

• 半透明。 バッファはピクセルごとに1つの面しか覚えません。半透明の面は後ろにある物と混ぜる必要がありますが、後ろの物が後から描かれると、深度テストに失敗して消えてしまいます（10.12節）。
• エイリアシング。 可視性をピクセルごとに1点で決めるので、辺や交線は図の階段の様にギザギザになります。MSAAはサンプルごとに深度を持って此れを直します（第6章と第2部）。
• 精度。 上で計算した通りです。
• オーバードロー。 最も近い面が来るまでに、1つのピクセルが何度もシェーディングされる事があります。GPUはアーリーZ（フラグメントシェーダーの前の深度テスト、第6章）で此れを減らし、エンジンはシーンを大まかに手前から奥へ描いたり、まず深度だけを描いて（「深度プリパス」）から見える所だけをシェーディングしたりします。

深度テストはOpenGLシリーズの第15章で自分で設定します。

10.4 スキャンライン法

隠面消去のスキャンライン法は、6.8節の多角形の塗り潰しを、多数のポリゴンに同時に広げた物です。
1960年代の終わりから1970年頃（ワイリー、ロムニー、エヴァンス、アーダール、ブークナイト、ワトキンス）、画面全体のZバッファの為のメモリが高価過ぎた時代に開発されました。

1行（スキャンライン）ずつ処理します：

1. 第6章のエッジテーブルとアクティブエッジリストを全てのポリゴンについてまとめて持ち、更に各ポリゴンの平面の方程式と色を持つポリゴンテーブルと、現在のスキャンラインを横切るポリゴンのアクティブポリゴンリストを持ちます。
2. 各スキャンラインで、辺との交点をxで並べ替えます。隣り合う2つの交点の間では、存在するポリゴンの組が変わりません。スキャンラインの此の一区間をスパンと呼びます。
3. 各スパンで見えるポリゴンを決めます。ポリゴンが1つだけなら其れです。複数あれば深度を比べます。スパンの両端で同じポリゴンが手前なら、スパン全体で其れが手前です（スキャンラインに沿って深度は線型だからです）。順番が入れ替わるなら、ポリゴンはスパンの中で交わっているので、交差する点でスパンを分けます。
4. 各スパンを見えるポリゴンで塗ります。

深度の比較はピクセルごとではなくスパンごとに1回で済み、アクティブなリストはスキャンラインごとに少ししか変わらない（スキャンラインの一貫性）ので、此の方法は速く、深度のメモリも高々1スキャンライン分で済みます。

計算例

10.3節の2つの三角形に、スキャンライン$y=3.5$（ピクセルの行3）を通してみましょう。
辺とスキャンラインの交点：

• 赤の左の辺、$(0,0)$から$(2,8)$：$x=3.5\cdot \frac{2}{8}=0.875$。
• 赤の右の辺、$(10,1)$から$(2,8)$：$x=10-8\cdot \frac{3.5-1}{7}=10-\frac{20}{7}\approx 7.143$。
• 青の下の辺、$(0,6)$から$(10,0)$：$x=\frac{6-3.5}{0.6}\approx 4.167$。
• 青の右の辺$x=10$。

並べ替えると0.875、4.167、7.143、10で、3つのスパンが出来ます：

• $[0.875,4.167)$：赤だけ。赤です。
• $[4.167,7.143)$：両方。スキャンラインに沿った赤の深度は$0.1+0.08x$、青は定数$0.3+0.08\cdot 3.5=0.58$です。左端で赤は0.433で0.58より手前、右端で赤は0.671で奥です。順番が入れ替わるので、$0.1+0.08x=0.58$となる$x=6$で分けます。$[4.167,6)$は赤、$[6,7.143)$は青です。
• $[7.143,10)$：青だけ。青です。

ピクセルの中心1.5から5.5は赤のスパンに、6.5から9.5は青のスパンに入ります。
Zバッファの結果の行3、.RRRRRBBBBと同じです。
同じ絵ですが、此の行で深度を比べたのは、両方の三角形がある1つのスパンの両端だけです。
三角形ごと、覆うピクセルごとに比べる必要はありませんでした。

実際の使われ方

スキャンライン法は、メモリが貴重だった頃の初期のハードウェアやオフラインレンダラーの標準で、其の考え方（スパン、一貫性、差分による更新）は今も全てのラスタライザーに生きています。
弱点は複雑さです。
辺とポリゴンの管理は、Zバッファの単純なピクセルごとの判定に比べて、並列ハードウェアに組み込むのがずっと難しいのです。

10.5 レイキャスティング法

レイキャスティング法は問いを逆にします。
ポリゴンをピクセルに投影する代わりに、各ピクセルから出発して、其処を通して視点に何が見えるかを問います。
ピクセルごとに、視点から投影面上の其のピクセルの位置を通るレイ（半直線）を飛ばし、全ての物体との交点を求め、視点の前方で最も近い交点を採ります。
アーサー・アペルが1968年に述べました。

レイは$𝐩(t)=𝐨+t𝐝$で、$𝐨$は始点（視点）、$𝐝$は方向、$t>0$です。
法線$𝐧$、方程式$𝐧\cdot 𝐩=c$の平面にレイを代入すると、交点のパラメータが得られます：

（$𝐧\cdot 𝐝=0$ならレイは平面に平行で、交わりません。）
ポリゴンの場合は、更に交点がポリゴンの内側にあるかを、例えば第6章のエッジ関数や重心座標で確かめます。

計算例

視点は原点にあり、−zの方向を見ています。
シーンには床（平面$y=-2$）と壁（平面$z=-4$、床から$y=2.2$まで）があります。
或るピクセルを通るレイの方向は$𝐝=(0,-0.25,-1)$です（ピクセルは距離1の投影面上、中心の少し下にあります）。

• 壁：$𝐧=(0,0,1)$、$c=-4$。$t=\frac{-4-0}{-1}=4$、交点は$(0,-1,-4)$。高さ−1は−2と2.2の間なので、壁の上です。
• 床：$𝐧=(0,1,0)$、$c=-2$。$t=\frac{-2-0}{-0.25}=8$、交点は$(0,-2,-8)$で、壁の向こうの床の上です。

最も近い交点は$t=4$なので、此のピクセルには壁が映ります。
方向$𝐝=(0,-1,-1)$の2本目のレイは、$t=\frac{-2}{-1}=2$で床の点$(0,-2,-2)$に当たります。
壁の平面には$t=4$、高さ−4で当たりますが、此れは床より下、壁の外なので外れです。
此のピクセルには床が映ります。

実際の使われ方

レイキャスティング法は画像空間法で、並べ替えが要らず、レイとの交点が求まる面なら何でも（ポリゴンだけでなく球、陰関数曲面、ボリュームも）扱え、深度バッファも要りません。
問題はコストです。
素朴にやると全てのレイを全ての物体と判定するので、100万個の三角形のシーンを1920×1080で描くと、約$2.07\cdot {10}^6\cdot {10}^6\approx 2\cdot {10}^{12}$回の判定が必要です。
高速化データ構造（階層バウンディングボリューム、格子、kd木）を使うと、レイごとのコストは大体対数程度まで下がります。
其れらは第12章で説明します。
レイキャスティングはレイトレーシングの最初の一歩でもあり、レイトレーシングは影、反射、屈折の為にレイを再帰的に飛ばし続けます（第12章）。
又、3Dエディターの「ピッキング」の仕組みでもあります。
マウスカーソルの下のレイが、どの物体がクリックされたかを教えてくれます。

10.6 BSP法

考え方

画家のアルゴリズムには奥から手前への順番が必要ですが、毎フレーム並べ替えるのは高価で、不可能な場合もあります。
BSP木（binary space partitioning、二分空間分割。BSP法、フュークス、ケデム、ネイラー、1980年）は、どんな視点の位置に対しても、並べ替え無しで正しい奥から手前への順番を読み出せる様にシーンを保存します。

鍵になる事実はこうです。
或るポリゴンの平面を考えます。
其の平面の視点と同じ側にある物は其のポリゴンを隠し得ますが、反対側にある物は隠せません。
従って、遠い側を先に、次に其のポリゴン、次に近い側を描けば、其のポリゴンに関しては順番が正しくなります。
各側の中でも同じ考えを再帰的に使えば、全体の順番が得られます。

木の構築（描画の前に1回だけ）：

1. ポリゴンを1つ選んで根にします。其の平面が空間を表側（法線が向く側）と裏側に分けます。
2. 其の他の全てのポリゴンを表のリストか裏のリストに入れます。平面を跨ぐポリゴンは2つに分割し、其々のリストに入れます。
3. 表のリストから表の部分木を、裏のリストから裏の部分木を、再帰的に作ります。

描画（毎フレーム）は各ノードで：

• 視点がノードの表側にあれば：裏の部分木、ノードのポリゴン、表の部分木の順に描きます。
• 視点が裏側にあれば：表の部分木、ポリゴン、裏の部分木の順に描きます。

2次元での計算例

2次元では「ポリゴン」は線分、「平面」は其の直線になります。
上から見た壁の間取り図と同じです。
4つの壁があり、其々の表側は進行方向の左で、小さな矢印で示しています：

• $a$：$(2,4)$から$(8,4)$、表は上。
• $b$：$(3,7)$から$(6,7)$、表は上。
• $c$：$(10,2)$から$(10,6)$、表は左。
• $d$：$(5,1)$から$(2,2)$、表は左下。

点$𝐩$が$𝐬$から$𝐞$への線分のどちら側にあるかは、6.9節のエッジ関数$E(𝐩)=(e_x-s_x)(p_y-s_y)-(e_y-s_y)(p_x-s_x)$で決めます。
正なら表（左）です。

$a$を根にして構築します。
$a$では$E(𝐩)=6(p_y-4)$なので、「表」は単に$y>4$という意味です。
$b$は$y=7$なので表です。
$d$は$y=1$と2なので裏です。
$c$は$y=2$（裏）から$y=6$（表）へ伸び、$a$の直線を跨ぐので、$(10,4)$で$(10,4)$から$(10,6)$への$c_1$（表）と、$(10,2)$から$(10,4)$への$c_2$（裏）に分割します。
表のリストは$b,c_1$です。
$b$を其の根にすると、$c_1$（$y=7$より下）は$b$の裏に入ります。
裏のリストは$c_2,d$です。
$c_2$を其の根にすると（$E(𝐩)=2(10-p_x)$で、表は）、$d$は$c_2$の表に入ります。

視点$E_1=(5,9)$で辿ります：

• $a$で：$E_1$は$y=9>4$なので表。従って、裏の部分木、$a$、表の部分木の順です。
• 裏の部分木の$c_2$で：$E_1$はなので表。従って、$c_2$の裏（空）、$c_2$、$c_2$の表つまり$d$の順です。
• 次に$a$。
• 表の部分木の$b$で：$y=9>7$なので表。従って、$b$の裏つまり$c_1$、次に$b$、最後に空の表です。

描画順は$c_2,d,a,c_1,b$です。
図と照らし合わせてみましょう。
$E_1$は上から見下ろしていて、一番近い$b$が最後に描かれ、$a$の下にある$d$は、其れを覆い得る$a$より先に描かれます。

$E_2=(12,3)$では、$a$（今度は裏、）、$b$（裏）、$c_2$（$x=12>10$で裏）の全ての判定が反転し、順番は$b,c_1,a,d,c_2$になります。
木は両方の視点で同じです。
変わるのは辿り方だけです。

実際の使われ方

BSP木は静的なシーンに向いています。
木の構築は高価ですが（根の選び方で分割の数が決まります）、辿るのはノードごとに1回の側の判定だけの速い線型の処理です。
其の為、id SoftwareのDoom（1993年）やQuakeは、他の工夫と組み合わせてレベルにBSP木を使い、レベルエディターには別に時間の掛かる「BSPの構築」の段階がありました。
奥から手前ではなく手前から奥へ辿るのも同じ位簡単で、Zバッファと組み合わせる時（近い物を先に描けば、遠い物は早く深度テストに落ちる）やカリングに便利です。
動く物体は静的な木に入らないので、其の上にZバッファで描きます。

10.7 領域分割法とAバッファ

ウォーノックのアルゴリズム

領域分割法、ジョン・ウォーノックのアルゴリズム（1969年）は、分割統治による画像空間法です。
画面の或る領域（最初は画面全体）を取り、各ポリゴンが其の領域とどんな関係にあるかを調べます：

• 取り囲む：ポリゴンが領域全体を覆う。
• 交差する：ポリゴンが領域の一部を覆い、外にはみ出す。
• 内包される：ポリゴンが完全に領域の中にある。
• 分離：ポリゴンが領域に触れない。

次の何れかが成り立てば、領域は単純で、其の儘描けます：

1. どのポリゴンも触れない：背景で塗る。
2. 丁度1つのポリゴンだけが触れる（交差又は内包）：背景で塗り、其のポリゴンの部分を描く。
3. 1つのポリゴンが領域を取り囲み、領域内の他の全てのポリゴンより手前にある：其のポリゴンで塗る。

そうでなければ、領域を4つに分けて其々で繰り返します。
1ピクセルの大きさになったら止め、ピクセルの中心で最も近いポリゴンを採ります。

図では、四角形Bが三角形Aの手前にあります。
16×16の画面は、256個のピクセルではなく64個の領域で終わります。
空が8個、ポリゴン1つが29個、手前のBに取り囲まれたのが13個、両方のポリゴンの辺が交わる所のピクセル大の物が14個です。
仕事は絵が複雑な所に集中し、大きく単純な所は1回で片付きます。
4つへの再帰的な分割は四分木で、第9章の八分木の2次元版です。

Aバッファ

Aバッファ（ローレン・カーペンター、1984年）は、逆にZバッファを拡張します。
各ピクセルは、其処に触れる面の断片（フラグメント）のリストを持ち、其々が深度、色、不透明度、そしてピクセルのどの部分を覆うかを示す小さなビットマスクを持ちます。
全てのポリゴンを描き終わったら、各ピクセルがリストを深度で並べ替えて断片を合成します。
此れでZバッファの2つの弱点が一度に解決します。
辺で部分的に覆われたピクセルは覆い具合で混ぜられ（アンチエイリアシング）、半透明の面は正しい順番で合成されます。
代償は、ピクセルごとに量が変わるメモリです。
ルーカスフィルムのREYESレンダラーの為に開発され、ピクセルごとのリストを使う今日のGPUの順序非依存の半透明の手法も、同じ考えに従っています（第2部）。

10.8 方法の比較

検定のポイント

• 背面除去だけで完全な隠面消去になるのは、凸な物体が1つだけの場合です。
• 物体空間法はポリゴン同士を比べ（正確、最大$n^2$組）、画像空間法はピクセルごとに決めます（精度はピクセルの格子まで）。
• 画家のアルゴリズムは奥から手前へ上書きして描きます。循環する重なりと貫通では、ポリゴンを分割しない限り破綻します。
• Zバッファ法：画像空間、並べ替え不要、描画順は自由、貫通も処理出来る、メモリはピクセル数に比例（ポリゴン数ではない）。半透明とアンチエイリアシングが苦手で、限られた精度がZファイティングを生み、カメラから遠い程悪くなります。
• スキャンライン法はスパン単位で働き、深度は1スキャンライン分だけで済みます。隣り合うスキャンラインの一貫性を利用します。
• レイキャスティング法は、各ピクセルを通るレイに沿って最も近い交点を採ります。
• BSP木は1回だけ作り、視点に依存しません。辿る時は視点から遠い側を先に描きます。
• ウォーノックのアルゴリズムは、各領域が単純になるまで画面を4つに分割します。

10.9 光源

次は2つ目の問い、見える面はどれだけ明るいか、です。
其れは面に届く光で決まるので、まず光源のモデルが必要です。

点光源

点光源は位置を持ち、小さな電球の様に全ての方向へ均等に光を出します。
光源への方向$𝐥$は、面上の点ごとに変わります。
物理的には、光源を囲む球を通る光は球の面積$4\pi d^2$に広がるので、距離$d$に届く光は逆2乗の法則に従って減ります：

距離が2倍なら、光は4分の1です。
リアルタイムのグラフィックスでは伝統的に、3つの定数を持つもっと柔軟な減衰の係数を使ってきました（OpenGLの昔の固定機能のライトが正に此の3つを持っていました）：

$k_c$は定数、$k_l$は1次、$k_q$は2次の減衰です。
$k_c=k_l=0$、$k_q=1$が物理の法則で、残りの項は光源のすぐ近くで光が発散するのを防ぎ、アーティストが減衰の形を調整出来る様にします。
例： $k_c=1$、$k_l=0.1$、$k_q=0.02$、$d=5$なら、$f_{\text{att}}=\frac{1}{1+0.5+0.02\cdot 25}=\frac{1}{2}=0.5$です。
現代の物理ベースのエンジンは、素の逆2乗の法則に滑らかな打ち切り半径を組み合わせて使います。

平行光源

平行光源は方向だけを持ちます。
全ての光線が平行で、$𝐥$はどの点でも同じで、減衰はありません。
とても遠い光源、何より太陽のモデルです。
太陽は約1億5千万kmの彼方にあるので、数kmのシーンの中では其の光線は実用上完全に平行です。
計算が一番安い光源です。

スポットライト

スポットライトは、円錐の中だけを照らす点光源です。
位置、軸の方向$𝐬$、カットオフ角${\theta }_c$を持ちます。
軸と、光源から面上の点への方向との角度を$\gamma$とすると、$\cos \gamma =-𝐥\cdot 𝐬$です（単位ベクトルで、$𝐥$は面から光源への向き）。
円錐の外（$\gamma >{\theta }_c$）では光は0です。
内側では、古典的な減衰（ウォーンのモデル）が光に$(\cos \gamma {)}^p$を掛けるので、軸上が一番明るくなります。
$p$が大きい程、光が集中します。
多くのエンジンは代わりに、内側と外側の円錐の角度の間で$\cos \gamma$について線型にフェードさせます。
例： $p=10$、$\gamma =20\text{°}$なら、${\cos }^{10}20\text{°}={0.9397}^{10}\approx 0.537$です。
内側の角度が20°、外側が30°なら、$\gamma =25\text{°}$の点は$\frac{\cos 25\text{°}-\cos 30\text{°}}{\cos 20\text{°}-\cos 30\text{°}}=\frac{0.9063-0.8660}{0.9397-0.8660}\approx 0.547$の光を受けます。

面光源

面光源は大きさのある面から光ります。
窓、天井のパネル、写真スタジオのソフトボックスなどです。
蛍光灯は其の1次元版の線光源です。
光が沢山の点から同時に来るので、物体は半影がなだらかな柔らかい影を落とし（第11章）、光沢のある物体のハイライトは光源の形になります。
オフラインレンダラーは光源上の多数の点をサンプリングし、リアルタイムのエンジンは巧妙な近似を使います（第2部とGLSLシリーズの第10章）。

環境光

現実では、どのランプにも背を向けた面でも真っ黒にはなりません。
光が壁や床や天井で跳ね返り、間接的に届くからです。
其れを正しく計算するのが大域照明です（第12章）。
安上がりな代役が環境光です。
あらゆる方向から届き、面の向きに関係無く全ての面を等しく照らす一定量の光$I_a$です。
影が真っ黒にならない様に埋めてくれますが、形を全く無視するので、影がのっぺりともします。

10.10 反射モデル

反射モデル（ライティングモデル、照明モデルとも言います）は、面上の点に届く光から、其の点から視点へ向かう光を求めます。
古典的な局所モデルは、環境光、拡散反射、鏡面反射の3つの部分から成ります。
面上の点Pで5つのベクトルを使います：

• $𝐧$：面の法線。
• $𝐥$：Pから光源への方向。
• $𝐯$：Pから視点への方向。
• $𝐫$：$𝐧$に関する$𝐥$の鏡映の方向。
• $𝐡$：$𝐥$と$𝐯$の間のハーフベクトル。

5つとも単位ベクトルです。
此の章では式を読み易くする為にハットを省きます。
図は下の計算例の数値を使っています：

色は1チャンネルずつ扱います。
以下の式は全てR、G、Bについて別々に計算し、2つの色の積はチャンネルごとの積です。
係数$k_a$、$k_d$、$k_s$は材質の反射率（チャンネルごとに0から1）で、$I_a$と$I_L$は環境光と光源の色です。

環境光の反射

物体全体で一定です。
普通は$k_a=k_d$とします。
赤い物体は赤い環境光を反射します。

拡散反射：ランバートの余弦則

艶消しの面（紙、漆喰、磨いていない木）は、受けた光を全ての方向に散らします。
此れが拡散反射です。
受ける光の量は、法線と光の方向の角度$\theta$で決まります。
斜めに当たる光の束はより広い面積に広がるので、1平方センチメートルごとの光は減ります。
此れがランバートの余弦則（ランベルト、1760年）で、単位ベクトルなら余弦は内積です（図は線型代数シリーズ第4章にあります）：

maxは面の裏からの光を取り除きます。

何故$𝐯$が出てこないのでしょうか？
理想的な拡散面（ランバート面）は、どの方向から見ても同じ明るさに見えます。
浅い角度から見ると、画像の1ピクセルが面のより広い部分を覆います（短縮）。
でも理想的な拡散面は、浅い方向へは面積当たりの光を見る角度の余弦に比例して少なく送るので、2つの効果は丁度打ち消し合います。
其の為、拡散反射は視点に依存しません。
紙の周りを歩いても、明るさは変わりません。
ラジオシティ法（第12章）が拡散の照明を全ての視点に対して1回だけ前計算出来るのも此の為です。

鏡面反射：フォンのモデル

光沢のある面（プラスチック、磨いた金属、濡れた肌）では鏡面反射も起こり、ハイライトとして見えます。
光が殆ど鏡の様に視点へ反射される所の明るい点です。
完全な鏡は、光を鏡映の方向にだけ反射します：

此れは線型代数シリーズ第4章の反射の式を、入射方向$-𝐥$に当てはめた物です。
本物の光沢面は、反射を$𝐫$の周りに広げます。
ブイ・トゥオン・フォン（1975年）は、此の広がりを$𝐫$と$𝐯$の角度$\varphi$の余弦の累乗で表しました：

指数$\alpha$は鏡面反射指数（ハイライト係数、光沢度）です。
1より小さい余弦を大きく累乗するとすぐに小さくなるので、$\alpha$が大きいと小さく鋭いハイライト（磨いた金属、$\alpha$は数百）、小さいと広く柔らかいハイライト（ゴム、$\alpha$は5〜10程度）になります。
鏡面反射は視点に依存します。
頭を動かすと、ハイライトが面の上を動きます。
プラスチックなどの非金属ではハイライトは光の色になり（$k_s$は灰色）、金属では金属の色になります（$k_s$に色が付きます。金を思い浮かべて下さい）。
鏡面反射の項は、光が面の表側にある時（$𝐧\cdot 𝐥>0$）だけ加えます。

フォンの照明方程式

3つの項と10.9節の減衰を足すと、フォンの反射モデルになります。
光源が複数$j=1,2,\dots$あれば、各光源が其々の拡散反射と鏡面反射を加え、環境光は1回だけ数えます：

足し算が成り立つのは光が線型に足し合わされるからで、其の為に此の和はリニアな値で計算し、最後にsRGBへエンコードしなければなりません（第3章の3.7節）。
結果が1を超えたらクリップするか、HDRレンダリングではトーンマッピングで圧縮します（第15章）。

計算例

床の上の点Pを、1つの点光源が照らしています：

• Pは原点にあり、床の法線は$𝐧=(0,1,0)$です。
• 光源は$(0,3,4)$にあり、色は$I_L=(1,0.9,0.8)$（少し暖色）、減衰は$k_c=1$、$k_l=0.1$、$k_q=0.02$です。
• 視点は$(0,8,-6)$にあります。
• 環境光は$I_a=(0.2,0.2,0.2)$です。
• 材質：$k_a=k_d=(0.8,0.4,0.2)$（オレンジ）、$k_s=(0.5,0.5,0.5)$、$\alpha =10$。

段階1：ベクトル。
光源へ：$(0,3,4)-(0,0,0)$、長さ$\sqrt{9+16}=5$なので、$d=5$、$𝐥=(0,0.6,0.8)$です。
視点へ：$(0,8,-6)$、長さ$\sqrt{64+36}=10$なので、$𝐯=(0,0.8,-0.6)$です。

段階2：減衰。

段階3：拡散反射の係数。

段階4：鏡面反射の係数。

視点は鏡映の方向に近い（$\varphi =\arccos 0.96\approx 16.3\text{°}$）ので、ハイライトはまだ最大の3分の2の強さがあります。

段階5：チャンネルごとの3つの項。

段階6：合計。

暖かいオレンジで、8ビットのsRGBにエンコードすると（第3章）約(198, 157, 129)です。
色の組み合わさり方に注目して下さい。
拡散反射はオレンジの材質と暖色の光の積ですが、ハイライトは灰色の$k_s$と光の積なので、光の色になります。
純粋な青い光$(0,0,1)$の下では、拡散反射は$0.3\cdot (0,0,0.2)=(0,0,0.06)$で、殆ど黒になります。
此の材質は青を殆ど反射しないからです。

同じ数値で、モデルを小さなC++の関数にした物です：

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

// component-wise product: the color of the light times the color of the material
Vec3 mul(Vec3 a, Vec3 b) { return {a.x * b.x, a.y * b.y, a.z * b.z}; }

struct Material {
  Vec3 ka, kd, ks; // ambient, diffuse and specular reflection coefficients (RGB)
  float shininess; // the exponent alpha
};

struct PointLight {
  Vec3 position;
  Vec3 color;       // I_L
  float kc, kl, kq; // constant, linear and quadratic attenuation
};

// The Phong reflection model for one point light.
// p: surface point, n: unit normal, eye: eye position.
Vec3 phong(Vec3 p, Vec3 n, Vec3 eye, const Material &m, const PointLight &light, Vec3 ambient) {
  Vec3 toLight = light.position - p;
  float d = length(toLight);
  Vec3 l = toLight / d;                      // unit vector towards the light
  Vec3 v = normalize(eye - p);               // unit vector towards the eye
  float att = 1.0f / (light.kc + light.kl * d + light.kq * d * d);
  float nl = dot(n, l);
  Vec3 color = mul(m.ka, ambient);           // ambient term
  if (nl > 0) {                              // the light is in front of the surface
    Vec3 r = 2.0f * nl * n - l;              // mirror direction of l
    float spec = std::pow(std::max(dot(r, v), 0.0f), m.shininess);
    color = color + att * (nl * mul(m.kd, light.color) + spec * mul(m.ks, light.color));
  }
  return color;
}

int main() {
  Material m{{0.8f, 0.4f, 0.2f}, {0.8f, 0.4f, 0.2f}, {0.5f, 0.5f, 0.5f}, 10.0f};
  PointLight light{{0, 3, 4}, {1.0f, 0.9f, 0.8f}, 1.0f, 0.1f, 0.02f};
  Vec3 c = phong({0, 0, 0}, {0, 1, 0}, {0, 8, -6}, m, light, {0.2f, 0.2f, 0.2f});
  printf("I = (%.4f, %.4f, %.4f)\n", c.x, c.y, c.z);
  return 0;
}

I = (0.5662, 0.3376, 0.2210)

ブリン・フォン：ハーフベクトル

ジム・ブリン（1977年）は、$𝐫\cdot 𝐯$の代わりに、法線とハーフベクトル（中間ベクトル）の角度を使いました。
ハーフベクトルは、光源と視点の丁度真ん中の方向です：

此れがブリン・フォンの反射モデルです。
法線が丁度$𝐡$を向いていれば、面は光を真っ直ぐ視点へ反射する鏡になるので、考え方は同じです。
今の例では$𝐥+𝐯=(0,1.4,0.2)$、長さは$\sqrt{1.96+0.04}=\sqrt{2}\approx 1.4142$なので、$𝐡\approx (0,0.9899,0.1414)$、$𝐧\cdot 𝐡\approx 0.9899$で、角度は約8.1°です。
此れは$\varphi \approx 16.3\text{°}$の半分です。
$𝐧$、$𝐥$、$𝐯$が1つの平面上にある時、$𝐧$と$𝐡$の角度は丁度$𝐫$と$𝐯$の角度の半分になります。
其の為、同じ指数ではブリン・フォンのハイライトの方が大きくなります。
0.665ではなく${0.9899}^{10}\approx 0.904$です。
大体同じハイライトにするには、指数をおよそ4倍にします。
${0.9899}^{40}\approx 0.668$で、フォンの0.665にとても近くなります。

ブリン・フォンが標準になった理由は3つあります。
平行光源と遠くの視点では$𝐥$と$𝐯$が一定なので、点ごとに$𝐫$を求める代わりに、$𝐡$を1フレームに1回求めるだけで済みます（OpenGLとDirect3Dの固定機能のライティングはハーフベクトルを使っていました）。
フォンのハイライトは常に丸いのに対し、ブリン・フォンのハイライトは浅い角度で本物の様に引き伸ばされます（湖に映る太陽の細長い反射を思い浮かべて下さい）。
そして、同じく$𝐧\cdot 𝐡$で書かれる第12章の物理ベースのマイクロファセットモデルに近いのです。

古典的なモデルの限界

フォンのモデルは経験的なモデルです。
物理から導いたのではなく、其れらしく見える様に作られました。
エネルギーを保存しませんし（$k_d+k_s$が届いた以上の光を反射するのを止める物は何も無く、$\alpha$を大きくするとハイライトは小さくなるのに明るくはなりません）、フレネル効果（浅い角度で面がより鏡の様になる事）もありませんし、直接光の1つの経路しか見ていません。
現代のレンダラーはBRDFによる物理ベースの反射を使いますが（第12章と第2部）、構造は同じです。
拡散反射の部分、鏡映の方向の周りにハイライトを持つ鏡面反射の部分、そして光源についての和です。
フォンのライティングはOpenGLシリーズの第10章で、3種類の光源は第12章で、シェーダーではGLSLシリーズの第9章で実装します。

10.11 シェーディング手法

反射モデルは、1つの点を1つの法線で照らす方法を教えてくれます。
ポリゴンメッシュは頂点（又は面ごと）にしか法線を持たず、其の間には何百万ものピクセルがあります。
シェーディング手法は、反射モデルを何処で評価し、其の結果でポリゴンをどう埋めるかを決めます。
古典的な物が3つあります。

フラットシェーディング

フラットシェーディング（コンスタントシェーディング）は、モデルをポリゴンごとに1回、ポリゴンの面法線で評価し、ポリゴン全体を其の1色で塗ります。
一番安く、平行光源と遠くの視点の下で本当に平らな面を持つ物体（立方体、結晶）には正確です。
ポリゴンで近似した曲面では全ての面が見えてしまい、目のマッハバンド（第3章）が明るさの段差を更に強調します。

グーローシェーディング

グーローシェーディング（アンリ・グーロー、1971年、スムーズシェーディングとも言います）は、モデルを頂点で評価し、色をポリゴン上で補間します：

1. 各頂点に頂点法線を与えます。普通は周りの面の法線の平均で（第9章）、隣のポリゴンと共有します。
2. 各頂点の色を反射モデルで計算します。
3. 色をポリゴン上で線型に補間します。古典的な方法では辺に沿って、次に各スキャンラインに沿って、GPUでは重心座標で補間します（6.9節）。

隣のポリゴンが頂点の色を共有するので、明るさは辺を跨いで連続になり、面の境目が消えます。
安価でもあります。
メッシュの頂点は、其れが覆うピクセルよりずっと少ないからです。
弱点は全て、光を頂点でしか計算しない事から来ます：

• ハイライトが消えたり、滲んだりします。 ポリゴンより小さなハイライトが頂点の間に落ちると、どの頂点も其れを見ないので、単に失われます。頂点に落ちたハイライトは周りの全てのポリゴンに広がり、メッシュに沿った形のぼやけた星になります。物体が動くと、ハイライトが頂点から頂点へ跳び、ちらつきます。
• マッハバンド。 明るさは辺を跨いで連続ですが、其の傾きは辺で変わり、目は其の様な傾きの変化に沿って明るい縞と暗い縞を加えるので（第3章）、メッシュの構造が透けて見える事があります。

フォンシェーディング

フォンシェーディング（フォン、1975年）は、色ではなく法線を補間し、反射モデルをピクセルごとに評価します：

1. 頂点法線をポリゴン上で補間します。
2. 各ピクセルで、補間した法線を正規化します。単位ベクトルの線型な混合は、すぐ後で見る様に長さが1より短くなり、モデルの内積には単位ベクトルが必要です。
3. 此の法線で反射モデルを評価します。

ハイライトは、大きなポリゴンの真ん中でも、在るべき所に現れます。
形もメッシュに関係無く、光と曲率で決まる形になります。
代償は、反射モデルの評価が頂点ごとではなくピクセルごとになる事です。

名前を混同しないで下さい。
フォンの反射モデル（10.10節）は、環境光、拡散反射、$(𝐫\cdot 𝐯{)}^{\alpha }$から成る式です。
フォンシェーディングは、法線を補間して全てのピクセルを照らす手法です。
此の2つは独立しています。
フォンのモデルをグーローシェーディングで使う事も出来ますし（固定機能のGPUが正に其れでした）、フォンシェーディングを全く別の物理ベースの反射モデルと組み合わせる事も出来ます（現代のエンジンは皆そうしています）。

計算例：2つの頂点の間のハイライト

メッシュの1本の辺を考えます。
2つの頂点の法線は次の通りです：

（両方とも単位ベクトルです：$0.36+0.64=1$。）
曲面の頂上を挟んだ両側の2点の様な物です。
光源と視点は両方とも真正面にあります：$𝐥=𝐯=(0,0,1)$（「ヘッドライト」の配置）。
拡散反射の係数$𝐧\cdot 𝐥$と、$\alpha =10$での鏡面反射の係数$(𝐫\cdot 𝐯{)}^{\alpha }$を見ます。

頂点では。
${𝐧}_1\cdot 𝐥=0.8$です。
${𝐫}_1=2\cdot 0.8\cdot (-0.6,0,0.8)-(0,0,1)=(-0.96,0,0.28)$なので、${𝐫}_1\cdot 𝐯=0.28$、${0.28}^{10}\approx 3\cdot {10}^{-6}$で、ハイライトは全くありません。
2つ目の頂点も対称なので同じです。

グーローの中点は此れらの結果を補間します。
拡散反射は$\frac{0.8+0.8}{2}=0.8$、鏡面反射は$\approx 0$です。

フォンの中点は法線を補間します：

すると$𝐧\cdot 𝐥=1$、$𝐫=2\cdot 1\cdot (0,0,1)-(0,0,1)=(0,0,1)$、$𝐫\cdot 𝐯=1$、$1^{10}=1$です。
拡散反射は1で、ハイライトは最大です。
面が光の方を向いている丁度其の場所で、グーローシェーディングは此れを完全に見逃しました。

${𝐧}_1$から4分の1の所：混合は$(-0.3,0,0.8)$、長さ$\sqrt{0.09+0.64}\approx 0.8544$で、正規化すると$(-0.3511,0,0.9363)$です。
すると$𝐧\cdot 𝐥=0.9363$で、$𝐥=𝐯$なので鏡映の項は$𝐫\cdot 𝐯=2(𝐧\cdot 𝐥{)}^2-1=2\cdot 0.8767-1\approx 0.7534$、鏡面反射の係数は${0.7534}^{10}\approx 0.059$です。
ハイライトは4分の1の所の殆ど0から真ん中の1へ立ち上がります。
細く、頂点の間にあるのです。

そして段階2は大事です。
正規化しないと、中点の法線$(0,0,0.8)$は$𝐧\cdot 𝐥=0.8$を与え、グーローと変わりません。
（実は此の2つの法線のどんな混合でもz成分は0.8なので、正規化しない法線では辺全体で一様に0.8になります。）

描画して比べる

ローポリゴンの球（経度方向に12分割、極から極へ8分割のUV球、三角形168個）を各手法で描いた物です。
10.10節のフォンの反射モデルを$\alpha =40$で使い、平行光源は左上から照らしています。
此の絵は、此の章と第6章の式を其の儘使う小さなソフトウェアラスタライザーで計算しました。
エッジ関数、重心座標による補間、Zバッファ、そしてシェーディング手法を使い、リニアな結果をsRGBにエンコードしています。

• フラット：全ての面が見え、ハイライトの方向を向いた面が丸ごと明るくなります。
• グーロー：滑らかですが、ハイライトが消えています。右のメッシュの図が理由を示しています。ハイライトは1つの四角形の中、全ての頂点から離れた所にあり、頂点には其の暗い裾しか見えません。
• フォン：ハイライトは在るべき所に丸く鋭く現れますが、輪郭は相変わらず多角形です。シェーディングが隠せるのは輪郭の内側の面の境目で、輪郭其の物ではありません。

次のグラフは、ハイライトの中心を通る画像の行に沿った明るさです：

フラットシェーディングは辺ごとに段差のある階段です。
グーローシェーディングは連続ですが直線の繋がりで、傾きが変わる角が正にマッハバンドの現れる所です。
フォンシェーディングは滑らかで、グーローには見えないハイライトの山を持っています。

GPUでは：頂点ごとかフラグメントごとか

GPUでは、反射モデルを何処で呼ぶかを選ぶだけです：

• 頂点シェーダーで呼んで色を渡すと、ラスタライザーが其れを補間し、グーローシェーディングになります。OpenGL 1.xやバージョン9までのDirect3Dの固定機能パイプラインは此の方式でした（glShadeModel(GL_SMOOTH)。GL_FLATでフラットシェーディング）。
• フラグメントシェーダーで、頂点シェーダーから渡された法線（と位置）を使って呼ぶと、ラスタライザーが法線を補間し、フラグメントシェーダーが其れを正規化してピクセルを照らすので、フォンシェーディングになります。今は此れが普通です。
• フラットシェーディング：varyingを補間しない様に指定します（GLSLではflat、SlangではHLSLと同じくnointerpolation）。すると三角形全体が其の頂点の1つ（「provoking vertex」）の値を使います。

コストの違い：1920×1080の画像は約207万ピクセル（オーバードローがあればフラグメントはもっと多い）ですが、典型的なキャラクターの頂点は数万個です。
現代のGPUは毎秒何十億回もフラグメントシェーダーを実行するので、ピクセルごとのライティングは十分安く、法線マッピング（第11章）の様な技法にはどの道必要です。

1つの点光源に対するフォンの反射モデルを使ったフォンシェーディングを、フラグメントシェーダーで書くと次の様になります（短くする為に減衰は省いています）：

struct Scene {
  float3 lightPos;   // world space
  float3 lightColor; // I_L
  float3 ambient;    // I_a
  float3 eyePos;     // world space
  float3 kd;         // diffuse (and ambient) color of the material
  float3 ks;         // specular color
  float shininess;   // alpha
};
ConstantBuffer<Scene> scene;

float3 phongModel(float3 n, float3 l, float3 v) {
  float3 color = scene.kd * scene.ambient;
  float nl = dot(n, l);
  if (nl > 0.0) {
    float3 r = reflect(-l, n); // = 2 (n.l) n - l
    float spec = pow(max(dot(r, v), 0.0), scene.shininess);
    color += scene.lightColor * (scene.kd * nl + scene.ks * spec);
  }
  return color;
}

[shader("fragment")]
float4 fragmentMain(float3 worldPos : TEXCOORD0, float3 normal : NORMAL) : SV_Target {
  float3 n = normalize(normal); // interpolation made it shorter than 1
  float3 l = normalize(scene.lightPos - worldPos);
  float3 v = normalize(scene.eyePos - worldPos);
  return float4(phongModel(n, l, v), 1.0);
}

#version 450

layout(location = 0) in vec3 worldPos;
layout(location = 1) in vec3 normal;
layout(location = 0) out vec4 outColor;

layout(set = 0, binding = 0) uniform Scene {
  vec3 lightPos;   // world space
  vec3 lightColor; // I_L
  vec3 ambient;    // I_a
  vec3 eyePos;     // world space
  vec3 kd;         // diffuse (and ambient) color of the material
  vec3 ks;         // specular color
  float shininess; // alpha
};

vec3 phongModel(vec3 n, vec3 l, vec3 v) {
  vec3 color = kd * ambient;
  float nl = dot(n, l);
  if (nl > 0.0) {
    vec3 r = reflect(-l, n); // = 2 (n.l) n - l
    float spec = pow(max(dot(r, v), 0.0), shininess);
    color += lightColor * (kd * nl + ks * spec);
  }
  return color;
}

void main() {
  vec3 n = normalize(normal); // interpolation made it shorter than 1
  vec3 l = normalize(lightPos - worldPos);
  vec3 v = normalize(eyePos - worldPos);
  outColor = vec4(phongModel(n, l, v), 1.0);
}

struct Scene {
  float3 lightPos;   // world space
  float3 lightColor; // I_L
  float3 ambient;    // I_a
  float3 eyePos;     // world space
  float3 kd;         // diffuse (and ambient) color of the material
  float3 ks;         // specular color
  float shininess;   // alpha
};
ConstantBuffer<Scene> scene;

float3 phongModel(float3 n, float3 l, float3 v) {
  float3 color = scene.kd * scene.ambient;
  float nl = dot(n, l);
  if (nl > 0.0) {
    float3 r = reflect(-l, n); // = 2 (n.l) n - l
    float spec = pow(max(dot(r, v), 0.0), scene.shininess);
    color += scene.lightColor * (scene.kd * nl + scene.ks * spec);
  }
  return color;
}

float4 fragmentMain(float3 worldPos : TEXCOORD0, float3 normal : NORMAL) : SV_Target {
  float3 n = normalize(normal); // interpolation made it shorter than 1
  float3 l = normalize(scene.lightPos - worldPos);
  float3 v = normalize(scene.eyePos - worldPos);
  return float4(phongModel(n, l, v), 1.0);
}

どの言語にもreflect(d, n)が組み込まれていて、入射方向$𝐝$に対して$𝐝-2(𝐝\cdot 𝐧)𝐧$を計算します。
此処では光が進む方向$-𝐥$を渡しています。
ブリン・フォンにするには、鏡面反射の2行をh = normalize(l + v)とpow(max(dot(n, h), 0.0), shininess)に置き換えます（線型代数シリーズ第4章と同じです）。
同じphongModelの呼び出しを頂点シェーダーに移し、法線の代わりに色を渡せば、グーローシェーディングになります。

10.12 半透明

ガラス、水、煙、木の葉は、後ろからの光を一部通します。
一番単純なモデルでは、各面に0（見えない）から1（不透明）までの不透明度$\alpha$を与え、普通は色の4番目のチャンネル、アルファとして保存します。
（此の$\alpha$は鏡面反射指数とは全く関係ありません。単に人気のある文字なだけです。）

アルファブレンディング

色$C_s$、不透明度${\alpha }_s$の面を、フレームバッファに既にある色$C_d$の上に描く時、アルファブレンディングはover演算子（ポーターとダフ、1984年）で2つを混ぜます：

後ろにある物と新しい面の間の線型補間で、GPUパイプラインのブレンディングの段階（6.5節）がチャンネルごとに行います。

順番に依存する

赤いガラス$(1,0,0)$と青いガラス$(0,0,1)$を、どちらも$\alpha =0.5$で、白い背景$(1,1,1)$の上に描きます。

赤が先、次に青：

青が先、次に赤：

最後に描いたガラスが勝ちます。
正しい絵にするには、視点に近い面を最後に混ぜなければならないので、半透明の面は奥から手前へ描く必要があります。
又しても画家のアルゴリズムです。

Zバッファと半透明

此れは、どんな順番でも平気で描くZバッファとぶつかります。
手前のガラスが先に描かれて深度を書き込むと、後から描かれた其の後ろの物体は、ガラス越しに見える代わりに深度テストに落ちて消えてしまいます。
標準的な手順は次の通りです：

1. まず全ての不透明な物体を、どんな順番でも良いので、深度テストと深度の書き込みを有効にして描きます。
2. 半透明の物体を奥から手前へ（カメラからの距離で）並べ替えます。
3. 深度テストは有効（手前の不透明な物体が其れを隠せる様に）、深度の書き込みは無効（互いや後の物体を隠さない様に）にして描きます。

並べ替えは物体単位なので、10.2節の問題を全て抱えています。
交わったり循環して重なったりする半透明の物体は、何処かで間違って描かれます。
正確な解決策は順序非依存の半透明の手法で、10.7節のAバッファやデプスピーリングなどがあります（第2部）。
並べ替えの要らない特別な場合が1つあります。
加算ブレンディング$C=C_d+{\alpha }_s{C}_s$は可換（足し算は順番を気にしない）なので、炎、火花、光の輝きは普通加算で描きます。
ブレンディングはOpenGLシリーズの第16章で設定します。

アルファブレンディングは面の後ろの背景を薄めるだけで、曲げはしません。
本物のガラスや水は光を屈折させ（スネルの法則）、浅い角度でより多く反射します（フレネル効果）。
レイトレーシングは其の両方を扱えます。
第12章で扱います。

検定のポイント

• フォンの反射モデル：環境光$k_a{I}_a$（一定）、拡散反射$k_d{I}_L(𝐧\cdot 𝐥)$（ランバート、視点に依存しない）、鏡面反射$k_s{I}_L(𝐫\cdot 𝐯{)}^{\alpha }$（視点に依存する）。$𝐫=2(𝐧\cdot 𝐥)𝐧-𝐥$です。
• 鏡面反射指数$\alpha$が大きい程、ハイライトは小さく鋭くなります。ブリン・フォンはハーフベクトルで$(𝐧\cdot 𝐡{)}^{\alpha \prime }$を使い、似たハイライトには$\alpha \prime \approx 4\alpha$です。
• 光源：点光源（位置、逆2乗で減衰）、平行光源（方向だけ、減衰無し、太陽）、スポットライト（円錐）、面光源（柔らかい影）、環境光（一定、間接光の代役）。
• フラットシェーディング：ポリゴンごとに1色。グーロー：頂点で色を求めて補間（安価、ハイライトが消えたり滲んだりする、マッハバンド）。フォンシェーディング：法線を補間して正規化し、ピクセルごとにモデルを評価。
• 「フォンシェーディング」（補間の手法）と「フォンの反射モデル」（式）は別物です。
• over演算子によるアルファブレンディングは描画順に依存します。半透明の面は不透明な面の後に、深度の書き込みを無効にして奥から手前へ描きます。

10.13 まとめ

• 隠面消去は各ピクセルで何が見えるかを決めます。物体空間法はポリゴンを比べ、画像空間法はピクセルごとに働きます。背面除去だけで足りるのは、凸な物体が1つの時だけです。
• 画家のアルゴリズム（奥行きソート法）は奥から手前へ描きます。循環する重なりと貫通ではポリゴンの分割が必要です。
• Zバッファ法はピクセルごとに深度を持ち、ピクセルごとの深度テストでどんな順番でも描けます。貫通は扱えますが半透明は扱えず、精度は距離の2乗で落ちます（Zファイティング）。
• スキャンライン法は1スキャンラインずつスパンごとに深度を比べ、レイキャスティング法はピクセルごとにレイに沿った最も近い交点を探し、BSP木はどの視点にも奥から手前への順番を与え、ウォーノックのアルゴリズムは各領域が単純になるまで画面を分割し、Aバッファはピクセルごとに断片のリストを持ちます。
• 光源：点光源（減衰$1/(k_c+k_{l}d+k_q{d}^2)$、物理的には$1/d^2$）、平行光源、スポットライト、面光源、環境光。
• フォンの反射モデルは、環境光、拡散反射（$𝐧\cdot 𝐥$）、鏡面反射（$(𝐫\cdot 𝐯{)}^{\alpha }$）の項を光源について、色のチャンネルごとに足します。ブリン・フォンはハーフベクトルを使います。
• フラットシェーディングはポリゴンごとに1回照らし、グーローシェーディングは頂点を照らして色を補間し、フォンシェーディングは法線を補間して全てのピクセルを照らします。
• アルファブレンディングは順番に依存します。不透明な物が先、次に半透明な物を奥から手前へ描きます。

10.14 用語

10.15 課題

1. ★ 3840×2160の画面が32ビットの深度バッファを使います。何バイトで、何MiBですか？ 24ビットの深度バッファ、$n=0.1$、$f=1000$で、距離50 mでまだ区別出来る最小の深度の差を見積もり、$n=0.5$でも求めて下さい。
2. ★ 色$(1,1,1)$の平行光源が$𝐥=(0,0.6,0.8)$の方向から来て、法線は$𝐧=(0,0,1)$、視点は$𝐯=(0,0,1)$の方向にあります。$k_a=k_d=(0.2,0.6,0.4)$、$I_a=(0.1,0.1,0.1)$、$k_s=(0.4,0.4,0.4)$、$\alpha =8$で、$𝐫$、3つの項、最終的な色を計算して下さい。次に鏡面反射の項をブリン・フォン、$\alpha \prime =32$に置き換えて比べて下さい。
3. ★★ 10.6節の線分を使い、視点$E_3=(1,3)$に対するBSPの描画順を求めて下さい。次に$b$を根にして（$a$、$c$、$d$の順に入れて）木を作り直し、$E_1$と$E_2$に対して本文の木と同じ順番になる事を確かめて下さい。
4. ★★ 辺の2つの頂点の法線が$(-0.28,0,0.96)$と$(0.28,0,0.96)$で、$𝐥=𝐯=(0,0,1)$、$\alpha =20$です。頂点と中点での鏡面反射の係数を、グーローシェーディングとフォンシェーディングで計算し、正規化する前の補間した法線の長さも求めて下さい。
5. ★★★ $\alpha =0.5$の3枚のガラス（赤、緑、青）を黒の上に混ぜます。2通りの描画順で結果が異なる事、でも加算ブレンディングならどの順番でも同じ結果になる事を数値で示して下さい。次に、半透明の物体を中心で並べ替えても失敗し得る理由を、10.2節の循環する重なりの様な図を使って説明して下さい。

選択問題

問1 ★ 次のうち、Zバッファ法について正しい物はどれか。

問2 ★ 次のうち、シェーディング手法について正しい物はどれか。

問3 ★★ 面上の点で$𝐧=(0,1,0)$、光源への方向が$𝐥=(0.6,0.8,0)$、視点への方向が$𝐯=(-0.8,0.6,0)$である。光の強さは1、$k_s=0.5$、$\alpha =2$とする。フォンの反射モデルの鏡面反射の項$k_{s}max(𝐫\cdot 𝐯,0{)}^{\alpha }$はどれか。

10.16 実践課題

小さなシーンを方眼紙の上でZバッファにかけ、シェーディングする。
方眼紙、定規、赤と青の色鉛筆、電卓を用意して下さい。
GPUが毎フレーム行っている事を手で行います。
Zバッファで可視性を決め、画家のアルゴリズムと比べ、1つの三角形を3通りにシェーディングします。

画面は8×6ピクセルで、ピクセル$(i,j)$は$(i,j)$から$(i+1,j+1)$までの正方形、中心は$(i+0.5,j+0.5)$です（yは上向き）。

• 三角形P：$A(0,0)$、$B(8,0)$、$C(0,6)$、深度0.2、0.6、0.2。深度の平面は$z_P=0.2+0.05x$です。
• 三角形Q：$(8,0)$、$(8,6)$、$(0,2)$、3つの頂点全てで深度0.4。

1. 覆う範囲。 格子と2つの三角形を描きます。各ピクセルの中心がPの中か、Qの中か、両方の中かを決めて下さい（第6章のエッジ関数か、辺の直線の方程式を使います。丁度辺の上にある中心はありません）。両方に覆われるピクセルに印を付けます。
2. 深度。 Pに覆われる全てのピクセルに$z_P$を、Qに覆われる全てのピクセルに0.4を書き込みます。2つの三角形は何処で互いを貫通しますか？
3. Zバッファ、2通りの順番。 全ての深度を1から始めます。深度テスト付きでP、次にQを描き、勝った色と深度を2枚目の格子に書き込みます。次に順番をQ、次にPにして、3枚目の格子でもう一度行います。結果に色を塗ります。
4. 画家のアルゴリズム。 PとQを頂点の深度の平均で並べ替え、奥から手前へ上書きしながら4枚目の格子に塗ります。Zバッファと結果が異なるピクセルを数え、其の理由を段階2の直線を使って説明して下さい。
5. 頂点をシェーディングする。 Pに頂点法線${𝐧}_A=(0,0,1)$、${𝐧}_B=(0.6,0,0.8)$、${𝐧}_C=(0,0.6,0.8)$を与え、灰色の材質$k_a{I}_a=0.1$、$k_d=0.6$、$k_s=0.3$、$\alpha =10$、強さ1の白い光、$𝐥=𝐯=(0,0,1)$を使います。A、B、Cでの明るさ$I=0.1+0.6(𝐧\cdot 𝐥)+0.3(𝐫\cdot 𝐯{)}^{10}$を計算して下さい（$𝐥=𝐯$なので$𝐫\cdot 𝐯=2(𝐧\cdot 𝐥{)}^2-1$です）。
6. フラット、グーロー、フォン。 フラットシェーディングでは、3つの頂点法線の和を正規化した物を面法線とし、三角形全体の明るさを1つ計算します。ピクセルの中心$(1.5,0.5)$と$(3.5,2.5)$で、A、B、Cに関する重心座標を求め（此処では単に${\lambda }_B=\frac{x}{8}$、${\lambda }_C=\frac{y}{6}$、${\lambda }_A=1-{\lambda }_B-{\lambda }_C$です）、グーローの明るさ（3つの頂点の明るさを補間）とフォンの明るさ（法線を補間し、正規化し、モデルを評価）を計算して下さい。
7. 比べる。 2つのピクセルについてフラット、グーロー、フォンの小さな表を作り、丁度頂点Aにあるハイライトがどうなるかを説明して下さい。

自分で確認する方法：

• 段階3の2枚の格子は同じになります。Zバッファは順番を気にしません。重なりの中では、でPが、$x>4$でQが勝ちます。
• 段階4が段階3と異なるのは数ピクセルだけで、全て重なりの中、$x=4$より右にあります。
• 段階5では、Aは最大のハイライトを受け、BとCは殆ど受けません。全ての明るさは0.1と1.0の間にあります。
• 段階6では、重心座標の各組の合計は1、正規化した全ての法線の長さは1（$x^2+y^2+z^2$で確かめます）、全てのグーローの値は頂点の明るさの最小値と最大値の間にあります。