1【特許請求の範囲】【請求項１】上位プロセッサから転送された多角形の頂点データを受け取り、各頂点データに基づいて、多角形をぬりつぶし描画するための走査線と直角な方向についての極大、極小を検出する極大極小検出手段（Ｂ）と、極大極小検出手段（Ｂ）による検出結果に基づいて極大、極小に対応する頂点が１点づつであるか否かを判別する個数判別手段（Ｃ）と、個数判別手段（Ｃ）による判別結果に基づいて、１走査線を１の連続部分のみに区画する多角形であるか否かを判別する多角形判別手段
10（Ｃ）とを含むことを特徴とする多角形の種類判別装置。
【請求項２】多角形の頂点データが輪郭線に沿う順序で順次転送されるものであり、極大極小検出手段（Ｂ）が、各頂点データを前後の頂点データと比較することに2より、極大、極小の検出を行なうものであり、個数判別手段（Ｃ）が、極大、極小に対応する頂点の数の和が２以下であるか否かを判別するものであり、多角形判別手段（Ｃ）が、頂点の数の和が２以下であることを示す個数判別手段（Ｃ）の判別結果に応答して、１走査線を１の連続部分のみに区画する多角形であると判別するものである上記特許請求の範囲第１項記載の多角形の種類判別装置。
【発明の詳細な説明】＜産業上の利用分野＞
この発明は走査型ディスプレイ装置上に一筆書き状に表示される多角形の種類が、１走査線を１の連続部分のみに区画するものに相当するか否かを判別する装置に関する。
＜従来の技術＞

(2)3
従来から走査型ディスプレイ上に一筆書き状に表示される多角形の内部をぬりつぶす方式がグラフィック・ディスプレイ装置等において採用されている。
上記多角形の形状は種々雑多であり、大別すれば、第10
図に示すように１走査線を１の連続部分のみに区画するもの、および第11図に示すように走査線を２以上の連続部分に区画するものに区分される。
そして、第10図に示す多角形であれば、走査線との交点の間の領域を単純にぬりつぶし表示すればよいのであるが、第11図に示す多角形であれば、走査線との交点が２対以上となる部分が存在し、何れの交点同士の間の領域をぬりつぶし表示すべきかを判別する必要がある。
このような点を考慮して、上記のぬりつぶし方式としては、例えばWater Filling Methodとして広く知られているように、多角形の各頂点データを、走査線の方向と直角な処理方向についてソーティングし、必要があれば走査線の方向についてソーティングし、走査線と交点を有する稜線のリストを作成して、始点−終点として対応する稜線の間を補間する。そして、全ての走査線について上記稜線のリストの作成、および対応する稜線の間の補間を行なうことにより、多角形の内部をぬりつぶし表示する方式が採用され、どのような種類の多角形でも、内部をぬりつぶすことができるようにしたものが一般的に採用されている。
また、上記第10図に示す種類の多角形についてのみ内部をぬりつぶすことができるようにした方式を考えてみれ
ば、ソーティングが不要になり、しかも稜線のリストの量が変化しないので管理を簡素化することができ、ぬりつぶし処理を高速で行なうことができるという利点を有すると思われる。
したがって、多角形の種類に対応させて上記両方式が選択的に採用されるようにすれば、多角形のぬりつぶし処理を全体として高速化することができるのであるが、従来は、上記２つの方式を多角形の種類に対応させて選択的に採用するための基準を、使用者の判断に委ねていた。
＜発明が解決しようとする問題点＞
上記従来の選択方式であれば、多角形の種類の判別を使用者の判断に委ねているので、判断を誤ると、不適正な方式により多角形のぬりつぶし処理を行なうことになり、ぬりつぶし処理の高速化が達成できない場合が生じ、或は確実なぬりつぶし処理を行なうことができなくなるという問題がある。
＜発明の目的＞
この発明は上記の問題点に鑑みてなされたものであり、ぬりつぶしを行なうべき多角形の種類を、１走査線を１の連続部分のみに区画するものであるか否かに大別して自動的に判別することができる多角形の種類判別装置を提供することを目的としている。
＜問題点を解決するための手段＞

1020304050

