Blog
Blog copied to clipboard
phenomLi
Comments, Thoughts, Conclusions, Ideas, and the progress.
上一篇我们介绍了一种简单的碰撞点求解算法：最近内部顶点法，还提到了算法的几个小缺陷。今天我们来看一种新的碰撞点求解算法 -- **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...
## 什么是粗检测 上一篇我们介绍了 AABB 的概念，我们可以使用 AABB 快速筛去根本不可能发生碰撞的物体，然而即使 AABB 相交检测很快，我们也不能为对每一个 AABB 进行两两相交检测，因为假如我们有 100 个物体，就需要 100 * 100 次的两两 AABB 相交检测，即使我们使用某种优化手段跳过已经检测过的 AABB 对，也需要至少 5000 多次的检测。在性能要求如此高的物理模拟中，这显然是不能接受的。我们必须在进行精确的碰撞检测前，找到一种方法来快速筛选可能相交的 AABB 对，降低检测 AABB 的规模，这个阶段就叫做**粗检测阶段**。 比如说，我们现在场景下有 6 个...
最近两个星期，都在实验室硬刚物理引擎。昨天写到了碰撞检测的凹多边形与凹多边形碰撞的判断，源用了以往的思路：将凹多边形分割为多个子凸多边形，然后再遍历两个凹多边形的子凸多边形进行判断。一气呵成地，写下了下面的代码： ```typescript for(子多边形1 in 凹多边形1) { for(子多边形2 in 凹多边2) { // 分离轴测试 SAT(子多边形1, 子多边形2); } } ``` 但是写完之后我看着它竟有点不爽，两个凹多边形，每一帧都这样搞，O(n^2)的复杂度里面再进行[分离轴](https://github.com/phenomLi/Blog/issues/23)测试？大家都知道分离轴测试是整个碰撞检测流程里面最昂贵的部分，这样很可能造成性能问题（以前没有意识到这个问题，现在想起来恍然大悟）。 那么有没有优化的办法呢？一番思考后我找到了一些苗头：两个凹多边形发生碰撞，绝大部分情况下都是各种单独某个子多边形间的碰撞，而凹多边形剩下的很大一部分是与碰撞无关的，如下图：  没错，这就是优化的切入点，所以现在问题的关键就是如何快速过滤掉这些不可能发生碰撞的子多边形。看到关键字“快速过滤”，很自然地，就想到了[包围盒](https://github.com/phenomLi/Blog/issues/22)。也就是说，我们可以对每个子多边形都创建一个包围盒，在进行分离轴检测前首先用包围盒过滤大部分与碰撞无关地子多边形。此时感觉一扇通往真相地大门就要开启了。 正当我准备开干时，脑海中又突然闪过一条重要地信息：记得之前看到过，**任意多边形都可以被划分为若干个子三角形**。这一点太重要了！换句话说，我们可以不需要再去区分凹多边形和凸多边形，对于任意的多边形，我们都把他分割为多个小三角形，然后再为每个小三角形创建包围盒即可！小三角形的粒度比子多边形要更细，也就是说使用小三角形能过滤更多无关的部分，而在最后进行的分离轴测试中，测试的只是两个三角形间的碰撞，这效率是很高的。  现在，**任意多边形间的碰撞最终都会收敛为两个三角形的碰撞**。我们现在要解决的问题便是：如何分解多边形为多个三角形？ ## 多边形的分割 其实多边形的分割算法是很简单，但有一个前提就是多边形顶点必须按照顺时针或者逆时针排序。在有序的顶点中分割三角形大致流程如下： 1. **任取多边形上一个顶点A，该点即为分割点** 2....
上个星期看可视化相关的论文，看到[一篇介绍了一种树形结构布局算法的论文](https://kns.cnki.net/KCMS/detail/detail.aspx?dbcode=CJFQ&dbname=CJFD2011&filename=CYYT201108061&v=MDEwNjJDVVJMT2ZZZVJxRmlua1VML0JKalRTZXJHNEg5RE1wNDlEWllSOGVYMUx1eFlTN0RoMVQzcVRyV00xRnI=)，算法效果图是这样子的：  该布局的规则是：子节点相对于父节点成等腰排列，即根节点位于叶子节点两端距离上方正中间。在所有节点不重叠的情况下相邻节点间距相等，所有节点均不能重叠。其次，算法应适应于任意宽度，任意深度的树。这个布局较为美观，而且空间利用率较高。 传统的树形布局通常将子节点按照兄弟节点的最大宽度分开（一个节点的最大宽度即以该节点为根的树所占的最大宽度）。这样做虽然代码上容易实现，只要在每个节点保存该子树的最大宽度即可，但是视觉上不够美观，比较浪费空间。在某些传统布局甚至限制子节点的数目。  而这种布局与传统的树形布局有很大不同，它做到了在布局上节点与节点尽可能地紧凑，而且始终保持对称性和任意子节点数目。 ## 构思 论文中只是介绍了布局的一些特点和优势，对于具体实现的思路细节并没有过多提及，说实话我第一次看到论文中的效果图，我感觉应该实现起来并不会很难，但是当时我并没有认真思考。之后隔离一天，准备动手写时我发现我被打脸了，要实现该布局，其实没有这么简单。。。。 首先，假如你有一棵树，你要将每个节点摆到正确的位置，你会发现从根往下开始一次遍历布局不行的，因为父节点的位置要根据子节点的位置而定，子节点为了避免交叉重叠，会相互隔得很开，父节点为了保持对称性，也会发生移动。而从底部往上一次遍历布局同样也行不通，因为子节点也要跟着父节点走，父节点位置改变了扫描过的子节点也需要移动。 所以，可以得出结论，只进行一次遍历是无法完成布局的（光是这点我就想了一个下午才相通，我太蔡了。。）。之后我又认真地想了两天，没错，是整整两天，没有写代码，就光想思路，终究有所收获。下面简单描述我的思路： 1. **首先，我们从上往下，先根据相邻节点间地最小间距`nodeInterval`和父子节点间地间距`yInterval`对树进行第一次布局。由于初始状态所有节点的坐标都是未知的，我们不妨把所有节点的坐标先都设置为(0，0) 。从根节点开始。人为设定好根节点的坐标 ，然后将根节点的子节点挂在根节点下，且子节点分布在根节点的`yInterval`高度下方，子节点彼此间距为`nodeInterval`且相对于根节点对称分布。递归进行此步骤，直到所有的节点都布局好。** 2. **然后，我们需要一个`hashTree`，用作将树保存到一个按层次分别的线性表中。我们将树转换到`hashTree`。效果图中的树对应`hashTree`如下：** ```typescript /** * layer [ * 0 [ node(0) ], * 1 [...
## 基础知识 对于检测精度要求高的场景。包围盒便不能满足了，需要一种更加精确的检测方法。碰撞检测系统的细检测使用**分离轴算法（SAT）**。分离轴算法是一项用于检测凸多边形碰撞的技术。 试想一下，用照明灯照射两个相交多边形到墙上，按照日常经验，无论在哪个角度照射，两个多边形在墙上的投影一定会相互重叠（绿色线段表示投影的重叠部分）：  但是，不相交的多边形在墙上的投影也可能相交：  然而，按照**分离轴定律**，两个不相交的多边形一定能找到一条轴，它们在这条轴上的投影不相交，也就是一定存在一个角度用电筒照这两个不相交多边形得到不相交的投影：  分离轴算法就是要验证： **两个多边形间是否存在这样一条轴，使得这个两个多边形在这条轴上的投影不相交，只要发现这样一条轴，即可马上判定两个多边形不相交，否则就是相交。这条轴就是分离轴。** 要实现算法，即要枚举所有可能的轴判断是否存在投影没有交集的情况，而二维空间中有无数条轴，不可能做到全部遍历。但幸运的是，两个多边形的每条边的法向量包含了这条轴的所有可能性，所以只要枚举所有边的法向量即可。即遍历所有边的法向量，看该法向量是否要找的分离轴。 对于多边形和圆形的碰撞，只要找出多边形离圆形最近的那个顶点，该顶点与圆心之间的连线就是多边形和圆形间的分离轴。 而圆形与圆形间的碰撞的判断便更简单了，只要判断两圆心间的距离与两圆半径的和的大小关系便可。 ## 算法实现 首先，要找出两个图形的所有候选分离轴： ```typescript // 获取两个图形的所有候选分离轴 // vector类型是两个点之间的向量 function getAxes(obj1: shapeData, obj2: shapeData): Array { //...
上一次讲了基于向量的碰撞求解方法，该方法基本上只适用于无方向的球体间的完全弹性碰撞，灵活性较低。今天介绍一种基于冲量的碰撞求解方法，该方法更加精确，强大，而且能模拟非弹性碰撞。 注意：该文章只涉及一定量数学，要求： - **高中向量知识** （虽然看着很多公式，但是大部分都是课本现成的物理公式，我们要做的工作只是把这些公式重新组合整理一下而已） ## 什么是冲量 **冲量（impulse）**是一个力学上的矢量，记作符号**J**用于描述物体动量的变化，冲量是一个过程量，比如一个物体t=0时动量5，t=1时动量10，那么该物体在0到1时的冲量为5。 但是我们毕竟不是搞物理的，不需要对某些概念这么深究。我本人简单地将冲量看作为 “ **一股一瞬间改变速度的力** ”，而且该“力”可以作用在物体的任何点上。这就是冲量最大的优点，如果冲量的作用点不过质心，那么物体便会发生旋转。  另外，使用冲量的另一个优点是，冲量可以很容易和力建立联系：  ## 两个小球间的碰撞 现在，我们先将问题简化，考虑两个小球间的碰撞。假设小球为**A**，**B**，如图：   其中小球**A**的质量为**massA**，碰撞时速度为**VA**，碰撞后速度为**V'A**。小球**B**的质量为**massB**，碰撞时速度为**VB**，碰撞后速度为**V'B**。**我们要求的就是改变小球速度的冲量J**，下面我们一步步来推导出**J**。 先从小球的速度入手，我们引入 **相对速度（relative velocity）** 这个概念：**A**，**B**间的相对速度即**A**的速度减去**B**的速度，即 **公式一** ：  其中**VAB**为**A**，**B**的相对速度（对于相对速度的具体理解，可以看下面的评论）。 在碰撞求解中，我们关注的是碰撞法线方向的相对速度，即**公式一**应该用碰撞法线**n**表示，也就是说，我们想知道从**A**到**B**沿碰撞法向的相对速度，得到**公式二**：...
最近因为一个可视化的项目，被导师要求去了解一些树形结构渲染相关的东西（还要做每周报告我的天）。其中有一个需求就是寻找两棵树差异的，这让我想起了React的diff算法。说起来都有好久没有去了解前端相关的东西了，现在看起来都有种与时代脱节的感觉。 React的diff其实大致就是虚拟DOM树的递归遍历，我在之前的issue已经写过虚拟DOM相关的东西了，但是当时只介绍了diff的大致思想流程，没有提到某些细节的方面，就比如今天要介绍的内容：React是如何做列表的diff的。 ## 基本思想 列表diff换句话来说就是要找出两个线性结构的差异，如**数组A是如何通过最少基本操作变成数组B的**，而基本操作包括**移动**，**插入**和**删除**。其实要高效地找出两个线性结构的差异不是一件简单的事情，通常情况下，假如有两个数组，旧数组（原数组）元素为 **A、B、C、D**，新数组（目标数组）元素为**B、A、D、C**：  为了从旧数组得到新数组，我们对新旧数组进行diff，发现B不等于A，然后就会创建B然后插入，并删除A节点，以此类推，创建并插入 A、D、C，然后移除B、C、D。 但是，这些元素其实都没有发生改变，仅仅是位置上发生了变化，却要进行一大堆的繁琐低效的创建插入删除等操作，这在大量数据下，是不可取的。 显然，由于新旧数组的元素只发生了移动，这些移动的元素我们可以对其进行复用，也就是只需要找出哪些元素需要移动，然后对其进行移动操作即可。React使用的是一种**最右访问位置**算法，这种算法的思想是：遍历新数组，查看新数组元素在旧数组中的下标，如果当前访问的元素比之前访问过的所有元素在旧数组的下标的最大值（也就是最靠右）要小，那么便可判断该元素是需要移动的。看起来很复杂，其实可以这么理解：在新数组中，访问过的元素的下标肯定要比当前访问的元素的下标要小，但是在旧数组中，当前访问的这个元素的下标却比之前访问的某个元素在旧数组中的下标要小，那么这个元素肯定被移动了。 同时，因为React需要复用元素，那么便需要确定新旧数组中哪一个元素是同一个元素，因此React建议在渲染列表时最好给列表元素添加`key`属性以提高diff的性能：  若没有`key`属性，React会像上面例子一样做暴力的diff，而有了`key`属性后，React就可以按照算法优雅地diff了：  新旧数组和上面例子一致，只不过每个节点都加上了唯一的`key`，通过这个`Key`发现新旧数组里面其实全部都是相同的元素，只不过位置发生了改变。因此就无需进行元素的创建、插入、删除等操作了，只需要将旧树当中节点的位置进行移动就可以了。React给出的diff结果为：B、D不做操作，A、C进行移动操作。 首先，react会去循环整个新的数组： 1. 从新数组中取到**B**，然后去旧数组中判断是否存在相同的**B**，确认**B**存在后，再去判断是否要移动： **B**在旧数组中的`index = 1`，有一个游标叫做`lastindex`。默认`lastindex = 0`，然后会把旧数组的`index`和游标作对比来判断是否需要移动，如果`index < lastindex` ，那么就做移动操作，在这里**B**的`index = 1`，不满足于` index...
距离上一次写东西已经有3个月了，开学之后有点忙，而且又懒了。今天写的就算是对之前工作的内容的一部分做一些提取和精练。 ## 什么是二叉树的差异识别 差异识别算法换句话说就是两棵二叉树的对比算法，本质上是求解一棵树演变为另一棵树的最短演变步骤。假如我们有两棵二叉树**Th（Host tree）** 和 **Tt（Target tree）**，那么差异识别算法要求解的就是**Th** 如何通过最少的改动，哪些改动来变成**Tt**。 ## 递归遍历方法的缺陷 一般情况下，对两棵二叉树进行比较使用的是**递归遍历方式**。如下图1所示，分别从**Th**，**Tt** 的根结点开始，递归对比**Th**，**Tt** 的每个子结点。设当前比较的结点分别为**qA**，**qB**，若发现**qA**，**qB** 非同一结点，则可马上断定**T(qA)**，**T(qB)** 整体（虚线框内）不相等。该算法复杂度为**O(n)**。 > T(x)表示二叉树T中以x结点为根节点的子树，下同。  fg1. 该方法虽简洁高效，但其差异判断规则过于简陋。首先，对于某个结点是销毁还是移动，该算法无法判定，也就是无法复用结点。如图2，**TA** 要演变为**TB**，显然只需简单修改结点3的双亲结点，这时我们可以称结点3被“移动”了。然而在上述算法中，递归比较至结点1右孩子指针域时，会判定结点3被销毁。然后比较结点2右孩子指针域时，会判定需创建一个结点3。  fg2. 虽然能得到正确的结果，但是相比于单纯地移动结点3，该算法却增加了无必要的结点销毁和创建开销，若结点3包含复杂的信息，该开销对性能的影响会十分明显。这个问题产生的原因是在销毁某一结点时，算法无法得知接下来的步骤是否会再出现该结点。当然，可以修改算法使得在每次需要销毁结点前，都查找**Tt** 是否存在该结点，然而修改后的算法复杂度增加至**O(n^2)**。 其次，递归遍历算法根据结点判定子树相等情况是不合理的。在某些情况下，子树间虽不严格相等，但却高度相似。图3分别展示了**Th** 中的子树**T(2)**，**Tt** 中的子树**T(4)**。**T(2)** 和**T(4)**...