JPH0810465B2 - ラスタ生成方法および装置 - Google Patents

Description

【発明の詳細な説明】 A.産業上の利用分野 本発明はラスタ生成に関し、特に印刷や他のバッチ型
ラスタ生成アプリケーションに用いる、パラレル・プロ
セッサによるラスタ生成に関する。

B.従来の技術 タイプライタのようなプリンタ（形状が決められ個数
が一定の文字の位置づけがページ上の特定の位置に限ら
れる）から、画素あるいはピクセルと呼ばれる数百万個
の細かいドットでページが構成され、全点をアドレスで
きる（APA）印刷装置に変わり、複雑なドキュメントを
コンピュータ印刷する道が開かれた。複雑なページの内
容を指定するプロセスを簡素化するために登場したペー
ジ記述言語は、ページの内容を構成する数百万個のピク
セルのそれぞれの濃さ（色）を判定するのに、かなりの
処理を必要とする。高速プリンタは急速に発展し、ペー
ジ内容の判定に利用できる処理能力を上回るほどにな
り、処理のボトルネックが生じている。本発明はこのボ
ルトネックを対象にする。

印刷プロセスは、ページ内容の指定をページ記述言語
（PDL）で生成するドキュメント・フォーマッタなどの
アプリケーション・プログラムから始まる。PDLで記述
されたページ内容はデータストリームと呼ばれる。デー
タストリームに加えられるPDLコマンドの例を以下に示
す。

「半径8cm（３インチ）の円を、ページの左マージン
から13cm（５インチ）、ページの左マージンから10cm
（４インチ）のところを中心にして描き、その円をマジ
ェンタで塗りつぶす」 「ページの上マージンから9.5cm（3.75インチ）、ペ
ージの左マージンから2.5cm（１インチ）のところを起
点にして、大きさ12プリンタ・ポイントのTimes Roman
フォントを使って“Now is the time for all good"を
水平に書く」 データストリームが生成されると、印刷または表示の
ために、データストリームを数百万個の数値の集まりに
変換しなくてはならない。各数値はページ上の１ピクセ
ルの色を表す。数値の集まりはページマップと呼ばれ、
変換プロセスはラスタ生成と呼ばれる。

最終的なページマップまたはディスプレイ上でどのオ
ブジェクト（またはオブジェクトの一部）が目に見える
かの判定は、普通、２次元（2D）オブジェクトと３次元
（3D）オブジェクトでは異なる。3Dオブジェクトには２
次元の奥行きがあり、その可視性は、オブジェクト記述
の一部を成す奥行き情報によって決まる。奥行き情報は
オブジェクトに含まれるので、オブジェクトをラスタ化
しページマップに適用する順序は重要ではない。

2Dオブジェクトの場合、オブジェクトの可視性は、デ
ータストリームにおけるそのロケーションと“混合モー
ド”との組み合わせで決まるのが通常である。たとえば
“オーバペイント”混合モードでは、“後の”オブジェ
クトは常に“先の”オブジェクトを隠す。一般的には、
混合モードでは、新しいオブジェクトによって色づけさ
れたピクセルの新しい値は常に、古い値と、新しいオブ
ジェクトによって与えられたピクセル色の規定関数であ
る。しかしこれを正しく処理するためには、同じピクセ
ルに影響を与える異なるオブジェクトが、それらがデー
タストリームに現れるのと同じ順序で処理されなくては
ならない。混合モードを用いて可視性を判定する際に
は、第３の“奥行き”次元の特性が２次元オブジェクト
のラスタ生成に加わる。そのためこのようなラスタ生成
はよく“2Dラスタ生成”と呼ばれる。

全点アドレス可能な（APA）印刷に“高機能"PDLが併
用され、ページのラスタ生成に必要な処理の量が大幅に
増加している。文字（キャラクタ）が、外形を表わすカ
ーブによって記述されたフォントの処理には、ラスタラ
イザが必要になることがある。キャラクタは、任意のサ
イズに拡大／縮小し、任意の角度に回転させる必要があ
る。ラスタライザはまた、グラフィカル・オブジェクト
のスケーリング（拡大、縮小、引き伸ばし）、回転、ビ
ットマップへの変換、および、すでにビットマップに変
換されたイメージのスケーリングと回転に必要になるこ
とがある。さらに、オブジェクトの範囲を定める（クリ
ップする）のにマスクも用いられ、オーバラップしたオ
ブジェクトを配置した結果を指定するために様々な混合
モードも用いられる。こうしたPDLは、条件分岐など汎
用プログラミング言語の特徴も合わせ持ち、メインフレ
ームやパーソナル・コンピュータなどの汎用デジタル・
コンピュータに近い処理が必要になる。最近では、カラ
ープリンタが登場し、ラスタライザでの処理に対する需
要がさらに増加している。

ラスタライザを実現する最も簡単な方法は、１個のプ
ロセッサと併用することである。しかし、処理の高速化
が求められ、プロセッサおよびメモリなどの関連コンポ
ーネントのコストが急激に増加するなか、コスト・メリ
ットが得られる高速プリンタを開発するのは不可能にな
っている。高速プリンタにかけるページを作成するに
は、妥当なコストのマイクロプロセッサ以上の高速処理
と処理能力が必要である。ある速度を超えると、プロセ
ッサのコストは、その処理速度よりも早く増大する（す
なわち低速のプロセッサ５個は、速度が５倍のプロセッ
サ１個よりも廉価である）ので、シングル・プロセッサ
の高速ラスタライザでは引き合わない。

したがって、ラスタライザのコストを調整できるよう
にしておくためには、また段階的な拡張性など他の理由
からも、高価なプロセッサ１個を使用するよりも、低コ
ストのプロセッサ数個を協調させる方が望ましい。

マルチプロセッサのラスタライザを設計する場合、か
なり大きな問題に取り組まなくてはならない。設計上
は、全体的な処理速度を上げるために、相当なレベルの
パラレリズムを実現する必要がある。設計段階で、プロ
セッサによるオーバヘッドと負荷の重複を抑える必要が
ある。これらは、所定のページに対する処理量を増や
し、実効性能を抑えるからである。また、プロセッサを
使用してもその影響がページの内容になるべく及ばない
ように設計する必要がある。さらに、競走力をもたせる
ためには、所要メモリが、性能が同等なシングル・プロ
セッサのラスタライザよりも少ない設計が求められる。

これらの目標のほかにも満足すべき基本要件が２つあ
る。一つは、データストリーム環境（カーソル位置、ス
ケール・ファクタ、カレント・フォントなど）は、その
処理が他のセグメントと独立してすぐスタートするよう
に、各セグメントの先頭で利用できなくてはならない。
もう一つは、ページマップ上のセグメントの表現がオー
バラップしないようにしなくてはならない。オーバラッ
プすれば、セグメントを処理する順序とその表現を適用
する順序が、最終的な外観に影響を与えることがあるか
らである。

従来の技術には、マルチプロセッサによるラスタ生成
にいくつかのアプローチがとられる。“パイプライン型
ラスタライザ”では、ラスタ生成プロセスは、いくつか
のステージに分けられ、ステージごとに異なるプロセッ
サが実行され、その結果が、パイプラインに沿った次の
ステージを処理するプロセッサに引き渡されるように、
ステージの“パイプライン処理”が行われる。このよう
なラスタライザは、第１および第２の条件を両方とも満
足する。どのプロセッサもデータストリーム全体を正し
い順序で認識し、ページマップを更新するのは１個のプ
ロセッサだけだからである。このパイプライン方式は、
所要メモリの観点からも効率がよい。しかし、パラレリ
ズムのレベルは、パイプライン処理が可能なステージの
数（３または４以内）に制限される。さらに、パイプラ
インを成す各プロセッサの相対的な処理負荷は、ページ
内容によって変化し得る。その結果、パイプライン型ラ
スタライザの速度は普通、シングル・プロセッサのラス
タライザの２倍以上になることがない（高速化率は２よ
り小さいのが普通である）。

