shigureni.dev

線のラスタライズ — Bresenham

格子に直線を引きたい。始点と終点を結ぶ直線の式は y = 始点 + 傾き × (x - 始点) で、x を一つ進めるたびに y を傾きぶん足す。けれど傾きは割り算で出る小数で、各セルでは Math.round の丸めが要る。格子の各マスを整数の足し引きだけで決めたい。

Bresenham のアルゴリズムは、直線を引くのに割り算も浮動小数も使わない。傾きの代わりに整数の誤差項 err を一つ持ち、x を一歩進めるごとに err へ dy を足す。err が閾値を越えたら y を一歩進め、err を dx ぶん戻す。理想の直線から今のマスがどれだけ離れているかを err が整数で覚えていて、離れすぎる前に縦へ寄せる。Jack Bresenham が 1962 年に IBM のプロッタ制御のために考案した。

始点と終点を格子座標で決めて、err を足し引きしながら一マスずつ進める。dx は横の距離、dy は縦の距離を負にしたもの。e2 = 2 * err を dy・dx と比べて、越えた向きへ一歩動かす。塗るのは面なので cellW = w / n・cellH = h / n でマスを埋める。終点に着いたら別の終点で引き直す。

export default (c) => {
  const w = c.canvas.width
  const h = c.canvas.height
  const n = 48
  const cellW = w / n
  const cellH = h / n

let line = null

const makeLine = () => {
    const x0 = 6
    const y0 = Math.floor(n / 2)
    const x1 = n - 6
    const y1 = 8 + Math.floor(Math.random() * (n - 16))
    const dx = Math.abs(x1 - x0)
    const dy = -Math.abs(y1 - y0)
    return {
      x: x0,
      y: y0,
      x1,
      y1,
      dx,
      dy,
      sx: x0 < x1 ? 1 : -1,
      sy: y0 < y1 ? 1 : -1,
      err: dx + dy,
      done: false,
    }
  }

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

return () => {
    if (line === null || line.done) {
      c.fillStyle = colors.paper
      c.fillRect(0, 0, w, h)
      line = makeLine()
    }

c.fillStyle = colors.tint(40)
    c.fillRect(line.x * cellW, line.y * cellH, cellW + 1, cellH + 1)

if (line.x === line.x1 && line.y === line.y1) {
      line.done = true
      return
    }

const e2 = 2 * line.err
    if (e2 >= line.dy) {
      line.err += line.dy
      line.x += line.sx
    }
    if (e2 <= line.dx) {
      line.err += line.dx
      line.y += line.sy
    }
  }
}

毎フレーム一マスずつ塗られて、始点から終点へ階段状に伸びる。err が横へ進むたびに減り、dx を越えると縦に一歩寄って dy ぶん戻る。傾きが緩いと横ばかり進んで縦の段が間遠になり、急だと縦の段が詰まる。割り算は一度も出ず、足し引きと比較だけでマスが決まる。終点へ届いたら新しい終点で引き直す。

中心から複数の終点へ同じ手順で引くと放射状になる。一本ぶんの x・y・err を線ごとに別々に持って、各フレームで全部を一歩ずつ進める。終点は角度 a を cos・sin で円周に並べて決める。sin(phase * 1.7 + i) を角度に混ぜて散らし、全本が着いたら phase を進めて引き直す。

export default (c) => {
  const w = c.canvas.width
  const h = c.canvas.height
  const n = 64
  const cellW = w / n
  const cellH = h / n
  const cx = Math.round(n / 2)
  const cy = Math.round(n / 2)
  const spokes = 12
  const radius = n * 0.42
  let phase = 0
  let lines = []

const makeLine = (i) => {
    const a = phase + (i / spokes) * Math.PI * 2 + Math.sin(phase * 1.7 + i) * 0.5
    const x1 = Math.round(cx + Math.cos(a) * radius)
    const y1 = Math.round(cy + Math.sin(a) * radius)
    const dx = Math.abs(x1 - cx)
    const dy = -Math.abs(y1 - cy)
    return {
      x: cx,
      y: cy,
      x1,
      y1,
      dx,
      dy,
      sx: cx < x1 ? 1 : -1,
      sy: cy < y1 ? 1 : -1,
      err: dx + dy,
      done: false,
    }
  }

for (let i = 0; i < spokes; i++) lines.push(makeLine(i))

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

return () => {
    c.fillStyle = colors.tintAlpha(238, 0.05)
    c.fillRect(0, 0, w, h)

let allDone = true
    for (const ln of lines) {
      if (ln.done) continue
      allDone = false

if (ln.x >= 0 && ln.x < n && ln.y >= 0 && ln.y < n) {
        c.fillStyle = colors.tint(40)
        c.fillRect(ln.x * cellW, ln.y * cellH, cellW + 1, cellH + 1)
      }

if (ln.x === ln.x1 && ln.y === ln.y1) {
        ln.done = true
        continue
      }

const e2 = 2 * ln.err
      if (e2 >= ln.dy) {
        ln.err += ln.dy
        ln.x += ln.sx
      }
      if (e2 <= ln.dx) {
        ln.err += ln.dx
        ln.y += ln.sy
      }
    }

if (allDone) {
      phase += 0.4
      const next = []
      for (let i = 0; i < spokes; i++) next.push(makeLine(i))
      lines = next
    }
  }
}

同じ誤差項の足し引きが線の本数ぶん並走して、中心から放射状に伸びる。半透明の paper を毎フレーム上から塗っているので、伸びた跡が尾を引いて薄れる。終点の角度を cos・sin で円周に置くだけで、上向きも斜めも同じ手順で引ける。spokes を増やすと線が密に、radius を上げると長く伸びる。

横を一歩進めるたびに整数の誤差を足し、閾値を越えたら縦へ一歩寄る——丸めも割り算もない足し引きだけで、格子の上に直線が立つ。