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

Description

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

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

次に、従来の多角形のスキャン変換による塗りつぶし処
理を、第10図並びに第11図（ａ）ないし（ｃ）を用いて
説明する。なお、第10図において、71はスキャン変換を
行なう矩形領域であり、72〜77はそれぞれ境界の多角形
の頂点、78〜83はそれぞれ多角形の辺、91は１つのスキ
ャンラインである。

まず、１つのスキャンライン91について、多角形の
辺との交点P0,P1,P2,P3を求め、それをスキャン方向の
座標値の順番にソートする。

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

次に、ソートされた交点を２つずつ対にして、それ
を両端とする線分（第10図中の線分84,85）を塗る。

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

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

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

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

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

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

（作用） この発明のパターンデータ生成方式では、塗りつぶしを
行なうべき領域に対し、境界のデータは、右回り、左回
りのいずれかの方向が定義されている。そして、このデ
ータは閉曲線の開始点の座標と、１点毎の変化量dx,dy
として与えられる。ここで、dx,dyそれぞれ＋1,−1,0の
いずれか１つの値をとる。

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

このようにして境界を表わす点をメモリに書込んだ後
は、スキャンラインに沿って各点にデータを書込むこと
により塗りつぶされたパターンデータを得る。このと
き、１つのスキャンラインが例えばｗビットからなって
いる時、スキャンライン上の各点におけるビットデータ
をd0,d1,…,d（ｗ−１）とすると、次のような排他的論
理和演算を順次行ない、その結果をメモリに書込むこと
によって塗りつぶされたパターンデータd0′,d1′，…,
d（ｗ−１）′を得るようにしている。

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

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

上記入力装置11は、塗りつぶしを行なう領域の境界線
を、右回りもしくは左回りの方向が定義された閉曲線の
データとして、開始点のx,y座標と、それぞれ＋1,−1,0
の値をとる１点毎の座標の変化量dx,dyを順次出力す
る。

プロセッサ12は上記データdx,dyに基づき、スキャン方
向に沿った塗るべき線分の全てにつき、各線分の２つの
端点のうち一方はそれ自体の点、他方はスキャン方向に
１点だけずれた点を、上記メモリ13中に構成された２次
元のビットマップの矩形領域（以下、単にメモリと称す
る）に書込む。なお、上記入力装置11の代わりにこのプ
ロセッサ12が座標の変化量dx,dyを出力するようにして
いもよい。さらにプロセッサ12は、メモリに予め書込ま
れた１つのスキャンライン上の各点b0′,b1′，…,b
（ｗ−２）′,b（ｗ−１）′のデータを用いて演算を行
ない、得られたデータを再び元のメモリもしくはメモリ
13以外のメモリに書込む。

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

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

まず、メモリが全て“0"にクリアされる。

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

上記多角形の辺上の点が入力装置11で右回りに順次
発生され、前の点からのずれ（dx1,dy1）及び次の点へ
のずれ（dx,dy）が順次出力される。プロセッサ12で
は、第１図のフローチャートで示されるようなアルゴリ
ズムに従い、境界を表わす点が順次発生され、これがメ
モリに書込まれる。また、メモリに境界を表わす点が書
込まれる際には、座標（x,y）に対応するメモリの１ビ
ットのデータｄ（x,y）と“1"との排他的オアの結果が
書込まれる。すなわち、 ｄ（x,y）←ｄ（x,y）＋“1" ……（２） となる。

開始点から次の点への変化量dx0,dy0が記憶され、
多角形を一周し、開始点に再び戻ってきたときに、最後
の変化量をdx1,dy1とし、開始点から次の点に至る変化
量をdx,dyとして第１図の処理が行なわれ、開始点に関
して境界を表わす点が発生され、これがメモリに書込ま
れる。

次に１つのスキャンラインがｗビットからなり、そ
のスキャンラインのビットデータをd0,d1,…ｄ（ｗ−
１）とすると、次の演算により新たなデータd0′,d
1′，…ｄ（ｗ−１）′が発生され、これがパターンデ
ータとしてメモリに書込まれる。

第１図のフローチャートでは、まず、ステップs1（以
下、単にｓという）でdx,dyが与えられる。次にs2でdy1
の値が判断され、−１であればs3に、０であればs4に、
＋１であればs5にそれぞれ進む。

s3ではdyの値が判断され、−１であればs6に、０であれ
ばs7に、＋１であればs8にそれぞれ進む。s6では座標
（x,y）に点が打たれ、その後、s9で座標（x,y）が更新
され、さらに次のs10で（dx1,dy1）が更新され、元のs1
に戻る。

