第4章基本光栅图形算法.ppt

《第4章基本光栅图形算法.ppt》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第4章基本光栅图形算法主要内容光栅图形生成算法是计算机图形学的基础，本章主要包括直线和圆弧的生成算法、多边形的填充以及其他相关的图形基本元素的生成算法。直线和圆弧等是图形的基本元素，生成基本元素算法的效率对图形系统的效率有直接关系。虽然很多智能绘图机和图形显示器都有自己生成直线和圆弧的功能，但也有很多情况下要自己编写一些设备的驱动程序，在图形软件包中用软件生成直线和圆弧有时也是十分必要的。多边形的填充算法是面显示的基础，其思想可用于解决计算机图形学中的消隐、真实感显示等许多问题，本章主要讨论此类图元的绘制问题。主要章节直线生成算法4.1圆弧生成算法4.2

2、多边形的填充4.3区域填充4.4光栅图形的反走样算法4.54.1直线生成算法数学上的直线理想的直线是没有宽度的，是由无数个点构成的集合光栅化的直线在光栅的有限像素点阵中，确定最佳逼近于该直线的一组像素，用这些像素表示该直线。常用算法DDA方法正负法Bresenham算法屏幕坐标系产生光栅图形，首先要为每个像素指定一个惟一坐标，因此需要在屏幕上建立一个坐标系，每个像素中心的坐标为该像素的坐标,坐标均为整数图4.1像素和坐标的对应关系(a)(b)直线的三种表示显示Y=kx+b隐式ax+by+c=0参数P(t)=(1-t)P0+tP14.1.1生成直线的D

3、DA算法设直线的起点为(xs,ys),终点为（xe,ye）,并设(xs,ys)和（xe,ye）都是整数（做求整处理）。令Δx=xe–xs,Δy=ye–ys。则直线的参数方程是(4.1)目标是能快速地求出能很好地表示直线的像素。提高速度的方法之一是:乘法用加法实现，用等步长计算直线上的点。设是第i步得到的直线上的点，则直线上第个i+1点是(,),其中(4.2)图4.2图中黑圆点表示用DDA法生成的直线当,即直线斜率小于1时应使x方向每次增加1，y方向最多增加1，此时取.当时，直线斜率大于1，取所以图4.2图中黑圆点表示用DDA法生成的直线用式4.2可求得图

4、4.2中直线上用三角形表示的点，但显示时要用像素表示，可用舍入的办法得到最靠近三角形的像素，用这些像素表示直线，这个方法称为DDA方法。DDA算法的缺点:计算量较大，产生一个像素需要2次加法，2次取整运算。算法还需要除法运算，增加了硬件实现上的困难。生成直线的DDA算法4.1.2正负法基本原理：为讨论方便，假设直线斜率在0和1之间。假设是直线上的一点（表示），与P最近的像素为（）(表示)，那么下一个与直线最近的像素只能是正右方的或右上方的两者之一。以M表示和的中点，Q是直线与垂线的交点。显然，若M在Q的下方，则离直线近，应取为下一个像素，否则应取图4.3

5、正负法每步迭代涉及的象素和中点示意图正负法算法的具体实现设直线的起点和终点分别为(x0,y0)和(x1,y1),直线方程为:其中，，分别对应于点在直线上、上方和下方要判断M在直线的上方还是下方，只需把M代入，判断它的符号即可。构造判别式d<0，Q在M上方，取P2为下一像素d>0，取P1为下一像素，d=0,可在两个点中任取一个，约定取右下方的点。P2P1正负法算法的具体实现在d>=0，取右下方像素P1，下一个像素应取哪个，应计算P2P1若d<0，则取右上方像素P2，并计算讨论d的初始值，第一个像素应取(x0,y0)由于(x0,y0)在直线上，故F(x0,y

6、0)=0。因此，正负法程序voidMidpointLine(intx0,inty0,intx1,inty1){inta,b,delta1,delta2,d,x,y;a=y0-y1;b=x1-x0;d=2*a+b;delta1=2*a;delta2=2*(a+b);x=x0;y=y0;glBegin(GL_POINTS);glVertex2s(x,y);glEnd();while(x

7、lEnd();}//EndWhile}//EndMidpointLine4.1.3Bresenham算法令m=△y/△x,考虑0≤m≤1(4.4)x方向增加1,y方向增加myi+1=yi+m(xi+1–xi)=yi+m(4.5)由起点(xs,ys),可求得直线上的点(xi，yi),i=1,2,3,…,其中x1=xs,y1=ys用坐标为(xi，round(yi))的象素来表示直线上的点下面考虑如何快速地求出直线上的点设B点是直线上的点，其坐标为(xi+1,yi+1)，点(xi+1,yi+1,r)只能从C或D点中选。设A为CD边的中点，若B在A点上面则应取D

8、点作为(xi+1,yi+1,r),否则应取C点。ε(xi+1)=yi+1–(yi