“ページ・パラレル”ラスタライザでは、処理される
ページはプロセッサによって異なる。この設計の場合、
普通、第１条件を満たすのは易しい。通常はページの先
頭で充分な情報が得られるからである。第２条件は、ペ
ージのオーバラップが（理論上は）存在しないので常に
クリアでき、高度なパラレリズムを実現できる。しか
し、大量のメモリが必要になり、１ページのラスタ生成
時間は短縮されない。また、ページ・ラスタ生成時間が
変化しやすいときは（単純なページと複雑なページが混
じっているときなど）、かなり大きなメモリを使用しな
い限り、プロセッサ利用率は大幅に低下する。ページは
ある決まった順序で印刷するから、ページ・パラレル・
ラスタライザに、最初に複雑なページがかかり、これに
単純なページが数ページ続くと、印刷エンジン（プリン
タ）は、１個を除く全プロセッサとともにアイドル状態
におかれ、複雑なページを処理するプロセッサが処理を
終えるまで待つことになる。

“機能的パラレリズム”を利用するラスタライザの場
合、タイプ（イメージ、テキスト、グラフィクスなど）
の異なる複数のブロックが個別にラスタ化され、その結
果がページマップに順次にマージされる。これは、ブロ
ックのタイプ数が限られるため、ごく平均的なパラレズ
ムを与えるだけである。さらに、所定のページで実際に
得られるパラレリズムは、異なるタイプに対する相対的
な処理負荷の影響を、よってページ内容の影響を受けや
すい。そしてラスタ生成の最後の段階（ブロックがペー
ジマップにマージされる）はパラレルにならない。

“ジオグラフィック・パラレリズム”を活用するラス
タライザの開発作業は、混合モードを“OR"に限定しな
い場合は成功していない。このようち限定すれば、重な
り合ったイメージは、どれがどれにオーバラップするか
を考慮せずにマージされる。ジオグラフィック・パラレ
リズムは、ページ内の異なる領域をパラレルに構成すれ
ばよいという直感が基になっている。しかし、第２の条
件を満たす必要性は、ラスタ生成プロセスの登場以来認
められており、これが、他の混合モードでの上記のアイ
デアの実現を妨げている。

“Ｚバッファを備えた3Dラスタライザ”の典型は、Pa
vicicによって提案された“スーパディスプレイ”であ
る。ここでは“オブジェクト・プロセッサ”が、ラスタ
“オブジェクト”を準備し、“イメージ・プロセッサ”
（スマート・メモリ）に送る。所定のロケーションから
のラスタ・オブジェクトはそれぞれ、そのロケーション
に対して指定されたイメージ・プロセッサに送られる。
オブジェクトは、ピクセルごとに強度値“I"と“z"値
（奥行き）を含む。イメージ・プロセッサは、（ｘ、
ｙ、ｚ、Ｉ）値をもつ新しいオブジェクトを受け取る
と、ｚ値をそれが現在保持している値と比較する。新し
いｚ値が古い値より大きい場合（新しいオブジェクトの
方が深い場合）、イメージ・プロセッサは、新しいエン
トリを棄却する。他の場合は古い値を新しい値に置き換
える。一部だけがカラー・ピクセルのオブジェクトを収
めるのに、値をいくつか維持するのは可能である。この
設計のＺバッファは、プリンタではなくディスプレイを
対象にしている。代表的なディスプレイ・ラスタライザ
では、独立した3Dオブジェクトのリストが、新しいオブ
ジェクトの追加や削除、古いオブジェクトの変更などを
含めて段階的に変化する。Ｚバッファは、ディスプレイ
（ページマップ）全体のバッチ型2Dラスタ生成にとって
はそれほど効率のよいものではない。イメージ・プロセ
ッサがピクセルを個別に更新し、2Dオブジェクトとオー
バペイント混合モード（オーダ・インプライド・デプス
ともいう）とでは、最後のオブジェクトが前のオブジェ
クトのすべてをカバーするという事実を利用していない
からである。混合モードがオーバペイントでなくても、
同じ動作が、影響を受けたピクセル全部に対して実行さ
れるもので、段階的更新は非効率である。うそのため、
ほとんどのAPAプリンタ・ラスタライザは、バッチ型ラ
スタ生成を行う。後続のページは、前に印刷されたペー
ジを更新したものではないからである。また、Ｚバッフ
ァは、深いオブジェクトを浅いオブジェクトでオーバペ
イントするという考え方に大きく傾き、得られる強度と
色が、過去のものと新しいものとの任意の関数である複
雑な処理には適さない。そのような処理は、ピクセルご
とに、過去の（ｚ、Ｉ）値のおそらくは無限のリストを
要するからであり、所定の奥行き範囲に対するラスタ生
成を完了させるという概念が欠けている。Ｚバッファ技
術には、状態に依存しないオブジェクトを発見すること
と、リソース準備（後述）の概念も欠けている。

“New Graphics Controller for Electrostatic Plot
ting",IEEE CG＆A,pp.16−25,January 1986、の中でA.B
en−DorとBrian Jones（Versatec）が説明している“ラ
スタ処理マシン”（RPM）は、完全なページマップを持
たない静電プロッタ用に開発されたものである。入力さ
れるグラフィック・オブジェクトは、内部フォーマット
に（並列にではなく）順次に変換される。このフッーマ
ットがボトルネックを生み、ラスタライザの性能が抑え
られる。変換されたオブジェクトは次に、ジオグラフィ
ック・ロケーションによって、マシンのラスタ・バッフ
ァのサイズ（ピクセルマップのバンド）に対応するビン
にソートされる。このプロセスが終わると、ビンが処理
され（おそらく並列に）、結果は対応する部分ピクセル
マップに置かれる。部分ピクセルマップはそこで組み合
わされ、データストリーム内のオブジェクトのシーケン
スは考慮されない。２つのオブジェクトがページ上で重
なりあっていると、それらは混合され印刷される。

C.発明の要旨 本発明は、少なくとも１出力イメージを指定するデー
タストリームをコンピュータ上でラスタ化する方法を含
む。第１ステップでは、データスラリーム内の状態独立
なブロックが識別される。これらのブロックは次に中間
形式のデータに並列に変換される。イメージの少なくと
も２つのジオグラフィカル領域に対する中間形式データ
は、少なくともイメージの一部を表すラスタ・ピクセル
マップに並列に変換される。この方法には、ピクセルマ
ップに組み込まれる、再利用可能な中間形式データ・リ
ソースを準備するパラレル・ステップを任意追加でき
る。

本発明はまた、少なくとも１出力イメージを指定する
データストリームをラスタ化する装置を含む。システム
には、データストリーム内の状態独立なブロックを識別
する手段と、ブロックを中間形式データに変換する少な
くとも２つのパラレル処理手段が含まれる。また、中間
形式データを、イメージの中の少なくとも２つのジオグ
ラフィック領域のそれぞれに対するラスタ化ピクセルマ
ップに変換する少なくとも２つのパラレル処理手段も含
まれる。このシステムには、データストリームの中で使
用頻度の高いアイテムに対する中間形式データを再利用
する手段を加えるのが望ましい。ブロック識別手段、ブ
ロック変換手段、ソート手段、および中間形式データ変
換手段は、汎用マイクロプロセッサとするのが望まし
い。

