多边形填充硬件算法的研究与实现

刘 洋,李庆诚,白振轩

(1.天津师范大学计算机与信息工程学院,天津 300387;2.南开大学信息技术科学学院,天津 300071)

多边形填充硬件算法的研究与实现

刘 洋1,2,李庆诚2,白振轩2

(1.天津师范大学计算机与信息工程学院,天津 300387;2.南开大学信息技术科学学院,天津 300071)

提出一种多边形填充的硬件算法,并通过在Xilinx公司生产的Vertex2 Pro实验板上进行验证,证明该算法的可行性及其良好高效性.

多边形填充算法;硬件加速算法;协处理IP核;Verilog语言;嵌入式开发套件(EDK)

多边形的填充是计算机图形学中最基本的问题之一,填充的任务是要找出所有位于多边形内部的像素,并赋以适当的像素值.以往,实现此类算法均需利用高级语言完成,硬件采用通用处理器,利用软件方法来实现.但在嵌入式设备中,由于考虑到功耗等问题,一般不可能使用高性能的通用处理器.如在嵌入式手持阅读器中,处理器的主频只有200 M Hz,但在版面显示之前,含有大量面向密集的计算[1],如在一般图形解析与矢量字体解析中的多边形填充问题,当通过软件完成这些任务时,速度会很慢,从而对用户快速浏览版面造成影响.因此,设计特别的硬件来弥补通用处理器的不足是一个非常自然且有效的办法[2].本研究在探讨各种多边形填充算法的基础上,提出一种基于硬件实现的多边形填充算法,即利用硬件加速的方法提高多边性的填充效率,并在Xilinx公司的Vertex2 Pro实验板上进行测试.

1 多边形填充算法

多边形填充算法主要有两种[3]:一种是通过横越区域的扫描线的覆盖间隔来填充;另一种是从给定的位置开始涂描,直至指定的边界条件为止.扫描线方法在一般图形软件包中,主要用来填充多边形、圆、椭圆和其他简单曲线.从内部点开始的填充方法用于边界形状复杂的多边形和交互式绘图系统.在矢量图形的填充问题上,扫描线填充算法是一种比较可行的算法,因此,许多研究在该算法上做了大量改进,以提高填充效率.例如,张玉芳等人提出一种混合填充算法,该算法采用链表和数组结合的数据结构,形成连续的填充轨迹,有效地提高了时间效率[4].2000年,甘泉提出通用扫描线多边形填充算法,该算法可以有效解决任意间距、任意倾角的扫描线对多边形的填充问题[5].2002年,阳波等人进一步结合代数曲线积分思想与活性边表技术,提出一种新的任意多边形代数积分算法[6].以上改进算法均从不同的角度改进了传统的扫描线算法,但大多是在软件平台上完成的.考虑到嵌入式产品自身的功耗问题,单纯依靠提高处理器主频的软件实现加速并非切实可行,而目前,国外的厂商,如 HP,CALCOMP,VERSTATEC等公司均在矢量图形光栅化上取得了良好效果,但这些技术都严格保密.西安电子科技大学李春霞硕士将图形学中一些基本算法进行硬件实现,并对其进行了性能分析[7].本研究在此基础上,针对多边形填充问题,提出并实现了其硬件算法.

2 核心算法的描述

本研究的多边形填充算法主要分2步:

第1步:初始化工作,包括3小步:

(1)求多边形坐标的最小值和最大值,分别记作minx,maxx;

(2)记录每条边的信息,存在数组line_ info中,其中每一个元素的结构如表1所示;

表1 边的数据结构Table1 Datastructureofedge

(3)记录顶点(较小x值)的信息,存在数组point info中,其中每一个元素的结构如表2所示.

表2 顶点的数据结构Table2 Datastructureofvertex

第2步:扫描所有列,得到交点.

∀x∈[minx,maxx),求x与各个边的交点y,将当前列(x列)的交点信息存在数组cur_ et中将上一列(x-1列)的交点信息存在数组prev _et中其中cur_ et与prev_ et中的元素结构相同,如表3所示.

表3 交点的数据结构Table3 Datastructureofintersection

求交点y的具体步骤分为以下7小步:

(1)x=minx,进入(2);

(2)如果x＜maxx,执行(3),否则结束;

(3)如果x＞minx,执行(4),否则执行(5);

(4)对于数组prev_ et中的所有交点,如果其值不大于它本身所在直线的最大x值减1,则利用Bresenham算法求出当前的交点值,并将结果按交点的大小顺序插入数组cur_ et中;否则考察数组中下一个交点;

