JPH03278190A

JPH03278190A - 多角形塗りつぶし方式

Info

Publication number: JPH03278190A
Application number: JP2078081A
Authority: JP
Inventors: Mitsuo Ouchi; 大内　光郎
Original assignee: NEC Corp
Current assignee: NEC Corp
Priority date: 1990-03-27
Filing date: 1990-03-27
Publication date: 1991-12-09
Anticipated expiration: 2013-08-06
Also published as: JP2782904B2

Abstract

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

Description

【発明の詳細な説明】〔産業上の利用分野〕本発明は、ディスプレイやプリンタに文字や図形を表示
あるいは印字する際の図形描画における多角形塗りつぶ
し方式に関し、特に外形が線分で定義された多角形内を
塗りつぶす多角形塗りつぶし方式に関する。

〔従来の技術〕

ディスプレイ上に図形・文字を表示する技術は、急速に
進歩しており、より美しい図形・文字を表示するなめに
様々な方式を提案されてきた。

特に文字を表示する方式は、ビットマツプ・フォント方
式、アウトライン・フォント方式と呼ばれる方式が主流
である。

ビットマツプ・フォント方式は、文字をｍ　Ｘ　ｎビッ
トのパターンとしてＲＯＭなどに格納しておき、画面の
１画素ごとに複数のビットを対応させたビットマツプ・
メモリの任意の位置にそのパターンをそのまま転送する
方式である。この方式は、どんな複雑な文字を表示する
場合でもｍＸｎビットのデータを転送するたけで済むた
め、処理が単純で高速であり様々なディスプレイ装置で
主流となっている方式である。しかしながら、この方式
には文字を拡大あるいは縮小した時に次の様な欠点がで
でくる。拡大時には斜めの線にジャギーとよばれる階段
状のギザギザが生じ見栄えが良くない、縮小時には点や
線がぬけるため文字品質が悪くなるなどである。

そこで文字を拡大・縮小しても品質が劣化しないアウト
ライン・フォント方式がクローズアップされている。こ
の方式を説明すると、文字情報として文字の外形（アウ
トライン）を定義する線分の頂点の座標をフォントとし
て持たせておき、文字を表示する際にはこれらの頂点間
を直線あるいは曲線で描画し、続いてこの図形内を塗り
つぶす。このようにして生成される文字は、拡大・縮小
するときに、座標値を変換すればよく、その後は上述し
た塗りつぶしを行えば良い。このようにすると、与えら
れる頂点と頂点の間は直線あるいは曲線で補間されるの
でジャギーや線抜けがなくなり、拡大縮小率に関係なく
美しい字体をそのまま保つことができる。

アウトライン・フォントの実際の描画方法について説明
する。まず、フォントＲＯＭに格納された文字の外形を
定義する線分の両端点のＸＹ座標を読出し、拡大縮小率
に応して座標変換を行う。

この座標変換は、一般によく知られているアフィン変換
と呼ばれる３×３の行列演算であり、変換後の座標値を
もとに、文字の外形内を塗りつぶすものである。この方
法には２種類あり、ＥＶＥＮ／○ＤＤ　　ＷＩＮＤＩＮ
Ｇ　　ＮＵＭＢＥＲルールによる塗りつぶしく以下ＥＯ
フィルと呼ぶ）とＮ０Ｎ−ＺＥＲＯＷＩＮＤ、ＩＮＧ　
　ＮＵＭＢＥＲルール（以下ＮＺファイルと呼ぶ）であ
る。

ＷＩＮＤＩＮＧ　　ＮＵＭＢＥＲ（以下ＷＮという）と
は、第５図（Ａ）に示すように、多角形を構成する線分
を左から検査し、交差した線分が下向きであれば、その
線分の右側の領域のＷＮを＋１し、上向きであれは−１
してえちれる数値である。このＷＮをベースにして、ど
の部分を塗りつぶすかを決定する方法に２種類あり、こ
れがＥＯファルとＮＺフィルである。ＥＯフィルは、第
５図（Ｂ）に示すようにＷＮが奇数の部分だけを塗りつ
ぶすもので、ＮＺフィルは、第５図（Ｃ）に示すように
ＷＮが０でない部分を塗りつぶすものである。したがっ
て、同じ多角形でも塗りつぶす規則により結果が異なる
。

