基本图元生成

1、Computer Graphics 计算机图形学第二章 基本图元的生成四、线型与线宽处理 1、线型处理 实际应用中，经常使用指定线型和线宽的直线或弧线。如虚线、点划线等，以便区分各种不同的意义。如采用实线表示立体线框中可见的轮廓线，用虚线表示不可见的轮廓线，用点划线表示中心线等。 可采用像素段方法实现。即程序沿线的路径输出连续像素段，每个像素段之间是空白。 线型用一个布尔值的数组（像素模板）来存放。例如，用一个18位整数可以存放18个布尔值，用这样的整数存放线型定义时，线型必须以18个象素为周期进行重复。 1 1 1 1 0 0 1 1 1 1 0 0 1 1 1 1 0 0将写像素语句put

2、pixel(x,y,color)更改为：if (位串i%18) putpixel(x,y,color) 其中i为循环变量，每处理一个象素递增1。缺点： 采用固定划线长度的实现方法会在不同直线方向上产生出不等长的划线段。原因在于相同个数的象素沿不同方向将生成不同长度的线段。解决方法： 为实现精确的线型定义，应按照直线的斜率调整线型定义数组中实线段和空白段的象素数目。 或对象素形成的线段的长度进行记录，按长度进行处理，不按象素的个数进行处理。 另一种精确定义线型的方法是：将线上的每一段实划线作为一段单独的线段，定位其始末端点坐标，再调用直线的扫描转换算法实现绘制。2、线宽处理线宽选择的实现取决于输

3、出设备的能力。线刷子、方刷子。 线刷子 生成具有一定宽度的直线，可以沿着生成直线时获得的像素点，通过移动一把具有 一定宽度的“线刷子”来实现。 假设直线斜率在-1，1之间，可把线刷子定成垂直方向，并将线刷子中心点对准直线上某一像素点，然后将线刷子沿直线运动就刷出了一条具有一定宽度的直线。 当直线斜率不在-1，1之间时，只需把线刷子运动方向改为水平方向即可。垂直刷(a)(b)水平刷水平线刷子的实现LineBrush (int x,int y,int color) putpixel(x,y,color); putpixel(x+1,y,color); putpixel(x-1,y,color);

4、putpixel(x+2,y,color); putpixel(x-2,y,color); putpixel(x-3,y,color); putpixel(x+3,y,color); 线刷子的特点：实现简单、效率高。斜线与水平(或垂直)线粗细不均匀。当线宽为偶数个象素时，线的中心将偏移半个象素。利用线刷子生成线的始末端总是水平或垂直的，看起来不太自然，在两条直线的连接处会产生缺口；解决：添加“线帽（line cap）” 当比较接近水平的线与比较接近垂直的线汇合时，汇合处外角将有缺口。 线刷子产生的缺口解决：斜角连接（miter join）圆连接（round join）斜切连接（bevel jo

5、in） 线刷子产生的缺口(a)斜角连接(b)圆连接(c)斜切连接方刷子： 把边宽为指定线宽的正方形的中心沿直线平行移动，即可获得具有线宽的线条。 实现正方形刷子最简单的办法是：把正方形中心对准单象素宽的线条上各个元素，并把正方形内的象素全部置成线条颜色。这种简单方法将重复地写象素。这是因为相邻两象素的方形一般会重叠。 方刷子方刷子的特点：简单，容易实现。效率低。线的末端总是水平或垂直的；在两条直线的连接处会产生缺口；宽度不均匀；宽度为偶数时无法实现。方刷子绘制的线条自然地带有一个“方线帽”方刷子的实现：SquarBrush (int x,int y,int color)putpixel(x,y

6、,color); putpixel(x+1,y,color); putpixel(x-1,y,color); putpixel(x+1,y+1,color); putpixel(x-1,y+1,color); putpixel(x+1,y-1,color); putpixel(x-1,y-1,color); putpixel(x,y-1,color); putpixel(x,y+1,color); 为了避免重复写象素，可以采用与活性边表类似的技术，为每条扫描线建一个表，存放该扫描线与线条的相交区间左右端点位置，在每个象素使用正方形刷子时，用该方形与扫描线的相交区间端点坐标去更新原表内端点数据。

