碰撞点求解（二）：V-clip 算法

[phenomLi]

上一篇我们介绍了一种简单的碰撞点求解算法：最近内部顶点法，还提到了算法的几个小缺陷。今天我们来看一种新的碰撞点求解算法 -- V-clip 算法。（我也不是很懂里面的 V 是什么意思）。

V-clip 是 box2d 里面使用的碰撞点求解算法，相比最近内部顶点法，V-clip 的求解更准确性能更好，而且弥补了最近内部顶点法的几个缺陷。

在这里不得不说一下，box2d 的作者 Erin Catto 是真的牛逼，简直大神级的存在。Erin Catto 前身是数学家，现在在暴雪工作，担任游戏引擎开发，box2d 是他业余时间写的一个物理引擎。他的 box2d 可谓是真真正正的商用级 2d 物理引擎标杆，其中独创了 V-clip，Sequential Impulses，Bilateral Advancement 等算法。V-clip 提供了准确度更高的碰撞点求解；Sequential Impulses 算法将约束求解器的复杂度降低了好几个等级，之后的绝大多数无论是玩具还是商用级的物理引擎都有 Sequential Impulses 的身影；Bilateral Advancement 更是将精确连续碰撞检测变为可能。另外，box2d 中的动态 AABB 树，island，还有各种严谨的数学公式，都证明了 box2d 在 2d 物理引擎中的老大哥地位。

V-clip

V-clip 名字虽然有 clip（裁剪），但是其核心思想并不是裁剪，而是筛选。

V-clip 有 3 个重要的概念，分别是 reference edge，incident edge （这两个我实在不知道怎么翻译）和筛选域，其中：

• reference edge：一物体上与碰撞法线 n 垂直的那一条边，也就是 SAT 中求出 n 的那一条边
• incident edge：另一物体上与 n 最垂直的边
• 筛选域：由 reference edge 划分的域，落在这个域上的顶点将被排除为碰撞点

V-clip 主要工作流程如下：

1. 确定 reference edge 和 incident edge，并将 incident edge 的两个端点加入到候选碰撞点
2. 第一次划分筛选域，为 reference edge 左右垂线的两侧
3. 将落在筛选域的候选碰撞点移除，且若 reference edge 左右垂线与 incident edge 有交点则将该交点加入到候选碰撞点
4. 第二次划分筛选域，为 reference edge 的左侧（顺时针）
5. 将落在筛选域的候选碰撞点移除

可见 V-clip 的关键是找出 reference edge，incident edge 和确定筛选域。看不懂没关系，我们举上一篇结尾的一个例子：

上一篇我提到了这种情况用内部顶点法无法解决，那现在我们来看看用 V-clip 怎么做。

Step 1

首先我们要做的是确定 reference edge 和 incident edge。现在假设我们已经用 SAT 求出了碰撞法线 n ，那么对于 reference edge 我们可以马上确定（图中黄色的线），因为 SAT 在求出 n 的同时已经求出了 reference edge，此时 reference edge 位于物体 A 。

至于 incident edge，我们可以先求出 B 距离 A 最近的一个顶点（图中蓝色的点），然后选取该点的两条邻边，分布与法线进行点乘，点乘越接近 0 的边表示与 n 越垂直，那么这条边就是 incident edge。最近点怎么求可以参考最近内部顶点法里面的方法。

现在，我们已求出 reference edge 和 incident edge ，并将 incident edge 的两个端点 v1，v2 加入到候选碰撞点里。

Step 2

接下来是进行第一次划分筛选域，我们过 reference edge 的两个端点 v3，v4 分布做一条垂直于 reference edge 的垂线。

Step 3

那么两垂线背向 reference edge 的一则即是第一次划分的筛选域，我们在下图中以灰色区域表示。

可以看到，顶点 v2 由于落在筛选域内，因此从候选碰撞点中移除。一条垂线和 incident edge 相交产生了顶点 v5 ，我们把 v5 加入到候选碰撞点中。至于如何求交点，可以看看我之前曾经介绍过一种相似三角形的方法。

Step 4

我们作第二次筛选域划分，这次 reference edge 的左侧区域成为筛选域。

边的左侧或右侧是怎么确定的呢？是根据物体的顶点顺序确定的。如图中 A 的顶点顺序为顺时针（v3 -> v4），因此此时筛选域为从 v3 出发到 v4 的左侧。如果你习惯使用逆时针顶点顺序，那么此时筛选域应该是 reference edge 右侧。

Step 5

v5 落在筛选域内，将其从候选碰撞点中移除。

此时算法执行完成，我们得到唯一的一个碰撞点 v1 。

如何确定顶点是否落在筛选域内？

其实这个问题很简单，一种方法是使用向量叉乘，box2d 使用了另一种稍微复杂一点的方法。

假设黄线为 reference edge ，虚线为筛选域的垂线。使用图中的方法，可以判断出 v1 不在筛选域内而 v2 在筛选域内。这种方法有一个很大的优点（这个优点使得 V-clip 必须使用这个方法来判断点是否在筛选域内）就是计算出来的 d1，d2 有重要的意义。

