JPS6288069A - 図形処理装置 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 以下の順序で本発明を説明する。

Ａ、産業上の利用分野 Ｂ、従来技術 Ｃ０発明が解決しようとする問題点 り０問題を解決するための手段 Ｅ、実施例 Ｅ　１．　　好ましい実施例の概略的説明（第１図、第
２ｂ図、第３図） Ｅ　２．　　多角形充填プロセッサ（第２ａ、ｂ図、第
３図、第６図、第７図） ｇ　３．　　動作（第３図、第４図、第８図）Ｅ　４．
　　点発生装置ＰＧ１、ＰＯ２（第５図、第６図、第７
図、第８図） Ｅ５．　　多角形充填サイクル（第９図）Ｅ　６．　　
マイクロコードの論理式 Ｆ０発明の効果 Ａ、産業上の利用分野 本発明は情報処理システム、さらに具体的には図形デー
タを処理する方法及び装置を含む情報処理システムに関
する。

Ｂ、従来技術 一般に、図形表示システムの多角形充填過程は２つの段
階よシ成る。最初に、多角形の辺を決める前処理段階が
あり、第２に多角形の辺の間に線を挿入する事による多
角形の領域を充填する走査過程がある。多角形は一般に
凸もしくは凹であると考えられる。従来、図形表示シス
テムで図形の発生に使用されている大部分の多角形は凸
多角形である。凸多角形の前処理は凹条角形の場合↓り
も簡単で実施が容易である。

次に従来技術を代表する多角形充填方法を含む図形表示
システムを説明する。

米国特許第４４２５５５９号は図形表示装置上で移動し
、寸法もしくは形状が変化出来る多角形の領域を画定す
る線分を記述する情報を使用する方法及び装置全開示し
ている。

この特許は線の端点を発生するのに線の勾配を使用する
アルゴリズムを用いている。この特許に説明されている
端点の発生方法は、線の端点を発生する修正プレセンハ
ム（Ｂｒｅｓｅｎｈａｍ　）’７＃ゴリズムを使用した
充填プロセッサの様な正確な適位置を与えない。

ＰＣＴ（特許協力条約）公開出願筒ｗＱ３３７０２５１
０号はラスターグラフィック・システムのカラーＣＲＴ
モニタによって表示される多角形を充填する方法及び装
置を開示しているが、この方法では境界のベクセル（画
素）が各充填要素の始点ベクセル及び終点ベクセルを決
定し、充填線が水平走査線と一致している。

この公開出願は多角形充填処理の走査段階のみを扱って
いる。この出願は多角形充填動作を遂行するアルゴリズ
ム及び論理を簡単にするために凸多角形の特性全利用し
た方法及び装置を開示していない。

米国特許第４４４７８０９号は多角形を発生するために
、個々の水平走査線に対応して辺データ金発生している
。

しかしながら、本明細書にあげられている他の従来のシ
ステムと同様に、この特許は表示すべき凸多角形の特定
の特性を認識する事による方法及び装置の効率化及び簡
単化を認識せず又利用していない。

米国特許第４４７５１０４号は表示すべき像を多角形で
表わす、２次元ラスタ表示システム上に３次元像を表示
する表示システムを開示している。

しかし、本明細書中の他の従来のシステムと同様に、こ
の特許も表示すべき凸多角形の特定の特性を認識する事
による、方法及び装置の効率化及び簡単化を認識してお
らず又利用していない。

米国特許第４４９２９５６号は図形を表わすベクトル・
データを記憶するメモリ回路、ラスタ・メモリ並びにベ
クトル・メモリ及びラスタ・メモリの動作を制御するプ
ロセッサを含む図形表示システムを開示している。

この特許は一般に多角形を形成する方法及び装置に関す
るものであるが、本明細書にあげた他の従来のシステム
と同じ様に、この特許は表示すべき凸多角形の特定の特
性を認識して、その方法及び装置の効率化及び簡単化す
るという事を認識していす、利用していない。

１９６５年刊アイ・ビー・エム・システム・ジャーナル
第４巻第１号の第２５頁のジェイ・イー・フレセンハム
の論文「ディジタル・プロッタを計算機で制御するだめ
のアルゴリズムＪ　（Ｊ、Ｅ。

Ｂｒｅｓｅｎｈａｍ　：　＠Ａ１ｇｏｒｉｔｈｍ　　ｆ
ｏｒ　ＣｏｍｐｕｔｅｒＣｏｎｔｒｏｌ　　ｏｆ　　ａ
　　Ｄｉｇｉｔａｌ　　Ｐｌｏｔｔｅｒ’、ＩＢＭ　　
Ｓｙｓｔｅｍｓ　　Ｊｏｕｒｎａｌ、Ｖｏｌ、４、Ｎｏ
。

