JP3707208B2 - Drawing processor - Google Patents
Drawing processor Download PDFInfo
- Publication number
- JP3707208B2 JP3707208B2 JP16554597A JP16554597A JP3707208B2 JP 3707208 B2 JP3707208 B2 JP 3707208B2 JP 16554597 A JP16554597 A JP 16554597A JP 16554597 A JP16554597 A JP 16554597A JP 3707208 B2 JP3707208 B2 JP 3707208B2
- Authority
- JP
- Japan
- Prior art keywords
- processing
- unit
- area
- data
- divided
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Fee Related
Links
- 238000013500 data storage Methods 0.000 claims description 83
- 238000000034 method Methods 0.000 claims description 73
- 230000008569 process Effects 0.000 claims description 68
- 238000007726 management method Methods 0.000 claims description 46
- 230000004044 response Effects 0.000 claims description 7
- 238000003672 processing method Methods 0.000 claims description 4
- 238000010586 diagram Methods 0.000 description 41
- 230000007246 mechanism Effects 0.000 description 12
- 238000004891 communication Methods 0.000 description 7
- 230000006870 function Effects 0.000 description 5
- 230000000694 effects Effects 0.000 description 4
- 238000003384 imaging method Methods 0.000 description 4
- 230000004913 activation Effects 0.000 description 2
- 230000008859 change Effects 0.000 description 2
- 230000003111 delayed effect Effects 0.000 description 2
- 239000000284 extract Substances 0.000 description 2
- 238000000605 extraction Methods 0.000 description 2
- 239000004065 semiconductor Substances 0.000 description 2
- 230000005540 biological transmission Effects 0.000 description 1
- 230000001186 cumulative effect Effects 0.000 description 1
- 238000013144 data compression Methods 0.000 description 1
- 230000003247 decreasing effect Effects 0.000 description 1
- 238000007689 inspection Methods 0.000 description 1
- 238000010422 painting Methods 0.000 description 1
- 239000007787 solid Substances 0.000 description 1
Images
Landscapes
- Image Processing (AREA)
- Image Generation (AREA)
Description
【０００１】
【発明の属する技術分野】
本発明は描画処理装置に関し、特にページ記述言語を入力として描画処理を行う描画処理装置に関する。
【０００２】
【従来の技術】
現在、ページプリンタでは、Ｉｎｔｅｒｐｒｅｓｓ（米国ゼロックス社の登録商標）やＰｏｓｔｓＳｃｒｉｐｔ（米国アドビ・システムズ社の商標）などのＰＤＬ（ページ記述言語）を入力として印刷を実行している。
【０００３】
このようなＰＤＬを入力として印刷を実行する際には、ＰＤＬ形式のデータからラスタ出力デバイスに適した形式のデータに変換するイメージング処理を行う必要がある。ところが、一般にイメージング処理にかかる時間は非常に長く、このことは特に高速のページプリンタに出力するシステムなどでは問題となっている。
【０００４】
例えば、カラーの高速ページプリンタは毎分４０枚以上の出力能力を持つものがあるにもかかわらず、イメージング処理にかかる時間は、１０数秒から数分かかってしまい、高価な高速ページプリンタの能力を十分に生かせなかった。したがって、イメージング処理を高速に行うために、並列描画処理を行う必要がある。
【０００５】
従来の並列描画処理方式には、印刷すべきＰＤＬデータをページ毎に分割してページ単位で並列処理を行うものや、予め定めた分割領域ごとにＰＤＬ内に記述されている描画オブジェクトを分割して並列描画を行うものなどがあったが、これらは並列処理を行う単位となるページ間や、分割領域間の描画処理負荷が均等にならないという事実により、期待通りの性能を得ることができなかった。
【０００６】
これらに対し、特願平０８−２１１２５８号に提案されている描画処理装置においては、ページ内での描画負荷の偏りにかかわらず、各並列描画処理部の処理負荷を均一にする上、並列描画処理部の一部の処理装置の処理がなんらかの外乱により遅れた場合も救済することを可能としていた。
【０００７】
【発明が解決しようとする課題】
しかし、この特願平０８−２１１２５８号に開示された描画処理装置においても、実行時に順番に割り当てられる描画領域の内、最後の方で割り当てられる分割描画領域に予想以上に負荷が偏っていた場合には、その分割描画領域の処理がボトルネックとなって、並列処理の効果が十分に上がらない場合があるという問題があった。
【０００８】
本発明はこのような点を鑑みてなされたものであり、複数の描画処理部に対して担当する分割描画領域が処理の実行時に動的に定められる並列描画処理装置において、描画オブジェクトの描画領域上の分布にかかわらず、安定して、より高速な並列描画処理を行う描画処理装置を提供することを目標とする。
【０００９】
【課題を解決するための手段】
本発明では上記課題を解決するために、ページ記述言語を入力として描画処理を行う描画処理装置において、描画命令を受け取り、描画図形の内部データを構成する描画データを生成する描画データ生成手段と、前記描画データの格納及び描画処理手段に対する出力の制御を行う描画データ格納制御手段と、前記描画データ格納制御手段からの描画データを入力して描画処理を実行する複数の描画処理手段と、前記複数の描画処理手段における処理単位を決定するための描画領域の分割基準となる基準値を保持する分割基準管理手段と、分割基準管理手段の有する基準値に基づいて描画領域を分割し、描画処理手段各々の要求に応じて、該分割描画領域を描画処理手段各々に割り当てる処理担当範囲割り当て手段と、複数の描画処理手段から出力される複数の処理結果を記憶する処理結果格納手段と、処理結果格納手段に格納された処理結果の出力を行う出力手段とを備え、分割基準管理手段は、異なる複数の基準値を有し、複数の描画処理手段における処理の全体の進行度に応じて選択される該複数の基準値の中の１つの基準値を処理担当範囲割り当て手段に出力し、該処理担当範囲割り当て手段は、該選択された基準値に基づき描画領域を分割し、該分割描画領域を複数の描画処理手段各々に割り当てることを特徴とする。
【００１０】
また、本発明の描画処理装置における分割基準管理手段は、描画処理手段における描画データの処理の進行度を示すデータとして描画処理手段に割り当て済みの分割描画領域の副走査方向の位置座標値を受領し、該受領位置座標値に基づいて複数の基準値から１つの基準値を選択する構成を有することを特徴とする。
【００１１】
また、本発明の描画処理装置における分割基準管理手段は、描画処理手段における描画データの処理の進行度を示すデータとして描画処理手段に割り当て済みの描画領域の面積と処理を要する全体面積、例えばページあたりの面積との比を示す値を受領し、該受領値に基づいて複数の基準値から１つの基準値を選択する構成を有することを特徴とする。
【００１２】
また、本発明の描画処理装置における分割基準管理手段の有する複数の基準値の各々に基づいて複数の描画処理手段に割り当てられる分割描画領域の各々は、描画領域の副走査方向における最小分割単位である単位描画領域（Ｒｎ）の整数倍となることを特徴とする。
【００１３】
また、本発明の描画処理装置における分割基準管理手段は、描画処理手段における描画データ処理の進行に従って、該描画処理手段に割り当てる描画領域の大きさを減少させるように基準値を選択することを特徴とする。
【００１４】
また、本発明の描画処理装置における分割基準管理手段は、描画処理手段における描画データ処理の進行に従って、該描画処理手段に割り当てる分割描画領域の単位描画領域数を減少させるように基準値を選択することを特徴とする。
【００１５】
また、本発明の描画処理装置における分割基準管理手段は、描画処理手段における描画データ処理の進行に従って、該描画処理手段に割り当てる１以上の単位描画領域各々に含まれる描画データの総数を減少させるように基準値を選択することを特徴とする。
【００１６】
また、本発明の描画処理装置における処理担当範囲割り当て手段は、複数の描画処理手段からの処理の割り当て要求に応じて、描画領域の割り当てを実行することを特徴とする。
【００１７】
また、本発明の描画処理装置における処理担当範囲割り当て手段は、分割基準管理手段の有する複数の基準値に基づき、複数の描画処理装置に対して割り当てる分割描画領域の大きさを、描画処理に係るデータについて一括して決定する構成を有することを特徴とする。
【００１８】
また、本発明の描画処理装置における処理担当範囲割り当て手段は、複数の処理手段に対する処理の割り当てを実行する際に、描画データ格納制御手段からの描画データに関する情報を受領し、該情報に基づいて描画領域の割り当てを実行することを特徴とする。
【００１９】
また、本発明の描画処理装置における処理担当範囲割り当て手段は、複数の描画処理装置からの描画領域要求を排他的に実行する排他的インタフェースを有することを特徴とする。
さらに、本発明の第２の側面は、描画命令を解釈し、描画処理を実行する描画処理方法において、描画命令を受け取り、描画図形の内部データを構成する描画データを生成する描画データ生成ステップと、前記描画データの格納及び描画処理手段に対する出力の制御を行う描画データ格納制御ステップと、複数の描画処理手段において、前記描画データ格納制御ステップの制御に基づいて出力される描画データを入力して描画処理を実行する描画処理ステップと、前記複数の描画処理手段における処理単位を決定するための描画領域の分割基準となる異なる複数の基準値から、前記複数の描画処理手段における処理の全体の進行度に応じて１つの基準値を選択し、選択した基準値を処理担当範囲割り当て手段に出力する分割基準管理ステップと、分割基準管理ステップにおいて選択された基準値に基づいて前記描画領域を分割し、前記描画処理手段各々の要求に応じて、該分割された描画領域を前記描画処理手段各々に割り当てる処理を実行する処理担当範囲割り当てステップと、前記複数の描画処理手段から出力される複数の処理結果を処理結果格納手段に格納する処理結果格納ステップと、前記処理結果格納手段に格納された処理結果の出力を行う出力ステップとを有することを特徴とする描画処理方法にある。
【００２０】
【発明の実施の形態】
以下、本発明の実施の形態を図面を参照しながら説明する。図１は、本発明の描画処理装置の原理図である。描画データ生成手段２０は、図示しない入力手段から入力されるページ記述言語１０である描画記述の解釈・展開を行い、描画記述に記述されていたイメージを描画するための描画データを生成して、描画データ格納制御手段３０に送信する。描画データ格納制御手段３０は、複数の描画処理手段４０ａ〜４０ｎに、描画データを送信する。
【００２１】
分割基準管理手段７０は、処理担当範囲割り当て手段６０から、割り当てを決定中の描画領域の位置座標や、割り当て済面積と描画領域全体の面積の比などの情報や、処理の進度を表した情報を受け取り、内部に記憶されている関数式あるいは表などを用いて、受け取った情報に対応した描画領域の分割基準値を求め、処理担当範囲割り当て手段６０に送信する。
【００２２】
処理担当範囲割り当て手段６０は、分割基準管理手段７０を参照して、２種類以上の大きさに描画領域を分割して複数の分割描画領域を規定し、複数の描画処理手段４０ａ〜４０ｎに対して、要求の順に割り当てる。
【００２３】
描画処理手段４０ａ〜４０ｎは、処理担当範囲割り当て手段６０と通信を行い、担当する分割描画領域の指定を受け取り、指定された分割描画領域の処理に必要な描画データを描画データ格納制御手段３０から読みだして描画処理を行う。
【００２４】
そして、処理結果格納制御手段５０は、描画処理手段４０ａ〜４０ｎで処理された結果を一時格納し、出力装置２００にその結果を送信する。
【００２５】
また、これらの各手段はその初期化や処理の開始、終了、同期などは図示しない制御手段により制御されて動作する。
【００２６】
ここで、分割基準管理手段７０は、処理の進度に対する基準値を、テーブルや表形式で管理していてもよいし、処理の進度に対する、関数の形で保持していてもよい。ここで、処理の進度が進むにつれて、基準値が分割描画領域の大きさを連続的あるいは段階的に小さくする方向に変化することを実現できればよい。
【００２７】
図２は、本発明の画像処理装置の別の実施例を示す構成図である。この図２においては、描画データ格納制御手段３０と処理担当範囲割り当て手段６０が通信路により接続されている。この通信路によって、描画データ格納制御手段３０は、複数の描画処理手段４０ａ〜４０ｎに、描画データを送信する以外に、処理担当範囲割り当て手段６０に対して、格納している描画データの存在範囲等の情報を処理担当範囲割り当て手段６０の要求に従って送信する。また、処理担当範囲割り当て手段６０は、分割描画領域を決定する際に、描画データ格納制御手段３０と通信して、描画データに関する情報を得て、分割描画領域の決定の際に利用する。
【００２８】
図３は、本発明が適用されるシステムの一例についての概念図である。このシステムは、ネットワーク４００に接続されたネットワークインタフェース３００を介して、描画処理装置１００が接続される。そして、描画処理装置１００からの処理結果を出力する出力装置２００が接続される。
【００２９】
システムの動作としては、図示しないクライアント・コンピュータから、イーサネットケーブルや電話線や無線などの様々な媒体を使用したネットワークを介して描画出力用のデータが送られる。この描画出力用のデータはネットワークインタフェース３００等のインタフェース装置を介して、描画処理装置１００に受信され処理される。そして、処理の終ったデータは出力装置２００に転送されて紙やフィルムやラスタイメージを表示するために使用されるメモリ装置などの媒体状にイメージが再現される。
【００３０】
図４は、描画処理装置の全体の流れを示すフローチャートである。描画処理装置が起動されるとまず、起動時の初期化が行われる（ステップ、Ｓ４０１）。このとき、図示しない制御手段の初期化や図示しないメモリ管理機構の初期化などが行われる他、この段階で分割基準管理手段７０等の初期化を行ってもよい。起動時の初期化が終ると、描画処理装置１００は描画記述の入力待ちである、ジョブ待ちの状態になる（ステップ、Ｓ４０２）。ジョブが受け付けられ、描画記述が入力されると、ジョブ開始時の初期化が行われる（ステップ、Ｓ４０３）。ここでは、描画処理装置１００の構成要素のいくつかについての初期化を行ってもよいが、特に、ジョブ毎に変化する設定についての初期化が行われる。例えば入力データ中に記述してある設定による初期化などが例としてあげられる。また、本発明においては、例えば、ジョブ毎に描画領域の分割基準を変更する場合には、この段階において分割基準管理手段７０の設定を行うことになる。ジョブ開始時の初期化が終ると、１ページごと描画処理が行われ、ジョブの全ページあるいは指定されたページ全ての描画処理が終るとジョブの終了処理が行われる（ステップ、Ｓ４０４、４０５、４０６）。ジョブの終了処理後、まだ他のジョブを処理するかどうかを判定し、他のジョブを更に処理しない場合には、獲得しているメモリ領域の解放などの終了処理を行ってから終了する（ステップ、Ｓ４０７、４０８）。
【００３１】
以降は簡単のため、説明は１ページ分の描画処理について行うものとする。図５は、１ページ分の処理の流れの概略を示した図である。
【００３２】
描画処理が開始されると、各手段において初期化が行われる（ステップ、Ｓ５０１）。この時、描画データ格納制御手段３０においては、記憶領域の初期化が行われ、処理結果格納制御手段５０は、処理結果を格納する記憶領域の初期化が行われ、描画処理手段４０ａ〜４０ｎは描画処理時に使用するワーク領域の初期化が行われ、さらに、処理担当範囲割り当て手段６０では、処理の単位の設定や処理済の位置などの初期化が実行される。また、この時、ページ毎に特殊な処理を行う設定が例えば入力されたページ記述言語１０などを通じて指定されていた場合には、この初期化の際にその設定が行われるし、ページの区切りで描画領域の分割基準を変更したい場合には、この段階で分割基準管理手段７０の設定変更が行われる。
【００３３】
初期化が終了すると、描画データ生成手段２０に対して、描画記述を読み込んで１ページ分の描画データを生成する指示が出される。そして、１ページ分の描画データが生成（ステップ、Ｓ５０２）され、描画データ格納制御手段３０に格納されると、図１、図２において図示していない制御手段は複数の描画処理手段４０ａ〜４０ｎに対して処理の開始を通知する。この後、描画処理手段による処理が実行される（ステップ、Ｓ５０３）。制御手段は、複数の描画処理手段４０ａ〜４０ｎの処理が全て終了したことを、描画処理手段４０ａ〜４０ｎからの通知を通して知る。あるいは未処理の描画領域が無いことを描画処理手段４０ａ〜４０ｎの全てに通知したことを処理担当範囲割り当て手段６０から通知される。
または、処理結果格納制御手段５０からの、描画領域全体の結果が格納されたことの通知によって処理の終了を知ることができる。この処理終了により、処理結果格納制御手段５０内のデータは、出力装置２００に対して描画処理の結果として出力（ステップ、Ｓ５０４）される。そして、終了処理（ステップ、Ｓ５０５）時には、使用したメモリの解放などが行われる。
【００３４】
次に、描画処理装置の各手段について詳しく説明する。図６は描画データ生成手段２０の処理の流れを示すフローチャートである。描画データ生成手段２０は、処理の開始を指示されるとページ記述言語である描画記述のデータを読み込み、１ページを構成する描画記述のデータが残っている間、描画記述のデータを読み込み、解釈を行って、描画データを生成（ステップ、Ｓ６０１、Ｓ６０２）して、生成した描画データを描画データ格納制御手段３０に送信する（ステップ、Ｓ６０３）ことを繰り返し行う。
【００３５】
図７に、描画データ生成手段２０で生成される描画データのデータ構造の一例として、以降の説明で使用するものを示す。図７では、走査線方向に平行な２辺を持つ台形表現により描画領域を表現する描画データ２１（図７、下図）とそのデータ構造２２（図７、上表）とを示している。そして、副走査線方向にＹ座標、走査線方向にＸ座標をとって描画領域上での位置をＸＹ座標系で表現している。この座標系の取り方は以降の説明でも使用する。
【００３６】
データ構造２２は描画領域に関する値（ＹＭＩＮ，ＹＭＡＸ，Ｘ１，Ｘ２，ＤＸ１，ＤＸ２）以外には、色などの塗りつぶし属性値（ＡＴＴＲ）と、重ね塗りの順番を制御する塗りつぶし優先順位の値（ＰＲＩＯ）などが格納される。台形データによる塗りつぶし領域の表現はさまざまなものが挙げられるが、ここではその一例を示している。図に示したＹ座標値の最大値ＹＭＡＸと最小値ＹＭＩＮ、左側の辺についてはＹ座標値の最小値の位置におけるＸ座標値Ｘ１、Ｙ座標値が単位量増加した際のＸ座標値の増分値ＤＸ１、右側の辺についてはＹ座標値の最小値の位置におけるＸ座標値Ｘ２、Ｙ座標値が単位量増加した際のＸ座標値の増分値ＤＸ２、により台形領域を少なくとも規定できる。
【００３７】
なお、本実施例の形態においては、説明の簡単のために描画データとして台形表現により塗りつぶし領域を表現する描画データを用いているが、描画データは主走査線方向に平行な２辺を持つ台形表現である必要はない。例えば、点列やベクトル表現による多角形表現、曲線を含めるあるいは含めない線分列表現、直線分のみからなるベクトル表現、向かい合う線分列同士を関連づけた線分列ペアによる表現、描画領域を三角形や矩形や台形などで分割した表現など、塗りつぶし領域あるいは塗りつぶし領域の境界あるいは塗りつぶし領域の境界の一部など、描画領域の座標系上において座標値や大きさを特定できる表現形式であれば何を用いても、本発明のの想定する描画データの範囲である。
【００３８】
次に描画データ格納制御手段３０について説明を行う。図８は描画データ格納制御手段３０の構成の一例を示した概念図である。
【００３９】
描画データ格納用インタフェース３１は、描画データ生成手段２０からの描画データを受信する。描画データ登録手段３５は、直接あるいは間接的に、描画データのＹ座標値の最大値、最小値の座標値をもとに描画データを抽出できるように登録する。これは、例えば、描画領域のＹ方向の単位描画領域に対応する描画データテーブルを用意し、各描画データをＹ方向の座標値の例えば最小値が含まれる単位描画領域に対応する場所に、描画データを登録することにより実現できる。描画データ送出用インタフェース３６は、描画処理手段４０と通信を行う。
【００４０】
図９は描画データ格納制御手段３０の図８に示した構成の描画データを格納する段階の処理の流れを示した図である。描画データ格納制御手段３０は、１ページ分の描画データが送られて来る間、描画データを描画データ登録手段３５に登録する（ステップ、Ｓ９０１）。そして、これらの操作は描画データ生成手段２０により生成されるすべての描画データについて入力が終了するまで（ステップ、Ｓ９０２）行われる。
【００４１】
図１０は描画データ格納制御手段３０の別の構成例を示した図である。この描画データ格納制御手段３０の構成は描画処理装置１００の構成が、図２に示したように描画データ格納制御手段３０と処理担当範囲割り当て手段６０の間に通信路が設けられている場合の描画データ格納制御手段３０の構成の一例である。
【００４２】
描画データ格納用インタフェース３１は、描画データ生成手段２０からの描画データを受信する。描画データ存在範囲抽出手段３２は、受信した各描画データから副走査線方向（以降説明の簡単のため、副走査線の方向をＹ方向、副走査線方向の位置を示す数値をＹ座標値、これに対し走査線の方向をＸ方向、走査線方向の位置を示す数値をＸ座標値と呼ぶ。）に対する存在範囲を検出する。
【００４３】
描画データ存在範囲集計手段３３は、検出したＹ方向の存在範囲を集計する。この集計とは例えば、Ｙ方向に順に処理することにより各単位描画領域に存在する描画データの個数を集計することができる。これは例えば、各単位描画領域をＹ座標値の小さい側から大きい側に順に処理するものとしたとき、処理中の単位描画領域の処理以前に存在していた描画データの個数から、一つ前で処理対象としていた単位描画領域にＹ座標値の最大値を持つ描画データの個数を引き、処理中の単位描画領域に最小値があるものとして登録されている描画データの個数を足すことによって順に得ることができる。描画データ存在数通知用インタフェース３４は、処理担当範囲割り当て手段６０と通信する。描画データ登録手段３５は、直接あるいは間接的に、描画データのＹ座標値の最大値、最小値の少なくとも一つの座標値をもとに描画データを抽出できるように登録する。描画データ送出用インタフェース３６は、描画処理手段４０ａ〜４０ｎと通信を行う。
【００４４】
図１１は描画データ格納制御手段３０の図１０に示した構成の描画データを格納する段階の処理の流れを示した図である。描画データ格納制御手段３０は、１ページ分の描画データが送られて来る間、送られて来た描画データに対して、その描画データについて描画データ存在範囲抽出手段３２により、その描画データのＹ方向の存在範囲を検出（ステップ、Ｓ１１１）し、この両端を描画データ存在範囲集計手段３３に登録（ステップ、Ｓ１１２）する。例えば、描画データ存在範囲抽出手段３２が描画データのＹ方向の座標値の最大値と最小値を抽出する。そして、最大値に当てはまる個数、最小値に当てはまる個数をカウントする一組ずつのカウンタが単位Ｙ座標毎に用意されている描画データ存在範囲集計手段３３中の対応するカウンタをインクリメントする。（以降、ここで例に挙げたようなカウンタのテーブルについて参照する際には、最小値側のカウンタを進入カウンタ、最大値側のカウンタを退出カウンタと呼ぶ。）
【００４５】
次に、描画データを描画データ登録手段３５に登録（ステップ、Ｓ１１３）する。例えば、描画領域のＹ方向の単位領域に対応する描画データテーブルを用意し、各描画データをＹ方向の座標値の例えば最小値に対応する場所に、描画データを登録することにより実現できる。そして、これらの操作は描画データ生成手段２０により生成されるすべての描画データについて行われる（ステップ、Ｓ１１４）。
【００４６】
なお、ここで説明する実施例においては、描画データ格納制御手段３０内の描画データ存在範囲集計手段３３、描画データ登録手段３５等にテーブル形式のデータ構造を使用するが、これは説明の簡単のためであり、他のデータ構造を用いてもよい。リスト構造や、ツリー構造、ハッシュ機構などのさまざまな他のデータ構造を利用しても同様の機能を得ることは可能である。
【００４７】
描画データ格納制御手段３０は、描画データの格納時以外にも、描画処理が行われている段階において、描画処理手段４０ａ〜４０ｎからの要求を受けて、データの要求された描画データの抽出と送出を行う。このとき、描画処理手段４０ａ〜４０ｎからは、Ｙ方向の座標値、あるいは、Ｙ方向の座標値の範囲を指定される。描画データ格納制御手段３０はその指定された座標値あるいは範囲に対応する描画データを一つずつあるいはまとめていくつかずつ、あるいは、その指定された分類に対応する描画データ全てを要求もとの描画処理手段４０に送信する。上記の描画データを送信する処理のうち、説明の簡単な要求された範囲に登録されている描画データをまとめて返送する場合について、概略を図１２を用いて説明する。
【００４８】
描画データ格納制御手段３０は、１ページ分の処理が終るまでの間、複数の描画処理手段４０ａ〜４０ｎからの個別に要求を受けては、描画データを転送することを繰り返す。具体的には、通信を受ける（ステップ、Ｓ１２１）と、その通信が１ページの処理の終了の通知でなく描画データの要求命令であれば（ステップ、Ｓ１２２）、その要求元にデータを転送できるだけの情報、すなわち、要求元を一意に示すＩＤやアドレス、あるいは、要求元の描画処理手段４０内の局所記憶装置内のアドレス、あるいは、要求元の描画処理手段４０が参照可能な記憶領域のアドレスを一時、描画データ送出用インタフェース３６内の図示しない記憶部に記憶（ステップ、Ｓ１２３）する。そして、描画データを要求されている範囲の指示を読み込み（ステップ、Ｓ１２４）、この要求された範囲に登録されている描画データを収集（ステップ、Ｓ１２５）する。そして、収集した描画データを一時保存されている前述の要求元を示す情報を元にして、転送（ステップ、Ｓ１２６）する。この処理の流れは、図８の構成においても、図１０の構成においても共通の流れとなる。
【００４９】
この描画データを転送する際あるいは、描画データを収集する際において描画データ格納制御手段３０内から描画データを取り出す際には、その描画データ自体を描画データ格納制御手段３０内に残らないように破壊的に取り出してもよいし、描画データ格納制御手段３０内の描画データ自体は保存したまま、その参照用のデータや、描画データの複製物を作って収集する場合もありうる。また、描画データ格納制御手段３０のデータの送出の機能は、描画処理手段４０ａ〜４０ｎ間の共有メモリ上に構成されている場合には、描画データ格納制御手段３０が能動的な機能を果たさずとも、描画処理手段４０ａ〜４０ｎが必要な範囲に登録されている描画データにアクセスできるデータ構造を提供するだけでもよい。このとき各描画処理手段４０ａ〜４０ｎはそれぞれ勝手に描画データを読み出していくことが可能である。
【００５０】
そして、描画データ格納制御手段３０が、図１０に示された構成を取る場合には、処理担当範囲割り当て手段６０と通信する際の処理が存在する。
【００５１】
処理担当範囲割り当て手段６０は、描画処理手段４０ａ〜４０ｎに対して、描画領域を分割して処理の担当を割り当てる。この描画領域の分割を決定する際に、単純に位置座標のみを基準にして描画領域を分割する以外にも、分割した描画領域内のオブジェクトの数などの入力データの特徴を反映して分割することもできる。このように、位置座標値以外を基準として描画領域の分割を行う場合に本発明を適用する場合の例について、ここでは入力データ中の描画データの分布を利用して描画領域の分割を決定する場合について説明を行う。そして、描画データの分布に関する情報を、処理担当範囲割り当て手段６０が得るために、処理担当範囲割り当て手段６０は描画データ格納制御手段３０と通信を行う。
【００５２】
以降の説明において、単位描画領域はＹ方向の最小分割単位であり、分割描画領域は、処理担当範囲割り当て手段６０により大きさと位置を決められて各描画処理手段４０に割り当てられる領域である。例えば、単位描画領域は走査線１〜数本分のＸ方向に細長い領域であり、分割描画領域はこの単位描画領域数個から数十個程度の大きさの領域となる。
【００５３】
処理担当範囲割り当て手段６０が分割描画領域を決定する際に、例えば、割り当てを決定中の分割描画領域中の各単位描画領域ごとに存在する（交わる）描画データの個数の総計が、基準値よりも大きいか小さいかを判定基準として分割描画領域を決定する例を考えると（処理担当範囲割り当て手段６０の処理の流れについては、後に改めて行う）、処理担当範囲割り当て手段６０は、描画データ格納制御手段３０に対して、単位描画領域を指定して、その単位描画領域中に描画データがいくつ存在するかというデータを要求することになる。
【００５４】
図１３は、この処理について、処理担当範囲割り当て手段６０と描画データ格納制御手段３０の通信ごとの処理の流れを示した図である。通信が開始されると、まず、データの要求されている範囲（簡単にはＹ座標値の範囲）を受け取り（ステップ、Ｓ１３１）、そして、指定された範囲について、描画データ存在範囲集計手段３３に問い合わせを行う。描画データ存在範囲集計手段３３は、この問い合わせの時点で指定された範囲に存在する描画データの個数を計算し、あるいは、予め計算して記憶してあった場所から取り出し（ステップ、Ｓ１３２）、そのデータを処理担当範囲割り当て手段６０に送出（ステップ、Ｓ１３３）する。
【００５５】
次に、処理担当範囲割り当て手段６０について説明する。図１４は、処理担当範囲割り当て手段６０の構成を示した図である。排他的インタフェース６１は、描画処理手段４０ａ〜４０ｎからいずれか一つの描画処理手段の要求を受け付ける。すると、分割描画領域決定手段６２で決定された分割描画領域についての情報が例えば、分割描画領域のＹ座標値の最大値と最小値の組などとして、問い合わせた描画処理手段に通知される。分割描画領域の決定は、例えば、順次描画領域の範囲を広げて行きながら、分割描画領域の幅が、後述する基準値と比較されることにより行われる。この分割描画領域の決定は、描画処理の進行と同期しながら行われてもよいし、描画処理に先立って決定が行われていてもよい。基準値問い合わせ用インタフェース６７は、分割描画領域決定手段６２から処理中の位置座標や、処理中の単位描画領域の位置や、処理済の面積と全体の描画領域の面積の比などの情報を受けて、分割基準管理手段７０と通信し、その処理時点での基準値を分割描画領域決定手段６２に通知する。描画範囲判定手段６３は、描画処理の進行にともない処理すべき描画領域がなくなった状態を判定する。未処理位置保持手段６４は、Ｙ方向の次の未処理位置すなわち、まだ割り当てを行っていない位置を保持するための保持手段であり、描画処理手段４０ａ〜４０ｎに対して分割描画領域を割り当てる際に更新される。分割描画領域決定手段６２は、描画範囲判定手段６３と未処理位置保持手段６４を参照し、順に分割描画領域の範囲を広げながら、基準値問い合わせ用インタフェース６７に問い合わせを行って、分割描画領域を決定することと、排他的インタフェース６１を通じた要求を受け、要求元の描画処理手段４０に分割描画領域の割り当ての情報を通知することを行う。
【００５６】
図１５は、処理担当範囲割り当て手段６０の処理の流れを示すフローチャートである。（ただし、このフローチャートは分割描画領域の決定を描画処理の進行と同期して行う場合についての処理の流れについてのみ示している）処理担当範囲割り当て手段６０は、全体の処理開始時に必要なら描画範囲判定手段６３や分割描画領域決定手段６２や分割基準管理手段の初期化が行われる他に、描画処理手段４０ａ〜４０ｎからの問い合わせがあると以下に示すような処理をおこなう。
【００５７】
描画処理手段４０ａ〜４０ｎからの要求は、排他的インタフェース６１によりアクセスを制限され、同時に複数の描画処理手段４０ａ〜４０ｎからいずれか一つの描画処理手段の要求を受け付ける（ステップ、Ｓ１５１）。担当範囲の割り当て要求があると、描画範囲判定手段６３を参照し、まだ未処理の描画領域があるかどうかを判断（ステップ、Ｓ１５２）する。未処理の描画領域が既になければ、その旨を要求元の描画処理手段に通知する。未処理の描画領域がまだある場合には、未処理位置保持手段６４に保持されている位置から順に、単位描画領域についての検討を行う。すなわち、割り当てを検討中の描画領域を少しずつ広げる（ステップ、Ｓ１５３）と共に、検討中の単位描画領域の位置での基準値を分割基準管理手段７０に問い合わせ、その処理位置における基準値を得る（ステップ、Ｓ１５４）。この基準値と、前記検討中の分割描画領域の幅を比較（ステップ、Ｓ１５５）し、基準値を越えていない場合には、さらに検討中の分割描画領域の幅を広げる処理を繰り返す。また、基準値を越えていた場合には以下の処理を行う。
【００５８】
ステップ１５５において、基準値を超えたことが確認されると、次に、割り当てる分割描画領域が実際にあるかどうかを判断（ステップ、Ｓ１５６）する。無い場合には、割り当てる分割描画領域が無いことを要求元の描画処理手段に送信（ステップ、Ｓ１５９）し、ある場合には、要求元の描画処理手段にその分割描画領域の情報、例えば、分割描画領域の境界の座標値などの情報を送信（ステップ、Ｓ１５７）して、未処理位置保持手段６４に保持されている位置を次の未処理の描画位置に更新（ステップ、Ｓ１５８）する。
【００５９】
図１６は、処理担当範囲割り当て手段６０が、位置座標以外の情報も描画領域の分割に使用する場合の例として、分割描画領域内の単位描画領域ごとの描画データの個数の総計値により分割描画領域を決定する場合の構成例を示した図である。
【００６０】
排他的インタフェース６１は、複数の描画処理手段４０ａ〜４０ｎからいずれか一つの描画処理手段の要求を受け付ける。すると、分割描画領域決定手段６２で決定された分割描画領域についての情報が例えば、分割描画領域のＹ座標値の最大値と最小値の組などとして、問い合わせた描画処理手段に通知される。分割描画領域の決定は、例えば、順次描画領域の範囲を広げて行きながら、描画データの個数の総計が、後述する基準値と比較されることにより行われる。基準値問い合わせ用インタフェース６７は、分割描画領域決定手段６２から処理中の位置座標や、処理中の単位描画領域の位置や、処理済の面積と全体の描画領域の面積の比などの情報を受けて、分割基準管理手段７０と通信し、その処理時点での基準値を分割描画領域決定手段６２に通知する。描画範囲判定手段６３は、描画処理の進行にともない処理すべき描画領域がなくなった状態を判定する。未処理位置保持手段６４は、Ｙ方向の次の未処理位置を保持するための保持手段であり、描画処理手段４０ａ〜４０ｎに対して分割描画領域を割り当てる際に更新される。描画データ数問い合わせ用インタフェース６６は、検討中の単位描画領域内の描画データの個数を描画データ格納制御手段３０に問い合わせるためのインタフェースである。描画データ数集計手段６５は、描画データ数問い合わせ用インタフェース６６を通じて得られた単位描画領域ごとの描画データ数を累算し、その値を保持する。分割描画領域決定手段６２は、描画範囲判定手段６３と未処理位置保持手段６４を参照し、順に分割描画領域の範囲を広げながら、基準値問い合わせ用インタフェース６７と描画データ数問い合わせ用インタフェース６６と描画データ数集計手段６５に問い合わせを行って、分割描画領域を決定することと、排他的インタフェース６１を通じた要求を受け、要求もとの描画処理手段４０に分割描画領域の割り当ての情報を通知することを行う。
【００６１】
図１７は、処理担当範囲割り当て手段６０が、図１６に示した構成を取る場合の処理の流れを示すフローチャートである。処理担当範囲割り当て手段６０は、全体の処理開始時に初期化が行われる他に、描画処理手段４０からの問い合わせがあると以下に示すような処理を行う。
【００６２】
描画処理手段４０ａ〜４０ｎからの要求は、排他的インタフェース６１によりアクセスを制限され、同時に複数の描画処理手段４０ａ〜４０ｎからいずれか一つの描画処理手段の要求を受け付ける（ステップ、Ｓ１７０１）。担当範囲の割り当て要求があると、描画範囲判定手段６３を参照し、まだ未処理の描画領域があるかどうかを判断（ステップ、Ｓ１７０２）する。未処理の描画領域が既になければ、その旨を要求元の描画処理手段に通知する。未処理の描画領域がまだある場合には、未処理位置保持手段６４に保持されている位置から順に、単位描画領域についての検討を行う。すなわち、描画データ格納制御手段３０に対してその単位描画領域ごとの描画データの数を問い合わせ（ステップ、Ｓ１７０３）、そして、未処理位置保持手段６４に保持されている位置から順に、前記と同様の処理により単位描画領域ごとの描画データの個数を累算し、単位描画領域の負荷推定値と分配描画領域の負荷推定値とを求める（ステップ、Ｓ１７０４、Ｓ１７０５）。一方、検討中の単位描画領域の位置での基準値を、分割基準管理手段７０に問い合わせ、その処理位置における基準値を得る（ステップ、Ｓ１７０６）。この基準値と、前記単位描画領域ごとの描画データの累算値を比較し、累算値が、基準値を越えるかどうかを判断（ステップ、Ｓ１７０７）する。値を越えない場合は、次の単位描画領域にまで、検討している分割描画領域を広げて処理を続け、そうでない場合には以下の処理を行う。
【００６３】
ステップ、Ｓ１７０７において、累算値が、基準値を越えたと判断されると、次に、割り当てる分割描画領域が実際にあるかどうかを判断（ステップ、Ｓ１７０８）する。無い場合は、分配する描画領域がないことを要求元の描画処理手段に送信（ステップ、Ｓ１７１１）し、ある場合には、要求元の描画処理手段にその分割描画領域の情報、例えば、分割描画領域の境界座標値などの情報を送信（ステップ、Ｓ１７０９）して、未処理位置保持手段６４に保持されている位置を次の未処理の描画位置に更新（ステップ、Ｓ１７１０）する。このとき、累算値は初期化されてもよいし、基準値と演算されて更新されてもよい。
【００６４】
次に描画処理手段４０ａ〜４０ｎについて説明を行う。描画処理手段の内部構成は、いずれも同じなので描画処理手段４０として説明する。
【００６５】
図１８は、描画処理手段４０の構成を示す図である。処理済描画位置保持手段４１は、処理済みの描画位置を保持する。担当描画範囲保持手段４２は、処理担当範囲割り当て手段６０から得られた、担当する分割描画領域についての情報（例えば、描画領域上での範囲を範囲の境界を示す座標値などで表した情報）を保持するための保持手段であり、半導体記憶装置や磁気ディスクなどにより容易に実現できる。
【００６６】
描画データ保持手段４３は、描画データ格納制御手段３０から得られた描画データを一時保持すると共に、先に処理した他の描画領域から引き継がれる描画データも保持するための保持手段である。この描画データ保持手段４３も半導体記憶装置などのさまざまな記憶手段により実現することが可能である。
【００６７】
描画データ判定・破棄手段４４は、描画機構４５が処理対象とする描画位置が更新されることに伴い、描画データ保持手段４３内の描画データの内、描画処理の行われる位置が、その描画データの存在範囲外になってしまったものを描画機構４５の処理の対象から除いて、描画機構４５の処理の効率をあげると共に、描画データ保持手段４３の必要記憶容量を削減するためのものである。
【００６８】
描画機構４５は、内部に描画位置を保持し、描画データ保持手段４３内のデータを描画処理バッファ４６をワーク領域として利用しながら処理して、担当する分割描画領域に関して、ラスタイメージデータと対応のとれるデータに変換する。処理結果データの形式としては、ラスタイメージデータを代表として、主走査線方向の範囲と色により表現されるランレングスデータ、これらのデータをデータ圧縮の技術により圧縮したデータ等色々な形式がありうる。描画機構４５は、処理結果を単位描画領域ごとに処理結果格納制御手段５０内に格納してもよい。
また、ある程度集めてから処理結果格納制御手段５０内に格納してもよい。特に、この処理結果格納制御手段５０は、描画処理手段４０ａ〜４０ｎ間の共有メモリ上に構築されている場合、例えば、副走査方向のテーブルの領域が予め確保されていれば、描画処理手段４０ａ〜４０ｎが各々、そのテーブルに処理結果を格納した記憶領域のアドレスを登録してもよい。
【００６９】
図１９は描画処理手段４０の処理の流れを示すフローチャートである。描画処理手段４０は、描画データ格納制御手段３０に予め定められた範囲のデータが格納されると、図示しない制御手段により動作の開始（ステップ、Ｓ１９０１）を指示される。処理の開始時には、処理済描画位置保持手段４１と描画データ保持手段４３と描画処理バッファ４６の初期化が行われる（ステップ、Ｓ１９０２）。初期動作が終ると、処理担当範囲割り当て手段６０に対して処理を担当する分割描画領域の問い合わせを行う（ステップ、Ｓ１９０３）。処理を担当する分割描画領域が伝えられると、これを担当描画範囲保持手段４２に格納し、描画処理位置を担当描画範囲保持手段４２に格納された範囲の片側の位置に設定（ステップ、Ｓ１９０４）する。
【００７０】
まず、描画データ判定・破棄手段４４が描画データ保持手段４３内に保持されている描画データを検査して、描画位置に影響を与えなくなった描画データを選び、破棄（ステップ、Ｓ１９０５）する。そして、処理済描画位置保持手段４１に格納されている位置と描画処理位置を組み合わせたデータとを使用して描画データ格納制御手段３０に描画データの要求を行う（ステップ、Ｓ１９０６）。例えば、この段階の処理は、描画データ格納制御手段３０が共有メモリ上の記憶領域として実現されていた場合には、各描画処理手段４０が処理済描画位置保持手段に格納されていた位置から、描画位置までに登録されている描画データを読み込むという処理になる。
【００７１】
また、描画機構４５により描画データ保持手段４３内に保持されている描画データから、描画処理バッファ４６を使用して処理（ステップ、Ｓ１９０７）が行われ、処理結果データが作成される。この段階での描画機構４５としての機能を発揮するものは、様々のものが提案されているので、それらの内、出力結果データの種類に応じたものを用いてもよい。ここでは、描画処理バッファ４６をラインバッファとして使用して、走査線単位で描画データを優先順位の低い順に重ね塗りを行って走査線毎のラスタデータを作成して行くものとして説明を続けるが、他の方法を特に排除するものではない。描画位置が決まると、描画処理バッファ４６内のラインバッファ領域の初期化を行う。そして、描画データ保持手段４３内のデータを優先順位の低い方から取り出し、これに対して決定された描画位置に対応する走査線方向の色塗情報を表現するランレングスデータを生成して、ラインバッファの対応する場所に色データを格納する。これを、描画データ保持手段４３内に格納されている描画データ分繰り返して処理する。
【００７２】
描画位置の処理が終る（ステップ、Ｓ１９０８）と、描画処理手段４０は描画処理バッファ４６内の処理結果を処理結果格納制御手段５０に転送（ステップ、Ｓ１９１０）する。描画処理手段４０ａ〜４０ｎが共有メモリを有する並列計算機システム上に構築されている場合には、例えば、描画位置の更新（ステップ、Ｓ１９０９）時に描画処理バッファ４６を共有メモリ上の領域として確保して描画機構４５を動作させる。そして、処理結果の格納は、処理結果格納制御手段５０内の描画位置を示すテーブルの描画位置に対応する場所に、処理結果を格納した領域のアドレスの値を記録するだけでもよい。
【００７３】
描画機構４５は、処理結果を処理結果格納制御手段５０に転送すると、処理済描画位置保持手段４１に処理の終った描画位置を記録した後、描画位置を進める。描画位置が担当している分割描画領域の範囲内であれば、描画データ保持手段４３内のデータの整理から繰り返して同様の処理を行う。
【００７４】
描画処理手段の処理の過程において、例外的な動作をする場合は、処理担当範囲割り当て手段６０により描画領域内に担当すべき未処理領域がないことを告げられた場合である。このとき、描画処理手段４０は処理を終了して停止する。
【００７５】
次に、具体的な描画サンプルを用いて、本発明である描画処理装置の動作を説明する。図２０は、入力描画記述データ（ページ記述言語による表現であるが、特定のページ記述言語の文法にそったものではない）と、その入力描画記述データが表す描画サンプルの概念図を示している。以降の説明では、この入力記述データを入力した時に描画処理を例として説明を行う。描画サンプル１１は、３つの多角形（ここでは３角形）と１つの楕円からなる。そして入力描画記述データ１２は、楕円の記述データｏｖａｌと多角形の記述データｐｏｌｙｇｏｎとからなる。例えば、ｐｏｌｙｇｏｎ（［１４８，０，１２，２５６，１４８，２５６］，４）は、（Ｘ１，Ｙ１）＝（１４８，０）、（Ｘ２，Ｙ２）＝（１２，２５６），（Ｘ３，Ｙ３）＝（１４８，２５６）であり、ハッチパターンが４であることを示している。その他も同様なので説明は省略する。
【００７６】
図２１は、図２０に示した入力描画記述データから、描画データ生成手段２０により生成される描画データの概念図を示したものである。ここでの例では、描画記述中のそれぞれの描画オブジェクトは、台形（三角形を含む）による描画領域を表現する形式に分割され、描画データＤ１〜Ｄ８のフォーマットに変換され、描画データ格納制御手段３０に送信される。
【００７７】
図２２は、単位描画領域の例を示した概念図である。描画領域ｃをここでは走査線単位の単位描画領域Ｒ１〜Ｒ１８に分割する。描画データＤ１〜Ｄ８は、描画データ生成手段２０により生成されると、描画データ格納制御手段３０に転送される。描画データ格納制御手段３０に転送されると、描画データＤ１〜Ｄ８は、図９で説明した処理を受けて描画データ格納制御手段３０内に格納される。
【００７８】
図２３は描画データＤ１〜Ｄ８が描画データ格納制御手段３０内に格納された状態の一例を示している。図８で説明した描画データ登録手段３５はここでは、単位描画領域ごとにエントリを持つテーブルから構成されており、各描画データＤ１〜Ｄ８はそれぞれの最小のＹ座標値に対応するエントリの位置と関係づけられて格納されている。
【００７９】
図２４は描画データ格納制御手段３０が図１０に示した構成になっている場合に、描画データＤ１〜Ｄ８が描画データ格納制御手段３０に格納された状態の一例を示している。図１０で説明した描画データ登録手段３５はここでは、単位描画領域ごとにエントリを持つテーブルから構成されており、各描画データＤ１〜Ｄ８はそれぞれの最小のＹ座標値に対応するエントリの位置と関係づけられて格納されている。図１０で説明した描画データ存在範囲集計手段３３内には、進入テーブルと退出テーブルと描画データ個数カウンタテーブルがあり、進入テーブルには、各単位描画領域において、その位置にＹ座標値の最小値（上側の座標）を持つ描画データがいくつあるかを集計しており、退出テーブルには、各単位描画領域において、その位置にＹ座標値の最大値（下側の座標）を持つ描画データがいくつあるかを集計している。描画データ個数カウンタテーブルは、各単位描画領域に描画データがいくつあるかを示す数値を保持するテーブルである。このテーブルは、描画処理時に進出テーブルと退出テーブルを走査することによって埋めていくこともできるが、ここでは説明の簡単のため、描画処理手段４０が描画処理を開始する前に、一度進入テーブルと退出テーブルを走査して、描画データ個数カウンタテーブルが埋められるものとして説明を行う。
【００８０】
以下の説明では、描画処理を３つの描画処理手段４０ａ、４０ｂ、４０ｃで行うものとして説明する。描画データ格納制御手段３０に描画データが格納されると、描画処理手段に対して起動命令が発行される。描画処理手段４０ａ〜４０ｃはほば同時に起動するが、処理担当範囲割り当て手段６０へのアクセスが排他的に制御されているため、この段階で順序づけられる。
【００８１】
ここでは、最初の処理担当範囲割り当て手段６０へのアクセスが描画処理手段４０ａ、描画処理手段４０ｂ、描画処理手段４０ｃの順で許可されたものとする。
【００８２】
まず、一番目の構成の場合の実行例を説明する。一番目の構成例においては、分割描画領域の大きさを、単純に分割描画領域の位置座標あるいは、その分割描画領域の処理順番により決定する。ここでは、分割描画領域の大きさを位置座標をキーとして決定する場合について説明する。そして、説明の簡単のため、分割描画領域の決定を描画処理に先だって行なう場合について説明するが、分割描画領域の決定は必ずしも描画処理に先だって行なう必要はなく、描画処理と同期しながら行なうことも可能である。
【００８３】
図２５にここで説明する描画領域の分割についての概念図を示す。まず、図２５の上側に、描画領域を分割する基準として分割基準管理手段７０に準備される情報の例を示す。この例においては、単位描画領域のＲ１〜Ｒ１２までの位置においては分割描画領域の幅は４単位描画領域Ｒ１３〜Ｒ１８までの位置においては分割描画領域の幅は１としてある。この結果として、図２５に示した分割描画領域ＢＲ１〜ＢＲ８が決定される。（但し、分割描画領域の割り当てはＢＲ１、ＢＲ２、…、ＢＲ１８）の順に行なわれるものとする。）
【００８４】
描画処理手段４０ａが最初に処理担当範囲割り当て手段６０に対して処理の割り当て要求を行なうと、処理担当範囲割り当て手段６０は描画処理手段４０ａに対して前記の分割描画領域ＢＲ１を割り当てる。
【００８５】
描画処理手段４０ａは、処理を担当する分割描画領域の情報を受け取ると、描画データ格納制御手段３０から描画データを読み込み、順に処理する。ここで読み込まれて描画処理の対象となる描画データは単位描画領域Ｒ１から単位描画領域Ｒ４の間にＹ方向の最小値（上側の座標値）を持ち、単位描画領域Ｒ１よりも上側にＹ方向の最大値（下側の座標値）を持たないＤ１，Ｄ２，Ｄ３である。描画処理手段４０ａは、これらの描画データを処理して単位描画領域Ｒ１からＲ４に対応する処理結果データを作成して処理結果格納制御手段５０に登録する。
【００８６】
そして、描画処理手段４０ａは再度、処理担当範囲割り当て手段６０に処理を担当する分割描画領域の割り当て要求を行なって処理を続けることになる。
【００８７】
描画処理手段４０ｂから問い合わせがあると処理担当範囲割り当て手段６０は、図１４および図１６で説明した未処理位置保持手段６４に保持されている単位描画領域Ｒ５から始まる分割描画領域ＢＲ２が描画処理手段４０ｂに割り当てられる。
【００８８】
描画処理手段４０ｂは、処理を担当する分割描画領域の情報を受け取ると、描画データ格納制御手段３０から描画データを読み込み、順に処理する。描画処理手段４０ｂは図１８で説明した処理済描画位置保持手段４１が初期化されたままであるため、単位描画領域Ｒ５からではなく、単位描画領域Ｒ１から描画データを要求し、単位描画領域Ｒ８までの間にＹ方向の最小値（上側の座標値）を持ち、単位描画領域Ｒ５よりも上側にＹ方向の最大値（下側の座標値）を持たない描画データとして、Ｄ１，Ｄ３，Ｄ４，Ｄ７を読み込んで処理の対象とする。
【００８９】
描画処理手段４０ｂは、これらの描画データを処理して単位描画領域Ｒ５から単位描画領域Ｒ８に対応する処理結果データを作成して処理結果格納制御手段５０に登録する。そして、描画処理手段４０は再度、処理担当範囲割り当て手段６０に処理を担当する分割描画領域の割り当て要求を行なって処理を続けることになる。
【００９０】
描画処理手段４０ｃからの最初の要求において、処理担当範囲割り当て手段６０は、図１４および図１６で説明した未処理位置保持手段６４に保持されている単位描画領域Ｒ９から始まる分割描画領域ＢＲ３を描画処理手段４０ｃに割り当てる。
【００９１】
描画処理手段４０ｃは、処理を担当する分割描画領域ＢＲ３の情報を受け取ると、描画データ格納制御手段３０から描画データを読み込み、順に処理する。描画処理手段４０ｃは、図１８で説明した処理済描画位置保持手段４１が初期化されたままであるため、単位描画領域Ｒ９からではなく、単位描画領域Ｒ１から描画データを要求し、単位描画領域Ｒ１２までの間にＹ方向の最小値（上側の座標値）を持ち、単位描画領域Ｒ９よりも上側にＹ方向の最大値（下側の座標値）を持たない描画データとしてＤ１，Ｄ３，Ｄ４，Ｄ５，Ｄ７を読み込んで処理の対象とする。描画処理手段４０ｃは、これらの描画データを処理して単位描画領域Ｒ９〜Ｒ１２に対応する処理結果データを作成して処理結果格納制御手段５０に登録する。
【００９２】
以降の処理は、描画処理手段４０ａ〜４０ｃの処理の終了する順により、各描画処理手段に対して割り当てが変わる。ここでは説明の簡単のために、先に、この実行例でののタイムチャートの概略を図２６に示す。図２６に示すように、各分割描画領域ＢＲ１〜ＢＲ９の描画処理の処理時間は、各分割描画領域内の描画データの量やその他の要因により一様ではない。
【００９３】
次に割り当てられる分割描画領域ＢＲ４は、図２６に示したように、最初に処理の終る描画処理手段４０ａに割り当てられる。描画処理手段４０ａは分割描画領域ＢＲ１の処理を終了すると、処理済描画位置保持手段４１に分割描画領域ＢＲ１の最も未処理側に近い単位描画領域である単位描画領域Ｒ４の位置を格納したのち、処理担当範囲割り当て手段６０に分割描画領域の割り当てを要求する。
処理担当範囲割り当て手段６０は、この要求に対して分割描画領域ＢＲ４を割り当てる。ここでは、描画処理に先だって分割描画領域を決定していたが、描画処理と同期して要求に従って描画領域を決定していた場合には割り当てる分割描画領域の位置がＲ１３以降になるため、この段階において分割基準管理手段７０が処理担当範囲割り当て手段６０に対して回答する基準値は、分割描画領域の幅４から分割描画領域の幅１に変項されてから、その基準値に従って分割描画領域ＢＲ４が決定されることになる。
【００９４】
描画処理手段４０ａは分割描画領域ＢＲ４を割り当てられると、描画データ判定・破棄手段４４により、分割描画領域ＢＲ４の範囲の単位描画領域の内、もっともＹ座標の小さい方側の単位描画領域である単位描画領域Ｒ１３のＹ座標値よりも、Ｙ座標の最大値が小さい描画データが、描画データ保持手段４３内から選ばれ、破棄される。具体的には、描画処理手段４０ａは分割描画領域ＢＲ１の処理時に描画データＤ１，Ｄ２，Ｄ３を読み込んで、描画データ保持手段４３に保持しているが、これらの内描画データＤ２，Ｄ３は破棄され、描画データＤ１は描画データ保持手段４３に残される。次に、処理済描画位置保持手段４１に格納されている単位描画領域Ｒ４の位置以降で、割り当てられた分割描画領域ＢＲ４の最も未処理方向の単位描画領域Ｒ１３までにＹ座標の最小値を持ち、単位描画領域Ｒ１３の位置よりもＹ座標の最大値が大きい描画データを描画データ格納制御手段３０に要求する。この結果Ｄ５，Ｄ７，Ｄ８が新たに描画処理手段４０ａに読み込まれて、描画データ保持手段４３に格納され、分割描画領域ＢＲ４の描画処理が行なわれる。以降同様にして、分割描画領域ＢＲ５の処理を描画処理手段４０ｂが、分割描画領域ＢＲ６の処理を描画処理手段４０ｃが、分割描画領域ＢＲ７の処理を描画処理手段４０ａが、分割描画領域ＢＲ８の処理を描画処理手段４０ａが、分割描画領域ＢＲ９の処理を描画処理手段４０ｂが順に行なって割り当てる分割描画領域が無くなり、描画処理が終了する。
【００９５】
図２９は、処理の結果として処理結果格納制御手段５０に格納される処理結果データの概念図を示したものである。図３０に比較のための均等に描画領域を分割した例として分割描画領域ＢＵ１〜ＢＵ６を示す。そして、図３１にその場合の処理の進行についてのタイムチャートの概略を示す。図２０に示した描画記述は、描画領域のうちＹ座標の大きい方に描画オブジェクトがかたよっており、このため、Ｙ座標の小さい方から大きい方に向けて描画処理を行なった場合図３０のように均等な大きさの分割描画領域に分割して処理した場合には、図３１に示したタイムチャートのように負荷の配分のバランスがくずれて、ボトルネックが生じることにより全体の処理速度が遅くなる。これに対して、本発明によれば、処理の後半において負荷の分割の粒度が細かくなることにより、図２０に示した描画記述のような場合にも、バランスよく負荷が配分されて、効率的に並列処理が行なわれる。
【００９６】
次に、図１０に示したように描画データ格納制御手段３０に描画データが格納された状態から、第二の構成例による実施例を説明する。
【００９７】
第二の構成例においては、分割描画領域の大きさを、入力データの分布などの入力データに依存した情報、あるいは、処理の進度を示す情報あるいは、それらの両方により決定する。ここでは、例として入力データに依存した情報として、単位描画領域あたりの描画データの個数により分割描画領域の大きさを決定する場合について説明する。描画データの分割描画領域あたりの個数は、描画処理を開始する前に決定可能であるため、描画処理に先だって分割描画領域を決定することも可能であるが、ここでは、処理の進行とともに順に描画領域を決定していく例について説明を行なう。
【００９８】
まず、説明の簡単のために、図２７にここでの実施例で決定される描画領域の分割についての概念図を前もって示す。ここに示す例においては単位描画領域Ｒ１〜Ｒ１３までは、単位描画領域あたりの描画データの個数が１０を越えたところで分割描画領域を区切り、単位描画領域Ｒ１４〜Ｒ１８では単位描画領域あたりの描画データの個数の累算値が４を越えたところで分割描画領域を区切るという基準が分割基準管理手段７０に格納されているものとし、この結果として、処理が進むにつれて図２７の下側に示した分割描画領域ＢＳ１〜ＢＳ６が決定される。また、同様に説明の簡単のために、まえもって第二の構成による処理の実行例のタイムチャートの概略を図２８に示す。処理は、分割描画領域ＢＳ１を描画処理手段４０ａが処理し、分割描画領域ＢＳ２を描画処理手段４０ｂが処理し、分割描画領域ＢＳ３を描画処理手段４０ｃが処理し、分割描画領域ＢＳ４を描画処理手段４０ａが処理し、分割描画領域ＢＳ５を描画処理手段４０ｂが処理し、分割描画領域ＢＳ６を描画処理手段４０ｃが処理する順で行なわれる。
【００９９】
描画処理の開始時は第一の構成の実行例の説明と同様に、描画処理手段４０ａ、描画処理手段４０ｂ、描画処理手段４０ｃの順に分割描画領域の割り当て要求が処理担当範囲割り当て手段６０に受け付けられるものとして説明を行なう。
【０１００】
描画処理手段４０ａの割り当て要求を処理担当範囲割り当て手段６０が受け取ると、処理担当範囲割り当て手段６０は、未処理位置保持手段６４に保持されている単位描画領域Ｒ１の位置から順に分割描画領域の範囲を広げて行く。ここで、説明の簡単のため、各単位描画領域ごとの描画データの個数は、描画処理に先だって描画データ格納制御手段３０内で上記の方法で進入テーブルと退出テーブルを一度走査して各単位描画領域ごとに生成されているものとして説明を行なうが、この各単位描画領域ごとの情報等も、描画処理と同期して生成されてもよい。また、以降の説明の簡単のため、単位描画領域ごとの描画データの個数を単に「データ個数」と呼び、分割描画領域内での「データ個数」の累算値を「データ個数累算値」と呼ぶ。処理担当範囲割り当て手段６０はまず、描画データ格納制御手段３０に対して単位描画領域Ｒ１の「データ個数」を要求し、値２を得る。そして、分割基準管理手段７０に単位描画領域Ｒ１での分割基準の値を問い合わせると、基準値１０を得る。そして、単位描画領域Ｒ２，Ｒ３，Ｒ４，Ｒ５の順にこの描画データ格納制御手段３０と分割基準管理手段７０への問い合わせを繰り返しながら分割描画領域の大きさを広げて行く。単位描画領域Ｒ５のところで、ちょうど「データ個数累算値」が分割の基準値１０になるため、ここで分割描画領域ＢＳ１を決定し、描画処理手段４０ａに通知し、未処理位置保持手段６４に単位描画領域Ｒ６の位置を格納する。描画処理手段４０ａは分割描画領域ＢＳ１を割り当てられると上記の第一の構成における描画処理手段の動作の説明と同様の処理を行なう。ここで描画処理手段４０ａにより描画データ格納制御手段３０から読み込まれる描画データはＤ１，Ｄ２，Ｄ３，Ｄ７となる。
【０１０１】
次に、処理担当範囲割り当て手段６０は描画処理手段４０ｂからの要求を受け付ける。未処理位置保持手段６４に格納されている単位描画領域Ｒ６の位置から順に描画データ格納制御手段３０に「データ個数」を問い合わせ、分割基準管理手段７０に分割の基準値を問い合わせることを繰り返して分割描画領域ＢＳ２を決定する。ここでも分割の基準値が１０のままで、単位描画領域Ｒ６，Ｒ７，Ｒ８，Ｒ９まで広げたところで「データ個数累算値」が１１となり、分割描画領域ＢＳ２はＲ６〜Ｒ９の領域に決定される。分割描画領域ＢＳ２は描画処理手段４０ｂに通知され、未処理位置保持手段６４には単位描画領域Ｒ１０の位置が格納される。
【０１０２】
描画処理手段４０ｂが分割描画領域ＢＳ２を割り当てられた時の処理は第一の構成の実行例で説明したものと同様なので説明を省略するが、ここで描画処理手段４０ｂに読み込まれる描画データは、Ｄ１，Ｄ３，Ｄ４，Ｄ７である。
【０１０３】
次に、処理担当範囲割り当て手段６０は描画処理手段４０ｃからの要求を受け付ける。未処理位置保持手段６４に格納されている単位描画領域Ｒ１０の位置から順に描画データ格納制御手段３０に「データ個数」を問い合わせ、分割基準管理手段７０に分割の基準値を問い合わせることを繰り返して分割描画領域ＢＳ３を決定する。ここでも分割の基準値が１０のままで、単位描画領域Ｒ１０，Ｒ１１，Ｒ１２，Ｒ１３まで広げたところで「データ個数累算値」が１２となり、分割描画領域ＢＳ３はＲ１０〜Ｒ１３の領域に決定され、描画処理手段４０ｃに通知され、未処理位置保持手段６４には単位描画領域Ｒ１４の位置が格納される。
【０１０４】
描画処理手段４０ｃが分割描画領域ＢＳ３を割り当てられた時の処理は第一の構成の実行例で説明したものと同様なので説明を省略するが、ここで描画処理手段４０ｃに読み込まれる描画データは、Ｄ１，Ｄ５，Ｄ７，Ｄ８である。
【０１０５】
次に、処理担当範囲割り当て手段６０は分割描画領域ＢＳ１の処理が終了した描画処理手段４０ａからの要求を受け付ける。未処理位置保持手段６４に格納されている単位描画領域Ｒ１４の位置から順に描画データ格納制御手段３０に「データ個数」を問い合わせ、分割基準管理手段７０に分割の基準値を問い合わせることを繰り返して分割描画領域ＢＳ４を決定する。ここでは、単位描画領域Ｒ１４の「データ個数」は４であり、分割基準管理手段７０に問い合わせた単位描画領域Ｒ１４の位置での分割の基準値は４である。このため、分割描画領域ＢＳ４は単位描画領域Ｒ１４だけの領域で決定され、描画処理手段４０ａに通知され、未処理位置保持手段６４には単位描画領域Ｒ１５の位置が格納される。
【０１０６】
描画処理手段４０ａが最初の処理が終って再度分割描画領域ＢＳ４を割り当てられた時の処理は第一の構成の実行例で説明したものと同様なので説明を省略するが、ここで、描画処理手段４０ａの描画データ保持手段４３からは描画データＤ２，Ｄ３が削除されＤ１が残され、新たにＤ６，Ｄ７，Ｄ８が読み込まれる。
【０１０７】
次に、処理担当範囲割り当て手段６０は分割描画領域ＢＳ２の処理が終了した描画処理手段４０ｂからの要求を受け付ける。未処理位置保持手段６４に格納されている単位描画領域Ｒ１５の位置から順に描画データ格納制御手段３０に「データ個数」を問い合わせ、分割基準管理手段７０に分割の基準値を問い合わせることを繰り返して分割描画領域ＢＳ５を決定する。ここでは、単位描画領域Ｒ１５の「データ個数」は４であり、分割基準管理手段７０に問い合わせた単位描画領域Ｒ１５の位置での分割の基準値は４である。このため、分割描画領域ＢＳ５は単位描画領域Ｒ１５だけの領域で決定され、描画処理手段４０ｂに通知され、未処理位置保持手段６４には単位描画領域Ｒ１６の位置が格納される。
【０１０８】
描画処理手段４０ｂが最初の処理が終って再度分割描画領域ＢＳ５を割り当てられた時の処理は上記と同様なので説明を省略するが、ここで、描画処理手段４０ｂの描画データ保持手段４３からは描画データＤ３，Ｄ４が削除されＤ１が残され、新たにＤ６，Ｄ７，Ｄ８が読み込まれる。
【０１０９】
次に、処理担当範囲割り当て手段６０は分割描画領域ＢＳ３の処理が終了した描画処理手段４０ｃからの要求を受け付ける。未処理位置保持手段６４に格納されている単位描画領域Ｒ１６の位置から順に描画データ格納制御手段３０に「データ個数」を問い合わせ、分割基準管理手段７０に分割の基準値を問い合わせることを繰り返して分割描画領域ＢＳ６を決定する。ここでは、単位描画領域Ｒ１６の「データ個数」は２であり、分割基準管理手段７０に問い合わせた単位描画領域Ｒ１６の位置での分割の基準値は４である。そして、順に単位描画領域Ｒ１７，Ｒ１８に分割描画領域が広げられＲ１８以降には単位描画領域が無いため、分割描画領域ＢＳ６は単位描画領域Ｒ１６，Ｒ１７，Ｒ１８の領域で決定され、描画処理手段４０ｃに通知され、未処理位置保持手段６４には未処理の領域が無いことを示す情報が格納される。
【０１１０】
描画処理手段４０ｃが最初の処理が終って再度分割描画領域ＢＳ６を割り当てられた時の処理は上記と同様なので説明を省略するが、ここで、描画処理手段４０ｃの描画データ保持手段４３からは描画データＤ５，Ｄ７，Ｄ８が削除されＤ１が残され、新たにＤ６が読み込まれる。
【０１１１】
以上、説明したように、本発明の描画処理装置は、描画処理の負荷を描画処理装置の数以上に分割し、さらに、処理の後半で割り当てられる描画処理の負荷が、処理の前半で割り当てられる描画処理の負荷よりも小さくなるように分割して並列描画処理を行なう構成とした。これにより、描画対象となるページイメージに部分的な負荷の偏りがあった場合、特に、処理の終盤に負荷の重い領域があった場合にも、描画処理の高速化を可能とし、また、処理の前半においては負荷の分割の粒度が大きくできるために処理の割り当ての切替えの回数を少なくすることができ資源へのアクセス競合によるオーバヘッドも削減することが可能になる。
【０１１２】
また、実行時に他のプロセスによる影響などにより、特定の部分処理を担当している処理手段の処理が一時的に遅れた場合にも、描画処理の高速化を可能とする。
【０１１３】
なお、処理担当範囲割り当て手段６０は、分割描画領域の大きさを描画処理手段４０ａ〜４０ｎからの問い合わせの時点で決定しても、問い合わせ時点より前、例えば極端な場合には、描画処理を開始する前にまとめて全ての分割描画領域の大きさを分割基準管理手段７０を参照して決定しておいてから、描画処理を開始してもよい。
【０１１４】
上記の例においては読み込み時に描画データのＹ座標の最大値と最小値を検査して各描画処理手段に読み込む例について説明したが、各描画データが各分割描画領域に入っているかどうかの検査の一部を省略して読み込み、各描画処理手段で行なうことも可能である。
【０１１５】
【発明の効果】
以上説明したように、本発明の描画処理装置の構成によれば、描画データの複数の分割基準値を持つことにより、描画処理装置中の複数の処理手段の各々が担当する処理範囲を動的に変更し、全体の処理時間の短縮を効果的に達成することができる。
【０１１６】
特に、処理の終盤において描画処理の分割の粒度を小さくなるように分割描画領域の大きさを決定し、各描画処理手段に割り当てる描画データをより少なくなるように構成したので、処理の終盤に割り当てられる描画領域に描画オブジェクトが偏って存在する場合においても、処理が特定の処理手段に偏ることを防止でき、高速な描画処理を行なうことが可能になる。
【図面の簡単な説明】
【図１】 本発明の描画処理装置の一実施例の構成を示す図である。
【図２】 本発明の描画処理装置の他の実施例の構成を示す図である。
【図３】 本発明の描画処理装置が適用されるシステムの例を示すブロック図である。
【図４】 本発明の描画処理装置を有するシステム全体の動作の例を示すフローチャートである。
【図５】 本発明の描画処理装置を有するシステム全体の１ページ分の動作の例を示すフローチャートである。
【図６】 本発明の描画処理装置の描画データ生成手段処理の流れを示すフローチャートである。
【図７】 描画データ生成手段で生成される描画データのデータ構造の一例を示す図である。
【図８】 本発明の描画処理装置の描画データ格納制御手段の一実施例の構成を示す図である。
【図９】 図８に示す描画データ格納制御手段の処理の流れを示すフローチャートである。
【図１０】 本発明の描画処理装置の描画データ格納制御手段の一実施例の構成を示す図である。
【図１１】 図１０に示す描画データ格納制御手段における処理の流れを示すフローチャートである。
【図１２】 描画データ格納制御手段から描画処理手段に描画データを送出する際の処理の流れを示すフローチャートである。
【図１３】 本発明の描画処理装置の処理担当範囲割り当て手段に対する描画データ格納制御手段の処理の流れを示すフローチャートである。
【図１４】 処理担当範囲割り当て手段の構成を示す図である。
【図１５】 処理担当範囲割り当て手段の処理の流れを示したフローチャートである。
【図１６】 処理担当範囲割り当て手段の構成を示す図である。
【図１７】 処理担当範囲割り当て手段の構成における処理の流れを示したフローチャートである。
【図１８】 本発明の描画処理装置の描画処理手段の処理の構成を示した図である。
【図１９】 描画処理手段の処理の流れを示した図である。
【図２０】 描画記述の例を示す図である。
【図２１】 描画データの例を示す図である。
【図２２】 本発明の描画処理装置における描画データの単位描画領域の例を示す図である。
【図２３】 本発明の描画処理装置における描画データの格納状態の一実施例を示す図である。
【図２４】 本発明の描画処理装置における描画データの格納状態の一実施例を示す図である。
【図２５】 本発明の描画処理装置における分割描画領域の一実施例を示す図である。
【図２６】 本発明の描画処理装置における一実施例のタイムチャートを示す図である。
【図２７】 本発明の描画処理装置における分割描画領域の一実施例を示す図である。
【図２８】 本発明の描画処理装置における一実施例のタイムチャートを示す図である。
【図２９】 描画処理の結果の概念図を示す図である。
【図３０】 描画領域を均等に分割した場合の分割描画領域を示す図である。
【図３１】 描画領域を均等に分割した場合の実行例のタイムチャートを示す図である。
【符号の説明】
１０ ページ記述言語
２０ 描画データ生成手段
３０ 描画データ格納制御手段
４０ 描画処理手段
５０ 処理結果格納制御手段
６０ 処理担当範囲割り当て手段
７０ 分割基準管理手段
２００ 出力装置
３００ ネットワークインタフェース
４００ ネットワーク
１００ 描画処理装置
２１ 描画データ
２２ データ構造
６１ 分割描画領域
３１ 描画データ格納用インタフェース
３２ 描画データ存在範囲抽出手段
３３ 描画データ存在範囲集計手段
３４ 描画データ存在数通知用インタフェース
３５ 描画データ登録手段
３６ 描画データ送出用インタフェース
６１ 排他的インタフェース
６２ 分割描画領域決定手段
６３ 描画範囲判定手段
６４ 未処理位置保持手段
６５ 描画データ数集計手段
６６ 描画データ数問い合わせ用インタフェース
６７ 基準値問い合わせ用インタフェース
４１ 処理済描画位置保持手段
４２ 担当描画範囲保持手段
４３ 描画データ保持手段
４４ 描画データ判定・破棄手段
４５ 描画機構
４６ 描画処理バッファ
１１ 描画サンプル
１２ 入力描画記述データ[0001]
BACKGROUND OF THE INVENTION
The present invention relates to a drawing processing apparatus, and more particularly to a drawing processing apparatus that performs drawing processing using a page description language as an input.
[0002]
[Prior art]
Currently, a page printer performs printing by inputting PDL (page description language) such as Interpress (registered trademark of Xerox Corporation in the United States) and PostsScript (trademark of Adobe Systems Corporation in the United States).
[0003]
When printing is performed using such PDL as input, it is necessary to perform an imaging process for converting the data in the PDL format into data in a format suitable for the raster output device. However, in general, the time required for imaging processing is very long, and this is a problem particularly in a system that outputs to a high-speed page printer.
[0004]
For example, although some color high-speed page printers have an output capacity of 40 sheets per minute or more, the time required for the imaging process takes 10 seconds to several minutes. I couldn't use it enough. Therefore, in order to perform imaging processing at high speed, it is necessary to perform parallel drawing processing.
[0005]
In the conventional parallel drawing processing method, PDL data to be printed is divided into pages and parallel processing is performed in units of pages, or drawing objects described in the PDL are divided into predetermined divided areas. Some of them perform parallel drawing, etc., but these do not achieve the expected performance due to the fact that the drawing processing load between the pages that are the units for parallel processing and between the divided areas is not uniform. It was.
[0006]
On the other hand, in the drawing processing apparatus proposed in Japanese Patent Application No. 08-212258, the processing load of each parallel drawing processing unit is made uniform and the parallel drawing regardless of the drawing load unevenness in the page. Even when processing of some processing devices of the processing unit is delayed due to some disturbance, it is possible to remedy.
[0007]
[Problems to be solved by the invention]
However, even in the drawing processing apparatus disclosed in Japanese Patent Application No. 08-212258, when the load is more biased than expected in the divided drawing area assigned at the end of the drawing areas assigned in order at the time of execution. However, there is a problem that the processing of the divided drawing area becomes a bottleneck and the effect of parallel processing may not be sufficiently improved.
[0008]
The present invention has been made in view of the above points, and in a parallel drawing processing apparatus in which divided drawing areas in charge of a plurality of drawing processing units are dynamically determined at the time of execution of a process, the drawing area of a drawing object It is an object of the present invention to provide a drawing processing apparatus that performs stable and faster parallel drawing processing regardless of the above distribution.
[0009]
[Means for Solving the Problems]
In the present invention, in order to solve the above-described problem, in a drawing processing apparatus that performs drawing processing using a page description language as an input, drawing data generating means for receiving drawing commands and generating drawing data constituting internal data of a drawing figure; Drawing data storage control means for controlling the output to the drawing data storage and drawing processing means, a plurality of drawing processing means for inputting drawing data from the drawing data storage control means and executing drawing processing, the plurality A division reference management means for holding a reference value as a reference for dividing the drawing area for determining a processing unit in the drawing processing means, and a drawing processing means for dividing the drawing area based on the reference value of the division reference management means. In response to each request, a processing range assignment unit that allocates the divided drawing area to each drawing processing unit, and a plurality of drawing processing units A processing result storage unit that stores a plurality of processing results that are input, and an output unit that outputs the processing results stored in the processing result storage unit. The division criterion management unit has a plurality of different reference values. ,pluralProcess of drawing processing meansoverallOne reference value selected from the plurality of reference values selected according to the degree of progress is output to the processing charge range assignment means, and the processing charge range assignment means divides the drawing area based on the selected reference value. The divided drawing area is assigned to each of a plurality of drawing processing means.
[0010]
The division reference management means in the drawing processing apparatus of the present invention receives the position coordinate value in the sub-scanning direction of the divided drawing area assigned to the drawing processing means as data indicating the progress of the drawing data processing in the drawing processing means. In addition, one reference value is selected from a plurality of reference values based on the reception position coordinate value.
[0011]
Further, the division criterion management means in the drawing processing apparatus of the present invention provides the area of the drawing area assigned to the drawing processing means as the data indicating the progress of the drawing data processing in the drawing processing means and the total area required for processing, for example, page It is characterized by having a configuration for receiving a value indicating a ratio with the per unit area and selecting one reference value from a plurality of reference values based on the received value.
[0012]
Further, each of the divided drawing areas allocated to the plurality of drawing processing means based on each of the plurality of reference values possessed by the division reference managing means in the drawing processing apparatus of the present invention is a minimum division unit in the sub-scanning direction of the drawing area. It is an integral multiple of a certain unit drawing area (Rn).
[0013]
The division reference management means in the drawing processing apparatus of the present invention selects the reference value so as to reduce the size of the drawing area assigned to the drawing processing means as the drawing data processing in the drawing processing means proceeds. And
[0014]
Further, the division reference management means in the drawing processing apparatus of the present invention selects the reference value so as to reduce the number of unit drawing areas of the divided drawing areas assigned to the drawing processing means as the drawing data processing in the drawing processing means proceeds. It is characterized by that.
[0015]
Further, the division criterion management means in the drawing processing apparatus of the present invention reduces the total number of drawing data included in each of one or more unit drawing areas allocated to the drawing processing means as the drawing data processing in the drawing processing means progresses. And selecting a reference value.
[0016]
Further, the processing range assignment means in the drawing processing apparatus of the present invention is characterized in that the drawing area is assigned in response to processing assignment requests from a plurality of drawing processing means.
[0017]
In addition, the processing charge range allocating unit in the drawing processing apparatus of the present invention relates to the drawing processing by assigning the size of the divided drawing area to be assigned to the plurality of drawing processing apparatuses based on the plurality of reference values of the dividing reference managing unit. It has the structure which determines collectively about data.
[0018]
Further, the processing charge range allocating means in the drawing processing apparatus of the present invention receives the information related to the drawing data from the drawing data storage control means when allocating the processing to the plurality of processing means, and based on the information It is characterized in that the allocation of the drawing area is executed.
[0019]
Further, the processing charge range allocating means in the drawing processing apparatus of the present invention has an exclusive interface for exclusively executing drawing area requests from a plurality of drawing processing apparatuses.
Further, according to a second aspect of the present invention, in a drawing processing method for interpreting a drawing command and executing a drawing process, a drawing data generation step for receiving a drawing command and generating drawing data constituting internal data of a drawing figure; A drawing data storage control step for storing the drawing data and controlling output to the drawing processing means; and a plurality of drawing processing means for inputting drawing data output based on the control of the drawing data storage control step. The overall progress of the processing in the plurality of drawing processing means from a drawing processing step for executing drawing processing and a plurality of different reference values serving as division criteria of the drawing area for determining processing units in the plurality of drawing processing means. A division criterion management step for selecting one criterion value according to the degree and outputting the selected criterion value to the processing range assignment means , Dividing the drawing area based on the reference value selected in the division reference management step, and executing a process of assigning the divided drawing area to each drawing processing means in response to a request from each drawing processing means. A processing range assignment step, a processing result storage step for storing a plurality of processing results output from the plurality of drawing processing means in a processing result storage means, and output of the processing results stored in the processing result storage means And an output step.
[0020]
DETAILED DESCRIPTION OF THE INVENTION
Embodiments of the present invention will be described below with reference to the drawings. FIG. 1 is a principle diagram of a drawing processing apparatus of the present invention. The drawing data generation means 20 interprets and expands a drawing description that is a
[0021]
The division
[0022]
The processing charge
[0023]
The drawing processing units 40 a to 40 n communicate with the processing assigned
[0024]
Then, the processing result storage control means 50 temporarily stores the results processed by the drawing processing means 40 a to 40 n and transmits the results to the
[0025]
Each of these means operates under the control of control means (not shown) such as initialization, processing start, end, and synchronization.
[0026]
Here, the division reference management means 70 may manage the reference value for the progress of processing in a table or table format, or may hold it in the form of a function for the progress of processing. Here, it is only necessary to realize that the reference value can be changed in the direction of decreasing the size of the divided drawing area continuously or step by step as the processing progresses.
[0027]
FIG. 2 is a block diagram showing another embodiment of the image processing apparatus of the present invention. In FIG. 2, the drawing data storage control means 30 and the processing charge range assignment means 60 are connected by a communication path. Through this communication path, the drawing data
[0028]
FIG. 3 is a conceptual diagram of an example of a system to which the present invention is applied. In this system, the
[0029]
As an operation of the system, drawing output data is sent from a client computer (not shown) via a network using various media such as an Ethernet cable, a telephone line, and radio. The drawing output data is received and processed by the
[0030]
FIG. 4 is a flowchart showing the overall flow of the drawing processing apparatus. When the drawing processing apparatus is activated, initialization at the time of activation is first performed (step S401). At this time, initialization of the control means (not shown) and initialization of the memory management mechanism (not shown) are performed, and the division criterion management means 70 and the like may be initialized at this stage. When the initialization at the start-up is completed, the
[0031]
Hereinafter, for the sake of simplicity, the description will be made on the drawing process for one page. FIG. 5 is a diagram showing an outline of the processing flow for one page.
[0032]
When the drawing process is started, initialization is performed in each means (step S501). At this time, the drawing data storage control means 30 initializes the storage area, the processing result storage control means 50 initializes the storage area for storing the processing results, and the drawing processing means 40a to 40n The work area used at the time of the drawing process is initialized, and further, the processing area assignment means 60 executes initialization of processing unit settings, processed positions, and the like. At this time, if a setting for performing special processing for each page is specified through, for example, the input
[0033]
When the initialization is completed, the drawing data generation means 20 is instructed to read the drawing description and generate one page of drawing data. When drawing data for one page is generated (step S502) and stored in the drawing data storage control means 30, the control means not shown in FIGS. 1 and 2 includes a plurality of drawing processing means 40a to 40n. Is notified of the start of processing. Thereafter, processing by the drawing processing means is executed (step S503). The control means knows through the notification from the drawing processing means 40a to 40n that the processing of the plurality of drawing processing means 40a to 40n has been completed. Alternatively, the processing charge
Alternatively, the end of the processing can be known by a notification from the processing result storage control means 50 that the result of the entire drawing area has been stored. Upon completion of this process, the data in the process result storage control means 50 is output as a result of the drawing process to the output device 200 (step, S504). In the end process (step S505), the used memory is released.
[0034]
Next, each means of the drawing processing apparatus will be described in detail. FIG. 6 is a flowchart showing the processing flow of the drawing data generation means 20. When the drawing data generation means 20 is instructed to start processing, it reads the drawing description data which is a page description language, and reads and interprets the drawing description data while the drawing description data constituting one page remains. The drawing data is generated (steps S601 and S602), and the generated drawing data is transmitted to the drawing data storage control means 30 (step S603) repeatedly.
[0035]
FIG. 7 shows an example of the data structure of the drawing data generated by the drawing data generation means 20 used in the following description. FIG. 7 shows drawing data 21 (FIG. 7, the lower diagram) and its data structure 22 (FIG. 7, the upper table) that represent the drawing area by a trapezoidal expression having two sides parallel to the scanning line direction. Then, the Y coordinate is taken in the sub-scanning line direction and the X coordinate is taken in the scanning line direction, and the position on the drawing area is expressed in the XY coordinate system. This method of coordinate system is also used in the following explanation.
[0036]
In addition to the values (YMIN, YMAX, X1, X2, DX1, DX2) relating to the drawing area, the
[0037]
In the present embodiment, for the sake of simplicity of description, drawing data that represents a filled area by a trapezoidal expression is used as drawing data. However, the drawing data has a trapezoid having two sides parallel to the main scanning line direction. It need not be an expression. For example, polygon representation by point sequence or vector representation, line segment representation with or without curves, vector representation consisting only of straight line segments, representation by line segment sequence pairs that face each other, and the drawing area is triangular What is an expression format that can specify the coordinate value and size on the coordinate system of the drawing area, such as a solid area, a rectangle, a trapezoid, etc. Even if it uses, it is the range of the drawing data which this invention assumes.
[0038]
Next, the drawing data storage control means 30 will be described. FIG. 8 is a conceptual diagram showing an example of the configuration of the drawing data storage control means 30.
[0039]
The drawing
[0040]
FIG. 9 is a diagram showing a flow of processing in the stage of storing the drawing data having the configuration shown in FIG. The drawing data storage control means 30 registers drawing data in the drawing data registration means 35 while drawing data for one page is sent (step S901). These operations are performed until input of all the drawing data generated by the drawing data generation means 20 is completed (step S902).
[0041]
FIG. 10 is a diagram showing another configuration example of the drawing data storage control means 30. In FIG. The drawing data storage control means 30 is configured when the
[0042]
The drawing
[0043]
The drawing data existence range counting means 33 adds up the detected existence ranges in the Y direction. For example, the number of drawing data existing in each unit drawing area can be counted by sequentially processing in the Y direction. For example, when each unit drawing area is processed in order from the smaller Y coordinate value side to the larger side, the previous one is calculated from the number of drawing data existing before the processing of the unit drawing area being processed. The number of drawing data having the maximum Y coordinate value is subtracted from the unit drawing area to be processed in
[0044]
FIG. 11 is a diagram showing a flow of processing in the stage of storing the drawing data having the configuration shown in FIG. While the drawing data for one page is being sent, the drawing data storage control means 30 applies the Y of the drawing data to the drawing data received by the drawing data existence range extraction means 32 for the drawing data received. The direction existence range is detected (step S111), and both ends thereof are registered in the drawing data existence range totaling unit 33 (step S112). For example, the drawing data existence range extracting unit 32 extracts the maximum value and the minimum value of the coordinate values in the Y direction of the drawing data. Then, a set of counters for counting the number corresponding to the maximum value and the number corresponding to the minimum value increments the corresponding counter in the drawing data existence range counting means 33 prepared for each unit Y coordinate. (Hereafter, when referring to the counter table as exemplified here, the counter on the minimum value side is referred to as an entry counter, and the counter on the maximum value side is referred to as an exit counter.)
[0045]
Next, the drawing data is registered in the drawing data registration means 35 (step S113). For example, it can be realized by preparing a drawing data table corresponding to a unit area in the Y direction of the drawing area and registering the drawing data in a place corresponding to, for example, the minimum value of the coordinate values in the Y direction. These operations are performed for all drawing data generated by the drawing data generation means 20 (step S114).
[0046]
In the embodiment described here, a data structure in a table format is used for the drawing data existence range totaling means 33, the drawing data registration means 35, etc. in the drawing data storage control means 30, but this is a simple explanation. Therefore, other data structures may be used. Similar functions can be obtained by using various other data structures such as a list structure, a tree structure, and a hash mechanism.
[0047]
The drawing data storage control means 30 receives the request from the drawing processing means 40a to 40n in the stage where the drawing processing is being performed, other than the time of storing the drawing data, and extracts the drawing data requested for the data. Send it out. At this time, the coordinate values in the Y direction or the range of coordinate values in the Y direction are designated from the drawing processing means 40a to 40n. The drawing data storage control means 30 draws the drawing data corresponding to the designated coordinate value or range one by one or several at a time, or all the drawing data corresponding to the designated classification. It transmits to the processing means 40. Of the processes for transmitting the drawing data described above, the outline of returning the drawing data registered in the requested range in a simple explanation will be described with reference to FIG.
[0048]
The drawing data storage control means 30 repeats transferring drawing data in response to individual requests from the plurality of drawing processing means 40a to 40n until the processing for one page is completed. Specifically, when communication is received (step, S121), if the communication is not a notification of completion of processing of one page but a drawing data request command (step, S122), data can be transferred to the request source. Information, i.e., an ID or address that uniquely indicates the request source, an address in the local storage device in the
[0049]
When drawing data is transferred from the drawing data storage control means 30 when transferring the drawing data or collecting the drawing data, the drawing data itself is destroyed so as not to remain in the drawing data storage control means 30. Alternatively, the drawing data stored in the drawing data storage control means 30 may be collected and stored as a reference data or a copy of the drawing data while being saved. In addition, when the drawing data storage control means 30 is configured on a shared memory between the drawing processing means 40a to 40n, the drawing data storage control means 30 does not perform an active function. In any case, the drawing processing means 40a to 40n may simply provide a data structure that can access the drawing data registered in a necessary range. At this time, each drawing processing means 40a to 40n can read drawing data without permission.
[0050]
When the drawing data
[0051]
The processing charge
[0052]
In the following description, the unit drawing area is the minimum division unit in the Y direction, and the divided drawing area is an area that is assigned to each drawing processing means 40 with its size and position determined by the processing range assignment means 60. For example, the unit drawing area is an elongated area in the X direction for one to several scanning lines, and the divided drawing area is an area having a size of several to several tens of unit drawing areas.
[0053]
When the processing charge
[0054]
FIG. 13 is a diagram showing the flow of processing for each communication between the processing charge
[0055]
Next, the processing charge range assignment means 60 will be described. FIG. 14 is a diagram showing the configuration of the processing charge range assignment means 60. The
[0056]
FIG. 15 is a flowchart showing the processing flow of the processing charge range assignment means 60. (However, this flowchart shows only the flow of processing in the case where the determination of the divided drawing area is performed in synchronization with the progress of the drawing process.) The processing range assignment means 60 can draw the drawing range if necessary at the start of the entire process. In addition to the initialization of the
[0057]
Requests from the drawing processing means 40a to 40n are restricted in access by the
[0058]
If it is confirmed in
[0059]
FIG. 16 shows an example in which the processing charge
[0060]
The
[0061]
FIG. 17 is a flowchart showing the flow of processing when the processing charge
[0062]
Requests from the drawing processing units 40a to 40n are restricted in access by the
[0063]
If it is determined in step S1707 that the accumulated value exceeds the reference value, it is next determined whether or not there is actually a divided drawing area to be allocated (step S1708). If there is no drawing area, the fact that there is no drawing area to be distributed is sent to the requesting drawing processing means (step S1711). If there is, the requesting drawing processing means sends information on the divided drawing area, for example, divided drawing. Information such as the boundary coordinate value of the area is transmitted (step, S1709), and the position held in the unprocessed position holding means 64 is updated to the next unprocessed drawing position (step, S1710). At this time, the accumulated value may be initialized, or may be calculated and updated with the reference value.
[0064]
Next, the drawing processing means 40a to 40n will be described. Since the internal configuration of the drawing processing unit is the same, the
[0065]
FIG. 18 is a diagram showing the configuration of the drawing processing means 40. The processed drawing position holding means 41 holds the processed drawing position. The assigned drawing
[0066]
The drawing
[0067]
The drawing data determining / discarding
[0068]
The
Further, after collecting the data to some extent, it may be stored in the processing result storage control means 50. In particular, when the processing result
[0069]
FIG. 19 is a flowchart showing the processing flow of the drawing processing means 40. The
[0070]
First, the drawing data determination / discard
[0071]
Further, processing (step S1907) is performed from the drawing data held in the drawing
[0072]
When the processing of the drawing position ends (step S1908), the drawing processing means 40 transfers the processing result in the
[0073]
When the
[0074]
In the course of processing of the drawing processing means, an exceptional operation is when the processing charge range assignment means 60 tells that there is no unprocessed area to be handled in the drawing area. At this time, the drawing processing means 40 ends the processing and stops.
[0075]
Next, the operation of the drawing processing apparatus according to the present invention will be described using specific drawing samples. FIG. 20 shows a conceptual diagram of input drawing description data (which is expressed in a page description language but not in accordance with the grammar of a specific page description language) and a drawing sample represented by the input drawing description data. . In the following description, drawing processing will be described as an example when the input description data is input. The
[0076]
FIG. 21 shows a conceptual diagram of drawing data generated by the drawing data generating means 20 from the input drawing description data shown in FIG. In this example, each drawing object in the drawing description is divided into a format representing a trapezoid (including a triangle) drawing area, converted into the drawing data D1-D8 format, and the drawing data storage control means 30. Sent to.
[0077]
FIG. 22 is a conceptual diagram showing an example of the unit drawing area. Here, the drawing area c is divided into unit drawing areas R1 to R18 in units of scanning lines. When the drawing data D1 to D8 are generated by the drawing data generation means 20, they are transferred to the drawing data storage control means 30. When transferred to the drawing data
[0078]
FIG. 23 shows an example of a state in which the drawing data D1 to D8 are stored in the drawing data storage control means 30. The drawing data registration means 35 described with reference to FIG. 8 is composed of a table having an entry for each unit drawing area. Each drawing data D1 to D8 includes the position of the entry corresponding to the minimum Y coordinate value. Stored in association.
[0079]
FIG. 24 shows an example of a state in which drawing data D1 to D8 are stored in the drawing data storage control means 30 when the drawing data storage control means 30 has the configuration shown in FIG. The drawing data registration means 35 described with reference to FIG. 10 is composed of a table having an entry for each unit drawing area. Each drawing data D1 to D8 includes the position of the entry corresponding to the minimum Y coordinate value. Stored in association. The drawing data existence range counting means 33 described with reference to FIG. 10 includes an entry table, an exit table, and a drawing data number counter table. The entry table has a minimum Y coordinate value at the position in each unit drawing area. The number of drawing data having (upper coordinates) is counted, and the withdrawal table includes drawing data having the maximum Y coordinate value (lower coordinates) at that position in each unit drawing area. The number is counted. The drawing data number counter table is a table that holds a numerical value indicating how many drawing data are present in each unit drawing area. This table can be filled by scanning the advance table and the exit table at the time of the drawing process, but for the sake of simplicity of explanation, here, before the drawing processing means 40 starts the drawing process, The explanation will be made on the assumption that the drawing data number counter table is filled by scanning the exit table.
[0080]
In the following description, it is assumed that the drawing process is performed by the three drawing processing units 40a, 40b, and 40c. When drawing data is stored in the drawing data storage control means 30, an activation command is issued to the drawing processing means. The drawing processing means 40a to 40c are activated almost at the same time, but since the access to the processing charge range assignment means 60 is controlled exclusively, they are ordered at this stage.
[0081]
Here, it is assumed that access to the first processing charge
[0082]
First, an execution example in the case of the first configuration will be described. In the first configuration example, the size of the divided drawing area is simply determined by the position coordinates of the divided drawing area or the processing order of the divided drawing area. Here, a case where the size of the divided drawing area is determined using the position coordinates as a key will be described. For the sake of simplicity, the description will be given of the case where the determination of the divided drawing area is performed prior to the drawing process. However, the determination of the divided drawing area is not necessarily performed prior to the drawing process, and may be performed in synchronization with the drawing process. Is possible.
[0083]
FIG. 25 shows a conceptual diagram about the division of the drawing area described here. First, an example of information prepared in the division
[0084]
When the drawing processing unit 40a first makes a processing assignment request to the processing charge
[0085]
When the drawing processing unit 40a receives the information of the divided drawing area in charge of processing, the drawing processing unit 40a reads the drawing data from the drawing data
[0086]
The drawing processing unit 40a again requests the processing assigned
[0087]
When there is an inquiry from the drawing processing means 40b, the processing charge range assignment means 60 determines that the divided drawing area BR2 starting from the unit drawing area R5 held in the unprocessed position holding means 64 described with reference to FIGS. 40b.
[0088]
When the drawing processing unit 40b receives the information of the divided drawing area in charge of processing, the drawing processing unit 40b reads the drawing data from the drawing data
[0089]
The drawing processing means 40b processes these drawing data, creates processing result data corresponding to the unit drawing area R8 from the unit drawing area R5, and registers it in the processing result storage control means 50. Then, the drawing processing means 40 again requests the processing charge range assignment means 60 to assign the divided drawing area in charge of processing and continues the processing.
[0090]
In the first request from the drawing processing means 40c, the processing range assignment means 60 draws the divided drawing area BR3 starting from the unit drawing area R9 held in the unprocessed position holding means 64 described in FIG. 14 and FIG. Assigned to the processing means 40c.
[0091]
When the drawing processing unit 40c receives the information of the divided drawing region BR3 in charge of processing, the drawing processing unit 40c reads the drawing data from the drawing data
[0092]
Subsequent processing is assigned to each drawing processing unit in the order in which the processing of the drawing processing units 40a to 40c ends. Here, for simplicity of explanation, FIG. 26 shows an outline of a time chart in this execution example. As shown in FIG. 26, the processing time of the drawing process in each divided drawing area BR1 to BR9 is not uniform due to the amount of drawing data in each divided drawing area and other factors.
[0093]
As shown in FIG. 26, the divided drawing area BR4 to be assigned next is assigned to the drawing processing means 40a that finishes processing first. When the drawing processing unit 40a finishes the processing of the divided drawing region BR1, the drawing processing unit 40a stores the position of the unit drawing region R4 that is the unit drawing region closest to the unprocessed side of the divided drawing region BR1 in the processed drawing
The processing charge range assignment means 60 assigns the divided drawing area BR4 to this request. Here, the divided drawing area is determined prior to the drawing process. However, when the drawing area is determined according to the request in synchronization with the drawing process, the position of the divided drawing area to be assigned is after R13. The reference value that the division reference management means 70 answers to the processing range assignment means 60 is changed from the
[0094]
When the drawing processing unit 40a is assigned the divided drawing area BR4, the drawing data determining / discarding
[0095]
FIG. 29 shows a conceptual diagram of the processing result data stored in the processing result storage control means 50 as a processing result. FIG. 30 shows divided drawing areas BU1 to BU6 as an example of equally dividing the drawing area for comparison. FIG. 31 shows an outline of a time chart regarding the progress of processing in that case. The drawing description shown in FIG. 20 is based on the drawing object having the larger Y coordinate in the drawing area. Therefore, when the drawing process is performed from the smaller Y coordinate to the larger one as shown in FIG. When the processing is divided into equally divided divided drawing areas, the balance of load distribution is lost as shown in the time chart of FIG. 31, and a bottleneck is generated, resulting in a slow overall processing speed. Become. On the other hand, according to the present invention, since the granularity of load division becomes fine in the latter half of the processing, even in the case of the drawing description shown in FIG. Parallel processing is performed.
[0096]
Next, an embodiment according to the second configuration example will be described from the state in which the drawing data is stored in the drawing data storage control means 30 as shown in FIG.
[0097]
In the second configuration example, the size of the divided drawing area is determined by information depending on input data such as the distribution of input data, information indicating the progress of processing, or both. Here, as an example, a case will be described in which the size of a divided drawing area is determined based on the number of drawing data per unit drawing area as information depending on input data. Since the number of drawing data per divided drawing area can be determined before starting the drawing process, it is also possible to determine the divided drawing area prior to the drawing process. An example of determining the area will be described.
[0098]
First, for the sake of simplicity of explanation, FIG. 27 shows in advance a conceptual diagram regarding the division of the drawing area determined in the embodiment here. In the example shown here, the unit drawing areas R1 to R13 are divided when the number of drawing data per unit drawing area exceeds 10, and the drawing data per unit drawing area is divided in the unit drawing areas R14 to R18. It is assumed that a criterion for dividing the divided drawing area when the cumulative value of the number of images exceeds 4 is stored in the division reference management means 70. As a result, as shown in the lower part of FIG. The drawing areas BS1 to BS6 are determined. Similarly, for simplicity of explanation, FIG. 28 shows an outline of a time chart of an execution example of processing according to the second configuration. The drawing processing unit 40a processes the divided drawing region BS1, the drawing processing unit 40b processes the divided drawing region BS2, the drawing processing unit 40c processes the divided drawing region BS3, and the drawing processing unit 40c. The drawing processing unit 40b processes the divided drawing area BS5, and the drawing processing unit 40b processes the divided drawing area BS6.
[0099]
At the start of the drawing process, as in the description of the execution example of the first configuration, the divided drawing area allocation request is received by the processing
[0100]
When the processing charge
[0101]
Next, the processing charge
[0102]
Since the processing when the drawing processing unit 40b is assigned the divided drawing region BS2 is the same as that described in the execution example of the first configuration, description thereof will be omitted, but here the drawing data read into the drawing processing unit 40b is D1, D3, D4, and D7.
[0103]
Next, the processing charge
[0104]
Since the processing when the drawing processing unit 40c is assigned the divided drawing region BS3 is the same as that described in the execution example of the first configuration, description thereof will be omitted, but the drawing data read into the drawing processing unit 40c here is D1, D5, D7, and D8.
[0105]
Next, the processing charge
[0106]
Since the processing when the drawing processing means 40a finishes the first processing and is assigned the divided drawing area BS4 again is the same as that described in the execution example of the first configuration, the description is omitted here. The drawing data D2 and D3 are deleted from the drawing data holding means 43 of 40a, D1 is left, and D6, D7 and D8 are newly read.
[0107]
Next, the processing charge
[0108]
The processing when the drawing processing unit 40b finishes the initial processing and is assigned the divided drawing region BS5 again is the same as described above, and will not be described here. However, the drawing processing unit 40b draws the drawing data from the drawing
[0109]
Next, the processing charge
[0110]
Since the processing when the drawing processing means 40c finishes the first processing and is assigned the divided drawing area BS6 again is the same as described above, the description thereof will be omitted, but here the drawing data holding means 43 of the drawing processing means 40c draws the drawing. Data D5, D7, and D8 are deleted, D1 is left, and D6 is newly read.
[0111]
As described above, the drawing processing device of the present invention divides the drawing processing load into more than the number of drawing processing devices, and the drawing processing load assigned in the latter half of the processing is assigned in the first half of the processing. The parallel drawing processing is performed by dividing the drawing processing so as to be smaller than the drawing processing load. This makes it possible to speed up the drawing process even when there is a partial load bias in the page image to be drawn, especially when there is a heavy load area at the end of the process. In the first half, the granularity of the load division can be increased, so that the number of times of switching the process allocation can be reduced, and the overhead due to the contention of access to resources can be reduced.
[0112]
Further, even when the processing of the processing means in charge of the specific partial processing is temporarily delayed due to the influence of other processes at the time of execution, the drawing processing can be speeded up.
[0113]
Even if the processing charge range allocation means 60 determines the size of the divided drawing area at the time of inquiry from the drawing processing means 40a to 40n, it starts drawing processing before the inquiry time, for example, in an extreme case. The drawing process may be started after the sizes of all the divided drawing areas are determined with reference to the division
[0114]
In the above example, the example in which the maximum value and the minimum value of the Y coordinate of the drawing data are inspected at the time of reading and read into each drawing processing means has been described, but the inspection of whether each drawing data is in each divided drawing area It is also possible to read out a part of the data and perform it by each drawing processing means.
[0115]
【The invention's effect】
As described above, according to the configuration of the drawing processing apparatus of the present invention, the processing range handled by each of the plurality of processing units in the drawing processing apparatus is dynamically determined by having a plurality of division reference values of the drawing data. Thus, the overall processing time can be effectively shortened.
[0116]
In particular, the size of the divided drawing area is determined so as to reduce the granularity of the drawing process at the end of the process, and the drawing data to be assigned to each drawing processing means is configured to be smaller. Even when drawing objects are biased in the drawn area, the processing can be prevented from being biased to specific processing means, and high-speed drawing processing can be performed.
[Brief description of the drawings]
FIG. 1 is a diagram showing a configuration of an embodiment of a drawing processing apparatus of the present invention.
FIG. 2 is a diagram showing the configuration of another embodiment of the drawing processing apparatus of the present invention.
FIG. 3 is a block diagram illustrating an example of a system to which the drawing processing apparatus of the present invention is applied.
FIG. 4 is a flowchart showing an example of the operation of the entire system having the drawing processing apparatus of the present invention.
FIG. 5 is a flowchart showing an example of the operation of one page of the entire system having the drawing processing apparatus of the present invention.
FIG. 6 is a flowchart showing a flow of drawing data generation means processing of the drawing processing apparatus of the present invention.
FIG. 7 is a diagram illustrating an example of a data structure of drawing data generated by a drawing data generation unit.
FIG. 8 is a diagram showing a configuration of an embodiment of drawing data storage control means of the drawing processing apparatus of the present invention.
FIG. 9 is a flowchart showing the flow of processing of the drawing data storage control means shown in FIG. 8;
FIG. 10 is a diagram showing a configuration of an embodiment of drawing data storage control means of the drawing processing apparatus of the present invention.
11 is a flowchart showing the flow of processing in the drawing data storage control means shown in FIG.
FIG. 12 is a flowchart showing the flow of processing when drawing data is sent from the drawing data storage control means to the drawing processing means.
FIG. 13 is a flowchart showing the flow of processing of the drawing data storage control means for the processing charge range assignment means of the drawing processing apparatus of the present invention.
FIG. 14 is a diagram illustrating a configuration of a processing charge range assignment unit.
FIG. 15 is a flowchart showing a processing flow of a processing charge range assignment unit.
FIG. 16 is a diagram showing a configuration of a processing charge range assignment unit.
FIG. 17 is a flowchart showing the flow of processing in the configuration of processing charge range assignment means.
FIG. 18 is a diagram showing a configuration of processing of a drawing processing unit of the drawing processing apparatus of the present invention.
FIG. 19 is a diagram showing a flow of processing of a drawing processing means.
FIG. 20 is a diagram illustrating an example of a drawing description.
FIG. 21 is a diagram illustrating an example of drawing data.
FIG. 22 is a diagram showing an example of a unit drawing area of drawing data in the drawing processing apparatus of the present invention.
FIG. 23 is a diagram illustrating an example of a storage state of drawing data in the drawing processing apparatus of the present invention.
FIG. 24 is a diagram showing an embodiment of a drawing data storage state in the drawing processing apparatus of the present invention.
FIG. 25 is a diagram showing an example of a divided drawing area in the drawing processing apparatus of the present invention.
FIG. 26 is a diagram showing a time chart of an embodiment in the drawing processing apparatus of the present invention.
FIG. 27 is a diagram showing an example of a divided drawing area in the drawing processing apparatus of the present invention.
FIG. 28 is a diagram showing a time chart of one embodiment in the drawing processing apparatus of the present invention.
FIG. 29 is a diagram illustrating a conceptual diagram of a result of a drawing process.
FIG. 30 is a diagram illustrating a divided drawing area when the drawing area is divided equally.
FIG. 31 is a diagram showing a time chart of an execution example when a drawing area is divided equally.
[Explanation of symbols]
10 page description language
20 Drawing data generation means
30. Drawing data storage control means
40 Drawing processing means
50 Processing result storage control means
60 Processing area allocation means
70 division criteria management means
200 Output device
300 Network interface
400 network
100 Drawing processing device
21 Drawing data
22 Data structure
61 Split drawing area
31 Drawing data storage interface
32 Drawing data existence range extraction means
33 Drawing data existence range counting means
34 Interface for notifying the number of drawing data
35 Drawing data registration means
36 Interface for sending drawing data
61 Exclusive interface
62 Divided drawing area determination means
63 Drawing range determination means
64 Unprocessed position holding means
65 Total number of drawing data
66 Interface for querying the number of drawing data
67 Reference value inquiry interface
41 Processed drawing position holding means
42 In charge drawing range holding means
43 Drawing data holding means
44 Drawing data judgment / discard means
45 Drawing mechanism
46 Drawing processing buffer
11 Drawing sample
12 Input drawing description data
Claims (13)
描画命令を受け取り、描画図形の内部データを構成する描画データを生成する描画データ生成手段と、
前記描画データの格納及び描画処理手段に対する出力の制御を行う描画データ格納制御手段と、
前記描画データ格納制御手段からの描画データを入力して描画処理を実行する複数の描画処理手段と、
前記複数の描画処理手段における処理単位を決定するための描画領域の分割基準となる基準値を保持する分割基準管理手段と、
前記分割基準管理手段の有する基準値に基づいて前記描画領域を分割し、前記描画処理手段各々の要求に応じて、該分割された描画領域を前記描画処理手段各々に割り当てる処理担当範囲割り当て手段と、
前記複数の描画処理手段から出力される複数の処理結果を記憶する処理結果格納手段と、
前記処理結果格納手段に格納された処理結果の出力を行う出力手段とを備え、
前記分割基準管理手段は、異なる複数の基準値を有し、複数の前記描画処理手段における処理の全体の進行度に応じて選択される１つの基準値を前記処理担当範囲割り当て手段に出力し、該処理担当範囲割り当て手段は、該選択された基準値に基づき前記描画領域を分割し分割描画領域を決定し、該分割描画領域を前記複数の描画処理手段各々に割り当てることを特徴とする描画処理装置。In a drawing processing device that interprets drawing commands and executes drawing processing,
Drawing data generation means for receiving a drawing command and generating drawing data constituting internal data of the drawing figure;
Drawing data storage control means for controlling the output to the drawing data storage and drawing processing means;
A plurality of drawing processing means for executing drawing processing by inputting drawing data from the drawing data storage control means;
A division criterion management unit that holds a reference value serving as a division criterion for a drawing area for determining a processing unit in the plurality of drawing processing units;
A processing charge range assigning unit that divides the drawing area based on a reference value possessed by the division reference managing unit, and assigns the divided drawing region to each of the drawing processing units in response to a request of each of the drawing processing units; ,
Processing result storage means for storing a plurality of processing results output from the plurality of drawing processing means;
Output means for outputting the processing result stored in the processing result storage means,
The division criterion management means has a plurality of different reference values, and outputs one reference value selected according to the overall progress of processing in the plurality of drawing processing means to the processing charge range assignment means, The processing area allocation means divides the drawing area based on the selected reference value, determines a divided drawing area, and assigns the divided drawing area to each of the plurality of drawing processing means. apparatus.
描画命令を受け取り、描画図形の内部データを構成する描画データを生成する描画データ生成ステップと、
前記描画データの格納及び描画処理手段に対する出力の制御を行う描画データ格納制御ステップと、
複数の描画処理手段において、前記描画データ格納制御ステップの制御に基づいて出力される描画データを入力して描画処理を実行する描画処理ステップと、
前記複数の描画処理手段における処理単位を決定するための描画領域の分割基準となる異なる複数の基準値から、前記複数の描画処理手段における処理の全体の進行度に応じて１つの基準値を選択し、選択した基準値を処理担当範囲割り当て手段に出力する分割基準管理ステップと、
分割基準管理ステップにおいて選択された基準値に基づいて前記描画領域を分割し、前記描画処理手段各々の要求に応じて、該分割された描画領域を前記描画処理手段各々に割り当てる処理を実行する処理担当範囲割り当てステップと、
前記複数の描画処理手段から出力される複数の処理結果を処理結果格納手段に格納する処理結果格納ステップと、
前記処理結果格納手段に格納された処理結果の出力を行う出力ステップと、
を有することを特徴とする描画処理方法。In a drawing processing method that interprets drawing commands and executes drawing processing,
A drawing data generation step for receiving a drawing command and generating drawing data constituting internal data of the drawing figure;
A drawing data storage control step for controlling the output to the drawing data storage and drawing processing means;
In a plurality of drawing processing means, a drawing processing step of executing drawing processing by inputting drawing data output based on the control of the drawing data storage control step;
A single reference value is selected from a plurality of different reference values that serve as division criteria for drawing areas for determining processing units in the plurality of drawing processing means according to the overall progress of processing in the plurality of drawing processing means. A division reference management step for outputting the selected reference value to the processing range assignment means,
A process of dividing the drawing area based on the reference value selected in the division reference management step and executing a process of assigning the divided drawing area to each of the drawing processing means in response to a request from each of the drawing processing means. The assignment range step,
A processing result storage step of storing a plurality of processing results output from the plurality of drawing processing means in a processing result storage means;
An output step for outputting the processing result stored in the processing result storage means;
A drawing processing method characterized by comprising:
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP16554597A JP3707208B2 (en) | 1997-06-23 | 1997-06-23 | Drawing processor |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP16554597A JP3707208B2 (en) | 1997-06-23 | 1997-06-23 | Drawing processor |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH1115983A JPH1115983A (en) | 1999-01-22 |
| JP3707208B2 true JP3707208B2 (en) | 2005-10-19 |
Family
ID=15814421
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP16554597A Expired - Fee Related JP3707208B2 (en) | 1997-06-23 | 1997-06-23 | Drawing processor |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JP3707208B2 (en) |
Families Citing this family (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP7149826B2 (en) * | 2018-12-04 | 2022-10-07 | シュナイダーエレクトリックホールディングス株式会社 | screen display device |
-
1997
- 1997-06-23 JP JP16554597A patent/JP3707208B2/en not_active Expired - Fee Related
Also Published As
| Publication number | Publication date |
|---|---|
| JPH1115983A (en) | 1999-01-22 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US5619624A (en) | Apparatus for selecting a rasterizer processing order for a plurality of graphic image files | |
| JP4464424B2 (en) | Image output system | |
| JP5475307B2 (en) | Memory management method, computer readable medium and apparatus for rasterization | |
| JP3474078B2 (en) | Drawing processing device | |
| CN103034618A (en) | Image processing device | |
| US20070112441A1 (en) | Modular layer for abstracting peripheral hardware characteristics | |
| JP5344075B1 (en) | Print image processing system and program | |
| JP5942860B2 (en) | Print data processing system | |
| JP3707208B2 (en) | Drawing processor | |
| JP3620154B2 (en) | Printing system and printing control method | |
| US20050094194A1 (en) | Enhanced image processing with shared data storage | |
| JP2000035870A (en) | Printing system and printer | |
| US8934121B2 (en) | Coordinated, distributed, reusable document component respository | |
| JP2002169682A (en) | Server apparatus, image processing apparatus, information processing apparatus, data processing method, information processing method, storage medium and program | |
| JPH0934660A (en) | Information processing device | |
| JP2018106222A (en) | Information processing apparatus and communication control method | |
| JP3728820B2 (en) | Drawing processor | |
| JP5799968B2 (en) | Printing system | |
| JP2000198239A (en) | Print system | |
| JP2000132350A (en) | Plotting processor | |
| JP2000132349A (en) | Plotting processor | |
| JP3225711B2 (en) | Job processing system and job processing execution device | |
| JP3897083B2 (en) | Print processing apparatus and print processing method | |
| JP2007152623A (en) | Image plotting controller, method for controlling plotting of image, memory medium, and program | |
| JPH10304180A (en) | Drawing processor and drawing processing method |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A977 | Report on retrieval |
Free format text: JAPANESE INTERMEDIATE CODE: A971007 Effective date: 20050218 |
|
| A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20050329 |
|
| A521 | Written amendment |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20050512 |
|
| A521 | Written amendment |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20050512 |
|
| TRDD | Decision of grant or rejection written | ||
| A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 Effective date: 20050712 |
|
| A61 | First payment of annual fees (during grant procedure) |
Free format text: JAPANESE INTERMEDIATE CODE: A61 Effective date: 20050725 |
|
| R150 | Certificate of patent or registration of utility model |
Free format text: JAPANESE INTERMEDIATE CODE: R150 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20090812 Year of fee payment: 4 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20100812 Year of fee payment: 5 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20110812 Year of fee payment: 6 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20120812 Year of fee payment: 7 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20120812 Year of fee payment: 7 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20130812 Year of fee payment: 8 |
|
| LAPS | Cancellation because of no payment of annual fees |