(57)【要約】【課題】無駄な計算や無駄なメモリアクセスを抑えることのできる描画装置を提供する。【解決手段】三次元グラフィックスを形成する三角形と直線との交点を求め、直線のうち、三角形内にある線分を求める。そして、線分上にあるピクセルを求め、これらのピクセルのみをメモリから読出し、描画処理するようにする。直線のうち、どの部分が三角形内にあるかは、エッジ関数を用いて判断する。【選択図】図１
2010140101.tif 000002
【特許請求の範囲】
【請求項１】
三角形から構成されるオブジェクトをスクリーンに描画する描画装置において、
該スクリーンのＸ軸あるいはＹ軸に平行な直線を、該直線がＸ軸に平行ならＹ軸方向に、Ｙ軸に平行ならＸ軸方向に移動させながら、該直線のうち、描画しようとする該三角形内部にある線分を取得するスパン作成部と、
該線分上にあるピクセルを描画する描画部と、
を備えることを特徴とする描画装置。
【請求項２】
前記スパン作成部は、前記三角形内部を表現する、辺ごとに定義されるエッジ関数ｆ（ｘ、ｙ）＝ａ＊ｘ＋ｂ＊ｙ＋ｃを用いて、前記線分を取得することを特徴とする請求項１に記載の描画装置。
【請求項３】
前記スパン作成部は、ディスプレイ上の描画可能範囲のＸ座標をＣＸｍｉｎからＣＸｍａｘとし、Ｙを前記直線のＹ座標値とした場合、前記線分の範囲を、
・ａ＞０の場合
Ｘ＝−ｆ（０，Ｙ）／ａとおいて、ＣＸｍａｘ＜Ｘの場合、範囲なしとし、ＣＸｍｉｎ≦
Ｘ ≦ＣＸｍａｘの場合、［Ｘ, ＣＸｍａｘ］とし、Ｘ＜ＣＸｍｉｎの場合、［ＣＸｍｉｎ, ＣＸｍａｘ］とし、
・ａ１＜０の場合
Ｘ＝−ｆ（０，Ｙ）／ａとおいて、ＣＸｍａｘ＜Ｘの場合、［ＣＸｍｉｎ, ＣＸｍａｘ］とし、
ＣＸｍｉｎ≦ Ｘ ≦ＣＸｍａｘの場合、［ＣＸｍｉｎ, Ｘ］とし、Ｘ ＜ＣＸｍｉｎの場合、範囲なしとし、
・ａ１＝０の場合
Ｘ＝ｆ（０，Ｙ）とおいて、Ｘ≧０の場合、［ＣＸｍｉｎ, ＣＸｍａｘ］とし、Ｘ＜０の場合、範囲なしとし、
以上の処理を前記三角形の３つの辺について行い、得られた範囲の論理積をとることによって求めることを特徴とする請求項２に記載の描画装置。
【請求項４】
三角形から構成されるオブジェクトをスクリーンに描画する描画方法において、
該スクリーンのＸ軸あるいはＹ軸に平行な直線を、該直線がＸ軸に平行ならＹ軸方向に、Ｙ軸に平行ならＸ軸方向に移動させながら、該直線のうち、描画しようとする該三角形内部にある線分を取得し、
該線分上にあるピクセルを描画する、
ことを特徴とする描画方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、描画装置に関する。
【背景技術】
【０００２】
三次元グラフィックス描画処理とは、三次元空間上に用意したオブジェクトを画像メモリで構成される二次元のスクリーン上に描画する処理である。描画対象のオブジェクトはプリミティブと呼ばれる細かな三角形により構成されている。したがって、三次元オブジェクトの描画処理は多数の三角形の描画処理といえる。
【０００３】
図７に、三次元グラフィックス描画装置のブロック構成図を示す。
ホストプロセッサ１０は、描画装置１２に対して描画オブジェクトや描画コマンドを与える。頂点／テクスチャメモリ１１は、ホストプロセッサが与える描画オブジェクトの頂点データやテクスチャデータを格納する。描画装置１２は、ホストプロセッサ１０から指示されて、頂点／テクスチャメモリ１１に格納されている描画オブジェクトのデータを描画する。このとき、画像メモリ１３から、すでに描画されている画像を読み込み、新たに描画する画像と混合する処理も行う。このような処理は、アルファブレンディングやデプステストを実装するために用いられる。アルファブレンディングは、２つの画像の画素をＡとＢとすると、αを０以上１以下の値として、新しい画素値Ｃ＝αＡ＋（１−α）Ｂを求める処理である。デプステスト（depth test）とは、描画オブジェクトが持っている、スクリーンからの深さを示すデータを、互いに重なる描画オブジェクト同士で比較し、深さを示すデータが小さいほうを（浅い部分にある描画オブジェクトを）描画し、深さを示すデータが大きいほうを（深い部分にある描画オブジェクトを）描画しないという判断を行う処理である。画像メモリ１３は、描画装置１２が描画結果を格納するメモリである。ディスプレイ１４は、画像メモリ１３から画像を受け取り、使用者に画像を出力する。
【０００４】
図８は、図７の描画装置内部の構成を示す図である。
頂点座標変換部２０は、三次元空間上の三角形の頂点を、視点や投影方法に基づいて二次元のディスプレイ上に写る三角形の座標に変換する。ラスタライズ処理部２１は、ディスプレイ座標で与えられる三角形を画像メモリ上にピクセルの形で描画する。ラスタライズ処理とは、このような処理を示す。描画対象となるピクセルは、その中心が三角形の内部に入るものである。ピクセルの描画を変更する場合には、すでに同じ座標に描画されているピクセル情報を得て、新たに描画する三角形のピクセル情報と混合して、改めて画像メモリのピクセルを更新する。
【０００５】
ここで、ディスプレイ座標、ピクセル、画像メモリの関係について説明する。まず、ディスプレイ座標とは、ディスプレイ上の座標でありＯｐｅｎＧＬの実装では左下を原点としている。ピクセルとは、ディスプレイ上の描画単位であり、ディスプレイ座標上に存在する１×１の正方形領域で表し、ＯｐｅｎＧＬの実装では正方形の左下の点の座標をピクセルの座標としている。また、ピクセルの座標はＸ、Ｙともに整数値であるとする。画像メモリはディスプレイに存在するすべてのピクセルの情報を格納している。
【０００６】
以後の説明では、座標系やピクセルの座標の定義はＯｐｅｎＧＬの実装に従うものとする。
三角形のラスタライズ処理は、三角形のそれぞれの辺に定義されたエッジ関数と呼ばれる式を用いて行うことができる。三角形の辺のエッジ関数とは、ディスプレイ座標Ｘ、 Ｙに関する一次式であり、以下の性質をもつ。
・対応する辺上で値が0になる
・関数の勾配が三角形の内部を向く（三角形の中にいくほど、エッジ関数の値が大きくなる）
以上の性質より、三角形の内部の点では常に3つのエッジ関数の値が正となる。
【０００７】
エッジ関数を用いて描画する場合の従来のラスタライズ処理部の構成を図９に示す。
バウンディングボックス生成部３０は、ディスプレイ上の三角形を覆う長方形（バンディングボックス）を生成する（三角形に外接する、Ｘ軸及びＹ軸に平行な辺のみで構成される長方形を生成する）。バウンディングボックスの生成により、三角形の存在するＸ，Ｙ座標それぞれの最小値と最大値を得ることができる。ここで得たバウンディングボックスの情報は、走査座標生成部３１と描画部３４に渡される。
【０００８】
走査座標生成部３１は、バウンディングボックス生成部３０から得たバウンディングボックスの情報をもとにバウンディングボックス内のピクセルの座標を描画対象の座標として一つずつ生成する。生成した座標はＸ，Ｙ座標ともに整数値であり、エッジ関数評価部３３に渡される。エッジ生成部３２は、三角形のディスプレイ座標から3つの辺のエッジ関数を生成する。エッジ関数の生成により、それぞれのエッジ関数の係数を得ることができる。ここで得られたエッジ関数は、エッジ関数評価部３３に渡される。
【０００９】
エッジ関数評価部３３は、走査座標生成部３１から得たピクセルの座標とエッジ生成部３２から得たエッジ関数を用いて、描画対象の座標が三角形の内部にあるか外部にあるかを判定する。もし、描画対象が三角形の内部にあるならば、描画部３４にその座標を渡す。外部にあるならば何もせず、次の描画対象の座標の処理に移る。
【００１０】
描画部３４は、エッジ関数評価部３３から描画対象の座標を得て、その座標に対応する三角形のピクセルを算出する。そして、画像メモリ１３から対応する既存の画素を得て、先ほど算出した画素と混合し、画像メモリ１３の内容を新たに更新する。画像メモリ１３の読み書きには時間を要する。したがって、描画に先立って、バウンディングボックス生成部３０からバウンディングボックスの情報を得て、画像メモリ１３からバウンディングボックス内のピクセルをバッファ３５に読み込む機構が設けられている。このような先読みの機構を備えることにより、画像メモリ１３へのアクセス時間を、演算時間の影に隠蔽することができる。
【発明の開示】
【発明が解決しようとする課題】
【００１１】
ラスタライズ処理部２１により、画像メモリ１３に三角形を描画することが可能となる。しかし、バウンディングボックス内のすべてのピクセルが描画されるわけではないため、以下に示す問題が発生する。
・描画されないピクセルの座標に対してもエッジ関数を計算してしまう
・読み込みを必要としないピクセル値を画像メモリに読み込んでしまう
図１０は、従来の問題点を説明する図である。
【００１２】
例えば、図１０に示された三角形４０の描画を考える。この三角形４０のバウンディングボックス３９は、図１０に示されるとおりであり、座標４１、４２、４３にあるピクセルの座標が図９の走査座標生成部３１により生成され、エッジ関数評価部３３に渡される。ところが、実際に描画されるピクセルの座標は、座標４３だけであるため、座標４１、４２についてのエッジ関数の計算は描画に寄与しない。また、図９の描画部３４は、描画に先立ってバウンディングボックスの内容をバッファ３５に読み込むが、座標４１、４２の座標に対応する画像メモリのピクセルは描画には用いられることはない。そのため、座標４１、４２のピクセルの読み込みは描画には寄与しない。
【００１３】
本発明の課題は、無駄な計算や無駄なメモリアクセスを抑えることのできる描画装置を提供することである。
【課題を解決するための手段】
【００１４】
本発明の描画装置は、三角形から構成されるオブジェクトをスクリーンに描画する描画装置において、該スクリーンのＸ軸あるいはＹ軸に平行な直線を、該直線がＸ軸に平行ならＹ軸方向に、Ｙ軸に平行ならＸ軸方向に移動させながら、該直線のうち、描画しようとする該三角形内部にある線分を取得するスパン作成部と、該線分上にあるピクセルを描画する描画部とを備える。
【発明の効果】
【００１５】
本発明によれば、無駄な計算や無駄なメモリアクセスを抑えることのできる描画装置を提供することができる。
【発明を実施するための最良の形態】
【００１６】
本発明の実施形態では、バウンディングボックス内の一つ一つの座標についてエッジ関数を適用し、座標の三角形に対する包含の是非を問うのではなく、ある一定の傾き（ディスプレイのＸ軸あるいはＹ軸に平行な傾き）をもつ複数の直線を用意し（あるいは、直線を順次移動させ）、それぞれの直線と三角形との交点を求めることにより、三角形内部に存在する座標を得る。以下の説明では、直線はＸ軸に平行で、Ｙ座標は半整数であると仮定する。Ｙ座標が半整数であるのは、ピクセルと三角形の包含判定が、ピクセルの中心点のエッジ関数の値で行われ、ピクセルの中心点の座標はＸ，Ｙともに半整数となるからである。以下では、Ｘ軸に平行な直線について説明するが、各式のＸとＹを入れ替えることにより、Ｙ軸に平行な直線を用い、Ｘ座標が半整数であるとした場合にも、以下の説明は同様に適用される。したがって、本発明の実施形態は、Ｘ軸に平行な直線の場合のみではなく、Ｙ軸に平行な直線の場合も含むものとする。Ｘ軸に平行な直線を用いるか、Ｙ軸に平行な直線を用いるかの基準は、例えば、三角形のバウンディングボックスを構成し、バウンディングボックスの長いほうの辺がＸ軸に平行ならば、Ｘ軸に平行な直線を用い、Ｙ軸に平行ならば、Ｙ軸に平行な直線を用いるというものが考えられる。
【００１７】
また、ピクセルが三角形のエッジの上に乗る場合、つまりピクセルの中心を三角形のエッジが通る場合、そのピクセルを三角形の内部に含めるのか否かという問題がある。以下の説明では三角形の左側のエッジに乗っているピクセルを描画し、右側のエッジに乗っているピクセルは描画しない、また、下側に乗っているピクセルは描画し、上側に乗っているピクセルは描画しないという判定方法を前提とする。その他の判定方法、つまり、三角形の右側のエッジに乗っているピクセルを描画し、左側のエッジに乗っているピクセルは描画しない、という判定方法を用いたとしても本発明の適用は可能であることを主張しておく。
【００１８】
図１は、本発明の実施形態に従った三角形内部のピクセルの取得の様子を示す図である。
初めに描画対象の三角形５０に、Ｘ軸に平行な直線５１を引き、三角形５０の辺５７と辺５８との交点５２と５３を得る。点５２から５３までの範囲が直線５１上で描画すべき範囲である。以降、このように、ひとつの直線の上で三角形が存在する範囲、つまり、三角形を描画すべき範囲を「スパン」と呼ぶことにする。直線５１上のスパン内にあるピクセル５４、５５、５６が三角形の内部にあり、描画すべきピクセルであると判断できる。そのピクセルがスパン上にあるか否かは、ピクセルの中心位置がスパンの範囲に入っているか否かを判断すれば、決定することが出来る。
以上の処理を、三角形に交わる、同じ傾きの直線すべてについて行うことで、三角形内
部に存在し、描画すべきピクセルをすべて求めることができる。
【００１９】
直線５１上の三角形のスパンを求める手順について説明する。
まず、三角形５０の辺５７、５８、５９のエッジ関数をｆ１（ｘ，ｙ）、ｆ２（ｘ，ｙ）、ｆ３（ｘ，ｙ）とする。すると、直線５１上の三角形のスパンは直線５１上でエッジ関数ｆ１、ｆ２、ｆ３がすべて正になる範囲、とすることができる。なぜなら、スパンは、直線５１の内、三角形内に存在する部分であるが、エッジ関数は、三角形の内部で正の値を取るからである。
【００２０】
次に、直線５１上でエッジ関数ｆ１が正になる範囲について考察する。ここで、直線５１のＹ座標をＹとおき、ｆ１は、以下の式で与えられるとする。
ｆ１（ｘ，ｙ）＝ａ１ｘ＋ｂ１ｙ＋ｃ１
また、ディスプレイ上の描画可能範囲のＸ座標をＣＸｍｉｎからＣＸｍａｘとする。ここに示したＣＸｍｉｎとＣＸｍａｘは業界用語で「シザークリップ枠」と呼ばれる。
【００２１】
直線５１上で、エッジ関数ｆ１が正になる範囲を求めるために、ｆ１のｘの係数ａの正負、および０の場合に応じて3つに場合分けする。
・ａ１＞０の場合
Ｘ＝−ｆ１（０，Ｙ）／ａ１＝−（ｂ１Ｙ＋ｃ１）／ａ１
とおく。Ｘは、ｆ１で示される辺と直線５１の交わる点のｘ座標である。
ＣＸｍａｘ＜Ｘの場合、描画範囲なしとする。
ＣＸｍｉｎ≦ Ｘ ≦ＣＸｍａｘの場合、［Ｘ, ＣＸｍａｘ］を描画範囲とする。
Ｘ＜ＣＸｍｉｎの場合、［ＣＸｍｉｎ, ＣＸｍａｘ］を描画範囲とする。
【００２２】
なぜなら、ａ１＞０の場合、ｘの値が大きくなるに従いｆ１の値も大きくなるので、三角形の内部は、ｆ１で示される辺よりｘが大きくなる方向にある、すなわち、ｆ１で表される辺は、三角形の左側の辺であるといえるからである。したがって、Ｘは、スパンの左端の座標を示すことになる。
【００２３】
・ａ１＜０の場合
Ｘ＝−ｆ１（０，Ｙ）／ａ１＝−（ｂ１Ｙ＋ｃ１）／ａ１
とおく。Ｘは、ｆ１で示される辺と直線５１の交わる点のｘ座標である。
ＣＸｍａｘ＜Ｘの場合、［ＣＸｍｉｎ, ＣＸｍａｘ］を描画範囲とする。
ＣＸｍｉｎ≦ Ｘ ≦ＣＸｍａｘの場合、［ＣＸｍｉｎ, Ｘ］を描画範囲とする。
Ｘ ＜ＣＸｍｉｎの場合、描画範囲なしとする。
【００２４】
なぜなら、ａ１＜０の場合、ｘの値が小さくなるに従いｆ１の値が大きくなるので、三角形の内部は、ｆ１で示される辺よりｘが小さくなる方向にある、すなわち、ｆ１で表される辺は、三角形の右側の辺であるといえるからである。したがって、Ｘは、スパンの右端の座標を示すことになる。
【００２５】
・ａ１＝０の場合
Ｘ＝ｆ１（０，Ｙ）＝ｂ１Ｙ＋ｃ１とおく。
Ｘ≧０の場合、［ＣＸｍｉｎ, ＣＸｍａｘ］を描画範囲とする。
Ｘ＜０の場合、描画範囲なしとする。
【００２６】
この場合は、直線５１がｘ軸に平行な直線となっている場合である。ｆ１が正の部分が三角形の内部であるので、ｆ１（０、Ｙ）＝Ｘ≧０の場合を描画範囲とする。
ｆ２、ｆ３についても同様に関数の値が正になる範囲を決定することができる。以上の方法で得られた範囲の論理積をとることにより、三角形のスパンを得ることができる。
【００２７】
以上は、描画範囲の取得の仕方であるが、以下に、より具体的な描画範囲の取得方法を
説明する。
図２は、本発明の実施形態に従ったラスタライズ部の構成図である。
【００２８】
ラスタライズ部６１は、座標変換後の頂点座標を入力とし、描画結果の画像を出力する。
Ｙ座標範囲作成部６３は、三角形が存在するＹ座標の範囲を求める部分である。三角形が存在するＹ座標の範囲は、入力される頂点座標のＹ座標値の範囲であり、それらの最大値と最小値から得られる。
【００２９】
Ｙ座標生成部６４は、Ｙ座標範囲作成部６３から得たＹ座標の範囲にあるピクセルのＹ座標値（整数）を一つずつ生成する。
エッジ生成部６５は、入力される頂点座標からエッジ関数の係数を求める。後段の描画スパン作成部６６で計算が簡単になるように、エッジ関数の係数を調節する。係数の調節方法は後述する。
【００３０】
描画スパン作成部６６は、Ｙ座標生成部６４から得るＹ座標値と、エッジ生成部６５から得るエッジ関数とから、取得されたＹ座標上にあって、三角形の内部に含まれるピクセルのＸ座標（整数）の範囲を求める。描画スパン作成部６６によるＸ座標の範囲の算出方法は後述する。
【００３１】
Ｘ座標生成部６７は、描画スパン作成部６６から得たＸ座標の範囲にあるピクセルのＸ座標（整数）を一つずつ生成する。
描画部６８は、Ｘ座標生成部６７から描画対象の座標を得て、その座標に対応する三角形の画素を算出する。そして、画像メモリ６２から、対応する既存の画素を得て、算出した画素と混合し、画像メモリの内容を新たに更新する。画像メモリの読み書きには時間を要するため、描画とは別に、描画スパン作成部６６から描画部分の情報を得て、画像メモリ６２から当該範囲のピクセルをバッファ６９に読み込む機構を備える。このような先読みの機構を備えることにより、画像メモリへのアクセス時間を隠蔽することができる。
【００３２】
エッジ生成部６５は、描画スパン作成部６６のためのエッジ関数の係数を算出する。スパンの算出は以下の計算を行うことを先に説明した。ここでは、Ｙは整数であるとしている。すなわち、Ｙは、直線５１のあるピクセルのｙ座標値としている。直線５１はピクセルの中心を通るので、直線５１のｙ座標は、ピクセルの左下端のｙ座標であるＹに、ピクセルの幅の半分の値０．５を加えたものとなる。
−ｆ（０，Ｙ＋０．５）／ａ
もしくは
ｆ（０，Ｙ＋０．５）
【００３３】
エッジ生成部６５は、算出したエッジ関数のａの値に基づいて処理を変え、調整したエッジ関数の係数ｂ’、ｃ’および、ａの正負零判定結果ａｄを描画スパン作成部６６へ送る。
【００３４】
以下では、次のような計算に基づいてエッジ関数の係数を調整する。
−ｆ（０、Ｙ＋０．５）／ａ＝−（ｂ（Ｙ＋０．５）＋ｃ）／ａ
＝−ｂ／ａ＊Ｙ−０．５＊ｂ／ａ−ｃ／ａ＝ｂ’＊Ｙ＋ｃ’
・ａ＞０の場合
ｂ’＝−ｂ／ａ
ｃ’＝−０．５＊ｂ／ａ−ｃ／ａ＋０．４９９９９９・・・
ａｄ＝正
【００３５】
ここで、ｃ’に０．４９９９９９・・・を加えているのは、例えば、ｂ’＊Ｙ＋ｃ’がちょうど、ピクセルの中心位置（整数＋０・５）となった場合、０．４９９９９９・・・
を加えることにより、Ｘの値が（整数＋０．９９９９９９・・・）となる。この値から小数点以下を切り捨てることにより、ピクセル位置が（整数）のピクセルを含むスパンを設定しているものである。また、ｂ’＊Ｙ＋ｃ’が（整数＋０．５１）などと、わずかにピクセルの中心からずれると、Ｘの値が（整数＋１．００９９９９・・・）のようになる。したがって、小数点以下を切り捨ててピクセルの位置を得ると、（整数＋１）となり、エッジ関数のあるピクセルの右隣のピクセルまで含めるようにスパンが設定される。後述するように、ピクセルが左の辺に乗っている場合には、そのピクセルを選択し、右の辺に乗っている場合には、そのピクセルを選択しないという処理を行うことになる。ここの０．４９９９９９・・・・という値は、これに限られず、０．５よりわずかに小さい値ならばよい。例えば、使用している演算器の扱う桁数が４桁ならば、０．４９９などとすればよい。あるいは、わずかな誤差が生じる可能性はあるが、０．４９などとしても良い。
なお、三角形の右側に乗っているピクセルを描画し、左側に乗っているピクセルを描画しない場合は、０．４９９９・・・の代わりに０．５を加えれば良い。
【００３６】
・ａ＜０の場合
ｂ’＝−ｂ／ａ
ｃ’＝−０．５＊ｂ／ａ−ｃ／ａ＋０．４９９９９９・・・
ａｄ＝負
ここの場合も、ｃ’に加えられている０．４９９９９９・・・は、上述と同じであり、０．５よりわずかに小さい値とする。
・ａ＝０の場合
ｂ’＝ｂ
ｃ’＝ｃ＋０．５＊ｂ
ａｄ＝零
【００３７】
描画スパン作成部６６は、エッジ生成部６５からエッジ関数の係数ｂ’、ｃ’と係数ａの正負零判定ａｄを受け取り、Ｙ座標生成部６４で指定したＹ座標上に存在する三角形の範囲をＸ座標で求める。エッジ関数は三角形の辺の数、すなわち３つ存在するが、本実施形態においてはそれらのエッジ関数の係数が、
（ｂ’１、ｃ’１、ａｄ１）、（ｂ’２、ｃ’２、ａｄ２）、（ｂ’３、ｃ’３、ａｄ３）
と組み合わされ、時分割で描画スパン作成部６６へ供給される。
【００３８】
図３に、本発明の実施形態に従ったスパンを算出する処理のフローを示す。
図３のステップＳ４０では、スパンの左端点と右端点の初期値を設定する。端点の初期値はディスプレイの描画可能範囲とする。ディスプレイの描画可能範囲は描画時の設定で別途与える。
【００３９】
ステップＳ４１、Ｓ４２、Ｓ４３では、エッジ生成部６５から得られるエッジ関数ｆ０、ｆ１、ｆ２の係数を基に、エッジ関数が正になる範囲を確定させ、左端点、右端点に反映させていく。エッジ関数が正になるＸ座標の範囲の確定方法は後述する。３つのエッジ関数が正になる範囲を左端点、右端点に反映させた結果が、3つのエッジ関数が同時に正になるピクセルのＸ座標の範囲（両端を含む）であり、この範囲が描画対象となる。ステップＳ４４では、この範囲をＸ座標生成部６７に出力する。もし、左端点＞右端点となっていれば描画範囲なしとする。
【００４０】
以下に、エッジ関数が正となる範囲の確定方法を示す。
初めに、
Ｘ＝｛（ｂ’＊Ｙ＋ｃ’）の切り捨て｝
とする。
・ａｄ＝正の場合：
スパンの左端点が更新対象となる。左端点の値＜Ｘならば、左端点の値をＸに更新し、
それ以外なら何もしない。
・ａｄ＝負の場合：
スパンの右端点が更新対象となる。右端点の値＞Ｘ−１ならば右端点の値をＸ−１に更新し、それ以外なら何もしない。
【００４１】
ここで、右端点の値をＸ−１と比較しているが、これは、スパンの右端の位置を１ピクセル分左に寄せていることになり、三角形の右の辺に乗っているピクセルは選択しないようにするための処理である。上記ａｄ＝正の場合とａｄ＝負の場合を合わせると、三角形の左の辺に乗っているピクセルは選択し、右の辺に乗っているピクセルは選択しないという範囲をスパンとして設定していることになる。
・ａｄ＝零かつＸ＞０の場合：
何もしない（ｘ軸に平行な直線をすべて描画するという意味）。ここは、エッジがｘ軸に並行で、ピクセルが三角形の内部であることを意味する。
・ａｄ＝零かつＸ＜０の場合：
左端点＝０、右端点＝−１とする（ｘ軸に平行な直線を引かない、すなわち、描画範囲なしという意味）。ここは、エッジがｘ軸に並行で、ピクセルが三角形の外であることを意味する。
・ａｄ＝零かつＸ＝０かつｂ’＞０の場合
何もしない。エッジがｘ軸に並行で、ピクセルの中心位置がエッジの上にあり、エッジの上側に三角形がある場合である。ｘ軸に並行な直線をすべて描画することを意味する。三角形の下のエッジに乗っているピクセルを描画せず、上のエッジに乗っているピクセルを描画する場合は、左端点＝０、右端点＝−１とし、描画範囲なしと設定する。
・ａｄ＝零かつＸ＝０かつｂ’＜０の場合
左端点＝０、右端点＝−１とする（描画範囲なしという意味）。エッジがｘ軸に並行で、ピクセルの中心位置がエッジの上にあり、エッジの下側に三角形がある場合である。この場合は、ｘ軸に平行な直線は描画しないということを意味する。
【００４２】
三角形の下のエッジに乗っているピクセルを描画せず、上のエッジに乗っているピクセルを描画する場合は何もせず、ｘ軸に平行な直線をすべて描画すると設定する。
【００４３】
図４及び図５は、本発明の実施形態の動作例を説明する図である。
以下のエッジ関数で表される三角形のＹ座標値が２であるピクセルのスパンを求める場合を、図４を参照しながら説明する。ただし、ディスプレイの描画領域を［０，６］とする。
ｆ１（ｘ，ｙ）＝２ｘ−ｙ
ｆ２（ｘ，ｙ）＝−ｘ＋２ｙ
ｆ３（ｘ，ｙ）＝−ｘ−ｙ＋６
【００４４】
ｆ１、ｆ２、ｆ３のエッジ係数を上記説明に従って調整した結果を図５の表1に示す。
以上に求めた係数を元に、図３のフローを実行すると次のようになる。
ステップＳ４０では、スパンの初期値を［０，６］に設定する
ステップＳ４１では、ｆ１を正にする範囲を決定する。Ｘ＝｛（０．５×２＋０．７４９９９・・・）の切捨て｝＝１となり、ａｄ１＝正なので、左端点が１になる。したがってスパンは［１，６］となる。
【００４５】
ステップＳ４２では、ｆ２を正にする範囲を決定する。Ｘ＝｛（２×２＋１．４９９・・）の切り捨て｝＝５となり、ａｄ２＝負なので、右端点が４になる。したがってスパンは［１，４］となる。
【００４６】
ステップＳ４３ではｆ３を正にする範囲を決定する。Ｘ＝｛（−１×２＋５．９９９・
・）の切り捨て｝＝３となり、ａｄ３は負なので、右端点が２になる。したがってスパンは［１，２］となる。
以上の結果より、Ｘ座標１とＸ座標２を描画することになる。
【００４７】
図６は、本発明の実施形態に従ったラスタライズ処理全体の処理フローである。
図６において、ステップＳ５０で、三角形の頂点座標を取得する。ステップＳ５１において、エッジ関数の係数を算出し、ステップＳ５２において、Ｙ座標の範囲を生成する。ステップＳ５３において、Ｙ座標の初期値の設定をする。例えば、Ｙ座標の範囲は、バウンディングボックスの縦の辺の範囲であり、Ｙ座標の初期値は、その範囲の下端の点の値である。ステップＳ５４において、Ｙ座標が範囲外になったか否かを判断する。ステップＳ５４の判断がＹｅｓの場合には、ラスタライズ処理を終了する。ステップＳ５４の判断がＮｏの場合には、ステップＳ５５で描画スパンの生成を行う。ステップＳ５５の処理は、前述したエッジ関数を使った描画スパンの決定方法の通りである。ステップＳ５６において、Ｘ座標の初期値の設定をする。Ｘ座標の初期値は、描画スパンの範囲の左端の点の値である。ステップＳ６７において、Ｘ座標がスパンの範囲外になったか否かを判断する。ステップＳ５７の判断がＹｅｓの場合には、ステップＳ６０に進む。ステップＳ５７の判断がＮｏの場合には、ステップＳ５８において、座標（Ｘ、Ｙ）のピクセルを描画し、ステップＳ５９において、Ｘ座標値を１だけ増やす更新をし、ステップＳ５７に戻る。ステップＳ６０では、Ｙ座標を１だけ増やす更新をし、ステップＳ５４に戻る。
【００４８】
上記実施形態によれば、描画に寄与しない計算を削減できると共に、描画に寄与しないメモリアクセスを削減できる。
【００４９】
以上の実施形態のほかに、以下の付記を開示する。
（付記１）
三角形から構成されるオブジェクトをスクリーンに描画する描画装置において、
該スクリーンのＸ軸あるいはＹ軸に平行な直線を、該直線がＸ軸に平行ならＹ軸方向に、Ｙ軸に平行ならＸ軸方向に移動させながら、該直線のうち、描画しようとする該三角形内部にある線分を取得するスパン作成部と、
該線分上にあるピクセルを描画する描画部と、
を備えることを特徴とする描画装置。
（付記２）
前記スパン作成部は、前記三角形内部を表現する、辺ごとに定義されるエッジ関数ｆ（ｘ、ｙ）＝ａ＊ｘ＋ｂ＊ｙ＋ｃを用いて、前記線分を取得することを特徴とする付記１に記載の描画装置。
（付記３）
前記スパン作成部は、ディスプレイ上の描画可能範囲のＸ座標をＣＸｍｉｎからＣＸｍａｘとし、Ｙを前記直線のＹ座標値とした場合、前記線分の範囲を、
・ａ＞０の場合
Ｘ＝−ｆ（０，Ｙ）／ａとおいて、ＣＸｍａｘ＜Ｘの場合、範囲なしとし、ＣＸｍｉｎ≦
Ｘ ≦ＣＸｍａｘの場合、［Ｘ, ＣＸｍａｘ］とし、Ｘ＜ＣＸｍｉｎの場合、［ＣＸｍｉｎ, ＣＸｍａｘ］とし、
・ａ１＜０の場合
Ｘ＝−ｆ（０，Ｙ）／ａとおいて、ＣＸｍａｘ＜Ｘの場合、［ＣＸｍｉｎ, ＣＸｍａｘ］とし、
ＣＸｍｉｎ≦ Ｘ ≦ＣＸｍａｘの場合、［ＣＸｍｉｎ, Ｘ］とし、Ｘ ＜ＣＸｍｉｎの場合、範囲なしとし、
・ａ１＝０の場合
Ｘ＝ｆ（０，Ｙ）とおいて、Ｘ≧０の場合、［ＣＸｍｉｎ, ＣＸｍａｘ］とし、Ｘ＜０の場合、範囲なしとし、
以上の処理を前記三角形の３つの辺について行い、得られた範囲の論理積をとることに
よって求めることを特徴とする付記２に記載の描画装置。
（付記４）
前記描画部は、前記三角形の左側及び下側の辺に乗っているピクセルは描画するが、該三角形の右側及び上側の辺に乗っているピクセルは描画しないことを特徴とする付記１に記載の描画装置。
（付記５）
前記ピクセルの座標値は、整数値であり、前記直線の、平行でない軸方向の座標値は、半整数であることを特徴とする付記１に記載の描画装置。
（付記６）
前記ピクセルを描画するか否かの判断は、該ピクセルの中心座標に基づいて判断されることを特徴とする付記１に記載の描画装置。
（付記７）
三角形から構成されるオブジェクトをスクリーンに描画する描画方法において、
該スクリーンのＸ軸あるいはＹ軸に平行な直線を、該直線がＸ軸に平行ならＹ軸方向に、Ｙ軸に平行ならＸ軸方向に移動させながら、該直線のうち、描画しようとする該三角形内部にある線分を取得し、
該線分上にあるピクセルを描画する、
ことを特徴とする描画方法。
【図面の簡単な説明】
【００５０】
【図１】本発明の実施形態に従った三角形内部のピクセルの取得の様子を示す図である。
【図２】本発明の実施形態に従ったラスタライズ部の構成図である。
【図３】本発明の実施形態に従ったスパンを算出する処理のフローを示す。
【図４】本発明の実施形態の動作例を説明する図（その１）である。
【図５】本発明の実施形態の動作例を説明する図（その２）である。
【図６】本発明の実施形態に従ったラスタライズ処理全体の処理フローである。
【図７】三次元グラフィックス描画装置のブロック構成図を示す。
【図８】図７の描画装置内部の構成を示す図である。
【図９】エッジ関数を用いて描画する場合の従来のラスタライズ処理部の構成図である。
【図１０】従来の問題点を説明する図である。
【符号の説明】
【００５１】
１０      ホストプロセッサ
１１      頂点／テクスチャメモリ
１２      描画装置
１３      画像メモリ
１４      ディスプレイ
２０      頂点座標変換部
２１      ラスタライズ処理部
３０      バウンディングボックス生成部
３１      走査座標生成部
３２      エッジ生成部
３３      エッジ関数評価部
３４      描画部
３５      バッファ
６０      頂点座標変換部
６１      ラスタライズ部
６２      画像メモリ
６３      Ｙ座標範囲作成部
６４      Ｙ座標生成部
６５      エッジ生成部
６６      描画スパン作成部
６７      Ｘ座標生成部
６８      描画部
６９      バッファ
【図１】
2010140101.tif 000003
【図２】
2010140101.tif 000004
【図３】
2010140101.tif 000005
【図４】
2010140101.tif 000006
【図５】
2010140101.tif 000007
【図６】
2010140101.tif 000008
【図７】
2010140101.tif 000009
【図８】
2010140101.tif 000010
【図９】
2010140101.tif 000011
【図１０】
2010140101.tif 000012