# US 8,279,220 B1 · System and method for estimating light transport using bidirectional path tracing

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 8,279,220 B1
- Document ID: US8279220B1
- Status: Granted
- Kind: B1
- Application number: 12/475,782
- Filed: 2009-06-01
- Granted: 2012-10-02
- Earliest claimed: 2009-06-01
- Assignees: NVIDIA Corporation
- Inventors: Jacopo Pantaleoni
- Web page: https://patentgrep.com/patent/US8279220B1

## CPC

- G06T 15/50: Lighting effects
- G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL

## Abstract

Systems and methods for estimating light transport between respective points includes selecting a plurality of first sub-paths extending the first point A, and selecting a plurality of second sub-paths extending from a second point B. A plurality of transport paths are constructed, wherein each one of the plurality of the first sub-paths is coupled to a respective one of the plurality of second paths, and wherein each transport path comprises one first sub-path and one second sub-path. Two or more of the transport paths are sampled, and a light transport value for each of the sampled transport paths is calculated to estimate the light transported between first point A and second point B.

## Claims

### Claim 1

A method for estimating the light transported between a first point A and a second point B, the method comprising:
selecting a plurality of first sub-paths extending from a first point A;
selecting a plurality of second sub-paths extending from a second point B;
constructing, utilizing a processor, a plurality of transport paths, wherein each one of the plurality of the first sub-paths is coupled to a respective one of the plurality of the second sub-paths to form one transport path, and wherein each transport path comprises one first sub-path and one second sub-path;
sampling two or more of the plurality of the transport paths to obtain a plurality of sampled transport paths; and
calculating a light transport value for each of the plurality of sampled transport paths to estimate light transported between the first point A and the second point B;
wherein constructing the plurality of transport paths comprises:
constructing a light transport matrix, wherein the plurality of first sub-paths defines respective column indices and the plurality of second sub-paths defines respective row indices, the light transport matrix including an entry Gij defined by a respective column i and a respective row j, whereby the entry Gij comprises a light transport value which describes light transported between the points A and B via a light transport path comprising a combination of a first sub-path corresponding to the column i, and a second sub-path corresponding to the row j;
wherein constructing the light transport matrix comprises:
sorting the plurality of first sub-paths into a plurality of different first sub-path groups, each of the first sub-path groups comprising first sub-paths having a same first path length, and
sorting the plurality of second sub-paths into a plurality of different second sub-path groups, each of the second sub-path groups comprising second sub-paths having a same second path length;
wherein one of the first sub-path groups and one of the second sub-path groups collectively form a sub-matrix within the light transport matrix, each sub-matrix comprising a plurality of column indices and a plurality of row indices, wherein each column index corresponds to a respective first sub-path, and each row index corresponds to a respective second sub-path;
wherein a plurality of sub-matrices form the light transport matrix;
wherein one or more column indices of one or more of the plurality of sub-matrices is ordered, comprising:
selecting one of the plurality of sub-matrices, the selected sub-matrix comprising a plurality of first sub-paths and a plurality of second sub-paths,
selecting a first column index for the selected sub-matrix, and
selecting, from among a predefined number of remaining column indices, a second column index for the selected sub-matrix based upon the first selected column index.

### Claim 2 (depends on 1)

The method of claim 1, wherein selecting the second column index comprises:
(a) selecting a predefined number of r vertices spatially closest to a terminating vertex of a first sub-path representing the first column index;
(b) selecting a plurality of m vertices of the plurality of second sub-paths within the selected sub-matrix;
(c) obtaining a plurality of r transport profiles, each of the r transport profiles describing light transport from one of the r vertices to each of the m vertices;
(d) comparing each of the r transport profiles to a reference transport profile; and
(e) selecting as the second column index, a first sub-path having a vertex corresponding to a transport profile which most closely matches the reference transport profile.

### Claim 3

