数学

一、前言 本文是“2D物理引擎基础”的第三篇文章，主要介绍物体刚体力学的相关知识以及碰撞发生后的处理办法。后者背后的数学原理较为复杂，因此这里大多情况只是罗列公式并做简要说明。 二、刚体力学 连续的刚体力学 我们考虑二维的情况。假设有一刚体，质量为 $M$，转动惯量为 $I$，在距质心 $\vec{r}$ 处受到一力 $\vec{F}$ 的作用。 那么刚体所受相对于质心的力矩 $\vec{M}$ 为： $$ \vec{M} = \vec{r} \times \vec{F} $$ 注意 $\vec{M}$ 的方向垂直于平面，后面的角速度同理。 在 $\Delta{t}$ 时间内速度变化 $\Delta{\vec{v}}$ 有 $$ \Delta{\vec{v}} = \int_{t_0}^{t0+\Delta{t}} \frac{\vec{F}(t)}{M} dt $$ 同样的，角速度变化 $\Delta{\vec{w}}$ 有 $$ \Delta{\vec{w}} = \int_{t_0}^{t0+\Delta{t}} \frac{\vec{M(t)}}{I} dt $$ 类似的，也有位置和角度的变化 $$ \Delta{\vec{p}} = \int_{t_0}^{t0+\Delta{t}} \vec{v}(t) dt $$ $$ \Delta{\vec{\theta}} = \int_{t_0}^{t0+\Delta{t}} \vec{w}(t) dt $$ 还有冲量 $$ \vec{I} = \int_{t_0}^{t0+\Delta{t}} \vec{F}(t) dt $$ 以及角冲量（或称冲量矩） $$ \vec{H} = \int_{t_0}^{t0+\Delta{t}} \vec{M}(t) dt $$ 并有等式 $$ \vec{I} = M \Delta{\vec{v}} $$ $$ \vec{H} = I \Delta{\vec{w}} $$ 离散的刚体模拟 正如第一篇文章中说过的，一般情况下计算机无法计算连续，只能通过离散的方式进行近似。物理引擎中进行的模拟会导致误差，但这对于视觉效果来说已经足够了。...

