[go: up one dir, main page]

US20050278406A1 - System and computer-implemented method for evaluating integrals using stratification by rank-1 lattices - Google Patents

System and computer-implemented method for evaluating integrals using stratification by rank-1 lattices Download PDF

Info

Publication number
US20050278406A1
US20050278406A1 US10/439,311 US43931103A US2005278406A1 US 20050278406 A1 US20050278406 A1 US 20050278406A1 US 43931103 A US43931103 A US 43931103A US 2005278406 A1 US2005278406 A1 US 2005278406A1
Authority
US
United States
Prior art keywords
sample point
sample
dimensional
point
generator
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Abandoned
Application number
US10/439,311
Other languages
English (en)
Inventor
Alexander Keller
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Nvidia ARC GmbH
Original Assignee
Mental Images GmbH
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Mental Images GmbH filed Critical Mental Images GmbH
Priority to US10/439,311 priority Critical patent/US20050278406A1/en
Publication of US20050278406A1 publication Critical patent/US20050278406A1/en
Assigned to MENTAL IMAGES GMBH reassignment MENTAL IMAGES GMBH MERGER (SEE DOCUMENT FOR DETAILS). Assignors: MENTAL IMAGES G.M.B.H. & CO. KG
Priority to US11/474,091 priority patent/US7589729B2/en
Priority to US11/688,698 priority patent/US7516170B2/en
Assigned to MENTAL IMAGES GMBH reassignment MENTAL IMAGES GMBH ASSIGNMENT OF ASSIGNORS INTEREST (SEE DOCUMENT FOR DETAILS). Assignors: KELLER, ALEXANDER
Priority to US12/416,236 priority patent/US8259106B2/en
Abandoned legal-status Critical Current

Links

Images

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/10—Complex mathematical operations

