一种全球三维地形显示方法

摘要

本发明公开了一种全球三维地形显示方法。一种全球三维地形显示方法，包括以下步骤：利用三角四叉树剖分模型构建层次性高程和纹理数据模型；利用星下点计算可视化区域，得到视点下可视区域所有的三角面片，所述星下点为地球中心与视点的连线在地球表面上的交点；根据星下点的视点误差确定实际对应的数据分辨率，将可视区域内的所有三角面片进行数据筛选，确定待绘制的可见数据集；绘制可见数据集。上述方案中，层次性高程和纹理模型建立在三角四叉树剖分模型的基础上，而不是基于平面地图的层次性剖分，有效地减少了信息冗余，避免极区及高纬度区域的放射问题；并且通过星下点计算可视区域，其时间复杂度较低，有助于充分提高计算效率。

权利要求

1.一种全球三维地形显示方法，其特征在于，包括：S1，利用三角四叉树剖分模型构建层次性高程和纹理数据模型；

S2，由视点确定星下点的位置；其中，所述星下点为地球中心与视点的连线在地球表面上的交点；

S3，由视点确定球面可视区域；

S4，以球面可视区域的最大弦为直径构成等效圆锥体；其中，所述等效圆锥体由以球面可视区域的最大弦为直径构成的视锥体与球面的四个交点和视点组成；

S5，利用等效圆锥体底面圆的半径和剖分分辨率估计式计算星下点三角面片剖分深度；

S6，根据邻域查找算法，将星下点对应的三角面片作为种子面片向外扩展，逐个获得落在或者部分落在可视区域的三角面片；其中，邻域查找算法为根据三角面片的相邻关系，包括上下左右关系，得到与之相邻的三角面片；

S7，获得每个可视区域三角面片的剖分深度；

S8，获得视场误差容许的分辨率；

S9，判断所述可视区域三角面片的剖分深度与所述视场误差容许的分辨率是否相等，若相等，则执行步骤S11；否则执行步骤S10；

S10，对所述可视区域三角面片进行剖分，执行步骤S9；

S11，将所述可视区域三角面片对应的数据加入待绘制的数据集中；

S12，绘制可见数据集；

其中，利用三角四/九叉树剖分模型构建层次性高程和纹理数据模型，具体为：选用适当的球面剖分模型构建正多面体四叉树表示的剖分模型；

将剖分模型进行多级剖分；

按照剖分结点网格将原始数据反算至球面，所述原始数据包括高程数据和纹理数据。

2.根据权利要求1所述的方法，其特征在于，所述正多面体为正八面体。

3.根据权利要求1所述的方法，其特征在于，所述正多面体为正二十面体。

说明书

一种全球三维地形显示方法

技术领域

[0001] 本发明涉及地形显示技术领域，特别是涉及一种全球三维地形显示方法。

背景技术

[0002] 随着Google Earth以及NASA的World Wind等软件的推出，基于全球的地形快速可视化技术逐渐成熟。Google Earth和World Wind是基于传统的层次性平面瓦片技术，通过经纬度投影，将球面展开为平面，按照某种方式进行平面剖分。

[0003] 以World Wind为例，其数据以全球纹理影像数据或者区域影像数据为基础，按照初始剖分规格生成多分辨率的纹理影像四叉树金字塔数据集。所谓金字塔是指一种分辨率由粗到精的影像数据结构，金字塔的最底层是原始影像，分辨率最高，数据量也最大；从底层开始，分辨率逐渐降低，数据量随之减小；金字塔数据结构模拟了人眼数据由粗到精的结构，常用于影像匹配和地形三维显示，生成金字塔数据结构可以采用抽点采样或小波的方法完成。World Wind主要的数据输入为全球范围或者某区域(附加空间位置描述信息)的地理坐标投影图像或者数字高程模型(DEM，digital elevation model)，支持TIFF、PNG、BMP等文件格式。它采用四分法对纹理数据进行处理。图1显示了一种纹理剖分方式：0级初始分割为5×10块，跨度为36度，然后其他级按照四分法进行构建，1个数据块分裂为4个数据块。考虑到DEM数据的压缩，对于DEM数据采用20度的分割单位，0级初始化分割为9×18块，每个数据块的纹理按照150×150进行采样。然后World Wind系统按照剖分深度逐次计算，找到适当分辨率下的视场所对应的可视数据，以得到待绘制的数据集。

