JPH0793570A - 閉図形塗りつぶし方法 - Google Patents

Abstract

(57)【要約】 【目的】 閉図形を定義するベクター信号を処理して当
該閉図形を塗りつぶす処理において、簡単で合理的な方
法を提供する。 【構成】 閉図形を定義するベクターデータを導入し、
それが展開されるべきフレームメモリの記憶セルの位置
に関連した一次処理データを作成し、一次処理データ群
の同一走査ライン上のオンデータ対を認識し、これらオ
ンデータ対間のデータをすべてオンとし、フレームメモ
リの対応する記憶セルに格納されたデータとそれぞれ排
他的論理和をとり、その結果をフレームメモリに格納す
るよう構成した。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】この発明は、表示器またはプリン
ター等の画像表示装置において、ベクターデータで指定
された図形をフレームメモリに展開し、画像表示装置に
出力するもの等に関し、特に図形の塗りつぶし方法の改
善に関するものである。

【０００２】

【従来の技術】図１０に示すような図形すなわち、大き
な閉図形の中に小さな円をくりぬいたような図形を考え
る。大きな図形とその中の小さな円とで囲まれた部分を
塗りつぶす際において、従来の方法では図１０に示すよ
うにベクターデータ（ｐ１ｐ２、ｐ２ｐ３、ｐ３ｐ４、
・・・、ｐ８ｐ９及びｐ１０を中心とする円）をフレー
ムメモリ上に展開した後、閉図形とそうでない部分の境
界線データを演算し、ついで、各境界線に挟まれた部分
の塗りつぶしオンオフを判別していた。なお、図１０に
おいて、４はフレームメモリで格子状に描いた各格子点
が１つの記憶セルを表している。

【０００３】

【発明が解決しようとする課題】このため、プロセッサ
の演算あるいは判断が多くなってしまい、処理時間等が
大きくなってしまう問題点があった。また、図形を移動
処理した際等において、当該図形が有効処理領域の外に
はみ出したことによる図形の欠損については考慮されて
おらず、この境界部分に対する塗りつぶし処理が行えな
いという問題点があった。さらに、曲線データ等を処理
した場合、処理装置の演算精度によりその端点座標がず
れてベクトル間のつなぎ部に隙間が生じる場合があっ
た。その結果、このつなぎ部に対する塗りつぶし処理が
行えないといった問題点があった。この発明はこれらの
問題点に鑑みなされたもので、処理が速く、また正確な
図形塗りつぶし方法を提供するものである。

【０００４】

【課題を解決するための手段】このため、この発明にお
いては、フレームメモリに展開された閉図形を構成する
１または複数のベクターデータについて、フレームメモ
リの同一走査ラインにおけるオンデータ対を順にさがし
出していき、これらのオンデータ対間を黒データとした
のち、先のデータと排他的論理和を順次とるように構成
したものである。またこのような処理において、有効処
理範囲との境界とを考慮するとともに隣接するベクター
データ間の端点の一致度を考慮するようにしたものであ
る。

【０００５】

【作用】図１〜図３を参照して、本発明の原理を説明す
る。図１はこの発明の構成を模式的に示す説明図で、１
は塗りつぶし処理部、２は塗りつぶし信号発生部、３は
排他的論理和回路、４はフレームメモリ、５はＣＲＴ表
示器である。

【０００６】まず、フレームメモリ４の図形生成部分を
クリアする。塗りつぶし処理部１に一つまたは一連のベ
クター信号からなる塗りつぶし信号が入力される。各ベ
クター信号は、展開されるべきフレームメモリ４の記憶
セルの位置に関連する一次処理データに順次変換され
る。次に、塗りつぶし信号発生部２において、これらの
ベクター信号に基づく一次処理データから前記フレーム
メモリに関する同一走査ライン上の、対となるオンデー
タが存在するか否か判定する。

【０００７】図２に示すように、このような塗りつぶし
においては、同一走査ライン上におけるオンデータ対と
して、典型的には（ａ）、（ｂ）、（ｃ）の３種類のも
のが有り得る。同一走査ラインにおいて、図２（ａ）に
示す１対のオンデータが存在する場合には、両オンデー
タ（Ａ及びＢ）を含むその間のすべてをオンデータとす
る。塗りつぶし信号発生部２は、上記オンデータ群を順
次排他的論理和回路３に出力する。排他的論理和回路３
には、もう一つの入力として、上述の順次出力されるオ
ンデータが展開されるべきフレームメモリ４の対応する
記憶セルに格納されたデータ（オンデータまたはオフデ
ータ）が付与される。そして、この排他的論理和回路３
内で塗りつぶし信号発生部２からのオンデータとそれに
対応するフレームメモリ４の記憶セルのデータとが演算
される。フレームメモリ４の最初の状態は、当該図形生
成部分についてはクリアされた状態であるので、排他的
論理和回路３に付与されるフレームメモリに関する入力
データはすべてオフデータとなる。したがって、この場
合の排他的論理和出力はすべてオンとなる。フレームメ
モリ４には、この排他的論理和出力が対応する記憶セル
内に格納される。

