基于凸包切割的不规则三角网及其邻接关系的生成算法

不规则三角网（TIN）是一种重要的数字高程模型,它一般是基于离散采样点来构建的;构建TIN的算法可归结为由二维平面内的离散点生成Delaunay三角网.目前有很多Delaunay三角网生成算法,但不足之处是已有的算法对三角形之间邻接关系的维护缺乏具体的论述和明确的约定.作者按照凸包切割的思想提出了一种完整的算法,并对三角网的生成和三角形邻接关系维护的具体步骤和约定做了详细论述.编程实验表明：本算法能够正确地将凸包剖分为三角形,且能够保证三角形之间具有正确的邻接关系;当将剩余的非凸包顶点的离散点插入已有的三角形时,仍能保持三角形之间的正确邻接关系.     

基于凸包切割的不规则三角网及其邻接关系的生成算法

不规则三角网(TIN)是一种重要的数字高程模型,它一般是基于离散采样点来构建的;构建TIN的算法可归结为由二维平面内的离散点生成Delaunay三角网.目前有很多Delaunay三角网生成算法,但不足之处是已有的算法对三角形之间邻接关系的维护缺乏具体的论述和明确的约定.作者按照凸包切割的思想提出了一种完整的算法,并对三角网的生成和三角形邻接关系维护的具体步骤和约定做了详细论述.编程实验表明:本算法能够正确地将凸包剖分为三角形,且能够保证三角形之间具有正确的邻接关系;当将剩余的非凸包顶点的离散点插入已有的三角形时,仍能保持三角形之间的正确邻接关系.     

地形三维可视化方案

采用生成Delaunay三角网的改进算法进行地形建模,以达到提高构网效率的目的,然后在DirectX9中用CJHJ 2005实现了川西某地域的三维可视化,并在此基础上,讨论了基于三角网的应用分析功能的实现,为三维地形的实施提出了有效的方案.     

基于最大外接圆的约束Delaunay三角剖分算法

目的 研究构建约束Delaunay三角网的方法 ,提高构建约束Delaunay三角网的速度.方法 基于生长法并利用分治法的思想,以约束边为基边分别向两侧重新构网,先构建Delaunay三角网,然后插入约束边并删除与约束边相交的边,按照构网条件对约束边两侧的空腔构网,直至约束边两侧构建成三角网,最后使其成为约束Delaunay三角网.结果 实验测试表明,在地形点数为5 000时,传统算法构建CDT时间为6 195 ms,笔者算法构建CDT时间为6 007ms,速度明显优于传统算法.结论 算法简单、运算速度快、内存开销小且易于实现.     

一种Delaunay三角网的改进生成算法

Delaunay三角网在地理信息系统等领域有着广泛的应用,通常被用于生成不规则三角网(Triangular Irregular Network,TIN)模型,并被用于描述地表的形态.基于传统的逐点插入法,提出一种改进的Delaunay三角网生成算法,通过合理的数据结构与拓扑关系,建立新生成的三角形之间以及点插入前后三角形之间的联系,优化三角形定位过程.首先通过点集凸包生成若干个初始三角形,然后依次插入各点,新点的三角形定位从前一插入点所在的三角形开始,可大幅缩短三角形定位过程的搜索路径,快速定位到新点所在的三角形,当所有点均插入后,最后对整个三角网进行局部优化.实践表明了该算法的高效性和稳定性.     

基于混合DEM数据存储结构的三维地形可视化

为了解决三维地形可视化中的海量数据快速高精度渲染问题,基于创建三维地形所使用的两种主要数字高程模型TIN（Triangulated Irregular Network）和GRID,研究了模型采样点的分布特征、各自优缺点以及存储数据结构,给出了构建混合DEM（Digital Elevation Models）模型的方法,详述了构建混合模型,计算地形复杂度的方法,混合模型的数据结构及三角网生成算法。通过实验说明了混合模型用于三维地形可视化的优势。     

三角网数字地面模型内插法研究

地形表面由一组规则或不规则的分布的采样点组成的矩形或三角形来表示,由于原始采样点的空间分布受到客观条件的限制,往往不能满足显示的需要,这就需要进行内插以产生更多的点,才能使构建的数字地面模型真实的反映地表.基于Delaunay三角网理论,运用格网点的检索、高程内插、沿坡面内插法构建地形特征的数字地面模型,对于不规则离散分布的特征点数据,可以建立各种不规则网的数字地面模型,并通过高程矩阵(Grid)与不规则三角网(TIN)建立数字地面模型的比较,TIN构建数字地面模型的存储量小,速度快,精度高.因此,TIN是表示数字地面模型最简单的、最好的方法.     

基于分治策略的快速构建Delaunay三角网算法

目的降低构建Delaunay三角网的时间复杂度,提高构建Delaunay三角网的速度.方法首先递归分割点集,然后按照构网条件以分割线为轴线对其两侧的点进行构造三角网的操作,直至每个点都被包含进所构建的三角网,最后使其成为Delaunay三角网.结果通过1000~5000个点的测试,表明基于分治策略的快速构建Delaunay三角网的生成速度要快于传统基于分治策略生成Delaunay三角网的速度.结论该方法能够到边建网边优化,使程序一次成型,提高了建网速度,本算法的设计思想还可以推广到三维空间.     

油藏任意约束平面域PEBI网格的生成算法

