Color Prism

塗りつぶし処理

CG

ラスタ化による図形の描画 では、ポリゴンの輪郭を画素として描く処理を見てきました。
続けて、その輪郭の内側を色で埋める塗りつぶし処理について見ていきます。

塗りつぶす領域
CG

塗りつぶし処理とは、ある境界で囲まれた領域の内側を、指定した色ですべて塗る処理であり、塗りつぶしの対象となるのは、境界となる画素で完全に囲まれた閉領域です。

境界が途切れていると、その隙間から塗りが外へ漏れ出し、本来塗るべきでない領域まで塗りつぶしてしまいます。そのため、塗りつぶしを正しく行うには、まず境界が閉じていることが前提になります。

閉領域であれば、内側のどこから塗り始めても、塗りが境界の手前で止まり、領域の外へはみ出しません。

スキャンライン塗りつぶし
CG

塗りつぶしにはいくつかの手法があり、その基本的な手法の1つがスキャンラインごとの塗りつぶしです。これは、行（水平な画素の列）を単位として、その行のうち図形の内側にあたる区間を一気に塗る手法です。

ポリゴンのラスタ化 では、スキャンライン（水平な走査線）をポリゴンの上端から下端まで1行ずつずらしながら、走査線がポリゴンの辺と交わる点を求めました。塗りつぶしでは、こうして求めた交点をもとに、内側にあたる区間を水平に塗っていきます。

1本のスキャンラインが塗りつぶし対象の閉領域と交わったとき、その交点は通常偶数個できます。

山が2つ並んだ形の領域を思い浮かべ、その上に1本のスキャンラインを左から右へ引いてみます。

左端から線をたどると、はじめは山の外（左側の地面）にいます。そのまま右へ進むと、

  • 1つ目の山の左の斜面とぶつかり、外から山の中（内側）へ入る
  • 1つ目の山の右の斜面を抜け、内側から山と山の間の谷（外側）へ出る
  • 2つ目の山の左の斜面とぶつかり、ふたたび外から内側へ入る
  • 2つ目の山の右の斜面を抜け、内側から外側へ出る

というように、斜面とぶつかる度に「外 → 内 → 外 → 内 → 外」と位置が交互に切り替わります。内か外かが切り替わる回数は、この矢印「→」の個数でわかります。つまり、線が斜面と交わる回数は4回（偶数回）です。

スキャンラインを左端からたどっていくと、はじめは領域の外側にいて、交点（＝境界との交わり）を越える度に、外から内、内から外へと位置が切り替わります。一度内側に入れば必ずどこかで外側へ出るので、交点は外と内を行き来した回数の分だけ、偶数個で揃うのです。

Action

たどった位置を右端まで動かし、走査線がポリゴンの輪郭を偶数回横切ることを確認しよう

Three.jsによる実装概要 
// 画像の広さ
const COLUMNS = 24
const ROWS = 16
const PITCH = 0.15
const PLOT_WIDTH = COLUMNS * PITCH
const PLOT_HEIGHT = ROWS * PITCH
const HALF_WIDTH = PLOT_WIDTH / 2
const HALF_HEIGHT = PLOT_HEIGHT / 2

// 塗りつぶす閉領域。山が 2 つ並んだ形をとる。
// 走査線は行の中心（行 + 0.5）を通るので、頂点の y を整数にとっておけば、
// 走査線が頂点の高さにちょうど重なることがない
const POLYGON: [number, number][] = [
  [2.5, 13],
  [7.5, 2],
  [11, 8],
  [14, 8],
  [17.5, 3],
  [21.5, 13]
]

// 走査線を引く位置と、左端からたどってきた位置
const SCAN_ROW = 7
const TRAVELED = 12.5

// xy 平面に重なる要素を、奥から手前へ少しずつ振り分ける z
const LAYER_FRAME = 0.01
const LAYER_SCANLINE = 0.02
const LAYER_TRAIL = 0.03
const LAYER_OUTLINE = 0.05
const LAYER_DOT = 0.07
const LAYER_MARKER = 0.08

// 画素を単位とした位置を、ワールド座標へ移す。
// 画像座標系は画像の左上を原点とし、x 軸を右向き、y 軸を下向きにとる。
// 整数が画素どうしの境目、+0.5 が画素の中心に当たる
const worldXOf = (x: number) => -HALF_WIDTH + x * PITCH
const worldYOf = (y: number) => HALF_HEIGHT - y * PITCH

