# Patent

## Title
Methods and systems of joint path importance sampling

## Abstract

Methods and systems of joint path importance sampling are provided to construct light paths in participating media. The product of anisotropic phase functions and geometric terms across a sequence of path vertices are considered. A connection subpath is determined to join a light source subpath with a light receiver subpath with multiple intermediate vertices while considering the product of phase functions and geometry terms. A joint probability density function (“PDF”) may be factorized unidirectional or bidirectional. The joint PDF may be factorized into a product of multiple conditional PDFs, each of which corresponds to a sampling routine. Analytic importance sampling may be performed for isotropic scattering, whereas tabulated importance sampling may be performed for anisotropic scattering.

## Background
CROSS-REFERENCE TO RELATED APPLICATIONS
This application claims the benefit of U.S. Provisional Application No. 61/861,636, filed on Aug. 2, 2013 and which is hereby incorporated herein by reference in its entirety.


TECHNICAL FIELD
The present application relates generally to computer graphics, more particularly, some embodiments relate to methods and systems of joint path importance sampling for rendering low-order anisotropic scattering.
DESCRIPTION OF THE RELATED ART
Simulating light transport in participating media has important applications across many diverse fields, such as medical imaging and nuclear physics, as well as computer graphics. However, faithful and accurate simulation of light transport can be challenging. Rendering is the process of generating an image from a model or a scene file. A scene file contains objects, comprising a virtual scene, in a strictly defined language or data structure, such as geometry, viewpoint, texture, lighting, and shading information. Data included in the scene file may be forwarded to a rendering program for processing and subsequently outputted to a digital image or raster graphics image file.
Tracing every particle of light in a scene is nearly impractical and would consume a huge amount of time. Even tracing a portion large enough to produce an image takes an inordinate amount of time if the sampling is not intelligently restricted. Methods for rendering participating media such as general Monte Carlo integration, the diffusion approximation, and the Feynman path integral approximation have emerged. However, each of the methods may be well suited for specific scattering scenarios, and a common limitation of all these methods is their inefficiency or inaccuracy in handling participating media with highly anisotropic scattering and moderate albedo.
BRIEF SUMMARY OF THE APPLICATION
Methods and systems of joint path importance sampling are provided to construct paths in participating media. The product of anisotropic phase functions and geometric terms across a sequence of path vertices are accounted for. Connection paths are introduced to join a light source (e.g., a light) subpath and a light receiver (e.g., a camera) subpath with multiple (e.g., two) additional intermediate vertices while accounting for the product of phase functions and geometry terms. In various embodiments, the probability density function (“PDF”) is simplified by considering the extra dimension as a degree of freedom along with symmetries uniquely present in media light transport.
Various embodiments create a subpath comprising a set of subpath segments to connect the light source subpath and a light receiver subpath by providing a set of intermediate vertices. The vertices may be determined by joint importance sampling thereby determining a set of connection subpath segments. In various embodiments, the set of vertices may be determined based on a configuration that is received. In one embodiment, the configuration received comprises a first endpoint as well as a first direction, and a second endpoint as well as a second direction. The first direction may be defined by the light source and the first vertex, whereas the second direction may be defined by the light receiver and the second vertex. The light source subpath defined by the light source and the first endpoint, and the light receiver subpath defined by the light receiver and the second endpoint, may have arbitrary lengths.
A joint probability density function (“PDF”) may be factorized differently. In some embodiments, factorization of a joint PDF is unidirectional. In other embodiments, factorization of a joint PDF is bidirectional. The set of connection vertices may be sampled from a joint distribution proportional to the geometry and scattering terms of the resulting connection subpath. In various embodiments, the joint PDF may be factorized into a product of multiple conditional PDFs, each of which corresponds to a sampling routine. Some embodiments perform analytic importance samplings for isotropic scattering. Exact importance sampling of the product of geometry terms for a sequence of vertices joining the given subpaths in the configuration is provided. Other embodiments perform tabulated importance sampling for anisotropic scattering. Tabulations for importance sampling the product of geometry and anisotropic phase function terms across a sequence of vertices joining the given subpaths in the configuration are provided.
Other features and aspects of the application will become apparent from the following detailed description, taken in conjunction with the accompanying drawings, which illustrate, by way of example, the features in accordance with embodiments of the application. The summary is not intended to limit the scope of the application, which is defined solely by the claims attached hereto.



BRIEF DESCRIPTION OF THE DRAWINGS
The present application, in accordance with one or more various embodiments, is described in detail with reference to the following figures. The drawings are provided for purposes of illustration only and merely depict typical or example embodiments of the application. These drawings are provided to facilitate the reader's understanding of the application and shall not be considered limiting of the breadth, scope, or applicability of the application. It should be noted that for clarity and ease of illustration these drawings are not necessarily made to scale.
FIG. 1 illustrates an exemplary configuration for joint path importance sampling.
FIG. 2 is a flow diagram illustrating an exemplary method 100 of joint path importance sampling.
FIG. 3A illustrates an exemplary process of unidirectional factorization of the joint PDF.
FIG. 3B illustrates that an exemplary geometric configuration for sampling a distance for unidirectional factorization of the joint PDF for sampling the distance tdc 313.
FIG. 3C illustrates that an exemplary geometric configuration for sampling a direction for unidirectional factorization of the joint PDF for sampling the direction ωcb 314.
FIG. 3D illustrates that an exemplary geometric configuration for sampling a distance for unidirectional factorization of the joint PDF for sampling the distance tcb 312.
FIG. 4 illustrates an exemplary process of bidirectional factorization of the joint PDF.
FIG. 5A illustrates a canonical coordinate system for tabulating a conditional PDF in unidirectional factorization of the joint PDF for a line tabulation for double scattering.
FIG. 5B illustrates a canonical coordinate system for tabulating a conditional PDF in unidirectional factorization of the joint PDF for a spherical tabulation.
FIG. 5C illustrates a canonical coordinate system for tabulating a conditional PDF in unidirectional factorization of the joint PDF for a line tabulation for single scattering.
FIG. 6A illustrates a canonical coordinate system for tabulating a conditional PDF in bidirectional factorization of the joint PDF for a spherical tabulation.
FIG. 6B illustrates a canonical coordinate system for tabulating a conditional PDF in bidirectional factorization of the joint PDF for a line tabulation for double scattering.
FIG. 6C illustrates a canonical coordinate system for tabulating a conditional PDF in bidirectional factorization of the joint PDF for a line tabulation for single scattering.
FIG. 7 illustrates an example computing module that may be used in implementing various features of embodiments of the application.



The figures are not intended to be exhaustive or to limit the application to the precise form disclosed. It should be understood that the application can be practiced with modification and alteration, and that the application be limited only by the claims and the equivalents thereof.
DETAILED DESCRIPTION OF THE EMBODIMENTS OF THE APPLICATION
Central to Monte Carlo-based rendering algorithms is the task of sampling light transport paths connecting light sources to a light receiver, e.g., a camera. A path integral formulation of light transport for surfaces is introduced and extended to participating media. The path integrand can be factorized into the product of several terms, such as the geometry, transmittance, and scattering terms. Ideally, Monte Carlo integration would sample paths from a probability density function (PDF) proportional to the product of all terms in the integrand. However, in practice, subpaths are constructed incrementally, vertex-by-vertex, followed by a (deterministic) subpath connection, which may yield path PDFs that cannot account for some high-variance terms.
Path-sampling approaches traditionally construct light transport paths incrementally by sequentially sampling local scattering events. Unfortunately, this incremental construction sacrifices a global view of the path's contribution, and can lead to significant variance. Path-sampling methods for surface illumination have traditionally been extended to participating media by simply incorporating propagation distance as an independent sampling dimension. This increases dimensionality even further, and normally results in a more complicated formulation.
FIG. 1 illustrates an exemplary configuration for joint path importance sampling. In the illustrated configuration, a light source 101 and a light receiver (e.g., a camera, or an observer, etc.) are provided, and the light subpath xla 110 and an eye subpath dxe 111 are given. The full path xlabcdxe is constructed to connect the endpoints a 103 and d 104 via a random-decision intermediate connection subpath comprising a set of connection subpath segments. The set of connection subpath segments may be determined by a set of vertices. For example, the vertices b 105 and c 106 determine a set of connection subpath segments ab 112, be 113, and cd 114. In various embodiments, given the vertices a 103 and d 104, respectively with an incident and an outgoing direction, the vertices b 105 and c 106 are sampled from a joint distribution proportional to the geometry and scattering terms of the resulting connection subpath segments 112-114. The subpaths xl 110 and xe 111 may have arbitrary lengths. For example, when xl 110 has a length of zero, the endpoint a is on the light source 101. When xe 111 has a zero length, the endpoint d is on the camera lens. In various embodiments, a direction ωdc at vertex d 104 is given, which may be sampled as part of the eye subpath. In various embodiments, the inputs to the joint path importance sampling may include the vertex a 103 with its incident direction ωla and the vertex d 104 with an outgoing direction ωdc. In one embodiment, the new vertex c 106 must reside on the ray (d, ωdc), and the distance tdc from the vertex d 104 along ωdc and another vertex b 105 need to be sampled. The probability density function (PDF) of the entire path xlabcdxe is provided in Equation (1):

