计算机图形学

上课时间：2-12周周二上午1/2/3节。

【Lesson1】9月15日

这堂课讲了第1/2/3章节

• 第一章 概述
• 第二章 计算机图形硬件系统
• 第三章 图形标准

第一章 概述

1.1 定义

计算机图形学是研究怎样用计算机生成、处理和显示图形的一门学科。

计算机图形学的基本含义是 使用计算机通过算法和程序在显示设备上构造出图形来。

1.2 发展历史

• 五十年代：第一台图形显示器；被动式图形学；末期，具有指挥和控制功能的CRT显示器，交互式图形学诞生。
• 六十年代：“Computer Graphics”术语诞生；Coons方法（超限插值）；Bézier曲线、曲面。
• 七十年代：光栅显示器产生，光栅图形学算法发展，区域填充、裁剪、消隐。真实感图形学和实体造型技术：光反射模型（漫反射＋环境光）；“漫反射模型＋插值”思想；简单光照模型-Phong模型。
• 八十年代：光透射模型-Whitted模型；引入辐射度方法，模拟理想漫反射表面间多重反射；超大规模集成电路迅猛发展。

1.3 相关学科

计算几何、计算机图形学、图形处理、计算机视觉

1.4 研究内容

图像硬件、图形标准、图形交互技术、光栅图形生成算法、曲线曲面造型、实体造型、真实感图形计算与显示、科学计算可视化、计算机动画、自然景物仿真、虚拟现实

1.5 应用领域

计算机辅助设计与制造（CAD/CAM）、科学计算可视化、虚拟现实、图形用户接口（GUI）、计算机艺术、地理信息系统（GIS）

第二章 计算机图形硬件系统

2.1 系统组成

2.2 图像处理器

又称为显卡，主要由主芯片（GPU）、显示缓存和数字模拟转换器（DAC）三部分组成。

• GPU：对输入图形指令进行构建和渲染，将结果存入显存。
• 显存：存储图形运算中间信息。
• DAC：把二进制数字转换成为和显示器相适应的模拟信号。

2.3 显示器

（1）种类发展：

• 扫描显示器：体积大、有辐射
  – 基于阴极射线管(CRT Cathode－Ray Tube)的监视器
  – 随机扫描系统 VS 光栅扫描系统
  – 彩色显示器

• 液晶显示器：体积小，无辐射。
• LED显示器：点距较大，只适合大屏幕显示。

（2）性能属性：刷新率、像素、分辨率
（3）真彩色：24位，1600万色
（4）假彩色：8位，查表显示

第三章 图形标准

3.1 目的

建立图形标准的目的是使得图形与计算机硬件、软件系统无关，实现

• 应用程序接口：程序可移植
• 图形数据交换：数据可交换

3.2 应用程序接口标准

• 1985，GKS（Graphics Kernel System）
  – ISO颁布
  – 提供应用程序与图形输入输出设备之间的功能接口，后又开发出了GKS-3D
• 1986，PHIGS（Programmer’s Hierarchical Interactive Graphics System）
  – ISO颁布
  – 同样在程序和图形设备之间提供一种功能接口，但具有高度动态性、交互性，描述、修改和显示图形更加高效迅速。

3.3 图形数据交换标准

• 1987，CGM（Computer Graphic Metafile）
  – ANSI与ISO成立共同制定
  – 提供在虚拟设备接口上存储和传输图形数据和控制信息的机制，是一套与设备无关的标准。
• windows 图元文件
  – 用来表示矢量图形的二进制记录。
• 1981，IGES（Initial Graphics Exchange Specification）
  – NBS主持、波音与通用电气参加制订
  – 功能丰富，包括实体模型与边界模型
• DXF（Drawing Exchange Format）
  – 由于AutoCAD系统的普遍应用，成为事实上的数据交换标准
• STEP（Standard for the Exchange of Product Model Data）
  – ISO制订
  – 描述了商品的全生命周期（设计、制造、使用、维护、报废等），弥补IGES不能满足复杂工业生产数据交换的缺点

OpenGL

（1）简介
是目前实际上的底层图形应用程序接口标准。
（2）API结构

（3）有关库函数

• 核心库（OpenGL）
  – 前缀：gl
  – 常规的、核心的图形处理。
