描画処理装置、テクスチャ処理装置、およびテセレーション方法
【課題】 テセレーション処理には再帰的な内分演算が必要であり、計算時間がかかり、メモリを消費する。
【解決手段】 ピクセルシェーダ32の内挿演算部34は、パラメトリック曲面のパッチのバラメータ座標値を補間係数として指定したテクスチャロード命令をテクスチャユニット70に対して発行し、テクスチャユニット70からバラメータ座標値にもとづいて補間された内分係数を取得する。さらに、内挿演算部34は、テクスチャユニット70から取得した内分係数を新たに補間係数として指定したテクスチャロード命令をテクスチャユニット70に対して発行し、テクスチャユニット70から内分係数にもとづいてあらかじめ内分された制御点を取得する。内挿演算部34は、パラメータ座標値に対応する内分係数にもとづいて、テクスチャユニット70から取得した制御点を再帰的に内挿演算し、パラメータ座標値に対応するパラメトリック曲面上の点を求める。
【解決手段】 ピクセルシェーダ32の内挿演算部34は、パラメトリック曲面のパッチのバラメータ座標値を補間係数として指定したテクスチャロード命令をテクスチャユニット70に対して発行し、テクスチャユニット70からバラメータ座標値にもとづいて補間された内分係数を取得する。さらに、内挿演算部34は、テクスチャユニット70から取得した内分係数を新たに補間係数として指定したテクスチャロード命令をテクスチャユニット70に対して発行し、テクスチャユニット70から内分係数にもとづいてあらかじめ内分された制御点を取得する。内挿演算部34は、パラメータ座標値に対応する内分係数にもとづいて、テクスチャユニット70から取得した制御点を再帰的に内挿演算し、パラメータ座標値に対応するパラメトリック曲面上の点を求める。
【発明の詳細な説明】
【技術分野】
【0001】
この発明は描画データを演算処理する描画処理装置、テクスチャ処理装置、およびテセレーション方法に関する。
【背景技術】
【0002】
描画オブジェクトの3次元モデルを生成する際、より複雑な形状を表現するために自由曲面を用いることが多い。自由曲面の表現方法の一つとして、NURBS曲線またはNURBS曲面は、数少ない制御点で滑らかな曲線または曲面を表現することができるという利点があり、広く用いられている。NURBSでは、制御点の他にも、重み、ノットといった形状を操作するためのパラメータが多く、局所的に形状を変化させることが可能である。また、NURBSは、円弧や直線、放物線等の円錐曲線も統一的に表現できるといった優れた表現能力をもつ。3次元コンピュータグラフィックスでは、NURBSデータで製作された描画モデルのレンダリング技術が求められている。
【0003】
NURBS曲面やベジェ曲面等のパラメトリック曲面の形式で滑らかに表現されたオブジェクトは、制御点などのパラメータで表現されているため、3次元オブジェクトを3角形などの多角形ポリゴンの集合で表現するポリゴンモデルと比べた場合、データ量が少なくて済む。また、ネットワークゲームのようなアプリケーションにおいては、3次元モデル情報をネットワークで伝送することがあるが、自由曲面によるオブジェクト表現は、データ量が少ないため、ネットワークアプリケーションにも適している。
【0004】
自由曲面で表された3次元モデルを描画する際には、自由曲面をポリゴンに分割して、レンダリングアルゴリズムを適用して描画演算処理する。自由曲面をポリゴン分割するためには、NURBSなどで定義されたパラメトリック曲面の方程式において媒介変数の値を所定の間隔で変化させることによりパラメトリック曲面上の頂点を直接求め、これらの点をつなぎ合わせてポリゴンを生成する。これによりパラメトリック曲面が所定の分割数で多数のポリゴンに細分化される。この処理はテセレーション処理と呼ばれる。
【発明の開示】
【発明が解決しようとする課題】
【0005】
テセレーション処理においてパラメトリック曲面の頂点の座標値を求めるには、パラメトリック曲面の形状を決める制御点に対して演算を繰り返し行う必要がある。このテセレーション処理をソフトウエアで行うと、演算量が多いため、計算時間が相当にかかり、実時間で描画結果を表示することが必要な3次元コンピュータグラフィックスのアプリケーションには、テセレーション処理は向いていない。また、テセレーション処理に必要なデータや中間演算結果を記憶するために大きなメモリ容量が必要であり、テセレーション処理をハードウエアに実装することを難しくしている。
【0006】
そこで、テセレーション処理の分割数を減らして計算量を減らしたり、制御点数を減らしたり、より簡単な曲線式を使うなど曲面の自由度を制限することで計算量やメモリ量を減らすことが行われるが、その結果、描画対象オブジェクトが粗いポリゴンで表現されることになり、十分な品質でコンピュータグラフィックスの画像を生成することができないという問題が生じる。
【0007】
本発明はこうした課題に鑑みてなされたものであり、その目的は、テセレーション処理を計算量の面で効率良く行うことのできる描画処理技術を提供することにある。また、別の目的は、テセレーション処理の実行にあたり、メモリ容量の面で有利な描画処理技術を提供することにある。
【課題を解決するための手段】
【0008】
上記課題を解決するために、本発明のある態様の描画処理装置は、1つのパラメータに対して座標点を対応づけることにより表されるパラメトリック曲線により描画対象物を近似処理する描画処理装置であって、前記パラメトリック曲線を構成する単位であるセグメントに対して定義される1次元パラメータ座標系におけるパラメータの1次関数で表される内分係数について、前記パラメータの定義域内の2つの点における前記内分係数の代表値の組を保持する係数データ記憶部と、処理対象のセグメントにおいて指定される前記パラメータの指定値を補間係数として、前記係数データ記憶部に記憶された前記内分係数の代表値の組を線形補間器により補間演算することにより、前記パラメータの指定値に対応する前記内分係数の補間値を算出する補間処理部と、前記内分係数の補間値にもとづいた比で、当該処理対象のセグメントの形状を決める複数の制御点を内挿演算することにより、当該処理対象のセグメントにおいて前記パラメータの指定値に対応する前記パラメトリック曲線上の頂点座標を算出する細分化処理部とを含む。
【0009】
本発明の別の態様もまた、描画処理装置である。この装置は、2つのパラメータの組に対して座標点を対応づけることにより表されるパラメトリック曲面により描画対象物を近似処理する描画処理装置であって、前記パラメトリック曲面を構成する単位であるパッチに対して定義される2次元パラメータ座標系における第1パラメータの1次関数で表される第1内分係数について、前記第1パラメータの定義域内の2つの点における前記第1内分係数の代表値の組を保持する係数データ記憶部と、処理対象のパッチにおいて指定される前記第1パラメータの指定値を補間係数として、前記係数データ記憶部に記憶された前記第1内分係数の代表値の組を線形補間器により補間演算することにより、前記第1パラメータの指定値に対応する前記第1内分係数の補間値を算出する補間処理部と、前記第1内分係数の補間値にもとづいた比で、当該処理対象のパッチの形状を決める複数の制御点を前記2次元パラメータ座標系の第1パラメータ軸方向に内挿演算する細分化処理部とを含む。
【0010】
本発明のさらに別の態様もまた、描画処理装置である。この装置は、テクスチャに関するデータを記憶するテクスチャ記憶部と、描画処理単位に対して定義されるパラメータ座標の指定値にもとづいて、前記テクスチャ記憶部に記憶された前記テクスチャに関するデータを線形補間器により補間演算することにより、前記パラメータ座標の指定値に対応する前記テクスチャに関する補間データを算出するテクスチャ処理部と、前記テクスチャに関する補間データを用いて、前記描画処理単位の演算処理を行う描画処理部とを含む。前記描画処理単位は、1次元パラメータ座標で表されるパラメトリック曲線を構成する単位であるセグメント、または2次元パラメータ座標で表されるパラメトリック曲面を構成する単位であるパッチであり、前記テクスチャ記憶部は、前記セグメントまたは前記パッチに対して定義されるパラメータ座標に依存する内分係数について、前記パラメータの定義域内の2つの点における前記内分係数の代表値の組を前記テクスチャに関するデータとして保持し、前記テクスチャ処理部は、処理対象のセグメントまたはパッチについて前記描画処理部により順次指定されるパラメータ座標の指定値を補間係数として、前記内分係数の代表値の組を線形補間器により補間演算することにより、前記パラメータ座標の指定値に対応する前記内分係数の補間値を算出し、前記描画処理部は、前記内分係数の補間値にもとづいた比で、当該処理対象のセグメントまたはパッチの形状を決める複数の制御点を内挿演算することにより、当該処理対象のセグメントまたはパッチにおいて前記パラメータ座標の指定値に対応する前記パラメトリック曲線またはパラメトリック曲面上の点の座標を順次算出する。
【0011】
本発明のさらに別の態様は、テクスチャ処理装置である。この装置は、テクスチャに関するデータを記憶するテクスチャ記憶部と、描画処理単位に対して定義されるパラメータ座標の指定値にもとづいて、前記テクスチャ記憶部に記憶された前記テクスチャに関するデータを線形補間器により補間演算することにより、前記パラメータ座標の指定値に対応する前記テクスチャに関する補間データを算出するテクスチャ処理部とを含む。前記描画処理単位は、1次元パラメータ座標で表されるパラメトリック曲線を構成する単位であるセグメント、または2次元パラメータ座標で表されるパラメトリック曲面を構成する単位であるパッチであり、前記テクスチャ記憶部は、前記セグメントまたは前記パッチの形状を決める複数の制御点の組を前記セグメントまたは前記パッチ毎に保持し、前記テクスチャ処理部は、処理対象のセグメントまたはパッチに適用すべき前記複数の制御点の組を前記テクスチャ記憶部から取得して線形補間器により内挿演算することにより、当該処理対象のセグメントまたはパッチにおいて指定される前記パラメータ座標の指定値に対応する前記パラメトリック曲線または前記パラメトリック曲面上の頂点座標を算出する。
【0012】
本発明のさらに別の態様は、テクスチャのデータ構造である。このテクスチャのデータ構造は、パラメトリック曲面の形状を決める制御点の3次元座標値がテクセル値として格納され、パラメトリック曲面の座標系におけるパラメータを指定値とするテクスチャの読み出し命令により隣接する2つの前記制御点の座標値がサンプリングされて、前記指定値に対応する制御点の補間値を計算可能に構成される。
【0013】
本発明のさらに別の態様もまた、テクスチャのデータ構造である。このテクスチャのデータ構造は、パラメトリック曲面の形状を決める制御点を再帰的に内挿演算する際の内分係数の始値およぶ終値が隣接するテクセル値として格納され、パラメトリック曲面の座標系におけるパラメータを指定値とするテクスチャの読み出し命令により前記内分係数の始値および終値がサンプリングされて、前記指定値に対応する内分係数の補間値を計算可能に構成される。
【0014】
本発明のさらに別の態様は、テセレーション方法である。この方法は、1つのパラメータに対して座標点を対応づけることにより表されるパラメトリック曲線を折れ線に細分化するテセレーション方法であって、前記パラメトリック曲線を構成する単位であるセグメントに対して定義される1次元パラメータ座標系におけるパラメータに依存して値が決まる内分係数について、前記パラメータの定義域の両端点における前記内分係数の値を始値および終値としてあらかじめ係数テーブルに格納しておき、処理対象のセグメントにおいて指定される前記パラメータの指定値を補間係数として、前記係数テーブルに格納された前記内分係数の始値および終値を補間することにより、前記パラメータの指定値に対応する前記内分係数の補間値を算出するステップと、前記内分係数の補間値にもとづいた比で、当該処理対象のセグメントの形状を決める複数の制御点を内挿演算することにより、当該処理対象のセグメントにおいて前記パラメータの指定値に対応する前記パラメトリック曲線上の頂点座標を算出するステップとを含む。
【0015】
本発明のさらに別の態様もまた、テセレーション方法である。この方法は、2つのパラメータの組に対して座標点を対応づけることにより表されるパラメトリック曲面をポリゴンメッシュに細分化するテセレーション方法であって、前記パラメトリック曲面を構成する単位であるパッチに対して定義される2次元パラメータ座標系における第1パラメータに依存して値が決まる第1内分係数について、前記第1パラメータの定義域の両端点における第1内分係数の値を始値および終値としてあらかじめ係数テーブルに格納しておき、処理対象のパッチにおいて指定される前記第1パラメータの指定値を補間係数として、前記係数テーブルに格納された前記第1内分係数の始値および終値を補間することにより、前記第1パラメータの指定値に対応する前記第1内分係数の補間値を算出するステップと、前記内分係数の補間値にもとづいた比で、当該処理対象のパッチの形状を決める複数の制御点を前記2次元パラメータ座標系の第1パラメータ軸方向に内挿演算するステップとを含む。
【0016】
なお、以上の構成要素の任意の組合せ、本発明の表現を方法、装置、システム、コンピュータプログラム、データ構造などの間で変換したものもまた、本発明の態様として有効である。
【発明の効果】
【0017】
本発明によれば、描画対象オブジェクトのテセレーション処理を効率良く行うことができる。
【発明を実施するための最良の形態】
【0018】
図1は、実施の形態に係る描画処理装置100の構成図である。描画処理装置100は、3次元モデル情報にもとづいて2次元画面に表示するための描画データを生成するレンダリング処理を行う。
【0019】
特に、本実施の形態の描画処理装置100は、自由曲面を用いてモデル化された描画対象オブジェクトの形状を細かく分割し、幾何学的なプリミティブの集合に変換するテセレーション(Tessellation)処理を行う。まず、描画処理装置100の構成を一般的な動作とともに説明し、その後、本実施の形態に特有のテセレーション処理に関する動作を説明する。
【0020】
ラスタライザ10は、メモリもしくは他のプロセッサや頂点シェーダなどから描画対象となるプリミティブの頂点データを取得し、描画するスクリーンに対応したピクセル情報に変換する。描画プリミティブは、3次元オブジェクトをポリゴンモデルで表した場合の点、線、三角形、四角形などの幾何学図形の描画単位であり、頂点単位で表されるデータである。ラスタライザ10は、3次元空間上の描画プリミティブを投影変換により描画平面上の図形に変換するビュー変換を行い、さらに、描画平面上の図形を描画平面の水平方向に沿ってスキャンしながら、1列毎に量子化されたピクセルに変換する。
【0021】
ラスタライザ10により、描画プリミティブがピクセル展開され、各ピクセルについて、RGB3原色で表されるカラー値、透明度を示すアルファ(α)値、奥行きを示すZ値、テクスチャ属性を参照するためのパラメータ座標であるUV座標値などを含むピクセル情報が算出される。
【0022】
ラスタライザ10は、1つ以上のピクセルを含む所定サイズのピクセル集合の単位で上記のラスタライズ処理を行い、ラスタライズ処理後のピクセル集合をバッファリングしながら、ピクセル集合の単位でシェーダユニット30に順次供給する。ラスタライザ10からシェーダユニット30に供給されたピクセル集合は、シェーダユニット30においてパイプライン処理される。ピクセル集合は、ラスタライザ10が一度に処理するピクセルをまとめたものであり、ラスタライズ処理の単位であり、また同時に、シェーダユニット30における描画演算処理の単位にもなっている。
【0023】
シェーダユニット30は、非同期動作する複数のピクセルシェーダ32を含み、それぞれが担当するピクセル集合を処理することでピクセルの描画処理を並列に実行する。各ピクセルシェーダ32は、ラスタライザ10からピクセル集合単位で分配されるピクセル情報をもとに、シェーディング処理を行ってピクセルのカラー値を求め、さらに、テクスチャマッピングを行う場合は、テクスチャユニット70から得られるテクスチャのカラー値を合成して最終的なピクセルのカラー値を算出し、メモリ50にピクセルデータを書き込む。
【0024】
テクスチャユニット70は、各ピクセルシェーダ32において処理されるピクセルにテクスチャデータをマッピングする処理を行う。ポリゴン面上のピクセルにマッピングされるテクスチャの位置は2次元パラメータ座標であるUV座標系で表される。テクスチャユニット70は、各ピクセルシェーダ32からピクセルにマッピングされるテクスチャの座標値(u,v)を取得し、座標値(u,v)に対応するカラー値を補間して、各ピクセルシェーダ32にその補間値を供給する。
【0025】
ピクセルシェーダ32は、さらに、メモリ50に保持された描画データに対して、フォギング、アルファブレンディング等の処理を行い、最終的なピクセルのカラー値を求め、メモリ50のピクセルデータを更新する。
【0026】
メモリ50は、各ピクセルシェーダ32により生成されたピクセルデータをスクリーン座標で格納するフレームバッファとして機能する領域をもつ。フレームバッファに格納されたピクセルデータは、最終描画画像であることも、シェーディング処理過程にある中間画像であることもある。フレームバッファに記憶されたピクセルデータは、表示装置に出力されて表示される。
【0027】
次に、描画処理装置100の各構成によるテセレーション処理に関する動作を説明する。
【0028】
ラスタライザ10は、正方形の描画プリミティブ(以下、単に正方形プリミティブという)の入力を受ける。正方形プリミティブは、正方形の対角線の両端である2つの頂点をパラメータとしてもつ。ラスタライザ10は、正方形プリミティブをピクセルデータに変換するラスタライズ処理の機能を利用して、正方形プリミティブ内でパラメトリック曲面の最小構成単位であるパッチに対して定義される2次元パラメータ座標値(u,v)をピクセル単位で生成する。
【0029】
また、ラスタライザ10は、パラメトリック曲面のパッチの形状を決める制御点データを参照するためのインデックスと、パッチのu、vそれぞれの方向で使用される後述のノットパターンのタイプを決め、パッチ内の2次元パラメータ座標値(u、v)とともにパッチのパラメータ情報としてシェーダユニット30のピクセルシェーダ32に供給する。
【0030】
図2(a)、(b)は、ラスタライザ10に入力される正方形プリミティブを説明する図である。図2(a)は、ラスタライザ10に入力される均等なサイズの正方形プリミティブ200〜203を示す。各正方形プリミティブ200〜203は、縦横4ピクセルのピクセル集合を縦方向、横方向にそれぞれ4つずつ並べたものであり、縦横16ピクセル、合計256ピクセルの描画領域をもつ。この場合、ラスタライザ10は、正方形プリミティブを縦横16分割、合計256分割で細分化して、2次元パラメータ座標値を順次生成する。
【0031】
図2(a)のように、ラスタライザ10が、描画対象オブジェクトに対して同一サイズの正方形プリミティブ200〜203の入力を受ける場合、描画対象オブジェクトの自由曲面の分割粒度は一定であり、自由曲面は均等に細分化される。描画オブジェクトの自由曲面を細分化する粒度を状況に応じて可変にする適応型テセレーション(Adaptive Tessellation)を行う場合は、正方形プリミティブのサイズを変えてラスタライザ10に入力すればよい。
【0032】
図2(b)は、適応型テセレーションを行う場合に、ラスタライザ10に入力される正方形プリミティブを説明する図である。縦横4ピクセルのピクセル集合を縦方向、横方向にそれぞれ2つずつ並べた正方形プリミティブ210、211は、縦横8ピクセル、合計64ピクセルの描画領域をもつ。この場合、ラスタライザ10は、正方形プリミティブを縦横8分割、合計64分割で細分化して、2次元パラメータ座標値を順次生成する。
【0033】
これに対して、縦横4ピクセルのピクセル集合を縦方向、横方向にそれぞれ5つずつ並べた正方形プリミティブ212は、縦横20ピクセル、合計400ピクセルの描画領域をもつ。この場合、ラスタライザ10は、正方形プリミティブを縦横20分割、合計400分割で細分化して、2次元パラメータ座標値を順次生成する。
【0034】
縦横4ピクセルのピクセル集合を縦方向、横方向にそれぞれ4つずつ並べた正方形プリミティブ213は、図2(a)で説明したように、縦横16分割、合計256分割で細分化される。
【0035】
このように正方形プリミティブのサイズが大きくなるほど、分割数が増え、同じ描画領域でもより細かく細分化される。たとえば、描画オブジェクトを描画する際の詳細度が高いほど、正方形プリミティブのサイズを大きくして分割数を増やしたり、パッチの法線方向と視線方向との関係に応じて正方形プリミティブのサイズを可変にして分割数を変えることができる。また、複雑な形状の描画オブジェクトの場合には、正方形プリミティブのサイズを大きくして分割数を増やすことができる。このように、正方形プリミティブのサイズを状況に応じて可変にすることで適応型テセレーション処理が可能になる。
【0036】
さらに、正方形プリミティブを指定するときのパラメータを調整すれば、本来の正方形領域よりも狭い範囲を指定してテセレーション処理を実行することも可能である。正方形プリミティブに対して、領域の対角線の両端の頂点を指定するパラメータを調整することで、描画範囲を限定することが可能である。正方形領域の対角線の両端の頂点パラメータは、(0,0)および(1,1)であるが、これを0〜1の間の値にすることで、描画範囲を狭めることができる。符号214で示すように、頂点(0.25,0.3)、(0.5,0.9)を指定することで、これらを結ぶ対角線で規定される長方形領域に正方形プリミティブの描画範囲を狭めることができる。このように描画領域を定める対角線の両端の頂点パラメータを調整することで、正方形プリミティブをラスタライザ10に入力した場合でも、長方形の形状に描画領域を制限することで、任意の矩形領域の曲面を生成することができる。
【0037】
テセレーション処理を行うためのシェーダユニット30とテクスチャユニット70の具体的な構成と動作について説明する前に、まず、テセレーション処理の大まかな手順を説明する。
【0038】
3次元オブジェクトを表現する際の自由曲面の種類としては、ベジエ(Bezier)曲面やBスプライン(B-Spline)曲面などいくつかの種類があり、より一般的な自由曲面の表現形式としてNURBS(Non Uniform Rational B-Spline)曲面が広く用いられている。これらの曲面は、2つのパラメータu、vを媒介変数としたパラメトリック曲面であり、2つの媒介変数(u,v)に対して曲面上の点(x,y,z)が連続的に定義される。パラメトリック曲面でオブジェクトをモデリングする際、パッチと呼ばれるパラメトリック曲面の最小構成単位をつなぎ合わせて1つの曲面を表現する。
【0039】
本実施の形態では、パラメトリック曲面として設計の自由度が高いNURBS曲面の場合を説明するが、他の種類の自由曲面の場合も、同様のテセレーション処理が可能である。
【0040】
図3は、パラメトリック曲面の最小構成単位であるパッチを説明する図である。パッチは0≦u≦1、0≦v≦1の範囲で定義され、4階のBスプライン曲面の場合は、制御点はu方向に4個、v方向に4個設けられ、合計16個の制御点P0〜P15をもつ。このパラメトリック曲面をu方向またはv方向で見た場合、パラメータuまたはvを媒介変数としたパラメトリック曲線と見ることができる。パラメトリック曲線の最小単位はセグメントと呼ばれ、4階のBスプライン曲線の場合、4個の制御点をもつ。
【0041】
テセレーション処理は、パラメトリック曲面のパッチ毎に2次元パラメータ座標値(u,v)を所定の間隔で変化させて、各2次元パラメータ座標値(u,v)に対応するパラメトリック曲面上の点をプリミティブの頂点座標として求める処理である。このテセレーション処理により、描画対象オブジェクトの自由曲面がパッチ毎にメッシュ状に細分化され、小さいプリミティブの集合に変換される。
【0042】
2次元パラメータ座標値(u,v)に対応するパラメトリック曲面上の点を求めるには、まず、パラメトリック曲面をu方向に見て、第1パラメータ座標値uに対応するパラメトリック曲線上の点を求め、次に、それをv方向に見て、第2パラメータ座標値vに対応するパラメトリック曲線上の点を求める。
【0043】
図4(a)〜(c)は、パラメトリック曲線の上の点を求める手順を説明する図である。ここでは、u方向、v方向のいずれでも手順は同じであるから、2次元パラメータ座標系の第1パラメータu、第2パラメータvを区別せずに、パラメータをtとおいて説明する。
【0044】
パラメトリック曲線のセグメント内でパラメータtに対応する点は、セグメントの形状を決める4つの制御点P0〜P3をパラメータtに依存する内分係数で再帰的に3回内挿演算することにより求められる。
【0045】
1回目の内挿演算では、図4(a)に示すように、第1、第2の制御点P0、P1をパラメータtに対応する内分係数a00にもとづく比a00:(1−a00)で内分する点P01を求める。同様に、第2、第3の制御点P1、P2を内分係数a10にもとづく比a10:(1−a10)で内分する点P12を求め、第3、第4の制御点P2、P3を内分係数a20にもとづく比a20:(1−a20)で内分する点P23を求める。1回目の内挿演算に用いる3つの内分係数a00、a10、a20を第1内分係数と呼ぶ。
【0046】
次に、2回目の内挿演算では、図4(b)に示すように、図4(a)で求めた第1、第2の内分点P01、P12をパラメータtに対応する内分係数a01にもとづく比a01:(1−a01)でさらに内分する点P012を求める。同様に、図4(a)で求めた第2、第3の内分点P12、P23をパラメータtに対応する内分係数a11にもとづく比a11:(1−a11)でさらに内分する点P123を求める。2回目の内挿演算に用いる2つの内分係数a01、a11を第2内分係数と呼ぶ。
【0047】
最後に、3回目の内挿演算では、図4(c)に示すように、図4(b)で求めた第1の内分点P012と第2の内分点P123をパラメータtに対応する内分係数a02にもとづく比a02:(1−a02)で内分する点P0123を求める。3回目の内挿演算に用いる1つの内分係数a02を第3内分係数と呼ぶ。
【0048】
このようにして4つの制御点を再帰的に3回内分することで得られた点P0123は、パラメータtに対応するパラメトリック曲線上の点になっている。
【0049】
図5は、4つの制御点P0〜P3の内分を繰り返すことにより、パラメトリック曲線上の点P0123が求められる様子を示す図である。4つの制御点P0〜P3をパラメータtに対応する第1内分係数で内分した点がP01(t)、P12(t)、P23(t)であり、それをさらにパラメータtに対応する第2内分係数で内分した点がP012(t)、P123(t)であり、それをさらにパラメータtに対応する第3内分係数で内分した点がP0123(t)である。パラメータtを変化させることにより、P0123(t)の描く軌跡がパラメトリック曲線Lである。なお、点P0123(t)におけるパラメトリック曲線Lの接線は、2点P012(t)、P123(t)の差分ベクトルで与えられる。
【0050】
テセレーション処理は、パラメータtを所定の間隔で小刻みに変化させながら、パラメータtに対応する内分係数を用いて4つの制御点を再帰的に3回内分して点P0123(t)を求めることで行われる。所定の間隔で変化するパラメータtに対する点P0123(t)を順に折れ線でつなげていけば、1セグメント内でパラメトリック曲線が折れ線近似される。これをu方向、v方向に行うことで、1パッチ内でパラメトリック曲面がメッシュ状に細分化され、所定の分割数のテセレーション結果が得られる。
【0051】
図6は、テセレーション処理を行うためのピクセルシェーダ32およびテクスチャユニット70の構成を示す図である。
【0052】
ピクセルシェーダ32は、ラスタライザ10から分配された正方形プリミティブに対してパラメトリック曲面のパッチを当てはめ、パッチ単位で描画対象オブジェクトの形状をメッシュ状に細分化する処理を行う。ピクセルシェーダ32は、ラスタライザ10により生成された2次元パラメータ座標値(u,v)に対応するパラメトリック曲面上の点をメッシュの頂点座標として求めることにより、パッチをメッシュに分割する。この計算を行うために、ピクセルシェーダ32は、パッチの形状を決める制御点と、制御点を再帰的に内挿演算するときの内分係数のデータを必要とする。
【0053】
後に詳しく説明するように、u方向に制御点を内挿するときに用いられる内分係数は、2次元パラメータ座標系の第1パラメータuの1次式で表され、v方向に制御点を内挿するときに用いられる内分係数は、2次元パラメータ座標系の第2パラメータvの1次式で表される。
【0054】
第1パラメータu、第2パラメータvを区別せずにtとおくと、パラメータtに対応する内分係数の値は、0≦t≦1の区間の両端点における値、すなわちt=0のときの始値と、t=1のときの終値さえ与えられれば、始値と終値をパラメータtにもとづく比t:(1−t)で内分することにより、任意のtに対する内分係数の値を求めることができる。
【0055】
この性質は、テクスチャユニット70の線形補間演算機能と親和性がある。内分係数の始値および終値をテクスチャデータとして扱い、テクスチャユニット70がパラメータtを補間係数として内分係数の始値および終値を線形補間することにすれば、任意のパラメータtに対する内分係数は、テクスチャの補間演算を利用して取得することができる。これは、いろいろなパラメータtの値に対する内分係数を保持したテーブルを用意したり、1次式にもとづいて内分係数を計算する方法に比べて、メモリ容量、計算コストの面で有利である。そこで、本実施の形態では、内分係数はその始値と終値だけがテクスチャデータとして内分係数テクスチャ54に格納されている。
【0056】
また、ピクセルシェーダ32は、パッチの形状を決める制御点を内分係数にもとづく比で再帰的に内挿演算するが、この内挿演算も、テクスチャユニット70の線形補間演算機能との親和性がある。制御点の座標値をテクスチャデータとして扱い、テクスチャユニット70が内分係数を補間係数として2つの制御点を線形補間することにすれば、制御点を内分係数にもとづいて内分した点は、テクスチャの補間演算を利用して取得することができる。そこで、本実施の形態では、制御点の再帰的な内挿演算の内、1回目の内挿演算をテクスチャユニット70の線形補間機能を用いて実行する。そのために、制御点データは、テクスチャデータとして制御点テクスチャ52に格納されている。
【0057】
ピクセルシェーダ32の内挿演算部34は、パラメトリック曲面のパッチの2次元バラメータ座標値(u,v)を補間係数として指定したテクスチャロード命令をテクスチャユニット70に対して発行し、テクスチャユニット70から2次元バラメータ座標値(u,v)にもとづいて補間された内分係数を取得する。内挿演算部34は、このテクスチャロード命令の発行の際、当該パッチに適用すべきノットパターンのタイプも指定する。このノットパターンのタイプは、テクスチャユニット70が内分係数テクスチャ54の参照行を決定するために必要となる。
【0058】
さらに、内挿演算部34は、テクスチャユニット70から取得した内分係数を新たに補間係数として指定したテクスチャロード命令をテクスチャユニット70に対して発行し、テクスチャユニット70から内分係数にもとづいて補間された制御点を取得する。内挿演算部34は、このテクスチャロード命令の発行の際、当該パッチに適用すべき制御点データのインデックスも指定する。このインデックスは、テクスチャユニット70が制御点テクスチャ52の参照行を決定するために必要となる。
【0059】
内挿演算部34は、2次元パラメータ座標値(u,v)に対応する内分係数にもとづいて、テクスチャユニット70から取得した制御点を再帰的に内挿演算し、2次元パラメータ座標値(u,v)に対応するパラメトリック曲面上の点をメッシュの頂点座標として求める。再帰的な内挿演算を可能にするため、内挿演算部34は、中間結果を保持するレジスタをもち、レジスタに演算の中間結果をいったん書き出し、レジスタに保持された中間結果を読み込んで中間結果に対するさらなる演算を行う。
【0060】
頂点データ出力部36は、内挿演算部34により求められたパラメトリック曲面のメッシュの頂点座標値を2次元パラメータ座標値(u,v)に対応づけてメモリ50に書き出す。内挿演算部34が2次元パラメータ座標値(u,v)を所定の間隔で変化させながら、パラメトリック曲面のメッシュの頂点座標値を求め、頂点データ出力部36がその頂点座標値を2次元パラメータ座標値(u,v)に対応づけてメモリ50に書き出すことで、メモリ50にはパッチ内のパラメトリック曲面をメッシュ状に細分化したデータがテセレーションデータ56として形成される。
【0061】
テクスチャユニット70は、ピクセルシェーダ32から2次元パラメータ座標値(u,v)を補間係数として受け取り、内分係数テクスチャ54から読み出した内分係数をその補間係数のもとで補間した値をピクセルシェーダ32に与える。また、テクスチャユニット70は、ピクセルシェーダ32から内分係数を補間係数として受け取り、制御点テクスチャ52から読み出した制御点をその補間係数のもとで補間した値をピクセルシェーダ32に与える。
【0062】
テクスチャユニット70が参照する制御点テクスチャ52および内分係数テクスチャ54は、それぞれテクスチャの形式で制御点と内分係数を格納したものであり、テクスチャユニット70は、テクスチャデータからテクセル値を読み出して線形補間器により線形補間する機能を利用して、制御点と内分係数を指定された補間係数で線形補間する。
【0063】
図7は、制御点テクスチャ52のデータ構造を説明する図である。制御点テクスチャ52は、パラメトリック曲面のパッチの形状を決める16個の制御点をテクセル値として行単位で格納したデータ構造をもつ。各行にはP0〜P15までの16個の制御点の3次元座標値(x,y,z)が格納されている。横方向1列の16個の制御点P0〜P15が1つのパッチ曲面分の制御点として利用される。縦方向には描画対象オブジェクトのパッチ曲面数分の制御点データが用意されている。
【0064】
テクスチャは、通常はRGB3色のカラー値からなるテクセル値を格納するものであるが、ここでは、テクセルのR、G、B値の代わりに制御点の座標値x,y,zをそれぞれ格納することで、テクスチャのデータ構造を制御点の3次元座標の格納に利用している。
【0065】
テクスチャユニット70は、制御点テクスチャ52の行番号sと制御点番号i(i=0,1…,15)にもとづく参照アドレスを指定することにより、制御点テクスチャ52から制御点の3次元座標値を読み出す。
【0066】
図8は、内分係数テクスチャ54のデータ構造を説明する図である。内分係数テクスチャ54は、NURBS曲面のパッチのノットパターン毎に、制御点の再帰的な内挿演算に用いる第1、第2および第3内分係数について、その始値および終値をテクセル値として格納したデータ構造をもつ。
【0067】
後に詳しく説明するように、本実施の形態では、NURBS曲面の隣接するパッチの滑らかな接続性を考慮してノットパターンは9種類に限定されている。内分係数テクスチャ54の各行は、ノットパターンのタイプ#1〜#9に対応しており、各行には、そのノットパターンのタイプの内分係数が4つのテクセルの形式で格納されている。
【0068】
第1テクセルには、1回目の内挿演算に用いる第1内分係数a00、a10、a20の始値(a00(0),a10(0),a20(0))がテクセル値として、カラー値(R,G,B)の代わりに格納されている。第2テクセルには、1回目の内挿演算に用いる第1内分係数a00、a10、a20の終値(a00(1),a10(1),a20(1))が格納されている。
【0069】
第3テクセルには、2回目の内挿演算に用いる第2内分係数a01、a11の始値および3回目の内挿演算に用いる第3内分係数a02の始値を組み合わせた(a01(0),a11(0),a02(0))がテクセル値として、カラー値(R,G,B)の代わりに格納されている。第4テクセルには、2回目の内挿演算に用いる第2内分係数a01、a11の終値および3回目の内挿演算に用いる第3内分係数a02の終値を組み合わせた(a01(1),a11(1),a02(1))が格納されている。
【0070】
テクスチャユニット70は、縦方向のノットパターンのタイプと横方向のテクセル番号にもとづく参照アドレスを指定することにより、内分係数テクスチャ54から内分係数を読み出す。
【0071】
図6に戻り、テクスチャユニット70のアドレス生成部74および線形補間部72が、内分係数テクスチャ54および制御点テクスチャ52をテクスチャデータとして参照して、内分係数および制御点を線形補間する動作について説明する。
【0072】
アドレス生成部74は、ピクセルシェーダ32の内挿演算部34から指定されたノットパターンのタイプと2次元パラメータ座標値(u,v)にもとづいて、内分係数テクスチャ54を参照するための参照アドレスを生成し、内分係数テクスチャ54から参照アドレスに対応する内分係数の始値および終値を読み出し、線形補間部72に入力として与える。
【0073】
線形補間部72は、加算器、差分器、乗算器、および補間係数を保持するレジスタを有する線形補間器である。線形補間器には、第1入力値X、第2入力値Y、および補間係数aが入力される。差分器は、第2入力値Yから第1入力値Xを引き算して、2入力値の差分Y−Xを計算し、乗算器に与える。乗算器は、差分器から入力された差分Y−Xに補間係数aを乗じた値a(Y−X)を計算し、加算器に与える。加算器は、乗算器から入力された乗算結果a(Y−X)に第1入力値Xを加算した値a(Y−X)+Xを計算し、線形補間器の最終的な出力値として出力する。
【0074】
線形補間部72の出力値Zは、Z=a(Y−X)+X=(1−a)X+aYと変形できるため、第1入力値Xと第2入力値Yを補間係数aにもとづくa:(1−a)の比で内分した値である。
【0075】
線形補間部72は、内挿演算部34から指定されたパラメータ座標u、vのそれぞれを補間係数として、アドレス生成部74により読み出された内分係数の始値および終値を線形補間し、内分係数の補間値を内挿演算部34に与える。具体的には、線形補間部72は、パラメータtを補間係数として、内分係数aijの始値aij(0)と終値aij(1)を線形補間器により補間した値aij(t)=(1−t)・aij(0)+t・aij(1)を出力する。
【0076】
さらに、内挿演算部34は、内分係数の補間値を線形補間部72から受け取ると、受け取った内分係数の補間値を新たに補間係数として指定してテクスチャユニット70に内分係数の補間値にもとづく比で内分された制御点を要求する。内挿演算部34は、通常は2次元パラメータ座標値(u,v)を補間係数として指定して、テクスチャユニット70に対して、2次元パラメータ座標値(u,v)にもとづいて補間されたテクセル値を要求するが、ここでは同じインタフェースを利用して(u,v)値の代わりに、内分係数を補間係数として指定する。
【0077】
アドレス生成部74は、内挿演算部34から指定された制御点データの参照行と補間係数にもとづいて、テクスチャを参照するための参照アドレスを生成し、制御点テクスチャ52から参照アドレスに対応する2つの制御点の値を読み出して、線形補間部72に入力として与える。
【0078】
線形補間部72は、内挿演算部34から指定された内分係数を補間係数として、アドレス生成部74により読み出された2つの制御点を線形補間し、制御点の補間値を内挿演算部34に与える。具体的には、線形補間部72は、パラメータtに対応する内分係数aij(t)を補間係数として、第1の制御点PAの座標値(xA,yA,zA)と第2の制御点PBの座標値(xB,yB,zB)を線形補間器により補間した座標値(xAB,yAB,zAB)=(1−aij(t))・(xA,yA,zA)+aij(t)・(xB,yB,zB)を出力する。
【0079】
図9は、ピクセルシェーダ32およびテクスチャユニット70によるテセレーション処理の手順を説明するフローチャートである。
【0080】
ピクセルシェーダ32は、ラスタライザ10から、処理対象のパッチのパラメータ情報として、当該パッチで使用される制御点データの参照行を指定するデータ(S10)、パッチのu、vそれぞれの方向で使用されるノットパターンのタイプを指定するデータ(S12)、およびパッチ内で所定の間隔で分割された2次元パラメータ座標値(u、v)を指定するデータ(S14)をそれぞれ受け取る。
【0081】
ピクセルシェーダ32の内挿演算部34は、パラメータuを補間係数とするテクスチャロード命令により、パラメータuに対応する内分係数の補間値aij(u)をロードする(S16)。テクスチャユニット70は、内挿演算部34によるテクスチャロード命令を受けて、ステップS12で指定されたu方向のノットパターンのタイプに対応する内分係数テクスチャ54の行から内分係数の始値aij(0)および終値aij(1)を読み出し、パラメータuにもとづく比u:1−uで内分係数の始値aij(0)と終値aij(1)を内分することにより、パラメータuに対応する内分係数の補間値aij(u)を求め、内挿演算部34に内分係数の補間値aij(u)をテクスチャロード命令の結果として返す。
【0082】
図10は、テクスチャロード命令により、内分係数の始値aij(0)と終値aij(1)から補間値aij(u)が得られる様子を説明する図である。内挿演算部34は、テクスチャユニット70に対して、テクスチャロード命令tldのパラメータとして(u,type)を与える。ここでtypeはノットパターンのタイプのインデックスであり、内分係数テクスチャ54の参照行に対応する。
【0083】
アドレス生成部74は、typeで指定された内分係数テクスチャ54の行の先頭アドレスを参照アドレスとして生成し、その参照アドレスから当該行の第1テクセルと第2テクセルを読み出し、線形補間部72に与える。これにより、第1内分係数の始値の組(a00(0),a10(0),a20(0))と第1内分係数の終値の組(a00(1),a10(1),a20(1))が線形補間部72に入力される。
【0084】
線形補間部72は、パラメータuを補間係数として、第1内分係数の始値(a00(0),a10(0),a20(0))と終値(a00(1),a10(1),a20(1))をu:(1−u)の比で内分した値(a00(u),a10(u),a20(u))を出力する。内挿演算部34は、テクスチャロード命令tldの返値として、指定したパラメータuに対応する内分係数の補間値(a00(u),a10(u),a20(u))を取得する。
【0085】
次に、内挿演算部34は、第2および第3内分係数についても、パラメータuに対応する補間値を取得するために、テクスチャロード命令tldのパラメータとして(u’,type)を与える。ここでu’はuの値に2テクセル分のオフセットを加えたものであり、このオフセットは、内分係数テクスチャ54のtypeで指定される行において、第1テクセルと第2テクセルを読み飛ばし、第3テクセルと第4テクセルの間で線形補間をするために必要となる。
【0086】
アドレス生成部74は、typeで指定された内分係数テクスチャ54の行の先頭アドレスに2テクセル分のオフセットを加算して参照アドレスを生成し、その参照アドレスから当該行の第3テクセルと第4テクセルを読み出し、線形補間部72に与える。これにより、第2および第3内分係数の始値の組(a01(0),a11(0),a02(0))と、第2および第3内分係数の終値の組(a01(1),a11(1),a02(1))が線形補間部72に入力される。
【0087】
線形補間部72は、パラメータuを補間係数として、第2および第3内分係数の始値(a01(0),a11(0),a02(0))と終値(a01(1),a11(1),a02(1))をu:(1−u)の比で内分した値(a01(u),a11(u),a02(u))を出力する。内挿演算部34は、テクスチャロード命令tldの返値として、指定したパラメータuに対応する内分係数の補間値(a01(u),a11(u),a02(u))を取得する。
【0088】
ステップS16の処理を擬似コードで書くと、次のようになる。
u方向について、補間された6つの係数をロード:
tld(u,type)=>a00(u),a10(u),a20(u)
u+2=>u’
tld(u’,type)=>a01(u),a11(u),a02(u)
ここで、=>は、左辺の演算命令の結果が右辺であることを示す。
【0089】
図9に戻り、内挿演算部34は、テクスチャロード命令を実行し、ステップS16で取得した第1内分係数の補間値a00(u)、a10(u)、a20(u)にもとづいた比でu方向に内挿された制御点をロードする(S18)。テクスチャユニット70は、内挿演算部34によるテクスチャロード命令の実行を受けて、制御点テクスチャ52の指定された参照行からu方向の4つの制御点の内、隣接する2つの制御点を順に取得し、線形補間部72に与える。線形補間部72は、第1内分係数の補間値a00(u)、a10(u)、a20(u)にもとづいた内分比で隣接する2つの制御点を内分し、内分された制御点を内挿演算部34にテクスチャロード命令の結果として返す。
【0090】
図11は、テクスチャロード命令により、制御点が内挿される様子を説明する図である。制御点テクスチャ52の各行には処理対象のパッチに対して指定された16個の制御点のデータが格納されている。ここでは、u方向のP0〜P3の4つの制御点に対する処理を説明する。u方向の他の4つの制御点P4〜P7、P8〜P11、P12〜P15についても、制御点テクスチャ52から読み出すテクセルを4つずつオフセットしていけば、処理としては同じである。
【0091】
制御点テクスチャ52の参照行sの第1〜第4テクセルには、4つの制御点P0〜P3の座標値が格納されている。内挿演算部34が、テクスチャユニット70に対して、テクスチャロード命令tldのパラメータとして(a00,s)を与える。
【0092】
アドレス生成部74は、制御点テクスチャ52の参照行sの先頭アドレスを参照アドレスとして生成し、その参照アドレスから当該行の第1テクセルと第2テクセルを読み出し、線形補間部72に与える。これにより、最初の2つの隣接する制御点P0とP1の座標値が線形補間部72に入力される。
【0093】
線形補間部72は、入力された2つの制御点P0とP1を第1内分係数a00にもとづく比a00:(1−a00)で内分した点P01の座標値を計算し、出力する。内挿演算部34は、テクスチャロード命令tldの返値として、第1内分係数の補間値a00(t)にもとづく内分比であらかじめ内分された制御点P01の座標値を取得する。
【0094】
次に、内挿演算部34は、テクスチャユニット70に対して、テクスチャロード命令tldのパラメータとして(a10’,s)を与える。ここでa10’はa10の値に1テクセル分のオフセットを加えたものであり、このオフセットは、制御点テクスチャ52の参照行sにおいて、第1テクセルを読み飛ばし、第2テクセルと第3テクセルの間で線形補間をするために必要となる。
【0095】
アドレス生成部74は、制御点テクスチャ52の参照行sの先頭アドレスに1テクセル分のオフセットを加算して参照アドレスを生成し、その参照アドレスから当該行の第2テクセルと第3テクセルを読み出し、線形補間部72に与える。これにより、次の2つの隣接する制御点P1とP2の座標値が線形補間部72に入力される。
【0096】
線形補間部72は、入力された2つの制御点P1とP2を第1内分係数a10にもとづく比a10:(1−a10)で内分した点P12の座標値を計算し、出力する。内挿演算部34は、テクスチャロード命令tldの返値として、第1内分係数の補間値a10(t)にもとづく内分比であらかじめ内分された制御点P12の座標値を取得する。
【0097】
さらに、内挿演算部34は、テクスチャユニット70に対して、テクスチャロード命令tldのパラメータとして(a20’,s)を与える。ここで、a20’はa20の値に2テクセル分のオフセットを加えたものであり、このオフセットは、制御点テクスチャ52の参照行sにおいて、第1、第2テクセルを読み飛ばし、第3テクセルと第4テクセルの間で線形補間をするために必要となる。
【0098】
アドレス生成部74は、制御点テクスチャ52の参照行sの先頭アドレスに2テクセル分のオフセットを加算して参照アドレスを生成し、その参照アドレスから当該行の第3テクセルと第4テクセルを読み出し、線形補間部72に与える。これにより、さらに次の2つの隣接する制御点P2とP3の座標値が線形補間部72に入力される。
【0099】
線形補間部72は、入力された2つの制御点P2とP3を第1内分係数a20にもとづく比a20:(1−a20)で内分した点P23の座標値を計算し、出力する。内挿演算部34は、テクスチャロード命令tldの返値として、第1内分係数の補間値a20(t)にもとづく内分比であらかじめ内分された制御点P23の座標値を取得する。
【0100】
ステップS18の処理の擬似コードは次のようになる。
補間された3つの制御点をロード:
tld(a00,s)=>P01xyz
a10+1−>a10’
tld(a10’,s)=>P12xyz
a20+2−>a20’
tld(a20’,s)=>P23xyz
【0101】
再び図9を参照する。内挿演算部34は、こうしてあらかじめ内挿された制御点を第2内分係数の補間値a01(u)、a11(u)にもとづいた比でu方向に内挿演算し、さらにその結果を第3内分係数の補間値a02(u)にもとづいた比でu方向に内挿演算する(S20)。この内挿計算は、内挿演算部34においてレジスタを用いた演算処理にて行われる。内挿演算部34は、3回の内挿演算の結果をストア命令stによりレジスタに書き込む。
【0102】
ステップS20の処理の擬似コードは次のようになる。
x座標を計算:
P01x+a01(P12x−P01x)=>P012x
P12x+a11(P23x−P12x)=>P123x
P012x+a02(P123x−P012x)=>P0123x
y座標を計算:
P01y+a01(P12y−P01y)=>P012y
P12y+a11(P23y−P12y)=>P123y
P012y+a02(P123y−P012y)=>P0123y
z座標を計算:
P01z+a01(P12z−P01z)=>P012z
P12z+a11(P23z−P12z)=>P123z
P012z+a02(P123z−P012z)=>P0123z
座標値をストア:
st P0123x
st P0123y
st P0123z
【0103】
次に、内挿演算部34は、パラメータvを補間係数とするテクスチャロード命令により、パラメータvに対応する第1、第2および第3内分係数の補間値bij(v)をロードする(S22)。テクスチャユニット70は、u方向の場合と同様に、内挿演算部34によるテクスチャロード命令を受けて、ステップS12で指定されたv方向のノットパターンのタイプに対応する内分係数テクスチャ54の行から内分係数の始値bij(0)および終値bij(1)を読み出し、パラメータvにもとづく比v:1−vで内分係数の始値bij(0)と終値bij(1)を内分することにより、パラメータvに対応する内分係数の補間値bij(v)を求め、内挿演算部34に内分係数の補間値bij(v)をテクスチャロード命令の結果として返す。
【0104】
ステップS22の演算の擬似コードは次のようになる。
v方向について、補間された6つの係数をロード:
tld(v,type)=>b00(v),b10(v),b20(v)
v+2=>v’
tld(v’,type)=>b01(v),b11(v),b02(v)
【0105】
内挿演算部34は、u方向に再帰的に3回内挿された制御点をロード命令ldによりレジスタから読み出し、そのu方向に内挿された後の制御点を、ステップS22で求めた第1、第2および第3内分係数の補間値bij(v)にもとづいた比でさらにv方向に再帰的に3回内挿演算する(S24)。v方向の内挿演算は、u方向の内挿演算と同様に行われる。ただし、u方向の1回目の内挿演算は、テクスチャユニット70の線形補間機能を用いて行われたが、v方向の内挿演算は、3回とも内挿演算部34においてレジスタに中間結果を保持しながら行われる。
【0106】
なお、一般に、NURBS曲面のパッチのu方向、v方向でノットパターンは異なるから、u方向の内挿演算に使われる第1、第2および第3内分係数aij(u)とv方向の内挿演算に使われる第1、第2および第3内分係数bij(v)は独立であり、u方向とv方向で異なるノットパターンのタイプに対応する内分係数が使われる。
【0107】
ステップS24において、最終的に2次元パラメータ座標値(u,v)に対応するパラメトリック曲面の点が得られる。内挿演算部34は、ストア命令stにより、得られたパラメトリック曲面の点をレジスタに保持する。
【0108】
ステップS24の処理の擬似コードは次のようになる。
u方向に計算された4つの制御点をロード:
ld P0x ld P0y ld P0z
ld P1x ld P1y ld P1z
ld P2x ld P2y ld P2z
ld P3x ld P3y ld P3z
【0109】
x座標を計算:
P0x+b00(P1x−P0x)=>P01x
P1x+b10(P2x−P1x)=>P12x
P2x+b20(P3x−P2x)=>P23x
P01x+b01(P12x−P01x)=>P012x
P12x+b11(P23x−P12x)=>P123x
P012x+b02(P123x−P012x)=>P0123x
【0110】
y座標を計算:
P0y+b00(P1y−P0y)=>P01y
P1y+b10(P2y−P1y)=>P12y
P2y+b20(P3y−P2y)=>P23y
P01y+b01(P12y−P01y)=>P012y
P12y+b11(P23y−P12y)=>P123y
P012y+b02(P123y−P012y)=>P0123y
【0111】
z座標を計算:
P0z+b00(P1z−P0z)=>P01z
P1z+b10(P2z−P1z)=>P12z
P2z+b20(P3z−P2z)=>P23z
P01z+b01(P12z−P01z)=>P012z
P12z+b11(P23z−P12z)=>P123z
P012z+b02(P123z−P012z)=>P0123z
【0112】
座標値をストア:
st P0123x
st P0123y
st P0123z
【0113】
頂点データ出力部36は、得られたパラメトリック曲面の点の座標値をメッシュの頂点座標値として、2次元パラメータ座標値(u,v)に対応づけて出力する(S26)。
【0114】
図12(a)〜(j)は、パラメトリック曲面のu方向、v方向に制御点を内挿して、2次元パラメータ座標値(u,v)に対応するパラメトリック曲面の点およびその点における接線を求める手順を模式的に示す図である。
【0115】
図12(a)は、パラメトリック曲面のパッチに対して定義された16個の制御点を示す。ここでは、同図の縦方向をu軸、横方向をv軸に取り、u方向に4つの制御点P0[j]、P1[j]、P2[j]、P3[j]を示す。[]内の添え字jは、v方向の列番号を示し、j=0〜3である。
【0116】
図12(b)は、図12(a)の16個の制御点に対して、u方向の1回目の内挿演算を施した結果を示す。u方向の1回目の内挿演算により、u方向に並ぶ各列4個の制御点P0[j]、P1[j]、P2[j]、P3[j]は、第1内分係数a00、a10、a20により内分され、各列3個ずつの内分点P01[j]、P12[j]、P23[j]が得られる。このu方向の1回目の内挿演算は、テクスチャユニット70の線形補間部72が、制御点テクスチャ52に格納された制御点を線形補間することにより行われる。
【0117】
図12(c)は、図12(b)の結果に対して、u方向の2回目の内挿演算を施した結果を示す。u方向の2回目の内挿演算により、u方向に並ぶ各列3個の内分点P01[j]、P12[j]、P23[j]は、第2内分係数a01、a11によりさらに内分され、各列2個ずつの内分点P012[j]、P123[j]が得られる。このu方向の2回目の内挿演算は、ピクセルシェーダ32の内挿演算部34により行われる。
【0118】
図12(d)は、図12(c)の結果に対して、u方向の3回目の内挿演算を施した結果を示す。u方向の3回目の内挿演算により、u方向に並ぶ各列2個の内分点P012[j]、P123[j]は、第3内分係数a02により内分され、各列1個ずつの制御点P0123[j]が得られる。このu方向の3回目の内挿演算も、内挿演算部34により行われる。
【0119】
図12(b)から(d)までの処理により、u方向の3回の内挿演算が完了し、v方向に並ぶ4個の内分点P0123[0]、P0123[1]、P0123[2]、P0123[3]が得られる。
【0120】
図12(e)は、図12(d)の結果に対して、v方向の1回目の内挿演算を施した結果を示す。v方向の1回目の内挿演算により、v方向に並ぶ4個の内分点P0123[0]、P0123[1]、P0123[2]、P0123[3]は、第1内分係数b00、b10、b20により内分され、3個の内分点P0123_01、P0123_12、P0123_23が得られる。このv方向の1回目の内挿演算は、内挿演算部34により行われる。
【0121】
図12(f)は、図12(e)の結果に対して、v方向の2回目の内挿演算を施した結果を示す。v方向の2回目の内挿演算により、v方向に並ぶ3個の内分点P0123_01、P0123_12、P0123_23は、第2内分係数b01、b11により内分され、2個の内分点P0123_012、P0123_123が得られる。このv方向の2回目の内挿演算も、内挿演算部34により行われる。
【0122】
図12(g)は、図12(f)の結果に対して、v方向の3回目の内挿演算を施した結果を示す。v方向の3回目の内挿演算により、v方向に並ぶ2個の内分点P0123_012、P0123_123は、3回目の内分係数b02により内分され、1個の内分点P0123_0123が得られる。このv方向の3回目の内挿演算も、内挿演算部34により行われる。
【0123】
図12(e)から(g)までの処理により、v方向の3回の内挿演算が完了し、最終的に1個の内分点P0123_123が得られる。これが2次元パラメータ座標値(u,v)に対応するパラメトリック曲面上の点である。
【0124】
最終的に得られた頂点P0123_123におけるu方向、v方向の接線を求めるには、図12(c)に示したu方向に2回の内挿演算を施した結果に対して、v方向に2回の内挿演算を施す。
【0125】
図12(h)は、図12(c)の結果に対して、v方向に1回目の内挿演算を施した結果を示す。このv方向の1回目の内挿演算により、1行目のv方向に並ぶ4個の内分点P012[0]、P012[1]、P012[2]、P012[3]は、第1内分係数b00、b10、b20により内分され、3個の内分点P012_01、P012_12、P012_23が得られる。同様に、2行目のv方向に並ぶ4個の内分点P123[0]、P123[1]、P123[2]、P123[3]は、第1内分係数b00、b10、b20により内分され、3個の内分点P123_01、P123_12、P123_23が得られる。このv方向の1回目の内挿演算は、内挿演算部34により行われる。
【0126】
図12(i)は、図12(h)の結果に対して、v方向に2回目の内挿演算を施した結果を示す。このv方向の2回目の内挿演算により、1行目のv方向に並ぶ3個の内分点P012_01、P012_12、P012_23は、第2内分係数b01、b11により内分され、2個の内分点P012_012、P012_123が得られる。同様に、2行目のv方向の並ぶ3個の内分点P123_01、P123_12、P123_23は、第2内分係数b01、b11により内分され、2個の内分点P123_012、P123_123が得られる。
【0127】
図12(j)は、図12(i)の結果から、図12(g)の頂点座標P0123_0123におけるu方向およびv方向の接線を求めた結果を示す。内挿演算部34は、図12(i)の4つの内分点の内、上側の2点P012_012、P123_012の中点U、下側の2点P123_012、P123_123の中点D、左側の2点P012_012、P123_012の中点L、右側の2点P012_123、P123_123の中点Rを求める。頂点座標P0123_0123におけるu方向の接線ベクトルは、上側の中点Uと下側の中点Dの差分ベクトルで与えられ、v方向の接線ベクトルは、左側の中点Lと右側の中点Rの差分ベクトルで与えられる。
【0128】
以下、NURBS曲面のノットパターンは、隣接するパッチの接続性を考慮すると9種類に限定することができること、およびNURBS曲面の制御点を内挿演算するときに用いられる内分係数がパラメータtの1次式で表されることについて詳しく説明する。
【0129】
NURBS曲面は、2つのパラメータu、vを媒介変数としたパラメトリック曲面であり、パラメトリック曲面のパッチの形状は、16個の制御点P0〜P15と、パラメータu、vの変化に伴う各制御点の影響力の変化を表す節点(ノット)の列であるノットベクトルによって操作される。パラメトリック曲面をu方向またはv方向で見た場合、パラメータuまたはvを媒介変数としたパラメトリック曲線と見ることができ、パラメトリック曲線のセグメントの形状は、u方向またはv方向の4個の制御点とノットベクトルによって操作される。
【0130】
パラメトリック曲面をパッチ毎に生成し、隣り合うパッチをつなぎ合わせることで1つの曲面を形成するが、パッチのつなぎ目において滑らかな連続性を確保するために、各パッチのu、v方向のそれぞれに適用すべきノットベクトルを定める。本実施の形態では、隣接パッチ間の接続性を考慮してパッチに適用するノットパターンを9種類に限定している。すなわち、任意のNURBS曲面を用いるのではなく、9種類のノットパターンで決まるNURBS曲面で描画対象オブジェクトの自由曲面をモデル化する。
【0131】
パラメトリック曲面をu、vいずれかの方向で見ると、パラメトリック曲線として考えることができるため、ここではパラメトリック曲線のノットパターンを説明する。ノットパターンはu方向、v方向に独立に指定することができる。
【0132】
4階すなわち3次のBスプライン曲線の場合、1セグメントは4つの制御点で定義される。5つの制御点でBスプライン曲線を定義する場合は2セグメント、6つの制御点でBスプライン曲線を定義する場合は3セグメントとなる。
【0133】
1つのセグメントに対して、9つのタイプのノットパターンのいずれかを用いる。曲線の形状を決める制御点の数によって、隣接セグメント間の接続性を考慮して、使用すべきノットパターンのタイプと順序を定める。
【0134】
隣接セグメント間を接続性を考慮する場合、セグメントの端点における滑らかな連続性が問題となる。1つのセグメントに注目したとき、セグメントの端点が制御点と一致する場合、その端点はオープンであるといい、一致しない場合はクローズであるという。さらに、曲線の接続性を考慮して、注目しているセグメントの前後に隣接するセグメントの端点が制御点と一致しているかどうか、すなわちオープンであるか、クローズであるかを区別する。さらに、注目セグメントの端点がクローズである場合、その端点を共有して接続している隣接セグメントの端点のオープン/クローズを考慮に入れ、その注目セグメントのノットパターンを決める。
【0135】
セグメントの接続関係を、注目セグメントの始点および終点のオープン/クローズと、その注目セグメントの始点側に隣接するセグメントの始点のオープン/クローズと、その注目セグメントの終点側に隣接するセグメントの終点のオープン/クローズの組み合わせによって、「(始点側隣接セグメントの始点のオープン/クローズ):(注目セグメントの始点のオープン/クローズ)−(注目セグメントの終点のオープン/クローズ):(終点側隣接セグメントの終点のオープン/クローズ)」の形式で表すことにする。
【0136】
図13(a)〜(c)は、制御点が4個、5個、および6個の場合のノットパターンについて説明する図である。
【0137】
図13(a)は、4個の制御点Q0〜Q3でNURBS曲線を定義する際に使用されるノットパターンであり、これをタイプ2とする。セグメントの始点、終点はそれぞれ制御点Q0、Q3に一致しており、オープンである。このノットパターンはベジェ曲線に一致する。
【0138】
図13(b)は、5個の制御点Q0〜Q4でNURBS曲線を定義する際に使用されるノットパターンを示す。この場合、NURBS曲線は第1、第2のセグメントを接続点E1でつなげて表される。
【0139】
第1セグメントの始点は制御点Q0に一致しており、オープンである。一方、第1セグメントの終点は、第2セグメントの始点と一致することで連続性が保たれており、いずれの制御点とも一致しないので、クローズである。また、第1セグメントの終点側隣接セグメントである第2セグメントの終点は、制御点Q4と一致し、オープンである。したがって、第1セグメントの接続関係は「オープン−クローズ:オープン」で表される。これをタイプ3とする。
【0140】
第2セグメントの始点は、第1セグメントの終点と接続し、いずれの制御点とも一致しないから、クローズであり、第2セグメントの終点は、制御点Q4に一致し、オープンである。第2セグメントの始点側隣接セグメントである第1セグメントの始点は、制御点Q0と一致し、オープンである。したがって、第2セグメントの接続関係は「オープン:クローズ−オープン」で表される。これをタイプ7とする。
【0141】
図13(c)は、6個の制御点Q0〜Q5でNURBS曲線を定義する際に使用されるノットパターンを示す。この場合、NURBS曲線は第1、第2、第3のセグメントを2つの接続点E1、E2でつなげて表される。
【0142】
第1セグメントの始点は制御点Q0に一致し、オープンであり、第1セグメントの終点は、第2セグメントの始点と接続し、いずれの制御点とも一致せず、クローズである。第1セグメントの終点側隣接セグメントである第2セグメントの終点は、いずれの制御点とも一致せず、クローズである。したがって、第1セグメントの接続関係は「オープン−クローズ:クローズ」で表される。これをタイプ4とする。
【0143】
第2セグメントの始点は、第1セグメントの終点と接続し、いずれの制御点とも一致せず、クローズであり、第2セグメントの終点は、第3セグメントの始点と接続し、いずれの制御点とも一致せず、クローズである。また、第2セグメントの始点側隣接セグメントである第1セグメントの始点は、制御点Q0に一致し、オープンであり、第2セグメントの終点側隣接セグメントである第3セグメントの終点は、制御点Q5に一致し、オープンである。したがって、第2セグメントの接続関係は「オープン:クローズ−クローズ:オープン」で表される。これをタイプ5とする。
【0144】
第3セグメントの始点は、第2セグメントの終点と接続し、いずれの制御点とも一致せず、クローズであり、第3セグメントの終点は、制御点Q5に一致し、オープンである。また、第3セグメントの始点側隣接セグメントである第2セグメントの始点は、クローズである。したがって、第3セグメントの接続関係は「クローズ:クローズ−オープン」で表される。これをタイプ6とする。
【0145】
図14(a)〜(c)は、制御点が7個、8個、および9個以上の場合のノットパターンについて説明する図である。
【0146】
図14(a)は、7個の制御点Q0〜Q6でNURBS曲線を定義する際に使用されるノットパターンを示す。この場合、NURBS曲線は第1〜第4のセグメントを3つの接続点E1〜E3でつなげて表される。
【0147】
第1セグメントは既に説明したタイプ4である。
【0148】
第2セグメントの始点は、第1セグメントの終点と接続し、いずれの制御点とも一致せず、クローズであり、第2セグメントの終点は、第3セグメントの始点と接続し、いずれの制御点とも一致せず、クローズである。また、第2セグメントの始点側隣接セグメントである第1セグメントの始点は、制御点Q0に一致し、オープンであり、第2セグメントの終点側隣接セグメントである第3セグメントの終点は、いずれの制御点とも一致せず、クローズである。したがって、第2セグメントの接続関係は「オープン:クローズ−クローズ:クローズ」で表される。これをタイプ8とする。
【0149】
第3セグメントの始点は、第2セグメントの終点と接続し、いずれの制御点とも一致せず、クローズであり、第3セグメントの終点は、第4セグメントの始点と接続し、いずれの制御点とも一致せず、クローズである。また、第3セグメントの始点側隣接セグメントである第2セグメントの始点は、クローズであり、第3セグメントの終点側隣接セグメントである第4セグメントの終点は、制御点Q6に一致し、オープンである。したがって、第3セグメントの接続関係は「クローズ:クローズ−クローズ:オープン」で表される。これをタイプ9とする。
【0150】
第4セグメントは既に説明したタイプ6である。
【0151】
図14(b)は、8個の制御点Q0〜Q7でNURBS曲線を定義する際に使用されるノットパターンを示す。この場合、NURBS曲線は第1〜第5のセグメントを4つの接続点E1〜E4でつなげて表される。
【0152】
第1セグメントは既に説明したタイプ4、第2セグメントはタイプ8である。
【0153】
第3セグメントの始点は、第2セグメントの終点と接続し、いずれの制御点とも一致せず、クローズであり、第3セグメントの終点は、第4セグメントの始点と接続し、いずれの制御点とも一致せず、クローズである。また、第3セグメントの始点側隣接セグメントである第2セグメントの始点は、クローズであり、第3セグメントの終点側隣接セグメントである第4セグメントの終点は、いずれの制御点とも一致せず、クローズである。第1セグメントの接続関係は「クローズ:クローズ−クローズ:クローズ」で表される。これをタイプ1とする。
【0154】
第4セグメントは既に説明したタイプ9、第5セグメントはタイプ6である。
【0155】
図14(c)は、9個以上の制御点、ここでは10個の制御点Q0〜Q9でNURBS曲線を定義する際に使用するノットパターンを示す。この場合、NURBS曲線は第1〜第7のセグメントを6個の接続点E1〜E6でつなげて表される。一般に、n個の制御点が与えられたとき、NURBS曲線は(n−3)個のセグメントをつなげて表される。
【0156】
この場合、第1〜第7のセグメントは、順にタイプ4、タイプ8、タイプ1、タイプ1、タイプ1、タイプ9、タイプ6になる。このように、9個以上の制御点の場合、中央にタイプ1のセグメントが挿入して接続することになる。
【0157】
図15に、図13(a)〜(c)および図14(a)〜(c)で述べたノットパターンのタイプ1〜9について、セグメントの接続関係をまとめる。このように注目セグメントの端点のオープン/クローズと、隣接セグメントの端点のオープン/クローズによって、ノットパターンが9種類に分けられる。
【0158】
図16(a)〜(c)は、パラメトリック曲面に対してu方向、v方向に適用されるノットパターンのタイプを説明する図である。
【0159】
図16(a)は、u方向に4個の制御点、v方向に5個の制御点が設けられた連続するパラメトリック曲面の模式図である。このパラメトリック曲面のu方向は、図13(a)に示した4個の制御点の場合に相当するから、u方向にはタイプ2のノットパターンが適用される。一方、パラメトリック曲面のv方向は、図13(b)に示した5個の制御点の場合に相当するから、v方向の1つ目のセグメントにはタイプ3のノットパターンが適用され、2つ目のセグメントにはタイプ7のノットパターンが適用される。
【0160】
図16(b)は、u方向に8個の制御点、v方向に6個の制御点が設けられた連続するパラメトリック曲面の模式図である。このパラメトリック曲面のu方向は、図14(b)に示した8個の制御点の場合に相当するから、u方向の各セグメントにはタイプ4、8、1、9、6の順でノットパターンが適用される。一方、パラメトリック曲面のv方向は、図13(c)に示した6個の制御点の場合に相当するから、各セグメントにはタイプ4、5、6の順でノットパターンが適用される。
【0161】
図16(c)は、u、v方向の制御点の個数によって、適用されるノットパターンのタイプの順序をまとめた表である。ラスタライザ10は、この表を用いて、パラメトリック曲面のu方向およびv方向の制御点の個数により、u方向、v方向のそれぞれの各セグメントに適用されるノットパターンのタイプの順序を決定する。決定されたノットパターンのタイプは、各パッチのパラメータ情報としてシェーダユニット30に与えられる。
【0162】
次に、NURBS曲面の制御点を内分するための内分係数が1次式で与えられることを説明する。
【0163】
まず、Bスプライン曲線について説明する。M階すなわち(M−1)次のBスプライン曲線の式P(t)は、制御点Q0,Q1,…,Qnを用いて、
P(t)=N0,M(t)Q0+N1,M(t)Q1+…+Nn,4(t)Qn
と書ける。
【0164】
ここで、N0,M,N1,M,…,Nn,Mは、Bスプライン基底関数であり、混ぜ合わせ関数とも呼ばれる。Bスプライン基底関数Nj,Mは、次のドゥ・ブァ・コックス(de Boor Cox)の漸化式により再帰的に求めることができる。
【0165】
Nj,M(t)=(t−tj)/(tj+M−1−tj)・Nj,M−1(t)+(tj+M−t)/(tj+M−tj+1)・Nj+1,M−1(t)
ただし、Nj,1(t)=1(tj≦t<tj+1),Nj,1(t)=0(それ以外)である。
【0166】
この漸化式に現れるtj,tj+Mなどは、パラメータtの節目すなわちノットである。Bスプライン基底関数あるいは混ぜ合わせ関数Nj,Mは、ノットを数値の列で表した次のノットベクトルTにもとづいて定められる。
T=[t0,t1,…,tM+N−1]
ここで、Nは制御点数、Mは階数である。ノットベクトルの要素数は、制御点数Nと階数Mの和である。
【0167】
ノットベクトルTのノット間隔が一定である場合には、ユニフォームであるといい、ノット間隔が一定でない場合は、ノンユニフォームであるという。
【0168】
ノンユニフォームで有理化されたBスプライン曲線がNURBS曲線である。NURBS曲線では、ノットベクトルTのノット間隔が可変であるため、ノット間隔の比で曲線の微分係数を補正することができ、曲線の形状を制御するのが容易であり、また、曲線の形状を局所的に変化させることも可能である。また、NURBS曲線は、Bスプライン曲線以外にもベジェ曲線、エルミート曲線などの曲線も表現することができ、いろいろな曲線を同一形式で表せるという利点もある。さらに、NURBSでは、有理化すなわち同次座標を用いた中心投影が行われているため、制御点に対する重みを設定することができ、有利化されていないBスプライン曲線では表現することができない真円なども表現することができる。
【0169】
また、混ぜ合わせ関数の値を求めるための上記のドゥ・ブァ・コックスの漸化式は、再帰的に演算できるため、コンピュータのレジスタや演算器などのハードウエア資源を用いて繰り返し計算するのに適している。
【0170】
本実施の形態では、4つの制御点で定まる4階すなわち3次のBスプライン曲線を扱うから、M=4、N=4の場合を考えればよい。たとえば、制御点数が4個で4階のユニフォームなBスプライン曲線のノットベクトルTはT=[−3,−2,−1,0,1,2,3,4]で与えられる。
【0171】
図17は、階数Mが4、制御点数Nが4のBスプライン曲線について、ドゥ・ブァ・コックスの漸化式により、Bスプライン基底関数を計算する過程を説明する図である。
【0172】
セグメントのパラメータtは、[0,1]の区間で変化し、9タイプのノットパターンのノットベクトルTは、すべてT=[*,*,*,0,1,*,*,*]と定義する。ここで*はタイプにより異なる値である。この場合、いずれのノットパターンのタイプでも、1階のBスプライン基底関数はNj,1=[0,0,0,1,0,0,0]である。
【0173】
ドゥ・ブァ・コックスの漸化式によれば、M階のj番目のBスプライン基底関数Nj,Mは、(M−1)階のj番目のBスプライン基底関数Nj,M−1と(M−1)階の(j+1)番目のBスプライン基底関数Nj+1,M−1を混ぜ合わせたものであるから、1階のBスプライン基底関数はNj,1=[0,0,0,1,0,0,0]を起点として、2階、3階、4階と順に計算していくことで、4階までのBスプライン基底関数をすべて求めることができる。同図は、この計算過程を表したものである。
【0174】
たとえば、2階のBスプライン基底関数は1階のBスプライン基底関数を用いて、
N2,2(t)=0+(t4−t)/(t4−t3)・N3,1(t)
N3,2(t)=(t−t3)/(t4−t3)・N3,1(t)+0
などと計算される。
【0175】
同様に、3階のBスプライン基底関数は2階のBスプライン基底関数を用いて、
N1,3(t)=0+(t4−t)/(t4−t2)・N2,2(t)
N2,3(t)=(t−t2)/(t4−t2)・N2,2(t)+(t5−t)/(t5−t3)・N3,2(t)
N3,3(t)=(t−t3)/(t5−t3)・N3,2(t)+0
などと計算される。
【0176】
ここで、ドゥ・ブァ・コックスの漸化式において、(M−1)階のj番目のBスプライン基底関数Nj,M−1と(M−1)階の(j+1)番目のBスプライン基底関数Nj+1,M−1を混ぜ合わせるときの混ぜ合わせ係数を説明の簡単のため、次のようにおく。
Aj,M=(t−tj)/(tj+M−1−tj)
Bj,M=(tj+M−t)/(tj+M−tj+1)
【0177】
混ぜ合わせ係数Aj,M、Bj,Mを用いれば、ドゥ・ブァ・コックスの漸化式は次のように書ける。
Nj,M(t)=Aj,M、・Nj,M−1(t)+Bj,M・Nj+1,M−1(t)
【0178】
図18は、図17の計算過程を混ぜ合わせ係数Aj,M、Bj,Mを用いて書き換えたものである。この計算過程によれば、Bスプライン基底関数は次の漸化式で求められる。
【0179】
4階のBスプライン基底関数を求める漸化式:
N0,4(t)=B0,4N1,3(t)
N1,4(t)=A1,4N1,3(t)+B1,4N2,3(t)
N2,4(t)=A2,4N2,3(t)+B2,4N3,3(t)
N3,4(t)=A3,4N3,3(t)
【0180】
3階のBスプライン基底関数を求める漸化式:
N1,3(t)=B1,3N2,2(t)
N2,3(t)=A2,3N2,2(t)+B2,3N3,2(t)
N3,3(t)=A3,3N3,2(t)
【0181】
2階のBスプライン基底関数を求める漸化式:
N2,2(t)=B2,2N3,1(t)
N3,2(t)=A3,2N3,1(t)
【0182】
1階のBスプライン基底関数は、
N3,1(t)=1である。
【0183】
Bスプライン曲線の式P(t)に、上記の4階のBスプライン基底関数を求める漸化式を適用すると、次のように変形できる。
P(t)=Q0N0,4(t)+Q1N1,4(t)+Q2N2,4(t)+Q3N3,4(t)
=Q0{B0,4N1,3(t)}
+Q1{A1,4N1,3(t)+B1,4N2,3(t)}
+Q2{A2,4N2,3(t)+B2,4N3,3(t)}
+Q3{A3,4N3,3(t)}
=N1,3(t){Q0B0,4+Q1A1,4}
+N2,3(t){Q1B1,4+Q2A2,4}
+N3,3(t){Q2B2,4+Q3A3,4}
【0184】
ここで、B0,4+A1,4=(t4−t)/(t4−t1)+(t−t1)/(t4−t1)=1であることに注意すると、Q0B0,4+Q1A1,4は、2点Q0、Q1をA1,4:B0,4の比で内分する点Q01を求める演算であることがわかる。
【0185】
一般的には、Bj,M+Aj+1,M=(tj+M−t)/(tj+M−tj+1)+(t−tj+1)/(tj+M−tj+1)=1であるから、Q1B1,4+Q2A2,4は、2点Q1、Q2をA2,4:B1,4の比で内分する点Q12を求める演算であり、Q2B2,4+Q3A3,4は、2点Q2、Q3をA3,4:B2,4の比で内分する点Q23を求める演算である。
【0186】
したがって、式P(t)は、内分点Q01、Q12、Q23を用いて、
P(t)=N1,3(t)Q01+N2,3(t)Q12+N3,3(t)Q23
と書くことができる。
【0187】
さらに、この式に、3階のBスプライン基底関数を求める漸化式を適用すると、次のように変形できる。
P(t)=Q01{B1,3N2,2(t)}
+Q12{A2,3N2,2(t)+B2,3N3,2(t)}
+Q23{A3,3N3,2(t)}
=N2,2(t){Q01B1,3+Q12A2,3}
+N3,2(t){Q12B2,3+Q23A3,3}
【0188】
ここで、Q01B1,3+Q12A2,3は、2点Q01、Q12をA2,3:B1,3の比で内分する点Q012を求める演算であり、Q12B2,3+Q23A3,3は、2点Q12、Q23をA3,3:B2,3の比で内分する点Q123を求める演算である。
【0189】
したがって、式P(t)は、内分点Q012、Q123を用いて、
P(t)=N2,2(t)Q012+N3,2(t)Q123
と書くことができる。
【0190】
さらに、この式に、2階のBスプライン基底関数を求める漸化式を適用すると、次のように変形できる。
P(t)=Q012B2,2N3,1(t)+Q123A3,2N3,1(t)
=N3,1(t){Q012B2,2+Q123A3,2}
【0191】
ここで、Q012B2,2+Q123A3,2は、2点Q012、Q123をA3,2:B2,2の比で内分する点Q0123を求める演算である。
【0192】
したがって、式P(t)は、内分点Q0123を用いて、
P(t)=N3,1(t)Q0123
と書くことができる。ここで、1階のBスプライン基底関数N3,1(t)は1であるから、P(t)=Q0123である。
【0193】
以上のことから、4つの制御点Q0、Q1、Q2、Q3に対して、隣り合う点の間で内分計算を再帰的に3回繰り返すことにより、4階のBスプライン曲線のパラメータtに対応する点P(t)を求められることがわかる。
【0194】
すなわち、1回目の内分計算では、4つの制御点Q0、Q1、Q2、Q3について、隣り合う制御点間で内分を計算し、3つの内分点Q01、Q12、Q23を求める。2回目は、その3つの内分点Q01、Q12、Q23について、隣り合う内分点間で内分を計算し、2つの内分点Q012、Q123を求める。3回目は、その2つの内分点Q012、Q123について内分を計算して、内分点Q0123を求める。3回目の内分計算の結果得られた内分点Q0123が点P(t)である。
【0195】
以上で説明した制御点を再帰点に内分することでBスプライン曲線上の点を求める方法は、ド・カステリョ(de Casteljau)のアルゴリズムとして知られている計算方法を応用したものである。ド・カステリョのアルゴリズムは、一般的にはベジェ曲線に対して知られている計算方法であるが、このように、ドゥ・ブァ・コックスの漸化式を変形することで、Bスプライン曲線に対してもド・カステリョのアルゴリズムを適用できることがわかる。
【0196】
4つの制御点Q0、Q1、Q2、Q3から4階のBスプライン曲線の点を求めるための漸化式をまとめると、次のようになる。
【0197】
1回目の内分計算:
Q01=(t4−t)/(t4−t1)・Q0+(t−t1)/(t4−t1)・Q1
Q12=(t5−t)/(t5−t2)・Q1+(t−t2)/(t5−t2)・Q2
Q23=(t6−t)/(t6−t3)・Q2+(t−t3)/(t6−t3)・Q3
【0198】
2回目の内分計算:
Q012=(t4−t)/(t4−t2)・Q01+(t−t2)/(t4−t2)・Q12
Q123=(t5−t)/(t5−t3)・Q12+(t−t3)/(t5−t3)・Q23
【0199】
3回目の内分計算:
Q0123=(t4−t)/(t4−t3)・Q012+(t−t3)/(t4−t3)・Q123
【0200】
ここで、内分係数を
a00(t)=(t−t1)/(t4−t1)
a10(t)=(t−t2)/(t5−t2)
a20(t)=(t−t3)/(t6−t3)
a01(t)=(t−t2)/(t4−t2)
a11(t)=(t−t3)/(t5−t3)
a02(t)=(t−t3)/(t4−t3)
とおくと、
【0201】
1回目の内分計算:
Q01=(1−a00(t))Q0+a00(t)Q1
Q12=(1−a10(t))Q1+a10(t)Q2
Q23=(1−a20(t))Q2+a20(t)Q3
【0202】
2回目の内分計算:
Q012=(1−a01(t))Q01+a01(t)Q12
Q123=(1−a11(t))Q12+a11(t)Q23
【0203】
3回目の内分計算:
Q0123=(1−a02(t))Q012+a02(t)Q123
と書ける。
【0204】
ノットパターンの各タイプに対して、ノットベクトルT=[t0,t1,…,t7]を次のように定義する。ただし、t0とt7は計算に関与しないため、任意の値でよい。また、各ノットベクトルTに対して定まる内分係数を示す。
【0205】
タイプ1:
ノットベクトルT=[−3,−2,−1,0,1,2,3,4]
このとき、内分係数は、a00(t)=(t+2)/3、a10(t)=(t+1)/3、a20(t)=t/3、a01(t)=(t+1)/2、a11(t)=t/2、a02(t)=tである。
【0206】
タイプ2:
ノットベクトルT=[0,0,0,0,1,1,1,1]
このとき、内分係数は、a00(t)=t、a10(t)=t、a20(t)=t、a01(t)=t、a11(t)=t、a02(t)=tである。
【0207】
タイプ3:
ノットベクトルT=[0,0,0,0,1,2,2,2]
このとき、内分係数は、a00(t)=t、a10(t)=t/2、a20(t)=t/2、a01(t)=t、a11(t)=t/2、a02(t)=tである。
【0208】
タイプ4:
ノットベクトルT=[0,0,0,0,1,2,3,4]
このとき、内分係数は、a00(t)=t、a10(t)=t/2、a20(t)=t/3、a01(t)=t、a11(t)=t/2、a02(t)=tである。
【0209】
タイプ5:
ノットベクトルT=[−1,−1,−1,0,1,2,2,2]
このとき、内分係数は、a00(t)=(t+1)/2、a10(t)=(t+1)/3、a20(t)=t/2、a01(t)=(t+1)/2、a11(t)=t/2、a02(t)=tである。
【0210】
タイプ6:
ノットベクトルT=[−3,−2,−1,0,1,1,1,1]
このとき、内分係数は、a00(t)=(t+2)/3、a10(t)=(t+1)/2、a20(t)=t、a01(t)=(t+1)/2、a11(t)=t、a02(t)=tである。
【0211】
タイプ7:
ノットベクトルT=[−1,−1,−1,0,1,1,1,1]
このとき、内分係数は、a00(t)=(t+1)/2、a10(t)=(t+1)/2、a20(t)=t、a01(t)=(t+1)/2、a11(t)=t、a02(t)=tである。
【0212】
タイプ8:
ノットベクトルT=[−1,−1,−1,0,1,2,3,4]
このとき、内分係数は、a00(t)=(t+1)/2、a10(t)=(t+1)/3、a20(t)=t/3、a01(t)=(t+1)/2、a11(t)=t/2、a02(t)=tである。
【0213】
タイプ9:
ノットベクトルT=[−3,−2,−1,0,1,2,2,2]
このとき、内分係数は、a00(t)=(t+2)/3、a10(t)=(t+1)/3、a20(t)=t/2、a01(t)=(t+1)/2、a11(t)=t/2、a02(t)=tである。
【0214】
図19にノットパターンのタイプ毎の内分係数をまとめて示す。このように内分係数は、すべてtの一次式で表される。テセレーション処理の際、パラメトリック曲線のパッチの分割数に応じて、パラメータtは[0,1]の区間で所定の間隔で離散的な値を取る。Bスプライン曲線上の点を求めるために、パラメータtの離散値のすべてについて、内分係数aij(t)の値が計算上必要となる。しかし、パラメータtの離散値のすべてについて内分係数aij(t)の値を用意しておかなくても、内分係数aij(t)がパラメータtの一次式で表されることから、t=0、1のときの内分係数の始値aij(0)、終値aij(1)の2つを記憶しておけば、任意のt(0<t<1)の値に対するaij(t)は、始値aij(0)と終値aij(1)をt:(1−t)の比で線形補間することにより、求めることができる。本実施の形態では、この性質がテクスチャユニット70において有効に利用されている。
【0215】
以上述べたように、本実施の形態によれば、パラメトリック曲面の制御点の再帰的内挿演算に必要な必要な内分計算の一部を、テクスチャユニット70の線形補間器を利用して実行するため、ピクセルシェーダ32の演算器を用いてすべての内分計算を行う場合に比べて、描画処理装置100全体の処理効率が向上する。
【0216】
また、2次元パラメータ座標値に依存して変化する内分係数の始値および終値だけをテクスチャとして保持しておくことにより、任意の2次元パラメータ座標値における内分係数をテクスチャの補間計算により効率良く取得することができる。また、内分係数の始値および終値だけをテクスチャに格納すればよいので、テセレーション処理に必要なメモリ量を少なく抑えることができる。また、パラメトリック曲面の制御点についても、テクスチャとして保持しておくことで、最初の内挿演算をテクスチャの補間計算により効率良く行うことができる。
【0217】
以上、本発明を実施の形態をもとに説明した。実施の形態は例示であり、それらの各構成要素や各処理プロセスの組合せにいろいろな変形例が可能なこと、またそうした変形例も本発明の範囲にあることは当業者に理解されるところである。そのような変形例を説明する。
【0218】
上記の説明では、2次元パラメータ座標系で定義されるパラメトリック曲面をパッチ毎にメッシュ状に細分化するテセレーション処理を説明したが、1次元パラメータ座標系で定義されるパラメトリック曲線をセグメント毎に折れ線で細分化するテセレーション処理も同様に行うことができる。パラメトリック曲線をテセレーション処理する場合は、ラスタライザ10には描画プリミティブとしてラインプリミティブを与えればよい。
【0219】
また、上記の説明では、パラメータtに依存する内分係数の始値aij(0)と終値aij(1)を線形補間して、指定されたパラメータtにおける内分係数aij(t)の値を求めたが、内分係数aij(t)はパラメータtの1次式であるから、始値と終値の組に限らず、任意の異なる2つのパラメータ値t1,t2における内分係数aij(t1)、aij(t2)を代表値として内分係数テクスチャ54に記憶しておき、これらの代表値を線形補間することにより、指定されたパラメータtにおける内分係数aij(t)の値を求めてもよい。なお、この線形補間には、内挿だけでなく、外挿も含まれる。
【0220】
また、実施の形態では、制御点に対するu方向の最初の内挿演算だけをテクスチャユニット70の線形補間機能を用いて行ったが、2回目、3回目の内挿演算についてもテクスチャユニット70の線形補間機能を用いて行ってもよい。その場合、ピクセルシェーダ32が、テクスチャユニット70から第1内分係数であらかじめ内分された制御点を受け取った後、その内分された制御点をテクスチャユニット70に投入することのできるインタフェースを設ける。テクスチャユニット70は、線形補間器により、ピクセルシェーダ32から投入された制御点を第2内分係数でさらに内分して、ピクセルシェーダ32に出力する。ピクセルシェーダ32は、テクスチャユニット70から受け取った第2内分係数で内分された制御点をさらにテクスチャユニット70に投入し、テクスチャユニット70は、それを第3内分係数でさらに内分して、ピクセルシェーダ32に返す。このようにすれば、テセレーション処理に必要なすべての内分演算をテクスチャユニット70の線形補間機能を用いて実現することができる。また、テクスチャユニット70の線形補間部72が線形補間結果をフィードバックして再入力できるように構成されていてもよい。
【図面の簡単な説明】
【0221】
【図1】実施の形態に係る描画処理装置の構成図である。
【図2】図1のラスタライザに入力される正方形プリミティブを説明する図である。
【図3】パラメトリック曲面の最小構成単位であるパッチを説明する図である。
【図4】パラメトリック曲線の上の点を求める手順を説明する図である。
【図5】4つの制御点の内分を繰り返すことにより、パラメトリック曲線上の点が求められる様子を示す図である。
【図6】テセレーション処理を行うための図1のピクセルシェーダおよびテクスチャユニットの構成を示す図である。
【図7】図6の制御点テクスチャのデータ構造を説明する図である。
【図8】図6の内分係数テクスチャのデータ構造を説明する図である。
【図9】図6のピクセルシェーダおよびテクスチャユニットによるテセレーション処理の手順を説明するフローチャートである。
【図10】テクスチャロード命令により、内分係数の始値と終値から補間値が得られる様子を説明する図である。
【図11】テクスチャロード命令により、制御点が内挿される様子を説明する図である。
【図12】2次元パラメータ座標値に対応するパラメトリック曲面の点およびその点における接線を求める手順を模式的に示す図である。
【図13】制御点が4個、5個、および6個の場合のノットパターンについて説明する図である。
【図14】制御点が7個、8個、および9個以上の場合のノットパターンについて説明する図である。
【図15】ノットパターンの各タイプについて、セグメントの接続関係をまとめた図である。
【図16】パラメトリック曲面に対して2次元パラメータ座標系の各方向に適用されるノットパターンのタイプを説明する図である。
【図17】階数が4、制御点数が4のBスプライン曲線について、漸化式によりBスプライン基底関数を計算する過程を説明する図である。
【図18】図17の計算過程を混ぜ合わせ係数を用いて書き換えた図である。
【図19】ノットパターンのタイプ毎の内分係数をまとめた図である。
【符号の説明】
【0222】
10 ラスタライザ、 30 シェーダユニット、 32 ピクセルシェーダ、 34 内挿演算部、 36 頂点データ出力部、 50 メモリ、 52 制御点テクスチャ、 54 内分係数テクスチャ、 56 テセレーションデータ、 70 テクスチャユニット、 72 線形補間部、 74 アドレス生成部、 100 描画処理装置。
【技術分野】
【0001】
この発明は描画データを演算処理する描画処理装置、テクスチャ処理装置、およびテセレーション方法に関する。
【背景技術】
【0002】
描画オブジェクトの3次元モデルを生成する際、より複雑な形状を表現するために自由曲面を用いることが多い。自由曲面の表現方法の一つとして、NURBS曲線またはNURBS曲面は、数少ない制御点で滑らかな曲線または曲面を表現することができるという利点があり、広く用いられている。NURBSでは、制御点の他にも、重み、ノットといった形状を操作するためのパラメータが多く、局所的に形状を変化させることが可能である。また、NURBSは、円弧や直線、放物線等の円錐曲線も統一的に表現できるといった優れた表現能力をもつ。3次元コンピュータグラフィックスでは、NURBSデータで製作された描画モデルのレンダリング技術が求められている。
【0003】
NURBS曲面やベジェ曲面等のパラメトリック曲面の形式で滑らかに表現されたオブジェクトは、制御点などのパラメータで表現されているため、3次元オブジェクトを3角形などの多角形ポリゴンの集合で表現するポリゴンモデルと比べた場合、データ量が少なくて済む。また、ネットワークゲームのようなアプリケーションにおいては、3次元モデル情報をネットワークで伝送することがあるが、自由曲面によるオブジェクト表現は、データ量が少ないため、ネットワークアプリケーションにも適している。
【0004】
自由曲面で表された3次元モデルを描画する際には、自由曲面をポリゴンに分割して、レンダリングアルゴリズムを適用して描画演算処理する。自由曲面をポリゴン分割するためには、NURBSなどで定義されたパラメトリック曲面の方程式において媒介変数の値を所定の間隔で変化させることによりパラメトリック曲面上の頂点を直接求め、これらの点をつなぎ合わせてポリゴンを生成する。これによりパラメトリック曲面が所定の分割数で多数のポリゴンに細分化される。この処理はテセレーション処理と呼ばれる。
【発明の開示】
【発明が解決しようとする課題】
【0005】
テセレーション処理においてパラメトリック曲面の頂点の座標値を求めるには、パラメトリック曲面の形状を決める制御点に対して演算を繰り返し行う必要がある。このテセレーション処理をソフトウエアで行うと、演算量が多いため、計算時間が相当にかかり、実時間で描画結果を表示することが必要な3次元コンピュータグラフィックスのアプリケーションには、テセレーション処理は向いていない。また、テセレーション処理に必要なデータや中間演算結果を記憶するために大きなメモリ容量が必要であり、テセレーション処理をハードウエアに実装することを難しくしている。
【0006】
そこで、テセレーション処理の分割数を減らして計算量を減らしたり、制御点数を減らしたり、より簡単な曲線式を使うなど曲面の自由度を制限することで計算量やメモリ量を減らすことが行われるが、その結果、描画対象オブジェクトが粗いポリゴンで表現されることになり、十分な品質でコンピュータグラフィックスの画像を生成することができないという問題が生じる。
【0007】
本発明はこうした課題に鑑みてなされたものであり、その目的は、テセレーション処理を計算量の面で効率良く行うことのできる描画処理技術を提供することにある。また、別の目的は、テセレーション処理の実行にあたり、メモリ容量の面で有利な描画処理技術を提供することにある。
【課題を解決するための手段】
【0008】
上記課題を解決するために、本発明のある態様の描画処理装置は、1つのパラメータに対して座標点を対応づけることにより表されるパラメトリック曲線により描画対象物を近似処理する描画処理装置であって、前記パラメトリック曲線を構成する単位であるセグメントに対して定義される1次元パラメータ座標系におけるパラメータの1次関数で表される内分係数について、前記パラメータの定義域内の2つの点における前記内分係数の代表値の組を保持する係数データ記憶部と、処理対象のセグメントにおいて指定される前記パラメータの指定値を補間係数として、前記係数データ記憶部に記憶された前記内分係数の代表値の組を線形補間器により補間演算することにより、前記パラメータの指定値に対応する前記内分係数の補間値を算出する補間処理部と、前記内分係数の補間値にもとづいた比で、当該処理対象のセグメントの形状を決める複数の制御点を内挿演算することにより、当該処理対象のセグメントにおいて前記パラメータの指定値に対応する前記パラメトリック曲線上の頂点座標を算出する細分化処理部とを含む。
【0009】
本発明の別の態様もまた、描画処理装置である。この装置は、2つのパラメータの組に対して座標点を対応づけることにより表されるパラメトリック曲面により描画対象物を近似処理する描画処理装置であって、前記パラメトリック曲面を構成する単位であるパッチに対して定義される2次元パラメータ座標系における第1パラメータの1次関数で表される第1内分係数について、前記第1パラメータの定義域内の2つの点における前記第1内分係数の代表値の組を保持する係数データ記憶部と、処理対象のパッチにおいて指定される前記第1パラメータの指定値を補間係数として、前記係数データ記憶部に記憶された前記第1内分係数の代表値の組を線形補間器により補間演算することにより、前記第1パラメータの指定値に対応する前記第1内分係数の補間値を算出する補間処理部と、前記第1内分係数の補間値にもとづいた比で、当該処理対象のパッチの形状を決める複数の制御点を前記2次元パラメータ座標系の第1パラメータ軸方向に内挿演算する細分化処理部とを含む。
【0010】
本発明のさらに別の態様もまた、描画処理装置である。この装置は、テクスチャに関するデータを記憶するテクスチャ記憶部と、描画処理単位に対して定義されるパラメータ座標の指定値にもとづいて、前記テクスチャ記憶部に記憶された前記テクスチャに関するデータを線形補間器により補間演算することにより、前記パラメータ座標の指定値に対応する前記テクスチャに関する補間データを算出するテクスチャ処理部と、前記テクスチャに関する補間データを用いて、前記描画処理単位の演算処理を行う描画処理部とを含む。前記描画処理単位は、1次元パラメータ座標で表されるパラメトリック曲線を構成する単位であるセグメント、または2次元パラメータ座標で表されるパラメトリック曲面を構成する単位であるパッチであり、前記テクスチャ記憶部は、前記セグメントまたは前記パッチに対して定義されるパラメータ座標に依存する内分係数について、前記パラメータの定義域内の2つの点における前記内分係数の代表値の組を前記テクスチャに関するデータとして保持し、前記テクスチャ処理部は、処理対象のセグメントまたはパッチについて前記描画処理部により順次指定されるパラメータ座標の指定値を補間係数として、前記内分係数の代表値の組を線形補間器により補間演算することにより、前記パラメータ座標の指定値に対応する前記内分係数の補間値を算出し、前記描画処理部は、前記内分係数の補間値にもとづいた比で、当該処理対象のセグメントまたはパッチの形状を決める複数の制御点を内挿演算することにより、当該処理対象のセグメントまたはパッチにおいて前記パラメータ座標の指定値に対応する前記パラメトリック曲線またはパラメトリック曲面上の点の座標を順次算出する。
【0011】
本発明のさらに別の態様は、テクスチャ処理装置である。この装置は、テクスチャに関するデータを記憶するテクスチャ記憶部と、描画処理単位に対して定義されるパラメータ座標の指定値にもとづいて、前記テクスチャ記憶部に記憶された前記テクスチャに関するデータを線形補間器により補間演算することにより、前記パラメータ座標の指定値に対応する前記テクスチャに関する補間データを算出するテクスチャ処理部とを含む。前記描画処理単位は、1次元パラメータ座標で表されるパラメトリック曲線を構成する単位であるセグメント、または2次元パラメータ座標で表されるパラメトリック曲面を構成する単位であるパッチであり、前記テクスチャ記憶部は、前記セグメントまたは前記パッチの形状を決める複数の制御点の組を前記セグメントまたは前記パッチ毎に保持し、前記テクスチャ処理部は、処理対象のセグメントまたはパッチに適用すべき前記複数の制御点の組を前記テクスチャ記憶部から取得して線形補間器により内挿演算することにより、当該処理対象のセグメントまたはパッチにおいて指定される前記パラメータ座標の指定値に対応する前記パラメトリック曲線または前記パラメトリック曲面上の頂点座標を算出する。
【0012】
本発明のさらに別の態様は、テクスチャのデータ構造である。このテクスチャのデータ構造は、パラメトリック曲面の形状を決める制御点の3次元座標値がテクセル値として格納され、パラメトリック曲面の座標系におけるパラメータを指定値とするテクスチャの読み出し命令により隣接する2つの前記制御点の座標値がサンプリングされて、前記指定値に対応する制御点の補間値を計算可能に構成される。
【0013】
本発明のさらに別の態様もまた、テクスチャのデータ構造である。このテクスチャのデータ構造は、パラメトリック曲面の形状を決める制御点を再帰的に内挿演算する際の内分係数の始値およぶ終値が隣接するテクセル値として格納され、パラメトリック曲面の座標系におけるパラメータを指定値とするテクスチャの読み出し命令により前記内分係数の始値および終値がサンプリングされて、前記指定値に対応する内分係数の補間値を計算可能に構成される。
【0014】
本発明のさらに別の態様は、テセレーション方法である。この方法は、1つのパラメータに対して座標点を対応づけることにより表されるパラメトリック曲線を折れ線に細分化するテセレーション方法であって、前記パラメトリック曲線を構成する単位であるセグメントに対して定義される1次元パラメータ座標系におけるパラメータに依存して値が決まる内分係数について、前記パラメータの定義域の両端点における前記内分係数の値を始値および終値としてあらかじめ係数テーブルに格納しておき、処理対象のセグメントにおいて指定される前記パラメータの指定値を補間係数として、前記係数テーブルに格納された前記内分係数の始値および終値を補間することにより、前記パラメータの指定値に対応する前記内分係数の補間値を算出するステップと、前記内分係数の補間値にもとづいた比で、当該処理対象のセグメントの形状を決める複数の制御点を内挿演算することにより、当該処理対象のセグメントにおいて前記パラメータの指定値に対応する前記パラメトリック曲線上の頂点座標を算出するステップとを含む。
【0015】
本発明のさらに別の態様もまた、テセレーション方法である。この方法は、2つのパラメータの組に対して座標点を対応づけることにより表されるパラメトリック曲面をポリゴンメッシュに細分化するテセレーション方法であって、前記パラメトリック曲面を構成する単位であるパッチに対して定義される2次元パラメータ座標系における第1パラメータに依存して値が決まる第1内分係数について、前記第1パラメータの定義域の両端点における第1内分係数の値を始値および終値としてあらかじめ係数テーブルに格納しておき、処理対象のパッチにおいて指定される前記第1パラメータの指定値を補間係数として、前記係数テーブルに格納された前記第1内分係数の始値および終値を補間することにより、前記第1パラメータの指定値に対応する前記第1内分係数の補間値を算出するステップと、前記内分係数の補間値にもとづいた比で、当該処理対象のパッチの形状を決める複数の制御点を前記2次元パラメータ座標系の第1パラメータ軸方向に内挿演算するステップとを含む。
【0016】
なお、以上の構成要素の任意の組合せ、本発明の表現を方法、装置、システム、コンピュータプログラム、データ構造などの間で変換したものもまた、本発明の態様として有効である。
【発明の効果】
【0017】
本発明によれば、描画対象オブジェクトのテセレーション処理を効率良く行うことができる。
【発明を実施するための最良の形態】
【0018】
図1は、実施の形態に係る描画処理装置100の構成図である。描画処理装置100は、3次元モデル情報にもとづいて2次元画面に表示するための描画データを生成するレンダリング処理を行う。
【0019】
特に、本実施の形態の描画処理装置100は、自由曲面を用いてモデル化された描画対象オブジェクトの形状を細かく分割し、幾何学的なプリミティブの集合に変換するテセレーション(Tessellation)処理を行う。まず、描画処理装置100の構成を一般的な動作とともに説明し、その後、本実施の形態に特有のテセレーション処理に関する動作を説明する。
【0020】
ラスタライザ10は、メモリもしくは他のプロセッサや頂点シェーダなどから描画対象となるプリミティブの頂点データを取得し、描画するスクリーンに対応したピクセル情報に変換する。描画プリミティブは、3次元オブジェクトをポリゴンモデルで表した場合の点、線、三角形、四角形などの幾何学図形の描画単位であり、頂点単位で表されるデータである。ラスタライザ10は、3次元空間上の描画プリミティブを投影変換により描画平面上の図形に変換するビュー変換を行い、さらに、描画平面上の図形を描画平面の水平方向に沿ってスキャンしながら、1列毎に量子化されたピクセルに変換する。
【0021】
ラスタライザ10により、描画プリミティブがピクセル展開され、各ピクセルについて、RGB3原色で表されるカラー値、透明度を示すアルファ(α)値、奥行きを示すZ値、テクスチャ属性を参照するためのパラメータ座標であるUV座標値などを含むピクセル情報が算出される。
【0022】
ラスタライザ10は、1つ以上のピクセルを含む所定サイズのピクセル集合の単位で上記のラスタライズ処理を行い、ラスタライズ処理後のピクセル集合をバッファリングしながら、ピクセル集合の単位でシェーダユニット30に順次供給する。ラスタライザ10からシェーダユニット30に供給されたピクセル集合は、シェーダユニット30においてパイプライン処理される。ピクセル集合は、ラスタライザ10が一度に処理するピクセルをまとめたものであり、ラスタライズ処理の単位であり、また同時に、シェーダユニット30における描画演算処理の単位にもなっている。
【0023】
シェーダユニット30は、非同期動作する複数のピクセルシェーダ32を含み、それぞれが担当するピクセル集合を処理することでピクセルの描画処理を並列に実行する。各ピクセルシェーダ32は、ラスタライザ10からピクセル集合単位で分配されるピクセル情報をもとに、シェーディング処理を行ってピクセルのカラー値を求め、さらに、テクスチャマッピングを行う場合は、テクスチャユニット70から得られるテクスチャのカラー値を合成して最終的なピクセルのカラー値を算出し、メモリ50にピクセルデータを書き込む。
【0024】
テクスチャユニット70は、各ピクセルシェーダ32において処理されるピクセルにテクスチャデータをマッピングする処理を行う。ポリゴン面上のピクセルにマッピングされるテクスチャの位置は2次元パラメータ座標であるUV座標系で表される。テクスチャユニット70は、各ピクセルシェーダ32からピクセルにマッピングされるテクスチャの座標値(u,v)を取得し、座標値(u,v)に対応するカラー値を補間して、各ピクセルシェーダ32にその補間値を供給する。
【0025】
ピクセルシェーダ32は、さらに、メモリ50に保持された描画データに対して、フォギング、アルファブレンディング等の処理を行い、最終的なピクセルのカラー値を求め、メモリ50のピクセルデータを更新する。
【0026】
メモリ50は、各ピクセルシェーダ32により生成されたピクセルデータをスクリーン座標で格納するフレームバッファとして機能する領域をもつ。フレームバッファに格納されたピクセルデータは、最終描画画像であることも、シェーディング処理過程にある中間画像であることもある。フレームバッファに記憶されたピクセルデータは、表示装置に出力されて表示される。
【0027】
次に、描画処理装置100の各構成によるテセレーション処理に関する動作を説明する。
【0028】
ラスタライザ10は、正方形の描画プリミティブ(以下、単に正方形プリミティブという)の入力を受ける。正方形プリミティブは、正方形の対角線の両端である2つの頂点をパラメータとしてもつ。ラスタライザ10は、正方形プリミティブをピクセルデータに変換するラスタライズ処理の機能を利用して、正方形プリミティブ内でパラメトリック曲面の最小構成単位であるパッチに対して定義される2次元パラメータ座標値(u,v)をピクセル単位で生成する。
【0029】
また、ラスタライザ10は、パラメトリック曲面のパッチの形状を決める制御点データを参照するためのインデックスと、パッチのu、vそれぞれの方向で使用される後述のノットパターンのタイプを決め、パッチ内の2次元パラメータ座標値(u、v)とともにパッチのパラメータ情報としてシェーダユニット30のピクセルシェーダ32に供給する。
【0030】
図2(a)、(b)は、ラスタライザ10に入力される正方形プリミティブを説明する図である。図2(a)は、ラスタライザ10に入力される均等なサイズの正方形プリミティブ200〜203を示す。各正方形プリミティブ200〜203は、縦横4ピクセルのピクセル集合を縦方向、横方向にそれぞれ4つずつ並べたものであり、縦横16ピクセル、合計256ピクセルの描画領域をもつ。この場合、ラスタライザ10は、正方形プリミティブを縦横16分割、合計256分割で細分化して、2次元パラメータ座標値を順次生成する。
【0031】
図2(a)のように、ラスタライザ10が、描画対象オブジェクトに対して同一サイズの正方形プリミティブ200〜203の入力を受ける場合、描画対象オブジェクトの自由曲面の分割粒度は一定であり、自由曲面は均等に細分化される。描画オブジェクトの自由曲面を細分化する粒度を状況に応じて可変にする適応型テセレーション(Adaptive Tessellation)を行う場合は、正方形プリミティブのサイズを変えてラスタライザ10に入力すればよい。
【0032】
図2(b)は、適応型テセレーションを行う場合に、ラスタライザ10に入力される正方形プリミティブを説明する図である。縦横4ピクセルのピクセル集合を縦方向、横方向にそれぞれ2つずつ並べた正方形プリミティブ210、211は、縦横8ピクセル、合計64ピクセルの描画領域をもつ。この場合、ラスタライザ10は、正方形プリミティブを縦横8分割、合計64分割で細分化して、2次元パラメータ座標値を順次生成する。
【0033】
これに対して、縦横4ピクセルのピクセル集合を縦方向、横方向にそれぞれ5つずつ並べた正方形プリミティブ212は、縦横20ピクセル、合計400ピクセルの描画領域をもつ。この場合、ラスタライザ10は、正方形プリミティブを縦横20分割、合計400分割で細分化して、2次元パラメータ座標値を順次生成する。
【0034】
縦横4ピクセルのピクセル集合を縦方向、横方向にそれぞれ4つずつ並べた正方形プリミティブ213は、図2(a)で説明したように、縦横16分割、合計256分割で細分化される。
【0035】
このように正方形プリミティブのサイズが大きくなるほど、分割数が増え、同じ描画領域でもより細かく細分化される。たとえば、描画オブジェクトを描画する際の詳細度が高いほど、正方形プリミティブのサイズを大きくして分割数を増やしたり、パッチの法線方向と視線方向との関係に応じて正方形プリミティブのサイズを可変にして分割数を変えることができる。また、複雑な形状の描画オブジェクトの場合には、正方形プリミティブのサイズを大きくして分割数を増やすことができる。このように、正方形プリミティブのサイズを状況に応じて可変にすることで適応型テセレーション処理が可能になる。
【0036】
さらに、正方形プリミティブを指定するときのパラメータを調整すれば、本来の正方形領域よりも狭い範囲を指定してテセレーション処理を実行することも可能である。正方形プリミティブに対して、領域の対角線の両端の頂点を指定するパラメータを調整することで、描画範囲を限定することが可能である。正方形領域の対角線の両端の頂点パラメータは、(0,0)および(1,1)であるが、これを0〜1の間の値にすることで、描画範囲を狭めることができる。符号214で示すように、頂点(0.25,0.3)、(0.5,0.9)を指定することで、これらを結ぶ対角線で規定される長方形領域に正方形プリミティブの描画範囲を狭めることができる。このように描画領域を定める対角線の両端の頂点パラメータを調整することで、正方形プリミティブをラスタライザ10に入力した場合でも、長方形の形状に描画領域を制限することで、任意の矩形領域の曲面を生成することができる。
【0037】
テセレーション処理を行うためのシェーダユニット30とテクスチャユニット70の具体的な構成と動作について説明する前に、まず、テセレーション処理の大まかな手順を説明する。
【0038】
3次元オブジェクトを表現する際の自由曲面の種類としては、ベジエ(Bezier)曲面やBスプライン(B-Spline)曲面などいくつかの種類があり、より一般的な自由曲面の表現形式としてNURBS(Non Uniform Rational B-Spline)曲面が広く用いられている。これらの曲面は、2つのパラメータu、vを媒介変数としたパラメトリック曲面であり、2つの媒介変数(u,v)に対して曲面上の点(x,y,z)が連続的に定義される。パラメトリック曲面でオブジェクトをモデリングする際、パッチと呼ばれるパラメトリック曲面の最小構成単位をつなぎ合わせて1つの曲面を表現する。
【0039】
本実施の形態では、パラメトリック曲面として設計の自由度が高いNURBS曲面の場合を説明するが、他の種類の自由曲面の場合も、同様のテセレーション処理が可能である。
【0040】
図3は、パラメトリック曲面の最小構成単位であるパッチを説明する図である。パッチは0≦u≦1、0≦v≦1の範囲で定義され、4階のBスプライン曲面の場合は、制御点はu方向に4個、v方向に4個設けられ、合計16個の制御点P0〜P15をもつ。このパラメトリック曲面をu方向またはv方向で見た場合、パラメータuまたはvを媒介変数としたパラメトリック曲線と見ることができる。パラメトリック曲線の最小単位はセグメントと呼ばれ、4階のBスプライン曲線の場合、4個の制御点をもつ。
【0041】
テセレーション処理は、パラメトリック曲面のパッチ毎に2次元パラメータ座標値(u,v)を所定の間隔で変化させて、各2次元パラメータ座標値(u,v)に対応するパラメトリック曲面上の点をプリミティブの頂点座標として求める処理である。このテセレーション処理により、描画対象オブジェクトの自由曲面がパッチ毎にメッシュ状に細分化され、小さいプリミティブの集合に変換される。
【0042】
2次元パラメータ座標値(u,v)に対応するパラメトリック曲面上の点を求めるには、まず、パラメトリック曲面をu方向に見て、第1パラメータ座標値uに対応するパラメトリック曲線上の点を求め、次に、それをv方向に見て、第2パラメータ座標値vに対応するパラメトリック曲線上の点を求める。
【0043】
図4(a)〜(c)は、パラメトリック曲線の上の点を求める手順を説明する図である。ここでは、u方向、v方向のいずれでも手順は同じであるから、2次元パラメータ座標系の第1パラメータu、第2パラメータvを区別せずに、パラメータをtとおいて説明する。
【0044】
パラメトリック曲線のセグメント内でパラメータtに対応する点は、セグメントの形状を決める4つの制御点P0〜P3をパラメータtに依存する内分係数で再帰的に3回内挿演算することにより求められる。
【0045】
1回目の内挿演算では、図4(a)に示すように、第1、第2の制御点P0、P1をパラメータtに対応する内分係数a00にもとづく比a00:(1−a00)で内分する点P01を求める。同様に、第2、第3の制御点P1、P2を内分係数a10にもとづく比a10:(1−a10)で内分する点P12を求め、第3、第4の制御点P2、P3を内分係数a20にもとづく比a20:(1−a20)で内分する点P23を求める。1回目の内挿演算に用いる3つの内分係数a00、a10、a20を第1内分係数と呼ぶ。
【0046】
次に、2回目の内挿演算では、図4(b)に示すように、図4(a)で求めた第1、第2の内分点P01、P12をパラメータtに対応する内分係数a01にもとづく比a01:(1−a01)でさらに内分する点P012を求める。同様に、図4(a)で求めた第2、第3の内分点P12、P23をパラメータtに対応する内分係数a11にもとづく比a11:(1−a11)でさらに内分する点P123を求める。2回目の内挿演算に用いる2つの内分係数a01、a11を第2内分係数と呼ぶ。
【0047】
最後に、3回目の内挿演算では、図4(c)に示すように、図4(b)で求めた第1の内分点P012と第2の内分点P123をパラメータtに対応する内分係数a02にもとづく比a02:(1−a02)で内分する点P0123を求める。3回目の内挿演算に用いる1つの内分係数a02を第3内分係数と呼ぶ。
【0048】
このようにして4つの制御点を再帰的に3回内分することで得られた点P0123は、パラメータtに対応するパラメトリック曲線上の点になっている。
【0049】
図5は、4つの制御点P0〜P3の内分を繰り返すことにより、パラメトリック曲線上の点P0123が求められる様子を示す図である。4つの制御点P0〜P3をパラメータtに対応する第1内分係数で内分した点がP01(t)、P12(t)、P23(t)であり、それをさらにパラメータtに対応する第2内分係数で内分した点がP012(t)、P123(t)であり、それをさらにパラメータtに対応する第3内分係数で内分した点がP0123(t)である。パラメータtを変化させることにより、P0123(t)の描く軌跡がパラメトリック曲線Lである。なお、点P0123(t)におけるパラメトリック曲線Lの接線は、2点P012(t)、P123(t)の差分ベクトルで与えられる。
【0050】
テセレーション処理は、パラメータtを所定の間隔で小刻みに変化させながら、パラメータtに対応する内分係数を用いて4つの制御点を再帰的に3回内分して点P0123(t)を求めることで行われる。所定の間隔で変化するパラメータtに対する点P0123(t)を順に折れ線でつなげていけば、1セグメント内でパラメトリック曲線が折れ線近似される。これをu方向、v方向に行うことで、1パッチ内でパラメトリック曲面がメッシュ状に細分化され、所定の分割数のテセレーション結果が得られる。
【0051】
図6は、テセレーション処理を行うためのピクセルシェーダ32およびテクスチャユニット70の構成を示す図である。
【0052】
ピクセルシェーダ32は、ラスタライザ10から分配された正方形プリミティブに対してパラメトリック曲面のパッチを当てはめ、パッチ単位で描画対象オブジェクトの形状をメッシュ状に細分化する処理を行う。ピクセルシェーダ32は、ラスタライザ10により生成された2次元パラメータ座標値(u,v)に対応するパラメトリック曲面上の点をメッシュの頂点座標として求めることにより、パッチをメッシュに分割する。この計算を行うために、ピクセルシェーダ32は、パッチの形状を決める制御点と、制御点を再帰的に内挿演算するときの内分係数のデータを必要とする。
【0053】
後に詳しく説明するように、u方向に制御点を内挿するときに用いられる内分係数は、2次元パラメータ座標系の第1パラメータuの1次式で表され、v方向に制御点を内挿するときに用いられる内分係数は、2次元パラメータ座標系の第2パラメータvの1次式で表される。
【0054】
第1パラメータu、第2パラメータvを区別せずにtとおくと、パラメータtに対応する内分係数の値は、0≦t≦1の区間の両端点における値、すなわちt=0のときの始値と、t=1のときの終値さえ与えられれば、始値と終値をパラメータtにもとづく比t:(1−t)で内分することにより、任意のtに対する内分係数の値を求めることができる。
【0055】
この性質は、テクスチャユニット70の線形補間演算機能と親和性がある。内分係数の始値および終値をテクスチャデータとして扱い、テクスチャユニット70がパラメータtを補間係数として内分係数の始値および終値を線形補間することにすれば、任意のパラメータtに対する内分係数は、テクスチャの補間演算を利用して取得することができる。これは、いろいろなパラメータtの値に対する内分係数を保持したテーブルを用意したり、1次式にもとづいて内分係数を計算する方法に比べて、メモリ容量、計算コストの面で有利である。そこで、本実施の形態では、内分係数はその始値と終値だけがテクスチャデータとして内分係数テクスチャ54に格納されている。
【0056】
また、ピクセルシェーダ32は、パッチの形状を決める制御点を内分係数にもとづく比で再帰的に内挿演算するが、この内挿演算も、テクスチャユニット70の線形補間演算機能との親和性がある。制御点の座標値をテクスチャデータとして扱い、テクスチャユニット70が内分係数を補間係数として2つの制御点を線形補間することにすれば、制御点を内分係数にもとづいて内分した点は、テクスチャの補間演算を利用して取得することができる。そこで、本実施の形態では、制御点の再帰的な内挿演算の内、1回目の内挿演算をテクスチャユニット70の線形補間機能を用いて実行する。そのために、制御点データは、テクスチャデータとして制御点テクスチャ52に格納されている。
【0057】
ピクセルシェーダ32の内挿演算部34は、パラメトリック曲面のパッチの2次元バラメータ座標値(u,v)を補間係数として指定したテクスチャロード命令をテクスチャユニット70に対して発行し、テクスチャユニット70から2次元バラメータ座標値(u,v)にもとづいて補間された内分係数を取得する。内挿演算部34は、このテクスチャロード命令の発行の際、当該パッチに適用すべきノットパターンのタイプも指定する。このノットパターンのタイプは、テクスチャユニット70が内分係数テクスチャ54の参照行を決定するために必要となる。
【0058】
さらに、内挿演算部34は、テクスチャユニット70から取得した内分係数を新たに補間係数として指定したテクスチャロード命令をテクスチャユニット70に対して発行し、テクスチャユニット70から内分係数にもとづいて補間された制御点を取得する。内挿演算部34は、このテクスチャロード命令の発行の際、当該パッチに適用すべき制御点データのインデックスも指定する。このインデックスは、テクスチャユニット70が制御点テクスチャ52の参照行を決定するために必要となる。
【0059】
内挿演算部34は、2次元パラメータ座標値(u,v)に対応する内分係数にもとづいて、テクスチャユニット70から取得した制御点を再帰的に内挿演算し、2次元パラメータ座標値(u,v)に対応するパラメトリック曲面上の点をメッシュの頂点座標として求める。再帰的な内挿演算を可能にするため、内挿演算部34は、中間結果を保持するレジスタをもち、レジスタに演算の中間結果をいったん書き出し、レジスタに保持された中間結果を読み込んで中間結果に対するさらなる演算を行う。
【0060】
頂点データ出力部36は、内挿演算部34により求められたパラメトリック曲面のメッシュの頂点座標値を2次元パラメータ座標値(u,v)に対応づけてメモリ50に書き出す。内挿演算部34が2次元パラメータ座標値(u,v)を所定の間隔で変化させながら、パラメトリック曲面のメッシュの頂点座標値を求め、頂点データ出力部36がその頂点座標値を2次元パラメータ座標値(u,v)に対応づけてメモリ50に書き出すことで、メモリ50にはパッチ内のパラメトリック曲面をメッシュ状に細分化したデータがテセレーションデータ56として形成される。
【0061】
テクスチャユニット70は、ピクセルシェーダ32から2次元パラメータ座標値(u,v)を補間係数として受け取り、内分係数テクスチャ54から読み出した内分係数をその補間係数のもとで補間した値をピクセルシェーダ32に与える。また、テクスチャユニット70は、ピクセルシェーダ32から内分係数を補間係数として受け取り、制御点テクスチャ52から読み出した制御点をその補間係数のもとで補間した値をピクセルシェーダ32に与える。
【0062】
テクスチャユニット70が参照する制御点テクスチャ52および内分係数テクスチャ54は、それぞれテクスチャの形式で制御点と内分係数を格納したものであり、テクスチャユニット70は、テクスチャデータからテクセル値を読み出して線形補間器により線形補間する機能を利用して、制御点と内分係数を指定された補間係数で線形補間する。
【0063】
図7は、制御点テクスチャ52のデータ構造を説明する図である。制御点テクスチャ52は、パラメトリック曲面のパッチの形状を決める16個の制御点をテクセル値として行単位で格納したデータ構造をもつ。各行にはP0〜P15までの16個の制御点の3次元座標値(x,y,z)が格納されている。横方向1列の16個の制御点P0〜P15が1つのパッチ曲面分の制御点として利用される。縦方向には描画対象オブジェクトのパッチ曲面数分の制御点データが用意されている。
【0064】
テクスチャは、通常はRGB3色のカラー値からなるテクセル値を格納するものであるが、ここでは、テクセルのR、G、B値の代わりに制御点の座標値x,y,zをそれぞれ格納することで、テクスチャのデータ構造を制御点の3次元座標の格納に利用している。
【0065】
テクスチャユニット70は、制御点テクスチャ52の行番号sと制御点番号i(i=0,1…,15)にもとづく参照アドレスを指定することにより、制御点テクスチャ52から制御点の3次元座標値を読み出す。
【0066】
図8は、内分係数テクスチャ54のデータ構造を説明する図である。内分係数テクスチャ54は、NURBS曲面のパッチのノットパターン毎に、制御点の再帰的な内挿演算に用いる第1、第2および第3内分係数について、その始値および終値をテクセル値として格納したデータ構造をもつ。
【0067】
後に詳しく説明するように、本実施の形態では、NURBS曲面の隣接するパッチの滑らかな接続性を考慮してノットパターンは9種類に限定されている。内分係数テクスチャ54の各行は、ノットパターンのタイプ#1〜#9に対応しており、各行には、そのノットパターンのタイプの内分係数が4つのテクセルの形式で格納されている。
【0068】
第1テクセルには、1回目の内挿演算に用いる第1内分係数a00、a10、a20の始値(a00(0),a10(0),a20(0))がテクセル値として、カラー値(R,G,B)の代わりに格納されている。第2テクセルには、1回目の内挿演算に用いる第1内分係数a00、a10、a20の終値(a00(1),a10(1),a20(1))が格納されている。
【0069】
第3テクセルには、2回目の内挿演算に用いる第2内分係数a01、a11の始値および3回目の内挿演算に用いる第3内分係数a02の始値を組み合わせた(a01(0),a11(0),a02(0))がテクセル値として、カラー値(R,G,B)の代わりに格納されている。第4テクセルには、2回目の内挿演算に用いる第2内分係数a01、a11の終値および3回目の内挿演算に用いる第3内分係数a02の終値を組み合わせた(a01(1),a11(1),a02(1))が格納されている。
【0070】
テクスチャユニット70は、縦方向のノットパターンのタイプと横方向のテクセル番号にもとづく参照アドレスを指定することにより、内分係数テクスチャ54から内分係数を読み出す。
【0071】
図6に戻り、テクスチャユニット70のアドレス生成部74および線形補間部72が、内分係数テクスチャ54および制御点テクスチャ52をテクスチャデータとして参照して、内分係数および制御点を線形補間する動作について説明する。
【0072】
アドレス生成部74は、ピクセルシェーダ32の内挿演算部34から指定されたノットパターンのタイプと2次元パラメータ座標値(u,v)にもとづいて、内分係数テクスチャ54を参照するための参照アドレスを生成し、内分係数テクスチャ54から参照アドレスに対応する内分係数の始値および終値を読み出し、線形補間部72に入力として与える。
【0073】
線形補間部72は、加算器、差分器、乗算器、および補間係数を保持するレジスタを有する線形補間器である。線形補間器には、第1入力値X、第2入力値Y、および補間係数aが入力される。差分器は、第2入力値Yから第1入力値Xを引き算して、2入力値の差分Y−Xを計算し、乗算器に与える。乗算器は、差分器から入力された差分Y−Xに補間係数aを乗じた値a(Y−X)を計算し、加算器に与える。加算器は、乗算器から入力された乗算結果a(Y−X)に第1入力値Xを加算した値a(Y−X)+Xを計算し、線形補間器の最終的な出力値として出力する。
【0074】
線形補間部72の出力値Zは、Z=a(Y−X)+X=(1−a)X+aYと変形できるため、第1入力値Xと第2入力値Yを補間係数aにもとづくa:(1−a)の比で内分した値である。
【0075】
線形補間部72は、内挿演算部34から指定されたパラメータ座標u、vのそれぞれを補間係数として、アドレス生成部74により読み出された内分係数の始値および終値を線形補間し、内分係数の補間値を内挿演算部34に与える。具体的には、線形補間部72は、パラメータtを補間係数として、内分係数aijの始値aij(0)と終値aij(1)を線形補間器により補間した値aij(t)=(1−t)・aij(0)+t・aij(1)を出力する。
【0076】
さらに、内挿演算部34は、内分係数の補間値を線形補間部72から受け取ると、受け取った内分係数の補間値を新たに補間係数として指定してテクスチャユニット70に内分係数の補間値にもとづく比で内分された制御点を要求する。内挿演算部34は、通常は2次元パラメータ座標値(u,v)を補間係数として指定して、テクスチャユニット70に対して、2次元パラメータ座標値(u,v)にもとづいて補間されたテクセル値を要求するが、ここでは同じインタフェースを利用して(u,v)値の代わりに、内分係数を補間係数として指定する。
【0077】
アドレス生成部74は、内挿演算部34から指定された制御点データの参照行と補間係数にもとづいて、テクスチャを参照するための参照アドレスを生成し、制御点テクスチャ52から参照アドレスに対応する2つの制御点の値を読み出して、線形補間部72に入力として与える。
【0078】
線形補間部72は、内挿演算部34から指定された内分係数を補間係数として、アドレス生成部74により読み出された2つの制御点を線形補間し、制御点の補間値を内挿演算部34に与える。具体的には、線形補間部72は、パラメータtに対応する内分係数aij(t)を補間係数として、第1の制御点PAの座標値(xA,yA,zA)と第2の制御点PBの座標値(xB,yB,zB)を線形補間器により補間した座標値(xAB,yAB,zAB)=(1−aij(t))・(xA,yA,zA)+aij(t)・(xB,yB,zB)を出力する。
【0079】
図9は、ピクセルシェーダ32およびテクスチャユニット70によるテセレーション処理の手順を説明するフローチャートである。
【0080】
ピクセルシェーダ32は、ラスタライザ10から、処理対象のパッチのパラメータ情報として、当該パッチで使用される制御点データの参照行を指定するデータ(S10)、パッチのu、vそれぞれの方向で使用されるノットパターンのタイプを指定するデータ(S12)、およびパッチ内で所定の間隔で分割された2次元パラメータ座標値(u、v)を指定するデータ(S14)をそれぞれ受け取る。
【0081】
ピクセルシェーダ32の内挿演算部34は、パラメータuを補間係数とするテクスチャロード命令により、パラメータuに対応する内分係数の補間値aij(u)をロードする(S16)。テクスチャユニット70は、内挿演算部34によるテクスチャロード命令を受けて、ステップS12で指定されたu方向のノットパターンのタイプに対応する内分係数テクスチャ54の行から内分係数の始値aij(0)および終値aij(1)を読み出し、パラメータuにもとづく比u:1−uで内分係数の始値aij(0)と終値aij(1)を内分することにより、パラメータuに対応する内分係数の補間値aij(u)を求め、内挿演算部34に内分係数の補間値aij(u)をテクスチャロード命令の結果として返す。
【0082】
図10は、テクスチャロード命令により、内分係数の始値aij(0)と終値aij(1)から補間値aij(u)が得られる様子を説明する図である。内挿演算部34は、テクスチャユニット70に対して、テクスチャロード命令tldのパラメータとして(u,type)を与える。ここでtypeはノットパターンのタイプのインデックスであり、内分係数テクスチャ54の参照行に対応する。
【0083】
アドレス生成部74は、typeで指定された内分係数テクスチャ54の行の先頭アドレスを参照アドレスとして生成し、その参照アドレスから当該行の第1テクセルと第2テクセルを読み出し、線形補間部72に与える。これにより、第1内分係数の始値の組(a00(0),a10(0),a20(0))と第1内分係数の終値の組(a00(1),a10(1),a20(1))が線形補間部72に入力される。
【0084】
線形補間部72は、パラメータuを補間係数として、第1内分係数の始値(a00(0),a10(0),a20(0))と終値(a00(1),a10(1),a20(1))をu:(1−u)の比で内分した値(a00(u),a10(u),a20(u))を出力する。内挿演算部34は、テクスチャロード命令tldの返値として、指定したパラメータuに対応する内分係数の補間値(a00(u),a10(u),a20(u))を取得する。
【0085】
次に、内挿演算部34は、第2および第3内分係数についても、パラメータuに対応する補間値を取得するために、テクスチャロード命令tldのパラメータとして(u’,type)を与える。ここでu’はuの値に2テクセル分のオフセットを加えたものであり、このオフセットは、内分係数テクスチャ54のtypeで指定される行において、第1テクセルと第2テクセルを読み飛ばし、第3テクセルと第4テクセルの間で線形補間をするために必要となる。
【0086】
アドレス生成部74は、typeで指定された内分係数テクスチャ54の行の先頭アドレスに2テクセル分のオフセットを加算して参照アドレスを生成し、その参照アドレスから当該行の第3テクセルと第4テクセルを読み出し、線形補間部72に与える。これにより、第2および第3内分係数の始値の組(a01(0),a11(0),a02(0))と、第2および第3内分係数の終値の組(a01(1),a11(1),a02(1))が線形補間部72に入力される。
【0087】
線形補間部72は、パラメータuを補間係数として、第2および第3内分係数の始値(a01(0),a11(0),a02(0))と終値(a01(1),a11(1),a02(1))をu:(1−u)の比で内分した値(a01(u),a11(u),a02(u))を出力する。内挿演算部34は、テクスチャロード命令tldの返値として、指定したパラメータuに対応する内分係数の補間値(a01(u),a11(u),a02(u))を取得する。
【0088】
ステップS16の処理を擬似コードで書くと、次のようになる。
u方向について、補間された6つの係数をロード:
tld(u,type)=>a00(u),a10(u),a20(u)
u+2=>u’
tld(u’,type)=>a01(u),a11(u),a02(u)
ここで、=>は、左辺の演算命令の結果が右辺であることを示す。
【0089】
図9に戻り、内挿演算部34は、テクスチャロード命令を実行し、ステップS16で取得した第1内分係数の補間値a00(u)、a10(u)、a20(u)にもとづいた比でu方向に内挿された制御点をロードする(S18)。テクスチャユニット70は、内挿演算部34によるテクスチャロード命令の実行を受けて、制御点テクスチャ52の指定された参照行からu方向の4つの制御点の内、隣接する2つの制御点を順に取得し、線形補間部72に与える。線形補間部72は、第1内分係数の補間値a00(u)、a10(u)、a20(u)にもとづいた内分比で隣接する2つの制御点を内分し、内分された制御点を内挿演算部34にテクスチャロード命令の結果として返す。
【0090】
図11は、テクスチャロード命令により、制御点が内挿される様子を説明する図である。制御点テクスチャ52の各行には処理対象のパッチに対して指定された16個の制御点のデータが格納されている。ここでは、u方向のP0〜P3の4つの制御点に対する処理を説明する。u方向の他の4つの制御点P4〜P7、P8〜P11、P12〜P15についても、制御点テクスチャ52から読み出すテクセルを4つずつオフセットしていけば、処理としては同じである。
【0091】
制御点テクスチャ52の参照行sの第1〜第4テクセルには、4つの制御点P0〜P3の座標値が格納されている。内挿演算部34が、テクスチャユニット70に対して、テクスチャロード命令tldのパラメータとして(a00,s)を与える。
【0092】
アドレス生成部74は、制御点テクスチャ52の参照行sの先頭アドレスを参照アドレスとして生成し、その参照アドレスから当該行の第1テクセルと第2テクセルを読み出し、線形補間部72に与える。これにより、最初の2つの隣接する制御点P0とP1の座標値が線形補間部72に入力される。
【0093】
線形補間部72は、入力された2つの制御点P0とP1を第1内分係数a00にもとづく比a00:(1−a00)で内分した点P01の座標値を計算し、出力する。内挿演算部34は、テクスチャロード命令tldの返値として、第1内分係数の補間値a00(t)にもとづく内分比であらかじめ内分された制御点P01の座標値を取得する。
【0094】
次に、内挿演算部34は、テクスチャユニット70に対して、テクスチャロード命令tldのパラメータとして(a10’,s)を与える。ここでa10’はa10の値に1テクセル分のオフセットを加えたものであり、このオフセットは、制御点テクスチャ52の参照行sにおいて、第1テクセルを読み飛ばし、第2テクセルと第3テクセルの間で線形補間をするために必要となる。
【0095】
アドレス生成部74は、制御点テクスチャ52の参照行sの先頭アドレスに1テクセル分のオフセットを加算して参照アドレスを生成し、その参照アドレスから当該行の第2テクセルと第3テクセルを読み出し、線形補間部72に与える。これにより、次の2つの隣接する制御点P1とP2の座標値が線形補間部72に入力される。
【0096】
線形補間部72は、入力された2つの制御点P1とP2を第1内分係数a10にもとづく比a10:(1−a10)で内分した点P12の座標値を計算し、出力する。内挿演算部34は、テクスチャロード命令tldの返値として、第1内分係数の補間値a10(t)にもとづく内分比であらかじめ内分された制御点P12の座標値を取得する。
【0097】
さらに、内挿演算部34は、テクスチャユニット70に対して、テクスチャロード命令tldのパラメータとして(a20’,s)を与える。ここで、a20’はa20の値に2テクセル分のオフセットを加えたものであり、このオフセットは、制御点テクスチャ52の参照行sにおいて、第1、第2テクセルを読み飛ばし、第3テクセルと第4テクセルの間で線形補間をするために必要となる。
【0098】
アドレス生成部74は、制御点テクスチャ52の参照行sの先頭アドレスに2テクセル分のオフセットを加算して参照アドレスを生成し、その参照アドレスから当該行の第3テクセルと第4テクセルを読み出し、線形補間部72に与える。これにより、さらに次の2つの隣接する制御点P2とP3の座標値が線形補間部72に入力される。
【0099】
線形補間部72は、入力された2つの制御点P2とP3を第1内分係数a20にもとづく比a20:(1−a20)で内分した点P23の座標値を計算し、出力する。内挿演算部34は、テクスチャロード命令tldの返値として、第1内分係数の補間値a20(t)にもとづく内分比であらかじめ内分された制御点P23の座標値を取得する。
【0100】
ステップS18の処理の擬似コードは次のようになる。
補間された3つの制御点をロード:
tld(a00,s)=>P01xyz
a10+1−>a10’
tld(a10’,s)=>P12xyz
a20+2−>a20’
tld(a20’,s)=>P23xyz
【0101】
再び図9を参照する。内挿演算部34は、こうしてあらかじめ内挿された制御点を第2内分係数の補間値a01(u)、a11(u)にもとづいた比でu方向に内挿演算し、さらにその結果を第3内分係数の補間値a02(u)にもとづいた比でu方向に内挿演算する(S20)。この内挿計算は、内挿演算部34においてレジスタを用いた演算処理にて行われる。内挿演算部34は、3回の内挿演算の結果をストア命令stによりレジスタに書き込む。
【0102】
ステップS20の処理の擬似コードは次のようになる。
x座標を計算:
P01x+a01(P12x−P01x)=>P012x
P12x+a11(P23x−P12x)=>P123x
P012x+a02(P123x−P012x)=>P0123x
y座標を計算:
P01y+a01(P12y−P01y)=>P012y
P12y+a11(P23y−P12y)=>P123y
P012y+a02(P123y−P012y)=>P0123y
z座標を計算:
P01z+a01(P12z−P01z)=>P012z
P12z+a11(P23z−P12z)=>P123z
P012z+a02(P123z−P012z)=>P0123z
座標値をストア:
st P0123x
st P0123y
st P0123z
【0103】
次に、内挿演算部34は、パラメータvを補間係数とするテクスチャロード命令により、パラメータvに対応する第1、第2および第3内分係数の補間値bij(v)をロードする(S22)。テクスチャユニット70は、u方向の場合と同様に、内挿演算部34によるテクスチャロード命令を受けて、ステップS12で指定されたv方向のノットパターンのタイプに対応する内分係数テクスチャ54の行から内分係数の始値bij(0)および終値bij(1)を読み出し、パラメータvにもとづく比v:1−vで内分係数の始値bij(0)と終値bij(1)を内分することにより、パラメータvに対応する内分係数の補間値bij(v)を求め、内挿演算部34に内分係数の補間値bij(v)をテクスチャロード命令の結果として返す。
【0104】
ステップS22の演算の擬似コードは次のようになる。
v方向について、補間された6つの係数をロード:
tld(v,type)=>b00(v),b10(v),b20(v)
v+2=>v’
tld(v’,type)=>b01(v),b11(v),b02(v)
【0105】
内挿演算部34は、u方向に再帰的に3回内挿された制御点をロード命令ldによりレジスタから読み出し、そのu方向に内挿された後の制御点を、ステップS22で求めた第1、第2および第3内分係数の補間値bij(v)にもとづいた比でさらにv方向に再帰的に3回内挿演算する(S24)。v方向の内挿演算は、u方向の内挿演算と同様に行われる。ただし、u方向の1回目の内挿演算は、テクスチャユニット70の線形補間機能を用いて行われたが、v方向の内挿演算は、3回とも内挿演算部34においてレジスタに中間結果を保持しながら行われる。
【0106】
なお、一般に、NURBS曲面のパッチのu方向、v方向でノットパターンは異なるから、u方向の内挿演算に使われる第1、第2および第3内分係数aij(u)とv方向の内挿演算に使われる第1、第2および第3内分係数bij(v)は独立であり、u方向とv方向で異なるノットパターンのタイプに対応する内分係数が使われる。
【0107】
ステップS24において、最終的に2次元パラメータ座標値(u,v)に対応するパラメトリック曲面の点が得られる。内挿演算部34は、ストア命令stにより、得られたパラメトリック曲面の点をレジスタに保持する。
【0108】
ステップS24の処理の擬似コードは次のようになる。
u方向に計算された4つの制御点をロード:
ld P0x ld P0y ld P0z
ld P1x ld P1y ld P1z
ld P2x ld P2y ld P2z
ld P3x ld P3y ld P3z
【0109】
x座標を計算:
P0x+b00(P1x−P0x)=>P01x
P1x+b10(P2x−P1x)=>P12x
P2x+b20(P3x−P2x)=>P23x
P01x+b01(P12x−P01x)=>P012x
P12x+b11(P23x−P12x)=>P123x
P012x+b02(P123x−P012x)=>P0123x
【0110】
y座標を計算:
P0y+b00(P1y−P0y)=>P01y
P1y+b10(P2y−P1y)=>P12y
P2y+b20(P3y−P2y)=>P23y
P01y+b01(P12y−P01y)=>P012y
P12y+b11(P23y−P12y)=>P123y
P012y+b02(P123y−P012y)=>P0123y
【0111】
z座標を計算:
P0z+b00(P1z−P0z)=>P01z
P1z+b10(P2z−P1z)=>P12z
P2z+b20(P3z−P2z)=>P23z
P01z+b01(P12z−P01z)=>P012z
P12z+b11(P23z−P12z)=>P123z
P012z+b02(P123z−P012z)=>P0123z
【0112】
座標値をストア:
st P0123x
st P0123y
st P0123z
【0113】
頂点データ出力部36は、得られたパラメトリック曲面の点の座標値をメッシュの頂点座標値として、2次元パラメータ座標値(u,v)に対応づけて出力する(S26)。
【0114】
図12(a)〜(j)は、パラメトリック曲面のu方向、v方向に制御点を内挿して、2次元パラメータ座標値(u,v)に対応するパラメトリック曲面の点およびその点における接線を求める手順を模式的に示す図である。
【0115】
図12(a)は、パラメトリック曲面のパッチに対して定義された16個の制御点を示す。ここでは、同図の縦方向をu軸、横方向をv軸に取り、u方向に4つの制御点P0[j]、P1[j]、P2[j]、P3[j]を示す。[]内の添え字jは、v方向の列番号を示し、j=0〜3である。
【0116】
図12(b)は、図12(a)の16個の制御点に対して、u方向の1回目の内挿演算を施した結果を示す。u方向の1回目の内挿演算により、u方向に並ぶ各列4個の制御点P0[j]、P1[j]、P2[j]、P3[j]は、第1内分係数a00、a10、a20により内分され、各列3個ずつの内分点P01[j]、P12[j]、P23[j]が得られる。このu方向の1回目の内挿演算は、テクスチャユニット70の線形補間部72が、制御点テクスチャ52に格納された制御点を線形補間することにより行われる。
【0117】
図12(c)は、図12(b)の結果に対して、u方向の2回目の内挿演算を施した結果を示す。u方向の2回目の内挿演算により、u方向に並ぶ各列3個の内分点P01[j]、P12[j]、P23[j]は、第2内分係数a01、a11によりさらに内分され、各列2個ずつの内分点P012[j]、P123[j]が得られる。このu方向の2回目の内挿演算は、ピクセルシェーダ32の内挿演算部34により行われる。
【0118】
図12(d)は、図12(c)の結果に対して、u方向の3回目の内挿演算を施した結果を示す。u方向の3回目の内挿演算により、u方向に並ぶ各列2個の内分点P012[j]、P123[j]は、第3内分係数a02により内分され、各列1個ずつの制御点P0123[j]が得られる。このu方向の3回目の内挿演算も、内挿演算部34により行われる。
【0119】
図12(b)から(d)までの処理により、u方向の3回の内挿演算が完了し、v方向に並ぶ4個の内分点P0123[0]、P0123[1]、P0123[2]、P0123[3]が得られる。
【0120】
図12(e)は、図12(d)の結果に対して、v方向の1回目の内挿演算を施した結果を示す。v方向の1回目の内挿演算により、v方向に並ぶ4個の内分点P0123[0]、P0123[1]、P0123[2]、P0123[3]は、第1内分係数b00、b10、b20により内分され、3個の内分点P0123_01、P0123_12、P0123_23が得られる。このv方向の1回目の内挿演算は、内挿演算部34により行われる。
【0121】
図12(f)は、図12(e)の結果に対して、v方向の2回目の内挿演算を施した結果を示す。v方向の2回目の内挿演算により、v方向に並ぶ3個の内分点P0123_01、P0123_12、P0123_23は、第2内分係数b01、b11により内分され、2個の内分点P0123_012、P0123_123が得られる。このv方向の2回目の内挿演算も、内挿演算部34により行われる。
【0122】
図12(g)は、図12(f)の結果に対して、v方向の3回目の内挿演算を施した結果を示す。v方向の3回目の内挿演算により、v方向に並ぶ2個の内分点P0123_012、P0123_123は、3回目の内分係数b02により内分され、1個の内分点P0123_0123が得られる。このv方向の3回目の内挿演算も、内挿演算部34により行われる。
【0123】
図12(e)から(g)までの処理により、v方向の3回の内挿演算が完了し、最終的に1個の内分点P0123_123が得られる。これが2次元パラメータ座標値(u,v)に対応するパラメトリック曲面上の点である。
【0124】
最終的に得られた頂点P0123_123におけるu方向、v方向の接線を求めるには、図12(c)に示したu方向に2回の内挿演算を施した結果に対して、v方向に2回の内挿演算を施す。
【0125】
図12(h)は、図12(c)の結果に対して、v方向に1回目の内挿演算を施した結果を示す。このv方向の1回目の内挿演算により、1行目のv方向に並ぶ4個の内分点P012[0]、P012[1]、P012[2]、P012[3]は、第1内分係数b00、b10、b20により内分され、3個の内分点P012_01、P012_12、P012_23が得られる。同様に、2行目のv方向に並ぶ4個の内分点P123[0]、P123[1]、P123[2]、P123[3]は、第1内分係数b00、b10、b20により内分され、3個の内分点P123_01、P123_12、P123_23が得られる。このv方向の1回目の内挿演算は、内挿演算部34により行われる。
【0126】
図12(i)は、図12(h)の結果に対して、v方向に2回目の内挿演算を施した結果を示す。このv方向の2回目の内挿演算により、1行目のv方向に並ぶ3個の内分点P012_01、P012_12、P012_23は、第2内分係数b01、b11により内分され、2個の内分点P012_012、P012_123が得られる。同様に、2行目のv方向の並ぶ3個の内分点P123_01、P123_12、P123_23は、第2内分係数b01、b11により内分され、2個の内分点P123_012、P123_123が得られる。
【0127】
図12(j)は、図12(i)の結果から、図12(g)の頂点座標P0123_0123におけるu方向およびv方向の接線を求めた結果を示す。内挿演算部34は、図12(i)の4つの内分点の内、上側の2点P012_012、P123_012の中点U、下側の2点P123_012、P123_123の中点D、左側の2点P012_012、P123_012の中点L、右側の2点P012_123、P123_123の中点Rを求める。頂点座標P0123_0123におけるu方向の接線ベクトルは、上側の中点Uと下側の中点Dの差分ベクトルで与えられ、v方向の接線ベクトルは、左側の中点Lと右側の中点Rの差分ベクトルで与えられる。
【0128】
以下、NURBS曲面のノットパターンは、隣接するパッチの接続性を考慮すると9種類に限定することができること、およびNURBS曲面の制御点を内挿演算するときに用いられる内分係数がパラメータtの1次式で表されることについて詳しく説明する。
【0129】
NURBS曲面は、2つのパラメータu、vを媒介変数としたパラメトリック曲面であり、パラメトリック曲面のパッチの形状は、16個の制御点P0〜P15と、パラメータu、vの変化に伴う各制御点の影響力の変化を表す節点(ノット)の列であるノットベクトルによって操作される。パラメトリック曲面をu方向またはv方向で見た場合、パラメータuまたはvを媒介変数としたパラメトリック曲線と見ることができ、パラメトリック曲線のセグメントの形状は、u方向またはv方向の4個の制御点とノットベクトルによって操作される。
【0130】
パラメトリック曲面をパッチ毎に生成し、隣り合うパッチをつなぎ合わせることで1つの曲面を形成するが、パッチのつなぎ目において滑らかな連続性を確保するために、各パッチのu、v方向のそれぞれに適用すべきノットベクトルを定める。本実施の形態では、隣接パッチ間の接続性を考慮してパッチに適用するノットパターンを9種類に限定している。すなわち、任意のNURBS曲面を用いるのではなく、9種類のノットパターンで決まるNURBS曲面で描画対象オブジェクトの自由曲面をモデル化する。
【0131】
パラメトリック曲面をu、vいずれかの方向で見ると、パラメトリック曲線として考えることができるため、ここではパラメトリック曲線のノットパターンを説明する。ノットパターンはu方向、v方向に独立に指定することができる。
【0132】
4階すなわち3次のBスプライン曲線の場合、1セグメントは4つの制御点で定義される。5つの制御点でBスプライン曲線を定義する場合は2セグメント、6つの制御点でBスプライン曲線を定義する場合は3セグメントとなる。
【0133】
1つのセグメントに対して、9つのタイプのノットパターンのいずれかを用いる。曲線の形状を決める制御点の数によって、隣接セグメント間の接続性を考慮して、使用すべきノットパターンのタイプと順序を定める。
【0134】
隣接セグメント間を接続性を考慮する場合、セグメントの端点における滑らかな連続性が問題となる。1つのセグメントに注目したとき、セグメントの端点が制御点と一致する場合、その端点はオープンであるといい、一致しない場合はクローズであるという。さらに、曲線の接続性を考慮して、注目しているセグメントの前後に隣接するセグメントの端点が制御点と一致しているかどうか、すなわちオープンであるか、クローズであるかを区別する。さらに、注目セグメントの端点がクローズである場合、その端点を共有して接続している隣接セグメントの端点のオープン/クローズを考慮に入れ、その注目セグメントのノットパターンを決める。
【0135】
セグメントの接続関係を、注目セグメントの始点および終点のオープン/クローズと、その注目セグメントの始点側に隣接するセグメントの始点のオープン/クローズと、その注目セグメントの終点側に隣接するセグメントの終点のオープン/クローズの組み合わせによって、「(始点側隣接セグメントの始点のオープン/クローズ):(注目セグメントの始点のオープン/クローズ)−(注目セグメントの終点のオープン/クローズ):(終点側隣接セグメントの終点のオープン/クローズ)」の形式で表すことにする。
【0136】
図13(a)〜(c)は、制御点が4個、5個、および6個の場合のノットパターンについて説明する図である。
【0137】
図13(a)は、4個の制御点Q0〜Q3でNURBS曲線を定義する際に使用されるノットパターンであり、これをタイプ2とする。セグメントの始点、終点はそれぞれ制御点Q0、Q3に一致しており、オープンである。このノットパターンはベジェ曲線に一致する。
【0138】
図13(b)は、5個の制御点Q0〜Q4でNURBS曲線を定義する際に使用されるノットパターンを示す。この場合、NURBS曲線は第1、第2のセグメントを接続点E1でつなげて表される。
【0139】
第1セグメントの始点は制御点Q0に一致しており、オープンである。一方、第1セグメントの終点は、第2セグメントの始点と一致することで連続性が保たれており、いずれの制御点とも一致しないので、クローズである。また、第1セグメントの終点側隣接セグメントである第2セグメントの終点は、制御点Q4と一致し、オープンである。したがって、第1セグメントの接続関係は「オープン−クローズ:オープン」で表される。これをタイプ3とする。
【0140】
第2セグメントの始点は、第1セグメントの終点と接続し、いずれの制御点とも一致しないから、クローズであり、第2セグメントの終点は、制御点Q4に一致し、オープンである。第2セグメントの始点側隣接セグメントである第1セグメントの始点は、制御点Q0と一致し、オープンである。したがって、第2セグメントの接続関係は「オープン:クローズ−オープン」で表される。これをタイプ7とする。
【0141】
図13(c)は、6個の制御点Q0〜Q5でNURBS曲線を定義する際に使用されるノットパターンを示す。この場合、NURBS曲線は第1、第2、第3のセグメントを2つの接続点E1、E2でつなげて表される。
【0142】
第1セグメントの始点は制御点Q0に一致し、オープンであり、第1セグメントの終点は、第2セグメントの始点と接続し、いずれの制御点とも一致せず、クローズである。第1セグメントの終点側隣接セグメントである第2セグメントの終点は、いずれの制御点とも一致せず、クローズである。したがって、第1セグメントの接続関係は「オープン−クローズ:クローズ」で表される。これをタイプ4とする。
【0143】
第2セグメントの始点は、第1セグメントの終点と接続し、いずれの制御点とも一致せず、クローズであり、第2セグメントの終点は、第3セグメントの始点と接続し、いずれの制御点とも一致せず、クローズである。また、第2セグメントの始点側隣接セグメントである第1セグメントの始点は、制御点Q0に一致し、オープンであり、第2セグメントの終点側隣接セグメントである第3セグメントの終点は、制御点Q5に一致し、オープンである。したがって、第2セグメントの接続関係は「オープン:クローズ−クローズ:オープン」で表される。これをタイプ5とする。
【0144】
第3セグメントの始点は、第2セグメントの終点と接続し、いずれの制御点とも一致せず、クローズであり、第3セグメントの終点は、制御点Q5に一致し、オープンである。また、第3セグメントの始点側隣接セグメントである第2セグメントの始点は、クローズである。したがって、第3セグメントの接続関係は「クローズ:クローズ−オープン」で表される。これをタイプ6とする。
【0145】
図14(a)〜(c)は、制御点が7個、8個、および9個以上の場合のノットパターンについて説明する図である。
【0146】
図14(a)は、7個の制御点Q0〜Q6でNURBS曲線を定義する際に使用されるノットパターンを示す。この場合、NURBS曲線は第1〜第4のセグメントを3つの接続点E1〜E3でつなげて表される。
【0147】
第1セグメントは既に説明したタイプ4である。
【0148】
第2セグメントの始点は、第1セグメントの終点と接続し、いずれの制御点とも一致せず、クローズであり、第2セグメントの終点は、第3セグメントの始点と接続し、いずれの制御点とも一致せず、クローズである。また、第2セグメントの始点側隣接セグメントである第1セグメントの始点は、制御点Q0に一致し、オープンであり、第2セグメントの終点側隣接セグメントである第3セグメントの終点は、いずれの制御点とも一致せず、クローズである。したがって、第2セグメントの接続関係は「オープン:クローズ−クローズ:クローズ」で表される。これをタイプ8とする。
【0149】
第3セグメントの始点は、第2セグメントの終点と接続し、いずれの制御点とも一致せず、クローズであり、第3セグメントの終点は、第4セグメントの始点と接続し、いずれの制御点とも一致せず、クローズである。また、第3セグメントの始点側隣接セグメントである第2セグメントの始点は、クローズであり、第3セグメントの終点側隣接セグメントである第4セグメントの終点は、制御点Q6に一致し、オープンである。したがって、第3セグメントの接続関係は「クローズ:クローズ−クローズ:オープン」で表される。これをタイプ9とする。
【0150】
第4セグメントは既に説明したタイプ6である。
【0151】
図14(b)は、8個の制御点Q0〜Q7でNURBS曲線を定義する際に使用されるノットパターンを示す。この場合、NURBS曲線は第1〜第5のセグメントを4つの接続点E1〜E4でつなげて表される。
【0152】
第1セグメントは既に説明したタイプ4、第2セグメントはタイプ8である。
【0153】
第3セグメントの始点は、第2セグメントの終点と接続し、いずれの制御点とも一致せず、クローズであり、第3セグメントの終点は、第4セグメントの始点と接続し、いずれの制御点とも一致せず、クローズである。また、第3セグメントの始点側隣接セグメントである第2セグメントの始点は、クローズであり、第3セグメントの終点側隣接セグメントである第4セグメントの終点は、いずれの制御点とも一致せず、クローズである。第1セグメントの接続関係は「クローズ:クローズ−クローズ:クローズ」で表される。これをタイプ1とする。
【0154】
第4セグメントは既に説明したタイプ9、第5セグメントはタイプ6である。
【0155】
図14(c)は、9個以上の制御点、ここでは10個の制御点Q0〜Q9でNURBS曲線を定義する際に使用するノットパターンを示す。この場合、NURBS曲線は第1〜第7のセグメントを6個の接続点E1〜E6でつなげて表される。一般に、n個の制御点が与えられたとき、NURBS曲線は(n−3)個のセグメントをつなげて表される。
【0156】
この場合、第1〜第7のセグメントは、順にタイプ4、タイプ8、タイプ1、タイプ1、タイプ1、タイプ9、タイプ6になる。このように、9個以上の制御点の場合、中央にタイプ1のセグメントが挿入して接続することになる。
【0157】
図15に、図13(a)〜(c)および図14(a)〜(c)で述べたノットパターンのタイプ1〜9について、セグメントの接続関係をまとめる。このように注目セグメントの端点のオープン/クローズと、隣接セグメントの端点のオープン/クローズによって、ノットパターンが9種類に分けられる。
【0158】
図16(a)〜(c)は、パラメトリック曲面に対してu方向、v方向に適用されるノットパターンのタイプを説明する図である。
【0159】
図16(a)は、u方向に4個の制御点、v方向に5個の制御点が設けられた連続するパラメトリック曲面の模式図である。このパラメトリック曲面のu方向は、図13(a)に示した4個の制御点の場合に相当するから、u方向にはタイプ2のノットパターンが適用される。一方、パラメトリック曲面のv方向は、図13(b)に示した5個の制御点の場合に相当するから、v方向の1つ目のセグメントにはタイプ3のノットパターンが適用され、2つ目のセグメントにはタイプ7のノットパターンが適用される。
【0160】
図16(b)は、u方向に8個の制御点、v方向に6個の制御点が設けられた連続するパラメトリック曲面の模式図である。このパラメトリック曲面のu方向は、図14(b)に示した8個の制御点の場合に相当するから、u方向の各セグメントにはタイプ4、8、1、9、6の順でノットパターンが適用される。一方、パラメトリック曲面のv方向は、図13(c)に示した6個の制御点の場合に相当するから、各セグメントにはタイプ4、5、6の順でノットパターンが適用される。
【0161】
図16(c)は、u、v方向の制御点の個数によって、適用されるノットパターンのタイプの順序をまとめた表である。ラスタライザ10は、この表を用いて、パラメトリック曲面のu方向およびv方向の制御点の個数により、u方向、v方向のそれぞれの各セグメントに適用されるノットパターンのタイプの順序を決定する。決定されたノットパターンのタイプは、各パッチのパラメータ情報としてシェーダユニット30に与えられる。
【0162】
次に、NURBS曲面の制御点を内分するための内分係数が1次式で与えられることを説明する。
【0163】
まず、Bスプライン曲線について説明する。M階すなわち(M−1)次のBスプライン曲線の式P(t)は、制御点Q0,Q1,…,Qnを用いて、
P(t)=N0,M(t)Q0+N1,M(t)Q1+…+Nn,4(t)Qn
と書ける。
【0164】
ここで、N0,M,N1,M,…,Nn,Mは、Bスプライン基底関数であり、混ぜ合わせ関数とも呼ばれる。Bスプライン基底関数Nj,Mは、次のドゥ・ブァ・コックス(de Boor Cox)の漸化式により再帰的に求めることができる。
【0165】
Nj,M(t)=(t−tj)/(tj+M−1−tj)・Nj,M−1(t)+(tj+M−t)/(tj+M−tj+1)・Nj+1,M−1(t)
ただし、Nj,1(t)=1(tj≦t<tj+1),Nj,1(t)=0(それ以外)である。
【0166】
この漸化式に現れるtj,tj+Mなどは、パラメータtの節目すなわちノットである。Bスプライン基底関数あるいは混ぜ合わせ関数Nj,Mは、ノットを数値の列で表した次のノットベクトルTにもとづいて定められる。
T=[t0,t1,…,tM+N−1]
ここで、Nは制御点数、Mは階数である。ノットベクトルの要素数は、制御点数Nと階数Mの和である。
【0167】
ノットベクトルTのノット間隔が一定である場合には、ユニフォームであるといい、ノット間隔が一定でない場合は、ノンユニフォームであるという。
【0168】
ノンユニフォームで有理化されたBスプライン曲線がNURBS曲線である。NURBS曲線では、ノットベクトルTのノット間隔が可変であるため、ノット間隔の比で曲線の微分係数を補正することができ、曲線の形状を制御するのが容易であり、また、曲線の形状を局所的に変化させることも可能である。また、NURBS曲線は、Bスプライン曲線以外にもベジェ曲線、エルミート曲線などの曲線も表現することができ、いろいろな曲線を同一形式で表せるという利点もある。さらに、NURBSでは、有理化すなわち同次座標を用いた中心投影が行われているため、制御点に対する重みを設定することができ、有利化されていないBスプライン曲線では表現することができない真円なども表現することができる。
【0169】
また、混ぜ合わせ関数の値を求めるための上記のドゥ・ブァ・コックスの漸化式は、再帰的に演算できるため、コンピュータのレジスタや演算器などのハードウエア資源を用いて繰り返し計算するのに適している。
【0170】
本実施の形態では、4つの制御点で定まる4階すなわち3次のBスプライン曲線を扱うから、M=4、N=4の場合を考えればよい。たとえば、制御点数が4個で4階のユニフォームなBスプライン曲線のノットベクトルTはT=[−3,−2,−1,0,1,2,3,4]で与えられる。
【0171】
図17は、階数Mが4、制御点数Nが4のBスプライン曲線について、ドゥ・ブァ・コックスの漸化式により、Bスプライン基底関数を計算する過程を説明する図である。
【0172】
セグメントのパラメータtは、[0,1]の区間で変化し、9タイプのノットパターンのノットベクトルTは、すべてT=[*,*,*,0,1,*,*,*]と定義する。ここで*はタイプにより異なる値である。この場合、いずれのノットパターンのタイプでも、1階のBスプライン基底関数はNj,1=[0,0,0,1,0,0,0]である。
【0173】
ドゥ・ブァ・コックスの漸化式によれば、M階のj番目のBスプライン基底関数Nj,Mは、(M−1)階のj番目のBスプライン基底関数Nj,M−1と(M−1)階の(j+1)番目のBスプライン基底関数Nj+1,M−1を混ぜ合わせたものであるから、1階のBスプライン基底関数はNj,1=[0,0,0,1,0,0,0]を起点として、2階、3階、4階と順に計算していくことで、4階までのBスプライン基底関数をすべて求めることができる。同図は、この計算過程を表したものである。
【0174】
たとえば、2階のBスプライン基底関数は1階のBスプライン基底関数を用いて、
N2,2(t)=0+(t4−t)/(t4−t3)・N3,1(t)
N3,2(t)=(t−t3)/(t4−t3)・N3,1(t)+0
などと計算される。
【0175】
同様に、3階のBスプライン基底関数は2階のBスプライン基底関数を用いて、
N1,3(t)=0+(t4−t)/(t4−t2)・N2,2(t)
N2,3(t)=(t−t2)/(t4−t2)・N2,2(t)+(t5−t)/(t5−t3)・N3,2(t)
N3,3(t)=(t−t3)/(t5−t3)・N3,2(t)+0
などと計算される。
【0176】
ここで、ドゥ・ブァ・コックスの漸化式において、(M−1)階のj番目のBスプライン基底関数Nj,M−1と(M−1)階の(j+1)番目のBスプライン基底関数Nj+1,M−1を混ぜ合わせるときの混ぜ合わせ係数を説明の簡単のため、次のようにおく。
Aj,M=(t−tj)/(tj+M−1−tj)
Bj,M=(tj+M−t)/(tj+M−tj+1)
【0177】
混ぜ合わせ係数Aj,M、Bj,Mを用いれば、ドゥ・ブァ・コックスの漸化式は次のように書ける。
Nj,M(t)=Aj,M、・Nj,M−1(t)+Bj,M・Nj+1,M−1(t)
【0178】
図18は、図17の計算過程を混ぜ合わせ係数Aj,M、Bj,Mを用いて書き換えたものである。この計算過程によれば、Bスプライン基底関数は次の漸化式で求められる。
【0179】
4階のBスプライン基底関数を求める漸化式:
N0,4(t)=B0,4N1,3(t)
N1,4(t)=A1,4N1,3(t)+B1,4N2,3(t)
N2,4(t)=A2,4N2,3(t)+B2,4N3,3(t)
N3,4(t)=A3,4N3,3(t)
【0180】
3階のBスプライン基底関数を求める漸化式:
N1,3(t)=B1,3N2,2(t)
N2,3(t)=A2,3N2,2(t)+B2,3N3,2(t)
N3,3(t)=A3,3N3,2(t)
【0181】
2階のBスプライン基底関数を求める漸化式:
N2,2(t)=B2,2N3,1(t)
N3,2(t)=A3,2N3,1(t)
【0182】
1階のBスプライン基底関数は、
N3,1(t)=1である。
【0183】
Bスプライン曲線の式P(t)に、上記の4階のBスプライン基底関数を求める漸化式を適用すると、次のように変形できる。
P(t)=Q0N0,4(t)+Q1N1,4(t)+Q2N2,4(t)+Q3N3,4(t)
=Q0{B0,4N1,3(t)}
+Q1{A1,4N1,3(t)+B1,4N2,3(t)}
+Q2{A2,4N2,3(t)+B2,4N3,3(t)}
+Q3{A3,4N3,3(t)}
=N1,3(t){Q0B0,4+Q1A1,4}
+N2,3(t){Q1B1,4+Q2A2,4}
+N3,3(t){Q2B2,4+Q3A3,4}
【0184】
ここで、B0,4+A1,4=(t4−t)/(t4−t1)+(t−t1)/(t4−t1)=1であることに注意すると、Q0B0,4+Q1A1,4は、2点Q0、Q1をA1,4:B0,4の比で内分する点Q01を求める演算であることがわかる。
【0185】
一般的には、Bj,M+Aj+1,M=(tj+M−t)/(tj+M−tj+1)+(t−tj+1)/(tj+M−tj+1)=1であるから、Q1B1,4+Q2A2,4は、2点Q1、Q2をA2,4:B1,4の比で内分する点Q12を求める演算であり、Q2B2,4+Q3A3,4は、2点Q2、Q3をA3,4:B2,4の比で内分する点Q23を求める演算である。
【0186】
したがって、式P(t)は、内分点Q01、Q12、Q23を用いて、
P(t)=N1,3(t)Q01+N2,3(t)Q12+N3,3(t)Q23
と書くことができる。
【0187】
さらに、この式に、3階のBスプライン基底関数を求める漸化式を適用すると、次のように変形できる。
P(t)=Q01{B1,3N2,2(t)}
+Q12{A2,3N2,2(t)+B2,3N3,2(t)}
+Q23{A3,3N3,2(t)}
=N2,2(t){Q01B1,3+Q12A2,3}
+N3,2(t){Q12B2,3+Q23A3,3}
【0188】
ここで、Q01B1,3+Q12A2,3は、2点Q01、Q12をA2,3:B1,3の比で内分する点Q012を求める演算であり、Q12B2,3+Q23A3,3は、2点Q12、Q23をA3,3:B2,3の比で内分する点Q123を求める演算である。
【0189】
したがって、式P(t)は、内分点Q012、Q123を用いて、
P(t)=N2,2(t)Q012+N3,2(t)Q123
と書くことができる。
【0190】
さらに、この式に、2階のBスプライン基底関数を求める漸化式を適用すると、次のように変形できる。
P(t)=Q012B2,2N3,1(t)+Q123A3,2N3,1(t)
=N3,1(t){Q012B2,2+Q123A3,2}
【0191】
ここで、Q012B2,2+Q123A3,2は、2点Q012、Q123をA3,2:B2,2の比で内分する点Q0123を求める演算である。
【0192】
したがって、式P(t)は、内分点Q0123を用いて、
P(t)=N3,1(t)Q0123
と書くことができる。ここで、1階のBスプライン基底関数N3,1(t)は1であるから、P(t)=Q0123である。
【0193】
以上のことから、4つの制御点Q0、Q1、Q2、Q3に対して、隣り合う点の間で内分計算を再帰的に3回繰り返すことにより、4階のBスプライン曲線のパラメータtに対応する点P(t)を求められることがわかる。
【0194】
すなわち、1回目の内分計算では、4つの制御点Q0、Q1、Q2、Q3について、隣り合う制御点間で内分を計算し、3つの内分点Q01、Q12、Q23を求める。2回目は、その3つの内分点Q01、Q12、Q23について、隣り合う内分点間で内分を計算し、2つの内分点Q012、Q123を求める。3回目は、その2つの内分点Q012、Q123について内分を計算して、内分点Q0123を求める。3回目の内分計算の結果得られた内分点Q0123が点P(t)である。
【0195】
以上で説明した制御点を再帰点に内分することでBスプライン曲線上の点を求める方法は、ド・カステリョ(de Casteljau)のアルゴリズムとして知られている計算方法を応用したものである。ド・カステリョのアルゴリズムは、一般的にはベジェ曲線に対して知られている計算方法であるが、このように、ドゥ・ブァ・コックスの漸化式を変形することで、Bスプライン曲線に対してもド・カステリョのアルゴリズムを適用できることがわかる。
【0196】
4つの制御点Q0、Q1、Q2、Q3から4階のBスプライン曲線の点を求めるための漸化式をまとめると、次のようになる。
【0197】
1回目の内分計算:
Q01=(t4−t)/(t4−t1)・Q0+(t−t1)/(t4−t1)・Q1
Q12=(t5−t)/(t5−t2)・Q1+(t−t2)/(t5−t2)・Q2
Q23=(t6−t)/(t6−t3)・Q2+(t−t3)/(t6−t3)・Q3
【0198】
2回目の内分計算:
Q012=(t4−t)/(t4−t2)・Q01+(t−t2)/(t4−t2)・Q12
Q123=(t5−t)/(t5−t3)・Q12+(t−t3)/(t5−t3)・Q23
【0199】
3回目の内分計算:
Q0123=(t4−t)/(t4−t3)・Q012+(t−t3)/(t4−t3)・Q123
【0200】
ここで、内分係数を
a00(t)=(t−t1)/(t4−t1)
a10(t)=(t−t2)/(t5−t2)
a20(t)=(t−t3)/(t6−t3)
a01(t)=(t−t2)/(t4−t2)
a11(t)=(t−t3)/(t5−t3)
a02(t)=(t−t3)/(t4−t3)
とおくと、
【0201】
1回目の内分計算:
Q01=(1−a00(t))Q0+a00(t)Q1
Q12=(1−a10(t))Q1+a10(t)Q2
Q23=(1−a20(t))Q2+a20(t)Q3
【0202】
2回目の内分計算:
Q012=(1−a01(t))Q01+a01(t)Q12
Q123=(1−a11(t))Q12+a11(t)Q23
【0203】
3回目の内分計算:
Q0123=(1−a02(t))Q012+a02(t)Q123
と書ける。
【0204】
ノットパターンの各タイプに対して、ノットベクトルT=[t0,t1,…,t7]を次のように定義する。ただし、t0とt7は計算に関与しないため、任意の値でよい。また、各ノットベクトルTに対して定まる内分係数を示す。
【0205】
タイプ1:
ノットベクトルT=[−3,−2,−1,0,1,2,3,4]
このとき、内分係数は、a00(t)=(t+2)/3、a10(t)=(t+1)/3、a20(t)=t/3、a01(t)=(t+1)/2、a11(t)=t/2、a02(t)=tである。
【0206】
タイプ2:
ノットベクトルT=[0,0,0,0,1,1,1,1]
このとき、内分係数は、a00(t)=t、a10(t)=t、a20(t)=t、a01(t)=t、a11(t)=t、a02(t)=tである。
【0207】
タイプ3:
ノットベクトルT=[0,0,0,0,1,2,2,2]
このとき、内分係数は、a00(t)=t、a10(t)=t/2、a20(t)=t/2、a01(t)=t、a11(t)=t/2、a02(t)=tである。
【0208】
タイプ4:
ノットベクトルT=[0,0,0,0,1,2,3,4]
このとき、内分係数は、a00(t)=t、a10(t)=t/2、a20(t)=t/3、a01(t)=t、a11(t)=t/2、a02(t)=tである。
【0209】
タイプ5:
ノットベクトルT=[−1,−1,−1,0,1,2,2,2]
このとき、内分係数は、a00(t)=(t+1)/2、a10(t)=(t+1)/3、a20(t)=t/2、a01(t)=(t+1)/2、a11(t)=t/2、a02(t)=tである。
【0210】
タイプ6:
ノットベクトルT=[−3,−2,−1,0,1,1,1,1]
このとき、内分係数は、a00(t)=(t+2)/3、a10(t)=(t+1)/2、a20(t)=t、a01(t)=(t+1)/2、a11(t)=t、a02(t)=tである。
【0211】
タイプ7:
ノットベクトルT=[−1,−1,−1,0,1,1,1,1]
このとき、内分係数は、a00(t)=(t+1)/2、a10(t)=(t+1)/2、a20(t)=t、a01(t)=(t+1)/2、a11(t)=t、a02(t)=tである。
【0212】
タイプ8:
ノットベクトルT=[−1,−1,−1,0,1,2,3,4]
このとき、内分係数は、a00(t)=(t+1)/2、a10(t)=(t+1)/3、a20(t)=t/3、a01(t)=(t+1)/2、a11(t)=t/2、a02(t)=tである。
【0213】
タイプ9:
ノットベクトルT=[−3,−2,−1,0,1,2,2,2]
このとき、内分係数は、a00(t)=(t+2)/3、a10(t)=(t+1)/3、a20(t)=t/2、a01(t)=(t+1)/2、a11(t)=t/2、a02(t)=tである。
【0214】
図19にノットパターンのタイプ毎の内分係数をまとめて示す。このように内分係数は、すべてtの一次式で表される。テセレーション処理の際、パラメトリック曲線のパッチの分割数に応じて、パラメータtは[0,1]の区間で所定の間隔で離散的な値を取る。Bスプライン曲線上の点を求めるために、パラメータtの離散値のすべてについて、内分係数aij(t)の値が計算上必要となる。しかし、パラメータtの離散値のすべてについて内分係数aij(t)の値を用意しておかなくても、内分係数aij(t)がパラメータtの一次式で表されることから、t=0、1のときの内分係数の始値aij(0)、終値aij(1)の2つを記憶しておけば、任意のt(0<t<1)の値に対するaij(t)は、始値aij(0)と終値aij(1)をt:(1−t)の比で線形補間することにより、求めることができる。本実施の形態では、この性質がテクスチャユニット70において有効に利用されている。
【0215】
以上述べたように、本実施の形態によれば、パラメトリック曲面の制御点の再帰的内挿演算に必要な必要な内分計算の一部を、テクスチャユニット70の線形補間器を利用して実行するため、ピクセルシェーダ32の演算器を用いてすべての内分計算を行う場合に比べて、描画処理装置100全体の処理効率が向上する。
【0216】
また、2次元パラメータ座標値に依存して変化する内分係数の始値および終値だけをテクスチャとして保持しておくことにより、任意の2次元パラメータ座標値における内分係数をテクスチャの補間計算により効率良く取得することができる。また、内分係数の始値および終値だけをテクスチャに格納すればよいので、テセレーション処理に必要なメモリ量を少なく抑えることができる。また、パラメトリック曲面の制御点についても、テクスチャとして保持しておくことで、最初の内挿演算をテクスチャの補間計算により効率良く行うことができる。
【0217】
以上、本発明を実施の形態をもとに説明した。実施の形態は例示であり、それらの各構成要素や各処理プロセスの組合せにいろいろな変形例が可能なこと、またそうした変形例も本発明の範囲にあることは当業者に理解されるところである。そのような変形例を説明する。
【0218】
上記の説明では、2次元パラメータ座標系で定義されるパラメトリック曲面をパッチ毎にメッシュ状に細分化するテセレーション処理を説明したが、1次元パラメータ座標系で定義されるパラメトリック曲線をセグメント毎に折れ線で細分化するテセレーション処理も同様に行うことができる。パラメトリック曲線をテセレーション処理する場合は、ラスタライザ10には描画プリミティブとしてラインプリミティブを与えればよい。
【0219】
また、上記の説明では、パラメータtに依存する内分係数の始値aij(0)と終値aij(1)を線形補間して、指定されたパラメータtにおける内分係数aij(t)の値を求めたが、内分係数aij(t)はパラメータtの1次式であるから、始値と終値の組に限らず、任意の異なる2つのパラメータ値t1,t2における内分係数aij(t1)、aij(t2)を代表値として内分係数テクスチャ54に記憶しておき、これらの代表値を線形補間することにより、指定されたパラメータtにおける内分係数aij(t)の値を求めてもよい。なお、この線形補間には、内挿だけでなく、外挿も含まれる。
【0220】
また、実施の形態では、制御点に対するu方向の最初の内挿演算だけをテクスチャユニット70の線形補間機能を用いて行ったが、2回目、3回目の内挿演算についてもテクスチャユニット70の線形補間機能を用いて行ってもよい。その場合、ピクセルシェーダ32が、テクスチャユニット70から第1内分係数であらかじめ内分された制御点を受け取った後、その内分された制御点をテクスチャユニット70に投入することのできるインタフェースを設ける。テクスチャユニット70は、線形補間器により、ピクセルシェーダ32から投入された制御点を第2内分係数でさらに内分して、ピクセルシェーダ32に出力する。ピクセルシェーダ32は、テクスチャユニット70から受け取った第2内分係数で内分された制御点をさらにテクスチャユニット70に投入し、テクスチャユニット70は、それを第3内分係数でさらに内分して、ピクセルシェーダ32に返す。このようにすれば、テセレーション処理に必要なすべての内分演算をテクスチャユニット70の線形補間機能を用いて実現することができる。また、テクスチャユニット70の線形補間部72が線形補間結果をフィードバックして再入力できるように構成されていてもよい。
【図面の簡単な説明】
【0221】
【図1】実施の形態に係る描画処理装置の構成図である。
【図2】図1のラスタライザに入力される正方形プリミティブを説明する図である。
【図3】パラメトリック曲面の最小構成単位であるパッチを説明する図である。
【図4】パラメトリック曲線の上の点を求める手順を説明する図である。
【図5】4つの制御点の内分を繰り返すことにより、パラメトリック曲線上の点が求められる様子を示す図である。
【図6】テセレーション処理を行うための図1のピクセルシェーダおよびテクスチャユニットの構成を示す図である。
【図7】図6の制御点テクスチャのデータ構造を説明する図である。
【図8】図6の内分係数テクスチャのデータ構造を説明する図である。
【図9】図6のピクセルシェーダおよびテクスチャユニットによるテセレーション処理の手順を説明するフローチャートである。
【図10】テクスチャロード命令により、内分係数の始値と終値から補間値が得られる様子を説明する図である。
【図11】テクスチャロード命令により、制御点が内挿される様子を説明する図である。
【図12】2次元パラメータ座標値に対応するパラメトリック曲面の点およびその点における接線を求める手順を模式的に示す図である。
【図13】制御点が4個、5個、および6個の場合のノットパターンについて説明する図である。
【図14】制御点が7個、8個、および9個以上の場合のノットパターンについて説明する図である。
【図15】ノットパターンの各タイプについて、セグメントの接続関係をまとめた図である。
【図16】パラメトリック曲面に対して2次元パラメータ座標系の各方向に適用されるノットパターンのタイプを説明する図である。
【図17】階数が4、制御点数が4のBスプライン曲線について、漸化式によりBスプライン基底関数を計算する過程を説明する図である。
【図18】図17の計算過程を混ぜ合わせ係数を用いて書き換えた図である。
【図19】ノットパターンのタイプ毎の内分係数をまとめた図である。
【符号の説明】
【0222】
10 ラスタライザ、 30 シェーダユニット、 32 ピクセルシェーダ、 34 内挿演算部、 36 頂点データ出力部、 50 メモリ、 52 制御点テクスチャ、 54 内分係数テクスチャ、 56 テセレーションデータ、 70 テクスチャユニット、 72 線形補間部、 74 アドレス生成部、 100 描画処理装置。
【特許請求の範囲】
【請求項1】
1つのパラメータに対して座標点を対応づけることにより表されるパラメトリック曲線により描画対象物を近似処理する描画処理装置であって、
前記パラメトリック曲線を構成する単位であるセグメントに対して定義される1次元パラメータ座標系におけるパラメータの1次関数で表される内分係数について、前記パラメータの定義域内の2つの点における前記内分係数の代表値の組を保持する係数データ記憶部と、
処理対象のセグメントにおいて指定される前記パラメータの指定値を補間係数として、前記係数データ記憶部に記憶された前記内分係数の代表値の組を線形補間器により補間演算することにより、前記パラメータの指定値に対応する前記内分係数の補間値を算出する補間処理部と、
前記内分係数の補間値にもとづいた比で、当該処理対象のセグメントの形状を決める複数の制御点を内挿演算することにより、当該処理対象のセグメントにおいて前記パラメータの指定値に対応する前記パラメトリック曲線上の頂点座標を算出する細分化処理部とを含むことを特徴とする描画処理装置。
【請求項2】
前記細分化処理部による前記内挿演算は、前記内分係数の補間値にもとづいた比で前記セグメント内の前記複数の制御点を再帰的に内挿する演算であることを特徴とする請求項1に記載の描画処理装置。
【請求項3】
前記セグメントの形状を決める複数の制御点の組をセグメント毎に保持する制御点データ記憶部をさらに含み、
前記補間処理部は、前記処理対象のセグメントに適用すべき前記複数の制御点を前記制御点データ記憶部から取得し、前記内分係数の補間値にもとづいた比で、取得した前記複数の制御点を前記線形補間器によりあらかじめ内挿した上で前記細分化処理部に与え、
前記細分化処理部は、前記内分係数の補間値にもとづいた比で、前記補間処理部により内挿された前記複数の制御点をさらに内挿演算することを特徴とする請求項1または2に記載の描画処理装置。
【請求項4】
前記パラメトリック曲線の節点の間隔が非一様である場合に、前記節点の間隔が異なる節点パターンを隣接セグメントとの接続関係により複数種類に定め、前記係数データ記憶部は、前記複数種類の節点パターンの各々に対応する前記内分係数について、前記パラメータの定義域内の2つの点における前記内分係数の代表値の組を保持し、
前記補間演算部は、前記処理対象のセグメントに適用すべき前記節点パターンの指定を受け、前記パラメータの指定値にもとづいた比で、指定された前記節点パターンに対応する前記内分係数の前記代表値の組を補間演算することにより、前記パラメータの指定値に対応する前記内分係数の補間値を算出することを特徴とする請求項1から3のいずれかに記載の描画処理装置。
【請求項5】
2つのパラメータの組に対して座標点を対応づけることにより表されるパラメトリック曲面により描画対象物を近似処理する描画処理装置であって、
前記パラメトリック曲面を構成する単位であるパッチに対して定義される2次元パラメータ座標系における第1パラメータの1次関数で表される第1内分係数について、前記第1パラメータの定義域内の2つの点における前記第1内分係数の代表値の組を保持する係数データ記憶部と、
処理対象のパッチにおいて指定される前記第1パラメータの指定値を補間係数として、前記係数データ記憶部に記憶された前記第1内分係数の代表値の組を線形補間器により補間演算することにより、前記第1パラメータの指定値に対応する前記第1内分係数の補間値を算出する補間処理部と、
前記第1内分係数の補間値にもとづいた比で、当該処理対象のパッチの形状を決める複数の制御点を前記2次元パラメータ座標系の第1パラメータ軸方向に内挿演算する細分化処理部とを含むことを特徴とする描画処理装置。
【請求項6】
前記係数データ記憶部は、前記2次元パラメータ座標系における第2パラメータの1次関数で表される第2内分係数について、前記第2パラメータの定義域内の2つの点における前記第2内分係数の代表値の組を保持し、
前記補間処理部は、当該処理対象のパッチについて指定される前記第2パラメータの指定値を補間係数として、前記第2内分係数の代表値の組を線形補間器により補間演算することにより、前記第2パラメータの指定値に対応する前記第2内分係数の補間値を算出し、
前記細分化処理部は、前記第2内分係数の補間値にもとづいた比で、前記第1パラメータ軸方向に内挿された前記複数の制御点をさらに前記2次元パラメータ座標系の第2パラメータ軸方向に内挿演算することにより、当該処理対象のパッチにおいて前記2次元パラメータ座標の指定値に対応する前記パラメトリック曲面上の頂点座標を算出することを特徴とする請求項5に記載の描画処理装置。
【請求項7】
テクスチャに関するデータを記憶するテクスチャ記憶部と、
描画処理単位に対して定義されるパラメータ座標の指定値にもとづいて、前記テクスチャ記憶部に記憶された前記テクスチャに関するデータを線形補間器により補間演算することにより、前記パラメータ座標の指定値に対応する前記テクスチャに関する補間データを算出するテクスチャ処理部と、
前記テクスチャに関する補間データを用いて、前記描画処理単位の演算処理を行う描画処理部とを含み、
前記描画処理単位は、1次元パラメータ座標で表されるパラメトリック曲線を構成する単位であるセグメント、または2次元パラメータ座標で表されるパラメトリック曲面を構成する単位であるパッチであり、
前記テクスチャ記憶部は、前記セグメントまたは前記パッチに対して定義されるパラメータ座標に依存する内分係数について、前記パラメータの定義域内の2つの点における前記内分係数の代表値の組を前記テクスチャに関するデータとして保持し、
前記テクスチャ処理部は、処理対象のセグメントまたはパッチについて前記描画処理部により順次指定されるパラメータ座標の指定値を補間係数として、前記内分係数の代表値の組を線形補間器により補間演算することにより、前記パラメータ座標の指定値に対応する前記内分係数の補間値を算出し、
前記描画処理部は、前記内分係数の補間値にもとづいた比で、当該処理対象のセグメントまたはパッチの形状を決める複数の制御点を内挿演算することにより、当該処理対象のセグメントまたはパッチにおいて前記パラメータ座標の指定値に対応する前記パラメトリック曲線またはパラメトリック曲面上の点の座標を順次算出することを特徴とする描画処理装置。
【請求項8】
前記描画処理部による前記内挿演算は、前記内分係数の補間値にもとづいた比で前記セグメントまたはパッチ内の前記複数の制御点を再帰的に内挿する演算であることを特徴とする請求項7に記載の描画処理装置。
【請求項9】
前記テクスチャ記憶部は、前記セグメントまたは前記パッチの形状を決める複数の制御点の組を前記セグメントまたは前記パッチ毎に保持し、
前記テクスチャ処理部は、前記内分係数の補間値を補間係数として、前記処理対象のセグメントまたはパッチに適用すべき前記複数の制御点を前記線形補間器により内挿し、
前記描画処理部は、前記内分係数の補間値にもとづいた比で、前記テクスチャ処理部により内挿された前記複数の制御点をさらに内挿演算することを特徴とする請求項7または8に記載の描画処理装置。
【請求項10】
テクスチャに関するデータを記憶するテクスチャ記憶部と、
描画処理単位に対して定義されるパラメータ座標の指定値にもとづいて、前記テクスチャ記憶部に記憶された前記テクスチャに関するデータを線形補間器により補間演算することにより、前記パラメータ座標の指定値に対応する前記テクスチャに関する補間データを算出するテクスチャ処理部とを含み、
前記描画処理単位は、1次元パラメータ座標で表されるパラメトリック曲線を構成する単位であるセグメント、または2次元パラメータ座標で表されるパラメトリック曲面を構成する単位であるパッチであり、
前記テクスチャ記憶部は、前記セグメントまたは前記パッチの形状を決める複数の制御点の組を前記セグメントまたは前記パッチ毎に保持し、
前記テクスチャ処理部は、処理対象のセグメントまたはパッチに適用すべき前記複数の制御点の組を前記テクスチャ記憶部から取得して線形補間器により内挿演算することにより、当該処理対象のセグメントまたはパッチにおいて指定される前記パラメータ座標の指定値に対応する前記パラメトリック曲線または前記パラメトリック曲面上の頂点座標を算出することを特徴とするテクスチャ処理装置。
【請求項11】
前記テクスチャ処理部は、前記線形補間器により内挿された前記複数の制御点を前記線形補間器に再投入することにより、前記セグメント内で前記複数の制御点を再帰的に内挿演算することを特徴とする請求項10に記載のテクスチャ処理装置。
【請求項12】
前記テクスチャ記憶部は、前記セグメントまたは前記パッチに対して定義されるパラメータ座標に依存する内分係数について、前記パラメータの定義域内の2つの点における前記内分係数の代表値の組を前記テクスチャに関するデータとして保持し、
前記テクスチャ処理部は、処理対象のセグメントまたはパッチにおいて指定されるパラメータ座標の指定値を補間係数として、前記内分係数の代表値の組を線形補間器により補間演算することにより、前記パラメータ座標の指定値に対応する前記内分係数の補間値を算出し、さらに、前記内分係数の補間値を補間係数として、前記複数の制御点を前記線形補間器により内挿演算することにより、当該処理対象のセグメントまたはパッチにおいて前記パラメータ座標の指定値に対応する前記パラメトリック曲線またはパラメトリック曲面上の点の座標を算出することを特徴とする請求項10または11に記載の描画処理装置。
【請求項13】
パラメトリック曲面の形状を決める制御点の3次元座標値がテクセル値として格納され、パラメトリック曲面の座標系におけるパラメータを指定値とするテクスチャの読み出し命令により隣接する2つの前記制御点の座標値がサンプリングされて、前記指定値に対応する制御点の補間値を計算可能に構成されたことを特徴とするテクスチャのデータ構造。
【請求項14】
パラメトリック曲面の形状を決める制御点を再帰的に内挿演算する際の内分係数の始値およぶ終値が隣接するテクセル値として格納され、パラメトリック曲面の座標系におけるパラメータを指定値とするテクスチャの読み出し命令により前記内分係数の始値および終値がサンプリングされて、前記指定値に対応する内分係数の補間値を計算可能に構成されたことを特徴とするテクスチャのデータ構造。
【請求項15】
1つのパラメータに対して座標点を対応づけることにより表されるパラメトリック曲線を折れ線に細分化するテセレーション方法であって、
前記パラメトリック曲線を構成する単位であるセグメントに対して定義される1次元パラメータ座標系におけるパラメータに依存して値が決まる内分係数について、前記パラメータの定義域の両端点における前記内分係数の値を始値および終値としてあらかじめ係数テーブルに格納しておき、処理対象のセグメントにおいて指定される前記パラメータの指定値を補間係数として、前記係数テーブルに格納された前記内分係数の始値および終値を補間することにより、前記パラメータの指定値に対応する前記内分係数の補間値を算出するステップと、
前記内分係数の補間値にもとづいた比で、当該処理対象のセグメントの形状を決める複数の制御点を内挿演算することにより、当該処理対象のセグメントにおいて前記パラメータの指定値に対応する前記パラメトリック曲線上の頂点座標を算出するステップとを含むことを特徴とするテセレーション方法。
【請求項16】
2つのパラメータの組に対して座標点を対応づけることにより表されるパラメトリック曲面をポリゴンメッシュに細分化するテセレーション方法であって、
前記パラメトリック曲面を構成する単位であるパッチに対して定義される2次元パラメータ座標系における第1パラメータに依存して値が決まる第1内分係数について、前記第1パラメータの定義域の両端点における第1内分係数の値を始値および終値としてあらかじめ係数テーブルに格納しておき、処理対象のパッチにおいて指定される前記第1パラメータの指定値を補間係数として、前記係数テーブルに格納された前記第1内分係数の始値および終値を補間することにより、前記第1パラメータの指定値に対応する前記第1内分係数の補間値を算出するステップと、
前記内分係数の補間値にもとづいた比で、当該処理対象のパッチの形状を決める複数の制御点を前記2次元パラメータ座標系の第1パラメータ軸方向に内挿演算するステップとを含むことを特徴とするテセレーション方法。
【請求項17】
前記2次元パラメータ座標系における第2パラメータに依存して値が決まる第2内分係数についても、第2パラメータの定義域の両端点における第2内分係数の値を始値および終値としてあらかじめ前記係数テーブルに格納しておき、当該処理対象のパッチにおいて指定される前記第2パラメータの指定値を補間係数として、前記係数テーブルに格納された前記第2内分係数の始値および終値を補間することにより、前記第2パラメータの指定値に対応する前記第2内分係数の補間値を算出するステップと、
前記第2内分係数の補間値にもとづいた比で、前記第1パラメータ軸方向に内挿された前記複数の制御点をさらに前記2次元パラメータ座標系の第2パラメータ軸方向に内挿演算することにより、当該処理対象のパッチにおいて前記2次元パラメータ座標の指定値に対応する前記パラメトリック曲面上の頂点座標を算出するステップとをさらに含むことを特徴とする請求項16に記載のテセレーション方法。
【請求項1】
1つのパラメータに対して座標点を対応づけることにより表されるパラメトリック曲線により描画対象物を近似処理する描画処理装置であって、
前記パラメトリック曲線を構成する単位であるセグメントに対して定義される1次元パラメータ座標系におけるパラメータの1次関数で表される内分係数について、前記パラメータの定義域内の2つの点における前記内分係数の代表値の組を保持する係数データ記憶部と、
処理対象のセグメントにおいて指定される前記パラメータの指定値を補間係数として、前記係数データ記憶部に記憶された前記内分係数の代表値の組を線形補間器により補間演算することにより、前記パラメータの指定値に対応する前記内分係数の補間値を算出する補間処理部と、
前記内分係数の補間値にもとづいた比で、当該処理対象のセグメントの形状を決める複数の制御点を内挿演算することにより、当該処理対象のセグメントにおいて前記パラメータの指定値に対応する前記パラメトリック曲線上の頂点座標を算出する細分化処理部とを含むことを特徴とする描画処理装置。
【請求項2】
前記細分化処理部による前記内挿演算は、前記内分係数の補間値にもとづいた比で前記セグメント内の前記複数の制御点を再帰的に内挿する演算であることを特徴とする請求項1に記載の描画処理装置。
【請求項3】
前記セグメントの形状を決める複数の制御点の組をセグメント毎に保持する制御点データ記憶部をさらに含み、
前記補間処理部は、前記処理対象のセグメントに適用すべき前記複数の制御点を前記制御点データ記憶部から取得し、前記内分係数の補間値にもとづいた比で、取得した前記複数の制御点を前記線形補間器によりあらかじめ内挿した上で前記細分化処理部に与え、
前記細分化処理部は、前記内分係数の補間値にもとづいた比で、前記補間処理部により内挿された前記複数の制御点をさらに内挿演算することを特徴とする請求項1または2に記載の描画処理装置。
【請求項4】
前記パラメトリック曲線の節点の間隔が非一様である場合に、前記節点の間隔が異なる節点パターンを隣接セグメントとの接続関係により複数種類に定め、前記係数データ記憶部は、前記複数種類の節点パターンの各々に対応する前記内分係数について、前記パラメータの定義域内の2つの点における前記内分係数の代表値の組を保持し、
前記補間演算部は、前記処理対象のセグメントに適用すべき前記節点パターンの指定を受け、前記パラメータの指定値にもとづいた比で、指定された前記節点パターンに対応する前記内分係数の前記代表値の組を補間演算することにより、前記パラメータの指定値に対応する前記内分係数の補間値を算出することを特徴とする請求項1から3のいずれかに記載の描画処理装置。
【請求項5】
2つのパラメータの組に対して座標点を対応づけることにより表されるパラメトリック曲面により描画対象物を近似処理する描画処理装置であって、
前記パラメトリック曲面を構成する単位であるパッチに対して定義される2次元パラメータ座標系における第1パラメータの1次関数で表される第1内分係数について、前記第1パラメータの定義域内の2つの点における前記第1内分係数の代表値の組を保持する係数データ記憶部と、
処理対象のパッチにおいて指定される前記第1パラメータの指定値を補間係数として、前記係数データ記憶部に記憶された前記第1内分係数の代表値の組を線形補間器により補間演算することにより、前記第1パラメータの指定値に対応する前記第1内分係数の補間値を算出する補間処理部と、
前記第1内分係数の補間値にもとづいた比で、当該処理対象のパッチの形状を決める複数の制御点を前記2次元パラメータ座標系の第1パラメータ軸方向に内挿演算する細分化処理部とを含むことを特徴とする描画処理装置。
【請求項6】
前記係数データ記憶部は、前記2次元パラメータ座標系における第2パラメータの1次関数で表される第2内分係数について、前記第2パラメータの定義域内の2つの点における前記第2内分係数の代表値の組を保持し、
前記補間処理部は、当該処理対象のパッチについて指定される前記第2パラメータの指定値を補間係数として、前記第2内分係数の代表値の組を線形補間器により補間演算することにより、前記第2パラメータの指定値に対応する前記第2内分係数の補間値を算出し、
前記細分化処理部は、前記第2内分係数の補間値にもとづいた比で、前記第1パラメータ軸方向に内挿された前記複数の制御点をさらに前記2次元パラメータ座標系の第2パラメータ軸方向に内挿演算することにより、当該処理対象のパッチにおいて前記2次元パラメータ座標の指定値に対応する前記パラメトリック曲面上の頂点座標を算出することを特徴とする請求項5に記載の描画処理装置。
【請求項7】
テクスチャに関するデータを記憶するテクスチャ記憶部と、
描画処理単位に対して定義されるパラメータ座標の指定値にもとづいて、前記テクスチャ記憶部に記憶された前記テクスチャに関するデータを線形補間器により補間演算することにより、前記パラメータ座標の指定値に対応する前記テクスチャに関する補間データを算出するテクスチャ処理部と、
前記テクスチャに関する補間データを用いて、前記描画処理単位の演算処理を行う描画処理部とを含み、
前記描画処理単位は、1次元パラメータ座標で表されるパラメトリック曲線を構成する単位であるセグメント、または2次元パラメータ座標で表されるパラメトリック曲面を構成する単位であるパッチであり、
前記テクスチャ記憶部は、前記セグメントまたは前記パッチに対して定義されるパラメータ座標に依存する内分係数について、前記パラメータの定義域内の2つの点における前記内分係数の代表値の組を前記テクスチャに関するデータとして保持し、
前記テクスチャ処理部は、処理対象のセグメントまたはパッチについて前記描画処理部により順次指定されるパラメータ座標の指定値を補間係数として、前記内分係数の代表値の組を線形補間器により補間演算することにより、前記パラメータ座標の指定値に対応する前記内分係数の補間値を算出し、
前記描画処理部は、前記内分係数の補間値にもとづいた比で、当該処理対象のセグメントまたはパッチの形状を決める複数の制御点を内挿演算することにより、当該処理対象のセグメントまたはパッチにおいて前記パラメータ座標の指定値に対応する前記パラメトリック曲線またはパラメトリック曲面上の点の座標を順次算出することを特徴とする描画処理装置。
【請求項8】
前記描画処理部による前記内挿演算は、前記内分係数の補間値にもとづいた比で前記セグメントまたはパッチ内の前記複数の制御点を再帰的に内挿する演算であることを特徴とする請求項7に記載の描画処理装置。
【請求項9】
前記テクスチャ記憶部は、前記セグメントまたは前記パッチの形状を決める複数の制御点の組を前記セグメントまたは前記パッチ毎に保持し、
前記テクスチャ処理部は、前記内分係数の補間値を補間係数として、前記処理対象のセグメントまたはパッチに適用すべき前記複数の制御点を前記線形補間器により内挿し、
前記描画処理部は、前記内分係数の補間値にもとづいた比で、前記テクスチャ処理部により内挿された前記複数の制御点をさらに内挿演算することを特徴とする請求項7または8に記載の描画処理装置。
【請求項10】
テクスチャに関するデータを記憶するテクスチャ記憶部と、
描画処理単位に対して定義されるパラメータ座標の指定値にもとづいて、前記テクスチャ記憶部に記憶された前記テクスチャに関するデータを線形補間器により補間演算することにより、前記パラメータ座標の指定値に対応する前記テクスチャに関する補間データを算出するテクスチャ処理部とを含み、
前記描画処理単位は、1次元パラメータ座標で表されるパラメトリック曲線を構成する単位であるセグメント、または2次元パラメータ座標で表されるパラメトリック曲面を構成する単位であるパッチであり、
前記テクスチャ記憶部は、前記セグメントまたは前記パッチの形状を決める複数の制御点の組を前記セグメントまたは前記パッチ毎に保持し、
前記テクスチャ処理部は、処理対象のセグメントまたはパッチに適用すべき前記複数の制御点の組を前記テクスチャ記憶部から取得して線形補間器により内挿演算することにより、当該処理対象のセグメントまたはパッチにおいて指定される前記パラメータ座標の指定値に対応する前記パラメトリック曲線または前記パラメトリック曲面上の頂点座標を算出することを特徴とするテクスチャ処理装置。
【請求項11】
前記テクスチャ処理部は、前記線形補間器により内挿された前記複数の制御点を前記線形補間器に再投入することにより、前記セグメント内で前記複数の制御点を再帰的に内挿演算することを特徴とする請求項10に記載のテクスチャ処理装置。
【請求項12】
前記テクスチャ記憶部は、前記セグメントまたは前記パッチに対して定義されるパラメータ座標に依存する内分係数について、前記パラメータの定義域内の2つの点における前記内分係数の代表値の組を前記テクスチャに関するデータとして保持し、
前記テクスチャ処理部は、処理対象のセグメントまたはパッチにおいて指定されるパラメータ座標の指定値を補間係数として、前記内分係数の代表値の組を線形補間器により補間演算することにより、前記パラメータ座標の指定値に対応する前記内分係数の補間値を算出し、さらに、前記内分係数の補間値を補間係数として、前記複数の制御点を前記線形補間器により内挿演算することにより、当該処理対象のセグメントまたはパッチにおいて前記パラメータ座標の指定値に対応する前記パラメトリック曲線またはパラメトリック曲面上の点の座標を算出することを特徴とする請求項10または11に記載の描画処理装置。
【請求項13】
パラメトリック曲面の形状を決める制御点の3次元座標値がテクセル値として格納され、パラメトリック曲面の座標系におけるパラメータを指定値とするテクスチャの読み出し命令により隣接する2つの前記制御点の座標値がサンプリングされて、前記指定値に対応する制御点の補間値を計算可能に構成されたことを特徴とするテクスチャのデータ構造。
【請求項14】
パラメトリック曲面の形状を決める制御点を再帰的に内挿演算する際の内分係数の始値およぶ終値が隣接するテクセル値として格納され、パラメトリック曲面の座標系におけるパラメータを指定値とするテクスチャの読み出し命令により前記内分係数の始値および終値がサンプリングされて、前記指定値に対応する内分係数の補間値を計算可能に構成されたことを特徴とするテクスチャのデータ構造。
【請求項15】
1つのパラメータに対して座標点を対応づけることにより表されるパラメトリック曲線を折れ線に細分化するテセレーション方法であって、
前記パラメトリック曲線を構成する単位であるセグメントに対して定義される1次元パラメータ座標系におけるパラメータに依存して値が決まる内分係数について、前記パラメータの定義域の両端点における前記内分係数の値を始値および終値としてあらかじめ係数テーブルに格納しておき、処理対象のセグメントにおいて指定される前記パラメータの指定値を補間係数として、前記係数テーブルに格納された前記内分係数の始値および終値を補間することにより、前記パラメータの指定値に対応する前記内分係数の補間値を算出するステップと、
前記内分係数の補間値にもとづいた比で、当該処理対象のセグメントの形状を決める複数の制御点を内挿演算することにより、当該処理対象のセグメントにおいて前記パラメータの指定値に対応する前記パラメトリック曲線上の頂点座標を算出するステップとを含むことを特徴とするテセレーション方法。
【請求項16】
2つのパラメータの組に対して座標点を対応づけることにより表されるパラメトリック曲面をポリゴンメッシュに細分化するテセレーション方法であって、
前記パラメトリック曲面を構成する単位であるパッチに対して定義される2次元パラメータ座標系における第1パラメータに依存して値が決まる第1内分係数について、前記第1パラメータの定義域の両端点における第1内分係数の値を始値および終値としてあらかじめ係数テーブルに格納しておき、処理対象のパッチにおいて指定される前記第1パラメータの指定値を補間係数として、前記係数テーブルに格納された前記第1内分係数の始値および終値を補間することにより、前記第1パラメータの指定値に対応する前記第1内分係数の補間値を算出するステップと、
前記内分係数の補間値にもとづいた比で、当該処理対象のパッチの形状を決める複数の制御点を前記2次元パラメータ座標系の第1パラメータ軸方向に内挿演算するステップとを含むことを特徴とするテセレーション方法。
【請求項17】
前記2次元パラメータ座標系における第2パラメータに依存して値が決まる第2内分係数についても、第2パラメータの定義域の両端点における第2内分係数の値を始値および終値としてあらかじめ前記係数テーブルに格納しておき、当該処理対象のパッチにおいて指定される前記第2パラメータの指定値を補間係数として、前記係数テーブルに格納された前記第2内分係数の始値および終値を補間することにより、前記第2パラメータの指定値に対応する前記第2内分係数の補間値を算出するステップと、
前記第2内分係数の補間値にもとづいた比で、前記第1パラメータ軸方向に内挿された前記複数の制御点をさらに前記2次元パラメータ座標系の第2パラメータ軸方向に内挿演算することにより、当該処理対象のパッチにおいて前記2次元パラメータ座標の指定値に対応する前記パラメトリック曲面上の頂点座標を算出するステップとをさらに含むことを特徴とする請求項16に記載のテセレーション方法。
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【図15】
【図16】
【図17】
【図18】
【図19】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【図15】
【図16】
【図17】
【図18】
【図19】
【公開番号】特開2006−243937(P2006−243937A)
【公開日】平成18年9月14日(2006.9.14)
【国際特許分類】
【出願番号】特願2005−56118(P2005−56118)
【出願日】平成17年3月1日(2005.3.1)
【出願人】(395015319)株式会社ソニー・コンピュータエンタテインメント (871)
【Fターム(参考)】
【公開日】平成18年9月14日(2006.9.14)
【国際特許分類】
【出願日】平成17年3月1日(2005.3.1)
【出願人】(395015319)株式会社ソニー・コンピュータエンタテインメント (871)
【Fターム(参考)】
[ Back to top ]