离散点集3D三角划分算法在裁剪曲面中的实现

提出一种在3D空间直接对曲面离散数据点进行三角网格划分的算法,该方法适用于非封闭曲面、封闭曲面及多连通复杂曲面的离散点集,同时也能处理剪载曲面的离散点集,得到优良的三角网格。在引入边界环融合的概念的基础上,详细阐述算法如何实现对剪载裁曲面离散点集三角划分,并给出应用实例。     

散乱数据点集的三角划分算法研究

在对当前的三角网格划分方法进行比较分析后，提出了一种散乱数据点集的3D三角网格划分算法，该算法不需如同二维划分方法一样要对散乱点集对应的自由曲面分片投影，并可自然处理含有凹边界及孔域的曲面数据点集，利用网格扩展、边界环分裂和边界环封闭，根据曲面的变化逐层推进生成三角网格，使算法能方便地处理非封闭曲面、空间剪裁曲面、封闭曲面、空间多连通曲面等各种曲面的散乱数据。     

散乱点云的三角划分算法研究

通过对当前的三角网格划分方法进行比较分析,提出了一种散乱点云的3D三角网格划分算法。该算法不需如同二维划分方法那样要对散乱点云对应的自由曲面分片投影,而是直接在3D空间,根据离散点集所对应的曲面形态变化,利用网格扩展、边界环分裂和边界环封闭,逐层收缩生成三角网格。该算法能方便地处理空间多种曲面的散乱点云数据,并且生成的三角网格形态优良,布局合理。     

一种非封闭自由曲面的点云边界提取算法

点云边界不仅作为表达曲面的重要的几何特征,而且作为求解曲面的定义域,对重建曲面模型的品质和精度起着重要的作用.以激光线性均匀扫描的点云数据为例论述了一种改进的空间非封闭自由曲面点云的边界提取方法,在原算法基础上增设阈值,变固定K值为变量K值.实验证明该算法不仅可以较快地提取边界,而且表达曲面边界特征比较精确.     

海量点云曲面增量拓扑重建EI北大核心CSCD

针对现有的曲面重建算法难以兼顾大规模采样数据的重建效率与重建曲面拓扑正确性的问题,提出一种基于局部Delaunay网格剖分的曲面增量重建算法.该算法采用波前扩展的策略,通过波前环的扩张、分裂、重叠面片的消除等步骤,将局部重建过程传播至每个样点的邻近区域,获得插值于采样点集的二维定向流形网格曲面,实现整个采样点集的增量拓扑重建;在曲面局部重建过程中,分别基于局部区域的Cocone算法与二维投影点集的Delaunay网格剖分方法重建曲面的尖锐区域与平坦区域,其中局部区域重建曲面网格的边界的正确性由区域之外的少量辅助样点保护.实验结果表明,文中算法具有较高的重建效率,适用于封闭和非封闭海量点云数据的重建;且在采样密度符合要求的情况下,重建的网格曲面与原表面拓扑同构.     

海量点云曲面增量拓扑重建

针对现有的曲面重建算法难以兼顾大规模采样数据的重建效率与重建曲面拓扑正确性的问题,提出一种基于局部Delaunay网格剖分的曲面增量重建算法.该算法采用波前扩展的策略,通过波前环的扩张、分裂、重叠面片的消除等步骤,将局部重建过程传播至每个样点的邻近区域,获得插值于采样点集的二维定向流形网格曲面,实现整个采样点集的增量拓扑重建;在曲面局部重建过程中,分别基于局部区域的Cocone算法与二维投影点集的Delaunay网格剖分方法重建曲面的尖锐区域与平坦区域,其中局部区域重建曲面网格的边界的正确性由区域之外的少量辅助样点保护.实验结果表明,文中算法具有较高的重建效率,适用于封闭和非封闭海量点云数据的重建;且在采样密度符合要求的情况下,重建的网格曲面与原表面拓扑同构.     

任意三角形网格的基于二元四次箱样条分片C1曲面

提出一种以任意三角剖分为控制网格的二元箱样条曲面算法.二元三方向剖分是方向最少的三角剖分,建立在其上的二元三向四次箱样条在CAGD等领域有着广泛的应用.其规范的箱样条曲面计算仅适用于控制点的价数均为6的网格.从规范的算法出发,提出了一种任意价数控制网格的曲面计算算法,并对算法的连续性等进行了详细的分析.生成的曲面具有保凸性,且是分片C1连续的.该算法可进行3D离散点全局或局部插值,并可应用于3D曲面重构等领域.     

