(57)【特許請求の範囲】
【請求項１】
描画すべき描画データを入力する描画データ入力手段と、描画された順序通りにメモリ上にデータを上書きしていく描画方式を用いて描画処理を行う第１の描画処理手段と、前記描画データから生成された中間コードの状態で描画図形の重なりを除去する処理を行う描画方式を用いて描画処理を行う第２の描画処理手段と、前記第１および第２の描画処理手段における処理負荷あるいは処理時間を推定する処理負荷推定手段と、前記処理負荷推定手段により推定された前記第１および第２の描画処理手段における処理負荷あるいは処理時間に基づいてもっとも高速に処理できる描画処理手段を選択する描画方式選択手段を備えることを特徴とする描画処理装置。
【請求項２】
前記処理負荷推定手段は、図形を描画するベクタのスキャンライン上の存在頻度を処理負荷として用いることを特徴とする請求項１に記載の描画処理装置。
【請求項３】
前記処理負荷推定手段は、前記第１の描画処理手段の処理負荷として描画面積を使用し、前記第２の描画処理手段の処理負荷として描画する図形の辺のスキャンライン上の存在頻度を使用することを特徴とする請求項１に記載の描画処理装置。
【請求項４】
固定的な描画方式を設定する設定手段を有し、前記描画方式選択手段は、前記設定手段で固定的な描画方式が設定された場合には設定された描画方式を選択することを特徴とする請求項１ないし請求項３のいずれか１項に記載の描画処理装置。
【請求項５】
前記描画方式選択手段は、ジョブ単位で前記第１または第２の描画処理手段を選択することを特徴とする請求項１ないし請求項４のいずれか１項に記載の描画処理装置。
【請求項６】
前記描画方式選択手段は、ページ単位で前記第１または第２の描画処理手段を選択することを特徴とする請求項１ないし請求項４のいずれか１項に記載の描画処理装置。
【請求項７】
前記描画方式選択手段は、バンド単位で前記第１または第２の描画処理手段を選択することを特徴とする請求項１ないし請求項４のいずれか１項に記載の描画処理装置。
【請求項８】
前記描画方式選択手段は、ライン単位で前記第１または第２の描画処理手段を選択することを特徴とする請求項１ないし請求項４のいずれか１項に記載の描画処理装置。
【請求項９】
前記描画データからベクタ形式の中間コード形式を生成する中間コード生成手段を有し、前記第１および第２の描画処理手段は、前記中間コード形式から描画処理を行うものであることを特徴とする請求項１ないし請求項８のいずれか１項に記載の描画処理装置。
【請求項１０】
前記描画データから台形形式の中間コード形式を生成する中間コード生成手段を有し、前記第１および第２の描画処理手段は、前記中間コード形式から描画処理を行うものであることを特徴とする請求項１ないし請求項８のいずれか１項に記載の描画処理装置。
【請求項１１】
前記描画データからランレングス形式の中間コード形式を生成する中間コード生成手段を有し、前記第１および第２の描画処理手段は、前記中間コード形式から描画処理を行うものであることを特徴とする請求項１ないし請求項８のいずれか１項に記載の描画処理装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、描画データに基づいて描画処理を行う描画処理装置に関するものである。
【０００２】
【従来の技術】
ＰｏｓｔＳｃｒｉｐｔ（登録商標）やＧＤＩなどの描画データを処理する描画処理装置においては、入力された描画データを、出力装置に応じたビットマップデータ等に展開する描画処理を行う。図１７は、従来の描画処理の一例を示すフローチャートである。Ｓ１０１において描画データを入力すると、Ｓ１０２において、入力された描画データに対応する中間コードを生成し、Ｓ１０３において、Ｓ１０２で生成した中間コードを蓄積しておく。Ｓ１０４において、ページ内の描画データが全て終了したか否かを判定し、１ページ分の描画データに対する処理が終了するまで、Ｓ１０１〜Ｓ１０３の処理を繰り返す。これによって、１ページ分の描画データに対応する中間コードが蓄積される。
【０００３】
その後、Ｓ１０５において、例えば１ページ単位や、１ページを帯状領域に分割したバンド単位などの単位毎に中間コードを取得し、Ｓ１０６において、その特定の単位毎に描画処理を行う。この時の描画処理は、予め組み込まれている特定の１つの描画方式を用いて行われる。Ｓ１０７において、すべての単位の中間コードを処理したか否かを判定し、全ての単位の処理が終了するまでＳ１０５及びＳ１０６の処理を繰り返す。このようにして、１ページ分の描画データに対応する画像を描画することができる。
【０００４】
上述のＳ１０６で説明したように、従来は同一の装置においては単一の描画処理方法を用いて描画処理を行っていた。描画処理方法の一つとして、例えば特開平９−１７１５６４号公報等に開示されているように、中間コードと展開用のバンドメモリを用いる方法がある。この方法は、出力されるページを短冊状に区切ったバンドに対応づけて１ページ分の中間コードを蓄積し、バンド単位に中間コードを取り出し、入力された描画データを順序どおりにバンドメモリ上に上書きするものである。この描画処理方法は、図１７における単位が「バンド単位」であり、特定の描画方式として「バンドメモリを使用した上書き処理」が相当する。この方式では、メモリ上で上書き処理を行うため、書き込み面積が大きくなると性能が悪くなるという問題がある。
【０００５】
また、別の描画処理方法として、例えば特開平１０−７９０３８号公報等に開示されているように、ベクタ形式のデータで蓄積し、スキャンライン毎にデータを取得して、クリップ処理と塗りつぶし処理を同時に行い、重なりが除去された状態でスキャンラインデータを出力している。この描画処理方法は、図１７における単位が「スキャンライン単位」であり、特定の描画方式として「クリップ処理と塗りつぶし処理を同時に行いかつ重なりも同時に除去する処理」が対応する。しかしこの描画処理方法では、スキャンライン上のデータをソートする必要があるため、入力されたデータが少ない場合にはソートのオーバヘッドにより、メモリ上書き方式に比べて性能が悪いという問題がある。
【０００６】
このように、それぞれの描画処理方法には一長一短がある。従来方式では、単一の描画処理方法を採用しているため、描画処理方式の特性により性能が悪化する場合があるという問題があった。
【０００７】
一方、それぞれの描画処理方式では、あるパラメータによって処理時間を予測できるようになってきている。処理時間を予測して、予測結果に応じて何か処理を行う技術が多数公開されている。例えば特開平８−２７９０５０号公報には、処理時間を予測した結果から実時間展開可能か否かを判断し、実時間展開不可能の場合にはラスタ形式に変換する技術が開示されている。さらに、例えば特開平１０−３０７６８９号公報には、処理時間を予測した結果から、実時間展開できない場合には、展開時間を短縮可能な中間コード形式に変更する技術が開示されている。同様に特開平１１−１９８４８９号公報には、予め定められた処理時間に対して高速に処理できる中間コード形式を選択する技術が開示されている。また特開平１０−３０７９２４号公報には、処理時間を予測した結果を用いて、並列処理における負荷均一化に適用する例が記載されている。
【０００８】
このように、それぞれの描画処理方法について処理時間を予測し、その描画処理方法で実時間展開ができない場合にはデータ形式の変更などの時間がかかる処理を予め行うことで対処していた。例えば他の描画処理方法で実時間展開が可能な場合であっても、他の描画処理方法が用いられることはなかった。そのため、描画処理に時間がかかっていた。
【０００９】
【発明が解決しようとする課題】
本発明は、上述した事情に鑑みてなされたもので、高速な描画処理を実現した描画処理装置を提供することを目的とするものである。
【００１０】
【課題を解決するための手段】
本発明では、描画された順序通りにメモリ上にデータを上書きしていく描画方式と、中間コード上で重なり処理を行う描画方式から、描画方式選択手段で選択された描画方式を用いて描画処理を行うことができる。例えば処理負荷推定手段により推定された描画方式毎の処理負荷あるいは処理時間に基づいて、もっとも高速に処理できる描画方式を選択して描画処理を行うことができる。これによって、単一の描画方式を用いた場合に描画処理の遅延が発生していた場合でも、他の描画方式の利点を活かして高速な描画処理を行うことができる。この場合、描画処理時間を低減するものであるため、他のデータ形式の変換などによる処理時間の遅延も抑えることができ、全体として処理の高速化を図ることができる。
【００１１】
なお、描画方式の選択は、固定的な描画方式が設定された場合には設定された描画方式を選択するように構成することも可能である。また描画方式の選択単位は、ジョブ単位、ページ単位、バンド単位、ライン単位などとすることができる。また、描画データを例えばベクタ形式、台形形式、ランレングス形式などの形式の中間コードに変換してから、描画処理を行うように構成することができる。
【００１２】
【発明の実施の形態】
図１は、本発明の描画処理装置の実施の一形態を示すブロック図である。図中、１は描画データ入力部、２は中間コード生成部、３は中間コード蓄積部、４−１〜ｎは描画負荷推定部、５は描画方式選択部、６は描画部、７−１〜ｎは描画方式、８は出力装置である。描画データ入力部１は、描画データを入力する。描画データは、文字、図形、ラスタ画像等から構成される。中間コード生成部２は、入力された描画データから中間コードを生成する。中間コード蓄積部３は、生成された中間コードを例えば１ページ分蓄積する。
【００１３】
描画負荷推定部４−１〜ｎは１ないし複数設けられ、生成された中間コードから各描画方式７−１〜ｎにおける処理時間あるいは処理時間に対応する処理負荷などを推定する。もちろん、描画方式の個数に合わせて設ける必要はなく、描画方式よりも少ない個数でもよいし、また、１つの描画方式についていくつかの推定方法により処理時間や処理負荷を推定してもよい。
【００１４】
描画方式選択部５は、１ないし複数の描画負荷推定部４−１〜ｎが推定した結果を基にして、複数の描画方式７−１〜ｎの中から最適な描画方式を選択する。描画部６は、描画方式選択部５によって選択された描画方式を使用して、中間コード蓄積部３に蓄積されている中間コードをもとにして描画処理を行い、出力装置８に対して出力する。
【００１５】
図２は、本発明の描画処理装置の実施の一形態における動作の一例を示すフローチャートである。図２では、一例として、１ページ毎に中間コードデータを蓄積し、ページ内で２つの描画方式（描画方式ａ，ｂ）を切り替える場合について示している。
【００１６】
Ｓ１１において描画データ入力部１に描画データが入力されると、Ｓ１２において、中間コード生成部２は入力された描画データに対応する中間コードデータを生成する。次にＳ１３において、各描画負荷推定部４−１〜ｎは、生成された中間コードの各種プロファイル情報を用いて、それぞれの描画方式で描画したときの描画処理にかかる負荷を、描画処理を切り替える単位毎に計算する。またＳ１４において、中間コード生成部２が生成した中間コードを中間コード蓄積部３に蓄積する。なお、描画負荷の計算と中間コードの蓄積は前後しても構わない。Ｓ１５においてページ内の描画データが終了したか否かを判定し、未処理の描画データが存在する場合には、Ｓ１１へ戻って、以上の処理を繰り返す。これによって、Ｓ１１〜Ｓ１４の処理を、１ページの描画データが終了するまで繰り返す。
【００１７】
１ページ分の描画データに対する処理が終了したら、Ｓ１６において、描画方式選択部５は、処理単位毎に各描画方式毎の負荷を描画負荷推定部４−１〜ｎから取得し、どの処理方式が高速に処理できるかを判定し、描画処理を行う描画方式を決定する。ここでは、描画方式ａの描画負荷が閾値より大きいか否かをＳ１７で判定し、閾値以内であればＳ１８において描画方式ａを選択する。また、描画方式ａの描画負荷が閾値より大きい場合には、Ｓ１９において描画方式ｂを選択する。そして、Ｓ１８またはＳ１９において、描画方式選択部５で選択された描画方式を用いて、描画部６により描画処理を実行する。そして描画結果を出力装置８へ出力する。
【００１８】
次に、全ての単位について処理が終わったか否かをＳ２０で判定し、処理が終わっていなければＳ１６へ戻って所定の単位毎の描画方式の選択及び選択された描画方式による描画処理を繰り返す。全ての単位について処理を終えたら、１ページ分の描画処理を終了する。
【００１９】
このようにして、所定の単位毎にそれぞれの描画方式について処理負荷を推定し、より好ましい描画方式を選択して、その描画方式を用いて描画処理を行うことができる。そのため、単一の描画方式では処理負荷が大きくなる場合でも、他の描画方式を用いることによって処理負荷を低減し、高速に描画処理を行うことができる。
【００２０】
図３は、本発明の描画処理装置の実施の一形態における描画方式の切替処理の概念図である。図３では、描画負荷推定部４−１，２で推定される処理負荷と、その処理負荷の時に描画部６で描画処理を行ったときの処理時間との関係を示している。例えば描画方式ａは、処理負荷が小さいときには描画処理時間が小さいが、処理負荷の増大とともに飛躍的に描画処理時間が増大するような描画方式であるとする。また、描画方式ｂは、処理負荷が小さいときにもそれほど描画処理時間は短くならないものの、処理負荷が増大しても描画処理時間の増加はそれほどでもないような描画方式であるものとする。
【００２１】
この場合、処理負荷が小さい場合には描画方式ａの方が描画処理時間は短く、処理負荷が大きい場合には描画方式ｂの方が描画処理時間は短くなる。従って、両者の交差する処理負荷を閾値として、推定された処理負荷が閾値以下であれば描画方式ａを選択し、閾値よりも推定された処理負荷が大きい場合には描画方式ｂを選択すれば、処理負荷の多少に関わらず描画処理時間は最小となり、常に高速に描画処理を行うことができる。
【００２２】
なお、上述のＳ１７及び図３においては、描画方式ａの処理負荷を用いて、描画方式の選択を行っている。しかし、この選択条件は一例であって、様々な判定条件を設定することが可能であり、例えば描画方式ａの処理負荷と描画方式ｂの処理負荷の大小を比較したり、あるいは、描画処理時間を推定して描画処理時間で描画方式の選択を行ってもよい。
【００２３】
以下、具体例を用いて上述の構成及び動作について説明してゆく。以下に説明する具体例では、中間コードとしてベクタ形式のデータを使用し、バンドメモリを用いて重なり処理を行う描画方式ａと、中間コード上で重なり処理を行ってからバンドメモリにデータを書き込む描画方式ｂを使用する。描画処理の負荷としてスキャンライン上のベクタの存在頻度を用いて、バンド毎に処理を切り替える。切り替え方法として、例えば上述の図３で説明したように、予め定められた負荷の閾値より小さい場合には描画方式ａを、大きい場合には描画方式ｂを選択するものとして、以下説明してゆく。
【００２４】
まず、２つの描画方式について説明しておく。図４は、描画方式ａの一例の説明図、図５は、描画方式ｂの一例の説明図である。ここでは図４（Ａ）及び図５（Ａ）に示すように、３つの描画データが入力されたものとする。描画順序は、下が先に描画されるデータ、上が後から描画されるデータであるとする。すなわち▲１▼，▲２▼，▲３▼の順で描画されるものとする。なお、それぞれの描画データについては、図示の都合上、異なるハッチングを付して区別している。
【００２５】
描画方式ａは、描画された順序どおりにメモリ上にデータを上書きしていく方式である。すなわち、図４（Ｂ）において▲１▼のデータを最初にメモリ上に書き込む。次に図４（Ｃ）に示すように▲２▼のデータ、最後に図４（Ｄ）に示すように▲３▼のデータを書き込む。このようにして▲１▼〜▲３▼のデータを描画する。
【００２６】
描画方式ｂは、中間コードをスキャンライン上の座標値順にソートし、スキャン順に上側の描画オブジェクトを選択して、必要な部分だけをメモリ上に書き込む方式である。まず図５（Ｂ）において、最初に▲３▼の描画開始点が取得されるが、これ以前にどの描画データも描画開始となっていないので、この座標値を描画開始点として記憶するにとどめる。次に図５（Ｃ）において、▲２▼の描画開始点が取得されるが、すでに▲２▼より後に描画される▲３▼が描画開始となっているので何もしない。次に図５（Ｄ）において、▲３▼の描画終了点が取得され、描画が開始している描画データの中で一番上なので、描画開始点からこの座標値まで▲３▼を描画し、描画開始点を更新する。次に図５（Ｅ）において、▲１▼の描画開始点が取得されるが、すでに▲１▼より後に描画される▲２▼が描画開始となっているので何もしない。次に図５（Ｆ）において、▲２▼の描画終了点が取得され、描画が開始している描画データの中で一番上なので、描画開始点からこの座標値まで▲２▼を描画し、描画開始点を更新する。次に図５（Ｇ）において、▲１▼の描画終了点が取得され、描画が開始している描画データの中で一番上なので、描画開始点からこの座標値まで▲１▼を描画し、描画開始点を更新する。このようにして▲１▼〜▲３▼のデータを描画する。
【００２７】
図６は、描画方式ａによる１つのバンドの描画処理の一例を示すフローチャートである。まずＳ３１において、出力に使用するバンドメモリをクリアする。次にＳ３２において、描画データの描画順に中間コードを取得する。次にＳ３３において、中間コード内のデータを１スキャンライン分だけ取得する。最初は、最上部（バンドメモリの上側方向から順に書き込む場合。逆にバンドメモリの下側から書き込む場合には最下部）のスキャンラインに対応するデータを取得する。
【００２８】
次にＳ３４において、中間コードが保持している描画開始点と描画終了点の座標値を取得し、Ｓ３５において、これらの座標値を基に、メモリの書き込み開始位置を計算する。またＳ３６において、中間コードからこのスキャンライン上の描画データの幅を取得する。さらにＳ３７において、中間コードからこの描画データの色データを取得する。そしてＳ３８において、実際のメモリ書き込みを行う。
【００２９】
次にＳ３９において、スキャンライン上のデータが無くなったか否かを判断し、まだ残っていれば、Ｓ３４へ戻って、スキャンライン上の処理（メモリ書き込み位置の計算から幅分データの上書きまで）を繰り返す。スキャンライン上のデータが無くなった場合には、Ｓ４０において、取得した中間コードの処理が終了したか否かを判断する。まだ残っている場合には、Ｓ３３の１スキャンライン上のデータ取得に戻って繰り返す。取得した中間コードの処理が終わった場合には、Ｓ４１において、バンド内の描画データをすべて処理したか否かを判断する。まだ残っている場合には、Ｓ３２に戻り、描画順に中間コードを取得して、中間コードに対する処理を繰り返す。すべての中間コードを処理した場合には、１つのバンド内の処理を終了する。
【００３０】
図７は、描画方式ｂによる１つのバンドの描画処理の一例を示すフローチャートである。まずＳ５１において、出力に使用するバンドメモリをクリアする。次にＳ５２において、スキャンライン上のデータをすべて取得する。最初は、最上部の（描画方式ａと同様に、最下部でも可能）スキャンライン上のデータを全て取得することになる。
【００３１】
次にＳ５３において、最も左側の描画点（左から右に描画する場合。右から左に描画する場合には最も右側の描画）を取得する。次にＳ５４において、Ｓ５３で取得した描画点が描画開始点であるか否かを判断する。
【００３２】
描画点が描画開始点である場合、Ｓ５５において、この描画データが描画開始になったことを登録しておく。次にＳ５６において、描画開始している描画データ内で最も上側（描画順で後に描画された）データであるか否かを判断し、最も上側である場合には、さらにＳ５７において、この描画データより下（描画順で前に描画されたデータ）があるか否かを判断する。この描画データより下（あるいは上）がある場合には、Ｓ５８において、下側の描画データの色で描画開始点から注目点（描画開始になった描画データの座標点）の左側の点までを描画し、Ｓ５９において描画開始点を注目点に変更する。描画を開始しているデータ内で最も上側でない場合、または下側で描画開始している描画データが無い場合には、Ｓ５９の描画開始点の変更までの処理をスキップしてＳ６２に進む。
【００３３】
Ｓ５４で描画点が描画開始点ではないと判断された場合（描画終了点）、Ｓ６０において、描画開始している描画データ内で最も上側であるか否かを判断し、最も上側である場合には、Ｓ６１において、この描画データの色で塗り開始点から注目点の左側の点までを描画し、Ｓ５９において描画開始点を注目点に変更する。描画を開始しているデータ内で最も上側ではない場合、Ｓ５９の描画開始点の変更までの処理をスキップしてＳ６２へ進む。
【００３４】
Ｓ６２において、スキャンライン上のデータをすべて処理したか否かを判断し、まだ残っている場合には、Ｓ５３の最左の描画点の取得の処理まで戻って繰り返す。すべてのスキャンライン上のデータを処理した場合には、Ｓ６３において、まだバンド内に処理していないスキャンラインがあるか否かを判断し、まだ残っている場合には、Ｓ５２のスキャンライン上のデータ取得の処理まで戻って繰り返す。すべて処理した場合には、１つのバンド内の処理を終了する。
【００３５】
このような描画方式ａあるいは描画方式ｂのいずれかを選択して描画処理を行うことになるが、いずれの描画方式を用いるかを、この例ではスキャンライン上のベクタの存在頻度を描画処理の負荷として用いて切り替える。ここで、このベクタについて説明しておく。図８は、ベクタのデータ形式の一例の説明図、図９は、ベクタの具体例の説明図である。ベクタは、例えば図８に示すようなデータ表現をとることができる。図８に示すベクタのデータ形式において、「順序」は描画コマンドの描画順序である。「Ｘ」は現在のスキャンラインを横切るベクタのＸ切片の値を示す。「Ｘ変位」は次のスキャンラインに処理が移動した場合のＸ切片の変化量を示している。「Ｙ変位」は当該ベクタに影響を受ける残りのスキャンライン数を示している。「向き」は当該ベクタの向きを示す。
【００３６】
図８に示すベクタを、図９に示す具体例を用いてさらに説明する。図９（Ａ）に示したように、３点Ｐ１（０，３００）、Ｐ２（６００，０）、Ｐ３（３００，６００）で表現される三角形を例にとる。ここで、座標系は図面左上方を原点とし、従って図面の水平右方向にＸ座標値は増加し、図面の垂直下方向にＹ座標値は増加するものとしている。この３点Ｐ１，Ｐ２，Ｐ３から、ベクタの向きを考慮して、Ｐ１Ｐ２、Ｐ２Ｐ３、Ｐ３Ｐ１の３つのベクタが生成される。それぞれのベクタは図９（Ｂ）に示すようになる。例えばＰ１Ｐ２は、「Ｘ」が６００、「Ｘ変位」が−２、「Ｙ変位」が３００、「向き」が−１となる。他のベクタも同様である。
【００３７】
このようなベクタのデータだけでは、塗り潰す描画範囲は分からない。そのため、このようなベクタをもとに、図形の内部／外部判定を行う必要がある。例えば上述の描画方式ａの処理を示す図６においては描画開始点と描画終了点を、また描画方式ｂの処理を示す図７においては描画開始点を、それぞれ判別する必要がある。以下、このような図形の内部／外部判定に用いる判定規則を示す。
【００３８】
判定規則には非ゼロ巻き規則と奇偶規則との２種類がある。これらはいずれも複数の外形（パス）で形成された一つの図形の内部を判定する際に用いられる規則である。図１０は、非ゼロ巻き規則及び奇偶規則による図形の内部判定方法の一例の説明図である。図１０（Ａ）には非ゼロ巻き規則、図１０（Ｂ）には奇偶規則の場合を示している。図１０（Ａ）に示す非ゼロ巻き規則は、図形を構成する外形がスキャンラインと交差する際の向きを考慮したものである。図１０（Ａ）では外形がスキャンラインを上向きに交差する場合を正、下向きに交差する場合を負としている。走査方向に向かって正の交差であれば１を加算し、負の交差であれば１を減算する。そして、合計値が０でなくなった点から０に戻った点までが内部であると判定する。図１０（Ａ）に示す例では、ハッチングを施して示し外側のパスの内側全体が描画領域となる。
【００３９】
一方、図１０（Ｂ）に示す奇偶規則は、スキャンラインと交差するパスの個数をカウントして、奇数の点から偶数の点までを内部と判定することにしている。この判定方法によれば、図１０（Ｂ）にハッチングを施して示すように、描画領域は外側のパスと内側のパスで挟まれた円環状の領域となる。
【００４０】
図１１は、ベクタの内部判定処理の一例を示すフローチャートである。なお、描画図形には、その図形対応した属性領域が別途設けられ、その中に内部判定規則や内部判定値などが格納されているものとする。また、これらの属性領域のデータは、例えば図８に示すベクタのデータ中の「順序」を示す値から取得できるものとする。
【００４１】
まずＳ７１において、ベクタの「順序」から、このベクタで構成される図形の内部判定規則を取得し、その内部判定規則をＳ７２で調べる。判定規則の種類が非ゼロ巻き規則であれば、Ｓ７３において内部判定値を取得し、Ｓ７４において値が０か否かをチェックする。内部判定値が０の場合には、Ｓ７５においてベクタの向き（＋１または−１）を足し、Ｓ７６において「領域の開始」であると判断する。Ｓ７４で内部判定値が０でない場合には、Ｓ７７においてベクタの向き（＋１または−１）を足してから、再度、Ｓ７８において内部判定値が０であるか否かをチェックする。内部判定値が０の場合には、Ｓ７９において「領域の終了」であると判断し、値が０以外の場合にはＳ８０において領域が継続すると判断する。
【００４２】
Ｓ７２で内部判定規則の種類が奇偶規則であれば、Ｓ８１において内部判定値を取得し、当該内部判定値を１だけ増加させてから２の剰余を求める。Ｓ８２において、内部判定値の２の剰余が１か０かにより内部判定値が奇数か偶数かを判定し、奇数であれば、図形が内部になるので、Ｓ８３において「領域の開始」と判断する。また、内部判定値が偶数であれば、図形の外部となるので、Ｓ８４において「領域の終了」と判断する。
【００４３】
なお、「領域の開始」が描画開始点に対応し、「領域の終了」が描画終了点に対応し、取得したベクタおのおのに対してこの処理を適用すれば、描画開始点と描画終了点を判別することができる。
【００４４】
次に、描画処理の負荷の計算方法について説明する。図１２は、描画負荷の計算処理の一例を示すフローチャートである。上述のように、この例においては描画処理の負荷として、スキャンライン上のベクタの存在頻度を用いている。まずＳ９１において、生成されたベクタおのおのに対して、どのバンドに属するかを判別し、各バンド内でのベクタのＹ軸における最大値と最小値を求める。そしてＳ９２において、各バンド毎に最大値から最小値を引いた数、すなわちＹ軸上での長さを求める。さらにＳ９３において、各バンド毎の負荷に対応した値に計算した値を足す。このようにしてベクタの存在頻度を計算し、描画処理の負荷とすることができる。
【００４５】
図１３は、描画負荷の計算方法の具体例の説明図である。図１３（Ａ）において、各バンドの高さを１２８とする。そこに、塗り潰して示した四角形が、初めて追加されたものとする。この四角形は、各バンドに６４、１２８、６４の長さで属している。通常、Ｘ軸と平行なベクタは除外されるので、この四角形は２本のベクタで表現される。このとき、左側のベクタの負荷として、それぞれのバンドにおいて６４、１２８、６４が計算される。右側のベクタに対しても負荷として、それぞれのバンドにおいて６４、１２８、６４が計算される。したがって、各バンドの負荷は、図１３（Ｂ）に示すようにそれぞれ１２８、２５６、１２８となる。
【００４６】
このようにして計算された描画負荷を用いて描画方式を切り替える。図１４は、描画方式の切替方法の一例の説明図である。図１４においては、図１４（Ａ）に示す４つの図形▲１▼〜▲４▼を、図１４（Ｂ）に示すように重ねて描画するものとする。なお、バンドの高さは１２８であるとする。各図形はバンドの境界に接する形で描画され、図形▲１▼はバンドＢ１〜Ｂ８に、図形▲２▼はバンドＢ２〜Ｂ７に、図形▲３▼はバンドＢ３〜Ｂ６に、図形▲４▼はバンドＢ４，Ｂ５に、それぞれ属するものとする。図１４（Ｂ）では、図形▲１▼の上に図形▲２▼を、さらにその上に図形▲３▼を、さらのその上に図形▲４▼を、それぞれ描画するため、図形中、他の図形の下になった部分は見えなくなっている。
【００４７】
このような図形▲１▼〜▲４▼について、図１２，図１３で説明したようにして各バンドにおける描画負荷を計算すると、図１４（Ｃ）の「負荷」の欄に示すようになる。例えば、バンドＢ１は、１つの図形が存在するので描画負荷は２５６、バンドＢ４は、上書きによって見えなくなる図形も含めて４つの図形が存在するので描画負荷は１０２４となる。
【００４８】
ここで、処理切り替えの閾値を１０００とすると、バンドＢ４とバンドＢ５の負荷が１０２４であるため、描画方式ｂが選択され、描画処理時に使用される。それ以外のバンドは描画方式ａが選択される。
【００４９】
上述のように描画方式ａでは、図１４（Ａ）に示す図形▲１▼〜▲４▼を順に描画してゆくため、重なりが多い部分では、上書きによって見えなくなる部分についても無駄な描画処理を行う。そのため、図形の重なりが多くなればなるほど、その描画処理時間は長くなる。これに対して描画方式ｂでは、重なり除去処理を行いながら描画処理を行うため、無駄な描画処理は発生しないが、描画領域を判定してゆく処理を行うため、その処理のオーバヘッドがかかる。そのため、重なりが少ない場合には判定処理のオーバヘッドが描画時間に影響してしまう。図１４に示す例では、バンドＢ１〜Ｂ３及びバンドＢ６〜Ｂ８については重なりが少ないものとして、重なりが少ないときに高速に描画処理を行うことができる描画方式ａを用い、バンドＢ４，Ｂ５のように重なりが多い部分では、重なりが多くても高速な描画処理を行うことができる描画方式ｂを用いる。このようにして、全体の描画処理時間を短縮し、高速な描画処理を行うことができる。
【００５０】
次に、別の具体例を説明する。上述の具体例では、中間コードとしてベクタ形式のデータを使用し、描画処理の負荷としてスキャンライン上のベクタの存在頻度を用いて描画方式の選択を行う例を示した。この具体例では、中間コードとして台形形式のデータを使用する例を示す。使用可能な描画方式は上述の例と同様に、バンドメモリを用いて重なり処理を行う描画方式ａと、中間コード上で重なり処理を行ってからバンドメモリにデータを書き込む描画方式ｂを使用するものとする。この例の場合の描画処理の負荷は、描画方式ａについては台形の面積（ピクセル数）を使用し、描画方式ｂについてはスキャンライン上の辺の存在頻度を用いることとする。切り替え方法として、負荷から予測時間を計算し、予測時間の小さいほうの処理方式を選択することとし、描画方式の切替をバンド毎に行うものとする。
【００５１】
図１５は、台形データの一例の説明図である。中間コードとして台形形式のデータを使用する場合、まず既存の種々の方法を用いて描画データが表す図形を走査線方向に平行な２辺を持つ台形に分割する。そして、副走査線方向をＹ座標軸、走査線方向にＸ座標軸をとって描画領域上での台形の位置や大きさに関する情報をＸＹ座標系で表現している。
【００５２】
図１５（Ａ）に示す台形のデータ構造においては、Ｙ座標値の最大値ＹＭＡＸと最小値ＹＭＩＮ、左側の辺についてはＹ座標の最小値の位置におけるＸ座標値Ｘ１、Ｙ座標値が単位量増加した際のＸ座標値の増分ＤＸ１、右側の辺については、Ｙ座標値の最小値の位置におけるＸ座標値Ｘ２、Ｙ座標値が単位量増加した際のＸ座標値の増分ＤＸ２、により台形領域を少なくとも規定している。それぞれの座標値については、図１５（Ｂ）に台形の一例を用いて示している。
【００５３】
また、これらの描画領域に関する値（ＹＭＩＮ、ＹＭＡＸ、Ｘ１、Ｘ２、ＤＸ１、ＤＸ２）以外には、色などの塗りつぶし属性値（「属性」）と、描画順序を表わす値（「順序」）などが格納される。なお、台形データによる塗りつぶし領域の表現はさまざまなものが挙げられ、ここではその一例を示すものであって、他の表現方法でも良い。もちろん、他の情報が含まれていてもよい。
【００５４】
台形は、塗りつぶす内部の図形を表現しているため、上述の中間コードをベクタで表現する場合に行っていた図１１に示す内部判定の処理を省略することができる。その代わりに、左側の斜辺の場合には領域の開始点、右側の斜辺の場合には領域の終了点であるとして扱えばよい。ただし、同一の図形を表現する台形同士が重なる場合があり、重なった領域を塗りつぶす必要がある場合においては、判定規則として非ゼロ巻き規則を適用する。
【００５５】
このように中間コードを台形で表現した場合の描画処理の負荷の計算方法について説明する。上述のように、この具体例の場合の描画処理の負荷は、描画方式ａについては台形の面積（ピクセル数）を使用し、描画方式ｂについてはスキャンライン上の辺の存在頻度を用いることとする。描画方式ａに対応する描画処理の負荷として用いる台形の面積は、上述の図１５を参照して、次のようにして計算することができる。
（（ＸＭＩＮ２−ＸＭＩＮ１）×２＋（ＤＸ１＋ＤＸ２）×（ＹＭＡＸ−ＹＭＩＮ））×（ＹＭＡＸ−ＹＭＩＮ）／２
ここで、ＸＭＩＮ１は左側の辺についてＹ座標値の最大値あるいは最小値におけるＸ座標値のうちいずれか小さい方、また、ＸＭＩＮ２は右側の辺についてＹ座標値の最大値あるいは最小値におけるＸ座標値のうちいずれか小さい方である。
【００５６】
なお、描画方式ｂに対応する描画処理の負荷は、台形の斜辺をベクタとみなして、上述の中間コードとしてベクタを用いる場合と同様にして、描画処理の負荷を計算すれば良い。
【００５７】
この例ではさらに、描画処理の負荷から処理時間を予測する。この描画処理の負荷に基づく処理時間の予測は、描画処理を行うプラットフォームによって異なってくる。そのため、実際に描画処理を行うプラットフォームに応じて描画処理の負荷から処理時間への関数を決定する必要がある。一例としては、
描画方式ａの処理時間＝描画方式ａの描画処理の負荷÷１６３８４
描画方式ｂの処理時間＝描画方式ｂの描画処理の負荷÷１２８
で求めることができる。
【００５８】
図１６は、中間コードとして台形形式を用いた場合の描画方式の切替方法の一例の説明図である。ここでは図１４（Ａ）に示した４つの図形▲１▼〜▲４▼を描画する場合を示している。なお、バンドの高さは図１４と同様に１２８であり、各図形▲１▼〜▲４▼の幅は、それぞれ１２８、２５６、３８４、５１２であるとする。
【００５９】
例えば、バンドＢ１の描画方式ａにおける描画処理の負荷は、
（１２８×２＋０）×１２８／２＝１２８×１２８＝１６３８４
であるので、処理時間は、
１６３８４÷１６３８４＝１
である。また、バンドＢ２の描画方式ａの処理時間は、図形▲１▼についての描画処理の負荷は１６３８４，図形▲２▼についての描画処理の負荷は図形▲１▼の２倍の３２７６８であるので、
（１６３８４＋３２７６８）÷１６３８４＝３
となる。バンドＢ３〜Ｂ８についても同様であり、図１６（Ｂ）の予測１の欄のようにそれぞれのバンドにおける描画方式ａの処理時間を予測することができる。
【００６０】
また、例えばバンドＢ１の描画方式ｂの処理時間は、図１４（Ｃ）に示した負荷の値を用いて
２５６÷１２８＝２
である。また、バンドＢ２の描画方式ｂの処理時間は、
５１２÷１２８＝４
となる。バンドＢ３〜Ｂ８についても同様であり、図１６（Ｂ）の予測２の欄のようにそれぞれのバンドにおける描画方式ｂの処理時間を予測することができる。
【００６１】
図１６（Ｂ）に示す描画方式ａ及び描画方式ｂの処理時間の予測値を比較すると、バンドＢ４とＢ５において、描画方式ｂの処理時間（予測２）が描画方式ａの処理時間（予測１）より小さくなる。従って、バンドＢ４とＢ５において描画方式ｂが選択され、それ以外は描画方式ａが選択される。このようにして選択された描画方式を用いて描画処理を行えばよい。このように、描画処理時間が短くなる描画方式を選択して描画処理を行うので、高速な描画処理を実現することができる。
【００６２】
さらに、中間コードとしてランレングス形式のデータを使用する場合がある。この場合でも同様にして描画方式の切替を行うことができる。上述の具体例と同様に、バンドメモリを用いて重なり処理を行う描画方式ａと、中間コード上で重なり処理を行ってからバンドメモリにデータを書き込む描画方式ｂを使用することとし、描画方式ａの負荷として台形の面積（ピクセル数）を、描画方式ｂの負荷としてスキャンライン上の辺の存在頻度を用いる。また、切り替え方法として、負荷から予測時間を計算し、予測時間の小さいほうの処理方式をバンド毎に選択するものとする。
【００６３】
ランレングスは、特殊な台形として考えればよい。すなわち、上述の台形の面積を求めた式において、ＹＭＡＸ−ＹＭＩＮが常に１で、ＤＸ１、ＤＸ２の値が０である。すなわち、
（（ＸＭＩＮ２−ＸＭＩＮ１）×２）／２＝ＸＭＩＮ２−ＸＭＩＮ１
となる。この式は、スキャンラインにおける描画終了点の座標から描画開始点の座標値を差し引いた値である。
【００６４】
なお、ランレングスも台形同様、塗りつぶす内部の図形を表現しているため、例えば図１１に示したような内部判定の処理を省略することができる。その代わりに、ランの開始点の場合には領域の開始点、ランの終了点の場合には領域の終了点であるとして扱えばよい。ただし、同一の図形を表現するランレングス同士が重なる場合があり、重なった領域を塗りつぶす必要がある場合においては、判定規則として非ゼロ巻き規則を適用すればよい。以下の処理は、中間コードが台形形状の場合と同じように処理すればよいので、説明は省略する。
【００６５】
上述の本発明の描画処理装置の実施の一形態及び具体例の説明においては、描画処理装置の内部で描画処理の負荷あるいは負荷に基づいて描画処理時間を判別して描画方式を切り替えていたが、例えばユーザからの指示を受け付ける設定手段を設け、設定手段に設定されたユーザからの指示に従って描画方式を決定してもよい。例えば、クライアント上のプリンタドライバの印刷設定の一つとして、処理方式を指定する方法が考えられる。また、描画を依頼するソフトウェアから描画方式を設定可能に構成してもよい。そのほか、描画処理装置側のコントロールパネルにおいて、固定の処理方式を設定とし、自動選択と手動設定が可能内容に構成してもよい。このような構成では、ユーザ自身が処理方式を選択できるので、自由度が高く、かつ、ユーザの望む通りの処理を行うことができるようになる。
【００６６】
また、上述の説明では、描画方式をバンド単位で切り替える例を用いて説明したが、ページ単位やジョブ単位、あるいはスキャンライン単位で処理を切り替えるようにしてもよい。もちろん、切り替えが可能な描画方式は、上述の具体例のようなバンドメモリを用いて重なり処理を行う描画方式ａと、中間コード上で重なり処理を行ってからバンドメモリにデータを書き込む描画方式ｂに限られるものではなく、任意の描画方式を用いることが可能である。また、備えておく描画方式の数も２つに限らず、３つ以上であってもよい。
【００６７】
【発明の効果】
以上の説明から明らかなように、本発明によれば、描画処理にかかる負荷や、その負荷に基づいて計算される描画処理時間などを用いて、複数の描画方式のうちから負荷の少ないあるいは描画処理時間が短いと予測される描画方式を選択して用いる。これによって、高速に図形の描画処理を行うことができるという効果がある。
【図面の簡単な説明】
【図１】  本発明の描画処理装置の実施の一形態を示すブロック図である。
【図２】  本発明の描画処理装置の実施の一形態における動作の一例を示すフローチャートである。
【図３】  本発明の描画処理装置の実施の一形態における描画方式の切替処理の概念図である。
【図４】  描画方式ａの一例の説明図である。
【図５】  描画方式ｂの一例の説明図である。
【図６】  描画方式ａによる１つのバンドの描画処理の一例を示すフローチャートである。
【図７】  描画方式ｂによる１つのバンドの描画処理の一例を示すフローチャートである。
【図８】  ベクタのデータ形式の一例の説明図である。
【図９】  ベクタの具体例の説明図である。
【図１０】  非ゼロ巻き規則及び奇偶規則による図形の内部判定方法の一例の説明図である。
【図１１】  ベクタの内部判定処理の一例を示すフローチャートである。
【図１２】  描画負荷の計算処理の一例を示すフローチャートである。
【図１３】  描画負荷の計算方法の具体例の説明図である。
【図１４】  描画方式の切替方法の一例の説明図である。
【図１５】  台形データの一例の説明図である。
【図１６】  中間コードとして台形形式を用いた場合の描画方式の切替方法の一例の説明図である。
【図１７】  従来の描画処理の一例を示すフローチャートである。
【符号の説明】
１…描画データ入力部、２…中間コード生成部、３…中間コード蓄積部、４−１〜ｎ…描画負荷推定部、５…描画方式選択部、６…描画部、７−１〜ｎ…描画方式、８…出力装置。
【図１】
0004022710.tif 000002
【図２】
0004022710.tif 000003
【図３】
0004022710.tif 000004
【図４】
0004022710.tif 000005
【図５】
0004022710.tif 000006
【図６】
0004022710.tif 000007
【図７】
0004022710.tif 000008
【図８】
0004022710.tif 000009
【図９】
0004022710.tif 000010
【図１０】
0004022710.tif 000011
【図１１】
0004022710.tif 000012
【図１２】
0004022710.tif 000013
【図１３】
0004022710.tif 000014
【図１４】
0004022710.tif 000015
【図１５】
0004022710.tif 000016
【図１６】
0004022710.tif 000017
【図１７】
0004022710.tif 000018