上記s7及びs8ではそれぞれ右折であるか否かが判断され
る。この右折とは、（dx,dy）のベクトルが（dx1,dy1）
のベクトルに対して右に曲がっていることを意味する。
例えば第３図（ａ）に示すように右方向がｘの＋方向、
下方向がｙの＋方向の座標系を用いると、次の式で与え
られるｔの値が０より大（ｔ＞０）の場合には右折、ｔ
の値が０より小（ｔ＜０）の場合には左折、ｔの値が０
（ｔ＝０）の場合には直進もしくは後退を意味する。

ｔ＝dx1・dy−dy1・dx …（４） 上記s7及びs8それぞれで右折でないと判断された場合、
その座標には点は打たれず、上記s9に進む。他方、s7で
右折と判断されたならば上記s6で座標（x,y）に点が打
たれ、その後、s9に進む。また、s8で右折と判断された
ならば、次のs11で、まず座標（x,y）に点が打たれ、次
のs12で座標（ｘ＋1,y）に点が打たれ、次に上記s9に進
む。

s4では右折であるか否かが判断され、右折でなければ前
記と同様に点は打たれず、右折であれば次のs13に進
む。このs13ではdyの値が判断され、−１ならば前記s6
で座標（x,y）に点が打たれ、＋１ならばs14で座標（ｘ
＋1,y）に点が打たれ、次に上記s9に進む。

s5ではdyの値が判断され、−１ならばs15に、０ならばs
16にそれぞれ進み、＋１ならば上記s14に進んで座標
（ｘ＋1,y）に点が打たれる。上記s15及びs16ではそれ
ぞれ右折であるか否かが判断され、それぞれで右折でな
いと判断されたならば点は打たれず、上記s9に進む。他
方、s15で右折と判断されたならばs11でまず座標（x,
y）に点が打たれ、さらにs12で座標（ｘ＋1,y）に点が
打たれる。また、s16で右折と判断されたならば、s14に
進んで座標（ｘ＋1,y）に点が打たれる。

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

まず、この頂点p11に対応した第３図（ｂ）のメモリの
点q11にはデータは書込まれず、元の“0"のままにされ
る。

次に、多角形の点p12に対する次の点p13へのずれである
（dx,dy）＝（0,−１）が与えられる。このとき、前の
点p12からのずれは（dx1,dy1）＝（＋1,−１）である。
このとき、dy1が−１であり、dy＝−１であるため、s6
で（x,y）の座標すなわち、この点p12に対応した第３図
（ｂ）のメモリの点q12に対し“1"との排他的オアの結
果である“1"が書込まれる。

次に、点p13に対し、次の点p14へのずれである（dx,d
y）＝（＋1,0）が与えられる。この場合、予め更新され
たdy1＝−１、dy＝０であり、かつ右折であるので、s6
で（x,y）の座標すなわち、この点p13に対応した第３図
（ｂ）のメモリの点q13に“1"が書込まれる。

次に、点p14に対し、次の点p15へのずれである（dx,d
y）＝（＋1,＋１）が与えられる。この場合、dy1＝０で
ありかつ右折であり、dy＝＋１であるため、s14で（ｘ
＋1,y）の座標すなわち、この点p14に対し１点だけ右方
向にずれた第３図（ｂ）のメモリの点q14に“1"が書込
まれる。

次に、点p15に対し、次の点p16へのずれである（dx,d
y）＝（＋1,−１）が与えられる。この場合、dy1＝＋
１、dy＝−１であり、かつ右折でないため、この点p15
に対して点は打たれない。

次に、点p16に対し、次の点p17へのずれである（dx,d
y）＝（＋1,＋１）が与えられる。この場合、dy1＝−
１、dy＝＋１であり、かつ右折であるため、まず、s11
で（x,y）の座標すなわち点p16に対応した第３図（ｂ）
のメモリの点q16Aに対して“1"が書込まれ、次のs12で
（ｘ＋1,y）の座標すなわち点p16に対し右方向に１点だ
けずれた第３図（ｂ）のメモリの点q16Bに“1"が書込ま
れる。

次に、点p17に対し、次の点p18へのずれである（dx,d
y）＝（0,＋１）が与えられる。この場合、dy1＝＋１、
dy＝＋１であるため、s14で（ｘ＋1,y）の座標すなわ
ち、点p17に対し１点だけ右方向にずれた第３図（ｂ）
のメモリの点q17に“1"が書込まれる。また、点p18、p1
9に対しても上記の場合と同様に、この両点p18、p19に
対しそれぞれ１点だけ右方向にずれた第３図（ｂ）のメ
モリの点q18、q19にそれぞれ“1"が書込まれる。

次に、点p20に対し、次の点p21へのずれである（dx,d
y）＝（−1,0）が与えられる。この場合、dy1＝＋１、d
y＝０であり、かつ右折であるため、s14で（ｘ＋1,y）
の座標すなわち、点p20に対し１点だけ右方向にずれた
第３図（ｂ）のメモリの点q20に“1"が書込まれる。