【０００８】同一走査ラインにおけるオンデータ対が、
図２（ｂ）に示すように、複数対存在した場合には、ま
ずＡＢ間の処理を、次いでＣＤ間の処理を行うよう構成
している。同一走査ラインにおけるオンデータ対が図２
（ｃ）に示すような場合すなわち閉図形内部にくりぬか
れるべき閉図形が存在した場合（この場合において、ベ
クターデータはオンデータＡ、Ｂに関するベクターデー
タ、・・・、Ｃ、Ｄに関するベクターデータの順で処理
されるものとする）には、ＡＢ間のオンデータ対の処理
を最初に行う。上述の通り、フレームメモリ４は最初ク
リアされているので、ＡＢ間に対応するフレームメモリ
４の記憶セルにオンデータが書き込まれる。次いで、Ｃ
Ｄ間に関する処理が実行される。塗りつぶし信号発生部
２はＣＤ間のすべてをオンデータとし排他的論理和回路
３に順次出力する。また、排他的論理和回路３のもう一
方の端子にはフレームメモリ４の対応する記憶セル群の
データが順次入力されており、両者の排他的論理和が演
算される。先のＡＢ間処理によりフレームメモリ４のＡ
Ｂ間に対応する記憶セルにはオンデータが書き込まれて
いる。したがって、この部分の論理和はオフとなりフレ
ームメモリ４のＡＢ間の記憶セルにはオフデータが格納
される。なお、このような閉図形においては、図３に示
すように図形の頂点の場合には、同一走査ラインにおい
て対となるオンデータが生じない。このような場合、こ
の発明の実施例装置においては、前記オンデータと同一
のダミーのオンデータを生成してオンデータ対として処
理している。以上のように、この発明では、オンデータ
間のすべてのデータをオンデータとした後、フレームメ
モリの対応する記憶セルのデータと排他的論理和をとる
ようにしたので、塗りつぶし処理が簡単になる利点があ
る。

【０００９】そして、当該図形が有効処理領域外にはみ
出した場合には、例えば図形の前処理段階において図形
がはみ出したことにより生じた開口部をダミーの線分で
結合して新たに閉図形を生成する処理、あるいは一次処
理データを取得した後にこの一次処理データが有効か否
かを判定し、有効でない（範囲外である）場合には有効
処理領域を示す境界座標を当該走査ラインにおける新た
な一次処理データとする処理を実行することで、描かれ
るべき閉図形が有効処理領域外にはみ出した場合でも正
常な塗りつぶしを行なうことができる。さらに、閉図形
を構成する複数のベクターデータに不連続部が生じてい
た場合、それらの不連続部を結合する処理をおこなわせ
ることで、何らかの事情により不連続部が生じた閉図形
であっても正常な塗りつぶしを行なうことができる。

【００１０】

【実施例】以下、図４及び図５を参照して、本発明の塗
りつぶし処理について説明する。まず、図４を参照して
実際の閉図形処理について説明する。なお、図中、１１
は塗りつぶし処理部１に設けられた開始位置レジスタで
ある。今、図４に示すように、ｐ１ｐ２、ｐ２ｐ３、ｐ
３ｐ４、ｐ４ｐ５、ｐ６ｐ７、ｐ７ｐ８、ｐ８ｐ９の直
線ベクター信号及び点ｐ１０を中心とする円描画ベクタ
ー信号がこの順で入力され処理されるものとする。フレ
ームメモリ４の各記憶セルを表す格子点について、その
位置を表すために仮に座標を付すことにする。左下の格
子点ｏ１の座標を（１，１）、その隣の格子点ｏ２の座
標を（２，１）、・・・、のように付すことにする。な
お、ここではフレームメモリ４のＹ座標位置を同一とす
るラインを同一走査ラインと呼ぶことにする。まず、開
始位置レジスタ１１をクリアする。この開始位置レジス
タ１１は各走査ラインに対応した記憶領域をもつもの
で、各走査ラインの最初のオンデータのＸ座標値を保持
するよう構成されている。

【００１１】第１の直線ｐ１ｐ２の処理を行う。直線ｐ
１ｐ２は、上述の座標に従えば、（５，３）、（５，
４）、（４，５）、（３，６）、（２，７）の各記憶セ
ルにオンデータが格納されてフレームメモリ４に、通常
の処理では展開されることになる。この明細書において
は、このような処理により生成された座標データを一次
処理データと呼ぶことにする。座標（５，３）として示
された一次処理データは走査ライン３のオンデータであ
り、またこの走査ラインに対応する開始位置レジスタ１
１の記憶領域３がクリアされている状態であるので、対
応する開始位置レジスタ１１の記憶領域３にデータ
「５」を格納する。同様に、座標（５，４）については
開始位置レジスタ１１の記憶領域４にデータ「５」を、
座標（４，５）については開始位置レジスタ１１の記憶
領域５にデータ「４」を、・・・、というように開始位
置レジスタ１１の各走査ラインに対応する記憶領域がク
リアされている限り、展開された各データ値のＸ座標値
が当該記憶領域に格納されるように構成されている。こ
のような処理は、第４の直線ｐ４ｐ５まで行われる。と
ころで、第３の直線ｐ３ｐ４の一次処理データは（２，
９）、（３，９）、（４，９）、（５，９）、（６，
９）、（７，９）となり、同一走査ライン（この場合に
は第９ライン）に複数のオンデータが生じる。この実施
例においては、同一のベクターデータを処理する際に同
一の走査ライン上に同一のデータが引き続く場合最初の
データを正規のデータとするよう処理している。すなわ
ち、この第９ラインに対応する開始位置レジスタ１１の
記憶領域９にはデータ「２」が格納される。