四边形网格划分过程中的边界提取与优化算法的实现

提出一种非封闭曲面的海量空间数据点四边形网格划分过程中的边界优化处理算法和边界快速提取方法;详细论述了边界拟合、边界跳跃、边界分离、边界融合、边界封闭的处理过程;边界点的提取算法,确保边界点提取的正确性,从而避免数据划分过程中带来的数据边界失真现象.给出边界优化处理和边界提取算法的运行实例,说明了算法的可行性.     

任意三角形网格的基于二元四次箱样条分片C1曲面

提出一种以任意三角剖分为控制网格的二元箱样条曲面算法.二元三方向剖分是方向最少的三角剖分,建立在其上的二元三向四次箱样条在CAGD等领域有着广泛的应用.其规范的箱样条曲面计算仅适用于控制点的价数均为6的网格.从规范的算法出发,提出了一种任意价数控制网格的曲面计算算法,并对算法的连续性等进行了详细的分析.生成的曲面具有保凸性,且是分片C¹连续的.该算法可进行3D离散点全局或局部插值,并可应用于3D曲面重构等领域.     

分片驱动的特征敏感曲面重建

为健壮处理包含尖锐特征或欠采样的数据点集,通过对基于边界推进曲面重建技术的扩展,提出一种分片驱动的、特征敏感的对无方向散乱数据点集进行曲面重建的算法.在一个光滑阈值的控制下,将曲面重建过程分成分片重建和特征缝合2个阶段.在分片重建中,从光滑的种子三角化区域开始进行边界推进三角化,并通过拓扑元素分类与特征检测对边界光顺和特征重定位,以进一步扩展该分片,重复该过程,得到对光滑区域三角化的一系列光滑分片;特征缝合阶段,在边界推进过程中将所有分离的分片或分片中的缝隙缝合在特征区域.这种两阶段的三角化策略可有效地处理含尖锐特征或不规则采样如不充分采样的点集,无需保证拓扑完整性的复杂数学测试,如协变分析和三角形相交检测等,基于局部光滑曲面的求交,可有效地恢复采样点集丢失的特征信息.实验结果表明,采用文中算法能健壮处理不规则采样点集,并生成特征敏感的高质量网格.     

Robust uniform triangulation algorithm for computer aided design

This paper presents a new robust uniform triangulation algorithm that can be used in CAD/CAM systems to generate and visualize geometry of 3D models. Typically, in CAD/CAM systems 3D geometry consists of 3D surfaces presented by the parametric equations (e.g. surface of revolution, NURBS surfaces) which are defined on a two dimensional domain. Conventional triangulation algorithms (e.g. ear clipping, Voronoi-Delaunay triangulation) do not provide desired quality and high level of accuracy (challenging tasks) for 3D geometry. The approach developed in this paper combines lattice tessellation and conventional triangulation techniques and allows CAD/CAM systems to obtain the required surface quality and accuracy. The algorithm uses a Cartesian lattice to divide the parametric domain into adjacent rectangular cells. These cells are used to generate polygons that are further triangulated to obtain accurate surface representation. The algorithm allows users to control the triangle distribution intensity by adjusting the lattice density. Once triangulated, the 3D model can be used not only for rendering but also in various manufacturing and design applications. The approach presented in this paper can be used to triangulate any parametric surface given in S(u,v) form, e.g. NURBS surfaces, surfaces of revolution, and produces good quality triangulation which can be used in CAD/CAM and computer graphics applications.     

On mesh-free valley surface extraction with application to low frequency sound simulation

Crease surfaces describe extremal structures of 3D scalar fields. We present a new region-growing-based approach to the meshless extraction of adaptive nonmanifold valley and ridge surfaces that overcomes limitations of previous approaches by decoupling point seeding and triangulation of the surface. Our method is capable of extracting valley surface skeletons as connected minimum structures. As our algorithm is inherently mesh-free and curvature adaptive, it is suitable for surface construction in fields with an arbitrary neighborhood structure. As an application for insightful visualization with valley surfaces, we choose a low frequency acoustics simulation. We use our valley surface construction approach to visualize the resulting complex-valued scalar pressure field for arbitrary frequencies to identify regions of sound cancellation. This provides an expressive visualization of the topology of wave node and antinode structures in simulated acoustics.     

