1【特許請求の範囲】【請求項１】１走査線を１の連続部分のみに区画する多角形の頂点データを、転送順に、順次格納するリストメ
モリと、走査方向と直角な方向についての各頂点の座標値の最大値、および最小値に対応する頂点を、当該頂点の転送順位をリストメモリに記憶することにより検出す
る頂点検出手段と、頂点検出手段により検出された最大値、および最小値に対応する頂点を基準とし、かつ転送順序に基づいて頂点を区分する区分手段と、区分手段により区分された各区分毎に頂点検出手段により検出され 10た最大値に対応する頂点から頂点検出手段により検出された最小値に対応する頂点に向かって互に隣り合う頂点同士の頂点データを補間し、かつこの補間を両区分について並行して行なうことにより、同時に１対の稜線データを得る稜線データ算出手段と、走査線と稜線データ算

2出手段により得られた１対の稜線との交点を、上記転送順序および稜線の補間順序に対応させて始点または終点とする始終点算出手段と、頂点検出手段により検出された最大値、および最小値に対応する両頂点の何れか一方から他方に向かって順に、始点と終点との間に対応する走査線部分をぬりつぶし表示するぬりつぶし表示手段とを含むことを特徴とする走査型ディスプレイ装置における多角形ぬりつぶし装置。
【発明の詳細な説明】〈産業上の利用分野〉
この発明は走査型ディスプレイ装置上に一筆書き状に表示される多角形の内部をぬりつぶす装置に関する。
〈従来の技術〉
従来から走査型ディスプレイ上に一筆書き状に表示される多角形の内部をぬりつぶす方式が採用されている。

(2)3上記多角形の形状は種々雑多であり、大別すれば、第９図に示すように１走査線を１の連続部分のみに区画するもの、および第10図に示すように１走査線を２以上の連続部分に区画する可能性があるものに区分される。
そして、第９図に示す多角形であれば、走査線との交点の間の領域を単純にぬりつぶし表示すればよいのであるが、第10図に示す多角形であれば、走査線との交点が２対以上となる部分が存在し、何れの交点同士の間の領域をぬりつぶし表示すべきかを判別する必要がある。
このような点を考慮して、上記のぬりつぶし方式としては、多角形の各頂点データを、走査線の方向と直角な処理方向についてソーティングし、必要があれば走査線の方向についてソーティングし、走査線と交点を有する稜線のリストを作成して、始点−終点として対応する稜線の間を補間する。そして、全ての走査線について上記稜線のリストの作成、および対応する稜線の間の補間を行なうことにより、多角形の内部をぬりつぶし表示する方式が採用され、どのような種類の多角形でも、内部をぬりつぶすことができるようにしている。
また、上記第９図に示す種類の多角形についてのみ内部をぬりつぶすことができるようにした方式としては、
画像メモリと別個に面生成用メモリプレーンを有し、多角形の各頂点のデータに基いて隣り合う頂点間を補間することにより多角形の閉ループを表わす閉ループデータを画像メモリに書込むと同時に面生成用メモリプレーンにも閉ループデータを書込み、この閉ループデータの最大値、および最小値を検出しておき、最大値、および最小値により定まる領域についてのみ上記面生成用メモリ
プレーンを走査して上記閉ループデータを読出すに際し、各走査毎に閉ループと走査ラインとの交点を得、一対の交点の間に対応させて、上記画像メモリ、または面生成用メモリプレーンに所定の論理信号を書込んで、上記閉ループで囲まれる領域内を所定の表示データでぬりつぶした面画像データを生成する方式がある（特開昭55−3069号公報、および特開昭55−3070号公報参照）。
〈発明が解決しようとする問題点〉
上記前者の方式であれば、処理方向についてのソーティングを行なうことが必須であり、しかも演算の対象とする稜線のリストを作成して管理しなければならないので、メモリの管理が必要になるという問題があるとともに、データの読出し、ソーティング、演算等の処理、データの書込み等、CPUによる処理が多くなり、データが与えられてから内部がぬりつぶされた多角形を走査型ディスプレイ上に表示するまでに長時間がかかるという問題がある。
また、上記後者の方式であれば、直線補間回路が１回路しかなく、しかも多角形の各稜線の補間が何れの頂点から開始するのかが分からないので、画像メモリとは別個に面表示を行なうための、特別のメモリが多重に必要になるという問題があるのみならず、面表示のために、1020304050