[0004] 但是，由于现有技术基于传统的层次性平面瓦片技术，数据点的分布与纬度无关，其数量并没有随着纬圈周长减少而减少，纬度越高，数据点密度越大，这样导致随着纬度增加，信息冗余也相应增大，所绘制的纹理的放射状越明显，以至于两极区域严重失真；并且2
当计算可视区域时，现有技术按照剖分深度逐次计算，其有较高的时间复杂度o(n)，其中n为剖分深度，计算效率较低。

发明内容

[0005] 为解决上述技术问题，本发明实施例提供一种全球三维地形显示方法，以有效地减小信息冗余，避免极区及高纬度区域的放射问题，并有效提高计算效率。

[0006] 本发明实施例提供一种全球三维地形显示方法，包括以下步骤：

[0007] A、利用三角四叉树剖分模型构建层次性高程和纹理数据模型；

[0008] B、利用星下点计算可视化区域，得到视点下可视区域所有的三角面片，所述星下点为地球中心与视点的连线在地球表面上的交点；

[0009] C、根据星下点的视点误差确定实际对应的数据分辨率，将可视区域内的所有三角面片进行数据筛选，确定待绘制的可见数据集；

[0010] D、绘制可见数据集。

[0011] 由以上本发明实施例提供的技术方案可见，层次性高程和纹理模型建立在三角四叉树剖分模型的基础上，而不是基于平面地图的层次性剖分，有效地减少了信息冗余，避免极区及高纬度区域的放射问题；并且通过星下点计算可视区域，其时间复杂度较低，有助于充分提高计算效率。

附图说明

[0012] 为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明中记载的一些实施例，对于本领域普通技术人员来讲，还可以根据这些附图获得其他的附图。

[0013] 图1为平面瓦片技术中一种纹理剖分方式剖分示意图：

[0014] 图2为正二十面体球面剖分透视图；

[0015] 图3为正八面体球面剖分透视图；

[0016] 图4为三角楔子构建三角面片最小包络体示意图；

[0017] 图5为多分辨率格网图；

[0018] 图6为屏幕误差计算的示意图；

[0019] 图7为原始三角内部经过四分法和九分法剖分后对应的示意图；

[0020] 图8为视锥体与球相交的一个截面图；

[0021] 图9为本发明实施例所提供的全球三维地形显示方法流程图一；

[0022] 图10为本发明实施例所提供的全球三维地形显示方法流程图二；

[0023] 图11为本发明实施例所提供的全球三维地形显示方法流程图三；

[0024] 图12为本发明实施例所提供的全球三维地形显示方法流程图四；

[0025] 图13为本发明实施例所提供的全球三维地形显示方法流程图五。

具体实施方式

[0026] 为了引用和清楚，现将本发明涉及到的技术名词以及一些运算方法介绍如下：

[0027] 1、三角四叉树剖分模型：在球内接柏拉图立体(比如正四面体、正六面体、正八面体、正二十面体等)所产生的球面三角剖分基础上，对每个球面三角进行四分，所得到的一种层次性三角剖分树；0级剖分根结点数目为柏拉图立体三角平面的数目，其他剖分深度父三角皆产生四个子球面三角。例如正二十面体球面剖分透视图(其中，左：剖分深度n＝0，中：n＝2，右：n＝4))如图2所示，正八面体球面剖分透视图(其中，左：剖分深度n＝
0，中：n＝2，右：n＝4))如图3所示。

[0028] 2、剖分分辨率的估计可采用两种方式：

[0029] 第一种为面积平均法：

[0030] 假设球半径为单位长，其球面积为4π。剖分n次，每个0级面片将产生22n个基2n
面片，正二十面体总共为20×2 个面片，每个面片的面积为： 正八面体总共
2n
为8×2 个面片，每个面片的面积为

[0031] 第二种为角度估计法：