D.実施例 D1.背景 本発明は、２次元オブジェクトの集合の一段高いレベ
ルでの記述を、１つのページマップまたは他のタイプの
ピクセルマップに変換するときに適用できる。実施例の
ラスタライザ10は、全点アドレス可能な（APA）コンピ
ュータ駆動型プリンタに対してページマップを準備す
る。

本発明による技術面の前進で大きいのは、コスト・メ
リットである。実施例を採用した高速マクチプロセッサ
・プロンタ・ラスタライザ10のコストは、速度が等しい
シングル・プロセッサ・ラスタライザを開発するコスト
よりもかなり少なくなる。このほか、実施例によるメリ
ットには、（ｉ）ハードウェアの効率利用すなわちオー
バヘッドと重複処理の低減、（ii）設計によって得られ
る柔軟性、（iii）スケーラビリティ、すなわちプロセ
ッサの個数はどのステージでも容易に増減できること、
（iv）プロセッサ数が増えるとき、本発明での所要メモ
リの増加率が低いこと、などである。ハードウェアの効
率利用は、協調型プロセッサ相互間の同期に工夫を凝ら
し、用途に応じてメモリを注意深く割り当てた結果であ
る。設計の柔軟性とスケーラビリティは、主として、ラ
スタ生成の全ステージに汎用プロセッサを採用した結果
である。これにより、どのプロセッサも任意のステージ
を処理できる。ただしここで注意しておきたいのは、こ
うした選択肢は望ましいが、本発明を正しく適用する上
で必須の要件ではないということである。

D2.概略 まず第１図と第７図を参照する。本発明のラスタライ
ザ10は、オブジェクト指向“データストリーム"12（こ
れはページの内容をページ記述言語“PDL"で記述する）
を“ページマップ"13（ラスタ化されたビットの集合）
に変換する。ページマップは、全点アドレス可能な（AP
A）デバイス（レーザ・プリンタなどが望ましい）に送
られる。この変換（ラスタ生成）は、第１ステージを除
く全ステージで複数のプロセッサを用い、４ステージで
実行される。

第１ステージ11では、１個の“スキャン・プロセッ
サ"14が、入力されたPDLデータストリーム12をスキャン
して、状態独立な“ブロック"16を識別する。各ブロッ
クには、“シーケンス番号”のタグがつけられ、後続の
ステージで動作するプロセッサを含めて全プロセッサが
使用できる共通メモリ18に格納される。

第２ステージ17では、１個の“ブロック・プロセッ
サ"22により、各ブロック16のPDLコマンドが“中間形式
オブジェクト"20に順次に変換される。ブロック・プロ
セッサ22は、使用可能になると、次にスキャンされたブ
ロック16を取り、ブロックの先頭から順次に中間形式オ
ブジェクト20を準備し、オブジェクトをブロックのシー
ケンス番号とともに、そのブロックのオブジェクト用に
予約された共通メモリ18の一部21に格納する。こうし
て、このステージは複数のブロック・プロセッサ22によ
って、ブロックごとに並列に実行される。

第３ステージ23では、複数の“ソート・プロセッサ"2
4が、格納された中間形式オブジェクト20を、ページマ
ップ13上のターゲットであるジオグラフィカル領域に従
って“ビン"26にソートする。ページマップ13は、処理
が開始される前に、非オーバラップ“ジオグラフィカル
領域”に分けられ、各領域に対してビンが形成される。
ここでも、同じブロックに属するオブジェクトは１個の
ソート・プロセッサによって順次に処理されるが、異な
るブロックは、数個のソート・プロセッサが並列に処理
できる。

第２と第３のステージ17、23では“リソース準備”が
“リソース・プロセッサ"27によって並列に行われる。
リソース・プロセッサ27は、第２ステージ17において、
キャラクタ、句読点、数値、符合など、複数回用いられ
たアイテムに対してブロック・プロセッサ22によって発
行された“リソース準備リクエスト"29から、中間形式
データ（リソース）28を作成してメモリに格納する。こ
れらのリソースは、第４ステージ31のビン・プロセッサ
30が再準備なく再利用できる。

第４ステージ31では、“ビン・プロセッサ"30が、ジ
オグラフィカルにソートされビン26に格納された中間形
式オブジェクト20をラスタ化し、得られたラスタ・デー
タ（部分的ページマップまたは“ピクセルマップ”）を
最終ページのページマップ13としてメモリに格納する。
ページマップ13は次に、APAプリンタ33に送られ、ここ
でデータストリーム12によって指定された実際の印刷ペ
ージが作成される。このプロセスで生成される最終的な
ページマップ13に一貫性を保つために、所定のビン内の
中間形式オブジェクト20が、１個のビン・プロセッサ30
によってブロック・シーケンス番号の順に処理される。

第２、第３、第４の各ステージおよびリソース準備プ
ロセスは、複数のプロセッサによって並列に実行され
る。第１ステージのスキャン・プロセッサ14は、それぞ
れ独自のデータ処理環境を持つ状態独立なブロック16を
生成するので、第２ステージのブロック・プロセッサ22
は、ブロックを並行または並列に処理できる。第３ステ
ージのソート・プロセッサ24は、中間形式オブジェクト
20をビン26に並列にソートし、各ソート・プロセッサ
は、１ブロックに対して格納されたオブジェクトを処理
する。第４ステージのビン・プロセッサ30は、ビン26の
内容を並行して、相互に独立にラスタ化するが、各ビン
は１個のビン・プロセッサによって順次に処理される。
リソース・プロセッサ27は、処理から解放されるときは
いつでも、リソース準備リクエスト・キュー上の次のリ
ソース準備リクエスト29をキューから取り出し（よって
次のリクエストをキューの先頭にもってくる）、リソー
スの中間形式データ28を準備する。リソースはこのよう
に複数のプロセッサが並列に準備することもできる。

４つのステージがすべてパイプライン処理されるの
で、次のステージは前のステージが完了する前にもスタ
ートできる。ブロック・プロセッサ22は、スキャン・プ
ロセッサ14がブロックのデータストリーム処理環境を識
別するとすぐにブロック16を処理し始める。ソート・プ
ロセッサ24は、ブロック・プロセッサ22が中間形式オブ
ジェクト20の生成を始めるとすぐ、そしてブロック・プ
ロセッサがブロック処理を終える前に、ブロックの中間
形式データ21のソートを開始する。ビン・プロセッサ30
は、ソート・プロセッサ24が、ソートされた中間形式オ
ブジェクト20のビン26を埋め始めるとすぐに、ソート・
プロセッサがそのビンの処理を終える前に、ビンの処理
を開始する。ただし、所与のビン26を処理するビン・プ
ロセッサ30は、次に続くブロック16から生成された、そ
のビン内のオブジェクト20に対する処理を、ビン・プロ
セッサが前の全ブロックに対する“ブロックの終わり”
マーカを検出するまでは開始しないことがある。これら
先行するブロックに対するオブジェクトが、ソート・プ
ロセッサ24から届いていないことがあるからである。こ
の条件は、最終的なページマップ13の一貫性を保証する
ために必要である。

スキャン・プロセッサ14、ブロック・プロセッサ22、
リソース・プロセッサ27、ソート・プロセッサ24、およ
びビン・プロセッサ30はすべて、従来の共通データ・バ
ス15を通して共通メモリ18と通信するシングル・タイプ
の汎用マイクロプロセッサが望ましい。プロセッサは、
おそらくスキャン・プロセッサは別として、ラスタ生成
プロセスのどのステージに対しても処理ができるように
プログラムできる。これにより、設計の柔軟性を最大限
に保証でき、とりわけ、開発によるボルトネックを防ぐ
ように、実行頻度の高いステージに対して、目的に応じ
たメモリの動的割り当てと、プロセッサの動的割り当て
ができる。プロセッサと共通メモリとの間には転送幅の
大きい通信が必要である。