p(x)=p(xl,a,ωdc,d,xe)p(b,tdc|ωla,a,ωdc,d)G(c,d),  (1)

where the geometry term G(c, d) converts the PDF to the volume measure. In various embodiments, the PDF p(xl,a,ωdc,d,xe) may be provided by a rendering algorithm.

FIG. 2 is a flow diagram illustrating an exemplary method 100 of joint path importance sampling. At step 202, an input configuration is received. The input configuration (ωla,a,ωdc,d) provides information regarding the endpoints a 103 and d 104. For example, a first direction ωla is the direction of the first path defined by a first endpoint a and the light source, and a second direction ωdc is the direction of the second path defined by a second endpoint d and the light receiver. All the PDFs including the directional PDFs and distance PDFs during the joint path importance sampling may be conditioned on the input configuration. In various embodiments, the input configuration may be represented as Ξ≡ωla,a,ωdc,d. In various embodiments, a first subpath and a second subpath are provided. The first subpath may be a light source subpath, defined by the light source, potentially several intermediate points, and the first endpoint. The second subpath may be a light receiver subpath, defined by the light receiver, potentially several intermediate points, and the second endpoint. For example, referring back to FIG. 1, the first subpath is the light subpath xla and the second subpath is the eye subpath dxe.
Subsequently, at step 204, a set of vertices are sampled. A connection subpath comprising a set of subpath segments may be determined based on the set of vertices. The connection subpath connects the first endpoint and the second endpoint. As such, the connection subpath together with the first and the second subpaths may construct the full path connecting the light source with the light receiver. In various embodiments, only the product of the geometry terms and the phase functions is sampled, such that

p(b,tdc|Ξ)G(c,d)=CΞG(abcd)ρ(abc),  (2)

where CΞ is a normalization factor dependent on the input configuration Ξ. In one embodiment, two vertices b and c are sampled, and three subpath segments (e.g., subpath segments ab, bc, and cd) defined by the vertices a-d may be determined. At step 206, the full path is created. In various embodiments, the first subpath and the second subpath are connected by the set of subpath segments determined at step 204. In various embodiments, the direction ωdc and the direction incident to the vertex d are given.

In various embodiments, at step 204, when sampling vertices, the joint PDF may be factorized. Factorization of the joint PDF may influence the definition of the individual sampling PDFs and the corresponding sampling routines. FIG. 3A illustrates an exemplary process of unidirectional factorization of the joint PDF. In one embodiment, factorization is unidirectional where the vertices are sampled from the same direction along the path starting from the first or the second vertex. In the illustrated example, the vertices a 310 and d 311 as well as the direction ωla 310 and ωdc 311 are given. The vertices b 303 and c 304, the distance of the subpath ab 311 and the direction ωcb 314 are sampled. To sample the vertices b 303 and c 304, a distance tdc 313 is sampled, which effectively samples the vertex c 304 in combination with the direction ωdc 311. Subsequently, a direction ωcb 314 is sampled and a distance tcb 312 is subsequently sampled to obtain the vertex b 303. The joint PDF may be measured as:

p(b,tdc|Ξ)=p(tcb,ωcb,tdc|Ξ)G(b,c),  (3)

because the vertex b 303 is sampled as a distance and direction from the vertex c 304. The joint PDF may be factorized into a product of three conditional PDFs, corresponding to sampling tdc 313 first, ωcb 314 thereafter, and tcb 312 finally:

p(tdc,ωcb,tcb|Ξ)=p(tdc|Ξ)  (4)

p(ωcb|tdc,Ξ)  (5)

p(tcb|ωcb,tdc,Ξ)  (6)

FIGS. 3B-3D illustrate geometric configurations for unidirectional factorization of the joint PDF. As illustrated in FIGS. 3B-3C, the vertex c 304 is obtained by sampling a distance tdc 313 along the direction ωdc 311. Subsequently, a direction ωcb 314 is sampled from the vertex c 304. Finally, the vertex b 303 is obtained by sampling a distance tcb 312 along the direction ωcb 314. FIG. 3B illustrates that an exemplary geometric configuration for sampling the distance tdc 313. FIG. 3C illustrates a geometric configuration for sampling the direction ωcb 314. FIG. 3D illustrates a geometric configuration for sampling the distance tcb 312. In various embodiments, the phase function is constant for the case of isotropic scattering, Equation (3) may be simplified to Equation (7):

p(tcb,ωcb,tdc|Ξ)=CΞG(a,b).  (7)

The PDF p(tcb|ωcb,tdc,Ξ) may be defined as the ratio of the joint distribution and the marginalized joint according to Equation (8):




  
    
      
        
          p
          ⁡
          
            (
            
              
                
                  t
                  cb
                
                |
                
                  ω
                  cb
                
              
              ,
              
                t
                dc
              
              ,
              Ξ
            
            )
          
        
        =
        
          
            
              p
              ⁡
              
                (
                
                  
                    t
                    cb
                  
                  ,
                  
                    ω
                    cb
                  
                  ,
                  
                    
                      t
                      dc
                    
                    |
                    Ξ
                  
                
                )
              
            
            
              p
              ⁡
              
                (
                
                  
                    ω
                    cb
                  
                  ,
                  
                    
                      t
                      dc
                    
                    |
                    Ξ
                  
                
                )
              
            
          
          .
        
      
    
    
      
        (
        8
        )
      
    
  




The denominator of Equation (8) may be obtained by integrating out the distance tcb 312 according to Equation (9):




  
    
      
        
          
            p
            ⁡
            
              (
              
                
                  ω
                  cb
                
                ,
                
                  
                    t
                    dc
                  
                  |
                  Ξ
                
              
              )
            
          
          =
          
            
              
                ∫
                0
                ∞
              
              ⁢
              
                p
                ⁡
                
                  (
                  
                    
                      t
                      cb
                    
                    ,
                    
                      ω
                      cb
                    
                    ,
                    
                      
                        t
                        dc
                      
                      |
                      Ξ
                    
                  
                  )
                
              
            
            =
            
              
                dt
                cb
              
              =
              
                
                  
                    C
                    Ξ
                  
                  ⁢
                  
                    
                      ∫
                      0
                      ∞
                    
                    ⁢
                    
                      
                        1
                        
                          
                            h
                            
                              ca
                              ⊥
                            
                            2
                          
                          +
                          
                            
                              (
                              
                                
                                  t
                                  
                                    ca
                                    ⊥
                                  
                                
                                -
                                
                                  t
                                  cb
                                
                              
                              )
                            
                            2
                          
                        
                      
                      ⁢
                      
                        dt
                        cb
                      
                    
                  
                
                =
                
                  C
                  ⁢
                  
                    
                  
                  ⁢
                  Ξ
                  ⁢
                  
                    
                      π
                      -
                      
                        θ
                        cb
                      
                    
                    
                      
                        t
                        ca
                      
                      ⁢
                      sin
                      ⁢
                      
                        
                      
                      ⁢
                      
                        θ
                        cb
                      
                    
                  
                
              
            
          
        
        ,
      
    
    
      
        (
        9
        )
      
    
  




where hca⊥ 327 is the distance between the vertex a 301 and the ray (c, ωcb), tca⊥ 326 is the distance between the vertex c 304 and this projection, and θcb 325 is the angle between ωcb 314 and the line between the vertices c 304 and a 301 of length tca 322, as illustrated in FIG. 3D. The PDF of tcb 312 is defined according to Equation (10):





  
    
      
        
          p
          ⁡
          
            (
            
              
                
                  t
                  cb
                
                |
                
                  ω
                  cb
                
              
              ,
              
                t
                dc
              
              ,
              Ξ
            
            )
          
        
        =
        
          
            
              
                t
                ca
              
              ⁢
              sin
              ⁢
              
                
              
              ⁢
              
                θ
                cb
              
            
            
              π
              -
              
                θ
                cb
              
            
          
          ⁢
          
            
              1
              
                
                  h
                  
                    ca
                    ⊥
                  
                  2
                
                +
                
                  
                    (
                    
                      
                        t
                        
                          ca
                          ⊥
                        
                      
                      -
                      
                        t
                        cb
                      
                    
                    )
                  
                  2
                
              
            
            .
          
        
      
    
    
      
        (
        10
        )
      
    
  