特公平７−４３７７１4
上記の目的を達成するための、この発明の多角形の種類
判別装置は、上位プロセッサから転送された多角形の頂点データを受け取り、各頂点データに基づいて、多角形をぬりつぶし描画するための走査線と直角な方向についての極大、極小を検出する極大極小検出手段と、極大極小検出手段による検出結果に基づいて極大、極小に対応する頂点が１点づつであるか否かを判別する個数判別手
段と、個数判別手段による判別結果に基づいて、１走査線を１の連続部分のみに区画する多角形であるか否かを判別する多角形判別手段とを含んでいる。
但し、多角形の頂点データが輪郭線に沿う順序で順次転送されるものであり、極大極小検出手段が、各頂点データを前後の頂点データと比較することにより、極大、極小の検出を行なうものであり、個数判別手段が、極大、極小に対応する頂点の数の和が２以下であるか否かを判別するものであり、多角形判別手段が、頂点の数の和が２以下であることを示す個数判別手段の判別結果に応答して、１走査線を１の連続部分のみに区画する多角形であると判別するものであることが好ましい。
＜作用＞上記の装置であれば、多角形の各頂点データを、隣合う頂点データと比較することにより、走査方向と直角な方向についての各頂点の座標値の極大、および極小に対応する頂点を検出し、極大に対応する頂点と極小に対応する頂点の数が各１であるか否かに基いて、多角形の種類を、１走査線を１の連続部分のみに区画する種類に相当するものであるか否かを判別することができる。
また、上記多角形の頂点データが輪郭線に沿う順序で順次転送されるものであり、極大極小検出手段が、各頂点データを前後の頂点データと比較することにより、極大、極小の検出を行なうものであり、個数判別手段が、極大、極小に対応する頂点の数の和が２以下であるか否かを判別するものであり、多角形判別手段が、頂点の数の和が２以下であることを示す個数判別手段の判別結果に応答して、１走査線を１の連続部分のみに区画する多角形であると判別するものであれば、頂点データをリストメモリに転送する途中において極大、極小の検出を行なうことができる。そして、転送開始頂点が極大、極小の何れにも該当しない場合には、極大、極小に対応する頂点の数の和が２となり、転送開始頂点が極大、極小の何れかに該当する場合には、極大、極小に対応する頂点の数の和が１となるので、極大、極小に対応する頂点の数の和が２以下であるか否かに基いて、多角形の種類を、１走査線を１の連続部分のみに区画する種類に相当するものであるか否かを判別することができる。
＜実施例＞
以下、実施例を示す添付図面によって詳細に説明する。
第１図はこの発明の多角形の種類判別方式を実施するための、一実施例を示す電気回路図である。
図において、座標変換処理、クリッピング処理等が施さ(3)5れた図形データ（例えば第10図、または第11図に示す多角形の各頂点の座標値、輝度値を示すデータ）が、増減検出部Ａに入力されて増減状態が検出され、増減検出信号が極大、極小検出部Ｂに入力されて極大、極小が検出され、極大、極小検出信号が個数判別部Ｃに入力されて個数の和が２個以下であるか否かが判別されるようにしている。
さらに詳細に説明すれば、上記増減検出部Ａは、第１段目のラッチ回路（11）と、第２段目のラッチ回路（12）と、コンパレータ（13）とから構成されており、第１段目のラッチ回路（11）にｉ番目の頂点データが入力された状態において第２段目のラッチ回路（12）に（ｉ−１）番目の頂点データが入力され、両頂点データのうち、走査線と直交する方向のデータ（以下、単に頂点データと称する）をコンパレータ（13）で比較することにより、ｉ番目の頂点データが（ｉ−１）番目の頂点データより大きいか小さいかを判別し、判別結果を極大、極小検出部Ｂに入力することができるようにしている。
上記極大、極小検出部Ｂは、フリップ・フロップ回路（14）と、２個のインバータ（15）（16）とから構成されており、上記コンパレータ（13）からの、ｉ番目の頂点データが（ｉ−１）番目の頂点データより大きいことを示す出力信号を、インバータ（15）を介してフリップ・フロップ回路（14）のプリセット入力端子に入力するとともに、ｉ番目の頂点データが（ｉ−１）番目の頂点データより小さいことを示す出力信号を、インバータ（16）を介してフリップ・フロップ回路（14）のリセッ
ト入力端子に入力して、ｉ番目の頂点データを先行する（ｉ−１）番目の頂点データより小さく、しかも次続するｊ番目の頂点データ（但し、ｊ≧ｉ＋１）が（ｊ−１）番目の頂点データよりも大きい場合に、極小であることを示すＱ信号（Ｑ信号の立上りのタイミングが極小指示信号となる）を出力し、ｉ番目の頂点データが先行する（ｉ−１）番目の頂点データより大きく、しかも次続するｊ番目の頂点データ（但し、ｊ≧ｉ＋１）が（ｊ−１）番目の頂点データよりも小さい場合に、極大であることを示す 信号（ 信号の立上りのタイミングが極大指示信号となる）を出力することができるようにしている。
上記個数判別部Ｃは、互に等しい構成の極大個数判別部（17）、極小個数判別部（18）、および両個数判別部（17）（18）からの出力信号が入力されるANDゲート（19）とから構成されている。
そして、上記極小個数判別部（18）は、上記フリップ・フロップ回路（14）からのＱ信号がクロック入力端子に入力される２個のフリップ・フロップ回路（20）（21）を有しており、上記フリップ・フロップ回路（20）からのＱ信号をフリップ・フロップ回路（21）のＤ入力端子に入力し、上記フリップ・フロップ回路（21）からの信号を上記ANDゲート（19）に入力している。したがっ1020304050

