第3讲 计算机图形学基础

1、3. 计算机图形学基础 3.1 基本图形的生成 简单图形的生成 区域填充和剖面线 裁剪 3.2 图形变换图形变换 二维变换二维变换 三维变换三维变换 投影变换投影变换 3.3 图形显示流程 回顾显示器显示原理回顾显示器显示原理 常规显示器上的图形由荧光屏的点阵组 成，电子束按行列次序扫描点矩阵，并 由显示内容来控制所扫描的点是否发亮， 每扫描一遍称为一帧 荧光屏上画面的每一点称为一个象素（pixel）。每个象素都对 应于buffer中的一个存储单元，里面存放着该象素的显示颜色值。 象素的颜色值控制电子束(共三支)对荧光屏的轰击强度，象素在 帧缓存寄存器中的位置编码控制电子束的偏转位置。 分辨率

2、（resolution）是光栅扫描显示设备最重要的指标 显示器用于显示字符、图形（触摸显示屏还可作为输入设备） setpixel (int x, int y, color c); 计算机图形学的研究内容计算机图形学的研究内容 探讨的主要问题是用计算机进行图形信息的表达、输入、存储、显 示、输出、检索及图形运算等。具体地说，大致有以下内容： (1)图形的输入：研究如何把要处理的图形输入到计算机内，以便 让计算机进行各种处理。 (2)产生图形的算法：研究在显示器或其它输出设备上产生图形的 各种算法； (3)图形的数据结构：研究图形在计算机内的表示方法； (4)图形的变换：研究图形的各种几何变换；

3、(5)图形运算：包括图形的分解、组合等； (6)图形语言：各种图形处理功能的语言; (7)图形软件的标准化：图形软件与设备无关及接口兼容性。 总的来说，计算机图形学应该解决和研究下列一些问题： (1)图形表示和处理的数学方法及其实现的计算机算法； (2)设计一个好的图形软件系统； (3)设计与实际应用相结合的图形应用系统。 图形的具体应用范围很广，但是从基本的处理技术看只有两类： l一类是线条，如工程图、地图、曲线图表等； l另一类是明暗图，与照片相似。为了生成图形，首先要有原 始数据或数学模型，如工程人员构思的机械零件模型，飞机 的总体方案模型，地形航测的判读数据等等。这些数字化的 输入经过

4、计算机处理后变成图形输出。 在此仅从cad需求角度来介绍相关研究内容： 工程产品设计中的二维工程图、三维实体模型的显示工程产品设计中的二维工程图、三维实体模型的显示 本章主要介绍：二维基本图形生成原理、图形变换原理、图本章主要介绍：二维基本图形生成原理、图形变换原理、图 形显示流程形显示流程 最常用的两种算法：最常用的两种算法： 直线直线dda（直接微分算法）（直接微分算法） 直线中的每一点坐标都可以由前一点坐标变化一个增量（dx, dy） 而得到，即表示为迭代式：xi+1=xi+dx，yi+1=yi+dy，并有关系：dy = m dx，(m1)迭代式的初值为直线的起点（x1, y1） 直线直

