Microsoft Technology Licensing, LLC

Hou Qiming

Baining Guo

Kun Zhou

Described is a technology by which a ray tracer incorporates a GPU-based kd-tree builder for rendering arbitrary dynamic scenes. For each frame, the ray tracer builds a kd-tree for the scene geometry. The ray tracer spawns and traces eye rays, reflective and refractive rays, and shadow rays. For each ray to be traced, the ray tracer walks through the kd-tree until it reaches leaf nodes and associated triangles. When a ray passes through both sides of a splitting plane, the 'far' sub-tree is pushed into the stack and the 'near' sub-tree is traversed first.

Ray tracing on graphics hardware using kd-trees

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.

Photon mapping on graphics hardware using kd-trees

Described is a technology in a computing environment comprising a programming language for general purpose computation on a graphics processing unit (GPU), along with an associated compiler. A Bulk-Synchronous GPU Programming (BSGP) program is programmed to include barriers to describe parallel processing on GPUs. A BSGP compiler detects barriers corresponding to supersteps, converts BSGP programs to kernels based on the barriers, and combines them. During compilation, the compiler aligns barriers in the statements and bundles the corresponding supersteps together. A par construct is provided to allow the programmer to control aspects of bundling, e.g., by specifying a block independent statements. Thread manipulation emulation is provided to transparently emulate thread creation and destruction, with operations fork and kill. Also provided is remote variable access intrinsics for efficient communications between threads, and collective primitive operations.

Bulk-synchronous graphics processing unit programming

Described is a technology for constructing kd-trees on GPUs, in a manner that is sufficiently fast to achieve real-time performance by exploiting GPU-based parallelism during the kd-tree construction. Tree nodes are built in breadth-first search order, e.g., to use a thread for each node at each level. For large nodes at upper tree levels, computations are parallelized over geometric primitives (instead of nodes). To this end, large nodes are split into child nodes by cutting off empty space based until an empty space ratio is achieved, and thereafter performing spatial splitting. Small nodes are split based on split candidate costs, e.g., computed by a surface area heuristic or a voxel volume heuristic (VVH).

Growing community of inventors

Beijing, China

Hou Qiming