１　１９６５　　ｐａｇｅ　　２５）　　は、離散的な
データ点を結ぶ線分によってデータをプロットするため
のアルゴリズムを開示している。この論文は線分を接続
するだめのデータ点を発生するためのアルゴリズムを与
え、本発明のベクトル発生器の部分を制御するのに使用
されるが、凸多角形中に充填線を引く際の応用の効率化
及び簡単化を認識していず又使用していない。

１９７８年２月刊アイ・ビー・エム・テクニカル・ティ
スフロージャ・バレテイン第２０巻、第９号、第６７０
６頁の論文「プレセンハム・アルゴリズムを使用した点
の発生Ｊ（”Ｇｅｎｅｒａｔｉｏｎｏｆ　　Ｐｏｉｎｔ
ｓｕｓｉｎｇ　　Ｂｒｅｓｅｎｈａｍ’ｓＡ１ｇｏｒｉ
ｔｈｍ”　）ｉｎ　　ＩＢＭ　ＴｅｃｈｎｉｃａｌＤｉ
ｓｃｌｏｓｕｒｅ　　Ｂｕｌｌｅｔｉｎ、Ｖｏｌ、２０
、Ｎｏ。

９、　Ｆｅｂｒｕａｒｙ　１９７８、ｐａｇｅ　５７０
５）はプレセンハム・アルゴリズムの応用として線に沿
って点を発生する方法全開示している。この論文に説明
されている技術は本発明の好ましい実施例で、使用され
る点発生装置を具体化するのに使用出来る。しかしなが
ら、プレセンノ・ム・アルゴリズムの場合と同様に、こ
のアルゴリズムも凸多角形中に充填線を引く際のこの方
法の効率化及び簡単化を認識し、もしくは利用していな
い。

Ｃ１発明が解決しようとする問題点 本発明の目的は制御情報及び入力データを制御するプロ
グラム・メモリ、入力データによって画定される多角形
の辺の座標を決定する装置、多角形を充填するため辺を
結ぶ複数の充填線のためのパラメータを発生する装置、
充填線の各々の画素特性を発生する鑓、表示装置上に表
示するためのペクセル特性を記憶する画素メモリ、上記
プログラム・メモリ、座標決定装置、パラメータ発生装
置、ペクセル特性発生装置、及び画素メモリに接続した
プロセッサを含む図形処理システムで、多角形の充ｊ′
ｆｉ４線の特性を計算する事にある。

Ｄ１問題点を解決するだめの手段 本発明に従う、図形処理システムで多角形の充填線の特
性を計算するだめの方法及び装置は、制御情報及び入力
データを記憶するだめの第１のメモリ装置、入力データ
によって多角形の辺の座標を決定する装置、上記多角形
？充填するために辺を結ぶ充填線のためのパラメータ発
生装置、各充填線のための画素特性発生装置、表示装置
上に表示するため画素特性を記憶する第２のメモリ、及
び上記第１のメモリ、座標決定装置、パラメータ発生装
置、画素特性発生装置及び第２のメモリに接続され、多
角形の充填線の特性の計算を制御するためのプロセッサ
より成る。

Ｅ、実施例 Ｅｌ　好ましい実施例の概略的説明 第１図ｆａ）、ｆｂ）を参照して、本発明の好ましい実
施例を説明する。本発明を具体化した基本的図形処理シ
ステムはメモリ１２、図形プロセッサ１４、多角形充填
プロセッサ１６、ベクトル発生装置１８及び画素メモリ
２０を含む。

メモリ１２はユーザ・プログラム、例えば１対の１６ピ
ツトの数（ｘ、ｙ）より成る、多角形の頂点のリストを
含む。

図形プロセッサ１４は汎用プロセッサでもビット・スラ
イス・プロセッサでもよい。これはメモリ１２中のユー
ザ・プログラムを使用して情報をベクトル（線）発生装
置１８に送り、発生装置１８は画素データを発生して、
画素メモリ２ｏ中に記憶する。

線を描（場合、図形プロセッサ１４は先ず多角形の頂点
の最初のｘ、ｙ値を画素メモＩＪ　２０にロードし、次
に線の端点のＸ、ｙ値の差、△Ｘ、Δｙをベクトル発生
装置１８に送る。

多角形充填プロセッサ１６は点発生装置ＰＧ１及びＰＧ
２と呼ばれる２つの修正プレセンハム線発生装置より成
る。このプロセッサ１６は図形プロセッサ１４から入力
として多角形の２辺を受取り、これ等の２つの辺の間の
水平走査線のためのパラメータを発生して、このパラメ
ータを画素メモリ２０及びベクトル発生装置１８に送る
。

