基于空间自适应剖分的Lightcuts多光源聚类算法  

Lightcuts Multi-Light Source Clustering Algorithm Based on Adaptive Space Subdivision

作　　者：袁昱纬[1] 刘传辉[1] 全吉成[1,2] 王宏伟[2] 吴晨[1] YUAN Yuwei LIU Chuanhui QUAN Jicheng WANG Hongwei WU Chen(Department of Electronic and Information Engineering, NAAU, Yantai Shandong 264001, China Department of Aeronautic and Astronautic Intelligence, Aviation University of Air Force, Changchun 130022, China)

机构地区：[1]海军航空工程学院电子信息工程系,山东烟台264001 [2]空军航空大学航空航天情报系,长春130022

出　　处：《海军航空工程学院学报》2017年第2期181-186,198,共7页Journal of Naval Aeronautical and Astronautical University

基　　金：国家自然科学基金资助项目(61301233);吉林省自然科学基金资助项目(20130101069JC)

摘　　要：针对Lightcuts算法在面对大规模复杂光源时计算效率较低的问题,提出了一种基于空间自适应剖分的Lightcuts多光源聚类算法。该算法采用二叉树森林代替传统Lightcuts算法中的二叉树,并提出自适应的视景体划分方法对三维场景进行剖分,通过构建包含"簇-光源"对的列表,快速剔除与当前渲染点无关的光源,同时利用空间聚类的相似性减少"光源割"搜索过程中的重复计算。实验结果表明,与传统方法相比,文章提出的算法在"光源割"计算阶段能够将搜索步数平均减少30.71%~42.09%,绘制时间平均缩短28.35%~34.84%,有效地加快了Lightcuts算法的计算速度,提高了多光源三维场景的绘制效率。In order to overcome the shortcomings of low efficiency of lightcuts algorithm when dealing with plenty of com- plex light sources, a lightcuts multi-source clustering algorithm based on adaptive space subdivision was proposed. Binary tree forest that was used in this algorithm, replaced the binary tree in traditional lightcuts algorithm, and a scheme of adap- tive spatial subdivision based on view frustum was proposed to subdivide the 3D scene. For purpose of quickly culling the light sources which was irrelevant to current rendering point, a list of ＂cluster-light＂ pairs was built. At the same time, the repeated computation in the process of finding cuts was reduced based on the similarity of space clustering. The experimen- tal results showed that, compared with the traditional method, the algorithm that was proposed in this paper could reduce the number of search steps by 30.71%-42.09% averagely in the stage of finding cut, and reduce the rendering time by 28.35%-34.84% averagely. It could accelerate the calculation speed of lightcuts algorithm significantly, and improve the rendering efficiency of multiple light source in 3D scene.

关 键 词：多光源 Lightcuts 自适应空间剖分 二叉树森林 场景绘制 

分 类 号：TP391.9[自动化与计算机技术—计算机应用技术]