• 实用库（OpenGL utility library，GLU）
  – 前缀：glu
  – 高级函数功能：复杂曲线曲面、高级坐标变换、多边形分割
• 实用工具包（OpenGL Utility Toolkit）
  – 前缀：glut
  – 第三方开发函数库：简单窗口操作、消息处理
• WGL函数
  – 前缀：wgl
  – 专门用于OpenGL与Windows窗口系统的联接
  – 还包括一些对Win32系统的扩展

【Lesson 2】9月28日

第四章 从图形到图像

4.1 图形图像的关系

图形：

• 矢量表示，是几何学对客观时间的建模
• 包含坐标、拓扑、颜色、纹理等等几何或非几何信息
• 与设备无关

图像：

• 点阵表示，只包含每个点的颜色信息
• 在定义域和值域上都不连续

4.2 直线生成算法

（1）数值微分法（DDA：Digital Differential Analyzer）
对于 ( x 0 , y 0 ) , ( x n , y n ) (x_0,y_0),(x_n,y_n) (x0​,y0​),(xn​,yn​) 两点确定的直线
y − y 0 y n − y 0 = x − x 0 x n − x 0   ⇒   y i = k x i + b \frac{y-y_0}{y_n-y_0}=\frac{x-x_0}{x_n-x_0}\ \Rightarrow\ y_i=kx_i+b yn​−y0​y−y0​​=xn​−x0​x−x0​​ ⇒ yi​=kxi​+b
屏幕上显示的点为
( x 0 , y 0 ) , ( x 1 , i n t ( y i + 0.5 ) ) , . . . , ( x n − 1 , i n t ( y n − 1 ) ) , ( x n , y n ) (x_0,y_0),(x_1,{\rm int}(y_i+0.5)),...,(x_{n-1},{\rm int}(y_{n-1})),(x_n,y_n) (x0​,y0​),(x1​,int(yi​+0.5)),...,(xn−1​,int(yn−1​)),(xn​,yn​)

（2）Bresenham算法
当 ∣ k ∣ ≤ 1 |{\rm k}|{\leq}1 ∣k∣≤1 时， x x x 每增加一个步长， y y y 增加不到一个步长，
令 e 0 = − 0.5 , e i + 1 = e i + k e_0=-0.5,e_{i+1}=e_{i}+k e0​=−0.5,ei+1​=ei​+k，
若 e i + 1 ≥ 0 e_{i+1}{\geq}0 ei+1​≥0，则 y i + 1 = y i + 1 , e i + 1 = e i + 1 − 1 y_{i+1}=y_i+1,e_{i+1}=e_{i+1}-1 yi+1​=yi​+1,ei+1​=ei+1​−1；
{\quad}{\quad}{\quad}{\quad} 否则 y i + 1 = y i y_{i+1}=y_i yi+1​=yi​

Bresenham算法的整型化
在上述推导中
e i + 1 = e i + k = e i + y n − y 0 x n − x 0 2 ∗ ( x n − x 0 ) ∗ e i + 1 = 2 ∗ ( x n − x 0 ) ∗ e i + ( y n − y 0 ) e_{i+1}=e_i+k=e_i+\frac{y_n-y_0}{x_n-x_0}\\ 2*(x_n-x_0)*e_{i+1}=2*(x_n-x_0)*e_i+(y_n-y_0)\\ ei+1​=ei​+k=ei​+xn​−x0​yn​−y0​​2∗(xn​−x0​)∗ei+1​=2∗(xn​−x0​)∗ei​+(yn​−y0​)
令 E 0 = − ( x n − x 0 ) ， E i = 2 ∗ ( x n − x 0 ) ∗ e i E_0=-(x_n-x_0)，E_i=2*(x_n-x_0)*e_i E0​=−(xn​−x0​)，Ei​=2∗(xn​−x0​)∗ei​，式子可简化为
E i + 1 = E i + 2 ∗ ( y n − y 0 ) E_{i+1}=E_i+2*(y_n-y_0) Ei+1​=Ei​+2∗(yn​−y0​)
当 E i + 1 ≥ 0 E_{i+1}{\geq}0 Ei+1​≥0 时， E i + 1 = E i − 2 ∗ ( x n − x 0 ) E_{i+1}=E_i-2*(x_n-x_0) Ei+1​=Ei​−2∗(xn​−x0​)