第３図に示した多角形を例として説明すると、（ａｌｐ
４の座標（Ｘ４、ｙ４）を画素メモリ２゜に送る。

（ｂ）　　辺ｐ４ｐ５のパラメータ（ｘ５−ｘ４、ｙ５
−ｙ４）をｐ４を開始点として使用して点発生装置ＰＧ
１（第６、第７図）に送る。

（ｃ）　　辺ｐ４ｐ３のパラメータを他の点発生装置Ｐ
Ｇ２に送る（第７図）。

（ｄ）　　第２ｂ図に示（〜た様に、下から上の方向に
水平走査線を発生して多角形を充填する。発生される走
査線の長さは２．７．１０．１５等である。

ベクトル発生装置１８が画素メモリ２０中の現在のｘ、
Ｘ位置から、プロットすべき線の△Ｘ、Δｙデータを使
用して画素を発生する。ベクトル発生装置１８は容易に
上述のブレセンノ・ム及び１８Ｍ　　ＴＤＢの論文に示
されたプレセンハム・アルゴリズムを使用して容易に具
体化出来る。

ベクトル発生装置１８への入力は△Ｘ及びΔｙである。

モニタの解像力と、画素メモリ２０中のビット平面が１
０２４ｘ１０２４ビツトであるために、座標系の寸法は
（０，１０２３）ｘ（０，１０２３）である。ベクセル
・メモリ２０への入力は次の様に要約出来る。

（ａ）　　書込みＸ、スクリーン上のＸ位置に書込む。

（ｂ）　　！込みｙ、スクリーン上のＸ位置に書込む。

（・・）　この（ｘ、ｙ）位置を１画素だけ隣りの８つ
の位置に林動するために、次の信号が必要゛’Ｈある。

Ｘ方向に対して １）０１１　Ｘ　　　ｄｉｒ　ｘ 右　　　　　　　１１ 左　　　　　　　１０ 不　動　　　口　　０もしくは１ （ここでｄｉｒは多角形の方向を示すフラグである。後
出。） Ｘ方向に対して ｐｏｓ　ｘ　　　ｄｉｒ　ｘ 上　　　　　　　１１ 下　　　　　　　１０ 不　動　　　０　０もしくは１ Ｅ２　多角形充填プロセッサ１６ 多角形充填プロセッサ１６は２つの点発生装置ＰＣＩ及
びＰＯ２より成る（第６図参照）。

ここで考えている多角形は凸多角形であるから、各水平
線は最高２つの辺とだけ交差する。最小のｙ座標を有す
る頂点から始まって（例えば第６図参照）、ＰＧｌはこ
の頂点の左側の辺全下から上に処理し、ＰＯ２は頂点の
右側の辺を処理する。

第２ｂ図に示した様に、ＰＧ１′Ｉ′ｉプレセンハム・
アルゴリズムを使用して線ｐ４ｐ５に沿う画素を発生し
、ＰＯ２は線ｐ４ｐ３を発生する。ｐ４から始まって、
発生した画素のｙの値が１だけインクレメントする時は
いつでも処理は停止する。

そしてこのｙ値の２つの辺間に水平走査線が引かれる。

この走査線の長さはアップ・ダウン・カウンタＤＬ（第
７図）中に記録され、この走査線の開始点が他のアップ
・ダウン・カウンタｘｐｏｓ中に記録される。

丁度発生した２つの画素が第２ａ、第２ｂ図の線ｐ４ｐ
５上のｑｌ及び線ｐ４ｐ３上のｒｌであるとすると、カ
ウンタＤＬは線分ｑ１ｒｌの長さ７を含み、ｘｐｏｓは
画素ｑ１のＸ座標であるＸ４−６を含んでいる。

次の走査線を発見するために、 （１）ＰＧ１ｉｄブレセンハム・アルゴリズムヲ使用し
て、次の上の点を見出し、線上の次の画素を決定し、Ｄ
Ｌ及びｘｐｏｓ（第９図）を調整する。

新しい画素のｙ値が１だけ増大したのであれば、これが
求める点である。そうでない場合は、ｆａＪ　　上のプ
ロセスをｙ値が１だけインクレメントする迄繰返えす。

もしくは （ｂ）　　線の端点に達したので、新しい線をＰＧｌに
送って上述のプロセスを繰返す。もしくは（ｅ）　　多
角形充填過程の終りに遜し７ている。

この様にしてｑ２を線ｐ４ｐ５上に発生した画素である
とする。

（２）ＰＯ２が同じプロセスを使用して次の上の点ｒ２
を見出す。

（′５）ベクトル発生装置１８が前の走査線ｑ１ｒｌを
引き終るのを待つ。

