(57)【要約】【課題】３次元コンピュータグラフィックス描画データ作成処理の高速化を図ることができる描画データ作成方法を提供する。【解決手段】３次元モデルデータ記憶手段１９から、対象となる３次元の物体の三角形ポリゴンを１つ抽出する（Ｐ１）。次に、三角形ポリゴンのモデリング座標系の頂点座標に対してモデルビュー変換を行い、三角形ポリゴンのモデリング座標系の頂点座標を視点座標系の頂点座標に変換する（Ｐ２）。次に、三角形ポリゴンが隠面ポリゴンであるか否かの判定を行う（Ｐ３）。即ち、三角形ポリゴンの視点座標系の頂点座標を用いて隠面ポリゴン判定を行う。【選択図】          図１
2006146309.tif 000002
【特許請求の範囲】
【請求項１】
３次元の物体を構成するポリゴンのモデリング座標系の頂点座標を視点座標系の頂点座標に自動変換するモデルビュー変換工程を有する描画データ作成方法であって、
前記ポリゴンの視点座標系の頂点座標を用いて隠面ポリゴン判定を自動的に行う隠面ポリゴン判定工程を有することを特徴とする描画データ作成方法。
【請求項２】
前記ポリゴンは三角形ポリゴンであり、
前記隠面ポリゴン判定は、
【数１】
2006146309.tif 000039
の値の正負により行うことを特徴とする請求項１記載の描画データ作成方法。
但し、ＰＳを射影行列から３行目を除いた３×４型行列、前記三角形ポリゴンの視点座標系の３頂点の座標を（Ｘ１ｅ、Ｙ１ｅ、Ｚ１ｅ、Ｗ１ｅ）、（Ｘ２ｅ、Ｙ２ｅ、Ｚ２ｅ、Ｗ２ｅ）、（Ｘ３ｅ、Ｙ３ｅ、Ｚ３ｅ、Ｗ３ｅ）とすると、ｄ１〜ｄ４、Ｄ１〜Ｄ４は、
【数２】
2006146309.tif 000040
である。
【請求項３】
３次元の物体を構成するポリゴンのモデリング座標系の頂点座標を視点座標系の頂点座標に変換するモデルビュー変換回路を有する描画データ作成装置であって、
前記ポリゴンの視点座標系の頂点座標を用いて隠面ポリゴン判定を行う隠面ポリゴン判定回路を有することを特徴とする描画データ作成装置。
【請求項４】
前記ポリゴンは三角形ポリゴンであり、
前記隠面ポリゴン判定は、
【数３】
2006146309.tif 000041
の値の正負により行うことを特徴とする請求項３記載の描画データ作成装置。
但し、ＰＳを射影行列から３行目を除いた３×４型行列、前記三角形ポリゴンの視点座標系の３頂点の座標を（Ｘ１ｅ、Ｙ１ｅ、Ｚ１ｅ、Ｗ１ｅ）、（Ｘ２ｅ、Ｙ２ｅ、Ｚ２ｅ、Ｗ２ｅ）、（Ｘ３ｅ、Ｙ３ｅ、Ｚ３ｅ、Ｗ３ｅ）とすると、ｄ１〜ｄ４、Ｄ１〜Ｄ４は、
【数４】
2006146309.tif 000042
である。
【請求項５】
コンピュータに、３次元の物体を構成するポリゴンのモデリング座標系の頂点座標を視点座標系の頂点座標に変換するモデルビュー変換工程と、前記ポリゴンの視点座標系の頂点座標を用いて隠面ポリゴン判定を行う隠面ポリゴン判定工程を実行させるプログラムを含むことを特徴とする描画データ作成プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、３次元コンピュータグラフィックス（3-Dimensional Computer Graphics）を描画する場合に使用して好適な描画データ作成方法、描画データ作成装置及び描画データ作成プログラムに関する。具体的には、３次元コンピュータグラフィックス描画データ作成処理の高速化技術に関する。
【背景技術】
【０００２】
３次元の物体を、計算により２次元平面に投影して描画した画像／映像である３次元コンピュータグラフィックスでは、例えば、図６に示すように、対象となる３次元の物体（この例では、球）１０をポリゴン（多角形）１１の組み合わせにより表現する。一般的には、計算のしやすさから、ほとんどの場合、ポリゴンとして三角形ポリゴンが使用される。そして、３次元の物体を構成する三角形ポリゴンの各頂点座標に対して、対応する２次元平面上の座標値を計算で求めることによって、３次元の物体が２次元平面に投影される。
【０００３】
図７はディスプレイに３次元コンピュータグラフィックスを描画する場合に使用される従来の描画データ作成方法の一例を示すフローチャートである。図７中、１２は３次元コンピュータグラフィックスの対象となる３次元の物体を構成する三角形ポリゴンのモデリング座標系（対象となる３次元の物体に固有の座標系）での各頂点座標を記憶する３次元モデルデータ記憶手段である。
【０００４】
図７に示す従来の描画データ作成方法では、まず、３次元モデルデータ記憶手段１２から、対象となる３次元の物体の三角形ポリゴンを１つ抽出する（ステップＳ１）。次に、対象となる３次元の物体の移動／回転／拡大／縮小を行うために、処理対象の三角形ポリゴンのモデリング座標系の頂点座標に対してモデルビュー変換を行い、処理対象の三角形ポリゴンのモデリング座標系の頂点座標を、視点を原点とする視点座標系の頂点座標に変換する（ステップＳ２）。
【０００５】
図８は３次元の物体のモデリング座標系から視点座標系への変換を示す図であり、図８（Ａ）は３次元の物体１０をモデリング座標系で表現した場合を示し、図８（Ｂ）は図８（Ａ）に示すモデリング座標系で表現されている３次元の物体１０を視点座標系に変換した場合を示している。図８中、ＸM、ＹM、ＺMはモデリング座標系の座標軸、ＸE、ＹE、ＺEは視点座標系の座標軸である。
【０００６】
次に、視点座標系の視界空間を辺の長さが２の立方体に正規化するために、視点座標系に対して射影変換を行い、クリップ座標系に変換し（ステップＳ３）、更に、透視除算（Ｗ除算）を行い、ＮＤＣ（Normalized Device Coordinates）座標系に変換する（ステップＳ４）。
【０００７】
図９は３次元の物体の視点座標系からＮＤＣ座標系への変換を示す図であり、図９（Ａ）は３次元の物体１０の視点座標系での表現例を示し、図９（Ｂ）は図９（Ａ）に示す３次元の物体１０をＮＤＣ座標系に変換した場合を示している。図９中、１３は視点座標系における３次元の物体１０の視界空間、ＸD、ＹD、ＺDはＮＤＣ座標系の座標軸である。
【０００８】
次に、ＮＤＣ座標系を実際の表示デバイス（ディスプレイ）の画面サイズに変換するために、ビューポート変換を行い、スクリーン座標系に変換する（ステップＳ５）。図１０はスクリーン座標系での３次元の物体１０を示している。
【０００９】
次に、３次元の物体を構成する三角形ポリゴンのうち、隠れた三角形ポリゴン（視点からは見えない側の三角形ポリゴン）の描画データを作成する無駄な処理を省略して、３次元グラフィックス描画データ作成処理を高速化するために、処理対象としている三角形ポリゴンが隠面ポリゴンであるか否かの判定を行う（ステップＳ６）。
【００１０】
図１１は３次元の物体の隠面を説明するための図である。図１１中、１４は３次元の物体、１５は視点、１６は視界空間であり、この例では、３次元の物体１４の面１７は隠面の一つとなる。ここで、ステップＳ６における隠面ポリゴン判定は、スクリーン座標系での三角形ポリゴンの符号付き面積を計算し、符号が正の場合には隠面ポリゴンではないと判定し、符号が負の場合には隠面ポリゴンであると判定する（これとは逆に、符号が負の場合に隠面ポリゴンではないと判定し、符号が正の場合に隠面ポリゴンであると判定する方法もある）ことにより行われる。
【００１１】
隠面ポリゴン判定において、処理対象の三角形ポリゴンは隠面ポリゴンではないと判定した場合（ステップＳ６でＮＯの場合）には、レンダリング処理を行い（ステップＳ７）、三角形ポリゴンのスクリーン座標系の各頂点座標から生成される三角形ポリゴンの描画データをグラフィックスメモリ（描画データ記憶メモリ）に格納すると共に、描画データ作成処理は、ステップＳ１に戻り、次の三角形ポリゴンについての描画データ作成処理を開始する。
【００１２】
これに対して、三角形ポリゴンは隠面ポリゴンであると判定した場合（ステップＳ６でＹＥＳの場合）には、レンダリング処理は実行せず、描画データ作成処理は、ステップＳ１に戻り、次の三角形ポリゴンについての描画データ作成処理を開始する。
【００１３】
ここで、三角形ポリゴンのモデリング座標系の頂点座標を（Ｘｍ、Ｙｍ、Ｚｍ、Ｗｍ）、モデルビュー行列をＭ、三角形ポリゴンの視点座標系の頂点座標を（Ｘｅ、Ｙｅ、Ｚｅ、Ｗｅ）とすると、三角形ポリゴンの視点座標系の頂点座標（Ｘｅ、Ｙｅ、Ｚｅ、Ｗｅ）は、数５に示すように、三角形ポリゴンのモデリング座標系の頂点座標（Ｘｍ、Ｙｍ、Ｚｍ、Ｗｍ）にモデルビュー行列Ｍを掛けることで求めることができる。
【００１４】
【数５】
2006146309.tif 000003
【００１５】
また、射影行列をＰ、三角形ポリゴンのクリップ座標系の頂点座標（Ｘｃ、Ｙｃ、Ｚｃ、Ｗｃ）とすると、三角形ポリゴンのクリップ座標系の頂点座標（Ｘｃ、Ｙｃ、Ｚｃ、Ｗｃ）は、数６に示すように、三角形ポリゴンの視点座標系の頂点座標（Ｘｅ、Ｙｅ、Ｚｅ、Ｗｅ）に射影行列Ｐを掛けることで求めることができる。
【００１６】
【数６】
2006146309.tif 000004
【００１７】
また、三角形ポリゴンのＮＤＣ座標系の頂点座標を（Ｘｄ、Ｙｄ、Ｚｄ）とすると、三角形ポリゴンのＮＤＣ座標系の頂点座標（Ｘｄ、Ｙｄ、Ｚｄ）は、数７に示すように、三角形ポリゴンのクリップ座標系の頂点座標（Ｘｃ、Ｙｃ、Ｚｃ、Ｗｃ）に対して透視除算を行うことで求めることができる。
【００１８】
【数７】
2006146309.tif 000005
【００１９】
また、三角形ポリゴンのスクリーン座標系の頂点座標を（Ｘｓ、Ｙｓ、Ｚｓ）とすると、三角形ポリゴンのスクリーン座標系の頂点座標（Ｘｓ、Ｙｓ、Ｚｓ）は、数８に示す計算式で求めることができる。
【００２０】
【数８】
2006146309.tif 000006
【００２１】
但し、ScaleX、ScaleＹ、ScaleＺは「ビューポートスケール」と呼ばれるパラメータ、OffsetＸ、OffsetＹ、OffsetＺは「ビューポートオフセット」と呼ばれるパラメータである。これらビューポート変換パラメータのうち、ScaleＸ、ScaleＹ、OffsetＸ、OffsetＹは、ＮＤＣ座標系をスクリーン座標系に変換したときの「スクリーン（表示領域）のピクセル数」によって決定されるパラメータである。
【００２２】
図１２はScaleＸ、ScaleＹ、OffsetＸ、OffsetＹの具体例を説明するための図であり、図１２（Ａ）はＮＤＣ座標系、図１２（Ｂ）はスクリーン座標系を示している。ここで、スクリーン座標系の原点が画面左下で、スクリーン１８の幅がＷピクセル、高さがＨピクセル、スクリーン１８の中心座標が（Ｏｘ、Ｏｙ）の場合、ScaleＸ、ScaleＹ、OffsetＸ、OffsetＹは数９に示す値をとる。
【００２３】
【数９】
2006146309.tif 000007
【００２４】
即ち、ScaleＸはスクリーン１８の横ピクセル数の１／２、ScaleＹはスクリーン１８の縦ピクセル数の１／２、OffsetＸはスクリーン１８の中心のスクリーン座標系での横位置、OffsetＹはスクリーン１８の中心のスクリーン座標系での縦位置を示す。
【００２５】
また、ScaleＺ、OffsetＺは、デプスバッファが取り得るＺ座標の範囲（スクリーン深度範囲）によって決定されるパラメータであり、デプスバッファが取り得るＺ座標の範囲が［ＭinＺ、ＭaxＺ］の場合、数１０に示す値をとる。即ち、ScaleＺはスクリーン深度範囲の１／２、OffsetＺはスクリーン深度範囲の中心位置を示す。
【００２６】
【数１０】
2006146309.tif 000008
【００２７】
また、スクリーン座標系における三角形ポリゴンの符号付き面積Ａは、三角形ポリゴンの３頂点のスクリーン座標を（Ｘ１ｓ、Ｙ１ｓ、Ｚ１ｓ）、（Ｘ２ｓ、Ｙ２ｓ、Ｚ２ｓ）、（Ｘ３ｓ、Ｙ３ｓ、Ｚ３ｓ）とすると、数１１で計算することができる。
【００２８】
【数１１】
2006146309.tif 000009
【００２９】
図１３は数１１に示す面積計算式の導出過程を説明するための図である。図１３に示すように、三角形ポリゴンＰ１Ｐ２Ｐ３の頂点Ｐ１、Ｐ２、Ｐ３のスクリーン座標系でのＸ座標、Ｙ座標を（Ｘ１ｓ、Ｙ１ｓ）、（Ｘ２ｓ、Ｙ２ｓ）、（Ｘ３ｓ、Ｙ３ｓ）、四角形ＢＥＤＣの面積をＳ、三角形ＥＰ３Ｐ２の面積をＴ１、三角形ＣＰ１Ｄの面積をＴ２、三角形ＢＰ２Ｐ１の面積をＴ３とすると、三角形ポリゴンＰ１Ｐ２Ｐ３の面積Ａの計算式は、数１２に示すように導出することができる。
【００３０】
【数１２】
2006146309.tif 000010
【００３１】
ここで、１つの三角形ポリゴンについて、モデルビュー変換後の射影変換（ステップＳ３）、透視除算（ステップＳ４）、ビューポート変換（ステップＳ５）及び隠面ポリゴン判定（ステップＳ６）に必要な計算コストは、乗算：７２回、加減算：５０回、除算：３回となる。
【特許文献１】特開２００１−２９７３３４号公報
【発明の開示】
【発明が解決しようとする課題】
【００３２】
図７に示す従来の描画データ作成方法では、三角形ポリゴンについて、スクリーン座標系の頂点座標を計算した後に、隠面ポリゴン判定（ステップＳ６）を行うとしているので、描画しない隠面ポリゴンについても、射影変換（ステップＳ３）、透視除算（ステップＳ４）、ビューポート変換（ステップＳ５）を実行する必要があり、これが、計算処理量を大きくし、３次元コンピュータグラフィックス描画データ作成処理の高速化を妨げていた。
【００３３】
本発明は、かかる点に鑑み、３次元コンピュータグラフィックス描画データ作成処理の高速化を図ることができるようにした描画データ作成方法、描画データ作成装置及び描画データ作成プログラムを提供することを目的とする。
【課題を解決するための手段】
【００３４】
本発明の描画データ作成方法は、３次元の物体を構成するポリゴンのモデリング座標系の頂点座標を視点座標系の頂点座標に自動変換するモデルビュー変換工程を有する描画データ作成方法であって、前記ポリゴンの視点座標系の頂点座標を用いて隠面ポリゴン判定を自動的に行う隠面ポリゴン判定工程を有するというものである。
【００３５】
本発明の描画データ作成装置は、３次元の物体を構成するポリゴンのモデリング座標系の頂点座標を視点座標系の頂点座標に変換するモデルビュー変換回路を有する描画データ作成装置であって、前記ポリゴンの視点座標系の頂点座標を用いて隠面ポリゴン判定を行う隠面ポリゴン判定回路を有するというものである。
【００３６】
本発明の描画データ作成プログラムは、コンピュータに、３次元の物体を構成するポリゴンのモデリング座標系の頂点座標を視点座標系の頂点座標に変換するモデルビュー変換工程と、前記ポリゴンの視点座標系の頂点座標を用いて隠面ポリゴン判定を行う隠面ポリゴン判定工程を実行させるプログラムを含むというものである。
【発明の効果】
【００３７】
本発明の描画データ作成方法によれば、３次元の物体を構成するポリゴンの視点座標系の頂点座標を用いて隠面ポリゴン判定を行う隠面ポリゴン判定工程を有するので、描画しない隠面ポリゴンについては、射影変換、透視除算、ビューポート変換を行う必要がない。
【００３８】
本発明の描画データ作成装置によれば、３次元の物体を構成するポリゴンの視点座標系の頂点座標を用いて隠面ポリゴン判定を行う隠面ポリゴン判定回路を有するので、描画しない隠面ポリゴンについては、射影変換、透視除算、ビューポート変換を行う必要がない。
【００３９】
本発明の描画データ作成プログラムによれば、コンピュータに、３次元の物体を構成するポリゴンの視点座標系の頂点座標を用いて隠面ポリゴン判定を行う隠面ポリゴン判定工程を実行させることができるので、描画しない隠面ポリゴンについては、射影変換、透視除算、ビューポート変換を行う必要がない。
【００４０】
したがって、本発明によれば、計算処理量を減らし、３次元コンピュータグラフィックス描画データ作成処理の高速化を図ることができる。特に、リアルタイムレンダリングが要求されるシステムにおいては、描画速度が重要になるため、本発明による効果は非常に大きい。
【発明を実施するための最良の形態】
【００４１】
（本発明の描画データ作成方法の一実施形態）
図１は本発明の描画データ作成方法の一実施形態を示すフローチャートであり、本発明の描画データ作成方法の一実施形態は、本発明の描画データ作成装置の第１実施形態又は第２実施形態で実行することができる。即ち、本発明の描画データ作成方法の一実施形態の各工程は、本発明の描画データ作成装置の第１実施形態又は第２実施形態により自動的に実行することができる。
【００４２】
図１中、１９は３次元コンピュータグラフィックスの対象となる３次元の物体を構成する各三角形ポリゴンのモデリング座標系（対象となる３次元の物体に固有の座標系）での頂点座標を記憶する３次元モデルデータ記憶手段である。本発明の描画データ作成方法の一実施形態においては、まず、３次元モデルデータ記憶手段１９から、対象となる３次元の物体の三角形ポリゴンを１つ抽出する（ステップＰ１）。
【００４３】
次に、対象となる３次元の物体の移動／回転／拡大／縮小を行うために、処理対象の三角形ポリゴンのモデリング座標系の頂点座標に対してモデルビュー変換を行い、処理対象の三角形ポリゴンのモデリング座標系の頂点座標を、視点を原点とする視点座標系の頂点座標に変換する（ステップＰ２）。
【００４４】
次に、対象である３次元の物体を構成する三角形ポリゴンのうち、隠れた三角形ポリゴン（視点からは見えない側のポリゴン）の描画データを作成する無駄な処理を省略して、３次元グラフィックス描画データ作成処理を高速化するために、処理対象としている三角形ポリゴンが隠面ポリゴンであるか否かの判定を行う（ステップＰ３）。
【００４５】
ここに、処理対象の三角形ポリゴンが隠面ポリゴンであると判定した場合（ステップＰ３でＹＥＳの場合）には、隠面ポリゴンである三角形ポリゴンについては、その後の処理は行わず、描画データ作成処理は、ステップＰ１に戻り、次の三角形ポリゴンについての描画データ作成処理を開始する。
【００４６】
これに対して、処理対象の三角形ポリゴンは隠面ポリゴンではないと判定した場合（ステップＰ３でＮＯの場合）には、視点座標系の視界空間を辺の長さが２の立方体に正規化するために、視点座標系に対して射影変換を行い、クリップ座標系に変換し（ステップＰ４）、更に、透視除算（Ｗ除算）を行い、ＮＤＣ座標系に変換する（ステップＰ５）。
【００４７】
次に、ＮＤＣ座標系を実際の表示デバイス（ディスプレイ）の画面サイズに変換するために、ビューポート変換を行い、スクリーン座標系に変換する（ステップＰ６）。次に、レンダリング処理を行い（ステップＰ７）、三角形ポリゴンのスクリーン座標系の各頂点座標から生成される三角形ポリゴンの描画データをグラフィックスメモリ（描画データ記憶メモリ）に記憶すると共に、描画データ作成処理は、ステップＰ１に戻り、次の三角形ポリゴンについての描画データ作成処理を開始する。
【００４８】
＜隠面ポリゴン判定式＞
本発明の描画データ作成方法の一実施形態においては、隠面ポリゴン判定は、数１３に示す隠面ポリゴン判定式Σｄｉ・Ｄｉの値Ｂの符号の正負によって行う。即ち、数１３に示す隠面ポリゴン判定式Σｄｉ・Ｄｉの値Ｂの符号が正の場合には、三角形ポリゴンは隠面ポリゴンではないと判定し、負の場合には、三角形ポリゴンは隠面ポリゴンであると判定する。
【００４９】
【数１３】
2006146309.tif 000011
【００５０】
ここで、ｄ１〜ｄ４、Ｄ１〜Ｄ４は、数１４に示す通りである。
【００５１】
【数１４】
2006146309.tif 000012
【００５２】
但し、ｄｅｔは行列の行列式を算出することを意味する。また、ＰＳは射影行列Ｐから３行目を除いて得た３×４型の行列である。つまり、
【００５３】
【数１５】
2006146309.tif 000013
【００５４】
とするとき、
【００５５】
【数１６】
2006146309.tif 000014
【００５６】
である。更に、（Ｘ１ｅ、Ｙ１ｅ、Ｚ１ｅ、Ｗ１ｅ）、（Ｘ２ｅ、Ｙ２ｅ、Ｚ２ｅ、Ｗ２ｅ）、（Ｘ３ｅ、Ｙ３ｅ、Ｚ３ｅ、Ｗ３ｅ）は、視点座標系における三角形ポリゴンの各頂点の座標値である。つまり、視点座標系における三角形ポリゴンの頂点をＶ１ｅ、Ｖ２ｅ、Ｖ３ｅとするとき、
【００５７】
【数１７】
2006146309.tif 000015
【００５８】
である。
【００５９】
＜ｄ１・Ｄ１の計算＞
ここで、ｄ１は、
【００６０】
【数１８】
2006146309.tif 000016
【００６１】
である。したがって、行列式の性質から、ｄ１・Ｄ１は、
【００６２】
【数１９】
2006146309.tif 000017
【００６３】
となる。但し、（Ｘ１ｃ、Ｙ１ｃ、Ｚ１ｃ、Ｗ１ｃ）、（Ｘ２ｃ、Ｙ２ｃ、Ｚ２ｃ、Ｗ２ｃ）、（Ｘ３ｃ、Ｙ３ｃ、Ｚ３ｃ、Ｗ３ｃ）はクリップ座標系における三角形ポリゴンの各頂点の座標値である。つまり、クリップ座標系における三角形ポリゴンの各頂点をＶ１ｃ、Ｖ２ｃ、Ｖ３ｃとするとき、それぞれ、
【００６４】
【数２０】
2006146309.tif 000018
【００６５】
である。
【００６６】
＜ｄ２・Ｄ２の計算＞
また、ｄ２は、
【００６７】
【数２１】
2006146309.tif 000019
【００６８】
である。したがって、行列式の性質から、ｄ２・Ｄ２は、
【００６９】
【数２２】
2006146309.tif 000020
【００７０】
となる。
【００７１】
＜ｄ３・Ｄ３の計算＞
また、ｄ３は、
【００７２】
【数２３】
2006146309.tif 000021
【００７３】
である。したがって、行列式の性質から、ｄ３・Ｄ３は、
【００７４】
【数２４】
2006146309.tif 000022
【００７５】
となる。
【００７６】
＜ｄ４・Ｄ４の計算＞
また、ｄ４は、
【００７７】
【数２５】
2006146309.tif 000023
【００７８】
である。したがって、行列式の性質から、ｄ４・Ｄ４は、
【００７９】
【数２６】
2006146309.tif 000024
【００８０】
となる。
【００８１】
＜Σｄｉ・Ｄｉの計算：その１＞
ｄ１・Ｄ１の計算結果（数１９）、ｄ２・Ｄ２の計算結果（数２２）、ｄ３・Ｄ３の計算結果（数２４）、ｄ４・Ｄ４の計算結果（数２６）から、隠面ポリゴン判定式Σｄｉ・Ｄｉの値Ｂは、数２７、数２８に示すように計算することができる。
【００８２】
【数２７】
2006146309.tif 000025
【００８３】
【数２８】
2006146309.tif 000026
【００８４】
このように、隠面ポリゴン判定式Σｄｉ・Ｄｉの値Ｂは、三角形ポリゴンの各頂点のクリップ座標値で表現することができる。
【００８５】
＜Σｄｉ・Ｄｉの計算：その２＞
ＮＤＣ座標系における三角形ポリゴンの頂点をＶ１ｄ、Ｖ２ｄ、Ｖ３ｄとすると、各頂点の座標値は、それぞれ、
【００８６】
【数２９】
2006146309.tif 000027
【００８７】
である。ここで、数２７、数２８の計算結果から、隠面ポリゴン判定式Σｄｉ・Ｄｉの値Ｂは、数３０に示すように、三角形ポリゴンの各頂点のＮＤＣ座標値で表現することができる。
【００８８】
【数３０】
2006146309.tif 000028
【００８９】
ここで、各頂点のクリップ座標値Ｗ１ｃ、Ｗ２ｃ、Ｗ３ｃは正であるから、
【００９０】
【数３１】
2006146309.tif 000029
【００９１】
である。したがって、符号に関して、隠面ポリゴン判定式Σｄｉ・Ｄｉの値Ｂを
【００９２】
【数３２】
2006146309.tif 000030
【００９３】
と同一視することができる。
【００９４】
＜Σｄｉ・Ｄｉの計算：その３＞
スクリーン座標系における三角形ポリゴンの頂点をＶ１ｓ、Ｖ２ｓ、Ｖ３ｓとすると、各頂点の座標値は、それぞれ、
【００９５】
【数３３】
2006146309.tif 000031
【００９６】
である。したがって、隠面ポリゴン判定式Σｄｉ・Ｄｉの値Ｂは、数３４に示すように、三角形ポリゴンの各頂点のスクリーン座標値で表現することができる。
【００９７】
【数３４】
2006146309.tif 000032
【００９８】
ここで、ScaleＸ、ScaleＹはそれぞれ正の数であるから、「隠面ポリゴン判定式Σｄｉ・Ｄｉの値Ｂの符号」＝「スクリーン座標系における三角形ポリゴンの面積の符号」である。したがって、隠面ポリゴン判定式Σｄｉ・Ｄｉの値Ｂの符号を求めることにより、三角形ポリゴンが隠面であるか否かを判定することができる。
【００９９】
以上のように、モデルビュー変換後に隠面ポリゴン判定を行う場合には、隠面ポリゴン判定に要する計算コストは、乗算：５２回、加減算：２３回となり、特に除算を必要としない。但し、これには、ｄ１〜ｄ４の値の算出にかかる計算コストは含まれていない。ｄ１〜ｄ４の値は固定値と考えてよいので、最初に１度計算しておけばよいためである。
【０１００】
また、この計算コストは、射影変換に使用する射影行列を限定しない場合の計算コストである。しかし、一般的な３次元コンピュータグラフィックス描画データ作成処理では、射影変換に使用する射影行列は限定されており、正射影行列もしくは透視射影行列のいずれかが使用される。
【０１０１】
ここで、正射影行列は数３５に示す形をしている。
【０１０２】
【数３５】
2006146309.tif 000033
【０１０３】
但し、Ｔｘ、Ｔｙ、Ｔｚは、数３６に示す通りである。
【０１０４】
【数３６】
2006146309.tif 000034
【０１０５】
また、透視射影行列は数３７に示す形をしている。
【０１０６】
【数３７】
2006146309.tif 000035
【０１０７】
但し、Ａ、Ｂ、Ｃ、Ｄは、数３８に示す通りである。
【０１０８】
【数３８】
2006146309.tif 000036
【０１０９】
ここで、「right」、「left」、「top」、「bottom」、「near」、「far」は、視界空間を定義するパラメータである。即ち、「right」は視界空間の前面の右上の点の横位置、「left」は視界空間の前面の左下の点の横位置、「top」は視界空間の前面の右上の点の縦位置、「bottom」は視界空間の前面の左下の点の縦位置、「near」は視点から視界空間の前面までの距離、「far」は視点から視界空間の後面までの距離である。
【０１１０】
例えば、図２に示す正射影の視界空間では、「right」は正射影の視界空間２０の前面２１の右上の点の横位置、「left」は前面２１の左下の点の横位置、「top」は前面２１の右上の点の縦位置、「bottom」は前面２１の左下の点の縦位置、「near」は視点２２から前面２１までの距離、「far」は視点２２から後面２３までの距離である。
【０１１１】
また、図３に示す透視射影の視界空間では、「right」は透視射影の視界空間２４の前面２５の右上の点の横位置、「left」は前面２５の左下の点の横位置、「top」は前面２５の右上の点の縦位置、「bottom」は前面２５の左下の点の縦位置、「near」は視点２６から前面２５までの距離、「far」は視点２６から後面２７までの距離である。
【０１１２】
ここで、正射影行列もしくは透視射影行列を利用した３次元コンピュータグラフィックス描画データ作成処理を行う場合において、ｄ１〜ｄ４を計算すると、表１に示すようになる。
【０１１３】
【表１】
2006146309.tif 000037
【０１１４】
したがって、数１３に示す隠面ポリゴン判定式Σｄｉ・Ｄｉの値Ｂの算出に必要な計算は、正射影の場合には数１４に示すｄ３の値の計算のみで良く、透視射影の場合には数１４に示すｄ４の値の計算のみで良い。この結果、射影行列として、正射影行列あるいは透視射影行列を使用した場合には、隠面ポリゴン判定に要する計算コストは、乗算：１２回、加減算：５回となり、除算は不必要となる。
【０１１５】
そこで、本発明の描画データ作成方法の一実施形態では、射影行列として、正射影行列あるいは透視射影行列を使用するものとする。表２は、隠面ポリゴン判定に要する計算コストを、図７に示す従来の描画データ作成方法の場合と本発明の描画データ作成方法の一実施形態の場合とを比較して示したものである。
【０１１６】
【表２】
2006146309.tif 000038
【０１１７】
以上のように、本発明の描画データ作成方法の一実施形態によれば、３次元の物体を構成する三角形ポリゴンの視点座標系の頂点座標を用いて隠面ポリゴン判定を行う（ステップＰ３）としているので、描画しない隠面ポリゴンについては、射影変換（ステップＰ４）、透視除算（ステップＰ５）、ビューポート変換（ステップＰ６）を行う必要がない。したがって、計算処理量を減らし、３次元コンピュータグラフィックス描画データ作成処理の高速化を図ることができる。
【０１１８】
（本発明の描画データ作成装置の第１実施形態）
図４は本発明の描画データ作成装置の第１実施形態を使用する３次元コンピュータグラフィックス描画装置の概略的構成図である。図４中、１９は前述した３次元モデルデータ記憶手段、２８は３次元モデルデータ記憶手段１９から３次元モデルデータを入力して３次元コンピュータグラフィックス用の描画データを作成する本発明の描画データ作成装置の第１実施形態である。
【０１１９】
２９は本発明の描画データ作成装置の第１実施形態２８が作成した３次元コンピュータグラフィックス用の描画データを入力して３次元コンピュータグラフィックスを表示するディスプレイである。
【０１２０】
また、本発明の描画データ作成装置の第１実施形態２８において、３０はポリゴン抽出回路であり、３次元モデルデータ記憶手段１９から、３次元コンピュータグラフィックスの対象である３次元の物体を構成する三角形ポリゴンのうち、未処理の三角形ポリゴンを１つずつ取り出す回路である。
【０１２１】
３１はモデルビュー変換回路であり、ポリゴン抽出回路３０が３次元モデルデータ記憶手段１９から取り出した三角形ポリゴンのモデリング座標系の各頂点座標を、数５に示す計算式に従ってモデルビュー変換し、視点座標系の頂点座標に変換するための回路である。
【０１２２】
３２は隠面ポリゴン判定回路であり、数１３に示す隠面ポリゴン判定式Σｄｉ・Ｄｉに従い、処理対象としている三角形ポリゴンが隠面ポリゴンであるか否かの判定を行う回路である。３３は射影変換回路であり、モデルビュー変換回路３１により得られた三角形ポリゴンの視点座標系の頂点座標を、数６に示す計算式に従って射影変換し、クリップ座標系の頂点座標に変換するための回路である。
【０１２３】
３４は透視除算回路であり、数７に示す計算式に従い、処理対象の三角形ポリゴンのクリップ座標系の頂点座標を透視除算し、ＮＤＣ座標に変換する回路である。３５はビューポート変換回路であり、処理対象の三角形ポリゴンのＮＤＣ座標系の頂点座標を、数８に示す計算式に従ってビューポート変換し、スクリーン座標系の頂点座標に変換するための回路である。
【０１２４】
３６はレンダリング処理回路であり、ビューポート変換回路３５から出力される三角形ポリゴンのスクリーン座標系の頂点座標から生成される三角形ポリゴンの描画データをグラフィックスメモリ（描画データ記憶メモリ）３７に描画（格納）する回路である。３８は画面表示回路であり、グラフィックスメモリ３７に記憶された描画データに基づいて３次元の物体をディスプレイ２９に表示する回路である。
【０１２５】
このように構成された本発明の描画データ作成装置の第１実施形態２８においては、ポリゴン抽出回路３０により、３次元モデルデータ記憶手段１９から、３次元コンピュータグラフィックスの対象である３次元の物体を構成する三角形ポリゴンのうち、未処理の三角形ポリゴンの１つが取り出される。
【０１２６】
次に、モデルビュー変換回路３１により、ポリゴン抽出回路３０が３次元モデルデータ記憶手段１９から取り出した三角形ポリゴンのモデリング座標系の各頂点座標が視点座標系の頂点座標に変換される。
【０１２７】
次に、隠面ポリゴン判定回路３２により、処理対象としている三角形ポリゴンが隠面ポリゴンであるか否かの判定が行われる。ここに、三角形ポリゴンが隠面ポリゴンであると判定した場合には、隠面ポリゴンである三角形ポリゴンのその後の処理は行われず、３次元モデルデータ記憶手段１９から、次の三角形ポリゴンの取り出しが行われる。
【０１２８】
これに対して、隠面ポリゴン判定回路３２において、処理対象の三角形ポリゴンは隠面ではないと判定した場合には、射影変換回路３３により、三角形ポリゴンの視点座標系の頂点座標がクリップ座標系の頂点座標に変換される。次に、透視除算回路３４により、処理対象の三角形ポリゴンのクリップ座標系の頂点座標の透視除算が行われ、処理対象の三角形ポリゴンのクリップ座標系の頂点座標がＮＤＣ座標系の頂点座標に変換される。
【０１２９】
次に、ビューポート変換回路３５により、透視除算回路３４が出力する三角形ポリゴンのＮＤＣ座標系の頂点座標がスクリーン座標系の頂点座標に変換される。次に、レンダリング処理回路３６により、ビューポート変換回路３５が出力する三角形ポリゴンのスクリーン座標系の頂点座標から生成される三角形ポリゴンの描画データがグラフィックスメモリ３７に描画（格納）される。
【０１３０】
以上の動作が未処理の三角形ポリゴンがなくなるまで繰り返して実行され、未処理の三角形ポリゴンがなくなると、グラフィックスメモリ３７に格納されている描画データ（画像）が画面表示回路３８に転送され、３次元の物体がディスプレイ２９に描画される。
【０１３１】
以上のように、本発明の描画データ作成装置の第１実施形態２８によれば、本発明の描画データ作成方法の一実施形態を実施することができる。したがって、計算処理量を減らし、３次元コンピュータグラフィックス描画データ作成処理の高速化を図ることができる。
【０１３２】
（本発明の描画データ作成装置の第２実施形態）
図５は本発明の描画データ作成装置の第２実施形態を使用する３次元コンピュータグラフィックス描画装置の概略的構成図である。図５中、１９は前述した３次元モデルデータ記憶手段、３９は３次元モデルデータ記憶手段１９から３次元モデルデータを入力して３次元コンピュータグラフィックス用の描画データを作成する本発明の描画データ作成装置の第２実施形態である。
【０１３３】
４０は本発明の描画データ作成装置の第２実施形態３９が作成した３次元コンピュータグラフィックス用の描画データを入力して３次元コンピュータグラフィックスを表示するディスプレイである。
【０１３４】
本発明の描画データ作成装置の第２実施形態３９はコンピュータを利用してなるものであり、本発明の描画データ作成装置の第２実施形態３９において、４１は演算・制御手段をなすＣＰＵ（central processing unit）、４２はＣＰＵ４１が使用する主記憶、４３は操作者が使用するコンピュータの操作盤、４４はグラフィックスメモリ（描画データ記憶メモリ）、４５は画面表示装置、４６は３次元コンピュータグラフィックス描画プログラム記憶手段である。
【０１３５】
３次元コンピュータグラフィックス描画プログラム記憶手段４６において、４７〜５４は３次元コンピュータグラフィックス描画プログラム記憶手段４６が記憶するプログラムである。４７はポリゴン抽出プログラムであり、３次元モデルデータ記憶手段１９から、３次元コンピュータグラフィックスの対象である３次元の物体を構成する三角形ポリゴンのうち、未処理の三角形ポリゴンを１つずつ取り出すためのプログラムである。
【０１３６】
４８はモデルビュー変換プログラムであり、ポリゴン抽出プログラム４７により３次元モデルデータ記憶手段１９から取り出した三角形ポリゴンのモデリング座標系の各頂点座標を、数５に示す計算式に従ってモデルビュー変換し、視点座標系の頂点座標に変換するためのプログラムである。
【０１３７】
４９は隠面ポリゴン判定プログラムであり、数１３に示す隠面ポリゴン判定式Σｄｉ・Ｄｉに従い、処理対象としている三角形ポリゴンが隠面ポリゴンであるか否かの判定を行うためのプログラムである。５０は射影変換プログラムであり、モデルビュー変換プログラム４８により得られた三角形ポリゴンの視点座標系の頂点座標を、数６に示す計算式に従って射影変換し、クリップ座標系の頂点座標に変換するためのプログラムである。
【０１３８】
５１は透視除算プログラムであり、数７に示す計算式に従い、処理対象の三角形ポリゴンのクリップ座標系の頂点座標を透視除算し、ＮＤＣ座標に変換するためのプログラムである。５２はビューポート変換プログラムであり、三角形ポリゴンのＮＤＣ座標系の頂点座標を、数８に示す計算式に従ってビューポート変換し、スクリーン座標系の頂点座標に変換するためのプログラムである。
【０１３９】
５３はレンダリング処理プログラムであり、ビューポート変換プログラム５２により得られる三角形ポリゴンのスクリーン座標系の頂点座標から生成される三角形ポリゴンの描画データをグラフィックスメモリ４４に描画（格納）するためのプログラムである。５４は画面表示プログラムであり、グラフィックスメモリ４４に記憶された描画データに基づいて３次元の物体をディスプレイ４０に表示するプログラムである。
【０１４０】
このように構成された本発明の描画データ作成装置の第２実施形態３９においては、操作盤４３の操作により、主記憶４２に３次元コンピュータグラフィックス描画プログラムがロードされて３次元コンピュータグラフィックスの描画処理が開始される。
【０１４１】
まず、ポリゴン抽出プログラム４７が実行され、３次元モデルデータ記憶手段１９から、３次元コンピュータグラフィックスの対象である３次元の物体を構成する三角形ポリゴンのうち、未処理の三角形ポリゴンの１つが取り出される。次に、モデルビュー変換プログラム４８が実行され、ポリゴン抽出プログラム４７により３次元モデルデータ記憶手段１９から取り出した三角形ポリゴンのモデリング座標系の各頂点座標が視点座標系の頂点座標に変換される。
【０１４２】
次に、隠面ポリゴン判定プログラム４９が実行され、処理対象としている三角形ポリゴンが隠面ポリゴンであるか否かの判定が行われる。ここに、三角形ポリゴンは隠面ポリゴンであると判定された場合には、隠面ポリゴンである三角形ポリゴンのその後の処理は実行されず、３次元モデルデータ記憶手段１９から、次の三角形ポリゴンの取り出しが実行される。
【０１４３】
これに対して、隠面ポリゴン判定において、処理対象の三角形ポリゴンは隠面ではないと判定された場合には、射影変換プログラム５０が実行され、モデルビュー変換プログラム４８により得られた三角形ポリゴンの視点座標系の頂点座標がクリップ座標系の頂点座標に変換される。次に、透視除算プログラム５１が実行され、処理対象の三角形ポリゴンのクリップ座標系の頂点座標の透視除算が行われ、処理対象の三角形ポリゴンのクリップ座標系の頂点座標がＮＤＣ座標系の頂点座標に変換される。
【０１４４】
次に、ビューポート変換プログラム５２が実行され、透視除算プログラム５１により算出された三角形ポリゴンのＮＤＣ座標系の頂点座標がスクリーン座標系の頂点座標に変換される。次に、レンダリング処理プログラム５３が実行され、ビューポート変換プログラム５２により得られた三角形ポリゴンのスクリーン座標系の頂点座標がグラフィックスメモリ４４に描画（格納）される。
【０１４５】
以上の動作が未処理の三角形ポリゴンがなくなるまで繰り返して実行され、未処理の三角形ポリゴンがなくなると、画像表示プログラム５４が実行され、グラフィックスメモリ４４に格納されている描画データ（画像）が画面表示装置４５に転送され、ディスプレイ４０に３次元の物体が描画される。
【０１４６】
以上のように、本発明の描画データ作成装置の第２実施形態３９によれば、本発明の描画データ作成方法の一実施形態を実施することができる。したがって、計算処理量を減らし、３次元コンピュータグラフィックス描画データ作成処理の高速化を図ることができる。
【０１４７】
なお、特許文献１には３次元画像構成装置が記載されているが、これは、１つの画素に１つの点を描くという技術を前提とするものであり、本発明のように３次元の物体をポリゴンの組み合わせにより表現するという技術を前提とするものではない。      
【０１４８】
ここで、本発明を整理すると、本発明には、少なくとも、以下の描画データ作成方法、描画データ作成装置及び描画データ作成プログラムが含まれる。
【０１４９】
（付記１）３次元の物体を構成するポリゴンのモデリング座標系の頂点座標を視点座標系の頂点座標に自動変換するモデルビュー変換工程を有する描画データ作成方法であって、前記ポリゴンの視点座標系の頂点座標を用いて隠面ポリゴン判定を自動的に行う隠面ポリゴン判定工程を有することを特徴とする描画データ作成方法。
【０１５０】
（付記２）前記ポリゴンは三角形ポリゴンであり、前記隠面ポリゴン判定は、数１３に示す隠面ポリゴン判定式の値の正負により行うことを特徴とする付記１記載の描画データ作成方法。
【０１５１】
（付記３）３次元の物体を構成するポリゴンのモデリング座標系の頂点座標を視点座標系の頂点座標に変換するモデルビュー変換回路を有する描画データ作成装置であって、前記ポリゴンの視点座標系の頂点座標を用いて隠面ポリゴン判定を行う隠面ポリゴン判定回路を有することを特徴とする描画データ作成装置。
【０１５２】
（付記４）前記ポリゴンは三角形ポリゴンであり、前記隠面ポリゴン判定は、数１３に示す隠面ポリゴン判定式の値の正負により行うことを特徴とする付記３記載の描画データ作成装置。
【０１５３】
（付記５）コンピュータに、３次元の物体を構成するポリゴンのモデリング座標系の頂点座標を視点座標系の頂点座標に変換するモデルビュー変換工程と、前記ポリゴンの視点座標系の頂点座標を用いて隠面ポリゴン判定を行う隠面ポリゴン判定工程を実行させるプログラムを含むことを特徴とする描画データ作成プログラム。
【０１５４】
（付記６）前記ポリゴンは三角形ポリゴンであり、前記隠面ポリゴン判定は、数１３に示す隠面ポリゴン判定式の値の正負により行うことを特徴とする付記５記載の描画データ作成プログラム。
【図面の簡単な説明】
【０１５５】
【図１】本発明の描画データ作成方法の一実施形態を示すフローチャートである。
【図２】正射影の視界空間を定義するパラメータを示す図である。
【図３】透視射影の視界空間を定義するパラメータを示す図である。
【図４】本発明の描画データ作成装置の第１実施形態を使用する３次元コンピュータグラフィックス描画装置の概略的構成図である。
【図５】本発明の描画データ作成装置の第２実施形態を使用する３次元コンピュータグラフィックス描画装置の概略的構成図である。
【図６】３次元コンピュータグラフィックスにおける３次元の物体の表現例を示す図である。
【図７】ディスプレイに３次元コンピュータグラフィックスを描画する場合に使用される従来の描画データ作成方法の一例を示すフローチャートである。
【図８】３次元の物体のモデリング座標系から視点座標系への変換を示す図である。
【図９】３次元の物体の視点座標系からＮＤＣ座標系への変換を示す図である。
【図１０】スクリーン座標系での３次元の物体を示す図である。
【図１１】３次元の物体の隠面を説明するための図である。
【図１２】ビューポートスケールScaleＸ、ScaleＹ及びビューポートオフセットOffsetＸ、OffsetＹの具体例を説明するための図である。
【図１３】数１１に示す面積計算式の導出過程を説明するための図である。
【符号の説明】
【０１５６】
１０…三次元の物体、１１…ポリゴン、１２…３次元モデルデータ記憶手段、１３…視界空間、１４…３次元の物体、１５…視点、１６…視界空間、１７…隠面、１８…スクリーン（表示領域）、１９…三次元モデルデータ記憶手段、２０…視界空間、２１…視界空間の前面、２２…視点、２３…視界空間の後面、２４…視界空間、２５…視界空間の前面、２６…視点、２７…視界空間の後面、２８…本発明の描画データ作成装置の第１実施形態、２９…ディスプレイ、３０…ポリゴン抽出回路、３１…モデルビュー変換回路、３２…隠面ポリゴン判定回路、３３…射影変換回路、３４…透視除算回路、３５…ビューポート変換回路、３６…レンダリング処理回路、３７…グラフィックスメモリ、３８…画面表示回路、３９…本発明の描画データ作成装置の第２実施形態、４０…ディスプレイ、４１…ＣＰＵ、４２…主記憶、４３…操作盤、４４…グラフィックスメモリ、４５…画面表示装置、４６…３次元コンピュータグラフィックス描画プログラム記憶手段、４７…ポリゴン抽出プログラム、４８…モデルビュー変換プログラム、４９…隠面ポリゴン判定プログラム、５０…射影変換プログラム、５１…透視除算プログラム、５２…ビューポート変換プログラム、５３…レンダリング処理プログラム、５４…画面表示プログラム
【図１】
2006146309.tif 000043
【図２】
2006146309.tif 000044
【図３】
2006146309.tif 000045
【図４】
2006146309.tif 000046
【図５】
2006146309.tif 000047
【図６】
2006146309.tif 000048
【図７】
2006146309.tif 000049
【図８】
2006146309.tif 000050
【図９】
2006146309.tif 000051
【図１０】
2006146309.tif 000052
【図１１】
2006146309.tif 000053
【図１２】
2006146309.tif 000054
【図１３】
2006146309.tif 000055