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