(57)【特許請求の範囲】
【請求項１】
図形の描画処理を行う図形処理装置において、
図形の描画要素やクリップ要素を記述するベクター情報を、前記描画要素やクリップ要素を構成するベクターの形状を多角形近似した直線ベクター情報に変換し、前記直線ベクター情報中に含まれる各直線ベクターをベクター開始スキャンライン座標値に基づいてソートして該各直線ベクターの方向、傾き、および横切るスキャンライン数、またはそれらと等価なデータを含む情報によって構成されるディスプレイリストを生成するディスプレイリスト生成手段と、
前記ディスプレイリストを蓄積するディスプレイリスト格納手段と、
クリップ要素と描画要素を表現するディスプレイリストについて、クリップ要素による描画要素のクリップ処理を実行するクリップ処理手段と、
描画領域に重なりを有する複数のディスプレイリストから、前記描画領域の重なりを除去した新たなディスプレイリストを生成する重なり除去手段と、
前記ディスプレイリストの表現する図形を描画するディスプレイリスト描画手段とを有し、
前記ディスプレイリスト生成手段によって生成された、描画要素を表わすディスプレイリストと、当該描画要素の描画領域を制限するクリップ要素を表わすディスプレイリストとをマージ処理し、描画要素とクリップ要素とが混在したディスプレイリストを生成するマージ処理手段をさらに有し、前記マージ処理手段は、描画要素を表わす前記ディスプレイリストと、クリップ要素を表わす前記ディスプレイリストについて、それぞれの外接矩形から少なくともその共通Ｙ座標範囲と共通Ｘ座標範囲のどちらか、または両方を求め、前記共通座標範囲内に制約された直線ベクターにより構成された混在ディスプレイリストを生成することを特徴とする図形処理装置。
【請求項２】
図形の描画処理を行う図形処理装置において、
図形の描画要素やクリップ要素を記述するベクター情報を、前記描画要素やクリップ要素を構成するベクターの形状を多角形近似した直線ベクター情報に変換し、前記直線ベクター情報中に含まれる各直線ベクターをベクター開始スキャンライン座標値に基づいてソートして該各直線ベクターの方向、傾き、および横切るスキャンライン数、またはそれらと等価なデータを含む情報によって構成されるディスプレイリストを生成するディスプレイリスト生成手段と、
前記ディスプレイリストを蓄積するディスプレイリスト格納手段と、
クリップ要素と描画要素を表現するディスプレイリストについて、クリップ要素による描画要素のクリップ処理を実行するクリップ処理手段と、
描画領域に重なりを有する複数のディスプレイリストから、前記描画領域の重なりを除去した新たなディスプレイリストを生成する重なり除去手段と、
前記ディスプレイリストの表現する図形を描画するディスプレイリスト描画手段とを有し、
前記重なり除去手段は、最前面に表示または印刷出力される上層の描画要素に対応するディスプレイリストから下層の描画要素に対応するディスプレイリストを順次、前記ディスプレイリスト格納手段から取り出して、該取り出した複数の描画要素に対応するディスプレイリストに基づいて重なり除去処理を行うことを特徴とする図形処理装置。
【請求項３】
図形の描画処理を行う図形処理装置において、
図形の描画要素やクリップ要素を記述するベクター情報を、前記描画要素やクリップ要素を構成するベクターの形状を多角形近似した直線ベクター情報に変換し、前記直線ベクター情報中に含まれる各直線ベクターをベクター開始スキャンライン座標値に基づいてソートして該各直線ベクターの方向、傾き、および横切るスキャンライン数、またはそれらと等価なデータを含む情報によって構成されるディスプレイリストを生成するディスプレイリスト生成手段と、
前記ディスプレイリストを蓄積するディスプレイリスト格納手段と、
クリップ要素と描画要素を表現するディスプレイリストについて、クリップ要素による描画要素のクリップ処理を実行するクリップ処理手段と、
描画領域に重なりを有する複数のディスプレイリストから、前記描画領域の重なりを除去した新たなディスプレイリストを生成する重なり除去手段と、
前記ディスプレイリストの表現する図形を描画するディスプレイリスト描画手段とを有し、
前記重なり除去手段は、前記重なり除去処理の対象となった複数の描画要素の描画領域全体を示す併合領域ディスプレイリストを生成して、新たに前記ディスプレイリスト格納手段から取り出されるディスプレイリストとの新たな重なり除去処理を行うことを特徴とする図形処理装置。
【請求項４】
図形の描画処理を行う図形処理装置において、
図形の描画要素を記述するベクター情報を、前記描画要素を構成するベクターの形状を多角形近似した直線ベクター情報に変換し、前記直線ベクター情報中に含まれる各直線ベクターをベクター開始スキャンライン座標値に基づいてソートして該各直線ベクターの方向、傾き、および横切るスキャンライン数、またはそれらと等価なデータを含む情報によって構成されるディスプレイリストを生成するディスプレイリスト生成手段と、
前記ディスプレイリストを蓄積するディスプレイリスト格納手段と、
描画領域に重なりを有する複数のディスプレイリストから、前記描画領域の重なりを除去した新たなディスプレイリストを生成する重なり除去手段と、
前記ディスプレイリストの表現する図形を描画するディスプレイリスト描画手段とを有し、
前記重なり除去手段は、最前面に表示または印刷出力される上層の描画要素に対応するディスプレイリストから下層の描画要素に対応するディスプレイリストを順次、前記ディスプレイリスト格納手段から取り出して、該取り出した複数の描画要素に対応するディスプレイリストに基づいて重なり除去処理を行うことを特徴とする図形処理装置。
【請求項５】
図形の描画処理を行う図形処理装置において、
図形の描画要素を記述するベクター情報を、前記描画要素を構成するベクターの形状を多角形近似した直線ベクター情報に変換し、前記直線ベクター情報中に含まれる各直線ベクターをベクター開始スキャンライン座標値に基づいてソートして該各直線ベクターの方向、傾き、および横切るスキャンライン数、またはそれらと等価なデータを含む情報によって構成されるディスプレイリストを生成するディスプレイリスト生成手段と、
前記ディスプレイリストを蓄積するディスプレイリスト格納手段と、
描画領域に重なりを有する複数のディスプレイリストから、前記描画領域の重なりを除去した新たなディスプレイリストを生成する重なり除去手段と、
前記ディスプレイリストの表現する図形を描画するディスプレイリスト描画手段とを有し、
前記重なり除去手段は、前記重なり除去処理の対象となった複数の描画要素の描画領域全体を示す併合領域ディスプレイリストを生成して、新たに前記ディスプレイリスト格納手段から取り出されるディスプレイリストとの新たな重なり除去処理を行うことを特徴とする図形処理装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、プリンタやディスプレイ装置などへ出力を行なうために、図形やアウトラインデータで表現された文字などの描画を行う図形処理装置に関する。
【０００２】
【従来の技術】
図形やアウトラインデータで表現された文字を扱うエディタ、ＣＡＤ／ＣＡＭシステムなどでは、それをプリンタやディスプレイ装置に出力するために、図形の描画処理が行われる。このような描画は、例えば図２に示すようなブロックを使って処理が進められる。
【０００３】
図２において、まず、ユーザ指示や外部からの入力により図形や文字の描画命令が入力されると、命令解釈部１により解釈され、ベクターデータ生成部２に入力される。ベクターデータ生成部２は、文字の場合にはフォント管理部３に要求して文字のアウトラインを表現するベクターデータを取得する。ストローク（線）図形は、太さや接続部分の形状をもとに例えば図３に示すようなベクターデータに変換される。このように変換された文字、ストローク図形、フィル（塗りつぶし）図形は、ディスプレイリスト生成部４に入力される。
【０００４】
ディスプレイリスト生成部４では、まずベジエ、スプラインなどで表現された曲線部分を微小直線で近似し、図４に示すような多角形のベクターデータに変換する。次に図７に示すようなディスプレイリスト形式の表現に変換する。ディスプレイリストは、多角形を構成するベクターに関するデータの一例として、Ｄｉｒ：方向フラグ（上向きの場合は＋１、下向きの場合は−１）、Ｘｓ：ベクター開始点のＸ座標、Ｙｅ：ベクター終了点のＹ座標、Ｄｘ：Ｙ座標の＋１増加に対するＸの変化量（傾き）、の４つの要素データを持つ。多角形からディスプレイリストへの変換については、さらに後段で詳述する。
【０００５】
このようにして生成されたディスプレイリストデータは、ディスプレイリスト描画部１３に入力される。ディスプレイリスト描画部１３では、入力されたディスプレイリストの各辺と出力デバイスの各スキャンラインとの交点座標をＤＤＡ（Ｄｉｇｉｔａｌ  Ｄｉｆｆｅｒｅｎｔｉａｌ  Ａｎａｌｙｚｅｒ）などの手法で計算し、各スキャンライン毎にＸ座標値でソートして塗りつぶしの始点／終点の対応を求め、その区間に対応した、スキャンラインに平行な線分をメモリ部１４上に描画する。このようにして描画されたメモリデータをプリンタやディスプレイ装置などの出力デバイス１５に転送することで、印刷や表示が行われる。
【０００６】
このような図形描画処理において、ディスプレイリスト描画部１３の動作は、各辺毎のＤＤＡやソート、メモリ描画などを含んでいるため重い処理となり、特にグラデーションなど重なりを含む複雑な図形を描画する際には、同じメモリ領域に何度も上書きが発生し、全体の処理速度を落とす大きな要因となる。さらに近年のプリンタ装置のように、描画命令を多角形やディスプレイリスト、エッジリストなどのレベルで蓄積することでページメモリを削減し、プリンタの印字速度に合わせてリアルタイムに画像形成を行いながら出力する場合には、重なりの多い複雑な部分で画像形成が間に合わずに絵抜けが生じる可能性があるという、問題（以下では、第１の問題とも呼ぶ）がある。
【０００７】
また、ディスプレイリスト描画部１３の動作は重いため、専用ハードウエアによる高速処理が意図される。そして、この処理は、図５（ａ）のように凸多角形の場合には比較的単純であるが、図５（ｂ）のように凹部を含んでいる場合や図５（ｃ）のように辺の交差を含んでいる場合には、各スキャンラインについて複数の始点／終点の対が存在することになるため、前述のように求められた各交点をソートして対応を見つける処理が必要になる。しかし、入力される図形の複雑さに制約が無い場合、交点の個数にも制限がなく、ハードウエアでソート回路を構成することは非常に困難であるという、問題（以下、第２の問題とも呼ぶ）がある。
【０００８】
従来、上記第１の問題を解決する試みとして、描画要素から重なりを除去することで処理の高速化やリアルタイム描画を行う手法が提案されている。このような考え方を用いた従来技術としては、特開平８−２７９０５０号公報や特開平９−６２８５１号公報、特開平９−１７１５６３号公報、特開平９−２８１９５３号公報などがある。
【０００９】
また従来、上記第２の問題を解決する試みとして、多角形を、底辺がＸ軸に平行な台形（四角形や三角形を含む）などのソートが発生しない部分図形に分割し、それぞれを処理する手法がある。そのような考え方を持った従来技術として、特開昭６０−７４０８６号公報や特開昭６１−２４８１７６号公報、特開昭６２−２７１１８６号公報などがある。
【００１０】
【発明が解決しようとする課題】
特開平８−２７９０５０号公報や特開平９−６２８５１号公報の手法は、描画要素をエッジリストの形式で蓄積し、同じスキャンラインに対する描画を行うエッジ情報を比較して重なりがある場合にこれを除去するものである。しかし、エッジリストでの描画要素の蓄積は、近年のプリンタ装置のように解像度が高くなると蓄積すべきデータ量が膨大となり、メモリコストが増大するなどの欠点がある。
【００１１】
特開平９−１７１５６３号公報や特開平９−２８１９５３号公報の手法は、描画要素を多角形データの形式で蓄積し、２つの多角形について重なり判定を行い、重なりがある場合にこれを除去するものである。しかし、多角形レベルで重なり除去を行うためには、多角形が単純な凸型になっている必要があり、凹型や辺の交差を含む多角形についてはこれを分割して凸型にするなどの前処理が必要である。また、重なり判定／オーバーレイグラフなどで対象を絞ってはいるものの、基本的に２つの多角形間の重なり除去を行う方式なので、Ｎ個の処理対象の重なりを完全に除去するためにはＮ！回の処理が必要となる。
【００１２】
本発明は以上のような従来技術の問題点を考慮してなされたものであり、ディスプレイリスト形式で表現された描画要素間の重なりを除去する重なり除去手段を持ち、エッジリストと比較して高解像度の場合でも少ないメモリ量での蓄積を可能とし、また特別な前処理を行わず、かつ少ない処理で重なり除去が可能な、高速の図形処理装置を実現することを、第１の目的とする。
【００１３】
次に、特開昭６０−７４０８６号公報や特開昭６１−２４８１７６号公報では、多角形を底辺がＸ軸に平行な台形（四角形や三角形を含む）に分割し、各台形を順に処理することで塗りつぶし処理時のソート回路を不要としている。しかしこの方式では、複雑な多角形を分割すると非常に多くの台形が生成されるため、その管理や一時記憶が難しく、また台形毎に処理されるため処理速度が上がらないという問題があった。
【００１４】
特開昭６２−２７１１８６号公報では、入力された曲線を含む図形を、曲線を含んだまま、各スキャンラインでの描画線分が１つとなるような部分図形に分割し、各部分図形を複数のＤＤＡ回路と線分描画回路に入力して並列に処理を行っている。しかし、この方式では入力される図形の複雑さに応じて部分図形の個数が変わり、幾つのＤＤＡ／線分描画回路が必要かが制限できず、また各部分図形の描画が異なるスキャンラインに対して行われるため、実際にメモリに書き込む部分で競合が発生し、処理速度が上がらないことが予想される。
【００１５】
このような問題に対して、本願の発明者は、特願平９−３０２４０３号において、２Ｎ個（Ｎは１以上）のＤＤＡ手段と、２Ｎ個の入力をソート可能なソート手段と、入力された任意のディスプレイリストを各スキャンラインでの描画線分数がＮ以下となる複数のディスプレイリストに分割する分割手段を持ち、入力された多角形を表現するディスプレイリストをＤＤＡ／ソート可能な部分多角形に分割して処理することで、分割図形をなるべく小さな領域で管理／記憶でき、高速に処理可能な図形処理装置を提案した。
【００１６】
上記の特願平９−３０２４０３号で提案された方式では、ディスプレイリスト描画部に相当する部分は描画要素のみを描画できる構成となっている。しかしながら、描画命令の中には、描画要素がメモリに描画される際の領域を制限するクリップ要素も含まれており、その場合にはディスプレイリスト描画部に入力される前までに描画要素をクリップ要素でクリップ処理する必要が生じ、速度を落とす要因となる場合があった。
【００１７】
この対策としては、描画要素とクリップ要素を混在させたディスプレイリスト情報を入力し、クリップしながら描画できるようにディスプレイリスト描画部の構成を変更することが考えられる。しかしながら、特願平９−３０２４０３号で提案されたディスプレイリストの分割方式は混在要素には対応できず、辺の本数が２Ｎよりも多いスキャンラインが存在する場合には、クリップ要素と描画要素を一度分離し、特願平９−３０２４０３号で述べた分割処理を別々に行ってから再度混在させるなどの複雑な処理が必要となり、全体のパフォーマンスが低下するという欠点があった。
【００１８】
本発明は以上のような点を考慮してなされたものであり、クリップ要素と描画要素とが混在している場合でも、分割図形をなるべく小さな領域で管理／記憶でき、高速に処理可能な図形処理装置を実現することを、第２の目的とする。
【００１９】
【課題を解決するための手段】
本発明は、上記の目的を達成するために成された図形処理装置に関するものである。即ち、本発明は、図形の描画処理を行う図形処理装置において：図形の描画要素やクリップ要素を記述するベクター情報（ベクター情報は、例えば描画要素やクリップ要素の形状や描画色、ストローク図形かフィル図形であるかについての指定、ストローク図形である場合の線幅や線種などの属性を表わす）から、前記描画要素やクリップ要素を構成するベクターの形状を多角形近似した直線ベクター情報に変換し、前記直線ベクター情報中に含まれる各直線ベクターをベクター開始スキャンライン座標値に基づいてソートして該各直線ベクターの方向、傾き、および横切るスキャンライン数、またはそれらと等価なデータを含む情報によって構成されるディスプレイリストを生成するディスプレイリスト生成手段と；前記ディスプレイリスト生成手段によって生成された、描画要素を表わすディスプレイリストと、当該描画要素の描画領域を制限するクリップ要素を表わすディスプレイリストとをマージ処理し、描画要素とクリップ要素とが混在したディスプレイリストを生成するマージ処理手段と；前記ディスプレイリストを蓄積するディスプレイリスト格納手段と；前記ディスプレイリストに基づいて、スキャンラインで交差する前記直線ベクター数が全スキャンラインにおいて２Ｎ（Ｎは１以上の整数）以下であるか否かを判定する判定手段と；クリップ要素と描画要素が混在したディスプレイリストについて、クリップ要素による描画要素のクリップ処理を実行し、描画要素のみのディスプレイリストに変換するクリップ処理手段と；前記クリップ処理手段によって変換された描画要素のみのディスプレイリストを全てのスキャンラインで交差する直線ベクター数が２Ｎ以下となるように分割し、複数のディスプレイリストを生成する分割処理手段と、描画領域に重なりを有する複数のディスプレイリストから、前記描画領域の重なりを除去した新たなディスプレイリストを生成する重なり除去手段と；前記ディスプレイリストに基づいて、各スキャンラインと前記直線ベクターの交点座標値を算出する２Ｎ個のＤＤＡ手段と、前記ＤＤＡ手段からの出力値をソートするソート手段と、前記ソート手段においてソートされたデータから描画線分を構成する始点および終点の位置情報を求めてその間のメモリ領域を塗りつぶすメモリ描画手段とを備えたディスプレイリスト描画手段と；前記ディスプレイリストを前記ディスプレイリスト描画手段で描画処理する際の処理時間を推定し、推定された描画処理時間に基づいて前記重なり除去手段による重なり除去処理の実行効果を判定する重なり除去処理判定手段とを設けることを特徴とする。
【００２０】
この構成によれば、ディスプレイリスト形式で表現された描画要素間の重なりを除去する重なり除去手段を持ち、エッジリストと比較して高解像度の場合でも少ないメモリ量での蓄積を可能とし、また特別な前処理を行わずかつ少ない処理で重なり除去が可能な、高速の図形処理装置を実現することができる。さらに、重なり除去処理が必要かどうかを判定する判定手段と、クリップ要素と描画要素が混在したディスプレイリストをクリップ処理して描画要素のみのディスプレイリストに変換するクリップ処理手段とを持つことで、重なり除去処理を必要最小限に抑え、かつクリップ要素と描画要素とが混在している場合でも対応可能な、高速の図形処理装置を実現することができる。さらに、最終的に描画対象の描画要素が２Ｎ個（Ｎは正の整数）を越えた場合には、ディスプレイリストを分割して処理することができ、描画データを小さな領域で管理および記憶が可能となり、かつクリップ要素と描画要素とが混在している場合でも分割図形をなるべく小さな領域で管理／記憶でき、高速に処理可能な図形処理装置を実現することができる。
【００２１】
さらに本発明は、図形の描画処理を行う図形処理装置において：図形の描画要素やクリップ要素を記述するベクター情報を、前記描画要素やクリップ要素を構成するベクターの形状を多角形近似した直線ベクター情報に変換し、前記直線ベクター情報中に含まれる各直線ベクターをベクター開始スキャンライン座標値に基づいてソートして該各直線ベクターの方向、傾き、および横切るスキャンライン数、またはそれらと等価なデータを含む情報によって構成されるディスプレイリストを生成するディスプレイリスト生成手段と；前記ディスプレイリスト生成手段によって生成された、描画要素を表わすディスプレイリストと、当該描画要素の描画領域を制限するクリップ要素を表わすディスプレイリストとをマージ処理し、描画要素とクリップ要素とが混在したディスプレイリストを生成するマージ処理手段と；前記ディスプレイリストに基づいて、スキャンラインで交差する前記直線ベクター数が全スキャンラインにおいて２Ｎ（Ｎは１以上の整数）以下であるか否かを判定する判定手段と；クリップ要素と描画要素が混在したディスプレイリストについて、クリップ要素による描画要素のクリップ処理を実行し、描画要素のみのディスプレイリストに変換するクリップ処理手段と；前記クリップ処理手段によって変換された描画要素のみのディスプレイリストを全てのスキャンラインで交差する直線ベクター数が２Ｎ以下となるように分割し、複数のディスプレイリストを生成する分割処理手段と；前記ディスプレイリストに基づいて、各スキャンラインと前記直線ベクターの交点座標値を算出する２Ｎ個のＤＤＡ手段と、前記ＤＤＡ手段からの出力値をソートするソート手段と、前記ソート手段においてソートされたデータから描画線分を構成する始点および終点の位置情報を求めてその間のメモリ領域を塗りつぶすメモリ描画手段とを備えたディスプレイリスト描画手段とを設けることを特徴とする。
【００２２】
この構成でも、クリップ要素と描画要素が混在したディスプレイリストをクリップ処理して描画要素のみのディスプレイリストに変換するクリップ処理手段とを持つことで、クリップ要素と描画要素とが混在している場合でも対応可能な、高速の図形処理装置を実現することができる。さらに、最終的に描画対象の描画要素が２Ｎ個（Ｎは正の整数）を越えた場合には、ディスプレイリストを分割して処理することができ、描画データを小さな領域で管理および記憶が可能となり、かつクリップ要素と描画要素とが混在している場合でも分割図形をなるべく小さな領域で管理／記憶でき、高速に処理可能な図形処理装置を実現することができる。
【００２３】
さらに本発明は、図形の描画処理を行う図形処理装置において：図形の描画要素やクリップ要素を記述するベクター情報を、前記描画要素やクリップ要素を構成するベクターの形状を多角形近似した直線ベクター情報に変換し、前記直線ベクター情報中に含まれる各直線ベクターをベクター開始スキャンライン座標値に基づいてソートして該各直線ベクターの方向、傾き、および横切るスキャンライン数、またはそれらと等価なデータを含む情報によって構成されるディスプレイリストを生成するディスプレイリスト生成手段と；前記ディスプレイリスト生成手段によって生成された、描画要素を表わすディスプレイリストと、当該描画要素の描画領域を制限するクリップ要素を表わすディスプレイリストとをマージ処理し、描画要素とクリップ要素とが混在したディスプレイリストを生成するマージ処理手段と；前記ディスプレイリストを蓄積するディスプレイリスト格納手段と；クリップ要素と描画要素が混在したディスプレイリストについて、クリップ要素による描画要素のクリップ処理を実行し、描画要素のみのディスプレイリストに変換するクリップ処理手段と；描画領域に重なりを有する複数のディスプレイリストから、前記描画領域の重なりを除去した新たなディスプレイリストを生成する重なり除去手段と；前記ディスプレイリストの表現する図形を描画するディスプレイリスト描画手段と；前記ディスプレイリストを前記ディスプレイリスト描画手段で描画処理する際の処理時間を推定し、推定された描画処理時間に基づいて前記重なり除去手段による重なり除去処理の実行効果を判定する重なり除去処理判定手段とを設けることを特徴とする。
【００２４】
この構成によれば、ディスプレイリスト形式で表現された描画要素間の重なりを除去する重なり除去手段を持ち、エッジリストと比較して高解像度の場合でも少ないメモリ量での蓄積を可能とし、また特別な前処理を行わずかつ少ない処理で重なり除去が可能な、高速の図形処理装置を実現することができる。さらに、重なり除去処理が必要かどうかを判定する判定手段と、クリップ要素と描画要素が混在したディスプレイリストをクリップ処理して描画要素のみのディスプレイリストに変換するクリップ処理手段とを持つことで、重なり除去処理を必要最小限に抑え、かつクリップ要素と描画要素とが混在している場合でも対応可能な、高速の図形処理装置を実現することができる。
【００２５】
さらに本発明は、図形の描画処理を行う図形処理装置において：図形の描画要素やクリップ要素を記述するベクター情報を、前記描画要素やクリップ要素を構成するベクターの形状を多角形近似した直線ベクター情報に変換し、前記直線ベクター情報中に含まれる各直線ベクターをベクター開始スキャンライン座標値に基づいてソートして該各直線ベクターの方向、傾き、および横切るスキャンライン数、またはそれらと等価なデータを含む情報によって構成されるディスプレイリストを生成するディスプレイリスト生成手段と；前記ディスプレイリストを蓄積するディスプレイリスト格納手段と；クリップ要素と描画要素を表現するディスプレイリストについて、クリップ要素による描画要素のクリップ処理を実行するクリップ処理手段と；描画領域に重なりを有する複数のディスプレイリストから、前記描画領域の重なりを除去した新たなディスプレイリストを生成する重なり除去手段と；前記ディスプレイリストの表現する図形を描画するディスプレイリスト描画手段とを設けることを特徴とする。
【００２６】
この構成でも、ディスプレイリスト形式で表現された描画要素間の重なりを除去する重なり除去手段を持ち、エッジリストと比較して高解像度の場合でも少ないメモリ量での蓄積を可能とし、また特別な前処理を行わずかつ少ない処理で重なり除去が可能な、高速の図形処理装置を実現することができる。さらに、クリップ要素と描画要素が混在したディスプレイリストをクリップ処理して描画要素のみのディスプレイリストに変換するクリップ処理手段とを持つことで、クリップ要素と描画要素とが混在している場合でも対応可能な、高速の図形処理装置を実現することができる。
【００２７】
さらに本発明は、図形の描画処理を行う図形処理装置において：図形の描画要素を記述するベクター情報を、前記描画要素を構成するベクターの形状を多角形近似した直線ベクター情報に変換し、前記直線ベクター情報中に含まれる各直線ベクターをベクター開始スキャンライン座標値に基づいてソートして該各直線ベクターの方向、傾き、および横切るスキャンライン数、またはそれらと等価なデータを含む情報によって構成されるディスプレイリストを生成するディスプレイリスト生成手段と；前記ディスプレイリストを蓄積するディスプレイリスト格納手段と；描画領域に重なりを有する複数のディスプレイリストから、前記描画領域の重なりを除去した新たなディスプレイリストを生成する重なり除去手段と；前記ディスプレイリストの表現する図形を描画するディスプレイリスト描画手段とを設けることを特徴とする。
【００２８】
この構成によれば、ディスプレイリスト形式で表現された描画要素間の重なりを除去する重なり除去手段を持ち、エッジリストと比較して高解像度の場合でも少ないメモリ量での蓄積を可能とし、また特別な前処理を行わずかつ少ない処理で重なり除去が可能な、高速の図形処理装置を実現することができる。
【００２９】
さらに本発明の図形処理装置において、前記ディスプレイリストを前記ディスプレイリスト描画手段で描画処理する際の処理時間を推定し、推定された描画処理時間に基づいて前記重なり除去手段による重なり除去処理の実行効果を判定する重なり除去処理判定手段を備えるようにしてもよい。
【００３０】
さらに本発明の図形処理装置において、前記ディスプレイリストを出力領域を分割した各部分領域毎に分割する部分領域分割処理手段を備え、部分領域毎に処理を行うようにしてもよい。
【００３１】
さらに本発明の図形処理装置において、前記マージ処理手段は、生成する前記混在したディスプレイリストにおいて、描画要素を構成する直線ベクターに関するディスプレイリスト中のベクター方向を示す値と、クリップ要素を構成する直線ベクターに関するディスプレイリスト中のベクター方向を示す値とを異なる値に設定するようにしてもよい。
【００３２】
さらに本発明の図形処理装置において、前記マージ処理手段は、描画要素を表わす前記ディスプレイリストと、クリップ要素を表わす前記ディスプレイリストについて、それぞれの外接矩形から少なくともその共通Ｙ座標範囲と共通Ｘ座標範囲のどちらか、または両方を求め、前記共通座標範囲内に制約された直線ベクターにより構成された混在ディスプレイリストを生成するようにしてもよい。
【００３３】
さらに本発明の図形処理装置において、前記判定手段は、前記ディスプレイリスト中に含まれる直線ベクターを開始スキャンライン座標値の小さい順に読み出して当該直線ベクターの終了スキャンライン座標値を保持し、読み出した直線ベクターの開始スキャンライン座標値が既に保持している終了スキャンライン座標値より大きい場合には保持している終了スキャンライン座標値を破棄する処理を行い、当該ディスプレイリストについて、保持している終了スキャンライン座標値数が２Ｎより大きくなった場合にはその時点で２Ｎ以下ではないとの判定結果を出力し、未読み出しの直線ベクター数と保持している終了スキャンライン座標値数との和が２Ｎ以下となった場合にはその時点で２Ｎ以下であるとの判定結果を出力するようにしてもよい。
【００３４】
さらに本発明の図形処理装置において、前記クリップ処理手段におけるクリップ処理による描画要素のみのディスプレイリストへの変換処理は、前記重なり除去処理判定手段により重なり除去処理が必要と判定された場合に、重なり除去処理の対象となる前記混在ディスプレイリストに対して実行するようにしてもよい。
【００３５】
さらに本発明の図形処理装置において、前記クリップ処理手段におけるクリップ処理による描画要素のみのディスプレイリストへの変換処理は、
ａ）前記ディスプレイリストが、前記判定手段において、スキャンラインと交差する前記直線ベクター数が２Ｎより大きいスキャンラインが存在すると判定され、かつ
ｂ）前記ディスプレイリストが、描画要素とクリップ要素とが混在しているディスプレイリストである、ことを条件として実行するようにしてもよい。
【００３６】
さらに本発明の図形処理装置において、前記分割処理手段における、全てのスキャンラインで交差する直線ベクター数が２Ｎ以下となるようにディスプレイリストを分割し、複数のディスプレイリストを生成する処理は、
ｃ）前記ディスプレイリストが、前記判定手段において、スキャンラインと交差する前記直線ベクター数が２Ｎより大きいスキャンラインが存在すると判定され、かつ
ｄ）前記ディスプレイリストが、描画要素のみによって構成されたものである、ことを条件として実行するようにしてもよい。
【００３７】
さらに本発明の図形処理装置において、前記重なり除去手段は、最前面に表示または印刷出力される上層の描画要素に対応するディスプレイリストから下層の描画要素に対応するディスプレイリストを順次、前記ディスプレイリスト格納手段から取り出して、該取り出した複数の描画要素に対応するディスプレイリストに基づいて重なり除去処理を行うようにしてもよい。
【００３８】
さらに本発明の図形処理装置において、前記重なり除去手段は、前記重なり除去処理の対象となった複数の描画要素の描画領域全体を示す併合領域ディスプレイリストを生成して、新たに前記ディスプレイリスト格納手段から取り出されるディスプレイリストとの新たな重なり除去処理を行うようにしてもよい。
【００３９】
さらに本発明の図形処理装置において、前記重なり除去処理判定手段での判定は、前記部分領域分割処理手段により分割された部分領域毎に行われ、該部分領域毎に重なり除去処理を行うか否かの切り替えを行うようにしてもよい。
【００４０】
さらに本発明の図形処理装置において、前記重なり除去処理判定手段で求められる前記ディスプレイリスト描画手段での描画処理時間推定値は、少なくとも当該ディスプレイリストの描画面積または外接矩形面積、高さのいずれかの情報を用いて求められるようにしてもよい。
【００４１】
さらに本発明の図形処理装置において、前記重なり除去処理判定手段で求められる前記ディスプレイリスト描画手段での描画処理時間推定値は、描画要素が文字、図形、画像のいずれであるかを示す情報を含む描画要素属性に応じた描画処理時間推定計算方法により実行するようにしてもよい。
【００４２】
さらに本発明の図形処理装置において、前記重なり除去処理判定手段は、前記重なり除去手段による処理結果に基づいて、前記ディスプレイリスト描画手段での描画処理時間推定値を求め、該求められた処理結果に基づく描画処理時間推定値が、予め定められた閾値以下となった場合には、前記重なり除去手段による新たな重なり除去処理を行わないようにしてもよい。
【００４３】
さらに本発明の図形処理装置において、前記重なり除去手段による処理は、処理対象となる複数の描画要素に対応するディスプレイリストを複数のグループに分割し、該分割されたグループ毎に実行するようにしてもよい。
【００４４】
さらに本発明の図形処理装置において、前記重なり除去手段による処理は、処理対象となる描画領域を複数の部分領域に分割し、該分割された部分領域毎に実行するようにしてもよい。
【００４５】
さらに本発明の図形処理装置において、前記メモリ描画手段は、処理対象であるディスプレイリストが、描画要素のみからなるディスプレイリストであるか、描画要素およびクリップ要素の混在する混在ディスプレイリストか、さらに、処理対象であるディスプレイリスト中の描画要素およびクリップ要素の塗りつぶし規則が偶奇規則であるか非零規則であるか、これらの処理対象ディスプレイリスト条件に基づいて、前記ソートデータからの描画線分構成始点および終点の位置情報算出方法を変更するようにしてもよい。
【００４６】
さらに本発明の図形処理装置において、前記２Ｎ個のＤＤＡ手段は、並列処理可能な構成を有し、各スキャンラインと直線ベクターの交点座標値の算出処理は、並列処理によって実行されるようにしてもよい。
【００４７】
さらに本発明の図形処理装置において、前記重なり除去手段による処理は、処理対象となる複数の描画要素を描画順の下から順に実際に描画して画像描画要素に変換し、当該画像描画要素と残りの図形要素を前記ディスプレイリスト描画手段で描画する場合の処理時間を前記重なり除去処理判定手段により推定し、重なり除去処理が不要と判定されるまで前記画像描画要素への変換を行うようにしてもよい。
【００４８】
さらに本発明の図形処理装置において、前記重なり除去手段による処理は、処理対象となる描画領域を複数の部分領域に分割し、分割された幾つかの部分領域を実際に描画して画像描画要素に変換し、当該画像描画要素と残りの部分領域に含まれる図形要素を前記ディスプレイリスト描画手段で描画する場合の処理時間を前記重なり除去処理判定手段により推定し、重なり除去処理が不要と判定されるまで順次複数の部分領域の前記画像描画要素への変換を行うようにしてもよい。
【００４９】
さらに本発明の図形処理装置において、前記重なり除去処理判定手段で求められる前記ディスプレイリスト描画手段での描画処理時間推定値は、ディスプレイリストの描画処理に相当する処理を要求された解像度以下の解像度で行って求められた面積の近似値情報を用いて求められるようにしてもよい。
【００５０】
さらに本発明の図形処理装置において、前記ディスプレイリスト生成手段は、図形がストローク図形である場合に、各ベクターのストローク長と線幅、線種などの情報を基に描画面積の近似値を求め、当該ストローク図形から生成された前記ディスプレイリストに前記描画面積の近似値情報を付加するようにしてもよい。
【００５１】
さらに本発明の図形処理装置において、前記ディスプレイリスト生成手段は、図形がフィル図形である場合に、少なくとも、自己交差を持つかどうか、分離した複数の図形要素から成り立っているかどうか、を判定し、自己交差を持たずかつ単一の図形要素から成り立っている場合には、当該図形を構成する各直線ベクターを基に描画面積の近似値を求め、当該フィル図形から生成された前記ディスプレイリストに前記描画面積の近似値情報を付加するようにしてもよい。
【００５２】
さらに本発明の図形処理装置において、前記クリップ処理手段は、少なくとも図形要素の形状が矩形であるかどうかを判定する手段を有し、前記判定手段での判定結果を基にクリップ処理方法を変更するようにしてもよい。
【００５３】
【発明の実施の形態】
以下、図面に基づき本発明に係わる図形処理装置の実施例について説明する。
【００５４】
図１は本発明の図形処理装置の実施例を示すブロック図である。同図において、図形処理装置は、命令解釈部１と、ベクターデータ生成部２と、フォント管理部３と、ディスプレイリスト生成部４と、ディスプレイリスト格納部５と、部分領域分割部６と、マージ処理部７と、クリップ処理部８と、重なり除去判定部９と、重なり除去処理部１０と、分割判定部１１と、分割処理部１２と、ディスプレイリスト描画部１３と、メモリ部１４と、出力デバイス１５とを含んで構成されている。さらに、ディスプレイリスト描画部１３は、２Ｎ個（Ｎは正の整数）のＤＤＡ部１３１と、ソート部１３２と、メモリ描画部１３３とを含んで構成されている。
【００５５】
以下、本実施例の各構成要素の概要および動作について説明する。
【００５６】
命令解釈部１は、入力された図形または文字の描画命令を解釈し、次のベクターデータ生成部２が理解できる形式に変換するものである。ＰｏｓｔＳｃｒｉｐｔ（米国アドビ・システムズ社商標）やＩｎｔｅｒｐｒｅｓｓ（米国ゼロックス社商標）などのページ記述言語では、これらの描画命令は文字列やバイナリ列として与えられるので、そのような場合には命令解釈部１はトークンを切り出し、字句解釈などを行って内部の描画命令に変換する。
【００５７】
ベクターデータ生成部２は、命令解釈部１からの入力を受けて、ベクターデータを生成する。入力がフィル（塗りつぶし）図形の場合は、命令解釈部１から図形の輪郭を表現するベクターと、偶奇規則／非零規則などの塗りつぶし規則と、曲線を直線近似する場合の精度を指示するフラットネス（ｆｌａｔｎｅｓｓ）値や、描画色などが与えられるので、その情報をそのまま出力する。入力がストローク（線）図形の場合には、線を表現するベクターと、線幅／線種／終端形状／接続形状などの線属性と、曲線を直線近似する場合の精度を指示するフラットネス値や、描画色などが与えられるので、このうちのベクターと線属性の情報を使って、図３に示すような輪郭ベクターを生成し、残りの情報とともに出力する。入力が文字の場合には、文字コードと、フォントＩＤと、描画位置や描画色などの情報が与えられるので、このうちの文字コードとフォントＩＤ、描画位置の情報をフォント管理部３に送って文字の輪郭ベクターを取得し、残りの情報とともに出力する。
【００５８】
フォント管理部３は、各種フォントに対するアウトラインベクターデータを記憶するとともに、与えられた文字コードとフォントＩＤによって、その文字に対するアウトラインベクターデータを提供する。
【００５９】
上記の処理により、入力された図形／文字は全て、輪郭を表現するベクターデータと描画色、フラットネス値、塗りつぶし規則の情報に変換される。ディスプレイリスト生成部４は、これらの入力されたベクターデータ中に曲線が含まれている場合には、まずその曲線部分を、誤差がフラットネス値で指定された精度以下となるように、微小な直線ベクターで近似する処理を行う。例えば曲線のベクターには、図６に示す４つの制御点で表現されるベジエ曲線が使われる。この場合直線ベクター化の処理は、図６に示す通りベジエ曲線を再帰的に分割し、高さ（距離ｄ）がフラットネス値より小さくなった時点で分割を終了する。そして分割された各ベジエ曲線の始点と終点を順番に結ぶことにより、直線ベクター化が完了する。
【００６０】
このように直線近似されたベクターデータを基にして、ディスプレイリスト生成部４は、次にこれをディスプレイリスト形式の表現に変換する。ここでディスプレイリストとは、例えば図７に示したようなものである。入力された多角形ベクターは、始めに各頂点のＹ座標が整数になるように変換される。具体的には、各辺についてＹ座標の小さい方の頂点は切上げし、大きい方の頂点は切捨てし、各辺の傾きが変わらないように整数化誤差をＸ座標値で補正する。このようにしてＹ座標値を整数化した後、同じ開始Ｙ座標を持つ辺が集められてリストで接続される。リストの各要素には、その辺の方向が上向きか下向きかを＋１／−１で表す方向フラグＤｉｒと、開始点ＹｓにおけるＸ座標値Ｘｓと、終了点のＹ座標値Ｙｅと、Ｙ座標値の＋１増加に対するＸ座標値の変化量で表した辺の傾きＤｘとが格納される。尚、水平に近い辺など、どのスキャンラインも横切らないものについては、ディスプレイリストの要素に登録されない。
【００６１】
このようにして生成されたディスプレイリストは、ディスプレイリスト格納部５に蓄積される。
【００６２】
これまでの説明は描画要素を対象に行ったが、クリップ領域を表わすクリップ要素についても（色などが含まれないことを除いて）ほぼ同様に処理が行われ、ディスプレイリストが生成される。ディスプレイリスト格納部５には、描画要素に先立って生成されたクリップ要素のディスプレイリストが一時保持されており、そのクリップ領域中に描画される描画要素が入力されてディスプレイリスト化された場合には、マージ処理部７によりクリップ領域のディスプレイリストとマージされ、再度ディスプレイリスト格納部５に出力される。
【００６３】
このマージ処理は、図８に示すように、ディスプレイリスト格納部５に一時保持されているクリップ要素（図８における太線）のディスプレイリストの各辺と、描画要素（図８の細線）のディスプレイリストの各辺とを、開始スキャンラインの昇順に混合し、かつその際にクリップ要素に含まれている辺については、Ｄｉｒを特定の値（図８では±２５６）に変更する。このＤｉｒ値は、１つのスキャンラインに交差する最大辺数の２倍以上であればよく、上限がわからない場合には余裕を持って大きな値を使うこともできる。以下では、通常１２８本以上の辺が同一スキャンライン中にあることはないとして、２５６で説明を行う。尚、マージ時に、両方の要素が共通に存在する矩形領域やＸ座標領域またはＹ座標領域の範囲でディスプレイリストをクリップすれば、処理をやや高速化できる。その一例として、共通Ｙ座標領域でクリップしてマージした例を図９に示す。
【００６４】
ここまでの処理で、それぞれの描画要素は、それを表現するディスプレイリストと（もしあれば）その描画要素のクリップ領域を表現するクリップ要素のディスプレイリストとが混在したディスプレイリストに変換される。
【００６５】
このようにして生成／蓄積されたディスプレイリストは、部分領域分割部６により、図１０に図示するように、ページを所定の幅で分割した部分領域（以下、バンドと称す）毎に分割され、各バンド毎にディスプレイリスト格納部５に蓄積される。
【００６６】
バンド分割するのは、ダブルバッファ方式により描画／出力することで、メモリ部１４の容量を２バンド分に低減するためである。メモリ部１４は、図１０に示すようなページを水平の短冊状に分割した領域の２個分の容量を持ち、交互に描画と出力デバイス１５への転送が行われる。尚、図１０に示す例では、ページを４バンドに分割しているが、分割数はメモリ部１４の容量や処理装置の構成などに基づいて、任意に設定することができる。
【００６７】
尚、ここまでの説明では、ディスプレイリスト生成→マージ処理→部分領域分割の順で処理を行ったが、ディスプレイリスト生成→部分領域分割→マージ処理の順で行っても全く問題はない。
【００６８】
重なり除去判定部９は、ディスプレイリスト格納部５に蓄積されたバンド毎のディスプレイリストを読み出し、そのバンドをディスプレイリスト描画部１３で描画処理する際の処理時間を推定し、出力デバイス１５の印字速度に間に合うかどうかを判定する。
【００６９】
判定の結果、間に合わないと判断されたバンドは、まずそのバンド中に描画要素とクリップ要素がマージされた混在ディスプレイリストを含んでいる場合には、その混在ディスプレイリストをクリップ処理部８により処理し、描画要素のみのディスプレイリストに変換する。次に、重なり除去処理部１０により重なり除去処理を行って、再度ディスプレイリスト格納部５に格納する。この重なり判定、クリップ、重なり除去の各処理については、後段で詳述する。
【００７０】
分割判定部１１は、ディスプレイリスト格納部５に蓄積されたディスプレイリストを順次読み込み、入力されたディスプレイリストについて、スキャンラインに交差する辺の数が２Ｎ（ＤＤＡ部１３１の個数２Ｎに等しい）を超える部分が存在しているかどうかを判定する。判定方法の詳細については、後述する。
【００７１】
判定の結果として、あるディスプレイリストがあるスキャンラインで２Ｎを超えている場合には、それが混在ディスプレイリストでない場合には分割処理部１２にディスプレイリストを出力して、全てのスキャンラインで交差する辺の数が２Ｎ以下である複数のディスプレイリストに分割する。分割処理の詳細は後述する。２Ｎを超えるスキャンラインがあり、かつ混在ディスプレイリストである場合には、初めに混在ディスプレイリストをクリップ処理部８に出力し、クリップ処理を行って描画要素のみのディスプレイリストに変換する。クリップ処理されたディスプレイリストは分割判定部１１に戻され、再度分割判定を行い、２Ｎを超えるスキャンラインが残っている場合には、これを分割処理部１２で分割する。
【００７２】
このようにして生成／蓄積されたディスプレイリストは、１個づつディスプレイリスト描画部１３に入力される。ディスプレイリスト描画部１３は、２Ｎ個のＤＤＡ部１３１と、ＤＤＡ部１３１から出力される２Ｎ個以下のデータをＸ座標値でソートするソート部１３２と、ソートされた結果から始点／終点の対を求め、その間を指定の描画色でメモリに描画するメモリ描画１３３とから構成され、入力されたディスプレイリスト表現された多角形を展開して、メモリ部１４中のバンドに対応するメモリ領域に描画する。この処理についても、後で詳細に説明する。
【００７３】
メモリ部１４にバンド内の全ての描画要素が描画されると、その結果は出力デバイス１５に出力され、プリンタまたはデイスプレイ等において印刷または表示される。
【００７４】
以上、本発明の図形処理装置の概要について記述した。次に、この図形処理装置の主要部の詳細について説明する。
【００７５】
初めに、クリップ処理部８について説明する。
【００７６】
クリップ処理部８は、図１１に示すように、クリップ処理の全体を制御するクリップ制御部８１と、アクティブリスト制御部８２と、ディスプレイリストを一時記憶するディスプレイリスト記憶部８３とから構成されている。
【００７７】
以下、クリップ制御部８１の動作を、図１２〜１５に示すフローチャートに沿って説明する。
【００７８】
始めにステップ１において、処理対象スキャンラインを表わすＹｃをＹｍｉｎに設定する。このＹｍｉｎは、対象ディスプレイリストに含まれる辺の開始スキャンラインＹ座標の最小値であり、例えば図９に示すディスプレイリストの場合にはＹｍｉｎ＝５である。
【００７９】
次にステップ２において、アクティブリスト制御部８２中の各辺とＹ＝Ｙｃとの交点のＸ座標値をＤＤＡなどの手法で計算する。尚、Ｙ＝Ｙｍｉｎの時点ではアクティブリスト制御部８２中には何も辺が登録されていないので、何も行われない。
【００８０】
ステップ３において、クリップ対象ディスプレイリストから、Ｙｃを開始点とする辺があればこれを抜き出してアクティブリスト制御部８２中のアクティブリストに追加する。アクティブリストは、対象スキャンラインに交点を持つ辺のみで構成されたリストであり、例えば図１６のように、Ｄｉｒ，Ｘｓ，Ｙｅ，Ｄｘ以外に後述する辺のステータス情報を格納するＳｔａｔｕｓ、現在のスキャンラインとの交点のＸ座標値Ｘｃ、辺の開始スキャンラインＹｓなどの情報が追加される。尚、追加されたばかりの辺は、Ｓｔａｔｕｓ＝ＩＮＩＴ，Ｘｃ＝Ｘｓ，Ｙｓ＝Ｙｃとなる。
【００８１】
ステップ４において、アクティブリスト中の辺データを、Ｘｃの昇順になるようにソートする。
【００８２】
次にＳ１（詳細を図１３に示す）に移り、図１３に示すステップ１０で変数ｃｄｉｒとｏｄｉｒをそれぞれ０に設定する。ここでｃｄｉｒのｃは現在（Ｃｕｒｒｅｎｔ）を意味し、ｏｄｉｒのｏ（Ｏｌｄ）は旧を意味する。
【００８３】
ステップ１１で、変数ｉを１に設定する。ここで変数ｉは処理対象の辺が第何番目の辺であるかを示す。これらステップ１０，１１において各初期値の設定が完了する。
【００８４】
ステップ１２で、アクティブリストからｉ番目の辺データを読み出す。
【００８５】
ステップ１３で、ｏｄｉｒ＝ｃｄｉｒと設定することで、ｏｄｉｒにｃｄｉｒを代入し、さらに、ｃｄｉｒに読み出したｉ番目の辺データのｄｉｒの値を加算する。
【００８６】
ステップ１４で、ｏｄｉｒ，ｃｄｉｒの値からモード判定を行う。このモード判定は、図１７に示す規則で行われる。図１７は、ｏｄｉｒ、ｃｄｉｒの両値に基づいて、モードがどのように決定されるかを示す規則を示した図である。入力描画要素の塗りつぶし規則には非零規則と、偶奇規則があり、処理すべき描画要素がいずれの規則によって示されたデータであるかによってモード判定は異なる。
【００８７】
図１７の上段に示す判定基準はクリップ要素が偶奇規則の場合、下段が非零規則の場合の判定規準である。それぞれのケースにおいて、描画要素が偶奇規則の場合、非零規則の場合とで判定基準が異なる。図１７において、ｏｄｉｒ、ｃｄｉｒの値のいずれか一方の値のみが実線領域内にあるときに、モード＝ＩＮと判定され、それ以外の場合はモード＝ＯＵＴと判定される。点線で示された領域は、その点線領域に記載された特定条件が満足された場合のみモード＝ＩＮと判定される。図１７の点線領域は、「奇数のみ」の条件が記されており、これら点線領域の奇数にｏｄｉｒ、ｃｄｉｒの値のいずれか一方のみが該当する場合にのみ、モード＝ＩＮと判定されることを意味する。また、図１７の実線の中央部分の白丸部分は、実線には該当しない部分であることを示し、例えば図１７上段のクリップ要素が偶奇、描画要素が非零規則の場合において、２５６を含む実線部分において、ｏｄｉｒ、ｃｄｉｒのいずれかの値のみが２５６以外のこれら領域範囲内にあれば、モード＝ＩＮであるが、２５６の場合には、モード＝ＯＵＴとなる。
【００８８】
例えば、描画要素が非零規則／クリップ要素が偶奇規則でｏｄｉｒ＝０，ｃｄｉｒ＝１の場合には、いずれも実線、点線領域になく、Ｍｏｄｅ＝ＯＵＴとなる。また、描画要素が偶奇規則／クリップ要素が非零規則でｏｄｉｒ＝２５７，ｃｄｉｒ＝２５６の場合には奇数のみの点線領域にｏｄｉｒ、ｃｄｉｒが該当し、ｏｄｉｒのみが奇数のみの条件を満足しているので、Ｍｏｄｅ＝ＩＮとなる。
【００８９】
Ｍｏｄｅ＝ＩＮの場合、現在のスキャンライン（Ｙ座標）において、対象の辺（ｉ）からつぎの辺（ｉ＋１）の間で塗りつぶしが有効である。逆に、Ｍｏｄｅ＝ＯＵＴの場合、現在のスキャンラインにおいて、対象の辺からつぎの辺までの間で塗りつぶしが無効である。Ｓｔａｔｕｓ＝ＩＮは当該辺が前回のスキャンラインでＭｏｄｅ＝ＩＮであることを示し、Ｓｔａｔｕｓ＝ＯＵＴは前回のスキャンラインでＭｏｄｅ＝ＯＵＴであることを示す。
【００９０】
図１３に示すフローの説明を続ける。ステップ１４でＭｏｄｅ＝ＯＵＴと判定された場合、Ｓ２（詳細を図１４に示す）に移ってステップ２０（図１４）でｉ番目の辺のステータス情報Ｓｔａｔｕｓが読み出され、ＳｔａｔｕｓがＩＮの場合にはステップ２１へ、それ以外（ＯＵＴ，ＩＮＩＴ）の場合にはステップ２３に移る。
【００９１】
辺のステータス情報は、先に説明したように対象スキャンラインに交点を持つ辺のみで構成されたアクティブリスト（図１６参照）に、Ｄｉｒ，Ｘｓ，Ｙｅ，Ｄｘ以外に付加されたベクターに関する情報であり、ＩＮＩＴ，ＩＮ，ＯＵＴのいずれかの値を持つ。追加されたばかりの辺は、Ｓｔａｔｕｓ＝ＩＮＩＴに設定され、その後、フローに従って値の変更が実行される。
【００９２】
ステップ２１では、ｉ番目の辺データからＹ＝Ｙｓ〜Ｙｃ−１の部分を、ディスプレイリスト記憶部８３に出力する。より具体的には、例えばｉ番目の辺データが、Ｙｓ＝１０，Ｙｅ＝２０，Ｘｓ＝３．５，Ｄｘ＝０．５，Ｄｉｒ＝＋１であり、Ｙｃ＝１５の場合には、Ｙｓ＝１０，Ｙｅ＝１４，Ｘｓ＝３．５，Ｄｘ＝０．５，Ｄｉｒ＝＋１の辺データが出力される。
【００９３】
ステップ２２では、ステップ２１で出力した部分を削除するため、アクティブリスト中のｉ番目の辺データを、Ｙｓ＝Ｙｃ，Ｘｓ＝Ｘｃに変更する。
【００９４】
ステップ２３では、ｉ番目の辺データのステータスをＯＵＴ（Ｓｔａｔｕｓ＝ＯＵＴ）に変更する。
【００９５】
ステップ２４では、ｉ番目の辺データのＹｅがＹｃと等しいかどうかが判定され、等しい場合にはステップ２５でその辺をアクティブリストから削除し、等しくない場合にはステップ２６でｉを１増加させる。以上でＳ２を終了し、図１３に示すステップ１５に移る。
【００９６】
図１３に示すステップ１４でＭｏｄｅ＝ＩＮと判定された場合は、Ｓ３（詳細を図１５に示す）に移って図１５に示すステップ３０でｉ番目の辺のステータス情報Ｓｔａｔｕｓが読み出され、このＳｔａｔｕｓがＯＵＴの場合にはステップ３１へ、それ以外（ＩＮ，ＩＮＩＴ）の場合にはステップ３２に移る。
【００９７】
ステップ３１では、アクティブリスト中のｉ番目の辺データを、Ｙｓ＝Ｙｃ，Ｘｓ＝Ｘｃに変更する。
【００９８】
ステップ３２では、ｉ番目の辺データのＳｔａｔｕｓ＝ＩＮに変更する。
【００９９】
ステップ３３では、ｉ番目の辺データのＹｅがＹｃと等しいかどうかが判定され、等しい場合にはステップ３４でその辺をディスプレイリスト記憶部８３に出力してアクティブリストから削除し、等しくない場合にはステップ２６でｉを１増加させる。以上でＳ３を終了し、ステップ１５に移る。
【０１００】
図１３のステップ１５では、アクティブリスト中にｉ番目の辺があるかどうかをチェックし、あればステップ１２に、なければＳ１を終了して図１２に示すステップ５に移る。
【０１０１】
ステップ５では、ＹｃがＹｍａｘと等しいかどうかが判定され、等しい場合には処理を終了し、そうでない場合にはステップ６でＹｃを１増加させてステップ２に移る。このＹｍａｘは、対象ディスプレイリストに含まれる辺の終了スキャンラインＹ座標の最大値であり、例えば図９に示すディスプレイリストの場合にはＹｍａｘ＝１４である。
【０１０２】
以上、フローチャートを用いて説明した処理を行うと、アクティブリストは図１６に経過の一部を示すように変更され、その結果としてディスプレイリスト記憶部８３に図１８に示すクリップ処理された新たなディスプレイリストが格納される。
【０１０３】
例えば、図９にＡで示す描画要素の辺は、Ｙ＝９でクリップ要素の辺Ｂと交差してその前後で塗りつぶしの状態が変化し、ＭｏｄｅがＩＮからＯＵＴとなり、Ｓ２（図１４）において、辺を分割して、交差点の手前までの分割辺をディスプレイリスト記憶部８３に記憶し、残りの分割辺のＳｔａｔｕｓをＯＵＴの状態とする。辺Ｂの状態はそれまでＯＵＴであり（図１６のＹ＝６参照）、Ｓ２においてそのまま状態をＯＵＴに保持したままとなっている。そして、Ｙ＝９において、Ｍｏｄｅ＝ＩＮとなるのでＳ３（図１５）においてＹ＝８までの辺情報を切り捨てＹ＝９以降のみにし、ＳｔａｔｕｓをＩＮの状態に変更する。
【０１０４】
このようにしてクリップ処理を加味した新たなディスプレイリストの辺が切り出される。
【０１０５】
図１８は、図９に示すデイスプレイリストから図１２〜図１５のフローに従って生成された重なり除去後の新たなディスプレイリストである。図９と図１８を比較して理解されるように太い実線で囲まれた領域（クリップ領域）内の細実線の辺データ（描画要素）に関するディスプレイリストのみが残り、太い実線の外にある領域のベクターに関するデイスプレイリストが排除された新たなディスプレイリストが図１８に示すように生成される。
【０１０６】
尚、前記フローチャートでの処理の結果、描画要素が非零規則のディスプレイリストであっても、出力は偶奇規則に変換される。また、処理後のディスプレイリストの辺には、ｄｉｒの値が±２５６のものも含まれるが、これはそれぞれ±１に変換して出力する。
【０１０７】
また、ここでは説明を簡単にするため、クリップ処理を全て上記フローで処理するように記述したが、幾つかの条件が成立する場合には、処理をより簡単にすることができる。例えば、描画要素とクリップ要素の外接矩形が共通領域を持たない場合には、クリップ処理結果は何も出力しない状態となるのは自明である。
【０１０８】
また例えば、描画要素またはクリップ要素のどちらかが矩形であることが分かっており、矩形である図形要素にもう一方の要素の外接矩形が包含されている場合、クリップ処理は矩形でない要素のディスプレイリストを出力するだけで処理できる。また包含されていない場合でも、矩形とのクリップ処理は、Ｙ座標方向には各直線ベクターの範囲を矩形のＹ座標範囲に制約するだけでよく、残りのＸ座標方向に関しては矩形の左右辺の間にもう一方の図形要素の辺がすべて入っているかまたはすべて入っていない場合に処理を省略できる。同様の簡略化は、条件がやや異なるが、台形や三角形などの比較的単純な図形の場合にも適用できる。
【０１０９】
次に、重なり除去判定部９について詳細に説明する。
【０１１０】
図１９は、重なり除去判定部９の実施の一例を表わすブロック図である。同図において、推定処理部９１は、入力されたディスプレイリストを基にディスプレイリスト描画部１３での処理時間を推定する。判定処理部９２は、推定処理部９１での推定処理の結果を基に、重なり除去処理が必要かどうかを判定する。パラメータ記憶部９３は、推定処理部９１や判定処理部９２で必要となる処理パラメータを記憶する。
【０１１１】
前述のように、ディスプレイリスト格納部５には、１ページ分の描画要素のディスプレイリストがバンド毎に分割されて格納されている。ここまでの処理が終了した後に、重なり除去判定部９はディスプレイリストを読み出し、バンド毎に重なり除去処理が必要かどうかを判定し、その結果を重なり除去処理部１０に通知する。重なり除去処理部１０は、その判定結果に従って、重なり除去が必要と判断されたバンドに含まれているディスプレイリストについて重なり除去処理を行う。
【０１１２】
推定処理部９１にディスプレイリストが入力されると、推定処理部９１は、そのディスプレイリストにより描画される図形の外接矩形を求め、その面積と高さから以下の式により描画時間を推定する。尚、下式のａ，ｂは予め求められた係数であり、パラメータ記憶部９３に保持され、推定処理部９１に供給される。
【０１１３】
【数１】
（推定描画時間）＝ａ×（外接矩形の面積）＋ｂ×（外接矩形の高さ）
．．．．．．（１）
描画処理をＨ／Ｗなどで実行する場合、通常はメモリ部１４への書込みが処理のボトルネックとなる。メモリへの書込みは描画面積に比例し、かつスキャンライン毎の書込みでのメモリアクセスモード切換えなどのオーバーヘッドがあるので、（１）式では、描画面積を近似した外接矩形の面積に比例係数を掛け、さらに描画スキャンライン数に相当する外接矩形の高さ（＝描画要素の高さ）に比例係数を掛けた項を付加している。
【０１１４】
尚、（１）式での外接矩形面積および高さは、描画要素とクリップ要素が混在しているディスプレイリストの場合には、描画要素とクリップ要素のそれぞれの外接矩形のＡＮＤ領域が用いられる。
【０１１５】
（１）式は、メモリへの書込みがボトルネックとなる構成の図形処理装置での描画処理時間の推定式を示しているが、異なる部分がボトルネックとなる構成の場合は、それに応じた推定式を用いることは当然である。また、（１）式ではディスプレイリストから描画面積を正確に求めることの処理量を勘案して、外接矩形面積で近似を行った。しかし、推定にはメモリへの描画は必要ないため、やや処理時間がかかるものの擬似的な描画処理を行って正確な描画面積を求めることも可能である。さらに、実際の出力解像度以下の解像度で擬似的な描画処理を行い、外接矩形より正確な描画面積を求めることも可能である。
【０１１６】
また例えば、ディスプレイリスト中の辺の数が多い描画要素は形状が複雑で、外接矩形面積と実際の描画面積との差が大きい可能性がある。そのような場合には、（１）式に辺の数による補正を行って、より近い推定値を求めることができる。
【０１１７】
また、図形がある条件を満たしている場合には、描画処理を行わなくてもより正確な面積を求めることが可能である。例えば、ディスプレイリスト生成部４に入力された要素がストローク図形である場合には、直線ベクターへの近似処理後に各直線ベクターの長さと幅を乗じたものを積算することで、近似的な描画面積を求めることが可能である。尚、線種が破線などの場合には、もし線の描画部分と空白部分の比が分かればそれを使って補正すればよく、もし分からなくても、外接矩形に比べればより正確な描画面積を求められる。
【０１１８】
また、ディスプレイリスト生成部４に入力された要素がフィル図形（ストローク図形から図３に示したようにフィル図形に変換されたものを含む）であり、かつ自己交差を持たず（自己交差を持つ例については図５（ｃ）参照）、かつ単一の図形から成り立っている（例えばドーナツのように外側と内側の円が分離している場合はこれに当たらない）、と判定できる場合には、直線ベクターへの近似処理後に、例えば以下の（２）式により面積を計算できる。尚、式中の（Ｘｉ，Ｙｉ）は多角形の頂点座標を順に表わしたもので、ｎは多角形の頂点数である。また、ａｂｓ（ｘ）はｘの絶対値の意である。
【０１１９】
【数２】
0003843794.tif 000002
この方式は、交差部分で図形を分割すれば自己交差がある場合にも適用可能であり、また分離した複数図形から成り立っている場合でも各分離図形に共通領域が無い場合には適用可能である。
【０１２０】
このようにして求めた面積やその近似値はメモリ部１４での描画面積とは一致しないが、外接矩形面積よりもかなり一致度が高いため、ディスプレイリスト生成時に当該ディスプレイリストに付加情報として付与し、それに合わせて（１）式を変更することで、重なり除去判定部９での判定精度を向上させることが可能である。
【０１２１】
尚、（１）式は描画要素として文字／図形が入力された場合を示しているが、描画命令に画像が含まれており、ディスプレイリスト描画部１３で画像の輪郭を表わすディスプレイリストを処理し、図１に図示されていない画像処理手段などで処理された画像を使って、描画領域内部を１画素毎に異なる画像データで描画する場合には、その画像データの読み込みがボトルネックとなる可能性がある。そのような場合には、各ディスプレイリストに属性情報として画像であるかどうかのフラグをつけ、それに応じて推定式や係数を切り替える必要がある。
【０１２２】
推定処理部９１は、上記の処理により各ディスプレイリスト毎の推定描画時間を求め、その値をバンドについて積算して、バンドの推定描画時間を求め、その結果を判定処理部９２に出力する。
【０１２３】
判定処理部９２は、重なり除去処理の効果を判定するものであり、部分領域の推定描画時間と、パラメータ記憶部９３に予め記憶された閾値との比較を行い、その結果が閾値以下ならば重なり除去処理が不要、閾値を超える場合には重なり除去処理が必要との判定結果を出力する。重なり除去処理部１０は、この判定結果に従って、当該バンドのディスプレイリストの重なり除去を行う。
【０１２４】
判定処理に用いられる閾値は、出力デバイス１５の印字速度や推定式の誤差などから予め決定される。例えば、Ａ４長手方向を３０秒で出力するプリンタ装置であり、バンドがＡ４長手方向を均等に１２０分割したものである場合、各部分領域は０．２５秒以内で展開される必要がある。また、推定誤差が推定値０．２５秒付近で最大０．０５秒ある場合、閾値は０．２０秒に設定される。
【０１２５】
次に、重なり除去処理部１０について詳細に説明する。
【０１２６】
図２０は、重なり除去処理部１０の実施の一例を表わすブロック図である。重なり除去処理部１０は、重なり除去制御部１０１と、アクティブリスト制御部１０２と、ディスプレイリストを一時記憶する第１のディスプレイリスト記憶部１０３と第２のディスプレイリスト記憶部１０４とから構成されている。
【０１２７】
重なり除去制御部１０１は、初めに、ディスプレイリスト格納部５に格納されたディスプレイリストを描画順の後ろから取り出し、第２のディスプレイリスト記憶部１０４に一時記憶されたディスプレイリストとマージして新たなディスプレイリストを生成する。
【０１２８】
描画順の後ろから取り出す、という意味について簡単に説明する。一般的な描画において複数の描画要素を含む場合、例えば三角形Ａの上に一部重なりを持って四角形Ｂを描画し、さらに四角形Ｂに一部重なりを持って円Ｃを描画する場合、ディスプレイリスト格納部５に保持される各描画要素Ａ，Ｂ、Ｃのディスプレイリストの各々はＡ、Ｂ、Ｃの順に並べられる。これは、まず描画要素Ａに関するディスプレイリスト処理を先に行って、その後、描画要素Ｂのディスプレイリストの処理を行うことによってＡの描画データの上にＢを上書きし、さらに、最後にＣのディスプレイリスト処理を行うことで、描画要素Ｃを描画要素Ａ、Ｂの上に上書きする処理を行うためである。このようにディスプレイリスト格納部５には、印刷上、あるいは画面上において最下層となる描画要素のディスプレイリストから順に最前面表示される描画要素のディスプレイリストまでを順番に配列して保持している。
【０１２９】
本発明の図形処理装置においては、このような複数の描画要素に対応する複数のディスプレイリストがディスプレイリスト格納部５に記憶されている場合、後列に位置する、すなわち最前面表示すべき描画要素に関するディスプレイリストから先にディスプレイリスト格納部５から取り出す。例えば上述したように、三角形Ａの上に一部重なりを持って四角形Ｂが描画され、さらに四角形Ｂに一部重なりを持って、円Ｃが描画される構成を有する場合、ディスプレイリスト格納部５には、ディスプレイリストＡ、ディスプレイリストＢ、ディスプレイリストＣの順に並べられて記憶されている。この場合、本発明の図形処理装置では、ディスプレイリストＣ、ディスプレイリストＢ、ディスプレイリストＡの順に取り出す。
【０１３０】
ディスプレイリスト格納部５に格納されたディスプレイリストを描画順の後ろから取り出し、第２のディスプレイリスト記憶部１０４に一時記憶されたディスプレイリストとマージして新たなディスプレイリストを生成する際に、後の処理の必要性から、第２のディスプレイリスト記憶部１０４に含まれているベクターについては、Ｄｉｒを特定の値（例えば±２５６）に変更してマージする。この値は、クリップ処理の場合と同じく、１つのスキャンラインに交差する最大ベクタ数の２倍以上であればよく、上限がわからない場合には余裕を持って大きな値を使うこともできる。以下では、通常１２８本以上のベクタが同一スキャンライン中にあることはないとして、Ｄｉｒの値として２５６を用いた例で説明を行う。尚、マージ時に、第２のディスプレイリスト記憶部１０４に一時記憶されたディスプレイリストを、ディスプレイリスト格納部５から読み出したディスプレイリストのＹの存在範囲でクリップすれば処理をやや高速化できる。図２１にマージしたディスプレイリストの例を、図２２に第２のディスプレイリスト記憶部１０４に一時記憶されたディスプレイリストをディスプレイリスト格納部５から読み出したディスプレイリストのＹの存在範囲でクリップしてマージした例を示す。
【０１３１】
マージされたディスプレイリストを作成した後の重なり除去制御部１０１の動作は、基本的にはクリップ制御部８１と同じである。処理フローも図１２〜１５に示したクリップ処理のフローと同じなので説明を省略する。但し、図１３中のステップ１４におけるモード判定の条件が異なっており、図２３に示した条件で行われる。
【０１３２】
クリップ処理の場合と異なり、重なり除去処理では、後述のように第２のディスプレイリスト記憶部１０４には、偶奇規則のディスプレイリストしか格納されない。そのため、モード判定は入力されたディスプレイリストの塗りつぶし規則により、図２３の上段または下段の条件が適用される。
【０１３３】
尚、図１４のステップ２１、図１５のステップ３４に相当する処理では、切り出された辺データは、第１のディスプレイリスト記憶部１０３に対して出力される。
【０１３４】
以上、図１２〜図１５のフローチャートに示した処理を行うと、アクティブリストは図２５に経過の一部を示すように変更され、その結果として第１のディスプレイリスト記憶部１０３には、図２６に示すような重なりが除去された新たなディスプレイリストが格納される。図２６は、図２２に示すデイスプレイリストから図１２〜図１５のフローに従って生成された重なり除去後の新たなディスプレイリストである。図２２と図２６を比較して理解されるように太い実線で囲まれた領域（例えば描画要素Ａを構成する）内の細実線の辺データ（例えば描画要素Ｂを構成する）に関するディスプレイリストが排除され、太い実線の外にある領域のベクターに関するデイスプレイリストからのみ構成される新たなディスプレイリストが図２６に示すように生成される。
【０１３５】
尚、前記フローチャートでの処理の結果、入力描画要素が非零規則のディスプレイリストであっても、出力は偶奇規則に変換される。
【０１３６】
ここまで述べた処理により、入力ディスプレイリストの重なり除去は終了したが、重なり除去処理部１０は、さらに新たな描画要素に関する次のディスプレイリストとの重なり除去処理を行うために必要となる併合領域を表わす併合領域ディスプレイリストの生成処理を行う。すなわち、上述の処理では描画要素Ａと描画要素Ｂとの重なり除去を行ったが新たに描画要素Ｃが入力された場合に、さらに、描画要素Ｃに対する（描画要素Ａ＋描画要素Ｂ）領域との重なり除去を実行することが必要となる。従って、この新たな重なり除去処理の前に併合領域：（描画要素Ａ＋描画要素Ｂ）を求めることが必要となる。以下、この処理について説明する。
【０１３７】
始めに、再度第２のディスプレイリスト記憶部１０４に一時記憶されているディスプレイリストと入力ディスプレイリストを重なり除去制御部１０１でマージする。この時には、入力ディスプレイリストのＹ存在範囲でのクリップは行わない。
【０１３８】
次に、重なり除去制御部１０１で先に説明したのと同じ処理を行う。但し、図１３のステップ１４に示したモード判定は図２４に示した条件で行い、また図１４のステップ２１と図１５のステップ３４での辺データの出力先を、第２のディスプレイリスト記憶部１０４に変更する。
【０１３９】
その結果、第２のディスプレイリスト記憶部１０４には、入力ディスプレイリストと元々第２のディスプレイリスト記憶部１０４に一時記憶されていたディスプレイリストとを併合した領域を表わす、図２７に示す（偶奇規則の）ディスプレイリストが生成される。
【０１４０】
以上で１つの描画要素に対する重なり除去処理は終了であり、ディスプレイリスト格納部５にさらに下に描画されるディスプレイリストが保持されている場合には、それを重なり除去処理部１０に入力して、これまで述べたと同様の処理を繰り返す。この一連の処理を順次ディスプレイリスト格納部５から取り出した新たなディスプレイリストについて実行すれば、すべての描画要素の重なりが除去されたディスプレイリストが生成される。
【０１４１】
尚、ここでは第２のディスプレイリスト記憶部１０４に既にディスプレイリストが記憶されている状態での処理を説明したが、当然ながら描画順が最も後である描画要素の重なり除去を行う際には、第２のディスプレイリスト記憶部１０４には何も格納されていない。その場合には、重なり除去処理は行わずに入力ディスプレイリストをそのまま第１のディスプレイリスト記憶部１０３に出力する。併合領域生成処理については、入力ディスプレイリストが偶奇規則の場合にはそのまま第２のディスプレイリスト記憶部１０４に出力し、非零規則の場合には入力ディスプレイリストのみで処理を行う。
【０１４２】
また、当然ながら重なり除去処理を必要とする最後の描画要素に対する処理では、併合領域の生成処理は不要である。
【０１４３】
また、これまでの説明では、説明を簡略化するために全ての描画要素に対応するディスプレイリストについて重なり除去処理を行うとしたが、例えば入力ディスプレイリストと併合ディスプレイリストとの間に重なりがないと判断できる場合には、併合領域生成処理のみを行うなどの処理の簡略化も可能である。重なり判定が複雑な場合には、例えば２つのディスプレイリストの外接矩形領域を比較して重なりがない場合には重なり除去処理を省略するなどの簡易判定も考えられる。
【０１４４】
本実施例では、部分領域毎のディスプレイリストに対して、判定処理結果を基に重なり除去処理を行う例を示した。しかしながら、本実施例での重なり除去処理の目的が出力デバイス１５の印字速度に描画を間に合わせることである場合、重なり除去処理時間を短縮する手法として、次のような変更も考えられる。
【０１４５】
重なり除去が必要と判定された場合に、描画順が後の描画要素から順に処理を行い、１つの要素の処理が終了する度に先の推定値を更新する。具体的には、重なり除去処理の前と後の外接矩形領域を求め、外接矩形面積と高さが縮小した分に相当する時間を先に求めた推定描画時間から差し引く。その結果として推定時間が閾値以下となった場合には、その時点で重なり除去処理を打ち切る。
【０１４６】
ディスプレイリスト描画部１３の性能として、描画領域のＮ倍程度の上書きが発生しても出力デバイス１５の印字速度に間に合うことが明らかな場合、重なり除去の結果として単層にする必要はない。そこで、処理対象となるディスプレイリストを描画順にＭ個のグループに分け、各グループ毎に重なり除去処理を行って（単層ではなく）Ｍ層に変換する。重なり除去処理は、対象となる描画要素数の増加に対して比例以上の傾きで処理時間が増加する傾向があるので、このようにＭ個のグループに分けて処理することで、全体としての処理時間を短縮することができる。
【０１４７】
また別の方法として、処理対象のバンドをさらに細分化し、各細分化された部分領域について前記重なり除去判定部９で描画処理時間を推定し、合計推定描画処理時間が閾値以下となるまで、例えば処理の重い細分化領域から順に重なり除去処理を行う方法も考えられる。
【０１４８】
さらに、画像の取り扱いが可能な図形処理装置である場合、描画要素の下から順に一部を実際に描画処理して画像要素に変換したり、または処理対象バンドを細分化した部分領域の幾つかを処理して画像要素に変換することで、対象バンドの描画処理時間を閾値以下に低減することも可能である。
【０１４９】
次に、分割判定部１１について詳細に説明する。
【０１５０】
分割判定部１１は、図２８に示すように、分割判定の全体を制御する分割判定制御部１１１と、終点記憶部１１２とから構成されている。以下、分割判定制御部１１１の動作を、図２９に示すフローチャートに沿って説明する。
【０１５１】
初めにステップ８０において、変数変数ｉを１に設定する。ここで変数ｉは処理対象の辺が第何番目の辺であるかを示す。
【０１５２】
次ににステップ８１において、対象ディスプレイリスト中の未読み出しの辺数と終点記憶部１１２に格納されている終点数との和をチェックし、これが２Ｎ以下の場合には分割が不要との判定結果を出力して、判定処理を終了する。尚、当然であるが、処理開始時は終点記憶部１１２に格納されている終点数は０である。
【０１５３】
次にステップ８２において、対象ディスプレイリストからｉ番目の辺情報を読み出す。
【０１５４】
次にステップ８３において、変数Ｙｃをｉ番目の辺の開始スキャンラインを表わすＹ座標値Ｙｓに設定する。尚、前述のように、ディスプレイリスト中の各辺は、開始スキャンラインの昇順に格納されている。
【０１５５】
次にステップ８４において、終点記憶部１１２からＹｃ未満の要素を全て削除する。
【０１５６】
次にステップ８５において、終点記憶部１１２に、ステップ８２で読み出したｉ番目の辺の終了スキャンラインを表わすＹ座標値Ｙｅを追加する。
【０１５７】
次にステップ８６において、終点記憶部１１２に格納されている終点の数をチェックし、それが２Ｎを超えている場合には分割が必要との判定結果を出力して、判定処理を終了する。２Ｎを超えていない場合にはステップ８７に移る。
【０１５８】
次にステップ８７において、対象ディスプレイリスト中に未読み出しの辺が残っているかどうかをチェックし、残っていない場合には分割が不要との判定結果を出力して、判定処理を終了する。残っている場合にはステップ８８に移る。
【０１５９】
次にステップ８８において、ｉを１増加させて、制御をステップ８１に戻す。
【０１６０】
このような処理を行うことで、判定対象ディスプレイリストが全てのスキャンラインで辺数２Ｎ以下の場合には分割が不要、そうでない場合には分割が必要との判定結果を得ることができる。尚、ここでは全てのディスプレイリストを判定するように説明を行ったが、例えばディスプレイリスト中の辺の総数が２Ｎ以下の場合のように、明らかに分割が不要な場合は処理を省略できる。
【０１６１】
次に、分割処理部１２について説明する。
【０１６２】
分割処理部１２は、図３０に示すように、分割処理の全体を制御する分割制御部１２１と、アクティブリスト制御部１２２と、ディスプレイリストを一時記憶する第１のディスプレイリスト記憶部１２３と第２のディスプレイリスト記憶部１２４とから構成されている。以下、分割制御部１２１の動作を、非零規則の場合と偶奇規則の場合に分けて、フローチャートに沿って説明する。
【０１６３】
非零規則の場合、分割制御部１２１の動作は、図１２の部分についてはクリップ制御部８１と同じであるのでその部分の説明は省略する。先に説明した、図１３〜１５のフローの代わりに、図３１〜３３のフローに従って説明する。
【０１６４】
ステップ４０において、変数ｃｄｉｒ，ｏｄｉｒとｃｏｕｎｔをそれぞれ０に設定する。
【０１６５】
ステップ４１で、変数ｉを１に設定する。
【０１６６】
ステップ４２で、アクティブリストからｉ番目の辺データを読み出す。
【０１６７】
ステップ４３で、ｏｄｉｒ＝ｃｄｉｒと設定することで、ｏｄｉｒにｃｄｉｒを代入し、さらに、ｃｄｉｒに読み出したｉ番目の辺データのｄｉｒの値を加算する。
【０１６８】
ステップ４４で、ｏｄｉｒ，ｃｄｉｒの値からモード判定を行う。このモード判定は、ｏｄｉｒとｃｄｉｒのどちらか一方のみが０の場合にＩＮ、それ以外はＯＵＴという規則で行われる。Ｍｏｄｅ＝ＩＮの場合にはステップ４５に、ＯＵＴの場合にはＳ２に制御を移す。
【０１６９】
ステップ４５では、変数ｃｏｕｎｔの値を１増加させる。
【０１７０】
次にステップ４６で、変数ｃｏｕｎｔの値が２Ｎより大きいかどうかをチェックし、大きい場合にはＳ２に、２Ｎ以下の場合にはＳ３に制御を移す。
【０１７１】
Ｓ２に移り、図３２に示すステップ５０ではｉ番目の辺のステータス情報Ｓｔａｔｕｓが読み出され、これがＩＮの場合にはステップ５１へ、それ以外（ＯＵＴ，ＩＮＩＴ）の場合にはステップ５３に移る。
【０１７２】
ステップ５１では、ｉ番目の辺データからＹ＝Ｙｓ〜Ｙｃ−１の部分を、第１のディスプレイリスト記憶部１２３に出力する。
【０１７３】
ステップ５２では、ステップ５１で出力した部分を削除するため、アクティブリスト中のｉ番目の辺データを、Ｙｓ＝Ｙｃ，Ｘｓ＝Ｘｃに変更する。
【０１７４】
ステップ５３では、ｉ番目の辺データのＳｔａｔｕｓ＝ＯＵＴに変更する。
【０１７５】
ステップ５４では、ｉ番目の辺データのＹｅがＹｃと等しいかどうかが判定され、等しい場合にはステップ５５でその辺を第２のディスプレイリスト記憶部１２４に出力してアクティブリストから削除し、等しくない場合にはステップ５６でｉを１増加させる。以上でＳ２を終了し、図３１のステップ４７に移る。
【０１７６】
図３１のステップ４６のｃｏｕｎｔ＞２Ｎの判定がＮｏとなり、Ｓ３に移った場合は、図３３に示すステップ６０に進み、ｉ番目の辺のステータス情報Ｓｔａｔｕｓが読み出され、これがＯＵＴの場合にはステップ６１へ、それ以外（ＩＮ，ＩＮＩＴ）の場合にはステップ６３に移る。
【０１７７】
ステップ６１では、ｉ番目の辺データからＹ＝Ｙｓ〜Ｙｃ−１の部分を、第２のディスプレイリスト記憶部１２４に出力する。
【０１７８】
ステップ６２では、ステップ６１で出力した部分を削除するため、アクティブリスト中のｉ番目の辺データを、Ｙｓ＝Ｙｃ，Ｘｓ＝Ｘｃに変更する。
【０１７９】
ステップ６３では、ｉ番目の辺データのＳｔａｔｕｓ＝ＩＮに変更する。
【０１８０】
ステップ６４では、ｉ番目の辺データのＹｅがＹｃと等しいかどうかが判定され、等しい場合にはステップ６５でその辺を第１のディスプレイリスト記憶部１２３に出力してアクティブリストから削除し、等しくない場合にはステップ６６でｉを１増加させる。以上でＳ３を終了し、図３１に示すステップ４７に移る。
【０１８１】
ステップ４７では、アクティブリスト中にｉ番目の辺があるかどうかをチェックし、あればステップ４２に、なければＳ１を終了してステップ５に移る。
【０１８２】
次に、偶奇規則の場合について説明する。偶奇規則の場合、分割制御部１２１の動作は、図１２，３２，３３の部分については非零規則と同じであるので説明を省略し、図３１の変わりのフローとして図３４のフローに従う。図３４について説明する。
【０１８３】
図３４のステップ７０において、変数ｃｏｕｎｔを０に設定する。
【０１８４】
ステップ７１で、変数ｉを１に設定する。
【０１８５】
ステップ７２で、アクティブリストからｉ番目の辺データを読み出す。
【０１８６】
ステップ７３で、変数ｃｏｕｎｔの値を１増加させる。
【０１８７】
ステップ７４で、変数ｃｏｕｎｔの値が２Ｎより大きいかどうかをチェックし、大きい場合にはＳ２に、２Ｎ以下の場合にはＳ３に制御を移す。
【０１８８】
Ｓ２，Ｓ３では、図３２、図３３に示すフローに従い、非零規則の場合と同じ処理を行った後、図３４のステップ７５に制御を戻す。ステップ７５では、アクティブリスト中にｉ番目の辺があるかどうかをチェックし、あればステップ７２に、なければＳ１を終了して図１２のステップ５に移る。
【０１８９】
以上、フローチャートを用いて説明した処理を行うと、その結果として第１のディスプレイリスト記憶部１２３に図３５に示すディスプレイリストが、第２のディスプレイリスト記憶部１２４に図３６に示すディスプレイリストが格納される。図３５，３６は、図１８のディスプレイリストをＮ＝２で分割処理した場合の例である。図３５と図３６のディスプレイリストを合成すれば図１８のディスプレイリストとなる。なお、前記フローチャートでの処理の結果、入力が非零規則のディスプレイリストであっても、出力は偶奇規則に変換される。
【０１９０】
非零規則が偶奇規則に変換されるため、分割が必要と判定された場合でも、分割処理の結果は第１のディスプレイリスト記憶部１２３のみとなる場合もある。また、第１のディスプレイリスト記憶部１２３には必ず２Ｎ以下のものが格納されるが、第２のディスプレイリスト記憶部１２４に格納されるディスプレイリストは２Ｎより多くなる可能性があるので、第２のディスプレイリスト記憶部１２４にも出力が生じている場合には、そのディスプレイリストを分割判定部１１に戻し、判定／分割を繰り返す必要がある。
【０１９１】
これまで説明した、クリップ処理、重なり除去処理、分割処理の処理フローについては幾つかの変更も考えられる。例えば図１２で説明したフローでは、Ｙｍｉｎ〜Ｙｍａｘについて毎回Ｘｃを更新してソートするように説明したが、アクティブリスト中の辺データのＳｔａｔｕｓ値は辺の追加／削除／交差が生じた場合しか変更されないことから、予め追加／削除／交差の発生するＹ座標値を求めておき、そのスキャンラインのみ処理する方法も考えられる。
【０１９２】
また別の方法として、ソートを全て省略することも可能である。具体的には、ディスプレイリストから辺データをアクティブリストに移動させる際に、既にアクティブリストに登録されている全ての辺データとの交差判定を行い、交差がある場合には辺をそこで分割し、分割された辺データの前半部をアクティブリストに登録、後半部をディスプレイリストに戻す。さらに前半部を登録する際に、Ｘｃの昇順となる位置に挿入する。このようにすれば、アクティブリスト中の辺データは必ずＸｃの昇順に並んでいることが保証されるので、ソートが不要となる。交差判定はアクティブリスト中に登録されている辺との間でのみ行われるので、対象数がそれほど多くなることはなく、また２つの辺についてＸｃ１＜Ｘｃ２かつＤｘ１＜Ｄｘ２などの場合には交差のないことが明らかなので、これらを除けばさらに処理を高速化できる。
【０１９３】
尚、図１１、２０、３０やその説明からも明らかなように、図中のアクティブリスト制御部やディスプレイリスト記憶部の動作は共通であり、独立に持つ必要はない。また、図２０の重なり除去制御部１０１と、図３０の分割制御部１２１で行っているマージ処理は、前記マージ処理部７の動作と同じであるので、共通に使用しても良い。また、クリップ制御部８１、重なり除去制御部１０１、分割制御部１２１の処理は、モード判定条件を除いてほぼ同じであるので、異なる部分をパラメータ化して共通に使用しても良い。
【０１９４】
次に、ディスプレイリスト描画部１３の動作について詳細に説明する。
【０１９５】
上述の処理により、描画要求された図形は、各スキャンラインに交わる辺の数が２Ｎ本以下に制約された、混在または描画要素のみのディスプレイリスト形式のデータに変更され、描画色データなどとともにディスプレイリスト描画部１３に入力される。ディスプレイリスト描画部１３は、この入力をもとにメモリ部１４に多角形を描画する。
【０１９６】
以下、ディスプレイリスト描画部１３の動作を、描画要素のみで偶奇規則の場合を例に図３７のフローチャートを使って説明し、その後にその他の場合を説明する。
【０１９７】
初めにステップ９０において、処理対象スキャンラインを表す変数Ｙｃを、ディスプレイリストのＹ座標の最小値Ｙｍｉｎに設定する。
【０１９８】
次にステップ９１において、ＤＤＡ部１３１を用いて、現スキャンラインと各辺との交点のＸ座標値を計算してＸｃを更新する。各辺の交点のＸ座標値Ｘｃは、１回前のＸｃを使って｛Ｘｃ＋Ｄｘ｝で求めることができる。もし、ここでどの辺もＤＤＡ部１３１に設定されていない場合には、ここでは何も行われない。
【０１９９】
次にステップ９２において、入力されたディスプレイリスト中にＹｃを開始点とする辺があれば、それを空いているＤＤＡ部にセットする。ＤＤＡ部は、現在のスキャンラインとの交点Ｘ座標Ｘｃと、辺の終点Ｙ座標Ｙｅと、Ｙ座標の＋１増加に対するＸ座標の変化量Ｄｘと、方向フラグＤｉｒとを持ち、Ｘｃ＝Ｘｓ，Ｙｅ＝Ｙｅ，Ｄｘ＝Ｄｘ，Ｄｉｒ＝ＤｉｒとしてＤＤＡ部１３１に代入される。
【０２００】
次にステップ９３において、辺が設定されているＤＤＡ部１３１からＸｃの値を全てソート部１３２に出力し、ソート部１３２はこれを昇順になるようにソートし、メモリ描画部１３３に出力する。
【０２０１】
次にステップ９４において、メモリ描画部１３３でソート済みのＸ座標値を先頭から２個づつ取り出して対にし、その対間の水平線分に対応するメモリ部１４の領域を塗りつぶす。尚、各Ｘｃは小数で出力されるが、メモリ部１４への描画は整数座標の必要があるので、実際の塗りつぶしは例えばＸｃを切捨て／切上げ／四捨五入などした座標値を使って行われる。また塗りつぶしの色は、文字／図形の場合には描画色データで指定された色、画像の場合にはその座標位置に描画されるべき画素値が読み出されて用いられる。
【０２０２】
次にステップ９５において、Ｙ＝Ｙｃで終了する辺についてのＤＤＡ部１３１からの削除を行う。
【０２０３】
次にステップ９６において、Ｙｃを１だけ増加させる。次にステップ９７において、このＹｃ値が対象ディスプレイリストの存在範囲のＹ座標最大値Ｙｍａｘより大きいかどうかをチェックし、もし大きければ処理を終了し、そうでない場合にはステップ９１に戻ってＹ＝Ｙｃの処理を継続する。
【０２０４】
図３８に、このようなフローで図３５のディスプレイリストを処理した場合の、Ｙｃ＝１０からＹｃ＝１１にかけての動作の説明図を示す。図３８に示すように、各辺はＤＤＡ部１３１によりスキャンラインとの交点を求められ、ソートされ、各対の間を塗りつぶされる。ここでは、Ｎ＝２とした例であり、２Ｎ個、すなわち４個のＤＤＡ部１〜４による処理がなされる。
【０２０５】
図３８の処理について図３７の処理フローと関連づけて説明する。図３８の上段左側から処理が進行し、まず、Ｙｃ＝１０についての４つのディスプレイリストに対して４（２Ｎ）個のＤＤＡ部１〜４がＸ座標値の計算を実行（図３７、ステップ９１に相当）する。さらに、計算されたＸ座標値をソート（ステップ９３）し、描画処理を実行（ステップ９４）する。さらに、Ｙ＝１０において終了する辺、図３８に示す例の場合、ＤＤＡ部２、ＤＤＡ部３で処理されたディスプレイリストはいずれもＹｅ＝１０のデータを有し、現在の処理点Ｙ＝１０で終了する辺であると判定されるので、これらのディスプレイリストをＤＤＡ部から削除する。さらに、次のラインＹ＝１１に移動して、同様の処理を実行する。４（＝２Ｎ）個のＤＤＡ部１〜４により、このような処理をＹｍｉｎからＹｍａｘまで行うことで、入力されたディスプレイリストが表現する多角形が、効率よくメモリ部１４上に描画される。
【０２０６】
なお、描画要素とクリップ要素には、それぞれ偶奇／非零の２つの塗りつぶし規則があるので、これらを組み合わせると、ディスプレイリスト描画部１３は以下の６つのケースに対応する必要がある。
１．描画要素のみで偶奇規則
２．描画要素のみで非零規則
３．描画要素が偶奇規則で、クリップ要素が偶奇規則
４．描画要素が偶奇規則で、クリップ要素が非零規則
５．描画要素が非零規則で、クリップ要素が偶奇規則
６．描画要素が非零規則で、クリップ要素が非零規則
上記中、２．のケースは、図３７に示すステップ９４において、ソート後のＸ座標値データを先頭から２個づつ対にする代わりに、各辺のＤｉｒを積算する変数を設けて値が０でなくなる辺と０になる辺とを対にして、そのＸｃの間を描画するようにフローを変更する。
【０２０７】
また、上記中３．〜６．のケースでは、各辺のＤｉｒを積算する変数を設けて、図１７で示した条件で対となる辺を決定し、そのＸｃの間を描画するようにフローを変更する。
【０２０８】
尚、ここでは説明を簡単にするため、Ｄｉｒの値が±１または±２５６であるとして説明を行ったが、ディスプレイリスト描画部１３をハードウエアで構成する場合などビット数削減にメリットがある場合には、クリップ要素を表わす１ビットのフラグを用いて、図１７と同じ結果となる判定条件を構成することも可能である。
【０２０９】
例えば、描画要素とクリップ要素とを区別するフラグを用いたディスプレイリストを図３９に示すように構成してもよい。Ｃｆ＝１がクリップ要素の辺であることを示し、Ｃｆ＝０が描画要素の辺であることを示す。この場合にも、各辺の状態が変化するかどうかをＹ座標の増分に応じて検査して描画要素の切り出しを行なうことができる。もちろん、重なり除去についても同様に行なうことができる。
【０２１０】
図４０は、このようなフラグを用いた場合の処理Ｓ１（図１３に対応する処理）の一例を示しており、この例では、描画およびクリップの双方を偶奇規則で行っている。この図において、ｄｄｉｒは、描画処理の偶奇規則の値であり、真であれば以降の描画が有効である。ｃｄｉｒはクリップ処理の偶奇規則の値であり、真であれば以降のクリップが有効であることを示す。以下、図４０のフローを簡単に説明する。
【０２１１】
［ステップ１００］：ｄｄｉｒ＝ｃｄｉｒ＝ｆａｌｓｅに初期化する。同様に、ｏｍｏｄｅ＝ｃｍｏｄｅ＝ｆａｌｓｅに初期化する。ｃｍｏｄｅは、現在の辺（ｉ）について（その辺の右側で）、クリップを加味したうえで描画が有効か無効かを示す。ｏｍｏｄｅは、直前の辺（ｉ−１）について（直前の辺の右側すなわち現在の辺の左側で）、クリップを加味した描画が有効か無効かを示す。クリップを加味した描画が有効かどうかはｄｄｉｒとｃｄｉｒの論理積で決定される。
［ステップ１０１］：辺の番号ｉを１に初期化する。
［ステップ１０２］：アクティブリストのｉ番目の辺データを読み出す。
［ステップ１０３］：読み出した辺データが描画ベクターのものかどうかをクリップフラグＣｆで判断する。描画ベクターならステップ１０４に進み、クリップベクターであればステップ１０５に進む。
［ステップ１０４］：ｄｄｉｒを反転する。
［ステップ１０５］：ｃｄｉｒを反転する。
［ステップ１０６］：現在のｃｍｏｄｅをｏｍｏｄｅに代入して、新たなｃｍｏｄｅをｄｄｉｒとｃｄｉｒとの論離積から生成する。
［ステップ１０７］：ｃｍｏｄｅとｏｍｏｄｅを比較し、一致していればＳ２（図１４）に進み、不一致であればＳ３（図１５）に進む。
［ステップ１０８］：アクティブリストの辺がなくなるまでステップ１０２以降の処理を繰り返す。
【０２１２】
以上は、描画およびクリップに偶奇規則を適用した場合の例であるが、それ以外の態様で処理を行なえることはもちろんである。例えば、図４１は、描画に非零規則を適用し、クリップに偶奇規則を適用したものである。また図４２は、描画に偶奇規則を適用し、クリップに非零規則を適用したものである。さらに、図４３は、描画およびクリップの双方に非零規則を適用したものである。
【０２１３】
図４１においては、ステップ１００およびステップ１０４（図４０）に代えてステップ１００’およびステップ１０４’を行なう。この図において、ｄｏｖａｌは描画要素の非零規則の直前の値、ｄｃｖａｌは描画要素の非零規則の現在の値を示す。この図の動作は図１３および図４０とほぼ同様であり、詳細な説明は省略する。
【０２１４】
図４２においては、ステップ１０１およびステップ１０５（図４０）に代えてステップ１００’’およびステップ１０５’を行なう。この図の動作も図１３および図４０とほぼ同様であり、詳細な説明は省略する。
【０２１５】
図４３においては、ステップ１００（図４０）に代えてステップ１００’’を行なう。また、ステップ１０４およびステップ１０５に代えてステップ１０４’およびステップ１０５’を行なう。この図において、ｃｏｖａｌはクリップ要素の非零規則の直前の値、ｃｃｖａｌはクリップ要素の非零規則の現在の値を示す。この図の動作も図１３および図４０とほぼ同様であり、詳細な説明は省略する。
【０２１６】
なお、クリップ処理を行なってどの描画要素あるいはクリップ要素の辺を新たなディスプレイリストの構成要素とするか、あるいは新たな辺として切り出すかは、上述の手順（図１３等）以外でも行なうことが可能である。要するに、切り出すための条件を設定し、それを満たすかどうかを判断しながら行なえばよい。
【０２１７】
また、上述実施例においては、ディスプレイリストの辺（直線ベクター）は昇順に格納され、順次に辺情報を取り出し、並列にＤＤＡ演算を行なえるかどうかを判断し、行なえない場合にはディスプレイリストを分割するようにしているが（図２９）、スキャンラインごとに順次それを開始点とする辺の情報を取出して、同様に分割が必要かどうかを判断するようにしてもよい。
【０２１８】
このような判断手順の処理を図４４に示す。図４４の処理を簡単に説明する。なお、処理の内容は図から容易に理解できるため詳細な説明は省略する。
【０２１９】
［ステップ８１’］：対象スキャンラインを表すＹｃをＹｍｉｎに設定する。このＹｍｉｎは判定対象のディスプレイリストのＹの存在範囲の最小値である。
［ステップ８２’］：判定対象のディスプレイリスト中にＹｃを開始点とする辺があれば、その辺の終了スキャンラインＹｅを終点記憶部１１２に格納する。
［ステップ８３’］：終点記憶部１１２ぶ格納されている終点の数をチェックし、それが２Ｎを越えている場合には分割が必要との判定結果を出力して判定を終了する。２Ｎを越えていなければステップ８４’に進む。
［ステップ８４’］：ＹｃがＹｍａｘと等しいかどうかをチェックし、等しい場合には分割が不要との判定結果を出力して判定処理を終了する。このＹｍａｘは判定対象のディスプレイリストのＹの存在範囲の最大値である。ＹｃがＹｍａｘと等しくない場合にはステップ８５’に進む。
［ステップ８５’］：Ｙｅ＝Ｙｃなる終点記憶部１１２の要素すべてを削除する。
［ステップ８６’］：Ｙｃの値を１増加させて、ステップ８２’に戻る。
【０２２０】
このような処理を行なうことで、判定対象ディスプレイリストがすべてのスキャンラインで辺数２Ｎ以下の場合には分割が不要、そうでない場合には分割が必要との判定結果を得ることができる。なお、ここではすべてのディスプレイリストを判定するようにしたが、例えば、ディスプレイリスト中の辺の総数が２Ｎ以下の場合のように、明らかに分割が不要な場合には処理を省略できる（図２９）。
【０２２１】
【発明の効果】
以上説明したように本発明では、ディスプレイリスト形式で表現された描画要素間の重なりを除去する重なり除去手段を持ち、エッジリストと比較して高解像度の場合でも少ないメモリ量での蓄積を可能とし、また特別な前処理を行わずかつ少ない処理で重なり除去が可能な、高速の図形処理装置を実現することができる。さらに、重なり除去処理が必要かどうかを判定する判定手段と、クリップ要素と描画要素が混在したディスプレイリストをクリップ処理して描画要素のみのディスプレイリストに変換するクリップ処理手段とを持つことで、重なり除去処理を必要最小限に抑え、かつクリップ要素と描画要素とが混在している場合でも対応可能な、高速の図形処理装置を実現することができる。
【０２２２】
また本発明では、ディスプレイリストから全てのスキャンラインで交差する辺の数が２Ｎ（＝ＤＤＡ手段の数）以下となるかどうかを判定する判定手段と、クリップ要素と描画要素が混在したディスプレイリストをクリップ処理して描画要素のみのディスプレイリストに変換するクリップ処理手段と、描画要素のディスプレイリストを全てのスキャンラインで交差する辺の数が２Ｎ以下となる複数のディスプレイリストに分割する分割手段と、２Ｎ個（Ｎは１以上）のＤＤＡ手段と、ＤＤＡ手段から出力された入力をソート可能なソート手段を有する構成としたことにより、描画命令中にクリップ要素と描画要素とが混在している場合でも、描画要素のみのディスプレイリストとする処理、またディスプレイリストをＤＤＡ手段の数である２Ｎ以下の分割ディスプレイリストに分割する処理を実行した後、並列処理可能な２Ｎ個のＤＤＡ手段による変換生成されたディスプレイリストに基づく位置情報算出処理を実行するように構成したので、描画データの小さな領域での管理および記憶が可能となり、かつクリップ要素と描画要素とが混在している場合でも分割図形をなるべく小さな領域で管理／記憶でき、高速に処理可能な図形処理装置を実現することができる。
【図面の簡単な説明】
【図１】  本発明の図形処理装置の実施例を示すブロック図である。
【図２】  既存の図形処理装置の一例を示すブロック図である。
【図３】  線図形の塗りつぶし図形への変換を説明する図である。
【図４】  曲線の微小直線での近似を説明する図である。
【図５】  各種の多角形を示す図である。
【図６】  ベジエ曲線の再帰的な分割を説明する図である。
【図７】  ディスプレイリストを説明する図である。
【図８】  描画要素とクリップ要素との混在ディスプレイリストを説明する図である。
【図９】  混在ディスプレイリストのＹ方向クリップを説明する図である。
【図１０】  本発明の図形処理装置における部分領域への分割を説明する図である。
【図１１】  本発明の図形処理装置におけるクリップ処理部の一例を示すブロック図である。
【図１２】  本発明の図形処理装置におけるクリップ処理の手順を示すフローチャート（その１）である。
【図１３】  本発明の図形処理装置におけるクリップ処理の手順を示すフローチャート（その２）である。
【図１４】  本発明の図形処理装置におけるクリップ処理の手順を示すフローチャート（その３）である。
【図１５】  本発明の図形処理装置におけるクリップ処理の手順を示すフローチャート（その４）である。
【図１６】  アクティブリストを説明する図である。
【図１７】  本発明の図形処理装置におけるクリップ処理でのモード判定を説明する図である。
【図１８】  本発明の図形処理装置におけるクリップ処理後に出力されるディスプレイリストを説明する図である。
【図１９】  本発明の図形処理装置における重なり除去判定部の一例を示すブロック図である。
【図２０】  本発明の図形処理装置における重なり除去処理部の一例を示すブロック図である。
【図２１】  描画要素と併合領域との混在ディスプレイリストを説明する図である。
【図２２】  混在ディスプレイリストのＹ方向クリップを説明する図である。
【図２３】  本発明の図形処理装置装置における重なり除去処理でのモード判定を説明する図である。
【図２４】  本発明の図形処理装置装置における重なり除去（併合領域生成）処理でのモード判定を説明する図である。
【図２５】  アクティブリストを説明する図（その２）である。
【図２６】  本発明の図形処理装置における重なり除去処理されたディスプレイリストを説明する図である。
【図２７】  本発明の図形処理装置における併合処理されたディスプレイリストを説明する図である。
【図２８】  本発明の図形処理装置における分割判定部の一例を示すブロック図である。
【図２９】  本発明の図形処理装置における分割判定処理の手順を示すフローチャートである。
【図３０】  本発明の図形処理装置における分割処理部の一実施例を示すブロック図である。
【図３１】  本発明の図形処理装置における分割処理の手順を示すフローチャート（その１）である。
【図３２】  本発明の図形処理装置における分割処理の手順を示すフローチャート（その２）である。
【図３３】  本発明の図形処理装置における分割処理の手順を示すフローチャート（その３）である。
【図３４】  本発明の図形処理装置における分割処理の手順を示すフローチャート（その４）である。
【図３５】  本発明の図形処理装置における分割処理後に出力されるディスプレイリストを説明する図である。
【図３６】  本発明の図形処理装置における分割処理後に残されるディスプレイリストを説明する図である。
【図３７】  本発明の図形処理装置におけるディスプレイリスト描画処理の手順を示すフローチャートである。
【図３８】  本発明の図形処理装置におけるディスプレイリスト描画処理を説明する図である。
【図３９】  ディスプレイリストの変形例を説明する図である。
【図４０】  変形例におけるクリップ処理および重なり除去処理を説明するフローチャートである。
【図４１】  他の変形例におけるクリップ処理および重なり除去処理を説明するフローチャートである。
【図４２】  さらに他の変形例におけるクリップ処理および重なり除去処理を説明するフローチャートである。
【図４３】  さらに他の変形例におけるクリップ処理および重なり除去処理を説明するフローチャートである。
【図４４】  他の変形例における分割判定処理を説明するフローチャートである。
【符号の説明】
１    命令解釈部
２    ベクターデータ生成部
３    フォント管理部
４    ディスプレイリスト生成部
５    ディスプレイリスト格納部
６    部分領域分割部
７    マージ処理部
８    クリップ処理部
９    重なり除去判定部
１０    重なり除去処理部
１１    分割判定部
１２    分割処理部
１３    ディスプレイリスト描画部
１４    メモリ部
１５    出力デバイス
８１    クリップ制御部
８２    アクティブリスト制御部
８３    ディスプレイリスト記憶部
９１    推定処理部
９２    判定処理部
９３    パラメータ記憶部
１０１    重なり除去制御部
１０２    アクティブリスト制御部
１０３    ディスプレイリスト記憶部１
１０４    ディスプレイリスト記憶部２
１１１    分割判定制御部
１１２    終点記憶部
１２１    分割制御部
１２２    アクティブリスト制御部
１２３    ディスプレイリスト記憶部１
１２４    ディスプレイリスト記憶部２
【図１】
0003843794.tif 000003
【図２】
0003843794.tif 000004
【図３】
0003843794.tif 000005
【図４】
0003843794.tif 000006
【図５】
0003843794.tif 000007
【図６】
0003843794.tif 000008
【図７】
0003843794.tif 000009
【図８】
0003843794.tif 000010
【図９】
0003843794.tif 000011
【図１０】
0003843794.tif 000012
【図１１】
0003843794.tif 000013
【図１２】
0003843794.tif 000014
【図１３】
0003843794.tif 000015
【図１４】
0003843794.tif 000016
【図１５】
0003843794.tif 000017
【図１６】
0003843794.tif 000018
【図１７】
0003843794.tif 000019
【図１８】
0003843794.tif 000020
【図１９】
0003843794.tif 000021
【図２０】
0003843794.tif 000022
【図２１】
0003843794.tif 000023
【図２２】
0003843794.tif 000024
【図２３】
0003843794.tif 000025
【図２４】
0003843794.tif 000026
【図２５】
0003843794.tif 000027
【図２６】
0003843794.tif 000028
【図２７】
0003843794.tif 000029
【図２８】
0003843794.tif 000030
【図２９】
0003843794.tif 000031
【図３０】
0003843794.tif 000032
【図３１】
0003843794.tif 000033
【図３２】
0003843794.tif 000034
【図３３】
0003843794.tif 000035
【図３４】
0003843794.tif 000036
【図３５】
0003843794.tif 000037
【図３６】
0003843794.tif 000038
【図３７】
0003843794.tif 000039
【図３８】
0003843794.tif 000040
【図３９】
0003843794.tif 000041
【図４０】
0003843794.tif 000042
【図４１】
0003843794.tif 000043
【図４２】
0003843794.tif 000044
【図４３】
0003843794.tif 000045
【図４４】
0003843794.tif 000046