Phenom
Phenom
先来实现一个简单的例子：**二叉树可视化**。 StructV将一次可视化行为抽象为一个函数：**View = V(Sources, Options)**，其中Sources是源数据，Options是配置项，V()是可视化实例，View是视图。 因此，使用**StructV**构建一个可视化实例分为3大步： 1. **确定源数据格式：定义Sources** 2. **编写默认配置项：定义Options** 3. **为可视化实例编写渲染函数：定义V。这一步是核心** StructV支持Typescript和Javascript，下面的代码部分将分别给出ts和js的相应实现。 ## Step 1 Sources作为可视化实例V的输入之一，自然十分重要。StructV中Sources必须为一个对象或数组，其中组成该对象或数组的元素称为**SourcesElement**。当有多种类型的SourcesElement时，Sources必须为对象，当只有一种类型的SourcesElement时，Sources便可简写为数组。一个SourcesElement必须为一个对象且在同类型SourcesElement中有唯一的id。 来理解一下。我们要构建的是二叉树可视化，那么显然，一个二叉树结点就是一个SourcesElement。构成一个二叉树结点的最少信息有： - **id** - **根标志 root（该节点是否为根节点）** - **左孩子结点 leftChild** - **右孩子结点 RightChild** #####...
阅读matter.js源码看到刚体update部分时发现了一种新的积分方法，赶紧学习总结下来。 **注意，今天这篇比较硬核，需要一点点高数基础。** ## 欧拉积分的缺陷 大多数物理引擎，包括box2d，在进行刚体位置更新时，通常使用以下方法：  ```typescript // 更新速度 body.velocity += body.acceleration*dt; // 更新位置 body.position += body.velocity*dt; ``` 这种我们经常在高中物理课本看到的速度和位置计算方法叫做欧拉积分法（Euler integration）。欧拉积分最大的好处就是简单，易于实现，性能好。 但是在中学，我们学习的都是匀加速运动，即加速度不变的运动，欧拉积分在恒定加速度的情况下表现良好。然而现代物理引擎常常包含复杂的碰撞，约束和摩擦力等，此时的加速度是不断变化的。在数学角度上，欧拉也可以求解变加速运动，因为加速度再怎么变化，位移s关于时间t的函数始终都是一个连续函数，而连续函数必定可积。但是在计算机中情况就不一样了，计算机模拟运动是离散的，物理引擎会设定一个**步长dt**（通常为1/60）作为每次模拟的时间间隔，也就是每隔dt时间，物理引擎便执行一次模拟，更新物理数据。 欧拉积分用当前时刻的值y(t) + y'(t)*dt来求y(t + 1)时刻的值。这种方法主要的误差来源于： **离散情况下dt区间内的y'(t)是变化的，而这里我们都用y(t)替代了，所以欧拉求得的y(t + 1)只能是近似值。** 所以当模拟时间长了之后，欧拉积分就会不够精确，甚至不够稳定。...
最近在看box2d的源码，看得好累。发现box2d的碰撞检测不止用到了SAT（分离轴）算法，还有**GJK算法**和V-clip算法（连google都找不到的冷门算法，不知道具体原理）。box2d貌似把3种算法糅合起来了，根本看不懂。 不过看到GJK时，我上网了解了一下，感觉眼前一亮，因为看到一种跟分离轴思路完全不同的碰撞检测算法还是很开心的。和SAT一样，GJK算法也只对凸多边形有效。GJK算法的最初目的是计算两个凸体之间的距离，但是后来却广泛应用于碰撞检测。 ## GJK基本思想 GJK原理是：如果两个凸图形的闵可夫斯基差包含原点, 那么这两个图形重叠，即问题转变成判断一个 **闵可夫斯基差（Minkowski Difference）** 图形是否包含原点。其中用到了闵可夫斯基差，我们可以先看看什么是闵可夫斯基和： 假设有两个多边形**A**，**B**，那么闵可夫斯基和用公式表示就是： **A + B = {a + b|a∈A, b∈B}** 用通俗的话说就是假如多边形**A**具有顶点{a, b, c}，多边形**B**具有顶点{d, e, f, g}，那么**A**和**B**的闵可夫斯基和就是： **{a + d, a + e,...
想要高效地进行碰撞检测，不是一件简单的事情。物理引擎通常面对的是多个物体同时出现在同一场景，比如说现在我们的场景中有 5 个物体：  我们当然可以用碰撞检测算法进行两两碰撞检测，如 SAT ，GJK 等。然而当场景中有 100 个物体时，即使使用优化手段跳过已经检测的物体对，至少也要执行 (100 * (100 - 1)) / 2 次 SAT 或 GJK 。这显然是不能接受的。 即使我们不能快速判断两个物体真的发生了碰撞，但是我们肯定是有办法快速判断两个物体**肯定没有发生碰撞**。场景中的物体形状都是随机的，这造成了碰撞检测的困难，因此我们可以使用一种简化的易于检测的图形去暂时代替物体，当两个简化的图形没发生相交，那么我们可以马上推断其相应的物体没有发生碰撞。 ## AABB 包围盒 AABB 名叫**轴对齐包围盒**（Axis align bounding...
分离轴算法只能检测圆形和凸多边形。对于凹多边形，要先将其分割为凸多边形。这里便涉及凹多边形判断和凹多边形分割算法。 ## 凹多边形判别 对于多边形的判别，可以利用**向量叉积**来判断。 > 假设有两向量a，b。当aXb0时，b在a的逆时针方向。 根据凸多边形的定义，凸多边形的每条邻边的必定具有相同的时针方向，因此，我们可以为多边形的每一条边建立一个向量，通过相邻边向量叉积运算来判断多边形凹凸性，**凸多边形的所有边的向量叉积均同号**，因此一个多边形的所有边向量的叉积结果不同号,则可判定其为凹多边形。  有了思路后要实现代码就很简单了： ```typescript /** * // 判断是否为凹多边形 * @param vexs 多边形顶点数组 */ function isConcavePoly(vexs: polygonVex): boolean { // prev: 上两邻边间叉乘结果；cur当前两邻边叉乘结果 let prev: number,...
## 前言 好久没有更新物理引擎相关的文章了，因为这段时间都在忙其他事情，当然初心还是不能忘的。不过物理引擎相关的文件夹也好久没有打开了，现在看起来竟然有一点陌生。 想了一下，这样零零散散地写意义不是很大，因此我决定接下来会好好整理一下与物理引擎有关的文章，最好整合成几个系列，国内物理引擎技术的教程或讲解都太少了，大多数都是只涉及点皮毛或者泛泛而谈之后就太监了，但我相信对这方面感兴趣的人是有不少的，因此坚持更新，总会有人需要的。 ## 什么是碰撞点 碰撞点，顾名思义便是两个物体发生碰撞或者接触的点。碰撞点是处理碰撞的关键，因为这取决了碰撞之后求解器计算出的冲量要应用于物体的哪个位置，在物体的不同位置应用冲量往往会产生截然不同的效果，比如在物体质心施加冲量物体会笔直地飞出去，而在偏离质心的位置施加冲量则会产生不同程度的旋转。执行完碰撞检测算法（如SAT）我们通常只会得到碰撞法线和穿透深度，而碰撞点，需要我们单独计算。 在现实世界中，两个正方体相接触，下面的红点就是碰撞点：  现实中碰撞点十分直观自然，我们可以一眼看出。然而在计算机中计算碰撞点并不是一件简单的事情，因为计算机的世界是离散的，往往我们检测到碰撞时两个物体已经发生了相交，如下图所示：  在相交的情况下，情况便变得复杂了。两物体相交时产生了几个都可以作为碰撞点的“候选点（即图中的黄点）”，因此我们要从这些点中筛选出真正的碰撞点。那么我们把所有黄点都作为碰撞点行不行呢？当然是不行的，因为在现实中（2d），两个凸多边形发生碰撞不可能会产生多于 2 个的碰撞点（不信你自己在脑中模拟一下），因此我们的碰撞点最少会有一个，最多只有两个。 ## 最近内部顶点法 碰撞点求解，（据我所知）主流方法有两种，今天我们要介绍的是比较简单好理解的一种，这种方法没有名字（可能有，但我不知道），因此我给它取了个名字叫 **closest-internal-vertices-method（最近内部顶点法）**。该方法的核心思想十分简单，就是**求两个物体彼此间距离最近的顶点**。怎么评估顶点与对象的相近程度呢？我们可以用**向量投影**，将顶点投影到碰撞法线上，投影值越大表示距离越近。 假设有两碰撞对象为 A，B ，碰撞法线为 n，求解 A，B 间的碰撞点，该算法主要分为 3 步： 1. **找出 A 中在...
如果你没有看过第一篇教程，强烈建议先阅读：[ StructV 教程（一）：实现二叉树可视化](https://github.com/phenomLi/Blog/issues/39) 今天来介绍一个复杂一点的例子：**哈希无向图可视化**，随便引出一点新东西。 我不知道到底有没有“哈希无向图”这种奇奇怪怪的数据结构，我只是想通过引入这种结构： 1. **展示 StructV 具有可视化任何结构的能力** 2. **利用该种结构，能覆盖到我想要介绍的新内容** 首先，先看看我们想要的目标效果：  看着不难吧。左边哈希表的每一个值都指向右边无向图的每一个结点，然后无向图里的结点又各有连接。为什么我偏要拿这个结构作为第二篇教程的例子呢，因为该结构有两个特点： - **哈希表的每个元素的图形（就是两个格子那个），StructV 中没有内置** - **该结构有两种不同类型的结点（哈希表元素和无向图结点）** So what should we do ？我们要做的：还行老三样：**1.定义源数据**，**2.编写配置项**，**3.编写可视化实例类**。 ## Step 1 首先，新建 `sources.ts`...
前段时间一直在做实验室的项目，也就是数据结构可视化的内容。目前来讲第一版已经完成了，然而在不断增加的需求下，代码逐渐变得不可控，于是我毅然选择了重构（其实基本上是换一种思路重写了），也就是第二版的开发。写这篇文章就是想把我在构建这个数据结构可视化系统从开始的构思，到发现问题（为什么要重构），最后用什么的思路重构的这个过程记录下来，我觉得很有必要。 ## 初始需求 根据导师的意思，在我们已有一个在线webIDE的情况下，构建一个可视化系统，在用户调试的过程中，对用户所编写实现某种数据结构的代码进行可视化，比如用户写了一棵二叉树，就在可视化区域绘制出这棵二叉树；其次，在每一步调试中，若发生数据结构的变化，可视化区域都要将前后两次变化用动画呈现出来，换句话说就是不能直接擦除旧的二叉树，又生成一棵新二叉树覆盖上去。最后，暂时只需支持二叉树和链表。 对这个需求抽丝剥茧，提取核心，可以得到以下信息： - **可视化系统可抽象为两种状态：初始状态和后续状态** - **对于初始状态，即在首次得到数据结构时，可视化系统直接根据数据结构进行图形绘制** - **对于后续状态，即之后数据结构每一次发生变化，可视化系统要基于上一次绘制的状态进行更新** ## 构思 那么，从这两个信息如何往代码结构层面转变？首先，对于初始状态，不难想到，可将可视化系统视作一个函数：`Sources => View`，这里 **Sources（源数据）** 指的是 **一种描述某种数据结构信息的数据**，作为可视化系统的输入， **View（视图）** 显然就是值可视化系统所绘制出的内容。其次根据单一职责原则，这个可视化系统只需实现从Sources输入到绘制View这个过程，至于如何识别用户写的是什么数据结构，Sources从哪里生成，这不是我所关心的内容。 其次，根据需求，每一次数据结构变化都理应生成一份新的Sources，重新输入可视化系统。但是此时不能直接输出View，即不能直接进行可视化绘制，因为要基于上一次的View进行更新。熟悉React的朋友应该都能联想到这种基于上一状态进行差异更新的机制的核心在于**前后数据的差异识别（differ）**，同样地我也是使用这种思路对可视化系统进行图形更新。那么，对于后续状态，可以抽象为：`Sources => differ => View `。 Sources作为可视化系统的输入，结构和格式应该由可视化系统进行约定，使用可视化系统前应将编译器的到的数据转化为Sources格式。以二叉树为例，初步设计的Sources格式如下（经过简化）： ```typescript class...
碰撞求解是紧接着碰撞检测后的一个步骤，顾名思义就是对发生碰撞的对象进行碰撞反应的模拟，比如反弹旋转等。碰撞求解可以说是物理引擎里最难的部分之一了，但是放心，这篇文章会先从最简单的向量部分入门，利用简单的向量知识，模拟简单的碰撞效果。 该文章只涉及少量简单数学，请放心食用。要求： - **高中向量知识** ## 球与墙壁的碰撞 我们先从最基本的开始，考虑在理想情况下（无重力，阻力，完全弹性碰撞）有一些球在盒子里自由运动的情况：  其中箭头方向代表球的速度方向。 先不考虑球与球直接的碰撞，那么在盒子中，球只会与墙壁发生碰撞，通过碰撞不断改变球的速度方向（大小不变）。我们可以想象到，当球碰撞墙壁时，它的运动轨迹是这样的：  其中蓝色向量代表球碰撞前的速度，红色向量代表球碰撞后的速度。 所以显然的，要求解球碰撞墙壁后的速度方向就是要求红色向量。 为了求解红色的向量，我们可以对这次碰撞进行建模：  **u**代表碰撞前速度，**v**代表碰撞后速度，**n**代表碰撞法向，且**u**，**v**关于**n**对称。碰撞法向**n**通常情况下不容易求得，但是由于现在情景简单，所以这里我们可以一眼看出**n**就是垂直与墙壁平面的向量。**注意n是一个单位向量**。 现在**u**和**n**都是已知的，我们要做的就是用**u**和**n**去表示**v**。现在还是不好求出**v**，但我们可以把**v**平移到**u**的起点，然后延长**n**，延长后的**n**记为**n'**。  这时，我们很容易得到一个关键等式：  所以只要求出**n'**就可以了。那么怎么求呢？观察发现，由于**u**，**v**是等长的，**u**，**v**和**n'** 形成了一个等腰三角形，我们可以用投影解决。 首先，我们把**u**投影到**n'**上，得到1/2|**n'**|。  将结果乘上2便得到**n'**的模长，再由于**n'**和**n**是共线的，且**n**为单位向量，所以只要将**n**乘上**n'**的模长即可求得**n'**：  最后，我们把**n'**换一下，得到**v**关于**u**，**n**的表达式：  解决了。很简单。 其实整个流程要注意的只有一点，就是**n**的方向，如果**n**是指向墙壁外的，那么最后的表达式就要加号换成减号。...
说说js中的异步
**这篇文章会帮您解答js中什么是同步什么是异步。** 通常来说，在js中，我要按顺序干两件事，这样写就行： ```javascript 吃饭(); 睡觉(); ``` 这样就可以做到先吃饭然后睡觉了。 现在假如吃饭要花费两秒，**我想要在吃完饭后睡觉**，我这样写： ```javascript const eat = function() { console.log('start to eat.'); setTimeout(function() { console.log('finish.'); }, 2000); }; const sleep = function() { console.log('start to...