Definitions

  • the invention relates generally to the field of systems and computer-implemented methods for evaluating integrals, and more particularly to such systems and computer-implemented methods that evaluate integrals using Monte Carlo and quasi-Monte Carlo methodologies.
  • the invention particularly provides a new and improved system and computer-implemented method for evaluating integrals using a Monte Carlo methodology in which the integration domain is stratified using a stratification methodology in which the number of strata is independent of the number of dimensions in the integration domain.
  • the invention provides a methodology that makes use of stratification based on rank-1 lattices.
  • Systems and computer-implemented methods according to the invention find utility in a number of applications, including but not limited to computer graphics.
  • a computer is used to generate digital data that represents the projection of surfaces of objects in, for example, a three-dimensional scene, illuminated by one or more light sources, onto a two-dimensional image plane, to simulate the recording of the image by, for example, a camera.
  • the simulated camera may include a lens for projecting the image of the scene onto the image plane, or it may comprise a pinhole camera in which case no lens is used.
  • the two-dimensional image is in the form of an array of picture elements (which are variably referred to as “pixels” or “pels”), and the digital data generated for each pixel represents the color and luminance of the scene as projected onto the image plane at the point of the respective pixel in the image plane.
  • the surfaces of the objects may have any of a number of characteristics, including shape, color, specularity, texture, and so forth, which are preferably rendered in the image as closely as possible, to provide a realistic-looking image.
  • the contributions of the light reflected from the various points in the scene to the pixel value representing the color and intensity of a particular pixel are expressed in the form of the one or more integrals of relatively complicated functions. Since the integrals used in computer graphics generally do not have a closed-form solution, numerical methods must be used to evaluate them to generate the pixel value. Typically, a methodology referred to as the “Monte Carlo” method has been used in computer graphics to numerically evaluate the integrals.
  • the random points ⁇ i are used as sample points for which sample values f( ⁇ i ) are generated for the function f(x).
  • the value of the estimate ⁇ overscore ( ⁇ ) ⁇ will converge toward the actual value of the integral ⁇ >.
  • One strategy which is described in the aforementioned Grabenstein patent application, is to use a low-discrepancy, strictly deterministic point methodology to generate the set of sample points that will be used in generating the sample values f( ⁇ i ) for the estimate.
  • a low-discrepancy, strictly deterministic methodology will ensure that the sample points are distributed throughout the integration domain [0,) s without clumping in particular regions, which can occur if the sample points are randomly distributed.
  • Stratifying the integration domain [0,1) s can also be helpful in ensuring that sample points are reasonably well distributed throughout the integration domain [0,1) s , and that they do not clump in the integration domain, which can occur if the locations of the sample points ⁇ i are randomly located in the integration domain.
  • stratification strategies have been proposed.
  • previously-proposed stratification strategies particularly stratification strategies that are based on axis-aligned grids, suffer exponential growth in the number of strata with increasing numbers of dimensions comprising the integration domain.
  • integrands ⁇ that are used in fields such as, for example, computer graphics, often have very high-dimensional integration domains, stratifying domains using such stratification strategies can be computationally quite intensive.
  • the invention provides a new and improved system and computer-implemented method for evaluating integrals using a Monte Carlo methodology in which the integration domain is stratified using a stratification methodology in which the number of strata is independent of the number of dimensions in the integration domain. Specifically, the invention provides a methodology that makes use of stratification based on rank-1 lattices.
  • the invention provides a system for numerically evaluating an integral of a function over an s-dimensional integration domain, 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-1 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 invention provides a computer implemented method of numerically evaluating an integral of a function over an s-dimensional integration domain, the method comprising a sample point generation step, a function value generation step and an integral value estimate generation step.
  • a sample point generation step a selected number of sample points are generated 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.
  • the function value generation step for respective ones of the sample points, a value for the function at the respective sample point is generated.
  • the integral value estimate generation step the function values generated during the function value generation step at the respective sample points are used in generating an estimate for the value of the integral.
  • the invention provides 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 comprises a computer readable medium having encoded thereon a sample point generator module, a function value generator module and an integral value estimate generator module.
  • the sample point generator module is 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.
  • the function value generator module is configured to enable the computer to, for respective ones of the sample points, generate a value for the function at the respective sample point.
  • the integral value estimate generator module is 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.
  • FIG. 1 depicts an illustrative computer graphics system that evaluates integrals using a Monte Carlo methodology in which the integration domain is stratified using a stratification methodology in which the number of strata is independent of the number of dimensions in the integration domain;
  • FIG. 2 depicts a table of information that is useful in understanding the operation of the computer graphics system depicted in FIG. 1 .
  • the invention provides a computer graphics system and method for generating pixel values for pixels in an image of a simulated scene that makes use of a Monte Carlo methodology in which an integral or integrals is evaluated of function(s) by using sample points determined by stratifying the integration domain using rank-1 lattices.
  • the function(s) represent the contributions of the light that is emitted from simulated light sources and reflected from the various simulated surfaces in the scene directed towards a simulated camera, and the integral(s) provide the pixel values for the respective pixels in the image.
  • Stratifying the integration domain in this manner provides that the number of strata will not grow exponentially with the number of dimensions in the integration domain, which can occur with, for example, axis-aligned strata.
  • FIG. 1 attached hereto depicts an illustrative computer system 10 that makes use of such a stratification methodology.
  • the computer system 10 in one embodiment includes a processor module 11 and operator interface elements comprising operator input components such as a keyboard 12 A and/or a mouse 12 B (generally identified as operator input element(s) 12 ) and an operator output element such as a video display device 13 .
  • the illustrative computer system 10 is of the conventional stored-program computer architecture.
  • the processor module 11 includes, for example, one or more processor, memory and mass storage devices, such as disk and/or tape storage elements (not separately shown), which perform processing and storage operations in connection with digital data provided thereto.
  • the operator input element(s) 12 are provided to permit an operator to input information for processing.
  • the video display device 13 is provided to display output information generated by the processor module 11 on a screen 14 to the operator, including data that the operator may input for processing, information that the operator may input to control processing, as well as information generated during processing.
  • the processor module 11 generates information for display by the video display device 13 using a so-called “graphical user interface” (“GUI”), in which information for various applications programs is displayed using various “windows.”
  • GUI graphical user interface
  • the computer system 10 is shown as comprising particular components, such as the keyboard 12 A and mouse 12 B for receiving input information from an operator, and a video display device 13 for displaying output information to the operator, it will be appreciated that the computer system 10 may include a variety of components in addition to or instead of those depicted in FIG. 1 .
  • the processor module 11 includes one or more network ports, generally identified by reference numeral 14 , which are connected to communication links which connect the computer system 10 in a computer network.
  • the network ports enable the computer system 10 to transmit information to, and receive information from, other computer systems and other devices in the network.
  • certain computer systems in the network are designated as servers, which store data and programs (generally, “information”) for processing by the other, client computer systems, thereby to enable the client computer systems to conveniently share the information.
  • a client computer system which needs access to information maintained by a particular server will enable the server to download the information to it over the network. After processing the data, the client computer system may also return the processed data to the server for storage.
  • a network may also include, for example, printers and facsimile devices, digital audio or video storage and distribution devices, and the like, which may be shared among the various computer systems connected in the network.
  • the communication links interconnecting the computer systems in the network may, as is conventional, comprise any convenient information-carrying medium, including wires, optical fibers or other media for carrying signals among the computer systems.
  • Computer systems transfer information over the network by means of messages transferred over the communication links, with each message including information and an identifier identifying the device to receive the message.
  • the computer graphics system 10 generates an image that attempts to simulate an image of a three-dimensional scene as would be recorded by a camera. In that operation, for each pixel of the camera's image plane, the computer graphics system 10 numerically evaluates one or more integrals of functions that represent light that is directed toward the respective pixel from the scene. An illustrative function will be described below.
  • the functions typically contain a number of terms, including one or more terms that represent light that is directly incident on the respective pixel from one or more light source sources, as well as one or more terms that represent light that, after having been emitted by a light source, is reflected by one or more surfaces of objects in the scene and ultimately directed toward the pixel.
  • the computer graphics system 10 shoots, or traces, simulated rays from a plurality of points in the pixel into the scene. At points in the scene at which the shot rays intersect surfaces of objects in the scene, the computer graphics system determines the contributions of light that are directed from those intersection points in the scene toward the respective points in the pixel from which the rays were shot. The computer graphics system can determine the contributions that are directed to the respective points in the pixel in a number of ways.
  • the computer graphics system 10 determines the illumination at the point in the scene at which the ray shot from the pixel intersects an object in the scene by shooting one or more rays from the intersection point in a plurality of directions, and determining the extent to which that point is illuminated directly by light sources, and indirectly by light that is reflected off of other surfaces of objects in the scene. After the computer graphics system has determined the extent to which the intersection point is illuminated, the direction or directions from which the point is illuminated, and other information that will be known by those skilled in the art, it generates a value that represents the light reflected toward the point in the pixel from which the ray was shot.
  • the computer graphics system will repeat these operations for the various points in the pixel from which rays are shot, and will determine a pixel value for the entire pixel from the various values that are generated therefor.
  • the computer graphics system also repeats the operations for all of the pixels to generate the final image.
  • the computer graphics system also shoots rays from light source or sources into the scenes and determines the pixel values in relation to points in at which those rays intersect points on surfaces of objects in the scene.
  • the computer graphics system 10 prior to shooting rays from the pixels in the image plane into the scene, the computer graphics system 10 first generates a photon map representing photons that are incident on the surfaces of objects in the scene directly from the light sources and indirectly by photons that are reflected from various surfaces in the scene. After the computer graphics system has generated the photon map, it will shoot rays from the points on the pixels into the scene, and generate the pixel value in relation to the photons, if any, that are proximate the point of intersection of those rays with points on surfaces of the objects in the scene.
  • the computer graphics system 10 uses the coordinates of the sample points that are obtained from the integration domain of the integral to control various aspects regarding the geometry while generating the image. These aspects may include, for example, determining the locations of the points on the various pixels from which rays are shot, determining the locations on light sources from which rays representing photons are shot, determining directions of reflection, determining whether to terminate a ray at a surface or to allow the ray to be reflected, and other aspects as will be aware to those skilled in the art.
  • the operations performed by the computer graphics system in generating pixel values for an image comprise the numerical evaluation of an integral over an integration domain that is defined over an s-dimensional unit cube [0,1) s .
  • the strata A 4 are defined by an “s” dimensional lattice.
  • the lattice divides the integration domain into a plurality of strata A j of equal size, and the computer graphics system 10 obtains a sample point from each stratum A j for use in generating the approximation for the integral.
  • the dimension “s” is the number of basis vectors that, in linear combinations, yield the lattice points.
  • the lattice is referred to as a “rank-1” lattice, because it is generated using a single generator vector g.
  • rank-1 lattice is a lattice that is generated based on the Fibonacci sequence.
  • Fibonacci lattices of dimension “s” higher than “two” can be defined in a similar manner using an “s”-dimensional generator vector.
  • the generator vector g ( 1 , F k - 1 , F k - 1 2 , ... ⁇ , F k - 1 s - 1 ) can be used, which would provide a lattice in Korobov form.
  • the computer graphics system 10 obtains sample points from strata A j that are defined by the lattice.
  • the strata relate to unit cells that are associated with the respective vertices z j .
  • the unit cell of a rank-1 lattice is not uniquely specified, but a suitable unit cell, which is referred to as a Delaunay unit cell, can be specified such that the volume of an s-dimensional sphere that is inscribed in the unit cell is maximized.
  • the unit cells that result on the rank-1 lattice are all of similar shape and can be mapped from one to another by means of rigid body transformations that basically perform a translation and/or rotation to move them from vertex to vertex.
  • Each unit cell is identified by the Voronoi diagram of the rank-1 lattice, whose nerve is constructed out of the “s” shortest vectors v 1 , . . . , v s from the origin of the coordinate system defining the lattice, to points of the lattice, where the value of the first component of each vector v j (1) is greater than zero.
  • Equation (10) defines what can be referred to as a “reduced Cranley-Patterson rotation,” which determines the location of the “j-th” sample point at which the function ⁇ will be evaluated for the contribution to the estimate ⁇ overscore ( ⁇ ) ⁇ of the value of the integral.
  • the second term in the second line of equation (9), namely, B x, essentially provides a displacement from locations of the respective unrotated vertices to the particular sample point that will be used in evaluating the function.
  • the computer graphics system 10 may use the same value for “x” for some or all of the vertices (reference the discussion below regarding correlated sampling), or it may use different values (reference the discussion below regarding jittered sampling).
  • the particular parallelopiped that is defined by B will depend on the particular form of the generator vector g that is used to define the lattice, the number “n” of vertices that are to comprise the lattice, the number of dimensions, and other criteria as will be appreciated by those skilled in the art.
  • FIG. 2 depicts a table that, for two-dimensional Fibonacci lattices of various numbers “n” of vertices, gives the generator vector g and values of j 1 and j 2 for use in connection with equation (11).
  • the stratum that is associated with the vertex having coordinates (0,0) comprises the quadrilateral bounded by line segments between points (0,0), (1/2,0), (1/2,1/2) and (0,1/2), with the quadrilateral including the line segments between points (0,0)-(1/2,0) and (0,0)-(0,1/2) (except for points (1/2,0) and (0,1/2)), and not including the line segments between points (1/2,0)-(1/2,1/2) and (0,1/2)-(1/2,1/2), and
  • the stratum that is associated with the vertex having coordinates (1/2,1/2) comprises the quadrilateral bounded by line segments between points (1/2,1/2), (1,1/2), (1,1) and (1/2,1), with the quadrilateral including the line segments between points (1/2,1/2)-(1,1/2) and (1/2,1/2)-(1/2,1) (except for points (1,1/2) and (1/2,1)), and not including the line segments through points (1,0)-(1,1) and (0,1)-(1,1).
  • the strata associated with the respective vertices essentially represent a rigid translation, and it is apparent that the stratum associated with the vertex having coordinates (1/2,1/2) has the same size and shape as the stratum associated with the vertex having coordinates (0,0). The particular location within each stratum at which the vertex of the rotated lattice will be determined by the value of “x” (reference the second line of equation (10)).
  • stratifying an “s”-dimensional domain using rank-1 lattices provides that the number of strata will not grow exponentially with the number of dimensions in the integration domain. This will be illustrated in connection with jittered sampling, correlating sampling and correlated trajectory sampling methodologies.
  • jittered sampling is achieved by placing the samples points used for evaluating the integrand ⁇ in random positions within respective strata.
  • the first line reflects the fact that the integral over
  • the computer graphics system 10 can readily partition the s-dimensional unit cube [0,1) s into a number “n” of strata, with the number “n” being independent of the number “s” of dimensions.
  • the estimator for the value of the integral which is described in equation (12), and particularly in the last line of that equation, is unbiased and can also be used in connection with generating estimates of the values of integrals of functions related to fields other than computer graphics.
  • correlated sampling also involves evaluating a sum of integrals of a function ⁇ over the s-dimensional unit cube.
  • one randomly generated element ⁇ is used in generating all of the sample points (equation (10)) that are used in evaluating the function ⁇ for use in the sum. This is derived from equation (12) by, with reference to the second line of equation (12), interchanging the finite sum and the integral.
  • the computer graphics system 10 will, for each value of “j,” make use of the generator vector g in generating the j n ⁇ g term of R j ( ⁇ ), and the same randomly-generated vector “ ⁇ ” as “x” in the Bx term of the sample point R j ( ⁇ ).
  • the computer graphics system 10 will separately evaluate the integral for each of the pixels in the image; and in that case the computer graphics system 10 may use the same element ⁇ for all of the integrals associated with the various pixels, or, alternatively, the computer graphics system 10 may use different random elements . . .
  • One advantage of using different elements for the various integrals is that that may result in the generation of noise in the image, which can obscure aliasing artifacts that might otherwise be present in an image.
  • the estimator (reference the second line of equation (13)) that is used for an integral can be realized by generating one random s-dimensional vector ⁇ ⁇ [0,1) s and replicating it using equation (10), that is, using the product of B and the random element ⁇ as an offset for each of the unrotated lattice vertices, which, as noted above, are defined j n ⁇ g .
  • the resulting correlated samples have a guaranteed minimum distance and good uniformity properties, if the generator vector g is suitably chosen.
  • Trajectory splitting can improve efficiency depending on the correlation of the integrand with respect to its lower dimensional projections. Trajectory splitting is used in a number of types of simulations, including but not limited to computer graphics. Trajectory splitting can be used in several ways in computer graphics, one of which will be described here and another below.
  • One use of trajectory splitting in connection with computer graphics is tracing multiple shadow rays to an light source that has a non-zero area.
  • the computer graphics system 10 traces a plurality of rays from respective points in the pixel into a simulated scene.
  • the computer graphics system 10 can trace one or more rays, which are referred to as shadow rays, from the point of intersection of the shot ray to various points on the area of the light source. If a shadow ray intersects another object in the scene, the point of intersection of the shot ray is in the other object's shadow for that shadow ray.
  • the light source is deemed to contribute to the direct illumination of the point in the scene for the pixel from which the ray was shot.
  • the shadow rays that are traced from the point of intersection to the light source are distributed over the surface of the light source, and so some of the shadow rays may intersect other objects in the scene, whereas others of the shadow rays may not.
  • the extent to which the point of intersection of the shot ray is illuminated by the light source is a function of the number of shadow rays from that point on the object that do not intersect other objects. Generally, if a scene contains multiple light sources, similar operations will be performed for each light source to determine the extent to which the point at which the ray that was shot from the pixel intersects the object, is illuminated by the various light sources.
  • a pixel also has an area, and the computer graphics system will typically shoot simulated rays into the scene from several points within the area of the pixel, and trace shadow rays from points at which they intersect the various objects.
  • the variance of the integrand with respect to the area of the pixel is less than the variance with respect to the area of the light source.
  • the samples (illustratively, the shadow rays) that are split off of one instance (illustratively, the ray that is traced from the pixel into the scene) do not need to be independent.
  • the function ⁇ in the integral is a function of both vector “x” and vector “y,” that is f(x,y), with vector “x” being associated with s 1 dimensions and vector “y” being associated with s 2 dimensions.
  • the portion of the integration domain that is associated with vector “x” is the s 1 -dimensional unit cube [0,1) s 1 and the portion of the integration domain that is associated with the vector “y” is the s 2 dimensional unit cube [0,1) 2 1 .
  • Equation (15) essentially reflects the fact that the rank-1 lattice, instead of being used to stratify the entire “s”-dimensional integration domain, can be used to stratify a subset s 2 ⁇ s of the dimensions comprising the integration domain.
  • the element ⁇ i is used to determine the location of a point within the pixel from which the simulated ray is to be shot into the scene.
  • R j ( ⁇ i ) (reference equation (10)) is used to determine the location on the area light source toward which a shadow ray will be traced from the point at which the ray shot from the pixel intersects an object in the scene.
  • the displacements in the respective strata on the light source towards which shadow rays will be shot will usually differ for the different rays that are shot in the scene from the respective pixel.
  • jittered sampling, correlated sampling and trajectory splitting methodologies as described above will be further described in connection with three particular applications that are used in connection with generating images in computer graphics, namely, generating photon maps, path tracing and distribution ray tracing.
  • the photon map methodology generally includes two phases, namely, a first “photon map generation” phase followed by a “gather” phase.
  • the computer graphics system 10 shoots rays that represent paths taken by simulated photons emitted by one or more simulated light sources into a simulated scene. Each rays is in the form of a random walk that is traced through at least a portion of the simulated scene.
  • the computer graphics system determines whether a ray intersects a surface of an object in the scene, and, if so, stores information relating to the photon associated with the ray in a database.
  • the information which may include, for example, the photon's color, its direction of incidence, the location of the intersection point, and other information that will be apparent to those skilled in the art, in a database.
  • the computer graphics system may terminate the photon at the point at which it intersects the object, or it may allow the photon to be reflected along another ray.
  • the computer graphics system determines the direction of reflection using a number of criteria, including, among other things, the angle of incidence and characteristics of the simulated object's surface, such as whether the surface is specular, glossy or diffuse.
  • the computer graphics system can make use of random factors in several ways, including, for example, determining whether to terminate a ray at a surface that the ray intersects, or to allow the ray it to be reflected.
  • the computer graphics system may also use random factors to jitter the angle with which a ray is to reflected, and as well as in other ways as will be apparent to those skilled in the art.
  • the computer graphics system After the computer graphics system has shot a number of rays into the scene, it initiates the second “gather” phase of the photon map methodology.
  • the computer graphics system 10 shoots simulated rays from a simulated image plane of a simulated camera into the scene.
  • the rays that are shot from the image plane into the scene during the gather phase essentially correspond to the directions into the scene that are visible from the respective points on the pixel from which they are shot.
  • the computer graphics system makes use of the information regarding the photons, if any, that intersected the surface proximate the point at which the ray shot from the camera intersected the surface, including the directions of incidence of the respective photons, the direction of incidence of the gather ray, and the various characteristics of the surface on which the gather ray is incident.
  • the computer graphics system uses that information to determine the brightness and color of the scene at that point in the image.
  • random factors can be used in several ways, including determining whether to terminate a ray at a surface that the ray intersects or whether to allow the ray to be reflected, determining the direction of reflection of the photons that are shot into the scene during the photon map generation phase, and other ways that will be appreciated by those skilled in the art.
  • the random factors that are used to jitter each ray are collected into an “s”-dimensional vector ⁇ ⁇ [0,1) s , where “s” is related to the maximum number of reflections or refractions that a photon may have before it is terminated. Problems have arisen in the past, since stratification of high-dimensional integration domains has not been available.
  • R j ⁇ j
  • the computer graphics system 10 can reduce the likelihood that correlation patterns will develop in the traces that the computer graphics system shoots into the scene.
  • the computer graphics system 10 evaluates a rendering equation that is of the form L ( ⁇ right arrow over ( x ) ⁇ , ⁇ right arrow over ( ⁇ ) ⁇ )+ ⁇ A L ( ⁇ right arrow over ( x ) ⁇ ′, ⁇ right arrow over ( ⁇ ) ⁇ ( ⁇ right arrow over ( x ) ⁇ ′, ⁇ right arrow over (x) ⁇ ) ⁇ r ( ⁇ right arrow over ( x ) ⁇ , ⁇ right arrow over ( ⁇ ) ⁇ ) ⁇ right arrow over ( x ) ⁇ ′, ⁇ right arrow over (x) ⁇ )) G ( ⁇ right arrow over ( x ) ⁇ , ⁇ right arrow over (x) ⁇ ′) V ( ⁇ right arrow over ( x ) ⁇ , ⁇ right arrow over (x) ⁇ ′) dA′ (16) where
  • L e ( ⁇ right arrow over (x) ⁇ , ⁇ right arrow over ( ⁇ ) ⁇ ) on the right-hand side is an emission term representing the illumination emitted from point ⁇ right arrow over (x) ⁇ in the direction ⁇ right arrow over ( ⁇ ) ⁇ ;
  • L( ⁇ right arrow over (x) ⁇ ′, ( ⁇ right arrow over (x) ⁇ ′, ⁇ right arrow over (x) ⁇ )) on the right-hand side represents the luminance at another point ⁇ right arrow over (x) ⁇ ′ in the scene that is reflected in the direction ⁇ ( ⁇ right arrow over (x) ⁇ ′, ⁇ right arrow over (x) ⁇ ) toward point ⁇ right arrow over (x) ⁇ ;
  • ⁇ r ( ⁇ right arrow over (x) ⁇ , ⁇ ( ⁇ right arrow over (x) ⁇ ′, ⁇ right arrow over (x) ⁇ )) on the right-hand side is a bidirectional scattering distribution function that describes how much of the light incident on from the point ⁇ right arrow over (x) ⁇ ′ is reflected, refracted or otherwise scattered in the direction ⁇ ( ⁇ right arrow over (x) ⁇ ′, ⁇ right arrow over (x) ⁇ ) toward the point ⁇ right arrow over (x) ⁇ , and is generally the sum of a diffuse component, a glossy component and a specular component;
  • point ⁇ right arrow over (x) ⁇ represents the point at which the luminance is to be determined and point ⁇ right arrow over (x) ⁇ ′ represents another point in the scene from which light may be emitted (in the case of a light source) or reflected toward the point ⁇ right arrow over (x) ⁇ .
  • equation (16) reflects the fact that the luminance at point ⁇ right arrow over (x) ⁇ in the direction ⁇ right arrow over ( ⁇ ) ⁇ is generally the sum of two components.
  • One component which is represented by item (ii) above (L e ( ⁇ right arrow over (x) ⁇ , ⁇ right arrow over ( ⁇ ) ⁇ )), represents the light (if any) that is emitted from the point ⁇ right arrow over (x) ⁇ in the direction ⁇ right arrow over ( ⁇ ) ⁇ . This component will be non-zero if the point ⁇ right arrow over (x) ⁇ is on a light source.
  • the second component which is represented by the integral on the right hand side of equation (16), represents the light (if any) that is directed toward point ⁇ right arrow over (x) ⁇ from elsewhere in the scene, including, for example, light sources and other surfaces, and that is directed to or reflected or otherwise scattered towards the point ⁇ right arrow over (x) ⁇ from other points ⁇ right arrow over (x) ⁇ ′ in the scene that are visible from point ⁇ right arrow over (x) ⁇ .
  • the integral may be non-zero for points on light sources as well as for points on other objects in the scene.
  • the integral in equation (16) is evaluated over the area A′ of the surface of a hemisphere that is formed from a sphere that is centered on the point ⁇ right arrow over (x) ⁇ and generally bisected by a plane that is tangent to the surface at point ⁇ right arrow over (x) ⁇ .
  • the computer graphics system 10 numerically evaluates the integral in equation (16) by shooting a plurality of rays from respective points on the pixel into the scene. For each ray shot from the pixel, if the path of the ray intersects the surface of an simulated object in the scene, in addition to shooting shadow rays to light sources as described above to determine the extent to the point on the object is illuminated by a light source, the computer graphics system 10 can also determine the extent to which the point on the object is illuminated by light reflected from elsewhere in the scene. In the latter operation, the computer graphics system 10 can extend the ray by tracing a path from the point on the object that the path of the ray as shot from the pixel intersected, in a direction that is generally a reflection of the path of incidence.
  • the computer graphics system can repeat these operations through a plurality of iterations, or until the path of the ray does not intersect an object in the scene.
  • the computer graphics system 10 will perform similar operations for all of the rays that are shot from the pixel, and the combine the results for the respective rays to determine the pixel value for the pixel.
  • the computer graphics system 10 makes use of a large number of paths in determining the pixel value, it can use correlated sampling to determine the locations of the points of the pixel. Since in correlated sampling the same value ⁇ is used for all of the sample points for the respective pixel, the computer graphics system 10 can generate the sample points R j ( ⁇ ) for the pixel by use of a rigid transformation, which is more efficient than, for example, jittered sampling.
  • the distribution ray tracing methodology extends the path tracing methodology as described above, by adding trajectory splitting.
  • the computer graphics system if a ray shot from the simulated image plane into the scene intersects the simulated surface of a simulated object in a scene, instead of using a single ray reflected from the surface, the computer graphics system reflects a plurality of rays along a like plurality of paths from the intersection point on the surface.
  • the computer graphics system divides the hemisphere into a plurality of strata, one for each path that is to be reflected from the surface.
  • the computer graphics system directs a ray through each stratum, and can make use of trajectory splitting as described above to determine the specific direction through the respective strata. Accordingly, the computer graphics system will trace a plurality of paths from the point at which the ray's path intersects the point on the object.
  • the computer graphics system can perform trajectory splitting at any point at which a ray's path intersects a point on an object.
  • the invention provides a number of advantages.
  • the invention provides a new and improved system and computer-implemented method for evaluating integrals using a Monte Carlo methodology in which the integration domain is partitioned into a plurality of strata using a stratification methodology in which the number of strata is independent of the number of dimensions comprising the integration domain.
  • the invention provides a methodology that makes use of stratification based on rank-1 lattices.
  • Systems and computer-implemented methods according to the invention find utility in a number of applications, including but not limited to computer graphics.
  • the invention is also beneficial in connection with one problem that can arise in computer graphics, namely, aliasing, which gives rise to artifacts in the form of, for example, jagged edges.
  • a computer graphics system 10 in accordance with the invention does not eliminate aliasing artifacts, but it does, however, mask them by noise that can arise from randomization.
  • the sample points are preferably random as between different pixels; however, the samples can be correlated within a pixel.
  • the estimator described above in connection with the last line of equation (13) matches these requirements.
  • the samples are a shifted lattice, with the amount of shift being determined by the value of the random element ⁇ that is used for the pixel, providing good uniformity of distribution throughout the area of the pixel, which, in turn, provides for fast convergence.
  • the various values of elements . . . ⁇ i ⁇ 1 , ⁇ i , ⁇ i+1 . . . that are used provides noise that can mask the aliasing artifacts in the image that is generated.
  • rank-1 lattice in the form of a lattice based on the Fibonacci sequence, it will be appreciated that other forms of rank-1 lattices may be used.
  • a system in accordance with the invention can be constructed in whole or in part from special purpose hardware or a general purpose computer system, or any combination thereof, any portion of which may be controlled by a suitable program.
  • Any program may in whole or in part comprise part of or be stored on the system in a conventional manner, or it may in whole or in part be provided in to the system over a network or other mechanism for transferring information in a conventional manner.
  • the system may be operated and/or otherwise controlled by means of information provided by an operator using operator input elements (not shown) which may be connected directly to the system or which may transfer the information to the system over a network or other mechanism for transferring information in a conventional manner.