A method for estimating the light transported between a first point A and a second point B, the method comprising:
selecting a plurality of first sub-paths extending from a first point A;
selecting a plurality of second sub-paths extending from a second point B;
constructing, utilizing a processor, a plurality of transport paths, wherein each one of the plurality of the first sub-paths is coupled to a respective one of the plurality of the second sub-paths to form one transport path, and wherein each transport path comprises one first sub-path and one second sub-path;
sampling two or more of the plurality of the transport paths to obtain a plurality of sampled transport paths; and
calculating a light transport value for each of the plurality of sampled transport paths to estimate light transported between the first point A and the second point B;
wherein constructing the plurality of transport paths comprises:
constructing a light transport matrix, wherein the plurality of first sub-paths defines respective column indices and the plurality of second sub-paths defines respective row indices, the light transport matrix including an entry Gij defined by a respective column i and a respective row j, whereby the entry Gij comprises a light transport value which describes light transported between the points A and B via a light transport path comprising a combination of a first sub-path corresponding to the column i, and a second sub-path corresponding to the row j;
wherein constructing the light transport matrix comprises:
sorting the plurality of first sub-paths into a plurality of different first sub-path groups, each of the first sub-path groups comprising first sub-paths having a same first path length, and
sorting the plurality of second sub-paths into a plurality of different second sub-path groups, each of the second sub-path groups comprising second sub-paths having a same second path length;
wherein one of the first sub-path groups and one of the second sub-path groups collectively form a sub-matrix within the light transport matrix, each sub-matrix comprising a plurality of column indices and a plurality of row indices, wherein each column index corresponds to a respective first sub-path, and each row index corresponds to a respective second sub-path;
wherein a plurality of sub-matrices form the light transport matrix;
wherein one or more row indices of one or more of the plurality of sub-matrices is ordered, comprising:
selecting one of the plurality of sub-matrices, the selected sub-matrix comprising a plurality of first sub-paths and a plurality of second sub-paths,
selecting a first row index for the selected sub-matrix, and
selecting, from among a predefined number of remaining row indices, a second row index for the selected sub-matrix based upon the first selected row index.

### Claim 4 (depends on 3)

The method of claim 3, wherein selecting the second row index comprises:
(a) selecting a predefined number of r vertices spatially closest to a terminating vertex of a second sub-path representing the first row index;
(b) selecting a plurality of m vertices of the plurality of first sub-paths within the selected sub-matrix;
(c) obtaining a plurality of r transport profiles, each of the r transport profiles describing light transport from one of the r vertices to each of the m vertices;
(d) comparing each of the r transport profiles to a reference transport profile; and
(e) selecting as the second row index, a second sub-path having a vertex corresponding to a transport profile which most closely matches the reference transport profile.

### Claim 5

A pixel rendering method for estimating the light transport between a first point A and a second point B, the method comprising:
selecting a plurality of first sub-paths extending from a first point A;
selecting a plurality of second sub-paths extending from a second point B;
constructing, utilizing a processor, a plurality of transport paths, wherein each one of the plurality of the first sub-paths is coupled to a respective one of the plurality of the second sub-paths to form one transport path, and wherein each transport path comprises one first sub-path and one second sub-path;
sampling two or more of the plurality of the transport paths to obtain a plurality of sampled transport paths; and
calculating a light transport value for each of the plurality of sampled transport paths to estimate light transported between the first point A and the second point B;
wherein constructing the plurality of transport paths comprises:
constructing a light transport matrix, wherein the plurality of first sub-paths defines respective column indices and the plurality of second sub-paths defines respective row indices, the light transport matrix including an entry Gij defined by a respective column i and a respective row j, whereby the entry Gij comprises a light transport value which describes light transported between the points A and B via a light transport path comprising a combination of a first sub-path corresponding to the column i, and a second sub-path corresponding to the row j;
wherein constructing the light transport matrix comprises:
sorting the plurality of first sub-paths into a plurality of different first sub-path groups, each of the first sub-path groups comprising first sub-paths having a same first path length, and
sorting the plurality of second sub-paths into a plurality of different second sub-path groups, each of the second sub-path groups comprising second sub-paths having a same second path length;
wherein one of the first sub-path groups and one of the second sub-path groups collectively form a sub-matrix within the light transport matrix, each sub-matrix comprising a plurality of column indices and a plurality of row indices, wherein each column index corresponds to a termination vertex of a respective first sub-path, and each row index corresponds to a termination vertex of a respective second sub-path;
wherein a plurality of sub-matrices form the light transport matrix;
wherein one or more column indices of one or more of the plurality of sub-matrices is ordered, comprising:
selecting one of the plurality of sub-matrices, the selected sub-matrix comprising a plurality of first sub-paths and a plurality of second sub-paths,
selecting a first column index for the selected sub-matrix, and
selecting, from among a predefined number of remaining column indices, a second column index for the selected sub-matrix based upon the first selected column index.

