JPH01196677A - パターンデータ生成方式 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 ［発明の目的］ （産業上の利用分野） この発明は、２次元のビットマツプ上で境界のデータが
定義された任意の閉図形の塗りつぶしが行なわれたパタ
ーンデータを生成するパターンデータ生成方式に関する
。

（従来の技術） グラフィクスの分野では、境界が多角形の領域を塗りつ
ぶしてパターンデータを作る要求が高い。

また、ＤＤＡ　（ディジタル微分解析器）等のハードウ
ェアを用いて任意の曲線を１点ずつ発生し、その内部を
塗りつぶす要求も高い。従来では、このような要求に対
し、多角形のスキャン変換を用いて塗りつぶしを行なっ
ている。このスキャン変換では、２次元のビットマツプ
の１つの方向を選び、これをスキャン方向と呼び、これ
に平行な直線をスキャンラインと呼ぶ。塗りつぶしの際
には各スキャンライン毎に閉図形の中に含まれる線分の
両端の座標を求め、その線分を全て塗りつぶすことによ
り閉図形全体の塗りつぶしを行なうようにしている。

次に、従来の多角形のスキャン変換による塗りつぶし処
理を、第１０図並びに第１１図（ａ）ないしくＣ）を用
いて説明する。なお、第１０図において、７１はスキャ
ン変換を行なう矩形領域であり、７２〜７７はそれぞれ
境界の多角形の頂点、７８〜８３はそれぞれ多角形の辺
、９１は１つのスキャンラインである。

■　まず、１つのスキャンライン９１について、多角形
の辺との交点ＰＯ，Ｐｉ、Ｐ２．Ｐ３を求め、それをス
キャン方向の座標値の順番にソートする。

■　次に交点が辺の端、すなわち多角形の頂点である場
合は、多角形の辺の繋がり方に応じた処理を行なう。例
えば、第１１図（ａ）の場合、頂点Ａは通常の交点と同
じに取扱う。また、第１１図（ｂ）の場合、頂点Ｂ、Ｃ
のうち、片方を交点として取扱う。さらに第１１図（Ｃ
）の場合には頂点りを交点２個分として取扱う。

■　次に、ソートされた交点を２つずつ対にして、それ
を両端とする線分（第１０図中の線分８４゜８５）を塗
る。

このため、従来ではソート等のソフトウェアによる処理
時間がかかり、高速な塗りつぶし処理が行なえず、また
ハードウェア化も困難であった。

また、線分を塗る際には上記の■の手順で説明したよう
に、頂点について特別な処理を必要とする。さらに、境
界を定義する曲線の１点毎の変化をプロセッサによりソ
フトウェア的に、またはＤＤＡ等のハードウェアにより
生成した場合でも、スキャン変換では１点毎の変化を１
つの線分として取扱わざるを得ず、そのために扱うデー
タ量が膨大になってしまう欠点がある。

（発明が解決しようとする課題） このように従来では閉図形の塗りつぶしを行なう場合に
、高速に行なえない、ハードウェア化が困難、等の種々
の欠点がある。

この発明は上記のような事情を考慮してなされたもので
あり、その目的は、塗りつぶしを高速に行なうことがで
き、かつハードウェア化が容易なパターンデータ生成方
式を提供することにある。

［発明の構成］ （課題を解決するための手段） この発明のパターンデータ生成方式は、入力データに基
づき、ビットマツプメモリ上で１つの方向をスキャン方
向としたとき、スキャン方向に沿った塗るべき線分の全
てにつき、各線分の２つの端点のうち一方はそれ自体の
点、他方はスキャン方向に１点だけずれた点をビットマ
ツプメモリに書込む手段と、１つのスキャンライン上に
ｂＯｌｂ　１．−、　　ｂ　（ｗ−’２）　、　　ｂ　
（ｗ−１）からなるＷ個（Ｗは正の整数）の点が存在す
る際に、点ｂ（ｊ）（ｊは０以上でＷ未満）に対応した
位置にｂｏ、ｂｌ、・・・、ｂ　（ｊ−１）のデータの
排他的論理和データを書込み、全てのスキャンラインに
ついて同様のデータ書込みを行なうことにより、上記閉
曲線で囲まれた領域の塗りつぶしが行なわれたパターン
データを生成する手段とを具備したことを特徴としてい
る。

