征 人 怨
[唐代][柳中庸]
岁岁金河复玉关，朝朝马策与刀环。
三春白雪归青冢，万里黄河绕黑山。

今天来介绍一下Intel在GDC 2013上关于light shaft的实现算法，这里是PDF链接以及源代码链接

1. Introduction

Atmospheric light scattering is an important natural phenomenon, which arises when light interacts with the particles distributed in the media. Rendering such effects can be exploited by many applications, such as computer games, to greatly improve scene realism. To accurately compute scattering contribution, a complex nested integral has to be solved for each screen pixel. Due to the complexity of the computations involved, achieving natural-looking atmospheric scattering effects at interactive frame rates is a challenging problem.

大气散射来自于光线跟传播介质中的粒子的碰撞反射，如果想要精确的计算散射效果，就需要对屏幕中的每个像素进行一次积分运算，因此，实时的大气散射效果是一个非常大的挑战

The technique demonstrated by this sample combines a number of recent approaches for rendering light scattering effect in participating media as well as several optimization techniques. It exploits epipolar sampling [ED10] to significantly reduce the number of samples for which computationally expensive ray marching is performed, while ray marching itself is accelerated with the 1D min/max mipmaps [CBDJ11]. This enables achieving high quality rendering at interactive frame rates on Intel processor graphics.

本文给出的demo采用了一系列比较新的实现方法以及相关的优化策略，比如使用了极坐标采样方式来降低ray marching的采样点数目，使用一维的min/max mipmap来加速ray marching方法等，通过这些方法，可以在Intel的显卡上实现可交互的大气散射效果。

Since the technique implemented in this sample is primarily based on concepts presented in [ED10] and [CBDJ11], it is highly recommended to read these papers.

在看完这个demo之后，强烈建议再去读读本文的两篇参考文献（[ED10] and [CBDJ11]）。

2. Light scattering basics

There are three main phenomena that affect the light as it goes through the media:

• Absorption is when electromagnetic energy is transformed to other forms of energy for example, heat

• Emission is radiating electromagnetic energy

• Scattering is changing the direction of light

光照与介质相遇之后，一共有三种情况会影响到输出光：吸收、自发光以及散射

Emission and absorption can be neglected for air, so we will consider effects of scattering only. Theoretically, a photon can reach the eye after a number of scattering events. Complete equation describing light transport in participating media which takes multiple scattering into account is very hard to solve. So in real time rendering single scattering model is usually used which assumes that the light is scattered only once in the media and no further scatterings are taken into account.

在大气中，自发光与吸收属性可以被忽略，因此只需要考虑大气对应光线的散射作用。理论上，抵达人眼的光束在传播期间散射的次数要远大于1，不过想要通过公式来完整的描述光线在大气中的多次散射过程是非常困难的，所以通常情况下为了简化处理，只考虑一次散射，也就是光线从光源发出后只被大气散射一次就进入人眼的情况（Single Scatter & Multiple Scatter）。

Scattering effects affect the scene objects in two ways which account for phenomenon called aerial perspective (fig.1). From one hand some portion of light Lo initially emitted from the object is out-scattered due to interactions with particles. From the other hand, some sun light is scattered towards the camera. Thus the final radiance measured at the camera is a sum of two contributions: attenuated object radiance and inscattering:

平常我们看到的大气透视效果主要来源与两种大气散射活动：其中一种是从物体发出的光线（准确来说是反射出的光线）经过大气散射后进入相机（或者人眼）的部分，这一部分叫做out-scattering（之所以叫out-scattering，是因为本来是正对着相机的场景，但是光线在直线传播的过程中由于散射而偏离了原路径，从而导致物体可见性降低，看起来像是蒙上了一层雾）；另一种是从太阳发出的经过大气散射后进入相机（人眼）的部分，这一部分叫做in-scattering（没有阳光，就没有大气透视，in-scattering的命名可以参考out-scattering，由于偏离了阳光的直线传播路径而进入相机的光线），其计算公式给出如下，前面部分表示Outscattering，由物体本身输出光强Lo以及传播过程中的衰减F_ex相乘而来，后面部分表示Inscattering：

