地図/気まぐれ/3Dの作り方

隠面消去 — 画家と Z バッファ

順方向で立体を塗ると、奥の面を手前の面で隠す問題が出る。いちばん素朴なのは画家のアルゴリズムで、面を奥行きでソートして遠い順に塗り、手前を上書きする。凸な立体なら正しく、CanvasRenderingContext2Dfill だけで立体になる。

画家のアルゴリズムは面のソートで前後を表すが、面どうしが貫通したり重なり順が循環すると、どんな順序でも正しく塗れない。これを画素単位で解くのが Z バッファ——各画素に現在もっとも手前の奥行きを記録し、それより奥の画素を捨てる。Edwin Catmull が 1974 年の博士論文で導入し、いまの GPU はこれをハードウェアで持つ。背面除去(裏を向いた面を描かない)は、凸多面体なら隠面消去の半分を肩代わりする。

work は立方体と八面体を回し、面を奥から塗って、法線と光の内積で陰影をつけている。面を重心の奥行きでソートする一行が画家のアルゴリズムで、これを外すと立体が裏返る。手順は立体を回すに分けて書いた。