1. 多边形填充到底在解决什么问题

1.1 从“画一个实心多边形”说起

很多人第一次接触计算机图形学，都是从画线、画三角形开始的。画线简单，两个点连一条直线，光栅化之后就是一堆像素。但当你需要画一个实心的多边形——比如一个五角星、一个不规则的地块轮廓、一个游戏里的角色碰撞区域——问题就来了：怎么判断哪些像素在多边形内部，哪些在外面？

这就是多边形填充要解决的核心问题。说白了，它要回答一句话：给定一个多边形的顶点序列，把落在它内部的像素全部找出来并涂上颜色。

听起来很直观，但真正动手写代码的时候，你会发现坑比想象的多。比如：

• 多边形可能是凹的，不是所有内角都小于180度；
• 多边形可能有自交，边和边之间会交叉；
• 顶点可能恰好落在扫描线上，处理不好就会出现“漏填”或“多填”；
• 边界像素到底算不算内部，不同规则会给出不同结果。

我在实际写渲染器的时候，最开始用的是一个非常朴素的思路：对屏幕上每一个像素，逐个判断它是否在多边形内部。这个方法叫逐点判断法，逻辑上完全正确，但性能惨不忍睹。一个800×600的视口有48万个像素，每个像素都要和多边形的每条边做一次相交测试，如果多边形有几十条边，计算量直接爆炸。

所以，真正可用的多边形填充算法，必须解决两个问题：正确性和效率。正确性保证填充结果符合预期，效率保证在实际分辨率下能跑得动。

1.2 适合谁来读这篇笔记

这篇笔记适合以下几类人：

• 正在学计算机图形学课程的学生：课上讲了扫描线算法、种子填充算法，但代码写出来总有小bug，想搞清楚边界情况怎么处理；
• 自己写软渲染器的开发者：不想依赖OpenGL或DirectX，想从零实现一个光栅化管线，多边形填充是绕不过去的一环；
• 做图像处理或GIS相关工作的工程师：需要自己实现区域填充、轮廓填充，理解底层原理比调库更有掌控感；
• 对底层渲染感兴趣的技术爱好者：想知道GPU里那些三角形是怎么被“涂满”的。

我写这篇笔记的出发点很简单：把我自己在实现多边形填充时踩过的坑、想明白的原理、以及最终稳定运行的方案整理出来。不会堆砌太多数学公式，但关键的计算过程一定会写清楚，让你能直接照着实现。

1.3 核心思路：从“逐点判断”到“扫描线”

逐点判断法之所以慢，是因为它没有利用连贯性。屏幕上相邻的像素，它们的内部/外部状态大概率是一样的。扫描线算法就是抓住了这个特点：按行处理，只计算每条扫描线与多边形边的交点，然后成对配对，一次性填充一整段像素。

这个思路的转变非常关键。逐点判断是“每个像素独立判断”，扫描线是“每行批量处理”。前者复杂度是O(像素数 × 边数)，后者是O(扫描线数 × 边数 + 填充像素数)。在实际场景中，扫描线数远小于像素数，所以效率提升非常明显。

后面我会详细拆解扫描线算法的每一个步骤，包括活性边表怎么维护、交点怎么计算、边界规则怎么定。先把整体思路建立起来，再抠细节。

2. 扫描线填充算法的核心细节拆解

2.1 算法整体流程：一条一条扫描线地处理

扫描线算法的基本流程可以概括为以下几步：

1. 求交：计算当前扫描线与多边形所有边的交点；
2. 排序：把所有交点按x坐标从小到大排序；
3. 配对：每两个交点组成一个区间，这个区间内的像素就是多边形内部；
4. 填充：把配对区间内的像素涂上颜色；
5. 下一条扫描线：y坐标加1，重复上述过程。

这个流程看起来简单，但每一步都有细节需要处理。比如求交的时候，如果扫描线恰好经过多边形的顶点，交点数量可能是奇数，导致配对失败。再比如，水平边与扫描线重合，怎么处理？这些问题不解决，填充结果就会出错。

我一开始写的时候，没有考虑顶点问题，结果画一个三角形，顶部顶点那一行要么漏填，要么多填一块。后来查了资料才知道，需要制定一套顶点处理规则，保证交点数量始终是偶数。

