Method and system for graphics rendering employing gradient domain metropolis light transport

A method of generating an image. The method includes simulating a presence of at least one light source within a virtualized three dimensional space. Within the virtualized three dimensional space, a light sensing plane is defined. The light sensing plane includes a matrix of a number of pixels to be displayed on a display screen. The method further includes using a light transport procedure, computing a gradient value for each pixel of the matrix to produce a number of gradient values. The gradient computation involves selecting a plurality of light path pairs that contribute to a pixel wherein the selection is biased towards selection of more light paths that pass through pixels having larger gradient values. The plurality of gradient values are converted to a plurality of light intensity values which represent the image.

BACKGROUND OF THE INVENTION

Metropolis sampling is a standard method for generating realistic images with global indirect illumination effects. Metropolis sampling is unbiased and adaptive. It is unbiased in the sense that generated results can be shown to be correct on average, which is desirable for predictive rendering applications. It is adaptive in the sense that that the procedure aims to spend most computational effort on parts of the light transport simulation that contribute the most absolute radiance to the final image. However, absolute radiance, where standard Metropolis sampling concentrates its effort, is not necessarily a good measure for adaptive sampling.

The standard Metropolis light transport procedure generates a number of samples (x⊥i,y⊥i,P⊥i) where x and y are image coordinates, and P is a path coordinate vector, a high-dimensional vector that identifies a particular chain of ray segments that propagate light from a light source to a particular pixel of a viewing plane. The Metropolis process generates samples such that they are distributed according to the path throughput function f(x, y, P) that measures the differential contribution of a single light path to a single image-space location. The final image is obtained from the samples by marginalizing over P, i.e., computing the density of the samples over the image. However, the current method may be slow in terms of obtaining visual convergence.

BRIEF SUMMARY OF THE INVENTION

Accordingly, a need exists for generating an image with faster visual convergence. Embodiments of the present invention provide for a system and methods for generating an intermediate image that depicts the gradient of an actual image by performing a Metropolis-like light transport process in which light path selection is biased to selection of more light paths for pixels having higher gradient values and then reconstructing the final image by solving a standard Poisson equation to convert from the gradient domain to the primal domain.

More specifically, embodiments of the present invention are directed toward a method of generating an image. The method includes simulating a presence of at least one light source within a virtualized three dimensional space. Within the virtualized three dimensional space, a light sensing plane is defined. The light sensing plane includes a matrix of a number of pixels to be displayed on a display screen. The method further includes using a light transport procedure, computing a gradient value for each pixel of the matrix to produce a number of gradient values. Computing the gradient values includes selecting a number of light path pairs within the virtualized three dimensional space. Computing the gradient values further includes determining for each light path pair, a gradient contribution for a respective pixel of the matrix. Additionally, computing the gradient values includes, for each light path pair, updating a gradient value for the respective pixel with the gradient contribution, wherein the selecting is biased toward selecting more light paths that pass through pixels having larger gradient values. The plurality of gradient values are then converted to a plurality of light intensity values which represent the image.

In another embodiment, the present invention is drawn toward a computer implemented method of generating an image. The method includes simulating a presence of at least one light source within a virtualized three dimensional space. A modified Metropolis light transport procedure is executed to produce a two dimensional pixel matrix of gradient values. The matrix represents a light sensor plane within the virtualized three dimensional space. The Metropolis light transport procedure is modified wherein light path sample selection is biased toward selecting more light paths that pass through pixels of the matrix having larger gradient values assigned thereto. The method further includes converting the gradient values to light intensity values. The light intensity values represent the image.

