2D体积光绘制算法设计

Posted on Edited on In Views: Symbols count in article: 4.9k Reading time ≈ 4 mins.

Volume2D

Preface

​ 最近玩Minecraft1.12时发现了一个极其棒的光影包，体积光（虚假的体积光，不是用光线追踪做的）做的极其漂亮，使我对这个游戏重新产生了兴趣。

Figure 1. 我的世界光影

​ 实际上，个人之前就对体积光有很大的兴趣，拍照的时候也很喜欢寻找存在"Gods' Ray"的场景，没有就将其强行用PS的径向模糊绘制出来。对于游戏内部的光影，我也很想自己实现一个光线效果（大一写的游戏Ethians alpha 1.1🔗中有阴影计算的算法（FOV shadow casting），但结果是基于栅格的，而不是基于像素的）。综合以上的想法 + 想精进一下C++ STL技术，我设计了一个这样的问题。

假设有一个点光源，在一个只有矩形障碍物的2D平面空间中，如何高效渲染场景中的阴影？

​ 这就是一个典型的渲染问题，我设计了一个渲染算法并采用C++ + OpenCV 4.5.1进行实现。

算法设计与实现

准备工作

​ 首先将整个地图进行栅格化。比如个人的实现中，一个1200 * 900的窗口，被栅格化为 40 * 30的地图，每个栅格大小为30 pixels。障碍物是基于栅格的（对于类似于Ethians Alpha 1.1这样的平面Roguelike Game适用），栅格越精细，障碍物也可以更加精细，阴影计算对应的时间消耗越大。

边界确定与划分

​ 对于矩形的障碍物，一个很自然的想法就是：对其边界进行管理，阴影投射的产生是由于边界对光线的截断作用。但是对于一个w * h的栅格化地图，每一个栅格存在4条边界（不考虑共用边界时），直接对所有边界进行操作，时间复杂度将至少是\(O(n^2)\)的。显然，在这个问题中，有些边界是完全不必要存在的，我们需要在此步内计算真正可能影响渲染的边界。关于边界我们还需要其他的信息：

  • 边界的两个端点位置
  • 边界是垂直的还是水平的
  • 边界是否被遮挡，是否被处理过
  • 边界相对于光线的方向

​ 后续的计算需要依赖于上述信息。

边界的按栅格确定

​ 刚开始时我的设计有些问题，我直接使用位置进行遍历（按照水平 / 竖直两个方向，并行），能够快速求出所有的边界。规则如下：

  1. 设置occupancy map（栅格占用2D数组），为0则表示没有障碍物，为1表示有障碍物
  2. 边界所在的位置 水平边的上方一格与下方一格occupancy map值不相等，竖直边则是左右块的值不相等
  3. 可以快速确定两个方向的所有边

​ 但是这样存在一个问题，我确实可以省略一些非边界位置，比如两个相邻障碍物块之间的边界或者两个空气方块之间的边界，仍然存在一些无用边界无法被剔除。如下图所示：

Figure 2. 冗余边界示意图

​ 实际上背对光源的边界对投影毫无帮助，计算时可以忽略。这样既可以节省内存，也可以节省计算时间。而如开始的设计，按照边界的水平 / 竖直方向进行边界计算无法获知某一条边界在栅格上的位置，也就无法获知其是否能影响投影结果。

​ 按照栅格进行确定，也就是遍历地图上所有的栅格，边界在栅格上是有其相对位置信息的，而栅格相对光源也是可以获知位置信息的，这样可以计算出边界是否会影响投影结果。具体的规则如下：

  • 在光源正上方的栅格，只有面朝光源的这一条边界是有意义的
  • 在光源侧面的栅格，根据光源的相对位置，最多选择两条面朝光源的边界
  • 首先计算栅格相对光源的位置：分为8种情况：
enum名称 意义 二进制编码 16进制表示
TL 左上 0000 0x00
DT 正上 0001 0x01
TR 右上 0010 0x02
DL 正左 0100 0x04
DR 正右 0110 0x06
BL 左下 1000 0x08
DB 正下 1001 0x09
BR 右下 1010 0x0a

