计算机图形学-第3章-直线与圆.ppt

第3章二维图形生成算法3.1直线图形对直线进行光栅化时，只能在显示器所给定的有限个像素中，确定最佳逼近于该直线的一组像素。用写点方式对像素进行写操作，这就是通常所说的用显示器绘制直线，或直线的扫描转换（如图3-1所示）。图3-1直线的扫描转换示意图3.1.1数值微分法数值微分法DDA（DigitalDifferentalAnalyzer）的本质，是用数值方法解微分方程，即通过同时对x和y各增加一个小增量，计算下一步的x、y值。1．DDA法的公式推导设直线的起点为(x0，y0)，终点为(x1，y1)，直线的斜率为：k=△y/△x△x＝x1-x0，△y＝y1-y0。设△x△y0，x从起点到终点变化，每步递增1个像素，计算对应的y坐标，y＝kx+b，这种方法直观可行，然而效率较低。每步运算都需一个浮点乘法与一个加法运算。可简化：yi+1=kxi+1+b=k(xi+1)+b=kxi+b+k=yi+k直线扫描转换的数值微分算法：k=(y1-y0)/(x1-x0)，x0=x0，y0=y0xi+1=xi+1，yi+1=yi+k，（i=0，1，2，…，x1－x0）当0△x△y时，每步y递增1个像素(yi+1=yi+1)，需计算对应的x坐标：xi+1=yi+1/k－b/k=(yi+1)/k-b/k=yi/k－b/k+1/k=yi+1/k图3-2DDA直线扫描转换算法示意图2．任意方向直线的DDA公式递推公式xi+1=xi+1，yi+1=yi+k(△x0，|△x||△y|)（1）△x0时不正确（2）|△x||△y|时不精确如(0,0)(2,5)将生成3个点0,01,32,5可将任意方向直线分为以下4类：xi+1=xi+1，yi+1=yi+k(△x0，|△x||△y|)yi+1=yi+1，xi+1=xi+1/k（△y0，|△x||△y|）xi+1=xi–1，yi+1=yi–k（△x0，|△x||△y|）yi+1=yi–1，xi+1=xi–1/k（△y0，|△x||△y|）3．程序设计绘制△x△y0方向直线段DDA法的主要程序intx0,y0,x1,y1;floaty,k;CDC*pDC=GetDC();k=(y1-y0)/(x1-x0);//(x0,y0)(x1,y1)为直线段的两个端点坐标y=y0;for(x=x0;x=x1;x++) {pDC-SetPixel(x,(int)(y+0.5),RGB(0,0,0)); y=y+k; }当x0=10,y0=10,x1=150,y1=120时，窗口的坐标原点在左上角，该程序的运行效果如图3-3所示。图3-3DDA法绘制直线效果示意图3.1.3Bresenham画线算法Bresenham算法增加了一个判别参数，实现了全整数计算，每步计算只包括一个正负判别和一个整数加法，适合硬件实现。已知：线段(x0,y0),(x1,y1)，斜率0k1,x,y为整数y=kx+bΔx=x1-x0Δy=y1-y0k=Δy/Δx（3）计算过程1计算Δx、Δy等常数计算e0=2Δy-Δx绘制点(x0,y0)2设xi点的计算、绘制已经完成，xi、yi、ei为已知，对xi+1点若ei=0，若ei0，3循环2

思路：x从x0开始，每次给予增量1，计算对应的y。事实上，y只有2个选择，即yi或yi+1，可以寻找一个判断方法，而不按方程进行计算。线段(0,0),(5,2)Δy=2，Δx=5，2Δy-2Δx=-6，2Δy=4,e0=2Δy-Δx=-1xye-----------------------------00-110321-331142-5524．程序设计直线的斜率在0、l之间的Bresenham画线算法的VC主要代码如下：C