企业官网建设流程全解析

1. 项目概述：从“撞上”到“检测”，游戏与仿真中的刚体物理基石

在开发2D游戏、物理仿真或是任何涉及图形交互的应用时，一个无法绕开的核心问题就是：屏幕上这两个图形对象，到底碰没碰到一起？对于简单的矩形或圆形，我们或许可以用边界框或距离公式快速判断。但当你需要处理任意形状的飞船、不规则的地形瓦片，或是复杂的机械零件时，问题就变得棘手了。这时，分离轴定理（Separating Axis Theorem, SAT）便闪亮登场，它被誉为2D凸多边形碰撞检测的“瑞士军刀”，高效、精确且原理优雅。

我最初接触SAT是在为一个2D平台游戏编写物理引擎时。面对各种多边形组成的角色和障碍物，简单的AABB（轴向包围盒）碰撞已经不够用了，角色在斜坡上会“卡住”，复杂的形状穿透更是家常便饭。在尝试并对比了多种算法后，SAT以其清晰的几何解释和稳定的性能成为了我的首选。它不依赖于特定的形状库，只要你提供的是凸多边形的顶点列表，它就能工作。无论是用C++编写高性能游戏引擎，还是在JavaScript中实现一个交互式演示，其核心思想都是相通的。

简单来说，SAT的核心思想非常直观：如果两个凸多边形没有发生碰撞，那么至少存在一条直线（分离轴），能够将这两个多边形完全分隔在直线的两侧。反之，如果找不到任何一条这样的分离轴，那么这两个多边形必然相交。我们的任务，就是去系统地检查所有可能的候选分离轴。对于凸多边形，这些候选轴就是每个多边形的每条边的法线方向。这个项目，就是要用C++，从零开始实现这一算法，构建一个可靠、高效的2D碰撞检测工具函数。

2. 核心原理拆解：为什么是边的法线？

在深入代码之前，我们必须吃透SAT背后的几何原理。为什么检查多边形的边就足够了？为什么是边的法线，而不是别的方向？理解这个“为什么”，是写出正确代码和后续调试的关键。

想象一下两个凸多边形A和B。如果它们没有碰撞，就像两个在桌子上互不接触的积木，你总能找到一条缝隙，插进一把刀片将两者分开。这把“刀片”的方向，就是分离轴。现在，考虑两个多边形所有可能的相对位置，最有可能成为那把“刀片”的，恰恰是它们彼此最接近的那些边。更严谨的数学原理是：凸多边形可以看作是其所有边的半空间的交集。两个凸集的交集为空，当且仅当存在一个超平面（在2D中就是一条直线）将它们分离。而支撑超平面的法线方向，就来自于两个凸集各自某个面的法线。

投影：将高维问题降维SAT的精妙之处在于引入了“投影”。在一条轴（一个方向向量）上，我们将一个多边形所有顶点投影到这条轴上，得到一个线段区间。例如，多边形在X轴上的投影，就是其所有顶点X坐标的最小值到最大值。碰撞检测这个2D空间的问题，被转化为了在一条条1D数轴上的区间重叠判断。如果在所有候选轴上，两个多边形的投影区间都重叠，那么它们在2D空间中就一定相交。只要存在一条轴，其上的投影区间不重叠，那么它们就一定分离。

候选轴的选择对于两个凸多边形，我们需要检查的候选轴集合是：多边形A每条边的法线 + 多边形B每条边的法线。边的法线是一个垂直于该边的单位向量，它指向多边形的“外侧”（这依赖于顶点是顺时针还是逆时针存储，需要统一）。理论上，两个多边形最多有(边数A + 边数B)条候选轴需要检查。但在实际优化中，因为一条边和它的法线是成对出现的，我们通常直接使用边的方向向量旋转90度得到的向量作为轴，无需单位化（在计算投影时统一处理），这可以节省一次开方运算。

注意：这里有一个非常重要的细节：我们使用的是“边的法线”，而不是“顶点连线”的方向。很多初学者会误以为需要检查所有顶点到顶点的连线，这是不必要的，也是SAT效率高的原因之一。对于凸多边形，检查所有边的法线足矣。