In yet another embodiment, the present invention is drawn toward a computer system. The computer system includes a processor coupled to a bus, a display screen coupled the bus, and a memory coupled to the bus. The memory includes instructions that when executed on the processor cause the computer system to implement a method of generating an image. The method includes simulating a presence of at least one light source within a virtualized three dimensional space. Within the virtualized three dimensional space, a light sensing plane is defined. The light sensing plane includes a matrix of a number of pixels to be displayed on a display screen. The method further includes using a light transport procedure, computing a gradient value for each pixel of the matrix to produce a number of gradient values. Computing the gradient values includes selecting a number of light path pairs within the virtualized three dimensional space. Computing the gradient values further includes determining for each light path pair, a gradient contribution for a respective pixel of the matrix. Additionally, computing the gradient values includes, for each light path pair, updating a gradient value for the respective pixel with the gradient contribution, wherein the selecting is biased toward selecting more light paths that pass through pixels having larger gradient values. The plurality of gradient values are converted to a plurality of light intensity values which represent the image.

DETAILED DESCRIPTION OF THE INVENTION

It should be borne in mind, however, that all of these and similar terms are to be associated with the appropriate physical quantities and are merely convenient labels applied to these quantities. Unless specifically stated otherwise as apparent from the following discussions, it is appreciated that throughout the present disclosure, discussions utilizing terms such as “allocating,” “associating,” “moving,” “copying,” “setting,” “accessing,” “erasing,” “freeing,” “controlling,” “adding,” “recording,” “determining,” “identifying,” “caching,” “maintaining,” “incrementing,” “comparing,” “removing,” “reading,” “writing,” or the like, refer to actions and processes (e.g., flowchart400ofFIG. 4) of a computer system or similar electronic computing device or processor (e.g., system100ofFIG. 1). The computer system or similar electronic computing device manipulates and transforms data represented as physical (electronic) quantities within the computer system memories, registers or other such information storage, transmission or display devices.

Embodiments described herein may be discussed in the general context of computer-executable instructions residing on some form of computer-readable storage medium, such as program modules, executed by one or more computers or other devices. By way of example, and not limitation, computer-readable storage media may comprise non-transitory computer-readable storage media and communication media; non-transitory computer-readable media include all computer-readable media except for a transitory, propagating signal. Generally, program modules include routines, programs, objects, components, data structures, etc., that perform particular tasks or implement particular abstract data types. The functionality of the program modules may be combined or distributed as desired in various embodiments.

FIG. 1shows an exemplary computer system100in accordance with one embodiment of the present invention. Computer system100depicts the components in accordance with embodiments of the present invention providing the execution platform for certain hardware-based and software-based functionality. In general, computer system100comprises a system board106including at least one central processing unit (CPU)102and a system memory104. The CPU102can be coupled to the system memory104via a bridge component/memory controller (not shown) or can be directly coupled to the system memory104via a memory controller120which in one embodiment can be internal to the CPU102.

Computer system100also comprises a graphics subsystem114including at least one graphics processor unit (GPU)110. For example, the graphics subsystem114may be included on a graphics card. The graphics subsystem114may be coupled to a display116. One or more additional GPU(s)110can optionally be coupled to computer system100to further increase its computational power. The GPU(s)110may be coupled to the CPU102and the system memory104via a communication bus108. The GPU110can be implemented as a discrete component, a discrete graphics card designed to couple to the computer system100via a connector (e.g., AGP slot, PCI-Express slot, etc.), a discrete integrated circuit die (e.g., mounted directly on a motherboard), or as an integrated GPU included within the integrated circuit die of a computer system chipset component (not shown). Additionally, memory devices112may be coupled with the GPU110for high bandwidth graphics data storage, e.g., the frame buffer. In an embodiment, the memory devices112may be dynamic random-access memory. A power source unit (PSU)118may provide electrical power to the system board106and graphics subsystem114.

The CPU102and the GPU110can also be integrated into a single integrated circuit die and the CPU and GPU may share various resources, such as instruction logic, buffers, functional units and so on, or separate resources may be provided for graphics and general-purpose operations. The GPU may further be integrated into a core logic component. Accordingly, any or all the circuits and/or functionality described herein as being associated with the GPU110can also be implemented in, and performed by, a suitably equipped CPU102. Additionally, while embodiments herein may make reference to a GPU, it should be noted that the described circuits and/or functionality can also be implemented with other types of processors (e.g., general purpose or other special-purpose coprocessors) or within a CPU.