The PDF p(ωcb|tdc,Ξ) may be derived according to Equation (11):




  
    
      
        
          p
          ⁡
          
            (
            
              
                
                  ω
                  cb
                
                |
                
                  t
                  dc
                
              
              ,
              Ξ
            
            )
          
        
        =
        
          
            
              p
              ⁡
              
                (
                
                  
                    ω
                    cb
                  
                  ,
                  
                    
                      t
                      dc
                    
                    |
                    Ξ
                  
                
                )
              
            
            
              p
              ⁡
              
                (
                
                  
                    t
                    dc
                  
                  |
                  Ξ
                
                )
              
            
          
          .
        
      
    
    
      
        (
        11
        )
      
    
  




The denominator of Equation (11) may be obtained by integrating out ωcb 314 according to Equation (12):




  
    
      
        
          p
          ⁡
          
            (
            
              
                t
                dc
              
              |
              Ξ
            
            )
          
        
        =
        
          
            
              ∫
              
                S
                2
              
            
            ⁢
            
              
                p
                ⁡
                
                  (
                  
                    
                      ω
                      cb
                    
                    ,
                    
                      
                        t
                        dc
                      
                      |
                      Ξ
                    
                  
                  )
                
              
              ⁢
              d
              ⁢
              
                
              
              ⁢
              
                ω
                cb
              
            
          
          =
          
            
              
                ∫
                0
                
                  2
                  ⁢
                  π
                
              
              ⁢
              
                
                  ∫
                  0
                  π
                
                ⁢
                
                  
                    C
                    Ξ
                  
                  ⁢
                  
                    
                      π
                      -
                      
                        θ
                        cb
                      
                    
                    
                      
                        t
                        ca
                      
                      ⁢
                      sin
                      ⁢
                      
                        
                      
                      ⁢
                      
                        θ
                        cb
                      
                    
                  
                  ⁢
                  sin
                  ⁢
                  
                    
                  
                  ⁢
                  
                    θ
                    cb
                  
                  ⁢
                  d
                  ⁢
                  
                    
                  
                  ⁢
                  θ
                  ⁢
                  
                    
                  
                  ⁢
                  d
                  ⁢
                  
                    
                  
                  ⁢
                  φ
                
              
            
            =
            
              
                
                  
                    C
                    Ξ
                  
                  ⁢
                  
                    π
                    3
                  
                
                
                  t
                  ca
                
              
              .
            
          
        
      
    
    
      
        (
        12
        )
      
    
  




Hence, the PDF of the direction ωcb 314 is derived as Equation (13):




  
    
      
        
          p
          ⁡
          
            (
            
              
                
                  ω
                  cb
                
                |
                
                  t
                  dc
                
              
              ,
              Ξ
            
            )
          
        
        =
        
          
            
              π
              -
              
                θ
                cb
              
            
            
              
                π
                3
              
              ⁢
              
                
              
              ⁢
              sin
              ⁢
              
                
              
              ⁢
              
                θ
                cb
              
            
          
          .
        
      
    
    
      
        (
        13
        )
      
    
  




As illustrated in FIG. 3B, the final step in the marginalization procedure provides the PDF for sampling a distance tdc 313 along the ray (d, ωdc). In various embodiments, the normalization factor C, is derived. The PDF of Equation (12) is enforced to integrate to 1 according to Equation (14):




  
    
      
        
          
            
              ∫
              0
              ∞
            
            ⁢
            
              
                p
                ⁡
                
                  (
                  
                    
                      t
                      dc
                    
                    |
                    Ξ
                  
                  )
                
              
              ⁢
              
                dt
                dc
              
            
          
          =
          
            
              
                ∫
                0
                ∞
              
              ⁢
              
                
                  
                    
                      C
                      Ξ
                    
                    ⁢
                    
                      π
                      3
                    
                  
                  
                    
                      
                        h
                        
                          da
                          ⊥
                        
                        2
                      
                      +
                      
                        
                          (
                          
                            
                              t
                              
                                da
                                ⊥
                              
                            
                            -
                            
                              t
                              dc
                            
                          
                          )
                        
                        2
                      
                    
                  
                
                ⁢
                
                  dt
                  dc
                
              
            
            =
            1
          
        
        ,
      
    
    
      
        (
        14
        )
      
    
  




where hca⊥ 327 is the distance between the vertex a 301 and the ray (c, ωdc), and tca⊥ 326 is the distance between vertex c 304 and this projection. By setting a maximum sampling distance tdcmax 313 along the direction ωdc 311, the normalization factor CΞ may be represented according to Equation (15):





  
    
      
        
          
            C
            Ξ
          
          ⁢
          
            π
            3
          
        
        =
        
          
            1
            
              C
              
                t
                dc
                max
              
            
          
          =
          
            
              1
              
                
                  a
                  ⁢
                  
                    
                  
                  ⁢
                  sin
                  ⁢
                  
                    
                  
                  ⁢
                  
                    h
                    ⁡
                    
                      (
                      
                        
                          
                            t
                            dc
                            max
                          
                          -
                          
                            t
                            
                              da
                              ⊥
                            
                          
                        
                        
                          h
                          
                            da
                            ⊥
                          
                        
                      
                      )
                    
                  
                
                -
                
                  a
                  ⁢
                  
                    
                  
                  ⁢
                  sin
                  ⁢
                  
                    
                  
                  ⁢
                  
                    h
                    ⁡
                    
                      (
                      
                        
                          -
                          
                            t
                            
                              da
                              ⊥
                            
                          
                        
                        
                          h
                          
                            da
                            ⊥
                          
                        
                      
                      )
                    
                  
                
              
            
            .
          
        
      
    
    
      
        (
        15
        )
      
    
  




The conditional PDF for the distance tdc 313 is defined as:





  
    
      
        
          p
          ⁡
          
            (
            
              
                t
                dc
              
              |
              Ξ
            
            )
          
        
        =
        
          
            1
            
              C
              
                t
                dc
                max
              
            
          
          ⁢
          
            
              1
              
                
                  
                    h
                    
                      da
                      ⊥
                    
                    2
                  
                  +
                  
                    
                      (
                      
                        
                          t
                          
                            da
                            ⊥
                          
                        
                        -
                        
                          t
                          dc
                        
                      
                      )
                    
                    2
                  
                
              
            
            .
          
        
      
    
    
      
        (
        16
        )
      
    
  




The joint unidirectional PDF p(b,tdc|Ξ) may be obtained by multiplying the conditional PDFs from Equations (10), (13), and (16):




  
    
      
        
          p
          ⁡
          
            (
            
              b
              ,
              
                
                  t
                  dc
                
                |
                Ξ
              
            
            )
          
        
        =
        
          
            
              p
              ⁡
              
                (
                
                  
                    t
                    cb
                  
                  ,
                  
                    ω
                    cb
                  
                  ,
                  
                    
                      t
                      dc
                    
                    |
                    Ξ
                  
                
                )
              
            
            ⁢
            
              G
              ⁡
              
                (
                
                  b
                  ,
                  c
                
                )
              
            
          
          =
          
            
              
                
                  G
                  ⁡
                  
                    (
                    
                      a
                      ,
                      b
                    
                    )
                  
                
                ⁢
                
                  G
                  ⁡
                  
                    (
                    
                      b
                      ,
                      c
                    
                    )
                  
                
              
              
                
                  π
                  3
                
                ⁢
                
                  C
                  
                    t
                    dc
                    max
                  
                
              
            
            .
          
        
      
    
    
      
        (
        17
        )
      
    
  