7、其它线宽处理方式区域填充改变刷子形状：封闭图形即实面积图形 (或有界表面)，在其封闭的面积上(轮廓内)具有相同的亮度或色彩。实面积图形既能描述物体的几何轮廊，还能表现物体的表面色彩。更为重要的是实面积图形还是描述三维物体、三维真实感图形的显示基础，它对今后学习三维图形学帮助极大。 五、区域填充 根据表示多边形的方法不同，实面积图形的生成可分为两大类。 第一类叫多边形的填充，即用多边形的顶点坐标数据来描述定义(简称实面积图形的图形表示法)，在其封闭的多边形内部填充用户指定的颜色； 第二类叫种子填充，即用点阵方式描述定义实面积图形，这个图形的实面积由用户指定的点阵颜色包围或组成(简称实面积图形的图

8、像表示法)，在图形的实面积上填充用户指定的颜色，其中这个指定的第一个填充点又称为种子。 有关概念 区域：一组相邻而且又相连的像素，而且具有相同属性的封闭区域。 种类：单域 复合域 多边形 多边形是一个由折线段组成的封闭图形，它由有序顶点的点集Vi(i=1n)及有向边的线集Ei定义。n为多边形的顶点数或边数，且Ei=ViVi+1，i=1，2，n。这里Vn+1=V1，用以保证多边形的封闭性。当用多边形来表示有界平面或实面积图形的边界时，规定多边形每条有向边的左侧为实面积区域(或内部区域)，因此它不允许多边形的边线自相交叉(见图)。V1V3V4V2V7V6V5V4V3V2V1V8多边形的表示： 顶点

9、表示；点阵表示 环 因为多边形的有向边线左侧为其实面积区域，故沿外轮廓线的顶点方向顺序环行时，要求该多边形顶点的整个环行方向逆时针旋转；而沿其内轮廓线顶点方向顺序环行时，要求该多边形顶点的整个环行方向顺时针旋转。这种定义了环行方向的多边形称为环。前者为外环、后者为内环(见图)。 多边形的外环、内环定义方向示意图 区域的建立（定义）方式： 内定区域：在所定义的区域内所有的像素具有相同的属性（如颜色等）。 （内部定义方式） 边界定义区域：区域以边界的属性来划分，区域内的像素和边界上的像素可具有不同的属性。 （外界定义方式）连通性：分为四向连通和八向连通。 四连通：各像素在水平、垂直的上、下、左、右