(1)

Fig.1: Scattering in participating media creates the effect of aerial perspective

Note that light intensity L is the function of 3 variables: the position in space x , direction v and wavelength lamda

.

当前点接收的光强L实际上是三个变量的函数：当前点的位置x， 光线的方向v以及光线的波长lamda。这三个变量组成了下面影响光强的两个函数：散射系数与相函数。

Light scattering in some point in space is described by two parameters: the scattering coefficient

which depends on position and wavelength and the phase function

which takes view and light directions as the arguments. The scattering coefficient describes which portion of light is scattered per unit length in any direction. The phase function describes the angular distribution of the scattered light. Since each scattered photon must go somewhere, the phase function must be normalized such that

where integration is performed over the whole set of directions

空间中某个点的光线散射可以通过两个变量来描述：其一是我们所说的散射系数

，这个散射系数跟当前点所在的位置x以及光线的波长有关；其二是所谓的相函数（Phase function）P(v,l)，这个函数跟光线方向以及观察方向有关。那么这两个变量有什么含义呢？散射系数描述的是沿着给定的传播方向，每单位长度散射出去的光强能量，而相函数描述的是不同的观察方向其散射的光强分布，通常来说，为了保证能量守恒，一般会对相函数进行归一化处理，即对光线散射的所有方向进行积分的话，得到的数值应该为1：

积分范围为所有散射方向。

Now let us consider the two parts of equation (1): the extinction

and the inscattering

Extinction

The amount of light scattered per some differential ray section

is proportional to the light intensity, the scattering coefficient and the section length:

光线沿着某个方向传播过程中散射失去的光强与光的本来强度以及传播距离成正比，其公式给出如下：

(2)

Since scattered amount of light is removed from the initial intensity, light attenuation by out-scattering is given by the following differential equation:

而沿着光线传播方向的光强衰减可以用如下的公式表述：

(3)

Integrating this over the whole path from the camera position

to the object

will give us the following formula for the attenuated light reaching the camera:

对上面公式沿着相机位置到物体原始位置连线进行积分，就能够得到如下的衰减能量总和（指数部分怎么来的？d(ln(f(y))) = 1/f(y) * df(y)）：

(4)

where

is the radiance at the end of the ray (emitted by the object). Since in general scattering coefficient

is not constant and varies along the ray, there is no closed form for integral (4).

换一种写法：

L(C, v, lamda) = Lo * F_ex(C, O, lamda)

这个公式中，Lo指的是光照射线出发点（物体身上）的光强，F_ex(C, O, lamda)为从O点传播到C点过程中光线的衰减系数。由于通常情况下，散射系数

是一个随着光线位置而变化的变量，因此这个积分公式并没有闭合解？

Optical depth or thickness along the path from point A to B is given by the following equation:

这里定义从光线传播路径上的A点到B点的光学深度或者光学厚度为：

(5)

Extinction coefficient is related to optical depth as follows:

衰减系数用光学深度来表示，可以写成如下形式（可以看到，衰减系数是指数形式的，这就是为什么在渲染大气的时候，指数雾的来历）：

Inscattering

Inscattering is more complex to compute. Let us again consider some differential ray segment

(fig. 2). The total amount of light scattered at this point is given by (2), but now we consider the sun light scattered towards the camera. It is proportional to the sun intensity at this point and also must be modulated by the phase function to get the fraction of light which is scattered in exactly the view ray. To account for shadowing we also need to introduce visibility term

which equals 1 if point

is not in shadow and 0 otherwise. Thus, differential amount of light scattered towards the camera is given by the following equation:

Inscaterring相对而言要复杂一点，跟Outscattering一样，我们来进行微观切片研究——考虑ds长度距离范围内的Inscattering。点x处的Inscattering与这个点的阳光强度有关，也与当前点的相函数p(v,l)有关（由于光照方向与视线方向是存在角度偏差的，所以需要添加这一项），此外考虑阳光可能会被其他物件遮挡，还需要引入V(x)项（为什么Outscattering不需要考虑这一项？那是因为Outscattering总是从可见的像素出发，因此不会出现不可见情况），用以判定当前点是否处于阴影中（1 for lit，0 for shadow），差分形式的Inscattering光强公式给出如下：