【００１２】さて、第５の直線ｐ５ｐ６の一次処理デー
タは、（１０，１５）、（１１，１４）、（１２，１
３）、・・・となる。ここで、第４の直線と第５の直線
は走査ラインに対して「山（Ｙ方向に頂点を持つ）」の
関係を有している。この関係は、第４の直線の傾きと第
５の直線の傾きを第５の直線の処理前（ベクター信号同
志の演算により）に知ることができる。このような場合
においては、第４の直線の最後のデータまたは第５の直
線の最初のデータ（１０，１５）について、同一のデー
タ（１０，１５）をダミーとして発生する。すでに、第
１５の走査ラインに対応する開始位置レジスタ１１の記
憶領域１５にはデータ「１０」が格納されているので、
この時点において、１対のオンデータが生成されたこと
になる。なお、この場合には、開始位置レジスタ１１の
記憶領域１５に格納されたｘ位置データとダミーのデー
タもともに「１０」となり、同一であるので、その間の
データは考慮する必要がなくそのままフレームメモリ４
の対応する記憶セルにオンデータとして保持しておくよ
うにしても良い。この処理が実行された段階で、開始位
置レジスタ１１の記憶領域１５はクリアされる。さて、
第５の直線ｐ５ｐ６の次の一次処理データは（１１，１
４）となる。開始位置レジスタ１１の記憶領域１４に
は、すでにデータ「９」が格納されているのでこの時点
でも１対のオンデータが生成される。この実施例ではフ
レームメモリ４とは別に一次処理データを作成処理する
ようにしているので、第１４の走査線上のこれらのデー
タ「９」及び「１１」を含むその間のデータ「１０」に
ついてオンデータが作成される。そして、これらのオン
データ群とフレームメモリ４の座標（９，１４）、（１
０，１４）、（１１，１４）に対応する記憶セルに格納
されたデータとに関し順次排他的論理和をとる。それぞ
れの記憶セルのデータはクリアされた状態（オフデー
タ）となっているので、上述の演算によりすべてオンデ
ータとなりフレームメモリ４の各記憶セルにはオンデー
タが格納される。同様に、この処理が成された段階で、
開始位置レジスタ１１の記憶領域１４（第１４走査ライ
ン）がクリアされる。これ以降の一次処理データについ
ても同様に順次処理されて、フレームメモリ４内に塗り
つぶしデータが作成格納される。

【００１３】第６の直線ｐ６ｐ７の一次処理データ（１
５，８）については、開始位置レジスタ１１の第８走査
ラインに対応する記憶領域にすでにデータ２が格納され
ているので、この走査ラインについてもオンデータ対が
生ぜられる。したがって、第８走査ライン上のＸ座標デ
ータ「２」〜「１５」に対応するフレームメモリ４の記
憶セルにオンデータが格納される。以上の処理を第１の
直線ｐ１ｐ２から第９の直線ｐ８ｐ９（ｐ８ｐ１）まで
順次処理することによってこれら第１〜第９の直線によ
って定義された閉図形の内部の塗りつぶしが完了する。
次ぎに、第１０のベクターデータ（点ｐ１０を中心とす
る円）の処理が行われる。この第１０の円データは、例
えば（１０，９）、（１０，１０）、（１１，１１）、
（１２，１１）、・・・、（１４，９）、・・・、（１
０，８）のように一次処理データが作成される。すなわ
ち、この円データは第７走査ラインから第１１走査ライ
ンまでのデータとなっている。ここで、開始位置レジス
タ１１の第７走査ライン〜第１１走査ラインに対応する
記憶領域７〜１１は、先の閉図形処理においてすべてオ
ンデータ対が生成されて塗りつぶし処理が行われた状態
の後であるので、クリアされた状態にある。したがっ
て、第１の一次処理データ（１０，９）については、第
９走査ラインに対応する記憶領域９にデータ「１０」が
格納される。そして、７番目の一次処理データ（１４，
９）が生成されたとき、第９走査ラインにおけるオンデ
ータ対が完成する。そして、第９走査ラインのこの間の
データ（Ｘ座標値「１０」〜「１４」）をオンデータと
して、対応するフレームメモリ４の記憶セルに格納され
たデータと排他的論理和をとる。フレームメモリ４の対
応する記憶セルのデータは先の閉図形処理においてオン
データであるので、この演算結果はオフデータとなり上
記各記憶セルにはオフデータが格納される。このよう
に、この実施例においてはくりぬき処理も容易に行え
る。

【００１４】上述の処理の実際においては、１ｍｍ当た
り少なくとも８個のデータが存在する極めて精細なデー
タ処理であるので、きれいな塗りつぶし処理を行うこと
ができる。そして、上述の処理では同一の走査ライン上
に同一のオンデータが連続して発生する場合に最初のデ
ータを正規のデータとして開始位置レジスタの対応する
記憶領域に格納するようにした例を述べたが、上記のよ
うに実際上はデータ間隔が極めて微細であるので、同一
の走査ライン上に同一のオンデータが連続する場合には
走査ラインが変更される１個前のデータ（図４の第３の
直線ｐ３ｐ４の場合（６，９）のデータ）を採用するよ
うにした方がきれいな塗りつぶし処理となる場合があ
る。また、走査ラインに対して、「山（または谷）」の
関係にあることを知る方法について、上述の処理におい
ては引き続くベクターデータの一次処理化に先だって、
１個前のベクターデータと引き続くベクターデータとを
比較する方式を用いたが、これとは別に前もってすべて
のベクターデータに関してそれらの関係を把握するよう
にしても良いし、最後の段階で「山（または谷）」関係
を把握して上述の処理を一括して行うようにしても良
い。また、上述の実施例装置においては、同一走査ライ
ン上の対となるオンデータを含めたその間のデータをす
べてオンデータとしてオンデータ群を作成するようにし
たが、対となるオンデータすなわち両端のデータについ
ては含まないものとしてオンデータ群を作成するように
しても良い。さらに、上述の実施例では、フレームメモ
リ４の図形生成部分のクリア処理は最初の段階で行うも
のとしたが、オンデータ対が認識され最初の排他的論理
和処理がなされる前のいずれの段階でクリアしても良
い。また、この実施例ではフレームメモリ４に直接塗り
つぶしを行なうものとしているが他のフレームメモリま
たはその他のメモリを使用して処理をなし塗りつぶしを
含めたすべてのデータ処理がなされた段階でフレームメ
モリ４に書き出すようにしてもよい。なお、閉図形を定
義するベクターデータの処理順序は、図２（ｃ）の場
合、Ｃに関するベクターデータ、ＡＢに関するベクター
データ及びＤに関するベクターデータの順で処理しても
同様な結果が得られる。従って、この発明ではどのよう
な処理順序でも良い。