次に、点p21に対し、次の点p22へのずれである（dx,d
y）＝（−1,0）が与えられる。この場合、dy1＝＋１、d
y＝０であり、かつ右折でなく水平であるため、この点p
21に対して点は打たれない。

次に、点p22に対し、次の点p23へのずれである（dx,d
y）＝（−1,−１）が与えられる。この場合、dy1＝−
１、dy＝−１であるため、s6で（x,y）の座標すなわ
ち、この点p22に対応した第３図（ｂ）のメモリの点q22
に“1"が書込まれる。

次に、点p23に対し、次の点（開始点p11）へのずれであ
る。（dx,dy）＝（−1,−１）が与えられる。この場合
にも点p22の場合と同様に点p23に対応した第３図（ｂ）
のメモリの点q23に“1"が書込まれる。

これにより開始点p11に戻ったことになり、最後の変化
量（dx1,dy1）は（−1,−１）であり、始めの（dx,dy）
は（＋1,−１）であるため、dy1＝−１、dy＝−１にな
り、s6で（x,y）の座標すなわち、この開始点p11に対応
した第３図（ｂ）のメモリの点q11に始めて“1"が書込
まれる。

上記第１図のフローチャートで示されるアルゴリズムを
まとめると以下のようなる。すなわち、ある境界上の点
につき、境界に沿って前後の点との座標変化量を、それ
ぞれdx1,dy1とdx,dyとし、かつ、ｔ＝dx1・dy−dy1・dy
としたとき、 右回りの曲線であれば、 ａ） dy1,dyともに−１のとき、境界上の点にフラグを
発生し、 ｂ） dy1,dyともに＋１のとき、境界上の点の１つ右に
あたる点にフラグを発生し、 ｃ） dy1,dyの片方が０、もう一方が＋１で、ｔ＞０の
とき、境界上の１つ右にあたる点にフラグを発生し、 ｄ） dy1,dyの片方が０、もう一方が−１で、ｔ＞０の
とき、境界上の点にフラグを発生し、 ｅ） dy・dy1が−１で、ｔ＞０のとき、境界上の点及
びその１つ右の点にフラグを発生し、 左回りの曲線であれば、 ａ） dy1,dyともに＋１のとき、境界上の点にフラグを
発生し、 ｂ） dy1,dyともに−１のとき、境界上の点の１つ右に
あたる点にフラグを発生し、 ｃ） dy1,dyの片方が０、もう一方が−１で、ｔ＜０の
とき、境界上の点の１つ右にあたる点にフラグを発生
し、 ｄ） dy1,dyの片方が０、もう一方が＋１で、ｔ＜０の
とき、境界上の点にフラグを発生し、 ｅ） dy・dy1が−１で、ｔ＜０のとき、境界上の点及
びその１つ右の点にフラグを発生することによって、ビ
ットマップメモリ上でｘ方向をスキャン方向としたと
き、スキャン方向に沿った塗るべき線分の全てにつき、
各線分の２つの端点のうち、一方はそれ自体の点、他方
はスキャン方向に１点だけずれた点をビットマップメモ
リに書込む。

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

この演算は、いま１つのスキャンラインが、第４図
（ａ）に示すようにb0,b1,…ｂ（ｗ−１）のｗビットの
点からなる場合、演算後のb0′には第４図（ａ）のb0で
ある“0"がそのまま書き込まれる。次に、演算後のb1′
には第４図（ａ）のb0とb1との排他的オアの結果が書き
込まれる。この場合、b0＝b1＝“0"なので、演算後のb
1′には“0"が書込まれる。さらに、演算後のb2には第
４図（ａ）のb0,b1、b2の排他的オアの結果が書き込ま
れる。この場合、b0＝b1＝“0"、b2＝“1"なので、演算
後のb2′には“1"が書込まれる。以下、同様の演算が行
なわれることによって第４図（ｂ）に示すようなデータ
が得られる。そして、このような演算が前記第３図
（ｂ）の全てのスキャンラインについて行なわれる結
果、第３図（ａ）に対する入力図形に対し、第３図
（ｃ）でパターンデータが得られる。このパターンデー
タを用いて表示を行なえば、前記第３図（ａ）の閉曲線
を境界とする多角形の領域が塗りつぶされた図形が正確
に表示されることになる。

このように上記実施例では、閉曲線で囲まれた領域が塗
りつぶされたパターンデータを生成することができる。
そして、この実施例によれば従来のようなソートの処理
が不要となり、高速な処理が実現できる。

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

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

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

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

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