Fig.2: Inscattering contribution from differential ray segment

This inscattered light is attenuated before it reaches the camera. If we denote current position on the ray by

then the total inscattering is given by integrating differential inscattering over the whole ray:

inscattering光强也是需要考虑光线在抵达相机的过程中的损耗，如果我们定义某个点P为传播路径上到相机位置C的距离为s的点：P = C + v * s，那么最终的inscattering的光强积分公式给出如下（此公式可以理解成从O到C的这一段距离内的所有Inscattering之和，而这一段距离上任意点P的Inscattering等于此点的Inscattering数值dL_insctr与从P到C这段距离的衰减exp(-T(P,C,lamda))相乘）：

Or

(6)

Scattering properties of air

Air is usually modeled as a mix of two types of particles: molecules and aerosols. Rayleigh scattering theory describes scattering on molecules with diameter

. The scattering probability depends only on the angle

between the light direction and the scattering direction (fig. 2). Normalized phase function for Rayleigh particles is given by the following equation:

空气中的散射粒子主要可以分成两种：尺寸较小的molecule（分子）以及尺寸较大的aerosol（雾化粒子）。瑞利散射主要发生在粒子半径小于0.1光波波长的分子粒子层面，其散射的概率只取决于光线方向与散射方向之间的夹角theta，其归一化的相函数公式可以给出如下：

(7)

Scattering on air molecules is wavelength-dependent and short wavelengths are scattered approximately 10 times as much as long wavelengths. This is why the sky is blue.

瑞利散射强度跟光波的波长的四次方成反比，因此短波光的散射强度大概是长波光的十倍以上，导致洁净（晴朗）的天空颜色为蓝色，因此其相关的参数如散射系数以及相函数等都是以RGB来描述的。

The scattering on aerosols is more complex and is described by Mie theory. In atmospheric scattering, Mie phase function for haze is commonly approximated with the Henyey-Greenstein phase function:

雾化粒子层面的散射可以通过米氏散射理论来描述，米氏散射与波长之间的关系比较小，因此可以通过单一的数值而非RGB来描述其相关的参数，在大气散射理论中，米氏散射通常会使用Henyey-Greenstein相函数来对薄雾的散射强度变化趋势进行描述：

(8)

A detailed derivation of scattering coefficients for Rayleigh and Mie particles can be found in [PSS99], [NSTN93] and [HP02]. We will be using the following values:

关于两种散射理论的相关知识可以直接翻阅参考文献，这里只给出直接选用的参数值（使用什么散射模型决定的是积分公式中的参数如散射系数以及相函数等是如何选取），注意在使用之前需要根据不同的场景对参数进行调整：

Note that these values must be adjusted to match the scene scale before using.

在实际计算使用的时候，有如下的公式（对于均匀介质而言，衰减函数可以用散射系数乘以传播距离来表述，其中散射系数需要考虑两种散射模型的情况，也就是二者相加；而经由散射系数调制后输出的相函数则需要将两种模型的调制相函数相加而求得）：

对于各向同性的均匀介质而言，P_m(theta) = 1/(4 *pi)，各向异性的米氏相函数有如下关系：

Assumptions

Since integral (6) is very complex to compute, a number of simplifications are usually made. We will follow [HP02] and assume that that

1. Scattering coefficients do not depend on position in space (homogeneous media):

2. Sun intensity is constant:

由于公式6的积分过于复杂，因此在实际使用中经常会进行简化处理，这里仿照[HP02]给出两个假设：

1.散射系数与位置无关：

2.阳光强度不随位置变化：

These simplifications are reasonable for rendering the scattering effects at the ground. For more general solutions refer to [NSTN93], [BN08].

这些简化处理对于在地面上观察的天空来说是非常合理的（如果是在天空上观察的话，这些假设就不存在了？），对于更为通用的简化处理，可以参考对应文献。

Under these assumptions equation (5) for optical depth simplifies to the following:

简化后的公式5公式6给出如下：

(9)

Where

is the distance between points

and

Now we can rewrite equation (6) for in-scattering:

