JP3651214B2 - 印刷処理装置及び印刷処理方法 - Google Patents

Description

【０００１】
【発明の属する技術分野】
本発明は印刷処理装置及び印刷処理方法に関し、特に描画命令をビットマップ展開して印刷処理する印刷処理装置及び描画命令をビットマップ展開して印刷処理する印刷処理方法に関する。
【０００２】
【従来の技術】
近年の小型、高速化したディジタル印刷に適した電子写真方式のページプリンタの開発に伴い、従来の文字情報中心の印刷から脱皮した、ラスタ、図形、文字などを同様に取り扱い、かつ図形、文字等の拡大、回転、変形などが自由に制御できる記述言語を用いた印刷処理装置が普及してきている。
【０００３】
この種の記述言語の代表例として、PostScript (Adobe Systems 社商標) 、Interpress (Xerox 社商標) 、Acrobat(Adobe Systems 社商標) 、GDI (Graphics Device Interface: Microsoft 社商標) 等が知られている。
【０００４】
記述言語で作成されている印刷データは、ページ内の任意の位置のラスタ、図形、文字を表現する描画命令が任意の順で構成されており、ページプリンタで印字するためには、印字前に印刷データをビットマップ展開しなければならない。
【０００５】
ビットマップ展開というのは、印刷データをページまたはページの一部を横切る一連の個々のドットまたは画素へ展開してラスタ走査線を形成し、そのページの下へ引き続く走査線を次々に発生する過程である。
【０００６】
記述言語で作成されている印刷データのうち、図形あるいは文字に関する描画命令を、それが表現する描画オブジェクトの輪郭を構成するエッジ情報を含んだリストを複数個連結させたディスプレイリストに変換した後、そのディスプレイリストをビットマップ展開することにより印刷処理を行う方法が一般的に知られている。
【０００７】
図２２、図２３はディスプレイリストからビットマップ展開のためのエッジの座標点を生成する処理の流れを示す図である。
図において多角形の輪郭は、４つのエッジから構成されている。これらのエッジは、絶対値の小さい方の頂点( 以下、エッジの始点と呼ぶ) のｙ座標値によりソートされ、ｙバケットリストに連結されて記憶されている。
【０００８】
ｙバケットリストの各セルは、走査ラインと各エッジの交点を発生させるための情報、即ち、エッジの始点のｘ座標値、走査ライン当たりのｘの変化量Δｘ 、エッジと走査ラインとの交差数Δｙを含んでいる。ｙバケットリストおよび各セルを含む全体をディスプレイリストと呼ぶ。
【０００９】
一般的にディスプレイリストからエッジの座標点を生成する処理は、走査ライン変換と呼ばれる。走査ライン変換によって生成されたエッジの座標点を座標値によりソートし、ソートされた座標点間を所定の色データで順次塗りつぶし処理を施したものがビットマップデータである。
【００１０】
走査ライン変換は、１走査ラインずつ、上部から下部までのエッジの座標点を発生する。即ち、現在の走査ラインと交わる全エッジをリスト化して、図２３に示すアクティブエッジリストを作成しながらエッジの座標点を出力する。
【００１１】
現在の走査ラインの処理後、アクティブエッジリストの各レコードは次走査のために更新（ｘ＝ｘ＋Δｘ, Δｙ＝Δｙ−１）される。Δｙ＝０になったバケットは、リストから削除される。
【００１２】
上記のような処理を行う従来技術としては、例えば特願平０９−１３８６０９号公報がある。これは、ディスプレイリストから描画オブジェクトのエッジを表す座標点を生成する座標点生成処理と、座標点に順序を付けるソート処理と、を独立させ、座標点生成処理に関しては、複数の座標点生成装置で繰り返し座標点生成のみを行うよう構成されている。
【００１３】
【発明が解決しようとする課題】
しかし、上記のような従来の複数の座標点生成装置は、１つの走査ラインに同期して座標点を生成するため、複数の座標点生成装置が処理している各セルのΔｙがすべて０になるまで走査ラインは更新され、継続して座標点生成処理を行うことになる。
【００１４】
したがって、その間にΔｙが０になった座標点生成装置は他の座標点生成装置の処理が終了するまで待機状態となって無駄が生じてしまう。
また、すべての座標点生成装置の処理が終了して、新たなセルをエントリする場合も、その時のｙ座標値に連結されるセルの数が複数の座標点生成装置の数よりも少なければ、待機状態となる座標点生成装置が発生してしまう。
【００１５】
さらに、Δｙが０になった座標点生成装置に対して、走査ラインを更新する毎に追加エントリできるセルがあればセルの追加を行って、なるべく待機状態の座標点生成装置を少なくしたとしても、追加判定の結果、その走査ライン上に追加エントリできるセルがなければ座標点生成装置は結局待機状態のままとなってしまう。
【００１６】
本発明はこのような点に鑑みてなされたものであり、座標点を順次非同期に生成することで待機状態をなくし、高速に印刷処理を行う印刷処理装置を提供することを目的とする。
【００１７】
また、本発明の他の目的は、座標点を順次非同期に生成することで待機状態をなくし、高速に印刷処理を行う印刷処理方法を提供することである。
【００１８】
【課題を解決するための手段】
本発明では上記課題を解決するために、描画命令をビットマップ展開して印刷処理する印刷処理装置において、少なくとも文字又は図形のいずれかの描画オブジェクトを有し、前記描画命令で記述されている印刷データを解釈して、内部命令に変換する印刷データ解釈手段と、前記内部命令から前記描画オブジェクトの輪郭を構成するエッジのエッジ情報を前記エッジ毎に有したディスプレイリストを走査ライン毎に生成するディスプレイリスト生成手段と、前記ディスプレイリストの前記エッジ情報を用いて、前記描画オブジェクトの前記エッジを表す複数の座標点を順次非同期に生成する座標点生成手段と、前記座標点に順番を付けるソート手段と、前記順番にしたがって整列させた前記座標点にもとづいて、前記印刷データを印刷出力可能な印刷画像データに変換する印刷画像データ変換手段と、前記印刷画像データの出力処理を行う印刷出力手段と、を有することを特徴とする印刷処理装置が提供される。
【００１９】
ここで、印刷データ解釈手段は、少なくとも文字又は図形のいずれかの描画オブジェクトを有し、描画命令で記述されている印刷データを解釈して、内部命令に変換する。ディスプレイリスト生成手段は、内部命令から描画オブジェクトの輪郭を構成するエッジのエッジ情報をエッジ毎に有したディスプレイリストを走査ライン毎に生成する。座標点生成手段は、ディスプレイリストのエッジ情報を用いて、描画オブジェクトのエッジを表す複数の座標点を順次非同期に生成する。ソート手段は、座標点に順番を付ける。印刷画像データ変換手段は、順番にしたがって整列させた座標点にもとづいて、印刷データを印刷出力可能な印刷画像データに変換する。印刷出力手段は、印刷画像データの出力処理を行う。
【００２０】
また、描画命令をビットマップ展開して印刷処理する印刷処理方法において、少なくとも文字又は図形のいずれかの描画オブジェクトを有し、前記描画命令で記述されている印刷データを解釈して、内部命令に変換し、前記内部命令から前記描画オブジェクトの輪郭を構成するエッジのエッジ情報を前記エッジ毎に有したディスプレイリストを走査ライン毎に生成し、前記ディスプレイリストの前記エッジ情報を用いて、前記描画オブジェクトの前記エッジを表す座標点を順次非同期に生成し、前記座標点に順番を付けるソートを行い、前記順番にしたがって整列させた前記座標点にもとづいて、前記印刷データを印刷出力可能な印刷画像データに変換し、前記印刷画像データの出力処理を行うことを特徴とする印刷処理方法が提供される。
【００２１】
ここで、印刷データは、まず内部命令に変換される。そして、内部命令から描画オブジェクトの輪郭を構成するエッジのエッジ情報をエッジ毎に有したディスプレイリストを走査ライン毎に生成する。その後、ディスプレイリストのエッジ情報を用いて、描画オブジェクトのエッジを表す座標点を順次非同期に生成する。そして、この座標点にもとづいて、印刷データを印刷出力可能な印刷画像データに変換して出力する。
【００２２】
【発明の実施の形態】
以下、本発明の実施の形態を図面を参照して説明する。図１は本発明の印刷処理装置の原理図である。
【００２３】
印刷データ解釈手段２は、少なくとも文字又は図形のいずれかの描画オブジェクトを有し、描画命令で記述されている印刷データ１を解釈して、内部命令に変換する。
【００２４】
ディスプレイリスト生成手段３は、内部命令から描画オブジェクトの輪郭を構成するエッジのエッジ情報をエッジ毎に有したディスプレイリストを走査ライン毎に生成する。
【００２５】
座標点生成手段４は、ハードウェアで構成され、ディスプレイリストのエッジ情報を用いて、描画オブジェクトのエッジを表す複数の座標点を順次非同期に生成する。また、座標点生成手段４は複数で構成され、座標点生成手段４の数と同数の座標点を一度に生成する。
【００２６】
ソート手段５は、所定のプログラムを中央演算処理装置で実行することにより座標点に順番を付ける。
印刷画像データ変換手段６は、この順番にしたがって整列させた座標点にもとづいて、印刷データ１を印刷出力可能な印刷画像データに変換する。印刷出力手段８は、印刷画像データの出力処理を行う。
【００２７】
本発明の印刷処理装置１０は、複数の座標点生成手段４を非同期に動作させることによって、あるエッジを表す座標点生成が終了すると直ちに次に処理すべきエッジのエッジ情報を転送し、座標点生成を開始させる構成とした。
【００２８】
すなわち、複数の座標点生成手段４は走査ラインに同期して座標点生成を行う必要がなく、各座標点生成手段毎に独立して座標点生成処理が行えるため、ある座標点生成手段の処理が終了すると、すぐに次のエッジ情報を転送して次の座標点生成処理を開始することができ、資源の有効活用が可能になる。
【００２９】
したがって、本発明を適用することにより、大規模なハードウェアを用意することなく、さらに複雑な描画オブジェクトを３角形や台形からなるディスプレイリストに分割するための多大な計算を必要とすることなく、高速にビットマップ展開することが可能になる。
【００３０】
次に印刷処理装置１０の詳細構成について説明する。図２は本発明の印刷処理装置１０の詳細構成を示す図である。
印刷データ１は印刷処理装置で処理可能な記述言語で記述されたものであり、図示されないパーソナルコンピュータやワークステーションにおいて、文書作成や編集等を処理するアプリケーションプログラムで作成された文書データから生成されたものである。
【００３１】
本実施の形態で対象とする記述言語は、例えばＧＤＩであるが、Ａｃｒｏｂａｔで代表されるＰＤＦ（Ｐｏｒｔａｂｌｅ Ｄｏｃｕｍｅｎｔ Ｆｏｒｍａｔ）、またはＰｏｓｔＳｃｒｉｐｔで代表されるページ記述言語であってもよい。
【００３２】
印刷データスプール手段１ａは、印刷データ１を入力するための通信機能や、印刷データ解釈手段２へ出力されるまで印刷データを一時的に記憶する機能等を備えたものである。
【００３３】
印刷データ解釈手段２は、印刷データスプール手段１ａより入力された印刷データを、定められた記述言語のシンタックスに従ってトークンとして切り出した後、トークンを解釈し、内部命令やその引数に変換する。
【００３４】
内部命令には、文字／図形／ラスタの描画を実行する描画命令や、色や線属性など描画に必要な情報を設定する描画状態命令がある。描画命令が文字あるいは図形の場合は、描画命令をディスプレイリスト生成処理手段３ａへ転送する。一方、描画命令がラスタの場合は、描画命令をラスタデータ処理手段３ｂへ転送するとともに、対象とするラスタデータの縦と横の大きさをディスプレイリスト生成手段３ａへ転送する。
【００３５】
ディスプレイリスト生成手段３ａは、文字／図形の描画命令に応じて、描画されるオブジェクトの輪郭を構成するエッジデータを生成した後、オブジェクト毎にヘッダ情報と、描画オブジェクトの輪郭を構成するエッジの始点、傾きおよびエッジと走査ラインとの交差数を含むエッジ情報とから構成されるディスプレイリストを生成する。
【００３６】
また、印刷データ解釈手段２より転送されたラスタデータの縦と横の大きさに基づき、ラスタデータの輪郭を示すディスプレイリストを生成する。
ラスタデータ処理手段３ｂは、ラスタの描画命令に応じて、対象とするラスタデータに対し座標変換、色補正等のラスタ処理を実行し、処理されたラスタデータをラスタデータバッファ３ｂ−１に格納する。
【００３７】
バンド分割手段３ａ−２は、ディスプレイリスト生成手段３ａで生成された描画オブジェクト毎のディスプレイリスト１ページ分を所定のバンド数で分割されるバンド単位で分割する。
【００３８】
バンドの分割数は、後段の出力バッファ８ａの大きさで決定される。バンド単位で分割されたディスプレイリストは、ディスプレイリストバッファ３ａ−１に格納される。
【００３９】
印刷データ解釈手段２からバンド分割手段３ａ−２までの処理を、ページを構成する全ての描画オブジェクトに対して実行することにより、ページ毎にバンド単位で分割されたディスプレイリストが、ディスプレイリストバッファ３ａ−１に格納される。
【００４０】
ディスプレイリストバンドバッファ３ａ−２は、２つのバッファで構成され、バンド単位でディスプレイリストバッファ３ａ−１からディスプレイリストデータが交互に入力される。
【００４１】
ディスプレイリスト管理手段４ａは、ディスプレイリストバンドバッファ３ａ−２からのディスプレイリストの読み出しと、後段の座標点生成処理手段４ｂが待機状態にあることの検出と、検出結果に基づき座標点生成処理手段４ｂへディスプレイリストのエッジ情報の転送を制御するものである。
【００４２】
また、ディスプレイリスト管理手段４ａでは、ヘッダ情報に基づき処理するオブジェクトのタイプが文字／図形かまたはラスタかを検出し、ラスタの場合は、印刷画像データ変換手段６にラスタデータバッファ３ｂ−１からラスタデータバンドバッファ７に当該オブジェクトのラスタデータを転送するよう指示する。
【００４３】
座標点生成処理手段４ｂは、エッジの始点、傾きおよびエッジと走査ラインとの交差数を含むエッジ情報から、エッジの座標点をエッジリストバッファ９に出力するものであり、座標点生成回路の数と同数のエッジの座標点を一度に出力する複数の座標点生成回路で構成される。
【００４４】
複数の座標点生成回路は、走査ラインに対して非同期に各々複数のエッジに対する座標点生成を実行する。処理中の全てのエッジに対する処理が終了すると、ディスプレイリスト管理手段４ａより次に処理すべき複数のエッジ情報が転送される。
【００４５】
１つのオブジェクトに対する全てのエッジの座標点生成が終了するまで、複数の座標点生成回路による座標点生成が繰り返される。また、処理するオブジェクトが文字／図形の場合は、ヘッダ情報に基づき処理するオブジェクトの色データがエッジリストバッファ９に格納される。
【００４６】
ソート手段５は、座標点生成処理手段４ｂによる１つのオブジェクトに対する全てのエッジの座標点生成が終了した後、エッジリストバッファ９に格納されている走査ライン毎のエッジ座標点データを、座標値の小さいものから順次整列するよう並べかえる処理を行うものであり、所定のプログラムを中央演算処理装置で実行する構成となっている。ソート処理のためのプログラムとしては、例えばクイックソートプログラムが用いられる。
【００４７】
印刷画像データ変換手段６は、エッジリストバッファ９の座標値の小さいものから順次整列するよう並べかえられたエッジの座標点のペアの間の塗りつぶし処理を行い、出力バッファ８ａに出力するものである。
【００４８】
処理するオブジェクトが文字／図形の場合は、エッジリストバッファ９に格納されている色データにより塗りつぶし処理を実行する。処理するオブジェクトがラスタデータの場合は、ラスタデータバンドバッファ７よりエッジの座標点のペアの間を埋めるラスタデータを読み出し、出力バッファ８ａに出力する。
【００４９】
なお、エッジリストバッファ９も２つのバッファで構成され、座標点生成処理およびソート処理と、印刷画像データ変換処理はパイプラインで実行可能に構成されている。
【００５０】
出力バッファ８ａは、２つのバッファで構成され、一方のバッファが印刷画像データ変換手段６により塗りつぶし処理が行われている間、他方のバッファは、後段のプリンタ装置制御手段８ｂを介して、プリンタ装置２０へ印刷画像データが転送されるよう構成されている。
【００５１】
プリンタ装置制御手段８ｂは、プリンタ装置２０の出力タイミングに応じて出力バッファ８ａの印刷画像データをプリンタ装置２０へ転送するとともに、プリンタ装置２０の状態制御および管理を実行するものである。
【００５２】
プリンタ装置２０は、プリンタ装置制御手段８ｂの制御に基づき、出力バッファ８ａから出力される印刷画像データを受け取って、記録用紙に印字し出力するものである。
【００５３】
さらに、詳しくは、ＣＭＹＢＫ（シアン、マゼンタ、イエロー、ブラック）カラーの色毎に露光、現像、転写を繰り返すことによりフルカラー画像を出力できるレーザ走査方式の電子写真方式を用いたカラーページプリンタである。
【００５４】
なお、本実施の形態はディスプレイリストが所定のバンド単位に分割され、バンド単位で処理されることを前提に記載されているが、これに限定されるものではなく、ページ単位で処理される構成であってもよい。
【００５５】
次に印刷処理装置１０における印刷処理の流れの概要について説明する。図３、図４は印刷処理の流れの概要を示すフローチャートである。
〔Ｓ１〕印刷データスプール手段１ａに文字または図形を含む印刷データ１が入力されると、印刷データ解釈手段２、ディスプレイリスト生成処理手段３ａ、バンド分割手段３ａ−２を介してディスプレイリストが生成され、少なくとも１ページ分のバンド分割されたディスプレイリストがディスプレイリストバッファ３ａ−１に格納される．
〔Ｓ２〕ディスプレイリストバッファ３ａ−１より、バンド単位で順次ディスプレイリストがディスプレイリストバンドバッファ３ａ−２に入力される。
〔Ｓ３〕ディスプレイリスト管理手段４ａにおいて、最初のオブジェクトのディスプレイリストのエッジ情報が、最大で座標点生成処理手段４ｂの有する座標点生成回路の数だけ座標点生成処理手段４ｂに転送される。
〔Ｓ４〕座標点生成処理手段４ｂでは、座標点の生成を行う。
〔Ｓ５〕座標点生成処理手段４ｂは走査ラインの更新を行う。
〔Ｓ６〕全ての座標点生成回路の待機状態のチェックが行われる。もし、全ての座標点生成回路が待機状態でなければ、ステップＳ４へ戻る。もし、全ての座標点生成回路が待機状態であれば、当該オブジェクトの全てのエッジの処理が終了していることになり、ステップＳ７へ行く。
〔Ｓ７〕ソート手段５でソート処理を実行する。
〔Ｓ８〕印刷画像データ変換手段６で印刷画像データへの変換処理および出力バッファ８ａへの出力が実行される。
〔Ｓ９〕バンド内の全てのオブジェクト処理終了のチェックが行われる。もし、当該バンドの全てのオブジェクトの処理が終了していなければ、ステップＳ３へ戻り、次のオブジェクトの最初のエッジ情報が、最大で座標点生成処理手段４ｂの有する座標点生成回路の数だけ座標点生成処理手段４ｂに転送され、ステップＳ４以下の処理が繰り返される。もし、当該バンドの全てのオブジェクトの処理が終了していれば、ステップＳ１０へ行く。
〔Ｓ１０〕プリンタ装置制御手段８ｂを介してプリンタ装置２０に印刷画像データの出力が行われる。
〔Ｓ１１〕次にページ内の全てのバンド処理終了のチェックが行われる。もし、当該ページの全てのバンドの処理が終了していなければ、ステップＳ２へ戻る。もし、当該ページの全てのバンドの処理が終了していれば、１ページ分の印刷処理は終了する。処理する印刷データが複数ページあれば、上記のような処理を複数ページ分繰り返す。
【００５６】
なお、図３及び図４の印刷データの流れの説明では、簡単にするため、ラスタデータ処理に関する記載は省略したが、ラスタデータ処理に関しては図２で説明したように処理される。
【００５７】
次にハードウェア構成について説明する。図５は印刷処理装置１０のハードウェアの構成例を示す図である。
印刷処理装置１０は、ホストコンピュータ１００と、ホストコンピュータ１００が接続されるネットワーク３０、描画処理カード１１０、プリンタ装置２０、描画処理カード１１０とプリンタ装置２０を接続する専用バス４０で構成されている。
【００５８】
ネットワーク３０は、例えばＥｔｈｅｒｎｅｔであり、ネットワーク３０を介して図示しないパーソナルコンピュータやワークステーションから印刷データ１が入力される。
【００５９】
ホストコンピュータ１００は、ＣＰＵ（中央演算処理装置）１０１と、メモリコントローラ１０２と、ＤＲＡＭ１０３と、システムバスコントローラ１０４と、ネットワークインタフェース１０５と、磁気ディスク１０６と、カードコントローラ１０７と、ＣＰＵバス１０８と、システムバス１０９とから構成される一般的なものである。
【００６０】
システムバス１０９は、例えばＰＣＩバスであり、カードコントローラ１０７はＣａｒｄＢｕｓ対応のコントローラであり、高速のデータ転送が可能である。
ホストコンピュータ１００には、印刷データスプール手段１ａ、印刷データ解釈手段２、ディスプレイリスト生成処理手段３ａ、バンド分割手段３ａ−２、ラスタデータ処理手段３ｂ、ラスタデータバッファ３ｂ−１、ディスプレイリストバッファ３ａ−１に相当する機能が実装される。
【００６１】
例えば、磁気ディスク１０６は、印刷データ解釈手段２、ディスプレイリスト生成処理手段３ａ、バンド分割手段３ａ−２、ラスタデータ処理手段３ｂの各処理のための所定のプログラム等の格納領域、印刷データスプール手段１ａの印刷データ格納領域として使用される。
【００６２】
また、ＤＲＡＭ１０３は、印刷データ解釈手段２、ディスプレイリスト生成処理手段３ａ、バンド分割手段３ａ−２、ラスタデータ処理手段３ｂの各処理のためのワークエリア、ラスタデータバッファ３ｂ−１、ディスプレイリストバッファ３ａ−１として使用される。
【００６３】
さらに、ＣＰＵ１０１は印刷データ解釈手段２、ディスプレイリスト生成処理手段３ａ、バンド分割手段３ａ−２、ラスタデータ処理手段３ｂの各処理を実行する。
【００６４】
図６は描画処理カード１１０のハードウェアの構成例を示す図である。フラッシュＲＯＭ１１３は、ソート手段５のソート処理のための所定のプログラム等が格納されるとともに、オペレーティングシステムのプログラムが格納される。
【００６５】
メモリ１１５は、例えばＤＲＡＭで構成され、ソート処理のためのプログラム実行のためのワークエリア、ディスプレイリストバンドバッファ３ａ−２、エッジリストバッファ９として使用される。
【００６６】
また、座標点生成ＬＳＩ１１６にはディスプレイリスト管理手段４ａと座標点生成処理手段４ｂの機能、印刷画像データ変換ＬＳＩ１１７には印刷画像データ変換手段６の機能、プリンタ制御ＬＳＩ１２０とビデオインタフェース１２１はプリンタ装置制御手段８ｂの機能がそれぞれ実装されている。
【００６７】
さらに、ＣＰＵ１１１はソート手段５のソート処理のための所定のプログラムの実行、ディスプレイリストバンドバッファ３ａ−２へのディスプレイリスト入力の制御、出力バッファメモリ１１８やラスタデータバンドバッファメモリ１１９のメモリクリアの制御等を実行する。また、出力バッファメモリ１１８とラスタデータバンドバッファメモリ１１９は、例えばＤＲＡＭで構成される。
【００６８】
このように、一体の回路基板上に構成することにより、カード内部バス１２２はホストコンピュータ１００のシステムバス１０９とは独立に設けることが可能になり、バスの競合によるデータ転送速度低下を低減することができる。
【００６９】
さらに、ホストコンピュータ１００のシステムバス１０９より高速のバスを設けることにより、データ転送の高速化が可能となる。また、出力バッファメモリ１１８とラスタデータバンドバッファメモリ１１９は、カード内部バス１２２を介さず直接印刷画像データ変換ＬＳＩ１１７に接続された構成をとっている。
【００７０】
このような構成をとることにより、データ転送のボトルネックを解消し、より高速のデータ転送が可能となる。また、ＣＰＵ１１１の主要な処理はソート処理に限定されるため、ホストコンピュータ１００のＣＰＵ１０１に比較して、性能の低いＣＰＵを使用することが可能であり、カード化が可能である。
【００７１】
次にディスプレイリストの構造およびディスプレイリスト管理手段４ａ及び座標点生成処理手段４ｂを実装する座標点生成ＬＳＩ１１６について詳細に説明する。
【００７２】
まず、文字／図形およびラスタデータの２つの場合のディスプレイリストの構造について説明する。図７はディスプレイリストの構成を示す図である。ＴｙｐｅＩＤが文字／図形の場合である。
【００７３】
ヘッダ部は、描画オブジェクトの種類を示すＴｙｐｅＩＤ（この場合、文字あるいは図形描画を示す）と、描画オブジェクトを何色で塗りつぶすかを示す色情報（例えば、ＣＭＹＢＫの値等）と、ｙバケットの総数であるｙリスト数と、各ｙリストに連結されているセルの総数である連結セル数と、次の描画オブジェクトのディスプレイリストへのポインタとから構成される。
【００７４】
リスト手段は、ｙバケットと、連結セルとから構成される。ｙバケットは、入力された各描画オブジェクト毎のベクタデータの始点のｙ座標値に相当する走査ラインｙと、最初の連結セルへのポインタであるセルポインタからなる。ここで、連結セルの存在しないｙバケットは、リスト手段に登録しない。連結セルは、入力された各描画オブジェクト毎のベクタデータの始点のｘ座標値と、そのベクタデータの走査ライン当たりのｘの増分であるΔｘと、そのベクタデータと交差する走査ラインの数であるΔｙと、その走査ラインｙを始点とする異なるベクタデータが存在するか否かを示す連結フラグから構成される。
【００７５】
連結フラグは、次に連結セルが存在する場合は、フラグ‘１’を付加し、最後の連結セルである場合は、ＥＯＣ（Ｅｎｄ Ｏｆ Ｃｅｌｌ）を表すフラグ‘０’を付加する。
【００７６】
図８はディスプレイリストの構成を示す図である。ＴｙｐｅＩＤがラスタの場合である。ヘッダ手段は、ＴｙｐｅＩＤ（この場合、ラスタ描画を示す）と、ラスタデータのデータサイズ（１画素当たりのビット数＊ｗ＊ｈ）と、ラスタデータの格納されているラスタデータバッファ３ｂ−１のアドレスに相当するデータアドレスと、各ｙリストに連結されているセルの総数である連結セル数と、次の描画オブジェクトのディスプレイリストへのポインタとから構成される。リスト部は、上述した文字／図形の場合と同様であるので説明を省略する。
【００７７】
次に座標点生成ＬＳＩ１１６について説明する。図９は座標点生成ＬＳＩ１１６の構成を示すブロック図である。
座標点生成ＬＳＩ１１６は、管理回路１１６ａと、４つの座標点生成回路Ａ〜Ｄ１１６ｂとから構成される。また、座標点生成ＬＳＩ１１６は、内部バス１２２に接続されているメモリコントローラ１１４を介してメモリ１１５にアクセスする構成になっている。
【００７８】
図１０は管理回路１１６ａが管理する内部レジスタの一覧を示す図である。管理回路１１６ａは、表１１６ａ−１に示す複数の内部レジスタを有し、現在処理中の走査ライン情報の管理、ディスプレイリストバンドバッファ３ａ−２およびエッジリストバッファ９へのアクセスの制御、ディスプレイリストデータのデコード処理、座標点生成回路１１６ｂの状態管理などの機能を備えるものである。
【００７９】
座標点生成回路Ａ〜Ｄは、管理回路１１６ａから１組ずつセルデータを入力し、各座標点生成回路Ａ〜Ｄ毎に非同期に最大４点のエッジデータを並列に生成する機能を備えるものである。４つの座標点生成回路Ａ〜Ｄは、全て同一の構造を持つ。
【００８０】
図１１は座標点生成回路１１６ｂのブロック構成示す図である。座標点生成回路１１６ｂは、ｘ座標値を保持するＸレジスタ１１６ｂ−０と、エッジの傾きを保持するΔＸレジスタ１１６ｂ−１、交差数を保持するΔＹレジスタ１１６ｂ−２と、Ｘレジスタ１１６ｂ−０およびΔＸレジスタ１１６ｂ−１の値を加算する加算器１１６ｂ−３と、ΔＹレジスタ１１６ｂ−２の値をデクリメントする演算器１１６ｂ−４と、２つのマルチプレクサ１１６ｂ−５および１１６ｂ−６と、実数値を整数値へ変換する整数変換器１１６ｂ−７と、ΔＹレジスタ１１６ｂ−２の値を０と比較する比較器１１６ｂ−８とから構成される。
【００８１】
入力Ｘ、ΔＸ、ΔＹは、対応する各レジスタの初期値であり、管理回路１１６ａから入力される。入力ＸＳＥＬ、ΔＹＳＥＬは、それぞれマルチプレクサ１１６ｂ−５および１１６ｂ−６の出力値の切り替え制御信号、入力ＸＬＤ、ΔＸＬＤ、ΔＹＬＤは、レジスタ１１６ｂ−０〜１１６ｂ−２の書き込み制御信号であり、管理回路１１６ａから入力される。
【００８２】
出力ＣＵＲＸは、管理回路１１６ａのカレントｘレジスタＣＵＲＸｉへ出力される。出力ＥＮＤは、エッジの終了を管理回路１１６ａに通知するための制御信号である。
【００８３】
図１２はエッジリストバッファ９の構成とエッジリストのデータ形式を示す図である。エッジリストデータは、オブジェクトの色情報と最初に現れるエッジのｙ座標値ｙｓｔａｒｔとから成るヘッダ部と、エッジと各走査ラインとの交点の座標値を含むエッジリスト部とから構成される。
【００８４】
エッジリストバッファ９は、エッジリストデータのヘッダ部を格納する領域と、エッジリスト部を格納する領域とから構成される。
エッジリストバッファ９のヘッダ部格納領域の先頭アドレスｅｌｈｄａｄｒと、エッジリスト部格納領域の先頭アドレスｙａｄｒ０は、座標点生成ＬＳＩ１１６の起動時に管理回路１１６ａのＥＬヘッダアドレスレジスタＥＬＨＤＡＤＲおよびＥＬトップアドレスレジスタＥＬＴＯＰＡＤＲにそれぞれ書き込まれる。
【００８５】
エッジリストバッファ９のエッジリスト部格納領域は、１バンドの全ての走査ラインに対してそれぞれＭ個のｘ座標値を格納することができる。
各走査ラインのエッジリストの先頭には、そのラインにいくつのｘ座標値が格納されているかを表すエッジデータ数Ｐｉが格納される。１走査ラインに格納可能なｘ座標値の最大数Ｍの値は、２５６以上の２のべき乗数が望ましい。
【００８６】
次に図１３〜１６を用いて、座標点生成ＬＳＩ１１６の１オブジェクトの座標点生成処理の流れを説明する。図１３は１オブジェクトの座標点生成処理の流れを示すフローチャートである。
〔Ｓ２０〕座標点生成ＬＳＩ１１６は、ＣＰＵ１１１から座標点生成処理開始の通知を受け取ると、ディスプレイリストデータのヘッダ部を処理するためにステップＳ２１に移る。
〔Ｓ２１〕管理回路１１６ａがメモリコントローラ１１４へディスプレイリストバンドバッファ３ａ−２へのリードアクセス要求を出す。アクセスが許可されると、管理回路１１６ａはＤＬ（ディスプレイリスト）ヘッダアドレスレジスタＤＬＨＤＡＤＲに保持しているアドレスをメモリコントローラ１１４へ出力し、該当アドレスからヘッダ部のデータを読み出して、一旦フェッチレジスタＦＥＴＣＨに格納する。
【００８７】
また、ステップＳ２２のｙリスト処理に備えて、ＤＬヘッダアドレスレジスタＤＬＨＤＡＤＲに保持しているアドレスとヘッダサイズからディスプレイリストバンドバッファ３ａ−２のｙリスト部の先頭アドレスを算出し、その値をｙリストアドレスレジスタＹＬＩＳＴＡＤＲにセットする。
【００８８】
オブジェクトが文字または図形の場合には、フェッチレジスタＦＥＴＣＨ内のヘッダ情報が、色情報とセル数と次ヘッダ部アドレスにデコードされて、それぞれカラーレジスタＣＯＬＯＲ、セルカウンタレジスタＮＵＭＣＥＬＬ、ＤＬヘッダアドレスレジスタＤＬＨＤＡＤＲに格納される。
【００８９】
オブジェクトがラスタの場合には、フェッチレジスタＦＥＴＣＨ内のヘッダ情報が、ラスタデータバッファアドレスとラスタデータサイズとセル数と次ヘッダ部アドレスにデコードされる。
【００９０】
管理回路１１６ａは、デコードしたラスタデータバッファアドレスとラスタデータサイズを印刷画像データ変換ＬＳＩ１１７に出力し、該当ラスタデータをホストコンピュータ１００のラスタデータバッファ３ｂ−１からラスタデータバンドバッファ７へ転送するよう指示する。
【００９１】
デコードしたセル数と次ヘッダ部アドレスは、それぞれセルカウンタレジスタＮＵＭＣＥＬＬ、ＤＬヘッダアドレスレジスタＤＬＨＤＡＤＲに格納する。
一方、ステップＳ２１でバンドの終了が検出された場合（ＮＵＭＣＥＬＬ＝０の場合）は、以降の処理を中断してバンドの終了をＣＰＵ１１１に通知し、次のバンドの処理に備えてＤＬヘッダアドレスレジスタＤＬＨＤＡＤＲをリセットして、座標点生成ＬＳＩ１１６はアイドル状態になる。
〔Ｓ２２〕ｙリストの読み込みとデコードを行う。まず管理回路１１６ａがメモリコントローラ１１４へディスプレイリストバンドバッファ３ａ−２へのリードアクセス要求を出す。
【００９２】
アクセスが許可されると、管理回路１１６ａはｙリストアドレスレジスタＹＬＩＳＴＡＤＲに保持しているアドレスをメモリコントローラ１１４へ出力し、該当アドレスからｙバケットデータを読み出して、一旦フェッチレジスタＦＥＴＣＨに格納する。
【００９３】
続いて、フェッチレジスタＦＥＴＣＨ内のｙバケットデータは、ｙバケットレジスタＹＢＵＣＫＥＴにコピーされ、ｙリストアドレスレジスタＹＬＩＳＴＡＤＲがインクリメントされる。最初のｙバケットを読み込んだ時のみ、そのｙ座標値がスタートｙレジスタＳＴＡＲＴＹに格納される。
〔Ｓ２３〕セルの読み込みとデコードを行い、座標点生成回路１１６ｂの内部レジスタを初期設定する。なお、ステップＳ２３は図１４を用いて後述する。
〔Ｓ２４〕セルカウンタレジスタＮＵＭＣＥＬＬの値がチェックされ、ＮＵＭＣＥＬＬ＝０ならばステップＳ２６へ進み、ＮＵＭＣＥＬＬ＞０ならばステップＳ２５へ進む。
〔Ｓ２５〕再びアイドルカウンタレジスタＮＵＭＩＤＬＥの値をチェックして、待機状態の座標点生成回路１１６ｂの有無を調べる。これは、後述する図１４のステップＳ３２でセルポインタ部の値がｎｕｌｌで、ステップＳ２３を終了した場合には、ステップＳ３３のチェックを通らないために、ここで再びＮＵＭＩＤＬＥの値をチェックしてさらにセルデータをセットできる座標点生成回路１１６ｂがないか調べるためのものである。
【００９４】
ＮＵＭＩＤＬＥ＝０の場合は、全ての座標点生成回路１１６ｂが処理状態にあるので、ステップＳ２６に進んで座標点生成を行う。
ＮＵＭＩＤＬＥ＞０の場合は、待機状態の座標点生成回路１１６ｂが存在し、かつ現在処理しているｙバケットにはセルが連結されていないので、待機状態の座標点生成回路１１６ｂに次のｙリストに連結されているセルデータを入力するために、ステップＳ２２に戻って次のｙリストの読み込みを行う。
〔Ｓ２６〕ステップＳ２３からステップＳ２５で全ての座標点生成回路１１６ｂにセルデータが設定されるか、あるいは全てのセルデータが座標点生成回路１１６ｂに設定されると、ステップＳ２６で実際に座標点の生成と出力が行われる。ステップＳ２６の処理の流れは図１５で後述する。
〔Ｓ２７〕セルカウンタレジスタＮＵＭＣＥＬＬの値がチェックされ、ＮＵＭＣＥＬＬ＞０ならばステップＳ２８へ進み、ＮＵＭＣＥＬＬ＝０ならばステップＳ２９へ進む。
〔Ｓ２８〕ｙバケットレジスタＹＢＵＣＫＥＴに格納されているセルポインタの値がチェックされる。もしセルポインタの値がｎｕｌｌならばステップＳ２２へ戻り、ｎｕｌｌ以外ならばステップＳ２３へ戻る。
〔Ｓ２９〕オブジェクトのヘッダ情報をエッジリストバッファ９へ書き込み、一連の座標点生成処理を終了する。まず管理回路１１６ａがメモリコントローラ１１４へエッジリストバッファ９へのライトアクセス要求を出す。
【００９５】
アクセスが許可されると、管理回路１１６ａはエッジリストヘッダアドレスレジスタＥＬＨＤＡＤＲに保持しているアドレスをメモリコントローラ１１４へ出力し、該当アドレスにカラーレジスタＣＯＬＯＲとスタートｙレジスタＳＴＡＲＴＹの値を書き込む。
【００９６】
そして、１オブジェクト分の座標点生成処理が終了したことをＣＰＵ１１１に通知して、座標点生成ＬＳＩ１１６はアイドル状態になる。
次にステップＳ２３について説明する。図１４はセルの入力とレジスタ設定処理の流れを示すフローチャートである。
〔Ｓ３０〕管理回路１１６ａがメモリコントローラ１１４へディスプレイリストバンドバッファ３ａ−２へのリードアクセス要求を出す。アクセスが許可されると、管理回路１１６ａはｙバケットレジスタＹＢＵＣＫＥＴのセルポインタ部に保持しているアドレスをメモリコントローラ１１４へ出力し、該当アドレスからセルデータを読み出して、一旦フェッチレジスタＦＥＴＣＨに格納する。
〔Ｓ３１〕フェッチレジスタＦＥＴＣＨ内のセルデータをデコードして、待機状態の座標点生成回路１１６ｂの内部レジスタにセットする。まずステータスレジスタＳＴＡＴＵＳの値をチェックし、待機状態の座標点生成回路１１６ｂを検出する。
【００９７】
次に検出された座標点生成回路１１６ｂにセルデータからデコードしたｘ座標値とエッジの傾きΔｘと交差数Δｙを入力し、それぞれＸレジスタ１１６ｂ−０、ΔＸレジスタ１１６ｂ−１、ΔＹレジスタ１１６ｂ−２へ格納する。
【００９８】
ステータスレジスタＳＴＡＴＵＳの検出された座標点生成回路１１６ｂの待機状態を表すビットは、処理中を表す‘０’に変更され、アイドルカウンタレジスタＮＵＭＩＤＬＥはデクリメントされる。
【００９９】
セルデータからデコードされたｘ座標値は、始点を出力するためにカレントｘレジスタＣＵＲＸｉにもコピーされる。次に、セルデータの連結フラグ部をデコードし、その値が継続を表す‘１’ならばｙバケットレジスタＹＢＵＣＫＥＴのセルポインタ部をインクリメントし、連結フラグの値が‘０’（ＥＯＣ）ならばｙバケットレジスタＹＢＵＣＫＥＴのセルポインタ部にｎｕｌｌ値をセットする。
【０１００】
さらに、セルカウンタレジスタＮＵＭＣＥＬＬをデクリメントし、セルデータをセットした座標点生成回路１１６ｂに対応するカレントｙレジスタＣＵＲＹｉにｙバケットレジスタＹＢＵＣＫＥＴに格納しているｙ座標値をコピーする。
〔Ｓ３２〕現在処理しているｙバケットにセルリストが連結されているか否かを調べる。もしｙバケットレジスタＹＢＵＣＫＥＴのセルポインタ部の値がｎｕｌｌならば、現在処理しているｙバケットにはセルが連結されていないので、図１３のステップＳ２３を終了してステップＳ２４に進む。
【０１０１】
ｎｕｌｌでない場合は、セルリストが連結されているのでステップＳ３３に進んで、再びセルを入力するかどうかを決定する。
〔Ｓ３３〕アイドルカウンタレジスタＮＵＭＩＤＬＥの値をチェックして、待機状態の座標点生成回路１１６ｂの有無を調べる。ＮＵＭＩＤＬＥ＝０の場合は、全ての座標点生成回路１１６ｂが処理状態にあるので、ステップＳ２３を終了してステップＳ２５に進む。
【０１０２】
ＮＵＭＩＤＬＥ＞０の場合は、待機状態の座標点生成回路１１６ｂが存在するので、ステップＳ３０に戻って次のセルデータを読み込み、図１３のステップＳ２３の処理を繰り返す。
【０１０３】
次にステップＳ２６について説明する。図１５は座標点生成と出力の流れを示すフローチャートである。
〔Ｓ４０〕エッジの始点の座標値をエッジリストバッファ９へ出力する。ステップＳ４０の処理の詳細は図１６で説明する。
〔Ｓ４１〕次の走査ラインとエッジの交点の座標値を計算する。まず、各カレントｙレジスタＣＵＲＹｉの値がそれぞれインクリメントされる。次に、処理状態にある座標点生成回路１１６ｂのＸレジスタ１１６ｂ−０とΔＹレジスタ１１６ｂ−２の値が、以下に示す式（１ａ）、（１ｂ）にしたがって、並列に更新される。
【０１０４】
【数１】
Ｘ＝Ｘ＋ΔＸ …（１ａ）
ΔＹ＝ΔＹ−１ …（１ｂ）
最後に、更新されたＸレジスタ１１６ｂ−０の値が、整数変換器１１６ｂ−７によって整数化されてカレントｘレジスタＣＵＲＸｉへ格納される。
〔Ｓ４２〕ステップＳ４１で計算された座標値をエッジリストバッファ９へ出力する。ステップＳ４２の処理の詳細は図１６で説明する。
〔Ｓ４３〕エッジの終点を出力した座標点生成回路１１６ｂを検出して、待機状態にする処理を行う。エッジの終点を出力し、ΔＹレジスタ１１６ｂ−２の値が‘０’になった座標点生成回路１１６ｂは、ＥＮＤ＝‘１’を出力する。
【０１０５】
管理回路１１６ａでは、アクティブになったＥＮＤ信号を検出し、ステータスレジスタＳＴＡＴＵＳの該当する座標点生成回路１１６ｂの状態を表すビットを、待機中を表す‘１’に変更する。またアイドルカウンタレジスタＮＵＭＩＤＬＥに、検出された座標点生成回路１１６ｂの個数を加算する。
〔Ｓ４４〕全ての座標点生成回路１１６ｂが処理中か否かを調べる。アイドルカウンタレジスタＮＵＭＩＤＬＥの値が０に等しければ、座標点生成回路Ａ〜Ｄは全て処理状態にあるので、ステップＳ４１に戻り、各々次の走査ラインの座標点生成と出力を繰り返す。
【０１０６】
ＮＵＭＩＤＬＥ＞０ならば、待機中の座標点生成回路１１６ｂが存在するので、ステップＳ４５に進む。
〔Ｓ４５〕セルカウンタレジスタＮＵＭＣＥＬＬの値がチェックされ、ＮＵＭＣＥＬＬ＝０ならば新たにセットするセルデータは存在しないので、現在の処理を継続するためにステップＳ４１に戻り、各々次の走査ラインの座標点生成と出力を繰り返す。
【０１０７】
ＮＵＭＣＥＬＬ＞０ならば待機中の座標点生成回路１１６ｂが存在し、さらに未処理のセルデータが存在するので、図１３のステップＳ２６を終了してステップＳ２７へ進む。
【０１０８】
次にステップＳ４０、４２について説明する。図１６は座標点出力処理の流れを示すフローチャートである。
〔Ｓ５０〕管理回路１１６ａは、メモリコントローラ１１４へエッジリストバッファ９へのアクセス要求を出し、並行してアクセス先のアドレスを計算する。
【０１０９】
現在処理中の走査ラインに対応するエッジデータ数が格納されているエッジリストバッファアドレスは、カレントｙレジスタＣＵＲＹｉの値を用いて、
【０１１０】
【数２】
ＥＬＴＯＰＡＤＲ＋Ｂ＊Ｍ＊ＣＵＲＹｉ …（２）
により計算され、エッジリストバッファアドレスレジスタＥＬＢＡＤＲに格納される。式（２）において、ＥＬＴＯＰＡＤＲはエッジリストバッファ９のエッジリスト部の先頭アドレスが格納されているＥＬトップアドレスレジスタＥＬＴＯＰＡＤＲの値を表し、Ｂは１つのｘ座標値を表現するために必要なバイト数を表す。ＢとＭが共に２のべき乗数である場合は、式（２）はハードウェアにより１クロックサイクルで計算される。さらに、メモリライトカウンタレジスタＣＮＴＭＥＭＷに（４−ＮＵＭＩＤＬＥ）の値をセットする。
〔Ｓ５１〕メモリコントローラ１１４によりエッジリストバッファ９へのアクセスが許可されると、管理回路１１６ａはステップＳ５０で計算したアドレスをメモリコントローラ１１４へ出力し、該当アドレスからエッジデータ数を読み込んで、一旦フェッチレジスタＦＥＴＣＨに格納する。
〔Ｓ５２〕フェッチレジスタＦＥＴＣＨ内のエッジデータ数をインクリメントし、結果をエッジリストバッファ９の読み込んだ時と同一のアドレスへ書き込む。
〔Ｓ５３〕エッジリストバッファアドレスレジスタＥＬＢＡＤＲに、フェッチレジスタＦＥＴＣＨ内のエッジデータ数にＢを乗じた値を加える。
【０１１１】
続いて、このアドレスへカレントｘレジスタＣＵＲＸｉの値を書き込む。そして、メモリライトカウンタレジスタＣＮＴＭＥＭＷの値をデクリメントする。
〔Ｓ５４〕メモリライトカウンタレジスタＣＮＴＭＥＭＷの値をチェックし、ＣＮＴＭＥＭＷ＞０ならばステップＳ５０に戻り、他の座標点生成回路１１６ｂより生成された座標点の出力処理を行う。
【０１１２】
ＣＮＴＭＥＭＷ＝０ならば、現在処理中の座標点生成回路１１６ｂから生成された座標点は全てエッジリストバッファに書き込まれたので、図１５のステップＳ４０あるいはステップＳ４２の座標点出力の処理は終了する。
【０１１３】
次にソート手段５について詳細に説明する。図１７はソート処理の詳細を示すフローチャートである。
〔Ｓ６０〕エッジリストバッファ９のアドレスｅｌｈｄａｄｒに格納されているヘッダ情報を読み込む。
〔Ｓ６１〕ヘッダ情報中のｙｓｔａｒｔの値により、最初に読み込むエッジリストバッファアドレスｙａｄｒを設定する。
〔Ｓ６２〕エッジリストバッファアドレスｙａｄｒから、エッジデータ数Ｐｉを読み込む。
〔Ｓ６３〕読み込んだエッジデータ数Ｐｉが、０か否かを判定する。０の場合は、現在のエッジリストバッファアドレスｙａｄｒが示すバッファも含めて、それ以降のエッジリストバッファ中には、エッジデータは存在しないので、ソート処理を終了する。０でない場合は、エッジデータが存在するのでステップＳ６４に処理を移す。
〔Ｓ６４〕読み込んだエッジデータ数Ｐｉと設定値との大小判定を行う。本実施の形態では、設定値＝１である。エッジデータ数Ｐｉが設定値以下であった場合、現在のエッジリストバッファアドレスｙａｄｒが示すバッファ中のエッジデータのソートは必要ないので、ステップＳ６６に処理を移す。
【０１１４】
エッジデータ数が設定値より大きい場合は、現在のエッジリストバッファアドレスｙａｄｒが示すバッファ中のエッジデータのソートが必要なので、処理をステップＳ６５に移す。
〔Ｓ６５〕現在のエッジリストバッファアドレスｙａｄｒが示すバッファ中に存在するエッジデータを、値の小さい順にソートする。詳細は図１８で後述する。
〔Ｓ６６〕エッジリストバッファアドレスｙａｄｒを次の走査ラインに対応するアドレスに設定する。
〔Ｓ６７〕アドレスがエッジリストバッファ領域を超えたかどうかを判定し、超えていない場合は、ステップＳ６２に処理を移して繰り返しソート処理を行う。超えた場合は、ソート処理を終了する。
【０１１５】
次にステップＳ６５について説明する。図１８はソート手段５のソート方法を示す概念図である。
まず、入力されたｎ個のエッジデータのうち、ｎ／２番目のエッジデータ値ｘに着目する。次に全エッジデータに対して、エッジデータ値ｘよりも小さいか否かにより、それぞれのエッジデータをエッジデータ値ｘ以下（１〜ｉ）のものと、エッジデータ値ｘ以上（ｊ〜ｎ）であるものとに振り分ける。
【０１１６】
１〜ｉまでのエッジデータおよびｊ〜ｎまでのエッジデータそれぞれに対して、上記で述べた方法を、全てのエッジデータが値の小さい順にソートされるまで再帰的に繰り返す。上記の方法により、順不同で入力されたエッジデータをソートすることが可能となる。
【０１１７】
図１９はソート手段５のブロック構成を示す図である。ソート手段５は、エッジリストバッファ９からエッジデータを入力するエッジデータ入力手段５ａと、入力したエッジデータを一時的に蓄えるソートバッファ５ｂと、最終的にソートされたエッジデータをソートバッファ５ｂからエッジリストバッファ９へ出力するエッジデータ出力手段５ｃと、ソートすべきエッジデータ数の設定などのソート処理全体を管理するソート処理管理手段５ｄと、（エッジデータ数／２）番目の値を選択する中点値選択部５ｅと、（エッジデータ数／２）番目の値とエッジデータ値の大小比較を行うエッジデータ判定手段５ｆと、エッジデータ判定手段５ｆの比較結果に従い、エッジデータを振り分けるエッジデータ分別手段５ｇと、から構成される。
【０１１８】
次にソート手段５の処理手順をフローチャートで説明する。図２０はソート手段５の処理手順を示すフローチャートである。まず、エッジデータ入力手段５ａで入力されたエッジデータは、まずソートバッファ５ｂに蓄えられる。
〔Ｓ７０〕ソート処理管理手段５ｄにより、エッジデータの個数ｎが算出される。ただし、１回目のソート処理の場合は、エッジリストバッファ９中のエッジデータ数の値をｎと設定する。またｆｉｒｓｔ値ｉ、ｌａｓｔ値ｊも設定する。
〔Ｓ７１〕中点値選択手段５ｅにより、（ｎ／２）番目の値ｘを選択する。
〔Ｓ７２、７３〕エッジデータ判定手段５ｆにより、値ｘとソートバッファ５ｂ中のエッジデータの大小比較を行う。
〔Ｓ７４〕エッジデータ判定手段５ｆで、振り分けが必要と判定されたエッジデータに対して、エッジデータ分別手段５ｇにより、エッジデータの振り分けを行い、振り分けた結果をソートバッファ５ｂに出力する。
〔Ｓ７５〕ソート処理管理手段５ｄにより、ソートバッファ５ｂ中の全エッジデータに対して、値ｘとの大小比較が完了したか判定し、完了していない場合は、ステップＳ７２からステップＳ７４の処理を繰り返す。値ｘとの大小比較がすべて完了している場合は次のステップに処理を移す。
〔Ｓ７６、７７〕ソート処理管理手段５ｄにより、値ｘにより振り分けられた１〜ｉまでのエッジデータおよびｊ〜ｎまでのエッジデータそれぞれに対して、ステップＳ７０からステップＳ７５の処理を繰り返し行うよう管理する。
【０１１９】
すべてのエッジデータがｘの値の小さい順にソートされるまで、ステップＳ７０からステップＳ７７までの処理を繰り返す。
上記の処理がすべて終了し、ソートバッファ５ｂ中の全エッジデータがソートされると、エッジデータ出力手段５ｃは、エッジリストバッファ９にソートバッファ５ｂ中のエッジデータを出力する。
【０１２０】
以上説明したように本発明に印刷処理装置１０では、所定の描画命令で記述されている印刷データを、ディスプレイリストに変換し、ディスプレイリストからビットマップ展開する印刷処理装置のエッジリストデータ生成処理において、描画オブジェクトのエッジを表す座標点を生成する座標点生成処理と、前記座標点に順序を付けるソート処理を分離し、複数の座標点生成装置を待機状態の座標点生成装置が発生しないよう管理しながら非同期で繰り返し座標点生成した後、ソート処理を行うよう構成した。このため、それぞれの処理に適した処理資源、即ち座標点生成処理はハードウェア、ソート処理はソフトウェアで処理することが可能となり、かつ有限の資源を有効に活用しながら記述言語で記述される複雑な描画オブジェクトに対しても軽い資源で高速の処理を行うことが可能になる。 次に本発明の印刷処理方法について説明する。図２１は本発明の印刷処理方法の処理手順を示すフローチャートである。
〔Ｓ８０〕少なくとも文字または図形のいずれかの描画オブジェクトを有し、描画命令で記述されている印刷データを解釈して、内部命令に変換する。
〔Ｓ８１〕内部命令から描画オブジェクトの輪郭を構成するエッジのエッジ情報をエッジ毎に有したディスプレイリストを走査ライン毎に生成する。
〔Ｓ８２〕ディスプレイリストのエッジ情報を用いて描画オブジェクトのエッジを表す座標点を順次非同期に生成する。
〔Ｓ８３〕座標点に順番を付けるソートを行う。
〔Ｓ８４〕順番にしたがって整列させた座標点にもとづいて、印刷データを印刷出力可能な印刷画像データに変換する。
〔Ｓ８５〕印刷画像データの出力処理を行う。
【０１２１】
以上説明したように、本発明の印刷処理方法は、ディスプレイリストのエッジ情報を用いて描画オブジェクトのエッジを表す座標点を順次非同期に生成するものとした。これにより、高速に印刷処理を行うことが可能になる。
【０１２２】
【発明の効果】
以上説明したように、本発明の印刷処理装置は、ディスプレイリストのエッジ情報を用いて描画オブジェクトのエッジを表す座標点を順次非同期に生成する構成とした。これにより、高速に印刷処理を行うことが可能になる。
【０１２３】
また、本発明の印刷処理方法は、ディスプレイリストのエッジ情報を用いて描画オブジェクトのエッジを表す座標点を順次非同期に生成するものとした。これにより、高速に印刷処理を行うことが可能になる。
【図面の簡単な説明】
【図１】本発明の印刷処理装置の原理図である。
【図２】本発明の印刷処理装置の詳細構成を示す図である。
【図３】印刷処理の流れの概要を示すフローチャートである。
【図４】印刷処理の流れの概要を示すフローチャートである。
【図５】印刷処理装置のハードウェアの構成を示す図である。
【図６】描画処理カードのハードウェアの構成例を示す図である。
【図７】ディスプレイリストの構成を示す図である。
【図８】ディスプレイリストの構成を示す図である。
【図９】座標点生成ＬＳＩの構成を示すブロック図である。
【図１０】管理回路が管理する内部レジスタの一覧を示す図である。
【図１１】座標点生成回路のブロック構成を示す図である。
【図１２】エッジリストバッファの構成とエッジリストのデータ形式を示す図である。
【図１３】１オブジェクトの座標点生成処理の流れを示すフローチャートである。
【図１４】セルの入力とレジスタ設定処理の流れを示すフローチャートである。
【図１５】座標点生成と出力の流れを示すフローチャートである。
【図１６】座標点出力の処理の流れを示すフローチャートである。
【図１７】ソート処理の詳細を示すフローチャートである。
【図１８】ソート手段のソート方法を示す概念図である。
【図１９】ソート手段のブロック構成を示す図である。
【図２０】ソート手段の処理手順を示すフローチャートである。
【図２１】本発明の印刷処理方法の処理手順を示すフローチャートである。
【図２２】ディスプレイリストからビットマップ展開のためのエッジの座標点を生成する処理の流れを示す図である。
【図２３】ディスプレイリストからビットマップ展開のためのエッジの座標点を生成する処理の流れを示す図である。
【符号の説明】
１ 印刷データ
２ 印刷データ解釈手段
３ ディスプレイリスト生成手段
４ 座標点生成手段
５ ソート手段
６ 印刷画像データ変換手段
８ 印刷出力手段
１０ 印刷処理装置
２０ プリンタ装置