また、この発明のパターンデータ生成方式では、閉曲線
で囲まれた領域の塗りつぶしの際には、口ウ、カラム方
向がビットマツプのｘ、ｙ方向に対応し、かつ１ロウ毎
に前記点ｂ（ｊ）に対して書込みを行なうべきｂＯ，ｂ
ｌ、・・・、ｂ　（ｊ−１）のデータの排他的論理和の
演算を行なう専用のメモリを使用することを特徴として
いる。

（作用） この発明のパターンデータ生成方式では、塗りつぶしを
行なうべき領域に対し、境界のデータは、右回り、左回
りいずれかの方向が定義されている。

そして、このデータは閉曲線の開始点の座標と、１点毎
の変化ｔｉｌｔｄｘ、ｄｙとして与えられる。ここで、
ｄｘ、ｄｙそれぞれ＋１．−１．０のいずれか１つの値
をとる。

このようなデータから塗りつぶしパターンデータを生成
するために、専用のメモリもしくはメモリの矩形領域を
使用し、ｄｘ、ｄｙのデータから境界を表わす点をメモ
リに書込む。この境界を表わす点とは境界上の点自体で
はなく、塗るべき線分の端点の一方はそれ自体、他方は
スキャン方向に１点ずらしたものである。

このようにして境界を表わす点をメモリに書込んだ後は
、スキャンラインに沿って各点にデータを書込むことに
より塗りつぶされたパターンデータを得る。このとき、
１つのスキャンラインが例えばＷビットからなっている
時、スキャンライン上の各点におけるビットデータをｄ
Ｏ，ｄｉ、・・・。

ｄ（ｗ−１）とすると、次のような排他的論理和演算を
順次行ない、その結果をメモリに書込むことによって塗
りつぶされたパターンデータｄＯ’。

ｄ１′、・・・、ｄ（ｗ−１）’を得るようにしている
。

以下、図面を参照してこの発明を実施例により説明する
。

第２図はこの発明の第１の実施例を実現するために使用
されるハードウェアの構成を示すブロック図である。図
において、１１は例えばホストコンピュータ等からなる
入力装置、１２はプロセッサ、１３はメモリ、１４はＣ
ＲＴなどの表示装置であり、これらはバス１５で相互に
接続されている。

上記人力装置１１は、塗りつぶしを行なう領域の境界線
を、右回りもしくは左回りの方向が定義された閉曲線の
データとして、開始点のＸ＋Ｙ座標と、それぞれ＋１．
−１．０の値をとる１点毎の座標の変化ｆｆ１ｄｘ、ｄ
ｙを順次出力する。

プロセッサ１２は上記データｄｘ、ｄｙに基づき、スキ
ャン方向に沿った塗るべき線分の全てにつき、各線分の
２つの端点のうち一方はそれ自体の点、他方はスキャン
方向に１点だけずれた点を、上記メモリＩ３巾に構成さ
れた２次元のビットマツプの矩形領域（以下、単にメモ
リと称する）に書込む。なお、上記入力装置１１の代わ
りにこのプロセッサ１２が座標の変化ｆｉｄｘ、ｄｙを
出力するようにしていもよい。さらにプロセッサ１２は
、メモリに予め書込まれた１つのスキャンライン上の各
点ｂＯ’　、ｂ　１’　、　・・−、ｂ　（ｗ−２）’
　。

ｂ（ｗ−１）’のデータを用いて演算を行ない、得られ
たデータを再び元のメ予りもしくはメモリ１３以外のメ
モリに書込む。

メモリに書込まれた上記演算後のデータはパターンデー
タとして表示装置１４に送られ、ここで上記閉曲線の領
域が塗りつぶされたパターンが表示される。

このようなハードウェアを使用してパターンデータを生
成する際の手順は次の通りである。

■　まず、メモリが全て′０”にクリアされる。

■　次に多角形の１つの頂点が開始点に選ばれる。

■　上記多角形の辺上の点が入力装置１１で右回りに順
次発生され、前の点からのずれ（ｄｘｌ。