5、线bresenham算法算法 过各行各列象素中心构造一组虚拟网格线。按直线从起点到终点的顺序 计算直线与各垂直网格线的交点，然后根据误差项的符号确定该列象素 中与此交点最近的象素。 不需乘除运算 3.1 基本图形生成算法基本图形生成算法 直线的生成算法直线的生成算法 画一条从（x1, y1）到（x2, y2）的直线，实质上是一个发现最佳逼近直 线的象素序列，并填入色彩数据的过程，这个过程也称为直线光栅化 0 1 2 3 4 5 3 2 1 line: p0(0, 0)- p1(5, 2) 圆弧的生成算法圆弧的生成算法 典型算法有扫描转换算法(斜率1)、中点算法及bresenham算法 (x,y

6、) y y=-xy=x 椭圆的生成算法椭圆的生成算法 y f x f x f y f ),0( 0 bp 曲线的生成算法曲线的生成算法 p p1 m p2 包容盒计算包容盒计算 包围盒(大多采用矩形包容盒，也有球包容盒及其它包容盒)计 算是对图形元素进行求交、编辑和拾取的前提。 直线的包围盒直线的包围盒计算直接利用其特征点起始点和终点就 可得到。 矩形的包围盒矩形的包围盒是其本身，圆的包围盒圆的包围盒是该圆的边界矩形 圆弧的包围盒圆弧的包围盒的计算主要是由因弧的起始点和终止点，以及 与通过圆心的4个坐标轴相交的交点 自由曲线的包容盒自由曲线的包容盒则可根据离散的小直线段的起始点和终止 点比较后

7、获得，若精确求解并不经济，因图形显示采用离散 多边形，且图形变换频繁。 复杂组合图形的包容盒复杂组合图形的包容盒则可以在简单图形的包容盒基础上 进行比较得到。 求交算法求交算法 l求交计算是常用算法。区域填充时要求线段交点， 消隐算法需要直线和平面多边形的求交等。 l求交运算比较复杂，为减小计算量，求交计算前， 先用凸包进行粗略比较，先排除显然不相交情形。 l求交计算是cad系统的重要部分，其准确性与效率 直接影响cad系统的可靠性与实用性。 求交问题可以分为两类 ： 求交点：线线求交、线面求交 求交线：面面求交 注意：在数学上两个浮点数可以严格相等，但计算机表示的浮点数有误差， 难以绝对相等

8、，相应地，求交运算中要引进容差。 i）当两个点的坐标值充分接近时，即其距离充分近时，就被认为是重合的 点，一般取 =10-6或更小的数。 ii）当两条直线的夹角接近0度（一般取 =10-6或更小）时，就被认为 是两条平行线。 iii）同样，共线、共面、平行面等的判断也是近似的。 区域填充算法区域填充算法 区域填充即给出一个区域的边界，要求对边界范围内的所有象素 单元赋予指定的颜色代码。区域填充中最常用的是多边形填色 填色算法分为两大类：扫描线算法和种子点算法填色算法分为两大类：扫描线算法和种子点算法 （1）扫描线填色（）扫描线填色（scan-line filling）算法）算法 这类算法建立在

9、多边形边边界的矢量形 式数据之上，可用于程序填色，也可用 交互填色。 该算法基于几何求交算法，步骤如下： i）输入多边形顶点坐标； ii）求多边形顶点中最大和最小y坐标， 以确定范围； iii）对每条扫描线进行计算，直至所有扫 描线被填充； 关键：如何快速求扫描线与多边形交点； 扫描线填充利用直线快速画法； 应该利用扫描线与多边形交点的连贯 性加速求交算法（多边形与扫描线相交，则 与下一条扫描线很可能相交） （2）种子填色（）种子填色（seed filling）算法）算法 这类算法建立在多边形边界的图象形 式数据之上，并需提供多边形界内一 点的坐标，一般只能用于人机交互填 色，而难以用于程序填

10、色。 表示内点 表示边界点 从多边形内部点出发，沿四个方向（或八个方向） 扩散搜索区域内所有待填充的象素点，适用于交 互绘图。其算法步骤： i）多边形边界给特定颜色； ii）内部填充颜色给另外的颜色； iii）从内部点 ( x, y ) 开始，检测该点与边界和 填充色是否相同，均不相同则填充该点； iv）检测相邻点与边界和填充色是否相同，均不 相同则填充该点； v）重复步iv）直至所有象素点被填充。 该算法直接基于象素算法，不必求交。 裁剪算法裁剪算法 确定图形中哪些部分落在显示区之内,以便显示落在显示区内的那 部分图形。这个选择过程称为裁剪裁剪 只有窗口内的物体才能显示出来。因此，窗口之外的

11、物体都是不 可见的，可以不参加标准化转换及随后的显示操作，节约处理时 间。裁剪（clipping）是裁去窗口之外物体的一种操作。 图形反走样算法图形反走样算法 剖面线算法剖面线算法 剖面线是一组等距的平行线，用填充算法 速度慢，直接画线更快，算法步骤： i) 按多边形的初始条件及剖面线的角度和 间距，计算剖面线的范围和数量； ii) 求剖面线与轮廓边的相交位置； iii）对剖面线上的交点进行排序，并按奇偶 规则绘制有效剖面线段。 简化算法：跳过顶点处交点判断 如图所示，画出的直线实际上是阶梯状，并不光滑。 因为计算机屏幕是离散象素组成，不是连续信号。象 素是有面积的，不可能面积为零。 线段反走

