Patent Description:
A common task in computer graphics is to render an image of a scene. This task is equivalent to determining a value for each pixel in the image, which in turn depends on solving a rendering equation representative of the scene. The rendering equation is an integral equation describing the amount of radiance towards any direction at any spatial point in the scene. However, due to its complex form, the rendering equation often has no closed-form solution. As a result, solving the rendering equation, i.e., rendering the image of the scene, is typically computed numerically using Monte Carlo methods.

Conventional Monte Carlo methods use repeated random sampling to approximate a solution to the rendering equation by expressing the integral as an expected value of random variables. Each sampling technique selects samples according to a unique probability distribution.

In some cases, a method called multiple importance sampling (MIS) can be used to combine different sampling techniques. However, combining sampling techniques with MIS can produce an overly defensive estimator that leads to unnecessarily high variance, i.e., noise, in the rendered image. <NPL>, Population Monte Carlo (PMC) sampling methods that are powerful tools for approximating distributions of static unknowns given a set of observations. <NPL>, a general method enhancing the robustness of estimators based on multiple importance sampling (MIS) in a numerical integration context. <NPL>, that Multiple Importance Sampling (MIS) is a key technique for achieving robustness of Monte Carlo estimators in computer graphics and other fields.

This specification describes modifications to conventional MIS. In general, the MIS framework represents a family of estimators, parametrized by weighting functions used to combine samples from different sampling techniques. Departing from the conventional MIS framework provides potential for estimator variance reduction. When compared to the images rendered using conventional MIS, those that are rendered as described in this specification show reduced variance. Like conventional MIS, the invention employs a combination of several sampling techniques, but unlike conventional MIS, the probability density function (pdf) of one of the sampling techniques is allowed to take any shape. Subsequently, an analytic expression is found for the pdf of the free technique that minimizes variance of the resulting estimator.

In a first aspect, the invention provides a computer-implemented method, comprising: receiving data describing a scene, wherein the scene comprises one or more light sources and one or more objects having different surface optical properties; receiving a request to render an image of the scene using a multiple importance sampling method of direct illumination that combines sampling of a high dynamic range - HDR - environment map and sampling of a cosine product of a bidirectional reflectance distribution function - BRDF - of an object surface, wherein each sampling technique uses a different probability distribution to sample a respective fraction of a total number of samples, wherein sampling from the HDR environment map is implemented using a tabulated probability density function, and sampling the cosine product of the BRDF is an analytical formula derived from a probability density function depending on the outgoing direction and surface position of a ray; modifying only the probability density function of the HDR environment map to reduce a variance of the multiple importance sampling method while holding the respective fractions and the other probability distribution fixed; rendering the scene using the multiple importance sampling using the modified particular probability distribution and the other probability distribution; and outputting the rendered scene in response to the request.

Other embodiments of this aspect include corresponding computer systems, apparatus, and computer programs recorded on one or more computer storage devices, each configured to perform the actions of the methods.

Other embodiments of this aspect can include one or more of the following optional features. The probability assigned to a given sample by the modified particular probability distribution is dependent on a difference between (i) a first value that is proportional to a contribution of the given sample to a rendering result and (ii) a second value that is a weighted sum of the probabilities assigned to the given sample by the other probability distributions. Each probability in the weighted sum is weighted by the respective sample count fraction for the corresponding other probability distribution. When the difference is greater than zero, the probability assigned to the given sample is the difference divided by the sample count fraction for the modified particular probability distribution and a normalization factor. When the difference is not greater than zero, the probability assigned to the given sample is zero.

The subject matter described in this specification can be implemented in particular embodiments so as to realize one or more of the following advantages. Images of scenes can be rendered with a high degree of visual realism while reducing the computational cost of image rendering. Rendering images can be performed more efficiently by selecting and combining in a specific manner various sampling techniques. As another advantage, the estimator variance of the improved version of MIS described in this specification can be reduced compared to the estimator variance of conventional MIS. The improvements to MIS described in this specification are simple to implement using one or more computing devices. The output can only decrease the variance, not increase it. The implementation can have little computation and memory overhead. Furthermore, the overall output can provide at least a same rendering quality of conventional MIS faster and with reduced computational effort.

