论文部分内容阅读
不规则三角网(TIN)在表达地表形态方面具有很大的优势,它能精确的逼近地形表面,反应地形的原始细节,并且能够避免因地形的平坦陡峭造成的数据冗余,因而被广泛用于地形构建,Delaunay三角网剖分生成的TIN(简称D-TIN)由于具有许多突出的性质,如能避免出现狭长的三角形,因而相比其他剖分方式更具有实际应用价值,本文研究的基于多核下大地形并行构建就是以D-TIN的并行构建入手,D-TIN串行方面的构建经过几十年的发展已经相当成熟,然而在并行方面的研究虽然也有较多成果,但大多数都是针对分布式多处理机的集群环境进行的,很少有关于D-TIN在单机多核环境下的应用,为了充分利用有限的资源,挖掘单台计算机的并行潜能,本文设计出了一套适合多核环境下的D-TIN并行构建方案。主要的研究内容和成果包括以下几个方面:(1)本文对D-TIN并行构建过程所涉及到的包括矢量数据读取、可视化方法、无约束与约束情况下三角网的构建方法及数据结构、并行模型、并行方式、数据划分策略等理论都做了详细的介绍,为整个论文的研究奠定了良好的理论基础。(2)通过分析总结当前D-TIN并行研究现状,提出了基于分治算法结合四方边缘结构,以Open Mp为多核并行模型的并行设计方案。(3)对无约束域离散点三角网的并行构建中关于子凸包并行构建和并行合并算法进行了详细描述,并通过具体实验生成了并行与串行构建的结果,比较了时间效率、加速比和并行效率等,结果证明多核并行设计方案切实可行。(4)为了更加真实的表达地形实际情况,本文加入了约束地物(如房屋、河流等)来进行并行构建,主要通过插入以多边形为例的约束地物,研究了顶点插入、边插入和内部清空整个流程的算法,并对其并行改造做了介绍,同样通过具体实验生成了并行与串行的构建结果,评估了各指标。实验证明采用并行方式实现,能有效提高整体性能,节约时间成本。