// 走査線の高さ y で、ポリゴンの辺と交わる点の x を左から順に並べる。
// 水平な辺は走査線と交点を作らないので飛ばし、辺の上端を含み下端を含まない
// 範囲で数えることで、頂点の高さでも交点を二重に数えないようにする
const crossingsAt = (y: number) => {
  const xs: number[] = []

  for (let i = 0; i < POLYGON.length; i++) {
    const [x1, y1] = POLYGON[i]
    const [x2, y2] = POLYGON[(i + 1) % POLYGON.length]
    if (y1 === y2) continue
    if (y < Math.min(y1, y2) || y >= Math.max(y1, y2)) continue

    xs.push(x1 + ((y - y1) * (x2 - x1)) / (y2 - y1))
  }

  return xs.sort((a, b) => a - b)
}

const scanY = worldYOf(SCAN_ROW + 0.5)
const barGeometry = new PlaneGeometry(1, 1)
const matrix = new Matrix4()

// 画像の外周。走査線がどこから入ってどこへ抜けるかの目印になる
const frameGeometry = new BufferGeometry().setFromPoints([
  new Vector3(-HALF_WIDTH, HALF_HEIGHT, LAYER_FRAME),
  new Vector3(HALF_WIDTH, HALF_HEIGHT, LAYER_FRAME),
  new Vector3(HALF_WIDTH, HALF_HEIGHT, LAYER_FRAME),
  new Vector3(HALF_WIDTH, -HALF_HEIGHT, LAYER_FRAME),
  new Vector3(HALF_WIDTH, -HALF_HEIGHT, LAYER_FRAME),
  new Vector3(-HALF_WIDTH, -HALF_HEIGHT, LAYER_FRAME),
  new Vector3(-HALF_WIDTH, -HALF_HEIGHT, LAYER_FRAME),
  new Vector3(-HALF_WIDTH, HALF_HEIGHT, LAYER_FRAME)
])
scene.add(new LineSegments(frameGeometry, new LineBasicMaterial({ color: "#7d8794" })))

// 塗りつぶす閉領域の輪郭。切れ目なく閉じた線。
// 線材（LineBasicMaterial）の線幅は WebGL では常に 1 ドットに固定されるため、
// 輪郭・走査線・たどった区間は細長い長方形として描く
const outlineMaterial = new MeshBasicMaterial({ color: "#6fd8ff" })
POLYGON.forEach(([x1, y1], index) => {
  const [x2, y2] = POLYGON[(index + 1) % POLYGON.length]
  const ax = worldXOf(x1)
  const ay = worldYOf(y1)
  const bx = worldXOf(x2)
  const by = worldYOf(y2)

  const edge = new Mesh(barGeometry, outlineMaterial)
  edge.scale.set(Math.hypot(bx - ax, by - ay), 0.03, 1)
  edge.rotation.z = Math.atan2(by - ay, bx - ax)
  edge.position.set((ax + bx) / 2, (ay + by) / 2, LAYER_OUTLINE)
  scene.add(edge)
})

// 走査線そのもの。まだたどっていない部分は控えめな色で置いておく
const scanline = new Mesh(barGeometry, new MeshBasicMaterial({ color: "#5e6672" }))
scanline.scale.set(PLOT_WIDTH + 0.28, 0.02, 1)
scanline.position.set(0, scanY, LAYER_SCANLINE)
scene.add(scanline)

// 走査線と輪郭の交点。ここを越えるたびに外と内が入れ替わる
const crossings = crossingsAt(SCAN_ROW + 0.5)
const crossingDots = new InstancedMesh(
  new CircleGeometry(0.046, 16),
  new MeshBasicMaterial({ color: "#f5f8fc" }),
  crossings.length
)
crossings.forEach((x, index) => {
  matrix.identity()
  matrix.setPosition(worldXOf(x), scanY, LAYER_DOT)
  crossingDots.setMatrixAt(index, matrix)
})
scene.add(crossingDots)

// 左端から今いる位置までを、越えてきた交点で区切る
const passed = crossings.filter((x) => x < TRAVELED)
const bounds = [0, ...passed, TRAVELED]

// 区切られた区間を、外側と内側で塗り分ける。
// 内側をたどった区間は、このあと実際に塗られる区間なので、塗った画素と同じ色にする
const outsideTrail = new InstancedMesh(
  barGeometry,
  new MeshBasicMaterial({ color: "#c8ccd4" }),
  bounds.length
)
const insideTrail = new InstancedMesh(
  barGeometry,
  new MeshBasicMaterial({ color: "#ffc857" }),
  bounds.length
)