<FIG> is a block diagram of an example image rendering system <NUM>. The image rendering system <NUM> is an example system of one or more computers in one or more locations that is capable of producing a rendered image <NUM> of a scene given a view point and an image plane, where the scene is a three-dimensional environment that includes one or more reflective and scattering surfaces and is affected by one or more light sources.

The image rendering system <NUM> obtains as input an environment model <NUM> and analyzes the environment model <NUM> to generate the rendered image <NUM> of the scene. The environment model <NUM> can include data describing the position, orientation, shape, or optical properties of various objects in the scene. The environment model <NUM> can also include information about a view point and an image plane, such as the position of the view point, the position of the image plane, the orientation of the image plane, the size of the image plane, the resolution of the rendered image, etc..

The image rendering system <NUM> includes a pre-rendering module <NUM> and a rendering module <NUM>. The pre-rendering module <NUM> optimizes the rendering process by preprocessing the environment model <NUM>. In some implementations, the pre-rendering module <NUM> can preprocess the scene to improve the sampling process performed by the rendering module <NUM>. For example, the pre-rendering module <NUM> can divide the scene into different regions based on one or more optical properties of the different regions, and recommend sampling techniques optimized for each region to the rendering module <NUM>.

The rendering module <NUM> renders an image representing the environment model <NUM>. During the rendering process, the rendering module <NUM> can support a variety of rendering techniques to determine a value for each of the pixels on the rendered image <NUM>. Examples of rendering techniques include image-centric ray tracing and rasterization. For example, to implement ray tracing, the rendering module <NUM> can cast multiple rays from the view point (viewing rays). The viewing rays go through pixels on the image plane and intersect points in the scene. If the points belong to a light source, the light source can directly contribute a value to the corresponding pixel on the rendered image. If the points belong to a non-light-emitting object, then the viewing rays can be reflected or scattered in one or more directions to reach a light source to contribute a pixel value. The number and the direction of the reflected/scattered rays depend on the specific optical properties and geometry of the points. For example, if the points are located on a scattering surface, multiple outgoing directions can be analyzed as the surface uniformly diffuses an incident ray. Each of the reflected or scattered rays can reach a light source that contributes to a pixel value corresponding to the original ray. In another example, the reflected/scattered rays can reach another non-light-emitting object that causes an additional reflection/scattering.

When scenes include complex lighting conditions and/or material surface models, tracing rays from all point in the scene can have high computational cost. To reduce the computational cost associated with rendering, the rendering module <NUM> samples rays, for example, from points in the scene to the light sources affecting the scene. That is, the rendering module <NUM> selects a set of surface points and/or a set of directions in the scene to estimate pixel values of the rendered image.

To sample rays, the rendering module <NUM> employs one or more sampling techniques. Two common sampling techniques used to evaluate lighting at a point on a surface include sampling the light source and sampling a bidirectional reflectance distribution function (BRDF). Sampling the light source can refer various types of light sources including, for example a point source, spherical source, rectangular source, etc. or, as described in more detail below, sampling a high dynamic range (HDR) map applied to a model of a scene.

The BRDF describes how light is reflected/scattered off a surface as a function of the direction of a ray incident on the surface. When a viewing ray is incident on a glossy surface a significant portion of the viewing ray is reflected in a single direction according to the law of reflection, which states that the angle of an incident ray is equal to the angle of a reflected ray. As a result, for efficient sampling purposes, the BRDF sampling technique can randomly select directions of the reflected or outgoing ray at surface points according to a probability distribution similar to that of the bidirectional reflectance distribution function. That is to say, the sampling technique randomly samples outgoing ray directions at the incident point of an incoming ray, with each particular direction having a probability of being sampled equal to the ratio of the light reflected in the particular direction to the amount of light incident on the surface from the incoming ray direction. When instead a ray is incident on a rough scattering surface, the outgoing rays can be scattered uniformly in all directions. As a result, it is more efficient to sample surface points on a light source than to sample outgoing ray directions at incident points in a scene. For example, the surface points on the light source can be sampled according to a uniform distribution.