（４）多角形充填プロセッサ１６は、 （ａ）　　信号Ｘストローブ−書込みＸによって９２の
Ｘ位置を画素メモＩＪ　２　Ｄに送り、（ｂ）　　信号
ｙストローブ−ｐｏｓ　ｙ、ｄｉｒ　ｙによつて現在の
位置のｙ値を１だけインクレメントして・ 現在の位置を９２に移動する。

（５）多角形充填プロセッサ１６がパラメータ△Ｘ＝Ｄ
Ｌ、△ｙ＝Ｑをベクトル発生装置１８に送る。

（６）段階１乃至５を繰返す（Ｅ５多角形充填サイクル
の項参照）。

Ｅ３動作 充填すべき凸多角形は連続した頂点ｐ１、ｐ２、・・・
・、ｐｎ　：ｐ　ｊ＝（Ｘｊ、ｙｊ）によって与えられ
る。Ｘ％　ｙの値はスクリーンの座標中で０から１０２
′！、迄の値を占める。図形プロセッサ１４が頂点のリ
ストを走査する時、プロセッサは、（ｎ）　　データを
ベクトル発生装置及び画素メモリに送ってスクリーン上
に辺をプロットする。

（ｂ）　　次の４つのレジスタを使用する。

ＥＤＧＳＴＡＲＴ・・・・リストの開始アドレスＹＢＯ
Ｔ　・・・・・・・・・・ｙの最小値ＢＯＴＰＴＲ・・
・・・・・・ｙの最小値に対応するＸのアドレス Ｃ０ＵＮＴ　　・・・・・・・辺の該 第６図の図形の場合のメモリ中の頂点のアドレス（１６
進）を次の通りであるとすると、アドレス １００　　　　　ｘｌ １［）２　　　　　ｙｌ １０４　　　　　ｘ２ １０６　　　　　ｙ２ １０８　　　　　ｘ３ １０Ａ　　　　　ｙ３ １００　　　　　ｘ４ １０Ｅ　　　　ｙ４ １１０　　　　　ｘ５ １１２　　　　　ｙｓ このプロセスの終りには、次の様になる。

ＥＤＧＳＴＡＲＴ＝１００ ＹＢＯＴ＝７４ ＢＯＴＰＴＲ＝１０Ｃ ＣＯＵＮＴ＝５ （ｃ）　　次にいくつかの連続した頂点のｙ値を使用し
て、多角形の方向、即ち時計方向もしくは反時計方向を
決定する。ここでもし時計方向ならば＝０で、そうでな
い時は＝＝１の値を占めるフラッグＤＩＲを使用する。

例えば第３図の例では、ｘ５−Ｘ４〉０であるから、Ｄ
ＩＲ＝０である。

（ｄｌ　　多角形充填のための開始点を画素メモリ２０
にロードする。第３図でｐ４の（ｘ、ｙ）座標の場合は
、数０が多角形充填プロセッサ中のＤＬレジスタにロー
ドされ、ｐ４のχ座標Ｘ４がＸＰＯＳレジスタにロード
される。開始点の左側の辺のΔＸ及び△ｙをＰＧｌにロ
ードし、右側の辺に対応するものをＰＯ２にロードする
。即ち第３図の例では（ｘ５−ｘ４、ｙ５−ｙ４）がＰ
Ｇｌに送られ、（ｘ５−ｘ４、ｙＦ６−ｙ４）がＰＯ２
に送られる。点発生装置のセット・アップ遅延のために
、充填過程を開始する迄に数サイクルを待つ。

点発生装置ＰＧ１もしくはＰＯ２（もしくはベクトル発
生装置１８）はΔＸ及び△ｙから誘導したパラメータを
使用する（第８図参照）。

（ｅ）　　多角形充填プロセッサの開始（第４図）上述
の５つのレジスタ並びに２つのポインタ、即ち多角形充
填プロセッサ１８の点発生装置ＰＧ１に送られる頂点の
ｙ値を指示するＥＤＧＰ’Ｉ’Ｒ１及び多角形充填プロ
セッサ１８の点発生装置ＰＧ２に送られる頂点のｙ値を
指示するＥＤＧＰＴＲ２を使用して、点発生装置ＰＧ１
、ＰＯ２に送られた辺を保持する。

（ｆｌ　　カウンタが負になった時、図形プロセッサ１
４の処理が完了する。

第６図の５角形について、次の５つの装置の内容（アド
レス）を縦に時間的経過を追って示すと次の第１表の通
りである。

