《计算机学报》文章摘要   全文下载
文章题目	启发式探查最佳分割平面的快速KD-Tree构建方法
作者	范文山1)，2)，3)，4) 王斌2)，3)，4)
作者单位	1)(清华大学计算机科学与技术系 北京 100084) 2)(清华大学软件学院 北京 100084) 3)(信息系统安全教育部重点实验室 北京 100084) 4)(清华信息科学与技术国家实验室 北京 100084)
发表年份	2009
发表月份	2期(185—192)
文章摘要	摘要 在基于光线跟踪方法的真实感绘制中，kd-tree是一种重要的加速结构.文章对kd-tree的构建方法进行了研究，提出了一种基于分区(binning)算法的快速构建方法.首先，通过分析kd-tree的成本函数，启发式地定位了当前节点的分割平面所在的子区间；其次，对探查到的子区间进行进一步的细化采样(sub-sampling)，使得到的分割平面更好地逼近最优分割位置；同时，文章分析了现有方法在处理分割终止时存在的问题，提出了更加合理的分割终止条件.与以往方法相比，新方法用更小的计算成本生成了质量更好的kd-tree，构建过程更加鲁棒.实验数据验证了文中方法的有效性. 关键词 光线跟踪；kd-tree；SAH；分区算法；细化采样 中图法分类号：TP391 DOI号: 10.3724/SP.J.1016.2009.00185