几何模型数据压缩及虚拟场景实时显示技术研究

几何模型数据压缩及虚拟场景实时显示技术研究几何模型数据压缩及虚拟场景实时显示技术研究绪论基于细分网格的数据压缩方法基于视点的网格简化算法基于视觉敏锐度的实时显示技术虚拟环境实时显示仿真系统结论绪论本文研究内容的必要性分布式虚拟环境研究概况基于渐进网格的传输方法综述几何模型数据压缩综述实时显示方法的研究概况本文完成的主要工作及其意义本文研究内容的必要性在分布式虚拟环境系统中有时需要快速传输几何数据，基于渐进传输的多分辨率几何数据压缩技术能够较好地解决这种大数据集的传输问题。对于复杂的动态交互场景，当前的高档图形工作站也难以保证实时地显示十分真实的图象。由于实时交互始终是分布式虚拟环境技术中一项基本要求，因此，一种普遍接受的方法是通过牺牲部分渲染图象的真实性，来换取整个系统的交互实时性。细节层次模型(简称LOD)管理是实现实时显示技术的一项重要工具，为了获得LOD模型，需要对几何数据进行简化。有了LOD模型，就可以应用各种显示策略实现分布式虚拟环境中虚拟场景的实时显示。本文主要研究了分布式虚拟环境中信息压缩及实时显示技术。基于渐进网格的传输方法综述通过对一给定网格（原始网格）进行某种变换，将其表示为一个很小的基本网格和一系列逐渐精细的细节信息的形式，这些细节信息能够为原始网格的精确（或近似）重建提供全部信息，本文将这种表示形式的网格数据称为渐进网格。渐进网格表示方法有利于多分辨率模型的存储和传输。在分布式虚拟环境中，交互的实时性是一项非常重要的指标。如果用户在交互之前等待正在传输的一幅精细的模型数据，势必造成用户时间的极大浪费，且很难保证交互的实时性。渐进传输就是在这种背景下提出的。几何数据压缩与简化综述在分布式虚拟环境中有时需对几何模型进行传输，通常几何模型数据量非常大，因此，必须对之进行压缩。几何数据压缩技术是为了解决大数据集的传输或存储而发展起来的实用技术。几何模型可分为单分辨率模型和多分辨率模型，因此，几何模型的数据压缩可分为单分辨率模型的几何数据压缩和多分辨率模型的几何数据压缩。下面分别进行介绍。单分辨率模型是指几何实体的某一层次细节的多边形网格表示形式，如果缺少该模型中任何一部分数据，则无法对该实体轮廓有一完整理解。单分辨率几何数据压缩是指对实体的某一层次细节的网格数据进行压缩。下面三种方法是比较有代表性的算法：(1)基于通用三角形网格的几何压缩(2)三角网格连接关系实时压缩算法(3)基于拓扑手术方法的几何压缩算法单分辨率模型的几何数据压缩综述多分辨率模型的几何数据压缩综述多分辨率模型是指几何实体的多个层次细节网格表示形式，相当于该实体的多个不同分辨率模型的集合。多分辨率模型又可分为离散多分辨率模型和连续多分辩率模型两种。对复杂网格进行简化，得到不同细节层次的多个三角网格模型，称之为离散多分辨率模型。连续多分辨率模型则是一种紧凑的模型表示方法，可生成任意多个不同分辨率的模型。基于这两种不同模型，面向多分辩率模型的压缩又可分为面向离散多分辨率模型的压缩和面向连续多分辨率模型的压缩。模型简化是几何数据压缩的基础。因此，下面首先介绍模型简化技术。层次细节模型数据简化技术综述网格简化算法可以被简单地划分为以下三类：（1）顶点去除(vertexdecimation)；（2）边折叠(edgecollapse)；（3）三角形折叠(trianglecollapse)。其中有代表性的算法有下面几种:（1）顶点聚类（2）区域合并（3）顶点抽取（4）迭代塌陷（5）小波分析方法图1-5边塌陷连续多分辨率模型的几何数据压缩综述多分辨率分析是支持压缩、渐进传输和复杂网格的LOD控制的基础工具，其中心思想是分解函数到低分辨率部分和一系列增加分辨率的修正项。网格的多分辨率数据压缩表示通常是由基本网格和提供丢失细节的修正项序列组成。下面两类是比较有代表性的算法:（1）基于小波分析的压缩方法（2）累进森林拆分压缩方法实时显示方法研究综述对于复杂的动态交互场景，为了使交互可视化达到实时性要求，需保证指定用户的目标幀速率。所谓实时显示方法，是指通过牺牲部分渲染图象的真实性，来换取整个系统的交互实时性的一种显示策略。几种有代表性的方法:（1）可见度判别方法（2）细节省略方法（3）自适应细节省略方法（4）定向凝视的自适应渲染方法（5）封闭选择（occlusionculling）方法基于细分网格的数据压缩方法必要性细分网格概念带有细分连通性的多分辨率模型的获取基于细分网格的数据压缩方法近似细分网格的重建及仿真实验结果本章小结对多分辨率模型数据压缩的研究很多，其中较有代表性的是下面介绍的两种方法。Eck多分辨率表示方法优点：能快速、连续地通过一种紧致的表示来获得多面体的多分辨率模型。缺点：没有利用正则曲面光滑特性，压缩仍有冗余。Khodakovsky等人的法线网格（normalmesh）优点：有较高的压缩效率,该方法有着广阔的应用前景缺点：产生法向网格的方法比较复杂本章提出了基于细分网格的压缩方法。该算法利用正则曲面的光滑特性，用一维标量代替部分三维细节信息。实践中，完全满足正则曲面条件的曲面很少，而具有细分连通性的细分曲面近似满足正则曲面条件。必要性图2-1细分网格具有细分连通性的网格，被称之为细分网格，这种细分连通性是由均匀分裂算子产生的。所谓细分连通性，是指由一个基本网格M0经过若干次一分四的分裂（细分）而形成的三维图形所具有的三角面片或顶点间的邻接和父子关系，如图2-1所示，该细分网格没有经过平滑处理。细分网格概念Fig.2-2ButterflyschemeFig.2-3Loopscheme带有细分连通性的多分辨率模型的获取采用Eck算法来获取带有细分连通性的多分辨率网格，基本想法是对多面体M进行局部参数化，并基于该参数化用重新采样技术生成多分辨率模型MJ，其中MJ具有与M相同的拓扑类型。细分网格的数据结构structFace{level_J;//整型数(层数)children[4];//面指针数组cornerVertex[3];//顶点指针数组(指向面片的三个顶点)edgeVertex[3];//顶点指针数组(指向细分该面中的三条边的三个顶点的指针数组)unitNormal[3];//法线信息数组};基于细分网格的数据压缩用下面结构表示顶点：structVertex{parentV[2];//顶点指针数组(指向该顶点所细分的边的两个顶点)parentF[2];//三角面片指针数组(指向该顶点所细分的边的两个面)fGeom;//坐标位置g;//XYZvector};细分网格的分解为了产生更粗糙层次的近似Mn-1，……，M0，我们使用逆细分算子，即撤消在Mk+1上的1-to-4分裂操作。设S是原始细分操作算子，那么网格Mk+1和其粗糙表示Mk满足如下关系：（2-4）（1）首先给粗糙网格结点分配位置，使其满足公式:（2-5）（2）对Mk进行细分操作，得到，但是网格中的奇数结点的位置必须得到纠正，以便精确地复制原始网格，这就需要为Mk+1中每一个奇数结点存储一个细节向量,Dk是Mk+1和之间对应奇数结点位置的差值。MSMkk11evenkevenkSPP1Mk~1Mk~1Mk~1oddkoddkkSPPD1:当某一细分层的抽样公差与上一细分层的抽样公差之差值小于压缩误差时，对该细分层求法向细节标量。要想求法向细节标量，首先需求出细分切平面的法线，然后将细节向量投影到细分切平面的法线方向上，细节向量在法线方向上的分量可以由一标量乘以单位法向表示，该标量就是法向细节标量。重建过程中，在每一细分步之后，加入这些法向细节标量，结合法向细节标量与对应的单位法向量，近似地恢复原来的细节信息(如公式(2-6)所示)。(2-6)其中为法向量，x为标量。图2-6求法向细节标量的活动标架图2-7细分网格中的法向图2-8面片abc和acd内的第二细分层上的顶点编码细节信息编码图2-9网格的近似重建近似细分网格的重建图2-11兔子的渐进网格仿真实验结果及分析本章提出的方法可以实现渐进传输，即几何数据可以被表示为一个较小的基本网格和一系列细节信息。该方法利用正则曲面法线向量特性及细分曲面的细分连通性，用一维标量信息代替三维信息，即对细节信息进行了压缩，该方法属于有损压缩。本章小结基于视点的网格简化算法必要性Garland-Heckert算法及轮廓线基于视点的网格简化算法外观相似性评价复杂性分析仿真结果及分析本章小结必要性Garland等人提出的基于二次误差度量的几何简化方法，采用二次误差度量来刻画误差，计算效率高，质量好。该算法能处理任何拓扑结构的三角网格，有效地产生细节层次模型。但是，该算法存在不足之处：在多边形较少的情况下，模型变粗，外观细节丢失较多。这是由于Garland方法并不能较好地保持模型外观特征所造成的。本章提出了基于视点的网格简化算法，该算法是为实时显示技术服务的，它能为实时显示算法提供细节层次模型。Garland-Heckert算法及轮廓线二次误差度量的几何简化算法图3-1边收缩基于视点的二次误差度量网格简化算法视点的选取通常，我们所说的基于视点是指考虑视点坐标，视线方向及观察者与聚焦平面的距离。本章中所使用的视线向量是指中心视线方向的单位向量。我们以观察兔子为例，概率最大的视线方向依次是侧向，前向及后向等。对重要的视点进行充分的抽样，抽中点尽可能不被移走；如果忽略了视点空间中某些重要部分，就很可能移走很重要的特征。为了简化计算量，目前我们只选择了侧向视线方向。基于视点的抽样准则定义1：在某一视点条件下，将三维模型投影到二维视平面上，其中映射到模型的二维边界上的三维模型中的那些对应边即为在该视点条件下模型的外观特性边界。后面提到的边界均指这种边界。引理1在视点Viewpoint下，如果给定模型是一个凸多面体，则边e是边界的充分必要条件是：(a)边邻居(b)边不在边界上(c)边在边界上图3-4两个相邻面的单位法向示意图基于视点的二次误差度量网格简化算法下面给出算法的具体步骤:步骤1：给出视线方向（单位向量）；步骤2：为所有初始顶点计算Q；步骤3：选择所有合适的点对，点对或者是一条边，或者满足，其中t是给定的阈值参数；步骤4：计算每一顶点对的最优收缩目标点和相应误差，把顶点对按误差大小顺序放在堆栈中(在顶端有最小误差)；步骤5：从堆栈中移走最小误差的顶点对，如果目标面小于300，且该顶点对没有超过最高抽中次数，则执行第六步；否则转到第七步；步骤6：应用基于视点的抽样标准公式：1）.如果，将原误差以代替，并把该顶点对按更新后的误差大小顺序放在堆栈中(在顶端有最小误差)，转到第八步；步骤7：使该顶点对收缩,然后更新包含v1的所有顶点对的误差；步骤8：如果目标没有达到，转到第五步；否则，结束。外观相似性的评价模型M的外观是在某一视点条件下由渲染系统产生的光栅图象I确定的。在某一视点条件下，如果模型M1和M2的对应图象相同，那么我们可以认为两模型M1和M2在视点条件下外观相同。如果I1和I2都是mmRGB光栅图象,可以用下面公式定义两者之间的不同[64]：其中是两个RGB向量与之差的欧氏长度，我们称为外观相似性误差。在给定视点下，如果M2是M1较好的近似，那麽值很小。如将灰度图象转换成0-1图象（即属于简化模型的象素点赋值为1，否则为0），那么也可以采用下面公式计算外观相似性误差：复杂性分析仿真结果及分析图4-9应用MSNS算法简化的网格图形本章提出了一种基于视点的非均匀抽样网格简化算法，它是通过采用视点空间中某些重要视点对各自轮廓进行抽样，以便用尽可能少的三角面片来表示尽可能多的模型外观特征。实验结果表明，该算法具有如下优点：可以在三角面片数较少的情况下，尽可能地保持了模型的重要外观特征。本章小结基于视觉敏锐度的自适应实时显示技术研究必要性视觉敏锐度概念基于视觉敏锐度的自适应实时显示算法仿真结果及分析本章小结对于复杂的动态交互场景，为了使交互可视化达到实时性要求，