3. 数据结构设计与数学工具准备

在动手实现碰撞检测函数前，我们需要搭建好基础设施。清晰的数据结构和基础的数学工具函数能让核心逻辑变得干净利落。

3.1 定义核心数据结构

我们首先定义二维向量Vec2，这是所有2D几何运算的基石。

// Vec2.hpp #ifndef VEC2_HPP #define VEC2_HPP #include <cmath> struct Vec2 { float x, y; Vec2() : x(0.0f), y(0.0f) {} Vec2(float x_, float y_) : x(x_), y(y_) {} // 向量加法、减法、数乘等基本运算 Vec2 operator+(const Vec2& other) const { return Vec2(x + other.x, y + other.y); } Vec2 operator-(const Vec2& other) const { return Vec2(x - other.x, y - other.y); } Vec2 operator*(float scalar) const { return Vec2(x * scalar, y * scalar); } // 点积（内积），用于投影计算 float dot(const Vec2& other) const { return x * other.x + y * other.y; } // 获取向量的垂直向量（法线），默认返回逆时针旋转90度的向量 Vec2 perpendicular() const { return Vec2(-y, x); } // 计算向量长度平方，避免开方用于比较 float lengthSquared() const { return x*x + y*y; } // 单位化向量 void normalize() { float len = std::sqrt(lengthSquared()); if (len > 1e-7) { // 避免除零 x /= len; y /= len; } } }; #endif // VEC2_HPP

接下来，定义多边形Polygon。我们假设多边形是凸的，顶点按顺序存储（顺时针或逆时针，但必须统一）。

// Polygon.hpp #ifndef POLYGON_HPP #define POLYGON_HPP #include <vector> #include "Vec2.hpp" class Polygon { public: std::vector<Vec2> vertices; // 顶点列表，按顺序存储 Polygon() = default; Polygon(const std::vector<Vec2>& verts) : vertices(verts) {} // 获取第i条边（从顶点i指向顶点i+1） Vec2 getEdge(size_t i) const { size_t next = (i + 1) % vertices.size(); // 循环到第一个顶点 return vertices[next] - vertices[i]; } // 获取第i条边的法线（未单位化，即垂直向量） Vec2 getEdgeNormal(size_t i) const { return getEdge(i).perpendicular(); // 使用我们定义的perpendicular方法 } // 计算多边形在给定轴上的投影区间 [min, max] void projectOntoAxis(const Vec2& axis, float& minProj, float& maxProj) const { if (vertices.empty()) { minProj = maxProj = 0.0f; return; } // 初始化：将第一个顶点的投影作为初始值 minProj = maxProj = axis.dot(vertices[0]); // 遍历所有顶点，找到投影的最小值和最大值 for (size_t i = 1; i < vertices.size(); ++i) { float proj = axis.dot(vertices[i]); if (proj < minProj) minProj = proj; if (proj > maxProj) maxProj = proj; } } }; #endif // POLYGON_HPP

3.2 投影与区间重叠判断

这是SAT算法的核心辅助函数。给定两个区间[minA, maxA]和[minB, maxB]，判断它们是否重叠，并计算重叠深度（用于后续可能的碰撞响应）。

// SATUtils.hpp #ifndef SATUTILS_HPP #define SATUTILS_HPP #include <algorithm> // for std::max, std::min namespace SAT { /** * 判断两个1D投影区间是否重叠，并计算重叠深度。 * @param minA 多边形A投影最小值 * @param maxA 多边形A投影最大值 * @param minB 多边形B投影最小值 * @param maxB 多边形B投影最大值 * @param overlap 输出参数，存储计算出的重叠深度（如果重叠） * @return true 如果区间重叠，否则 false */ bool intervalsOverlap(float minA, float maxA, float minB, float maxB, float& overlap) { // 检查分离情况：A整体在B左边，或A整体在B右边 if (maxA < minB || maxB < minA) { return false; // 不重叠，存在分离轴 } // 计算重叠的两种情形，取最小的重叠量作为“穿透深度” // 情形1: A部分在B左边，重叠部分为 maxA - minB // 情形2: A部分在B右边，重叠部分为 maxB - minA overlap = std::min(maxA, maxB) - std::max(minA, minB); // 这里可以处理“刚好接触”的情况。通常，如果overlap == 0，我们可以认为没有碰撞（分离）。 // 但在某些物理引擎中，刚好接触也需要响应。这里我们定义 overlap <= 0 为不重叠。 // 为了数值稳定性，我们使用一个很小的容差。 const float epsilon = 1e-5f; if (overlap <= epsilon) { return false; } return true; } } #endif // SATUTILS_HPP

