面向并行的动态增量式Delaunay三角剖分算法

三角剖分是计算机图形学中的重要话题。并行三角剖分算法的发展对传统三角剖分算法提出了新需求,其中之一即是给定一个点数不断增大的点集,实现对该点集三角剖分的快速增量更新。虽然现今已有一些增量三角剖分算法,但都无法支持新增点落入原有三角剖分之外的情况。为解决此问题,提出了三角剖分的外扩技术,基于插入法设计了增量三角剖分算法TID。该算法能够支持任意次、任意数量、任意位置点的增量添加。TID算法能够对任意分布的点集均给出唯一三角剖分结果。对TID算法的性能评估表明,TID算法比现有算法具有更高的计算效率,且增量功能引入的额外开销较小。此外,该算法已成功作为局地三角剖分算法用于并行三角剖分算法中。     

基于贪心算法与多边形剖分的印鉴匹配算法

将计算几何中平面点集的三角剖分方法之一贪心算法与多边形三角剖分方法引入印鉴匹配,研究了一种基于三角网格(用贪心算法进行平面点集的三角剖分)的印鉴匹配方法.用贪心算法对基于线条的细节点集进行三角剖分,而对于基于多边形的细节点直接进行多边形的三角剖分.通过对两种细节点(基于线条的细节点和基于多边形的细节点)的拓扑结构进行三角划分,把空间上位置相近的细节点按照一定的规则相连,得到三角形网格.然后基于该网格寻找若干参考点对,并根据获得的参考点对将两幅印鉴图像进行姿势调整.最后使用获得的参考点时实现基于点模式的印鉴匹配,经分析该方法是一种行之有效的印鉴识别方法.     

基于FDTD的机载短波天线辐射特性分析

机载天线辐射特性的研究对于机载天线的设计与布局具有重要的意义。机载天线在机身的影响下会改变其原有辐射特性,针对上述问题采用时域有限差分法(FDTD)对机载短波天线的辐射特性进行了分析,并应用FDTD对某型号机载短波天线进行了仿真:使用软件建立整机模型,应用自适应网格对其进行了剖分,设置了PML吸收边界,添加激励并计算得出增益方向图,最后将仿真结果与实测结果进行了比较,二者在天线工作频带内吻合,验证了FDTD对机载天线辐射特性进行分析的有效性与实用性。     

基于凹凸顶点判定的简单多边形的三角剖分

本文提出了一种基于凹凸顶点判定的简单多边形的三角剖分,该算法首先计算简单多边形顶点的凹凸性,然后用环形追踪算法到一个三角剖分,最后通过局部变换得到一个较好的三角剖分。     

一种散乱点云空间直接剖分算法

散乱点云的三角剖分在曲面重建中发挥着重要作用。在对三角剖分基本方法深入分析的基础上对此类点云提出了一种高效的重构算法。本算法将基于动态球策略的搜索算法引入到曲面重建中,源于增量式计算的思想,结合约束准则和设计的顶点度量函数,从基础三角面片开始扩展到覆盖整个物体表面。分析及实验结果表明,该算法能有效地对点云数据进行三角网格化,同时剖分后的三角网格曲面最大限度地保持了原有曲面的特性,证明了提出的基于动态球的曲面重构算法应用于散乱点云曲面重构问题的可行性。     

三维散乱点云快速曲面重建算法

提出了一种基于Delaunay三角剖分的三维散乱点云快速曲面重建算法。算法首先计算点云的Delaunay三角剖分, 从Delaunay四面体提取初始三角网格, 根据Voronoi体元的特征构造优先队列并生成种子三角网格, 然后通过区域生长的方式进行流形提取。实验结果表明, 该算法可以高效、稳定地重构具有复杂拓扑结构、非封闭曲面甚至是非均匀采样的点云数据。与传统的基于Delaunay的方法比较, 该算法仅需要进行一次Delaunay三角剖分, 无须极点的计算, 因此算法的重构速度快。     

适用于电磁场有限元计算的网格剖分算法

