3、表面建模.ppt

1、第三堂课是关于数字高程模型曲面建模，首先是曲面建模的基本概念，其次是数字高程模型曲面建模方法，第三，三角剖分生成算法简介，第四，网格生成算法简介，第五，通过比较三角网和网格，用多少个点来描述一个曲面？这些点是规则分布还是随机分布？采样点位于局部最大值和最小值？采样的核心问题，表面建模的核心问题，根据有限的离散采样点，我们如何得到地形表面上任意位置的高程？物体的计算机表示是通过表面模拟建立的，表面模拟通常是多边形面片的集合。从离散点到连续曲面插值的基本依据是空间自相关，即所谓的地理第一定律：空间中的东西越近，它们之间的影响就越大。插值和数字高程模型建模可以使用一个或多个数学函数来描述表面。这种数

2、学函数通常被认为是插值函数。插值包括通过使用相邻点的某个“平均值”来估计未知点的高程的整个过程、插值、使用什么类型的曲面以及如何重建、曲面建模中的插值方法以及曲面建模的基本概念。数字高程模型是地形表面的“数学/数字模型”，它是根据不同的数据集用一个或多个“数学函数”表示的。数学函数通常被认为是插值。表示地形表面的各种处理被称为表面重建或表面建模，重建的表面是数字高程模型表面。因此：地形表面重建=DEM表面重建/表面生成，地形表面重建和插值的一般多项式函数，Z=f (x，y)，2。数字高程模型曲面建模方法中，多项式中每个项的曲面形状都有自己的特点。当一个特定的建模程序建立一个实际的曲面时，它通常

3、只使用几个函数，但不一定需要这个函数中的所有项，曲面重建的一般多项式。一般多项式中单项的曲面形状，平面z=A0，y，线性z=a1x，x，y，z，线性z=a2y，x，y，z，x，z，z，y，二次z=a3x2，2。数字高程模型曲面建模方法，根据建模过程中使用的基本几何单元，数字地形曲面的建模方法可以分为以下四类：基于点的建模方法、基于三角形的建模方法、基于网格的建模方法以及基于两种混合建模方法的组合。基于点的建模方法利用单点数据建立一个平面区域来表示点所在区域的表面，整个数字高程模型表面可以由一系列相邻但不连续的表面组成；这种方法简单，但很难确定相邻点的边界。理论上，这种方法只涉及独立的点，因此它

4、可以用来处理所有类型的数据。2.数字高程模型表面建模方法，2。数字高程模型曲面建模方法，三角形曲面建模使用三个点形成一个三角形平面；每个三角形可以用来表示三角形所覆盖的区域，整个数字高程模型表面可以由一系列相互连接的三角形组成。这种方法称为基于三角形的表面建模；三角曲面造型可以将正方形、矩形等任意形状分解成一系列三角形；基于三角形的表面建模可应用于所有数据结构，无论这些数据是通过选择性采样、混合采样、常规采样、剖面采样还是等高线法生成的；由于其灵活的形状和尺寸，三角形建模易于融合断裂线、生成线或任何其他数据；二是数字高程模型曲面建模方法，网格曲面建模规则网格四个相邻的点形成一个曲面，它可以是一

5、个线性曲面或由四个点拟合的曲面；整个数字高程模型由相互连接的正方形或矩形面片或拟合的光滑曲面表示。2.数字高程模型表面建模方法，2。数字高程模型曲面建模方法，网格曲面建模适用于网格采样和渐进式采样，尤其是基于正方形网格采样方法获得的数据；它适用于平坦地区的地形表达，但不适用于地形起伏较大、有大量断层和陡坡的情况，网格模型易于管理、计算、分析和可视化。数据冗余大；二是数字高程模型曲面建模方法，当有多种采样方法或多种数据类型时，混合曲面建模容易采用混合曲面建模；混合曲面建模通常是指网格建模和三角剖分建模的结合；然而，为了便于统一处理，混合建模通常转换为三角曲面；3.三角网生成算法介绍。不规则三角网

6、通过从不规则分布的数据点生成连续的三角形表面来接近地形表面。优点：地形表面可以用不同的分辨率来描述。三角网模型有三个基本要求：(1)三角网是唯一的；(2)争取三角形的最佳几何形状，每个三角形尽可能接近等边形。(3)确保最近的点形成三角形，即三角形边长之和最小。3.1生成三角网：从离散点进行Delaunay三角剖分，如何将散乱点集划分成不均匀的三角网格，即散乱点集的三角剖分，这是数值分析和图形处理中一项极其重要的预处理技术。关于德劳奈三角形，狄利克雷在1850年和沃罗诺伊在1908年首次讨论了空间离散点之间的关系；1934年德劳奈提出了沃罗诺伊图的对称图，即空间三角剖分；没有四点圆，每个面都是三