特公平８−３１１３８4
メモリからのデータの読出し、およびメモリへのデータの書込みに長時間がかかるとともに、直線補間されるべき稜線の始点と終点とを得るまでに長時間がかかり、直線補間回路がかなりの時間ウェイト状態になるので、データが与えられてから内部がぬりつぶされた多角形を走査型ディスプレイ上に表示するまでに長時間がかかるという問題がある。
〈発明の目的〉
この発明は上記の問題点に鑑みてなされたものであり、ぬりつぶしのために必要なメモリの増加を抑制し、しかもデータが与えられてから内部がぬりつぶされた多角形を走査型ディスプレイ上に表示するまでの所要時間を短縮することができる走査型ディスプレイ装置における多角形ぬりつぶし装置を提供することを目的としている。
〈問題点を解決するための手段〉
１走査線を１の連続部分のみに区画する多角形の頂点データを、転送順に、順次格納するリストメモリと、走査方向と直角な方向についての各頂点の座標値の最大値、および最小値に対応する頂点を、当該頂点の転送順位とリストメモリに記憶することにより検出する頂点検出手段と、頂点検出手段により検出された最大値、および最小値に対応する頂点を基準とし、かつ転送順序に基づいて頂点を区分する区分手段と、区分手段により区分された各区分毎に頂点検出手段により検出された最大値に対応する頂点から頂点検出手段により検出された最小値に対応する頂点に向かって互に隣り合う頂点同士の頂点データを補間し、かつこの補間を両区分について並行して行なうことにより、同時に１対の稜線データを得る
稜線データ算出手段と、走査線と稜線データ算出手段により得られた１対の稜線との交点を、上記転送順序および稜線の補間順序に対応させて始点または終点とする始終点算出手段と、頂点検出手段により検出された最大値、および最小値に対応する両頂点の何れか一方から他方に向かって順に、始点と終点との間に対応する走査線部分をぬりつぶし表示するぬりつぶし表示手段とを含むものである。
上記の装置であれば、１走査線を１の連続部分のみに区画する多角形の各頂点データを、転送順、即ち一筆書き状の順序でリストメモリに格納し、走査方向と直角な方向についての各頂点の座標値の最大値、および最小値に対応する頂点を、当該頂点の転送順位を記憶することにより検出し、最大値、および最小値に対応する頂点を基準とし、かつ転送順序を考慮して頂点を区分する。そして、一方の区分については、リストメモリに格納された順序にしたがって、最大値に対応する頂点から最小値に対応する頂点に向かって互に隣り合う頂点同士に頂点データを補間して得た稜線データと走査線との交点を、転送順序が左回りであるか、右回りであるかに対応させて始点または終点とし、他方の区分については、リスト

(3)5メモリに格納された順序と逆の順序にしたがって、最大値に対応する頂点から最小値に対応する頂点に向かって互に隣り合う頂点同士の頂点データを補間して同時に得た１対の稜線データと走査線との交点を、転送順序が左回りであるか、右回りであるかに対応させて終点または始点とし、最大値に対応する頂点から最小値に対応する頂点に向かって、または最小値に対応する頂点から最大値に対応する頂点に向かって、順に、始点と終点との間に対応する走査線部分をぬりつぶし表示することにより、内部がぬりつぶされた多角形を走査型ディスプレイ上に表示することができる。
また、上記走査方向と直角な方向についての各頂点の座標値の最大値、および最小値に対応する頂点の検出を、当該頂点の転送順位を記憶することにより行なうものであるから、転送順位のみに基いて始点側の稜線、および終点側の稜線を把握することができ、カウンタ等のハードウェアによる対応が可能となる。
〈実施例〉
以下、実施例を示す添付図面によって詳細に説明する。
第１図はこの発明の多角形ぬりつぶし方式を実施するための、一実施例を示すブロック図である。
図において、座標変換処理、クリッピング処理等が施された図形データ（例えば第９図に示す多角形の各頂点の座標値、輝度値を示すデータ）が、最大、最小値頂点検出回路（１）、リストメモリ（２）、およびリストメモリ制御回路（３）に印加されている。そして、リストメモリ制御回路（３）による制御下においてリストメモリ（２）から読出された頂点データが左一辺終了検出回路（４）、右一辺終了検出回路（５）、および一多角形終了検出回路（６）に印加されているとともに、左辺補間回路（７）、右辺補間回路（８）にも印加され、上記左辺補間回路（７）、および右辺補間回路（８）からの補間データがDDA回路（直線補間描画回路）（９）に印加されている。さらに、上記左一辺終了検出回路（４）、右一辺終了検出回路（５）、および一多角形終了検出回路（６）からの終了検出信号が上記リストメモリ制御回路（３）に印加されている。
上記最大、最小値頂点検出回路（１）は、第２図に示すように、データバス（11）を通して転送される多角形の角数データが当初入力され、頂点データが入力される毎にカウントダウンする角数ダウンカウンタ（12）と、上記多角形の各頂点データを入力として最大値、最小値をそれぞれ検出する最大値検出回路（13）、最小値検出回路（14）と、ポインタ用アップカウンタ（15）と、上記最大値検出回路（13）からのラッチ信号に基いてポインタ用アップカウンタ（15）からのポインタ信号をラッチする最大値ポインタラッチ回路（16）と、上記最小値検出回路（14）からのラッチ信号に基いてポインタ用アップカウンタ（15）からのポインタ信号をラッチする最1020304050

