华中科技大学大学CAD技术及应用 第二部分 图形学基础

计算机图形学基础算法1、三维形体的计算机表达2、图形变换3、基础算法4、线框及消隐显示5、真实感显示6、图形学的其它应用现实生活中的产品都是由不同类型的三维(3D)几何形状构成的集合体。描述产品对象的形状、大小、位置与结构等几何信息的模型称为几何模型(GeometricModel)。利用计算机图形技术可在计算机内部描述产品的几何模型和属性(如颜色、纹理等)，并生成直观真实感的图形。三维几何形体的表达计算机中表示形体几何模型通常用：线框模型表面模型实体模型线框模型和表面模型保存的三维形体信息都不完整。只有实体模型才能够完整地、无歧义地表示三维形体。点用三维坐标表示，是最基本的元素边是形体相邻面的交界，可为空间直线或曲线环是有序、有向的封闭边界，外环仅一个，逆时针方向，内环可有可无，也可多个，方向顺时针。面是一个单连通区域，可以是平面或曲面，由一个外环和若干个内环组成；面的方向由面的法矢决定，法矢向外为正向面。基本概念及定义实体是由若干个面组成的闭包，实体的边界是有限个面的集合。形体表面上任一点的足够小的邻域在拓扑上应是一个等价的封闭圆，即围绕该点的形体邻域在二维空间中可构成一个单连通域，我们把满足该定义的形体称为正则形体。否则为非正则形体，如存在悬面、悬边的长方体为非正则形体。线框模型线框模型用顶点和棱边表示三维形体，其棱边可以为直线、圆弧、二次曲线及样条曲线组成。线框模型在计算机内存储的数据结构：顶点表：记录各顶点坐标值；棱线表：记录每条棱线所连接的两顶点。classPOINTclassEDGE{{doublev[3];//坐标值intstart_point_no;//边的起点intpointtype;//点的属性intend_point_no;//边的终点CURVEcur；//边方程定义；…………..…………..}}以立方体为例，其线框模型结构如下表：优点1.结构简单，计算机内部易于表达，绘制快速；2.物体的三维数据可以产生任意视图，为生成工程图带来了方便缺点1.有二义性，缺少表面轮廓信息，当形状复杂、棱线过多时，会引起模糊理解。2.在数据结构中缺少边与面、面与体之间关系的信息。从原理上讲，此种模型不能消除隐藏线、计算物性、生成数控加工刀具轨迹、有限元网格剖分、物体干涉检验等。表面模型表面模型是用有连接顺序的棱边围成的有限区域来定义形体的表面,再由表面的集合来定义形体。表面可以是平面，也可以是柱面、球面等类型的二次曲面，也可是样条曲面构成的自由曲面。表面模型是在线框模型的基础上，增加有关面边信息以及表面特征、棱边的连接方向等内容。表面模型存储几何信息的方法是建立三表结构，即顶点表、边表和面表。1）顶点坐标值存放在顶点表中；2）含有指向顶点表指针的边表，用来为多边形的每条边标识顶点；3）面表有指向边表的指针，用来为每个表面标识其组成边。classPOINTclassEDGEclassFACE{{{同线框模型同线框模型intedge_num；//边数int*edge_no;//边链表intface_type;//面类型SURFACEsur；//面方程………….………….…………….}}}表面模型唯一没有解决的问题是形体究竟在表面的哪一侧，因而在物性计算、有限元分析等应用中，表面模型在形体的表示上仍然缺乏完整性。表面模型可以满足面面求交，线面消隐、明暗处理和数控加工的要求。表面模型的特点实体模型为了解决形体存在于表面的哪一侧的问题，可采用实体模型来描述三维立体在表面模型的基础上可用三种方法来定义表面的哪一侧存在实体。1）给出实体存在一侧的一点；2）直接用表面的外法矢来指明实体存在的一侧；3）用有向棱边隐含地表示表面的外法矢方向，该方法为CAD系统广泛采用。（思考：为什么不直接用法矢？）用有向棱边隐含地表示表面的外法矢方向时，规定有向棱边按右手法则取向：沿着闭合的棱边所得的方向与表面外法矢方向一致。思考：相邻两个面的公共棱边的方向不会矛盾吗？（有矛盾，CAD系统中增加“环”的定义解决矛盾）classPOINTclassEDGEclassFACE{{{同线框模型同线框模型intedge_num；//边数EDGE*edge;//边链表intface_type;//面类型SURFACEsur；//面方程………….………….………….}}}数据结构如下：根据实体模型，可以进行物性计算（如体积、质量，惯量）、有限元分析等应用。从前面的实体模型可知，本质上我们仍然采用了形体的边界表面的数学描述代替实体描述，并非真正描述了实体内部属性。这种典型的边界表面描述方法通常称为实体的边界表达方法（BREP），这在后面内容将详细介绍。线框、表面与实体模型的比较模型表示应用范围局限性二维线框画二维线框图（工程图）无法观察参数的变化，不可能产生有实际意义的形体三维线框画二、三维线框图不能表示实体、图形会有二义性表面模型艺术图形、形体表面的显示、数控加工不能表示实体实体模型物性计算、有限元分析用集合运算构造形体只能产生正则形体抽象形体的层次较低1、三维形体的计算机表达2、图形变换3、基础算法4、线框及消隐显示5、真实感显示6、图形学的其它应用图形变换在CAD系统中，经常将显示的形体进行放大缩小、旋转、平移等，以便用户更清楚地观察或编辑操作。实现形体放大缩小、旋转、平移的方法是图形变换。在CAD系统中，常用的图形变换有平移、旋转、比例、投影等变换。二维图形变换三维图形变换简单几何形体的图形变换应用举例Tzyxzzyyxxzyxzzyyxx111111888212121888212121式中：T为所要进行的图形变换矩阵假定一六面体ABCDEFGH各点的坐标分别为（x1,y1,z1）,…..,(x8,y8,z8)，则经过图形变换后的坐标为：图形的显示流程1、三维形体的计算机表达2、图形变换3、基础算法4、线框及消隐显示5、真实感显示6、图形学的其它应用1）网格剖分算法目前三维几何图形的显示算法均是基于三角形网格，且算法不断被固化到硬件中（如显卡、图形加速卡等），如：三维游戏及动画复杂场景渲染显示CAD模型显示有限元分析科学数据可视化电影、战场仿真A）平面上的三角剖分任意多边形的三角剖分平面点集的三角剖分边界离散网格生成网格后处理分析、显示软件一般处理过程B）参数曲面的三角剖分为了显示三维零件形体，CAD系统内部提供参数曲面的三角剖分算法，对形体的每一个表面都进行三角剖分，如图所示。经过三角剖分处理，三维零件形体表面都生成并记录了完整的多面体离散数据（即显示数据）CAD系统中的显示算法（线框图、消隐图、真实感显示图等）大多数都是基于该多面体离散数据的算法处理。C)空间散乱点集的三角剖分（曲面重建）曲面重建点集网格拓扑重建数据分割曲面拟合区域增量构造方法距离函数方法基于雕刻的方法基于边的方法基于面的方法参数曲面拟和隐式曲面拟和变形曲面拟和细分曲面拟和其他曲面拟和四边域曲面拟和三边域曲面拟和???合理分割数据并准确重建原产品特征约束模型仍存在困难???快速重建与产品外形拓扑一致的网格局部网格基于三维Delaunay的构造重建的网格拓扑同产品局部外形拓扑一致局部点集的三维Delaunay剖分得到对应的Voronoi图连接Voronoi区中心点得到局部构造网格在八叉树点集中快速得到绕中心点的邻域点集P1rP2rP3rP4rP5rP6rP7rPPD)有限元单元网格三角剖分有限元网格生成技术发展到现在,已经出现了大量的不同实现方法。当前广泛使用的Delaunay三角化、推进波前法和八叉树方法等。三维几何数据压缩是指对描述三维场景的模型数据进行压缩,以便于模型数据的存储和网络传输,在分布式虚拟现实、协同应用、多用户视频游戏、模型数据在计算机内部的存储和传输有着非常重要的意义。事实上三维图形的信息容量有时也非常大，给存储和传输带来了严重的障碍，必须进行压缩编码才适应现有的网络传输技术，而且在一些需实时处理的应用场合更需要压缩技术的支持。2）三角形网格压缩单分辨率模型的几何数据压缩单分辨率模型的几何数据压缩是指对物体的一种层次细节的多边形网格表示形式的几何数据进行压缩。使之生成：三角形条带、扇形、网格每个三角形独立地由其3个顶点的9个坐标来表述,如果用浮点数,则需要36个字节来描述一个三角形(暂且不考虑颜色、法向、纹理坐标等属性数据)；这种表述方案使得每个顶点约需被描述6次,浪费了大量存储空间。一种改进的方案是顶点和三角形分开表示，每个顶点用其3个浮点数表示的位置坐标确定;而每个三角形,则用三角形描述表来表示,其中每个表项仅包含该三角形的3个顶点序号.这使得存储空间得到很大程度的节省。三角形条带的引入进一步减少了不必要的顶点传输：两个相邻的三角形公用一条边,那么从第二个三角形开始,一个新顶点的加入和其前一个三角形的一条边即可构成另一三角形,这使得每个顶点最多必须传送两次。V0V2V3V4V5V1V10V9V8V7V6V12V11V14V13V15V0V1V70110111110110000000000000该技术有利于缓解图形显示硬件传输瓶颈，加速显示速度多分辨率模型的压缩是面向多分辨率模型的压缩方法，多分辨率模型可分为：离散多分辨率模型连续多分辨率模型离散多分辨率模型是对复杂的三角形网格通过简化算法逐步得到不同细节层次的多个三角网格模型连续多分辨率模型则是通过一种紧凑的模型表示方法,可生成任意多个不同分辨率的模型（不介绍）。多分辨率模型的几何数据压缩离散多分辨率模型的压缩离散多分辨率模型是对复杂的三角形网格经过一系列简化操作得到了多个不同分辨率的多边形网格模型。这种简化算法通过对三角形网格施以局部的变化而逐步得到不同的细节层次(LOD)，为了保证对原始网格的足够近似,每个简化步骤都须得到控制。在分布式图形应用中,针对多分辨率模型,累进传输是一个非常有效的传送措施。该方案的思想是首先传输LOD层次中一个最低分辨率的模型，然后在绘制操作开始的同时传送一系列的细化操作（类似JPGE2000思想）；逐步细化的LOD显示可以与更加细化LOD操作信息的传送同步进行,减少了操作人员的等待时间。但是由于累进传输对全局状态设置的要求以及累进传输受到传输速度的制约,使得累进传输的研究进展较为缓慢。随着研究的逐步深入，会使得几何压缩的算法更加成熟和先进，更能满足网络几何图形传输、分布式虚拟环境、电子购物等的应用需求,进一步推动计算机图形学向前发展。3）相交测试与碰撞测试在计算机图形学、CAD、CAE中经常遇到相交测试盒碰撞测试（运动物体）。如鼠标拾取，视窗裁剪、曲面求交、光线跟踪、布尔运算、装配干涉校验、动画漫游、运动碰撞、机器人与机床刀具的轨迹规划等。尤其对较大规模数据的模型而言，相交测试和碰撞测试的速度对系统影响很大。基本定义：射线：r(t)=o+t·dO:原点，d：射线方向T：参数轴对齐包容盒（矩形盒）：通常称：AABB表面平行于坐标面有向包容盒：简称：OBB即任意方向的AABB往往由一个中心，三个单位矢量和三个半边长定义包容盒离散有向多面体简称k－DOPn3n1n2n4s1d1maxd1min由k/2（k为偶数）个规一化法矢ni定义，每个ni有两个标量值dimin和dimax，由三元组（ni，dimin，dimax）描述一个平板层Si，所有平板层的交集是k－DOP的实际体积，上图为8－DOP。包容盒的创建：AABB：直接比较所有多面体（前面的离散多面体）顶点坐标即可得k－DOP：是AABB得扩展，将所有多面体顶点坐标投影到k－DOP的每条法线ni上，然后保留dimin、dimax，所有这些值定义一个最小的k－DOP。球体包容盒：计算比较麻烦。较为简单的方法是先计算AABB，再计算AABB的中心，以此为球心，球心到最远顶点的距离即为半径。其它更好更优的算法可查资料。显然，最远距离两点最为球的直径是最优解，关键是快速搜索。OBB：计算方法较多，较繁琐。方法之一是