vrc变换算法的硬件实现分析

《vrc变换算法的硬件实现分析》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第一章绪论所使用的软件包括有：MAX+PLUSII9．5、FPGAExpress3．1、ActiveHDL3．1以及XilinxFoundationl．2。接下来，首先给出现有的矢量光栅变换基本算法，这些算法是实现硬件化的基础，以后的各种实现方法都是在此基础上展开的。4VRC变换算法的硬件实现研究第二章矢量光栅变换基本算法本章简要介绍各类常见的矢量光栅变换(VRC)算法，包括三角形、宽直线和二次曲线生成算法，并对各类算法的性能进行简要的分析，最后，讨论针对这些算法的加速方法的研究情况。§2．1三角形生成算法三角形是最简单的多边形，对三角形的处理可

2、以按照多边形填充的方法进行。现有的方法有扫描线相关算法，边填充算法以及种子填充算法等。这里仅介绍扫描线相关算法，其它算法可以参见文献[1，2，3]。一般三角形的填充过程，对于一条扫描线，可以分为四个步骤：1．求交：计算扫描线与三角形的交点，一般为两个；2．排序：把所有交点按X方向进行排序；3．交点配对：确定三角形内部区间；4．三角形生成：输出区间内的点。扫描线相关算法主要利用了扫描线和三角形边的相关性：第i条扫描线与多边形的边相交，则第i+l条扫描线也很可能与这条边相交，如图2．1所示。为此算法采用了两个较为复杂的数据结构实现边相关性，即活性边表

3、(AET)和边表(ET)。其中活性边表是保存当前扫描线与各边交点的链表，边表是保存多边形各边最低点所处扫描线位置的链表。算法根据活性边表来判断填充多边形，并依据活性边表和边表信息更新、排序。详细情况请参见文献[1，2】。图2．1扫描线相关三角形填充由于扫描线相关算法是针对一般多边形提出的，所以当应用于三角形时，活性边表和边表就显得复杂了，其中排序更新不适合硬件实现，并且采用浮点运算使得效率不高。因此针对三角形有必要提出新的填充方法，以适应硬件化的要求。第二章矢量光栅变换基本算法§2．2宽直线生成算法我们所熟悉的经典直线扫描转换算法都是单象素直线的

4、生成。这些算法已经很成熟，如数值微分法(DDA)、Bresenham算法、中点画线法等[1，2】。然而实际应用中直线的绘制都是有一定宽度的，所以对宽直线生成算法的研究更具有实际价值。这里指的宽度是宽直线两平行边的垂直距离。§2．2．1宽直线线宽的处理宽直线线宽的处理一般采用所谓的“刷子”原理，也就是顺着扫描所生成的单象素线条轨迹，移动一把具有一定宽度的“刷子”来获得。“刷子”的形状可以是线段或正方形。根据刷子形状的不同，可分为线刷子、方刷子、圆刷子等

5、5】。线刷子算法，也称为复制象素法，是将宽线的中心线象素沿着垂直于主轴的方向复制，复制的个数等于

6、线宽。直线斜率在[_1，1]之间时，刷子置成垂直方向，刷子的中点对准直线一端点，然后让刷子中心往直线的另一端移动，完成一次刷的动作。当斜率不在【．1，1]之间时，只需把刷子置成水平方向。算法简单、效率高是线刷子的优点。但是，线的始末端总是水平或垂直的。因此，当线宽较大时，宽线两端就很不自然了，尤其当两条宽线相交时，汇合处将有缺口出现。而且宽直线不是旋转不变的，也就是说直线的绘制线宽会随着斜率的变化而改变。水平线和垂直线最粗，与指定线宽相等，而对角线的宽度仅为指定线宽的1／42(约o．7倍)。最后，因为将刷子起始点定位在宽线中心会引起在采用线刷子绘

7、制线宽为偶数个象素时，线条要么多一个象素，要么少一个象素。文献[5】中的图2．4和图2．5给出了利用线刷子绘制宽直线的例子。方刷子和圆刷子分别采用正方形和园形完成刷子动作的。方刷子同样存在着线头粗糙，线宽随斜率变化的缺点，而且方刷子的效率比线刷子低。圆刷子的优点是效果非常突出，线宽不随斜率变化，线接头不用特殊处理，适合曲线的绘制，但是实现的复杂度要比线刷子和方刷子大得多，对硬件实现不太适合。当然，除了刷子方法外也可以采用区域填充的算法处理宽线。这时将宽直线看成为四边形，采用多边形填充算法进行处理。这种方法可以得到效果比较好的宽线，同样该方法比刷子

8、算法麻烦，而且要有复杂的数据结构(边表、活性边表)支持以及复杂的操作，例如一般情况下需进行两次添加边和删除边的操作，判断当前边是否处理完是必须的，会增加时间开销。6VRC变换算法的硬件实现研究§2．2．2宽线线头的处理“3除了线宽和线长的定义外，宽直线还包括直线终端(线头)和直线接头两个属性。一般线头分为四种，平头端、方头端、三角端和圆头端，如图2．2所示。[]口口面平头端方头端三角端圆头端图2．2四种直线终端当两条直线相交时，如果不进行接头处理，那么在相交处会产生不良效果，只有圆形线头能很光滑，其它的终端则会有空隙或毛刺。因此在要求高的场合时就

9、必须进行额外的线间接头处理，图2．3给出了四种类型的接头。丝丝丝丝斜削接头§2．2．3线刷子的改进斜切接头三角接头圆形接头图2．3四种类