D3.走査−第１ステージ 第２図に示すとおり、スキャン・プロセッサ14は、入
力としてデータストリーム12を受け取る。データストリ
ーム12には、あるページ記述言語（PDL）でページのシ
ーケンスが記述されている。スキャン・プロセッサの出
力はわずかに変更されたデータストリームであり、基本
的には本来のデータストリーム12が、ブロック境界につ
いての状態情報と各ブロックのブロック・シーケンス番
号32とともに状態独立なブロック16に分割されたもので
ある。ブロックは“状態独立”である。つまり各ブロッ
ク16は、そのデータストリーム処理環境（その“状
態”）に関して、中間形式データを準備するのに充分な
情報を持つ。このような状態情報には、たとえばテキス
トのキャラクタや符号に用いられたカレント・フォント
と適用されるカレント・スケールや回転についてのデー
タが含まれる。

スキャン・プロセッサの詳細は、処理されたPDLだけ
に依存する。一般的には、次のようなコマンドによっ
て、状態独立なブロックの先頭が識別される。

「位置ｘ＝5.45cm（2.45インチ）、ｙ＝18.75cm（7.4
3インチ）へ移動」 「カレント・フォントをTimes Roman Italic 12ポイ
ントにセット」 「グラフィクス状態をスケールｘ＝1.0、ｙ＝1.1、回
転90°にセット」 PDLのPOSTSCRIPT（Adobe Systems,Inc.）では、“gsa
ve"（グラフィクス・セーブ）、“grestore"（グラフィ
クス・リストア）などのコマンドがブロックの識別に用
いられる。

スキャンの処理量と得られるブロック・サイズとの間
にはトレードオフがある。たとえば簡単なスキャン・プ
ロセッサ14は、単にページ境界を捜し、それによってペ
ージマップ13ごとに１個のブロック16を生成し、ラスタ
ライザ10全体を簡素化する。これは、所与のページマッ
プに対するオブジェクト20がすべて、１個のブロック・
プロセッサ22によって正しい順序で生成され、各ビン26
が１個のソート・プロセッサ24によって埋められるから
である。そのため、ブロックの終わりのマーカと関連す
る同期化メカニズムの必要がなくなる。しかしこの簡単
なラスタライザでも、ページマップ13は第４（ページマ
ップ形成）ステージにおいて複数のビン・プロセッサ30
が同じページマップを処理できるように、ページマップ
13をジオグラフィカル領域に分割できる。ただしラスタ
ライザは、複数の完成したぺーじに対するデータストリ
ームを格納できなくてはならないので、ラスタライザの
所要メモリは増加する。

もう一つの極端の例として、非常に複雑なスキャン・
プロセッサ14は、ページマップ13ごとに多くのブロック
16を生成する。スキャン・プロセッサ14にどの程度の複
雑さが最適かどうかは、PDLデータストリーム12内の状
態独立なブロック16を識別する難しさと、ラスタライザ
10の他の部分にどの程度の複雑さが求められるかによ
る。

D4.中間形式オブジェクト−第２ステージ 第３図に示すとおり、ブロック・プロセッサ22は、第
２ステージにおいて状態独立なデータストリーム・ブロ
ック16を中間形式オブジェクト20に変換する。ブロック
の形式は全く、処理された特定のPDLに依存する。その
ためブロック・プロセッサのプログラミングはPDLに合
ったものでなくてはならない。ただし、得られる中間形
式データ20は特定のPDL入力に依存しない。

第２ステージのブロック処理は、複数のブロック・プ
ロセッサ22によって、複数のブロック16について並列に
実行される。ブロック・プロセッサ22はそれぞれ、ブロ
ックのPDL 16を解析すなわち解釈し、回転、スケーリン
グ、レンダリングの大半など、複雑なグラフィクス処理
を実行する。ブロック・プロセッサ22はまた、テキスト
・キャラクタなど再利用可能なリソース28への参照を識
別し、これらのリソースに対して中間形式データを準備
するために、リソース準備リクエスト・キューにリクエ
スト29を配置する。これについては「リソース準備」の
項で詳述する。所定のブロック16から生成された中間形
式オブジェクト20は、１個のブロック・プロセッサ22に
よって順次に生成され、そのブロックに予約された共通
メモリ18の一部21に順次に格納される。したがって、ブ
ロックごとにブロック・シーケンス番号を１回格納すれ
ば充分である。

まとめると、第２ステージは、状態独立なデータスト
リーム・ブロックを取り出して、中間形式オブジェクト
の集合に並列に変換する。各ブロックは異なるブロック
・プロセッサによって処理され、所与のブロックから得
られたオブジェクトにはブロックのシーケンス番号がま
とめてつけられ一括格納される。第２ステージはまた、
リソース準備リクエストも生成する。

D5.リソース準備プロセッサ 複数回用いられたアイテムに対する中間形式データか
ら成るリソースは、第４図に示すように、第２、第３ス
テージのブロック処理とソーティングに対して並列に準
備される。

第２ステージでは、あるブロック・プロセッサ22が、
データストリーム12によって、準備されていない再利用
可能アイテムが指定されていると判定すると、そのブロ
ック・ブロセッサは、そのアイテムに対する中間形式デ
ータ（リソース）のために、共通メモリ18にプレース
（リソース）28を予約し、“リソース準備リクエスト”
の共通キュー（リスト）にリソース準備リクエスト29を
配置する。同時にブロック・プロセッサ22は、リソース
が各種のブロックによって指定された回数を記録してお
くために、“リソース参照カウント”を初期化する。ブ
ロック・プロセッサ22は次に、リソースの中間形式デー
タを準備せずにそのブロック16の処理を続ける。各リソ
ース準備リクエスト29は、リソース・プロセッサ27のい
ずれかによってリソース・キューから順に引き出され
る。そのリソース・プスセッサ27は、リソース（の中間
形式データ）29を準備し、共通メモリ18内の、そのため
に予約されたプレースに格納する。

リソースが要求されると、後のブロック・プロセッサ
22は、すでに要求されているリソース・アイテムの指定
を認識したとき、リソース（の中間形式データ）28が未
完成のまま削除されてしまわないように、メモリに格納
されたリソース28へのポインタを、形成途中の中間形式
オブジェクト20に置き、リソースの参照カウントを更新
するだけである。このポインタは、次に、そのオブジェ
クト20を処理するビン・プロセッサ30によって、リソー
スの中間形式データ28を取得するのに用いられる。

このように、使用頻度の高いリソース・アイテムに対
する中間形式データは１回準備されるだけなので、重複
負荷が軽減され、ラスタライザの性能が向上する。

D6.ジオグラフィカル・ソーティング−第３ステージ 第５図に示す通り、第３ステージでの中間形式オブジ
ェクト20は、形成されたページマップ13のジオグラフィ
カル領域に対応するビン26にソートされる。

第３ステージのソーティングは、複数のソート・プロ
セッサ24上で、オブジェクト20の異なるオブジェクト・
グループ21に対して並列に実行されるが、各ブロックの
オブジェクト内では順次に実行される。第３ステージ
は、入力されたPDLには依存しない。ソートされるオブ
ジェクト20が中間形式だからである。以下、ビン26とブ
ロック番号32の両方によって、オブジェクト20を順に正
しくソートするのに必要な適用形態などの詳細について
述べる。