Landscapes

  • Engineering & Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • Theoretical Computer Science (AREA)
  • Mathematical Physics (AREA)
  • Data Mining & Analysis (AREA)
  • General Physics & Mathematics (AREA)
  • Mathematical Analysis (AREA)
  • Mathematical Optimization (AREA)
  • Computational Mathematics (AREA)
  • Pure & Applied Mathematics (AREA)
  • Databases & Information Systems (AREA)
  • Software Systems (AREA)
  • General Engineering & Computer Science (AREA)
  • Algebra (AREA)
  • Image Generation (AREA)
US10/439,311 2002-05-15 2003-05-15 System and computer-implemented method for evaluating integrals using stratification by rank-1 lattices Abandoned US20050278406A1 (en)

Priority Applications (4)

Application Number Priority Date Filing Date Title
US10/439,311 US20050278406A1 (en) 2002-05-15 2003-05-15 System and computer-implemented method for evaluating integrals using stratification by rank-1 lattices
US11/474,091 US7589729B2 (en) 2002-05-15 2006-06-23 Image synthesis by rank-1 lattices
US11/688,698 US7516170B2 (en) 2002-05-15 2007-03-20 Computer graphics systems and methods using stratification by rank-1 lattices
US12/416,236 US8259106B2 (en) 2002-05-15 2009-04-01 Low-dimensional rank-1 lattices in computer image synthesis

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US37811502P 2002-05-15 2002-05-15
US10/439,311 US20050278406A1 (en) 2002-05-15 2003-05-15 System and computer-implemented method for evaluating integrals using stratification by rank-1 lattices