【００１５】図５は、この発明に関わる塗りつぶし処理
の流れの１例を示すフローチャートである。ステップ
（２）では最初のベクター信号を導入する。ステップ
（３）において前段ベクター信号の有無を判定し、前段
ベクター信号がなければステップ（６）に移る。前段ベ
クター信号が存在する場合その関係すなわち「山」また
は「谷」の関係にあるか判定する。「山」または「谷」
の関係にある場合にはステップ（５）にてダミー点を発
生し、ステップ（９）にてフレームメモリ４の対応する
記憶セルに格納されたデータと排他的論理和をとる。
「山」または「谷」の関係でない場合には直線補間すな
わちベクター信号の一次処理を行い最初の一次処理デー
タに関してステップ（７）にて対応する位置レジスタ１
１を参照する。オンデータ対が完成していればステップ
（９）にて塗りつぶしが行われ、ステップ（１０）にて
当該位置レジスタをクリアした後ステップ（１１）に移
動する。ステップ（７）にてオンデータ対が完成してい
ない場合には当該位置レジスタにその直線補間値（一次
処理データ）を格納する（ステップ（８））。そして、
ステップ（１１）にて次の直線補間値（一次処理デー
タ）の有無をチェックし、存在すればステップ（７）に
戻り同様な処理を行う。ステップ（１１）にて次の直線
補間値がない場合すなわち一つのベクターデータの処理
が完了した場合には、ステップ（１３）にて引き続くベ
クター信号の有無を判定する。あればステップ（１４）
にて次のベクター信号を導入してステップ（３）以下の
処理を引き続き行う。ステップ（１３）にて引き続くベ
クター信号がない場合にはステップ（１５）に移り最初
のベクター信号との関係すなわち「山」または「谷」の
関係があるか否かチェックする。あればステップ（１
６）にて、ダミー点を発生し塗りつぶし処理（ステップ
（１７））を行い、ステップ（１８）に移る。ステップ
（１５）にて「山」、「谷」の関係がない場合には、ス
テップ（１８）にて次の組のベクター信号があるか否か
（図４に示す円データのようなベクター信号）チェック
し、あればステップ（１４）にて次の組のベクター信号
を導入してステップ（３）以下の処理を行う。

【００１６】次ぎに、図６および図７を参照して、有効
処理範囲外に位置付けられた閉図形の処理について説明
する。ここで、図６は処理すべき閉図形の状態を模式的
に示した説明図であり、図７はそのフローチャートであ
る。図６に示した例では、直線ｐ１ｐ２、ｐ２ｐ３、ｐ
３ｐ４、ｐ５ｐ６、ｐ６ｐ７およびｐ７ｐ８が境界線Ｘ
１、Ｙ１と交差し、直線ｐ４ｐ５はすべてが有効処理範
囲外にある。そしてこれらの直線はｐ１ｐ２、ｐ２
ｐ３、ｐ３ｐ４、ｐ４ｐ５、ｐ８ｐ７、ｐ６ｐ
５、ｐ６ｐ７、ｐ８ｐ１の順で描かれる。また前記
境界線Ｘ１、Ｙ１が交差している点を原点ｐ０とする。
この処理においては、線分等のベクターを処理する場
合、まずこのベクターが有効処理範囲内にあるか否かを
判定する。その結果、このベクターの全てが有効処理範
囲外にあると判定された場合には、このベクターを処理
の対象から除外する。そしてこのベクターの一部が有効
処理領域外にあると判定された場合には、このベクター
と境界線との交点を算出し、前記ベクターにおける有効
処理領域外側の端点をこの交点に置き換える。すなわ
ち、このベクターにおける有効処理領域内側の端点と算
出した交点とを結ぶ直線を新たなベクターとする処理を
行なう。また、この実施例装置にはＸ側の境界線Ｘ１に
対応する境界レジスタ１２Ｘが用いられている。この境
界レジスタ１２Ｘは、前記境界線Ｘ１に処理ベクターが
交差したり接触した場合にその交点のＹ座標値を保持す
るもので、先に説明した開始位置レジスタ１１と同様な
処理をなすものである。本実施例においては、この境界
レジスタ１２Ｘを使用して境界線Ｘ１上にダミーベクタ
ーを発生する。この境界レジスタ１２Ｘは一群のデータ
導入前に一旦クリアされる。また、境界線Ｙ１との交差
部分についてはダミーベクターは生成しない。これは前
述したように本発明がオンデータ対を用いて走査ライン
方向（Ｙ軸方向）に塗りつぶしを行なう方式であり、境
界線Ｙ１上の交点情報（オンデータ）を取得することが
できれば当該境界線Ｙ１上における塗りつぶし処理が行
えるからである。