(5)扫描顶点交点信息(即数组point_ info),查找是否存在坐标x值与当前列相同的点,并将其按y值大小顺序插入到数组cur_ et中;

(6)输出当前x列值,以及数组cur_ et所有信息(即当前列与所有边的交点坐标);

(7)将数组cur_ et中的信息写回prev_ et中,以备下次使用,置x=x+1,返回(2).

下面,以多边形 A(2,1),B(7,1),C(9,5),D(6,8),E(5,4),F(2,9)为例:

第1步:初始化工作,分为3小步:

(1)minx=2,maxx=9;

(2)记录每条边的信息,存在数组line info中,如表4所示;

表4 本例中边表情况Table4 Onecaseabouttheedgetable

(3)记录顶点(较小x值)的信息,存在数组point_ info中,如表5所示;

表5 本例中顶点表情况Table5 Onecaseaboutthevertextable

第2步:扫描所有列,得到交点.

(1)x=2,扫描数组point_ info,将A点和 F点按大小顺序插入数组cur_ et,输出交点(2,1)和(2,9),并将数组cur_ et的内容放入prev_ et中;

(2)x=3,读取数组prev_ et,利用Bresenham算法求出当前的交点值,按大小顺序插入数组cur_ et中,然后,扫描数组point_ info,但没有相应点,无需插入,输出交点(3,1)和(3,8),将数组cur_ et的内容放入prev_ et中;

(3)x=4,5,6,7和8的情况与(2)相同,不再赘述;

(4)x=9,程序结束.

3 算法的实现

多边形填充算法的实现:在Xilinx公司的Vertex2 Pro实验板[8]上完成.Vertex2 Pro系列 FPGA是Xilinx公司推出的高端 FPGA产品,该开发板引入M icroBlaze内核并提供相应的集成开发环境EDK.其中,M icroBlaze是基于Xilinx公司FPGA的微处理器软 IP核,该 IP核采用 RISC架构和哈佛结构的32位指令和数据总线,内部有32个32位宽度的通用寄存器;在150 M Hz的时钟频率下,最高可以达到125 DM IPS的处理性能,其逻辑结构如图1所示(图中省略了指令侧的同类接口).

图1 M icroBlaze IP核逻辑结构Fig.1 M icroBlaze IP core structure

使用Xilinx公司提供的EDK,可以在参数化的图形界面下方便地完成嵌入式软处理器系统的设计.该套件具备2个突出的优点:一是设计灵活;二是可以整合用户自定义IP核,使算法在硬件中并行执行,而不是在软件中串行执行,从而极大地加速了任务的执行速度,即所谓的硬件加速.本研究首先利用Xilinx公司的 EDK,很方便地构架出实验结构,如图2所示.

图2 多边形填充异构单M icroBlaze核处理器设计模块图Fig.2 Polygon f illing design block diagram based on hybrid M icroBlaze processor

图中,M icroBlaze核作为主处理器,主要负责数据的输入输出,而实现算法的主要部分放在自行设计的IP核中,作为主处理器的协处理核,实现多边形填充的硬件加速功能.其设计遵循如下基本需求:

(1)指令集适用于多边形填充问题,能够通过使用此指令集的软件编程控制硬件,适应具体的应用场景;

(2)能够针对具体密集计算真正起到硬件加速作用;

(3)能够快速地存取大量数据,主核与协核之间的通信不会成为整个系统的瓶颈.

IP核的设计与实现是在 Xilinx公司提供的ISE开发工具上完成的,所使用的算法如本研究第2部分所述,语言是Verilog语言,对于该模块的接口定义如下:

编写程序后,在modelsim下进行逻辑仿真与后仿真成功,其仿真结果如图3.

图3 在modelsim下后仿真图Fig.3 The ModelSim Simulation Result

协核由于功能单一,一般不具备完整的人机交互等功能,主要靠主核控制,而主核与协核之间需要设计特别的通信或数据共享机制,该机制应保证数据的正确性、可控制性和传输效率等.

在EDK中,主核M icroBlaze与用户自定义的IP核的连接是通过快速单向链路总线(Fast Simp lex Link,简称 FSL)完成的.FSL总线是M icroBlaze所特有的总线,可以实现用户IP核与软核处理器的高速连接,为设计者提供了一条解决这类问题的途径.最后,实验结果通过实验板上的串口输出到计算机屏幕上,以验证结果的正确性.

