(57)【特許請求の範囲】
【請求項１】
ページ記述言語を入力として描画処理を行う描画処理装置において、
前記ページ記述言語を変換してイメージを描画するための描画データを生成する描画データ生成手段と、
走査線単位の単位領域で、前記描画データの描画処理の負荷を推定して負荷推定補正値を算出する負荷推定補正値算出手段と、
前記描画データと前記負荷推定補正値との格納及び送信の制御を行う描画データ格納制御手段と、
前記描画データ格納制御手段から前記描画データを読みだして並列描画処理を行う複数の描画処理手段と、
前記負荷推定補正値算出手段によって前記負荷推定補正値が算出された後に、前記走査線単位の単位領域内の描画データの数と、前記負荷推定補正値とを入力とした演算を行い、演算結果を単位領域負荷推定値とし、前記走査線単位の単位領域毎に求めた前記単位領域負荷推定値を累算する負荷算出処理を行いながら、前記描画処理手段に割り当てる描画領域である描画処理範囲を広げていき、累算結果が基準値に達する毎に、前記描画処理範囲を定めていくことで、前記描画処理手段毎に割り当てる前記描画処理範囲毎の描画処理の前記負荷の重さが均一となるように描画処理範囲を決定し、前記描画処理範囲を個々の前記描画処理手段に割り当てる処理担当範囲割り当て手段と、
前記描画処理手段で処理された結果を格納して出力装置に送信する処理結果格納制御手段と、
を有することを特徴とする描画処理装置。
【請求項２】
前記描画データ格納制御手段は、前記描画データの格納時に描画データの存在範囲を抽出する描画データ存在範囲抽出手段と、抽出した存在範囲を描画領域上での位置と対応づけて集計する描画データ存在範囲集計手段と、前記負荷推定補正値を描画領域上での位置と関係づけて登録する負荷推定補正値登録手段と、を含むことを特徴とする請求項１記載の描画処理装置。
【請求項３】
前記処理担当範囲割り当て手段は、描画処理の実行時に動的に前記描画処理範囲を割り当てることを特徴とする請求項１記載の描画処理装置。
【請求項４】
前記描画データ格納制御手段は、複数の前記描画処理手段間の共有メモリ上に構成されていることを特徴とする請求項１記載の描画処理装置。
【請求項５】
前記処理結果格納制御手段は、複数の前記描画処理手段間の共有メモリ上に構成されていることを特徴とする請求項１記載の描画処理装置。
【請求項６】
ページ記述言語を入力として描画処理を行う描画処理装置において、
前記ページ記述言語を変換してイメージを描画するための描画データを生成する描画データ生成手段と、
走査線単位の単位領域で、前記描画データの描画処理の負荷を推定して負荷推定補正値を算出する負荷推定補正値算出手段と、
前記描画データと前記負荷推定補正値との格納及び送信の制御を行う描画データ格納制御手段と、
前記描画データ格納制御手段から前記描画データを読みだして並列描画処理を行う複数の描画処理手段と、
前記走査線単位の単位領域内の描画データの数と、前記負荷推定補正値とを入力とした演算を行い、演算結果を単位領域負荷推定値とし、前記走査線単位の単位領域毎に求めた前記単位領域負荷推定値を累算する負荷算出処理を行いながら、前記描画処理手段に割り当てる描画領域である描画処理範囲を広げていき、累算結果が基準値を超えない範囲で、前記描画処理範囲を定めていくことで、前記描画処理手段毎に割り当てる前記描画処理範囲毎の描画処理の前記負荷の重さが均一となるように描画処理範囲を決定し、描画処理が進むにつれて割り当てる描画処理範囲を小さくする処理担当範囲割り当て手段と、
前記描画処理手段で処理された結果を格納して出力装置に送信する処理結果格納制御手段と、
を有することを特徴とする描画処理装置。
【請求項７】
ページ記述言語を変換してイメージを描画するための描画データを生成する描画データ生成手段と、
走査線単位の単位領域で、前記描画データの描画処理の負荷を推定して負荷推定補正値を算出する負荷推定補正値算出手段と、
前記描画データと前記負荷推定補正値との格納及び送信の制御を行う描画データ格納制御手段と、
前記描画データ格納制御手段から前記描画データを読みだして並列描画処理を行う複数の描画処理手段と、
前記走査線単位の単位領域内の描画データの数と、前記負荷推定補正値とを入力とした演算を行い、演算結果を単位領域負荷推定値とし、前記走査線単位の単位領域毎に求めた前記単位領域負荷推定値を累算する負荷算出処理を行いながら、前記描画処理手段に割り当てる描画領域である描画処理範囲を広げていき、累算結果が基準値に達する毎に、前記描画処理範囲を定めていくことで、前記描画処理手段毎に割り当てる前記描画処理範囲毎の描画処理の前記負荷の重さが均一となるように描画処理範囲を決定し、描画処理が進むにつれて前記描画処理手段に割り当てる描画処理範囲を決定するために使用している前記基準値を変化させる処理担当範囲割り当て手段と、
前記描画処理手段で処理された結果を格納して出力装置に送信する処理結果格納制御手段と、
を有することを特徴とする描画処理装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は描画処理装置に関し、特にページ記述言語を入力として描画処理を行う描画処理装置に関する。
【０００２】
【従来の技術】
現在、ページプリンタでは、Ｉｎｔｅｒｐｒｅｓｓ（米国ゼロックス社の登録商標）やＰｏｓｔＳｃｒｉｐｔ（米国アドビ・システムズ社の商標）などのＰＤＬ（ページ記述言語）を入力として印刷を実行している。
【０００３】
このようなＰＤＬを入力として印刷を実行する際には、ＰＤＬ形式のデータからラスタ出力デバイスに適した形式のデータに変換するイメージング処理を行う必要がある。ところが、一般にイメージング処理にかかる時間は非常に長く、このことは特に高速のページプリンタに出力するシステムなどでは問題となっている。
【０００４】
例えば、カラーの高速ページプリンタは毎分４０枚以上の出力能力を持つものがあるにもかかわらず、イメージング処理にかかる時間は、１０数秒から数分かかってしまい、高価な高速ページプリンタの能力を十分に生かせなかった。したがって、イメージング処理を高速に行うために、並列描画処理を行う必要がある。
【０００５】
図３０は、描画領域を均等に分割して並列描画処理を行う場合の図である。この図の描画要素４は、描画領域の中心部分に要素が多く、かつ重なり合いが複雑になっている。そして、このような描画要素４に対して、領域単位が均等に分割されて各描画処理部１〜３で並列描画処理が行われるものとする。
【０００６】
【発明が解決しようとする課題】
しかし、上述したように描画要素４の領域単位を均等に分割して描画処理部１〜３に等しく割り当てたとしても、描画要素の数や図形同士の重なり合いなどの描画要素自体の複雑さがあるため、描画処理部１〜３が担当する負荷の重さはそれぞれ異なるものになる。
【０００７】
図３１は、図３０で示した各描画処理部の描画処理動作タイミングを示す図である。このタイミングが示す各単位描画領域あたりの処理時間は、各領域内に属する描画要素の数だけではなく、描画要素同士の重なり具合などの影響も含めている。図から描画処理部１、２に比べて複雑な描画要素を担当した描画処理部３に負荷が集中してしまうことにより、他の描画処理部１、２が待ち状態に陥っていることがわかる。
【０００８】
このように描画領域を均等に分割して並列描画処理を行うと、重い負荷が割り当てられた描画処理部が律速となって、並列描画処理の効果を落とすという問題があった。
【０００９】
また、これらの並列描画処理をマルチプロセッサなどの複数のＣＰＵ上でソフトウェアとして実現した場合に処理量を等しくなるように負荷を分配したとしても、各ＣＰＵ上で他のプロセスが動作する時間やタイミングなどのバラツキにより、処理の実行時間は等しくならないという問題があった。
【００１０】
本発明はこのような点に鑑みてなされたものであり、負荷の重さが均一になるように描画処理範囲を割り当てて高速な並列描画処理を行う描画処理装置を提供することを目的とする。
【００１１】
【課題を解決するための手段】
本発明では上記課題を解決するために、ページ記述言語を入力として描画処理を行う描画処理装置において、前記ページ記述言語を変換してイメージを描画するための描画データを生成する描画データ生成手段と、走査線単位の単位領域で、前記描画データの描画処理の負荷を推定して負荷推定補正値を算出する負荷推定補正値算出手段と、前記描画データと前記負荷推定補正値との格納及び送信の制御を行う描画データ格納制御手段と、前記描画データ格納制御手段から前記描画データを読みだして並列描画処理を行う複数の描画処理手段と、前記負荷推定補正値算出手段によって前記負荷推定補正値が算出された後に、前記走査線単位の単位領域内の描画データの数と、前記負荷推定補正値とを入力とした演算を行い、演算結果を単位領域負荷推定値とし、前記走査線単位の単位領域毎に求めた前記単位領域負荷推定値を累算する負荷算出処理を行いながら、前記描画処理手段に割り当てる描画領域である描画処理範囲を広げていき、累算結果が基準値に達する毎に、前記描画処理範囲を定めていくことで、前記描画処理手段毎に割り当てる前記描画処理範囲毎の描画処理の前記負荷の重さが均一となるように描画処理範囲を決定し、前記描画処理範囲を個々の前記描画処理手段に割り当てる処理担当範囲割り当て手段と、前記描画処理手段で処理された結果を格納して出力装置に送信する処理結果格納制御手段と、を有することを特徴とする描画処理装置が提供される。
【００１２】
ここで、描画データ生成手段は、ページ記述言語から描画データを生成する。負荷推定補正値算出手段は、走査線単位の単位領域で、描画データの描画処理の負荷を推定して負荷推定補正値を算出する。描画データ格納制御手段は、描画データと前記負荷推定補正値との格納及び送信の制御を行う。複数の描画処理手段は、割り当てられた描画データを並列に描画処理する。処理担当範囲割り当て手段は、前記負荷推定補正値算出手段によって前記負荷推定補正値が算出された後に、走査線単位の前記単位領域内の描画データの数に、前記負荷推定補正値を係数にして乗算して、乗算結果を負荷推定値とし、描画すべき前記単位領域から前記負荷推定値を求めながら前記負荷推定値を累算する負荷算出処理を行い、累算結果が基準値を超えない描画領域までを、描画処理を要求している前記描画処理手段に割り当て、累算結果が前記基準値を超えた描画領域から、前記負荷算出処理を再度行って、あらたに求めた累算結果が前記基準値を超えないあらたな描画領域までを、描画処理を要求している次の前記描画処理手段に割り当てて、描画領域を更新して広げていくことで、前記描画処理手段に対して、前記負荷の重さが均一となるように描画処理範囲を決定し、前記描画処理範囲を個々の前記描画処理手段に割り当てる。処理結果格納制御手段は、並列描画処理後の結果を格納し、出力装置に送信する。
【００１３】
【発明の実施の形態】
以下、本発明の実施の形態を図面を参照しながら説明する。図１は、本発明の描画処理装置の原理図である。描画データ生成手段２０は、図示しない入力手段から入力されるページ記述言語１０である描画記述の解釈・展開を行い、描画記述に記述されていたイメージを描画するための描画データを生成する。そして、この描画データから後述する負荷推定補正値を負荷推定補正値算出手段３０で算出する。また、描画データと負荷推定補正値とは、描画データ格納制御手段４０に送信される。
【００１４】
描画データ格納制御手段４０は、複数の描画処理手段６０ａ〜６０ｎに、描画データを送信する。さらに、描画データの存在範囲を指定するためのデータと負荷推定補正値とを処理担当範囲割り当て手段５０に送信する。
【００１５】
処理担当範囲割り当て手段５０は、描画データ格納制御手段４０から描画データの存在範囲と負荷推定補正値とを受信して、描画処理手段６０ａ〜６０ｎが要求する担当描画処理範囲に対しての制御を行う。
【００１６】
描画処理手段６０ａ〜６０ｎは、処理担当範囲割り当て手段５０で均一に割り当てられた担当描画処理範囲の描画処理を行う。そして、処理結果格納制御手段７０は、描画処理手段６０ａ〜６０ｎで処理された処理結果を格納し、出力装置２００にその結果を送信する。
【００１７】
また、これらの各手段はその初期化や処理の開始、終了、同期などは図示しない制御手段により制御されて動作する。
図２は、本発明の描画処理装置が適用されるシステムの概念図である。このシステムは、ネットワーク４００に接続されたネットワークインタフェース３００を介して、描画処理装置１００が接続される。そして、描画処理装置１００からの処理結果を出力する出力装置２００が接続される。
【００１８】
システムの動作としては、図示しないクライアント・コンピュータから、ネットワークや専用線を介して描画出力用のデータが送られる。この描画出力用のデータはネットワークインタフェース３００を介して、描画処理装置１００に受信され処理される。そして、処理の終ったデータは出力装置２００に転送されて紙やフィルムなどの媒体上にイメージが再現される。
【００１９】
以上説明したように、本発明は、クライアントとなるコンピュータからネットワークあるいは専用通信路などを通じて、描画データを受信してプリンタ等の出力機用のデータに変換する装置内に配置される。
【００２０】
図３は、描画処理装置の全体処理の流れを示すフローチャートである。ここでは１ページ分の処理の流れの例を簡略化して示している。
描画記述が入力されると、描画データ格納制御手段４０、処理結果格納制御手段７０、処理担当範囲割り当て手段５０、描画処理手段６０ａ〜６０ｎに対して、初期化命令を発行し初期化処理が行われる（ステップＳ１）。そして、入力された描画記述から描画データを生成するために、描画データ生成手段２０に処理の開始を指示する（ステップＳ２）。その後、描画記述の処理が予め定められた描画領域分、あるいは予め定められた描画記述のデータ量分生成し終えると、描画処理手段６０ａ〜６０ｎに対して、描画処理の開始を指示する（ステップＳ３）。この後、図１で図示してない制御手段は、複数の描画処理手段６０ａ〜６０ｎの処理が全て終了したことを、描画処理手段６０ａ〜６０ｎからの通知を通して知るか、あるいは未処理の描画領域が無くなったことを処理担当範囲割り当て手段５０からの通知を通して知ると、処理結果格納制御手段７０内のデータを出力装置２００に対して転送する（ステップＳ４）。
【００２１】
次に、描画処理装置の各手段について詳しく説明する。図４は、描画データ生成手段２０の処理の流れを示すフローチャートである。ただし、入力データの中に負荷推定補正値が既に記述されているものする。
【００２２】
描画データ生成手段２０は、処理の開始を指示されるとページ記述言語である描画記述データを読み込み、負荷推定補正値が記述されているかどうかを判断する（ステップＳ１０）。記述されていない場合は、描画処理手段６０ａ〜６０ｎが処理できる形式である描画データに変換して、描画データ格納制御手段４０に転送する（ステップＳ１１）。また、描画記述データ中に負荷推定補正値が記述されていた場合には、負荷推定補正値を切り出して、これを読みこんで描画データ格納制御手段４０に転送する（ステップＳ１２）。そして、描画データが入力済みかどうかを判断する。入力済みの場合は終了し、そうでない場合は、ステップＳ１０に戻る。
【００２３】
図５は、描画データ生成手段２０で処理される描画データのデータ構造の一例を示す図である。走査線方向に平行な２辺を持つ台形表現により描画領域を表現する描画データ２０ａと、そのデータ構造２０ｂとを示している。そして、副走査線方向をＹ座標軸、走査線方向にＸ座標軸をとって描画領域上での位置をＸＹ座標系で表現している。
【００２４】
データ構造２０ｂの描画領域に関する値（YMIN,YMAX,X1,X2,DX1,DX2)以外には、色などの塗りつぶし属性値（ATTR) と、重ね塗の順番を制御する塗りつぶし優先順位の値（PRIO) などが格納される。また、台形データによる塗りつぶし領域の表現はさまざまなものが挙げられるが、ここではその一例を示している。図ではＹ座標の最大値YMAXと最小値YMIN、左側の辺についてはＹ座標の最小値の位置におけるＸ座標値X1、Ｙ座標が単位量増加した際のＸ座標の増分値DX1 、右側の辺についてはＹ座標の最小値の位置におけるＸ座標値X2、Ｙ座標が単位量増加した際のＸ座標の増分値DX2 、により台形領域を少なくとも規定できる。
【００２５】
なお、本実施の形態においては、説明の簡単のため描画データとして台形表現により描画領域を表現する描画データを用いているが、描画データは主走査線方向に平行な２辺を持つ台形表現である必要はない。例えば、点列やベクトル表現による多角形表現、曲線を含めた線分列表現、向かい合う線分列同士を関係づけた線分列ペアによる表現、描画領域を三角形や矩形で分割した表現でもよい。
【００２６】
次に、負荷推定補正値算出手段３０について説明する。図６は、負荷推定補正値算出手段３０の構成図である。描画データ参照手段３１は、描画データを参照して後の処理手段に対して必要なデータを分配する。描画データ種別判別手段３２は、参照されている描画データの種類を判定する。
【００２７】
描画データ領域代替データ算出手段３３は、参照されている描画データのおおまかな存在範囲を算出あるいは、おおまかな存在範囲がすでに描画データの中に記述されている場合には、そのデータを取り出して、描画データ領域代替データを作成する。この描画データ領域代替データとしては描画データの存在範囲を正確に記述できるデータを使用してもよいが、目的とする負荷推定補正値を算出するためには、図形の外接矩形程度の情報量があればよいため、以降では説明の簡単のために、この描画データ代替データが描画データの外接矩形データであるものとする。
【００２８】
また、この外接矩形データは、描画データの正確な存在範囲である必要はないため、描画データを表現している点列などの座標値から単純に算出したものでもよいし、単純に算出される外接矩形にマージンを加えたものであってもよい。
【００２９】
描画データ種別負荷推定補正値算出手段３４は、描画データ種別判別手段３２から、処理中の描画データの種類を示すデータを得る。このデータを元に描画データ種別負荷推定補正値算出手段３４は、その描画データの負荷推定補正値を求める。この求め方は、単純に描画データの種類別に負荷推定補正値の値や算出式が格納されたテーブルを用意しておき、そのテーブルを引いて求めることで容易に実現可能である。
【００３０】
負荷推定補正値の係数が求まると、描画データ領域代替データ算出手段３３から、描画データ領域代替データを得て、描画データの存在範囲を算出する。その後、算出した存在範囲について求めた負荷推定補正値の値を加算するという指示を負荷推定補正値累算手段３７に伝える。
【００３１】
例えば、描画データがラスタイメージデータであった場合に、描画データの種類別に負荷推定補正値を格納したテーブル内に負荷推定補正値＝（分割描画領域内の存在範囲の概算面積）×１００という算出式が格納されていたとする。このとき描画領域代替データからこの描画データが関係する分割描画領域内の存在範囲の概算面積を描画領域代替データから求め、この値を用いて各分割描画領域毎に算出した負荷推定補正値を負荷推定補正値累算手段３７に通知する。
【００３２】
重なり度算出手段３５は、描画データ同士の重なり関係から負荷推定補正値を算出する。この重なり度算出手段３５においては、例えば、分割描画領域ごとにその分割描画領域内で描画データ同士の重なりが何回あるかを概算し、その数値に何らかの演算を行って負荷推定補正値として負荷推定補正値累算手段３７に通知する。分割描画領域内での描画データ同士の重なり回数の概算については後述する。
【００３３】
負荷推定補正値累算手段３７は、描画データ種別負荷推定補正値算出手段３４からのデータを分割描画領域毎に累算するとともに、重なり度算出手段３５から得られる分割描画領域内の描画データ同士の重なり回数の概算値から算出される負荷推定補正値を格納し、これら両者を分割描画領域毎に演算を行って合成して、分割描画領域ごとの負荷推定補正値を作る。
【００３４】
そして、描画データ種別負荷推定補正値算出手段３４のデータをα、重なり度算出手段３５のデータをβとして、合成するときの合成式は、ｆｌｏｏｒ（３．９５・ｆｌｏｏｒ（α／１２８．５）＋５．３・ｆｌｏｏｒ（β／３．３）＋１）のような式を用いる。ただし、この式に限定されるものではない。
【００３５】
次に、分割描画領域毎の描画データ同士の重なり回数の概算について説明する。ここでは、描画データ同士の重なり回数の概算を行うための入力データとして、描画データ領域代替データを使用する。このデータは、描画データ領域代替データ保持手段３６に蓄積されているものである。描画データ領域代替データは、描画データの外接矩形などの比較的単純な図形データで領域を表現しているものであり、同種のデータの２つの間では、容易に重なり判定を行うことができる。
【００３６】
例えば、描画データ領域代替データが描画データの外接矩形であった場合には、２つの描画データ領域代替データ間の重なり判定には２つの長方形の交わりの有無を判定する問題になり、実現は容易である。以降、描画データ領域代替データを単に矩形データと呼ぶ。
【００３７】
分割描画領域ごとの矩形データ間の重なり回数の算出は、描画領域を一方向に走査しながら処理することができる。この走査処理の際に、走査位置に対応する矩形データを描画データ領域代替データ保持手段３６から順に取り出すことにより、各走査位置においては、その位置で走査処理が進む方向と直交する直線上に存在する矩形データを全て集め、その直線上に存在しない矩形データを排除した集合を作り処理することができる。
【００３８】
これを実現するために描画データ領域代替データ保持手段３６は、描画データ領域代替データを単純に一方向に順に並べ直したリストでもよいし、この走査処理の処理単位ステップごとのきざみをもったテーブルの様なものを用意して、各描画データ領域代替データをその片側の座標値をキーとしてそのテーブルに登録してもよい。
【００３９】
以降、この走査処理は描画領域に向かって上方向から下方向に進むものとして説明を行い、走査処理を重なり走査、重なり走査処理の方向に直交する方向の直線を重なり走査処理補助線と呼ぶ。また、各走査位置における重なり走査処理補助線上にある矩形データ集合を保持、管理する手段を重なり走査処理補助線上矩形データ集合管理手段と呼ぶ。
【００４０】
図７は、重なり走査処理補助線上の矩形データ間の共通区間を示す図である。重なり合う矩形データＡ〜Ｃの組み合わせについて、１回ずつ重なりを検出するには、例えば、重なり走査処理が進んで走査位置が変更になることにより、新たに矩形データが参照された時に、その時に１回、重なり走査処理補助線３０ａ上の矩形データ集合管理手段に管理されている矩形データＢと、新たに読み込まれた矩形データＣとの共通の区間３０ｂ（重なり走査処理補助線方向の区間）を持つものを探索することにより実現できる。
【００４１】
この探索処理は、新たに参照された矩形データとの総当たりのチェックでも実現できるが、通常は、重なり走査処理補助線上矩形データ集合管理手段を各矩形データを重なり走査処理補助線方向の区間により管理するツリー構造で実現することによって重なり合う矩形データの組を探索する処理の負荷を軽減する。
【００４２】
図８は、一方向の区間を持つデータを示す概念図であり、図９は、一方向の区間でデータを管理するツリー構造の例を示す図である。以降、一方向の区間を持つデータを区間データと言い替えて説明する。このツリー構造の各ノードは２level ×ｎから２level ×（ｎ＋１）の区間のデータを管理する。各ノードが直接管理する描画データは（２level ×ｎ＋２level ×（ｎ＋１））／２の位置、すなわち、各ノードが管理する領域の中点をまたぐデータであり、中点よりも左の領域にある描画データはそのノードの左側の枝の下に管理され、中点よりも右の領域にある描画データはそのノードの右側の枝の下に管理される。
【００４３】
そして、このツリー構造に対して、特定の区間データと交わる区間データを探索する際には、探索する区間データと関係のない枝を探索する必要がなくなるので効率的に探索を実現することができる。図９では、区間データをツリー構造に格納してあり、この時区間データ〔９，１３〕について重なるものを探索した時の探索の道筋を例示してある。探索はまず０〜１６のノードに格納されている区間データ〔３，１０〕について重なりチェックを行う。これは、区間同士の単純な比較により重なりがあることが判定できる。
【００４４】
そして、区間データ〔９，１３〕は０〜１６のノードが管理する範囲の中点８よりも右側にあるため、０〜８以下の枝については探索する必要がなくなり、８〜１６のノード以下の枝について同様の探索を繰り返す。その結果８〜１６のノードで区間データ〔１０，１４〕、８〜１２のノードで区間データ〔９，１１〕を見つけることができる。１２〜１６のノードについては探索されない。そして、探索後、あるいは探索の途中で重なりを問い合わせた区間データ〔９，１３〕は８〜１６のノードに格納される。
【００４５】
以上により、重なりあう矩形データの組を順に見つけることができ、各分割描画領域毎に重なり回数を計算してその回数から各分割描画領域毎の負荷推定補正値を求めることが可能である。なお、単純に重なり回数から負荷推定補正値を求めるのではなく、重なり部分の面積や重なりあう描画要素の種類の組み合わせなどにより、負荷推定補正値を求めてもよい。また、重なりを検出した際に単純に各分割描画領域毎に回数を増やすのではなく、重なりの組み合わせの検出毎に負荷推定補正値を算出してそれを累積してもよい。
【００４６】
次に、描画データ格納制御手段４０について説明する。図１０は、描画データ格納制御手段４０の構成を示す図である。まず、データ格納用インターフェース４１は、描画データ生成手段２０からの描画データを受信する。描画データ存在範囲抽出手段４２は、受信した各描画データから副走査線方向（以降説明の簡単のため、副走査線の方向をＹ方向、副走査線方向の位置を示す数値をＹ座標値、これに対し走査線の方向をＸ方向、走査線方向の位置を示す数値をＸ座標値と呼ぶ。）に対する存在範囲を検出する。
【００４７】
描画データ存在範囲集計手段４３は、検出したＹ方向の存在範囲を集計する。負荷推定補正値登録手段４４は、描画領域の特定の範囲についての負荷推定の補正値を格納する。負荷推定基データ用インタフェース４５は、処理担当範囲割り当て手段５０と通信する。描画データ登録手段４６は、Ｙ方向の存在範囲から、Ｙ座標値の最大値、最小値の少なくとも一つの座標値をもとに描画データを抽出できるように登録する。描画データ送出用インタフェース４７は、描画処理手段６０ａ〜６０ｎと通信を行う。
【００４８】
描画データ格納制御手段４０は、大きく分けると少なくとも４種類の処理フェーズを持つ。それらは、初期化、データの格納、描画データの送出、負荷推定基データの送出である。
【００４９】
図１１は、描画データ格納制御手段４０の初期化の処理の流れを示したフローチャートである。描画データ格納制御手段４０は、描画データ存在範囲集計手段４３の初期化（ステップＳ２０）と、描画データ登録手段４６の初期化（ステップＳ２１）と、負荷推定補正値登録手段４４の初期化（ステップＳ２２）を行う。
【００５０】
図１２は、描画データ格納制御手段４０が描画データ生成手段２０から描画データを受信して格納する際の処理の流れを示すフローチャートである。描画データ生成手段２０と負荷推定補正値算出手段３０とからデータが送信されると、描画データであるか、負荷推定の補正値であるかを判定する（ステップＳ３０）。描画データであると、描画データ存在範囲抽出手段４２によりその描画データのＹ方向の存在範囲を検出し（ステップＳ３１）、この両端を描画データ存在範囲集計手段４３に登録する（ステップＳ３２）。
【００５１】
例えば、描画データ存在範囲抽出手段４２が描画データのＹ方向の座標値の最大値と最小値を抽出する。そして、最大値に当てはまる個数、最小値に当てはまる個数をカウントする１組ずつのカウンタが単位Ｙ座標毎に用意されている描画データ存在範囲集計手段４３中の対応するカウンタをインクリメントする。
【００５２】
以降、ここで例に挙げたようなカウンタのテーブルについて参照する際には、最小値側のカウンタを進入カウンタ、最大値側のカウンタを退出カウンタと呼ぶ。
【００５３】
次に、描画データを描画データ登録手段４６に登録する（ステップＳ３３）。例えば、描画領域のＹ方向の単位領域に対応する描画データテーブルを用意し、各描画データをＹ方向の座標値の例えば最小値に対応する場所に、描画データを登録することにより実現できる。そして、これらの操作は描画データ生成手段２０により生成されるすべての描画データについて行われる。
【００５４】
一方、負荷推定の補正値であった場合には、負荷推定補正値登録手段４４にこれを登録する（ステップＳ３４）。この負荷推定補正値登録手段４４も例えば、同様に描画領域のＹ方向の単位領域に対応するテーブル領域を用意し、このテーブル領域に受け取った補正値データを登録することにより実現できる。
【００５５】
なお、本実施の形態においては、描画データ格納制御手段４０内の描画データ存在範囲集計手段４３、描画データ登録手段４６、負荷推定補正値登録手段４４等にテーブル形式のデータ構造を使用するが、これは説明の簡単のためであり、他のデータ構造を用いてもよい。リスト構造や、ツリー構造、ハッシュ機構などさまざまな他のデータ構造を利用しても同様の機能を得ることは可能である。
【００５６】
その後、描画データが入力済みかどうかを判断する。入力済みの場合は終了し、そうでない場合は、ステップＳ３０に戻る（ステップＳ３５）。
図１３は、描画データ格納制御手段４０から、描画処理手段６０ａ〜６０ｎに描画データを送出する際の処理の流れを示すフローチャートである。描画データ格納制御手段４０は、描画データの転送要求を受け取ると、要求された範囲に登録されている描画データを抽出して（ステップＳ４０）、転送要求もとの描画処理手段に送出する（ステップＳ４１）。この時、抽出した描画データを全て送出してもよいし、抽出した描画データの中から、要求された範囲の片側の端にかからないデータを除いてから送出することもできる。
【００５７】
また、描画データ格納制御手段４０のデータ送出の機能は、描画処理手段６０ａ〜６０ｎ間の共有メモリ上に構成されている場合には、描画データ格納制御手段４０が能動的な機能を果たさずとも、描画処理手段６０ａ〜６０ｎが必要な範囲に登録されている描画データにアクセスできるデータ構造を提供するだけでもよい。このとき各描画処理手段６０ａ〜６０ｎはそれぞれ勝手に描画データを読みだしていくことが可能である。
【００５８】
次に、処理担当範囲割り当て手段５０について説明する。図１４は、処理担当範囲割り当て手段５０に対する描画データ格納制御手段４０の処理の流れを示すフローチャートである。処理担当範囲割り当て手段５０は、描画処理手段６０ａ〜６０ｎに対して、描画領域を分割して処理の担当を割り当てる。この描画領域の分割を決定する際には、分割した描画領域における描画処理の負荷の推定値を算出する。
【００５９】
以降、Ｙ方向の最小分割単位を単位描画領域と呼び、処理担当範囲割り当て手段５０により大きさと位置を決められて各描画処理手段６０ａ〜６０ｎに割り当てられる領域を分配描画領域と呼ぶ。例えば、単位描画領域は走査線１〜数本分のＸ方向に細長い領域であり、分配描画領域はこの単位描画領域数個から数十個程度の大きさの領域となる。
【００６０】
処理担当範囲割り当て手段５０が分配描画領域を決定する際には、割り当てる分配描画領域を各描画処理手段６０ａ〜６０ｎが処理する場合の負荷の推定値にもとづいて計算する。この時、負荷の推定値を計算する範囲について、描画データ格納制御手段４０に対して、図１０で説明した描画データ存在範囲集計手段４３に登録されているデータの要求（ステップＳ５０）と、図１０で説明した負荷推定補正値登録手段４４に登録されているデータの要求（ステップＳ５１）を行う。
【００６１】
描画データ格納制御手段４０は、この要求に対して描画データ存在範囲集計手段４３と負荷推定補正値登録手段４４とを指定された描画位置をもとに検索することによりデータを集め、これを処理担当範囲割り当て手段５０に送出する（ステップＳ５２）。
【００６２】
図１５は、処理担当範囲割り当て手段５０の構成を示す図である。排他的インタフェース５１は、描画処理手段６０ａ〜６０ｎからいずれか１つの描画処理手段の要求を受け付ける。すると、分配描画処理領域決定手段５２で決定された分配描画領域の範囲が通知される。分配描画領域の範囲は、この分配描画領域の負荷推定値が予め定められた基準に見合うように決定される。
【００６３】
この予め定められた基準は分配描画処理領域決定手段５２内に保持されており、図示しない制御手段により供給される。例えば、順次、分配描画領域の範囲を広げていき、分配描画領域の負荷推定値が予め定めておいた基準値を越えるところで分配描画領域を決定してもよい。
【００６４】
描画範囲判定手段５３は、描画処理の進行にともない処理すべき描画領域がなくなった状態を判定する。未処理位置保持手段５４は、Ｙ方向の未処理位置を保持するための保持手段であり、描画処理手段６０ａ〜６０ｎに単位描画処理領域を割り当てる際に更新される。負荷推定値算出手段５５は、負荷推定基データ保持手段５６に保持されているデータに加えて、負荷推定値を算出している領域に関する補正値が描画データ格納制御手段４０から得られれば、これを組み合わせて、単位描画領域ごとに負荷推定値を算出する。この負荷推定値は単位描画領域ごとに算出された後、例えば加算のような演算により複数の単位描画領域にわたって結合されて、分配描画領域の負荷推定値が算出される。
【００６５】
負荷推定基データ保持手段５６は、描画データ格納制御手段４０に問い合わせることにより得た描画データの存在範囲の集計値等から算出した負荷推定基データが格納される。
【００６６】
図１６は、処理担当範囲割り当て手段５０の処理の流れを示すフローチャートである。処理担当範囲割り当て手段５０は、全体の処理の開始時に初期化が行われる他に、描画処理手段６０ａ〜６０ｎから問い合わせがあると以下に示すような処理を行う。
【００６７】
描画処理手段６０ａ〜６０ｎからの要求は、排他的インタフェース５１によりアクセスを制御され、同時に、描画処理手段６０ａ〜６０ｎからいずれか１つの描画処理手段の要求を受け付ける（ステップＳ６０）。担当範囲の割り当て要求があると、描画範囲判定手段５３を参照し、まだ未処理の描画領域があるかどうかを判断する（ステップＳ６１）。未処理の描画領域が既になければ、その旨を要求元の描画処理手段に通知し、後述するステップＳ６６に行く。
【００６８】
未処理の描画領域がまだある場合には、未処理位置保持手段５４に保持されている位置から順に、単位描画領域についての負荷推定値を算出する。すなわち、描画データ格納制御手段４０に対してその単位描画領域ごとの描画要素の数などを問い合わせ（ステップＳ６２）、その単位描画領域についての負荷推定補正値も要求して算出する（ステップＳ６３）。
【００６９】
この推定値は例えば、その単位描画領域から始まる描画要素の数と、負荷推定基データ保持手段５６に保持されている直前の単位描画領域から続いている描画要素の値を足すことによりその単位描画領域に存在する描画要素の数を推定し、この値に、負荷推定補正値があればこれを係数としてかけ合わせた数値を、単位描画領域の負荷推定値とすることができる。単位描画領域の値を算出すると、その単位描画領域で終る描画要素の数をその単位描画領域における描画要素の数から引いた値を負荷推定基データ保持手段５６に格納しておく。
【００７０】
そして、未処理位置保持手段５４に保持されている位置から順に、同様の処理により単位描画領域ごとの負荷推定値を算出して、これを累算していき、分配描画領域の負荷推定値を算出する（ステップＳ６４）。そして、累算値が、予め定めておいた値を越えるかどうかを判断する（ステップＳ６５）。値を越えない場合は、ステップＳ６１へ戻り、そうでない場合はステップＳ６６に行く。
【００７１】
そして、割り当てる分配描画領域があるかどうかを判断する（ステップＳ６６）。ない場合は、分配する描画領域のないことを要求元に送信する。ある場合は、要求元の描画処理手段に対して送信して（ステップＳ６８）、未処理位置保持手段５４に保持されている位置を次の未処理の描画位置に更新する（ステップＳ６９）。
【００７２】
次に、描画処理手段６０ａ〜６０ｎについて説明する。描画処理手段の内部構成は、いずれも同じなので描画処理手段６０として説明する。図１７は、描画処理手段６０の構成を示す図である。処理済み描画位置保持手段６１は、処理済みの描画位置を保持する。担当描画範囲保持手段６２は、処理担当範囲割り当て手段５０から得られた、担当する描画処理範囲を保持するための保持手段であり、半導体記憶装置や磁気ディスク装置により実現できる。
【００７３】
描画データ保持手段６３は、描画データ格納制御手段４０から得た描画データを一時保持すると共に、先に処理した他の描画領域から引き継がれる描画データをも保持するための保持手段である。この描画データ保持手段６３も半導体記憶装置などのさまざまな記憶手段により実現することが可能である。
【００７４】
描画データ判定・破棄手段６４は、描画機構６５が処理対象とする描画位置が更新されることに伴い、描画データ保持手段６３内の描画データの内、描画処理の行われる位置が、その描画データの存在範囲外になってしまったものを描画機構６５の処理の対象から除いて、描画機構６５の処理の効率をあげると共に、描画データ保持手段６３の必要記憶容量を削減するためのものである。
【００７５】
描画機構６５は、内部に描画位置を保持し、描画データ保持手段６３内のデータを描画処理バッファ６６をワーク領域として利用しながら処理して、担当描画領域に関して、ラスタイメージデータと対応のとれる処理結果データに変換する。処理結果データの形式としては、ラスタイメージデータを代表として、主走査線方向の範囲と色により表現されるランレングスデータ、これらのデータをデータ圧縮の技術により圧縮したデータ等さまざまな形式がありうる。
【００７６】
描画機構６５は、処理結果を単位描画処理領域ごとに処理結果格納制御手段７０に格納してもよい。また、ある程度集めてから処理結果格納制御手段７０内に格納してもよい。この処理結果格納制御手段７０は、複数の描画処理手段６０ａ〜ｎ間の共有メモリ上に構築され副走査方向のテーブルの領域が予め確保されていれば、描画処理手段６０ａ〜６０ｎが各々、そのテーブルに処理結果を格納した記憶領域のアドレスを登録してもよい。
【００７７】
図１８は、描画処理手段６０の処理の流れを示すフローチャートである。描画処理手段６０は、描画データ格納制御手段４０に予め定められた範囲のデータが格納されると動作の開始を指示される。処理の開始時には、処理済み描画位置保持手段６１と描画データ保持手段６３の初期化が行われる（ステップＳ７０）。初期化動作が終ると、処理担当範囲割り当て手段５０に対して処理を担当する描画領域の範囲の問い合わせを行う（ステップＳ７１）。処理を担当する描画領域が伝えられると、これを担当描画範囲保持手段６２に格納し、描画処理位置を担当描画範囲保持手段６２に格納された範囲の片側の位置に設定する（ステップＳ７２）。
【００７８】
まず、描画データ判定・破棄手段６４が描画データ保持手段６３内に保持されている描画データを検査して、描画位置に影響を与えなくなった描画データを選び、破棄する（ステップＳ７３）。そして、処理済み描画位置保持手段６１に格納されている位置と描画処理位置を組み合わせたデータとを使用して描画データ格納制御手段４０に描画データの要求を行う。例えば、この段階の処理は、描画データ格納制御手段４０が共有メモリ上の記憶領域として実現されていた場合には、各描画処理手段６０ａ〜６０ｎが処理済み描画位置保持手段６１に格納されていた位置から、描画位置までに登録されている描画データを読み込むという処理になる（ステップＳ７４）。
【００７９】
この際、描画位置に影響を与えない描画データは読み込まれない、あるいは読み込んでから破棄される。そして、担当する描画領域の処理が終了かどうかを判断し（ステップＳ７６）、終了でなければ描画位置を更新し（ステップＳ７７）、そうでなければ終了する。
【００８０】
また、描画機構６５により描画データ保持手段６３内に保持されている描画データから、描画処理バッファ６６を使用して処理が行われ、処理結果データが作成される（ステップＳ７５）。この段階での描画機構６５としての機能を発揮するものは、さまざまのものが提案されているので、それらの内、出力結果データの種類に応じたものを用いてもよい。ここでは、描画処理バッファ６６をラインバッファとして使用して、走査線単位で描画データを優先順位の低い順に重ね塗りを行って走査線毎のラスタデータを作成していくとする。描画位置が決まると、描画処理バッファ６６内のラインバッファ領域の初期化を行う。そして、描画データ保持手段６３内のデータを優先順位の低い方から取り出し、これに対して決定された描画位置に対応する走査線方向の色塗情報を表現するランレングスデータを生成して、ラインバッファの対応する場所に色データを格納する。これを、描画データ保持手段６３内に格納されている描画データ分繰り返して処理する。
【００８１】
描画位置の処理が終ると、描画処理手段６０は描画処理バッファ６６内の処理結果を処理結果格納手段７０に転送する。描画処理手段６０が共有記憶装置を有する並列計算機システム上に構築されている場合には、描画位置の更新時に描画処理バッファ６６を共有メモリ上の領域として確保して描画機構６５を動作させる。そして、処理結果の格納は、処理結果格納制御手段７０内の描画位置を示すテーブルの描画位置に対応する場所に、処理結果を格納した領域のアドレスの値を記録するだけでよい。
【００８２】
描画機構６５は、処理結果を処理結果格納制御手段７０に転送すると、処理済み描画位置保持手段６１に処理の終った描画位置を記録した後、描画位置を進める。描画位置が担当している描画領域内であれば、描画データ保持手段６３内のデータの整理から繰り返して同様の処理を行う。
【００８３】
描画処理手段の処理の過程において、例外的な動作をする場合は、処理担当範囲割り当て手段５０により描画領域内に担当すべき未処理領域がないことを告げられた場合である。このとき、描画処理手段６０は処理を終了して停止する。
【００８４】
次に、具体的な描画サンプルを用いて、本発明である描画処理装置の動作を説明する。図１９は、入力描画記述データと、その入力描画記述データが表す描画サンプルの概念図を示している。以降の説明では、この入力描画記述データを入力した時の描画処理を例として説明を行う。描画サンプル１１は、３つの楕円と２つの三角形からなる。そして、入力描画記述データ１２は、楕円の記述データｏｖａｌと三角形の記述データｔｒｉａｎｇｌｅと負荷推定補正値ＦｕｋａＲとからなる。例えば、ｔｒｉａｎｇｌｅ（１８４，１２８，２１６，１９２，１８４，１９２，１５）は、（Ｘ１，Ｙ１）＝（１８４，１２８）、（Ｘ２，Ｙ２）＝（２１６，１９２）、（Ｘ３，Ｙ３）＝（１８４，１９２）であり、ハッチングパターンが１５であることを示している。また、ＦｕｋａＲ（２，１８４，２００）は、Ｙ軸の座標位置１８４〜２００間で負荷が２倍大きいことを示している。その他も同様なので説明は省略する。
【００８５】
図２０は、図１９に示した入力描画記述データから、描画データ生成手段２０により生成される描画データの概念図を示したものである。ここでの例では、描画記述中のそれぞれの描画オブジェクトは、台形による描画領域を表現する形式に分割され、描画データＤ１〜Ｄ１１のフォーマットに変換され、描画データ格納制御手段４０に送信される。
【００８６】
図２１は、単位描画領域の例を示した概念図である。描画領域２０ｃを走査線単位の単位描画領域Ｒ１〜Ｒ１６に分割する。描画データＤ１〜Ｄ１１は、描画データ生成手段２０により生成されると、描画データ格納制御手段４０に転送される。描画データ格納制御手段４０に転送されると、描画データＤ１〜Ｄ１１は、図１２で説明した処理を受けて描画データ格納制御手段４０内に格納される。
【００８７】
図２２は、描画データＤ１〜Ｄ１１が描画データ格納制御手段４０内に格納された状態の一例を示している。図１０で説明した描画データ存在範囲集計手段４３内には、進入テーブル４３ａと退出テーブル４３ｂがあり、進入テーブル４３ａには、各単位描画領域において、その位置にＹ座標値の最小値（上側の座標）を持つ描画データがいくつあるかを集計しており、退出テーブル４３ｂには、各単位描画領域において、その位置にＹ座標値の最大値（下側の座標）を持つ描画データがいくつあるかを集計している。
【００８８】
図１０で説明した描画データ登録手段４６はここでは、単位描画領域ごとにエントリを持つテーブル４６ａから構成されており、各描画データＤ１〜Ｄ１１はそれぞれの最小のＹ座標値に対応するエントリの位置と関係づけられて格納されている。
【００８９】
そして、図１０で説明した負荷推定補正値登録手段４４もまた、単位描画領域ごとに数値を登録できるテーブルで構成されている。この例では、ほぼ中央の領域に対応する数値が２となり、他の数値はみな１となっている。これは、数値が２となっている領域では描画要素の重なり具合や描画要素自体の複雑さなどの理由により、描画要素の数などから単純に推測した負荷の値の２倍程度の負荷量となることを入力データ中のヒント情報から抽出したものである。
【００９０】
以下の説明では、描画処理を３つの描画処理手段６０ａ、６０ｂ、６０ｃで行うものとして説明する。
描画データ格納制御手段４０に描画データが格納されると、描画処理手段に対して起動命令が発行される。描画処理手段６０ａ〜６０ｃはほぼ同時に起動するが、処理担当範囲割り当て手段５０へのアクセスが排他的に制御されているため、この段階で順序づけられる。
【００９１】
ここでは、最初の処理担当範囲割り当て手段５０へのアクセスが描画処理手段６０ａ、描画処理手段６０ｂ、描画処理手段６０ｃの順で許可されたものとする。
【００９２】
図２３は、描画処理手段６０ａが最初に処理担当範囲割り当て手段５０に対して、担当描画領域を要求した時の処理を示す概念図である。描画処理手段６０ａから問い合わせがあると処理担当範囲割り当て手段５０は、最初の単位描画領域Ｒ１から順に負荷の推定値を算出しながら、分配描画領域を広げていく。
【００９３】
ここでは、領域を分割する基準値の例を８としておく。単位描画領域Ｒ１においては、まず描画データ格納制御手段４０に問い合わせを行い、単位描画領域Ｒ１から始まる描画データが２つあり（描画データＤ１、Ｄ１０）、終るデータが０個である。よって、次の単位描画領域に受け渡す描画データの数は、０（前の領域からつながっている描画データの数）＋２（進入テーブル４３ａの値）−０（退出テーブル４３ｂの値）＝２である。また、負荷の推定を補正するためのデータが１（補正情報特になし）というデータを負荷推定補正値登録手段４４から得る。これから、単位描画領域Ｒ１における負荷の推定値は、（０（直前の単位描画領域から受け渡された描画データの数）＋２（描画データ数））×１（負荷推定の補正値）＝２となる。
【００９４】
単位描画領域Ｒ２においては、描画データ格納制御手段４０に問い合わせの結果、単位描画領域Ｒ２から始まる描画データが０個、終るデータが０個であり、負荷の推定を補正するためのデータが１（補正情報特になし）であるという情報が得られる。すなわち、単位描画領域Ｒ２においては描画データの個数は単位描画領域Ｒ１と同じ２個であり、負荷の推定値は２（描画データ数）×１（負荷推定の補正値）＝２となる。
【００９５】
単位描画領域Ｒ３においては、描画データ格納制御手段４０に問い合わせの結果、単位描画領域Ｒ３から始まる描画データが０個、終るデータが１個であり、負荷の推定を補正するためのデータが１（補正情報特になし）であるという情報が得られる。すなわち、単位描画領域Ｒ３においては描画データの個数は単位描画領域Ｒ２と同じ２個であり、負荷の推定値は２（描画データ数）×１（負荷推定の補正値）＝２となる。ここで、単位描画領域Ｒ３で終る描画データが１つあるため、次の単位描画領域Ｒ４に渡される描画データは２−１で１になる。単位描画領域Ｒ３の段階までは、分配描画領域の負荷の推定値は２＋２＋２で６にしかならならないため、さらに単位描画領域Ｒ４に分配描画領域を広げる。
【００９６】
単位描画領域Ｒ４においては、描画データ格納制御手段４０に問い合わせの結果、単位描画領域Ｒ４から始まる描画データが１個、終るデータが０個であり、負荷の推定を補正するためのデータが１（補正情報特になし）である。すなわち、描画データは単位描画領域Ｒ３から引き継いだ描画データが１個、新しく入って来た描画データが１個で合計２個である。負荷の推定値は２（描画データ数）×１（負荷推定の補正値）＝２となり、ここまでの分配描画領域の負荷の推定値は８となる。
【００９７】
処理担当範囲割り当て手段５０は、この段階で描画処理手段６０ａに対して、処理の担当範囲を単位描画領域Ｒ１〜単位描画領域Ｒ４に割り当てて、次の描画処理手段の要求の処理に移る。この時、図１５で説明した未処理位置保持手段５４は単位描画領域Ｒ５にセットされると共に、図１５で説明した負荷推定基データ保持手段５６には、単位描画領域Ｒ５に受け渡される描画データの個数２がセットされる。
【００９８】
描画処理手段６０ａは、処理の担当範囲を受け取ると、描画データ格納制御手段４０から描画データを読み込み、順に処理する。ここで読み込まれて描画処理の対象となる描画データは単位描画領域Ｒ１から単位描画領域Ｒ４の間にＹ方向の最小値（上側の座標値）を持ち、単位描画領域Ｒ１よりも上側にＹ方向の最大値（下側の座標値を持たない）Ｄ１，Ｄ２，Ｄ３である。描画処理手段６０ａは、これらの描画データを処理して単位描画領域Ｒ１から単位描画領域Ｒ４に対応する処理結果データを作成して処理結果格納制御手段７０に登録する。
【００９９】
そして、描画処理手段６０ａは再度、処理担当範囲割り当て手段５０に処理担当範囲の割り当て要求を行って処理を続けることになる。
図２４は、描画処理手段６０ｂが描画処理手段６０ａの次に処理担当範囲割り当て手段５０に対して、担当描画領域を要求した時の処理を示す概念図である。
【０１００】
描画処理手段６０ｂから問い合わせがあると処理担当範囲割り当て手段５０は、図１５で説明した未処理位置保持手段５４に保持されている単位描画領域Ｒ５から順に負荷の推定値を算出しながら、分配描画領域を広げていく。
【０１０１】
単位描画領域Ｒ５においては、まず描画データ格納制御手段４０に問い合わせを行い、単位描画領域Ｒ５から始まる描画データが１個あり、終るデータが０個であり、負荷の推定を補正するためのデータが１（補正情報特になし）というデータを得る。これから、単位描画領域Ｒ５の描画データの個数は図１５で説明した負荷推定基データ保持手段５６に保持されていた値２と単位描画領域Ｒ５から始まる描画データの数１とを足した３となる。
【０１０２】
そして、負荷の推定値は３（描画データ数）×１（負荷推定の補正値）＝３となる。以下同様の処理を行い、描画処理手段６０ｂには、単位描画領域Ｒ５、単位描画領域Ｒ６、単位描画領域Ｒ７が割り当てられる。このとき、未処理位置保持手段５４は、単位描画領域Ｒ８、負荷推定基データ保持手段５６には数値１が格納される。
【０１０３】
描画処理手段６０ｂは、処理の担当範囲を受け取ると、描画データ格納制御手段４０から描画データを読み込み、順に処理する。描画処理手段６０ｂは、図１７で説明した処理済み描画位置保持手段６１が初期化されたままであるため、単位描画領域Ｒ５からではなく、単位描画領域Ｒ１から描画データを要求し、単位描画領域Ｒ７までの間にＹ方向の最小値（上側の座標値）を持ち、単位描画領域Ｒ５よりも上側にＹ方向の最大値（下側の座標値）を持たない描画データとしてＤ２、Ｄ１０、Ｄ６を読み込んで処理の対象とする。
【０１０４】
描画処理手段６０ｂは、これらの描画データを処理して単位描画領域Ｒ５から単位描画領域Ｒ７に対応する処理結果データを作成して処理結果格納制御手段７０に登録する。そして、描画処理手段６０ｂは再度、処理担当範囲割り当て手段５０に処理担当範囲の割り当て要求を行って処理を続けることになる。
【０１０５】
図２５は、描画処理手段６０ｃが描画処理手段６０ｂの次に処理担当範囲割り当て手段５０に対して、担当描画領域を要求した時の処理を示す概念図である。描画処理手段６０ｃから問い合わせがあると処理担当範囲割り当て手段５０は、図１５で説明した未処理位置保持手段５４に保持されている単位描画領域Ｒ８から同様の処理を行うが、単位描画領域Ｒ８の領域においては描画要素の数を同様に算出すると４となり、負荷推定補正値の値が２になっているため、この単位描画領域Ｒ８だけで基準として設定している値８に達してしまう。このため、描画処理手段６０ｃに対して、単位描画領域Ｒ８だけを担当範囲として設定する。
【０１０６】
描画処理手段６０ｃは、処理の担当範囲を受け取ると、描画データ格納制御手段４０から描画データを読み込み、順に処理する。描画処理手段６０ｃは、図１７で説明した処理済み描画位置保持手段６１が初期化されたままであるため、単位描画領域Ｒ８からではなく、単位描画領域Ｒ１から描画データを要求し、単位描画領域Ｒ８までの間にＹ方向の最小値（上側の座標値）を持ち、単位描画領域Ｒ８よりも上側にＹ方向の最大値（下側の座標値）を持たない描画データとしてＤ１０、Ｄ３、Ｄ９、Ｄ７を読み込んで処理の対象とする。描画処理手段６０ｃは、これらの描画データを処理して単位描画領域Ｒ８に対応する処理結果データを作成して処理結果格納制御手段７０に登録する。
【０１０７】
図２６は、描画処理手段６０ａが最初の処理が終わって再度、処理担当範囲割り当て手段５０に対して、担当描画領域を要求した時の処理を示す概念図である。  描画処理手段６０ａから問い合わせがあると処理担当範囲割り当て手段５０は、図１５で説明した未処理位置保持手段５４に保持されている単位描画領域Ｒ９から同様の処理を行うが、単位描画領域Ｒ９の領域においては単位描画領域Ｒ８の領域と同様に、描画要素の数を同様に算出すると４、負荷推定補正値の値が２になっているため、この単位描画領域Ｒ９だけで基準として設定している値８に達してしまう。このため、描画処理手段６０ａに対して、単位描画領域Ｒ９だけを担当範囲として設定する。
【０１０８】
描画処理手段６０ａは、処理の担当範囲を受け取ると、描画データ格納制御手段４０から描画データを読み込み、順に処理する。描画処理手段６０ａは、図１７で説明した処理済み描画位置保持手段６１が以前の処理により単位描画領域Ｒ４に設定されているため、単位描画領域Ｒ９からではなく、単位描画領域Ｒ４から描画データを要求し、単位描画領域Ｒ９までの間にＹ方向の最小値（上側の座標値）を持ち、単位描画領域Ｒ８よりも上側にＹ方向の最大値（下側の座標値）を持たない描画データとしてＤ３、Ｄ９、Ｄ７、Ｄ１１を読み込んで処理の対象とする。
【０１０９】
描画処理手段６０ａは、これらの描画データを処理して単位描画領域Ｒ９に対応する処理結果データを作成して処理結果格納制御手段７０に登録する。
図２７は、描画処理手段６０ｂが最初の処理が終って再度、処理担当範囲割り当て手段５０に対して、担当描画領域を要求した時の処理を示す概念図である。
【０１１０】
描画処理手段６０ｂから問い合わせがあると処理担当範囲割り当て手段５０は、図１５で説明した未処理位置保持手段５４に保持されている単位描画領域Ｒ１０から同様の処理を行った結果、単位描画領域Ｒ１０から単位描画領域Ｒ１２を担当範囲として描画処理手段６０ｂを設定する。
【０１１１】
描画処理手段６０ｂは、処理の担当範囲を受け取ると、描画データ格納制御手段４０から描画データを読み込み、順に処理する。描画処理手段６０ｂは、図１７で説明した処理済み描画位置保持手段６１が以前の処理により単位描画領域Ｒ７に設定されているため、単位描画領域Ｒ８から描画データを要求し、単位描画領域Ｒ１２までの間にＹ方向の最小値（上側の座標値）を持ち、単位描画領域Ｒ１０よりも上側にＹ方向の最大値（下側の座標値）を持たない、描画データとしてＤ８、Ｄ４、Ｄ１１を読み込んで処理の対象とする。
【０１１２】
描画処理手段６０ｂは、これらの描画データを処理して単位描画領域Ｒ１０から単位描画領域Ｒ１２に対応する処理結果データを作成して処理結果格納制御手段７０に登録する。
【０１１３】
図２８は、並列描画処理のタイムチャートの概略を示す。この例は、負荷推定補正値が十分な精度を持っていない場合を示している。負荷の推定値で重みづけを行った単位描画領域Ｒ７、単位描画領域Ｒ８は、重みづけを行わなかった場合に単位描画領域Ｒ７、単位描画領域Ｒ８がまとめて一つの描画処理手段に割り当てられるところをそれぞれ別の描画処理手段に割り当てることができたという点で効果を発揮しているが、単位描画領域Ｒ７、単位描画領域Ｒ８の処理は予想外に重く、仮に次に設定されるであろう分配描画領域を順番に描画処理手段６０ａに割り当てると描画処理手段６０ｂの処理能力を余らせたまま、描画処理手段６０ｃの処理の終了待ちという状態が生じてしまう。
【０１１４】
しかし、本実施の形態においては、処理の終った描画処理手段がそれぞれ処理担当範囲割り当て手段５０に対して担当範囲の割り当てを要求するため、次に担当範囲を要求する描画処理手段は自動的に描画処理手段６０ｂとなる。これにより、静的に割り当てる場合よりもより効率的に描画処理手段の並列描画処理を実現することが可能となる。
【０１１５】
図２９は、処理の結果として処理結果格納制御手段７０に格納される処理結果データ７０ａの概念図を示す。本実施の形態において、担当描画処理領域を最初から最小の描画処理範囲ごとに割りふることも可能ではあるが、この場合、アクセスを排他制御している処理担当範囲割り当て手段５０へのアクセス頻度が高まってしまうことにより、処理担当範囲割り当て手段５０へのアクセスの競合が頻繁におこり、かえって処理効率が落ちてしまうという結果となる。
【０１１６】
このため、処理担当範囲割り当て手段５０へのアクセス回数を適度に抑えるとともに、適度な粒度で描画領域を分割するために負荷の推定手段が必要であり、この負荷の推定をより精度を上げるために負荷推定補正値を利用している。逆に、負荷の推定を完全なものにすることは非常に難しいため、この誤差や実行時の揺れを吸収するために動的な割り当てが効果を発揮する。
【０１１７】
上記の説明では、処理担当範囲割り当て手段５０が分配描画領域の大きさを決定する際に使用している基準値は固定としたが実行時に可変であってもよい。また、処理の後半において、何らかの原因でどれかの描画処理手段が遅くなってしまった場合などを救済するためには、描画領域の処理の後半ほどこの基準値の大きさを小さくして、分配描画領域の大きさを小さくしておいてもよい。
【０１１８】
また、並列動作の効果を高めるために上記実施の形態においては、負荷の推定を基準にして各描画処理手段に対して割り当てる描画領域の範囲を決定したが、予め定めた大きさの描画領域を各描画処理手段に対して要求順に与え、そして、割り当てる描画領域の大きさを処理の進み具合で変化させてもよい。例えば、処理の後半ほど小さくする、なども本実施の形態では容易に実現できる。ただし、この場合、描画データ格納制御手段４０と処理担当範囲割り当て手段５０との間の通信路は必ずしも必要ではない。
【０１１９】
以上説明したように、本発明の描画処理装置は、描画処理の負荷を処理実行時に均一に分割して並列描画処理を行う構成とした。これにより、描画対象となるページイメージに部分的な偏りがあった場合にも、描画処理の高速化を可能とする。さらに、負荷が軽い領域での資源へのアクセス競合によるオーバーヘッドも削減することが可能になる。
【０１２０】
また、実行時に他のプロセスによる影響などにより特定の部分処理を担当している処理手段の処理が一時的に遅れた場合にも描画処理の高速化を可能とする。
【０１２１】
【発明の効果】
以上説明したように、本発明の描画処理装置は、走査線単位の単位領域で、描画データの負荷を推定して、負荷推定補正値を算出し、負荷推定補正値が算出された後に、単位領域毎の負荷推定値を用いて、負荷の重さが均一となるように描画処理範囲を決定し、決定した描画処理範囲を個々の描画処理手段に割り当てる構成とした。これにより、複数の描画処理手段は、略同一時間に描画処理を終えることができるので、高速な並列描画処理を行うことが可能になる。
【図面の簡単な説明】
【図１】本発明の描画処理装置の原理図である。
【図２】描画処理装置が適用されるシステムの概念図である。
【図３】描画処理装置の全体処理の流れを示すフローチャートである。
【図４】描画データ生成手段の処理の流れを示すフローチャートである。
【図５】描画データ生成手段で処理される描画データのデータ構造の一例である。
【図６】負荷推定補正値算出手段の構成図である。
【図７】重なり走査処理補助線上の矩形データ間の共通区間を示す図である。
【図８】一方向の区間を持つデータを示す概念図である。
【図９】一方向の区間でデータを管理するツリー構造の例を示す図である。
【図１０】描画データ格納制御手段の構成を示す図である。
【図１１】描画データ格納制御手段の初期化の処理の流れを示すフローチャートである。
【図１２】描画データ格納制御手段が描画データ生成手段から描画データを受信して格納する際の処理の流れを示すフローチャートである。
【図１３】描画データ格納制御手段から、描画処理手段に描画データを送出する際の処理の流れを示すフローチャートである。
【図１４】処理担当範囲割り当て手段に対する描画データ格納制御手段の処理の流れを示すフローチャートである。
【図１５】処理担当範囲割り当て手段の構成を示す図である。
【図１６】処理担当範囲割り当て手段の処理の流れを示すフローチャートである。
【図１７】描画処理手段の構成を示す図である。
【図１８】描画処理手段の処理の流れを示すフローチャートである。
【図１９】入力描画記述データと描画サンプルの概念図である。
【図２０】描画データの概念図である。
【図２１】単位描画領域の例を示した概念図である。
【図２２】描画データＤ１〜Ｄ１１が描画データ格納制御手段内に格納された状態の一例を示す図である。
【図２３】描画処理手段６０ａが最初に処理担当範囲割り当て手段に対して担当描画領域を要求した時の処理を示す概念図である。
【図２４】描画処理手段６０ｂが描画処理手段６０ａの次に処理担当範囲割り当て手段に対して、担当描画領域を要求した時の処理を示す概念図である。
【図２５】描画処理手段６０ｃが描画処理手段６０ｂの次に処理担当範囲割り当て手段に対して、担当描画領域を要求した時の処理を示す概念図である。
【図２６】描画処理手段６０ａが最初の処理が終わって再度、処理担当範囲割り当て手段に対して、担当描画領域を要求した時の処理を示す概念図である。
【図２７】描画処理手段６０ｂが最初の処理が終わって再度、処理担当範囲割り当て手段に対して、担当描画領域を要求した時の処理を示す概念図である。
【図２８】並列描画処理のタイムチャートの概略を示す。
【図２９】処理の結果として処理結果格納制御手段に格納される処理結果データの概念図である。
【図３０】描画領域を均等に分割して並列描画処理を行う場合の図である。
【図３１】描画処理部の描画処理動作タイミングを示す図である。
【符号の説明】
１０  ページ記述言語
２０  描画データ生成手段
３０  負荷推定補正値算出手段
４０  描画データ格納制御手段
５０  処理担当範囲割り当て手段
６０ａ〜６０ｎ  描画処理手段
７０  処理結果格納制御手段
８０  出力装置
【図１】
0003728820.tif 000002
【図２】
0003728820.tif 000003
【図３】
0003728820.tif 000004
【図４】
0003728820.tif 000005
【図５】
0003728820.tif 000006
【図６】
0003728820.tif 000007
【図７】
0003728820.tif 000008
【図８】
0003728820.tif 000009
【図９】
0003728820.tif 000010
【図１０】
0003728820.tif 000011
【図１１】
0003728820.tif 000012
【図１２】
0003728820.tif 000013
【図１３】
0003728820.tif 000014
【図１４】
0003728820.tif 000015
【図１５】
0003728820.tif 000016
【図１６】
0003728820.tif 000017
【図１７】
0003728820.tif 000018
【図１８】
0003728820.tif 000019
【図１９】
0003728820.tif 000020
【図２０】
0003728820.tif 000021
【図２１】
0003728820.tif 000022
【図２２】
0003728820.tif 000023
【図２３】
0003728820.tif 000024
【図２４】
0003728820.tif 000025
【図２５】
0003728820.tif 000026
【図２６】
0003728820.tif 000027
【図２７】
0003728820.tif 000028
【図２８】
0003728820.tif 000029
【図２９】
0003728820.tif 000030
【図３０】
0003728820.tif 000031
【図３１】
0003728820.tif 000032