​ 设置编码的原因是，可以根据逻辑运算快速求出栅格或者边界是否属于某个方向（例如上方 包括左上 正上和右上，或者正方向，包括四个正向）。

  • 只有正方向的栅格存在一条有效边界，其余栅格均存在两条有效边界，如下图所示：

Figure 3. 有效边界示意图

​ 根据边中点与光源的相对位置可以计算出边的方向（orient），边的orient图：

Figure 4. 边方向计算图，中部灰色方块是光源

​ 边界计算是分块并行的。由于我使用的机器为4核的，使用了4个线程（也就是依图像中心划分为四个象限，并行计算，最后合并到一个vector内）

边界重新计算

​ 光有边界是没有用的，我们需要通过边界来计算渲染问题，前面的步骤只是在减少不必要的边界计算以及渲染框计算。关于阴影区域的一个简单想法是：投影是存在先后顺序的，距离光源近的边界必然是需要被预先处理的，并且在距离近的边界投影完成之后，可能导致其他边界被遮挡。被完全遮挡的边界是不需要参与后续计算的，这是因为更远的边界被完全遮挡后，其投影的阴影部分必然小于遮挡此边的边界的投影阴影区域（很绕？）。

​ 既然存在先后顺序，就必然涉及到排序。为了避免进行排序，实现中直接用了一个小顶堆（C++ <queue> 头文件中的 priority_queue）。可惜的是，priority_queue的特性与queue相似，没有迭代器，无法遍历，所以priority_queue存放的是边界类的指针，指向vector中的某个边界类。

1
2
3
4
5
6
7
struct EdgeCompFunctor{
    bool operator() (const Edge* const e1, const Edge* const e2) const {
        return e1->getDistance() > e2->getDistance();
    }
};

std::priority_queue<Edge*, std::vector<Edge*>, EdgeCompFunctor> edges;

​ 边界到光源的距离在计算边界的时候，按照中点到光源的欧式距离已经计算过了。

​ 边界重新计算主要解决两个问题：

  • 完全被遮挡的边界，设置其内部的valid flag为false，之后出队时如果遇到标签无效的边界直接跳过。
  • 部分被遮挡的边界，需要重新计算其端点。这个才是最重要的部分。

​ 如何判定一个Edge在某个距离更近的边界产生的阴影内部呢？可以使用相对角度进行判定：绝对角度坐标（比如极坐标）是不好的，不管使用什么表征（除非四元数），都会存在奇异性，比如极坐标的x正向实际分割了0°与360°，这会让角度大小判定变得复杂。

Figure 5. 遮挡性计算

​ 如上图所示，假设我们看左上角那条边界。首先对于正在投影的边界（Projecting edge），其遮挡范围有个角度θ。那么有如下规则，假设一条需要判断的边界到到两条边界的角度为\(\theta_{ij},i,j=1,2\)。其中 \(\theta{ij}\)表示边界端点i到光线j的夹角：

  • 某端点与光源连线到两束光线的角度均小于光线夹角θ：说明这个端点在不可视范围内
  • 某端点到光源连线到两束光线的角度中，至少有一个角度大于θ，说明这个端点在可视范围内。

​ 如果我们通过计算方向向量，使用方向向量进行内积的计算，内积的结果就是端点和光线夹角的cos值，显然，cos值越接近1（越大），对应端点连线 / 光线的夹角越小。（注意这内积值是cos值，cos在0-\(\pi\)是减函数，开始忽略了这一点，直接“越小越好”导致了爆炸）。

​ 得到了夹角之后有如下规则：

  • 两个端点均在不可视范围内的直接设置valid = false，之后不再处理
  • 其中一个端点在不可视范围内的，计算此端点的更新值（恰好在光线上的点）。

​ 关于端点更新到什么位置：简单的想法是，端点更新到离他近的光线上（夹角小的光线上）。我之前这样做的时候引起了问题：假如夹角小的那条光线对应的位置在障碍物内部或者在空气方块内部（总之不在边界上），就会出现问题。所以需要判定：优先投影到夹角小的光线对应的更新位置上，如果occupancy map指示对应位置不是边界，则投影到另一条光线位置。

