《光栅图形生成算法》PPT课件

《《光栅图形生成算法》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Ch3光栅图形生成算法光栅显示器显示的图形是用一系列紧靠该图形路径的像素表示的。确定哪些像素能构成所需图形的过程称为图形的光栅化(也称光栅图形生成算法)，或称为图形的扫描转换。本章讨论内容直线生成算法圆和圆弧的程序设计区域填充算法字符生成反走样技术直线生成算法直线是最基本的图元，曲线由一系列直线段逼近，复杂图形可看作是由无数直线段组成的。直线生成质量影响计算机图形设计的质量。因此，光栅化直线生成算法必须服从四条原则：直而光滑、端点准确、亮度均匀、速度快。直线生成算法逐点比较法绘图仪常用的一种方法。在每次画图过程中,绘图笔每画一笔，就与规定的图形进行比较，然后决定下一步的走向，用步

2、步逼近的方法画出规定的图形。XYO假设以坐标原点作为直线起点，各象限中画笔走向如图所示。逐点比较法一般公式:要画的线段为OA，画笔的当前的位置为M。以OM，OA的斜率的大小来计算偏差。d=tg-tg=ym/xm-ya/xa=(ym*xa-ya*xm)/xm*xa；（1）偏差计算（以第一象限为例）当d<0时，表示笔在OA线段的下方，根据约定此时应走+y一步；当d>=0时，表示笔在OA线段的上方，应该走+x一步。只判断d的正负,不管大小,第一象限xm,xa均为正。第一象限偏差的判断公式:Fm=ym*xa-ya*xmXYOA(xA,yA)M(xM,yM)αβ逐点比较法递推公式:上述公

3、式要计算两次乘法,设法用前一点的偏差来推算走步的方向以及走步后的偏差.（1）偏差计算笔的当前位置为Mi(xi,yi),此时Fi=yixa-yaxi.如果Fi<0,应走+y一步到Mi+1,即:xi+1=xi,yi+1=yi+1;Mi+1处的偏差Fi+1=yi+1xa-yaxi+1=yixa+xa-yaxi=Fi+xa;如果Fi>=0,应走+x一步到Mi+1,即:xi+1=xi+1,yi+1=yi;Mi+1处的偏差Fi+1=yi+1xa-yaxi+1=yixa-yaxi-ya=Fi-ya;如果Fi>=0则走+x一步,此时Fi+1=Fi-ya;如果Fi<0则走+y一步,此时Fi+1=Fi

4、+xa;逐点比较法设步距为t,直线在x,y方向的增量分别为x和y.按上述运算方法,绘图笔从直线的起点画到终点,在x方向应走

5、x/t

6、步,在y方向应走

7、y/t

8、步.取n=

9、x/t

10、+

11、y/t

12、作为终点判断的控制数,并将此数存入计数器内.在x或y方向上每走一步计数器减1,当计数器减到零时,作图停止.（2）终点判断直线生成算法Bresenham直线生成算法基本原理：沿某一计长方向上，每次变化一个单位步长，另一方向上的变化量通过计算获得。这种方法在计算判别式时，计算量很小，生成的直线光滑，因而应用广泛。假设直线的斜率在0~1之间，k=△y/△x，x的变化率比y的变化率

13、大，约定每次x方向变化一个像素单位，相应y方向的变化量为0或1个像素单位。Bresenham直线生成算法已知直线起点(x1,y1)，终点(x2,y2)；直线上第i个像素为P(xi,yi)，它是已经选定的离直线最近的当前像素。现在要决定下一个像素是S(xi+1,yi),还是T(xi+1,yi+1)?若s=t,则选择T。P(xi,yi)S(xi+1,yi)T(xi+1,yi+1)stQ(x,y)计算判别式:理论直线上点Q坐标为y=k(xi+1)+b;求s和t:s=y-yi=k(xi+1)+b-yi;t=(yi+1)-y=(yi+1)-k(xi+1)

14、-bstP(xi,yi)S(xi+1,yi)T(xi+1,yi+1)计算判别式:理论直线上点Q坐标为y=k(xi+1)+b;求s和t:s=y-yi=k(xi+1)+b-yi;t=(yi+1)-y=(yi+1)-k(xi+1)-b则s-t=2k(xi+1)-2yi+2b-1由于k=△y／△x,△x=x2-x1,△y=y2-y1,代入上式，得到△x(s-t)=2△y·xi-2△x·yi+(2△y-△x+2b△x)(3-1)记di=△x(s-t),△x＞0,di与(s-t)同号;di值符号为选择下一个像素的判别因子。为得到di的递推形式,以i+1代入式(3-1)的i，得di+1=2△

15、y·xi+1-2△x·yi+1+(2△y-△x+2b△x)(3-2)计算判别式:将(3-2)减去(3-1),且xi+1=xi+1，得di+1=di+2△y-2△x(yi+1-yi)(3-3)其中,yi+1-yi=0或1取决于判别因子di值的符号。如果di＜0，取S为下一像素,即xi+1=xi＋1,yi+1=yi,有di+1=di+2△y(3-4)如果di≥0，取T为下一像素,即xi+1=xi+1,yi+1=yi+1,有di+1=di+2△y-2△x(3-5)将y1