### Claim 6 (depends on 5)

The method of claim 5, wherein selecting the second column index comprises:
(a) selecting a predefined number of r vertices spatially closest to a terminating vertex of a first sub-path representing the first column index;
(b) selecting a plurality of m vertices of the plurality of second sub-paths within the selected sub-matrix;
(c) obtaining a plurality of r transport profiles, each of the r transport profiles describing light transport from one of the r vertices to each of the m vertices;
(d) comparing each of the r transport profiles to a reference transport profile; and
(e) selecting as the second column index, a first sub-path having a vertex corresponding to a transport profile which most closely matches the reference transport profile.

### Claim 7

A pixel rendering method for estimating the light transport between a first point A and a second point B, the method comprising:
selecting a plurality of first sub-paths extending from a first point A;
selecting a plurality of second sub-paths extending from a second point B;
constructing, utilizing a processor, a plurality of transport paths, wherein each one of the plurality of the first sub-paths is coupled to a respective one of the plurality of the second sub-paths to form one transport path, and wherein each transport path comprises one first sub-path and one second sub-path;
sampling two or more of the plurality of the transport paths to obtain a plurality of sampled transport paths; and
calculating a light transport value for each of the plurality of sampled transport paths to estimate light transported between the first point A and the second point B;
wherein constructing the plurality of transport paths comprises:
constructing a light transport matrix, wherein the plurality of first sub-paths defines respective column indices and the plurality of second sub-paths defines respective row indices, the light transport matrix including an entry Gij defined by a respective column i and a respective row j, whereby the entry Gij comprises a light transport value which describes light transported between the points A and B via a light transport path comprising a combination of a first sub-path corresponding to the column i, and a second sub-path corresponding to the row j;
wherein constructing the light transport matrix comprises:
sorting the plurality of first sub-paths into a plurality of different first sub-path groups, each of the first sub-path groups comprising first sub-paths having a same first path length, and
sorting the plurality of second sub-paths into a plurality of different second sub-path groups, each of the second sub-path groups comprising second sub-paths having a same second path length;
wherein one of the first sub-path groups and one of the second sub-path groups collectively form a sub-matrix within the light transport matrix, each sub-matrix comprising a plurality of column indices and a plurality of row indices, wherein each column index corresponds to a termination vertex of a respective first sub-path, and each row index corresponds to a termination vertex of a respective second sub-path;
wherein a plurality of sub-matrices form the light transport matrix;
wherein one or more row indices of one or more of the plurality of sub-matrices is ordered, comprising:
selecting one of the plurality of sub-matrices, the selected sub-matrix comprising a plurality of first sub-paths and a plurality of second sub-paths,
selecting a first row index for the selected sub-matrix, and
selecting, from among a predefined number of remaining row indices, a second row index the selected sub-matrix based upon the first selected row index.

### Claim 8 (depends on 7)

