JPH0154752B2 - - Google Patents

Description

【発明の詳細な説明】 Ａ 産業上の利用分野 本発明は、CRTを用いた図形表示装置または
印刷ヘツドを有する図形印刷装置のような図形再
生装置で再生される塗りつぶし図形を発生するた
めの図形処理装置に関し、特に、ラスタ走査型
CRT表示装置に塗りつぶし図形を表示するのに
適した図形処理装置に関する。

Ｂ 開示の概要 図形を構成する輪郭線は一連の線セグメントす
なわち一連のベクトルとして与えられ、水平な線
セグメントは無視される。水平な線セグメント以
外の各線セグメントは上から下または下から上へ
の一方向で始点と終点の座標アドレスによつて指
定される。各線セグメントはXY座標系における
近似画素に変換され、ランダム・アクセス・ワー
ク・メモリに記憶される。各線セグメントの画素
をワーク・メモリに記憶するときは、各線セグメ
ントを各水平ライン当り１画素で表わし、各線セ
グメントの始点の画素を書込まず、始点に続く画
素をワーク・メモリの対応座標アドレスの読取り
画素データとの排他的ORを取つて書込むという
規則に従つて行なわれる。これにより、ワーク・
メモリに書込まれた輪郭線画素は各水平ラインに
偶数個存在することになる。したがつて、ワー
ク・メモリの各水平ラインを走査し、奇数番目の
輪郭線画素から偶数番目の輪郭線画素までの画素
記憶セルをオンにすることにより塗りつぶしを実
現できる。この技術によれば、複雑な図形でも簡
単に塗りつぶしを行なうことができる。

Ｃ 従来技術 図形処理装置において塗りつぶしは基本的な画
像処理機能の１つであり、これまで種々の塗りつ
ぶし方法が提案されている。最も基本的な方法
は、ソフトウエアによつて、ランダム・アクセ
ス・メモリの各画素ライン毎に塗りつぶし範囲を
逐一指定し、指定された範囲のライン画素を塗り
つぶすものであるが、このようなソフトウエアに
よる塗りつぶしは処理時間が長いという問題があ
る。

米国特許第4189743号はランダム・アクセス・
メモリに書込んだ閉じた輪郭線領域内の任意の１
点をシード点として選び、先ずシード点を通る画
素ラインを輪郭線の範囲で塗りつぶし、次にこの
画素ラインに隣接する画素ラインを塗りつぶし、
以下同様の手順を繰返すことによつて塗りつぶし
を行なう技術を示しているが、この方法は非常に
複雑な手順を必要とする。

特公昭54−40179号公報はリフレツシユ・メモ
リの各画素ラインが偶数個の輪郭線ドツトを持つ
ように輪郭線ドツトを選択的に除去して輪郭線パ
ターンを書込み、ラスタ走査と同期して各画素ラ
インを読取るときに奇数番目の輪郭線ドツトで
CRTへのビデオ信号をオンにし、偶数番目の輪
郭線ドツトでビデオ信号をオフにすることにより
塗りつぶし図形を表示する技術を示している。し
かしこの特許は除去したドツトによる図形歪みが
目立つ、処理できる図形に制限がある、リフレツ
シユ・メモリ上で画像処理できないなどの問題を
有する。この特許は、本発明における方向づけし
たベクトル・データの使用、排他的ORによる端
点処理および塗りつぶしについては示していな
い。

Ｄ 発明が解決しようとする問題点 したがつて本発明の目的は、図形の輪郭線を構
成する一連の線セグメントを表わすベクトル・デ
ータに基いて複雑な塗りつぶし図形を高速且つ簡
単に発生することができる図形処理装置を提供す
ることである。