实操心得：容差（Epsilon）的重要性在浮点数计算中，由于精度问题，两个理论上刚好接触的多边形，其投影区间的maxA和minB可能并不完全相等，而是有极其微小的差异（如1e-7）。如果不设置容差，算法可能会错误地报告碰撞或非碰撞，导致物体“抖动”或“粘滞”。这个epsilon的值需要根据你的世界坐标尺度来调整。如果你的游戏单位是米，1e-5通常足够；如果单位是像素，可能需要0.1或0.5。这是一个需要根据实际情况微调的参数。

4. SAT碰撞检测算法完整实现

有了上面的准备，我们现在可以实现核心的checkSATCollision函数。这个函数不仅返回是否碰撞，还可以返回碰撞法线和穿透深度，这些信息对于后续的碰撞响应（如将物体推开）至关重要。

// SATCollision.hpp #ifndef SATCOLLISION_HPP #define SATCOLLISION_HPP #include "Polygon.hpp" #include "SATUtils.hpp" #include <limits> // for std::numeric_limits namespace SAT { struct CollisionResult { bool isColliding = false; Vec2 normal; // 碰撞法线（单位向量），指向从A到B的分离方向（或最小穿透方向） float depth = 0.0f; // 穿透深度 }; /** * 使用分离轴定理检测两个凸多边形是否碰撞。 * @param polyA 多边形A * @param polyB 多边形B * @return CollisionResult 包含碰撞状态、法线和深度 */ CollisionResult checkSATCollision(const Polygon& polyA, const Polygon& polyB) { CollisionResult result; result.depth = std::numeric_limits<float>::max(); // 初始化为最大值 Vec2 smallestAxis; // 记录最小穿透深度的轴 // 用于临时存储投影区间 float minA, maxA, minB, maxB; // 1. 检查多边形A的所有边法线 for (size_t i = 0; i < polyA.vertices.size(); ++i) { // 获取当前边的法线（候选轴） // 注意：这里我们使用边的垂直向量，它不一定单位化。 Vec2 axis = polyA.getEdgeNormal(i); // 将两个多边形投影到该轴上 polyA.projectOntoAxis(axis, minA, maxA); polyB.projectOntoAxis(axis, minB, maxB); float overlap; if (!intervalsOverlap(minA, maxA, minB, maxB, overlap)) { // 发现分离轴，绝对没有碰撞 result.isColliding = false; return result; } // 如果重叠，记录最小的重叠深度及对应的轴 // 穿透深度是投影重叠的长度，但我们需要考虑轴的“长度”对投影值的影响。 // 因为 axis 可能不是单位向量，直接计算的 overlap 是投影标量差，不是空间距离。 // 我们需要将 overlap 除以轴的长度，得到真实的空间穿透距离。 // 更高效的做法：在投影前将轴单位化，或者在此处进行校正。 // 我们选择在投影函数内部不单位化轴，以节省计算，在此处校正。 float axisLength = std::sqrt(axis.dot(axis)); // 计算轴的长度 if (axisLength > 1e-7) { overlap /= axisLength; // 得到真实的空间穿透深度 } if (overlap < result.depth) { result.depth = overlap; smallestAxis = axis; // 暂时存储当前轴，方向可能还需要调整 } } // 2. 检查多边形B的所有边法线 for (size_t i = 0; i < polyB.vertices.size(); ++i) { Vec2 axis = polyB.getEdgeNormal(i); polyA.projectOntoAxis(axis, minA, maxA); polyB.projectOntoAxis(axis, minB, maxB); float overlap; if (!intervalsOverlap(minA, maxA, minB, maxB, overlap)) { result.isColliding = false; return result; } float axisLength = std::sqrt(axis.dot(axis)); if (axisLength > 1e-7) { overlap /= axisLength; } if (overlap < result.depth) { result.depth = overlap; smallestAxis = axis; } } // 3. 如果所有轴都重叠，则发生碰撞 result.isColliding = true; // 4. 确定碰撞法线的方向。 // smallestAxis 目前只是最小分离轴的方向向量（未单位化）。 // 我们需要确保法线指向从A到B的分离方向（即，将A沿此方向平移可以最快地分离）。 // 一个常用的方法是：计算从A中心到B中心的向量，然后检查其与法线的点积。 // 如果点积为正，说明中心向量与法线方向大致相同，法线方向正确（从A指向B）。 // 如果点积为负，则需要反转法线方向。 Vec2 centerA(0,0), centerB(0,0); // 简单计算多边形的中心（质心），对于凸多边形，可以用顶点平均值近似 for (const auto& v : polyA.vertices) centerA = centerA + v; for (const auto& v : polyB.vertices) centerB = centerB + v; centerA = centerA * (1.0f / polyA.vertices.size()); centerB = centerB * (1.0f / polyB.vertices.size()); Vec2 centerToCenter = centerB - centerA; // 从A中心指向B中心的向量 // 单位化 smallestAxis 作为最终的法线 smallestAxis.normalize(); // 如果中心向量与法线方向相反，则反转法线 if (centerToCenter.dot(smallestAxis) < 0) { smallestAxis = smallestAxis * (-1.0f); } result.normal = smallestAxis; // 注意：此时的 depth 已经是沿法线方向的最小穿透距离。 return result; } } #endif // SATCOLLISION_HPP

