Photon mapping on graphics hardware using kd-trees

Patent metadata

Field	Value
Publication number	US-8928658-B2
Application number	US-24104608-A
Country	US
Kind code	B2
Filing date	Sep 30, 2008
Priority date	Sep 30, 2008
Publication date	Jan 6, 2015
Grant date	Jan 6, 2015

Abstract

Described is a technology by which a GPU-based photon mapping mechanism/algorithm uses a kd-tree to render arbitrary dynamic scenes. For each frame, the mechanism emits and traces a set of photons into the scene. When a photon hits a surface, it can either be reflected, transmitted, or absorbed based on the surface material. Once photon tracing is done, a kd-tree is built for the stored photons. To estimate the radiance value at an arbitrary surface point, the k-nearest photons are located and filtered. The photon tracing and photon kd-tree construction, as well as the radiance estimation using k-nearest neighbor (KNN) searches are performed on graphics hardware, e.g., a GPU. In one example, only caustic photons are traced, whereby a photon is terminated and stored once it hits a diffuse surface.

First claim

What is claimed is:

1. In a computing environment, a method comprising:
building a kd-tree representative of scene geometry via graphics processing unit (GPU)-based parallel processing, wherein building the kd-tree comprises storing data representative of the photons in the kd-tree, and wherein small nodes and large nodes of the kd-tree nodes are built in breadth-first search order in which the small nodes are defined by a threshold corresponding to a number of geometric primitives;
using the kd-tree for photon mapping to produce a frame of a dynamic scene, wherein using the kd-tree for photon mapping comprises estimating a radiance value at a surface point by locating a set of nearby photons, and
wherein locating the set of nearby photons comprises performing a k-nearest neighbor search;
emitting and tracing a set of photons into a scene;
determining a search radius by constructing a histogram via a fixed-radius range search;
reducing the search radius based upon the histogram; and
iteratively repeating the constructing and reducing operations until an iteration number is met.

2. The method of claim 1 wherein building the kd-tree comprises, differentiating large nodes from small nodes based on geometry primitives associated with each node, splitting large nodes into child nodes by empty space splitting and spatial splitting, and splitting small nodes into child nodes based on computed costs for split candidates.

3. The method of claim 2 wherein differentiating large nodes from small nodes comprises evaluating a number of points in a node relative to the threshold.

4. The method of claim 1 wherein building the kd-tree comprises storing data representative of caustic photons in the kd-tree, including by terminating and storing data for each photon that hits a diffuse surface.

5. The method of claim 1 wherein locating the set of nearby photons comprises returning a count of the photons within the search radius.

6. In a computing environment having a graphics processing unit (GPU), a system comprising:
a kd-tree building mechanism coupled to the GPU, and
a photon mapping mechanism coupled to the kd-tree building mechanism configured to:
build a kd-tree representative of scene geometry completely in breadth-first order,
split at least some nodes of the kd-tree into child nodes based on computed costs for split candidates via a voxel volume heuristic, and
traverse the kd-tree to determine photon-related data to produce a frame of a dynamic scene,
emit a set of photons into a scene,
trace the photons, and
estimate a radiance value at a surface point by locating a set of nearby photons by performing a k-nearest neighbor search,
determine a search radius for the k-nearest neighbor search by constructing a histogram via a fixed-radius range search,
reduce the search radius based upon the histogram, and
iteratively repeat the constructing and reducing operations until an iteration number is met.

7. The system of claim 6 wherein the photon mapping mechanism and kd-tree building mechanism are configured to build a new kd-tree for each frame of a set of subsequent frames.

8. The system of claim 6 wherein the kd-tree building mechanism is configured to differentiate large nodes from small nodes based on geometry primitives associated with each node, and to split small nodes into child nodes based on the computed costs for split candidates via the voxel volume heuristic.

9. The system of claim 6 wherein a size of the histogram and the iteration number are received as parameters by the photon mapping mechanism.

10. The system of claim 6 wherein the photon mapping mechanism is configured to emit a set of photons into a scene, traces only caustic photons, and is configured to estimate a radiance value at a surface point by locating a set of nearby caustic photons.

11. An article comprising one or more computer-readable storage devices having computer-executable instructions stored thereon, which in response to execution by a computer, cause the computer to perform steps, comprising:
tracing and mapping photons via a graphics processing unit (GPU), using the GPU to construct small and large nodes of a kd-tree representative of the traced photons in breadth-first search order in which the small nodes are differentiated from the large nodes based upon a number of points associated with each node, and
using the GPU to estimate radiance for a point by using a k-nearest neighbor search to determine a number of photons within a radius of that point, wherein a search-radius for the k-nearest neighbor search is determined by:
constructing a histogram via a fixed-radius range search,
reducing the search radius based upon the histogram, and
iteratively repeating the constructing and reducing operations until an iteration number is met.

12. The article of claim 11 wherein tracing and mapping the photons comprises tracing only caustic photons based upon whether each photon hits a diffuse surface.

Assignees

• Zhou Kun
• Qiming Hou
• Guo Baining
• Microsoft Corp

Inventors

• Zhou Kun
• Qiming Hou
• Guo Baining

Classifications

• G06T15/50

  Lighting effects · CPC title

• G06T17/005 Primary

  Tree description, e.g. octree, quadtree · CPC title

• G06F3/048

  Interaction techniques based on graphical user interfaces [GUI] · CPC title