// 水平な区間 [left, right] を、走査線の高さに細長い長方形として置く
const setSpan = (trail: InstancedMesh, index: number, left: number, right: number) => {
  const ax = worldXOf(left)
  const bx = worldXOf(right)
  matrix.makeScale(Math.max(bx - ax, 0), 0.055, 1)
  matrix.setPosition((ax + bx) / 2, scanY, LAYER_TRAIL)
  trail.setMatrixAt(index, matrix)
}

// はじめは領域の外側にいて、交点を越えるたびに外と内が入れ替わる
let outsideCount = 0
let insideCount = 0
for (let i = 0; i + 1 < bounds.length; i++) {
  // 区切りを越えた回数が偶数なら外側、奇数なら内側
  if (i % 2 === 0) {
    setSpan(outsideTrail, outsideCount++, bounds[i], bounds[i + 1])
  } else {
    setSpan(insideTrail, insideCount++, bounds[i], bounds[i + 1])
  }
}
outsideTrail.count = outsideCount
insideTrail.count = insideCount
scene.add(outsideTrail)
scene.add(insideTrail)

// 走査線を左からたどっている、今の位置
const marker = new Mesh(new CircleGeometry(0.075, 24), new MeshBasicMaterial({ color: "#f2766a" }))
marker.position.set(worldXOf(TRAVELED), scanY, LAYER_MARKER)
scene.add(marker)

偶数個の交点を左から順に並べ、1番目と2番目の区間、3番目と4番目の区間、というように、奇数番目の交点から次の偶数番目の交点までの区間を塗れば、ちょうど内側だけを塗ることができます。スキャンラインごとにこの区間を塗っていけば、ポリゴンの内部全体が塗りつぶされます。

Action

交点が4個ある行では、1番目から2番目までと3番目から4番目までが塗られ、2番目から3番目まで（山と山の間）は塗られないことを確認しよう

Three.jsによる実装概要 
// 画素の格子
const COLUMNS = 24
const ROWS = 16
const PITCH = 0.15
const PLOT_WIDTH = COLUMNS * PITCH
const PLOT_HEIGHT = ROWS * PITCH

// 塗りつぶす閉領域。山が 2 つ並んだ形をとる。
// 走査線は画素の中心（行 + 0.5）を通るので、頂点の y を整数にとっておけば、
// 走査線が頂点の高さにちょうど重なることがない
const POLYGON: [number, number][] = [
  [2.5, 13],
  [7.5, 2],
  [11, 8],
  [14, 8],
  [17.5, 3],
  [21.5, 13]
]

// いま走査している行。この行の 1 つ上の行までは塗り終えた状態を描く
const SCAN_ROW = 7

// xy 平面に重なる要素を、奥から手前へ少しずつ振り分ける z
const LAYER_PIXEL = 0.01
const LAYER_CURRENT_PIXEL = 0.015
const LAYER_GRID = 0.02
const LAYER_SCANLINE = 0.05
const LAYER_OUTLINE = 0.06
const LAYER_DOT = 0.08

// 画素を単位とした位置を、ワールド座標へ移す。
// 画像座標系は画像の左上を原点とし、x 軸を右向き、y 軸を下向きにとる。
// 整数が画素どうしの境目、+0.5 が画素の中心に当たる
const worldXOf = (x: number) => -PLOT_WIDTH / 2 + x * PITCH
const worldYOf = (y: number) => PLOT_HEIGHT / 2 - y * PITCH

// 走査線の高さ y で、ポリゴンの辺と交わる点の x を左から順に並べる。
// 水平な辺は走査線と交点を作らないので飛ばし、辺の上端を含み下端を含まない
// 範囲で数えることで、頂点の高さでも交点を二重に数えないようにする
const crossingsAt = (y: number) => {
  const xs: number[] = []

  for (let i = 0; i < POLYGON.length; i++) {
    const [x1, y1] = POLYGON[i]
    const [x2, y2] = POLYGON[(i + 1) % POLYGON.length]
    if (y1 === y2) continue
    if (y < Math.min(y1, y2) || y >= Math.max(y1, y2)) continue

    xs.push(x1 + ((y - y1) * (x2 - x1)) / (y2 - y1))
  }

  return xs.sort((a, b) => a - b)
}

