边标志算法的改进与硬件实现

王利祥，肖铁军

（江苏大学 计算机科学与通信工程学院，江苏 镇江212013）

0 引 言

传统的嵌入式图形显示的处理方式主要依赖于微处理器，然而当面对高质量和高效率显示需求时，单纯使用软件来实现多边形填充［1，2］这一复杂的过程，显然成为了图形显示质量的一个瓶颈，因此使用硬件来满足高要求显示不失为一种可行的方案。

传统的边标志算法［3］在遇到极值点［4］及狭长条时会出现异常填充的现象，因此许多文献对其进行了改进，如王秀华等［5］提出了一种改进的边标志算法，该算法成功解决了极值点问题，但是引入了扫描线填充算法［6］中使用的边表结构，使得算法的数据结构变得复杂；叶国栋等［7］提出了解决狭长条多边形填充的方法，但是在算法实现过程中使用了求交点运算，使得算法的效率有所降低。本文在深刻理解目前边标志算法的基础上，提出了一种新的改进算法。该算法充分利用了光栅化多边形边界时的特点，使用计数型的边标记变量flag，采用对访问的边界像素点的标记进行加1的操作，方便简捷地将极值点和狭长条上的点与普通边界点区别开来，从而解决了极值点和狭长条填充时产生异常现象的问题。该算法既保持了传统边标志算法不需要边表结构以及求交点运算的优点，又解决了特殊点填充时产生异常现象的问题，最终使用现场可编程门阵列（FPGA）［8］进行实现并加以验证。

1 传统边标志算法分析及缺陷

1.1 传统边标志算法的概述

传统的边标志算法的思想及实现比较简单，大致可以分为两步：

（1）边标记，即在将多边形的边进行扫描转换时对边界上的像素点打上边的标志。

（2）填充，对于每条与多边形相交的扫描线，按照从左到右的顺序逐个像素点进行扫描，判断该像素点是否在多边形的内部，如果在多边形的内部则进行填充。填充的具体实现规则为：设置一个布尔变量insider，用于表示当前点的状态。对于每条扫描线，insider的初始值为假。当访问到边界像素点时insider的值便取反。当insider的值为真时，便把该像素点填充为填充色；否则便填充为背景色。

1.2 缺 陷

传统的边标志算法在遇到以下情景时便会出现异常填充现象。

1.2.1 极值点

极值点的一般判断方法是设某两条边的交点为A，如果两条边的另一个顶点都位于点A的同侧，则点A即为极值点。否则不是极值点。例如，对于含有极值点的多边形（10，10）、（50，120）、（90，10）、（50，70），当扫描线为10和120时，就会出现在点 （50，120）处出现带 “尾巴”的现象以及2个最高点处不应该连接。填充结果如图1所示。

图1 未处理极值点时的实际填充效果

1.2.2 狭长条

狭长条问题是指当多边形的两条边的斜率非常接近时，其多边形区域太过细窄以致在这个区域中容纳不下扫描线上任何可见的最短跨段。例如对于狭长条多边形 （50，25）、（50，225）、（90，225）、（90，125）、（55，125），对于点 （50，25）附近即会出现带 “尾巴”的填充效果，如图2所示。

2 改进的边标志算法及流程图

图2 未处理狭长条问题的实际填充效果

基于上述描述分析可以发现，之所以产生填充错误的原因在于传统的边标志算法没有将普通的边界点与极值点和狭长条上的像素点区别开来，因此针对上述原因，本文提出了一种新的改进方法，其主要思想为：在进行光栅化多边形的边时，使用flag（初始值为0）标记是否为多边形的边界，当在对其余边进行光栅化时取出当前像素点的flag值，对flag值加1之后，再存储到当前像素点的flag中。依次光栅化多边形的每一条边。在进行填充的过程中，首先取出当前像素点的flag值，如果当前像素点的flag值为1，则分别取出其前一个和后一个像素点的flag值，若前后2个像素点的flag值都为1，则布尔变量insider保持不变，否则取反。填充颜色时如果flag的值大于0或者insider为真时，则对当前像素点进行填充，否则填充为背景色。如对于图1中的A点和B点，在对两点所在边界光栅化之后他们的flag值等于2，是大于1的，因此在进行多边形填充时首先将A和B点的颜色填充为填充色。又因为其前后2个像素点的flag值不都为1，因此insider的值仍未假，从而两点右边的像素点不进行填充。算法的流程如图3所示。

3 硬件实现

3.1 多边形边界的光栅化