ｄｏｌｌ）及び次の点へのずれ（ｄ　ｘ、　　ｄ　ｙ）
が順次出力される。プロセッサ１２では、第１図のフロ
ーチャートで示されるようなアルゴリズムに従い、境界
を表わす点が順次発生され、これがメモリに書込まれる
。また、メモリに境界を表わす点が書込まれる際には、
座標（ｘ、ｙ）に対応するメモリの１ビツトのデータｄ
　（ｘ、ｙ）と“１ｍとの排他的オアの結果が書込まれ
る。すなわち、ｄ　（ｘ、ｙ）”ｄ　（ｘ、ｙ）＋“１
”　　　−（２）となる。

■　開始点から次の点への変化ｆｆ１ｄ　Ｘ　Ｏ。

ｄｙＯが記憶され、多角形を一周し、開始点に再び戻っ
てきたときに、最後の変化量をｄｘｌ。

ｄｙｌとし、開始点から次の点に至る変化量をｄｘ、ｄ
ｙとして第１図の処理が行なわれ、開始点に関して境界
を表わす点が発生され、これがメモリに書込まれる。

■　次に１つのスキャンラインがＷビットからなり、そ
のスキャンラインのビットデータをｄＯ。

ｄｌ、・・・ｄ（ｗ−１）とすると、次の演算により新
たなデータｄＯ’　、ｄｌ’　、−ｄ　（ｗ−１）’が
発生され、これがパターンデータとしてメモリ第１図の
フローチャートでは、まず、ステップｓｌ（以下、単に
Ｓという）でｄｘ、ｄｙが与えられる。次に８２でｄｙ
ｌの値が判断され、−１であればＳ３に、０であればＳ
４に、＋１であればＳ５にそれぞれ進む。

Ｓ３ではｄｙの値が判断され、−１であればＳ６に、０
であればＳ７に、＋１であればＳ８にそれぞれ進む。Ｓ
６では座標（ｘ、ｙ）に点が打たれ、その後、Ｓ９で座
標（ｘ、ｙ）が更新され、さらに次のｓｌＯで（ｄ　ｘ
　１．　　ｄ　ｙ　１）が更新され、元の５１に戻る。

上記ｓ７及びＳ８ではそれぞれ右折であるか否かが判断
される。この右折とは、（ｄｘ、ｄｙ）のベクトルが（
ｄ　ｘ　１．　　ｄ　Ｙ　１）のベクトルに対して右に
曲がっていることを意味する。例えば第３図（ａ）に示
すように右方向がＸの子方向、下方向がｙの子方向の座
標系を用いると、次の式で与えられるｔの値が０より大
（１００）の場合には右折、ｔの値が０より小（１００
）の場合には左折、ｔの値が０’（ｔ−０）の場合には
直進もしくは後退を意味する。

ｔ−ｄｘｌ　　・　ｄｙ−ｄｙｌ　　争　ｄｘ　　　　
　　　　−１４）上記Ｓ７及びＳ８それぞれで右折でな
いと判断された場合、その座標には点は打たれず、上記
ｓ９に進む。他方、Ｓ７で右折と判断されたならば上記
ｓ６で座標（ｘ、ｙ）に点が打たれ、その後、Ｓ９に進
む。また、Ｓ８で右折と判断されたならば、次のａｌｌ
で、まず座標（ｘ、ｙ）に点が打たれ、次のＳ１２で座
標（ｘ＋１．ｙ）に点が打たれ、次に上記Ｓ９に進む。

Ｓ４では右折であるか否かが判断され、右折でなければ
前記と同様に点は打たれず、右折であれば次のＳ１３に
進む。このＳ１３ではｄｙＯ値が判断され、−１ならば
前記ｓ６で座標（ｘ、ｙ）に点が打たれ、＋１ならばＳ
１４で座標（ｘ＋１．ｙ）に点が打たれ、次に上記ｓ９
に進む。

Ｓ５ではｄｙの値が判断され、−１ならばＳ１５に、０
ならばｓｌＢにそれぞれ進み、＋１ならば上記ｓ１４に
進んで座標（ｘ＋１．ｙ）に点が打たれる。上記ｓ１５
及びｓｌ［ｉではそれぞれ右折であるか否かが判断され
、それぞれで右折でないと判断されたならば点は打たれ
ず、上記ｓ９に進む。他方、ｓ　１５で右折と判断され
たならばｓｌｌでまず座標（ｘ、ｙ）に点が打たれ、さ
らにＳ１２で座標（ｘ＋１．ｙ）に点が打たれる。また
、ｓｌＧで右折と判断されたならば、Ｓ１４に進んで座
標（ｘ＋１．ｙ）に点が打たれる。

