线性复杂度的网格优化划分

• 作者: 李静 王文成
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 网格 光线跟踪 动态场景 大规模场景 分辨率
• 年，卷（期）: 2011,（10）
• 所属期刊栏目: 计算机图形学与计算机辅助设计
• 页码范围: 2488-2496
• 分类号: TP391
• 字数: 8780字
• 语种: 中文
• DOI: 10.3724/SP.J.1001.2011.03927

摘要

均匀网格划分是一种重要的场景空间组织结构,在光线跟踪绘制、碰撞检测、路径规划等方面有着广泛的应用.特别是由于其计算简单,很适合动态环境的处理.由于该结构的创建时间、空间需求和应用效率与网格分辨率密切相关,优化的网格划分一直是国际上探讨的重要问题对此,提出一种新的优化划分方法,确保该结构的创建时间和空间需求都是O(N)复杂度的.这里,N是场景的面片数.同时,在相关的应用计算方面,比如光线跟踪,可与目前最好的加速计算结构相媲美.实验结果表明,该优化划分方法所产生的层次网格结构具有与当前主流的加速结构kd树相当的加速效率,且大幅降低了创建时间,优于已有的类似工作.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李静	中国科学院软件研究所计算机科学国家重点实验室	238	2528	23.0	40.0
2	王文成	中国科学院软件研究所计算机科学国家重点实验室	42	484	13.0	20.0