[0032] 对于STQIE以及QTM等剖分，赤道上分布的边长是均匀的，赤道n(n＞0)次剖分后n-1 n将被等分为10×2 或者4×2 个弧段。因此正二十面体的基面片的弧为：
正八面体的基面片的弧为：angle＝π2-n-1。

[0033] 设弧边为α，对于正二十面体，令理想面片的剖分深度为n且剖分深度
-n-1 -n-2

[0034] 对于正八面体，令理想面片的剖分深度为n且π2 ≥α≥π2 ，剖分深度[0035] 其中 为计算比α小的最大整数的操作算子，计算过程如下：

[0036]

[0037] 3、对象空间(ε)误差和屏幕空间(ρ)误差

[0038] 本发明建立在全球高程模型基础上，法线方向是球心与顶点之间的连线，因此高度矢量方向各不相同。可采用三角楔子来构建三角面片最小包络体，如图4所示。对于任一顶点i，假设投影屏幕误差为ρij＝ρ(εj，pi，θ)，其中εj为该顶点所在的三角面片j的对象空间误差，θ为视点。当pij小于一个常数τ，则三角面片j的子三角不可见，三角不需要进一步分裂；反之亦然。如果从底向上构建层次性三角网，则合并子三角以形成更大的三角直到ρij首次等于或大于τ。假设ρ(εj，pi，θ)是一个ε单调函数及ρ(εj，pi，θ)＞ρ(εk，pi，θ)，其中k为三角j的所有子三角。当εj增大，三角分裂机率也随之增大，而对于同一个视点，父三角应该在子三角之前分裂，父三角不分裂，小三角的可见性越小。满足这个关系，就能保证：子三角可见，则父三角面片必然可见；三角不可见，则其子三角必不可见。如图5为多分辨率格网显示个例。

[0039] (i)三角面片的对象空间误差ε

[0040] 多数地形三维显示研究，包括Lindstrom等都直接采用原始数据点与顶替点之间垂直高度差或点到面的垂直距离。发明采用后一种方式，即点到面的垂直距离μ来衡量表面的起伏度。为了计算简便，可以用由顶点与顶点法向线段和平面的交点组成的线段代替，如图4楔子中的EH、FJ或DG代替，其中 令三角面片j的对象空间误差

[0041]

[0042] 其中μk为剖分三角面片j新增顶点到三角面片j的距离。

[0043] (ii)屏幕空间误差ρ

[0044] 屏幕空间误差ρ是指将对象空间ε投影在屏幕上的大小。

[0045] 主要考虑透视投影。视点矢量 通过球心O。如图6，假设视点矢量 与过pi的法方矢量 交角为θ，则pi的对象空间误差的矢量可分解为视点矢量方向分量σ以及与投影面平行的分量v，其中σ＝εcosθ，且v＝εsinθ。v分量与投影有关。

[0046] 根据透视投影的概念可知，存在下面的投影关系：

[0047]

[0048] 其中λ为屏幕像素映射比例，一般地 为视场角，w为视场角对应的像素数目。由于σ＜＜||e-pi||， 且||Me||＝||oe||-||opi||cosθ。上式转换为

[0049]

[0050] 代入ρj＞τ得到

[0051]

[0052] 因此当上式成立时，pi可见，所在三角需要进一步分裂。注意当θ为0时，即pi在视点矢量方向上，cosθ为1，上式右侧为无穷。

[0053] 为了使本技术领域的人员更好地理解本发明中的技术方案，下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员所获得的所有其他实施例，都应当属于本发明保护的范围。

[0054] 本发明提供一种全球三维地形显示方法，以有效地减小信息冗余，避免极区及高纬度区域的放射问题，并有效提高计算效率。

[0055] 如图9所示，本发明所提供的全球三维地形显示方法，包括以下步骤：

[0056] S1、利用三角四叉树剖分模型构建层次性高程和纹理数据模型；

[0057] S2、利用星下点计算可视化区域，得到视点下可视区域所有的三角面片，所述星下点为地球中心与视点的连线在地球表面上的交点；

[0058] S3、根据星下点的视点误差确定实际对应的数据分辨率，将可视区域内的所有三角面片进行数据筛选，确定待绘制的可见数据集；