次に上記の手順により、実際に第３図（ａ）で示すよう
な閉曲線を境界とする多角形の塗りつぶしを行なう場合
を説明する。なお、開始点として第３図（ａ）の閉曲線
の１つの頂点ｐｔｔが選ばれるものとする。

まず、この頂点ｐｏに対応した第３図（ｂ）のメモリの
点ｑｔｔにはデータは書込まれず、元の０２のままにさ
れる。

次に、多角形の点ｐ　１’２に対する次の点ｐ１３への
ずれである（ｄｘ、ｄｙ）＝　（０，−１）が与えられ
る。このとき、前の点ｐ１２からのずれは（ｄｘｌ、ｄ
ｙｌ）簡（＋１．−１）である。このとき、ｄｙｌが−
１であり、ｄｙ−−１であるため、Ｓ６で（ｘ、ｙ）の
座標すなわち、この点ｐ１２に対応した第３図（ｂ）の
メモリの点Ｑ１２に対し”１“との排他的オアの結果で
ある“１”が書込まれる。

次に、点ｐ１３に対し、次の点ｐ１４へのずれである（
ｄｘ、ｄｙ）＝　（＋１．０）が与えられる。

この場合、予め更新されたｄＹｌ−−１、ｄｙ−０であ
り、かつ右折であるので、Ｓ６で（ｘ、ｙ）の座標すな
わち、この点ｐ１３に対応した第３図（ｂ）のメモリの
点ｑ１３に“１”が書込まれる。

次に、点ｐ１４に対し、次の点ｐ１５へのずれである（
ｄｘ、ｄｙ）−（＋１．＋１）が与えられる。

この場合、ｄｙｌ−０でありかつ右折であり、ａｙ−＋
ｌであるため、ｓ１４で（ｘ＋１．ｙ）の座標すなイつ
ち、この点ｐ１４に対し１点だけ右方向にずれた第３図
（ｂ）のメモリの点ｑ１４に“１”が書込まれる。

次に、点ｐ１５に対し、次の点ｐ１Ｂへのずれである（
ｄｘ、ｄｙ）＝　（＋１．−１）が与えられる。

この場合、ｄｙｌ−＋１、ｄｙ−−１であり、かつ右折
でないため、この点ｐ１５に対して点は打たれない。

次に、点ｐ１６に対し、次の点ｐ１７へのずれである（
ｄｘ、ｄｙ）−（＋１．＋１）が与えられる。

この場合、ｄＹｌ−−１、ｄｙ−＋ｌであり、かつ右折
であるため、まず、ｓｌｌで（ｘ、ｙ）の座標すなわち
点ｐｌＧに対応した第３図（ｂ）のメモリの点ｑ　１８
Ａに対して“１“が書込まれ、次のｓ１２で（ｘ＋１．
ｙ）の座標すなわち点ｐｌＢに対し右方向に１点だけず
れた第３図（ｂ）のメモリの点ｑｌＧＢに“１“が書込
まれる。

次に、点ｐ１７に対し、次の点ｐ１８へのずれである（
ｄｘ、ｄｙ）＝　（０，＋１）が与えられる。

この場合、ｄＹｌ−＋１、ｄｙ−＋ｌであるため、ｓ１
４で（ｘ＋１．ｙ）の座標すなわち、点ｐ１７に対し１
点だけ右方向にずれた第３図（ｂ）のメモリの点Ｑ１７
に“１”が書込まれる。また、点ｐ１８、ｐ１９に対し
ても上記の場合と同様に、この両点ｐ１ｇ、ｐ１９に対
しそれぞれ１点だけ右方向にずれた第３図（ｂ）のメモ
リの点ｑ１８、ｑ１９にそれぞれ“１″が書込まれる。

次に、点ｐ２０に対し、次の点ｐ２１へのずれである（
ｄｘ、ｄｙ）＝　（−１，０）が与えられる。

この場合、ｄｙｌ−＋１、ｄｙ−ｏであり、かつ右折で
あるため、ｓ１４で（ｘ＋１．ｙ）の座標すなわち、点
ｐ２０に対し１点だけ右方向にずれた第３図（ｂ）のメ
モリの点ｑ２０に“１“が書込まれる。