In various embodiments, the corresponding sampling routines derived using the inverse cumulative distribution functions (CDFs) of the conditional PDFs (10), (13), and (16) may be needed in order to use in the context of importance sampling for rendering. A random distance tdc along ωdc may be sampled using the inverse CDF of Equation (16):




  
    
      
        
          
            t
            dc
          
          =
          
            
              
                t
                da
              
              ⁢
              sin
              ⁢
              
                
              
              ⁢
              
                h
                ⁡
                
                  (
                  
                    ξC
                    
                      t
                      dc
                      max
                    
                  
                  )
                
              
            
            -
            
              
                t
                
                  da
                  ⊥
                
              
              ⁡
              
                (
                
                  1
                  +
                  
                    cos
                    ⁢
                    
                      
                    
                    ⁢
                    
                      h
                      ⁡
                      
                        (
                        
                          ξC
                          
                            t
                            dc
                            max
                          
                        
                        )
                      
                    
                  
                
                )
              
            
          
        
        ,
      
    
    
      
        (
        18
        )
      
    
  




where tda=√{square root over (hda⊥2+tda⊥2)} is the distance between vertices d 302 and a 301, and ξε[0,1) is a uniform random number.

The corresponding CDF for the PDF for the direction ωcb in Equation (13) is:




  
    
      
        
          P
          ⁡
          
            (
            
              ω
              cb
            
            )
          
        
        =
        
          
            
              ∫
              0
              
                2
                ⁢
                π
              
            
            ⁢
            
              
                ∫
                0
                
                  θ
                  cb
                
              
              ⁢
              
                
                  
                    π
                    -
                    θ
                  
                  
                    
                      π
                      3
                    
                    ⁢
                    sin
                    ⁢
                    
                      
                    
                    ⁢
                    θ
                  
                
                ⁢
                sin
                ⁢
                
                  
                
                ⁢
                θ
                ⁢
                
                  
                
                ⁢
                d
                ⁢
                
                  
                
                ⁢
                θ
                ⁢
                
                  
                
                ⁢
                d
                ⁢
                
                  
                
                ⁢
                φ
              
            
          
          =
          
            
              
                
                  (
                  
                    
                      2
                      ⁢
                      π
                    
                    -
                    
                      θ
                      ⁢
                      
                        
                      
                      ⁢
                      cb
                    
                  
                  )
                
                ⁢
                
                  θ
                  cb
                
              
              
                π
                2
              
            
            .
          
        
      
    
    
      
        (
        19
        )
      
    
  




Equation (19) may be inverted to determine the angle θcb:

θcb=π(1−√{square root over (ξ1)}), and φcb=2πξ2,  (20)

where ξ1 and ξ2 are uniform random numbers. In some embodiments, subsequent to being sampled in a local frame where the direction from the vertex c 304 to the vertex a 301 is the z-axis, the direction ωcb 314 may be transformed into world coordinates.

Given a uniform random number ξ, a distance tcb 312 along ωcb 314 may be sampled using the inverse CDF of the equiangular PDF (10), and the vertex b 303 may be obtained according to Equation (21):




  
    
      
        
          t
          cb
        
        =
        
          
            t
            
              ca
              ⊥
            
          
          +
          
            
              h
              
                ca
                ⊥
              
            
            ⁢
            
              
            
            ⁢
            
              
                tan
                ⁡
                
                  (
                  
                    
                      ξ
                      ⁡
                      
                        (
                        
                          π
                          -
                          
                            θ
                            cb
                          
                        
                        )
                      
                    
                    +
                    
                      θ
                      cb
                    
                    -
                    
                      π
                      2
                    
                  
                  )
                
              
              .
            
          
        
      
    
    
      
        (
        21
        )
      
    
  




FIG. 4 illustrates an exemplary process of bidirectional factorization of the joint PDF. In one embodiment, factorization is bidirectional where the vertices are sampled from the opposite directions. To sample the vertices b 403 and c 404, a direction ωab 415 from the vertex a 401 may be first sampled, a distance tab 414 may be subsequently sampled to obtain the vertex b 403, and finally a distance tdc 413 is sampled from the vertex d 402 along the direction ωdc 411 to obtain the vertex c 404. Because the vertex b 403 is sampled as a distance and direction from the vertex a 401, the joint PDF may be measured according to Equation (22):

p(b,tdc|Ξ)=p(tab,ωab,tdc|Ξ)G(a,b).  (22)

The joint PDF may be factorized into a product of three conditional PDFs, corresponding to sampling ωab 415 first, tab 414 thereafter, and tdc 413 finally as such:

p(ωab,tab,tdc|Ξ)=p(ωab|Ξ)  (23)

p(tab|ωab,Ξ)  (24)

p(tdc|ωab,tab,Ξ)  (25)

In various embodiments, to handle anisotropic scattering, a table may be constructed to store tabulated PDFs for a discrete set of positions and directions. In one embodiment, a table may tabulate PDFs of Equation (3) using both the unidirectional and the bidirectional factorizations. A circularly symmetric 1-dimensional (1D) phase function, that depends only on the deflection angle between the incident and outgoing directions, may be assumed. In one embodiment where isotropic scattering is processed, the phase function is ρ=1⁄4π. For a medium with a given phase function, an entire family of PDFs exist and may be determined for the geometric configuration of each sampling event. For example, given a line (c,ωcb) there is in general a different 1D PDF along that line for every possible relative location of the vertex a and incident direction ωla. Various embodiments may construct the table to hold tabulated line PDFs for a discrete set of positions a and directions ωla.
In some embodiments, a canonical coordinate system is designed to reduce the dimensionality of tables and the construction time. In some embodiments, the PDF domain may be warped via a suitable reparameterization that analytically eliminates tabulation variations.
In some embodiments where unidirectional factorization is performed, the factors given in Equations (4)-(6) are tabulated for the joint PDF such that the phase functions are taken into account according to Equation (26):

p(tcb,ωcb,tdc|Ξ)=CΞG(a,b)ρ(a)ρ(b)ρ(c).  (26)

FIGS. 5A-5C illustrate canonical coordinate systems for tabulating the conditional PDFs in unidirectional factorization of the joint PDF, such as the unidirectional factorization (4)-(6) of the joint PDF (2) for the case of anisotropic scattering. In various embodiments, a table indexed by various table parameters (e.g., the directions ωla 501 and ωdc 503, and the angle θdc 502) may be constructed for each configuration received. Each table may store tabulated PDFs that are used for making the corresponding sampling decisions, such as those illustrated in FIGS. 3B-D. FIG. 5A illustrates a line tabulation for double scattering; FIG. 5B illustrates a spherical tabulation; and FIG. 5C illustrates a line tabulation for single scattering.
The PDF p(tcb|ωcb,tdc,Ξ) is the anisotropic generalization of the PDF defined in Equation (8), as illustrated in FIG. 3D. FIG. 5C illustrates the canonical coordinate system used for tabulation of the PDF p(tcb|ωcb,tdc,Ξ). The PDF p(tcb|ωcb,tdc,Ξ) may be tabulated by precomputing accurate approximations of the PDFs once and storing them in a compact table. The table may be used to sample a distance along any given ray. This configuration may be parameterized by (a,c,ωla,ωcb), which may be expressed using two angles representing ωla 501 in a canonical coordinate system. The entire family of PDFs may be precomputed into a compact 2D table of 1D PDFs. As illustrated in FIG. 5C, given a line (c,ωcb) and the vertex a 511, the distance between the line and the vertex is scaled to one. The origin is placed at the vertex a 511, the z-axis is aligned with the line (c,ωcb), and the x-axis lies in the same plane. The table may be indexed by the direction vector ωla 501. Each entry in the table may be a PDF p(u) over the signed distance u along the line, measured from the projection of the vertex a 511 onto the line. The infinite line may be mapped to a finite angular domain from the x-axis with θ=arc cotu. Each entry in the table may be a piecewise-linear approximation of Equation (27):




  
    
      
        
          p
          ⁡
          
            (
            
              θ
              ⁡
              
                (
                u
                )
              
            
            )
          
        
        =
        
          
            
              p
              ⁡
              
                (
                u
                )
              
            
            |
            
              
                d
                u
              
              
                d
                θ
              
            
            |
          
          =
          
            
              
                p
                ⁡
                
                  (
                  u
                  )
                
              
              ⁢
              
                1
                
                  G
                  ⁡
                  
                    (
                    
                      a
                      ,
                      
                        b
                        ⁡
                        
                          (
                          u
                          )
                        
                      
                    
                    )
                  
                
              
            
            ∝
            
              
                ρ
                ⁡
                
                  (
                  a
                  )
                
              
              ⁢
              
                
                  ρ
                  ⁡
                  
                    (
                    
                      b
                      ⁡
                      
                        (
                        u
                        )
                      
                    
                    )
                  
                
                .
              
            
          
        
      
    
    
      
        (
        27
        )
      
    
  