4.3 圆的生成算法(中点画圆法)

使用函数 F ( x , y ) = x 2 + y 2 − r 2 F(x,y)=x^2+y^2-r^2 F(x,y)=x2+y2−r2 来判断某点是否在圆内。

以画第一象限的上半1/8圆弧为例，
设圆的最顶点为 ( x p , y p ) (x_p,y_p) (xp​,yp​)，其右边一列上下两个像素的中点 M M M为 ( x p + 1 , y p − 0.5 ) (x_p+1,y_p-0.5) (xp​+1,yp​−0.5)，用该点的函数值 F ( x m , y m ) F(x_m,y_m) F(xm​,ym​)，决定显示哪一个点。
① F ( x m , y m ) < 0 F(x_m,y_m)<0 F(xm​,ym​)<0， ( x p + 1 , y p ) (x_p+1,y_p) (xp​+1,yp​) 为下一像素点，再下一个像素取决于
F ( x p + 2 , y p − 0.5 ) = F ( x p + 1 , y p − 0.5 ) + 2 x p + 3 F(x_p+2,y_p-0.5)=F(x_p+1,y_p-0.5)+2x_p+3 F(xp​+2,yp​−0.5)=F(xp​+1,yp​−0.5)+2xp​+3

② F ( x m , y m )   ≥   0 F(x_m,y_m)\ {\geq}\ 0 F(xm​,ym​) ≥ 0， ( x p + 1 , y p − 1 ) (x_p+1,y_p-1) (xp​+1,yp​−1) 为下一像素点
F ( x p + 2 , y p − 1.5 ) = F ( x p + 1 , y p − 0.5 ) + 2 ( x p − y p ) + 3 F(x_p+2,y_p-1.5)=F(x_p+1,y_p-0.5)+2(x_p-y_p)+3 F(xp​+2,yp​−1.5)=F(xp​+1,yp​−0.5)+2(xp​−yp​)+3
绘制1/8圆的伪代码

MidCircle18(int r)
{
	int x,y;
	float f;
	x = 0; y = r; f = 1.25-r;
	while(x<=y){
		point(x,y);
		if(f<0) f+=2*x+3;
		else {f+=2*(x-y)+5;y--;}
		x++;
	}
}

4.4 多边形的扫描转换

多边形分为凹多边形、凸多边形、含内环的多边形，其中外环要逆时针给，内环要顺时针给。

扫描线算法

• 求交：扫描线与多边形各边交点
• 排序：按 x x x 递增排序所有交点（存放在一个链表中）
• 配对：奇偶交点配对，代表相交区间
• 着色：相交区间内像素置为多边形颜色

活性边：为提高效率，处理一条扫描线时，仅对与它相交的多边形的边进行求交运算，称为活性边。

活性边表：将活性边按 x x x 坐标递增顺序存放在一个链表 NET[i]中，称为活性边表NET。

每条扫描线的X增量是斜率的倒数

算法过程：

void polyfil(polygon, color)
{
	构造新边表NET[i]；
	y = 最低扫描线号；
	初始化活性边表为空；
	对各条扫描线，执行
	{
		把新表边NET[i]中的边结点插入AET表，按x坐标递增顺序排列；
		将AET表中的边奇偶为区间，对区域内像素着色；
		检查AET表，把y_max=i的结点从AET表中删除，其他边的x交点坐标按增量递增；
	}
}

原则：不遗漏点，无重复点

措施：

• 新加入边时，考虑退出边。
• 适当进行区间合并
• 水平边不参与计算。

4.4.1 OpenGL对光栅化的处理

OpenGL在子像素级上进行光栅化，将直线图元视为数学直线，填充图元视为数学直线包围的区域，窗口坐标视为笛卡尔网格，每个网格对应屏幕上一个像素。

• 点图元在像素边界内，光栅化该点。
• OpenGL一般不生成线段的第二个顶点，避免一个像素绘制两次。
• 画填充图元时，像素中心位于图元数学边界内才绘制，避免不重叠的填充图元共享一条边时相同图元不会绘制两次。

4.4.2 光栅图像的区域填充

区域填充：赋予区域内一点指定颜色，然后将改颜色扩展到整个区域的过程。