特公平８−３１１３８6
小値ポインタラッチ回路（17）とを有している。
そして、上記角数ダウンカウンタ（12）からのカウントゼロ信号を上記最大値ポインタラッチ回路（16）、および最小値ポインタラッチ回路（17）に印加することにより、各ポインタラッチ回路（16）（17）にラッチされているポインタを上記データバス（11）に出力することができるようにしている。
即ち、多角形の各頂点データをリストメモリ（２）に書込む間に、最大値、最小値に対応するポインタを得、多角形の全ての頂点データの書込みを終了した時点で、上記ポインタをリストメモリ（２）に書込むことができ、ポインタを得るための特別の処理時間は必要でないことになる。
上記リストメモリ（２）は、第３図に示すように、行アドレスと列アドレスとで各データのアドレスを割付けられているものであり、行アドレスが０であり、かつ列アドレスが０であるメモリエリアに多角形の角数データを格納し、行アドレスが１からｎであるメモリエリアに多角形（ｎの角数の多角形）の各頂点データを格納し、行アドレスがｎ＋１であり、かつ列アドレスが０であるメモリエリアに最大値ポインタを格納し、行アドレスがｎ＋１であり、かつ列アドレスが１であるメモリエリアに最小値ポインタを格納している。そして、上記行アドレスが１からｎまでのメモリエリアは、列アドレスが０から３までのメモリエリアに区画されており、２次元輝度変化なし、２次元輝度変化あり、３次元輝度変化なし、および３次元輝度変化ありの各モードの何れのデータ（x,y），（x,y,I），（x,y,z），（x,y,z,I）にも対応できるようにしている。
以後の多角形についても、同様の配列（多角形の角数データ、各頂点データ、最大値ポインタ、および最小値ポインタの配列）で各メモリエリアにデータが格納されている。
上記リストメモリ制御回路（３）は、第４図に示すよ
うに、先頭行アドレスと、多角形の角数に１を加算して得たデータとを加算して最大値ポインタ、および最小値ポインタが格納されている行アドレス（第３図の場合にはｎ＋１）を得、上記行アドレスに格納されている最大値ポインタと、上記先頭行アドレスとを加算することにより最大値行アドレスを得ることができる。もちろん最小値ポインタと先頭行アドレスとを加算することにより最小値行アドレスを得ることができる。
したがって、最大値ポインタ、および最小値ポインタに基いて簡単に、最大値、および最小値に対応する頂点の行アドレスを得ることができ、例えば、転送されてくる多角形の各頂点データの順序が反時計回りであれば、行アドレスを順次増加させることにより（例えば、与えられた多角形の角数ｎと等しい進数のアップカウンタを順次カウントしてゆくことにより）、最大値に対応する頂点から最小値に対応する頂点に向かう頂点データを順(4)7次得ることができ、または行アドレスを順次減少させる
ことにより（例えば、与えられた多角形の角数ｎと等しい進数のダウンカウンタを順次カウントしてゆくことにより）、最小値に対応する頂点から最大値に対応する頂点に向かう頂点データを逆の順序、即ち、最大値に対応する頂点から最小値に対応する頂点に向かう順序で順次得ることができる。
上記左一辺終了検出回路（４）は、第５図に示すように、ｙ座標（走査線と直角な方向の座標）を基準として、開始点（ｙ座標がy0）から一点補間する毎にｙ座標値を減算し、稜線の終了点のｙ座標値ynと一致した時点での１の稜線の補間が終了したことを検出し、終了検出信号をリストメモリ制御回路（３）に印加する。
上記右一辺終了検出回路（５）についても同様である。
上記一多角形終了検出回路（６）は、第６図に示すよ
うに、ｙ座標値が最大の点ymaxから左右両辺の補間を行なってゆき、ｙ座標値が最小値yminと一致した時点で１の多角形の処理が終了したことを検出し、終了検出信号をリストメモリ制御回路（３）に印加する。
上記左辺補間回路（７）、および右辺補間回路（８）は、例えば、多角形の各頂点データが反時計回りに転送され、しかもｙ座標値の最大値から順に補間を行なってゆく場合には、それぞれ左側の稜線に対応する頂点アドレス用アップカウンタ、右側の稜線に対応する頂点アドレス用ダウンカウンタを有し、両カウンタに初期値としてｙ座標値の最大値アドレスをロードし、第７図に示す
ように、最大値アドレスを基準として同時にカウントア
ップ、およびカウントダウンを行ない、左右の稜線を同時に補間し、左の稜線の補間値を始点、右の稜線の補間値を終点としてDDA回路（９）に印加する。
以上の構成であれば、座標変換、クリッピング等が施されたデータ（多角形の角数データ、および各頂点データ）をリストメモリ（２）に格納する間に、最大、最小値頂点検出回路（１）により、走査線とｙ座標値（走査線と直角な方向の座標値）の最大値、および最小値に対応する頂点のポインタを検出して、リストメモリ（２）の上記データの後に格納する。
そして、リストメモリ制御回路（３）の制御下において上記ポインタに基いて最大値に対応する頂点データを左辺補間回路（７）、および右辺補間回路（８）に入力するとともに、上記頂点データの後の頂点データ、および前の頂点データをそれぞれ左辺補間回路（７）、および右辺補間回路（８）に入力し、ｙ座標値の最大値を基準として各稜線の補間を行ない、両補間値をDDA回路（９）に印加する。以上の場合において、各稜線の補間が終了したと判別された場合には、左一辺終了検出回路（４）、または右一辺終了検出回路（５）からの終了検出信号に基いてリストメモリ制御回路（３）の制御下において次の頂点データを対応する補間回路に入力する。