【００１７】以下、具体的な処理について説明する。ま
ず直線ｐ１ｐ２の処理を行なう。この場合、端点ｐ２が
有効処理範囲外にあり、直線ｐ１ｐ２は境界線Ｙ１との
み交差している。従って、ここではその交点ｐ９を算出
し直線ｐ１ｐ２を直線ｐ１ｐ９に置き換える。そして直
線ｐ２ｐ３についても同様な処理が行われ、交点ｐ１０
を算出した後に新たな直線ｐ１０ｐ３に置き換えられ
る。次ぎに直線ｐ３ｐ４を処理する。この直線ｐ３ｐ４
は有効処理範囲内にて境界線Ｙ１と交差し、さらに有効
処理範囲外にて境界線Ｘ１と交差している。まずこの直
線ｐ３ｐ４と境界線Ｘ１とが比較され交点ｐ１２が算出
される。ここで、この交点ｐ１２の座標値に基づいてこ
の交点ｐ１２の属性が判定され「Ｘ側で境界線Ｘ１上で
ありＹ側にて下限値より下にある点」と認識される。こ
れにより前記境界レジスタ１２Ｘを参照する。この時点
においてこの境界レジスタ１２Ｘはクリアされているの
で、この境界レジスタ１２Ｘに原点ｐ０のＹ座標値を設
定する。本来ならばこの値は境界線Ｘ１と交差した位置
のＹ座標値を設定するべきであるが、境界線Ｙ１より下
側の範囲は使用しないのでＹ側下限値、すなわち原点ｐ
０のＹ座標値を設定する。次いでこの直線ｐ３ｐ４と境
界線Ｙ１とを比較し交点ｐ１１を算出する。そしてこの
直線ｐ３ｐ４をｐ３ｐ１１に置き換える。なお、この処
理において、境界線Ｙ１で規定される処理範囲外に前記
境界線Ｘ１と交差する線分が複数本存在する場合が考え
られる。この場合、境界レジスタ１２Ｘがクリアされた
状態にあっては原点ｐ０のＹ座標値を設定する。また既
に境界レジスタ１２Ｘに値が格納されている場合であっ
てその値が原点ｐ０のＹ座標値であった場合にはこの境
界レジスタ１２Ｘをクリアして次順の処理に移行する。
その値が原点ｐ０のＹ座標値以外の場合にはその座標と
原点ｐ０との間にダミー線分を生成し、レジスタをクリ
アする処理が行われる。

【００１８】次ぎに直線ｐ４ｐ５の処理を行なう。まず
境界線Ｘ１、Ｙ１との比較が行なわれる。そしてこの直
線ｐ４ｐ５は「すべて有効処理範囲外にある」と判定さ
れ、これによりこの直線ｐ４ｐ５は以後の処理に関して
対象外となる。次ぎに直線ｐ８ｐ７の処理を行なう。こ
の直線ｐ８ｐ７はＸ側境界線Ｘ１とのみ交差しているの
でこの境界線Ｘ１との交点ｐ１６が算出され、この直線
ｐ８ｐ７は直線ｐ８ｐ１６に置き換えられる。そして交
点ｐ１６が算出されたことにより前記境界レジスタ１２
Ｘを参照する。この時点においてこの境界レジスタ１２
Ｘには原点ｐ０のＹ座標値が格納されておりデータ対が
作成可能であるので、交点ｐ１６と原点ｐ０とを結ぶ直
線ｐ１６ｐ０を第１のダミー直線として生成する。そし
てこの直線が生成されたことにより前記境界レジスタ１
２Ｘの値はクリアされる。

【００１９】次ぎに直線ｐ６ｐ５の処理を行なう。この
直線ｐ６ｐ５は有効処理範囲内において境界線Ｘ１と交
差し、有効処理範囲外にて境界線Ｙ１と交差している。
まず境界線Ｘ１と比較され交点ｐ１４が算出される。そ
してこの直線ｐ６ｐ５をｐ６ｐ１４に置き換えた後、前
記境界レジスタ１２Ｘを参照する。この時点において境
界レジスタ１２Ｘはクリアされた状態にあるので、前記
交点ｐ１４のＹ座標値を境界レジスタ１２Ｘに格納す
る。次いでこの直線ｐ６ｐ５と境界線Ｙ１とを比較す
る。ここで交点ｐ１３が算出されるが、本発明において
は境界線Ｘ１上にダミーの線分を生成する構成となって
いるのでこの交点ｐ１３は意味を持たない。従って、こ
の交点ｐ１３を算出したら次ステップに移行する。勿
論、判定処理を追加することにより境界レジスタ１２Ｘ
に値を格納した時点で次ステップに移行する構成として
もよい。