还记得上一篇最后的第二个例子吗，我们提到了一种用最近内部顶点法无法确定每个碰撞点的穿透深度的情况。然而在 V-clip 中情况不一样了，我们在第二次划分筛选域中判断两个候选碰撞点（图中红点）是否位于 reference edge 左侧（顺时针）时，因为刚好这两个点都不在筛选域，因此碰撞点就是这个两个点，所以，计算出的 d1，d2 正正就是两个碰撞点各自的穿透深度。

你可能暂时不知道为什么，但是当你熟悉了 SAT 和 V-clip 之后，就能想明白了。同时你应该注意到，这种情况下，V-clip 求得的碰撞点和最近内部顶点法求得的并不一样，说明了这个例子很好地反映了两种算法之间地差异。

[shangqingLin]

https://www.merl.com/publications/docs/TR97-05.pdf
是这里介绍的V-Clip算法吗？

[conanjunn]

膜拜大佬！请问大佬这些知识都是在哪学习的？国内能找到的这方面的教程太少了

[phenomLi]

多去google找找 外网资料挺多的 有什么疑问的也可以交流

…

------------------ 原始邮件 ------------------ 发件人: "phenomLi/Blog" ***@***.***>; 发送时间: 2021年5月11日(星期二) 下午3:30 ***@***.***>; ***@***.******@***.***>; 主题: Re: [phenomLi/Blog] 碰撞点求解（二）：V-clip 算法 (#42) 膜拜大佬！请问大佬这些知识都是在哪学习的？国内能找到的这方面的教程太少了 — You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub, or unsubscribe.

[conanjunn]

多去google找找 外网资料挺多的 有什么疑问的也可以交流
…
------------------ 原始邮件 ------------------ 发件人: "phenomLi/Blog" @.>; 发送时间: 2021年5月11日(星期二) 下午3:30 @.>; @.@.>; 主题: Re: [phenomLi/Blog] 碰撞点求解（二）：V-clip 算法 (#42) 膜拜大佬！请问大佬这些知识都是在哪学习的？国内能找到的这方面的教程太少了 — You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub, or unsubscribe.

3q，有问题请教大佬，我去学习了

[onrefy]

写的真的不错！但是看上去好久没更新了，好可惜啊……

[phenomLi]

因为之后都太忙了，没什么时间了，如果对这方面有兴趣的话，可以交流

…

------------------ 原始邮件 ------------------ 发件人: ***@***.***>; 发送时间: 2021年8月13日(星期五) 下午4:02 收件人: ***@***.***>; 抄送: ***@***.***>; ***@***.***>; 主题: Re: [phenomLi/Blog] 碰撞点求解（二）：V-clip 算法 (#42) 写的真的不错！但是看上去好久没更新了，好可惜啊…… — You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub, or unsubscribe.

[THZthz]

V-clip 的意思是 Voronoi Clip，因为它和你所说的“筛选域”有关（其实我感觉裁剪和筛选区别不大），这里只用到了点在线段上的Voronoi区域。
这个算法是由Sutherland Hodgman 多边形裁剪算法得到启发而产生的。
reference edge可以叫 参考边
incident edge可以叫 裁剪边

[Balbalnom]

受益匪浅。 不知道有没有什么算法是针对2d碰撞物体面积的？

[phenomLi]

受益匪浅。 不知道有没有什么算法是针对2d碰撞物体面积的？
碰撞物体面积是什么意思？

[Balbalnom]

想要获取两个物体发生碰撞后，它们之间overlapping的信息 (比如说碰撞盒是矩形，但里面的图形可能是一个不规则图形)。想要解决的问题其实是尝试在canvas里面实现做一个wrap text的功能。有点类似adobe的wrap text around object。

[phenomLi]

想要获取两个物体发生碰撞后，它们之间overlapping的信息 (比如说碰撞盒是矩形，但里面的图形可能是一个不规则图形)。想要解决的问题其实是尝试在canvas里面实现做一个wrap text的功能。有点类似adobe的wrap text around object。

我理解你的意思应该是求两个图形相交后相交部分的面积是吧，如果两者都是多边形的话，可以首先求两个多边形的交点，然后分别求一个多边形在另一多边形中的顶点，然后求这些点组成的多边形的面积即可。圆形的话就比较麻烦，想不到很好的办法。

[a416297338]

incident edge：并非是另一个物体的所有的边，而是另一物体穿插深度最深的点（图中蓝色的点），相邻的两边更垂直的边

[Balbalnom]

想要获取两个物体发生碰撞后，它们之间overlapping的信息 (比如说碰撞盒是矩形，但里面的图形可能是一个不规则图形)。想要解决的问题其实是尝试在canvas里面实现做一个wrap text的功能。有点类似adobe的wrap text around object。

我理解你的意思应该是求两个图形相交后相交部分的面积是吧，如果两者都是多边形的话，可以首先求两个多边形的交点，然后分别求一个多边形在另一多边形中的顶点，然后求这些点组成的多边形的面积即可。圆形的话就比较麻烦，想不到很好的办法。

看到了一些地质学方面的algorithm可以提供这种clip path的解决方案. 还挺有意思的， 但好像还是不太能处理curve shape.

• Greiner-Hormann algorithm
• Martinez-Rueda-Feito algorithm (x) 最快解决类似Boolean operations between two polygons的问题
• Sutherland-Hodgman algorithm

另外看到paper.js的库有curve的解决方案