构建可视化的多分辨率三角形不规则网络模型外文翻译资料

 2022-04-26 22:47:04

英语原文共 10 页，剩余内容已隐藏，支付完成后下载完整资料

构建可视化的多分辨率三角形不规则网络模型

杨碧生[1]，李清泉[2]，史文忠[3]

  1. 苏黎世大学Irchel分校地理系GIS部门，190，CH-8057瑞士苏黎世
  2. 武汉大学测绘遥感信息工程，国家重点实验室，武汉
  3. 香港理工大学, 土地测量和地理信息学系，空间信息技术高级研究中心，香港

摘要

动态有效地生成多分辨率不规则三角网模型的重要性表现在可以解决三维可视化、虚拟现实、地理信息系统技术在数据上处理繁琐、数量巨大的问题。本文提出了一种新动态生成多分辨率三角网的方法，它扩展了迭代边缘塌陷和顶点分裂算法。并且，本文提出了一种全新高效的方法以提高在多分辨率三角网中存储顶点拓扑关系的效率，它还定义了一套用于判断顶点分割和边缘塌陷合理性的规则。为了评估这种方法的性能，测量顶点高程的平方根误差（RMSE）和评估三角形形状的质量，来评估生成的多分辨率三角网模型。实验结果表明，该方法生成的多分辨率三角网模型具有更高的准确性和更好的时间表达。

2004 Elsevier有限公司保留所有权力。

关键字：TIN; 三维可视化;多分辨率/边缘塌陷

1 绪论

不规则三角网（TIN）是一种通用的表面模型，因其具有简单的数据结构和可以被常用图形硬件渲染的特性而广泛的应用于地理信息系统，计算机图形的虚拟现实技术中。为了表达模型的细节，一种高分辨率的TIN模型（具有密集三角网络）应用颇广。虽然如此，高分辨率的TIN模型的表达任然需要处理大量的数据，并且在计算时需要耗费大量的时间。另一方面，尽管低分辨率的模型表达可以减少计算的数据量，但是模型的细节将会丢失。因此，可以根据要求选择不同层次下不同模型细节的可变分辨率的TIN模型来解决这个问题。多分辨率TIN模型是集3D压缩，地形可视化，多分辨率分析和渐进传输等方面的一个重要研究领域。它已经被许多学者研究过（DeFloriani，1989; Mallat，1989; Eck et al，。1995; DeFloriani等，1996,2000; Lindstrom等，1996; 霍普，1996年，1998年）。许多复杂的算法和模型都被开发出来用来构建多分辨率TIN模型。例如，层次三角法，三角抽取法，迭代边缘崩溃和顶点算法。

迭代边缘折叠和顶点分割算法的优势在于它建立的层次结构。虽然如此，但是如何在多分辨率TIN模型中高效的存储顶点拓扑关系仍是算法中亟待解决的关键问题。顶点拓扑关系的存储对可视化速度和数据存储上有很大的影响。此外，它也是判断边缘崩溃的合法性的一个先决条件。夏等人提出了明确存储顶点拓扑关系的方法，EI-Sana和Varshney则通过一种隐式的方法来提高数据存储方式。事实上，这种方法有一种非必需的局限性阻止了原始模型的进一步简化。除了顶点拓扑关系的存储，另外一个重要的问题是多分辨率TIN模型的质量。这里的质量由模型的平方根误差，有效的拓扑关系和多分辨率TIN模型中的三角形形状共同决定。尽管如此，多分辨率TIN模型的质量问题在现有的研究中也常常被忽略。本文提出的方法旨在拓展迭代边缘塌陷和顶点分割算法，它采用一种新的编码方式提高了顶点拓扑关系在多分辨率TIN模型中的存储效率，并且通过定义两条新的规则来判断边缘崩溃和顶点分割的有效性。本本文所提方法的核心在于为多分辨率TIN模型提出了一种有效的可以动态存储顶点拓扑关系的算法，

本文的剩余部分安排如下：第二部分提出了所提方法的原理，边缘崩溃和顶点分割的有效性判断规则以及顶点拓扑关系的编码方式和存储方法；第三部分表明了实施的步骤；第四部分说明实验结果；第五部分得出了实验结论。

2 建议方法的原则

本文所提出的方法是基于图1所示的迭代边缘塌陷和顶点分割算法。根据迭代边缘塌陷和顶点分割算法的原理，将解决四个关键问题来得出多分辨率TIN的有效解决方案模型的生成。分别为：（a）选择候选边缘崩溃; （b）判断边缘崩溃和顶点分裂的有效性; （c）对顶点拓扑关系进行存储和编码;（d）评估模型的质量。上述四个问题中，前三个问题是关于多分辨率模型的拓扑效度以及该模型本身的构建。第四个问题是关于多分辨率TIN模型的质量问题。在构建多分辨率TIN模型时，边缘崩溃和顶点分裂的操作会一直发生。它们会影响操作是否可以根据多分辨率模型中的三角形数量或所指示模型的质量进行

图1 边缘崩溃和顶点分割的示意图