【００２０】次ぎに直線ｐ６ｐ７の処理を行なう。この
直線ｐ６ｐ７は先に説明した直線ｐ８ｐ７と同様に処理
され、交点ｐ１５が算出された後に新たな直線ｐ６ｐ１
５に置き換えられる。次いで境界レジスタ１２Ｘを参照
し、交点ｐ１４と交点ｐ１５との間に第２のダミー線分
を生成する。そして最後に線分ｐ８ｐ１に対する処理を
行なう。まずこの直線ｐ８ｐ１と境界線Ｘ１、Ｙ１との
比較が行われ「範囲内」の判定結果が得られる。この結
果を受けて次ステップに移行する。以上の処理により、
導入された直線データは、ｐ１ｐ９、ｐ１０ｐ３、
ｐ３ｐ１１、ｐ８ｐ１６、ｐ１６ｐ０（第１のダ
ミー線分）、ｐ１４ｐ６、ｐ６ｐ１５、ｐ１４ｐ
１５（第２のダミー線分）、ｐ８ｐ１の各線分に変換
される。そして、これら各線分は〜の順序で前記し
た塗りつぶし処理手段に導入される。なお、以上はＸ側
境界線が左側境界部を、Ｙ側境界線が下側境界部をそれ
ぞれ規定している例について説明したが、右側境界部及
び上側境界部についても同様に処理することができる。
また、導入ベクターはどのような順序で入力されたとし
ても、塗りつぶし処理において同じ結果が得られる。

【００２１】図７は上述した境界部処理の流れを示すフ
ローチャートである。本実施例装置においてはまずＸ側
境界線に対する処理が行われる。ステップ（２）で境界
レジスタ１２Ｘの内容をクリアするイニシャライズを行
い、次いでステップ（３）でベクターデータを導入す
る。ステップ（４）ではステップ（３）で導入したベク
ターデータが有効領域内にあるか否かについて判定す
る。そして、「領域内」と判定された場合にはステップ
（５）に移り、また「領域外」と判定された場合にはス
テップ（１９）で対象から除外した後にステップ（２
１）へ移行し次順ベクターを処理する。ステップ（５）
では導入ベクターとＸ側境界線とを比較する。両者が交
差していないと判定された場合にはステップ（１６）に
移りＹ側の処理に移行する。両者が交差していると判定
された場合にはステップ（６）にて両者の交点座標を算
出した後にステップ（７）に移り、この座標が処理領域
内に属するか否かを判定する。ステップ（７）で「領域
内」と判定された場合にはステップ（８）に移り算出し
た座標を交点座標として保持し、「領域外」と判定され
た場合にはステップ（９）に移り上限値又は下限値を交
点座標として保持する。次いでステップ（１０）に移り
境界レジスタを参照する。この境界レジスタに値が格納
されていない場合にはステップ（１１）にて保持してい
る交点座標を境界レジスタに格納しステップ（１６）に
移行する。また境界レジスタに値が格納されている場合
にはステップ（１２）にてこの格納値が上下限値である
か否かを判定する。上下限値でない場合、ステップ（１
３）に移行して算出した交点座標（上下限値）と格納座
標との間にダミーの線分を生成し、ステップ（１４）に
て境界レジスタをクリアする。また格納値が上下限値で
あった場合、ステップ（１５）に移り算出した交点座標
が上下限値であるか否かを判定する。ステップ（１５）
で上下限値でないと判定された場合にはステップ（１
３）にてダミーの線分を生成し、上下限値であると判定
された場合にはステップ（１４）にて境界レジスタをク
リアする。以上でＸ側境界線に対する処理が終了する。

【００２２】次いでＹ側境界線に対する処理を行なう。
まずステップ（１６）にて導入ベクターとＹ側境界線と
を比較する。両者が交差していないと判定された場合に
はステップ（２１）に移行する。両者が交差していると
判定された場合にはステップ（１８）にて両者の交点座
標を算出した後にステップ（１９）に移り、この座標が
処理領域内に属するか否かを判定する。ここで「範囲
内」と判定された場合にはステップ（２０）にて算出さ
れた交点を端点とする新たな線分を生成しそしてステッ
プ（２１）に移行する。一方「範囲外」と判定された場
合にはそのままステップ（２１）に移行する。ステップ
（２１）では次順ベクターが残存するか否かを判定し、
残存する場合にはステップ（３）にて新たなベクターデ
ータを導入する。

【００２３】この境界部の処理は一次処理データ取得時
に行なうこともできる。これは、各ベクターデータから
一次処理データを取得する際に、１つのドットに対する
座標値を取得した後にこのドットが有効処理領域内にあ
るか否かをこの座標値に基づいて判定し、「存在しな
い」と判定した場合には領域外とされた側の座標値を境
界線上の座標値に変換することにより行われる。例え
ば、Ｙ側の境界線が「Ｙ＝１」で、線分を展開して得ら
れた一次処理データのＸＹ座標値が（５，−５）であっ
たとする。この場合、Ｙ座標値が「−５」であるので、
この点はＹ方向で領域外となっていることが判る。そし
て次の段階でこのデータを（５，１）に変換する。この
処理を各ドット毎に行なうことによりはみ出した閉図形
に対する境界部の処理を行なうことができる。

【００２４】次いで図８を参照し、本発明における曲線
を含む線分群を処理する際に生じる端点処理について説
明する。図８は、２つの直線間を曲線により補間する場
合について説明する図である。まずこの図を参照し、従
来装置の問題点について示すことにする。図８に示した
図形は、第１の直線ｐ１ｐ２、円弧ｐ２ｐ３、第２の直
線ｐ３ｐ４及び第３の直線ｐ４ｐ１から構成されてい
る。ところで、上記円弧ｐ２ｐ３を処理する場合、この
円弧を複数の短い線分ｐ２ｐ５、ｐ５ｐ６、・・・ｐ１
０ｐ１１で近似するとその処理が高速化でき都合がよ
い。しかしながら、この直線による近似は三角関数を使
用する必要があり誤差を伴ってしまう。すなわち円弧を
複数の線分で近似するために、中心座標、半径、始点・
終点角及び分割数等を与え、三角関数により円弧上の近
似点を決定する方法が採られている。このようにして描
画された円弧はその端点を三角関数を使用した演算処理
により決定しているのでこの演算精度に基づくズレが生
じてしまう。そして、最終の短直線の端点ｐ１１と第２
の線分の端点ｐ３との間に僅かなズレが生じ、本来閉図
形となる図形の一部が欠落して塗りつぶし処理が正常に
行えなかった。

