(57)【特許請求の範囲】
【請求項１】
プリミティブをラスタ化する方法であって、
ａ）より大きいメモリ・タイルに含まれた複数のより小さいメモリ・タイルから、その内の１つを選択するステップであって、該選択されたより小さいメモリ・タイルが前記プリミティブの頂点を含むステップと、
ｂ）前記より大きいメモリ・タイルに含まれた前記複数のより小さいメモリ・タイルを横断するステップであって、その横断は、前記選択されたより小さいメモリ・タイルで開始して、前記プリミティブ内に位置する１つ以上の記憶場所を有する各より小さいメモリ・タイルを順に通る、横断するステップと、
ｃ）複数のより小さなメモリ・タイル内に含まれるどの記憶位置が前記プリミティブ内に位置するかを決定するステップであって、
ｉ）前記プリミティブの各エッジに対する１つのエッジ評価器を用いて、前記複数のより小さなメモリ・タイル内のｘ及びｙ座標に対するそれぞれのエッジ関数の値を計算するステップと、
ｉｉ）各エッジ評価器に対する１つの加算器ツリーを用いて、前記複数のより小さなメモリ・タイル内の各記憶位置に対するエッジ評価器のエッジ関数を再計算するステップと、
からなるステップと、
ｄ）ステップ（ｃ）中に出会った各記憶位置をラスタ化するステップと、
を含むプロセッサによって実行される方法。
【請求項２】
前記より大きいメモリ・タイルが、更により大きいメモリ・タイルに含まれた複数の前記より大きいメモリ・タイルからのものであり、前記方法が、
ｅ）前記プリミティブ内に位置する１つ以上の記憶場所を有する、前記更により大きいメモリ・タイル内の各より大きいメモリ・タイルを横断するステップと、
ｆ）ステップ（ａ）、（ｂ）および（ｃ）を、ステップ（ｅ）中に出会ったより大きい各メモリ・タイルに適用するステップとを更に含む請求項１に記載の方法。
【請求項３】
前記更により大きいメモリ・タイルが、前記プリミティブにわたる一連の複数の更により大きいメモリ・タイルの１つであり、前記方法が、
ｇ）各更により大きいメモリ・タイルを横断するステップと、
ｈ）ステップ（ｅ）および（ｆ）を、ステップ（ｇ）中に出会った各更により大きいメモリ・タイルに適用するステップとを更に含む請求項２に記載の方法。
【請求項４】
前記更により大きいメモリ・タイルに含まれた複数の前記より大きいメモリ・タイルが、方形または正方形として配置され、左から右へ、上から下へ横断される請求項２に記載の方法。
【請求項５】
前記プリミティブの頂点を開始頂点として選択するステップと、
より小さいメモリ・タイルを選択し、当該より小さいメモリ・タイルが前記開始頂点を含むようにするステップとを更に含む請求項１に記載の方法。
【請求項６】
前記より大きいメモリ・タイルに含まれた複数の前記より小さいメモリ・タイルが、方形または正方形として配置され、左から右へ、上から下へ横断される請求項１に記載の方法。
【請求項７】
一連のメモリ・タイルとして編成されているフレーム・バッファ内のプリミティブをラスタ化する方法であって、
ａ）前記プリミティブ内の記憶場所を含むメモリ・タイルのセットを横断するステップと、
ｂ）複数のメモリ・タイル内に含まれるどの記憶位置が前記プリミティブ内に位置するかを決定するステップであって、
ｉ）前記プリミティブの各エッジに対する１つのエッジ評価器を用いて、前記複数のメモリ・タイル内のｘ及びｙ座標に対するそれぞれのエッジ関数の値を計算するステップと、
ｉｉ）各エッジ評価器に対する１つの加算器ツリーを用いて、前記複数のメモリ・タイル内の各記憶位置に対するエッジ評価器のエッジ関数を再計算するステップと、
からなるステップと、
ｃ）ステップ（ｂ）中に出会った複数の前記メモリ・タイルを、複数のより小さいメモリ・タイルのそれぞれのシーケンスとしてアクセスするステップと、
ｄ）前記複数のより小さいメモリ・タイルのシーケンス内の複数のより小さいメモリ・タイルをラスタ化して、当該ラスタ化が前記プリミティブの頂点を含むより小さいメモリ・タイルに対して先ず実行されるようにするステップと、
を含むプロセッサによって実行される方法。
【請求項８】
ラスタ化を行うために、前記複数のより小さいメモリ・タイルのシーケンス内で複数のより小さいメモリ・タイルを選択するステップを更に含む請求項７に記載の方法。
【請求項９】
ステップ（ｄ）が、前記複数のより小さいメモリ・タイルに含まれたどの記憶場所が前記プリミティブに含まれるかを決定するステップを更に含む請求項７に記載の方法。
【請求項１０】
ステップ（ｄ）が、
ｉ）前記複数のより小さいメモリ・タイルを、複数の更により小さいメモリ・タイルのそれぞれのシーケンスとしてアクセスするステップと、
ｉｉ）前記複数の更により小さいメモリ・タイルのシーケンス内で、前記複数の更により小さいメモリ・タイルをラスタ化するステップとを更に含む請求項７に記載の方法。
【請求項１１】
ラスタ化を行うために、前記複数の更により小さいメモリ・タイルのシーケンス内で複数の更により小さいメモリ・タイルを選択するステップを更に含む請求項１０に記載の方法。
【請求項１２】
フレーム・バッファのグラフィックス・プリミティブをラスタ化するシステムであって、
前記フレーム・バッファの複数の記憶場所のグループを複数のメモリ・タイルとしてアクセスする手段と、
メモリ・タイルを複数のより小さいメモリ・タイルのシーケンスとしてアクセスする手段と、
前記複数のより小さいメモリ・タイルのシーケンス内で前記複数のより小さいメモリ・タイルをラスタ化して、当該ラスタ化がグラフィックス・プリミティブの頂点を含むより小さいメモリ・タイルに対して先ず実行されるようにする手段であって、複数のより小さなメモリ・タイル内に含まれるどの記憶位置が前記プリミティブ内に含まれるかを決定する手段を更に含み、更に、
前記プリミティブの各エッジに対して１つのエッジ評価器であって、各エッジ評価器が前記複数のより小さなメモリ・タイル内のｘ及びｙ値に対するそれぞれのエッジ関数を計算するように構成されている手段と、
各エッジ評価器に対する１つの加算器ツリーであって、エッジ評価器に対する前記加算器ツリーが前記複数のより小さなメモリ・タイル内の各記憶位置に対するエッジ評価器のエッジ関数を再計算するように構成されている手段、
とを含むシステム。
【請求項１３】
ラスタ化を行うために、前記複数のより小さいメモリ・タイルのシーケンス内で複数のより小さいメモリ・タイルを選択する手段を更に含む請求項１２に記載のシステム。
【請求項１４】
より小さいメモリ・タイルをラスタ化する前記手段が、前記複数のより小さいメモリ・タイルに含まれたどの記憶場所が前記プリミティブに含まれるかを決定する手段を更に含む請求項１２に記載のシステム。
【請求項１５】
より小さいメモリ・タイルをラスタ化する前記手段が、
前記より小さいメモリ・タイルを、複数の更により小さいメモリ・タイルのそれぞれのシーケンスとしてアクセスする手段と、
前記複数の更により小さいメモリ・タイルのシーケンス内で、前記更により小さいメモリ・タイルをラスタ化する手段とを更に含む請求項１２に記載のシステム。
【請求項１６】
ラスタ化を行うために、前記複数の更により小さいメモリ・タイルのシーケンス内で複数の更により小さいメモリ・タイルを選択する手段を更に含む請求項１５に記載のシステム。
【請求項１７】
フレーム・バッファのグラフィックス・プリミティブをラスタ化するシステムであって、
前記フレーム・バッファの複数の記憶場所のグループを複数のメモリ・タイルとしてアクセスする手段と、
メモリ・タイルを複数のより小さいメモリ・タイルのシーケンスとしてアクセスする手段と、
前記複数のより小さいメモリ・タイルのシーケンス内で前記複数のより小さいメモリ・タイルをラスタ化して、当該ラスタ化がグラフィックス・プリミティブの頂点を含むより小さいメモリ・タイルに対して先ず実行されるようにする手段と、
を含み、
前記より小さいメモリ・タイルをラスタ化する前記手段が更に、
前記より小さいメモリ・タイルを、複数の更により小さいメモリ・タイルのそれぞれのシーケンスとしてアクセスする手段と、
前記複数の更により小さいメモリ・タイルのシーケンス内で、前記更により小さいメモリ・タイルをラスタ化する手段とを更に含み、
前記更により小さいメモリ・タイルをラスタ化する前記手段が、前記複数の更により小さいメモリ・タイルに含まれたどの記憶場所が前記プリミティブに含まれるかを決定する手段と、前記複数の更により小さいメモリ・タイルのシーケンス内で複数の更により小さいメモリ・タイルを選択する手段と更に含み、
前記複数の更により小さいメモリ・タイルに含まれたどの記憶場所が前記プリミティブに含まれるかを決定する前記手段が、前記プリミティブの各エッジに対して１つのエッジ評価器であって、各エッジ評価器が、前記複数の更により小さいメモリ・タイル内のｘおよびｙ値に対するそれぞれのエッジ関数の値を計算するように構成されているものと、各エッジ評価器に対して１つの加算器ツリーであって、エッジ評価器のための前記加算器ツリーが、前記複数の更により小さいメモリ・タイル内の各記憶場所に対する前記エッジ評価器の前記エッジ関数を再計算するように構成されているものを更に含む、
システム。
【請求項１８】
ＡＮＤゲートのセットを更に含み、前記ＡＮＤゲートが前記複数の加算器ツリーの出力を結合し、前記ＡＮＤゲートが複数の出力のセットを作成し、各出力が、更により小さいメモリ・タイルの特定の記憶場所が前記プリミティブに含まれるかどうかを指定する請求項１７に記載のシステム。
【請求項１９】
プロセッサ上で実行されると、当該プロセッサをして、
より大きいメモリ・タイルに含まれた複数のより小さいメモリ・タイルから、その内の１つを選択するステップであって、該選択されたより小さいメモリ・タイルが前記プリミティブの頂点を含むステップと、
前記より大きいメモリ・タイルに含まれた前記複数のより小さいメモリ・タイルを横断するステップであって、その横断は、前記選択されたより小さいメモリ・タイルで開始して、前記プリミティブ内に位置する１つ以上の記憶場所を有する各より小さいメモリ・タイルを順に通る、横断するステップと、
複数のより小さなメモリ・タイル内に含まれるどの記憶位置が前記プリミティブ内に位置するかを決定するステップであって、
ｉ）前記プリミティブの各エッジに対する１つのエッジ評価器を用いて、前記複数のより小さなメモリ・タイル内のｘ及びｙ座標に対するそれぞれのエッジ関数の値を計算するステップと、
ｉｉ）各エッジ評価器に対する１つの加算器ツリーを用いて、前記複数のより小さなメモリ・タイル内の各記憶位置に対するエッジ評価器のエッジ関数を再計算するステップと、
からなるステップと、
前記横断ステップ中に出会った各より小さいメモリ・タイルをラスタ化するステップと、
を実行させる命令を記憶する機械可読媒体。
【請求項２０】
プロセッサ上で実行されると、当該プロセッサをして、
前記プリミティブ内の記憶場所を含むメモリ・タイルのセットを横断するステップと、
複数のメモリ・タイル内に含まれるどの記憶位置が前記プリミティブ内に位置するかを決定するステップであって、
ｉ）前記プリミティブの各エッジに対する１つのエッジ評価器を用いて、前記複数のメモリ・タイル内のｘ及びｙ座標に対するそれぞれのエッジ関数の値を計算するステップと、
ｉｉ）各エッジ評価器に対する１つの加算器ツリーを用いて、前記複数のメモリ・タイル内の各記憶位置に対するエッジ評価器のエッジ関数を再計算するステップと、
からなるステップと、
前記複数のメモリ・タイルのセットの横断中に出会った前記複数のメモリ・タイルを、複数のより小さいメモリ・タイルのそれぞれのシーケンスとしてアクセスするステップと、
前記複数のより小さいメモリ・タイルのシーケンス内の複数のより小さいメモリ・タイルをラスタ化して、当該ラスタ化が前記プリミティブの頂点を含むより小さいメモリ・タイルに対して先ず実行されるようにするステップと、
を実行させる命令を記憶する機械可読媒体。
【請求項２１】
コンピュータに、
ａ）より大きいメモリ・タイルに含まれた複数のより小さいメモリ・タイルから、その内の１つを選択するステップであって、該選択されたより小さいメモリ・タイルが前記プリミティブの頂点を含むステップと、
ｂ）前記より大きいメモリ・タイルに含まれた前記複数のより小さいメモリ・タイルを横断するステップであって、その横断は、前記選択されたより小さいメモリ・タイルで開始して、前記プリミティブ内に位置する１以上の記憶場所を有する各より小さいメモリ・タイルを順に通る、横断するステップと、
ｃ）複数のより小さなメモリ・タイル内に含まれるどの記憶位置が前記プリミティブ内に位置するかを決定するステップであって、
ｉ）前記プリミティブの各エッジに対する１つのエッジ評価器を用いて、前記複数のより小さなメモリ・タイル内のｘ及びｙ座標・に対するそれぞれのエッジ関数の値を計算するステップと、
ｉｉ）各エッジ評価器に対する１つの加算器ツリーを用いて、前記複数のより小さなメモリ・タイル内の各記憶位置に対するエッジ評価器のエッジ関数を再計算するステップと、
からなるステップと、
ｄ）ステップ（ｃ）中に出会った各記憶位置をラスタ化するステップと、
を含む、プリミティブのラスタ化方法を実行させるプログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項２２】
前記より大きいメモリ・タイルが、更により大きいメモリ・タイルに含まれた複数の前記より大きいメモリ・タイルからのものであり、前記方法が、
ｅ）前記プリミティブ内に位置する１以上の記憶場所を有する、前記更により大きいメモリ・タイル内の各より大きいメモリ・タイルを横断するステップと、
ｆ）ステップ（ａ）、（ｂ）および（ｃ）を、ステップ（ｅ）中に出会ったより大きい各メモリ・タイルに適用するステップとを更に含む請求項２１に記載のコンピュータ読み取り可能な記録媒体。
【請求項２３】
前記更により大きいメモリ・タイルが、前記プリミティブにわたる一連の複数の更により大きいメモリ・タイルの１つであり、前記方法が、
ｇ）各更により大きいメモリ・タイルを横断するステップと、
ｈ）ステップ（ｅ）および（ｆ）を、ステップ（ｇ）中に出会った各更により大きいメモリ・タイルに適用するステップとを更に含む請求項２２に記載のコンピュータ読み取り可能な記録媒体。
【請求項２４】
前記更により大きいメモリ・タイルに含まれた複数の前記より大きいメモリ・タイルが、方形または正方形として配置され、左から右へ、上から下へ横断される請求項２２に記載のコンピュータ読み取り可能な記録媒体。
【請求項２５】
前記プリミティブの頂点を開始頂点として選択するステップと、
より小さいメモリ・タイルを選択し、当該より小さいメモリ・タイルが前記開始頂点を含むようにするステップとを更に含む請求項２１に記載のコンピュータ読み取り可能な記録媒体。
【請求項２６】
前記より大きいメモリ・タイルに含まれた複数の前記より小さいメモリ・タイルが、方形または正方形として配置され、左から右へ、上から下へ横断される請求項２１に記載のコンピュータ読み取り可能な記録媒体。
【請求項２７】
複数のピクセルがメモリ・タイルに組織化されたメモリに記憶されたプリミティブをラスタ化する方法であって、
ａ）より大きいメモリ・タイルに含まれた複数のより小さいメモリ・タイルから、その内の１つを選択するステップであって、該選択されたより小さいメモリ・タイルが前記プリミティブの頂点を含むステップと、
ｂ）前記より大きいメモリ・タイルに含まれた前記複数のより小さいメモリ・タイルを横断するステップであって、その横断は、前記選択されたより小さいメモリ・タイルで開始して、前記プリミティブ内に位置する１以上の記憶場所を有する各より小さいメモリ・タイルを順に通る、横断するステップと、
ｃ）ステップｂ）中に出会った各より小さいメモリ・タイルをラスタ化するステップ、
とを含み、前記より大きいメモリ・タイルが、更に大きいメモリ・タイルに含まれる複数のより大きいメモリ・タイルからのものであって、前記方法が更に、
ｄ）前記プリミティブ内に位置する１つ以上の記憶場所を有する、前記更により大きいメモリ・タイル内の各より大きいメモリ・タイルを横断するステップと、
ｅ）ステップ（ａ）、（ｂ）および（ｃ）を、ステップ（ｄ）中に出会ったより大きい各メモリ・タイルに適用するステップ、
とを含み、
メモリ・タイルは２つ以上のピクセルの記憶を構成し、単一のピクセルをアクセスする為に用いられるアドレスの一部を用いてアドレスされ、
前記より小さいメモリ・タイル、より大きいメモリ・タイル及び前記更により大きいメモリ・タイルの横断が順番に実行され、かつ前記横断はレンダリング装置によって前記プリミティブの完全に外部に在ると決定されたメモリ・タイルを除外し、当該レンダリング装置が、
前記プリミティブの頂点を含む選択されたより小さいメモリ・タイルからのｘ及びｙ値で各々初期化される３つのエッジ評価器と、
ラスタ化されているメモリ・タイル内の各ｘ及びｙ位置に対する各エッジ評価器から受け取った値をそれぞれが再計算する３つの加算器ツリーと、
前記プリミティブを含むメモリ・タイル内のメモリ位置を表す値のセットを提供するＡＮＤ手段と、
から成ることを特徴とする方法。
【請求項２８】
複数のピクセルがメモリ・タイルに組織化されたメモリに記憶されたプリミティブをラスタ化する方法であって、
ａ）より大きいメモリ・タイルに含まれた複数のより小さいメモリ・タイルから、その内の１つを選択するステップであって、前記より大きいメモリ・タイルは更に大きなメモリ・タイルに含まれ、前記選択されたより小さいメモリ・タイルが前記プリミティブの頂点を含むステップと、
ｂ）前記より大きいメモリ・タイルに含まれた前記複数のより小さいメモリ・タイルを横断するステップであって、その横断は、前記選択されたより小さいメモリ・タイルで開始して、前記プリミティブ内に位置する１以上の記憶場所を有する各より小さいメモリ・タイルを順に通る、横断するステップと、
ｃ）ステップｂ）中に出会った各より小さいメモリ・タイルをラスタ化するステップであって、前記より大きいメモリ・タイルに含まれるより小さいメモリ・タイルが方形または正方形として配置され、前記より小さいメモリ・タイル、より大きいメモリ・タイル及び前記更により大きいメモリ・タイルがそれぞれの順番で横断され、
メモリ・タイルのアドレスがメモリ・タイル内に記憶された２つ以上のピクセルをアクセスし、かつ前記横断はレンダリング装置によって前記プリミティブの完全に外部に在ると決定されたメモリ・タイルを除外し、当該レンダリング装置が、
前記プリミティブの頂点を含む選択されたより小さいメモリ・タイルからのｘ及びｙ値で各々初期化される３つのエッジ評価器と、
ラスタ化されているメモリ・タイル内の各ｘ及びｙ位置に対する各エッジ評価器から受け取った値をそれぞれが再計算する３つの加算器ツリーと、
前記プリミティブを含むメモリ・タイル内のメモリ位置を表す値のセットを提供するＡＮＤ手段と、
から成ることを特徴とする方法。
【請求項２９】
各々が２つ以上のピクセルを含む一連の方形のメモリ・タイルとして編成されているフレーム・バッファ内のプリミティブをラスタ化する方法であって、
ａ）前記プリミティブ内の記憶場所を含むメモリ・タイルのセットを横断するステップであって、当該横断が前記プリミティブの頂点を含むメモリ・タイルから開始するステップと、
ｂ）ステップ（ａ）中に出会った複数の前記メモリ・タイルを、複数のより小さいメモリ・タイルのそれぞれのシーケンスとしてアクセスするステップと、
ｃ）前記複数のより小さいメモリ・タイルのシーケンス内の複数のより小さいメモリ・タイルをラスタ化するステップであって、更に前記複数のより小さいメモリ・タイルを、複数の更により小さいメモリ・タイルのそれぞれのシーケンスとしてアクセスするステップと、前記複数の更により小さいメモリ・タイルのシーケンス内で、前記複数の更により小さいメモリ・タイルをラスタ化するステップとから成るステップと、
からなり、
ラスタ化はタイルサイズの増大に従う階層的に実行され、かつ前記横断はレンダリング装置によって前記プリミティブの完全に外部に在ると決定されたメモリ・タイルを除外し、当該レンダリング装置が、
前記プリミティブの頂点を含む選択されたより小さいメモリ・タイルからのｘ及びｙ値で各々初期化される３つのエッジ評価器と、
ラスタ化されているメモリ・タイル内の各ｘ及びｙ位置に対する各エッジ評価器から受け取った値をそれぞれが再計算する３つの加算器ツリーと、
前記プリミティブを含むメモリ・タイル内のメモリ位置を表す値のセットを提供するＡＮＤ手段と、
から成ることを特徴とする方法。
【発明の詳細な説明】
【０００１】
（発明の分野）
本発明は、一般に、コンピュータ・グラフィックスのシステムに関する。具体的には、本発明はグラフィックス・プリミティブを効率的にラスタ化する方法および装置を含む。
【０００２】
（発明の背景）
コンピュータ・システム（および関連デバイス）は、典型的に、グラフィックス・パイプラインとして知られるステージのシーケンスを使用して３次元画像を作成する。初期のパイプライン・ステージ中に、モザイクのような手法を用いて画像がモデリングされる。その際、各画像は個々の点、直線、多角形の集合からなる。これらの点、直線、多角形は、プリミティブとして知られており、単一の画像には、数千または数百万ものプリミティブが必要になることもある。各プリミティブは、その形状および位置、並びに色およびテクスチャなどの他の属性に関して定義される。
【０００３】
初期のパイプライン・ステージで使用されたプリミティブは、ラスタ化ステージ中にピクセル値の集合に変換される。ラスタ化ステージは、専用グラフィックス・プロセッサによって実行されることが多く（ローエンド・システムでは、直接ホスト・プロセッサがラスタ化を実行することもある）、結果として生じるピクセル値が、フレーム・バッファとして知られるデバイスに格納される。フレーム・バッファとは、一連のランダム・アクセス可能な記憶場所を含むメモリである。フレーム・バッファ内の各記憶場所は、画像が最後に表示される出力デバイスに含まれている対応するピクセルを定義する。その対応するピクセルを定義するために、各記憶場所は一連のビットを含む。典型的には、これらのビットが、赤、青、緑の輝度を定義する分離部分に分割される。各記憶場所は、重なり合うプリミティブの間のピクセル所有権を決定する深度情報を含むであろう。
【０００４】
ラスタ化ステージ中に、グラフィックス・プロセッサは各プリミティブをフレーム・バッファ内にレンダリングする。グラフィックス・プロセッサはこの作業を実施するにあたって、どのフレーム・バッファ記憶場所が各プリミティブの境界内に含まれるかを決定する。次いで、含まれる記憶場所が、色およびテクスチャを含むプリミティブの属性を反映するように初期化される。
【０００５】
ラスタ化ステージの後に、表示ステージが続く。このステージでは、表示コントローラが、フレーム・バッファに格納されたピクセル値を使用中の出力デバイスを駆動する信号へ変換する。表示コントローラは、フレーム・バッファに含まれる記憶場所を走査することによってこの作業を実施する。各場所の赤、青、緑の部分が適切な出力信号に変換され、出力デバイスへ送信される。
【０００６】
グラフィックス・パイプラインのスループットは、フレーム・バッファの性能に大いに依存している。これは、フレーム・バッファがラスタ化ステージと表示ステージの間の媒介者として機能するためである。結果として、フレーム・バッファは、グラフィックス・プロセッサと表示コントローラが共に繰り返しメモリ・アクセスを行う中心となる。これらのアクセス数は、非常に多くなる可能性がある。フレーム・バッファは、性能ボトルネックになることを避けようとする場合、これらのアクセスの高い割合を維持できなければならない。
【０００７】
フレーム・バッファは、典型的に、ダイナミック・ランダム・アクセス・メモリ（ＤＲＡＭ）構成要素のアレイを使用して製作される。スタティック・ランダム・アクセス・メモリ（ＳＲＡＭ）などの他の技術と比較すると、ＤＲＡＭ構成要素は、性能とコストの間でよりよい折り合いを表す。同時に、受け入れ可能なフレーム・バッファ性能を達成することは、ＤＲＡＭ構成要素を使用すると、かなり複雑になる可能性がある。ＤＲＡＭ使用に含まれる複雑性は、これらの構成要素によって使用されるアドレス指定スキームから生ずる。このスキームでは、記憶場所が、行アドレスおよび列アドレスの組み合わせを用いてアドレス指定される。行および列アドレスは、行アドレスが最初、列アドレスが２番目の順序で供給される。使用するＤＲＡＭ構成要素の特定のタイプに応じて、この２ステップのアドレス指定スキームでは、フレーム・バッファ使用に必要なメモリ・アクセス率を維持するために時間がかかりすぎる可能性がある。
【０００８】
幸いに、多数のＤＲＡＭ構成要素がより高速のページ・アドレス指定モードも備えている。このモードでは、行アドレスを供給した後で、列アドレスのシーケンスをＤＲＡＭ構成要素に供給することができる。行内のアクセスには、単一のアドレスのみが必要である。全体の効果は、ＤＲＡＭ構成要素へのアクセスが、一連のアクセスが単一の行に限られるときに大幅に高速になることである。新しい行に含まれる場所へのアクセスは、ページ・ミスと呼ばれ、大幅に遅い。
【０００９】
このため、フレーム・バッファはＤＲＡＭの行内の連続アクセスを最大にして、ページ・ミスを最小にするように設計されることが多い。これを実施する１つの方法は、グラフィックス・プリミティブが単一ＤＲＡＭの行または少数のＤＲＡＭの行にマッピングする傾向になるように、フレーム・バッファを構築することである。メモリ・タイリングはこのタイプのフレーム・バッファ構造の一例である。メモリ・タイリングを使用するフレーム・バッファでは、ＤＲＡＭの行に含まれる記憶場所がピクセルの方形ブロックにマッピングする。これは、ＤＲＡＭの行がピクセルの直線にマッピングする、より典型的なフレーム・バッファ構成と対照的である。メモリ・タイリングは、多くのプリミティブが容易にブロックに適合し、容易に直線に適合するプリミティブがほとんどないということを利用している。このようにして、メモリ・タイリングは、所与のプリミティブが単一のＤＲＡＭの行または少数のＤＲＡＭの行に含まれる機会を増加することによって、ページ・ミスを低減する。
【００１０】
ＤＲＡＭの行内の連続アクセスを最大にし、ページ・ミスを最小にするための別の方法は、グラフィックス・プロセッサとフレーム・バッファとの間にキャッシュ・メモリを配置することである。キャッシュ・メモリは、グラフィックス・プロセッサによって実行されたアクセスを収集し、それらをより効率的な行毎にキャッシュへ送る。
【００１１】
メモリ・タイリングとキャッシュ・メモリは共に、ＤＲＡＭベースのフレーム・バッファの性能を向上させるための有効な技術である。残念ながら、大抵のフレーム・バッファ内で使用されるラスタ化技術は、メモリ・タイリングまたはメモリ・タイリングと組み合わせて使用されるキャッシュ・メモリの全性能を十分に活用しない。これは、ラスタ化が典型的には行毎に実行されるためである。タイル化フレーム・バッファで使用する場合、行毎のラスタ化は、フレーム・バッファのタイル化構造を実際上無視する。結果として、所与のラスタ化は、あるいは所与のタイルのセットにアクセスおよび再アクセスする可能性がある。これによって、ＤＲＡＭページ・ミスの数が増加し、フレーム・バッファおよびグラフィックス・パイプラインのスループットが減少する結果となる。結果として、メモリ・タイリングおよびメモリ・タイリングと組み合わせて使用されるキャッシュ・メモリの全性能をより効果的に活用するラスタ化方法が必要である。
【００１２】
（発明の概要）
本発明の一実施態様は、グラフィックス・プリミティブを効率的にラスタ化する方法および装置を含む。以下の説明においては、本発明の一実施態様を、代表的なグラフィックス・パイプラインに関連して記載する。グラフィックス・パイプラインは、ホスト・コンピュータ・システムに含まれた構成要素のシーケンスである。この構成要素のシーケンスは、フレーム・バッファと、その後に続く表示コントローラで終了する。
【００１３】
フレーム・バッファは、一連の記憶場所を含むランダム・アクセス・メモリ・デバイスである。フレーム・バッファ内の記憶場所は、モニタなどの出力デバイスに含まれるピクセルに対応する。各記憶場所は、一連のビットを含み、ビットの数および分布は実装によって決まる。説明のため、各記憶場所が４つの８ビット・バイトを含むと仮定することができる。これらのバイトの３つは、赤、青、緑の輝度をそれぞれ定義する。４番目のバイトであるアルファは、ピクセルのカバーレッジまたは透過性を定義する。
【００１４】
フレーム・バッファに含まれる記憶場所は、タイル化アドレス指定スキームを使用して編成されることが好ましい。このスキームでは、フレーム・バッファに含まれる記憶場所が、出力デバイスに含まれるピクセルの方形タイルに対応して編成される。単一のタイルに含まれるピクセルの数（およびフレーム・バッファ記憶場所の数）は、異なるフレーム・バッファ実装の間で変わる可能性がある。大抵の場合、タイルのサイズは２の累乗となる。これによって、上位のアドレス・ビットが特定のタイルを選択し、下位のアドレス・ビットが特定のタイル内のオフセットを選択するという、好都合なスキームを提供することができる。フレーム・バッファがＤＲＡＭまたはＤＲＡＭのようなメモリ構成要素を使用して製作されている場合、各タイルがＤＲＡＭの行の一部にマッピングすることが好ましい。したがって、各ＤＲＡＭの行は１つまたは複数のメモリ・タイルを含む。
【００１５】
表示コントローラは、フレーム・バッファに含まれた記憶場所を走査する。走査する各場所について、表示コントローラは、赤、青、緑の輝度を適切な出力信号へ変換する。表示コントローラは、これらの出力信号を使用中の出力デバイスへ送信する。表示コントローラはこの走査プロセスを継続的に繰り返す。このようにして、フレーム・バッファの内容が継続的に出力デバイスへ送信される。
【００１６】
グラフィックス・プロセッサは、グラフィックス・プリミティブをフレーム・バッファにラスタ化する。この作業を実施するため、グラフィックス・プロセッサは、どのフレーム・バッファ記憶場所が各プリミティブの境界内に含まれるかを決定する。次いで、含まれる記憶場所が、色およびテクスチャを含むプリミティブの属性を反映するように初期化される。ラスタ化中に、グラフィックス・プロセッサはメモリ・タイルの階層を使用する。この階層内では、より小さいタイルがより大きいタイルにグループ化される。これらのより大きいタイルは、さらに大きいタイルにグループ化される可能性がある。本発明の代表的な実施態様では、タイル階層は３つのレベルを含む。この階層の最下位レベルは、４ピクセル×４ピクセルの低レベル・タイルからなる。これらの４×４タイルは８×８の中間レベル・タイルにグループ化され、８×８タイルは１６×１６の高レベル・タイルにグループ化される。
【００１７】
グラフィックス・プロセッサは、プリミティブの頂点の１つを開始頂点として選択することによって、プリミティブをラスタ化するプロセスを開始する。次いで、グラフィックス・プロセッサは、開始頂点を含む低レベル・タイルをラスタ化する。最初の低レベル・タイルのラスタ化が完了したとき、グラフィックス・プロセッサは、最初の低レベル・タイルと同じ中間レベル・タイルに含まれた、残りの低レベル・タイルに対して左から右へ、上から下へ移動する。グラフィックス・プロセッサは、プリミティブ内のピクセルを含むこれらの各低レベル・タイルをラスタ化する。これらの低レベル・タイルの最後をラスタ化したとき、グラフィックス・プロセッサは最初の中間レベル・タイルのラスタ化を完了している。
【００１８】
最初の中間レベル・タイルのラスタ化が完了したとき、最初の中間レベル・タイルと同じ高レベル・タイルに含まれた、残りの中間レベル・タイルに対してグラフィックス・プロセッサは左から右へ、上から下へ移動する。グラフィックス・プロセッサは、プリミティブ内のピクセルを含むこれらの各中間レベル・タイルをラスタ化する。これは、最初の中間レベル・タイルをラスタ化するために使用した方法を繰り返すことによって（すなわち、それらの構成要素の低レベル・タイルをラスタ化することによって）行う。これらの中間レベル・タイルの最後をラスタ化したとき、グラフィックス・プロセッサは最初の高レベル・タイルのラスタ化を完了している。
【００１９】
最初の高レベル・タイルのラスタ化が完了したとき、グラフィックス・プロセッサはプリミティブにわたって残りの高レベル・タイルに対して、左から右へ、上から下へ移動する。グラフィックス・プロセッサは、これらの各高レベル・タイルをラスタ化する。これは、最初の高レベル・タイルをラスタ化するために使用した方法を繰り返すことによって（すなわち、それらの構成要素の低レベル・タイルをラスタ化することによってラスタ化される、それらの構成要素の低レベル・タイルをラスタ化することによって）行う。これらの高レベル・タイルの最後をラスタ化したとき、グラフィックス・プロセッサはプリミティブのラスタ化を完了している。
【００２０】
実際上、プリミティブはボトムアップ式にラスタ化される。グラフィックス・プロセッサは低レベル・タイル、中間レベル・タイルおよび高レベル・タイルをラスタ化し、階層を上がる前に各レベルでラスタ化を完了する。タイル階層を使用することによって、所与のメモリ・タイル内のアクセスの時間的局所化が増加する。時間的局所化が増加することによって、タイル・アクセスの間が減少する。高速タイル・ベース・アクセスをサポートするフレーム・バッファでは、これによってグラフィックス・スループットが向上する。所与のメモリ・タイル内のアクセスの時間的局所化が増加することによって、キャッシュ・メモリの性能も向上させることができる。これは特に、キャッシュ・メモリ／フレーム・バッファのインタラクションがタイル毎に実行される場合に真である。
【００２１】
本発明の利点を、部分的に以下の説明において述べるが、部分的には、当業者には本明細書の説明から理解されるであろう。本発明の利点は、特に添付の特許請求の範囲および均等物で指摘した要素および組み合わせを用いて、理解および達成されるであろう。
【００２２】
添付の図面は本明細書に組み込まれ、その一部を構成するものであり、本発明のいくつかの実施形態を例示して、説明と共に本発明の原理を説明するために役立つものである。
【００２３】
（好ましい実施形態の詳細な説明）
以下に、本発明の好ましい実施形態について詳細に説明し、その例を添付の図面において例示する。好都合な場合は、図面全体で同じ参照番号を使用して、同じまたは同様の部分を参照する。
【００２４】
環境 図１では、ホスト・コンピュータ・システム１００を本発明の代表的な環境として示す。構造上、ホスト・コンピュータ・システム１００は、ホスト・プロセッサ１０２ａ〜１０２ｄで表されている単一又は複数のホスト・プロセッサを含む。ホスト・プロセッサ１０２は、幅広い範囲の市販またはメーカ独自のタイプを表す。ホスト・コンピュータ・システム１００は、ホスト・コンピュータ・システム１００の代表的な環境について示した４つよりも多くの、または少ないホスト・プロセッサ１０２を含んでもよい。
【００２５】
ホスト・プロセッサ１０２は、メモリ要求ユニット１０４と、その後に続くメモリ・コントローラ１０６から開始する構成要素のシーケンスに接続される。メモリ・コントローラ１０６の後にシステム・メモリ１０８が続く。ホスト・プロセッサ１０２は、この構成要素のシーケンスを使用して、システム・メモリ１０８に含まれた記憶場所にアクセスする。これらのアクセスの一部として、ホスト・プロセッサ１０２は仮想メモリ・アクセス要求をメモリ要求ユニット１０４へ送信する。メモリ要求ユニット１０４は、この要求を、対応する物理メモリ・アクセス要求へ変換する。次いで、その物理メモリ・アクセス要求がメモリ・コントローラ１０６へ渡される。次いで、メモリ・コントローラ１０６はシステム・メモリ１０８にアクセスして、要求された動作を実行する。上述の実施形態では、メモリ・コントローラ１０６およびシステム・メモリ１０８は、タイル化および線形ページを含むある範囲のページ・タイプをサポートする。メモリ・コントローラ１０６およびシステム・メモリ１０８は、タイル化および線形ページについてある範囲のページ・サイズもサポートする。
【００２６】
メモリ・コントローラ１０６は、他の構成要素がシステム・メモリ１０８にアクセスすることができるインタフェースとしても機能する。図１では、メモリ・コントローラ１０６は、グラフィックス・プロセッサ１１０および入出力コントローラ１１２へのこのタイプのインタフェースとなっている。グラフィックス・プロセッサ１１０は、システム・メモリ１０８に含まれたメモリを使用して、その処理の大部分を実行することが好ましい。これによって、グラフィックス・プリミティブまたはデータがシステム・メモリ１０８からグラフィックス・プロセッサ１１０へ移動された場合に生じる遅延を避けることができる。入出力コントローラ１１２は、ホスト・コンピュータ・システム１００が、ディスク・ドライブ、不揮発性記憶システム、キーボード、モデム、ネットワーク・アダプタおよびプリンタなど、幅広い範囲の入出力デバイスへ接続することができる、チャネルとして機能する。
【００２７】
上述のように、ホスト・コンピュータ・システム１００を、本発明の代表的な環境として示す。しかし、本発明はある範囲のコンピュータ・システムおよび関連デバイスに等しく適用可能であり、ホスト・コンピュータ・システム１００の代表的な環境に限定されるものではないことを理解されたい。
【００２８】
グラフィックス・プロセッサ１１０は、図２に示すタイプの１つまたは複数のフレーム・バッファを使用する。これは全体として符号２００で示されている。フレーム・バッファ２００はランダム・アクセス・メモリ・デバイスであり、一連の記憶場所を含み、記憶場所２０２ａ、２０２ｂおよび２０２ｃが代表的なものである。各記憶場所２０２は、モニタまたはビデオ・ディスプレイなどの出力デバイスに含まれる単一のピクセルに対応する。記憶場所２０２は、一連の行および列に配置される。図２の特定の実施形態では、１０２４行および１２８０列が含まれる。これは、１０２４行および１２８０列のピクセルを有するモニタに対応する。各記憶場所２０２は、一連のビットを含み、ビットの数および分布は実装によって決まる。説明のため、各記憶場所２０２が４つの８ビット・バイトを含むと仮定することができる。これらのバイトの３つは、赤、青、緑の輝度をそれぞれ定義する。各記憶場所２０２に含まれた４番目のバイトはアルファと呼ばれ、ピクセルのカバレッジまたは透過性を定義する。
【００２９】
フレーム・バッファ２００は、典型的に、メモリ構成要素のアレイを使用して製作される。これらの構成要素は、ＶＲＡＭおよびＳＤＲＡＭタイプを含む、適切なＤＲＡＭタイプから選択することができる。ホスト・コンピュータ・システム１００の特定の実施形態では、フレーム・バッファ２００がシステム・メモリ１０８内で動的に割り付けられる。他のアーキテクチャでは、フレーム・バッファ２００を、グラフィックス・プロセッサ１１０などの他の適した場所内に含めることができる。
【００３０】
フレーム・バッファ２００は、一連のメモリ・タイルを含むことが好ましく、メモリ・タイル２０４ａおよび２０４ｂが代表的なものである。各メモリ・タイル２０４は、方形として配置された一連の記憶場所２０２を含む。メモリ・タイル２０４のサイズは実装によって大きく変わる。したがって、フレーム・バッファ２００は、大型または小型のメモリ・タイル２０４を含むように構成することができる。メモリ・タイル２０４の寸法も、実装によって大きく変わる。したがって、フレーム・バッファ２００は、高い、または幅広いメモリ・タイル２０４を含むことができる。さらに一般には、いくつかの実装では、フレーム・バッファ２００が、ある範囲のサイズおよび寸法を有するメモリ・タイル２０４の混合物を含むことが可能である。図２の特定の実施形態では、各メモリ・タイル２０４が、１６×１６の正方形として配置された、合計で２５６の記憶場所２０２を含む。
【００３１】
フレーム・バッファ２００は、上位のアドレス・ビットが特定のメモリ・タイル２０４を選択し、下位のアドレス・ビットは選択されたメモリ・タイル２０４内の特定の記憶場所２０２を選択するという、アドレス指定スキームを使用することが好ましい。フレーム・バッファ２００がＤＲＡＭまたはＤＲＡＭのようなメモリ構成要素を使用して製作されている場合、各メモリ・タイル２０４がＤＲＡＭの行の一部をマッピングすることが好ましい。したがって、各ＤＲＡＭの行は１つまたは複数のメモリ・タイル２０４を含む。これによって、メモリ・タイル２０４内の複数の記憶場所に、単一のＤＲＡＭの行アドレスを使用してアクセスすることができる。あるタイプの高速行内アクセス・モード（ページ・モード・アクセスなど）を利用するＤＲＡＭ構成要素では、これによって、タイル内に含まれた記憶場所２０２に連続して高速にアクセスできる。
【００３２】
タイル階層
フレーム・バッファ２００内で、メモリ・タイル２０４はタイル階層の最高レベルを表す。この階層の他のレベルを図３でより明確に示す。この図ではメモリ・タイル２０４が４つの中間レベル・タイル３００ａから３００ｄを含む。各中間レベル・タイル３００は、４つの低レベル・タイル３０２ａから３０２ｄを含む。全体の結果として、３レベルの階層が形成される。この階層内で、４×４の低レベル・タイル３０２が８×８の中間レベル・タイル３００にグループ化され、８×８の中間レベル・タイル３００が１６×１６のメモリ・タイル２０４にグループ化される。より多くのレベルまたは少ないレベルを含む他の階層は同様に可能である。
【００３３】
ラスタ化方法
本発明の一実施形態は、グラフィックス・プリミティブを効率的にラスタ化する方法を提供することである。このラスタ化方法は、点、直線および多角形を含む、幅広い範囲のグラフィックス・プリミティブタイプと組み合わせて作業することを意図している。
【００３４】
グラフィックス・プロセッサ１１０は、プリミティブの頂点の１つを開始頂点として選択することによって、プリミティブをラスタ化するプロセスを開始する。次いで、グラフィックス・プロセッサ１１０は、開始頂点を含む低レベル・タイル３０２をラスタ化する。最初の低レベル・タイル３０２のラスタ化が完了したとき、グラフィックス・プロセッサ１１０は、中間レベル・タイル３００に含まれた残りの低レベル・タイル３０２に対して最初の低レベル・タイル３０２と同じように、左から右へ、上から下へ移動する。グラフィックス・プロセッサ１１０は、プリミティブ内のピクセルを含むこれらの各低レベル・タイル３０２をラスタ化する。これらの低レベル・タイル３０２の最後をラスタ化したとき、グラフィックス・プロセッサ１１０は最初の中間レベル・タイル３００のラスタ化を完了している。
【００３５】
最初の中間レベル・タイル３００のラスタ化が完了したとき、グラフィックス・プロセッサ１１０は、最初の中間レベル・タイル３００と同じメモリ・タイル２０４に含まれた残りの中間レベル・タイル３００に対して、左から右へ、上から下へ移動する。グラフィックス・プロセッサ１１０は、プリミティブ内のピクセルを含むこれらの各中間レベル・タイル３００をラスタ化する。これは、最初の中間レベル・タイル３００をラスタ化するために使用した方法を繰り返すことによって（すなわち、それらの構成要素の低レベル・タイル３０２をラスタ化することによって）行う。これらの中間レベル・タイル３００の最後をラスタ化したとき、グラフィックス・プロセッサ１１０は最初のメモリ・タイルのラスタ化を完了している。
【００３６】
最初のメモリ・タイル２０４のラスタ化が完了したとき、グラフィックス・プロセッサ１１０はプリミティブにわたる残りのメモリ・タイル２０４に対して左から右へ、上から下へ移動する。グラフィックス・プロセッサ１１０は、これらの各メモリ・タイル２０４をラスタ化する。これは、最初のメモリ・タイル２０４をラスタ化するために使用した方法を繰り返すことによって（すなわち、それらの構成要素の低レベル・タイル３０２をラスタ化することによってラスタ化される、それらの構成要素の低レベル・タイル３０２をラスタ化することによって）行う。これらのメモリ・タイル２０４の最後をラスタ化したとき、グラフィックス・プロセッサ１１０はプリミティブのラスタ化を完了している。
【００３７】
ラスタ化方法をよりよく説明するため、図４にフレーム・バッファ２００の一部に載る例示的プリミティブ４００を示す。プリミティブ４００は、三角形である。この特定の形状は、一般的なプリミティブを表すために選択されたものであり、本発明は他のプリミティブの形状およびタイプにも等しく利用できるのであることを理解されたい。図４のように、プリミティブ４００は、２つのメモリ・タイル２０４ａおよび２０４ｂにわたっている。
【００３８】
プリミティブ４００のラスタ化を開始するため、グラフィックス・プロセッサ１１０は、プリミティブ４００の頂点から開始頂点を選択する。一般には、頂点の選択は幾分恣意的であり、本発明は、いかなる所与の点においてもラスタ化を開始するように適合させることができる。しかし、以下の説明を簡素にするため、グラフィックス・プロセッサ１１０がプリミティブ４００の左上の頂点を開始頂点として選択すると仮定する。
【００３９】
開始頂点を選択した後、グラフィックス・プロセッサ１１０は、１のマークがついた低レベル・タイル３０２のピクセルをラスタ化する。低レベル・タイル３０２−１が開始頂点を含むので、この場所でラスタ化が開始する。低レベル・タイル３０２−１をラスタ化した後、グラフィックス・プロセッサ１１０は、低レベル・タイル３０２−１を含む中間レベル・タイル３００内で、左から右へ、上から下へ移動する。グラフィックス・プロセッサ１１０は、プリミティブ４００内のピクセルを含むこの中間レベル・タイル内の各低レベル・タイル３０２をラスタ化する。特定すると、グラフィックス・プロセッサ１１０は右へ移動して低レベル・タイル３０２−２をラスタ化し、下へ移動して低レベル・タイル３０２−３をラスタ化する。
【００４０】
この時点で、グラフィックス・プロセッサ１１０は最初の中間レベル・タイル３００のラスタ化を完了している（この中間レベル・タイル３００内に含まれた最後の低レベル・タイル３０２は完全にプリミティブ４００の領域外にある）。ラスタ化・プロセスを継続するため、グラフィックス・プロセッサ１１０は、次の中間レベル・タイル３００内の低レベル・タイル３０２−４へジャンプする。グラフィックス・プロセッサ１１０は、低レベル・タイル３０２を横断するために使用したものと同じ、左から右へ、上から下へのパターンを使用して、中間レベル・タイル３００を選択する。低レベル・タイル３０２−４をラスタ化した後、グラフィックス・プロセッサ１１０は、低レベル・タイル３０２−４を含む中間レベル・タイル３００内で、左から右へ、上から下へ移動する。特定すると、グラフィックス・プロセッサ１１０は右へ移動して低レベル・タイル３０２−５をラスタ化し、左下へ移動して低レベル・タイル３０２−６をラスタ化し、右へ移動して低レベル・タイル３０２−７をラスタ化する。
【００４１】
この時点で、グラフィックス・プロセッサ１１０は、最初のメモリ・タイル２０４ａのラスタ化を完了している（残りの中間レベル・タイル３０２およびそれらに含まれた低レベル・タイル３０２は完全にプリミティブ４００の領域外にある）。ラスタ化・プロセスを継続するため、グラフィックス・プロセッサ１１０は、次のメモリ・タイル２０４ｂ内の低レベル・タイル３０２−８へジャンプする。グラフィックス・プロセッサ１１０は、中間レベル・タイル３００および低レベル・タイル３０２を横断するために使用したものと同じ、左から右へ、上から下へのパターンを使用して、メモリ・タイル２０４を選択する。低レベル・タイル３０２−４をラスタ化した後、グラフィックス・プロセッサ１１０は、低レベル・タイル３０２−８を含む中間レベル・タイル３００内で、左から右へ、上から下へ移動する。特に、グラフィックス・プロセッサ１１０は下へ移動して、低レベル・タイル３０２−９をラスタ化する。低レベル・タイル３０２−９をラスタ化することによって、グラフィックス・プロセッサ１１０は、プリミティブ４００のラスタ化を完了する。
【００４２】
上述の説明において、グラフィックス・プロセッサ１１０は、左から右へ、上から下への横断を使用して、メモリ・タイル２０４、中間レベル・タイル３００および低レベル・タイル３０２を選択する。一般には、この特定の横断パターンは、多数の可能なパターンの１つでしかないことを理解されたい。実際に、本発明は、ラスタ化がより高い階層レベルへ進む前により低い各レベルで完了することを確実にする、いかなるパターンの使用にも適合させることができる。異なる横断パターンを異なる階層レベルで使用することができることも、明らかであるべきである。したがって、グラフィックス・プロセッサ１１０は、第１の横断パターンを使用してメモリ・タイル２０４を横断し、第２の横断パターンを使用して中間レベル・タイル３００を横断し、第３の横断パターンを使用して低レベル・タイル３０２を横断することができる。
【００４３】
上述の説明では、グラフィックス・プロセッサ１１０は、横断パターンを修正して、ラスタ化中のプリミティブの全く外部に入るメモリ・タイル２０４、中間レベル・タイル３００および低レベル・タイル３０２を除外することも同様に仮定する。この修正を実施するため、グラフィックス・プロセッサ１１０がルックアヘッド機構を含むように構成されることが好ましい。ルックアヘッド機構は、グラフィックス・プロセッサ１１０が所与の低レベル・タイル３０２をラスタ化中に、どの低レベル・タイルを次にラスタ化すべきかを決定する。ルックアヘッド機構は、ラスタ化中のプリミティブの全く外部に入るメモリ・タイル２０４、中間レベル・タイル３００および低レベル・タイル３０２を無視するように構成されることが好ましい。しかし、このタイプの機構は好ましいが、必要ではないことを理解されたい。したがって、グラフィックス・プロセッサ１１０は、中間レベル・タイル３００内の低レベル・タイル３０２又はメモリ・タイル２０４内の中間レベル・タイル３００を網羅的に横断するように構成することができる。
【００４４】
グラフィックス・プロセッサ１１０は、タイル階層を使用して、グラフィックス・プリミティブのラスタ化中に低レベル・タイル３０２が選択される順序を制御する。この順序付けの効率を最大にするため、グラフィックス・プロセッサ１１０は、選択された低レベル・タイル３０２内の１６の記憶場所２０２を同時またはほぼ同時にラスタ化するように構成されることが好ましい。上述の実施形態では、グラフィックス・プロセッサ１１０は、次の形式の一次式を用いて各プリミティブの各エッジを定義することによって、この同時性を達成する。すなわち、Ｆ（ｘ，ｙ）＝Ａｘ＋Ｂｙ＋Ｃである。これらの式を使用すると、１つのエッジのある側にあるすべての点がＦ（ｘ，ｙ）≧０である。同じエッジの別の側のすべての点は、Ｆ（ｘ，ｙ）≦０である。所与のプリミティブに対して低レベル・タイル３０２をラスタ化するには、グラフィックス・プロセッサ１１０は、低レベル・タイル３０２内の各記憶場所２０２に対するプリミティブのエッジ関数のそれぞれを計算する。たとえば、エッジＦ（ｘ，ｙ）、Ｆ’（ｘ，ｙ）およびＦ”（ｘ，ｙ）によって境界付けられた三角形のプリミティブでは、グラフィックス・プロセッサ１１０は、これらの各式を、ラスタ化中の低レベル・タイル３０２内の各記憶場所２０２に対して計算する。グラフィックス・プロセッサ１１０は、プリミティブのエッジ関数の奇数が記憶場所２０２でゼロ未満の場合、記憶場所２０２が三角形のプリミティブ内にあると決定する。
【００４５】
グラフィックス・プロセッサ１１０は、追加プロセスを使用して、低レベル・タイル３０２の記憶場所２０２のすべてについて、同時またはほぼ同時にエッジ関数を評価することが好ましい。追加プロセスは、図５を参照することによってよりよく理解することができる。図５は、低レベル・タイル３０２に含まれた記憶場所２０２に対して、グラフィックス・プロセッサ１１０によって計算された値である。図のように、グラフィックス・プロセッサ１１０は、低レベル・タイル３０２の左下隅に位置する記憶場所２０２ａに対して値Ｆ（ｘ，ｙ）を計算する。グラフィックス・プロセッサ１１０は、記憶場所２０２ａの１つ右側の場所に位置する記憶場所２０２ｂについて値Ｆ（ｘ，ｙ）＋Ａを、記憶場所２０２ａの２つ右側の場所に位置する記憶場所２０２ｃについてＦ（ｘ，ｙ）＋２Ａを、計算し、以下同様である。効率的に、グラフィックス・プロセッサ１１０は、記憶場所２０２ａの右側の各記憶場所２０２に対してエッジ関数を計算する。これは、記憶場所２０２ａについて計算したエッジ関数に定数Ａの倍数を加算することによって行う。類似の方法で、グラフィックス・プロセッサ１１０は、記憶場所２０２ａの上の各記憶場所２０２に対してエッジ関数を計算する。これは、定数Ｂの倍数を、記憶場所２０２ａについて計算したエッジ関数に加算することによって行う。記憶場所２０２ａの右側および上にある記憶場所は、ＡおよびＢの適切な倍数を加算することによって計算された値を有する。全体の結果として、グラフィックス・プロセッサ１１０は、Ｆ（ｘ，ｙ）、Ｆ’（ｘ，ｙ）およびＦ”（ｘ，ｙ）を、低レベル・タイル３０２につき一度計算するだけでよい。次いで、計算された値は、一連の加算を用いて、低レベル・タイル３０２に含まれたすべての記憶場所に外挿される。
【００４６】
装置
上述の方法は、幅広い範囲のハードウェアおよびソフトウェア環境において使用可能である。しかし、典型的には、これらの方法は、完全または部分的に専用レンダリング装置内で実装されるときにもっとも効率的である。このタイプの装置を図６に示し、一般には６００で示す。
【００４７】
レンダリング装置６００は、３つのエッジ評価器６０２ａ〜６０２ｃのセットを含む。各エッジ評価器は、入力および制御バス６０４によって、グラフィックス・プロセッサ１１０の残りのロジックに接続される。各エッジ評価器６０２は、それぞれの加算器ツリー６０６ａから６０６ｃにも接続される。加算器ツリー６０６は、ａｎｄゲート６０８に接続される。ａｎｄゲート６０８の出力は、フラグメント選択ユニット６１０に接続される。
【００４８】
各エッジ評価器６０２は、グラフィックス・プロセッサ１１０からの一次式Ｆ（ｘ，ｙ）＝Ａｘ＋Ｂｙ＋Ｃを特徴付けるパラメータのセットを受け入れるように構成される。これらのパラメータには、この式の初期値、および、ＡおよびＢの適切な値が含まれる。グラフィックス・プロセッサ１１０は、これらのパラメータを、入力および制御バス６０４を使用してエッジ評価器６０２へ送信する。エッジ評価器６０２は、初期化された後、それらの関連するエッジ式について連続した値を計算するように構成されている。エッジ評価器６０２は、ＡまたはＢをそれらの初期値に適切に加算することによって、これらの値を計算する。
【００４９】
所与のプリミティブをラスタ化する前に、グラフィックス・プロセッサ１１０は、このプリミティブを表す各エッジ関数の初期値を計算する。グラフィックス・プロセッサ１１０はこれらの初期値を計算する。この計算は、これからラスタ化される初期の低レベル・タイル３０２内の最初の記憶場所２０４（すなわち、開始頂点を含む低レベル・タイル）のｘおよびｙ座標を使用して行う。次いで、グラフィックス・プロセッサ１１０はエッジ評価器６０２を初期化して、初期値およびＡおよびＢの適切な値を含むようにする。
【００５０】
初期化が完了した後、エッジ評価器６０２は、それらの関連するエッジ関数の値（すなわち、これからラスタ化される初期の低レベル・タイル３０２内の最初の記憶場所２０４について計算された初期値）を出力する。各エッジ評価器６０２のこれらの出力は、それぞれの加算器ツリー６０６へ渡される。各加算器ツリー６０６は、一連の加算を実行して１６個の出力値のセットを作成する。この出力値は、図５の値と同値である。このようにして、各加算器ツリー６０６は、その連結されたエッジ評価器から受け取った値を、ラスタ化中の低レベル・メモリ・タイル３０２内の各ｘおよびｙの位置について再計算する。
【００５１】
ａｎｄゲート６０８は、３つの加算器ツリー６０６によって出された１６個の値の３つのセットを結合する。この結果は、１６個の値の単一セットとなる。単一セットの出力値は、ラスタ化中の低レベル・タイル３０２内のどの記憶場所２０４がプリミティブに含まれるかを示す。１６個の出力値のセットは、フラグメント選択ユニット６１０に渡される。
【００５２】
ラスタ化・プロセスを継続するため、グラフィックス・プロセッサ１１０は、エッジ評価器６０２に対し、それらの出力関数を再評価してラスタ化・プロセスの動きを追加の低レベル・タイル３０２に反映させるように、繰り返し指示する。追加の各低レベル・タイル３０２について、加算器ツリー６０６は、再評価した関数を、ラスタ化中の低レベル・タイル３０２内の記憶場所２０４のそれぞれに適用する。ａｎｄゲート６０８は、加算器ツリー６０６によって出された値を結合し、ラスタ化中のプリミティブに含まれる記憶場所２０４を示す値の統一セットを作成する。
【００５３】
エッジ評価器６０２の詳細は、図７を参照することによってよりよく理解される。図７では、エッジ評価器６０２がＡレジスタ７００およびＢレジスタ７０２を含むことが分かる。これらのレジスタを使用して、それぞれＡおよびＢの値を格納する。エッジ評価器６０２は、Ｘ保存レジスタ７０４およびＹ保存レジスタ７０６も含む。以下により詳細に記載するように、これらのレジスタを使用して、ラスタ化・プロセス中の特定の時間におけるエッジ評価器６０２のチェックポイント出力値を格納する。Ｘ保存レジスタ７０４およびＹ保存レジスタ７０６は、レジスタ・セットである。各セットは、使用中のタイル階層の各レベルにつき１つのレジスタを含む。記載する実施形態では、つまり、Ｘ保存レジスタ７０４とＹ保存レジスタ７０６に共に３つのレジスタがあるということである。エッジ評価器６０２は、カレント・レジスタ７０８も含む。カレント・レジスタ７０８を使用して、エッジ評価器６０２に関連するエッジ関数の現行値（すなわち、Ｆ（ｘ，ｙ）＝Ａｘ＋Ｂｙ＋Ｃの現行値）を格納する。
【００５４】
Ａレジスタ７００およびＢレジスタ７０２の出力は、ステップ命令マルチプレクサ７１０のデータ入力に接続される。ステップ命令マルチプレクサ７１０の制御入力は、入力および制御バス６０４に接続される。これによって、グラフィックス・プロセッサ１１０が、ステップ命令マルチプレクサ７１０の出力を、Ａレジスタ７００またはＢレジスタ７０２のいずれかの出力として選択することができる。ステップ命令マルチプレクサ７１０の出力は、加算器７１２の第１の入力に接続される。
【００５５】
Ｘ保存レジスタ７０４、Ｙ保存レジスタ７０６およびカレント・レジスタ７０８の出力は、カレント／リストア・マルチプレクサ７１４のデータ入力に接続される。カレント／リストア・マルチプレクサ７１４の制御入力は、入力および制御バス６０４に接続される。これによって、グラフィックス・プロセッサ１１０が、カレント／リストア・マルチプレクサ７１４の出力を、Ｘ保存レジスタ７０４、Ｙ保存レジスタ７０６またはカレント・レジスタ７０８のいずれかの出力として選択することができる。カレント／リストア・マルチプレクサ７１４の出力は、加算器７１２の第２の入力に接続される。
【００５６】
加算器７１２の出力は、初期化マルチプレクサ７１６の第１のデータ入力に接続される。初期化マルチプレクサの第２のデータ入力およびデータ初期化マルチプレクサ７１６の制御入力は、入力および制御バス６０４に接続される。これによって、グラフィックス・プロセッサ１１０が、初期化マルチプレクサ７１６の出力を、加算器７１２の出力またはグラフィックス・プロセッサ１１０によって指定された値のいずれかとして選択することができる。
【００５７】
加算器７１２の出力も、Ｘ保存レジスタ７０４およびＹ保存レジスタ７０６の入力に接続される。Ｘ保存レジスタ７０４およびＹ保存レジスタ７０６の書き込み可能入力は、入力および制御バス６０４に接続される。これによって、グラフィックス・プロセッサ１１０は、加算器７１２の出力を、Ｘ保存レジスタ７０４またはＹ保存レジスタ７０６のいずれかに選択的に保存することができる。
【００５８】
Ａレジスタ７００およびＢレジスタ７０２の入力は、入力および制御バス６０４に接続される。これによって、グラフィックス・プロセッサ１１０がＡレジスタ７００およびＢレジスタ７０２を初期化して、それぞれＡおよびＢの値を含めることができる。
【００５９】
エッジ評価器６０２を初期化するため、グラフィックス・プロセッサ１１０は、エッジ関数Ｆ（ｘ，ｙ）＝Ａｘ＋Ｂｙ＋Ｃの初期値を計算する。上述のように、グラフィックス・プロセッサ１１０は、ラスタ化される初期の低レベル・タイル３０２内の最初の記憶場所２０４のｘおよびｙ座標（すなわち、開始頂点を含む低レベル・タイル）を使用して、この初期値を計算する。次いで、グラフィックス・プロセッサ１１０は入力および制御バス６０４を使用して、この初期値をカレント・レジスタ７０８に格納する。また、グラフィックス・プロセッサ１１０は、入力および制御バス６０４を使用して、値ＡおよびＢをそれぞれＡレジスタ７００およびＢレジスタ７０２に格納する。初期化が完了すると、エッジ評価器６０２の出力が、グラフィックス・プロセッサ１１０によって計算されたエッジ関数の初期値となる。
【００６０】
ラスタ化・プロセスを継続するため、グラフィックス・プロセッサ１１０は、入力および制御バス６０４を使用して、ステップ命令マルチプレクサ７１０にＡレジスタ７００またはＢレジスタ７０２を選択させる。Ａレジスタ７００が選択され、エッジ評価器６０２に、ＡまたはＢを加算することによってカレント・レジスタ７０８の初期値を再評価させる。再評価された値は、カレント・レジスタ７０８に格納され、エッジ評価器６０２の現行出力となる。実際上は、Ａレジスタ７００またはＢレジスタ７０２を選択し、初期値を再評価することによって、グラフィックス・プロセッサ１１０は、エッジ評価器６０２に、ラスタ化・プロセスを低レベル・タイル３０２から１つ移動させる。この移動は、左から右へ（Ａレジスタ７００を選択したとき）、または上から下へ（Ｂレジスタ７０２を選択したとき）となる可能性がある。
【００６１】
結論 タイル階層を使用することによって、所与のメモリ・タイル２０４内のラスタ化が、別のメモリ・タイル２０４内のラスタ化が開始される前に、完了することが確実になる。これによって、ラスタ化・プロセス中のメモリ・タイル２０４内のアクセスの時間的局所化が増加する。高速のタイル・ベース・アクセスをサポートするフレーム・バッファでは、これによってグラフィックス・スループットが向上する。所与のメモリ・タイル２０４内のアクセスの時間的局所化が増加することによって、キャッシュ・メモリの性能も向上させることができる。これは特に、キャッシュ・メモリ／フレーム・バッファのインタラクションがタイル毎に実行される場合に真である。このようにして、本発明は、フレーム・バッファ内でメモリ・タイリングの使用を十分に活用する、グラフィックス・プリミティブをラスタ化する効率的な方法を提供する。
【００６２】
他の実施形態は、ここに開示した本発明の明細書および実施を考慮することによって、当業者には明らかになるであろう。明細書および例は例示的のみであるとみなされ、本発明の真の範囲は、以下の特許請求の範囲および均等物によって示されることを意図するものである。
【図面の簡単な説明】
【図１】  本発明の一実施形態の例示的環境としてのホスト・コンピュータ・システムのブロック図である。
【図２】  本発明の一実施形態によるフレーム・バッファのブロック図である。
【図３】  本発明の一実施形態によるメモリ・タイルのブロック図である。
【図４】  本発明の一実施形態をさらに記述するための、フレーム・バッファの上に載る例示的グラフィックス・プリミティブのブロック図である。
【図５】  低レベル・タイルの各記憶場所について計算されたエッジ関数の値を示すブロック図である。
【図６】  本発明の一実施形態によるラスタ化装置のブロック図である。
【図７】  本発明の一実施形態によるエッジ評価器のブロック図である。
【図１】
0004477237.tif 000002
【図２】
0004477237.tif 000003
【図３】
0004477237.tif 000004
【図４】
0004477237.tif 000005
【図５】
0004477237.tif 000006
【図６】
0004477237.tif 000007
【図７】
0004477237.tif 000008