ＥＯフィルについては、台形フィルを描画するハードウ
ェアを用いて多角形内を塗りつぶす方式が知られている
。まず、台形の４頂点をどう選ぶかについて述べる。こ
の４頂点のうち、２点は多角形を構成する線分の両端点
であり、他の２点は全頂点のＸ座標のうちの最小値Ｘ□
１ｎによって決定する点である。つまり、台形は文字外
形のある線分の両端点の座標を（χ１．Ｙ１）、（Ｘ２
゜Ｙ２）としたときに、この線分を右辺とし、左辺が（
ＸｍＩｎ、Ｙ１）、（Ｘ、、、１．、Ｙ２）の線分とし
て与えられるものである。この台形を“０′クリアされ
たビットマツプ・メモリ上へ描画する。

ビットマツプ・メモリ上へ書込む際のデータ処理として
、書込むビット位置のデータをリードし、そのデータと
′１″を排他的ＯＲしてからメモリ上に書込むようにす
る。こうして全ての線分について台形描画を行うと所望
のアウトライン文字の内側だけが１゛となる。これは、
排他的ＯＲで描画するために、ビットマツプ・メモリ上
の左から右へむかって、奇数番目に交差した点からつぎ
の点までが“１″となり、偶数番口に交差した点から次
の点までは０“どなるからである。

このようにＥ○フィルによる多角形内塗りつぶしは、台
形フィルを高速に描画できるハードウェアを利用して、
高速にアウトライン文字を描画することができる。

一方、ＮＺフィルを実現する方法としては、多角形の上
から１ラインずつ検査し、１ライン上に存在する線分と
の交点を算出しながら、どの範囲が塗りつぶすべき領域
であるかを判定し描画する方法が使用されている。この
方法は、ＮＺフィルはもちろん、処理の一部を変更する
だけでＥＯフィルにも適用できるのて、広く使用されて
いる。

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

しかし、従来の台形フィルによる方法は、ＥＯフィルに
関しては高速に処理できたが、ＮＺフィルに関しては使
用できなかった。一方、１ライン単位に領域を判定する
方法は、１ライン上に存在する交点の数が多くなると各
交点の座標を計算する時間、交点のソーティング時間が
膨大になり処理が低速であるという欠点をもっていた。

ＥＯフィルに関しては、前述した台形フィルによる方法
の方が一般に十倍高速である。

本発明の目的は、このような問題を解決し、多角形塗り
つぶしを２段階の処理に分けることによってＥ○フィル
、ＮＺフィルのいずれの方法に対しても使用できると共
に、高速に塗りつぶしができる多角形塗りつぶし方式を
提供することにある。

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

本発明の構成は、ディスプレイやプリンタに文字や図形
を表示あるいは印字するために画素ごとに対応したメモ
リを備え、このメモリ上に座標系を定義し、多角形の頂
点群の座標を入力として多角形の内部に位置する前記メ
モリ上のビットを塗りつぶす多角形塗りつぶし方式にお
いて、前記頂点群の座標値から予め定めた方法て基準点
の座標値Ｘをもとめる第１の工程と、前記頂点群のうち
の頂点Ａからつぎの頂点Ｂへの移動方向をもとめる第２
の工程と、前記頂点Ａの座標（Ｘｌ。

Ｙ１）と前記頂点Ｂの座標（Ｘ２、Ｙ２）と、前記座標
値Ｘを参照した座標（Ｘ、Ｙ１）と座標（Ｘ、Ｙ２）で
決定される台形内を塗りつぶす第３の工程と、この第３
の工程において前記台形内を塗りつぶす際に、前記移動
方向により前記メモリに書かれている内容をリード／モ
ディファイ／ライトする演算モードを少なくとも複数の
算術演算の中から選択する第４の工程と、前記第１から
第４の工程によって前記全頂点に関する台形塗りつぶし
処理を終了した後、前記多角形に外接する長方形内のデ
ータを検査して、特定の基準でデータを変更して別の領
域に書込む第５の工程とを備えることを特徴とする。

〔実施例〕

次に本発明について図面を参照して説明する。

第１図は本発明の第１の実施例を説明するフローチャー
ト、第２図は第１図を実現するシステムのハードウェア
構成図である。本実施例は、ソフトウェア手段によって
多角形塗りつぶしを行う場合について述べる。第２図に
おいて、１はＣＰＵ、２は主記憶、３はビットマツプ・
メモ９す、４は表示コントローラである。