次に、点ｐ２１に対し、次の点ｐ２２へのずれである（
ｄｘ、ｄｙ）＝　（−１，０）が与えられる。

この場合、ｄｙｌ−＋１、ｄ３／−０であり、かつ右折
でなく水平であるため、この点ｐ２１に対して点は打た
れない。

次に、点ｐ２２に対し、次の点ｐ２３へのずれである（
ｄｘ、ｄｙ）＝　（−１，−１）が与えられる。

この場合、ｄｙｌ−−１、ｄｙ−−１であるため、ｓ６
で（ｘ、ｙ）の座標すなわち、この点ｐ２２に対応した
第３図（ｂ）のメモリの点ｑ２２に“１”が書込まれる
。

次に、点ｐ２３に対し、次の点（開始点ｐ１１）へのず
れである（ｄｘ、ｄｙ）＝　（−１，−１）が与えられ
る。この場合にも点ｐ２２の場合と同様に点ｐ２３に対
応した第３図（ｂ）のメモリの点ｑ２３に“１”が書込
まれる。

これにより開始点ｐＨに戻ったことになり、最後の変化
量（ｄｘｌ、ｄｙｌ）は（−１，−１）であり、始めの
（ｄ　ｘ、　　ｄ　ｙ）は（＋１．−１）であるため、
ｄＹｌ−−１、ｄｙ−−１になり、ｓ６で（ｘ、ｙ）の
座標すなわち、この開始点ｐｔｔに対応した第３図（ｂ
）のメモリの点ｑｔｔに始めて“１″が書込まれる。

このようにして、スキャン方向に沿った塗るべき線分の
全てにつき、各線分の２つの端点のうち一方にはそれ自
体の点、他方はスキャン方向に１点だけずれた点がメモ
リに書込まれる。この後は、第３図（ｂ）のようなデー
タを用いて、前記■の手順における演算が行なわれ、そ
の演算結果がメモリに書込まれる。

この演算は、いま１つのスキャンラインが、第４図（ａ
）に示すようにｂｏ、ｂｌ。

・・・ｂ（ｗ−１）のＷビットの点からなる場合、演算
後のｂＯ′には第４図（ａ）のｂＯである０”がそのま
ま書き込まれる。次に、演算後のｂ１′には第４図（ａ
）のｂＯとｂｌとの排他的オアの結果が書き込まれる。

この場合、ｂＯ−ｂｌ−“０”なので、演算後のｂｌ’
には“０”が書込まれる。さらに、演算後のｂ２には第
４図（ａ）のｂＯ，ｂｌ、ｂ２の排他的オアの結果が書
き込まれる。この場合、ｂＯ−ｂｌ−“０”　、ｂ２−
“１１なので、演算後のｂ２’には１′が書込まれる。

以下、同様の演算が行なわれることによって第４図（ｂ
）に示すようなデータが得られる。

そして、このような演算が前記第３図（ｂ）の全てのス
キャンラインについて行なわれる結果、第３図（ａ）に
対する入力図形に対し、第３図（ｃ）でパターンデータ
が得られる。このパターンデータを用いて表示を行なえ
ば、前記第３図（ａ）の閉曲線を境界とする多角形の領
域が塗りつぶされた図形が正確に表示されることになる
。

このように上記実施例では、閉曲線で囲まれた領域が塗
りつぶされたパターンデータを生成することができる。

そして、この実施例によれば従来のようなソートの処理
が不要となり、高速な処理が実現できる。

次に上記実施例の変形例について説明する、上記の説明
では閉曲線で囲まれた領域が塗りつぶされたパターンデ
ータを生成する場合について説明したが、これは第３図
（ｄ）に示すように領域の外側が塗りつぶされたパター
ンデータを生成させることもできる。この場合には前記
（３）式の演算の代わりに、下記の演算を前記第３図（
ｂ）のデータに対し、各スキャンライン毎に実行すれば
よい。

上記の説明では、閉曲線が右回りに発生される場合であ
ったが、右回りに発生される場合の１点毎の処理に第１
図の代わりに第５図のフローチャートに示されるアルゴ
リズムを用いればよい。

