计算机图形学笔记及练习

1. 计算机图形学概述

1.1 研究内容

图形含有几何属性，或者说更强调场景的集合表示，是由场景的几何模型和警务的物理属性共同组成。（矢量/参数）
图像是指计算机内以位图形式存在的灰度信息。（位图）
计算机图形学：利用计算机研究一系列原理、方法与技术的学科。
图形的表示和生成：如何对数据建模，并将数据转换为图像？
图形的处理和显示：如何在专门的显示设备上显示图形？
一个完整的图形处理过程包括：
图形的输入
图形的处理
图形的输出

1.2 计算机图形学的发展历史

50年代，CTR的出现为计算机生成和显示图形提供了可能。
50年代末期，MIT的林肯实验室在“旋风”计算机上开发SAGE空中防御体系，通过光笔在屏幕上指点与系统交互，标志着交互式图形技术的诞生。
60年代
MIT林肯实验室的I. E. Sutherland发表了一片题为“Sketchpad：一个人机交互通信的图形系统”的博士论文，确定了交互图形学作为一个学科分支。
法国雷诺汽车公司的工程师Pierre Bezier提出 Bezier曲线、曲面的理论，而称为计算机辅助几何设计(CAGD)的先驱。
MIT的教书 Steven A. Coons提出了超限插值的新思想，通过插值四条任意便捷的曲线来构造曲面，
70年代
光栅图形学迅速发展
图形软件标准化：ISO发布CGI、CGM、GKS、PHIGS
真实感图形学和实体造型技术：(1970)Bouknight提出第一个光反射模型；(1971)Gourand提出“漫反射模型 + 插值”的思想，被称为Gourand明暗处理；(1975)Phong提出著名的简单光照模型-Phong模型。

1.3 图形软件发展及软件标准的形成

近二十年，国际标准化组织ISO已经批准和正在讨论的与计算机图形有关的标准有：
GKS、GKS-3D、PHIGS、CGM、CGI、IGES、STEP
事实标准
SGI的OpenGL，微软的Direct X，Adobe的Postscript等。

1.4 当前研究热点

造型技术
真实感图形绘制技术
人机交互技术
与计算机网络技术的紧密结合
远程导航与维修
远程教育
图像生成技术与图像处理的结合
虚拟现实技术

1.5 图形系统

一个图形系统通常由：图形处理器、图形输入设备和图形输出设备构成。

图形输入设备

鼠标
键盘：输入控制命令，利用光标指示对象与位置。
光笔：一种检测光的装置。P13 考核原理，判断正误
数字化仪：数控板/手写板
扫描仪：直接把图形和图像扫描到计算机中以像素信息进行存储的设备。
光学信号 -> 模拟信号 -> 数字信号
触摸屏，3D图形输入设备

图形处理器(显卡)

显示主芯片是显卡的核心，俗称GPU
显存用于存储将要现实的图形信息及保存图形运算的中间数据。

图形显示设备

图形输出包括图形的显示和图形的绘制
图形显示指的是在屏幕上输出图形。
图形绘制通常指把图形画在纸上(硬拷贝)，如打印机和绘图仪
显示器分类：
CRT显示器
平板显示器

阴极射线管(CRT) P9

CRT显示器分类
视觉属性：单色CRT，彩色CRT
偏转系统：偏转电场式，偏转磁场式
扫描方式：随机扫描，光栅扫描
组成：
电子枪
聚焦系统
加速电极
偏转系统
荧光屏
工作原理
电子枪发射电子束
经过聚焦系统、加速电极、偏转系统，轰击到荧光屏的不同部位，被其表面的荧光物质吸收，发光产生可见的图形。
为要保持一幅稳定的画面，必须不断地发射电子束(不断刷新)，以抵消亮度的衰减。
电子枪
阴极：电流通过，灯丝加热，发出电子束。
控制栅：通过调节负电压来控制电子数量，即控制荧光屏上相应点的亮度。
聚焦系统：通过电场和磁场控制电子束变细，保证亮点足够小，提高分辨率。
加速电极：加正的高电压(几万伏)，使电子达到轰击激发荧光屏应有的速度
偏转系统
控制静电场或磁场，使电子束偏转。
最大的偏转角是系统性能的最重要的指标，显示器长短与此有关。
CRT显示器屏幕越大，整个显像管就越长。
荧光屏
荧光物质：吸收电子束而发光
余辉时间：持续发光时间。电子束离开某点后，该点的亮度值衰减到初始值。
刷新：为了让荧光物质保持在一个稳定的亮度值。
刷新频率：每秒重绘屏幕次数，显示器更新图像的速率。
光点：电子束打在荧光屏上，显示器能显示的最小的发光点。
像素：构成屏幕的最小元素。
图形显示在屏幕上时，按当前的图形显示分辨率所能提供的最小元素点。像素点可看做光点的集合，其最小尺寸等于光点。
屏幕分辨率/光栅分辨率：是物理分辨率，CRT在水平或者竖直方向单位长度上能识别的最大像素个数，单位通常为dip。
显示分辨率：计算机显示控制器所提供的显示模式分辨率。

P9 考点假设荧光物质的持续发光时间为40ms 则，CRT产生稳定图像所需要的最小刷新频率 = 1秒/荧光物质的持续发光时间= 1000/40ms = 25 Hz
只有刷新频率高达一定值后，图像才能稳定显示，约为每秒60帧(60Hz)。一般必须要有85Hz以上的刷新频率。

彩色阴极射线管

彩色CRT：通过将能发不同颜色的光的荧光物质进行组合而产生彩色。
渗透性 - 射线穿透法：常用于随机扫描显示器。
多枪型 - 影孔板法：常用于光栅扫描显示器。

射线穿透法

屏幕内表面涂有两层荧光涂层。红色光和绿色光两种发光物质，不同速度电子束穿透荧光层的深浅，决定所产生的颜色。
应用：主要用于画线显示器
优点：成本低
缺点：只能产生有限几种颜色

影孔板法 P10

影孔板被安装在荧光屏的内表面，用于精确定位像素的位置。
分类：
点阵式：球面显像管。
栅线式：柱面显像管，如日本索尼公司的特丽珑管，三菱公司的钻石龙管。
栅格式/沟槽式：LG的未来窗显像管。
工作原理：
三基色(红绿蓝)，三色荧光点，三只电子枪。
电子枪、影孔板中的一个小孔和对应的荧光点呈一直线。
每个小孔与一个像素（即三个荧光点）对应。
调节各电子枪发生的电子束中所含电子的数目，即可控制各色光点亮度。
显示器能同时显示的颜色个数：如果每支电子枪发出的电子束的强度有256个等级，则显示器能同时显示256*256*256=16M种颜色，称为真彩系统。

栅线式 vs 点阵式

原理的区别：光线的选择方式和荧光点的排列不同
点阵式的缺点：
用于球面荧光屏，几何失真大。
三角形的荧光点排列，即使很密很细也不会特别清晰。
栅线式的优点：
亮度更高，色彩也更鲜艳。
用于高分辨率的柱面和平面显示器。
电子束通过率有很大的提高。

荫罩式显示器的固有缺陷

由合金钢板制成的荫罩易磁化
受热受冲击时易变形
显像管内射向荧光屏的电子束中有75% 以上被荫罩阻挡，转变成热量浪费了
屏幕尺寸越大或清晰度越高，就越难制造， 生产成本高，成品率偏低，价格过高
制约彩色显像管清晰度提高的技术瓶颈是彩色显像管中的荫罩

随机扫描显示系统特点

数据表示：矢量表示，只有端点信息，无线段中间点
扫描方式：电子束像一支快速移动的画笔，在任意方向上自由移动，
按照显示命令用画线的方式绘出图形
显示图形：几何属性为主，线框图形
别称：矢量扫描显示器，画线显示器
优点：扫描速度快，分辨率高，线条质量好，易修改，交互性好，
动态性能好
缺点：价格贵，只能显示线框图形，应用于军事、CAD领域

光栅扫描的显示系统特点

数据表示：像素矩阵，像素数组
扫描方式：从上到下，从左到右，与电视工作原理类似
显示图形：几何属性＋视觉属性(Visual attribute) , 真实
感图形

光栅图形显示系统