5. 算法优化与边界情况处理

基础的SAT实现已经完成，但在实际应用中，我们还需要考虑性能优化和处理一些棘手的边界情况。

5.1 性能优化技巧

1. 提前剔除（Broad Phase）：SAT是一种“精细检测”（Narrow Phase）。在场景中有成百上千个物体时，对每对物体都进行SAT检测是不可接受的。必须先使用空间划分（如四叉树、网格）或粗略包围体（如AABB、包围圆）进行快速筛选，只对可能碰撞的物体对进行SAT检测。

2. 缓存法线：如果一个多边形的形状不变（比如静态地形），可以预先计算并存储其所有边的单位法线，避免在每次检测时重复计算perpendicular()和normalize()。

3. 投影计算优化：projectOntoAxis函数中的点积循环是热点。确保编译器能进行向量化优化。对于顶点数固定的简单形状（如矩形、三角形），可以手动展开循环。

4. 使用平方长度进行比较：在寻找最小穿透深度时，我们比较的是overlap（已经是距离）。但有时在早期分离判断中，我们可以先比较未除以轴长度的overlap平方，因为开方运算较慢。不过在现代CPU上，一次检测中的几次开方开销通常可以接受，代码清晰更重要。

5. 尽早跳出：一旦发现任何一条分离轴，函数立即返回false。这是SAT算法高效的关键之一。

5.2 处理特殊与边界情况

1. 退化多边形：确保多边形至少有三个顶点，且顶点不共线。在构造函数或顶点设置函数中可以添加验证。

2. 顶点顺序：算法假设顶点是连续且按顺序（顺时针或逆时针）排列的。如果顶点顺序是乱的，getEdgeNormal计算的法线方向将不一致，导致检测失败。可以在Polygon类中添加一个ensureWindingOrder方法来纠正顶点顺序。

3. “刚好接触”的处理：如前所述，使用epsilon容差。对于某些游戏逻辑（如平台边缘判定），你可能希望overlap == 0时返回“碰撞”，以便触发事件。这时可以调整intervalsOverlap函数的逻辑，将overlap <= epsilon改为overlap < -epsilon才判定为分离。