一、前言 本篇是“2D物理引擎基础”的第二篇文章，将主要讲解碰撞检测的基本原理和算法。 碰撞检测是物理引擎十分重要的组成部分。碰撞检测及后续的碰撞约束反映了物质的不可入性，是物理模拟真实性的基础。另外碰撞检测也能有效用于游戏逻辑的实现，如触发陷阱、探测障碍等等。 二、碰撞检测的基本概念 碰撞检测的目标就是判断两个几何体是否存在重合部分，如果存在重合部分，则得到接触点、碰撞法线和穿透深度。 接触点（Contact Point）指的是两个几何体相接触的位置。当然对于碰撞检测而言，接触的部分并非点而是区域，但是我们可以通过算法从中近似地取出接触点，一般位于其中一个几何体的顶点或边上。 碰撞法线指示了一个物体与另一个物体发生碰撞后，后者为了分离而应该采取的运动方向。这一法线大多是几何体中某一条边的法线 穿透深度是沿碰撞法线方向最终分离所需的距离，这一数值常用来修正碰撞后两几何体的位置，避免两几何体在视觉上发生重叠。 三、分离轴定理（SAT，Separating Axis Theorem） 分离轴定理是如下内容：若两个凸物体没有重合，则总会存在一条直线，能将两个物体分离。这样的直线称为分离轴。对于高维物体来说这同样适用，只不过分离轴将变为分离超平面。 利用分离轴定理可以实现凸几何体的碰撞检测。对于多边形，算法是这样的： 对两个多边形的每一条边，做垂直于该边的直线 对两个多边形的每一个顶点，分别做到步骤1中所得直线的投影 如果存在一条直线，两个多边形对这条直线的投影并不重合，则两个多边形不重合 如果不存在步骤3中的直线，则两个多边形重合。 完全按照算法思路得到代码如下 def sat(body_a, body_b): return not find_separate_axis(body_a, body_a, body_b) and not find_separate_axis(body_b, body_a, body_b) def find_separate_axis(lines_body, body_a, body_b): for i in range(len(lines_body) - 1): p1 = lines_body[i] p2 = lines_body[i] + get_normal(lines_body[i+1] - lines_body[i]) a_min, a_max = body_cast(p1, p2, body_a) b_min, b_max = body_cast(p1, p2, body_b) if p1[0] != p2[0]: max_min = a_min if a_min[0] > b_min[0] else b_min min_max = a_max if a_max[0] < b_max[0] else b_max if max_min[0] < min_max[0]: continue else: max_min = a_min if a_min[1] > b_min[1] else b_min min_max = a_max if a_max[1] < b_max[1] else b_max if max_min[1] < min_max[1]: continue return True return False def body_cast(a, b, body): body_min = body_max = point_cast(a, b, body[0]) for p in body: p_cast = point_cast(a, b, p) if p_cast[0] < body_min[0] or (p_cast[0] == body_min[0] and p_cast[1] < body_min[1]): body_min = p_cast if p_cast[0] > body_max[0] or (p_cast[0] == body_max[0] and p_cast[1] > body_max[1]): body_max = p_cast return body_min, body_max def point_cast(a, b, p): u = p - a v = b - a p_cast = a + v * (np....

一、前言 本系列是我学习物理引擎相关知识的总结。虽说最初的目标是自己实现一个完整的物理引擎，但是随着学习的深入我认识到，为了让引擎更好地模拟实际，所需要的各种数学原理和处理技巧远远超出了“涉猎”的程度。因此我决定就此止步，但是还是留下了自己的实践成果和经验总结，就在这系列文章中。 本文是“2D物理引擎基础”的第一篇，将介绍物理引擎中物体所需的物理属性 二、物理引擎中的物体 在物理引擎中，模拟的物体对象被假定为刚体。刚体是如此致密坚硬的一种物体，以至于任何碰撞都无法改变其形状。同时物理引擎还常常假定对象的密度均匀，这样对象的质心将只由其几何形状决定。通过这样的假设，物理引擎将能够通过算法优化高效地进行计算模拟： 刚体说明物体不会改变形状，这样当物体受到力的作用时，力的作用效果就不会造成改变物体运动之外的其他影响，如质心改变。 密度均匀使得质心的求解更为方便，将质心位置和偏转角度作为物体属性，就可以完全表示物体上各点的位置信息 接下来所说的物理属性也是在如上约定的基础上的。 三、运动学属性 形状的表示 物理引擎中的形状用描述物体边界的属性表示。不同形状的物体通过不同的几何参数进行表示，如矩形可用长宽表示，圆可用半径长度表示，这些较为简单。更一般地我们考虑多边形，多边形可用顶点坐标表示，但是我们希望形状是位置无关的，那么多边形的顶点坐标也不能在坐标轴上随意选取。虽然 $(0, 0), (1, 0), (1, 1), (0, 1)$ 和 $(1, 1), (2, 1), (2, 2), (1, 2)$ 表示相同形状的多边形，但我们需要选择与位置无关的那一个。我们可以选择使多边形的质心在坐标原点的顶点集合，因为我们后续需要通过质心确定运动学属性。对于均质物体来说，这也就是多边形的几何中心在原点。 我们不能人为地在设置形状时就限制顶点围成的形状中心必须在原点，这对于复杂的形状来说十分困难。我们可以根据顶点集合先确定几何中心位置，再对每一顶点减去中心坐标以将物体平移到集合中心为原点的位置。 对于多边形，计算几何中心的公式为 $$ A = \frac{1}{2} \sum_{i=0}^{N-1}(x_iy_{i+1} - x_{i+1}y_i) $$ $$ c_x = \frac{1}{6A} \sum_{i=0}^{N-1}(x_i + x_{i+1})(x_iy_{i+1} - x_{i+1}y_i) $$ $$ c_y = \frac{1}{6A} \sum_{i=0}^{N-1}(y_i + y_{i+1})(x_iy_{i+1} - x_{i+1}y_i) $$ 其中 $A$ 为多边形面积， $(c_x, c_y)$ 即几何中心位置。需要注意的是，在这个公式中，顶点序列为逆时针，且第一个和最后一个应是同一个坐标，以暗示这是一个闭合图形并且方便公式表示。$N$ 是不重合的顶点个数/边数。 如下是求集合中心的 python 代码 def get_geometric_center(points): area = 0 c_x = c_y = 0 n = points....

一、自然语言处理（nlp）简介 一份思绪奔驰的前言： 语言的边界就是思想的边界。如果从人类所具有的一切中挑出一个事物，让它来显示出人与其他生物的不同之处，那一定是语言。语言是我们用来思考和交流的方式，我们的一切文明都构筑在这简单的一维序列中，可我们却几乎不曾深入了解过它。 有人说，我们不曾真正的理解语言，我们所有对语言的运用和理解，不过建立在婴儿及此后对他人的声音与书本上符号的猜测上。或许正是如此，但是我们依旧要做出猜测，向着语言的神秘进发，这是我们的信念，是我们认识我们的认识的开始。 （1）作为语言学的 nlp 早在计算机的上古时代，深度学习还未诞生的时候，自然语言处理作为语言学的一个领域就已诞生了，这个领域也被语言学家们称为计算机语言学。两个名称在一起，才表达出 nlp 的真正含义——通过机器处理语言。nlp 最早的研究方向是机器翻译，那时人们人为地总结语言的规律，对词汇进行标注，对语句进行句法分析。结果是人为的规则覆盖面不足，所设计的系统无法扩展。 （2）作为机器学习研究领域的 nlp 随着计算机的发展，出现了基于传统统计学习模型的自然语言处理方式。这些原始的模型较之之前有所进步，但受限于计算机性能，统计方法也遭遇了瓶颈。 直到近年来算力的发展，使得深度神经网络成为可能。深度神经网络结构中潜在的学习能力，在 nlp 领域发挥了作用。通过多维数据表示语言和含义，深度学习以高效且与人类认知过程相似的方式发挥了巨大的效果。 二、词向量 词汇作为符号，其形象是离散的；但词汇的所指作为定义，其含义却是丰富而连续的。比如说“母亲”这个词汇，既表示了这个概念所对应的事物是在一种血缘关系中的一方（她是孩子的母亲）；又表示了这个事物是能繁殖者（母鸡）；在一定程度上，同样表示了非血缘关系，但具有类似血缘关系的行为的个体（大地是母亲）。 偏个题，《来自深渊》中有对生骸语的类似的描述. 因此，我们就不能再将词汇只作为离散的符号看待了，不能认为词汇之间是相互排斥的关系了。我们需要将词汇看做某些元含义在不同程度下的集合，或者从机器学习的角度，把这些元含义称作特征。那么也就是说，我们将每个词汇都看成一定维度的向量。 但是我们要如何确定特征呢？特征的数量又有多少？如果人工地确定特征为“存在、含义、物质、精神”等等，这一过程将耗费精力且永无止境。实际上按照机器学习的一般策略，我们只需要通过统计文本，自发的构建词汇向量即可。 这一方面有许多算法，如 N-gram 算法，GloVe 算法等等。另外也可以在深度学习的过程中利用反向传播自发的调整词向量，在 pytorch 中这通过 Embedding 层来实现。 三、循环神经网络（RNN）及其变体 （1）朴素 RNN 考虑我们说话或写作时的基本逻辑。对于一段语言序列，在之后的词汇总是和之前的词汇有关，未表达的部分总是已表达部分的补全或补充。循环神经网络的机制类似，我们需要用一个或多个隐藏变量作为对之前语句含义的表示，在输出下一个词汇时，会让隐藏变量参与决策；同时每多说完一个词汇，这个词汇也会更新隐藏变量，以实现表达含义的更新。 具体来说，我们用 $t$ 表示时间序列，对某一时间 $t$，$x_t$ 表示输入，$y_t$ 表示输出，$h_t$ 表示隐含状态。那么朴素的 RNN 网络即： $$ h_t = tanh(W^{(hx)} x_t + W^{(hh)} h_{t-1}) $$ $$ y_t = W^{(S)} h_t $$ 容易看出 RNN 和 Moore 自动机有相似之处。 其中 $W^{(hx)}, W^{(hh)}, W^{(S)} h_t$ 分别为三个不同的矩阵。RNN 的激活函数也可以选择 ReLU。同时可以为激活函数中的部分添加偏置（bias）$b^{(hx)}, b^{(hh)}$ 等。...

一、引子——双色球 我们知道，双色球每注投注号码由 6 个红色球号码和 1 个蓝色球号码组成。红色球号码从 1—33 中选择；蓝色球号码从 1—16 中选择。现在要求写出一个程序，模拟双色球的抽奖过程。 我们很容易想到使用某种方法生成一定范围内的随机数。蓝色球很好解决，但对于红色球，需要的是随机生成 6 个号码不同的数，可一定范围内的随机数总可能出现相同的情况，这样要如何解决？ 也就是说：对于 $1, 2, ..., m$ 这 m 个数字，随机抽取其中 $n(n \lt m)$ 个数。要采取怎样的算法？ 二、两种思路 其一 : 暴力方法 的确，随机数总有可能出现相同的情况，但是我们知道，同一个数多次出现的概率很小，以至于我们可以将其忽略。因此，我们只需要不断地取范围内的随机数，遇到重复的舍弃，直到取得的数字数目达到 n 即可。 void rand1(int m, int n, int rands[]) { char* hasSelect = calloc(m+1, sizeof(char)); for (int i = 0; i < n; ) { int r = randomInt(1, m); if (!hasSelect[r]) { rands[i++] = r; hasSelect[r] = 1; } } free(hasSelect); } 但这种算法是有缺陷的。问题在于，概率达到多小才算作可以忽略？ 考虑 $m=100, n=99$ 的情况。首先，取得第一个球，一定只需要选取 1 次；但是，我们再计算一下取得最后一个球的选取次数。为了取得第 99 个数，选中的概率为 $p_{99} = \frac{1}{50}$。我们设离散型随机变量 $X$ 表示为了取得第 99 个数所需的选取次数，则 $P\{X = k\} = (1-p)^{k-1}p$ 服从几何分布。因此 $E(X) = \frac{1}{p} = 50$。从期望上看，需要整整 50 次才能取到第 99 个数！！这中间的差距说明了，在 m 一定时，随着 n 的增大，随机的效率明显降低。...

一、引言 另一种常用的非监督学习应用场景是异常检测。异常检测会学习正常情况下的样本数据，并在应用时检测出现的异常数据。 异常检测会运用正态分布等知识，这里先介绍一下正态分布（同时也作为自己对概率统计中的相关知识的一点总结）。 二、正态分布 对于连续型随机变量 X，若其概率密度函数为如下的形式 $$ f(x) = \frac{1}{\sqrt{2\pi}\sigma} e^{-\frac{(x-\mu)^2}{2\sigma^2}} $$ 其中 $\sigma > 0, \mu \in R$ 则称 X 服从正态分布（Normal distribution），记 $X \sim N(\mu, \sigma^2)$。 取 $\mu = 0, \sigma = 1$，此时 $X \sim N(0, 1)$，称 X 服从标准正态分布。记标准正态分布的概率密度为 $\phi(x)$，分布函数为 $\Phi(x)$，则任意的服从正态分布的随机变量 X，其分布函数为 $F(x) = \Phi(\frac{x - \mu}{\sigma})$。 标准正态分布的分布函数数值有表可查。 任意正态分布的分布函数等式中的 $\frac{x - \mu}{\sigma}$ 是不是有点熟悉？在特征放缩那一篇文章中的 Z score 标准化部分有出现。 Z score 标准化似乎就是假定特征数值服从正态分布，并将其转化为标准正态分布形式。 三、算法 我们假设不同训练样本的每一个特征服从服从正态分布。那么，对每一个特征 x_j，求其期望 $\mu_j$ 和方差 $\sigma_j^2$，则该特征对应的概率密度为 $p(x_j, \mu_j, \sigma_j^2) = \Phi(\frac{x - \mu}{\sigma})$。我们假设各个特征之间相互独立，则对于任意的 $\vec{x}=(x_1, x_2, ....