Ｅ 問題点を解決するための手段 本発明は、一定の規則にしたがつて輪郭線を発
生しこれをランダム・アクセス・メモリに記憶す
る。輪郭線は一連の線セグメントすなわちベクト
ルとして指定されるが、水平な線セグメントは用
いられない。水平な線セグメント以外の各線セグ
メントは上から下または下から上への一方向で指
定される。各線セグメントは近似画素に変換され
る。各線セグメントは水平ライン当り１画素で表
わされ且つ各線セグメントの始点は書込まれな
い。画素はランダム・アクセス・メモリの対応座
標アドレスの読取り画素データとの排他的ORに
よりランダム・アクセス・メモリに書込まれる。
これにより、ランダム・アクセス・メモリに書込
まれた輪郭線画素は各水平ラインに偶数個存在す
ることになり、どのように複雑な図形でも奇偶反
転法により簡単に塗りつぶすことができる。

Ｆ 実施例 先ず、本発明による塗りつぶし技術の概要およ
び本発明において用いられる処理の規則について
説明する。

第２図は２次元図形の画素データを、対応する
XYの２次元平面に記憶するランダム・アクセ
ス・メモリに書込んだ閉じた輪郭線画素ドツトを
示している。この輪郭線画素を水平な画素ライン
毎に走査し、奇偶反転法、すなわち、奇数番目の
輪郭線画素から次の偶数番目の画素までのドツト
をオンに設定する方法によつて塗りつぶしをする
場合、１つの画素ラインに奇数個の輪郭線がある
ときは、第２図のｌ１，ｌ２，ｌ３，ｌ４のよう
に、塗りつぶされるべきでない部分が塗りつぶさ
れ、塗りつぶされるべき部分が塗りつぶされない
（ラインｌ３の破線部分）という問題が生じる。

本発明は第３図Ａに示す如く、各画素ラインに
常に偶数個の輪郭線画素が存在し、したがつて奇
偶反転法の画素書込によつて簡単に塗りつぶしを
行なうことができるように輪郭線をランダム・ア
クセス・メモリに書込むものである。第３図にお
いて、“Ｘ”印は書込まれない輪郭線画素を示し
ている。

本発明では、図形を構成する輪郭線を一連の線
セグメントすなわちベクトルとして表わし、各線
セグメントの始点と終点を示す座標データに基い
て近似画素ドツトを発生し、それをランダム・ア
クセス・メモリに記憶する。本発明では、第３図
の如く輪郭線画素を書込むために、下記の５つの
規則を用いる。

規則１：水平な線セグメントは書かない。

規則２：各線セグメントは各ライン当り１画素で
表わす。

規則３：各線セグメントの始点は書かない。

規則４：輪郭線画素はこの画素を書込もうとして
いるメモリ・アドレスに記憶されている画素
データとの排他的ORを取つて、その結果を
書込む。

規則５：各線セグメントは上から下または下から
上への一方向で指定する。

規則１は、第２図のラインｌ２のように水平な
輪郭線部分に含まれる輪郭線画素Ｐ１〜Ｐ２によ
つて１つのラインに奇数個の輪郭線画素が生じる
のを防止するためのものである。通常の図形処理
では水平線が多用されるから、水平線セグメント
の省略は塗りつぶし処理の高速化にも寄与する。

規則２は、線セグメントの角度に関係なく常に
１ライン当り１画素で輪郭線を表わすものであ
る。例えば、第４図に示すように始点Ｓ、始点Ｅ
を有し水平ラインに対し45゜以下の角度をなす線
セグメントの近似ドツトを発生する場合、１つの
ラインに複数ドツトが生じるが、この場合は最初
に発生されるドツトｄ１，ｄ２が輪郭線ドツトと
して用いられ、２番目のドツトｄ３，ｄ４は書込
まれない。

規則３は、上向きまたは下向きの頂点を除去す
るものである。規則５にしたがつて例えば上から
下への一方向で線セグメントを指定するものとす
れば、規則３は第２図の上向きの頂点の輪郭線画
素Ｐ５およびＰ１０を除去する。

