三维形体显示技术

三维形体显示技术第1页，共33页，2023年，2月20日，星期三本章目的

1、了解三角剖分基本原理2、掌握形体线框显示技术3、了解线框消隐显示技术4、了解形体浓淡图简单绘制原理第2页，共33页，2023年，2月20日，星期三

CAD系统几何建模过程形体定义输入1形体定义输入2形体定义输入n内部CSG＋BREP表达布尔运算结果形体BREP表达三角剖分显示数据结构显示渲染显示参数定义工程应用第3页，共33页，2023年，2月20日，星期三在CAD系统中，用户采用参数化特征建模交互方式建立CAD模型，并以CSG＋BREP表达存储模型数据。11.1形体表面的三角剖分1）概述第4页，共33页，2023年，2月20日，星期三因此，必须将BREP表示转化为基于三角形的显示格式。在CAD系统中，广泛采用OpenGL、DirectX等显示技术。OpenGL、DirectX等广泛支持基于三角形网格的多边形显示技术（其简单编程介绍见讲义第2部分）。第5页，共33页，2023年，2月20日，星期三通常在CAD系统中，形体BREP表达面的方程多采用参数曲面等数学描述，面的边界多采用参数曲线描述。为实现形体线框消隐，首先需将形体的表面（曲面）进行离散，用平面多边形逼近的方法近似表示（多采用三角剖分），如下图所示。2）曲面三角剖分算法曲面三角剖分算法是CAD系统的基础算法，国内外关于该算法的研究文献很多（参阅有关参考文献）。第6页，共33页，2023年，2月20日，星期三经三角剖分处理后，形体上的所有面用三角形面逼近表示，形体上的边用三角形边的两个端点来定义，最终三维形体表面都生成并记录了完整的多面体离散数据（即显示数据）。CAD系统中的显示算法（线框图、线框消隐图、真实感显示图等）大多数都是基于该多面体离散数据的算法处理。在CAD系统中，为满足显示需要，通常采用全自动三角剖分算法，避免用户干预。则三角化算法主要考虑因素为算法速度、曲面逼近精度，其次考虑算法所生成的三角形数量（尽量少）。第7页，共33页，2023年，2月20日，星期三对于有限元分析来说，对网格剖分质量要求更高，通常网格剖分时允许用户进行适当交互。则对三角形的形态进行约束，如避免狭窄三角形、三角形密度变化比较平滑等。根据网格生成过程的不同，网格剖分主要分为映射网格划分和自由网格划分两类。映射网格划分是对规整模型的一种规整网格划分方法，对于面是四边形，网格划分数需在对边上保持一致；对于体是六面体，形成的单元全部为六面体。映射网格划分为多数商用有限元分析软件所采用。自由网格划分又分为节点连接法、拓扑分解法、几何分解法、栅格法等。在此仅介绍较为常用的节点连接法。第8页，共33页，2023年，2月20日，星期三步骤1：边界离散节点连接法该算法实现主要分为以下几个步骤：1）边界离散；2）参数域内部节点生成；3）参数域网格拓扑连接；4）曲面上映射；5）按精度自适应加密逼近。根据给定初始精度对曲面的边界及参数域边界进行离散，生成一组边界节点，构成多边形边界。步骤2：参数域内部节点生成考虑到空间曲面的复杂性，为使算法简便，网格生成先在参数域内进行，给定初始密度对参数域内部布置一定数量节点。为方便起见，不妨取水平方向或垂直方向按一定间隔扫描布点。如果所布置节点离边界节点或已有的内部节点很近，则取消该节点和调整间隔。第9页，共33页，2023年，2月20日，星期三步骤3：网格拓扑连接波前法：1985年由Lo.S.H提出。生成过程从外边界开始（此时前沿边即为边界），象波浪一样向区域内部推进。具体如下：1）每一次操作在所生成的前沿边中取出一条边，然后在所剩的内部节点中选取一个最合适的点，生成一个三角形；2）随之前沿边及剩余内部点集接着动态更新，直至网格全部生成（此时前沿边和剩余内部点集为空集）。该方法在选择内部节点的过程中，设三角形前沿边长为a，则所选点应使边b、c满足（b2＋c2）为最小即可生成合理的三角形。典型的网格拓扑生成算法两种：波前法、Delaunay方法。第10页，共33页，2023年，2月20日，星期三Delaunay方法：目前最为广泛的方法。其算法思想为：（Voronoi多边形生成算法可详见计算几何参考书）1）对于已生成的每一个节点Pi（i＝1,2,…,N）,在其邻域建立一个区域，一般是凸多边形，称Voronoi多边形；2）该多边形的边界由该点与其近旁的节点连线后并作的中垂线构成；3）该多边形只与那些与p点最邻近的点有关，较远的点不起作用；4）N个节点得到N个Voronoi多边形，连接两相邻多边形中的节点即为所求三角形。第11页，共33页，2023年，2月20日，星期三步骤4：曲面上映射将参数域所得的三角形网格一一映射到空间曲面，形成参数域与空间域一一对应的拓扑连接关系。步骤5：自适应加密对空间曲面网格的每个三角形进行校验，如果该三角形对曲面的逼近误差超过所需精度，则对该三角形进一步网格加密。加密方法主要有如右图所示三种方法，但要注意域邻近三角形的过渡连接，避免T型节点。算法说明：对于有退化情况的参数曲面，其算法应作一定修正。对于有限元分析，网格则还应增加一个优化步骤，避免狭窄三角形出现。第12页，共33页，2023年，2月20日，星期三11.2、多边形模型的几何压缩（选学）随着CG&CAD技术应用范围日益扩大，对计算机图形合成质量要求也不断提高，这就需要有足够精细的几何模型；三角化越精细，其数据容量越大，其存储、传输及显示越困难；因此，研究新的占用空间小、绘制速度快，适合于计算机网络传输的三维几何数据表示方法有着十分重要的意义。仅硬件升级不够，还需软件算法支持。1）几何压缩概述第13页，共33页，2023年，2月20日，星期三几何压缩分为：单分辨率模型压缩、多分辨率模型压缩单分辨率模型压缩算法代表：Deering等为代表的三角网格连接关系实时压缩算法Taubin等为代表的基于拓扑手术的压缩算法多分辨率模型压缩分为：