Claims (8)

1. 描画命令をビットマップ展開して印刷処理する印刷処理装置において、
   少なくとも文字又は図形のいずれかの描画オブジェクトを有し、前記描画命令で記述されている印刷データを解釈して、内部命令に変換する印刷データ解釈手段と、
   前記内部命令から前記描画オブジェクトの輪郭を構成するエッジのエッジ情報を前記エッジ毎に有したディスプレイリストを走査ライン毎に生成するディスプレイリスト生成手段と、
   前記ディスプレイリストの前記エッジ情報を用いて、前記描画オブジェクトの前記エッジを表す複数の座標点を順次非同期に生成する座標点生成手段と、
   前記座標点に順番を付けるソート手段と、
   前記順番にしたがって整列させた前記座標点にもとづいて、前記印刷データを印刷出力可能な印刷画像データに変換する印刷画像データ変換手段と、
   前記印刷画像データの出力処理を行う印刷出力手段と、
   を有することを特徴とする印刷処理装置。
2. 前記座標点生成手段は、複数で構成され、前記座標点生成手段の数と同数の前記座標点を一度に生成することを特徴とする請求項１記載の印刷処理装置。
3. 前記座標点生成手段は、座標点生成処理が終了すると直ちに、他の未処理のエッジの座標点生成処理を開始することを特徴とする請求項１記載の印刷処理装置。
4. 前記描画オブジェクトの全ての前記座標点の生成が終了するまで、前記ディスプレイリストを前記座標点生成手段に繰り返し転送する管理手段を有することを特徴とする請求項１記載の印刷処理装置。
5. 前記管理手段は、前記座標点生成手段が待機中にあることを検出する検出手段と、検出された前記座標点生成手段へ前記ディスプレイリストの前記エッジ情報を転送する転送手段と、を有することを特徴とする請求項４記載の印刷処理装置。
6. 前記管理手段は、前記検出手段が待機中にある前記座標点生成手段を検出すると、直ちに前記転送手段により次に転送すべき前記エッジ情報を待機状態にある前記座標点生成手段に転送することを特徴とする請求項５記載の印刷処理装置。
7. 前記転送手段は、前記座標点の生成により特定の前記エッジの交差数が０になった場合に座標点生成処理が終了したものとして、前記座標点生成手段へ前記エッジ情報を転送することを特徴とする請求項５記載の印刷処理装置。
8. 描画命令をビットマップ展開して印刷処理する印刷処理方法において、
   少なくとも文字又は図形のいずれかの描画オブジェクトを有し、前記描画命令で記述されている印刷データを解釈して、内部命令に変換し、
   前記内部命令から前記描画オブジェクトの輪郭を構成するエッジのエッジ情報を前記エッジ毎に有したディスプレイリストを走査ライン毎に生成し、
   前記ディスプレイリストの前記エッジ情報を用いて、前記描画オブジェクトの前記エッジを表す座標点を順次非同期に生成し、
   前記座標点に順番を付けるソートを行い、
   前記順番にしたがって整列させた前記座標点にもとづいて、前記印刷データを印刷出力可能な印刷画像データに変換し、
   前記印刷画像データの出力処理を行うことを特徴とする印刷処理方法。

Images