System100can be implemented as, for example, a desktop computer system or server computer system having a powerful general-purpose CPU102coupled to a dedicated graphics rendering GPU110. In such an embodiment, components can be included that add peripheral buses, specialized audio/video components, IO devices, and the like. Similarly, system100can be implemented as a portable device (e.g., cellphone, PDA, etc.), direct broadcast satellite (DBS)/terrestrial set-top box or a set-top video game console device such as, for example, the Xbox®, available from Microsoft Corporation of Redmond, Wash., or the PlayStation3®, available from Sony Computer Entertainment Corporation of Tokyo, Japan. System100can also be implemented as a “system on a chip”, where the electronics (e.g., the components102,104,110,112, and the like) of a computing device are wholly contained within a single integrated circuit die. Examples include a hand-held instrument with a display, a car navigation system, a portable entertainment system, and the like.

Gradient Domain Metropolis Light Transport

Embodiments of the present invention provide for a system and method for using a modified Metropolis light transport process for generating an intermediate image within a viewing plane that depicts the light gradient values of an actual image and then reconstructing the final image by solving a standard Poisson equation to convert from the gradient domain to the primal domain. However, embodiments of the present invention may be applied to any system or method for generating an image. The original Metropolis light transport procedure is described by E. Veach and L. Guibas 1997. Metropolis Light Transport. Proc. SIGGRAPH '97.

FIG. 2depicts a virtualized three dimensional graphics scene200represented as data objects stored in memory including a light source221, according to an embodiment of the present invention. The virtualized three dimensional scene200also includes objects223within the scene. Light source221illuminates virtualized three dimensional scene200via illumination path225. One can appreciate that illumination path225is just one of many illumination paths casted by light source221in virtualized three dimensional space200. The virtualized three dimensional scene200also includes a viewpoint227. Viewpoint227is the point at which objects223are viewed within the three dimensional scene200. Viewpoint227casts a viewpoint through viewing window229. Viewing window229is a two dimensional light sensing plane including a matrix of pixels231to be displayed on a display device e.g., display device116(FIG. 1).

Illumination path225casted by light source221reflects and bounces off objects223. Illumination path225is cast according to the standard Metropolis light transport procedure, which is well known in the art. Illumination path225passes through a pixel231on viewing window229. In an embodiment of the present invention, illumination path225may be perturbed in either the x-direction or the y-direction resulting in a Δx light path233or a Δy light path235. The Δx light path233and the Δy light path235are light paths that are perturbed from illumination path255by one pixel in either the x or y direction. Together, illumination path225and Δx light path233form a light sample path pair. Similarly, illumination path225and Δy light path235also form a light sample path pair. These light sample path pairs allow embodiments of the present invention to calculate a light intensity gradient for pixel231is a particular direction, e.g., Δx or Δy. The gradient contributions, or the amount of light intensity differential within the pair, is stored for the pixel231either in the Δx gradient value or the Δy gradient value. Each pixel231within the matrix of viewing window229therefore stores a gradient value for each direction (x-direction and y-direction).

The standard Metropolis light transport procedure generates a path and stores the path's nodes in a list. It can then modify the path by adding extra nodes and creating a new light path. While creating this new path, the procedure decides how many new nodes to add and whether or not these new nodes will actually create a new path. In other words, while path selection may be done partly in accordance with the Metropolis light transport procedure, embodiments of the present invention differ from the Metropolis light transport procedure in that 1) the path sample is perturbed to allow gradient computation and 2) sample light path selection is biased toward selecting more paths that pass through pixels having larger gradient values and vice-versa. In contrast, in the traditional Metropolis light transport algorithm, path selection is biased towards selecting more paths that contribute more lights toward the image.

The present invention aims to discover sample light paths that contribute a larger gradient to the image. In turn, this effects the probability of changing paths to the ones perturbed based on those paths that contribute a larger gradient to the image. Each path contributes a fixed value to the gradient. The path selection is biased based on selection of paths that pass through pixels having a greater gradient. More paths are selected that pass through pixels of large gradients. In this way, sample path selection is biased toward image areas that have greater gradients, e.g., those image areas where the light intensity changes the most. Using a Poisson equation, the gradient values are converted to absolute values (primal domain) of each pixel and the resulting image is displayed on a display device116(FIG. 1).

