一种无记忆点云迭代简化算法

针对目前点云迭代简化算法在简化过程中需要保持原始模型信息而占用较大内存的问题,提出了一种无记忆点云迭代简化算法,简化过程中不需要记录原始模型相关几何信息。该算法使用体积优化和距离优化计算点对收缩后的最优点位置并对点对进行排序。实验表明,该算法可以在内存占用较小的情况下得到误差较小的简化模型。     

保持特征的点云迭代简化算法

提出了一种特征保持的三维点云迭代简化算法。首先对点云模型构造KD树结构,计算采样点的k邻域,然后利用点云模型的局部几何信息作为参数,包括局部采样密度、采样点的精度和曲率,计算评估函数值,迭代删除评估函数值最小的点。实验结果表明,算法在简化点云数据的同时,能有效去除噪声数据,而且很好地保留了原始模型的特征信息。     

特征保持的点模型简化技术研究

提出一种以物体表面上不附加任何几何和拓扑信息的散乱点集为处理对象,特征保持的点云数据简化的方法。通过直接在散乱点上计算曲率的方法,将数据点分为特征点和非特征点两类,分别应用不同参数的均值漂移聚类算法进行简化。实验结果表明算法既能有效简化点云数据,而且很好地保留了原网格模型的特征信息。     

基于均值漂移聚类的点模型简化方法

为了有效简化稠密采样点模型,提出了一个基于均值漂移（mean shift）聚类的点模型简化方法。通过mean shift迭代过程,计算点模型中点对应的局部模式点,即模态点。利用模态点代替聚集在其周围的数据点,实现对模型的简化。实验结果表明该算法能有效减少稠密采样点模型的点数,且简化速度较快,简化模型能很好地保持原始模型的几何形状。     

基于散乱点云加权邻域采样点的简化算法

提出一种基于散乱点云的邻域采样点数目加权的聚类简化算法,此算法以曲面变化度和聚类中采样点的数目加权共同进行阈值控制,能够在简化过程中更偏向于将包含采样点数比较多且有一定曲率的聚类进行划分,得到更合理的简化效果。     

保特征的点云骨架提取算法

三维模型的骨架提取是计算机图形学中一个重要的研究方向。对于有噪声的点云模型,曲线骨 架提取的难点在于保持正确的拓扑结构以及良好的中心性;对于无噪声的点云模型,曲线骨架提取的难点在于 对模型细节特征的保留。目前主流的点云骨架提取方法往往无法同时解决这 2 个难点。算法在最优传输理论的 基础之上结合聚类的思想,将点云骨架提取的问题转化为一个最优化问题。首先使用最优传输得到原始点云与 采样点云之间的传输计划。然后使用聚类的思想将原始点云进行分割,采样点即成为了簇的中心。接着通过簇 与簇之间的调整与合并减少聚类个数,优化聚类结果。最后通过迭代的方式得到粗糙的骨架并使用插点操作进 行优化。大量实验结果表明,该算法在有噪声与无噪声的三维点云模型上均能提取出质量良好的曲线骨架并保 留模型的特征。     

基于点重要性判断的点云简化

为了有效保持散乱点云的显著几何特征,提高点云简化的精度和效率,提出一种点重要性判断点云简化方法.首先,计算点云中点的重要性,并根据重要性提取特征点;然后,采用八叉树算法对非特征点进行简化,从而保留点云的主要细节特征,实现点云简化处理;最后,通过对公共点云和文物点云数据模型的简化实验来验证该点云简化方法.结果表明,该点重要性判断点云简化方法可以在有效保持点云细节几何特征的同时,实现点云的有效简化,是一种快速、高精度的点云简化方法.     

应用遗传模糊聚类实现点云数据区域分割

为了准确地实现点云数据的区域分割,将基于遗传算法的模糊聚类算法应用于逆向工程中的点云数据区域分割中。首先估算出法矢量、高斯曲率和平均曲率,并与坐标一起组成八维特征向量,用加权距离代替欧氏距离,然后通过遗传算法获得全局最优解的近似解;最后将近似解作为模糊聚类的初始解进行迭代,实现点云数据的区域分割,从而避免传统FCM算法的局部性和对初始解的敏感性,减少了迭代次数。以汽车钣金件为例,证明了应用遗传模糊聚类实现点云数据区域分割的有效性,并验证了该方法能快速、准确地实现点云数据的区域分割。     

近似刚性的快速点云变形算法

针对大规模的复杂点云模型,提出了一种非线性变形算法.通过保持局部邻域的刚性使得点云模型进行近似刚性的变形,在大尺度变形时有效地保持几何细节和体积;为了保证求解过程的收敛性,对原始点云进行聚类,快速生成其简化点云,进而在稀疏的简化点云上完成变形,并将该变形作用给原始点云以得到合理的初始结果.此外,还给出一种动态重采样方法,以消除变形造成的冗余点和裂缝.实验结果和对比数据表明,文中算法简单高效,能够防止几何细节的扭曲和明显的体积变化,获得了令人满意的变形效果.     