特公平７−４３７７１6て、当初クリア信号によりセットされた状態において、上記フリップ・フロップ回路（14）からのＱ信号が２回以上入力された場合にのみ 信号がローレベルになる。
また、上記極大個数判別部（17）の構成は、上記極小個数判別部（18）と同じであるから、説明を省略する。
したがって、上記両個数判別部（17）（18）からの各信号がハイレベル（極大、極小の検出回数が１回以下）の場合にのみANDゲート（19）が、１走査線を１の連続部分のみに区画する種類の多角形であることを示すハイレベルの信号を出力することができる。
尚、上記頂点データとしては、２次元輝度変化なし、２次元輝度変化あり、３次元輝度変化なし、および３次元輝度変化ありの各モードの何れのデータ（x,y），（x,y,I），（x,y,z），（x,y,z,I）であってもよい。
第２図は上記の種類判別方式により判別された、第10図に示すタイプの多角形の内部をぬりつぶすための装置の一実施例を示すブロック図である。
図において、座標変換処理、クリッピング処理等が施された図形データ（例えば第10図に示す多角形の各頂点の座標値、輝度値等を示すデータ）が、最大、最小値検出回路（２）、リストメモリ（３）、およびリストメモリ制御回路（４）に印加されている。そして、リストメモリ制御回路（４）による制御下においてリストメモリ（３）から続出された頂点データが左一辺終了検出回路（５）、右一辺終了検出回路（６）、および一多角形終了検出回路（７）に印加されているとともに、左辺補間回路（８）、右辺補間回路（９）にも印加され、上記左辺補間回路（８）、および右辺補間回路（９）からの補間データがDDA回路（直線補間描画回路）（10）に印加されている。さらに、上記左一辺終了検出回路（５）、右一辺終了検出回路（６）、および一多角形終了検出回路（７）からの終了検出信号が上記リストメモリ制御回路（４）に印加されている。
上記最大、最小検出回路（２）は、第３図に示すように、データバス（22）を通して転送される多角形の角数データが当初入力され、頂点データが入力される毎にカウントダウンする角数ダウンカウンタ（23）と、上記多角形の各頂点データを入力として最大値、最小値をそれぞれ検出する最大値検出回路（24）、最小値検出回路（25）と、ポインタ用アップカウンタ（26）と、上記最大値検出回路（24）からのラッチ信号に基いてポインタ用アップカウンタ（26）からのポインタ信号をラッチする最大値ポインタラッチ回路（27）と、上記最小値検出回路（25）からのラッチ信号に基いてポインタ用アップカウンタ（26）からのポインタ信号をラッチする最小値ポインタラッチ回路（28）とを有している。
そして、上記角数ダウンカウンタ（23）からのカウントゼロ信号を上記最大値ポインタラッチ回路（27）、および最小値ポインタラッチ回路（28）に印加することにより、各ポインタラッチ回路（27）（28）にラッチされて(4)7いるポインタを上記データバス（22）に出力することができるようにしている。
即ち、多角形の各頂点データをリストメモリ（３）に書込む間に、最大値、最小値に対応するポインタを得、多角形の全ての頂点データの書込みを終了した時点で、上記ポインタをリストメモリ（３）に書込むことができ、ポインタを得るための特別の処理時間は必要でないことになる。
上記リストメモリ（３）は、第４図に示すように、行アドレスと列アドレスとで各データのアドレスを割付けられているものであり、行アドレスが０であり、かつ列アドレスが０であるメモリエリアに多角形の角数データを格納し、行アドレスが１からｎであるメモリエリアに多角形（ｎの角数の多角形）の各頂点データを格納し、行アドレスがｎ＋１であり、かつ列アドレスが０であるメモリエリアに最大値ポインタを格納し、行アドレスがｎ＋１であり、かつ列アドレスが１であるメモリエリアに最小値ポインタを格納している。そして、上記行アドレ
スが１からｎまでのメモリエリアは、列アドレスが０から３までのメモリエリアに区画されており、２次元輝度変化なし、２次元輝度変化あり、３次元輝度変化なし、および３次元輝度変化ありの各モードの何れのデータ（x,y），（x,y,I），（x,y,z），（x,y,z,I）にも対応できるようにしている。
以後の多角形についても、同様の配列（多角形の角数データ、各頂点データ、最大値ポインタ、および最小値ポインタの配列）で各メモリエリアにデータが格納されている。
上記リストメモリ制御回路（４）は、第５図に示すように、先頭行アドレスと、多角形の角数に１を加算して得たデータとを加算して最大値ポインタ、および最小値ポインタが格納されている行アドレス（第４図の場合にはｎ＋１）を得、上記行アドレスに格納されている最大値ポインタと、上記先頭行アドレスとを加算することにより最大値行アドレスを得ることができる。もちろん最小値ポインタと先頭行アドレスとを加算することにより最小値行アドレスを得ることができる。
したがって、最大値ポインタ、および最小値ポインタに基いて簡単に、最大値、および最小値に対応する頂点の行アドレスを得ることができ、例えば、転送されてくる多角形の各頂点データの順序が反時計回りであれば、行アドレスを順次増加させることにより（例えば、与えられた多角形の角数ｎと等しい進数のアップカウンタを順次カウントしてゆくことにより）、最大値に対応する頂点から最小値に対応する頂点に向かう頂点データを順次得ることができ、または行アドレスを順次減少させることにより（例えば、与えられた多角形の角数ｎと等しい進数のダウンカウンタを順次カウントしてゆくことにより）、最小値に対応する頂点から最大値に対応する頂点に向かう頂点データを逆の順序で順次得ることができ