4. 含旋转和多边形的检测：我们的Polygon类存储的是局部坐标或世界坐标。如果物体有旋转、缩放和平移，你需要在检测前，将物体的模型变换（旋转、缩放）应用到顶点上，生成一个世界空间的多边形副本，或者更高效地，在投影时结合变换矩阵进行计算。通常的做法是维护一个物体的变换矩阵，在检测时动态计算其世界空间顶点。

   // 示例：在物体类中获取世界空间多边形 class GameObject { Polygon localPolygon; // 局部坐标下的形状 Vec2 position; float rotation; // 弧度 float scale; public: Polygon getWorldPolygon() const { std::vector<Vec2> worldVerts; worldVerts.reserve(localPolygon.vertices.size()); float cosR = std::cos(rotation); float sinR = std::sin(rotation); for (const auto& v : localPolygon.vertices) { // 应用缩放、旋转、平移 Vec2 transformed; transformed.x = (v.x * cosR - v.y * sinR) * scale + position.x; transformed.y = (v.x * sinR + v.y * cosR) * scale + position.y; worldVerts.push_back(transformed); } return Polygon(worldVerts); } };

6. 完整测试用例与调试可视化

理论再完美，也需要实践检验。编写全面的测试用例和简单的可视化调试工具，是确保算法正确性的不二法门。

6.1 编写单元测试

使用简单的测试框架（如Catch2）或直接写main函数测试。

// test_sat.cpp #include <iostream> #include "SATCollision.hpp" void testBasicCollision() { // 测试1：两个分离的三角形 Polygon triA({Vec2(0,0), Vec2(2,0), Vec2(1,2)}); Polygon triB({Vec2(5,0), Vec2(7,0), Vec2(6,2)}); auto result = SAT::checkSATCollision(triA, triB); std::cout << "Test 1 - Separated triangles: " << (result.isColliding ? "FAIL" : "PASS") << std::endl; // 测试2：相交的矩形和三角形 Polygon rect({Vec2(0,0), Vec2(3,0), Vec2(3,2), Vec2(0,2)}); Polygon triC({Vec2(2,1), Vec2(4,1), Vec2(3,3)}); result = SAT::checkSATCollision(rect, triC); std::cout << "Test 2 - Intersecting rect and tri: " << (result.isColliding ? "PASS" : "FAIL") << std::endl; if (result.isColliding) { std::cout << " Collision Normal: (" << result.normal.x << ", " << result.normal.y << ")" << std::endl; std::cout << " Penetration Depth: " << result.depth << std::endl; } // 测试3：刚好接触（在容差内） Polygon rectA({Vec2(0,0), Vec2(2,0), Vec2(2,2), Vec2(0,2)}); Polygon rectB({Vec2(2,0), Vec2(4,0), Vec2(4,2), Vec2(2,2)}); // 右边刚好接触 result = SAT::checkSATCollision(rectA, rectB); // 根据我们的epsilon设置，应该判定为不碰撞 std::cout << "Test 3 - Touching rectangles: " << (!result.isColliding ? "PASS" : "FAIL") << std::endl; } int main() { testBasicCollision(); return 0; }

6.2 简单可视化调试（基于控制台或简单图形库）

对于复杂的碰撞情况，肉眼难以判断。可以借助简单的图形库（如SFML、SDL2甚至OpenCV）将多边形和分离轴画出来。

调试绘制思路：

1. 绘制两个多边形。
2. 在检测过程中，将每条候选轴也绘制出来（从某个中心点延伸）。
3. 用不同颜色标记投影区间是否重叠。
4. 最终，用醒目的颜色标出“最小穿透深度轴”（即碰撞法线）。

这个过程能极大地帮助你理解算法每一步在做什么，以及为什么某些情况下会判断错误。例如，你可能会发现因为顶点顺序错误，导致所有法线都指向多边形内部，从而永远检测不到分离轴。

7. 常见问题排查与性能调优实录

在实际项目中集成SAT时，你几乎一定会遇到下面这些问题。这里记录了我的排查日记和解决方案。

问题1：物体高速移动时发生“隧道效应”（Tunneling）

