留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

一种顾及多重约束的三维地形简化方法

李胜辉 史瑞芝 朱明

李胜辉, 史瑞芝, 朱明. 一种顾及多重约束的三维地形简化方法[J]. 武汉大学学报 ● 信息科学版, 2018, 43(2): 241-247. doi: 10.13203/j.whugis20160431
引用本文: 李胜辉, 史瑞芝, 朱明. 一种顾及多重约束的三维地形简化方法[J]. 武汉大学学报 ● 信息科学版, 2018, 43(2): 241-247. doi: 10.13203/j.whugis20160431
LI Shenghui, SHI Ruizhi, ZHU Ming. Simplification Approach for 3D Terrain with Multi-constraints Consideration[J]. Geomatics and Information Science of Wuhan University, 2018, 43(2): 241-247. doi: 10.13203/j.whugis20160431
Citation: LI Shenghui, SHI Ruizhi, ZHU Ming. Simplification Approach for 3D Terrain with Multi-constraints Consideration[J]. Geomatics and Information Science of Wuhan University, 2018, 43(2): 241-247. doi: 10.13203/j.whugis20160431

一种顾及多重约束的三维地形简化方法

doi: 10.13203/j.whugis20160431
基金项目: 

国家自然科学基金 61301231

详细信息
    作者简介:

    李胜辉, 博士生, 主要从事三维地图交互与显示和地图制图与出版等领域的理论与方法研究。lishenghui2006@126.com

    通讯作者: 史瑞芝, 博士, 教授。ruizhishi@sina.com
  • 中图分类号: P283;P208

Simplification Approach for 3D Terrain with Multi-constraints Consideration

Funds: 

The National Natural Science Foundation of China 61301231

More Information
    Author Bio:

    LI Shenghui, PhD candidate, specializes in the theories and methods of 3D map display, cartography and map publication. E-mail: lishenghui2006@126.com

    Corresponding author: SHI Ruizhi, PhD, professor. E-mail: ruizhishi@sina.com
图(6) / 表(1)
计量
  • 文章访问数:  867
  • HTML全文浏览量:  85
  • PDF下载量:  337
  • 被引次数: 0
出版历程
  • 收稿日期:  2017-05-11
  • 刊出日期:  2018-02-05

一种顾及多重约束的三维地形简化方法

doi: 10.13203/j.whugis20160431
    基金项目:

    国家自然科学基金 61301231

    作者简介:

    李胜辉, 博士生, 主要从事三维地图交互与显示和地图制图与出版等领域的理论与方法研究。lishenghui2006@126.com

    通讯作者: 史瑞芝, 博士, 教授。ruizhishi@sina.com
  • 中图分类号: P283;P208

摘要: 三维模型在许多领域内均有着越来越深入的应用,为保证三维模型在不同存储空间、不同图形绘制能力、不同显示分辨率的终端电子设备上显示的统一性和一致性,在很多情况下需要对三维模型进行适度的简化。对于三维地形而言,纹理颜色、地形区域边界和重要顶点是其非常重要的视觉特征,本文将这三项特征作为约束因子引入到三维地形的简化过程中,并根据这三项特征对现有的二次误差测度算法和边折叠代价的计算方法进行了改进,使其在三维地形简化过程中不会出现明显退化。本文还将改进后的算法与原来算法进行了实验对比,结果表明,改进后的简化算法不仅能够在不同精度上保持三维地形视觉上的一致性,而且产生的几何误差也相对较小。

English Abstract