If a scene includes surfaces with different optical properties, e.g. both glossy reflective surfaces and rough scattering surfaces, a single sampling technique may be insufficient to sample the scene. As a result, multiple sampling techniques may be used, each suitable for rendering a different region of a scene. By combining the sampling techniques using MIS, a low noise level can be achieved across the entire rendered image.

When the rendering module <NUM> employs multiple sampling techniques, multiple importance sampling provides a simple yet robust means for combining the sampling techniques with provable variance bounds.

Consider an integral F = ∫X f(x)dµ(x) of a non-negative function f(x). An unbiased Monte Carlo estimator (F) for the integral can be constructed by taking n random variables (samples) Xi, i = <NUM>,. , n generated by a sampling technique with the pdf p(x), and setting the estimator <MAT>. Variance of the estimator depends on the number of samples and on how 'similar' the pdf p(x) is to the integrand f(x). Whenever p is exactly proportional to f up to a normalization constant, i.e., p(x) = f(x)/F, the variance is zero.

Finding a single pdf that closely approximates f under all circumstances may be difficult, but there may be multiple sampling techniques, t ∈ T, with pdfs pt(x), each of which approximates some important feature of f, e.g., bidirectional reflectance distribution function (BRDF) sampling or high dynamic range (HDR) map sampling.

Multiple importance sampling (MIS) provides a general framework for constructing a combined estimator given multiple sampling techniques. Suppose there are nt = ct * n independent samples from each technique, where ct denotes the respective fractions of the total sample count and each ith independent sample is denoted Xt,i. The multi-sample combined estimator then reads: <MAT> where the first summation is over the multiple sampling techniques and the second summation is over the independent samples, and where the weighting functions wt(x) provide a degree of freedom that can be used to optimize the estimator's variance.

Thus, the image rendering system can optimize the combination of the different sampling techniques by adjusting the weighting functions, e.g., by adjusting the contribution of the different sampling techniques for different regions of the rendered image, such as different portions of object surfaces. In this way, the weighting functions provide a degree of freedom that can be used to optimize the MIS estimator's variance. In some implementations, the balance heuristic is used for wt(x), which is described in greater detail below.

The equation for balance heuristic is: <MAT> Where ct is the respective fraction of the total sample count for the sampling technique t in the set of sampling techniques, T, and pt(x) is the pdf of the sampling technique t. The prime symbol in the denominator indicates that the sum in the denominator goes over all sampling techniques (including t) while the numerator uses just the individual sampling technique t corresponding to the weight.

Combining the balance heuristic with the general MIS estimator of equation <NUM> yields a combined estimator in the form: <MAT> Where Peff(x) equals ∑t'∈T ct'pt' (x) from the balance heuristic denominator in equation <NUM> above. This combined estimator shows that the use of the balance heuristic effectively corresponds to a regular Monte Carlo estimator with samples drawn from a peff(x), i.e., a weighted average of pdfs of the sampling techniques.

While the balance heuristic generally results in a low variance MIS estimator in a global sense, when applied to a particular fixed set of sampling techniques it may not result in a good estimator. Since the balance heuristic effectively averages pdfs of the combined sampling techniques, it can cause high-value areas to be undersampled and low-value areas to be oversampled.

However, the estimator variance can be reduced by optimizing one of the sampling techniques to effectively "sharpen" its pdf to compensate for the effect of pdf averaging induced by the balance heuristic.