In an embodiment of the present invention, a gradient value between illumination path225and Δx light path233is calculated. The gradient contribution may be either +1 or −1. The gradient contribution is then deposited to the overall gradient sum (for the x-direction) of illumination path225for pixel231. A similar procedure is carried out for the y-direction. The process is repeated for a subsequent illumination path its corresponding Δx light path and Δy light path. Multiple sample path selection therefore builds up gradient values in the Δx and Δy directions for all pixels in the array.

FIG. 3Adepicts a grid within a viewing plane or screen333including a plurality of pixels231having gradient values, according to an embodiment of the present invention. Each pixel231includes two gradient values representing the gradient of the image intensity stored at each pixel231. Accordingly, what is stored at each pixel is ΔI/Δx and ΔI/y, the overall gradient sum. Additionally, each pixel also includes a coordinate value. The gradient values of the pixel231are difference between light path pairs, as described inFIG. 2.

The Metropolis procedure is executed to select paths. The path selection is biased towards those paths that contribution larger gradient values to the pixel. The gradient values are maintained across the screen333coordinates of the displayed pixels231. A Poisson equation is solved on the gradient values to convert the gradient values to absolute values for each pixel231. The resulting image is then displayed on screen333of display device116(FIG. 1).

Embodiments of the present invention perform Metropolis light transport based on light path selection biased toward those image areas that have higher gradient values to compute gradient values in the gradient domain for each pixel and convert the gradient values to absolute values in the primal domain prior to displaying the resulting image on a display device.

FIG. 3Bdepicts an array of pixels within a viewing plane or screen333including a plurality of pixels having gradient values, wherein certain pixels have greater gradient values than other pixels, according to an embodiment of the present invention. Screen333includes a first pixel337and a second pixel339. In this particular example, first pixel337has a larger gradient contribution than second pixel339. As a result, casting of illumination rays225is biased toward first pixel337and more samples are taken at first pixel337. In comparison, less samples are taken at second pixel339. As mentioned above, both first pixel337and second pixel339have perturbed light paths, either a Δx light path233or a Δy light path235for each sample. Together, each illumination ray225forms a light path pairs with a Δx light path233or a Δy light path235. Accordingly, first pixel337will have more light path pairs than second pixel339. Each pixel231also includes two gradient values representing the gradient of the image intensity stored at each pixel231. Accordingly, what is stored at each pixel is ΔI/Δx and Ally, the overall gradient sum.

FIG. 4depicts a flowchart400of an exemplary computer controlled process of constructing an image from a gradient based Metropolis light transport procedure, according to an embodiment of the present invention. Flowchart400depicts the flow of a modified Metropolis light transport procedure. The computations are operated within the gradient domain. The aim of operating in the gradient domain is to concentrate effort on “where things happen” in the image, offering the potential for faster visual convergence.

Generally, a standard Metropolis light transport procedure generates a number of samples (x⊥i,y⊥i,P⊥i) where x and y are image coordinates, and P is a path coordinate vector, a high-dimensional vector that identifies a particular chain of ray segments that propagate light from the light source to a particular pixel. The Metropolis process generates samples such that they are distributed according to the path throughput function f(x, y, P) that measures the differential contribution of a single light path to a single image-space location, i.e., (xi,yi,Pi)∝ƒ(x,y,P). The final image is obtained from the samples by marginalizing over P, e.g., computing the density of the samples over the image.

In embodiments of the present invention, Metropolis sampling is utilized to generate samples that are distributed according to the finite differences of the path throughput function in the x and y directions. Samples are selected that are biased towards selection of those light paths that pass through pixels of higher gradient values. In principle, two sets of samples A and B are generated such that:
(xiA,yiA,PiA)∝|ƒ(x+1,y,P)−ƒ(x,y,P)|
and
(xiB,yiB,PiB)∝|ƒ(x+1,y,P)−ƒ(x,y,P)|
e.g., the first set of samples A is distributed according to the absolute per-pixel x differences, and the set B is distributed according to the absolute y differences. In an embodiment, the sample sets are computed using a single sampler, using the direction of the difference as an additional variable in the path throughput function, and switching stochastically between the two according to the standard Metropolis procedure. This process is advantageous in that computing effort is spent on regions of change while still maintaining unbiasedness. It enables estimation of the true signed derivative, as required by the subsequent reconstruction step, instead of its absolute value which drives the sampler.