// 区間 [left, right) を塗る画素の列。
// 画素の中心は列 + 0.5 にあるので、中心が区間に入る列だけを塗る
const columnsIn = (left: number, right: number) => ({
  first: Math.max(0, Math.ceil(left - 0.5)),
  last: Math.min(COLUMNS - 1, Math.ceil(right - 0.5) - 1)
})

// 画素どうしの境目
const gridPoints: Vector3[] = []
for (let column = 0; column <= COLUMNS; column++) {
  const x = worldXOf(column)
  gridPoints.push(
    new Vector3(x, -PLOT_HEIGHT / 2, LAYER_GRID),
    new Vector3(x, PLOT_HEIGHT / 2, LAYER_GRID)
  )
}
for (let row = 0; row <= ROWS; row++) {
  const y = worldYOf(row)
  gridPoints.push(
    new Vector3(-PLOT_WIDTH / 2, y, LAYER_GRID),
    new Vector3(PLOT_WIDTH / 2, y, LAYER_GRID)
  )
}
const gridGeometry = new BufferGeometry().setFromPoints(gridPoints)
scene.add(new LineSegments(gridGeometry, new LineBasicMaterial({ color: "#7d8794" })))

const barGeometry = new PlaneGeometry(1, 1)
const matrix = new Matrix4()

// 行 row の塗る区間を画素で埋め、埋めた画素の数を返す。
// 交点を左から順に並べ、奇数番目の交点から次の偶数番目の交点までを塗る
const fillRow = (row: number, pixels: InstancedMesh, offset: number, z: number) => {
  const crossings = crossingsAt(row + 0.5)
  let painted = offset

  for (let i = 0; i + 1 < crossings.length; i += 2) {
    const { first, last } = columnsIn(crossings[i], crossings[i + 1])
    for (let column = first; column <= last; column++) {
      matrix.makeScale(PITCH, PITCH, 1)
      matrix.setPosition(worldXOf(column + 0.5), worldYOf(row + 0.5), z)
      pixels.setMatrixAt(painted++, matrix)
    }
  }

  return painted - offset
}

// 塗り終えた行の画素。今塗った区間と見分けるため、控えめな濃さにする。
// 塗った色をそのままの濃さで見せたいので、陰影の付かない材質にする
const pastPixels = new InstancedMesh(
  barGeometry,
  new MeshBasicMaterial({ color: "#ffc857", transparent: true, opacity: 0.45 }),
  COLUMNS * ROWS
)
let pastCount = 0
for (let row = 0; row < SCAN_ROW; row++) {
  pastCount += fillRow(row, pastPixels, pastCount, LAYER_PIXEL)
}
pastPixels.count = pastCount
scene.add(pastPixels)

// いま走査している行で、交点をもとに塗った区間の画素
const currentPixels = new InstancedMesh(
  barGeometry,
  new MeshBasicMaterial({ color: "#ffc857" }),
  COLUMNS
)
currentPixels.count = fillRow(SCAN_ROW, currentPixels, 0, LAYER_CURRENT_PIXEL)
scene.add(currentPixels)

// 塗りつぶす閉領域の輪郭。格子とは無関係に、切れ目なく閉じた線。
// 線材（LineBasicMaterial）の線幅は WebGL では常に 1 ドットに固定されるため、
// 図の主役である輪郭と走査線は細長い長方形として描く
const outlineMaterial = new MeshBasicMaterial({ color: "#6fd8ff" })
POLYGON.forEach(([x1, y1], index) => {
  const [x2, y2] = POLYGON[(index + 1) % POLYGON.length]
  const ax = worldXOf(x1)
  const ay = worldYOf(y1)
  const bx = worldXOf(x2)
  const by = worldYOf(y2)

  const edge = new Mesh(barGeometry, outlineMaterial)
  edge.scale.set(Math.hypot(bx - ax, by - ay), 0.03, 1)
  edge.rotation.z = Math.atan2(by - ay, bx - ax)
  edge.position.set((ax + bx) / 2, (ay + by) / 2, LAYER_OUTLINE)
  scene.add(edge)
})

// 走査線。画像を横切る 1 本の水平な線で、行を 1 つずらすたびに下へ動く
const scanline = new Mesh(barGeometry, new MeshBasicMaterial({ color: "#f2766a" }))
scanline.scale.set(PLOT_WIDTH + 0.28, 0.028, 1)
scanline.position.set(0, worldYOf(SCAN_ROW + 0.5), LAYER_SCANLINE)
scene.add(scanline)

