kNN Search Architecture Design for Photon Density Estimation

在以物理模擬為基礎的繪圖演算法中，光子映射（photon mapping）是一種可模擬相當多樣光影效果的演算法。光子在電腦繪圖中是從場景中光源散布出的能量的概念，而光子映射繪圖於近十多年來被提出，直到今日仍是熱門的研究發展領域，在近年來更時常被整合至追求高繪圖效果的先進繪圖演算法。這種發展趨勢顯示光子的概念在進代的繪圖演算法中扮演了相當重要的角色。 然而純軟體的光子映射演算法在今日仍然難以達到實時的效能。光子映射演算法包含了兩項步驟：光子追蹤（photon tracing）和光子密度估計（photon density estimation）；光子追蹤即為光線追蹤（ray tracing）的步驟，而光線追蹤的硬體加速以經被研究多年，在現代的GPGPU或純硬體化的ASIC中大約可以達到每秒追蹤400M道光線的效能；而光子密度估計的硬體加速系統在今日則仍只有GPGPU為主的研究，純粹硬體ASIC的加速方式則是一門尚未被研究的領域。根據這樣的研究背景，這篇論文將重點放在探討光子密度估計的硬體實作方式。 k-近鄰（kNN）搜尋是光子密度估計的基本演算，在適當減少光影效果的雜訊下，通常數百萬數量級的光子和搜集點需要被計算，光子密度估計則利用每個搜集點附近的光子能量總合來計算每個圖片像素的顏色能量。為了達到更高的效率，近似k-近鄰（kANN）演算法通常被使用，而本論文則研究並實現在大數量資料點下的近似k-近鄰硬體架構。 本論文提出了第一個以光子密度估計應用為目標的近似k-近鄰硬體架構，適用在如光子映射的大量資料點搜尋。架構以合理的硬體使用實現在Altera DE4 FPGA上，並經由PCIe連接電腦作為k-近鄰搜尋引擎，在256x256的解析度、每像素4個樣本下，繪畫具有反射或折射光影效果的場景可達到4-5秒的效能，較純軟體的實作約超出3-4倍。由於FPGA效能的限制，系統僅實行在125MHz的速度上，記憶體的頻寬也遠低於現代GPU的規格，然而這樣的結果顯示了在先進製程下此硬體架構達成實時光子密度估計的可能。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