Related Child Applications (2)

Application Number Title Priority Date Filing Date
US11/474,091 Continuation-In-Part US7589729B2 (en) 2002-05-15 2006-06-23 Image synthesis by rank-1 lattices
US11/688,698 Continuation US7516170B2 (en) 2002-05-15 2007-03-20 Computer graphics systems and methods using stratification by rank-1 lattices

Publications (1)

Publication Number Publication Date
US20050278406A1 true US20050278406A1 (en) 2005-12-15

Family

ID=29549909

Family Applications (2)

Application Number Title Priority Date Filing Date
US10/439,311 Abandoned US20050278406A1 (en) 2002-05-15 2003-05-15 System and computer-implemented method for evaluating integrals using stratification by rank-1 lattices
US11/688,698 Expired - Fee Related US7516170B2 (en) 2002-05-15 2007-03-20 Computer graphics systems and methods using stratification by rank-1 lattices

Family Applications After (1)

Application Number Title Priority Date Filing Date
US11/688,698 Expired - Fee Related US7516170B2 (en) 2002-05-15 2007-03-20 Computer graphics systems and methods using stratification by rank-1 lattices

Country Status (5)

Country Link
US (2) US20050278406A1 (fr)
EP (1) EP1523715A2 (fr)
AU (1) AU2003239298A1 (fr)
CA (1) CA2495277A1 (fr)
WO (1) WO2003098467A2 (fr)