規則４および規則５は規則３によつて処理され
る頂点と反対向きの頂点の輪郭線画素（この例で
はＰ７）を除去する。

ここで、第３図Ａの輪郭線画素パターンを書込
む手順について説明する。第３図の輪郭線は６つ
の線セグメントによつて指定される。いま、上か
ら下への向きに線セグメントを指定するとすれ
ば、これらの線セグメントはＰ５→Ｐ３、Ｐ５→
Ｐ６、Ｐ６→Ｐ７、Ｐ１０→Ｐ７、Ｐ１０→Ｐ１
２、Ｐ１→Ｐ１５によつて表わされる。水平線セ
グメントの画素Ｐ１→Ｐ２、Ｐ１３，Ｐ１４は無
視される。線セグメントＰ５→Ｐ３では、始点の
画素Ｐ５は書込まれず、次の画素から終点の画素
Ｐ３まで書込まれる。書込みは、書込むべき画素
データと、この画素データが書込まれるべきメモ
リ・アドレスから読取られた画素データとの排他
的ORの結果を書込むことによつて行なわれる。
輪郭線画素データを２進１で表わし、メモリが２
進０を記憶しているとすれば、輪郭線画素データ
はそのまま書込まれる。

線セグメントＰ５→Ｐ６では、同様に、始点Ｐ
５は書込まれず、残りの画素は２進１に設定され
る。線セグメントＰ６→Ｐ７では、始点Ｐ６は書
込まれないが、Ｐ６はセグメントＰ５→Ｐ６で既
に書込まれている。始点Ｐ６に続く画素は終点Ｐ
７も含めて排他的ORにより書込まれる。

セグメントＰ１０→Ｐ７では、始点Ｐ１０は書
込まれず、これに続く画素は書込まれる。終点Ｐ
７はセグメントＰ６→Ｐ７の書込みによつて２進
１であるから、終点Ｐ７の排他的OR書込みは終
点Ｐ７を再び２進０に戻し、下向きの頂点Ｐ７を
輪郭線から除去する。以下同様に、セグメントＰ
１０→Ｐ１２、Ｐ１→Ｐ１５の輪郭線ドツトが書
込まれる。

輪郭線画素の書込み終了後、メモリの各ライン
を走査し、奇数番目の輪郭線画素から次に生じる
奇数番目の輪郭線画素までのメモリ・ドツトを２
進１に書込む。この場合、偶数番目の輪郭線画素
は後述する理由のため、２進０にするのが好まし
い。この書込みは、メモリから各ラインの画素デ
ータを読取り、同一ライン上の各画素と直前の画
素データとの排他的ORを取り、その結果を書込
むことによつて好適に行なうことができる。した
がつて、第３図Ｂに示すように奇数番目の輪郭線
画素に続く２進０の画素は２進１になる。画素Ｐ
１０は輪郭線書込みの際に除去したが、塗りつぶ
しの段階で２進１にされ、最初に無視した画素Ｐ
１３，Ｐ１４も塗りつぶされる。最初に無視した
画素Ｐ１−Ｐ２、Ｐ５，Ｐ７は塗りつぶし図形か
ら除去される。ここで注目すべきことは、排他的
ORによる塗りつぶしにより各ライン上の偶数番
目の輪郭線画素Ｐ３，Ｐ４，Ｐ８，Ｐ９，Ｐ１５
−Ｐ１６がすべて除去されることである。したが
つて既述した特公昭54−40179号のように頂点の
ドツトを単純に除去する場合に比べて図形の歪み
が最小になる。また、偶数番目の輪郭線画素の除
去は隣接する図形の発生を容易にするという利点
を与える。これについては後述する。