ページマップ13からジオグラフィカル領域への分割
は、第３ステージがスタートする前に行われる。ページ
マップ13の領域は、オーバラップせず、ひとまとまりで
ページ全体をカバーするものと事前に定義され、各ソー
ト・プロセッサ24に知られている。同時に、ページマッ
プ13ごとに多数の“第４ステージ・ワーク・キュー”が
生成される（各ジオグラフィカル領域に１つ）。これら
のキューは、すべてのソート・プロセッサ24がアクセス
できる。実施例では、第４ステージ・ワーク・キューお
よびそのエントリによって指し示されるオブジェクトは
ともに、“ビン”の実施例を成す。領域の形状と中間形
式オブジェクトのタイプの選択は、この第３ステージの
ソーティングを促進するように行われる。実施例では、
たとえば、領域は水平ページ・バンドとなるように選ば
れ、中間形式オブジェクト20は、底辺が、領域を成すバ
ンドと平行な台形または四角形のいずれかに制限され
る。ページマップの区画にはプロセッサが１個以上割り
当てられるが、これは基本的には設計上の選択の問題で
ある。第１ステージが、以下に述べるように段層的に並
列化される場合、最初の“簡単な”スキャン・プロセッ
サ（データストリーム12をページマップの大きさのスー
パブロックに分ける）は、それが識別する各ページマッ
プに対して領域を定義できる。あるいは領域は、どのペ
ージマップに対しても一様に定義してもよい。

各ビン26は、ビンのそれぞれのジオグラフィカル領域
に（部分的または全体的に）印刷される中間形式オブジ
ェクト20を格納するための、共通メモリ18の指定エリア
である。各オブジェクト20は、それを各ビン内にブロッ
ク番号の順に維持するために、オブジェクトが置かれる
ページマップ13内のジオグラフィカル領域に対応するビ
ン26に、オブジェクトの各ブロック・シーケンス番号32
とともに格納される。

第３ステージの“ソート”ステップでは、オブジェク
ト20の各ブロックのグループ21が複数の一時ワーク・エ
リアにソートされる。各ワーク・エリアは、ページマッ
プ13のジオグラフィカル領域すなわちビン26に対応す
る。ソート・プロセッサ24はそれぞれ、共通データスト
リーム・ブロック16から生成され、共通メモリのそのブ
ロックの部分21に一括格納された一連の中間形式オブジ
ェクト20を受け取る。ソート・プロセッサ24は、ソート
・ステップを始める前に、共通メモリ18内の複数の一時
ワーク・エリアの割り当て（ジオグラフィカル領域当た
り１部分）を取得し、ブロックのシーケンス番号32を各
ワーク・エリアの先頭に置く。ソート・プロセッサ24
は、ブロックのメモリ部分21内の各オブジェクト20を調
べて、ページマップ13のどの領域がその対象かを判定
し、オブジェクトの領域に対応する一時ワーク・エリア
にオブジェクトを配置する。オブジェクト20がいくつか
の領域にまたがる場合、そのオブジェクトは各領域のワ
ーク・エリアに置かれる。ソート・プロセッサ24は、所
定のブロック16のオブジェクト20のグループ21をソート
して一時ワーク・エリアに配置すると、そのブロックの
“ブロックの終わりのマーカ”を、それが取得したすべ
てのワーク・エリアの配置する。以下、ブロックの終わ
りのマーカの追加について説明する。

ソート・プロセッサ24は次に、ページマップ13の各ジ
オグラフィカル領域に対する第４ステージのワーク・キ
ューへポインタを追加する。ポインタは、ソート・プロ
セッサ24が作成したばかりのワーク・エリアを指し示
す。これらのポインタは、ソート・プロセッサ24によっ
てソートされたばかりのブロック16のブロック・シーケ
ンス番号32に従って、第４ステージ・ワーク・キュー内
の位置に置かれる。これによりオブジェクトは、第４ス
テージでブロック番号の順に処理される。ソート・プロ
セッサ24が使用するワーク・エリアは、このときソート
・プロセッサによって解放されるが、ワーク・エリアの
メモリの割り当ては、第４ステージのビン・プロセッサ
30がワーク・エリア内のオブジェクトを処理するまでは
解除されない。

第３ステージのソーティングの疑似コードの例を第８
図に示した。

第10図は、第８図の疑似コードに対応するフローチャ
ートである。フローチャートのボックスに記した参照番
号は、疑似コードの行番号に対応する。

D7.ページマップの形成 第４（最終）ステージでビン・プロセッサ30は、ビン
26に格納された中間形式オブジェクト20をピクセルマッ
プ（個々のピクセルのカラー値の集合）に変換し、pm13
にマージして、ラスタ生成プロセッサを完了する。第
２、第３ステージでは、パラレリズムはブロックごとで
あるが、第４ステージのパラレリズムは、異なるジオグ
ラフィカル領域に対応するビン26が、異なるビン・プロ
セッサ30によって並列に処理されるので、ジオグラフィ
ックである。

最初に各ビン・プロセッサ30にビン26が割当られる。
ビンは１個のビン・プロセッサにしか割当られない。し
たがって、ある特定のビン26に対応するページマップ13
の領域を更新するビン・プロセッサ30は１個だけであ
る。

各ビン・プロセッサ30は、そのビン26内のオブジェク
トをブロック番号順に処理する。オブジェクト20が、第
２ステージにおいてソート・プロセッサ24によってブロ
ック番号順に各ビン26内に格納されるからである。各ビ
ン26内のこのブロック番号による順序づけにより、同じ
領域内にあるが、異なるブロックによって生成されたオ
ブジェクトでも正しい順序に維持される。特定のブロッ
クからのオブジェクトの正しい順序は、各ビン26内で、
これらのオブジェクトがビン26に順次に配置されること
によって維持される。異なるブロック（並列）から生成
されたオブジェクト相互の順序は、ブロック・シーケン
ス番号によって維持される。

ビン・プロセッサ30は、次に番号が大きいブロックか
らのオブジェクトにとりかかる前に、所定のブロックか
らのそのビン26内のオブジェクト20をすべて処理し終え
なくてはならない。オブジェクト20はブロック・プロセ
ッサ22によって、異なる遅延時間、持続時間で並列に生
成されているので、ビン・プロセッサ30には、特定のブ
ロックからのオブジェクトがすべて生成されていること
を、ソート・プロセッサ24が明示的に通知しなくてはな
らない。これは、ソート・プロセッサがブロックの終わ
りのマーカ36をビン26に格納することにより行われる。

ビン・プロセッサ30は、リソース28への参照を検出す
ると、リソース準備が完了しているかどうかを確認す
る。リソースが準備されていなければ、ビン・プロセッ
サ30はそれを待たなければならない。リソース28が準備
されると、それを必要とするビン・プロセッサ30は、中
間形式オブジェクト内に置かれたポインタを使って、リ
ソースの中間形式データを見つける。ビン・プロセッサ
30は、リソースの中間形式データ28をピクセルマップに
変換し、ページマップ13内の位置に置く。ビン・プロセ
ッサ30は、リソース28を使用した後、リソースの参照カ
ウントをデクリメントする。リソースの参照カウントが
０になると、すなわちそれが必要なくなると、リソース
の中間形式データの割り当てを解除できる。リソース割
り当ての解除は、必要に応じて行われるので、使用頻度
の高いリソースの割り当ては、ある時間にそれらに対す
るリクエストが保留されている可能性がなくても、直ち
に解除されることはない。割り当て解除に適した方法と
しては、LRU（least recently used）やLFU（least fre
quently used）などがよく知られている。

ページマップ13が形成されると、それはプリンタに送
られて印刷される。プリンタ33は、IBMモデル3812−002
PAGEPRINTER、IBMモデル4019 LASERPRINTERなど、従来
の全点アドレス（APA）プリンタである。

ビン・プロセッサ30よりもビン26の方が多い場合、ビ
ン・プロセッサには複数のビンが割り当てられる。この
ようなビン・プロセッサは、準備されソートされる１個
のビン26のオブジェクト20を待つ必要があると、その他
のビンで処理を試すことができる。ビン・プロセッサ30
は、そのビン26のページマップ13の終わりに達すると、
ビン・プロセッサにまだ割り当ててなかった別のビンの
処理を開始する。

