(57)【要約】サンプル・ポイントの発生は、並行処理で行われ、その結果は後続する過程で収集され、後続する画像表示処理に必要なものとして用いられる。サンプル・ポイントはコース・ハルトン・シーケンスを用いて発生させる。このコース・ハルトン・シーケンスは、式１１で与えられるコース・ラディカル・インバース・ヴァリューＦbi,M（ｊ）を利用している。ここで、基数「ｂ」は好ましくは素数であるが、「Ｍ」の約数ではない。また、「ｉ」は整数とする。この定義を用いると、積分値を評価する際に用いられるサンプル・ポイントを定義するのに用いられるｓ次元のコース・ハルトン・シーケンスＵsCHal,i,Mを式１２のように定義可能である。ここで、ｂ１、…、ｂｓは「Ｍ」の約数ではない最初の「ｓ」個の数である。「ｉ」の各々の値は、ロー・ディスクレパンシ・シーケンスであるサブシーケンスを定義する。そして、これも処理に関連して用いられる。同様にして、「ゼロ」から「Ｍ−１」までのあらゆる「ｉ」の値に対する全てのサブシーケンスの集合は、同様にロー・ディスクレパンシ・シーケンスである。このため、このような全ての「ｉ」の値に対するコース・ハルトン・シーケンスを用いた処理の結果をまとめて収集することによって、同様の手法でサンプル・ポイントを規定するためのハルトン・シーケンスを用いてサンプル・ポイント発生させたかのような結果を得ることができる。
2005503607.tif 000002
【特許請求の範囲】
【請求項１】
光景の一点を表す画像内のピクセルのピクセル値を発生させるコンピュータ・グラフィクス・システムであって、選択された関数の積分値を評価することによって該ピクセル値を発生するべく構成されており、
Ａ．所定の確定的コース・ロー・ディスクレパンシー・シーケンスを用いて、一群のサンプル・ポイントを発生するよう構成されているサンプル・ポイント発生器と、
Ｂ．該サンプル・ポイント発生器により生成したサンプル・ポイントの内の一つにおける上記選択された関数の評価をそれぞれ表す複数の関数値を発生させるとともに、当該関数値を用いて該ピクセル値を発生させる関数評価部とをそなえる、コンピュータ・グラフィクス・システム。
【請求項２】
該サンプル・ポイント生成部が、前記コース・ハルトン・シーケンスとして前記所定のコース・ロー・ディスクレパンシー・シーケンスを発生させるように構成されている、請求項１記載のコンピュータ・グラフィクス・システム。
【請求項３】
該サンプル・ポイント生成部が、下記の式にて定められる根基逆数値Φbi,M（ｊ）を用いて前記コース・ハルトン・シーケンスを発生させるように構成されている、請求項２記載のコンピュータ・グラフィクス・システム。
【数１】
2005503607.tif 000027
ここで、基数「ｂ」は好ましくは素数であり、且つ「Ｍ」の約数ではなく、又、根基逆関数Φbは下記の式により定義されるものとする。
【数２】
2005503607.tif 000028
なお、
【数３】
2005503607.tif 000029
は、整数基数「ｂ」における数「ｉ」を表すものとする。
【請求項４】
前記サンプル・ポイント発生器が該サンプル・ポイントを発生するときにおけるコース・ハルトン・シーケンスが、所定の置換演算子σに従ってスクランブルされたコース・ハルトン・シーケンスである、請求項３記載のコンピュータ・グラフィクス・システム。
【請求項５】
該サンプル・ポイント発生器が、整数０からｂ−１にわたる対称群Ｓbから作られており、かつ置換演算子σを用いてスクランブルされたコース・ハルトン・シーケンスを発生するべく構成されており、スクランブルされた根基逆関数が下記の式によって定義されている、請求項４記載のコンピュータ・グラフィクス・システム。
【数４】
2005503607.tif 000030
【請求項６】
該サンプル・ポイント発生器が、基数ｂ＝２に対して置換σ2＝（０，１）から帰納的に定義されたスクランブルされた置換演算子σを用いてコース・ハルトン・シーケンスを発生するべく構成され、置換の手順が下記のごとく定義されている、請求項５記載のコンピュータ・グラフィクス・システム。
（i）基数「ｂ」が偶数のときには、該置換演算子σbが、先ず２σb/2の値をとり、次に２σb/2＋１を付加することによって発生させる。
（ii）基数「ｂ」が奇数のときには、σb-1の値をとり、（ｂ−１）／２よりも大きいかまたは等しい各々の値を１だけインクリメントし、ｂ−１の値を両者の間に挿入する。
【請求項７】
前記サンプル・ポイント発生器におけるコース・ハルトン・シーケンスが、下記のようなｓ次元のコース・ハルトン・シーケンス，ＵsCHal,iMとして発生すべく構成されている、請求項３記載のコンピュータ・グラフィクス・システム。ただし、ｂ1，…，ｂsは、「Ｍ」の約数ではない最初の「ｓ」個の素数である。
【数５】
2005503607.tif 000031
【請求項８】
該サンプル・ポイント発生器が、複数のコース・ハルトン・シーケンスを発生させるべく構成され、各々のコース・ハルトン・シーケンスは、異なった値「ｉ」に対応付けられており、その各々のコース・ハルトン・シーケンスはサブシーケンスとして機能している、請求項３記載のコンピュータ・グラフィクス・システム。
【請求項９】
該関数評価器が、上記サンプル・ポイント発生器が発生したサンプル・ポイントの内の一つにおいて上記選択された関数の評価をそれぞれ表す複数の関数値を発生させるべく構成され、該関数評価器が、異なるサブシーケンスに対して選択された関数を並行して評価するよう構成されている、請求項８記載のコンピュータ・グラフィクス・システム。
【請求項１０】
該サンプル・ポイント発生器が、「０」と「Ｍ−１」との間の全ての値「ｉ」に対応するサブシーケンスを発生すべく構成されている、請求項８記載のコンピュータ・グラフィクス・システム。
【請求項１１】
光景上の一点を表す画像内のピクセルのピクセル値を選択された関数の積分値を評価することによって容易に発生させるコンピュータ・グラフィクス表示方法であって、
Ａ．所定のコース・ロー・ディスクレパンシー・シーケンスを用いることによって、サンプル・ポイント群を発生するステップを含んでいるサンプル・ポイント発生ステップと、
Ｂ．該サンプル・ポイント発生ステップにより発生したサンプル・ポイントの内の一つにおいて上記選択された関数の評価をそれぞれ表す複数の関数値を発生させるとともに、該ピクセル値を発生させる際にその関数値を使用する関数評価ステップとをそなえている、コンピュータ・グラフィクス表示方法。
【請求項１２】
該サンプル・ポイント発生ステップが、コース・ハルトン・シーケンスとして所定の確定的コース・ロー・ディスクレパンシー・シーケンスを発生する手順を含んでいる、請求項１１記載のコンピュータ・グラフィクス表示方法。
【請求項１３】
該サンプル・ポイント発生ステップが、下記の式にて定められる根基逆数値Φbi,M（ｊ）を用いた上記コース・ハルトン・シーケンスを発生させるステップを含んでいる請求項１２記載のコンピュータ・グラフィクス表示方法。
【数６】
2005503607.tif 000032
ここで、基数「ｂ」は好ましくは素数であり、且つＭの約数ではなく、又、根基逆関数Φbは下記の式により定義されるものとする。
【数７】
2005503607.tif 000033
なお、
【数８】
2005503607.tif 000034
は、整数基数「ｂ」における数「ｉ」を表すものとする。
【請求項１４】
該サンプル・ポイント発生ステップにおいてサンプル・ポイントを発生するときにおけるコース・ハルトン・シーケンスが、所定の置換演算子σに従ってスクランブルされたコース・ハルトン・シーケンスを含んでいる請求項１３記載のコンピュータ・グラフィクス表示方法。
【請求項１５】
該サンプル・ポイント発生ステップが、整数０からｂ−１にわたる対称群Ｓbから作られており、かつ置換演算子σを用いてスクランブルされたコース・ハルトン・シーケンスを発生するステップを含んでおり、スクランブルされた根基逆数が下記の式によって定義されている請求項１４記載のコンピュータ・グラフィクス表示方法。
【数９】
2005503607.tif 000035
【請求項１６】
該サンプル・ポイント発生ステップが、基数ｂ＝２に対して置換σ2＝（０，１）から帰納的に定義されたスクランブルされた置換演算子σを用いてコース・ハルトン・シーケンスを発生するステップを含み、置換の手順が下記のごとく定義されている、請求項１５記載のコンピュータ・グラフィクス表示方法。
（i）基数「ｂ」が偶数のときには、置換演算子σbはまず２σb/2の値をとり、次に２σb/2＋１を付加することによって発生させる。
（ii）基数「ｂ」が奇数のときには、置換演算子σbはσb-1の値をとり、（ｂ−１）／２よりも大きいかまたは等しい各々の値を１だけインクリメントし、ｂ−１の値を両者の間に挿入する。
【請求項１７】
上記サンプル・ポイント発生ステップにおけるコース・ハルトン・シーケンスが、下記のようなｓ次元のコース・ハルトン・シーケンスＵsCHal,i,Mとして発生するステップを含んでいる、請求項１３記載のコンピュータ・グラフィクス表示方法。ただし、ｂ1，…，ｂsは、「Ｍ」の約数ではない最初の「ｓ」個の素数である。
【数１０】
2005503607.tif 000036
【請求項１８】
該サンプル・ポイント発生ステップが、複数のコース・ハルトン・シーケンスを発生させるステップを含み、各々のコース・ハルトン・シーケンスは、異なった値「ｉ」に対応付けられており、その各々のコース・ハルトン・シーケンスはサブシーケンスとして機能している、請求項１３記載のコンピュータ・グラフィクス表示方法。
【請求項１９】
該関数評価ステップは、上記サンプル・ポイント発生ステップにおいて発生したサンプル・ポイントの内の一つにおいて上記選択された関数の評価をそれぞれ表す複数の関数値を発生させるステップを含み、該関数評価ステップが、異なるサブシーケンスに対して選択された関数を並行して評価するよう構成されている、請求項１８記載のコンピュータ・グラフィクス表示方法。
【請求項２０】
該サンプル・ポイント発生ステップが、「０」と「Ｍ−１」との間の全ての値「ｉ」に対応するサブシーケンスを発生するステップを含んでいる、請求項１８記載のコンピュータ・グラフィクス表示方法。
【請求項２１】
光景上の一点を表す画像内のピクセルのピクセル値を発生させるコンピュータ・グラフィクス・システムを提供するコンピュータとの関連で使用されるコンピュータ・プログラム・プロダクトであって、上記コンピュータ・グラフィクス・システムが、選択された関数の積分値を評価することによって該ピクセル値を発生するべく構成され、上記コンピュータ・プログラム・プロダクトが、
Ａ．所定の確定的コース・ロー・ディスクレパンシー・シーケンスを用いることによって、コンピュータが一組のサンプル・ポイントを発生することが可能なように構成されているサンプル・ポイント発生器モジュールと、
Ｂ．前記サンプル・ポイント発生器モジュールにより発生したサンプル・ポイントの内の一つにおいて上記選択された関数の評価をそれぞれ表す複数の関数値をコンピュータが発生しうるようにするとともに、ピクセル値を発生させる際にコンピュータがその関数値を使用するべく構成されている関数評価器モジュールとを、
エンコードされた形式でコンピュータが読み取り可能な媒体として構成されている、コンピュータ・プログラム・プロダクト。
【請求項２２】
該サンプル・ポイント発生器モジュールが、コース・ハルトン・シーケンスとして所定のコース・ロー・ディスクレパンシー・シーケンスを該コンピュータに発生させるべく構成されている、請求項２１記載のコンピュータ・プログラム・プロダクト。
【請求項２３】
該サンプル・ポイント発生器モジュールが、下記の式にて定められる根基逆数値Φbi,M（ｊ）を用いた上記コース・ハルトン・シーケンスを該コンピュータに発生させるべく構成されている、請求項２２記載のコンピュータ・プログラム・プロダクト。
【数１１】
2005503607.tif 000037
ここで、基数「ｂ」は好ましくは素数であり、且つ「Ｍ」の約数ではなく、又、根基逆関数Φbは下記の式により定義されるものとする。
【数１２】
2005503607.tif 000038
なお、
【数１３】
2005503607.tif 000039
は、基数「ｂ」における数「ｉ」を表すものとする。
【請求項２４】
前記サンプル・ポイント発生器モジュールがサンプル・ポイントを発生するときにおけるコース・ハルトン・シーケンスが、所定の置換演算子σに従ってスクランブルされたコース・ハルトン・シーケンスであり、コンピュータが当該コース・ハルトン・シーケンスを発生すべく構成されている、請求項２３記載のコンピュータ・プログラム・プロダクト。
【請求項２５】
該サンプル・ポイント発生器モジュールが、整数０からｂ−１にわたる対称群Ｓbから作られており、置換演算子σを用いてスクランブルされたコース・ハルトン・シーケンスをコンピュータが発生するべく構成されており、スクランブルされた根逆関数が下記の式によって定義されている、請求項２４記載のコンピュータ・プログラム・プロダクト。
【数１４】
2005503607.tif 000040
【請求項２６】
該サンプル・ポイント発生器モジュールが、基数ｂ＝２に対して置換σ2＝（０，１）から帰納的に定義された置換演算子σを用いてスクランブルされたコース・ハルトン・シーケンスをコンピュータが発生するべく構成され、置換の手順が下記のごとく定義されている、請求項２５記載のコンピュータ・プログラム・プロダクト。
（i）基数「ｂ」が偶数のときは、置換演算子σbはまず２σb/2の値をとり、次に２σb/2＋１を付加することによって発生させる。
（ii）基数「ｂ」が奇数のときは、置換演算子σbはσb-1の値をとり、（ｂ−１）／２よりも大きいかまたは等しい各々の値を１だけインクリメントし、ｂ−１の値を両者の間に挿入する。
【請求項２７】
前記サンプル・ポイント発生器モジュールにおけるコース・ハルトン・シーケンスが、該コンピュータをして下記のようなｓ次元のコース・ハルトン・シーケンスＵsCHal,i,Mとして発生すべく構成されている請求項２３記載のコンピュータ・プログラム・プロダクト。ただし、ｂ1，…，ｂsは、「Ｍ」の約数ではない最初の「ｓ」個の素数。
【数１５】
2005503607.tif 000041
【請求項２８】
該サンプル・ポイント発生器モジュールが、該コンピュータをして複数のコース・ハルトン・シーケンスを発生させるべく構成され、各々のコース・ハルトン・シーケンスが、異なった値「ｉ」に対応付けられており、その各々のコース・ハルトン・シーケンスがサブシーケンスとして機能している、請求項２３記載のコンピュータ・プログラム・プロダクト。
【請求項２９】
該関数評価器モジュールが、前記サンプル・ポイント発生器モジュールが発生したサンプル・ポイントの内の一つにおいて上記選択された関数の評価をそれぞれ表す複数の関数値を該コンピュータに発生させるべく構成され、上記関数評価器モジュールが、異なるサブシーケンスに対して選択された関数を並行して評価するよう構成されている、請求項２８記載のコンピュータ・プログラム・プロダクト。
【請求項３０】
該サンプル・ポイント発生器モジュールが、「０」と「Ｍ−１」との間にある「ｉ」の値すべてに対応するサブシーケンスを該コンピュータが発生すべく構成されている、請求項２８記載のコンピュータ・プログラム・プロダクト。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般的にはコンピュータ・グラフィクスに関し、特に、ピクセル値を表す積分値の見積もり値を発生させるためのサンプル・ポイントを提供する確定的なロー・ディスクレパンシー・シーケンスを用いて、表示すべき画像のピクセルのためのピクセル値を生成する、システム及び方法に関する。
【背景技術】
【０００２】
（ａ）参考文献の編入
マーティン・グラベンスタインらによる、「サンプル・ポイントを発生させるための確定的な方法論を用いた画像の中のピクセルのためのピクセル値を発生させるためのシステム及び方法」（以下「グラベンスタイン出願」という）と題された、１９９７年６月２３日出願の米国特許出願シリアルナンバー０８／８８０，４１８号の出願であって、その出願の譲受人に譲渡されたものを、参照文献１として編入する。
【０００３】
アレキサンダー・ケラーによる「サンプル・ポイントを発生させるための確定的な方法論を用いた画像の中のピクセルのためのピクセル値を発生させるためのシステム及び方法」（以下「ケラー出願」という）と題された、２００１年６月１９日出願の米国特許出願シリアルナンバー０９／８８４，８６１号であって、その出願の譲受人に譲渡されたものを、参照文献２として編入する。
（ｂ）発明の背景
コンピュータ・グラフィクスの世界では、対象となっている物体の表面を、例えば、１個以上の光源によって照明された３次元的な画像を２次元の画像平面に投射して表すデジタルデータを発生させたり、人間の目で見られる光景やカメラ等によって記録される光景をシミュレートしたりするのにコンピュータを用いる。なお、このカメラは、画像平面に光景の画像を投射するためのレンズをそなえても良いし、あるいはレンズというものが存在しないピンホールカメラのように構成されていてもよい。２次元画像は画素（この言葉はピクセルまたはペルともよばれる）の配列によって構成されており、各ピクセルに対して発生されるデジタルデータは、画像平面内のそれぞれのピクセルの点で画像平面に投射される各光景の色や輝度を表している。対象物の表面は、形状、色、光沢、質感などを含む様々な特性を含んでも良い。そして、これらの特性は、その画像が出来る限り実物のように見える画像として構成されるようにするために、適切に画像上に反映されることが望ましい。
【０００４】
一般的に、その光景における様々な点から反射した光が、特定のピクセルに対してその色や強度を表すピクセル値に関して与える影響は、比較的複雑な関数の１個以上の積分値の形式で表される。コンピュータグラフィクスで用いられる積分は、一般には近似解を持っていないため、この積分値を見積もるための数値解法が用いられ、これによってピクセル値を発生させることになる。典型的には、コンピュータ・グラフィクスでは、この積分値を数値的に見積もるためには通常の「モンテ・カルロ法」が用いられてきた。一般的には、モンテカルロ法は、下記の積分値を見積もるための方法である。
【０００５】
【数１】
2005503607.tif 000003
【０００６】
ここで、ｆ（ｘ）は、ｓ次元の立方体［０，１）s（すなわち、「ゼロ」を含み「１」を含まない立法体）における実関数であり、まず統計的に独立なランダムに位置するＮ個の点ｘｉ，ｉ＝１，…，Ｎを、積分領域全体にわたって発生させる。このランダム点ｘｉは、サンプル・ポイントとして利用され、これらの点においてサンプル値ｆ（ｘi）が関数ｆ（ｘ）に対して発生させられ、積分にたいする見積もり値としてのｆを下記の式のように発生させる。
【０００７】
【数２】
2005503607.tif 000004
【０００８】
サンプル値ｆ（ｘｉ）を発生させることに用いられるランダム点が増加するに従って、見積もり値であるｆｅ（上記式中におけるｆの上部に横棒を付して示した符号を、以下、文章中においてはｆｅと示す）の値は、積分値の実際の値＜ｆ＞に収斂するようになる。一般的にいって、「Ｎ」個の様々な値、すなわちサンプル点の様々な数に対して発生される見積もり値の分布は、実際の値を中心としてこの周囲に下記の式によって近似される標準偏差での正規分布となる。
【０００９】
【数３】
2005503607.tif 000005
【００１０】
ただし、サンプル値ｆ（ｘi）を発生させるために用いるポイントｘiが統計的に独立であること、すなわち、このポイントｘiはこの積分領域において真にランダムに分布しているものとする。
一般的に、モンテ・カルロ法のようなランダム処理手法を適用する場合は、形成される画像にモアレ・パターンやエイリアシングのような対象の光景には存在しない、好ましくない人為的結果が表れないようにすることが必要であるとされてきた。しかしながら、モンテ・カルロ法をコンピュータ・グラフィクスに用いる場合にいくつかの問題が持ち上がってきた。まず、モンテ・カルロ法に用いられているサンプル点ｘiは、ランダムに分布しているために、積分値の評価対象となっている領域の様々な場所に偏在してしまう可能性がある。従って、発生したポイントの偏在の仕方に応じては、モンテ・カルロ法では、その領域が重要な領域であるにもかかわらずサンプル値ｆ（ｘi）が発生しているサンプル・ポイントｘiが存在しない場合がありうる。この場合、誤差が極めて大きなものになる。コンピュータ・グラフィクスでのピクセル値を発生させる手続きでは、モンテ・カルロ法を用いて実際に発生させたピクセル値は、もしそのサンプル・ポイントｘiが領域にわたって均一に分布することが保証されていたなら含まれていたであろういくつかの要素が抜け落ちてしまう可能性があるのである。この問題は、この領域を複数のサブ領域に分割することによってある程度は軽減することができる。しかしながら、この領域をいくつのサブ領域に分割すればよいかということを、先験的に決定することは困難である。更に、複数次元の積分領域に分割するとき、ほとんどの場合でその積分領域を等しい大きさのサブ領域に分割するのであるが、そのプロセスはきわめて複雑なものとなりうる。
【００１１】
さらに、この方法は乱数を利用しているため、誤差
【００１２】
【数４】
2005503607.tif 000006
【００１３】
（ここで｜ｘ｜は「ｘ」の絶対値を表すものとする）、すなわち、見積もり値であるｆｅと実際の値である＜ｆ＞との差は蓋然的であり、更に、「Ｎ」の値が様々に大きな値をとる場合に、これに対する誤差の値が実際の値である＜ｆ＞を中心とした正規分布に近いものとなるため、発生するであろう見積もり値ｆｅのわずか６８パーセントが実際の値である＜ｆ＞のひとつの標準偏差の範囲内に収まることが保証されるにすぎない。
【００１４】
さらに、式（３）からも明らかなように、標準偏差は、サンプル・ポイント「Ｎ」が増加するに従って減少し、Ｎの平方根の逆数、すなわち
【００１５】
【数５】
2005503607.tif 000007
【００１６】
に比例する。このため、２の因数分だけ統計的誤差を縮小することが求められる場合は、４の因数分だけサンプル・ポイントＮの数を増加させることが必要になる。このため、画像の中に含まれる多数のピクセルの各々について、ピクセル値を発生させるための計算機負荷が増大することになる。
加えて、モンテ・カルロ法では、積分領域にそれぞれのサンプル・ポイントｘiのための座標軸を定義するために、乱数を必要とするが、この乱数を発生するための効率的な機構が必要になる。一般的にデジタルコンピュータは、いわゆる「乱数」発生器をそなえている。この乱数発生器は、コンピュータプログラムによって構成され、おおむねランダムであると考えられる数の組を発生する処理を行う。この乱数発生器は、決定論的技法を用いており、発生する数は厳密にはランダムではない。しかしながら、乱数発生器からの後続する乱数における統計的独立性は、コンピュータが擬似乱数を発生させるときの決定論的技法を有効に実施することによって維持されることが望ましい。
【００１７】
グラベンスタイン出願では、サンプル・ポイントを発生するための確定的な方法論を用いて画像中のピクセルのためのピクセル値を発生するためのコンピュータ・グラフィクス・システムと方法とを説明しているが、このシステムと方法においては、モンテ・カルロ法における上述した問題を回避している。グラベンスタイン出願で説明されている確定的方法論では、見積もられるそれぞれの積分がなされる領域全体にわたって一層均一にサンプル・ポイントが分布することが先験的に確保されるロー・ディスクレパンシ・サンプル・ポイント・シーケンスが提供される。このグラベンスタイン出願で説明されている一つの実施例では、用いられているサンプル・ポイントは、いわゆるハルトン・シーケンスに基づいて生成されている。この点に関しては、例えばＪ．Ｈ．ハルトンの「Numerische  Mathematik」における第２巻８４ページから９０ページ（１９９０）を、また、Ｗ．Ｈ．プレスらによるNumerical  Recipes  in  Fortran  （第２版）の３００ページ（Cambridge  University  Press、１９９２）を参照されたい。「ｂ」を基数として発生させたハルトン・シーケンスでは、基数「ｂ」は選択された素数であり、Ｈbiによって表されるシーケンスのｉ番目の値は、一般的に下記の式によって定義される「根基逆」関数Φbを用いることによって発生させる。
【００１８】
【数６】
2005503607.tif 000008
【００１９】
ここで、
【００２０】
【数７】
2005503607.tif 000009
【００２１】
は、整数の基数「ｂ」におけるｉを表している。一般的に、「ｋ」の値の根基逆数は、次のステップにより発生させる。
（１）選択された基数「ｂ」における値の数値表示として値「ｉ」を書き、ＤMＤM-1…Ｄ2Ｄ1と表記される値のための数表示とする。ここでＤｍ（ｍ＝１，２，…，Ｍ）はこの表示における数値である。
【００２２】
（２）（十進法で書かれた数における小数点に対応する）基数点を、上記のステップ（１）によって書かれた数表示ＤMＤM-1…Ｄ2Ｄ1の最下位桁のところに書く。
（３）Ｈbiに対応する０．Ｄ1Ｄ2…ＤM-1ＤMという数表示をするために基数点を中心として桁数字の配列を反転させる。
ここで、以下のような点を認識すべきである。すなわち、基数「ｂ」で記述された１、２、…、「ｋ」の数列のあらゆる値の数表示のために基数「ｂ」をどのように選択しようとも、この数表示の最下位桁は、最上位桁よりも速い速度で変化するのである。この結果、ハルトン・シーケンスＨb1、Ｈb2、…、Ｈbiにおいて、最上位桁はその速いほうの速度で変化し、その結果シーケンスの早いステージに現れる数値は、ゼロから１までの区間にわたって比較的まんべんなく分布することになり、シーケンスの遅いステージに発生する数値は、シーケンスの早いステージに発生する数値のすきまに充填されていくことになる。上述したモンテ・カルロ法において用いられる乱数ないし擬似乱数とは異なり、ハルトン・シーケンスの値は統計的には独立ではない。これとは対照的に、ハルトン・シーケンスの値は、確定的であり、その区間全体にわたって相互に重複を最大限に避け合うようになり、偏在して発生することがない。この点は、モンテ・カルロ法において用いられる乱数ないし擬似乱数が偏在して発生しうるのと対照をなしている。
【００２３】
上述したハルトン・シーケンスでは、単一次元に基づく場合を含めて、ゼロから１までの区間にわたる数値のシーケンスが提供されることに留意されたい。多次元ハルトン・シーケンスも同様の方法によって発生させることができる。ただし、それぞれの次元に応じて異なる基数を定める必要がある。
上述したハルトン・シーケンスは特別な場合であるが、一般化したハルトン・シーケンスは、以下のようにして発生させる。ゼロから１までの数値上の区間に沿ってこれらの点を含めてそれぞれの開始点を定め、異なるハルトン・シーケンスを発生させる。ゼロと１とを含めこれらの間におけるあらゆるｘ及びｙの擬似和
【００２４】
【数８】
2005503607.tif 000010
【００２５】
を２よりも大きな整数「ｐ」に対して定義する。この擬似和は最上位桁の数字から最下位桁の数字へと逆の順番で「ｘ」と「ｙ」とを表す数字を加算することによって発生させる。この各々の加算においては、次の比較的高位の桁の和から発生するキャリーの中でも加算が行われる。ここで、仮に基数「ｂ」における「ｘ」が各々の「Ｘm」が基数を「ｂ」とする桁を表す数字であるとして０．Ｘ1Ｘ2…ＸM-1ＸMのように表され、基数を「ｂ」とする「ｙ」が各々の「Ｙn」が基数「ｂ」における桁を表す数字であるとして０．Ｙ1Ｙ2…ＹN-1ＹNのように表され（さらに「Ｍ」が、基数を「ｂ」とする「ｘ」の数表現における桁の数を表し、「Ｎ」が、基数を「ｂ」とする「ｙ」の数表現における桁の数を表し、これらが相互に異なっているものとすると）、擬似和「ｚ」は０．Ｚ1Ｚ2…ＺL-1ＺLのように表される。ただし、各々の「Ｚl」は、基数「ｂ」において、
【００２６】
【数９】
2005503607.tif 000011
【００２７】
によって与えられる数であり、更に「mod」はモジュロ関数、さらに、
【００２８】
【数１０】
2005503607.tif 000012
【００２９】
はＣlがゼロに設定されているときの「ｌ−１番目」の桁位置からのキャリー値とする。
上述の擬似和関数を用いることにより、グラベンスタイン出願において説明されているシステムで使用されている一般化されたハルトン・シーケンスは、以下の手続きにより発生させる。まず、「ｂ」は整数とし、ｘ0をゼロと１とを含むこれらの数の間にある任意の値であるものとすると、ｐ進フォン・ノイマン・カクタニ変換Ｔb（ｘ）は下記の式によって与えられる。
【００３０】
【数１１】
2005503607.tif 000013
【００３１】
さらに、一般化されたハルトン・シーケンスｘ0，ｘ1，ｘ2，…は帰納的に下記の式によって与えられる。
【００３２】
【数１２】
2005503607.tif 000014
【００３３】
上記式（５）と（６）とから次のことが明らかになる。すなわち、基数「ｂ」のあらゆる値に対して一般化されたハルトン・シーケンスでは、それぞれの開始値ｘ、すなわち各々のｘ0に対して異なったシーケンスを発生することができる。上述したハルトン・シーケンスＨbiは、一般化されたハルトン・シーケンス（式（５）および（６））における、ｘ0＝０の特別な場合であることに留意されたい。
【００３４】
ケラー出願においても、確定的な方法論を用いて画像内のピクセルに対してピクセル値を発生させるコンピュータ・グラフィクスにおけるシステムと方法とが説明されている。この場合は、ｓ次元のハマーズレイ点群を用いている。このＳ次元のハマーズレイ点群は下記の式によって定義される。
【００３５】
【数１３】
2005503607.tif 000015
【００３６】
ここで、Ｉsは、ｓ次元の単位立方体  [０，１）  であり、この組内における点の数「Ｎ」は固定されており、
【００３７】
【数１４】
2005503607.tif 000016
【００３８】
は基数が「ｂx」における「ｉ」の根基逆数であって、基数ｂ1，．．．，ｂs-1の各基数をサンプル・ポイントとする場合のものである。これらの基数は必ずしも素数である必要はない。しかしながら、点の分布を相対的に均一にするためには、素数であるほうがより好ましい。
さらに、ケラー出願では、スクランブルハマーズレイ点群を用いることを説明しており、これによって高次元のロー・ディスクレパンシー・シーケンスとの関連で発生する問題を軽減したり解消したりしている。典型的には、根基逆数関数Φbは１／ｂを間隔とするｂ−１の等差サブシーケンスを有している。これは、相関パターンをもたらす。これらの相関パターンはｓ次元空間全てを使った場合にだけ顕在化するものではあるが、この相関パターンによってエイリアシングをもたらす傾向があるので望ましくない。ケラー出願では、スクランブルを導入することによってこの影響を緩和する方法について開示している。このスクランブル化は、根基逆数化に用いられているｂ項表現における桁数字に、置換を適用することに対応する。整数０、…、ｂ−１にわたる対称なグループＳbからの置換σに対して、スクランブルされた根基逆数は下記のように定義される。
【００３９】
【数１５】
2005503607.tif 000017
【００４０】
置換「σ」が置換後も同一の数列となった場合は、このスクランブルされた根基逆数は、スクランブルの処理を施されていない根基逆数に対応する。一つの実施例として、置換σは帰納的に下記のように定義される。まず基数ｂ＝２に対して置換σ2＝（０，１）から開始し、置換の順序を以下のように規定する。
（i）基数「ｂ」が偶数の場合、まず２σb/2の値をとることによって置換σbを発生させ、２σb/2＋１の値を付加する。
（ii）基数「ｂ」が奇数の場合、まずσb-1の値をとることによって置換σbを発生させ、（ｂ−１）／２よりも大きいか又は等しい各々の値を１だけインクリメントし、このｂ−１の値を中間に挿入する。
この帰納的手続きによって下記のような置換が発生する。
【００４１】
σ2＝（０，１）
σ3＝（０，１，２）
σ4＝（０，２，１，３）
σ5＝（０，３，２，１，４）
σ6＝（０，２，４，１，３，５）
σ7＝（０，２，５，３，１，４，６）
σ8＝（０，４，２，６，１，５，３，７）…
従って、基数「ｂ」での値「ｉ」に対して根基逆数が与えられたものとして、この根基逆数に対する数表示のｋ番目の桁の数が「ｊ」の値を持っていたとすると、スクランブルされた根基逆数のｋ番目の桁数は、上述の置換σbにおけるｊ番目の数の値に対応する値となる。スクランブルされた根基逆数を使用すると、これは、ハマーズレイ点群と同様、ハルトン・シーケンスやその他のロー・ディスクレパンシ・シーケンスに対して適用可能であるが、上述の相関パターンを緩和しまたは消去する。
【００４２】
確定的なロー・ディスクレパンシ・シーケンスを使用することによって、モンテ・カルロ法に関連して使用される乱数もしくは擬似乱数と比較して多くの利点が得られる。モンテ・カルロ法に関連して使用される乱数とは異なり、ロー・ディスクレパンシ・シーケンスの場合は、それぞれの領域もしくは時間区間にわたってサンプル・ポイントをいっそう均一に分布させることが確実にできるようになる。このため、モンテカルロ法を用いた場合に起こるサンプル・ポイントの偏在に起因する画像の誤差を軽減することができる。このため、モンテ・カルロ法を用いて同数のサンプル・ポイントで同じ程度の計算コストをかけた場合と比較しても、品位の向上した画像を形成することが可能となる。しかしながら、並行して複数のプロセッサを用いて画像を形成することが求められる場合には問題が生じる。なぜならば、個々のプロセッサがその処理プロセスにおいて用いるシーケンスは、ロー・ディスクレパンシ・シーケンスであることが一般的には求められるからである。
【特許文献１】
米国出願番号０８／８８０，４１８号
【特許文献２】
米国出願番号０９／８８４，８６１号
【非特許文献１】
Ｊ．Ｈ．ハルトン著「Numerische  Mathematik」第２巻（１９９０）（第８４頁−第９０頁）
【非特許文献２】
Ｗ．Ｈ．プレス等著「Numerical  Recipes  in  Fortran」第２版（Cambridge  University  Press、１９９２）（第３００頁）
【発明の開示】
【００４３】
本発明では、確定的なロー・ディスクレパンシ・シーケンスを用いて形成される画像のピクセルのピクセル値を発生させるための、新規で改良されたシステムと方法とを提供する。ここでは、ピクセル値を表す積分値の評価を発生させるためのサンプル・ポイントの発生処理が、確定的なロー・ディスクレパンシ・シーケンスを用いて行われ、システムが複数のプロセッサを並行して動作させながら行うことができるようになっている。
【００４４】
すなわち、本発明の一つの観点では、サンプル・ポイントの発生を並行して行うことのできるサンプル・ポイント発生のためのシステム及び方法を提供する。サンプル・ポイントの発生は、並行処理で行われ、その結果は後続する過程で収集され、後続する画像表示処理に必要なものとして用いられる。本発明によれば、サンプル・ポイントをコース・ハルトン・シーケンスを用いて発生させる。このコース・ハルトン・シーケンスは、下記の式で与えられるコース・ラディカル・インバース・ヴァリューΦbi,M（ｊ）を利用している。
【００４５】
【数１６】
2005503607.tif 000018
【００４６】
ここで、「ｂ」は好ましくは素数であるが、「Ｍ」の約数ではない。また、「ｉ」は整数とする。この定義を用いると、積分値を評価する際に用いられるサンプル・ポイントを定義するのに用いられるｓ次元のコース・ハルトン・シーケンスＵsCHal,i,Mを下記のように定義可能である。
【００４７】
【数１７】
2005503607.tif 000019
【００４８】
ここで、ｂ1、…、ｂsは「Ｍ」の約数ではない最初の「ｓ」個の数である。「ｉ」の各々の値は、ロー・ディスクレパンシ・シーケンスであるサブシーケンスを定義する。そして、これも処理に関連して用いられる。同様にして、「ゼロ」から「Ｍ−１」までのあらゆる「ｉ」の値に対する全てのサブシーケンスの集合は、同様にロー・ディスクレパンシ・シーケンスである。このため、このような全ての「ｉ」の値に対するコース・ハルトン・シーケンスを用いた処理の結果をまとめて収集することによって、同様の手法でサンプル・ポイントを規定するためのハルトン・シーケンスを用いてサンプル・ポイント発生させたかのような結果を得ることができる。
【発明を実施するための最良の形態】
【００４９】
本発明は、光景における画像内のピクセルのためのピクセル値を発生するためのコンピュータ・グラフィクス・システム及びその方法を提供するものである。本発明においては、積分値を見積もるためのサンプル値を発生させるときに用いられるサンプル・ポイント発生のための確定的な方法論が用いられている。この場合における積分の関数は、光景の画像における様々な点からそれぞれのピクセル値へと投射される光量子が画像形成に寄与する成分を表している。この点は、従来より用いられているランダム的もしくは擬似ランダム的方法であるモンテ・カルロ法と異なっている点である。確定的な方法を用いることによって、積分値がロー・ディスクレパンシー・シーケンスによって見積もることが要請される区間もしくは領域全体にわたって、サンプル・ポイントが一層均一に分布することが先験的に確かなものとなる。
【００５０】
図１は、そのような確定的な方法論を用いて動作するコンピュータ・システム１０を示している。この図１に示すように、ひとつの実施例としてのコンピュータ・システム１０は、プロセッサ・モジュール１１と、キーボード１２Ａ及び／又はマウス１２Ｂ（まとめて操作入力要素１２と記す場合もある）のような操作入力手段をそなえた操作入力要素と、ビデオ・ディスプレイ装置１３のような操作出力要素とをそなえている。図示のコンピュータ・システム１０は格納されているプログラムにしたがって動作する従来のコンピュータ・アーキテクチャを持つものでよい。プロセッサ・モジュール１１は、例えば一つ以上のプロセッサやメモリ、更に例えばディスク装置やテープなど（個別には示さない）の大容量蓄積装置を含む。これらの要素は、供給されるデジタル・データとのかかわりにおいて処理や蓄積の動作を行う。このプロセッサ・モジュール１１が複数のプロセッサ装置を含み、各々のプロセッサ装置が単一のタスクのうちの様々な部分を並行して処理するように構成されているものとすると、そのように構成されていない場合と比較して一層迅速にそのタスクを処理することが期待される。操作入力要素１２によって、オペレータは処理のための情報を入力することができる。ビデオ・ディスプレイ装置１３によって、プロセッサ・モジュール１１が発生した表示出力情報が画面１４にオペレータに対して表示される。この表示出力情報には、オペレータが処理のために入力したデータやオペレータが制御処理のために入力した情報、及び処理を通じて発生した情報が含まれる。プロセッサ・モジュール１１は、いわゆるグラフィカル・ユーザー・インターフェース（ＧＵＩ）を用いてビデオ・ディスプレイ装置１３に表示する情報を発生する。このグラフィカル・ユーザー・インターフェース上に、様々なアプリケーション・プログラムのための情報が様々な「ウィンドウ」の形式を用いて表示される。この場合のコンピュータ・システム１０は、オペレータが入力する情報を受けるためのキーボード１２Ａやマウス１２Ｂなどの特定のコンポーネント、及びオペレータに対して出力情報を表示するビデオ・ディスプレイ装置１３といったコンポーネントをそなえたものとして示しているが、このコンピュータ・システム１０は、図１に示すこれらのコンポーネントに加え、あるいはこれらのコンポーネントに代えて様々なコンポーネントを含んで構成されてもよい。
【００５１】
さらに付け加えると、このプロセッサ・モジュール１１は、参照符号１４で包括的に示す１つ以上のネットワーク・ポートをそなえている。このネットワークポートはコミュニケーション・リンクとつながることによってコンピュータ・システム１０がコンピュータ・ネットワークと接続されることになる。このネットワーク・ポートによってコンピュータ・システム１０がネットワーク上の別のコンピュータ・システムや装置と情報をやりとりすることができるようになる。例えばクラアント・サーバー・パラダイムに従って構築された典型的なネットワークにおいては、ネットワークにおけるある種のコンピュータ・システムはサーバーとして設計される。このサーバーとしてのコンピュータ・システムは、データとプログラム（一般的には「情報」といわれる）を蓄積し、別のコンピュータ・システム、すなわちクライアントによる処理に供される。このようにして、複数のクライアントがこの情報を使い勝手の良い形で共有することができる。特定のサーバによって維持されている情報にアクセスすることを必要としているクライアント・コンピュータ・システムは、ネットワークを通じてサーバーから情報をダウンロードすることができる。情報の処理が終了すると、そのクライアント・コンピュータ・システムは、その処理を終えた情報をサーバーに戻し、そこへ蓄積する。（上述のクラアントやサーバーを含める）コンピュータ・システムに加えて、ネットワークは、例えばプリンタ、ファックス送信機、デジタル・オーディオ・ビデオ情報蓄積装置、配信装置その他を含んで構成されることもあり、これらがネットワークに接続されている様々なコンピュータ・システムによって情報共有されることもある。ネットワーク内でコンピュータ・システムが相互接続されているコミュニケーション・リンクは、従来のように、適当な情報伝達媒体、例えばワイヤ、光ファイバケーブル、その他の媒体であってコンピュータ・システム間で信号伝達を達成することが出来るものをそなえていてもよい。コンピュータ・システムは、コミュニケーション・リンク内にメッセージを伝達させることによってネットワークに情報を伝達させる。各々のメッセージは、情報とそのメッセージを受信すべき装置を識別する識別子とを含んでいる。
【００５２】
本発明によれば、コンピュータ・グラフィクス・システムによって画像表示における並行処理を容易に行うことの出来る構成が提供される。これにより画像表示に含まれる操作は、複数のプロセッサにより並行して行うことができるようになり、画像表示のための処理速度が向上する。この並行処理は、この方法論が他の側面に拡張可能であることが認識されてはいるが、画像表示における一つの側面、特に光の発散の問題と関連付けて説明する。上述したように、グラベンスタイン出願においては、確定的な方法論を用いて画像内のピクセルのためのピクセル値を発生させるコンピュータ・グラフィクス・システム及びその方法を説明している。この方法論において用いられているサンプル・ポイントは、いわゆるハルトン・シーケンスに基づいて発生される。本発明の一つの観点によれば、コンピュータ・グラフィクス・システム１０はここでコース・ハルトン・シーケンスとよんでいるものを利用している。ここでいうコース・ハルトン・シーケンスとは、以下のように定義されるものである。ここで、Φb（ｊ）が「ｊ」の根基逆数であるものとすると、一つの整数「Ｍ」と別の整数「ｉ」とが与えられたとき、コース・ハルトン・シーケンスは、下記の式で与えられるコース・ラディカル・インバース値Φbi,M（ｊ）を利用する。
【００５３】
【数１８】
2005503607.tif 000020
【００５４】
ここで、基数「ｂ」は好ましくは素数であり、かつ「Ｍ」の約数ではないものとする。この定義を用いて、積分値を見積もることに用いられるサンプル・ポイントを定義するのに用いられるｓ次元のコース・ハルトン・シーケンスＵsCHal,i,Mは、下記の式に示すように定義される。
【００５５】
【数１９】
2005503607.tif 000021
【００５６】
ここで、ｂ1，…，ｂsは最初のｓ個の数であり、かつ「Ｍ」の約数ではないものとする。すなわち、これらの数は、「Ｍ」に対して素であるような数である。
このコンピュータ・グラフィク・システム１０は、前述したような置換σを用いたスクランブルされたコース・ハルトン・シーケンスも利用している。この場合、スクランブルされたコース・インバース値Φbi,M（ｊ，σb）は下記の式により定義される。
【００５７】
【数２０】
2005503607.tif 000022
【００５８】
ここで、σbはケラー出願とも関連する前述の各基数「ｂ」に対応する置換である。この定義を用いてスクランブルされたｓ次元のコース・ハルトン・シーケンスＵsCSHal,i,Mは下記の式により定義される。
【００５９】
【数２１】
2005503607.tif 000023
【００６０】
以下の説明は主にこのｓ次元のコース・ハルトン・シーケンスＵsCHal,i,Mに関して行う。ただし、スクランブルされたｓ次元のコース・ハルトン・シーケンスＵsCSHal,i,Mも代わりに利用されることもあることに留意されたい。
異なった値“ｉ”に対応したｓ次元のコース・ハルトン・シーケンスＵsCHal,i,Mと、スクランブルされたｓ次元のコース・ハルトン・シーケンスＵsCSHal,i,Mとは、本質的にハルトン・シーケンス及びスクランブルされたハルトン・シーケンスのサブシーケンスである。ここで、「Ｍ」を割り切ることのできる基数「ｂ」の根基逆数は含まれていない。コース・ハルトン・シーケンスとスクランブルされたコース・ハルトン・シーケンスとは、共にロー・ディスクレパンシー・シーケンスであり、上述のハルトン・シーケンスによって提示されるディスクレパンシーとは似通っている。「Ｍ」を等しく分割する基数を除去することの必要性は、下記の例によって理解される。ここに、「Ｍ」と基数「ｂ」とが共に２である１次元のハルトン・シーケンスというものを想定する。この場合、「ｉ」の偶数値に対応するサブシーケンスは、その値が区間［０，１／２）  の中に存するコース・ハルトン・シーケンスである。また、「ｉ」の奇数値に対応するサブシーケンスは、その値が区間［１／２，１）  の中に存するコース・ハルトン・シーケンスである。そしてそのいずれでもないサブシーケンスは全体の区間［０，１）にわたってロー・ディスクレパンシー特性を呈する。一方、「Ｍ」が３であり、基数「ｂ」が２であるとすると、「ｉ」の偶数値及び奇数値に対応したサブシーケンスは、全体の区間［０，１）内にその値が存在するコース・ハルトン・シーケンスとなり、区間内のどこにも偏在が起こらなくなる。さらに、各々のサブシーケンスは「ｉ」の異なった値と対応しているために、この方法では、「ｉ」の値が「Ｍ」の値よりも小さいならば、全てのサブシーケンスが互いに素であり、すなわちどの２つのサブシーケンスの組み合わせにおいても同じ値を有することは無いことが担保される。さらに、サブシーケンスを発生させるために用いられた「ｉ」の値が「ゼロ」からＭ−１までの全ての整数を含んでいるとすると、そのようなサブシーケンスの集合はそれ自身でロー・ディスクレパンシー・シーケンスである。
【００６１】
ｓ次元のコース・ハルトン・シーケンスＵsCHal,i,Mを用いると、画像表示処理の様々な側面を並行処理することが容易になる。これは、「ｉ」の各値に対応した各々のサブシーケンスがｓ次元の単位立体［０，１）sにわたってロー・ディスクレパンシー・シーケンスとなるからである。特にそのようなサブシーケンス全体の集合がそれ自身でロー・ディスクレパンシー・シーケンスとなるようサブシーケンスを発生させた場合は、「ｉ」の値が「ゼロ」からＭ−１までの全ての整数を含んでいるとすると、上述したように、どの２つのサブシーケンスの組み合わせにおいても同じ値を有することは無いことが担保される。このことは、画像表示処理のひとつの側面、特に光の発散と関連付けて説明されよう。ただし、コース・ハルトン・シーケンスＵsCHal,i,Mの利用により別の側面を並行化することとの関連において有用性を見出すことが可能である点も評価されるだろう。サブシーケンスは互いに素であるように発生するため、コンピュータ・グラフィクス・システム１０は光量子の発散に関するＭ個のジョブを並行して行うことができる。ここで、「ｉ」は「ｉ」番目のジョブを識別する働きをする。全てのジョブが実行され、所望の数「Ｎ」が蓄積されるまで光量子が発散されると、コンピュータ・グラフィクス・システム１０は、この全てのジョブから得られた結果を収集して利用することができる。これは、どの二つの光量子も同一の発散特性を持っていないからである。下記のコード・セグメント１は、プログラム・コードの表示可能なセグメントであり、Ｃプログラム言語で記述されている。
コード・セグメント１
2005503607.tif 000024
上記コード・セグメント１における（１）行から（８）行に至るemit_photons_allシーケンスによって、コンピュータ・グラフィクス・システム１０は、少なくとも表示すべき画像の部分表示に関連した表示オペレーションのために蓄積しなければならない全ての光量子を蓄積することになる。emit_photons_allシーケンスは、このオペレーションにおけるemit_photons_partシーケンスを利用している。このemit_photons_partシーケンスは、（２）行から（６ｂ）行によって決定される"actual" value M_actに対応する数のジョブの中で実行される。これらのジョブは、プロセッサ・モジュール１１によって提供されるそれぞれのプロセッサによって並行処理的に実行される。
【００６２】
一般的に、（２）行から（６ｂ）行にわたるemit_photons_all  のシーケンスでは、最初の「ｍ」個の素数によっては割り切ることのできない最小の数を決定することによってジョブの数が決定される。ここに「ｍ」は選択された数である。上述したコード・セグメント１では、「ｍ」の値は４として選択され、その最初の４個の数として、「２」，「３」，「５」，「７」が指定される。「ｍ」の値は「Ｍ」の値と一緒に用いられる。（２）行目において初期設定される提示されるジョブの数は、M_actに対応した値を決定することに用いられ、これがemit_photons_partのコマンドが実行されるときの実際のジョブの数となる。提示されたジョブの数「Ｍ」に対応して選ばれる値は「１」でもよく、またその他の適当な値でもよい。この値は、プロセッサ・モジュール１１又はそのうちの選択されたコンポーネントにおけるプロセッサの数に対応させてもよい。M_actに対応した値は、（６ａ）行及び（６ｂ）行にて決定される。コード・セグメント１においては、M_actに対応した値は、これが最初の「ｍ」個の素数でわりきることのできない最小の値に達するまでインクリメントされる。従って、「ｍ」の値が「４」であり、行（２）における提示されたジョブの数「Ｍ」が「１」から「１１」までのどれかの値のときは、「M_actの実際のジョブの数の値」は「１１」と決定される。これは、この値が最初の４個の素数によっては割り切れない最小の値だからである。一方、行（２）において提示されたジョブの数「Ｍ」が「２０」のときは、「M_actの実際のジョブの数の値」は「２３」と決定される。これは、この数が「２０」を超える数であって、当初の４個の素数によって割り切れない最小の数となるからである。「ｍ」の値はあらゆる数の基準から選択されうる。一つの実施例においては、「ｍ」の値を十分小さい値に選択することによって、M_actの値が「Ｍ」の値とは実質的には異ならないようにすることが好ましい。これは、「ｍ」の値を少なくとも次元の数である「ｓ」となるように選択することによって、「ｓ」次元のコース・ハルトン・シーケンスＵsCHal,i,Mを発生させるときに用いる基数ｂsに対応した十分な数の素数を確保するためである。一つの代替案としては、「ｍ」の値を「ｓ」とは異なるように選択し、中間値を反転させてもよい。これは、比較的小さな基数を用いて発生させたハルトン・シーケンスが望ましいサンプル・ポイントを発生させるが、「ｍ」を大きな値に選択しすぎると、避けるべきシーケンスとなってしまうからである。
【００６３】
M_actの実際のジョブの数の値が決定されると、（７）行目のemit_photons_allシーケンスでは、（９）行目から（１３ｂ）までのemit_photons_partシーケンスを用いて実際に光量子を発生し蓄積する。emit_photons_partシーケンスは、光量子の蓄積と式（９）と（１０）の関連において説明したコース・ハルトン・シーケンスＵsCHal,i,Mを利用する。コード・セグメント１における（７）行目のコマンドでは、emit_photons_allシーケンスは、emit_photons_partシーケンスを「M_act」回呼び出し、その呼び出しの各回においてそれぞれのジョブを処理するのに必要な値である「ｉ」、「N/M_act」、「M_act」の値を提供する。「ｉ」に対応して提供される値は、「０」から「M_act」までの範囲にあり、これがジョブのインデクスの作用をする。さらに、「ｉ」の値は、それぞれのジョブにおいてコース・ハルトン・シーケンスＵsCHal,i,Mの「ｉ」の値として用いられる。「M_act」の値は、全てのジョブにおいてコース・ハルトン・シーケンスＵsCHal,i,Mの「Ｍ」の値として用いられる。各々のジョブに対応してインデクス値「ｉ」の値が異なっており、「０」からM_actまでの範囲にあるので、コード・セグメント１によって、それぞれのジョブに関連したコース・ハルトン・シーケンスはすべて相互に異なっていることが確保される。この場合において、全てのジョブにより蓄積された全ての光量子は異なっている。（７）行目における「N/M_act」の値は、それぞれのジョブによって蓄積されるべき光量子の数を識別する。この値は
【００６４】
【数２２】
2005503607.tif 000025
【００６５】
と対応する。この値は、蓄積されるべき光量子の合計数である「Ｎ」、を、ジョブの数を表わす「M_act」によって除された数の整数部分である。蓄積されるべき光量子のおよその合計数である「Ｎ」は、（３）行目におけるemit_photons_allシーケンスにより提供される。「M_act」の値が「Ｎ」の値を均等に割らない場合は、蓄積されるであろう実際の光量子の数は、（３）行目における「Ｎ」よりも幾分小さな値となることに留意されたい。
【００６６】
emit_photons_partシーケンス（コード・セグメント１の（９）行目から（１３ｂ）行目）は、関数の独立変数「ｉ」、「Ｎ」、「Ｍ」の供給を受ける。emit_photons_partシーケンスを用いて作成された全てのジョブは、「Ｎ」と「Ｍ」に関して同一の値の指定を受ける。すなわち、「Ｎ」の値は（７）行目にける「N/M_act」に対応し、「Ｍ」の値は（７）行目における「M_act」の値に対応する。emit_photons_partシーケンスを用いて作成された各々のジョブは、固有の値としての「ｉ」の割り当てを受ける。各々のジョブを実行していく中で、多数の光量子が式（９）及び（１０）と関連付けて説明した「ｓ」次元のコース・ハルトン・シーケンスＵsCHal,i,Mを用いて発光し、コード・セグメント１の（１３ａ）行と（１３ｂ）行において表されている数「Ｎ」（（１１）行目において定義され、（７）行目において
【００６７】
【数２３】
2005503607.tif 000026
【００６８】
と対応付けられている数）に到達するまで蓄積されていく。光量子の発光と蓄積に関連したコンピュータ・グラフィクス・システム１０のようなコンピュータ・グラフィクス・システムを用いた方法論は、この技術分野において公知であり、以下詳細な説明は省略する。このような方法論の一つは上述したケラー出願においても説明されている。
様々なジョブが完了した後、emit_photons_allシーケンスの（８）行目に従って、全てのジョブの結果が集積される。上述したように、それぞれのジョブのジョブ・インデクス「ｉ」の値は全て固有であり、「M_act」の値よりも小さいため、全てのジョブにより発生した全ての蓄積光量子は固有になる。
【００６９】
ここで、タスクが分割されることによって発生した実際のジョブの数である「M_act」に対応した値の決定するのに用いられた最初の素数の数「ｍ」が先験的に分かっていたものとすると、「M_act」の値は固定される。これは、この値がこれらの素数のいずれによっても割り切ることの出来ない値のうち、次に大きい値である必要があるからである。しかしながら、「M_act」の値を固定とはせず、代わりに「M_act」の値に対応する最低基準値として機能する関数の独立変数「Ｍ」（（２）行目参照）に対応する値をユーザーが選択できるようにすることによって、コンピュータの実行時間中に決定してもよい。そのようにすることにより、コード・セグメント１により、emit_photons_partジョブの数が調整される。この場合は、「M_act」の値が固定されている場合よりもサンプリング性能がよくなる。
【００７０】
並行処理化に関連してコース・ハルトン・シーケンスＵsCHal,i,Mのサブシーケンスを利用することにより、その他の並行処理化の方法論、例えばハルトン・シーケンスを選択されたインデクシングの方法論を用いて複数のサブシーケンスに分割する方法論などと比較して、向上した画像表示ができるようになる。このコース・ハルトン・シーケンスＵsCHal,i,Mによって、おのおののサブシーケンスがロー・ディスクレパンシー・サブシーケンスとなることが担保され、それらが皆実質的に同一で互いに相違の少ない特性を有するようになる。このことは、その他の平行化の方法論ではかならずしも確保されている性質ではなかった。
【００７１】
図２はコード・セグメント１に関連してコンピュータ・グラフィクス・システム１０によってなされるオペレーションを詳しく説明したフローチャートである。
上述した構成には、様々な変更が加えられてもよいことに留意されたい。例えば、ハルトン・シーケンスもしくはスクランブルされたハルトン・シーケンスの代わりにその他のロー・ディスクレパンシーの確定的なシーケンスを実用的に用いてもよい。
【００７２】
また、本発明によるシステムを、その全体がまたはその部分が、特定用途のハードウェア又は汎用のハードウェアもしくはこれらの組み合わせにより構成してもよい。更に、その構成のどの部分についても、適当なプログラムによって制御されてもよい。そして、どのようなプログラムであれ、その全体又は一部が既知の方法により、システムの一部を成したり、又はシステム上に保存されたりするように構成することができる。あるいは、このようなプログラムの全体又は部分を、既知の方法で情報伝達をするためのネットワークやその他の機構を介して、システムに提供してもよい。さらに、このシステムは、オペレータがオペレータ用入力装置（図示せず）を用いて入力する情報によって操作され又は制御されてもよい。なお、この場合のオペレータ用入力装置としては、システムに直接接続されたものでも良いし、既知の方法で情報伝達するためのネットワークやその他の機構を介してシステムに情報入力するものであってもよい。
【００７３】
上述の説明は、本発明の特定の実施例を説明するものにすぎない。従って、本発明の利点の一部又は全部を維持しつつ様々な変形や変更を本発明に加えることが可能であるのは明らかである。添付の特許請求の範囲は、これらの変形や変更を網羅することを目的としたものであり、それらは本発明の趣旨に沿うものである。
【図面の簡単な説明】
【００７４】
【図１】図１は本発明に従って構築されたコンピュータ・グラフィック・システムを示すものである。
【図２】図２は図１に示したコンピュータ・グラフィック・システムの本発明にしたがう動作を説明するためのフローチャートである。
【図１】
2005503607.tif 000042
【図２】
2005503607.tif 000043
【国際公開パンフレット】
2005503607.tif 000044
2005503607.tif 000045
2005503607.tif 000046
2005503607.tif 000047
2005503607.tif 000048
2005503607.tif 000049
2005503607.tif 000050
2005503607.tif 000051
2005503607.tif 000052
2005503607.tif 000053
2005503607.tif 000054
2005503607.tif 000055
2005503607.tif 000056
2005503607.tif 000057
2005503607.tif 000058
2005503607.tif 000059
2005503607.tif 000060
2005503607.tif 000061
2005503607.tif 000062
2005503607.tif 000063
2005503607.tif 000064
2005503607.tif 000065
2005503607.tif 000066
2005503607.tif 000067
2005503607.tif 000068
2005503607.tif 000069
2005503607.tif 000070
2005503607.tif 000071
【国際調査報告】
2005503607.tif 000072
2005503607.tif 000073