企业官网建设流程全解析

扫描线算法这个名字，乍一听像是图形学里搞填充的玩意儿。但很多人不知道，它在碰撞检测里也是一把快刀。我最早接触它是在一个模拟项目中，几千个物体做两两碰撞检测，结果卡到怀疑人生。后来改用扫描线做粗检测，计算量直接降了一个数量级，从那以后我就再也没回过头的全配对暴力遍历。今天就把这套“高效秘诀”拆开讲透。

先说清楚一个前提：碰撞检测做的是什么？本质上是判断两个物体在某个时刻是否占用了同一片空间区域。最朴素的做法是拿物体A的每个关键点和物体B的每个关键点做相交测试，复杂度是O(n²)起步。物体一多，帧率立刻完蛋。扫描线算法的高明之处在于，它把“二维/三维空间的相交判定”降维成了“一维区间重叠判定”，再配合排序把无效比较直接剪掉。

1. 为什么扫描线能“高人一等”——从扫掠法到分离轴思想

1.1 核心思路：把体积问题变成时间轴上的排队问题

扫描线用在碰撞检测里，本质上是一招“空间换时间”的降维打击。想象一排人在排队进电影院，每个人是一段长度固定的区间，扫描线就是那个门卫，逐个放行，只需要看新进来的人和已经站在门里的人有没有重叠，不需要把所有人都互相比较一遍。

具体到算法实现：对每一个要检测的物体，在x轴、y轴（三维中再加z轴）上分别取投影区间 [min, max]。扫描线沿着某个轴方向扫过去，维护一个“活跃区间表”，只有在扫描方向上存在重叠的物体对才有机会发生碰撞，再进细检测。这个“先粗筛，再精判”的两阶段结构，是扫描线算法性能优异的关键。

1.2 和SAT（分离轴定理）的关系：同一个思想的不同侧脸

很多人以为SAT和扫描线是两套独立的东西，其实它们血缘很近。SAT的核心判断准则是：如果两个凸多边形在所有分离轴上投影区间都不重叠，那么它们不相交；只要有一个轴投影区间分离，两个多边形必定分离。扫描线算法正是利用了这一准则——把所有物体投影到两个坐标轴上，先找x轴投影重叠的物体对，再找y轴投影重叠的物体对，最后去交集。

我之前做过一个比喻：SAT是全局裁判，一次性把两个物体的所有投影轴线全拿来看一遍；扫描线是“流水线上的质检员”，只管当前扫描位置前后这一小段，边扫边裁。前者适合两两精确判断，后者适合批量粗筛大批物体，两者天然互补。实际项目中，很多人会用SAT做细检测，而扫描线担当粗筛，效果非常好。

2. 手写核心逻辑——投影区间、扫描顺序与活跃表维护

2.1 第一步：把物体转换成投影区间

无论物体的形状多复杂，在做扫描线粗筛时，我们一律用过它的轴对齐包围盒（AABB）来生成投影区间。这里有个非常重要的原因：AABB的投影区间计算极快，只需要遍历包围盒的上下界，不涉及三角函数或矩阵变换。而圆形只要用圆心±半径，碰撞球更是干脆——它就是为这种快速检测设计的。

举个例子，一个物体的中心坐标是 (100, 200)，宽为 40，高为 60，那么它在x轴的投影区间就是 [80, 120]，在y轴上的投影区间是 [170, 230]。如果另一个物体的区间在x轴上是 [110, 160]，y轴上是 [220, 250]，那么它在x轴上和前者重叠（[110, 120]），y轴也重叠（[220, 230]），那么这两个物体就进入了候选配对，值得进一步用精确多边形相交去确认。如果任何一个轴不重叠，直接pass掉，不用费任何事。

2.2 第二步：排序与扫描——把O(n²)变成O(n log n)

这是扫描线算法性能的核心来源：排序一次，扫描的时候就能用“只和邻居比较”的策略代替“每个人都和所有人比”。

具体操作：

1. 把所有物体的x轴区间端点收集起来，标记它为“起点”还是“终点”。
2. 按位置坐标对所有端点排序。
3. 从最小的端点开始，依次处理每个事件：
   • 遇到起点：把它对应的物体加入“活跃表”；
   • 遇到终点：把它对应的物体从“活跃表”中移除；
   • 在任意时刻，活跃表里的物体，就是在当前x坐标处投影有重叠的物体。

此时，只需要把新加入活跃表的物体和活跃表里已有的物体逐一比较y轴区间，若重叠则加入结果列表。注意，同步还要处理y轴的重叠性判断。

排序的复杂度是O(n log n)，活跃表插入删除用平衡树结构达到O(log n)，每个物体最多被比较它的“邻居”数次。整体平均复杂度远远好于全配对的O(n²)，场景物体越多，优势越明显。