4 实验结果

为了测试本算法的性能,将该算法与软件实现的多边形填充算法在时间上作了多组比较,其平均时间如图4所示.

图4 实验结果对照图Fig.4 The comparison of experimental result

图中,本研究提出的硬件算法所用的时钟频率为100 M Hz,平均所需填充时间为 163μs.而用软件实现算法时,使用传统的扫描线方法,测试环境分别有三种:第一种是在 PC环境下,处理器是AMD Athlontm64 X2 Dual Core Processor 3 600+2.00 GHz,内存大小为1 GB;第二种是在Xilinx公司的Vertex2 Pro实验板上搭建的PowerPC 405处理器系统平台,其主频为100 M Hz,内存为256 MB的DDR SDRAM(最大实际工作频率为133 M HZ);第三种也是在PowerPC 405处理器系统上,其主频为300 M Hz,其他与第二种相同.

由图4可以看出,第一种软件实现是在高主频CPU下完成的,其平均所需填充时间为 128μs,在PC环境下,多边形填充算法程序与其他程序共享CPU与内存资源,故真实的程序运行时间应好于此值;第二、三种软件实现是在嵌入式系统通常使用的低主频处理器上实现的,其平均时间分别为2079μs和1 066μs,PowerPC主频为300 M Hz的情况下,与100 M Hz运算速度相比没有提高3倍,主要是因为连接 PowerPC与内存之间的总线频率仅为100 M Hz,成为整个系统的瓶颈.通过图4所反映的数据可以看到,本研究的硬件算法在主频为100 M Hz的情况下,填充速度已基本达到目前主流通用处理器对该问题的处理速度,并远远超过了一般嵌入式处理器的处理速度,从而验证了该硬件算法的高效性.

5 结论

上述实验表明,本研究设计的算法能够对一般多边形进行有效填充,并具有以下特点:(1)由于使用Bresenham算法求出当前的交点值,故无需乘除运算,便于硬件实现;(2)算法中有大量可同时进行的步骤,稍加改动,即可实现并行化.同时,该算法也有片上资源使用率较高等需要改进的环节.总之,本研究的主要目标在于满足嵌入式手持阅读器的版面加速需求,但目前还处于实验阶段,将其真正应用于实践是本研究下一阶段需要完成的任务.

[1] Johnston W E.High-speed,wide area,data intensive computing:a ten year retrospective[C].//IEEE Computer Society.Proceedings of theSeventh International Symposium on High Perfo rmance Distributed Computing.Chicago IL:University of Chicago Press,1998:280-291.

[2] 戴鸿君.基于异构多核体系与组件化软件的嵌入式系统研究[D].杭州:浙江大学,2007.

[3] Donald H,Baker M P.计算机图形学[M].北京:电子工业出版社,1998.

[4] 张玉芳,刘君,彭燕.一种改进的扫描线多边形填充算法[J].计算机科学,2005.

[5] 甘泉.通用扫描线多边形填充算法[J].计算机工程与应用,2000.

[6] 阳波,王卫星,魏许青.基于曲线积分的任意多边形填充算法[J].计算机工程与应用,2002.

[7] 李春霞.矢量光栅变换(VCR)的研究与硬件实现[D].西安电子科技大学,2005.

[8] Xilinx Inc..Xilinx XUP Virtex-II Pro Development System[EB/OL].(2009-11-3)[2009-11-3].http://www.xilinx.com/univ/xupv2p.

Research and im plementation of polygon filling algorithm based on hardware

L IU Yang1,2,L IQingcheng2,BA I Zhenxuan2

(1.College of Computer and Information Engineering,Tianjin Normal University,Tianjin 300387,China;2.College of Information Technical Science,Nankai University,Tianjin 300071,China)

A kind of polygon filling algo rithm based on hardware is p resented,and its feasibility and good perfo rmance are confirmed by the imp lementation on Vertex2 Pro board of Xilinx Co rpo ration.

polygon filling algo rithm;hardware advanced algorithm;co-p rocessor IP co re;Verilog Language;embedded design kit(EDK)

TP368.2

A

1671-1114(2010)01-0019-04

2009-09-04

天津市科技支撑计划重点项目(08ZCKFGX01400)

刘 洋(1977—),男,讲师,博士研究生,主要从事片上多核系统,软硬件协同设计方面的研究.E-mail:snake8young@yahoo.com.cn

(责任编校 纪翠荣)