计算机图形学复习提纲.doc

计算机图形学复习提纲 第一章 绪论。 （课件为主） 1.1图形无处不在（1）定义：计算机图形学是研究怎样用数字计算机生成、处理和显示图形的一门学科。（2）计算机软硬件的发展促进了计算机图形学的发展。随机扫描刷新式显示器 采用阴极射线管，利用两对偏转电极或电磁偏转线圈控制电子束在荧光屏上的落点位置，在屏幕上绘制出闪亮的线条。光栅扫描式显示器 采用成熟的彩色电视机技术，用三个电子束同步逐行扫描荧光屏上整齐排列的红、绿、蓝三基色点簇。一条电子束对准一种基色，一个点簇称为一个象素。一幅画面可以由640480，800600，1024768，12801024不等的象素构成。将需要显示的图形点阵分解为红、绿、蓝三基色，并将各象素所对应的色彩编码值存储在帧缓存器内，用以控制扫描电子束每一瞬间的激励强度。 色彩编码：计算机中将红、绿、蓝三种基色的强度分为256级，因此这三种基色的组合共有256 256 256=种，也就是说，计算机可以显示1600多万种颜色。高档微机的出现图形软件的迅速发展（3）计算机图形学与图象处理计算机图形学的内容：用计算机生成景物的数字模型，并将它显示在计算机屏幕上，或者绘制成纸张或胶片上的图形。图象处理的内容：用摄象机或扫描仪等观测手段将客观世界中原来存在的景物设置成数字化图象，对图象进行处理和分析，理解图象的内涵，进而从图象中提取所关注的景物的二维或三维几何模型。（4）计算机图形学的应用数字地球：1998年1月31日美国副总统戈尔在洛杉机加利福尼亚科学中心召开的地理信息系统年会上提出了这一设想。计算机辅助设计：在工业（汽车、飞机、轮船、机械、建筑等）设计中得到广泛应用。计算机艺术科学计算可视化：给数据以形象；给信息以智能仿真模拟、电影、计算机游戏、多媒体远程教育、电子邮件 1.2景物的几何建模：贝齐埃曲线 1.3场景绘制取景变换 将几何对象的三维坐标转换到屏幕上的象素位置，需要进行一系列的坐标变换，这些变化统称为取景变换。删除隐藏面 背向视点的面被正面遮挡，需要及早删除。目的是为了减少图形绘制工作量，提高场景动态显示的实时性。裁减 超出屏幕显示范围的场景要从几何模型上裁减掉。目的也是了减少图形绘制的工作量，提高场景动态显示的实时性。光亮度计算 牵涉到定义景物的表面材质和颜色，确定光源的性质和位置，模拟光线传播的物理机制，处理好透明、半透明、镜面反射和物体相互遮挡、阴影生成等种种问题，为此设计各种复杂的算法。反走样算法 由于图形显示器采用光栅模式，连续的景物表面只能以离散的光栅图像显示。每一象素取一定的红绿蓝三基色分量来显示该象素处可见的景物表面采样点的颜色和亮度。由于屏幕具有一定的分辨率，用离散的、固定大小的象素来表示画面上的纹理细节，必然要产生失真，因此需要采用反走样算法来缓和视觉上的反差。QuickTime技术简介 QuickTime是苹果公司开发的新一代虚拟现实技术。它是一种基于静态图像处理的，在微机平台上能够实现的初级虚拟现实技术。它的出现使得以往专业实验室中成本昂贵的虚拟现实技术的应用普及有了广阔的前景。假定我们在一室空间进行观察，室内空间一般有六个面，如果我们获取了这六个面的许多不同距离，不同方位的实景照片并将它们按照相互的关系有机连接起来，就可以在视觉上形成这个房间整个空间的整体认识，这就是全景概念。 1.4人机交互界面 （1）目前流行的图形界面（2）虚拟现实（Virtual Reality简称VR）虚拟现实是指用立体眼镜、传感手套等一系列传感辅助设施来实现的一种三维现实，人们通过这些设施以自然的方式（如头的转动、手的运动等）向计算机送入各种动作信息，并且通过视觉、听觉以及触觉设施使人们得到三维的视觉、听觉等感觉世界。随着人们不同的动作，这些感觉也随之改变。1.5 计算机动画我国第一部利用计算机辅助摄制的动画片是咪咪钓鱼，1991年由北方工业大学和北京电视台合作制作，以二维动画为主。用386微机和C语言编程，利用数字化仪和摄象机产生关键帧，再由计算机在相邻两幅关键帧之间内插生成中间帧，并自动跟踪上色。多层画面叠加在一起，形成完整的画面。10分钟的片子，5人小组花了10个月时间。计算机动画的应用领域非常广，最典型的有：1、计算机模拟飞行2、动画片3、电视广告第二章 计算机图形系统及其设备 （课件为主）CRT显示器的原理、类型 P13P14光栅扫描图形显示原理（概念要清楚）液晶显示器显示适配器的结构、标准（有哪几个） P18 计算机图形系统概述：微型计算机图形系统、图形工作站、虚拟现实系统图形输入设备、输出设备（理解原理） 第三章 生成直线和圆弧的算法 DDA方法原理 （了解原理）Bresenham算法（直线和圆弧的原理要清楚）生成直线算法的进一步改进绘圆弧的正负法和圆的多边形迫近法（了解即可）第四章 变换 （公式要熟悉）记住变换公式（平移、缩放、旋转、剪切） 平行投影和透视投影的原理和计算公式（z=0平面） 理解裁减Sutherlan-Cohen算法 （原理要清楚）中点分割算法和梁友栋Barsky算法（原理要清楚）其他图形的裁减需要理解一下第六章 交互技术 （课件为主）交互的硬件设备（概念和原理） 基本交互任务进一步交互技术（概念和原理） 输入过程基本处理模式（有10个）人机交互一般风格原则（所见即所得，直接操作，菜单和图形符号驱动）6.1 交互的硬件设备6.1.1 定位设备：鼠标、屏幕上的光标、操纵杆、数字化仪、键盘上的方向键、光笔、触摸屏等。6.1.2 键盘设备：用于输入字母和数字。6.1.3 取数设备6.1.4 选择设备：鼠标、功能键等。6.1.5 其它输入设备：语音识别器、数据手套、数据头盔等6.2 基本的交互任务：定位、选择、数量输入、文本输入、进一步的交互技术、几何约束6.3进一步的交互技术 6.3.1几何约束 定位约束：在屏幕或窗口上定义一些不可见的网格，有时也可以用点的形式表示网格结点的位置。对用任何方式输入一个点都用离它最近的一个网格结点来代替。假如定义不可见网格线为x=10i,y=10j, i,j=0,1,2,n设输入点的坐标为(x,y)，则离它最近的网格点坐标为(10*(round(x)+5)div 10),10*(round(y)+5)div 10) 方向约束：例如要绘制的线只能是垂直或水平两个方向，当给定的起点和终点连线与水平线的夹角小于45时，便绘出一条直线，否则就绘垂直线。这种约束对只要绘垂直线或水平线的情况带来很大方便。6.3.2 拖动 当我们要把一个图形放到一个新位置时，如果我们不是简单地用光标指定新位置的一个点，而是随着鼠标引导光标移动的同时图形也跟着拖到新的位置。这将使用户感到更直观并可把图形的位置定得更准确、恰当。6.3.3 橡皮筋技术 在平面上确定一条直线一般是先定下起点再定下终点，最后把起点和终点连成直线。所谓橡皮筋技术就是在起点确定后，光标移出去确定终点时，在屏幕上始终显示一条连结起点和光标中心的直线，这条直线随着光标中心位置的变动而变动。6.3.4 图形变比 为了把屏幕上的图形的某部分放大或缩小，可用图形变比（zoom）。例如可以用矩形的橡皮筋在屏幕上划定一个区域，要求把区域内的图形部分放大，要实现这个功能只要在程序中把这个矩形定义为窗口，再显示时就可把窗口包含的图形部分显示在视区内，窗口越小，图形放得越大。6.3.5 引力场效果 在用光标选图时，要把光标中心移到图段上去，如果被选的图形只是一个点或一根线，那么把光标中心对准一点或一条直线段需要花较多时间。为了比较容易地做到这一点，可用引力场的方法。在每一条线段的周围假想有一个区域，这个区域象一根香肠或哑铃，如图6.11所示，光标中心落在这个区域时，就自动地被直线上最近的一个点所代替。这就好象一个质点进入了直线周围的引力场后，就会被吸引到这条直线上去一样。香肠或哑铃的粗细要适中，太细了不易进入引力区，太粗了线和线的引力区相交，光标在进入引力区相交部分可能会被吸引到不是要选的线段上去，这样就出现错误了。 6.3.6 标尺和导向线 为了能用比较准确的尺寸来绘图，可以在屏幕上使用标尺。用户可用适当的命令在屏幕上显示标尺。 使用一条线表示当前光标中心所在的位置。6.3.7 坐标显示 为了能把点定位得准确，可以在屏幕上显示光标中心所在位置的坐标。6.3.8 在三视图上作三维输入 在输入一个立体图时，时常是一个个点、一条条线或一个个面单独输入的，而对一个点、一条线或者一个面来说，只要在三视图上给出足够的信息，总是可以惟一地确定三维空间中的对应图形。对输入一个点来说，实际上只要在两个视图上把点的对应位置指定后便惟一确定了三维空间中的一个点，因为给定了一个点在两个视图上两个对应位置后，便可确定该点的x,y和z坐标值，因而也确定了三维空间中的一个点。这样把直线段上两端点在三视图上输入后便可决定三维空间的一条直线，把一个面上的顶点在三视图上输入后，也惟一确定了三维空间中的一个面。如果把一个多面体的各面均用上述方法输入，也就在三维空间中输入了一个多面体。用三视图来输入立体图是目前主要的一种输入手段。6.3.9 推移 很多立体图形可以通过二维图形经过一定推移（如延伸、旋转等）而得到。这样的图形称为“二维半”图形。 6.3.10 结构平面 输入立体图形常是由简到繁一步一步地构造，例如要生成图6.20的图形，先要生成图6.18中的二维半图形，再在平面ABCD上用推移的方法拉伸出一个柱体来。为了指定要在ABCD平面进一步绘图，可用交互的办法指定A,B,C三点。然后将ABCD平面旋转到它的法线方向恰好指向用户的位置，如图6.19所示，然后在ABCD平面上绘一个圆，并指定要在上面生成圆柱体的高度，在通过拉伸操作，使ABCD平面上加上了一个柱体。这个ABCD平面便称为结构平面。6.4 输入过程基本处理模式 为了实现上述的交互功能，必须把从输入设备输入的信息和应用程序有机的结合好。由于输入设备是多种多样的，而且对一个应用程序而言可以有多个输入设备。同一设备又有可能为多个任务服务，这就要求输入过程的处理要有一些合理的办法。现在常用的三种基本模式为请求方式、取样方式和事件方式。 6.4.1 请求方式 当程序运行到某一点时，需要用户输入，这时，程序会暂停在这一点上，一直到用户输入了信息后，才继续执行。 6.4.2 取样方式 输入设备连续输入，应用程序采用取样的方式接受输入的信息。由于是取样方式，所以可能会失掉某些输入信息。 6.4.3 事件方式 当设备设置成事件方式后，输入设备和程序同时工作。当用户在输入设备上发生一个表示输入的动作（如按一下按钮）便产生一个事件，输入信息及该设备编号等便会存放到一个事件的队列中去。这队列是以事件发生的时间排序的。不同的应用程序可到队列中来检索和取走属于该应用程序有关的事件。由于每次用户产生输入信息的动作后，输入信息便保存在事件队列中等待用户一一取走，所以要输入的信息是不会遗失的。 6.5 设计人机交互的一般风格及原则 人机交互设计的风格“所见即所得”：屏幕上所见的设计结果与输出结果一致直接操作：对对象、特性及关系的操作以直观形象的表示菜单和图形符号驱动：不需要专门学习和记忆，便可借助菜单及图形符号来运行系统人机交互设计的原则：简单易学 提供反馈 对错误操作容易纠正 设计的一致性 6.6 图形标准和图形程序库OpenGLOpenGL是一个函数库，它含有100多个库函数。它有以下基本功能：（1）模型的描述（2）变换（3）颜色模式（4）光照模型（5）纹理映射（6）实时动画（7）交互功能第七章 光栅图形的扫描转换与区域填充 （所有的原理和概念）多边形的扫描转换（逐点判断算法、扫描线算法、边缘填充算法、边界标志算法）区域填充（表示和类型、递归算法、扫描线算法）多边形的扫描转换与区域填充的区别比较（基本思想、对边界要求、出发点不同）反走样基本方法 第八章 隐藏面和隐藏线的消除 基本概念（前向面、后向面、多边形的边界盒）多面体的隐藏线消除（概念、原理、包括不可见阶的算法）曲面的隐藏线消除（需要理解一下）面消除算法：区域子分算法、z缓冲器算法和扫描线算法、区间扫描线算法（原理要熟悉一下）面消除算法各自的优缺点 8.1 多面体的隐藏线消除前向面：内法线方向背向视点的面。后向面：除前向面以外的面。后向面总是看不见的，并且不会仅由于后向面的遮挡，而使别的棱成为不可见，因此可以把后向面全部去掉，这并不影响消隐结果。步骤一、判断后向面设多边形F的顶点为v1,v2,vL，顶点vi的坐标为(xi,yi,zi)。顶点的次序要求这样排列，使观察者在多面体外沿着v1-v2-v3vL走时，多边形的内部始终在他的右侧。并计算多边形在oxy平面上投影的有向面积。有向面积可如下计算：sp = (1/2) (xk - x1)(yk+1 - y1) - (xk+1 - x1)(yk - y1)如果sp0，则F所在的面为后向面。步骤二、对于某条边L，求出其与所有可能遮挡其的多边形的边界的交点，并记录该交点是进点还是出点。（1）如边L两个端点都在多边形所在平面靠近观察者的一侧，则不计算该多边形与L的交点。（2）将L和多边形投影到OXY平面，计算它们的投影之间的交点，若交点在L上对应的点在多边形的后面，则记录该交点及进出性质。否则不记录。求交时可以采用边界盒的方法进行初步排除，可以大大减少求交量。（3）如没有交点，则判断L的两个端点之一是否在多边形内部。如是，则该边L被完全遮挡，不用再计算L与其他多边形的交点了。步骤三、判断L的可见部分如果边L和所有多边形的交点及进出性质都求出后，便可以判断其可见部分了。（1）将所有交点按照从起点到终点进行排序，假设每个交点对应的参数值为l,则该序列为l1,l2,（2）确定起点处的不可见阶ivord值，先将ivord置为零，对每一个和L相交的多边形，找出l值最小的那个交点，若这个交点为出点，则ivord值加1，若为进点，则不改变。最后若ivord值为零，则从起点至l1段为可见，否则为不可见。（3）确定L上其它交点处的不可见阶ivord值。若l1处为进点，则ivord值加1，否则减1, 若ivord 0, 则l1至l2段为不可见，否则可见。依此类推。从而确定L上所有可见部分。现在说明上述各步骤的具体做法。设多边形的顶点为v1,v2,，vL，其坐标为（xi,yi,zi），i=1,2, ,L。任取三个不在一条直线上的顶点，设为v3,v4,v5，则这个多边形所在的平面方程为设点vj的坐标为(xj, yj, zj)，若z(xj, yj) zj，则vj在多边形所在平面的前面，否则认为vj在多边形所在平面的后面。为了求边vivj和多边形的边界在oxy平面上投影的交点，可把vivj的投影线段用参数方程x = xi(1 - l) + xjly = yi(1 - l) + yjl 0l1 (8.5)表示。多边形上任一边vsvs+1的投影用x = xs(1 - t) + xs+1ty = ys(1 - t) + ys+1t 0t1 (8.6)表示。求交点时解上述方程组可得l = (xs - xi)(ys - yi+1) - (ys - yi)(xs - xs+1)/R (8.7)t = (ys - yi)(xj - xi) - (xs - xi)(yj - yi)/R (8.8)其中R = (ys - ys+1)(xj - xi) - (xs - xs+1)(yj - yi) (8.9)只有当0l1和0t1时线段vsvs+1和线段vivj在oxy平面上的投影才有交点。如果R yu(j) 或yjnyu(j) then yu(j)= yjiif yjiyl(j) then yl(j)= yji 若式(8.14)不成立，则(xj,yjn,zn)为不可见，也不要修改yu(j）或yl(j)的值了。 对z=zn平面上的曲线完成上述工作后，再对平面z=zn-1上的曲线重复上述工作，这样按z值递减方向一条一条曲线处理过去，就得到了一组消除隐藏线的曲线族了。8.3 区域子分算法如果要对物体的不同面上涂上不同颜色和灰度，这时，消隐问题不再是讨论线段的可见与否，而是讨论一个面或面的一部分可见与否。为了减少计算量，可先去掉所有的后向面。区域子分算法是一种所谓分而治之的算法。整个屏幕称为窗口，分而治之算法是一个递推的四等分过程，每一次把矩形的窗口等分成四个相等的小矩形，分成的矩形也称为窗口。每一次子分，均要把要显示的多边形和窗口的关系作一判断。这种关系可以有以下四种，即1）多边形包围了窗口2）多边形和窗口相交3）窗口包围了多边形4）窗口和多边形分离在窗口和每个多边形的关系确定后，有些窗口内的图形便可显示了。它们属于下列三种情况之一。1）所有多边形都和窗口分离，这时只要把窗口内所有象素填上背景颜色。2)只有一个多边形与窗口相交，或这个多边形包含在窗口内。这时先对窗口内每一象素填上背景颜色，再对窗口内多边形部分用扫描线算法填色。3）只有一个多边形和窗口相交，这个多边形把窗口整个包围在内，或虽有几个多边形和窗口相交，但离观察者最近的一个多边形包围了整个窗口，这时把整个窗口填上离观察者最近的那个多边形的颜色。 对上述三种情况的窗口来说，图已可画出，因而不必再细分了。对上述三种情况不成立的窗口再一分为四，分得的窗口再重复上述的处理。对不能处理的窗口再一分为四。窗口的边长越分越短，分了若干次后，窗口的边长就和一个象素的宽度一样，这时这个窗口对应的象素的颜色可取成最靠近观察者的多边形的颜色，或和这个窗口相交的多边形的平均值。8.4 z缓冲器算法和扫描线算法 z缓冲器算法是最简单的消除隐藏面算法之一，z缓冲器是一组存储单元，其单元个数和屏幕上象素的个数相同，也和帧缓冲器的单元个数相同，而且它们之间是一一对应的。Z缓冲器中每单元的值是对应象素点所反应的对象上点的z坐标值。Z缓冲器中每个单元的初值取成z的极小值，帧缓冲器中每个单元的初值可放对应背景颜色的值。图形消隐和生成的过程就是给帧缓冲器和z缓冲器中相应单元填值的过程，在把显示对象的每个面上每一点的属性（颜色或灰度）值填入帧缓冲器相应单元前，要把这点的z坐标值和z缓冲器中相应单元的值作比较。只有前者大于后者时才改变帧缓冲器的那一个单元的值，同时z缓冲器中相应单元的值也要改成这点的z坐标值。如果这点的z坐标值小于z缓冲器中相应单元的值，则说明对应象素已显示了对象上一个点的属性，该点要比考虑的点更接近观察者。这样无论帧缓冲器或z缓冲器相应单元的值均不应改变。对显示对象的每一个面上的每一点都作了上述处理后，便可得到消隐了隐藏面的图。 上述算法的优点是简单、可靠，不需要对显示对象的面预先进行排序。 缺点是要很大的z缓冲器，显示对象的表面和象素对应的每一个点处都要计算它的z值，因而工作量较大。为了克服第一个缺点，可把整个平面分成若干区域，一区一区来显示，这样z缓冲器的单元数只要等于屏幕上一个区域的象素个数。如果把这个区域取成屏幕上一行，就得到了扫描线z缓冲器算法。这时z缓冲器的单元数可以取成和一行上的象素数目相同。从最上面的一条扫描线开始工作，向下对每一条扫描线作处理。对每一条扫描线来说，把相应的帧缓冲器单元置成底色，在z缓冲器中存放z的极小值。对每个多边形检查它在oxy平面上的投影和当前的扫描线是否相交，若不相交，则不考虑该多边形。如果相交，则扫描线和多边形边界的交点一定是成对出现。对每对交点中间的象素计算多边形所在平面对应点的深度（即z值），并和缓冲器中相应单元存放的深度值作比较。若前者大于后者，则z缓冲器的相应单元内容要被求得的平面深度代替，帧缓冲器相应单元的内容也要换成该平面的属性。对所有多边形都作上述处理后，帧缓冲器中这一行的值便反应了消隐后的图形。对帧缓冲器每一行的单元都填上相应内容后也就得到了整个消隐后的图。8.5 区间扫描线算法 上节讲的扫描线z缓冲器算法将消隐问题分散到每一条扫描线上去解决，这样，问题变得较简单了。但在每个象素处计算多边形z值的工作量仍是很大的。实际上每条扫描线被各多边形边界在oxy平面上的投影分割成为数不多的区间，每一个区间上只显示一个面，因此，只要在区间上任一点处，找出在该处的z值最大的一个面，这个区间上的每个象素就用这个面的颜色来显示。这种做法就是所谓区间扫描线算法。 Z缓冲器算法、区域子分算法和扫描线算法各有优缺点，但从效率来看，还是区间扫描线法为好。8.6 优先级表算法 上面讨论的很多算法是基于多边形离视点的远近来决定它们之间的隐藏关系，优先级表算法就是企图按多边形离观察者的远近来建立一张表，距离观察者远的优先级低，近的优先级高。如果这张表能正确地建立好，那么只要从优先级低的多边形开始，依次把多边形的颜色填入帧缓冲存储器中以形成该多边形的图形，直到优先级最高的多边形的图形送入帧缓冲器后整幅图就显示好了。 上述算法的困难在于怎样对多边形做一个正确的排序。下面给出了一个动态的方法。 先可根据每个多边形顶点z坐标的极小值zmin的大小把多边形做一初步排序。设zmin最小的多边形为P，它暂时成为优先级最低的一个多边形，把多边形序列中其它多边形记为Q。现在先来确定P和其它多边形Q的关系。如果P的顶点z坐标的极大值Pzmax比某一多边形Q的顶点z坐标的极小值Qzmin还要小，即P zmaxP zmax，则P确定是优先级最低的。如果对某一多边形Q有Q zminP zmax，则必须作进一步的检查，才能确定P和Q的确切关系。这种检查分以下五项。1）P和Q在oxy平面上投影的边界盒在x方向上不相交2）P和Q在oxy平面上投影的边界盒在y方向上不相交3）P的各顶点均在Q的远离视点的一侧4）Q的各顶点均在P的靠近视点的一侧5）P和Q在oxy平面上的投影不相交 上述五项只要有一项成立，P就不遮挡Q。由于从第一项至第五项每项检查所需的工作量是递增的，因此检查时要按第一至第五项的次序进行。 如果上述五项均不成立，则不能确定P不遮挡Q，这时要在多边形序列中把P和Q交换一下次序，并对交换后的序列中优先级最低的多边形P检查，看P是否遮挡别的多边形。第九章 曲线曲面的表示 Bezier曲线(概念、定义、特征、性质、原理)Bezier曲线的曲线拼接、离散生成（原理要清楚） Bezier曲面（一般性了解）B样条曲线（概念、原理、定义、性质）与Bezier相互转化的关系B样条曲线的离散生成（原理要清楚）有理形式的曲线（概念、原理、基本特征）第十章 三维实体造型 三种表示方法的定义、各自的原理和优缺点 一三维实体造型的三种表示方法 1 CSG树表示法 ：在许多情况下，一个复杂物体可由一些比较简单、规则的物体经过布尔运算得到，因而这个复杂的物体可以描述为一棵树，这棵树的终端结点为基本体素（如立方体、圆柱、圆锥），而中间结点为正则集合运算结点。这棵树称为CSG树。CSG树结点数据结构的组织方式：Op-Code(操作码)：按约定方式取值。如0:基本体素；1：求并；2：求差；3：求交。Transform(坐标变换)：该结点所表示物体在进行新的集合运算前所作坐标变换信息。以指针方式存储。Primitive(基本体素)：基本体素指针。Left-SubTree(左子树)：左子树指针。Right-SubTree(右子树)：右子树指针。 CSG树结点数据结构只定义了所表示物体的构造方式，而没有存储顶点、棱边、表面等体的有关边界信息。所以CSG树表示又被称为物体的隐式模型或算法模型。 但用CSG树表示一个复杂形体十分简洁，它所表示的物体的有效性是由基本体素的有效性和集合运算的正则性而自动得到保证的。由于CSG树提供了足够的信息，以判定空间任一点在它所定义体的内部、体外或体的表面上，因此它可以惟一地定义一个物体，并支持对这个物体的一切几何性质的计算。包括它自身的几何性质，如体积、面积、重心等，也包括它与别的物体相互关联的性质。CSG树表示的分治算法分治算法：分而治之的算法。由于CSG树表示法只给出物体的构造方式，欲直接计算它所定义物体的几何性质常常比较困难。这时可采用“分治”算法。例如：欲确定物体A和B求并所生成的新物体C的重心，可先分别计算A和B的重心，然后再将所得结果按适当规则合成，求出C的重心，当A，B为基本体素时，其重心可直接求出，否则继续按“分治”方法递归计算下去。光线投射算法由于CSG树表示不显式表示物体的边界，因而无法直接显示CSG树表示的物体。为此，光线投射算法提供了圆满的解决方案，即不必求出CSG树表示物体的边界，而能够直接快速地对物体进行光栅图形显示。核心思想：从视点出发向显示屏幕的每一象素透射光线，求出与距离视点最近的可见表面的交点和交点处的表面法矢量，然后根据光照模型计算出表面可见点的色彩和亮度，生成物体的光栅图形。关键步骤：确定光线与物体之间距离视点最近的交点。具体算法如下：(1)将射线与CSG树中的所有体素求交，求出所有的交点。(2)对交点进行分类，确定位于CSG树表示的物体的边界上的交点。(3)对位于物体边界上的交点计算它们在射线上的参数值并进行排序，确定距离视点最近的交点。CSG树表示法的优缺点：三维物体最有效的表示方法之一。优点在于记录了物体的构造过程，表示的有效性自动保证，表示十分简洁。缺点在于，尽管CSG树表示可以支持它所表示物体的多种几何性质的计算及其它应用，但并非适用于一切场合。例如，它不适于对物体形状作局部修改。生成工程中常用的线画图形效率较低。这时常将物体的CSG树表示转化为边界表示，以便获取边界信息。2 边界表示法 ：通过描述物体的边界来表示物体。所谓边界就是物体内部点与外部点的分界面。显然，定义了物体的边界，该物体也就被惟一地定义了。 边界表示法描述物体的信息包括几何信息和拓扑信息两个方面。物体的拓扑信息指物体上所有的顶点、棱边、表面间是如何连接的。就多面体而言，其顶点、棱边和表面之间的连接关系共有9中表示方法，其中每一种关系都可以由其他任何一种关系经过适当的运算导出。边界表示法的典型数据结构翼边结构：在顶点、棱边、表面组成物体的三要素中，翼边结构以边为中心来组织数据。 棱边e的数据结构中，包含两个点指针，分别指向e的两个端点：顶点P1和P2。e被看作为一有向线段，P1为棱边e的起点，P2为其终点。如果e为一直线段，则它已为P1,P2两端点惟一定义，否则，棱边e数据结构中还应包含一项指针，指向e所在曲线信息的数据项。此外，e中还设置有两个环指针，分别指向棱边e所邻接的两个表面上的环Loop左和Loop右。这样就确定了棱边与相邻表面之间的拓扑关系。 为了能从棱边e出发找出它所在的任一闭合面环上的其它棱边，在e中又增设了四个边指针Ercc, Ercw, Elcc, Elcw。 由于翼边数据结构在边的构造与使用方面比较复杂，因此人们对其进行了改进，提出了半边数据结构。半边数据结构已成为边界表示的主流数据结构。半边数据结构与翼边结构的主要区别是将一条物理边拆成两条边表示，使其中每条边只与一个邻接面相关。由于半边数据结构中的边只表示相应物理边的一半信息，所以称为半边。 除了上述的两种以边为中心的边界表示法以外，还有以面为中心的边界表示。 在边界表示法中，可以定义一系列操作来建立三维形体，构造三维形体的边界表示，或对计算机中已经存储的实体进行修改。常用的这类运算有Sweep运算、欧拉运算、局部运算、集合运算。边界表示法一个很重要的特点就是描述物体的信息包括几何信息与拓扑信息两个方面。 优点：（1）便于具体查询物体中各元素； （2）容易支持对物体的各种局部操作； （3）对于具有相同拓扑结构的物体可以用同一的数据结构表示； （4）便于在数据结构上附加各种非几何信息； 缺点：物体之间的集合运算量涉及所有表面的求交、比较，运算量巨大，影响了算法的效率和可靠性。 3 八叉树表示法 物体的并、交、差运算是物体造型的十分有用的手段。但有缺点：（1）计算量大，效率低（2）由于求交情况复杂，影响算法可靠性。为此