The entire domain of θε[0;π], may be tabulated by employing adaptive refinement to improve accuracy. The tabulation is constant if the scattering is isotropic. When scattering at the vertex a 511 is isotropic, the entire 2D table reduces to a single 1D distribution.
For any given ray (c,ωcb), the vertex a 511, and the direction ωla 501, subsequent to constructing the coordinate system, the table may be indexed with the canonical spherical coordinates of ωla 501. An angle θb 515 may be drawn from the retrieved tabulated PDF and constrained to the interval θbε[0; arc cot uC], and transformed to a canonical distance ub=cot θb to obtain the desired scattering distance along the ray tcb=uc+ub. The PDF may be transformed from the angular measure to the Euclidean length measure according to Equation (28):




  
    
      
        
          
            p
            ⁡
            
              (
              
                u
                b
              
              )
            
          
          =
          
            
              
                p
                ⁡
                
                  (
                  
                    θ
                    b
                  
                  )
                
              
              |
              
                
                  d
                  
                    θ
                    b
                  
                
                
                  d
                  
                    u
                    b
                  
                
              
              |
            
            =
            
              
                
                  p
                  ⁡
                  
                    (
                    
                      θ
                      b
                    
                    )
                  
                
                ⁡
                
                  [
                  
                    G
                    ⁡
                    
                      (
                      
                        a
                        ,
                        b
                      
                      )
                    
                  
                  ]
                
              
              ⁢
              
                h
                
                  ca
                  ⊥
                
              
            
          
        
        ,
      
    
    
      
        (
        28
        )
      
    
  




where hca⊥ is the distance between the vertex a 511 and line (c,ωcb).

The spherical distribution, p(ωcb|tdc,Ξ), is used to sample the scattering direction ωcb 516 at the vertex c 513. The spherical distribution p(ωcb|tdc,Ξ) is the anisotropic variant of the PDF defined in Equation (11). The Equations (29)-(30) may be tabulated:




  
    
      
        
          
            p
            ⁡
            
              (
              
                
                  
                    ω
                    cb
                  
                  |
                  
                    t
                    cb
                  
                
                ,
                Ξ
              
              )
            
          
          ∝
          
            
              ∫
              0
              ∞
            
            ⁢
            
              
                p
                ⁡
                
                  (
                  
                    
                      t
                      dc
                    
                    ,
                    
                      ω
                      cb
                    
                    ,
                    
                      
                        t
                        cb
                      
                      |
                      Ξ
                    
                  
                  )
                
              
              ⁢
              
                dt
                cb
              
            
          
        
        ,
      
    
    
      
        (
        29
        )
      
    
  
  
    
      
        
          ∝
          
            
              p
              ⁡
              
                (
                c
                )
              
            
            ⁢
            
              
                
                  
                    ∫
                    0
                    ∞
                  
                  ⁢
                  
                    
                      G
                      ⁡
                      
                        (
                        
                          a
                          ,
                          b
                        
                        )
                      
                    
                    ⁢
                    
                      ρ
                      ⁡
                      
                        (
                        a
                        )
                      
                    
                    ⁢
                    
                      ρ
                      ⁡
                      
                        (
                        b
                        )
                      
                    
                    ⁢
                    
                      dt
                      cb
                    
                  
                
                }
              
              
                P
                ⁡
                
                  (
                  
                    ω
                    cb
                  
                  )
                
              
            
          
        
        ,
      
    
    
      
        (
        30
        )
      
    
  




where ρ(c) is in front of the integral, as it does not depend on the distance tcb. The integral P(ωcb) is the normalization of a PDF entry in the previous tabulation for p(tcb|ωcb,tdc,Ξ), and can be looked up without being computed. The directional distribution is proportional to the product of ρ(c)P(ωcb)

FIG. 5B illustrates the canonical coordinate system used for the tabulation of the spherical distribution. The origin is at the vertex c 513, the z-axis is the direction from the vertex c 513 to the vertex a 511, the x-axis is coplanar with the z-axis and the direction ωdc 503. The PDF family (30) may have three degrees of freedom: 1) the direction ωla 501 and the angle θdc 502 of ωdc 503 from the z-axis. In one embodiment, ρ(c) and P(ωcb) are tabulated separately and sampled from their product. A 2D table of spherical PDFs for P(ωcb) may be constructed, indexed by the direction ωla 501, where for every tabulated direction ωcb, P(ωcb) is evaluated by looking up the corresponding PDF normalization from the p(tcb|ωcb,tdc,Ξ) table. The single-scattered incident radiance filed (omitting transmittance) from the vertex a 511 at the vertex c 513, for a number of lobe orientations at the vertex a 511. The PDFs in the table are stored as fitted mixtures of von Mises Fischer (vMF) distributions.
The domain may be warped according to ωu,v=ω(π(1−√{square root over (u)}),2πv), and the PDFs stored are:




  
    
      
        
          p
          ⁡
          
            (
            
              ω
              
                u
                ,
                ν
              
            
            )
          
        
        =
        
          
            
              p
              ⁡
              
                (
                ω
                )
              
            
            |
            
              
                d
                ω
              
              
                d
                
                  ω
                  
                    u
                    ,
                    ν
                  
                
              
            
            |
          
          =
          
            
              p
              ⁡
              
                (
                ω
                )
              
            
            ⁢
            sin
            ⁢
            
              
            
            ⁢
            
              
                θ
                dc
              
              .
            
          
        
      
    
    
      
        (
        31
        )
      
    
  




Subsequently, (u,v) is sampled with PDF p(u,v), which yields ωcb=ωu,v, using the transformation. The PDF of the sampled direction is:




  
    
      
        
          p
          ⁡
          
            (
            
              ω
              cb
            
            )
          
        
        =
        
          
            
              p
              ⁡
              
                (
                
                  u
                  ,
                  ν
                
                )
              
            
            |
            
              
                
                  d
                  u
                
                ⁢
                
                  d
                  ν
                
              
              
                d
                
                  ω
                  cb
                
              
            
            |
          
          =
          
            
              
                p
                ⁡
                
                  (
                  
                    u
                    ,
                    ν
                  
                  )
                
              
              ⁡
              
                [
                
                  
                    π
                    -
                    
                      θ
                      cb
                    
                  
                  
                    
                      π
                      3
                    
                    ⁢
                    
                      
                    
                    ⁢
                    sin
                    ⁢
                    
                      
                    
                    ⁢
                    
                      θ
                      cb
                    
                  
                
                ]
              
            
            .
          
        
      
    
    
      
        (
        32
        )
      
    
  




In one embodiment, when scattering at the vertex a 511 is isotropic, e.g., a point light, the PDF family (30) has only one degree of freedom, which is the angle θdc 502. The entire family may be stored in a compact 1D table of 2D PDFs, for a set of angles θdc, without the need for vMF fitting and product sampling.
The PDF p(tdc|Ξ) may be used to sample a distance along the ray (d,ωdc), and is the anisotropic variant of the PDF defined in Equations (12) and (16), and may be represented as Equation (33):

p(tdc|Ξ)∝∫s2∫0∞p(tdc,ωcb,tcb|Ξ)dtcbωcb  (33)

∝∫s2p(ωcb|tdc,Ξ)dωcb.  (34)

In various embodiments, the value of this PDF may be obtained by looking up in the corresponding PDF normalizations from the table for ωcb.

FIG. 5A illustrates the geometric configuration for this family of PDFs, is identical to the one for tcb, and the same coordinate system illustrated in FIG. 5C may be used. Variations due to the geometry may be eliminated by reparameterizing the tabulation domain using a different transformation: v=a sin hu. The stored PDFs are:




  
    
      
        
          
            p
            ⁡
            
              (
              
                ν
                ⁡
                
                  (
                  u
                  )
                
              
              )
            
          
          =
          
            
              
                p
                ⁡
                
                  (
                  u
                  )
                
              
              |
              
                
                  d
                  u
                
                
                  d
                  ν
                
              
              |
            
            =
            
              
                
                  p
                  ⁡
                  
                    (
                    u
                    )
                  
                
                ⁡
                
                  [
                  
                    1
                    
                      
                        1
                        +
                        
                          u
                          2
                        
                      
                    
                  
                  ]
                
              
              =
              
                
                  p
                  ⁡
                  
                    (
                    u
                    )
                  
                
                ⁢
                
                  t
                  a
                
              
            
          
        
        ,
      
    
    
      
        (
        35
        )
      
    
  




where ta is the distance between the corresponding point and the vertex a 501.