【００２５】本発明においては、このようにずれた端点
座標を補間した後に塗りつぶしを行うよう構成されてい
る。以下、この図８を参照してこの補間動作について説
明する。図８において１３は候補点レジスタで、接合さ
れるべき線分の候補となる端点（候補点）が順次格納さ
れるものである。まず、第１の直線ｐ１ｐ２に関する始
点ｐ１、終点ｐ２を導入する。まず始点ｐ１に関し前処
理ベクターにより発生した候補点との一致／非一致が判
定され、次いでこの始点の周囲の所定範囲内に他の候補
点が存在するか否かが判定される。そして、終点ｐ２に
対しても同様の判定処理が行われる。この場合第１の直
線ｐ１ｐ２は最初に描かれた直線であるから、判定結果
はいずれも「存在なし」となる。これを受けて端点ｐ
１、ｐ２を候補点として候補点レジスタ１３の記憶セル
１、２に格納する。なお、上記所定範囲は種々条件によ
って規定される距離であるが、１ｍｍあたり８ドット程
度のものにおいて０〜４ドット程度、すなわちコンマ数
ｍｍ程度に規定される。図８において、前記点ｐ３とｐ
１１はこの所定範囲内の点同士であるものとする。

【００２６】次いで、曲線ｐ２ｐ３に対する処理を行な
う。この曲線ｐ２ｐ３は、先に述べたように複数の短直
線ｐ２ｐ５、・・・ｐ１０ｐ１１で与えられる。そし
て、これらの短直線群は第１の短直線ｐ２ｐ５から順次
処理される。まず第１の短直線の始点ｐ２と先の上記第
１の直線の終点とが一致するか否かが判定される。この
場合、両者は点ｐ２で一致しているので連続線分と判定
され、これにより候補点レジスタ１３の記憶セル２から
点ｐ２が削除される。これで始点ｐ２に対する処理を終
了し終点ｐ５に対する処理が行われる。終点ｐ５につい
ても同様の判定が行われ、まず第１の直線の終点ｐ２と
の比較が行われる。ここでは非一致と判定されて次ステ
ップに移行する。次ステップでは終点ｐ５の周囲に他の
端点（候補点）が存在するか否かを格納の新しい順に判
定する。この場合、候補点レジスタ１３の記憶セル１と
の比較、すなわち第１の直線の始点ｐ１との比較が行わ
れるが両者は距離が離れているので非一致と判定され
る。これにより終点ｐ５が候補点レジスタ１３の記憶セ
ル２に格納される。以上で第１の短直線に対する処理が
終了する。次いで第２の短直線ｐ５ｐ６が導入される。
この場合の処理も先の第１の短直線ｐ２ｐ５と同様に行
われる。まず第２の短直線の始点ｐ５と第１の短直線の
終点が比較され、両者はｐ５で一致しているのでこれに
より両者は連続線分と判定される。次に第２の短直線の
終点ｐ６が比較されてこの点ｐ６が候補点レジスタ１３
の記憶セル２に格納される。このような処理を最終の短
直線ｐ１０ｐ１１まで繰り返し実行する。その結果、第
１の直線ｐ１ｐ２から最終の短直線ｐ１０ｐ１１までが
連続した線分と判定され、そして前記候補点レジスタ１
３の記憶セル１には第１の直線の始点ｐ１が、記憶セル
２には最終の短直線の終点ｐ１１が格納される。

【００２７】次ぎに第２の直線ｐ３ｐ４が導入される。
まずこの第２の短直線の始点ｐ３と最終の短直線の終点
ｐ１１とが一致しているか否かを比較する。この場合非
一致と判定されて次ステップに移行する。次ステップで
は、まず第２の直線の始点ｐ３と候補点レジスタ１３の
記憶セル内に格納された候補点とを格納の新しい順に比
較し所定範囲内の点であるか否かを判定する。ここでは
記憶セル２に格納された最終の短直線ｐ１１が所定範囲
内の点と判定される。この判定を受けて上記第２の直線
ｐ３ｐ４とこの最終の直線ｐ１０ｐ１１との結合処理が
行なわれる。この場合には双方の座標が異なっているの
で、最終の短直線の終点座標ｐ１１と第２の直線の始点
座標ｐ３との間にダミーの線分ｐ３ｐ１１を生成し、上
記最終の短直線ｐ１０ｐ１１と上記第２の直線ｐ３ｐ４
とを結合する。この結合処理においては、第２の直線ｐ
３ｐ４に関し、この第２の直線の始点座標ｐ３を上記最
終の短直線の終点座標ｐ１１に変更し、上記第２の直線
をｐ１１ｐ４としてもよい。このように構成すると、第
２の直線が比較的長い線分である場合に補間した部分が
目立たないといった利点がある。次ぎに第３の直線ｐ４
ｐ１を処理し、一連の処理を終了する。