1020304050

特公平８−３１１３８8
以上のようにして全ての稜線の補間が終了した場合には、一多角形終了検出回路（６）からの終了検出回路に基いてリストメモリ制御回路（３）の制御下において次の多角形のデータを読出して、上記と同様の処理を反復することにより、必要な全ての多角形についての処理を行なうことができる。
第８図はより具体化した実施例を示している。尚、第８図には、第１図、第２図の各構成要素に対応する参照符号が付記されている。
図において（11）はデータバスであり、（18）はデータバスを通して転送されるデータの最初のワードとしてのモードワード（２次元輝度変化なし、２次元輝度変化あり、３次元輝度変化なし、および３次元輝度変化ありの各モードを示す情報、多角形の角数を示す情報等）を解析するモードワード解析部であり、データバス（11）を通して転送される多角形の角数データが当初入力され、頂点データが入力される毎にダウンカウントする角数ダウンカウンダ（12）をも兼ねている。（13）は最大値検出部であり、（14）は最小値検出部であり、（15）はポインタ用アップカウンタであり、（16）は最大値ポインタラッチ部であり、（17）は最小値ポインタラッチ部であり、（19）は上記モードワード解析部（18）からの、モード情報を入力としてモード別の制御信号を出力する属性別制御部であり、（20）は属性別制御部（19）からのアドレスインクリメント信号を入力として入力側アドレスを発生させるアップカウンタである。
（21）（22）（23）（24）は、それぞれｘ座標値用、ｙ座標値用、ｚ座標値用、インデックス値（輝度値等）用のリストメモリであり、それぞれ２枚のRAMで構成されている。ここで、各リストメモリが２枚のRAMで構成されているのは、１枚のRAMに格納可能なポリゴン数を越えた場合に、他のRAMを用いてポリゴンの各頂点データの格納を行なわせることができるようにするためであるとともに、リストメモリの下位側が処理要求の要求を行なっており、かつ上位側で現在転送中のものが完了したことを条件としてRAMの切換を行なわせて上位・下位間の速度差を吸収するためである。
（25）はポリゴン数カウンタであり、（26）は各２枚づつのRAMを切換えるためのRAM切換制御部であり、（27）（28）（29）はそれぞれ左辺を補間するための減算部、除算部、加算部であり、（30）（31）（32）はそれぞれ右辺を補間するための減算部、除算部、加算部であり、（33）は両辺の補間演算同期部である。
（34）はDDA側アドレス発生部であり、（35）は実行終了検出部であり、（36）（37）はモードワードラッチ部である。
したがって、この実施例の場合にも、例えば、第７図中に矢印で示すように、転送順序が左回りの場合に（任意の頂点を基準として反時計回り方向に、上位プロセッサから頂点データが順次転送される場合に）、最大値に(5)特公平８−３１１３８

