3光栅图形生成讲解.ppt

1 0 3 2 5 4 7 6 0 1 2 3 4 5 6 7 8 9 s 4,3 5,3 4,4 3,3 5,2 4,2 3,2 5,1 4,1 3,1 3,1 2、扫描线种子填充算法 从包含种子像素的堆栈中弹出区段的种子像素 沿着扫描线对包含种子像素的区段左右像素进行填充，直到遇到边界像素为止，从而填满包含种子像素的区段 区段内最左的和最右的像素记为Xleft和Xright 在Xleft ≤x ≤ Xright范围内,检查与当前扫描线相邻的上下两条扫描线是否全为边界像素或者前面已经填充过的像素.如果这些扫描线既不包含边界像素,也不包含已填充的像素，那么在Xleft ≤ x≤ Xright中把每一区段的最右像素作为种子像素并压入堆栈. 0 2 4 6 8 10 12 0 2 4 6 8 10 s 0 2 4 6 8 10 12 0 2 4 6 8 10 1 2 3 0 2 4 6 8 10 12 0 2 4 6 8 10 1 2 3 3 0 2 4 6 8 10 12 0 2 4 6 8 10 1 2 3 3 0 2 4 6 8 10 12 0 2 4 6 8 10 1 2 3 3 0 2 4 6 8 10 12 0 2 4 6 8 10 1 2 3 4 5 3 2. 中点画圆法 以从(0，R)到( ， )的1/8圆为例，假定当前已确定了圆弧上的一个像素点为 那么，下一个像素只能是右方的 或右下方的 。 构造函数F(x,y)=x2+y2-R2, F(x,y)=0 F(x,y)0 F(x,y)0 点(x,y)在圆上 点(x,y)在圆外 点(x,y)在圆内 设M为P1和P2的中点，M为（xp+1,yp-0.5） 若F(M)0，M在圆内，P1点离圆弧更近，取P1为下一个像素； 若F(M)0，M在圆外，P2点离圆弧更近，取P2为下一个像素； 若F(M)=0，M在圆上，P1、P2可任取，这里约定取P2 ； 构造判别式 若dp0 则应取P1为下一像素，再下一像素的判别式为: 3.2 线的生成算法 若dp≥0 若dp0 初始值: d0=F(1,R-0.5) =1.25-R 设置e=d-0.25 MidPointCircle(int r, int color) { int x,y; int e; x=0; y=r; e=1-r; circlepoints (x,y,color);//做对称处理 while(x=y) { if(e0) e+=2*x+3; else { e+=2*(x-y)+5; y--; } x++; circlepoints (x,y,color); //做对称处理 } } 中点画圆算法 1.输入圆的半径和颜色; 2.设置初始点及判别式的值,扫描第一个点; 3.如果判别式小于0，判别式的值加2x+3,取水平方向点;否则判别式的值加2(x-y)+5,取右下方向点;扫描点(x,y); 4.如果xy,转到3，否则结束. 3. 椭圆的绘制 中点画圆法可以推广到一般二次曲线的生成 定义椭圆中点算法的判别式: F(x,y)=b2x2+a2y2-a2b2 F(x,y)=0 F(x,y)0 F(x,y)0 点(x,y)在椭圆上 点(x,y)在椭圆外 点(x,y)在椭圆内 根据F(x,y)=b2x2+a2y2-a2b2 椭圆的斜率为:dy/dx=-b2x/a2y x y 若dp0 斜率k=-1 xp+1=xp+1 若dp=0 dp的初始条件是： 根据弧起点(0,b),所以第一个中点是(1,b-0.5),故对应的判别式是 y方向变化快的判别式怎么求？初始值为多少？ x y 斜率k=-1 3.3 区域填充 3.3.1 扫描线算法 3.3.2 种子填充算法 有序边表的扫描线算法 边界标志算法 边填充算法 简单种子填充算法 扫描线种子填充算法 3.3.1 扫描线算法 多边形区域有两种重要的表示方法: 顶点表示 点阵表示 即是用多边形的顶点序列来表示多边形。 这种表示直观、几何意义强、占内存少，易于进行几何变换，但由于它没有明确指出哪些像素在多边形内，故不能直接用于区域填充。 用位于多边形内的像素集合来刻画多边形 这种表示丢失了许多几何信息，但便于进行填充 扫描线类算法 种子填充类算法 扫描线多边形区域填充算法基本原理:待填充区域按Y方向(X方向亦可)扫描线顺序扫描生成。 具