chap5 基本图形生成算法

《chap5 基本图形生成算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、计算机图形学基础华东理工大学计算机系·谢晓玲2如何在指定的输出设备上根据坐标描述构造基本二维几何图形（点、直线、圆、椭圆、多边形域、字符串及其相关属性等）。第五章基本图形生成算法3图形生成的概念直线段的扫描转换圆的扫描转换多边形的扫描转换与区域填充属性处理反走样技术在OpenGL中绘制图形第五章基本图形生成算法4图形的生成：是在指定的输出设备上，根据坐标描述构造二维几何图形。图形的扫描转换：在光栅显示器等数字设备上确定一个最佳逼近于图形的象素集的过程。图5.1用象素点集逼近直线图形生成的概念55.1直线的扫描转换线

2、画图元的扫描转换计算出落在线段上或充分靠近它的一串像素，并以此像素集近似代替连续直线在屏幕上显示的过程。直线的绘制要求（1）直线要直；（2）直线的端点要准确，无定向性无断裂；（3）直线的亮度、色泽要均匀；（4）画线的速度要快；（5）具有不同的色泽、亮度、线型等。6直线的扫描转换解决的问题：给定直线两端点P0(x0,y0)和P1(x1,y1)，画出该直线。数值微分法（DigitalDifferentialAnalyzer,DDA）中点Bresenhan算法改进的Bresenhan算法数值微分法数值微分法即DDA(Di

3、gitalDifferentialAnalyzer)算法，是根据直线的微分方程来计算Δx或Δy生成直线的扫描转换算法。在一个坐标轴上以单位间隔对线段取样,以决定另一个坐标轴方向上最靠近理想线段的整数值。数值微分法的本质，是用数值方法解微分方程，通过同时对x和y各增加一个小增量，计算下一步的x、y值。数值微分法(DDA法)8数值微分法(DDA法)直线的微分方程：ε=1/max(

4、△x

5、,

6、△y

7、)图5.2DDA算法原理max(

8、△x

9、,

10、△y

11、)=

12、△x

13、，即

14、k

15、≤1的情况：max(

16、△x

17、,

18、△y

19、)=

20、△y

21、，

22、此时

23、k

24、≥1：数值微分法步骤：给定：两个端点P0(x0,y0)和P1(x1,y1)，则：dx=(x1-x0)；dy=(y1-y0);根据

25、dx

26、、

27、dy

28、，哪个大，哪个为步长参数：①当

29、dx

30、>

31、dy

32、，即

33、m

34、<1时，若x0x1，即直线从右到左，则x=-1，y=-m②当

35、dx

36、≤

37、dy

38、，即

39、m

40、≥1时，若x0x1，即直线从右到左，则y=-1，x=-1/m数值微分法(DDA法)voidDDA_Li

41、ne(intx0,inty0,intx1,inty1,intcolor)inti；floatdx,dy,length,x,y;if(fabs(x1-x0)>=fabs(y1-y0))length=fabs(x1-x0);elselength=fabs(y1-y0);dx=(x1-x0)/length;dy=(y1-y0)/length;i=1;x=x0;y=y0;while(i<=length){PutPixel(int(x+0.5),int(y+0.5),color);x=x+dx;y=y+dy;i++;x

42、int(y+0.5)y+0.5000+0.5100.4+0.5210.8+0.5311.2+0.5421.6+0.5522.0+0.5直线段的DDA扫描转换举例:线段P0(0,0)和P1(5,2)的DDA方法扫描转换。12增量算法：加法+取整直观、易实现x与dx、y与dy用浮点数表示，每一步要进行四舍五入后取整，不利于硬件实现。数值微分法(DDA法)——特点13中点Bresenham算法算法原理：根据直线的斜率确定或选择变量在x或y方向上每次递增一个单位，而另一方向的增量为1或0，它取决于实际直线与相邻象素点的距离

43、，这一距离称为误差项。14中点Bresenham算法直线的方程图5.4直线将平面分为三个区域假定0≤k≤1，即0≤Δy/Δx≤1，x是最大位移方向，则每次x加1，若M在Q下放，y加1（取Pu)；若M在Q上放，取y加0（取Pd)。图5.5Brensemham算法生成直线的原理判别式：则有：图5.5Brensemham算法生成直线的原理d的意义：d=F(xM,yM)=F(xi+1,yi+0.5)=yi+0.5-k(xi+1)-b=yi+0.5-[k(xi+1)+b]=yM-yQ这里：yQ=k(xi+1)+b、yM=yi

44、+0.5图5.5Brensemham算法生成直线的原理误差项的递推（d1<0）图5.6误差项递推(a)误差项的递推（d1≥0）图5.6误差项递推(b)20初始值d的计算中点Bresenham算法图5.9计算初值21改进：用2d△x代替d,令D＝2d△x则：中点Bresenham算法——改进yDikdixxdiDi+1D③dyxDiyxxdikdixxdiDi