面向四面体网格生成的Delaunay refinement器官表面重建

为满足生物医学仿真系统对器官几何模型在Delaunay表面重构和四面体建模两方面的需求,提出一种面向四面体网格生成的Delaunay refinement表面重构算法.算法将从医学体数据中经过等值面提取和简化的初始表面作为输入和边界限定条件,为每个限定点计算局部特征尺寸并构建保护球,计算保护球与限定线段的交点并与限定点一起作为初始点集,生成Delaunay辅助四面体网格,引入一个迭代细分过程恢复边界,最终获得Delaunay重构表面.针对细分过程中的收敛性问题,文中给出了详细的理论证明和算法实例.此外,通过Delaunay四面体生成的对比实验表明该算法在Delaunay器官表面重构和四面体建模两方面兼具有效性和优越性.     

3维任意域内点集的Delaunay四面体化研究

Delaunay空球准则广泛应用于3维四面体剖分算法,但标准的Delaunay四面体化只适用于点集的凸包区域,且要求不存在多点共球。为了将Delaunay四面体化更广泛地应用于网络剖分,通过引入局部优化三角形面代替Deluany严格的空球准则,提出了3维任意域内点集Deluanay四面体化(DTETAD)的概念,并首先通过若干关键定理的证明,研究了一个四面体划分是DETEAD的充要条件,然后建立了DTETAD的空球准则。该研究成果为拓展Delaunay算法在更广泛范围的应用提供了理论依据。     

点与三角形位置关系对三角网格拓扑的影响

逐点添加、局部优化的Watson算法和局部变换法是生成大规模离散点集Delaunay三角网格的常用方法。点与三角形位置关系判别和三角形外接圆包含点的测试分别是局部变换法和Watson算法正确生成Delaunay三角网格的重要环节。计算误差会导致点与三角形位置关系以及三角形外接圆包含点的错误判别,从而生成几何拓扑关系不正确的三角网格。采用相对位置坐标可以提高面积坐标和外接圆圆心、半径的计算精度。以等高线地图采集的地形数据为例,用改进的算法生成了包含393252个离散点的Delaunay三角网格。     

基于Voronoi 最小邻近点集的Delaunay 三角化方法

针对局部条件下网格生成的需求,提出一种基于节点的Delaunay 三角化 生成算法,该算法以Delaunay 三角形及其对偶Voronoi 图的局部性特征为基础,通过在局部 搜索最小Voronoi 邻近点集,来生成约束点附近的局部网格,通过建立背景索引网格,来提 高算法效率。给出算法的原理证明、程序实现、效率分析和测试结果,并给出了算法的应用 领域。     

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

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

用随机增量局部转换算法实现三维点集的Delaunay三角剖分

Delaunay三角剖分作为计算几何中的一个核心问题,尤其适用于三维网格生成.因此就需要开发出高效、健壮性的算法来实现.本文在原有算法的基础上提出了随机增量局部转换的算法来实现三维点集的Delaunay三角剖分.采用不退化的四点生成最初的三角剖分,每次加入一点,通过局部交换使新的三角剖分保持Delaunay性质,直到处理完所有点.还讨论了局部交换的思想和对不同面类型的处理方法,给出了两个剖分实例.     

基于符号体积值的Delaunay逐点插入法

传统Delaunay逐点插入法需在全局范围内进行点定位操作,或涉及到面的法向量计算,效率较低。提出一种基于符号体积值的Delaunay逐点插入法。设计简要的数据结构,利用四面体带符号体积值的符号,判断新插入点所在方位,逐步搜索将该新插入点包含在其内部的中心四面体,完成局部范围的点定位;进一步利用体积值符号进行Delaunay空洞可视面测试;对多点共面或共球的退化情况,将点坐标加以细微扰动,提高算法健壮性。实验结果表明,基于符号体积值的Delaunay逐点插入法的点定位操作效率较高,计算量相对减少。     

三维点集Voronoi图的算法实现

对现有三维点集Voronoi图的生成算法进行深入研究，提出并实现由Delaunay三角剖分构建Voronoi图的算法．首先采用随机增量局部转换计算Delaunay三角剖分，然后再根据对偶特性构建Voronoi图．该算法健壮性很高，适用于处理各种非完全共面三维点集．     

局部四面体内点测试三维定位算法

针对现有的三维定位算法过分依赖于锚节点的信息,缺乏网络计算效率和定位精度等问题,提出一种应用于三维无线传感器网络的局部四面体内点测试定位算法。以未知节点为原点建立局部坐标系,获取邻居节点的相对位置关系,选取合适的邻居节点建立局部四面体;通过四面体内点测试方法,找到包含未知节点的四面体;采用质心算法求得未知节点的物理坐标。仿真结果表明,该算法充分利用邻居节点的位置信息,缩小了定位范围,减小了质心定位的误差。     

非均匀三维查找表的快速查找技术

利用四面体插值算法进行色彩校正时，通过样本集直接建立起来的三维查找表往往是不均匀的，为了生成符合ICC规范的Profile，必须通过插值得到均匀的Profile数据。在均匀化过程中，耗时最严重的是如何准确定位插值颜色点所在的四面体。从数据的邻域相关性，除了基于历史的局部搜索法，同时从粗定位和细定位角度提出了基于辅助表的快速定位算法。实验结果证明任何一种加速算法都有效缩短了Profile数据生成的时间，同时结合两种加速算法的效果更佳。     

