Volume2D Shader Pro

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

Volume2D Pro

I. Preface

​ 觉得之前的算法太菜了，只能处理方形障碍物（虽然如果要给我的游戏用也够了），所以想着升级一下算法。近期实习刚好也做了一些类似的事情，但实习期间设计的算法很难debug（bug制造机就是我），在实习末期重新设计了一下，见Github Repo：[Enigmatisms/Volume]

Video 1. 不规则障碍物体积光算法效果

​ 不得不说，叠buff式编程真的很恶心，从实习开始到现在我都处于叠buff式编程中。

什么叫叠buff式编程

叠buff式编程指的是编写的代码不能一次性通过所有测试用例，需要一点一点测试之前没有考虑到的方面（定义来自 HQY）

II. 算法设计简介

2.1 数据表示

1
2
3
4
5
6
class Edge: public std::deque<Eigen::Vector3d> {
public:
    std::pair<int, int> proj_ids;           // 待投影点的id
    double min_dist = 1e9;
    bool valid = true;                      // 是否完全被遮挡
};

​ Edge是一个继承了std::vector<Eigen::Vector3d>的类，除了包含vector的所有特性之外，还实现了一些方法，诸如旋转数组二分查找，带奇异性的角度判定等等。Edge实际上就是每一条参与投影的边，在Edge之上有Object来进行管理。Edge是不断开的，面向光源的障碍物边界部分。

​ Vector3d在此处表示的是：x，y，角度（点到观测点形成的向量，求反正切的角度）。

1
2
3
4
5
6
7
8
9
class Object {
using HeapType = std::priority_queue<size_t, std::vector<size_t>, EdgeCompFunctor>;
public:
    int id;
    bool valid;
    double min_dist;
    std::vector<Edge> edges;
    std::pair<double, double> angle_range;
};

​ Object是Edge的集合体，除了Edge之外还封装了一些附加信息，用于判定：

  • 哪些Edge先参与投影
  • 哪些Edge完全被遮挡等等

​ Object内部有一个Edge的堆，堆结构在Volume2D中也曾使用，本次使用了双层堆，并且堆称为了临时变量（因为调试过程中发现全局堆有些问题）。

2.2 边界分割

​ 之前在做点云相关工作的时候，知道：

LaserScan内部的点都是具有方向性的，可根据两个点形成线段的法向量判定面向激光器与背向激光器的scan

​ 和Volume 2D一样，我也不希望太多无效的边界参与投影过程，进行“Back Culling”理论上可以减少一半的计算量（障碍物面向以及背向光源的部分正常来说各占一半）。故在做边界分割时，只保留面向光源边对应的点。

​ 此外由于边界是使用vector进行顺序保存的，存在以下的几种情况需要考虑：

Figure 1. 三种不同的情况

​ 最简单的显然就是：需要添加的边从front()或者中间位置开始，最多需要添加到back()处的点。这种情况下可以直接遍历添加，无需下标循环。

​ 第二种情况在开始撰写代码时考虑到了，觉得可能会有这种需要从front()到back()循环连接的情况。所以一开始设计Edge类就使用了双端队列（真的号用）。因为已知：同一个Object上由于中间有不可视（背向光源）的段，可能会将一条完整的边界分割为若干段面向光源的edges，那：front()处加入的点留在对应的edge种，而back()对应的edges则需要反向加入到front()对应edge的头部。也就像这样：

1
2
for (Edge::const_reverse_iterator rit = to_add.crbegin(); rit != to_add.crend(); rit++)
	front.push_front(*rit);

​ 第三种情况开始没有考虑到（不周啊），头部只有一个点加入。我的逻辑是不会保存孤立点的（形成Edge至少要两个点），而如果front()确实应该加入，但遍历时，front()联系的边都是背向边，那么可能会错误地丢弃front()。最后是多加入了几个判断才完成这部分。

2.3 内外投影

2.3.1 内外投影简介

​ 已知，我的算法对于Edge的管理基于类Object，其逻辑是：

  • 内投影：首先选择离光源最近的物体，计算该物体内部的遮挡（内部的形状复杂时）
  • 外投影：此物体如何影响别的物体，如何判定遮挡关系

​ 为什么要区分内外投影呢？内投影与外投影有什么关系呢？在我最初的构想中，区别挺大的，但仔细思考后发现，内外都会有如下的情况发生：

Figure 2. 两种内部遮挡情况

​ 尤其是第一种，开始时我认为第一种情况是不会出在内投影的情况中的，我开始认为：内部不会有切分一条边为两条的情况。（我对应的切分函数breakEdge开始是给外部投影实现的），但事实上是，都有可能。

2.3.2 两个设计

proj_ids

​ proj_ids是每一个Edge都携带的结构，是一个std::pair<int, int>。使用这个pair可以快速查找，此edge有哪些是需要参与后续内外投影的点。示意图如下：

Figure 3. proj_ids 使用

​ 图中蓝色点是投影形成的点，在判断外部遮挡时，显然应该由外侧点（意味着范围更大）来进行投影（也就是红色点）。也就是说，蓝色点只保存，不参与后续的投影，但是红色点与后续投影有很大的关系。蓝色点不参与计算可以减少部分计算负担。

Eigen::Vector3d

​ 为什么不好好地使用Eigen::Vector2d，反倒要使用Vector3d，保存一个角度？首先我对问题做了一个这样的假设：

我们的每一个edge，上面每一个点的角度（相对于观测点的反正切角度）都不同，并且由于做了背面剔除，在非奇异（atan函数角度从\(-\pi\)到\(\pi\)的奇异跃迁）情况下，是一个按角度递增的数组。存在奇异的情况下，是一个旋转数组，front()必然大于back()