まず、本実施例の処理の流れについて説明する。ＮＺフ
ィル、Ｅ○フィルいずれもワークメモリを使用し、これ
を主記憶２上の一部にマツピングする。ＣＰＵＩはこの
ワークメモリ上でＷＮを計算しなから図形の元情報を生
成していく。主記憶２には、ワークメモリだけでなくｃ
ｐｕｌが処理を実行するためのプログラムやデータが格
納される。このあと、ＣＰＵＩはこのＷＮ情報をベース
に、ビットマツプ・メモリ３上に最終図形を描画するの
である。ワークメモリは、ＷＮ値を格納するために使用
するので、ＷＮ値の最大値、最小値をあらかしめ想定し
て１画素に相当するビット数を決定しておく。本実施例
では、１ラスク上に１４本以下の線分しか存在しないと
いう前提のもとで、ＷＮは４ビツトで表現し、つまりＷ
Ｎの取り得る値の範囲は、−７≦ＷＮ≦７である。ビッ
トマツプ・メモリ３に描画された内容は表示コントロー
ラ４を介してディスプレイに表示される。

　０次に、第１図を用いて多角形塗りつぶしの方式いついて
詳細に説明する。まず、ステップ１０１〜１０３のルー
プにおいて、ステップ１０１で゛多角形を形成する線分
の端点の座標（Ｘ、Ｙ）をすべてリードし、ステップ１
０２において最大値Ｘ　ｍａＸ　＋　Ｙｍａｘ　＋最小
値Ｘｍ１ｎ＋Ｙｍｌｎを検出する。全座標についてこの
処理を終了後、ここで求めた最大、最小値は使用するワ
ークメモリの大きさを決定するために用い、（Ｘｍ１ｎ
、Ｙ、、、Ｉｎ）と（ＸｍａＸＹ、ｎａＸ）を対角線の
端点とする長方形内を処理の対象とする。この領域はＷ
Ｎ値の格納用として使用するのて、初期設定としてステ
ップ１０４においてこの領域内のデータを“０″クリア
しておく。

次に、ステップ１０５において多角形上の連続する２点
の座標値をリードする。台形はこの２点ノＪｕ標値（Ｘ
　１　、　Ｙ　１　）、（Ｘ２、Ｙ２）を右辺、（Ｘ、
、、Ｉｎ、Ｙ１）、（Ｘ、Ｉｎ、Ｙ２）を左辺として決
定される。つまり、この台形の上底と下底はＸ軸に平行
である。台形フィルの演算モードは、ステップ１０６に
おいて２点の座標のＹ座標により決定する。つまり、Ｙ
ｌとＹ２を比較し、Ｙｌ＞Ｙ２てあれば”　＋　’Ｉ　
”モード、Ｙ１≦Ｙ２であれば゛−１°″モードとする
。

ここまでが台形フィルの前処理であり、以降台形フィル
の実際の動作となる。

台形フィルは、ステップ１０７〜１］１のループで構成
され、１ラインごとの描画を繰り返すことによって実現
する。あるラインの処理に入る際には、ステップ１０７
において右辺を直線発生により座標を生成し、１ライン
上の処理データの範囲を決定する。このライン」−のデ
ータをステップ１０８によって、１画素ずつリードし、
前述した演算モードにしたがってその画素値に＋１ある
いは−１したあと、同じ番地にリライトする（ステップ
１０９）。この処理を１ライン上の全画素について実行
する。さらに、この処理を全ラインに繰り返すと１つの
台形フィルの処理が完了する。

引続いて、ステップ１１２において全ての頂点について
の台形フィル処理が終了したかどうかをチエツクし、終
了していない場合には、つぎの頂点についての処理を繰
り返し実行する。全頂点について終了すると、その多角
形内のＷＮ値が全て決定される。

次に、実際にビットマツプ・メモリ３への書込みになる
。ＮＺフィルかＥＯフィルかによって処理が異なるのは
この部分である。この処理は基本的には、多値のＷＮ値
から１１０の２値の値を生成することである。

まず、ＮＺフィルについて説明する。ワークメモリ上の
（Ｘｍ＋ｎ　、　Ｙｍｌｎ　）と（ｘ、、、、、、ｙ−
、りを対角線の端点とする長方形は処理の対象となる多
角形に外接する領域である。この領域内について処理を
進める。ステップ１１３において、この矩形領域内のデ
ータつまりＷＮ値を１画素分づつリードし、ステップ１
１５においてＷＮ値が′“Ｏ″であれば“Ｏ”、ＷＮ値
が”　ｏ　”以外であれば′１“°とし２値の出力を得
る。この出力値の１１０の従って、データをビットマツ
プ・メモリ上の所望の位置に書込む。本実施例では、こ
の出　３カイ直が“１′″であれば゛、ステップ１１６において
、相当するビットを′１′″て描画し、出力値が“′０
″であれば描画しないで、ステップ１１７にジャンプす
るようにしている。これを矩形領域内の全ＷＮ値につい
て実行すると処理が完了する。