离散多分辨率模型、连续多分辨率模型

离散多分辨率模型压缩是对复杂的三角形网格通过简化算法逐步得到不同细节层次的多个三角网格模型；

连续多分辨率模型压缩则是通过一种紧凑的模型表示方法，可生成任意多个不同分辨率的模型。想一想，当你观看远处风景，你能看清细节吗？在CG&CAD中，对距离较远的物体进行显示时不需细节，而越来越近时则细节越清晰。由此提出网格模型简化压缩的需求，此即几何压缩。第14页，共33页，2023年，2月20日，星期三2）单分辨率模型的几何数据压缩指对物体的一种层次细节的多边形网格表示形式的几何数据进行压缩。使之生成：三角形条带、扇形、网格。目前图形加速卡均支持三角形条带、扇形、规范网格的传输和渲染显示。在计算机内部，每个三角形3个顶点（9个坐标）需36个字节来描述（不考虑颜色、法向、纹理等）。如果每个三角形独立表示并输出，则每个顶点被重复多次，浪费显存，影响传输（目前传输是瓶颈）。用三角形条带表示减少顶点传输量：相邻三角形公用一条边，从第二个三角形开始，每新增一个三角形增加一个点，这使得每个顶点最多只须传送两次。该算法的核心在于产生尽可能长的三角形条带，提高显示传送速度。第15页，共33页，2023年，2月20日，星期三3）离散多分辨率模型的几何压缩离散多分辨率模型是对复杂的三角形网格经过一系列简化操作，得到了多个不同分辨率的多边形网格模型。这种简化算法通过对三角形网格施以局部的变化而逐步得到不同的细节层次(LOD)。LOD技术在不影响画面视觉效果的条件下，通过逐次简化景物的表面细节来减少场景的几何复杂性，以提高绘制效率。该技术通常对每一原始多面体模型建立几个不同逼近精度的几何模型，每个模型均保留了一定层次的细节。目前很多造型软件和VR开发系统都支持LOD模型表示。第16页，共33页，2023年，2月20日，星期三针对多分辨率模型，累进传输是有效的措施。首先传输LOD层次中一个最低分辨率的模型，然后在绘制操作开始的同时传送一系列细化操作（类JPGE2000思想），减少等待时间。网格简化的主要目标是产生低分辨率近似，这种近似必须能保持原始模型的主要特征及总体外观。因此，一些特征点（或线）应保留。一般来说被简化的顶点（或边、面）处曲率半径较大，即平坦区域的三角形密度更小一些。目前网格简化算法可以被简单地划分为以下3种方法：（1）顶点去除(vertexdecimation)；

（2）