第１図はラスタ走査型CRTグラフイツク表示
システムに適用した本発明の実施例を示してい
る。マイクロプロセツサ１０はアドレス線１２お
よびデータ線１４を介してリフレツシユ・メモリ
５０に接続され、リフレツシユ・メモリ５０はラ
スタ走査型CRT表示装置７０に接続される。リ
フレツシユ・メモリ５０は表示装置７０の画素ド
ツトに対応する記憶セルを有するランダム・アク
セス・メモリである。デイスプレイ・システムは
更に、塗りつぶし図形を記憶するのに用いられる
ワーク・メモリ６０に塗りつぶし図形を形成する
ための輪郭線／塗りつぶし制御装置２０および線
セグメント―画素ドツト変換装置３０を含む。こ
の例では、塗りつぶし図形をワーク・メモリ６０
に発生し、表示に際してはワーク・メモリ６０の
塗りつぶし図形をリフレツシユ・メモリ５０に書
込む方式を用いているが、リフレツシユ・メモリ
５０を消去して用いるならば、リフレツシユ・メ
モリ５０に直結塗りつぶし図形を書込むことも可
能である。しかしリフレツシユ・メモリ５０が図
形データを持つ場合は制御が非常に面倒になるか
ら、別個のワーク・メモリ６０を用いるのが好ま
しい。特に、ワーク・メモリの使用はリフレツシ
ユ・メモリ上で画像処理するのに有利である。勿
論、リフレツシユ・メモリ５０およびワーク・メ
モリ６０は物理的に別体である必要はなく、単一
のメモリの別々の領域でもよい。

ワーク・メモリ６０はリフレツシユ・メモリと
同様に、表示装置７０に表示される２次元図形の
画素ドツトと対応する記憶セルを有するランダ
ム・アクセス・メモリである。塗りつぶし図形
は、既述した手順にしたがつて、ワーク・メモリ
６０に輪郭線画素を書込み、次に輪郭線によつて
定められた領域の記憶セルを２進１に設定するこ
とによつて、ワーク・メモリ６０に形成される。

動作において、マイクロプロセツサ１０は先
ず、第３図に関して説明したように、塗りつぶさ
れるべき図形の輪郭線を構成する一連の線セグメ
ントの始点と終点の座標アドレスを順次に供給す
る。処理は１線セグメントずつ行なわれ、各セグ
メントは線セグメント−画素ドツト変換装置３０
によつて近似画素ドツトに変換される。

変換装置３０は、この例では、ブレゼンハム
（Bresenham）のアルゴリズムに基いて動作す
る。Bresenhamのアルゴリズムはアイビーエ
ム・システムズ・ジヤーナル（IBM Systems
Journal）、第４巻、第１号、1965年、第25〜30頁
に所載の“デイジタル・プロツタのコンピユータ
制御のためのアルゴリズム（Algorithm for
comPutercontrol of ａ digital comPuter）”
に示されるように公知のものである。このアルゴ
リズムは、要するに、ベクトルの始点と終点のＸ
座標およびＹ座標の差（ΔX、ΔY）のうち長い
方を長軸、短い方を短軸とし、長軸の値を始点座
標値から終点座標値に向けて１座標値（＋１また
は−１）ずつ変えたとき、短軸の座標値を変えな
いかまたは１座標値（＋１または−１）変えるか
を選択することによつて、近似点を発生するもの
である。

マイクロプロセツサ１０は変換されるべき１つ
の線セグメントの長軸始点座標値、長軸終点座標
値、短軸始点座標値を変換装置３０のレジスタ３
１，３２，３３にロードする。また、マイクロプ
ロセツサ１０はその線セグメントの長軸がＸであ
るかＹであるかを示す信号を制御装置２０のレジ
スタ２２にセツトする。これに線セグメントの角
度に依存する。更に、マイクロプロセツサ１０は
その線セグメントの始点から終点へ行とき、長
軸、短軸それぞれの座標値を増加させるべきかま
たは減少させるべきかを示す信号をレジスタ２
３，２４にセツトする。第４図の例では、長軸＝
Ｘ、長軸減少、短軸増加がセツトされる。また、
輪郭線書込モードを示す信号がレジスタ２５にセ
ツトされる。ΔX＝ΔYの場合は、ＸまたはＹの
一方を長軸として指定すればよい。