これはＮＺフィルの場合である。ＥＯフィルの場合はＷ
Ｎ値を２値化する際に、ステップ１１５の代りにステッ
プ１４を実行し、ＷＮが偶数であれば’ｏ”、奇数であ
れば′１°°を出力するように変更されるだけである。

以上によって、Ｅ○フィル、ＮＺフィルの両方の規則に
よる多角形フィルを実行できる。この場合、どんな多角
形を塗りつぶす際にも、上述したフローと全く同様に処
理することができる。

本発明においては、第１の処理で、従来の台形フィルを
行う際に、ビットマツプ・メモリへの書込みの段階で論
理演算だけでなく算術演算をサポートし、台形の左右直
線の方向によりその算術演算の種類を変更し、第２の処
理として、第１の処理を多角形の全ての線分に対して実
行した後　４に、メモリに格納されているＷＮ値を全て検査しフィル
の種類に応してそのＷＮに対応するビットマツプ・メモ
リ上に描画するか否かを判定するという新しい処理を導
入することにより、Ｅ○フィル、ＮＺフィルいずれの方
法による多角形内塗りつぶしをも実現できるようにして
いる。

第３図は本発明の第２の実施例を実施するハードウェア
のブロック図、第４図は第３図の台形フィル・プロセッ
サのブロック図であり、本実施例は第１の実施例の一部
をハードウェア化し、高速化した多角形塗りつぶし装置
であり、処理のながれは第１図に示したフローチャート
と同しである。本実施例は、第１の実施例に第２図に台
形フィル・プロセッサ５が付加されたものである。

ビットマツプ・メモリ３は、台形フィル・プロセッサ５
のワークエリアとしても使用され、またＣＰＵＩがビッ
トマツプ・メモリ３を直接アクセスできるようなバスを
用意している。これは、台形フィル・プロセッサ５がア
クセスするメモリをＣＰＵ１のバスと切り離すことによ
って高速化を図る目的がある。したかって、第１の実施
例との相違点は、ワークメモリをビットマツプ・メモリ
３にマツピングしたこと、フローの一部を台形フィル・
プロセッサ５に実行させたことだけである。ここでは台
形フィル・プロセッサ５の動作を中心に説明する。

台形フィル・プロセッサ５が処理する内容は、第１図の
フローチャー１〜のステップ１０７〜］１１の部分てあ
り、この部分をハードウェア化するために第４図の構成
をとった。台形フィル　プロセッサの設計のポイントは
、１ライン上の複数の画素に対する処理をワード単位に
一括して実行するようにしている。本実施例では、１ワ
ード１６ビツトとし、４画素分のデータを一括して演算
する演算回路などを備えた。

第４図において、１０はリードデータ　レジスタ、１１
はライトデータ・レジスタ、１２〜１５は演算回路、１
６はアドレス発生回路、１７はＤＤＡ発生回路、１８は
ピクセル・カウンタ、１９は加算値生成回路、２０はエ
ンドフラグである。

ステップ１０７は、ＤＤＡ生成回路１７により行われ、
この結果、１ライン上の描画すべきピクセル数が決定さ
れる。つづくステップ１０８１０９を１ワ一ド単位で処
理するようにしている。これは、ビットマツプ・メモリ
３がらリードした１ワードのデータをリードデータ・レ
ジスタ１０に格納し、そのデータに対して演算回路１２
〜１５を同時に動作させる。１ワードは１６ビツトなの
で、各演算回路にはＷＮ値のビット数に相当する４ビツ
トずつデータが入力される。リードデータ・レジスタ１
ｏの内容と共に演算回路１２〜１５に入力されるのが加
算値である。この加算値は、加算値生成回路１９で生成
され、各演算回路ごとに独立した値を出力する。この加
算値の生成条件は、まず、ステップ１０６で決定された
演算モードが”　＋　１　”モードの場合“１″、演算
モードが−１″の場合パ−１°”、さらに、ピクセル・
カウンタ１８から出力されるエンド・フラグ　７２０がアクティブのときには演算モードによらず０″′
になる。このエンド　フラグ２０は１ラインの最終ワー
ドに含まれる複数の画素のうち、演算の対象にならない
画素に対してアクティブになる。こうして演算回路１２
〜１５て演算された個々のデータは、再び１ワードにパ
ックされてライトデータ・レジスタ１１に格納され、ビ
ットマツプ・メモリ３にリライトされる。