第　　１　　表 ＰＣＩ　ＰＯ２ＢＤＧＰＴＲｌ　ＥＤＧＰＴＲ２Ｃ０Ｕ
ＮＴ１０Ｃ１０Ｃ５ ｐ４　　ｐ４　１０ＣＩＯＣ４ ｐ４ｐ５　　１１０　１０Ｃ３ ｐ４ｐ５１１０　１０８　２ ｐ５ｐ１　　　　　　　　１００　　　　　１０８　　
　　　１ｐ３ｐ２　　　１００　　　　　１０４　　　
　　０ｐ１ｐ２　　　　　　　　１０４　　　　　１０
４　　　　−１同様に第４８、第４ｂ、第４ｃ及び第４
ｄ図に示した他の形状及び位置付けの多角形について５
つの装置の内容を示すと、夫々次の第２ａ、第２ｂ、第
２０及び第２ｄ表の様になる。

第２ａ表 ＰＧＩ　　ＰＯ２Ｃ０ＵＮＴ ｐ３　　　ｐ５　　４ ｐ３ｐ４　　　　　５ ｐ３ｐ２　　２ ｐ４ｐ５　　　　　１ ｐ２ｐ１　　０ ｐ５ｐ１　　　　−１ 第２ｂ表 ＰＧＩ　　ＰＯ２Ｃ０ＵＮＴ ｐ３　　　ｐ３　　４ ｐ、５ｐ４　　　　　５ ｐ５ｐ２　　２ ｐ４ｐ５　　　　　１ ｐ２ｐ１　　０ ｐ５ｐ１　　　　−１ （ＰＧ２１７ｐ正） 第２ｃ表 ＰＧｌ　　ＰＯ２Ｃ０ＵＮＴ Ｐ　４　　　ｐ　４　　４ ｐ４ｐ５　　　　　３ Ｐ４Ｐ３　　２ ｐ３ｐ２　　１ ｐ２ｐ１　　０ ｐ５ｐ１　　　　−ｉ 第２ｄ ＰＧＩ　　　　　　ＰＯ２ ｐ３　　　　　　　ｐ３ ３ｐ４ ３ｐ２ ４ｐ５ Ｐ：２１）　１ １ｐ５ ｏ　ＵＮＴ 〇 ２　　　Ｎ　　　　　　腰 口 Ｅ４　点発生器ＰＧｊ及びＰＯ２ 第６図及び第７図に示した点発生装置ＰＧ１及びＰＯ２
はプレセンハム線発生装置の修正実施例である。

第８図に示し念ベクトル発生装置１８は次の様にセット
・アップされる。

マイクロ・コードがΔＸをその符号大きさに変換してＳ
Ｍ（ΔＸ）を形成し、Δｙをその符号大きさに変換して
ＳＭ（Δｙ）を形成する。

ＳＭ（△χ）をストローブして、符号Ｘ−符号（ΔＸ）
にセット ＳＭ（Δｙ）ｔストローブして、符号ｙ＝符号（Δｙ）
にセット 〔ベクトル発生装置のセットアツプ〕 （１）　　ＳＭ（Δｘ　）−８Ｍ（Δｙ　）を計算Ｄｘ
＝ｌΔｘｌ及びＤｙ＝ｌΔｙｌで、これ等は１２ビツト
の正の数であるから、２８Ｍ（Δｘ　　）−８Ｍ（Δｙ
　）＝２　Δｘ　−Δｙ　（２の補数）である。従って
符号ビットはｘＬＴｙである。

（２）ａ、もしｘＬＴｙ＝０　（Ｄｘ＝＞Ｄｙ）なら（
３１２Ｄ７　　　　−−）ＮＥＧＩＮＣ１８２（４１２
（Ｄｙ　　Ｄり−＞　ＰＯ８ｒＮＣ１８４（５）　　２
Ｄｙ−Ｄｘ　　−−）　ＤＮ　　１８６（６）　　Ｄｘ
　　　　　　−＞カウンタ１８８（２）　ｂ　、もしｘ
ＬＴｙ＝１なら （３）　　２Ｄｘ　　　　　−−）ＮＥＣＩＮＣ１８２
（４）　　　　２（Ｄｘ−Ｄｙ　　ン−−＞ＰＯ８ＩＮ
Ｃ（５）　　２Ｄｘ−Ｄｙ　　　＞ＤＮ　　１８（５（
６）　　Ｄｘ　　　　　　　　＞カウンタ　１８８ベク
トル発生装置１８（第８図）は入力ΔＸ及びΔｙを次の
パラメータに変換するＡＬＵＩ９０を含む。

ＤＸ＝　ｌ△ｘ１、ＤＹ＝　ｌΔｙ１と置き、もしＤＸ
）Ｄｙなら、ＮＥＧＩＮＣ＝２ＤＸ、ＰＯＳ　ＩＮＣ＝
２　（ＤＸ−ＤＹ）、カウンターＤＹ ８つの方向が次の６ビツトによって決定される。