【００２８】図９は上述した端点処理の流れの１例を示
すフローチャートである。ステップ（２）では一つのベ
クター信号の始点座標Ｐｓと終点座標Ｐｅを導入する。
ここで線分が曲線である場合、このベクター信号は当該
曲線を分割した短直線に相当する。ステップ（３）にお
いて、前回導入したベクター信号の終点座標と今回導入
したベクター信号の始点座標Ｐｓとが一致するか判定す
る。一致した場合にはステップ（７）に移り、非一致の
場合にはステップ（４）に移る。ステップ（４）では上
記始点座標Ｐｓと候補点バッファに格納された端点座標
とを格納の新しい順に比較する。そしてステップ（５）
へ移り、上記始点座標Ｐｓに対し所定範囲内の端点座標
（対象座標という）が存在したか否かを判定する。存在
していた場合にはステップ（６）に移り、この始点座標
Ｐｓと対象座標との結合処理を実行する。この結合処理
は、始点座標Ｐｓと対象座標との間にダミーの線分を生
成すること、あるいは対象座標を含む線分に対し、その
端点座標を対象座標から始点座標Ｐｓに置き換えること
により行われる。そしてステップ（７）では、上記ステ
ップ（６）で結合処理が行われた端点座標、あるいは上
記ステップ（２）で「一致」と判定された端点座標を上
記候補点バッファから削除し、ステップ（９）に移る。
一方、上記ステップ（５）で所定範囲内の端点座標が存
在しなかった場合にはステップ（８）にて上記始点座標
Ｐｓを候補点バッファに登録し、ステップ（９）に移
る。ステップ（９）〜（１４）では、上述した処理を終
点座標Ｐｅについて行っている。そしてこの処理は、先
のステップ（２）〜（８）におけるＰｓをＰｅに置き換
えただけであるので、その説明を省略する。そして、ス
テップ（１３）あるいはステップ（１４）を経るとステ
ップ（１５）に移り、ここで全ベクター信号の処理が終
了したか否かを判定する。全ベクター信号が処理された
場合にはステップ（１６）に移り塗りつぶし処理に移行
する。一方、未処理のベクター信号がある場合にはステ
ップ（２）に移り次順のベクター信号の処理を行なう。

【００２９】

【発明の効果】以上説明したように、この発明によれば
ベクターデータの一次処理値を求めオンデータ対が完成
した段階で塗りつぶし処理を行うよう構成したので、連
続した処理を順次に行うことができ、処理時間を短縮す
ることができる。そして、有効処理領域外にはみ出した
図形をダミーの線分で処理し、新たに閉図形を生成する
ので、図形が有効処理領域外にはみ出した場合でも正常
な塗りつぶしを行なうことができるといった利点があ
る。さらに、曲線を含む図形に対し、演算誤差によって
ずれた曲線の端点と対応する線分の端点とを結合するの
で、正常な塗りつぶしを行なうことができるといった利
点がある。

【図面の簡単な説明】

【図１】図１は、本発明の構成例を模式的に示す説明図
である。

【図２】図２は、本発明の塗りつぶし処理の原理を説明
する模式図である。

【図３】図３は、本発明の塗りつぶし処理の例外を説明
する模式図である。

【図４】図４は、本発明の塗りつぶし方法を説明する模
式図である。

【図５】図５は、本発明の塗りつぶし処理の流れを示す
フローチャートである。

【図６】図６は、本発明の塗りつぶし処理における境界
部処理方法を説明する模式図である。

【図７】図７は、本発明の塗りつぶし処理における境界
部処理の流れを示すフローチャートである。

【図８】図８は、本発明の塗りつぶし処理における端点
部処理方法を説明する模式図である。

【図９】図９は、本発明の塗りつぶし処理における端点
部処理の流れを示すフローチャートである。

【図１０】図１０は、従来の塗りつぶし方法を説明する
模式図である。

【符号の説明】

１：塗りつぶし処理部 ２：塗りつぶし信号発生部 ３：排他的論理和回路 ４：フレームメモリ ５：ＣＲＴ表示器

Claims (3)

【特許請求の範囲】
1. 【請求項１】閉図形を構成する１個または複数のベクタ
   ーデータを順次取り込み該閉図形の内部を塗りつぶす閉
   図形塗りつぶし方法において、 前記ベクターデータを順次取り込みそれらのベクターデ
   ータが展開されるべきフレームメモリの記憶セルの位置
   に関連する一次処理データを得る段階、 前記得られた一次処理データに関して、前記フレームメ
   モリの同一走査ラインにおけるオンデータ対を認識する
   段階、 前記同一走査ライン上のオンデータ対間のデータをオン
   データとするオンデータ群を作成する段階、 前記生成した同一走査ライン上のオンデータ群と当該オ
   ンデータ群の各々に対応するフレームメモリの記憶セル
   内のデータとの排他的論理和を演算する段階、 前記排他的論理和の結果を前記フレームメモリの対応す
   る記憶セルのデータとする段階、 とを有した閉図形塗りつぶし方法。
2. 【請求項２】前記閉図形を構成する１個または複数のベ
   クターデータと有効処理範囲を示す境界線との交点とか
   ら境界データを取得し、取得した境界データに基づき前
   記境界線に沿った仮想のベクターデータを生成すること
   により、前記有効処理範囲内に閉図形を生成する段階を
   有してなる請求項１記載の閉図形塗りつぶし方法。
3. 【請求項３】複数のベクターデータから成る閉図形に関
   し、該複数のベクターデータの各端点の一致度を判定す
   る段階と、接続すべきベクターデータ間の端点が不一致
   である時、それらを結合する段階を設けたことを特徴と
   する請求項１記載の閉図形塗りつぶし方法。