// 走査線と輪郭の交点。この点の位置から、塗る区間が決まる
const crossings = crossingsAt(SCAN_ROW + 0.5)
const crossingDots = new InstancedMesh(
  new CircleGeometry(0.046, 16),
  new MeshBasicMaterial({ color: "#f5f8fc" }),
  crossings.length
)
crossings.forEach((x, index) => {
  matrix.identity()
  matrix.setPosition(worldXOf(x), worldYOf(SCAN_ROW + 0.5), LAYER_DOT)
  crossingDots.setMatrixAt(index, matrix)
})
scene.add(crossingDots)

スキャンライン塗りつぶしは、行単位でまとめて塗るため効率がよく、ポリゴンのように辺の方程式から交点を計算できる図形に適しています。

一方で、交点を計算で求めるこの方法は、複雑な形の領域には使えません。そうした任意の形の領域を塗るには、画素どうしの隣り合いをたどって塗りを広げていく、別の考え方が必要になります。その土台となるのが、次に見る連結性です。

連結性
CG

画素どうしの隣り合いをたどる塗りつぶしでは、「ある画素にとって、どの画素が近傍（隣）なのか」をあらかじめ決めておく必要があります。この隣接の捉え方を連結性といい、代表的なものに4連結と8連結の2通りがあります。

  • 4連結：上下左右の4方向の画素を隣とみなす
  • 8連結：上下左右に斜め4方向を加えた8方向の画素を隣とみなす

どちらを基準にするかで、塗りの広がり方が変わります。
4連結では斜めに接する画素へは塗りが伝わりませんが、8連結では斜め方向にも塗りが伝わっていきます。そのため、同じ領域でも、斜めに細く繋がった部分まで塗られるかどうかが連結性の選び方によって変わってきます。

Action

次の点に着目して、デモを動かしてみよう

  • たどった歩数を1にしたときに隣とみなされる画素は、4連結では上下左右の4つ、8連結では斜めを加えた8つになる
  • たどった歩数を2にすると、4連結でも斜めの画素に届く
  • たどった歩数を増やすと、4連結では菱形に、8連結では正方形に広がっていく
Three.jsによる実装概要 
// 画素の格子。中心の画素を 1 つに決められるよう、縦横は奇数個にとる
const CELLS = 7
const CENTER = (CELLS - 1) / 2
const PITCH = 0.33
const PLOT_SIZE = CELLS * PITCH
const HALF_SIZE = PLOT_SIZE / 2

// 2 つの格子のあいだの隙間
const GRID_GAP = 0.42

// 中心の画素から近傍を何歩たどったか
const STEPS = 1

// 近傍のとらえ方。中心の画素から見て、隣とみなす画素の列と行のずれ
const NEIGHBORS_4: [number, number][] = [
  [0, -1],
  [-1, 0],
  [1, 0],
  [0, 1]
]
const NEIGHBORS_8: [number, number][] = [
  ...NEIGHBORS_4,
  [-1, -1],
  [1, -1],
  [-1, 1],
  [1, 1]
]

// 左右に並べる 2 つの格子。同じ歩数でも、近傍のとらえ方で広がる形が変わる
const GRIDS = [
  { offsetX: -(PLOT_SIZE + GRID_GAP) / 2, neighbors: NEIGHBORS_4 },
  { offsetX: (PLOT_SIZE + GRID_GAP) / 2, neighbors: NEIGHBORS_8 }
]

// xy 平面に重なる要素を、奥から手前へ少しずつ振り分ける z
const LAYER_PIXEL = 0.01
const LAYER_CENTER_PIXEL = 0.015
const LAYER_GRID = 0.02

// 画素を単位とした位置を、格子の中心を原点とするワールド座標へ移す。
// 画像座標系は y 軸を下向きにとるので、行が増えるほど下へ下がる。
// 整数が画素どうしの境目、+0.5 が画素の中心に当たる
const localXOf = (x: number) => -HALF_SIZE + x * PITCH
const localYOf = (y: number) => HALF_SIZE - y * PITCH

// 中心の画素から近傍をたどって、steps 歩で届く画素を求める。
// いま届いたばかりの画素（frontier）の近傍へ、1 歩ずつ広げていく
const reachedWithin = (steps: number, neighbors: [number, number][]) => {
  const reached = Array.from({ length: CELLS }, () => Array.from({ length: CELLS }, () => false))
  reached[CENTER][CENTER] = true

  let frontier: [number, number][] = [[CENTER, CENTER]]

  for (let step = 0; step < steps; step++) {
    const next: [number, number][] = []

    for (const [column, row] of frontier) {
      for (const [dc, dr] of neighbors) {
        const c = column + dc
        const r = row + dr
        if (c < 0 || c >= CELLS || r < 0 || r >= CELLS) continue
        if (reached[r][c]) continue

        reached[r][c] = true
        next.push([c, r])
      }
    }

    frontier = next
  }

  return reached
}

