一种基于剖分与聚类的三维手势建模方法

针对有些建模方法需要设置复杂参数,或所建模型不够平滑、完整,以及出现多余网格等问题,提出了一种基于Delaunay三角剖分与K-Means聚类的三维手势静态建模方法。首先对点云进行半径滤波,再把点云投影在X0Y平面上,然后进行Delaunay三角剖分,对于剖分得到的三角网格中的长边与短边,使用K-Means算法聚为两类,最后删除含有长边的三角面片,得到完整手势的三维模型。实验结果表明,该方法有利于减少多余的网格面,形成的三维手势模型的网格面也较为平滑、完整。     

约束四面体剖分和三维物体表面重建

该文提出了约束曲面和约束最大空球凸多面体的概念,在此基础上设计了一种在空间区域上做约束Delaunay四面体剖分的算法。该算法的基本思路是首先对空间区域进行约束最大空球凸多面体剖分,然后在各个约束最大空球凸多面体内部做Delaunay四面体剖分。利用约束Delaunay四面体剖分算法,该文进一步设计了一种三维物体表面重建算法。     

约束四面体部分和三维物体表面重建

该文提出了约束曲面和约束最大空球凸多面体的概念，在此基础上设计了一种在空间区域上约束Delaunay四面体部分的算法，该算法的基本思路是首先对空间区域进行约束最大空球凸多面体剖分，然后在各个约束最大空球凸多面体内部做Delaunay四面体剖分，利用约束Delaunay四面体剖分算法，该文进一步设计了一种三维物体表面重建算法。     

空间散乱点集Delaunay四面体剖分切割算法

提出最大空圆凸多边形和最大空球凸多面体的概念 .在此基础上 ,提出一种空间散乱点集 Delaunay四面体剖分算法 ,即对空间散乱点集首先进行最大空球凸多面体剖分 ,然后在多面体内部作 Delaunay四面体剖分 .这种方法消除了“退化”现象 (平面 3个以上点共圆或空间 4个以上点共球面 )引起的潜在错误 .最后分析了一类常见的 De-launay四面体剖分算法的潜在错误     

空间散点集Delaunay四面体剖分切割算法

提出最大空圆凸多边形和最大空球凸多面体的概念，在此基础上，提出一种空间散乱点集Delaunay四面体剖分算法，即对空间散乱点集首先进行最大空球凸多面体剖分，然后在多面体内部作Delaunay四面体剖分，这种方法消除了“退化”现象（平面3个以上点共圆或空间4个以上点共球面）引起的潜在错误，最后分析了一类常见的Delaunay四面体剖分算法的潜在错误。     

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

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

Delaunay四面体网格并行生成算法研究进展

纵观近20年国内外Delaunay四面体网格并行生成算法的发展,依据其并行框架分为区域分解模式和基于节点模式,其中区域分解模式根据通信复杂程度进一步分为耦合的和非耦合的;对典型算法中网格质量传承性、串行代码嵌入率、扩展性、负载平衡和容错性等性能进行分析,结合数值测试结果总结了各类模式算法的优缺点.最后,针对各类模式算法的特点探讨了Delaunay四面体网格并行生成技术的发展趋势.     

医学体数据中基于局部特征尺寸的Delaunay四面体化算法*

为了从医学体数据构建面向虚拟手术仿真系统的器官实体模型,提出一种基于局部特征尺寸的Delaunay四面体化算法。首先采用Marching Cubes算法和外存模型简化技术从体数据中得到器官等值面简化模型,提出重心射线法去除内部冗余网格,获得器官多面体表面;然后基于局部特征尺寸构建表面顶点保护球,结合Delaunay细分算法生成边界一致的初始四面体网格;最后提出基于随机扰动的空间分解法快速生成内部节点,并逐点插入到四面体网格中优化单元质量。该算法克服了Delaunay细分算法无法处理锐角输入的缺点,并从理论     

球面凸类图形Delaunay三角剖分再分算法及其收敛性分析

在计算曲面Ricci Flow时,会因为三角网格中存在过小的角而出现不收敛的情况。针对这种不收敛的问题,提出一种提高最小角角度的球面凸类图形Delaunay三角剖分再分算法。首先,给出球面凸类图形Delaunay三角剖分再分算法。它的核心操作有两个：1）如果某条Delaunay劣弧被"侵占",通过添加Delaunay劣弧中点分割Delaunay劣弧;2）如果存在"瘦"球面三角形,通过添加球面三角形外接球面小圆圆心分解球面三角形。然后,利用局部特征尺度探索出所提算法的收敛条件并给出输出顶点的一个上界公式。根据实验输出的网格验证,所提算法网格生成的球面三角形没有狭小的角,适合用来计算Ricci Flow。     

噪声鲁棒的分水岭网格分割算法

提出一种对逆向工程网格噪声鲁棒的分水岭分割算法.该算法在计算网格离散曲率时,针对曲率计算对网格噪声特别敏感的问题,根据拟合曲面的曲面误差估计,动态地调整拟合曲面的顶点个数,提高了曲率计算的精确性,增强了基于曲率的分水岭算法对噪声的鲁棒性;通过后续的标识、聚类和分割后处理方法,提高了算法的分割精度和效果.该算法在大量的噪声网格模型上获得了较好的分割结果,适用于逆向工程中的二次曲面识别和NURBS曲面逼近.     

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.     

基于分类体数据的四面体网格剖分算法