レジスタ３１の長軸始点は長軸カウンタ３５に
セツトされ、レジスタ３３の短軸始点は短軸カウ
ンタ３６にロードされる。長軸カウンタ３５は制
御論理回路２１からの長軸ステツプ・パルスによ
り１ずつ増加または減少される。増減の方向はレ
ジスタ２３のセツト値によつて制御される。短軸
カウンタ３６は計算回路３４からの短軸ステツ
プ・パルスによつて１ずつ増加または減少され
る。増減の方向はレジスタ２４のセツト値に依存
する。計算回路３４は、上記Bresenhamのアル
ゴリズムにしたがつて、長軸が１ステツプする毎
に短軸＝不変または１ステツプを選択することに
よつて最近似点を判定し、短軸＝１ステツプのと
き短軸ステツプ・パルスを発生するものである。

長軸カウンタ３５の値は比較器３７でレジスタ
３２の長軸終点値と比較され、変換装置３０は、
この値が一致するまで動作を続ける。セレクタ３
８はレジスタ２２の長軸指示に応答し、長軸＝Ｘ
のとき長軸カウンタ３５をＸ出力へ、短軸カウン
タ３６をＹ出力へ接続し、長軸＝Ｙのとき長軸カ
ウンタ３５、短軸カウンタ３６をそれぞれＹ出
力、Ｘ出力へ接続する。長軸カウンタ３５、短軸
カウンタ３６は最初始点の座標値を含む、１つの
近似画素ドツトが決定される毎に更新される。

リフレツシユ・メモリ５０およびワーク・メモ
リ６０はｘ軸方向は８ビツトの画素データ・バイ
トを配列して記憶するものであり、バイト単位で
アクセスされる。したがつて画素アドレスをバイ
ト・アドレスに変換するため、セレクタ３８のＸ
出力の下位３ビツトを除くＸ上位アドレス・ビツ
トとセレクタ３８のＹ出力のＹアドレス・ビツト
の組合わせがアドレス回路４４に与えられ、書込
むべきバイトをアドレスする。Ｘ出力の下位３ビ
ツトはデコーダ３９に加えられ、アドレスされる
バイトの８ビツトすなわち８画素ドツトのうちそ
の下位３ビツトによつて指定される画素ドツトを
２進１にセツトしたビツト・パターンに変換され
る（例えば、011→00100000）。

ワーク・メモリ・アクセスは変換装置３０にお
いて１つの近似画素ドツトが決定される度に行な
われる。輪郭線書込み／塗りつぶし動作では各ワ
ーク・メモリ・アクセス・サイクルは常に読取
り、書込みの２ステツプ動作を含む。これは制御
論理回路の読取り／書込み信号Ｒ／Ｗによつて制
御される。輪郭線書込みモードでは、先ず、セレ
クタ３８のＸ出力の上位ビツトとＹ出力のビツト
によつてアドレスされる１バイトが読取られる。
読取られた１バイトとデコード３９の出力は排他
的OR（EX−OR）４０へ与えられる。EX−OR
４０の出力はセレクタ４２へ与えられるが、セレ
クタ４２は輪郭線書込みの時はEX−OR４０の
出力を選択し、これをゲート４３へ供給する。

読取りの次に書込みが続くが、上述の規則２，
３にしたがつて始点を除去し且つ１ライン１画素
で輪郭線を書込必要がある。制御装置２０の始点
制御回路２７はレジスタ２５の輪郭線モード信号
および制御論理回路２１からの輪郭線書込みスタ
ート・サイクル・タイミング信号に応答し、最初
のワーク・メモリ・アクセス・サイクルのとき
OR２９を介してゲート４３を禁止する。輪郭線
制御回路２８はレジスタ２５の輪郭線モード信
号、レジスタ２２の長軸＝Ｘの表示、および計算
回路３４からの短軸ステツプ・パルスなしの指示
に応答して、短軸（Ｙ）の値が変わらないときゲ
ート４３を禁止する。第３図に関して説明したよ
うに、同一のＸラインに複数個の近似ドツトが発
生するのは長軸＝Ｘの場合である。

