Photon mapping is one of the most popular global illumination algorithms. The main operations of photon mapping consist of ray tracing and the k-nearest neighbor(KNN) search. Among the two operations, more research has been investigated to improve the performance ray tracing. As a result, the bottleneck of photon mapping becomes the KNN search. The KNN search in photon mapping is used to estimate the radiance for each ray. In addition to reducing the cost of the KNN search, reducing the construction time of photon maps gets more important because dynamic scenes and lights are widely used in various applications such as games and computer-generated movies.
This thesis presents a hybrid data structure that combines a hash-grid and kd-trees to reduce both the construction time and the runtime KNN search time. We compute a uniform grid on the input scene. Then, we construct a photon kd-tree for each cell of the grid. For the KNN search at runtime, we can remove photons that do not contribute to the radiance estimate using the hash-grid. More specifically, we only consider gird cells that are in close proximity to the grid cell that contains the query point of the KNN search. Then, kd-trees in these grid cells are traversed for finding the exact k-nearest-neighbor photons.
We compare our representation against the original kd-tree representation that is constructed from all the photons. By using our hybrid representation, we can reduce the traversal time and thus improve the performance of the KNN search by up to 2 times. Also, due to the simplicity of our representation, we reduce the construction time by up to 7 times. Finally, we have found that our method shows a higher scalability on a multi-core CPU, since we access small kd-trees of gird cell instead of accessing the big single kd-tree during the KNN search.
포톤 매핑은 가장 많이 사용되고 있는 전역 조명 알고리즘 중에 하나이다. 포톤 매핑의 주요 연산은 광선 추적과 K개의 근접 포톤 검색이며, 광선 추적의 경우 많은 연구를 통해 성능이 향상되었다. 이로 인해 K개의 근접 포톤 검색은 포톤 매핑의 병목이 되었다. 또한, 영화, 게임과 같은 분야에서 동적 오브젝트와 조명의 요구가 증가하고 있으며, 이로 인해 포톤 맵 생성 시간을 줄이는 것 역시 중요해지고 있다.
해당 학위논문에서는 해쉬-그리드 방식과 KD-나무를 융합한 하아브리드 포톤 맵을 제안하였다. K개의 근접 포톤 검색을 하기 위하여 먼저 그리드를 통해 불필요한 포톤을 제거한 후, KD-나무를 이용하여 정확하고 빠르게 K개의 포톤을 찾는 것 이다.
저자는 이를 통해 기존의 단순 KD-나무 방식보다 K개의 포톤 검색에서 최대 2배의 성능 향상을 이루었으며, 생성시간을 최대 7배 감소 시켰다. 또한, 저자가 제안한 하이브리드 포톤 맵은 멀티 코어 CPU에 적합하며, 코어 수에 따라 확정성을 보여주었다.
