(57)【特許請求の範囲】
【請求項１】
ピクセル値を備えたピクセルを有するオブジェクトのイメージをディスプレイ装置に発生し、表示するようにしたコンピュータ・グラフィックス・システムで、所定の遠近関係に基づいて所定のオブジェクトにテクスチャを表示するためにテクセル値を能率よく計算する方法において
走査線に沿った１対の端点間における複数の区分点を適切に選択するステップであって、テクセル正確度判定基準を選択するステップと、その選択されたテクセル正確度判定基準の関数として前記走査線に沿った前記複数の区分点の位置を計算するステップと、を含む前記適切に選択するステップと、
前記走査線の隣接した区分点間に位置する複数のピクセルに対応する複数の中間テクセル値を近似計算するステップと
を有することを特徴とするオブジェクトにテクスチャを表示するためにテクセル値を計算する方法。
【請求項２】
さらに、前記走査線の前記端点の１つと隣接区分点との間に位置する第２の複数のピクセルに対応する第２の複数の中間テクセル値を近似計算するステップを有する請求項１に記載の方法。
【請求項３】
さらに、前記走査線の前記区分点と前記端点に対応する複数のテクセル値を正確に計算するステップから構成されることを特徴とする請求項１に記載の方法。
【請求項４】
さらに、前記中間テクセル値を利用して、前記ピクセルの前記ピクセル値を修正するステップを有する請求項１に記載の方法。
【請求項５】
ピクセル値を備えたピクセルから成るオブジェクトのイメージをディスプレイ装置に発生し、修正し、表示するコンピュータ・グラフィックス・システムに用いられるテクセル値発生器において、
選択されたテクセル正確度判定基準の関数として走査線に沿った複数の区分点の位置を計算する計算器と、
前記計算器に結合されて、前記走査線の隣接区分点間に位置する複数のピクセルに対応する複数の中間テクセル値を計算する近似計算器と
を有するテクセル値発生器。
【請求項６】
さらに、前記計算器に結合されて、前記選択されたテクセル正確度判定基準を記憶するための記憶素子を有する請求項５に記載のテクセル値発生器。
【請求項７】
ピクセル値を備えたピクセルから成るオブジェクトのイメージをディスプレイ装置に発生し、修正し、表示するコンピュータ・グラフィックス・システムに用いられるテクスチャ・マッピング・システムにおいて、
選択されたテクセル正確度判定基準の関数として走査線に沿った複数の区分点の位置を計算する計算器と、
前記計算器に結合されて、前記走査線の隣接区分点間に位置する複数のピクセルに対応する複数の中間テクセル値を計算する近似計算器と、
前記近似計算器に結合され、前記中間テクセル値によって前記ピクセル値に修正を加えるコンバイナと
を有するマッピング・システム。
【請求項８】
さらに、前記計算器に結合されて、前記選択されたテクセル正確度判定基準を記憶するための記憶素子を有する請求項７に記載のマッピング・システム。
【請求項９】
前記ピクセル値が、下記の式を利用して前記中間テクセル値のＭＩＰマップ・レベルを計算することによって修正されることを特徴とする請求項７に記載のマッピング・システム。
【数１】
0003786995.tif 000007
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明は、１９９４年４月１日に提出され、Ｓｕｎ  Ｍｉｃｒｏｓｙｓｔｅｍｓ  Ｉｎｃ．に譲渡された、背景の説明を補足するため、参考までに本書に組み込まれている、Ｙａｋｏｖ  Ｋａｍｅｎ及びＵｍａ  Ｓａｂａｄａによる「Ａ  ｍｅｔｈｏｄ  ａｎｄ  Ａｐｐａｒａｔｕｓ  ｆｏｒ  ａｎ  ＡｄａｐｔｉｖｅＴｅｘｔｕｒａｌ  Ｍａｐｐｉｎｇ  Ｃｏｎｔｒｏｌｌｅｒ」と題する米国特許出願第０８／０４１，０７３号に関するものである。
【０００２】
本発明は、コンピュータ・グラフィックスの分野に関するものである。とりわけ、本発明は、近似によるテクスチャ・マッピングの分野に関するものである。
【０００３】
【従来の技術】
上述の係属中の出願には、コンピュータ・グラフィックス及びテクスチャ・マッピングに関する一般的な背景の説明が含まれている。この背景セクション自体は、遠近関係補正による従来のテクスチャ・マッピング、これを実施するための方法、及び、その欠点に焦点を合わせたものである。
【０００４】
大部分の従来式コンピュータ・グラフィックスには、均等に間隔をあけたピクセルのビット・マップ・アレイとして表される２次元イメージを表示するためのディスプレイ装置が含まれている。各ピクセルは、ピクセル値を備えており、Ｘ軸及びＹ軸座標値対によって一意的に識別される。このデカルトＸ−Ｙ座標表現は、例えば、陰極線管（ＣＲＴ）及び能動／受動液晶ディスプレイ（ＬＣＤ）といった、そのイメージがＸ軸に沿った複数の走査線から構成される大部分のグラフィックス・ディスプレイ装置に適合するものである。
【０００５】
従来、テクスチャは、視点及び遠近関係の変化に応じて表面にパターンが付与されたように見えるようにして、グラフィックス・オブジェクトの表面に施される、カラー、輝度、表面標準透明度、または、他の表面特性の変形と定義されている。ディスプレイ装置に３次元オブジェクトを質の高い２次元イメージとしてリアルに表示するため、各ピクセル毎に、遠近法によってテクセル値と呼ばれる適正なテクスチャ・マッピング値を発生し、イメージのピクセル値に修正が施される。
【０００６】
優れた画質が得られるようにするため、数学モデルが用いられたが、計算集約形であり、コンピュータ・グラフィックス・システムのプロセッサに過度の要求をすることになりがちであった。一般に、テクセル値の発生には、遠近関係補正を計算するため、イメージの各ピクセル毎に、２つの区分計算またはその同等物を伴うことになる。コンピュータ技術において周知のように、プロセッサに区分計算を実施する専用のハードウェアが装備されていたとしても、区分計算には、一般に、かなり多くのクロック・サイクルを要することになる。ＳＰＡＲＣベースのプロセッサのような強力なプロセッサを利用すれば、ピクセル当たり２区分の計算をリアル・タイムで実施することが可能であるが、結果として生じるテクスチャ計算のために、他のプロセスを同時に支援するプロセッサの能力が制限を受けることになる。Ｉｎｔｅｌ  ８０４８６  ＳＸマイクロプロセッサのような能力的に劣るプロセッサの場合、ピクセル毎に２区分を必要とするリアル・タイムのテクスチャ値計算は、プロセッサの手に負えない可能性がある。従って、遠近法で補正された質の高いテクスチャ・マップを生成するための計算要件を軽減することが極めて望ましい。典型的な従来のアプローチでは、正確に計算された区分点間において所定の間隔で位置するピクセルの代わりに線形補間を利用することによって、区分計算の総数を減少させる。
【０００７】
図１Ａ及びＢに示すように、第１の事前決定的補間方法の場合、親多角形１００が、漸次、幾何学的方法で所定の数のより小さい子多角形１１０、１２０、１３０、１４０、．．．１９０に細分される。結果として生じる子多角形の１つ１１０を詳細に示す図１Ｃを参照すると、例えば、走査線１１１が子多角形１１０の境界線と交差する端点１１１ａ及び１１１ｚのような端点対に関して、正確なテクセル値が計算される。次に、走査線１１１に沿って線形補間することによって、端点１１１ａ、１１１ｚ間に位置するピクセル１１１ｂ、１１１ｃ、．．．１１１ｙに関して近似テクセル値が計算される。このプロセスは、子多角形１１０の残りの走査線１１２、１１３、．．．１１９に関して繰り返され、また、親多角形１００内にある全てのピクセルに関するテクセル値の計算が済むまで、残りの子多角形１２０、１３０、．．．１９０の全ての走査線についても同様のやり方で繰り返されることになる。
【０００８】
次に図２Ａを参照すると、第２の事前決定的補間方法は、例えば、多角形２００の走査線２１０のような各走査線を、所定の数の区分点２１２、２１３、．．．２１８と端点２１１、２１９によって描写される走査線セグメントに細分する方法が示されている。例えば、走査線２１０のような各走査線毎に、端点２１１、２１９及び区分点２１２、２１３、．．．２１８に関して正確なテクセル値が計算される。次に、図２Ｂに示すように、走査線２１０に沿った残りのピクセル２１１ａ、２１１ｂ、．．．２１１ｚ、２１２ａ、２１２ｂ、．．．２１２ｚ、２１８ａ、２１８ｂ、．．．２１８ｚに関するテクセル値が、線形補間によって計算される。このプロセスは、多角形２００の全てのピクセルについてテクセル値の計算が済むまで、残りの走査線２２０、２３０、．．．２９０に関して繰り返される。
【０００９】
上述の従来の方法の場合、中間テクセル値の線形補間は、図２Ｃの多角形２０００に適用されているように、下記の典型的な方程式によって実施することができる。多角形２０００は、トリプル（ｘi，ｙi，ｚi，ｗi，ｕi，ｖi）によって指定される三角形であり、ｉ＝１，２，３であり、ここで、（ｘi，ｙi）は三角形の頂点の装置座標であり、ｚiは、頂点におけるＺ深さであり、ｗiは、同次クリップ座標系における頂点のｗ成分の逆数の絶対値であり、（ｕi，ｖi）は、頂点の２次元テクスチャ座標である。Ｕ、Ｖ及びＷは、（ｘ1，ｙ1，ｚ1，ｗ1，ｕ1，ｖ1）と（ｘ3，ｙ3，ｚ3，ｗ3，ｕ3，ｖ3）の間において、三角形２０００の左辺に沿って、それぞれ、線形補間されたｕ、ｖ、ｗの値である。
【数２】
0003786995.tif 000002
【００１０】
上述の従来の方法によれば、幾分計算集約的な区分計算の代わりにより単純な線形補間を用いることによって、プロセッサに対する計算負荷が軽減されるが、あいにく、従来の方法は、両方とも、融通性がなく、非効率的で、かつ、満足のゆくテクセル値が得られないか、あるいは、そのいずれかである。これは、区分量をあらかじめ決定するので、イメージ全体にわたって、オブジェクト間のテクスチャ変動とオブジェクト内におけるテクスチャ勾配が、両方とも、かなりの程度に一定している場合にしか、うまく働かないためである。実際、異なるイメージの異なるオブジェクトは、異なるテクスチャ特性を備えている可能性があり、従って、走査線区分の所定のレベルが１つでは、全てのオブジェクトに最適というわけにはゆかない。例えば、所定の走査線セグメントが短すぎる場合、すなわち、区分点の間隔があまりに近すぎる場合、プロセッサに過剰な量の区分計算が要求されることになる。逆に、所定の走査線セグメントが長すぎる場合、区分点に対して遠いピクセル位置において、著しく不正確な近似によるテクセル値が得られることになり、イメージ全体としてのテクスチャの質が劣化する。
【００１１】
【発明が解決しようとする課題】
本発明の目的は、最少量の計算集約的区分、すなわち、最少数の区分点を利用して、テクセル値を発生し、同時に、走査線に沿った選択可能なテクセル正確度判定基準を維持することが可能なテクセル値発生器を備えたコンピュータ・グラフィックス・システムを提供することにある。
【００１２】
【課題を解決するための手段】
これは、各走査線に沿って走査線セグメントを描く区分点を適応するように選択し、選択されたテクセル正確度判定基準を越えないで、区分点の間隔ができるだけ広くなるようにすることによって実現される。
【００１３】
テクセル・エラー限界のようなテクセル正確度判定基準が選択されているので、走査線に沿った区分点の位置は、選択された正確度判定基準の関数として計算される。一般に、テクスチャ勾配は、所定のオブジェクトの表面に均等に分布しておらず、イメージの異なるオブジェクト間には、テクスチャ変動が存在するので、１度に１つずつ、適応するように区分点を選択し、区分点間における局所テクスチャ勾配が許容するだけの数のピクセルをスキップするのが有利である。すなわち、任意の隣接する２つの区分点間における任意選択によるピクセル数は、局所テクスチャ勾配に応じて変動する。
【００１４】
走査線の端点間における区分点の選択が済むと、正確なテクセル値が、これらの区分点と、走査線の端点においても計算される。一般に、２つの区分計算、または、逆数及び乗算の計算といった同等の数学演算を利用して、各テクセル値の正確な計算が行われる。次に、走査線に沿った隣接対をなす区分点間に位置するピクセルに関して近似テクセル値が計算される。適合する近似案には、線形補間のような補間法が含まれる。
【００１５】
区分点を選択し、これらの区分点及び端点における正確なテクセル値を計算し、さらに、隣接区分点及び／または端点間に位置するピクセルに対するテクセル値を近似計算する上述のプロセスは、所定のオブジェクトを表示するための全てのピクセル・テクセル値の計算が済むまで、オブジェクトにオーバラップする各走査線毎に繰り返される。
【００１６】
定義
ピクセル：例えば、表示すべき所定のオブジェクトのイメージに関連したピクセル値を有するＸ−Ｙ座標のような、あらかじめ定義された座標系に位置する整数点。
ＭＩＰ（小さいが内容豊富な）マップ：例えば、［ｕ，ｖ，ｄ］座標系におけるレベル内及びレベル間の両方の三線座標補間案を可能にするピラミッド形パラメータ・データ構造。ここで、ｕ、ｖは、ピラミッド・レベル内のポイントにアクセスするために用いられる空間座標であり、ｄ座標は、ピラミッドの異なるレベルに対する指標付け及びそのレベル間の補間に用いられる。
テクセル値：所定の遠近関係に基づいて所定のオブジェクトのテクスチャが表示されるように、対応するピクセル値のマッピングを行うためのテクスチャ値。グラフィックス・イメージ：グラフィックス・ディスプレイ装置に表示される所定のオブジェクトの表現。
多角形：所定のオブジェクトにおいて問題となる数学的に都合のよい形状の領域。
【００１７】
【発明の実施の形態】
下記の説明における多くの細目によって、本発明の完全な理解が可能になる。これらの細目には、ソフトウェア、ハードウェア、または、その組み合わせによって、効率のよい適応型テクセル値発生器を実現する上で開発者の助けとなる機能ブロック及び典型的なテクセル正確度判定基準が含まれる。さらに、本発明のテクセル値発生器は、特定の実施形態に関連して解説されるが、本発明は、多種多様なコンピュータ・グラフィックス・システム及び環境に適用可能である。本発明を不必要に曖昧にしないように、他の例において周知の回路、構造、及び、プログラム・コードに関する詳細な説明は行わない。
【００１８】
図３は、本発明のテクセル値発生器３１０を含むテクスチャ・マッピング・システム３００の実施形態の１つを示すブロック図である。テクスチャ・マッピング・システム３００には、ＭＩＰマップ・セレクタ３２０、テクスチャ・ルックアップ・テーブル３３０、照度値発生器３４０、コンバイナ３５０、ビット・マップされたピクセル値バッファ３６０、３つのデジタル・アナログ変換器（ＤＡＣ）３７０ａ、３７０ｂ、３７０ｃ、及び、ディスプレイ装置３８０も含まれている。
【００１９】
テクセル値発生器３１０は、直接、及び、ＭＩＰマップ・セレクタを介してテクスチャ・ルックアップ・テーブル３３０に結合される。テクスチャ・ルックアップ・テーブル３３０及び照度値発生器３４０のそれぞれの出力ノードは、コンバイナ３５０に結合される。コンバイナ３５０の出力ノードは、ビット・マップされたピクセル値バッファ３６０に結合される。さらに、ピクセル値バッファ３６０は、ＤＡＣ３７０ａ、３７０ｂ、３７０ｃのデジタル入力ノードに結合される。ＤＡＣ３７０ａ、３７０ｂ、３７０ｃのアナログ出力ノードは、ディスプレイ装置３８０に結合される。
【００２０】
テクセル値発生器３１０は、テクスチャ・ルックアップ・テーブル３３０及びＭＩＰセレクタ３２０に、それぞれ、ｕ、ｖ信号及び微分ｕ、ｖ信号を加える。さらに、ＭＩＰセレクタ３２０は、テクスチャ・ルックアップ・テーブル３３０にＭＩＰマップ選択信号を加える。テクスチャ・ルックアップ・テーブル３３０及び照度値発生器３４０は、それぞれ、コンバイナ３５０のためにテクスチャ及び照度値を発生する。次に、コンバイナ３５０は、これらのテクスチャ及び照度値と、ピクセル値バッファからのフィードバック・ピクセル値を組み合わせて、バッファ３６０への組み合わされてビットマップされたピクセル値を発生する。最後に、ピクセル値バッファ３６０によって、それぞれのデジタルＲＧＢ信号が送り出され、ＤＡＣ３７０ａ、３７０ｂ、３７０ｃによって、ディスプレイ装置３８０への対応するアナログＲＧＢ信号に変換される。
【００２１】
図４Ａ及び４Ｂは、走査線を適切に細分するための最適の方法を示すフローチャートであり、この方法はテクセル値発生器３１０に有効である。実施形態の１つでは、最も一般的なグラフィックス・ディスプレイ装置に適合させるため、テクセル値は、それぞれ、所定のオブジェクトにおける問題となる領域を形成する多角形と境を接した走査線に沿って発生する。各走査線は、走査線が多角形の境界と交差する端点対を備えている。これらの走査線は、Ｘ−Ｙ座標系における整数位置においてピクセル列に分解可能である。
【００２２】
図４Ａのフローチャートを参照すると、まず、走査線の端点は、打ち切りまたは切り上げ／切り捨てといった、適合する方法によって整数ピクセル座標位置に調整される（ステップ４１０）。走査線が極めて短い場合、すなわち、２つの整数端点が併合されたために、走査線のスパンが空の場合、細分は不要である（ステップ４２０）。同様に、走査線のスパンが短すぎて、細分による恩恵があまりない場合には、細分は実施されない（ステップ４３０）。
【００２３】
逆に、スパンが十分に長く、細分による恩恵を大いに受けることになる場合、テクセル値発生器３１０は、最適になるように走査線のスパンを最少数の最適な間隔の細区分に細分する（ステップ４４０）。
【００２４】
次に、図４Ｂのフローチャートを参照すると、ステップ４４０がさらに詳細に示されている。まず、適合するテクセル正確度判定基準が選択される（ステップ４４２）。この実施形態の場合、テクセル正確度判定基準は、テクセル・エラー限界である。テクセル値発生器３１０は、走査線の一方の端から開始して、選択された正確度判定基準を満たす最大の細区分スペースに対応する、走査線に沿った次の整数区分点の位置を計算する（ステップ４４４）。付加区分点の計算は、走査線のもう一方の端に達するまで、走査線に沿って繰り返される（ステップ４４６）。付録Ａ及びＢには、それぞれ、望ましい実施形態における区分点の位置を計算するための方程式及び計算プログラムが示されている。
【００２５】
図５には、走査線５１０が区分点ｘ2、ｘ3、ｘ4、及び、端点ｘ1、ｘ5によって細分された多角形５００が示されている。望ましい実施形態によれば、近似されたテクセル値のエラーが増し、エラー限界値ｅまたはほぼエラー限界値ｅで最大に達し、次に、隣接区分点／端点間において減少する。エラー限界値ｅに対して最適化すると、端点／区分点対ｘ1とｘ2、ｘ2とｘ3、ｘ3とｘ4、及び、ｘ4とｘ5によって示すように、不均一なスペースが生じる可能性がある。
【００２６】
望ましい実施形態の場合、隣接区分点間のスペースｔは、下記の方程式を利用して計算される：
【数３】
0003786995.tif 000003
【００２７】
ここで、ｅ＝エラー限界
ｗ＝ｗ成分の逆数の絶対値
及びｄｗ＝（ｗｒ−ｗｌ）／（ｘｒ−ｓｌ）
ここで、ｗｌ＝左の区分点におけるｗ値
ｗｒ＝隣接する右の区分点におけるｗ値
【００２８】
走査線のスパンに沿って、所定のステップｔにおいて、ｄｗ及びｅは定数であり、ｗｌは変化する。ｅの適合する値の１つは、０．５、すなわち、ピクセルの半分である。ｅ＝０．５を選択することによって、各ピクセルは、それが納まるべきピクセルの半分内にマップする。拡大されたテクセルのエッジは、非単調性の偶然のグリッチを示すが、これは、選択されたｅ値を減少させることによって簡単に補正することが可能である。逆に、選択されたｅ値を増すと、エラー限界が増大するので、不調の確率が高くなる。
【００２９】
代替案として方程式が次の形をとるものとすることが可能である。
【数４】
0003786995.tif 000004
多角形に対するｗの正規化によって、「ｗｌ」は「０，１」の範囲に保つことが可能である。平方根計算の代わりに、平方根関数に関するルックアップ・テーブルを利用することが可能である。
【数５】
0003786995.tif 000005
は、各多角形に対して一定であるため、さらに効率が向上する可能性もある。
【００３０】
図６は、区分点を選択した後、走査線のスパンに沿ってテクセル値を近似計算するための方法を示すフローチャートである。まず、テクセル値発生器３１０が、２つの整数端点における正確なテクセル値を計算する（ステップ６１０）。もしあれば、ステップ４４４において選択される整数区分点に関する正確なテクセル値も計算される（ステップ６２０）。最後に、近似計算器３１０ａを含むテクセル値発生器３１０が、各走査線の隣接している端点と区分点の間に位置する中間ピクセルの近似テクセル値を発生する（ステップ６３０）。適切な近似法には、上述の式ＥＱ（ｉ）〜（ｉｘ）を利用した線形補間のような補間技法が含まれる。
【００３１】
実施形態によっては、ＭＩＰマップ・レベルも近似計算されるものもある。隣接する区分点によって形成される細分された線セグメントのそれぞれが、アフィン変換に関するものであるため、ＭＩＰマップ・レベルは各線セグメント全体にわたって一定である。一般に、ＭＩＰマップはｕ及びｖが１／２に分割される。従って、ＭＩＰマップ・レベルは、下記の式を用いて近似計算することが可能である。
【数６】
0003786995.tif 000006
【００３２】
望ましい実施形態に関連して本発明の説明を行ってきたが、本発明の精神を逸脱することなく、多くの追加及び修正が可能である。従って、本発明の範囲は、付属の請求項によって判断するのが望ましい。
【図面の簡単な説明】
【図１】  親多角形を所定の数の複数の子多角形に分割する従来の方法を示し（Ａ，Ｂ）、子多角形の１つを詳細に示す図（Ｃ）である。
【図２】  多角形の走査線を、所定の数の区分点によって分離される隣接したピクセル・グループに分割する従来の方法を示す図（Ａ，Ｂ）と中間テクセル値の線形補間を明らかにするための典型的な三角形を示す図（Ｃ）である。
【図３】  本発明のテクセル値発生器を含むテクスチャ・マッピング・システムを示すブロック図である。
【図４】  本発明に基づいて走査線を適応するように細分するための方法を示すフローチャートである。
【図５】  走査線が最適に細分された多角形を示す図である。
【図６】  テクセル値の近似計算を行い、同時に、選択可能なテクセル正確度判定基準も満たすための方法を示すフローチャートである。
【符号の説明】
３００    テクスチャ・マッピング・システム
３１０    テクセル値発生器
３２０    ＭＩＰマップ・セレクタ
３３０    テクスチャ・ルックアップ・テーブル
３４０    照度値発生器
３５０    コンバイナ
３６０    ビット・マップ・ピクセル値バッファ
３７０ａ  デジタル・アナログ変換器
３７０ｂ  デジタル・アナログ変換器
３７０ｃ  デジタル・アナログ変換器
３８０    ディスプレイ装置
【図１】
0003786995.tif 000008
【図２】
0003786995.tif 000009
【図３】
0003786995.tif 000010
【図４】
0003786995.tif 000011
【図５】
0003786995.tif 000012
【図６】
0003786995.tif 000013