For an MIS combination of a given set T of sampling techniques t ∈ T with sample fractions ct > <NUM>, one of the sampling techniques can be designated as "free. " The objective of the modified MIS is to find a pdf for sampling technique τ: pτ(x), that will minimize variance of the combined estimator with the balance heuristic shown above in equation <NUM>. That is, to reduce the estimator's variance, the system optimizes one of the sampling techniques.

In an ideal case, the MIS estimator from equation <NUM> would have zero variance. For this to happen, the mixture density peff(x) has to be exactly proportional to the integrand f(x), i.e., <MAT>.

Assuming the balance heuristic, it holds that peff(x) = q(x) + cτ pτ(x), where there are separated pdfs of all the fixed sampling techniques under a single term q(x) = Σt'∈T\{τ} ct pt(x).

This can be algebraically solved for the pdf as: <MAT> However, to make the resulting pdf valid, the negative values can be clamped and the equation renormalized to obtain the optimized pdf for the modified MIS as: <MAT>.

The pdf of equation <NUM> provides a generalized formula for a modified pdf that can be applied to any MIS estimator even outside of the context of image rendering of the invention. <FIG> and <FIG>, below, describe an application of this general result to the specific context of the invention of image-based lighting in image rendering systems.

<FIG> illustrates an example of image-based lighting in accordance with the invention. Image-based lighting concerns the computation of illumination due to a high-dynamic-range (HDR) environment map on a surface with an arbitrary BRDF. The HDR environment map can correspond, for example, to an omnidirectional capture of real-world illumination that is projected on to a hemisphere relative to the surface being lit. An image rendering system, e.g., the image rendering system <NUM> of <FIG>, is used to compute the illumination of a scene based on the HDR environment map using MIS.

Specifically, <FIG> shows a surface <NUM> having an arbitrary BRDF <NUM>. HDR map <NUM> can be used to determine the illumination on a point x <NUM> on the surface from a particular angle. The surface has a normal n, <NUM>.

The reflected radiance of point x on the surface <NUM> due to direct illumination from the HDR map is calculated as:
<MAT>.

In equation <NUM>, x is the position on the surface, n is the surface normal at x. ωo is the outgoing view direction shown by ray <NUM> in <FIG>. <IMG>(n) is the hemisphere centered on the surface normal n. The HDR map emission coming from direction ωi is given by LI(ωi), which is illustrated by ray <NUM> in <FIG>. Variable ρ denotes the surface BRDF and |ωi · n|+ the positive part of the cosine of the angle between ωi and n.

A Monte Carlo estimation of the direct illumination from the HDR map, Ldir(x, ωo), typically relies on two sampling techniques that use random sampling to find approximate solutions to the radiance. The first sampling technique involves sampling of the HDR map while the second sampling technique involves sampling of the product of the BRDF and cosine |ωi · n|+. MIS is then used to combine the sampling techniques.

Sampling from the HDR map, e.g., map <NUM>, in accordance with the invention, is implemented using a tabulated probability density function (pdf) pI(ωi). By contrast, sampling the cosine product of the BRDF is an analytical formula derived from a pdf pρ(ωi)|ωo, x), which generally depends on the outgoing direction and surface position.

An image rendering system then renders the surface <NUM> using MIS by combining results produced by the two sampling techniques to generate the reflected radiance of points on the surface <NUM>. Moreover, as will be described in greater detail below with respect to <FIG>, optimizing one of these sampling techniques is used to reduce estimator variance from the estimator result of conventional MIS.

<FIG> is a flow diagram of a process <NUM> in accordance with the invention for rendering an image of a scene having image-based lighting using a modified multiple importance sampling. For convenience, the process <NUM> will be described as being performed by a system of one or more computers, located in one or more locations, and programmed appropriately in accordance with this specification. For example, an image rendering system, e.g., the image rendering system <NUM> of <FIG>, appropriately programmed, can perform the process <NUM>.

