吉林大学计算机图形学资料汇总

1、 名词解释*计算机图形学是指用计算机产生对象图形的输出的技术。更确切的说，计算机图形学是研究通过计算机将数据转换为图形，并在专门显示设备上显示的原理、方法和技术的学科。*图形学的主要研究内容：图形的生成和表示技术；图形的操作和处理方法；图形输出设备与输出技术的研究；图形输入设备、交互技术和用户接口技术的研究；图形信息的数据结构及存储、检索方法；几何模型构造技术；动画技术；图形软硬件的系列化、模块化和标准化的研究；科学计算的可视化*能够正确地表达出一个对象性质、结构和行为的描述信息，成为这个对象的模型。*图像处理是指用计算机来改善图像质量的数字技术。*模式识别是指用计算机对输入图形进行识别的技术

2、。*计算几何学是研究几何模型和数据处理的学科。*交互式计算机图形学是指用计算机交互式地产生图形的技术。*计算机图形系统的硬件包括五部分：计算机、显示处理器、图形显示器、输入设备、硬拷贝设备。*CRT图形显示器工作方式有两种：随机扫描方式和光栅扫描方式。*随机扫描方式的图形显示器通过画出一系列线段来画出图形。*一帧：扫描过程所产生的图像。*像素：在光栅扫描图形显示器中，屏幕上可以点亮或熄灭的最小单位。*分辨率：显示屏上像素的总数。*帧存储器：二维矩阵，帧存储大小=分辨率*单元字节，存储屏幕上每个像素对应的颜色或亮度值。*屏幕上每个像素对应的颜色或亮度值要存储在帧存储器中。*将图形描述转换成用像素

3、矩阵表示的过程称为扫描转换。*在光栅扫描显示方式中像素坐标是行和列的位置值，只能取整数。*图形基元（输出图形元素）：图形系统能产生的最基本图形。*区域是指光栅网络上的一组像素。*区域填充是把某确定的像素值送入到区域内部的所有像素中。*区域填充方法：一类方法是把区域看做是由多边形围成的，区域事实上由多边形的顶点序列来定义，相应的技术称为是以多边形为基础的；另一类方法是通过像素的值来定义区域的内部，这时可以定义出任意复杂形状的区域。相应的技术称为是以像素为基础的。*通过像素的值的定义区域有两种常用的方法。一种是内定义区域，另一种是由边界定义区域。*以像素为基础的区域填充主要是依据区域的连通性进行。

4、*四连通区域是指从区域的一个像素出发，经过连续地向上、下、左、右四个相邻像素的移动，就可以到达区域内的任意另一个像素的区域。（四联通区域必是入连通的，反之未必）*八连通：如果除了要经上下左右的移动，还要经左上、右上、左下和右下的移动，才能由一个像素走到区域中另外任意一个像素。*利用区域的连通性进行区域填充，除了需要区域应该明确定义外，还需要事先给定一个区域内部像素，这个像素称为种子。做区域填充时，要进行对光栅网格的遍历。*像素段：将区域内由边界点限定的同一行内相连接的不具有新值newvalue的一组像素称为一个像素段，像素段用它最右边的像素来标识。*奇偶性质：即一条直线与任意封闭的曲线相交时，

5、总是从第一个交点进入内部，再从第二个交点退出，以下交替的进入退出，即奇数次进入，偶数次退出。当然可能有一些“相切”的点应特殊处理。*活跃边：与当前扫描线相交的边。*活跃边表AET：存贮当前扫描线相交的各边的表。*边表ET：记录多边形的所有边。*“吊桶”中各项的内容一次是：1、边的另一端点的较大的y坐标ymax；2、与较小的y坐标对应的边的断电的x坐标xmin；3、斜率的倒数，1/m。*栅栏：指一条与扫描线垂直的线，把多边形一分为二。*规范化设备坐标系：图形系统为具体设备无关的引入，是二维正方形或三维正方体，即各坐标范围规定为从0到1。*常见的基本二维图形几何变换有：平移变换、比例变换和旋转变换

6、。*本体坐标系（模型坐标系）：为规定基本形体而引入的便于描述的坐标系。*用户坐标系（世界坐标系）：用户引入描述整个形体的坐标系。*观察坐标系（视觉坐标系/目坐标系）：为说明观察姿态而引入，也就是观察者所处的位置。*设备坐标系（显示器坐标系/屏坐标系）：是各种图形设备自身规定的在显示表面上采用的坐标系。*齐次坐标表示法就是用n+1维向量表示一个n维向量。*窗口就是在用户坐标系中指出的那个要显示出来的区域，这一区域通常为矩形区域*通常把整个显示屏幕区域称作屏幕域，它是设备输出图形的最大区域，是有限的区域。*视见区是屏幕域中的一个子区域，通常为矩形区域，它最大与屏幕域等同。视见区用于显示窗口中的图形