符号（△Ｘ）、符号（Δｙ）、符号Ｉ　ＤＸ−ＤＹ　ｉ
〔多角形充填プロセッサ〕 多角形充填プロセッサ１６は２つの点発生装ｊ凧Ｐ　Ｇ
　１及びＰＧ２より成る（第６図及び第７図）。ＰＣＩ
及びＰＧ２は共に下から上に向って画素を発生するので
、符号Ｘ−符号（△Ｘ）及びｘｕｔｙ−符号（ＤＸ−Ｄ
Ｙ）によって決定さ扛るわずか４つの方向がある（第５
図参照）。

１）　Ｇ　１には次の様ないくつかの外部信号が与えら
れる。即ちいくつフカの制＃線が存在する。

ＰＧＩ　ＤＯＮＥ−現在の線の処理がなされた事を示す
。

ｌＮＣｌ−発生した画素のｙ値を１だけインクレメント
した事全示す。

ＰＧ　Ｉ　ＨＯＬＩ）−ＰＧ　２が走行中である、もし
くは新しい線をロード中である、もしくは多角形充填プ
ロセッサがパラメータ全ベクトル発生装置に通過中であ
るだめ、ＰＧｌを停止する。

ＸＩ　ｌＮＣ−次の画素を発生した時に、Ｘ１１ＮＣは
走査線レジスタＤＬの長さを１だけ増大（もしくは減少
）し、走査線レジスタの初期位置を１だけ減少（もしく
は増大）する。次にアップ・ダウン・カウンタＤＬ及び
ｘｐ　ｏ　ｓｌ制御する信号を示す。

Ｘ１１ＮＣ＝１ ＰＧｌ　　　符号Ｘ−符号（ΔＸン 符号ｘ＝１　　　符号ｘ＝Ｏ Ｄ　Ｌ　　　　　　　　＋　　ｔ　　　　　　　　　　
−１ＸＰＯＸ　　　　　−１＋１ ベクトル発生装置（第８図、第１０図）において、ＩＮ
ＣＲがＤｓｕｂｎ　（決定変数）の符号ビットを表わす
ものとする。Ｄ　ｘ　）　Ｄ　ｙならば、ｙ値はカウン
タ１８８の各サイクル毎にインクレメントされる。そう
でない時はｙ値は決定変数Ｄｓｕｂｎ＞０の時のみ、も
しくは（ＩＮＣＲ・・・・）信号が高い事が表明された
時にインクレメントされる。

ＰＧｌの場合はＩＮＣＲｌ全ＩＮＣＲに相当するものと
すると、 Ｘｉ　　ＩＮＣ＝（ｘｕ　ｔｙ・・）＋ｘ１１ｔｙ・（
ｌＮＣＲ１・・）ｆＮＣ１＝ｘ＋！ｔｙ＋（ｘｆｆｔｙ
・・）・（ｌＮＣＲ１・ＪＰＧ２の場合は、次の様ない
くつかの外部信号即ち制御信号（線）が存在する。

ＰＣ２ＤＯＮＥ−現在の線の処理が行われた事を示す。

ｌＮＣ２−発生した画素のｙ値を１だけインクレメント
した事を示す。

ＰＧ　２ＨＯＬＤ−ＰＧ　１が走行中、新しい線のロー
ド中、もしくは多角形充填プロセッサ１６がベクトル発
生装置１８にパラメータ全速っているために、Ｐ　Ｇ　
２　全停止する。

Ｘ２　ｌＮＣ−次の画素が発生した時に、Ｘ２ＩＮＣは
走査線レジスタＤＬｉ１だけ増加（もしくは減少）する
。次にアンプ・ダウン・カウンタＤＬ及びｘｐｏｓｌ制
御する信号？示す。

Ｘ丁ＮＣ＝１ ＰＧ２　　　符号Ｘ−符号（ΔＸ） 符号ｘ＝１　　　符号ｘ＝Ｏ Ｄ　　Ｌ　　　　　　　　−１＋　　１ＰＧ２の場合に
は、ｌＮＣＲ２がＩＮＣＲに相当する。

Ｘ２１ＮＣ＝（ｘＮｉｙ＝）＋ｘｌｌｔｙ　・（ＩＮＣ
Ｒ２・・）ＩＮＣ２＝ｘｎｔｙ＋（ｘＮｔｙ）・（ＩＮ
ＣＲ２・・）Ｒ５多角形充填サイクル（第９図） （１）マイクロコードがＤＯＦ　Ｉ　ＬＬを表明する、
。

（２）成るサイクルの後に、ＰＧ１開始が表明される。

