游戏引擎

一、前言 本文是“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....