第3讲计算机图形学基础

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

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

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

4、究内容：工程产品设计中的二维工程图、三维实体模型的显示工程产品设计中的二维工程图、三维实体模型的显示本章主要介绍：二维基本图形生成原理、图形变换原理、图本章主要介绍：二维基本图形生成原理、图形变换原理、图形显示流程形显示流程最常用的两种算法：最常用的两种算法：直线直线dda（直接微分算法）（直接微分算法） 直线中的每一点坐标都可以由前一点坐标变化一个增量（dx, dy）而得到，即表示为迭代式：xi+1=xi+dx，yi+1=yi+dy，并有关系：dy = m dx，(m1)迭代式的初值为直线的起点（x1, y1） 直线直线bresenham算法算法过各行各列象素中心构造一组虚拟网格线。按直线从

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

6、生成算法 p p1mp2包容盒计算包容盒计算 包围盒(大多采用矩形包容盒，也有球包容盒及其它包容盒)计算是对图形元素进行求交、编辑和拾取的前提。直线的包围盒直线的包围盒计算直接利用其特征点起始点和终点就可得到。矩形的包围盒矩形的包围盒是其本身，圆的包围盒圆的包围盒是该圆的边界矩形圆弧的包围盒圆弧的包围盒的计算主要是由因弧的起始点和终止点，以及与通过圆心的4个坐标轴相交的交点自由曲线的包容盒自由曲线的包容盒则可根据离散的小直线段的起始点和终止点比较后获得，若精确求解并不经济，因图形显示采用离散多边形，且图形变换频繁。复杂组合图形的包容盒复杂组合图形的包容盒则可以在简单图形的包容盒基础上进行比较得

7、到。求交算法求交算法 l求交计算是常用算法。区域填充时要求线段交点， 消隐算法需要直线和平面多边形的求交等。l求交运算比较复杂，为减小计算量，求交计算前， 先用凸包进行粗略比较，先排除显然不相交情形。l求交计算是cad系统的重要部分，其准确性与效率直接影响cad系统的可靠性与实用性。求交问题可以分为两类 ： 求交点：线线求交、线面求交 求交线：面面求交注意：在数学上两个浮点数可以严格相等，但计算机表示的浮点数有误差，难以绝对相等，相应地，求交运算中要引进容差。i）当两个点的坐标值充分接近时，即其距离充分近时，就被认为是重合的点，一般取 =10-6或更小的数。ii）当两条直线的夹角接近0度（一般

8、取 =10-6或更小）时，就被认为是两条平行线。iii）同样，共线、共面、平行面等的判断也是近似的。区域填充算法区域填充算法 区域填充即给出一个区域的边界，要求对边界范围内的所有象素单元赋予指定的颜色代码。区域填充中最常用的是多边形填色 填色算法分为两大类：扫描线算法和种子点算法填色算法分为两大类：扫描线算法和种子点算法（1）扫描线填色（）扫描线填色（scan-line filling）算法）算法这类算法建立在多边形边边界的矢量形式数据之上，可用于程序填色，也可用交互填色。该算法基于几何求交算法，步骤如下：i）输入多边形顶点坐标；ii）求多边形顶点中最大和最小y坐标，以确定范围；iii）对每条

9、扫描线进行计算，直至所有扫描线被填充；关键：如何快速求扫描线与多边形交点； 扫描线填充利用直线快速画法； 应该利用扫描线与多边形交点的连贯性加速求交算法（多边形与扫描线相交，则与下一条扫描线很可能相交）（2）种子填色（）种子填色（seed filling）算法）算法这类算法建立在多边形边界的图象形式数据之上，并需提供多边形界内一点的坐标，一般只能用于人机交互填色，而难以用于程序填色。表示内点表示边界点从多边形内部点出发，沿四个方向（或八个方向）扩散搜索区域内所有待填充的象素点，适用于交互绘图。其算法步骤：i）多边形边界给特定颜色；ii）内部填充颜色给另外的颜色；iii）从内部点 ( x, y

10、) 开始，检测该点与边界和填充色是否相同，均不相同则填充该点；iv）检测相邻点与边界和填充色是否相同，均不相同则填充该点；v）重复步iv）直至所有象素点被填充。该算法直接基于象素算法，不必求交。裁剪算法裁剪算法 确定图形中哪些部分落在显示区之内,以便显示落在显示区内的那部分图形。这个选择过程称为裁剪裁剪只有窗口内的物体才能显示出来。因此，窗口之外的物体都是不可见的，可以不参加标准化转换及随后的显示操作，节约处理时间。裁剪（clipping）是裁去窗口之外物体的一种操作。 图形反走样算法图形反走样算法 剖面线算法剖面线算法 剖面线是一组等距的平行线，用填充算法速度慢，直接画线更快，算法步骤： i