The method of claim 7, wherein selecting the second row index comprises:
(a) selecting a predefined number of r vertices spatially closest to a terminating vertex of a second sub-path representing the first row index;
(b) selecting a plurality of m vertices of the plurality of first sub-paths within the selected sub-matrix;
(c) obtaining a plurality of r transport profiles, each of the r transport profiles describing light transport from one of the r vertices to each of the m vertices;
(d) comparing each of the r transport profiles to a reference transport profile; and
(e) selecting as the second row index, a second sub-path having a vertex corresponding to a transport profile which most closely matches the reference transport profile.

### Claim 9

A system operable to estimate the light transport between a first point A and a second point B, the system including a processor operable to:
select a plurality of first sub-paths extending from a first point A;
select a plurality of second sub-paths extending from a second point B;
construct a plurality of transport paths, wherein each one of the plurality of the first sub-paths is coupled to a respective one of the plurality of the second sub-paths to form one transport path, and wherein each transport path comprises one first sub-path and one second sub-path;
sample two or more of the plurality of transport paths to obtain a plurality of sampled transport paths; and
calculate a light transport value for each of the plurality of sampled transport paths to estimate light transported between the first point A and the second point B;
wherein the processor, in constructing the plurality of transport paths, is operable to:
construct a light transport matrix, wherein the plurality of first sub-paths defines respective column indices and the plurality of second sub-paths defines respective row indices, the light transport matrix including an entry Gij defined by a respective column i and a respective row j, whereby the entry Gij comprises a light transport value which describes light transported between the points A and B via a light transport path comprising a combination of a first sub-path corresponding to the column i, and a second sub-path corresponding to the row j;
wherein the processor, in constructing the light transport matrix, is operable to:
sort the plurality of first sub-paths into a plurality of different first sub-path groups, each of the first sub-path groups comprising first sub-paths having a same first path length, and
sort the plurality of second sub-paths into a plurality of different second sub-path groups, each of the second sub-path groups comprising second sub-paths having a same second path length;
wherein one of the first sub-path groups and one of the second sub-path groups collectively form a sub-matrix within the light transport matrix, each sub-matrix comprising a plurality of column indices and a plurality of row indices, wherein each column index corresponds to a termination vertex of a respective first sub-path, and each row index corresponds to a termination vertex of a respective second sub-path;
wherein a plurality of sub-matrices form the light transport matrix;
wherein the processor is operable to order one or more column indices of one or more of the plurality of sub-matrices, the processor operable to:
select one of the plurality of sub-matrices, the selected sub-matrix comprising a plurality of first sub-paths and a plurality of second sub-paths,
select a first column index for the selected sub-matrix, and
select, from among a predefined number of remaining column indices, a second column index for the selected sub-matrix based upon the first selected column index.

### Claim 10 (depends on 9)

The system of claim 9, wherein the processor, in selecting the second column index, is operable to:
(a) select a predefined number of r vertices spatially closest to a terminating vertex of a first sub-path representing the first column index;
(b) select a plurality of m vertices of the plurality of second sub-paths within the selected sub-matrix;
(c) obtain a plurality of r transport profiles, each of the r transport profiles describing light transport from one of the r vertices to each of the m vertices;
(d) compare each of the r transport profiles to a reference transport profile; and
(e) select as the second column index, a first sub-path having a vertex corresponding to a transport profile which most closely matches the reference transport profile.

### Claim 11

