Journal of Software:2011.22(10):2488-2496

(中国科学院 软件研究所 计算机科学国家重点实验室,北京 100190)
Optimizing Grid Construction in Linear Complexity
LI Jing,WANG Wen-Cheng
(State Key Laboratory of Computer Science, Institute of Software, The Chinese Academy of Sciences, Beijing 100190, China)
Chart / table
Similar Articles
Article :Browse 3287   Download 2987
Received:November 19, 2009    Revised:March 05, 2010
> 中文摘要: 均匀网格划分是一种重要的场景空间组织结构,在光线跟踪绘制、碰撞检测、路径规划等方面有着广泛的应用.特别是由于其计算简单,很适合动态环境的处理.由于该结构的创建时间、空间需求和应用效率与网格分辨率密切相关,优化的网格划分一直是国际上探讨的重要问题.对此,提出一种新的优化划分方法,确保该结构的创建时间和空间需求都是O(N)复杂度的.这里,N 是场景的面片数.同时,在相关的应用计算方面,比如光线跟踪,可与目前最好的加速计算结构相媲美.实验结果表明,该优化划分方法所产生的层次网格结构具有与当前主流的加速结构kd树相当的加速效率,且大幅降低了创建时间,优于已有的类似工作.
Abstract:Uniform grid is one of the important spatial organization structures, which is widely used in many applications such as ray tracing, collision detection, path planning and so on. Its simplicity to compute makes it very suitable for processing dynamic scenes. Because its construction time, space requirement and application efficiency are closely related with the grid resolution, optimizing grid construction has always been an important topic in the world. Hense, a new optimization method for grid construction which ensures that both of the construction time and the space requirement are in the complexity O(N), where N is the number of the primitives in the scene is proposed. In the related applications, such as ray tracing, it can achieve high acceleration efficiency, comparable with the best acceleration structures to date, such as the kd-tree, while reducing the construction time dramatically. These have been approved by the experimental results.
文章编号:     中图分类号:    文献标志码:
基金项目:国家自然科学基金(60873182, 60773026, 60833007) 国家自然科学基金(60873182, 60773026, 60833007)
Foundation items:
Reference text:


LI Jing,WANG Wen-Cheng.Optimizing Grid Construction in Linear Complexity.Journal of Software,2011,22(10):2488-2496