显示处理器：主要任务是将应用程序定义为一组像素强度值，存放在帧缓冲存储器中。
帧缓冲存储器：俗称显存，保存了对应屏幕所有亮点的亮度值。
视频控制器：建立帧缓存与屏幕像素之间一一对应，负责刷新。
CRT显示器

帧缓存与显示器分辨率的关系

帧缓存的大小 = 显示器分辨率的大小 * 帧缓存的位平面数 / 8
eg. 分辨率为640x480、1280x1024、1024x1024的显示器各需要多少字节位平面数为24的帧缓存？ans: 分辨率*24/8

显存问题

高分辨率和真彩要求有大的显存：1024x1024真彩模式需要3M字节显存。
解决办法：
采用查色表或者称彩色表机制。
采用隔行扫描的方法。

带宽问题

带宽T与分辨率(M*N)、帧频(刷新频率)F的关系：T >= M * N * F
高分辨率和高刷新频率要求高带宽
解决办法：
隔行扫描(现在一般用逐行扫描)
对Z缓冲期内容进行压缩和快速清除。

光栅显示系统的特点

优点
成本低
易于绘制填充图形
色彩丰富
刷新频率一定，与图形的复杂度无关
易于修改图形
缺点
需要扫描转换
扫描转换速度偏低，交互操作响应慢
分辨率偏低，有阶梯效应，会产生走样

LCD显示器

优点
外观小巧精致，厚度只有6.5-Bcm左右
响应速度快、无闪烁、无干扰
工作电压低，功耗小，省电
没有电磁辐射，对人体健康没有任何影响
缺点
成品率偏低导致成本偏高，冷阴极荧光灯的使用寿命井不算太长，可
视角度有限

1.6 计算机图形学的应用及研究前沿

计算机辅助设计与制造
可视化
真实感图形实时绘制与自然景物仿真
计算机动画
用户接口
计算机艺术

2.基本图形的生成算法

### 2.1 直线绘制算法 - 光栅平面的显示图形 - 在光栅显示平面上，我们只能用二维光栅网格上**尽可能靠近**这条直线的象素集合来表示它。 - 每个象素具有一定的尺寸，是显示平面上可被访问的最小单位， - 它的**坐标x和y只能是整数**，也就是说相邻象素的坐标值是阶跃的而不是连续的。

直线段的扫描转换

两点确定一条直线
通过直线的两个点的坐标计算出斜率和截距，确定直线方程。
通过x值确定每一个y的值，并舍入y的值。

数值微分(DDA)算法

基本思想：
假设直线段的宽度为1,直线段的斜率: |k| ≤ 1
已知过端点P₀(x₀, y₀), P₁(x₁, y₁)的直线L：y = kx + b。
直线斜率 k = (y₁ - y₀) / (x₀ - x₀)
当x的增量D_x = 1， y_i+1 = y_i + k
当x每递增1，y递增k(即直线斜率)；取象素点(x, round(y))作为当前点的坐标。