A system operable to estimate the light transport between a first point A and a second point B, the system including a processor operable to:
select a plurality of first sub-paths extending from a first point A;
select a plurality of second sub-paths extending from a second point B;
construct a plurality of transport paths, wherein each one of the plurality of the first sub-paths is coupled to a respective one of the plurality of the second sub-paths to form one transport path, and wherein each transport path comprises one first sub-path and one second sub-path;
sample two or more of the plurality of transport paths to obtain a plurality of sampled transport paths; and
calculate a light transport value for each of the plurality of sampled transport paths to estimate light transported between the first point A and the second point B;
wherein the processor, in constructing the plurality of transport paths, is operable to:
construct a light transport matrix, wherein the plurality of first sub-paths defines respective column indices and the plurality of second sub-paths defines respective row indices, the light transport matrix including an entry Gij defined by a respective column i and a respective row j, whereby the entry Gij comprises a light transport value which describes light transported between the points A and B via a light transport path comprising a combination of a first sub-path corresponding to the column i, and a second sub-path corresponding to the row j;
wherein the processor, in constructing the light transport matrix, is operable to:
sort the plurality of first sub-paths into a plurality of different first sub-path groups, each of the first sub-path groups comprising first sub-paths having a same first path length, and
sort the plurality of second sub-paths into a plurality of different second sub-path groups, each of the second sub-path groups comprising second sub-paths having a same second path length;
wherein one of the first sub-path groups and one of the second sub-path groups collectively form a sub-matrix within the light transport matrix, each sub-matrix comprising a plurality of column indices and a plurality of row indices, wherein each column index corresponds to a termination vertex of a respective first sub-path, and each row index corresponds to a termination vertex of a respective second sub-path;
wherein a plurality of sub-matrices form the light transport matrix;
wherein the processor is operable to order one or more row indices of one or more of the plurality of sub-matrices, the processor operable to:
select one of the plurality of sub-matrices, the selected sub-matrix comprising a plurality of first sub-paths and a plurality of second sub-paths,
select a first row index for the selected sub-matrix, and
select, from among a predefined number of remaining row indices, a second row index for the selected sub-matrix based upon the first selected row index.

### Claim 12 (depends on 11)

The system of claim 11, wherein the processor, in selecting the second row index, is operable to:
(a) select a predefined number of r vertices spatially closest to a terminating vertex of a second sub-path representing the first row index;
(b) select a plurality of m vertices of the plurality of first sub-paths within the selected sub-matrix;
(c) obtain a plurality of r transport profiles, each of the r transport profiles describing light transport from one of the r vertices to each of the m vertices;
(d) compare each of the r transport profiles to a reference transport profile; and
(e) select as the second row index, a second sub-path having a vertex corresponding to a transport profile which most closely matches the reference transport profile.

### Claim 13

A non-transitory computer readable medium having a computer program product including executable programming instructions stored thereon, for estimating the light transport between a first point A and a second point B, comprising:
instruction code to select a plurality of first sub-paths extending from a first point A;
instruction code to select a plurality of second sub-paths extending from a second point B;
instruction code to construct a plurality of transport paths, wherein each one of the plurality of the first sub-paths is coupled to a respective one of the plurality of the second sub-paths to form one transport path, and wherein each transport path comprises one first sub-path and one second sub-path;
instruction code to sample two or more of the plurality of transport paths to obtain a plurality of sampled transport paths; and
instruction code to calculate a light transport value for each of the plurality of sampled transport paths to estimate light transported between the first point A and the second point B;
wherein the instruction code to construct the plurality of transport paths comprises:
instruction code to construct a light transport matrix, wherein the plurality of first sub-paths defines respective column indices and the plurality of second sub-paths defines respective row indices, the light transport matrix including an entry Gij defined by a respective column i and a respective row j, whereby the entry Gij comprises a light transport value which describes light transported between the points A and B via a light transport path comprising a combination of a first sub-path corresponding to the column i, and a second sub-path corresponding to the row j;
wherein the instruction code to construct the light transport matrix comprises:
instruction code to sort the plurality of first sub-paths into a plurality of different first sub-path groups, each of the first sub-path groups comprising first sub-paths having a same first path length, and
instruction code to sort the plurality of second sub-paths into a plurality of different second sub-path groups, each of the second sub-path groups comprising second sub-paths having a same second path length;
wherein one of the first sub-path groups and one of the second sub-path groups collectively form a sub-matrix within the light transport matrix, each sub-matrix comprising a plurality of column indices and a plurality of row indices, wherein each column index corresponds to a respective first sub-path, and each row index corresponds to a respective second sub-path;
wherein a plurality of sub-matrices form the light transport matrix;
wherein further included is instruction code to order one or more column indices of one or more of the plurality of sub-matrices, comprising:
instruction code to select one of the plurality of sub-matrices, the selected sub-matrix comprising a plurality of first sub-paths and a plurality of second sub-paths,
instruction code to select a first column index for the selected sub-matrix, and
instruction code to select, from among a predefined number of remaining column indices, a second column index for the selected sub-matrix based upon the first selected column index.