7、角形；每个三角形对应一个voronoi图顶点(外接圆中心)；每条边对应一个voronoi图边；每个节点对应一个voronoi图区域；德劳奈图的边界是一个凸壳。如果三角测量中所有边的长度之和最小，则对角线较短的三角测量是最佳选择。，Delaunay三角剖分的特点，以及最优三角剖分。劳森(1977)提出根据最大最小角度规则建立具有最佳局部几何的三角剖分：在由两个相邻三角形组成的凸四边形中，交换该四边形的两条对角线不会增加这两个三角形的六个内角之和的最小值。据此，劳森提出了局部最优化方法：交换凸四边形的对角线，得到具有最佳等角性质的三角形网。带约束的狄龙三角剖分，带约束的狄龙规则：只有当三角形的外切

8、圆不包含任何其他点并且其三个顶点相互可见时，三角形才是带约束的狄龙三角形；带约束的狄洛尼-劳森交换：由两个相邻三角形组成的凸四边形的局部最优对角线只有在满足带约束的狄洛尼规则时才被选择。三角剖分生成算法，分治算法；渐进插入算法；三角剖分增长算法，Delaunay三角剖分基本算法，首先将数据分成不相交的子集；在为每个子集建立三角网之后，子集被合并以生成最终的Diloni三角网；李和沙赫特(1980)；Dwyer(1987)提出了带约束的加工方法。分治算法，让数据集v包含n个数据点，它们的平面不互相重叠，那么：1 .按升序排列v，以便(xi，彝语)(xi 1，彝语1)，条件是：(xi=或xi 1和

9、伊一1)；2.把V分成两部分，VL和VR，大小相等。VL包含数据的前半部分，虚拟现实包含剩余的点；3.建立两部分数据的Delaunay三角剖分，并通过Lawson LOP进行优化。4.计算每一半数据的凸闭包，并搜索上下部分的公共切线(最终三角剖分的一部分)；5.从下面的公共切线开始，沿着相邻的边将两个三角网合并到最上面的公共切线，并在合并过程中同时对它们进行优化；6.重复上述2-5，直到三角测量建立。分治算法，分治算法，渐进插入算法，将未处理的点添加到现有的Delaunay三角剖分中，一次插入一个点，并重新定义Delaunay三角剖分。定义包含所有数据点的超级三角形的顶点，作为初始的Dilon

10、i三角形：从数据中取出点P，并将其添加到三角网中；搜索包含点p的三角形，将点p与三角形的三个顶点连接，形成三个三角形；利用劳森LOP从内向外优化整个三角网；重复上述过程，直到处理完所有点；删除包含一个或多个超级三角形顶点的所有三角形；基于矩形结构的基本算法是：矩形中有n个数据点，所有与矩形顶点重合的点都被删除(以矩形顶点为计算起点)；矩形被分成N1/2块或更小的矩形区域；对块中数据点进行排序；将添加到矩形的第一点与矩形的四个顶点连接，以形成初始三角网；将第二个点添加到现有的三角网，并将其与包含它的三角形顶点连接起来；从内向外优化整个三角测量；重复上述步骤，直到处理完所有点；三角形生长算法，算法

11、过程如下：取数据集中的任意一点，找到离该点最近的点，并将其连接为初始基线；在初始基线右侧用德劳奈法则搜索第三点；生成德劳奈三角形，并将该三角形的两条新边作为新的基线；重复前面的过程，直到处理完所有基线；该算法花费大量时间搜索满足要求的邻域点。为了减少搜索时间，许多学者提出了许多不同的方法，如将数据分成块并并行排列，用外切圆限制搜索范围等。三角形增长算法和径向扫描算法：寻找最接近数据重心的点作为起点；计算中心点和所有其他点之间的距离和方向；根据方向、距离等，以升序排列所有其他点。径向扫描数据点，连接中心点和径向点，连接相邻线段的任意两个连续端点，生成径向三角形直至数据边界；通过检查由一对相邻三角

12、形形成的四边形的两条对角线的长度，从外到内优化三角网。上述所有算法都没有考虑在三角网中加入外围约束边界时切割三角网的边界，因此这些算法对于带约束边界的三角网构造是不完整的。边界裁剪或多边形裁剪对于应避免在有限区域内进行轮廓插值的应用来说是必要和关键的。接下来给出了一个完整的算法，该算法可以同时处理平面点和约束，不仅可以构造三角网，还可以切割边界。凸包生成算法，完整的凸包插入算法，凸包插入算法包括以下步骤：将数据点分成NK块，即NK等边行和列段。这里k是每个块中的平均点数，默认值为4；(数据的初始划分)确定每个块的凸闭包(凸闭包的计算)；用狄洛尼法则建立了具有凸闭包的狄洛尼三角形网络。重复插入不