通过海拔的RMSE或模型中海拔的最大误差。构建多分辨率TIN模型的过程如下。在这里，我们假设是原始模型:

从到的过程是边倒塌的过程，也是顶点拆分的过程。显然，在每一步的操作中，边缘塌陷或顶点分裂的操作都将发生。一个边缘崩溃分的操作分为两个步骤：第一步是选择候选边; 第二步是判断手术的有效性。边缘折叠或顶点分割的有效性是避免三角形折叠的前提条件，但这可能导致多分辨率TIN模型中的无效拓扑。

2.1候选边缘选择

很多方法已经被提出用于选择候选边缘的倒塌，例如：二次度量误差方法（Garland and Heckbert，1997），最小能量方法（Hoppe，1996）以及到平均平面的距离的方法。（图 2）（Schroeder等，1992）。二次度量误差和最小能量方法考虑了TIN模型的全局精度。虽然这些方法可以获得更高的图形质量， 但是，这些方法的速度性能相对较低，需要大量数据。 最小能量方法实现起来也有些困难（Lindstrom and Pas-cucci，2002），而到平均飞机的距离的方法更容易实现，且这种方法占用较少的存储空间。

图2 平均面的距离计算

根据到平均平面的距离的方法选择候选边缘。根据Schroeder等人提出的方法可以很容易地构建平均飞机。（1992），并且距离可以通过公式从点到飞机计算。对于一个边，假设和是顶点和到平均平面的距离，而不是到的距离; 的距离是到它的平均平面的一半。所以，所有的距离可以根据堆栈结构中存储的距离值对其平均平面的边缘进行排序。与平均平面距离最小的边缘将首先从堆栈中弹出以便潜在崩溃。虽然基于平均距离的方法的标准是可行的，但额外的标准被添加来控制模型的质量。在图2中，红色边缘由两个三角形共享。假设两个三角形的法线是和,那么两个三角形之间的角度可以通过以下公式计算出来:

两个三角形之间的角度可以作为在构建多分辨率TIN的过程中选择候选边的附加标准模型。例如,可以将设置为阈值。如果角度超出阈值,则所选候选边缘对于边缘塌陷无效。这个标准对于保持原始模型中的诸如脊线等地貌特征的特征线很有用。

当边缘折叠或顶点分割时，它必须符合某些规则。否则，多分辨率TIN模型中可能会出现无效拓扑（三角折叠）。 图3 B表示出了一个情况。因此，需要定义边折叠或顶点分割的有效性判断规则，以避免多分辨率TIN模型中的无效拓扑。

图3 一个无效的边缘倒塌操作的例子

2.2边缘折叠和顶点分割的规则

夏等人（1997）提出了关于顶点拆分和边折叠的以下有效性规则：顶点c可以折叠到顶点p; 只有当顶点是作为p和c的邻居呈现。 但是，规则的严格性需要进一步调查。 如图3A所示，顶点邻域关系符合上述规则。但是，当顶点c折叠到顶点p时，三角形折叠仍然是不可避免的（图3B）。

提出的新规则克服了现有规则的不足，避免了三角折叠问题。 为了清楚地呈现新规则，我们首先定义了以下概念。

·顶点的相邻顶点：这被定义为一个顶点集合，其中每个顶点集合和顶点由TIN模型中的一条边组成（图4A）。

·顶点的相邻三角形：这被定义为一个三角形集合（1,2，···，6），其中集合中的所有三角形都有一个公共顶点p（图4A）。

·影响顶点的区域：这被定义为使用顶点的所有相邻三角形（多边形）构建的多边形（图4B）。

图4 A三角判断 B 影响范围

基于上述概念，定义以下规则来检查顶点分割或边缘塌陷的有效性。

规则1.只有当顶点的影响区域是凸多边形时，顶点才能折叠成顶点;

规则2.只有当顶点的崩溃操作出现在顶点的影响区域的顶点之前时，才能安全地分割顶点;

新的规则是严格的，可以用来防止三角折叠。

规则1的证明：我们假设顶点的相邻顶点集合为; 并且顶点在该顶点集内。根据边缘凸起的原理，通过将顶点连接到顶点集合中的其他顶点来生成新边缘。 因为由顶点集组成的多边形是一个凸多边形，所以新边与这个多边形中的其他边不相交。因此，它是一个安全的方式来崩溃边缘。

规则2的证明。假设顶点的相邻顶点（例如:）被折叠，并且顶点的折叠操作发生在顶点之前：因为顶点和顶点相邻，所以必须发生顶点的分割操作 在顶点之前，以恢复顶点，边和三角形之间的原始拓扑关系。

通过规则1和2，建立了边缘崩溃和顶点分裂的严格数学基础。这些是避免多分辨率TIN模型中无效三角形的前提条件。如果这些条件未得到满足，则可能发生在可视化3D TIN模型中视觉上注意到的无效三角形。