1020304050

特公平７−４３７７１8る。
上記左一辺終了検出回路（５）は、第６図に示すように、ｙ座標（走査線と直角な方向の座標）を基準として、開始点（ｙ座標がy0）から一点補間する毎にｙ座標値を減算し、稜線の終了点のｙ座標値ynと一致した時点で１の稜線の補間が終了したことを検出し、終了検出信号をリストメモリ制御回路（４）に印加する。
上記右一辺終了検出回路（６）についても同様である。
上記一多角形終了検出回路（７）は、第７図に示すように、ｙ座標値が最大の点ｙmaxから左右両辺の補間を行なってゆき、ｙ座標値が最小値ｙminと一致した時点で１の多角形の処理が終了したことを検出し、終了検出信号をリストメモリ制御回路（４）に印加する。
上記左辺補間回路（８）、および右辺補間回路（９）は、例えば、多角形の各頂点データが反時計回りに転送され、しかもｙ座標値の最大値から順に補間を行なってゆく場合には、それぞれ左側の稜線に対応する頂点アドレス用アップカウンタ、右側の稜線に対応する頂点アドレス用ダウンカウンタを有し、両カウンタに初期値としてｙ座標値の最大値アドレスをロードし、第８図に示すように、最大値アドレスを基準として同時にカウントアップ、およびカウントダウンを行ない、左右の稜線を同時に補間し、左の稜線の補間値を始点、右の稜線の補間値を終点としてDDA回路（10）に印加する。
以上の構成であれば、座標変換、クリッピング等が施されたデータ（多角形の角数データ、および各頂点データ）をリストメモリ（３）に格納する間に、最大、最小値頂点検出回路（２）により、走査線とｙ座標値（走査線と直角な方向の座標値）の最大値、および最小値に対応する頂点のポインタを検出して、リストメモリ（３）の上記データの後に格納する。
そして、リストメモリ制御回路（４）の制御下において上記ポインタに基いて最大値に対応する頂点データを左辺補間回路（８）、および右辺補間回路（９）に入力するとともに、上記頂点データの後の頂点データ、および前の頂点データをそれぞれ左辺補間回路（８）、および右辺補間回路（９）に入力し、ｙ座標値の最大値を基準として各稜線の補間を行ない、両補間値をDDA回路（10）に印加する。以上の場合において、各稜線の補間が終了したと判別された場合には、左一辺終了検出回路（５）、または右一辺終了検出回路（６）からの終了検出信号に基いてリストメモリ制御回路（４）の制御下において次の頂点データを対応する補間回路に入力する。
以上のようにして全ての稜線の補間が終了した場合には、一多角形終了検出回路（７）からの終了検出回路に基いてリストメモリ制御回路（４）の制御下において次の多角形のデータを読出して、上記と同様の処理を反復することにより、必要な全ての多角形についての処理を行なうことができる。
第９図はより具体化したぬりつぶし装置を示している。