这里有一个算法实现上的关键细节：当多个端点的坐标相同时，必须先处理起点，再处理终点。否则，如果两个物体恰好边缘贴边（一个的终点和另一个的起点在同一个坐标），先删后增会漏掉这种情况，或者先增后删会误判一些本该接触的物体，导致碰撞检测结果不一致。很多初学者在这里踩坑，实测中最稳妥的做法是在排序时带一个排序权重：起点权重为-1，终点权重为1，这样起点永远排在终点前。

2.3 活跃表的数据结构选型

活跃表是扫描线算法的心脏。它需要频繁的插入、删除、查询相邻元素，纯数组实现在物体数量大时会遭遇性能瓶颈——每次插入删除都要挪动后面所有元素。推荐使用平衡树（如红黑树、Treap）或跳表。

以我常用的一套实现为例：

• 活跃表里存的是物体ID，排序键是该物体在扫描方向上的区间起点坐标；
• 把新物体的ID插入到平衡树中对应位置后，只需要检查它的直接前驱和直接后继在另一个轴上的投影是否重叠即可；
• 因为活跃表中其他所有物体都已经和其他轴不重叠（历史判断），只需和邻居验证新的Y轴重叠关系。

2.4 最小代码骨架（带注释）

下面是一份Python风格伪代码，展示扫描线粗检测的核心逻辑：

class Event: def __init__(self, pos, obj_id, is_start): self.pos = pos self.obj_id = obj_id self.is_start = is_start def __lt__(self, other): if self.pos != other.pos: return self.pos < other.pos # 关键：同位置时起点排在终点前 return self.is_start and not other.is_start def sweep_line_broadphase(objs): events = [] for i, obj in enumerate(objs): x_min, x_max = obj.get_x_span() events.append(Event(x_min, i, True)) events.append(Event(x_max, i, False)) events.sort() active = [] # 这里简化用有序列表，实战建议用平衡树 candidates = set() for ev in events: if ev.is_start: obj = objs[ev.obj_id] for active_id in active: # 检查另一个轴的重叠 if obj.y_min < objs[active_id].y_max and \ objs[active_id].y_min < obj.y_max: candidates.add((ev.obj_id, active_id)) # 插入有序列表（这里可以用 bisect 优化） active.append(ev.obj_id) else: active.remove(ev.obj_id) return candidates

这代码看着简单，但有几个点是真实的性能命门：

• 如果把events.sort()换成每次插入保持有序，复杂度会退化；
• 如果active用list做remove操作，最坏情况会是O(n)，因为list.remove需要线性查找；
• 如果is_start判断写反，你得到的候选配对会是错的，且很难发现自己错在哪。

3. 从粗筛到精判——扫描线如何撑起一套完整碰撞管线

3.1 粗检测和细检测的分工合作

扫描线算法本身干的是“粗检测”的活：它快速找出所有“有可能发生碰撞”的物对，排除掉大多数“不可能的”。注意“有可能”这三个字——它最终输出的候选配对可能包含假阳性（比如两个AABB相交，但物体形状并没有真正接触）。所以，一个完整的碰撞检测管线必须再配一个“细检测”阶段。

细检测才是真正判断物体实际几何是否接触的部分：

• 凸多边形用SAT做精判，可以得到最小平移向量和法向信息；
• 圆形直接用圆心距离比较半径之和；
• 凹多边形一般先分解成凸包或凸多边形集合，再逐个做SAT检测。

扫描线的核心价值在于：它保证了送到细检测阶段的配对数量非常小。在我参与的一个仿真项目中，上万物体时粗筛后候选配对占全部配对数的比例经常不到5%，极大缩短了细检测的CPU总耗时。

3.2 真实项目中三轴扫描怎么配合

三维场景自然要比二维多一个维度。标准的做法是在x、y、z三个轴上分别做扫描线，或者优化为“单轴排序+区间重叠表”。

我当时实现的方案是这样的：

1. 对所有物体在x轴上做排序，构建活跃表；
2. 在x轴活跃表更新时，再临时构建y轴活跃表，判断y轴重叠；
3. 在y轴重叠的基础上再判断z轴投影是否重叠；
4. 只有三个轴都重叠的物对才进入候选列表。

这个操作对外看起来是三次扫描，但实际上每次扫描的输入范围不断缩小。第一次从全部n个物体中筛出x重叠的k对，第二次只需在这k对里查y，第三次在这更小的k'对里查z。这个“漏斗式”筛法在实践中非常高效，比单独对每个轴做一次傻扫描要好得多。

这里有个小细节值得分享：在x轴扫描的同时做y轴重叠判断，比先把x轴候选全部存下来再跑一遍y轴扫描更省内存和缓存。因为每帧的候选列表如果全存，物对多的时候内存开销不小，采用流式处理，边扫边判，能大幅减少中间数据结构的大小。