[0059] S4、绘制可见数据集。

[0060] 三维客户端直接对待绘制的数据集进行处理，从而完成地形三维绘制任务。

[0061] 由以上本发明实施例提供的技术方案可见，层次性高程和纹理模型建立在三角四叉树剖分模型的基础上，而不是基于平面地图的层次性剖分，有效地减少了信息冗余，避免极区及高纬度区域的放射问题；并且通过星下点计算可视区域，其时间复杂度较低，有助于充分提高计算效率。

[0062] 其中，步骤S1中，高程和纹理数据转换为全球三角四叉树剖分模型基础上，即按照剖分模型对原始的高程数据和纹理数据进行重新采样而生成，具体步骤如图10所示：

[0063] S11、选用适当的球面剖分模型构建正多面体四叉树表示的剖分模型；

[0064] 适当的球面剖分模型可以为可以选用STQIE剖分模型、Snyder的ISEA、Dutton的QTM、HTM以及SQT等球面剖分模型。选择其中一种球面剖分模型构建正八面体、正二十面体或者其他正多面体四叉树表示的剖分模型。

[0065] 在构建剖分模型时，构建方式可以为以下三种：第一种方式是在球面柏拉图立体(包括正四面体、正六面体、正八面体、正十二面体和正二十面体)上直接剖分球面，如Sadourny的剖分模型以及Lian Song等所提出的小圆弧剖分模型等；第二种方式是循环剖分柏拉图立体的弦，然后映射到球面，如Dutton所提出的QTM模型等；第三种方式是均匀剖分展开在柏拉图立体各面的地图投影，如袁文所提出的EARP投影族、Snyder多面体投影族、Fekete提出的SQT模型、Fuller-Gray投影等，然后反投影到球面。

[0066] S12、将剖分模型进行多级剖分；

[0067] 所谓的多级剖分可以四分法，九分法，如图7所示，图中从左到右依次为原始三角，四分后的原始三角和九分后的原始三角。在具体的剖分过程中，选择适当的分法进行多级剖分，构建全球网格模型。

[0068] S13、按照剖分结点网格将原始数据反算至球面，所述原始数据包括高程数据和纹理数据。

[0069] 其中，按照一定采样分辨率形成拓扑三角节点数据集，以此构成剖分结点网格。

[0070] 在实际构建高程和纹理数据模型的过程中，不限于先多级剖分再进行原始数据的反算，也可以先进行原始数据的反算至球面，然后再进行多级剖分。

[0071] 更进一步的，步骤S2由视点确定星下点的位置，然后利用星下点计算可视区域中的所有三角面片，具体步骤如图11所示：

[0072] S21、由视点确定星下点的位置；

[0073] 由于星下点是地球中心与视点的连线在地球表面上的交点，所以可根据视点确定星下点的位置。

[0074] S22、根据等效圆锥体底面圆半径计算星下点对应的三角面片的剖分深度，所述等效圆锥体由以球面可视区域的最大弦为直径构成的视锥体与球面的四个交点和视点组成；

[0075] 根据等效圆锥体底面圆半径计算星下点对应的三角面片的剖分深度，具体步骤如图12所示：

[0076] S221、由视点确定球面可视区域；

[0077] S222、以球面可视区域的最大弦为直径构成等效圆锥体；

[0078] 等效圆锥体是以球面可视区域的最大弦为直径构成的一个圆锥体。由于视锥体一般地为正四棱台，那么其切割球体时，至少能找到由四个侧平面与球面的交点组成的平面使得四个点以及视点在同一侧。则该平面切割球体得到一个圆，以该圆为圆锥底面构建任意的圆锥体，圆锥体顶点在视点一侧且在在该侧圆锥体与球体不存在切割，则该圆锥体为视锥体在球面上的等效圆锥体，该圆锥体与球面的切割包囊了整个可视区域。图5为视锥体与球相交的一个截面，DMN为等效圆锥体的截面。图8中为视锥体与球的相交截面，其中E为视点，EC为视点方向，AEB为视角，AB为近裁平面截面，M和N分别为截面与球面的交点，C为MN中点，D为等效圆锥体的顶点，OC延长线上任意一点。