点模型的面元简化方法

为有效地简化稠密采样点模型,提出了一种基于面元（surfel）重建的点模型简化方法。该算法首先对每个采样点面元的初始半径进行估算,并同时根据曲率的变化确定每个面元的简化权值;然后采用surfel合并的方法来聚合、减少surfel图元的数量,按照计算的surfel权值,确定surfel合并的顺序,合并并重建成一个新的surfel,合并过程中判断误差是否满足要求,满足则合并成功。如此迭代,直到surfel合并引起的误差达到阈值或surfel权值达到某个给定值。实验结果表明该算法能有效减少稠密采样点模型的点数,且在相同误差控制下简化率高于一般的基于纯采样点的简化算法;同时,简化模型能很好地保持原始模型的几何形状,防止简化后表面空洞现象的产生。     

基于细节迁移的快速外存模型简化方法

现有的快速外存模型简化方法一般是对模型进行近似均匀采样,无法根据细节分布对模型进行不同程度的简化,从而对于细节分布非均匀的模型失真较大.给出一种快速的外存模型简化方法,用于对无法一次装入内存的大型几何模型进行简化,大大改善了细节分布非均匀的模型的简化结果.该方法首先均匀采样,对外存模型快速生成初始简化模型,生成的同时计算原模型特征的统计信息,然后依此对初始简化模型进行细节迁移和局部精细采样.该方法在保持近似线性处理速度的同时,大大提高了简化模型的质量,所需的内存空间也非常小.     

自适应K-means聚类的散乱点云精简

目的 点云精简是曲面重建等点云处理的一个重要前提,针对以往散乱点云精简算法的精简结果存在失真较大、空洞及不适用于片状点云的问题,提出一种自适应K-means聚类的点云精简算法。方法 首先,根据k邻域计算每个数据点的曲率、点法向与邻域点法向夹角的平均值、点到邻域重心的距离、点到邻域点的平均距离,据此运用多判别参数混合的特征提取方法识别并保留特征点,包括曲面尖锐点和边界点;然后,对点云数据建立自适应八叉树,为K-means聚类提供与点云密度分布相关的初始化聚类中心以及K值;最后,遍历整个聚类,如果聚类结果中含有特征点则剔除其中的特征点并更新聚类中心,计算更新后聚类中数据点的最大曲率差,将最大曲率差大于设定阈值的聚类进行细分,保留最终聚类中距聚类中心最近的数据点。结果 在聚类方面,将传统的K-means聚类和自适应K-means聚类算法应用于bunny点云,后者在聚类的迭代次数、评价函数值和时间上均优于前者;在精简方面,将提出的精简算法应用于封闭及片状两种不同类型的点云,在精简比例为1/5时fandisk及saddle模型的精简误差分别为0.29×10^-3、-0.41×10^-3和0.037、-0.094,对于片状的saddle点云模型,其边界收缩误差为0.030 805,均小于栅格法和曲率法。结论 本文提出的散乱点云精简算法可应用于封闭及片状点云,精简后的数据点分布均匀无空洞,对片状点云进行精简时能够保护模型的边界数据点。     

改进顶点聚类方法的并行核外模型简化算法

面向大型网格模型的简化问题,提出了一种基于顶点聚类方法采用多数据流策略的并行核外模型简化算法。算法首先将传统顶点聚类简化算法中的代表点计算方法改进为顶点筛选方法,进而设计了一种适用于分布式计算环境的数据外存储策略,最后采用多数据流的思想改进单元筛选与顶点筛选两个方法的执行过程,从而形成完整的并行核外模型简化算法。实验结果表明,该算法有效避免了基于区域分解的并行算法对模型结构的破坏,提高了模型简化的质量;相比于多种现有的并行算法,该算法极大程度优化了并行资源的负载分配问题,具备更为理想的加速比和并行效率。     

局部特征熵的网格非均匀简化算法

针对三维模型简化后的精度与效率上难以平衡的问题进行研究,提出一种局部特征熵的半边折叠非均匀网格简化算法。采用两次局部区域聚类探测,首先探测三维数据点所在边聚类局部区域,获取该探测区域法向量,其次以三维数据点临近点区域的重心约束来探测二次聚类区域法向量;根据信息熵的定义利,用两次探测的法向量之间夹角信息构建局部区域特征熵值做为半边折叠的代价,局部区域特征熵越大表示该区域越趋于平面,应优先简化,否则当保留;最后采用三角形内角判断方法来保留简化后网格中三角形的正则度,以减小变形引起的误差。实验结果表明,本算法在三维模型分均匀简化中在局部细节特性精度上和时间效率上能达到较优的平衡。     

Graph matching and clustering using spectral partitions

