三角形の塗りつぶしと深度バッファ

目標

重心座標で三角形を塗りつぶし、頂点の値を補間し、深度バッファーで前後を決めて、裏面を取り除きます。このラボが終われば、ラスタライザー一式の核心が、手に入ります。

なぜ重要なのか

画面はピクセルの格子で、三角形の辺は格子に合いません。どのピクセルがこの三角形のものかを決める規則が必要ですが、重心座標が、その規則と値の補間を、一度に解決します。3つの係数がすべて0以上なら内側で、同じ係数で、色・法線・テクスチャ座標・深度を混ぜればよいのです。

深度バッファーは、それよりもさらに大きなものをくれます。ピクセルごとに、これまでの最小の深度を記憶しておけば、描く順序と無関係に、同じ絵が出ます。三角形を並べ替える必要がなくなり、互いに貫通する物体も、自然に処理されます。ハードウェアが、画家のアルゴリズムの代わりに、こちらを選んだ理由です。

ステップ

/root/rasterに、ツールボックスを置きます。
/root/raster/bary.pyに、重心座標を作ります。
/root/raster/out/tri.pngに、三角形を塗りつぶします。
/root/raster/out/tri_rgb.pngに、頂点の色を補間して描きます。
/root/raster/out/zbuffer.pngに、深度バッファーで2つの三角形を描きます。
深度だけを入れ替えて、/root/raster/out/zswap.pngを作ります。
/root/raster/tris.txtを読んで裏面を捨て、/root/raster/out/cull.pngと/root/raster/out/07-cull.txtを作ります。

参考

絵は、nohup python3 -m http.server 8080 -d /root/raster/out &で立てたあと、Webプレビューでhttp://localhost:8080/を開いて見ます。zbuffer.pngとzswap.pngを並べて見ることが、このラボの核心の場面です。
ピクセルの中心は(x+0.5, y+0.5)です。整数座標で判定すると、境界が1行ずれます。
よくあるミスの1つ目は、深度の比較はしたのに、深度バッファーを更新しないことです。そうすると、あとで描いたものが常に勝ちます。
よくあるミスの2つ目は、バウンディングボックスを取らずに、画面全体を回ることです。結果は同じですが、Pythonでは数倍遅くなります。

描画のツールボックスを置く

/root/raster/gfxlib.pyを例のとおりに保存し、/root/raster/check.pyでテストパターンを描いて、/root/raster/out/00-check.pngを作ってください。パターンは、64x64の黒い背景に、(0,0)から(63,63)まで、白(255,255,255)の対角線を引き、そのあとに、(0,32)から(63,32)まで、赤(255,0,0)の横線を重ねて引いたものです。

このラボからは、PNGエンコーダーを作り直しません。最初のラボで手で作ったものと同じコードを、ツールとして配ります。ここで学ぶのは、ファイル形式ではないからです。

ラボのPodにはボリュームがないので、前のラボで作ったファイルが残っていません。そのため、ラボごとに、ツールボックスを置き直すことから始めます。

Canvas(w, h, bg)を作り、line(x0, y0, x1, y1, rgb)で2本の線を引いたあと、write_png(path)で保存してください。交差点(32,32)が赤になるには、横線をあとで引く必要があります。

重心座標

/root/raster/bary.pyにbarycentric(a, b, c, p)を作ってください。a・b・c・pは2次元の点で、p = u*a + v*b + w*cとなる(u, v, w)の3つの実数を返します。

分母は、三角形の面積の2倍(符号付き)です。

d = (b1-c1)*(a0-c0) + (c0-b0)*(a1-c1)
u = ((b1-c1)*(p0-c0) + (c0-b0)*(p1-c1)) / d
v = ((c1-a1)*(p0-c0) + (a0-c0)*(p1-c1)) / d
w = 1 - u - v

確認は、頂点で行います。pがaなら(1,0,0)、bなら(0,1,0)、cなら(0,0,1)である必要があります。そして、3つの値の和は、どこでも常に1です。

3つの値がすべて0以上なら、三角形の内側です。この性質1つが、内外の判定と、値の補間を、同時に解決します。

三角形を塗りつぶす

