shigureni.dev

奥から塗る — 画家のアルゴリズム

面を塗る順番で前後を表す。奥の面から先に塗り、手前の面を後で塗ると、手前が奥を上書きして隠す。画家が背景から前景へ塗り重ねるのと同じ手順。面を奥行きで並べ替えるだけ。

画家のアルゴリズムは、面を視点からの距離（普通は重心の奥行き）でソートし、遠い順に塗る。実装が単純で、凸多面体なら正しい結果になる。ただし限界がある——面どうしが貫通していたり、A が B の手前で B が C の手前で C が A の手前、のように重なり順が循環すると、どんな順序でも正しく塗れない。これを画素単位で解くのが Z バッファで、各画素に現在最も手前の奥行きを記録し、それより奥の画素は捨てる。Edwin Catmull が 1974 年の博士論文で導入した。ハードウェアの GPU は Z バッファを使うので、面の事前ソートは要らない。CanvasRenderingContext2D には画素ごとの奥行き判定がないので、面のソートで近似する。

立方体の六面を重心の奥行きでソートし、奥から塗る。面ごとに違う明度を割り当てて、どの面が手前に来ているかを見せる。

export default (c) => {
  const w = c.canvas.width
  const h = c.canvas.height
  const cx = w / 2
  const cy = h / 2
  const r = Math.min(w, h) * 0.2
  const camZ = Math.min(w, h) * 0.85
  const focal = Math.min(w, h) * 0.95
  let t = 0

const verts = []
  for (let i = 0; i < 8; i++) {
    verts.push([(i & 1) * 2 - 1, ((i >> 1) & 1) * 2 - 1, ((i >> 2) & 1) * 2 - 1])
  }
  const faces = [
    [1, 3, 7, 5],
    [0, 4, 6, 2],
    [2, 6, 7, 3],
    [0, 1, 5, 4],
    [4, 5, 7, 6],
    [0, 2, 3, 1],
  ]
  const shades = [60, 95, 130, 160, 190, 220]

const project = (v, ca) => {
    const x = v[0] * r
    const y = v[1] * r
    const z = v[2] * r
    const x1 = x * ca.cy - z * ca.sy
    const z1 = x * ca.sy + z * ca.cy
    const y2 = y * ca.cx - z1 * ca.sx
    const z2 = y * ca.sx + z1 * ca.cx
    const s = focal / (camZ + z2)
    return [cx + x1 * s, cy - y2 * s, z2]
  }

return () => {
    t += 0.013
    const ca = { cy: Math.cos(t), sy: Math.sin(t), cx: Math.cos(t * 0.55), sx: Math.sin(t * 0.55) }
    const proj = verts.map((v) => project(v, ca))

const polys = faces.map((f, fi) => {
      let zc = 0
      for (const i of f) zc += proj[i][2]
      return { f, zc: zc / f.length, shade: shades[fi] }
    })
    polys.sort((p, q) => q.zc - p.zc) // 奥(z 大)から

c.fillStyle = colors.paper
    c.fillRect(0, 0, w, h)

for (const poly of polys) {
      c.beginPath()
      for (let i = 0; i < poly.f.length; i++) {
        const p = proj[poly.f[i]]
        if (i === 0) c.moveTo(p[0], p[1])
        else c.lineTo(p[0], p[1])
      }
      c.closePath()
      c.fillStyle = colors.tint(poly.shade)
      c.fill()
      c.strokeStyle = colors.tint(8)
      c.lineWidth = 1.5
      c.stroke()
    }
  }
}

polys.sort((p, q) => q.zc - p.zc) が肝で、重心の奥行き zc が大きい（奥の）面を先に塗る。この一行を消すと、面が定義順のまま塗られて、奥の面が手前の面を上書きして立体が裏返ったり穴が空いたりする。面ごとの固定明度は塗り順を見せるための便宜で、本当の陰影ではない。回すと手前に来た面が後から塗られて、箱に見える。