（计算机应用技术专业论文）矢量光栅变换的研究与硬件实现.pdf

摘要 本文主要讨论了矢量光栅变换( v e c t o rt or a s t e rc o n v e r s i o n ) 技术硬件化过程 中的一些问题，包括二次曲线生成算法和多边形生成及填充算法的硬件实现。首 先讨论了现有的基本图形生成算法，包括圆形、椭圆的生成算法和梯形填充算法， 同时介绍了加速算法的研究现状，接着具体讨论了这些图形的硬件化过程。给出 了各算法的状态机流程图，到状态转换图，再到状态机图。v h d l 程序接口的定 义和实现框架，并且从理论角度给出了二次曲线加速算法的证明；在以上基础上 介绍了高级语言到硬件描述语言的映射，提出了算法到状态机流程图抽象的规律： 还对v r c 芯片与主机的输入输出接口进行了研究；最后采用e d a 工具对所有 v h d l 程序进行仿真、综合。 关键词：矢量光栅变换硬件描述语言加速算法 a b s t r a c t i nt h i sp a p e r , w em a i n l yd i s c u s ss o m ei s s u e so ft h ei m p l e m e n t a t i o no fv r c ( v e c t o rr a s t e rc o n v e r s i o n ) i nh a r d w a r e , i n c l u d i n gt h ei m p l e m e n t a t i o no fc o n i ca n d p o l y g o n f i r s t , t h eb a s i cr a s t e rg r a p h i c sa l g o r i t h m sf o rd r a w i n g2 dp r i m i t i v e sa r c i n t r o d u c e d , i n c l u d i n ga d v a n c e da l g o r i t h m so fc i r c l ea n de l l i p s e i na d d i t i o nt h ec u r r e n ts i t u a t i o no ft h ea d v a n c e da l g o r i t h m si sa l s oi n v o l v e d s e c o n d ，t h ei m p l e m e n t a t i o no fb a s i cg r a p h i c si nh a r d w a r ei sd i s c u s s e di nd e t a i l , t h es t a t em a c h i n ef l o w c h a r t s ，s t a t ec o n v e r s i o nc h a r t sa n ds t a t em a c h i n ec h a r t sa r cd r a w ni nt h ep a p e r , t h ei m p l e m e n t i n gf j a m ea n dt h ei n t e r f a c e so fv h d la r cd c 6 n e da n dt h ea c c e l e r a t e d a l g o r i t h mo fc o n i ci sp r o v e d o nt h eb a s i co fa b o v e ，t h em a p p i n go fh i g hl e v e lp r o g r a m m i n gl a n g u a g et oh a r d w a r ed e s c r i p t i o nl a n g u a g ei sd e s c r i b e d , s o m ep r i n c i p l e so ft h ec o n v e r s i o no fa l g o r i t h mt os t a t em a c h i n ef l o wc h a na r ca l s op r o p o s e 也f o u t h , t h ei n - o n ti n t e r f a c eo fc h i pv r ca n dh o s tc o m p u t e ra r cr e s e a r c h e d f i n a l l y , t h ev h d lp r o g r a m sa r es i m u l a t e 正s y n t h e s i z e da n di m p l e m e n t e dw i t ht h ee d a t 0 0 1 k e y w e r d ：v r c h a r d w a r ed e s c r i p t i o nl a 唧a g ea d v a n c e da l g o r i t h m 创新性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果：也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名： 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。 日期： 日期： 扣口5 ，礼、描 x 却6 ib 第一章绪论 第一章绪论 1 1 矢量光栅交换的研究背景 工作站等一些计算机绘图系统输出的图形多是矢量格式，这些图形要在点阵 输出设备上输出，就需要将矢量图形转换成光栅图形，这部分工作是通过一个叫 做“矢量光栅转换器( v e c t o r r a s t e rc o n v e r t e r , 简称v r c ) ”的过程来完成，它已经 成为所有点阵输出设备输出图形时不可或缺的过程。 以往，这些转换过程基本上由高级语言算法来实现，硬件采用通用的处理器。 如今，随着人们对计算机速度的要求越来越高，在专用领域采用通用处理器必然 会影响速度，因此可以将一些基本固定不变的算法采用硬件芯片来实现，这就是 软件的硬化。近年来日益成熟的可编程芯片技术( 如f p g 蝴i d ) 以及硬件描述 语言的广泛应用已经使这种软件硬化过程变的越来越方便和简单7 。例如在数字 信号处理、图形图像处理、神经网络、专家系统以及视频压缩等方面已经有了很 大的成就。 矢量光栅变换技术主要应用于计算机的显示输出设备，如显示器、打印机、 绘图机等，其特点是核心算法简单固定，数据量大和要求的处理速度高。因此非 常适合将基本算法固化到专用的芯片上，这样可以在很大程度上提高处理速度， 缓解由速度产生的瓶颈问题，更重要的是当进行批量生产后可以大大地降低成本。 可以说，具有了高速地v r c 处理器将成为产品在市场上具有竞争力的一个重要标 志。 借助强大的e d a 工具和先进的半导体工艺可以很容易地将a p l 血悝p g a 转换 为a s i c ，进而可以成批地投入生产，达到了缩短设计周期、降低开发费用、减小 投资风险等目的。同时可以获得宝贵的m 库，使得以后的数字电路设计水平极大 地提高。所以矢量光栅变换的f p g a j a s i c 实现是实现高速v r c 算法而同时又具 有快速的产品原型化及相对小的投资的优良选择。 1 2 论文研究的目的和意义 矢量光栅变换是指把向量描述的图形转换成点阵位图的过程，它是任何点阵 式输出设备输出图形所不可缺少的重要环节。i 。 点阵式图形输出设备主要包括有静电式、热敏式、喷墨式、热转印、激光式 和电子照相式等几种方式，其中以静电式绘图速度最快。为了提高出图速度和质 量要求v r c 的处理速度尽可能快且精确，这是影响图形输出设备性能的关键因素 之一，设法提高其速度以便与图形的输出速度相匹配就成为研究的核心。 2矢量光栅变换的研究与硬件实现 目前国外的厂商，如h p ，c a l c o m p ，v e r s t a t e c 等，v r c 的实现上大多 采用高速微处理器或a s l c 芯片，取得了良好的效果，达到了较高的处理速度。但 是这些技术是严格保密，有的还申请了专利，这就形成了一定的技术垄断，限制 了国内厂商的发展。在国内，我校外设所已在“八五”军事预研项目。高精度彩 色静电绘图机”中，开始了对v r c 的研究，经过不懈的努力，已经形成了多年的 积累并取得了相应的成果。本论文就是在此基础上，进一步将图形学中一些基本 算法转换为v h d l 语言，并对其进行优化争取达到硬件实现的目的。另外还对其 进行了性能分析，而且在算法级上对加速方法进行了研究。 除了上述的实用价值以外，论文还通过对v r c 算法的研究，总结出了一般高 级语言算法抽象与硬件描述语言抽象的映射关系，试图以此对一般算法硬件实现 有所帮助，使得设计更加规范化，提高设计效率。 矢量光栅变换技术具有通用性，研究成果可直接用于高速点阵式输出设备上， 如高速静电绘图机与喷墨绘图、用于绘制高精度的军事电子地图，以及为满足战 场上临时快速输出军事态势图与地形图的需要，而在民用领域，所开发的产品亦 可用于电子设计自动化，机械建筑图纸，超大规模集成电路版图的绘制。总之， v r c 技术具有广阔的市场前景，将在军用和民用绘图打印领域发挥巨大作用。 1 3 论文的主要工作 本论文是在西安电子科技大学外设所申请的“九五”军事预研项目“高速矢 量光栅变换技术研究”课题的基础上展开的。 至今为止，论文完成的工作包括； 1 图形的矢量光栅变换的v h d l 实现。 a ：椭圆的生成转换 完成了二次曲线中椭圆的v h d l 语言的描述。对c 语言中的中点画椭圆的基 本算法进行了改进，使之适合于硬件描述语言( v h d l ) 的实现，并对改进算法进行 了优化。在具体实现上综合了椭圆中点算法和椭圆双步增量算法，即适合于v h d l 编程的实现又避免了椭圆双步增量算法复杂的计算，其效果与椭圆双步增量算法 基本一样。可以达到每一个时钟周期输出一个转换坐标的速度。 b ：梯形的生成转换及其填充 完成了多边形中梯形的v h d l 语言的描述。利用了直线的v h d l 转换算法和 多边形填充的技术，使梯形的转换快速方便的完成。对已有的梯形转换算法进行 了改进，充分利用了梯形的特性，使改进后的算法达到了提高效率和易于理解的 目的。 2 高级语言算法到数字系统抽象( v 】眦儿语言) 转换的讨论。 第一章绪论 3 3 系统输入输出接口的设计 针对椭圆和梯形的v h d l 转换算法，对它们的具体输入输出接口电路进行了 讨论，使设计出来的v r c 芯片能和计算机主机系统在数据输入输出上正确的配合。 最终达到v r c 芯片输出的转换坐标能够被计算机主机c p u 正确及时的读取和存 储。 4 采用相应的e d a 软件对上述各个v h d l 程序进行综合，仿真。 使用的相关软件有：m a x p l u s q u a r t u sl i 等。 第二章二次曲线光栅化算法研究及硬件实现5 第二章二次曲线光栅化算法研究及硬件实现 在矢量光栅变换研究中有很多曲线的生成。二次曲线是曲线当中最基本的也 是最简单的，这里仅研究圆和椭圆的矢量光栅变换，包括基本算法，加速算法和 算法硬件化的过程。 本章讨论二次曲线生成算法，包括圆和椭圆的矢量光栅变换算法。研究了现 有的椭圆双步增量算法，提出了一种新的椭圆算法，这种算法类似椭圆双步增量 算法，但思想简单，程序易于理解。由于圆形的生成算法较为简单，程序中没有 复杂的浮点数运算，所以本节的重点将是椭圆的双步增量加速算法的证明和椭圆 新算法的分析和实现。 2 1 1 圆的生成算法 2 1 二次曲线生成算法 圆形是对称性最好的图形，不需要对整个圆形进行扫描转换，只要能生成8 分圆，那么圆的其它部分可通过一系列的简单反射变换得到。假设己知一个以原 点为圆心的圆上的一点( 】【y ) ，根据对称性可得到另外7 个8 分圆上的对应点( y ) ， ( y ，一x ) ，( - x ，- y ) ，( - y ，x ) ，( - x ，y ) 因此，只需讨论8 分圆的扫描转换。一般地采用中点 画圆法和b r e s e n h a m 画圆法来生成8 分圆。下面讨论中点画圆法，考虑中心在原 点，半径为r 的圆的第二个8 分圆，如何从( 0 ，r ) 到( i t 2 ，r 2 ) 顺时针 地最佳逼近该圆弧的象素序列。假设x 坐标为x p 的象素中与该圆弧最近者己确定， 为p ( x p , y p ) ，那么，下一个象素只能是正右方的p 1 ( x r 1 ，y p ) 或右下方的p 2 ( x r l - 1 ，y r 一1 ) 两者之一如图2 1 所示。 p 图2 1 圆生成示意 构造函数： f ( x ，y ) - x 2 + y 2 一r 2式( 2 1 ) 6矢量光栅变换的研究与硬件实现 对于圆上的点，f ( x ，y ) = 0 ；对于圆外的点，f ( x ，y ) 0 ；而对舌圆内的点，则 有f ( x ，y ) o 。设m 是p l 和p 2 的中点，那么m = ( x e + l ，y r - - o 5 ) 。所以，当f ( m ) 0 时， 这表明p 2 距离圆弧更近，取p 2 作为下一个象素。当f ( n 0 = o 时，在p 1 与p 2 之间 任取一个即可，这里约定取p 2 作为下一个象素。至此可按照直线的中点线算法， 构造判别式： d = f ( m ) = f ( x r v l ，y r - - 0 5 ) = ( x p + 1 ) 2 + ( y r - - 0 5 ) 2 - 式( 2 2 ) 若d = 0 ，则p 2 是下一个象素，判别式为： d = f ( m ) = f ( x p + 2 ，y v - - i 5 ) = ( x 一2 ) 2 + ( y e - 1 5 ) 2 r 2 式( 2 - 4 ) 所以，沿着右下方向，d 的增量为2 ( x ry r ) + 5 。 2 1 2 椭圆的生成算法 我们知道，假如椭圆的方程为：f ( x ，y ) ：b 2 】【2 + a 2y 2 一a 2b 2 = 0 由微积分知识，该 椭圆上一点( x ，y ) 处的法向量为：n ( x ，y ) = ( o f a x ) * i + ( o f o y ) * j = 2 b 2 x i + 2 a 2 y j 其中，i 和j 分别为沿x 轴和y 轴方向的单位向量。 图2 2图2 3 法向量 由上图知，在上部分，法向量的y 分量更大，而在下部分，法向量的x 分量 更大。因此，若在当前中点，法向量( 2 b 2 ( x p + t ) ，2 a 2 ( y w 0 5 ) ) 的y 分量比x 分量大，即b 2a 印十1 ) a 2 0 p - 0 5 ) 而在下一个中点，不等号改变方向，则说明椭 圆弧从上部分转入下部分。 与中点画圆算法类似，当我们确定一个象素之后，接着在两个候选象素的中 第二章二次曲线光栅化算法研究及硬件实现 7 点计算下一个判别式的值。并根据判别式符号确定两个候选象素那个离椭圆更近。 下面讨论算法的具体步骤。先看椭圆弧的上部分。假设横坐标为x p 的象素中与椭 圆弧最接近的是( x p ，v p ) ，那么下一对候选象素的中点是( x p + l ，y p - o 5 ) 。因此判 别式为d l = f ( x p + l ，y p - 0 5 ) = b z ( x p + 1 ) 2 i - a 2 ( y p - o 5 y a 2b 2 它的符号决定下一个象素 是取正右方的那个，还是右下方的那个，如上图所示。若d l = o ，中点在椭圆之外，这时应该取右下方象素，并且更新判别式为d 1 = f ( x p + 2 ，y p - i 5 ) = b z ( x p + 2 y + a 2 ( y p q 5 ) 2 一a 2b 2 = d l + b 2 ( 2 x p + 3 ) - l - a z ( - 2 y p + 2 ) 。所以， 沿右下方向，判别式d 的增量为b 2 ( 2 x p + 3 ) - i - a 2 ( - 2 y p + 2 ) 。接下来，我们来看判别 式d 1 的初始条件。由于弧起点为( o ，b ) ，因此，第一个中点是( 1 ，b - 0 5 ) 对应的 判别式是d l o = f ( 1 , b - o 5 ) = b 2 + a 2 ( b - 0 卵一a 2b 2 = b 2 + a 2 ( b + o 2 5 ) 在扫描转换椭圆弧的上部分时，在每步迭代中，必须通过计算和比较法向量 的两个分量来确定何时从上部分转入下部分，这是由于在下部分算法确有不同。 在下部分，应改为从正下方和右下方两个象素中选择下一象素。在刚转入下一部 分之时，必须对下部分的中点判别式d 2 进行初始化。具体的说如果在上部分所选 择的最后一象素是( x p ，y p ) 则下部分的中点判别式d 2 在( x p + o 5 ，y p - 1 ) 处计算。 d 2 在正下方向与右下方向的增量计算与上部分类似。下部分弧的终止条件是y = 0 。 2 1 3 二次曲线加速算法的分析 一加速算法概述 在计算机图形学中，曲线的扫描转换大多采用增量类型的算法，这些算法在 沿某坐标轴递增一步后，从两个可能象素点中选择一个离曲线最近的象素构成光 栅平面上曲线的离散轨迹。通常这种选择是根据判别式的符号决定，而判别式又 服从递归公式，使得计算仅用整数类型和二进制移位，达到了简单快速的要求， 得到了广泛的使用。 然而，曲线的扫描转换速度还可以进一步地提高。为此不少学者研究了新的 加速算法，比如步距长度片( r u n l e n g t h - s l i c e ) 算法，对称性算法( s y m m e t r ya l g o r i t h m ) ， 双步增量算法( d o u b l e s t e pi n c r e m e n t a lg e n e r a t i o n ) , 以及对称双步增量算法。步距长 度片算法是指在直线斜率较小情况下，主轴的步长可以有规律的增大，加快直线 的生成速度，但是由于不定长度片会产生帧缓存不对齐，使工程应用受限。对称 性算法是根据直线段关于中点对称的特性提出的，从而理论上只需转换整个线段 的一半就可以完成全部转换，提高了生成速度。这两种方法均是针对直线的特征 矢量光栅变换的研究与硬件实现 提出的，对于二次曲线就得采用双步增量算法。双步增量算法依据二次曲线 f ( x ，y ) = 0 在光栅平面的离散特性，在每次步长都是二的情况下，曲线呈现出特定的 模式，从中选择出一种模式完成曲线的扫描转换。由于两倍步长，所以理论上可 以使速度提高一倍。在 2 7 1 中详细讨论了直线和圆的双步增量算法，我们将在此基 础上讨论更一般的二次曲线一椭圆的双步增量算法，仔细地研究了【2 7 1 的证明方法 后，提出了一种提高速度的证明方法。 二平面上的曲线的性质 1 2 x 2 网格上离散曲线的模式 设f ( 支，y ) = 0 为具有连续一阶导数的二次曲线，并将其分为满足以下条件的曲线 段： ( 1 ) 0 d 鲫d 】【1 ( 3 ) - c o d y d x - 1 ( 2 ) k d 妙d x + 一 ( 4 ) - 1 一 d y d x o 群赫群群 模式l 模式2模式3模式4 图2 4 那么对于每一种曲线段，考虑光栅平面上的2 x 2 网格中，曲线仅能为特定的 四种模式之一。具体地讲，当曲线满足条件( 1 ) 时，在2 x 2 网格上仅表现为图 4 1 2 的四种模式。以( 】【o ，y 0 ) 为起点，那么模式1 和模式4 发生时，中间的象素点就 可以无需计算地确定。对于模式2 和模式3 ，如果在具有灰度级设备显示，可以将 中间两个象素点置为灰度级的一半，这样同时起了反走样的效果。但是对于单级 显示就必须回退一步将模式2 和模式3 区分开来。即使时回退一步，双步增量方 法退化为单步增量，转换速度也不会下降太大。 2 模式判别 双步增量算法就是从这四个模式中选择其中之一，每次步进两个单位。首先 可以视模式2 和模式3 为一种模式记为2 ( 3 ) ，可根据显示要求或进行反走样处理或 进一步构造判别式将其区分本文采用新判别式区分模式2 和模式3 。从三种模式 中选择一种是三态逻辑，构造的判别式必须具有三个值，这相当于进行两次逻辑 判断，这样做与单步增量并没有什么区别，所以必须将三态逻辑转化为两态逻辑。 有以下定理： 定理2 1 ：在实数区间【如】上，曲线f ( x ，y ) = 0 满足( 2 1 ) 的条件之一，并且d 2 y m 2 x 不改变符号，那么存在【咖l 使得在he 和 ；，b 内f ( x ，y ) = 0 在光栅平面上 不能同时出现模式l 和模式4 。 根据以上定理可知在找到满足条件的区间 a b 后就可以在予区间内构造二 第二二章二次曲线光栅化算法研究及硬件实现 9 值逻辑的判别式，也就是从模式1 和模式2 ( 3 ) 判别或者从模式2 ( 3 ) 和模式4 判别。 对应一般的f ( x ，y ) - - 0 ，分界点是很难找到。然而当直线斜率在0 到l 之间时，斜 率为1 2 处的分界点就是的位置。 三椭圆双步增量算法 1 椭圆的分段 设椭圆x j ，a 2 + y 铀2 = l ，只需生成第一象限曲线部分，其它部分可以根据对称性 得到。对于中心不在原点的椭圆需将中心平移至原点，扫描转换后再反方向平移 至原来的中心点。由椭圆的性质知在第一象限内曲线的一阶导数单调，在区间 0 ，a 内曲线的切线斜率从0 递减到一一。根据前述将曲线按一阶导数分为( - 1 ，0 ) 和( 一 一，- 1 ) 两个区间。如图4 1 3 所示： 图2 5 椭圆的分段 2 判别式的构造 一 这里仅对第1 i 部分的判别式进行推导，第1 部分的判别式只需将第1 i 部分 判别式中x 与y ，a 与b 互换即可得到。在第1 i 部分曲线满足图2 4 中第3 种情 况，这时四种模式为( 见图2 6 ) ：其中右下角y 0 ) 为起始点，y 轴为主轴，x 向 左递减。 摊口鞲口鞲时鞲 蕞式1纰羹式3模式l 图2 6 第1 i 部分曲线四种模式 设在第i 次循环时曲线如图2 7 所示，点( 酢l ，y i 1 ) 为前一步所确定的点。图中 r 、m 、l - - - 点分别对应着模式1 、模式2 ( 3 ) 和模式4 。 1 0 矢量光栅变换的研究与硬件实现 图2 7 椭圆第i 次循环 设( x ，蝴是曲线上的点，6 = x t - l - x ，那么从图中可知r 、m 、l 的条件分别是6 1 2 、1 2 6 0 ，所以6 1 2 等价于d i + 62 0 这时只需d + 62 0 就可以判断出是模式1 ，但由于6 是变量，不能构造递归 的判别式，所以还得迸一步化简。容易想到如果d i + 62 o 等价于d i 1 4 ，那么当6 ( 0 ，1 2 ) 时，d i 4 - 62 0 与d i o 等价。这就是说 当d i o 时选择r 点为下一次循环的起始点，模式1 出现；否则，模式2 ( 3 ) 或模式 4 ，就必须进行下一步的判断。这时将参考点从r 移到m ，设x = x i - 1 1 ，代入得 d i = d i 2 x 。当d i 0 时，模式2 ( 3 ) 出现，但d i 和d i 存在简单关系所以并 不会加大运算量。第一次模式4 出现说明了定理2 1 中分界点得位置，以后得 判别就只需区分开模式2 ( 3 ) 和模式4 ，不会再有模式1 了。以下给判别式的递推 公式：d i + l d i = x i 2 + ( a 2 b 2 ) y i + 1 2 _ a h x i _ 1 2 + ( a 2 b 2 ) y i 2 - a 2 x i - 1 】= x i 2 x i - 1 2 + ( a 2 b 2 ) y i + 1 2 y i 2 1 4 - x i - i - x i 有y l + t = y i + 2 ，x - l = x j 一x 代入得d j + l d i = ( 2 x i - 1 ) x + “y i + 1 ) ( a 2 b 2 ) - 气 其中x 分别等于0 ，- i ，- 2 对应于r 、m 、l 三个点，因此有 d i “i 2 + 劬2 6 2 ) ( ) ，l + 1 麒m b + 心2 6 2 ) ( ) ，j + 1 ) - 2 x i 模式2 ( 3 ) 式( 2 1 ) q + 劬2 6 2 ) ( ) ，l + 垆钒一2 模式4 由于从( a ，0 ) 点开始转换所以d l - 4 ( a 2 ) a 考虑到只需判别d 。的符号，可 以给d 。乘以b 2 消除浮点数除法，这样得到只含有整数运算的递推公式： d + 如2 饥+ 1 麒如 d i “i d i + 4 a 2 ( ) ，l + 1 ) - 幼2 毛模式2 ( 3 ) 式( 2 1 ) id j + 4 4 2 ( ) ，f + 驴b 2 ( 4 x , + 2 ) 模式4 第二章二次曲线光栅化算法研究及硬件实现 l l 当判断出模式2 ( 3 ) 时，为了进一步区分模式2 和模式3 ，需将参考点从r 移 到b 处。b ( x m y i - 1 ) 代入式( 2 - - i ) 得到一个临时判羽式d t ：d i = d i ( a 2 b 2 ) ( 2 y i 1 ) 如 果d 。 o 则模式2 ，否则模式3 。因此判断d i ( s 2 b ：x 2 y i 1 ) 就可以区分模式2 和模式 3 。对于无浮点数运算的情况只需判断d i a 2 ( y p + 1 ) 。而在下一 个中点，不等号改变方向，则说明椭圆弧已从下部分转入上部分，而上部分已经 转换完毕了，因此算法结束。 2 2 2 椭圆的光栅化算法的硬件实现 这里我们采用c 语言算法中的椭圆中点扫描算法，根据对称性只需画出第一 象限的椭圆弧，在一个时钟周期内并行的画出4 个点。c 语言的程序流程图如下： 第二章二次曲线光栅化算法研究及硬件实现 图2 9 椭圆c 语言程序流程图 图中各个环节解释如下： 初始化1 ：x = o ，y = b ，d l _ b 2 + a 2 ( - b + o 2 5 ) 条件l ：b 2 ( x + 1 ) s 4 ： w h i l e 2 一 s 8 ： c a s e 4 - s 1 2 ； r e a d l 一 s l ：w h i l e l 一 s 2 ；c o n d i t i o n l 卜 s 3 ： c a s e l 一 s 5 ；c a s e 2 一 s 6 ；d r a w l 一 s 7 ； f i n i s h 一 s 9 ：c o n d i t i o n l 2 一 s l o ；c a s e 3 - s 1 1 ； d r a w 2 一 s 1 3 。 当在复位状态s o 时，r d - - - - l ，当r d = 0 时，状态由s o 转移到s 1 。下 面要判断s t a r t l 是否为1 。如果s t a r t l 为1 ，则从状态s 1 转移至状态s 2 ， 进入椭圆上半部分输出坐标点的循环。如果s t a r t l 为“0 ”则仍在s l 状态，在状 态s 1 中读入初值x = o ，y = b 和计算d 1 的初值。在s 2 状态下，若b 2 ( x + 1 ) u s 4 ，$ 1 , o s 2 ，s 2 v s 4 ，和s l vs 4 。线段s 3 和任 何其它线段是不可比较的。 7 图3 1 线段之间的一个次序关系 第三章多边形光栅化算法研究及硬件实现 关系 x 是一个全序关系，当从左到右扫描垂直线时，它以三种方式变化： 1 遇见线段s 的左端点。此时s 一定被加入次序关系。 2 遇见s 的右端点。此时s 一定从次序关系中被移去，因为它不再和任何其 他线段可比较。 3 达到两条线段s 1 和s 2 的一个交点。在次序关系中这里的s l 和s 2 交换位置。 两条线段s l 和s 2 相交的一个必要条件时有某个x ，在次序 i 关系中s l 和s 2 是相邻的。由于仅仅相邻线段可相交，且所有相邻的线段至少被正确地检查 一次，所以此算法不会遗漏交点。并且，恰好每个交点被报告一次。将多边 形的n 条边作为n 条线段应用于该算法，如果将所有线段测试完毕，没有产 生交点，则该多边形为简单多边形，若有交点，则将交点按次序插入多边形 的顶点序列中去。如图3 2 所示，原来的多边形顶点序列为协b ，c ，d 插入交 点后的顶点序列为 a e ，b ，c ，e d 。也就是说，如果多边形原来有1 1 条边，并 且n 条边有k 个交点，现在就将这n 条边分解成了n + 2 k 条边。然后按照前面 描述的梯形剖分算法，依次将这n + 2 k 条边加入，完成对整个平面的梯形剖分， 然后去掉多边形外的梯形，最终得到多边形的梯形剖分结果。 图3 2 自交叉多边形 在前面我们判断梯形是否属于多边形的内部时，规定了5 条规则，如果符合5 条规则中的一条，梯形就不属于简单多边形。当多边形为非简单多边形时，规则4 不再适用，因为一旦多边形自交叉，就无法规定它的外环和内环的方向了，因此 需要对不符合规则1 、2 、3 、5 的多边形做进一步的判断。剖分产生的梯形不是整 个在多边形内部，就是整个多边形的外部，因此只要能判断梯形中任一点的位置， 就能确定整个梯形的位置。为此，我们取梯形中的一点，采用传统的射线法，判 断该点的位置。也就是说，如果通过该点的水平线与多边形边的交点个数为奇数， 该点在多边形的内部；反之，如果交点个数为偶数个，该点在多边形的外部。通 过这种方法就能正确判断梯形的位置。 3 4 2 梯形光栅化算法的硬件实现 在上一节中我们提到了多边形的梯形剖分，由于利用改进的算法对多边形进 矢量光栅变换的研究与硬件实现 行梯形剖分效率也是非常的高。所以我们这里就讨论一下梯脚9 光栅化算法的硬 件实现。 众所周知，梯形是有上、下两条平行边的四边形，所以我们可以将梯形划分 为左右两个直角三角形和中间的一个矩形。这里我们不采用宽直线中三角形扫描 转换算法，而是采取更为简单和直接的算法。我们可以在b r e s e n h a m 直线扫描算 法中加入一个循环语句，这条语句就是负责对两个直角三角形内部进行填充的功 能。具体来说就是在直角三角形的斜边生成过程中，每输出一个直角三角形斜边 生成的点然后以横坐标方向以生成的这个点为起点对直角三角形内部进行填充， 直到碰到这个直接三角形垂直的那个直角边为止。其中左边的直角三角形填充方 向是x 轴正方向，右边的直角三角形填充方向是x 轴反方向。对于中间的矩形则 更为简单，它的线刷子宽度是固定的，其值等于左右两个直角三角形垂直直角边x 坐标相减。每一次填充循环后，y 坐标增1 并进行下一轮填充循环，直到碰到最上 面的水平边为止。我们以左边直角三角形为例来说明具体的过程，矩形和右边的 直角三角形在程序结构上与左边直角三角形相似。程序流程图如下： 图3 3 左三角形程序流程图 第三章多边形光栅化算法研究及硬件实现 上图中各个状态具体解释如下： 初始化：斜边起点横坐标x o ，纵坐标y 0 ，终点横坐标x 1 ，纵坐标y 1 ， 计算d x = x 1 x o , o y - - y 1 y o 。e - 一d x 条件h 判断斜边是否生成完毕m o u t x _ ：e g s o ：r e a d - s 1 ；w h i l e l 一 s 2 ；w h i l e 2 - s 3 ； d r a w - s 4 ：n e x t l i n e s 5 ；f i n i s h - s 6 当在复位状态s 0 时，r d = 1 ，当r d = 0 时，状态由s o 转移到s l 。下面要 判断s t a r t 是否为1 。如果s t a r t 为1 ，则从状态s 1 转移至状态s 2 ，进入三角形 斜边各点生成的循环。如果s t a r t 为“0 ”则仍在s 1 状态，在状态s 1 中读入初值 x o ，y o , x l ，y l 和计算d x ，d y , e 的值。在s 2 状态下，若m o u t x _ _ r e g = e n d x ，则从状态s 2 矢量光栅变换的研究与硬件实现 转移至状态s 3 ，否则从状态s 2 转移至状态s 6 程序结束。在状态s 3 下若m o u t x = e n d x 则从状态s 3 转移至状态s 4 输出程序的斜边坐标点并使x 增1 ，否则从状态s 3 转移 至状态s 5 。在状态s 5 中进行e 值的判断，若e 值大于等于零则对y 值增1 并重新 计算e 值最后转移至状态s 2 ，否则直接转移至状态s 2 进行程序下一轮的循环。 根据以上的算法状态转换图，可以很容易画出它的状态机图，具体如下： 图3 5 左三角形状态机图 第三章多边形光栅化算法研究及硬件实现 根据以上的算法状态机图，可以写出相应的v h d l 程序。其接口定义如下： e n t i t yt i x i n gi s p o r t ( r e s e t ，c l k ：i ns t d - l o g i c ： r d ，a 4 ，a 3 ，a 2 ，a 1 ，a 0 ：i ns t 九l o g i c ： d i n：i ns t d - l o g i c _ v e c t o r ( 7d o w n t o0 ) ； o v e r：0 u ts t d - l o g i c ： d o u t x l ，d o u t y l ：o u ts t d - l o g i cv e c t o r ( 7d o w n t o0 ) d o u t x 2 ，d o u t y 2 ：o u ts t d - l o g i c _ v e c t o r ( 7d o w n t o0 ) d o u t x 3 ，d o u t y 3 ：o u ts t d l o g i cv e c t o r ( 7d o w n t o0 ) ) e n dt i x i n g ； 各个信号的含义如下： r e s e t ： 系统复位信号； c l k ： 系统时钟信号； r d ： 读入动作的开始标志；低电平有效； d i n ：系统的读入数据线； a 4 ，a 3 ，a 2 ，a 1 ，a o 寄存器地址，其含义如下： 0 0 0 0 0 ：坐标原点的横坐标；0 0 0 0 1 ：坐标原点的纵坐标 o o o l o ：左三角形斜边起点的横坐标；0 0 0 1 1 ：左三角形斜边起点的纵坐标 0 0 1 0 0 ：右三角形斜边终点的横坐标；0 0 1 0 1 ：右三角形斜边终点的纵坐标 d o u t x ：左三角形输出点的横坐标： d o u t y ：左三角形输出点的纵坐标； d o u t x x ：右三角形输出点的横坐标； d o u t y y ：右三角形输出点的纵坐标； d o u t x x x ：矩形输出点的横坐标； d o u t y y y ：矩形输出点的纵坐标； o v e r ： 扫描转换结束标志； 最后我们得到综合后的整个梯形v h d l 程序仿真结果如下图：( 梯形四个角坐 标：x 0 = - i ，y o = l , x l = 7 , y l f 4 , x 2 = 1 2 ，y 2 - - - 4 , x 3 = 1 8 ，y 3 = l 详见附录b ) 3 0 矢量光栅变换的研究与硬件实现 r n 喧虫! _ _ je i i 嗣t i r o ll 笪刚坦l ji 咖i 曼苎q q ! i j r 叫uu uu uu _ l j _ l 厂uu l ju _ 1 _ l _ ul juu 一 x 0 1 题d 匝x 叩x 亘x 亘x 砸x x 重x 亘) 弓叵d pd o u t y t 口pd o u l r r e pd o j t y y y 梯形仿真图3 6 1 整个梯形的v h d l 程序由四个进程组成。其中前三个进程分别负责左右直角三 角形和中间矩形的扫描填充，最后一个进程负责判断前三个进程是否全部结束。 程序的信号量部分说明如下所示： a r c h i t e c t u r eh xo ft i x i n gi s 一一左三角形的各个状态量 c o n s t a n ti d l e ：s t d - l o g i c _ v e c t o r ( 4d o w n t o0 ) ：= 0 0 0 0 0 ”： c o n s t a n tr e a d ：s t n l o g i c _ v e c t o r ( 4d o w n t o0 ) ：= ”0 0 0 0 1 ： c o n s t a n tw h i l e l ：s t d - l o g