基于曲面局平特性的散乱数据拓扑重建算法

提出了一种基于曲面局平特性的,以散乱点集及其密度指标作为输入,以三角形分片线性曲面作为输出的拓扑重建算法.算法利用曲面的局平特性,从散乱点集三维Delaunay三角剖分的邻域结构中完成每个样点周围的局部拓扑重建,并从局部重建的并集中删除不相容的三角形,最终得到一个二维流形拓扑曲面集作为重建结果.该算法适应于包括单侧曲面在内的任意不自交的拓扑曲面集,并且重建结果是相对优化的曲面三角形剖分,可以应用于科学计算可视化、雕塑曲面造型和反求工程等领域.     

医学图像三维重建中的关键算法

该文主要讨论了基于序列图像的三维重建中的两个关键算法:特征数据点列的重采样算法与三角化算法。把Douglas-Peucker线性简化算法应用在特征边界的重采样上,数据的压缩比得到了明显的改善,也显著地提高了可视化速度。并使用一种简单的三角化算法,对重采样后的数据点列进行三角化,实现目标的三维重建。     

一种基于三维Delaunay三角化的曲面重建算法

提出一种基于三维Delaunay三角化的区域增长式曲面重建方法。该方法以空间点云的Delaunay三角化为基础,结合局部区域增长的曲面构造,较以往方法具有人为参与更少、适用范围更广的优点。算法采用增量式插入点的方式构建空间Delaunay划分,采用广度优先算法,以外接圆最小为准则从Delaunay三角化得到的四面体中抽取出合适的三角片构成曲面。该算法的设计无须计算原始点集的法矢,且孔洞系数对重建的结果影响很小,重建出的三角网格面更符合原始曲面的几何特征。无论待建曲面是否是封闭曲面,本算法均可获得较好的重建效果。     

A highly solid model boundary preserving method for large-scale parallel 3D Delaunay meshing on parallel computers

In this paper, we propose a novel parallel 3D Delaunay triangulation algorithm for large-scale simulations on parallel computers. Our method keeps the 3D boundary representation model information during the whole parallel 3D Delaunay triangulation process running on parallel computers so that the solid model information can be accessed dynamically and the meshing results can be very approaching to the model boundary with the increase of meshing scale. The model is coarsely meshed at first and distributed on CPUs with consistent partitioned shared interfaces and partitioned model boundary meshes across processors. The domain partition aims at minimizing the edge-cuts across different processors for minimum communication cost and distributing roughly equal number of mesh vertices for load balance. Then a parallel multi-scale surface mesh refinement phase is iteratively performed to meet the mesh density criteria followed by a parallel surface mesh optimization phase moving vertices to the model boundary so as to fit model geometry feature dynamically. A dynamic load balancing algorithm is performed to change the partition interfaces if necessary. A 3D local non-Delaunay mesh repair algorithm is finally done on the shared interfaces across processors and model boundaries. The experimental results demonstrate our method can achieve high parallel performance and perfect scalability, at the same time preserve model boundary feature and generate high quality 3D Delaunay mesh as well.     

三维约束Delaunay三角化的研究

概述了约束三角化的研究进展,着重分析了三维约束Ｄｅｌａｕｎａｙ三角化中存在的问题,提出并论证了边界边、边界面片在Ｄｅｌａｕｎａｙ三角化中存在的条件,讨论了存在性条件在实际工程中的应用范围,充实了三维约束Ｄｅｌａｕｎａｙ三角化的研究基础,为三维Ｄｅｌａｕｎａｙ三角化算法的设计提供了理论依据。     

基于八叉树和混合搜索树的地质曲面快速求交方法

为处理地质界面之间的空间相交关系,提出一种新的针对三角地质曲面的快速求交方法。该方法融合优化八叉树法和OBB搜索树方法,可以更快速准确地剔除远离交线的其他三角形。求交剩余的三角形得到交线,应用三角网局部重构和网格优化算法修正交线附近的三角网,最终分割交线两侧的地质曲面,完成2个地质曲面的离散化求交过程。与AABB、OBB和空间分解法相比,该方法在大数据量三角曲面求交中效率优势明显,可以快速准确处理地质模型构建和分析中的曲面求交问题,为三维地质模型自动化构建的实现提供有效支撑。