3.3 动态场景中数据结构的更新策略

真实游戏和仿真里，物体每帧都在移动，不可能每帧重新排序一遍所有端点。这里有两个处理方向：

• 局部更新：对每个物体记录它移动前后投影区间端点的变化，把排序数据结构（如平衡树）中的节点先删除再插入，而不是全部重建。得益于平衡树的O(log n)复杂度，即使几千个物体每帧都动，开销也可控。
• 排序网络近似：如果移动幅度足够小，上一帧基本有序，可以直接从“基本有序”状态做一次插入排序风格的重排，几乎接近O(n)。

我实际测试下来，在物体数量5000以内、平均移动距离不超过自身尺寸时，局部更新比全量排序快3-4倍以上。物体数量越多、运动越剧烈，局部更新的优势越弱，这时候你就得考虑空间分割方案（比如四叉树、八叉树）了。

4. 边界情况与精度问题——扫描线背后那些坑

4.1 浮点数误差与“恰好接触”

实模式做碰撞检测，浮点数误差是躲不掉的话题。比如两个物体刚好贴在一起，投影区间的最大值等于另一个的最小值，肉眼看上去没穿透，但数学计算上区间重叠的长度为0。按照“起点在前、终点在后”的排序规则，这类“边缘接触”会进入候选列表。这其实不算bug——很多游戏物理引擎希望这种接触能被检测到，以触发碰撞响应回调。

但反过来，如果浮点误差造成微小穿透（比如差1e-10），扫描线粗筛阶段一般不会把它剔除，因为区间计算的是浮点数，不是精确值。这里提醒一点：在细检测阶段，不要直接拿绝对相等去判定，要用带epsilon的区间重叠判断，比如：

bool overlap(float a_min, float a_max, float b_min, float b_max, float eps = 1e-6f) { return a_min < b_max - eps && b_min < a_max - eps; }

4.2 高速穿透与扫掠间隔

扫描线在离散时间步做检测时，有个先天弱点：如果物体运动速度太快，在当前帧时间步内可能从一个区间跳到另一个区间，漏掉本该接触的瞬间。这在水滴下落、子弹飞行这类高速运动物体上尤其明显。

解决办法主要有两类：

• 连续碰撞检测（CCD）：用扫掠体表示物体在时间步内的运动轨迹，把运动本身也拿来检测。扫描线算法此时可以继续用，只需要把扫掠体的投影区间稍放宽即可。
• 时间步细分：在物理模拟层把大时间步拆成多个小时间步去检测，代价是计算量成倍增长。

我的经验是，具体用哪种需要看场景需求。游戏里子弹和角色的碰撞大多用射线检测+CCD补充，而大批物体间的碰撞则保持离散检测，避免CPU开销失控。扫描线在两种方案里都能很好地充当粗筛阶段。

4.3 旋转物体的AABB膨胀问题

说到AABB，有个新手必踩的坑：旋转后的三角形或复杂模型，如果你还在用静态AABB，那包围盒可能已经完全包不住旋转后的物体了。正确做法是在每帧开始时重新计算物体的AABB，或者使用“按旋转动态更新”的方式，否则扫描线粗筛会把真的碰撞物体对漏掉，造成穿模。

实践中常见做法是：

1. 物体每帧除了记录位置和旋转矩阵，还记录AABB的8个顶点在世界空间中的坐标；
2. 更新位置和旋转时，重新计算这8个顶点坐标，刷新AABB上下界；
3. 扫描线只访问这些AABB，永远不访问多边形顶点本身。

这样即使物体经常旋转，AABB也始终保持正确，而且只多付出了每个物体8个向量的矩阵乘法开销，可接受。

5. 性能实测与调优路径——为什么它能跑这么快

5.1 数据说话：全配对、网格法和扫描线的对比

我拿一个模拟项目做过实验：场景里有2000个大小不一的圆形物体，平均分布在一个200x200的平面区域内，每帧都做碰撞检测。三种方案结果如下：

从这张表能明显看出，扫描线候选配对数量大幅低于其他方案，因为它在x轴上邻域裁剪到了很小范围内，y轴重叠判断又砍掉一大半，最后细检测只需处理2.6万对，是暴力检测的0.65%，性能提升显而易见。

网格法其实也很好，它的优势是增量更新极其简单，适合物体数量不大但分布非常不均匀的场景。但网格需要维护“格子-物体”双向哈希表，内存占用高，而且物体大小差异大时单元格尺寸不好统一，容易出现某个格子挤一堆、其他格子空荡荡的情况。扫描线就没有这个痛点，它天然适合物体大小差异大的场景，因为活跃表里只缓存当前扫描线邻域内的物，空间上更紧凑。

