GPU상에서 동작하는 Ray Tracing을 위한 효과적인 k-D tree 탐색 알고리즘 = An Efficient k-D tree Traversal Algorithm for Ray Tracing on a GPU

다국어 초록 (Multilingual Abstract)

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.

국문 초록 (Abstract)

본 논문은 GPU상에서 작동되는 ray tracing을 위한 효과적인 k-D tree 탐색 알고리즘을 제안한다. 기존의 k-D tree를 위한 GPU 기반 탐색 알고리즘은 임의의 단말노드에서 교차되는 primitive를 찾지 못한 경우. root 노드 방향으로 bottom-up 탐색하여 부모 노드에서 bounding box 교차검사를 이용해 형제 노드의 기 방문 여부를 판단한다. 이러한 방법은 이미 방문한 부모 노드의 방문과 bounding box 교차검사를 중복적으로 수행한다. 본 논문에서 제안하는 알고리즘은 bottom-up 탐색을 수행 할 때 형제노드가 이전에 방문했는지를 확인할 수 있는 효율적인 방법을 제시함으로써 형제노드 및 부모로드의 방문을 생략하도록 하고, 또한 아직 방문하지 않은 노드에 대해서만 bounding box 교차검사를 수행함으로써 중복된 연산을 피한다. 결과적으로 본 논문의 실험은 기존 알고리즘 대비 제안하는 알고리즘이 약 30%의 성능 향상이 있음을 보여 준다.

참고문헌 (Reference)

• 1 N. A. Carr, "The Ray Engine" Department of Computer Science 2002
• 2 A. Nathan, "The Ray Engine" 37-46, 2002
• 3 S. Popov, "Stackless KD-Tree Traversal for High Performance GPU Ray Tracing" 10 (10): 2007
• 4 M. Ernst, "Stack implementation on programmable graphics hardware" Vision Modeling and Visualization 255-262, 2004
• 5 I. Wald, "Realtime Ray Tracing and its Use for Interactive Global Illumination" EUROGRAPHICS State of the Art Reports 85-122, 2003
• 6 T. J. Purcell, "Ray tracing on programmable graphics hardware" 703-712, 2002
• 7 M. Pharr, "Physically Based Rendering: From Theory to Implementation" Morgan Kaufmann 2004
• 8 J. L. Bentley, "Multidimensional Binary Search Trees Used for Associative Searching" Communications of the ACM 509-517, 1975
• 9 T. Foley, "KD-Tree Acceleration Structures for a GPU Raytracer" 15-22, 2005
• 10 S. Parker, "Interactive ray tracing" 119-126, 1999
• 11 D. R. Horn, "Interactive k-d tree GPU raytracing" 167-174, 2007
• 12 I. Wald, "Interactive Rendering with Coherent Ray Tracing" 20 (20): 153-164, 2001
• 13 J. D. MacDonald, "Heuristics for ray tracing using space subdivision" The Visual Computer 1990
• 14 V. Havran, "Department of Computer Science and Engineering" Czech Technical University in Prague 2000
• 15 F. W. Jason, "Data structures for ray tracing" 57-73, 1986
• 16 I. Buck, "Brook for GPUs: Stream computing on graphics hardware" 2004