针对油藏任意约束平面多边形区域提出了一种实用的局部正交化网格（PEBI）生成算法。首先对边界顶点和区域内部散乱点按扫描方式排序，依次扫描各点生成新的三角形，再扫描新生成的三角形中不满足Delaunay准则的三角形，进而不断的处理这些不合理三角形最终完成整个区域的三角网格化，最后连接每个三角彤的外接圆圆心生成PEBI网格。剖分过程中采用了弹性平滑和对角线交换优化方法，很容易实现局部区域的最优化剖分。通过平面映射法就可以应用到油藏的三维PEBI网格剖分，因此本算法具有很好的可操作性和实用性。     

一种基于Graham三角剖分生成Delaunay三角网的算法

目的提出一种基于Graham三角剖分生成Delaunay三角网的算法,加快Delaunay三角网的生成速度.方法首先按Graham扫描法对平面散乱点集进行排序,然后将排好序的点通过可见点的判断连接成Graham三角网,最后利用拓扑结构快速进行优化,使其成为Delaunay三角网.结果通过500至10000个点的测试,表明这种基于Graham三角剖分生成Delaunay三角网的生成速度快于传统基于凸包生成Delaunay三角网的生成速度.结论采用可见点表的数据结构以及利用点、边、三角形的有序性的特点构建Delaunay三角网,是提高建网速度的关键.     

Hybrid Level of Detail Algorithm for Real-Time Rendering of Large-Scale Terrain

Real-ti me rendering of terrain model is one of themost difficult tasks of computer graphics,especiallywhen the scale of a terrain model is very large.LODis ani mportant techniquetoresolvethis problem.Ac-cording to the evolution,there are two kinds ofLOD:…     

大比例尺地形仿真中地形建模与实时绘制技术的研究

大比例尺地形环境仿真以TIN DEM为基础,可精细描述复杂的地形环境,但是在建模、实时绘制以及应用等方面都较以Grid DEM为基础的中小比例尺地形环境仿真更为复杂。文章研究了大比例尺地形环境仿真在建模过程中模型与场景的融合问题及实时绘制中TIN DEM的分块问题最后以实践为基础给出优化设计的实例。     

基于层次块的大地形实时细节合成及渲染算法

为解决渲染真实大地形场景面临的数据获取困难问题,减轻海量地形数据存储与调度的压力,提出了基于层次块实时生成可控的地形细节,完成地形渲染的新方法。采用了层次块结构组织采样数据。给出了基于层次块生成可控细节的方法,使用块网格细分增加采样点,提出了基于Perlin噪声的可控多重分形算法计算细节,保证了生成的细节受真实采样点属性控制。采用统一的细节选择标准完成了细节合成与LOD方法集成,其结果与原始地形块共同构成了动静结合的双层自适应层次结构,实现了视相关的大地形渲染。面向GPU实现了实时合成算法。实验分析表明了该方法能够利用有限的真实地形数据实时产生与实际地形特征相近的细节,完成大地形渲染。     

基于GPU的平滑地形可视化算法

提出了一种基于GPU的平滑地形可视化算法,侧重于解决地形可视化方法面临的时间连续性和空间连续性问题。算法采用了规则地形块的批LOD可视化方法。基于平滑过渡的思想,考虑了地形块相邻层次间的过渡和相邻的不同地形块间的边界匹配关系,以地形块的区域划分为基础,为每个顶点实时分配相应的过渡权值,在地形块的绘制过程中同时完成了不同LOD层次以及不同地形块间的平滑过渡,实现了整个地形的平滑可视化。面向GPU的算法设计与实现保证了其执行效率。针对典型数据集,该算法能够以较高的帧率完成大规模地形的实时平滑漫游,避免可视化过程中的裂缝和突跳等不连续现象。     

一种渐进格网模型的改进算法

多分辨率的动态简化是一种提高地形三维显示速度的重要方法．研究了适用于道路与地形集成模型的多分辨率动态简化方法，分析了渐进格网模型应用于地形集成模型的简化时所存在的一些问题，并根据集成模型的特点。提出了一种改进的算法，与其他方法不同的是：1）此模型采用一种“回”结构的分辨率划分方法，与模型的几何形状无关，较好地实现了道路与地形集成模型的动态简化；2）通过控制顶点树的深度，解决了模型简化后难以恢复的问题，同时避免了在模型简化过程中出现交叉、重叠和细长的三角形．结果表明：该算法能更好地适用于道路与地形集成模型的多分辨率动态简化，并具有较高的速度．     

一种基于顶点移动的三角面模型虚拟切割算法

针对基于面模型的虚拟切割算法中存在的大量畸形三角面片以及运行效率不高等问题,提出了一种基于顶点移动的算法。该算法通过切割轨迹生成、顶点移动以及网格重构等来实现。与传统算法相比,对面数近万的模型,顶点移动算法6次切割运行效率大约提高21%;对面数40余万的复杂模型,运行效率大约提高6%;生成的新面片较为均匀且无畸形。     

基于节点的局部网格生成并行算法

结合基于节点的局部网格生成算法和约束D elaunay路径(CDP)划分区域技术,提出了基于节点的局部网格生成并行算法。使用CDP划分任意给定节点的求解域,能够消除局部网格生成过程中并行处理器间频繁的通讯量,并最大限度地降低了总刚度矩阵生成过程中处理器间的通讯量。文中的并行算法自然实现了网格生成和刚度矩阵计算的无缝连接,从而使基于节点的局部有限元方法的潜在并行效率得到充分展现。数值试验结果表明,该局部网格生成并行算法是有效的、可靠的,尤其当计算大规模的问题时,选取合适的处理器数,并行效率几乎都能达到90%。