• 两种表示形式：内点表示（区域所有像素同色）、边界表示（边界点同色）
• 两种区域联通：4向连通区、8向连通区

（1）区域填充的递归算法

内点表示的4连通区域递归填充算法

void FloodFill4(x, y, oldcolor, newcolor){
	int x, y;
	COLOR oldcolor, newcolor;
	if(getpixel(x,y)==oldcolor){
		drawpixel(x,y,newcolor);
		FloodFill4(x,y+1,oldcolor,newcolor);
		FloodFill4(x,y-1,oldcolor,newcolor);
		FloodFill4(x-1,y,oldcolor,newcolor);
		FloodFill4(x+1,y,oldcolor,newcolor);
	}
}

边界表示的4连通区域递归填充算法

void BoundaryFill4(x, y, edgecolor, newcolor){
	int x, y;
	COLOR edgecolor,newcolor;
	COLOR color = getpixel(x,y);
	if(color!=newcolor && color!=edgecolor){
		drawpixel(x,y,newcolor);
		BoundaryFill4(x,y+1,edgecolor,newcolor);
		BoundaryFill4(x,y+1,edgecolor,newcolor);
		BoundaryFill4(x,y+1,edgecolor,newcolor);
		BoundaryFill4(x,y+1,edgecolor,newcolor);
	}
}

（2）区域填充的扫描线算法

递归算法的算法原理和程序都很简单，但是递归太多，效率不高。

扫描线算法基本过程：

• 给定种子 ( x , y ) (x,y) (x,y) ，首先填充种子点所在扫描线上的位于给定区域的一个区段。
• 然后确定与这一区段相连通的上下两条扫描线上位于给定区域内的区段。

实现步骤

• （1）初始化：堆栈置空，将种子点 ( x , y ) (x,y) (x,y) 入栈。
• （2）出栈：栈空→结束；栈不空→取栈顶元素 ( x , y ) (x,y) (x,y) ，以y为当前扫描线。
• （3）从种子点 ( x , y ) (x,y) (x,y) 出发，沿当前扫描线向左、右两方向填充，标记区段的左右端点为 x l xl xl 和 x r xr xr。
• （4）确定新的种子点：在区间 [ x l , x r ] [xl,xr] [xl,xr] 中检查与当前扫描线 y y y 上下相邻的两条扫描线上的像素，若存在非边界、未填充的像素，则把每一区间的最右像素作为种子点压入堆栈，返回第（2）步；

程序

typedef struct{
	int x,y;
} Seed;   // 记录种子点

void ScanLineFill(int x,int y,COLOR oldcolor,COLOR newcolor){
	int xl,xr;
	bool spanNeedFill;    // 决定是否压栈
	Seed pt;
	setstackempty();
	pt.x = x;pt.y = y;stackpush(pt);    // 种子进栈
	while(!isstackempty()){
		pt = stackpop(); x = pt.x; y = pt.y;    // 出栈
		while(getpixel(x,y)==oldcolor){    // 向右填充
			drawpixel(x,y,newcolor);
			x++;
		}
		xr = x - 1;
		x = pt.x -1;
		while(getpixel(x,y)==oldcolor){    // 向左填充
			drawpixel(x,y,newcolor);
			x--;
		}
		xl = x + 1;
		// 处理上面一条扫描线
		x = xl;
		y = y + 1;
		while(x<=xr){
			spanNeedFill = false;
			while(getpixel(x,y)==oldcolor)
			{
				spanNeedFill = true;
				x++;
			}    // 处理内点
			if(spanNeedFill)
			{
				pt.x = x-1; pt.y = y;
				stackpush(pt);    // 每个区间的最右像素
				spanNeedFill = false;
			}
			while(getpixel(x,y)!=oldcolor && x<=xr)
				x++;    // 处理外点
		}  // End of while(x<=xr)
		// 处理下面一条扫描线，代码与处理上面一条扫描线类似
		x = xl;y = y-2;
		while(x<=xr){...}
	}  // End of while(!isstackempty())
}

【Lesson 3】10月12日

第五章 曲线和曲面

5.1 曲线的数学表示

曲线的数学表示方法有显式表示、隐式表示、参数表示三种，其中参数方程比显式、隐式方程有更多的优越性，主要表现在：

