(57)【要約】      （修正有）【課題】コンピュータに実装されるディスプレイ・システムにおいて、半透明で、複雑な形状の重なり合っている層を短い処理時間で描写するためのシステムおよび方法。【解決手段】ウィンドウ・システムのようなコンピュータ・ディスプレイ内で重なり合っている層に対し、表示される画像の前から後ろへ向かう組み立てを使用して、ウィンドウのような任意の数の重なり合うエレメントが、一時記憶スペースまたは追加の画面外のバッファを必要とせずに表されるようにすることで、前から後ろへ向かう組み立て技術によって、画像を描写することに関して実行されるメモリ転送の数を最小限にし、最終画像に寄与しないピクセルの不必要な読み取り及び処理を回避して、半透明、シャドウおよび不規則な形状といったような特殊効果が、対応され処理される。【選択図】図４
2007304576.tif 000002
【特許請求の範囲】
【請求項１】
複数の層を含む画像であって、前記層の第１の層は、前記層の第２の層に重っており、各層は端によって規定された境界を含んでおり、前記第１の層の少なくとも一つの端は前記第２の層の境界内部に位置している、画像において、タイルを細区分する方法は、
前記第2の層の境界内に位置する前記第1の層の少なくとも一つの端の延長線に対応する線に沿って前記第2の層を細区分して、二つのタイル細区分を獲得するステップと、
前記獲得されたタイルの細区分の少なくとも一つの部分集合の表現を、タイルリストに格納するステップと、
を含む、方法。
【請求項２】
請求項１に記載の方法において、前記獲得されたタイルの細区分の少なくとも一つを使用して前記細区分するステップを繰り返すステップと、をさらに含む、方法。
【請求項３】
請求項１に記載の方法において、前記タイルリストの、少なくとも二つの隣接したタイル細区分を結合するステップと、
をさらに含む、方法。
【請求項４】
請求項１に記載の方法において、お互いに同じ組の同一の層の部分を含む少なくとも二つの隣接したタイルの細区分に応じて、前記タイルリストの前記少なくとも二つの隣接したタイルの細区分を結合するステップをさらに含む、方法。
【請求項５】
複数の層を持つデバイスであって、前記層の第１の層は、前記層の第２の層に重っており、各層は端によって規定された境界を含んでおり、前記第１の層の少なくとも一つの端は前記第２の層の境界内部に位置している、デバイスにおいて、タイルを細区分するシステムは、
前記第２の層の境界内に位置する前記第1の層の少なくとも一つの端の延長線に対応する線に沿って第２の層を細区分するための、タイルサブディバイダーと、
前記獲得されたタイルの細区分の少なくとも一つの部分集合の表現をタイルリストに格納するための、前記タイルサブディバイダーに結合された、タイルリストと、
を含む、システム。
【請求項６】
複数の層を含む画像であって、前記層の第１の層は前記層の第２の層に重っており、各層は端によって規定された境界を含んでおり、前記第１の層の少なくとも一つの端は前記第２の層の境界内部に位置している、画像において、タイルを細区分するため、その中に具体化されたコンピュータ読み取り可能コードを持つコンピュータ使用可能媒体を含むコンピュータ・プログラム製品であって、
コンピュータに、前記第２の層の境界内に位置する前記第1の層の少なくとも一つの端の延長線に対応する線に沿って第２の層を細区分し、二つのタイル細区分を獲得するように構成された、コンピュータ読み取り可能プログラム・コードデバイスと、
コンピュータに、前記獲得されたタイルの細区分の少なくとも一つの部分集合の表示をタイルリストに格納させるように構成されたコンピュータ読み取り可能プログラムコードデバイスと、
を含む、コンピュータプログラム製品。
【発明の詳細な説明】
【技術分野】
【０００１】
発明の背景
１．発明の技術分野
本発明は、一般に、コンピュータに実装されるディスプレイ・システムに関係し、特に、ディスプレイ・システム内の半透明で、複雑な形状の重なり合っている層を描写する（ｒｅｎｄｅｒｉｎｇ）ためのシステムおよび方法に関係する。
【背景技術】
【０００２】
２．従来の技術
多くの既存のディスプレイ・システムは、最終画像を生成するために２つ以上のディスプレイ・エレメントを合成することができる。そのようなシステムでは、ディスプレイ・エレメントはしばしば、例えば、ウィンドウのようなスクリーン上のエレメントがあちこち移動し互いの上に置かれる、グラフィカル・ユーザ・インターフェース用のウィンドウ・システムにおけるような、重なり合っている層を含む。
【０００３】
２つ以上の重なり合っている層を持つ画像を描写し表示すると、特に層が重なり合っている画像部分を描写する方法を決定する際に、ある問題が起こる。重なり合っている層が不透明の場合、グラフィックス・システムはどの層が「最上層」にあるかを単に判定し、最終画像にその層の関連する部分を表示すればよく、不明瞭になる下に置かれる層の部分は、無視されてもよい。しかしながら、重なり合っている層が半透明の場合、重なり合っている各層内の画素（ピクセル）間にある程度の相互作用があるので、より複雑な処理が要求される。従って、最終画像を引き出すために、画像エレメントを重ね合わせるための、ある演算が要求される。
【０００４】
これらの計算を実行するための合成技術は、この技術分野ではよく知られている。例えば、Ｔ．ポーター等による１９８４年のＳＩＧＧＲＡＰＨ’８４という会報のページ２５３〜５９にある「デジタル画像の合成」を参照すること。しかしながら、一般に、そのような技術は、一度に二層だけを合成するためのものである。二層以上が合成されようとする場合、多くの別個の作業が、最終画像を生成するために実行されなければならない。これは、以下の層に対して実行された合成作業の結果と、各々の新しい層とを連続的に結合する下から上へ向かうアプローチで、画像エレメントを合成することにより一般的に達成される。
【０００５】
このステップバイステップで合成するアプローチは、いくつかの欠点を持つ。画像がフレーム・バッファに構築される場合、システムがフレーム・バッファに数回連続して書き込む毎に、スクリーンのちらつきが生じる可能性がある。代わりに、スクリーンのちらつきを回避するために、画像が画面外のバッファに構築されてもよいが、そのような技術は、バッファに配分されるための付加メモリを要求し、また最終画像がフレーム・バッファに転送される時、付加メモリへの読み取り及び書き込みを要求する。
【０００６】
さらに、最終画像のステップバイステップによる生成には、多数の算術演算が実行されなければならないために、性能が低下してしまうことがある。フレーム・バッファへのデート（ｄａｔｅ）の書込みは、多くのコンピュータ上で特に遅く、したがって、フレーム・バッファにいくつかの層を連続して書き込む従来のシステムは、特に厳しい性能の低下に直面する。
【０００７】
最終的に、そのような技術はしばしば、他の画像エレメントによって後で見えなくさせられる画像エレメントのいくつかの部分について、不必要な生成を行う結果になる。
【０００８】
従来より、任意に形作られるウィンドウおよび層は、長方形の領域にウィンドウを分割し、及び／又は長方形のいくつかの部分を覆い隠すことで、長方形の層が任意に形作られているように見せることによって達成される。そのような技術はしばしば、最終画像上に何の効果も持たないウィンドウのエリアに対して追加の処理時間を費やす結果になる。
【０００９】
必要とされるものは、それは上記に言及された欠陥を回避し、スクリーンのちらつきを引き起こさずに、および追加の画面外のバッファを要求せずに、複数の層の合成を可能にする、半透明の層を描写するためのシステムおよび方法である。さらに必要とされるものは、複数の重なり合う半透明の層を持つ画像を生成する時に、従来の技術システムの性能を向上させる描写システムおよび方法である。さらに必要とされるものは、最終画像内の他の画像エレメントによって見えなくさせられる画像エレメント部分の不必要な生成を回避する、描写システムおよび方法である。
【００１０】
【発明の開示】
【課題を解決するための手段】
【００１１】
発明の要旨
本発明に従って、半透明で複雑な形状の重なり合っている層の効率的な合成を促進するレンダリングのシステムおよび方法が提供される。透明度の指標が層内のピクセル毎をベースにして指定されることができるようにするために、アルファ・チャンネルが各層に提供される。レンダリングは前から後へ向かう順序で実行される。その結果、本発明は、最終画像に寄与しない層の部分の不必要な演算を回避することができる。さらに、１つの実施例では、合成が、最初に画像エリアを長方形に細分することによって、より効率的に為され、その場合、所定の長方形内のすべての点に対する重なり合っている層の集合（またそれらの順序）は一定である。その後、合成の操作は、各長方形毎に別々に実行されることができ、その結果、処理操作の最内ループ内の複雑で時間を消費する境界照合の操作を回避することができる。
【００１２】
本発明は、アルファ・チャンネルを持つ２つ以上の重なり合っている層を目標ビットマップ（ｄｅｓｔｉｎａｔｉｏｎ ｂｉｔｍａｐ）に描写する。目標ビットマップは、例えばビデオシステムのフレーム・バッファでもよい。目標ビットマップ内の各ピクセルに対して、本発明は、色値及びアルファ値を蓄積しながら、対応するピクセルを持つ層を前から後ろへ向かう順序で処理する。いったん蓄積されたアルファ・チャンネルが完全な不透明度に達すると、本発明はそのピクセルに対する作業を中止する、なぜなら、その中止点より下に存在するいかなるピクセルも（完全な不透明度が達成されているので）完全に見えなくなっていて、処理される必要がない。
【００１３】
このように本発明は、最終画像に寄与しないピクセルに対応するピクセル・データの読み込みを回避する。画像処理におけるこの節約が、グラフィックス・システムの性能を改善することになる。さらに、目標ビットマップがフレーム・バッファである場合、目標ビットマップ内の各ピクセルがたかだか一度に書き込まれるので、ちらつき効果が弱められる。また本発明は、シャドウ、グロー効果（ｇｌｏｗ ｅｆｆｅｃｔ）、及びそれと同種のものだけでなく、ウィンドウのフェーディング・イン及びフェーディング・アウトのような視覚効果を容易に実現することができる。
【００１４】
１つの実施例では、最後の更新以降に変化した最上層にタグを付けることにより、さらなる性能の向上が達成される。前から後ろに向かう合成を行う操作が、タグ付きの層に到達する前に終了する場合、最後の更新以降、同じデータを、出力ビットマップが既に保持しているので、出力ビットマップ（フレーム・バッファ）にその結果を書き込む必要はない。このように本発明は、そのような状況での不必要な書込み操作を回避し、そのために、特に出力がフレーム・バッファに書き込まれる場合、システム性能を向上させることができる。
【００１５】
１つの実施例では、最初に目標ビットマップを、その各タイルが描写のための同じ積重ねの層を保持している多くのタイルに、細分することにより、さらなる最適化が達成される。そのような細区分の実行によって、本発明は、ピクセル毎をベースにするよりも、タイル毎をベースにして、どの層が最終画像に寄付するかに関する決定を行うことができる。このことは、境界照合の工程を単純化し、工程の最内ループ中で為される必要のある演算の数を最小限にし、その結果、全体的な性能を向上させる。
【００１６】
本発明は、例えば、改良されたグラフィカル・ユーザ・インターフェースで、重なり合う半透明のウィンドウを効率的に描写するウィンドウ・システム内で、実現されることができる。
【００１７】
【発明を実施するための最良の形態】
【００１８】
好適な実施の態様に関する詳細な説明
では図１を参照しながら、本発明の１つの実施例の全体的な構成のブロック図が示される。この実施例では、システム１００が、中央処理装置及び／又はグラフィックス・プロセッサ１０１、並びにブラウン管（ＣＲＴ）又は液晶表示（ＬＣＤ）デバイスのようなディスプレイ１０５を持つ従来のパーソナルコンピュータ上で実現される。この技術分野では知られているように、本発明のステップは、コンピュータ内のプロセッサ１０１によって実行されるための、オペレーティング・システム内のソフトウェア、あるいはアプリケーション・ソフトウェアとして格納されることができる。例えば、システム１００は、ＭａｃＯＳオペレーティング・システムを実行するＡｐｐｌｅ社製のＭａｃｉｎｔｏｓｈRコンピュータ上で実現されてもよく、そしてそのソフトウェアが、オペレーティング・システム内のウィンドウ・サーバ・モジュールの一部を形成してもよい。
【００１９】
層データ１０３は、ディスプレイ１０５上に表示するために合成されるべきソース・イメージを表す。例えば、層１０３は、ウィンドウ、グラフィカル・ユーザ・インターフェース（ＧＵＩ）エレメント、写真、図、アニメーション、およびその他同種のもの、のビットマップ表現を含む。１つの実施例では、各層１０３が、いかなる任意の形状およびサイズであってもよいし、半透明な領域、透明な領域、および不透明な領域を、要求される任意の組合せで含んでいてもよい。１つの実施例では、各層１０３が、色（ＲＧＢ）値、アルファ値、およびフェード値を格納するための複数のデータ構造１０６−１０８を含む。いかなる数の層１０３が、システム１００によって処理用に提供されてもよい。
【００２０】
グラフィックス・プロセッサ１０１は、コンピュータの従来の中央処理装置（ＣＰＵ）として実装されてもよいし、グラフィックス処理専用のプロセッサであってもよい。１つの実施例におけるアキュムレータ１０２は、計算される値の一時記憶用のレジスタあるいは記憶場所である。下に記述されるように、１つ以上のアキュムレータ１０２が、提供され、１つの実施例において、本発明は、複数のアキュムレータ１０２を使用することによって、いくつかのピクセルを並列で処理することができる。
【００２１】
フレーム・バッファ１０４は、ランダム・アクセス・メモリ（ＲＡＭ）のようなメモリ領域であり、この技術分野では知られているように、それは表示データの格納用に予約されている。１つの実施例では、フレーム・バッファ１０４は、プロセッサ１０１がフレーム・バッファに結果を書き込んだ後、ディスプレイ１０５がフレーム・バッファ１０４の内容を出力できるように、ディスプレイ１０５に接続される。他の実施例では、プロセッサ１０１が、画像を、フレーム・バッファ１０４にではなく、メモリの他の領域（示されていない）、またはディスク（示されていない）、または他のあるストレージ・デバイスに書き込む。
【００２２】
では図２を参照して、本発明の出力の例が示される。３つの層１０３が、合成用にシステム１００への入力として提供される。ディスプレイ１０５に示されるような出力画像２０４は、互いに重なり合う３つの層１０３をすべて含む。図から見ることができるように、層１０３はいかなる任意の形状であってもよく、不透明、透明、及び（または）半透明な領域を、任意の組合せで含んでもよい。１つの実施例では、任意に形作られる画像が、透明な領域および不透明な領域の両方を持つ長方形の層として表わされることができるように、すべての層が長方形の領域として提供される。下にある画像は重なり合うエリアが透明であれば影響を受けないので、透明な層又はエリアの合成は重要ではない作業である。
【００２３】
１つの実施例では、各層１０３が複数のピクセルを含み、各ピクセルが色値を持つ。各ピクセルの色値は、（赤緑青つまりＲＧＢ色符号化スキームといったような）従来の色符号化スキームに従って色を表す。１つの実施例では、各ピクセルがまた、そのピクセルに対する相対的な透明度（あるいは不透明度）を表すアルファ値を持つ。そのような技術は、ピクセル毎をベースにした、各層の透明度に対する十分な制御を容易にし、任意に形作られた画像だけでなく、半透明な効果も可能にする。
【００２４】
図２の例に示されるように、本発明は、いくつかの半透明で複雑な形状をしたウィンドウを結合する出力を生成することができる。したがって本発明は、ユーザが下にあるエレメントを見ることができるように、重なり合うエレメント又はウィンドウが半透明である、グラフィック的に豊富なユーザ・インターフェースを持つスクリーン上でのウィンドウシステムを可能にするために使用されることができる。
【００２５】
では図３を参照して、本発明によるピクセルのトップダウン処理の例が示される。１つの実施例では、本発明が画像の各ピクセルを別々に処理する。別の実施例では、下で記述されるように、いくつかのピクセルが多くのアキュムレータを用いて、並列で処理される。
【００２６】
画像内の各ピクセル３０１に対して、１つ以上の層１０３が、ピクセル３０１の色値に寄与する。一般に、色値に寄与する層１０３は、処理されている画像ピクセルに関連する物理的な座標に対応するイメージ・データを保持している層１０３である。ピクセル３０１を処理する前に、アキュムレータ１０２がリセットされる。その後、層（複数）１０３のうちの１つの層内の寄与している各ピクセル３０１に対して、本発明は、画像ピクセル用の最終値を引き出すために、寄与しているピクセル３０１の色値およびアルファ値を蓄積する。
【００２７】
この技術分野では知られているように、各層１０３は、相対的な「垂直」位置を持つ。層１０３の垂直位置は、層が互いの上に積み重ねられる順番を概念的に表現したものである。したがって最終画像で、層Ｂが層Ａの一部を部分的に不明瞭にするウィンドウとして描写される場合、層Ｂは層Ａの「上にある」と見なされるだろう。
【００２８】
１つの実施例では、本発明は、トップダウンの順で、最初に蓄積される最上層１０３を持つ層（複数）１０３からピクセル・データを読取る。各ピクセルのデータが読取られると、それは、下でより詳細に記述されるような合成方法を用いて、アキュムレータ１０２の現在の値とマージされる。１つの実施例では、本発明が色値もアルファ値も蓄積する。すべての層１０３が処理されてしまう前に、蓄積されるアルファ値が完全な不透明度を示す場合、現在の層の下のいかなる層１０３も、既に処理された層１０３によって完全に見えなくさせられるので、現在のピクセルに対する処理は終了されてもよい。この方法で、本発明は、最終画像に寄与しない処理ピクセル・データを読み取って処理するステップを回避することができる。
【００２９】
いったん本発明がピクセル３０１に寄与するすべての層１０３を読み取ってしまうか、あるいは完全な不透明度が到達されたならば、アキュムレータ１０２内の値が出力される。１つの実施例では、その値が、フレーム・バッファ１０４にダイレクトに書き込まれる。色値の蓄積がアキュムレータ１０２で起こるので、フレーム・バッファ１０４への書き込み要求は１回だけであり、その結果、スクリーン上のディスプレイの（フレーム・バッファ１０４への複数回の書き込みが原因である）過度のちらつきが回避される。さらに、アキュムレータ１０２出力はフレーム・バッファ１０４にダイレクトに書き込まれることができるので、蓄積がアキュムレータ１０２で起こる以上、画像の一時記憶用の画面外のバッファは必要ではない。
【００３０】
では図６を参照しながら、１つの実施例による本発明の作業のフローチャートが示される。図６で示されるステップは、複数の層が対応するピクセルを持っている最終画像内の各ピクセルに対して実行される。プロセッサ１０１は、初期の色値およびアルファ値でアキュムレータ１０２を初期化する６０２。１つの実施例では、アキュムレータ１０２がプロセッサ１０１内のレジスタとして実装される。別の実施例では、図６のステップが多くのピクセルに対して同時に実行されるように、２つ以上のアキュムレータ１０２が提供される。
【００３１】
プロセッサ１０１は、描写されようとしているピクセルの位置に対応するピクセルを持つそれらの層の中から１つの層１０３を選択する６０３。１つの実施例では、最上層１０３がトップダウン処理を実現するために選択されるが、他の実施例では、いかなる層１０３が選択されてもよい。
【００３２】
プロセッサ１０１は、描写されようとしている画像ピクセルに対応する位置を持つ層１０３の中のピクセルを識別し、識別されたピクセルの色値をアキュムレータ１０２の現在値とマージする６０４。１つの実施例では、プロセッサ１０１は、また、識別されたピクセルのアルファ値をアキュムレータ１０２に格納されたアルファ値とマージする。
【００３３】
その後、プロセッサ１０１は、描写されようとしている画像ピクセルの色値に寄与することができる層がまだ残っているかどうかを判定する６０５。トップダウン処理が用いられている場合、１つの実施例では、この判定は、蓄積されたアルファ値が、完全な不透明度の達成を示しているかどうかをチェックすることによりなされる。完全な不透明度が達成された場合、その下にあるいかなるピクセルも、画像ピクセルの最終の色値に寄与することはできない。いかなる残りの層も寄与することができない場合、アキュムレータ１０２内の蓄積された色値が出力される６０６。代わりに、他の記憶場所またはストレージ・デバイスに出力が実行されてもよいが、１つの実施例では、その値がディスプレイ１０５上の表示用のフレーム・バッファ１０４に出力される。
【００３４】
ステップ６０５で、アキュムレータ１０２が完全な不透明度を示さないか、あるいは追加の層１０３が処理される必要があるという何か他の決定が為される場合、システムは、描写されようとしている画像ピクセルに対応するピクセルを持つ何等かの追加の層が存在しているかどうかを判定する６０７。もしそうでなければ、アキュムレータ１０２内に蓄積された色値が出力される６０６。
【００３５】
ステップ６０７で、追加の層１０３が残っている場合、プロセッサ１０１は、描写されようとしている画像ピクセルの位置に対応するピクセルを持つそれらの層の中から別の層１０３を選択する６０８。他の実施例では、任意の残りの層１０３が選択されてもよいが、１つの実施例では、トップダウン処理を実現するために、残りの層１０３の最上層が選択される。その後、プロセッサ１０１はステップ６０４に戻る。
【００３６】
完全な不透明度が達成されるか、あるいは、処理されようとしている画像ピクセルの色値に対して、いかなる残りの層１０３も寄付することができないという何か他の判定が為されるか、あるいは、いかなる層も残っていない状態になるまでは、ステップ６０４、６０５および６０７が繰り返される。
【００３７】
図６のステップは、必要に応じて、画像内の各ピクセルに対して繰り返される。ピクセルは任意の順で処理されてもよい。
１つの実施例では、ステップ６０３で、プロセッサ１０１が、描写されようとしているピクセル位置に対して、不透明なピクセルを保持している層を見つけるまで、（最上層から始めて）次に続く各層を通してループする。もしその最初の透明でないピクセルが完全に不透明であると判明する場合、いかなるマージ作業も実行せずに、その結果を直ちにフレーム・バッファに書き込むことができる。
【００３８】
ピクセルが完全に不透明ではない場合、融合及びマージの作業がステップ６０４で継続する。
１つの実施例では、ステップ６０４で、プロセッサ１０１は、Ｔ．ポーター等による１９８４年のＳＩＧＧＲＡＰＨ’８４という会報のページ２５３〜５９にある「デジタル画像の合成」の中で記述されているように、よく知られた合成技術によって色値およびアルファ値をマージする。では図７を参照しながら、色値及びアルファ値をマージする方法が示される。不透明度及び色値は、設定値をゼロにするによることによって初期化される７０１。第１の層が選択される７０２。完全な不透明が達成された場合、（不透明度が１．０のような事前に決められたしきい値に達する場合）、工程は終了する７０８。
【００３９】
完全な不透明が到達されないで、追加の層が存在する限り、ステップ７０３〜７０７が繰り返される。７０４で、ピクセルに対するフェード値は、方程式 
【００４０】
【数１】
2007304576.tif 000003
【００４１】
ただし、δn：層ｎに対する全体的なフェード値 αn（ｘ、ｙ）：層ｎ内の現在のピクセルの不透明度（アルファ値）である α：蓄積された不透明度（アルファ値）。
を用いて、決定される。
【００４２】
７０５で、ピクセルに対する色値は、方程式
【００４３】
【数２】
2007304576.tif 000004
【００４４】
【数３】
2007304576.tif 000005
【００４５】
【数４】
2007304576.tif 000006
【００４６】
ただし、ｒn（ｘ、ｙ）、ｇn（ｘ、ｙ）、ｂn（ｘ、ｙ）は層ｎ内の現在のピクセルの色値で、ｒ、ｇ、ｂは蓄積された色値、を用いて、フェード値によって調整され、アキュムレータに加えられる。
【００４７】
７０６で、ピクセルに対するフェード値は、
【００４８】
【数５】
2007304576.tif 000007
【００４９】
によって、不透明度アキュムレータに追加される。
７０７で、次の層が選択される（ｎが追加される）。
【００５０】
図７によって表される実施例で、本発明は、事前の乗算なしで入力層の値を格納し、蓄積された値を事前に乗算された形式で格納する。最終の色値が既に乗算された形であるので、この技術はループ内で実行される必要がある作業数を減少させる。
【００５１】
フェード値δnは、全体としての層の不透明度を計る。フェード値の使用は、本発明の実行にとって不可欠ではないけれども、それは、層のフェード・アウトまたは半透明のドラッギングのような効果を促進する。フェード値は、Ａｄｏｂｅ社製のＰｈｏｔｏＳｈｏｐのようないくつかのアプリケーション内で知られる。
【００５２】
上記の説明は、アキュムレータ１０２内で色値とアルファ値とをマージするための単に可能な１つの技術を表現している。当業者にとって明らかであるように、他の合成技術が用いられてもよい。１つの実施例では、それが適切であれば、各層は異なる合成方法に関連させられてもよい。
【００５３】
上で記述された技術は、Ｎがピクセルに寄与することができる層の数である場合、多くてもＮ＋１回の読み取り／書き込み操作（Ｎ回の読み取り、１回の書き込み）を用いて、画像ピクセルを生成できることがわかった。従来の技術システムは、一般に３（Ｎ−１）回の読み取り／書き込み操作を要求する（２（Ｎ−１）回の読み取り、（Ｎ−１）回の書き込み）。例えば、４つの層Ａ、Ｂ、ＣおよびＤが利用可能である場合、本発明は次の読み取り／書き込み操作を実行する。
【００５４】
・読み取りＡ 
・読み取りＢ 
・読み取りＣ 
・読み取りＤ 
・結果の書き込み
したがって、Ｎ＝４であれば、多くてもＮ＋１＝５回の操作が実行される。アキュムレータ１０２内に結果を蓄積することによって、読み取り／書き込み操作の総数が著しく減少させられる。さらに、本発明のピクセル毎のトップダウン・アプローチが、実行される作業数をさらに減少させる。
【００５５】
例えば、「ペインターズ・アルゴリズム（Ｐａｉｎｔｅｒ’ｓ Ａｌｇｏｒｉｔｈｍ）」として知られ、Ｆｏｌｅｙ等による１９９０年のＣｏｍｐｕｔｅｒ Ｇｒａｐｈｉｃｓ：Ｐｒｉｎｃｉｐｌｅｓ ａｎｄ Ｐｒａｃｔｉｃｅ（コンピュータグラフィックス：原理および実践）のページ６７３に記述されている１つの従来技術は、次のようにして４つの層を合成する。
【００５６】
・Ｃの読み取り 
・Ｄの読み取り 
・Ｃ＋Ｄの結果の書き込み 
・Ｂの読み取り 
・Ｃ＋Ｄの結果の読み取り 
・Ｂ＋Ｃ＋Ｄの結果の書き込み 
・Ａの読み取り 
・Ｂ＋Ｃ＋Ｄの結果の読み取り 
・Ａ＋Ｂ＋Ｃ＋Ｄの結果の書き込み
したがって、Ｎ＝４であれば、従来技術は３（Ｎ−１）＝９回の読み取り／書き込み操作を実行する。さらに、たとえ下にある層のうちのいくつかが、最終結果に寄与しなくても、９回の読み取り／書き込み操作がすべて実行されるが、本発明は、いくつかの層が寄与しない場合は、操作の数を減少させることができる。
【００５７】
読み取り／書き込み操作の数を減少させることに加えて、上記の例から分かるように、本発明は、関与する演算操作の数も減少させる。
１つの実施例では、さらに、最適化が以下のように達成される。システム１００は、前回のデータがフレーム・バッファ１０４に書き込まれて以来、変更された最上層１０３にタグをつけることができる。上に記述された前から後ろへ向かう（ｆｒｏｎｔ−ｔｏ−ｂａｃｋ）処理方法で実行している際に、もしプロセッサ１０１がタグの付いた層１０３に到達する前に終了するならば、フレーム・バッファ１０４は既に同じ値を保持しているので、フレーム・バッファ１０４に新しい画像ピクセルを書き込む必要はない。したがって、ビデオメモリへのアクセスが比較的遅いシステムでは、フレーム・バッファ１０４への不必要な書き込みを回避することにより、著しい性能の改善が達成される。
【００５８】
１つの実施例では、本発明が、図６に関して上で記述された方法を始める前に、前処理ステップで画像エリアを細分する。では図４を参照して、この実施例による画像細区分の例が示される。
【００５９】
画像４０１は、合成されるべき３つの層１０３ａ、１０３ｂおよび１０３ｃを含む。画像エリアはこのようにタイル４０２〜４２３へ細分されることができる。各タイルについては、所定の層の集合１０３が、タイル内のピクセルに影響を与えることができる。こうして、図４の例では、
・タイル４０２、４０３、４０５、４０６、４１０、４１１、４１７、４１８、４２１および４２３は、任意の層をアクセスせずに、（バックグラウンドのみで）描写され、
・タイル４０４、４０７および４１２は、層１０３ｃからのデータを用いて描写され、
・タイル４０８および４１３は、層１０３ｂおよび１０３ｃからのデータを用いて描写され、
・タイル４０９および４１９は、層１０３ｂからのデータを用いて描写され、
・タイル４１４は、層１０３ａ、１０３ｂおよび１０３ｃからのデータを用いて描写され、
・タイル４１５および４２０は、層１０３ａおよび１０３ｂからのデータを用いて描写され、そして
・タイル４１６および４２２は、層１０３ａからのデータを用いて描写される。
【００６０】
このように、各タイルは積重ねが同じである層を保持し、最終画像を描写するために結合される。この方法では、どの層が所定のピクセルに対する値に寄与しているかについての判定ステップのほとんどが、最も内側のループの外で実行されるが、それは、そのような判定が所定のタイル内のすべてのピクセルにとって一定であるからである。そのことが、そのような判定ステップが実行される回数を減少させるので、境界照合の工程が単純化され、性能が向上される。
【００６１】
では図５を参照しながら、本発明の１つの実施例の細区分技術の例が示される。タイル５０２は事前に細分されたタイルまたは全体画像を表す。層５０１がタイル５０２の上に重ねられると、タイル５０２が新しいタイル５０３〜５０７に細区分されることになる。一般的に言えば、このタイル細区分操作は、以下のように実行される。つまり、タイル５０２を切り抜く少なくとも１辺を持つ各層５０１に対して、タイル５０２は、層５０１の上方の境界線および下方の境界線をタイル５０２の左端および右端まで延長することにより細分される。その結果生じるタイル５０３〜５０７は、個々のピクセルを処理する時の、プロセッサ１０１による後の検索に備えてタイル・リスト内に格納される。新しいタイル５０２〜５０７のうちのいくつかは、層５０１が完全にタイル５０２の内部にあるわけではない場合のように、ゼロの幅または高さを持つこともある。そうである場合、そのような形を成さない長方形は、タイル・リスト内には格納されない。タイル細区分は、図８と関連させて、より詳細に下で記述される。
【００６２】
他の結果を生み出す、タイル細区分の他の技術が、実行されてもよい。水平走査線に沿った方向に向かうピクセル横断アルゴリズムであるために、垂直切断の数を最小にする細区分が有利であり、水平切断の数はそれほど重要でないことが発見された。
【００６３】
１つの実施例では、実際の合成が始まる前に、タイル・リストが、ｙ−オーダにソートされる。このステップの実行によって、システムはより整然としたやり方で更新を実行し、多くの更新がすばやく続けて要請される場合に生じることがある、目に見える「テアリング（ｔｅａｒｉｎｇ）」を減少させることができる。
【００６４】
１つの実施例で、最初のタイル細区分が実行された後、タイル・リストが点検され、合成する段階でのタイル・カウントを減少させるために、隣接するタイルがなるべく連結される。図４の例では、タイル４０２、４０３、４０５、４０６、４１０、４１１、４１７、４１８、４２１、及び４２３が１つのタイルにマージされることができ、タイル４０４、４０７および４１２が第２のタイルにマージされることができ、以下同様である。タイルの連結は、図９と関連させて、より詳細に下で記述される。
【００６５】
１つの実施例では、他の層がタイルと交差する時でも、さらなる細区分が行われるべきでないことを示す、「凍結（ｆｒｏｚｅｎ）」というマークを特定のタイルに付けることができる。この技術は、不透明な層の下に存在する層はすべて見ることができないため、さらなる細区分が必要とされないので、完全に不透明な層の一部を保持するタイルが作成された場合に、さらなる細区分を回避するのに役立つ。
【００６６】
タイルの細区分が、図６と関連して上で記述された方法で結合される場合、特定のタイル内のピクセルはすべて、次のタイルに進む前に処理されることができる。この方式では、どの層が出力値に寄付するかに関する決定が、ピクセル・レベルではなくタイル・レベルで実行されることができ、それにより、実行される操作の数を減少させることができる。さらに、１つの実施例では、特別な場合のアルゴリズムが、合成されるべき層の特定の結合のために開発され、それらの結合を保持するタイルに適用されることができる。
【００６７】
１つの実施例で、上に記述されるように、いくつかのピクセルが同時に処理されてもよい。例えば、１つの実施例では、ＡｌｔｉＶｅｃまたはＭＭＸが可能なプロセッサのように、８つの値を同時に蓄積することができるプロセッサ１０１を用いて、８つのピクセルが並列で処理される。またその並行処理は、本発明がインテル社製のＩＡ−６４アーキテクチャのような多くの実行ユニットを持つシステム上に実装される場合にも有利となる。
【００６８】
では図８を参照しながら、本発明の１つの実施例に従う、タイル細区分を描くフローチャートが示される。システムは、スクリーンのエリアを表わす単一のタイルで始まり、次に、
【００６９】
【数６】
2007304576.tif 000008
【００７０】
をコールすることによりトップダウンで層を追加し、必要に応じてタイル・リストを延長する。上に記述されるように、不透明（ｏｐａｑｕｅ）フラグはタイルを凍結するために用いられる。
【００７１】
図８のフローチャートで示されるように、切断タイル（ｃｕｔＴｉｌｅｓ）ルーチンが実装される。またあるのであれば次のタイルが選択されることで８０２、プロセッサ１０１が始まるように、
1176185827601_20
のステップは画像内に存在する各々のタイルに対して繰り返される。タイルが凍結されている場合８０３、またはタイルが切断タイルへのコールで指定されるエリアの完全に外部にある場合８０４、プロセッサ１０１は、まだタイルが存在するかを判定し８１０、次のタイルに進む８０２。これ以上のタイルが存在しない場合、工程は終了する８１１。
【００７２】
タイルが完全に指定されたエリア内にある場合８０５、タイルに対応する新しい層が作成され８０６、もしそのエリアが不透明である場合は、凍結が指定される。
【００７３】
もしタイルが指定されたエリアの完全に内側でもなく、完全に外部でもない場合、重なりが存在する。タイルの重なりが判定されると８０７、それに従って、重なり合っている領域を表すために新しいタイルが作成される８０８。座標値が新しいタイルに割り当てられる８０９。
【００７４】
そのタイルが処理されたならば、プロセッサ１０１は、追加のタイルが存在するかどうかを判定し８１０、存在するならば、次のタイルを選択するために８０２に戻る。
【００７５】
上に記述されるように、１つの実施例では、最初のタイル細区分が実行された後、タイル・リストが点検され、合成する段階でのタイル・カウントを減少させるために、隣接するタイルがなるべく連結される。では図９を参照しながら、１つの実施例に従う、タイルを連結する方法を描くフローチャートが示される。
【００７６】
プロセッサ１０１は、処理されるべきタイルを選択する９０１。９０２で、そのタイルが積重ねが同じである層を持つ別のタイルｔに隣接しているとプロセッサ１０１が判定する場合、そのタイル端はタイルｔのエリアを含めるよう調整され９０３、タイルｔは削除される９０４。処理されるべきさらなるタイルがある場合９０５、プロセッサ１０１は９０２に戻る。
【００７７】
１つの実施例では、上に記述された発明が、グラフィカル・ユーザ・インターフェース内の重なり合う半透明のウィンドウを表示することができるウィンドウ・システムを実現するために用いられる。図２に示されるように、各ウィンドウは１つ以上の層として表される。重なり合っているタイルに対して上に記述されたように、ウィンドウに関連する色値およびアルファ値が合成される。アプリケーションが、その補助記憶に相当するビットマップをその層に描く時、及びスクリーン上に更新を要請する時、本発明は、上に記述された合成技術を用いて、フレーム・バッファの対応する部分を再度組み立てることによりスクリーンを更新する。ウィンドウを開くステップ、閉じるステップ、サイズを変更するステップ、あるいは移動させるステップが、（それが用いられる場合に）上に記述されたタイル細区分の方法を引き起こす引き金になる。
【００７８】
そのようなウィンドウ・システムでは、上に記述されるようなフェード値が、ウィンドウのフェード・インおよびフェード・アウトを実現するために用いられることができる。これは、開かれたり、あるいは閉じられたりするウィンドウに対応する層のフェード値を徐々に変化させることにより達成される。
【００７９】
また上で記述された技術を用いるウィンドウ・システムは、カーソルが位置する最上のウィンドウが、通常はカーソル駆動されるイベントのターゲットである、従来の重なり合うウィンドウ・システムに関連するものとは異なるイベント・ルーティング・スキーム（ｅｖｅｎｔ ｒｏｕｔｉｎｇ ｓｃｈｅｍｅ）を実現する。現在のシステム中で、例えば、ユーザがマウス・クリックを実行する場合、マウスクリック・イベントは、必ずしもカーソルが位置する最上のウィンドウではない特定のウィンドウに送られる。１つの実施例では、カーソルが位置する最上の不透明なウィンドウが、マウス・イベントのターゲットである。別の実施例では、いくつかの層がイベントを全く受理しないように、指示されてもよい、例えば、ウィンドウのシャドウを保持する層はイベントを受理してはならない。当業者に明らかであるように、代わりのイベント・ルーティング・スキームもまた、本発明に従って、実装されるウィンドウ・システムと併せて、使用されることができる。
【００８０】
上記の説明から、ここに開示された本発明が、ディスプレイ・システム内の半透明で複雑な形状の層を描写するための斬新で有利なシステムおよび方法を提供することは明らかである。先の説明は、本発明の単に典型的な方法および実施例のみを開示し記述している。当業者では理解できるように、本発明はその精神あるいは本質的な特徴から外れない他の特定の形式で具体化されることができる。従って、本発明の開示は、制限するものではなく、次の特許請求の範囲の中で述べられる本発明の適用範囲を説明するよう意図される。
【図面の簡単な説明】
【００８１】
【図１】本発明の実施例の全体的な構成のブロック図である。
【図２】本発明の出力の例を示す図である。
【図３】本発明によるピクセルのトップダウン処理を示す図である。
【図４】本発明の１つの実施例によるタイル細区分の例を示す図である。
【図５】本発明の１つの実施例によるタイル細区分の例を示す図である。
【図６】本発明の１つの実施例の作業を示すフローチャートである。
【図７】本発明の１つの実施例による色およびアルファをマージを示すフローチャートである。
【図８】本発明の１つの実施例によるタイル細区分を示すフローチャートである。
【図９】本発明の１つの実施例によるタイルを連結する方法を示すフローチャートである。
【図１】
2007304576.tif 000009
【図２】
2007304576.tif 000010
【図３】
2007304576.tif 000011
【図４】
2007304576.tif 000012
【図５】
2007304576.tif 000013
【図６】
2007304576.tif 000014
【図７】
2007304576.tif 000015
【図８】
2007304576.tif 000016
【図９】
2007304576.tif 000017