7、。*窗口与视见区的差别在于：窗口是在用户坐标系中确定的，它指出了要显示的图形，也就是我们想要看见什么；而视见区在设备坐标系中确定，它指出了实际显示的图形处于显示屏幕的哪一部分，也就是我们要用显示屏幕的哪部分实际去看。视见区在设备坐标系中定义，也可以用矩形区域的左下角点和右上角点的坐标来表示。*视见变换：就是将用户坐标系窗口内的图形变换到显示屏幕设备坐标系的视见区中以产生显示。*投影就是把n维空间中的点投射到小于n维的空间中去。*投影是如何形成的：首先在三维空间中确定一个投影中心和一个投影平面，然后从投影中心引出一些投射直线，这些直线通过形体上的没一点，与投影平面相交，在投影平面上就形成了形体的

8、投影。*平行投影：当投影中心与投影平面的距离为无穷远时，投射直线成为一组平行线，这种投影称为平行投影。*透视投影：当投影中心与投影平面的距离是有限数值时，投射直线交于一点，形成灭点，这种投影称为透视投影。*平行投影可以分为两种类型：正交投影和斜交投影。*正交投影：投影方向与投影平面的法向相同。即投影方向垂直于投影平面。*常见的正交投影（三视图）：正视投影、顶视投影、侧视投影。*正投影：投影平面垂直于坐标轴的正交投影。（正视投影、顶视投影和侧视投影）*等轴投影：投影方向与三个坐标轴的夹角都相等。这种投影能使在三个坐标轴方向上有相等的透视缩短。*斜交投影：投影方向与投影平面的法向不同。*常见的斜交

9、投影：斜二侧投影和斜等轴投影。在斜交投影中，投影平面一般取坐标平面。*斜二侧投影：垂直于投影平面的线段长度缩短为原来的一半。*斜等轴投影：使垂直于投影平面的线段仍保持长度。*透视投影性质：任意一组平行直线，如果平行于投影平面，则经透视投影后所得到的直线或者重合，或者仍保持平行；如果不平行于投影平面，将不再保持平行，并且必会汇聚于同一点。*消失点（灭点）：任意一组不平行于投影平面的平行直线，投影后所得的直线，必将汇聚于同一点。消失点可以取任意多个。*主消失点：三维直角坐标系中，透视投影时，如果一组平行直线平行于三个坐标轴中的一个，那么对应的消失点将落在坐标轴上。最多只有三个主消失点。*裁剪：去掉

10、窗口外的不可见部分，保留窗口内的可见部分的过程。*三维图形显示的处理流程:Z方向深度裁剪à世界坐标变换T1à投影T2à窗口至视窗的变换T3à至物理设备变换T4à裁剪à显示*参数曲线的构造方法：曲线上每一点的坐标均要表示成某个参数t的一个函数式，则曲线上每一点笛卡尔坐标参数式是：x=x(t)，y=y(t)，z=z(t)；把三个方程合写到一起，曲线上一点坐标的向量表示是：P(t)=x(t) y(t) z(t)；如用“'”表示对参数求导，则P(t)关于参数t的切向量或导函数是：P(t)=x(t) y(t) z(t)。类似地，曲面写为

11、参数方程形式为：x=x(u,w)，y=y(u,w)，z=z(u,w)；写成向量形式，则是：P(u,w)=x(u,w)，y(u,w)，z(u,w)*参数方程的优点：1）对非参数方程表示的曲线、曲面进行变换，必须对曲线、曲面上的每个型值点进行几何变换；而对参数表示的曲线、曲面可对其参数方程直接进行几何变换（如平移、比例、旋转），从而节省计算工作量。2）便于处理斜率为无限大的问题。3）有更大的自由度来控制曲线、曲面的形状。同时对于复杂的曲线和曲面具有很强的描述能力和丰富的表达能力。4）参数方程中，代数、几何相关和无关的变量是完全分离的，而且对变量个数不限，从而便于用户把低维空间中的曲线、曲面扩展到高

12、维空间去。这种变量分离的特点使我们可以用数学公式去处理几何分量，同时可以使曲线和曲面具有统一的表示形式。5）规格化的参数变量t0，1，使其相应的几何分量是有界的，而不必用另外的参数去定义其边界。它便于曲线和曲面的分段、分片描述，易于实现光顺连接。6）易于用向量和矩阵表示几何分量，计算处理简便易行。*计算机上表现的曲线和曲面，大体上可分为两类：一类要求通过事先给定的离散的点，称为插值的曲线或曲面。另一类不要求通过事先给定的各离散点，而只是用给定各离散点形成的控制多边形来控制形状，成为逼近的曲线或曲面。事先给定的离散点常称为型值点，由型值点求插值的或逼近的曲线或曲面的问题，称为曲线或曲面的拟合问题

13、。*插值：要求构造一条曲线顺序通过型值点，称为对这些型值点进行插值。*逼近：当型值点太多时，构造插值函数使其通过所有的型值点相当困难的。此时人们往往构造一条曲线，使它在某种意义上最佳逼近这些型值点，称之为对这些型值点进行逼近。*曲线的数学表示形式：显示、隐式、参数*在计算机上表现的曲线和曲面，大体分为两类：一类要求通过事先给定的离散的点，称为插值的曲线或曲面，另一类不要求通过事先给定的各离散点，而只是用给定各离散点形成的控制多边形来控制形状，称为逼近的曲线或曲面。*光顺是指曲线的拐点不能太多，要光滑顺畅。*Bezier曲线性质：1.P(0)=P0,P(1)=P1,曲线通过所给出型值点列的起点和