第４（ページマップ形成）ステージは、データストリ
ームに用いられるPDLとは全く独立している。このステ
ージはまた、処理すべきデータ量は大きいものの、比較
的簡単な処理しか要しない。これは専用ハードウェアで
も効果的に実行できるが、汎用マイクロプロセッサの方
が望ましいと考える。

第９図は、第４のページマップ形成ステージの疑似コ
ードの例である。行207は、ブロック・プロセッサ22の
いずれかが時間を長くかけていることを表す。ビン・プ
ロセッサ30は、特定のブロック16からのオブジェクト20
をすべて処理し、そのブロックのブロックの終わりのマ
ーカ36を検出しなかったとき、ブロックのブロック・プ
ロセッサ22がまだブロック処理を終えていないことを認
識する。ビン・プロセッサ30は、ブロック16が処理され
ソートされて、ブロックのブロックの終わりのマーカ36
がビン・プロセッサのビン26に現れるまで、待機するほ
かない。従来の技術には、ここで採用できる待機／通知
方式がいくつかある。

第11図は、第９図の疑似コードに対応するフローチャ
ートである。フローチャートのボックスに記した参照符
号は疑似コードの行番号に対応する。

D8.具体例 ラスタライザ10の動作について、第２図ないし第６図
はあわせて説明する。

最初に第２図を参照する。第１ステージでPDLデータ
ストリーム12は、スキャン・プロセッサ14によって受け
取られ、ブロック16に分けられる。図には最初のページ
PAGE1の最初の３ブロックしか示していないが、代表的
なデータストリームは、複数のページを指定するブロッ
クが数十、数百あるいは数千もある。各ブロックの内容
は、データストリームPDLのフラグメントであり、これ
はラスタ生成のために後のステージでオブジェクトとな
る。そのため、データストリームの小さいフラグメント
が複数のオブジェクトになることがある。たとえば、円
を描くデータストリーム・コマンドは、多数の台形オブ
ジェクトに変換される場合がある。第２図と第３図は、
説明の便宜上、各オブジェクトを、ブロック内のデータ
ストリームの対応する一意のフラグメントを持つものと
して示している。BLOCK 1は、PDLフラグメントPDL 1A、
PDL 1B、およびPDL 1Cを持つものとして示している。同
様にBLOCK 2は、PDL 2A、PDL 2Bを、BLOCK 3は、PDL 3
A、PDL 3Bを含む。

第３図に示した第２ステージ17では、異なるブロック
・プロセッサ22が各ブロク16を、対応する中間形式デー
タ・オブジェクトのグループ21に変換する。ブロック・
プロセッサ22は、ブロック16を並列に処理するので、ブ
ロックのシーケンス番号32と、ブロックを処理するブロ
ック・プロセッサとは必ずしも対応しない。

第２ステージ17のこの例では、BLOCK 1は３つの中間
形式オブジェクトOBJ 1A、OBJ 1B、およびOBJ 1Cに変換
される。さらにBLOCK 1は、RES 1、RES 2と示した、複
数回用いられた２つのリソースに対するデータストリー
ム・フラグメントを含む。BLOCK 1を処理するブロック
・プロセッサ22は、これらのリソースに対するリソース
準備リクエスト29、REQ RES 1とREQ RES 2を、リソース
準備リクエスト・キューに配置する。ブロック・プロセ
ッサはまた、これらのリソースの中間形式データ28のス
トレージ・ロケーションへのポインタをリソースを使用
するオブジェクト内に置く。こうしてOBJ 1AはRES 1とR
ES 2へのポインタを、OBJ 1BとOBJ 1CはリソースRES 2
へのポインタを含む。

同様にBLOCK 2は、中間形式オブジェクトOBJ 2A、OBJ
2Bおよびリソース準備リクエストREQ RES 3に、BLOCK3
は、OBJ 3A、OBJ 3Bにそれぞれ変換される。ここで注意
しておきたいが、オブジェクト20のサイズは可変であ
る。サイズは通常（常にそうとは限らないが）、得られ
るイメージのサイズまたは複雑さに関係する。

リソース準備プロセッサは第４図に示した。２つのリ
ソース・プロセッサ27は、リソース準備リクエスト・キ
ューからリソース準備リクエスト29を取り、要求された
リソースの中間形式データ28を準備・格納する。リソー
スの中間形式データ28は、共通メモリ18の、第２ステー
ジ17においてリソースの準備を要求したブロック・プロ
セッサ22によって割り当てられたロケーションに格納す
る。したがってREQ RES 1が処理されて、RES 1に対する
中間形式データ28が共通メモリ18に格納される。同様に
REQ RES 2とREQ RES 3が処理されてRES 2とRES 3が生成
される。

ジオグラフィカル・ロケーションごとに中間形式オブ
ジェクト20をソートする第３ステージ23を第５図に示し
た。ここで３つのソート・プロセッサ24が、オブジェク
トのグループ21をソートする。第２ステージ17のよう
に、ブロック・シーケンス番号32と、そのブロックのオ
ブジェクトをソートするソート・プロセッサ24との相関
は必要ない。

第３ステージ23のこの例では、BLOCK 1のオブジェク
トOBJ 1AとOBJ 1Bが、BIN 2に割り当てられているペー
ジマップ13のジオグラフィカル領域に置かれるイメージ
を指定し、これらのオブジェクト（正確にはオブジェク
トへのポインタ）がBIN 2に置かれる。BLOCK 1の第３オ
ブジェクトOBJ 1CはBIN 1に置かれる。ソート・プロセ
ッサ24は次に、BLOCK 1のブロックの終わりのマーカ36
（END 1）を、ラスタ・ページマップ13に対するすべて
のビン26に配置する。

同様に、BLOCK 2のオブジェクトはそれぞれのビンに
置かれ、OBJ 2AはBIN 3に、OBJ 2BはBIN 1に、そしてBL
OCK 3のオブジェクトOBJ 3AはBIN 2にそれぞれ置かれ
る。OBJ 3Bは、BIN 2とBIN 3の両方の領域にオーバラッ
プするので、それらのビン26の両方に置かれる。

第６図に示した第４ステージ31はラスタ・ページマッ
プ13を生成する。パラレル・ビン・プロセッサ30は（そ
れぞれ１個のビン26のオブジェクト20を処理する）、ビ
ンの個々のジオグラフィカル領域のラスタ・ピクセルマ
ップを生成する。これらのピクセルマップはともにペー
ジマップ13を形成する。

BIN 1の内容を処理するビン・プロセッサは最初に、O
BJ 1Cをラスタ化する。これには、そのオブジェクトの
関連リソースRES 2のラスタ生成が必要である。その結
果、ラスタ・リソース・イメージ（R2）を含むラスタ・
イメージ1CがBIN 1のピクセルマップに置かれる。次に
ビン・プロセッサは、ブロックの終わりのマーカ36（EN
D 1）を処理し、オブジェクトOBJ 2Bのラスタ化へ進
み、それをBIN 1のピクセルマップに置く。イメージ2B
は、部分的にイメージ1Cに重なり、このデータストリー
ム12はオーバペイント混合モードを指定するので、イメ
ージ2B（データストリームの後の方で現れる）は部分的
にイメージ1Cに重なり、スーパインポーズされる。BIN
1に対するビン・プロセッサ30は次に、マーカEND 2とEN
D3を検出して、次のビンの処理に進む。