また、上記の説明では閉曲線で囲まれた領域の塗りつぶ
しを行なう際に、境界を含んで行なう場合について説明
したが、これは境界を含まずに塗りつぶしを行なうこと
もできる。この場合、右回りの境界に対しては、１点毎
の処理に第５図のフローチャートで示すようなアルゴリ
ズムを用い、左回りの境界に対しては、１点毎の処理に
第１図のフローチャートで示すようなアルゴリズムを用
いればよい。この場合、第３図（ａ）のような境界デー
タに対して、まず第３図（ｅ）で示されるようなデータ
が得られ、この第３図（ｅ）のデータに対し前記（３）
式の演算を各スキャンライン毎に実行すれば第３図（ｆ
）で示されるようなパターンデータが得られる。

また、上記実施例によれば、第６図（ａ）で示されるよ
うな境界データに対しても正しい塗りつぶしを行なうこ
とができる。すなわち、この場合、１つのスキャンライ
ン２１に着目すると、このスキャンライン２１は境界と
４つの交点２２〜２５を有している。ここで、２つの交
点２３と２４とは、スキャン方向で隣接しており、塗り
つぶしを行なう際には交点２２と２５を結ぶ線分を塗れ
ばよい。この場合、前記の■の手順により交点２２〜２
５に対し、メモリには第６図（ｂ）に示すように点３２
．３３．３４が書込まれる。このとき、点３３に対して
は２回書込みが行なわれるためにこの点３３は“０”に
なり、スキャンライン２１上には点３２と３４の２点に
“１”が書込まれる。この結果、最終的には第６図（ｃ
）に示すように、境界を含む領域が塗りつぶされた正確
なパターンデータが得られる。

第７図はこの発明の第２の実施例を実現するために使用
されるハードウェアの構成を示すブロック図である。こ
の実施例では前記のようなパターンデータの生成を専用
のハードウェアを用いて実現するようにしたものである
。このハードウェアは、ＤＤＡ部５１、メモリ部５２、
制御部５３及びこれら相互に接続するバス５４とから構
成されている。

ＤＤＡ部５１はＤＤＡの機能を用いて、ｄｘ。

ｄｙ倍信号発生する。ｄｘ、ｄｙ倍信号ＤＸＯ。

ＤＸＯ，ＤＹＯ，ＤＹＯのそれぞれ２ビツトからなり、
ｄｘ倍信号下記の表に示すようにコード化されている。

なお、ｄｙ倍信号ついても同様にコード化されている。

メモリ部５２は第８図のブロック図に示すように構成さ
れている。第８図において、６Ｉはロウ、カラム方向が
それぞれビットマツプのＸ、ｙ方向に対応しているｎＸ
ｍビットのメモリセルアレイ、６２はＸ座標値を保持し
、値のプリセットが可能なアップダウンカウンタからな
るＸカウンタ、６３はＸ座標値を保持し、値のプリセッ
トが可能なアップダウンカウンタからなるＸカウンタ、
６４は上記Ｘカウンタ６２の内容をデコードしてカラム
セレクト信号を発生するカラムデコーダ、６５は上記Ｘ
カウンタ６３の内容をデコードしてロウセレクト信号を
発生するロウデコーダ、６６は１ロウ分（Ｗビ・ソト）
のデータを保持し、後述する演算機能を有するロウデー
タバッファ、６７は上記ロウデータバッフアルＧＧで保
持されているＷビットのデータを１個のにビット（ＪＸ
ｋ−ｗ）に分割し、このうちの１個のにビットのデータ
をロウアドレス信号の一部を用いて選択しバス５４に接
続するセレクタ、６８は上記ｄｘ、ｄｙ信号が入力され
、上記ロウデータバッフ７６Ｇの機能を制御するための
３ビツトのコードを発生するコード生成器である。

上記Ｘカウンタ８２はモード信号Ｍ１に応じて、バス５
４」二の値をプリセットするか、ｄｘ倍信号基づいてそ
の内容をインクリメントするかまたはデクリメントする
。Ｘカウンタ６３も同様に、上記モード信号Ｍ１に応じ
て、°バス５４上の値をプリセットするか、ｄｙ倍信号
基づいてその内容をインクリメントするかまたはデクリ
メントする。

上記ロウデータバッファ６６は演算機能を有しており、
モード信号Ｍ２に応じて次の４つの動作を選択的に行な
う。