In various embodiments, sampling a distance tdc=−ud+uc along a ray (d,ωdc) proceeds analogously to tcb. The canonical coordinate system may be constructed and the distribution corresponding to ωla may be retrieved. vc may be sampled from the corresponding tabulated PDF and constrained to the interval vcε[0;a sin hud], and uc=sin h vc is computed. The PDF of the sampled distance is:




  
    
      
        
          p
          ⁡
          
            (
            
              u
              c
            
            )
          
        
        =
        
          
            
              p
              ⁡
              
                (
                
                  ν
                  c
                
                )
              
            
            |
            
              
                d
                
                  ν
                  c
                
              
              
                d
                
                  u
                  c
                
              
            
            |
          
          =
          
            
              
                p
                ⁡
                
                  (
                  
                    ν
                    c
                  
                  )
                
              
              ⁡
              
                [
                
                  1
                  
                    t
                    ca
                  
                
                ]
              
            
            .
          
        
      
    
    
      
        (
        36
        )
      
    
  




In some embodiments where bidirectional factorization is performed, the factors given in Equations (23)-(25) are tabulated for the joint PDF where the phase functions are also taken into account:

p(ωab,tab,tdc|Ξ)=CΞG(b,c)ρ(a)ρ(b)ρ(c)  (37)

FIGS. 6A-6C illustrate canonical coordinate systems for tabulating the conditional PDFs in a bidirectional factorization of the joint PDF, such as the bidirectional factorization (23)-(25) of the joint PDF (2) for the case of anisotropic scattering. In various embodiments, a table indexed by various table parameters (e.g., the directions ωla 601 and ωab 604, the vertex d 603, the distance ud 602, and the angle θdc 605) may be constructed for each configuration. Each table may store tabulated PDFs that are used for sampling distances or directions. FIG. 6A illustrates a spherical tabulation; FIG. 6B illustrates a line tabulation for double scattering; and FIG. 6C illustrates a line tabulation for single scattering.
The PDF p(tab|ωab,Ξ) may be used to sample a distance along a ray (a,ωab), given another ray (d,ωdc). In various embodiments, the PDF p(tab|ωab,Ξ) may be defined as:




  
    
      
        
          p
          ⁡
          
            (
            
              
                
                  t
                  ab
                
                |
                
                  ω
                  ab
                
              
              ,
              Ξ
            
            )
          
        
        =
        
          
            
              
                p
                ⁡
                
                  (
                  
                    
                      ω
                      ab
                    
                    ,
                    
                      t
                      ab
                    
                    ,
                    Ξ
                  
                  )
                
              
              
                p
                ⁡
                
                  (
                  
                    
                      ω
                      ab
                    
                    ,
                    Ξ
                  
                  )
                
              
            
            ∝
            
              p
              ⁡
              
                (
                
                  
                    ω
                    ab
                  
                  ,
                  
                    t
                    ab
                  
                  ,
                  Ξ
                
                )
              
            
          
          =
          
            
              ∫
              
                
                  G
                  ⁡
                  
                    (
                    
                      b
                      ,
                      c
                    
                    )
                  
                
                ⁢
                
                  ρ
                  ⁡
                  
                    (
                    a
                    )
                  
                
                ⁢
                
                  ρ
                  ⁡
                  
                    (
                    b
                    )
                  
                
                ⁢
                
                  ρ
                  ⁡
                  
                    (
                    c
                    )
                  
                
                ⁢
                
                  dt
                  dc
                
              
            
            ∝
            
              ∫
              
                
                  G
                  ⁡
                  
                    (
                    
                      b
                      ,
                      c
                    
                    )
                  
                
                ⁢
                
                  ρ
                  ⁡
                  
                    (
                    b
                    )
                  
                
                ⁢
                
                  ρ
                  ⁡
                  
                    (
                    c
                    )
                  
                
                ⁢
                
                  
                    dt
                    dc
                  
                  .
                
              
            
          
        
      
    
    
      
        (
        38
        )
      
    
  




Anisotropic scattering at the vertex b 612 is taken into account and the semi-infinite extent of line (d,ωdc) is considered.

FIG. 6B illustrates the corresponding geometric configuration for table construction of the PDF p(tab|ωab,Ξ). The canonical coordinate system is constructed such that the x-axis is aligned with the shortest connecting line between (a,ωab) and (d,ωdc) and the origin o 613 is set to the end of the connecting line on (a,ωab). The z-axis may be aligned with the direction ωdc 614. An entire family of these PDFs exist and may be parameterized by (a,ωab) and (d,ωdc) half-lines. The symmetries in the geometry configuration and scale-invariance allow the family of PDFs to be parameterized by a few parameters including the angle θab 605 between the direction ωab 604 and the direction ωdc 614. The shape of the PDFs may depend on the actual location of the vertex d 603 along the (d,ωdc) line. The distance ud 602 from the projection of the origin onto (d,ωdc) may be an additional parameter to construct a 2D table of 1D PDFs. For every combination of the angle θab 605 and the distance ud 602, the associated PDF assigns probability density to distance u from the origin on the infinite line (a,ωab). The piecewise-linear approximation of this PDF may be constructed by looking up the integral (38), to which the constructed PDF is proportional, from the previously constructed table for the PDF p(tdc|ωab,tab,Ξ).
The PDF p(u) in the canonical coordinate system may be defined over an entire infinite (a,ωab) line. The PDF p(u) may be mapped to a finite domain by parameterize the position u using v=a sin hu to allow tabulation. The PDFs which is stored in the table are:




  
    
      
        
          
            p
            ⁡
            
              (
              
                ν
                ⁡
                
                  (
                  u
                  )
                
              
              )
            
          
          =
          
            
              
                p
                ⁡
                
                  (
                  u
                  )
                
              
              |
              
                
                  d
                  u
                
                
                  d
                  ν
                
              
              |
            
            =
            
              
                
                  p
                  ⁡
                  
                    (
                    u
                    )
                  
                
                ⁡
                
                  [
                  
                    1
                    
                      
                        1
                        +
                        
                          u
                          2
                        
                      
                    
                  
                  ]
                
              
              =
              
                
                  p
                  ⁡
                  
                    (
                    u
                    )
                  
                
                ⁢
                
                  t
                  
                    o
                    ⊥
                  
                
              
            
          
        
        ,
      
    
    
      
        (
        39
        )
      
    
  




which may be constant for isotropic phase functions ρ(c) and ρ(b), and an infinite ray (d,ωdc), where to⊥ is the distance between the corresponding point and o⊥. Any possible variation of the PDF may be solely due to the anisotropy of the phase function and the position of the vertex d 603 along the direction ωdc 614.

Given two rays (d,ωdc) and (a,ωab), the canonical coordinate system may be constructed and the distribution corresponding to the direction ωla 601 may be retrieved for sampling. vb may be sampled from the corresponding tabulated PDF, constrained to the interval vbε[0;a sin h ua], and ub=sin h vb is computed. The PDF of the sampled distance tab=ua+ub is:




  
    
      
        
          p
          ⁡
          
            (
            
              u
              b
            
            )
          
        
        =
        
          
            p
            ⁡
            
              (
              
                ν
                b
              
              )
            
          
          |
          
            
              d
              
                ν
                b
              
            
            
              d
              
                u
                b
              
            
          
          |
          
            
              
                p
                ⁡
                
                  (
                  
                    ν
                    b
                  
                  )
                
              
              ⁡
              
                [
                
                  1
                  
                    t
                    
                      bo
                      ⊥
                    
                  
                
                ]
              
            
            .
          
        
      
    
    
      
        (
        40
        )
      
    
  




The PDF p(ωab|Ξ) is used to sample a direction ωab at the vertex a 611, and may be defined as:




  
    
      
        
          
            p
            ⁡
            
              (
              
                
                  ω
                  ab
                
                |
                Ξ
              
              )
            
          
          =
          
            
              
                
                  p
                  ⁡
                  
                    (
                    
                      
                        ω
                        ab
                      
                      ,
                      Ξ
                    
                    )
                  
                
                
                  p
                  ⁡
                  
                    (
                    Ξ
                    )
                  
                
              
              ∝
              
                p
                ⁡
                
                  (
                  
                    
                      ω
                      ab
                    
                    ,
                    Ξ
                  
                  )
                
              
            
            =
            
              
                ∫
                
                  
                    p
                    ⁡
                    
                      (
                      
                        
                          ω
                          ab
                        
                        ,
                        
                          
                            t
                            ab
                          
                          |
                          Ξ
                        
                      
                      )
                    
                  
                  ⁢
                  
                    dt
                    ab
                  
                
              
              ∝
              
                
                  p
                  ⁡
                  
                    (
                    a
                    )
                  
                
                ⁢
                
                  
                    
                      ∫
                      
                        
                          G
                          ⁡
                          
                            (
                            
                              b
                              ,
                              c
                            
                            )
                          
                        
                        ⁢
                        
                          ρ
                          ⁡
                          
                            (
                            b
                            )
                          
                        
                        ⁢
                        
                          ρ
                          ⁡
                          
                            (
                            c
                            )
                          
                        
                        ⁢
                        
                          dt
                          ab
                        
                      
                    
                    }
                  
                  
                    P
                    ⁡
                    
                      (
                      
                        ω
                        ab
                      
                      )
                    
                  
                
              
            
          
        
        ,
      
    
    
      
        (
        41
        )
      
    
  