14、终点2.P(0)=n(P1-P0),P(1)=n(Pn-Pn-1)曲线在始点和终点处的切线方向与它的控制多边形的第一边和最后一边的走向一致。3.曲线有对称性，4.曲线的凸包性。整条曲线都包含在所有控制点所张成的凸包中。*简述B样条曲线与Bezier之间的关系N+1个控制点P0,P1,Pn所确定的最高阶的B样条曲线是k=n+1阶的，这时由节点向量(0,0,0,1,1,1)所去顶的B样条曲线，与该n+1个控制点所确定的Bezier曲线相同。这个结论说明了B样条曲线确实是Bezier曲线的一种推广，Bezier曲线是B样条曲线的特例。*凸壳：包含一个平面点集的最小凸区域。*凸区域：指要求区域内任意两

15、点的连线仍在该区域内。*求点集S的凸壳（设S是平面上n个点的集合，则S的凸壳是一个凸多边形，它包含所有n点且面积最小）：1）在S中选出壳上的点；2）给出围成凸多边形的序列。*Graham扫面的实质是围绕已经按“倾角”排序的各顶点进行一次扫描，在扫描过程中消去在凸壳内部的点，留下以希望次序排列的壳顶点。由于是按倾角递增排序，故可知若三个顶点P1.P2.P3连续“右转”，则P2是一个应去掉的内点。*简单多边形：是平面上不相邻的边不能相交的多边形。*简单多边形做三角剖分：要求选出完全在内部又互不相交的一组对角线，把整个多边形划分成一些三角形。（对角线是不相邻顶点间的连线）*简单多边形的三角剖分：是选

16、出的对角线的集合。*最小权三角剖分（最小三角剖分）：一个三角剖分中选取的对角线的总长度最小。*与空间任意形体有关的信息可以分为：图形信息和非图形信息两类。*图形信息指构成它们的点、线、面的位置，互相关系及大小等。*非图形信息指形体的颜色、亮度、质量、体积等一些性质。*图形信息包括：1、几何信息：形体在空间的位置和大小。2、拓扑信息：组成形体各部分的数目及相互间的连接关系。*形体的表示方法通常可分为两类：1、边界表示：用边界将形体分为内部和外部。2、空间分区表示：描述形体的内部性质，将包含形体的空间区域划分为一组小的非重叠的连续实体。*曲线的表示法：1、折线法：就是用多段线段形成的折线去逼近曲线

17、。2、带树法：带树就是一棵二叉树，树的每个结点对应一个矩形带段，这样每个结点可由八个字段组成，前六个字段描述矩形带段，后二个是指向两个子结点的指针，即矩形带段的起点是（xb，yb），终点是（xe，ye）。相对从起点到终点的连线，矩形有两边与之平行，两边与之垂直，平行两边与之距离分别为wl和wr。*三种四叉树的存储结构，即规则方式、线性方式、一对四方式*四叉树优点（与像素阵列表示）：1）节省存储空间；2）可以用不同精度来表示；3）与设备无关，便于移植。*形体的模型：主要指的就是包含图形信息所形成的模型。*几何元素：形体本身的构造有一定的层次性，底层部分组合构成上一层部分，而上一层部分组合又可以构

18、成更高一层的部分，依次类推可形成多层结构。其中，每一层中的部分，我们把它又称为几何元素。*消除隐藏面（面消隐）：确定可见面等价于消除场景中物体的不可见面。*消除隐藏线（线消隐）：显示采用线框模型表示的物体时，要消除不可见的线。*面消隐算法分两大类：1、图像空间算法：对显示设备上每一个可分辨像素进行判断，看组成物体的多个多边形表面中哪一个在该像素上可见，既要对每一像素检查所有的表面。2、客体空间算法：把注意力集中在分析要显示形体各部分之间的关系上，这种算法对每一个组成形体的表面，都要与其它各表面进行比较，以便消去不可见的面或面的不可见部分。*可见面：朝向观察位置的面。*范围检查：即为最大最小检验

19、，通过比较有关的最大或最小值来实现。*点：是0维几何元素，有端点、交点、切点、孤立点等形式。*边：是一维几何元素，是两个邻面（正则形体）或多个邻面（非正则形体）的交界。*环：有序有向边（直线段或曲线段）组成的面的封闭边界。*面：是二维几何元素，是形体上一个有限、非零的区域，它由一个外环和若干个内环所界定。*体是三维几何元素，由封闭表面围成的空间，它是欧氏空间R3中非空、有界的封闭子集，其边界是有限面的并集。*体素：是可以用有限个尺寸参数定位和定型的体。*形体的层次结构：点 -> 边 -> 环 -> 面 -> 外壳 -> 形体*常用的多面体三表表示法是：顶点表，边表