BIN 2を処理するビン・プロセッサは、OBJ 1Aおよび
そのリソースRES 1、RES2をラスタ化して、ラスタ・リ
ソース・イメージ（R1、R2）を含むイメージ1Aを生成す
る。リソース・イメージ（R2）を含むイメージ1Bも、マ
ーカEND 1とEND 2が検出されてから、イーメジ3Aと同様
に生成される。BIN 1のように、イメージ3Aは、イメー
ジ1Bに重なり、OBJ 3Aはデータストリーム12の後の方で
発生するので、イメージ3Aはイメージ1Bの一部を覆う。
BIN 2では、BIN 2とBIN 3の領域にオーバラップするオ
ブジェクトOBJ 3Bは、イメージ3Bにラスタ化される。こ
れはイメージ3Aの一部に重なる。

BIN 3では、ラスタ・リソース・イメージ（R3）を含
むイメージ2Aが、イメージ3BのBIN 3の領域内の部分に
続いて、ピクセルマップに置かれる。

PAGE 1のページマップ13は最後に、それが含まれるピ
クセルマップからアセンブルされ、そこでプリンタへ送
信して印刷できる。

D9.他の実施例 ここでは、説明の便宜上、本発明の具体的な実施例に
ついて説明しているが、本発明は、その要締と範囲から
逸脱することなく様々に変更可能である。特に、実施例
ではプリンタ・ページマップが生成されるが、本発明
は、２次元オブジェクトのイメージング並びに、２次元
オブジェクトの一段高いレベルでの記述をラスタ・ペー
ジマップ表現または他のピクセルマップ表現に変換する
アプリケーションに用いられるディスプレイにも適用で
きる。

また、実施例の第１スキャン・ステージは、１個のス
キャン・プロセッサ14によって順次に実行されるが、デ
ータストリーム12のスキャンは並列化可能である。この
ような構成を１つ考えると、始めの簡単なシーケンシャ
ル・スキャン・プロセッサは、データストリームを、ペ
ージ全体のデータストリームを含むブロックに分ける。
各ブロックは次に数個の複雑なパラレル・スキャン・プ
ロセッサのいずれかに引き渡され、状態独立な小さいブ
ロックに分けられる。こうしてブロックは状態独立な数
個のサブブロックに分けられ、各ブロックがシーケンス
番号を持つ。そのため、数個のブロック・プロセッサと
ソート・プロセッサは、メイン・ブロックを並行して処
理できる。さらに、本発明のスキャン・プロセッサとブ
ロック・プロセッサは、従来の“機能的”ラスタライザ
と似た方法により、ある特定のタイプのブロックを処理
するように特殊化できる。

実施例では、所定のブロックのオブジェクトがすべて
１個のソート・プロセッサによってソートされるが、各
オブジェクトが、そのブロックの第２ステージ・ブロッ
ク・プロセッサによって、オブジェクト自体のブロック
・シーケンス番号とともに格納されていれば、同じブロ
ックのオブジェクトを複数のソート・プロセッサが処理
できる。あるいは、第３ステージのソーティングは、第
２ステージの中間形式オブジェクトの生成とマージでき
る。ただしその場合には、パイプライン処理可能なステ
ージ数が減り、よって条件によってはラスタライザの性
能が下がることがある。

実施例では複数の独立したマイクロプロセッサが用い
られるが、本発明のステージは、マルチプロセッサであ
るIBMモデル3090（メインフレーム・コンピュータ）、I
BM OS/2 EXTENDED EDITIONなどマルチタスクのオペレー
ティング・システムを実行するIBM PS/2（パーソナル・
コンピュータ）を含め、マルチタスク・プログラミング
の汎用デジタル・コンピュータ１台でも実行できる。あ
るいは、各ステージに対するプロセッサを個々に最適化
するために、ステージごとにタイプの異なるプロセッサ
を使用してもよい。プロセッサのタイプが異なる場合に
は、プロセッサは、共通メモリ全体をアクセスするので
はなく、独立したメモリ区画に接続すれば、プロセッサ
が、メモリ内の異なるエリアを並行してアクセスでき、
よって、高速メモリや高速プロセッサを必要とせずに通
信転送幅を大きくとれる。

リソース準備は、第２ステージの中間形式データの準
備と組み合わせられる。こうすれば、サイズの不明なリ
ソースに、量の不明なメモリを割り当てる難しさも回避
できよう。ただし、リソースを並列に準備すれば、１つ
のデータストリーム・ブロックに対して複数のリソース
を準備する必要がある際に、ラスタライザの性能が低下
することがある。１個のブロック・プロセッサがすべて
の処理を引き受けることになるからである。

ラスタライザ10は、プリンタ33とは分離したプリプロ
セッサとして説明しているが、これは、ラスタライザ
を、データストリームを生成するアプリケーションが実
行されるコンピュータ内に置くか、ラスタライザをプリ
ンタに組み込むか、ラスタライザを個別コンポーネント
として構成するかといった設計上の選択肢にすぎない。
データストリームを生成するアプリケーションが、マル
チタスクの可能なコンピュータ上で実行される場合は、
本発明に従ったラスタ生成は、アプリケーション・ライ
クなポストプロセッサとして実行できる。データストリ
ームを生成するアプリケーションが、１個のアプリケー
ション内でマルチスレッドが可能なコンピュータ上で実
行されるときは、本発明によるラスタ生成は、アプリケ
ーション内で実行可能である。

D10.従来の技術との比較 本発明のラスタライザは、各ステージにパラレリズム
を与え、負荷分散の問題を少なくすることによって、従
来の単純なパイプライン型ラスタライザの性能を上回
る。本発明では、ステージの相対負荷を基準に、プロセ
ッサを、その個数を変えて、ステージごとに静的または
動的に割り当てることができる。

本発明は、従来のページ・パラレル・ラスタライザを
上回る重要なメリットを提供する。数個のプロセッサが
同じページを扱うので、プロセッサの個数にかかわら
ず、ページマップに必要なメモリは実質上少なくなる。
本発明はまた、異なるページをページ・パラレル・ラス
タライザよりも高速にラスタ化する。複数のブロック・
プロセッサ、ソート・プロセッサ、およびビン・プロセ
ッサが、ブロックおよび各ページマップの領域を協調し
て処理するからである。そしてプロセッサは、ページの
複雑さが変わりやすい場合でもアイドル状態に置かれる
ことがなく、これによってメモリを追加する必要が生じ
ることもない。

Ｚバッファを備えた3Dラスタライザでは、２つの主な
ラスタ生成フェーズがプロセッサのグループによって並
列に実行されるが、2Dオブジェクトを処理するときは、
ピクセル当たりのメモリ量に制限があると、混合ルール
の組み合わせを正しく処理することができない。これ
は、混合モードが複数あると、オブジェクトは、指定さ
れた順序どおりに適用しなくてはならないからであり、
ページマップ・ビルダにその順序で与えられない場合
は、ビルダは、ページが完成するまで値をすべて格納し
ておき、完成したときだけ、シーケンス番号順にソート
し、ピクセルごとに１つずつ、ページマップに適用しな
くてはならない。Ｚバッファ・ラスタライザが最も適し
ているオーバペイント・モードでも、奥行き値をピクセ
ルごとに格納する必要がある。ピクセルは、プリンタで
は１ビットないし４ビットで表され、典型的な奥行き情
報は少なくとも６ビットを要するので、Ｚバッファ・ラ
スタライザには、本発明によるラスタライザよりもはる
かに大量のメモリが必要になる。これは、本発明が、デ
ータストリームにおけるオブジェクトの出現順序が、オ
ブジェクトの相対奥行きを反映するという事実を利用し
ているからである。そのためデータストリームの後の方
に現れるオブジェクトは、視点に“近く”、したがって
それらのオブジェクトが重なり合うオブジェクトにオー
バペイントされる。