[0079] 对于上述等效圆锥体存在以下定理：

[0080] 落在等效圆锥体里的球面点与等效圆锥体顶点的距离小于等效圆锥体锥体与球面交点与顶点的距离 而锥体外部的球面点的距离则大于交点的距离

[0081] 所述可视区域为球体曲面与视锥体的相交的区域且该区域所对应的球表面面向视点。

[0082] S223、利用等效圆锥体底面圆的半径和剖分分辨率估计式计算星下点三角面片剖分深度。

[0083] 根据视场角、视场比例以及视锥体的参数方程式等获得等效圆锥体的半径，利用该半径和分辨率估计式获得星下点所在面片的剖分深度。

[0084] S23、将所述三角面片作为种子面片向外扩展，逐个获得落在或者部分落在可视区域的三角面片。

[0085] 根据邻域查找算法，将所述三角面片作为种子面片向外扩展，逐个获得落在或者部分落在可视区域的三角面片，以确定可视区域的三角面片，其中，邻域查找算法为根据三角面片的相邻关系，包括上下左右关系，快速的得到与之相邻的三角面片。

[0086] 上述步骤S3具体步骤如图13所示：

[0087] S31、获得每个可视区域三角面片的剖分深度；

[0088] S32、获得视场误差容许的分辨率；

[0089] S33、判断所述可视区域三角面片的剖分深度与所述视场误差容许的分辨率是否相等，若相等，则执行步骤S35；否则执行步骤S34；

[0090] S34、对所述可视区域三角面片进行剖分，执行步骤S33；

[0091] S35、将所述可视区域三角面片对应的数据加入待绘制的数据集中。

[0092] 可以理解的是，上述方案只是一种具体的实现方式，并不构成对本发明方案的限定，在上述方案的基础上，本领域技术人员可以根据实际应用环境设计其他形式的经验函数，或者采用其他具体方式获得网络处于安全/不安全状态的可信度，这些也都应属于本发明的保护范围。

[0093] 为了使本技术领域的人员更好地理解本发明方案，下面结合上述流程图，以构建正八面体四叉树剖分模型为例对本发明作进一步的详细说明。

[0094] 选用一种球面剖分模型构建正八面体，构建方式可以为在球面柏拉图立体上直接剖分球面；

[0095] 采用四分法，将剖分模型多级剖分；

[0096] 按照剖分结点网格将包括高程和纹理数据等原始数据反算值球面；可按照一定采样分辨率形成拓扑三角结点数据集，对于正八面体，原始三角边结点数目为8，令k＝8，带入拓扑三角结点数目公式 得到正八面体对应的拓扑三角结点数目。

[0097] 确定一个视点，由视点确定星下点的位置，以及球面可视区域；

[0098] 由视点以及球面可视区域最大弦为直径确定视锥体，以视锥体与球面的四个交点和视点组成一个等效圆锥体；假设视场角为φ，视场比例为η。则在视场坐标系中，视锥体边可用下面的参数方程式表示(设视点与球心距离为T，球半径为R)：

[0099]

[0100] 取其与圆x2+y2＝R2的靠近视点一侧的交点，即取t最小解：

[0101]

[0102] 将t带入上式并得到x，y。

[0103] 此时等效圆锥体的顶点与交点间的距离平方

[0104] 然后估计剖分深度。通过等效圆锥体底面圆的半径y估计剖分深度。设长为2y的弦的弧度为β，则 带入正八面体的剖分分辨率估计式 获得正八面体对应的剖分深度

[0105] 由此得到视点星下点所在剖分深度n的三角面片，即种子面片，然后通过邻域查找方法，检测种子面片邻接的面片的可视性，从而得到当前的可视区域范围。

[0106] 根据正八面体剖分分辨率的公式获得可视区域中每个三角面片的剖分深度；

[0107] 估计三角面片视场误差容许分辨率；