12、样算法：线段反走样算法：将线段处理为有宽度的狭长矩形 抖动反走样算法：抖动反走样算法：高分辨率计算，低分辨率显示 3.2 图形变换 图形变换的数学基础 向量运算 矩阵运算 二维变换 三维变换 3.2.1 二维变换 点的变换可以通过矩阵运算来实现，令 dc ba t 称t为变换矩阵，有： dybxcyax dc ba yx y x 这里x,y为变换后点的坐标，x,y为变换前 点的坐标，变换矩阵中a,b,c,d的不同取值，可以实 现各种不同变换，从而达到对图形进行变换的目的 。 二维基本变换 比例变换 对称变换 错切变换 旋转变换 平移变换 二维组合变换 比例变换 在变换矩阵 中，令b=c=0，则

13、为比例变 换矩阵 dc ba t 0d, a d0 0a ts 其中a，d分别为x，y方向上的比例因子 对称变换 对坐标轴的对称变换对坐标轴的对称变换 1-0 01 tmx2.对x轴对称: 1.对y轴对称: 10 01- tmy 对原点的对称变换对原点的对称变换: : 1-0 01- t mo 旋转变换 在二维空间里，我们作如 下规定：图形的旋转是指绕 坐标系原点旋转角，且逆 时针为正，顺时针为负，变 换矩阵为 cossin sincos tr xsinycossinrcoscosrsinrsin y ysinxcossinrsincosrcosrcos x 对字母t进行旋转变换 （旋转60)

14、 平移变换 这里x，y是平移量，应为常数，但是应用上述 变换矩阵对点进行变换 而这里的cy，bx均非常量，因此用原来的因此用原来的2 22 2的变的变 换矩阵是无法实现平移变换。换矩阵是无法实现平移变换。 上述四种变换都可以通过变换矩阵 来实现，但是，若实现平移变换，变换前后的坐标 必须满足下面的关系 dc ba t yyy xxx dybxcyax dc ba yxyx 将变换矩阵增加一行一列，实 施对点进行平移变换 1 1 010 001 11mylx ml yxyx 齐次坐标 在平移变换中，我们将x y扩充为x y 1 实际上是由二维向量变为三维向量。 这种用三维向量表示二维向量的方法叫

15、做齐次坐 标法。进一步推广，用n+1维向量表示n维向量的方法 称之为齐次坐标法。 所谓齐次坐标就是用n+1维向量表示n维向量得到 的坐标。对齐次坐标进行坐标变换称为齐次变换，相 应的变换矩阵称为齐次变换矩阵。 设三维空间点p的坐标为(x,y,z)，它是唯一的。 若用齐次坐标表示时，则为(hx,hy,hz,h)，且不唯一。 齐次坐标的几何意义 将oxy坐标系增加一与x轴和y轴正 交的w轴。 在w=1的平面上有点p1(x,y,1),则当 w由0变化到无穷时，齐次坐标 p pw w(x(xw w,y,yw w,w,w) ) 将处在由op1定义的射线 oq上。二维坐标则是该射线在w1平 面上的交点,

16、有 w y y, w x x ww 二维齐次变换表示了在w=1平面上点的坐标变换，即p1到 p1*的坐标变换 齐次坐标的特点 1. 当w=0时，齐次坐标可用来表示无穷远的点 2. 将图形处理中的各种变换用统一的方式来处理 如二维图形变换矩阵的一般表达式： 3. 齐次变换矩阵通常是非奇异矩阵。当该矩阵奇异 时，det a a = 0，坐标经变换后维数将降低，如 三维坐标在二维平面上的投影变换等。 sml qdc pba t sml qdc pba 11yxyx 二维齐次变换矩阵 其中22阶矩阵 可以实现图形的比例、 对称、错切、旋转等基本变换； 12阶矩阵 可以实现图形的平移变换； 21阶矩阵

17、可以实现图形的透视变换， 而s可以实现图形的全比例变换。 dc ba ml tqp 小结 二维组合变换 上述的几种变换可用统一的变换矩阵形式来实现， 称之基本变换。 但有些变换仅用一次基本变换是不够的，必须由 两次或多次基本变换组合才能实现。这种由多种基 本变换组合而成的变换称之为组合变换，相应的变 换矩阵叫做组合变换矩阵。 设坐标p经过n次变换t1,t2,tn到p*，则变换结果 为： p* = pt1t2tn = pt 式中，t = t1t2tn 为总的变换矩阵，组合变换 的目的是将一个变换序列表示为一个变换矩阵。 绕任意点旋转变换（vcad例子） 平面图形绕任意点c(x,y)旋转角，需要通