2.2 活性边表：避免重复计算的关键数据结构

如果每条扫描线都重新遍历所有边，效率还是不够高。因为很多边在连续的扫描线上都是“活跃”的，它们的交点x坐标只是按斜率递增。活性边表（Active Edge Table，AET）就是用来维护这些活跃边的。

具体做法是：

• 先建立一个边表（Edge Table，ET），按每条边的最小y坐标分类存储；
• 从最小的y开始扫描，把ET中对应y的边加入AET；
• 每条扫描线处理完后，更新AET中每条边的交点x坐标（x += 1/斜率）；
• 如果某条边的最大y等于当前扫描线，就把它从AET中移除。

这样做的好处是，每条边只在它跨越的扫描线范围内被处理，不需要每次全量遍历。AET中的边按交点x坐标排序，配对的时候直接相邻取两个就行。

注意：AET中的边需要保持按x坐标有序。如果每次更新后重新排序，效率会下降。常见的优化是使用插入排序，因为相邻扫描线之间，边的相对顺序变化很小。

2.3 交点计算与边界规则：避免漏填和多填

交点计算本身不难，就是直线方程求交。但边界规则才是真正让人头疼的地方。

问题一：扫描线经过顶点怎么办？

假设多边形有一个顶点，它的y坐标恰好等于当前扫描线的y。如果直接算交点，这个顶点会被两条边各算一次，导致交点数量变成奇数。解决办法是：只计算顶点所连接的两条边中，y坐标较小那条边的交点。或者更通用的做法是，把顶点分为“局部最高点”“局部最低点”“中间点”，根据类型决定是否计数。

问题二：水平边怎么处理？

水平边与扫描线重合，理论上有无穷多个交点。实际处理时，直接忽略水平边，不参与求交。因为水平边的两个端点会被相邻的非水平边处理到。

问题三：边界像素算不算内部？

这涉及到填充规则。常见的有两种：

• 奇偶规则：交点配对后，奇数区间填充，偶数区间不填充；
• 非零环绕规则：根据边的方向计算环绕数，非零则填充。

对于简单多边形，奇偶规则就够了。对于自交多边形，非零环绕规则能给出更符合直觉的结果。

我在实现的时候，用的是奇偶规则，配合顶点处理规则，基本能覆盖大多数场景。但如果多边形有自交，还是需要非零环绕规则。

2.4 斜率与增量计算：浮点数还是定点数

扫描线算法中，每条边的交点x坐标需要按斜率递增。如果直接用浮点数计算，精度问题可能导致填充结果有细微偏差。比如，当斜率很大时，x的增量很小，浮点数累加可能产生误差。

一种常见的优化是使用定点数或者整数增量。具体做法是，把x和斜率都放大若干倍，用整数运算代替浮点运算。这样既提高了速度，又避免了精度问题。

不过，在现代CPU上，浮点运算已经很快了，除非是极端性能敏感的场景，否则直接用float或double问题不大。我自己的渲染器用的是float，实测下来在1080p分辨率下填充一个几百条边的多边形，耗时在毫秒级别，完全够用。

3. 从零实现一个扫描线填充器

3.1 数据结构设计：边、边表、活性边表

先定义边的结构。一条边需要存储以下信息：

• y_max：边的最大y坐标；
• x：当前扫描线与边的交点x坐标；
• dx：x的增量，即1/斜率；
• next：指向下一条边的指针（用于链表）。

边表ET是一个数组，数组下标对应扫描线的y坐标，每个元素是一个链表，存储所有最小y等于该下标的边。

活性边表AET也是一个链表，按x坐标排序。

typedef struct Edge { int y_max; float x; float dx; struct Edge* next; } Edge; Edge* ET[MAX_Y]; // 边表 Edge* AET; // 活性边表

3.2 建立边表：按最小y坐标分类

遍历多边形的每一条边，对于非水平边，计算它的y_min、y_max、x（在y_min处的x坐标）和dx。然后把这条边插入到ET[y_min]的链表中。

