JPH02275591A - 図形発生装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔産業上の利用分野］ 本発明は、三角形の塗りつぶしを高速に行う事を可能に
した図形発生装置である。

〔発明の概要〕

三角形の塗りつぶしを行う図形発生装置において、塗り
つぶし過程に線分の長さが負となる事をｊＵＩ別できる
回路を付加した。これによってＣＰＵの負イ苛を軽減さ
せ高速に三角形の塗りつぶしができる。

以下、図面を参照しながら従来の技術を説明する。

従来この種の図形発生装置は、第５図に示される様にＣ
ＰＵＩ、線分発生値Ｗ２、画像メモリ３で構成されてい
る。そこで、三角形の塗りつぶしを行う場合、第３図に
示した様に、スキャンライン方向に線分を発生させ、三
角形を塗りつぶして行くものであり、この時、線分の発
生の仕方は、最初に線分１０１を発生させ次に線分１０
２、線分１０３、線分１０４の様に順次上方向に発生さ
せて行う。

ここで、図形情報は画像メモリ３に書き込まれるために
、塗りつぶされた三角形と画像メモリ３に書き込まれた
ビクセルとの関係は、第４図に示した様になる。例えば
、第４図線分１０１を発生させる場合は、以下の手順で
発生を行っている。まず、第５図のＣＰＵ　（中央演算
処理装置）ｌによって線分１０１の始点へと終点Ｂとの
差分を求め、後段に置かれた線分発生装置２へ始点Ａの
座標値と差分ｌを渡す。次に、線分発生装置２では始点
Ａから差分１分だけスキャンライン方向に線分を発生さ
れる。同様に線分１０２の発生は始点りと終点已によっ
て線分発生が行われる。このように三角形Ａ、Ｂ、Ｃを
量子化されたピクセルで塗りつぶしを行っていく場合に
、第４図に示すように三角形内部のピクセルのみを発生
しなければならない。すなわち、Ａ点、Ｂ点、０点を頂
点とする三角形の塗りつぶしにおいては、Ａ点、Ｃ点間
の辺α、Ｂ点、Ｃ点間の辺βよりも外側のピクセルは発
生させてはいけない。そのため、三角形を構成するスキ
ャンライン方向の線分の始点５終点を求める際は、以下
のように行っていく。ここで、三角形を構成するスキャ
ンライン方向の線分の始点終点は、常に１点のみあれば
よいために、始点。

終点を求める演算方式は、Ｙ方向に１を加算するＹ方向
を主軸としたＯＤＡ演算を行わなければならない。

第８図にこの演算のアルゴリズムを示す、第７図に示す
Ａ点、Ｂ点。０点を頂点とする三角形において、まづ、
Ａ点と０点のＹ方向の差ΔＹを計算してＬとする＋８＋
。

次に、Ａ点の座標ＷＸ、Ｗ、を求め（ｂ、　　ｃ）、始
点座標（ＷＸ　、　Ｗｖ　）を出力する（ｄ＋。

ここで、Ｌ−０ならば終了する＋８＋。

Ｌ≠０ならば、次の線分の始点座標を演算する（ｆ、ｇ
）　、Ｌ−１＝Ｌを計算しくｈｌ、新たな線分の始点座
標を出力する＋ｄｌ。

ここで、処理ｇが四捨五入の場合では、第６図の２番目
の線分の始点はＩ（点となり、辺αより外側のピクセル
となってしまう、そのため、この場合は処理ｇは切り上
げ処理を行い、ピクセルＦ点を算出する。同様に、３番
目の始点は、四捨五入された１点ではなく切り上げ処理
を行ったＧ点としなければならない。第９図では、三角
形の内側に同じくピクセルを発生させるために切り捨て
処理が必要となることがわかる。しかし、切り上げ。