18、过以下 几个步骤来实现： (1)将旋转中心平移到原点; (2)将图形绕坐标系原点旋转角; (3)将旋转中心平移回到原来位置。 组合变换顺序对图形的影响 复杂变换是通过基本变换的组合而成的，由于矩阵 的乘法不适用于交换律，即： ab ba 因此，组合的顺序一般是不能颠倒的，顺序不同， 则变换的结果亦不同，如图所示。 3.2.2 三维图形变换 三维图形的变换是二维图形变换的简单扩展，变换 的原理还是把齐次坐标点(x,y,z,1)通过变换矩阵变 换成新的齐次坐标点(x,y,z,1)，即 t1zyx1 z y x 其中t为三维基本(齐次)变换矩阵： t 齐次变换矩阵： 平移 缩放 旋转 错切 透视变换

19、整体缩放 比例和对称变换 1000 000 000 000 t s z y x s s s s t1zyx1zyx 1.一般情况，sx,sy,sz0，图形沿三个坐标轴方向作放缩变换； 2.当sx=1,sy=sz=-1时，图形相对于x轴中心对称，其余类推; 3.当sx-1,sy=sz=1时，图形相对于yoz平面对称，其余类推; 4.当sx=sy=sz=-1时，图形相对于原点中心对称。 整体缩放 得到： 左边同乘 s s000 0100 0010 0001 ts s t1zyx1zyx szyx1 z y x 平移变换 t t1zyx1 z y x 1ttt 0100 0010 0001 t x

20、t zy 平移变换矩阵 旋转变换 三维组合变换 与二维组合变换一样，通过对三维基本变换矩阵的组合， 可以实现对三维物体的复杂变换。设坐标p经过n次变换 t1,t2,tn到p*，则变换结果为 p*=pt1t2tn=pt 与二维相同，组合变换时，同样需要注意乘法的顺序 绕任意轴旋转变换 绕任意轴旋转变换是组合变换，变换过程比较复杂。首先，对物 体作平移和绕轴旋转变换，使得所绕之轴与某一根标准坐标轴重 合。然后，绕该标准坐标轴作所需角度的旋转。最后，通过逆变 换使所绕之轴恢复到原来位置。这个过程须由7个基本变换的级 联才能完成。 设旋转任意轴为p1（ x1,y1,z1 ）, p2（ x2,y2,z2