11、) 按多边形的初始条件及剖面线的角度和间距，计算剖面线的范围和数量；ii) 求剖面线与轮廓边的相交位置；iii）对剖面线上的交点进行排序，并按奇偶规则绘制有效剖面线段。 简化算法：跳过顶点处交点判断如图所示，画出的直线实际上是阶梯状，并不光滑。因为计算机屏幕是离散象素组成，不是连续信号。象素是有面积的，不可能面积为零。 线段反走样算法：线段反走样算法：将线段处理为有宽度的狭长矩形抖动反走样算法：抖动反走样算法：高分辨率计算，低分辨率显示 3.2 图形变换 图形变换的数学基础 向量运算 矩阵运算 二维变换 三维变换3.2.1 二维变换 点的变换可以通过矩阵运算来实现，令 dcbat称t为变换矩阵

12、，有： dybxcyaxdcbayx y x 这里x,y为变换后点的坐标，x,y为变换前点的坐标，变换矩阵中a,b,c,d的不同取值，可以实现各种不同变换，从而达到对图形进行变换的目的 。 二维基本变换 比例变换 对称变换 错切变换 旋转变换 平移变换 二维组合变换比例变换在变换矩阵 中，令b=c=0，则为比例变换矩阵 dcbat0d, ad00ats其中a，d分别为x，y方向上的比例因子对称变换对坐标轴的对称变换对坐标轴的对称变换1-001tmx2.对x轴对称:1.对y轴对称:1001-tmy对原点的对称变换对原点的对称变换: : 1-001-tmo旋转变换 在二维空间里，我们作如下规定：图

13、形的旋转是指绕坐标系原点旋转角，且逆时针为正，顺时针为负，变换矩阵为cossinsincostrxsinycossinrcoscosrsinrsin yysinxcossinrsincosrcosrcos x 对字母t进行旋转变换（旋转60)平移变换 这里x，y是平移量，应为常数，但是应用上述变换矩阵对点进行变换 而这里的cy，bx均非常量，因此用原来的因此用原来的2 22 2的变的变换矩阵是无法实现平移变换。换矩阵是无法实现平移变换。 上述四种变换都可以通过变换矩阵来实现，但是，若实现平移变换，变换前后的坐标必须满足下面的关系dcbatyyyxxxdybxcyaxdcbayxyx将变换矩阵增

14、加一行一列，实施对点进行平移变换1101000111mylxmlyxyx齐次坐标 在平移变换中，我们将x y扩充为x y 1 实际上是由二维向量变为三维向量。 这种用三维向量表示二维向量的方法叫做齐次坐标法。进一步推广，用n+1维向量表示n维向量的方法称之为齐次坐标法。 所谓齐次坐标就是用n+1维向量表示n维向量得到的坐标。对齐次坐标进行坐标变换称为齐次变换，相应的变换矩阵称为齐次变换矩阵。 设三维空间点p的坐标为(x,y,z)，它是唯一的。若用齐次坐标表示时，则为(hx,hy,hz,h)，且不唯一。齐次坐标的几何意义 将oxy坐标系增加一与x轴和y轴正交的w轴。 在w=1的平面上有点p1(x

15、,y,1),则当w由0变化到无穷时，齐次坐标p pw w(x(xw w,y,yw w,w,w) ) 将处在由op1定义的射线oq上。二维坐标则是该射线在w1平面上的交点,有wyy,wxxww 二维齐次变换表示了在w=1平面上点的坐标变换，即p1到p1*的坐标变换齐次坐标的特点1. 当w=0时，齐次坐标可用来表示无穷远的点2. 将图形处理中的各种变换用统一的方式来处理如二维图形变换矩阵的一般表达式：3. 齐次变换矩阵通常是非奇异矩阵。当该矩阵奇异时，det a a = 0，坐标经变换后维数将降低，如三维坐标在二维平面上的投影变换等。smlqdcpbatsmlqdcpba11yxyx二维齐次变换矩

16、阵 其中22阶矩阵 可以实现图形的比例、对称、错切、旋转等基本变换； 12阶矩阵 可以实现图形的平移变换； 21阶矩阵 可以实现图形的透视变换， 而s可以实现图形的全比例变换。dcbamltqp小结二维组合变换 上述的几种变换可用统一的变换矩阵形式来实现，称之基本变换。 但有些变换仅用一次基本变换是不够的，必须由两次或多次基本变换组合才能实现。这种由多种基本变换组合而成的变换称之为组合变换，相应的变换矩阵叫做组合变换矩阵。设坐标p经过n次变换t1,t2,tn到p*，则变换结果为： p* = pt1t2tn = pt 式中，t = t1t2tn 为总的变换矩阵，组合变换的目的是将一个变换序列表示

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

