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

• 作者: 王斌 范文山
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 光线跟踪 kd-tree SAH 分区算法 细化采样
• 年，卷（期）: 2009,（2）
• 所属期刊栏目: 研究论文与技术报告
• 页码范围: 185-192
• 页数: 8页
• 分类号: TP391
• 字数: 6811字
• 语种: 中文
• DOI: 10.3724/SP.J.1016.2009.00185

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王斌	清华大学软件学院	41	286	10.0	15.0
10	范文山	清华大学计算机科学与技术系	1	32	1.0	1.0