DDALine(x0,y0,x1,y1,color) 
int x0,y0,x1,y1,color;
{
	int x
	float dx,dy,k,y
	dx=x1-x0; dy=y1-y0; 
	k=dy/dx;
	y=y0;
	for(x=x0;x<=x1;x++)
	{
		drawpixel(x,int(y+0.5),color); 
		y=y+k;
	}

注意：
当|k| ≤ 1时，x每增加1，y最多变化1。
当|k| > 1时，必须把x与y的地位互换。
DDA算法的特点 以|k| ≤ 1为例
y与k必须用浮点数表示
每一步都要对y进行四舍五入后取整
不利于硬件实现

中点算法

基本原理
通过在每列(行)象素中确定与理想直线最接近的象素来进行扫描转换
考虑直线斜率k在0~1之间
当前象素点为P（x_p,y_p），则下一个象素点有两种可选择点
P₁（x_p+1,y_p）, P₂（x_p+1,y_p+1）
P1与P2的中点（x_p+1,y_p+0.5）称为M
Q为理想直线与x = x_p+1垂线的交点
当M在Q的下方时，则取P₂应为下一个象素点
当M在Q的上方时，则取P₁为下一个象素点
算法实现
过点(x₀,y₀)、(x₁, y₁)的直线段L的方程式为：F(x, y)=ax+by+c=0
其中，a = y₀ - y₁, b = x₁ - x₀, c = x₀y₁ - x₁y₀
欲判断中点M在交点Q点的上方还是下方，只要把M代入F（x，y），并判断它的符号即可
构造判别式：d=F(M)=F(x_p+1, yp+0.5)=a(x_p+1)+b(y_p+0.5)+c
当d<0时，M在L(Q点)下方，取P2为下一个象素
当d>0时，M在L(Q点)上方，取P1为下一个象素
当d=0时，选P1或P2均可，约定取P1为下一个象素

增量法改进：

注意到d是x_p, y_p的线性函数，可采用增量计算，提高运算效率
d = F(M)=F(x_p+1, y_p+0.5) = a(x_p+1)+b(y_p+0.5)+c
若当前象素（P的下一个像素）处于d≥0情况，则取P的正右方象素P1(x_p+1, y_p)，再下一个象素位置的判别式：
d₁ = F(x_p+2, y_p+0.5) = a(x_p+2)+b(y_p+0.5)+c = d+a
增量为a
若当前象素（P的下一个像素） d<0时，则取右上方象素P2(x_p+1, y_p+1)，再下一个像素位置的判别式：
d₂ = F(x_p+2, y_p+1.5) = a(x_p+2)+b(y_p+1.5)+c = d+a+b
增量为a＋b
初值计算
画线从(x₀, y₀)开始， F(x₀, y₀) = 0
d的初值：起始点(x0, y0) 下一个像素的判别式：
d₀ = F(x₀+1, y₀+0.5)+c = F(x₀, y₀)+a+0.5b = 0 + a+0.5b = a+0.5b
摆脱小数计算
我们使用的只是d的符号
d的增量都是整数，只是初始值包含小数
可以用2d代替d来摆脱小数

void Midpoint Line (int x0,int y0,int x1, int y1,int color)
{ 
	int a, b, d1, d2, d, x, y;
	a=y0-y1； b=x1-x0；d=2*a+b; //初值
	d1=2*a； d2=2* (a+b);
	x=x0；y=y0;
	drawpixel(x, y, color);
	while (x<x1)
	{ 
		if (d<0) 
		{
			x++;
			y++；;
			d+=d2; 
		}
		else 
		{
			x++;
			d+=d1;
		}
		drawpixel (x, y, color);
	} 
}

Bresenham算法

基本思想：
过各行各列象素中心构造一组虚拟网格线
按直线从起点到终点的顺序计算直线与各垂直网格线的交点
然后根据误差项的符号确定该列象素中与此交点最近的象素
采用增量计算，使得对于每一列，只要检查一个误差项的符号，就
可以确定该列的所求象素
算法实现
先考虑斜率k=dy/dx≤1的直线，直线方程可以表示为
假设当前像素的x坐标已经确定为x_i，其y坐标为y_i
由于坐标(x_i, y_i)只能取整数，下一个像素的x坐标为
而y_i＋1的坐标有两种可能：保持不变，即y_i＋1＝y_i；y坐标递增1，即y_i＋1＝y_i＋1
设A为CD边的中点，若B点在A点上方，选择D点；否则，选C点。
具体实现
如果直线的起始点在象素中心，所以误差项d的初值d₀＝0。
x下标每增加1，d的值相应递增直线的斜率值k，即d＝d＋k。
一旦d≥1，就把它减去1，这样保证d在0与1之间。
①当d≥0.5时，最接近于当前象素的右上方象素（x_i+1, y_i+1）
②当d<0.5时，更接近于右下方象素（x_i+1, y_i）
为方便计算，令e＝d-0.5
e的初值为-0.5 (d0 = 0)，增量为k
①当e≥0时，最接近于当前象素的右上方象素（x_i+1, y_i+1）
②当e<0时，更接近于右方象素（x_i+1, y_i）

void Bresenhamline (int x0,int y0,int x1, int y1,int color)
{
	int x, y, dx, dy;
	float k, e;
	dx = x1-x0, dy = y1- y0, k=dy/dx;
	e=-0.5, x=x0, y=y0;
	for (i=0; i≤dx; i++)
	{
		drawpixel (x, y, color);
		x=x+1, e=e+k;
		if (e≥0)
		{ 
			y++, e=e-1;
		}
}
}

Bresenham画线算法优点：
快速增量算法
仅使用整数计算
效率高，易于用硬件实现
与DDA算法相比，DDA算法的问题：
误差的累积会使直线远离真实的结果
四舍五入运算和浮点运算耗时

改进的Bresenham算法

可以改用整数以避免除法。由于算法中只用到误差项的符号，因此可作如下替换：
e’ = 2 * e * dx 即用2 * dx * e代替原有的e。

void InterBresenhamline (int x0,int y0,int x1, int y1,int color)
{
	dx = x1-x0, dy = y1- y0；
	e=-dx; x=x0; y=y0;
	for (i=0; i<dx; i++)
	{
		drawpixel (x, y, color）
		x++； e=e+2*dy;
		if (e>=0) 
		{
			 y++; 
			 e=e-2*dx;
		}
	}
}

2.2 圆的生成

八等分圆：可以同时绘制八分对称的点。
八分对称性同时解决了“绘制点稀疏”的问题。
只需绘制右上八分之一的圆弧。
①切线斜率|dy/dx| ≤ 1 ②y的变化慢于x ③x每递增1，y最多最多改变一个像素单位 ④不会产生像素空隙 ⑤会有更多的像素拟合圆弧 ⑥使圆弧拟合更精确。

中点画圆法

构造判别式(圆方程)：F(x, y) = x² + y² - R²
判断点在圆内(F < 0)、圆上(F = 0)、圆外(F > 0)
M(x_p + 1,y_p - 0.5)是P1和P2的中点
d = F(M) = F(x_p + 1,y_p - 0.5) = (x_p + 1)² + (y_p - 0.5)² - R²
八分之一圆弧（如半径R=20），初始象素坐标(0, R)
下一个像素的绘制位置(1, R) 或(1, R-1)
得到中点坐标(1, R-0.5)
构造判别式d₀ = F(M) -> d₁, d₂…

增量算法避免重复计算

MidPointCircle(int R int color)
{
	int x,y;
	float d;
	x=0; y=R; d=1.25-R;
	CirclePoints (x,y,color); //显示圆弧上的八个对称点
	while(x<=y)
	{
		if(d<0) 
			d+=2*x+3;
		else 
		{ 
			d+=2*(x-y)+5; 
			y--; 
		}
		x++;
		CirclePoints(x,y,color); //显示圆弧上的八个对称点
	}
}

为了进一步提高算法的效率，可以将上面的算法中的浮点数改写成整数，将乘法运算改成加法运算，即仅用整数实现中点画
圆法。
初始化运算使用 Q:为什么可以去掉0.25？
d’= d - 0.25 = 1.25 – R – 0.25 = 1 – R 代替 d = 1.25 - R

中点算法小结

圆弧各点切线斜率绝对值<1 -> 从x扫描至x+1，y的备选绘制点为y, y-1
适当利用对称性提高效率
- 利用圆的八分对称性 -> 只需绘制圆右上八分之一圆弧
利用中点判别法选择绘制点
联合圆方程 + 每一步的两个备选绘图点的中点 -> 构造判别式
设计增量算法 -> 避免重复计算
符号判别 -> 简化浮点运算为整数运算

生成圆弧的Bresenham法

以点(0, R) 为起点按顺时针方向生成圆，则在第一象限内（四分之一圆弧）y是x的单调递减函的单调递减函。
假设圆心和起点均精确地落在像素中心上。如果已经知道圆弧上的一点 (x_i,y_i )，下一像素的选取有三种可能：
①正右方像素H ②右下角像素D ③正下方像素V
构造函数：F(x_p + 1,y_p - 0.5) = (x_p + 1)² + (y_p - 0.5)² - R²
这三个像素的偏差的平方为：

2.3 椭圆的生成

F(x,y) = b²x²+a²y²-a²b²=0
椭圆的对称性：
只考虑第一象限椭圆弧生成只考虑第一象限椭圆弧生成，分上下两部分
以切线斜率为-1的点作为分界的点。
椭圆上一点处的法向量：N(x,y) = (F)’ x i+(F)’ y j = 2b²x i+2a²y j
在上部分，法向量的y向分量较大，斜率K满足 |k|< 1,|△x| ＞|△y| ，所以 x方向为主位移方向。
在下部分，法向量的x向分量较大，斜率K满足 |k|> 1,|△y| ＞|△x| ，所以 y方向为主位移方向。
与圆弧中点算法类似：确定一个象素后，接着在两个候选象素的中点计算一个判别式的值，由判别式的符号确定更近的点。
先讨论椭圆弧的上部分：
(x_p, y_p)的中点(x_p + 1, y_p - 0.5)
d₁ = F(x_p + 1, y_p - 0.5)
算法步骤：

输入椭圆的长半轴 a 和短半轴 b。
计算初始值 d=b²+a²(-b+ 0.25 )，x= 0，y=b 。
绘制点 (x, y )及其在四分象限上的另外三个对称点。
判断 d 的符号。若d≤ 0，则先将d更新为d+b²(2x + 3)，再将 ( x, y)更新为 (x+ 1,y)；否则先将d更新为 d+b²(2x + 3) + a²(-2y + 2)，再将 ( x, y )更新为 (x + 1, y - 1)。
当b²(x+1) < a²(y - 0.5)时，重复步骤 3 和 4 。否则转到步骤 6 。
用上半部分计算的最后点 ( x, y )来计算下半部分中d的初值：d = b²(x + 0.5)² + a² (y - 1)² - a² b²

2.4 多边形的扫描转换

1. 实区域填充算法

点在多边形内的包含性检验
检验夹角之和：若夹角和为0，则点p在多边形外；若夹角和为360°，则点p在多边形内。
射线法检验交点数：交点数 = 偶数(包括0) -> 点在多边形之外；交点数 = 奇数 -> 点在多边形之内
逐点测试：效率低不实用。
解决办法：包围盒法。
分类
扫描线填充算法：按扫描线顺序，测试点的连贯性
种子填充算法：从内部一个种子点出发，测试点的连贯性。

2. 多边形种类

多边形 :由一系列首尾相连的直线段构成的图形称为多边形。
凸多边形是指任意两顶点间的连线均在多边形内;
凹多边形是指任意两顶点间的连线有不在多边形内的部分;
含内环的多边形则是指多边形内再套有多边形，多边形内的多边形也叫内环，内环之间不能相交。

3. 如何表示多边形

顶点表示是用多边形的顶点序列来表示多边形。
表示直观、几何意义强、占内存少，易于进行几何变换，被广泛用于各种几何造型系统中;
点阵表示是用位于多边形内的象素集合来刻画多边形。
丢失了许多几何信息(如边界、顶点)，但它是光栅显示图形所需要的表示形式。
多边形的扫描转换处理对象：非自交多边形 (边与边之间除了顶点外无其它交点)

4. 多边形的扫描转换 / 扫描线算法 / 多边形的有序边表法

4个基本步骤：
求交：计算扫描线与多边形各边的交点
排序：把所有交点按x值递增顺序排序
配对：将第一个与第二个、第三个与第四个等交点配对，每对交点代表扫描线与多边形的一个相交区间。
填色：把相交区间内的像素置成多边形的颜色，相交区间外的颜色置成背景色。
顶点交点的计数问题：
思路1: 局部最高点和局部最低点：计偶数次交点
思路2: 检查交于该顶点的两条边的另外两个端点的y坐标值：大于该顶点y坐标值的个数
填充扩大化问题
取中心扫描线 y+0.5
– 检查交点右方像素的中心是否落在区间内：x_l ≤ x + 0.5 ≤ x_r
效率问题：
影响算法效率的因素：求交和交点排序
把多边形所有边放在一个表中，按顺序取出，分别计算与当前扫描线求交点。
为了减少和简化求交点计算，对每条扫描线，建立一个活性边表：把所有与当前扫描线有交点的边放到一个表中存储。(活性边：仅与当前扫描线有交点的边)
活性边表 AET：
结点信息：
① x:当前扫描线与边的交点
②△x:从当前扫描线到下一条扫描线之间的x增量
③ymax:边所交的最高扫描线号
活性边表的更新：
①结点信息的更新 x’ = x + △ x
②旧边的删除
③新边的插入
新边表 NET
为解决新边插入的问题，对每条扫描线建立一个新边表。
扫描线与边的交点应为扫描线与边的初始交点
结点信息
①x₀:扫描线与边的初始交点。（若采用中心扫描线，则需将活性边的较低端点的x坐标值加上0.5△x作为x0）
②△x:从当前扫描线到下一条扫描线之间的x增量
③ymax:边所交的最高扫描线号
优点:
对每个像素只访问一次
与设备无关
缺点:
数据结构复杂，表的维护、排序开销大
只适合软件实现

扫描线算法步骤

根据给出的多边形顶点坐标，建立NET表;
求出顶点坐标中最大y值ymax和最小y值ymin。
初始化AET表指针，使它为空。
执行下列步骤直至NET和AET都为空.
如NET中的第y类非空，则将其中的所有边取出并插入AET中;
如果有新边插入AET，则对AET中各边排序;
对AET中的边两两配对，(1和2为一对，3和4为一对，…)，将每对边中x坐标按规则取整，获得有效的填充区段，再填充.
当前扫描线纵坐标y值递值1;
如果AET表中某记录的ymax=yj，则删除该记录(因为每条边被看作下闭上开的);
对AET中剩下的每一条边的x递增1/k，即x = x+ 1/k .

边填充算法

无需复杂的链表结构
涉及到屏幕像素的异或写操作
第一次异或写操作，像素被置为前景色
第二次异或写操作，像素被置为背景色
边填充算法的基本思想
对每一条与多边形相交的中心扫描线
将像素中心位于交点右方的全部像素取补 (异或写)
分类：
算法1：以扫描线为中心的边缘填充算法
算法2：以边为中心的边缘填充算法
边填充算法的优点:
最适合于有帧缓存的显示器
可按任意顺序处理多边形的边
仅访问与该边有交点的扫描线上右方的像素，算法简单
缺点:
对复杂图形，每一像素可能被访问多次，输入/输出量大
图形输出不能与扫描同步进行，只有全部画完才能打印

边界标志法 P27

在帧缓冲器中对多边形的每条边进行直线扫描转换，亦即对多边形边界所经过的象素打上标志。
对每条与多边形相交的扫描线依从左到右的顺序，逐个访问该扫描线上的象素。
使用一个布尔量inside来指示当前点是否在多边形内的状态。
Inside的初值为假，每当当前访问的象素为被打上边标志的点，就把inside取反。
对未打标志的象素，inside不变。
若访问当前象素时，inside为真，说明该象素在多边形内，则把该象素置为填充颜色。
用软件实现时，有序边表算法(扫描线算法)与边界标志算法的执行速度几乎相同。
但由于边界标志算法不必建立维护边表以及对它进行排序，所以边界标志算法更适合硬件实现，这时它的执行速度比有序边表算法快一至两个数量级。

2.5 区域(种子)填充算法

区域填充

区域：指已经表示成点阵形式的填充图形，它是象素的集合。
表示方法: 内点表示、边界表示
内点表示
枚举处区域内部的所有像素
内部的所有像素着同一个颜色
边界像素着与内部像素不同的颜色
边界表示
枚举出边界上所有的像素
边界上的所有像素着同一颜色
内部像素着与边界像素不同的颜色
种子填充算法的另外一种思路:
假设多边形区域内至少有一个像素已知
由该像素出发找出区域内部的所有像素
区域连通方式
4连通区域(4个方向运动：上下左右)
8连通区域(8个方向运动)

种子填充的一种非递归(栈)算法

以4连通边界为例
种子像素入栈
当栈非空时，重复以下步骤:
栈顶像素出栈
将出栈象素置成填充色
按左、上、右、下顺序检查与出栈象素相邻的四象素，若其中某象素不在边界上且未被置成填充色，则将其入栈
特点: 每个像素都需要压栈，耗内存，费时间

种子填充的扫描线算法

基本思想:
利用扫描线的连贯性，每次填充一行像素
减少压入堆栈的像素数目
种子像素入栈
当栈非空时，重复以下步骤:
栈顶像素出栈
沿扫描线对出栈像素的左右像素进行填充，直到遇到边界像素为止
将上述区间内最左、最右像素记为x_l,和x_r
在区间[x_l,x_r]中检查与当前扫描线相邻的上下两条扫描线是否全为边界像素、或已填充的像素，若为非边界、未填充的像素，则把每一区间的最右像素取为种子像素入栈。(后进先出)
扫描线种子填充算法的特点
适用于边界定义的区域
四连通边界定义的区域既可以是凸的，也可以是凹的，还可以是有孔的。
算法减少了每个像素的访问次数
所需堆栈深度较浅
每次递归填充一行像素，因而速度较快

多边形扫描转换(A)与区域填充方法(B)比较

都是光栅图形面着色，用千真实感图形显示。
可相互转换。
不同点：

基本思想不同；

A用于将顶点表示转换成点阵表示；
B只改变区域内填充颜色，没有改变表示方法。

对边界的要求不同

A：只要求扫描线与多边形边界交点个数为偶数。
B：区域封闭，防止递归填充跨界。

基本的条件不同

A：从边界顶点信息出发。
B：区域内种子点。

2.6 字符

字符的表示和输出

字符：数字、字母、汉字，计算机中字符由一个数字编码唯一标识。
字符集：
ASCII码：美国信息交换标准代码。
ISO 8859：是国际标准化组织(ISO)及国际电工委员会(IEC)联合制定的一系列8位字符集的标准，现时定义了15个字符集。增加、加192个字母及符号，附加符号的拉丁字母语言
GB2312/GBK, 这就是汉字的国标码，专门用来表示汉字，是双字节编码，
Unicode可以用来表示所有语言的字符，而且是定长双字节（也有四字节的）编码，包括英文字母在内。
UTF可以用来表示所有语言的字符， utf编码是不定长编码，每一个字符的长度从1-6个字节不等。另外， utf编码自带简单的校验功能。一般来讲，英文字母都是用一个字节
表示，而汉字使用三个字节。
字库：字库中存储了每个字符的形状信息，字库分为矢量和点阵型两种。
点阵字符：
在点阵表示中，每一个字符由一个点阵位图来表示。点阵字符的存储是按行或者按列进行编码。
显示时，形成字符的像素图案。
矢量字符
采用直线和曲线段来描述字符形状，矢量字符库中记录的是笔划信息(存的是顶点的位置信息)。
显示时，解释字符的每个笔划信息

2.7 反走样

什么是反走样?
把由离散量表示连续量引起的失真称为走样;
把减少或克服走样效果的技术称为反走样技术，简称反走样。
光栅图形的走样有如下几种:
产生阶梯或锯齿形;
狭小图形遗失;细节失真
实时动画忽隐忽现、闪烁跳跃。
常用的反走样的主要方法 P41
提高分辨率方法(硬件技术)
非加权区域采样：改变直线段的模型，由此产生算法。将直线段看作具有一定宽度的狭长矩形。缺点是直线离像素中心点越近，贡献越大。
加权区域采样：使相交区域对象亮度的贡献依赖于该区域与像素中心的距离。

3. 三维图形的剪裁

场景由世界坐标中指定的对象集合组成
当我们显示场景时，仅显示特定窗口中的那些对象
因为将内容绘制到显示器需要时间，我们会剪切窗口外的所有内容
设窗口的边界为wx_min, wy_min, wx_max, wy_max
当一个点(x, y)满足：wx_min < x < wx_max && wy_min < y < wy_max 则不需要被剪裁
否则被剪裁。

3.1 直线段裁剪

Cohen-Sutherland算法

优点：减少了必须计算的线与窗口的交点的数量。
世界空间根据窗口边界划分为区域：
每个区域具有唯一的四位区域码。
区域码表示区域相对于窗口的位置。
<img src = “区域码.png” width =50%”>
判别方法：设线段的两个端点为P1(x1，y1)和P2(x2，y2)，根据上述规则，可以求出P1和P2所在区域的分区代码C1和C2。
C1 = C2 = 0，表明两端点全在窗口内，因而整个线段也在窗内，应予保留。
C1 And C2 ≠ 0(两端点代码按位作逻辑乘不为0)，即C1和C2至少有某一位同时为1，表明两端点必定处于某一边界的同一外侧，因而整个线段全在窗外，应予舍弃。
不属于上面两种情况，均需要求交点。
注意：求的交点可能是延长线上的交点。
求交点：
使用直线的方程计算与窗口边界的交点
假设一条直线具有端点(x1, y1), (x2, y2)
与垂直窗口边界的交点坐标为 y = y₁ + m(x_边界 - x₁), x_边界可以为x_min或者x_max
与水平窗口边界的交点坐标 x = x₁ + (y_边界 - x₁) / m
m = (y₂ - y₁) / (x₂ - x₁)

中点分割剪裁算法

注意：求的交点是真实的交点。
基本思想：
P( (x₁ + x₂) / 2 , (y₁ + y₂) / 2 )
如果P1与P同侧，移动P1点。即可能的交点只能出现在PP2段 if((C1&C)!=0) P1=P;
如果P1与P不同侧，移动P2点。即可能的交点只能出现在P1P段 if((C1&C)= =0) P2=P;
<img src = “中点分割.png” width =22%”>
算法步骤：
将直线的两端点P1、P2编码得：C1、C2。
根据C1和C2的具体值，可以有三种情况：
①C1=C2=0，表明两端点全在窗口内，因而整个线段也在窗内，应予保留。
②C1&C2≠0，表明两端点必定处于某一边界的同一外侧，因而整个线段全在窗外，应予舍弃。
③不属于上面两种情况，均需要求交点。
求交点
①令窗外端点为P1，如果窗外点不是P1，则P1和P2交换端点。保留窗内端点P2到暂存器里。
②对P1编码为C1，用中点公式求出中点，并编码得C。按照中点算法的求交规则：
若P1和P同侧，移动P1点if((C1&C)!=0) P1=P; 否则，移动P2点 else P2=P
③流程转②，直到P1和P2相差一个单位时:令交点为P2，取出暂存器的端点赋给P1，然后转向流程①
算法特点：
- 求交点的次数(n)与线段长度(L)有关，其关系为: L = 2ⁿ 例如：线段长度为256，则求交点的次数为8。
- 中点分割法求出的交点是边界上的有效交点，而不是边界及其延长线上的交点。而Cohen-Sutherland直线裁剪算法求出的则是边界上或者边界的延长线上的交点。

3.2 多边形裁剪

Sutlerland-Hodgman算法 / 逐边裁剪算法

窗口的一条边以及延长线构成的裁剪线该线把平面分成两个部分：可见一侧；不可见一侧。
简单地通过依次将多边形与每个边界进行比较来修剪多边形。
多边形的各条边的两端点S、P。它们与裁剪线的位置关系只有四种：
S，P均在可见一侧 → 输出P
S，P均在不可见一侧 → 无输出
S可见，P不可见 → 输出SP与裁剪线的交点I
S不可见，P可见 → 输出SP与裁剪的交点I和P
特点：
裁剪算法采用流水线方式， 适合硬件实现。
可推广到任意凸多边形裁剪窗口

Weiler-Atherton算法

特点：
裁剪窗口为**任意多边形(凸、凹、带内环)**的情况:
内裁减与外裁剪：
内裁剪: 即通常意义上的裁剪，取图元位于窗口之内的部分
外裁剪: 取图元位于窗口之外的部分。
如果主多边形与裁剪多边形有交点，则交点成对出现。它们被分为如下两类:
一类称“入”点。即被裁剪多边形由此点进入裁剪窗口，如图中a、c、e。
一类称“出”点。即被裁剪多边形由此点离开裁剪窗口，如图中b、d、f。
Weiler-Atherton算法步骤

建顶点表
求交点
裁剪

详细步骤

顺时针输入被裁剪多边形顶点序列 I 放入数组1中。
顺时针输入裁剪窗口顶点序列II放入数组2中。
求出被裁剪多边形和裁剪窗口相交的所有交点，并给每个交点打上 “入”、“出”标记。然后将交点按顺序插入序列I得到新的顶点序列 III ，并放入数组3中;同样也将交点按顺序插入序列II得到新的顶点序列 IV ，放入数组4中;
初始化输出数组Q，令数组Q为空。接着从数组3中寻找“入”点。如果“入”点没找到，程序结束。
如果找到“入”点，则将“入”点放入S中暂存。
将“入”点录入到输出数组Q中。并从数组 3 中将该“入”点的“入” 点标记删去。
沿数组 3 顺序取顶点: 如果顶点是“出点”，则将顶点录入到输出数组Q中，流程转第7步。否则，流程转第8步。
沿数组4顺序取顶点:如果顶点是“入点”，则将顶点录入到输出数组Q中，流程转第8步。否则，流程转第9步。
如果顶点不等于起始点S，流程转第6步，继续跟踪数组3。否则，将数组Q输出。
流程转第4步，寻找可能存在的分裂多边形。算法在第4步：满足“入”点没找到的条件时，算法结束。

交点的奇异情况处理
与裁剪多边形边重合的主多边形的边不参与求交点;
对于顶点落在裁剪多边形的边上的主多边形的边，如果落在该裁
剪边的内侧，将该顶点算作交点;而如果这条边落在该裁剪边
的外侧，将该顶点不看作交点。

3.3 字符裁剪

基于字符串：将包围字符串的外接矩形对窗口作裁剪。当字符串外接矩形整个在窗口内时予以显示，否则不显示。
基于字符：将包围字符的外接矩形对窗口作
裁剪，如某个字符外接矩形整个落
在窗口内予以显示，否则不显示。
基于构成字符的最小元素 / 像素：点阵字符：点裁剪；矢量字符：线裁剪

4. 图形的变换

4.1 图形变换的数学基础

图形几何变换：几何图形按照某种法则或规律变换成另一种几何图形的过程。
矩阵及其运算 P203

4.2 二维几何变换

齐次坐标

齐次坐标：所谓齐次坐标, 就是将一个原本是n维的向量用一个n+1 维向量来表示。
例如, 向量(x₁, x₂, …, x_n)的齐次坐标表示为
(H_x₁, H_x₂, …, H_{x_n}, H), 其中H是一个不为0的实数。
由点或向量的齐次坐标(H_x₁, H_x₂, …, H_{x_n}, H)求它的规范化齐次坐标, 可根据如下公式求得：
x₁ = H_x₁ / H, x₂ = H_x₂ / H, …, x_n = H_{x_n} / H
齐次坐标表示不是唯一的，通常当h=1时，称为规格化齐次坐标，在计算机图形学里面，我们常用的是规格化齐次坐标。
为什么需要引入齐次坐标？
多个变换作用于多个目标
引入齐次坐标，变换的表示法统一
图形变换具有统一表示形式的优点：
便于变换合成
便于硬件实现

几何变换

平移、旋转、缩放变换
对称变换：
错切变换：
也称为剪切、错位变换，用于产生弹性物体的变形处理。
错切的变换矩阵
(a) 错切角 (b) 沿x方向错切 (c) 沿y方向错切
仿射变换
变换的坐标x’和y’都是原始坐标x和y的线性函数。
仿射变换具有平行线转换成平行线和有限点映射到有限点的一般特性。
平移、比例、旋转、对称和错切变换是二维仿射变换的特例，任何常用的二维仿射变换总可表示为这五种变换的组合。

复杂变换

复合变换是指对图形进行一次以上的变换，变换的结果是每次的变换矩阵相乘。
任何一组变换都可以表示成一个复合变换矩阵，只需要计算每一个单独变换矩阵，并求解出乘积。
从另一个方面讲，任何一个复杂的几何变换都可以看作基本几何变换的组合形式，也叫复合变换。

4.3 窗口到视区的变换

基本概念

坐标系：建立了图形与数之间的对应联系
世界坐标系：用户需要在图形独享所在的控件定义一个坐标系
用户坐标系：用户按照自己习惯建立世界坐标系，所以世界坐标系有时也称用户坐标系。
局部坐标系：简化图形对象的描述，相对于图形定义
屏幕坐标系：屏幕上或绘图纸上定义一个二维直角坐标系，也称为设备坐标系。
窗口：在计算机图形学中，将在用户坐标系中需要进行观察和处理的一个坐标区域。
视区：将窗口映射到显示设备上的坐标区域。
改变视区的位置，可以在输出设备的不同位置显示图形对象。
改变视区的大小和比例可以改变显示对象的大小和比例。
裁剪在扫描转换之前

窗口到视区变换

变换步骤：
将窗口左下角点移至用户系统系的坐标原点
针对原点进行比例变换
进行反平移
两种情况：

窗口区的边与坐标轴平行
窗口区的边与坐标轴不平行：将窗口左下角点移至用户系统系的坐标原点后需要旋转到与坐标轴平行。

4.4 三维几何变换

三维齐次坐标

(x, y, z)对应的齐次坐标为(x_h, y_h, z_h, h)
标准齐次坐标(x,y,z,1) ==〉用来表示三维空间点(x, y, z)。
使用右手坐标系(z轴正方向向外)

三维几何变换

三维平移变换、放缩变换
三维旋转变换
是指给定的三维立体绕三维空间某个指定的坐标轴旋转θ角度。
旋转后, 立体的空间位置将发生变化, 但形状不变。
θ角的正负按右手规则确定, 右手大姆指指向旋转轴的正向, 其余四个手指指向旋转角的正向。

三维错切变换：是指三维立体在空间沿x、 y、 z三个方向实现错切变形, 三维错切是二维错切变换的一个扩充。
三维对称变换

5. 投影

5.1 三维图形显示的基本问题

在二维屏幕上如何显示三维物体?

显示器屏幕、绘图纸等是二维的，显示对象是三维的
解决方法：投影

如何表示三维物体?

二维形体的表示：直线段, 折线, 曲线段, 多边形区域
二维形体的输入：简单(图形显示设备与形体的维数一致)
三维形体的表示：空间直线段、折线、曲线段、多边形、曲面片
三维形体的输入、运算、有效性保证**(困难)**
解决方法：各种用于形体表示的理论、模型、方法

如何反映遮挡关系?

物体之间或物体的不同部分之间存在相互遮挡关系
遮挡关系是空间位置关系的重要组成部分
解决方法：消除隐藏面与隐藏线

如何产生真实感图形?

人们观察现实世界产生的真实感来源于
• 空间位置关系：近大远小的透视关系和遮挡关系
• 光线传播引起的物体表面颜色的自然分布
解决方法：建立光照明模型、开发真实感图形绘制方法

三维图形显示的基本研究内容

投影
三维形体的表示
消除隐藏面与隐藏线
建立光照明模型、开发真实感图形绘制方法

5.2 平面几何投影

投影 — 照相机模型
选定投影类型 → 透视投影与平行投影
设置投影参数 → 拍摄方向、距离等
三维裁剪 → 取景
投影和显示 → 成像
简单的三维图形显示流程图
投影：将n维的点变换成小于n维的点。比如将3维的点变换成小于3维的点
投影中心(COP: Center of Projection)
eg. 视觉系统—观察点、视点; 电影放映机—光源
投影面：不经过投影中心的面
eg. 平面–照相机底片; 曲面—球幕电影,视网膜
投影线：从投影中心向物体上各点发出的射线
eg. 直线—光线; 曲线—喷绘
平面几何投影：投影面是平面，投影线为直线
投影变换：投影过程，投影的数学表示
平面几何投影的分类

透视投影

投影中心与投影平面之间的距离为有限
参数：投影中心、投影方向
eg. 室内白炽灯的投影，视觉系统
灭点：不平行于投影平面的平行线，经过透视投影之后收敛于一点，称为灭点。
主灭点：坐标轴方向的平行线在投影面上形成的灭点称作主灭点。
一点透视：表现范围广，纵深感强，适合表现庄重、严肃的室内空间或建筑物。比较呆板，与真实效果有一定的距离
两点透视为：构图画面增加动感，使画面结构丰富。
三点透视：一般用于超高层建筑俯瞰图或仰视图。
特点：产生近大远小的视觉效果，由它产生的图形深度强，看起来更加真实。

平行投影

投影中心与投影平面之间的距离为无限
是透视投影的极限状态
分类:
- 根据投影射线与投影平面的关系，平行投影可分为正投影和斜投影。
正投影：
根据投影面和坐标轴的夹角可分为两类:三视图和正轴测图
当投影面与某一坐标轴垂直时，得到的投影为三视图，这时投影方向和这个坐标轴的方向一致。否则，得到的投影为正轴测图。
三视图: 包括主视图、侧视图和俯视图三种，投影面分别与X轴、Y轴和Z轴垂直
正轴侧：当投影平面与三个坐标轴都不垂直时。
正轴侧又分为等轴侧、正二侧和正三侧。
当投影面与三个坐标轴之间的夹角都相等时为等轴测。
当投影面与两个坐标轴之间的夹角相等时为正二测。
当投影面与三个坐标轴之间的夹角都不相等时为正三测。

斜投影

投影方向不垂直于投影面
分类：
斜等侧投影:投影方向和投影面夹角α成45°
斜二侧投影:投影方向和投影面夹角α=arctan(2)

投影总结

平行投影:投影中心与投影面间距离为无穷远。
正平行投影:投影方向和投影面垂直。
三视图:三个投影面和坐标轴相互垂直。
正轴侧:投影面和坐标轴呈一定的关系。
斜平行投影:投影方向和投影面不垂直。
透视投影:投影中心与投影面间距离为有限。

5.3 投影变换 & 投影举例

三维观察变换所起的作用是完成从用户空间选取的一部分物体描述变换到显示屏上指定的视窗中的图形描述。
简单的三维观察流水线：
取景变换:完成从用户坐标系中的描述 -> 观察坐标系中的描述的坐标变换。
观察坐标系(VRC):照相机所在的坐标系

建立观察坐标系

挑选一个用户坐标点称为观察参考点VRP(View Reference Point)，即该点为观察坐标系的原点;
通过给定观察平面法向量来选择观察坐标系的 Zv轴和观察平面方向;
指定一观察向上向量，通过该向量来建立观察坐标系的Yv轴;
确定观察点又称为投影中心(若为透视投影时) 或确定投影方向(若为平行投影时)

用户坐标到观察坐标的变换

在物体描述投影到观察平面之前，必须将其转换成观察坐标。该变换顺序是:
平移观察参考点VRP(x0,y0,z0)到用户坐标系原点;
进行旋转分别让Xv,Yv和Zv轴对应到用户坐标系的x、y、和z轴。一旦景物中物体的用户坐标描述转换到观察坐标后，我们就可以将三维
物体投影到二维观察平面上。
为使剪取处理简单和规范化(即单位化)，需要利用坐标变换将视见体规范化。

视见体(View Port)

视见体是三维裁剪窗口。
建立步骤：
定义窗口 → 发出射线 → 形成观察空间 → 前后剪裁面 → 形成视见体
需注意，对于透视投影，前截面必须在投影中心和后截面之间。
投影参考点(PRP: Projection Reference Point)
透视投影: COP==PRP;
平行投影: 投影方向DOP= CW-PRP
透视投影: 观察空间为四棱锥
平行投影: 观察空间为四棱柱

透视投影变换

问题：在uvn中，投影平面为n=0，投影中心为(0，0，d)，待投影点为P(u_p，v_p，n_p)，求投影点Q (u_Q，v_Q，n_Q)
透视投影变换矩阵:作用就是将三维物体变换成二维透视投影。

斜平行投影

投影方向不垂直于投影平面的平行投影被称为斜平行投影。

从世界坐标系到观察坐标系的变换

5.4 规范视见体变换 / 规范裁剪空间

为什么引入规范视见体?
使裁剪算法非常容易、直观
有助于隐藏线和隐藏面的消除。
规范化变换：将任意视见体变换成规范视见体的变换
三维图形的显示流程图
采用视见体变换的三维图形显示流程图
观察变换：从世界坐标系到观察坐标系的变换

何时裁剪

投影之前裁剪三维裁剪
优点：只对可见的物体进行投影变换
缺点：三维裁剪相对复杂
投影之后裁剪二维裁剪
优点：二维裁剪相对容易
缺点：需要对所有的物体进行投影变换
采用投影后裁剪的三维图形显示流程图
在投影之前裁剪的理由
三维物体的表面通常被离散表示成多边形或折线，而对这类简单图元，三维裁剪同样比较简单。
三维图形在显示过程中需要被消隐，做这个工作要有图形的深度信息，所以必须在投影之前完成。消隐很费时，如果在此之前裁剪 (或部分裁剪)掉不可见的图形，可使需要消隐的图形减至最小。

6. 隐藏面的消除

6.1 基本概念

要画出确定的、立体感很强的三维图形，就必须将那些被不透明的面
(或物体)所遮挡的线段(或面)移去，这就是隐藏线或隐藏面的消隐处理。
按消隐对象将三维物体消隐分为两类:
线消隐：其消隐对象是物体上的边, 消除的是物体上不可见的边，用于线框图。
面消隐：其消隐对象是物体上的面, 消除的是物体上不可见的面，用于填色图。
根据消隐空间的不同，将消隐算法分为3类：
物体空间的消隐算法：将场景中每一个面与其它每个面比较, 求出所有点、边、面的遮挡关系。算法精度较高。如光线投射等。
图像空间的消隐算法：对屏幕上每个像素进行判断, 决定哪个多边形在该像素可见。如：Z-buffer、扫描线等。
物体空间和图像控件的消隐算法：在物体空间中预先计算面的可见性优先级, 再在图像空间中生成消隐图。如：画家算法等。

6.2 提高消隐算法效率的常见方法

利用连贯性

物体的连贯性
面的连贯性
区域的连贯性
扫描线的连贯性

将透视投影转换成平行投影

消隐与投影方式有关 (消隐必须在投影之前完成)
包围盒技术：包围目标的简单形体
背面剔除
空间分割技术
物体分层表示

包含消隐的三维图形显示流程图：

消隐的基本(核心)问题:排序

整体排序: 画家算法
点排序: Z-Buffer算法、光线投射算法
区间排序: 扫描线算法
区域排序: 区域子分算法

6.3 画家算法

基本思想
先将场景中的物体按其距观察点的远近进行排序，结果放在一张线性表中;
线性表构造:距观察点远的称优先级低，放在表头;距观察点近的称优先级高，放在表尾。该表称为深度优先级表
然后按照从表头到表尾的顺序逐个绘制物体。
基本步骤
对场景中的多边形按深度进行排序，
形成深度优先级表;
按从远到近的顺序显示多边形;
画家算法不能处理的情况
多边形循环遮挡
多边形相互穿透
解决办法: 沿多边形所在平面之间的交线循环地分割这些多边形，直至最终可建立确定的优先级表。

6.4 Z缓冲器算法

基本思想
先将Z缓冲器中个单元的初始值置为-1 (规范视见体的最小n值)。
当要改变某个像素的颜色值时，首先检查当前多边形的深度值是否大于该像素
原来的深度值(保存在该像素所对应的Z缓冲器的单元中);
如果大于，说明当前多边形更靠近观察点，用它的颜色替换像素原来的颜色;
否则说明在当前像素处，当前多边形被前面所绘制的多边形遮挡了，是不可见的，像素的颜色值不改变。
优点
算法简单、稳定
便于硬件加速
不需要整个场景的几何数据
缺点
需要Z缓冲器 改进: 扫描线Z缓冲器算法
计算复杂度大 改进:区域子分算法

需要计算的像素深度值次数 = 多边形个数 * 多边形平均占据的像素个数

6.5 扫描线Z缓冲器算法

改进一: 将窗口分割成扫描线
缺点：在每一个被多边形覆盖像素处需要计算深度值；被多个多边形覆盖的像素需要多次计算深度值
改进二：利用扫描线的连贯性计算深度 (增量法)
改进三：采用多边形分类表(PT)、活化多边形表 (APT)避免多边形与扫描线的盲目求交
改进四：利用边、边的分类表(ET)、边对、活化边对表(AEPT)避免边与扫描线的盲目求交

6.6 区间扫描线算法

要求多边形不能相互贯穿
该算法可以看作是边相关扫描线填充算法的延伸。
不同的是在消隐算法中处理的是多个面片，而多边形填充中是对单个多边形面进行填充。
它是把当前扫描线与各多边形在投影平面的投影的交点进行排序后，使扫描线分为若干子区间。因此，只要在区间任一点处找出在该处z值最大的一个面，这个区间上的每一个象素就用这个面的颜色来显示。
改进：
在一条扫描线上，以区间为单位确定多边形的可见性
不需要Z-Buffer

6.7 区域子分割算法

首先将场景中的多边形投影到绘图窗口内(假设它为边长为k的正方形)
判断窗口是否足够简单，若是则算法结束;
否则将窗口进一步分为四块(左上，右上，左下，右下)。
对此四个小窗口重复上述过程，直到窗口仅为一个像素大小。
此时可能有多个多边形覆盖了该像素，计算它们的深度值，以最近的颜色显示该像素即可。

6.8 光线投射算法

考察由视点出发穿过观察屏幕的一像素而射入场景的一条射线,则可确定出场景中与该射线相交的物体。
在计算出光线与物体表面的交点之后, 离像素最近的交点的所在面片的颜色为该像素的颜色; 如果没有交点, 说明没有多边形的投影覆盖此像素, 用背景色显示它即可。

7. 真实感图形的生成

当光照射到物体表面时，光线可能被吸收、反射和透射。被物体吸收的部分转化为热，反射、透射的光进入人的视觉系统，使我们能看见物体。
为模拟这一现象，我们建立一些数学模型来替代复杂的物理模型，这些模型就称为明暗效应模型或者光照明模型。三维形体的图形经过消隐后，再进行明暗效应的处理，可以进一步提高图形的真实感。

7.1 简单光照明模型

光照射到物体表面，主要发生:
反射
透射(对透明物体)
部分被吸收成热能
反射光和透射光的光谱分布——决定景物表面的颜色
反射光和透射光的强弱——决定景物表面的明暗程度
环境光：在空间中近似均匀分布，即在任何位置、任何方向
上强度一样
点光源:几何形状为一个点，位于空间中的某个位置，向周围所有的方向上辐射等强度的光。
在物体的不同部分其亮度也不同，亮度的大小依赖于物体的朝向及它与点光源之间的距离。
漫反射：粗糙、无光泽物体(如粉笔，墙面)表面对光的反射
各点反射光的强度只与①点光源强度、入射角 ②物体表面的反射系数 ③物体各表面的朝向有关
与观察者的观察方向无关
镜面反射: 光滑物体(如金属或塑料)表面对光的反射
n为镜面反射(高光)指数，n越大，则Is(镜面反射光强)随α的增大衰减的越快
n的取值与表面粗糙程度有关
①n越大，表面越平滑(散射现象少，稍一偏离，明暗亮度急剧下降)
②n越小，表面越毛糙(散射现象严重)
高光: 入射光在光滑物体表面形成的特别亮的区域

Phong光照明模型

由物体表面上一点P反射到视点的光强 I 为环境光的反射光强 I_e， 理想漫反射光强 I_d，和镜面反射光I_s的总和。
Phong光照明模型是真实感图形学中提出的第一个有影响的光照明模型
经验模型，Phong模型存在不足:
显示出的物体象塑料，无质感变化
没有考虑物体间相互反射光
镜面反射颜色与材质无关
镜面反射大入射角失真现象

7.2 多边形表示的明暗处理

Gouraud明暗处理(双线性光强插值)

先计算物体表面多边形各顶点的光强, 然后用双线性插值, 求出多边形内部区域中各点的光强。
基本算法描述:

计算多边形顶点的平均法向;
计算顶点的平均光强;
插值计算离散边上的各点光强;
插值计算多边形内域中各点的光强。

优点
简单易行，计算量小
只需已知顶点的法向量
缺点
只适用于简单的漫反射光照模型，不能正确模拟镜面反射高光形状
用于动态显示物体时，物体表面明暗以不规则方式进行变化，高光显示问题
光亮度变化不连续的边界处出现过亮或过暗的条纹
公共顶点处颜色不连续，顶点方向不具代表性
在Gouraud提出明暗处理方法时，Phong模型还没有出现

Phong明暗处理 (双线性法向插值)

与双线性光强插值相比, 该方法有如下特点:
保留双线性插值, 对多边形边上的点和内域各点, 采用增量法。
对顶点的法向量进行插值, 而顶点的法向量, 用相邻的多边形的法向作平均。
由插值得到的法向, 计算每个像素的光亮度。
假定光源与视点均在无穷远处, 光强只是法向量的函数。
优点
Phong方法绘制的图形比Gouraud方法更真实
缺点
计算量远大于Gouraud方法

阴影的生成

阴影
光源不能直接照射的区域
对光源来说，不可见的面(隐藏面)

7.3 透明

现实世界中有许多透明物体，如玻璃等。透过透明物体，可以观察到其后面的景物。
产生简单透明效果的方法
插值透明方法
过滤透明方法

Whitted光透射模型

基于经验、理论，不是严格的物理模型。

Hall光透射模型

在Whitted光透射模型的基础上推广而来。
加入光源引起的规则透射分量。
可以处理理想的漫透射。

7.4 整体光照明模型

五个组成部分：
简单光照模型是一种局部光照模型，不考虑周围环境对当前景物表面的光照明影响，忽略了光在环境景物之间的传递，很难表现自然界复杂场景的高质量真实感图形。
基于简单光照明模型的光透射模型，虽然可以模拟光的折射，但是这种折射的计算范围很小，不能很好的模拟多个透明体之间的复杂光照明现象。
对于上述的这些问题，就必须要有一个更精确的光照明模型。整体光照明模型就是这样的一种模型，它是相对于局部光照明模型而言的。

7.5 光线跟踪算法 P149

四种光线
视线：由视点与象素(x，y)发出的射线
阴影测试线：物体表面上点与光源的连线
反射光线
折射光线
无论是Gouraud还是Phong明暗绘制算法，都只能模拟局部光照明效果。
如果场景中存在光亮的镜面物体和透明物体，则光线会在物体之间反射和折射，这些都是上述算法所无法模拟的。还不能产生阴影效果。如果必须模拟这些效果，则我们可以采用光线跟踪算法或辐射度算法。
自然界中光线的传播过程：光源 -> 物体表面 -> 物体表面 -> 人眼
光线跟踪过程：光线传播的逆过程(视线跟踪)
光源发出光线，经反射与折射，只有很少部分可以进入人的眼睛。因此直接从光源出发，沿光的传播方向进行光线跟踪是不现实的，也是不必要的。
实际上，光线跟踪算法的跟踪方向与光传播的方向是相反的，是视线跟踪。
优点: 能够方便的产生阴影，模拟镜面反射与折射现象。
缺点: 计算量大，每一条光线都要与场景中的物体进行求交、计算光照模型等。

递归终止条件

该光线未碰到任何物体。
该光线碰到了背景。
光线在经过许多次反射和折射以后，就会产生衰减，光线对于视点的光强贡献很小(小于某个设定值)。
光线反射或折射次数即跟踪深度大于一定值。

7.6 纹理

颜色纹理：光滑表面的花纹、图案。
几何纹理：粗糙的表面(如桔子表面的皱纹), 是基于物体表面的微观几何形状的表面纹理。
两种方法来定义纹理:
图像纹理
函数纹理

分辨率为1024x1024的显示器各需要多少字节位平面
数为24的帧缓存？
A) 512KB ; B) 1 MB ; C) 2MB ; D) 3MB
哪一个不是国际标准化组织(ISO)批准的图形标准？
A) GKS ; B) PHIGS ; C) CGM ; D) DXF
在计算机图形学的发展历史上，是谁确立了计算机图形学作为一门新学科的地位，他的哪些技术直到今天还在使用？
计算机图形系统的硬件设备有哪些？
光栅扫描显示器中，屏幕图形是依靠帧缓存进行刷新的，帧缓存里存放的是什么？
简述随机扫描显示器和光栅扫描显示器的简单工作原理和各自的特点。
用中点画线方法扫描转换连接两点P0（0,0）和P1（5,2）的直线段。
a = y0 - y1 = -2
b = x1 - x0 = 5
d0 = 2 * a + b = 1
d1 = 2 * a = -4
d2 = 2 * (a+b) = 6