20、，面表*通常用正则集合运算来实现这种组合。*确定可见面等价于消除场景种物体的不可见面，即消除隐藏面（面消隐）*消隐面算法大体分为两个大类，即图像空间算法和客体空间算法。*图像空间算法把注意力集中在最终形成的图形上。客体空间算法把注意力集中在分析要显示形体各部分之间的关系上。*范围检查又称为最大最小检验。设平面上四点设平面上四点(1，1)，(2，3)，(4，3)，(3，1)确定的Bezier曲线是P(t)，如果在点P(1/2)处将它分为两段，求前后两段做为Bezier曲线各自的四个控制点坐标。解答：使用分裂法，有：P0(1,1)R0P1(2,3)R1P2(4,3)R2P3(3,1)R3R0=(3

21、/2,2)R1=(3,3)R2=(7/2,2)R0=(9/4,5/2)R1=(13/4,5/2)R0=(11/4,5/2)i=0i=1i=2Q0Q1Q2Q3前半段四个控制点Q0(1,1)，Q1(3/2,2)，Q2(9/4,5/2)，Q3(11/4,5/2)，0t1/2；后半段四个控制点R0(11/4,5/2)，R1(13/4,5/2)，R2(7/2,2)，R3(3,1)，1/2t1。*用计算机在图形设备上生成真实感图形必须完成四个基本的任务。第一用数学方法建立所构造三 维场景的几何描述，并将它们输入至计算机。第二,将三维几何描述转换为二维透视图。第三,确定场景中的所有可见面，这需要使用隐藏面消

22、除算法将被其它物体遮挡的不可见面消去。第四 计算场景中可见面的颜色，严格地说，就是根据基于光学物理的光照明模型计算可见面投射到观察者眼中的光亮度大小和颜色组成，并将它转换成适合图形设备的颜色值，从而确定投影画面上每一象素的颜色，最终生成图形。*设计一个光照模型需要考虑的主要问题是照明特性、表面特性和观察角度光照模型可以分解为三个部分，即漫射照明，具体光源的照射和透射效应具体光源在物体表面可以引起漫反射和镜面反射。亮度公式：I=IaKa+IpKd(L*N)Phong Bui Tuong 提出的光照明模型，用cosna来近似表示反射光线引起的亮度随着a增大而下降的速率。N的取值一般在02000之间

23、，决定于反射表面的有关性质。对于理想的反射表面，n就是无穷大。这里选用cosna，是以观察经验为基础的。对实际物质来说，被镜面反射的入射光的数量与入射角B有关，如果将镜面反射光的百分数记为W(B)，那么久可以将计算表面亮度的公式I=IaKa+IpKd(L*N)/(r+k)修改得到I=IaKa+Ip/(r+k)*Kd(L*N)+Ks(R*V)n方*$8深度暗示技术首先，再投影坐标系中定义两个平面Z=Zf,Z=Zb,分别为前参考面和后参考面，并赋予比例因子Sf和Sb(Sf,Sb(-0,1)。给定物体上一点的深度值Z0,该点对应的比例因子S0这样来确定1)当Z0>Zf时，取S0=Sf 2)当Z

24、0<Zb时，取S0=Sb 3)当Z0(- Zb,Zf时，S0=Sb+(Sf-Sb)/(Zf-Zb)*(Z0-Zb)原亮度I按比例S0与亮度Idc混合，目的是活的最终用于显示的亮度I,Idc由用户指定：I=S0I+(1-S0)Idc 若取Sf=1,Sb=0,Idc=0,则当物体位于前参考面之前时，I=I.即亮度没有被衰减；当物体位于后参考面之后，I=Idc=0，即亮度被衰减为0，else I=S0I,亮度被部分衰减。*Phong方法绘制多边形步骤1) 计算多边形的单位法向量2) 计算多边形顶点的单位法向量。3) 再扫描线消隐算法中，对多边形顶点的法向量进行双线性插值，计算出多边形内部各点法

25、向量1. 当扫描线y递增一个单位，变为y+1时，Na,Nb的增量分别为Na,Nb2. 当x递增一个单位时Np增量为Np4) 利用光照模型计算P点的颜色 解答题*计算机图形学是指用计算机产生对象图形的输出的技术。更确切的说，计算机图形学是研究通过计算机将数据转换为图形，并在专门显示设备上显示的原理、方法和技术的学科。*图形学的主要研究内容：图形的生成和表示技术；图形的操作和处理方法；图形输出设备与输出技术的研究；图形输入设备、交互技术和用户接口技术的研究；图形信息的数据结构及存储、检索方法；几何模型构造技术；动画技术；图形软硬件的系列化、模块化和标准化的研究；科学计算的可视化*与计算机图形学相关

26、的学科及它们之间的关系： 对象的描述 à计算机图形学 模式识别ß对象的图形图像处理图像处理是指用计算机来改善图像质量的数字技术。模式识别是指计算机对输入图形进行识别的技术。*计算机图形系统的硬件包括五部分：计算机、显示处理器、图形显示器、输入设备、硬拷贝设备。*CRT图形显示器工作方式有两种：随机扫描方式和光栅扫描方式。*窗口与视见区的差别在于：窗口是在用户坐标系中确定的，它指出了要显示的图形，也就是我们想要看见什么；而视见区在设备坐标系中确定，它指出了实际显示的图形处于显示屏幕的哪一部分，也就是我们要用显示屏幕的哪部分实际去看。视见区在设备坐标系中定义，也可以用矩形区域的