The system receives data describing a scene (<NUM>). The scene can include one or more objects, which can have different surface optical properties, as well as data describing image-based illumination, for example, an HDR map of image-based illumination. The object data can describe, for example, the position, orientation, shape, or optical properties of the one or more objects. The data describing the scene may be a complete set of data, i.e., it includes all the necessary information for the system to render a visually realistic image of the scene. As an example, the scene can be the scene represented by surface <NUM> of <FIG>.

The data can also describe the amount of light, i.e., radiance, emitted from various points in the scene along a particular viewing direction. The outgoing radiance, i.e., the radiance leaving a point in any direction in the scene, is a sum of emitted radiance (radiance emitted from the point, e.g., if the point lies on the surface of a light source) and reflected radiance (radiance reflected from the point). This relation can be captured by the rendering equation as: <MAT>.

This rendering equation gives the amount of radiance leaving a point in the scene (as described by the vector x) in a specific direction (as described by the angle ω<NUM>). The data describing the scene specifies all the parameters included in the rendering equation. In particular, it is important to note that Lreflected in equation <NUM> corresponds to Ldir + Lindir, where Ldir is given by equation <NUM> and corresponds to the value improved by the modified MIS. Lindir is typically solved recursively by tracing a reflected ray and computing equation <NUM> at a point where the reflected ray hits the scene being rendered.

The system receives a request to render an image of the scene using a multiple importance sampling (<NUM>). n total samples can be sampled in the scene using a specified number of sampling techniques with different probability distributions, each used to sample a respective fraction of the n total samples.

For example, the image can be an image taken from the perspective of a specified view point in a specified image plane. The system can render the image by image-centric ray tracing, i.e., tracing the path of light through pixels in the image plane and simulating the effects of its encounters with objects in the scene. Rendering an image is equivalent to solving the associated rendering equation and obtaining a function that describes how a ray interacts with the one or more objects in the scene. However, the term Lreflected (x, ω<NUM>) involves a complex integral, resulting in the rendering equation often having no closed-form solution. To approximate a solution, the rendering equation can be evaluated numerically using Monte Carlo estimation that relies on multiple sampling techniques. These sampling techniques are then combined using MIS. As noted above, conventional MIS relies on different weighting functions for each sampling technique to fine-tune the contribution of each sampling technique. The MIS estimator variance therefore also depends on the weighting functions used.

Referring back to <FIG>, the first sampling technique involves sampling of the HDR map describing the omnidirectional image-based illumination of the scene while the second sampling technique involves sampling of the product of the BRDF at points of the surface and |ωi · n|+.

Mathematically, each of the sampling techniques is associated with a probability distribution function. The probability distribution indicates the likelihood that a data point will be sampled. For example, a uniform probability distribution indicates that all data points are equally likely to get sampled.

The system modifies a probability distribution associated with one of the sampling techniques (<NUM>). In contrast to conventional MIS, the modified MIS described in this specification optimizes a pdf from one of the sampling techniques to reduce the estimator variance. In the above invention for image-based lighting, sampling from the HDR map is implemented using a tabulated pdf, which is typically simpler to modify than the pdf used to sample the BRDF-cosine product.

In particular, in some implementations, the system optimizes the tabulated probability density in a preprocess, the modification can be used in any renderer relying on MIS for HDR sampling without any modifications of the sampling routines themselves. That is, the optimization can be done before the sampling starts and does not rely on any adaptive updates to the system. Since the system merely modifies a tabulated pdf, it has no overhead and marginal impact on the time per sample.

To get the modified pdf p̃I for the image-based lighting scenario described in <FIG>, the integrand from equation <NUM> and the BRDF sampling technique pρ (ωi|ωO, x) is plugged into the generalized pdf solution of equation <NUM> above to obtain: <MAT> where cI is the fraction of samples taken from the HDR map and fI(x, ωO, ωi) = LI(ωi)ρ(x, ωO, ωi)|ωi · n|+. The normalization factor b ensures that p̃I(ωi|ωO,x) integrates to one.