18、次)变换矩阵：t 齐次变换矩阵：平移缩放旋转错切透视变换整体缩放比例和对称变换1000000000000tszyxsssst1zyx1zyx1.一般情况，sx,sy,sz0，图形沿三个坐标轴方向作放缩变换；2.当sx=1,sy=sz=-1时，图形相对于x轴中心对称，其余类推;3.当sx-1,sy=sz=1时，图形相对于yoz平面对称，其余类推;4.当sx=sy=sz=-1时，图形相对于原点中心对称。整体缩放得到：左边同乘 s s000010000100001tsst1zyx1zyx szyx1 z y x平移变换 tt1zyx1 z y x1ttt010000100001txtzy平移变换矩阵

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

20、转角度为（图(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 。 注意： 10000cossin00sincos000012aaaa 10000cos0sin00100sin0cos3 10100001000011111zyx 1000010000cossin00sincos4

21、其组合变换矩阵为： t t1 t2 t3 t4 t3-1 t2-1 t1-1例：简单几何体的图形变换例：简单几何体的图形变换tzyxzzyyxxzyxzzyyxx111111888212121888212121式中：t为所要进行的图形变换矩阵 假定一六面体abcdefgh各点的坐标分别为（x 1, y 1, z 1）,., (x 8, y 8, z 8)，则经过图形变换后的坐标为：3.2.3 投影变换将三维图形向二维平面上投影生成二维图形表示的过程称为投影变换。根据视点的远近，投影分为平行投影和透视投影。当投影中心(观察点)与投影平面之间的距离为无穷远时，为平行投影，否则为透视投影。透视投影的

22、图形与眼睛观察景物的原理及效果是一致的，因而常用于图形的真实效果显示。由于平行投影后直线间的平行关系不变，因而它常用于三维图形交互和生成工程图的视图。投影变换分类:投影平行投影透视投影正平行投影斜平行投影正交投影正轴测投影正等测投影正二测正三测斜等测斜二测一点透视二点透视三点透视正交投影投影方向垂直于投影平面时称为正平行投影，正交投影（也称正投影）是正平行投影的特殊形式，其投影平面相互垂直，常用于生成工程图的三视图正交投影 设模型坐标为p(x,y,z)，投影坐标系的x轴向右，y轴向上，z轴垂直于纸面向外，投影后的坐标为p(x,y,z)，有 ppa，a为投影变换矩阵，可以看成从投影坐标系到模型坐

23、标系的变换矩阵。 在采用第一角画法的三视图中，各视图的投影矩阵为 10001000000001avvvyx10000000100001ahhhyx10001000010000awwwyx 主视图 俯视图 左视图平移量 轴测投影将三维图形绕其模型坐标系的x轴和y铀分别旋转一定的角度后，再垂直于xoy平面向该平面投影，可获得具有立体感的轴测图。或者，当视点在模型空间的任意位置e(a,b,c)向坐标原点观察时，将图形沿观察方向向垂直于视线的平面投影，也可以得到轴测图，a=b=c时为正等测投影。在应用中常采用输入视点坐标的方式来确定轴测投影的方向，它比绕两轴旋转给定角度的几何意义更明确。正轴测投影变换

24、将坐标系作两次旋转变换trz(90+)和trx()，其中trz(90+)使视线oe与新坐标系的yoz平面重合，y轴方向与ao重合，trx()使新坐标系的z”轴指向视点。 hrxrzatptp90*透视投影 透视投影的视线（投影线）是从视点（观察点）出发，视线是不平行的。不平行于投影平面的视线汇聚的一点称为灭点，在坐标轴上的灭点叫做主灭点。主灭点数和投影平面切割坐标轴的数量相对应。按照主灭点的个数，透视投影可分为一点透视、二点透视和三点透视。 一点透视的投影(z) pprppprpvpppvphhhdzdzzddzzyxhzyx/)/(00/ 1/00001000011坐标变换 假定有两个坐标系

25、oxyz和ouvn，见右图： nvuozoyx在坐标系oxyz中，o的坐标为（ox， oy， oz）, ou 、ov 和on分别为三个单位矢量（ux,uy,uz）、（vx,vy,vz）和（nx,ny,nz），要将坐标系oxyz 中的图形变换到坐标系ouvn中去，称该坐标变换为t xyzuvn ，其变换为：10000001010000100001zzzyyyxxxzyxnvunvunvuoooxyz1 = x y z 1 txyz1 t-1 = x y z 1注：图形变换也可由坐标变换得到，且变换矩阵互逆注：图形变换也可由坐标变换得到，且变换矩阵互逆则点的坐标计算：3.3 图形显示流程 在图形学

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