切り捨て処理を行うと、第１０図に示す様な鋭角三角形
の点Ａ付近の始点、終点ピクセルが逆となってしまう場
合が存在する。すなわち、辺ＡＣの切り上げ処理で生成
される始点ピクセル２２と、辺ＡＢの切り捨て処理で生
成される終点ピクセル２１とが逆となってしまう。この
ため、この場合は線分発生を中止しなければならず、線
分発生を行うか、中止するかの判別を第５図のＣＰＵ　
（中央演算処理装置）１が行っていた。

〔発明が解決しようとする課題〕

この線分発生を中止させるか否かの判別は、始点と終点
の減算を行った場合、演算結果が負となるかどうかであ
る。第３図に示しである様に、１つの三角形を構成する
スキャンライン方向の線分の数は多い。そのため、０本
の線分で構成される三角形の塗りつぶしには、必然的に
生成しようとする線分の長さが負であるかどうかを判別
するステップが２ステツプとすれば、三角形１つにつき
２×ｎステツプの負でがＣＰＵ　Ｌに付加され、処理の
高速化を妨げていた。

〔課題を解決するための手段〕

本発明は、上記問題点を解決するために、前記線分発生
部に対して、長さが負である線分を発生させない機構を
付加した。このことによって、従来ＣＰＵで行っていた
処理をハードウェア、すなわち線分発生部に持たせ高速
化を実現した。

〔作用〕

本発明は上記の構成によって、図形発生装置内のＣＰＵ
の負荷の軽減を実現し、これによって高速に三角形の塗
りつぶしが可能となった。

〔実施例〕

以下、本発明の好適な実施例を図面に基づき詳述する。

第１図は、本発明による図形発生装置の一実施例を示す
構成図である。本発明では、Ｃ））Ｕ（中央演算処理装
置）１から線分発生装置２ヘバス２に加えて５ＩＧＮ信
号７を付加させた。この５ＩＧＮ信号７がｆｌｉｇｈの
時、すなわち線分の長さが負の場合は、線分発生装置２
においては線分を発生しない。

さらに、線分発生装置２について第２図を用いて説明を
加える。線分発生装置２は線分の長さを保持する差分レ
ジスタ１３と差分カウンタ１４、制御回路１５、ＸＹ座
標発生回路、ビクセル発生回路１６から構成される。第
１図のｃｐｕ　＜中央演算処理装置）１からは、データ
バス８を介して差分レジスタ１３へ線分の長さ情報がセ
ットされる。この時、線分の長さ情報が正の時は、５Ｉ
ＧＮ信号７はり。

−となっている。次に、この線分発生回路に対して、ス
タート信号９がアクティブにされると、差分レジスタ１
３の内容が差分カウンタ１４へ移され、線分発生が始ま
る。差分カウンタ１４は１ビクセル発生するごとに、デ
クリメントされ差分カウンタ１４の内容がゼロ、すなわ
ち線分発生が終了した時、信号１７によって終了を制御
回路１５へ知らせる。線分の長さが負の場合は、５ＩＯ
Ｎ信号７は旧ｇｈとなり、この時、スタート信号９がア
クティブになっても制御回路１５は、線分発生を行わな
い構成となっている。

〔発明の効果〕

以上述べてきたように、本発明によれば負の線分を発生
させない機構を有することによって、より高速に三角形
の塗りつぶしが実現可能になったという効果を有するも
のである。

【図面の簡単な説明】

第１図は本発明による図形発生装置の一実施例を示す構
成図、第２図は本発明による線分発生回路の一実施例を
示すブロック図、第３図はスキャンライン方向に分割さ
れた三角形を示す図、第４図は三角形内のビクセルを示
す図、第５図は従来の図形発生装置の構成図、第６図は
第４図の辺α付近の拡大図、第７図、第８図は線分の始
点、終点演算処理を説明する図、第９図は切り捨て処理
が必要な場合を示す図、第１０図は始点、終点が逆とな
る場合を示す図である。 以上 出願人　セイコー電子工業株式会社

Claims (1)

【特許請求の範囲】
1. 三角形の塗りつぶしを行う図形発生装置において、三角
   形を塗りつぶす過程で、線分の長さが負となる事を判別
   する手段を有することを特徴とする図形発生装置。