したがつて、変換装置３０は始点から終点まで
の全近似画素ドツトを相次ぐサイクルで連続的に
発生し、アドレス回路４４は各サイクルでワー
ク・メモリ６０をアクセスするが、始点と不要ド
ツトは書込まれないことになる。

各線セグメント毎に輪郭線画素の書込みが行な
われ、長軸カウンタ３５の値がレジスタ３２の長
軸始点の値と等しくなつたとき、比較器３７から
長軸一致信号が発生し、この長軸一致信号はマイ
クロプロセツサ１０へ送られ、１つの線セグメン
トの書込み終了を通知する。

マイクロプロセツサ１０は長軸一致信号に応答
し、次の線セグメントの始点と終点の座標値をレ
ジスタ３１，３２，３３にセツトし、同様に線セ
グメント−画素ドツトの変換および輪郭線画素の
書込みを行なう。動作は最終の線セグメントの処
理が完了するまで同様に続けられ、マイクロプロ
セツサ１０は最終の線セグメントの処理において
比較器３７から長軸一致信号が発生されたことに
応答して制御装置２０の制御論理回路２１へ塗り
つぶし指示信号（図示せず）を与える。制御回路
２１はこれに応答して塗りつぶしモード信号を発
生し、セレクタ４２は塗りつぶしモード信号に応
答して塗りつぶし回路４１の出力をゲート４３へ
通過させるように切替えられる。

制御装置２０の塗りつぶしアドレス発生回路２
６は塗りつぶしモード信号と長軸ステツプ・パル
スに応答し、ワーク・メモリ６０のデータを各Ｘ
ライン毎に１バイトずつ読取るためのアドレスを
アドレス回路４４へ発生する。第５図は塗りつぶ
しアドレス発生回路２６の回路例を示している。
ワーク・メモリ６０に書込まれた輪郭線を取囲む
任意の長方形領域、好ましくは輪郭線よりもわず
かに大きな長方形領域のＸ始点、Ｘ終点、Ｙ終
点、Ｙ始点の値がマイクロプロセツサ１０により
レジスタ８１，８２，８３，８４にセツトされ、
Ｘ始点レジスタ８１、Ｙ始点レジスタ８４の値は
Ｘカウンタ８６、Ｙカウンタ８７にロードされ
る。ゲート回路８５は塗りつぶしモード信号に応
答して長軸ステツプ・パルスをＸカウンタ８６へ
与えられる。したがつてＸカウンタ８６は順次歩
進される。Ｘカウンタ８６の下位３ビツトを除く
ビツトとＹカウンタ８７のビツトはバイト・アド
レスとしてアドレス回路４４へ与えられる。Ｘカ
ウンタ８６の値がＸ終点に等しくなつたとき、比
較器８８はＸ一致出力を発生し、Ｙカウンタ８７
を＋１とすると共にＸカウンタ８６をリセツト
し、Ｘ始点をＸカウンタ８６に再ロードする。同
様に動作が続き、Ｙカウンタ８７の値がＹ終点に
等しくなつたとき比較器８９はＹ一致出力を発生
する。指定された長方形領域の全バイトの読取り
が終了したときＸ一致出力とＹ一致出力が発生
し、AND回路は塗りつぶし完了信号をマイクロ
プロセツサ１０に与える。