Cited By (13)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20070109320A1 (en) * 2002-05-15 2007-05-17 Sabrina Skibak Image synthesis by rank-1 lattices
US20080150938A1 (en) * 2006-12-14 2008-06-26 Mental Images Gmbh Computer graphics using meshless finite elements for light transport
US20080180442A1 (en) * 2007-01-30 2008-07-31 Jeffrey Douglas Brown Stochastic Addition of Rays in a Ray Tracing Image Processing System
US20080180441A1 (en) * 2007-01-26 2008-07-31 Jeffrey Douglas Brown Stochastic Culling of Rays with Increased Depth of Recursion
WO2007002592A3 (fr) * 2005-06-23 2008-11-20 Mental Images Gmbh Synthese d'images par reseaux de rang 1
WO2009044282A3 (fr) * 2007-10-04 2009-10-29 Mental Images Gmbh Simulation de la propagation de la lumière par la méthode quasi-monte carlo utilisant un tracé des rayons efficace
US20100281480A1 (en) * 2009-04-29 2010-11-04 Alexander Keller System, method, and computer program product for decomposing a sampling task into a plurality of jobs
US20110304624A1 (en) * 2010-06-14 2011-12-15 Industry-Academic Cooperation Foundation Yonsei University Method and apparatus for ray tracing in a 3-dimensional image system
US8847957B1 (en) * 2011-10-05 2014-09-30 Nvidia Corporation Divide-and-conquer system, method, and computer program product for providing photon mapping
US8860725B2 (en) 2010-08-13 2014-10-14 Nvidia Corporation System, method, and computer program product for deterministically simulating light transport
US8866813B2 (en) 2011-06-30 2014-10-21 Dreamworks Animation Llc Point-based guided importance sampling
US11170254B2 (en) 2017-09-07 2021-11-09 Aurora Innovation, Inc. Method for image analysis
US11334762B1 (en) 2017-09-07 2022-05-17 Aurora Operations, Inc. Method for image analysis

