JP4646436B2 - デジタル画像の画像処理装置 - Google Patents
デジタル画像の画像処理装置 Download PDFInfo
- Publication number
- JP4646436B2 JP4646436B2 JP2001148269A JP2001148269A JP4646436B2 JP 4646436 B2 JP4646436 B2 JP 4646436B2 JP 2001148269 A JP2001148269 A JP 2001148269A JP 2001148269 A JP2001148269 A JP 2001148269A JP 4646436 B2 JP4646436 B2 JP 4646436B2
- Authority
- JP
- Japan
- Prior art keywords
- fill
- pixel
- priority
- module
- color
- 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
Images
Classifications
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- G06T11/00—2D [Two Dimensional] image generation
- G06T11/40—Filling a planar surface by adding surface attributes, e.g. colour or texture
Landscapes
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Image Generation (AREA)
- Record Information Processing For Printing (AREA)
- Image Processing (AREA)
Description
【０００１】
【発明の属する技術分野】
本発明はデジタル画像の画素を処理する装置に関し、特にグレイスケールグラフィックオブジェクトをラスタ画素画像にレンダリングすることに関する。
【０００２】
【背景技術】
オブジェクトを利用するグラフィックスシステムの多くは、ページ又は画面の画素ベース画像を保持するためにフレームストア又はページバッファを利用している。通常、図形オブジェクトの輪郭を計算し、埋め込み（fill)して、フレームストアに書き込む。２次元図形の場合、他のオブジェクトの前方に現れるオブジェクトは単に背景オブジェクトの後にフレームストアに書き込まれるだけであるので、画素ごとに背景と置き換えられる。当該技術分野においては、これは一般に「ペインターのアルゴリズム」として知られている。オブジェクトは最も後ろの位置にあるオブジェクトから最も前方のオブジェクトまで優先順位に従って考慮され、通常、各オブジェクトは走査線の順にラスタ化され、画素は各走査線に沿って逐次ランとしてフレームストアに書き込まれる。
【０００３】
この技法には本質的に２つの問題がある。第１の問題は、フレームストアの全ての画素に対して高速ランダムアクセスが要求されることである。これは、考慮される新たなオブジェクトがいずれもフレームストア内のいずれかの画素に影響を及ぼす可能性があるためである。このため、フレームストアは通常は半導体ランダムアクセスメモリ（ＲＡＭ）に保持されている。高分解能のカラープリンタの場合、要求されるＲＡＭの量は非常に多く、通常は１００メガバイトを越えてしまうので、そのようなメモリはコストもかかり、高速で動作させるのは困難である。第２の問題は、多くのペイント（レンダリング）された画素が、後に現れるオブジェクトにより上書きペイント（再レンダリング）されるという点である。以前のオブジェクトに対する画素のペイントは、時間の無駄である。
【０００４】
フレームストアが大型になるという問題を克服する１つの方法は、「バンディング」を使用する方法である。バンディングを使用すれば、ある１つの時点でメモリに存在するのはフレームストアのごく一部ということになる。描き出すべき全てのオブジェクトは「表示リスト」に保持される。画像全体は先に説明したようにレンダリングされるが、存在するフレームストアの一部分の外側をペイント（レンダリング）しようとする画素ペイント（レンダリング）動作は「クリップアウト」される。全てのオブジェクトが描かれた後、フレームストアのその一部分をプリンタ（又は他の何らかの場所）へ送信し、フレームストアの別の部分を選択して、このプロセスを繰り返す。この技法には不都合な点がある。例えば、描くべきオブジェクトを何度も、すなわち、バンドごとに一度ずつ考慮しなければならない。バンドの数が増えるにつれて、レンダリングを要求するオブジェクトの検査を繰り返す回数も増加する。従って、バンディングの技法は上書きペイント（over-painting）の不利益の問題を解決するものではない。
【０００５】
他のいくつかのグラフィックシステムは画像を走査線の順に考慮する。この場合にも、描き出すべき全てのオブジェクトは表示リストに保持される。走査線ごとに、その走査線と交わるオブジェクトを優先順位に従って考慮し、オブジェクトごとに、オブジェクトの辺の交差点の間の画素のスパンをラインストアにセットする。この技法もフレームストアの問題を克服するが、上書きペイントの問題は依然として残る。
【０００６】
フレームストアが大型になるという問題と、上書きペイントの問題を共に克服する技法は他にもある。そのような技法の１つによれば、各走査線を順次生成する。この場合にも、描くべき全てのオブジェクトは表示リストに保持される。走査線ごとに、その走査線と交わるオブジェクトの辺を走査線との交差点の座標の小さい順に保持する。それらの交差点、すなわち、辺交差を順次考慮し、アクティブフラグのアレイをトグルするために使用する。走査線上で関心のあるオブジェクト優先順位ごとに１つのアクティブフラグが存在する。考慮される各対の辺の間で、アクティブフラグに対して優先順位符号器を使用して、どの優先順位が最高であるかを判定し、且つ２つの辺の間のスパンの画素に対してその優先順位と関連する色を使用することにより、第１の辺と次の辺との間に位置する画素ごとのカラーデータを生成する。次の走査線を準備する中で、各辺の性質に従って各辺の交差点の座標を更新する。この更新の結果として誤って分類されることになった隣接する辺を交換する。また、新たな辺を辺のリストに併合する。
【０００７】
この技法は、フレームストア又はラインストアがなく、上書きペインティングもなく、オブジェクトの優先順位が順位Ｎ時間（Ｎは優先順位の数である）ではなく、一定の順位時間で扱われるという著しく大きな利点を有する。
【０００８】
このようなグラフィックシステムの出力は、通常、クロックサイクルごとにトグルするような画素カラーデータを搬送するためのバス（２４ビット又は３２ビット幅）から構成されている。画素データバスに付随して、画素の属性及び特性を示すいくつかの制御信号がある。画素カラーデータは、通常、その色成分、すなわち、赤、緑、青の成分から形成されており、不透明度チャネル（すなわち、シアン、マゼンタ、黄色及び黒の各チャネル）を伴う場合と、伴わない場合がある。
【０００９】
グレイスケールレンダリングの場合、システムは、より狭いデータパス（すなわち８ビット幅）を有するか、又は、カラーグラフィックシステムの使用可能な４つのチャネルのうちの１つを使用する。
【００１０】
【発明の概要】
本発明の目的は、既存の構成の１つ又は複数の欠点をほぼ克服すること又は少なくとも軽減することである。
【００１４】
本発明の１つの態様によれば、デジタル画像の画素を処理する画像処理装置であって、
複数のカラー出力チャネルを有する画像処理装置を第１の動作モード又は第２の動作モードで動作するように構成するホストプロセッサを具備し、前記画像処理装置は、
前記第１の動作モード中、複数の画素色成分を有する１つのカラー画素を生成し、且つ生成された各画素の前記複数の画素色成分を、対応する前記カラー出力チャネルから出力することにより、前記生成された複数のカラー画素を出力する塗りつぶしモジュールと、
前記第２の動作モード中、塗りつぶし指令が適用されるラスタ順の連続する画素位置の数であって、１から前記カラー出力チャネルの数に等しい最大数まで変化できる数を指示するパラメータをそれぞれ含む１つ又は複数の塗りつぶし指令を生成するモジュールとを具備し、
前記塗りつぶしモジュールは、前記第２の動作モード中、１つ又は複数の前記画素位置に対して１つ又は複数の前記塗りつぶし指令に応答して、塗りつぶし指令の数及び前記塗りつぶし指令のパラメータに従って決まる数の、各々が１つの画素色成分を有する画素を生成し、且つ複数の前記画素を、前記複数の前記カラー出力チャネルから出力することを特徴とする画像処理装置が提供される。
【００１６】
本発明の別な態様によれば、デジタル画像の画素を処理する画像処理装置において、
画像処理装置を第１の動作モード又は第２の動作モードで動作するように構成するホストプロセッサを具備し、前記画像処理装置は、
前記第１の動作モード中、対応する画素位置に対して１つ又は複数の塗りつぶし指令を生成する優先順位モジュールと、
前記第１の動作モード中、前記画素位置に対して１つ又は複数の対応する前記塗りつぶし指令に応答して、複数の画素色成分を有する１つの画素を出力する塗りつぶしモジュールとを具備し、
前記優先順位モジュールは、前記第２の動作モード中、塗りつぶし指令が適用されるラスタ順の連続する画素位置の数であって、１から前記カラー出力チャネルの数に等しい最大数まで変化できる数を指示するパラメータをそれぞれ含む１つ又は複数の塗りつぶし指令を生成し、且つ
前記塗りつぶしモジュールは、前記第２の動作モード中、１つ又は複数の前記画素位置に対して１つ又は複数の前記塗りつぶし指令に応答して、塗りつぶし指令の数及び前記塗りつぶし指令のパラメータに従って決まる数の、各々が１つの画素色成分を有する複数の画素を生成し、且つ生成された複数の画素を、対応する複数の前記カラー出力チャネルから出力することを特徴とする画像処理装置が提供される。
【００２０】
【実施形態】
次に、添付の図面を参照して本発明のいくつかの好ましい実施形態を説明する。
【００２１】
添付の図面のいずれか１つ又は２つ以上においてステップ及び／又は特徴を参照する場合、本明細書においては、特に指示のない限り、便宜上、同じ図中符号を付されているステップ及び／又は特徴は同じ機能又は動作を有するものとする。
【００２２】
そこで図１を参照すると、コンピュータグラフィックオブジェクト画像をレンダリングし、提示するように構成されたコンピュータシステム１が概略的に示されている。システムは、不揮発性のハードディスクドライブ又はそれに類する装置５と、揮発性の半導体ＲＡＭ４とを含むシステムランダムアクセスメモリ（ＲＡＭ）３と関連するホストプロセッサ２を含む。システム１は、通常は半導体ＲＯＭ７を基礎とし、多くの場合にコンパクトディスク装置（ＣＤ ＲＯＭ）８により補足されているシステム読み取り専用メモリ（ＲＯＭ）６を更に含む。更に、システム１は、共にラスタ方式で動作するビデオ表示装置（ＶＤＵ）又はプリンタなどの何らかの画像表示手段１０を含んでいても良い。
【００２３】
以上説明したシステム１の構成要素はバスシステム９を介して相互に接続し、ＩＢＭ ＰＣ／ＡＴ型パーソナルコンピュータやそこから派生した構成、Sun Sparc stationsなどの当該技術では良く知られているコンピュータシステムの通常動作モードで動作可能である。
【００２４】
更に、図１に示すように、画素逐次レンダリング装置２０がバス９に接続しており、本好適な実施形態では、この装置２０はバス９を介してシステム１から供給される命令及びデータを与えられた図形オブジェクトベースの記述から取り出される画素ベース画像を逐次レンダリングするように構成されている。装置２０はオブジェクト記述をレンダリングするためにシステムＲＡＭ３を利用しても良いが、レンダリング装置２０に関連して、通常は半導体ＲＡＭから構成される専用レンダリングストア構成３０を設けるのが好ましいであろう。
【００２５】
好適な実施形態の機能データ流れ図を図２に示す。この機能流れは、オブジェクトグラフィック記述１１から開始する。このオブジェクトグラフィック記述は、ホストプロセッサ２により生成されるのに適切であるように図形オブジェクトのそれらのパラメータを記述するために使用され、且つ／又は、システムＲＡＭ３に適宜格納されるか、又はシステムＲＯＭ６から適宜取り出され、且つそこから画素ベース画像をレンダリングするために画素逐次レンダリング装置２０により解釈されても良い。例えば、オブジェクト図形記述１１は、表示装置上の１点から別の点につながる直線の辺（単純なベクトル）を含むいくつかのフォーマット、又は２次元オブジェクトが直交する線を含む複数の辺により定義されるような直交辺フォーマットによる辺を伴うオブジェクトを含んでいても良い。三次スプラインなどの別のデータフォーマットを使用しても良い。オブジェクトは多数の異なる種類の辺が混合しているものとして考えられる。通常、全てのフォーマットに共通して、各々の線（直線又は曲線のいずれでも）の始まりと終わりを示す識別子が存在し、それらは、通常、走査線番号により識別されるので、曲線をレンダリングしうる特定の出力スペースを定義することになる。
【００２６】
好適な実施形態の動作を図７に示す単純な画像７８のレンダリングの例を参照しながら部分的に説明する。画像７８は２つの図形オブジェクトを含むことがわかる。特に、一部透明な青色の三角形８０が不透明な赤色の四角形９０の上に重ねてレンダリングされ、そのために、四角形９０は一部を暗くした状態になっている。図示されているように、四角形９０は、様々な画素位置（Ｘ）及び走査線位置（Ｙ）により定義される辺９２、９４、９６及び９８を含む。辺９６及び９８は走査線の上に形成されている（従って、走査線と平行である）ので、四角形９０の実際のオブジェクト記述は、図８Ａに示すように、辺９２及び９４にのみ基づくことができる。これに関連して、辺９２は画素位置（４０、３５）から始まり、画面に沿ってラスタ方向に下方へ伸び、画素位置（４０、１０５）で終わっている。同様に、辺９４は画素位置（１６０、３５）から画素位置（１６０、１０５）まで伸びている。四角形の図形オブジェクト９０の水平部分は、単に辺９２から辺９４へラスタ化方式で走査することにより得られるであろう。
【００２７】
しかし、青色の三角形のオブジェクト８０は３つのオブジェクト辺８２、８４及び８６により定義されており、それらの辺はそれぞれ三角形の頂点を定義するベクトルとしてみなされる。辺８２及び８４は画素位置（１００、２０）で始まり、それぞれ画素位置（１７０、９０）及び（３０、９０）まで伸びている。辺８６はそれら２つの画素位置の間で従来通りの左から右へのラスタ化方向に伸びている。この特定の例においては、辺８６は先に述べた辺９６及び９８と同様に水平であるので、辺８６は辺８２及び８４の関連する終点により特徴づけられるため（図８Ｂを参照）、辺８６を定義することは不可欠ではない。辺８２及び８４を記述するために使用される始めと終わりの画素位置に加えて、これらの辺は、それぞれ、関連する傾き値、この場合には、＋１と−１を有する。
【００２８】
図９は、走査線３５から始まって四角形９０がレンダリングされる方法と、辺８２及び８４が走査線３５と交差する様子を示している。図９から明らかなように、画像７８をラスタ化するためには、より高い優先順位レベルを有するオブジェクトが低い優先順位レベルのオブジェクトの「上に」レンダリングされるように、２つのオブジェクト９０及び８０の分析（resolution)が必要である。このことは、画像７８をレンダリングするために使用される辺リストレコードを表す図１０からわかる。図１０のレコードは２つのエントリ、すなわち、オブジェクトごとに１つのエントリを含み、それらのエントリは対応するオブジェクトの開始点に対応する走査線値に、ラスタレンダリングの順に配列されている。図１０に示すように、各々の辺レコードは、関連するオブジェクトの優先順位レベルと、記述すべき辺の性質に関するその他の詳細（例えば、色、傾きなど）とを有する。
【００２９】
表示リストの生成１２は、付属のＲＯＭ６及びＲＡＭ３を利用してホストプロセッサ２で実行されるソフトウェアモジュールとして実現されるのが好ましい。表示リストの生成１２は、周知の図形記述言語のいずれか１つ又は２つ以上、図形ライブラリ呼び出し又は他の何らかのアプリケーション特定フォーマットで表現されるオブジェクト図形記述を表示リストに変換する。表示リストは、通常、一般にはＲＡＭ４の中に形成されている表示リストストア１３に書き込まれるが、表示リストストアはレンダリングストア３０の中に形成されても良い。図３に示すように、表示リストストア１３はいくつかの構成要素を含むことができ、その１つは命令ストリーム１４であり、もう１つは辺情報１５であり、ラスタ画像画素データ１６を適宜含んでいても良い。
【００３０】
命令ストリーム１４は、いずれかの特定の画像において望まれる特定の図形オブジェクトをレンダリングするために画素逐次レンダリング装置２０により読み取られるべき命令として解釈可能なコードを含む。図７に示す画像の例の場合、命令ストリーム１４は、
（１）走査線２０で（何も）レンダリングしない；
（２）走査線２０で２本の青色の辺８２及び８４を追加する；
（３）走査線３５にレンダリングする
（４）走査線３５で２本の赤色の辺９２及び９４を追加する；
（５）完成までレンダリングする
という形態をとると考えられるであろう。
【００３１】
同様に、図７の例の場合の辺情報１５は、
辺８４は画素位置１００で始まり、−１の傾きで７０本の走査線と交わりつつ進む；
辺８２は画素位置１００で始まり、１の傾きで７０本の走査線と交わりつつ進む；
辺９２は画素位置４０で始まり、０の傾きで７０本の走査線と交わりつつ進む；
辺９４は画素位置１６０で始まり、０の傾きで７０本の走査線と交わりつつ進む
という情報を含むと考えられる。
【００３２】
図７はラスタ画像画素データを含んでいないので、表示リスト１３のストア部分１６に格納すべき物はない。
【００３３】
表示リストストア１３は画素逐次レンダリング装置２０により読み取られる。画素逐次レンダリング装置２０は集積回路として実現されるのが普通であるが、ホストプロセッサ２などの汎用処理装置で実行される等価のソフトウェアモジュールとして実現されても良い。画素逐次レンダリング装置２０は表示リストをラスタ画素のストリームに変換し、それらのラスタ画素のストリームは、例えば、プリンタ、表示装置又はメモリストアなどの別の装置へ供給可能である。
【００３４】
図３は、画素逐次レンダリング装置２０、表示リストストア１３及び一時レンダリングストア３０の構成を示している。画素逐次レンダリング装置２０の処理段２２は命令実行部３００と、辺処理モジュール４００と、優先順位判定モジュール５００と、塗りつぶし（fill）色判定モジュール６００と、画素合成モジュール７００と、画素出力モジュール８００とを含む。処理段で使用される一時ストア３０は、先に述べた通り、表示リストストア１３と同じ装置（例えば、磁気ディスク又は半導体ＲＡＭ）と共用されても良いし、あるいは処理速度を最適化するという目的のために個別のストアとして実現されても良い。辺処理モジュール４００は、走査線から走査線へと送り出される辺情報を保持するために辺レコードストア３２を使用する。優先順位判定モジュール５００は、各々の優先順に関する情報と、走査線がレンダリングされている間の辺の交差に関する各優先順位の現在状態とを保持するために、優先順位特性・状態テーブル３４を使用する。塗りつぶし色判定モジュール６００は、特定の位置における特定の優先順位の塗りつぶし色を判定するために要求される情報を保持するために、塗りつぶしデータテーブル３６を使用する。画素合成モジュール７００は、１つの出力画素の値を判定するために複数の優先順位からの色を要求するその画素の判定中に中間結果を保持するために、画素合成スタック３８を使用する。
【００３５】
図３の実施形態に示される処理ステップは処理パイプライン２２の形態をとる。この場合、パイプラインの各モジュールは画像データの異なる部分に対して同時に並列して実行され、それらのモジュールの間で以下で説明するようにメッセージが交換される。
【００３６】
命令実行部３００は命令ストリーム１４から命令を読み取って、それを処理し、それらの命令をメッセージにフォーマット化する。メッセージは出力線３９８を介してパイプライン２２中の他のモジュール４００、５００、６００及び７００へ転送される。本好適な実施形態では、命令ストリーム１４は次のような命令を含むであろう。
【００３７】
命令実行部３００は、通常、命令をマッピングし且つそれらを様々なモジュールに供給するためにパイプライン動作に復号するマイクロコード状態機械により形成される。あるいは、それに対応するソフトウェアプロセスを利用しても良い。
【００３８】
次に、図４を参照して走査線レンダリング動作中の辺処理モジュール４００の動作を説明する。走査線のレンダリングに要する初期条件は３つの辺レコードのリストを利用できることである。それらのリストのいずれか又は全てが空であっても良い。それらのリストは、辺情報１５から得られ、命令によりセットされる新たな辺を含む新規辺リスと４０２と、先の走査線から送り出された辺レコードを含む主辺リスと４０４と、同様に先の走査線から送り出された辺レコードを含むこぼれ辺リスト４０６である。各辺レコードは次に示すパラメータのうち１つ又は２つ以上を含んでいれば良い。
・ 現在走査線交差座標（ここではＸ座標という）、
・ この辺の現在セグメントが持続しうる走査線の本数（実施形態によってはＹ限界としても表される）を表すカウント（ここではＮＹという）、
・ 走査線を１本すぎるごとにこの辺レコードのＸ座標に加算すべき値（ここではＤＸという）、
・ 走査線を１本すぎるごとにこの辺レコードのＤＸに加算すべき値（ここではＤＤＸという）、
・ １つ又は複数の優先順位番号（Ｐ）,
・ 通常のラスタ（上下）方式で、辺が走査線と左から右へ交差するか又は右から左へ交差するかを指示する方向（ＤＩＲ）フラグ、及び
・ リスト中の次の辺セグメントのアドレス（ＡＤＤ）
３つのリスト４０２、４０４及び４０６の各々のレコードは走査線交差（Ｘ）座標の順に配列されている。これは、通常、分類プロセスにより得られ、当初は、辺情報を含めて命令実行部３００からのメッセージを受信する辺入力モジュール４０８により管理される。辺入力モジュール４０８はメッセージを出力線４９８を介してパイプライン２２を下ってモジュール５００、６００及び７００へ適宜中継する。
【００３９】
辺入力モジュール４０８は３つのリスト４０２、４０４及び４０６の各々への参照を維持すると共に、各リストからの辺データを受信する。その後、辺入力モジュール４０８は、選択されるレコードが３つの参照されたレコードの中の最小Ｘ座標を持つレコードであるように、３つの参照された辺レコードのうち１つからの１つの辺レコードを選択する。その選択された辺は１つのメッセージにフォーマット化され、辺更新モジュール４１０に送られる。また、辺のいくつかのフィールド、特に、現在Ｘ、優先順位番号、方向フラグなどを１つのメッセージにフォーマット化し、そのメッセージは辺処理モジュール４００の出力４９８としてＦＩＦＯ５１８を介して優先順位判定モジュール５００へ送信される。
【００４０】
辺を受信すると、辺更新モジュール４１０はＮＹカウントを減分し、１つ又は２つ以上の関連する辺パラメータを更新する。ＮＹカウントが０に達したならば、次のセグメントアドレスにより指示されるアドレスから新たなセグメントを読み取り、辺の次の走査線についてＸ座標を計算する。辺レコードの修正が終了すると、辺更新モジュール４１０は、辺プール４１２に新たな辺が追加されたことを信号線４１６を介して辺出力モジュール４１４に報知する。そこで、辺レコードが辺レコードストア３２に戻されて、格納される前に、辺レコードは辺出力モジュール４１４により分類される。
【００４１】
ＦＩＦＯ５１８は辺処理モジュール４００と優先順位判定モジュール５００の動作を切り離す。先に述べたテーブル３４の一部を構成する優先順位状態テーブル５０２は、各オブジェクトの優先順位に関する情報を保持するために使用される。ＦＩＦＯ５１８の大きさは、１回のアクションで走査線１本分の辺交差の辺処理モジュール４００からの受信及び優先順位状態テーブル５０２への転送をイネーブルするように定められている。これにより、優先順位判定モジュール５００は同じ画素（Ｘ）位置で複数の辺交差を正確に処理することができる。優先順位状態テーブル５０２及び優先順位データテーブル（例えば、レベルアクティべーションテーブル５３０）は、同じ画素Ｘ位置で交差メッセージを受信するたびに更新される。優先順位状態テーブル５０２の各レコードは次のような塗りつぶしパラメータを記録している。
・ この優先順位が奇数／偶数塗りつぶし規則又は非ゼロワインディング塗りつぶし規則の適用によりその内側対外側状態を判定されるべきであるか否かを指示する塗りつぶし規則フラグ；
・ この優先順位に影響を及ぼす辺との交差が起こるたびに塗りつぶし規則により指示されるように修正される塗りつぶしカウント；
・ この優先順位をクリッピング又は塗りつぶしのために使用すべきか否か及びクリップの種類（クリップイン又はクリップアウト）を指示するクリッパフラグ及びクリップ形フラグ；
・ この優先順位がそれより下のレベルを最初に計算することを要求するか否かを指示する「ニードビロー」フラグと呼ばれるフラグ。
【００４２】
図１１Ａ及び図１１Ｂは、奇数／偶数規則及び非ゼロワインディング規則の適用を示している。非ゼロワインディング規則に関して、図１１Ａは、オブジェクト７０の辺７１及び７２が下向きであるか、又は上向きであるかに従って、それらの辺に概念上の方向がどのように割り当てられるかを示す。閉じた境界を形成するために、辺は境界に沿って数珠つなぎのようにリンクされる。塗りつぶし規則（後述する）の場合に辺に与えられる方向は、セグメントが定義された順序とは無関係である。辺セグメントは、レンダリング方向に対応して、追跡される順に定義される。
【００４３】
図１１Ｂは、２つの下向きの辺７３及び７６と、３つの上向きの辺７４、７５及び７７とを有する１つのオブジェクト（星形）を示す。奇数／偶数規則は、単に、各辺が問題の走査線と交差するたびにブール値（Boolean value）をトグルし、それにより有効にオブジェクトの色をターンオン又はターンオフするだけで動作する。非ゼロワインディング規則は、交差中の辺の方向に応じて塗りつぶしカウント値を増減する。図１１Ｂでは、走査線が初めに出会う２つの辺７３及び７６は下向きの辺であるので、それらの辺と交わることにより、塗りつぶしカウントはそれぞれ＋１と、＋２に増分される。次に走査線が出会う２つの辺７４及び７７は上向きの辺であるので、塗りつぶしカウントはそれぞれ＋１と０に減分される。
【００４４】
実施形態によっては、この情報の一部が表示リスト１３及び先に説明した様々な辺リストの中の辺と関連しており、辺交差メッセージの一部として優先順位判定モジュール５００へ送信される場合がある。特に、塗りつぶし規則フラグ、クリッパフラグ、クリップ形フラグ、ニードビローフラグ及びその他の情報はこのようにして処理されれば良い。
【００４５】
図５を参照すると、優先順位更新モジュール５０６は、処理を完了するまでの走査線交差座標を記録するカウンタ５２４を維持する。これを優先順位更新モジュール５０６の現在Ｘ（current X）という。走査線の始まりにおける初期値は０である。
【００４６】
ＦＩＦＯ５１８のヘッドで受信した辺交差メッセージを検査して、優先順位更新モジュール５０６は辺交差メッセージ中のＸ交差値を現在Ｘと比較する。辺交差メッセージ中のＸ交差値が優先順位更新モジュール５０６の現在Ｘと等しければ、優先順位更新モジュールは辺交差メッセージを処理し、現在Ｘより大きければ、優先順位更新モジュールは辺交差メッセージにおけるＸ交差値と現在Ｘとの差の画素ごとに塗りつぶし指令（commands）を生成する。
【００４７】
ある画素が優先順位に関わる塗りつぶし規則に従って優先順位に適用される境界辺の内側にあり、且つ優先順位のクリップカウントが０である場合、その画素において優先順位はアクティブである。優先順位が最上のアクティブな優先順位である場合、又はその優先順位を越える全てのアクティブな優先順位の対応するニードビローフラグがセットされている場合、優先順位は露出される。このように、画素値は露出された優先順位の塗りつぶしデータのみを使用して生成される。
【００４８】
優先順位のニードビローフラグ（need-below flag）は表示リストの情報で確定され、フラグがセットされない限り、問題の優先順位より下のアクティブな優先順位がいずれもレンダリングすべき画素値に寄与しないことを画素生成システムに報知するために使用される。最終的な画素値に全く関与しないと考えられる余分な合成動作を防止するために、フラグは適宜クリアされる。
【００４９】
辺交差メッセージ中の優先順位ごとに、その優先順位により指示される優先順位状態テーブルレコードのフィールドを参照して、プロセスは、
（ｉ）現在優先順位の現在塗りつぶしカウントを記録する工程と、
（ii）（ａ）現在優先順位の塗りつぶし規則が奇数／偶数である場合、塗りつぶしカウントがその時点で０でなければ塗りつぶしカウントを０に設定し、そうでなければ０でないいずれかの値に設定するか、
（ｂ）現在優先順位の塗りつぶし規則が非ゼロワインディングである場合、塗りつぶしカウントを（辺方向フラグに応じて）増減する工程と、
（iii）新たな塗りつぶしカウントを記録した塗りつぶしカウントと比較し、一方が０であり、他方が０でない場合に、現在優先順位に対して「アクティブフラグ更新」（後述する）動作を実行する工程とを含む。
【００５０】
実施形態によっては、各辺交差メッセージに複数の優先順位を導入するのではなく、優先順位ごとに別個の辺交差メッセージを使用しても良い。
【００５１】
アクティブフラグ更新動作は、まず、現在優先順位について新たなアクティブフラグを確定することを含む。優先順位状態テーブル５０２中の優先順位の塗りつぶしカウントが０ではなく且つ優先順位のクリップカウントが０である場合、アクティブフラグは０ではなく、そうでない場合にはアクティブフラグは０である。アクティブフラグ更新動作の第２のステップでは、判定されたアクティブフラグをアクティブフラグアレイ５０８の、現在優先順位により指示される位置に格納し、更に、現在優先順位に関わる優先順位状態テーブルのニードビローフラグがゼロであれば、アクティブフラグを不透明アクティブフラグアレイ５１０の、現在優先順位により指示される位置に格納する。
【００５２】
辺交差メッセージ中のＸ交差値が優先順位更新モジュール５０６の現在Ｘより大きいとき、優先順位更新モジュール５０６は、辺交差メッセージのＸ交差値と現在Ｘとの差である、生成すべき画素の数を示すカウントを形成する。このカウントは優先順位生成メッセージとしてフォーマット化され、接続線５２０を介して優先順位生成モジュール５１６へ送信される。そこで、優先順位更新モジュール５０６は、所定の数の画素についての処理が完了したことを示す、優先順位生成モジュール５１６からの信号５２２を待つ。信号５２２を受信すると、優先順位更新モジュール５０６はその現在Ｘを辺交差メッセージ中のＸ交差値に設定し、先に説明したように処理を続ける。
【００５３】
優先順位生成モジュール５１６は、同様にテーブル３４内に形成され、各優先順位に関する情報を保持するために使用される優先順位データテーブル５０４を参照して動作する。優先順位データテーブル５０４の各レコードは、
塗りつぶしテーブルアドレス及び型、
合成演算コード及びフラグ、
この優先順位の色が所定のＹに対して一定であるか否かを記録する、「Ｘ独立（x-independent）」フラグと呼ばれるフラグを含む。
【００５４】
優先順位生成メッセージ５２０を受信すると、優先順位生成モジュール５１６は、供給されたカウントにより指示される回数にわたり「画素優先順位生成動作」（後述する）を実行し、その後、その動作を完了したことを信号５２２により優先順位更新モジュール５０６に報知する。
【００５５】
各画素優先順位生成動作は、第一に、不透明アクティブフラグアレイ５１０に対して優先順位符号器５１４（例えば、４０９６では、１２ビット優先順位符号器）を使用して、最高の不透明アクティブフラグの優先順位番号を判定する。この優先順位（もし、存在すれば）は、優先順位データテーブル５０４を索引付けするために使用され、そのようにして参照されたレコードのコンテンツは優先順位生成モジュール５１６からの塗りつぶし優先順位メッセージ出力５９８として作成され、塗りつぶし色判定モジュール６００へ送信される。更に、先のステップにより優先順位が判定されていた（すなわち、少なくとも１つの不透明アクティブフラグがセットされていた）場合、判定された優先順位を保持するが、これを「現在優先順位」という。優先順位が判定されていなかったならば、現在優先順位は０に設定される。そこで、優先順位生成モジュール５１６はアクティブフラグアレイ５０８に対して修正優先順位符号器５１２を繰り返し使用して、現在優先順位より大きい最低のアクティブフラグを判定する。そのようにして判定された優先順位（もし、存在すれば）は、優先順位データテーブル５０４を索引付けするために使用され、そのようにして参照されたレコードのコンテンツは塗りつぶし優先順位メッセージとして作成され、塗りつぶし色判定モジュール５００へ送信され（５９８）、その後、判定された優先順位は現在優先順位を更新するために使用される。判定される優先順位がなくなるまで（すなわち、アクティブフラグの中でフラグ付けされた、現在優先順位より大きい優先順位が存在しなくなるまで）、このステップは繰り返し使用される。
【００５６】
以上説明した基本動作の好ましい特徴として、優先順位生成モジュール５１６は、シーケンスの第１の画素を処理している間に塗りつぶし色判定モジュール６００へ送り出す各メッセージのＸ独立フラグの値を記録する。送り出される全てのメッセージのＸ独立フラグが指定されたものであれば、隣接する辺交差の間の画素のスパンにある全ての後続メッセージをカウント−１の単一の反復仕様と置き換えることができる。これは、反復メッセージを生成し、それをこのシーケンスにおける他の全ての処理に代えて塗りつぶし色判定モジュール６００へ送信することにより実行される。
【００５７】
上述の基本動作の別の好ましい特徴として、優先順位生成モジュール５１６は、各レベル生成メッセージの後に、最高の不透明優先順位を接続線５２２を介して優先順位更新モジュール５０６へ送信する。優先順位更新モジュール５０６はこれをストア５２６に保持する。そこで、優先順位判定モジュール５０６は、画素優先順位生成メッセージを生成する前に、メッセージ中のＸ交差点が現在Ｘより大きいこと及びメッセージ中のレベルの少なくとも１つが最高の不透明優先順位以上であることの試験を実行する。これを実行することによって、より少ない回数の画素優先順位判定動作を実行するだけで済み、より長い反復シーケンスを生成できる。
【００５８】
図１２Ａから図１２Ｅは、好適な実施形態における、アレイ５０８、５１０及び符号器５１２、５１４と共にレベルアクティべーションテーブル５３０と呼ばれる１つのテーブルに併合されている優先順位テーブル５０２及び５０４の動作を示している。図１２Ａに示すように、辺交差メッセージは辺処理モジュール４００から１本の走査線について順次受信され、優先順位の順に配列されるテーブル５３０にロードされる。この例では、辺交差メッセージは辺横断の非ゼロワインディング規則に従って増分方向を含む。優先順位テーブル５３０のエントリをいずれもセットしないことは可能である。
【００５９】
５３０で示すようなレベルアクティべーションテーブルは塗りつぶしカウントに対応する列エントリを含む。これらは非ゼロワインディング規則又は（適切であれば）奇数／偶数規則に従って辺から判定される。ニードビローフラグは優先順位の特性であり、レンダリング動作に先立って部分レベル特性としてセットされる。ニードビローフラグは、テーブル５３０がロードされるときに全ての優先順位レベルに対してセットされる。「クリップカウント」及び「塗りつぶし索引テーブル」などの他の列を使用しても良いが、この例においては、説明を簡単にするため、それらの列は省略されている。レベルがいずれもアクティブではない場合、対応するエントリは０に設定される。更に、アレイ５１０及び５０８の値は後続する辺交差を受信した後にテーブル５３０から更新される。
【００６０】
図１２Ａから明らかであるように、ここでは、明瞭を期するためにいくつかのレコードを便宜上省略してある。通常、レベルアクティべーションテーブル５３０は、優先順位の順に配列された次のレコードを含むであろう。
【００６１】
塗りつぶしカウント
クリップカウント
塗りつぶし型
アクティベーション条件及びフラグ（次のものを含む）
ニードビローフラグ
クリップ型
クリッパフラグ
図形合成動作及びフラグ（次のものを含む）
ラスタ演算コード
アルファチャネル演算コード
「発信元ポップ」フラグ
「宛先ポップ」フラグ
Ｘ独立フラグ
塗りつぶし規則
属性、及び
塗りつぶしテーブル索引
テーブル５３０のコンテンツは、優先順位判定モジュール５００で使用されない場合、画素生成のためにメッセージとして塗りつぶし色判定モジュール６００へ送信されると共に、合成動作のために画素合成モジュール７００へ送信される。テーブル５３０のコンテンツは辺交差メッセージから得られるのが好ましい。あるいは、レベルアクティべーションテーブル５３０の静的コンテンツを辺交差メッセージの受信前に事前にロードしておいても良い。
【００６２】
図１２Ａには、走査線３５（図９）の第１の辺交差が示されている。この場合、Ｐ＝１（優先順位レベル１）のとき、塗りつぶしカウントは非ゼロワインディング規則に従って辺の値に更新される。その下にオブジェクトは存在しないので、「ニードビロー」は０のレベルに設定される。
【００６３】
テーブル５３０の先行状態は設定されていなかったため、アレイ５１０及び５０８はセットされないままであり、優先順位符号器５１４は優先順位を出力できない。このことは優先順位生成モジュール５１６により解釈され、優先順位生成モジュール５１６は、走査線３５の初めのブランクの部分である「オブジェクトなし」優先順位（例えば、Ｐ＝０）に対してカウントｎ＝４０（画素）を出力する。
【００６４】
図１２Ｂは、走査線（図９）の第２の辺交差が受信されるときの配列を示す。塗りつぶしカウントが更新される。そこで、アレイ５１０及び５０８はテーブル５３０からの先行最高レベルによって設定される。この時点で、モジュール５１６はカウントｎ＝４５を出力し、Ｐ＝１は半透明の三角形８０との交差前の不透明の赤色オブジェクト９０の辺９６を表現している。
【００６５】
図１２Ｃは、図９の走査線３５の第３の辺交差が受信されるときの配列を示す。尚、非ゼロワインディング規則であるために塗りつぶしカウントは下方へ調整されている。現在辺交差を受信する前に有効であったオブジェクトは不透明ではないので、修正優先順位符号器５１２を使用して、最高アクティブレベルとして優先順位Ｐ＝２を選択し、これは現在値としてｎ＝（１１５−８５）＝３０について出力される。
【００６６】
図１２Ｄは、図９の走査線３５の最終辺交差が受信されるときの配列を示す。尚、先に変更されたＰ＝２の「ニードビロー」はアクティブアレイ５０８へ既に転送されているため、優先順位符号器はｎ＝（１６０−１１５）＝４５画素について現在の値Ｐ＝１を出力できる。
【００６７】
図１２Ｅは、辺交差をそれ以上利用できないときの結果を示し、ｎ＝（１８０−１６０）＝２０画素についてＰ＝０の出力を提供している。
【００６８】
このように、優先順位モジュール５００は１本の走査線の全ての画素について画素のカウントと、対応する優先順位表示値とを出力する。
【００６９】
次に、図６を参照して塗りつぶし色判定モジュール６００の動作を説明する。優先順位判定モジュール５００から入力される、塗りつぶしデータセットメッセージ、反復メッセージ、塗りつぶし優先順位メッセージ、画素終わりメッセージ及び走査線終わりメッセージを含むメッセージ５９８は、まず、塗りつぶしルックアップ制御モジュール６０４へ送信される。塗りつぶしルックアップ制御モジュール６０４は、塗りつぶし色判定モジュール６００の様々な構成要素により使用されるべき現在Ｘ位置カウンタ６１４及び現在Ｙ位置カウンタ６１６を維持している。
【００７０】
走査線終わりメッセージを受信すると、塗りつぶしルックアップ制御モジュール６０４は現在Ｘカウンタ６１４を０にリセットし、現在Ｙカウンタ６１６を増分する。その後、走査線終わりメッセージは画素合成モジュール７００へ送信される。
【００７１】
塗りつぶしデータセットメッセージを受信すると、塗りつぶしルックアップ制御モジュール６０４はそのデータを塗りつぶしデータテーブル３６の指定場所６０２に格納する。
【００７２】
反復メッセージを受信すると、塗りつぶしルックアップ制御モジュール６０４は現在Ｘカウンタ６１４を反復メッセージからのカウントの分だけ増分する。その後、反復メッセージは画素合成モジュール７００へ送信される。
【００７３】
画素終わりメッセージを受信すると、塗りつぶしルックアップ制御モジュール６０４は同様に現在Ｘカウンタ６１４を増分し、その後、画素終わりメッセージは画素合成モジュール７００へ送信される。
【００７４】
塗りつぶし優先順位メッセージを受信すると、塗りつぶしルックアップ制御モジュール６０４は、
− 塗りつぶし優先順位メッセージからの塗りつぶし型を使用して、塗りつぶし優先順位メッセージからのテーブルアドレスにおいてレコードサイズを選択すること（レコードサイズは３６で判定される通り）；
− 前記の塗りつぶしテーブルを使用して、塗りつぶしデータテーブル３６から１つのレコードを選択すること；
− 塗りつぶし優先順位メッセージからの塗りつぶし型を使用して、塗りつぶし色の生成を実行するためのサブモジュールを判定し、選択すること（サブモジュールは図形を処理するためのラスタ画像モジュール６０６、フラットカラーモジュール６０８、直線ランプカラーモジュール６１０及び不透明度タイルモジュール６１２を含むであろう）；
− 判定されたレコードを選択されたサブモジュール６０６~６１２に供給すること；
− 選択されたサブモジュール６０６~６１２が供給されたデータを使用して、色及び不透明度値を判定すること；
− 判定された色及び不透明度を塗りつぶし色メッセージからのその他の情報、すなわち、ラスタ演算コード、アルファチャネル演算コード、発信元ポップフラグ及び宛先ポップフラグと組み合わせて、接続線６９８を介して画素合成モジュール７００へ送信される色合成メッセージを形成すること
を含む動作を実行する。
【００７５】
画素色成分は、通常は画素ごとに３２ビットを提供する８ビット精度を有する赤色、緑色、青色及び不透明度の４つの成分である。しかし、その代わりに、不透明度の示唆を伴うシアン、マゼンタ、黄色及び黒色の４つの成分、あるいはその他の数多くの周知の色表現のいずれか１つを使用しても良い。
【００７６】
次に、画素合成モジュール７００の動作を説明する。塗りつぶし色判定モジュール６００から入力される、反復メッセージ、色合成メッセージ、画素終わりメッセージ及び走査線終わりメッセージを含むメッセージは順次処理される。
【００７７】
反復メッセージ又は走査線終わりメッセージを受信すると、画素合成モジュール７００はそのメッセージをそれ以上の処理を加えずに出力ＦＩＦＯ７０２へ送信する。
【００７８】
色合成メッセージを受信すると、画素合成モジュール７００は、通常、色合成メッセージからのラスタ演算及びアルファチャネル演算に従って、色合成メッセージからの色及び不透明度を画素合成スタック３８からポップされた色及び不透明度と組み合わせる。次に、その結果を画素合成スタック３８に押し戻す。色合成メッセージの受信時に実行される処理については後に説明する。
【００７９】
画素終わりメッセージを受信すると、画素合成モジュール７００は画素合成スタック３８から色及び不透明度をポップするが、例外として、スタック３８が空である場合には、不透明白色値を使用する。その結果得られた色及び不透明度は画素出力メッセージとして形成され、このメッセージは画素出力モジュール８００へ送信される。
【００８０】
次に、画素出力モジュール８００の動作を説明する。画素出力ＦＩＦＯから入力される、画素出力メッセージ、反復メッセージ及び走査線終わりメッセージが読み取られ、順次処理される。
【００８１】
画素出力メッセージを受信すると、画素出力モジュール８００はその画素を格納すると共に、画素を出力部へ送信する。反復メッセージを受信すると、最前に格納されていた画素が反復メッセージからのカウントにより指定される回数だけ出力部８９８へ送信される。走査線終わりメッセージを受信すると、画素出力モジュール８００はそのメッセージを出力部へ送り出す。
【００８２】
出力部８９８は、画素画像データを利用する何らかの装置に必要に応じて接続可能である。そのような装置としては、ビデオ表示装置又はプリンタなどの出力装置、あるいはハードディスクやラインストア、バンドストア又はフレームストアを含む半導体ＲＡＭ等のメモリ格納装置、又はコンピュータネットワークなどがある。しかし、以上の説明から明らかであるように、レンダリングプロセス中に画素画像データの中間格納を必要とせずに精巧な図形記述言語により要求される機能性を余す所なく発揮して図形オブジェクトをレンダリングすることができる方法及び装置が説明されている。
【００８３】
次に図１３Ａ及び図１３Ｂを参照すると、カラー動作モード１３００及びグレイスケール動作モード１３０２でそれぞれ動作するときの画素逐次レンダリング装置２０のデータ流れが示されている。命令実行部３００はホストプロセッサ２からの命令に応答して、塗りつぶし順位判定モジュール５００、塗りつぶし色判定モジュール６００、画素合成モジュール７００及び画素出力モジュール８００に、カラー動作モード又はグレイスケール動作モードのいずれかで動作するように命令する。
【００８４】
カラー動作モード中、塗りつぶし色判定モジュール６００、画素合成モジュール７００及び画素出力モジュール８００は、４つの画素成分を有するカラー画素データを４つの出力チャネル１３０４からそれぞれ出力する。出力チャネル１３０４はバス（２４ビット又は３２ビット幅）を構成しているのが好ましい。カラー画素データは、例えば、不透明度成分を伴う又は伴わないその色成分、例えば、赤色成分、緑色成分、青色成分に分解されるか、又はシアン、マゼンタ、黄色及び黒色の各成分に分解される。それらの色成分はそれぞれ８ビットから構成されているのが好ましく、それぞれ対応する４つの出力チャネル１３０４を介して出力される。カラー動作モード中、塗りつぶし色判定モジュール６００、画素合成モジュール及び画素出力モジュール８００は４つの出力チャネル１３０４を介して、クロックサイクルごとに１画素ずつ同期して出力する。
【００８５】
グレイスケールレンダリングモード中、塗りつぶし色判定モジュール６００、画素合成モジュール７００及び画素出力モジュール８００は、８ビットのグレイスケール画素成分のみを有する画素データを４つの出力チャネル１３０４から出力する。このモード中、塗りつぶし色判定モジュール６００、画素合成モジュール７００及び画素出力モジュール８００はクロックサイクルごとに４つの連続する画素をラスタ順に同期してそれぞれ対応する４つの出力チャネル１３０４を介して出力する。
【００８６】
カラー画素逐次レンダリング装置２０はグレイスケールレンダリングを２つの異なる方法で加速する。優先順位判定モジュール５００はカラー動作モードの場合は反復指令と塗りつぶし指令を生成するが、加速グレイスケール動作モードの場合には、それらの指令の動作はグレイスケールレンダリングを加速するように修正される。
【００８７】
これら２つの指令、すなわち、塗りつぶし指令及び反復指令の詳細と動作については、以下にカラー動作モードに関して説明する。
【００８８】
反復指令は優先順位判定モジュール５００により１つのパラメータを伴って生成される。このパラメータは、同一の画素データを有する画素の数を指定し、この指令は画素出力モジュール８００に至る経路にある下流側の全てのモジュールへ送信される。指定の画素位置についてこの指令が下流側のモジュールにより処理され終わったならば、それらの下流側モジュールは次の画素位置へ進む。
【００８９】
カラー動作モード中、塗りつぶし指令は、オブジェクト識別子、塗りつぶし型、塗りつぶしアドレス、合成動作、画素属性、及びオブジェクトがこの画素に関する最終オブジェクトであるか、すなわち、この画素に関してアクティブである全てのオブジェクトのうち最上のオブジェクトであるか否かを指示するためのフラグ（last_object）などのいくつかのパラメータを有する。処理すべき現在画素位置に寄与する各オブジェクトの色を得るために、この指令は塗りつぶし色判定モジュール６００により翻訳されなければならない。塗りつぶし指令についてlast_objectフラグがＴＲＵＥにセットされており且つその塗りつぶし指令が現在画素位置について塗りつぶし色判定モジュール６００により処理され終わっている場合、塗りつぶし色判定モジュール６００は次の画素位置へ処理を進める。しかし、last_objectフラグがＦＡＬＳＥにセットされていた場合には、塗りつぶし色判定モジュール６００は現在画素位置を処理し続ける。
【００９０】
反復指令は、現在画素に続く１つ又は複数の後続画素がＸ座標独立オブジェクト、例えば、フラットカラー又はｙ方向の直線ランプカラーの色塗りつぶしを伴うオブジェクトを有する場合に作成される。そのような状況の下では、塗りつぶし色判定モジュール６００は先頭の画素について塗りつぶし指令を処理し、その後、下流側の全てのモジュールに反復指令を送信するだけで良い。反復すべき画素の数は、優先順位判定モジュール５００が次に受信する辺交差Ｘ"座標と、現在辺交差のＸ座標とによって決まる。すなわち、反復指令のパラメータは（Ｘ"−（Ｘ＋１））に等しい。
【００９１】
１つ又は複数のオブジェクトがビットマップ、もしくは画素ごとに異なる潜在色データを有する他の何らかの色塗りつぶし動作を有する場合、優先順位判定モジュール５００は塗りつぶし指令をオブジェクトがアクティブである画素ごとに送る以外の選択肢を持たない。その代わりに、塗りつぶし色判定モジュール６００は画素ごとの最終画素色を処理する。
【００９２】
次に図１４を参照すると、複数のオブジェクトから構成される画像の一例の表現が示されている。オブジェクトＡの左の辺は画素位置６、７、８及び９で走査線５４、５５、５６及び５７とそれぞれ交差している。また、オブジェクトＡの右の辺は画素位置１３、１６、１８及び２１で走査線５４、５５、５６及び５７とそれぞれ交差している。オブジェクトＢの左の辺は画素位置１０、９、９及び７で走査線５４、５５、５６及び５７とそれぞれ交差している。また、オブジェクトＢの右の辺は画素位置１８、１８、１９及び１９で走査線５４、５５、５６及び５７とそれぞれ交差している。オブジェクトＡは、Ｘ方向の画素位置とは無関係である、すなわち、Ｘから独立したフラットカラーを有する。これに対し、オブジェクトＢは、画素がＸに依存するようなビットマップである。オブジェクトＡ及びオブジェクトＢは、画素１０から１３を含む走査線５４、画素９から１６を含む走査線５５、画素９から１８を含む走査線５６及び画素９から１９を含む走査線５７の画素について共通してアクティブである。オブジェクトＢの優先順位はオブジェクトＡより低いので、オブジェクトＡはこの画素についてアクティブである全てのオブジェクトのうち最上位置のオブジェクトである。
【００９３】
カラー動作モードにおいて、図１４に示す例の第１の走査線及び最終走査線（５４及び５７）に対する優先順位判定モジュール５００の入力部４９８及び出力部５９８における指令は次の通りである。
・ 走査線５４（入力指令）：
1. edge_crossing:x=6;object=A;edge=UP;priority=11;
2. edge crossing:x=10;object=B;edge=UP;priority=15;
3. edge crossing:x=13;object=A;edge=DOWN;priority=11
4. edge crossing:x=18;object=B;edge=DOWN;priority=15
・ 走査線５４（出力指令）：
1. repeat 4
2. fill:object=A;type=flat;fill_address=20;last_object=true;
3. repeat 3
4. fill:object=B;type=bitmap;fill_address=32;last_object=false;
5. fill:object=A;type=flat;fill_address=20;last_object=true;
6. fill:object=B;type=bitmap;fill_address=32;last_object=false;
7. fill:object=A;type=flat;fill_address=32;last_object=true;
8. fill:object=B;type=bitmap;fill_address=32;last_object=false;
9. fill:object=A;type=flat;fill_address=20;last_object=true;
10. fill:object=B;type=bitmap;fill_address=32;last_object=false;
11. fill:object=A;type=flat;fill_address=20;last_object=true
12. fill:object=B;type=bitmap;fill_address=32;last_object=true
13. fill:object=B;type=bitmap;fill_address=32;last_object=true;
14. fill:object=B;type=bitmap;fill_address=32;last_object=true;
15. fill:object=B;type=bitmap;fill_address=32;last_object=true;
16. fill:object=B;type=bitmap;fill_address=32;last_object=true;
・ 走査線５７（入力指令）：
1. edge_crossing:x=7;object=B;edge=UP;priority=15;
2. edge crossing:x=9;object=A;edge=UP;priority=11;
3. edge crossing:x=19;object=B;edge=DOWN;priority=15
4. edge crossing:x=21;object=A;edge=DOWN;priority=11
・ 走査線５7（出力指令）：
1. repeat 5
2. fill:object=B;type=bitmap;fill_address=32;last_object=true;
3. fill:object=B;type=bitmap;fill_address=32;last_object=true
4. fill:object=B;type=bitmap;fill_address=32;last_object=false;
5. fill:object=A;type=flat;fill_address=20;last_object=true;
6. fill:object=B;type=bitmap;fill_address=32;last_object=false;
7. fill:object=A;type=flat;fill_address=20;last_object=true;
8. fill:object=B;type=bitmap;fill_address=32;last_object=false;
9. fill:object=A;type=flat;fill_address=20;last_object=true;
10. fill:object=B;type=bitmap;fill_address=32;last_object=false;
11. fill:object=A;type=flat;fill_address=20;last_object=true
12. fill:object=B;type=bitmap;fill_address=32;last_object=false
13. fill:object=A;type=flat;fill_address=20;last_object=true;
14. fill:object=B;type=bitmap;fill_address=32;last_object=false;
15. fill:object=A;type=flat;fill_address=20;last_object=true;
16. fill:object=B;type=bitmap;fill_address=32;last_object=false;
17. fill:object=A;type=flat;fill_address=20;last_object=true;
18. fill:object=B;type=bitmap;fill_address=32;last_object=false;
19. fill:object=A;type=flat;fill_address=20;last_object=true;
20. fill:object=B;type=bitmap;fill_address=32;last_object=false;
21. fill:object=A;type=flat;fill_address=20;last_object=true;
22. fill:object=B;type=bitmap;fill_address=32;last_object=false;
23. fill:object=A;type=flat;fill_address=20;last_object=true;
24. fill:object=B;type=bitmap;fill_address=32;last_object=falst;
25. fill:object=A;type=flat;fill_address=20;last_object=true;
26. fill:object=A;type=flat;fill_address=20;last_object=true;
27. repeat 1
先に述べた通り、辺交差メッセージ（入力指令）はその他にもパラメータを含んでいて良い。例えば、図１２Ａに関連する説明を参照。簡単にするため、図１４に関連してそれらのパラメータのうちいくつかを示してあるにすぎない。
【００９４】
fill_addressパラメータは、塗りつぶし色判定モジュールにより、この特定のオブジェクトと関連する色値を処理するために使用される。塗りつぶし色判定モジュール６００へ送信される塗りつぶし指令ごとに、対応するカラーデータはＲＧＢＯ又はＣＭＹＫいずれかのフォーマットで生成される。
【００９５】
グレイスケール動作モード中、優先順位判定モジュールと塗りつぶし色判定モジュールの双方は塗りつぶし指令ごとに４画素までの分解能で動作するので、４つの出力チャネルを効率良く利用できる。これにより、グレイスケールレンダリング時に１つの出力チャネルしか使用しない場合と比較して、グレイスケールレンダリング速度は４倍まで改善される。
【００９６】
優先順位判定モジュール５００はグレイスケールレンダリングモード中も、カラー動作モード中も、Ｘ独立領域が現れたときに、依然として塗りつぶし指令に続いて繰り返しが起こるという点で同様に動作する。この場合、塗りつぶし色判定モジュール６００と画素合成モジュール７００は１つの出力チャネル１３０４から１つの画素を出力するだけで良く、その後に反復指令が続く。しかし、画素出力モジュール８００は反復指令を使用するのではなく、後に画素出力装置１０が使用することを考慮して、全ての画素データを出力することが望ましい。加えて、グレイスケール動作モード中、画素出力モジュール８００は４つの出力チャネルを介して４つまでの画素をそれぞれ同時に供給するのが好ましい。グレイスケール動作モード中、画素出力モジュール８００は１つの画素を受信し、次に反復指令を受信すると、各出力チャネル１３０４のうち４つまでのチャネルを介して適切な数の画素を同時に送り出す。５つ以上の画素がある場合には、反復指令は４つ１組の画素のグループを順次出力させる。反復指令は画素を所定の順序でチャネルから出力させる。例えば、画素は最も低いチャネル、次に低いチャネルと続き、最後にもっとも上のチャネルに至るという順序で出力される。すなわち、反復指令が２つの画素を送り出す場合、それらの画素は最も低いチャネルと次に低いチャネルから同時に出力される。反復すべき画素の量は常に４の倍数であるとは限らないので、画素出力モジュール８００は画素出力モジュール８００の送り出しサイクル中の有効チャネルの数を指示するための出力信号も供給する。後者の例では、それらの信号は下２つのチャネルが有効であり、上２つのチャネルは無効であることを指示することになるであろう。
【００９７】
通常はビットマップデータが存在することにより発生するＸ従属領域の場合、優先順位判定モジュールは、グレイスケールレンダリング中に４つまでの画素について１つの塗りつぶし指令を送信する。これは、塗りつぶし指令が適用されるラスタ順の連続する画素の数を識別する「no_pixel」と呼ばれる塗りつぶし指令の別のパラメータにより実現される。１つの塗りつぶし指令中に表現できる画素の数は、次の辺交差の前に残留している画素の数によって決まる。次の辺交差がレンダリング中である現在ｘ位置から５画素以上離れて起こる場合には、発行される塗りつぶし指令は４画素について有効である。残る画素については別の塗りつぶし指令を発行しなければならない。そうでない場合には、塗りつぶし指令中の有効画素の数は単に辺交差前の残留画素の数である。更に、塗りつぶし指令は、その塗りつぶし指令が適用される画素を所定の順序で出力チャネル１３０４から出力させる。例えば、画素は最も低いチャネル、次に低いチャネルと続き、最後に最も上のチャネルに至るような順序で出力される。従って、塗りつぶし指令パラメータ「no_pixel」＝２である場合、対応する２つの画素は最も低いチャネルと次に低いチャネルから同時に出力されることになる。
【００９８】
そこで、塗りつぶし色判定モジュール６００は所定の塗りつぶし指令の有効画素ごとに同時に結果として得られた色を処理する。これは、隣接する画素のビットマップデータが通常はローカルメモリの隣接するアドレススペースに格納されているために可能である。更に、塗りつぶし色判定モジュール６００は、通常、性能を改善するために、ローカルメモリから１画素分を超える量のデータを取り出す。
【００９９】
また、塗りつぶし色判定モジュール６００は、複数の画素を伴う１つの塗りつぶし指令の結果として、複数の「色合成メッセージ」を生成することができる。これは、キャッシュが複数画素のビットマップデータの一部しか含んでおらず、その結果、通常は極めてゆっくりとした速度で、まず、ローカルメモリから取り出されなければならないために有用である。この状況においては、モジュールは第１の色合成メッセージを修正画素有効性値と共に下流側のモジュールへ送信する。後続する画素データを利用できる場合、同じ塗りつぶし指令から残る画素位置について第２のメッセージが生成される。
【０１００】
更に下流側へ下って、画素合成モジュール７００の動作は変化がなく、チャネルが有効画素を含むか又はグレイスケールレンダリングの場合にないかに関わらず、利用できる全てのチャネルに対して合成動作を単純に実行できる。しかし、画素データバッファリングの動作を簡単にするために画素出力モジュール８００は、有効画素が常に最下位チャネルから始まるように保証するという意味で一種のハウスキーピングを実行することを望む場合もある。
【０１０１】
再び図１４に戻って説明を続けると、加速グレイスケールレンダリングの場合の第１の走査線及び最終走査線（５４及び５７）についての優先順位判定モジュール５００の入力部及び出力部における指令（command）は、グレイスケール動作モードの場合と比較して次のようになる。
・ 走査線５４（入力指令）：
1. edge_crossing:x=6;object=A;edge=UP;priority=11;
2. edge crossing:x=10;object=B;edge=UP;priority=15;
3. edge crossing:x=13;object=A;edge=DOWN;priority=11;
4. edge crossing;x=18;object=B;edge=DOWN;priority=15;
・ 走査線５４（出力指令）：
1. repeat 4
2. fill:object=A;type=flat;fill_address=20;last_object=true;no_pixel=1;
3. repeat 3
4. fill:object=B;type=bitmap;fill_address=32;last_object=false;no_pixel=4;
5. fill:object=A;type=flat;fill_address=20;last_object=true;no_pixel=4;
6. fill:object=B;type=bitmap;fill_address=32;last_object=true;no_pixel=4;
7. fill:object=B;type=bitmap;fill_address=32;last_object=true;no_pixel=1;
8． 走査線５７（入力指令）：
1. edge_crossing:x=7;object=B;edge=UP;priority=15;
2. edge crossing:x=9;object=A;edge=UP;priority=11;
3. edge crossing:x=19;object=B;edge=DOWN;priority=15;
4. edge crossing;x=21;object=A;edge=DOWN;priority=11;
・ 走査線５７（出力指令）：
1. repeat 5
2. fill:object=B;type=bitmap;fill_address=32;last_object=true;no_pixel=2;
3. fill:object=B;type=bitmap;fill_address=32;last_object=false;no_pixel=4
4. fill:object=A;type=flat;fill_address=20;last_object=true;no_pixel=4;
5. fill:object=B;type=bitmap;fill_address=32;last_object=false;no_pixel=4;
6. fill:object=A;type=flat;fill_address=20;last_object=true;no_pixel=4;
7. fill:object=B;type=bitmap;fill_address=32;
last_object=false;no_pixel=3;
8. fill:object=A;type=flat;fill_address=20;last_object=true;no_pixel=3
9. fill:object=A;type=flat;fill_address=20;last_object=true;no_pixel=1
10. repeat 1
所定の２本の走査線に関する例から性能の向上がはっきりと見て取れる。２本の走査線（５４及び５７）において、塗りつぶし指令の数は、それぞれ、１４から５へ、２５から８へと減っており、非常に大きな改善であることがわかる。
【０１０２】
以下の表は、先に挙げた例の走査線５４における初めの３つの指令に関してカラーレンダリングとグレースケールレンダリングの場合の画素出力モジュールの動作を示す。尚、カラーレンダリングの場合、チャネル３,２,１及び０はそれぞれ不透明度、青色、緑色及び赤色のチャネルとして機能することに注意する。
【０１０３】
【表１】
【０１０４】
【表２】
【０１０５】
次に、図１５及び図１６に示すフローチャートを参照して画素逐次レンダリング装置２０を動作させる方法を説明する。この方法は、塗りつぶし色判定モジュール６００、画素合成モジュール７００及び画素出力モジュール８００をカラー動作モード又は加速グレイスケール動作モードで動作するように構成することができる。方法は、ホストプロセッサから命令実行部３００を介して受信される命令に応答してこれらのモードの一方を動作させるように構成される。これら２つのモードにおいて、方法は塗りつぶし色判定モジュール６００、画素合成モジュール７００及び画素出力モジュール８００の各々に対して指令を発生する。それらの指令はほぼ類似しているが、モードによって異なる。カラー動作モードで動作しているとき、方法はカラー動作モード指令に応答して、１つの画素の４つの画素成分を塗りつぶし色判定モジュール６００、画素合成モジュール７００及び画素出力モジュール８００の４つの出力チャネル１３０４をそれぞれ介して出力する。加速グレイスケール動作モードで動作しているとき、方法はグレイスケール動作モード指令に応答して、４つのまでの連続する画素をラスタ順に塗りつぶし色判定モジュール６００、画素合成モジュール７００及び画素出力モジュール８００のそれぞれ対応する４つの出力チャネル１３０４を介してクロックサイクルごとに同期させて出力する。
【０１０６】
そこで図１５を参照すると、カラー動作モードで動作しているときに指令を生成する方法のフローチャートが示されている。指令を生成する方法１５００はレンダリングすべき画像の走査線ごとに実行される。説明を容易にするため、ここでは現在走査中の走査線と呼ばれる１本の走査線に関してのみ指令を発生する場合に関連して方法を説明する。
【０１０７】
方法１５００は、現在走査中の走査線において、変数current_xを１に設定することにより開始される（１５０２）。この変数は、考慮すべき現在画素の位置を指示するカウンタとして機能する。先に述べた通り、辺交差メッセージ（入力指令）は走査線交差（Ｘ）座標の順にＦＩＦＯ５１８を介して優先順位判定モジュール５００へ送信される。方法１５００は、それらの辺交差メッセージをその走査線交差（Ｘ）座標の順に処理する。それらの辺交差メッセージは図１４を参照して説明した、例えば、edge_crossing:x＝６;object＝A;edge＝UP;priority＝１１及びその他のフィールドのようなフォーマットをとっていても良い。
【０１０８】
方法１５００は、ステップ１５０４で辺交差メッセージを検索し、ループの各々のパス中に走査線交差（Ｘ）座標の順にそれらのメッセージを処理するループ（１５０４−１５１２−１５０４、１５０４−１５２４−１５０４）の形態をとっている。同じ走査線交差座標（Ｘ）を有する複数の辺交差メッセージが存在する場合、方法は、ループの１回のパス中に処理するためにそれら複数の辺交差メッセージの全てを検索する（１５０４）。言い換えれば、ループの現在パス中に、方法１５００は、走査線の順で、ループの最前のパス中に検索された辺交差メッセージの（Ｘ）座標の次に来る同じ（Ｘ）座標を有する１つ又は複数の辺交差メッセージを獲得する（１５０４）。
【０１０９】
開始ステップ１５０２の後、方法１５００は、走査線の順で初めて現れた走査線交差座標（Ｘ）を有する辺交差メッセージを獲得する（１５０４）。全てが走査線の順で初めて現れる同じ交差（Ｘ）座標を有する複数の辺交差メッセージが存在する場合、方法はそれら初めて現れた全ての辺交差メッセージを獲得する（１５０４）。また、方法１５００は、先に説明したように、現在Ｘ座標についてその時点で検索された辺交差メッセージを使用してレベルアクティべーションテーブル５３０を更新する。最初の辺交差メッセージの（Ｘ）座標が２より大きい場合、方法１５００は更に指令「repeat X−2」を塗りつぶし色判定モジュール６００、画素合成モジュール７００及び画素出力モジュール８００へ送信する。この反復指令のフラグは、画素X＝１からX−１にわたるオブジェクトが存在せず且つそれらの画素位置において背景をペイントしても良いことを指示するようにＯＮにセットされているのが好ましい。
【０１１０】
ステップ１５０４の後、方法１５００は、その時点で検索されていた辺交差メッセージを利用して、フラグテーブル５０８及び５１０に格納されている「アクティブフラグ」及び「不透明アクティブフラグ」を更新する（１５０６）。「アクティブフラグ」及び「不透明アクティブフラグ」がどのようにして更新されるかについては、先に詳細に説明してある。
【０１１１】
次に、方法１５００は、current_xの現在値に位置する画素について「アクティブフラグ」がＯＮにセットされている優先順位オブジェクトが存在するか否かを判定する（１５０８）。それら１つ又は複数のオブジェクトの全ての関連する「アクティブフラグ」がＯＦＦにセットされているならば、それらのオブジェクトは現在画素に全く寄与しないので、決定ブロック１５０８はＦＡＬＳＥ（ノー）を戻し、方法１５００はステップ１５１６へ進む。
【０１１２】
そこで、走査線の順で次の辺交差メッセージのＸ座標の値をnew_Xとし、変数current_xの現在値をcurrent_xとするとき、（new_X−current_x）＞０であるならば、方法１５００は指令「repeat（new_X−current_x）」を送信する（１５１６）。この場合、反復指令の前記フラグは、current_xからnew_Xに位置する画素にわたるオブジェクトは存在せず且つそれらの画素位置で背景をペイントしても良いことを指示するようにＯＮにセットされている。次に、方法はステップ１５１８へ進む。
【０１１３】
ステップ１５１８中、方法１５００は変数current_xを走査線の順で次の辺交差メッセージのＸ座標に等しいnew_Xに設定する。次に、方法はステップ１５０４に戻り、ループの次のパス中に処理するためにnew_Xで辺交差を有する次の辺交差メッセージを獲得する（１５０４）。
【０１１４】
これに対し、current_xの現在値に位置する画素についてオブジェクトの「アクティブフラグ」のいずれか１つがＯＮになっている場合には、決定ブロック１５０８はＴＲＵＥ（イエス）を戻し、方法１５００はステップ１５１０へ進む。
【０１１５】
ステップ１５１０中、方法１５００はcurrent_xの現在値に位置する画素について塗りつぶし指令を生成し始める。このステップ１５１０中、方法１５００は、「アクティブフラグ」がＯＮにセットされ且つ最高「不透明アクティブフラグ」がＯＮにセットされているオブジェクト以下の優先順位を有する、「アクティブフラグ」がＯＮにセットされているオブジェクトを優先順位の順に判定する。それらの塗りつぶし指令のパラメータのデータは、それまでに検索されていた辺交差メッセージに含まれる情報から間接的に得られる。特に、塗りつぶし指令のパラメータはcurrent_xの現在値に関する更新後のレベルアクティべーションテーブル５３０から獲得される。この生成ステップ１５１０中、方法１５００は、current_xの現在値に位置する画素について２つ以上の塗りつぶし指令が存在する場合、更にそれらの塗りつぶし指令の優先順位を判定する。すなわち、current_xの現在値に位置する画素の塗りつぶし指令はそのオブジェクト優先順位の順に生成される。尚、この生成ステップ１５１０は１つの画素についてのみ１つ又は複数の塗りつぶし指令を生成することに注意すべきである。それらの塗りつぶし指令（出力指令）は図１４を参照して先に説明したようなフォーマットをとっていても良い。例えば、１つの画素の塗りつぶし指令はfill:object＝B;type＝bitmap;fill_address＝32;last_object＝false;fill:object＝A;type＝flat;fill_address＝20;last_object＝trueであっても良い。パラメータlast_object＝trueは、この塗りつぶし指令が現在画素に対する最終塗りつぶし指令であることを示す。オブジェクトの塗りつぶし指令はＸ独立フラグ（例えば、型）を更に含むのが好ましい。先に述べた通り、このフラグは、このアクティブオブジェクトの色が所定のＹ（すなわち、走査線）に対して一定であるか否かを指示する。
【０１１６】
生成ステップ１５１０の後、方法１５００は、先に生成された塗りつぶし指令と関連するオブジェクトが型パラメータに関してＸ独立であるか否かを判定する（１５１２）。
【０１１７】
決定ブロック１５１２が先に生成された塗りつぶし指令と関連する全てのオブジェクトはＸ独立であると判定した場合、方法１５００は、それらの先に生成された塗りつぶし指令を塗りつぶし色判定モジュール６００、画素合成モジュール７００及び画素出力モジュール８００へ送信する（１５１４）。ステップ１５１４の後、方法１５００は変数current_xを１増分し（１５１５）、ステップ１５１６へ進む。
【０１１８】
そこで、走査線の順で次の辺交差メッセージのＸ座標の値をnew_Xとし、変数current_xの現在値をcurrent_xとするとき、（new_X−current_x）＞０であるならば、方法１５００は指令「repeat（new_X−current_x）」を送信する（１５１６）。この場合、反復指令の前記フラグはＯＦＦにセットされる。これは、current_xの現在値に対する塗りつぶし指令を後続する位置についても反復すべきであることを指示する。次に、方法はステップ１５１８へ進む。しかし、値new_X−current_xが０に等しい場合には、反復指令は送信されず、方法は直接にステップ１５１８へ進む。
【０１１９】
そこで、方法１５００は変数current_xをnew_Xの値に設定し（１５１８）、ステップ１５０４に戻って、ループの次のパス中に、new_Xで辺交差を有する次の辺交差メッセージを処理する。
【０１２０】
これに対し、決定ブロック１５１２が先に生成された塗りつぶし指令の１つ又は複数のオブジェクトはＸ従属であると判定した場合には、方法１５００はステップ１５２０へ進む。このような状況は、例えば、オブジェクトの１つがビットマップである場合に起こるであろう。すなわち、決定ブロック１５１２がＦＡＬＳＥ（ノー）を戻したならば、方法１５００はcurrent_xに位置する画素に対して塗りつぶし指令（出力指令）を送信する（１５２０）。それらの指令は塗りつぶし色判定モジュール６００、画素合成モジュール７００及び画素出力モジュール８００へ送信される。
【０１２１】
送信ステップ１５２０の後、方法１５００は変数current_xを１増分し（１５２２）、決定ブロック１５２４へ進む。
【０１２２】
決定ブロック１５２４中、方法１５００は、変数current_xの現在値が走査線の順で次に処理されるべき辺交差メッセージのＸ座標であるnew_Xと等しいか否かを検査する。決定ブロック１５２４がcurrent_xの現在値はnew_Xと等しくないと判定したならば、方法１５００はステップ１５２０に戻る。ステップ１５２０では、current_xの新たな値に位置する画素に対して、先のステップ１５２０のパス中に送信されたのと同じ塗りつぶし指令を再び送信する。
【０１２３】
これに対し、決定ブロック１５２４がＴＲＵＥ（イエス）を戻した場合には、方法１５００はステップ１５０４に戻り、ループの次のパス中に次の辺交差メッセージを処理する。
【０１２４】
処理すべき辺交差メッセージがなくなった時点で、方法１５００は現在走査線に関する処理を終了する（図示せず）。
【０１２５】
次に図１６を参照すると、カラー動作モードで動作しているときに指令を生成する方法のフローチャートが示されている。指令を生成する方法１６００は、レンダリングすべき画像の走査線ごとに実行される。説明を容易にするため、ここでは現在走査中の走査線と呼ばれる１本の走査線についてのみ指令を発生する場合について方法を説明する。
【０１２６】
方法１６００は、現在走査中の走査線について、変数current_xを１に設定することにより始まる（１６０２）。この変数は、考慮すべき現在画素の位置を指示するカウンタとして機能する。先に述べた通り、辺交差メッセージ（入力指令）は走査線交差（Ｘ）座標の順にＦＩＦＯ５１８を介して優先順位判定モジュール５００へ送信される。方法１６００はそれらの辺交差メッセージをその走査線交差（Ｘ）座標の順に処理する。それらの辺交差メッセージは、図１４を参照して説明した、edge_crossing:x＝６;object＝A;edge＝UP;priority＝１１及びその他のフィールドのようなフォーマットをとっていても良い。
【０１２７】
方法１６００は、辺交差メッセージを検索し（１６０４）、ループの各々のパス中に走査線交差（Ｘ）座標の順にそれらのメッセージを処理するループ（１６０４−１６１２−１６０４、１６０４−１６４２−１６０４）の形態をとっている。同じ走査線交差座標（Ｘ）を有する複数の辺交差メッセージが存在する場合、方法は、ループの１回のパス中に処理するためのそれら複数の辺交差メッセージの全てを検索する（１６０４）。言い換えれば、ループの現在パス中、方法１６００は、走査線の順で、ループの最前のパス中に検索された辺交差メッセージの（Ｘ）座標の次に来る同じ（Ｘ）座標を有する１つ又は複数の辺交差メッセージを獲得する（１６０４）。
【０１２８】
開始ステップ１６０２の後、方法１６００は、走査線の順で最初に現れた走査線交差座標（Ｘ）を有する辺交差メッセージを獲得する（１６０４）。全て走査線の順で最初に現れた同じ交差（Ｘ）座標を有する複数の辺交差メッセージが存在する場合、方法はそれら最初の辺交差メッセージの全てを獲得する（１６０４）。また、方法１６００は、先に説明したように、現在Ｘ座標についてその時点で検索されている辺交差メッセージを使用してレベルアクティべーションテーブル５３０を更新する。最初の辺交差メッセージの（Ｘ）座標が２より大きい場合、方法１６００は更に指令「repeat X−2」を塗りつぶし色判定モジュール６００、画素合成モジュール７００及び画素出力モジュール８００へ送信する。初期反復指令は、画素X＝１からX−１にわたるオブジェクトが存在しないことを指示する。この反復指令のフラグは、画素X＝１からX−１にわたるオブジェクトが存在せず且つそれらの画素位置で背景をペイントしても良いことを指示するＯＮにセットされているのが好ましい。
【０１２９】
ステップ１６０４の後、方法１６００は、その時点で検索されている辺交差メッセージを利用して、フラグテーブル５０８及び５１０に格納されている「アクティブフラグ」及び「不透明アクティブフラグ」を更新する（１６０６）。「アクティブフラグ」及び「不透明アクティブフラグ」がどのようにして更新されるかについては先に詳細に説明してある。
【０１３０】
次に、方法１６００は、current_xの現在値に位置する画素について「アクティブフラグ」がＯＮにセットされている優先順位オブジェクトが存在するか否かを判定する（１６０８）。それら１つ又は複数のオブジェクトの全ての関連する「アクティブフラグ」がＯＦＦにセットされていたならば、それらのオブジェクトは現在画素に全く寄与しないので、決定ブロック１６０８はＦＡＬＳＥ（ノー）を戻し、方法１６００はステップ１６１６へ進む。
【０１３１】
そこで、走査線の順で次の辺交差メッセージのＸ座標の値をnew_Xとし、変数current_xの現在値をcurrent_xとするとき、（new_X−current_x）＞０であるならば、方法１６００は指令「repeat（new_X−current_x）」を送信する（１６１６）。この場合、反復指令の前記フラグは、current_xからnew_Xに位置する画素にわたるオブジェクトは存在せず且つそれらの画素位置で背景をペイントしても良いことを指示するＯＮにセットされている。次に、方法はステップ１６１８に進む。
【０１３２】
しかし、値new_X−current_xが０に等しい場合には、反復指令は送信されず、方法は直接にステップ１６１８へ進む。
【０１３３】
ステップ１６１８中、方法１６００は変数current_xを走査線の順で次の辺交差メッセージのＸ座標に等しいnew_Xに設定する。次に、方法１６００はステップ１６０４に戻り、方法１６００は、ループの次のパス中に処理するためにnew_Xで辺交差を有する次の辺交差メッセージを獲得する（１６０４）。
【０１３４】
これに対し、current_xの現在値に位置する画素についてオブジェクトの「アクティブフラグ」のいずれか１つがＯＮにセットされている場合には、決定ブロック１６０８はＴＲＵＥ（イエス）を戻し、方法１６００はステップ１６１０へ進む。
【０１３５】
ステップ１６１０中、方法１６００はcurrent_xの現在値に位置する画素に対して塗りつぶし指令を生成し始める。このステップ１６１０中、方法１６００は、優先順位の順に、「アクティブフラグ」がＯＮにセットされ且つ最高「不透明アクティブフラグ」がＯＮにセットされているオブジェクト以下の優先順位を有する、「アクティブフラグ」がＯＮにセットされているオブジェクトを判定する。それらの塗りつぶし指令のパラメータのデータは、それまでに検索されていた辺交差メッセージに含まれる情報から間接的に得られる。特に、塗りつぶし指令のパラメータは、current_xの現在値について更新後のレベルアクティべーションテーブル５３０から獲得される。この生成ステップ１６１０中、current_xの現在値に位置する画素に対する塗りつぶし指令が２つ以上存在する場合、方法１６００は更に塗りつぶし指令の優先順位を判定する。すなわち、current_xの現在値に位置する画素に対する塗りつぶし指令はそのオブジェクト優先順位の順に生成される。尚、この生成ステップ１６１０は１つの画素についてのみ１つ又は複数の塗りつぶし指令を生成することに注意すべきである。それらの塗りつぶし指令（出力指令）は先に図１４を参照して説明したようなフォーマットをとっていても良い。例えば、１つの画素に対する塗りつぶし指令はfill:object＝B;type＝bitmap;fill_address＝32;last_object＝false;no_pixel＝Z;fill:object＝A;type＝flat;fill_address＝20;last_object＝true;no_pixel＝Zであっても良い。パラメータlast_object＝trueは、この塗りつぶし指令が現在画素に対する最終塗りつぶし指令であることを示す。パラメータno_pixelは、現在画素から始めてこの塗りつぶし指令が適用される連続する画素の数を示す１から４までの数字である。このパラメータの値は方法１６００中、塗りつぶし指令を送信する直前に判定される。１つのオブジェクトに関する塗りつぶし指令はＸ独立フラグ（例えば、型）を更に含むのが好ましい。先に述べた通り、このフラグは、このアクティブオブジェクトの色が所定のＹ（すなわち、走査線）に対して一定であるか否かを指示する。
【０１３６】
生成ステップ１６１０の後、方法１６００は、ループの現在パス中に生成された塗りつぶし指令と関連するオブジェクトが型パラメータに関してＸ独立であるか否かを判定する（１６１２）。
【０１３７】
決定ブロック１６１２がループの現在パス中に生成された塗りつぶし指令と関連する全てのオブジェクトはＸ独立であると判定した場合、方法１６００はそれらの塗りつぶし指令を塗りつぶし色判定モジュール６００、画素合成モジュール７００及び画素出力モジュール８００へ送信する（１６１４）。それらの塗りつぶし指令を送信する（１６１４）前に、方法１６００は塗りつぶし指令のパラメータno_pixelを１に設定する。ステップ１６１４の後、方法１６００は変数current_xを１増分し（１６１５）、ステップ１６１６へ進む。
【０１３８】
そこで、走査線の順で次の辺交差メッセージのＸ座標の値をnew_Xとし、変数current_xの現在値をcurrent_xとするとき、（new_X−current_x）＞０であるならば、方法１６００は指令「repeat（new_X−current_x）」を送信する（１６１６）。この場合、反復指令の前記フラグはＯＦＦにセットされている。これは、current_xの現在値についての塗りつぶし指令を後続する画素位置に対して反復すべきであることを指示する。次に、方法はステップ１６１８へ進む。しかし、値new_X−current_xが０に等しい場合には、反復指令は送信されず、方法は直接にステップ１６１８へ進む。
【０１３９】
次に、方法１６００は変数current_xをnew_Xの値に設定し（１６１８）、ステップ１６０４に戻って、ループの次のパス中に、new_Xで辺交差を有する次の辺交差メッセージを処理する。
【０１４０】
これに対し、決定ブロック１６１２がループの現在パス中に生成された塗りつぶし指令の１つ又は複数のオブジェクトはＸ従属であると判定した場合には、方法１６００は決定ブロック１６２６へ進む。このような状況は、例えば、オブジェクトの１つがビットマップである場合に起こるであろう。すなわち、決定ブロック１６１２がＦＡＬＳＥ（ノー）を戻した場合、方法１６００は決定ブロック１６２６へ進む。
【０１４１】
決定ブロック１６２６は、値current_x＋3がnew_Xより小さいか否かを判定する。決定ブロック１６２６がＴＲＵＥ（イエス）を戻した場合、方法１６００は４つの画素について有効である１つ又は複数の塗りつぶし指令を送信する（１６２８）。すなわち、方法１６００は、ループの現在パス中に生成された塗りつぶし指令を塗りつぶし色判定モジュール６００、画素合成モジュール７００及び画素出力モジュール８００へ送信する（１６２８）。この送信（１６２８）に先立って、方法１６００はそれらの塗りつぶし指令のno_pixelパラメータを４に設定する。ステップ１６２８の後、方法は変数current_xを４増分し（１６３０）、決定ブロック１６２６に戻る。決定ブロック１６２６が再びＴＲＵＥ（イエス）を戻した場合には、方法１６００は、no_pixelパラメータを４に設定した状態でループの現在パス中に生成されたもう１組の塗りつぶし指令を送信する（１６２８）。
【０１４２】
これに対し、決定ブロック１６２６がＦＡＬＳＥ（ノー）を戻した場合には、方法１６００は決定ブロック１６３２へ進む。決定ブロック１６３２は、値current_x＋2がnew_Xより小さいか否かを判定する。決定ブロック１６３２がＴＲＵＥ（イエス）を戻した場合、方法１６００はループの現在パス中に生成された塗りつぶし指令を塗りつぶし色判定モジュール６００、画素合成モジュール７００及び画素出力モジュール８００へ送信する（１６３４）。この送信（１６３４）に先立って、方法１６００はそれらの塗りつぶし指令のno_pixelパラメータを３に設定する。ステップ１６３４の後、方法は変数current_xを３増分し（１５３０）、決定ブロック１６３２に戻る。
【０１４３】
決定ブロック１６３２がＦＡＬＳＥ（ノー）を戻した場合、方法１６００は決定ブロック１６３６へ進む。決定ブロック１６３６は、値current_x＋１がnew_Xより小さいか否かを判定する。決定ブロック１６３６がＴＲＵＥ（イエス）を戻した場合、方法１６００は２つの画素について有効である１つ又は複数の塗りつぶし指令を送信する（１６３８）。すなわち、方法１６００は、ループの現在パス中に生成された塗りつぶし指令を塗りつぶし色判定モジュール６００、画素合成モジュール７００及び画素出力モジュール８００へ送信する（１６３８）。この送信（１６３８）に先立って、方法１６００はそれらの塗りつぶし指令のno_pixelパラメータを２に設定する。ステップ１６３８の後、方法は変数current_xを２増分し（１６４０）、決定ブロック１６３６に戻る。
【０１４４】
決定ブロック１６３６がＦＡＬＳＥ（ノー）を戻した場合には、方法１６００は決定ブロック１６４２に戻る。決定ブロック１６４２は、値current_xがnew_Xより小さいか否かを判定する。決定ブロック１６４２がＴＲＵＥ（イエス）を戻した場合、方法１６００は１つの画素について有効である１つ又は複数の塗りつぶし指令を送信する（１６４４）。すなわち、方法１６００は、ループの現在パス中に生成された塗りつぶし指令を塗りつぶし色判定モジュール６００、画素合成モジュール７００及び画素出力モジュール８００へ送信する（１６４４）。この送信（１６４４）に先立って、方法１６００はそれらの塗りつぶし指令のno_pixelパラメータを１に設定する。ステップ１６４４の後、方法は変数current_xをnew_Xに設定し（１６４６）、ステップ１６０４に戻って、次の辺交差メッセージを処理する。
【０１４５】
これに対し、決定ブロック１６４２がＦＡＬＳＥ（ノー）を戻した場合には、方法１６００は変数current_xをnew_Xに設定し（１６４６）、ステップ１６０４に戻って、次の辺交差メッセージを処理する。
【０１４６】
処理すべき辺交差メッセージがなくなった時点で、現在走査線について方法１６００の処理は終了する（図示せず）。
【０１４７】
カラー動作モードで動作しているとき、塗りつぶし色判定モジュール６００は塗りつぶし指令を獲得し、塗りつぶし指令のパラメータに含まれている情報を利用して画素を生成する。塗りつぶし色判定モジュール６００は、カラー動作モードで動作しているとき、そのような画素を一度に１つずつ出力カラーチャネルを介して出力する。それらの画素は複数の色成分を有し、それらの色成分は塗りつぶし色判定モジュール６００のそれぞれ対応するカラー出力チャネルから出力される。また、塗りつぶし色判定モジュール６００は反復指令をカラー出力チャネルを介して画素出力モジュール８００へ送信する。画素出力モジュール８００は反復指令を受信すると、先に出力された画素を反復指令のパラメータに従った回数だけ繰り返し出力する。塗りつぶし色判定モジュール６００は塗りつぶし指令ごとに１つの画素を生成し、走査線の現在画素位置に対して複数の塗りつぶし指令が存在する場合には、塗りつぶし色判定モジュール６００は走査線のその現在位置について複数の画素を生成し、優先順位の順にそれらの画素を一度に１つずつ出力チャネルから出力する。塗りつぶし色判定モジュール６００が走査線の現在画素位置について複数の画素を生成する場合、塗りつぶし色判定モジュール６００は、更に、それらの生成画素を合成するための合成情報を含む合成メッセージを生成する。合成メッセージは、元の塗りつぶし指令から得られる合成情報から構成される。それらの合成メッセージは塗りつぶし色判定モジュール６００からカラー出力チャネルを介して画素合成モジュール７００へも送信される。
【０１４８】
加速グレイスケール動作モードで動作しているとき、塗りつぶし色判定モジュール６００は塗りつぶし指令を獲得し、塗りつぶし指令のパラメータに含まれている情報を利用して、１つの色成分を有する画素を生成する。それらの画素は、その後、塗りつぶし指令のパラメータno_pixelに応じて塗りつぶし色判定モジュール６００のそれぞれのカラー出力チャネルから出力される。例えば、塗りつぶし指令のパラメータno_pixel＝４である場合、塗りつぶし色判定モジュール６００の４つの出力チャネルから４つの画素が同時に出力される。また、塗りつぶし色判定モジュール６００は、塗りつぶし指令に含まれる合成情報を使用して合成メッセージを送信する。それらの合成メッセージは塗りつぶし色判定モジュール６００から出力チャネルを介して画素合成モジュール７００へ送信される。同様に、それらの合成メッセージはno_pixelなどのパラメータを含む場合があり、それにより、画素合成モジュール７００から出力チャネルを介していくつかの画素が同時に出力されることになる。加速グレイスケール動作モードでは、塗りつぶし色判定モジュール６００は、更に、カラー動作モードの場合と同様に反復指令を送信する。
【０１４９】
【産業上の適用可能性】
以上の説明から、本発明の実施形態はコンピュータグラフィックス及びプリントの分野に適用可能であることが明白である。
【０１５０】
以上、本発明の実施形態を説明したが、それらの実施形態は単なる例であって、限定的な意味を持たず、本発明の趣旨から逸脱せずに実施形態に対して変形及び／又は変更を実施することは可能である。
【図面の簡単な説明】
【図１】好適な実施形態によるコンピュータシステムを示す概略ブロック構成図である。
【図２】好適な実施形態の機能データ流れを示すブロック構成図である。
【図３】好適な実施形態の画素逐次レンダリング装置と、関連する表示リスト及び一時ストアとを示す概略ブロック構成図である。
【図４】図２の辺処理モジュールの概略機能図である。
【図５】図２の優先順位判定モジュールの概略機能図である。
【図６】図２の塗りつぶしデータ判定モジュールの概略機能図である。
【図７】好適な実施形態の動作を説明するための一例として使用される２オブジェクト画像を示す図である。
【図８Ａ】、
【図８Ｂ】図７のオブジェクトのベクトル辺を示す図である。
【図９】図７の画像の数本の走査線のレンダリングを示す図である。
【図１０】図７のカラーレンダリングを実行するときに出力される様々なモジュールにおける処理画素のスナップショットを示す図である。
【図１１Ａ】、
【図１１Ｂ】偶数／奇数及び非ゼロワインディング塗りつぶし規則を示す図である。
【図１２Ａ】、
【図１２Ｂ】、
【図１２Ｃ】、
【図１２Ｄ】、
【図１２Ｅ】図５の構成により実現される優先塗りつぶしルーチンを示す図である。
【図１３Ａ】、
【図１３Ｂ】カラー動作モード及びグレイスケール動作モード中の画素逐次レンダリング装置の機能データ流れを示す図である。
【図１４】複数のオブジェクトから構成される画像の一例を表す図である。
【図１５】カラー動作モードで動作しているときの指令生成方法を示すフローチャートである。
【図１６】加速グレイスケール動作モードで動作しているときの指令生成方法を示すフローチャートである。
【発明の属する技術分野】
本発明はデジタル画像の画素を処理する装置に関し、特にグレイスケールグラフィックオブジェクトをラスタ画素画像にレンダリングすることに関する。
【０００２】
【背景技術】
オブジェクトを利用するグラフィックスシステムの多くは、ページ又は画面の画素ベース画像を保持するためにフレームストア又はページバッファを利用している。通常、図形オブジェクトの輪郭を計算し、埋め込み（fill)して、フレームストアに書き込む。２次元図形の場合、他のオブジェクトの前方に現れるオブジェクトは単に背景オブジェクトの後にフレームストアに書き込まれるだけであるので、画素ごとに背景と置き換えられる。当該技術分野においては、これは一般に「ペインターのアルゴリズム」として知られている。オブジェクトは最も後ろの位置にあるオブジェクトから最も前方のオブジェクトまで優先順位に従って考慮され、通常、各オブジェクトは走査線の順にラスタ化され、画素は各走査線に沿って逐次ランとしてフレームストアに書き込まれる。
【０００３】
この技法には本質的に２つの問題がある。第１の問題は、フレームストアの全ての画素に対して高速ランダムアクセスが要求されることである。これは、考慮される新たなオブジェクトがいずれもフレームストア内のいずれかの画素に影響を及ぼす可能性があるためである。このため、フレームストアは通常は半導体ランダムアクセスメモリ（ＲＡＭ）に保持されている。高分解能のカラープリンタの場合、要求されるＲＡＭの量は非常に多く、通常は１００メガバイトを越えてしまうので、そのようなメモリはコストもかかり、高速で動作させるのは困難である。第２の問題は、多くのペイント（レンダリング）された画素が、後に現れるオブジェクトにより上書きペイント（再レンダリング）されるという点である。以前のオブジェクトに対する画素のペイントは、時間の無駄である。
【０００４】
フレームストアが大型になるという問題を克服する１つの方法は、「バンディング」を使用する方法である。バンディングを使用すれば、ある１つの時点でメモリに存在するのはフレームストアのごく一部ということになる。描き出すべき全てのオブジェクトは「表示リスト」に保持される。画像全体は先に説明したようにレンダリングされるが、存在するフレームストアの一部分の外側をペイント（レンダリング）しようとする画素ペイント（レンダリング）動作は「クリップアウト」される。全てのオブジェクトが描かれた後、フレームストアのその一部分をプリンタ（又は他の何らかの場所）へ送信し、フレームストアの別の部分を選択して、このプロセスを繰り返す。この技法には不都合な点がある。例えば、描くべきオブジェクトを何度も、すなわち、バンドごとに一度ずつ考慮しなければならない。バンドの数が増えるにつれて、レンダリングを要求するオブジェクトの検査を繰り返す回数も増加する。従って、バンディングの技法は上書きペイント（over-painting）の不利益の問題を解決するものではない。
【０００５】
他のいくつかのグラフィックシステムは画像を走査線の順に考慮する。この場合にも、描き出すべき全てのオブジェクトは表示リストに保持される。走査線ごとに、その走査線と交わるオブジェクトを優先順位に従って考慮し、オブジェクトごとに、オブジェクトの辺の交差点の間の画素のスパンをラインストアにセットする。この技法もフレームストアの問題を克服するが、上書きペイントの問題は依然として残る。
【０００６】
フレームストアが大型になるという問題と、上書きペイントの問題を共に克服する技法は他にもある。そのような技法の１つによれば、各走査線を順次生成する。この場合にも、描くべき全てのオブジェクトは表示リストに保持される。走査線ごとに、その走査線と交わるオブジェクトの辺を走査線との交差点の座標の小さい順に保持する。それらの交差点、すなわち、辺交差を順次考慮し、アクティブフラグのアレイをトグルするために使用する。走査線上で関心のあるオブジェクト優先順位ごとに１つのアクティブフラグが存在する。考慮される各対の辺の間で、アクティブフラグに対して優先順位符号器を使用して、どの優先順位が最高であるかを判定し、且つ２つの辺の間のスパンの画素に対してその優先順位と関連する色を使用することにより、第１の辺と次の辺との間に位置する画素ごとのカラーデータを生成する。次の走査線を準備する中で、各辺の性質に従って各辺の交差点の座標を更新する。この更新の結果として誤って分類されることになった隣接する辺を交換する。また、新たな辺を辺のリストに併合する。
【０００７】
この技法は、フレームストア又はラインストアがなく、上書きペインティングもなく、オブジェクトの優先順位が順位Ｎ時間（Ｎは優先順位の数である）ではなく、一定の順位時間で扱われるという著しく大きな利点を有する。
【０００８】
このようなグラフィックシステムの出力は、通常、クロックサイクルごとにトグルするような画素カラーデータを搬送するためのバス（２４ビット又は３２ビット幅）から構成されている。画素データバスに付随して、画素の属性及び特性を示すいくつかの制御信号がある。画素カラーデータは、通常、その色成分、すなわち、赤、緑、青の成分から形成されており、不透明度チャネル（すなわち、シアン、マゼンタ、黄色及び黒の各チャネル）を伴う場合と、伴わない場合がある。
【０００９】
グレイスケールレンダリングの場合、システムは、より狭いデータパス（すなわち８ビット幅）を有するか、又は、カラーグラフィックシステムの使用可能な４つのチャネルのうちの１つを使用する。
【００１０】
【発明の概要】
本発明の目的は、既存の構成の１つ又は複数の欠点をほぼ克服すること又は少なくとも軽減することである。
【００１４】
本発明の１つの態様によれば、デジタル画像の画素を処理する画像処理装置であって、
複数のカラー出力チャネルを有する画像処理装置を第１の動作モード又は第２の動作モードで動作するように構成するホストプロセッサを具備し、前記画像処理装置は、
前記第１の動作モード中、複数の画素色成分を有する１つのカラー画素を生成し、且つ生成された各画素の前記複数の画素色成分を、対応する前記カラー出力チャネルから出力することにより、前記生成された複数のカラー画素を出力する塗りつぶしモジュールと、
前記第２の動作モード中、塗りつぶし指令が適用されるラスタ順の連続する画素位置の数であって、１から前記カラー出力チャネルの数に等しい最大数まで変化できる数を指示するパラメータをそれぞれ含む１つ又は複数の塗りつぶし指令を生成するモジュールとを具備し、
前記塗りつぶしモジュールは、前記第２の動作モード中、１つ又は複数の前記画素位置に対して１つ又は複数の前記塗りつぶし指令に応答して、塗りつぶし指令の数及び前記塗りつぶし指令のパラメータに従って決まる数の、各々が１つの画素色成分を有する画素を生成し、且つ複数の前記画素を、前記複数の前記カラー出力チャネルから出力することを特徴とする画像処理装置が提供される。
【００１６】
本発明の別な態様によれば、デジタル画像の画素を処理する画像処理装置において、
画像処理装置を第１の動作モード又は第２の動作モードで動作するように構成するホストプロセッサを具備し、前記画像処理装置は、
前記第１の動作モード中、対応する画素位置に対して１つ又は複数の塗りつぶし指令を生成する優先順位モジュールと、
前記第１の動作モード中、前記画素位置に対して１つ又は複数の対応する前記塗りつぶし指令に応答して、複数の画素色成分を有する１つの画素を出力する塗りつぶしモジュールとを具備し、
前記優先順位モジュールは、前記第２の動作モード中、塗りつぶし指令が適用されるラスタ順の連続する画素位置の数であって、１から前記カラー出力チャネルの数に等しい最大数まで変化できる数を指示するパラメータをそれぞれ含む１つ又は複数の塗りつぶし指令を生成し、且つ
前記塗りつぶしモジュールは、前記第２の動作モード中、１つ又は複数の前記画素位置に対して１つ又は複数の前記塗りつぶし指令に応答して、塗りつぶし指令の数及び前記塗りつぶし指令のパラメータに従って決まる数の、各々が１つの画素色成分を有する複数の画素を生成し、且つ生成された複数の画素を、対応する複数の前記カラー出力チャネルから出力することを特徴とする画像処理装置が提供される。
【００２０】
【実施形態】
次に、添付の図面を参照して本発明のいくつかの好ましい実施形態を説明する。
【００２１】
添付の図面のいずれか１つ又は２つ以上においてステップ及び／又は特徴を参照する場合、本明細書においては、特に指示のない限り、便宜上、同じ図中符号を付されているステップ及び／又は特徴は同じ機能又は動作を有するものとする。
【００２２】
そこで図１を参照すると、コンピュータグラフィックオブジェクト画像をレンダリングし、提示するように構成されたコンピュータシステム１が概略的に示されている。システムは、不揮発性のハードディスクドライブ又はそれに類する装置５と、揮発性の半導体ＲＡＭ４とを含むシステムランダムアクセスメモリ（ＲＡＭ）３と関連するホストプロセッサ２を含む。システム１は、通常は半導体ＲＯＭ７を基礎とし、多くの場合にコンパクトディスク装置（ＣＤ ＲＯＭ）８により補足されているシステム読み取り専用メモリ（ＲＯＭ）６を更に含む。更に、システム１は、共にラスタ方式で動作するビデオ表示装置（ＶＤＵ）又はプリンタなどの何らかの画像表示手段１０を含んでいても良い。
【００２３】
以上説明したシステム１の構成要素はバスシステム９を介して相互に接続し、ＩＢＭ ＰＣ／ＡＴ型パーソナルコンピュータやそこから派生した構成、Sun Sparc stationsなどの当該技術では良く知られているコンピュータシステムの通常動作モードで動作可能である。
【００２４】
更に、図１に示すように、画素逐次レンダリング装置２０がバス９に接続しており、本好適な実施形態では、この装置２０はバス９を介してシステム１から供給される命令及びデータを与えられた図形オブジェクトベースの記述から取り出される画素ベース画像を逐次レンダリングするように構成されている。装置２０はオブジェクト記述をレンダリングするためにシステムＲＡＭ３を利用しても良いが、レンダリング装置２０に関連して、通常は半導体ＲＡＭから構成される専用レンダリングストア構成３０を設けるのが好ましいであろう。
【００２５】
好適な実施形態の機能データ流れ図を図２に示す。この機能流れは、オブジェクトグラフィック記述１１から開始する。このオブジェクトグラフィック記述は、ホストプロセッサ２により生成されるのに適切であるように図形オブジェクトのそれらのパラメータを記述するために使用され、且つ／又は、システムＲＡＭ３に適宜格納されるか、又はシステムＲＯＭ６から適宜取り出され、且つそこから画素ベース画像をレンダリングするために画素逐次レンダリング装置２０により解釈されても良い。例えば、オブジェクト図形記述１１は、表示装置上の１点から別の点につながる直線の辺（単純なベクトル）を含むいくつかのフォーマット、又は２次元オブジェクトが直交する線を含む複数の辺により定義されるような直交辺フォーマットによる辺を伴うオブジェクトを含んでいても良い。三次スプラインなどの別のデータフォーマットを使用しても良い。オブジェクトは多数の異なる種類の辺が混合しているものとして考えられる。通常、全てのフォーマットに共通して、各々の線（直線又は曲線のいずれでも）の始まりと終わりを示す識別子が存在し、それらは、通常、走査線番号により識別されるので、曲線をレンダリングしうる特定の出力スペースを定義することになる。
【００２６】
好適な実施形態の動作を図７に示す単純な画像７８のレンダリングの例を参照しながら部分的に説明する。画像７８は２つの図形オブジェクトを含むことがわかる。特に、一部透明な青色の三角形８０が不透明な赤色の四角形９０の上に重ねてレンダリングされ、そのために、四角形９０は一部を暗くした状態になっている。図示されているように、四角形９０は、様々な画素位置（Ｘ）及び走査線位置（Ｙ）により定義される辺９２、９４、９６及び９８を含む。辺９６及び９８は走査線の上に形成されている（従って、走査線と平行である）ので、四角形９０の実際のオブジェクト記述は、図８Ａに示すように、辺９２及び９４にのみ基づくことができる。これに関連して、辺９２は画素位置（４０、３５）から始まり、画面に沿ってラスタ方向に下方へ伸び、画素位置（４０、１０５）で終わっている。同様に、辺９４は画素位置（１６０、３５）から画素位置（１６０、１０５）まで伸びている。四角形の図形オブジェクト９０の水平部分は、単に辺９２から辺９４へラスタ化方式で走査することにより得られるであろう。
【００２７】
しかし、青色の三角形のオブジェクト８０は３つのオブジェクト辺８２、８４及び８６により定義されており、それらの辺はそれぞれ三角形の頂点を定義するベクトルとしてみなされる。辺８２及び８４は画素位置（１００、２０）で始まり、それぞれ画素位置（１７０、９０）及び（３０、９０）まで伸びている。辺８６はそれら２つの画素位置の間で従来通りの左から右へのラスタ化方向に伸びている。この特定の例においては、辺８６は先に述べた辺９６及び９８と同様に水平であるので、辺８６は辺８２及び８４の関連する終点により特徴づけられるため（図８Ｂを参照）、辺８６を定義することは不可欠ではない。辺８２及び８４を記述するために使用される始めと終わりの画素位置に加えて、これらの辺は、それぞれ、関連する傾き値、この場合には、＋１と−１を有する。
【００２８】
図９は、走査線３５から始まって四角形９０がレンダリングされる方法と、辺８２及び８４が走査線３５と交差する様子を示している。図９から明らかなように、画像７８をラスタ化するためには、より高い優先順位レベルを有するオブジェクトが低い優先順位レベルのオブジェクトの「上に」レンダリングされるように、２つのオブジェクト９０及び８０の分析（resolution)が必要である。このことは、画像７８をレンダリングするために使用される辺リストレコードを表す図１０からわかる。図１０のレコードは２つのエントリ、すなわち、オブジェクトごとに１つのエントリを含み、それらのエントリは対応するオブジェクトの開始点に対応する走査線値に、ラスタレンダリングの順に配列されている。図１０に示すように、各々の辺レコードは、関連するオブジェクトの優先順位レベルと、記述すべき辺の性質に関するその他の詳細（例えば、色、傾きなど）とを有する。
【００２９】
表示リストの生成１２は、付属のＲＯＭ６及びＲＡＭ３を利用してホストプロセッサ２で実行されるソフトウェアモジュールとして実現されるのが好ましい。表示リストの生成１２は、周知の図形記述言語のいずれか１つ又は２つ以上、図形ライブラリ呼び出し又は他の何らかのアプリケーション特定フォーマットで表現されるオブジェクト図形記述を表示リストに変換する。表示リストは、通常、一般にはＲＡＭ４の中に形成されている表示リストストア１３に書き込まれるが、表示リストストアはレンダリングストア３０の中に形成されても良い。図３に示すように、表示リストストア１３はいくつかの構成要素を含むことができ、その１つは命令ストリーム１４であり、もう１つは辺情報１５であり、ラスタ画像画素データ１６を適宜含んでいても良い。
【００３０】
命令ストリーム１４は、いずれかの特定の画像において望まれる特定の図形オブジェクトをレンダリングするために画素逐次レンダリング装置２０により読み取られるべき命令として解釈可能なコードを含む。図７に示す画像の例の場合、命令ストリーム１４は、
（１）走査線２０で（何も）レンダリングしない；
（２）走査線２０で２本の青色の辺８２及び８４を追加する；
（３）走査線３５にレンダリングする
（４）走査線３５で２本の赤色の辺９２及び９４を追加する；
（５）完成までレンダリングする
という形態をとると考えられるであろう。
【００３１】
同様に、図７の例の場合の辺情報１５は、
辺８４は画素位置１００で始まり、−１の傾きで７０本の走査線と交わりつつ進む；
辺８２は画素位置１００で始まり、１の傾きで７０本の走査線と交わりつつ進む；
辺９２は画素位置４０で始まり、０の傾きで７０本の走査線と交わりつつ進む；
辺９４は画素位置１６０で始まり、０の傾きで７０本の走査線と交わりつつ進む
という情報を含むと考えられる。
【００３２】
図７はラスタ画像画素データを含んでいないので、表示リスト１３のストア部分１６に格納すべき物はない。
【００３３】
表示リストストア１３は画素逐次レンダリング装置２０により読み取られる。画素逐次レンダリング装置２０は集積回路として実現されるのが普通であるが、ホストプロセッサ２などの汎用処理装置で実行される等価のソフトウェアモジュールとして実現されても良い。画素逐次レンダリング装置２０は表示リストをラスタ画素のストリームに変換し、それらのラスタ画素のストリームは、例えば、プリンタ、表示装置又はメモリストアなどの別の装置へ供給可能である。
【００３４】
図３は、画素逐次レンダリング装置２０、表示リストストア１３及び一時レンダリングストア３０の構成を示している。画素逐次レンダリング装置２０の処理段２２は命令実行部３００と、辺処理モジュール４００と、優先順位判定モジュール５００と、塗りつぶし（fill）色判定モジュール６００と、画素合成モジュール７００と、画素出力モジュール８００とを含む。処理段で使用される一時ストア３０は、先に述べた通り、表示リストストア１３と同じ装置（例えば、磁気ディスク又は半導体ＲＡＭ）と共用されても良いし、あるいは処理速度を最適化するという目的のために個別のストアとして実現されても良い。辺処理モジュール４００は、走査線から走査線へと送り出される辺情報を保持するために辺レコードストア３２を使用する。優先順位判定モジュール５００は、各々の優先順に関する情報と、走査線がレンダリングされている間の辺の交差に関する各優先順位の現在状態とを保持するために、優先順位特性・状態テーブル３４を使用する。塗りつぶし色判定モジュール６００は、特定の位置における特定の優先順位の塗りつぶし色を判定するために要求される情報を保持するために、塗りつぶしデータテーブル３６を使用する。画素合成モジュール７００は、１つの出力画素の値を判定するために複数の優先順位からの色を要求するその画素の判定中に中間結果を保持するために、画素合成スタック３８を使用する。
【００３５】
図３の実施形態に示される処理ステップは処理パイプライン２２の形態をとる。この場合、パイプラインの各モジュールは画像データの異なる部分に対して同時に並列して実行され、それらのモジュールの間で以下で説明するようにメッセージが交換される。
【００３６】
命令実行部３００は命令ストリーム１４から命令を読み取って、それを処理し、それらの命令をメッセージにフォーマット化する。メッセージは出力線３９８を介してパイプライン２２中の他のモジュール４００、５００、６００及び７００へ転送される。本好適な実施形態では、命令ストリーム１４は次のような命令を含むであろう。
【００３７】
命令実行部３００は、通常、命令をマッピングし且つそれらを様々なモジュールに供給するためにパイプライン動作に復号するマイクロコード状態機械により形成される。あるいは、それに対応するソフトウェアプロセスを利用しても良い。
【００３８】
次に、図４を参照して走査線レンダリング動作中の辺処理モジュール４００の動作を説明する。走査線のレンダリングに要する初期条件は３つの辺レコードのリストを利用できることである。それらのリストのいずれか又は全てが空であっても良い。それらのリストは、辺情報１５から得られ、命令によりセットされる新たな辺を含む新規辺リスと４０２と、先の走査線から送り出された辺レコードを含む主辺リスと４０４と、同様に先の走査線から送り出された辺レコードを含むこぼれ辺リスト４０６である。各辺レコードは次に示すパラメータのうち１つ又は２つ以上を含んでいれば良い。
・ 現在走査線交差座標（ここではＸ座標という）、
・ この辺の現在セグメントが持続しうる走査線の本数（実施形態によってはＹ限界としても表される）を表すカウント（ここではＮＹという）、
・ 走査線を１本すぎるごとにこの辺レコードのＸ座標に加算すべき値（ここではＤＸという）、
・ 走査線を１本すぎるごとにこの辺レコードのＤＸに加算すべき値（ここではＤＤＸという）、
・ １つ又は複数の優先順位番号（Ｐ）,
・ 通常のラスタ（上下）方式で、辺が走査線と左から右へ交差するか又は右から左へ交差するかを指示する方向（ＤＩＲ）フラグ、及び
・ リスト中の次の辺セグメントのアドレス（ＡＤＤ）
３つのリスト４０２、４０４及び４０６の各々のレコードは走査線交差（Ｘ）座標の順に配列されている。これは、通常、分類プロセスにより得られ、当初は、辺情報を含めて命令実行部３００からのメッセージを受信する辺入力モジュール４０８により管理される。辺入力モジュール４０８はメッセージを出力線４９８を介してパイプライン２２を下ってモジュール５００、６００及び７００へ適宜中継する。
【００３９】
辺入力モジュール４０８は３つのリスト４０２、４０４及び４０６の各々への参照を維持すると共に、各リストからの辺データを受信する。その後、辺入力モジュール４０８は、選択されるレコードが３つの参照されたレコードの中の最小Ｘ座標を持つレコードであるように、３つの参照された辺レコードのうち１つからの１つの辺レコードを選択する。その選択された辺は１つのメッセージにフォーマット化され、辺更新モジュール４１０に送られる。また、辺のいくつかのフィールド、特に、現在Ｘ、優先順位番号、方向フラグなどを１つのメッセージにフォーマット化し、そのメッセージは辺処理モジュール４００の出力４９８としてＦＩＦＯ５１８を介して優先順位判定モジュール５００へ送信される。
【００４０】
辺を受信すると、辺更新モジュール４１０はＮＹカウントを減分し、１つ又は２つ以上の関連する辺パラメータを更新する。ＮＹカウントが０に達したならば、次のセグメントアドレスにより指示されるアドレスから新たなセグメントを読み取り、辺の次の走査線についてＸ座標を計算する。辺レコードの修正が終了すると、辺更新モジュール４１０は、辺プール４１２に新たな辺が追加されたことを信号線４１６を介して辺出力モジュール４１４に報知する。そこで、辺レコードが辺レコードストア３２に戻されて、格納される前に、辺レコードは辺出力モジュール４１４により分類される。
【００４１】
ＦＩＦＯ５１８は辺処理モジュール４００と優先順位判定モジュール５００の動作を切り離す。先に述べたテーブル３４の一部を構成する優先順位状態テーブル５０２は、各オブジェクトの優先順位に関する情報を保持するために使用される。ＦＩＦＯ５１８の大きさは、１回のアクションで走査線１本分の辺交差の辺処理モジュール４００からの受信及び優先順位状態テーブル５０２への転送をイネーブルするように定められている。これにより、優先順位判定モジュール５００は同じ画素（Ｘ）位置で複数の辺交差を正確に処理することができる。優先順位状態テーブル５０２及び優先順位データテーブル（例えば、レベルアクティべーションテーブル５３０）は、同じ画素Ｘ位置で交差メッセージを受信するたびに更新される。優先順位状態テーブル５０２の各レコードは次のような塗りつぶしパラメータを記録している。
・ この優先順位が奇数／偶数塗りつぶし規則又は非ゼロワインディング塗りつぶし規則の適用によりその内側対外側状態を判定されるべきであるか否かを指示する塗りつぶし規則フラグ；
・ この優先順位に影響を及ぼす辺との交差が起こるたびに塗りつぶし規則により指示されるように修正される塗りつぶしカウント；
・ この優先順位をクリッピング又は塗りつぶしのために使用すべきか否か及びクリップの種類（クリップイン又はクリップアウト）を指示するクリッパフラグ及びクリップ形フラグ；
・ この優先順位がそれより下のレベルを最初に計算することを要求するか否かを指示する「ニードビロー」フラグと呼ばれるフラグ。
【００４２】
図１１Ａ及び図１１Ｂは、奇数／偶数規則及び非ゼロワインディング規則の適用を示している。非ゼロワインディング規則に関して、図１１Ａは、オブジェクト７０の辺７１及び７２が下向きであるか、又は上向きであるかに従って、それらの辺に概念上の方向がどのように割り当てられるかを示す。閉じた境界を形成するために、辺は境界に沿って数珠つなぎのようにリンクされる。塗りつぶし規則（後述する）の場合に辺に与えられる方向は、セグメントが定義された順序とは無関係である。辺セグメントは、レンダリング方向に対応して、追跡される順に定義される。
【００４３】
図１１Ｂは、２つの下向きの辺７３及び７６と、３つの上向きの辺７４、７５及び７７とを有する１つのオブジェクト（星形）を示す。奇数／偶数規則は、単に、各辺が問題の走査線と交差するたびにブール値（Boolean value）をトグルし、それにより有効にオブジェクトの色をターンオン又はターンオフするだけで動作する。非ゼロワインディング規則は、交差中の辺の方向に応じて塗りつぶしカウント値を増減する。図１１Ｂでは、走査線が初めに出会う２つの辺７３及び７６は下向きの辺であるので、それらの辺と交わることにより、塗りつぶしカウントはそれぞれ＋１と、＋２に増分される。次に走査線が出会う２つの辺７４及び７７は上向きの辺であるので、塗りつぶしカウントはそれぞれ＋１と０に減分される。
【００４４】
実施形態によっては、この情報の一部が表示リスト１３及び先に説明した様々な辺リストの中の辺と関連しており、辺交差メッセージの一部として優先順位判定モジュール５００へ送信される場合がある。特に、塗りつぶし規則フラグ、クリッパフラグ、クリップ形フラグ、ニードビローフラグ及びその他の情報はこのようにして処理されれば良い。
【００４５】
図５を参照すると、優先順位更新モジュール５０６は、処理を完了するまでの走査線交差座標を記録するカウンタ５２４を維持する。これを優先順位更新モジュール５０６の現在Ｘ（current X）という。走査線の始まりにおける初期値は０である。
【００４６】
ＦＩＦＯ５１８のヘッドで受信した辺交差メッセージを検査して、優先順位更新モジュール５０６は辺交差メッセージ中のＸ交差値を現在Ｘと比較する。辺交差メッセージ中のＸ交差値が優先順位更新モジュール５０６の現在Ｘと等しければ、優先順位更新モジュールは辺交差メッセージを処理し、現在Ｘより大きければ、優先順位更新モジュールは辺交差メッセージにおけるＸ交差値と現在Ｘとの差の画素ごとに塗りつぶし指令（commands）を生成する。
【００４７】
ある画素が優先順位に関わる塗りつぶし規則に従って優先順位に適用される境界辺の内側にあり、且つ優先順位のクリップカウントが０である場合、その画素において優先順位はアクティブである。優先順位が最上のアクティブな優先順位である場合、又はその優先順位を越える全てのアクティブな優先順位の対応するニードビローフラグがセットされている場合、優先順位は露出される。このように、画素値は露出された優先順位の塗りつぶしデータのみを使用して生成される。
【００４８】
優先順位のニードビローフラグ（need-below flag）は表示リストの情報で確定され、フラグがセットされない限り、問題の優先順位より下のアクティブな優先順位がいずれもレンダリングすべき画素値に寄与しないことを画素生成システムに報知するために使用される。最終的な画素値に全く関与しないと考えられる余分な合成動作を防止するために、フラグは適宜クリアされる。
【００４９】
辺交差メッセージ中の優先順位ごとに、その優先順位により指示される優先順位状態テーブルレコードのフィールドを参照して、プロセスは、
（ｉ）現在優先順位の現在塗りつぶしカウントを記録する工程と、
（ii）（ａ）現在優先順位の塗りつぶし規則が奇数／偶数である場合、塗りつぶしカウントがその時点で０でなければ塗りつぶしカウントを０に設定し、そうでなければ０でないいずれかの値に設定するか、
（ｂ）現在優先順位の塗りつぶし規則が非ゼロワインディングである場合、塗りつぶしカウントを（辺方向フラグに応じて）増減する工程と、
（iii）新たな塗りつぶしカウントを記録した塗りつぶしカウントと比較し、一方が０であり、他方が０でない場合に、現在優先順位に対して「アクティブフラグ更新」（後述する）動作を実行する工程とを含む。
【００５０】
実施形態によっては、各辺交差メッセージに複数の優先順位を導入するのではなく、優先順位ごとに別個の辺交差メッセージを使用しても良い。
【００５１】
アクティブフラグ更新動作は、まず、現在優先順位について新たなアクティブフラグを確定することを含む。優先順位状態テーブル５０２中の優先順位の塗りつぶしカウントが０ではなく且つ優先順位のクリップカウントが０である場合、アクティブフラグは０ではなく、そうでない場合にはアクティブフラグは０である。アクティブフラグ更新動作の第２のステップでは、判定されたアクティブフラグをアクティブフラグアレイ５０８の、現在優先順位により指示される位置に格納し、更に、現在優先順位に関わる優先順位状態テーブルのニードビローフラグがゼロであれば、アクティブフラグを不透明アクティブフラグアレイ５１０の、現在優先順位により指示される位置に格納する。
【００５２】
辺交差メッセージ中のＸ交差値が優先順位更新モジュール５０６の現在Ｘより大きいとき、優先順位更新モジュール５０６は、辺交差メッセージのＸ交差値と現在Ｘとの差である、生成すべき画素の数を示すカウントを形成する。このカウントは優先順位生成メッセージとしてフォーマット化され、接続線５２０を介して優先順位生成モジュール５１６へ送信される。そこで、優先順位更新モジュール５０６は、所定の数の画素についての処理が完了したことを示す、優先順位生成モジュール５１６からの信号５２２を待つ。信号５２２を受信すると、優先順位更新モジュール５０６はその現在Ｘを辺交差メッセージ中のＸ交差値に設定し、先に説明したように処理を続ける。
【００５３】
優先順位生成モジュール５１６は、同様にテーブル３４内に形成され、各優先順位に関する情報を保持するために使用される優先順位データテーブル５０４を参照して動作する。優先順位データテーブル５０４の各レコードは、
塗りつぶしテーブルアドレス及び型、
合成演算コード及びフラグ、
この優先順位の色が所定のＹに対して一定であるか否かを記録する、「Ｘ独立（x-independent）」フラグと呼ばれるフラグを含む。
【００５４】
優先順位生成メッセージ５２０を受信すると、優先順位生成モジュール５１６は、供給されたカウントにより指示される回数にわたり「画素優先順位生成動作」（後述する）を実行し、その後、その動作を完了したことを信号５２２により優先順位更新モジュール５０６に報知する。
【００５５】
各画素優先順位生成動作は、第一に、不透明アクティブフラグアレイ５１０に対して優先順位符号器５１４（例えば、４０９６では、１２ビット優先順位符号器）を使用して、最高の不透明アクティブフラグの優先順位番号を判定する。この優先順位（もし、存在すれば）は、優先順位データテーブル５０４を索引付けするために使用され、そのようにして参照されたレコードのコンテンツは優先順位生成モジュール５１６からの塗りつぶし優先順位メッセージ出力５９８として作成され、塗りつぶし色判定モジュール６００へ送信される。更に、先のステップにより優先順位が判定されていた（すなわち、少なくとも１つの不透明アクティブフラグがセットされていた）場合、判定された優先順位を保持するが、これを「現在優先順位」という。優先順位が判定されていなかったならば、現在優先順位は０に設定される。そこで、優先順位生成モジュール５１６はアクティブフラグアレイ５０８に対して修正優先順位符号器５１２を繰り返し使用して、現在優先順位より大きい最低のアクティブフラグを判定する。そのようにして判定された優先順位（もし、存在すれば）は、優先順位データテーブル５０４を索引付けするために使用され、そのようにして参照されたレコードのコンテンツは塗りつぶし優先順位メッセージとして作成され、塗りつぶし色判定モジュール５００へ送信され（５９８）、その後、判定された優先順位は現在優先順位を更新するために使用される。判定される優先順位がなくなるまで（すなわち、アクティブフラグの中でフラグ付けされた、現在優先順位より大きい優先順位が存在しなくなるまで）、このステップは繰り返し使用される。
【００５６】
以上説明した基本動作の好ましい特徴として、優先順位生成モジュール５１６は、シーケンスの第１の画素を処理している間に塗りつぶし色判定モジュール６００へ送り出す各メッセージのＸ独立フラグの値を記録する。送り出される全てのメッセージのＸ独立フラグが指定されたものであれば、隣接する辺交差の間の画素のスパンにある全ての後続メッセージをカウント−１の単一の反復仕様と置き換えることができる。これは、反復メッセージを生成し、それをこのシーケンスにおける他の全ての処理に代えて塗りつぶし色判定モジュール６００へ送信することにより実行される。
【００５７】
上述の基本動作の別の好ましい特徴として、優先順位生成モジュール５１６は、各レベル生成メッセージの後に、最高の不透明優先順位を接続線５２２を介して優先順位更新モジュール５０６へ送信する。優先順位更新モジュール５０６はこれをストア５２６に保持する。そこで、優先順位判定モジュール５０６は、画素優先順位生成メッセージを生成する前に、メッセージ中のＸ交差点が現在Ｘより大きいこと及びメッセージ中のレベルの少なくとも１つが最高の不透明優先順位以上であることの試験を実行する。これを実行することによって、より少ない回数の画素優先順位判定動作を実行するだけで済み、より長い反復シーケンスを生成できる。
【００５８】
図１２Ａから図１２Ｅは、好適な実施形態における、アレイ５０８、５１０及び符号器５１２、５１４と共にレベルアクティべーションテーブル５３０と呼ばれる１つのテーブルに併合されている優先順位テーブル５０２及び５０４の動作を示している。図１２Ａに示すように、辺交差メッセージは辺処理モジュール４００から１本の走査線について順次受信され、優先順位の順に配列されるテーブル５３０にロードされる。この例では、辺交差メッセージは辺横断の非ゼロワインディング規則に従って増分方向を含む。優先順位テーブル５３０のエントリをいずれもセットしないことは可能である。
【００５９】
５３０で示すようなレベルアクティべーションテーブルは塗りつぶしカウントに対応する列エントリを含む。これらは非ゼロワインディング規則又は（適切であれば）奇数／偶数規則に従って辺から判定される。ニードビローフラグは優先順位の特性であり、レンダリング動作に先立って部分レベル特性としてセットされる。ニードビローフラグは、テーブル５３０がロードされるときに全ての優先順位レベルに対してセットされる。「クリップカウント」及び「塗りつぶし索引テーブル」などの他の列を使用しても良いが、この例においては、説明を簡単にするため、それらの列は省略されている。レベルがいずれもアクティブではない場合、対応するエントリは０に設定される。更に、アレイ５１０及び５０８の値は後続する辺交差を受信した後にテーブル５３０から更新される。
【００６０】
図１２Ａから明らかであるように、ここでは、明瞭を期するためにいくつかのレコードを便宜上省略してある。通常、レベルアクティべーションテーブル５３０は、優先順位の順に配列された次のレコードを含むであろう。
【００６１】
塗りつぶしカウント
クリップカウント
塗りつぶし型
アクティベーション条件及びフラグ（次のものを含む）
ニードビローフラグ
クリップ型
クリッパフラグ
図形合成動作及びフラグ（次のものを含む）
ラスタ演算コード
アルファチャネル演算コード
「発信元ポップ」フラグ
「宛先ポップ」フラグ
Ｘ独立フラグ
塗りつぶし規則
属性、及び
塗りつぶしテーブル索引
テーブル５３０のコンテンツは、優先順位判定モジュール５００で使用されない場合、画素生成のためにメッセージとして塗りつぶし色判定モジュール６００へ送信されると共に、合成動作のために画素合成モジュール７００へ送信される。テーブル５３０のコンテンツは辺交差メッセージから得られるのが好ましい。あるいは、レベルアクティべーションテーブル５３０の静的コンテンツを辺交差メッセージの受信前に事前にロードしておいても良い。
【００６２】
図１２Ａには、走査線３５（図９）の第１の辺交差が示されている。この場合、Ｐ＝１（優先順位レベル１）のとき、塗りつぶしカウントは非ゼロワインディング規則に従って辺の値に更新される。その下にオブジェクトは存在しないので、「ニードビロー」は０のレベルに設定される。
【００６３】
テーブル５３０の先行状態は設定されていなかったため、アレイ５１０及び５０８はセットされないままであり、優先順位符号器５１４は優先順位を出力できない。このことは優先順位生成モジュール５１６により解釈され、優先順位生成モジュール５１６は、走査線３５の初めのブランクの部分である「オブジェクトなし」優先順位（例えば、Ｐ＝０）に対してカウントｎ＝４０（画素）を出力する。
【００６４】
図１２Ｂは、走査線（図９）の第２の辺交差が受信されるときの配列を示す。塗りつぶしカウントが更新される。そこで、アレイ５１０及び５０８はテーブル５３０からの先行最高レベルによって設定される。この時点で、モジュール５１６はカウントｎ＝４５を出力し、Ｐ＝１は半透明の三角形８０との交差前の不透明の赤色オブジェクト９０の辺９６を表現している。
【００６５】
図１２Ｃは、図９の走査線３５の第３の辺交差が受信されるときの配列を示す。尚、非ゼロワインディング規則であるために塗りつぶしカウントは下方へ調整されている。現在辺交差を受信する前に有効であったオブジェクトは不透明ではないので、修正優先順位符号器５１２を使用して、最高アクティブレベルとして優先順位Ｐ＝２を選択し、これは現在値としてｎ＝（１１５−８５）＝３０について出力される。
【００６６】
図１２Ｄは、図９の走査線３５の最終辺交差が受信されるときの配列を示す。尚、先に変更されたＰ＝２の「ニードビロー」はアクティブアレイ５０８へ既に転送されているため、優先順位符号器はｎ＝（１６０−１１５）＝４５画素について現在の値Ｐ＝１を出力できる。
【００６７】
図１２Ｅは、辺交差をそれ以上利用できないときの結果を示し、ｎ＝（１８０−１６０）＝２０画素についてＰ＝０の出力を提供している。
【００６８】
このように、優先順位モジュール５００は１本の走査線の全ての画素について画素のカウントと、対応する優先順位表示値とを出力する。
【００６９】
次に、図６を参照して塗りつぶし色判定モジュール６００の動作を説明する。優先順位判定モジュール５００から入力される、塗りつぶしデータセットメッセージ、反復メッセージ、塗りつぶし優先順位メッセージ、画素終わりメッセージ及び走査線終わりメッセージを含むメッセージ５９８は、まず、塗りつぶしルックアップ制御モジュール６０４へ送信される。塗りつぶしルックアップ制御モジュール６０４は、塗りつぶし色判定モジュール６００の様々な構成要素により使用されるべき現在Ｘ位置カウンタ６１４及び現在Ｙ位置カウンタ６１６を維持している。
【００７０】
走査線終わりメッセージを受信すると、塗りつぶしルックアップ制御モジュール６０４は現在Ｘカウンタ６１４を０にリセットし、現在Ｙカウンタ６１６を増分する。その後、走査線終わりメッセージは画素合成モジュール７００へ送信される。
【００７１】
塗りつぶしデータセットメッセージを受信すると、塗りつぶしルックアップ制御モジュール６０４はそのデータを塗りつぶしデータテーブル３６の指定場所６０２に格納する。
【００７２】
反復メッセージを受信すると、塗りつぶしルックアップ制御モジュール６０４は現在Ｘカウンタ６１４を反復メッセージからのカウントの分だけ増分する。その後、反復メッセージは画素合成モジュール７００へ送信される。
【００７３】
画素終わりメッセージを受信すると、塗りつぶしルックアップ制御モジュール６０４は同様に現在Ｘカウンタ６１４を増分し、その後、画素終わりメッセージは画素合成モジュール７００へ送信される。
【００７４】
塗りつぶし優先順位メッセージを受信すると、塗りつぶしルックアップ制御モジュール６０４は、
− 塗りつぶし優先順位メッセージからの塗りつぶし型を使用して、塗りつぶし優先順位メッセージからのテーブルアドレスにおいてレコードサイズを選択すること（レコードサイズは３６で判定される通り）；
− 前記の塗りつぶしテーブルを使用して、塗りつぶしデータテーブル３６から１つのレコードを選択すること；
− 塗りつぶし優先順位メッセージからの塗りつぶし型を使用して、塗りつぶし色の生成を実行するためのサブモジュールを判定し、選択すること（サブモジュールは図形を処理するためのラスタ画像モジュール６０６、フラットカラーモジュール６０８、直線ランプカラーモジュール６１０及び不透明度タイルモジュール６１２を含むであろう）；
− 判定されたレコードを選択されたサブモジュール６０６~６１２に供給すること；
− 選択されたサブモジュール６０６~６１２が供給されたデータを使用して、色及び不透明度値を判定すること；
− 判定された色及び不透明度を塗りつぶし色メッセージからのその他の情報、すなわち、ラスタ演算コード、アルファチャネル演算コード、発信元ポップフラグ及び宛先ポップフラグと組み合わせて、接続線６９８を介して画素合成モジュール７００へ送信される色合成メッセージを形成すること
を含む動作を実行する。
【００７５】
画素色成分は、通常は画素ごとに３２ビットを提供する８ビット精度を有する赤色、緑色、青色及び不透明度の４つの成分である。しかし、その代わりに、不透明度の示唆を伴うシアン、マゼンタ、黄色及び黒色の４つの成分、あるいはその他の数多くの周知の色表現のいずれか１つを使用しても良い。
【００７６】
次に、画素合成モジュール７００の動作を説明する。塗りつぶし色判定モジュール６００から入力される、反復メッセージ、色合成メッセージ、画素終わりメッセージ及び走査線終わりメッセージを含むメッセージは順次処理される。
【００７７】
反復メッセージ又は走査線終わりメッセージを受信すると、画素合成モジュール７００はそのメッセージをそれ以上の処理を加えずに出力ＦＩＦＯ７０２へ送信する。
【００７８】
色合成メッセージを受信すると、画素合成モジュール７００は、通常、色合成メッセージからのラスタ演算及びアルファチャネル演算に従って、色合成メッセージからの色及び不透明度を画素合成スタック３８からポップされた色及び不透明度と組み合わせる。次に、その結果を画素合成スタック３８に押し戻す。色合成メッセージの受信時に実行される処理については後に説明する。
【００７９】
画素終わりメッセージを受信すると、画素合成モジュール７００は画素合成スタック３８から色及び不透明度をポップするが、例外として、スタック３８が空である場合には、不透明白色値を使用する。その結果得られた色及び不透明度は画素出力メッセージとして形成され、このメッセージは画素出力モジュール８００へ送信される。
【００８０】
次に、画素出力モジュール８００の動作を説明する。画素出力ＦＩＦＯから入力される、画素出力メッセージ、反復メッセージ及び走査線終わりメッセージが読み取られ、順次処理される。
【００８１】
画素出力メッセージを受信すると、画素出力モジュール８００はその画素を格納すると共に、画素を出力部へ送信する。反復メッセージを受信すると、最前に格納されていた画素が反復メッセージからのカウントにより指定される回数だけ出力部８９８へ送信される。走査線終わりメッセージを受信すると、画素出力モジュール８００はそのメッセージを出力部へ送り出す。
【００８２】
出力部８９８は、画素画像データを利用する何らかの装置に必要に応じて接続可能である。そのような装置としては、ビデオ表示装置又はプリンタなどの出力装置、あるいはハードディスクやラインストア、バンドストア又はフレームストアを含む半導体ＲＡＭ等のメモリ格納装置、又はコンピュータネットワークなどがある。しかし、以上の説明から明らかであるように、レンダリングプロセス中に画素画像データの中間格納を必要とせずに精巧な図形記述言語により要求される機能性を余す所なく発揮して図形オブジェクトをレンダリングすることができる方法及び装置が説明されている。
【００８３】
次に図１３Ａ及び図１３Ｂを参照すると、カラー動作モード１３００及びグレイスケール動作モード１３０２でそれぞれ動作するときの画素逐次レンダリング装置２０のデータ流れが示されている。命令実行部３００はホストプロセッサ２からの命令に応答して、塗りつぶし順位判定モジュール５００、塗りつぶし色判定モジュール６００、画素合成モジュール７００及び画素出力モジュール８００に、カラー動作モード又はグレイスケール動作モードのいずれかで動作するように命令する。
【００８４】
カラー動作モード中、塗りつぶし色判定モジュール６００、画素合成モジュール７００及び画素出力モジュール８００は、４つの画素成分を有するカラー画素データを４つの出力チャネル１３０４からそれぞれ出力する。出力チャネル１３０４はバス（２４ビット又は３２ビット幅）を構成しているのが好ましい。カラー画素データは、例えば、不透明度成分を伴う又は伴わないその色成分、例えば、赤色成分、緑色成分、青色成分に分解されるか、又はシアン、マゼンタ、黄色及び黒色の各成分に分解される。それらの色成分はそれぞれ８ビットから構成されているのが好ましく、それぞれ対応する４つの出力チャネル１３０４を介して出力される。カラー動作モード中、塗りつぶし色判定モジュール６００、画素合成モジュール及び画素出力モジュール８００は４つの出力チャネル１３０４を介して、クロックサイクルごとに１画素ずつ同期して出力する。
【００８５】
グレイスケールレンダリングモード中、塗りつぶし色判定モジュール６００、画素合成モジュール７００及び画素出力モジュール８００は、８ビットのグレイスケール画素成分のみを有する画素データを４つの出力チャネル１３０４から出力する。このモード中、塗りつぶし色判定モジュール６００、画素合成モジュール７００及び画素出力モジュール８００はクロックサイクルごとに４つの連続する画素をラスタ順に同期してそれぞれ対応する４つの出力チャネル１３０４を介して出力する。
【００８６】
カラー画素逐次レンダリング装置２０はグレイスケールレンダリングを２つの異なる方法で加速する。優先順位判定モジュール５００はカラー動作モードの場合は反復指令と塗りつぶし指令を生成するが、加速グレイスケール動作モードの場合には、それらの指令の動作はグレイスケールレンダリングを加速するように修正される。
【００８７】
これら２つの指令、すなわち、塗りつぶし指令及び反復指令の詳細と動作については、以下にカラー動作モードに関して説明する。
【００８８】
反復指令は優先順位判定モジュール５００により１つのパラメータを伴って生成される。このパラメータは、同一の画素データを有する画素の数を指定し、この指令は画素出力モジュール８００に至る経路にある下流側の全てのモジュールへ送信される。指定の画素位置についてこの指令が下流側のモジュールにより処理され終わったならば、それらの下流側モジュールは次の画素位置へ進む。
【００８９】
カラー動作モード中、塗りつぶし指令は、オブジェクト識別子、塗りつぶし型、塗りつぶしアドレス、合成動作、画素属性、及びオブジェクトがこの画素に関する最終オブジェクトであるか、すなわち、この画素に関してアクティブである全てのオブジェクトのうち最上のオブジェクトであるか否かを指示するためのフラグ（last_object）などのいくつかのパラメータを有する。処理すべき現在画素位置に寄与する各オブジェクトの色を得るために、この指令は塗りつぶし色判定モジュール６００により翻訳されなければならない。塗りつぶし指令についてlast_objectフラグがＴＲＵＥにセットされており且つその塗りつぶし指令が現在画素位置について塗りつぶし色判定モジュール６００により処理され終わっている場合、塗りつぶし色判定モジュール６００は次の画素位置へ処理を進める。しかし、last_objectフラグがＦＡＬＳＥにセットされていた場合には、塗りつぶし色判定モジュール６００は現在画素位置を処理し続ける。
【００９０】
反復指令は、現在画素に続く１つ又は複数の後続画素がＸ座標独立オブジェクト、例えば、フラットカラー又はｙ方向の直線ランプカラーの色塗りつぶしを伴うオブジェクトを有する場合に作成される。そのような状況の下では、塗りつぶし色判定モジュール６００は先頭の画素について塗りつぶし指令を処理し、その後、下流側の全てのモジュールに反復指令を送信するだけで良い。反復すべき画素の数は、優先順位判定モジュール５００が次に受信する辺交差Ｘ"座標と、現在辺交差のＸ座標とによって決まる。すなわち、反復指令のパラメータは（Ｘ"−（Ｘ＋１））に等しい。
【００９１】
１つ又は複数のオブジェクトがビットマップ、もしくは画素ごとに異なる潜在色データを有する他の何らかの色塗りつぶし動作を有する場合、優先順位判定モジュール５００は塗りつぶし指令をオブジェクトがアクティブである画素ごとに送る以外の選択肢を持たない。その代わりに、塗りつぶし色判定モジュール６００は画素ごとの最終画素色を処理する。
【００９２】
次に図１４を参照すると、複数のオブジェクトから構成される画像の一例の表現が示されている。オブジェクトＡの左の辺は画素位置６、７、８及び９で走査線５４、５５、５６及び５７とそれぞれ交差している。また、オブジェクトＡの右の辺は画素位置１３、１６、１８及び２１で走査線５４、５５、５６及び５７とそれぞれ交差している。オブジェクトＢの左の辺は画素位置１０、９、９及び７で走査線５４、５５、５６及び５７とそれぞれ交差している。また、オブジェクトＢの右の辺は画素位置１８、１８、１９及び１９で走査線５４、５５、５６及び５７とそれぞれ交差している。オブジェクトＡは、Ｘ方向の画素位置とは無関係である、すなわち、Ｘから独立したフラットカラーを有する。これに対し、オブジェクトＢは、画素がＸに依存するようなビットマップである。オブジェクトＡ及びオブジェクトＢは、画素１０から１３を含む走査線５４、画素９から１６を含む走査線５５、画素９から１８を含む走査線５６及び画素９から１９を含む走査線５７の画素について共通してアクティブである。オブジェクトＢの優先順位はオブジェクトＡより低いので、オブジェクトＡはこの画素についてアクティブである全てのオブジェクトのうち最上位置のオブジェクトである。
【００９３】
カラー動作モードにおいて、図１４に示す例の第１の走査線及び最終走査線（５４及び５７）に対する優先順位判定モジュール５００の入力部４９８及び出力部５９８における指令は次の通りである。
・ 走査線５４（入力指令）：
1. edge_crossing:x=6;object=A;edge=UP;priority=11;
2. edge crossing:x=10;object=B;edge=UP;priority=15;
3. edge crossing:x=13;object=A;edge=DOWN;priority=11
4. edge crossing:x=18;object=B;edge=DOWN;priority=15
・ 走査線５４（出力指令）：
1. repeat 4
2. fill:object=A;type=flat;fill_address=20;last_object=true;
3. repeat 3
4. fill:object=B;type=bitmap;fill_address=32;last_object=false;
5. fill:object=A;type=flat;fill_address=20;last_object=true;
6. fill:object=B;type=bitmap;fill_address=32;last_object=false;
7. fill:object=A;type=flat;fill_address=32;last_object=true;
8. fill:object=B;type=bitmap;fill_address=32;last_object=false;
9. fill:object=A;type=flat;fill_address=20;last_object=true;
10. fill:object=B;type=bitmap;fill_address=32;last_object=false;
11. fill:object=A;type=flat;fill_address=20;last_object=true
12. fill:object=B;type=bitmap;fill_address=32;last_object=true
13. fill:object=B;type=bitmap;fill_address=32;last_object=true;
14. fill:object=B;type=bitmap;fill_address=32;last_object=true;
15. fill:object=B;type=bitmap;fill_address=32;last_object=true;
16. fill:object=B;type=bitmap;fill_address=32;last_object=true;
・ 走査線５７（入力指令）：
1. edge_crossing:x=7;object=B;edge=UP;priority=15;
2. edge crossing:x=9;object=A;edge=UP;priority=11;
3. edge crossing:x=19;object=B;edge=DOWN;priority=15
4. edge crossing:x=21;object=A;edge=DOWN;priority=11
・ 走査線５7（出力指令）：
1. repeat 5
2. fill:object=B;type=bitmap;fill_address=32;last_object=true;
3. fill:object=B;type=bitmap;fill_address=32;last_object=true
4. fill:object=B;type=bitmap;fill_address=32;last_object=false;
5. fill:object=A;type=flat;fill_address=20;last_object=true;
6. fill:object=B;type=bitmap;fill_address=32;last_object=false;
7. fill:object=A;type=flat;fill_address=20;last_object=true;
8. fill:object=B;type=bitmap;fill_address=32;last_object=false;
9. fill:object=A;type=flat;fill_address=20;last_object=true;
10. fill:object=B;type=bitmap;fill_address=32;last_object=false;
11. fill:object=A;type=flat;fill_address=20;last_object=true
12. fill:object=B;type=bitmap;fill_address=32;last_object=false
13. fill:object=A;type=flat;fill_address=20;last_object=true;
14. fill:object=B;type=bitmap;fill_address=32;last_object=false;
15. fill:object=A;type=flat;fill_address=20;last_object=true;
16. fill:object=B;type=bitmap;fill_address=32;last_object=false;
17. fill:object=A;type=flat;fill_address=20;last_object=true;
18. fill:object=B;type=bitmap;fill_address=32;last_object=false;
19. fill:object=A;type=flat;fill_address=20;last_object=true;
20. fill:object=B;type=bitmap;fill_address=32;last_object=false;
21. fill:object=A;type=flat;fill_address=20;last_object=true;
22. fill:object=B;type=bitmap;fill_address=32;last_object=false;
23. fill:object=A;type=flat;fill_address=20;last_object=true;
24. fill:object=B;type=bitmap;fill_address=32;last_object=falst;
25. fill:object=A;type=flat;fill_address=20;last_object=true;
26. fill:object=A;type=flat;fill_address=20;last_object=true;
27. repeat 1
先に述べた通り、辺交差メッセージ（入力指令）はその他にもパラメータを含んでいて良い。例えば、図１２Ａに関連する説明を参照。簡単にするため、図１４に関連してそれらのパラメータのうちいくつかを示してあるにすぎない。
【００９４】
fill_addressパラメータは、塗りつぶし色判定モジュールにより、この特定のオブジェクトと関連する色値を処理するために使用される。塗りつぶし色判定モジュール６００へ送信される塗りつぶし指令ごとに、対応するカラーデータはＲＧＢＯ又はＣＭＹＫいずれかのフォーマットで生成される。
【００９５】
グレイスケール動作モード中、優先順位判定モジュールと塗りつぶし色判定モジュールの双方は塗りつぶし指令ごとに４画素までの分解能で動作するので、４つの出力チャネルを効率良く利用できる。これにより、グレイスケールレンダリング時に１つの出力チャネルしか使用しない場合と比較して、グレイスケールレンダリング速度は４倍まで改善される。
【００９６】
優先順位判定モジュール５００はグレイスケールレンダリングモード中も、カラー動作モード中も、Ｘ独立領域が現れたときに、依然として塗りつぶし指令に続いて繰り返しが起こるという点で同様に動作する。この場合、塗りつぶし色判定モジュール６００と画素合成モジュール７００は１つの出力チャネル１３０４から１つの画素を出力するだけで良く、その後に反復指令が続く。しかし、画素出力モジュール８００は反復指令を使用するのではなく、後に画素出力装置１０が使用することを考慮して、全ての画素データを出力することが望ましい。加えて、グレイスケール動作モード中、画素出力モジュール８００は４つの出力チャネルを介して４つまでの画素をそれぞれ同時に供給するのが好ましい。グレイスケール動作モード中、画素出力モジュール８００は１つの画素を受信し、次に反復指令を受信すると、各出力チャネル１３０４のうち４つまでのチャネルを介して適切な数の画素を同時に送り出す。５つ以上の画素がある場合には、反復指令は４つ１組の画素のグループを順次出力させる。反復指令は画素を所定の順序でチャネルから出力させる。例えば、画素は最も低いチャネル、次に低いチャネルと続き、最後にもっとも上のチャネルに至るという順序で出力される。すなわち、反復指令が２つの画素を送り出す場合、それらの画素は最も低いチャネルと次に低いチャネルから同時に出力される。反復すべき画素の量は常に４の倍数であるとは限らないので、画素出力モジュール８００は画素出力モジュール８００の送り出しサイクル中の有効チャネルの数を指示するための出力信号も供給する。後者の例では、それらの信号は下２つのチャネルが有効であり、上２つのチャネルは無効であることを指示することになるであろう。
【００９７】
通常はビットマップデータが存在することにより発生するＸ従属領域の場合、優先順位判定モジュールは、グレイスケールレンダリング中に４つまでの画素について１つの塗りつぶし指令を送信する。これは、塗りつぶし指令が適用されるラスタ順の連続する画素の数を識別する「no_pixel」と呼ばれる塗りつぶし指令の別のパラメータにより実現される。１つの塗りつぶし指令中に表現できる画素の数は、次の辺交差の前に残留している画素の数によって決まる。次の辺交差がレンダリング中である現在ｘ位置から５画素以上離れて起こる場合には、発行される塗りつぶし指令は４画素について有効である。残る画素については別の塗りつぶし指令を発行しなければならない。そうでない場合には、塗りつぶし指令中の有効画素の数は単に辺交差前の残留画素の数である。更に、塗りつぶし指令は、その塗りつぶし指令が適用される画素を所定の順序で出力チャネル１３０４から出力させる。例えば、画素は最も低いチャネル、次に低いチャネルと続き、最後に最も上のチャネルに至るような順序で出力される。従って、塗りつぶし指令パラメータ「no_pixel」＝２である場合、対応する２つの画素は最も低いチャネルと次に低いチャネルから同時に出力されることになる。
【００９８】
そこで、塗りつぶし色判定モジュール６００は所定の塗りつぶし指令の有効画素ごとに同時に結果として得られた色を処理する。これは、隣接する画素のビットマップデータが通常はローカルメモリの隣接するアドレススペースに格納されているために可能である。更に、塗りつぶし色判定モジュール６００は、通常、性能を改善するために、ローカルメモリから１画素分を超える量のデータを取り出す。
【００９９】
また、塗りつぶし色判定モジュール６００は、複数の画素を伴う１つの塗りつぶし指令の結果として、複数の「色合成メッセージ」を生成することができる。これは、キャッシュが複数画素のビットマップデータの一部しか含んでおらず、その結果、通常は極めてゆっくりとした速度で、まず、ローカルメモリから取り出されなければならないために有用である。この状況においては、モジュールは第１の色合成メッセージを修正画素有効性値と共に下流側のモジュールへ送信する。後続する画素データを利用できる場合、同じ塗りつぶし指令から残る画素位置について第２のメッセージが生成される。
【０１００】
更に下流側へ下って、画素合成モジュール７００の動作は変化がなく、チャネルが有効画素を含むか又はグレイスケールレンダリングの場合にないかに関わらず、利用できる全てのチャネルに対して合成動作を単純に実行できる。しかし、画素データバッファリングの動作を簡単にするために画素出力モジュール８００は、有効画素が常に最下位チャネルから始まるように保証するという意味で一種のハウスキーピングを実行することを望む場合もある。
【０１０１】
再び図１４に戻って説明を続けると、加速グレイスケールレンダリングの場合の第１の走査線及び最終走査線（５４及び５７）についての優先順位判定モジュール５００の入力部及び出力部における指令（command）は、グレイスケール動作モードの場合と比較して次のようになる。
・ 走査線５４（入力指令）：
1. edge_crossing:x=6;object=A;edge=UP;priority=11;
2. edge crossing:x=10;object=B;edge=UP;priority=15;
3. edge crossing:x=13;object=A;edge=DOWN;priority=11;
4. edge crossing;x=18;object=B;edge=DOWN;priority=15;
・ 走査線５４（出力指令）：
1. repeat 4
2. fill:object=A;type=flat;fill_address=20;last_object=true;no_pixel=1;
3. repeat 3
4. fill:object=B;type=bitmap;fill_address=32;last_object=false;no_pixel=4;
5. fill:object=A;type=flat;fill_address=20;last_object=true;no_pixel=4;
6. fill:object=B;type=bitmap;fill_address=32;last_object=true;no_pixel=4;
7. fill:object=B;type=bitmap;fill_address=32;last_object=true;no_pixel=1;
8． 走査線５７（入力指令）：
1. edge_crossing:x=7;object=B;edge=UP;priority=15;
2. edge crossing:x=9;object=A;edge=UP;priority=11;
3. edge crossing:x=19;object=B;edge=DOWN;priority=15;
4. edge crossing;x=21;object=A;edge=DOWN;priority=11;
・ 走査線５７（出力指令）：
1. repeat 5
2. fill:object=B;type=bitmap;fill_address=32;last_object=true;no_pixel=2;
3. fill:object=B;type=bitmap;fill_address=32;last_object=false;no_pixel=4
4. fill:object=A;type=flat;fill_address=20;last_object=true;no_pixel=4;
5. fill:object=B;type=bitmap;fill_address=32;last_object=false;no_pixel=4;
6. fill:object=A;type=flat;fill_address=20;last_object=true;no_pixel=4;
7. fill:object=B;type=bitmap;fill_address=32;
last_object=false;no_pixel=3;
8. fill:object=A;type=flat;fill_address=20;last_object=true;no_pixel=3
9. fill:object=A;type=flat;fill_address=20;last_object=true;no_pixel=1
10. repeat 1
所定の２本の走査線に関する例から性能の向上がはっきりと見て取れる。２本の走査線（５４及び５７）において、塗りつぶし指令の数は、それぞれ、１４から５へ、２５から８へと減っており、非常に大きな改善であることがわかる。
【０１０２】
以下の表は、先に挙げた例の走査線５４における初めの３つの指令に関してカラーレンダリングとグレースケールレンダリングの場合の画素出力モジュールの動作を示す。尚、カラーレンダリングの場合、チャネル３,２,１及び０はそれぞれ不透明度、青色、緑色及び赤色のチャネルとして機能することに注意する。
【０１０３】
【表１】
【表２】
次に、図１５及び図１６に示すフローチャートを参照して画素逐次レンダリング装置２０を動作させる方法を説明する。この方法は、塗りつぶし色判定モジュール６００、画素合成モジュール７００及び画素出力モジュール８００をカラー動作モード又は加速グレイスケール動作モードで動作するように構成することができる。方法は、ホストプロセッサから命令実行部３００を介して受信される命令に応答してこれらのモードの一方を動作させるように構成される。これら２つのモードにおいて、方法は塗りつぶし色判定モジュール６００、画素合成モジュール７００及び画素出力モジュール８００の各々に対して指令を発生する。それらの指令はほぼ類似しているが、モードによって異なる。カラー動作モードで動作しているとき、方法はカラー動作モード指令に応答して、１つの画素の４つの画素成分を塗りつぶし色判定モジュール６００、画素合成モジュール７００及び画素出力モジュール８００の４つの出力チャネル１３０４をそれぞれ介して出力する。加速グレイスケール動作モードで動作しているとき、方法はグレイスケール動作モード指令に応答して、４つのまでの連続する画素をラスタ順に塗りつぶし色判定モジュール６００、画素合成モジュール７００及び画素出力モジュール８００のそれぞれ対応する４つの出力チャネル１３０４を介してクロックサイクルごとに同期させて出力する。
【０１０６】
そこで図１５を参照すると、カラー動作モードで動作しているときに指令を生成する方法のフローチャートが示されている。指令を生成する方法１５００はレンダリングすべき画像の走査線ごとに実行される。説明を容易にするため、ここでは現在走査中の走査線と呼ばれる１本の走査線に関してのみ指令を発生する場合に関連して方法を説明する。
【０１０７】
方法１５００は、現在走査中の走査線において、変数current_xを１に設定することにより開始される（１５０２）。この変数は、考慮すべき現在画素の位置を指示するカウンタとして機能する。先に述べた通り、辺交差メッセージ（入力指令）は走査線交差（Ｘ）座標の順にＦＩＦＯ５１８を介して優先順位判定モジュール５００へ送信される。方法１５００は、それらの辺交差メッセージをその走査線交差（Ｘ）座標の順に処理する。それらの辺交差メッセージは図１４を参照して説明した、例えば、edge_crossing:x＝６;object＝A;edge＝UP;priority＝１１及びその他のフィールドのようなフォーマットをとっていても良い。
【０１０８】
方法１５００は、ステップ１５０４で辺交差メッセージを検索し、ループの各々のパス中に走査線交差（Ｘ）座標の順にそれらのメッセージを処理するループ（１５０４−１５１２−１５０４、１５０４−１５２４−１５０４）の形態をとっている。同じ走査線交差座標（Ｘ）を有する複数の辺交差メッセージが存在する場合、方法は、ループの１回のパス中に処理するためにそれら複数の辺交差メッセージの全てを検索する（１５０４）。言い換えれば、ループの現在パス中に、方法１５００は、走査線の順で、ループの最前のパス中に検索された辺交差メッセージの（Ｘ）座標の次に来る同じ（Ｘ）座標を有する１つ又は複数の辺交差メッセージを獲得する（１５０４）。
【０１０９】
開始ステップ１５０２の後、方法１５００は、走査線の順で初めて現れた走査線交差座標（Ｘ）を有する辺交差メッセージを獲得する（１５０４）。全てが走査線の順で初めて現れる同じ交差（Ｘ）座標を有する複数の辺交差メッセージが存在する場合、方法はそれら初めて現れた全ての辺交差メッセージを獲得する（１５０４）。また、方法１５００は、先に説明したように、現在Ｘ座標についてその時点で検索された辺交差メッセージを使用してレベルアクティべーションテーブル５３０を更新する。最初の辺交差メッセージの（Ｘ）座標が２より大きい場合、方法１５００は更に指令「repeat X−2」を塗りつぶし色判定モジュール６００、画素合成モジュール７００及び画素出力モジュール８００へ送信する。この反復指令のフラグは、画素X＝１からX−１にわたるオブジェクトが存在せず且つそれらの画素位置において背景をペイントしても良いことを指示するようにＯＮにセットされているのが好ましい。
【０１１０】
ステップ１５０４の後、方法１５００は、その時点で検索されていた辺交差メッセージを利用して、フラグテーブル５０８及び５１０に格納されている「アクティブフラグ」及び「不透明アクティブフラグ」を更新する（１５０６）。「アクティブフラグ」及び「不透明アクティブフラグ」がどのようにして更新されるかについては、先に詳細に説明してある。
【０１１１】
次に、方法１５００は、current_xの現在値に位置する画素について「アクティブフラグ」がＯＮにセットされている優先順位オブジェクトが存在するか否かを判定する（１５０８）。それら１つ又は複数のオブジェクトの全ての関連する「アクティブフラグ」がＯＦＦにセットされているならば、それらのオブジェクトは現在画素に全く寄与しないので、決定ブロック１５０８はＦＡＬＳＥ（ノー）を戻し、方法１５００はステップ１５１６へ進む。
【０１１２】
そこで、走査線の順で次の辺交差メッセージのＸ座標の値をnew_Xとし、変数current_xの現在値をcurrent_xとするとき、（new_X−current_x）＞０であるならば、方法１５００は指令「repeat（new_X−current_x）」を送信する（１５１６）。この場合、反復指令の前記フラグは、current_xからnew_Xに位置する画素にわたるオブジェクトは存在せず且つそれらの画素位置で背景をペイントしても良いことを指示するようにＯＮにセットされている。次に、方法はステップ１５１８へ進む。
【０１１３】
ステップ１５１８中、方法１５００は変数current_xを走査線の順で次の辺交差メッセージのＸ座標に等しいnew_Xに設定する。次に、方法はステップ１５０４に戻り、ループの次のパス中に処理するためにnew_Xで辺交差を有する次の辺交差メッセージを獲得する（１５０４）。
【０１１４】
これに対し、current_xの現在値に位置する画素についてオブジェクトの「アクティブフラグ」のいずれか１つがＯＮになっている場合には、決定ブロック１５０８はＴＲＵＥ（イエス）を戻し、方法１５００はステップ１５１０へ進む。
【０１１５】
ステップ１５１０中、方法１５００はcurrent_xの現在値に位置する画素について塗りつぶし指令を生成し始める。このステップ１５１０中、方法１５００は、「アクティブフラグ」がＯＮにセットされ且つ最高「不透明アクティブフラグ」がＯＮにセットされているオブジェクト以下の優先順位を有する、「アクティブフラグ」がＯＮにセットされているオブジェクトを優先順位の順に判定する。それらの塗りつぶし指令のパラメータのデータは、それまでに検索されていた辺交差メッセージに含まれる情報から間接的に得られる。特に、塗りつぶし指令のパラメータはcurrent_xの現在値に関する更新後のレベルアクティべーションテーブル５３０から獲得される。この生成ステップ１５１０中、方法１５００は、current_xの現在値に位置する画素について２つ以上の塗りつぶし指令が存在する場合、更にそれらの塗りつぶし指令の優先順位を判定する。すなわち、current_xの現在値に位置する画素の塗りつぶし指令はそのオブジェクト優先順位の順に生成される。尚、この生成ステップ１５１０は１つの画素についてのみ１つ又は複数の塗りつぶし指令を生成することに注意すべきである。それらの塗りつぶし指令（出力指令）は図１４を参照して先に説明したようなフォーマットをとっていても良い。例えば、１つの画素の塗りつぶし指令はfill:object＝B;type＝bitmap;fill_address＝32;last_object＝false;fill:object＝A;type＝flat;fill_address＝20;last_object＝trueであっても良い。パラメータlast_object＝trueは、この塗りつぶし指令が現在画素に対する最終塗りつぶし指令であることを示す。オブジェクトの塗りつぶし指令はＸ独立フラグ（例えば、型）を更に含むのが好ましい。先に述べた通り、このフラグは、このアクティブオブジェクトの色が所定のＹ（すなわち、走査線）に対して一定であるか否かを指示する。
【０１１６】
生成ステップ１５１０の後、方法１５００は、先に生成された塗りつぶし指令と関連するオブジェクトが型パラメータに関してＸ独立であるか否かを判定する（１５１２）。
【０１１７】
決定ブロック１５１２が先に生成された塗りつぶし指令と関連する全てのオブジェクトはＸ独立であると判定した場合、方法１５００は、それらの先に生成された塗りつぶし指令を塗りつぶし色判定モジュール６００、画素合成モジュール７００及び画素出力モジュール８００へ送信する（１５１４）。ステップ１５１４の後、方法１５００は変数current_xを１増分し（１５１５）、ステップ１５１６へ進む。
【０１１８】
そこで、走査線の順で次の辺交差メッセージのＸ座標の値をnew_Xとし、変数current_xの現在値をcurrent_xとするとき、（new_X−current_x）＞０であるならば、方法１５００は指令「repeat（new_X−current_x）」を送信する（１５１６）。この場合、反復指令の前記フラグはＯＦＦにセットされる。これは、current_xの現在値に対する塗りつぶし指令を後続する位置についても反復すべきであることを指示する。次に、方法はステップ１５１８へ進む。しかし、値new_X−current_xが０に等しい場合には、反復指令は送信されず、方法は直接にステップ１５１８へ進む。
【０１１９】
そこで、方法１５００は変数current_xをnew_Xの値に設定し（１５１８）、ステップ１５０４に戻って、ループの次のパス中に、new_Xで辺交差を有する次の辺交差メッセージを処理する。
【０１２０】
これに対し、決定ブロック１５１２が先に生成された塗りつぶし指令の１つ又は複数のオブジェクトはＸ従属であると判定した場合には、方法１５００はステップ１５２０へ進む。このような状況は、例えば、オブジェクトの１つがビットマップである場合に起こるであろう。すなわち、決定ブロック１５１２がＦＡＬＳＥ（ノー）を戻したならば、方法１５００はcurrent_xに位置する画素に対して塗りつぶし指令（出力指令）を送信する（１５２０）。それらの指令は塗りつぶし色判定モジュール６００、画素合成モジュール７００及び画素出力モジュール８００へ送信される。
【０１２１】
送信ステップ１５２０の後、方法１５００は変数current_xを１増分し（１５２２）、決定ブロック１５２４へ進む。
【０１２２】
決定ブロック１５２４中、方法１５００は、変数current_xの現在値が走査線の順で次に処理されるべき辺交差メッセージのＸ座標であるnew_Xと等しいか否かを検査する。決定ブロック１５２４がcurrent_xの現在値はnew_Xと等しくないと判定したならば、方法１５００はステップ１５２０に戻る。ステップ１５２０では、current_xの新たな値に位置する画素に対して、先のステップ１５２０のパス中に送信されたのと同じ塗りつぶし指令を再び送信する。
【０１２３】
これに対し、決定ブロック１５２４がＴＲＵＥ（イエス）を戻した場合には、方法１５００はステップ１５０４に戻り、ループの次のパス中に次の辺交差メッセージを処理する。
【０１２４】
処理すべき辺交差メッセージがなくなった時点で、方法１５００は現在走査線に関する処理を終了する（図示せず）。
【０１２５】
次に図１６を参照すると、カラー動作モードで動作しているときに指令を生成する方法のフローチャートが示されている。指令を生成する方法１６００は、レンダリングすべき画像の走査線ごとに実行される。説明を容易にするため、ここでは現在走査中の走査線と呼ばれる１本の走査線についてのみ指令を発生する場合について方法を説明する。
【０１２６】
方法１６００は、現在走査中の走査線について、変数current_xを１に設定することにより始まる（１６０２）。この変数は、考慮すべき現在画素の位置を指示するカウンタとして機能する。先に述べた通り、辺交差メッセージ（入力指令）は走査線交差（Ｘ）座標の順にＦＩＦＯ５１８を介して優先順位判定モジュール５００へ送信される。方法１６００はそれらの辺交差メッセージをその走査線交差（Ｘ）座標の順に処理する。それらの辺交差メッセージは、図１４を参照して説明した、edge_crossing:x＝６;object＝A;edge＝UP;priority＝１１及びその他のフィールドのようなフォーマットをとっていても良い。
【０１２７】
方法１６００は、辺交差メッセージを検索し（１６０４）、ループの各々のパス中に走査線交差（Ｘ）座標の順にそれらのメッセージを処理するループ（１６０４−１６１２−１６０４、１６０４−１６４２−１６０４）の形態をとっている。同じ走査線交差座標（Ｘ）を有する複数の辺交差メッセージが存在する場合、方法は、ループの１回のパス中に処理するためのそれら複数の辺交差メッセージの全てを検索する（１６０４）。言い換えれば、ループの現在パス中、方法１６００は、走査線の順で、ループの最前のパス中に検索された辺交差メッセージの（Ｘ）座標の次に来る同じ（Ｘ）座標を有する１つ又は複数の辺交差メッセージを獲得する（１６０４）。
【０１２８】
開始ステップ１６０２の後、方法１６００は、走査線の順で最初に現れた走査線交差座標（Ｘ）を有する辺交差メッセージを獲得する（１６０４）。全て走査線の順で最初に現れた同じ交差（Ｘ）座標を有する複数の辺交差メッセージが存在する場合、方法はそれら最初の辺交差メッセージの全てを獲得する（１６０４）。また、方法１６００は、先に説明したように、現在Ｘ座標についてその時点で検索されている辺交差メッセージを使用してレベルアクティべーションテーブル５３０を更新する。最初の辺交差メッセージの（Ｘ）座標が２より大きい場合、方法１６００は更に指令「repeat X−2」を塗りつぶし色判定モジュール６００、画素合成モジュール７００及び画素出力モジュール８００へ送信する。初期反復指令は、画素X＝１からX−１にわたるオブジェクトが存在しないことを指示する。この反復指令のフラグは、画素X＝１からX−１にわたるオブジェクトが存在せず且つそれらの画素位置で背景をペイントしても良いことを指示するＯＮにセットされているのが好ましい。
【０１２９】
ステップ１６０４の後、方法１６００は、その時点で検索されている辺交差メッセージを利用して、フラグテーブル５０８及び５１０に格納されている「アクティブフラグ」及び「不透明アクティブフラグ」を更新する（１６０６）。「アクティブフラグ」及び「不透明アクティブフラグ」がどのようにして更新されるかについては先に詳細に説明してある。
【０１３０】
次に、方法１６００は、current_xの現在値に位置する画素について「アクティブフラグ」がＯＮにセットされている優先順位オブジェクトが存在するか否かを判定する（１６０８）。それら１つ又は複数のオブジェクトの全ての関連する「アクティブフラグ」がＯＦＦにセットされていたならば、それらのオブジェクトは現在画素に全く寄与しないので、決定ブロック１６０８はＦＡＬＳＥ（ノー）を戻し、方法１６００はステップ１６１６へ進む。
【０１３１】
そこで、走査線の順で次の辺交差メッセージのＸ座標の値をnew_Xとし、変数current_xの現在値をcurrent_xとするとき、（new_X−current_x）＞０であるならば、方法１６００は指令「repeat（new_X−current_x）」を送信する（１６１６）。この場合、反復指令の前記フラグは、current_xからnew_Xに位置する画素にわたるオブジェクトは存在せず且つそれらの画素位置で背景をペイントしても良いことを指示するＯＮにセットされている。次に、方法はステップ１６１８に進む。
【０１３２】
しかし、値new_X−current_xが０に等しい場合には、反復指令は送信されず、方法は直接にステップ１６１８へ進む。
【０１３３】
ステップ１６１８中、方法１６００は変数current_xを走査線の順で次の辺交差メッセージのＸ座標に等しいnew_Xに設定する。次に、方法１６００はステップ１６０４に戻り、方法１６００は、ループの次のパス中に処理するためにnew_Xで辺交差を有する次の辺交差メッセージを獲得する（１６０４）。
【０１３４】
これに対し、current_xの現在値に位置する画素についてオブジェクトの「アクティブフラグ」のいずれか１つがＯＮにセットされている場合には、決定ブロック１６０８はＴＲＵＥ（イエス）を戻し、方法１６００はステップ１６１０へ進む。
【０１３５】
ステップ１６１０中、方法１６００はcurrent_xの現在値に位置する画素に対して塗りつぶし指令を生成し始める。このステップ１６１０中、方法１６００は、優先順位の順に、「アクティブフラグ」がＯＮにセットされ且つ最高「不透明アクティブフラグ」がＯＮにセットされているオブジェクト以下の優先順位を有する、「アクティブフラグ」がＯＮにセットされているオブジェクトを判定する。それらの塗りつぶし指令のパラメータのデータは、それまでに検索されていた辺交差メッセージに含まれる情報から間接的に得られる。特に、塗りつぶし指令のパラメータは、current_xの現在値について更新後のレベルアクティべーションテーブル５３０から獲得される。この生成ステップ１６１０中、current_xの現在値に位置する画素に対する塗りつぶし指令が２つ以上存在する場合、方法１６００は更に塗りつぶし指令の優先順位を判定する。すなわち、current_xの現在値に位置する画素に対する塗りつぶし指令はそのオブジェクト優先順位の順に生成される。尚、この生成ステップ１６１０は１つの画素についてのみ１つ又は複数の塗りつぶし指令を生成することに注意すべきである。それらの塗りつぶし指令（出力指令）は先に図１４を参照して説明したようなフォーマットをとっていても良い。例えば、１つの画素に対する塗りつぶし指令はfill:object＝B;type＝bitmap;fill_address＝32;last_object＝false;no_pixel＝Z;fill:object＝A;type＝flat;fill_address＝20;last_object＝true;no_pixel＝Zであっても良い。パラメータlast_object＝trueは、この塗りつぶし指令が現在画素に対する最終塗りつぶし指令であることを示す。パラメータno_pixelは、現在画素から始めてこの塗りつぶし指令が適用される連続する画素の数を示す１から４までの数字である。このパラメータの値は方法１６００中、塗りつぶし指令を送信する直前に判定される。１つのオブジェクトに関する塗りつぶし指令はＸ独立フラグ（例えば、型）を更に含むのが好ましい。先に述べた通り、このフラグは、このアクティブオブジェクトの色が所定のＹ（すなわち、走査線）に対して一定であるか否かを指示する。
【０１３６】
生成ステップ１６１０の後、方法１６００は、ループの現在パス中に生成された塗りつぶし指令と関連するオブジェクトが型パラメータに関してＸ独立であるか否かを判定する（１６１２）。
【０１３７】
決定ブロック１６１２がループの現在パス中に生成された塗りつぶし指令と関連する全てのオブジェクトはＸ独立であると判定した場合、方法１６００はそれらの塗りつぶし指令を塗りつぶし色判定モジュール６００、画素合成モジュール７００及び画素出力モジュール８００へ送信する（１６１４）。それらの塗りつぶし指令を送信する（１６１４）前に、方法１６００は塗りつぶし指令のパラメータno_pixelを１に設定する。ステップ１６１４の後、方法１６００は変数current_xを１増分し（１６１５）、ステップ１６１６へ進む。
【０１３８】
そこで、走査線の順で次の辺交差メッセージのＸ座標の値をnew_Xとし、変数current_xの現在値をcurrent_xとするとき、（new_X−current_x）＞０であるならば、方法１６００は指令「repeat（new_X−current_x）」を送信する（１６１６）。この場合、反復指令の前記フラグはＯＦＦにセットされている。これは、current_xの現在値についての塗りつぶし指令を後続する画素位置に対して反復すべきであることを指示する。次に、方法はステップ１６１８へ進む。しかし、値new_X−current_xが０に等しい場合には、反復指令は送信されず、方法は直接にステップ１６１８へ進む。
【０１３９】
次に、方法１６００は変数current_xをnew_Xの値に設定し（１６１８）、ステップ１６０４に戻って、ループの次のパス中に、new_Xで辺交差を有する次の辺交差メッセージを処理する。
【０１４０】
これに対し、決定ブロック１６１２がループの現在パス中に生成された塗りつぶし指令の１つ又は複数のオブジェクトはＸ従属であると判定した場合には、方法１６００は決定ブロック１６２６へ進む。このような状況は、例えば、オブジェクトの１つがビットマップである場合に起こるであろう。すなわち、決定ブロック１６１２がＦＡＬＳＥ（ノー）を戻した場合、方法１６００は決定ブロック１６２６へ進む。
【０１４１】
決定ブロック１６２６は、値current_x＋3がnew_Xより小さいか否かを判定する。決定ブロック１６２６がＴＲＵＥ（イエス）を戻した場合、方法１６００は４つの画素について有効である１つ又は複数の塗りつぶし指令を送信する（１６２８）。すなわち、方法１６００は、ループの現在パス中に生成された塗りつぶし指令を塗りつぶし色判定モジュール６００、画素合成モジュール７００及び画素出力モジュール８００へ送信する（１６２８）。この送信（１６２８）に先立って、方法１６００はそれらの塗りつぶし指令のno_pixelパラメータを４に設定する。ステップ１６２８の後、方法は変数current_xを４増分し（１６３０）、決定ブロック１６２６に戻る。決定ブロック１６２６が再びＴＲＵＥ（イエス）を戻した場合には、方法１６００は、no_pixelパラメータを４に設定した状態でループの現在パス中に生成されたもう１組の塗りつぶし指令を送信する（１６２８）。
【０１４２】
これに対し、決定ブロック１６２６がＦＡＬＳＥ（ノー）を戻した場合には、方法１６００は決定ブロック１６３２へ進む。決定ブロック１６３２は、値current_x＋2がnew_Xより小さいか否かを判定する。決定ブロック１６３２がＴＲＵＥ（イエス）を戻した場合、方法１６００はループの現在パス中に生成された塗りつぶし指令を塗りつぶし色判定モジュール６００、画素合成モジュール７００及び画素出力モジュール８００へ送信する（１６３４）。この送信（１６３４）に先立って、方法１６００はそれらの塗りつぶし指令のno_pixelパラメータを３に設定する。ステップ１６３４の後、方法は変数current_xを３増分し（１５３０）、決定ブロック１６３２に戻る。
【０１４３】
決定ブロック１６３２がＦＡＬＳＥ（ノー）を戻した場合、方法１６００は決定ブロック１６３６へ進む。決定ブロック１６３６は、値current_x＋１がnew_Xより小さいか否かを判定する。決定ブロック１６３６がＴＲＵＥ（イエス）を戻した場合、方法１６００は２つの画素について有効である１つ又は複数の塗りつぶし指令を送信する（１６３８）。すなわち、方法１６００は、ループの現在パス中に生成された塗りつぶし指令を塗りつぶし色判定モジュール６００、画素合成モジュール７００及び画素出力モジュール８００へ送信する（１６３８）。この送信（１６３８）に先立って、方法１６００はそれらの塗りつぶし指令のno_pixelパラメータを２に設定する。ステップ１６３８の後、方法は変数current_xを２増分し（１６４０）、決定ブロック１６３６に戻る。
【０１４４】
決定ブロック１６３６がＦＡＬＳＥ（ノー）を戻した場合には、方法１６００は決定ブロック１６４２に戻る。決定ブロック１６４２は、値current_xがnew_Xより小さいか否かを判定する。決定ブロック１６４２がＴＲＵＥ（イエス）を戻した場合、方法１６００は１つの画素について有効である１つ又は複数の塗りつぶし指令を送信する（１６４４）。すなわち、方法１６００は、ループの現在パス中に生成された塗りつぶし指令を塗りつぶし色判定モジュール６００、画素合成モジュール７００及び画素出力モジュール８００へ送信する（１６４４）。この送信（１６４４）に先立って、方法１６００はそれらの塗りつぶし指令のno_pixelパラメータを１に設定する。ステップ１６４４の後、方法は変数current_xをnew_Xに設定し（１６４６）、ステップ１６０４に戻って、次の辺交差メッセージを処理する。
【０１４５】
これに対し、決定ブロック１６４２がＦＡＬＳＥ（ノー）を戻した場合には、方法１６００は変数current_xをnew_Xに設定し（１６４６）、ステップ１６０４に戻って、次の辺交差メッセージを処理する。
【０１４６】
処理すべき辺交差メッセージがなくなった時点で、現在走査線について方法１６００の処理は終了する（図示せず）。
【０１４７】
カラー動作モードで動作しているとき、塗りつぶし色判定モジュール６００は塗りつぶし指令を獲得し、塗りつぶし指令のパラメータに含まれている情報を利用して画素を生成する。塗りつぶし色判定モジュール６００は、カラー動作モードで動作しているとき、そのような画素を一度に１つずつ出力カラーチャネルを介して出力する。それらの画素は複数の色成分を有し、それらの色成分は塗りつぶし色判定モジュール６００のそれぞれ対応するカラー出力チャネルから出力される。また、塗りつぶし色判定モジュール６００は反復指令をカラー出力チャネルを介して画素出力モジュール８００へ送信する。画素出力モジュール８００は反復指令を受信すると、先に出力された画素を反復指令のパラメータに従った回数だけ繰り返し出力する。塗りつぶし色判定モジュール６００は塗りつぶし指令ごとに１つの画素を生成し、走査線の現在画素位置に対して複数の塗りつぶし指令が存在する場合には、塗りつぶし色判定モジュール６００は走査線のその現在位置について複数の画素を生成し、優先順位の順にそれらの画素を一度に１つずつ出力チャネルから出力する。塗りつぶし色判定モジュール６００が走査線の現在画素位置について複数の画素を生成する場合、塗りつぶし色判定モジュール６００は、更に、それらの生成画素を合成するための合成情報を含む合成メッセージを生成する。合成メッセージは、元の塗りつぶし指令から得られる合成情報から構成される。それらの合成メッセージは塗りつぶし色判定モジュール６００からカラー出力チャネルを介して画素合成モジュール７００へも送信される。
【０１４８】
加速グレイスケール動作モードで動作しているとき、塗りつぶし色判定モジュール６００は塗りつぶし指令を獲得し、塗りつぶし指令のパラメータに含まれている情報を利用して、１つの色成分を有する画素を生成する。それらの画素は、その後、塗りつぶし指令のパラメータno_pixelに応じて塗りつぶし色判定モジュール６００のそれぞれのカラー出力チャネルから出力される。例えば、塗りつぶし指令のパラメータno_pixel＝４である場合、塗りつぶし色判定モジュール６００の４つの出力チャネルから４つの画素が同時に出力される。また、塗りつぶし色判定モジュール６００は、塗りつぶし指令に含まれる合成情報を使用して合成メッセージを送信する。それらの合成メッセージは塗りつぶし色判定モジュール６００から出力チャネルを介して画素合成モジュール７００へ送信される。同様に、それらの合成メッセージはno_pixelなどのパラメータを含む場合があり、それにより、画素合成モジュール７００から出力チャネルを介していくつかの画素が同時に出力されることになる。加速グレイスケール動作モードでは、塗りつぶし色判定モジュール６００は、更に、カラー動作モードの場合と同様に反復指令を送信する。
【０１４９】
【産業上の適用可能性】
以上の説明から、本発明の実施形態はコンピュータグラフィックス及びプリントの分野に適用可能であることが明白である。
【０１５０】
以上、本発明の実施形態を説明したが、それらの実施形態は単なる例であって、限定的な意味を持たず、本発明の趣旨から逸脱せずに実施形態に対して変形及び／又は変更を実施することは可能である。
【図面の簡単な説明】
【図１】好適な実施形態によるコンピュータシステムを示す概略ブロック構成図である。
【図２】好適な実施形態の機能データ流れを示すブロック構成図である。
【図３】好適な実施形態の画素逐次レンダリング装置と、関連する表示リスト及び一時ストアとを示す概略ブロック構成図である。
【図４】図２の辺処理モジュールの概略機能図である。
【図５】図２の優先順位判定モジュールの概略機能図である。
【図６】図２の塗りつぶしデータ判定モジュールの概略機能図である。
【図７】好適な実施形態の動作を説明するための一例として使用される２オブジェクト画像を示す図である。
【図８Ａ】、
【図８Ｂ】図７のオブジェクトのベクトル辺を示す図である。
【図９】図７の画像の数本の走査線のレンダリングを示す図である。
【図１０】図７のカラーレンダリングを実行するときに出力される様々なモジュールにおける処理画素のスナップショットを示す図である。
【図１１Ａ】、
【図１１Ｂ】偶数／奇数及び非ゼロワインディング塗りつぶし規則を示す図である。
【図１２Ａ】、
【図１２Ｂ】、
【図１２Ｃ】、
【図１２Ｄ】、
【図１２Ｅ】図５の構成により実現される優先塗りつぶしルーチンを示す図である。
【図１３Ａ】、
【図１３Ｂ】カラー動作モード及びグレイスケール動作モード中の画素逐次レンダリング装置の機能データ流れを示す図である。
【図１４】複数のオブジェクトから構成される画像の一例を表す図である。
【図１５】カラー動作モードで動作しているときの指令生成方法を示すフローチャートである。
【図１６】加速グレイスケール動作モードで動作しているときの指令生成方法を示すフローチャートである。
Claims (2)
- デジタル画像の画素を処理する画像処理装置であって、
複数のカラー出力チャネルを有する画像処理装置を第１の動作モード又は第２の動作モードで動作するように構成するホストプロセッサを具備し、前記画像処理装置は、
前記第１の動作モード中、複数の画素色成分を有する１つのカラー画素を生成し、且つ生成された各画素の前記複数の画素色成分を、対応する前記カラー出力チャネルから出力することにより、前記生成された複数のカラー画素を出力する塗りつぶしモジュールと、
前記第２の動作モード中、塗りつぶし指令が適用されるラスタ順の連続する画素位置の数であって、１から前記カラー出力チャネルの数に等しい最大数まで変化できる数を指示するパラメータをそれぞれ含む１つ又は複数の塗りつぶし指令を生成するモジュールとを具備し、
前記塗りつぶしモジュールは、前記第２の動作モード中、１つ又は複数の前記画素位置に対して１つ又は複数の前記塗りつぶし指令に応答して、塗りつぶし指令の数及び前記塗りつぶし指令のパラメータに従って決まる数の、各々が１つの画素色成分を有する画素を生成し、且つ複数の前記画素を、前記複数の前記カラー出力チャネルから出力することを特徴とする画像処理装置。 - デジタル画像の画素を処理する画像処理装置において、
画像処理装置を第１の動作モード又は第２の動作モードで動作するように構成するホストプロセッサを具備し、前記画像処理装置は、
前記第１の動作モード中、対応する画素位置に対して１つ又は複数の塗りつぶし指令を生成する優先順位モジュールと、
前記第１の動作モード中、前記画素位置に対して１つ又は複数の対応する前記塗りつぶし指令に応答して、複数の画素色成分を有する１つの画素を出力する塗りつぶしモジュールとを具備し、
前記優先順位モジュールは、前記第２の動作モード中、塗りつぶし指令が適用されるラスタ順の連続する画素位置の数であって、１から前記カラー出力チャネルの数に等しい最大数まで変化できる数を指示するパラメータをそれぞれ含む１つ又は複数の塗りつぶし指令を生成し、且つ
前記塗りつぶしモジュールは、前記第２の動作モード中、１つ又は複数の前記画素位置に対して１つ又は複数の前記塗りつぶし指令に応答して、塗りつぶし指令の数及び前記塗りつぶし指令のパラメータに従って決まる数の、各々が１つの画素色成分を有する複数の画素を生成し、且つ生成された複数の画素を、対応する複数の前記カラー出力チャネルから出力することを特徴とする画像処理装置。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| AUPQ7580A AUPQ758000A0 (en) | 2000-05-17 | 2000-05-17 | Processing pixels of a digital image |
| AU7580 | 2000-05-17 |
Publications (3)
| Publication Number | Publication Date |
|---|---|
| JP2002063583A JP2002063583A (ja) | 2002-02-28 |
| JP2002063583A5 JP2002063583A5 (ja) | 2008-07-03 |
| JP4646436B2 true JP4646436B2 (ja) | 2011-03-09 |
Family
ID=3821658
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP2001148269A Expired - Fee Related JP4646436B2 (ja) | 2000-05-17 | 2001-05-17 | デジタル画像の画像処理装置 |
Country Status (3)
| Country | Link |
|---|---|
| US (1) | US6795048B2 (ja) |
| JP (1) | JP4646436B2 (ja) |
| AU (1) | AUPQ758000A0 (ja) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US11521302B2 (en) | 2019-07-10 | 2022-12-06 | Canon Kabushiki Kaisha | Image processing apparatus and image processing method |
Families Citing this family (10)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6891536B2 (en) * | 2001-11-30 | 2005-05-10 | Canon Kabushiki Kaisha | Method of determining active priorities |
| AUPS134202A0 (en) | 2002-03-25 | 2002-05-09 | Canon Kabushiki Kaisha | System and method for optimizing halftoning printer performance |
| US7755629B2 (en) * | 2004-06-30 | 2010-07-13 | Canon Kabushiki Kaisha | Method of rendering graphic objects |
| US7230560B2 (en) * | 2005-08-05 | 2007-06-12 | Microsoft Corporation | Image compression and decompression |
| US20070085860A1 (en) * | 2005-10-13 | 2007-04-19 | Honeywell International Inc. | Technique for improving the readability of graphics on a display |
| US20090096792A1 (en) * | 2007-10-15 | 2009-04-16 | Ati Technologies Ulc | Fill mode determination in vector graphics |
| US8595689B2 (en) | 2008-12-24 | 2013-11-26 | Flir Systems Ab | Executable code in digital image files |
| US8749572B2 (en) * | 2010-05-28 | 2014-06-10 | Adobe Systems Incorporated | System and method for simulation of brush-based painting in a color space that includes a fill channel |
| US8988461B1 (en) | 2011-01-18 | 2015-03-24 | Disney Enterprises, Inc. | 3D drawing and painting system with a 3D scalar field |
| US9142056B1 (en) * | 2011-05-18 | 2015-09-22 | Disney Enterprises, Inc. | Mixed-order compositing for images having three-dimensional painting effects |
Citations (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH0652323A (ja) * | 1992-07-31 | 1994-02-25 | Canon Inc | 画像処理方法及び装置 |
| JPH07105388A (ja) * | 1993-06-23 | 1995-04-21 | Sun Microsyst Inc | 高性能３次元グラフィック・アクセラレータの作図プロセッサ |
| JPH09507310A (ja) * | 1994-01-04 | 1997-07-22 | ハネウエル・インコーポレーテッド | ラスタ・エンハンスメント機構を備えた再構成可能なビデオ出力アーキテクチャ |
Family Cites Families (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5097518A (en) * | 1990-02-27 | 1992-03-17 | Eastman Kodak Company | Technique for performing digital image scaling by logically combining or replicating pixels in blocks of differing groupsizes |
| US5237655A (en) * | 1990-07-05 | 1993-08-17 | Eastman Kodak Company | Raster image processor for all points addressable printer |
| EP0673011B1 (en) * | 1994-03-11 | 1999-06-02 | Canon Kabushiki Kaisha | Dynamic refinement of pixel structure in a display |
-
2000
- 2000-05-17 AU AUPQ7580A patent/AUPQ758000A0/en not_active Abandoned
-
2001
- 2001-05-02 US US09/846,365 patent/US6795048B2/en not_active Expired - Lifetime
- 2001-05-17 JP JP2001148269A patent/JP4646436B2/ja not_active Expired - Fee Related
Patent Citations (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH0652323A (ja) * | 1992-07-31 | 1994-02-25 | Canon Inc | 画像処理方法及び装置 |
| JPH07105388A (ja) * | 1993-06-23 | 1995-04-21 | Sun Microsyst Inc | 高性能３次元グラフィック・アクセラレータの作図プロセッサ |
| JPH09507310A (ja) * | 1994-01-04 | 1997-07-22 | ハネウエル・インコーポレーテッド | ラスタ・エンハンスメント機構を備えた再構成可能なビデオ出力アーキテクチャ |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US11521302B2 (en) | 2019-07-10 | 2022-12-06 | Canon Kabushiki Kaisha | Image processing apparatus and image processing method |
Also Published As
| Publication number | Publication date |
|---|---|
| US20020175925A1 (en) | 2002-11-28 |
| AUPQ758000A0 (en) | 2000-06-08 |
| US6795048B2 (en) | 2004-09-21 |
| JP2002063583A (ja) | 2002-02-28 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JP3919754B2 (ja) | 画素順次描画システムにおいて実行される合成演算回数の削減法 | |
| JP4366387B2 (ja) | 画像処理装置及び方法 | |
| JP4343344B2 (ja) | ラスタ形式のグラフィックオブジェクトを用いたイメージの高速レンダリング方法 | |
| US20100315431A1 (en) | Combining overlapping objects | |
| EP1577838B1 (en) | A method of rendering graphical objects | |
| US7538770B2 (en) | Tree-based compositing system | |
| JP4646436B2 (ja) | デジタル画像の画像処理装置 | |
| US8723884B2 (en) | Scan converting a set of vector edges to a set of pixel aligned edges | |
| US7714865B2 (en) | Compositing list caching for a raster image processor | |
| US7551173B2 (en) | Pixel accurate edges for scanline rendering system | |
| JPH0872317A (ja) | カラー印刷装置及びその方法 | |
| US20060001681A1 (en) | Method of rendering graphic objects | |
| US6591020B1 (en) | Antialiazed high-resolution frame buffer architecture | |
| JP2009009345A (ja) | ベクター画像描画装置、ベクター画像描画方法およびプログラム | |
| JP3604152B2 (ja) | ページプリンタ用に強度のレンダリングを必要としないプロセッサ／メモリ | |
| JP6904717B2 (ja) | 画像処理装置、その制御方法、およびプログラム | |
| JP2008107970A (ja) | 画像形成装置 | |
| JPH09171564A (ja) | 描画装置 | |
| JPH0729021A (ja) | 画像出力装置 | |
| AU770175B2 (en) | Processing pixels of a digital image | |
| JP2006031160A (ja) | グラフィックオブジェクト処理方法 | |
| JPH09314915A (ja) | 印刷制御装置と印刷装置の制御方法、印刷システム、並びに記憶媒体 | |
| JP2005235205A (ja) | 形状チャネルを用いないクリップ・トゥ・セルフ（ｃｌｉｐ−ｔｏ−ｓｅｌｆ）機能を有する合成 | |
| JP4533019B2 (ja) | グラフィックオブジェクト処理装置及びグラフィックオブジェクト処理方法 | |
| AU2004200655B2 (en) | Reducing the Number of Compositing Operations Performed in a Pixel Sequential Rendering System |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A521 | Request for written amendment filed |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20080519 |
|
| A621 | Written request for application examination |
Free format text: JAPANESE INTERMEDIATE CODE: A621 Effective date: 20080519 |
|
| A977 | Report on retrieval |
Free format text: JAPANESE INTERMEDIATE CODE: A971007 Effective date: 20100712 |
|
| A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20100720 |
|
| A521 | Request for written amendment filed |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20100916 |
|
| 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: 20101206 |
|
| A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 |
|
| A61 | First payment of annual fees (during grant procedure) |
Free format text: JAPANESE INTERMEDIATE CODE: A61 Effective date: 20101207 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20131217 Year of fee payment: 3 |
|
| R150 | Certificate of patent or registration of utility model |
Free format text: JAPANESE INTERMEDIATE CODE: R150 |
|
| LAPS | Cancellation because of no payment of annual fees |