// 画素どうしの境目。2 つの格子をまとめて 1 本のジオメトリに引く
const gridPoints: Vector3[] = []
GRIDS.forEach(({ offsetX }) => {
  for (let column = 0; column <= CELLS; column++) {
    const x = offsetX + localXOf(column)
    gridPoints.push(new Vector3(x, -HALF_SIZE, LAYER_GRID), new Vector3(x, HALF_SIZE, LAYER_GRID))
  }
  for (let row = 0; row <= CELLS; row++) {
    const y = localYOf(row)
    gridPoints.push(
      new Vector3(offsetX - HALF_SIZE, y, LAYER_GRID),
      new Vector3(offsetX + HALF_SIZE, y, LAYER_GRID)
    )
  }
})
const gridGeometry = new BufferGeometry().setFromPoints(gridPoints)
scene.add(new LineSegments(gridGeometry, new LineBasicMaterial({ color: "#7d8794" })))

const barGeometry = new PlaneGeometry(1, 1)
const matrix = new Matrix4()

// 近傍をたどって届いた画素。2 つの格子で色は同じなので、まとめて 1 つに確保しておく。
// 塗った色をそのままの濃さで見せたいので、陰影の付かない材質にする
const reachedPixels = new InstancedMesh(
  barGeometry,
  new MeshBasicMaterial({ color: "#ffc857" }),
  CELLS * CELLS * GRIDS.length
)
let painted = 0
GRIDS.forEach(({ offsetX, neighbors }) => {
  const reached = reachedWithin(STEPS, neighbors)

  for (let row = 0; row < CELLS; row++) {
    for (let column = 0; column < CELLS; column++) {
      if (!reached[row][column]) continue
      // 中心の画素は別の色で描くので、ここでは重ねない
      if (row === CENTER && column === CENTER) continue

      matrix.makeScale(PITCH, PITCH, 1)
      matrix.setPosition(offsetX + localXOf(column + 0.5), localYOf(row + 0.5), LAYER_PIXEL)
      reachedPixels.setMatrixAt(painted++, matrix)
    }
  }
})
reachedPixels.count = painted
scene.add(reachedPixels)

// たどり始める中心の画素。届いた画素と見分けるため、別の色で描く
const centerMaterial = new MeshBasicMaterial({ color: "#f2766a" })
GRIDS.forEach(({ offsetX }) => {
  const centerPixel = new Mesh(barGeometry, centerMaterial)
  centerPixel.scale.set(PITCH, PITCH, 1)
  centerPixel.position.set(
    offsetX + localXOf(CENTER + 0.5),
    localYOf(CENTER + 0.5),
    LAYER_CENTER_PIXEL
  )
  scene.add(centerPixel)
})

シードフィル
CG

連結性が決まれば、ある画素から隣の画素へ塗りを伝えていく処理を組み立てられます。その代表的な手法がシードフィル（flood fill）です。

シードフィルでは、塗りつぶしの出発点となる1つの画素をシード点として与え、次の操作を繰り返します。

  1. シード点から始めて、隣接する画素を調べる
  2. 境界でなければ塗り色で塗る
  3. さらにそこから隣接する画素を調べる

塗れる画素がなくなるまで続けると、シード点を含む閉領域全体が塗りつぶされます。

境界色基準と連結性

ここで「その画素を塗ってよいか（境界に達していないか）」をどう判定するかによって、シードフィルには2つの方式があります。

境界色基準

あらかじめ決めた境界色に出会うまで塗り進める方式

  • 止まる判定：隣接画素が境界色なら、そこで止まる
  • 向いている場面：輪郭がはっきり1色で描かれている場合

内部色基準

塗り始める前の内部の色と同じ画素だけを塗る方式

  • 止まる判定：色が変わったところを領域の端とみなして止まる
  • 向いている場面：特定の色の領域だけを別の色で塗り替えたい場合

また、隣接画素の判定を4連結にするか8連結にするかによっても、塗りの広がり方が変わります。隣の画素へと塗りを広げるシードフィルは、連結性の取り決めの上に成り立っているのです。