图形学题目

Breenham算法：
中点画圆算法
用边相关扫描线填充算法将顶点为P1 (2，2)，P2 (5，1)， P3(10，3)， P4(8，8)，P5(5，5)，P6(2，7)的多边形填充。请说明如何建立新边表NET和活动边表AET并写出该多边形填充的新边表NET和活动边表AET。
用数值微分DDA算法、中点算法和Bresenham算法扫描转换直线段(1,1)–(5,3)，
写出扫描转换的结果:写出每一步递推过程的x，y坐标及判别式d的值，图示计
算结果。
图中有两条圆弧A和B，假定当前取点为(xi，yi)，那么下一点只能是正
右方的 E(xi+1，yi)或右下方的SE(xi+1，yi-1)两者之一。假设M是E和SE的中点，即，利用中点画圆算法，回答下列问题:

当F(M) < 0时，下一点应取哪个点? E点
当F(M) > 0时，下一点应取哪个点? SE点
当F(M) = 0时，下一点应取哪个点? 在E与SE之中随便取一个即可，我们约定取SE点。

裁剪的实质是什么?

ans：裁剪的实质就是决定图形中哪些点、线段、文字、以及多边形在窗口之内。

已知窗口左下角坐标(50，50)，右上角坐标(400，400) 直线的端点坐标P1(40，100)和P2(500，420)，试用Cohen-Sutherland直线编码裁剪算法，结合编码图示，求出P1和P2所在区域的分区代码C1和C2。