（３１ＰＧ１がサイクル動作全開始し、ｙ値がインクレ
メントした時（ＩＮＣＩ＝１）、もしくは線分の充填が
完了した時（ＰＧＩ　ＤＯＮＥ＝１　）、或はこの両方
が行われた時に停止する。

（４）　　もしＰＧ　１　ＤＯＮＢ＝　１なら、ＰＧｌ
に（存在するならばン次のΔＸ、Δｙをロードし、マイ
クロコードがＰＧＩＲＥＳＴＡＲＴ（ＰＧ１再開始）を
表明してＰＧ１全再開始する。

（５）　　もしｒＮｃ１＝１も表明されていないと、Ｐ
Ｇｌは実行を続ける。もしＩＮＣＩ＝１が表明されてい
るとＰＧ２が実行を開始する。

（６）ＰＣ２はｙ値がインクレメントした時、もしくは
線分の充填が完了した時、或はこれ等が共に発生した時
に停止する。

（７）　　Ｐ　Ｇ　２　Ｄ　ＯＮ　Ｅ　＝　１ならば、
ＰＣ２には（もし存在するならば）次のΔｘ１Δｙがロ
ードされ、マイクロコードはＰＧ２ＲＥＳＴＡＲＴを表
明してＰＣ２を再開始する。

（８）　　Ｉ　Ｎ　Ｃ２＝　１も表明されていないと、
ＰＣ２は実行を続ける。ｌＮＣ２＝１が表明されている
と、ベクトル発生装置（ＶＧ）セットアツプ段階（・て
入る。

（９）ベクトル発生装置が遊休である事をチェックした
後（ＶＧＢＵＳＹ・・・・）、ＶＧＳ　ＥＴＵＰを表明
する。

（１０）成るサイクルの後、Ｘ５ＴＲＯＢＥがＶＣにＤ
Ｌをロードし、同時に、画素メモリのＸ位置カウンタに
ｘｐｏｘの値をロードする。

（１１）成るサイクルの後に、ＹＳＴＲＯＢＥがＶＧに
パラメータΔｙとしてＯをロードする。これと同時に画
素メモリのｙ位置カウンタの内容をインクレメントする
。

（１２）成るサイクルの後に、５ＴＡＲＴＬＩＮＥを表
明する。

（１６）成るサイクルの後にＣ０ＮＴを表明する。

（１４）成るサイクルの後に、ＰＣＩＳＴＡＲＴを表明
する。以上の過程を繰返す。

ロ　　ロ　　Ｆ　　Ｆ　　ロ　　−０００Ｃ１０ロ ロロ −Ｃ１ ００Ｃ）　ｙ　　　　　ｙ　Ｗ ｏ　　０　　ロ　　−　　ロ　　−　　Ｏロ　　−〇〇
　　−Ｏｖ−０口　　Ｏ口　　Ｏロ 苦 苦 硯　　　。

Ｏロ　　０　−　　口　　ＯＯＯＯ口 （イ） ロ　　ロ　　□　　　ｖ−ｒ−ＰＣ）　　　０　　　ロ
　　Ｃ口　　ロ　　０　　０　　０　　　ｙ　　　ＯＯ
口　　【０　　０　　　ｙ　　　ｖ−０Ｆ　　Ｏ０Ｃ）
　　　Ｉ−、−Ｑ、　　　　Ｑ、　　　　Ω、　　　ロ
、　　　α　　　−〉　　　ＸＯロ　　ＯＯＯＯロ Ｃ）　　　　ｒ−” ロ　　−ロ　へ 苦 −口　　０　　苦 苦 ロ　　ロ　　Ｏ留 ０　０　０　０　　ロ　　Ｏロ ロ　　ロ　　ＯＰ　　Ｏ口　　Ｏ 入　λ　詠 入　Δ　如 Δ　へ　Ｃ Φ　　−ｂｏ　　　Φ　　Φ　　　　　　　　−−〉入
りＱ　ｌ＋　Ｇｌ、偽へ　り留Ｑ Ｅ６　マイクロコードの論理式 上述の信号を発生するためのマイクロコードの論理式は
次の通りである。ここでく−はクロック動作によるもの
、−は直接動作によるものを示す。

