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

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

针对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.