03光栅图形生成算法.ppt

Ch3 光栅图形生成算法 光栅显示器显示的图形是用一系列紧靠该图形路径的像素表示的。 本章讨论内容 直线生成算法 圆和圆弧的程序设计 区域填充算法 字符生成 反走样技术 直线生成算法 直线是最基本的图元，曲线由一系列直线段逼近，复杂图形可看作是由无数直线段组成的。直线生成质量影响计算机图形设计的质量。因此，光栅化直线生成算法必须服从四条原则：直而光滑、端点准确、亮度均匀、速度快。 直线生成算法 逐点比较法 绘图仪常用的一种方法。在每次画图过程中,绘图笔每画一笔，就与规定的图形进行比较， 然后决定下一步的走向，用步步逼近的方法画出规定的图形。 逐点比较法 逐点比较法 逐点比较法 直线生成算法 Bresenham直线生成算法 Bresenham直线生成算法 已知直线起点(x1,y1)，终点(x2,y2)； 直线上第i个像素为P(xi,yi)，它是已经选定的离直线最近的当前像素。现在要决定下一个像素是S(xi+1,yi),还是T(xi+1,yi+1)? 若st, 则S靠近直线, 应该选择S; 若 s=t,则选择T。 计算判别式: 理论直线上点Q坐标为y= k(xi+1)+b;求s和t: s=y-yi=k(xi+1)+b-yi; t=(yi+1)-y=(yi+1)-k(xi+1)-b 计算判别式: 理论直线上点Q坐标为y= k(xi+1)+b;求s和t: s=y-yi=k(xi+1)+b-yi; t=(yi+1)-y=(yi+1)-k(xi+1)-b 计算判别式: Bresenham画线算法流程 本章讨论内容 直线生成算法 圆和圆弧的程序设计 区域填充算法 字符生成 反走样技术 圆的生成算法-中点圆生成算法 以单位间隔取样并在每个步长中确定离指定圆最近的像素位置。 对于给定半径r和屏幕中心(xc，yc)， 运用平移：先给出计算中心在坐标原点(0，0)圆的像素位置的算法，然后通过将xc加到x和yc加到y而把每个计算出的位置(x，y)移动到其适当的屏幕位置。 运用对称：在第一像限中，圆弧段从x=0到x=y，曲线的斜率从0变化到-1，因此，可以这八分圆上的正x方向取单位步长，并使用决策参数来确定每一步中两个可能的y位置中更接近于圆的位置，而后在其它七个八分圆中的位置可由对称性得到。 中点圆生成算法：算法原理 定义圆函数：fcircle(x，y) = x2+ y2－r2 ， 圆边界上任何具有半径r的点(x，y)满足方程fcircle(x，y)=0。 任何点(x，y)的相对位置可由对圆函数符号的检测来决定： fcircle(x，y)＜0，(x，y)位于圆边界内; fcircle(x，y)＝0，(x，y)位于圆边界上; fcircle(x，y)＞0，(x，y)位于圆边界外。 在中点算法中圆函数是决策参数，并且可像在画线算法中一样为这个函数设置增量运算。 决策参数是圆函数在这两个候选像素的中点处求值： Pk = fcircle(xk+1，yk-1/2)；根据决策参数判断： 假如pk＜0，这个中点在圆内，扫描线yk上的像素(高像素)接近圆边界。 假如pk0，中点位于圆外或在圆周边界上，选择扫描线yk-1的像素(低像素)。 中点圆生成算法：决策参数 下图示出了取样位置xk+1处两候选像素间的中点， 假设(xk，yk)为前一像素， 需要决定下列哪个像素：像素位置(xk+1，yk)，像素位置(xk+1，yk-1)更接近于圆？ 注意：圆在第一像限，△y0，y方向应取减量。 中点圆生成算法：生成过程 本章讨论内容 直线生成算法 圆和圆弧的程序设计 区域填充算法 字符生成 反走样技术 区域填充 区域是指一组相邻而又连通、具有相同属性的像素集。在区域内，生成某一属性的实心或图案的过程称为区域填充。 内点, 边界和外点:位于区域的点称为内点, 与内点相邻但又不属于该区域的像素组成了边界,不是内点和边界的像素是外点. 扫描线填充算法 按顺序计算扫描线与多边形的相交区域，用要求的颜色显示这些区间的像素，即完成填充工作。 填充过程，对于一条扫描线，可以分成四个步骤： 种子填充算法 基本思想:从区域内部已定义新值的某像素(种子)开始,有哪些信誉好的足球投注网站与该种子相邻且位于区域内的像素,该像素为新的种子；不断地递归有哪些信誉好的足球投注网站,逐个像素填充所需颜色,直到填充完区域边界内的所有像素为止。 连通区域定义 4连通区域： 任取区域内两点，在该区域内，允许通过上、下、左、右四个方向的运动，这两点相互可达。 8连通区域： 任取区域内两点，在该区域内，允许通过水平、垂直、两个对角线八个方向的运动，这两点相互可达。 连通区域定义 由定义可知：4连通区域也可以看作是8连通区域。但它作为4连通区