在光栅化多边形的边界时，鉴于Bresenham直线算法［9－11］没有除法及小数运算等适合硬件实现的优点，本文选用了Bresenham直线算法。大致思想为：将二维平面划分为8个区域，如图4所示，首先将任意斜率的直线统一映射到直线斜率为 ［0，1］的IA区域中，因此在对任意直线的光栅化就简化为只对区域IA中的直线进行光栅化，然后再使用传统的Bresenham直线画法绘制直线。在光栅化的过程中再映射到原始的任意直线。这样不仅使硬件结构得到简化，硬件资源占有量也会得到相应的减少。

在边标志算法硬件实现中，直线光栅化的大致绘制过程：在图5中，ST0状态用于接收多边形边的顶点信息，如果边是水平边或竖直边则相应的转移到ST2、ST3、ST4或者ST5。若为倾斜的直线则转移到ST6状态，在状态PRE＿DRAW对直线进行映射处理，将其它区域的直线映射到统一的区域IA中，在状态POST＿DRAW时将统一区域的直线映射回到原始的区域中，在状态ADDRESS中得到相应的地址，进入状态READ＿RAM对边标记存储器进行读操作，GET＿FLAG时得到当前地址的flag，并在状态JUDGE＿FLAG时flag加1，然后将处理之后的flag值在状态WRITE＿MEMORY写入到边标记存储器中，依次对下一个像素点进行处理，直至边的终点。

3.2 多边形扫描转换

在图6中，对第一条边进行扫描时，在INIT＿MAX＿MIN状态对横纵坐标的最大最小值用得到的边的顶点信息初始化，然后GET＿POINT状态得到以后各个边的顶点信息。在ORIGIN＿MAX＿MIN及TERMINAL＿MAX＿MIN求得多边形扫描的最小区域，即多边形顶点的横纵坐标的最大值和最小值。之后进入多边形边的光栅化状态即上述的Bresenham直线算法。当bresenham＿done信号有效后即多边形的一个边光栅化之后，转入JUDGE＿LINE状态，判断是否对所有的边进行了光栅化，若有，则转向GET＿POINT状态，进行下一个边的光栅化；否则，转向SCAN＿Y状态，开始多边形的扫描转换过程。

所有的边光栅化之后，根据求得的多边形的最小扫描区域，扫描线scan＿y从最小值Y＿MIN开始依次对该水平线上的每个在X＿MIN和X＿MAX之间的像素点进行扫描，直至Y＿MAX，并在ADDRESS状态时得到当前像素点及其前后两个像素点在存储器中的地址。依次对多边形的最小扫描区域中的每个像素点进行处理。当scan＿y大于Y＿MAX时转移到IDLE＿POLY状态，表示多边形中的每个像素点处理完毕。

4 验证系统及实验结果分析

为了验证改进后的边标志算法的实际填充效果，本文首先在Intel酷睿i3双核主频为2.0GHz的处理器，内存为1G的PC计算机上分别以极值点多边形 （10，10）、 （50，120）、 （90，10）、 （50，70）和狭长条多边形 （50，25）、（50，225）、（90，225）、（90，125）、（55，125）作为实例使用VC＋＋6.0在上述PC机上进行了验证，验证结果表明没有出现异常填充的现象，之后采用DE2－70FPGA开发板和分辨率为800＊480的LCD显示屏搭建了如图7所示的基于FPGA的显示方案。

从图8可以看出，当扫描线scan＿y和scan＿x都等于10时，遇到极值点 （10，10），此时从边标志存储器中读取该极值点的标记值iflag＿poly等于2，根据本文提出的算法思想，将该极值点填充为填充色，即ocolor＿data＿poly等于0。此时insider的值没有被取反，即仍为0，因此该极值点之后的像素点没有被填充。由此可见本文提出的算法正确处理了极值点问题，同样可以验证狭长条问题。从实际填充效果图9和图10中可以看出，使用改进之后的边标志算法填充后的多边形完全解决了极值点和狭长条问题，填充效果良好。

从系统资源占用情况的角度分析，该系统使用的逻辑单元总数为1938个。由此可以看出改进之后的算法在硬件资源的占用量上还是比较少的，适合在嵌入式系统中使用。

图9 有极值点时的填充效果

图10 狭长条多边形的填充效果

从实时性角度分析，系统中使用的时钟频率为33 MHz。由上述状态机可以得到一个边界像素点的处理大约需要8个时钟周期，扫描转换过程中一个像素点需要10个时钟周期。对于上述的极值点多边形来说，边界像素点为174个，多边形的最小扫描范围中像素点的个数为9061个，从而可以估算出处理该多边形大约需要的时间为2.95ms。从上面的分析可以看出，改进之后的算法完全可以满足嵌入式系统中高质量显示的要求。

