(57)【特許請求の範囲】
【請求項１】
表現ツリーを生成する装置であって、前記表現ツリーは、１つ以上のバイナリノードと複数のリーフノードを有する複数のノードを有し、ここで、それぞれの前記バイナリノードはそれにぶらさがる左ブランチと右ブランチとを有して該２つのぶらさがるノードへの２進演算を表し、それぞれの前記ノードは、１個以上のグラフィックオブジェクトが重なったグラフィックオブジェクトを表し、前記グラフィックオブジェクトの重なりの各々が、左ノード領域、共通領域、および右ノード領域を含み、前記装置が、
１つ以上の画素位置のグループを決定する手段と、
それぞれの前記グループについて、前記１つ以上のバイナリノードの左右のブランチが、現在スキャンされている画素がブランチに対応するグラフィックオブジェクトに適用される境界エッジの中にあるならばアクティブであると判断し、現在スキャンされている画素がブランチに対応するグラフィックオブジェクトに適用される境界エッジの外にあるならば非アクティブであると判断する手段と、
それぞれの前記グループについて、前記表現ツリーをなぞる手段と、ここで、なぞられたバイナリノードの左右ブランチがアクティブである場合、或いは、前記左ノード領域が前記なぞられたバイナリノードの２進演算に必要であり、前記なぞられたバイナリノードの左ブランチがアクティブで右ブランチが非アクティブである場合に、前記なぞられたバイナリノードの左ブランチにぶらさがるノードへなぞられ、また、前記なぞられたバイナリノードの左右ブランチがアクティブである場合、或いは、前記右ノード領域が前記なぞられたバイナリノードの２進演算に必要であり、前記なぞられたバイナリノードの右ブランチがアクティブであり、左ブランチが非アクティブである場合に、前記なぞられたバイナリノードの右ブランチにぶらさがるノードへなぞられ、
それぞれの前記グループのために、前記アクティブな左右ブランチを有する前記なぞられたバイナリノードのための演算子命令、およびなぞられたリーフノードのためのリーフ値命令を生成する手段とを備えることを特徴とする装置。
【請求項２】
前記なぞる手段は表現ツリーをなぞり、前記なぞられたバイナリノードの左右ブランチがアクティブであり、前記なぞられたバイナリノードの右ブランチの下方ノードを表すグラフィックオブジェクトが、前記なぞられたバイナリノードの下方ノードの共通領域において、前記なぞられたバイナリノードの前記左ブランチの下方ノードを表すグラフィックオブジェクトを隠さない場合、前記なぞられたバイナリノードの左ブランチの下方ノードへとなぞられ、また、なぞられたバイナリノードの左右ブランチがアクティブであり、前記なぞられたバイナリノードの前記左ブランチの下方ノードを表すグラフィックオブジェクトが、前記なぞられたバイナリノードの下方ノードを表すグラフィックオブジェクトの共通領域において、前記なぞられたバイナリノードの右ブランチの下方ノードを表すグラフィックオブジェクトを隠さない場合、前記なぞられたバイナリノードの右ブランチの下方ノードへなぞられることを特徴とする請求項１に記載の装置。
【請求項３】
表現ツリーから、複数の走査線と各走査線に複数の画素位置を有するラスタ画素イメージを描画する装置であって、前記表現ツリーは１つ以上のバイナリノードと複数のリーフノードとを備える複数のノードを有し、ここで前記バイナリノードの各々は下方ノードを有する左ブランチと下方ノードを有する右ブランチを有するとともに２つの前記下方ノードに対する２進演算を表わし、また前記リーフノードの各々は１つ以上のグラフィックオブジェクトが重なったグラフィックオブジェクトを表し、重なっているグラフィックオブジェクトの各々は左ノード領域、共通領域、および右ノード領域を含み、
前記表現ツリーを表すテーブルを生成する手段と、ここで前記テーブルは関連するバイナリノードとリーフノードに対応する複数のレコードを含み、そして、前記関連するバイナリノードのそれぞれの前記レコードは、前記左ノード領域が前記関連するバイナリノードに関連する演算子の動作に必要であるかどうかを示す第１フィールドと、右ノード領域が前記関連するバイナリノードに関連する演算子の動作に必要であるかどうかを示す第２フィールドと、前記関連するバイナリノードの左ブランチがアクティブであるかどうかを示す第３フィールドと、前記関連するバイナリノードの右ブランチがアクティブかどうかを示す第４フィールドとを備え、
１つ以上の画素位置のグループを決定する手段と、
前記グループの各々に関して、前記１つ以上のバイナリノードの左右のブランチが、現在スキャンされている画素がブランチに対応するグラフィックオブジェクトに適用される境界エッジの中にあるならばアクティブであると判断し、現在スキャンされている画素がブランチに対応するグラフィックオブジェクトに適用される境界エッジの外にあるならば非アクティブであると判断する手段と、
前記グループの各々に関して、前記判断されたアクティブ及び非アクティブのブランチのために、前記テーブルの前記第３及び第４フィールドを更新する手段と、
それぞれの前記グループに関して、前記更新されたテーブルに従って、前記表現ツリーをなぞる手段と、ここで、なぞられたバイナリノードの左右ブランチがアクティブであるか、または、前記左ノード領域がなぞられたバイナリノードの２進演算に必要であり、該なぞられたバイナリノードの左ブランチがアクティブであり、かつ右ブランチが非アクティブである場合に、前記なぞられたバイナリノードの左ブランチがその下方ノードへとなぞられ、また、前記なぞられたバイナリノードの左右ブランチがアクティブであるか、または前記右ノード領域がなぞられたバイナリノードの２進演算に必要であり、該なぞられたバイナリノードの右ブランチがアクティブであり、左ブランチが非アクティブである場合に、なぞられたバイナリノードの右ブランチがその下方ノードへとなぞられ、
前記グループの各々に関して、前記右及び左ブランチがアクティブであるなぞられたバイナリノードに対して演算命令を生成し、なぞられたリーフノードに対してリーフ値命令を生成する手段と、
前記グループの各々に関して、前記イメージを描画するために、前記生成された対応する命令を実行する手段とを備えることを特徴とする装置。
【請求項４】
前記テーブルは、前記関連するバイナリノードのそれぞれの前記レコードに関して、前記関連するバイナリノードの右ブランチの下方ノードを表すグラフィックオブジェクトが、前記関連するバイナリノードの下方ノードを表すグラフィックオブジェクトの共通領域において、前記関連するバイナリノードの左ブランチの下方ノードを表すグラフィックオブジェクトを隠すかどうかを表す第５フィールドと、前記関連するバイナリノードの左ブランチの下方ノードを表すグラフィックオブジェクトが、前記関連するバイナリノードの下方ノードを表すグラフィックオブジェクトの共通領域において、前記関連するバイナリノードの右ブランチの下方ノードを表すグラフィックオブジェクトを隠すかどうかを表す第６フィールドとを更に備え、前記なぞる手段は、前記更新されたテーブルに従って、前記表現ツリーをなぞり、ここでなぞられたバイナリノードの左右ブランチがアクティブであり、前記なぞられたバイナリノードの右ブランチの下方ノードを表すグラフィックオブジェクトが、前記なぞられたバイナリオブジェクトの下方ノードを表すグラフィックオブジェクトの共通領域において、前記なぞられたバイナリノードの左ブランチの下方ノードを表すグラフィックオブジェクトを隠さない場合は、なぞられたバイナリノードの左ブランチの下方ノードへ向かってなぞられ、なぞられたバイナリノードの左右ブランチがアクティブであり、前記なぞられたバイナリノードの左ブランチの下方ノードを表すグラフィックオブジェクトが、前記なぞられたバイナリオブジェクトの下方ノードを表すグラフィックオブジェクトの共通領域において、前記なぞられたバイナリノードの右ブランチの下方ノードを表すグラフィックオブジェクトを隠さない場合は、なぞられたバイナリノードの右ブランチの下方ノードへ向かってなぞられることを特徴とする請求項３に記載の装置。
【請求項５】
前記第５フィールド及び第６フィールドは、CLIP INもしくはCLIPOUT動作を実行するのに使用されることを特徴とする請求項４に記載の装置。
【発明の詳細な説明】
【０００１】
著作権表示
本特許明細書は著作権保護を受ける対象となる内容を含む。著作権所有者は、この特許明細書、もしくは特許庁からの関連する資料をレビューの目的で複製することに異議を唱えるものではないが、他の点においてはあらゆる著作権を保有するものである。
【０００２】
発明の技術分野
本発明は、グラフィックオブジェクトベースのイメージの描画に関するものである。特に、本発明は表現ツリーのための命令を生成するための方法と装置に関連する。また、本発明はラスタ画素イメージに表現ツリーを描画するための方法と装置に関連する。また、発明は上述の方法のいずれかを実行するためのコンピュータプログラムを備えたコンピュータ可読媒体に関連する。
【０００３】
発明の背景
大部分のオブジェクトベースのグラフィックスシステムでは、ページまたは画面上の画素ベース画像を保持するためにフレームストアまたはページバッファが使用される。通常、グラフィックオブジェクトの輪郭は、計算され、塗り潰され、フレームストアに書き込まれる。二次元グラフィックスの場合、他のオブジェクトの手前にあるオブジェクトは、単純に背景オブジェクトを書き込んだ後にフレームストアに書き込まれ、これによって、画素単位で背景を置換する。これは、当技術分野では、「ペインタのアルゴリズム（Painter's algorithm）」として一般に知られているものである。オブジェクトは、最も奥のオブジェクトから最も手前のオブジェクトという優先順位で考慮され、通常は、各オブジェクトがスキャンラインの順序でラスタ化され、各スキャンラインに沿ったシーケンシャルな並びで画素がフレームストアに書き込まれる。
【０００４】
この技法には、基本的に２つの問題がある。第１の問題は、フレームストア内のすべての画素への高速なランダムアクセスが必要であることである。これは、新たに考慮される各オブジェクトが、フレームストア内のどの画素にも影響を及ぼす可能性があるからである。このため、フレームストアは、通常は半導体のランダムアクセスメモリ（ＲＡＭ）内に保持される。高解像度カラープリンタの場合、必要なＲＡＭの量は非常に多くなり、通常は１００Ｍバイトを超える。このため、コストがかかり、高速での動作が困難である。第２の問題は、多数の画素がペイント（レンダリング）され、その後、時間的に後のオブジェクトによって上塗り（再レンダリング）されることである。このため、時間的に前のオブジェクトによる画素のペイントは、時間の浪費になる。
【０００５】
大量のフレームストアの問題を克服するための方法の１つが、「バンディング（banding）」の使用である。バンディングを使用する場合には、フレームストアの一部だけが常時メモリ内に存在することになる。描画されるべきオブジェクトのすべてが「表示リスト」に保持される。画像全体は上記と同様にレンダリングされるが、存在するフレームストアの部分の外側をペイント（レンダリング）しようとする画素ペイント（レンダリング）動作は、「クリップ」アウトされる。オブジェクトのすべてが描画された後、フレームストアの部分をプリンタ（または他の場所）に送り、フレームストアの別の部分を選択し、この処理を繰り返す。この技法には、ペナルティが伴う。たとえば、描画されるオブジェクトは考慮され、何度も（バンドごとに１回）再考慮されなければならない。バンドの数が増えるにつれて、レンダリングが必要なオブジェクトの検査の繰り返し回数も増える。従って、バンディングの技法は、上塗りのコストという問題を解決しない。
【０００６】
いくつかの他のグラフィックシステムでは、スキャンラインの順で画像が検討される。やはり、描画されるオブジェクトのすべてが、表示リストに保存される。各スキャンライン上で、そのスキャンラインと交差するオブジェクトが優先順位の順でオブジェクトごとに検討され、オブジェクトのエッジの交差点の間の画素のスパンが、ラインストアにセットされる。この技法も、大量のフレームストアの問題を克服するが、やはり上塗りの問題をこうむる。
【０００７】
これらのほかに、大きいフレームストアの問題と上塗りの問題の両方を解決する技法がある。そのような技法の１つでは、各スキャンラインが順番に作られる。やはり、描画されるオブジェクトのすべてが、表示リストに保存される。各スキャンラインでは、そのスキャンラインと交差するオブジェクトのエッジが、スキャンラインとの交差の座標の昇順で保持される。これらの交差の点、すなわちエッジの交点が、順番に検討され、アクティブフィールドの配列のトグルに使用される。そのスキャンライン上での対象となるオブジェクト優先順位ごとに１つのアクティブフィールドがある。考慮されるエッジの対のそれぞれの間で、最初のエッジと次のエッジの間にある各画素の色データが、アクティブフラグに対する優先順位エンコーダを使用してどの優先順位が最も上にあるかを判定すること、および２つのエッジの間のスパンの画素に関するその優先順位に関連する色を使用することによって生成される。次のスキャンラインに備えて、各エッジの交差の座標が、各エッジの性質に応じて更新される。この更新の結果として誤ってソートされた状態になった隣接するエッジは、交換される。新しいエッジも、エッジのリストに合併される。
【０００８】
この技法は、フレームストアまたはラインストアがなく、上塗りがなく、オーダーＮの回数（このＮは優先順位の数）ではなく一定のオーダーの時間でオブジェクト優先順位が処理されるという大きい長所を有する。
【０００９】
しかしながら、これらの優先順位エンコーダはツリーベースのグラフィカルな表現に対処するための柔軟性を欠いている。特に、Porter,T、Duff,Tによる「合成ディジタルイメージ（Compositing Digital Images）」（Vol.18、No.3(1984)pp.253-259）で記述されるような、OUTとATOP PorterおよびDuffの合成演算子を含むそれらの表現に対処するための柔軟性を欠く。与えられた画素位置において、合成演算が、その演算によって合成されたグラフィックオブジェクトのどれが有効であるのかに依存するために、問題が生じる。この問題の１つの解決は切取りオブジェクトの複雑な整理を使用することである。それは多くの余分なエッジ処理を必要として、切取りオブジェクトに関する多くのレベルを必要とする。
【００１０】
本発明の目的は、既存の構成の１つまたは複数の短所を実質的に克服するか、少なくとも改善することである。
【００１５】
本発明の第１の態様によれば、次の装置が提供される。すなわち、表現ツリーを生成する装置であって、前記表現ツリーは、１つ以上のバイナリノードと複数のリーフノードを有する複数のノードを有し、ここで、それぞれの前記バイナリノードはそれにぶらさがる左ブランチと右ブランチとを有して該２つのぶらさがるノードへの２進演算を表し、それぞれの前記ノードは、１個以上のグラフィックオブジェクトが重なったグラフィックオブジェクトを表し、前記グラフィックオブジェクトの重なりの各々が、左ノード領域、共通領域、および右ノード領域を含み、前記装置が、
１つ以上の画素位置のグループを決定する手段と、
それぞれの前記グループについて、前記１つ以上のバイナリノードの左右のブランチが、現在スキャンされている画素がブランチに対応するグラフィックオブジェクトに適用される境界エッジの中にあるならばアクティブであると判断し、現在スキャンされている画素がブランチに対応するグラフィックオブジェクトに適用される境界エッジの外にあるならば非アクティブであると判断する手段と、
それぞれの前記グループについて、前記表現ツリーをなぞる手段と、ここで、なぞられたバイナリノードの左右ブランチがアクティブである場合、或いは、前記左ノード領域が前記なぞられたバイナリノードの２進演算に必要であり、前記なぞられたバイナリノードの左ブランチがアクティブで右ブランチが非アクティブである場合に、前記なぞられたバイナリノードの左ブランチにぶらさがるノードへなぞられ、また、前記なぞられたバイナリノードの左右ブランチがアクティブである場合、或いは、前記右ノード領域が前記なぞられたバイナリノードの２進演算に必要であり、前記なぞられたバイナリノードの右ブランチがアクティブであり、左ブランチが非アクティブである場合に、前記なぞられたバイナリノードの右ブランチにぶらさがるノードへなぞられ、
それぞれの前記グループのために、前記アクティブな左右ブランチを有する前記なぞられたバイナリノードのための演算子命令、およびなぞられたリーフノードのためのリーフ値命令を生成する手段とを備える。
【００１６】
また本発明の第２の態様によれば、次の装置が提供される。すなわち、表現ツリーから、複数の走査線と各走査線に複数の画素位置を有するラスタ画素イメージを描画する装置であって、前記表現ツリーは１つ以上のバイナリノードと複数のリーフノードとを備える複数のノードを有し、ここで前記バイナリノードの各々は下方ノードを有する左ブランチと下方ノードを有する右ブランチを有するとともに２つの前記下方ノードに対する２進演算を表わし、また前記リーフノードの各々は１つ以上のグラフィックオブジェクトが重なったグラフィックオブジェクトを表し、重なっているグラフィックオブジェクトの各々は左ノード領域、共通領域、および右ノード領域を含み、
前記表現ツリーを表すテーブルを生成する手段と、ここで前記テーブルは関連するバイナリノードとリーフノードに対応する複数のレコードを含み、そして、前記関連するバイナリノードのそれぞれの前記レコードは、前記左ノード領域が前記関連するバイナリノードに関連する演算子の動作に必要であるかどうかを示す第１フィールドと、右ノード領域が前記関連するバイナリノードに関連する演算子の動作に必要であるかどうかを示す第２フィールドと、前記関連するバイナリノードの左ブランチがアクティブであるかどうかを示す第３フィールドと、前記関連するバイナリノードの右ブランチがアクティブかどうかを示す第４フィールドとを備え、
１つ以上の画素位置のグループを決定する手段と、
前記グループの各々に関して、前記１つ以上のバイナリノードの左右のブランチが、現在スキャンされている画素がブランチに対応するグラフィックオブジェクトに適用される境界エッジの中にあるならばアクティブであると判断し、現在スキャンされている画素がブランチに対応するグラフィックオブジェクトに適用される境界エッジの外にあるならば非アクティブであると判断する手段と、
前記グループの各々に関して、前記判断されたアクティブ及び非アクティブのブランチのために、前記テーブルの前記第３及び第４フィールドを更新する手段と、
それぞれの前記グループに関して、前記更新されたテーブルに従って、前記表現ツリーをなぞる手段と、ここで、なぞられたバイナリノードの左右ブランチがアクティブであるか、または、前記左ノード領域がなぞられたバイナリノードの２進演算に必要であり、該なぞられたバイナリノードの左ブランチがアクティブであり、かつ右ブランチが非アクティブである場合に、前記なぞられたバイナリノードの左ブランチがその下方ノードへとなぞられ、また、前記なぞられたバイナリノードの左右ブランチがアクティブであるか、または前記右ノード領域がなぞられたバイナリノードの２進演算に必要であり、該なぞられたバイナリノードの右ブランチがアクティブであり、左ブランチが非アクティブである場合に、なぞられたバイナリノードの右ブランチがその下方ノードへとなぞられ、
前記グループの各々に関して、前記右及び左ブランチがアクティブであるなぞられたバイナリノードに対して演算命令を生成し、なぞられたリーフノードに対してリーフ値命令を生成する手段と、
前記グループの各々に関して、前記イメージを描画するために、前記生成された対応する命令を実行する手段とを備える。
【００２０】
発明の実施の形態
添付の１つ又は複数の図面において同一の参照番号が付されたステップ及び／或いは機能は、特に断りのない限り、同じ機能或いは動作を記述するものである。
【００２１】
図１は、コンピュータグラフィックオブジェクト画像のレンダリングおよびプレゼンテーションのために構成されたコンピュータシステム１を概略的に示す図である。このシステムには、システムランダムアクセスメモリ（ＲＡＭ）３に関連するホストプロセッサ２が含まれ、システムＲＡＭ３には、不揮発性のハードディスクドライブ５または類似の装置と、揮発性の半導体ＲＡＭ４を含めることができる。システム１には、システム読取専用メモリ（ＲＯＭ）６も含まれ、システムＲＯＭ６は、通常は半導体ＲＯＭ７をベースとし、多くの場合、コンパクトディスク装置（ＣＤ−ＲＯＭ）８によって補足することができる。システム１には、ラスタ式に動作するビデオ表示装置（ＶＤＵ）またはプリンタなどの、画像を表示するための手段１０も組み込むことができる。
【００２２】
システム１に関して上で説明した構成要素は、バスシステム９を介して相互接続され、IBM PC/ATタイプのパーソナルコンピュータおよびそれから発展した構成、Sun Sparcstationsおよびその類似装置など、当技術分野で周知のコンピュータシステムの通常動作モードにて動作可能である。
【００２３】
また、図１に図示されているように、画素シーケンシャルレンダリング装置２０がバス９に接続される。画素シーケンシャルレンダリング装置２０は、好ましい実施形態において、システム１からバス９を介して命令およびデータを供給され、グラフィックオブジェクトベースの記述から導出される画素ベースの画像のシーケンシャルレンダリングを実行する。レンダリング装置２０は、オブジェクト記述のレンダリングのためにシステムＲＡＭ３を使用することができるが、レンダリング装置２０は、通常は半導体ＲＡＭから形成される、専用のレンダリング格納部３０に関連付けられることが好ましい。
【００２４】
本発明の大綱は、有向隣接図表に対する命令を生成すること、具体的には表現ツリーを生成する際のアプリケーションを有する。これは、好適な実施形態においては、画素シーケンシャルレンダリング装置２０のアクティビティ判断及び命令生成モジュール５００（図５）において実現される。このモジュールは、本明細書のセクション「３．０  アクティビティ判断及び命令生成モジュール」において詳細に説明される。
【００２５】
次に図２を参照すると、好ましい実施形態の全体的な機能のデータ流れ図が示されている。図２の機能流れ図は、オブジェクトグラフィック記述１１から始まる。このオブジェクトグラフィック記述１１は、ホストプロセッサ２によって作り出されるグラフィックオブジェクトに適切な様式で、且つ/又は、システムＲＡＭ３内に記憶されたりシステムＲＯＭ６から導出されるグラフィックオブジェクトに適切な様式でそれらのパラメータを記述するのに使用される。そして、このグラフィックオブジェクト記述は、画素ベースの画像をレンダリングするために、画素シーケンシャルレンダリング装置２０によって解釈され得る。たとえば、オブジェクトグラフィック記述１１は、ディスプレイ上の１点から別の点までをなぞる直線のエッジ（単純ベクトル）または、直交する線を含む複数のエッジによって二次元オブジェクトが定義される直交エッジフォーマットを含むいくつかのフォーマットによって、エッジを有するオブジェクトを組み込むことができる。これ以外に、連続曲線によってオブジェクトが定義されるフォーマットも適当であり、これらには、乗算を実行する必要なしに二次曲線を単一の出力空間内でレンダリングできるようにする複数のパラメータによって単一の曲線を記述できる二次多項式の線分を含めることができる。それ以外の、三次スプラインやその類似物などのデータフォーマットを使用することもできる。オブジェクトには、多数の異なるエッジタイプの混合物を含めることができる。通常、すべてのフォーマットに共通するのは、それぞれの線（直線であれ曲線であれ）の始点と終点との識別子であり、通常は、これらは、スキャンライン番号によって識別され、したがって、その曲線をレンダリングすることのできる特定の出力空間が定義される。
【００２６】
たとえば、図１４Ａに、線分を適当に記述し、レンダリングするために、２つの線分６０１および６０２に分割する必要があるエッジ６００に対する従来のエッジ記述を示す。分割の必要が生じるのは、従来のエッジ記述が、二次式を介して簡単に計算されるが、変曲点６０４に適応することができないからである。したがって、エッジ６００は、終点６０３および６０４または終点６０４および６０５を有する２つの別々のエッジとして扱われた。図１４Ｂに、終点６１１および６１２と制御点６１３および６１４によって記述される三次スプライン６１０を示す。このフォーマットでは、レンダリングのために三次多項式の計算が必要であり、したがって、計算時間がかかる。
【００２７】
図１４Ｃ及び図１４Ｄに、好ましい実施形態に適用可能なエッジの例を示す。
好ましい実施形態では、エッジは、単一の実体とみなされ、必要であれば、異なるフォーマットで記述できるエッジの部分を示すために区分されるが、その具体的な目的は、各部分の記述の複雑さが最小限になるようにすることである。
【００２８】
図１４Ｃの左側には、スキャンラインＡ〜Ｍの間にまたがる単一のエッジ６２０が示されている。エッジは、start_x、start_y、エッジの次の線分を指すアドレスを含む１つまたは複数の線分記述、および、エッジの終了に使用される最終線分を含む複数のパラメータによって記述される。好ましい実施形態によれば、エッジ６２０は、３つのステップ線分、１つのベクトル線分および１つの二次線分として記述することができる。ステップ線分は、単純に、ｘステップ値とｙステップ値を有するものとして定義される。図示の３つのステップ線分の場合、線分記述は［０，２］、［＋２，２］および［＋２，０］である。なお、ｘステップ値は符号付きであり、これによってステップの向きが示されるが、ｙステップ値は、必ず、スキャンラインの値が増えるラスタスキャン方向であるから符号なしである。次の線分はベクトル線分であり、通常はパラメータstart_x、start_y、finish_yおよび傾斜（DX）を必要とする。この例では、ベクトル線分がエッジ６２０の中間線分であるから、start_xおよびstart_yは、前の線分から生じるので、省略することができる。傾斜値（DX）は、符号付きであり、前のスキャンラインのｘ値に加算されて、現行スキャンラインのｘ値を与える。図示の例では、DX＝＋１である。次の線分は、二次線分であり、これは、ベクトル線分に対応する構造を有するが、さらに、やはり符号付きであり、線分の傾斜を変更するためにDXに加算される２階値（DDX）も有する。
【００２９】
図１４Ｄの右側の線分は、好ましい実施形態による三次曲線の例を示す図であり、これには上記の二次線分に対応する記述が含まれるが、線分の傾斜の変化の割合を変更するためにDDXに加算される符号付きの３階値（DDDX）が追加されている。他の多数階についても、同様にして実施することができる。
【００３０】
上記から、エッジの線分を記述する複数のデータフォーマットを処理する能力があると、複雑で計算コストの高い数学演算に頼らずに、エッジの記述と評価を単純化することができることが明白である。これに対して、図１４Ａの従来技術のシステムでは、直交、ベクトルまたは二次のいずれであれ、すべてのエッジを二次形式で記述する必要があった。
【００３１】
好ましい実施形態の動作を、図８に示された画像７８のレンダリングという単純な例に関して説明する。画像７８は、２つのグラフィカルオブジェクト、具体的に言うと、不透明の赤色の長方形９０とその上にレンダリングされ、これによって長方形９０を部分的に隠す、部分的に透明の青色の三角形８０を含む。図からわかるように、長方形９０には、種々の画素位置（Ｘ）とスキャンライン位置（Ｙ）の間で定義された辺（エッジ）９２、９４、９６および９８が含まれる。エッジ９６および９８は、スキャンライン上に形成される（したがってこれらと平行である）ので、長方形９０の実際のオブジェクト記述は、図９Ａに示されているように、エッジ９２および９４だけに基づくものとすることができる。図９Ａにおいて、エッジ９２は、画素位置（４０，３５）から始まり、ラスタ方向で画面の下側へ延びて、画素位置（４０，１０５）で終わる。同様に、エッジ９４は、画素位置（１６０，３５）から位置（１６０，１０５）まで延びる。長方形グラフィックオブジェクト９０の水平部分は、単にエッジ９２からエッジ９４へラスタ化された形で走査することによって得ることができる。
【００３２】
しかし、青い三角形のオブジェクト８０は、３つのオブジェクトエッジ８２、８４および８６によって定義され、各エッジは、三角形の頂点を定義するベクトルとみなされる。エッジ８２および８４は、画素位置（１００，２０）から始まり、それぞれ画素位置（１７０，９０）または（３０，９０）まで延びる。エッジ８６は、これら２つの画素位置の間で、従来のラスタ化された左から右への方向に延びる。この特定の例では、エッジ８６が、上で述べたエッジ９６および９８と同様に水平なので、エッジ８６が定義されることは必須ではない。というのは、エッジ８６が、エッジ８２および８４の終点をもつという特徴があるからである。エッジ８２および８４の記述に使用される始点および終点の画素位置のほかに、これらのエッジのそれぞれに、この場合ではそれぞれ＋１または−１の傾斜値が関連付けられる。
【００３３】
図１０に、スキャンライン３５で始まる長方形９０がレンダリングされる様子と、エッジ８２および８４がスキャンライン３５とどのように交差するかを示す。図１０から、画像７８のラスタ化には、高い優先順位レベルを有するオブジェクトが、低い優先順位レベルを有するオブジェクトの「上」にレンダリングされる形で２つのオブジェクト９０および８０が描画される必要のあることがわかる。これを図１１に示す。図１１は、画像７８のレンダリングに使用されるエッジリストレコードを示す図である。図１１のレコードには、オブジェクトごとに１つずつの、２つの項目が含まれる。これらの項目は、それぞれのオブジェクトのラスタレンダリング順での始点に対応するスキャンライン値で配置される。図１１から、エッジレコードのそれぞれが、オブジェクトに対応する優先順位レベルと、記述されるエッジの性質に関する詳細（たとえば色、傾斜など）を有することがわかる。
【００３４】
再び図２に戻って説明する。レンダリングされるグラフィックオブジェクトの記述に必要なデータを識別したので、グラフィックシステム１は、表示リスト生成ステップ１２を実行する。
【００３５】
表示リスト生成１２は、ＲＯＭ６およびＲＡＭ３を有するホストプロセッサ２上で実行されるソフトウェアモジュールとして実施されることが好ましい。表示リスト生成１２では、周知のグラフィック記述言語、グラフィックライブラリ呼出しまたは他のアプリケーション固有フォーマットのうちの１つまたは複数で表現されたオブジェクトグラフィック記述を表示リストに変換する。表示リストは、通常は、表示リスト格納部１３に書き込まれる。表示リスト格納部１３は、一般にＲＡＭ４内で形成されるが、レンダリング格納部３０内に形成するようにしてもよい。図３からわかるように、表示リスト格納部１３には、複数の構成要素を含めることができ、その１つは命令ストリーム１４であり、もう１つはエッジ情報１５であり、ラスタ画像画素データ１６を含めることができる。
【００３６】
命令ストリーム１４には、特定の画像内で所望される特定のグラフィックオブジェクトをレンダリングするために画素シーケンシャルレンダリング装置２０によって読み取られる、命令として解釈可能なコードが含まれる。図８に示された画像の例では、命令ストリーム１４が、下記の形になり得る。
【００３７】
（１）スキャンライン２０までレンダリング（何もしない）、
（２）スキャンライン２０で２つの青いエッジ８２および８４を追加、
（３）スキャンライン３５までレンダリング、
（４）スキャンライン３５で２つの赤いエッジ９２および９４を追加、
（５）最後までレンダリング。
【００３８】
同様に、図８の例によれば、エッジ情報１５には、下記が含まれることになる。すなわち、
・エッジ８４は画素位置１００から始まり、エッジ８２は画素位置１００から始まる；
・エッジ９２は画素位置４０から始まり、エッジ９４は画素位置１６０から始まる；
・エッジ８４は７０スキャンライン延び、エッジ８２は７０スキャンライン延びる；
・エッジ８４は傾斜＝−１を有し、エッジ８４は傾斜＝＋１を有する；
・エッジ９２は傾斜＝０を有し、エッジ９４は傾斜＝０を有する；
・エッジ９２および９４は７０スキャンラインだけ延びる。
【００３９】
上の命令ストリーム１４およびエッジ情報１５の例とそれぞれが表現される形から、図８の画像７８では、画素位置（Ｘ）とスキャンライン値（Ｙ）によって、画像７８がレンダリングされる単一の出力空間が定義されることが認められる。しかし、本開示の原理を使用して、他の出力空間構成を実現することもできる。
【００４０】
図８には、ラスタ画像画素データが含まれず、したがって、表示リスト１３の記憶部分１６には何も記憶する必要がない。この特徴については後述する。
【００４１】
表示リスト格納部１３は、画素シーケンシャルレンダリング装置２０によって読み取られる。画素シーケンシャルレンダリング装置２０は、通常は集積回路を用いて実施される。画素シーケンシャルレンダリング装置２０は、表示リストをラスタ画素のストリームに変換し、このストリームは、たとえばプリンタ、ディスプレイまたはメモリ格納装置などの別の装置に転送され得る。
【００４２】
なお、好ましい実施形態においては、画素シーケンシャルレンダリング装置２０を集積回路として説明するが、これは、ホストプロセッサ２などの汎用処理ユニット上で同等の処理を実行可能なソフトウェアモジュールによって実施することもできる。このソフトウェアモジュールは、ディスク装置またはコンピュータネットワークなどのコンピュータ可読媒体を介してユーザに配布することのできるコンピュータプログラム製品の一部を形成することができる。
【００４３】
図３は、画素シーケンシャルレンダリング装置２０、表示リスト格納部１３および一時的なレンダリング格納部３０の構成を示す図である。画素シーケンシャルレンダリング装置２０の処理ステージ２２は、
命令実行部３００（本明細書の「１．０  命令実行部」においてより詳細に説明する）、
エッジ処理モジュール４００（本明細書の「２．０  エッジ処理モジュール」においてより詳細に説明する）、
アクティビティ判断及び命令生成モジュール５００（本明細書の「３．０  アクティビティ判断及び命令生成モジュール」においてより詳細に説明する）、
塗潰し色決定モジュール６００（本明細書の「４．０  塗潰し色決定モジュール」においてより詳細に説明する）、
画素合成モジュール７００（本明細書の「５．０  画素合成モジュール」においてより詳細に説明する）、及び
画素出力モジュール８００（本明細書の「６．０  画素出力モジュール」においてより詳細に説明する）を含む。
【００４４】
また、本処理動作では一時的格納部３０を使用するが、これは、上で述べたように表示リスト格納部１３と同一の装置（たとえば磁気ディスクまたは半導体ＲＡＭ）を共用してもよいし、速度最適化のために個々に格納部（ストア）を用いて実施することができる。エッジ処理モジュール４００は、エッジレコード格納部３２を使用して、スキャンラインからスキャンラインへ順方向に運ばれるエッジ情報を保持する。アクティビティ判断及び命令生成モジュール５００は、レベルアクティベーションテーブル３４を使用して演算子性能に関する情報と、スキャンラインがレンダリングされている間のエッジ交差に関する各領域のその時点におけるアクティビティの状態に関する情報とを保持する。塗潰し色決定モジュール６００は、塗潰しデータテーブル３６を使用して、特定の位置で特定の優先順位の塗潰し色を決定するのに必要な情報を保持する。画素合成モジュール７００は、画素合成スタック３８を使用して、値を決定するために多数の優先順位からの色を要求する出力画素を決定する間、中間結果を保持する。
【００４５】
表示リスト格納部１３および上記で詳細を示した他の格納部３２乃至３８は、ＲＡＭ内で実現するか、他のデータ記憶技術によって実現することができる。
【００４６】
図３の実施形態に示された処理ステップは、処理パイプライン２２の形をとる。この場合、パイプラインのモジュールは、以下で説明する形態でそれらの間でメッセージを受け渡しながら、画像データの異なる部分に対して並列に同時に実行することができる。もう１つの実施形態では、以下で説明するメッセージのそれぞれが、下流モジュール制御への同期転送の形をとることができ、上流処理は、下流モジュールがそのメッセージの処理を完了するまで中断される。
【００４７】
１．０  命令実行部
命令実行部３００は、命令ストリーム１４から命令を読み取り、処理し、その命令を、出力３９８を介してパイプライン２２内の他のモジュール４００、５００、６００および７００に転送されるメッセージにフォーマットする。好ましい実施形態では、命令ストリーム１４に、以下の命令を含めることができる。
【００４８】
LOAD_PRIORITY_PROPERTIES：この命令は、レベルアクティベーションテーブル３４にロードされるデータと、そのデータがロードされるテーブル内のアドレスに関連する。命令実行部３００は、この命令を検出したとき、レベルアクティベーションテーブル３４の指定された位置にデータを格納するためのメッセージを発行する。これは、このデータを含むメッセージをフォーマットし、処理パイプライン２２を介して、格納動作を実行するアクティビティ判断及び命令生成モジュール５００に渡すことによって達成できる。
【００４９】
LOAD_FILL_DATA：この命令は、塗潰しデータテーブル３６にロードされるデータと、そのデータがロードされるテーブル内のアドレスに関連する。命令実行部３００は、この命令を検出したとき、塗潰しデータテーブル３６の指定されたアドレスのデータを格納するためのメッセージを発行する。これは、このデータを含むメッセージをフォーマットし、処理パイプライン２２を介して、格納動作を実行する塗潰しデータ決定モジュールに渡すことによって達成できる。
【００５０】
LOAD_NEW_EDGES_AND_RENDER：この命令は、次のスキャンラインをレンダリングする時にレンダリング処理に導入される新しいエッジ１５の表示リスト格納部１３内におけるアドレスに関連する。命令実行部３００は、この命令を検出すると、このデータを含むメッセージをフォーマットし、エッジ処理モジュール４００に渡す。エッジ処理モジュール４００は、新しいエッジのアドレスをエッジレコード格納部３２に格納する。指定されたアドレスにあるエッジは、次のスキャンラインをレンダリングする前に、最初のスキャンライン交差座標に基づいてソートされる。一つの実施形態では、エッジは、表示リスト生成処理１２によってソートされる。また、別の実施形態では、エッジは、画素シーケンシャルレンダリング装置２０によってソートされる。
【００５１】
SET_SCAN LINE_LENGTH：この命令は、レンダリングされるスキャンラインのそれぞれで作られる画素数に関連する。命令実行部３００は、この命令を検出すると、この値をエッジ処理モジュール４００および画素合成モジュール７００に渡す。
【００５２】
SET_OPACITY_MODE：この命令は、画素合成演算で不透明度チャネル（当技術分野ではアルファチャネルとも称する）を使用するかどうかを示すフラグに関連する。命令実行部３００は、この命令を検出すると、このフラグの値を画素合成モジュール７００に渡す。
【００５３】
命令実行部３００は、通常は、命令をマッピングし、パイプライン動作に復号して、さまざまなモジュールに渡す、マイクロコードステートマシンによって形成されるが、その代わりに、対応するソフトウェア処理を使用することもできる。
【００５４】
２．０  エッジ処理モジュール
スキャンラインのレンダリング動作中のエッジ処理モジュール４００の動作を、図４を参照して以下に説明する。スキャンラインのレンダリングのための初期条件は、以下の３つのエッジレコードのリストが使用可能であることである。これら３つのリストのいずれかまたはすべては空でもよい。これらのリストは、エッジ情報１５から取得されLOAD_NEW_EDGES_AND_RENDER命令によってセットされる、新しいエッジを含む新エッジリスト４０２、前のスキャンラインから順方向に運ばれたエッジレコードを含む主エッジリスト４０４および、やはり前のスキャンラインから順方向に運ばれたエッジレコードを含むスピルエッジリスト４０６である。各エッジレコードには、下記が含まれ得る。
【００５５】
（ｉ）現時点のスキャンラインの交差の座標（本明細書ではＸ座標と称する）、
（ii）現時点のこのエッジの線分が続くスキャンラインの数（本明細書ではNYと称する。また、いくつかの実施形態では、これをＹ限界と表現する場合がある）、
（iii）各スキャンラインの後でこのエッジレコードのＸ座標に加算される値（本明細書ではDXと称する）、
（iv）各スキャンラインの後でこのエッジレコードのDXに加算される値（本明細書ではDDXと称する）、
（ｖ）１つまたは複数の優先順位番号（P）、
（vi）エッジがスキャンラインと上向き（＋）に交差するか下向き（−）に交差するかを示す方向フラグ（DIR）、
（vii）リスト内の次のエッジ線分のアドレス（ADD）。
【００５６】
このようなフォーマットは、ベクトル、直交配置されたエッジおよび二次曲線に適合する。これ以外のパラメータ、たとえばDDDXの追加によって、このような配置が三次曲線に適合できるようになる。三次ベジェスプラインなど、いくつかの応用分野では、６階多項式（すなわちDDDDDDXまで）が必要になる場合がある。
【００５７】
図８のエッジ８４および９４の例では、スキャンライン２０での対応するエッジレコードが、図１６において示されるテーブルのようになる。
【００５８】
この説明では、レンダリング処理によって生成されつつあるスキャンラインに沿って画素から画素へステップする座標を、Ｘ座標と称し、スキャンラインからスキャンラインへとステップする座標を、Ｙ座標と称する。各エッジリストには、メモリ内で連続的に配置された０個以上のレコードが含まれることが好ましい。ポインタチェインの使用を含む他の記憶配置も可能である。３つのリスト４０２、４０４および４０６のそれぞれのレコードは、スキャンライン交差（Ｘ）座標の順で配置される。これは、通常は、最初は、エッジ情報を含むメッセージを命令実行部３００から受け取るエッジ入力モジュール４０８によって管理されるソート処理によって得られる。各スキャンライン交差座標の整数部分だけを有意とみなすためにソートを簡易化することが可能である。また、各スキャンラインの交差座標を、現在のレンダリング処理によって作られる最小および最大のＸ座標にクランプされるとみなすことによってさらにソートを簡易化することが可能である。適切な場合には、エッジ入力モジュール４０８は、メッセージを、出力４９８を介してパイプライン２２の下流のモジュール５００、６００および７００に受け渡す。
【００５９】
エッジ入力モジュール４０８は、３つのリスト４０２、４０４および４０６のそれぞれへの参照を継続し、これらのリストからエッジデータを受け取る。これらの参照のそれぞれは、スキャンラインの処理の開始時に、各リスト内の最初のエッジを参照するように初期設定される。その後、エッジ入力モジュール４０８は、３つの参照されるレコードのうちの最小のＸ座標を有するレコードを選択するべく、３つの参照されたエッジレコードのうちの１つを選択する。複数のレコードのＸが等しい場合には、それぞれが任意の順序で処理され、対応するエッジ交差が、下記の形で出力される。そのレコードの選択に使用された参照は、その後、そのリストの次のレコードに進められる。選択されたばかりのエッジは、メッセージにフォーマットされ、エッジ更新モジュール４１０に送られる。また、エッジのいくつかのフラグ、具体的には現在のＸ、優先順位番号および方向フラグが、メッセージにフォーマットされ、このメッセージは、エッジ処理モジュール４００の出力４９８としてアクティビティ判断及び命令生成モジュール５００に転送される。なお、本明細書に記載されたものより多数または少数のリストを使用する実施形態も可能である。
【００６０】
エッジを受け取った時に、エッジ更新モジュール４１０は、現在の線分が続くスキャンライン数のカウントをデクリメントする。そのカウントが０に達した場合には、次の線分アドレスによって示されるアドレスから新しい線分を読み取る。線分では、下記が指定される。
（ｉ）線分を読み取った直後に現在のＸ座標に加算される値、
（ii）そのエッジの新しいDX値、
（iii）そのエッジの新しいDDX値、
（iv）新しい線分が続くスキャンライン数の新しいカウント。
【００６１】
示されたアドレスに使用可能な次の線分がない場合には、そのエッジに対してそれ以上の処理は実行されない。そうでない場合には、エッジ更新モジュール４１０は、そのエッジの次のスキャンラインにおけるＸ座標を計算する。これには、通常は、現在のＸ座標をとり、これにDX値を加算することが用いられる。DXは、処理されるエッジの種類に応じて、必要であればDDX値を加算される場合がある。その後、エッジは、複数のエッジレコードの配列であるエッジプール４１２内の使用可能な空きスロットに書き込まれる。空きスロットがない場合には、エッジ更新モジュール４１０は、スロットが使用可能になるのを待つ。エッジレコードがエッジプール４１２に書き込まれたならば、エッジ更新モジュール４１０は、新しいエッジがエッジプール４１２に追加されたことを、信号線４１６を介してエッジ出力モジュール４１４に知らせる。
【００６２】
スキャンラインのレンダリングのための初期条件として、エッジ出力モジュール４１４は、図４には図示されていないが、エッジレコード３２内のリスト４０４および４０６に関連する次の主エッジリスト４２０および次のスピルエッジリスト４２２のそれぞれへの参照を有する。これらの参照のそれぞれは、当初は空のリスト４２０および４２２が構築される位置に初期設定される。エッジ出力モジュール４１４は、エッジがエッジプール４１２に追加されたことを示す信号４１６を受け取ったとき、追加されたエッジが、次の主エッジリスト４２０に最後に書き込まれたエッジ（があれば）より小さいＸ座標を有するかどうかを判定する。これが真である場合には、順序付けの基準を侵害せずにそのエッジを主エッジリスト４０４の末尾に追加することができないので、「スピル」が発生したという。スピルが発生したときには、そのエッジは、好ましくはソートされた次のスピルエッジリスト４２２を維持する形で、次のスピルエッジリスト４２２に挿入される。たとえば、これは、ソフトウェアソートルーチンを使用して達成することができる。いくつかの実施形態では、スピルが、極端に大きいＸ座標など、他の条件によってトリガされる場合がある。
【００６３】
エッジプール４１２に追加されたエッジが、次の主エッジリスト４２０に最後に書き込まれたエッジ（があれば）以上のＸ座標を有し、エッジプール４１２に使用可能な空きスロットがない場合には、エッジ出力モジュール４１４は、エッジプール４１２から、最小のＸ座標を有するエッジを選択し、そのエッジを次の主エッジリスト４２０の末尾に追加し、この処理で次の主エッジリスト４２０を延長する。エッジプール４１２内の、そのエッジによって占められていたスロットは、空きとしてマークされる。
【００６４】
エッジ入力モジュール４０８は、これら３つの入力リスト４０２、４０４および４０６のすべてからすべてのエッジを読み取り、転送した後に、スキャンラインの終りに達したことを示すメッセージを形成し、そのメッセージを、アクティビティ判断及び命令生成モジュール５００とエッジ更新モジュール４１０の両方に送る。エッジ更新モジュール４１０は、そのメッセージを受け取ると、現在実行しているすべての処理が完了するのを待ち、その後、このメッセージをエッジ出力モジュール４１４に転送する。そのメッセージを受け取ったエッジ出力モジュール４１４は、エッジプール４１２からの残りのエッジレコードのすべてを、Ｘ順で次の主エッジリスト４０４に書き込む。その後、次の主エッジリスト４２０および主エッジリスト４０４への参照を、エッジ入力モジュール４０８とエッジ出力モジュール４１４の間で交換し、同様の交換を、次のスピルエッジリスト４２２とスピルエッジリスト４０６に関しても実行する。この形で、次のスキャンラインのための初期条件が確立される。
【００６５】
エッジレコードの挿入時に次スピルエッジリスト４２２をソートするのではなく、そのようなエッジレコードを、単にリスト４２２の末尾に追加することができ、スキャンラインの末尾であって現在のスピルリスト４０６との交換の前にソートされたリスト４２２は、次のスキャンラインのエッジラスタ化でアクティブになる。エッジをソートする他の方法において、より少数またはより多数のリストを使用することができ、また、異なるソートアルゴリズムを使用することができる。
【００６６】
上記から、エッジ交差メッセージが、スキャンライン順および画素順（すなわち、まずＹでソートされ、次にＸでソートされる）でアクティビティ判断及び命令生成モジュール５００に送られること、および各エッジ交差メッセージに、それに適用される優先順位のラベルが付けられることを推論できる。
【００６７】
図１２Ａは、エッジの線分が受け取られる時にエッジ処理モジュール４００によって作成され得るアクティブエッジレコード４１８の具体的な構造を示す図である。エッジの最初の線分がステップ（直交）線分である場合には、エッジのＸ値を、最初の線分の「Ｘステップ」と称する変数に加算して、アクティブ化されたエッジのＸ位置を得る。そうでない場合には、エッジのＸ値を使用する。これは、新しいエッジレコードのエッジが、Ｘedge＋Ｘstepによってソートされなければならないことを意味する。したがって、最初の線分のＸstepは、エッジのソートを単純化するために０でなければならない。最初の線分のＹ値は、アクティブエッジレコード４１８のＮＹフィールドにロードされる。アクティブなエッジのＤＸフィールドは、ベクトルまたは二次線分のＤＸフィールド識別子からコピーされ、ステップ線分の場合には０がセットされる。図１２Ａに示されたｕフラグは、線分が上向き（図１３Ａに関連する説明を参照されたい）である場合にセットされる。ｑフラグは、線分が二次線分の場合にセットされ、そうでない場合にはクリアされる。ｉフラグが設けられ、これは、線分が不可視である場合にセットされる。ｄフラグは、エッジが、関連するクリッピングレベルのない直接的なクリッピングオブジェクトして使用され、閉じた曲線に適用可能である時にセットされる。線分の実際の優先順位レベルまたはレベルアドレスは、新しいエッジレコードの対応するフィールドからアクティブエッジレコード４１８のレベル（ADDR）フィールド（Level(Addr)）にコピーされる。アクティブエッジレコード４１８の線分アドレス／ＤＤＸフィールド（Seg.Addr(DDX)）は、線分リスト内の次の線分のアドレスであるか、線分が二次線分の場合にセグメントのＤＤＸ値からコピーされるかのいずれかである。線分アドレスは、エッジレコードを終了させるのに使用される。その結果、好ましい実施形態では、全ての二次曲線（すなわち、ＤＤＸフィールドを使用する曲線）が、エッジレコードの終端線分になる。
【００６８】
図１２Ａから、他のデータ構造も可能であり、たとえばより高次の多項式の実装が使用される場合にはそれが必要であることを諒解されたい。さらに、線分アドレスおよびＤＤＸフィールドは、異なるフィールドに分離することができ、代替実施態様に合わせて追加のフラグを設けることができる。
【００６９】
図１２Ｂは、エッジ処理モジュール４００で使用される、上で説明した好ましい実施形態のエッジレコードの配置を示す図である。エッジプール４１２は、新アクティブエッジレコード４２８、現アクティブエッジレコード４３０およびスピルアクティブエッジレコード４３２によって補足される。図１２Ｂからわかるように、レコード４０２、４０４、４０６、４２０および４２２は、ある時点でレンダリングされるエッジの数に応じてそのサイズを動的に変更することができる。各レコードには、新エッジリスト４０２の場合にはLOAD_EDGES_AND_RENDER命令に組み込まれたSIZE値によって決定される、限界値が含まれる。このような命令が検出された場合には、SIZEを検査し、０でない場合には、新しいエッジレコードのアドレスをロードし、リスト４０２の限界サイズを決定する限界値を計算する。
【００７０】
好ましい実施形態では、エッジレコードの処理のために配列とそれに関連するポインタを使用するが、たとえばリンクリストなどの、他の実施態様を使用することができる。これらの他の実施態様は、ハードウェアベース、ソフトウェアベースまたはその組合せとすることができる。
【００７１】
図８に示された画像７８の具体的なレンダリングを、図１０に示されたスキャンライン３４、３５および３６に関連して以下に説明する。この例では、次のスキャンラインの新しいＸ座標の計算が、説明を明瞭にするために省略され、図１２Ｃないし図１２Ｉでは、出力エッジ交差が、エッジプール４１２のレジスタ４２８、４３０および４３２の１つから導出される。
【００７２】
図１２Ｃは、スキャンライン３４（半透明の青い三角形８０の最上部）のレンダリングの終りでの、上で述べたリストの状態を示す図である。スキャンライン３４には、新しいエッジがなく、したがって、リスト４０２が空であることに留意されたい。主エッジリスト４０４および次主エッジリスト４２０のそれぞれには、エッジ８２および８４だけが含まれる。リストのそれぞれには、対応するポインタ４３４、４３６および４４０が含まれ、これらは、スキャンライン３４の完了時に、対応するリスト内の次の空きレコードを指す。各リストには、対応するリストの末尾を指すために必要な、アスタリスク（＊）によって示される限界ポインタ４５０も含まれる。リンクリストを使用する場合には、リンクリストに、対応する機能を実行するヌルポインタ終端子が含まれるので、このような限界ポインタは不要になる。
【００７３】
上で述べたように、各スキャンラインの始めに、次の主エッジリスト４２０と主エッジリスト４０４が交換され、新しいエッジが、新エッジリスト４０２に受け取られる。残りのリストはクリアされ、ポインタのそれぞれは、各リストの最初のメンバを指すようにセットされる。スキャンライン３５の始めでは、配置は図１２Ｄのようになる。図１２Ｄからわかるように、レコードには、４つのアクティブなエッジが含まれ、図１０からわかるように、エッジ９２、９４、８４および８２に対応する。
【００７４】
図１２Ｅを参照すると、レンダリングが開始されるときに、新エッジレコード４０２の最初の線分が、アクティブエッジレコード４２８にロードされ、主エッジリスト４０４およびスピルエッジリスト４０６の最初のアクティブなエッジレコードが、それぞれレコード４３０および４３２にコピーされる。この例では、スピルエッジリスト４０６は空であり、したがって、ローディングは行われない。レコード４２８、４３０および４３２内のエッジのＸ位置が比較され、エッジ交差が、最小のＸ位置を有するエッジについて発行される。この場合、発行されるエッジは、エッジ９２に対応するエッジであり、このエッジがその優先順位値と共に出力される。その後、ポインタ４３４、４３６および４３８が、リスト内の次のレコードを指すように更新される。
【００７５】
その後、エッジ交差が発行されるエッジが更新され（この場合、その位置にDX＝０を加算することによって）、エッジプール４１２にバッファリングされる。このエッジプール４１２は、この例では３つのエッジレコードを保持するサイズになる。発行されたエッジが現れたリスト（この場合ではリスト４０２）内の次の項目が、対応するレコード（この場合ではレコード４２８）にロードされる。
これを図１２Ｆに示す。
【００７６】
さらに、図１２Ｆから明らかなとおり、レジスタ４２８、４３０および４３２の間の比較によって、もう一度最小のＸ値を有するエッジが選択され、適切な次のエッジ交差（Ｘ＝８５、Ｐ＝２）として出力される。そして、同様に、選択され出力されたエッジは、更新され、エッジプール４１２に追加され、適当なポインタのすべてがインクリメントされる。この場合、更新される値は、Ｘ←Ｘ＋DXによって与えられ、ここでは、８４＝８５−１として与えられる。また、図からわかるように、新しいエッジのポインタ４３４が、この場合では新エッジリスト４０２の末尾に移動される。
【００７７】
図１２Ｇでは、現在の最小のＸ値を有すると識別された次のエッジが、やはり、レジスタ４３０から取得され、エッジ交差（Ｘ＝１１５、Ｐ＝２）として出力される。そして、エッジの更新が発生し、図示のように、その値がエッジプール４１２に追加される。この時、エッジプール４１２は満杯になり、ここから、最小のＸ値を有するエッジが選択され、出力リスト４２０に発行され、対応する限界ポインタが、それに相応して移動される。
【００７８】
図１２Ｈからわかるように、次の最小のエッジ交差は、レジスタ４２８からのものであり、これが出力される（Ｘ＝１６０、Ｐ＝１）。やはりエッジプール４１２が更新され、次に小さいＸ値が出力リスト４２０に発行される。
【００７９】
スキャンライン３５の終りに、図１２Ｉからわかるように、Ｘ値の小さい順で、エッジプール４１２の内容が出力リスト４２０にフラッシュされる。図１２Ｊからわかるように、次の主エッジリスト４２０と主エッジリスト４０４は、次のスキャンライン３６のレンダリングに備えて、ポインタを交換することによって交換される。交換の後に、図１２Ｊからわかるように、主エッジリスト４０４の内容には、スキャンライン３６上の現在のエッジのすべてが含まれ、これらはＸ位置の順で配置され、これによって、高速のレンダリングを容易にする便利なアクセスが可能になる。
【００８０】
通常、新しいエッジは、Ｘ位置の昇順でエッジ処理モジュール４００によって受け取られる。新しいエッジが現れる時には、その位置が更新され（次にレンダリングされるスキャンラインのために計算され）、これによって、以下の処置が決定される。
（ａ）更新された位置が信号線４９８に出力された最後のＸ位置より小さい場合には、新しいエッジは、主スピルリスト４０６へのソートされる挿入であり、対応する限界レジスタが更新される。
（ｂ）そうでない場合に、空間があるならば、そのエッジはエッジプール４１２内で保存される。
【００８１】
前述から明白なとおり、エッジプール４１２は、ラスタ化画像の次のスキャンラインのレンダリングに備えた順序付きの形でのリストの更新を補助する。さらに、エッジプール４１２のサイズは、多数の順序付けられていないエッジに適合するために変更することができる。しかし、実際には、エッジプール４１２が、一般にグラフィック処理システムの処理速度および使用可能なメモリに依存する、実用的な限界を有することは明白である。制限的な意味では、エッジプール４１２を省略することができるが、これは、通常は、更新されたエッジを、次の出力エッジリスト４２０へのソートされた挿入にすることを必要とする。しかし、好ましい実施形態では、上で述べたスピルリストの使用を介することにより、必然的にこの状況が回避される。スピルリストを設けることによって、好ましい実施形態を、実用的なサイズのエッジプールを用いて実施でき、なおかつ、ソフトウェア集中的なソート手順に頼らずに比較的複雑なエッジ交差を処理することができる。稀ではあるが、エッジプールとスピルリストがエッジ交差の複雑さに適合するのに不十分になった場合では、ソート法を使用するようにしてもよい。
【００８２】
スピルリスト手順が使用される場合の例を、図１３Ａに示す。図１３Ａでは、３つの任意のエッジ６０、６１および６３が、スキャンラインＡおよびＢの間の相対的位置で任意のエッジ６２と交差する。さらに、スキャンラインＡおよびＢのそれぞれについて実際に表示される画素位置６４が、スパン画素位置Ｃ乃至Ｊとして図示されている。エッジプール４１２が３つのエッジレコードを保存するサイズであるとした上記の例では、このような配置だけでは、図１３Ａに示された隣接するスキャンラインの間で発生する３つのエッジの交差に適合するのに不十分であることは明白である。
【００８３】
図１３Ｂに、スキャンライン上のエッジ６０、６１および６３をレンダリングした後のエッジレコードの状態を示す。エッジ交差Ｈは、最も最近に発行されたエッジ交差であり、エッジプール４１２は、次のスキャンラインであるスキャンラインＢのための、それぞれエッジ６０、６１および６３の更新されたＸ値Ｅ、ＧおよびＩで満杯になっている。エッジ６２は、現アクティブエッジレコード４３０にロードされ、エッジプール４１２が満杯なので、エッジ６０に対応する最小のＸ値が、出力エッジリスト４２０に出力される。
【００８４】
図１３Ｃでは、次のエッジ交差が発行され（エッジ６２、Ｘ＝Ｊ）、対応する更新された値、この場合はスキャンラインＢのＸ＝Ｃが決定される。新たに更新された値Ｘ＝Ｃは、出力リスト４２０からコピーされた最も最近の値Ｘ＝Ｅより小さいので、現在のエッジレコードとそれに対応する新たに更新された値が、出力スピルリスト４２２に直接に転送される。
【００８５】
図１３Ｄに、スキャンラインＢの開始時のエッジレコードの状態を示す。この図では、主リストおよび出力リストと、それらに対応するスピル構成要素が交換されていることがわかる。最初に発行されるエッジを決定するために、エッジ６０を現アクティブエッジレジスタ４３０にロードし、エッジ６２を、スピルアクティブエッジレジスタ４３２にロードする。Ｘ値が比較され、最小のＸ値（Ｘ＝Ｃ）を有するエッジ６２が発行され、更新され、エッジプール４１２にロードされる。
【００８６】
エッジの発行と更新は、主エッジリスト４０４内の残りのエッジについて継続され、スキャンラインの終りに、エッジプール４１２がフラッシュされて、図１３Ｅに示された状況になる。図１３Ｅからは、エッジ６０ないし６３のそれぞれが、次のスキャンラインでのレンダリングのために適当に順序付けられ、スキャンラインＢ上で正しく発行され、レンダリングされたことがわかる。
【００８７】
上記から明らかになるように、スピルリストは、複雑なエッジ交差状況の存在のもとで、エッジラスタ化順序の維持をもたらす。さらに、このリストがサイズにおいて動的に変更可能であることによって、エッジ交差の数と複雑さの大きい変化を、例外的に複雑なエッジ交差以外のすべてのエッジ交差でソート手順に頼る必要なしに処理できる。
【００８８】
好ましい実施形態では、エッジプール４１２は、８つのエッジレコードを保存するサイズにされ、リスト４０４および４２０のサイズは、それらに関連するスピルリスト４０６および４２２と一緒に、動的に変更可能であり、これによって、複雑なエッジ交差要件を有する大きい画像を処理するために十分な範囲が提供される。
【００８９】
３．０  アクティビティ判断及び命令生成モジュール
表現ツリーはイメージを形成するのに必要となる合成演算を記述するのにしばしば使用され、通常は、リーフノード、単項ノードおよびバイナリノードを含む多くのノードを備える。リーフノードは表現ツリーの一番はずれのノードであり、これに続く下位のノードを持たず、イメージのプリミティブな構成要素、すなわちグラフィックオブジェクトを表す。単項ノードは、単項演算子の下位のツリーの部分より生じるオブジェクトの画素データを変更する操作を表す。通常、バイナリのノードは左右のサブツリーに分岐する。ここで、サブツリーはそれぞれ少なくとも１つのリーフノードを備える。バイナリのノードは１つのブランチ上の１つのオブジェクトと、他のブランチ上の他のオブジェクトとの間の演算を表す。
【００９０】
そのような演算に関する例は「ディジタルイメージの合成（Compositing Digital Images）」（Porter、T及びDuff、T、コンピュータグラフィックス、Vol.18No.3(1984)、253-259ページ）において記述されている。これらのPorterとDuffの合成演算のいくつかを図１５に示す。図示を容易にするために、図１５で示されるグラフィックオブジェクトは完全に不透明であるとする。図からわかるように、これらの演算子のいくつか（例えば、out）はデータ（例えば、色データ）を、２個のオブジェクトの中央のオーバラッピング領域に提供しない。一般に、２個のオブジェクトの１つもしくは両方が部分的に透明であるならば、これらの演算子（例えば、out）は常にデータ（例えば、色データ）をそれら２個のオブジェクトの中央オーバラッピング領域に提供することになる。しかしながら、２個のオブジェクトの１つもしくは両方が完全に不透明であるならば、特定の演算子がいかなるデータをもこれら２個のオブジェクトの中央オーバラッピング領域に提供しないという特別な場合が生じることになる。
【００９１】
次に、図１９をみると、単純な表現ツリーとこれに対応する命令リストの典型的な例が示されている。表現ツリーは、それぞれグラフィックオブジェクトＡ、Ｂ、Ｃ、ＤおよびPAGEを記述するリーフノード１０、９、７、６及び０−５を備える。また、表現ツリーは、２つのブランチを有し、それぞれ演算、“out”、“in”、“over”および“over”を表わすノード８、１１、１２、および１３を含む。命令リストは表現ツリーを描画するための命令のリストを含んでいる。しかしながら、合成演算が、その演算によって合成されるグラフィックオブジェクトのどれが与えられた画素位置で有効であるかということに影響されるので、与えられた画素位置に対して命令リストを生成するときには問題が生じる。好適なアクティビティ判断及び命令生成モジュール５００は、これらの問題を解決しようとするものである。
【００９２】
次に、アクティビティ判断及び命令生成モジュール５００の動作について図５を参照して説明する。初期化処理段階の間、命令生成部３００は、レンダリングされるイメージのオブジェクト図形記述をレベルアクティベーションテーブル生成部５０２に渡す。このオブジェクト図形記述は、例えば図１９で示される表現ツリーのような、表現ツリーの形態をとる。次に、レベルアクティベーションテーブル生成部５０２は、レベルアクティベーションテーブルを生成する。このテーブルは、表現ツリーの１次形式であり、レベルアクティベーションテーブル格納部３４に格納される。生成されたレベルアクティベーションテーブルは複数のレコードを含んでおり、表現ツリーの２項演算子ノード、単項ノード、及びリーフノードの各々に対して一つのノードが割り当てられている。
【００９３】
さらに、また、レベルアクティベーションテーブルは２項演算子のある特有な性質に関するデータ格納のためのフィールドと、２項演算子ノードのブランチのアクティビティに関するデータ格納のためのフィールドとを含んでいる。２項演算子の性質に関するデータは静的である。すなわち、現在スキャンされた画素の位置に依存するのではなく、使用される実際の演算子に依存する。その結果、初期化処理段階の間に、このデータは生成され、レベルアクティベーションテーブルの中に格納されることができる。しかしながら、ブランチのアクティビティに関するデータは、現在スキャンされている画素位置に依存する。初期化処理段階の間は、その時点で有効な画素位置はないので、レベルアクティベーションテーブルのブランチアクティビティデータは無効な状態に初期化される。
【００９４】
そして、画素順次描画装置２０は、ラスタスキャン順次で、イメージの画素位置をスキャンし始める。エッジ処理モジュール４００はレベルアクティベーションテーブル更新モジュール５０４に、スキャンされている現在のスキャンラインのエッジの画素位置を渡す。レベルアクティベーションテーブル更新モジュール５０４は格納部３４からレベルアクティベーションテーブルにアクセスして、どの画素位置が現在スキャンされているのかに依存してテーブルを更新する。実現の容易化のために、テーブルは隣接しているエッジの間のそれらの画素位置に対して一度だけアップデートされる。これは、スキャンラインの２つの隣接するエッジの間の画素位置の１つのグループ内では、表現ツリーをレンダリングするための命令リストは同一であるということの認識に基づいている。或いは、それぞれのスキャンされた画素位置に対してテーブルはアップデートされる構成とすることもできる。
【００９５】
トラバーサル及び命令生成モジュール５０６は、次に、この更新されたレベルアクティベーションテーブルに基づいて命令を生成する。その命令は、次に、塗潰し色決定モジュール６００に渡される。イメージが描画されるまで、隣接しているエッジの間の画素位置の各グループに対して、このプロセスは持続される。
【００９６】
本実施形態の更なる説明に先立って、本明細書において使用される用語について簡単に説明する。
【００９７】
図１８Ａと１８Ｂをみると、ソースオブジェクトＬと目的オブジェクトＲの間の２進演算（表現ツリーとして表されている）が示される。表現ツリーには、オブジェクトＬへの左のブランチとオブジェクトＲへの右のブランチを有するバイナリノードＯＰが示される。オブジェクトに適用される境界エッジの中に現在スキャンされている画素があるならば、オブジェクトはその画素にアクティブであるとみなされる。境界エッジの外に画素があるならば、オブジェクトはその画素に非アクティブである。こうして、境界エッジの中のそれらの画素のグループを走査する間、そのオブジェクトはアクティブになる。オブジェクトがアクティブである場合、オブジェクトへの演算子のブランチはアクティブであるとみなされる。実際に実行される動作とは関係なく、図１８Ａの２進演算は以下で示されるような、４つのアクティビティの領域に分解される。すなわち、
領域１：ＬオブジェクトがアクティブでＲオブジェクトが無効(L∩/R)、
領域２：ＬオブジェクトがアクティブでＲオブジェクトもアクティブ(L∩R)、
領域３：Ｌオブジェクトが無効でＲオブジェクトがアクティブ(/L∩R)、
領域４：Ｌオブジェクトが無効でＲオブジェクトも無効（／(L∪R)）。
【００９８】
ここで、領域４は、常に、無演算（ＮＯＰ）の実行が要求されることになる。
従って、結果として、バイナリツリーのための有効なレベルとしては３つの異なった組合せが存在することになる。説明の簡単化のために、ここでは、領域(L∩/R)を左のノード領域或いは左の領域と称し、領域(/L∩R)を右のノード領域或いは右の領域と称し、領域(L∩R)を共通の領域と称する。左のノード領域と右ノード領域は、それぞれ親ノードの左及び右ブランチと関連し、イメージにおけるそれらの位置に対応するものではなく、オブジェクト演算子の順序（たとえば、Ｌｏｐ Ｒといった順序）に対応している。
【００９９】
この説明の目的のために、２項演算子がデータをツリーに提供するならば、その２項演算子はアクティブであるとみなされる。２項演算子のアクティビティは演算子自体の特有な性質とその左右のブランチのアクティビティである。
【０１００】
例として、図１８Ａと図１５の“out”演算子を比べてみる。“out”演算子には、領域(L∩/R)に関して、先頭のオブジェクト（左ブランチ）が部分的に透明であるか不透明であるかの如何にかかわらずツリーにデータを渡し、そして、共通の領域(L∩R)では、後続のオブジェクト（右のブランチ）が部分的に透明である場合にのみ、ツリーにデータを渡すという特有な性質がある。前者の場合は、現在スキャンされている画素のグループに対して、左ブランチがアクティブに、右ブランチが非アクティブになる場合にのみ発生する。後者の場合は、左右ブランチが、現在スキャンされた画素のグループに対してともにアクティブであるときに発生する。他方、“out”演算子には、後続（右ブランチ）のオブジェクトが部分的に透明であるかまたは不透明であるかにかかわらず、領域(/L∩R)に対して、データをツリーに渡さないという特有な性質がある。
【０１０１】
別の例として、図１８Ａと図１５の“in”演算子を比べてみる。“in”演算子には、領域(L∩R)に関して、データ（例えば色データ）をツリーに渡す特有な性質がある。しかしながら、これは、その左右ブランチがアクティブであるときにだけ生じる。他方、“in”演算子には、領域(/L∩R)と(L∩/R)に対し、どんなデータもツリーに渡さないという特有な性質がある。
【０１０２】
別の例として、図１８Ａと図１５の“ROUT”演算子を比較する。“ROUT”演算子には、領域(/L∩R)に関して、先頭の（右ブランチ）オブジェクトが部分的に透明であるか不透明であるかにかかわらずデータをツリーに渡し、共通領域(L∩R)では、後続の（左ブランチ）オブジェクトが部分的に透明である場合にのみデータをツリーに渡す特有の性質がある。前者の場合は、現在スキャンされた画素のグループに対してその左ブランチが非アクティブになり、右のブランチがアクティブになる場合にのみ発生する。後者の場合は、左右ブランチが現在スキャンされた画素のグループに対して共にアクティブであるときにだけ発生する。他方、“ROUT”演算子には、領域(L∩/R)に関して、下側（左ブランチ）のオブジェクトが部分的に透明であるかまたは不透明であるかにかかわらず、いかなるデータもツリーに渡さないという特有な性質がある。
【０１０３】
２項演算子のパフォーマンスとそのアクティビティの間には区別があることに注意すべきである。その両方のブランチがアクティブである場合にのみ、２項演算子は演算動作を実行する。さもなければ、演算子が要求する場合に、その結果は直接にアクティブなブランチから取得される。
【０１０４】
アクティビティ判断及び命令生成モジュール５００は、２項演算子のアクティビティと、表現ツリーのブランチのアクティビティ、およびグラフィックオブジェクト（リーフノード）のアクティビティに基づいてツリーをなぞり、命令を生成する。
【０１０５】
これらの命令が生成される方法について、図２０で示される例を参照して説明する。図２０は、図１９の表現ツリーにおいてオブジェクトＣがアクティブである状態を示すとともに、アクティビティ判断及び命令生成モジュール５００によって生成された、対応する命令リストを示す。モジュール５００は、まず最初に、表現ツリーの演算子の前述した特有の性質を判断する。これらの性質は、モジュール５００によって、検索と利用のために永久的（不揮発）に格納されている（不図示）。図２０において示される例では、モジュール５００は、記憶機構から“over”、“in”、および“out”演算子の２項演算子の性質を検索する。これらの性質は論理形式で格納されている。例えば、“over”演算子の性質は(/L∩R)=TRUEかつ(L∩/R)=TRUEとして格納される。すなわち、“over”演算子には、これらの領域に関してデータをツリーに渡す能力がある。別の例では、“in”演算子の性質は(/L∩R)=FALSEかつ(L∩/R)=FALSEとして格納される。すなわち、“in”演算子には、これらの領域に関して、ツリーにデータを渡す能力がない。更に別の例では、“out”演算子の性質は(/L∩R)=TRUEかつ(L∩/R)=FALSEとして格納される。以上の説明より明らかなように、領域(L∩R)の２項演算子の特有の性質はモジュール５００のパフォーマンスに対して不要であり、メモリに格納されない。そのノードの２進演算は、左右ブランチがアクティブであるときにいつも実行されるからである。
【０１０６】
図２０の例において、初期化処理段階の後、アクティビティ判断及び生成モジュール５００は、スキャンされた画素位置の特定のグループのために、そのオブジェクトＣがアクティブで、オブジェクトＡ、Ｂ、およびＤが非アクティブであることを判断する。モジュール５００はオブジェクトのアクティビティから、それぞれのバイナリノードのブランチのアクティビティを決定する。すなわち、アクティブなリーフノードオブジェクト（例えばオブジェクトＣ及びPAGE）をルートノード（例えば、１３）に直接に結合させている全てのブランチがアクティブとなる。この説明において、アクティブな左ブランチはL Active=TRUEとして示され、非アクティブな左ブランチはL Active=FALSEとして示され、アクティブな右ブランチはR Active=TRUEとして示され、非アクティブな右ブランチはR Active=FALSEとして示される。図２０の例において、モジュール５００は以下のことを決定する。
【０１０７】
（ｉ）バイナリノード１３の左右ブランチはアクティブである（すなわち、L Active=TRUE、かつR Active=TRUE）、
（ii）バイナリノード１２で 左ブランチは非アクティブであり、右ブランチはアクティブである（すなわち、L Active=FALSE、かつR  Active=TRUE）、
（iii）バイナリノード１１の左右ブランチは非アクティブである（すなわち、L Active=FALSE、かつR Active=FALSE)、
（iv）バイナリノード８で、左ブランチはアクティブであり、右ブランチは非アクティブである（すなわち、L Active=TRUE、かつR Active=FALSE）。
【０１０８】
この説明の目的のために、本明細書ではシンボル&&、||、及び！を、それぞれバイナリ論理演算子のＡＮＤ、ＯＲ、ＮＯＴとして用いる。
【０１０９】
次に、アクティビティ判断及び命令生成モジュール５００は、現在スキャンされた画素位置のグループについてなぞり、命令を生成する。それは２項演算子のアクティビティ、表現ツリーのブランチのアクティビティ、およびグラフィックオブジェクト（リーフノード）のアクティビティに基づいている。モジュール５００は、上から下へ、左から右という方法で、ルートノード（例えば、ノード１３）で始まる表現ツリーをなぞる。
【０１１０】
ここで、モジュール５００は、以下の条件を満たす表現ツリーのブランチのみをなぞる。すなわち、
（１）先になぞられたバイナリノードに関して、（L active && R active）||（(L∩/R)&& L active && !R active）==TRUEである場合は、先になぞられたバイナリノードの左ブランチの下方ノードへなぞる（トラバースする）。
（２）先になぞられたバイナリノードに関して、（L active && R active）||(/L∩R)&& !L active && R active）==TRUEの場合、先になぞられたバイナリノードの右ブランチの下方ノードへなぞる。
【０１１１】
このなぞり（トラバース）と同時間の間、アクティビティ判断及び命令生成モジュール５００は、アクティブな左右ブランチを有するなぞられたバイナリノードのための演算子命令と、なぞられたあらゆるリーフノードのためのリーフ値命令を生成する。
【０１１２】
図２０の例において、アクティビティ判断及び命令生成モジュール５００は、ルートノード１３からそのトラバースを開始する。ルートノード１３の左右のブランチ両方がアクティブであるので、モジュール５００は“over”演算子命令を生成する。同じ理由で、モジュール５００は、バイナリノード１２とバイナリノード０〜５をなぞる。モジュール５００が上から下へ、左から右へという方式でなぞるので、最初にバイナリノード１２がなぞられる。このバイナリノード１２では、バイナリ１２の左ブランチが非アクティブであるので、モジュール５００は“over”演算を生成しない。同じ理由で、モジュール５００は左ブランチであるバイナリノード１１をなぞらない。しかしながら、バイナリノード１２の右ブランチがアクティブであり、バイナリノード１２の左ブランチが非アクティブであり、“over”演算子に関して(/L∩R)=TRUEであるので、モジュール５００はバイナリのノード８をなぞる。このバイナリノード８では、その右ブランチが非アクティブであるため、モジュール５００は“out”演算を生成しない。同じ理由で、モジュール５００は右ブランチであるリーフノード６をなぞらない。しかしながら、バイナリノード８の左ブランチがアクティブであり、バイナリノード８の右ブランチが非アクティブであり、“out”演算子に関する(L∩/R)＝TRUEが成立するので、モジュール５００はリーフノード７をなぞる。リーフノード７では、モジュール５００がリーフ値命令Ｃを生成する。次に、リーフノード０−５をなぞるために、モジュール５００はルートノード１３に戻る。リーフノード０−５では、モジュール５００がリーフ値命令“PAGE”を生成する。図１９と図２０を比較すると、モジュール５００が、スキャンされた画素位置のその現在のグループに対する表現ツリーに対応する最小量の命令セットを生成していることがわかる。そして、モジュール５００は、次の隣接しているエッジの間のスキャンされた画素位置の次のグループのために動作を繰り返す。
【０１１３】
アクティビティ判断及び命令生成モジュール５００の各部の動作について、図５を参照して更に詳細に説明する。
【０１１４】
上述したように、レベルアクティベーションテーブル生成部５０２はレベルアクティベーションテーブルを生成する。図２１をみると、そのような生成されたレベルアクティベーションテーブルの例が示されている。この特定のLevel Activation Tableは図１９で示される表現ツリーのリニアライズされた書式を表す。図２１のレベルアクティベーションテーブルは、表現ツリーのそれぞれのノードに関するレコードを有する。これらのレコードは、それぞれ以下のフィールドを有する。“Index”、“L Active”、“R Active”、“(L∩/R)”、“(/L∩R)”、“Leaf/Operator Entry”、“Node Active”、“Parent”、“Node is L”、“Generate L”、“Generate R”、“(L∩R) op used”、および“R Branch Index”がある。“Index”、“(L∩/R)”、“(/L∩R)”、“Leaf/Operator Entry”、“Parent”、“Node is L”、および“R Branch Index”のフィールドの内容は、現在のスキャンされた画素位置に関する関数として変化するものではないので、静的である。一方、“L Active”、“R Active”、“Node Active”、“Generate L”、“Generate R”、および“(L∩R) op used”というフィールドの内容は、現在スキャンされた画素位置によって異なる可能性がある。後者のフィールドは、隣接しているエッジの間の画素位置の各グループのために、レベルアクティベーションテーブル更新モジュール５０４によってアップデートされる。
【０１１５】
“Index”フィールドは適切なレコードと関連するノードの数値ラベルを含んでいる。例えば、図１９のノード１２に対応するレコードは、その“Index”フィールドが１２に設定される。“Parent”フィールドはレコードと関連するノードの親ノードの数値ラベルを含んでいる。例えば、図１９のノード１２に対応するレコードは「親」フィールドを１２に設定させる。すなわち、ノード１２の親ノードはノード１３である。“R branch Index”フィールドはそのレコードに関連するノードの右ブランチにぶら下がるノードの数値ラベルを含んでいる。例えば、図１９のノード１２に対応するレコードは、８に設定された“R branch Index”フィールドを有する。すなわち、ノード１２の右ブランチ上のノードはノード８である。“Node is L”フィールドは、レコードと関連する当該ノードが、その親ノードの左ブランチからぶら下がっているかどうかを示す論理フィールドである。例えば、ノード１２に対応するレコードは、TRUE(1)にセットされた“Node is L”フィールドを有する。すなわち、ノード１２は親ノード１３の左ブランチを通して親ノード１３にぶら下がっている。“Leaf/Operator Entry”フィールドは、そのレコードに関連するバイナリノードの２項演算子か、或いはリーフノードのオブジェクトを含んでいる。例えば、図１９のバイナリノード１２に対応するレコードは、合成演算子“over”にセットされた“Leaf/Operator Entry”フィールドを有する。また、別の例では、図１９のリーフノード７に対応するレコードは、オブジェクト“Ｃ”がセットされた“Leaf/Operator Entry”フィールドを有する。このようにして、表現ツリーの構造を完全に再建することができる。
【０１１６】
“L Active”フィールドは、現在スキャンされている画素のグループに依存して、レコードに対応するバイナリノードの左ブランチがアクティブであるかどうかを示す論理フィールドである。同様に、“R Active”フィールドは、現在スキャンされている画素のグループに依存して、レコードに対応するバイナリノードの右ブランチがアクティブであるかどうかを示す論理フィールドである。初期化処理段階の間、スキャン中の画素は存在しないので、バイナリレコードのすべての“L Active”と“R Active”フィールドがFALSE(0)にセットされる。ただし、ルートノードの“R Active”フィールドには例外がある可能性がある。例えば、図１９のルートノード１３に対抗するレコードの“R Active”フィールドはTRUE(1)に設定される。ノード１３の右ブランチが画素のスキャンの如何にかかわらずいつもアクティブだからである。なお、リーフノードはいかなるブランチも有さないので、対応するレコードにおける“L Active”と“R Active”フィールドを設定する必要がない。
【０１１７】
“(L∩/R)”フィールドは、この領域(L∩/R)からのデータが表現ツリーに渡される必要があるかどうかを示す論理フィールドである。同様に、“(/L∩R)”フィールドは、この領域(/L∩R)からのデータが表現ツリーに渡される必要があるかどうかを示す論理フィールドである。以上のように、これは合成演算子の固有の特性である。例えば、図１９のノード１２に対応するレコードは、“over”に設定された“Leaf/Operator Entry”を有する。また、(/L∩R)と(L∩/R)の領域の両方からのデータがツリーに渡される必要があるので、TRUE(1)に設定された関連するフィールド“(/L∩R)”と“(L∩/R)”を有する。別の例では、図１９のノード１１に対応するレコードは、“in”に設定された“Leaf/Operator Entry”を有する。また、領域(/L∩R)と(L∩/R)からのデータがツリーに渡される必要がないので、FALSE(0)に設定された関連するフィールド“(/L∩R)”と“(L∩/R)”を有する。これらのフィールドはバイナリノード（すなわち、合成演算）のみに関連するので、リーフノードに対応するレコードについてはこれらのフィールドを設定する必要はないことに注意されたい。
【０１１８】
以下の条件、
0004630482.tif 000002
を満足する場合に、“Node Active”フィールドは、TRUE(1)に設定され、他の場合にはFALSE(0)に設定される。
【０１１９】
例えば、図１９で示されるバイナリノード８、１１、及び１２の“Node Active”フィールドは、初期化処理段階の間、FALSE(0)に設定される。すべての対応するブランチ(L ActiveとR Active)が非アクティブ（すなわち、 FALSE）だからである。初期化処理段階の間、図１９のバイナリノード１３のための“Node Active”フィールドはTRUE(1)にセットされる。その右ブランチがアクティブであり（R Active=TRUE）、その左ブランチが非アクティブであり（L Active=FALSE）、その領域が演算子“over”の演算に必要であるからである。このフィールドがバイナリノード（すなわち、合成演算）だけに関連するので、リーフノードに対応するレコードのためのこれらフィールドを設定する必要がないことに注意すべきである。レコードの“Node Active”フィールドは、対応する２項演算子がアクティブであるかどうかを示す。
【０１２０】
0004630482.tif 000003
を満たす場合にTRUE(1)に設定され、そうでない場合にFALSE(0)に設定される論理フィールドである。
【０１２１】
例えば、図１９のすべてのバイナリノード１３、１２、１１に関する“Generate L”フィールドは、初期化処理段階の間、FALSE(0)に設定される。この条件がこれらのノードのいずれによっても満たされないからである。すなわち、ノード８、１１、１２及び１３の左ブランチがすべて非アクティブ、すなわちL Active = FALSE (0)である。また、このフィールドがバイナリノード（すなわち、合成演算）だけに関連するので、リーフノードに対応するレコードに対してこれらのフィールドを設定する必要ない。
【０１２２】
同様に、“Generate R”フィールドは、以下の条件、
0004630482.tif 000004
が満たされるときにTRUE(1)に設定され、そうでない場合にはFALSE(0)に設定される論理フィールドである。
【０１２３】
例えば、初期化処理段階の間、上記条件が図１９のバイナリノード１２、１１及び８のいずれによっても満たされないので、これらのノードに対する“Generate R”フィールドはFALSE(0)に設定される。例えば、ノード８、１１及び１２の右ブランチはすべて非アクティブ、すなわちR Active=FALSE(0)である。しかしながら、バイナリノード１３の右のブランチがアクティブであるので、バイナリノード１３の“Generate R”フィールドは初期化処理の間TRUE(1)にセットされ、左のブランチは非アクティブにセットされ、(/L∩R)=TRUEである。また、このフィールドがバイナリノードだけ（すなわち、合成演算）に関連するので、リーフノードに対応するレコードにおけるこれらのフィールドを設定する必要はないことに注意されたい。
【０１２４】
“(L∩R) op used”フィールドは、以下の条件、
(L active && Ractive)＝＝TRUE
が満たされるときにTRUE(1)に設定され、他の場合にはFALSE(0)に設定される論理フィールドである。
【０１２５】
例えば、初期化処理段階の間、図１９のバイナリノードの全ての左ブランチが非アクティブであるので、すべてのバイナリノードに対するこのフィールドはFALSE(0)に設定される。
【０１２６】
次に、図２２を参照すると、レベルアクティベーションテーブルの前述のフィールド、“Node Active”、“Generate L”、“Generate R”、および“(L∩R) op used”を設定するための論理回路が示されている。この論理回路は従来形式の一連の論理ゲートで示されており、その動作は自明であるため、これ以上の説明を省略する。
【０１２７】
次に、図５に戻って、レベルアクティベーションテーブル生成モジュール５０２は初期化処理段階の間に作り出されるレベルアクティベーションテーブルをメモリ３４に格納する。次に、更新モジュール５０４は、隣接しているエッジの間のスキャンされている画素位置の各グループに対するこの初期化されたレベルアクティベーションテーブルを取得して、そのテーブルのフィールドを更新する。更新モジュール５０４は、現在のスキャンされている画素位置のグループに依存して、フィールド“L Active”、“R Active”、“Node Active”、“Generate L”、“Generate R”、および“(L∩R) op used”の状態を変える。更新モジュール５０４は、所定の方法でレコードを更新する。その更新は、その画素位置においてアクティブなオブジェクトに対応するリーフノードの親ノードのレコードから始める。レコードにおける“Node Active”フィールドの状態を変えるときには、“Node is L”フィールドの状態に依存して、更新モジュール５０４は親ノードのレコードにおける“L active”或いは“R active”フィールドの状態における変更を引き起こす。そして、この新たに変えられた“L Active”或いは“R Active”フィールドに従って、更新モジュール５０４は親ノードのレコードの残りのフィールドを更新する。この更新プロセスは、“Node Active”フィールドが変わらずに残るところのレベルまで継続する。１つ以上のアクティブオブジェクトがあるとき、更新モジュールは一度に１つのアクティブオブジェクトについてテーブルをアップデートする。
【０１２８】
更新モジュール５０４の更新プロセスについて、図２３を参照して説明する。
図２３は、図２０に示したオブジェクトＣがアクティブである表現ツリーのための更新されたレベルアクティベーションテーブルを示す。更新モジュール５０４は、最初に、オブジェクトＣがスキャンされた画素位置の現在のグループに対してアクティブであるかを判断し、次にメモリ３４から初期化されたレベルアクティベーションテーブルを取得する。更新モジュール５０４は、リーフノードＣのレコードの“Parent”フィールドから、アクティブオブジェクトＣの親ノードを決定する。次に、更新モジュールは、以下の方法でテーブルのレコードを更新するべく処理を進める。これは、オブジェクトＣの親ノードより開始される（レコード８）。
【０１２９】
−親ノード（レコード８）の“L Active”フィールドが設定される;
−これはレコード８における“Generate L”フィールドをアサートする;
−レコード８の“Node Active”フィールドが設定される;
−親ノード（レコード１２）の“R active”フィールドが設定される;
−これはれコード１２における“Generate R”フィールドをアサートする;
−レコード１２の“Node Active”フィールドが設定される;
−親ノード（レコード１３）の“L Active”フィールドが設定される;
−これはレコード１３における“Generate L”と“L∩R op used”フィールドをアサートする;
−レコード１３における“Node Active”フィールドが既に設定されているので、処理を止める。
【０１３０】
この時点で、テーブルは命令生成のための正しい状態となる。
【０１３１】
図５に戻り、更新モジュール５０４は現在スキャンされている画素位置のグループのための、この更新されたレベルアクティベーションテーブルをメモリ３４に格納する。そして、このメモリ３４より、トラバーサル及び命令生成モジュール５０６によって、更新されたレベルアクティベーションテーブルが取得される。トラバーサル及び命令生成モジュール５０６はスタックマシンベースのロボットであり、表現ツリーをトップダウン型でなぞり、更新されたレベルアクティベーションテーブルに従って命令を生成する。スタックは、レコードの“R branch Index”を格納するのに使用される。以下の中間コードに従って、スタックマシンは以下の動作を実行する。
【０１３２】
0004630482.tif 000005
【０１３３】
命令モジュール５０６のトラバースと命令生成プロセスについて、図２３を参照して説明する。図２３は、オブジェクトＣがアクティブである図２０の表現ツリーのための更新されたレベルアクティベーションテーブルを示す。上記の中間コードと図２３のレベルアクティベーションテーブルとに従った命令の生成は以下のように進行する。
【０１３４】
（i）処理はレコード１３（ルートノード）より開始する;
（ii）レコード１３の“L∩R op used”フィールドがTRUE(1)  なので、“over”命令が命令リストに加えられる;
（iii） レコード１３の“Generate R”フィールドがTRUE(1)なので、レコード１３の“R Branch Index”の内容がスタックに加えられる。その結果、スタックはインデックス（５）を格納する;
（iv）レコード１３の“Generate L”フィールドがTRUE(1)であるので、処理はレコード１２に進む;
（v）レコード１２の“L∩R op used”フィールドがFALSE(0)であるので、いかなる命令も加えられない;
（vi） レコード１２の“Generate R”フィールドがTRUE(1)であるので、レコード１２の“R Branch Index”の内容がスタックに加えられる。その結果、スタックは、その時点で、インデックス（８，５）を格納する;
（vii） レコード１２の“Generate L”フィールドがFALSE(0)であり、その結果、処理は抜け落ちる;
(viii) スタックが空ではないので、インデックス８がスタックからポップされて、処理はインデックス８に対応するレコードへ移動する。その結果、この時点で、スタックはインデックス（５）を格納することになる;
（ix）レコード８の“L∩R op used”フィールドがFALSE(0)であるので、どんな命令も加えられない;
（x） レコード８の“Generate R”フィールドがFALSE(0)であるので、スタックに何も加えられない。その結果、スタックは、この時点でインデックス（５）を格納する;
（xi）レコード８のフィールド“Generate L”がTRUE(1)であるので、処理は次のエントリ、すなわちレコード７に移動する;
（xii）レコード７がリーフであるので、リーフ値命令がリストに加えられて、処理は抜け落ちる;
（xiii）スタックが空でないので、インデックス５がスタックからポップされて、処理はインデックス５へ移動する。スタックはこの時点で空になる。
このプロセスは完了へと続く。
【０１３５】
この例において生成された命令が図２０に示される。
【０１３６】
このようにして、トラバーサル及び命令生成モジュール５０６は、あらゆる１つ以上のアクティブオブジェクトのために、表現ツリーの描画に必要な命令の最小限のセットを生成することができる。これらの命令は、次に、色塗潰し決定モジュール６００に渡される。
【０１３７】
アクティビティ判断及び命令生成モジュール５００の別の実施形態において、モジュールは、不透明物体がオーバラッピング領域でもう片方のオブジェクトを見えなくするかもしれないという事実を考慮に入れる。実際に、ノードのブランチの一方は、他方によって隠され得る。両方のオブジェクトがアクティブである場合に、オブジェクトが不透明物体によって隠されるならば、そのオブジェクトを生成する必要はない。これらの余分な処理が実行されるのを防ぐために、レベルアクティベーションテーブルを変更することができる。
【０１３８】
次に図２５を参照すると、そのような改造されたレベルアクティベーションテーブルの例が示されている。このテーブルは、２つのフィールド“L obscures R（LはRを隠す）”と“R obscures L（RはLを隠す）”が加わっているという点を除いて、図２１のレベルアクティベーションテーブルと同じ構造である。“LはRを隠す”フィールドは論理フィールドであり、左右両方のオブジェクトがアクティブであるときに、左のオブジェクトが右のオブジェクトを隠すかどうかを示す。同様に、フィールド“RはLを隠す”も論理フィールドであり、左右両方のオブジェクトがアクティブであるときに、右のオブジェクトが左のオブジェクトを隠すかどうかを示す。“Generate R”、“L∩R op used”及び“Generate L”フィールドに含まれるデータも、図２１のれベルアクティベーションテーブルとは異なる論理に基づく。obscuranceフラグは不透明なオブジェクトと透明なオブジェクトを含む表現ツリーで非常に役に立つ。
【０１３９】
図２４には、改造されたレベルアクティベーションテーブルのフィールド、“Node Active”、“Gnerate L”、“Generate R”、および“(L∩R) op used”を設定するための論理回路が示される。図２２に対して“Node Active”の論理が変化しており、その時点のデータがノードによって生成されたかどうかに基づいていることがわかる。回路のクリティカルパスは長いが、これは、同じ論理を使用して実行されるオブジェクトのクリッピングを可能とする。obscuranceフィールドの両方がセットされるならば、どんなデータも論理積領域において生成されない（これは、CLIP OUTの実現の一部である）。
【０１４０】
これらのobscuranceフィールドは、図２５のLevel Activation Tableに示されるように、CLIP IN動作とCLIP OUT動作を実現するのに用いられてもよい。CLIP INとCLIP OUT動作のためのフィールド設定は図２５のTableに示されている。
【０１４１】
CLIP IN動作と単純なin動作との間の違いは、右ブランチ動作が決して実行されないということである。図２６に示されるIN動作の真理値表と図２７に示されるCLIP IN動作の真理値表との比較からこれを見ることができる。これらの真理値表では、Ｔは透明(非アクティブ)を表し、Ｏは不透明を表す。そして、ＬとＲはそれぞれＬの不透明が未知であること、Ｒの不透明が未知であることを表す。違いのあるボックスは強調表示されている。CLIP INの場合では、右オブジェクトの使用開始が左オブジェクトのための命令の生成を可能にするので、左のオブジェクトは切り取られるエッジである。なお、右オブジェクトは任意の多くのオブジェクトの合成であってもよい。この合成には、必要に応じたいかなる組合せ、異なる充てんルールも使用してよい。右オブジェクトのアクティビティ状態は、全てCLIP IN動作によって使用される。従前のシステムでは、切取りオブジェクトは別々の単一レベルから成る。それは、アクティベートされるかまたはディアクティベートされるときに、クリップが適用されるすべてのレベルに対するカウンタに作用した。本構成においては、クリップオブジェクトは特殊なものとして全体図オブジェクトの特殊ケースとして現れ、表現ツリーのノードとして現れる。そして、その結果、あらゆるレベルでカウンタを増加するかまたは減少させる必要性なく、アクティブ化或いは非アクティブ化がクリップを適用する。
【０１４２】
CLIP OUT動作と単純なout動作との間の違いは、図２８に示されるＯＵＴ動作の真理値表と図２９に示されるCLIP IN動作に関する真理値表との比較から見ることができる。ここでも、Ｔは透明（非アクティブ）を表し、Ｏは不透明を表し、ＬとＲは、それぞれＬの不透明が未知であること、Ｒの不透明が未知であることを表す。また、違いの生じているボックスが強調表示されている。CLIP OUTの場合では、右オブジェクトのアクティブ化が左オブジェクトのための命令の生成を防ぐので、左オブジェクトは切り取られるエッジである。CLIP INに関しては、右オブジェクトは必要に応じた異なった充てんルールを有する、オブジェクトの任意の複雑なコレクションとなるかもしれない。クリッピングに使用されるのは、アクティビティの状態だけである。
【０１４３】
上述したアクティビティ判断及び命令生成モジュール５００は、表現ツリーに基づく。しかしながら、モジュール５００の本質はＤＡＧｓ（有向隣接図表：Directed Adjacency Graphs）に一般化され得る。これは、レベルアクティベーションテーブルのレコードの親ノードフィールドが、その親ノードへのテーブルエントリのリストを含むことを許容し、Ｌインデックスポインタを提供することによって、モジュール５００の更なる実施形態によって達成され得る。ノードの状態の変更は、その親ノードのすべてが変更されることを要求し、命令の生成は、単に次のテーブルエントリを探すのではなく、Ｌインデックスに従うために必要となる。ＤＡＧｓは、クリッピングオブジェクトとの使用に関して有用である。そこでは、複数のオブジェクトが同じオブジェクトによってクリップされる。
【０１４４】
更に別の実施形態は、開始ノード、すなわち、演算或いはデータを提供する最初のノード、がその左ブランチからのデータをレンダリングされたページ上に合成するということに基づく。これは、左ブランチをレンダリングされたページと合成するノードを特定するレベルアクティベーションテーブルに“Page”フィールドを加えることによって特定され得る（R is PAGE）。そのページにデータを置いているアクティブなノードを特定するためのテーブルエントリデータを１ビットで提供するために、この“Page”フィールドと“Generate L”フィールドとをANDしてもよい。開始ノードはこれらのうちの最優先ノードであり、命令生成のために、サーチされ得る。これはツリーの幹にある、動作を提供しないノードに関してツリーをなぞることによるオーバヘッドを排除する。
【０１４５】
次に、図３０をみると、レンダリングされたページにそれらの左ブランチを合成するノードを示す模式的な表現ツリー３００が示されている。わかるように、ノード３０２、３０４、３０６、および３０８はそれらの左ブランチがレンダリングされたブランチ上に合成され、これらのノードの各々の“Page”フィールドがTRUE(1)にセットされる。この“Page”フィールドは同じノードの“Generate L”フィールドとのANDであってもよい。ここで、Generate L”フィールドは、ページにデータを置くそれらのアクティブなノードを確認する。表現ツリーの例において、ノード３０２、３０６、および３０８はアクティブであって、ノード３０４は非アクティブである。したがって、必要な命令を生成するために、アクティブなノード３０２、３０６、および３０８のそれらのサブツリーだけがなぞられる必要がある。こうして、ツリーのトラバーサルを最小にする、
以上、好適な実施形態としてアクティビティ判断及び命令生成モジュール５００を集積回路として説明したが、ホストプロセッサ２等のような汎用処理ユニット上で実行可能な等価なソフトウエアモジュールとして実現されてもよい。ソフトウェアモジュールはディスク装置やコンピュータネットワークなどのようなコンピュータ可読媒体を介してユーザに配られ得るコンピュータプログラム製品の一部を形成してもよい。
【０１４６】
４．０  塗潰し色決定モジュール
塗潰し色決定モジュール６００の動作を、図６を参照して、以下に説明する。
アクティビティ判断及び命令生成モジュール５００からの着信メッセージ５９８は、塗潰しデータ設定メッセージ、反復メッセージ、塗潰し優先順位メッセージ、画素の終りメッセージおよびスキャンラインの終りメッセージを含み、まず、塗潰しルックアップ及び制御モジュール６０４に渡される。塗潰しルックアップ及び制御モジュール６０４は、塗潰し色決定モジュール６００のさまざまな構成要素による使用のために、現行Ｘ位置カウンタ６１４および現行Ｙ位置カウンタ６１６を維持する。
【０１４７】
スキャンラインの終りメッセージを受け取った時には、塗潰しルックアップ及び制御モジュール６０４は、現行Ｘ位置カウンタ６１４を０にリセットし、現行Ｙ位置カウンタ６１６をインクリメントする。スキャンラインの終りメッセージは、その後、画素合成モジュール７００に渡される。
【０１４８】
塗潰しデータ設定メッセージを受け取ったときには、塗潰しルックアップ及び制御モジュール６０４は、塗潰しデータテーブル３６の指定された位置６０２にそのデータを記憶する。
【０１４９】
反復メッセージを受け取ったときには、塗潰しルックアップおよび制御モジュール６０４は、反復メッセージからのカウントだけ現行Ｘ位置カウンタ６１４をインクリメントする。反復メッセージは、その後、画素合成モジュール７００に渡される。
【０１５０】
画素の終りメッセージを受け取ったときには、塗潰しルックアップ及び制御モジュール６０４は、やはり現行Ｘ位置カウンタ６１４をインクリメントし、この画素の終りメッセージは、その後、画素合成モジュール７００に渡される。
【０１５１】
塗潰し優先順位メッセージを受け取ったときには、塗潰しルックアップ及び制御モジュール６０４は、下記の処理を含む動作を実行する。
【０１５２】
（ｉ）塗潰し優先順位メッセージからの塗潰しタイプを使用して、テーブル３６のレコードサイズを選択する、
（ii）塗潰し優先順位メッセージからの塗潰しテーブルアドレスと、上で決定されたレコードサイズを使用して、塗潰しデータテーブル３６からレコードを選択する、
（iii）塗潰し優先順位メッセージからの塗潰しタイプを使用して、塗潰し色の生成を実行するサブモジュールを決定し、選択する。サブモジュールには、ラスタイメージモジュール６０６、フラットカラーモジュール６０８、リニアランプカラーモジュール６１０および不透明タイルモジュール６１２を含めることができる、
（iv）決定されたレコードを、選択されたサブモジュール６０６乃至６１２に供給する、
（ｖ）選択されたサブモジュール６０６乃至６１２が、供給されたデータを使用して、色と不透明度の値を決定する。
【０１５３】
（vi）決定された色と不透明度は、塗潰し色メッセージからの残りの情報、すなわち、ラスタ演算コード、アルファチャネル演算コード、ソースポップフラグおよびデスティネーションポップフラグと組み合わされて、色合成メッセージを形成し、この色合成メッセージは、接続６９８を介して画素合成モジュール７００に送られる。
【０１５４】
好ましい実施形態では、決定された色と不透明度が、８ビットの精度の赤、緑、青および不透明度の４つの組であり、通常の形で３２ビット／画素が与えられる。しかし、シアン、マゼンタ、黄および黒の、不透明度を含有する４つの組か、他の多数の既知の色表現のうちの１つを、その代わりに使用することができる。以下では、赤、緑、青および不透明度の場合を説明するが、この説明は、他の場合にも適用することができる。
【０１５５】
ラスタ画像モジュール６０６、フラットカラーモジュール６０８、リニアランプカラーモジュール６１０および不透明タイルモジュール６１２の動作を以下に説明する。
【０１５６】
フラットカラーモジュール６０８は、供給されたレコードを、３つの８ビットの色成分（通常は赤、緑および青の成分と解釈される）と１つの８ビットの不透明度値（通常は、指定された色によって覆われる画素の割合の尺度と解釈され、０は覆われないすなわち完全な透明を意味し、２５５は完全に覆われるすなわち完全な不透明を意味する）を含む固定フォーマットのレコードと解釈する。この色と不透明度の値は、接続６９８を介して直接に出力され、それ以上の処理なしで、決定された色および不透明度を形成する。
【０１５７】
リニアランプカラーモジュール６１０は、供給されたレコードを、３つの色成分および１つの不透明度成分に関連する４組の定数cx、cyおよびdと、リニアランプの基準点の座標である２つの位置値xbaseおよびybaseを含む固定フォーマットのレコードと解釈する。基準点では、色成分と不透明度成分が、それに関連付けられたd値を有する。
【０１５８】
４組のそれぞれについて、結果の値rは、次式を使用して、現在のXY座標とxbaseおよびybase定数に３つの定数を組み合わせることによって計算される。すなわち、
0004630482.tif 000006
のように定義される。
【０１５９】
代替の実装では、リニアランプカラーモジュール６１０は、供給されたレコードを、３つの色成分および１つの不透明度成分に関連する、４組の３つの定数cx、cyおよびdを含む固定フォーマットのレコードと解釈する。これらの４組のそれぞれについて、結果の値ｒは、次式を使用して、３つの定数を現行Ｘカウントであるｘおよび現行Ｙカウントであるｙと組み合わせることによって、
r=clamp(cx×x+cy×y+d)
により計算される。ここで、関数clampは、上で定義されたものである。
【０１６０】
以上のように生成された４つの結果は、色と不透明度の値に形成される。この色と不透明度の値は、接続６９８を介して直接に出力され、それ以上の処理なしで決定された色および不透明度を形成する。
【０１６１】
同一の結果を与える他の算術計算を使用することができる。
【０１６２】
不透明タイルモジュール６１２は、供給されたレコードを、３つの８ビット色成分、１つの８ビット不透明度値、整数のＸ位相（px）、Ｙ位相（py）、Ｘスケール（sx）、Ｙスケール（sy）および６４ビットのマスクを含む固定フォーマットのレコードと解釈する。これらの値は、表示リスト生成から発し、通常は、元のページ記述に含まれる。ビットマスク内のビットアドレスaは、以下の式、
a=((x/2sx+px)mod 8)+((y/2sy+py)mod 8)×8
で決定される。
【０１６３】
ビットマスク内のアドレス「a」のビットが検査される。検査されるビットが１の場合には、レコードからの色と不透明度が、モジュール６１２の出力に直接にコピーされ、決定された色および不透明度を形成する。検査されるビットが０の場合には、３つの０成分値を有する色と０の不透明度値が形成され、決定された色および不透明度として出力される。
【０１６４】
ラスタ画像モジュール６０６は、供給されたレコードを、６つの定数a、b、c、d、xbaseおよびybaseと、サンプリングされるラスタ画像画素データ１６の各ラスタライン内のビット数の整数カウント（bpl）と、画素タイプとを含む固定フォーマットのレコードと解釈する。画素タイプは、ラスタ画像画素データ内の画素データ１６を、次のうちのどれとして解釈するかを示す。
【０１６５】
（ｉ）１ビット毎画素の白黒不透明画素
（ii）１ビット毎画素の不透明黒または透明の画素
（iii）８ビット毎画素のグレイスケール不透明画素
（iv）８ビット毎画素の黒不透明スケール画素
（ｖ）２４ビット毎画素の不透明３色成分画素
（vi）３２ビット毎画素の３色成分と不透明度の画素
他の多くのフォーマットが可能である。
【０１６６】
ラスタ画像モジュール６０６は、画素タイプインジケータを使用して、ビット単位の画素サイズ（ｂｐｐ）を決定する。その後、ラスタ画像画素データ１６内のビットアドレスａを、以下の式、
0004630482.tif 000007
から計算する。
【０１６７】
レコード６０２からの画素タイプに従って解釈された画素は、ラスタ画像画素データ１６内の計算されたアドレス「ａ」から取り出される。この画素は、３つの８ビット色成分と１つの８ビット不透明度成分を有するために、必要に応じて展開される。「展開」とは、たとえば、８ビット／画素のグレイスケール不透明ラスタ画像からの画素が、赤、緑および青の成分のそれぞれに適用されるサンプリングされた８ビット値と、完全な不透明がセットされた不透明度成分を持つことを意味する。これが、画素合成モジュール７００への決定された色および不透明度の出力６９８を形成する。
【０１６８】
その結果、表示可能オブジェクト内で有効なラスタ画素データは、メモリ内の画像画素データ１６へのマッピングの決定を介して得られる。これによって、ラスタ画素データのオブジェクトベース画像へのアフィン変換が効率的に実施され、これは、グラフィックオブジェクトとの合成が発生する可能性がある場合に画像ソースからの画素データをフレームストアに転送する従来技術の方法より効率的である。
【０１６９】
上記に対する好ましい特徴として、任意選択として、ラスタ画像画素データ１６内の画素間の補間を、まず中間結果ｐおよびｑを以下の式、
p=a×(x-xbase)+c×(y-ybase)
q=b×(x-xbase)+d×(y-ybase)
に従って計算することによって実行することができる。
【０１７０】
次に、ラスタ画像画素データ１６内の４画素のビットアドレスa00、a01、a10およびa11を、以下の式、
a00=bpp×└p┘+bpl×└q┘
a01=a00+bpp
a10=a00+bpl
a11=a00+bpl+bpp
に従って決定する。
【０１７１】
次に、各色成分および不透明度成分のそれぞれについて、結果の画素成分値rを、以下の式
r=interp(interp(get(a00),get(a01),p),interp(get(a10),get(a11),p),q)
に従って、決定する。
ここで、関数interpは、
interp(a,b,c)=a+(b-a)×(c-└c┘)
のように定義される。
【０１７２】
上の諸式で、表現└値┘=floor（値）であり、floor演算では、値の端数部分の切捨が行われる。
【０１７３】
get関数は、所与のビットアドレスでの、ラスタ画像画素データ１６からサンプリングされた現行画素成分の値を返す。いくつかの画像タイプのいくつかの成分について、これが暗黙の値になる可能性があることに留意されたい。
【０１７４】
上記に対する好ましい特徴として、任意選択として、供給されたレコードから読み取られるタイルサイズを用いる剰余演算によって現行Ｘ位置カウンタ６１４および現行Ｙ位置カウンタ６１６から導出されるｘおよびｙの値を上式で使用することによって、画像タイリングを実行することができる。
【０１７５】
多数の他のこのような塗潰し色生成サブモジュールが可能である。
【０１７６】
５．０  画素合成モジュール
以下に、画素合成モジュール７００の動作を説明する。塗潰し色決定モジュール６００からの着信メッセージには、反復メッセージ、色合成メッセージ、画素の終りメッセージおよびスキャンラインの終りメッセージが含まれるが、このメッセージは、順番に処理される。
【０１７７】
反復メッセージまたはスキャンラインの終りメッセージを受け取った時には、画素合成モジュール７００は、それ以上の処理なしで画素出力ＦＩＦＯ７０２にそのメッセージを転送する。
【０１７８】
色合成メッセージを受け取った場合の画素合成モジュール７００の動作概要を示せば、色合成メッセージからの色と不透明度を、色合成メッセージからのラスタ演算およびアルファチャネル演算に従って、画素合成スタック３８からポップされた色および不透明度と組み合わせる。その後、結果を画素合成スタック３８にプッシュする。色合成メッセージの受取り時に実行される処理の説明は以下でなされる。
【０１７９】
画素の終りメッセージを受け取った時には、画素合成モジュール７００は、画素合成スタック３８から色と不透明度をポップする。ただし、スタック３８が空の場合には不透明の白の値が使用される。結果の色と不透明度は、画素出力ＦＩＦＯに転送される画素出力メッセージに形成される。
【０１８０】
既知の合成アプローチは、ポーター（Porter,T）およびダフ（Duff,T）著「Compositing Digital Images」、Computer Graphics誌、Vol.18  No.3、1984年、第253〜259ページに記載されている。ポーター−ダフ合成演算の例を、図１５に示す。しかし、このようなアプローチでは、合成によって形成される交差領域内のソースおよびデスティネーションの色の処理だけが可能であり、その結果、交差領域内の透明度の影響には適合できないという点で不完全である。その結果、ポーターおよびダフによって定義されたラスタ演算は、透明度の存在下で基本的に動作不能である。
【０１８１】
色合成メッセージを受け取った時に画素合成モジュール７００によって実行される処理を以下に説明する。
【０１８２】
色合成メッセージを受け取った際に、画素合成モジュール７００は、まず、ソースの色と不透明度を形成する。これは、色合成メッセージでポップソースフラグがセットされていない限り、色合成メッセージで供給された色と不透明度が使用され、ポップソースフラグがセットされている場合には、その代わりに画素合成スタック３８から色がポップされる。この場合、すなわち、画素合成スタックのポップ中に画素合成スタック３８が空であることがわかった場合、エラー表示なしで不透明の白の色値が使用される。次に、デスティネーションの色と不透明度が、画素合成スタック３８からポップされる。ただし、色合成メッセージでデスティネーションポップフラグがセットされていない場合には、スタックポインタが「ポップ」動作中に変更されず、その結果スタック３８の最上部からの読み取りになる。
【０１８３】
ソースの色および不透明度をデスティネーションの色および不透明度と組み合わせる方法を、図７Ａないし図７Ｃを参照して以下に説明する。色および不透明度の値は、通常は０から２５５までの範囲の８ビット値として記憶されるが、ここでは説明の目的のために、０から１までの範囲（すなわち正規化されている）とみなす。２画素を合成する目的のために、各画素が２つの領域、すなわち、完全に不透明な領域と完全に透明な領域に分割されるものとみなし、不透明度値は、これら２つの領域の比率の表示であるとみなされる。図７Ａに、図示されない３成分色値と、不透明度値（so）を有するソース画素７０２を示す。ソース画素７０２の影付きの領域は、画素７０２の完全に不透明な部分７０４を表す。同様に、図７Ａの影付きでない領域は、ソース画素７０２のうちで、完全に透明であるとみなされる部分７０６を表す。図７Ｂに、ある不透明度値（do）を有するデスティネーション画素７１０を示す。デスティネーション画素７１０の影付きの領域は、画素７１０の完全に不透明な部分７１２を表す。同様に、画素７１０は、完全に透明な部分７１４を有する。ソース画素７０２およびデスティネーション画素７１０の不透明領域は、組合せのために、互いに直交するとみなされる。これら２つの画素のオーバーレイ７１６を、図７Ｃに示す。対象の３つの領域が存在し、これには、so×（1-do）の面積を有するデスティネーション外ソース７１８、面積so×doを有するソースデスティネーション交差７２０および、（1-so）×doの面積を有するソース外デスティネーション７２２が含まれる。これら３つの領域のそれぞれの色値は、概念上は独立に計算される。デスティネーション外ソース領域７１８は、その色をソース色から直接にとる。ソース外デスティネーション領域７２２は、その色をデスティネーション色から直接にとる。ソースデスティネーション交差領域７２０では、その色をソース色とデスティネーション色の組合せからとる。上で説明した他の動作とは別個の、ソース色とデスティネーション色の組合せの処理は、ラスタ演算と称され、これは、画素合成メッセージからのラスタ演算コードによって指定される、１組の関数のうちの１つである。好ましい実施形態に含まれるラスタ演算の一部を、図１７に示す。
【０１８４】
各関数は、ソース色およびデスティネーション色の対応する色成分の対のそれぞれに適用されて、結果の色において同様の成分が得られる。多くの他の関数が可能である。
【０１８５】
画素合成メッセージからのアルファチャネル演算も考慮されている。アルファチャネル演算は、３つのフラグを使用して実行され、フラグのそれぞれは、ソース画素７０２とデスティネーション画素７１０のオーバーレイ７１６内の対象の領域のうちの１つに対応する。領域のそれぞれについて、領域の不透明度値が形成され、この不透明度値は、アルファチャネル演算で対応するフラグがセットされていない場合には０、それ以外の場合にはその領域の面積である。
【０１８６】
結果の不透明度は、領域の不透明度の合計から形成される。結果の色の各成分は、領域の色と領域の不透明度の対のそれぞれの積の和を結果の不透明度で除算することによって形成される。
【０１８７】
結果の色および不透明度は、画素合成スタック３８にプッシュされる。
【０１８８】
６．０  画素出力モジュール
画素出力モジュール８００の動作を以下に説明する。着信メッセージは、画素出力ＦＩＦＯから読み取られ、これには、画素出力メッセージ、反復メッセージおよびスキャンラインの終りメッセージが含まれ、順番に処理される。
【０１８９】
画素出力メッセージを受け取った時に、画素出力モジュール８００は、画素を記憶し、その画素をその出力に転送する。反復メッセージを受け取った時には、最後に記憶した画素が、反復メッセージからのカウントによって指定される回数だけ、出力８９８に転送される。スキャンラインの終りメッセージを受け取った時には、画素出力モジュール８００は、そのメッセージをその出力に渡す。
【０１９０】
出力８９８は、必要に応じて、画素画像データを使用する装置に接続することができる。このような装置には、ビデオ表示ユニットまたはプリンタなどの出力装置、または、ハードディスク、ラインストア、バンドストアまたはフレームストアを含む半導体ＲＡＭなどのメモリ記憶装置、または、コンピュータネットワークが含まれる。
【０１９１】
多数のレベルにわたるオブジェクトの合成も、本明細書に記載の方法の外挿によって可能であることを、当業者は了解するであろう。さらに、示されたさまざまな操作を、フレームストアベースシステムおよび他のスタックベース、ラインベースまたはバンドベースの合成システムを含む異なる合成パラダイムで使用することができることも諒解されるであろう。
【０１９２】
前述から、本明細書に記載の方法および装置が、レンダリング処理中の画素画像データの中間記憶を必要とせずに、洗練されたグラフィック記述言語が必要とする機能性のすべてを備えたグラフィックオブジェクトのレンダリングを提供することは、明白であろう。
【０１９３】
産業上の利用性
本発明の実施形態がコンピュータグラフィックス及び印刷産業に適用可能であることが上述の説明より明らかである。
【０１９４】
前述は、本発明の一つの或いはいくつかの実施形態を記述したのみであり、それらは説明のために用いられるもので限定的なものではなく、それらに対して本発明の趣旨および範囲を逸脱せずに改造及び変更を行なうことができる。
【図面の簡単な説明】
【図１】好ましい実施形態を組み込まれるコンピュータシステムの概略ブロック図である。
【図２】好ましい実施形態の機能データフローを示すブロック図である。
【図３】好ましい実施形態の画素シーケンシャルレンダリング装置と、関連する表示リストおよび一時ストアの概略ブロック図である。
【図４】図２のエッジ処理モジュールの概略機能図である。
【図５】図２の優先順位決定モジュールの概略機能図である。
【図６】図２の塗潰しデータ決定モジュールの概略機能図である。
【図７】ソースとデスティネーションの間の画素の組合せを示す図である。
【図８】好ましい実施形態の演算を説明するための例として使用される、オブジェクトが２つある画像を示す図である。
【図９】図８のオブジェクトのベクトルエッジを示す図である。
【図１０】図８の画像の複数のスキャンラインのレンダリングを示す図である。
【図１１】図８の画像のエッジレコードの配置を示す図である。
【図１２Ａ】図１０の例のために図４の配置によって実施されるエッジ更新ルーチンを示す図である。
【図１２Ｂ】図１０の例のために図４の配置によって実施されるエッジ更新ルーチンを示す図である。
【図１２Ｃ】図１０の例のために図４の配置によって実施されるエッジ更新ルーチンを示す図である。
【図１２Ｄ】図１０の例のために図４の配置によって実施されるエッジ更新ルーチンを示す図である。
【図１２Ｅ】図１０の例のために図４の配置によって実施されるエッジ更新ルーチンを示す図である。
【図１２Ｆ】図１０の例のために図４の配置によって実施されるエッジ更新ルーチンを示す図である。
【図１２Ｇ】図１０の例のために図４の配置によって実施されるエッジ更新ルーチンを示す図である。
【図１２Ｈ】図１０の例のために図４の配置によって実施されるエッジ更新ルーチンを示す図である。
【図１２Ｉ】図１０の例のために図４の配置によって実施されるエッジ更新ルーチンを示す図である。
【図１２Ｊ】図１０の例のために図４の配置によって実施されるエッジ更新ルーチンを示す図である。
【図１３Ａ】Ｘ座標の大きな変化がスピル条件にどのように寄与し、それらがどのように処理されるかを示す図である。
【図１３Ｂ】Ｘ座標の大きな変化がスピル条件にどのように寄与し、それらがどのように処理されるかを示す図である。
【図１３Ｃ】Ｘ座標の大きな変化がスピル条件にどのように寄与し、それらがどのように処理されるかを示す図である。
【図１３Ｄ】Ｘ座標の大きな変化がスピル条件にどのように寄与し、それらがどのように処理されるかを示す図である。
【図１３Ｅ】Ｘ座標の大きな変化がスピル条件にどのように寄与し、それらがどのように処理されるかを示す図である。
【図１４】２つの従来技術のエッジ記述フォーマットと、好ましい実施形態で使用されるエッジ記述フォーマットを比較するための図である。
【図１５】いくつかの合成演算の結果を示す図である。
【図１６】図２のエッジレコード格納部における格納のための、エッジレコードの模式的なテーブルを示す図である。
【図１７】好適な実施形態において用いられるラスタ演算子のいくつかに関するテーブルを示す図である。
【図１８】エクスプレッションツリーとして示される単純な合成式と対応する図を示す図である。
【図１９】オブジェクトＡ，Ｂ，Ｃ及びＤ、及び対応する命令リストに関して、一連のPorterとDuffの合成操作を実現するための典型的な表現ツリーを示す図である。
【図２０】オブジェクトＣが有効な場合の図１９の表現ツリーと対応する命令リストを示す図である。
【図２１】図５に示したレベルアクティベーションテーブル生成部によって生成される、図２０の表現ツリーに関するレベルアクティベーションテーブルを示す図である。
【図２２】図５に示したレベルアクティベーションテーブルの更新モジュールにおいて使用される論理回路を示す図である。
【図２３】オブジェクトＣが有効である、図２０の表現ツリーのための更新されたレベルアクティベーションテーブルを示す図である。
【図２４】図５に示したレベルアクティベーションテーブルの更新モジュールにおいて使用される論理回路の別の具体例を示す図である。
【図２５】図２４の更なる実施形態と共に用いるためのレベルアクティベーションテーブルを示す図である。
【図２６】ＩＮ合成操作のための真理値表を示す図である。
【図２７】ＣＬＩＰ  ＩＮ合成操作のための真理値表を示す図である。
【図２８】ＯＵＴ合成操作のための真理値表を示す図である。
【図２９】ＣＬＩＰ  ＯＵＴ合成操作のための真理値表を示す図である。
【図３０】左側のブランチを描画されたページに合成するノードを支援す表現ツリーの典型的な例を示す図である。
【図１】
0004630482.tif 000008
【図２】
0004630482.tif 000009
【図３】
0004630482.tif 000010
【図４】
0004630482.tif 000011
【図５】
0004630482.tif 000012
【図６】
0004630482.tif 000013
【図７】
0004630482.tif 000014
【図８】
0004630482.tif 000015
【図９】
0004630482.tif 000016
【図１０】
0004630482.tif 000017
【図１１】
0004630482.tif 000018
【図１２Ａ】
0004630482.tif 000019
【図１２Ｂ】
0004630482.tif 000020
【図１２Ｃ】
0004630482.tif 000021
【図１２Ｄ】
0004630482.tif 000022
【図１２Ｅ】
0004630482.tif 000023
【図１２Ｆ】
0004630482.tif 000024
【図１２Ｇ】
0004630482.tif 000025
【図１２Ｈ】
0004630482.tif 000026
【図１２Ｉ】
0004630482.tif 000027
【図１２Ｊ】
0004630482.tif 000028
【図１３Ａ】
0004630482.tif 000029
【図１３Ｂ】
0004630482.tif 000030
【図１３Ｃ】
0004630482.tif 000031
【図１３Ｄ】
0004630482.tif 000032
【図１３Ｅ】
0004630482.tif 000033
【図１４】
0004630482.tif 000034
【図１５】
0004630482.tif 000035
【図１６】
0004630482.tif 000036
【図１７】
0004630482.tif 000037
【図１８】
0004630482.tif 000038
【図１９】
0004630482.tif 000039
【図２０】
0004630482.tif 000040
【図２１】
0004630482.tif 000041
【図２２】
0004630482.tif 000042
【図２３】
0004630482.tif 000043
【図２４】
0004630482.tif 000044
【図２５】
0004630482.tif 000045
【図２６】
0004630482.tif 000046
【図２７】
0004630482.tif 000047
【図２８】
0004630482.tif 000048
【図２９】
0004630482.tif 000049
【図３０】
0004630482.tif 000050