Action

波及の歩数を進めると、シード点から隣へと塗りが広がり、どの画素で止まるかを見てみよう

  • 判定の基準によって、部屋を横切る別の色の部分を塗り替えて向こう側まで進むか、そこで遮られるかが変わる
  • 連結性を8連結にすると、斜めに進むことができるようになり、右下の部屋まで塗りが広がる
Three.jsによる実装概要 
// 盤面。B が境界の画素、. が塗る前の内部の色、O が内部にある別の色の部分、- が領域の外。
// 左上の部屋は別の色の帯で上下に仕切られていて、右下の部屋とは
// 角どうしが斜めに触れているだけで繋がっている
const BOARD = [
  "----------------",
  "--BBBBBBBB------",
  "--B......B------",
  "--B......B------",
  "--BOOOOOOB------",
  "--B......B------",
  "--B......BBBBB--",
  "--BBBBBBB....B--",
  "--------B....B--",
  "--------B....B--",
  "--------B....B--",
  "--------BBBBBB--",
  "----------------"
]

// 塗りつぶしの出発点となるシード点（列, 行）。帯より下の側に置く
const SEED: [number, number] = [3, 6]

// 画素の格子
const ROWS = BOARD.length
const COLS = BOARD[0].length
const PITCH = 0.2
const PLOT_WIDTH = COLS * PITCH
const PLOT_HEIGHT = ROWS * PITCH

// 近傍のとらえ方。いま見ている画素から見て、隣とみなす画素の列と行のずれ
const NEIGHBORS_4: [number, number][] = [
  [0, -1],
  [-1, 0],
  [1, 0],
  [0, 1]
]
const NEIGHBORS_8: [number, number][] = [
  ...NEIGHBORS_4,
  [-1, -1],
  [1, -1],
  [-1, 1],
  [1, 1]
]

// 判定の基準（境界色基準）と近傍のとらえ方（4 連結）、シード点からたどった歩数
const CRITERION = "boundary"
const NEIGHBORS = NEIGHBORS_4
const STEPS = 0

// xy 平面に重なる要素を、奥から手前へ少しずつ振り分ける z
const LAYER_CELL = 0.01
const LAYER_FILL = 0.015
const LAYER_FRONTIER = 0.02
const LAYER_GRID = 0.025
const LAYER_SEED = 0.05

// 画素を単位とした位置を、ワールド座標へ移す。
// 画像座標系は画像の左上を原点とし、x 軸を右向き、y 軸を下向きにとる。
// 整数が画素どうしの境目、+0.5 が画素の中心に当たる
const worldXOf = (x: number) => -PLOT_WIDTH / 2 + x * PITCH
const worldYOf = (y: number) => PLOT_HEIGHT / 2 - y * PITCH

// 画素 (column, row) を塗ってよいか。
// 境界色基準は境界色でなければ塗り進め、内部色基準は塗り始める前の内部の色と同じ画素だけを塗る
const canFill = (column: number, row: number) => {
  const cell = BOARD[row][column]
  return CRITERION === "boundary" ? cell !== "B" : cell === "."
}

// シード点から近傍をたどって、steps 歩で塗れた画素と、いま広がった先端を求める。
// 隣接する画素を順に調べ、塗ってよければ塗り、そこからさらに隣接する画素を調べる
const spreadFrom = (steps: number) => {
  const filled = Array.from({ length: ROWS }, () => Array.from({ length: COLS }, () => false))
  filled[SEED[1]][SEED[0]] = true

  let frontier: [number, number][] = [SEED]

  for (let step = 0; step < steps; step++) {
    const next: [number, number][] = []

    for (const [column, row] of frontier) {
      for (const [dc, dr] of NEIGHBORS) {
        const c = column + dc
        const r = row + dr
        if (c < 0 || c >= COLS || r < 0 || r >= ROWS) continue
        // すでに塗ってあればやり直さない
        if (filled[r][c]) continue
        // 境界に達していたら塗らない
        if (!canFill(c, r)) continue

        filled[r][c] = true
        next.push([c, r])
      }
    }

    frontier = next
  }

  return { filled, frontier }
}

const cellGeometry = new PlaneGeometry(1, 1)
const matrix = new Matrix4()