10、四个方向上是连通的。 八连通：各像素在上、下、左、右以及四个对角线方向都是连通的。2、逐点判断填充算法区域填充的基本(初级)方法:逐点判断填充算法逐点判断绘图窗口内的每一个像素；若在区域的内部：用指定的属性设置该点；否则不予处理；设有如下函数： True when x DInside(D,x,y)= False when x DD取矩形R(x1xx2,y1yy2)，使R包围D，则逐点判断填充算法如下：for(y=y1;y=y2;y+) for(x=x1;x=x2;x+) if(inside(D,x,y) putpixel(x,y,color);上述算法原理简单、实用，但效率低； 效率低的原因是

11、没有考虑各象素之间的联系，孤立地考察象素与区域的关系，使得几十万甚至几百万个象素都要一一判别，每次判别又要多次求交点，需要做大量的乘除运算，花费很多时间。 如何判断点在多边形的内或外？（包含性检查的方法）射线法；累计角度法；编码法(1)射线法 从被监测点V点出发射线，与多边形边相交，若交点个数偶数，V点在外边，反之在内部。当射线经过顶点时，可通过”左开右闭”，或”上开下闭”进行处理。PP奇异情况处理： 当射线穿过的顶点两边在射线两侧，此时认为相交一次。而在同侧时，则认为相交两次。ABCDE12P(2) 累计角度法ABCDE 从v点向多边形P顶点发出射线，形成有向角，计算有相交的和，通过像素的值

12、定义区域内部，又称基于像素的区域填充。基于像素的区域填充一是内定义法，就是指出区域内部所有像素值；边界定义法，即区域边界定义相应值，指出区域内部。种子填充算法假设在多边形内有一象素已知，由此出发利用连通性找到区域内的所有象素，并进行填充。3.种子填充算法 从已知种子点出发，每填充一点，在其周围寻找新种子点，重复进行，直到再无未填充的点为止。 针对内点表示法的4连通区域的递归填充具体步骤: 1.种子入栈. 2.当栈非空时,进行下面的操作,否则结束. 3.栈顶元素出栈,如果是未填充的内部点,则将其填充. 继续考察与其连通的点,若是未填充的内部点,则该点入栈.返回2.1）深度递归的种子填充算法(漫水

13、法） 设（x,y）为内点表示的4连通区域内的一点，oldcolor为区域的原色，要将整个区域填充为新的颜色newcolor。 内点表示法的4连通区域的递归填充算法:用函数的递归调用来实现内点表示法void FloodFill (int x,int y,int oldcolor,int newcolor) if(getpixel(x,y)=oldcolor) putpixel(x,y,newcolor); FloodFill (x,y+1,oldcolor,newcolor); FloodFill(x,y-1,oldcolor,newcolor); FloodFill(x-1,y,oldcolo

14、r,newcolor); FloodFill(x+1,y,oldcolor,newcolor); #includevoid floodfill4(int x,int y,int oldcolor,int newcolor) if(getpixel(x,y)=oldcolor) putpixel(x,y,newcolor); delay(20000); floodfill4(x,y+1,oldcolor,newcolor); floodfill4(x,y-1,oldcolor,newcolor); floodfill4(x-1,y,oldcolor,newcolor); floodfill4(x

15、+1,y,oldcolor,newcolor); main() int a,b,c,d,i,j; int graphdriver=DETECT, graphmode=0; initgraph(&graphdriver,&graphmode, ); cleardevice(); setcolor(14); rectangle(100,100,150,150); for(i=101;i150;i+) for(j=101;j150;j+) putpixel(i,j,4); delay(1000); a=120; b=110; c=4; d=2; floodfill4(a,b,c,d); getch(

16、); closegraph(); void BoundaryFill (int x,int y,int boundarycolor,int newcolor) int color= Getpixel(x,y); if(color!=newcolor & color!=boundarycolor) putpixel(x,y,newcolor); BoundaryFill (x,y+1, boundarycolor,newcolor); BoundaryFill (x,y-1, boundarycolor,newcolor); BoundaryFill (x-1,y, boundarycolor,

17、newcolor); BoundaryFill (x+1,y, boundarycolor,newcolor); 边界表示的4连通区域的递归填充算法:#include;#include;void BoundaryFill4(int x,int y,int boundarycolor,int newcolor) if(getpixel(x,y)!=boundarycolor&getpixel(x,y)!=newcolor) putpixel(x,y,newcolor); delay(20000); BoundaryFill4(x,y+1,boundarycolor,newcolor); Boun

18、daryFill4(x,y-1,boundarycolor,newcolor); BoundaryFill4(x-1,y,boundarycolor,newcolor); BoundaryFill4(x+1,y,boundarycolor,newcolor); main() int a,b,c=14,d,i,j; int graphdriver=DETECT,graphmode=0; initgraph(&graphdriver,&graphmode, ); cleardevice(); setcolor(c); rectangle(100,100,150,150); for(i=101;i1

19、50;i+) for(j=101;j i结点的x值递增D x； 若允许多边形的边自相交，则用冒泡排序法对AET表重新排序； 遍历AET表，把配对交点区间(左闭右开)上的象素(x, y)，用drawpixel (x, y, color) 改写象素颜色值； /* polyfill */基本思想： 对于每条边上的每一点都将所在扫描线上其右方的所有象素的颜色取补。 算法简单，但对于复杂图型，每一象素可能被访问多次。5、边填充算法(正负相消法)求余运算：假定A为一个正整数，则M的余定义为A M, 记为 。计算机中取A为n位能表示的最大整数。即，A=0 xFFFFFFFF由来：光栅图形中，如果某区域已着上

20、值为M的颜色值做偶数次求余运算，该区域颜色不变；而做奇数次求余运算，则该区域颜色变为值为 的颜色。这一规律应用于多边形扫描转换，就为边缘填充算法。算法基本思想：对于每条扫描线和每条多边形边的交点，将该扫描线上交点右方的所有象素取余。1、将当前扫描线上的 所有象素着上 颜色；2、求余：for(i = 0;i = m; i+)在当前扫描线上， 从横坐标为Xi的交 点向右求余； 算法1（以扫描线为中心的边缘填充算法）1、将绘图窗口的背景色置为 ；2、对多边形的每一条非水平边做：从该边上的每个象素开始向右求余；算法2（以边为中心的边缘填充算法）适合用于具有帧缓存的图形系统。处理后，按扫描线顺序读出帧缓存的内容，送入显示设备。优点：算法简单缺点：对于复杂图形，每一象素可能被访问多次，输入/输出的量比有序边表算法大得多引入栅栏，以减少填充算法访问象素的次数。栅栏：与扫描线垂直的直线，通常过一顶点，且把多边形分为左右二半。基本思想：扫描线与多边形的边求交，将交点与栅栏之间的象素取补。减少了象素重复访问数目，但不彻底。6、栅栏填充算法 基本思想：在帧缓冲器中对多边形的每条边进行直线扫描转换，亦即对多边形边