基于几何和属性误差的边折叠网格简化算法.pdfVIP

维普资讯 大 庆 石 油 学 院 学 报 第 31卷 第 1期 2007年 2月 VoI．31 No．1 Feb． 2007 J0URNALOFDAQINGPETROLEUM INSTITUTE 基于几何和属性误差的边折叠网格简化算法 刘贤梅 ，张 婷 ，田 枫 (大庆石油学院 计算机与信息技术学院，黑龙江 大庆 163318) 摘 要：针对基于 LOD技术的三维虚拟场景的快速绘制需求 ，提 出一种带属性 的边折叠 的三角形 网格简化方法．该 方法利用二次误差控制简化，通过边折叠操作完成简化过程．用二次误差衡量三角形网格表面的几何精确性和表面属性 的逼真度 ，使简化后的模型尽可能保持原有属性特征 ，得到了较高质量的简化 网格 ．将该网格简化方法应用于采油厂厂 区漫游和安全训练仿真系统 ，达到了实时绘制 的目的． 关 键 词 ：边折叠 ；三角形网格 ；网格简化 ；二次误差 ；几何误差；属性误差 中图分类号：TP393 文献标识码：A 文章编号：1000—1891(2007)01—0076—03 虚拟现实的实时真实感图形生成与绘制 中的加速技术十分关键．当建立比较复杂 的三维虚拟场景 时，需要大量的多边形才能刻画出复杂物体的细节，虽然绘制的图像质量越来越高，但同时也导致多边形 数据量过大 ，难于存储 、传输和绘制．应用过程中，常常把复杂描述和简要描述相结合 (即LOD技术)．为 了实现基于 LOD技术的三维虚拟场景的快速绘制 ，需要对复杂的三维模型网格实行简化操作．在图形系 统中，三角形面片是最通用的绘图元语[1]．三角形 的基本联结关系简单 ，任何图形库和图形硬件系统都能 处理三角形网格 ，曲面也可以利用三角形网格描述 ，现实生活中的环境 、人 、物体等的三维形态都可以通过 三角形 网格进行描述．由此 ，LOD模型的 自动生成可以转化为三角形网格简化问题． 1 算法描述 网格简化的 目的是把一个三角形 网格模型用一个近似模型表示 ，近似模 型基本保持了原始模型的可 视特征(即满足对原始模型逼近精度的要求)，但三角形面片数少于原始网格的三角形面片数．通常的做 法是把一些 “不重要的”图元 (顶点 、边或三角形)从三角形网格 中移去．网格简化算法可 以分为 自适应剖 分型、重采样型和几何元素删除型等 3类口]．在删除型算法中，几何元素可以是顶点、边 、三角形 ，它们运 用简化元操作对原始 网格模型进行处理 ，从而得到简化模型，简化元包括顶点删除、三角形删除、边折叠、 三角形折叠和顶点聚类．文中主要探讨边折叠方法． 1．1 基本定义 定义 1 三角形网格 M 由顶点集合 ’，和三角形面集合F定义 ，三角形面仅沿公共边及在顶点处相邻 接 ，每个顶点 v(vEV)由一个几何位置 p(pER。)和 m个特征量 s(sER )表示 ，这 2个元素构成一个列向 量 v一 (ps)。，vERa+埘．例如 ，一个 网格顶点若具有 (r，g，6)颜色特征 ，则 仇一3，即v一[z，3，『z，r，g，6] ； 若具有颜色和法线特征 ，则 一6．每个三角形 ，(，∈F)由一个顶点三元组 (1，，l，，l，。)表示． 定义 2 对于M 中任意一条边 ，如果该边只为一个三角形享有 ，则称该边为边界边 ，该边的2个顶点 称为边界顶点，该边所在的三角形称为边界三角形． 1．2 简化思想 边折叠是指把三角形网格模型的一条边折叠成一个新点，并把与这条边相连的点都连接到新点上 ，同 收稿 日期：2006一O5—19；审稿人：李从信 ；编辑 ：郑丽芹 基金项目：黑龙江省自然科学基金项 目(F0517) 作者简介 ：刘贤梅(1968一)，女，硕士，副教授 ，主要从事虚拟现实 、计算机 图形学方面的研究． · 76 · 维普资讯 第 1期