网格剖分是有限元法的关键,其剖分得到的网格质量决定了有限元法计算结果的准确性.提出基于Persson-Strang算法生成非结构化三角形网格的新算法.通过分析Laplacian平滑函数作用原理,提出新的平滑函数来减少迭代次数;提出一种在优化设计过程中无重构变形方法,通过定义边界网格框架利用坐标映射技术可以快速推导出网格;通过设置质量评估来解决不可终止性的可能和过度迭代,加入边界节点筛选功能,并对剖分得到的三角元进行有限元逆序编号处理.将该算法与Persson-Strang算法进行剖分效果对比,验证该算法应用于电磁场领域的有效性.     

月面地形重构系统中的并行Delaunay算法设计

三角剖分过程是影响三维重建系统实时性的瓶颈之一,为提高三角剖分速度,基于共享内存多核计算机设计并实现了并行Delaunay算法。该算法在分治三角剖分算法的基础上,通过改进子三角网归并过程及Delaunay三角网优化过程避免了并行计算中的数据竞争问题。利用月面仿真实验场真实地形数据在50万到500万不同规模的点云数据集上进行了实验,加速比最高可达6.44。除此之外,对算法复杂度、加速比以及并行效率进行了全面分析,并将算法实际应用于月面地形重构系统,实现了虚拟地形的快速构建。     

并行分布式体绘制算法的设计

体绘制是一种需要大量计算资源和内存资源的可视化任务，本文提出一种并行分布式体绘制算法，对绘制任务进行适当剖分，使用连网的工作站进行计算，有效地加快了图形绘制速度。     

Delaunay三角剖分并行算法研究及实现

本文通过对Delaunay三角剖分的特性和并行性进行分析,提出了一种基于网格的Delaunay三角剖分并行算法。该算法解决了四点共圆的不唯一性及并行处理边界的任意性问题,在任务分配上较好地保证了负载的均衡,并在分布式环境中成功地实现该算法,有较好的并行效果。     

基于区域分解的并行动态LOD构建算法

面向大规模可视数据的高速绘制问题,提出了一种基于区域分解的并行动态LOD（level-of-detail,层次细节模型）构建算法。算法首先改进了传统的渐进网格方法,实现了基于二次误差测度网格简化算法的渐进网格方法;接着提出了一种基于模型包围盒的区域分解算法,实现了原始模型的自适应区域分解;在每个子区域上,并行地执行渐进网格方法,实现了模型的并行动态LOD构建。实验结果表明,该算法可生成高质量的LOD模型,具备理想的加速比和可扩放性;与串行算法相比,该算法有效地提高了算法的执行效率。     

基于PRAM并行模型最大值查找的方法与改进

随着多处理器的出现,并行技术受到了广泛的关注,成为了加速处理问题速度的重要技术.但是使用并行技术在加速计算的同时也带来了对处理器数量需求的急剧提升,并行成本的显著增加.针对这一问题,通过研究基于PRAM （Parallel Random Access Machine）下的3种最大值查找并行算法中的不足,提出了一种比平衡树算法,快速查找法,双对数深度树方法并行成本（cost）更优的基于数据划分方法的最大值查找并行算法.基于数据划分方法的最大值查找算法有效的解决了现有并行方法中处理器工作量分配不均,对处理器需求过大,实现条件苛刻等问题.为此后类似并行算法降低并行成本提供一个方向.     

数据分布型sort-first并行图形绘制系统的研究与实现

sort-first体系结构常用来构建高性能并行图形绘制系统，基于immediate-mode的数据集中型Sort-first系统，对网络带宽高度依赖，网络带宽和归属计算易成为系统瓶颈,提出了一个基于retain-mode的数据分布型并行绘制系统，工作原理是将几何数据分布于绘制结点，并利用帧间相似性动态调整绘制结点上的数据分布以适应视角的改变，有效地降低了数据分布所需的传输开销，系统利用Cell结构来控制并行粒度，实验结果显示能以相对较低的并行开销实现高分辨率显示和并行加速。     