ラスタ処理マシン（RPM）とは異なり、本発明は、複
数のプロセッサを使用してデータストリームを中間形式
に変換し、そのプロセッサでのRPMのボルトネックを解
消している。おそらくこれよりも重要だと思われるの
は、本発明のラスタライザが、RPMラスタライザとは異
なり、適用される混合モードを考慮して、オブジェクト
が正しく配置されるページマップを生成することであ
る。

また、従来のラスタライザはいずれも、ここで述べた
リソースを並列に準備する機能を提供していない。

【図面の簡単な説明】

第１図は、本発明によるマルチプロセッサ・プリンタ・
ラスタライザの実施例を示すブロック図である。 第２図は、スキャン・プロセッサが、入力されたPDLデ
ータストリームを状態独立なブロックに分ける、第１図
のラスタライザの第１ステージを示すブロック図であ
る。 第３図は、ブロック・プロセッサが、中間形式オブジェ
クトとリソース・リクエストを準備する、第１のラスタ
ライザの第２ステージを示すブロック図である。 第４図は、第１図のラスタライザのリソース準備プロセ
ッサを示すブロック図である。 第５図は、ソート・プロセッサが、中間形式オブジェク
トをジオグラフィカル・ビンにソートする、第１図のラ
スタライザの第３ステージを示すブロック図である。 第６図は、ビン・プロセッサが、ソートされた中間形式
オブジェクトと準備されたリソースをラスタ・ピクセル
マップに変換してページマップを形成する、第１図のラ
スタライザの第４ステージを示すブロック図である。 第７図は、各ステージにおける並列処理とステージ相互
間のパイプライン処理を示す、第１図のラスタライザの
動作図である。 第８図は、１個のソート・プロセッサにおける、中間形
式オブジェクトをソートする第３ステージの疑似コード
の実施例を示す図である。 第９図は、１個のビン・プロセッサにおける、ページマ
ップの領域を形成する第４ステージの疑似コードの実施
例を示す図である。 第10図は、第８図の疑似コードに対応するプログラミン
グ・フローチャートである。 第11図は、第９図の疑似コードに対応するプログラミン
グ・フローチャートである。

Claims (26)

【特許請求の範囲】
1. 【請求項１】出力イメージを少なくとも１個指定するデ
   ータストリームのラスタ生成方法であって、 （ａ）上記データストリーム内の状態独立なブロックを
   少なくとも２個識別するステップと、 （ｂ）上記ブロックを中間形式データに並列に変換する
   ステップと、 （ｃ）上記出力イメージのうち少なくとも２つのジオグ
   ラフィカル領域に関連する上記中間形式データを、該出
   力イメージの少なくとも一部を表すラスタ・ピクセルマ
   ップに変換するステップとを含むことを特徴とするラス
   タ生成方法。
2. 【請求項２】請求項（１）に記載の方法であって、ステ
   ップ（ｂ）がステップ（ａ）とパイプラインを成す方
   法。
3. 【請求項３】請求項（１）に記載の方法であって、ステ
   ップ（ｃ）がステップ（ｂ）とパイプラインを成す方
   法。
4. 【請求項４】請求項（１）に記載の方法であって、中間
   形式データをラスタ・ピクセルマップに変換する前に、
   ブロックの中間形式データをイメージのジオグラフィカ
   ル領域ごとに並列にソートするステップを含む方法。
5. 【請求項５】請求項（１）に記載の方法であって、 （ｄ）ピクセルマップをイメージの表現にアセンブルす
   るステップを含む方法。
6. 【請求項６】請求項（５）に記載の方法であって、デー
   タストリームが、プリンタのページ記述言語（PDL）の
   コマンドを含み、 （ｅ）イメージを印刷するステップを含む方法。
7. 【請求項７】請求項（１）に記載の方法であって、ステ
   ップ（ａ）ないし（ｃ）が、プログラムされた汎用マイ
   クロプロセッサによって実行される方法。
8. 【請求項８】請求項（７）に記載の方法であって、マイ
   クロプロセッサが、ステップ（ａ）ないし（ｃ）のうち
   ２ステップ以上を実行する方法。
9. 【請求項９】請求項（１）に記載の方法であって、ソー
   トされた中間形式データをピクセルマップに変換する際
   に、中間形式データを再利用するステップを含む方法。
10. 【請求項１０】請求項（９）に記載の方法であって、選
    択されたブロックの少なくとも２つのアイテムに対し
    て、再利用可能な中間形式データを並列に準備するステ
    ップを含む方法。
11. 【請求項１１】請求項（10）に記載の方法であって、再
    利用可能な中間形式データが、ブロックから中間形式デ
    ータへの変換と並列に準備される方法。
12. 【請求項１２】請求項（10）に記載の方法であって、再
    利用可能な中間形式データが、中間形式データのソーテ
    ィングと並列に準備される方法。
13. 【請求項１３】出力イメージを少なくとも１個指定する
    データストリームのラスタ生成システムであって、 上記データストリーム内の状態独立なブロックを少なく
    とも２個識別する手段と、 上記ブロックを中間形式データに変換する並列処理手段
    と、 上記中間形式データを、上記出力イメージのうち少なく
    とも２つのジオグラフィカル領域のそれぞれのラスタ・
    ピクセルマップに変換する並列処理手段とを含むラスタ
    生成装置。
14. 【請求項１４】請求項（13）に記載の装置であって、ブ
    ロックを変換する手段がブロックを識別する手段とパイ
    プラインを成す装置。
15. 【請求項１５】請求項（13）に記載の装置であって、中
    間形式データを変換する手段がブロックを変換する手段
    とパイプラインを成す装置。
16. 【請求項１６】請求項（13）に記載の装置であって、中
    間形式データをページマップのジオグラフィカル領域ご
    とにソートする並列処理手段を少なくとも２つ含む装
    置。
17. 【請求項１７】請求項（16）に記載の装置であって、ソ
    ーティング手段がブロック変換手段とパイプラインを成
    し、 中間形式データ変換手段が上記ソーティング手段とパイ
    プラインを成す装置。
18. 【請求項１８】請求項（13）に記載の装置であって、ペ
    ージマップを基にイメージを印刷する手段を含む装置。
19. 【請求項１９】請求項（18）に記載の装置であって、プ
    リンタを含む装置。
20. 【請求項２０】請求項（13）に記載の装置であって、ブ
    ロック変換手段が、並列に動作するようにプログラムさ
    れた汎用マイクロプロセッサを少なくとも２個含む装
    置。
21. 【請求項２１】請求項（13）に記載の装置であって、ソ
    ーティング手段が、並列に動作するようにプログラムさ
    れた汎用マイクロプロセッサを少なくとも２個含む装
    置。
22. 【請求項２２】請求項（13）に記載の装置であって、中
    間形式データ変換手段が、並列に動作するようにプログ
    ラムされた汎用マイクロプロセッサを少なくとも２個含
    む装置。
23. 【請求項２３】請求項（13）に記載の装置であって、中
    間形式データをラスタ・ピクセルマップに変換する際
    に、該中間形式データを再利用する手段を含む装置。
24. 【請求項２４】請求項（23）に記載の装置であって、選
    択されたブロックの少なくとも２つのアイテムに対し
    て、再利用可能な中間形式データを並列に準備する手段
    を含む装置。
25. 【請求項２５】請求項（23）に記載の装置であって、再
    利用可能な中間形式データを、ブロックを中間形式デー
    タに変換する手段と並列に準備する手段を含む装置。
26. 【請求項２６】請求項（23）に記載の装置であって、再
    利用可能な中間形式データを、中間形式データのソーテ
    ィング手段と並列に準備する手段を含む装置。