/root/raster/fill.pyで、/root/raster/out/tri.png(256x256、黒い背景)に、頂点(30,30)、(220,60)、(120,230)の三角形を、赤(255,60,60)で塗りつぶしてください。ピクセル(x, y)の中心は(x+0.5, y+0.5)とみなし、重心座標の3つがすべて0以上のときに塗ります。

画面全体を走査せず、バウンディングボックスの中だけを回ってください。3つの頂点のxの最小・最大、yの最小・最大で、ボックスを取れば済みます。GPUも、同じことをタイル単位で行います。

ピクセルの中心を(x+0.5, y+0.5)とおくことが重要です。整数座標で判定すると、境界で1行ずれます。

塗られたピクセルの数が、三角形の面積に近い必要があります。靴ひも公式で面積を求めて、比べてみてください。

頂点の色を混ぜる

/root/raster/interp.pyで、同じ三角形を/root/raster/out/tri_rgb.pngに描きますが、頂点A(30,30)は赤(255,0,0)、B(220,60)は緑(0,255,0)、C(120,230)は青(0,0,255)にして、ピクセルの色をu*A색 + v*B색 + w*C색で混ぜてください(プレースホルダーは、各頂点の色です)。

重心座標は、内外の判定にだけ使うものではありません。頂点に付いたどんな値でも、同じ係数で混ぜればよいのです。色、テクスチャ座標、法線、深度は、すべて同じ方式です。

チャンネルごとに別々に混ぜます。r = u*255 + v*0 + w*0のようにです。

重心座標の3つがそれぞれ1/3である場所(三角形の重心)では、3つのチャンネルがすべて85前後になり、灰色に見えます。確認してみてください。

深度バッファーで前後を決める

/root/raster/zbuf.pyで、/root/raster/out/zbuffer.png(256x256、黒い背景)を作ってください。三角形Aは、(30,30),(200,30),(30,200)で、青(60,60,255)、深度0.2、三角形Bは、(60,60),(230,60),(60,230)で、黄(255,220,60)、深度0.8です。ピクセルごとに深度バッファーを置き、より小さい深度が勝ちます。

深度バッファーは、画面と同じサイズの実数の配列です。最初は、とても大きな値(例: float("inf"))で埋めます。

ピクセルを塗る前に、z < zbuf[y][x]かどうかを見て、そのときだけ、色と深度をあわせて書きます。深度を更新しないと、あとで描いたものが無条件に勝ちます。

ここでは、三角形ごとに深度が一定ですが、実際のレンダラーは、深度も重心座標で補間します。このステップの要点は、描く順序と無関係に、同じ絵が出ることです。

深度だけを入れ替える

三角形の位置と色はそのままにして、深度だけを入れ替えて(Aを0.8、Bを0.2)、/root/raster/out/zswap.pngを作ってください。

コードは、ほとんどそのままです。深度の値2つを、互いに入れ替えるだけです。

2つの絵を並べて見てください。重なる領域の色だけが変わり、残りはまったく同じです。深度バッファーがすることが、まさにそれです。ピクセル単位で前後を決めます。

三角形を描く順序を変えても、結果が同じかどうか、試してみてください。同じなら正常です。その順序への非依存性が、Zバッファーを使う本当の理由です。

裏面を選んで捨てる

/root/raster/tris.txtの6つの三角形を読み、画面座標の符号付きの面積が負のものだけを、/root/raster/out/cull.png(256x256、黒い背景)に自分の色で塗りつぶし、/root/raster/out/07-cull.txtに、total=、drawn=、culled=と、t1=front|backからt6=までの、9行を書いてください。

符号付きの面積は、次のように求めます。

signed_area = ((Bx-Ax)*(Cy-Ay) - (Cx-Ax)*(By-Ay)) / 2

負なら表面(front)、正なら裏面(back)とみなします。画面座標はyが下に向かって増えるので、符号が、数学の授業の慣習とは逆に読まれます。

tris.txtの各行は、x0 y0 x1 y1 x2 y2 r g bの9つの整数です。split()で切って使えば済みます。

閉じた物体では、裏面はどのみち表面に隠れるので、この符号1つで、三角形の半分を、ラスタライズの前に捨てられます。