塗りつぶし処理

ラスタ化による図形の描画 では、ポリゴンの輪郭を画素として描く処理を見てきましたが、その内部を塗りつぶす処理については触れていませんでした。
ここでは、ある領域の内側を色で埋める塗りつぶし処理について見ていきます。

塗りつぶす領域

CG

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

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

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

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

CG

塗りつぶしにはいくつかの手法があります。

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

ポリゴンのスキャンライン処理 では、スキャンライン（水平な走査線）をポリゴンの上端から下端まで1行ずつずらしながら、走査線がポリゴンの辺と交わる点を求めました。

塗りつぶしでは、こうして求めた交点をもとに、内側にあたる区間を水平に塗っていきます。

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

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

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

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

連結性

CG

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

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

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

シードフィル

CG

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

シードフィルでは、塗りつぶしの出発点となる1つの画素をシード点として与えます。
シード点から始めて、隣接する画素を順に調べ、境界でなければ塗り色で塗り、さらにそこから隣接する画素を調べる、という操作を繰り返します。塗れる画素がなくなるまで続けると、シード点を含む閉領域全体が塗りつぶされます。

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

• 境界色基準：あらかじめ決めた境界色に出会うまで塗り進める方式。隣接画素が境界色なら、そこで止まる
• 内部色基準：塗り始める前の内部の色と同じ画素だけを塗る方式。色が変わったところを領域の端とみなして止まる

境界色基準は、輪郭がはっきり1色で描かれている場合に向いています。内部色基準は、特定の色の領域だけを別の色で塗り替えたい場合に向いています。

塗りつぶしの手順を擬似コードで表すと、次のようになります。隣接画素を未処理の画素の集まりに入れておき、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)  // 隣接画素を未処理の集まりに加える

neighbors(p)が返す隣接画素を4連結にするか8連結にするかで、塗りの広がり方が変わります。このように、シードフィルは連結性の取り決めの上に成り立っています。

シードフィルは境界の形を問わず、複雑に入り組んだ領域でも塗れる柔軟さをもちます。

辺の方程式から交点を計算できるポリゴンにはスキャンライン塗りつぶしが効率的で、それ以外の任意の形をした領域にはシードフィルが向いている、というように、塗りつぶしたい領域の性質に応じてこれらの手法は使い分けられます。