27、左下角点和右上角点的坐标来表示。*投影的形成过程：首先在三维空间中确定一个投影中心和一个投影平面，然后从投影中心引出一些投射直线，这些直线通过形体上的没一点，与投影平面相交，在投影平面上就形成了形体的投影。*三维图形显示的处理流程:Z方向深度裁剪à世界坐标变换T1à投影T2à窗口至视窗的变换T3à至物理设备变换T4à裁剪à显示*参数曲线的构造方法：曲线上每一点的坐标均要表示成某个参数t的一个函数式，则曲线上每一点笛卡尔坐标参数式是：x=x(t)，y=y(t)，z=z(t)；把三个方程合写到一起，曲线上一点坐标的向量表示是：P(t)=x

28、(t) y(t) z(t)；如用“'”表示对参数求导，则P(t)关于参数t的切向量或导函数是：P(t)=x(t) y(t) z(t)。类似地，曲面写为参数方程形式为：x=x(u,w)，y=y(u,w)，z=z(u,w)；写成向量形式，则是：P(u,w)=x(u,w)，y(u,w)，z(u,w)*参数方程的优点：1）对非参数方程表示的曲线、曲面进行变换，必须对曲线、曲面上的每个型值点进行几何变换；而对参数表示的曲线、曲面可对其参数方程直接进行几何变换（如平移、比例、旋转），从而节省计算工作量。2）便于处理斜率为无限大的问题。3）有更大的自由度来控制曲线、曲面的形状。同时对于复杂的曲线和曲

29、面具有很强的描述能力和丰富的表达能力。4）参数方程中，代数、几何相关和无关的变量是完全分离的，而且对变量个数不限，从而便于用户把低维空间中的曲线、曲面扩展到高维空间去。这种变量分离的特点使我们可以用数学公式去处理几何分量，同时可以使曲线和曲面具有统一的表示形式。5）规格化的参数变量t0，1，使其相应的几何分量是有界的，而不必用另外的参数去定义其边界。它便于曲线和曲面的分段、分片描述，易于实现光顺连接。6）易于用向量和矩阵表示几何分量，计算处理简便易行。*计算机上表现的曲线和曲面，大体上可分为两类：一类要求通过事先给定的离散的点，称为插值的曲线或曲面。另一类不要求通过事先给定的各离散点，而只是用

30、给定各离散点形成的控制多边形来控制形状，成为逼近的曲线或曲面。事先给定的离散点常称为型值点，由型值点求插值的或逼近的曲线或曲面的问题，称为曲线或曲面的拟合问题。*Bezier曲线性质：1.P(0)=P0,P(1)=P1,曲线通过所给出型值点列的起点和终点2.P(0)=n(P1-P0),P(1)=n(Pn-Pn-1)曲线在始点和终点处的切线方向与它的控制多边形的第一边和最后一边的走向一致。3.曲线有对称性，4.曲线的凸包性。整条曲线都包含在所有控制点所张成的凸包中。*简述B样条曲线与Bezier之间的关系N+1个控制点P0,P1,Pn所确定的最高阶的B样条曲线是k=n+1阶的，这时由节点向量(0

31、,0,0,1,1,1)所去顶的B样条曲线，与该n+1个控制点所确定的Bezier曲线相同。这个结论说明了B样条曲线确实是Bezier曲线的一种推广，Bezier曲线是B样条曲线的特例。*Graham扫面的实质是围绕已经按“倾角”排序的各顶点进行一次扫描，在扫描过程中消去在凸壳内部的点，留下以希望次序排列的壳顶点。由于是按倾角递增排序，故可知若三个顶点P1.P2.P3连续“右转”，则P2是一个应去掉的内点。*形体的表示方法通常可分为两类： 1、边界表示：用边界将形体分为内部和外部。 2、空间分区表示：描述形体的内部性质，将包含形体的空间区域划分为一组小的非重叠的连续实体。*曲线的表示法：1、折线

32、法：就是用多段线段形成的折线去逼近曲线。2、带树法：带树就是一棵二叉树，树的每个结点对应一个矩形带段，这样每个结点可由八个字段组成，前六个字段描述矩形带段，后二个是指向两个子结点的指针，即矩形带段的起点是（xb，yb），终点是（xe，ye）。相对从起点到终点的连线，矩形有两边与之平行，两边与之垂直，平行两边与之距离分别为wl和wr。*面消隐算法分两大类：1、图像空间算法：对显示设备上每一个可分辨像素进行判断，看组成物体的多个多边形表面中哪一个在该像素上可见，既要对每一像素检查所有的表面。2、客体空间算法：把注意力集中在分析要显示形体各部分之间的关系上，这种算法对每一个组成形体的表面，都要与其它