where ρ(a) is in front of the integral, as it does not depend on the distance tab. The integral P(ωab) is the normalization of a corresponding PDF in the table constructed for the PDF p(tab|ωab,Ξ), and can be readily looked up. The desired distribution is proportional to the product ρ(a)P(ωab)

FIG. 6C illustrates the canonical coordinate system used for the tabulation of p(ωab|Ξ). The origin is at the vertex a, the z-axis is aligned with the direction ωdc 614, and the x-axis lies in the same plane. The PDF family (41) may be spanned by the direction ωla 601 and the position of the vertex d 603 along the direction ωdc 614, given by the distance ud 602, as illustrated. A 1D table of tabulated 2D PDFs may be constructed and indexed by the distance ud 602. The spherical distributions in the PDF family have a singularity around the z-axis, which is due to the sin−1 θ factor in the analytic inverse CDF. This singularity may be eliminated by warping the spherical domain using the transformation. The PDFs that are stored are:




  
    
      
        
          p
          ⁡
          
            (
            
              ω
              
                u
                ,
                ν
              
            
            )
          
        
        =
        
          
            
              p
              ⁡
              
                (
                ω
                )
              
            
            |
            
              
                d
                ω
              
              
                d
                
                  ω
                  
                    u
                    ,
                    ν
                  
                
              
            
            |
          
          =
          
            
              p
              ⁡
              
                (
                ω
                )
              
            
            ⁢
            sin
            ⁢
            
              
            
            ⁢
            
              
                θ
                ab
              
              .
            
          
        
      
    
    
      
        (
        42
        )
      
    
  




Subsequently, the given configuration may be transformed into the canonical coordinate system and a PDF may be retrieved from the table and indexed with the distance ud 602. (u,v) may be sampled with PDF p(u,v), which yields ωcb=ωu,v using the transformation. The PDF of the sampled direction is:




  
    
      
        
          p
          ⁡
          
            (
            
              ω
              ab
            
            )
          
        
        =
        
          
            
              p
              ⁡
              
                (
                
                  u
                  ,
                  ν
                
                )
              
            
            |
            
              
                
                  d
                  u
                
                ⁢
                
                  d
                  ν
                
              
              
                d
                
                  ω
                  ab
                
              
            
            |
          
          =
          
            
              
                p
                ⁡
                
                  (
                  
                    u
                    ,
                    ν
                  
                  )
                
              
              ⁡
              
                [
                
                  1
                  
                    2
                    ⁢
                    
                      π
                      2
                    
                    ⁢
                    
                      
                    
                    ⁢
                    sin
                    ⁢
                    
                      
                    
                    ⁢
                    
                      θ
                      ab
                    
                  
                
                ]
              
            
            .
          
        
      
    
    
      
        (
        43
        )
      
    
  




