《基于快速k近邻的参与介质算法研究》-工学论文，计算机论文-论文范文参考-科学狗论文网

标题

基于快速k近邻的参与介质算法研究

范文

王海波

摘要：空气中有许多细小颗粒形成的参与介质如云雾、烟尘、冰雪，光子映射能较好地模拟参与介质，对参与介质的光辐射强度估算是参与介质算法的一个关键技术，传统使用简单、有效的k近邻（kNN）算法，但kNN具有计算复杂度高，内存需求量的缺点，新算法针对kNN的缺点，改进kNN搜索光子的方式，先将空间分割为多个固定长度的立方体，每个立方体体包含一定数量的光子数，通过测试各个立方体与估算点之间的位置搜索估算点周围的k个最近邻光子，减少计算复杂度，进而改进参与介质的光辐射强度估算，实验表明基于新算法的参与介质算法速度更快。

关键词：参与介质;光子映射;光辐射强度估算;k近邻

中图分类号：TP3 文献标识码：A

文章编号：1009-3044（2019）31-0278-02

1参与介质

空气中的细小颗粒形成的参与介质如云雾、烟尘、冰雪，会在对光线产生吸收、发射、散射等现象。参与介质的吸收是指光的辐射能量转换成其他形式的能量，导致发光强度减小，距离的不同，能量减小的程度不同;发射是指介质中的粒子发光等因素，增加光照在传播过程中的能量;散射是指光线与介质中的粒子发生碰撞从而导致光线向不同的方向发射，包括内散射（in-scattering）和外散射（out-scattering），其中内散射增加光照在传播过程中的能量，而外散射则减少光照在传播过程中的能量。光子映射算法绘制介质参可取得较好的效果，光子映射算法能取得较好的模拟参与介质。

光子映射分为两个阶段第一个阶段发射光子，跟踪光子，建立光子图;第二阶段利用光子图估算光照，从图形像素的角度发出光线，如果遇到反射或折射后，记录接触点，搜索接触点周围的光子，对接触点进行光辐射强度估算，渲染图形。因此光辐射强度估算是光子映射算法的第二阶段的一个关键技术。

参与介质的光辐射强度的估算的原理图如图1所示，像素接受到来自从Xs发出的，方向为ω的光线，Tr为光线透过率，L为Xs点发出的光强度角度为ω，L经过参与介质后到达像素处既图中眼睛处，像素的光强度如（1）式所示。

2.2构建新算法

新算法使用空间网格的方法先将空间划分为若干立方体，将所有光子置入到这些立方体中。立方体网格单元太大太小，都会对整个查找过程产生不良影响，若立方体网格单元太小，会增加存储量，降低效率;若立方体网格单元太大，则每个立方体单元会包含过多面片，对求交造成困难，因此新算法划分立方体的个数为p=n/t其中n是光子总数，t是未知数，一般取值为20，立方体的边长为L，满足L3=n/t。如果有多个不包含光子的立方体连续在一起，则合并为一个立方体，保证生成的空间单元数不超过0（n），如算法1所示。接着搜索估算点周围的k个立方体，并从k个立方体中搜索最近的k个光子，完成对估算点光辐射强度的估算如算法2，图2所示。

算法1：构造立方体

Step1：计算n/t，算出立方体的数量σ

Step2：计算立方体的边长

Step3：划分立方体。

算法2：寻找估算点的最近邻光子

Step1：查找出估算点附件的包含自己在内的k个立方体，

Step2：从最近的k個立方体中查找k个最近邻光子。

2.3算法分析

设发射光子数n，k为kN N算法参数，m为估算点的个数。传统KNN的时间复杂度为0（mn k），表示每个估算点要计算同n个光子的距离，同时为求出k个最近邻的光子，内存中要维持一个k长度的插入排序表，在排序表中，每插入一个新值，对表的最大操作次数为k。新算法中设立方体的总数为p，时间复杂性包含求k个最小立方体及其所包含样本中的k个最近邻样本。每个立方体平均包含的光子数为n/p，因此时间复杂性为0（mpk+mnk2/p）=0（m k（p+nk/p）），故当p+nk/pp 2/（p-k）时，新算法的时间复杂性低于传统kNN算法，由于k取值同立方体数相比要小得多，故当n>p>k时，实际取值p<=n/20，因此n>p>k条件是成立的，新算法的运行效率优于传统的kNN算法。

3算法实现

采用vs2013和OpenGL的编程环境，在一台配置为Intel（R）Core（TM）i5，8GB内存，NVIDIA GeForce 610M显卡，win7下进行实验。

实验所用的测试场景如图2，图3，图4所示，其中图2的光子数为10M，图3光子数15M，图4光子数20M。由表1可看出新算法渲染比传统kNN算法快，其中图3快了%30，图4快了29.8%，图5快了28%，因此新算法提高了参与介质的渲染速度

4结束语

新算法针对kNN的缺点进行了改进，先将空间分割为多个固定长度的立方体，每个立方体体包含一定数量的光子数，通过测试各个球体与接触点之间的位置速搜索测试点周围的k个最近邻光子，进而较好地改善了参与介质的光辐射强度估算光辐射强度，实验表明基于新算法的参与介质算法速度更快。

随便看

科学优质学术资源、百科知识分享平台，免费提供知识科普、生活经验分享、中外学术论文、各类范文、学术文献、教学资料、学术期刊、会议、报纸、杂志、工具书等各类资源检索、在线阅读和软件app下载服务。