• 易满足几何不变性、更多自由度控制、可直接进行几何变换、便于处理斜率无穷大情况、容易将低维曲线曲面扩展到高维空间、可以对参数变量的变化范围归一化、易于使用矢量和矩阵运算

5.2 曲线分析

（1）活动坐标系

设曲线为 P ( t ) = [ x ( t ) , y ( t ) , z ( t ) ] P(t)=[x(t),y(t),z(t)] P(t)=[x(t),y(t),z(t)] 时，切矢量为 P ′ ( t ) P'(t) P′(t)，单位切矢量记为 T T T，随着弧长变化，切矢的导矢方向的单位矢量为主法矢 N N N，副法矢 B = T × N B=T\times N B=T×N。
这三个矢量构成了曲线上的活动坐标系， N N N、 B B B 构成法平面， N N N、 T T T 构成密切平面， B B B、 T T T 构成从切平面。

（2）曲线的曲率和挠度

曲率 κ \kappa κ：曲线的单位切矢对弧长的转动率；
挠度 τ \tau τ：曲线的副法矢方向对弧长的转动率；
两者都是几何量，与参数选择无关。

右旋螺旋线与左旋螺旋线，根据双手进行判断

5.3 曲面分析

（1）曲面的表示

曲面用函数 P = P ( u , v ) P=P(u,v) P=P(u,v) 表示，在曲面上一点 P ( u 0 , v 0 ) P(u_0,v_0) P(u0​,v0​) 处，总存在一条 u u u 线和 v v v 线，也分别有 u u u 向切矢 P u ( u 0 , v 0 ) Pu(u_0,v_0) Pu(u0​,v0​) 和 v v v 向切矢 P v ( u 0 , v 0 ) Pv(u_0,v_0) Pv(u0​,v0​)。这两个切矢的矢量积，决定了曲面在该点处的法矢 n ( u 0 , v 0 ) n(u_0,v_0) n(u0​,v0​)。

偏移曲面：将曲面上的每一个点沿着法矢方向移动固定距离 d d d。

（2）直纹面和可展曲面

直纹面：
可展平面：直纹面沿着每一条母线只有唯一的切平面，即曲面可以通过简单的弯曲来展平。

（3）曲面的曲率性质

研究曲面的弯曲程度，过曲面上一点的法线能产生无数个平面，每个平面都能和曲面相交，产生无数条法截线、无数个“法曲率”，其中最大和最小的法曲率为主曲率，所在方向相互垂直

两个主曲率的乘积为高斯曲率、全曲率、总曲率。
两个主曲率的均值为平均曲率、中曲率。

5.4 曲线的插值、逼近与拟合

• 插值：构造一条曲线，顺序通过给定数据点，进行插值。
• 逼近：构造一条曲线，某种意义上最接近给定数据点。
• 拟合：上述两者统称。

（1）多项式插值
对于 n + 1 n+1 n+1 个数据点 P i P_i Pi​ 及其对应参数 t i t_i ti​ ，可构造 n n n 次插值多项式：
p ( u ) = ∑ i = 0 n a i t i p(u)=\sum^n_{i=0}a_it_i p(u)=i=0∑n​ai​ti​

（2）多项式逼近

5.5 参数化

参数化：为一组有序的数据点 ( P 0 , P 1 , . . . P n ) (P_0,P_1,...P_n) (P0​,P1​,...Pn​) 赋予相应的一组参数 ( t 0 < t 1 < . . . < t n ) (t_0<t_1<...<t_n) (t0​<t1​<...<tn​)，有以下几种常用参数化方式：
① 均匀参数化
② 累加弦长参数化
③ 向心参数化
④ 修正弦长参数化法

5.6 几何连续性

一条复杂形状的曲线，一般是通过多段简单曲线的拼接完成的，需要考虑拼接处的连续性问题。
连续性的两种度量方式：参数连续性 - C n C^n Cn 连续；几何连续性 - G n G^n Gn 连续；
要达到 G 2 G^2 G2 连续，连接点处必须满足：

• G 0 G^0 G0 连续：两端直线首尾相接。
• G 1 G^1 G1 连续：两端

5.7 参数三次样条曲线

5.8 Bezier曲线

5.9 Bezier曲面

5.10 B样条曲线

5.11 B样条曲面

5.12 NURBS曲线与曲面