for (int i = 0; i < n; i++) { Point p1 = polygon[i]; Point p2 = polygon[(i+1) % n]; if (p1.y == p2.y) continue; // 忽略水平边 if (p1.y > p2.y) { swap(p1, p2); } Edge* e = malloc(sizeof(Edge)); e->y_max = p2.y; e->x = p1.x; e->dx = (float)(p2.x - p1.x) / (p2.y - p1.y); e->next = ET[p1.y]; ET[p1.y] = e; }

这里注意，p1和p2要保证p1.y < p2.y，这样x和dx才是基于y_min计算的。

3.3 扫描线主循环：更新AET并填充像素

主循环从最小的y开始，逐条扫描线处理：

AET = NULL; for (int y = y_min; y <= y_max; y++) { // 把ET[y]中的边加入AET Edge* e = ET[y]; while (e != NULL) { insertEdge(&AET, e); e = e->next; } // 移除y_max == y的边 removeEdges(&AET, y); // 按x排序AET sortAET(&AET); // 配对填充 Edge* p = AET; while (p != NULL && p->next != NULL) { int x_start = ceil(p->x); int x_end = floor(p->next->x); for (int x = x_start; x <= x_end; x++) { setPixel(x, y, color); } p = p->next->next; } // 更新AET中每条边的x updateAET(&AET); }

这个主循环是整个算法的骨架。每一步的细节都需要仔细处理，尤其是排序和更新。

3.4 边界处理与像素中心采样

在配对填充的时候，x_start和x_end的计算方式会影响边界像素是否被填充。常见的做法是：

• x_start = ceil(左交点x)；
• x_end = floor(右交点x) - 1（如果右交点恰好是整数）。

或者更简单的做法是，直接用像素中心采样：对于每个像素，判断它的中心是否在区间内。这样边界规则更统一。

我自己的做法是，x_start = ceil(left_x)，x_end = floor(right_x)。如果left_x和right_x都是整数，那么左交点对应的像素会被填充，右交点对应的像素不会被填充。这样保证相邻多边形之间不会重叠填充。

提示：如果你的渲染器需要处理多个多边形拼接，边界规则一定要统一，否则会出现缝隙或重叠。

3.5 性能实测：不同分辨率下的表现

我在自己的软渲染器上做了简单测试，多边形是一个有200条边的不规则形状，填充区域大约占屏幕的30%。测试环境是普通笔记本，CPU是四核。

这个性能对于软渲染器来说已经够用了。如果进一步优化，比如用SIMD指令并行填充，或者用多线程按扫描线分块处理，还能再快几倍。

4. 常见问题与排查技巧实录

4.1 填充结果出现“漏填”或“多填”怎么办

这是最常见的问题，通常有以下几个原因：

• 顶点处理规则不对：扫描线经过顶点时，交点数量变成奇数。检查你的顶点处理逻辑，确保只计算一次。
• 水平边没有忽略：水平边参与求交会导致交点数量异常。确保在建立边表时跳过水平边。
• 排序不稳定：AET中的边按x排序时，如果两条边的x坐标相同，排序结果可能不一致。建议使用稳定的排序算法，或者在比较时加入次要关键字。
• 浮点数精度问题：当斜率很大时，x的增量很小，浮点数累加可能产生误差。可以尝试用定点数或双精度浮点数。

我遇到过一次漏填，排查了半天，最后发现是顶点处理规则写反了。把局部最高点和局部最低点的判断条件交换了一下，问题就解决了。

4.2 自交多边形的填充规则选择

对于自交多边形，奇偶规则和非零环绕规则会给出不同的填充结果。奇偶规则是“隔一个区间填一个”，非零环绕规则是根据边的方向计算环绕数。

如果你的应用场景是简单的区域填充，奇偶规则就够了。如果需要处理复杂路径（比如字体轮廓），建议用非零环绕规则。

实现非零环绕规则的方法是：在每条边上记录一个方向（+1或-1），填充时计算当前区间的环绕数，非零则填充。

4.3 性能瓶颈定位与优化方向

如果填充速度慢，可以从以下几个方面排查：

• AET排序太频繁：每条扫描线都重新排序AET，效率很低。可以用插入排序，利用相邻扫描线之间顺序变化小的特点。
• 交点计算重复：每条扫描线都重新计算交点，没有利用增量。确保使用dx增量更新x。
• 像素填充太慢：逐像素调用setPixel函数，函数调用开销大。可以批量填充，或者直接操作帧缓冲区。
• 内存访问不连续：AET是链表结构，内存访问不连续，缓存命中率低。可以考虑用数组代替链表。

我在优化的时候，把AET从链表改成数组，性能提升了大约30%。因为数组的内存是连续的，CPU缓存友好。

4.4 常见问题速查表

注意：以上问题的排查顺序建议从顶点处理规则开始，因为这是最容易出错的地方。确认顶点处理没问题后，再检查水平边和排序。

5. 多边形填充的扩展应用与个人体会

5.1 从填充到抗锯齿：边缘柔化的思路

基本的多边形填充是“硬边缘”的，像素要么被填充，要么不被填充。在实际渲染中，边缘往往需要抗锯齿，让过渡更自然。

一种简单的抗锯齿方法是超采样：把每个像素分成多个子像素，计算每个子像素是否在多边形内部，然后取平均值作为像素颜色。这样边缘像素会得到介于背景色和填充色之间的颜色。

另一种方法是覆盖率计算：直接计算像素被多边形覆盖的面积比例，用这个比例混合颜色。这种方法更精确，但计算量更大。

我在自己的渲染器里用的是4倍超采样，边缘质量明显提升，性能下降也在可接受范围内。

5.2 在软渲染器中的实际集成经验

把多边形填充集成到软渲染器里，需要注意以下几点：

• 坐标系一致性：确保多边形的顶点坐标和屏幕像素坐标在同一个坐标系下。如果顶点是归一化坐标，需要先转换到屏幕坐标。
• 深度测试：如果多个多边形重叠，需要配合深度缓冲，只填充深度更近的像素。
• 颜色插值：如果多边形顶点有不同颜色，填充时需要插值。这可以在扫描线填充的基础上，增加颜色增量计算。
• 裁剪：如果多边形部分在屏幕外，需要先裁剪，避免无效计算。

我在集成的时候，最开始没有做裁剪，结果一个大部分在屏幕外的多边形，填充耗时反而比全屏多边形还长。后来加了简单的矩形裁剪，性能立刻恢复正常。

5.3 我踩过的三个坑和对应的解决方案

第一个坑：顶点处理规则写反了。导致三角形顶部漏填，底部多填。后来仔细画图分析，才明白局部最高点和局部最低点的区别。解决方案是：对于局部最高点，只计算一条边的交点；对于局部最低点，计算两条边的交点。

第二个坑：AET排序用了冒泡排序。每条扫描线都全量排序，效率极低。后来改成插入排序，利用相邻扫描线之间顺序变化小的特点，性能提升明显。

第三个坑：浮点数累加误差。当斜率很大时，x的增量很小，浮点数累加多次后误差累积，导致填充区域偏移。后来改用双精度浮点数，问题缓解。如果追求极致，可以用定点数。

5.4 后续可以继续深入的方向

多边形填充是光栅化的基础，后续可以继续深入的方向包括：

• 三角形填充的优化：三角形是最基本的多边形，GPU里对三角形填充做了大量优化，比如并行处理、层次化光栅化。
• 抗锯齿技术：MSAA、FXAA、TAA等，都是围绕边缘质量做文章。
• 填充规则扩展：非零环绕规则、奇偶规则、正负规则，不同规则适用于不同场景。
• 硬件加速：利用GPU的并行能力，把扫描线算法映射到计算着色器上。

我个人在实际操作中的体会是，多边形填充看起来简单，但真正写好、写稳，需要对边界情况有足够的耐心。每一次漏填或多填，背后都是一个具体的逻辑漏洞。把这些问题一个个解决掉，你对光栅化的理解就会深入一层。

最后再分享一个小技巧：在调试填充算法的时候，可以先用一个简单的凸多边形（比如三角形或矩形）验证基本流程，确认没问题后，再逐步增加复杂度，测试凹多边形、自交多边形、带水平边的多边形。这样排查问题的范围会小很多，效率更高。