// 盤面のうち、文字が cell の画素をまとめて置く。
// 塗った色をそのままの濃さで見せたいので、陰影の付かない材質にする
const placeCells = (cell: string, color: string) => {
  const cells = new InstancedMesh(cellGeometry, new MeshBasicMaterial({ color }), COLS * ROWS)

  let placed = 0
  for (let row = 0; row < ROWS; row++) {
    for (let column = 0; column < COLS; column++) {
      if (BOARD[row][column] !== cell) continue

      matrix.makeScale(PITCH, PITCH, 1)
      matrix.setPosition(worldXOf(column + 0.5), worldYOf(row + 0.5), LAYER_CELL)
      cells.setMatrixAt(placed++, matrix)
    }
  }
  cells.count = placed
  scene.add(cells)
}

placeCells("B", "#6fd8ff")
placeCells(".", "#4a5160")
placeCells("O", "#a58bd8")

// 画素どうしの境目
const gridPoints: Vector3[] = []
for (let column = 0; column <= COLS; column++) {
  const x = worldXOf(column)
  gridPoints.push(
    new Vector3(x, -PLOT_HEIGHT / 2, LAYER_GRID),
    new Vector3(x, PLOT_HEIGHT / 2, LAYER_GRID)
  )
}
for (let row = 0; row <= ROWS; row++) {
  const y = worldYOf(row)
  gridPoints.push(
    new Vector3(-PLOT_WIDTH / 2, y, LAYER_GRID),
    new Vector3(PLOT_WIDTH / 2, y, LAYER_GRID)
  )
}
const gridGeometry = new BufferGeometry().setFromPoints(gridPoints)
scene.add(new LineSegments(gridGeometry, new LineBasicMaterial({ color: "#7d8794" })))

// 塗った画素と、そのうち直前の 1 歩で広がった先端
const { filled, frontier } = spreadFrom(STEPS)
const onFrontier = Array.from({ length: ROWS }, () => Array.from({ length: COLS }, () => false))
frontier.forEach(([column, row]) => {
  onFrontier[row][column] = true
})

const fillPixels = new InstancedMesh(
  cellGeometry,
  new MeshBasicMaterial({ color: "#ffc857" }),
  COLS * ROWS
)
const frontierPixels = new InstancedMesh(
  cellGeometry,
  new MeshBasicMaterial({ color: "#f2766a" }),
  COLS * ROWS
)
let fillPlaced = 0
let frontierPlaced = 0

for (let row = 0; row < ROWS; row++) {
  for (let column = 0; column < COLS; column++) {
    if (!filled[row][column]) continue

    const isFrontier = onFrontier[row][column]
    matrix.makeScale(PITCH, PITCH, 1)
    matrix.setPosition(
      worldXOf(column + 0.5),
      worldYOf(row + 0.5),
      isFrontier ? LAYER_FRONTIER : LAYER_FILL
    )

    if (isFrontier) {
      frontierPixels.setMatrixAt(frontierPlaced++, matrix)
    } else {
      fillPixels.setMatrixAt(fillPlaced++, matrix)
    }
  }
}
fillPixels.count = fillPlaced
frontierPixels.count = frontierPlaced
scene.add(fillPixels, frontierPixels)

// 塗りつぶしの出発点。塗られたあとも位置が分かるように、点で重ねておく
const seedDot = new Mesh(
  new CircleGeometry(0.055, 16),
  new MeshBasicMaterial({ color: "#f5f8fc" })
)
seedDot.position.set(worldXOf(SEED[0] + 0.5), worldYOf(SEED[1] + 0.5), LAYER_SEED)
scene.add(seedDot)

塗りつぶしの手順を擬似コードで表すと、次のようになります。隣接画素を未処理の画素の集まりに入れておき、1つずつ取り出して塗っていきます。

push(seed)  // シード点を未処理の集まりに入れる
while 未処理の画素がある:
    p <- pop()  // 未処理の画素を 1 つ取り出す
    if is_boundary(p):  // 境界に達していたら塗らない
        continue
    if is_filled(p):  // すでに塗ってあればやり直さない
        continue
    fill(p)  // 画素 p を塗り色で塗る
    for q in neighbors(p):  // p の隣接画素（4 連結 or 8 連結）
        push(q)  // 隣接画素を未処理の集まりに加える

スキャンライン塗りつぶしとの比較

スキャンライン塗りつぶしとシードフィルは、塗りつぶしたい領域の性質に応じて使い分けられます。

  • スキャンライン塗りつぶし：辺の方程式から交点を計算できるポリゴン向き
  • シードフィル：境界の形を問わず、複雑に入り組んだ領域でも塗りつぶせる