(57)【特許請求の範囲】
【請求項１】
コンピュータ・ソフトウェアにより実現されるシステムにおいて、３Ｄオブジェクトの３Ｄモデルを、画像サンプリング点群を含む画像としてレンダリングするための方法であって、前記３Ｄモデルは距離フィールドであり、前記距離フィールドは、前記３Ｄオブジェクトのサーフェイスの部分を表すサーフェイスセルを含み、
前記システムにて前記３Ｄオブジェクトの前記３Ｄモデルを画像としてレンダリングする処理手段が、
３Ｄオブジェクトの３Ｄモデルの各サーフェイスセルが処理順序の単位となるオブジェクト順フェーズにおいて、各サーフェイスセルについて前記画像内の画像サンプリング点群のセットを決定する第１のステップと、
他のサーフェイスセルから独立して、各サーフェイスセルを処理する第２のステップと、
前記画像をレンダリングして出力画像とする第３のステップとを含み、
前記各サーフェイスセルを処理する前記第２のステップは、
画像内の各画像サンプリング点が処理順序の単位となる画像順フェーズにおいて、前記サーフェイスセルの前記画像サンプリング点への寄与を求めるために、前記画像サンプリング点群のセット内の各画像サンプリング点から、前記サーフェイスセルを通過するように光線を投光することをさらに含む、
３Ｄオブジェクトの３Ｄモデルをレンダリングするための方法。
【請求項２】
前記投光することは、
前記距離フィールドを使用して、前記光線が前記サーフェイスセルに入る入口点及び前記光線が前記サーフェイスセルを出る出口点が共に前記サーフェイスの内部にあるか否かを判断し、真である場合、前記寄与が前記入口点から求められることをさらに含む
請求項１記載の方法。
【請求項３】
前記サーフェイスセルは、バウンディングボックスを有し、
前記求めるステップは、
前記画像サンプリング点群のセットを求めるために、前記バウンディングボックスを前記画像上に投影することをさらに含む
請求項１又は２記載の方法。
【請求項４】
前記距離フィールドは、距離フィールドサンプリング点群を含み、
連続関数を使用して、前記距離フィールドサンプリング点群から距離値を復元するステップをさらに含む
請求項１又は２記載の方法。
【請求項５】
深度バッファーを使用して前記寄与を結合するステップをさらに含む
請求項１又は２記載の方法。
【請求項６】
各サーフェイスセルは、前記求めるステップ及び前記投光することにつき１度のみ処理される
請求項１又は２記載の方法。
【請求項７】
前記距離フィールドは、距離フィールドサンプリング点群を含み、
三重一次形式の復元を用いて、前記距離フィールドサンプリング点群から距離値を復元するステップをさらに含む
請求項１又は２記載の方法。
【請求項８】
前記距離フィールドは、距離フィールドサンプリング点群を含み、
三重二次形式の復元を用いて、前記距離フィールドのサンプリング点群から距離値を復元するステップをさらに含む
請求項１又は２記載の方法。
【請求項９】
前記距離フィールドサンプリング点群には符号が付されており、前記サーフェイスセルの２つの隣接頂点の前記距離フィールドサンプリング点の前記符号の変化は、前記サーフェイスの前記部分が、交点において前記サーフェスセルの前記２つの隣接頂点の間のエッジと交差することを示す
請求項４記載の方法。
【請求項１０】
前記交点において前記距離値を復元することをさらに含む
請求項９記載の方法。
【請求項１１】
前記サーフェイスと前記サーフェイスセルのエッジとの間の交差部のセットを求めるステップと、
前記画像サンプリング点群のセットを求めるために、前記交差部のセットを前記画像上に投影するステップとをさらに含む
請求項１又は２記載の方法。
【請求項１２】
隣接する画像サンプリング点を、それら隣接画像サンプリング点から投光される前記光線が前記サーフェイスに交差する限りは、前記画像サンプリング点群のセットに追加するステップをさらに含む
請求項１又は２記載の方法。
【請求項１３】
３Ｄオブジェクトの３Ｄモデルを、画像サンプリング点群を含む画像としてレンダリングするためのシステムであって、前記３Ｄモデルは距離フィールドであり、前記距離フィールドは、前記３Ｄオブジェクトのサーフェイスの部分を表すサーフェイスセルを含み、
３Ｄオブジェクトの３Ｄモデルの各サーフェイスセルが処理順序の単位となるオブジェクト順フェーズにおいて、各サーフェイスセルについて前記画像内の画像サンプリング点群のセットを決定する第１の手段と、
他のサーフェイスセルから独立して、各サーフェイスセルを処理する第２の手段と、
前記画像をレンダリングして出力画像とする第３の手段とを備え、
前記各サーフェイスセルを処理する前記第２の手段は、
画像内の各画像サンプリング点が処理順序の単位となる画像順フェーズにおいて、前記画像サンプリング点への前記サーフェイスセルの寄与を求めるために、前記画像サンプリング点群のセット内の各前記画像サンプリング点から、前記サーフェイスセルを通過するように光線を投光する手段をさらに含む、
３Ｄオブジェクトの３Ｄモデルをレンダリングするためのシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的にはコンピューターグラフィックスの分野及び３Ｄオブジェクトの３Ｄモデルをレンダリングすることに関し、より詳細には、３Ｄオブジェクトの３Ｄモデルが、３Ｄ距離フィールドとして表されると共に、コンピューター数値制御された（ＣＮＣ）機械加工操作の結果をシミュレートするのに使用される、該３Ｄモデルをレンダリングすることに関する。
【背景技術】
【０００２】
距離フィールド
コンピューターグラフィックスアプリケーションでは、３次元（３Ｄ）オブジェクトは複数の異なる方法、たとえばポリゴンモデル、点群モデル、パラメトリック関数、又は陰関数を使用する方法を使用して表すことができる。
【０００３】
方法の１つのクラスは、３Ｄ空間内の任意のロケーションｘ＝（ｘ，ｙ，ｚ）からオブジェクトのサーフェイスまでの最小距離ｄ（ｘ）を規定する距離フィールドを使用する。距離フィールドｄ（ｘ）はオブジェクトの内部、外部、及びサーフェイスを区別することができ、たとえばｄ（ｘ）＜０はオブジェクトの外側であり、ｄ（ｘ）＞０はオブジェクトの内側であり、ｄ（ｘ）＝０はオブジェクトのサーフェイス上である。
【０００４】
さらに、距離フィールドを使用して、オブジェクトの実際のサーフェイスからオフセットされたサーフェイス、すなわちｄ（ｘ）＝０からオフセットされたサーフェイスを位置特定することができる。一般に、サーフェイス基準はｄ（ｘ）＝ｃとして定義される。ここで、ｃはオブジェクトのサーフェイスからオフセットされた一定の距離であり、０に等しい場合がある。代替的に、オフセットされたサーフェイスが条件Ｄ（ｘ）＝０を満たすように、新たなオフセット距離フィールドＤ（ｘ）＝ｄ（ｘ）−ｃを使用することができる。本明細書全体を通じて、一般性を損なうことなく、実際の距離フィールドの代わりにオフセット距離フィールドを使用することができることを理解されたい。
【０００５】
オブジェクトの距離フィールドは、多数の異なる手段によって規定することができる。単純な形状のオブジェクトの場合、距離フィールドは解析的に規定することができる。たとえば、３Ｄ座標（ｘ０，ｙ０，ｚ０）を中心とする半径Ｒの球の距離フィールドは、ｄ（ｘ）＝Ｒ−ｓｑｒｔ［（ｘ−ｘ０）２＋（ｙ−ｙ０）２＋（ｚ−ｚ０）２］と書くことができる。この場合、パラメーターＲ及び（ｘ０，ｙ０，ｚ０）は、球の距離関数と組み合わせて、オブジェクトの距離フィールド及び３Ｄ形状を完全に規定するのに十分である。一般に、３Ｄ距離フィールドはパラメーターのセットｐ＝｛ｐ０，ｐ１．．．ｐｎ｝及び距離関数ｆ（ｘ，ｙ，ｚ，ｐ０，ｐ１．．．ｐｎ）によって規定することができる。
【０００６】
距離関数ｆは、他の関数の組み合わせとすることができる。たとえば、オブジェクトは、球及び立方体のような２つのオブジェクトの論理和（UNION）によって形成される複合オブジェクトとすることができる。この場合、３Ｄ空間ｘにおける点は、ｄｓｐｈｅｒｅ（ｘ）＞０  ＯＲ  ｄｃｕｂｅ（ｘ）＞０の場合、複合オブジェクトのサーフェイスの内側にある。ここで、ＯＲは、ブールＯＲ関数である。論理和（UNION）、論理積（INTERSECTION）、及び論理差（DIFFERENCE）のブール演算によるこのオブジェクトの組み合わせは、当該技術分野において、構成的ソリッドジオメトリ（ＣＳＧ）として知られている。
【０００７】
コンピューターシミュレーションのような、距離フィールドのアプリケーションによっては、３Ｄ空間における一連のロケーションにおいて、距離フィールドを計算してメモリ内に格納する、すなわちサンプリングすることが有用である場合がある。等間隔３Ｄグリッドでの距離フィールドサンプリングは単純性の利点を有するが、空間サンプリングレートは、存在する最も高い空間周波数を捕捉するのに十分高い必要がある。さらに、３Ｄ空間を複数の領域に分割することが有用である場合がある。ここでは、異なる領域において異なる距離関数及び／又はパラメーターが使用される。たとえば、距離関数は、（ｘａ，ｙａ，ｚａ）から（ｘｂ，ｙｂ，ｚｂ）に延在する空間の領域における球の距離関数とすることができる一方、距離関数は、（ｘｃ，ｙｃ，ｚｃ）から（ｘｄ，ｙｄ，ｚｄ）に延在する空間の領域における立方体の距離関数とすることができる。ここでは、空間のこれらの領域は、セルのコーナーの座標を頂点として有するセルとして定義される。
【０００８】
空間分割は、多数の手段によって行うことができる。長方形又は立方体の形状のセルを使用することが有用である場合があるが、一般性を損なうことなく他の任意のセル形状を使用することができる。さらに、セルをツリーのようなデータ構造に編成して、特定の空間的関係を有するようにセルを配置できるようにすることが有用である場合がある。たとえば、セルは立方体とすることができ、単純な立方グリッド又はオクトリーデータ構造で配置することができる。代替的に、セルを長方形とし、ｋｄ次元のツリー構造に配置してもよい。
【０００９】
しかしながら、これらの高い周波数がサーフェイスの至るところに存在するのは極端な場合のみである。より一般的には、サーフェイスは平滑な部分を含み、該部分はディテールを損なうことなく、より低いレートでサンプリングすることができる。
【００１０】
３Ｄの適応的にサンプリングされた距離フィールド（ＡＤＦ）において、距離フィールドは、オブジェクトのサーフェイスの局所的なディテールのレベルに比例して、場所場所で異なる空間周波数にてサンプリングされる。大量の空間的ディテールを有するオブジェクトのサーフェイスの部分が、ディテールの少ないエリア、たとえばサーフェイスの平滑な部分よりも高い周波数でサンプリングされる。このようにして、オブジェクトの形状を格納するのに使用されるメモリ量が最小限にされる一方、空間的ディテールは高い解像度で維持される。一般的に、３Ｄ距離フィールドはセルの頂点においてサンプリングされ、セルのオクトリーとして階層的に格納される。該オクトリーにおいて、セルはディテールのレベルに従って再帰的に分割される。
【００１１】
上述したのと同じようにして、３Ｄ空間における任意のロケーションにおける距離フィールドの値を距離フィールドサンプリング点群から計算することができる。この場合、距離フィールドサンプリング点群は、距離関数のパラメーターであり、距離関数は、復元カーネルとしても知られる、距離フィールドサンプリング点群から距離フィールドを復元するための関数である。たとえば、距離フィールドは三重一次（tri-linear）補間によってセルの頂点での距離フィールドサンプリング点から計算することができる。しかしながら、三重二次（tri-quadratic）補間、ベクトル距離フィールド補間、又は他の復元カーネルも使用することができる。さらに、復元カーネルは、空間の任意の点において距離フィールドの勾配（gradient）を計算する手段を提供する。オブジェクトのサーフェイス上又はサーフェイス付近に位置する点の場合、勾配はサーフェイス法線と同じ方向に向く。
【００１２】
レンダリング
従来技術において、３Ｄ  ＡＤＦは、３つのクラスの方法、すなわち点レンダリング、画像順投光法、オブジェクト順ポリゴンレンダリングによってレンダリングされてきた。参照により本明細書に援用される、２００２年５月２８日にフリスケン（Frisken）他によって発行された、米国特許第６，３９６，４９２号「ディテール指向型階層距離フィールド（Detail-directed hierarchical distance fields）」を参照されたい。
【００１３】
点レンダリング
距離フィールドの点レンダリングは、オブジェクトの３Ｄ空間内の点群のセットから開始することによって達成される。距離フィールド及びその勾配ベクトルは、各点において計算され、その後、該点は勾配ベクトルに沿ってサーフェイスの方向に移動されることによって反復的に変更される。点が所定のレベルの精度内でオブジェクトのサーフェイスに到達すると移動が終わる。
【００１４】
一連のサーフェイス点が見つかると、それらを複数の手段によってレンダリングすることができる。たとえば、単一の画素のプリミティブ（すなわち、ＧＬ＿ＰＯＩＮＴ）をＯｐｅｎＧＬグラフィックＡＰＩを使用して非常に単純にレンダリングすることができる。代替的に、時にはスプライト又はスプラットとも呼ばれる拡張型のプリミティブを各ロケーションにおいてレンダリングすることができる。
【００１５】
点レンダリングは、単純であるという利点を有し、非常に高速であり得る。しかしながら、穴のない画像を作成することは困難となり得る。サーフェイスを点群で均一にカバーすることは保証されておらず、欠けた領域を特定し埋めるのにはかなりの取り組みが必要となる。
【００１６】
画像順投光法
画像順投光法は、出力画像内の画素の色及び輝度を、個々の画素単位で求める。光線が画像内の画素から距離フィールドを貫通するように投光される。光線は、サーフェイスが見つかるまでセルからセルへと追跡される。
【００１７】
利点として、投光法は３Ｄ  ＡＤＦと同じだけ正確であり、たとえば１０６分の１以上であることができる。投光される光線の方向に沿って、サーフェイスを含むサーフェイスセルをオクトリー内で特定するプロセスは、非常に単純であるが、コンピューターメモリアクセスの観点で非常に非効率であり得る。オクトリー内で空間的に隣接したセルに関連付けられるデータは、多くの場合、コンピューターメモリ内では大きく隔てられており、それによってＣＰＵメモリキャッシュミス率が高くなり、これによってレンダリング方法の全体性能が劣化する。
【００１８】
セルを貫通するように光線を投光するのに必要とされるデータが、必要なときにＣＰＵキャッシュ内に存在しない場合、レンダリング更新レートが大幅に低下し、場合によっては、モデルを操作しながらリアルタイムのレート、たとえば毎秒１０回更新のレートで、インタラクティブなレンダリングを行うことが不可能になるところまで悪化する。
【００１９】
オブジェクト順ポリゴンレンダリング
３Ｄ  ＡＤＦのオブジェクト順ポリゴンレンダリングは、ＡＤＦのポリゴン表現を必要とする。ＡＤＦからポリゴンモデルを生成するための様々な方法が知られており、これにはマーチングキューブ及びサーフェイスネットが含まれる。
【００２０】
一般に、オブジェクト順レンダリングは、いかなる他のポリゴンからも独立して、各ポリゴンによって影響された画像内の画素のセットを求める。ｚバッファーを使用してこれらの独立した寄与を適切に結合するのが一般的であるが、他の手段、たとえばペインターズアルゴリズム又は塗り重ね法が既知であり、その場合は、ポリゴンは、レンダリングの前に、まず深度順でソートされる。
【００２１】
ポリゴンモデルはコンピューターグラフィックの主流を占めているため、多岐にわたるポリゴンレンダリングハードウェア及びソフトウェア、たとえばＭｉｃｒｏｓｏｆｔ  Ｄｉｒｅｃｔ３Ｄ及びＳｉｌｉｃｏｎ  Ｇｒａｐｈｉｃ  ＯｐｅｎＧＬが利用可能である。ポリゴンモデルが生成された後、該モデルは、画像順投光法に可能であるよりも通常はるかに高いレートで画像にレンダリングすることができる。
【００２２】
しかしながら、ポリゴン表現は平坦なプリミティブを使用し、ＡＤＦの近似でしかない。この結果、外観がよりファセット状（faceted）の画像となり、したがって湾曲したサーフェイスを正確に表すことができない。これは、レンダリングが高度に正確、たとえば１０６分の１でなくてはならないときに特に問題である。ポリゴンレンダリングを用いると、非常に平滑なサーフェイス画像を生成するためには管理不可能なほど多数の非常に小さなポリゴンを用いる必要があり、その結果、非常に厳しいメモリ要件及び／又は処理要件が生じる。
【００２３】
レンダリングされた画像におけるクラック
ＡＤＦのような空間分割法では、隣接セルは局所的なディテールのレベルに依拠して異なるサイズを有する可能性がある。結果として、１つのセルの距離フィールドサンプリング点から復元されるサーフェイスが、隣接セルの距離フィールドサンプリング点から復元されるサーフェイスと厳密にマッチしない場合があり、その結果、レンダリングされた画像にクラックが現れる。
【発明の概要】
【発明が解決しようとする課題】
【００２４】
３Ｄ距離フィールドによって表されるサーフェイスをレンダリングするための、投光法の精度及びポリゴンレンダリングの速度を有する方法を提供することが望まれている。さらに、レンダリングのためのこの方法が、クラックアーティファクトを一切有しない画像を生成することが望まれている。
【００２５】
また、フライス加工及び他の工作機械によって行われるような製造動作に組み込むことができるシミュレーションを提供することが望まれている。そのようなシミュレーションは、オペレーターが、機械加工プロセスにおける誤りを、部品が実際に機械加工される前に視覚的に識別し、それによって時間及び場合によっては材料を節減することを可能にするであろう。
【課題を解決するための手段】
【００２６】
方法及びシステムが、３Ｄオブジェクトの３Ｄモデルを、画像サンプリング点群を含む画像としてレンダリングする。前記３Ｄモデルは距離フィールドであり、該距離フィールドは、前記３Ｄオブジェクトのサーフェイスの部分を表すサーフェイスセルを含む。
【００２７】
オブジェクト順フェーズにおいて前記サーフェイスセルごとに前記画像内の画像サンプリング点群のセットが求められる。次に、各前記サーフェイスセルが他のサーフェイスセルから独立して処理される。
【００２８】
前記処理は、画像順フェーズにおいて、前記画像サンプリング点群のセット内の各前記画像サンプリング点群から、前記サーフェイスセルを通過するよう光線を投光して、前記画像サンプリング点群への前記サーフェイスセルの寄与を求め、次に前記画像がレンダリングされる。
【図面の簡単な説明】
【００２９】
【図１Ａ】本発明の実施の形態による、３Ｄオブジェクトの３Ｄモデルをレンダリングするための方法の流れ図である。
【図１Ｂ】本発明の一実施の形態による、適応的にサンプリングされた距離フィールド（ＡＤＦ）の２Ｄ概略図である。
【図２】本発明の実施の形態による、図１の方法のオブジェクト順フェーズの流れ図である。
【図３】本発明の実施の形態による、図１の方法の画像順フェーズの流れ図である。
【図４】本発明の実施の形態による変換の流れ図である。
【図５】本発明の実施の形態による、ＡＤＦ及びレンダリングパラメーターのトップダウンの概略図である。
【図６Ａ】本発明の実施の形態による、凸包及び領域拡張の概略図である。
【図６Ｂ】本発明の実施の形態による、凸包及び領域拡張の概略図である。
【図６Ｃ】本発明の実施の形態による、凸包及び領域拡張の概略図である。
【図７Ａ】本発明の実施の形態による投光法の図である。
【図７Ｂ】本発明の実施の形態による投光法の図である。
【図８】本発明の一実施の形態による、補正されるクラックを含むＡＤＦの概略図である。
【図９】本発明の実施の形態による、工作機械をシミュレートするためのシステムを示す図である。
【発明を実施するための形態】
【００３０】
方法及びシステムの概観
図１Ａ及び図１Ｂに示すように、本発明の実施の形態は、３Ｄオブジェクト１０１の３Ｄモデル１１１を出力画像１０２としてレンダリングするための方法を提供する。レンダリングは、ディスプレイ若しくはプリントデバイス１０９、又はメモリに対するものとすることができる。図１はその方法を示し、図１Ｂはセルベースのデータ構造を示す。レンダリングは、図９に示すような、フライス盤によって実行されるような機械加工操作をシミュレートすることができる。
【００３１】
本発明の１つの実施の形態では、モデルは、オクトリー１１３としてコンピューターシステムのメモリ１１２内に格納された、３Ｄの適応的にサンプリングされた距離フィールド（ＡＤＦ）としてオブジェクトを表す。しかしながら、一般的に、モデルは空間分割データ構造、たとえばｋｄ次元ツリー又はオクトリーとして構造的に表される任意の距離フィールドとすることができる。さらに、距離フィールドは距離フィールドサンプリング点群から復元することもできるし、たとえば連続関数により解析的に求めることもできる。
【００３２】
距離フィールドがオクトリーデータ構造内に格納されると、オクトリーは、３つのタイプのセル、すなわち、ルートセル、中間セル、及び末端セルを含む。末端セルは、内部セル、外部セル、又は（図１Ｂにおいて網掛けを付した）サーフェイスセル１０３のいずれかとすることができる。本発明の１つの目的は、処理されるセルの数を最小限にすることである。したがって、本明細書において説明される処理は、主にサーフェイスセルに関する。本発明は、モデルをオブジェクト空間において表現される複数のサーフェイスセルに分割され、それらサーフェイスセルがウィンドウ座標での画像サンプリング点（画素）の領域に投影されるような、任意のオブジェクト表現に対してうまく動作することに留意されたい。
【００３３】
サーフェイスセル群は、オブジェクトのサーフェイス１０４全体を表す。三重一次形式（tri-linear）の距離フィールドの場合は、距離フィールドはサーフェイスセルの８つの頂点（コーナー）１０５においてサンプリングされる。サーフェイスなるものは、距離フィールドｄ（ｘ）がゼロに等しいものであり、セルを貫通することから、サーフェイスセルでは、少なくとも２つの頂点ロケーションにおいて距離フィールドのサンプリング（値)が、反対の符号を有する。
【００３４】
当該技術分野において、３Ｄ空間におけるサーフェイスセルの範囲はバウンディングボックス１０７と呼ばれることが理解されている。
【００３５】
オブジェクト順／画像順ハイブリッドレンダリング
従来技術の方法に勝る１つの利点として、本発明者らのレンダリング方法は、ハイブリッドレンダリング法において、従来の投光法の精度を、ポリゴンレンダリングの速度と組み合わせる。レンダリングの間、距離フィールドの各サーフェイスセル１０３は、まずオブジェクト順フェーズ２００において処理され、次に画像順フェーズ３００において処理される。
【００３６】
オブジェクト順フェーズ２００中、各サーフェイスセル１０３について、独立して、サーフェイスセル内のサーフェイス１０４の部分に対応する、出力画像１０２内の画像サンプリング点群のセット１０８を決定する（以下、「求める」と表記する）。上述したように、これはサーフェイスセルをウィンドウ座標に投影することによって行われる。
【００３７】
後続の画像順フェーズ３００中、光線８０５がセット１０８内の各画像サンプリング点から投影され、該画像サンプリング点に対するサーフェイスの部分の寄与が、他のサーフェイスセルから独立して確定される。これは、光線パラメーターをウィンドウ座標からセル座標に変換することによって行われる。
【００３８】
当該技術分野において既知であるように、ｚバッファー（深度バッファーとも呼ばれる場合がある）を使用して、個々のサーフェイスセルの寄与を出力画像内の画像サンプリング点に結合する。このようにして、本発明者らのレンダリング方法において、各サーフェイスセルはステップごとに１回のみ処理される。
【００３９】
最後に、画像サンプリング点が表示用の画像画素にコンバートされる。最も単純な実施態様では、画像サンプリング点は画像画素に対し直接１対１の対応を有することができる。しかしながら、画像サンプリング点から画像画素への他のコンバージョンを用いてもよい。たとえば、画像は、多数の画像サンプリング点が単一の画像画素に対応する場合、スーパーサンプリングすることができる。画像サンプリング点は、最終画像における、いわゆるエイリアシングアーティファクトを除去する目的で共に平均化することができる。代替的に、画像はサブサンプリングされるか、又は画像画素よりも少ない画像サンプリング点が存在するようにサンプリングされてもよい。次に、画像サンプリング点を処理して画像画素を生成することができる。一般に、サブサンプリングは直接サンプリングよりも要求する計算量が少なく、それによってレンダリング速度及び関連するインタラクティブ性が増加する。一般に、画像サンプリング点は、様々な理由によって、表示される最終的な画像における実際の画素とは異なる解像度を有し得る。
【００４０】
驚くべきことに、本発明者らのレンダリング方法の性能は、正確性を損なうことなく、従来の距離フィールド投光法よりも約１桁高速であり、従来のポリゴンレンダリング法に匹敵する速度である。さらになお驚くべきことには、ポリゴンレンダリングに勝る本発明者らの方法の性能の利点は、中間ポリゴンモデルの生成のオーバーヘッドが高くなる、より複雑なオブジェクトに関して増大する。
【００４１】
別の利点として、本方法は、いくつかの距離フィールドベースのレンダリング方法に共通の「クラック」を除去するための手順を含む。
【００４２】
座標系
図４及び図５に示し、３Ｄコンピューターグラフィックにおいて一般的であるように、本発明者らのレンダリング方法は、線形変換によって関係付けられる複数の座標系を使用する。本発明者らの座標系は特に、オープングラフィックライブラリ（ＯｐｅｎＧＬ）標準規格仕様に基づく。座標系は、セル座標ｘｃｅｌｌ４０１、モデル座標ｘｍ４０２、視点座標（eye coordinate）ｘｅ４０３、クリップ座標ｘｃ４０４、及びウィンドウ座標ｘｗ４０５を含む。
【００４３】
一般に、１つの座標系の座標ｘの、別の座標系の座標ｘ’への変換は、行列、たとえばｘ’＝ＡｘＴとの乗算を伴う。ここで、ｘＴは列ベクトルであり、Ａは一般変換行列（generic transformation matrix）である。セル座標からモデル座標への変換はセル行列Ｃ４１０を使用し、モデル座標から視点座標への変換はモデルビュー行列Ｍ４２０を使用し、視点座標からクリップ座標への変換は投影行列Ｐ４３０を使用し、クリップ座標からウィンドウ座標への変換はビューポート行列Ｖ４４０を使用する。
【００４４】
図５は、ビューイングウィンドウ５０１のトップダウンビュー（ｙ次元）、及びｚ−ｆｒｏｎｔ５０３、ｚ−ｂａｃｋ５０４、ｘ−ｌｅｆｔ５０５、ｘ−ｒｉｇｈｔ５０６によって境界を画される視錐台５０２も示している。視錐台は、ｙ−ｂｏｔｔｏｍ５０７及びｙ−ｔｏｐ５０８によってさらに境界を画される。これらは図示されるビューに直交する。
【００４５】
セル座標における３Ｄロケーションの成分ｘＣｅｌｌ＝（ｘ，ｙ，ｚ，１）は、間隔［０，１］にわたる範囲をとる。セル座標はセル行列
【００４６】
【数１】
0005188628.tif 000002
【００４７】
によってモデル座標ｘｍに変換される。ここで、ＣＳはサーフェイスセルのサイズ４１１であり、ＣＯはモデル座標におけるサーフェイスセルの原点４１２の座標である。適応的にサンプリングされ、オクトリーに格納される距離フィールドにおいて、ＡＤＦのルート（レベル０）セルの原点がモデル座標系の原点４０２と一致するのが一般的である。
【００４８】
モデル座標は、モデルビュー行列Ｍによって視点座標に変換される。モデルビュー行列は、モデルの回転、並進、及びスケーリング４２１を特定する。通常、ユーザー１５０は、モデルビュー行列を変化させることによってインタラクティブにモデルを操作し、モデルを眺める。
【００４９】
視点座標は、投影行列Ｐによってクリップ座標に変換される。投影行列は視錐台５０２のサイズ４３１を使用する。視錐台は、出力画像内に現れるモデルの部分を定義する。例として、投影行列は、正投影又は透視投影を表すことができる。
【００５０】
オブジェクトの可視部分のクリップ座標は、単位立方体（−１，−１，−１）〜（１，１，１）内に位置する。単位立方体の外側の、オブジェクトのいかなる部分も、出力画像において可視でない。本発明の１つの目標は、そのような部分の処理を最小限にすることである。
【００５１】
クリップ座標は、ビューポート行列Ｖによってウィンドウ座標に変換される。ビューポート行列は出力画像１０２のサイズ（幅及び高さ）４４１に依拠する。
【００５２】
当業者であれば、セル座標から画像画素への上述した変換は、用いることができる変換の１つのあり得るセットでしかないことが理解される。一般に、セル座標から画像座標にマッピングするために、線形であれ非線形であれ、変換の任意のセットを使用することができる。
【００５３】
レンダリング
レンダリングを目的とする場合、重要なセルはサーフェイスセル１０３のみである。オブジェクトのサーフェイスを含むのはこれらのセルのみである。オクトリー階層１１３において、セルがオブジェクトのサーフェイスの一部分を表している限りは、任意のレベルのセルがサーフェイスセルとなり得る。
【００５４】
レンダリングプロセスは、サーフェイスセルの原点４０２の座標、セルのサイズ４１１、及び距離値ｄ（ｘ）を必要とする。距離値は、解析的に、又はサンプリングによって取得することができる。オクトリー内のセルは立方体であるので、各セルの３つの寸法は等しく、セルの頂点のセル座標を特定するには、原点及びサイズがあれば十分である。三重一次形式の復元の場合、８つのサンプリングされた距離フィールド値が存在する一方、三重二次形式の復元には２７個の値が必要とされる。
【００５５】
レンダリングは、モデル座標を使用する際、サーフェイスの色、並びに光源の色及びロケーションも必要とする。
【００５６】
レンダリングプロセスの性能は、後述するように、不要な計算を除去することによって改善される。
【００５７】
オブジェクト順フェーズ
オブジェクト順フェーズ２００中、距離フィールド１１１のサーフェイスセル１０３の頂点の座標、及びサーフェイスセル内のサーフェイスのサーフェイス法線の座標は、モデル座標から視点座標に変換される（２１０）。背面間引き２２０は、出力画像において可視となるオブジェクトのサーフェイスの部分を特定する。モデルビュー行列Ｍ４２０、投影行列Ｐ４３０、及びビューポート行列Ｖ４４０を使用して、セル座標がウィンドウ座標４０５に変換され、ウィンドウ間引きが適用されて（２４０）、画像順フェーズ３００における投光のためのウィンドウ領域が特定される（２５０）。
【００５８】
背面間引き
サーフェイスの可視である部分は、該サーフェイスの遮蔽されていない部分のみであり、それらの部分の法線は概ねビューイング方向に向く。オブジェクトのサーフェイスの背面部分を表すサーフェイスセルは、それらが含むサーフェイスの部分が可視でないため、処理される必要がない。正確なサーフェイス表現に依拠して、セル内のサーフェイスの向きを求めるのに複数の手段が利用可能である。セル内のサーフェイス法線の範囲を求める解析手段を用いることができる。代替的に、法線の範囲は、距離フィールドが生成又は編集されるときに予め計算することができる。たとえば、本レンダリング方法に、セル内のサーフェイス法線の境界を示す法線錐を受け渡すようにすることができる。
【００５９】
代替的に、三重一次形式の復元カーネルを使用するサンプリングされた距離フィールドの場合は、サーフェイス法線の範囲は、セルの頂点１０５における値によって限界づけることができる。したがって、サーフェイス法線の範囲は、セルの各頂点における法線から求めることができる。
【００６０】
サーフェイスの向きを求めるために、法線の座標は、モデルビュー変換の逆行列を転置したもの（Ｍ−１）Ｔと乗算されることによって、オブジェクト座標から視点座標に変換される。次に、変換された法線とビューイング方向との間の内積が求められる。全ての頂点における法線の内積がゼロ未満である場合、セル内のサーフェイスの部分は背面を向いており、そのセルの処理はこれ以上必要でない。
【００６１】
ウィンドウ間引き
距離フィールドのオブジェクト順レンダリングにおいて、セル内に含まれるサーフェイスの部分によって影響される、出力画像における画像サンプリング点群のセットを求めることが必要である。サーフェイスの可視である部分は、出力画像のビューイングウィンドウ５０１内の部分のみである。ビューイングウィンドウの外側のいかなる部分も見えることはできず、処理される必要がない。したがって、このウィンドウ内にないサーフェイスの部分を含むセルの処理を除去することによって性能を改善することができる。
【００６２】
影響を受けた画像サンプリング点群のセットを求めるための１つの手順において、サーフェイス６０２の部分を含むセルのバウンディングボックス６０１の、出力画像への投影を、モデルビュー変換、透視変換、及びビューポート変換によってバウンディングボックスの頂点のモデル座標を変換することによって求める。次に、バウンディングボックスの投影の境界の周りに描かれた長方形６０３を使用して、レンダリングのための画像サンプリング点群のセットを定義することができる。これは、定義上、サーフェイスがバウンディングボックスを越えて広がることはないため、保守的な手法である。
【００６３】
しかしながら、上述の手順は、バウンディングボックス６０３の投影の範囲内の多数の画像サンプリング点がサーフェイス６０２の投影の外側にあるので、あまり効率的でない場合がある。したがって、多数の光線がサーフェイスに交差しない。
【００６４】
別の手順は点６０４の座標を使用する。この手順では、サーフェイスセルのエッジとサーフェイスとが交差してレンダリング領域を定義する。符号付き距離値を有する本発明者らの距離フィールドでは、サンプリングされた距離ｄの符号が２つの隣接頂点の間で変化していれば、それは、サーフェイスがそれら頂点間のセルのエッジと交差していることを示している。
【００６５】
セルのエッジの全てについて、交点６０４があれば、その座標を求めることができる。出力画像におけるサーフェイスを含む領域の境界を画す凸包６０５を、交差座標のウィンドウ座標から求めることができる。凸包によって、光線が投影される画像サンプリング点の数が最小限にされるが、いずれの画像サンプリング点が凸包内にあるかを求めるプロセスは依然として大きな計算量を必要とする。
【００６６】
代替的に、図６Ｃに示すように、サーフェイスとサーフェイスセルのエッジとの間の交点のウィンドウ座標（ｘ，ｙ）の最小値及び最大値を位置特定することによって、長方形画像領域６０６を定義することができる。これによって、バウンディングボックスの投影を使用する手順の使用と比較して、性能を大幅に改善することができる。
【００６７】
交点の座標はクリップ座標に変換され、範囲［−１，１］と比較される。変換された交差座標のうちのいずれもこの範囲内にない場合、サーフェイスのいずれの部分も可視でなく、セルの処理はこれ以上必要でない。そうでない場合、交差座標はこの範囲に入るようにクランプされ、ウィンドウ座標に変換される。
【００６８】
範囲拡張
図６Ｃに示すように、交差に基づく手順は、セル内のサーフェイスのスクリーン投影の真の広がりを少なく見積もる可能性がある。たとえば、セルによって表されるサーフェイスは、部分６０７が１つ又は複数の領域境界に沿ったエッジ／サーフェイス交差部から求められる領域６０６の外側に延びるように曲線を描く場合がある。これが補正されない場合、出力画像は「穴」を有することになる。
【００６９】
この問題を回避するために、画像領域の境界線に沿っては可視な画像サンプリング点が存在しないことを要件にしている。後続の投光中、サーフェイスの或る部分が画像領域の境界線と交差すると判断された場合、領域境界の外側部分６０７にある追加的行又は列から、適切な（並びの）方向に沿って、光線が投影される。実際には、隣接する画像サンプリング点から投影される光線がサーフェイスと交差する限り、該画像サンプリング点をセルの画像サンプリング点のセットに追加する。この領域拡張プロセスは、上記の境界基準が満たされるまで継続する。シーディング（種まき）方式の領域拡張のような他の領域拡張方法が使用され得ることに留意されたい。
【００７０】
画像順フェーズ
図３に示す画像順フェーズ３００中、光線が出力画像１０２内の画像サンプリング点からモデル１１１を通過するように投光される。ステップ３１０は、出力画像内の画像サンプリング点のウィンドウ座標からの光線パラメーターを求める。光線パラメーターは、各光線の始点及び方向を特定する。光線パラメーターは、セル座標に変換される（３２０）。光線は、各サーフェイスセルのバウンディングボックスと交差する（３３０）。交点において距離フィールド（の値）が復元される（３４０）。
【００７１】
光線とサーフェイスセル内のオブジェクトのサーフェイスとの交点は、バウンディングボックス交点における復元された距離フィールド（の値）から補間される（３５０）。
【００７２】
サーフェイスに交差する光線に関して、深度検査３６０のためにｚバッファーが使用される。照明計算３８０のためにサーフェイス法線が求められる（３７０）。
【００７３】
投光
スクリーン領域６０６が確定された後、図７Ａ及び図７Ｂに示すように、画像サンプリング点から光線が画像サンプリング順で投影される。ここで画像サンプリング順はたとえば、ｘの昇順、次いでｙの昇順とすることができる。しかしながら、一般性を損なうことなく任意の順序を使用することができる。光線は画像順で処理される。光線は、ウィンドウ座標において、ビューイングウィンドウにおける画像サンプリング点の座標Ｒｏ＝（ｘｗ，ｙｗ，０）から、方向Ｒｄに発生する。方向Ｒｄは、たとえば一般的な−ｚ方向とすることができる。パラメーター化された光線方程式は、Ｒ（ｔ）＝Ｒｏ＋ｔＲｄである。ここで、ｔは光線進行パラメーターである。
【００７４】
方向ベクトルＲｄは単位ベクトル、すなわち｜Ｒｄ｜＝１とすることができる。代替的に、別の長さを使用することができる。たとえば、視錐台の近位値Ｎ及び遠位値Ｆを用いて正投影が使用される場合、長さ｜Ｒｄ｜＝Ｆ−Ｎを有する光線方向ベクトルを使用することよって、結果として光線パラメーターｔが［０，１］の範囲、すなわち従来のＯｐｅｎＧＬｚバッファーにおいて用いられるのと同じ範囲内にあることとなる。したがって、パラメーターｔはウィンドウ座標における光線の深度として扱うことができる。
【００７５】
光線サーフェイス交差は、セル座標４０１において効率的に行うことができる。したがって、光線の始点及び光線の方向は、逆行列Ｃ−１Ｍ−１Ｐ−１Ｖ−１を乗算されることによって、ウィンドウ座標からセル座標に変換される。次に、光線と、座標軸に平行なバウンディングボックスとの、前方交差における光線パラメーターｔｆｒｏｎｔ及び後方交差における光線パラメーターｔｂａｃｋが従来通りに求められる。ｔｆｒｏｎｔ＞ｔｂａｃｋの場合、光線はバウンディングボックスには出会わず、サーフェイスと交差することができないため、画像サンプリング点の処理はこれ以上必要ではなく、処理は次の画像サンプリング点に進む。光線がバウンディングボックスと交差する場合、前方交差の座標Ｒ（ｔｆｒｏｎｔ）及び後方交差の座標Ｒ（ｔｂａｃｋ）が光線方程式から計算される。
【００７６】
復元カーネルを使用して、距離フィールドｄｆ＝ｄ（Ｒ（ｔｆｒｏｎｔ））は前方交差座標において補間され、ｄｂ＝ｄ（Ｒ（ｔｂａｃｋ））は後方交差座標において補間される。ｄｆ≦０かつｄｂ≧０である場合、前方交点はサーフェイスの外側にあり、後方交点はサーフェイスの内側にあり、光線はサーフェイスに交差する。そうでない場合、処理は次の画像サンプリング点に進む。ｄｆ＜０かつｄｂ＜０の光線はサーフェイスの完全に外側にある一方、ｄｆ＞０かつｄｂ＞０の光線はサーフェイスの完全に内側にある。
【００７７】
光線／サーフェイス交差の座標を見つけるのに多数の方法を用いることができる。或る特定の距離フィールド表現の場合に、光線及びサーフェイスの交点における光線パラメーターの閉形式の解析解を見つけることが可能である場合がある。代替的に、ニュートン−ラプソン近似のような反復手順を使用することができる。反復手順の良好な開始点を取得するために、距離フィールド補間の線形近似ｄ（ｔ’）＝ｄｆ＋ｔ’（ｄｂ−ｄｆ）を使用することができる。この際、ｔ’＝ｄｆ／（ｄｆ−ｄｂ）においてｄ（ｔ’）＝０である。多くの場合に、実際の交点からの誤差を小さくすることができるので、この開始点を交点として使用することができる。パラメーターｔ’から、交点における光線パラメーターｔｓをｔｓ＝ｔｆ＋ｔ’（ｔｂ−ｔｂ）によって求めることができる。
【００７８】
上述したように、光線／サーフェイス交差部における光線パラメーターｔｓは、ウィンドウ座標におけるサーフェイスの深度である。サーフェイスセルのそれぞれの寄与の正確な遮蔽のために、ｚバッファーが深度検査３６０に使用される。パラメーターｔｓは、画像サンプリング点のｚバッファー内に格納されている深度値ｚ（ｘｗ，ｙｗ）と比較される。ｔｓ＞ｚ（ｘｗ，ｙｗ）の場合、現在の光線／サーフェイス交差部は、前のサーフェイスセルによって遮蔽されている。したがって、さらなる処理は必要とされない。
【００７９】
現在の交点がｚテストを通過する場合、処理は照明計算３８０に進む。交点の光線座標から、セル座標における交点がＲｓ＝Ｒｆ＋ｔ’（Ｒｂ−Ｒｆ）によって求められる。従来のフォンシェーディングの場合、サーフェイス法線ベクトルＮが、復元カーネルから交点Ｒｓにおいて求められる。次に、照明計算が従来通り実行される。
【００８０】
クラックの修正
距離フィールドレンダリング方法によっては、出力画像において「クラック」として現れる画像アーティファクトが生じる。クラックは、隣接するサーフェイスセルが異なるサイズを有する可能性があり、それによって距離フィールドサンプリング点から復元されるサーフェイスロケーションがわずかに異なることに起因して発生する。たとえば図８に示すように、大きなセル８０２内のサーフェイスの部分８０１は、小さなセル８０４内の部分８０２とわずかに異なるロケーションにおいて復元され、それによって光線８０５はクラック８０６を通過する。
【００８１】
本発明者らのレンダリング方法は、そのようなクラックを除去する非常に明快で効率的な手段を提供する。距離フィールドを使用して、光線がサーフェイスセルに入る入口点６１１及び光線がサーフェイスセルを出る出口点８１２が共にセル内のサーフェイスの部分に関してサーフェイスの内部にあるか否かを判断し、真である場合、画像に対する寄与が光線の入口点から求められる。
【００８２】
詳細には、小さなセル８０４における光線８０５の場合のように、サーフェイスセルのバウンディングボックスと交差し、オブジェクトのサーフェイスの完全に内部にある光線については、まずｔ’＝０とし、次に光線がサーフェイスと交差したかのように光線の処理を継続する。これは、これらのエリアのバウンディングボックスの前部８０７を、それがサーフェイスの一部であるかのようにレンダリングする効果を有する。これは概算のサーフェイスであるが、このエリアにおける画像サンプリング点は正しいサーフェイスの内側にあり、それゆえ、概算のサーフェイス由来のほとんどの画像サンプリング点は、ｚテストに通らないか、又は隣接セルからの正しいサーフェイスによって後に上書きされ、そうでないエリアにおいてのみクラックが現れる。
【００８３】
復元カーネルから求められた概算サーフェイス点のサーフェイス法線は、正確なサーフェイスの法線と同じ方向に向いており、これによって、修正エリアにおけるサーフェイスの照明上のアーティファクトが回避される。この手順によって出力画像内のクラックが除去される。
【００８４】
距離フィールドによって記述されるサーフェイスは、実際には空間的に連続しており、クラックも穴も有しないことを理解されたい。レンダリングされた画像内に現れるいかなるクラックも、レンダリングプロセスのアーティファクトである。
【００８５】
空間的に分割された距離フィールドをレンダリングする方法は、異なる計算システムにおいて実行される。この方法は、Ｃ又はＣ＋＋のような汎用プログラミング言語で書かれ、コンパイルされて汎用ＣＰＵで動作する。代替的に、本方法は、汎用プログラミング言語、及びＯｐｅｎＧＬシェーダー言語のような専用グラフィックプログラミング言語の組み合わせで書かれ、ＣＰＵ及びグラフィック処理ユニット（ＧＰＵ）の組み合わせにおいて実行することができる。代替的に、カスタム特定用途向け集積回路（ＡＳＩＣ）又はフィールドプログラマブルゲートアレイ（ＦＰＧＡ）のようないくつかの他の専用プロセッサを用いることができる。本方法は、コンピューター可読媒体に格納することができる。
【００８６】
シミュレーションアプリケーション
図９に示すように、上述された本方法は、材料を製造物９０１から取り除く工作機械９１０の動作をシミュレートするためのシステムにおいて使用することができる。従来の機械加工は、一群の材料加工プロセスを含み、該プロセスにおいて、旋盤、フライス盤、及びボール盤のような電力駆動型工作機械が鋭利な切削工具と共に使用されて、材料を機械的に切断し、所望の形状、たとえば３Ｄモデル１１１によるオブジェクト１０１の形状を達成する。
【００８７】
ほとんどの現代的な工作機械は、コンピューター数値制御（ＣＮＣ）を使用する。ＣＮＣにおいて、コンピューター実装されるコントローラーが、プログラム、たとえばＧコード９０２を実行し、工作機械を駆動する。工具の通過ごとに約０．００３ｍｍ未満の材料を取り除くために、通常、非常に高い精度の工作機械が設定される。明らかに、機械のオペレーターがそのように小さな変化を観測するのは不可能である。したがって、工具９０１の操作をシミュレートする（９２０）必要がある。シミュレーション９２０の間、本発明において説明されるレンダリング方法は、オペレーターが、機械加工プロセスにおける誤りを、部品が実際に機械加工される前に視覚的に識別することを可能にする。
【００８８】
本発明を好ましい実施の形態の例として説明してきたが、本発明の趣旨及び範囲内で様々な他の適応及び変更を行うことができることは理解されたい。したがって、添付の特許請求の範囲の目的は、本発明の真の精神及び範囲内に入るすべての変形及び変更を包含することである。
【図１Ａ】
0005188628.tif 000003
【図１Ｂ】
0005188628.tif 000004
【図２】
0005188628.tif 000005
【図３】
0005188628.tif 000006
【図４】
0005188628.tif 000007
【図５】
0005188628.tif 000008
【図６Ａ】
0005188628.tif 000009
【図６Ｂ】
0005188628.tif 000010
【図６Ｃ】
0005188628.tif 000011
【図７Ａ】
0005188628.tif 000012
【図７Ｂ】
0005188628.tif 000013
【図８】
0005188628.tif 000014
【図９】
0005188628.tif 000015