Incorporating object-centered sampling and Delaunay tetrahedrization for visual hull reconstruction

In this paper we present a novel shape from silhouette algorithm. For an object to be modeled, the algorithm first computes a cloud of points located on a pencil of rays and distributed evenly on the visual hull surface, inside and outside the visual hull. Then Delaunay tetrahedrization is applied to the point cloud to partition its convex hull into a set of tetrahedrons. Finally, outlier tetrahedrons are removed by tetrahedron peeling, and a mesh model of the visual hull is extracted. The algorithm is robust, free from discretization artifacts, and produces a mesh model composed of well-shaped triangles.     

Algebraic solution to forward kinematics of a 3‐DOF spherical parallel manipulator

A three degree‐of‐freedom (3‐DOF) spherical parallel manipulator consists of two tetrahedrons (pyramids). The base tetrahedron is fixed while the moving tetrahedron is rotating at the joint apex of the two tetrahedrons. This article studies the forward kinematics to a special 3‐DOF spherical parallel manipulator, where the three apical angles of the moving tetrahedron are equal to their counterparts in the base tetrahedron, respectively. The final result of the forward kinematics to this parallel manipulator is a univariate quartic polynomial equation, which has a direct algebraic solution. In addition, a special right‐angle case of the manipulator is investigated and its forward kinematics can be obtained directly. © 2001 John Wiley & Sons, Inc.     

一种改进的彩色打印机校正方法

提出一种基于改进的四面体插值技术的校正方法。根据给定点将L*a*b*样本分区,通过比较体积找出包含给定点的体积最小的四面体,利用四面体插值及各顶点信息完成L*a*b*到设备空间的转换。实验过程中对打印机进行校正,采用多项式回归及神经网络等方法与该算法进行比较,结果显示该算法的平均误差小于其他2种算法,可以应用到彩色设备的校正中。     

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

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

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.     

Determining gouge-free ball-end mills for 3D surface machining from point cloud data

This paper presents an algorithm to automatically determine the optimal size of the ball-end milling tool used for the three-axis finish machining of free-form surfaces directly from discrete coordinate data points. The tool is considered optimal if it is of the largest possible diameter that can access every data point without causing an overcut situation or gouging the other data points. Two well-developed techniques in computational geometry, Voronoi diagram and Delaunay triangulation, are used to establish the geometric relationship among data points from which the information required to determine the optimal tool size is extracted. The result of Delaunay triangulation is a set of tetrahedrons, with the data points as vertices, which define a corresponding set of empty circum-spheres. Each data point is a vertex of several tetrahedrons and the largest of the corresponding circum-spheres represents a valid estimation of the optimal tool size at the point. Since the data points are only a sample of the original 3D surface, accuracy of the estimated tool size can be improved by using the approximated normal vector at the data point. The estimated tool size is evaluated by comparing it to its theoretical value. Extensive simulation tests show that a robust and accurate method of determining the optimal ball-end mill size has been developed.     

Reconstruction of 2D polygonal curves and 3D triangular surfaces via clustering of Delaunay circles/spheres

A simple and efficient method is presented in this paper to reliably reconstruct 2D polygonal curves and 3D triangular surfaces from discrete points based on the respective clustering of Delaunay circles and spheres. A Delaunay circle is the circumcircle of a Delaunay triangle in the 2D space, and a Delaunay sphere is the circumsphere of a Delaunay tetrahedron in the 3D space. The basic concept of the presented method is that all the incident Delaunay circles/spheres of a point are supposed to be clustered into two groups along the original curve/surface with satisfactory point density. The required point density is considered equivalent to that of meeting the well-documented r-sampling condition. With the clustering of Delaunay circles/spheres at each point, an initial partial mesh can be generated. An extrapolation heuristic is then applied to reconstructing the remainder mesh, often around sharp corners. This leads to the unique benefit of the presented method that point density around sharp corners does not have to be infinite. Implementation results have shown that the presented method can correctly reconstruct 2D curves and 3D surfaces for known point cloud data sets employed in the literature.     

三维Delaunay三角剖分快速点定位算法研究

提高点定位的速度是提高Delaunay三角剖分运行效率的关键。本文对四面体定位算法进行了研究,结合有向查找定位的技术,建立合理的数据结构,通过对每个搜索四面体只需计算三个面的法向量,优化了基于法向定位的算法,从减少算法中运算量的角度提高运行效率。该算法定位路径唯一,效率更高,而且具有较好的效果。     

医学断层图像三维重建的辅助轮廓线法

在原有的轮廓线基础上生成与之相似的辅助轮廓线．然后把各轮廓线三角化形成一层层的三角面片,最后按一定的规则把各层三角面片从外到内直接连接形成四面体,从而完成三维重构．文中算法尤其适合基于断层轮廓线的医学图象三维重构,与已有的三维重构法（如MC．MT,Delaunay四面体化）相比,具有算法简单、思路自然、易于实现的特点．