(10)

If we drop visibility term

for the moment, we will be able to solve integral (10) analytically:

如果不考虑光照的可见性V（这个操作是否合理？），那么还可以继续简化：

(11)

If we introduce the following notations:

(12)

(13)

then (11) can be rewritten as follows:

(14)

上述这个公式还有另一种表述方式：

这个公式是Hoffman and Preetham推导所得的分析式散射公式，其对于平行光而言是比较合适的，对于点光等局部光照，上述公式就不再适用，准确来说，是无法得到闭合分析解（为什么呢？），不过还是可以推导出一个半分析的解法：

其中相函数还是一个cos项，可以很容易计算出来，相函数之后的分母项是光源到散射点的距离（L-P）^2,分子指数高亮部分则是从L到P的距离+从P到C的距离（注意Sc是一个带符号的数，因此虽然公式给的是-Sc，但是实际上Sc是一个负值），从从这些符号解析可以看出，点光的散射公式主要与三个参数有关，h，Sc以及s（为什么公式中给的是So呢？因为积分区间是从Sc到So）

这个公式的计算还是有点复杂，通常在实现中，会将So为无穷大，以h跟Sc作为两个变量离线生成一个二维贴图，之后在运行时实时采样：

在计算对应的点光散射积分时，就可以应用如下的公式进行：

注意，之所以需要在L[h, So]前面乘上一个散射损耗，是因为离线烘焙的结果都是以对应的距离作为光源垂直投影点来进行的，在这里需要减去的实际上是光源以Sc作为垂直投影点而对应的从So到无穷远处的积分，因此需要乘以这个距离带来的损耗（其实也可以理解成从O点到C点之间的传播损耗）。如果考虑遮挡关系的话，那么就需要将上述公式分段进行：

Since there is no in-scattering contribution in shadowed region, integral (10) can be re-written as a sum of contributions from lit sections only (fig. 3). If we subdivide the ray into the lit sections

, we will be able to rewrite (10) as follows:

对于平行光而言，就不需要借助查表了，可以直接根据分析式公式求取散射光照：前面是假设移除遮挡项V之后才得到公式14，如果不移除的话，那么公式10可以改写成只对光照区域进行的分段积分：

(15)

Fig.3: Partitioning view ray into lit sections

Using notations (12) and (13), equation (15) can be rewritten as follows：

用公式12与13代替其中的复杂项，得到公式16：

(16)

Using (16) we can now formulate our initial algorithm for calculating inscattering integral:

根据公式16，我们就可以开始进行我们的inscattering积分算法初始化了：

1. Subdivide the ray into N segments（将光束分割成N段）

2. Set up

(this is

)（相关参数初始化）

3. For each segment i do the following:（对于每段光照区域）

a. Compute [图片上传失败...(image-d5c6b2-1569853932818)]

image.png

where

is the distance to the end of the current ray section（计算CurrI.rgb，其中d_i指的是到当前光照区域段末端的距离，C是相机所在位置，Ei指的是第i个segment的End端点）

b. If current section is not in shadow, then

（如果当前区域段未被遮挡，那么就有这样的计算方式）

c.

（这里将E_i-1当成了Si来处理）

4.

Algorithm 1: Computing in-scattering integral.

3. Epipolar sampling

To apply volumetric lighting effects, we need to cast a ray from the camera through each pixel and execute Algorithm 1, which is too computationally expensive. So it is necessary to find a way to reduce the number of computations involved. Light shafts seen on the screen has special structure: they all emanate from the position of the sun on the screen. Engelhardt and Dachsbacher [ED10] noticed that the inscattered light varies orthogonally to these rays, but mostly smoothly along them. To account for this property they proposed an efficient sampling scheme. Their idea is to locate ray marching samples sparsely along epipolar lines going from the sun position to the screen borders with additional samples placed at depth breaks (fig. 4). Since light intensity varies smoothly along the rays, the intensity can be linearly interpolated from sparsely placed ray marching samples.