Once marginalized over P, the two sets of samples A and B form a stochastic estimate of the numerical gradient of the final image. A standard Poisson solver is then employed for generating the image based on the estimated gradients.

More specifically, in block402, the process of reconstructing and displaying an image from gradients then using a Poisson solver to convert to the primal domain is started. An initial path, P, is chosen and its fitness is computed. A path's fitness is, in many embodiments, the absolute difference of the path contribution. In other embodiments, the path's fitness may be the absolute difference of the path contribution of the primal domain contribution of the path255. The path selection is biased toward selecting more paths that pass through pixels having larger gradient values and vice-versa. For example, inFIG. 2an initial path reflecting off the objects is chosen and its fitness is computed.

In block404, a decision is made whether the process should be terminated due to run time or image completeness. Typically, the process will not be terminated on the first pass of the process. If the process is to be terminated, the image will be reconstructed from the gradients using a Poisson solver, block428. The process will then end and the final image will be displayed, block430.

In block406, if the process is not to be terminated in block404, a decision is made whether the fitness for P is negative. If the fitness is deemed to be negative, a contribution C is set to negative one, block410. If the fitness is deemed to be non-negative, a contribution C is set to one, block408. Typically, pixels having larger gradient values will have more samples selected that pass there through and will have more contribution toward the resulting image. For example, inFIG. 3B, the first pixel has a larger gradient value and thus has more samples selected that pass there through.

In block412, upon setting contribution C to either one or negative one (in block408or block410), contribution C of path P is deposited within the image. For example, inFIG. 2a contribution of the path is deposited within the gradient value for the pixel associated with the path.

In block414, a mutated path P′ for is proposed and subsequently a fitness for P′ is computed in block416. In an embodiment, mutated path P′ is adjacent to path P. For example, inFIG. 3A, the mutated path is adjacent to original path P, such that it passes through a neighboring pixel, either Δx or Δy.

In block418, a path P″ is constructed. The path far P″ is offset (Δx or Δy) one pixel from P′. Subsequently, a fitness for P″ is computed in block420. For example, inFIG. 3A, the mutated path is adjacent to original path P.

In block422, the fitness of P′ is replaced by the absolute difference of the fitness of P′ and the fitness of P″. The absolute difference is computed as part of the procedure.

In block424, a decision is made whether the mutated path should be probabilistically accepted based on comparing the fitness of P and the fitness of P′. If the mutated path should be accepted, P should be replaced with P′, block426, and the process is repeated with the new P value. If the mutated path should not be accepted, the process is repeated without replacing the P value.

It is appreciated that while flowchart400applies to derivatives in the X direction, a similar procedure is run independently for the Y direction. The standard Metropolis light transport procedure comprises blocks402,404,408,412,414,416,424,426, and430. The present invention adds blocks406,410,418,420,422, and428. Blocks416,418,420, and422are all a part of the fitness computation. These steps apply to the initial fitness computation in block402as well.

By application of this process over the selection of many many paths, step412populates the pixels of the display plane with the Δx and Δy gradient values to thereby construct the image in the gradient domain. At the final step, the Poisson solver may be used, step428, to convert the gradient domain to the primal domain, e.g., the image intensity values. Knowing the gradients for each pixel and the average image intensity across the image allows conversion to the primal domain, in one embodiment.

In an embodiment, the process of flowchart400may be used to directly estimate the numerical Laplacian of the final image instead of its gradient. This involves computing second-order differences along both the x and the y dimensions. A Laplacian representation of the final image is a tighter representation than the gradient field because not every vector field is the gradient of a scalar function.