Although inexact graph-matching is a problem of potentially exponential complexity, the problem may be simplified by decomposing the graphs to be matched into smaller subgraphs. If this is done, then the process may cast into a hierarchical framework and hence rendered suitable for parallel computation. In this paper we describe a spectral method which can be used to partition graphs into non-overlapping subgraphs. In particular, we demonstrate how the Fiedler-vector of the Laplacian matrix can be used to decompose graphs into non-overlapping neighbourhoods that can be used for the purposes of both matching and clustering.     

非均匀抽样网格简化

提出了一种考虑视点空间中某些重要视点的非均匀抽样网格简化的新方法,是在借鉴了Garland-Heckbert方法的基础上提出的,是一种考虑外观相似性的简化算法。给出并证明了两个判定边界的定理,为抽样提供了理论依据。在简化过程中,该算法通过采用视点空间中某些重要视点对模型进行抽样,使抽中的顶点对（轮廓附近的顶点对）得到适当保护。该算法除具有Garland-Heckbert方法的长处外,还可以在三角面片数较少的情况下（50多个三角面片）,尽可能保持模型的重要外观特征,给出了计算0－1图像的外观相似性误差的公式,通过该公式对简化结果进行比较,证明提出的简化算法对保持模型的外观特征是行之有效的。最后对该算法的时间和空间复杂性进行了分析。     

OFDM中继系统的传输策略选择与资源分配

提出传输策略选择结合资源分配的迭代算法,证明其收敛性。进一步将算法简化为顺序进行的三步：子信道指配,传输策略选择和中继的发射功率分配,源的发射功率分配。仿真结果表明,所提资源分配迭代方案和简化方案的频谱效率性能均优于已有的两种资源分配方案,简化方案更适合实际应用。     

Manifold-guaranteed out-of-core simplification of large meshes with controlled topological type

In this paper, a simple and efficient algorithm is proposed for manifold-guaranteed out-of-core simplification of large meshes with controlled topological type. By dual-sampling the input large mesh model, the proposed algorithm utilizes a set of Hermite data (sample points with normals) as an intermediate model representation, which allows the topological structure of the mesh model to be encoded implicitly and thus makes it particularly suitable for out-of-core mesh simplification. Benefiting from the construction of an in-core signed distance field, the proposed algorithm possesses a set of features including manifoldness of the simplified meshes, toleration of nonmanifold mesh data input, topological noise removal, topological type control and, sharp features and boundary preservation. A novel, detailed implementation of the proposed algorithm is presented, and experimental results demonstrate that very large meshes can be simplified quickly on a low-cost off-the-shelf PC with tightly bounded approximation errors and with time and space efficiency.     

Mesh-driven vector field clustering and visualization: an image-based approach

Vector field visualization techniques have evolved very rapidly over the last two decades, however, visualizing vector fields on complex boundary surfaces from computational flow dynamics (CFD) still remains a challenging task. In part, this is due to the large, unstructured, adaptive resolution characteristics of the meshes used in the modeling and simulation process. Out of the wide variety of existing flow field visualization techniques, vector field clustering algorithms offer the advantage of capturing a detailed picture of important areas of the domain while presenting a simplified view of areas of less importance. This paper presents a novel, robust, automatic vector field clustering algorithm that produces intuitive and insightful images of vector fields on large, unstructured, adaptive resolution boundary meshes from CFD. Our bottom-up, hierarchical approach is the first to combine the properties of the underlying vector field and mesh into a unified error-driven representation. The motivation behind the approach is the fact that CFD engineers may increase the resolution of model meshes according to importance. The algorithm has several advantages. Clusters are generated automatically, no surface parameterization is required, and large meshes are processed efficiently. The most suggestive and important information contained in the meshes and vector fields is preserved while less important areas are simplified in the visualization. Users can interactively control the level of detail by adjusting a range of clustering distance measure parameters. We describe two data structures to accelerate the clustering process. We also introduce novel visualizations of clusters inspired by statistical methods. We apply our method to a series of synthetic and complex, real-world CFD meshes to demonstrate the clustering algorithm results.     

一种基于包络控制的三角形收缩简化三维几何模型的新算法

本文算法先将原始模型上的每一点沿各自的法矢量方向偏移一定的距离，使整个原始模型收缩或扩张，生成内外两层包络．在构造包络时采用了一维搜索中的二分法来逼近最佳偏移值，以保证原始模型尽可能简化，然后依次选择原始模型上的一些三角形，将其三个顶点合并，收缩成一个三雏点．如果这样收缩简化后的模型依然位于两层包络围成的空间中．则收缩操作产生的误差被认为是可接受的．这也就保证了简化模型与原始模型外形上的相似．同时，本文还设计了一个演示系统，实现了这种算法．实验结果表明．通过这种算法简化三维几何模型后，简化模型不仅具有一定的压缩率，而且保留了原始几何模型的尖锐特征，两者在外形上十分相似。