想要实现体积雾效果，就需要从相机向着屏幕内的每个像素投射出一条射线，并对每个像素按照前面的算法1进行一次ray marching计算，这个过程消耗过高，想要实现实时渲染的话就必须进行优化。不过屏幕上的Light Shafts其实是有一个特殊规律的：所有的光束都是从太阳在屏幕中的位置出发的。Engelhardt and Dachsbacher [ED10]还注意到inscattered光强的变化方向其实是与这些光束相垂直的（从字面上来看是这个意思，不过从实际物理来判断感觉又不像？），且大多数情况下，沿着这些光束的传播方向的inscattering光强是平滑变化的，据此可以减少大量的计算，他们的基本实现思路给出如下：

1.从太阳在屏幕中的位置向着屏幕边缘引出多条射线

2.在这些射线上找出一些关键节点（初始的稀疏采样点以及深度不连贯的位置）

3.计算这些关键点的inscattering光强

4.由于光强在这些关键节点之间的变化是平滑的，因此剩余节点的数值可以通过线性插值得到

5.将inscattering color计算出来后，跟背景进行blend

Fig.4: Epipolar sampling with ray marching and interpolation samples

The algorithm proposed by Engelhardt and Dachsbacher [ED10] consists of the following steps:

• Render the scene from the camera and from the light source

• Compute the inscattering contribution

• Sparsely locate initial ray marching samples along epipolar lines

• Place additional samples at depth discontinuities

• Perform ray marching for the selected samples

• Interpolate inscattering for remaining samples from ray marching samples

• Compute scattering for each pixel using interpolation from nearby epipolar lines

• Attenuate background and combine with inscattering

In our implementation we follow basic ideas of Engelhardt and Dachsbacher with some improvements and modifications discussed in section 5.

本文的实现算法基本上沿袭了这种思路，此外还进行了轻微的改进。

4. 1D min/max mipmap optimization

Epipolar sampling has one important property: all camera rays in an epipolar slice share the same plane. Intersection of this plane with the shadow map essentially forms a one-dimensional height map. Shadow test in Algorithm 1 is intrinsically a check if current position on the ray is under this height map or above it (fig. 5).

极坐标系采样有一个非常好的特性，从相机出发的所有射线，只要是处于同一个epipolar slice（如何定义一个epipolar slice？相机位置+太阳位置+相机出射线构成的一个面片）中的，都是共面的，那么这个面与转换到屏幕空间后的shadow map就会存在一条相交的线，这个线可以看成是一个一维的高度图，那么之前算法1中的阴影检测就可以直接通过一次贴图采样就可以求得。

Fig.5: All camera rays in one epipolar slices are tested against the same 1D height map

The property of all camera rays from one epipolar slice using the same 1D height map was recognized by Chen et al [CBDJ11]. To accelerate ray marching they proposed constructing 1D min/max binary tree for each epipolar slice (fig. 6) and using this structure to identify long lit and shadowed regions on the ray.

处于同一个epipolar slice的射线共面这个属性与一维高度图采样的这种思路是Chen在[CBDJ11]中提出的，根据这个属性，他们为每个epipolar slice都构建了一个一维的min/max二叉树（二叉树的使用方式后续会说到，大致是将整个epipolar slice对应的一维shadow map贴图按照二分法生成一个二叉树，每个元素都包含了当前区间中的最大最小值，在进行比对的时候，先按照最粗的粒度进行，如果比对结果存在交叉，就继续二分进行比对）来实现ray marching算法的加速（how？我们知道，屏幕中的像素只有在从相机到相机出射线碰到几何体这一段路程中都被遮挡的情况下，大气散射才会是0，其他情况下都会存在大气散射，其散射的强度可以根据前面的算法1来计算，而这个计算就需要进行沿着从相机出发的射线进行ray marching，前面说到大气散射的积分是分段进行的，那么我们就可以对每个积分段，计算出其最小值与最大值，通过这种方式降低段内ray marching的消耗），借助这个数据结构，可以很容易的定位射线上的点亮区域与阴影区域。

Fig.6: First level of min/max binary tree for the epipolar slice

Consider fig. 7. If the maximum of depths at the ends of the current ray section is less than the minimum depth stored in the min/max tree, then current ray section is completely lit and we can add inscattering contribution. This condition is true for section AB:

, which means that during the next four steps (because this is the second level of the tree) of the Algorithm 1, the current point will be in light. Thus instead of doing 4 iterations we can safely do just one without expensive shadow map fetches and obtain the same result.

如图7所示，如果某个射线的两个端点上的深度值（由于射线段上所有点都是连续的，那么其对应于光照空间中的深度也应该是连续的，那么最大的深度值只可能出现在端点处）中的较大的值都比当前线段区间所对应的min/max树中的最小值要小（说明未被遮挡），那么这个线段就完全暴露在光照中，就可以直接将之加入到大气散射的计算之中，而不再需要进行试探了，对应于算法1中，其接下来的四步计算中就不再需要进行四次迭代，只用一次就能够达到相同的效果，同时还省去了shadow map读取的消耗。

From the other hand, if the minimum of depths at the ends is greater than the maximum value stored in the tree, current ray section is fully in shadow and we can skip it. This holds true for section CD:

. In this case we can safely advance by 4 steps along the ray without introducing any error.

另外，如果当前射线段的两个端点中较小的深度值都要比当前min/max树对应的区间中的最大的深度值都要大，那么说明这个线段处于阴影之中，对于大气散射不会有任何贡献，可以直接跳过后续的计算。

It is also possible that neither condition is true which is the case for section EF. In this case it is necessary to go down to the next finer tree level and repeat the test. If we have reached the original shadow map at this point, we should perform the test using it.

而如果上述两种情况都不满足的话，那么就需要进行更进一步的min/max二叉树判定（将区间进一步细分，类似二分查找），将此射线段一分为二，分别进行判定，直到最细的拆分（也就是达到shadow map的像素级别，每个射线段对应的区间只包含一个像素），这就是为什么叫做二叉树方法的原因。

Note that in practice we use complimentary depth buffering, so that all checks are inverted.

注意，在实际使用的时候，我们使用的深度buffer采用的是comlimentary buffer，因此上述的所有比对测试操作应该是按照相反的方式来进行（没太懂complimentary buffer的意思）

Fig.7: Using second level of min/max binary tree to determine shadowed/lit regions

The binary tree traversal algorithm presented by Chen et al [CBDJ11] is essentially an adaptation of ray/height map intersection method described in [TIS08] where the traversal is done without recursion. We adopt the same idea in our sample with some differences discussed below. Having 1D min/max binary tree for the slice, the Algorithm 1 can be improved as shown in Algorithm 2. Note that ray marching is done in shadow map space. For this, end position of the ray is projected onto the shadow map and sampling is done along the resulting projected line [GMF09].

Chen在[CBDJ11]给出的二叉树遍历的算法实际上是[TIS08]中给出的光线与高度图相交检测算法（此算法不需要通过循环迭代）中的一个变种。本文给出的算法采用的也是这种思路，不过具体的实现有所不同（后面会给出），通过二叉树的算法，原有的算法1就可以升级成算法2，注意，在算法2中，ray marching的实现是在shadow map空间中进行的，因此在计算的时候，需要将射线段的两个端点投影到shadow map空间。

1. Project start and end points of the view ray onto shadow map, compute

（将射线段的端点投影到shadow map空间，并计算出三个对应的UV坐标）

2. Set up

（设定散射的初始值）

3. Set up

（设定初始的检测等级以及采样索引，采样索引指的是当前检测等级的第几个细分线段）

4. Set up

（设定UV为起始端点所在位置）

5. until ray is marched, do the following（开始进行循环，直到当前线段已经被完全处理完成）

5.1. if

, then

（如果当前的采样索引已经抵达当前检测等级的终点，那么就继续对等级进行递增，如果Level=0对应的是最细的划分，那么此时的Level=1应该也粗不到哪里去，感觉跟认知不符呢？）

5.2. while

（在检测等级大于0时，继续循环）

5.2.1. Compute depths

and

at the ends of the current ray section taking into account scale

of the current level step（将对应的检测等级区间上，对应的采样索引对应的细分段的端点转换到shadow map空间，得到对应的深度值，如果单个像素的跨度是1的话，那么）

5.2.2. Fetch min/max depth