第６図は塗りつぶし回路４１を示している。塗
りつぶし回路は１つのラツチと８個のEX−OR
回路で構成され、ラツチの入力はビツト０のEX
−ORの出力に接続され、その出力はビツト７の
EX−ORの入力に接続され、ビツト７〜２のEX
−ORはビツト６〜０のEX−ORの入力に接続さ
れている。読取られた１バイトはビツト７〜０の
入力端子に与えられる。例えば、読取られたバイ
トのビツト６＝２進１で、これが最初の奇数番目
の輪郭線画素ドツトとすると、ビツト６〜０の
EX−ORは１出力を発生する。ラツチは制御論
理回路２１からのリセツト信号RST（第１図では
図示せず）により動作開始前にリセツトされるか
ら、ビツト７＝０であり、したがつて01111111が
同じバイト・アドレスに記憶される。書込み後制
御論理回路２１からの書込み完了信号（Ｗ／Ｃ）
（第１図では図示せず）によりビツト０のEX−
ORの２進１出力がラツチに記憶され、ビツト７
のEX−ORの入力へ１を与える。したがつてこ
の回路はその後２進０の画素ビツトが読出される
限りオール２進１の出力を発生する。最初の偶数
番目の輪郭線画素ドツトがあるバイトのビツト５
で生じたとすると、ビツト５のBX−ORは２進
０を発生し、ビツト４〜０も２進０となる。した
がつて最初の奇数、偶数ドツト間の塗りつぶしが
終了し、ラツチは０にセツトされる。２番目の奇
数ドツトが検出されたとき、同様に次の偶数ドツ
トまで塗りつぶし書込みが行なわれる。ラツチは
各Ｘラインの走査の終了後リセツトされる。この
回路によれば、偶数番目の輪郭線画素が消去され
る。

塗りつぶし完了後、マイクロプロセツサ１０は
アドレス回路４４へアドレスを与え、ワーク・メ
モリ６０の塗りつぶされた図形を１バイトずつ読
取り、これをリフレツシユ・メモリ５０に書込
む。塗りつぶされた図形はリフレツシユ・メモリ
５０の任意の位置に書込むことができる。白黒表
示の場合リフレツシユ・メモリ５０は単一のメモ
リ・プレーンを持つが、１画素当り複数ビツトで
階調表示またはカラー表示する場合は、ビツト対
応に複数のメモリ・プレーンを持つことができ
る。この場合、メモリ・アドレス入力およびデー
タ入力は各メモリ・プレーンに共通に与え、そし
て書込まれるプレーンを選択することにより、所
望の階調またはカラーで塗りつぶし図形をリフレ
ツシユ・メモリに記憶できる。

最後に、本発明の利用について説明する。

(1) 先ず、上向きまたは下向きの頂点が複数個あ
るような複雑な図形でも簡単に且つ高速に塗り
つぶしできる。

(2) 単に頂点を除去するだけでなく、塗りつぶし
の段階で偶数番目の輪郭線画素をオフにするこ
とにより、頂点の除去による原図形の形状の歪
みを最小にできる。

(3) 水平な線セグメントを省略するため、ベクト
ル指定が簡単になる。

(4) 交差する線を含む図形でも塗りつぶしでき
る。例えば第７図の図形の場合Ｐ１→Ｐ３、Ｐ
２→Ｐ４の２つの線セグメントで輪郭線指定で
きるが、画素Ｐ５はセグメントＰ１→Ｐ３で書
込まれるがセグメントＰ２→Ｐ４のEX−OR
書込みによつて２進０になるから、交点処理な
しで塗りつぶしできる。

(5) 偶数番目の輪郭線画素を除去することによ
り、境界線を完全に一致させた形で隣接図形の
塗りつぶしを行なうことができる。

