kNN Search Architecture Design for Photon Density Estimation
Date Issued
2014
Date
2014
Author(s)
Zeng, Ren-Pei
Abstract
Among physically-based rendering algorithms, photon mapping is a robust global illumination algorithm that simulates a wide range of lighting effects. Though lots of new rendering techniques are being presented in recent years, photon mapping is still being developed and even integrated in advanced high-quality rendering algorithms. The trend on rendering techniques has shown the important role of photons as vehicles of energy distributed from light sources. However, the performance of pure software implementations of photon-based algorihtms is far from the requirements of real-time applications today. Every photon-based algorithm contains two steps: photon tracing pass and photon density estimation. Hardware accelerators for ray tracing with general-purpose graphics processing unit (GPGPU) or triangle-hit ASIC have being investigated for years which can help accelerating photon tracing as well. For hardware implementations of photon density estimation, GPU algorithms are still under developing, and pure hardware ASIC is leaved an open research field. Based on this background, this work focuses on hardware architecture design for photon density estimation. $k$-nearest neighbor ($k$NN) searching is an essential part of photon density estimation. To render a scene with noiseless lighting effects, typically millions of photons and gathering points are needed as the input of $k$NN search engine. Photon density estimation then calculates pixel radiance according to total energy of nearby photons around each gathering point. For higher performance, approximated $k$-nearest neighbor ($k$ANN) searching is often adopted in computer graphics. We survey and implement hardware architecture for $k$ANN search with large number of data and query points. As a result, this paper presents a first $k$ANN search engine for photon density estimation. It is suitable for large number of data and query points that meets the requirements of photon mapping algorithms. On Altera DE4 FPGA via PCI-Express connector, the architecture can be scaled for reasonable resource usage and for desired performance. The result FPGA system takes $4$-$5$ seconds to render a typical scene with reflective or refractive caustics in $256 imes 256$ image resolution and $4$ samples per pixel, which wins the performance by $3$-$4$ times of pure software implementation. Limited to FPGA performance, our prototype system operates at $125$MHz clock speed and far less bandwidth than modern GPUs. This result reveals the possibility of real-time hardware $k$NN accelerator with hardware fabrication in modern process technologies.
Subjects
photon mapping
kNN search
hardware architecture
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-103-R01943050-1.pdf
Size
23.32 KB
Format
Adobe PDF
Checksum
(MD5):501ca8cbe7c10a5278a2474a2f0f9e63