and

for level

at position

（读取对应的二叉树结构中的最大最小值）

5.2.3. if

, then

, break（将端点深度与min/max深度值进行比对，其规则跟前面描述的一致，下同）

5.2.4. else if

, then

, break

5.2.5. else

（如果存在交叉，继续细分）

5.2.6. if

, then compute

by sampling shadow map at location

（如果level等于0，说明抵达了最小的分割级别，可以直接采样shadow map进行计算了）

5.3. Compute

where

is the distance to the end of the current ray section taking into account scale

of the current level step（计算I）

5.4. if

, then

（处于光照中的线段，进行散射计算）

5.5.

5.6.

5.7.

（从这个加法来看，每个level应该最多检测两次）

6.

Algorithm 2: Optimized version of the in-scattering integral calculation.

There are a number of important differences compared to Algorithm 1. Step length in Algorithm 1 is fixed, while in Algorithm 2 it is scaled by

, which is the key to performance improvement. As a result, Algorithm 1 always executes the same number of steps, while number of iterations Algorithm 2 performs depends on the complexity of the camera ray intersection with the shadow map. The most important differences are in steps 5.1 and 5.2 where min/max tree is accessed. Step 5.1 is responsible for going to the next coarser level of the tree at appropriate locations. Loop in the step 5.2 executes until it is detected that at some tree level current ray section is fully shadowed (step 5.2.3) or fully lit (step 5.2.4), or finest level is reached (step 5.2.6). Note that computational results of both algorithms are identical.

算法2跟算法1的关键区别在于以下几点：

1.检测Step对于算法1而言是固定的，而对于算法2而言，则是变化的，其长度取决于射线段与shadow map相交的复杂程度

2.在算法2中的5.1中，对检测的级别进行调整，使得下面的循环从一个比较粗的粒度进行，并根据情况逐渐细分（比如，如果这种粒度下的两个线段都是处于光照中，那么对于这两个线段所表示的区间的计算就完成了，可以开始下一个区间的计算了：二叉计算）

There are also a number of differences with original 1D min/max mipmap acceleration algorithm by Chen et al [CBDJ11]，这个算法跟原始的算法也是有区别的:

• [CBDJ11] exploits a sophisticated mathematical approach based on singular value decomposition to bring view ray-dependent terms out of the shadow test. They are also required to use a partial sum tree structure to compute scattering contributions on a ray section. In our method, we use an analytical approach that is both simpler and more accurate.

• 原算法使用了一种基于奇异值分解（singular value decomposition, SVD）的高级算法来将射线相关的项从阴影检测中剔除出去，这种算法需要使用一种“部分累加树(partial sum tree)”的结构来计算某个线段上的散射强度，而本文给出的算法则是一种分析式的算法，实现简单且更为精确

• In the original algorithm, it is necessary to execute brute force ray marching for the small area near the epipole, without using the 1D min/max mipmap, which can be expensive. In our algorithm, we do not have such problems and can process all the rays using accelerated traversal.

• 原算法在极点（epipole）位置附近的区域还是需要通过ray marching来计算散射，而没有使用一维的min/max mipmap，这样会导致消耗较高，而本文的算法则没有这种问题

• [CBDJ11] also performs nonlinear transformation of the shadow map. For directional light sources, their shadow map stores the angle to the light direction. This involves additional computational overhead. In our approach we use just the depth seen from the light source. We also construct min/max mipmap directly from the original shadow map.

• 原算法还需要对shadow map进行非线性转换，对于方向光来说，转换后的shadow map存储的是相对于光照方向的夹角，这种转换会有一定的消耗，而本文的算法存储的就是纯粹的光照深度，只需要直接从原始的shadow map中构建min/max mipmap即可

Notice that Engelhardt and Dachsbacher [ED10] tried using a 1-dimensional min-max depth mipmap in their method but for the purpose of searching depth discontinuities along epipolar lines, not for accelerating ray marching.

另外，需要一提的是，Engelhardt and Dachsbacher [ED10]也曾尝试过一维的min/max深度mipmap，不过他们是用于检测深度边缘，而非如本文一般用于加速ray marching。