蒙特卡罗算法综述
摘要：本文介绍了蒙特卡罗算法的起源，原理，描述及应用，列举了一个蒙特卡罗全局光照算法得实例及研究过程。
关键词：蒙特卡罗；全局光照；统计；自适应
Monte Carlo Algorithms
Liu Bingkun
Abstract: This article describes a Monte Carlo algorithm for the origin of principle, description and application cited the instance of a MonteCarlo global illumination algorithms and the research process.
Keywords: Monte Carlo; global illumination; statistics; adaptive
1引言
蒙特·卡罗算法（Monte Carlo method），也称统计模拟方法，是二十世纪四十年代中期由于科学技术的发展和电子计算机的发明，而被提出的一种以概率统计理论为指导的一类非常重要的数值计算方法。是指使用随机数（或更常见的伪随机数）来解决很多计算问题的方法。蒙特·卡罗方法的名字来源于摩纳哥的一个城市蒙地卡罗，该城市以赌博业闻名，而蒙特·卡罗方法正是以概率为基础的方法。起源于早期的用几率近似概率的数学思想 ,它利用随机数进行统计试验 ,以求得的统计特征值 (如均值、概率等) 作为待解问题的数值解. 随着现代计算机技术的飞速发展，蒙特卡罗算法也在不断的改进。
全局光照是三维软件中的特有名词，光具有反射和折射的性质。在真实的大自然中，光从太阳照射到地面是经过无数次的反射和折射的，所以我们看到地面的任何地方都是清晰的（白天），在三维软件中，里面的光虽然也具有现实当中光的所有性质，但是光的热能传递却不是很明显。
全局光照，表现了直接照明和间接照明的综合效果。光线碰到拍摄对象，反射正反射光或漫反射光，这就控制了色彩、物体间相互作用的反射、折射、焦散等光效，最后演绎了现实的自然光。所以在渲染的时候，为了实现真实的场景效果，就要在渲染器中指定全局光照，全局光照有多种实现方法，例如辐射度、光线追踪、环境光遮蔽（ambient occlusion）、光子贴图、Light Probe等[1]。
当光从光源被发射出来后，碰到障碍物就反射和折射，经过无数次的反射和折射，物体表面和角落都会有光感，像真实的自然光。全局光照占内存是很厉害的。它属于间接照明，缩写为GI，全名为Global Illumination（全局光照）[1] 1986 年，Ｋajiya 首次将蒙特卡罗方法应用到全局光照领域，提出以建立从视点到光源的随机游动链为基础的蒙特卡罗光径跟踪算法来逐像素地生成图像。须注意的是，蒙特卡罗光径跟踪属于蒙特卡罗全局光照方法，如目前应用广泛的Phtoton Mapping 算法，生成图像的基本框架。蒙特卡罗光径跟踪的核心环节在于抽样穿过像素的光径样本，像素值即为所有光径样本光照值的均值。光径的建立过程是：在像素区域内随机地抽样一个以视点出发产生一条射线穿过射进场景，计算该光线与第一个物体的交点1y ，以1y 为起点、根据1y 所在物体表面的散射特性随机产生一个方向而形成一条射线，再求出另一个交点2y ，上述过程反复进行，在任一交点处，光径均可以一定的概率而终止。整个光径的光照值按照蒙特卡罗积分可以得到。
2007年中国天津大学徐庆老师提出了一种基于基于信息熵的蒙特卡罗全局光照的自适应抽样算法，在真实感图形生成领域里，[2]蒙特卡罗方法是计算整体光照问题的极佳选择。但是，在用基于蒙特卡罗的全局光照算法生成的图像中，当没有足够多的采样量的时候，存在大量的噪声。自适应抽样方法是减少这种噪声的一种很好的方法。该文提出了一种新的基于信息熵的自适应抽样算法。实验结果表明，该方法的效果优于香农信息熵等经典方法。
2来源
1946年，美国拉斯阿莫斯国家实验室的三位科学家John von Neumann,Stan Ulam 和 Nick Metropolis共同发明，被称为蒙特卡洛方法。它的具体定义是：在广场上画一个边长一米的正方形，在正方形内部随意用粉笔画一个不规则的形状，现在要计算这个不规则图形的面积，怎么计算呢?蒙特卡洛(Monte Carlo)方法告诉我们，均匀的向该正方形内撒N（N 是一个很大的自然数）个黄豆，随后数数有多少个黄豆在这个不规则几何形状内部，比如说有M个，那么，这个奇怪形状的面积与正方形的面积之比便近似于M/N，N越大，算出来的值便越精确。在这里我们要假定豆子都在一个平面上，相互之间没有重叠。蒙特卡洛方法可用
于近似计算圆周率：让计算机每次随机生成两个0到1之间的数，看这两个实数是否在单位圆内。生成一系列随机点，统计单位圆内的点数与总点数，（圆面积和正方形面积之比为PI:1，PI为圆周率），当随机点取得越多（但即使取10的9次方个随机点时，其结果也仅在前4位与圆周率吻合）时，其结果越接近于圆周率。就数学特性而言 ,蒙特卡罗方法的发展可以追溯到 18 世纪著名的蒲丰问题. 1777年 ,法国科学家蒲丰(Buffon)提出用投针试验计算圆周率π值的问题. 这里我们用蒲丰问题来初步说明蒙特卡罗方法的基本原理和解决问题的基本手续.蒲丰问题是这样一个古典概率问题:在平面上有彼此相距为 2 a 的平行线 ,向此平面任意投一长度为 2 l 的针 ,假定 l < a ,显然 ,所投的针至多可与一条直线相交 ,那么 ,此针与任意条平行线相交的概率可以求出 ,由下面的分析可知 ,此概率与所取针长 2 l、平行线间距 2 a 有关 ,并且包含有π值. 在这里 ,任投一针的概率含义有以下三点 :(1) 针的中点 Ml在平行线之间等概率落入 ,即 Ml距平行线的距离 x 均匀分布在区间[0 , a ]之内; (2) 针与线的夹角θ均匀分布在区间-π2,π2之内;(3) x 与θ互相独立.在某一条平行线上的 x 轴 ,不失一般性 ,假定针的中心处于图示中的 x 轴上. 由于对称性 ,我们只需分析针中心处在 x ∈(0 , a) 范围的情况即可. 令探针中心的坐标值为x ,显然 ,只有 x ≤l 时才可能发生相交的事件. 我们来分析在条件 x ≤l 满足时 ,针与线相交的概率 :只有当θ≤θ0 = arccosxl时才能相交 ,且相交的概率为P1 =2πarccosxl(1)下面再来分析针中心位置在轴上的分布 ,显然 ,这是一个均匀分布 ,即针中心处于区间( x , x + d x)内的概率为d P2 =d xa (2)这样 ,一次投掷 ,针中心落入( x , x + d x) 且与线相交的概率为d P = P1d P2 =2πaarccosxld x(3)则一次投掷 ,针与线相交的总概率为P =∫d P =∫l0πaarccosxld x =2 lπa(4)即 :π =2 lPa从(5) 式可见 ,可利用投针试验计算π值 :设投针 N 次 ,其中 n 次针与线相交 ,则可用频率值 n/ N 作为概率P 的估计值 ,从而求得π的估计值为π≈2 laNn(6)这就是早期的用频率值作为概率近似值的方法的应用实例 ,表 1 是在历史上一些有名的用投针试验计算π值的结果[2],其中针长以 a为单位。需要指出的是 ,上述由投针试验求得π
的近似值的方法 ,是进行真正的试验 ,并统计试验结果 ,要使获得的频率值与概率值偏差小 ,就要进行大量的试验[3],这在实际中 ,往往难以做到. 可以设
