QQ客服 官方微博 反馈留言

	启发式探查最佳分割平面的快速KD-Tree构建方法
	范文山 ; 王斌 ; FAN Wen-Shan ; WANG Bin
	2010-06-09 ; 2010-06-09
关键词	光线跟踪 kd-tree SAH 分区算法 细化采样 ray tracing kd-tree SAH binning algorithm sub-sampling TP391.41
其他题名	A Fast KD-Tree Construction Method by Probing the Optimal Splitting Plane Heuristically
中文摘要	在基于光线跟踪方法的真实感绘制中,kd-tree是一种重要的加速结构.文章对kd-tree的构建方法进行了研究,提出了一种基于分区(binning)算法的快速构建方法.首先,通过分析kd-tree的成本函数,启发式地定位了当前节点的分割平面所在的子区间;其次,对探查到的子区间进行进一步的细化采样(sub-sampling),使得到的分割平面更好地逼近最优分割位置;同时,文章分析了现有方法在处理分割终止时存在的问题,提出了更加合理的分割终止条件.与以往方法相比,新方法用更小的计算成本生成了质量更好的kd-tree,构建过程更加鲁棒.实验数据验证了文中方法的有效性.; 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.; 国家自然科学基金(90715043,90818011,60773143,60533070); 国家“九七三”重点基础研究发展规划项目基金(2004CB719400); 国家“八六三”高技术研究发展计划项目基金(2007AA040401); 高等学校全国优秀博士学位论文作者专项资金(200342); 霍英东教育基金会(111070)资助~~
语种	中文 ; 中文
内容类型	期刊论文
源URL	[http://hdl.handle.net/123456789/55253]
专题	清华大学
推荐引用方式 GB/T 7714	范文山,王斌,FAN Wen-Shan,等. 启发式探查最佳分割平面的快速KD-Tree构建方法[J],2010, 2010.
APA	范文山,王斌,FAN Wen-Shan,&WANG Bin.(2010).启发式探查最佳分割平面的快速KD-Tree构建方法..
MLA	范文山,et al."启发式探查最佳分割平面的快速KD-Tree构建方法".(2010).

个性服务

查看访问统计

相关权益政策

暂无数据

收藏/分享

除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。