多层次-跨尺度物理中并行DVM-DAC算法

多尺度现象及相关理论方法是复杂物质系统研究中重要的科学问题.单一的量子力学或分子动力学方法无法解释多尺度体系中存在的现象.第一原理离散变分线性标度（DVM-DAC）算法是一种有效的大尺度体系计算方法.它采用分而治之方案,获得了O（n）的计算复杂性.但由于需要求解大量的特征方程,实现中存在严重的计算瓶颈.发展了一种并行DVM-DAC算法并付诸实现,有效地解决了原有算法的计算瓶颈问题.测试结果表明,并行DVM-DAC算法具有很好的可扩展性,并成功完成104碳纳米管原子体系的计算,为多尺度体系研究提供重要工具.     

高效RSA算法的研究与并行实现

RSA算法依赖于大数的运算,实现起来较为困难,并且对计算机速度、容量等要求较高。针对上述问题,提出一种有效的解决方案,即将大整数分解成小整数进行相乘以提高幂乘运算速度,并给出改进的负载均衡并行算法,进一步提高计算速度。实验结果表明,与传统的RSA算法相比,该算法在计算速度上有明显的提高,具有较好的可扩展性。     

基于联合权重超图划分的SNN负载均衡方法

大规模脉冲神经网络并行模拟是探究大脑机能的重要手段。其难点在于合理地将负载映射到并行分布式平台上,提升模拟速度。为解决该问题,提出一种基于联合权重超图划分的SNN负载均衡方法,解决并行计算中进程间计算负载与通信负载的均衡问题,提高SNN模拟速度。并使用稀疏通信的方式替代集体通信,解决事件通信过程中的数据冗余问题,提升通信效率。实验结果表明,该方法使带有STDP突触20%规模的皮质层微电路模型的模拟时间,比标准循环分配算法缩短约64.5%,比普通超图分配算法缩短约57.4%,同时事件通信数据量减少了90%以上。     

基于Fork/Join框架的等值面快速生成并行算法

针对传统串行等值面提取算法在处理离散点数量多、网格点密度大的数据时生成效率差的问题,提出一种新的基于Fork/Join框架下的等值面快速生成并行算法。通过对传统串行算法中的关键步骤进行并行计算可行性分析,提出可以实施并行计算的四个单独步骤:离散点数据网格化处理、等值点计算、等值线追踪与光滑、等值面标记识别。通过将并行计算作用于等值面生成的这四个步骤中,减少了等值面计算的执行时间,加快了等值面的生成速度。实验结果表明,在数据计算量较大时,与传统串行算法相比,并行算法能在2秒内快速生成等值面,最大加速比高于5.0,提高了等值面的生成效率并取得了良好的绘制效果,满足了高实时性的业务需求。     

一种基于动态分组策略和多线程并行IO的并行镶嵌算法优化

遥感图像的镶嵌处理具有数据量大,流程复杂,算法处理耗时巨大的特点,并行计算是加速镶嵌处理过程速度的有效手段。但是,传统的并行镶嵌算法由于任务分配采用静态策略,导致计算节点负载不均衡,并行效率不高。同时,由于传统并行镶嵌算法中存在大量非常耗时的数据存取操作,并且在重采样和匀色过程中存在不合理的流程配置,使得并行效率降低,难以得到比较线性的加速比。本文提出的基于动态任务分配和多线程并行I/O的并行镶嵌算法,较好地解决了上述问题,通过对比分析和实验表明,本算法对大规模图像的镶嵌处理,具有较好的并行处理速度,以及理想的线性并行加速比曲线,节点扩展能力较强。     

分布并行的分形图像压缩算法

分形图像压缩算法的时间复杂性很大，在单机上受到限制，针对这方面提出的分类方法，基于邻域搜索算法等虽然降低了时间复杂性，但同时也影响了图像的压缩质量，本文把分布并行机制引入分形压缩算法，提出分布并行的自适应四分树分形压缩算法，并在基于Java RMI的分布并行计算系统中加以实现，实验表明可以获得接近计算结点数的加速比。