In a further embodiment, the Poisson solver may be regularized by computing a low-resolution, possibly low-resolution, and noisy primal domain “guidance image” that simultaneously sets the correct scale and offset for the gradient reconstruction and steers the reconstruction towards the correct low-frequency content. This may be accomplished by requiring the local weighted averages of both the reconstructed and guidance images to match.

In yet another embodiment, the procedure may be extended to compute derivatives on multiple scales. For example, double-length gradients |ƒ(x+2,y,P)−ƒ(x,y,P)| and |ƒ(x,y+2,P)−ƒ(x,y,P)| and drive the sampler stochastically at multiple scales to build a gradient pyramid.

FIG. 5depicts a comparison of an image generated using a standard Metropolis light transport procedure520and an image generated using gradient domain Metropolis light transport procedure522, according to an embodiment of the present invention.

The image generated using the gradient domain Metropolis light transport procedure522uses a single indirect bounce of illumination in a simple scene. The image generated using a standard Metropolis light transport procedure520is calculated in the primal domain. The image generated using the gradient domain Metropolis light transport procedure522requires a lower number of samples per pixel than the image generated using a standard Metropolis light transport procedure520as modified herein to produce gradient computation and light path selection through pixels of higher gradient values. For example, the approximate number of samples per pixels is 16 for the gradient domain Metropolis light transport procedure522and less than or equal to 32 for the image generated using a standard Metropolis light transport procedure520.

FIG. 6depicts a flowchart600of an exemplary computer implemented process of generating an image, according to an embodiment of the present invention.

In block602, a presence of a least one light source within a virtualized three dimensional space is simulated. For example, inFIG. 5, the gradient domain Metropolis light transport procedure uses a single indirect bounce of illumination in a simple scene.

In block604, within the virtualized three dimensional space, a light sensing plane is defined. The light sensing plane includes a matrix of a plurality of pixels to be displayed on a display screen.

In block606, using a light transport procedure, a gradient value is computed for each pixel of the matrix to produce a plurality of gradient values. The computation for each pixel of the matrix is described in the flowchart ofFIG. 7. In an embodiment, the light transport procedure is a modified Metropolis light transport procedure. Block606is repeated until the process should be terminated due to run time or image completeness.

In block608, the plurality of gradient values are converted to a plurality of light intensity values which represent the image. The converting includes converting the plurality of gradient values to the plurality of light intensity values using a Poisson solver procedure. In an embodiment, the converting further includes a Metropolis light transport procedure to produce a coarse plurality of light intensity values for the matrix. Further, the converting also includes using the coarse plurality of light intensity values in combination with the plurality of gradient values to produce the plurality of light intensity values.

In an embodiment, the process of generating an image also includes displaying the image on the display screen. The process of flowchart600may be implemented using system100(FIG. 1).

FIG. 7depicts a flowchart700of an exemplary computer implemented process of computing a gradient value, according to an embodiment of the present invention. Flowchart700describes computing the gradient value in block606ofFIG. 6.

In block702, a plurality of light path pairs within the virtualized three dimensional space is selected.

In block704, for each light path pair, a gradient contribution for a respective pixel of the matrix is determined. In an embodiment, the determining includes, for a first light path of a light path pair, computing a first light intensity contribution to a first pixel of the matrix. Further, the determining includes, for a second light path of the first light path pair, computing a second light intensity contribution to a second pixel, where the second pixel is adjacent to the first pixel. Moreover, the determining includes determining a difference between the first and second light intensity contributions. Additionally, the determining includes assigning the gradient contribution a positive value if the difference is positive and assigning the gradient contribution a negative value if the difference is negative.

In an embodiment, the first and second pixels are positioned in accordance with (x, y) and (x, y+1), respectively, within the matrix. In another embodiment, the first and second pixels are positioned in accordance with (x, y) and (x+1, y).

In block706, for each light path pair, a gradient value for the respective pixel with the gradient contribution is updated. The selecting in block502is biased toward selecting more light paths that pass through pixels having larger gradient values.

FIG. 8depicts a flowchart800of an exemplary computer implemented method of generating an image, according to an embodiment of the present invention.