ステップ１．１０はピクセル・カウンタ１８で処理され
る。つまり、ＤＤＡ発生回路１７で決定された１ライン
上のピクセル数を初期値として１ワ一ド分処理が終了す
るごとに、このピクセル・カウンタ１８の内容を４ずつ
減算する。この結果が負になれば１ラインの処理が終了
する。ステップ１１１はアドレス発生回路１６で行われ
、アドレス発生回路１６には座標Ｙ１からＹ２を減算し
た値が格納されており、この回数すなわちライン数分ア
ドレスを発生すると処理を終了するようになっている。

なお、本実施例てはＷＮ値を４ビツトとじた　８が、この数値に制限されるものではない。またＷＮ値を
もとにしたビットマツプ・メモリへの書込みに関して、
データを書込むか否かを区別することにしたが、ＷＮ値
の判定をもとに、カラーや演算モードを選択するように
構成することも容易に実現できる。さらに、描画する際
に任意形状のクリッピング領域を定義しておき、その領
域内だけが描画できる範囲とした装置においても、クリ
ッピング領域をあらかじめ本方式で生成し、実際の多角
形をＷＮ値をもとにビットマツプ・メモリへ書込む際に
、クリッピング領域をマスクとして扱った３オペランド
演算を応用して実現することも考えられる。要するに、
本発明は、多角形の内側か外側かをＥ○ルール、ＮＺル
ールいずれの規則によってもほとんど同一の処理で判定
できるような方式であって、その後の描画形態などの付
帯的な事項に制限されるものでない。

〔発明の効果〕

以上述べたように、本発明によれば、台形フィルを処理
の基本としており、もとの多角形の複雑さに依存せず単
純な処理を繰り返して実行することにより、所望のＥＯ
フィル、ＮＺフィルのいずれの多角形塗りつぶしをも高
速に実行てきるといプ効果がある。

【図面の簡単な説明】

第１図は本発明の第１の実施例を説明するフローチャー
ト、第２図は第１図を実施するハードウェアのフロック
図、第３図は本発明の第２の実施例を説明するハードウ
ェアのブロック図、第４図は第３図の台形フィル・プロ
セッサのブロック図、第５図（Ａ）〜（Ｃ）は多角形塗
りつぶしの説明図である。１・・・ＣＰＵ、２・・・主記憶、３・・・ビットマツ
プ・メモリ、４・・・表示コントローラ、５・・・台形
フィル・コントローラ、１０・・・リードデータ・レジ
スタ、１１・・・ライトデータ・レジスタ、１２〜゛１
５・・・演算回路、１６・・・アドレス生成回路、１７
・・・ＤＤＡ生成回路、１８・・・ピクセル・カウンタ
、１９・・・加算生成回路、２０・・・エンド・フラグ
、０１〜１７・・・処理ステップ。　１−

Claims

【特許請求の範囲】

ディスプレイやプリンタに文字や図形を表示あるいは印
字するために画素ごとに対応したメモリを備え、このメ
モリ上に座標系を定義し、多角形の頂点群の座標を入力
として多角形の内部に位置する前記メモリ上のビットを
塗りつぶす多角形塗りつぶし方式において、前記頂点群
の座標値から予め定めた方法で基準点の座標値Ｘをもと
める第１の工程と、前記頂点群のうちの頂点Ａからつぎ
の頂点Ｂへの移動方向をもとめる第２の工程と、前記頂
点Ａの座標（Ｘ１、Ｙ１）と前記頂点Ｂの座標（Ｘ２、
Ｙ２）と、前記座標値Ｘを参照した座標（Ｘ、Ｙ１）と
座標（Ｘ、Ｙ２）で決定される台形内を塗りつぶす第３
の工程と、この第３の工程において前記台形内を塗りつ
ぶす際に、前記移動方向により前記メモリに書かれてい
る内容をリード／モディファイ／ライトする演算モード
を少なくとも複数の算術演算の中から選択する第４の工
程と、前記第１から第４の工程によって前記全頂点に関
する台形塗りつぶし処理を終了した後、前記多角形に外
接する長方形内のデータを検査して、特定の基準でデー
タを変更して別の領域に書込む第５の工程とを備えるこ
とを特徴とする多角形塗りつぶし方式。