DDA部51はDDAの機能を用いて、dx,dy信号を発生する。d
x,dy信号はDX1,DX0、DY1,DY0のそれぞれ２ビットからな
り、dx信号は下記の表に示すようにコード化されてい
る。なお、dy信号についても同様にコード化されてい
る。

メモリ部52は第８図のブロック図に示すように構成され
ている。第８図において、61はロウ，カラム方向がそれ
ぞれビットマップのx,y方向に対応しているｎ×ｍビッ
トのメモリセルアレイ、62はｘ座標値を保持し、値のプ
リセットが可能なアップダウンカウンタからなるｘカウ
ンタ、63はｙ座標値を保持し、値のプリセットが可能な
アップダウンカウンタからなるｙカウンタ、64は上記ｘ
カウンタ62の内容をデコードしてカラムセレクト信号を
発生するカラムデコーダ、65は上記ｙカウンタ63の内容
をデコードしてロウセレクト信号を発生するロウデコー
ダ、66は１ロウ分（ｗビット）のデータを保持し、後述
する演算機能を有するロウデータバッファ、67は上記ロ
ウデータバッファル66で保持されているｗビットのデー
タをｌ個のｋビット（ｌ×ｋ＝ｗ）に分割し、このうち
の１個のｋビットのデータをロウアドレス信号の一部を
用いて選択しバス54に接続するセレクタ、68は上記dx,d
y信号が入力され、上記ロウデータバッファ66の機能を
制御するための３ビットのコードを発生するコード生成
器である。

上記ｘカウンタ62はモード信号M1に応じて、バス54上の
値をプリセットするか、dx信号に基づいてその内容をイ
ンクリメントするかまたはデクリメントする。ｙカウン
タ63も同様に、上記モード信号M1に応じて、バス54上の
値をプリセットするか、dy信号に基づいてその内容をイ
ンクリメントするかまたはデクリメントする。

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

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

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

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

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

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

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

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

上記コード生成器68は、内部に１つ前のdx,dyである前
記dx1,dy1を記憶するレジスタを有しており、dx,dyの入
力に対し、第９図のフローチャートで示されるようなア
ルゴリズムに従って上記３ビットのコードを生成する。

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

メモリセルを全て“0"にクリアする。

バス54を介して外部からx,y座標が入力され、ｘカ
ウンタ62及びｙカウンタ63にプリセットデータとしてセ
ットされる。

バス54を介して外部からdx,dy信号が入力され、ｘ
カウンタ62及びｙカウンタ63の内容がインクリメントも
しくはデクリメントされ、dx1,dy1と合せて第９図のフ
ローチャートのアルゴリズムに従って生成されるコード
に応じて次の処理が行なわれる（これをDDAモードと称
する）。

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

（２） コードが（101）の場合には、座標（ｘ＋1,y）
のメモリセルの内容が反転される。

（３） コードが（111）の場合には、座標（x,y）と
（ｘ＋1,y）のメモリセルの内容が反転される。

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

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

前記制御部53は、DDA部51にバス54を経由して各種パラ
メータをセットし、DDA部51に起動をかけ、かつメモリ
部52に前記モード信号M1,M2を出力して制御を行なう。

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

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

DDA部51にパラメータをセットし、起動をかける。

DDA部51でdx,dyを発生する。

上記dx,dyにより、境界に関するデータをメモリ部5
2に書込む。

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

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

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

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

ところで、この実施例において、塗りつぶし処理に要す
る時間Tpは、DDA部51の動作の周期をT0、境界上の点の
数をＮ、メモリ部52における塗りつぶしモードでの１ス
キャンラインの塗りつぶしに要する時間をT1とすると、
次の式で与えられる。

Tp＝T0＋Ｎ・T1 …（６） この実施例からわかるように、この発明の方式は専用の
ハードウエア化が容易であり、高速の塗りつぶしが実現
できる。

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

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

【図面の簡単な説明】

第１図はこの発明の第１の実施例を説明するためのフロ
ーチャート、第２図は上記実施例を実現するために使用
されるハードウエアの構成を示すブロック図、第３図な
いし第６図はそれぞれ上記実施例を説明するための図で
あり、第３図は曲線及びメモリにおける記憶状態を示す
図、第４図はデータを示す図、第５図はフローチャー
ト、第６図は曲線及びメモリにおける記憶状態を示す
図、第７図はこの発明の第２の実施例を実現するために
使用されるハードウエアの構成を示すブロック図、第８
図はその一部を詳細に示すブロック図、第９図は上記第
２の実施例を説明するためのフローチャート、第10図及
び第11図はそれぞれ従来の塗りつぶし処理を説明するた
めの図である。 11……入力装置、12……プロセッサ、13……メモリ、14
……表示装置、15……バス、51……DDA部、52……メモ
リ部、53……制御部、54……バス。

Claims (2)

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