US2005278406A1PendingUtilityA1
System and computer-implemented method for evaluating integrals using stratification by rank-1 lattices
Est. expiryMay 15, 2022(expired)· nominal 20-yr term from priority
Inventors:Alexander Keller
G06F 17/10
45
PatentIndex Score
0
Cited by
0
References
0
Claims
Abstract
A system for numerically evaluating an integral of a function over an s-dimensional integration domain is described, the system comprising a sample point generator, a function value generator and an integral value estimate generator. The sample point generator is configured to generate a selected number of sample points over the integration domain, the sample points being generated such that there is at least one sample point in each of a plurality of strata distributed over the integration domain, the strata being defined by a rank-I lattice. The function value generator is configured to, for respective ones of the sample points, generate a value for the function at the respective sample point. The integral value estimate generator is configured to use the function values generated by the function value generator at the respective sample points in generating an estimate for the value of the integral. The system finds utility in a number of areas, including computer graphics.
Claims
exact text as granted — not AI-modified1 . A system for numerically evaluating an integral of a function over an s-dimensional integration domain comprising:
A. a sample point generator configured to generate a selected number of sample points over the integration domain, the sample points being generated such that there is at least one sample point in each of a plurality of strata distributed over the integration domain, the strata being defined by a rank-1 lattice; B. a function value generator configured to, for respective ones of the sample points, generate a value for the function at the respective sample point; and C. an integral value estimate generator configured to use the function values generated by the function value generator at the respective sample points in generating an estimate for the value of the integral:
2 . A system as defined in claim 1 in which the integration domain comprises the “s”-dimensional unit cube [0,1) s .
3 . A system as defined in claim 2 in which, for each stratum A j , the sample point generator is configured to generate the “j-th” sample point R j (x) in accordance with the bijection
R
j
:
[
0
,
1
)
s
->
A
j
x
↦
(
j
n
·
g
+
B
x
)
mod
[
0
,
1
)
s
where “n” is the selected number of sample points, g is a generator vector for the rank-1 lattice, and B is a matrix that defines a linear transformation that represents a rotation and/or shear.
4 . A system as defined in claim 3 in which the sample point generator is configured to generate the “j-th” sample point such that “x” is a vector.
5 . A system as defined in claim 4 in which the sample point generator is configured to generate the “j-th” sample point such that the vector “x” is the same for all sample points.
6 . A system as defined in claim 4 in which, for each value of index “j ,” the sample point generator is configured to generate the “j-th” sample point such that the vector “x” is the “j-th” element of a sequence of vectors P n =(ξ 0 , . . . ,ξ n-1 ).
7 . A system as defined in claim 6 in which the elements of the sequence are generated using a random sequence generation methodology.
8 . A system as defined in claim 6 in which at least one vector in the sequence is an “s”-dimensional vector.
9 . A system as defined in claim 2 in which the sample point generator is configured to generate the “j-th” sample point such that the “s-”dimensional unit cube [0,1) s comprises an “s 1 ”-dimensional portion and an “s 2 ”-dimensional portion, where each sample point is defined by (ξ i ,R j (ζ i )), where ξ i is an element of an “s 1 ”-dimensional sequence, ζ i is an element of an “s 2 ”-dimensional sequence, and R j is defined by the bijection
R
j
:
[
0
,
1
)
s
2
->
A
j
x
↦
(
j
n
·
g
+
B
x
)
mod
[
0
,
1
)
s
2
where “n” is the selected number of sample points, g is a generator vector for the rank-1 lattice, and B is a matrix that defines a linear transformation that represents a rotation and/or shear.
10 . A system as defined in claim 9 in which the sample point generator is configured to generate the “j-th” sample point such that the elements of the “s 1 ”-dimensional sequence are generated using a random sequence generation methodology.
11 . A system as defined in claim 9 in which the sample point generator is configured to generate the “j-th” sample point such that the elements of the “s 2 ”-dimensional sequence are generated using a random sequence generation methodology.
12 . A computer implemented method of numerically evaluating an integral of a function over an s-dimensional integration domain comprising:
A. a sample point generation step of generating a selected number of sample points over the integration domain, the sample points being generated such that there is at least one sample point in each of a plurality of strata distributed over the integration domain, the strata being defined by a rank-1 lattice; B. a function value generation step of, for respective ones of the sample points, generating a value for the function at the respective sample point; and C. an integral value estimate generation step of using the function values generated during the function value generation step at the respective sample points in generating an estimate for the value of the integral.
13 . A method as defined in claim 12 in which the integration domain comprises the “s”-dimensional unit cube [0,1) s .
14 . A method as defined in claim 13 in which, for each stratum A j , the sample point generation step includes the step of generating the “j-th” sample point R j (x) in accordance with the bijection
R
j
:
[
0
,
1
)
s
->
A
j
x
↦
(
j
n
·
g
+
Bx
)
mod
[
0
,
1
)
s
where “n” is the selected number of sample points, g is a generator vector for the rank-1 lattice, and B is a matrix that defines a linear transformation that represents a rotation and/or shear.
15 . A method as defined in claim 14 in which the sample point generation step includes the step of generating the “j-th” sample point such that “x” is a vector.
16 . A method as defined in claim 15 in which the sample point generation step includes the step of generating the “j-th” sample point such that the vector “x” is the same for all sample points.
17 . A method as defined in claim 15 in which, for each value of index “j,” the sample point generation step includes the step of generating the “j-th” sample point such that the vector “x” is the “j-th” element of a sequence of vectors P n =(ξ 0 , . . . ,ξ n-1 ).
18 . A method as defined in claim 17 in which the sample point generation step includes the step of generating the elements of the sequence using a random sequence generation methodology.
19 . A method as defined in claim 17 in which at least one vector in the sequence is an “s”-dimensional vector.
20 . A method as defined in claim 13 in which the sample point generation step includes the step of generating the “j-th” sample point such that the “s-”dimensional unit cube [0,1) s comprises an “s 1 ”-dimensional portion and an “s 2 ”-dimensional portion, where each sample point is defined by (ξ i ,R j (ζ i )),where ξ i is an element of an “s 1 ”-dimensional sequence, ζ i is an element of an “s 2 ”-dimensional sequence, and R j is defined by the bijection
R
j
:
[
0
,
1
)
s
2
->
A
j
x
↦
(
j
n
·
g
+
Bx
)
mod
[
0
,
1
)
s
2
where “n” is the selected number of sample points, g is a generator vector for the rank-1 lattice, and B is a matrix that defines a linear transformation that represents a rotation and/or shear.
21 . A method as defined in claim 20 in which the sample point generation step includes the step of generating the “j-th” sample point such that the elements of the “s 1 ”-dimensional sequence are generated using a random sequence generation methodology.
22 . A method as defined in claim 20 in which the sample point generation step includes the step of generating the “j-th” sample point such that the elements of the “s 2 ”-dimensional sequence are generated using a random sequence generation methodology.
23 . A computer program product for use with a computer to provide a system for numerically evaluating an integral of a function over an s-dimensional integration domain, the computer program product comprising a computer readable medium having encoded thereon:
A. a sample point generator module configured to enable the computer to generate a selected number of sample points over the integration domain, the sample points being generated such that there is at least one sample point in each of a plurality of strata distributed over the integration domain, the strata being defined by a rank-1 lattice; B. a function value generator module configured to enable the computer to, for respective ones of the sample points, generate a value for the function at the respective sample point; and C. an integral value estimate generator module configured to enable the computer to use the function values generated by the function value generator at the respective sample points in generating an estimate for the value of the integral.
24 . A computer program product as defined in claim 23 in which the integration domain comprises the “s”-dimensional unit cube [0,1) s .
25 . A computer program product as defined in claim 24 in which, for each stratum A j , the sample point generator module is configured to enable the computer to generate the “j-th” sample point R j (x) in accordance with the bijection
R
j
:
[
0
,
1
)
s
->
A
j
x
↦
(
j
n
·
g
+
Bx
)
mod
[
0
,
1
)
s
where “n” is the selected number of sample points, g is a generator vector for the rank-1 lattice, and B is a matrix that defines a linear transformation that represents a rotation and/or shear.
26 . A computer program product as defined in claim 25 in which the sample point generator module is configured to enable the computer to generate the “j-th” sample point such that “x” is a vector.
27 . A computer program product as defined in claim 26 in which the sample point generator module is configured to enable the computer to generate the “j-th” sample point such that the vector “x” is the same for all sample points.
28 . A computer program product as defined in claim 26 in which, for each value of index “j,” the sample point generator module is configured to enable the computer to generate the “j-th” sample point such that the vector “x” is the “j-th” element of a sequence of vectors P n =(ξ 0 , . . . ,ξ n- 1 ).
29 . A computer program product as defined in claim 28 in which the elements of the sequence are generated using a random sequence generation methodology.
30 . A computer program product as defined in claim 28 in which at least one vector in the sequence is an “s”-dimensional vector.
31 . A computer program product as defined in claim 24 in which the sample point generator module is configured to enable the computer to generate the “j-th” sample point such that the “s-”dimensional unit cube [0,1) s comprises an “s 1 ”-dimensional portion and an “s 2 ”-dimensional portion, where each sample point is defined by (ξ i ,R j (ζ i )), where ξ i is an element of an “s”-dimensional sequence, ζ i is an element of an “s 2 ”-dimensional sequence, and R j is defined by the bijection
R
j
:
[
0
,
1
)
s
2
->
A
j
x
↦
(
j
n
·
g
+
Bx
)
mod
[
0
,
1
)
s
2
where “n” is the selected number of sample points, g is a generator vector for the rank-1 lattice, and B is a matrix that defines a linear transformation that represents a rotation and/or shear.
32 . A computer program product as defined in claim 31 in which the sample point generator module is configured to enable the computer to generate the “j-th” sample point such that the elements of the “s 1 ”-dimensional sequence are generated using a random sequence generation methodology.
33 . A computer program product as defined in claim 31 in which the sample point generator module is configured to enable the computer to generate the “j-th” sample point such that the elements of the “s 2 ”-dimensional sequence are generated using a random sequence generation methodology.
34 . A computer graphics system for generating a pixel value for a pixel in an image, the pixel being representative of a point in a scene, the scene comprising at least one object and at least one light source, the computer graphics system generating the pixel value by an evaluation of an integral of a selected function over an s-dimensional integration domain comprising:
A. a sample point generator configured to generate a selected number of sample points over the integration domain, the sample points being generated such that there is at least one sample point in each of a plurality of strata distributed over the integration domain, the strata being defined by a rank-1 lattice; B. a function value generator configured to, for respective ones of the sample points, generate a value for the function at the respective sample point; and C. an integral value estimate generator configured to use the function values generated by the function value generator at the respective sample points in generating an estimate for the value of the integral in relation to the at least one object and at least one light source, the estimate corresponding to the pixel value for the image.
35 . A system as defined in claim 34 in which the integration domain comprises the “s”-dimensional unit cube [0,1) s and for each stratum A j , the sample point generator is configured to generate the “j-th” sample point R j (x) in accordance with the bijection
R
j
:
[
0
,
1
)
s
->
A
j
x
↦
(
j
n
·
g
+
Bx
)
mod
[
0
,
1
)
s
where “n” is the selected number of sample points, g is a generator vector for the rank-1 lattice, and B is a matrix that defines a linear transformation that represents a rotation and/or shear.
36 . A system as defined in claim 35 in which the sample point generator is configured to use the same vector “x” for at least some of the sample points.
37 . A system as defined in claim 36 in which at least part of the selected function represents a path tracing methodology in which the function value generator is configured to generate the function value associated with a point in the scene in relation to a plurality of simulated traces projected from the point, the directions of the traces being determined by strata defined on at least a portion of a sphere centered on the point induced by at least a portion of the rank-1 lattice.
38 . A system as defined in claim 35 in which, for each value of index “j,” the sample point generator is configured to generate the “j-th” sample point such that the vector “x” is the “j-th” element of a sequence of vectors P n =(ξ 0 , . . . ,ξ n-1 ).
39 . A system as defined in claim 38 in which the elements of the sequence are generated using a random sequence generation methodology.
40 . A system as defined in claim 39 in which at least part of the selected function represents a photon map methodology in which the function value generator is configured to generate the function values by using sample points generated by the sample point generator module using least some of the vectors from the sequence to control a random walk of traces from the light source through at least a portion of the scene.
41 . A system as defined in claim 35 in which the sample point generator is configured to generate the “j-th” sample point such that the “s-” dimensional unit cube [0,1) s comprises an “s 1 ”-dimensional portion and an “s 2 ”-dimensional portion, where each sample point is defined by (ξ i ,R j (ζ i )), where ξ i is an element of an “s 1 ”-dimensional sequence, ζ i is an element of an “s 2 ”-dimensional sequence, and R j is defined by the bijection
R
j
:
[
0
,
1
)
s
2
->
A
j
x
↦
(
j
n
·
g
+
Bx
)
mod
[
0
,
1
)
s
2
where “n” is the selected number of sample points, g is a generator vector for the rank-1 lattice, and B is a matrix that defines a linear transformation that represents a rotation and/or shear.
42 . A system as defined in claim 41 in which the sample point generator is configured to generate the “j-th” sample point such that the elements of the “s 1 ”-dimensional sequence are generated using a random sequence generation methodology.
43 . A system as defined in claim 41 in which the sample point generator is configured to generate the “j-th” sample point such that the elements of the “s 2 ”-dimensional sequence are generated using a random sequence generation methodology.
44 . A system as defined in claim 41 in which at least part of the selected function represents a shadow ray methodology, in which a plurality of shadow rays comprising simulated traces are traced from a point in the scene towards respective points on the light source, the locations of the points on the light source being determined by R j , the function value generator being configured to generate the function value in relation to whether respective ones of the shadow rays intersect at least one of said objects in the scene.
45 . A system as defined in claim 41 in which at least a part of the selected function represents a distribution path tracing methodology, in which the function value generator is configured to generate the function value associated with a point in the scene in relation to a plurality of simulated traces projected from the point, the directions of the traces being determined by strata defined on at least a portion of a sphere centered on the point induced by R j .
47 . A computer implemented method of generating a pixel value for a pixel in an image, the pixel being representative of a point in a scene, the scene comprising at least one object and at least one light source, the computer graphics method generating the pixel value by an evaluation of an integral of a selected function over an s-dimensional integration domain, the computer graphics method comprising:
A. a sample point generation step of generating a selected number of sample points over the integration domain, the sample points being generated such that there is at least one sample point in each of a plurality of strata distributed over the integration domain, the strata being defined by a rank-1 lattice; B. a function value generation step of, for respective ones of the sample points, generating a value for the function at the respective sample point; and C. an integral value estimate generation step of using the function values generated during the function value generation step at the respective sample points in generating an estimate for the value of the integral in relation to the at least one object and at least one light source, the estimate corresponding to the pixel value for the image.
48 . A method as defined in claim 47 in which the integration domain comprises the “s”-dimensional unit cube [0,1) s and for each stratum A j , the sample point generation step including the step of generating the “j-th” sample point R j (x) in accordance with the bijection
R
j
:
[
0
,
1
)
s
->
A
j
x
↦
(
j
n
·
g
+
Bx
)
mod
[
0
,
1
)
s
where “n” is the selected number of sample points, g is a generator vector for the rank-1 lattice, and B is a matrix that defines a linear transformation that represents a rotation and/or shear.
49 . A method as defined in claim 48 in which the sample point generation step includes the step of using the same vector “x” for at least some of the sample points.
50 . A method as defined in claim 49 in which at least part of the selected function represents a path tracing methodology in which the function value generation step includes the step of generating the function value associated with a point in the scene in relation to a plurality of simulated traces projected from the point, the directions of the traces being determined by strata defined on at least a portion of a sphere centered on the point induced by at least a portion of the rank-1 lattice.
51 . A method as defined in claim 48 in which, for each value of index “j,” the sample point generation step includes the step of generating the “j-th” sample point such that the vector “x” is the “j-th” element of a sequence of vectors P n =(ξ 0 , . . .ξ n-1 ).
52 . A method as defined in claim 51 in which the sample point generation step includes the step of generating the elements of the sequence using a random sequence generation methodology.
53 . A method as defined in claim 52 in which at least part of the selected function represents a photon map methodology in which the function value generation step includes the step of generating the function values by using sample points generated during the sample point generation step using least some of the vectors from the sequence to control a random walk of traces from the light source through at least a portion of the scene.
54 . A method as defined in claim 48 in which the sample point generation step includes the step of generating the “j-th” sample point such that the “s-”dimensional unit cube [0,1) s comprises an “s 1 ”-dimensional portion and an “s 2 ”-dimensional portion, where each sample point is defined by (ξ i ,R j (ζ i )), where ζ i is an element of an “s 1 ”-dimensional sequence, ζ i is an element of an ”s 2 ”-dimensional sequence, and R j is defined by the bijection
R
j
:
[
0
,
1
)
s
2
->
A
j
x
↦
(
j
n
·
g
+
Bx
)
mod
[
0
,
1
)
s
2
where “n” is the selected number of sample points, g is a generator vector for the rank-1 lattice, and B is a matrix that defines a linear transformation that represents a rotation and/or shear.
55 . A method as defined in claim 54 in which the sample point generation step includes the step of generating the “j-th” sample point such that the elements of the “s 1 ”-dimensional sequence are generated using a random sequence generation methodology.
56 . A method as defined in claim 54 in which the sample point generation step includes the step of generating the “j-th” sample point such that the elements of the “s 2 ”-dimensional sequence are generated using a random sequence generation methodology.
57 . A method as defined in claim 54 in which at least part of the selected function represents a shadow ray methodology, in which a plurality of shadow rays comprising simulated traces are traced from a point in the scene towards respective points on the light source, the locations of the points on the light source being determined by R j , the function value generation step including the step of generating the function value in relation to whether respective ones of the shadow rays intersect at least one of said objects in the scene.
58 . A method as defined in claim 54 in which at least a part of the selected function represents a distribution path tracing methodology, in which the function value generation step includes the step of generating the function value associated with a point in the scene in relation to a plurality of simulated traces projected from the point, the directions of the traces being determined by strata defined on at least a portion of a sphere centered on the point induced by R j .
59 . A computer program product for use in connection with a computer to provide a computer graphics system for generating a pixel value for a pixel in an image, the pixel being representative of a point in a scene, the scene comprising at least one object and at least one light source, the computer graphics system generating the pixel value by an evaluation of an integral of a selected function over an s-dimensional integration domain, the computer program product comprising a computer-readable medium having encoded hereon:
A. a sample point generator module configured to enable the computer to generate a selected number of sample points over the integration domain, the sample points being generated such that there is at least one sample point in each of a plurality of strata distributed over the integration domain, the strata being defined by a rank-1 lattice; B. a function value generator module configured to enable the computer to, for respective ones of the sample points, generate a value for the function at the respective sample point; and C. an integral value estimate generator module configured to enable the computer to use the function values generated by the function value generator at the respective sample points in generating an estimate for the value of the integral in relation to the at least one object and at least one light source, the estimate corresponding to the pixel value for the image.
60 . A computer program product as defined in claim 59 in which the integration domain comprises the “s”-dimensional unit cube [0,1) s and for each stratum A j , the sample point generator module is configured to enable the computer to generate the “j-th” sample point R j (x) in accordance with the bijection
R
j
:
[
0
,
1
)
s
->
A
j
x
↦
(
j
n
·
g
+
Bx
)
mod
[
0
,
1
)
s
where “n” is the selected number of sample points, g is a generator vector for the rank-1 lattice, and B is a matrix that defines a linear transformation that represents a rotation and/or shear.
61 . A computer program product as defined in claim 60 in which the sample point generator module is configured to enable the computer to use the same vector “x” for at least some of the sample points.
62 . A computer program product as defined in claim 61 in which at least part of the selected function represents a path tracing methodology in which the function value generator module is configured to enable the computer to generate the function value associated with a point in the scene in relation to a plurality of simulated traces projected from the point, the directions of the traces being determined by strata defined on at least a portion of a sphere centered on the point induced by at least a portion of the rank-1 lattice.
63 . A computer program product as defined in claim 60 in which, for each value of index “j,” the sample point generator module is configured to enable the computer to generate the “j-th” sample point such that the vector “x” is the “j-th” element of a sequence of vectors P n =(ξ ) , . . . ,ξ n-1 ).
64 . A computer program product as defined in claim 63 in which the elements of the sequence are generated using a random sequence generation methodology.
65 . A computer program product as defined in claim 64 in which at least part of the selected function represents a photon map methodology in which the function value generator module is configured to enable the computer to generate the function values by using sample points generated by the sample point generator module using least some of the vectors from the sequence to control a random walk of traces from the light source through at least a portion of the scene.
66 . A computer program product as defined in claim 60 in which the sample point generator module is configured to enable the computer to generate the “j-th” sample point such that the “s-”dimensional unit cube [0,1) s comprises an “s 1 ”-dimensional portion and an “s 2 ”-dimensional portion, where each sample point is defined by (ξ i ,R j (ζ i )), where ζ i is an element of an “s 1 ”-dimensional sequence, ζ i is an element of an “s 2 ”-dimensional sequence, and R j is defined by the bijection
R
j
:
[
0
,
1
)
s
2
->
A
j
x
↦
(
j
n
·
g
+
Bx
)
mod
[
0
,
1
)
s
2
where “n” is the selected number of sample points, g is a generator vector for the rank-1 lattice, and B is a matrix that defines a linear transformation that represents a rotation and/or shear.
67 . A computer program product as defined in claim 66 in which the sample point generator module is configured to enable the computer to generate the “j-th” sample point such that the elements of the “s 1 ”-dimensional sequence are generated using a random sequence generation methodology.
68 . A computer program product as defined in claim 66 in which the sample point generator module is configured to enable the computer to generate the “j-th” sample point such that the elements of the “s 2 ”-dimensional sequence are generated using a random sequence generation methodology.
69 . A computer program product as defined in claim 66 in which at least part of the selected function represents a shadow ray methodology, in which a plurality of shadow rays comprising simulated traces are traced from a point in the scene towards respective points on the light source, the locations of the points on the light source being determined by R j , the function value generator being configured to generate the function value in relation to whether respective ones of the shadow rays intersect at least one of said objects in the scene.
70 . A computer program product as defined in claim 66 in which at least a part of the selected function represents a distribution path tracing methodology, in which the function value generator module is configured to enable the computer to generate the function value associated with a point in the scene in relation to a plurality of simulated traces projected from the point, the directions of the traces being determined by strata defined on at least a portion of a sphere centered on the point induced by R j .Cited by (0)
No later patents cite this yet.
References (0)
No backward citations on record.