虚拟内窥手术是以真实病人的CT或者MRI扫描数据为基础，首先通过组织分割，在计算机内部建立起三维模型，然后通过虚拟现实技术来模拟窥镜手术全过程的一项技术。其中，人体器官的三维网格建模是该技术中一个十分重要的部分，为了准确地进行了人体器官三维网格建模，在对三维体数据进行组织分割的基础上，提出了一种由分类体数据直接建立三维四面体网格的方法，由于Delaunay三角剖分所产生的网格质量比较高，所以该方法沿用逐点插入算法的思想，以特征点的提取和Steiner布点为基础来生成四面体网格，并通过组织边界的判定准则和利用flip操作来恢复组织边界，实践证明，该方法所生成的网格具有自适应的网格密度。     

复杂非均质地层的等值线生成算法研究

等值线图是复杂油气藏地质研究中的一类重要表示形式。针对地层数据特点,研究和分析了复杂非均质地层数据等值线绘制方法的不足,提出一种新的分区方法,实现了带断层的数据集合划分。基于Delaunay三角剖分算法,并以几何多边形为雏形,建立了带约束的三角网格模型。采用约束Delaunay三角网的拓扑结构,选用改进的反距离加权插值算法,有效地解决了断层两侧高程值问题,并结合实际应用要求在VC++与OpenSceneGraph的开发环境下,实现了非均质带断层的地层等值线的绘制。通过对国内某采油厂的实际油气储集地层数据等值线图的绘制和可视化,证明了方法的可行性和准确性。     

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

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

Delaunay三角剖分在离群点检测中的应用

在传统的基于[K]近邻的算法中,需要为算法设置邻居参数[k]的值,只有具备相关的先验知识才能确定合适的参数值。为了减少参数对于离群点检测的影响,提出了一种无需参数的基于Delaunay三角剖分的离群点检测算法。Delaunay三角剖分是数值分析以及图形学中的重要基础理论,它的构建无需任何参数,在三角剖分图中的每个数据对象与它空间上相邻的点都存在边直接相连,因此可以形成一种有效的邻居关系。算法首先通过Delaunay三角剖分形成每个点的空间邻居集合,然后根据每个点与它们空间邻居之间的分布特征,计算它们的离群程度,根据离群程度的大小判断该点是否为离群点。通过实验与相关的算法比较,算法具有更好的效果。     

Delaunay meshing of isosurfaces

We present an isosurface meshing algorithm, DelIso, based on the Delaunay refinement paradigm. This paradigm has been successfully applied to mesh a variety of domains with guarantees for topology, geometry, mesh gradedness, and triangle shape. A restricted Delaunay triangulation, dual of the intersection between the surface and the three-dimensional Voronoi diagram, is often the main ingredient in Delaunay refinement. Computing and storing three-dimensional Voronoi/Delaunay diagrams become bottlenecks for Delaunay refinement techniques since isosurface computations generally have large input datasets and output meshes. A highlight of our algorithm is that we find a simple way to recover the restricted Delaunay triangulation of the surface without computing the full 3D structure. We employ techniques for efficient ray tracing of isosurfaces to generate surface sample points, and demonstrate the effectiveness of our implementation using a variety of volume datasets.     

平面域上离散点的三角化实现

简单回顾了生成Delaunay三角网的分治算法，逐点插入法，三角网生长法等三类主流算法，提出了一种基于逐点插入思想的快速，有效的分区逐点插入三角化算法，实现了平面域上离散数据点的三角化，网络的优化是在网格生成过程中完成的，生成的网格符合Delaunay准。     

Sketching freeform meshes using graph rotation functions

We present a new approach for sketching free form meshes with topology consistency. Firstly, we interpret the given 2D curve to be the projection of the 3D curve with the minimum curvature. Then we adopt a topology-consistent strategy based on the graph rotation system, to trace the simple faces on the interconnecting 3D curves. With the face tracing algorithm, our system can identify the 3D surfaces automatically. After obtaining the boundary curves for the faces, we apply Delaunay triangulation on these faces. Finally, the shape of the triangle mesh that follows the 3D boundary curves is computed by using harmonic interpolation. Meanwhile our system provides real-time algorithms for both control curve generation and the subsequent surface optimization. With the incorporation of topological manipulation into geometrical modeling, we show that automatically generated models are both beneficial and feasible.     

Automatic mesh generation for complex three-dimensional regions using a constrained Delaunay triangulation

This paper describes a method for generating tetrahedral meshes. The algorithm, based on the Delaunay triangulation, can treat objects of essentially arbitrary complexity. In order to preserve the surface triangulation of solid objects, it is necessary to override the Delaunay property and redefine the triangulation when points are introduced that are close to solid boundaries. Details of this constrained Delaunay algorithm are presented and an efficient implementation of the triangulation method is described. Techniques for controlling the distribution of mesh points and tetrahedron quality are also discussed.     

基于Delaunay三角剖分密度度量的聚类算法

针对K-means聚类算法无法正确识别非凸形状簇的缺陷,提出一种基于Delaunay三角剖分密度度量的聚类方法,利用Delaunay三角剖分图的最近性、邻接性等优良特性来反映数据自身特点并进行密度度量,同时以混沌优化方法实现聚类目标函数的全局优化,达到全局最小解。实验结果证明,基于Delaunay三角剖分密度度量方式的聚类算法能发现任意非凸形状簇。