1、3、 画直线的算法有哪几种？画圆弧的算法有哪几种？ c1）逐点比较法；（ 2）数值微分法；（ 3） Bresenham 算法。 画弧线的常用方法有：（ 1）逐点比较法；（ 2）角度 DDA 法；（ 3） Bresenham 算法。 4、 分别写出平移、旋转、缩放及其组合的变换矩阵。 1）平移变换： 其中， , , 是物体在三个坐标方向上的位移量。 2）旋转变换： 绕 Z 轴旋转的公式为： 绕 X 轴旋转的公式为： 绕 Y 轴旋转的公式为： 如果旋转所绕的轴不是坐标轴，设其为任意两点 p1,p2 所定义的矢量，旋转角度为 。则 可由 7个基本变换组合构成： 1 使 p1,点与原点重合； 2 ，使
2、轴 p1p2 落入平面 xoz 内； 3 ，使 p1p2 与 z轴重合； 4 ，执行绕 p1p2 轴的 角旋转； 5 ，作 3的逆变换； 1 6 ，作 2的逆变换； 7 作 1的逆变换。 3）缩放变换： 其中， ， ， 是物体在三个方向上的比例变化量。记为 。 若对于某个非原点参考点 进行固定点缩放变换，则通过如下的级联变换实现： 5、 如何用几何变换实现坐标系的变换？ 坐标系的变换，亦即将某一坐标系 lcs1 中的点 变换为另一个坐标系 lcs2 下的坐标。若 ， 矩阵的推导分三步。 1）将 lcs1 中的点变换到世界坐标系的矩阵 ; x_axis, y_axis, z_axis 为 lcs
3、1 中 x,y,z 轴矢量在世界坐标系的表示 org为 lcs1 中原点在世界坐标系的表示 2）将世界坐标系的点变换到 lcs2 中的点矩阵 ; x_axis, y_axis, z_axis 为 lcs1 中 x,y,z 轴矢量在世界坐标系的表示 org为 lcs1 中原点在世界坐标系的表示 a = - x_axis.x * org.x - x_axis.y * org.y - x_axis.z * org.z b = - y_axis.x * org.x - y_axis.y * org.y - y_axis.z * org.z c = - z_axis.x * org.x - z_axis
4、.y * org.y - z_axis.z * org.z 6、 写出几种线裁剪算法；写出几种多边形裁剪算法。 （ 1）、矢量裁剪法（ 2）、编码裁剪法（ 3）、中点分割裁剪法多边形的裁剪算法： （ 1）、逐边裁剪法（ 2）、双边裁剪法 7、 写出 Bezier 曲线和面片的几种表达形式。 2 空间给定的 n+1 个点 ，称下列参数曲线为 n 次的 Bezier 曲线。 其中 是 Bernstein 基函数，即 i = 0,1,n 空间给定的 (n+1)*(m+1)个点 为曲面片的控制顶点（ i = 0,1, ,n; j = 0,1, ,m） ,则下列张量积形式的参数曲面为 次的 Bezier
5、 曲面： Bezier 曲面齐次坐标形式为： 其中 为 Bernstein 多项式。 8、 写出 B 样条的矩阵形式和调和函数。为什么使用非均匀有理 B样条？ n+1个控 制点 ,K 阶（ K-1 次） B样条曲线的表达式是： 其中 是调和函数，按照递归公式可定义为： 其中 是节点值， 是 K阶 B样条函数的节点矢量。 非均匀 B 样条函数的节点参数沿参数轴的分布是不等距的，近年来，它得到了广泛的发展和应用，主要原3 因是： （ 1） 对标准的解析形状（如圆锥曲线，二次曲线，回转面等）和自由曲线，曲面提供了统一的数学表示，无论是解析形状还是自由格式的形状均有统一的表示参数，便于工程数据库的存取
6、和应用。（ 2） 可通过控制点和权因子来灵活的改变形状。 3） 对插入节点，修改 ，分割，几何插值等的处理工具比较有利。（ 4） 具有透视投影变换和仿射变换的不变性。（ 5） 非有理 B 样条，有理及非有理 Bezier 曲线，曲面是 NURBS 的特例表示。 9、 简述边界表示法（ BREP）实体构造表示法（ CSG）。 边界表示法是用实体的表面来表示实体的形状，它的基本元素是面、边、顶点。它以欧拉公式作为理论基础，要求实体的基本拓扑结构符合欧拉公式。目前采用的比较多的数据结构是翼边数据结构和半边数据结构（又称对称数据结构）。实体构造表示法的基本思想是将简单的实体（又称体素）通过集合运算组成
7、所需要的物体 。其中，集合运算的实现过程由一棵二叉树来描述，二叉树的叶子节点表示体素或者几何变换的参数，非终端节点表示施加于其子结点的正则集合算子或几何变换的定义。 10、 写出透视变换矩阵和各种投影（三视图、正轴测和斜投影）变换矩阵。 透视变换矩阵形式为： 主视图： 俯视图： 侧视图： 正轴测： 斜投影： 11、 观察空间有哪些参数？其作用是什么？写出从物体空间坐标系到观察空间坐标系转换矩阵。 参数 名称 作用 VRP 观察参考点 确定观察坐标系原点 VPN 观察平面法向 确定观察平面法向 VUP 观察正向 确定观察平面上 v轴的方向 4 F 前截面距离 确定前截面位置 B 后截面距离 确定
8、后截面位置 Pt 投影类型 定义投影是平行投影还是透视投影 PRP 投影参考点 确定投影中心或投影方向 Umin,Umax,Vmin,Vmax 观察窗口 在观察平面上定义观察窗口 从物体空间坐标系到观察空间坐标系的转换 矩阵： 12、 分别写出对于透视投影和平行投影的从裁剪空间到规范化投影空间的转换矩阵。 平行投影： Tvcper=T3T4T5parT6par 5 透视投影： Tvcper=T3T4T5per 13、 写出从规范化投影空间到图像空间的转换矩阵。 14、 写出光线与几种常见物体面的求交算法。 假设光线射线定义为 X=Dt+E (t=0) 其中， E=(e1,e2,e3)为射线起点
9、， D=(d1,d2,d3)为射线方向， |D| = 1， X=(x,y,z)为射线上任意点。 1）与多边形求交算法 假 设多边形所在的平面方程为 ax+by+cz+d = 0 把射线参数方程代入平面方程得到： t0 = - (N * K + d) / (N * D) (N*D0，交点为 X0 = Dt0 + E。这时，还要判断交点是否在多边形上。判断时，只要把交点和多边形投影到某个坐标平面上判断即可。 2）与球面求交算法 设球心在 P0(x0,y0,z0)，半径为 r 的球面方程为 (P P0) * (P P0) = r * r 代入射线方程，有 at*t + bt + c = 0 其中 a
10、 = D*D， b = 2D *(E-P0)， c = (E-P0) * (E-P0) r * r 当 b*b-4ac= 0 AXIS * (P P0) = 0 时，可以由求根公 式求出解。 求出 t以后，还要看是否满足后面两个不等式，才能决定是否在圆柱面上。 15简述消隐算法的分类。 根据消隐空间的不同，消隐算法可分为两类： （ 1）物体空间的消隐算法：物体空间是物体所在的空间，即规范化投影空间。这类算法是将物体表面上的K 个多边形中的每一个面与其余的 K-1 个面进行比较，精确求出物体上每条边或每个面的遮挡关系。计算量正比于 K2。（ 2）图象空间的消隐算法：图象空间就是屏幕坐标空间，这类
11、算法对屏幕的每一象素进行判断，以决定物体上哪个多边形在该象素点上是可见的。若屏幕上有 m n个象素点，物体表 面上有 K个多边6 形，则该类消隐算法计算量正比于 mnk。 16、 简述深度缓存算法及其特点。 深度缓存算法是一种典型的、也是最简单的图象空间的消隐算法。在屏幕空间坐标系中， 轴为观察方向，通过比较平行于 轴的射线与物体表面交点的 值（又称为深度值），用深度缓存数组记录下最小的 值，并将对应点的颜色存入显示器的帧缓存。 深度缓存算法最大的优点是简单。它在 、 、 方向上都没有进行任何排序，也没有利用任何相关性。算法复杂性正比于 。在屏幕大小，即 一定的情况下，算法的计算 量只与多边形
12、个数 成正比。 另一个优点是算法便于硬件实现，并可以并行化。 17、 简述点与多边形之间的包含性检测算法。 先将该点变换到多边形所在平面，在二维空间讨论该问题，过该点沿任意方向做一条射线，与多边形边界求交点，若交点个数为偶数， 0， 2， 4，则该点在多边形外部，否则在内部。如果射线与多边形某条边、某个顶点重合，则可以改变射线方向重新测试。 18、 描述扫描线算法。 扫描线算法如下： （ 1）对于每个多边形，根据多边形顶点的最小的 y值，将多边形置入多边形 Y 桶。 （ 2）有效多边形表 APT 初始化为空， 有效边表初始化为空。 （ 3）对每一条扫描线 j， j从最小值 1 开始，做以下工作
13、： 颜色缓存 CB置为背景色。 深度缓存 ZB置为机器无穷大。 检查多边形 Y桶中对应扫描线 j的链中是否有新的多边形。如有，则将新多边形加到有效多边形表 APT 中。 对于新添到有效多边形表中的多边形，生成对应的边 Y 桶。 对于有效多边形表 APT 中的每一个多边形，若其边 Y桶中对应扫描线 j 有新的边，则将新边配对加入到有效边表 AET 中。 对于 有效边表 AET中的第一个边对，计算起止 x坐标间点的 z值，与 ZB中对应值比较，若小，在更新 ZB 的值，并将该点颜色值存入 CB。 将 CB 的内容写入显示器帧缓存的第 j行。 检查有效多边形表 APT 中的个多边形，若多边形顶点的最
14、大 Y坐标已等于 j，则从 APT 中删去多边形，释放对应的边 Y桶的空间，并从有效边表 AET 中删去属于该多边形的所有边对。 检查有效边表 AET的每一边对，调整相应的起止 x 坐标，和 z值。 19、 简述几种阴影生成算法。 阴影生成算法主要分为如下几种： 影 域多边形方法：由于物体遮挡光源后在它们后面形成一个影域，所以确定某点是否落在阴影中只要判别该点是否位于影域即可。 曲面细节多边形方法：基于多边形区域分类的隐藏面消去算法，通过从光源和视点两次消隐生成阴影。 z 缓冲器方法：该方法分为两部。首先，利用 z 缓冲器消隐算法按光源方向对景物进行消隐。在 z 缓冲器（阴影缓冲器）中记录离光
15、源最近景物点的深度值。第二部，采用 z缓冲器消隐算法按视线方向计算画面。将每一象素对应点变换到光源坐标系，并用变换后点的深度值与阴影缓冲器中的深度值比较，若阴影缓冲器中的深度值较小，则说明该点 从光源方向不可见，位于阴影中。 光线跟踪方法：在光线跟踪算法中，要确定某点是否在某个光源的阴影内，只要从该点出发向光源发出一根测试光线即可。若测试光线在到达给定光源前，先与其它景物相交，在该点位于给定光源的阴影中，否7 则受到该光源的直接照射。 20、 试描述您所熟悉的计算机图形系统的硬软件环境。 计算机图形系统是计算机硬件、图形输入输出设备、计算机系统软件和图形软件的集合。 例如：计算机硬件采用 PC
16、、操作系统采用 windows2000，图形输入设备有键盘、鼠标、光笔、触摸屏等，图形输出设备有 CRT、 LCD 等，安 装 3D MAX 图形软件。 21、 图形硬件设备主要包括哪些？请按类别举出典型的物理设备 ? 图形输入设备：鼠标、光笔、触摸屏和坐标数字化仪，以及图形扫描仪等。 图形显示设备： CRT、液晶显示器（ LCD）等。 图形绘制设备：打印机、绘图仪等。 图形处理器： GPU（图形处理单元）、图形加速卡等等。 22、 为什么要制定图形软件标准？可分为哪两类？ 为了提高计算机图形软件、计算机图形的应用软件以及相关软件的编程人员在不同计算机和图形设备之间的可移植性。图形软件标准通常
17、是指图形系统及其相关应用系统中各界面之间 进行数据传送和通信的接口标准，另外还有供图形应用程序调用的子程序功能及其格式标准。 23、 请列举出当前已成为国际标准的几种图形软件标准，并简述其主要功能。 （ 1） CGI(Computer Graphics Interface)，它所提供的主要功能集包括控制功能集、独立于设备的图形对象输出功能集、图段功能集、输入和应答功能集以及产生、修改、检索和显示以像素数据形式存储的光栅功能集。（ 2） GKS(Graphcis Kernel System)，提供了应用程序和图形输入输出设备之间的接口，包括一系列交互和非交互式 图形设备的全部图形处理功能。主要功
18、能如下：控制功能、输入输出功能、变换功能、图段功能、询问功能等。 24、 试列举计算机图形学的三个应用实例。 （ 1） CAD/CAM（ 2） VISC（ 3） VR. 25、 在图形设备上如何输出一个点？为输出一条任意斜率的直线，一般受到哪些因素影响？ 若图形设备是光栅图形显示器，光栅图形显示器可以看作是一个像素的矩阵，光栅图形显示器上的点是像素点的集合。 在光栅图形显示器上输出一条任意斜率的直线，主要受到以下因素的影响： （ 1）光栅图形显示器的分辨率； 2）线宽、线型；（ 3）直 线的扫描转换的算法。 28、在齐次坐标系中，写出下列变换矩阵： （ a） 整个图象放大 2倍；（ b） y
19、向放大 4倍和 x 向放大 3 倍；（ c） 图象上移 10 个单位和右移 5个单位（ d） 保持 x=5 和 y=10 图形点固定，图象 y 向放大 2 倍和 x向放大 3倍； e） 图象绕坐标原点顺时针方向转 /2;f） 图象绕点 x=2和 y=5 反时针方向转 /4。 （ a） 整个图象放大 2倍； （ b） y向放大 4倍和 x 向放大 3倍； （ c） 图象上移 10 个单位和右移 5 个单位； 8 （ d） 保持 x=5 和 y=10 图形点固定，图象 y 向放大 2 倍和 x向放大 3 倍； (1) 将坐标系平移到点（ 5， 10） T1 = (2) 将图象 y向放大 2倍和 x
20、 向放大 3倍 S = (3) 平移坐标系至（ -5， -10）点 T2 = T = T2 ST1 = = （ e） 图象绕坐标原点顺时针方向转 /2; R = （ f） 图象绕点 x=2 和 y=5 反时针方向转 /4。 (1) 将坐标系平移到点（ 2， 5）； T1 = (2) 将图象绕原点反时针方向转 /4； R = (3) 将坐标系平移到点（ -2， -5）； 9 T2 = T = T2 RT1 = = 29、 由比例、平移和旋转变换构成的复合变换，仅在某些情况下交换次序不影响总的变换效果，它们是哪几种两个变换的组合。 （ 1） 两个连续的平移变换；（ 2） 两个连续的比例变换；（ 3
21、） 两个连续的旋转变换；（ 4） 比例系数相等的比例变换和旋转变换。 38、 光栅扫描显示器由哪些部分组成？它们功能分别是什么？简述之。 光栅扫描式显示器主要由五个部分组成， （ 1）显示存储器：它是整个显示器的核心，存放着在屏幕上显示图形的映像（ Image）。 （ 2）图像生成器：它的作用是把计算机送来的画线、画短形、画填充区域或写 字符等基本画图命令扫描转换成为相应的点阵（称位图），存放在显示存储器中，即存放着需要在荧光屏上显示出来的图形的映像。 （ 3）彩色表：平衡显示存储器不能过大而又尽量满足实际需要。 （ 4） CRT 控制器： CRT 控制器的作用是一方面使电子束不断地自上而下、
22、自左面右进行屏幕扫描，形成光栅（ Raster），产生水平和垂直同步信号送往 CRT；另一方面又不断地读取存放在显示存储器的位图数据，作为 RGB信号或辉亮信号送往 CRT。 （ 5） CRT 监视器： CRT监视器是由阴极射线管和有关附加电路（如扫描偏转电路、视频放大电路等组 成。类似电视机屏幕，供显示图形用。 39、 简述编码裁剪法（即 Cohen-Sutherland 线段裁剪法）的算法过程。 由 Dan Cohen 和 Ivan Sutherland 提出的区域编码判断方法，采用四位数码来标识线段的端点与窗口区域的关系，然后： （ 1）检查线段 P1P2 是否为完全可见，或完全不可见，
23、对于这两种情况或完全取之，或完全弃之，否则 “ 2”。 （ 2）找到 P1P2 在窗口外的一个端点 P1（或 P2）； （ 3）用窗口的边与 P1P2 的交点取代端点 P1（或 P2）； （ 4） P1P2 线段是否完全可见，若是， 则结束，否则转到“ 2“继续执行。 40、 试述单个凸多面体消隐的基本方法。 定义垂直于物体平面且背离物体的直线向量为平面法线向量，定义从视点到物体表面上任一点直线方向为视线向量方向，那么利用这两个矢量之间夹角可以进行背面测试，只有当两个矢量之间夹角小于 90O 时面为可见面。 42、简述在 C语言图形程序设计过程中制作动画都可以采取哪些方法？ （ 1）全局画擦画： cleardevice( ) （ 2）局部画擦画： getimage( ) putimage( )