边折叠(edgecollapse)；（3）三角形折叠(trianglecollapse)。顶点去除边折叠三角形折叠第17页，共33页，2023年，2月20日，星期三11.3、简单线框显示线框显示简单快捷，适合于CAD实时交互。但有二义性。为了消除二义性及生成工程图，通常需进行消隐显示。经过三角剖分处理，形成了完整的形体三角网格显示模型的数据结构。为了直观快速交互显示形体，通常直接显示其线框模型。显示方法：遍历所有多边形网格的点表和边表，依次画直线。通常两种显示状态可以任选：a）仅显示轮廓边（内部边不显示）；b）显示所有离散多边形。第18页，共33页，2023年，2月20日，星期三11.4、线框消隐算法多面体消隐结果与形体几何有关，也与视点有关。从应用角度看，消隐问题分为：线消隐（Hidden-line）和面消隐（Hidden-surface）。前者用于线框图，如凸（凹）多面体隐藏线消隐算法；后者用于填色图，如Z-Buffer算法、扫描线算法、画家算法等。11.4.1、消隐算法概述第19页，共33页，2023年，2月20日，星期三外法矢与视线矢量的夹角θ将平面分为两类：（1）若θ≤90°，称后向面；

（2）若90°＜θ≤180°,称前向面后向面是不可见的；但前向面有可能全部可见，也可能部分可见。11.4.2凸多面体消隐算法对于凸多面体来说，前向面总可见，如右图所示。若观察方向V（从眼睛出发指向物体）与Z轴一致，则凸多面体消隐，仅需判断后向面（即V·N>0）即可把后向面的棱边全部消除。Vn想一想，机械制图课程中怎样判断可见性？第20页，共33页，2023年，2月20日，星期三为加速计算，可将凸多面体变换，使观察方向V（从眼睛出发指向物体）与Z轴方向一致，则仅判断前向面的法矢分量Nz<0即可。凸多面体消隐算法如下：//假设已知凸多面体的面—边—顶点表Begin

对凸多面体进行变换使V与Z同向；for（所有的面）

{计算该面法矢的Z分量Nz；

if（Nz<0）//为前向面{for(该面所有棱边）画出棱边；

}}EndVnizxy想一想，有什么更快速的方法判断后向面？第21页，共33页，2023年，2月20日，星期三课堂练习（一）如图，正六棱柱绕轴线l旋转45度，试判定旋转后面f的可见性。假设轴线l经过点（10，20，30），其方向矢为（0.5，-0.3，0.7）。yzof第22页，共33页，2023年，2月20日，星期三11.4.3、任意多面体消隐算法1）基本算法思路（1）所有后向面的棱边不可见；（2）为加速运算，对视锥以外的物体进行裁剪，减少不必要的运算；v投影平面前裁剪面后裁剪面投影平面前裁剪面后裁剪面vnunu透视投影的视见体平行投影的视见体对于任意形状多面体来说，后向面上的所有棱边仍不可见，前向面则有可能可见，有可能不可见，也可能仅部分可见。算法的重点是判断前向面的棱边的可见性。第23页，共33页，2023年，2月20日，星期三（3）对每一个前向面的所有棱边判断可见性，即判断面对线的遮挡关系。判断面与线的遮挡关系时将反复进行线线、线面求交，求交速度是关键。线面求交线线求交2）前向面直线段对任意某平面遮挡关系判断算法(1)若线段两端点及视点在给定平面同侧（图a），线段可见，转6；(2)若线段投影与平面投影的包围盒无交（图b），线段可见，转6；图a视点与线段同侧

图b包围盒不交第24页，共33页，2023年，2月20日，星期三(3)求直线与平面的交点。若无交点转4；否则交点在线段内部或外部，则判断：

a）交点在线段内，将线段分两段（图c），与视点同侧的一段可见，转6；剩余另一段在视点异侧，转4继续判断。

b）若交点在线段外部，转4继续判断。图c线段与平面求交(5)求第一段中点，若第一段中点在平面的投影内，则相应段被遮挡，否则不被遮挡；其他段的遮挡关系可依次交替取值判断（如图e）。(6)各可见段分别进入下一个面循环比较。直至所有面比较完毕，该线段判断结束。图e分段交替取值

