04/17 15:14 シードフィルというのは「注目点のピクセルを塗る→上下左右の隣のピクセルが境界色でなければそこを新しい注目点にする」をずっと（再帰的に）繰り返すことで、閉空間が塗り潰せてしまうというアルゴリズムのことなのだが、これが奥が深い…
(rido)
04/17 15:50 まず「次に注目する点の探索（スキャン）」。既に塗り潰したところをまたスキャンするのは大変もったいないので、それを減らすことが最初の課題になる。そこで、ライン単位に分解して効率化しよう…ということになる
(gizi)
04/17 15:50 次に「再帰的に繰り返す」作業はスタックを使うのが一般的だが、「再帰で書けることの多くはキューで書いたほうが効率がいい」の法則の通り、シードフィルもこれに従うことが多い
(gizu)
04/17 15:50 また、その世代の多くのパソコンはスキャンのためのメモリすら貴重だったくらいで、境界・塗り潰し判定用のオフスクリーンバッファなぞ考えようもなかった。よって、表示バッファ（VRAM）から境界色を直接読み出し、塗り潰し色を直接描き込む必要があった
(gize)
04/17 15:50 当時のVRAMは「横8pxで１バイト、それを数プレーン重ねることで多色化」という構造が一般的だったので、ここから１ピクセルの境界色を読み出し、また１ピクセルの塗り潰し色を描き込むのに「何バイトもアクセスしては論理演算を繰り返す」必要があり、これをいかに効率化するかの手腕が問われた
(gizo)
04/17 15:50 更にはこの「何バイトもアクセスしては論理演算を繰り返す」部分がハードウェア支援されるようになり、特定の手法でアクセスすることで単純化できるようになった。いかにこの機能を使いこなすかの手腕も問われるように (gida)
04/17 15:50 また、多色が扱える環境では、「境界色を１つじゃなくて複数選びたい」「塗り潰しも１色じゃなくてタイルパターンを扱いたい」という要求が生まれて、複雑化していく
(gidi)
04/17 15:50 ということで、「高機能のシードフィルを効率よく実装する」ことは、単純な考えから始められて、かつ多方面のアルゴリズムやハードウェア知識を要求されるテーマたりうるのであった… :D
(gidu)
04/17 15:50 もっとも、今なら大抵のことは「対象サーフェスから境界ピクセルを抽出したサーフェスを作成」「そのサーフェスに対して単純なシードフィル」「シードフィルしたサーフェスをマスクにして、描き込みたい画像を合成」で済んじゃうんだけどね… :D
(gide)
04/17 15:56 余談：効率的なシードフィルを試験するための「複雑な閉空間」を用意する手段として、迷路を生成する手法を覚えると便利。確か初代PC-8801なんかでこの迷路画像にPAINT命令を仕掛けると、スタックオーバーフローで死んだりするんだ…（苦笑
(gudu)