### Claim 14 (depends on 13)

The non-transitory computer readable medium of claim 13, wherein the instruction code to-select the second column index comprises:
(a) instruction code to-select a predefined number of r vertices spatially closest to a terminating vertex of a first sub-path representing the first column index;
(b) instruction code to-select a plurality of m vertices of the plurality of second sub-paths within the selected sub-matrix;
(c) instruction code to-obtain a plurality of r transport profiles, each of the r transport profiles describing light transport from one of the r vertices to each of the m vertices;
(d) instruction code to compare each of the r transport profiles to a reference transport profile; and
(e) instruction code to-select as the second column index, a first sub-path having a vertex corresponding to a transport profile which most closely matches the reference transport profile.

### Claim 15

A non-transitory computer readable medium having a computer program product including executable programming instructions stored thereon, for estimating the light transport between a first point a and a second point B, comprising:
instruction code to select a plurality of first sub-paths extending from a first point A;
instruction code to select a plurality of second sub-paths extending from a second point B;
instruction code to construct a plurality of transport paths, wherein each one of the plurality of the first sub-paths is coupled to a respective one of the plurality of the second sub-paths to form one transport path, and wherein each transport path comprises one first sub-path and one second sub-path;
instruction code to sample two or more of the plurality of transport paths to obtain a plurality of sampled transport paths; and
instruction code to calculate a light transport value for each of the plurality of sampled transport paths to estimate light transported between the first point A and the second point B;
wherein the instruction code to construct the plurality of transport paths comprises:
instruction code to construct a light transport matrix, wherein the plurality of first sub-paths defines respective column indices and the plurality of second entry Gij defined by a respective column i and a respective row j, whereby the entry Gij comprises a light transport value which describes light transported between the points A and B via a light transport path comprising a combination of a first sub-path corresponding to the column i, and a second sub-path corresponding to the row j;
wherein the instruction code to construct the light transport matrix comprises:
instruction code to sort the plurality of first sub-paths into a plurality of different first sub-path groups, each of the first sub-path groups comprising first sub-paths having a same first path length, and
instruction code to sort the plurality of second sub-paths into a plurality of different second sub-path groups, each of the second sub-path groups comprising second sub-paths having a same second path length;
wherein one of the first sub-path groups and one of the second sub-path groups collectively form a sub-matrix within the light transport matrix, each sub-matrix comprising a plurality of column indices and a plurality of row indices, wherein each column index corresponds to a respective first sub-path, and each row index corresponds to a respective second sub-path;
wherein a plurality of sub-matrices form the light transport matrix;
wherein the instruction code to order one or more row indices of one or more of the plurality of sub-matrices is ordered, comprising:
instruction code to-select one of the plurality of sub-matrices, the selected sub-matrix comprising a plurality of first sub-paths and a plurality of second sub-paths,
instruction code to-select a first row index for the selected sub-matrix, and
instruction code to select, from among a predefined number of remaining row indices, a second row index for the selected sub-matrix based upon the first selected row index.

### Claim 16 (depends on 15)

The non-transitory computer readable medium of claim 15, wherein instruction code to select the second row index comprises:
(a) instruction code to-select a predefined number of r vertices spatially closest to a terminating vertex of a second sub-path representing the first row index;
(b) instruction code to-select a plurality of m vertices of the plurality of first sub-paths within the selected sub-matrix;
(c) instruction code to-obtain a plurality of r transport profiles, each of the r transport profiles describing light transport from one of the r vertices to each of the m vertices;
(d) instruction code to compare each of the r transport profiles to a reference transport profile; and
(e) instruction code to select as the second row index, a second sub-path having a vertex corresponding to a transport profile which most closely matches the reference transport profile.
