本文是Gino van den Bergen写的EPA[1]论文解析。
GJK算法只能获得两个不相交物体之间的距离以及最近点对，或者判断两个物体是否相交。但在相交时无法确定穿透深度和挤出距离。使用EPA可以解决这个问题。
本论文的大部分前置知识都基于Gino之前写的GJK优化论文。建议先看。此论文中也有对这些知识的回顾，但本文不再赘述。
解析
整篇论文最核心的只有第四章述说了EPA算法。其他章节几乎都是对GinoGJK的回顾。
定义CSO(configuration space obstacle)为两个物体$A$,$B$的Minkowski差$A - B$。
$$ p(A, B) = \inf \{||\vec{x}||:\vec{x} \in A - B\} $$这里$\inf$是infimum（下确界）的意思。
$$ p(A, B) = \min \{||\vec{x}|| : \vec{x} \in \operatorname{co}(A - B)\} $$其实就是Minkowski差中边距离原点最近的距离。
接下来是计算穿透深度：
算法的输入是GJK的结果：一个包含原点的Simplex。
算法是迭代完成的。每次迭代中，选择距离原点最近的面上，指向原点的反方向$\vec{v}$作为支撑点查找方向找到新支撑点$\vec{w} = S_{A-B}(\vec{v})$。
新增点时，最短的边分裂成两条新边（2D情况）
在$R^3$下新增点时，旧面不仅要删除使用新的三个面替代，原始的polyhedron有可能因为此操作变为凹的。这时要删除其他面直到变为凸的，然后使用其他面的边和新点$\vec{w}$进行缝合(Suture)构造新polyhedron：
下图展示了构建新面时可能导致多个面被删除的情况（一般发生于球或球扫略体和凸几何体之间，纯粹的凸几何体之间不会发生）：
这里左图中上面两个面都会被删除。
而如何选择距离原点最近的边/面呢？这里可以用到优先队列，使用最近距离排序。每次都使用队头的边/面即可。
那么算法何时停止呢？对于Polyhedron之间的操作，只需要当新支撑点仍旧在当前Polyhedron中就行。这说明已经找不到新点了，算法结束。
$$ |\vec{v}| \lt r \lt \vec{v}\frac{\vec{w}}{|\vec{v}|} $$$$ \vec{v}\frac{\vec{w}}{|\vec{v}|} - |\vec{v}| \le \epsilon $$即可。这里$\epsilon$是用户给定的容差值。
实现中为了避免开方，一般比较这两者的平方值。
注意，这里$\vec{v}$是原点到当前支撑点的向量，长度不是1。
上下界的差值，其实就是CSO中边到原点最近距离，减去 当前膨胀的Simplex的边到原点距离。这个距离会随着算法的每步逐渐减小，直到等于0（polyhedron情况）或者小于容差$\epsilon$（二次曲线情况）。
所以这里不需要像GinoGJK那样保存历史上所有迭代步骤中的最大下界和最小上界。就用当前步骤中的值就行。
3D情况下的优化
在3D情况下且含有二次曲面时，每次加新点时，需要将一个三角面分裂成3个新三角面。这不太好，因为：
- 反复分列三角面后，整体的膨胀Simplex会呈现出长条形。这就有可能导致数值精度问题（详见GinoGJK论文和GJK原始论文）
- 由于三角形的边永远不会断裂（总是在原有边上连接新点变成面），当穿透深度接近初始多面体的边缘时，算法将很难接近表面。新增的点$\vec{w}$可能落到膨胀Simplex的某个边上。这可能导致之后的新点$\vec{w}_i = \vec{w}$从而导致算法死循环。
论文的处理方法是分裂三角面的时候同时分裂他们所在的边。对每条边$e$，使用边上离原点最近的点$\vec{v_e}$作为支撑点搜索方向找到$\vec{w_e} = S_{A-B}(\vec{v_e})$。然后用此点将边分裂成两条：
但是，如果边已经是CSO的边界了就不需要拆分了（当CSO有扁面时就会发生）。这种情况当且仅当$\vec{v_e}\cdot \vec{w_e} = ||\vec{v_e}||^2$时会发生。所以如果检测到这个条件，就不要拆分边。
但实际操作中不会使用这个算法，而是使用前面说的面缝合方法更好（本质上也是打破旧边）。
接触点对(Contact Points)
$$ \vec{v} = a - b. a \in A, b \in B $$这两个点可以作为接触点返回给物理引擎。