21、 ）两点所定义的 单位矢量(a,b,c)。旋转角度为（图(a) 。这7个基本变换是： 1平移t(x1,y1,z1)使p1点与原点重合(图(b)； 2rx()，使得轴p1p2落入平面xoz内(图(c)； 3ry()，使p1p2与z轴重合(图(d); 4rz()，执行绕p1p2轴的角度旋转(图(e)； 5ry()，作3的逆变换t3-1 ； 6rx()，作2的逆变换t2-1 ； 7t(x1,y1,z1) 作1的逆变换 t1-1 。 注意： 1000 0cossin0 0sincos0 0001 2 aa aa 1000 0cos0sin 0010 0sin0cos 3 1 0100 0010 000

22、1 111 1 zyx 1000 0100 00cossin 00sincos 4 其组合变换矩阵为： t t1 t2 t3 t4 t3-1 t2-1 t1-1 例：简单几何体的图形变换例：简单几何体的图形变换 t zyx z z y y x x zyx z z y y x x 1 1 1 1 1 1 888 2 1 2 1 2 1 888 2 1 2 1 2 1 式中：t为所要进行的图形变换矩阵 假定一六面体abcdefgh各点的坐标分别为（x 1, y 1, z 1）,., (x 8, y 8, z 8)，则经过图形变换后的坐标为： 3.2.3 投影变换 将三维图形向二维平面上投影生成二维

23、图形表示的 过程称为投影变换。 根据视点的远近，投影分为平行投影和透视投影。 当投影中心(观察点)与投影平面之间的距离为无穷 远时，为平行投影，否则为透视投影。 透视投影的图形与眼睛观察景物的原理及效果是一 致的，因而常用于图形的真实效果显示。由于平行 投影后直线间的平行关系不变，因而它常用于三维 图形交互和生成工程图的视图。 投影变换分类: 投 影 平行 投影 透视 投影 正平行 投影 斜平行 投影 正交投影 正轴测 投影 正等测投影 正二测 正三测 斜等测 斜二测 一点透视 二点透视 三点透视 正交投影 投影方向垂直于投影平面时称为正平行投影，正交投影 （也称正投影）是正平行投影的特殊形式

24、，其投影平面相 互垂直，常用于生成工程图的三视图 正交投影 设模型坐标为p(x,y,z)，投影坐标系的x轴向右，y轴 向上，z轴垂直于纸面向外，投影后的坐标为 p(x,y,z)，有 ppa，a为投影变换矩阵，可以 看成从投影坐标系到模型坐标系的变换矩阵。 在采用第一角画法的三视图中，各视图的投影矩阵为 10 0010 0000 0001 a vv v yx 10 0000 0010 0001 a hh h yx 10 0010 0001 0000 a ww w yx 主视图 俯视图 左视图 平移量 轴测投影 将三维图形绕其模型坐标系的x轴和y铀分别旋转一 定的角度后，再垂直于xoy平面向该平面

25、投影，可 获得具有立体感的轴测图。 或者，当视点在模型空间的任意位置e(a,b,c)向坐 标原点观察时，将图形沿观察方向向垂直于视线的 平面投影，也可以得到轴测图，a=b=c时为正等测 投影。 在应用中常采用输入视点坐标的方式来确定轴测投 影的方向，它比绕两轴旋转给定角度的几何意义更 明确。 正轴测投影变换 将坐标系作两次旋转变换t rz(90+)和trx()，其中 trz(90+)使视线oe与新坐标系的yoz平面重合，y轴 方向与ao重合，trx()使新坐标系的z”轴指向视点。 hrxrz atptp90 * 透视投影 透视投影的视线（投影线）是从视点（观察点）出发，视线是 不平行的。不平行

26、于投影平面的视线汇聚的一点称为灭点，在坐标 轴上的灭点叫做主灭点。主灭点数和投影平面切割坐标轴的数量相 对应。按照主灭点的个数，透视投影可分为一点透视、二点透视和 三点透视。 一点透视的投影(z) pprppprpvp ppvp hhh dzdzz ddz zyxhzyx /)/(00 / 1/00 0010 0001 1 坐标变换 假定有两个坐标系oxyz 和ouvn，见右图： n v u o z o y x 在坐标系oxyz中，o的坐标为（ox， oy， oz）, ou 、ov 和 on分别为三个单位矢量（ux,uy,uz）、（vx,vy,vz）和（nx,ny,nz）， 要将坐标系oxyz

27、 中的图形变换到坐标系ouvn中去，称该坐标变 换为t xyzuvn ，其变换为： 1000 0 0 0 1 0100 0010 0001 zzz yyy xxx zyx nvu nvu nvu ooo xyz1 = x y z 1 t xyz1 t-1 = x y z 1 注：图形变换也可由坐标变换得到，且变换矩阵互逆注：图形变换也可由坐标变换得到，且变换矩阵互逆 则点的坐标计算： 3.3 图形显示流程 在图形学中，涉及许多坐标系和坐标变换 模型坐标系：模型坐标系： 方便于物体模型定义的坐标系，又称局部坐标系局部坐标系、或工作坐标工作坐标 系系。因为物体模型在某一任意坐标系下定义可能是非常困

28、难， 如立方体斜放在某坐标系中（如图a），顶点坐标很难确定；最 好将立方体放在某坐标系中使角点重合坐标原点，三条边平行 于坐标轴(如图b)，通过模型变换再实现其任意位置。 图a 图b 世界坐标系世界坐标系(wc) ： 世界坐标系（也有称用户坐标系）是用户用于定义所有物体的统统 一参考坐标系一参考坐标系，它在计算过程中始终保持唯一性，无论物体在何 位置，在什麽模型坐标系，一般应变换到统一的世界坐标系（即 统一的参照坐标系），然后进行其它计算，避免坐标系的混乱， 引起不必要的错误。 物体从模型坐标下经几何变换到世界坐标系称模型变换模型变换，变换矩 阵由坐标变换坐标变换即得。 观察坐标系：观察坐标系： 实际中，可以物体不动照相机动 (移动和转动)，也可相机不动 物体动。通常取物体所在的坐标系为世界坐标系(wc)，投影平面 与投影中心也在世界坐标系中指定。考虑到在世界坐标系中，要 获取某角度物体的投影，所指定的投影平面与投影中心的表示可 能很复杂，