As used herein, the term module might describe a given unit of functionality that can be performed in accordance with one or more embodiments of the present application. As used herein, a module might be implemented utilizing any form of hardware, software, or a combination thereof. For example, one or more processors, controllers, ASICs, PLAs, PALs, CPLDs, FPGAs, logical components, software routines or other mechanisms might be implemented to make up a module. In implementation, the various modules described herein might be implemented as discrete modules or the functions and features described can be shared in part or in total among one or more modules. In other words, as would be apparent to one of ordinary skill in the art after reading this description, the various features and functionality described herein may be implemented in any given application and can be implemented in one or more separate or shared modules in various combinations and permutations. Even though various features or elements of functionality may be individually described or claimed as separate modules, one of ordinary skill in the art will understand that these features and functionality can be shared among one or more common software and hardware elements, and such description shall not require or imply that separate hardware or software components are used to implement such features or functionality.
Where components or modules of the application are implemented in whole or in part using software, in one embodiment, these software elements can be implemented to operate with a computing or processing module capable of carrying out the functionality described with respect thereto. One such example computing module is shown in FIG. 7. Various embodiments are described in terms of this example-computing module 700. After reading this description, it will become apparent to a person skilled in the relevant art how to implement the application using other computing modules or architectures.
Referring now to FIG. 7, computing module 700 may represent, for example, computing or processing capabilities found within desktop, laptop and notebook computers; hand-held computing devices (PDA's, smart phones, cell phones, palmtops, etc.); mainframes, supercomputers, workstations or servers; or any other type of special-purpose or general-purpose computing devices as may be desirable or appropriate for a given application or environment. Computing module 700 might also represent computing capabilities embedded within or otherwise available to a given device. For example, a computing module might be found in other electronic devices such as, for example, digital cameras, navigation systems, cellular telephones, portable computing devices, modems, routers, WAPs, terminals and other electronic devices that might include some form of processing capability.
Computing module 700 might include, for example, one or more processors, controllers, control modules, or other processing devices, such as a processor 704. Processor 704 might be implemented using a general-purpose or special-purpose processing engine such as, for example, a microprocessor, controller, or other control logic. In the illustrated example, processor 704 is connected to a bus 702, although any communication medium can be used to facilitate interaction with other components of computing module 700 or to communicate externally.
Computing module 700 might also include one or more memory modules, simply referred to herein as main memory 708. For example, preferably random access memory (RAM) or other dynamic memory, might be used for storing information and instructions to be executed by processor 704. Main memory 708 might also be used for storing temporary variables or other intermediate information during execution of instructions to be executed by processor 704. Computing module 700 might likewise include a read only memory (“ROM”) or other static storage device coupled to bus 702 for storing static information and instructions for processor 704.
The computing module 700 might also include one or more various forms of information storage mechanism 710, which might include, for example, a media drive 712 and a storage unit interface 720. The media drive 712 might include a drive or other mechanism to support fixed or removable storage media 714. For example, a hard disk drive, a floppy disk drive, a magnetic tape drive, an optical disk drive, a CD or DVD drive (R or RW), or other removable or fixed media drive might be provided. Accordingly, storage media 714 might include, for example, a hard disk, a floppy disk, magnetic tape, cartridge, optical disk, a CD or DVD, or other fixed or removable medium that is read by, written to or accessed by media drive 712. As these examples illustrate, the storage media 714 can include a computer usable storage medium having stored therein computer software or data.
In alternative embodiments, information storage mechanism 710 might include other similar instrumentalities for allowing computer programs or other instructions or data to be loaded into computing module 700. Such instrumentalities might include, for example, a fixed or removable storage unit 722 and an interface 720. Examples of such storage units 722 and interfaces 720 can include a program cartridge and cartridge interface, a removable memory (for example, a flash memory or other removable memory module) and memory slot, a PCMCIA slot and card, and other fixed or removable storage units 722 and interfaces 720 that allow software and data to be transferred from the storage unit 722 to computing module 700.
Computing module 700 might also include a communications interface 724. Communications interface 724 might be used to allow software and data to be transferred between computing module 700 and external devices. Examples of communications interface 724 might include a modem or softmodem, a network interface (such as an Ethernet, network interface card, WiMedia, IEEE 802.XX or other interface), a communications port (such as for example, a USB port, IR port, RS232 port Bluetooth® interface, or other port), or other communications interface. Software and data transferred via communications interface 724 might typically be carried on signals, which can be electronic, electromagnetic (which includes optical) or other signals capable of being exchanged by a given communications interface 724. These signals might be provided to communications interface 724 via a channel 728. This channel 728 might carry signals and might be implemented using a wired or wireless communication medium. Some examples of a channel might include a phone line, a cellular link, an RF link, an optical link, a network interface, a local or wide area network, and other wired or wireless communications channels.
In this document, the terms “computer program medium” and “computer usable medium” are used to generally refer to media such as, for example, memory 708, storage unit 720, media 714, and channel 728. These and other various forms of computer program media or computer usable media may be involved in carrying one or more sequences of one or more instructions to a processing device for execution. Such instructions embodied on the medium, are generally referred to as “computer program code” or a “computer program product” (which may be grouped in the form of computer programs or other groupings). When executed, such instructions might enable the computing module 700 to perform features or functions of the present application as discussed herein.
While various embodiments of the present application have been described above, it should be understood that they have been presented by way of example only, and not of limitation. Likewise, the various diagrams may depict an example architectural or other configuration for the application, which is done to aid in understanding the features and functionality that can be included in the application. The application is not restricted to the illustrated example architectures or configurations, but the desired features can be implemented using a variety of alternative architectures and configurations. Indeed, it will be apparent to one of skill in the art how alternative functional, logical or physical partitioning and configurations can be implemented to implement the desired features of the present application. Also, a multitude of different constituent module names other than those depicted herein can be applied to the various partitions. Additionally, with regard to flow diagrams, operational descriptions and method claims, the order in which the steps are presented herein shall not mandate that various embodiments be implemented to perform the recited functionality in the same order unless the context dictates otherwise.
Although the application is described above in terms of various exemplary embodiments and implementations, it should be understood that the various features, aspects and functionality described in one or more of the individual embodiments are not limited in their applicability to the particular embodiment with which they are described, but instead can be applied, alone or in various combinations, to one or more of the other embodiments of the application, whether or not such embodiments are described and whether or not such features are presented as being a part of a described embodiment. Thus, the breadth and scope of the present application should not be limited by any of the above-described exemplary embodiments.
Terms and phrases used in this document, and variations thereof, unless otherwise expressly stated, should be construed as open ended as opposed to limiting. As examples of the foregoing: the term “including” should be read as meaning “including, without limitation” or the like; the term “example” is used to provide exemplary instances of the item in discussion, not an exhaustive or limiting list thereof; the terms “a” or “an” should be read as meaning “at least one,” “one or more” or the like; and adjectives such as “conventional,” “traditional,” “normal,” “standard,” “known” and terms of similar meaning should not be construed as limiting the item described to a given time period or to an item available as of a given time, but instead should be read to encompass conventional, traditional, normal, or standard technologies that may be available or known now or at any time in the future. Likewise, where this document refers to technologies that would be apparent or known to one of ordinary skill in the art, such technologies encompass those apparent or known to the skilled artisan now or at any time in the future.
The presence of broadening words and phrases such as “one or more,” “at least,” “but not limited to” or other like phrases in some instances shall not be read to mean that the narrower case is intended or required in instances where such broadening phrases may be absent. The use of the term “module” does not imply that the components or functionality described or claimed as part of the module are all configured in a common package. Indeed, any or all of the various components of a module, whether control logic or other components, can be combined in a single package or separately maintained and can further be distributed in multiple groupings or packages or across multiple locations.
Additionally, the various embodiments set forth herein are described in terms of exemplary block diagrams, flow charts and other illustrations. As will become apparent to one of ordinary skill in the art after reading this document, the illustrated embodiments and their various alternatives can be implemented without confinement to the illustrated examples. For example, block diagrams and their accompanying description should not be construed as mandating a particular architecture or configuration.

## Claims

1. A computer-implemented method of sampling light paths connecting a light source subpath to a light receiver subpath, comprising:
receiving an input configuration, the input configuration comprises a first endpoint, a first direction, a second endpoint, and a second direction;
sampling a set of vertices to determine a set of subpath segments according to a sampling function defined as a product of a set of geometry terms and a set of phase functions;
creating a subpath comprising the set of subpath segments to connect the light source subpath with the light receiver subpath;
wherein the sampling function comprises a joint probability density function, and the step of sampling a set of vertices comprises factorizing the joint probability density function into a product of a set of conditional probability density functions; and
each of the conditional probability density function corresponds to a distance sampling and a direction sampling.

2. The computer-implemented method of claim 1, wherein the step of sampling the set of vertices comprises deriving the set of conditional probability density functions and a set of sampling routines, each sampling routine of the set of sampling routines corresponding to a conditional probability density function of the set of conditional probability density functions.

3. The computer-implemented method of claim 2, wherein the step of sampling the set of vertices comprises:
obtaining a first vertex by sampling a first distance along the second direction from the second endpoint; and
obtaining a second vertex by sampling a third direction from the first vertex and sampling a second distance along the third direction.

4. The computer-implemented method of claim 2, wherein each of the set of conditional probability density functions is configured for isotropic scattering.

5. The computer-implemented method of claim 1, wherein the set of conditional probability density functions are obtained by performing a unidirectional factorization such that the set of vertices are sampled from the same direction along a path starting from a second vertex.

6. The computer-implemented method of claim 5, wherein each sampling routine is derived from using an inverse cumulative distribution function of the each conditional probability density function.

7. The computer-implemented method of claim 6, wherein the step of sampling the set of vertices comprises:
obtaining a first vertex by sampling a third direction from the first endpoint and sampling a first distance along the third direction; and
obtaining a second vertex by sampling a second distance along the second direction from the second endpoint.

8. The computer-implemented method of claim 6, wherein each of the set of conditional probability density functions is configured for anisotropic scattering.

9. The computer-implemented method of claim 8, wherein the step of sampling the set of vertices comprise constructing a set of tables comprising a set of tabulated line probability density functions for a set of positions and directions for each of the set of conditional probability density functions.

10. The computer-implemented method of claim 8, wherein the step of constructing the set of tables comprises:
creating a first tabulation for a first PDF for by sampling a third direction from the first endpoint;
creating a second tabulation for a second PDF for a first distance along the third direction from the first endpoint to obtain a first vertex; and
creating a third tabulation for a third PDF for sampling a second distance along the second direction from the second endpoint.

11. The computer-implemented method of claim 1, wherein the set of conditional probability density functions are obtained by performing a bidirectional factorization such that the set of vertices are sampled from opposite directions.

12. A system of sampling light paths connecting a light source subpath to a light receiver subpath, comprising:
non-transitory memory storing a set of instructions; and
a processor coupled to the non-transitory memory, wherein the set of instructions are configured to cause the processor to perform:
receiving an input configuration, the input configuration comprises a first endpoint, a first direction, a second endpoint, and a second direction;
sampling a set of vertices to determine a set of subpath segments according to a sampling function defined as a product of a set of geometry terms and a set of phase functions;
creating a subpath comprising the set of subpath segments to connect the light source subpath with the light receiver subpath;
wherein the sampling function comprises a joint probability density function, and the set of instructions are configured to cause the processor to factorize the joint probability density function into a product of a set of conditional probability density functions when performing the step of sampling a set of vertices.

13. The system of claim 12, wherein the set of conditional probability density functions are obtained by performing a unidirectional factorization such that the set of vertices are sampled from the same direction along a path starting from a second endpoint.

14. The system of claim 13, wherein each of the set of conditional probability density functions is configured for isotropic scattering.

15. The system of claim 14, wherein the each sampling routine is derived from using an inverse cumulative distribution function of the each conditional probability density function.

16. The system of claim 15, wherein the set of instructions are configured to cause the processor to:
obtain a first vertex by sampling a third direction from the first endpoint and sampling a first distance along the third direction; and
obtain a second vertex by sampling a second distance along the second direction from the second endpoint, when performing the step of sampling a set of vertices.

17. The system of claim 12, wherein the set of instructions are configured to cause the processor to perform:
obtaining a first vertex by sampling a first distance along the second direction from the second endpoint; and
obtaining a second vertex by sampling a third direction from the first vertex and sampling a second distance along the third direction, when performing the step of sampling a set of vertices.

18. The system of claim 12, wherein the set of conditional probability density functions are obtained by performing a bidirectional factorization such that the set of vertices are sampled from opposite directions.

19. The system of claim 18, wherein each of the set of conditional probability density functions is configured for anisotropic scattering.

20. The system of claim 19, wherein the set of instructions are configured to cause the processor to construct a set of tables comprising a set of tabulated line probability density functions for a set of positions and directions for each of the set of conditional probability density functions, when sampling the set of vertices.

21. The system of claim 19, wherein the set of instructions are configured to cause the processor to:
create a first tabulation for a first PDF for by sampling a third direction from the first endpoint;
create a second tabulation for a second PDF for a first distance along the third direction from the first endpoint to obtain a first vertex; and
create a third tabulation for a third PDF for sampling a second distance along the second direction from the second endpoint, when performing the step of constructing the set of tables.