超素朴なやり方で、ビットマップ上に太さのある線分を描く

背景

HTMLのCanvas要素を使ってビットマップベースのお絵かきアプリケーション的なものを作っていました。

Canvasには基本的な図形描画のAPIがいくつかありますが、一つ重大な問題がありました。
それは、アンチエイリアスがかかってしまうことです。

ビットマップ上に絵を描くとき、塗りつぶしツールが欲しくなるのが人の常だと思いますが、アンチエイリアスがかかってしまうとこの「塗りつぶし」がうまく実装できません。

となると、ビットマップ上に図形を描画するAPIを自分で実装しなくてはなりません。

マウスなどでフリーハンドで線を描くときに必要なのは、線分を描くAPIです。
イベントが発生するたびに、前の座標から今の座標に線分を描きます。

というわけで、太さのある線分を描く処理を自分で実装することになりましたとさ。

やり方

基本方針

太さを$n$とします。
ビットマップ上で、線分からの距離が$\frac{n}{2}$以下の点を塗りつぶします。

はい、とても簡単です。

ちなみにこれを定義通り実装すると、端点が丸くなった線分が描画されますが、それは想定通りです。
端点を丸くすると、フリーハンドで描いた線が滑らかに見えるようになります。

また、そんな雑な実装でパフォーマンスは大丈夫なのか？と思われるかもしれません。
ところが今回のような用途では、一つ一つの線分はあまり長くならないため、富豪的な実装をしてもそこまで影響は大きくないようでした。(あくまで体感的なものです。)

実装のための考え方

まず、線分の2つの端点を$P_1 (x_1,y_1)$と$P_2 (x_2,y_2)$とします。
すると、2点を結ぶ直線の方程式は次のようになります。
(過程は省略しましたが、気になる人は導出してみてください。)

$$ax + by + c = 0 \\ \text{where} \quad a = y_1 - y_2, \: b = x_2 - x_1, \: c = x_1 y_2 - x_2 y_1$$

次に、任意の点$Q(x,y)$を考え、$Q$から直線$P_1 P_2$に垂線を引きます。
その垂線と$P_1 P_2$の交点を$R(x_0,y_0)$とします。

これも過程は省略しますが、連立方程式を解いて$R$の座標が次のように求まります。

$$x_0 = \frac{b^2 x - aby - ac}{a^2 + b^2} \\ y_0 = \frac{-abx + a^2 y - bc}{a^2 + b^2}$$

ところで、この$R$は線分$P_1 P_2$上にある場合と、そうでない場合があります。
線分上にあるかをどうやって判定すれば良いでしょうか？

そのために、ベクトルの内積を用います。
Rが線分上にある場合、$\overrightarrow{RP_1}$と$\overrightarrow{RP_2}$の内積は0以下になります。

$R$が線分上にあるかどうかが分かりました。
線分上にある場合は、$Q$と線分の距離は、$Q$と$R$の距離です。
線分上になり場合は、$Q$と線分の距離は、$Q$と$P_1$の距離または$Q$と$P_2$の距離のうち小さい方となります。

このようにして求めた$Q$と線分の距離を利用して、距離が$\frac{n}{2}$以下のピクセルに色を塗るというわけです。

実装

概ね上で説明したものをコードにしただけですが、大きなポイント(?)は、最初に描画する範囲を決めていることです。
線分の端点の座標と線の太さから、描画すべき座標の範囲を計算しています。(minX,minY,maxX,maxY)

(実際のアプリのコードをon the flyで修正して載せたので、間違いなどあったらすみません。)

function drawLine(
  imageData: ImageData,
  x1: number,
  y1: number,
  x2: number,
  y2: number,
  lineWidth: number,
  color: [number, number, number, number]
) {
  const { width, height, data } = imageData
  const w2 = lineWidth / 2
  const w22 = w2 * w2
  const minX = Math.round(Math.max(0, Math.min(x1, x2) - w2 - 1))
  const minY = Math.round(Math.max(0, Math.min(y1, y2) - w2 - 1))
  const maxX = Math.round(Math.min(width - 1, Math.max(x1, x2) + w2 + 1))
  const maxY = Math.round(Math.min(height - 1, Math.max(y1, y2) + w2 + 1))
  const a = y1 - y2
  const b = x2 - x1
  const c = x1 * y2 - x2 * y1
  const a2 = a * a
  const b2 = b * b
  const a2b2 = a2 + b2
  const ab = a * b
  const ac = a * c
  const bc = b * c
  for (let x = minX; x <= maxX; x++) {
    for (let y = minY; y <= maxY; y++) {
      const x0 = (b2 * x - ab * y - ac) / a2b2
      const y0 = (-ab * x + a2 * y - bc) / a2b2
      const vx1 = x0 - x1
      const vy1 = y0 - y1
      const vx2 = x0 - x2
      const vy2 = y0 - y2
      const isInside = vx1 * vx2 + vy1 * vy2 <= 0
      const distance = isInside
        ? norm2(x - x0, y - y0)
	: Math.min(norm2(x - x1, y - y1), norm2(x - x2, y - y2))
      if (distance <= w22) {
        const i = (x + y * width) * 4
	data[i + 0] = color[0]
	data[i + 1] = color[1]
	data[i + 2] = color[2]
	data[i + 3] = color[3]
      }
    }
  }
}

function norm2(x: number, y: number): number {
  return x * x + y * y
}

まとめ

かなり愚直なやり方で、ビットマップ上に太さのある線を描く方法を紹介しました。

線分との距離が一定の数値以下のピクセルを塗るというだけの本当に簡単なやり方です。
もしそのようなものを実装したい方がいたら、参考になれば幸いです。

おまけ

繰り返しのパターンを簡単に描けるWebアプリ Moyou(https://moyou.app) というものを作っています。
まだプロトタイプの段階ですが、描いた模様を保存したり、Web上で上で公開したりする機能を実装してリリースする予定です。
よければ、試してみてください。

ここで紹介した方法は、そのMoyouの描画処理の一部です。