(57)【特許請求の範囲】
【請求項１】
画素はシーン中の点
0004072209.tif 000097
を表し、コンピュータ・グラフィックス装置は、前記シーン中の前記点に中心を置く球面にわたって関数ｆ（ｘ）の計算によって表され、前記関数ｆ（ｘ）は  ｇ（ｘ）＋∫Ｋ（ｘ，ｙ）ｆ（ｙ）ｄｙ  の形態を持ち、ここでｆ（ｘ）（および同様にｆ（ｙ））は未知の関数、ｇ（ｘ）とＫ（ｘ，ｙ）は既知の関数で、Κ（ｘ，ｙ）は積分の「核」として機能する、画像中の画素の画素値を発生するコンピュータ・グラフィックス装置であって、
Ａ．Θ（ｘ）がヘビサイド関数を表し、ξ1(n)，ξ′1(n)，ξ2(n)，ξ′2(n)，・・・，ξL(n)，ξ′L(n)は厳密に決定論的な食い違いが小さい所定の多次元数列の成分を表し、「ｎ」が数列のインデックスを示すものとして、選択された数「Ｎ」の推定量ｆ(n)RR（ｘ）を
0004072209.tif 000098
として発生し、かつ値０を持つ項を発生するまで各推定量値ｆ(n)RR（ｘ）に対する連続した項を発生する推定量発生器と、
Ｂ．前記シーン内の前記点についての照度値を、前記推定量発生器により発生された前記推定量値の平均として発生する照度値発生器と、
Ｃ．画素値を発生する際に前記シーン中の前記点について発生された照度値を用いる画素値発生器と、
を有する、画像中の画素の画素値を発生するコンピュータ・グラフィックス装置。
【請求項２】
前記の食い違いが小さい所定の数列が多次元の一般化された多次元ホールトン数列である、請求項１に記載のコンピュータ・グラフィックス装置。
【請求項３】
前記推定量値発生器が前記推定量ｆ(n)RR（ｘ）を
0004072209.tif 000099
として発生し、ここで「ｐ（ｘ，ｙ）」は０から１までの区間の値を取る任意の関数を表す、請求項１に記載のコンピュータ・グラフィックス装置。
【請求項４】
前記推定量発生器は、少なくとも１つの推定量値を、′をつけられていない成分ξ1(n)，・・・，ξL(n)として発生する際に、選択された変換に従って処理された前記食い違いの小さい数列（ξ1(n)，ξ′1(n)，ξ2(n)，ξ′2(n)，・・・，ξL(n)，ξ′L(n)）の′をつけられていない成分を使用する、請求項１に記載のコンピュータ・グラフィックス装置。
【請求項５】
Ａ．
0004072209.tif 000100
点
0004072209.tif 000101
から向き
0004072209.tif 000102
の放出に起因する照度値、
Ｂ．
0004072209.tif 000103
ここで
（ｉ）  関数
0004072209.tif 000104
は、向き
0004072209.tif 000105
から来る光のどれだけが反射され、屈折され、さもなくば向き
0004072209.tif 000106
に散乱させられるかを記述し、かつほぼ拡散成分と、光沢のある成分と、反射する成分との和である双方向散乱分配関数であり；
（ｉｉ）  関数
0004072209.tif 000107
は幾何学的項：
0004072209.tif 000108
であり、ここで、θおよびθ′は点
0004072209.tif 000109
と
0004072209.tif 000110
におけるそれぞれの表面の法線に対する角度であり、
（ｉｉｉ）  関数
0004072209.tif 000111
は、点
0004072209.tif 000112
が点
0004072209.tif 000113
から見えるならば値１に等しく、点
0004072209.tif 000114
が点
0004072209.tif 000115
から見えないならば値０に等しい可視度関数である、請求項１に記載のコンピュータ・グラフィックス装置。
【請求項６】
画素はシーン中の点
0004072209.tif 000116
を表し、画素値は、前記シーン中の前記点に中心を置く球面上にわたる積分の計算によって表され、前記積分は形
0004072209.tif 000117
を持ち、ここでｆ（ｘ）（および同様にｆ（ｙ））は未知の関数、ｇ（ｘ）とＫ（ｘ，ｙ）は既知の関数で、Ｋ（ｘ，ｙ）は積分の「核」として機能する、全体照明をシミュレートするように発生される、画像中の画素の画素値を発生する、推定量発生器と照度値発生器と画素値発生器とを有するコンピュータ・グラフィックス装置で行われるコンピュータ・グラフィックス方法であって、
Ａ．前記推定量発生器が、Θ（ｘ）がヘビサイド関数を表し、ξ1(n)，ξ′1(n)，ξ2(n)，ξ′2(n)，・・・，ξL(n)，ξ′L(n)，が厳密に決定論的な食い違いが小さい所定の数列の成分を表し、「ｎ」が数列のインデックスを示すものとして、選択された数「Ｎ」の推定量ｆ(n)RR（ｘ）を
0004072209.tif 000118
として発生し、そして、前記推定量発生器が値０を持つ項を発生するまで各推定量値ｆ(n)RR（ｘ）に対する連続した項を発生することと、
Ｂ．前記照度値発生器が、前記シーン内の前記点についての照度値を、前記推定量値の平均として発生することと、
Ｃ．前記画素値発生器が、画素値を発生する際に前記シーン中の前記点について発生された照度値を用いることと、
を有する、画像中の画素の画素値を発生するコンピュータ・グラフィックス法。
【請求項７】
食い違いの小さい前記所定の数列が一般化された多次元ホールトン数列である、請求項６に記載のコンピュータ・グラフィックス方法。
【請求項８】
前記推定量値ｆ(n)RR（ｘ）が
0004072209.tif 000119
として発生され、ここに「ｐ（ｘ，ｙ）」は０から１までの区間内の値をとる任意の関数を表す、請求項６に記載のコンピュータ・グラフィックス方法。
【請求項９】
少なくとも１つの推定量値を、′をつけられていない成分ξ1(n)，・・・，ξL(n)として発生する際に、前記食い違いの小さい数列（ξ1(n)，ξ′1(n)，ξ2(n)，ξ′2(n)，・・・，ξL(n)，ξ′L(n)）の′をつけられていない成分が、選択された変換に従って処理される、請求項６に記載のコンピュータ・グラフィックス法。
【請求項１０】
Ａ．
0004072209.tif 000120
点
0004072209.tif 000121
から向き
0004072209.tif 000122
の放出に起因する照度値、
Ｂ．
0004072209.tif 000123
ここに
（ｉ）  関数
0004072209.tif 000124
は、向きｗ′から来る光のどれだけが向きｗ′に反射され、屈折され、さもなくば散乱させられるかを記述し、かつほぼ拡散成分と、光沢のある成分と、反射する成分との和である双方向散乱分配関数であり
（ｉｉ）  関数
0004072209.tif 000125
は幾何学的項
0004072209.tif 000126
であり、ここで、θおよびθ′はそれぞれ点
0004072209.tif 000127
と
0004072209.tif 000128
において各表面の法線に対する角度であり、
（ｉｉｉ）  関数
0004072209.tif 000129
は、点
0004072209.tif 000130
が点
0004072209.tif 000131
から見えるならば値１に等しく、点
0004072209.tif 000132
が点
0004072209.tif 000133
から見えないならば値０に等しい可視度関数である、
請求項６に記載のコンピュータ・グラフィックス法。
【発明の詳細な説明】
発明の分野
本発明は概してコンピュータ・グラフィックスの分野に関し、特に、画像中の画素の画素値を発生する装置および方法に関する。
発明の背景
コンピュータ・グラフィックスにおいては、たとえば三次元シーンの記録をたとえばカメラによってシミュレートするために、１つまたは複数の光源により照明されている、三次元シーン中の物体の表面の二次元画像面上の投影を表すデジタル・データを発生するためにコンピュータが用いられている。カメラはシーンの画像を画像面上に投影するためのレンズを含むことができ、またはレンズは用いられないピンホールカメラで構成できる。二次元画像は画像要素（それらは「画素（ｐｉｘｅｌ）」または「ペル（ｐｅｌ）」と呼ばれる変量である）のアレイの形をし、各画素ごとに発生されるデジタル・データは画像平面上に投影されたシーンの画像平面内のそれぞれの画素の点における色と輝度を表す。物体の表面は、形、色、鏡面度、きめ等を含むいくつかの特性のいずれかを有することができる。実物のように見える画像を得るために、それらの特性は画像中でできるだけしっかりと表現することが好ましい。
一般に、特定の画素の色と強さを表す画素値へのシーン中の種々の点から反射される光の寄与は、比較的複雑な関数の１つまたは複数の積分の形で表される。コンピュータ・グラフィックスで用いられる積分は閉じられた形の解を一般に持たないために、それらを計算して画素値を発生するために数値法を使用しなければならない。通常は、積分を数値計算するためにコンピュータ・グラフィックスでは通常の「モンテ・カルロ」法が用いられてきた。一般に、モンテ・カルロ法では、ｆ（ｘ）を０から１まで（０と１を含む）の実数区間としてについての実関数として積分
0004072209.tif 000002
を計算するために、統計的に独立しているＮ個の乱数ｘi、ｉ＝１，．．．，Ｎが前記区間にわたって発生させられる。乱数ｘiは、関数ｆ（ｘ）についての標本値ｆ（ｘi）が発生される標本点として用いられる。次にその積分に対する推定値ｆが
0004072209.tif 000003
として発生させられる。標本点ｆ（ｘi）の発生するのに用いられる乱数の数が増加するにつれて、推定値ｆが積分＜ｆ＞の実際の値へ向かって収束する。一般に、ｆ（ｘi）を発生するために用いられる値ｘiが統計的に独立であるとすると、すなわち、値ｘiが真に無作為に発生されるものとすると、「Ｎ」の種々の値に対して、すなわち、標本の種々の数に対して発生される推定値の分布は、
0004072209.tif 000004
で計算される標準偏差σで、実際の値を中心とする正規分布である。
一般に、モンテ・カルロ法に類似する無作為方法は、モアレ・パターンおよびエイリアシング（ａｌｉａｓｉｎｇ）等の、シーン中にはない望ましくない人工物が、発生される画像中に発生されないようにする必要があると信じられている。しかし、コンピュータ・グラフィックスにおけるモンテ・カルロ法の使用からいくつかの問題が起きる。第１に、モンテ・カルロ法で使用される標本点ｆ（ｘi）はランダムに分布しているために、それらは区間にわたって一般に一様に分布しないことがあり、その代わりに、積分を計算すべき区間の種々の領域にかたまることがある。したがって、発生される乱数の組に応じて、モンテ・カルロ法では区間の大きな部分に標本値ｆ（ｘi）が発生される標本点ｘiが存在しないことがある。その場合には、誤差が非常に大きくなることがある。コンピュータ・グラフィックスにおいて画素値を発生するということに関して、モンテ・カルロ法を用いて実際に発生される画素値は、標本点ｘiが区間にわたってほぼ一様に分布することを保証されるならば反映されることがあるいくつかの要素を反映しないことがある。この問題は、区間を複数の小区間に分割することによっていくらか軽減できるが、区間を分割すべき小区間の数を先験的に決定することは一般に困難であり、かつ多次元積分領域（これは、ここで説明している一次元区間の代わりに、コンピュータ・グラフィックスで実際に用いられている）では領域を等しい大きさの小領域に区分することは全く複雑であることがある。
また、この方法は乱数を使用しているために、推定値ｆと実際の値＜ｆ＞との誤差
0004072209.tif 000005
（ここに│ｘ│は値「ｘ」の絶対値を表す）は確率的であり、かつ「Ｎ」の種々の値に対する誤差値は実際の値＜ｆ＞の周囲に正規分布しているために、発生させられるかもしれない推定値ｆの６８パーセントのみが実際の値＜ｆ＞の１標準偏差内に含まれることが保証される。
さらに、式（３）から明らかなように、標準偏差σは標本の数Ｎが増加すると小さくなり、「Ｎ」の平方根の逆数
0004072209.tif 000006
に比例する。したがって、統計的な誤差を半分にしたいとするならば、標本の数Ｎを４倍にする必要がある。そうすると、画像中の数多くの各画素について、画素値を発生するのに必要な計算負荷が増加する。
また、モンテ・カルロ法は乱数を必要とするために、乱数を発生する効率的な機構が必要とされる。一般に、デジタルコンピュータにいわゆる「乱数」発生器が設けられている。その乱数発生器は、ほぼ乱数である１組の数を発生するために処理できるコンピュータ・プログラムである。乱数発生器は決定論的技術を使用するために、発生される数は真にランダムではない。しかし、乱数発生器からの引き続く乱数が統計的に独立しているという性質を、疑似乱数をコンピュータ上で決定論的に実現することによって維持すべきである。
発明の概要
本発明は、画像の様子を決定する積分の計算に使用される標本点を発生する、厳密に決定論的な方法論を用いて画像中の画素の画素値を発生する新規かつ改良されたコンピュータ・グラフィックス装置および方法を提供するものである。
簡単に要約すれば、本発明のコンピュータ・グラフィックス装置は、
（１）点光源とは異なって、ディスクなどの、面積を持つ光源によって照明されるシーンについて発生されるぼやけた影、
（２）視野の深さのシミュレーション、
（３）動きのぼけ、
（４）ジッタリング、および
（５）全体的な照明、
を含む、いくつかのコンピュータ・グラフィックス技術をシミュレートするために用いられる積分を計算するための標本点として、厳密に決定論的な、食い違いの小さい数列、たとえばホールトン（Ｈａｌｔｏｎ）数列を用いて、シーン中の物体の画像中の画素の画素値を発生する。
このコンピュータ・グラフィックス装置は、
（１）シーンを照明している光源の領域にわたって標本点を発生するために、ぼやけた影に関連して、
（２）シーンと画像との間のレンズの領域にわたって標本点を発生するために、視野の深さのシミュレーションに関連して、
（３）シーン中の動いている物体に対して動きのぼけをシミュレートすべき時間間隔にわたって標本点を発生するために、動きのぼけに関連して、
（４）画像または隣接する複数の画素にわたってジッタされた標本点を発生するために、ジッタリングに関連して、
（５）全体的照明のシミュレーションに使用される推定子を発生する、厳密に決定論的なロシアルーレット方法論で使用される標本点を発生するために、全体的な照明に関連して、
食い違いの小さい数列を使用する。
モンテ・カルロ技術に関連して使用される乱数とは異なって、食い違いの小さい数列は、それぞれの領域または時間間隔にわたって標本点が確実に一様に分布するようにし、それによって、モンテ・カルロ技術において起きることがあるそれらの標本点のかたまりの結果として生ずることがある誤差を小さくする。
【図面の簡単な説明】
本発明は添付されている請求の範囲に特に示されている。本発明の上記利点およびその他の利点は、添付図面とともに以下の説明を参照することによりより良く理解されるであろう。
図１は本発明に従って構成されたコンピュータ・グラフィックス装置を示す。
図２から図６Ｂは図１に示されている本発明のコンピュータ・グラフィックス装置の動作を理解するのに有用な流れ図である。
例示的実施形態の詳細な説明
本発明は、過去に用いられてきたランダムな、または疑似ランダムなモンテ・カルロ法ではなくて、シーン中の種々の点から反射される光のそれぞれの画素値に対する寄与を表す関数の積分を計算するための標本値を発生するのに使用される標本点を発生する厳密に決定論的な方法を使用する、シーンの画像中の画素の画素値を発生するコンピュータ・グラフィック装置および方法を提供するものである。この厳密に決定論的な方法によって、食い違いが小さいようなやり方で積分が計算される区間すなわち領域にわたって標本点がほぼ一様に分布することを先験的に保証するものである。
ここに添付されている図１はそのような厳密に決定論的な方法を使用するコンピュータ装置の例１０を示す。図１を参照すると、一実施形態のコンピュータ装置１０はプロセッサ・モジュール１１と、キーボード１２Ａおよび／またはマウス１２Ｂ（オペレータ入力要素１２と総称する）などのオペレータ入力部品と、ビデオ表示装置１３などのオペレータ出力要素とを備えるオペレータ・インタフェース要素とを含む。この例示的なコンピュータ装置１０は従来のプログラム内蔵コンピュータ・アーキテクチャを有している。プロセッサ・モジュール１１は、たとえば、プロセッサと、メモリと、供給されるデジタル・データに関連して処理および記憶動作を行うディスク記憶装置および／またはテープ記憶装置（別々に示されてはいない）などの大容量記憶装置を含む。オペレータ入力要素１２はオペレータが処理するための情報を入力できるようにするために設けられている。ビデオ表示装置１３は、処理のためにオペレータが入力するデータと、処理を制御するためにオペレータが入力する情報と、処理中に発生される情報とを含むプロセッサ・モジュール１１によりスクリーン１４上に発生された、出力情報をオペレータに示すために設けられている。プロセッサ・モジュール１１は、種々のアプリケーション・プログラムの情報を種々の「ウィンドウ」を用いて表示する、いわゆる「グラフィカル・ユーザ・インタフェース」（「ＧＵＩ」）を用いてビデオ表示装置１３により表示する情報を発生する。コンピュータ装置１０は、オペレータからの入力情報を受けとる、キーボード１２Ａおよびマウス１２Ｂ、出力情報をオペレータに示すビデオ入力装置１３などの特定の部品を備えているものとして示されているが、コンピュータ装置１０は図１に示されているものに加えて、またはそれの代わりに各種の部品を含むことができることが理解されるであろう。
また、プロセッサ・モジュール１１は全体が参照番号１４により示されている１つまたは複数のネットワーク・ポートを含み、これらネットワーク・ポートはコンピュータ・ネットワーク内のコンピュータ装置１１０を接続する通信リンクに接続されている。ネットワーク・ポートはコンピュータ装置１０が、ネットワーク中の他のコンピュータ装置およびその他の装置へ情報を送ること、およびそれらの装置から情報を受けることを可能にしている。たとえば、クライアント−サーバ・パラダイムに従って編成された通常のネットワークでは、ネットワーク中のあるコンピュータ装置は、他のコンピュータ装置、すなわち、クライアント・コンピュータ装置が処理するデータおよびプログラム（全体として「情報」）を蓄積し、これによってクライアント・コンピュータ装置がその情報を好都合に共用できるようにするサーバと呼ばれる。特定のサーバにより保持されている情報にアクセスする必要があるクライアント・コンピュータ装置は、サーバがその情報をそのクライアントにネットワークを通じてダウンロードできるようにする。そのデータを処理した後で、クライアント・コンピュータ装置は処理されたデータをサーバへ送り返して保存させる。コンピュータ装置（上記サーバとクライアントを含む）に加えて、ネットワークは、ネットワークに接続されている種々のコンピュータ装置の間で共用できる、たとえば、プリンタ装置およびファクシミリ装置、デジタルオーディオまたはビデオ記録・配給装置等を含むこともできる。ネットワーク中のコンピュータ装置を相互に接続する通信リンクは、従来と同じように、ケーブル、光ファイバ、またはコンピュータ装置の間で信号を伝えるためのその他の媒体を含む、都合のよいいかなる情報伝達媒体も有することができる。コンピュータ装置は、通信リンクを通じて転送される、情報と、そのメッセージを受ける装置を識別する識別子とを含むメッセージによりネットワーク上に情報を転送する。
上記のように、コンピュータ・グラフィックス装置１０は、シーン中の種々の点から反射される光のそれぞれの画素値に対する寄与を表す関数の積分を計算するのに使用される標本値を発生するために用いられる標本点を選択する、厳密に決定論的な方法を使用し、シーンの画像中の画素についての画素値を発生する。１つの特定の実施形態においては、コンピュータ・グラフィックス装置１０により用いられる厳密に決定論的な方法は、標本点が、それぞれの積分が計算される領域にわたってほぼ一様に分布することを先験的に保証する、食い違い度が小さい標本点数列を提供する。一実施形態では、用いられる標本点はいわゆるホールトン数列を基にしている。たとえば、Ｊ．Ｈ．Ｈａｌｔｏｎ著「数値数学（Ｎｕｍｅｒｉｓｃｈｅ  Ｎａｔｈｅｍａｔｉｋ）」、第２巻８４〜９０ページ（１９６０）、およびＷ．Ｈ．Ｐｒｅｓｓ他著「フォートランにおける数値レシピ（ＮｕｍｅｒｉｃａｌＲｅｃｉｐｅｓ  ｉｎ  Ｆｏｒｔｒａｎ）」（第２版）３００ページ（ケンブリッジ大学プレス（Ｃａｍｂｒｉｄｇｅ  Ｕｎｉｖｅｒｓｉｔｙ  Ｐｒｅｓｓ、１９９２））を参照されたい。選択された素数数底「ｐ」に対して発生されたホールトン数列においては、Ｈpkで表される、数列の「ｋ番目」の値は次の２つの動作によって発生される。
（１）値「ｋ」を、選択された底「ｐ」における値の数値表現として書込むことにより、Ｄｍ（ｍ＝１、２、．．．、Ｍ）がその表現の数字であるその値に対する表現をＤMＤM-1・・・Ｄ2Ｄ1として与える。
（２）基点（底１０で書かれた数の小数点に対応する）を上のステップ（１）で書かれた表現ＤMＤM-1・・・Ｄ2Ｄ1の終りに置き、その基点のまわりの数字を反映してＨpkに相当する０．Ｄ1Ｄ2・・・ＤM-1ＤMを得る。
この表現に対して選択された底「ｐ」とは無関係に、底「ｐ」で書かれた値のいかなる列１、２、．．「ｋ」に対して、その表現の最下位の数字は最上位の数字よりも速く変化することがわかるであろう。その結果、ホールトン数列ＨＭp1、Ｈp2、．．．，Ｈpkにおいては、最上位の数字がより速く変化し、その結果その数列中の初めの方の値は０から１までの区間にわたってほぼ広く分布し、その数列中の後の方の値は数列中の初めの方の値の間の隙間に入る。モンテ・カルロ法で用いられる乱数または疑似乱数とは異なって、ホールトン数列の値は統計的には独立しておらず、これに反して、ホールトン数列の値は厳密に決定論的であって、その区間にわたって相互に「最大限に避ける」ために、それらの値はかたまらないのに、モンテ・カルロ法で用いられている乱数または疑似乱数はかたまることがある。
上記ホールトン数列は１つの次元に沿って、０から１までの区間（０と１を含む）にわたって値の列を提供することがわかるであろう。同様なやり方で、しかし各次元ごとに異なる底を使用して多次元ホールトン数列を発生できる。
一般化されたホールトン数列、そのうちの上で述べたホールトン数列は特殊な場合である、は次のようにして発生される。０から１まで（０と１を含む）の数値区間に沿う各始点に対して、異なるホールトン数列を発生する。２より大きい値を持つ任意の整数「ｐ」に対して、０から１まで（０と１を含む）の区間にわたる任意のｘとｙに対して疑似和ｘ▲＋▼pｙを定めると、その疑似和を、「ｘ」と「ｙ」を表す数字を逆の順序で、最上位の数字から最下位の数字へ、加え合わせ、かつ各加算に対して、次のより上位の数字の和から生じた桁上りでまた加え合わせることによって形成する。そうすると、底「ｐ」の「ｘ」を０．Ｘ1Ｘ2・・・ＸM-1ＸMにより表し（各「Ｘｍ」は底「ｐ」での数）、底「ｐ」の「ｙ」を０．Ｙ1Ｙ2・・・ＹN-1ＹNにより表すと（各「Ｙｎ」は底「ｐ」での数）、（ここで、底「ｐ」での「ｘ」の表現における数字の数である「Ｍ」は、底「ｐ」での「ｙ」の表現における数字の数である「Ｎ」とは異なる）ものとすると、疑似和「ｚ」は０．Ｚ1Ｚ2・・・ＺL-1ＺLにより表される。ここで、各Ｚ1はＺ1＝（Ｘ1＋Ｙ1＋Ｃ1）ｍｏｄ  ｐにより与えられる底「ｐ」での数である。ここに、「ｍｏｄ」はモジュロ関数を表し、
Ｘl-1＋Ｙl-1＋Ｃl-1≧ｐに対して  Ｃl＝１
他の場合    Ｃl＝０
Ｃlは０にセットされる。
上記疑似和関数を用いて、一般化されたホールトン数列は次のようにして発生される。「ｐ」が整数で、ｘ0が０から１までの区間（０と１を含む）における任意の値であるならば、「ｐ」−ａｄｉｃ  ｖｏｎ  Ｎｃｕｍａｎｎ−Kakutani変換Ｔp（ｘ）」は
0004072209.tif 000007
により与えられ、一般化されたホールトン数列ｘ0，ｘ1，ｘ2，・・・は
ｘn+1＝Ｔp（ｘ）                      （５）
として回帰的に定められる。
式（４）と（５）から、「ｐ」の任意の値に対して、一般化されたホールトン数列は、「ｘ」の各出発値、すなわち、各ｘ0に対して発生される異なる数列を与えることができることが明らかであろう。上記ホールトン数列Ｈpkは一般化されたホールトン数列の、ｘ0＝０に対する特殊なケースである（式（４）と（５））であることがわかるであろう。
コンピュータ・グラフィックスにおいて画像中の画素の画素値を発生するために、積分の計算において食い違いの小さい数列を使用することを、いくつつかの特定のコンピュータ・アプリケーション、特に、
（１）点光源とは異なって、ディスクなどの、面積を持つ光源によって照明されるシーンについて発生されるぼやけた影、
（２）視野の深さのシミュレーション、
（３）動きのぼけ、
（４）ジッタリング、および
（５）全体的な照明、
を表す画像についての画素値の発生に関連して説明する。それらの各々に関連してコンピュータ・グラフィックス装置１０により実行される動作を以下に説明する。
（１）ぼやけた影
ぼやけた影は、シーン中の物体が、点光源の代わりに、円板などの、識別可能な面積を持つ光源により照明される時にシーン内に起きることがある。たとえば、日食が起きると、月によって地球に投影された影の周縁部がぼやけた影であり、本影部分が完全な影を構成する。日食の本影部分は、地球のうち月により太陽が完全に隠される地域に生じ、周縁部は月が太陽を部分的に隠す地域に生ずる。周縁部における影の度合いは本影から外側へ向かって進むにつれて小さくなり、周縁部は日食の「ぼやけた影」を構成する。あるシーン中の特定の影に対しては、ぼやけた影は完全に影になっているシーンの領域（もしあれば）から影のない領域までの移行を表す。
シーン中では、ある面積を持つ光源による照度を表す、シーン中のある点についての画素値の一部が、光源によるシーン中の特定の点の照度をその光源の面積にわたって平均することにより発生される。そのシーン中のその点が完全な影領域内にあるならば、これはその点がシーン中の１つまたは複数の物体により完全に隠される時に起きることであるが、その平均は完全な影を表す輝度レベルを表すであろう。同様に、その点が影のない領域内にあれば、その平均は影のないことを表す輝度レベルを表すであろう。他方、その点がシーン中の物体によって光源の全面積から部分的に隠され、したがってその点がぼやけた影領域内にあるならば、平均は隠されている光源の大きさを基にした中間輝度レベルを表すであろう。いずれの場合にも、その平均は例として二次元積分
0004072209.tif 000008
により与えられる。ここで、
0004072209.tif 000009
は照度値が発生されているシーン中の点、
0004072209.tif 000010
は点光源上の点、
0004072209.tif 000011
はシーン中の点
0004072209.tif 000012
における照度を表し、
0004072209.tif 000013
は広がりを持つ光源の光照射のレベルを示し、
0004072209.tif 000014
は、光源上の点
0004072209.tif 000015
がシーン中の点
0004072209.tif 000016
から見えれば１に等しく、光源上の点
0004072209.tif 000017
がシーン中の点
0004072209.tif 000018
から見えなければ０に等しい可視度関数である。積分は光源の面積Ａ′にわたって計算される。特定の画像に対する関数
0004072209.tif 000019
の定式化は当業者には知られていることである。
本発明に従って、コンピュータ・グラフィックス装置１０は、一般化された二次元のホールトン数列を用いて標本点
0004072209.tif 000020
の数「Ｎ」を選択することにより画素値を発生するために、積分（式（６））を計算する。標本点
0004072209.tif 000021
が発生された後で、コンピュータ・グラフィックス装置１０は関数
0004072209.tif 000022
を、発生された各標本点に対して計算し、積分（式（６））の値を、照度値
0004072209.tif 000023
を発生すべきシーン中の各点
0004072209.tif 000024
に対して
0004072209.tif 000025
として近似する。食い違いの小さい数列、例として、ホールトン数列を使用すると、標本点がかたまらなくなるが、その代わりに光源の面積にわたって一様に分布する。
一実施形態では、照度値
0004072209.tif 000026
を発生すべきシーン中の各点
0004072209.tif 000027
に対して、コンピュータ・グラフィックス装置１０は、発生されたならばぼやけた影に濃淡のむらがあるように見えるかもしれないようにするような画素値を発生することを避けるように、上記の一般化されたホールトン数列方法（式（５））に従って発生される、異なるホールトン数列を用いる。この実施形態では、画素値が発生されような画像中の点であって、シーン中の点
0004072209.tif 000028
と関連する点の座標を基にしているベース値ｘ0を用いて特定のホールトン数列が発生される。
ぼやけた影を生ずるように画素値の発生に関連して上で説明した動作が図２の流れ図で示されている。その流れ図に示されている動作は上の説明から当業者には容易にわかるので、その図の流れ図はこの明細書では個々には説明しない。
式（６）で用いられている関数
0004072209.tif 000029
は、ぼやけた影をシミュレートするために画素値の発生に関連して使用できる関数の例であることがわかるであろう。その他の関数は、式（７）と（８）に対応した変更を施すことにより、当業者には明らかであろう。たとえば、式（６）における
0004072209.tif 000030
の分母で、項
0004072209.tif 000031
は二乗（すなわち、平方）されたものであるように取られているように示されているが、他のべきを使用できること、その場合には式（７）と（８）はそれに従って修正されることがわかるであろう。また、計算のための標本点を得るために用いられるものとしてホールトン数列が示されているが、この技術で知られている、食い違いが小さい他の数列を代わりに使用できることがわかるであろう。
また、広がりを持つ光源に関連してぼやけた影をシミュレートするものとしてコンピュータ・グラフィックス装置１０を説明してきたが、コンピュータ・グラフィックス装置１０は線状光源に関連して上記のようにしてぼやけた影をシミュレートすることもできることがわかるであろう。広がりを持つ光源についてのぼやけた影のシミュレーションの場合と同じように、コンピュータ・グラフィックス装置１０は標本点
0004072209.tif 000032
を無理に光源上に来るようにする。また、光源が線状光源であれば、コンピュータ・グラフィックス装置１０は一次元に一般化されたホールトン数列を用いて標本点
0004072209.tif 000033
を発生できる。
（２）視野の深さシミュレーション
上記したように、コンピュータ・グラフィックス装置１０は、ピンホールカメラに対して記録される画像を表す表現される画像を構成する画素値を発生し、あるいは、レンズ付きカメラに対して記録される画像を表す表現される画像を構成する画素値を発生する。通常は、レンズなしカメラでは、全ての被写体は通常は焦点が合っている。しかし、レンズ付きの従来のカメラでは、レンズから特定の距離にある被写体と、「視野の深さ」として知られている、それの所定の距離の平面内の被写体とに焦点が合う。それよりも近かったり、遠かったりする被写体は次第にぼけてくる。
ある視野の深度を持つカメラに対する画像をシミュレートするために、コンピュータ・グラフィックス装置１０は積分
0004072209.tif 000034
の計算を基にして各画素についての画素値を発生する。ここで、
0004072209.tif 000035
はレンズ上の点（ｘ′，ｙ′）から画像平面内の点（ｘ，ｙ）の向きに来る照度を示す。コンピュータ・グラフィックス装置１０はレンズの面積Ａeffにわたって積分を計算する。特定の画像に対する関数
0004072209.tif 000036
の定式化は当業者に知られていることである。
本発明に従って、コンピュータ・グラフィックス装置１０は、標本点を得るためにホールトン数列を用いてレンズ上の点（ｘi，ｙi）に対する「Ｎ」個の標本点を選択することにより画素値を発生するために積分（式（９））を計算する。標本点が発生された後で、コンピュータ・グラフィックス装置１０は「Ｎ｝個の標本点（ｘi，ｙi）の各々に対して関数
0004072209.tif 000037
を計算し、積分（式（９））を
0004072209.tif 000038
として近似する。１つの特定の実施形態では、画像平面上の各点（ｘi，ｙi）に対してコンピュータ・グラフィックス装置１０は、発生したならばぼやけた影に濃淡のむらがあるように見えるかもしれないようにするような画素値を発生しないように、上記の一般化されたホールトン数列方法（式（５））に従って発生される、異なるホールトン数列を用いる。その実施形態では、画素値が発生されような画像中の点であって、画像平面中の点（ｘi，ｙi）と関連している点の座標を基にしているベース値ｘ0を用いて特定のホールトン数列が発生される。食い違いの小さい数列、例として、ホールトン数列を使用すると、標本点は確実にかたまらなくなるが、その代わりにレンズの領域にわたって一様に分布する。
視野の深さを得るように画素値の発生に関連して上で説明した動作が図３の流れ図で示されている。その流れ図に示されている動作は上の説明から当業者には容易にわかるので、その図の流れ図はこの明細書では個々には説明しない。
積分（式（９））の計算のために上記のように選択された標本点（ｘi）を使用することは、食い違いが小さい標本点の組の使用が、標本点が一緒にかたまらないようにする「自己回避」特性を有するという点で有利である。そのようにかたまることは乱数をベースにするモンテ・カルロ法などの従来の方法では起こり得ることである。別の利点は、計算の前には標本点（ｘi）の数を先験的に選択する必要がないことである。
式（９）で用いられる関数
0004072209.tif 000039
は、視野の深さをシミュレートするために画素値の発生に関連して使用できる関数の例であることがわかるであろう。他の諸関数は、式（１０）に対応する変更を加えることで、当業者には明らかであろう。また、計算のための標本点を得るために用いられるものとしてホールトン数列が示されているが、この技術で知られている、食い違いが小さい他の数列を代わりに使用できることがわかるであろう。
（３）動きのぶれ
動きのぶれは、たとえば、静止カメラで記録されつつあるシーン中の被写体が動いている時に起きる。動きのぶれが起きる理由は、カメラのシャッターが開かれている時間間隔が０でなく、かつ、動いている被写体を画像中の同じ点に正確に維持するようにカメラが動かされないならば、動いている被写体が画像中に現れる点がその時間間隔にわたって動くことである。したがって、動きの方向に交わる被写体の縁部が画像上でぶれているように見える。
開いている時間間隔が０でないシャッタのカメラにより、その中で物体が動いているシーンの画像の発生をシミュレートするために、コンピュータ・グラフィックス装置１０は、積分
0004072209.tif 000040
の計算を基にして各画素についての画素値を発生する。ここで、Ｌ（ｘ，ｙ）は点（ｘ，ｙ）の輝度、Ｌ（ｘ，ｙ，ｔ）は画像中の点（ｘ，ｙ）の時刻「ｔ」における照度、「ｔs」はシャッターが開かれている時間である。Ｌ（ｘ，ｙ）は本質的には時間ｔsにわたるＬ（ｘ，ｙ，ｔ）の平均であることがわかるであろう。特定の画像に対する関数Ｌ（ｘ；ｙ，ｔ）の定式化は当業者には知られている。
本発明に従って、コンピュータ・グラフィックス装置１０は、標本点を与えるためにホールトン数列を用いて、点（ｔi）に対するＮ個の標本点を０からｔsまでの時間間隔にわたって選択することにより画素値を発生するために積分（式（１１））を計算する。標本点が発生された後で、コンピュータ・グラフィックス装置１０は「Ｎ」個の標本点（ｔi）のおのおのに対して関数Ｌ（ｘ，ｙ，ｔ）を計算し、積分（式（１１））を
0004072209.tif 000041
として近似する。１つの特定の実施形態では、画像中の各画素に対して、コンピュータ・グラフィックス装置１０は、発生されたならばぼやけた影に濃淡のむらがあるように見えるかもしれないようにするような画素値を発生しないように、上記の一般化されたホールトン数列方法（式（５））に従って発生される、異なるホールトン数列を用いる。その実施形態では、画素値が発生されような画像中の点であって、画像中の点（ｘ，ｙ）の座標を基にしているベース値ｘ0を用いて特定のホールトン数列が発生される。食い違いの小さい数列、例として、ホールトン数列を使用すると、標本点は確実にかたまらなくなるが、その代わりに積分（式（１１））を計算すべき時間にわたって一様に分布する。
動きのぶれを行わせるように画素値の発生に関連して上で説明した動作が図４の流れ図で示されている。その流れ図に示されている動作は上の説明から当業者には容易にわかるので、その図の流れ図はこの明細書では個々には説明しない。
式（１１）で用いられる関数Ｌ（ｘ，ｙ，ｔ）は、視野の深さをシミュレートするために画素値の発生に関連して使用できる関数の例であることがわかるであろう。他の諸関数は、式（１２）に対応する変更を加えることで、当業者には明らかであろう。また、計算のための標本点を得るために用いられるものとしてホールトン数列が示されているが、この技術で知られている、食い違いが小さい他の数列を代わりに使用できることがわかるであろう。
また、画像中の各標本点（ｘ，ｙ）について時間次元「ｔ」に沿って式（１２）で使用される標本点（ｔi）を発生するために、一次元ホールトン数列をコンピュータ・グラフィックス装置１０が使用できることがわかるであろう。その場合には、画素値の発生中は、コンピュータ・グラフィックス装置１０は標本点（ｘ，ｙ）についての輝度値Ｌ（ｘ，ｙ）を式（１２）に従って発生する。あるいは、コンピュータ・グラフィックス装置１０は、式（１２）で使用される、時間次元「ｔ」と画像平面の空間次元「ｘ」と「ｙ」に沿って標本点（ｘi，ｙi，ｔi）を発生するために、たとえば、三次元ホールトン数列を使用でき、かつ輝度値Ｌ（ｘi，ｙi，ｔi）を用いる式（１２）を用いて輝度値を発生できる。ここで、（ｘi，ｙi）は画素の領域内の標本点である。
（４）ジッタリング
画像中のそれぞれの点における画素の色を表す画素についての画素値を発生するために、画素値により表される色は画素の面積にわたって平均される。それをシミュレートするために、コンピュータ・グラフィックス装置１０は、積分
0004072209.tif 000042
を計算することにより、画素Ｐiが平均された色Ｌiを有するための画素値を発生する。ここで、Ｌ（ｘ，ｙ）は画像中の点（ｘ，ｙ）における色を表し、│Ｐi│は画素Ｐiの面積を表す。特定の画像についての関数Ｌ（ｘ，ｙ）の定式化は当業者に知られていることである。
コンピュータ・グラフィックス装置１０は、標本点を得るためにホールトン数列を用いて、画素Ｐiにおける「Ｎ」個の標本点（ｘi，ｙi）を選択することにより画素値を発生するために積分（式（１３））を計算する。標本点が発生された後で、コンピュータ・グラフィックス装置１０は「Ｎ」個の標本点（ｘi，ｙi）のおのおのに対して関数Ｌ（ｘ，ｙ）を計算し、積分（式（１３））を
0004072209.tif 000043
として近似する。しかし、各画素ごとに発生されるホールトン数列を用いて積分（式（１３））を計算すると、いくつかの問題が起きる。まず、１つの画素内でかたまりが起きないことをホールトン数列は保証するが、隣接する画素の境界でかたまりが起きないことは保証しない。また、画素に対して発生されたホールトン数列は画素レベルで周期性を示し、その場合には眼に明らかに見えることがある人工物が画像中に発生することがある。
したがって、それらの問題に対処するために、本発明に従って、コンピュータ・グラフィックス装置１０はホールトン数列を発生して、画像全体に対して、または所定数の隣接する画素に対して標本点を次のようにして発生する。最初に、コンピュータ・グラフィックス装置１０は画像、または所定数の隣接する画素をサイズが「ｎ」×「ｍ」の格子を基にして分割する。ここで、ｎ＝２iは正の２のべき（「ｉ」）、ｍ＝３jは正の３のべき（「ｊ」）である。（この説明では、２と３は二次元ホールトン数列の発生のために選択された数底（すなわち、一次元ホールトン数列を記述する式４と５における「ｐ」）である。二次元ホールトン数列の発生のためにコンピュータ・グラフィックス装置１０が他の数底を使用すると、「ｎ」と「ｍ」はそれらの数底のべきであるように選択されるであろう）。その後でコンピュータ・グラフィックス装置１０は換算は「ｎ」および「ｍ」の値に従う二次元ホールトン数列を構成する、（ｎＨ2k，ｍＨ3k）、ｋ＝1，・・・，ｎｍとして式（１４）の計算に使用する標本点（ｘi，ｙi）の組を発生する。そのように発生された標本点、正確には１つの標本点は、各サブ画素の左下境界がそのサブ画素の一部を構成するものとみなされ、各サブ画素の右上境界がそのサブ画素の一部を構成しないものとみなされるならば、各画素中の複数のサブ画素のおのおのに与えられる。
たとえば、コンピュータ・グラフィックス装置１０が各画素に対する「Ｎ」×「Ｎ」のサブ画素で標本点を発生し、画像中の行の数または隣接する画素の選択されたサブセットの数がＲｅｓxであり、かつ画像中の列の数または隣接する画素の選択されたサブセットの数がＲｅｓyであるとすると、コンピュータ・グラフィック装置１０は、ｎ＝２i≧Ｎ・Ｒｅｓxおよびｍ＝３j≧Ｎ・Ｒｅｓyであるように、整数「ｉ」と「ｊ」を最初に選択することによって、画像中の画素または画素の選択されたサブセットで使用される、Ｎ・Ｒｅｓxｘ×Ｎ・Ｒｅｓy個の標本点を発生できる。「ｎ」×「ｍ」個のサブ画素のサブ画素格子は、画像のサイズまたは隣接する画素の選択されたサブセットのサイズよりも一般に大きいことに注目されたい。
上記の機構に従って、コンピュータ・グラフィックス装置１０は、それぞれの画素の領域内にある標本点を用いて各画素についての式（１４）の積分を計算できる。
式（１４）における積分の計算で、全画像または隣接する画素の選択されたサブセットに対して、換算されていない二次元ホールトン数列（すなわち、たとえば、（Ｈ2kＨ3k））を１つの画素内で標本点として用いる代わりに、換算された二次元ホールトン数列（ｎＨ2k，ｍＨ3k）を用いて標本点を発生することからいくつかの利点が生ずる。まず、換算された二次元ホールトン数列を用いることにより、換算されていない二次元ホールトン数列に関連して起きることがある、画素のレベルにおける標本点の周期性が避けられる。また、換算された二次元ホールトン数列（ｎＨ2k，ｍＨ3k）を用いると、換算されていない二次元ホールトン数列に関連して起きることがある、隣接する画素の境界に標本点のかたまりが起きなくされる。したがって、換算された二次元ホールトン数列（ｎＨ2k，ｍ3k）を用いると、標本点が全体の画像または画素の隣接する領域全体にわたって一様に分布するようにされる。これは、比較的少数の標本点が用いられるか、画素当りただ１つの標本点が用いられる場合にもそうである。
ジッタリングを生ずるように画素値の発生に関連して上で説明した動作が図５の流れ図に示されている。その流れ図に示されている動作は上の説明から当業者には容易にわかるので、その図の流れ図はこの明細書では個々には説明しない。
（５）全体照明
「全体照明」は、間接照明、拡散および光り輝く相互反射、火線（ｃａｕｓｔｉｃ）および色染み出し（ｃｏｌｏｒ  ｂｌｅｅｄｉｎｇ）などの、コンピュータ・グラフィックス装置１０がシーン中の被写体の画像の発生においてシミュレートするある種の光学的効果を含む。全体照明をシミュレートするために、「表現式」が解かれる。全体照明のシミュレーションにおいて有用な表現式の例の一般的な形式、すなわち、
0004072209.tif 000044
に対しては、シーン中の特定の点ｘに照射された光は一般に２つの成分、すなわち、その点から放出される光（もしあれば）の量と、他の全ての点から生じて、点ｘから反射さもなくば散乱させられた光（もしあれば）の量との和であるとわかっている。式（１５）において、
0004072209.tif 000045
は向き
0004072209.tif 000046
（ここで「θ」は点シーン中の点
0004072209.tif 000047
を含んでいる被写体の表面の垂直な方向に対する向きｗ）の角度を表し、「φ」は点
0004072209.tif 000048
に接する平面内の向き
0004072209.tif 000049
の成分の角度を表す）の点
0004072209.tif 000050
における放射輝度を表す。同様に、積分中の
0004072209.tif 000051
は向き
0004072209.tif 000052
（ここで、「θ′」はシーン中の点
0004072209.tif 000053
を含んでいる被写体の表面の垂直な方向に対する向き
0004072209.tif 000054
の角度を表し、「φ′」は点
0004072209.tif 000055
に接する平面内の向きｗ′の成分の角度を表す）の点
0004072209.tif 000056
における放射輝度を表し、かつ点
0004072209.tif 000057
から反射さもなくば散乱させられることがある点ｘ′から放出される光（もしあれば）を表す。
式（１５）では、
0004072209.tif 000058
は和の成分、すなわち、点ｘからの向きｗの放射に基づく放射輝度を表し、球面Ｓ′における積分は第２の成分、すなわち、点ｘにおける光の散乱に基づく放射輝度を表す。
0004072209.tif 000059
は、向きｗ′から来る光のうちのどれだけが向き
0004072209.tif 000060
に反射され、屈折され、さもなくば散乱させられるかを記述する双方向散乱分布関数であって、一般に拡散成分と、光沢のある成分と、反射成分との和である。式（１５）で、関数Ｇ（ｘ，ｘ′）は幾何学的項
0004072209.tif 000061
である。ここで、θとθ′はそれぞれ点
0004072209.tif 000062
と
0004072209.tif 000063
におけるそれぞれの表面の垂線に対する角度である。さらに式（１５）では、
0004072209.tif 000064
は、点
0004072209.tif 000065
が点
0004072209.tif 000066
から見えれば値１に等しく、点
0004072209.tif 000067
が点
0004072209.tif 000068
から見えなければ値０に等しい視度関数である。特定の画像に対する種々の関数
0004072209.tif 000069
は当業者には知られているものである。
コンピュータ・グラフィックス装置１０は、上で述べたいくつかの光学的な効果をシミュレートするために画像の発生に関連して全体照明および表現式、すなわち、式（１５）を用いる。特に、観測者が見た画像を、光子を表す光線を光源から観測者の眼まで追跡することにより画像をコンピュータ・グラフィックス装置１０がシミュレートする、光線追跡を用いるシミュレーションの１つの態様に関連して、本発明に従って、コンピュータ・グラフィックス装置１０は「厳密に決定論的なロシアルーレット」法を用いて、シミュレートされる光線を終わらせるか否かを厳密には決定論的な方法を用いて決定する。
背景として、ｆ（ｘ）（および同様にｆ（ｙ））は未知の関数、ｇ（ｘ）は既知の関数（表現式（式（１５）に関連して）
0004072209.tif 000070
Ｋ（ｘ，ｙ）は積分演算子の「核」として働く他の既知の関数
0004072209.tif 000071
である
0004072209.tif 000072
積分中に関数「ｆ」を繰り返し代入することによって、正式に解くことができる。次に、「Ｌ」次元の食い違いの小さい数列（ξ1(n)，．．．，ξL(n)）（「ｎ」は数列のインデックスを示す）を用いて、「ｇ（ｘ）」を０番目の項とみなす式（１８）におけるノイマン数列の最初の「Ｌ」個の項の食い違いの小さい標本化を行うことによって式（１７）を近似的に数値計算できる。一実施形態では、「Ｌ」次元の食い違いの小さい数列は上記のように、数列の要素が相互に最大限避けようとする、たとえばＬ次元ホールトン数列である。その数列の各要素に対して、推定量値ｆ(n)（ｘ）は
0004072209.tif 000073
として発生され、式（１９）に従って発生される「Ｎ」個の推定子ｆ(n)（ｘ）を用いてｆ（ｘ）の近似が
0004072209.tif 000074
として得られる。食い違いの小さい数列、たとえばホールトン数列を用いることによって標本点がかたまらないようにされるが、その代わりに、ノイマン数列（式（１８））の最初の「Ｌ」個の項を計算すべき空間であるＬ次元空間にわたって一様に分布する。
表現式（式（１５））を計算するために式（１７）から（２０）に関連して上で説明した方法を用いることに伴なう１つの問題は、ノイマン数列（式（１８））は無限数列であるが、ある点で数列を計算するためには数列を切り捨てる必要がある。表現式（式（１５））の計算に関連して、ノイマン数列の切り捨ての結果、画像中の望ましい諸特徴が失われることになることがある。この問題を軽減するために、本発明に従って、コンピュータ・グラフィックス装置１０は「Ｎ」個の推量量を用いてｆ（ｘ）の近似を発生するが、各推量値に対して、推量値を発生するために用いられる数列中の項の数を無限でないことを保証する方法を用いる。したがって、本発明の方法では、推量値の発生のために切り捨ては必要でなく、それによって画像の諸特徴が失われないことが保証される。
ここで「厳密に決定論的なロシアルーレット」法と呼ばれる、本発明の方法を以下に説明する。準備として、数値「ｌ」を積分
0004072209.tif 000075
として表すことができることがわかる。ここで、θ（ｘ）は
0004072209.tif 000076
として定められるヘビサイド関数（「ステップ関数」としても知られている）を示す。ここで、「ｗ」は間隔０（０を含まない）から１（１も含む）までの重み係数である。式（２１）と（２２）を用いて、数値「ｌ」に対する厳密に決定論的な推定量１estは
0004072209.tif 000077
として、および数値「１」に対する推定量を
0004072209.tif 000078
として発生する。
式（２１）を用いて、Ｋ（ｘ，ｙ）が０から１までの区間内の値をとると仮定すると、それ（すなわち、Ｋ（ｘ，ｙ））を
0004072209.tif 000079
と書くことができる。式（２５）を用いて、ノイマン数列（式（１８））は
0004072209.tif 000080
として再定式化される。式（２６）を式（１８）と比較すると、式（１８）の全てのｎ次積分に対して２ｎ次元積分が式（２６）に与えられており、かつ、ｘl（ｌ＝１，２，．．．）にわたる全ての積分に対して、ｘl′にわたる追加の積分が式（２６）に与えられていることがわかるであろう。
上の式（１７）の場合と同じように、「ｎ」は数列のインデックスを示し、「２Ｌ」は長さ「Ｎ」のシミュレーション中に必要な成分の最大数である食い違いの小さい多次元数列（ξl(n)，ξ′l(n)，ξ2(n)，ξ′2(n)，．．．，ξL(n)，ξ′L(n)）を用いて、「ｇ（ｘ）」は０番目の項とみなされる式（２６）中のノイマン数列の最初の「Ｌ」個の項の食い違いの小さい標本化を行うことにより、式（２６）を計算して数値近似を行う。「Ｌ」の値はコンピュータ・グラフィックス装置１０が前もって知っていたり、選択する必要はないこと、および食い違いの小さい数列の連続する成分ξ1(n)とξ′1(n)を必要に応じて発生できることが以下の説明から明らかであろう。一実施形態では、食い違いの小さい各「２Ｌ次元」の数列は上で説明したように、数列の要素は相互に最大限に避けようとする、たとえば２Ｌ次元のホールトン数列である。その数列の各要素に対して、推量値ｆRR(n)（ｘ）が
0004072209.tif 000081
として発生される。式（２７）では、表現式（式（１５））に関連して、和中の項「ｇ（ｘ）」は表現式の放出された輝度値項
0004072209.tif 000082
に相当すること、および、推量値の発生で用いられる多次元ホールトン数列の特定の要素に対する表現式中の積分
0004072209.tif 000083
の推量値が他の項から得られることがわかるであろう。
ヘビサイド関数（式（２２））の定義から、ある特定のレベル「１，」において、ξ′1(n)の値がＫ（ξl-1(n)，ξ1(n)）より大きいならば、その項、および式（２７）中の連続的に高い項では、対応するヘビサイド関数は零であることがわかるであろう。したがって、式（２７）におけるように、推量値ｆRR(n)（ｘ）を定式化することによって、無限ノイマン数列が自己切り捨ててあり、したがって有限数列になる。したがって、ｆ（ｘ）の近似を
0004072209.tif 000084
として得ることができる。この式は、表現式（式（１５））に関連して、
0004072209.tif 000085
の値、すなわち、画像中の点
0004072209.tif 000086
における向き
0004072209.tif 000087
の輝度値を与える。
上記のように、式（２１）から（２８）に関連して上で説明した方法は、Ｋ（ｘ，ｙ）が０から１までの数値区間内の値を取ると仮定している。Ｋ（ｘ，ｙ）がその区間内の値を取らないと、０から１までの数値区間内の値をとる関数ｐ（ｘ，ｙ）をとり、Ｋ（ｘ，ｙ）をＫ（ｘ，ｙ）を
0004072209.tif 000088
と書き、式（参照式（２５））を
0004072209.tif 000089
で置き換えることによってこの方法を一般化できる。その場合には、推量値ｆRR(n)（ｘ）（式（２７））は
0004072209.tif 000090
として発生される。
この背景で、厳密に決定論的なロシアルーレット法に従って、積分核
0004072209.tif 000091
と放出された輝度値項
0004072209.tif 000092
が、コンピュータ・グラフィックス装置１０により画像がシミュレートされている対象であるシーン中の点
0004072209.tif 000093
についての表現式（式（１５））に対して求められた後で、コンピュータ・グラフィックス装置１０は表現式の解の数値近似を発生する。その演算では、表現式（式（２８））中の
0004072209.tif 000094
についての近似の発生で使用すべき推量値ｆ(n)RR（ｘ）の数である、「Ｎ」の値が選択され、コンピュータ・グラフィックス装置１０は多次元ホールトン数列の「Ｎ」個の要素を発生する。そのような各要素に対して、コンピュータ・グラフィックス装置１０は式（２７）に従って推量値ｆ(n)RR（ｘ）を発生する。その演算では、コンピュータ・グラフィックス装置１０は式（２７）における和の連続する各項の値を発生し、その項が値０を持つと判定するまで、発生された値を以前に発生された値に加え合わせる。式（２７）中の和の項が０であるとコンピュータ・グラフィックス装置１０が判定すると、それはその特定の推量値ｆ(n)RR（ｘ）についての演算を終了させることができる。上記のようにして発生された多次元ホールトン数列の「Ｎ」個の要素の全てに対する推量値ｆ(n)RR（ｘ）をコンピュータ・グラフィックス装置１０が発生した後、コンピュータ・グラフィックス装置１０は、式（２８）に関連して示したように、表現式についての数値近似を推定量の平均として発生する。
全体照明をシミュレートするように画素値の発生に関連して上で説明した動作が図６に流れ図で示されている。その流れ図に示されている動作は上の説明から当業者には容易にわかるので、その図の流れ図はこの明細書では個々には説明しない。
式（１５）で上に述べた表現式の形と、それにおける種々の機能は、全体照明をシミュレートするために画素値の発生に関連して使用できる形態と機能の例であり、その他の積分の諸形態および諸機能は特に式（２７）において対応した変更を行うことで当業者には明らかであろうことがわかるであろう。たとえば、コンピュータ・グラフィックス装置１０が、たとえば、上の定式化において考えられているものとは異なる数の次元のための全体照明をシミュレートすると、またはそのシミュレーションを多数の色で行わなければならないと、あるいは、シーン内の表面が拡散、光沢があり、または鏡のようであると（いわゆる「局所照明モデル」を用いて）、または特定の表面で光線の反射または屈折を行うかについての判定を行うと、積分の特定の形態とそれにおける種々の機能は上で説明したものとは異なることがある。表現式およびそれにおける種々の機能の定式化が、ある特定の面で、ここで説明したものとは一般に異なることがあるが、そのために用いられる特定の表現式は上で式（１７）において説明したものに対応する形態を持つであろうから、コンピュータ・グラフィックス装置１０は、式を計算するために式（２７）と（２８）に関連して上で説明した厳密に決定論的なロシアルーレット法を使用できる。
式（２７）に関連して上で説明したように、各「ｘ」についての推量値ｆ(n)RR（ｘ）の発生は食い違いの小さい多次元数列（ξ1(n)，ξ′1(n)，ξ2(n)，ξ′2(n)，．．．，ξL(n)，ξ′L(n)）を使用する。その数列の「′のつけられていない」成分ξ1(n)，．．．，ξL(n)は記号のない変数ｘｌ，ｘ２，．．．についての積分と関連し（参照式（２６））、その数列の「′のつけられている」成分ξ′1(n)，．．．，ξ′L(n)は「′のつけられている」変数ｘ′1，ｘ′2，．．．についての積分と関連している（参照式（２６））。ある状況では、推量値ｆ(n)RR（ｘ）の発生において「生の」′のつけられていない成分ξ1(n)，．．．，ξL(n)の代わりに、推量値ｆ(n)RR（ｘ）の発生において関数Ｋ（ｘ，ｙ）中の諸特徴が計算において効率的に捕らえられるようにするために選択できる、数列の選択された機能または変換を使用することが望ましいことがあることを当業者は分かるであろう。しかし、′のつけられていない成分ξ1(n)，．．．ξL(n)が用いられるとしても、「生の」′のつけられている成分ξ′1(n)，．．．，ξ′L(n)が推量値ｆ(n)RR（ｘ）の発生に使用されるようにすることが一般に望ましい。
また、計算のための標本点を得るために用いられているものとしてホールトン数列が示されているが、この技術で知られている、食い違いの小さい他の数列を代わりに使用できることがわかるであろう。
式（２１）から（２８）に関連して上で説明したように、多次元ホールトン数列などの厳密に決定論的な、食い違いの小さい数列を用いる、厳密に決定論的なロシアルーレット法は、モンテ・カルロ・ロシアルーレット法（すなわち、乱数を用いるロシアルーレット法）、ならびに式（１８）から（２０）に関連して上で説明した非ロシアルーレット法の両者に対していくつかの利点を有する。他のいかなるモンテ・カルロ法の場合と同様にモンテ・カルロ・ロシアルーレット法に関して、そのような方法は乱数を使用し、したがって、上記のような類似の諸欠点を持つ。すなわち、厳密に決定論的なロシアルーレット法とは異なって、それの厳密に決定論的な食い違いの小さい数列はモンテ・カルロ・ロシアルーレット法で用いられる乱数から起きることがあるかたまりと比較して、推量値を食い違いが小さいやり方で計算すべき領域である多次元領域にわたって標本点がほぼ一様に分布することを先験的に確実にする。したがって、厳密に決定論的なロシアルーレット法は、近似
0004072209.tif 000095
の満足できる値を得るために、モンテ・カルロ・ロシアルーレット法と比較して必要とする推定量が少ない。
また、厳密に決定論的なロシアルーレット法とは異なって、非ロシアルーレット法（式（１８）から（２０））に対しては、各推量値ｆ(n)（ｘ）（式（１９））を発生するために用いられるノイマン数列が無限数列であることが一般にあてはまる。したがって、そのような数列のおのおのは所定の最大数の項で切り捨てる必要があり、この結果画像中の諸特徴が失われることがある。式（２７）および（２８）に関連して上で説明したように、厳密に決定論的なロシアルーレット法では、各推量値ｆ(n)RR（ｘ）に対して、特定のレベル「１，」において、そのレベルおよびそれの後の任意のレベルに対する推量値の項（式（２７））の値は零であることが保証され、したがってその数列は有限数列である。いいかえると、厳密に決定論的なロシアルーレット法では、数列（式（２７）は自己切り捨てであることが保証され、一方、厳密に決定論的な非ロシアルーレット法では、数列（式（１９）は一般に自己切り捨てではなく、その代わりにコンピュータ・グラフィックス装置１０にその数列を切り捨てるよう一般に要求する。したがって、厳密に決定論的な非ロシアルーレット法とは異なって、厳密に決定論的なロシアルーレット法は画像の諸特徴が失われないようにする。
また、一般に、推量値ｆ(n)（ｘ）に関連して用いられるノイマン数列などの有限数列では、その数列の初めのいくつかの項が推量値ｆ(n)（ｘ）の結果としての値へ主に寄与する。自己切り捨て特性のために、厳密に決定論的なロシアルーレット法は、少なくとも、ノイマン数列の初めのいくつかの項（それらは最も重要な項である）が、ノイマン数列の以後の項（それらは一般に重要度が低い）よりもはるかにしばしば推量値ｆ(n)（ｘ）において考慮される、という理由で厳密に決定論的な非ロシアルーレット法（式（１８）から（２０）に関連して上で説明した）を改良する。したがって、厳密に決定論的なロシアルーレット法は近似
0004072209.tif 000096
の満足できる値を得るために、非ロシアルーレット法と比較してより少ない推量値を必要とする。
さらに、厳密に決定論的なロシアルーレット法では、各推量値ｆ(n)RR（ｘ）の数列は自己切り捨てであるために、その方法は全体照明のシミュレーションにおいて光路を終わらせるかどうかを自動的に決定できるようにする。式（１８）と（２６）において、各対（ｘ，ｘ1）、（ｘ1，ｘ2）、．．．（ｘi，ｘj）は空間内で点「ｘj」から点「ｘi」まで（右から左へと読む）延びているそれぞれの光路を表し、各推量値において、各項は全体照明のシミュレーションへの光線の寄与を表している。厳密に決定論的なロシアルーレット法では、各推量値ｆ(n)RR（ｘ）を発生するために用いられる数列は、項が零であるような対（ｘi，ｘj）に対して自動的に切り捨てるので、光路（ｘ，ｘ1）、（ｘ1，ｘ2）、．．．，（ｘi，ｘj）は自動的に終了する。他方、上記のように、厳密に決定論的な非ロシアルーレット法は自動的に終了せず、光路は自動的に終了しないが、その代わりに数列が任意に切り捨てられるような項に関連する点で終了させられる。
上記のように、対（ｘ，ｘ1）、（ｘ1，ｘ2）、．．．（ｘi，ｘj）は空間内で点「ｘj」から点「ｘi」まで延びているそれぞれの光路を表す。式（２１）から（２８）に関連して上で説明した厳密に決定論的なロシアルーレット法では、光路は光源から延びるものと仮定されている。たとえばカメラから延びる光路に関連して有用な類似の方法は当業者には明らかであろう。
本発明のシステムは専用のハードウェアまたは汎用のコンピュータ装置、あるいは、それらの任意の組合わせから全体としてまたは部分的に構成でき、それの任意の部分を適切なプログラムで制御できることがわかるであろう。どのようなプログラムも全体としてまたは部分的に、従来の方法で、システムの一部を構成し、またはシステムに内蔵され、またはそれは全体としてまたは部分的に、ネットワークまたは情報を従来の方法で転送するための他の機構を通じてシステムに提供できる。また、このシステムは、システムに直接接続でき、またはネットワークまたは情報を従来の方法で転送するための他の機構を通じて情報をシステムへ転送できるオペレータ入力要素（図示せず）を用いてオペレータにより供給される情報によって、動作および／または制御されることがわかるであろう。
以上の説明は本発明の特定の実施形態に限定されたものである。しかし、本発明の利点のいくつかは、本発明の全てまたはある利点を達成して種々の変更および修正を本発明に対して行うことができることが明らかであろう。発明の要旨および範囲内に入るものとしてそれらの他の変更および修正を包含することが添付の請求の範囲の目的である。
新規であるとして請求され、かつ特許証により権利を保証されることを希望するものは：
【図１】
0004072209.tif 000134
【図２】
0004072209.tif 000135
【図３】
0004072209.tif 000136
【図４】
0004072209.tif 000137
【図５】
0004072209.tif 000138
【図５Ａ】
0004072209.tif 000139
【図６】
0004072209.tif 000140
【図６Ａ】
0004072209.tif 000141
【図６Ｂ】
0004072209.tif 000142