(57)【特許請求の範囲】
【請求項１】
３次元（３Ｄ）グラフィックスを生成する方法であって、
各スキャンラインごとに、スキャンラインの第１の位置座標に関して複数のテクスチャ値のそれぞれに対してスキャンラインの開始位置で１度だけスキャンライン勾配をプロセッサによって計算するステップと、
スキャンラインの第２の位置座標に関してスキャンラインの画素のそれぞれに対して画素勾配をプロセッサによって計算するステップと、
スキャンライン勾配の２乗の和と画素勾配の２乗の和をプロセッサによって比較するステップと、
上記２つの２乗の和のうち大きい方が対応する画素に対する最大スケール・ファクタであると、プロセッサによって選択するステップと、
この最大スケール・ファクタに基づいて画素をレンダリングする際に使用する１つのテクスチャ・マップを複数のテクスチャ・マップからプロセッサによって選択するステップと、
この選択されたテクスチャ・マップを使用して、スキャンラインのすべての画素をレンダリングするステップとを含む方法。
【請求項２】
スキャンライン勾配（ｃ１およびｃ２）が、プロセッサによってスキャンラインの開始位置で１度だけスキャンラインのＸ座標に関して２つのテクスチャ値（ｕおよびｖ）のそれぞれについて計算され、スキャンライン勾配が次式を使用して計算され、
ｃ１＝（ｑ*ｄｕp／ｄｘ−ｕp*ｄｑ／ｄｘ）
ｃ２＝（ｑ*ｄｖp／ｄｘ−ｖp*ｄｑ／ｄｘ）
上式で、＊は乗算記号であり、ｕおよびｖがテクスチャ値であり、ｘおよびｙがテクセルの画面上での位置値であり、ｑがｑ軸に沿ってのゼロ点からの距離値である、請求項１に記載の方法。
【請求項３】
スキャンラインの各画素ごとに１度だけ、スキャンラインの第２の位置座標に対する複数のテクスチャ値のそれぞれの画素勾配がプロセッサによって計算され、前記画素勾配が、最大スケール・ファクタを計算するためにプロセッサによって使用される請求項１に記載の方法。
【請求項４】
画素勾配（ｃ３およびｃ４）が、スキャンラインのＹ座標に関して２つのテクスチャ値（ｕおよびｖ）のそれぞれについてプロセッサによって計算され、スキャンライン画素勾配が次式を使用して計算され、
ｃ３＝（ｑ*ｄｕp／ｄｙ−ｕp*ｄｑ／ｄｙ）
ｃ４＝（ｑ*ｄｖp／ｄｙ−ｖp*ｄｑ／ｄｙ）
上式で、＊は乗算記号であり、ｕおよびｖがテクスチャ値であり、ｘおよびｙがテクセルの画面位置値であり、ｑがｑ軸に沿ってのゼロ点からの距離値である、請求項３に記載の方法。
【請求項５】
最大スケール・ファクタがＲｈｏであり、Ｒｈｏが送信元テクセルと画面画素との最大の比であり、Ｒｈｏが、次式を使用してプロセッサによって計算される、
Ｒｈｏ＝ＭＡＸ［（ｃ１*ｃ１＋ｃ２*ｃ２），（ｃ３*ｃ３＋ｃ４*ｃ４）］／（ｑ*ｑ）
上式で、ｃ１，ｃ２およびｃ３，ｃ４はそれぞれ請求項２および請求項４に記載のスキャンライン勾配、画素勾配であり、＊は乗算記号であり、ｑがｑ軸に沿ってのゼロ点からの距離値である、請求項４に記載の方法。
【請求項６】
画素勾配の導関数が、プロセッサによって各スキャンラインごとに、スキャンラインの開始位置で１度だけ複数のテクスチャ値のそれぞれについて計算され、前記画素勾配の前記導関数が、最大スケール・ファクタを計算するためにプロセッサによって使用される請求項１に記載の方法。
【請求項７】
画素勾配の導関数（ｄｅｌｔａ ｃ３およびｄｅｌｔａ ｃ４）が、プロセッサによって２つのテクスチャ値（ｕおよびｖ）のそれぞれについて計算され、前記画素勾配の前記導関数が次式を使用して計算され、
ｄｅｌｔａ ｃ３＝（ｄｑ／ｄｘ*ｄｕp／ｄｙ−ｄｕp／ｄｘ*ｄｑ／ｄｙ）
ｄｅｌｔａ ｃ４＝（ｄｑ／ｄｘ*ｄｖp／ｄｙ−ｄｖp／ｄｘ*ｄｑ／ｄｙ）
上式で、ｃ３，ｃ４は請求項４に記載の画素勾配であり、＊は乗算記号であり、ｕおよびｖがテクスチャ値であり、ｘおよびｙがテクセルの画面位置値であり、ｑがｑ軸に沿ってのゼロ点からの距離値である、請求項６に記載の方法。
【請求項８】
さらに、各テクスチャ・マップが異なる解像度でレンダリングされる、複数のテクスチャのそれぞれについて複数のテクスチャ・マップをプロセッサによって生成するステップを含む請求項１に記載の方法。
【請求項９】
第１の位置座標がＸ座標であり、第２の位置座標がＹ座標である請求項１に記載の方法。
【請求項１０】
さらに、詳細レベル（ＬＯＤ）をプロセッサによって計算するステップを含み、
ＬＯＤ＝ｌｏｇ2（Ｒｈｏ）であり、前記ＬＯＤが、画素をレンダリングするためのテクスチャ・マップを選択するために使用される請求項１に記載の方法。
【請求項１１】
メモリと、
メモリに結合され、３次元（３Ｄ）グラフィックスを生成するプロセッサ・サブシステムとを備え、
各スキャンラインごとに、スキャンラインの第１の位置座標に関して複数のテクスチャ値のそれぞれに対してスキャンラインの開始位置で１度だけスキャンライン勾配がプロセッサ・サブシステムによって計算され、
スキャンラインの第２の位置座標に関してスキャンラインの画素のそれぞれに対して画素勾配が前記プロセッサ・サブシステムによって計算され、
スキャンライン勾配の２乗の和と画素勾配の２乗の和をプロセッサ・サブシステムによって比較し、
上記２つの２乗の和のうち大きい方が対応する画素に対する最大スケール・ファクタであると、プロセッサ・サブシステムによって選択し、
この最大スケール・ファクタに基づいて画素をレンダリングする際に使用する１つのテクスチャ・マップを複数のテクスチャ・マップからプロセッサ・サブシステムによって選択し、
この選択されたテクスチャ・マップを使用して、スキャンラインのすべての画素をプロセッサ・サブシステムによってレンダリングするコンピュータ・システム。
【請求項１２】
プロセッサ・サブシステムが、スキャンラインの開始位置で１度だけ、スキャンラインのＸ座標に関して２つのテクスチャ値（ｕおよびｖ）のそれぞれのスキャンライン勾配（ｃ１およびｃ２）を計算し、スキャンライン勾配が次式を使用して計算され、
ｃ１＝（ｑ*ｄｕp／ｄｘ−ｕp*ｄｑ／ｄｘ）
ｃ２＝（ｑ*ｄｖp／ｄｘ−ｖp*ｄｑ／ｄｘ）
上式で、＊は乗算記号であり、ｕおよびｖがテクスチャ値であり、ｘおよびｙがテクセルの画面位置値であり、ｑがｑ軸に沿ってのゼロ点からの距離値である、請求項１１に記載のコンピュータ・システム。
【請求項１３】
プロセッサ・サブシステムが、スキャンラインの各画素ごとに１度だけ、スキャンラインの第２の位置座標に対する複数のテクスチャ値のそれぞれの画素勾配を計算し、前記画素勾配が、最大スケール・ファクタを計算するためにプロセッサ・サブシステムによって使用される請求項１１に記載のコンピュータ・システム。
【請求項１４】
画素勾配（ｃ３およびｃ４）が、スキャンラインのＹ座標に関して２つのテクスチャ値（ｕおよびｖ）のそれぞれについてプロセッサ・サブシステムによって計算され、スキャンライン画素勾配がプロセッサ・サブシステムによって次式を使用して計算され、
ｃ３＝（ｑ*ｄｕp／ｄｙ−ｕp*ｄｑ／ｄｙ）
ｃ４＝（ｑ*ｄｖp／ｄｙ−ｖp*ｄｑ／ｄｙ）
上式で、＊は乗算記号であり、ｕおよびｖがテクスチャ値であり、ｘおよびｙがテクセルの画面位置値であり、ｑがｑ軸に沿ってのゼロ点からの距離値である、請求項１３に記載のコンピュータ・システム。
【請求項１５】
最大スケール・ファクタがＲｈｏであり、Ｒｈｏが送信元テクセルと画面画素との最大の比であり、Ｒｈｏが、プロセッサ・サブシステムによって次式を使用して計算される、
Ｒｈｏ＝ＭＡＸ［（ｃ１*ｃ１＋ｃ２*ｃ２），（ｃ３*ｃ３＋ｃ４*ｃ４）］／（ｑ*ｑ）
上式で、ｃ１，ｃ２およびｃ３，ｃ４はそれぞれ請求項１２および請求項１４に記載のスキャンライン勾配、画素勾配であり、＊は乗算記号であり、ｑがｑ軸に沿ってのゼロ点からの距離値である、請求項１４に記載のコンピュータ・システム。
【請求項１６】
プロセッサ・サブシステムが、各スキャンラインごとに、スキャンラインの開始位置で１度だけ、複数のテクスチャ値のそれぞれの画素勾配の導関数を計算し、前記画素勾配の前記導関数が、最大スケール・ファクタを計算するためにプロセッサ・サブシステムによって使用される請求項１１に記載のコンピュータ・システム。
【請求項１７】
プロセッサ・サブシステムが、２つのテクスチャ値（ｕおよびｖ）のそれぞれについて画素勾配の導関数（ｄｅｌｔａ ｃ３およびｄｅｌｔａ ｃ４）を計算し、前記画素勾配の前記導関数がプロセッサ・サブシステムによって次式を使用して計算され、
ｄｅｌｔａ ｃ３＝（ｄｑ／ｄｘ*ｄｕp／ｄｙ−ｄｕp／ｄｘ*ｄｑ／ｄｙ）
ｄｅｌｔａ ｃ４＝（ｄｑ／ｄｘ*ｄｖp／ｄｙ−ｄｖp／ｄｘ*ｄｑ／ｄｙ）
上式で、ｃ３，ｃ４は請求項１５に記載の画素勾配であり、＊は乗算記号であり、ｕおよびｖがテクスチャ値であり、ｘおよびｙがテクセルの画面位置値であり、ｑがｑ軸に沿ってのゼロ点からの距離値である、請求項１６に記載のコンピュータ・システム。
【請求項１８】
プロセッサ・サブシステムがさらに、各テクスチャ・マップが異なる解像度でレンダリングされる、複数のテクスチャのそれぞれについて複数のテクスチャ・マップを生成し、
ＬＯＤ＝ｌｏｇ2（Ｒｈｏ）であり、画素をレンダリングするためのテクスチャ・マップを選択するために使用される詳細レベル（ＬＯＤ）を、計算するように構成される請求項１１に記載のコンピュータ・システム。
【請求項１９】
３次元（３Ｄ）グラフィックスを生成するステップをコンピュータに実行させるプログラムを記録したコンピュータ読み取り可能な記録媒体であって、前記ステップが、
各スキャンラインごとに、スキャンラインの第１の位置座標に関して複数のテクスチャ値のそれぞれに対してスキャンラインの開始位置で１度だけスキャンライン勾配を計算するステップと、
スキャンラインの第２の位置座標に関してスキャンラインの画素のそれぞれに対して画素勾配を計算するステップと、
スキャンライン勾配の２乗の和と画素勾配の２乗の和を比較するステップと、
上記２つの２乗の和のうち大きい方を対応する画素に対する最大スケール・ファクタであると、選択するステップと、
この最大スケール・ファクタに基づいて画素をレンダリングする際に使用する１つのテクスチャ・マップを複数のテクスチャ・マップから選択するステップと、
この選択されたテクスチャ・マップを使用して、スキャンラインのすべての画素をレンダリングするステップとを含むコンピュータ読み取り可能な記録媒体。
【請求項２０】
前記プログラムが、コンピュータに、スキャンラインの開始位置で１度だけスキャンラインのＸ座標に関して２つのテクスチャ値（ｕおよびｖ）のそれぞれのスキャンライン勾配（ｃ１およびｃ２）を計算させ、スキャンライン勾配が次式を使用して計算され、
ｃ１＝（ｑ*ｄｕp／ｄｘ−ｕp*ｄｑ／ｄｘ）
ｃ２＝（ｑ*ｄｖp／ｄｘ−ｖp*ｄｑ／ｄｘ）
上式で、＊は乗算記号であり、ｕおよびｖがテクスチャ値であり、ｘおよびｙがテクセルの画面位置値であり、ｑがｑ軸に沿ってのゼロ点からの距離値である、請求項１９に記載のコンピュータ読み取り可能な記録媒体。
【請求項２１】
前記プログラムが、コンピュータに、スキャンラインの各画素ごとに１度だけ、スキャンラインの第２の位置座標に対する複数のテクスチャ値のそれぞれの画素勾配を計算させ、前記画素勾配が、最大スケール・ファクタを計算するために使用される請求項１９に記載のコンピュータ読み取り可能な記録媒体。
【請求項２２】
前記プログラムが、コンピュータに２つのテクスチャ値（ｕおよびｖ）のそれぞれについて画素勾配（ｃ３およびｃ４）を計算させ、スキャンライン画素勾配が次式に従って計算され、
ｃ３＝（ｑ*ｄｕp／ｄｙ−ｕp*ｄｑ／ｄｙ）
ｃ４＝（ｑ*ｄｖp／ｄｙ−ｖp*ｄｑ／ｄｙ）
上式で、＊は乗算記号であり、ｕおよびｖがテクスチャ値であり、ｘおよびｙがテクセルの画面位置値であり、ｑがｑ軸に沿ってのゼロ点からの距離値である、請求項２１に記載のコンピュータ読み取り可能な記録媒体。
【請求項２３】
最大スケール・ファクタがＲｈｏであり、Ｒｈｏが送信元テクセルと画面画素との最大の比であり、前記プログラムが、コンピュータに、次式に従ってＲｈｏを計算させる、
Ｒｈｏ＝ＭＡＸ［ｓｑｒｔ（ｃ１*ｃ１＋ｃ２*ｃ２），ｓｑｒｔ（ｃ３*ｃ３＋ｃ４*ｃ４）］／（ｑ*ｑ）
上式で、ｃ１，ｃ２およびｃ３，ｃ４はそれぞれ請求項２０および請求項２２に記載のスキャンライン勾配、画素勾配であり、＊は乗算記号であり、ｑがｑ軸に沿ってのゼロ点からの距離値である、請求項２２に記載のコンピュータ読み取り可能な記録媒体。
【請求項２４】
前記命令がシステムに、各スキャンラインごとに、スキャンラインの開始位置で１度だけ、複数のテクスチャ値のそれぞれの画素勾配の導関数を計算させ、前記画素勾配の前記導関数が、最大スケール・ファクタを計算するために使用される請求項１９に記載のコンピュータ読み取り可能な記録媒体。
【請求項２５】
前記プログラムが、コンピュータに、２つのテクスチャ値（ｕおよびｖ）のそれぞれについて画素勾配の導関数を計算させ、前記画素勾配の前記導関数が次式に従って計算され、
ｄｅｌｔａ ｃ３＝（ｄｑ／ｄｘ*ｄｕp／ｄｙ−ｄｕp／ｄｘ*ｄｑ／ｄｙ）
ｄｅｌｔａ ｃ４＝（ｄｑ／ｄｘ*ｄｖp／ｄｙ−ｄｖp／ｄｘ*ｄｑ／ｄｙ）
上式で、ｃ３，ｃ４は請求項２２に記載の画素勾配であり、＊は乗算記号であり、ｕおよびｖがテクスチャ値であり、ｘおよびｙがテクセルの画面位置値であり、ｑがｑ軸に沿ってのゼロ点からの距離値である、請求項２４に記載のコンピュータ読み取り可能な記録媒体。
【請求項２６】
前記プログラムが、コンピュータにさらに、
各テクスチャ・マップが異なる解像度でレンダリングされる、複数のテクスチャのそれぞれについて複数のテクスチャ・マップを生成するステップと、
ＬＯＤ＝ｌｏｇ2（Ｒｈｏ）であり、画素をレンダリングするためのテクスチャ・マップを選択するために使用される詳細レベル（ＬＯＤ）を、計算するステップを実行させる請求項１９に記載のコンピュータ読み取り可能な記録媒体。
【請求項２７】
最大スケール・ファクタがＲｈｏであり、Ｒｈｏが送信元テクセルと画面画素との最大の比であり、前記プログラムが、コンピュータに、次式を使用してＲｈｏを計算させる、
Ｒｈｏ＝ＭＡＸ［（ｃ１*ｃ１＋ｃ２*ｃ２），（ｃ３*ｃ３＋ｃ４*ｃ４）］／（ｑ*ｑ）
上式で、ｃ１，ｃ２およびｃ３，ｃ４はそれぞれ請求項２０および請求項２２に記載のスキャンライン勾配、画素勾配であり、＊は乗算記号であり、ｑがｑ軸に沿ってのゼロ点からの距離値である、請求項２２に記載のコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
（発明の分野）
本発明は、コンピュータ・グラフィックスの分野に関する。詳細には、本発明は画素ごとのＭＩＰマッピングおよび三線フィルタリングの改良された方法および装置を開示する。
【０００２】
（背景）
マルチメディア・グラフィックスは通常、画面または陰極線管上に配置される独立に制御される小さなドット、または画素の集合として画像を処理することによって生成される。コンピュータ・グラフィック画像は通常、背景画像上にレンダリングされたいくつかの対象物体で構成される。それぞれの対象物体は複数の画素からなる。レンダリング中、複合技法を使用して、対象物体をすでに生成された対象物体と組み合わせることができ、この場合、複合とは、画像同士を重ね合わせるか、あるいは混合することによって複数の画像を組み合わせることである。複合画像では、各画素の値は画像成分から計算される。
【０００３】
３次元（３Ｄ）コンピュータ・グラフィックスは一般に、豊富な色、テクスチャ、正しい視点、および影付けを用いるグラフィックス環境を示す。典型的な３Ｄグラフィックス・システムは一般に、コンピュータ・グラフィックス開発者により優れた、より現実的なグラフィックス環境を作成させる一連の技法を実施する。これらの技法のいくつかを以下に詳しく説明する。
【０００４】
３Ｄ場面の構成単位は多角形である。多角形はレンダリングされた画素を使用して生成される平坦な形状である。たとえば、様々な形状を作成するために三角形が頻繁に使用される。多角形は、平坦に見える単一の色を有する画素を使用するか、あるいは距離や場面の照明に基づいて少しずつ暗く見えるように色が変化するようにシェーディングが施された画素を使用してレンダリングすることができる。
【０００５】
画像を形成する三角形を構成する際、各頂点または座標は、特定のカラー・モデルの対応する色値を有する。カラー・モデルは、３Ｄ色座標系と、特定の色域内のすべての色が存在する座標系内の可視サブセットとで表すことができる。この場合、色域とはすべての可視色度のサブセットである。たとえば、赤（Ｒ）、緑（Ｇ）、青（Ｂ）のカラー・モデル（ＲＧＢ）は３Ｄデカルト座標系の単位立方体サブセットである。カラー・モデルの目的は、ある色域内で色を好都合に指定することを可能にすることである。ＲＧＢ原色は、各原色の個々の寄与が互いに加算されて結果的な画素が生成されるという点で加法原色である。複合マルチメディア画像内の各画素の色値は、画像成分からある方法で計算される。
【０００６】
テクスチャ・マッピングは、３Ｄ開発者が、ビットマップ画像ファイルをスケーリングし、多角形上にマッピングすることによって現実的で、細部まで表現された印象的な場面を作成することができる技法である。単に多角形を赤くシェーディングする代わりに、テクスチャ・マッピングを使用すれば、現実的なレンガ壁のように見せることができる。
【０００７】
Ｍｕｌｔｕｍ  ｉｎ  ｐａｒｖｏ（ＭＩＰ）マッピングは、テクスチャ・マッピングの可視品質を改善し、同時に性能を最適化するために使用される技法である。この技法は、各テクスチャ・マップが異なる解像度でレンダリングされた、複数のテクスチャ・マップを各テクスチャごとに有することによって機能する。この場合、様々なテクスチャ・マップを使用して画像が様々な距離に表される。双線形フィルタリングを使用してテクスチャ・マッピングの可視品質を改善することもできる。双線形フィルタリングは、テクスチャ・マップから得た４つの取り囲んでいるテクセルを使用して、３Ｄ空間内の任意の所与の画素の値をより厳密に計算する。テクセルとはテクスチャ・マップ内のドットであり、それに対して画素とは画面上のドットを指す。
【０００８】
三線フィルタリング（trilinear filtering ）は高度なフィルタリング技法であり、第３の次元へのフィルタリングを使用する。三線フィルタリングを用いた場合、結果として得られる画素は、２つの最も近くのＭＩＰマップから得た４つの取り囲んでいるテクセルを平均した値である。三線フィルタリングでは、テクスチャ・マッピングの可視品質が向上するが、双線形フィルタリングとは異なり１画素当たり４回のメモリ読取りではなく１画素当たり８回のメモリ読取りと、どのＭＩＰマップから読み取るべきかを判定するための計算とが必要になる。これを正確に計算するには非常にコストがかかる。この計算には、詳細レベル（ＬＯＤ）の計算が含まれる。この場合、次式が成立する。
【数１】
0004160261.tif 000002
および
ＬＯＤ＝ｌｏｇ2Ｒｈｏ
平方根を求めることを回避するように簡略化すると、これらの数式は次式のようになる。
【数２】
0004160261.tif 000003
および
【数３】
0004160261.tif 000004
【０００９】
各画素ごとにＲｈｏ’を正確に計算するためには、乗算器および加算器を使用してｄｕ／ｄｘ、ｄｖ／ｄｘ、ｄｕ／ｄｙ、およびｄｖ／ｄｙを計算する。追加の乗算器および加算器を使用してこれらの値のそれぞれの２乗を計算する。極めて高い処理機能を有するシステムでは、４回の追加のメモリ読取りを実行するコストが三線フィルタリングを制限することはない。しかし、パーソナル・コンピューティング環境など、より処理能力の低い環境では、三線フィルタリングを実施すると必ず性能に影響が及ぶ。したがって、性能に影響を与えない三線フィルタリングを行うための改良された費用効果の高い方法が極めて望ましい。
【００１０】
（発明の概要）
各スキャンラインの開始位置でのみある項を計算して、グラフィックスをレンダリングする際に実行される計算の数を削減することによって三線フィルタリングの性能が改善される、画素ごとのＭＩＰマッピングおよび三線フィルタリングのための方法および装置を提供する。一実施態様では、各スキャンラインの開始位置で１度だけ、スキャンラインのｘ座標に対する２つのテクスチャ値のそれぞれのスキャンライン・グラジェント（gradient：勾配）が計算される。各スキャンラインの開始位置でのスキャンライン勾配計算の後で、スキャンラインのｙ座標に対してスキャンラインの各画素ごとに画素勾配が計算される。スキャンライン勾配の２乗の和と画素勾配の２乗の和とが比較され、この２つの数量のうちの大きい方が、対応する画素の最大Ｒｈｏ定数項として選択される。最大Ｒｈｏ定数を使用して、スキャンラインの各画素ごとに詳細レベル（Level of Detail:ＬＯＤ）が計算される。各画素のＬＯＤ値を使用して、対応する画素をレンダリングするためのテクスチャ・マップが選択される。
【００１１】
代替実施態様では、各スキャンラインの開始位置で１度だけ、２つのテクスチャ値のそれぞれのスキャンライン勾配が計算され、各スキャンライン開始位置でのスキャンライン勾配計算の後で、スキャンラインのｙ座標に対してスキャンラインの第１の画素に対して２つのテクスチャ値のそれぞれについて画素勾配が計算される。画素勾配に関する導関数が計算され、この導関数を使用して画素勾配が求められ、それによって各画素ごとの画素勾配の計算が不要になる。スキャンライン勾配の２乗の和と画素勾配の２乗の和とが比較され、この２つの量のうちの大きい方が、対応する画素の最大Ｒｈｏ定数項として選択される。最大Ｒｈｏ定数を使用してＬＯＤが計算され、各画素のＬＯＤ値を使用して、対応する画素をレンダリングするためのテクスチャ・マップが選択される。
【００１２】
添付の図面では、本発明を制限としてではなく一例として示す。図面で、同じ参照符号は同様な要素を指す。
【００１３】
（詳細な説明）
本発明は、画素ごとのＭＩＰマッピングおよび三線フィルタリングのための改良された方法および装置を開示する。以下の詳細な説明では、本発明を完全に理解していただくために、多数の特定の詳細について述べる。当業者には、これらの特定の詳細を使用せずに本発明を実施できることが理解されよう。他の例では、本発明を不必要に曖昧にしないように、周知の構造、インタフェース、およびプロセスは詳しく示していない。
【００１４】
図１は、本発明が実施されるコンピュータ・システム１の一実施形態である。コンピュータ・システム１は、システム・バス３０によってシステム・メモリ２０に結合された中央演算処理装置（ＣＰＵ）１０を含む。ＣＰＵ１０およびメモリ２０は、バス・インタフェース５０を通しシステム・バス３０を介して周辺要素相互接続（ＰＣＩ）バス４０に結合される。ＰＣＩバス４０には、グラフィックス／ビデオ・アクセレレータ・カード６０と様々な周辺装置８０、９０が結合されている。グラフィックス／ビデオ・アクセレレータ・カード６０はディスプレイ／モニタ７０に結合されている。
【００１５】
図２は、様々な３次元（３Ｄ）グラフィックス機能を実行する回路を含め、一実施形態のグラフィックス／ビデオ・アクセレレータ・カード６０内に含まれる例示的な回路を示す。ＰＣＩインタフェース１００は、グラフィックス／ビデオ・アクセレレータ・カード６０をＰＣＩバス４０に結合する。グラフィックス・プロセッサ１０２は、ＰＣＩインタフェース１００に結合され、様々なグラフィックス処理機能およびビデオ処理機能を実行するように設計されている。グラフィックス・プロセッサ１０２は通常、ＲＩＳＣ（縮小命令セット・コンピューティング）プロセッサである。
【００１６】
画素エンジン１２０は、グラフィックス・プロセッサ１０２に結合され、後述のように、三線フィルタリングやＭＩＰマッピングなど様々なグラフィックス機能を実行する回路を含む。ローカル・ランダム・アクセス・メモリ（ＲＡＭ）１１０は、送信元画素色値と宛先画素色値の両方を記憶する。宛先色値は、メモリ１００内のフレーム・バッファ１１２に記憶される。好ましい実施形態では、メモリ１１０としてはダイナミックＲＡＭ（ＤＲＡＭ）が使用される。ディスプレイ・コントローラ１１４がＲＡＭ１１０および先入先出しバッファ（ＦＩＦＯ）１１６に結合されている。ディスプレイ・コントローラ１１４の制御下で、フレーム・バッファ１１２に記憶されている宛先色値がＦＩＦＯ１１６に供給される。ＦＩＦＯ１１６に記憶されている宛先値は１組のデジタル・アナログ変換器（ＤＡＣ）１１８に供給され、デジタル・アナログ変換器１１８は赤、緑、青のアナログ色信号をモニタ７０に出力する。
【００１７】
ＲＡＭ１１０にはメモリ・コントローラ１０８も結合されている。メモリ・コントローラ１０８はＲＡＭ１１０と画素エンジン１２０とグラフィックス・プロセッサ１０２の両方との間のデータの転送を制御する。命令キャッシュ１０４およびデータ・キャッシュ１０６はそれぞれ、グラフィックス・プロセッサ１０２およびメモリ・コントローラ１０８に結合され、それぞれ、頻繁に使用される命令およびデータを記憶するために使用される。データ・キャッシュ１０６は、ＰＣＩインタフェース１００および画素エンジン１２０にも結合されている。
【００１８】
一実施形態の画素エンジンは三角形エンジンを備える。三角形エンジンは、３Ｄ画像をレンダリングするためにスキャンライン・アルゴリズムと共に使用される。３Ｄ画像をレンダリングする際、複数の画素をレンダリングすることによって複数の多角形または三角形が形成される。三角形の画素をレンダリングするためにスキャンライン・アルゴリズムが使用される。図３は、一実施形態の三角形３００および対応するスキャンライン３０２および画素３０４である。三角形エンジンは、後述のように、画素をレンダリングするためのすべての計算を実行する。
【００１９】
コンピュータ・グラフィックス内の合成画像に可視ディテールを加えるためにテクスチャ・マッピングが使用される。一実施形態のテクスチャ・マッピングは一連の空間変形を含む。この変形は、テクスチャ平面［ｕ、ｖ］が３Ｄ表面［ｘ、ｙ、ｚ］に変形され、次いで出力画面［ｘ、ｙ］上に投影される。テクスチャ・マッピングは、単に、壁紙と同様に表面上に画像ディテールを付与することによって、画像上に複雑な外観を作成する働きをする。テクスチャは一般に、目標の表面上に色をマッピングするために使用された画像とされている。さらに、面法線を摂動し、したがって、こぶおよびしわを、そのような摂動をモデル化する必要なしにシミュレートさせるのにテクスチャが使用される。
【００２０】
一実施形態で画素をレンダリングする際、色画像を複数の解像度でメモリに記憶するためにＭＩＰマップが使用される。図４は、ＲＧＢカラー・モデルを使用する一実施形態のＭＩＰマップ・メモリ構成である。このＭＩＰマップは三線補間をサポートする。この補間では、３つの正規化座標ｕ、ｖ、およびｑを使用してレベル内補間およびレベル間補間を計算することができる。ｕとｖは共に、テクスチャ・マップ内の点にアクセスするために使用される空間座標である。ｑ座標は、角錐の様々なレベルにインデックス付けし、それらのレベル同士を補間するために使用される。ＲＧＢカラー・モデルでは、東側境界および南側境界に接触している象限は、色画像の最初の赤成分、緑成分、および青成分を含む。残りの左上の象限はオリジナルのすべてのより低い解像度のコピーを含む。各レベルは、［ｕ、ｖ、ｑ］座標系によってインデックス付けされるが、この実施形態はこのように制限されるわけではない。三線補間または三線フィルタリングは、［ｕ、ｖ、ｑ］座標系を使用して行うことができる。ｑの値は、エイリアシングとブラーリングとのトレードオフをバランスさせる式を使用して選択され、この式は、次式のように、表面投影を使用して部分導関数を計算する。
【数４】
0004160261.tif 000005
【００２１】
一実施形態では、２つの最も近くのＭＩＰマップから得た４つの取り囲んでいるテクセルから、結果として得られる画素を判定するために、三線フィルタリングが使用される。一実施形態の三線フィルタリングを実行する際、特定の画素をレンダリングするうえで使用されるＭＩＰレベルを選択するために、最大スケール・ファクタＲｈｏが使用される。Ｒｈｏとは、送信元テクセルと画面画素との最大の比であり、次式を使用して計算される。
【数５】
0004160261.tif 000006
ただし、この実施形態はこのように制限されるわけではない。詳細レベル（ＬＯＤ）は、選択される実際のＭＩＰレベルであり、次式のように定義される。
【数６】
0004160261.tif 000007
ただし、この実施形態はこのように制限されるわけではない。
【００２２】
一実施形態の三線フィルタリングは、商法則を使用して次式を示すことによって実現される。
ｄｕ／ｄｘ＝ｄ（（ｕ*ｑ）／ｑ）／ｄｘ＝（ｑ*ｄｕp／ｄｘ−ｕp*ｄｑ／ｄｘ）／（ｑ*ｑ）    （３）
上式で、ｕp＝ｕ*ｑである（すなわち、三角形を描画する際に反復される遠近法によって補正されるｕ）。同様に、次式が示される。
ｄｖ／ｄｘ＝（ｑ*ｄｖp／ｄｘ−ｖｐ*ｄｑ／ｄｘ）／（ｑ*ｑ）
（４）
ｄｕ／ｄｙ＝（ｑ*ｄｕp／ｄｙ−ｕｐ*ｄｑ／ｄｙ）／（ｑ*ｑ）および
（５）
ｄｖ／ｄｙ＝（ｑ*ｄｖp／ｄｙ−ｖｐ*ｄｑ／ｄｙ）／（ｑ*ｑ）
（６）
【００２３】
本発明の一実施形態によれば、上記の定義に基づいて、以下の項が定義される。
ｃ１＝（ｑ*ｄｕp／ｄｘ−ｕp*ｄｑ／ｄｘ）
（７）
ｃ２＝（ｑ*ｄｖp／ｄｘ−ｖp*ｄｑ／ｄｘ）
（８）
ｃ３＝（ｑ*ｄｕp／ｄｙ−ｕp*ｄｑ／ｄｙ）および
（９）
ｃ４＝（ｑ*ｄｖp／ｄｙ−ｖp*ｄｑ／ｄｙ）
（１０）
上式で、ｕおよびｖはテクスチャ値であり、ｘおよびｙはテクセルの画面位置値であり、ｑは距離値である。したがって、数式７〜１０を使用して次式が示される。
Ｒｈｏ’＝ＭＡＸ［（ｃ１*ｃ１＋ｃ２*ｃ２）／（ｑ*ｑ*ｑ*ｑ），
（１１）
（ｃ３*ｃ３＋ｃ４*ｃ４）／（ｑ*ｑ*ｑ*ｑ）］
（１２）
上式は次式を意味する。
Ｒｈｏ’＝ＭＡＸ［（ｃ１*ｃ１＋ｃ２*ｃ２），（ｃ３*ｃ３＋ｃ４*ｃ４）］／（ｑ*ｑ*ｑ*ｑ）
（１３）
および
【数７】
0004160261.tif 000008
【００２４】
本発明の第１の実施形態によれば、三角形のあらゆる点ではなく、各スキャンラインの開始位置でのみある項を計算することにより、グラフィックスをレンダリングする際に実行される計算の数を削減し、それによって三線フィルタリングの性能が改善される。上記の数式中のｃ１およびｃ２の導関数はゼロであり、したがって、ｃ１およびｃ２はスキャンラインに沿った定数であり、この場合、スキャンラインは、ｙ軸に沿って単一の値を有し、かつｘ軸に沿って増減する値を有する。したがって、一実施形態によれば、数量（ｃ１*ｃ１＋ｃ２*ｃ２）は各スキャンラインの開始位置で１度だけ計算され、それに対して、数量（ ｃ３*ｃ３＋ｃ４*ｃ４ ）は、スキャンラインに沿って各点ごと、あるいは各画素ごとに計算される。数量（ｃ１*ｃ２＋ｃ２*ｃ２）を各スキャンラインごとに１度計算するだけでよく、かつ数量（ｃ３*ｃ３＋ｃ４*ｃ４）の計算がスキャンラインに沿った各画素ごとに上記の計算に従うので、この実施形態では、数量（ ｃ１*ｃ１＋ｃ２*ｃ２ ）および数量（ｃ３*ｃ３＋ｃ４*ｃ４）を計算する際に同じ乗算器ユニットを使用することができる。というのは、これらの値が同時に計算されることはないからである。
【００２５】
図５は、第１の実施形態の三線フィルタリングを使用する画素レンダリングに関するフローチャートである。演算はステップ５０２から開始し、レンダリングすべき多角形のスキャンラインが選択される。各スキャンラインの開始位置で、三角形エンジンはステップ５０４で、数式７および数式８を使用し、スキャンラインのｘ座標に対する２つのテクスチャ値のそれぞれのスキャンライン勾配を計算する。これらのスキャンライン勾配を使用して数量（ｃ１*ｃ１＋ｃ２*ｃ２）が計算される。一実施形態では、これらの計算は、各スキャンラインごとに６回の乗算、２回の減算、および１回の加算を使用して行われるが、この実施形態はこのように制限されるわけではない。この実施形態は６つの乗算器を使用するので、Ｒｈｏを単一のクロック・サイクルで計算することができる。
【００２６】
各スキャンラインの開始位置でのスキャンライン勾配計算の後で、三角形エンジンはステップ５０６で、スキャンラインのｙ座標に対するスキャンラインの各画素の画素勾配を計算する。画素勾配は、数式９および数式１０を使用して２つのテクスチャ値のそれぞれについて計算される。この画素勾配を使用して数量（ｃ３*ｃ３＋ｃ４*ｃ４）が計算される。ステップ５０８で、数量（ｃ１*ｃ１＋ｃ２*ｃ２）が数量（ｃ３*ｃ３＋ｃ４*ｃ４）と比較され、ステップ５１０で、この２つの数量のうちの大きい方が、対応する画素に関する最大Ｒｈｏ定数項として選択される。一実施形態では、最大Ｒｈｏ定数計算は、各画素ごとに６回の乗算、２回の減算、１回の加算、および１回の比較演算を使用して行われるが、この実施形態はこのように制限されるわけではない。
【００２７】
最大Ｒｈｏ定数を求めた後で、三角形エンジンはステップ５１２で、数式２を使用してスキャンラインの各画素ごとにＬＯＤを計算する。各画素のＬＯＤ値は、ステップ５１４で、対応する画素をレンダリングするためのテクスチャ・マップを選択するために使用される。画素は、ステップ５１６でレンダリングされる。ステップ５１８で、スキャンラインのすべての画素がレンダリングされているかどうかが判定される。現在のスキャンラインのすべての画素がレンダリングされているわけではない場合、演算はステップ５０６に進み、スキャンラインの他の画素について画素勾配が計算される。現在のスキャンラインのすべての画素がレンダリングされている場合、演算はステップ５２０に進み、現在の多角形のすべてのスキャンラインがレンダリングされているかどうかが判定される。現在の多角形のすべてのスキャンラインがレンダリングされているわけではない場合、演算はステップ５０２に進み、多角形の新しいスキャンラインがレンダリングすべきスキャンラインとして選択される。現在の多角形のすべてのスキャンラインがレンダリングされている場合、現在の多角形に関する演算は終了する。
【００２８】
本発明の第２の実施形態によれば、三角形のあらゆる点ではなく、各スキャンラインの開始位置でのみある項を計算することによりグラフィックスをレンダリングする際に実行される計算の数を削減することによって三線フィルタリングの性能が改善される。前述のように、ｃ１およびｃ２はスキャンラインに沿った定数であり、したがって、数量（ｃ１*ｃ１＋ｃ２*ｃ２）は各スキャンラインの開始位置で１度だけ計算される。さらに、数式９および数式１０中のｃ３およびｃ４が線形数量であることに留意されたい。したがって、画素（ｘ、ｙ）、すなわちスキャンラインの開始位置で数量（ｃ３*ｃ３＋ｃ４*ｃ４）が計算された場合、画素（ｘ＋１、ｙ）、すなわちスキャンライン上の次の画素については次式が成立し、
（ｃ３*ｃ３＋ｃ４*ｃ４）＝
［（ｃ３＋ｄｅｌｔａ＿ｃ３）*（ｃ３＋ｄｅｌｔａ＿ｃ３）＋（ｃ４＋ｄｅｌｔａ＿ｃ４）*（ｃ４＋ｄｅｌｔａ＿ｃ４）］＝
［ｃ３*ｃ３＋２*ｃ３*ｄｅｌｔａ＿ｃ３＋ｄｅｌｔａ＿ｃ３*ｄｅｌｔａ＿ｃ３＋ｃ４*ｃ４＋２*ｃ４*ｄｅｌｔａ＿ｃ４＋ｄｅｌｔａ＿ｃ４*ｄｅｌｔａ＿ｃ４］
（１５）
画素（ｘ＋２、ｙ）については次式が成立する。
（ｃ３*ｃ３＋ｃ４*ｃ４）＝
［（ｃ３＋ｄｅｌｔａ＿ｃ３）*（ｃ３＋ｄｅｌｔａ＿ｃ３）＋（ｃ４＋ｄｅｌｔａ＿ｃ４）*（ｃ４＋ｄｅｌｔａ＿ｃ４）］＝
［ｃ３*ｃ３＋４*ｃ３*ｄｅｌｔａ＿ｃ３＋４*ｄｅｌｔａ＿ｃ３*ｄｅｌｔａ＿ｃ３＋ｃ４*ｃ４＋４*ｃ４*ｄｅｌｔａ＿ｃ４＋４*ｄｅｌｔａ＿ｃ４*ｄｅｌｔａ＿ｃ４］
（１６）
したがって、各スキャンラインの開始位置でｃ３およびｃ４の導関数が計算された場合、そのスキャンラインに沿った各画素ごとにｃ３およびｃ４が計算されることはない。
【００２９】
図６は、第２の実施形態の三線フィルタリングを使用する画素レンダリングに関するフローチャートである。演算はステップ６０２から開始し、レンダリングすべき多角形のスキャンラインが選択される。各スキャンラインの開始位置で、三角形エンジンは、ステップ６０４で、数式７および数式８を使用し、スキャンラインのｘ座標に対する２つのテクスチャ値のそれぞれのスキャンライン勾配を計算する。これらのスキャンライン勾配を使用して数量（ｃ１*ｃ１＋ｃ２*ｃ２）が計算される。各スキャンラインの開始位置でのスキャンライン勾配計算の後で、三角形エンジンは、ステップ６０６で、スキャンラインのｙ座標に対するスキャンラインの第１の画素の画素勾配を計算する。画素勾配は、数式９および数式１０を使用して２つのテクスチャ値のそれぞれについて計算される。ステップ６０８で、次式および数式１５に従って画素勾配に関する導関数が計算される。
ｄｅｌｔａ＿ｃ３＝（ｄｑ／ｄｘ*ｄｕp／ｄｙ−ｄｕp／ｄｘ*ｄｑ／ｄｙ）
（１７）
ｄｅｌｔａ＿ｃ４＝（ｄｑ／ｄｘ*ｄｖp／ｄｙ−ｄｖp／ｄｘ*ｄｑ／ｄｙ）
（１８）
この導関数を使用して各画素ごとに画素勾配が求められ、したがって、各画素の画素勾配を別々に計算することが不要になる。数量（ｃ１*ｃ１＋ｃ２*ｃ２）は、スキャンライン勾配を使用して計算され、数量（ｃ３*ｃ３＋ｃ４*ｃ４）は、画素勾配を使用して計算される。一実施形態では、これらの計算は、各スキャンラインごとに２０回の乗算、６回の減算、５回の加算、および２回の左シフト演算を使用して行われるが、この実施形態はこのように制限されるわけではない。一実施形態では、１０個の乗算器を使用して各スキャンラインごとに２クロック・サイクルにわたって最大Ｒｈｏ定数が計算され、この計算は、現在のスキャンラインについて画素がレンダリングされている間、連続するスキャンラインについて実行することができる。
【００３０】
ステップ６１０で、数量（ｃ１*ｃ１＋ｃ２*ｃ２）が数量（ｃ３*ｃ３＋ｃ４*ｃ４）と比較され、ステップ６１２で、この２つの数量のうちの大きい方が、対応する画素に関する最大Ｒｈｏ定数項として選択される。一実施形態では、最大Ｒｈｏ定数計算は、各画素ごとに２回の加算および１回の比較演算を使用して行われるが、この実施形態はこのように制限されるわけではない。
【００３１】
最大Ｒｈｏ定数を求めた後で、三角形エンジンは、ステップ６１４で、数式２を使用してスキャンラインの各画素ごとにＬＯＤを計算する。各画素のＬＯＤ値は、ステップ６１６で、対応する画素をレンダリングするためのテクスチャ・マップを選択するために使用される。画素は、ステップ６１８でレンダリングされる。ステップ６２０で、スキャンラインのすべての画素がレンダリングされているかどうかが判定される。現在のスキャンラインのすべての画素がレンダリングされているわけではない場合、演算はステップ６１０に進む。現在のスキャンラインのすべての画素がレンダリングされている場合、演算はステップ６２２に進み、現在の多角形のすべてのスキャンラインがレンダリングされているかどうかが判定される。現在の多角形のすべてのスキャンラインがレンダリングされているわけではない場合、演算はステップ６０２に進み、多角形の新しいスキャンラインがレンダリングすべきスキャンラインとして選択される。現在の多角形のすべてのスキャンラインがレンダリングされている場合、現在の多角形に関する演算は終了する。
【００３２】
したがって、画素ごとのＭＩＰマッピングおよび三線フィルタリング用の方法および装置を開示する。本明細書で説明するこれらの特定の構成および方法は本発明の原則を例示するものに過ぎない。当業者によって、本発明の範囲から逸脱せずに形態および詳細に多数の修正を加えることができる。特定の好ましい実施形態に関して本発明を示したが、本発明をそのように制限されるものとみなすべきではない。本発明は、添付の特許請求の範囲によってのみ制限される。
【図面の簡単な説明】
【図１】  本発明が実施されるコンピュータ・システムの一実施形態を示す図である。
【図２】  一実施形態のグラフィックス／ビデオ・アクセレレータ・カード内に含まれる例示的な回路を示す図である。
【図３】  一実施形態の三角形および対応するスキャンラインおよび画素を示す図である。
【図４】  ＲＧＢカラー・モデルを使用して一実施形態のＭＩＰマップ・メモリ構成を示す図である。
【図５】  第１の実施形態の三線フィルタリングを使用した画素レンダリングに関するフローチャートである。
【図６】  第２の実施形態の三線フィルタリングを使用した画素レンダリングに関するフローチャートである。
【図１】
0004160261.tif 000009
【図２】
0004160261.tif 000010
【図３】
0004160261.tif 000011
【図４】
0004160261.tif 000012
【図５】
0004160261.tif 000013
【図６】
0004160261.tif 000014