13、在凸闭包中的其他点，并更新现有的三角剖分(插入其他数据点)；重复插入新的约束线段并更新现有的三角测量(插入约束线段)；删除除内部外围边界或外部外围边界(外围边界裁剪)之外的所有三角形。1.数据的初始分割，加快了邻域点的搜索速度，提高了算法的效率；目前，分块方法广泛应用于Voronoi和Delaunay几何算法中；分块时一般采用二维空间的排序方法，一般采用递归排序方法。凸闭包的计算。平面点凸闭包的定义是包含这些平面点的最小凸多边形。计算块数据的凸闭包：搜索分别对应于xy，xy最大值和xy，xy最小值的两个点。这些点是凸闭包的顶点，并且总是位于数据集的四个角上，如右图所示(3-3-10(a)中的点

14、79、12和6)。这些点逆时针存储在循环链表中。在链表中的点I及其后的点j上调用递归子算法凸(I，j)，搜索线段IJ右侧凸闭包上的所有点。递归算法传送(I，j):检查数据块中IJ及其右侧线段上的所有点，计算到IJ的偏移最大的点k，给IJ的右侧点指定正偏移值，给IJ的左侧点指定负值。检查最大偏移值的符号：如果值为正，将K插入链表中I和j之间的位置，并继续调用凸函数(I，K)和凸函数(K，j)；如果值为0，并且K在I和J之间，在链表中的I和J之间插入K，并调用函数凸(I，K)和凸(K，J)；否则，停止调用凸函数，2。计算凸闭包，2。计算凸闭包，3。生成凸闭包三角剖分，假设凸闭包的顶点数为m，随机分

15、布点数为n(通常m远小于n)。将m个顶点逆时针排序，然后按照以下步骤建立凸闭包的Diloni三角剖分(图3311):建立一个空的基线链表，凸闭包的第一条边存储在这个链表中；使用迪罗尼定律，第一条基线左侧的第三个点被检测到。建立一个Diloni三角形，并将该三角形的所有(内)边添加到基线链表中。三角形的新边是这样确定的，即它从基线边的开始节点到第三点，然后从第三点到基线边的结束节点。更新拓扑数据结构中边和三角形之间的相邻拓扑关系。重复步骤2-4，生成Diloni三角测量，直到处理完所有基线。4.用于插入其他该三角网的搜索是通过三角形重心的块结构和保持边与三角形之间邻接的拓扑数据结构进行的。具体过

16、程是通过块结构搜索要选择的第一个三角形，然后通过拓扑数据结构向外分析该三角形的相邻三角形，以确定剩余的三角形。使用迪罗尼定律，第二条基线左侧的第三个点被检测到。新的点与三角网的顶点相连，以创建新的边和三角形。值得注意的是，劳森LOP交易所已被含蓄地和自动地纳入这一进程。重定义后更新新点会影响三角剖分内部或其相邻边以及三角形的相邻拓扑关系。重复1)-4)，直到凸闭包中的所有其他点都被处理。5.插入约束线段，确定其内边缘与约束线段相交的所有三角形，计算交点，并形成约束线段的相交三角剖分。将交点插入虚拟点链表。将所有虚拟点添加到约束线段的相交三角测量中。以与上述点插入相同的方式更新此三角测量(仅更新

17、相交三角测量中的那些三角形)。从约束线段的起点开始，追踪所有相交的虚拟点，并通过生成的短线段重新定义约束线段，直到约束线段的结束节点。重复上述操作，直到添加完所有约束线段。6.切掉外围边界，包括内部和外部边界。内周边界可以定义轮廓插值中应该避免的区域。外围边界定义了一个极限框架，在此框架外的内插或外插不正确、无用或无效。因此，应该从Diloni三角测量中删除内周边界内和外周边界外的所有三角形，并修剪内边界。对于数据中的所有内周边界，以下步骤处理内边界裁剪：以建立一个空的删除边链表，并将内周边界的第一条边存储在该链表中。对于链表中的下一条删除的边，删除其左边的三角形，并将该三角形所有边的非边界边添加到链表中。更新边界边和与内周边界相邻的三角形之间的相邻拓扑关系。重复上述操作，直到所有删除的边界都被处理完毕。与内部边界约简类似，外部边界约简包括以下