| 启发式探查最佳分割平面的快速KD-Tree构建方法 |
| |
| 引用本文： | 范文山,王斌. 启发式探查最佳分割平面的快速KD-Tree构建方法[J]. 计算机学报, 2009, 32(2). DOI: 10.3724/SP.J.1016.2009.00185 |
| |
| 作者姓名： | 范文山 王斌 |
| |
| 作者单位： | 1. 清华大学计算机科学与技术系,北京,100084;清华大学软件学院,北京,100084;信息系统安全教育部重点实验室,北京,100084;清华信息科学与技术国家实验室,北京,100084
2. 清华大学软件学院,北京,100084;信息系统安全教育部重点实验室,北京,100084;清华信息科学与技术国家实验室,北京,100084 |
| |
| 基金项目： | 国家自然科学基金，国家重点基础研究发展规划(973计划)，国家高技术研究发展计划(863计划)，高等学校全国优秀博士学位论文作者专项基金，霍英东青年教师基金 |
| |
| 摘 要： | 在基于光线跟踪方法的真实感绘制中,kd-tree是一种重要的加速结构.文章对kd-tree的构建方法进行了研究,提出了一种基于分区(binning)算法的快速构建方法.首先,通过分析kd-tree的成本函数,启发式地定位了当前节点的分割平面所在的子区间;其次,对探查到的子区间进行进一步的细化采样(sub-sampling),使得到的分割平面更好地逼近最优分割位置;同时,文章分析了现有方法在处理分割终止时存在的问题,提出了更加合理的分割终止条件.与以往方法相比,新方法用更小的计算成本生成了质量更好的kd-tree,构建过程更加鲁棒.实验数据验证了文中方法的有效性.
|
| 关 键 词： | 光线跟踪 分区算法 细化采样 |
A Fast KD-Tree Construction Method by Probing the Optimal Splitting Plane Heuristically |
| |
| FAN Wen-Shan,WANG Bin. A Fast KD-Tree Construction Method by Probing the Optimal Splitting Plane Heuristically[J]. Chinese Journal of Computers, 2009, 32(2). DOI: 10.3724/SP.J.1016.2009.00185 |
| |
| Authors: | FAN Wen-Shan WANG Bin |
| |
| Affiliation: | Department of Computer Science and Technology;Tsinghua University;Beijing 100084;School of Software;Beijing 100084;Key Laboratory for Information System Security;Ministry of Education of China;Beijing 100084;Tsinghua National Laboratory for Information Science and Technology;Beijing 100084 |
| |
| 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 ... |
| |
| Keywords: | kd-tree SAH |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
