第3章 二维线画图元的生成

本章目标 如何绘制简单线画图元（点、线、圆等） 使用OpenGL的相关函数

主要内容 3.1 二维图形显示 3.2 扫描转换直线段 3.3 扫描转换圆弧 3.4 线画图元的属性 3.5 OpenGL相关函数

3.1 二维图形显示 图元的生成 是指完成图元的参数表示形式到点阵表示形式的转换。通常也称扫描转换图元(Scan Converter) 参数表示形式由图形软件包的使用者指定 点阵表示形式是光栅显示系统刷新时所需的表示形式 参数: p0，p1 点阵： 点图示法 区域图示法

3.1 二维图形显示 像素操作函数（画像素和读像素） 最基本的绘图函数 画（写）像素: SetPixel ( int x, int y, int color ) 读像素: int GetPixel ( int x, int y) 注意：具体的语言环境使用的函数名可能不同，这里的函数名仅用于课堂教学 坐标 原点 注意：屏幕坐标系统(GDI 默认） 为了方便表示，课堂上使用常用坐标系统。 OpenGL中的坐标系统可变化。 Y X O 课堂 采用

3.1 二维图形显示 用OpenGL实现读/写像素函数 3.1 二维图形显示 用OpenGL实现读/写像素函数 void SetPixel(int x, int y,float r, float g, float b ) { glColor3f(r,g,b); glBegin(GL_POINTS) glVertex2i(x,y); glEnd(); } float* GetPixel(int x, int y) float *rgb= new float[3]; glReadPixels(x,y,1,1,GL_RGB,GL_FLOAT,rgb); return rgb;

3.2 扫描转换直线段 扫描转换直线 约束 像素间均匀网格 整型坐标系 几点假设 求与直线段充分接近的像素集，并以此像素集替代原连续直线段在屏幕上显示 约束 像素间均匀网格 整型坐标系 几点假设 直线段为： 直线段的宽度为1 直线段的斜率 P1 P0

3.2.1 直线方程法 基本思想 直线方程 方法 根据直线的几何方程确定线段路径上的像素位置 M 表示斜率，b 表示 y 轴截距 3.2.1 直线方程法 基本思想 根据直线的几何方程确定线段路径上的像素位置 直线方程 M 表示斜率，b 表示 y 轴截距 方法 划分区间[x0, x1]: k0, k1,…, kn, ki+1=xi+1, 其中k0 = x0, kn= x1 计算纵坐标y：yi = mki + b 取整： 主要运算： 乘法+加法+取整 浮点运算

3.2.2 DDA算法 数字差分分析法DDA (Digital Differential Analyzer) 方法 程序：p45 主要运算 加法+取整 浮点运算

3.2.2 DDA算法 以下代码是否正确 void LineDDA(int x0,int y0,int x1,int y1,int color) { int x, dx, dy, y; float m; dx = x1 - x0; dy = y1 - y0; m = dy / dx; y = y0; for(x = x0; x <= x1; x++) y = (int)(y + 0.5); SetPixel(x, y, color); y += m; }

3.2.3 中点算法 目标 隐式方程 直线的正负划分性 消除DDA算法中的浮点运算 F(x, y) = ax + by + c = 0 式中 a = y0-y1= -y, b = x1-x0 = x, c = x0*y1 - x1*y0 直线的正负划分性 直线上方的点：F(x, y) ＞0 直线下方的点：F(x, y) ＜0 直线 上的点： F(x, y) ＝0

3.2.3 中点算法 问题：如何判断距直线最近的下一个像素点？ 根据可能所取点间的中点在直线的位置 构造判别式：d = F(M) = F(xp+1, yp+0.5) 由 d 的正和负可判定下一个像素。其中（xp , yp）为当前点坐标: d < 0，取NE；否则取E yi 表示实际坐标； yi, r 表示取整后的坐标； M是中点 p

3.2.3 中点算法 判定再下一个像素 d≥0，中点M在线段上方，取E d <0，中点M在线段下方，取NE 1）若d≥0，取正右方像素E，则判定下一个像素，得： d1 = F(xp+2, yp+0.5) = a(xp+2) + b(yp+0.5) + c = d + a， d的增量是a(即-y) 2）若d＜0，取右上方像素NE，则判定下一个像素，得： d2 = F(xp+2, yp+1.5) = d + a+b ， d的增量为a+b (即-(y-x)) d≥0，中点M在线段上方，取E d <0，中点M在线段下方，取NE p

3.2.3 中点算法 增量d的初始值 增量d的递推公式 d0=F(x0+1, y0+0.5)=F(x0, y0)+a+0.5b 因(x0, y0)在直线上，F(x0, y0)=0, 所以，d0 = a + 0.5b 增量d的递推公式 优化: 增量都是整数，只有初始值包含小数，可以用2d代替d， 2a改写成a + a 特点：算法中只有整数变量，不含乘除法，可用硬件实现 2d代替d

3.2.3 中点算法 MidpointLine(int x0,int y0, int x1,int y1,int color) /*x0<x1,y0<y1,0<=m<=1*/ { int a,b,d1,d2,d,x,y; a = y0 - y1; b = x1 – x0; d = a + a + b; d1 = a + a; d2 = (a + b) + ( a + b); x = x0; y = y0; SetPixel(x, y, color); while (x<x1) if (d<0) { y++; d += d2; } else d += d1; x++ ; SetPixel(x,y,color); } 递推公式 程序 教材更正，P47

3.2.3 中点算法 例3-1：直线段端点坐标 斜率m＝0.8; p0(20,10) 和p1(30,18) 3.2.3 中点算法 p1(30,18) 例3-1：直线段端点坐标 p0(20,10) 和p1(30,18) △x ＝ 30－20＝10； △y＝ 18－10=8 斜率m＝0.8; a = y0-y1 = -y = -8; b = x1-x0 = x = 10; d0 = 2a+b= -6； 2(a＋b）= 4 p0(20,10) i d （xi，yi） －6 （21，11） 1 －2 （22，12） 2 （23，12） 3 －14 （24，13） 4 －10 （25，14） 5 （26，15） 6 （27，16） 7 （28，16） 8 （29，17） 9 （30，18）

3.2.3 中点算法 例3-2：直线段端点坐标 斜率m＝2; p0(0, 0) 和p1(6,12) 3.2.3 中点算法 例3-2：直线段端点坐标 p0(0, 0) 和p1(6,12) △x ＝ 6－0＝6； △y＝ 12－0=12 斜率m＝2; a = y0-y1 = -y = -12; b = x1-x0 = x = 6; d0 = 2a+b= -18； 2(a＋b）= -12 i d （xi，yi） －18 （0，0） 1 －30 （1，1） 2 －42 （2，2） 3 -54 （3，3） 4 -66 （4，4） 5 -78 （5，5） 6 -90 （6，6）

3.2.3 中点算法 其它几种情况 Y m>1 m<-1 di<0时，y增1 m为无穷大 X 0>m>-1 di>0时，x增1

3.2.3 中点算法 Y m>1 m<-1 m为无穷大 di>0时，y减1 X 0>m>-1 di<0时，x增1

3.3 扫描转换圆弧 处理对象：圆心在原点的圆弧 圆的八对称性 其它情况如何考虑? 平移到原点，扫描转换后再平移到原位置 只需要扫描转换八 3.3 扫描转换圆弧 处理对象：圆心在原点的圆弧 其它情况如何考虑? 平移到原点，扫描转换后再平移到原位置 圆的八对称性 只需要扫描转换八 分之一圆弧即可

3.3 扫描转换圆弧 两种直接计算方法 离散点 离散角度 缺点：开平方，三角函数运算，计算量大，不可取

3.3.1 圆弧的中点算法 圆弧的正负划分性 圆弧外的点：F(x，y)＞0 圆弧内的点：F(x，y)＜0 圆弧上的点：F(x，y)＝0

3.3.1 圆弧的中点算法 第二个八分圆 特点： 第一象限的八分之一圆弧中x 的变化大于y的变化， 即圆弧上的切矢量斜率在0 ... -1间

3.3.1 圆弧的中点算法 问题：如何判断距圆弧最近的下一个像素点？ 隐函数 基本原理 F(x , y) = x2 + y2 - R2 = 0 切线斜率 -1 ≤ m ≤ 0 基本原理 点(xp, yp)下一点所取可能点间线段的中点 M = (xp+1, yp - 0.5) 当F(M)≤0时，M在圆内，说明E距离圆弧更近，取E； 当F(M)＞0时， M在圆外， 取SE p

3.3.1 圆弧的中点算法 构造判别式 d = F(M) = F(xp+1, yp-0.5) = (xp+1)2+(yp-0.5)2-R2 若d <= 0，取E， 再下一个像素的判别式为： d1 = F(xp+2, yp-0.5) = d+2xp+3， 沿正右方向，d 的增量为2xp+3 若d > 0，取SE， d2 = F(xp+2, yp-1.5) = d+(2xp+3)+(-2yp+2) 沿右下方向，d 的增量为2(xp-yp)+5 p

3.3.1 圆弧的中点算法 d 的初始值(在第一个像素(0, R)处) 递推公式 程序：p51－52 d0 = F(1, R-0.5) = 1.25 - R 算法中有浮点数，用h=4d H0＝5－4R 递推公式 程序：p51－52

3.3.1 圆弧的中点算法 消除乘法运算 P 令 递推公式

3.3.1 圆弧的中点算法 初始值 变量关系 x y H E SE x=x+1 H<=0 不变 H+E E+8 SE+8 H>0 H+SE SE+16

3.3.2 圆弧的多边形逼近法 两种方法 特点 正内接多边形迫近法 等面积正多边形迫近法 多边形边数足够多时接近圆 误差控制边数 显示多边形的边可用扫描转换直线段的中点算法来实现

3.3.2 圆弧的多边形逼近法 （1）正内接多边形迫近法 圆：x2 + y2 = R2 内接多边形顶点集： 令 pi 的幅角为 ，边的圆心角为 则有 是常数， ， 只在开始时计算一次所以，一个顶点只需4次乘法，共4n次乘法，外加直线段的中点算法的计算量

3.3.2 圆弧的多边形逼近法 问题：多少条边合适？ 给定最大逼近误差（最大 距离） d ，如何确定多边形的边数n或a？ R – Rcos(a/2) <= d cos(a/2) >= (R – d)/R a <= 2 arc cos (R – d)/R amax = 2 arc cos (R – d)/R n = 360 /a 即 n = 2π/ a

3.3.2 圆弧的多边形逼近法 例 教材更正 p59：alfa＝2*acos… p60：第一行添加 alfa =6.28/n; d = 20 d = 10 d = 5 d = 2 教材更正 p59：alfa＝2*acos… p60：第一行添加 alfa =6.28/n; p60 ：cos改成cosa sin改成sina

3.3.2 圆弧的多边形逼近法 （2）等面积正多边形迫近法 面积 步骤 正多边形的面积等于圆的面积 内接正多边形的面积小于圆的面积 求多边形边长，从而求所有顶点坐标值 由逼近误差值，确定边所对应的圆心角α

3.3.2 圆弧的多边形逼近法 求多边形径长|OP0|= |OPi| ，从而求所有顶点坐标值 （假定圆心角为） }d

3.3.2 圆弧的多边形逼近法 由逼近误差值d，确定边所对应的圆心角α }d

3.3.3 椭圆的中点算法* 基本思想 椭圆弧对称性与划分 与圆弧中点算法类似：确定一个像素后，接着用两个候选像素的中点计算一个判别式的值，由判别式的符号确定下一个像素点 椭圆弧对称性与划分 四部分 每部分组成 上部分 下部分 P点处切线斜率为-1 y x

3.3.3 椭圆的中点算法* 正负划分性 椭圆的方程： 隐函数方式： P点的坐标 椭圆弧上的法向量 椭圆弧上的切向量 切线斜率为－1的点满足

3.3.3 椭圆的中点算法* 正负划分性 b x a a>b F(x,y)<0 F(x,y)>0 F(x,y)=0

3.3.3 椭圆的中点算法* 先讨论椭圆弧的上部分 (xp, yp)下一个点所取两点连线的 中点坐标为(xp +1, yp-0.5) d1=F(xp +1, yp-0.5) = b2(xp +1)2+a2(yp-0.5)2－a2b2 根据d1的符号来决定下一像素是取正右方的那个，还是右上方的那个。 若d1＜0,中点在椭圆内，取正右方象素，判别式更新为： d1'=F(xp +2, yp-0.5)= d1 +b2(2 xp +3) d1的增量为b2(2 xp +3) 当d1≥0，中点在椭圆外，取右下方象素，更新判别式： d1'=F(xp +2, yp-1.5)= d1 +b2(2 xp +3)+a2(-2yp+2) d1的增量为b2(2 xp +3)+a2(-2 yp +2)

3.3.3 椭圆的中点算法* d1的初始条件 椭圆弧的下部分 椭圆弧起点为(0，b)，第一个中点为(1,b-0.5) 初始判别式：d10=F(1,b-0.5)=b*b+a*a(-b+0.25) 椭圆弧的下部分 下部分，下一象素可能是一正下方或右下方(x发生变化) d2 = F(xp+0.5, yp-1) = b2(xp+0.5)2+a2(yp-1)2-a2b2 若d2 <0,则d2’ = F(xp+1.5, yp-2) = d2 + b2(2xp+2) + a2(-2yp+3) 若d2 >=0,则d2’ = F(xp+0.5, yp-2) = d2 + a2(-2yp+3) d2 0 = F(X+0.5,Y-1) = b2(X+0.5)2+a2(Y-1)2-a2b2 下半部分弧的终止条件为 y = 0 (X,Y)为上部的终点

3.3.3 椭圆的中点算法* 程序 MidpointEllipe(int a, int b, int color) { int x,y; float d1,d2; x = 0; y = b; d1 = b*b +a*a*(-b+0.25); SetPixel(x,y,color); while( b*b*(x+1) < a*a*(y-0.5)) { if (d1<0) d1 +=b*b*(2*x+3); x++; } else { d1 +=(b*b*(2*x+3)+a*a*(-2*y+2)) x++; y--; } }//上部分 d2 = sqr(b*(x+0.5)) +sqr(a*(y-1)) – sqr(a*b); while(y >0) { if (d2 <0) { d2 +=b*b*(2*x+2)+a*a*(-2*y+3); x++; y--；} else {d2 += a*a*(-2*y+3); y--; } SetPixel(x,y,color); }

3.4 线画图元的属性 线画图元属性 线宽控制 控制外观，主要有线宽、线型和颜色 （1）像素复制： 方法：扫描转换时同时显示k（宽度）个像素 优点：实现简单 缺点： ①线段两端要么为水平的， 要么是竖直的

3.4 线画图元的属性 缺点： ②折线顶点处有缺口 ③图元的宽度不均匀 ④产生宽度为偶数像素的图元效果不好（没有中心，缺少对称性）

3.4 线画图元的属性 （2）移动刷子 方法：将宽度为指定线宽的刷子的中心沿直线移动 缺点：重复绘制部分像素

3.4 线画图元的属性 （3）利用填充图元 方法：绘制出边界，再在内部填颜色 优点：生成的图形质量高 缺点： ①计算量大 ②有些图形的等距线难以获得

3.4 线画图元的属性 线型控制 1 1 1 1 0 0 1 1 1 1 0 0 1 1 1 1 0 0 显示4个像素后空2个像素的点划线 包括：实线、虚线和点划线 扫描转换时通过绘制像素段来显示线型属性 实现时采用掩码(Mask)中的位控制像素是否绘制 一般位长为16位 如： 1 1 1 1 0 0 1 1 1 1 0 0 1 1 1 1 0 0 显示4个像素后空2个像素的点划线

3.5 OpenGL相关函数 坐标系：gluOrtho2D(xmin, xmax,ymin,ymax) (Xmax, Ymax) 函数设定屏幕显示窗口的二维笛卡儿坐标系 同时gluOrtho2D指定投影方式为正交投影 正交投影是一种投影变换（直接去掉一个坐标分量），采用矩阵运算，因此初始状态要设矩阵为单位矩阵 使用方法，一般在初始化OpenGL时调用，应用程序窗口大小发生变化时也需要调用 glMatrixMode(GL_PROJECTION); glLoadIdentity(); gluOrtho2D(xmin, xmax,ymin, ymax); (Xmax, Ymax) Viewport 参数为绝对坐标，图元坐标超出部分将不显示 (Xmin, Ymin)

3.5 OpenGL相关函数 例3-5-1 #include <gl/glut.h> int iWindowWidth=300,iWindowHeight=300; void init (void) { glClearColor (1.0, 1.0, 1.0, 0.0); glMatrixMode(GL_PROJECTION); glLoadIdentity(); gluOrtho2D(-iWindowWidth/2, iWindowWidth/2, -iWindowHeight/2, iWindowHeight/2); } void keyboard(unsigned char key, int x, int y) { switch (key) { case 27://ESC键 exit(0); break; }

3.5 OpenGL相关函数 void Reshape(int width, int height)//改变窗口大小 { glViewport(0, 0, width, height); glMatrixMode(GL_PROJECTION); glLoadIdentity(); gluOrtho2D(-width/2, width/2, -height/2, height/2); glMatrixMode(GL_MODELVIEW); glClear (GL_COLOR_BUFFER_BIT); iWindowWidth = width; iWindowHeight = height; }

3.5 OpenGL相关函数 void display (void) { glClear (GL_COLOR_BUFFER_BIT); //绘制坐标系 glLineWidth(2); glColor3f (0.0, 0.0, 0.0); glBegin(GL_LINES); glVertex2i(iWindowWidth/2-5,0); glVertex2i(-iWindowWidth/2+5,0);//X glVertex2i(iWindowWidth/2-20,5); glVertex2i(iWindowWidth/2-5,0);//Arrow glVertex2i(iWindowWidth/2-5,0); glVertex2i(iWindowWidth/2-20,-5); glVertex2i(0,iWindowHeight/2-5); glVertex2i(0,-iWindowHeight/2+5);//Y glVertex2i(-5,iWindowHeight/2-20); glVertex2i(0,iWindowHeight/2-5);//Arrow glVertex2i(0,iWindowHeight/2-5);glVertex2i(5,iWindowHeight/2-20); glEnd(); glPointSize(10);//Centre glBegin(GL_POINTS); glColor3f(1,0,0); glVertex2i(0,0); glFlush(); }

3.5 OpenGL相关函数 int main(int argc, char** argv) { glutInit(&argc, argv); glutInitDisplayMode (GLUT_RGB); glutInitWindowSize (250, 250); glutInitWindowPosition (300, 300); glutCreateWindow ("Demo"); init(); glutDisplayFunc(display); glutKeyboardFunc(keyboard); glutReshapeFunc(Reshape); glutMainLoop(); return 0; }

3.5 OpenGL相关函数 图元绘制 指定图元的类型（glBegin(type)指定） 定义顶点（坐标glVertex，颜色glColor等） 结束（glEnd()） 编码方法 glBegin(type); glVertex*(); //指定顶点坐标1 glVertex*(); //指定顶点坐标2 ┆ glEnd()；

3.5 OpenGL相关函数 type类型 类型 说明 GL_POINTS 单个顶点集 GL_LINES 多组双顶点线段 GL_POLYGON 单个简单填充凸多边形 GL_TRIANGLES 多组独立填充三角形 GL_QUADS 多组独立填充四边形 GL_LINE_STRIP 不闭合折线 GL_LINE_LOOP 闭合折线 GL_TRIANGLE_STRIP 线型连续填充三角形串 GL_TRIANGLE_FAN 扇形连续填充三角形串 GL_QUAD_STRIP 连续填充四边形串

3.5 OpenGL相关函数 画点 glBegin中的参数为GL_POINTS glVertex的后缀组成 n (i|s|f|d) {v} 例: (1)glBegin(GL_POINTS) (2)int point1[]={50,100}; glVertex2i(50,100); int point2[]={750,150}; glVertex2i(75,150); int point2[]={100,200}; glVertex2i(100,200); glBegin(GL_POINTS) glEnd(); glVertex2iv(point1); ┆

3.5 OpenGL相关函数 点的属性 颜色函数 (1) glColor(3|4)(b|d|f|i|s|ub|ui|us)(TYPE r,TYPE g,TYPE b ) (2) glColor(3|4)(b|d|f|i|s|ub|ui|us)v(TYPE *rgb ) 其中：u表示无符号 RGB色立方体 颜色模式：RGB(RGBA)和颜色表模式 大小：glPointSize（GLfloat size）

3.5 OpenGL相关函数 画线 glBegin中的参数为：GL_LINES、GL_LINE_STRIP、 GL_LINE_LOOP 例：顶点序列p1,p2,p3,p4,p5 glBegin(GL_LINES) glVertex2iv(p1); glVertex2iv(p2); glVertex2iv(p3); glVertex2iv(p4); glVertex2iv(p5); glEnd(); GL_LINE_STRIP GL_LINE_LOOP GL_LINES

3.5 OpenGL相关函数 线的属性 颜色：由点的颜色决定 宽度：glLineWidth（GLfloat width ） 只能用在glBegin之前，不能用在glBegin和glEnd之间 线型：void glLineStipple(GLint factor, GLushort pattern); 使用前需要激活：glEnable(GL_LINE_STIPPLE); pattern: 16位掩码 factor：每位重复次数

3.5 OpenGL相关函数 程序:(绘制回调函数) GLfloat y; // Storage for varying Y coordinate GLint factor = 1; // Stippling factor GLushort pattern = 0x31df;//f38d; // Stipple pattern glEnable(GL_LINE_STIPPLE); glLineWidth(2); for(y = 30.0f; y < 190.0f; y += 20.0f) { // Reset the repeat factor and pattern glLineStipple(factor ,pattern); // Draw the line glBegin(GL_LINES); glVertex2f(80.0f, y); glVertex2f(240.0f, y); glEnd(); factor++; }

小结 扫描转换的概念 直线的扫描转换算法 DDA算法 中点算法 圆弧的扫描转换算法 逼近算法 图元属性表示 OpenGL基本绘制图元函数

作业 （1）比较直线段扫描转换三种算法中的运算特点。 （2）根据抛物线 的正负性和对称性，当y∈[-24，24]时，推导中点算法中的判别式。

上机题一 简单图形编辑系统 功能 要求 (1)面向对象程序设计语言 (2)构建简单几何对象类（点、线和多边形等） (3)定义合适的文件格式 绘制：直线段、多边形、圆等简单二维图形 处理：裁剪和变换 交互：参数由鼠标或键盘输入；选中并修改图形 存贮：图形数据可以保存到文件中，并能读文件 要求 (1)面向对象程序设计语言 (2)构建简单几何对象类（点、线和多边形等） (3)定义合适的文件格式 (4)交互方式要通用化