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

第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>△y>0，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(△x>0，|△x|>|△y|)（1）△x<0时不正确（2）|△x|<|△y|时不精确如(0,0)(2,5)将生成3个点0,01,32,5可将任意方向直线分为以下4类：xi+1=xi+1，yi+1=yi+k(△x>0，|△x|>|△y|)yi+1=yi

+1，xi+1=xi+1/k

（△y>0，|△x|<|△y|）xi+1=xi

–1，yi+1=yi–k

（△x<0，|△x|>|△y|）yi+1=yi

–1，xi+1=xi

–1/k

（△y<0，|△x|<|△y|）3．程序设计绘制△x>△y>0方向直线段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)，斜率0<k<1,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，

若ei<0，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=-1

xye-----------------------------00-110321-331142-5524．程序设计直线的斜率在0、l之间的Bresenham画线算法的VC主要代码如下：CDC*pDC=GetDC();dx=x1-x0;dy=y1-y0;e=-dx;y=y0;dxx=dx+dx;dyy=dy+dy;for(x=x0;x<=x1;x++){ pDC->SetPixel(x,y,RGB(0,0,0));

if(e>=0)y=y++,e=e-dxx; e=e+dyy;}（1）误差计算

可以作为选择y的判别量，但式子还复杂。乘Δx，并代入kΔx=Δy则ei的计算仅包括整数运算，其符号与(d1-d2)的符号相同。当ei<0时，直线上理想位置与像素(xi＋1，yi)更接近，应取yi；当ei>0时，像素(xi＋1，yi＋1)与直线上理想位置更接近，应取yi+1；当ei=0时，两个像素与直线上理想位置一样接近，可约定取(xi＋1，yi＋1)。

特别地，代入xi=x0，yi=y0，b=y0-Δy/Δx*x0，则e0=2Δy-Δxe0=2Δy*x0-2Δx*y0+[2Δy+Δx*(2b-1)]=2Δy*x0-2Δx*y0+2Δy+Δx*(2y0-Δy/Δx*x0-1)=2Δy*x0-2Δx*y0+2Δy+2Δx*y0-2Δy*x0–Δx

=2Δy-Δxei的几何意义：ei是使用xi点信息计算的量，用于判断xi+1点上y的选取。（2）ei的递推代入x的增量为1，则如果选择右上方像素，即：，则：如果选择右方像素，即：，则：上述公式假设Δx>Δy>0e0=2Δy-Δxxi+1=xi+1ifei>0yi+1=yi+1,ei+1=ei+2Δy-2Δxelseyi+1=yi,ei+1=ei+2Δy共包含8种情况，其他情况可以类似地进行推导如Δx<0,Δy>0,|Δx|>|Δy|时e0=2Δy-|Δx|xi+1=xi-1ifei>0yi+1=yi+1,ei+1=ei+2Δy-2|Δx|elseyi+1=yi,ei+1=ei+2Δy练习：1(-1,0)(4,4)2(4,1)(-1,5)3.1.4直线线宽的处理（1）垂直线刷子：假设直线斜率在[－1，1]之间，把刷子放置成垂直方向，刷子中点对准直线一端点，然后让刷子中心往直线的另一端移动，即可“刷出”具有一定宽度的线。如图3-8所示为线宽为5的线段。

（2）水平线刷子：直线斜率不在[－1，1]之间，可以把刷子放置成水平方向，刷子中点对准直线一端点并往直线的另一端移动，可“刷出”具有一定宽度的线，如图3-9所示。图3-8垂直线刷子绘制具有宽度的线图3-9水平线刷子绘制具有宽度的线线刷子算法简单、效率高。但有以下几个缺点：①线的始末端总是水平或垂直，当线宽较大时，看起来很不自然。②两条线的汇合处外角将有缺口，如图3-10所示。③斜线与水平（或垂直）线不一样粗。对于水平线或垂直线，刷子与线条垂直，因而最粗。其粗细与指定线宽相等。而对于45°斜线，刷子与线条成45°角，粗细仅为指定线宽的倍。④当线宽为偶数个像素时，用上述方法绘制的线条要么粗一个像素，要么细一个像素。（3）方形刷子：把边宽为指定线宽的正方形的中心沿直线作平行移动，即可获得具有线宽的线条。图3-11所示为用正方形刷子绘制的具有宽度的线条。图3-10刷子所产生的缺口图3-11方形刷子绘制的具有宽度的线3.2圆与椭圆图形3.2.1简单方程产生圆弧利用圆的参数方程，直接计算离散点值。圆的参数方程为

x=x0+rcos

y=y0+rsin

（0≤

≤2

）式中，x0和y0为圆的圆心坐标，r为圆的半径。对以上方程进行离散化：

xi=x0+rcos

i

yi=y0+rsin

i关键的问题是

i+1与

i的关系，即

i+1=

i+d中的d如何确定。如果使用画点生成圆，则d与圆的半径r相关，r越大，圆的周长就长，圆周上的像素点就多。对于固定范围内的

，d就越小，根据圆周长公式，取d=1/(2

r)。离散化后圆的参数取值如下：

0=0,

i+1=

i+1/(2

r),i=0,1,2…,直到

i=2

时结束其VC主要程序代码为：

CDC*pDC=GetDC();d=0.5/r/3.14;for(t=0;t<6.283;t=t+d){ x=x0+r*cos(t); y=y0+r*sin(t); pDC->SetPixel(x,y,RGB(0,0,0));}3.2.3Bresenham画圆算法基本思想是寻找最接近于实际圆周上的点。与中点画圆算法相似，考虑圆心在原点，半径为R的8分圆，取（0，R）为起点，按顺时针方向生成圆。即Bresenham画圆算法的递归式为d0=3-2R(x0=0，y0=R)当di＜0时，di+1=di+4xi+6，xi+1=xi+1当di≥0时，di+1=di+4(xi－yi)+10，

xi+1=xi+1，y