(57)【要約】【課題】入力される三角形の一部が視点より後方に存在するか否かを問わずに、統一的な処理でラスタライズ処理を行うこと。【解決手段】三次元グラフィクス画像を描画する際に、三角形の頂点に関する頂点データからピクセルデータを生成するラスタライズ処理を行う描画処理装置であって、頂点データからピクセルが三角形の内部領域に存在するか否かを判定するためのエッジ関数のエッジ係数を算出するエッジ係数算出部２０１と、算出されたエッジ係数に基づいて、投影面における前記三角形の投影像のバウンディングボックスを求めるバウンディング領域計算部２０２と、三角形の投影像を、各辺の前記エッジ係数の組み合わせに基づいて分類し、分類に基づいて前記バウンディング領域の端点から走査開始点を決定する開始点決定部２０３とを有するセットアップ処理部１００と、決定された走査開始点から、バウンディングボックスを走査してピクセルデータを生成するトラバース処理部３００とを備えた。【選択図】        図１
2005182547.tif 000002
【特許請求の範囲】
【請求項１】
三次元グラフィクス画像を描画する際に、三角形の頂点に関する頂点データからピクセルデータを生成するラスタライズ処理を行う描画処理装置であって、
前記頂点データからピクセルが三角形の内部領域に存在するか否かを判定するためのエッジ関数のエッジ係数を算出するエッジ係数算出手段と、
前記エッジ係数算出手段によって算出されたエッジ係数に基づいて、投影面における前記三角形の投影像のバウンディング領域を求めるバウンディング領域計算手段と、
前記三角形の投影像を、各辺の前記エッジ係数の組み合わせに基づいて分類し、分類に基づいて前記バウンディング領域の端点から走査開始点を決定する開始点決定手段と、
前記開始点決定手段によって決定された走査開始点から、前記バウンディング領域を走査してピクセルデータを生成するトラバース手段と、
を備えたことを特徴とする描画処理装置。
【請求項２】
前記バウンディングボックス計算手段は、各頂点から左右方向の辺の前記エッジ係数と、前記頂点の同次座標とから投影面における三角形の投影像のバウンディング領域を求めることを特徴とする請求項１に記載の描画処理装置。
【請求項３】
前記開始点決定手段は、前記三角形の投影像を、各辺ごとの前記投影面におけるＸ軸方向の前記エッジ係数の符号とＹ軸方向のエッジ係数の符号の組み合わせに基づいて分類し、分類に基づいて前記バウンディング領域の端点から走査開始点を決定することを特徴とする請求項１に記載の描画処理装置。
【請求項４】
前記開始点決定手段は、前記三角形の投影像を、各辺ごとの前記投影面におけるＸ軸方向の前記エッジ係数の符号とＹ軸方向のエッジ係数の符号の組み合わせと前記エッジ係数の分類を示すビット値を予め定めた分類ビットテーブルとに基づいて分類し、前記分類ビットテーブルに基づいて前記バウンディング領域の端点から走査開始点を決定することを特徴とする請求項３に記載の描画処理装置。
【請求項５】
前記開始点決定手段は、前記三角形の投影像を、各辺ごとの前記投影面におけるＸ軸方向の前記エッジ係数の符号とＹ軸方向のエッジ係数の符号の組み合わせと前記エッジ係数の分類を示すビット値を予め定めた分類ビットテーブルと前記ビット値の合計とに基づいて分類し、前記分類ビットテーブルと前記合計値とに基づいて前記バウンディング領域の端点から走査開始点を決定することを特徴とする請求項４に記載の描画処理装置。
【請求項６】
前記開始点決定手段は、さらに前記バウンディング領域において前記三角形の内部領域の端点から走査開始点を決定することを特徴とする請求項１に記載の描画処理装置。
【請求項７】
前記三角形の各辺の内外判定を行うための先行点を、前記バウンディング領域における走査方向と前記エッジ係数との関係に基づいて決定する先行点決定手段をさらに備え、
前記トラバース手段は、前記開始点決定手段によって決定された走査開始点から、前記先行点決定手段によって決定された先行点に基づいてピクセルが三角形の内部領域に存在するか否かを判定しながら、前記バウンディング領域を走査してピクセルデータを生成することを特徴とする請求項１に記載の描画処理装置。
【請求項８】
前記トラバース手段は、前記開始点決定手段によって決定された走査開始点を含むスタンプまたはエリアから、隣接するスタンプまたはエリアを順次移動してピクセルを走査してピクセルデータを生成することを特徴とする請求項１に記載の描画処理装置。
【請求項９】
前記トラバース手段は、前記投影面を列方向に区切ったタイルの内部に含まれるエリアを順次辿ってピクセルを走査し、前記エリアの内部に含まれるスタンプを順次辿ってピクセルを走査してピクセルデータを生成することを特徴とする請求項１に記載の描画処理装置。
【請求項１０】
三次元グラフィクス画像を描画する際に、三角形の頂点に関する頂点データからピクセルデータを生成するラスタライズ処理を行う描画処理方法であって、
前記頂点データからピクセルが三角形の内部領域に存在するか否かを判定するためのエッジ関数のエッジ係数を算出するエッジ係数算出ステップと、
前記エッジ係数算出手段によって算出されたエッジ係数に基づいて、投影面における前記三角形の投影像のバウンディング領域を求めるバウンディング領域計算ステップと、
前記三角形の投影像を、各辺の前記エッジ係数の組み合わせに基づいて分類し、分類に基づいて前記バウンディング領域の端点から走査開始点を決定する開始点決定ステップと、
前記開始点決定手段によって決定された走査開始点から、前記バウンディング領域を走査してピクセルデータを生成するトラバースステップと、
を含むことを特徴とする描画処理方法。
【請求項１１】
三次元グラフィクス画像を描画する際に、三角形の頂点に関する頂点データからピクセルデータを生成するラスタライズ処理を行う描画処理プログラムであって、
前記頂点データからピクセルが三角形の内部領域に存在するか否かを判定するためのエッジ関数のエッジ係数を算出するエッジ係数算出手順と、
前記エッジ係数算出手段によって算出されたエッジ係数に基づいて、投影面における前記三角形の投影像のバウンディング領域を求めるバウンディング領域計算手順と、
前記三角形の投影像を、各辺の前記エッジ係数の組み合わせに基づいて分類し、分類に基づいて前記バウンディング領域の端点から走査開始点を決定する開始点決定手順と、
前記開始点決定手段によって決定された走査開始点から、前記バウンディング領域を走査してピクセルデータを生成するトラバース手順と、
をコンピュータに実行させる描画処理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、三次元グラフィクス画像の描画処理を行う描画処理装置、描画処理方法および描画処理プログラムであって、特に、三角形の画像のラスタライズ処理に関するものである。
【背景技術】
【０００２】
従来から、一般的なコンピュータグラフィクスの描画処理装置としては、次のような構成となっている。図２９は、従来の一般的なリアルタイムＣＧ描画装置の構成を示すブロック図である。従来の描画処理装置は、三角形の頂点データを入力するための頂点入力処理部２９０１と、頂点入力処理部２９０１から入力された頂点データに対する演算を行うための頂点演算処理部２９０２と、頂点演算処理部２９０２によって加工された頂点データからピクセルデータを生成するためのラスタライズ処理部２９０３と、ラスタライズ処理部２９０３によって生成されたピクセルデータに対する演算を行うためのピクセル処理部２９０７と、頂点演算処理部２９０２から入力される頂点データをバッファリングするための頂点データバッファ２９０６と、ピクセル処理部２９０７によって加工されたピクセルデータを記憶するための描画メモリ２９０８から主に構成されている。
【０００３】
ラスタライズ処理部２９０３は、頂点データバッファ２９０６から三角形の３頂点のデータを取得してラスタライズに必要なセットアップデータを生成するためのセットアップ処理部２９０４と、セットアップ処理部２９０５から受け渡されたセットアップデータを用いてピクセルデータを生成するトラバース処理部２９０５を備えた構成となっている。
【０００４】
ラスタライズ処理部２９０３に入力される頂点データは、同次座標やウィンドウ座標などの頂点座標と、カラー、フォグ（ｆｏｇ）、テクスチャ座標、法線ベクトルなどの頂点パラメータから構成される。ラスタライズ処理部２９０３はこの頂点データを用いて、三角形の内側に入るピクセルを見つける処理とピクセルのパラメータを求める処理を行い、ピクセルデータを生成する。ピクセルデータは、ウィンドウ座標、奥行き値（ｄｅｐｔｈ）、カラー、フォグ、テクスチャ座標、法線ベクトル、三角形の内側に入るかどうかを表すフラグなどから構成される。
【０００５】
一般に、ラスタライズ処理部２９０３は三角形の形状を数１式のような３辺の線形方程式の組で表す。
【０００６】
数１
Ａ０（Ｘ，Ｙ）＝ａ０＊（Ｘ−Ｘ０）＋ｂ０＊（Ｙ−Ｙ０）
Ａ１（Ｘ，Ｙ）＝ａ１＊（Ｘ−Ｘ１）＋ｂ１＊（Ｙ−Ｙ１）
Ａ２（Ｘ，Ｙ）＝ａ２＊（Ｘ−Ｘ２）＋ｂ２＊（Ｙ−Ｙ２）
【０００７】
ここでＸ，Ｙはピクセルのウィンドウ座標、（Ｘ０，Ｙ０），（Ｘ１，Ｙ１），（Ｘ２，Ｙ２）は三角形の頂点のウィンドウ座標、ａ０，ａ１，ａ２，ｂ０，ｂ１，ｂ２は定数である。これらの線形方程式はエッジ関数と呼ばれ、ディスプレイ上のピクセルを、三角形の内側、辺上、外側の３つの領域に分類するために使用される。
【０００８】
すなわち、エッジ関数の値が０より大きいピクセルは三角形の内側領域、ちょうど０のピクセルは辺上、０より小さいピクセルは外側領域にあることを意味する。ラスタライズ処理部２９０３は、トラバース処理部２９０５によって３辺のエッジ関数の値がすべて０より大きいかどうかを調べることにより、ピクセルが三角形の内側に入るかどうかを判定する。なお、エッジ関数の傾きａ０，ｂ０，ａ１，ｂ１，ａ２，ｂ２は数２式により計算する。
【０００９】
数２
ａ０＝Ｙ０−Ｙ１
ｂ０＝Ｘ１−Ｘ０
ａ１＝Ｙ１−Ｙ２
ｂ１＝Ｘ２−Ｘ１
ａ２＝Ｙ２−Ｙ０
ｂ２＝Ｘ０−Ｙ２
【００１０】
このような計算手順をハードウェアで実装する方法にはＤＤＡ（Ｄｉｇｉｔａｌ  Ｄｉｆｆｅｒｅｎｔｉａｌ  Ａｎａｌｙｓｅｒ）とＤＥ（Ｄｉｒｅｃｔ  Ｅｖａｌｕａｔｉｏｎ）の２種類がある。
【００１１】
ＤＤＡの場合には、代表ピクセルにおけるエッジ関数の初期値のみを数１式により計算し、その初期値にエッジ関数の傾きを次々と足し合わせていくことにより、隣接するピクセルのエッジ関数の値を求める。
【００１２】
ＤＤＡによれば、初期値の計算以外は加算のみで済むので回路面積を小さくすることができるが、加算の積み重ねによる誤差を考慮する必要がある。この場合、ラスタライズ処理部２９０３はセットアップ処理部２９０４によって初期値と傾きの計算を行い、トラバース処理部２９０５によって傾きの加算を行う。
【００１３】
ＤＥの場合には、すべてのピクセルのエッジ関数の値を数１式により計算する。このため、ＤＥの場合には、ＤＤＡの場合のように誤差を考慮する必要はないが、乗算を多用するため回路面積は大きくなる。この場合、ラスタライズ処理部２９０３はセットアップ処理部２９０５によって傾きの計算を行い、トラバース部３３にて数１式の乗算を行う。
【００１４】
次に、ラスタライズ処理部２９０３は、三角形の内側領域に入ると判定されたピクセルの奥行き値、カラー、フォグ、テクスチャ座標、法線ベクトルなどのパラメータを求める。これらのパラメータは三角形の３頂点のパラメータを補間することによって計算される。補間計算の方法にはＤＤＡと重心座標βを使う方法の２種類がある。
【００１５】
ＤＤＡの場合は、まず代表ピクセル（Ｘ，Ｙ）におけるパラメータの初期値を数３式により計算する。
【００１６】
数３
Ｐ（Ｘ，Ｙ）＝ａ＊Ｘ＋ｂ＊Ｙ＋ｃ
【００１７】
そして、その初期値に傾きａ，ｂを次々と足し合わせていくことにより、隣接するピクセルのパラメータを求める。なお、数３式の係数ａ，ｂ，ｃを求めるには数４式を解く。
【００１８】
数４
ａ＊Ｘ０＋ｂ＊Ｙ０＋ｃ＝ｐ０
ａ＊Ｘ１＋ｂ＊Ｙ１＋ｃ＝ｐ１
ａ＊Ｘ２＋ｂ＊Ｙ２＋ｃ＝ｐ２
【００１９】
ここで、（Ｘ０，Ｙ０），（Ｘ１，Ｙ１），（Ｘ２，Ｙ２）は三角形の３頂点のウィンドウ座標、ｐ０，ｐ１，ｐ２は対応する頂点のパラメータである。エッジ関数の場合と同様に、初期値の計算以外は加算のみで済むので演算回路を小さくすることができるが、加算の積み重ねによる誤差を考慮する必要がある。また、パラメータの数だけ数４式により係数ａ，ｂ，ｃを求める必要があるため、パラメータ数が多い場合に計算量が大きくなるという欠点がある。この場合、ラスタライズ処理部２９０３は、セットアップ処理部２９０５によって初期値と傾きの計算を行い、トラバース処理部２９０５によって傾きの加算を行う。
【００２０】
これに対して重心座標βを使う方法では、数５式を用いてすべてのパラメータを補間することができる。
【００２１】
数５
Ｐ（Ｘ，Ｙ）＝s０＊ｐ０＋s１＊ｐ１＋s２＊ｐ２
【００２２】
パラメータが変わっても重心座標β０，β１，β２を使いまわして補間できるため、パラメータ数が多い場合に有効である。なお、重心座標β０，β１，β２は数６式により計算する。
【００２３】
数６
β０（Ｘ，Ｙ）＝（１／ｓｕｍ（Ｘ，Ｙ））＊Ａ０（Ｘ，Ｙ）
β１（Ｘ，Ｙ）＝（１／ｓｕｍ（Ｘ，Ｙ））＊Ａ１（Ｘ，Ｙ）
β２（Ｘ，Ｙ）＝（１／ｓｕｍ（Ｘ，Ｙ））＊Ａ２（Ｘ，Ｙ）
１／ｓｕｍ（Ｘ，Ｙ）＝１／（Ａ０（Ｘ，Ｙ）＋Ａ１（Ｘ，Ｙ）＋Ａ２（Ｘ，Ｙ））
【００２４】
この場合、ラスタライズ処理部２９０３では、トラバース処理部２９０５によって数６式の計算を行い、各ピクセルの重心座標を計算する。数５式の計算はトラバース処理部２９０５あるいはラスタライズ処理部２９０３の後段に接続されたピクセル処理部２９０７によって行う。
【００２５】
以上の方法により、ラスタライズ処理部２９０３は、ピクセルが三角形の内側領域に入るか否かを判定する処理と、頂点パラメータを補間してピクセルのパラメータを求める処理を行っている。
【００２６】
【特許文献１】米国特許第６５０４５４２号明細書
【特許文献２】米国特許第６４６２７３７号明細書
【特許文献３】米国特許第６１９８４８８号明細書
【発明の開示】
【発明が解決しようとする課題】
【００２７】
このように従来の技術では、ピクセルが三角形の内側領域に入るかどうかを判定する処理と、頂点パラメータを補間してピクセルのパラメータを計算する処理を行っているが、これらの処理は描画プリミティブの頂点のウィンドウ座標を用いて行うようになっている。このため、頂点演算処理部２９０２によって頂点をウィンドウ上に投影し、ウィンドウ上に投影したときのウィンドウ座標をラスタライズ処理部２９０３へ受け渡すようになっている。
【００２８】
しかしながら、ラスタライズ処理部２９０３に入力される三角形の頂点データの中に視点座標のＷ成分が０より小さいものが含まれる場合、つまり三角形の一部が視点より後方にある場合がある。このように、三角形が視点後方の頂点を含む場合、その頂点はウィンドウ上に投影されないためウィンドウ座標を有しないこととなる。そこで、このような三角形に対してラスタライズ処理を行う際には、あらかじめ図３２のように三角形を近クリップ面で切断し、ビューポート上に投影される部分３２０１と投影されない部分３２０２に分割する。そして、ラスタライズ処理部２９０３にはウィンドウ上に投影される部分３２０１のウィンドウ座標を入力する。このように描画プリミティブをクリップ面で分割する処理をクリッピング処理という。クリッピング処理は、複雑かつ処理量が多いため、専用ハードウェアを用いて行うのが一般的であるが、特許文献１ではクリッピング処理を不要にできるラスタライズ処理の技術が開示されている。
【００２９】
しかしながら、このような従来技術のラスタライズ処理を採用するためには、走査の開始点を効率よく探索する処理が新たに必要となる。このため、三角形の一部が視点より後方にある場合には、三角形のすべての領域が投影面に投影されている場合の処理の他に、走査の開始点を探索するなどの特別な処理が必要となり、処理の効率が悪化する。
【００３０】
本発明は、上記に鑑みてなされたものであって、入力される三角形の一部が視点より後方に存在するか否かを問わずに、統一的な処理でラスタライズ処理を行うことができる描画処理装置、描画処理方法および描画処理プログラムを提供することを目的とする。
【課題を解決するための手段】
【００３１】
上述した課題を解決し、目的を達成するために、本発明は、三次元グラフィクス画像を描画する際に、三角形の頂点に関する頂点データからピクセルデータを生成するラスタライズ処理を行う描画処理装置であって、前記頂点データからピクセルが三角形の内部領域に存在するか否かを判定するためのエッジ関数のエッジ係数を算出するエッジ係数算出手段と、前記エッジ係数算出手段によって算出されたエッジ係数に基づいて、投影面における前記三角形の投影像のバウンディング領域を求めるバウンディング領域計算手段と、前記三角形の投影像を、各辺の前記エッジ係数の組み合わせに基づいて分類し、分類に基づいて前記バウンディング領域の端点から走査開始点を決定する開始点決定手段と、前記開始点決定手段によって決定された走査開始点から、前記バウンディング領域を走査してピクセルデータを生成するトラバース手段とを備えたことを特徴とする。
【００３２】
また、本発明は、三次元グラフィクス画像を描画する際に、三角形の頂点に関する頂点データからピクセルデータを生成するラスタライズ処理を行う描画処理方法であって、前記頂点データからピクセルが三角形の内部領域に存在するか否かを判定するためのエッジ関数のエッジ係数を算出するエッジ係数算出ステップと、前記エッジ係数算出手段によって算出されたエッジ係数に基づいて、投影面における前記三角形の投影像のバウンディング領域を求めるバウンディング領域計算ステップと、前記三角形の投影像を、各辺の前記エッジ係数の組み合わせに基づいて分類し、分類に基づいて前記バウンディング領域の端点から走査開始点を決定する開始点決定ステップと、前記開始点決定手段によって決定された走査開始点から、前記バウンディング領域を走査してピクセルデータを生成するトラバースステップとを含むことを特徴とする。
【００３３】
また、本発明は、三次元グラフィクス画像を描画する際に、三角形の頂点に関する頂点データからピクセルデータを生成するラスタライズ処理を行う描画処理プログラムであって、前記頂点データからピクセルが三角形の内部領域に存在するか否かを判定するためのエッジ関数のエッジ係数を算出するエッジ係数算出手順と、前記エッジ係数算出手段によって算出されたエッジ係数に基づいて、投影面における前記三角形の投影像のバウンディング領域を求めるバウンディング領域計算手順と、前記三角形の投影像を、各辺の前記エッジ係数の組み合わせに基づいて分類し、分類に基づいて前記バウンディング領域の端点から走査開始点を決定する開始点決定手順と、前記開始点決定手段によって決定された走査開始点から、前記バウンディング領域を走査してピクセルデータを生成するトラバース手順と、をコンピュータに実行させる描画処理プログラムである。
【発明の効果】
【００３４】
本発明は、三角形の頂点データからピクセルが三角形の内部領域に存在するか否かを判定するためのエッジ関数のエッジ係数を算出し、算出されたエッジ係数に基づいて、投影面における三角形の投影像のバウンディング領域を求め、三角形の投影像を、各辺の前記エッジ係数の組み合わせに基づいて分類し、分類に基づいてバウンディング領域における走査開始点を決定し、決定された走査開始点から、前記バウンディング領域を走査してピクセルデータを生成することで、頂点のウィンドウ座標を大小比較する代わりに、エッジ関数のエッジ係数）の組み合わせによって三角形の投影像を分類し、分類に応じてバウンディング領域の端点から走査開始点を決定しているので、入力される三角形の一部が視点より後方にある場合でも特別な処理を必要とせずに、三角形の全てが投影面に投影されている場合と同様に、統一的な処理でセットアップデータを生成することができるという効果を奏する。
【発明を実施するための最良の形態】
【００３５】
以下に添付図面を参照して、この発明にかかる描画処理装置、描画処理方法および描画処理プログラムの最良な実施の形態を詳細に説明する。
【００３６】
（描画処理装置の全体構成）
図１は、本実施の形態における描画処理装置の構成図である。この描画処理装置は、図１に示すように、頂点入力処理部１０１と、頂点演算処理部１０２と、ラスタライズ処理部１００と、複数のピクセル処理部１０３と、描画メモリ１２０と、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）に確保された頂点データバッファ１１１および複数のピクセルデータバッファ１１２を備えた構成となっている。図２９に示す従来の描画処理装置と構成上異なる点は、ラスタライズ処理部１００に補間処理部１０４をさらに備え、ＲＡＭにピクセルデータバッファ１１２をさらに備えた点である。
【００３７】
頂点入力処理部１０１は、描画する三角形の頂点データを入力するものである。ここで、頂点データは、同次座標やウィンドウ座標などの頂点座標と、カラー、フォグ（ｆｏｇ）、テクスチャ座標、法線ベクトルなどの頂点パラメータから構成される。
【００３８】
頂点演算処理部１０２は、頂点入力処理部１０１から入力された頂点データに対する演算を行うものである。
【００３９】
ラスタライズ処理部１００は、頂点演算処理部１０２によって加工された頂点データからピクセルデータを生成するものである。
【００４０】
ピクセル処理部１０３は、ラスタライズ処理部１００によって生成されたピクセルデータに対する演算を行うものである。本実施の形態では、ピクセル処理の並列処理を行うため、複数のピクセル処理部１０３を設けている。このため、ディスプレイをエリア（area）と呼ぶ矩形領域に分割し、分割されたエリア単位に異なるピクセル処理部１０３を割り当てている。
【００４１】
ここで、ピクセルデータは、ウィンドウ座標、奥行き値（ｄｅｐｔｈ）、カラー、フォグ、テクスチャ座標、法線ベクトル、三角形の内側領域に存在するか否かを示すフラグなどから構成される。
【００４２】
ラスタライズ処理部１００は、図１に示すように、セットアップ処理部２００と、トラバース処理部３００と、複数の補間処理部１０４とから構成されている。
【００４３】
セットアップ処理部２００は、頂点データバッファ１１１から三角形の３頂点のデータを取得してラスタライズに必要なセットアップデータを生成するものである。
【００４４】
トラバース処理部３００は、セットアップ処理部２００から受け渡されたセットアップデータを用いてピクセルデータを生成するものである。
【００４５】
補間処理部１０４は、頂点データバッファ１１１に保存されている三角形の３頂点のパラメータを補間して、ピクセルデータバッファ１１２に保存されているピクセルのパラメータを計算するものである。
【００４６】
ラスタライズ処理部１００の処理を効率良く実行するためには、処理対象のピクセルをできるだけ効率的に走査する必要がある。このような処理対象のピクセルを効率良く走査するために、本実施の形態では、スタンプ（stamp）と呼ぶ矩形領域単位で走査を行っている。スタンプは、ラスタライズ処理部１００が１サイクルに並列処理するピクセルの集合である。
【００４７】
例えばスタンプの大きさが２×４ピクセルの場合は、ラスタライズ処理部１００は１サイクルの間に８個のピクセルを処理することになる。ラスタライズ処理部１００のトラバース処理部３００は、スタンプを１サイクルごとに移動させてディスプレイ上を走査し、ピクセルデータを生成する。この際、スタンプ周辺の点が三角形の内側領域に入るか否かを判定し、その判定結果に基づいて移動方向を決定することにより、三角形の内側に入るピクセルを無駄なく走査している。スタンプ周辺の点は、移動方向に対して位置的に先行する点であることから先行点（sense point）と呼ぶ。
【００４８】
頂点データバッファ１１１は、頂点演算処理部１０２から入力される頂点データを保存し、ピクセルデータバッファは、トラバース処理部３００にて生成されるピクセルデータを保存するものである。
【００４９】
描画メモリ１２０は、ピクセル処理部１０３によって加工されたピクセルデータを記憶するものである。この描画メモリ１２０は、本実施の形態のように描画専用のメモリを用いる他、ＲＡＭを用いてもよい。
【００５０】
（セットアップ処理部２００の構成）
図２は、セットアップ処理部２００の機能的構成を示すブロック図である。セットアップ処理部２００は、図２に示すように、エッジ係数算出部２０１とバウンディングボックス計算部２０２と開始点決定部２０３と先行点決定部２０４とエッジ関数初期値算出部２０５とから構成される。
【００５１】
エッジ係数算出部２０１は、エッジ関数の係数（傾き）を計算するものである。バウンディングボックス計算部２０２は、三角形の投影像のバウンディングボックスを計算するものである。開始点決定部２０３と先行点決定部２０４は、バウンディングボックス計算部２０２にて計算されたバウンディングボックスの四隅から走査開始点を決定するものである。エッジ関数初期値算出部２０５は、代表ピクセルにおけるエッジ関数の値をDDAの初期値として計算するものである。
【００５２】
（トラバース処理部３００の構成）
図３は、トラバース処理部３００の機能的構成を示すブロック図である。トラバース処理部３００は、図３に示すように、走査部３０１とエッジ関数計算部３０２と重心座標計算部３０３とから構成される。
【００５３】
走査部３０１は、開始点決定部２０３によって決定された走査開始点を含むスタンプあるいはエリアから、隣接するスタンプあるいはエリアを辿ってピクセルを走査するものである。エッジ関数計算部３０２は、スタンプ内に含まれるピクセルのエッジ関数の値を計算するものである。重心座標計算部３０３は、スタンプ内に含まれるピクセルの重心座標を計算するものである。
【００５４】
本実施の形態の描画処理装置は、ＣＰＵなどの制御装置と、ＲＯＭ（Read Only Memory）やＲＡＭ（Ramdom Access Memory）などの記憶装置と、ハードディスクおよびハードディスクドライブ装置（ＨＤＤ）、ＣＤドライブ装置などの外部記憶装置と、ディスプレイ装置などの表示装置と、キーボードやマウスなどの入力装置を備えており（いずれも不図示）、ゲーム専用のゲーム装置やコンピュータを利用したハードウェア構成となっている。
【００５５】
本実施形態の描画処理装置で実行される描画処理プログラムは、インストール可能な形式又は実行可能な形式のファイルでＣＤ−ＲＯＭ、フレキシブルディスク（ＦＤ）、ＣＤ−Ｒ、ＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｋ）等のコンピュータで読み取り可能な記録媒体に記録されて提供される。
【００５６】
また、本実施形態の描画処理装置で実行される描画処理プログラムを、インターネット等のネットワークに接続されたコンピュータ上に格納し、ネットワーク経由でダウンロードさせることにより提供するように構成しても良い。また、本実施形態の描画処理装置で実行される描画処理プログラムをインターネット等のネットワーク経由で提供または配布するように構成しても良い。
【００５７】
本実施形態の描画処理装置で実行される描画処理プログラムは、上記記憶媒体から読み出して実行することにより主記憶装置上にロードされ、上述した各部（ラスタライズ処理部１００、ピクセル処理部１０３など）が主記憶装置上に生成されるようになっている。
【００５８】
次に、このように構成された本実施の形態の描画処理装置による三角形の描画処理方法について説明する。
【００５９】
（セットアップ処理部２００の処理）
まず、セットアップ処理部２００の処理について説明する。図４は、セットアップ処理部２００によるセットアップデータの生成処理の手順を示すフローチャートである。
【００６０】
セットアップ処理部２００では、まずエッジ係数算出部２０１により、頂点データバッファ１１１から三角形の３頂点のデータを取得する（ステップＳ４０１）。図５は、頂点データの一例を示すデータ構造図である。図５に示す例では、頂点データは、同次座標、ウィンドウ座標、カラー、テクスチャ座標、フォグ、法線ベクトルから構成される。なお、頂点データは図５に示すデータ構造に限定されるものではなく、他のデータ構造を有するように構成してもよい。
【００６１】
なお、ここで、取得した３頂点の同次座標のW成分がすべて０より小さい場合は、その三角形が完全に視点より後ろ側にあることを意味している。このため、この場合には以降の処理を実行せずに次の三角形の３頂点のデータを取得するように構成してもよい。
【００６２】
次に、エッジ係数算出部２０１によって、エッジ関数の係数を計算する（ステップＳ４０２）。本実施形態のエッジ関数は、数７式のように表される。
【００６３】
数７
Ｖ０（ｘ，ｙ，ｗ）＝ａ０＊ｘ＋ｂ０＊ｙ＋ｃ０＊ｗ
Ｖ１（ｘ，ｙ，ｗ）＝ａ１＊ｘ＋ｂ１＊ｙ＋ｃ１＊ｗ
Ｖ２（ｘ，ｙ，ｗ）＝ａ２＊ｘ＋ｂ２＊ｙ＋ｃ２＊ｗ
【００６４】
ここで（ｘ，ｙ，ｗ）は三角形の頂点の同次座標である。エッジ係数ａ０，ｂ０，ｃ０，ａ１，ｂ１，ｃ１，ａ２，ｂ２，ｃ２は数８式〜数１０式を解くことにより計算する。
【００６５】
数８
ａ０＊ｘ０＊ｂ０＊ｙ０＋ｃ０＊ｗ０＝１
ａ０＊ｘ１＊ｂ０＊ｙ１＋ｃ０＊ｗ１＝０
ａ０＊ｘ２＊ｂ０＊ｙ２＋ｃ０＊ｗ２＝０
【００６６】
数９
ａ１＊ｘ０＊ｂ１＊ｙ０＋ｃ１＊ｗ０＝０
ａ１＊ｘ１＊ｂ１＊ｙ１＋ｃ１＊ｗ１＝１
ａ１＊ｘ２＊ｂ１＊ｙ２＋ｃ１＊ｗ２＝０
【００６７】
数１０
ａ２＊ｘ０＊ｂ２＊ｙ０＋ｃ２＊ｗ０＝０
ａ２＊ｘ１＊ｂ２＊ｙ１＋ｃ２＊ｗ１＝０
ａ２＊ｘ２＊ｂ２＊ｙ２＋ｃ２＊ｗ２＝１
上記数８〜１０式は、行列を用いて書き直すと数１１式のように表せる。
【００６８】
数１１
Ｍ＊Ｖ＝Ｉ
ここで、行列Ｍ，Ｖ，Ｉはそれぞれ数１２式、数１３式、数１４式に示すとおりである。
【００６９】
【数１】
2005182547.tif 000003
【００７０】
【数２】
2005182547.tif 000004
【００７１】
【数３】
2005182547.tif 000005
【００７２】
数１１式より、エッジ係数の行列Ｍは、行列Ｖの逆行列Ｖ-1そのものであることがわかる。従って、行列Ｍの各行列要素は数１５式により計算することができる。
【００７３】
数１５
ａ０＝（ｙ１＊ｗ２−ｙ２＊ｗ１）／ｄｅｔ
ｂ０＝（ｗ１＊ｘ２−ｗ２＊ｘ１）／ｄｅｔ
ｃ０＝（ｘ１＊ｙ２−ｘ２＊ｙ１）／ｄｅｔ
ａ１＝（ｙ２＊ｗ０−ｙ０＊ｗ２）／ｄｅｔ
ｂ１＝（ｗ２＊ｘ０−ｗ０＊ｘ２）／ｄｅｔ
ｃ１＝（ｘ２＊ｙ０−ｘ０＊ｙ２）／ｄｅｔ
ａ２＝（ｙ０＊ｗ１−ｙ１＊ｗ０）／ｄｅｔ
ｂ２＝（ｗ０＊ｘ１−ｗ１＊ｘ０）／ｄｅｔ
ｃ２＝（ｘ０＊ｙ１−ｘ１＊ｙ０）／ｄｅｔ
ｄｅｔ＝ｘ０＊（ｙ１＊ｗ２−ｙ２＊ｗ１）
−ｘ１＊（ｙ０＊ｗ２−ｙ２＊ｗ０）＋ｘ２＊（ｙ０＊ｗ１−ｙ１＊ｗ０）
【００７４】
ただし、同次座標では比だけが意味をもつため、数１６式のｄｅｔでの除算は省略することができる。したがって、エッジ係数ａ０，ｂ０，ｃ０，ａ１，ｂ１，ｃ１，ａ２，ｂ２，ｃ２は数１６式によって計算できる。
【００７５】
数１６
ａ０＝ｙ１＊ｗ２−ｙ２＊ｗ１
ｂ０＝ｗ１＊ｘ２−ｗ２＊ｘ１
ｃ０＝ｘ１＊ｙ２−ｘ２＊ｙ１
ａ１＝ｙ２＊ｗ０−ｙ０＊ｗ２
ｂ１＝ｗ２＊ｘ０−ｗ０＊ｘ２
ｃ１＝ｘ２＊ｙ０−ｘ０＊ｙ２
ａ２＝ｙ０＊ｗ１−ｙ１＊ｗ０
ｂ２＝ｗ０＊ｘ１−ｗ１＊ｘ０
ｃ２＝ｘ０＊ｙ１−ｘ１＊ｙ０
【００７６】
以上の計算手順をまとめると、エッジ係数算出部２０１は数１６式を計算することによってエッジ係数を求める（ステップＳ４０２）。ただし、三角形の縮退判定および表裏判定をする場合には別途計算が必要になる。
【００７７】
次いで、バウンディングボックス計算部２０２によって、バウンディングボックスを計算する（ステップＳ４０３）。バウンディングボックスとは、三角形の投影像の外接矩形とシザーボックス（ｓｃｉｓｓｏｒ  ｂｏｘ）の共通領域のことである。一般に、シザーボックスは描画処理装置へのパラメータとして入力されるので、ここでは三角形の投影像の外接矩形を求めることが主な処理となる。
【００７８】
バウンディングボックスの計算が終了すると、開始点決定部２０３によって走査の開始点を決定する（ステップＳ４０４）。そして、開始点が決定されると、先行点決定部２０４によって三角形の各辺の内外判定に使用する先行点を決定する（ステップＳ４０５）。先行点が決定されると、次に、エッジ関数初期値算出部２０５によって、代表ピクセルにおけるエッジ関数の値をＤＤＡの初期値として計算する（ステップＳ４０６）。代表ピクセル（Ｘ，Ｙ）におけるエッジ関数の値を求めるためには、数７式の両辺をそれぞれｗ０，ｗ１，ｗ２で除算することによって得られる数１７式を用いる。
【００７９】
数１７
Ｖ０（Ｘ，Ｙ）＝Ｖ０（ｘ，ｙ，ｗ）／ｗ０＝ａ０＊Ｘ＋ｂ０＊Ｙ＋ｃ０
Ｖ１（Ｘ，Ｙ）＝Ｖ１（ｘ，ｙ，ｗ）／ｗ１＝ａ１＊Ｘ＋ｂ１＊Ｙ＋ｃ１
Ｖ２（Ｘ，Ｙ）＝Ｖ２（ｘ，ｙ，ｗ）／ｗ２＝ａ２＊Ｘ＋ｂ２＊Ｙ＋ｃ２
【００８０】
セットアップ処理部２００の後段に接続されたトラバース処理部３００は、ステップＳ４０６によって計算した初期値に傾きを順次足し合わせていくことにより、代表ピクセル以外のピクセルのエッジ関数の値を求める。セットアップ処理部２００で生成されたセットアップデータは、トラバース処理部３００へ送られる（ステップＳ４０７）。図１５は、セットアップデータのデータ構造を示す説明図である。図１５に示すように、セットアップデータ、エッジ関数、バウンディングボックス、開始点、各辺の先行点、エッジ関数の初期値から構成される。
【００８１】
（バウンディングボックス計算部の処理）
次に、ステップＳ４０３におけるバウンディングボックス計算部２０２によるバウンディングボックスの計算処理について説明する。図６は、バウンディングボックスの計算処理の手順を示すフローチャートである。
【００８２】
通常、三角形の投影像の外接矩形は頂点のウィンドウ座標のＸＹ成分の最小値と最大値を求めることによって簡単に求めることができる。しかし、同次座標のＷ成分が０より小さい頂点を含む三角形の場合は、その頂点が投影面に投影されない。このため、本実施の形態では、外接矩形を以下のように求めている。
【００８３】
まず、バウンディングボックス計算部２０２は、外接矩形を初期化する。外接矩形は左上隅の点のウィンドウ座標（Ｘmin，Ｙmin）と右下隅の点のウィンドウ座標（Ｘmax，Ｙmax）で表される。ここでは、（Ｘmin，Ｙmin）＝（０，０），（Ｘmax，Ｙmax）＝（ｗｉｄｔｈ−１，ｈｅｉｇｈｔ−１）と初期化する（ステップＳ６０１）。なお、ｗｉｄｔｈ，ｈｅｉｇｈｔはビューポートである。
【００８４】
次に、三角形の３頂点の中からＷ座標成分が０より大きな頂点をひとつ選択する（ステップＳ６０２）。ステップＳ６０３〜Ｓ６０６では、選択した頂点から見て左方向に伸びる辺のＸ方向の傾きをａＬ、右方向に伸びる辺のＸ方向の傾きをａＲと表記している。ステップＳ６０７〜Ｓ６０９では、選択した頂点から見て左方向に伸びる辺のＹ方向の傾きをｂＬ、右方向に伸びる辺のＹ方向の傾きをｂＲと表記している。
【００８５】
そして、ａＬ＜０，ａＲ＞＝０，Ｙ＞Ｙｍｉｎの条件が成り立つかどうかを判定し（ステップＳ６０３）、成り立つ場合は、ＹminにＹを設定する（ステップＳ６０４）。成り立たない場合はステップＳ６０４をスキップする。
【００８６】
次に、ａＬ＞＝０，ａＲ＜０，Ｙ＜Ｙｍａｘの条件が成り立つかどうかを判定し（ステップＳ６０５）、成り立つ場合はＹmaxにＹを設定する（ステップＳ６０６）。成り立たない場合はステップＳ６０６をスキップする。
【００８７】
次に、バウンディングボックス計算部２０２は、ｂＬ＞＝０，ｂＲ＜０，Ｘ＞Ｘｍｉｎの条件が成り立つかどうかを判定し（ステップＳ６０７）、成り立つ場合はＸminにＸを設定する（ステップＳ６０８）。成り立たない場合はステップＳ７０８をスキップする。
【００８８】
次に、ｂＬ＜０，ｂＲ＞＝０，Ｘ＜Ｘｍａｘの条件が成り立つかどうかを判定し（ステップＳ６０９）、成り立つ場合はＸmaxにＸを設定する（ステップＳ６１０）。成り立たない場合はステップＳ２１０をスキップする。
【００８９】
そして、ステップＳ６０３〜Ｓ６１０の処理が三角形の３頂点すべてについて終了したかどうかを判定し（ステップＳ６１１）、終了した場合は外接矩形を求める処理を終了する。未処理の頂点が残っている場合はステップＳ６０２へ戻って頂点を選択し、ステップＳ６０３〜Ｓ６１０の処理を繰り返す。
【００９０】
上記の処理が終了したときの（Ｘmin，Ｙmin）が外接矩形の左上隅の点のウィンドウ座標、（Ｘmax，Ｙmax）が右下隅の点のウィンドウ座標を表している。例えば三角形が図９に示す（Ａ）のような場合、この処理は以下のように動作する。
【００９１】
ステップＳ６０１：（Ｘmin，Ｙmin ）＝（０，０），（Ｘmax，Ｙmax）＝（ｗｉｄｔｈ−１，ｈｅｉｇｈｔ−１）
ステップＳ６０２：頂点（Ｘ０，Ｙ０）を選択する。
ステップＳ６０７：ｂ１＞＝０，ｂ２＜０，Ｘ０＞ＸminなのでステップＳ６０８へ進む。
ステップＳ６０８：Ｘmin＝Ｘ０
ステップＳ６１１：未処理の頂点が２個残っているのでステップＳ６０２へ戻る。
ステップＳ６０２：頂点（Ｘ１，Ｙ１）を選択する。
ステップＳ６０５：ａ２＞＝０，ａ０＜０，Ｙ１＜ＹmaxなのでステップＳ６０４へ進む。
ステップＳ６０６：Ｙｍａｘ＝Ｙ１
ステップＳ６０９：ｂ２＜０，ｂ０＞＝０，Ｘ１＜ＸmaxなのでステップＳ６０４へ進む。
ステップＳ６１０：Ｘmax＝Ｘ１
ステップＳ６１１：未処理の頂点が１個残っているのでステップＳ６０２へ戻る。
ステップＳ６０２：頂点（Ｘ２，Ｙ２）を選択
ステップＳ６０３：ａ０＜０，ａ１＞＝０，Ｙ２＞ＹminなのでステップＳ６０４へ進む。
ステップＳ６０４：Ｙmin＝Ｙ２
ステップＳ６１１：未処理の頂点がなくなったので処理を終了する。
【００９２】
外接矩形の左上隅の点（Ｘ０，Ｙ２）と右下隅の点（Ｘ１，Ｙ１）が正しく計算できていることが分かる。また、この処理手順は、図７に示す（Ｂ）のように、視点座標のＷ成分が０より小さい頂点を含む三角形に対しては以下のように動作する。
【００９３】
ステップＳ６０１：（Ｘmin，Ｙmin）＝（０，０），（Ｘmax，Ｙmax）＝（ｗｉｄｔｈ−１，ｈｅｉｇｈｔ−１）
ステップＳ６０２：頂点（Ｘ０，Ｙ０）を選択
ステップＳ６１１：未処理の頂点が２個残っているのでステップＳ６０２へ戻る。
ステップＳ６０２：頂点（Ｘ１，Ｙ１）は視点座標のＷ成分が０より小さいので選択しない。
ステップＳ６１１：未処理の頂点が１個残っているのでステップＳ６０２へ戻る。
ステップＳ６０２：頂点（Ｘ２，Ｙ２）を選択する。
ステップＳ６０３：ａ０＜０，ａ１＞＝０，Ｙ２＞ＹminであるためステップＳ６０４へ進む。
ステップＳ６０４：Ｙmin＝Ｙ２
ステップＳ６１１：未処理の頂点がなくなったので処理を終了する。
【００９４】
外接矩形の左上隅の点（０，Ｙ２）と右下隅の点（ｗｉｄｔｈ−１，ｈｅｉｇｈｔ−１）が正しく計算できていることが分かる。バウンディングボックス計算部２０２は、ここで求めた外接矩形とシザーボックスの共通領域を計算することによってバウンディングボックスを求める。
【００９５】
（開始点決定部２０３の処理）
次に、図４におけるステップＳ４０４の開始点決定部２０３の開始点決定処理について説明する。
【００９６】
一般に、三角形の投影像は８種類の三角形に分類され、開始点決定部２０３は、この分類に応じて走査の開始点を決定する。図８は、８種類の三角形と、各三角形における走査の開始点位置と進行方向を示した説明図である。入力された三角形が８種類の中のどの三角形に投影されるかを判断するためには、各頂点のウィンドウ座標のＸＹ成分を大小比較すればよい。
【００９７】
しかし、同次座標のＷ成分が０より小さい頂点を含む三角形の場合は、その頂点がディスプレイ上に投影されないため、上記の８種類の三角形とは異なる形状に投影される。そこで本実施の形態の描画処理装置では、頂点のウィンドウ座標のＸＹ成分を大小比較する代わりに、エッジ関数の傾き（係数）の組み合わせによって三角形の投影像を分類している。そして、この分類に応じて、投影像のバウンディングボックスの四隅の中から開始点を選択している。
【００９８】
エッジ関数の傾き（係数）は５つのグループに分類される。第１のグループは図９−１１に示す（Ａ）〜（Ｄ）の４種類の傾きである。このグループの傾きは、Ｘ方向の傾き（ａ０あるいはａ１あるいはａ２）あるいはＹ方向の傾き（ｂ０あるいはｂ１あるいはｂ２）が０の場合、すなわちエッジ関数がＸ軸あるいはＹ軸に平行なものである。傾きはバウンディングボックスのバウンダリ（ｂｏｕｎｄａｒｙ）上に重なっている。
【００９９】
第２のグループは、図９−２に示すような傾きの場合である。このグループの傾きは、Ｘ方向の傾き（ａ０あるいはａ１あるいはａ２）とＹ方向の傾き（ｂ０あるいはｂ１あるいはｂ２）の両方が０より大きいものである。傾きはバウンディングボックスを左上領域と右下領域に分割し、左上領域は三角形の外側、右下領域は三角形の内側を表している。
【０１００】
第３のグループは、図９−３に示すような傾きである。このグループの傾きは、Ｘ方向の傾き（ａ０あるいはａ１あるいはａ２）が０より小さく、Ｙ方向の傾き（ｂ０あるいはｂ１あるいはｂ２）が０より大きいものである。傾きはバウンディングボックスを右上領域と左下領域に分割し、右上領域は三角形の外側、左下領域は三角形の内側領域を表している。
【０１０１】
第４のグループは、図９−４に示すような傾きである。このグループの傾きは、Ｘ方向の傾き（ａ０あるいはａ１あるいはａ２）が０より大きく、Ｙ方向の傾き（ｂ０あるいはｂ１あるいはｂ２）が０より小さいものである。傾きは第３のグループと同様にバウンディングボックスを右上領域と左下領域に分割する。ただし、第３のグループとは反対に、右上領域は三角形の内側領域、左下領域は三角形の外側領域を表している。
【０１０２】
第５のグループは図９−５に示すような傾きである。このグループの傾きは、Ｘ方向の傾き（ａ０あるいはａ１あるいはａ２）とＹ方向の傾き（ｂ０あるいはｂ１あるいはｂ２）の両方が０より小さいものである。傾きは２つ目のグループと同様にバウンディングボックスを左上領域と右下領域に分割する。ただし、第２のグループとは反対に、左上領域は三角形の内側領域、右下領域は三角形の外側領域を表している。
【０１０３】
本実施の形態では。このようなエッジ関数の５つのグループの傾きを分類ビットとして、０，１，２，４，８の５つのビット値に対応させて表している。このとき、分類ビットの各ビット値と、そのビット値の傾きがつくる三角形の外側領域の対応に着目すると、ビット値０の場合は領域なし、ビット値１の場合は左上領域、ビット値２の場合は右上領域、ビット値４の場合は左下領域、ビット値８の場合は右下領域という関係になっている。そこで図９−１〜９−５に示すように、この関係に合わせてビット値を配置した２×２のテーブル（分類ビットテーブル）をＲＡＭなどに設け、各ビット値における三角形の外側領域を視覚的に表すことにする。以下では、この分類ビットテーブルを用いて三角形の投影像を分類する方法について説明していく。
【０１０４】
図１０は、開始点決定部２０３による、入力された三角形の投影像を分類して開始点を決定する処理の手順を示すフローチャートである。
【０１０５】
開始点決定部２０３は、まず変数ｏｒ，ｓｕｍを０に初期化する（ステップＳ１００１）。ｏｒとｓｕｍはエッジ関数の傾きの組み合わせを表すための変数である。そして、三角形の３辺の中からひとつを選択する（ステップＳ１００２）。
【０１０６】
次に、選択した辺の少なくとも一方の頂点の同次座標のＷ成分が０より大きいかどうか、すなわち投影面に投影されているか否かを判定する（ステップＳ１００３）。そして、選択した辺の少なくとも一方の頂点の同次座標のＷ成分が０より大きい場合は（ステップＳ１００３：Ｙｅｓ）、辺が投影面に投影されていると判断し、選択した辺のエッジ関数の傾きを表すビット値ｂｉｔを求める（ステップＳ１００４）。ここで、上述したように、ｂｉｔの値は０，１，２，４，８のいずれかである。一方、ステップＳ１００３において、選択した辺の両方の頂点の同次座標のＷ成分が０以下の場合には（ステップＳ１００３：Ｎｏ）、辺が完全に視点の後ろ側にあると判断し、ステップＳ１００４〜Ｓ１００５までの処理を実行せずにステップＳ１００６へ進む。
【０１０７】
次に、変数ｏｒとｂｉｔの論理和を計算して結果をｏｒにセットする。また、変数ｓｕｍとｂｉｔの算術和を計算して結果をｓｕｍにセットする（ステップＳ１００５）。
【０１０８】
次に、三角形の３辺すべてについてステップＳ１００３〜Ｓ１００５の処理が終了したかどうかを判定し（ステップＳ１００６）、終了した場合はステップＳ１００７へ進む。未処理の辺が残っている場合はステップＳ１００２へ戻って辺を選択し、ステップＳ１００３〜Ｓ１００５の処理を繰り返す。
【０１０９】
次に、三角形の３辺すべてについてステップＳ１００３〜Ｓ１００５の処理が終了した場合には、変数ｏｒ，ｓｕｍの値に基づいて三角形の投影像を分類する。
【０１１０】
ｏｒ＝０の場合、図１１−１に示すように、各辺のエッジ関数のｂｉｔ値は０であるから、ｏｒ＝０｜０｜０＝０，ｓｕｍ＝０＋０＋０＝１となる。
【０１１１】
ｏｒ＝１の場合、図１１−２に示すように投影像はｓｕｍ＝１，２，３の３種類に分類される。ｓｕｍ＝１の投影像は右下に直角をもつ直角三角形である。直角を挟む２辺はＸ軸あるいはＹ軸に平行であるため、エッジ関数のｂｉｔ値は０、残りの１辺のｂｉｔ値は１であるから、ｏｒ＝０｜０｜１＝１，ｓｕｍ＝０＋０＋１＝１となる。ｓｕｍ＝２の場合は２辺のｂｉｔ値が１で、残りの１辺は完全に視点後ろ側にあるのでｂｉｔ値は０であるから、ｏｒ＝１｜１｜０＝１，ｓｕｍ＝１＋１＋０＝２となる。ｓｕｍ＝３の場合は３辺のｂｉｔ値が１であるから、ｏｒ＝１｜１｜１＝１，ｓｕｍ＝１＋１＋１＝３となる。三角形の辺は３本しかないので、投影像の辺は最大３本である。したがって、ｏｒ＝１の場合の投影像は、図１１−２に示したｓｕｍ＝１，２，３の３種類以外ありえない。
【０１１２】
ｏｒ＝２以降についてもｏｒ＝１の場合と同様に分類される。ｏｒ＝２の場合、図１１−３のように投影像はｓｕｍ＝２，４，６の３種類に分類される。
【０１１３】
ｏｒ＝３の場合、図１１−４に示すように投影像はｓｕｍ＝３，４，５の３種類に分類される。ｏｒ＝４の場合、図１１−５に示すように投影像はｓｕｍ＝４，８，１２の３種類に分類される。ｏｒ＝５の場合、図１１−６に示すように投影像はｓｕｍ＝５，６，９の３種類に分類される。ｏｒ＝６の場合、図１１−７のように投影像はｓｕｍ＝６，８，１０の３種類に分類される。ｏｒ＝７の場合、図１１−８に示すように投影像は１種類のみである。ｏｒ＝８の場合、図１１−９に示すように投影像はｓｕｍ＝８，１６，２４の３種類に分類される。ｏｒ＝９の場合、図１１−１０に示すように投影像はｓｕｍ＝９，１０，１７の３種類に分類される。ｏｒ＝１０の場合、図１１−１１に示すように投影像はｓｕｍ＝１０，１２，１８の３種類に分類される。ｏｒ＝１１の場合、図１１−１２に示すように投影像は１種類のみである。ｏｒ＝１２の場合、図１１−１３に示すように投影像はｓｕｍ＝１２，１６，２０の３種類に分類される。ｏｒ＝１３の場合、図１１ー１４に示すように投影像は１種類のみである。ｏｒ＝１４の場合も、図１１−１５に示すように投影像は１種類のみである。
【０１１４】
このように投影像は合計３５種類になる。変数ｏｒとｓｕｍの組み合わせパターンはこれ以外ありえないので、すべての投影像はこの３５種類の中のいずれかに分類されることになる。
【０１１５】
図１０に戻ると、投影像を上述のように分類したら、投影像の分類結果に応じてラスタライズの走査開始点を決定する。図１１−１〜図１１−１５の分類図において、バウンディングボックスの四隅の点のいずれかに○印で示されているのが開始点である。
【０１１６】
走査開始点は、バウンディングボックスの四隅の中から、三角形の外側領域に属さない点が選ばれている。例えば、図１１−４のｏｒ＝３，ｓｕｍ＝３の場合には、バウンディングボックスの四隅の内、左上の点と右上の点は三角形の外側領域に属しているため、これらの点は走査開始点として選択しない。仮に、これらの点から走査を開始すると、図１２−１、図１２−２に矢印で示したように、三角形の外側領域を走査するという無駄な走査が生じるからである。三角形の外側領域に属さない左下の点、あるいは右下の点から走査を開始すればこのような無駄な走査が生じることはない。
【０１１７】
投影像の分類と開始点位置の対応をまとめると次のようになる。
・ｏｒ＝０
開始点はバウンディングボックスの任意の四隅
・ｏｒ＝６，８，１０，１２，１４
開始点はバウンディングボックスの左上隅
・ｏｒ＝２，３，１１
開始点はバウンディングボックスの左下隅
・ｏｒ＝１，７
開始点はバウンディングボックスの右下隅
・ｏｒ＝４，５，９，１３
開始点はバウンディングボックスの右上隅
【０１１８】
なお、本実施の形態では、投影像の分類を網羅していることを示すために変数ｓｕｍを使用したが、上記対応関係から変数ｓｕｍの値は開始点の位置とは無関係である。このため、ｓｕｍを開始点決定部２０３の処理において、ｓｕｍを考慮しないように構成してもよい。例えば、開始点決定部２０３の処理をハードウェアにより実装する際には図１０における変数ｓｕｍに関する処理を省略してもよい。以上の手順により、開始点決定部２０３はバウンディングボックスの四隅から開始点を決定する。
【０１１９】
（先行点決定部２０４の処理）
次に、図４にけるステップＳ４０５の先行点決定部２０４による三角形の各辺の内外判定に使用する先行点の決定処理について説明する。
【０１２０】
先行点にはＡ，Ｂ，Ｃの３種類があり、これら３点は走査方向に関して常に相対的に同じ位置になるように配置されている。また、先行点はスタンプとエリアの２つの矩形領域ごとに位置が決められている。例えば、開始点がバウンディングボックスの左上隅の場合、すなわち走査が右下方向に進む場合には、スタンプとエリアの先行点は図１３に示す（Ａ）のように配置されている。同様に、開始点がバウンディングボックスの右上隅の場合は図１３に示す（Ｂ）、左下隅の場合は図１３に示す（Ｃ）、右下隅の場合は図１３に示す（Ｄ）のように先行点が配置されている。
【０１２１】
先行点決定部２０４は、走査方向とエッジ関数の傾き（エッジ係数）の関係から、三角形の各辺の内外判定に使用する先行点をＡ，Ｂ，Ｃの中から選択する。図１４は、先行点決定部２０４による先行点決定処理の手順を示すフローチャートである。
【０１２２】
まず、先行点決定部２０４は、三角形の３辺の中からひとつを選択する（ステップＳ１４０１）。そして、走査が右方向に進み、かつ選択した辺のＸ方向の傾きが０より大きいという条件が成立するか否かを判定する（ステップＳ１４０２）。成立しない場合には、その辺の内外判定に使用する先行点をＡ点に決定してからステップＳ１４０９へ進む（ステップＳ１４０６）。
【０１２３】
一方、ステップＳ１４０２の条件が成立する場合は、走査が左方向に進み、かつ選択した辺のＸ方向の傾きが０以下であるという条件が成立するか否かを判定する（ステップＳ１４０３）。成立しない場合は、その辺の内外判定に使用する先行点をＡ点に決定してからステップＳ１４０９へ進む（ステップＳ１４０６）。
【０１２４】
一方、ステップＳ１４０３の条件が成立しない場合には、走査が下方向に進み、かつ選択した辺のＹ方向の傾きが０より大きいという条件が成立するか否かを判定する（ステップＳ１４０４）。成立しない場合には、その辺の内外判定に使用する先行点をＢ点に決定してからステップＳ１４０９へ進む（ステップＳ１４０７）。
【０１２５】
一方、ステップＳ１４０４の条件が成立する場合には、走査が上方向に進み、かつ選択した辺のＹ方向の傾きが０以下であるという条件が成立するか否かを判定する（ステップＳ１４０５）。成立しない場合には、その辺の内外判定に使用する先行点をＢ点に決定してからステップＳ１４０９へ進む（ステップＳ１４０７）。
【０１２６】
一方、ステップＳ１４０５の条件が成立する場合には、選択した辺の内外判定に使用する先行点をＣ点に決定する（ステップＳ１４０８）。そして、ステップＳ１４０２〜Ｓ１４０８までの処理が三角形の３辺すべてについて終了したかどうかを判定し（ステップＳ１４０９）、終了した場合は三角形の各辺の内外判定に使用する先行点を決定する処理を終了する。未処理の辺が残っている場合はステップＳ１４０２〜Ｓ１４０８の処理を繰り返す。
【０１２７】
以上の処理により、先行点決定部２０４は三角形の各辺の内外判定に使用する先行点をＡ，Ｂ，Ｃの中から決定する。図１１−１〜１５の投影像の分類図では、この手順によって各辺に割り当てられた先行点が示されている。セットアップ処理部２００の後段に接続されたトラバース処理部３００は、ここで求めた先行点が各辺の内側に入るかどうかを判定することにより、次に走査するスタンプあるいはエリアを決める。
【０１２８】
以上説明したように、本実施形態のセットアップ処理部２００によれば、頂点のウィンドウ座標のＸＹ成分を大小比較する代わりに、エッジ関数の傾き（エッジ係数）の組み合わせによって三角形の投影像を分類し、分類に応じてバウンディングボックスの四隅から走査開始点を決定しているので、入力される三角形の一部が視点より後方にある場合でも特別な処理を必要とせずに、三角形の全ての領域が投影面に投影されている場合と同様に、統一的な処理でセットアップデータを生成することができる。
【０１２９】
（トラバース処理部の処理）
次に、トラバース処理部３００の処理について説明する。トラバース処理部３００は、生成したピクセルデータをエリア単位にまとめてピクセル処理部４に渡しており、このため、トラバース処理部３００はひとつのエリア内のスタンプ走査を終えてから、次のエリア内へとスタンプを移動させている。
【０１３０】
エリアとピクセル処理部１０３の割り当ては、ピクセル処理部１０３の負荷を分散させるためにインタリーブ（interleave）の構成を採用している。例えばピクセル処理部１０３が８個ある場合、エリアとピクセル処理部１０３の割り当ては図３０に示すとおりになる。ここで、エリア内に記入されている１〜８の数字がピクセル処理部１０３の番号を表している。
【０１３１】
隣接するエリアを辿って走査を進めていくため、このような割り当てにすると８個のピクセル処理部１０３への負荷が分散し、ピクセル処理性能が向上する。例えば、図３０の小さい方の三角形を右下から左上に向かって走査する場合、５番、８番、７番、６番、５番、４番、３番、２番、１番、８番、７番、６番のように８個のピクセル処理部１０３に平均的に負荷がかかることになる。
【０１３２】
しかし、上記のようにエリアとピクセル処理部１０３を割り当てた場合でも、巨大な三角形をラスタライズする場合には半数のピクセル処理部１０３に負荷が集中し、ピクセル処理の性能が劣化してしまう。例えば、図３０において、大きい方の三角形を右下から左上に向かって走査する場合、ピクセル処理部１０３は４番、３番、２番、１番、あるいは８番、７番、６番、５番の順番で繰り返しエリアを処理することが多くなる。この結果、４番、３番、２番、１番のピクセル処理部１０３に処理が集中しているときは８番、７番、６番、５番のピクセル処理部が遊んでしまい、反対に８番、７番、６番、５番のピクセル処理部に処理が集中しているときは４番、３番、２番、１番のピクセル処理部１０４が遊んでしまう。
【０１３３】
このため、本実施の形態では、ディスプレイを図３１に示すようにタイル（tile）という列領域に分割し、ひとつのタイル内のエリア走査を終えてから、次のタイル内のエリアへと移動している。例えば、図３１示す大きい方の三角形を走査する場合、ピクセル処理部１０３は１番、２番、３番、４番、８番、７番、６番、５番、あるいは４番、３番、２番、１番、５番、６番、７番、８番の順番で繰り返しエリアを処理することが多くなり、８個のピクセル処理部１０３の負荷を分散させることができる。
【０１３４】
図１６はトラバース処理部３００によるピクセルデータの生成処理の手順を示すフローチャートである。まず、トラバース処理部３００は、セットアップ処理部２００からセットアップデータを取得する（ステップＳ１６０１）。そして、走査部３０１によってスタンプあるいはエリアを走査する（ステップＳ１６０２）。なお、かかる走査の処理については後述する。
【０１３５】
走査部３０１がスタンプあるいはエリアを１つ移動したら、すなわちスタンプ走査あるいはエリア走査の処理が１回終了したら、エッジ関数計算部３０２によってスタンプ内のピクセルおよび先行点におけるエッジ関数の値を計算する（ステップＳ１６０３）。次に、重心座標計算部３０３によってスタンプ内のピクセルの重心座標を計算する（ステップＳ１６０４）。そして、スタンプ内のピクセルデータをピクセルデータバッファ１１２に保存する（ステップＳ１６０５）。そして、走査部３０１の走査処理が終了したかどうかを判定し、終了した場合はトラバース処理部３００の処理を終了し、走査対象のピクセルが残っている場合はステップＳ１６０２の走査処理から繰り返す。
【０１３６】
（走査部３０１の処理）
次に、トラバース処理部３００の走査部３０１による、ステップＳ１６０２の走査処理について説明する。図１７は、走査部３０１の走査処理の手順を示すフローチャートである。
【０１３７】
走査部３０１は、まず、開始点決定部２０３によって決定された走査開始点を含むエリアを走査開始エリアとして選択する（ステップＳ１７０１）。そして、走査開始点を含むスタンプを走査開始スタンプとして選択する（ステップＳ１７０２）。
【０１３８】
次に、スタンプの次の列へ移動できるか否かの判定処理（ステップＳ１７０３）、スタンプの次の行へ移動できるか否かの判定処理（ステップＳ１７０４）のスタンプ走査の処理を順次実行する。さらに、エリアの次の列へ移動できるか否かの判定処理（ステップＳ１７０５）、エリアの次の行へ移動できるか否かの判定処理（ステップＳ１７０６）、エリアの次のタイルへ移動できるか否かの判定処理（ステップＳ１７０７）のエリア走査の処理を順次実行する。
【０１３９】
図１８−１はステップＳ１７０３の次の列のスタンプへの移動判定処理の手順を示すフローチャートである。
【０１４０】
まず、スタンプが次の列のエリアとの境界に到達しているかどうかを判定する（ステップＳ１８０１）。到達していた場合は、ステップＳ１８０２へ進み、到達していなかった場合はステップＳ１８０３へ進む。
【０１４１】
ステップＳ１８０２では、スタンプがＡ辺の内側に入っているかどうかを判定する。ここでＡ辺とは、先行点決定部２０４にて、内外判定に使用する先行点としてＡ点を割り当てられた辺である。スタンプがＡ辺の内側に入っているかどうかを判定するには、先行点ＡがＡ辺の内側に入っているかどうかを調べればよい。ステップＳ１８０２の判定の結果、スタンプがＡ辺の内側に入っている場合（図１８−２（Ａ））はスタンプの次の行への移動判定処理（図１７のステップＳ１７０４）へ進み、内側に入っていない場合（図１８−２（Ｂ））は、エリアの次の列への判定処理（図１７のステップＳ１７０５）へ進む。
【０１４２】
次に、ステップＳ１８０３では、スタンプがＢ辺あるいはＣ辺の外側に出ているかどうかを判定する（ステップＳ１８０３）。ここでＢ辺、Ｃ辺とは、内外判定に使用する先行点としてそれぞれＢ点、Ｃ点を割り当てられた辺である。スタンプがＢ辺あるいはＣ辺の外側に出ているかどうかを判定するには、先行点ＢあるいはＣがＢ辺あるいはＣ辺の外側に出ているかどうかを調べる。かかる判定の結果、外側に出ている場合（図１８−２（Ｃ））はスタンプの次の行への移動判定処理（図１７のステップＳ１７０４）へ進む。
【０１４３】
一方、外側に出ていない場合は、次の列のスタンプがバウンディングボックスに含まれないかどうかを判定し（ステップＳ１８０４）、含まれない場合はステップＳ１８０５へ進む。含まれる場合は次の列のスタンプに移動し、ステップＳ１８０１から処理を繰り返す。
【０１４４】
ステップ１８０５では、スタンプがＡ辺の内側に入っているかどうかを判定し（ステップＳ１８０５）、内側に入っている場合（図１８−２（Ｄ））は、スタンプの次の行への移動判定処理（図１７のステップＳ１７０４）へ進み、内側に入っていない場合（図１８−２（Ｅ））はエリアの次の列への判定処理（図１７のステップＳ１７０５）へ進む。
【０１４５】
図１９−１は、ステップＳ１７０４の次の行のスタンプへの移動判定処理の手順を示すフローチャートである。
【０１４６】
まず、次の行のスタンプが異なるエリアに属するかどうかを判定する（ステップＳ１９０１）。異なるエリアに属する場合（図１９−２（Ａ））は、エリアの次の列への移動判定処理（図１７のＳ１７０５）へ進む。
【０１４７】
一方、同じエリアに属する場合は、次の行のスタンプがバウンディングボックスに含まれないかどうかを判定する（ステップＳ１９０２）。
【０１４８】
バウンディングボックスに含まれない場合（図１９−２（Ｂ））は、エリアの次の列への移動判定処理（図１７のＳ１７０５）へ進む。
【０１４９】
一方、含まれる場合は、次の行のスタンプが前のタイルでＣ辺の外側に出たときのＹ座標に到達するかどうかを判定する（ステップＳ１９０３）。到達する場合（図１９−２（Ｃ））は、エリアの次の列への移動判定処理（図１７のＳ１７０５）へ進む。
【０１５０】
一方、到達しない場合は、次の行のスタンプが前のエリアでＣ辺の外側に出たときのＹ座標に到達するかどうかを判定する（ステップＳ１９０４）。到達する場合（図１９−２（Ｄ））は、エリアの次の列への移動判定処理（図１７のＳ１７０５）へ進む。一方、到達しない場合は、次のスタンプに移動し（ステップＳ１９０５）、スタンプの次の列への移動判定処理（素１７のステップ１７０３）へ進む。
【０１５１】
図２０−１は、エリアの次の列への移動判定処理の手順を示すフローチャートである。まず、エリアが次のタイルとの境界に到達しているかどうかを判定する（ステップＳ２００１）。到達している場合はステップＳ２００２２へ進み、到達していない場合はステップＳ２００３へ進む。
【０１５２】
ステップＳ２００２では、エリアがＡ辺の内側に入っているかどうかを判定する（ステップＳ２００２）。内側に入っている場合（図２０−２（Ａ））はエリアの次の行への判定処理（図１７のＳ１７０６）へ進み、外側に出ている場合（図２０−２（Ｂ））はエリアの次のタイルへの移動判定処理（図１７のＳ１７０７）へ進む。
【０１５３】
ステップＳ２００３では、エリアがＢ辺あるいはＣ辺の外側に出ているかどうかを判定する（ステップＳ２００３）。外側に出ている場合（図２０−２（Ｃ））は、エリアの次の行への判定処理（図１７のＳ１７０６）へ進み、内側に入っている場合はステップＳ２００４へ進む。
【０１５４】
ステップＳ２００４では、次の列のエリアがバウンディングボックスに含まれないかどうかを判定する（ステップＳ２００４）。含まれない場合はステップＳ２００５へ進み、含まれる場合は、次の列のエリアに移動し（ステップＳ２００６）、図１７のステップＳ１７０２へ進み、走査開始スタンプの選択を行う。
【０１５５】
ステップＳ２００５では、エリアがＡ辺の内側に入っているかどうかを判定する（ステップＳ２００５）。内側に入っている場合（図２０−２（Ｄ））はエリアの次の行への判定処理（図１７のＳ１７０６）へ進み、外側に出ている場合（図２０−２（Ｅ））は処理を終了する。
【０１５６】
図２１−１は、ステップＳ１７０７のエリアの次のタイルへの移動判定処理の手順を示すフローチャートである。まず、次のタイルが有効かどうかを判定する（ステップＳ２１０１）。有効である場合は、次のタイルへ移動し（ステップＳ２１０２）、有効でない場合は処理を終了する。
【０１５７】
ステップＳ２１０１の有効か否かの判定処理は、次のタイルが有効かどうかを表すフラグを用いて行う。このフラグは、エリアを移動する際（ステップＳ２１０２）に更新される。すなわち、エリアが次のタイルとの境界に到達しているかどうかを判定する（ステップＳ２１０３）。到達している場合はステップＳ２１０４へ進み、到達していない場合は、次のタイルの有効フラグをＯＦＦにして次のタイルを無効とする（ステップＳ２１０６）。
【０１５８】
一方、ステップＳ２１０４では、次の列のエリアがバウンディングボックスに含まれるかどうかを判定する（ステップＳ２１０４）。含まれる場合（図２１−２）は、次のタイルの有効フラグをＯＮにして次のタイルを有効とし（ステップＳ２１０５）、含まれない場合は次のタイルを無効とする（ステップＳ２１０６）。
【０１５９】
図２２−１は、図１７のステップＳ１７０６のエリアの次の行への移動判定処理の手順を示すフローチャートである。まず、次の行のエリアがバウンディングボックスに含まれないかどうかを判定する（ステップＳ２２０１）。そして、含まれない場合（図２２−２（Ａ））は、エリアの次のタイルへの移動判定処理（図１７のＳ１７０７）へ進む。
【０１６０】
一方、ステップＳ２２０１において、次の行のエリアがバウンディングボックスに含まれると判断される場合は、次の行のエリアが前のタイルでＣ辺の外側に出たときのＹ座標に到達しているかどうかを判定する（ステップＳ２２０２）。到達している場合（図２２−２（Ｂ））は、エリアの次のタイルへの移動判定処理（図１７のＳ１７０７）へ進む。一方、到達していない場合は、次の行のエリアに移動し（ステップＳ２２０３）、図１７のステップＳ１７０２の走査開始スタンプの選択を行う。
【０１６１】
ここで、次の列のエリアへ移動した場合、走査開始スタンプの選択処理（図１７のＳ１７０２）を行う必要がある。この走査開始スタンプは、前のエリア内でスタンプを移動しているときに、図２３の（Ａ）および（Ｂ）に示すようにあらかじめ見つけておく。すなわち、図２３の（Ａ）に示すように、スタンプが次の列のエリアとの境界に到達していて、かつエリア内で初めてＢ辺の内側に入った場合には、その次の列のスタンプが、次の列のエリアでの走査開始スタンプとして選択する。
【０１６２】
ただし、この条件が成立しない状態で次の列のエリアへ移動する場合がある。例えば図２３の（Ｂ）の例では、スタンプがＢ辺の内側に１度も入らないまま次の列のエリアへ移動してしまう。このような場合は、最後に次の列のエリアとの境界に到達したときの次の列のスタンプを、次の列のエリアでの走査開始スタンプにすればよい。
【０１６３】
同様に、次の行のエリアへ移動した場合も、走査開始スタンプを選択する必要がある。この走査開始スタンプは、前のエリア内でスタンプを移動しているときに、図２４に示すようにあらかじめ見つけておく。すなわち、図２４に示しように、スタンプが次の行のエリアとの境界に到達していて、その行で初めてＡ辺の内側に入った場合に、その次の行のスタンプが、次の行のエリアでの走査開始スタンプとする。
【０１６４】
これに対して、次のタイルのエリアへ移動した場合は、走査開始エリアの選択処理（図１７のＳ１７０１）を行う要がある。この走査開始エリアは、前のタイル内でエリアを移動しているときに図２５の（Ａ）および（Ｂ）に示すようにあらかじめ見つけておく。すなわち、図２５の（Ａ）に示すように、エリアが次のタイルとの境界に到達していて、かつタイル内で初めてＢ辺の内側に入った場合に、その次の列のエリアを、次のタイルでの走査開始エリアとする。
【０１６５】
ただし、この条件が成り立たないまま次のタイルへ移動することもある。例えば２５の（Ｂ）に示すように、エリアがＢ辺の内側に１度も入らないまま次のタイルへ移動してしまう。このような場合は、最後に次のタイルとの境界に到達したときの次の列のエリアを、次のタイルでの走査開始エリアにすればよい。
【０１６６】
以上説明した走査部による走査結果の例を図２６−１および図２６−２に示す。図２６−１はエリア走査の順番を、図２６−２はエリア内のスタンプ走査の順番を矢印で示している。
【０１６７】
このような走査処理を行った後、上述したように、エッジ関数計算部３０２にてスタンプ内のピクセルおよび先行点におけるエッジ関数の値を計算し、重心座標計算部３０３によりスタンプ内のピクセルの重心座標を計算し、スタンプ内のピクセルデータをピクセルデータバッファ１１２へ保存する。
【０１６８】
図２７は、ピクセルデータのデータ構造を示す説明図である。図２７に示すように、ピクセルデータは、ウィンドウ座標、重心座標、頂点インデックス、ｃｏｖｅｒａｇｅから構成される。
【０１６９】
このように、本実施形態のトラバース処理部３００によれば、入力される三角形の一部が視点より後ろ側にあるかどうかによらず、統一的な処理でピクセルデータを生成することができる。
【産業上の利用可能性】
【０１７０】
以上のように、本発明にかかる描画処理装置、描画処理方法および描画処理プログラムは、三次元グラフィクス画像を描画する際に、ラスタライズ処理を行う描画処理装置、描画処理方法および描画処理プログラムに有用であり、特に、三次元グラフィクス画像を描画するゲーム装置、ゲーム方法およびゲームプログラムに適している。
【図面の簡単な説明】
【０１７１】
【図１】本実施形態による描画処理装置の構成を示すブロック図である。
【図２】セットアップ処理部の構成を示すブロック図である。
【図３】トラバース処理部の構成を示すブロック図である。
【図４】セットアップ処理部の処理手順を示すフローチャートである。
【図５】頂点データの例を示すデータ構造図である。
【図６】バウンディングボックス計算部による三角形の投影像の外接矩形を求める処理手順を示すフローチャートである。
【図７】三角形の投影像の外接矩形を求める処理の例を示す図である。
【図８】一般的な三角形の形状の分類方法を示す図である。
【図９−１】エッジ関数の傾きの分類を示す説明図である。
【図９−２】エッジ関数の傾きの分類を示す説明図である。
【図９−３】エッジ関数の傾きの分類を示す説明図である。
【図９−４】エッジ関数の傾きの分類を示す説明図である。
【図９−５】エッジ関数の傾きの分類を示す説明図である。
【図１０】開始点決定部による走査開始点の決定処理の手順を示すフローチャートである。
【図１１−１】ｏｒ＝０の場合の三角形の投影像を示す図である。
【図１１−２】ｏｒ＝１の場合の三角形の投影像を示す図である。
【図１１−３】ｏｒ＝２の場合の三角形の投影像を示す図である。
【図１１−４】ｏｒ＝３の場合の三角形の投影像を示す図である。
【図１１−５】ｏｒ＝４の場合の三角形の投影像を示す図である。
【図１１−６】ｏｒ＝５の場合の三角形の投影像を示す図である。
【図１１−７】ｏｒ＝６の場合の三角形の投影像を示す図である。
【図１１−８】ｏｒ＝７の場合の三角形の投影像を示す図である。
【図１１−９】ｏｒ＝８の場合の三角形の投影像を示す図である。
【図１１−１０】ｏｒ＝９の場合の三角形の投影像を示す図である。
【図１１−１１】ｏｒ＝１０の場合の三角形の投影像を示す図である。
【図１１−１２】ｏｒ＝１１の場合の三角形の投影像を示す図である。
【図１１−１３】ｏｒ＝１２の場合の三角形の投影像を示す図である。
【図１１−１４】ｏｒ＝１３の場合の三角形の投影像を示す図である。
【図１１−１５】ｏｒ＝１４の場合の三角形の投影像を示す図である。
【図１２】ｏｒ＝３，ｓｕｍ＝３の場合の三角形の投影像にて無駄な走査が生じることを示す図である。
【図１３】スタンプとエリアの先行点の配置を示す図である。
【図１４】先行点決定部による先行点を決定する処理の流れを示すフローチャートである。
【図１５】セットアップデータの例を示すデータ構造図である。
【図１６】トラバース処理部の処理手順を示すフローチャートである。
【図１７】ピクセル走査処理の手順を示すフローチャートである。
【図１８−１】スタンプの次の列への移動判定処理の手順を示すフローチャートである。
【図１８−２】スタンプの次の列への移動判定処理の内容を示す説明図である。
【図１９−１】スタンプの次の行への移動判定処理の手順を示すフローチャートである。
【図１９−２】スタンプの次の行への移動判定処理の内容を示す説明図である。
【図２０−１】エリアの次の列への移動判定処理の手順を示すフローチャートである。
【図２０−２】エリアの次の列への移動判定処理の内容を示す説明図である。
【図２１−１】エリアの次のタイルへの移動判定処理の手順を示すフローチャートである。
【図２１−２】エリアの次のタイルへの移動判定処理の内容を示す説明図である。
【図２２−１】エリアの次の行への移動判定処理の手順を示すフローチャートである。
【図２２−２】エリアの次の行への移動判定処理の内容を示す説明図である。
【図２３】次の列のエリアの走査開始スタンプを示す図である。
【図２４】次の行のエリアの走査開始スタンプを示す図である。
【図２５】次のタイルの走査開始エリアを示す図である。
【図２６−１】ピクセル走査結果の例を示す図である。
【図２６−２】ピクセル走査結果の別の例を示す図である。
【図２７】ピクセルデータの例を示すデータ構造図である。
【図２８】パラメータデータ合成後のピクセルデータの例を示すデータ構造図である。
【図２９】一般的な従来の描画処理装置の構成を示すブロック図である。
【図３０】エリアラスタライズの説明図である。
【図３１】タイル単位のエリアラスタライズの説明図である。
【図３２】三角形のクリッピング処理の概要を示す模式図である。
【符号の説明】
【０１７２】
１００  ラスタライズ処理部
１０１  頂点入力処理部
１０２  頂点演算処理部
１０３  ピクセル処理部
１０４  補間処理部
１１１  頂点データバッファ
１１２  ピクセルデータバッファ
１２０  描画メモリ
２００  セットアップ処理部
２０１  エッジ係数算出部
２０２  バウンディングボックス計算部
２０３  開始点決定部
２０４  先行点決定部
２０５  エッジ関数初期値算出部
３００  トラバース処理部
３０１  走査部
３０２  エッジ関数計算部
３０３  重心座標計算部
【図１】
2005182547.tif 000006
【図２】
2005182547.tif 000007
【図３】
2005182547.tif 000008
【図４】
2005182547.tif 000009
【図５】
2005182547.tif 000010
【図６】
2005182547.tif 000011
【図７】
2005182547.tif 000012
【図８】
2005182547.tif 000013
【図９−１】
2005182547.tif 000014
【図９−２】
2005182547.tif 000015
【図９−３】
2005182547.tif 000016
【図９−４】
2005182547.tif 000017
【図９−５】
2005182547.tif 000018
【図１０】
2005182547.tif 000019
【図１１−１】
2005182547.tif 000020
【図１１−２】
2005182547.tif 000021
【図１１−３】
2005182547.tif 000022
【図１１−４】
2005182547.tif 000023
【図１１−５】
2005182547.tif 000024
【図１１−６】
2005182547.tif 000025
【図１１−７】
2005182547.tif 000026
【図１１−８】
2005182547.tif 000027
【図１１−９】
2005182547.tif 000028
【図１１−１０】
2005182547.tif 000029
【図１１−１１】
2005182547.tif 000030
【図１１−１２】
2005182547.tif 000031
【図１１−１３】
2005182547.tif 000032
【図１１−１４】
2005182547.tif 000033
【図１１−１５】
2005182547.tif 000034
【図１２】
2005182547.tif 000035
【図１３】
2005182547.tif 000036
【図１４】
2005182547.tif 000037
【図１５】
2005182547.tif 000038
【図１６】
2005182547.tif 000039
【図１７】
2005182547.tif 000040
【図１８−１】
2005182547.tif 000041
【図１８−２】
2005182547.tif 000042
【図１９−１】
2005182547.tif 000043
【図１９−２】
2005182547.tif 000044
【図２０−１】
2005182547.tif 000045
【図２０−２】
2005182547.tif 000046
【図２１−１】
2005182547.tif 000047
【図２１−２】
2005182547.tif 000048
【図２２−１】
2005182547.tif 000049
【図２２−２】
2005182547.tif 000050
【図２３】
2005182547.tif 000051
【図２４】
2005182547.tif 000052
【図２５】
2005182547.tif 000053
【図２６−１】
2005182547.tif 000054
【図２６−２】
2005182547.tif 000055
【図２７】
2005182547.tif 000056
【図２８】
2005182547.tif 000057
【図２９】
2005182547.tif 000058
【図３０】
2005182547.tif 000059
【図３１】
2005182547.tif 000060
【図３２】
2005182547.tif 000061