The modified tabulated pdf in equation <NUM> is difficult to apply in practice, because the pdf p̃I(ωi | ωO, x) depends on both ωo and x, and the equation requires the system to tabulate the pdf for each view direction and surface position. However, a normal-dependent pdf (nd), which provides a practical approximation of the pdf of equation <NUM>, can be derived by assuming Lambertian BRDFs with unit albedo, the fraction of incident light that is reflected by a surface, <MAT>, as shown below:
<MAT>
where <MAT>.

The resulting pdf now depends only on the surface normal n, and could be precomputed for a number of directions. To obtain a more convenient result that can be readily applied in existing renderers, the dependence on n is removed to generate a normal-independent pdf (ni) by averaging <MAT> over all possible normal directions. This yields the practical modified probability distribution: <MAT> where LI is the mean HDR map luminance and bni ensures that <MAT> integrates to one.

The system renders the scene using the modified probability distribution (<NUM>). For example, the system can replace the free sampling technique with a modified sampling technique having the modified probability distribution described above. The system can combine the sampling techniques, including the modified sampling technique, using an appropriate weighting functions, e.g., using the balance heuristic. The improved multiple importance sampling that uses the modified sampling technique, has a reduced MIS estimator variance compared to a conventional MIS estimator.

The system outputs the rendered image (<NUM>). Once the system obtains a value for each pixel on the rendered image, the image can be converted to a suitable format and displayed. Examples of image data formats include JPEG, PNG, TIFF, SVG, CGM, FITS, etc..

While this disclosure discusses, in accordance with the invention, the application of an improved MIS to the field of computer graphics, in general, the improved MIS can be applied to a wide range of problems relying on MIS, which do not form part of the invention.

For example, the modified MIS as described in this specification can be used in transport path guiding applications, freeflight sampling in heterogeneous media, or light sampling for direct or indirect illumination. All those approaches feature empirically constructed pdfs combined with a defensive technique that lend themselves to the modified MIS described in this specification.

Embodiments of the subject matter described in this specification can be implemented as one or more computer programs, i.e., one or more modules of computer program instructions encoded on a tangible non transitory program carrier for execution by, or to control the operation of, data processing apparatus. Alternatively, or in addition, the program instructions can be encoded on an artificially generated propagated signal, e.g., a machine-generated electrical, optical, or electromagnetic signal, that is generated to encode information for transmission to suitable receiver apparatus for execution by a data processing apparatus. The computer storage medium is not, however, a propagated signal.

A computer program (which may also be referred to or described as a program, software, a software application, a module, a software module, a script, or code) can be written in any form of programming language, including compiled or interpreted languages, or declarative or procedural languages, and it can be deployed in any form, including as a standalone program or as a module, component, subroutine, or other unit suitable for use in a computing environment.

Claim 1:
A computer-implemented method, comprising:
receiving (<NUM>) data describing a scene, wherein the scene comprises one or more light sources and one or more objects having different surface optical properties;
receiving (<NUM>) a request to render an image of the scene using a multiple importance sampling method of direct illumination that combines sampling of a high dynamic range - HDR - environment map and sampling of a cosine product of a bidirectional reflectance distribution function - BRDF - of an object surface, wherein each sampling technique uses a different probability distribution to sample a respective fraction of a total number of samples, wherein sampling from the HDR environment map is implemented using a tabulated probability density function, and sampling the cosine product of the BRDF is an analytical formula derived from a probability density function depending on the outgoing direction and surface position of a ray;
modifying (<NUM>) only the probability density function of the HDR environment map to reduce a variance of the multiple importance sampling method while holding the respective fractions and the other probability distribution fixed;
rendering (<NUM>) the scene using the multiple importance sampling using the modified particular probability distribution and the other probability distribution; and
outputting (<NUM>) the rendered scene in response to the request.