C1为0001; C2为1010 。

当线段与窗口边界有交点时，如果线段的长度为1024，用中点分割算法求交点的次数是多少?

10次。

用Weiler-Atherton算法完成内裁剪和外裁剪。DCBA为裁剪窗口，dcba为要裁剪的多边形。
一个由顶点(10，20)，(20，20)和(15，30)所定义的三角形，让它相对于点Q(5，25)正向旋转30°，求其变换后的三角形。
推导以直线ax+by+c=0为对称轴的二维对称变换矩阵。
在坐标系oxyz中，求一个变换将P(1,1,1)Q(2,2,2)变换到z 轴上:P在坐标原点，Q在z轴正半轴。
如图所示三角形ABC，将其关于A点逆时针旋转90度，写出其变换矩阵和变换后图形各点的规范化齐次坐标。
下列有关平面几何投影的叙述，错误的是( )
A)透视投影又可分为一点透视、二点透视、三点透视;
B)斜投影又可分为斜等测、斜二测;
C)正轴测又可分为正一测、正二测、正三测;
D)三视图又可分为正视图、侧视图、俯视图。
下列有关平面几何投影的叙述语句中，正确的论述为( )
A)在平面几何投影中，若投影中心移到距离投影面无穷远处，则成为平行投影;
B)透视投影与平行投影相比，视觉效果更有真实感，而且能真实地反映物体的精确的尺寸和形状;
C)透视投影变换中，一组平行线投影在与之平行的投影面上，可以产生灭点;
D)在三维空间中的物体进行透视投影变换，可能产生三个或者更多的主灭点。
用下列二维图形变换矩阵:
2 0 1
T = 0 1 1
0 0 1
将产生变换的结果为( )
A) 图形放大2倍;
B) 图形放大2倍，同时沿X、Y坐标轴方向各移动1个绘图单位;
C) 沿X坐标轴方向各移动2个绘图单位;
D) 沿X坐标轴方向放大2倍，同时沿X、Y坐标轴方向各平移1个绘图单位。
下列有关透视投影的叙述，错误的是( )
A)投影线从视点出发;
B)投影线不平行;
C)任何一束不平行于投影面的平行线的透视投影将汇成一点;
D)主灭点有无数个。
请解释平面几何投影的含义。
何为“透视投影”?并说明“灭点”和“主灭点”是如何产生的?
什么是观察坐标系?为什么要建立观察坐标系?
已知投影面为xoy坐标平面，投影中心在z轴的正向、z=d的位置上，求透视投影变换矩阵。
描述Z缓存器消隐算法的基本原理和算法实现;
光线跟踪算法的跟踪方向与光传播的方向是相同的，是视线跟踪。( )
双线性法向插值算法先计算出曲面在各多边形顶点处的光强，然后再采用双线性插值方法确定在扫描线上每个像素处的光强值，得到多边形的光滑颜色分布。( )
非理想镜面反射中，镜面反射指数n模拟镜面反射光在空间中的汇聚程度，n越大，表面越粗糙( )。
粗糙的物体表面能够将反射光向各个方向散射，称为( )。
比较Gouraud明暗处理算法和Phong明暗处理算法的优缺点。
何谓“光线跟踪算法”?请简要叙述光线跟踪算法的基本思想。