面は塗りつぶしで作る

初期のパソコンのグラフィック画面はVRAMに点や線をひとつずつ描いていたのですが、これだといわゆる「線画」にしかなりません。最初のスター・ウォーズの戦闘機で出てきた目標を示すコンピュータ・グラフィックスも、そんな感じでした。当時のCPUの能力ではリアルタイムに処理するのは、そのくらいが精一杯だったんですよね。

Star Wars for the Apple II (映画は版権がうるさそうなのゲームのほうで)

ですからゲームなどでは苦しいのですが、グラフを描けば中を塗りつぶしたくなります。単純な図形であれば方程式を解いて、ある点が図形の内側か否かを判定して点を打っていくことも不可能ではないですが、パックマンのような欠けている円になった途端、方程式も複雑になりすぎます。そんな訳である点を指定して、そこから境界となる線というか点を見つけるまでの領域を塗りつぶす方法で面を描くということが一般的になりました。

これがBASICのPAINT命令です。調べた限りでは、この命令が初めて実装されたのがFM-8のようです。まあ、それ以前のPCは点のひとつひとつに独立した色を付けることができなかったので、まあその頃なんだと思います。PAINT命令も機種ごとのバリエーションがあるのですが、起点となる座標を指定し、塗りつぶす色と境界の色をしていするものが普通です。機種によっては特定の色ではなくパターンで塗りつぶすことも出来たようです。

さて、いったいどんな方法で塗りつぶしを実現していたのでしょうか。当時コードを解析したことは無かったのですが、塗るのが目に見える速度だったので、何かをスタックに積みながら処理をしているんだろうなというところだけは想像していました。

ペイント・ルーチン

閉領域の塗り潰し

この命令は論理的な計算をするのではなく、実際にメモリに書き込まれた境界色の点を探すので、複数の線を繋ぐときの繋目や円周や円弧が途切れていて隙間があると、そこから「漏れて」境界と指定したつもりの線を超えて塗りつぶし始めるのが見ていてもわかりました。新しいパソコンが登場すると、まずPAINTを実行させて今度の機種はこれだけ高速になったぞと言っていたのですが、正直に言ってそれでも五十歩百歩でしたね。

という訳でグラフを描くには間に合うものの、数あるBASICの命令の中ではもっとも遅い命令ではないかと思われるほどのパフォーマンスだったので、なかなか使いにくいものはありました。こんなに遅いのなら、もし可能ならば最初から矩形領域をちゃんと順序立てて描いていった方が、まだ耐えられそうでした。どうせ複雑な図形を塗ろうとすると延々と待たされた挙げ句にスタックが溢れてエラーメッセージで終わるということもあったくらいですし。

逆に言えば、こういう時こそ「我こそは」と挑戦する人も出てくるもので、高速に塗りつぶしためのアルゴリズムを研究してアセンブラで実装するツワモノも出てきた気もするのですが、どんなに頑張ったところでゲームなどで使うには耐えられるものではありませんでした。

領域内高速塗りつぶし法 / High-speed Region Fill Method

塗りつぶすという操作自身はペイント系のアプリで今でも必須の機能ですし、アルゴリズムの勉強には面白そうです。

塗りつぶしアルゴリズム(Flood fill)のPythonでの実装

そんなところで PAINT命令自体はずっと生き残ったものの、その使われる場所は限定的でした。画面の解像度も上がりパソコンに搭載されているメモリも増えてくると、その都度、線を組み立てて絵を描くよりも小さな領域を組み合わせて全体の画面を作っていく方法が主流となっていきました。そういえばGET@やPUT@もFM-8からだったかな。

そういえば塗りつぶしのアイコンって、どうしてこぼしたバケツなんだろう。