例えば、前の塗りつぶし図形に接する塗りつぶ
し図形を追加したりまたは前の図形と異なる色の
隣接塗りつぶし図形を表示したりする場合は、前
の図形をリフレツシユ・メモリに移動した後に、
前の図形と隣接した図形をつくる必要がある。こ
のような場合本発明では前の図形で用いた線セグ
メントを用いて輪郭線を書くことができる。例え
ば第３図において線セグメントＰ５→Ｐ３、Ｐ１
→Ｐ１５、Ｐ１０→Ｐ７、Ｐ１０→Ｐ１２を指定
して塗りつぶしすれば、上、右、下側で前の図形
と接した塗りつぶし図形を得ることができる。画
素Ｐ１０は書込まれないから、前の図形と干渉す
ることはない。また画素Ｐ９，Ｐ８，Ｐ７は書込
まれるが画素Ｐ１１，Ｐ１２は塗りつぶしの段階
で除去される。したがつて、前の図形と部分的に
重なつたりあるいは隣接する図形間にすき間が生
じたりしない。

本明細書では特定の例について示したが、本発
明の範囲内で種々の変更が可能であることは明ら
かであろう。例えば、本発明では別個の塗りつぶ
しアドレス発生回路２６を用いたが、回路２６と
変換装置３０の類似性から明らかなように、回路
２６の代わりに変換装置３０を利用することがで
きる。この場合は、回路２６のレジスタ８１，８
２，８４の代わりに変換装置３０のレジスタ３
１，３２，３３が用いられるが、Ｙ終点レジスタ
８３に対応する短軸終点レジスタ、比較器８９に
対応する比較器、およびAND回路９０に対応す
るAND回路を追加する必要がある。また、塗り
つぶしモードにおいて比較器３７の出力を短軸ス
テツプ・パルスとして短軸カウンタ３６へゲート
する必要があるが、これらの制御は明らかであろ
う。また、実施例では始点の除去および１ライン
１画素の制御をデータ・ゲート４３の禁止によつ
て行なつたが、例えば変換装置３０の出力に同様
の禁止ゲートを設けることもできよう。

Ｇ 発明の効果 本発明によれば、複雑な図形でも、簡単に且つ
高速に塗りつぶしを行なうことができる。

【図面の簡単な説明】

第１図は本発明の実施例、第２図は閉じた輪郭
線を用いたときの塗りつぶしを示す図、第３図は
本発明による塗りつぶしを示す図、第４図は近似
画素ドツトを示す図、第５図は塗りつぶしアドレ
ス発生回路図、第６図は塗りつぶし回路図、およ
び第７図は塗りつぶし図形を例示する図である。 １０……マイクロプロセツサ、２０……輪郭
線／塗りつぶし制御装置、２７……始点制御回
路、２８……輪郭線制御回路、３０……線セグメ
ント―画素ドツト変換装置、４０……排他的OR
回路、４１……塗りつぶし回路、５０……リフレ
ツシユ・メモリ、６０……ランダム・アクセス・
ワーク・メモリ、７０……CRT表示装置。

Claims (1)

1. 【特許請求の範囲】 １ 図形再生装置と、２次元図形の画素データを
   記憶する記憶セルを有するランダム・アクセス・
   メモリとを備え、上記メモリに上記図形再生装置
   で再生するための塗りつぶし図形を発生するグラ
   フイツク図形処理装置において、 (イ) 図形の輪郭線を構成する一連の線セグメント
   のうち水平な線セグメントを除く各線セグメン
   トを一方向で指定するための手段と、 (ロ) 指定された各線セグメントの近似画素を発生
   するための手段と、 (ハ) 上記発生手段に応答し、各線セグメントの始
   点を含まず各線セグメントを水平ライン当り１
   画素で表わす画素を、上記メモリの対応座標ア
   ドレスの読取り画素データとの排他的ORを取
   つて上記メモリに書込み輪郭線画素を設定する
   ための手段と、 (ニ) 上記ランダム・アクセス・メモリに書込まれ
   た輪郭線画素をライン単位で走査し、各ライン
   の奇数番目の輪郭線画素と次に現われる偶数番
   目の輪郭線画素との間の記憶セルをオンに設定
   するための手段と、 を有する図形処理装置。