본 논문은 GPU상에서 작동되는 ray tracing을 위한 효과적인 k-D tree 탐색 알고리즘을 제안한다. 기존의 k-D tree를 위한 GPU 기반 탐색 알고리즘은 임의의 단말노드에서 교차되는 primitive를 찾지 못한 경우. root 노드 방향으로 bottom-up 탐색하여 부모 노드에서 bounding box 교차검사를 이용해 형제 노드의 기 방문 여부를 판단한다. 이러한 방법은 이미 방문한 부모 노드의 방문과 bounding box 교차검사를 중복적으로 수행한다. 본 논문에서 제안하는 알고리즘은 bottom-up 탐색을 수행 할 때 형제노드가 이전에 방문했는지를 확인할 수 있는 효율적인 방법을 제시함으로써 형제노드 및 부모로드의 방문을 생략하도록 하고, 또한 아직 방문하지 않은 노드에 대해서만 bounding box 교차검사를 수행함으로써 중복된 연산을 피한다. 결과적으로 본 논문의 실험은 기존 알고리즘 대비 제안하는 알고리즘이 약 30%의 성능 향상이 있음을 보여 준다.
This paper proposes an effective k-D tree traversal algorithm for ray tracing on a GPU. The previous k-D tree traverse algorithm based on GPU uses bottom-up searching from a leaf to the root after failing to find the ray intersected primitive in the leaf node. During the bottom-up search the algorithm decides the current node is visited or not from the parent node. In such a way, we need to visit the parent node which was already visited and the duplicated bounding box intersection tests. The new k-D tree traverse algorithm reduces the brother and parent duplicated visit by using an efficient method which decides whether the brother node is already visited or not during the bottom-up search. Also the algorithm take place bounding box intersection tests only for the nodes which is not yet done. As a result our experiment shows the new algorithm is about 30% faster than the previous.