(4)求线段的投影与平面边界投影的所有交点（图d），并求交点在原直线方程的Z值(即深度)，所求得的各交点将线段的投影分成若干段。若无交点，转6。图d线段投影与平面边界投影的交点第25页，共33页，2023年，2月20日，星期三（1）上述算法分析一条边、一个面的情况，对多边多面通过循环嵌套实现（可采用GPU并行算法加速）；（2）如果有N条棱消隐，当N很大时，用两两求交计算量很大O（N2）。为提高算法效率，需要减少求交工作量。常用方法有：加快相交测试；只对可见子线段进行可见性判断，对不可见线段不予计算；（3）消隐是一项非常耗时计算。现有商用CAD系统消隐算法正确率难以达到100%，尚不能完全满足工程图的特殊要求，且速度有待提高。（4）不同消隐算法的关键在于加速计算的策略和方法不同，重点在于线段可见性的判断速度和正确性。3）算法分析讨论该算法能支持工程图生成。对CAD图形来说，常常需要显示轮廓，而非内部三角形边界，上述算法必须修正：（1）过滤三角形内部边界，可加快速度，但丢失轮廓边界；（2）若显示轮廓边界，只需对边界和轮廓边进行消隐计算；（3）工程图中部分不可见边用虚线绘出，需单独标识。第26页，共33页，2023年，2月20日，星期三注意：（1）该算法计算量大，非常耗时，不适合实时交互操作（如拖动）；（2）由于求交量大，因精度误差导致消隐图局部有时出现暇次；（3）曲面的轮廓线不够光滑。第27页，共33页，2023年，2月20日，星期三11.5.1、光照效果影响因素思考：我们所见物体的颜色是怎样形成的？影响观察物体颜色的主要因素有哪些？11.5、形体浓淡图简单绘制光：当光照射到物体表面时，物体对光会发生反射、透射、吸收、衍射、折射和干涉。被物体吸收的部分转化为热，反射光和折射光则遵循反射定律和折射定律。

第28页，共33页，2023年，2月20日，星期三颜色：是光刺激人眼而产生的主观感觉，是物理和心理相互作用的一种复杂生理反映，使我们能看见物体的颜色。物体的颜色不仅取决于物体本身（材质、粗糙度等），而且还与光源（光的特性）、周围环境、以及观察者的视觉有关。但人的感觉也会出现错觉哦（如下图）！古言：耳听为虚，眼见为实，对吗？？第29页，共33页，2023年，2月20日，星期三实验表明：白光经棱镜被分解为红、橙、黄、绿、青、蓝、紫的可见光谱。人对红、绿、蓝三色最敏感，红色最强，蓝色相对较弱。三基色（三原色）原理：大多数的颜色可以通过红、绿、蓝三色按照不同的比例合成。三基色相互独立，任何一种基色都不能有其它两种颜色合成。某一种颜色和这三基色的关系可用下面的式子来描述：在计算机图形学中有两种三基色系统：红、绿、蓝加色系统(RGB)和青、品红、黄减色系统(CMY)

，前者适合显示系统，后者适合印刷系统。RGB加色系统CMY减色系统三基色（或三原色）颜色C＝R(红色百分比)＋G(绿色百分比)＋B(蓝色百分比)第30页，共33页，2023年，2月20日，星期三11.5.2简单效果的浓淡图生成1）多边形填充——Flat模型算法思路及步骤：1）颜色计算：以三角形为单位计算颜色，根据多面体表面的平面法矢决定颜色值，其颜色值根据法矢与光线的夹角确定（平行于光线最亮）。2）三角形填充：利用第2讲基于扫描线的多边形填充算法（或直接调用OpenGL的多边形填充算法）即可。该算法简单，但所绘制图形的轮廓分明，各多边形之间过渡不光滑，没考虑视线及其它光照环境因素。例：基于OpenGL进行Flat模型编程实验。

仅需对第2讲中的MyDiisplay（）函数进行简单修改即可。第31页，共33页，2023年，2月20日，星期三voidmyDisplay(void)

{

glClear(GL_COLOR_BUFFER_BIT);//buffer设置为颜色可写

glShadeModel(GL_SMOOTH);//设置为光滑明暗模式

//第1个三角形

glBegin(GL_TRIANGLES);//开始画三角形

glColor3f(1.0,0.0,0.0);//设置第一个顶点为鲜红色

glVertex2f(-1.0,-1.0);//设置第一个顶点的坐标为（-1.0，-1.0）

glColor3f(1.0,0.0,0.0);//设置第二个顶点为鲜红色

glVertex2f(0.0,-1.0);//设置第二个顶点的坐标为（0.0，-1.0）

glColor3f(1.0,0.0,0.0);//设置第三个顶点为鲜