■　ロウセレクト信号で選択された１つのロウに全て“
０”を書込む。

■　コード生成器６８からの３ビツトのコードに応じて
次の動作を行なう （１）　　コードが（ＯＸＸ）及び（１００）の場合（
Ｘは０または１）には何もしない。

（２）　　コードが（１１０）の場合には、バッファの
うちカラムセレクト信号で選択されたビットだけを反転
し、ロウセレクト信号で選択されたロウに書込む。

（３）　　コードが（１０１）の場合には、バッファの
うちカラムセレクト信号で選択されたビットの、カラム
アドレスが増加する方向に隣接するビットだけを反転し
、ロウセレクト信号で選択されたロウに書込む。

（４）　　コードが（１１１）の場合には、バッファの
うちカラムセレクト信号で選択されたビットと、それに
カラムアドレスが増加する方向に隣接するビットとを反
転し、ロウセレクト信号で選択されたロウに書込む。

■　バッファのデータを、前記（３）式で与えられる演
算を行なう図示しないビットマスク生成回路に入力し、
生成されたビットマスク（例えば、前記第３図（ｃ）に
示すようなデータ）をロウセレクト信号で選択されたロ
ウに書込む。

■　ロウセレクト信号で選択された１ロウのデータをバ
ッファに取込み、セレクタ６７を通してバス５４に出力
する。

上記コード生成器６８は、内部に１つ前のｄｘ。

ｄｙである前記ｄｘ１．ｄｙｌを記憶するレジスタを有
しており、ｄｘ、ｄｙの入力に対し、第９図のフローチ
ャートで示されるようなアルゴリズムに従って上記３ビ
ツトのコードを生成する。

第８図の詳細図で示されるメモリ部５２には次の５つの
機能がある。

■　メモリセルを全て“０°にクリアする。　　　−■
　バス５４を介して外部からｘ、ｙ座標が入力され、Ｘ
カウンタ６２及びＸカウンタ６３にプリセットデータと
してセットされる。

■　バス５４を介して外部からｄｘ、ｄｙ倍信号入力さ
れ、Ｘカウンタ６２及びｙカウンタＢ３の内容がインク
リメントもしくはデクリメントされ、ｄｘｌ、ｄｙｌと
合せて第９図のフローチャートのアルゴリズムに従って
生成されるコードに応じて次の処理が行なわれる（これ
をＤＤＡモードと称する）。

（１）　　コードが（１１０）の場合には、座標（ｘ、
ｙ）のメモリセルの内容が反転される。

（２）コードが（１０１）の場合には、座標（ｘ＋１．
ｙ）のメモリセルの内容が反転される。

（３）　　コードが（１１０）の場合には、座標（ｘ、
ｙ）と（ｘ＋１．ｙ）のメモリセルの内容が反転される
。

■　全てのロウについてロウデータがビットマスク発生
器に順次人力され、得られた出力が書込まれる（これを
塗りつぶしモードと称する）。

■　メモリセルアレイ６１の内容かにビットずつ外部に
読み出される（これを読み出しモードと称する。

前記制御部５３は、ＤＤＡ部５１にバス５４を経由して
各種パラメータをセットし、ＤＤＡ部５１に起動をかけ
、かつメモリ部５２に前記モード信号Ｍｌ。

Ｍ２を出力して制御を行なう。

このようなハードウェアを用いた塗りつぶし処理は次の
ような手順で行なわれる。

■　閉曲線を部分曲線または部分直線に分解する。

■　ＤＤＡ部５１にパラメータをセットし、起動をかけ
る。

■　ＤＤＡ部５１でｄｘ、ｄｙを発生する。

■　上記ｄｘ、ｄｙにより、境界に関するデータをメモ
リ部５２に書込む。

■　上記■〜■の手順を部分曲線の数に対応した回数だ
け繰返す。なお、この処理はパイプライン動作で実現す
ることにより高速処理が可能である。

■　メモリ部５２を塗りつぶしモードで動作させ、メモ
リ部５２にパターンデータを書込む。

■　読み出しモードにより、書込まれたパターンデータ
をメモリ部５２から外部に読み出す。

このように、この実施例では専用の７Ｘ−ドウエアを用
いて塗りつぶし処理が行なわれたパターンデータを得る
ことができる。