910
対応する頂点から最小値に対応する頂点に向かって互に＊ メモリの増加を抑制することができるとともに、転送順隣り合う頂点同士の頂点データを補間して得た稜線（第位のみに基いて始点側の稜線、および終点側の稜線を把７図中の左辺参照）と走査線との交点を始点として把握握することができ、カウンタ等のハードウェアにより対することができるとともに、最小値に対応する頂点から応が可能になり、しかもメモリからの読出し、およびメ最大値に対応する頂点に向かって互に隣り合う頂点同士モリへの書込みの頻度を減少させて、データが与えられの頂点データを補間して得た稜線（第７図中の右辺参てから内部がぬりつぶされた多角形を走査型ディスプレ照）と走査線との交点を終点として把握することができイ上に表示するまでの所要時間を短縮することができる（転送順序が左回りの場合）、この把握結果に基いてぬという特有の効果を奏する。
りつぶし表示を行なうことができるので、ぬりつぶした【図面の簡単な説明】
面データを書込むメモリは必要でなく、しかもメモリか 10 第１図はこの発明の多角形ぬりつぶし方式を実施するたらの読出し、およびメモリへの書込みの頻度を著しく減めの、一実施例を示すブロック図、少させて、データが与えられてから内部がぬりつぶされ第２図は最大、最小値頂点検出回路を詳細に示す図、た多角形を走査型ディスプレイ上に表示するまでの所要
第３図はリストメモリの内容を示す図、時間を著しく短縮することができる。具体的には、従来第４図はリストメモリ制御回路の動作を説明する図、800ポリゴン/sec.程度の速度であったのに比べて、上記第５図は左一辺終了検出回路の動作を説明する図、実施例によれば40000ポリゴン/sec.程度の速度にするこ
第６図は一多角形終了検出回路の動作を説明する図、とができた。ここで、１ポリゴンは20ドット×20ドット
第７図は左辺補間回路、および右辺補間回路の動作を説の任意方向に傾斜した正方形を意味している。
明する図、
尚、この発明においては、１走査線を１の連続部分の第８図はより具体化した実施例を示すブロック図、みに区画する多角形についてのみぬりつぶし処理を行な 20 第９図、および第10図は異なるタイプの多角形を示す
わせることができるので、上記以外の多角形については図。
従来方式によるぬりつぶし処理を行なう必要があるが、（１）……最大、最小値頂点検出回路、（２）……リス
特に３次元図形においては殆どが上記多角形に該当する
トメモリ、（３）……リストメモリ制御回路、（７）…
ので、非常に有用性が高いものであるといえる。
…左辺補間回路、（８）……右辺補間回路、（９）……
〈発明の効果〉
DDA回路
以上のようにこの発明は、ぬりつぶしのために必要な＊
【第２図】

【第５図】

【第６図】

(6)

【第１図】

特公平８−３１１３８

【第７図】

【第９図】

【第３図】

(7)

【第４図】

【第１０図】

特公平８−３１１３８(8)【第８図−１】

特公平８−３１１３８(9)【第８図−２】

特公平８−３１１３８