图形的具体应用范围很广，但是从基本的处理技术看只有两类： 一类是线条，如工程图、地图、曲线图表等；

另一类是明暗图，与照片相似。为了生成图形，首先要有原 始数据或数学模型，如工程人员构思的机械零件模型，飞机 的总体方案模型，地形航测的判读数据等等。这些数字化的 输入经过计算机处理后变成图形输出。
求交算法
求交计算是常用算法。区域填充时要求线段交点， 消隐算法需要直线和平面多边形的求交等。 求交运算比较复杂，为减小计算量，求交计算前， 先用凸包进行粗略比较，先排除显然不相交情形。 求交计算是CAD系统的重要部分，其准确性与效率 直接影响CAD系统的可靠性与实用性。
求交问题可以分为两类 ： 求交点：线线求交、线面求交 求交线：面面求交
对字母T进行旋转变换 （旋转60°)
平移变换
上述四种变换都可以通过变换矩阵 必须满足下面的关系 x ' x x
y' y y
a T换前后的坐标
这里△x，△y是平移量，应为常数，但是应用上述 变换矩阵对点进行变换
xw yw x ,y w w
二维齐次变换表示了在w=1平面上点的坐标变换，即P1到 P1*的坐标变换
齐次坐标的特点
1. 当w=0时，齐次坐标可用来表示无穷远的点 2. 将图形处理中的各种变换用统一的方式来处理
a b p T 如二维图形变换矩阵的一般表达式： c d q l m s
对称、错切、旋转等基本变换； 2×1阶矩阵 p
1×2阶矩阵 l m 可以实现图形的平移变换；
q 可以实现图形的透视变换，
T
而[s]可以实现图形的全比例变换。
小结
二维组合变换
上述的几种变换可用统一的变换矩阵形式来实现， 称之基本变换。 但有些变换仅用一次基本变换是不够的，必须由 两次或多次基本变换组合才能实现。这种由多种基 本变换组合而成的变换称之为组合变换，相应的变 换矩阵叫做组合变换矩阵。
（2）种子填色（Seed Filling）算法 这类算法建立在多边形边界的图象形 式数据之上，并需提供多边形界内一 点的坐标，一般只能用于人机交互填 色，而难以用于程序填色。
表示内点
表示边界点
从多边形内部点出发，沿四个方向（或八个方向） 扩散搜索区域内所有待填充的象素点，适用于交 互绘图。其算法步骤： i）多边形边界给特定颜色； ii）内部填充颜色给另外的颜色； iii）从内部点 ( x, y ) 开始，检测该点与边界和 填充色是否相同，均不相同则填充该点； iv）检测相邻点与边界和填充色是否相同，均不 相同则填充该点； v）重复步iv）直至所有象素点被填充。
区域填充算法
区域填充即给出一个区域的边界，要求对边界范围内的所有象素 单元赋予指定的颜色代码。区域填充中最常用的是多边形填色
填色算法分为两大类：扫描线算法和种子点算法
（1）扫描线填色（Scan-Line Filling）算法
这类算法建立在多边形边边界的矢量形 式数据之上，可用于程序填色，也可用 交互填色。 该算法基于几何求交算法，步骤如下： i）输入多边形顶点坐标； ii）求多边形顶点中最大和最小y坐标， 以确定范围； iii）对每条扫描线进行计算，直至所有扫 描线被填充； 关键：如何快速求扫描线与多边形交点； 扫描线填充利用直线快速画法； 应该利用扫描线与多边形交点的连贯 性加速求交算法（多边形与扫描线相交，则 与下一条扫描线很可能相交）
x
y 1
x
a y 1 c l
p d q m s b
3. 齐次变换矩阵通常是非奇异矩阵。当该矩阵奇异 时，det A = 0，坐标经变换后维数将降低，如 三维坐标在二维平面上的投影变换等。
二维齐次变换矩阵
a b 其中2×2阶矩阵 可以实现图形的比例、 c d
在此仅从CAD需求角度来介绍相关研究内容： 工程产品设计中的二维工程图、三维实体模型的显示 本章主要介绍：二维基本图形生成原理、图形变换原理、图 形显示流程
3.1 基本图形生成算法
直线的生成算法
画一条从（x1, y1）到（x2, y2）的直线，实质上是一个发现最佳逼近直 线的象素序列，并填入色彩数据的过程，这个过程也称为直线光栅化
SetPixel (int x, int y, color c);
计算机图形学的研究内容
探讨的主要问题是用计算机进行图形信息的表达、输入、存储、显 示、输出、检索及图形运算等。具体地说，大致有以下内容： (1)图形的输入：研究如何把要处理的图形输入到计算机内，以便 让计算机进行各种处理。 (2)产生图形的算法：研究在显示器或其它输出设备上产生图形的 各种算法； (3)图形的数据结构：研究图形在计算机内的表示方法； (4)图形的变换：研究图形的各种几何变换； (5)图形运算：包括图形的分解、组合等； (6)图形语言：各种图形处理功能的语言; (7)图形软件的标准化：图形软件与设备无关及接口兼容性。 总的来说，计算机图形学应该解决和研究下列一些问题： (1)图形表示和处理的数学方法及其实现的计算机算法； (2)设计一个好的图形软件系统； (3)设计与实际应用相结合的图形应用系统。
该算法直接基于象素算法，不必求交。
裁剪算法
确定图形中哪些部分落在显示区之内,以便显示落在显示区内的那 部分图形。这个选择过程称为裁剪 只有窗口内的物体才能显示出来。因此，窗口之外的物体都是不 可见的，可以不参加标准化转换及随后的显示操作，节约处理时 间。裁剪（clipping）是裁去窗口之外物体的一种操作。
• 二维基本变换
– – – – – 比例变换 对称变换 错切变换 旋转变换 平移变换
• 二维组合变换
比例变换
a b 在变换矩阵 T 中，令b=c=0，则为比例变 c d 换矩阵 a 0 a, d 0 Ts 0 d
其中a，d分别为x，y方向上的比例因子
设坐标P经过n次变换T1,T2,…,Tn 到P*，则变换结果 为： P* = PT1T2…Tn = PT
3. 计算机图形学基础
3.1 基本图形的生成
简单图形的生成 区域填充和剖面线 裁剪
3.2 图形变换
二维变换 三维变换 投影变换
3.3 图形显示流程
回顾显示器显示原理
常规显示器上的图形由荧光屏的点阵组 成，电子束按行列次序扫描点矩阵，并 由显示内容来控制所扫描的点是否发亮， 每扫描一遍称为一帧 荧光屏上画面的每一点称为一个象素（Pixel）。每个象素都对 应于Buffer中的一个存储单元，里面存放着该象素的显示颜色值。 象素的颜色值控制电子束(共三支)对荧光屏的轰击强度，象素在 帧缓存寄存器中的位置编码控制电子束的偏转位置。 分辨率（Resolution）是光栅扫描显示设备最重要的指标 显示器用于显示字符、图形（触摸显示屏还可作为输入设备）
设三维空间点P的坐标为(x,y,z)，它是唯一的。 若用齐次坐标表示时，则为(hx,hy,hz,h)，且不唯一。
齐次坐标的几何意义
将Oxy坐标系增加一与x轴和y轴正 交的w轴。
在w=1的平面上有点P1(x,y,1),则当 w由0变化到无穷时，齐次坐标 Pw(xw,yw,w) 将处在由OP1定义的射线 OQ上。二维坐标则是该射线在w＝1平 面上的交点, 有
cos Tr sin
sin cos
x ' Rcos Rcoscos Rsinsin xcos ysin y' Rsin Rsincos Rcossin ycos xsin
矩形的包围盒是其本身，圆的包围盒是该圆的边界矩形 圆弧的包围盒的计算主要是由因弧的起始点和终止点，以及 与通过圆心的4个坐标轴相交的交点
自由曲线的包容盒则可根据离散的小直线段的起始点和终止 点比较后获得，若精确求解并不经济，因图形显示采用离散 多边形，且图形变换频繁。
复杂组合图形的包容盒则可以在简单图形的包容盒基础上 进行比较得到。
y y=-x y=x
P P1
M
(x,y)
P2
椭圆的生成算法
p0 (0, b)
F F y x
曲线的生成算法
F y
F x
包容盒计算
包围盒(大多采用矩形包容盒，也有球包容盒及其它包容盒)计 算是对图形元素进行求交、编辑和拾取的前提。
直线的包围盒计算直接利用其特征点——起始点和终点就 可得到。
剖面线算法
剖面线是一组等距的平行线，用填充算法 速度慢，直接画线更快，算法步骤： i) 按多边形的初始条件及剖面线的角度和 间距，计算剖面线的范围和数量； ii) 求剖面线与轮廓边的相交位置； iii）对剖面线上的交点进行排序，并按奇偶 规则绘制有效剖面线段。 简化算法：跳过顶点处交点判断
图形反走样算法
如图所示，画出的直线实际上是阶梯状，并不光滑。 因为计算机屏幕是离散象素组成，不是连续信号。象 素是有面积的，不可能面积为零。 线段反走样算法：将线段处理为有宽度的狭长矩形
抖动反走样算法：高分辨率计算，低分辨率显示
3.2 图形变换
• 图形变换的数学基础
– 向量运算 – 矩阵运算
• 二维变换 • 三维变换
直线Bresenham算法
1 0 1 2 3 4 5
过各行各列象素中心构造一组虚拟网格线。按直线从起点到终点的顺序 计算直线与各垂直网格线的交点，然后根据误差项的符号确定该列象素 中与此交点最近的象素。
不需乘除运算
d d d d
圆弧的生成算法
典型算法有扫描转换算法(斜率<1)、中点算法及Bresenham算法
3.2.1 二维变换
a b 点的变换可以通过矩阵运算来实现，令 T c d 称T为变换矩阵，有：
a b x' y' x y ax cy bx dy c d
这里[x’,y’]为变换后点的坐标，[x,y]为变换前点 的坐标，变换矩阵中a,b,c,d的不同取值，可以实现 各种不同变换，从而达到对图形进行变换的目的 。