（计算机应用技术专业论文）支持交互绘制的巨型网格表面简化技术研究.pdf

北京工业大学工学硕士学位论文 k e y w o r d sc o i n p u t c rm o d e l i n 吕s i m p l i f i c 撕o no f h u g em e s h e s ；c 衄o f c o r e ；o c t - 仃e e s t r i l c t t l r e ；m u l d - r e s o h 岫o nr 印r e s e n t a 正o n i v 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 签名： 日期：趔 ：q ：笪回 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 日期：挫q ：口 1 1 多边形模型应用 第1 章绪论 多边形模型是计算机图形学上最常用的一种3 d 模型表示方法，其简单，高 效，能够表示各种形状的表面模型。基于多边形的计算可直接为各种图形显卡硬 件支持。 现代技术能够生成超大数据量的多边形表面模型。大型激光扫描仪，计算机 算视觉系统，医学图像设备都能够生成复杂的多边形表面模型。近年来，随者计 算机技术的发展，全世界的数字文化遗产是一个非常热点的研究项目。数字文化 遗产项目要求在计算机上精确再现各种艺术雕塑和建筑模型，从而可以为各种研 究项目所使用，并且结合网络图形技术，使全世界的人们都可以通过互联网来领 略艺术文化遗产，其中，既有巨大的商业价值，又是对文化遗产的一种保护。数 字文化遗产的技术目标是，利用现代计算机技术，精确再现艺术遗产的每个细节， 使人们在计算机上可以浏览，查看，获取艺术文化遗产的每个细节和属性。但是， 这些现实中的模型体积往往非常巨大，虽然利用大型3 d 扫描仪能够精确地获取 模型的每个细节信息，但是获取的数据量往往非常巨大，例如，著名的大卫雕像 扫描生成的数据量高达几个g b 的数据量。这些上g b 数据量虽然可咀精确记录 模型细节，但是模型可视化确是一个非常严峻的问题。某些超级计算机能够处理 这么大的数据量，但是超级计算机并不能为大多数人所用，大量普及的计算机却 没有能力处理如此庞大的数据量。 为了能够可视化这些巨型模型，使人们都可以通过互联网等手段对模型进行 浏览，建立巨型网格的多分辨率表示模型是最主要的手段。传统的多分辨率模型 都是核( c p u 和内存) 内的，通过网格简化方法来生成网格多个细节层次模型 ( i d d ) 。如果利用传统的简化方法来生成多分辨率的网格模型，只能够完全依 靠内外存i o 缓冲和虚拟内存机制。传统的核内简化方法，在每次简化时，必须 参照整个模型信息。将传统的核内方法应用于巨型网格时，就必须像处理传统模 型一样，对整个模型数据进行检索。由于大部分的网格数据是存储在外存上的， 在对整个模型数据进行检索时，绝大部分的时间完全消耗在内外存加数据访问 在对整个模型数据进行检索时，绝大部分的时间完全消耗在内外存数据访问 北京王业大学工学硕士学披论文 上。而一次内外存i ，o 的时间和次内存“o 的时间相熬了很多个数量级，比如， 从外存取一个字节的时黼与从内存区一个字节的鞋于阉鲔差羽藕懑子l o 天与l 移 的差别 ”。当然，实际的内外存会因为外存缓冲区机制速发会大大提高。 所以研究基于核外的简化算法成为当今的一个研究热点。 1 2 基千核外模墼的网格简化介绍 网格简化的基本思想就是找到另外组多边形，该缆多边形表示的模型与原 始网格表示豹多迭形具商最小的几何距离。按照可否在斑存中逃行处理，可以撼 3 d 多边形表面模型分成两大类，核内( i o c ：h lo fc o r e ) 模黧和核外( o o c ： 0 越o f e o 揩) 模耀。基予孩乡 挨整麓夔化葵法髂必菝乡 麓纯霎浚，反之，黎为援 内简化算法。 棱乡 篱证算法基本瓣怒是建立表嚣瓣格数撵鲍素弓l 结梅，程筵索弓l 结椽基璐 上，对网格进行简化。在索引结构上使用的简化方法，必须和索引结构相适应。 腻存储的方式来看，3 d 模整的本质是一个多边形集合，这些多迭澎集合近 似模拟了一个现实摸型豹几何逡续表殛。网格麓化分为两_ 种近似，表面属性近似 和几何近似，本文中所讨论的网格简化专指几何角度的嘲格简化。 在核多 模型上建立多边形黛合素弓| 缕橡，葵基本懿慰想是按照尼露经要对多 边形集含进行索引，基本方法魑按照空间位置关系把多边形分成一个个子集合， 每个子集表示一个多逮澎瑟冀。辩匿羹模墅表瑟分害l 方法是萋予多 存捺房戆，懑 道外存排序算法，将多边形按照空间位溉，重新安排每个多边形在外存中的位置， 使其形成一个个多边形簇，每个簇内的多边形分布予同个凡何空闯内。表露分 割方法建立了一耪对巨烈网格数据的素弓l 结构，按照空闻来索引多边形簇。 建立核外模型的外存索引结构，可以大大减少检索核外模型数据的o 冗余， 丈夫热抉了模型数据豹擒索速发。瞧是，在实躲的核始模型应翔孛，单革姣靠送 种索引结构，远近不能达到数据的实时检索。农可视化应用中，处理核外模型撼 零愚怒怒在魏索孳| 结穆瓣基磷上，霹模蹙遴行麓继，建立棱羚臻垄! 豹多分瓣率淡 示。巨烈网格的多分辨率表示，使实时测览巨型网格成为可能，不仅仅可以应用 予文仡遗产等可筏仡顼嚣，两样也用于大鍪l 瘟缎现实应雳，院鲡飞季亍禳羧，战场 模拟等。 第l 章绪论 基于核外模型的网格简化方法，同传统的核内简化方法最基本的不同就是， 核外模型简化，每次只能够加载模型的某一部分，只能对模型的某一部分进行简 化。根据模型的最优化表示理论，要达到一个模型的最优化表示，必须参照原始 模型的全局信息。所以，基于核外模型的网格简化方法研究焦点在于，在简化过 程中，如何在不访问模型所有信息的情况下，达到网格的最优化表示。 本文主要的工作在于两点： l 、该进现有核外模型的外存索引结构，结合表面网格的特点，进一步提高 网格数据检索效率。 2 、基于本模型的索引结构，确定核外模型表面网格简化方法。 1 3 前人工作 之前的关于核外模型的筒化方法，主要研究点在：一、核外模型外存索引结 构建立方法；二、核外模型简化过程中的误差控制。 建立外存索引结构的主要途径是对面片进行分割，主要有两类分割方法，固 定分割方法和自适应分割方法。固定分割方法最早应用于高度域( h e i g h tf i e l d ) 图形处理上，因为高度域图形可以将面片映射到某个平面上，而后对该平面进行 固定分割。这种方法简单，高效，每个分割块内多边形连通，只有一个独立面片， 但是需要对分割边界进行专门的处理。应用非高度域的3 d 网格，方法高效，分 割速度快，但是某些节点内会包含多个独立面片。自适应的分割方法利用多边形 的关联性，和简化误差来进行分割平面，其特点不需要进行专门的处理，其每个 节点内部只包含一个独立面片，建立过程中就建立了网格的多分辨率表示，但是 其处理速度非常慢，而且算法设计非常复杂，通用性不好，且建立过程依赖于所 使用的简化策略。 核外简化过程中的误差控制集中于通过对比其他的节点的简化代价，其基本 思想是将核内简化方法应用这种索引结构上。基于固定分割的索引结构的网格简 化方法，都必须有一个结构来记录简化过程中的误差，根据这些误差来确定导入 节点的简化程度。基于自适应分割索引结构的网格简化方法，则是完全基于核内 的误差评价方法，对每个面片进行单独的误差评价。 本文所确立的方法建立索引结构采用了基于八叉树的固定分割方法，但是在 北京工业大学工学硕士学位论文 分割完成后进行了专门的处理，保证每个节点内部只包含有一个面片。在此基础 上确定基于节点的误差评价，采用了边收缩最大误差作为面片简化代价，在对每 个面片进行简化时，则采用了一种“简化步长”，简化到一定程度后再于其它的 面片进行比较。实验证明这种简化策略的效果，在几何误差方面是非常好的。 1 4 本文工作 本文提出的算法对巨型多边型网格模型的简化提供了一种解决方法，首先对 传统的八叉树分割方法做了改进，建立共享多边形结构，而后进行面片合并处理， 提高了八叉树模型的检索效率。在此基础上，确定了以面片为单位的巨型网格简 化方法，阐述了基于面片误差评价与面片简化步长相结合的方法对巨型模型进行 简化，其中面片误差评价采用了基于二次误差矩阵的边收缩最大代价作为面片误 差，简化步长是基于多边形数目。 本文的特点有两点： l 、改进了传统的基于八叉树分割方法中，对八叉树结构进行专门处理，使 每个叶子节点内只包含一个独立的面片，且叶子节点的数据较为平均，便于基于 节点作面片误差评价。在面片的边界处理中，采用了共享多边形的结构，不必要 专门对边界进行处理。 2 、在基于面片的简化方法中，使用最大边收缩代价的面片误差评价方法和 使用了多边形数目来决定单个面片简化步长。 1 5 论述结构 本文在第2 章首先论述了传统的核内简化策略，相关的分片算法，模型简化 误差评价理论。第3 章分析了基于八叉树的分割策略的不足，并且改进的方法， 并且阐述改进八叉树模型的简化方法：第4 章，通过实验对算法作了验证，确定 算法的局限性。 第2 章巨型网格简化基本理论 第2 章巨型网格简化基本理论 2 1 多边形网格核内简化方法 多边形网格m 由一个顶点集合y = ( v 1 ，叱，一) 和一个面集合 f = 石，五， ) 组成，它确定了一个特定分辨率模型。因为所有的非三角形多 边形都可以三角化为三角形集合，我们之后所说的多边形特指三角形，多边形网 格就指三角形网格。设有一个多边形网格表示的模型m ，想得到一个近似的多 边形网格m ，其中近似网格m ，包含较少数目的多边形但跟原始网格吖近似， 多边形网格简化的目的就是为了能够从原始网格模型m 自动产生它的近似网格 模型m ，。 多边形表面网格简化多应用于降低超量采样模型的数据量，比如有扫瞄设备 扫瞄模型。这类模型通常是均匀三角化，在平坦区域与高曲率区域的三角形密度 是相等的，但是如果三角形的密度符合网格局部曲率相适应，那么表示同样的模 型时，多边形数目会相对较少一些。经验证明 2 】，三角形数据往往可以被减少5 0 左右，但是其外形同原始模型却基本相同。 由于多种不同的应用，我们希望的模型可能不是一个单一的简化模型。多分 辨率模型是模型一种表示方式，这种表示方式可以覆盖模型在一定范围内不同的 近似表示，可以重建其范围内的任何一种近似表示。为了满足于实时应用，重建 近似模型表示的代价必须很低，另外还有一个要求，多边率表示的模型跟原始模 型和各个近似表示模型在数据量上应该是同一个数量级。 核内简化算法指的是只利用内存与c p u 的简化方法，主要分类标准是它们 是否会改变模型表面的拓扑结构。一些算法严格限制拓扑结构的改变；大部分算 法会基于几何标准来简化，但是简化过程中的一个附带的效果就是会简化模型的 拓扑结构；另外的算法会明确简化表面拓扑结构和几何结构。 在一些应用中我们必须防止拓扑结构的改变。比如在医学图像应用中，保留 心脏壁上的洞要比保留表面的精确形状要重要的多。在大多数的绘制应用系统 中，简化模型的拓扑结构就是非常必要的。比如一个海绵模型，海绵上的各种孔 洞是非常重要的视觉特性的，但是如果从很远的距离来看，这些空洞基本不可见， 北京工业大学工学硕士学位论文 整个模型基本上就等于一个长方体盒子。 表面模型假设是流形的。实际中遇到的大部分的模型是流形的，大部分的简 化算法需要流形的模型。 2 1 1 手工简化 最早期的游戏和飞行仿真领域的模型部是手工简化的，这种方法依赖于特定 的模型编辑器来产生各种不同分辨率的模型，是一个耗时且繁琐的工作，这是一 种早期的原始的模型简化方法。 2 1 2 细化方法 通过渐进细化模型的方法生成多分辨率模型的方法很早就提出来，子剖分方 法是一种常见的细化方法。细化方法一般多用于曲线和高度域恻图形的多分辨率 模型生成，马赛克化方法则多用于一般的曲面。在一般曲面上使用细化方法最主 要问题在于初始的粗模型的构建，如果通过简单的子剖分规则来细化模型，则近 似模型的拓扑与原模型的拓扑一定相同，这种方法是保证模型拓扑的一种方法。 2 1 3 顶点簇方法 顶点簇方法【1 】【2 1 把几何空间分成一个顶点簇集合，把相同簇内的顶点合并在 一起。这种算法速度快，可以在任意的三角形网格上，但是生成网格的效果不好。 最简单的顶点簇方法是均匀顶点分簇算法，首先通过子剖分包围盒分成一 个以格子，把顶点集合分配到每一个格子内，每个格子通过一些实验上有效的标 准计算一个代表顶点。这个过程执行效率会很高，但这种算法往往会改变原始模 型的拓扑结构。如下图所示，本来分离的部分在简化完成后会结合在一起。这种 算法对分割过程中分割线位置非常敏感，并且不能够简化那些大于单位格子的多 边形。 扩展均匀分簇方法的最自然的想法就是使用自适应的分簇方法【3 】，比如八叉 树分簇法。在重要顶点周围聚簇就会很好的改善简化效果。 第2 章巨型嗣格简化基本理论 b 利b f ea 翕盯 图2 一l 顶点簇简化方法示意图 f i & 2 - lv 矾e xc l l l s t e r i n gs i m p l i 丘c 撕o n 当原始模型过采样时并且简化目标不高的情况下，分簇方法会有很好的效 果，其中，表面三角形的大小要远小于格子大小，顶点移动的距离要远小于格子 的直径，当简化的要求很高的，分簇方法的效果就大大折扣。 2 1 4 区域合并 通过合并表面区域【4 】来简化模型也是一种可行的简化算法。超平面简化算法 【4 1 基于平面标准把表面分成孤立的区域，每个区域用一个多边形面片来替代，多 边形面面片的边界会被简化，简化后的结果被再一次三角化。这些算法适用于流 形表面，并不改变模型的拓扑结构。 区域合并的算法应用并不广泛，相对于其他的算法来说，简化效果不好，并 且计算复杂。 2 1 5 小波分解 小波分解的方法把一个表面分解成一个基形体和一系列的更细的表面细节， 近似模型可以通过丢掉一些不重要的细节来实现，这种思想成功地应用于模型多 分辨率表示。l 0 1 1 1 1 s b 哪6 增人开发了一种通过对关联信息作子剖分来分解表面的 方法，这种方法不容易产生最优的网格，因为需要有大量的三角形保留连接信息。 h o p p e 【5 谰述了通过一种网格能量的思想，每次选取网格能量最小的边进行简化， 生成一种渐进模型。如下公式： 甜氅算舻 北京工业大学工学硕士学位论文 其中吖表示生成的基模型，m o 表示原始网格。h o p p e 的网格能量方程： 三= 如e 硒+ 其中，e 。( 肘) 表示距离能量，( m ) 表示对网格顶点数目减少的代价， e 鲫。( m ) 表示网格每条边加上的一个弹性系数的代价a 2 1 6 顶点去除法 顶点去除法是一种马赛克化的方法，虽早由s c h r o e d d 7 1 等人提出，在马赛克 化过程中，从模型中选择一个顶点，将其去除并且去除与顶点相关联的所有面， 对由此引起空洞进行重新三角化，如图2 - 2 。 秒意眵 bej!b健alb叮 图2 2 马赛克化方法示意图 f 培2 2p o l y g o nd e c 曲a 曲n 在马赛克化的过程中需要把表面的局部投射到一个平面上，所以这种方法仅仅局 限于拓扑结构是流形的模型，顶点去除法不会改变模型的拓扑结构，这种方法的 有很好的时间效率与空间效率，但是对于保留曲面平滑性上就大打折扣。 2 1 7 点对收缩方法 这种方法基于点对的迭代收缩来简化模型，虽然之前的一些算法提出了面收 缩方法8 】【9 】【10 】【1 ，但仍可以归结到此类方法，因为一个面的收缩可以通过点对收 缩的方法来间接达到，只要收缩一个三角形的两个边就可以达到面收缩效果，两 者差别很小。点对收缩，( m ，v ，) j 可，通过三步来改变曲面： 第l 步：把顶点v ，v ；移动到新的位置矿； 第2 步：把所有与v ，的元素关联到v ，； 第3 步：把v ；删除，与此关联的所有面就退化，从模型中删除。 第2 章巨型网格简化基本理论 第l 步中更改模型的几何结构；第2 步中更改网格的连接信息；在没有明确指明 需要保留拓扑结构的前提下，表面的拓扑结构会被简化；第3 步则从模型中去除 掉已经不需要的信息。 当一条边收缩时，它的两个端点被一个顶点所替代，退化为边的三角形被删 除，如图2 3 。 函 b e 奴e a 最e r 图2 - 3 边收缩不意图 f i g 2 3 ：n e xp a i r sc o n 衄c t i o n 边收缩的思想并不需要点的相邻元素必须是拓扑流形的，这点上它比顶点去除方 法适用性要广得多。 广泛意义上的点对v ，v i 并不一定是一条边。对一条非边点对进行收缩的操 作可能会将互不关联的区域结合在一起。通过点对收缩来执行拓扑简化的算法可 以支持非流形拓扑结构的表面，当两个分离的部分被结合在一起的时候，一个非 流形区域( n o n - m 姐i f 0 1 d ) 就会产生。如图2 - 4 。 i 穸一一 b 醯玎e n 挣疆删 - _ _ 图2 4 非边点对收缩改变拓扑结构示意图 f i g 2 _ 41 b p 0 1 0 9 yc h a n g e so f n o v e r t e xp a i rc o n s t r a c t i o n 为了执行点对收缩( v ；，y i ) 哼哥，必须选择目标点虿。最简单的策略就是选择点对 中的任何一个端点作为目标顶点，也可选择最优策略，计算最优目标顶点，这样 会生成更好的模型，但是需要更多的空间来存储多分辨率模型。 大部分的点对收缩都是基于一种贪心策略来确定点对简化的顺序，每一个点 对收缩都会有一个代价，每次简化代价最小的点对，点对代价可以有很多种不同 的计算方法，一般情况下通过计算点对收缩后的误差作为点对收缩的代价。 北京工业大学工学硕士学位论文 2 2 简化误差控制方法 简化的主要目的就是能够生成一个近似模型，这个模型同原始模型尽可能的 接近。为了能量化确定近似度，我们就需要量化相似度的评价方法。一个给定的 多边形模型m 和一个近似模型m ，我们确定一个误差矩阵e ( m ，m ) 来度量 近似误差。 一般情况下，大部分采用的相似度测量标准会因应用的不同而不同，绘制 系统会比较偏向于表面相似度，而简化系统则比较偏爱于几何相似度。 2 2 1 模型几何近似误差评价 绘制系统中的模型的相似完全表现于表面属性相似程度。本文中关于误差的 论述完全指的是几何误差，因为几何误差评价是一种比较容易的手段，有非常精 确的数学表示，另外几何的相似性也是视觉相似性的最重要的一方面。 2 2 - 1 1 函数近似表示 函数的近似表示是数学上一个重要的问题，给多边形模型的近似表示以启 发。给定一个实值函数，( f ) 和它的近似函数g ( f ) ，它们的定义域是【a ，6 a 三。范 数定义如下： i i ，一g 忆= 罢纠，( f ) 一g 酬 其定义了原函数与近似函数之间的最大变化值。 三：范数定义如下： l i 厂一g i i ：= r ( 邝) 一g ( f ) ) 2 出 其定义了原函数与近似函数之间的平均变化。 在定义域内，我们叫g ( f ) 是最优的近似函数时，当且仅当，不存在另外的近 似函数g ( f ) 满足： l i 厂一9 0 。 1 1 厂一9 1 | 。 三。能够作为原始函数与近似函数之间距离的全局绝对约束，上。范式可以作为一 种性质保证机制，但他一个非常大的缺点就是他对原始模型中的“噪音”非常敏 第2 章巨型网格简化基本理论 感。相对而言，厶范数应用更加广泛，更好表示函数的整体相似性，但是可能 会抵消掉一些局部的扭曲。 2 2 1 2 表面模型近似评价 我们可以定义基于表面模型的三：范数与k 范数。我们基于值域的垂直距离 i ，( r ) 一g ( f ) j 来测量原始函数与近似函数的相似性，相对于一般的表面模型来说， 没有特定的方向来计算距离，通常采用的一种方法是通过原始模型与近似模型中 最近点对的距离来定义距离。从点v 到模型m 距离通过从点v 到点w 的距离来表 示，其中，w 表示模型m 中到点v 距离最近的点，最近距离如下表示： 巩) 2 删l v 一卅j 其中，表示欧拉距离算子。 一个比较常用的几何误差测量距离是汉斯道夫( h a u s d o r f f ) 距离，其按照工。 范式来定义，如下定义： e 一( m ，m ：) = m a 号搿d v ( m z ) ，? 孥d v ( m - ) ) 汉斯道夫( h a u s d o 册) 测量两个模型之问的最大扭曲度。如果e 。( m ，m 。) 占， 每个顶点与其近似顶点的距离都在占范围内，原模型的每个点也在近似模型表面 的f 范围内。同样依据上：范式来定义汉斯道夫( h a u s d o r 舯距离： 似，m ：) = 去毗似：) + 去。：( m 。) 其中，w 1 ，w 2 分别指模型m 。，m ：的表面积。在计算e 一和占名时，必须平等 对待模型m ，：，不仅要考虑m 。上每个点到m ：上距离最近的点，也必须同 样考虑m ，上每个点到模型m ，的距离最近的点。 在实际中完全依照公式精确计算误差矩阵的代价是非常昂贵的，通常分别对 模型m 。，肘：表面的点集合x 。，z ：按照某一个距离d 作均匀采样，以采样点来 计算e 一，e 0 。当采样距离d ，趋于零，点集合五，x ：就会覆盖模型m 。，m ： 的所有顶点。 一些简化算法应用e 一，也。的思想来确定近似模型的重建。h o p p e 吲的能 量方程点0 就跟层一非常相似。 北京工业大学工学硕士学位论文 为了进一步的减少计算e 一，点k 的代价，其他的一些算法提出了距离函数 z ，的局部版本。按照d ，( m ) 的定义，需要计算点v 到整个模型的最近点。我们把 距离函数的计算限制在模型m 的一个局部范围r 内，定义局部距离d 。( r ) 。很多 表面简化算法就是对于原始模型某一个区域内的一点v ，计算其近似模型上点邻 域内的一个对应点，作为点到其对应区域的距离，确定局部简化的误差。 2 2 2 误差控制方法综述 h o p p e 【5 1 采用能量方程的思想来构建渐进网格，算法的主要部分是几何误差 的计算跟e 。计算非常相似。算法中在原始模型和近似模型都设定一个采样点集 合，这些点与其在原始模型中对应点的距离就是其几何误差。这个算法可以生成 很高质量的网格，但是代价是运行时间过长。h 9 p p e 【1 2 】中提出的方法网格优化思 想是渐进网格构建算法的早期形式，是基于全局搜索的，能够产生更高质量的网 格，同样其花费的时间会更长。 g u e z i e c 【1 3 1 提出的算法基本思想就是在近似模型周围设定一个约束体 ( t 0 i e f a n c ev 0 1 u n l e ) ，而在简化过程中保证原始网格在这个约束体内部。通过在 近似模型的每个顶点周围定义一个圆球，这些圆球所围绕区域的并集覆盖了模型 表面创建了一个所谓的“胖三角形”，即为了约束体，近似模型的顶点集被约束 于约束体内部。这种算法会比较慢，但相对于h o p p e 的算法来说，速度还是比 较快的，并且其效果也比较好。 r d n 觚和r o s s i g n a c 【1 4 1 算法中，每个顶点都关联于一个平面集合，这个顶点 的误差被定义为该顶点到这个平面集合中平方距离的最大值。当点对收缩时对应 的平面集合合并。 g 盯1 a i l d 和h e c k b e n 8 j 【9 1 提出的基于二次误差矩阵算法也是基于点到平面的 几何距离来定义误差。但是它使用了更精确地表示方法。每个顶点都被赋予一个 4 4 矩阵，这个矩阵能够测量点到集合中所有平面的距离之和。在合适条件下， 一个平滑曲面二次误差矩阵的特征向量和特征值可以由曲面的主曲率和主方向 来确定。二次误差矩阵方法在确保近似误差的情况下能够满足一定的精度，并且 其运行效率非常高。 l i n s 咖m 和t l h 醛1 5 】提出的一种节约内存的算法，完全以当前近似模型为标 第2 章巨型网格简化摹本理论 准，不保留初始模型的任何信息，在选择候选点对以及选择点对候选点位置时， 它使用了一种基于体积保持的线性约束方法，事实上，采用的体积优化的部分与 二次误差矩阵非常相似。实验结果也能表明这种方法效果非常好，特别在内存消 耗上，效率非常高。 2 3 核外模型表面简化技术 以上讨论的所有的简化策略和误差评价方法都是基于核内模型的。虽然基于 核内模型简化算法的主要处理对象就是复杂模型，然而从目前的情况来看，对真 正数据量足够大的情形核外模型，传统简化算法本身已经不太符合实际。但是 传统简化策略和误差评价方法则是核外模型简化算法的基础。因为传统的核内模 型简化技术需要把整个完整的网格存储在主存中，而核外模型的数据量远远大于 内存可处理量，为了解决这个问题提出了很多的基于核外模型的简化算法。核外 模型简化算法的主要手段就是对模型作处理，通过某种方式使之可以在内存处 理。核外模型简化算法既可以产生一个近似模型，也可生成核外模型的多分辨率 表示。 当前所存在的针对核外模型的表面简化算法比较少，主要原因是之前的核内 简化算法并不适合于在核外的方式。当前大部分的核内简化算法主要就是迭代的 执行一系列的网格局部粗化操作，比如2 1 节讲的马赛克化方法 9 】顶点去除方法 1 2 4 】，点对收缩剐方法等，操作的执行顺序主要取决于简化引起与原始网格的误 差，比如通过一定的误差评价方法来测量近似网格与原始网格的距离，不断的进 行误差最小的操作。典型的误差测量则基于2 - 2 节方法来量化网格到网格距离， 局部曲率等。为了调整误差矩阵，必须对每一次粗化操作中消失的几何图元做跟 踪，必须根据其中每个几何图元的连接信息以及其周围的几何结构来作调整。因 此，核内方法需要明确的数据结构来表示模型元素的连接关系，粗化操作的优先 级序列。对于n 大小的网格，则需要d ( n ) 个存储单元，所以核内算法对模型的 大小有很明确的限制。简单的虚拟内存技术并不是一个可行的选择，简化过程的 局部性不好导致对网格访问的非常零散，从而引起过多的内外存数据传递。然而 从可用的核外简化算法来看，在付出一定代价的条件下，随机的存取可以避免。 如2 1 所述，有很多种表面简化的方法，对三角形网格中比较流行的操作有 第2 章巨型嗣格简化基本理论 图2 - 52 维空间分区简化图示 f 噜2 5s p 撕a ls e g m 锄s i m p l i f i c 撕o n i n2 - d 印a c e r d s s i 船a c 和b 删【4 0 l 的核内算法就是使用了类似的网格，尽管如此，此算法中 所使用的矩阵完全依赖于网格的完整的连接信息。另外，还需要一个层级结构来 表示一个簇中最重要的顶点，这种方法并不适合于核外模型。然而r d s s i 辨a c 和 b o h - e 1 比较原始的分区算法却为许多核外模型算法提供了基础。 2 3 1 1 固定空间分簇技术 为了把r o s s i 盟a c 和b o r r e l 的技术扩展到核外领域，l i n d s 响m 【3 5 】提出了使用 g 础a n d 的二次误差矩阵阎【9 1 来测量误差。l i n d s 仃0 m 的方法被称为基于核外的简 化( o o c s ) 。首先扫描外存的三角形网格，计算每个三角形的误差矩阵。使用一 个主存中的稀疏栅格，三角形的三个顶点连带其对应的误差矩阵被分配于相应的 栅格内。对于每一个顶点，无论它是属于一个三角形还是更多簇，其对应的误差 矩阵都被赋到栅格中，只有分别属于不同的簇的三角形才能够保留下来，剩余的 三角形都收敛而不能输出。在每一个三角形都被读入之后，输出一个简化后三角 形歹u 表，每一个栅格内二次误差矩阵列表。每个顶点相应二次矩阵，通过计算最 小误差得到最优的点位置，从而输出一个网格输出。 l 洒d s 仃d m 的算法时间效率等同于输入网格的大小，在理论上和实际中都很 有效的，在普通的p c 机上处理速度可以达到2 5 ，o o o 三角形每秒。虽然他的算 法可以简化任意大的网格，但他却需要主存来存储所有简化后三角网格，因此在 北京工业大学工学碗士学位论文 输出的网格上有一个很大的限制。为了突破这种限制，“n d s 乜d m 和s i l v a 3 4 1 提出 一种o o c s 算法的扩展版，在外存上进行所有的计算，仅仅需要常量的内存。用 对外存连续访问栅格来代替内存的随机访问，把所有与栅格有关的信息全部存放 于外存上，基本的处理方式为首先把所有的顶点都映射到相应的栅格，然后把每 个簇中二次误差写入外，接下来通过对栅格进行快速外存排序，之后遍历排序文 件，二次误差被累加，从而得出最优的顶点坐标。最后，对输出三角形列表进行 三次顺序扫描和替换，每一次都包含一个外存排序，用定点序列的中的索引来代 替簇标示符。 由于使用了空间分区和二次误差，i j n d s 昀m 【3 4 】并没有使用网格连接信息。 尽管如此，在使用同一种分区策略下，最终的结果同g d a n d 【8 】算法结果相同。 但是网格的拓扑特点，比如表面边界，尖锐边等，都没有考虑。为了更正这一点， l i n d s 虹d m 和s i l v a 3 5 】中提议同时计算切线和法线误差，切线误差不考虑平面区域 的边，但对尖锐边和边界进行惩罚。结果，边界，尖锐边就可以被保留，但同时 却不用明确计算连接信息。 2 3 1 2 自适应的空间分簇技术 之前讨论的空间分簇算法并不一定要求是直线分区。事实上，网格三维空间 分区不一定统一，就分区单位格来讲，也并不一定需要凸包。因为网格的细节往 往随着表面变化，因此，非常必要把单位格按照表面形状进行调整，使用大量的 细致格来划分表面的细节信息，较粗的格来划分较为平滑的区域。s h a 妇f e r 和 g a r l a l l d 【4 1 】首先阐明了自适应分区的好处。这种方法使用两种途径输入网格，第 一种途径相似于o c c s 算法【3 8 1 ，但是其中每一个固定格既有到面的距离的累加， 又有到点距离的累加。对这些二 诖嘶暇涂梢圆捎 基于面片的网格简化方法。 基于面片的网格简化方法主要包括两个方面，一、从局部上看，如何简化单 个面片以及如何保证与其他面片的连续性；二、从全登算筒麴i 薹蔬囊囊鬻鞠猫 懑滗博本i 酬鞴引彭翠嚣影囊行；舷鞭鞋抹毖糍鼷矍；雾裂蒋蕊藉茧姜i擎备戮骝受蚕缝磁明鞭列翟塑!娄燮羹翁粥黼攀匹羹甄 彦! 刊剽墅羹在需要高解析度酊格? 叫 格。但是这部分内存开销是 第2 章巨型网格简化基本理论 已经被g d a n d 和s h a 丘甜”1 提出来了。 固定分区策略对格平移和旋转等变化非常敏感，在输出粗略的网格上经常会 有走样的现象。受在图像处理和数字信号处理领域工作的启发，f e i 【3 8 】提出用两 个相互交叉的格，在各个方向进行一半格平移，来避免走样。他指出表面的细节 区域对空间网格的平移相对敏感。通过在这两个相互交叉的空间网格上面进行分 簇操作，从而得到两个二次误差矩阵，通过比较两类输出网格的相似性来预测其 细节。相对以上的算法，这种自适应算法住往需要对网输入网格做一次处理。 2 3 1 2 表面分割技术 空间分簇技术主要基于对表面所在空间进行分区。另外一方面，表面分割技 术则侧重于划分表面本身自己，使每一个节点可以在核内中处理。这样每一个面 片就可以在一定误差条件下，通过一种高质量的简化算法在主存中进行简化。从 点集分区的角度来看，表面分区把顶点集合粗略的分为一些较小集合，这些集合 最后在主存中简化。表面分割可以是固定的，也可以是自适应的。 2 3 2 1 固定表面分割技术 h o p p e 【1 7 】首先在高度域网格上核外表面分割技术。他的方法将将高度域网格 映射到二维平面，而后做二维分割，如图2 6 ，将其分割为一些矩形块，在内存中 在误差允许的前提下对每一块进行简化。相关联的块按照层级进行组织形成一个 更大的块，其中，对块边界不可以进行任何调整，这个过程进行一种简化。2 0 0 0 年p r i n c e 【3 观对h o p p e l l7 】的方法作进一步的改进，使用了三维固定的空间格来对空 间进行分区，对表面进行分割。这两种方法都有一个好处：可以产生一种非静态 约化，这种表示方法用渐进网格【5 】表示，支持自适应细化和视点相关绘制。他 通过一种误差驱动的边折叠操作，精度较好，但是速度较慢，需要更多的内存。 第3 章基于改进八叉树模型的巨型网格简化方法 第3 章基于改进八叉树模型的巨型网格简化方法 3 1 概述 如第2 章所述，基于八叉树的空间分割方法来对模型进行分片可以很快的达 到分片的目的，但是针对表面模型，基于空间的分割方法会造成如下的问题： 1 、各个叶子节点内的数据量极不均衡，有些叶子节点仅仅包含一个顶点： 2 、某些叶子节点内可能包含多个独立的面片。 本章主要针对以上的问题，改进了基于八叉树的简化方法，该方法的基本特 点是在八叉树创建阶段，建立叶子之间的共享多边形结构；在共享多边形结构的 基础上，对叶子节点做合并处理，确保每个叶子节点只有一个独立面片；按照一 定的阈值进行合并，保证所有叶子节点的数据量某个阈值之上，从而保证叶子节 点数据量均衡。 在此改进型的基于八叉树的结构上进行简化，充分利用每个叶子节点内部只 有一个面片，确定了基于叶子节点面片的简化方法，将叶子节点面片作为模型的 简化单位，主要阐述了基于单位面片的误差评价方法边收缩最大代价，单位面 片的简化“步长”算子基于面片的多边形数目简化步长评价方法。 3 2 传统的八叉树分片简化方法分析 在处理存储于外存上的模型一核外模型时，主要的技术瓶颈是：一、存储于 外存上的数据模型巨大，但内外存i ，o 效率低下【4 2 】；二、模型数据量巨大但简化 方法却要求参照整个模型的全局信息，需要巨大的内存开销和时间开销。 传统的基于八叉树的块分割方法分割效率较高，通过分割方法实现对巨型模 型的分治，极大的提高了i o 效率，但是分割方法引起的叶子节点数据不均衡， 使叶子节点数据的检索效率有待提高。在简化过程中，需要专门的数据结构和算 法来记录所有节点的简化代价，内存开销较大。 北京工业大学工学硕士学位论文 3 2 1 简化代价和多边形位置的关系 模型简化操作的代价同简化操作所发生的位置是相关的，相邻近区域的简化 代价是相近的。网格优化基本目标就是产生网格的最优表示，即，在某个误差约 束下，使用最小的多边形数目表示模型。就网格局部来讲，多边形数日随着曲率 的变化而变化，高曲率的部分，需要较多的多边形表示曲面曲率变化，则简化中 的代价就比较高：低曲率的部分，曲率变化较小，需要的多边形数目较少，简化 代价比较低。从简化代价的数学表示，也可以得出同样的结论。根据2 2 节所叙 述，两个模型m 。，m ：之间的距离，是基于汉斯道夫( h 孤l s d o 仃) 距离来评价： e 。c m 。，m ：) = 去嘶( m z ) + 亡j ：，。：影( m - ) ( 3 - 1 ) 其中，彩( m ) 表示点v 到模型m 距离，从点v 到模型m 距离定义如下： d ，) = 删1 1 ，一训 ( 3 2 ) 其中，i h | 表示欧拉距离算子，w 表示模型m 中到点v 距离最近的点。就模型的局 部来讲，某点v 的简化代价，跟点v 所处位置的曲率有很大的关系。假设简化前， v 对应的最近点w ，v 被简化为v ，v 对应的最近点是w t ，按照式( 3 2 ) ，简化 代价就是： c = 1 1 v 一叫l i l v 一w 1 i ( 3 - 3 ) 当v 处于高曲率区域，由于瞌面变化比较剧烈，当v 的位置发生很小的变化，就 可能造成v 所对应最近点w 。的位置发生很大的变化，则根据3 - 3 式，简化代价c 就 比较高。由此，我们知道，在曲面曲率比较高的位置，简化代价往往比较高，需 要的多边形数目也就比较多，反之亦然。由于曲面表面瞳率变化的连续性，邻近 区域的简化代价也是相近的。 基于八叉树的分割方法很好利用了简化代价和面片位置的相关性，对模型所 占的空间进行固定的分割，保证某个分割区域内的多边形在位置上相近，但是并 不能保证分割区域内的多边形式相连通的。即，某个区域内保含多个离散的面片。 在某种情况下，某些部分会被分割成几个断裂的区域，这种情况会造成一个节点 内的简化代价变化很大。当某个节点内的简化代价变化很大时，在简化过程中， 会造成简化节点的效率不高，当某个节点内两次的简化代价相差很大，而其他节 点内部有简化代价更小的顶点，按照简化代价最小者被简化8 1 的原则，必须去加 第3 章基于改进八叉树模型的巨型阿 吾简化方法 载其他节点面片进入内存，增加了内外i o 次数。另外，从面片误差评价的角度 来看，基于八叉树结构的网格简化方法中，某个叶子节点是否被处理和简化，取 决于该叶子节点的简化代价大小，而当一个叶子节点内部包含多个离散面片时， 因为简化代价跟位置是相关的，多个离散面片是处于不同区域的，则节点的简化 代价评价就会变得非常难，且不准确，造成面片简化代价评价误差增大，简化效 果降低。 所以，从多边形位置与简化代价的关系来看，传统的基于八叉树的分割方法 会造成某个节点内部含有多个面片，造成简化效率降低，简化代价评价误差增大。 为了解决这个问题，我们必须专门对叶子节点内部包含多个面片的情况作专门处 理。对传统的八叉树方法作专门的处理，当某叶子节点内部包含多个离散面片时， 就将其中较小的面片分配合适的叶子节点。寻找合适的合并叶子节点的原则是基 于最大相关原则 2 0 】，跟当前节点内待分配的面片有最大的关联的面片。 3 2 2 基于传统的八叉树分片方法i ，o 效率分析 传统的基于八叉树分片方法的思想是用空间分割的方法分割曲面，会引起分 割面片大小不均，降低i o 效率。如第2 章论述，从内外存i ，o 次数和算法复杂 度上来讲，空间分割方法是一种效率较高的分片方法。基于八叉树的空间分割方 法，它采用的是一种分治的思想，将模型分割很多小模型，每次处理一个小模型， 最后达到处理大模型的目的。分割思想是按照空间分割，同一块空间区域内的多 边形处于同一个叶子节点内。这种分割方法不仅可以提供一种外存数据模型的索 引方式，对模型简化来说，可以大大提高简化效率，根据3 2 1 节叙述，相互连 通的多边形地简化代价相近的概率比较大，这样的某个时间内，简化操作发生一 个叶子节点内部概率增大，因为同节点内简化跃迁较大而引起的内外存大大 减少，提高了“o 效率。但是八叉树分割方法是一种基于空间的分割方法，它对 表面模型所包围的空间进行分割，分割对象是网格所表示空间中的一个曲面。由 于网格表面的所占空间分布的随机性，会造成有些节点内部包围较多的多边形， 而有些节点内部仅仅包含一个点；大部分的叶子节点则是空节点，不包含一个多 边形或者网格元素。如下图3 1 所示： 她裒王业大学王学颈士学霞论文 图3 一i 节点网格不均衡乐慈图 残誊3 - ln 黼啦正驴e 搬鼬遮斑el 髓谨s 藏疆髂 税简化过程中，会造成简化某些较小面片所花的时间甚至小于内存工，o 的时间， 褥显峦予嚣片多逑形数瓣不臻匀，本身虢会遥簸一些鬏终煞痰帮糟次数。 改进传统的糖于八叉树分割方法的内外哟效率的方法，就是合并较小面片， 傻面片数匿眈较均匀。 3 2 3 墓子分截面片的耀格筒仡分析 墓予，叉瓣分裁方浚将匿黧模童分餐残一个令枣露片，逶遭篱纯每一令夸覆 片，最殿达到简化整个模型的目的。但是分割眉的面片毕竟是模型的一部分，栈 简化过稔中，必须保证黼模登其他部分的连续。 保诞面片之