ＰＧＤＯＮＥ＝ＰＧＩＤＯＮＥ＋ＰＧ２ＤＯＮＥ１）Ｇ
ｌＨＯＬＤＴ＜＝（ＰＧ１ＨＯＬＤ＋ＩＮＣＩ）・（Ｐ
ＣＩＳＴＡＲＴ＋ＰＧＩＲＥＳＴＡＲＴ）ＰＧ２１（Ｏ
ＬＤＴ（＝（ＰＧ２ＨＯＬＤ＋ｌＮＣ２）・ＰＧ　Ｉ　
ＨＯＬＤ＝ＰＧ　Ｉ　ＨＯＬＤＴ＋ＰＧＤＯＮＥＰＧ２
ＨＯＬＤ＝ＰＧ２ＨＯＬＤＴ＋ＰＧＤＯＮＥＰＧＩＳＴ
ＡＲＴ（＝ＤＯＦＩＬＬ＋Ｃ０ＮＴＰＣ２ＳＴＡＲＴ＜
＝ＩＮＣＩ・ＲＵＮＮＩＮＧＶＧＳＥＴＵＰ（＝ＶＧＳ
ＥＴＵＰ−ｙｓＴＲＯＢＥ＋ｌＮＣ２・ＲＵＮＮ　Ｉ　
ＮＧ ＸＳＴＲＯＢＥく＝ＶＧＳＥＴＵＰ−ＶＧＢＵＳｙ　；
又Ｘ位置カウンタにｘＰＯ８の内容をロードしても得ら
れる。

ｙｓＴＲＯＢＥ（＝ｘＳＴＲＯＢＥ　：又ｙ位置カウン
タ全インクレメント ５ＴＡＲＬＩＮＥ（＝ＳＴＡＲＬＩＮＥ−ＣＯＮＴ＋ｙ
ｓＴＲＯＢＥ ＣＯＮＴ（＝ＰＧＤＯＮＥ−８ＴＡＲＬＩＮＥＢＵＳｙ
（＝ＢＵＳｙ・ｌＮＣ２＋ＰＧ　Ｉ　５ＴＡＲＴ＋ＰＣ
２ＳＴＡＲＴ＋ＰＧＩＲＥＳＴＡＴ＋ＰＧ２ＲＥＳＴＡ
ＲＴ ＲＵＮＮＩＮＧ＝ＢＵＳｙ＠ＰＧＤＯＮＥＦ０発明の効
果 以上のように、本発明に従い、ラスク図形表示システム
中で表示される凸多角形を充填する装置が与えられる。

【図面の簡単な説明】

第１図（ａ）、（ｂ）は本発明に従う図形データ処理シ
ステムのブロック図である。第２ａ図は本発明の方法及
び装置によって充填されるべき多角形の一部を示した概
略図である。第２ｂ図は本発明に従い多角形の一部の２
つの辺間の・領域を充填したところを示した概略図であ
る。第６図は本発明の方法及び装置によって充填される
５角形の線図である。第４ａ図、第４ｂ図、第４ｃ図及
び第４ｄ図は夫々本発明に従って処理される異なる形状
及び位置付けの多角形を示した線図である。第５図は△
Ｘの符号と充填過程間を関連を示した概略図である。第
６図は本発明に従う点発生装置のブロック図である。第
７図は本発明に従う多角形充填プロセッサのブロック図
である。第８図は本発明に従うベクトル発生装置のブロ
ック図である。第９−１図及び第９−２図は本発明に従
う多角形充填過程のフローチャートである。 １２・・・・メモリ、１４・・・・図形プロセッサ、１
６・・・・多角形充填プロセッサ、１８・・・・ベクト
ル発生装置、２０・・・・画素メモリ。 出願人　　インターナシタカル・ビジネス・マシーンズ
・コーポレーション才１　回 図形舊理衷！ 多角形の一部 才２０回 ｆ％ｕ　　　　　　　　　ｒ：Ｊ４（Ｘ４．ｙ４）？＠
Ｌ２ 充煩動作 第２ｂａ］ ５角形の伊１ 才３図 Δ×の符号と充ま具の関イ系 才５０ 才４Ｃ回 ５角形０）９リ　　　　　　　　　　　　　　　　　　
　　　　　　５テり形Ｏダ１１オ４ｂ回　　　　　　　
　　　　　才４ｄ口、船、発生液！ ７６　　回 Ｐ角形フ５七・ンダ オ７圀 べ′り１〜ル完生駁置 オ８　図

Claims (1)

1. 【特許請求の範囲】 （ａ）制御情報及び入力データを記憶するための第１の
   メモリと、 （ｂ）上記入力データによつて画定される多角形の辺の
   座標決定手段と、 （ｃ）上記辺間を接続して上記多角形を充填するべく、
   複数本の充填線のためのパラメータを発生する手段と、 （ｄ）上記複数本の充填線の各々のための画素特性を発
   生する手段と、 （ｅ）表示装置上に表示するため上記画素特性を記憶す
   るための第２のメモリと、 （ｆ）上記第１のメモリ、上記座標決定手段、上記パラ
   メータを発生する手段、上記画素特性を発生する手段及
   び上記第２のメモリに接続され、多角形の充填線特性の
   計算を制御するプロセッサとを具備する、 図形処理装置。