​ 那么整个流程应该是：

  • 取堆顶，堆顶指针指向的边界为当前投影边，计算光线方向向量，pop
  • “八叉”搜索（个人叫法，现在没有用八叉树实现，但是实际应该是可以用类似结构实现的），搜索需要更新的边，进行更新
  • 更新就是判定是否要更新端点或者valid flag值，此处可以并行
  • 所有需要更新的边更新之后，确定渲染框

八叉搜索

​ 由于每条边都包含方向信息，而在某条边投影时，并非整张地图上的边都有可能更新。更新只发生在与投影边相同方向（或是相近方向）的边中。规则是：

  • 如果是正方向上的边，比如投影边是正上方的，由于正方向障碍物的阴影覆盖面广，需要搜索正上方，左上方，右上方的所有边。也就是说，正方向的投影边需要搜索一个大方向（包含3个小的方向）
  • 如果不是正方向上的边，只需要搜索边集合（vector）中与投影边相同方向的边即可。

​ 这种方法还只是基于一维vector的全遍历，实际可以使用unordered_map，以方向编码为key，value为vector，只搜索部分vector。

渲染框确定

​ 个人认为，本投影问题实际上是：每一条边投影时产生图像上的一部分阴影部分，每投影一条边时就可以计算一个渲染框，只需要将此渲染框内填充满阴影（的颜色）即可。如下图所示，给定一条边界，需要计算此边界产生的阴影区域，也就是需要获得光线（或者阴影边界线）与地图边界的交点。如果得到交点，经过排序之后，可以直接使用OpenCV提供的fillConvexPoly进行凸多边形的颜色填充。

Figure 6. 渲染框计算示意图

​ 如果需要解边界上的点位置，我们需要如下信息：光源位置\((x_c, y_c)\)，光线向量\((v_x,v_y), (u_x,u_y)\)，边界：\(x=0,y=0,x=x_M,y=y_M\)，并设对应边界为：\((x_b,y_b)\)那么可以根据： \[ (x_c,y_c)+t(v_x,v_y)=(x_b,y_b) \] ​ 在边界上\(x_b,y_b\)中必然有一个是已知的，可以解出t，得到未知的边界坐标分量。实际上，一条射线（一个向量）可能与两个边界（相邻的x / y方向边界）相交，得到两个解，从两个解中选择合理值（两个分量均在边界范围内）作为解。

​ 此外，得到了边界交点并不代表着渲染框完全选取好了，由于边界交点并不一定在同一条地图边界上，可能需要增加额外的地图corner为渲染框角点。有如下三种情况：

Figure 7. 渲染框增加地图边界点的三种情况

​ 在出现需要增加点的情况下，需要人为设计一些规则，讨论如何判定进入这三种情况中的哪一种情况：

  • 加入两个点的情况出现时，特征的表现是：两个解的某个分量差的绝对值等于地图某个方向的长度。
  • 加入一个点的情况出现时，特征的表现是：两个解的对应分量不会相等。

​ 渲染框需要emplace到某个二维vector中。此后使用4个线程同时绘制渲染框即可（地图内100个随机障碍块时，绘制时间大概是1.5ms）。结果如下图所示：
随机地图渲染框绘制 非随机地图渲染框绘制

美化

​ 美化主要做了两个事情：可视范围确定 + 光强衰减。这两个事情可以合并起来处理。开始我使用线性衰减，设置阴影的色彩为(20, 20, 20)： \[ max(255-\frac{255-20}{R_{max}}R,20) \] ​ 此式说明，光强度线性衰减到\(R_{max}\)后，维持在最低光强值处。线性衰减的效果并不好，可见范围内较亮位置比较小。而改换成较为符合物理学的光强衰减公式（平方反比）后，效果较好： \[ max(\frac{255}{(aR+1)^2},20),where\;a=\frac{\sqrt\frac{255}{20}-1}{R_{max}} \] ​ 美化后的结果如下两张图所示：
随机地图渲染框绘制 非随机地图渲染框绘制

结果与代码

​ 代码见[Github🔗Algorithm Plus/cpp/volume]，代码依赖：OpenCV 4.5.1，OpenMP，C++ 11（或以上），CMake。

​ 加入了平滑运动：光源的运动不是按照栅格进行的，而是按照像素进行的，运动过程比较平滑，可以通过键盘操控光源的移动。输出的gif如下：

Figure 8. 体积光与光源运动

Do you like what you♂see ?