Chinese Journal of Computers   Full Text
Title	A Fast KD-Tree Construction Method by Probing the Optimal Splitting Plane Heuristically
Authors	FAN Wen-Shan1)，2)，3)，4) WANG Bin2)，3)，4)
Address	1)(Department of Computer Science and Technology, Tsinghua University, Beijing 100084) 2)(School of Software, Tsinghua University, Beijing 100084) 3)(Key Laboratory for Information System Security, Ministry of Education of China, Beijing 100084) 4)(Tsinghua National Laboratory for Information Science and Technology, Beijing100084)
Year	2009
Issue	No.2(185—192)
Abstract &   Background	Abstract In the field of ray-tracing based photo-realistic rendering, kd-tree is used as an important acceleration structure. This paper focuses on the effective construction of kd-tree, and proposes a novel and fast construction method which is based on the binning algorithm. The method is composed of two main steps. Firstly, by analyzing the SAH cost function, the method determines the most-likely sub-span which holds the splitting plane. Secondly, sub-sampling is used on the resulted span to get much better approximation to the optimal splitting plane. Moreover, the paper discusses the exiting schemes on binning termination condition, points out their problems, and proposes a more reasonable termination condition. The experimental results show that the novel approach is effective. Compared with the previous works, it decreases the construction overhead, improves the quality of generated kd-tree, and the construction procedure is more robust as well. Keywords ray tracing; kd-tree; SAH; binning algorithm; sub-sampling Background As one of the most important acceleration structure, kd-tree is used widely by most of the ray-tracing based photo-realistic rendering applications. There are two problems in relation to the use of kd-tree. One is how to traverse it as rapidly as possible. Much effort has been done to solve it, such as MLRTA. Another one is how to build high quality kd-tree in as less time as possible. The problem has been investigated just in recent years. This paper focuses on the latter. The building procedure of kd-tree is a calculation intensive and tactical task. With the increase of complexity of the scene, the overhead paid for kd-tree construction has grown tremendously. So it is significant to present a fast kd-tree building method. One of the problems of existing approaches on quick kd-tree construction is that they use fixed and uniform binning style, which incurs the dilemma that the used binning scheme can’t accommodate to the random distribution of the nature scene. Another problem is that the fixed and uniform binning style needs the unnecessary iteration on the whole span. To address the problems, the authors propose a novel, adaptive binning method by digging out the heuristic information from the SAH cost function. On the first step, the method tries to find the most-likely sub-span, which holds the splitting plane of current node. Doing as that can avoid the unnecessary iteration and speedup the building procedure. On the second step, the sub-sampling is used on the found sub-span to get the much better approximating splitting plane. After both of that, the more reasonable termination condition is used, which is helpful to improve the quality of resulted kd-tree and stability of construction procedure. The proposed method can be parallelized in multi-thread style easily as well. The experimental results show the effectiveness of the novel, fast kd-tree construction method. The research was supported by the National High Technology Research and Develop Program (863 Program) of China (Grant No.2007AA040401), the National Basic Research Program (973 Program) of China (Grant No.2004CB719400), National Natural Science Foundation of China (grant Nos.90715043, 90818011, 60773143, 60533070).