(5)特公平７−４３７７１910
図において（22）はデータバスであり、（29）はデータ＊ て、上記実施例によれば40000ポリゴン/sec.程度の速度バスを通して転送されるデータの最初のワードとしてのにすることができた。ここで、１ポリゴンは20ドット×モードワード（２次元輝度変化なし、２次元輝度変化あ20ドットの任意方向に傾斜した正方形を意味している。
り、３次元輝度変化なし、および３次元輝度変化ありの尚、上記何れのぬりつぶし装置においても、１走査線を各モードを示す情報、多角形の角数を示す情報等）を解１の連続部分のみに区画する種類の多角形についてのみ析するモードワード解析部であり、（24）は最大値検出ぬりつぶし処理を行なわせることができるので、上記以部であり、（25）は最小値検出部であり、（26）はポイ外の多角形については従来公知の方式（例えばWater Fiンタ用アップカウンタであり、（27）は最大値ポインタlling Method等）によるぬりつぶし処理を行なう必要がラッチ部であり、（28）は最小値ポインタラッチ部でああるが、特に３次元図形においては殆どが上記多角形にり、（30）は上記モードワード解析部（29）からの、モ 10 該当するので、この発明による種類判別を行なって、１ード情報を入力としてモード別の制御信号を出力する属
走査線を１の連続部分のみに区画する種類の多角形のみ性別制御部であり、（31）は属性別制御部（30）からのについて上記装置によるぬりつぶし処理を行なうこと
アドレスインクリメント信号を入力として入力側アドレ
は、全体としての処理の高速化の面から非常に有用性がスを発生させるアップカウンタである。
高いものであるといえる。
（32）（33）（34）（35）は、それぞれｘ座標値用、ｙ＜発明の効果＞
座標値用、ｚ座標値用、インデックス値（輝度値等）用
以上のようにこの発明は、走査線と直角な方向の極大、のリストメモリであり、それぞれ２枚のRAMで構成され極小に対応する頂点の数の和が２であるか否かを判別すている。
ることにより、簡単に多角形の種類を、１走査線を１の（36）はポリゴン数カウンタであり、（37）は各２枚づ連続部分のみに区画する種類の多角形か否かを判別する
つのRAMを切換えるためのRAM切換制御部であり、（38） 20 ことができるという特有の効果を奏する。
（39）（40）はそれぞれ左辺を補間するための減算部、【図面の簡単な説明】
除算部、加算部であり、（41）（42）（43）はそれぞれ第１図は多角形の種類判別方式を実施するための、一実右辺を補間するための減算部、除算部、加算部であり、施例を示す電気回路図、（44）は両辺の補間演算同期部である。
第２図は多角形ぬりつぶし装置の一例を示すブロック（45）はDDA側アドレス発生部であり、（46）は実行終図、了検出部であり、（47）（48）はモードワードラッチ部
第３図は最大、最小値頂点検出回路を詳細に示す図、である。
第４図はリストメモリの内容を示す図、
したがって、このぬりつぶし装置の場合にも、最大値に第５図はリストメモリ制御回路の動作を説明する図、対応する頂点から最小値に対応する頂点に向かう稜線と第６図は左一辺終了検出回路の動作を説明する図、走査線との交点を始点として把握することができるとと 30 第７図は一多角形終了検出回路の動作を説明する図、もに、最小値に対応する頂点から最大値に対応する頂点
第８図は左辺補間回路、および右辺補間回路の動作を説に向かう稜線と走査線との交点を始点として把握するこ
明する図、とができ（転送順序が左回りの場合）、この把握結果に第９図はより具体化した多角形ぬりつぶし装置を示すブ
基いてぬりつぶし表示を行なうことができるので、ぬりロック図、つぶした面データを書込むメモリは必要でなく、しかも第10図、および第11図は異なるタイプの多角形を示すメモリからの読出し、およびメモリへの書込みの頻度を図。
著しく減少させて、データが与えられてから内部がぬり
Ａ……増減検出部、Ｂ……極大、極小検出部、つぶされた多角形を走査型ディスプレイ上に表示するまＣ……個数判別部、（17）……極大個数判別部、での所要時間を著しく短縮することができる。具体的に（18）……極小個数判別部、（19）……ANDゲートは、従来800ポリゴン/sec.程度の速度であったのに比べ＊40
【第６図】

【第７図】

(6)

【第１図】

特公平７−４３７７１

(7)

【第２図】

【第８図】

特公平７−４３７７１【第１０図】【第１１図】

(8)

【第３図】

【第４図】

特公平７−４３７７１

(9)

【第５図】

特公平７−４３７７１

(10)【第９図−１】

特公平７−４３７７１

(11)【第９図−２】

特公平７−４３７７１