(57)【特許請求の範囲】
【請求項１】
複数のオブジェクトと、前記オブジェクトを合成演算するための演算子からなるツリーとに従って形成すべき画像を作成する方法であって、
前記ツリーの部分式ごとに、前記合成演算に従い、前記ツリーのリーフから上向きにルートの方へ、前記オブジェクトのアウトラインまたはその一部のうちの少なくとも１つにより定義されるアクティブ領域を求めるステップと、
前記ツリーの各節点ごとに、前記ツリーのルートから下向きにリーフの方へ、各部分式のアクティブ領域およびその親のクリップ領域との共通集合に基づいて再帰的に、部分式の画素が最終的な画像に寄与するクリップ領域を求めるステップと、
前記クリップ領域と前記アクティブ領域の共通集合に基づいて、前記ツリーの各節点ごとに、その節点に関連する演算についてスタック演算を生成する必要がある有効領域を求めるステップと、
対応する合成演算を、前記有効領域に実質的に適用して画像を形成するステップと
を有することを特徴とする方法。
【請求項２】
前記アクティブ領域を求めるステップでは、前記部分式の演算子により、該演算子のオペランドであるオブジェクトのアクティブ領域のいずれか一方、又はそれらの合併集合、又はそれらの共通集合を、前記部分式のアクティブ領域として求めることを特徴とする請求項１に記載の方法。
【請求項３】
前記アクティブ領域を求めるステップに先行して前記オブジェクトの不透明領域を判定するステップを更に有し、
前記アクティブ領域を求めるステップでは、前記オブジェクトとして、当該オブジェクトの不透明領域を用いてアクティブ領域を求めることを特徴とする請求項１又は２に記載の方法。
【請求項４】
複数のオブジェクトと、前記オブジェクトを合成演算するための演算子からなるツリーとに従って形成すべき画像を作成する装置であって、
前記ツリーの部分式ごとに、前記合成演算に従い、前記ツリーのリーフから上向きにルートの方へ、前記オブジェクトのアウトラインまたはその一部のうちの少なくとも１つにより定義されるアクティブ領域を求める手段と、
前記ツリーの各節点ごとに、前記ツリーのルートから下向きにリーフの方へ、各部分式のアクティブ領域およびその親のクリップ領域との共通集合に基づいて再帰的に、部分式の画素が最終的な画像に寄与するクリップ領域を求める手段と、
前記クリップ領域と前記アクティブ領域の共通集合に基づいて、前記ツリーの各節点ごとに、その節点に関連する演算についてスタック演算を生成する必要がある有効領域を求める手段と、
対応する合成演算を、前記有効領域に実質的に適用して画像を形成する手段と
を有することを特徴とする装置。
【請求項５】
前記アクティブ領域を求める手段は、前記部分式の演算子により、該演算子のオペランドであるオブジェクトのアクティブ領域のいずれか一方、又はそれらの合併集合、又はそれらの共通集合を、前記部分式のアクティブ領域として求めることを特徴とする請求項４に記載の装置。
【請求項６】
前記アクティブ領域を求める手段に先行して前記オブジェクトの不透明領域を判定する手段を更に有し、
前記アクティブ領域を求める手段は、前記オブジェクトとして、当該オブジェクトの不透明領域を用いてアクティブ領域を求めることを特徴とする請求項４又は５に記載の装置。
【請求項７】
複数のオブジェクトと、前記オブジェクトを合成演算するための演算子からなるツリーとに従って形成すべき画像を作成する装置としてコンピュータを機能させるためのプログラムが記録されたコンピュータで読み取り可能な記録媒体であって、
前記ツリーの部分式ごとに、前記合成演算に従い、前記ツリーのリーフから上向きにルートの方へ、前記オブジェクトのアウトラインまたはその一部のうちの少なくとも１つにより定義されるアクティブ領域を求める手段と、
前記ツリーの各節点ごとに、前記ツリーのルートから下向きにリーフの方へ、各部分式のアクティブ領域およびその親のクリップ領域との共通集合に基づいて再帰的に、部分式の画素が最終的な画像に寄与するクリップ領域を求める手段と、
前記クリップ領域と前記アクティブ領域の共通集合に基づいて、前記ツリーの各節点ごとに、その節点に関連する演算についてスタック演算を生成する必要がある有効領域を求める手段と、
対応する合成演算を、前記有効領域に実質的に適用して画像を形成する手段と
してコンピュータを機能させるためのプログラムが記録されたコンピュータで読み取り可能な記録媒体。
【請求項８】
前記アクティブ領域を求める手段は、前記部分式の演算子により、該演算子のオペランドであるオブジェクトのアクティブ領域のいずれか一方、又はそれらの合併集合、又はそれらの共通集合を、前記部分式のアクティブ領域として求めることを特徴とする請求項７に記載のプログラムが記録されたコンピュータで読み取り可能な記録媒体。
【請求項９】
前記アクティブ領域を求める手段に先行して前記オブジェクトの不透明領域を判定する手段としてコンピュータを更に機能させるためのプログラムであって、
前記アクティブ領域を求める手段は、前記オブジェクトとして、当該オブジェクトの不透明領域を用いてアクティブ領域を求めることを特徴とする請求項７又は８に記載のプログラムが記録されたコンピュータで読み取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、静止ピクチャ形式とビデオ画像形式の両方のコンピュータ生成画像の作成に関し、詳細には、複数のグラフィカルオブジェクトを合成することによって構成された画像を作成する効率的なプロセスおよび装置に関する。
【０００２】
【従来の技術】
コンピュータ生成画像は通常、最終画像を作成するように合成されレンダリングされた多数の異なる構成要素またはグラフィカルオブジェクトで構成される。各グラフィカルオブジェクトは一般に、フィルタイプおよび１組のアウトラインとして表される。グラフィカルオブジェクトは、合成演算を使用してそれらをページ上で組み合わせることによってレンダリングすることができる。一般に、グラフィカルオブジェクトの表現の一部として「不透明度チャネル」（「マット」、「アルファチャネル」、あるいは単に「不透明度」とも呼ぶ）も使用されている。不透明度チャネルは、各要素の透明性に関する情報を含む。不透明度チャネルは通常、色の各インスタンスと共に記憶され、したがって、たとえば不透明度を有する画素ベースの画像は、各画素の表現の一部として不透明度値を記憶する。このように、各グラフィカルオブジェクトは、画像領域全体を占有するオブジェクトとして解釈することができ、したがって、グラフィカルオブジェクトのアウトラインは、その外側でオブジェクトが完全に透明である領域を定義する。この領域をオブジェクトの「アクティブ領域」と呼ぶ。明白な不透明度チャネル情報を含まないグラフィカルオブジェクトは通常、オブジェクトのアウトライン内で完全に不透明であると理解され、このようなアウトラインの外側では完全に透明であると仮定される。
【０００３】
画像をその構成要素に関して体系的に表し、後で行われるレンダリングを容易にする手段として「式ツリー」がある。式ツリーは通常、リーフ節点、１分節点、２分節点を含む複数の節点を含む。より高度な節点または代替定義を使用することもできる。リーフ節点は、式ツリーの最外節点であり、子孫節点がなく、画像のプリミティブ構成要素を表す。１分節点は、１分演算子の下方にあるツリーの部分から得た画素データを修正する演算を表す。１分節点には、色変換や畳み込み（ブラーリングなど）などの演算が含まれる。２分節点は通常、左部分ツリーおよび右部分ツリーに枝分かれし、各部分ツリーはそれ自体が、少なくとも１つのリーフ分節点を含む式ツリーである。２分節点は、その子の画素データを組み合わせて単一の結果を形成する演算を表す。たとえば、２分節点は、ｏｖｅｒ、ｉｎ、ｏｕｔ、ａｔｏｐ、アルファＸＯＲなどの標準合成演算子のうちの１つでよい。標準合成演算子およびその他の演算子の例を図２に示す。Ｐｏｒｔｅｒ−Ｄｕｆｆ合成演算子によって表される合成演算は、不透明度を含む算術演算またはビットごとの演算であり、グラフィカルオブジェクトの色の成分値に対して実行される。
【０００４】
上記の種類の節点のうちのいくつかを組み合わせて式ツリーを形成することができる。この一例を図１に示す。図１に示す式ツリーの左側の結果は、色変換（Ｃｏｎｖｅｒｓｉｏｎ）され、スプライン境界（Ｐａｔｈ）にクリッピングされた（Ｉｎ）画像（画像１）として解釈することができる。この構造が第２の画像（画像２）と合成される。
【０００５】
グラフィカルオブジェクトのアクティブ領域は、それ自体があるサイズのものでよいが、最終画像で完全に可視である必要はなく、あるいはアクティブ領域の一部のみが最終画像に対する効果を有すればよい。たとえば、あるサイズの画像をディスプレイ上に表示すると仮定する。画像の左上隅部のみが表示装置上に表示されるように画像を配置した場合、画像の残りの部分は表示されない。したがって、表示装置上に表示される最終画像は、画像の可視部分を含み、このような場合の不可視部分をレンダリングする必要はない。
【０００６】
そのほかに、オブジェクトのアクティブ領域の一部のみが効果を有するのは、その部分が他のオブジェクトによって曖昧にされた場合である。たとえば、表示（またはレンダリング）すべき最終画像は１つまたは複数の不透明なグラフィカルオブジェクトを含むことができ、いくつかのグラフィカルオブジェクトは他のグラフィカルオブジェクトを曖昧にする。したがって、曖昧にされたオブジェクトは最終画像に対する効果を有さない。
【０００７】
２つの従来型のレンダリングモデルに「フレームバッファレンダリング」および「画素順次レンダリング」が含まれる。従来型のフレームバッファレンダリングは、複数のオブジェクトを一度に１つずつレンダリングしてフレームバッファに格納する「ペインターズアルゴリズム」に基づくレンダリングである。オブジェクトの境界内のあらゆる画素について合成演算が実行される。単一フレームバッファ手法は、透明度を使用する合成演算からなる任意の式をレンダリングするほど高度な手法ではない。透明度を使用する合成演算からなる任意の式をレンダリングするうえで余分のフレームバッファが必要になることがある。この余分なフレームバッファは中間結果を格納するために必要である。
【０００８】
従来型のフレームバッファで使用される「オブジェクト順次レンダリング」に対する画素順次レンダリングでは、単一の画素を作成するのに必要なすべての合成演算が実行された後に次の画素に移る。このような従来型の方法では、実際の画素演算が非常に簡単であるので、毎秒１５フレームを超えるオーダーの対話型フレームレートを実現することができる。したがって、従来型のシステムは、複雑なコードを必要とせずに、受容できるフレームレートが得られるほど高速である。しかし、このことが、複雑な式ツリーからなる合成環境に当てはまらないことは確かである。これは、合成の画素当たりコストが極めて高額になるからである。複雑な合成式の場合、画素合成演算が冗長になり、レンダリング速度が低下する可能性がある。これは、通常、画像が８ビットアルファチャネルだけでなく２４ビット色でレンダリングされ、したがって画素当たり３２ビットになるからである。したがって、式ツリーの各合成演算子は４つのチャネルのそれぞれに対処する必要がある。
【０００９】
【発明が解決しようとする課題】
従来型の方法を使用する従来技術の方法では問題が生じる。このような方法は、各画素を計算するのに必要な１組の合成演算を評価する画素当たりコストが過度に高いので非常に非効率的である。さらに、画素順次レンダリングは、画素をレンダリングするために使用される特定の合成演算が、合成中のオブジェクトの境界の外側にある画素に影響を与えないという仮定の下で正しく働くように設計される。この仮定は、すべての合成演算に当てはまるわけではない。たとえば、２つのグラフィックオブジェクトＡおよびＢが与えられた場合、合成式「Ａ  ｒｉｎ  Ｂ」は、オブジェクトＡの境界の外側にある画素を透明にする。上記の仮定が成立しないこの種の合成式では、合成命令を生成する際に問題が生じる。
【００１０】
【課題を解決するための手段】
本発明の目的は、複数の構成要素を合成することによって合成された画像を作成する方法を提供することによって、前述の方法の１つまたは複数の欠陥をほぼ解消または改善することである。
【００１１】
本発明の一態様によれば、複数のオブジェクトと、前記オブジェクトを合成演算するための演算子からなるツリーとに従って形成すべき画像を作成する方法であって、
前記ツリーの部分式ごとに、前記合成演算に従い、前記ツリーのリーフから上向きにルートの方へ、前記オブジェクトのアウトラインまたはその一部のうちの少なくとも１つにより定義されるアクティブ領域を求めるステップと、
前記ツリーの各節点ごとに、前記ツリーのルートから下向きにリーフの方へ、各部分式のアクティブ領域およびその親のクリップ領域との共通集合に基づいて再帰的に、部分式の画素が最終的な画像に寄与するクリップ領域を求めるステップと、
前記クリップ領域と前記アクティブ領域の共通集合に基づいて、前記ツリーの各節点ごとに、その節点に関連する演算についてスタック演算を生成する必要がある有効領域を求めるステップと、
対応する合成演算を、前記有効領域に実質的に適用して画像を形成するステップと
を有することを特徴とする方法が提供される。
【００２３】
【発明の実施の形態】
任意の１つまたは複数の図面で、同じ参照符号を有するステップおよび／または特徴を参照する場合、相反するものが表れるまでは、このようなステップおよび／または特徴は同じものを説明するためのものである。
【００２４】
好適な実施形態は、画像を作成する方法である。本好適な実施形態は、所与の合成式を評価するのに必要な画素演算の数が最小限に抑えられるように式を最適に評価するために使用される「レベル活性化テーブル」と呼ばれるレベルのテーブルを使用することができる。好適な実施形態は、好ましくは、合成演算を実行する必要がある最小領域を判定し、この領域を使用してレベル活性化テーブルを作成することができ、このテーブルにおいて、冗長な画素演算および／または誤った画素演算を回避するために演算にクリッピングが適用される。好適な実施形態は、好ましくは、後述の合成モデル（図１１参照）で使用され、このモデルでは、スタックマシン（図示せず）および関連する合成スタック３８を使用してオブジェクトがページ上で合成される。スタック３８は、ｐｕｓｈ、ｐｕｌｌ、ｐｏｐなどの標準スタック演算を使用して処理することができる。スタックマシンに対する命令はレベル活性化テーブル３４から取り出される。レベル活性化テーブル３００の例を図３に示す。各レベルは通常、グラフィカルオブジェクトを表すと共に、オブジェクト関連フィルデータと、その下方に並べられたレベルから得たデータとの合成を制御するグラフィックス演算とを表す。レベル活性化テーブル３００の合成は、並べられた最下位レベルから最高レベルまで進行する。各レベルで、レベル活性化テーブルに指定された演算が実行され、結果が合成スタック上にプッシュされる。本好適な実施形態では、式は変換されない。しかし、式を好ましい実施形態の方法に適用する前に資源の使用度を最小限に抑えるように簡略化し事前処理することができる。
【００２５】
図９は、コンピュータグラフィックオブジェクト画像のレンダリングし表示するように構成されたコンピュータシステム１を概略的に示す。システムは、システムランダムアクセスメモリ（ＲＡＭ）３に関連するホストプロセッサ２を含み、システムランダムアクセスメモリ３は非揮発性ハードディスクまたは同様な装置５、および揮発性半導体ＲＡＭ４を含むことができる。システム１は、通常半導体ＲＯＭ７上に設けられ、多くの場合、コンパクトディスク装置（ＣＤ  ＲＯＭ）８によって補助することができるシステム読取り専用メモリ（ＲＯＭ）６も含む。システム１は、共にラスタ的に動作するビデオディスプレイユニット（ＶＤＵ）やプリンタなど、画像を表示するある種の手段１０を組み込むこともできる。
【００２６】
システム１の前述の構成要素は、バスシステム９を介して相互接続され、ＩＢＭ  ＰＣ／ＡＴ型パーソナルコンピュータや、そのようなコンピュータから進化した構成、すなわちＳｕｎ  Ｓｐａｒｃｓｔａｔｉｏｎなど、当技術分野でよく知られているコンピュータシステムの通常の動作モードで動作することができる。
【００２７】
図９に示すように、画素順次レンダリング装置２０は、バス９に接続され、好適な実施形態では、バス９を介してシステム１から命令およびデータが供給されるグラフィックオブジェクトベースの記述から得られる画素ベースの画像の順次レンダリングを行うように構成される。好ましくは、レンダリング装置２０は、それと連携する通常は半導体ＲＡＭで形成された専用レンダリング記憶装置３０を有しているけれども、装置２０は、システムＲＡＭ３を使用してオブジェクト記述をレンダリングすることができる。
【００２８】
次に図１０を参照すると、好適な実施形態の機能データ流れ図が示されている。図１０の機能流れ図はオブジェクトグラフィック記述１０００から始まる。オブジェクトグラフィック記述１０００は、ホストプロセッサ２によって生成され、かつ／またはシステムＲＡＭ３内の適当な場所に記憶されるか、あるいはシステムＲＯＭ６から得られるグラフィックオブジェクトのパラメータを適当な方法で記述するために使用され、かつ画素ベースの画像をレンダリングするために画素順次レンダリング装置２０によって解釈することができる。たとえば、オブジェクトグラフィック記述１０００には、ディスプレイ上の１つの点から他の点へ横切る直線エッジ（単純なベクトル）、または直交線を含む複数のエッジによって２次元オブジェクトが定義される直交エッジフォーマットを含むいくつかのフォーマットのエッジを有するオブジェクトを組み込むことができる。連続する曲線によってオブジェクトが定義される他のフォーマットも適切であり、このようなフォーマットには、乗算を実行する必要なしに単一の出力空間で二次ベースの曲線をレンダリングできるようにするいくつかのパラメータによって単一のカーブを記述できる二次多項フラグメントを含めることができる。三次スプラインなど他のデータフォーマットを使用することもできる。オブジェクトは多数の異なるエッジタイプの混合物を含むことができる。通常、すべてのフォーマットに共通するのは、各線（直線でも曲線でもよい）の開始位置および終了位置の識別子であり、通常、各フォーマットは、曲線をレンダリングすることのできる特定の出力空間を定義するスキャンライン番号によって識別される。グラフィックシステム１は、レンダリングすべきグラフィックオブジェクトを記述するのに必要なデータを識別した後、表示リスト生成ステップ１００１を実行する。
【００２９】
表示リスト生成ステップ１００１は好ましくは、取り付けられたＲＯＭ６およびＲＡＭ３を有するホストプロセッサ２上で実行されるソフトウェアモジュールとして実装される。表示リスト生成ステップ１００１は、周知のグラフィック記述言語、グラフィックライブラリコール、または他のアプリケーション特有フォーマットのうちの任意の１つまたは複数で表されたオブジェクトグラフィックス記述を表示リストに変換する。表示リストは通常、表示リスト記憶１００３に書き込まれ、表示リスト記憶１００３は一般にＲＡＭ４内に形成されるが、レンダリング記憶３０内に形成することもできる。図１１を見るとわかるように、表示リスト記憶１００３はいくつかの構成要素、たとえば、命令ストリーム１１０１や、エッジ情報１１０３や、必要に応じてラスタ画像画素データ１１０５を含むことができる。命令ストリーム１１０１は、任意の特定の画像中の所望の特定のグラフィックオブジェクトをレンダリングするために画素順次レンダリング装置２０によって読み取るべき命令として解釈できる符号を含む。
【００３０】
表示リスト記憶１００３は画素順次レンダリング装置２０によって読み取られ、画素順次レンダリング装置２０は通常、集積回路として実装される。画素順次レンダリング装置２０は表示リストをラスタ画素ストリームに変換し、このラスタ画素ストリームを他の装置、たとえば、プリンタや、ディスプレイや、メモリ記憶に転送することができる。
【００３１】
好適な実施形態では画素順次レンダリング装置２０を集積回路として説明するが、この装置は、ホストプロセッサ２などの汎用処理ユニット上で実行できる同等なソフトウェアモジュールとして実装することができる。このソフトウェアモジュールは、ディスク装置やコンピュータネットワークなどコンピュータ可読媒体を介してユーザに転送することのできるコンピュータプログラム製品の一部を形成することができる。
【００３２】
図１１は、画素順次レンダリング装置２０、表示リスト記憶１００３、および一時レンダリング記憶３０の構成を示す。画素順次レンダ装置２０の処理ステージは、命令実行装置１２００、エッジ処理モジュール１２０１、優先順位決定モジュール１２０３、フィルカラー決定モジュール１２０５、画素合成モジュール１２０７、および画素出力モジュール１２０９を含む。処理演算では一時記憶３０が使用され、一時記憶３０は、表示リスト記憶１００３と同じ装置（たとえば、磁気ディスクや半導体ＲＡＭ）を共用することも、あるいは速度を最適化するために個々の記憶として実装することもできる。エッジ処理モジュール１２０１は、エッジ記録記憶３２を使用して、スキャンライン同士の間で搬送されるエッジ情報を保持する。優先順位決定モジュール１２０３は、スキャンラインがレンダリングされる間、各優先順位に関する情報、およびエッジ交差に対する各優先順位の現在の状態を、優先順位特性レベル活性化テーブル３４を使用して保持する。フィルカラー決定モジュール１２０５は、特定の位置での特定の優先順位のフィルカラーを決定するのに必要な情報をフィルデータテーブル３６を使用して保持する。画素合成モジュール１２０７は、値を決定するときに複数の優先順位の色が必要になる出力画素を決定する間、画素合成スタック３８を使用して中間結果を保持する。
【００３３】
上記で詳しく説明した表示リスト記憶１００３およびその他の記憶３２−３８は、ＲＡＭまたはその他のデータ記憶技法で実装することができる。
【００３４】
図１１の実施形態に示す処理ステップは処理パイプライン２２の形をとる。好適な実施形態によれば、画像データの様々な部分に対してパイプラインの各モジュールを同時に実行することができ、後述のように、各モジュールの間でメッセージをわたすことができる。他の実施形態では、後述のメッセージは、制御の下流側モジュールへの同期転送の形をとることができ、この場合、上流側の処理は、下流側モジュールがメッセージの処理を完了するまで中止される。
【００３５】
命令実行装置１２００は、命令ストリーム１１０１から命令を読み取って処理し、この命令をメッセージとしてフォーマットし、このメッセージが出力３９８を介してパイプライン２２内の他のモジュール１２０１、１２０３、１２０５、および１２０７に転送される。セット優先順位データメッセージ、セットフィルデータメッセージ、エッジ交差メッセージ、およびエンドオブスキャンラインメッセージを含めることのできる着信メッセージは、エッジ処理モジュール１２０１および優先順位決定モジュール１２０３を通過する。エッジ交差メッセージは、特定のスキャンラインについての順序でエッジ処理モジュール１２０１から渡され、レベル活性化テーブル３４にロードされる。レベル活性化テーブル３４は優先順位決定モジュールによって優先順位順に構成される。テーブル３４の内容は、メッセージとして、画素を生成するために各フィルカラー決定モジュール１２０５に渡され、合成演算のために画素合成モジュール１２０７に渡される。
【００３６】
フィルオーダ決定モジュール１２０５は、反復メッセージ、色合成メッセージ（すなわち、ラスタ演算およびアルファチャネル演算）、エンドオブピクセルメッセージ、およびエンドオブスキャンラインメッセージを生成し、これらのメッセージを画素合成モジュール１２０７に渡し、画素合成モジュール１２０７がこれらのメッセージを順次処理する。画素合成モジュール７００は、色合成メッセージを受け取ると通常、一般に、色合成メッセージのラスタ演算およびアルファチャネル演算に従って、色合成メッセージの色不透明度情報と、画素合成スタック３８からポップされた色および不透明度と組み合わせる。画素合成モジュール７００は次いで、結果を画素合成スタック３８上にプッシュする。
【００３７】
好適な実施形態に従ってコンピュータグラフィックオブジェクトをレンダリングするように構成されたコンピュータシステム１については、豪州特許出願第４７５０９／９９号および対応する米国特許出願第０９／３９２７４１号に詳しく記載されている。
【００３８】
合成スタックを構築する際、実行される合成演算にかかわらず、演算は、以下に示すように、ソース（Ｓ）およびデスティネーション（Ｄ）の４つのケース（すなわち、バイナリ演算の場合）あるいは活動の領域に帰着される。
【００３９】
（１）（Ａ）Ｓアクティブ、（Ｂ）Ｄアクティブ、
（２）（Ａ）Ｓアクティブ、（Ｂ）Ｄアクティブ、
（３）（Ａ）Ｓアクティブ、（Ｂ）Ｄアクティブ、および
（４）（Ａ）Ｓイナクティブ、（Ｂ）Ｄアクティブ。
【００４０】
ケース４では常に、演算を実行する必要がなく（ＮＯＰ）、したがって、２分木にはバイナリレベルの３つの異なる組合せが存在する。この概念を３分木、４分木、およびそれよりも高いオーダーの木に拡張できることは当業者には明らかである。
【００４１】
したがって、（２分木の）合成スタック３８を構築する際、上記で識別した３つの演算のうちの１つをスタック３８で実施する必要がある。さらに、スタック内の各オブジェクトに関連するそれぞれの異なる演算は、レベル活性化テーブル３４内でそのオブジェクトの下方にあるものに依存する。ペインターズアルゴリズムで行われるような簡単なＯＶＥＲ演算を使用するオブジェクトのレンダリングの場合、上記の依存性にはまったく問題がない。しかし、他の合成演算の場合、その合成演算のオペランドの活動に応じてスタック演算を変更する必要がある。この問題は、スタック演算をもたらすレベルをクリッピングすることによって解消することができる。しかし、各レベルに加えられるクリップの数が急激に増加し、スタック演算の処理が困難になる可能性がある。好適な実施形態は、式を画像の作成について評価するのに必要な画素演算の数が最小限に抑えられるように最適レベル活性化テーブルをコンパイルする方法を提供する。
【００４２】
図１２は、本発明の好適な実施形態による画像を作成する方法を示す流れ図である。画像は、画像の合成式を表す式ツリーに従ってグラフィカルオブジェクトを合成することによって形成される。式ツリー内の各節点は、最初の式の部分式に対応し、ツリーのルート節点は、画像の全体的な式を表す。プロセスはステップ１２０１で始まり、合成式の各部分式ごとにアクティブ領域が求められる。部分式のアクティブ領域は、部分式の結果が非透明として分類される最小領域を表す。節点のアクティブ領域は、その節点のオペランド（すなわち、部分式）のアクティブ領域と、その節点によって表される演算の種類とに依存する。前述のように、オブジェクトのアクティブ領域は、そのオブジェクトのアウトラインの内側の領域として定義される。本発明の実施形態によるアクティブ領域の計算について以下に詳しく説明する。次のステップ１２０３で、現在の合成式の各部分式ごとに他の領域が求められる。この領域は、現在の部分式が現われる各部分式および／または式のアクティブ領域の共通集合として算出される。この領域は、部分式内の画素が最終的な表示画像に寄与する領域を表す。この領域を部分式のクリッピング領域と呼ぶ。本発明の実施形態によるこの領域の計算について以下に詳しく説明する。プロセスは次のステップ１２０５に進み、式ツリーの各節点ごとに有効領域が求められる。有効領域は、この節点のオペランドに関連するアクティブ領域およびこの節点に関連する他の領域の少なくとも１つの特性に実質的に依存する。算出される各有効領域は、対応するレンダリング演算を有し、したがって、レンダリング演算は合成演算とスタック演算の両方を含む。有効領域は、その節点に関連する演算についてスタック演算を生成する必要がある領域を表す。本発明の実施形態による有効領域の計算について以下に詳しく説明する。次のステップ１２０７で、対応するレンダリング演算が有効領域に実質的に適用され、画像が作成される。
【００４３】
本発明の一実施形態によれば、ステップ１２０７は、有効領域および対応するレンダリング演算を、複数のレベルを含むレベル活性化テーブルにマッピングするサブステップを含む。本発明の実施形態によるレベル活性化テーブルについて以下に説明する。レベルは、式ツリー内の各節点ごとにレベル活性化テーブル内に作成され、各レベルをその有効領域にクリッピングする必要に応じて追加のクリップレベルが作成される。本発明の実施形態によれば、演算の左オペランドである節点をその演算と組み合わせ単一のレベルを得ることができる。
【００４４】
図４は、本発明の実施形態による、画像を作成するために所与の合成式を最適に評価するように最適レベル活性化テーブルをコンパイルする方法の流れ図である。この方法はステップ４０２から開始し、所与の合成式が「プリミティブ」（形式ｐｕｓｈ  Ａの１つの「レベル」で表される）であるかどうかを判定する検査が行われる。処理はステップ４０４に進み、式がプリミティブではなく「コンプレックス」（複数のアクティブ領域で表される）である場合、演算の左オペランドがプリミティブであるかどうかを判定する検査が行われる。好適な合成モデルでは、演算の左オペランド（すなわち、ソースフィルデータ）は現在のレベルから取り出され、右オペランド（すなわち、デスティネーションフィルデータ）はスタックの最上レベルからポップされる。次のステップ４０６で、式の左オペランドがプリミティブではない場合、本発明の実施形態によるコンプレックス左オペランドのレベル活性化テーブルコンパイル規則を使用して、左オペランドの有効領域が算出される（添付の図１８参照）。有効領域およびレベル活性化テーブルコンパイル規則については以下に詳しく説明する。処理はステップ４０８に進み、所与の合成式の最適レベル活性化テーブルに「ｐｏｐ」レベルが加えられる。ｐｏｐレベルとは、レベルの明示的な一部ではなく、最適レベル活性化テーブルを合成する間に左オペランドをスタックからポップさせる演算を表すレベルである。次のステップ４１０で、有効領域が「コンプレックス」であるかどうかを判定する検査が行われる。この場合のコンプレックスは、複数のオブジェクト境界を含む有効領域を意味する。有効領域がコンプレックスである場合、ステップ４１２で、クリッピングレベル、および必要に応じて重複レベルが、合成式の最適レベル活性化テーブルに加えられる。重複レベルを加える必要があるのは、演算の有効領域がコンプレックスである場合だけである。加えてクリッピング領域に関するブール演算の論理和形式で合併集合が使用される場合も、クリッピングされるレベルを重複する必要がある。左オペランドのクリッピング領域は、この左オペランドが含まれる合成式を評価できるようにするためにこの左オペランドを評価する必要がある最小領域である。したがって、最適レベル活性化テーブルにクリッピングレベルが加えられ、合成中の不要な画素演算が回避される。クリッピング領域およびクリッピングレベルについては以下に詳しく説明する。処理はステップ４１４に進み、クリッピングレベルを加える必要がない場合、あるいは必要なクリッピングレベルおよび重複レベルを最適レベル活性化テーブルに加えた後、フローチャートによって概略的に示した方法が繰り返され、所与の合成式の左オペランドについてレベル活性化テーブルのレベルが再帰的にコンパイルされる。
【００４５】
ステップ４０４で左オペランドがプリミティブである場合、処理はステップ４１６に進み、本発明の実施形態によるプリミティブ左オペランドのレベル活性化テーブルコンパイル規則（以下の図１７を参照されたい）を使用して左オペランドの有効領域が算出される。次のステップ４１８で、左オペランドに関して適切なｏｐ値レベルが加えられる。ｐｏｐレベルおよびクリップレベルの場合と同様に、この点で重複したｏｐ  値レベルを加え、プリミティブまたはその補集合の合併集合の合成を可能にすることができる。処理はステップ４２０に進み、左オペランドの有効領域がコンプレックスであるかどうかを判定する検査が行われる。有効領域がコンプレックスである場合、ステップ４２２で、クリッピングレベル、および必要に応じて重複レベルが、合成式の左オペランドに加えられる。処理はステップ４２４に進み、クリッピングレベルを加える必要がない場合、あるいは必要なクリッピングレベルおよび重複レベルを最適レベル活性化テーブルに加えた後、「ｐｕｓｈ」レベルを加える必要があるかどうかを判定する検査が、左オペランドの有効領域に対して行われる。ｐｕｓｈレベルは、右オペランドが欠落している領域内の左オペランドに等しい値が演算によって生成される場合を表す。ｐｕｓｈレベルは合成スタックの深さを増加させる。演算の有効領域がコンプレックスである場合、この点で重複ｐｕｓｈレベルを加えることもできる。必要に応じて、次のステップ４２６で、レベル活性化テーブルにｐｕｓｈレベルが加えられる。そうでない場合、処理はステップ４４０に進み、左側オペランドの場合と同じ方法を使用して、合成式の右側オペランドが再帰的にコンパイルされる。
【００４６】
ステップ４２６の後に続くステップ４２８で、左オペランドの有効領域がコンプレックスであるかどうかを判定する検査が行われる。有効領域がコンプレックスである場合、ステップ４３０で、クリッピングレベル、および必要に応じて重複レベルが、合成式のレベル活性化テーブルに加えられる。そうでない場合、処理はステップ４４０に進み、左側オペランドの場合と同じ方法を使用して、合成式の右側オペランドが再帰的にコンパイルされる。合成式の右側オペランドのレベルがコンパイルされた後、最適レベル活性化テーブルが完成し、処理はステップ４４２で終了する。
【００４７】
ステップ４０２で、所与の合成式がプリミティブである場合、処理はステップ４３２に進み、所与の式の有効領域が、所与の式のアクティブ領域およびクリップ領域の共通集合として算出される。次のステップ４３４で、この式に「ｐｕｓｈ  値」レベルが加えられる。この場合も、演算の有効領域がコンプレックスである場合、この点で重複ｐｕｓｈレベルを加えることもできる。処理はステップ４３６に進み、加えられたｐｕｓｈレベルの結果として得られたこの式の有効領域がコンプレックスであるかどうかを判定する検査が行われる。有効領域がコンプレックスである場合、ステップ４３８で合成式の左オペランドにクリッピングレベルが加えられる。そうでない場合、処理はステップ４４２で終了する。
【００４８】
前述の方法を使用して最適レベル活性化テーブルがコンパイルされた後、好適な合成モデルのスタックマシンは、本発明によって画像を作成するために、レベル活性化テーブルによって表された式の合成を開始することができる。前述のように、最適レベル活性化テーブルの合成は最下位レベルから最高レベルに進む。各レベルで、最適レベル活性化テーブルに指定された演算が実行され、結果が合成スタック上にプッシュされる。使用されるレベルの数と、合成式を評価するために実行される画素演算の数との兼合いをとる必要があることが判明している。いくつかの例では、より多くのレベルを導入することによって、実行される画素演算の数を削減することができる。
【００４９】
次に、好適な実施形態の領域および方法の評価について詳しく論じる。合成式のレベル活性化テーブル上へのマッピングについて説明するために、以下の例を参照する。
例
図３を見るとわかるように、グラフィカルオブジェクトおよび合成演算からなる所与の合成式３１０の場合、式ツリーを右から左に評価することによって得られた自然マッピングによってレベル活性化テーブル３００が生成され、このテーブルから式を評価することができる。レベル活性化テーブルの自然マッピングは以下のように４つの段階で行われる。
１．式をポーランド記法で書く。
すなわち、ｏｖｅｒ  ｏｖｅｒ  ｉｎ  Ａ  Ｂ  ｏｕｔ  Ｃ  Ｄ  Ｅ
２．グラフィックオペランドに隣接する各オペランドを組み合わせてレベルを形成する。
すなわち、ｏｖｅｒ  ｏｖｅｒ（ｉｎ  Ａ）Ｂ（ｏｕｔ  Ｃ）Ｄ  Ｅ
３．画素を残りの各グラフィックからスタック上にプッシュするレベルでグラフィックを置き換える。
すなわち、ｏｖｅｒ  ｏｖｅｒ（ｉｎ  Ａ）（ｐｕｓｈ  Ｂ）（ｏｕｔ  Ｃ）（ｐｕｓｈ  Ｄ）（ｐｕｓｈ  Ｅ）
４．残りの各演算子を、そのソースをスタックからポップさせるレベルで置き換える。
すなわち、（ｏｖｅｒ  ｐｏｐ）（ｏｖｅｒ  ｐｏｐ）（ｉｎ  Ａ）（ｐｕｓｈＢ）（ｏｕｔ  Ｃ）（ｐｕｓｈ  Ｄ）（ｐｕｓｈ  Ｅ）
この例で、
「（ｐｕｓｈ  Ｘ）」は、フィル（ｆｉｌｌ）Ｘで定義された色値がスタック上にプッシュされる演算（Ｏｐｅｒａｔｉｏｎ）を表すレベルを示す。この種のレベルでは、レベルによって左オペランドが明示的に指定される。
「（ｏｐ  Ｘ）」は、フィルＸおよび色演算ｏｐを用いて現在のレベルを示す。演算に関するソースフィルデータＸは現在のレベルから取り出され、デスティネーションフィルデータはスタックの最上レベルからポップされる。
「（ｏｐ  ｐｏｐ）」は、フィルＸで定義された色値がスタックからポップされる演算ｏｐを表すレベルを示す。この種のレベルでは、レベルによって左オペランドが明示的に指定される。
【００５０】
合成式３１０の自然マッピングの結果として、各部分式がテーブル３００の連続サブセットに対応する平坦な式ツリーのようなレベル活性化テーブル３００が得られる。式ツリーの単一のパスで各部分式を再帰的に処理するアルゴリズムによって同じテーブルエントリを算出することもできる。式は、レベルを生成する必要がある順序に応じて、右から左、あるいは左から右に処理することができる。式ツリー３１０は、レベル活性化テーブル３００を使用してすべての部分式のアクティブ領域の共通集合内で正しく評価される。しかし、この領域外の画素の場合、好適な合成モデルが、自然マッピングによって生成されたレベル活性化テーブル３００を使用して正しい値を算出するとは限らない。したがって、正しい最適レベル活性化テーブルを作成するための余分な作業が必要である。
【００５１】
好適な実施形態の方法は、アクティブ領域分析を使用して、演算の両方のオペランドが利用できる領域にその演算をクリッピングすることによって冗長な画素演算を回避する。この方法では、オペランドに適用される演算によって非透明画素が作成される領域にオペランドをクリッピングすることもできる。大部分の例では、以下に論じるように、正しいレベル活性化テーブルを作成するには領域分析が必要である。好適な実施形態の方法は、式を表すのに十分なレベルと、式を評価するのに十分なスタック空間があるかぎり、任意の所与の合成式を評価することができる。
【００５２】
不要な合成演算の実行は、演算をそのレベルがアクティブであるときにのみ実行し、すなわち、レベルに対応するグラフィカルオブジェクトのアクティブ領域の内側に位置する画素のみに演算を実行することによって回避することができる。この動作は、効率的であると共に、かなり正確であるが、前述のように、すべての合成式について常に正しい結果を生成するとはかぎらない。残念なことに、前述の自然マッピングを使用して生成されるレベル活性化テーブルは、特殊な状況の下でのみ、あるいは特殊な種類の式についてのみ正しい画素を作成する。
【００５３】
前述の好適な合成モデルは、右側に傾斜する式ツリーに対して最もうまく働く。理想的には、各合成演算は、レベル活性化テーブル内の単一のレベルに対応する。この場合、テーブル内の各レベルは、オブジェクトと演算を指し、オブジェクトの画素を合成スタックの１番上のデータと組み合わせる。この場合、合成スタック上の画素の数が１よりも多くなることはない。
【００５４】
式ツリーが全体的に右に傾斜しており、式がｉｎ演算も、ｏｕｔ演算も、ｒａｔｏｐ演算も含まない場合、結果として得られるレベル活性化テーブルは、このページ上のあらゆる画素の式の値を正しく算出する。式がこの範疇に入らない場合、合成モデルに正しい画素値をどのように算出させるべきかを理解するには、各部分式のアクティブ領域を慎重に検討する必要がある。レベル活性化テーブルに対する必要な修正には、余分なクリッピングレベルを追加することおよび／またはレベルを、ページの様々な領域内の様々な演算を計算する数組のレベルで置き換えることが含まれる。
【００５５】
スタックが空であるときに合成演算を実行する場合、不透明白色値を右オペランドとして使用することによってこれを補償できることが知られている。しかし、このような場合、好ましくは、背景色のスタック上へのプッシュを表す１つまたは複数の余分なレベルをレベル活性化テーブルに追加することができる。式を正しくレンダリングするにはｏｖｅｒ演算レベルも必要である。
【００５６】
問題は、処理を行わないと決定する場合に、両方のオペランドのアクティブ領域を考慮する必要があることである。好適な合成モデルは、ページ上のあらゆる場所に演算を適用するか、あるいは左オペランドのアクティブ領域の内側にのみ演算を適用する。前述のような単なる式のレベル活性化テーブル上への自然マッピングでは誤った結果が生成されるいくつかの状況がある。
【００５７】
１．ソースをフィルテーブルから取り出すレベルの場合、演算はソースオペランドの境界の内側に適用される。このことは、デスティネーションオペランドの画素が下方のレベルによってスタック上に配置されていないときに、場合によってはスタック演算が適用されることを意味する。
【００５８】
２．いくつかの合成演算の結果は、ソースオペランドのアクティブ領域の外側にある画素に影響を与え、したがって、フィルテーブルからソース画素を取り出すレベルが正しい領域で常にアクティブであるとは限らない。たとえば、ｒｉｎでは、ソースオペランドのアクティブ領域の外側に位置する画素は透明になる。
【００５９】
３．ソースをスタックからポップさせるレベルの場合、下のレベルによってオペランドが実際にスタック上に配置されているか否かにかかわらず、あらゆる場所に演算が適用される。
【００６０】
これらの問題を解決するための最も簡単な方法は、合成式内の各プリミティブ部分式ＡをＡ  ｏｖｅｒ  ｇｌａｓｓで置き換えることである。この場合、ｇｌａｓｓはページ全体のサイズの透明フィルを表す。この形式の式を自然マッピングを介してレベル活性化テーブルに変換する場合、任意の所与のレベルでのスタック深さは、ページ内のあらゆる画素について同じである。結果として得られるテーブルは常に、あらゆる画素に関して正しい値を算出するが、この手法を使用すると、新たに追加されたｏｖｅｒレベルを除くあらゆるレベルがページ全体に関してアクティブになる。この場合、必要なよりも多くの画素演算が実行される。
【００６１】
より効率的な解決策を得るには、各部分式がアクティブである領域に注意を払う必要がある。理想的には、各レベルは、領域の外側では、結果として得られる画素が透明になると（領域分析によって）求めることのできる最小領域の内側でのみスタック演算を実行すべきである。演算は、両方のオペランドがアクティブである領域で実行するだけでよい。
【００６２】
添付の図１４および図１５は、オブジェクトのアクティブ領域を考慮しない場合に合成演算を実施するレベル活性化テーブルエントリを示す。図１４は、各合成演算についての問題１および問題２を示し、図１５は問題３をカバーしている。各テーブル内の「演算（Ｏｐｅｒａｔｉｏｎ）」列は、合成演算を適用することによって評価すべき式を含む。「領域（Ｒｅｇｉｏｎ）」列はオペランドのアクティブ領域のすべての組合せをリストしており、「値（Ｖａｌｕｅ）」列は各組合せごとの合成式の正しい値を示す。「レベル（Ｌｅｖｅｌ）」列は、演算を実施するために使用されるレベルを示す。図１４は、ソースがフィルテーブルから取り出される演算を示す。図１５は、ソースをスタックから取り出す（すなわち、ポップする）演算を示す。
【００６３】
図１５で、「スタック（Ｓｔａｃｋ）」列はスタック上の画素を示す。「結果（Ｒｅｓｕｌｔ）」列は、レベルが算出する値を示す。図１４内の演算は、スタック深さを変更せず、スタック上のデスティネーション画素を、「結果」列に示された結果と置き換える。図１５で、「スタック（Ｓｔａｃｋ）」列は、スタック上の１番上の２つの画素の値を示す（左の画素がスタックの最上画素である）。図１５内の演算は常に、スタック上の１番上の２つの値を、「結果（Ｒｅｓｕｌｔ）」列に示された演算の結果と置き換え、したがって、スタック深さを１だけ減少する。
【００６４】
疑問符を含む式は、スタックの最上画素の未知の値が使用されることを示す。スタックが空ではない場合、スタック深さが誤って減少され、誤った値がスタック上にプッシュされる。スタックが空である場合、合成モデルがこのオペランドを不透明白画素で置き換えるので問題にはならない。疑問符自体は、スタックの最上画素が変更されないことを示す。各オペランドの計算に責任を負うテーブルの部分は、部分式のアクティブ領域の内側ではスタック上に１つの画素のみをプッシュし、アクティブ領域の外側では何もプッシュしないと仮定する。
【００６５】
「補正（Ｃｏｒｒｅｃｔ）」列は、スタック上に正しい値を残すために実行する必要のある演算を示す。「補正（Ｃｏｒｒｅｃｔ）」列の結果は、アクティブ領域を考慮した結果である。しかし、この結果ではクリッピングは考慮されず、場合によっては、式のアクティブ領域の外側にある未使用画素を削除するためにｐｏｐが必要である。オペランドｐｏｐは、オペランドがスタックの１番上にあり、結果がスタック上にプッシュされる前にスタックからポップされることを示す。後述の他の最適化では、余分なクリッピングレベルが追加され、ポップする必要のある画素の生成が回避される。図１５で、「補正（Ｃｏｒｒｅｃｔ）」列の演算は、結果がスタック上にプッシュされる前に両方のオペランドをスタックからポップさせると仮定される。
【００６６】
場合によっては、ｐｕｓｈ演算が合成演算に置き換わることに留意されたい。ｐｕｓｈが現われる場合、スタック深さが増加することによって、スタックからデスティネーションオペランドが欠落しているという仮定が補償される。
【００６７】
上記では、その外側ではオブジェクトが透明であることが知られている領域をグラフィカルオブジェクトのアクティブ領域として定義した。以下のパラグラフでは、式のアクティブ領域とは何かと、このアクティブ領域をどのように算出すべきかについて説明する。
【００６８】
領域の外側では式がｇｌａｓｓとして評価される最小領域を式のアクティブ領域として定義することによって、アクティブ領域の定義を任意の合成式に拡張することができる。
【００６９】
以下の図１６に示すように、いくつかの規則を適用し、部分式のアクティブ領域（Ａｃｔｉｖｅ  Ｒｅｇｉｏｎ）を組み合わせることによって、任意の合成式のアクティブ領域を算出することができる。各合成演算について、演算の結果のアクティブ領域をこの演算のオペランドのアクティブ領域で定義することができる。たとえば、Ａ  ｏｖｅｒ  Ｂのアクティブ領域はＡおよびＢのアクティブ領域の合併集合である。
【００７０】
式（Ｅｘｐｒｅｓｓｉｏｎ）のアクティブ領域（Ａｃｔｉｖｅ  Ｒｅｇｉｏｎ）は、図１６に示された規則を各部分式に最適に適用することによって算出することができる。これらの規則は、ツリーの最下部から上向きにルートの方へ適用される。図５は、アクティブ領域の式が各レベルの隣に示された式ツリー５００を示す。
【００７１】
いくつかの場合においては、部分式のアクティブ領域が、式が現われるその式のアクティブ領域に含まれないことに留意されたい。このような場合、部分式は、式ツリーの高い場所に位置する必要のない画素を生成する。不要な画素演算を回避するには、各部分式が現れる各式のアクティブ領域の共通集合にその部分式をクリッピングする必要がある。したがって、部分式のクリッピング領域は、（部分）式が現われるすべての（部分）式のアクティブ領域の共通集合として定義することができる。前述のように、部分式のクリッピング領域は、その部分式が含まれる式を評価できるようにするために、その部分式を評価する必要がある最小領域である。
【００７２】
クリッピング領域は、式ツリーのルートから下向きにリーフの方へ算出される。合成式中の各部分式についてのクリッピング領域は、以下のステップを使用して算出することができる。
１．各部分式にそのアクティブ領域をラベル付けする。
２．最上レベル式のクリッピング領域をこの式のアクティブ領域として設定する。
３．各部分式のアクティブ領域およびその親のクリッピング領域の共通集合を各部分式のクリッピング領域として再帰的に設定する。
【００７３】
図６は式ツリー６００を示し、この場合、式ツリー６００内の各部分式のルート節点にその部分式のクリッピング領域がラベル付けされる。たとえば、部分式Ｄ  ｏｕｔ  Ｅのクリッピング領域はＤである。
【００７４】
クリッピング領域とは、各部分式を評価する必要がある最小領域である。しかし、式を正しく評価するには、各演算の両方のオペランドが利用できる領域、すなわち、クリッピング領域の共通集合にのみその演算を適用すべきである。この領域を演算の有効領域と呼ぶ。ある演算の有効領域は、一般に、その演算がルートを形成する部分式のクリッピング領域と同じではないことに留意されたい。有効領域は通常、この演算がルートである部分式のクリッピング領域の固有のサブセットである。図７は式ツリー７００を示し、この場合、式ツリー７００内の各部分式のルート節点にその部分式の有効領域がラベル付けされる。たとえば、部分式Ｄ  ｏｕｔ  Ｅの有効領域はＤ∩Ｅである。リーフ節点は、有効領域がクリッピング領域と同じであるｐｕｓｈ演算とみなすことができる。
【００７５】
式ツリーの各部分式の有効領域が前述の方法で使用され、合成式が最適レベル活性化テーブルにコンパイルされる。残念なことに、有効領域は、好適な合成モデルではサポートされない任意に複雑なブール式であることがある。あらゆるブール式を選言的形式で、プリミティブあるいはプリミティブの補集合の共通部分の互いに素な合併集合として書き直すことができるので、上記の問題は解消することができる。選言的形式の有効領域は、必要な計算を行うレベル活性化テーブルにコンパイルすることができる。
【００７６】
図８は、選言的標準形７１０で書かれた図７の式７００の最適レベル活性化テーブルを示す。ａｔｏｐおよびその引数を除くすべての有効領域は、プリミティブ領域またはその補集合の共通集合である。ａｔｏｐおよびその引数は（Ａ∩（Ｂ∩Ｃ）∪Ｄ）にクリップする必要があり、（Ａ∩（Ｂ∩Ｃ）∪Ｄ）は（Ａ∩Ｂ∩Ｃ∩Ｄ）∪（Ａ∩Ｄ）として書き直すことができる。
【００７７】
図７の部分式Ｄ  ｏｕｔ  Ｅはテーブル８００内の３つのレベルで表される。この部分式は、ｐｕｓｈ  Ｅレベル８１０、ｏｕｔ  Ｄレベル８２０、およびｐｕｓｈ  Ｄレベル８４０で表される。ｏｕｔ演算はＤ∩Ｅの外側では正しい結果を生成しないので、余分のｐｕｓｈ  Ｄが必要である。プリミティブが、同じ有効領域を有する演算の左オペランドであるときは、プリミティブは単一レベルへの動作と結合できる、そうでない場合は、演算の有効領域の外側でのみアクティブである余分なｐｕｓｈレベルが必要である。これによって、ｐｕｓｈが、それが置き換わる演算と同時にアクティブになることはなくなる。この例での他のすべての場合に、各左プリミティブのクリッピング領域は、このプリミティブをページ上で合成する演算と同じであり、したがって、ｐｕｓｈをこの演算と組み合わせることができる。
【００７８】
図８を見るとわかるように、ａｔｏｐ  Ａレベルはレベル８５０およびレベル８６０として重複される。上記で図４に関して論じたように、これによって、単一のレベルをプリミティブまたはその補集合の合併集合にクリップすることができる。第１のａｔｏｐ  Ａ８６０は領域Ａ∩Ｄでアクティブであり、第２のａｔｏｐ  Ａ８５０はＡ∩Ｂ∩Ｃ∩Ｄでアクティブである。２つのレベルの有効領域は互いに素であるので、任意のある時点ではこれらの領域のうちの多くても一方がアクティブである。全体として、この２つのレベルは領域（Ａ∩Ｂ∩Ｃ∩Ｄ）∪（Ａ∩Ｄ）で演算を実行する。
【００７９】
図１７および図１８は、本発明の実施形態による、合成式をレベル活性化テーブルにコンパイルするための規則を要約した図である。これらの図は、図１４、図１５、および図１６の情報を組み合わせることによって得られる。すべての式は以下の３つの範疇に入る。
１．プリミティブ式：形式ｐｕｓｈ  Ａの１つのレベルで表される。
２．一次演算がプリミティブ左オペランドを有する式：図１７はこのような式を評価するのに必要なレベルを表す。
３．一次演算がコンプレックス左オペランドを有する式：図１８はこのような式を評価するのに必要なレベルを表す。
【００８０】
図１７および図１８の「レベル（Ｌｅｖｅｌｓ）」列は、部分式の演算（Ｏｐｅｒａｔｉｏｎ）を実施するのに必要なレベルを示す。「クリップ（Ｃｌｉｐ）」列は、各レベルをクリッピングする必要のある領域を示す。「クリップ（Ｃｌｉｐ）」列内に「ｃｌｉｐ」で示された領域は、再帰的に部分式に渡される領域である。「クリップ（Ｃｌｉｐ）」列で、「Ａ」および「Ｂ」は部分式Ａおよび部分式Ｂのアクティブ領域を示す。たとえば、Ａがプリミティブである領域ｃｌｉｐにクリップされる形式Ａ  ｏｕｔ  Ｂの部分式について、図１７は、サブテーブルを使用して部分式Ｂを実施し２つのレベル（ｐｕｓｈ  Ａおよびｏｕｔ  Ａ）を使用してｏｕｔ演算を実施することによってこの部分式を評価できることを示す。このサブテーブルは、図１７の「レベル（Ｌｅｖｅｌｓ）」列に「ｔａｂｌｅ  Ｂ」で表されている。ｐｕｓｈ  ＡレベルはｃｌｉｐとＢのアクティブ領域の補集合との共通集合でのみアクティブであるべきである。ｏｕｔ  Ａレベルは、ｃｌｉｐとＢのアクティブ領域との共通集合でのみアクティブであるべきである。Ｂを実施するサブテーブルは、ｃｌｉｐとＡのアクティブ領域の共通集合に等しいクリップ領域に同じ規則を再帰的に適用することによって生成される。
【００８１】
前述の領域分析では、オブジェクトの不透明度に関する知識は考慮されていない。いくつかのオブジェクトが完全に不透明であることがわかっている場合、さらなる最適化が可能になる。ある式内のオブジェクトの不透明度チャネルを検査し各オブジェクトの透明性を判定することができる。この検査は、好適な実施形態の方法における領域を算出するステップの前に行うことができる。
【００８２】
ある式の不透明領域は、完全に不透明であることがわかっている領域として定義することができる。式の不透明領域は常に、そのアクティブ領域のサブセットである。式の部分式の不透明領域がわかっている場合、式内のアクティブ領域をさらに修正することができる。不透明領域はアクティブ領域と同様に算出することができる。図１９は、コンプレックス式の不透明領域（Ｏｐａｑｕｅ  Ｒｅｇｉｏｎ）を算出するための規則と、クリッピング領域およびアクティブ領域（Ａｃｔｉｖｅ  Ｒｅｇｉｏｎ）を算出するための更新された１組の規則とを示す。図１９は、不透明領域を考慮するように修正された図１６と組み合わされた図１８の凝縮（ｃｏｎｄｅｎｓｅｄ）バージョンである。ＡおよびＢの不透明領域（Ｏｐａｑｕｅ  Ｒｅｇｉｏｎ）はそれぞれ、ＯAおよびＯBとして示される。「クリップＡ（Ｃｌｉｐ  Ａ）」列および「クリップＢ（Ｃｌｉｐ  Ｂ）」列は部分式Ａおよび部分式Ｂのクリッピング領域を示す。親式のクリッピング領域は明示的に示されていないが、部分式のクリッピング領域を算出する際には含めなければならない。
【００８３】
図１９を見るとわかるように、オペランドの一方または両方が不透明であるか、あるいは部分的に不透明であることがわかっているいくつかの場合にはアクティブ領域（Ａｃｔｉｖｅ  Ｒｅｇｉｏｎ）がより小さくなる。オペランドが完全に不透明である場合、画素演算の実行は完全に回避することができる。たとえば、Ａ  ｏｖｅｒ  Ｂを評価する場合、Ａが不透明であるとき、有効領域はＡ∩（Ｂ∩ＯA）＝Ａ∩Ｂ∩Ａ＝φである。
【００８４】
本発明の他の実施形態によれば、ページ上にレンダリングすべき画像を表す式は、好ましくはテキストファイルとして記憶される。この式は、オブジェクトおよび合成演算からなる。各オブジェクトは好ましくはアウトラインおよびフィルで定義される。フィルは、場合によってはビットマップ画像形式の、オブジェクトに関する色情報および透明度情報からなる。フィル情報は、好適な実施形態によれば式の一部でよく、あるいは式によって参照されるファイルにフィルを記憶することができる。オブジェクトのアウトラインは、内側にオブジェクトの色情報が適用される領域を表す。アウトラインの外側の画素は透明であると仮定される。各合成演算は、ページ内のあらゆる画素に関して計算すべき演算を表す。
【００８５】
本発明の実施形態は、レンダリングすべき式内の各合成演算ごとに、演算を実行する必要があるページの最小領域を算出することにより、レンダリング装置によって行われる作業の量を削減する。他の実施形態によれば、領域はブール式として算出される。このような式は好ましくは式ツリーとして式される。前述のように、情報をレベル活性化テーブルとして符号化する場合、式ツリー内の情報が式テーブルとして処理される。図１３は、本発明の他の実施形態による画像を作成する方法を示す流れ図である。プロセスはステップ１３０１から開始し、レンダリングすべき画像を表す式が解析され式ツリーに変換される。式ツリー内の各節点は最初の式の部分式に対応し、ルート節点は式全体（すなわち、完全な画像）を表す。次のステップ１３０３で、各部分式ごとに（すなわち、式ツリー内の各節点ごとに）、合成演算の結果が非透明であることがわかっている最小領域が算出される。前述のように、この領域を部分式のアクティブ領域と呼ぶ。演算節点のアクティブ領域は、演算のオペランドのアクティブ領域および演算の種類に依存する。オブジェクトのアクティブ領域はオブジェクトのアウトラインの内側の領域に規定される。アクティブ領域は、式ツリーのリーフから開始し、以下のサブステップを使用して式ツリーのルートの方へ進むことによって、ステップ１３０１で算出される。
ａ）式内の各オブジェクトごとに（すなわち、式ツリー内の各リーフ節点ごとに）、オブジェクトのアウトラインによって画定される領域をアクティブ領域として設定する。
ｂ）オペランドのアクティブ領域がすでにわかっている各演算ごとに、図１６に定義された規則に従って演算のアクティブ領域を算出する。
ｃ）すべてのアクティブ領域が算出されるまでステップｂを繰り返す。
【００８６】
プロセスはステップ１３０５に進み、式内の各部分式ごとにクリッピング領域が算出される。クリッピング領域は、各（部分）式が現われるその（部分）式のアクティブ領域の共通集合として算出される。前述のように、クリッピング領域は、部分式内の画素が最終画像に寄与する領域を表す。クリッピング領域は、式ツリーのルートから開始し、以下のサブステップを使用してリーフの方へ進むことによって、ステップ１３０５で算出される。
ａ）部分式に関連するルート節点のクリッピング領域が部分式のアクティブ領域と等しくなるように設定する。
ｂ）クリッピング領域がすでに算出されている各演算節点ごとに、図１７に定義された規則を使用して各オペランドのクリッピング領域を求める。
ｃ）すべてのクリッピング領域が算出されるまでステップｂを繰り返す。
【００８７】
次のステップ１３０７で、ツリー内の各節点ごとに有効領域が算出される。前述のように、有効領域は、節点に関連する演算に関してスタック演算を生成する必要がある領域を表す。ツリー内の各節点の有効領域は、節点がリーフ節点である場合には、その節点のクリッピング領域とアクティブ領域の共通集合をその節点の有効領域として設定することによって、ステップ１３０７で算出される。これに対して、節点が演算節点である場合には、有効領域が節点のオペランドのアクティブ領域とその節点のクリッピング領域との共通集合として設定される。プロセスは次のステップ１３０９に進み、活性化情報（すなわち、アクティブ領域情報、有効領域情報、およびクリッピング領域情報）が、ハードウェアまたはソフトウェアのレンダラを使用して効率的にレンダリングできる形式に符号化される。このようなレンダラは好ましくは、画素ベースのレンダリング演算を実行する手段と、現在の画素がある領域に属するかどうかに応じてレンダリング演算を制限する手段とを備える。
【００８８】
本発明の他の実施形態によれば、ステップ１３０５とステップ１３０７を組み合わせて単一のパスを得ることができる。図１７は、この実施形態によってステップ１３０５とステップ１３０７を組み合わせるための規則を示す。ステップ１３０９は、レンダリングハードウェアに依存する。さらに、ステップ１３０９は、ステップ１３０５およびステップ１３０７と同じパスで実行することができる。
【００８９】
ある式のすべてまたはいくつかのオブジェクトが不透明であることがわかっているとき、他の計算を追加して、関連するアクティブ領域を修正し、したがって有効領域も修正し、この式をレンダリングするのに必要な画素合成演算の数をさらに削減することができる。
【００９０】
本発明の他の実施形態によれば、図１３のステップ１３０３に不透明領域の計算を追加することができる。不透明領域は、図１９に定義された規則を適用することによってアクティブ領域と同様に算出することができる。演算節点の不透明領域は、節点のオペランドのアクティブ領域および不透明領域と、実行中の演算とに依存する。
【００９１】
不透明領域を導入すると、アクティブ領域の計算が修正される。演算節点のアクティブ領域も、節点のオペランドのアクティブ領域および不透明領域と、実行中の演算との両方に依存する。クリッピング領域および有効領域は、アクティブ領域にのみ依存し、したがって、クリッピング領域および有効領域の計算は、本発明の実施形態では、不透明領域が導入されても変更されない。ステップ１３０３は、まず各部分式ごとに（すなわち、式ツリー内の各節点ごとに）、式が非透明であることがわかっている最小領域と、式が不透明であることがわかっている最大領域とを算出することによって、不透明領域を含むように修正することができる。これらの領域を部分式のアクティブ領域および不透明領域と呼ぶ。演算節点のアクティブ領域および不透明領域はそれぞれ、演算のオペランドのアクティブ領域および不透明領域と、演算の種類とに依存する。前述のように、オブジェクトのアクティブ領域は、オブジェクトのアウトラインの内側の領域として定義される。これに対して、オブジェクトの不透明領域は、オブジェクトが不透明であることがわかっていない場合には空であり、オブジェクトが不透明であることがわかっている場合にはオブジェクトのアウトラインの内側の領域である。
【００９２】
アクティブ領域および不透明領域は、式ツリーのリーフから開始し、以下のサブステップを使用してルートの方へ進むことによって、ステップ１３０３で算出することができる。
ａ）式内の各オブジェクトごとに（すなわち、式ツリー内の各リーフ節点ごとに）、オブジェクトのアウトラインで画定される領域をアクティブ領域として設定し、オブジェクトが不透明である場合にはオブジェクトのアウトラインで画定される領域を不透明領域として設定し、そうでない場合に不透明領域を空として設定する。
ｂ）オペランドのアクティブ領域および不透明領域がすでにわかっている各演算ごとに、図１９に定義された規則に従って演算のアクティブ領域および不透明領域を算出する。
ｃ）すべてのアクティブ領域および不透明領域が算出されるまでステップｂを繰り返す。
【００９３】
前述の好適な方法は特定の制御フローを含む。好適な方法には他の多数の変形形態があり、それらの形態は、本発明の趣旨または範囲から逸脱せずに様々な制御フローを使用する。さらに、好適な方法の１つまたは複数のステップを順次ではなく並行して実行することができる。特に、図１２のステップ１２０３とステップ１２２５を並行して実行することができる。
【００９４】
付録Ａは、本発明の実施形態による最適レベル活性化テーブルを作成する合成式用のコンパイラの擬似符号インプリメンテーションを示す。擬似符号構文はＣ＋＋に近い構文であるが、Ｃ＋＋構造体の使用は回避される。このコンパイラは効率性を所期したものではない。このコンパイラの目的は、合成演算をどのようにコンパイルすべきかを示すことである。実際のインプリメンテーションは好ましくは、再帰的には書かれない。さらに、付録Ａに示すコンパイラは不透明領域を考慮していない。最後に、この擬似符号インプリメンテーションは、いくつかの抽象データタイプ、すなわち、式、演算、領域、テーブル、およびレベルが利用可能であると仮定している。これらはそれぞれ、合成式、合成演算、ページの領域を表すブール式、レベル活性化テーブル、およびレベル活性化テーブル内の個々のレベルを表す。
【００９５】
Ｍｉｃｒｏｓｏｆｔ  Ｃｏｒｐｏｒａｔｉｏｎによって開発されたＷｉｎｄｏｗｓＴＭオペレーティングシステム上で実行されるコンピュータアプリケーションプログラムとして本発明の好適な実施形態を説明した。しかし、当業者には、他のオペレーティングシステムによって駆動されるコンピュータシステム上に前述の実施形態を実装できることが認識されよう。たとえば、好適な実施形態は、ＵＮＩＸＴＭ、ＯＳ／２ＴＭ、ＤＯＳＴＭを実行するコンピュータシステム上で実行することができる。このアプリケーションプログラムは、メニュー項目を含むユーザインタフェースと、マウス操作およびキーボード操作に応答する制御装置とを有する。このアプリケーションプログラムは、ホストコンピュータに直接接続されるか、あるいはネットワークを介してアクセスされる１つまたは複数のプリンタにデータを送信する能力を有する。このアプリケーションプログラムは、接続されたデジタル通信網（たとえば、「インターネット」）にデータを送信し、この通信網からデータを受信する能力も有する。
【００９６】
本発明の実施形態は、図９に示すコンピュータシステム１などの（ホスト）コンピュータシステムを使用して実施することができ、この場合、上記で論じ他の図面を参照して説明したアプリケーションプログラムは、コンピュータシステム１上で実行されるソフトウェアとして実現される。
【００９７】
通常、好適な実施形態のアプリケーションプログラムは、ハードディスクドライブ５上に存在し、プロセッサ２を使用して読み取られ制御される。プログラムおよびプリントリスト、ならびにネットワークから取り込まれたデータの中間記憶は、半導体メモリを、場合によってはハードディスクドライブ５と共に使用して行うことができる。いくつかの例では、アプリケーションプログラムは、ＣＤ−ＲＯＭまたはフロッピィディスク上に符号化してユーザに供給するか、あるいはユーザによってモデム装置（図示せず）を介してネットワークから読み込むことができる。
【００９８】
実施形態は、この方法のステップの関数または部分関数を実行する１つまたは複数の集積回路などの専用ハードウェアで実施することもできる。このような専用ハードウェアには、グラフィックプロセッサ、デジタル信号プロセッサ、または１つまたは複数のマイクロプロセッサおよび関連するメモリを含めることができる。
【００９９】
上記では、本発明の小数の実施形態のみを説明したが、当業者なら、本発明の範囲および趣旨から逸脱せずにこれらの実施形態に修正および／または変更を加えることができる。
【０１００】
たとえば、スタックマシンではなくデータフロープロセッサを使用してグラフィックオブジェクトデータを合成するシステムで、好適な実施形態の方法を使用することができる。
【０１０１】
さらに、前述の方法は、グラフィックスオブジェクトの合成に限らない。式の評価を含む任意のプロセスにこの方法を使用することができる。
【０１０２】
0004323671.tif 000002
0004323671.tif 000003
0004323671.tif 000004
0004323671.tif 000005
0004323671.tif 000006
* 所与の領域にクリッピングされた所与のフィルを有する所与の演算を実施するレベルをレベル活性化テーブルに追加する。opは合成演算または「PUSH」でよい。フィルはプリミティブ式または「POP」でよい。クリップ領域を簡単な共通集合として表すことができない場合、重複レベルが追加される。
0004323671.tif 000007
0004323671.tif 000008
* レベル活性化テーブルにクリップレベルを追加する。所与の１組のエッジについてクリップレベルがすでに存在している場合、クリップすべきレベルが既存のレベルに追加される。クリップ引数はプリミティブ領域またはその補集合でなければならない。クリップ引数がプリミティブ領域である場合、追加されるレベルはCLIPINである。プリミティブの補集合である場合、追加されるレベルはCLIPOUTである。
0004323671.tif 000009
【０１０３】
【発明の効果】
本発明によれば、複数の構成要素を合成することによって合成された画像を作成する方法を提供することによって、各画素を計算するのに必要な１組の合成演算を評価する画素当たりコストを低減し、さらに、画素をレンダリングするために使用される特定の合成演算が、合成中のオブジェクトの境界の外側にある画素に影響を与えないという仮定が成立しない合成式でも、画素順次レンダリングを可能とする。
【図面の簡単な説明】
【図１】いくつかの重なり合ったオブジェクトを含む合成式ツリーを示す図である。
【図２】本発明に有用な様々な合成演算子の結果を示す図である。
【図３】自然マッピング法を使用して形成された対応するレベル活性化テーブルと共に式ツリーを示す図である。
【図４】本発明の実施形態による、最適レベル活性化テーブルをコンパイルする方法の流れ図である。
【図５】本発明の実施形態による、アクティブ領域の式が各レベルの隣に示された式ツリーを示す図である。
【図６】本発明の実施形態による、クリッピングされたアクティブ領域の式が各レベルの隣に示された式ツリーを示す図である。
【図７】本発明の実施形態による、有効領域の式が各レベルの隣に示された図５の式ツリーを示す図である。
【図８】本発明の実施形態による、図５の式ツリーの最適レベル活性化テーブルを示す図である。
【図９】本発明の実施形態を組み込んだコンピュータシステムの概略ブロック図である。
【図１０】実施形態の機能データフローを示すブロック図である。
【図１１】本発明の実施形態を組み込んだコンピュータシステムの画素順次レンダリング装置および関連する表示リストならびに一次記憶の概略ブロック図である。
【図１２】本発明の一実施形態による画像を作成する方法を示すフローチャートである。
【図１３】本発明の他の実施形態による画像を作成する方法を示すフローチャートである。
【図１４】オブジェクトのアクティブ領域を考慮しない場合に合成演算を実現するレベル活性化テーブルエントリを示す図である。
【図１５】オブジェクトのアクティブ領域を考慮しない場合に合成演算を実現するレベル活性化テーブルエントリを示す図である。
【図１６】本発明の実施形態による、合成式のアクティブ領域を算出するための規則を示す図である。
【図１７】合成式を、一次演算がプリミティブ左オペランドを有するレベル活性化テーブルにコンパイルするための規則を示す図である。
【図１８】合成式を、一次演算がコンプレックス左オペランドを有するレベル活性化テーブルにコンパイルするための規則を示す図である。
【図１９】修正された図１６と組み合わされた図１８の凝縮バージョンの図である。
【図１】
0004323671.tif 000010
【図２】
0004323671.tif 000011
【図３】
0004323671.tif 000012
【図４】
0004323671.tif 000013
【図５】
0004323671.tif 000014
【図６】
0004323671.tif 000015
【図７】
0004323671.tif 000016
【図８】
0004323671.tif 000017
【図９】
0004323671.tif 000018
【図１０】
0004323671.tif 000019
【図１１】
0004323671.tif 000020
【図１２】
0004323671.tif 000021
【図１３】
0004323671.tif 000022
【図１４】
0004323671.tif 000023
【図１５】
0004323671.tif 000024
【図１６】
0004323671.tif 000025
【図１７】
0004323671.tif 000026
【図１８】
0004323671.tif 000027
【図１９】
0004323671.tif 000028