启发式探查最佳分割平面的快速KD-Tree构建方法

作     者：范文山 王斌 FAN Wen-Shan;WANG Bin

作者机构：清华大学计算机科学与技术系北京100084 清华大学软件学院北京100084 信息系统安全教育部重点实验室北京100084 清华信息科学与技术国家实验室北京100084 

出 版 物：《计算机学报》 (Chinese Journal of Computers)

年 卷 期：2009年第32卷第2期

页      面：185-192页

核心收录：

学科分类：0810[工学-信息与通信工程] 0808[工学-电气工程] 08[工学] 081203[工学-计算机应用技术] 0839[工学-网络空间安全] 0835[工学-软件工程] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：国家自然科学基金(90715043 90818011 60773143 60533070) 国家"九七三"重点基础研究发展规划项目基金(2004CB719400) 国家"八六三"高技术研究发展计划项目基金(2007AA040401) 高等学校全国优秀博士学位论文作者专项资金(200342) 霍英东教育基金会(111070)资助~~ 

主　　题：光线跟踪 kd-tree SAH 分区算法 细化采样 

摘      要：在基于光线跟踪方法的真实感绘制中,kd-tree是一种重要的加速结构.文章对kd-tree的构建方法进行了研究,提出了一种基于分区(binning)算法的快速构建方法.首先,通过分析kd-tree的成本函数,启发式地定位了当前节点的分割平面所在的子区间;其次,对探查到的子区间进行进一步的细化采样(sub-sampling),使得到的分割平面更好地逼近最优分割位置;同时,文章分析了现有方法在处理分割终止时存在的问题,提出了更加合理的分割终止条件.与以往方法相比,新方法用更小的计算成本生成了质量更好的kd-tree,构建过程更加鲁棒.实验数据验证了文中方法的有效性.