[0108] 由于可见三角面片是根据视锥体确定的最大三角剖分面片，还必须根据视场误差确定相应数据的分辨率。通过取从可表征三角面片几何特征的点集选择离视点最近的点来估计三角面片的分辨率。所述特征点是位于三角曲面上的可以表征三角区域面空间范围的任意点。假设该点为p，该点附近处一个微小距离与视线垂直，即θ为 将之代入屏幕空间误差的公式 得到 令ρ≤τ。则得到下面式子：

[0109]

[0110] ε表示了该点视觉容许的距离误差。因此，可以把ε看成最小面片的长度。则带入正八面体剖分分辨率估计式 得到三角面片的误差容许深度m：

[0111] 显然存在m≥n。

[0112] 对每个可见三角面片进行数据筛选。由上述可知m＞n，则表明该三角面片所对应的数据分辨率低于最优分辨率，需要对该三角面片进行剖分至m深度，并将所得到的三角面片所对应的数据集加入待绘制的数据集中。所述数据集包括纹理数据及高程数据。

[0113] 三维客户端直接对待绘制的数据集进行处理，从而完成地形三维绘制任务。

[0114] 上述利用星下点计算可视区域，能够快速定位剖分深度，检测的面片有限。图为三角检测数目与可视三角数目实测数据分布图，据统计，可视三角数目/三角检测数目为0.3～0.8之间，其时间复杂度与可视三角数目相关。星下三角最多拥有12个相邻三角，假设星下点所对应深度为l，最大动态剖分深度为k，本发明需检测的三角数目最多为：

[0115]

[0116] 而对于正八面体模型中，逐层检测方法的时间复杂度为：

[0117]

[0118] 对于正二十面体，时间复杂度为：

[0119]

[0120] 一般可以k将限制在2之内，最优值为1。因此，本方法的时间复杂度为o(1)，而d逐层检测方法的时间复杂度为o(4)。因此本发明的方法能有效提高可视化速度。

[0121] 以上具体实施例中，层次性高程和纹理模型建立在三角四叉树剖分模型的基础上，建立正八面体的剖分模型，而不是基于平面地图的层次性剖分，有效地减少了信息冗余，避免极区及高纬度区域的放射问题；并且通过星下点计算可视区域，其时间复杂度仅仅2
为o(1)，而逐层次计算的时间复杂度为o(n)，这样有助于充分提高计算效率。

[0122] 利用本发明，构建正二十面体四叉树剖分模型来实现全球三维地形显示的过程与构建正八面体四叉树剖分模型相似，不同的是正二十面体的剖分分辨率公式不同，使得星下点对应面片的剖分深度为 三角面片的误差容许深度为在此不在赘述。

[0123] 通过以上的实施方式的描述可知，本领域的技术人员可以清楚地了解到本发明可借助软件加必需的通用硬件平台的方式来实现。基于这样的理解，本发明的技术方案本质上或者说对现有技术做出贡献的部分可以以软件产品的形式体现出来，该计算机软件产品可以存储在存储介质中，如ROM/RAM、磁碟、光盘等，包括若干指令用以使得一台计算机设备(可以是个人计算机，服务器，或者网络设备等)执行本发明各个实施例或者实施例的某些部分所述的方法。

[0124] 本发明可用于众多通用或专用的计算系统环境或配置中。例如：个人计算机、服务器计算机、手持设备或便携式设备、平板型设备、多处理器系统、基于微处理器的系统、置顶盒、可编程的消费电子设备、网络PC、小型计算机、大型计算机、包括以上任何系统或设备的分布式计算环境等等。

[0125] 本发明可以在由计算机执行的计算机可执行指令的一般上下文中描述，例如程序模块。一般地，程序模块包括执行特定任务或实现特定抽象数据类型的例程、程序、对象、组件、数据结构等等。也可以在分布式计算环境中实践本发明，在这些分布式计算环境中，由通过通信网络而被连接的远程处理设备来执行任务。在分布式计算环境中，程序模块可以位于包括存储设备在内的本地和远程计算机存储介质中。

[0126] 以上所述仅是本发明的具体实施方式，应当指出，对于本技术领域的普通技术人员来说，在不脱离本发明原理的前提下，还可以做出若干改进和润饰，这些改进和润饰也应视为本发明的保护范围。