扫描线多边形填充算法：从原理到高效实现

1. 多边形填充到底在解决什么问题1.1 从“画一个实心多边形”说起很多人第一次接触计算机图形学都是从画线、画三角形开始的。画线简单两个点连一条直线光栅化之后就是一堆像素。但当你需要画一个实心的多边形——比如一个五角星、一个不规则的地块轮廓、一个游戏里的角色碰撞区域——问题就来了怎么判断哪些像素在多边形内部哪些在外面这就是多边形填充要解决的核心问题。说白了它要回答一句话给定一个多边形的顶点序列把落在它内部的像素全部找出来并涂上颜色。听起来很直观但真正动手写代码的时候你会发现坑比想象的多。比如多边形可能是凹的不是所有内角都小于180度多边形可能有自交边和边之间会交叉顶点可能恰好落在扫描线上处理不好就会出现“漏填”或“多填”边界像素到底算不算内部不同规则会给出不同结果。我在实际写渲染器的时候最开始用的是一个非常朴素的思路对屏幕上每一个像素逐个判断它是否在多边形内部。这个方法叫逐点判断法逻辑上完全正确但性能惨不忍睹。一个800×600的视口有48万个像素每个像素都要和多边形的每条边做一次相交测试如果多边形有几十条边计算量直接爆炸。所以真正可用的多边形填充算法必须解决两个问题正确性和效率。正确性保证填充结果符合预期效率保证在实际分辨率下能跑得动。1.2 适合谁来读这篇笔记这篇笔记适合以下几类人正在学计算机图形学课程的学生课上讲了扫描线算法、种子填充算法但代码写出来总有小bug想搞清楚边界情况怎么处理自己写软渲染器的开发者不想依赖OpenGL或DirectX想从零实现一个光栅化管线多边形填充是绕不过去的一环做图像处理或GIS相关工作的工程师需要自己实现区域填充、轮廓填充理解底层原理比调库更有掌控感对底层渲染感兴趣的技术爱好者想知道GPU里那些三角形是怎么被“涂满”的。我写这篇笔记的出发点很简单把我自己在实现多边形填充时踩过的坑、想明白的原理、以及最终稳定运行的方案整理出来。不会堆砌太多数学公式但关键的计算过程一定会写清楚让你能直接照着实现。1.3 核心思路从“逐点判断”到“扫描线”逐点判断法之所以慢是因为它没有利用连贯性。屏幕上相邻的像素它们的内部/外部状态大概率是一样的。扫描线算法就是抓住了这个特点按行处理只计算每条扫描线与多边形边的交点然后成对配对一次性填充一整段像素。这个思路的转变非常关键。逐点判断是“每个像素独立判断”扫描线是“每行批量处理”。前者复杂度是O(像素数 × 边数)后者是O(扫描线数 × 边数 填充像素数)。在实际场景中扫描线数远小于像素数所以效率提升非常明显。后面我会详细拆解扫描线算法的每一个步骤包括活性边表怎么维护、交点怎么计算、边界规则怎么定。先把整体思路建立起来再抠细节。2. 扫描线填充算法的核心细节拆解2.1 算法整体流程一条一条扫描线地处理扫描线算法的基本流程可以概括为以下几步求交计算当前扫描线与多边形所有边的交点排序把所有交点按x坐标从小到大排序配对每两个交点组成一个区间这个区间内的像素就是多边形内部填充把配对区间内的像素涂上颜色下一条扫描线y坐标加1重复上述过程。这个流程看起来简单但每一步都有细节需要处理。比如求交的时候如果扫描线恰好经过多边形的顶点交点数量可能是奇数导致配对失败。再比如水平边与扫描线重合怎么处理这些问题不解决填充结果就会出错。我一开始写的时候没有考虑顶点问题结果画一个三角形顶部顶点那一行要么漏填要么多填一块。后来查了资料才知道需要制定一套顶点处理规则保证交点数量始终是偶数。2.2 活性边表避免重复计算的关键数据结构如果每条扫描线都重新遍历所有边效率还是不够高。因为很多边在连续的扫描线上都是“活跃”的它们的交点x坐标只是按斜率递增。活性边表Active Edge TableAET就是用来维护这些活跃边的。具体做法是先建立一个边表Edge TableET按每条边的最小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坐标dxx的增量即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[(i1) % 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是四核。分辨率扫描线数平均耗时640×4804801.2ms1280×7207202.8ms1920×108010805.6ms这个性能对于软渲染器来说已经够用了。如果进一步优化比如用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 常见问题速查表问题现象可能原因解决方法顶部顶点漏填顶点处理规则错误只计算y较小边的交点底部顶点多填顶点处理规则错误只计算y较小边的交点水平边导致异常水平边参与求交建立边表时跳过水平边填充区域有缝隙边界规则不统一统一使用像素中心采样填充速度慢AET排序频繁使用插入排序填充结果偏移浮点数精度问题使用定点数或双精度自交多边形填充错误填充规则选择不当使用非零环绕规则注意以上问题的排查顺序建议从顶点处理规则开始因为这是最容易出错的地方。确认顶点处理没问题后再检查水平边和排序。5. 多边形填充的扩展应用与个人体会5.1 从填充到抗锯齿边缘柔化的思路基本的多边形填充是“硬边缘”的像素要么被填充要么不被填充。在实际渲染中边缘往往需要抗锯齿让过渡更自然。一种简单的抗锯齿方法是超采样把每个像素分成多个子像素计算每个子像素是否在多边形内部然后取平均值作为像素颜色。这样边缘像素会得到介于背景色和填充色之间的颜色。另一种方法是覆盖率计算直接计算像素被多边形覆盖的面积比例用这个比例混合颜色。这种方法更精确但计算量更大。我在自己的渲染器里用的是4倍超采样边缘质量明显提升性能下降也在可接受范围内。5.2 在软渲染器中的实际集成经验把多边形填充集成到软渲染器里需要注意以下几点坐标系一致性确保多边形的顶点坐标和屏幕像素坐标在同一个坐标系下。如果顶点是归一化坐标需要先转换到屏幕坐标。深度测试如果多个多边形重叠需要配合深度缓冲只填充深度更近的像素。颜色插值如果多边形顶点有不同颜色填充时需要插值。这可以在扫描线填充的基础上增加颜色增量计算。裁剪如果多边形部分在屏幕外需要先裁剪避免无效计算。我在集成的时候最开始没有做裁剪结果一个大部分在屏幕外的多边形填充耗时反而比全屏多边形还长。后来加了简单的矩形裁剪性能立刻恢复正常。5.3 我踩过的三个坑和对应的解决方案第一个坑顶点处理规则写反了。导致三角形顶部漏填底部多填。后来仔细画图分析才明白局部最高点和局部最低点的区别。解决方案是对于局部最高点只计算一条边的交点对于局部最低点计算两条边的交点。第二个坑AET排序用了冒泡排序。每条扫描线都全量排序效率极低。后来改成插入排序利用相邻扫描线之间顺序变化小的特点性能提升明显。第三个坑浮点数累加误差。当斜率很大时x的增量很小浮点数累加多次后误差累积导致填充区域偏移。后来改用双精度浮点数问题缓解。如果追求极致可以用定点数。5.4 后续可以继续深入的方向多边形填充是光栅化的基础后续可以继续深入的方向包括三角形填充的优化三角形是最基本的多边形GPU里对三角形填充做了大量优化比如并行处理、层次化光栅化。抗锯齿技术MSAA、FXAA、TAA等都是围绕边缘质量做文章。填充规则扩展非零环绕规则、奇偶规则、正负规则不同规则适用于不同场景。硬件加速利用GPU的并行能力把扫描线算法映射到计算着色器上。我个人在实际操作中的体会是多边形填充看起来简单但真正写好、写稳需要对边界情况有足够的耐心。每一次漏填或多填背后都是一个具体的逻辑漏洞。把这些问题一个个解决掉你对光栅化的理解就会深入一层。最后再分享一个小技巧在调试填充算法的时候可以先用一个简单的凸多边形比如三角形或矩形验证基本流程确认没问题后再逐步增加复杂度测试凹多边形、自交多边形、带水平边的多边形。这样排查问题的范围会小很多效率更高。