ところで、この実施例において、塗りつぶし処理に要す
る時間Ｔｐは、ＤＤＡ部５１の動作の周期をＴＯ１境界
上の点の数をＮ１メモリ部５２における塗りつぶしモー
ドでの１スキヤンラインの塗りつぶしに要する時間をＴ
１とすると、次の式で与えられる。

Ｔｐ−ＴＯ＋Ｎ−７１・・・（６） この実施例かられかるように、この発明の方式は専用の
ハードウェア化が容品であり、高速の塗りつぶしが実現
できる。

［発明の効果］ 以上説明したようにこの発明によれば、従来のものに比
べてソートの処理が不要であり、ソフトウェア的に処理
を行なった場合にはソフトウェアの処理が軽減し、処理
速度が高速になる。また、ソートの処理が不要なため、
専用のハードウェア化が容易であり、かつ高速処理が可
能である。

さらに、この発明では、塗るべき線分の端点の一方を実
際の座標点からずらすことによって、線分の塗りつぶし
の処理が簡単になると共に、従来のように頂点に対する
特別なソフトウェア的な処理が不要なため、高速な塗り
つぶしが可能である。

【図面の簡単な説明】

第１図はこの発明の第１の実施例を説明するためのフロ
ーチャート、第２図は上記実施例を実現するために使用
されるハードウェアの構成を示すブロック図、第３図な
いし第６図はそれぞれ上記実施例を説明するための図で
あり、第３図は曲線及びメモリにおける記憶状態を示す
図、第４図はデータを示す図、第５図はフローチャート
、第６図は曲線及びメモリにおける記憶状態を示す図、
第７図はこの発明の第２の実施例を実現するために使用
されるハードウェアの構成を示すブロック図、第８図は
その一部を詳細に示すブロック図、第９図は上記第２の
実施例を説明するためのフローチャート、第１０図及び
第１１図はそれぞれ従来の塗りつぶし処理を説明するた
めの図である。 １１・・・入力装置、１２・・・プロセッサ、１３・・
・メモリ、１４・・・表示装置、１５・・・バス、５１
・・・ＤＤＡ部、５２・・・メモリ部、５３・・・制御
部、５４・・・バス。 出願人代理人　弁理士　鈴江武彦 第１図 第　６　図 苗　９　ロ

Claims (2)

【特許請求の範囲】
1. （１）ビットマップ上において閉曲線で囲まれた領域の
   塗りつぶし処理を行なう際に、領域の境界線であり、右
   回りもしくは左回りの方向が定義された閉曲線のデータ
   として、開始点のｘ、ｙ座標と、それぞれ＋１、−１、
   ０の値をとる１点毎の座標の変化量ｄｘ、ｄｙが与えら
   れるパターンデータ生成方式において、 上記データｄｘ、ｄｙに基づき、ビットマップメモリ上
   で１つの方向をスキャン方向としたとき、スキャン方向
   に沿った塗るべき線分の全てにつき、各線分の２つの端
   点のうち一方はそれ自体の点、他方はスキャン方向に１
   点だけずれた点をビットマップメモリに書込む手段と、 １つのスキャンライン上にｂ０、ｂ１、…、ｂ（ｗ−２
   ）、ｂ（ｗ−１）からなるｗ個（ｗは正の整数）の点が
   存在する際に、点ｂ（ｊ）（ｊは０以上でｗ未満）に対
   応した位置に点ｂ０、ｂ１、…、ｂ（ｊ−１）のデータ
   の排他的論理和データを書込み、全てのスキャンライン
   について同様のデータ書込みを行なうことにより、上記
   閉曲線で囲まれた領域の塗りつぶしが行なわれたパター
   ンデータを生成する手段と を具備したことを特徴とするパターンデータ生成方式。
2. （２）前記閉曲線で囲まれた領域の塗りつぶしの際には
   専用のメモリが使用され、 このメモリはロウ、カラム方向がビットマップのｘ、ｙ
   方向に対応し、かつこのメモリは１ロウ毎に前記点ｂ（
   ｊ）に対して書込みを行なうべき点ｂ０、ｂ１、…、ｂ
   （ｊ−１）のデータの排他的論理和の積の演算を行なう
   ように構成されている請求項１記載のパターンデータ生
   成方式。