摘要：空气中有许多细小颗粒形成的参与介质如云雾、烟尘、冰雪，光子映射能较好地模拟参与介质，对参与介质的光辐射强度估算是参与介质算法的一个关键技术，传统使用简单、有效的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，满足L³=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