33、各表面进行比较，以便消去不可见的面或面的不可见部分。*用计算机在图形设备上生成真实感图形必须完成四个基本的任务。第一用数学方法建立所构造三 维场景的几何描述，并将它们输入至计算机。第二,将三维几何描述转换为二维透视图。第三,确定场景中的所有可见面，这需要使用隐藏面消除算法将被其它物体遮挡的不可见面消去。第四 计算场景中可见面的颜色，严格地说，就是根据基于光学物理的光照明模型计算可见面投射到观察者眼中的光亮度大小和颜色组成，并将它转换成适合图形设备的颜色值，从而确定投影画面上每一象素的颜色，最终生成图形。 算法分析&5.简单多边形包含性检验的算法：1.【准备】XnßX0,yn&

34、#223;y0,mß -1,iß02.【排除必不相交情形】若下列条件有一个成立，则到41)xp<x,&&xp<xi+12)xp>=xi&&xp>=xi+13)xp<y&&yp<yi+13.【计算交点】y=yi+(xp-xi)(yi+1 - yi)/(xi+1 - xi)分两种情形：1)若y=yp,则P在多边形边界上，算法结束2)若y<yp，则 mß(-1)m;4.【结束判断】ißi+1，若i<n,则返回到2，否则算法结束，此时若m = -1 则点P在多边形外部

35、，m=1,则在内部。*简述扫描线种子填充算法的工作步骤。1， 对种子所在的像素段进行填充2， 从右到左检查种子所在行的上一横行，将查到的像素段依次编号存入堆栈。实际存入堆栈内的可以是每个像素段最右边像素的地址。接着对种子所在行的下一横行同样处理。3， 若堆栈为空则算法结束，否则从堆栈顶部取出一个像素段。因为按先进后出的顺序，所以将取出编号最大的像素段。实际取出的是这个像素段最右边像素的地址。就以这个像素为新的种子，返回到1.写出Graham凸壳求解算法1.(倾角排序)选出输入电集S中X坐标最小的点，若这样的点不唯一则再由其中选出y坐标最小的点，设为O.设想有一条从O向右的射线OX,对点集中其余

36、每一点P,计算倾角POX,再按倾角排序，得到点序列Q1=O,Q2,Q3,Qn;2.(准备扫描)vßQ1;3.(扫描)若NEXT(v) != Q1,则循环执行下面的操作至NEXT(v)=Q1时止，此时点序列中剩下排成凸多边形的壳上顶点，算法结束。若三个相继的点v, Next(v), Next(NEXT(v)形成一个左转，则vßNEXT(v);否则先删除NEXT(v),再做vßPRED(v);*写出Jarvis凸壳求解算法1(准备)v0ß点集S中按x,y字典次序最小的点；dß竖直向下的一个方向向量；点v0送入收集凸壳顶点的队列Q中；S1ß

37、S u,v0；ußv02(一步行进)v1ßWrapping(u,d,S1);S1中各点相对于自u出发方向为d的射线，计算倾角，取倾角最小的点，若倾角相同，取与u距离最远的点，Wrapping(u,d,S1);返回下一个壳顶点。3(准备下次) if v1 != v0,v1送入Q中；S1 = S u,v1; dß从u到v1的一个方向向量； ußv1;返回步骤24(结束)Q中存入所有的壳顶点，算法结束*试写出判定一空间多边形与一凸多面体之间关系的算法1. 求出空间多边形和凸多面体的包围盒分别做x,y,z三向测试，若包围盒检查(最大最小检验)有一个为真，则空间多

38、边形和凸多面体分离。算法输出分离并结束。2. 一次用凸多面体的每一表面多边形来求解与空间多边形各边的交点若有交点，测试空间多边形的顶点是否均在凸多面体内，若均在体内，则为包含；若有交点，测试空间多边形的顶点有内有外，则相交；若无交点，测试空间多边形的顶点是否在凸多面体内，若均在体内，则为包含；若无交点，测试空间多边形的顶点均在凸多面体外，则为分离。7.1线面比较法消除隐藏线1）、消除隐藏线的线面比较法的最先一步就是利用外法线判断出所有可能的可见面。2）、做xv方向和yv方向的范围检查。3）、接着做zv方向的范围检查，即粗略的深度比较。4）、进行精确的深度比较。比较时，应计算线段两端点在可能遮挡

39、它的平面上的投影点，比较相应的z坐标。如果z1z1并且z2z2，则线段不会被遮挡；如果z1z1并且z2z2，则线段有可能被遮挡，还需要做进一步检查。如果不是上述两种情况，必发生线段与表面相交。这时，需要用交点，这些交点把线段的投影分成两部分。判断得知线段确实被平面遮挡了哪些部分。5）、做精确计算。计算是求出线段的投影与遮挡平面上多边形表面边框投影的所有交点，这些交点把线段的投影分成可见和不可见的一些子线段。对子线段的可见性，先取其上一点做点的包含性检验来进行判断。7.3*深度排序(优先级)算法1.把所有的多边形按顶点最大z坐标值进行排序。2.解决当多边形在z坐标范围内发生交迭时出现的不明确问题

40、1)多边形的x坐标范围不相交迭，所以多边形不相交迭2)多边形的y坐标范围不相交迭，所以多边形不相交迭3）P完全在Q远离观察点的一侧4）Q完全在P靠近观察点的一侧5）多边形在z=0平面上的投影本身不相交迭。实现这个检查可以检查一个多边形的每条边与另一个多边形的每条边是否相交。若这步检查为真，则两个多边形也是互补遮挡的。如果上述5步检查都为假，就假定P遮挡了Q,交换P和Q在排序表中的位置。事实上，P不一定遮挡Q,所以交换后应该重新上述5步的检查。3.按最大z坐标值逐次减小的次序，对每个多边形进行扫描转换。|7.5*深度缓存算法(Z-Buffer)的基本工作流程。帧缓冲区置成背景色；Z-缓冲区置成最