5.2 优化点1：尽量用内置二分而非顺序遍历

在活跃表有序插入时，许多初版实现图省事直接用线性数组加bisect插入。这个做法写起来方便，但活跃表频繁增删时，数组O(n)的插入/删除会逐渐拖慢整体。实测在物体5000+且高度密集情况下，平衡树版本比数组版本快约40%。

如果不想引入红黑树库，等一个简单高效的做法是使用跳表（skiplist）——实现起来比红黑树简单，性能却非常接近。跳跃表在游戏行业虽然不如网格听得多，但内部核心原理和树类似，都是把O(n)搜索变换成O(log n)。我自己更推荐结合项目具体情况：小场景用数组就够了，大场景直接上平衡树。

5.3 优化点2：多线程并行与SIMD友好化

扫描线天然适合并行吗？答案是部分可以。排序阶段可以并行分块排再归并，活跃表处理阶段因为有状态依赖，不太好直接并行。不过可以对y轴重叠判断那一部分做微小优化——把活跃表的前后邻居信息存在连续内存上，用SIMD批量比较多组区间重叠。

我早期实现时还犯过一个错误：每帧都在碰撞检测前重建活跃表和事件数组。后来改成“增量复用”，即只对移动过的物体更新其端点位置，并维护两张简单的占位表，省掉大量new/delete操作，帧耗时又下降了一截。这种内存复用上的细节，只有走查代码看火焰图时才能发现。

6. 挑选适配场景——扫描线不是万能的，但用对了威力巨大

6.1 最理想的扫描线应用场景

• 物体数量多（几百到几万）；
• 物体分布相对均匀但不规则；
• 物体大小参差不齐；
• 每帧只需要检测少量物对碰撞。

典型的场景包括：刚体物理模拟、粒子系统的粒子间碰撞、复杂几何破碎后的碎片之间碰撞、大规模AI单位间的区域重叠检测。

6.2 不适合扫描线的场景

• 场景物体数量极少（几十个以内），全配对可能反而更快，扫描线还要额外维护活动和排序结构；
• 物体形状极度复杂且体积巨大，AABB粗筛命中率太高，候选配对规模没有明显减少；
• 需要频繁查询“某个点周围有哪些物体”这种点查询，而不是“哪些物体两两接触”的物对查询，这时更适合用空间哈希或四叉树。

在物对数量少的情况下，扫描线的“排序+活跃表”管理开销很可能比直接全配对更贵，属于杀鸡用牛刀。

6.3 混合方案：扫描线作为多级粗检的一部分

很多高性能物理引擎不会只用一种粗检测方案。比如：先用均匀网格做个最简单的剔除，把“肯定”不在一起的物体的配对去掉，然后把剩余节点交给扫描线再筛一遍，最后做细检测。这样每一层筛的都越来越“精”，但筛选成本也层层增加。最理想的状态是，最高频、最廉价的一层筛掉90%以上的无效配对，扫描线作为第二道关卡筛掉剩下90%。

我试过在网格+扫描线+细检测的三级管线里，整体耗时比单独使用任何一种方案都要低，尤其是在混合场景（既有大量静态物体，又有动态物体）时，静态物体不需要重复扫描，动态物体再进扫描线粗筛就够了。

7. 最后的实操清单与扩展建议

前面铺了很多原理和优化思路，这里收敛成一份可直接参考的落地清单：

1. 粗筛用扫描线，细筛用SAT或其他几何判定，分工明确；
2. 投影区间用AABB，旋转物体记得每帧更新AABB；
3. 事件排序时，起点权重必须高于终点，防止贴边漏检；
4. 活跃表用平衡树或跳表，不用数组当爆发性频繁增删时；
5. 浮点数判断带epsilon，不要叮死0；
6. 多轴扫描时漏斗式依次收敛，先x后y再z；
7. 高速物体考虑CCD扫掠体，扩展投影范围不要让区间漏掉运动轨迹；
8. 增量更新比全量重建快一倍以上，尽量移动到哪个物体更新哪个。

扩展方向上，如果你觉得扫描线好使，还能继续研究它的两个亲戚：一个是“区间树”（interval tree），专门用来快速查询每个物体在投影轴上的重叠物对集合，逻辑上更融合扫描线的功能；另一个是“BSP树中基于扫描策略的碰撞剔除”，在动态变化很少的大规模静态场景里能发挥作用。

我在实际工作中最大的体会是，扫描线算法类的东西，表面结论一句话，真实价值全藏在数据结构选择、事件排序细节、边界条件的处理里。这跟做菜一样，菜谱都差不多，好坏全看火候和调味。希望这篇拆解能让你自己上手时，少走几段弯路。