​ 顺序化或者旋转顺序化的数据结构可以使用二分查找或是旋转数组二分查找，在障碍物表面特别不平（比如激光点云）时，可以显著加快交点搜索速度。此处我们使用旋转数组二分查找，查找投影关系：

  • 主投影边src上的点，如何投影到被投影边dst上，src的front() / back() 角度对应到dst的哪两个点之间？
  • 使用这两个点以及已知的src投影光线，进行交点计算

2.3.2 主要函数 projEdge2Edge

​ projEdge2Edge是用于投影的主要函数，此函数适用于内外投影。其主要逻辑是：

首先规定：主投影边（产生遮挡的边）为src，dst则为被遮挡的边。一般来说，主投影边的min_dist（内部点到光源的最小距离）会比dst的min_dist更小，但是也有例外。见下图。

Figure 4. 按照最小距离建立堆产生的问题

​ 上图首先选中更长的边（蓝色线连接的长边），因为最小距离长边对应最小（观测点选得好就会这样）。那么场边会先于两个实际上应该判定为更近的小障碍物进行投影，这样就会出现问题。比如：

Figure 5. 边异常消失问题

​ 可能原因是，由于开始的实现是：只要dst在src的角度范围内（角度上完全覆盖），那么dst就会被设为valid = false（完全覆盖不需要再投影）。但是如果src选错，就会出现如上问题。

​ 本函数的逻辑为：

  • 首先判定src可用投影点数为（proj_ids中有多少个大于等于0者），如果有两个，可能出现breakEdge的情况（投影产生新的Edge）
  • 如果只有一个可用点，需要判定（实际逻辑比下面简介的复杂得多，因为情况太多了）：
    • src / dst首尾两点到观测点的连线夹角是否小于90度？不小于则可能是反方向的障碍物，不应该参与
    • 判定src是否完全覆盖dst。为了避免atan角度奇异性，这里使用了基于内积的相对判定方法。具体实现不讲了。
    • 如果可能存在完全覆盖，需要反向筛查（查找dst首尾两点会被src内部那两对点“夹住”），如果存在这样的点对，才能认为是完全覆盖的。
  • 根据计算结果求解交点（省略了很多逻辑，不想讲，逻辑太复杂了，包括奇异处理，裕量处理，一些意想不到的情况）

2.4 交点求解

​ 求解两对点对应的两条直线的交点，只需要一些数学上的处理。首先我们知道，不能使用斜截式，因为 在本问题中，可能存在斜率无穷大的直线，导致病态。而另一方面，我们知道线段上一点可以使用线段的法向量表示：

直线上一点(x, y)到直线上已知一点\((x_0,y_0)\)的向量会垂直于法向量

​ 那么由此，交点可以列两个方程。假设光线发射点为\((x_0, y_0)\)，交点位置为\((x,y)\)，障碍物的edges对应两点为\((x_1,y_1),(x_2,y_2)\)，光线的方向向量为\((v_x,v_y)\)那么有： \[ \begin{align} & (u_x,u_y)=(x_1-x_2,y_1-y_2) \\ & (-v_y,v_x)\cdot(x-x_0,y-y_0)=0\tag{eq 1}\\ & (-u_y,u_x)\cdot(x-x_1,y-y_1)=0\tag{eq 2} \end{align} \] ​ 由(eq 1), (eq 2)组成两个方程，可以解出\((x, y)\)，只需判定对应齐次方程系数矩阵行列式是否很小（不可逆），如果不可逆，直接返回被投影点更近的那个点，如果可逆，那么解出的\((x,y)\)就是结果。

2.5 其他

​ 还有很多！逻辑是真的很复杂，情况很多，我不想写这个，要一一解释太麻烦了。

III. 效果一览

Video 1. 不规则障碍物体积光算法效果
Video 2. 更多障碍物下的表现

​ 边界计算结果使用截图的方式记录了一下：

Figure 6. 边界计算（demo1），图中绿色点是观测点，黄色是计算最后需要绘制的边

Figure 7. 边界计算（demo2），图中绿色点是观测点，黄色是计算最后需要绘制的边

IV. 库的使用

​ 本项目已经上传至Github，见Github库[Enigmatisms/Volume]，里面有非常详细的说明，不过是英文的。怎么说呢，关于这个问题，我想到了一个绝妙的解决办法，可惜今晚很困，写不完（老费马了）。如果有细节方面的疑问，欢迎直接联系我。

Reference

​ 关于EdgeCompFunctor这个还是有必要说一下的：

1
2
3
4
5
6
7
struct EdgeCompFunctor{
    EdgeCompFunctor(const std::vector<Edge>& _egs): egs(_egs) {}
    const std::vector<Edge>& egs;
    bool operator() (const size_t& e1, const size_t& e2) const {
        return egs[e1].min_dist > egs[e2].min_dist;
    }
};

​ std::priority_queue接收一个自定义的比较函数，由于C++高版本的匿名函数特性很不错，一般都使用匿名函数来填充这个自定义比较函数，但也可以使用较为老式的Functor写法。而此处，我更改了在Volume2D算法中使用的“保存Edge*”的实现，因为已知保存在堆中的指针没有办法正确指向vector。原因我哥已经帮我解释了：

  • 因为vector的内部存储的地址是会变的
  • 比如resize的时候 它会构造一个新的数组 把原来的数据复制进去 然后销毁之前的数组 这样地址就变了
  • 如果直接存指针 是会失效的

​ 这种携带了一个常引用，初始化EdgeCompFunctor时需要传入edges这个vector常应用的写法来自于[stackoverflow/C++ std list sort with custom comparator that depends on an member variable for the object instance]。显然，保存索引比保存指针优雅多了。