Families Citing this family (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US7432935B2 (en) 2002-11-19 2008-10-07 Mental Images Gmbh Image synthesis methods and systems for generating sample points in a graphics scene
US8259106B2 (en) 2002-05-15 2012-09-04 Mental Images Gmbh Low-dimensional rank-1 lattices in computer image synthesis
JP4383302B2 (ja) * 2004-09-29 2009-12-16 富士通株式会社 評価結果出力プログラム
AU2006279337B2 (en) * 2005-08-18 2010-08-26 Mental Images, Gmbh Image synthesis methods and systems
GB2459024B (en) * 2008-04-03 2011-01-26 Nvidia Corp Low-dimensional rank-1 lattics in computer image synthesis

Citations (6)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20030063082A1 (en) * 2001-06-07 2003-04-03 Georgy Abramov System and method for rendering images using a strictly-deterministic methodology for generating a coarse sequence of sample points
US20050264568A1 (en) * 2000-06-19 2005-12-01 Alexander Keller Computer graphic system and computer-implemented method for generating images using a ray tracing methodology that makes use of a ray tree generated using low-discrepancy sequences and ray tracer for use therewith
US20050264564A1 (en) * 2000-06-19 2005-12-01 Alexander Keller Computer graphic system and computer-implemented method for generating images using a sub-domain photon map methodology
US20050264565A1 (en) * 2000-06-19 2005-12-01 Alexander Keller Computer graphic system and computer-implemented method for generating an image using sample points determined on a sub-pixel grid offset using elements of a low-discrepancy sequence
US20050275663A1 (en) * 2004-06-09 2005-12-15 Yoshiyuki Kokojima Rendering apparatus, rendering processing method and computer program product
US20050275652A1 (en) * 2000-06-19 2005-12-15 Alexander Keller Computer graphics system and computer-implemented method for simulating participating media using sample points determined using elements of a low-discrepancy sequence

Patent Citations (8)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20050264568A1 (en) * 2000-06-19 2005-12-01 Alexander Keller Computer graphic system and computer-implemented method for generating images using a ray tracing methodology that makes use of a ray tree generated using low-discrepancy sequences and ray tracer for use therewith
US20050264564A1 (en) * 2000-06-19 2005-12-01 Alexander Keller Computer graphic system and computer-implemented method for generating images using a sub-domain photon map methodology
US20050264565A1 (en) * 2000-06-19 2005-12-01 Alexander Keller Computer graphic system and computer-implemented method for generating an image using sample points determined on a sub-pixel grid offset using elements of a low-discrepancy sequence
US20050275660A1 (en) * 2000-06-19 2005-12-15 Alexander Keller System and method for generating pixel values for pixels in an image using strictly deterministic methodologies for generating sample points
US20050275652A1 (en) * 2000-06-19 2005-12-15 Alexander Keller Computer graphics system and computer-implemented method for simulating participating media using sample points determined using elements of a low-discrepancy sequence
US20030063082A1 (en) * 2001-06-07 2003-04-03 Georgy Abramov System and method for rendering images using a strictly-deterministic methodology for generating a coarse sequence of sample points
US6911976B2 (en) * 2001-06-07 2005-06-28 Mental Images G.M.B.H. & Co., Kg System and method for rendering images using a strictly-deterministic methodology for generating a coarse sequence of sample points
US20050275663A1 (en) * 2004-06-09 2005-12-15 Yoshiyuki Kokojima Rendering apparatus, rendering processing method and computer program product

Cited By (22)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20070109320A1 (en) * 2002-05-15 2007-05-17 Sabrina Skibak Image synthesis by rank-1 lattices
US7589729B2 (en) 2002-05-15 2009-09-15 Mental Images Gmbh Image synthesis by rank-1 lattices
AU2006261874B2 (en) * 2005-06-23 2010-09-02 Mental Images Gmbh Image synthesis by rank-1 lattices
WO2007002592A3 (fr) * 2005-06-23 2008-11-20 Mental Images Gmbh Synthese d'images par reseaux de rang 1
US20080150938A1 (en) * 2006-12-14 2008-06-26 Mental Images Gmbh Computer graphics using meshless finite elements for light transport
US8102394B2 (en) 2006-12-14 2012-01-24 Mental Images Gmbh Computer graphics using meshless finite elements for light transport
US8022950B2 (en) * 2007-01-26 2011-09-20 International Business Machines Corporation Stochastic culling of rays with increased depth of recursion
US20080180441A1 (en) * 2007-01-26 2008-07-31 Jeffrey Douglas Brown Stochastic Culling of Rays with Increased Depth of Recursion
US8085267B2 (en) * 2007-01-30 2011-12-27 International Business Machines Corporation Stochastic addition of rays in a ray tracing image processing system
US20080180442A1 (en) * 2007-01-30 2008-07-31 Jeffrey Douglas Brown Stochastic Addition of Rays in a Ray Tracing Image Processing System
WO2009044282A3 (fr) * 2007-10-04 2009-10-29 Mental Images Gmbh Simulation de la propagation de la lumière par la méthode quasi-monte carlo utilisant un tracé des rayons efficace
US20100281480A1 (en) * 2009-04-29 2010-11-04 Alexander Keller System, method, and computer program product for decomposing a sampling task into a plurality of jobs
US8266623B2 (en) * 2009-04-29 2012-09-11 Nvidia Corporation System, method, and computer program product for decomposing a sampling task into a plurality of jobs
US20110304624A1 (en) * 2010-06-14 2011-12-15 Industry-Academic Cooperation Foundation Yonsei University Method and apparatus for ray tracing in a 3-dimensional image system
US9189882B2 (en) * 2010-06-14 2015-11-17 Samsung Electronics Co., Ltd. Method and apparatus for ray tracing in a 3-dimensional image system
US8860725B2 (en) 2010-08-13 2014-10-14 Nvidia Corporation System, method, and computer program product for deterministically simulating light transport
US8866813B2 (en) 2011-06-30 2014-10-21 Dreamworks Animation Llc Point-based guided importance sampling
US8847957B1 (en) * 2011-10-05 2014-09-30 Nvidia Corporation Divide-and-conquer system, method, and computer program product for providing photon mapping
US11170254B2 (en) 2017-09-07 2021-11-09 Aurora Innovation, Inc. Method for image analysis
US11334762B1 (en) 2017-09-07 2022-05-17 Aurora Operations, Inc. Method for image analysis
US11748446B2 (en) 2017-09-07 2023-09-05 Aurora Operations, Inc. Method for image analysis
US12056209B2 (en) 2017-09-07 2024-08-06 Aurora Operations, Inc Method for image analysis

Also Published As

Publication number Publication date
US7516170B2 (en) 2009-04-07
US20070271322A1 (en) 2007-11-22
WO2003098467A3 (fr) 2004-01-29
AU2003239298A8 (en) 2003-12-02
AU2003239298A1 (en) 2003-12-02
EP1523715A2 (fr) 2005-04-20
WO2003098467A2 (fr) 2003-11-27
CA2495277A1 (fr) 2003-11-27

Similar Documents

Publication Publication Date Title
US7516170B2 (en) Computer graphics systems and methods using stratification by rank-1 lattices
CA2294995C (fr) Systeme et procede de generation de valeurs de pixels
EP1305775B1 (fr) Generation de valeurs de pixels par l'utilisation de methodes deterministes pour la generation de points echantillons
US7358971B2 (en) Generating images using ray tracing and ray tree generated using low-discrepancy sequences
US7453461B2 (en) Image generation using low-discrepancy sequences
US20080049019A1 (en) Generating Images Using Multiple Photon Maps
US20090122063A1 (en) Computer Graphics Methods and Systems Using Quasi-Monte Carlo Methodology
US20090141026A1 (en) Computer graphics with enumerating qmc sequences in voxels
US20070211051A1 (en) Computer Graphics Systems, Methods and Computer Program Products Using Sample Points Determined Using Low-Discrepancy Sequences
EP0907933B1 (fr) Systeme et procede de generation de valeurs de pixels dans une image selon des methodologies strictement deterministes destinees a generer des points echantillons
EP1628263B1 (fr) Génération de valeurs de pixels par l'utilisation de méthodes déterministes pour la génération de points échantillons
Remington A Radiosity Approach to Realistic Image Synthesis
Fournier et al. Speeding up global illumination computations using programmable GPUs
Nowicki Global illumination and approximating reflectance in real-time

Legal Events

Date Code Title Description
AS Assignment

Owner name: MENTAL IMAGES GMBH, GERMANY

Free format text: MERGER;ASSIGNOR:MENTAL IMAGES G.M.B.H. & CO. KG;REEL/FRAME:017251/0320

Effective date: 20031001

STCB Information on status: application discontinuation

Free format text: ABANDONED -- FAILURE TO RESPOND TO AN OFFICE ACTION

AS Assignment

Owner name: MENTAL IMAGES GMBH, GERMANY

Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:KELLER, ALEXANDER;REEL/FRAME:020209/0743

Effective date: 20071115