In block802, a presence of at least one light source within a virtualized three dimensional space is simulated.

In block804, a modified Metropolis light transport procedure is executed to produce a two dimensional pixel matrix of gradient values. The matrix represents a light sensor plane within the virtualized three dimensional space. The modified Metropolis light transport procedure is modified wherein light path sample selection is biased toward selecting more light paths that pass through pixels of the matrix having larger gradient values assigned thereto.

Executing the Metropolis light transport procedure includes selecting a plurality of light path pairs within the virtualized three-dimensional space. Further, the procedure includes determining for each light path pair, a gradient contribution for a respective pixel of the matrix. Additionally, the procedure includes, for each light pair, updating a gradient value for the respective pixel with the gradient contribution.

In an embodiment, the determining includes, for a first light path of a light path pair, computing a first light intensity contribution to a first pixel of the matrix. Further, the determining includes, for a second light path of the first light path pair, computing a second light intensity contribution to a second pixel, the second pixel being adjacent to the first pixel. Moreover, the determining includes determining a difference between the first and second light intensity contributions. Additionally, the determining includes assigning the gradient contribution a positive value if the difference is positive and assigning the gradient contribution a negative value if the difference is negative.

In yet another embodiment, the first and second pixels are positioned in accordance with (x, y) and (x, y+1), respectively, within the matrix.

In block806, the gradient values are converted to light intensity values. The light intensity values represent the image. In an embodiment, the converting includes converting the gradient values to the light intensity values using a Poisson solver procedure.

In an embodiment, the process of flowchart800also includes rendering the image by displaying the light intensity values on a display screen.

In yet another embodiment, the process of flowchart800also includes performing a standard Metropolis light transport procedure to produce a coarse plurality of light intensity values for the matrix. The converting includes using the coarse plurality of light intensity values in combination with the gradient values to produce the light intensity values.

FIG. 9depicts a flowchart of an exemplary computer implemented process of producing a plurality of light intensity values, in accordance with an embodiment of the present invention. In block902, a Metropolis light transport procedure is performed to produce a coarse plurality of light intensity values for a matrix comprising a plurality of pixels. For example, inFIG. 2, a standard Metropolis light transport procedure is performed to produce a plurality of light intensity values for the matrix. The matrix includes a plurality of pixels.

In block904, a modified Metropolis light transport procedure is used to select sample light paths and use the paths to select light path pairs and compute a plurality of gradient values for each pixel of the matrix. For example, inFIG. 2, a modified Metropolis light transport procedure is used to select sample light paths generated by the light source. The sample light paths are then used to select light path pairs. The light path pairs are a combination of the illumination path and either a Δx light path or Δy light path. The light path pairs are then used to compute a plurality of gradient values for each pixel within the matrix.

In block906, using the coarse plurality of light intensity values in combination with the plurality of gradient values, a plurality of light intensity values is produced. For example, inFIG. 4, the coarse plurality of light intensity values combined with the plurality of gradient values are used to produce a plurality of light intensity values prior to displaying the image.

While various embodiments have been described and/or illustrated herein in the context of fully functional computing systems, one or more of these example embodiments may be distributed as a program product in a variety of forms, regardless of the particular type of computer-readable media used to actually carry out the distribution. The embodiments disclosed herein may also be implemented using software modules that perform certain tasks. These software modules may include script, batch, or other executable files that may be stored on a computer-readable storage medium or in a computing system. These software modules may configure a computing system to perform one or more of the example embodiments disclosed herein. One or more of the software modules disclosed herein may be implemented in a cloud computing environment. Cloud computing environments may provide various services and applications via the Internet. These cloud-based services (e.g., software as a service, platform as a service, infrastructure as a service, etc.) may be accessible through a Web browser or other remote interface. Various functions described herein may be provided through a remote desktop environment or any other cloud-based computing environment.

Embodiments according to the invention are thus described. While the present disclosure has been described in particular embodiments, it should be appreciated that the invention should not be construed as limited by such embodiments, but rather construed according to the below claims.