5 结束语

本文提出的改进方法不仅保持了传统的边标志算法数据结构简单、思想简单以及容易实现的优点，而且仅采用对边标记变量进行加1的方法，统一进行边界点标志，便可一次性的完成了极值点和狭长条上的点与普通边界点的区别，从而成功解决了极值点多边形和狭长条多边形填充时产生的异常现象。在改进后的算法的实现过程中不仅完全避免了为解决极值点和狭长条问题而引进复杂的边表结构或者引入求交点运算的问题，而且在使用硬件实现之后在很大程度上提高了填充效率，能够减轻嵌入式系统中微处理器的负担，提高系统的处理能力。

［1］LI Zhaoheng，ZHANG Anding，WANG Zhoulong.An improved rasterizing algorithm based on boundary－labeling ［J］.Science of Surveying and Mapping，2009，34 （5）：121－122（in Chinese）.［李兆恒，张安定，王周龙.改进的边标志栅格化算法 ［J］.测绘科学，2009，34 （5）：121－122.］

［2］LIU Yang，LI Qingcheng，BAI Zhenxuan.Research and implementation of polygon filling algorithm based on hardware［J］.Journal of Tianjin Normal University （Natural Science Edition），2010，30 （1）：19－22 （in Chinese）.［刘洋，李庆诚，白振轩.多边形填充硬件算法的研究与实现 ［J］.天津师范大学学报 （自然科学版），2010，30 （1）：19－22.］

［3］HAO Xiaosong.The common problems and solutions of boundary labeling method in the course of realization ［J］.Journal of Xi’an University of Engineering Science and Technology，2006，20 （5）：643－645 （in Chinese）.［郝筱松.边标志算法实现过程中的常见问题及解决方法 ［J］.西安工程科技学院学报，2006，20 （5）：643－645.］

［4］WU Zhangwen，YANG Dailun，GOU Chengjun，et al.Singular point distinguishing algorithm for area filling ［J］.Journal of Computer－Aided Design ＆ Computer Graphics，2003，15 （8）：979－983 （in Chinese）.［吴章文，杨代伦，勾成俊，等.区域填充极点判别算法 ［J］.计算机辅助设计与图形学学报，2003，15 （8）：979－983.］

［5］WANG Xiuhua，YAN Bing.An improved edge marking algorithm ［J］.Journal of Computer Applications，2004，24（s1）：181－182 （in Chinese）.［王秀华，严兵.一种边标志填充的改进算法 ［J］.计算机应用，2004，24 （s1）：181－182.］

［6］LI Ping，HAN Jungang，LI Zidi.The hardware design and implementation of area filling scan－line algorithm ［J］.Microcomputer Information，2011，27 （6）：124－125 （in Chinese）.［李平，韩俊刚，李自迪.区域填充扫描线算法的硬件设计与实现 ［J］.微计算机信息，2011，27 （6）：124－125.］

［7］Ye Guodong，Lin Gui，Zhu Changqing.A designed edge marking fill algorithm for elongated polygon ［C］／／Database Technology and Applications，2009：22－24.

［8］HUA Chun，XIAO Tiejun.Moving object detection algorithm with Gauss modeling based on FPGA ［J］.Computer Engineering and Design，2011，32 （9）：3000－3003 （in Chinese）.［华纯，肖铁军.基于FPGA的高斯建模运动目标检测算法［J］.计算机工程与设计，2011，32 （9）：3000－3003.］

［9］JIA Yunning，ZHAO Feng.Implementation of graphics accelerator of line raster based on Bresenham algorithm ［J］.Information Technology，2008，32 （9）：229－232 （in Chinese）.［贾运宁，赵峰.Bresenham直线光栅化算法的硬件实现方法研究 ［J］.信息技术，2008，32 （9）：229－232.］

［10］LIU Jing，LI Jun，SUN Han.A modified Bresenham algorithm for line generation ［J］.Computer Applications and Software，2008，25 （10）：247－249 （in Chinese）.［刘晶，李俊，孙涵.改进的Bresenham直线生成算法 ［J］.计算机应用与软件，2008，25 （10）：247－249.］

［11］Niu Lianqiang，Feng Haiwen.A line segments approximation algorithm of grating lines ［C］／／IEEE Computer Society，2009：34－37.