• 现象：一个快速移动的子弹，从两个障碍物的缝隙中穿过，没有触发碰撞。
• 原因：离散的帧检测。在上一帧，子弹在障碍物前；下一帧，子弹已经穿到了障碍物后。两帧之间的位置都没有发生碰撞。
• 解决方案：
  • 连续碰撞检测（CCD）：不是检测两个静态形状，而是检测从上一帧到当前帧的“运动扫掠体”（Swept Volume）是否与目标相交。实现更复杂。
  • 增加检测频率：提高物理更新的帧率（如从60Hz到240Hz）。
  • 使用更宽的“厚”形状：对于高速物体，使用比其视觉模型稍大的碰撞体进行检测。
  • 子步采样（Sub-stepping）：在渲染帧内进行多次物理检测。例如，物体从A移动到B，在中间插入多个检测点。

问题2：碰撞法线方向不稳定，导致物体响应时抖动

• 现象：两个盒子堆叠时，上面的盒子会轻微地左右抖动。
• 原因：当两个多边形的多条边几乎平行时，计算出的几条分离轴投影重叠深度可能非常接近。由于浮点数精度误差，最小深度的轴可能在两帧之间来回切换，导致法线方向突变。
• 解决方案：
  • 法线平滑：不要直接使用当前帧的法线，而是与上一帧的法线进行加权平均（如normal = 0.7 * oldNormal + 0.3 * newNormal然后单位化）。
  • 增加容差：在比较重叠深度时，增加一个小的容差范围。如果两条轴的重叠深度差小于容差，则优先选择与上一帧法线更接近的那条轴。
  • 使用“最稳定”的轴：有时，选择与两物体中心连线方向最接近的法线作为碰撞法线，反而更稳定。

问题3：对于非常细长的多边形，检测结果不可靠

• 现象：一个很细的针状多边形与另一个多边形相交，但SAT可能检测不到。
• 原因：细长多边形在垂直于其长边的方向上投影区间非常短。如果穿透主要发生在长边方向，而算法检查的是边的法线（即短边方向），微小的浮点误差可能导致投影区间被误判为分离。
• 解决方案：
  • 增加顶点：在长边上中间插入更多顶点，但这会增加计算量。
  • 使用GJK算法：对于极端形状，Gilbert–Johnson–Keerthi (GJK) 算法可能更健壮，它不依赖于投影所有边，而是通过迭代寻找单纯形。
  • 结合AABB快速剔除：先用AABB快速判断，如果AABB不相交，则直接返回不碰撞。这可以避免大部分无意义的SAT检测。

问题4：性能瓶颈分析当游戏实体数量（n）很大时，即使有粗略阶段，精细检测的对数（m）也可能很大。使用性能分析工具（如Visual Studio Profiler、Very Sleepy）定位热点。

• 发现：projectOntoAxis中的点积循环和sqrt开方运算是主要开销。
• 优化：
  • SIMD指令集：使用SSE或AVX指令集并行计算多个顶点的点积。这对于顶点数固定的形状（如使用8个顶点的八边形）效果显著。
  • 近似计算：在寻找最小穿透深度时，可以不进行开方，而是比较overlapSquared / axisLengthSquared。因为除法和开方开销大，但比较本身不需要精确值，只需要找出最小值对应的轴。找到轴后，再计算一次精确的深度和单位法线。
  • 减少候选轴：对于某些特定形状对（如矩形对矩形），只有4条独立的轴需要检查（两个矩形的各两条主轴），而不是8条。可以写特化的检测函数。

下表总结了常见问题与解决思路：

实现一个健壮的SAT碰撞检测器，就像打磨一把好刀。核心算法（checkSATCollision）是刀身，必须坚固锋利。而数据结构、数学工具、测试用例和这些优化技巧，则是刀柄、刀鞘和磨刀石，它们共同决定了这把刀在实际战斗中的可靠性与手感。从理解原理到写出代码，再到处理各种边界情况和性能优化，每一步都需要耐心和实践。当你看到自己编写的物理引擎里，各种形状的物体流畅、稳定地碰撞和反弹时，那种成就感是对所有调试时间最好的回报。