(57)【特許請求の範囲】
【請求項１】
描画すべき描画データから、外形を表す描画ベクター及びクリップベクターを生成するベクター生成部と、
前記描画すべき描画データから描画属性を取得し、前記描画ベクターのそれぞれが前記クリップベクターのいずれでクリップされるかを示す対応表を作成する描画属性処理部と、
生成された前記描画ベクター及びクリップベクターをスキャンラインごとに取り出して、前記対応表に基づいて塗りつぶし処理とクリップ処理を行う塗りつぶし・クリップ処理部と
を有することを特徴とする描画処理装置。
【請求項２】
描画順序を表すＩＤと外形形状を決定する点列を含む描画コマンドから、前記ＩＤとスキャンライン上でのＸ切片の値とを含む複数の描画ベクター及びクリップベクターを生成するベクター生成部と、
前記ＩＤに基づいて、前記描画ベクターのそれぞれが前記クリップベクターのいずれでクリップされるかを示す対応表を作成する描画属性処理部と、
前記描画ベクター及びクリップベクターから一のスキャンラインを横切るベクター列を取得するベクター取得部と、
前記対応表及び、前記ベクター列内の描画ベクターとクリップベクターのＸ切片の値に基づいて、前記一のスキャンライン上の描画開始位置及び終了位置を決定して塗りつぶし処理とクリップ処理を行う塗りつぶし・クリップ処理部と
を有することを特徴とする描画処理装置。
【請求項３】
請求項２記載の描画処理装置において、
前記ベクター取得部で取得された前記ベクター列を前記Ｘ切片の値により、ソートするソート手段を有することを特徴とする描画処理装置。
【請求項４】
請求項３記載の描画処理装置において、
前記ソート手段は、前記塗りつぶし・クリップ処理部がスキャンラインを走査する順序で前記描画ベクター及びクリップベクターを取得できるようにソートすることを特徴とする描画処理装置。
【請求項５】
請求項３記載の描画処理装置において、
出力装置に出力画像を提供する画像出力部をさらに設け、
前記ソート手段は、前記画像出力部の主走査方向にソートすることを特徴とする描画処理装置。
【請求項６】
請求項２乃至５のいずれかに記載の描画処理装置において、
前記塗りつぶし・クリップ処理の後、前記一つのスキャンラインの次の処理対象のスキャンラインに無関係のベクター列を前記ベクター列から排除するベクター列排除手段を有することを特徴とする描画処理装置。
【請求項７】
請求項１乃至６のいずれかに記載の描画処理装置において、
前記ベクター生成部で生成された前記描画ベクター及びクリップベクターを記憶するベクター記憶部を有していることを特徴とする描画処理装置。
【請求項８】
請求項１乃至７のいずれかに記載の描画処理装置において、
前記描画属性処理部で作成された対応表を記憶する描画属性記憶部を有していることを特徴とする描画処理装置。
【請求項９】
請求項１乃至８のいずれかに記載の描画処理装置において、
前記描画ベクターのそれぞれが前記クリップベクターのいずれでクリップされるかを示す対応表は、塗りつぶし・クリップ処理に先立って生成されることを特徴とする描画処理装置。
【請求項１０】
請求項１乃至９のいずれかに記載の描画処理装置において、
前記塗りつぶし・クリップ処理部は、クリップ処理される描画ベクターに対応するクリップの状態に応じて、当該描画ベクター及び当該描画ベクターが影響を受けるクリップの全てが内部状態にある場合に登録される「内部状態」と、当該描画ベクターは内部状態にあるが、当該描画ベクターが影響を受けるクリップの一部または全部が内部状態にはなっていない場合に登録される「登録待ち状態」とに当該描画ベクターを分類する描画状態表を有することを特徴とする描画処理装置。
【請求項１１】
描画すべき描画データから、外形を表す描画ベクター及びクリップベクターを生成するベクター生成ステップと、
前記描画すべき描画データから描画属性を取得し、前記描画ベクターのそれぞれが前記クリップベクターのいずれでクリップされるかを示す対応表を作成する描画属性処理ステップと、
生成された前記描画ベクター及びクリップベクターをスキャンラインごとに取り出して、前記対応表に基づいて塗りつぶし処理とクリップ処理を行う塗りつぶし・クリップ処理ステップと
を有することを特徴とする描画処理方法。
【請求項１２】
請求項１１記載の描画処理方法において、
前記塗りつぶし・クリップ処理ステップは、クリップ処理される描画ベクターに対応するクリップの状態に応じて、当該描画ベクター及び当該描画ベクターが影響を受けるクリップの全てが内部状態にある場合に登録される「内部状態」と、当該描画ベクターは内部状態にあるが、当該描画ベクターが影響を受けるクリップの一部または全部が内部状態にはなっていない場合に登録される「登録待ち状態」とに当該描画ベクターを分類する描画状態表を用いることを特徴とする描画処理方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、描画処理装置に関し、特に、複数の任意形状のクリップ領域でクリップ処理及び塗りつぶし処理を行う描画処理装置に関する。
【０００２】
【従来の技術】
コンピュータ・グラフィックス（ＣＧ）、あるいはデスクトップ・パブリッシング（ＤＴＰ）等における描画処理装置は、入力された画像データや文字データ等に対して部分的表示を行わせるクリップ処理、所定の領域内を彩色する塗りつぶし処理、あるいはその両方の処理を必要に応じて行うことができるようになっている。
【０００３】
クリップ処理において、図形をクリップするクリップ領域には、矩形領域だけのものと任意形状を扱えるものとがある。クリップ領域として矩形領域だけ扱うクリップ処理では、描画要素とクリップ領域である矩形領域のすべての交点を求め、内部／外部を判定して、クリップ領域のみ表示させる方法が一般的である。このようなクリップ処理に基づく技術は、特開平１−１０３７８４号公報及び、特開昭６３−２４５５７６号公報、特開昭６３−１９８１７４号公報に開示されている。
【０００４】
一方、ＣＧ、ＤＴＰのように任意形状のクリップが頻繁に行われるような場合には、描画要素とクリップ領域とが交わる交点の数が非常に多くなる。従って、上述のクリップ処理方法を用いたのではクリップ領域の内部／外部の判定に費やす時間が膨大になってしまい、クリップ処理にかかる時間が増加してしまう。また、特開平６−１６８３３９号公報にしめされるように、太さを持つ線分を描画する際には、それが端点や接続点での図形を伴った複雑な外形の図形となるため、さらにクリップ処理の時間が増大してしまう。
【０００５】
そこで、エッジリストを用いてクリップ処理する方法が、特開平６−２７４６４３号公報に開示されている。エッジリストを用いたことにより、交点処理がスキャンライン毎の処理として単純化されており、高速にクリップ処理が行えるようになっている。
【０００６】
【発明が解決しようとする課題】
しかしながら、このエッジリストを用いるクリップ処理方法では、第１に、処理結果のマージ処理に時間がかかってしまう、第２に、ディスプレイリストで塗りつぶし処理をおこなってからその後クリップ処理を行うので処理に２ステップ要しており、処理が煩雑になってしまうという問題がある。
【０００７】
また、別のクリップ処理として、ベクターで図形のクリップを行う方法が特開平４−２８２７８４号公報に開示されている。しかしこの方法では、図形とクリップ領域が１対１の関係にある場合しか考慮しないクリップ処理なので、複数のクリップを処理する場合にはページメモリ上などでマージする必要が生じてしまい、やはりこのマージ処理に多くの時間を要してしまうという問題を有している。
【０００８】
本発明は、上述の従来の描画処理装置が有している問題を解決するためになされたものであって、その目的とするところは、クリップ領域が複数の任意形状からなるクリップ処理を、塗りつぶし処理と同時に高速に行うことができる描画処理装置を提供することにある。
【０００９】
【課題を解決するための手段】
上記目的は、描画すべき描画データから、外形を表す描画ベクター及びクリップベクターを生成するベクター生成部と、描画すべき描画データから描画属性を取得し、描画ベクターのそれぞれがクリップベクターのいずれでクリップされるかを示す対応表を作成する描画属性処理部と、生成された描画ベクター及びクリップベクターをスキャンラインごとに取り出して、対応表に基づいて塗りつぶし処理とクリップ処理を行う塗りつぶし・クリップ処理部とを有することを特徴とする描画処理装置によって達成される。
【００１０】
また、上記目的は、描画順序を表すＩＤと外形形状を決定する点列を含む描画コマンドから、前記ＩＤとスキャンライン上でのＸ切片の値とを含む複数の描画ベクター及びクリップベクターを生成するベクター生成部と、ＩＤに基づいて、描画ベクターのそれぞれがクリップベクターのいずれでクリップされるかを示す対応表を作成する描画属性処理部と、描画ベクター及びクリップベクターから一のスキャンラインを横切るベクター列を取得するベクター取得部と、対応表及び、ベクター列内の描画ベクターとクリップベクターのＸ切片の値に基づいて、一のスキャンライン上の描画開始位置及び終了位置を決定して塗りつぶし処理とクリップ処理を行う塗りつぶし・クリップ処理部とを有することを特徴とする描画処理装置によって達成される。
【００１１】
このように本発明は、複数の塗りつぶし処理とクリップ処理をベクターの状態で行うようにして、処理のステップ数を減らすと共に時間のかかるマージ処理を省略させるようにしている。
【００１２】
【発明の実施の形態】
本発明の一実施の形態としての描画処理装置を図１乃至図３５を用いて説明する。
まず初めに、本実施の形態の描画処理装置の構成を図１に示すブロック図を用いて説明する。本実施の形態の描画処理装置は、描画すべき描画データを受け取る描画データ入力部２を有している。描画データ判別部３は、描画データ入力部２に入力された描画データから描画データの種別を判別し、描画データの種別により外形を持つものはベクター生成部４と描画属性処理部５に描画データを渡し、外形を持たない場合は描画属性処理部５に描画データを渡す。ベクター生成部４は、描画データ判別部３から受け取った描画データから外形を表すベクターを生成する。描画属性処理部５では、描画データ判別部３から渡された描画データから、描画データの種別ごとで異なる描画属性を取得し、必要に応じて処理を行う。
【００１３】
描画ベクター記憶部６は、ベクター生成部４で生成されたベクターのうち、「塗り」及び「細線」の描画に関するベクター（描画ベクター）を保持する。クリップベクター記憶部８は、ベクター生成部４で生成されたベクターのうち、クリップに関するベクタ（クリップベクター）を保持する。描画属性記憶部９は、描画属性処理部で処理された描画属性データを保持する。塗りつぶし・クリップ処理部１０は、描画ベクター記憶部６とクリップベクター記憶部８で保持されている各ベクターをスキャンライン毎に取り出し、塗りつぶし処理とクリップ処理を同時に行うようになっている。画像出力部１２は、塗りつぶし処理とクリップ処理の終了したデータを画像出力装置（図示せず）に出力するようになっている。
【００１４】
以下、図１で示した本実施の形態の描画処理装置の個々の構成及び動作を図面を用いて詳細に説明する。
まず、描画データ入力部２で受け取られる描画データの構造を図２乃至図５に示す。描画データは図２に示すように描画コマンドの列として与えられる。例えば「クリップ登録」という描画コマンドは、描画順序を示すＩＤ及び、描画コマンドの種類がクリップ登録であることを示す識別子（ＣＬＩＰＳＥＴ）、クリップ領域の内部／外部の判定に用いる判定規則、クリップ形状を決定する座標値列（点１、・・・、点ｎ）から構成される。
【００１５】
また、「クリップ解除」という描画コマンドは、描画順序を示すＩＤ及び描画コマンドの種類がクリップ解除であることを示す識別子（ＣＬＩＰＣＬＥＡＲ）、解除するクリップのＩＤから構成される。さらに、「塗り」の描画コマンドの場合は、「クリップ登録」と同様に描画順序を示すＩＤ及び、描画コマンドの種類が塗りであることを示す識別子（ＦＩＬＬ）、塗りつぶし領域の内部／外部の判定に用いる判定規則、外形形状を決定する座標値列（点１、…、点ｎ）から構成され、さらに色の情報が追加されている。「細線」の場合には、内部／外部判定の規則は必要なく、ＩＤ及び、識別子、色、座標値列から構成されている。
【００１６】
描画コマンドの種類は、図３に示すように、「クリップ登録」、「クリップ削除」、「塗り」、「細線」等がある。「文字」や「ラスタ」等については、「文字」は「塗り」で表現でき、「ラスタ」は外形を図形で表現し、色が特殊なものとして扱うことができるので本実施の形態では除外するものとする。
【００１７】
クリップ領域及び塗りつぶし領域の内部／外部判定に用いる判定規則を図４に示す。判定規則にはワインディング規則（ＮＺ）と奇偶規則（ＥＯ）との２種類がある。これらはいずれも複数の外形（パス）で形成された一つの図形の内部を判定する際に用いられる規則である。ワインディング規則及び奇偶規則による図形の内部判定方法を図５を用いて説明する。図５（ａ）に示すワインディング規則は、図形２２を構成する外形がスキャンライン（走査線）２０と交差する際の向きを考慮したものである。図５（ａ）では外形がスキャンライン２０を上向きに交差する場合を正、下向きに交差する場合を負としている。走査方向に向かって正の交差であれば１を加算し、負の交差であれば１を減算することにし、合計値が０でなくなった点から０に戻った点までが内部であると判定する。図５（ｂ）に示す奇偶規則は、スキャンライン２０と交差するパスの個数をカウントして、奇数の点から偶数の点までを内部と判定することにしている。
【００１８】
次に、図１のベクター生成部４での処理を図６及び図７を用いて説明する。上述の通りベクター生成部４は、入力された描画データから外形を表すベクターを生成する。描画データには曲線成分も含まれているが、ここでは全て直線近似した後の直線データとして扱う。
【００１９】
ベクター生成部４で生成されるベクターは図６に示すようなデータ表現をとる。図６のベクターにおいて「ＩＤ」は描画コマンドのＩＤである。「Ｘ」は現在のスキャンラインを横切るベクターのＸ切片の値を示す。「Ｘ変位」は次のスキャンラインに処理が移動した場合のＸ切片の変化量を示している。「Ｙ変位」は当該ベクターに影響を受ける残りのスキャンライン数を示している。「向き」は当該ベクターの向きを示す。
【００２０】
図６のベクターを図７を用いてより具体的に説明する。図７において、座標系は図面左上方を原点とし、従って図面の水平右方向にＸ座標値は増加し、図面の垂直下方向にＹ座標値は増加するものとする。図７（ａ）に示すベクターは、始点Ｐ１の座標が（１００，１００）、終点Ｐ２の座標が（２００，２００）である。このベクターは、「ＩＤ」が例えばαとし、スキャンラインでのＸ切片の値を示す「Ｘ」は１００、次のスキャンラインに移動した場合のＸ切片の変化量「Ｘ変位」は１、残りのスキャンライン数「Ｙ変位」は１００、となる。ベクターの「向き」は座標系のＹ方向が増加する向きを１と定義し、座標系のＹ方向が減少する向きを−１と定義している。従って図７（ａ）でのベクターの「向き」は１である。この「向き」はワインディング規則で内部／外部判定を行う際に、どの向きでスキャンラインを横切るかを示す情報として用いられる。図７（ｂ）は、「向き」が−１の場合を示している。
【００２１】
本実施の形態においては、図２に示した描画コマンドにおける点列は、「塗り」と「クリップ登録」の場合には最後の点と最初の点とが結ばれるものと仮定している。従って、３角形の３辺は点列が３点あれば記述される。「細線」の場合には２点で構成されこの２点間を結ぶ直線が描画される。
このようなベクター表現で、描画データ入力部２に入力された描画データから外形を表すベクターがベクター生成部４で生成される。
【００２２】
ベクター生成部４で生成されたベクターのうち、「塗り」及び「細線」の描画に関するベクター（描画ベクター）は描画ベクター記憶部６に保持され、クリップに関するベクター（クリップベクター）はクリップベクター記憶部８で保持される。
【００２３】
次に、図１の描画属性処理部５および描画属性記憶部９での処理を図８乃至図１１を用いて説明する。描画属性処理部５では、図８に示したとおり、描画コマンドの種類ごとに必要な属性を取得する。例えば「クリップ登録」という描画コマンドからは、識別子（ＣＬＩＰＳＥＴ）、判定規則が取得される。また「塗り」の描画コマンドの場合は、「クリップ登録」と同様に識別子（ＦＩＬＬ）、判定規則、色が取得される。「細線」の場合には、識別子（ＳＴＲＯＫＥ）、色が取得される。「クリップ解除」という描画コマンドからは、何も取得されない。
【００２４】
取得された属性値は、図９に示すレコードを持つ描画属性表に、ＩＤをキーとして登録される。図１０に描画コマンドの種別ごとに、格納されるデータを示してある。図１０（ａ）はクリップ登録の場合のレコードで、種別はＣＬＩＰＳＥＴ、属性１は判定規則である。図１０（ｂ）は塗りの場合のレコードで、種別はＦＩＬＬ、属性１は判定規則、属性２は色である。図１０（ｃ）は細線の場合で、種別はＳＴＲＯＫＥ、属性１は色である。また、ＩＤとさまざまな情報を結び付ける目的で、このレコードには上記取得した属性値以外の情報も付加される。取得した属性値以外の情報については、後ほど詳細に説明する。
【００２５】
描画コマンドの種類が「クリップ登録」と「クリップ解除」の場合には、クリップ検索表が作成される。クリップ検索表は２種類あり、一つめはあるクリップの組でクリップを行うかどうかを判別する表（クリップ状態表）で、二つめはあるクリップの有効範囲を調べる表（クリップ範囲表）である。
【００２６】
クリップ状態表は、ある描画コマンドのＩＤをキーとして検索され、結果としてクリップを行うかどうかが判別できる。クリップ範囲表は、あるクリップのＩＤをキーとして検索され、結果としてクリップ状態表の書換えの範囲を得ることができる。
【００２７】
クリップ検索表について図１１を用いて具体的に説明する。図１１（ａ）に示すように、描画順序を示すＩＤ＝ａで描画種別＝クリップＡ登録、ＩＤ＝ｂで描画種別＝クリップＢ登録、ＩＤ＝ｃで描画種別＝クリップＡ解除、ＩＤ＝ｄで描画種別＝クリップＣ登録、ＩＤ＝ｅで描画種別＝クリップＣ解除、及びＩＤ＝ｆで描画種別＝クリップＢ解除の描画コマンド列があるとする（但し、ａ＜ｂ＜ｃ＜ｄ＜ｅ＜ｆ）。
【００２８】
この描画コマンド列から図１１（ｂ）に示すようなＩＤとクリップ状態の２分木によるクリップ状態表と図１１（ｃ）に示すようなクリップ範囲表が作成される。本例でのクリップ状態表は２分木で作成したが、他の方法により作成してもよい。
【００２９】
図１１（ｂ）において、ルートの［０、Ｅ）は、ＩＤが０以上Ｅ（ＩＤの最後）未満であるＩＤの区間を示している。区間を表す去記「［」は「以上」を、「）」は「未満」を意味するものとし、図１１（ｂ）の各ノードのＩＤの区間表記においても同じ意味で用いるものとする。最下層のノードには、区間データ及び、セットされているクリップの個数、カウンタ値がデータとして格納される。図においては例えば最下層のノード［ａ、ｂ）で区間データを表し、［ａ、ｂ）の左下側にはセットされているクリップの個数１、右下側にはカウンタ値０が格納されている。クリップ状態表の末端ノードのカウンタ値は、塗りつぶし描画処理のときにクリップ領域が新たに内部になったときに増加させ、外部になったとき減少させる。クリップの個数とカウンタの値とが等しくなると、この区間の全てのクリップが内部状態にあることになる。
【００３０】
従って、ＩＤがａ’（但し、ａ＜ａ’＜ｂ）の「塗り」の描画コマンドは、ルート［０、Ｅ）から、ノード［０、ｄ）、［０、ｂ）、［ａ、ｂ）の順に探索することにより、ノード［ａ、ｂ）に格納された個数（この場合１）のクリップ（この場台クリップＡ）だけから影響を受けることが分かる。また例えばＩＤがｄ’（但し、ｄ＜ｄ’＜ｅ）の「塗り」の描画コマンドは、ルート［０、Ｅ）から、ノード［ｄ、Ｅ）、［ｄ、ｆ）、［ｄ、ｅ）の順に探索することにより、ノード［ｄ、ｅ）に格納された個数（この場合２）のクリップ（この場合クリップＢとＣ）から影響を受ける（クリアされているクリップＡには影響されない）ことが分かる。
【００３１】
従って、「クリップ登録」の場合には、クリップ状態表の最下層にあるノード（末端ノード）にデータ（区間データ、クリップの個数、及びカウンタ値）を追加する処理が行われる。但し「クリップ登録」が連続する場合には、ノードは追加する必要はなく区間データのＩＤを変更させてからクリップの個数のデータの値を増加させるだけでよい。
【００３２】
「クリップ解除」の場合には、前区間のノードを終了し、新しい区間を示すノードを追加する。追加したノードのクリップの個数のデータは、前区間のクリップの個数から１減少させたものとなる。「クリップ解除」が連続する場合も、ノードは追加する必要はなくクリップの個数を減少させるだけでよい。
【００３３】
描画ベクター記憶部６とクリップベクター記憶部８とで保持されている各ベクターはスキャンライン順に塗りつぶし・クリップ処理部１０に取り出され、塗りつぶしとクリップ処理が同時に行われる。塗りつぶし・クリップ処理において、必要に応じて描画属性記憶部に保持されているデータが参照される。塗りつぶしとクリップ処理の終了したデータは画像出力部１２から画像出力装置（図示せず）に出力される。ここで、塗りつぶし・クリップ処理部１０は本実施の形態の描画処理装置における中心的役割を有しており、さらにその詳細な説明は後程行うことにする。
【００３４】
次に、本実施の形態における描画処理装置による塗りつぶし・クリップ処理の全体の概略を図１２に示すフローチャートを用いて説明する。
図１２に示す処理の流れは２つのループに大別される。第１のループはステップＳ１０からステップＳ１４までのループで構成される。第２のループはステップＳ１５からステップＳ２３までのループで構成される。
【００３５】
第１のループでは、まず描画データ入力部２が描画コマンド列を取得する（ステップＳ１０）。次に、取得された描画コマンド列のうち一つの描画コマンドを取り出して、ベクター生成部４により当該一つの描画コマンドに付随している全ての点列からベクターが生成される（ステップＳ１１）。描画コマンドの種類に応じて描画ベクター記憶部６、或いはクリップベクター記憶部８のいずれかの対応するベクター記憶部に、作成した全てのベクターを登録する（ステップＳ１２）。次に、描画コマンドから描画属性を取得し、描画コマンドの種類に応じて描画属性記憶部９内に描画属性を登録する。描画コマンド列の全ての描画コマンドに対してステップＳ１４の登録終了になるまでステップＳ１０からステップＳ１３が繰り返される。この第１のループについては図１５に示すフローチャートを用いて後程さらに詳細に説明する。
【００３６】
次に、第２のループとして、まずベクター記憶部６、８に保持されているベクターのうち、処理対象となるスキャンラインにかかるベクターを取り出して、アクティブテーブルヘ登録する（ステップＳ１５）。次に、アクティブテーブルが空であるか調べる（ステップＳ１６）。アクティブテーブルが空である場合には、ステップＳ２３へ移行する。アクティブテーブルが空でなければ、現在のアクティブテーブルに登録されているベクターをスキャンラインの走査方向に従ってソートする（ステップＳ１７）。次にアクティブテーブルからベクターを順次取り出して（ステップＳ１８）、ベクターの種類を判別する（ステップ１９）。判別した結果がクリップベクターの場合は内部判定を行いながらクリップ処理を行う（ステップＳ２０）。判別した結果が描画ベクターの場合は内部判定を行いながら塗りつぶし処理を行う（ステップＳ２１）。一つのスキャンラインの処理が終了した後、アクティブテーブルを更新する（ステップＳ２２）。全てのスキャンラインに対してステップＳ２３で処理終了になるまでステップＳ１５からステップＳ２２が繰り返される。この第２のループの詳細については図２２を用いて後程さらに説明する。
【００３７】
以上が本実施の形態による描画処理装置の塗りつぶし・クリップ処理の全体の概略である。続いて、本実施の形態としての描画処理装置による処理を図１３に示す具体例に基づいてさらに明確且つ十分に説明する。
【００３８】
図１３は、描画コマンドとして２つのクリップが指定され、このクリップから影響を受ける３つの矩形領域を描画した例を示している。まず、描画コマンド「クリップＡ」により、図示の通り３点ＣＡ１、ＣＡ２、ＣＡ３で構成される三角形領域２４が画定される。次に、描画コマンド「クリップＢ」により、３点ＣＢ１、ＣＢ２、ＣＢ３より構成される三角形領域２６が画定される。本具体例では点ＣＡ１、ＣＡ２、及びＣＢ３のＹ座標値は同一であり、点ＣＡ３、ＣＢ１、及びＣＢ２のＹ座標値も同一である。また、点ＣＡ１とＣＢ１、ＣＡ３とＣＢ３、ＣＡ２とＣＢ２のＸ座標値はそれぞれ同一である。従って、２つの三角形領域２４、２６とで菱形領域２８が形成される。この菱形領域２８がクリップ領域となる。
【００３９】
次に、描画コマンド「描画領域Ａ」、「描画領域Ｂ」、「描画領域Ｃ」によりそれぞれ異なる位置に異なる色で矩形領域３０、３２、３４が順に塗りつぶし処理される。
クリップ処理された描画結果として、内部に矩形領域３０、３２、３４で指定された色で塗りつぶされた菱形領域３６が得られる。
【００４０】
図１３の描画処理における描画コマンド列を図１４に示す。図１４に示した描画コマンド列は、７つの描画コマンドから構成される。描画コマンド「クリップＡ」は、描画順序を表すＩＤ＝ＩＤ１、描画コマンド種類が「クリップ登録」であることを示す識別子ＣＬＩＰＳＥＴ、内部判定のための判定規則＝ＮＺ、クリップ形状を決定する点の位置情報ＣＡ１、ＣＡ２、ＣＡ３とから構成されている。描画コマンド「クリップＢ」も同様に、ＩＤ＝ＩＤ２、識別子ＣＬＩＰＳＥＴ、判定規則＝ＮＺ、点の位置情報ＣＢ１、ＣＢ２、ＣＢ３とから構成されている。描画コマンド「描画領域Ａ」は、ＩＤ＝ＩＤ３、描画コマンド種類が「塗り」であることを示す識別子ＦＩＬＬ、判定規則＝ＮＺ、点の位置情報ＤＡ１、ＤＡ２、ＤＡ３、ＤＡ４と、さらに塗りつぶしの色情報「色１」から構成されている。描画コマンド「描画領域Ｂ」も同様に、ＩＤ＝ＩＤ４、識別子ＦＩＬＬ、判定規則＝ＮＺ、色情報「色２」、点の位置情報ＤＢ１、ＤＢ２、ＤＢ３、ＤＢ４から構成されている。描画コマンド「描画領域Ｃ」は、ＩＤ＝ＩＤ５、識別子ＦＩＬＬ、判定規則＝ＮＺ、色情報「色３」、点の位置情報ＤＣ１、ＤＣ２、ＤＣ３、ＤＣ４から構成されている。
【００４１】
この図１４に示した描画コマンド列を用いて、本実施の形態における描画処理装置の処理手順の詳細な説明を行う。
初めに図１２で概説した第１のループの詳細を図１５を用いて説明する。
まず、画像データ入力部２に入力された描画コマンド列の一つの描画コマンドから、ＩＤと描画コマンドの種別を取り出す（ステップＳ３０）。次に描画コマンドの種別を判別し（ステップＳ３１）、クリップ以外の場合はステップＳ３２、クリップ登録の場合はステップＳ３６、クリップ解除の場合はステップＳ４０へ分岐する。
【００４２】
クリップ以外の場合には、描画コマンドに付随する全ての点列に対して２点を取り出して描画ベクターを作成する（ステップＳ３２）。ステップＳ３２で作成される描画ベクターは、前述の図６に示したような形式で表現されるベクターである。すなわち、図７に示した座標系の向きを考慮し、ベクターの「向き」を算出する。座標系のＹ軸が図面垂直下方向に正であるとすると、取り出した２点のうちの始点の方が大きい座標値を持っている場合には向きが反転されて−１となる。例として２点（２００，２００）−（１００，１００）が与えられた場合には、Ｘ切片として１００、向きが−１となる（図７（ｂ）参照）。
【００４３】
このようにして作成された描画ベクターは描画ベクターテーブルに登録される（ステップＳ３３）。描画コマンド（クリップを除く）の全ての点列を処理するまでステップＳ３２及びステップＳ３３が繰り返される（ステップＳ３４）。点列の処理が完了した後の描画ベクターテーブルの状態を図１６に示す。なお、Ｘ座標に平行なベクターは処理に関係しないので登録しなくてもよい（ここでは登録しない）。
【００４４】
次に、描画コマンドに付随する描画属性値を取り出して描画属性表に登録する（ステップＳ３５）。ステップＳ３５で登録される描画属性は、前述の図９に示したような形式で表現されるレコードである。すなわち、描画コマンドが塗りの場合には図１０（ｂ）のレコードとなり、描画コマンドが細線の場合には図１０（ｃ）のレコードとなる。
【００４５】
次に、ステップＳ３１でクリップ登録と判断された場合には、ステップＳ３６に移行し、描画コマンドに付随する全ての点列に対して２点を取り出して、図６に示すベクター表現のクリップベクターを作成する（ステップＳ３６）。作成されたクリップベクターは、クリップベクターテーブルに登録する（ステップＳ３７）。クリップ登録の描画コマンドの全ての点列を処理するまでステップＳ３６とステップＳ３７が繰り返される（ステップＳ３８）。その後で、クリップ登録のＩＤをもとに、クリップ状態表へノードを追加する（ステップＳ３９）。次に、描画コマンドに付随する描画属性値を取り出して描画属性表に登録する（ステップＳ４０）。点列の処理が完了した後のクリップベクターテーブルの状態を図１７に示す。
【００４６】
図１６及び図１７に示した描画ベクターテーブル及びクリップベクターテーブルを図１８を用いてより詳細に説明する。図１８は、図１３及び図１４の具体例に基づくスキャンラインとベクターとの関係を示している。図中縦方向には複数のスキャンラインが並列しており、各ベクターの始点及び終点に関係するスキャンラインに上方からＹ１〜Ｙ８の番号を付している。例えば、描画領域Ｂを構成する２つの描画ベクター（ＤＢ４、ＤＢ１）及び（ＤＢ３、ＤＢ２）は、スキャンラインＹ１に結び付けられている。ベクターは、ベクターの「向き」を考慮して必ず下向きに補正された状態でベクターの開始点のＹ座標に結び付けられるので、ベクターの始点ＤＢ２、終点ＤＢ３の描画ベクター（ＤＢ３、ＤＢ２）はスキャンラインＹ１に結び付けられる。同様にして描画領域Ａ、Ｃの描画ベクターがそれぞれスキャンラインＹ３、Ｙ５に結び付けられている。
一方、クリップベクターも同様にベクターの「向き」を考慮してスキャンラインＹ２に結び付けられている。
【００４７】
なお、図１６の描画ベクターテーブルにあっては、スキャンラインＹ２、Ｙ４及びＹ６〜Ｙ８のように、図１７のクリップベクターテーブルにあってはスキャンラインＹ１及びＹ３〜Ｙ８のように、共にベクターとの交点を有するスキャンラインの情報も持たせているが、この情報はなくてもよい。或いは逆に、全スキャンラインのデータを配列としてテーブルに保持するようにしてもよい。
【００４８】
次に、ステップＳ３１でクリップ解除と判断された場合には、ステップＳ４１に移行し、クリップ解除コマンド自身のＩＤをもとに、クリップ状態表の前区間のノードを終了し、新しい区間のノードを追加する（ステップＳ４１）。そして、クリップ解除コマンド自身のＩＤとクリップ解除コマンドに付随する解除するクリップのＩＤをもとに、クリップ範囲表に、解除するクリップのＩＤのノードを追加し、クリップ状態表の関連する末端ノードと結び付ける（ステップＳ４２）。すべての描画コマンドを処理した後の、すなわち、第１のループが終了した段階でのクリップ状態表を図１９に、クリップ範囲表を図２０に示す。
【００４９】
図１９に示したように、ＩＤ１からＩＤ５までの区間は、２つのクリップから影響を受けることを表しており、カウンタ値によってこの区間のクリップの内部状態を調べることができる。図２０に示したように、クリップＡとクリップＢは、ともにクリップ状態表のＩＤ１からＩＤ５までの区間に影響を与えることを表している。このように、クリップ状態表は、描画コマンドのクリップ状態を簡単に調べることができ、クリップ範囲表はあるクリップの内部状態が変化したときに、どの区間に影響を与えるかを簡単に調べることができる。
以上の処理を、描画コマンド列の全ての描画コマンドの処理が終了するまで繰り返す（ステップＳ４３）。
【００５０】
第１のループの最後の処理として、ステップＳ４４において、描画属性表に付加情報を追加する。図２１に、すべての描画コマンドを処理した後の、描画属性のレコードを示してある。図２１にあるように、図１０に示した各コマンドの種類ごとのレコードにその他の情報として、塗りと細線の場合にはクリップ状態表へのリンク、クリップ登録の場合にクリップ範囲表へのリンクを追加したものである。
【００５１】
図２１において、ＩＤ１のクリップＡのクリップ登録に対応するレコードは、種別（ＣＬＩＰＳＥＴ）、判定規則（ＮＺ）、そして、付加情報としてクリップＡのクリップ範囲表へのリンクが追加されている。ＩＤ２のクリップＢのクリップ登録に対応するレコードは、同様に、種別（ＣＬＩＰＳＥＴ）、判定規則（ＮＺ）、クリップＢのクリップ範囲表へのリンクである。ＩＤ３の描画領域Ａに対応するレコードは、種別（ＦＩＬＬ）、判定規則（ＮＺ）、色（色１）、そして、付加情報としてクリップ状態表（ＩＤ１からＩＤ５）へのリンクが追加されている。ＩＤ４の描画領域Ｂに対応するレコードは、同様に、種別（ＦＩＬＬ）、判定規則（ＮＺ）、色（色２）、クリップ状態表（ＩＤ１からＩＤ５）へのリンクである。ＩＤ５の描画領域Ｃに対応するレコードは、同様に、種別（ＦＩＬＬ）、判定規則（ＮＺ）、色（色３）、クリップ状態表（ＩＤ１からＩＤ５）へのリンクである。
【００５２】
このように、複数の描画ベクターと複数のクリップベクターが存在する場合であってもそれらの対応関係を容易に得ることができるようになる。
以上のようにして、描画コマンドの上記処理が終了することにより、図１２で説明した第１のループが終了する。
【００５３】
次に図１２の第２のループについて図２２を用いて詳細に説明する。図２２のフローチャートにおいて、まず、全てのスキャンラインが処理されたかどうかが判断される（ステップＳ５０）。全てのスキャンラインについての処理を終了したら第２のループが終了し、本実施の形態における描画処理装置によるクリップ処理及び塗りつぶし処理が終了する。
【００５４】
処理すべきスキャンラインがまだ残っている場合にはステップＳ５１において、現在のスキャンラインにかかるベクターを、図１６に示した描画ベクターテーブル及び、図１７に示したクリップベクターテーブルからそれぞれ取得してアクティブテーブルに格納する。クリップベクターはアクティブテーブル内のクリップテーブルに、描画ベクターはアクティブテーブル内の描画テーブルに登録される。
【００５５】
次にアクティブテーブルが空であるかどうかが判断される（ステップＳ５２）。図１６、図１７の場合のようにスキャンラインＹ１〜Ｙ８にベクターが存在し、それ以外のスキャンラインにはベクターが存在しないとすれば、Ｙ１〜Ｙ８以外のスキャンラインについてのアクティブテーブルは空となる。アクティブテーブルが空であれば、当該スキャンラインには何もデータが存在しないことになるので、空のスキャンラインを生成して本ループの最初であるステップＳ５０に戻る（ステップＳ５８）。
【００５６】
次に、アクティブテーブルにベクターが存在している場合には、現在処理対象としているスキャンラインで新たなベクターが加わったかどうかにかかわらず、当該スキャンラインの全ベクターのソートを行う（ステップＳ５３）。このソートは、スキャンライン間でベクターが交差するような場合には、当該スキャンラインでのベクターの状態が前スキャンラインでのベクターの状態とは異なるものとなるので、改めて当該スキャンラインでの全ベクターのソートを行って当該スキャンラインにかかるベクターを所定の順序に並べ替えるために行われる。
【００５７】
ソートは、現在のアクティブテーブルに存在する全てのベクターを、描画テーブル、クリップテーブル共にソートするようにして行われる。また、スキャンラインの走査方向に、Ｘ座標の座標値の小さい順にソートするようにしている。本実施の形態ではスキャンライン毎に必ずアクティブテーブル内の全ベクターのソートを実行しているが、例えば、ベクターの交差情報に基づいてソートするかしないかを判断するようにしてもよい。
【００５８】
ソートの例として、図１８に示したスキャンラインのうちスキャンラインＹ３のアクティブテーブルにベクターを登録しソートを実行した直後の状態を図２３に示す。描画テーブルは、描画領域Ｂの中に描画領域Ａが存在していることを表している。クリップテーブルは、クリップＡの中にクリップＢが存在していることを表している。
【００５９】
次に、スキャンライン内でのベクターの共通の情報を初期化する（ステップＳ５４）。スキャンライン内での共通の情報とは、図２４で示した内部判定テーブルの情報、及び描画状態表の情報である。
【００６０】
描画状態表は、描画図形の内部判定を行った結果として、現在、どの図形が内部の状態にあるかを保持するために設けられている。これについての詳しい説明は後述する。
【００６１】
ステップＳ５４でのベクターの共通情報の初期設定が終わった後、スキャンラインの走査方向に塗りつぶしとクリップ処理を行う（ステップＳ５５）。この塗りつぶし・クリップ処理の全体の流れは図２６を用いて後程詳述する。
【００６２】
一つのスキャンラインの処理が終了すると、次のスキャンラインに備えてアクティブテーブルの更新処理を行う（ステップＳ５６）。アクティブテーブルの更新処理の流れを図２５を用いて説明する。まず、アクティブテーブルから描画ベクターと、クリップベクターとを取得する（ステップＳ６０）。ベクターが取得されたかどうかを判断し（ステップＳ６１）、取得されなければ処理を終了して元に戻る。ベクターが取得されれば、取得されたベクターのＹ変位が１より大きいかどうかを判断する（ステップＳ６２）。ベクターのＹ変位が１より大きければ、次のスキャンラインは当該ベクターに影響される可能性があるので、当該べクターのＸ値にＸ変位値を加えた値をＸ値の更新値とし、Ｙ変位から１を減した値をＹ変位の更新値とする（ステップＳ６４）。Ｙ変位の更新値が０であれば当該ベクターは、次のスキャンラインに影響を及ぼさないのでアクティブテーブルから削除する（ステップＳ６３）。
【００６３】
以上のステップが当該スキャンラインの全ての描画ベクター、クリップベクターについて行われる。
アクティブテーブルの更新が終了すると、次に当該スキャンラインの出力を行う（ステップＳ５７）。以上が第２のループでの処理であり、全てのスキャンラインについてこの処理が行われる。
【００６４】
次に、塗りつぶし・クリップ処理のより詳細な流れを図２６を用いて説明する。まず初めに、アクティブテーブルから順次ベクターを取得する（ステップＳ７０）。ここで、ベクターの取得の際にクリップベクターと描画ベクターとが同一のＸ座標値を有している場合には、クリップベクターを先に取得するものとする。
【００６５】
アクティブテーブルに取得すべきベクターが無くなったら、スキャンラインの残りの領域を空白として処理を終了する（ステップＳ８０）。
クリップベクター或いは描画ベクターがある場合には、当該ベクターの内部判定処理を行う（ステップＳ７２）。内部判定処理の詳細は図３１を用いて後程詳述する。次に内部判定処理の結果を元に、３つの場合に分岐する（ステップＳ７３）。まず、内部判定処理結果が「領域の継続」の場合には、状態の変化はないのでステップＳ７０の処理の最初に戻る。「領域の開始」の場合には、さらに当該ベクターが描画ベクターかクリップベクターかをＩＤを用いて図２１のテーブルを参照することにより判断し（ステップＳ７４）、クリップベクターの場合には、図２７に示すクリップ開始処理を行い（ステップＳ７５）、描画ベクターの場合には、図２８に示す描画開始処理を行う（ステップＳ７６）。「領域の終了」の場合にも、同様に描画ベクターかクリップベクターかを判断し（ステップＳ７７）、クリップベクターの場合には、図３０に示すクリップ終了処理を行い（ステップＳ７９）、描画ベクターの場合には、図２９に示す描画開始処理を行う（ステップＳ７８）。図２７乃至図３０に示す各処理の詳細は後述する。
【００６６】
以上の処理が終了すると当該スキャンライン内の次のベクターをアクティブテーブルから取得するためステップＳ７０に戻る。以上のようにして、塗りつぶし・クリップ処理が行われる。
【００６７】
次に、ステップＳ７２でのベクターの内部判定処理の詳細を図３１を用いて説明する。まず、ベクターのＩＤから、このベクターで構成される図形の内部判定規則を図２１のテーブルから取得する（ステップＳ９０）。判定規則の種類がＮＺ（ワインディング規則）であればステップＳ９２へ移行し、ＥＯ（奇偶規則）であればステップＳ１００へ移行する（ステップＳ９１）。
【００６８】
判定規則がＮＺであれば、ベクターのＩＤから内部判定テーブル（図２４）の値を取得し（ステップＳ９２）、当該値が０であるかないかを判断する（ステップＳ９３）。値が０であれば当該ベクターで構成される図形は必ず内部になる。従って、図２４の内部判定テーブルの当該ベクターのＩＤの位置に格納されている値にベクターの向きを加えてから（ステップＳ９４）、「領域の開始」として戻る（ステップＳ９５）。取り出した値が０でない場合には、図２４の内部判定テーブルの当該ベクターのＩＤの位置にある値にベクターの向きを加え（ステップＳ９６）、加えた結果が０であるかどうかを判断する（ステップＳ９７）。加えた結果が０であれば、「領域の終了」として戻る（ステップＳ９８）。加えた結果が０以外の場合は、引き続き内部状態が継続するので「領域の継続」として戻る（ステップＳ９９）。
【００６９】
ステップＳ９１で判定規則がＥＯであると判断されると、当該ベクターのＩＤから内部判定テーブル（図２４）の値を取得し、当該値を１だけ増加させてから２の剰余を求める（ステップＳ１００）。２の剰余の値が１であれば判定結果は奇数となり（ステップＳ１０１）、図形が内部になるので「領域の開始」として戻る（ステップＳ１０３）。２の剰余が０であれば判定結果は偶数となり図形の外部となるので「領域の終了」として戻る（ステップＳ１０２）。このようにして、図２６でのステップＳ７２の内部判定処理が行われる。
【００７０】
次に、内部判定処理の結果に基づくクリップ処理及び塗りつぶし処理の詳細を図２７乃至図３０を用いて説明する。
初めに、クリップ処理及び塗りつぶし処理の両方に共通して用いられる描画状態表と、描画判定処理について説明する。
【００７１】
まず、描画状態表を図３２を用いて説明する。描画状態表は、現在内部状態にある描画図形（描画ベクター）を保持する機能と、現在処理中のスキャンラインのどこまでの描画が完了したかの情報を保持する機能とを有している。図３２に示すように、描画状態表は「内部状態」、「登録待ち状態」、「描画開始位置」から構成される。「内部状態」には、図形（描画ベクター）及びその図形が影響を受けるクリップの全てが内部状態にある場合に図形が登録される。「登録待ち状態」には、図形は内部状態にあるが、その図形が影響を受けるクリップの一部または全部が内部状態にはなっていない場合に図形が登録される。「描画開始位置」には、現在処理中のスキャンラインのこれから塗りつぶしが行われるＸ座標値が保持される。従って、「描画開始位置」に格納されているＸ座標値より小さいＸ座標値の領域はすでに塗りが確定した領域である。
【００７２】
次に描画判定処理について図３３を用いて説明する。描画判定処理は、塗りを行うか行わないかを判断する処理であり、図２７乃至図３０に示した塗りつぶし・クリップ処理の各処理で共通に使用されるルーチンである。描画判定処理のルーチンではあらかじめ「比較用のＩＤ」と「比較用のＸ座標値」が渡されている。まずステップＳ１１０で、図３２の描画状態表に「内部状態」の図形が登録されているか否かを調べる。内部状態の図形がなければ、描画開始位置から比較用のＸ座標値−１まで何も塗らない領域であるので、「描画開始位置」を比較用のＸ座標値に設定して処理を終了する（ステップＳ１１４）。このとき、当初の描画開始位置から比較用のＸ座標値まで透明を出力するようにしてもよい。
【００７３】
描画状態表の「内部状態」に図形があれば、「内部状態」にある最大のＩＤと比較用のＩＤとを比較する（ステップＳ１１１）。内部状態にある最大ＩＤの方が比較用ＩＤより大きければ、何もせずに処理を終了する。つまり、既に内部状態にある図形のうち最後に描画された図形が、比較用の図形よりも上に塗られているので何も処理する必要が生じないのである。「内部状態」の最大ＩＤの方が比較用ＩＤより小さいか等しければ、さらに描画状態表に登録されている「描画開始位置」と比較用のＸ座標値−１を比較し、描画開始位置の方が大きいか等しい場合には何もしないで処理を終了する（ステップＳ１１２）。描画開始位置の方が比較用Ｘ座標値−１より小さければ、描画開始位置から比較用のＸ座標値−１まで内部状態ベクターの最大ＩＤの色で塗りを行う（ステップＳ１１３）。そして、描画開始位置を比較用のＸ座標値に設定して処理を終了する（ステップＳ１１４）。
【００７４】
さて、以上説明した描画状態表（図３２）及び描画判定処理（図３３）に基づいて、クリップ及び描画それぞれの開始、終了処理について説明する。
【００７５】
始めにクリップ開始処理を図２７を用いて説明する。まず当該クリップベクターのＩＤを用いて、描画属性表（図２１）から当該クリップベクターが関係する範囲を取得し、すべての範囲に対してクリップ状態表（図１９）のカウンタを１だけ増加させる（ステップＳ１２０）。次に、描画状態表の「登録待ち状態」にある描画ベクターのＩＤが、ＩＤの大きい順に取り出される（ステップＳ１２１）。「登録待ち状態」に描画ベクターがなければクリップ開始処理を終了する（ステップＳ１２２）。
【００７６】
ステップＳ１２２で「登録待ち状態」の描画ベクターがあった場合には、当該描画ベクターのＩＤを用いて、描画属性表の対応するレコードにあるクリップ状態表へのリンク先を調べ、当該ＩＤが属する区間のクリップの個数とカウンタの値が等しいかどうかを調べる（ステップＳ１２３）。ステップＳ１２４で当該区間のクリップの個数とカウンタの値が異なる場合には、描画状態表から「登録待ち状態」の描画ベクターを取り出す処理（ステップＳ１２１）に戻る。
【００７７】
ステップＳ１２４で描画ベクターのＩＤが属する区間のクリップの個数とカウンタの値が等しければ、ステップＳ１２５において、前述の図３３の描画判定処理を行う。ここで描画判定処理に用いられる比較用ＩＤは「登録待ち状態」にある描画ベクターのＩＤである。比較用のＸ座標値はこのクリップベクターのＸ座標値である。さらに図３２の描画状態表の「登録待ち状態」から「内部状態」ヘこの描画ベクターのＩＤを移動させる（ステップＳ１２６）。そして、描画状態表から「登録待ち状態」の描画ベクターを取り出す処理（ステップＳ１２１）に戻る。以上のようにしてクリップ開始処理が行われる。
【００７８】
次に、描画開始処理を図２８を用いて説明する。まず、当該描画ベクターのＩＤを用いて、描画属性表（図２１）の対応するレコードにあるクリップ状態表へのリンク先を調べる（ステップＳ１３０）。このとき、この描画ベクターのＩＤが属する区間のクリップ個数とカウンタ値が等しければ（ステップＳ１３１）図形として描画できる状態にあるので、塗りを行うかどうかの描画判定処理を行う（ステップＳ１３２）。描画判定処理における比較用ＩＤは当該描画ベクターのＩＤであり、比較用Ｘ座標値は当該描画ベクターのＸ座標値である。最後に、ステップＳ１３３で、描画状態表（図３２）の「内部状態」ヘ当該描画ベクターのＩＤを新たに登録する。ステップＳ１３１でクリップ個数とカウンタ値が等しくなければ、描画状態表の「登録待ち状態」ヘ当該描画ベクターのＩＤを登録する（ステップＳ１３４）。以上のようにして描画開始処理が行われる。
【００７９】
次に、描画終了処理を図２９を用いて説明する。まず、描画状態表（図３２）を調べて当該描画ベクターが「内部状態」にあるかどうかを調べる（ステップＳ１４０）。「内部状態」になければ「登録待ち状態」にあるので、描画状態表の「登録待ち状態」から当該描画ベクターのＩＤを削除して処理を終了する（ステップＳ１４３）。当該描画ベクターが「内部状態」にある場合には、図３３の描画判定処理を行う（ステップＳ１４１）。判定用ＩＤは当該描画ベクターのＩＤであり、判定用Ｘ座標値は当該描画ベクターのＸ座標値である。次に、描画状態表の「内部状態」から当該描画ベクターのＩＤを削除して処理を終了する（ステップＳ１４２）。以上のようにして描画終了処理が行われる。
【００８０】
次に、クリップ終了処理を図３０を用いて説明する。まず、当該クリップベクターのＩＤを用いて、描画属性表（図２１）から当該クリップベクターが関係する範囲を取得し、すべての範囲に対してクリップ状態表（図１９）のカウンタを１だけ減じる（ステップＳ１５０）。
【００８１】
次に、描画状態表の「内部状態」にある描画ベクターのＩＤを、ＩＤの大きい順に取り出す（ステップＳ１５１）。「内部状態」に描画ベクターがなければクリップ終了処理を終了する（ステップＳ１５２）。ステップＳ１５１で「内部状態」の描画ベクターがあった場合には、当該描画ベクターのＩＤを用いて、描画属性表の対応するレコードにあるクリップ状態表へのリンク先を調べ、当該ＩＤが属する区間のクリップの個数とカウンタの値が等しいかどうか調べる（ステップＳ１５３）。ステップＳ１５４で当該区間のクリップの個数とカウンタの値が等しい場合には、描画状態表から「内部状態」の描画ベクターを取り出す処理（ステップＳ１５１）に戻る。ステップＳ１５４で描画ベクターのＩＤが属する区間のクリップの個数とカウンタの値とが異なる場合には、ステップＳ１５５において描画判定処理を行う。
【００８２】
描画判定処理に用いられる比較用ＩＤは「登録待ち状態」にある描画ベクターのＩＤである。比較用のＸ座標値はこのクリップベクターのＸ座標値である。さらに描画状態表の「内部状態」から「登録待ち状態」ヘこの描画ベクターのＩＤを移動させる（ステップＳ１５６）。そして、描画状態表から「内部状態」の描画ベクターを取り出す処理（ステップＳ１５１）に戻る。以上のようにしてクリップ終了処理が行われる。
【００８３】
次に、塗りつぶし・クリップ処理の具体例として、図１８に示したＹ３のスキャンラインに着目し、その描画状態表の変化を図３４及び図３５を用いて説明する。まず、図３４（ａ）において、取得ベクターとして描画ベクター（ＤＢ４、ＤＢ１）が得られ、内部判定は図２４のワーク領域から０が読み出されるので描画開始となる。しかし、クリップ状態はまだ１つもセットされていないので、描画状態表の「登録待ち状態」にＩＤ４が登録される。描画状態表の「描画開始位置」は０である。クリップ状態表は図１９のように表されている。すなわち、ＩＤの区間がＩＤ１からＩＤ５までであり、この区間が２つのクリップにより影響を受けることを表している。但し、カウンタ値はまだ０となっている。
【００８４】
次に、図３４（ｂ）で取得ベクターとして描画ベクター（ＤＡ４、ＤＡ１）が得られるが、クリップ状態はまだ１つもセットされておらず描画ベクター（ＤＢ４、ＤＢ１）と状況は変わらないため、描画状態表の「登録待ち状態」にＩＤ３がＩＤ４の下位に登録される。
【００８５】
次に、図３４（ｃ）で取得ベクターとしてクリップベクター（ＣＡ１、ＣＡ３）が得られ、内部判定はワーク領域から０が読み出されるのでクリップ開始となる。従って、クリップ状態表のカウンタの値が１になる。登録待ちのＩＤを用いてクリップ状態を調べると、まだ、１個のクリップしか開始されていないので、描画状態は変わらない。
【００８６】
次に、図３４（ｄ）で取得ベクターとしてクリップベクター（ＣＢ３、ＣＢ１）が得られ、内部判定はワーク領域から０が読み出されるのでクリップ開始となる。従って、カウンタ値が２となる。「登録待ち状態」の描画ベクターのＩＤを用いて描画属性表の対応するレコードからクリップ状態表へのリンクをたどると、ＩＤ４とＩＤ３が条件を満たすので、ＩＤ４とＩＤ３共に描画状態表の「内部状態」ヘ移動される。ＩＤ４の描画判定処理のときに、描画状態表の「描画開始位置」は（ＤＢ４、ＤＢ１）のＹ３におけるＸ座標値（ここではＸ１とする）がセットされる。ＩＤ３の描画判定のときには、すでに大きいＩＤであるＩＤ４が内部状態にあるため、内部状態に移動するだけである。
【００８７】
次に、図３５（ａ）で取得ベクターとしてクリップベクター（ＣＢ３、ＣＢ２）が得られ、内部判定は最終的に０となり、クリップ終了となる。従って、カウンタ値が１となる。「内部状態」の描画ベクターのＩＤを用いて描画属性表の対応するレコードからクリップ状態表へのリンクをたどると、ＩＤ４とＩＤ３が条件を満たすので、ＩＤ４とＩＤ３共に「登録待ち状態」ヘ移動される。ＩＤ４の描画判定処理のときに、ＩＤ４の色でＸ座標値Ｘ１からＸ２−１までの範囲が塗られる（但し、Ｘ２は（ＣＢ３、ＣＢ２）のＹ３におけるＸ座標値であるとする）。「描画開始位置」にはＸ２がセットされる。ＩＤ３の描画判定のときには、「描画開始位置」がＸ２であるため、「登録待ち状態」に移動されるだけである。
【００８８】
次に、図３５（ｂ）で取得ベクターとしてクリップベクター（ＣＡ２、ＣＡ３）が得られ、内部判定は最終的に０になり、クリップ終了となる。従って、カウンタが０となる。「内部状態」に変化はない。
【００８９】
次に、図３５（ｃ）で取得ベクターとして描画ベクター（ＤＡ３、ＤＡ２）が得られ、内部判定は最終的に０になり、描画終了となる。このベクターは「内部状態」にないので、「登録待ち状態」から削除する。
【００９０】
次に、図３５（ｄ）て取得ベクターとして描画ベクター（ＤＢ３、ＤＢ２）が得られ、内部判定は最終的に０になり、描画終了となる。このベクターは「内部状態」にないので、「登録待ち状態」から削除する。
【００９１】
このようにして、Ｘ座標値Ｘ１からＸ２−１の領域がＩＤ４の色で塗られることになる。
【００９２】
以上の通り、描画状態表と描画属性表を用いる本実施の形態における描画処理装置によれば、従来別ステップにて行われていた複数のクリップ処理と塗りつぶし処理を同時に行うことができるようになり、且つ処理時間に長時間を要していたマージ処理を省略することができるようになる。
【００９３】
本発明は、上記実施の形態に限らず種々の変形が可能である。
例えば、上記実施の形態においては、描画ベクター記憶部とクリップベクター記憶部を備えていたが、これらを統合させて一つのベクター記憶部とすることももちろん可能である。
【００９４】
また、アクティブテーブル内をソートする際に、スキャンラインの走査方向にＸ座標の座標値の小さい順にソートしたが、これに限らず、使用した座標系や画像出力装置の走査方向に基づいて別のソートの方法を用いることも可能である。
【００９５】
また、描画領域とクリップ領域の情報を１ページ分蓄積してから上記実施の形態で示した処理を行うことにより、１ページ分のクリップと描画領城の塗りつぶし処理を同時に行うようにすることももちろん可能である。
【００９６】
【発明の効果】
以上の通り、本発明によれば、クリップ領域が複数の任意形状からなるクリップ処理を、塗りつぶし処理と同時に高速に行うことができるようになる。
【図面の簡単な説明】
【図１】本発明の一実施の形態による描画処理装置の構成を示すブロック図である。
【図２】描画コマンドの構成を示す図てある。
【図３】描画コマンドのコマンド種別を説明する図である。
【図４】描画コマンドの内部判定規則の種類を示す図である。
【図５】内部判定の規則を説明する図である。
【図６】ベクター生成部４で生成されるベクターの説明図である。
【図７】図６に示すベクターを具体的に説明する図である。
【図８】コマンドの種別ごとの描画属性の種類を示す図である。
【図９】描画属性記憶部９で管理される描画属性の説明図である。
【図１０】描画コマンドの種別ごとの描画属性を説明する図である。
【図１１】クリップ状態表とクリップ範囲表を説明する図である。
【図１２】本発明の一実施の形態における描画処理装置による塗りつぶし・クリップ処理の全体の流れを説明する図である。
【図１３】本発明の一実施の形態における描画処理装置による塗りつぶし・クリップ処理の具体例を示す図である。
【図１４】図１３に示す描画処理における描画コマンド列を示す図である。
【図１５】図１２における第１のループを詳細に説明する図てある。
【図１６】点列の処理が完了した後の描画ベクターテーブルの状態を示す図である。
【図１７】点列の処理が完了した後のクリップベクターテーブルの状態を示す図である。
【図１８】図１３に示す具体例に対応させた、スキャンラインとベクターの関係を示す図である。
【図１９】図１３に示す具体例に対応させた、クリップ状態表を説明する図である。
【図２０】図１３に示す具体例に対応させた、クリップ範囲表を示す図である。
【図２１】図１３に示す具体例に対応させた、描画属性表を示す図である。
【図２２】図１２における第２のループを詳細に説明する図である。
【図２３】アクティブベクターテーブルを説明する図である。
【図２４】塗りつぶし・クリップ処理を行う際に図形の内部状態を判定するために用いる内部判定テーブルを説明する図である。
【図２５】図２２に示すアクティブテーブル更新処理をより詳細に説明する図である。
【図２６】図２２に示す塗りつぶし・クリップ処理をより詳細に説明する図である。
【図２７】図２６に示すクリップ開始処理をより詳細に説明する図である。
【図２８】図２６に示す描画開始処理をより詳細に説明する図である。
【図２９】図２６に示す描画終了処理をより詳細に説明する図である。
【図３０】図２６に示すクリップ終了処理をより詳細に説明する図である。
【図３１】図２６に示す内部判定処理をより詳細に説明する図である。
【図３２】描画状態表を説明する図である。
【図３３】描画判定処理を詳細に説明する図である。
【図３４】図１６のＹ３スキャンラインにおける描画状態表の変化を説明する図である。
【図３５】図１６のＹ３スキャンラインにおける描画状態表の変化を説明する図である。
【符号の説明】
２  描画データ入力部
３  描画データ判別部
４  ベクター生成部
５  描画属性処理部
６  描画ベクター記憶部
８  クリップベクター記憶部
９  描画属性記憶部
１０  塗りつぶし・クリップ処理部
１２  画像出力部
２０  スキャンライン
２２  図形
２４、２６  三角形領域
２８  菱形領域
３０、３２、３４  矩形領域
３６  菱形領域
【図１】
0003617225.tif 000002
【図２】
0003617225.tif 000003
【図３】
0003617225.tif 000004
【図４】
0003617225.tif 000005
【図５】
0003617225.tif 000006
【図６】
0003617225.tif 000007
【図７】
0003617225.tif 000008
【図８】
0003617225.tif 000009
【図９】
0003617225.tif 000010
【図１０】
0003617225.tif 000011
【図１１】
0003617225.tif 000012
【図１２】
0003617225.tif 000013
【図１３】
0003617225.tif 000014
【図１４】
0003617225.tif 000015
【図１５】
0003617225.tif 000016
【図１６】
0003617225.tif 000017
【図１７】
0003617225.tif 000018
【図１８】
0003617225.tif 000019
【図１９】
0003617225.tif 000020
【図２０】
0003617225.tif 000021
【図２１】
0003617225.tif 000022
【図２２】
0003617225.tif 000023
【図２３】
0003617225.tif 000024
【図２４】
0003617225.tif 000025
【図２５】
0003617225.tif 000026
【図２６】
0003617225.tif 000027
【図２７】
0003617225.tif 000028
【図２８】
0003617225.tif 000029
【図２９】
0003617225.tif 000030
【図３０】
0003617225.tif 000031
【図３１】
0003617225.tif 000032
【図３２】
0003617225.tif 000033
【図３３】
0003617225.tif 000034
【図３４】
0003617225.tif 000035
【図３５】
0003617225.tif 000036