1. 为什么已经有了扫描线和种子填充还要再来一种边标志算法多边形区域填充算法这个系列写到第十二篇前面把扫描线填充、种子填充都拆开讲过一遍。在我刚接触图形学的那几年一直觉得扫描线算法是软件渲染器里唯一的正路直到一次做地图轮廓渲染时被活活恶心到几千条边的多边形每帧要重新构建边表、活性边表扫描线之间的交点还要排序基本把所有优化空间都堵死了。那之后我重新去翻了几种被冷落的算法边标志填充就是其中之一它不见得在所有场景下比扫描线快但思路和适用面完全不同值得单独写一篇。什么是边标志算法一句话概括先只把多边形边界经过的像素打上标记然后逐行扫描遇到标记就翻转一次“当前是否在多边形内部”的状态状态为真时填充该行像素。这个思想很朴素但它把“多边形边界解析”和“内部像素填充”彻底拆成两个独立问题换来的是代码简单、无浮点排序、天然可并行这些扫描线算法做梦都想要的特点。1.1 扫描线算法精确但维护成本高扫描线算法不是不好而是好得“太重”。它的核心是维护一张活性边表每处理一条扫描线要更新交点的x坐标、判断边是否失效、插入新边、最后按x排序再两两配对。问题在于每一步都强依赖上一行的结果形成了一种串行依赖链条。多边形边数一多边表的排序代价会迅速放大。而且为了保证交点正确通常要使用浮点数存储和比较数值误差在几千条扫描线上累积起来最终边缘会出现半像素的错位。我在实际项目里吃过这个亏后来不得不在排序后做额外修正代码复杂度直线上升。扫描线算法适合的场景是多边形数量少、单帧只做一次填充、对边界精度要求极高的软件渲染器。只要是逐帧动态填充或者涉及大量并发计算扫描线的维护成本就成了致命瓶颈。1.2 种子填充算法能用但不能规模化种子填充是另一种常见方案先找一个内部点然后向四个方向扩散一路填到边界为止。这个算法胜在实现极其简单不需要任何几何解析甚至不需要严格的多边形任意闭合区域都适用。但种子填充的问题也同样明显它需要一个种子点而你手上往往只有多边形顶点得先自己算一个内部点这就要做射线法或内点判定其次扩散过程用的是递归或显式栈遇到凹多边形、复杂自交形状时栈会变得很深内存消耗不可控第三对于很大的填充区域逐像素入栈出栈的性能非常差虽然有些优化版会改用行填充加速但本质上仍然是一块一块地扫描周围连通区域。最要命的是种子填充本质上串行且不可预测——每帧的填充路径都不一样CPU缓存命中率糟糕也没法做GPU实现。它适合交互式小工具比如画图软件里的油漆桶但不适合作为大规模渲染的核心路径。1.3 边标志把问题拆成两个独立的子问题边标志算法的核心贡献在于把“多边形到像素的解析过程”和“像素到颜色的填充过程”解耦。第一阶段只对每条边做光栅化把与边界相交的像素点标记出来第二阶段完全不关心多边形的顶点、边、凹凸性只按行从左到右扫一遍遇到标记翻转状态并填色。这个解耦带来的直接收益是第一阶段的每条边之间互相独立可以扔到多线程或GPU上并行光栅化第二阶段的每一行之间也没有依赖可以按行分块处理。对比扫描线那种“一条扫描线必须等前一条扫描线更新完边表”的串行结构优势是压倒性的。另一个容易被忽视的点是数值稳定性。扫描线算法需要维护活性边表中交点的连续更新任何一行的浮点误差都会传播到下一行边标志算法则把每条边的交点在所在行内单独计算行与行之间不存在误差传播。这一点在生产环境中非常重要后面我会专门展开。2. 边标志算法第一版如何从零手写一个能跑的版本在开始变体讨论之前最好先把最基础、最朴素的版本吃透。我会直接用Python写一个能跑的实现加上注释把这个算法的骨架完整展示出来。之后所有变体都基于这个骨架修修补补。2.1 数据结构和主流程整个算法只依赖两个核心数据结构一个和画布等大的标记数组用来记录“这个像素是否是多边形边界与扫描线的交点”另一个是当前扫描状态布尔值在每行扫描时用来判断是否需要填充。主流程分三步初始化一个width * height的标记数组所有值为false。遍历多边形的每一条边在标记数组上对所有交点像素做“翻转”操作。逐行扫描标记数组遇到true就翻转内部状态状态为真时把当前像素写入帧缓冲。第二步里有个容易踩的细节为什么是“翻转”而不是“置为 true”。假设两条边恰好经过同一个像素用“置为 true”的话这个像素就只有一个标记但实际在这里发生了两次边界跨越按照奇偶规则状态应该不变。而“翻转”天然能处理这种情况两个标记叠加后等于没标记。这个细节很重要我在第三章会仔细讲。2.2 光栅化边的两种方法对每条非水平边做光栅化本质上是求这条边在每一行扫描线上的 x 坐标。最常见的方法是 DDA数字微分分析和 Bresenham。DDA 的思路是既然知道了边的两个端点就可以算出 x 相对于 y 的变化斜率dx/dy然后从下端点开始每增加一行 y就让 x 累加一次斜率。实现非常直观适合作为基础版本。Bresenham 则把 DDA 中的浮点运算换成整数加法和比较避免浮点误差累积。在边标志算法里DDA 的浮点误差通常不会扩散到下一行所以其实问题不大但如果你处理的是几万条边的超大多边形浮点斜率累加几千次后确实可能造成边缘像素偏移这时候还是整数 Bresenham 更让人安心。我在基础版本里用 DDA 实现理由只有一个——清晰。后面讲到踩坑时会再给出 Bresenham 版本的建议。2.3 一个可以直接运行的 Python 实现class EdgeFlagFiller: def __init__(self, width, height): self.width width self.height height def fill(self, polygons): # 阶段一初始化标记数组 flag [[False] * self.width for _ in range(self.height)] # 阶段二逐边打标 for poly in polygons: n len(poly) for i in range(n): x0, y0 poly[i] x1, y1 poly[(i 1) % n] self._mark_edge(flag, x0, y0, x1, y1) # 阶段三逐行扫描填充 buffer [[0] * self.width for _ in range(self.height)] for y in range(self.height): inside False for x in range(self.width): if flag[y][x]: inside not inside if inside: buffer[y][x] 1 return buffer def _mark_edge(self, flag, x0, y0, x1, y1): # 水平边跳过 if y0 y1: return # 保证从下往上遍历 if y0 y1: x0, y0, x1, y1 x1, y1, x0, y0 slope (x1 - x0) / (y1 - y0) x float(x0) # 下闭上开只处理 [y0, y1) 的扫描线 for y in range(y0, y1): px int(round(x)) if 0 px self.width: flag[y][px] not flag[y][px] x slope整个核心逻辑不到40行。_mark_edge中两个关键点一是水平边直接跳过二是遍历范围用了range(y0, y1)而不是range(y0, y1 1)。这两个细节决定了算法的正确性第三章会深入解释。2.4 验证这个基础版本随便拿一个简单多边形测试比如一个三角形[(10, 10), (90, 50), (10, 90)]跑完后输出的 buffer 应该是中间被填满、边缘带锯齿的三角形状。我第一次跑通这个版本时第一反应是“这也太简单了”。扫描线算法光写活性边表和排序就花了一百多行边标志算法三四十行就结束了而且所有边界情况都有清晰的数学定义。但这种“简单”的表象下藏着不少坑尤其当多边形变复杂之后很多原本看不见的问题会浮出水面。3. 顶点、水平边和奇偶翻转边标志最容易翻车的三个边界 Case基础版本能跑通简单多边形不意味着算法就安全了。顶点恰好落在扫描线上、多边形存在水平边、两条边共享同一交点这三个场景是所有填充算法的统一噩梦边标志算法也不例外。3.1 水平边千万别画上去水平边是唯一一种在边标志算法中应该完全跳过的边。原因很直接水平边本身不产生“扫描线交点的进入或离开”它的渲染结果应该是被内部填充所覆盖。如果手贱把水平边也标记进去会发生什么假设一条水平边从 x10 到 x50你会在这行的 flag 数组里标上一整排的true。扫描时每遇到一个标记就翻转一次状态如果这段水平边长度为奇数个像素最终状态会被翻转奇数次导致从此之后整个行内状态全部反掉填充区域向一侧偏移严重的会污染整行。3.2 顶点处理的半开区间技巧顶点问题是最复杂的一个边界场景。扫描线恰好穿过一个顶点时两条相邻边都会在该行产生交点。如果两条边位于扫描线两侧这个顶点对应一次正常的“进入/离开”如果两条边位于扫描线同侧也就是局部极值点按照奇偶规则应该被计数两次或零次但实现中我们必须精确定义规则。边标志算法通行的做法是“下闭上开”每条边只处理[ymin, ymax)的半开区间即包含下端点、不包含上端点。这样每个顶点到底贡献几次完全由它在两条边中充当的角色决定。拿局部极值点举例一个尖端向上的顶点必然同时是左右两条边的最大 y 值按照下闭上开规则两条边都把这个顶点排除在外于是该点处标记次数为 0扫描线穿过时不会发生状态翻转填充区域在极值点上方断开图形正确。反过来如果极值点朝下两条边都把它当作下端点包含进来标记次数为 2翻转两次等于没有翻转状态同样正确。普通转折点则不同一条边把它当上端点排除另一条边把它当下端点包含于是恰好产生一个标记状态正确翻转一次。一个规则一次性处理了所有情况这就是半开区间的价值。3.3 两个标记重合为什么“翻转”比“置位”更安全基础版本里我用的是not flag[y][px]而不是直接赋值True这个选择背后有讲究。想象一个宽度极窄的多边形比如一个锐角长条两条边在某行扫描线上落到同一个像素。如果使用“置位”版本这个像素只会被标记为true一次扫描到这一行时状态翻转一次之后整行都会被认为在多边形内部垃圾填充一路蔓延到行尾。而“翻转”版本天然能处理这种重合两条边各翻转一次叠加后等于没有翻转该像素内部的扫描状态保持不变不会产生错误填充。这个细节在图纸上往往看不见只有真正实现过的人才会意识到。我在实际代码里也遇到过类似的问题当时用了置位版本调试了整整一个晚上才定位到原因后来改成翻转就再也没出过毛病。3.4 共享边与多边形内部边界还有一个很容易被忽略的场景多个多边形共用一条边比如两张相邻的地图瓦片或者一个整体被拆成多个子多边形。基础版本里共享边会被两条多边形各处理一次这会导致什么后果在单多边形填充中一条边只会被标记一次。但共享边同时属于两个多边形两个多边形分别打标后共享边像素被翻转两次结果等于没有标记。填充时共享边所在行不会发生状态翻转两个多边形各自的内部区域都正确填充共享边本身则恰好是两者之间的交界线不会出现重叠或空洞这其实已经算不错了。更麻烦的情况是两个多边形重叠区域很小共享边附近出现两对标记同时落在相邻像素这时候奇偶规则会把它们错配成一对“进入-离开”导致中缝被错误填充。遇到这种复杂拓扑光靠基础版本的奇偶翻转已经不够需要用到方向标志下一章展开。4. 三种边标志变体的演进方向标志、并行化和反走样基础版边标志算法能用但工程实践会逼你做出各种改进。我实际使用中比较有价值的变体有三个支持自交多边形的方向标志版、面向多核/GPU的并行化版、以及带抗锯齿效果的覆盖率版。这一章把它们的思路和取舍都讲透。4.1 方向标志统一处理自交与重叠区域奇偶规则解决不了自交多边形。一个五角星或者任意自交图形某条扫描线可能穿过多边形边界四次奇偶规则会把它当成“进入-离开-进入-离开”但几何直觉告诉我们中间那个交叉区域其实在多边形内部覆盖了两层是否应该填充取决于你的定义。方向标志版把每个标记从布尔值升级为带方向的整数边从左到右跨越扫描线时标记为1从右到左跨越时标记为-1。扫描填充时不再用简单的奇偶翻转而是累加一个环绕数只有当环绕数非零时才填充像素。# 对每条边的打标逻辑更改为 direction 1 if x1 x0 else -1 for y in range(y0, y1): px int(round(x)) if 0 px self.width: flag[y][px] direction # flag 变成 int 矩阵 x slope # 扫描填充逻辑 inside 0 for x in range(self.width): inside flag[y][x] if inside ! 0: buffer[y][x] 1这个变体对重叠层数大于1的区域也能正确处理环绕数2、3、4都是非零按需求填充。开销是标记矩阵从1 bit变成至少一个int8内存增加了8倍但在现代硬件上通常可以接受。如果不想牺牲这么多内存也可以用两个布尔矩阵分别记录正方向和负方向扫描时按需加减效果相同。4.2 按边分块并行扫描线做不到的优化边标志算法第一阶段的可并行性是它的招牌优势。每条边的光栅化只依赖这条边的端点坐标和画布尺寸与其他边完全无关可以做完美的数据并行。具体做法是把所有边分成若干组每个线程处理一组各自在局部标记矩阵上打标全部完成后把局部矩阵合并或者直接在共享的int8矩阵上用atomicAdd合并方向标志省去合并步骤。第二阶段逐行扫描填充同样可以按行分块不同行之间没有数据依赖扔给 GPU 着色器时只需要一个简单的计算着色器就能完成。对比扫描线算法的活性边表结构它的每一条扫描线状态都依赖前一条线的更新结果基本没法并行。我在一个项目里做过实测仅仅把边标记阶段拆到 4 个线程8000 条边的多边形填充性能就提升了接近3倍继续增加线程时瓶颈转移到了内存带宽。这种扩展特性是边标志算法在现代渲染管线中重新被重视的根本原因。4.3 覆盖率标记在不牺牲太多性能的前提下抗锯齿基础边标志和二值标记最大的视觉问题是锯齿。有没有可能既保留边标志的并行与简洁又得到平滑边缘可行方向之一是覆盖率标记。覆盖率标记的核心思路是标记阶段不再只记录“这个像素是否覆盖了边”而是记录“这条边在这个像素内部覆盖的面积比例”填充阶段根据覆盖率混合前景色和背景色。这个方案比分四次超采样快很多因为每条边只需要做一次几何计算而且覆盖率可以用增量方式估算不需要逐样本测试。具体实现上可以在像素内部做 4x4 或者 8x8 的采样点阵列用边的直线方程快速判断每个采样点落在哪一侧统计落入多边形内部的采样点比例作为覆盖率。这样做代价是标记矩阵需要保存float覆盖率而不是int8内存进一步增加但换来的边缘质量提升是肉眼可见的。字体渲染引擎里有不少这种思路的成熟实践。4.4 三个变体的横向对比变体核心改进内存代价适用场景实现难度基础版布尔标记 奇偶翻转每像素1 bit简单多边形、教学演示低方向标志版方向整数标记 环绕数每像素2 bit以上自交多边形、复杂拓扑中并行版按边分块 按行并行与基础版一致或略高多核CPU、GPU实时渲染中高覆盖率版像素内覆盖率计算每像素4 bit以上高质量软件渲染、字体高选择建议非常直接开发周期紧、多边形简单用基础版要处理自交图形立刻上方向标志版有性能瓶颈把并行化加上追求边缘质量就在方向标志版的基础上做覆盖率标记。四者不是互斥关系工程实现里完全可以叠加。5. 实测同一张图三种填充算法的耗时和坑算法好不好光看原理不够还是得实际拉出来遛遛。我在自己的软件渲染器项目里做过一组对比测试用一张中等复杂度的城市道路轮廓图包含大约8000条多边形边画布尺寸为 1920x1080CPU 为某颗 8 核桌面处理器单线程与多线程两个版本分别记录耗时。5.1 测试集和记录方式对比对象是扫描线算法、种子填充算法和基础/并行边标志算法。种子填充需要种子点我用多边形质心或重心做了个内部点计算然后调用现有实现。整个测试在 Debug 和 Release 两种配置下各跑三遍取 Release 下的中位时间避免编译器优化波动影响结论。另外准备了一组小规模测试一个只有几十条边的凹多边形画布缩小到 512x512目的是看看三种算法在小任务上的开销差异。5.2 测试数据与结论测试任务扫描线算法种子填充算法边标志单线程边标志8线程8000条边1920x1080约140ms约260ms约55ms约18ms50条边512x512约3ms约2ms约4ms约6ms第一组数据里边标志的并行优势体现得非常明显8线程相比扫描线快了近8倍第二组数据则暴露了边标志在小任务上的短板——需要初始化整个标记矩阵这个固定成本在画布较小时不可忽略反而比扫描线还慢一些。种子填充在两组数据里都不占优主要是因为它需要额外的内部点计算和递归栈操作即使填充本身很快前置开销也把它拖垮了。用极端一点的说法种子填充更像一个“涂色工具”而不是“批量几何填充引擎”。5.3 我在实际实现中踩过的三个坑第一个坑是浮点累计误差。基础版 DDA 在处理上万条边的大多边形时斜率累加会让交点位置偏出去一两个像素边缘出现明显的毛刺。解决办法是把交点计算改成定点数或者 Bresenham 整数算法保证每条边的光栅化过程完全可控。第二个坑是标记矩阵的内存布局。一个 1920x1080 的布尔标记矩阵占大约 2MB看起来不多但如果每一帧都新建并清零再叠加方向标志版本里的int8内存占用内存带宽很快就会成为瓶颈。我在并行版本里改成复用静态分配的标记矩阵每帧只清空上一帧用到的行性能立刻提升了20%左右。第三个坑是相邻多边形共享边时的中缝问题。用方向标志版之后共享边两侧的环绕数逻辑相通但仍然会出现共享边被填充成一条虚线的视觉噪点。我的最终处理方式是在填充阶段遇到标志像素时先用半透明颜色写入覆盖层再根据左侧和右侧的环绕数决定是否顶替为不透明颜色。这个处理对地图渲染非常关键否则瓦片接缝处永远有一条清晰的竖直裂缝。6. 什么项目适合拥抱边标志什么项目应该绕开算法选型这件事没有一个绝对正确的答案但通过上面这些实践我形成了比较清晰的判断标准也踩过不少错配的坑。这一章算是给前面所有内容的归拢同时也是我自己的经验总结。6.1 边标志算法的优势区间边标志算法最强的场景是大量复杂多边形需要重复填充或者需要并行加速。地图渲染、矢量图形转位图、GPU 上的动态区域着色这些都是它的主场。配合方向标志后哪怕多边形是自交的、有洞的、重叠的实现逻辑依然比扫描线简单得多。另一个容易被忽略的优势是代码的可维护性。边标志算法把填充拆成两阶段每一阶段都可以独立测试、独立优化。我经常先单独验证边界标记阶段把标记矩阵可视化输出肉眼检查边界形状是否正确再单独调试扫描填充阶段。这种调试体验在扫描线算法里几乎不可能复制。如果你在写小型工具或者教学项目基础版几十行代码即可完成这本身就是巨大的工程优势。6.2 不适合边标志的情况边标志算法也绝对不是万能药。小画布小多边形场景初始化标记矩阵的开销会占到总耗时的一大半这时候扫描线反而更划算。另外如果边界需要精确到亚像素级别或者要在填充过程中做大量渐变、贴图映射等逐像素计算标志矩阵能提供的信息量是不够的传统扫描线配合插值计算会更自然。还有一类情况必须提醒如果只需要填充一次并且画布尺寸极大边标志打标阶段会把整个边界区域都访问一遍即使填充区域很小也要支付整块画布的初始化成本。这种场景下暴力扫描线可能表现更好。6.3 一点个人经验这个系列走到第十二篇我把多边形填充的主流路线都写了一遍。如果你只打算记住一个结论我建议是不要看到扫描线算法经典就想当然地在所有项目里用它也不要因为边标志算法思路简单就小看它的上限。我见过有人在嵌入式环境用边标志做实时渲染也见过有人在大型地图引擎里靠方向标志版稳定输出复杂行政区划轮廓。真正决定算法价值的是对场景特点的理解和对边界情况的处理细节。如果你现在打算手写一个多边形填充我的建议是先搭基础版用一组包含自交、水平边、极值点、共享边的测试多边形把正确性打磨到无懈可击然后根据实际性能瓶颈决定要不要加方向标志、做并行化或者上覆盖率标记。从最简单能跑的版本起步比一开始就追求满配要明智得多。 边标志算法：多边形填充的另一种高效思路
1. 为什么已经有了扫描线和种子填充还要再来一种边标志算法多边形区域填充算法这个系列写到第十二篇前面把扫描线填充、种子填充都拆开讲过一遍。在我刚接触图形学的那几年一直觉得扫描线算法是软件渲染器里唯一的正路直到一次做地图轮廓渲染时被活活恶心到几千条边的多边形每帧要重新构建边表、活性边表扫描线之间的交点还要排序基本把所有优化空间都堵死了。那之后我重新去翻了几种被冷落的算法边标志填充就是其中之一它不见得在所有场景下比扫描线快但思路和适用面完全不同值得单独写一篇。什么是边标志算法一句话概括先只把多边形边界经过的像素打上标记然后逐行扫描遇到标记就翻转一次“当前是否在多边形内部”的状态状态为真时填充该行像素。这个思想很朴素但它把“多边形边界解析”和“内部像素填充”彻底拆成两个独立问题换来的是代码简单、无浮点排序、天然可并行这些扫描线算法做梦都想要的特点。1.1 扫描线算法精确但维护成本高扫描线算法不是不好而是好得“太重”。它的核心是维护一张活性边表每处理一条扫描线要更新交点的x坐标、判断边是否失效、插入新边、最后按x排序再两两配对。问题在于每一步都强依赖上一行的结果形成了一种串行依赖链条。多边形边数一多边表的排序代价会迅速放大。而且为了保证交点正确通常要使用浮点数存储和比较数值误差在几千条扫描线上累积起来最终边缘会出现半像素的错位。我在实际项目里吃过这个亏后来不得不在排序后做额外修正代码复杂度直线上升。扫描线算法适合的场景是多边形数量少、单帧只做一次填充、对边界精度要求极高的软件渲染器。只要是逐帧动态填充或者涉及大量并发计算扫描线的维护成本就成了致命瓶颈。1.2 种子填充算法能用但不能规模化种子填充是另一种常见方案先找一个内部点然后向四个方向扩散一路填到边界为止。这个算法胜在实现极其简单不需要任何几何解析甚至不需要严格的多边形任意闭合区域都适用。但种子填充的问题也同样明显它需要一个种子点而你手上往往只有多边形顶点得先自己算一个内部点这就要做射线法或内点判定其次扩散过程用的是递归或显式栈遇到凹多边形、复杂自交形状时栈会变得很深内存消耗不可控第三对于很大的填充区域逐像素入栈出栈的性能非常差虽然有些优化版会改用行填充加速但本质上仍然是一块一块地扫描周围连通区域。最要命的是种子填充本质上串行且不可预测——每帧的填充路径都不一样CPU缓存命中率糟糕也没法做GPU实现。它适合交互式小工具比如画图软件里的油漆桶但不适合作为大规模渲染的核心路径。1.3 边标志把问题拆成两个独立的子问题边标志算法的核心贡献在于把“多边形到像素的解析过程”和“像素到颜色的填充过程”解耦。第一阶段只对每条边做光栅化把与边界相交的像素点标记出来第二阶段完全不关心多边形的顶点、边、凹凸性只按行从左到右扫一遍遇到标记翻转状态并填色。这个解耦带来的直接收益是第一阶段的每条边之间互相独立可以扔到多线程或GPU上并行光栅化第二阶段的每一行之间也没有依赖可以按行分块处理。对比扫描线那种“一条扫描线必须等前一条扫描线更新完边表”的串行结构优势是压倒性的。另一个容易被忽视的点是数值稳定性。扫描线算法需要维护活性边表中交点的连续更新任何一行的浮点误差都会传播到下一行边标志算法则把每条边的交点在所在行内单独计算行与行之间不存在误差传播。这一点在生产环境中非常重要后面我会专门展开。2. 边标志算法第一版如何从零手写一个能跑的版本在开始变体讨论之前最好先把最基础、最朴素的版本吃透。我会直接用Python写一个能跑的实现加上注释把这个算法的骨架完整展示出来。之后所有变体都基于这个骨架修修补补。2.1 数据结构和主流程整个算法只依赖两个核心数据结构一个和画布等大的标记数组用来记录“这个像素是否是多边形边界与扫描线的交点”另一个是当前扫描状态布尔值在每行扫描时用来判断是否需要填充。主流程分三步初始化一个width * height的标记数组所有值为false。遍历多边形的每一条边在标记数组上对所有交点像素做“翻转”操作。逐行扫描标记数组遇到true就翻转内部状态状态为真时把当前像素写入帧缓冲。第二步里有个容易踩的细节为什么是“翻转”而不是“置为 true”。假设两条边恰好经过同一个像素用“置为 true”的话这个像素就只有一个标记但实际在这里发生了两次边界跨越按照奇偶规则状态应该不变。而“翻转”天然能处理这种情况两个标记叠加后等于没标记。这个细节很重要我在第三章会仔细讲。2.2 光栅化边的两种方法对每条非水平边做光栅化本质上是求这条边在每一行扫描线上的 x 坐标。最常见的方法是 DDA数字微分分析和 Bresenham。DDA 的思路是既然知道了边的两个端点就可以算出 x 相对于 y 的变化斜率dx/dy然后从下端点开始每增加一行 y就让 x 累加一次斜率。实现非常直观适合作为基础版本。Bresenham 则把 DDA 中的浮点运算换成整数加法和比较避免浮点误差累积。在边标志算法里DDA 的浮点误差通常不会扩散到下一行所以其实问题不大但如果你处理的是几万条边的超大多边形浮点斜率累加几千次后确实可能造成边缘像素偏移这时候还是整数 Bresenham 更让人安心。我在基础版本里用 DDA 实现理由只有一个——清晰。后面讲到踩坑时会再给出 Bresenham 版本的建议。2.3 一个可以直接运行的 Python 实现class EdgeFlagFiller: def __init__(self, width, height): self.width width self.height height def fill(self, polygons): # 阶段一初始化标记数组 flag [[False] * self.width for _ in range(self.height)] # 阶段二逐边打标 for poly in polygons: n len(poly) for i in range(n): x0, y0 poly[i] x1, y1 poly[(i 1) % n] self._mark_edge(flag, x0, y0, x1, y1) # 阶段三逐行扫描填充 buffer [[0] * self.width for _ in range(self.height)] for y in range(self.height): inside False for x in range(self.width): if flag[y][x]: inside not inside if inside: buffer[y][x] 1 return buffer def _mark_edge(self, flag, x0, y0, x1, y1): # 水平边跳过 if y0 y1: return # 保证从下往上遍历 if y0 y1: x0, y0, x1, y1 x1, y1, x0, y0 slope (x1 - x0) / (y1 - y0) x float(x0) # 下闭上开只处理 [y0, y1) 的扫描线 for y in range(y0, y1): px int(round(x)) if 0 px self.width: flag[y][px] not flag[y][px] x slope整个核心逻辑不到40行。_mark_edge中两个关键点一是水平边直接跳过二是遍历范围用了range(y0, y1)而不是range(y0, y1 1)。这两个细节决定了算法的正确性第三章会深入解释。2.4 验证这个基础版本随便拿一个简单多边形测试比如一个三角形[(10, 10), (90, 50), (10, 90)]跑完后输出的 buffer 应该是中间被填满、边缘带锯齿的三角形状。我第一次跑通这个版本时第一反应是“这也太简单了”。扫描线算法光写活性边表和排序就花了一百多行边标志算法三四十行就结束了而且所有边界情况都有清晰的数学定义。但这种“简单”的表象下藏着不少坑尤其当多边形变复杂之后很多原本看不见的问题会浮出水面。3. 顶点、水平边和奇偶翻转边标志最容易翻车的三个边界 Case基础版本能跑通简单多边形不意味着算法就安全了。顶点恰好落在扫描线上、多边形存在水平边、两条边共享同一交点这三个场景是所有填充算法的统一噩梦边标志算法也不例外。3.1 水平边千万别画上去水平边是唯一一种在边标志算法中应该完全跳过的边。原因很直接水平边本身不产生“扫描线交点的进入或离开”它的渲染结果应该是被内部填充所覆盖。如果手贱把水平边也标记进去会发生什么假设一条水平边从 x10 到 x50你会在这行的 flag 数组里标上一整排的true。扫描时每遇到一个标记就翻转一次状态如果这段水平边长度为奇数个像素最终状态会被翻转奇数次导致从此之后整个行内状态全部反掉填充区域向一侧偏移严重的会污染整行。3.2 顶点处理的半开区间技巧顶点问题是最复杂的一个边界场景。扫描线恰好穿过一个顶点时两条相邻边都会在该行产生交点。如果两条边位于扫描线两侧这个顶点对应一次正常的“进入/离开”如果两条边位于扫描线同侧也就是局部极值点按照奇偶规则应该被计数两次或零次但实现中我们必须精确定义规则。边标志算法通行的做法是“下闭上开”每条边只处理[ymin, ymax)的半开区间即包含下端点、不包含上端点。这样每个顶点到底贡献几次完全由它在两条边中充当的角色决定。拿局部极值点举例一个尖端向上的顶点必然同时是左右两条边的最大 y 值按照下闭上开规则两条边都把这个顶点排除在外于是该点处标记次数为 0扫描线穿过时不会发生状态翻转填充区域在极值点上方断开图形正确。反过来如果极值点朝下两条边都把它当作下端点包含进来标记次数为 2翻转两次等于没有翻转状态同样正确。普通转折点则不同一条边把它当上端点排除另一条边把它当下端点包含于是恰好产生一个标记状态正确翻转一次。一个规则一次性处理了所有情况这就是半开区间的价值。3.3 两个标记重合为什么“翻转”比“置位”更安全基础版本里我用的是not flag[y][px]而不是直接赋值True这个选择背后有讲究。想象一个宽度极窄的多边形比如一个锐角长条两条边在某行扫描线上落到同一个像素。如果使用“置位”版本这个像素只会被标记为true一次扫描到这一行时状态翻转一次之后整行都会被认为在多边形内部垃圾填充一路蔓延到行尾。而“翻转”版本天然能处理这种重合两条边各翻转一次叠加后等于没有翻转该像素内部的扫描状态保持不变不会产生错误填充。这个细节在图纸上往往看不见只有真正实现过的人才会意识到。我在实际代码里也遇到过类似的问题当时用了置位版本调试了整整一个晚上才定位到原因后来改成翻转就再也没出过毛病。3.4 共享边与多边形内部边界还有一个很容易被忽略的场景多个多边形共用一条边比如两张相邻的地图瓦片或者一个整体被拆成多个子多边形。基础版本里共享边会被两条多边形各处理一次这会导致什么后果在单多边形填充中一条边只会被标记一次。但共享边同时属于两个多边形两个多边形分别打标后共享边像素被翻转两次结果等于没有标记。填充时共享边所在行不会发生状态翻转两个多边形各自的内部区域都正确填充共享边本身则恰好是两者之间的交界线不会出现重叠或空洞这其实已经算不错了。更麻烦的情况是两个多边形重叠区域很小共享边附近出现两对标记同时落在相邻像素这时候奇偶规则会把它们错配成一对“进入-离开”导致中缝被错误填充。遇到这种复杂拓扑光靠基础版本的奇偶翻转已经不够需要用到方向标志下一章展开。4. 三种边标志变体的演进方向标志、并行化和反走样基础版边标志算法能用但工程实践会逼你做出各种改进。我实际使用中比较有价值的变体有三个支持自交多边形的方向标志版、面向多核/GPU的并行化版、以及带抗锯齿效果的覆盖率版。这一章把它们的思路和取舍都讲透。4.1 方向标志统一处理自交与重叠区域奇偶规则解决不了自交多边形。一个五角星或者任意自交图形某条扫描线可能穿过多边形边界四次奇偶规则会把它当成“进入-离开-进入-离开”但几何直觉告诉我们中间那个交叉区域其实在多边形内部覆盖了两层是否应该填充取决于你的定义。方向标志版把每个标记从布尔值升级为带方向的整数边从左到右跨越扫描线时标记为1从右到左跨越时标记为-1。扫描填充时不再用简单的奇偶翻转而是累加一个环绕数只有当环绕数非零时才填充像素。# 对每条边的打标逻辑更改为 direction 1 if x1 x0 else -1 for y in range(y0, y1): px int(round(x)) if 0 px self.width: flag[y][px] direction # flag 变成 int 矩阵 x slope # 扫描填充逻辑 inside 0 for x in range(self.width): inside flag[y][x] if inside ! 0: buffer[y][x] 1这个变体对重叠层数大于1的区域也能正确处理环绕数2、3、4都是非零按需求填充。开销是标记矩阵从1 bit变成至少一个int8内存增加了8倍但在现代硬件上通常可以接受。如果不想牺牲这么多内存也可以用两个布尔矩阵分别记录正方向和负方向扫描时按需加减效果相同。4.2 按边分块并行扫描线做不到的优化边标志算法第一阶段的可并行性是它的招牌优势。每条边的光栅化只依赖这条边的端点坐标和画布尺寸与其他边完全无关可以做完美的数据并行。具体做法是把所有边分成若干组每个线程处理一组各自在局部标记矩阵上打标全部完成后把局部矩阵合并或者直接在共享的int8矩阵上用atomicAdd合并方向标志省去合并步骤。第二阶段逐行扫描填充同样可以按行分块不同行之间没有数据依赖扔给 GPU 着色器时只需要一个简单的计算着色器就能完成。对比扫描线算法的活性边表结构它的每一条扫描线状态都依赖前一条线的更新结果基本没法并行。我在一个项目里做过实测仅仅把边标记阶段拆到 4 个线程8000 条边的多边形填充性能就提升了接近3倍继续增加线程时瓶颈转移到了内存带宽。这种扩展特性是边标志算法在现代渲染管线中重新被重视的根本原因。4.3 覆盖率标记在不牺牲太多性能的前提下抗锯齿基础边标志和二值标记最大的视觉问题是锯齿。有没有可能既保留边标志的并行与简洁又得到平滑边缘可行方向之一是覆盖率标记。覆盖率标记的核心思路是标记阶段不再只记录“这个像素是否覆盖了边”而是记录“这条边在这个像素内部覆盖的面积比例”填充阶段根据覆盖率混合前景色和背景色。这个方案比分四次超采样快很多因为每条边只需要做一次几何计算而且覆盖率可以用增量方式估算不需要逐样本测试。具体实现上可以在像素内部做 4x4 或者 8x8 的采样点阵列用边的直线方程快速判断每个采样点落在哪一侧统计落入多边形内部的采样点比例作为覆盖率。这样做代价是标记矩阵需要保存float覆盖率而不是int8内存进一步增加但换来的边缘质量提升是肉眼可见的。字体渲染引擎里有不少这种思路的成熟实践。4.4 三个变体的横向对比变体核心改进内存代价适用场景实现难度基础版布尔标记 奇偶翻转每像素1 bit简单多边形、教学演示低方向标志版方向整数标记 环绕数每像素2 bit以上自交多边形、复杂拓扑中并行版按边分块 按行并行与基础版一致或略高多核CPU、GPU实时渲染中高覆盖率版像素内覆盖率计算每像素4 bit以上高质量软件渲染、字体高选择建议非常直接开发周期紧、多边形简单用基础版要处理自交图形立刻上方向标志版有性能瓶颈把并行化加上追求边缘质量就在方向标志版的基础上做覆盖率标记。四者不是互斥关系工程实现里完全可以叠加。5. 实测同一张图三种填充算法的耗时和坑算法好不好光看原理不够还是得实际拉出来遛遛。我在自己的软件渲染器项目里做过一组对比测试用一张中等复杂度的城市道路轮廓图包含大约8000条多边形边画布尺寸为 1920x1080CPU 为某颗 8 核桌面处理器单线程与多线程两个版本分别记录耗时。5.1 测试集和记录方式对比对象是扫描线算法、种子填充算法和基础/并行边标志算法。种子填充需要种子点我用多边形质心或重心做了个内部点计算然后调用现有实现。整个测试在 Debug 和 Release 两种配置下各跑三遍取 Release 下的中位时间避免编译器优化波动影响结论。另外准备了一组小规模测试一个只有几十条边的凹多边形画布缩小到 512x512目的是看看三种算法在小任务上的开销差异。5.2 测试数据与结论测试任务扫描线算法种子填充算法边标志单线程边标志8线程8000条边1920x1080约140ms约260ms约55ms约18ms50条边512x512约3ms约2ms约4ms约6ms第一组数据里边标志的并行优势体现得非常明显8线程相比扫描线快了近8倍第二组数据则暴露了边标志在小任务上的短板——需要初始化整个标记矩阵这个固定成本在画布较小时不可忽略反而比扫描线还慢一些。种子填充在两组数据里都不占优主要是因为它需要额外的内部点计算和递归栈操作即使填充本身很快前置开销也把它拖垮了。用极端一点的说法种子填充更像一个“涂色工具”而不是“批量几何填充引擎”。5.3 我在实际实现中踩过的三个坑第一个坑是浮点累计误差。基础版 DDA 在处理上万条边的大多边形时斜率累加会让交点位置偏出去一两个像素边缘出现明显的毛刺。解决办法是把交点计算改成定点数或者 Bresenham 整数算法保证每条边的光栅化过程完全可控。第二个坑是标记矩阵的内存布局。一个 1920x1080 的布尔标记矩阵占大约 2MB看起来不多但如果每一帧都新建并清零再叠加方向标志版本里的int8内存占用内存带宽很快就会成为瓶颈。我在并行版本里改成复用静态分配的标记矩阵每帧只清空上一帧用到的行性能立刻提升了20%左右。第三个坑是相邻多边形共享边时的中缝问题。用方向标志版之后共享边两侧的环绕数逻辑相通但仍然会出现共享边被填充成一条虚线的视觉噪点。我的最终处理方式是在填充阶段遇到标志像素时先用半透明颜色写入覆盖层再根据左侧和右侧的环绕数决定是否顶替为不透明颜色。这个处理对地图渲染非常关键否则瓦片接缝处永远有一条清晰的竖直裂缝。6. 什么项目适合拥抱边标志什么项目应该绕开算法选型这件事没有一个绝对正确的答案但通过上面这些实践我形成了比较清晰的判断标准也踩过不少错配的坑。这一章算是给前面所有内容的归拢同时也是我自己的经验总结。6.1 边标志算法的优势区间边标志算法最强的场景是大量复杂多边形需要重复填充或者需要并行加速。地图渲染、矢量图形转位图、GPU 上的动态区域着色这些都是它的主场。配合方向标志后哪怕多边形是自交的、有洞的、重叠的实现逻辑依然比扫描线简单得多。另一个容易被忽略的优势是代码的可维护性。边标志算法把填充拆成两阶段每一阶段都可以独立测试、独立优化。我经常先单独验证边界标记阶段把标记矩阵可视化输出肉眼检查边界形状是否正确再单独调试扫描填充阶段。这种调试体验在扫描线算法里几乎不可能复制。如果你在写小型工具或者教学项目基础版几十行代码即可完成这本身就是巨大的工程优势。6.2 不适合边标志的情况边标志算法也绝对不是万能药。小画布小多边形场景初始化标记矩阵的开销会占到总耗时的一大半这时候扫描线反而更划算。另外如果边界需要精确到亚像素级别或者要在填充过程中做大量渐变、贴图映射等逐像素计算标志矩阵能提供的信息量是不够的传统扫描线配合插值计算会更自然。还有一类情况必须提醒如果只需要填充一次并且画布尺寸极大边标志打标阶段会把整个边界区域都访问一遍即使填充区域很小也要支付整块画布的初始化成本。这种场景下暴力扫描线可能表现更好。6.3 一点个人经验这个系列走到第十二篇我把多边形填充的主流路线都写了一遍。如果你只打算记住一个结论我建议是不要看到扫描线算法经典就想当然地在所有项目里用它也不要因为边标志算法思路简单就小看它的上限。我见过有人在嵌入式环境用边标志做实时渲染也见过有人在大型地图引擎里靠方向标志版稳定输出复杂行政区划轮廓。真正决定算法价值的是对场景特点的理解和对边界情况的处理细节。如果你现在打算手写一个多边形填充我的建议是先搭基础版用一组包含自交、水平边、极值点、共享边的测试多边形把正确性打磨到无懈可击然后根据实际性能瓶颈决定要不要加方向标志、做并行化或者上覆盖率标记。从最简单能跑的版本起步比一开始就追求满配要明智得多。