第03章1-基于光栅扫描转换的二维图元生成算法讲述.pptx

计算机图形学Computer Graphics 第3章 基于光栅扫描的二维图元生成算法 第3章 基于光栅扫描的二维图元生成算法 本章研究如何将连续的图形转换成显示器能够识别的栅格点阵形式 – 离散化。 从20世纪70年代初光栅图形显示器的诞生到现在，出现了大量比较成熟的光栅扫描算法，主要是针对以栅格排列像素的显示设备，研究图形输出的近似算法。包括各种画线算法、填充算法、多种线型线宽的绘制方法、字型技术、图形的裁剪算法以及反走样技术等 3.1 直线的扫描转换 在数学上，理想的直线是没有宽度的，是由无数个点构成的集合。 当我们对直线进行光栅化时，只能在显示器所给定的有限个象素组成的矩阵中，确定最佳逼近于该直线的一组象素，并且按扫描线顺序，以指定的方式对这些象素进行写操作，这就是通常所说的用显示器绘制直线或直线的扫描转换。 3.1 直线的扫描转换 通常直线段是有宽度的 为简单起见，讨论只有一个像素宽度的直线段的扫描转换算法。对于具有一个像素宽度的直线段来说，近似表示它的像素集也应该具有一个像素的宽度 当该线段的斜率落在-1到1之间时，它在每个扫描列上仅有一个像素。 同样，当线段的斜率的绝对值大于1时，它在每个扫描行上仅有一个像素。 3.1.1 基本增量算法DDA 直线方程：y=mx+b 0m1， m= △y/ △x ； ?x=1，xi+1=xi+ 1，yi+1=yi+m 3.1.1 基本增量算法DDA 增量算法的定义：每一步都是根据前一步进行增量计算。这种算法通常被称作数值微分(DDA)算法。DDA(Digital Differential Analyzer algorithm)是用数值方法解决微分方程的一种手段 如果｜m｜1，则x的步进会使y的步进超过1，此时，如果采用上述算法将会使得点亮的象素个数太少，画出来的线没有很好的模拟理想直线。解决办法是颠倒x与y的位置，给y以单位增量，而x的增量为Δx=Δy/m=1/m，即取x轴和y轴中变化最快的轴作为参考轴以保证直线被光栅化后有足够多的象素。 增量算法的缺点是需要用浮点数表示，而且每一步运算都必须舍入取整，这不利于用硬件实现运算。 3.1.1 基本增量算法DDA 为直线类CLineType增加一个函数DDADrawLine void CLineType::DDADrawLine(HDC hdc, COLORREF rgb) { int x0,y0,x1,y1, i; double m,y; x0 = m_ptBegPos.Getx(); y0 = m_ptBegPos.Gety(); x1 = m_ptEndPos.Getx(); y1 = m_ptEndPos.Gety(); m=(double)(y1-y0)/(double)(x1-x0); y=y0; CPointType *p; for(i=x0;ix1;i++){ p = new CPointType(i,(int)(y+0.5)); p-DrawPoint(hdc,rgb); delete p; y+=m; } } 3.1.2 中点画线算法 消除了浮点加法和取整运算，采用整数加法和比较运算，大大提高了运算速度 主要采用整数加法和比较运算，运算速度大大提高，是图形软件广泛采用的算法 仍然假定直线斜率 3.1.2 中点画线算法 直线方程 隐函数形式 直线的正负划分性 3.1.2 中点画线算法 中点M=(xp+1,yp+1/2) d=F(M) =0 M是直线一点 0 M在直线上方 0 M在直线下方 d =0 点亮E或者NE 0 点亮E 0点亮NE 已知当前dp，可推算出下一个像素(xp+1,yp+1) 接着推算出下一个dp+1 3.1.2 中点画线算法 由 令 -Δy=a, Δx=b, -Δx·b=c dp=a(xp＋1)+b(yp＋1/2)＋c dp+1=F(xp+1＋1，yp+1＋1/2) =F(xp+2，yp+3/2)，当dp0 =F(xp+2，yp+1/2)，当dp0 dp+1 = a(xp+2)+b(yp+3/2)+c，当dp0 a(xp+2)+b(yp+1/2)+c，当dp0 dp+1 = dp+a+b，当dp0 dp+a， 当dp0 3.1.2 中点画线算法 dp+1 = dp- Δy+Δx ，当dp0 dp-Δy， 当dp0 由于d和2d的正负判别式是等价的，不妨都乘以2，则 dp+1 = dp- 2Δy+2Δx ，当dp0 dp-2Δy， 当dp0 yp+1 = yp+1 ，当dp0 yp， 当dp0 3.1.2 中点画线算法 void CLineType::MidDrawL