由于在构建多分辨率TIN模型时边缘塌陷和顶点分裂的操作，当边缘塌陷或顶点分裂时，顶点，边缘和三角形之间的局部拓扑关系将改变。在这里，我们将拓扑关系明确地表述为顶点拓扑关系。为了保持多分辨率TIN模型的拓扑正确性，在运行时间内维护顶点拓扑关系是必要的。这是将多分辨率TIN模型从较低分辨率恢复到较高分辨率的先决条件。有效编码并且存储顶点拓扑关系对于一种方法的运行时间和数据存储量有重要影响（EI-Sana and Varshney，1999）。如果顶点拓扑关系显式存储，则需要大量数据量。为了存储和编码这些顶点拓扑关系的有效性，提出了顶点树和相应的编码方法。顶点树被用来存储顶点拓扑关系和编码方法是基于一般包围法（Donaghey，1980），它被证明是一个简洁的结构代表树木结构中的顶点拓扑关系（Park等人，2001）。

2.3 顶点树

图5图示了树结构的编码结果。基于一般的包围方法，图可以用一对嵌套的括号表示。左括号可以表示为0，右括号可以表示为1.树结构（包括顶点和连通性以及位置级别）可以分解为一组嵌套的括号。 可以从括号集中恢复树中顶点的连通性和位置级别。 树的编码结果由一组括号（比特流0和1）和重新排序的顶点组成。 因此，顶点的连通性可以用每个顶点2位来编码（Park et al。，2001）。

图5 顶点关系的编码方式

在运行时间期间连续发生顶点分割或边缘塌陷的操作。例如，当一个边被折叠时，将生成一个顶点（父）与由二叉树组成的两个子顶点（子）之间的关系。因此，由顶点分割和边缘塌陷操作生成的所有二叉树由顶点树组成。为了使用一般包围方法对顶点树之间的顶点关系进行编码和存储，插入虚拟顶点作为顶点树的根顶点。图6图示了顶点树的示例。基于一般包围法，顶点树可以由一组记录的顶点和一组括号（比特流为0和1）编码。括号集记录顶点树中记录的顶点之间的隐式连通性和级别。由于顶点树中的最小单位是一棵二叉树（一个有两个子对象的父亲），顶点遍历算法很容易用宽度优先遍历算法实现。可以通过遍历括号集来动态编码顶点树中顶点之间的连通性和级别。此外，通过选择顶点树中顶点的不同密度（图6中的A或B），可以调整原始模型的各种分辨率模型。

图6 顶点在顶点树中的位置

图7 算法中顶点树的生成

3 建议方法的实施

3.1 数据结构

数据结构对算法或模型的效率有很大的影响。根据上面提出的顶点树模型，提出了顶点，三角形和顶点树结构来满足所提出的方法的要求。以下伪代码算法说明了顶点，三角形和顶点树的数据结构。

与顶点树和顶点的数据结构相比，三角形的数据结构非常简单。 在顶点的数据结构中，顶点的相邻三角形和相邻顶点逆时针排列。 变量m_nLayerinTree是顶点树顶点的位置。 顶点树中根顶点的高度为零，变量m_dDistancetoAveragePlane是顶点到由其相邻顶点组成的平均平面的距离。 在这里，顶点树的数据结构是根据一般包围法开发的。顶点集和具有0和1的比特流是表示顶点之间连通性的基础。顶点，三角形和顶点树的数据结构形成了基础的建议方法。

3.2拟议的方法的伪代码算法

当边缘崩溃或顶点分裂时，会产生顶点拓扑关系，例如两个顶点合并成一个顶点或者一个顶点被分成两个顶点。 顶点和顶点的拓扑关系将被插入到顶点树中，并且它们将基于一般的包围方法进行编码。 下面给出基于一般括号方法构造顶点树的伪代码算法。

图8示出了在所提出的方法运行期间的时刻的中间编码结果。 当边缘崩溃或顶点分裂时，顶点树的平衡会改变。 顶点树中的每个顶点对应某个影响区域。 平衡良好的顶点树意味着在原始TIN模型中不同区域之间出现边缘塌陷和顶点分裂，并且这些区域的重叠在原始TIN模型内占据较小区域。 因此，顶点树的平衡与三角形的形状有关。 更好的平衡意味着在构建多分辨率TIN模型的过程中，产生细长三角形的机会较小。 为了在顶点树中保持合理的平衡，尽可能多的边应当在顶点树的每一层折叠。 结果，可以避免在小的局部区域连续崩溃。 这意味着产生细长三角形的机会非常低。

图8 边缘崩溃的产生以及顶点树中的顶点编码

4 实验研究和分析

所提出的方法在Windows XP操作系统平台上采用C 语言实现。选择一个总共87,152个三角形和44,003个转换点的区域进行案例研究，以评估所提出的方法的时间性能和多分辨率的质量 TIN模型。 该实验是在配置CPU奔腾IV 2.0GHz，RAM 256Mb的戴尔笔记本电脑中进行的。

根据所提出的方法构建了不同的分辨率模型。作为与简化模型相

全文共10363字，剩余内容已隐藏，支付完成后下载完整资料

资料编号：[13267]，资料为PDF文档或Word文档，PDF文档可免费转换为Word

原文和译文剩余内容已隐藏，您需要先支付 30元 才能查看原文和译文全部内容！立即支付

以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。

您可能感兴趣的文章