李胜辉, 史瑞芝, 朱明. 一种顾及多重约束的三维地形简化方法[J]. 武汉大学学报 ● 信息科学版, 2018, 43(2): 241-247. doi: 10.13203/j.whugis20160431
引用本文: 李胜辉, 史瑞芝, 朱明. 一种顾及多重约束的三维地形简化方法[J]. 武汉大学学报 ● 信息科学版, 2018, 43(2): 241-247. doi: 10.13203/j.whugis20160431
LI Shenghui, SHI Ruizhi, ZHU Ming. Simplification Approach for 3D Terrain with Multi-constraints Consideration[J]. Geomatics and Information Science of Wuhan University, 2018, 43(2): 241-247. doi: 10.13203/j.whugis20160431
Citation: LI Shenghui, SHI Ruizhi, ZHU Ming. Simplification Approach for 3D Terrain with Multi-constraints Consideration[J]. Geomatics and Information Science of Wuhan University, 2018, 43(2): 241-247. doi: 10.13203/j.whugis20160431
  • 近年来,三维地形建模技术在地形仿真、三维导航、虚拟现实和增强现实领域得到了越来越广泛的应用[1]。随着多终端电子设备的不断发展,如移动手机、平板电脑、可穿戴设备等,这些移动终端也对三维地形有了新的显示需求。一般来讲,三维模型越精细越能表现出地形的细节要素,显示效果越好[2]。但不同终端设备的存储空间、图形绘制能力、显示分辨率等存在差异,尤其是移动终端的配置往往相对较低。若要在不同终端设备上表现相同的显示效果,虽然可以通过不断提升终端设备的硬件配置来实现[3],但仍需要利用相关简化算法对三维模型进行适度简化计算,建立不同精度的细节层次LOD模型(levels of detail,LOD),使之在满足对三维模型精度需求的基础上,保持显示效果的统一性和一致性[4]

    三维模型的简化需要在减少模型多边形面数的同时,尽量保持三维模型的原始形状和拓扑结构[5]。实现三维模型简化的算法有很多,如顶点删除[6]、小波变换[7]、顶点聚类[8]、边折叠等[9]。其中,经过改进过的边折叠算法由于具有简化效果好、简化速度快等优势,成为目前非常有效的一种简化算法。许多学者对边折叠算法进行了多项优化和改进,比如采用局部二次误差测度来衡量边折叠的代价[10],提高了算法运行效率和简化效果,将纹理颜色考虑在内,有效保持简化模型的视觉特征等等[11]

    对于三维地形而言,除了纹理颜色之外,地形的区域边界、重要顶点特征等均为三维地形非常重要的视觉特征[12],所以在简化过程中,这些视觉特征也应当被考虑在内,而目前的地形简化算法却较少充分考虑这方面的问题。本文对边折叠算法的误差测度算法和折叠代价的计算方法进行了改进,综合考虑了三维地形的区域边界、纹理颜色和顶点重要度等视觉要素,并将三者作为特征约束因子应用到三维地形的简化过程当中,尽量减少视觉特征在三维地形简化过程中受到的影响。此外,本文还将改进后的算法与未考虑特征约束的边折叠算法进行了实验对比,以进一步定量评估改进算法的简化效果。

    • 边折叠简化算法是一种适用于三角形网格的简化算法,如图 1所示。通过对边(vi, vj)进行折叠操作,产生新的顶点vn,并用vn代替vivj,连接原有顶点,从而实现三角形面数的删减。在边折叠简化算法的计算过程当中,关键在于折叠边的选择和新顶点位置的确定。选择折叠边时要保证简化后的模型与原始模型的误差尽可能的小,一般是采用计算折叠代价的方式评估删除折叠边对整体三维模型所造成的影响,折叠代价越大,折叠后对模型造成的影响越大;反之,折叠后对模型的影响越小。根据折叠代价的大小可以对待折叠边进行排序,优先删除折叠代价较小的边,然后再重新计算新模型各边的折叠代价并排序,如此循环,直至模型简化至符合要求为止。

      图  1  边折叠

      Figure 1.  Edge Collapse

      边折叠代价可以通过计算顶点与其所有相邻三角形的几何距离进行度量[13],在欧式三维空间内,任何一个三维平面均可用nTv+d=0来表示,其中n=[a, b, c]T,为平面的法矢量,则顶点v=(x, y, z)到该平面距离的平方D2(v)可表示为:

      $$ \begin{align} {D^2}\left( v \right) = &{({\boldsymbol{n}^{\rm T}}v + d)^2} = ({\boldsymbol{n}^{\rm T}}v + d)({\boldsymbol{n}^{\rm T}}v + d) = \\ &{v^{\rm T}}(\boldsymbol{n}{\boldsymbol{n}^{\rm T}})v + 2d{\boldsymbol{n}^{\rm T}}v + {d^2} \end{align} $$ (1)

      从式中可以看出,D2(v)明显是一个二次的多项式,所以该算法又称为二次误差测度算法,同时式(1)也可用式(2)代替表示:

      $$ Q\left( v \right) = {v^{\rm T}}Av + 2{b^{\rm T}}v + c $$ (2)

      其中,Q=(A, b, c) =(nnT, dn, d2)。

      一般情况下,顶点v会与多个三角形面相连,顶点v到这些三角形面的距离平方均可采用式(2)的方法进行计算,然后将这些距离的平方相加,这样就可以得到三维模型中每个顶点的二次误差测度。当边(vi, vj)→vn进行折叠的时候,边(vi, vj)的二次误差测度采用Q=Qi+Qj计算即可,边(vi, vj)的折叠代价则可以用新顶点vn处产生的误差来计算,即Q(vn)= Qi(vn)+Qj(vn)。通过计算每条边的折叠代价可以建立一个升序序列,优先删除序列中折叠代价较小的边,从而使每次简化都能保证简化模型与原始模型的几何差异尽可能的小。

      在计算边折叠代价之前,折叠后新顶点的坐标位置也需要进行确定。一般有两种新顶点位置的确定方法,一种是子集位置确定,另一种是最优位置确定。前者采用vivj中折叠代价较小的顶点来作为新的顶点,这种方法运算简单,速度较快,但简化后的模型与原始模型的几何差异会比较明显。所以,本文选择最优位置确定方法来计算新顶点的坐标位置。最优位置确定方法理论上也比较简单,通过对边(vi, vj)的二次误差测度Qxyz方向上求偏导,即∂Q/∂x=∂Q/∂y=∂Q/∂z=0,求解这个三元一次方程组,即可得到新顶点的坐标位置(xn, yn, zn)。由于Q在点(xn, yn, zn)处是极小值,所以折叠代价也最小,因此通过这种方法计算得到的新顶点能够较大程度上减少简化模型与原始模型之间的几何差异。

    • 三维地形除了几何特征之外,还会有许多其他属性,比如区域边界、颜色纹理、顶点重要度等,这些特征属性在模型简化过程中也是需要特别处理和保留的。在前文的模型简化过程中,仅以顶点与相邻平面的距离来计算折叠代价,进而决定边的折叠顺序,一些重要的属性特征并没有得到特别处理和保留,所以在模型简化过程中很容易造成这些重要特征的退化。因此,本文结合三维地形的特点,介绍3种特征约束因子,并将其结合到折叠代价的计算过程当中,用以保留三维地形的一些重要特征。

    • 三维地形的边界是非常重要的特征,在三维地形的简化处理过程中需要进行特别保留。如图 2所示,通过对三维地形模型中的所有边进行标记,将边分别标记为内边、一般边和边界边,以区分不同边的类型。内边是指一条边的两个端点都不在边界上,一般边指一条边的两个端点有一个在边界上,边界边则两个端点均在边界上,任何一条边(vi, vj)都属于这三者之一[14]。通过调整3种类型边在计算过程中的权重,可以使边界边的折叠代价最大,内边的折叠代价最小,从而延迟对边界边的简化,使其得到较好的保留。由于三维地形的立体特征,若要保持地形整体结构在简化过程中的一致性,不仅需要保留区域边界,还需要保证地形的整体结构在简化过程中保持一致,为了解决这个问题,本文引入了顶点重要度这项指标,具体在§2.3进行阐述。

      图  2  3种类型的边

      Figure 2.  Three Types of Edge

    • 除了几何特征之外,三维地形模型为了增强地形场景的真实感,会将纹理影像贴附在模型的表面,从而使三维模型在视觉上与真实地形更加接近[15]。在三维地形的简化过程中,如果不把纹理颜色信息考虑在内,仅仅根据几何特征进行计算,会使简化后的模型与原始模型的纹理颜色存在较大差异,影响三维地形的视觉一致性。

      对于具有纹理的三维地形模型,每个顶点除了空间坐标Vposition=(x, y, z)之外,还需要增加纹理贴图的坐标Vtexture=(u, v)。这样对于三维地形模型中的每个顶点而言,原来是用3个坐标值进行表示,增加纹理之后,就需要采用5个值进行表示,即顶点Vertex=(Vposition, Vtexture)=(x, y, z, u, v),也可以看做将每个顶点的表示从原来的三维扩展到了五维,前3个值表示代表空间坐标,后两个值代表纹理坐标。

    • 顶点重要度是衡量三维模型表面凹凸特性的一项指标,一般来讲,顶点越凸起,则该顶点越重要,在模型简化过程中越应当进行保留。反映在三维地形上,这些重要顶点主要分布在山顶、山脊、陡坡等区域,这些区域由于角度变化比较明显,与其他区域相比,对于保持地形的整体结构和轮廓更为重要。目前计算顶点重要性的方法有很多,比如高斯曲率、体积近似估计、平均法向量等等[16]。相比较而言,计算平均法向量的方法对于三维模型重要顶点的保持具有较好的效果[17]

      图 3所示,平均法向量是计算顶点V0所有相邻平面法向量的平均值来衡量顶点的重要性。式(3)为平均法向量的计算公式,m为相邻平面的个数。如果V0相邻平面的法向量与V0方向向量的方向越接近,顶点V0所处的位置就越平坦,该顶点越不重要,可以被优先删除。反之,如果相邻三角形面法向量与顶点V0的方向差别越大,顶点V0所处的位置就越凸起,该顶点就越重要,此时对V0的删除也应当做延后处理。

      图  3  平均法向量

      Figure 3.  Average Normal Vector

      $$ \boldsymbol{N} = \frac{{\sum\limits_{i = 1}^m {{\boldsymbol{n}_i}} }}{m} $$ (3)

      此外,实验表明,如果将顶点V0的方向向量与相邻三角形面的夹角作为权值,加入到平均法向量的计算过程中,会对三维模型顶点特征的保持具有较好的运算效果[18]图 3中的α为顶点V0与相邻三角形的夹角,式(4)为改进后的平均法向量计算公式:

      $$ \boldsymbol{N} = \frac{{\sum\limits_{i = 1}^m {{\alpha _i}{\boldsymbol{n}_i}} }}{{\sum\limits_{i = 1}^m {{\alpha _i}} }} $$ (4)
    • 现有的二次误差测度算法是通过计算原始模型与简化模型之间的几何误差来进行简化的,并没有涉及到其他属性特征的计算。对于三维地形而言,如果将区域边界、纹理颜色、顶点重要性等约束因子考虑在内的话,每个顶点不仅要有3个空间坐标值描述其空间位置,还应该有相应的属性值来描述这些约束因子。

      在各待折叠边进行数据初始化的时候,通过对各个边进行标记,分别标记为内边、一般边和边界边,能够完成区域边界特征的描述。纹理坐标可以用Vtexture=(u, v)进行表示,顶点特征约束主要是通过法向量进行计算,所以各个顶点的法向量可以用Vnormal=(a, b, c)进行表示。如果用八维向量描述模型中的每个顶点,则对于每个顶点V,前3个值描述空间坐标,其他值用来描述顶点的纹理坐标和法向量,如式(5)所示。

      $$ \begin{align} V& = \left( {{V_{\rm position}},{V_{\rm texture}},{V_{\rm normal}}} \right)\\ &= \left( {x,y,z,u,v,a,b,c} \right) \end{align} $$ (5)

      三维地形中的每个顶点都可以用式(5)中的8个值描述其空间坐标、纹理坐标和法向量,然后根据这8个值应用现有的折叠代价计算框架进行计算。不过,目前的二次误差测度计算公式实际上是根据每个顶点的空间坐标值计算距离,没有涉及到属性值的误差计算,所以需要对该计算方法进行相应的改进。

      对于三维地形中任意一个三角形面T=(p, q, r),其中pqr为三角形面的3个顶点,每个顶点都有8个值,即顶点p=(px, py, pz, pu, pv, pa, pb, pc)。所以相当于用3个八维的点来定义了一个二维的平面,此时的二次误差测度应该是计算顶点到这个3个八维点所定义二维平面的距离。如图 4所示,令e1e2为三角形面T平面上两个正交的单位向量,p为原点,则顶点v到平面T的距离就等于顶点v到正交单位向量e1e2所定义平面的距离。

      图  4  正交单位向量e1e2

      Figure 4.  Orthonormal Vectors e1 and e2

      由于e1e2为三角形面T=(p, q, r)上两个正交的单位向量,所以e1e2可以用顶点pqr进行表示,如式(6)、式(7)所示。由于三维模型中的每个顶点都有8个值进行描述,所以可以看做把顶点放在一个原点为p的八维空间内,每个点都有八个互相正交的单位向量进行描述,即e1e2e3e4e5e6e7e8,这8个向量均为单位向量且互相正交。

      $$ {\boldsymbol{e}_1} = \frac{{q - p}}{{\left\| {q - p} \right\|}} $$ (6)
      $$ {\boldsymbol{e}_2} = \frac{{r - p - ({\boldsymbol{e}_1}\cdot\left( {r - p} \right)){\boldsymbol{e}_1}}}{{r - p - ({\boldsymbol{e}_1}\cdot\left( {r - p} \right)){\boldsymbol{e}_1}}} $$ (7)

      根据目前简化算法原理,需要计算顶点到相邻三角形面距离的平方。同理,对于八维空间中的任意一点v,需要计算该点到相邻三角形面T=(p, q, r)距离的平方D2(v)。令u=p-vp为坐标原点,则u长度的平方可表示:

      $$ {\left\| \boldsymbol{u} \right\|^2} = (\boldsymbol{u} \cdot {\boldsymbol{e}_1}){ ^2} + {(\boldsymbol{u} \cdot {\boldsymbol{e}_2})^2} + \ldots + {(\boldsymbol{u} \cdot {\boldsymbol{e}_8})^2} $$ (8)

      式(8)可变形为:

      $$ \begin{array}{l} {\left\| \boldsymbol{u} \right\|^2} - {\left( {\boldsymbol{u} \cdot {\boldsymbol{e}_1}} \right)^2} - {\left( {\boldsymbol{u} \cdot {\boldsymbol{e}_2}} \right)^2}\\ = {(\boldsymbol{u}\cdot{\boldsymbol{e}_3})^2} + {(\boldsymbol{u}\cdot{\boldsymbol{e}_4})^2} + \ldots + {(\boldsymbol{u}\cdot{\boldsymbol{e}_8})^2} \end{array} $$ (9)

      由于p为坐标原点,从式(9)可以明显看出,式(9)的等号右边为顶点v到单位向量e1e2所定义平面距离的平方,换而言之,式(9)等号右边即为顶点v到三角形面T=(p, q, r)距离的平方。所以对于三维模型中的任一顶点v,它到其相邻三角形面距离的平方可以用式(10)表示:

      $$ \begin{array}{l} \quad{\boldsymbol{D}^2}\left( v \right) = {\left\| \boldsymbol{u} \right\|^2} - {\left( {\boldsymbol{u} \cdot {\boldsymbol{e}_1}} \right)^2} - {\left( {\boldsymbol{u} \cdot {\boldsymbol{e}_2}} \right)^2}\\ = {\boldsymbol{u}^{\rm T}}\boldsymbol{u} - ({\boldsymbol{u}^{\rm T}}\cdot{\boldsymbol{e}_1})(\boldsymbol{e}^{\rm T}_1 \cdot \boldsymbol{u}) - ({\boldsymbol{u}^{\rm T}} \cdot {\boldsymbol{e}_2})(\boldsymbol{e}^{\rm T}_2\cdot u) \end{array} $$ (10)

      u=p-v代入式(10),可得:

      $$ \begin{array}{c} {\boldsymbol{D}^2}\left( v \right) = {\boldsymbol{v}^{\rm T}}\boldsymbol{v} - 2{\boldsymbol{p}^{\rm T}}\boldsymbol{v} + \boldsymbol{p} \cdot \boldsymbol{p}\\ - {\boldsymbol{v}^{\rm T}}({\boldsymbol{e}_1}\boldsymbol{e}^{\rm T}_1)\boldsymbol{v} + 2(\boldsymbol{p} \cdot {\boldsymbol{e}_1})\boldsymbol{e}^{\rm T}_1\boldsymbol{v} - {(\boldsymbol{p}\cdot{\boldsymbol{e}_1})^2}\\ - {\boldsymbol{v}^{\rm T}}({\boldsymbol{e}_2}\boldsymbol{e}^{\rm T}_2)\boldsymbol{v} + 2(\boldsymbol{p} \cdot {\boldsymbol{e}_2})\boldsymbol{e}^{\rm T}_2\boldsymbol{v} - {(\boldsymbol{p} \cdot {\boldsymbol{e}_2})^2} \end{array} $$ (11)

      式(11)可表示为二次误差测度公式的形式,即Q(v)=vTAv+2bTv+c,其中Abc分别如式(12)所示。经过改进后的二次误差度量公式,将纹理、顶点重要性约束因子考虑在内,使折叠代价的计算不仅仅依据几何误差,还加入纹理和法向量的误差计算:

      $$ \left\{ \begin{array}{l} \boldsymbol{A }= 1 - {\boldsymbol{e}_1} \cdot \boldsymbol{e}^{\rm T}_1 - {\boldsymbol{e}_2} \cdot \boldsymbol{e}^{\rm T}_2\\ \boldsymbol{b} = (\boldsymbol{p} \cdot {\boldsymbol{e}_1}){\boldsymbol{e}_1} + (\boldsymbol{p} \cdot {\boldsymbol{e}_2}){\boldsymbol{e}_2} - \boldsymbol{p}\\ \boldsymbol{c} = \boldsymbol{p} \cdot \boldsymbol{p} - {(\boldsymbol{p} \cdot {\boldsymbol{e}_1})^2} - {(\boldsymbol{p}\cdot{\boldsymbol{e}_2})^2} \end{array} \right. $$ (12)
    • 改进后的算法综合考虑了区域边界、颜色纹理、顶点重要度3项特征,其运算过程主要包括以下6个步骤。

      1) 三维地形数据初始化,根据每条边两个端点的情况,将每条边标记为内边,一般边和边界边;

      2) 利用改进后的二次误差测度算法计算每条边的折叠代价;

      3) 根据每条边的的类型,增加边界边的权值,然后计算加权后的折叠代价;

      4) 根据折叠代价大小进行排序,建立一个升序序列,并存放于堆中;

      5) 选取折叠代价最小的边进行折叠,并利用1)~4)步计算与折叠边端点相关所有边的折叠代价,然后更新折叠代价的排序;

      6) 重复执行1)~5)步,直至简化至符合要求为止。

      为了定量评估改进算法对三维地形一致性的保持效果,本文采用三维模型误差计算方法对简化模型和原始模型的误差进行估计[19]。三维地形的误差估计主要依据两个指标,一是最大误差,二是平均误差[20]。最大误差的算法如式(13)和式(14)所示,式(13)中的d(vv′)为三维空间内两点间的欧式距离,e(vS)为简化后模型中的一点到原始模型S中所有点距离的最小值,式(14)中的E(S1S2)表示简化模型S1与原始模型S2的最大误差,在实际计算过程中E(S1S2)有时与E(S2S1)并不相等,本实验取两者较大值作为三维地形简化前后的最大误差,平均误差的计算如式(15)所示:

      $$ e\left( {v,S} \right) = \mathop {\min }\limits_{v\prime \in S} d\left( {v,v\prime } \right) $$ (13)
      $$ E({S_1},{S_2}) = \mathop {\max }\limits_{v \in {S_1}} e(v,{S_2}) $$ (14)
      $$ {E_m}({S_1},{S_2}) = \frac{1}{{\left| {{S_1}} \right|}}\int_{{S_1}} {e(v,{S_2}){\rm{d}}s} $$ (15)
    • 本文算法所运行的硬件环境为i5-2310,3.00 GHz处理器,显卡为NVIDIA Geforce GT420,内存为3 G的计算机,系统环境为Windows 7 Professional,软件开发工具为Microsoft Visual Studio 2010和OpenGL。简化前的三维地形模型共有30 868个面,15 718个顶点和566个边界边。图 5为根据几何距离进行边折叠简化的原来算法的简化效果,图 6为考虑边界特征、纹理颜色、顶点重要性等多重特征约束的改进后的三维地形简化效果。

      图  5  原来算法简化效果

      Figure 5.  Simplification Result by the Original Algorithm

      图  6  改进算法简化效果

      Figure 6.  Simplification Result by the Improved Algorithm

      图 5图 6可以看出,在将三维地形简化至20 000面以下时,仅根据几何距离进行简化的三维地形就出现了纹理颜色错乱,部分边界特征退化的现象,而顾及多重特征约束的简化算法对三维地形的边界特征、纹理颜色和重要顶点均有较好的保持效果,在不同的精度上基本可以保持与原始三维模型在视觉上的一致性。表 1为简化后的三维地形各项数据和误差,从渲染耗时来看,改进算法与原来算法的时间消耗差别不大,但改进算法能够更好保持三维地形在简化过程中视觉感受上的一致性。同时,简化等级越高的地形渲染耗时越少,说明地形简化算法对提高三维地形的绘制效率具有非常重要的意义。另外,由于改进算法对边界边进行了加权处理,所以边界边在简化过程中没有受到损失。简化后的三维地形误差可以采用Hausdorff距离度量,从表 1最大误差和平均误差的对比结果可以看出,与未考虑特征约束的边折叠算法相比,对于同一简化水平的三维地形,改进后的三维地形简化算法所产生的最大误差和平均误差均相对较小。

      表 1  简化数据对比

      Table 1.  Contrast of the Simplification Data

      简化等级 三角形面数/个 顶点数/个 边界边数/个 渲染耗时/ms 最大误差/m 平均误差/m
      原来算法 改进算法 原来算法 改进算法 原来算法 改进算法 原来算法 改进算法 原来算法 改进算法 原来算法 改进算法
      等级-1 24 693 24 692 12 625 12 630 555 566 673 672 0.096 0.051 0.021 0.013
      等级-2 12 339 12 338 6 295 6 453 251 566 426 431 0.913 0.617 0.210 0.091
      等级-3 6 171 6 170 3 178 3 369 187 566 264 273 3.248 1.783 1.012 0.483
      等级-4 3 085 3 084 1 604 1 826 124 566 191 199 5.328 3.611 2.093 1.007
      等级-5 1 541 1 540 812 1 054 83 566 112 117 7.715 4.322 3.132 1.909
      等级-6 769 768 413 668 55 566 77 83 9.127 6.315 5.012 2.368
    • 对于三维地形简化而言,地形的边界特征、纹理颜色和重要顶点是其非常重要的属性特征,本文将这些特征作为约束因子引入到三维地形的简化过程中,并根据这些约束因子的特点对边折叠算法中二次误差测度和折叠代价的计算方法进行了改进,实验结果表明:经过改进后的三维地形简化算法对地形的边界特征、纹理颜色和重要顶点具有较好的保持效果,而且简化产生的几何误差也相对较小。

      不过,由于顾及多重约束的简化方法是对角度变化比较明显的区域进行了特别的处理和保留,这些区域的保留效果也比较好。但对于角度变化相对平缓的区域,如部分鞍部、缓坡等区域会进行较大程度的舍弃。因此,如何在简化过程中平衡这些问题仍然需要进一步的实验和研究。

参考文献 (20)

目录

    /

    返回文章
    返回