41、大z值；For(各个多边形)扫描转换该多边形for(计算多边形所覆盖的每个像素(x,y) 计算多边形在该象素的深度值Z(x,y);If(Z(x,y)小于Z缓冲区中的(x,y)处的值)把Z(x,y)存入Z缓冲区中(x,y)处;把多边形在(x,y)处的亮度值存入更新缓存区(x,y)处*对Z缓冲算法进行改进，只用一个缓冲存储器实现消隐。Z-Buffer() 帧缓存全置为背景色For(屏幕上的每个像素(I,j)深度缓存变量zb置最大值MaxValueFor(多面体上的每个多边形pk)if(像素点(I,j)在pk的投影多边形之内)计算pk在(I,j)处的深度值depth;If(depth小于zb)zb

42、= depth; indexp = k; If(zb != MaxValue)计算多边形Pindexp在交点(I,j)处的光照颜色并显示。7.7*区域分割算法（图像空间算法）区域分割算法要将投影平面分割成区域，考察区域内的图像。如果容易决定在这个区域内某些多边形是可见的，那么就可以显示那些可见的多边形，完成对这一区域的显示任务；否则，就将区域再分割成小的区域，对小的区域递归地进行判断。由于区域逐渐变小，每个区域内的多边形逐渐变小，最终总可以判定哪些多边形是可见的。在下面四种情况下，可以很容易做出判定，而不必再做进一步分割：1. 所有的多边形与区域分离，所以在区域内只显示背景值。2. 只有一个相

43、交的多边形，或者只有一个被包含的多边形。这时可以对区域首先填充背景值，然后对多边形进行扫描转换。在某些显示设备上，将整个帧存储器都初始化为背景值，可能更为方便。对于相交的多边形，只是被包含的部分被扫描转换3. 只有一个包围的多边形，没有其他的多边形。这时整个区域可填充这个包围多边形的像素值。4. 有多于一个包围的、相交的或被包围的多边形，且至少有一个包围的多边形。这时可以检查是否能有一个包围的多边形位于所有其他多边形的前面*八叉树算法：1. 遍历形体原来的八叉树T1，对遇到的每个黑节点，做下述步2.2. 对遇到黑节点对应的正立方体做相应变换，得到一般来说斜置的新位置。若这位置已超出定义八叉树的

44、充分大正立方体C之外，报告出错；否则执行下述的步3.3. 从要计算求出的目标树T2的根开始，检查2.中确定的处于新位置立方体与T2中节点对应的直立的正立方体是否相交，分以下三种情况进行处理：(1) 不相交，说明正考查直立正方体未被占据，可保持为白节点，不做处理。(2) 直立的正立方体整个被占据，即它在变换后“斜置”立方体内，置对应节点为黑节点。(3) 在上述两条都不成立时，生成当前节点的八个子节点，对八个子节点对应的八个直立子立方体，依次再递归执行步3. 如果最终这八个节点被标上同样特性，比方为黑节点，则应再删掉这八个子节点而把它们的共同父节点置为黑。*修改Cohen-Sutherland直线

45、裁剪算法，使其成为一个直线“开窗”算法，即指定一个窗口后，窗口内舍弃，窗口外保留。解答：根据题意，可知只需要对原Cohen-Sutherland算法中的两处进行修改即可满足要求。第一处是判断C1和C2的逻辑乘结果不为0时，此时如果该条件满足，表示线段完全在窗外，原算法此处需要将原线段完全舍弃，这里就需要将原线段完全绘制出来即可。第二处是最后要将原线段中窗口中可见部分绘制出来，此时原算法已经完成对原线段的裁剪，得出来原线段在窗口内的部分，这里只需要改成将原线段去掉窗口以内部分后的线段绘制出来即可。根据以上分析，修改Cohen-Sutherland直线裁剪算法为直线“开窗”算法如下：double

46、xl, xr, yt, yb; (这里事先给出窗口的位置，四个数值是已知的)，修改的部分用蓝色表示void Cohen_Sutherland(double x0, y0, x2, y2)int c, c1, c2;double x, y;/需要将原线段的端点保存起来，以备后面需要确定原线段去除窗口内部分时使用double x00=x0,y00=y0,x22=x2,y22=y2;makecode(x0, y0,c1); makecode(x2, y2, c2);while (c1!=0 | c2!=0)if (c1&c2!=0) showline(x00, y00, x22, y22);

47、/显示原线段，能走到这说明原线段都在窗口外return;c=c1; if (c=0) c=c2;if (c&1=1) y=y0+(y2-y0)*(x1-x0)/(x2-x0); x=x1;else if (c&2=2) y=y0+(y2-y0)*(xr-x0)/(x2-x0); x=xr;else if (c&4=4) x=x0+(x2-x0)*(yb-y0)/(y2-y0); y=yb;else if (c&8=8) x=x0+(x2-x0)*(yt-y0)/(y2-y0); y=yt;if (c=c1)x0=x; y0=y; makecode(x, y, c

48、1);elsex2=x; y2=y; makecode(x, y, c2);/因为原算法的线段分割保证了端点的顺序性，所以采用如下的方法可确定原线段在窗口外的部分if (x00!=x0 | y00!=y0) showline(x00,y00,x0,y0);if (x2!=x22 | y2!=y22) showline(x2,y2,x22,y22);此算法已经编码实现并测试通过。另一种方法是在分割线段的同时绘制窗口外的线段，该方法无需记录初始点坐标。double xl, xr, yt, yb; (这里事先给出窗口的位置，四个数值是已知的)，修改的部分用蓝色表示void Cohen_Sutherl

49、and(double x0, y0, x2, y2)int c, c1, c2;double x, y;makecode(x0, y0,c1); makecode(x2, y2, c2);while (c1!=0 | c2!=0)if (c1&c2!=0) /显示线段，此时绘制的是分割完后，完全在窗口外同侧的线段showline(x0, y0, x2, y2); return;c=c1; if (c=0) c=c2;if (c&1=1) y=y0+(y2-y0)*(x1-x0)/(x2-x0); x=x1;else if (c&2=2) y=y0+(y2-y0)*(xr

50、-x0)/(x2-x0); x=xr;else if (c&4=4) x=x0+(x2-x0)*(yb-y0)/(y2-y0); y=yb;else if (c&8=8) x=x0+(x2-x0)*(yt-y0)/(y2-y0); y=yt;if (c=c1)showline(x0,y0,x,y);/绘制被分割抛弃的线段x0=x; y0=y; makecode(x, y, c1);elseshowline(x,y,x2,y2);/绘制被分割抛弃的线段x2=x; y2=y; makecode(x, y, c2);DDA直线扫描转换算法 void DDALine(int x1,in

51、t y1,int x2,int y2) double dx,dy,e,x,y; dx=x2-x1; dy=y2-y1;e=(fabs(dx)>fabs(dy)?fabs(dx):fabs(dy);dx/=e;dy/=e;x=x1;y=y1;for(int i=1;i<=e;i+) SetPixel(int)(x+0.5), (int)(y+0.5);x+=dx;y+=dy;中点画线算法void MidpointLine (int x0,int y0,int x1,int y1)int a,b,delta1,delta2,d,x,y ;a = y0 - y1;b = x1 - x0;

52、d = 2 * a + b ;delta1 = 2 * a ;delta2 = 2 *( a + b);x = x0 ;y = y0 ;SetPixel(x,y);while( x<x1 )if( d<0 ) x +;y +;d+= delta2;else x +;d+= delta1;SetPixel(x,y);Bresenham画线算法void BresenhamLine(int x1,int y1,int x2,int y2)int x,y,dx,dy,p;x=x1;y=y1;dx=x2-x1; dy=y2-y1;p=2*dy-dx;for(;x<=x2;x+) Set

53、Pixel(x,y);if(p>=0) y+;p+=2*(dy-dx);elsep+=2*dy;四连通内定义区域的填充算法void Floodfill(int x,int y,COLORREF oldvalue,COLORREF newvalue) if (GetPixel(x,y) = oldvalue) SetPixel(x,y,newvalue);/赋值为新值Floodfill(x,y-1,oldvalue,newvalue);/四向扩散Floodfill(x,y+1,oldvalue,newvalue);Floodfill(x-1,y,oldvalue,newvalue);Flo

54、odfill(x+1,y,oldvalue,newvalue); 扫描线种子填充算法1对种子所在像素段进行填充。2从右至左检查种子所在行的上一横行，将查得的像素段依次编号存入堆栈。接着对种子所在行的下一横行同样处理。 3若堆栈为空则算法结束，否则从堆栈顶部取出一个像素段。就以这个像素为新的种子，返回到1。void ScanlineSeedfill(int x,int y,COLORREF boundaryvalue,COLORREF newvalue)int x0,xl,xr,y0,xid;int flag;Stack s; Point p;s.push(Point(x,y);/种子像素入栈w

55、hile(!s.isempty()p=s.pop(); /栈顶像素出栈x=p.x;y=p.y;SetPixel(x ,y ,newvalue); x0= x+1;while(GetPixel(x0,y)!=boundaryvalue)/填充右方像素SetPixel(x0 ,y ,newvalue);x0+;xr=x0-1;/最右像素x0= x-1;while(GetPixel(x0,y)!=boundaryvalue)/填充左方像素SetPixel(x0 ,y ,newvalue);x0-;xl=x0+1;/最左像素/检查上一条扫描线和下一条扫描线，/若存在非边界且未填充的像素，/则选取代表各连续区间的种子像素入栈。y0=y;for(in