第2章 图形基元的显示.pptVIP

第二章 图形基元的显示 第一节 直线扫描转换算法 第二节 圆的扫描转换算法 第三节 区域填充 扫描转换 将图形描述转换成用像素矩阵表示的过程 图形基元（输出图形元素）图形系统能产生的最基本图形 线段、圆、多边形 第一节 直线扫描转换算法 DDA直线扫描转换算法 中点画线法 Bresenham画线算法 1.DDA线段扫描转换算法 2.中点画线法 假定直线斜率在0、1之间，x = xi时已选（xi,yi）像素， 确定x = xi +1与直线最近的像素 P1 ( xi + 1,yi )、P2 ( xi+1,yi+1) M表示P1与P2的中点，M = ( xi+1,yi +0.5)。 Q是直线与垂直线x = xi + 1的交点 若M在Q的下方，则P2离直线近，应取为下一个像素；否则应取P1 起点和终点分别为 ( x0 , y0 ) 和( x1 , y1 )。 其所在直线F(x , y) = ax + by + c 其中，a=y0－y1，b=x1－x0，c=x0y1－x1y0 。 直线上的点，F (x，y) = 0 ； 直线上方的点，F(x，y) 0 ； 直线下方的点，F(x，y) 0。 Q在M的上方还是下方，只要把M代入F(x，y)，并判断它的符号。 d = F(M) = F( xi+1，yi+0.5 ) = a ( xi+1 ) + b ( yi+0.5 ) + c 当 d 0 时，M在直线下方(即在Q的下方) ，应取右上方的P2 。 当 d 0 时，则取正右方的P1。 当 d = 0 时，二者一样合适，取P1。 d是xi, yi的线性函数，因此可采用增量计算，提高运算效率。 3.Bresenham画线算法 斜率m在0到1之间，并且 设在第i步已经确定第i个像素点是 ，它是直线上点 的最接近位置， ，现在看第i+1步如何确定第i+1个像素点的位置。 算法三：中点画圆法 讨论如何从点(0，R)至( ， )的1／8圆周 若x坐标为(xi,yi)，下一个像素只能是(xi+1,yi) 的P1点或 (xi+1,yi-1) 的P2点 构造函数：F(x,y)=x2+y2-R2 圆上的点，F(x,y)=0 圆外的点，F(x,y) 0 圆内的点，F(x,y) 0 P1和P2的中点为 M=(xi+1,yi-0.5) F(M) 0时，M在圆内，取P1 F(M) 0时，M在圆外，取P2 F(M)=0时，P1或P2随取一个即可，取P2 算法三：中点画圆法改进一 在上述算法中，使用了浮点数来表示判别式d。 简化算法，在算法中全部使用整数，使用e=d-0.25代替d。 初始化运算d=1.25-R对应于e=1-R。 由于e的初值为整数，且在运算过程中的增量也是整数，故e始终是整数，所以 判别式d 0对应于e -0.25，等价于e 0。 判别式d≥0对应于e≥-0.25，等价于e≥0。 算法三：中点画圆法改进二 上述算法还可以进一步改进。以提高效率。注意到d的增量是x、y的线性函数，每当x递增1，d递增Δx=2。每当y递减1，d递增Δy =2。由于初始像素为(0,R)，所以Δx的初值为3，Δy的初值为-2R+2。 算法四：Bresenham画圆算法 第三节 区域填充 种子填充算法 多边形扫描转换算法 一、种子填充算法 二、多边形的扫描转换算法 “奇偶”性质：即一条直线与任意封闭的曲线相交时，总是从第一个交点进入内部，再从第二个交点退出，以下交替的进入退出，即奇数次进入，偶数次退出。当然可能有一些“相切”的点应特殊处理。 奇偶规则 二、多边形的扫描转换算法 扫描转换算法步骤： step1．找出扫描线与多边形边界线的所有交点； step2．按x坐标增加顺序对交点排序； step3．在交点对之间进行填充。（偶数） “相切”点的特殊处理： 正确的解决办法是，当顶点表现为是局部极大或局部极小时，就看做是二个，否则看做一个。如果一个顶点的前面和后面各有一些相邻顶点的y坐标，都小于该顶点的y坐标，则这个顶点是局部极大。局部极小可类似地确定。 实际处理这个问题可以有一个简便办法，那就是对应该看做是一个的顶点，将其上面的边缩短两条相邻扫描线对应的一个单位。 void Polygonfill(PointArray ptArray,COLORREF color){ int len; int i; CEdgeTable ET;CActiveEdgeTable AET; ET.Init(ptArray); AET.AETlist .RemoveAll (); int y=ET.ETli