边标志算法的改进与硬件实现-论文.pdf

《边标志算法的改进与硬件实现-论文.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、2014年8月计算机工程与设计Aug．2014第35卷第8期COMPUTERENGINEERINGANDDESIGNVo1．35No．8边标志算法的改进与硬件实现王利祥，肖铁军(江苏大学计算机科学与通信工程学院，江苏镇江212013)摘要：针对传统的边标志算法在遇到极值点以及狭长条等情况时会出现异常填充的现象，提出一种新的改进方法。充分利用多边形边界光栅化时极值点和狭长条上的点会被重复访问的特点，设置一个计量型标记变量flag，访问到一个像素点时将该像素点的flag值加1，与其它边界点进行区别，以解

2、决上述问题。在Altera公司的cycloneII系列FPGA开发板上进行实现与验证。验证结果表明，该方法填充效果良好，且在系统时钟为33MHz时填充一个像素点仅需0．24ms，在嵌入式图形加速器中具有较高的应用价值。关键词：计算机图形学；边标志算法；多边形填充；现场可编程门阵列；嵌入式图形加速器中图法分类号：TP391．41文献标识号：A文章编号：1000—7024(2014)08—2817—05Improvededgemarkingalgorithmanditshardwareimplement

3、ationWANGLi—xiang，XIAOTie-un(Schoo1ofComputerScienceandTelecommunicationEngineering，JiangsuUniversity，ZheNiang212013，China)Abstract：Animprovedmethodfortraditionaledgemarkingalgorithmwasproposed，asthetraditionalonefailstOfillanelonga—tedpolygonandsingul

4、arpointsinthepolygonproperly．Thecharacteristicsthatapointontheboundaryofthepolygonisrepea-tedlyaccessedwhenmeetingsingularpointsandelongatedpointsweretakenfulladvantageof，andthenameasurementvariableflagwassetupwhichwasusedtOmarktheboundarypoint，theflag

5、ofthepresentpointwasaddedby1whenthepointwas3c—cessed．Thismethoddistinguisheslocalpointsandelongatedpointsfromordinarypointsconvenientlyandsimply，SOitsolvestheaboveproblem．Finally，itwasimplementedandverifiedbyusingAltera’ScycloneIIdevelopmentboard．There

6、sultsshowthatthismethodfillsnotonlythepolygonperfectly，butalsoapointwith0．24mswhenthesystemclockwas33MHz，SOithashighpracticalvalueinembeddedgraphicsaccelerator．Keywords：computergraphics；edgemarkingalgorithm；polygon-filling；FPGA；embeddedgraphicsaccelera

7、tor刻理解目前边标志算法的基础上，提出了一种新的改进算0引言法。该算法充分利用了光栅化多边形边界时的特点，使用传统的嵌入式图形显示的处理方式主要依赖于微处理计数型的边标记变量flag，采用对访问的边界像素点的标器，然而当面对高质量和高效率显示需求时，单纯使用软记进行加1的操作，方便简捷地将极值点和狭长条上的点件来实现多边形填充_1I2]这一复杂的过程，显然成为了图形与普通边界点区别开来，从而解决了极值点和狭长条填充显示质量的一个瓶颈，因此使用硬件来满足高要求显示不时产生异常现象的问题。该算法既保持

8、了传统边标志算法失为一种可行的方案。不需要边表结构以及求交点运算的优点，又解决了特殊点传统的边标志算法_3]在遇到极值点l4]及狭长条时会出填充时产生异常现象的问题，最终使用现场可编程门阵列现异常填充的现象，因此许多文献对其进行了改进，如王(FPGA)_8]进行实现并加以验证。秀华等l5提出了一种改进的边标志算法，该算法成功解决1传统边标志算法分析及缺陷了极值点问题，但是引入了扫描线填充算法_6]中使用的边表结构，使得算法的数据结构变得复杂；叶国栋等l_7]提出1．1