Efficient representation and extraction of 2-manifold isosurfaces using kd-trees

In this paper, we propose the utilization of a kd-tree based hierarchy as an implicit object representation. Compared to an octree, the kd-tree based hierarchy is superior in terms of adaptation to the object surface. In consequence, we obtain considerably more compact implicit representations especially in case of thin object structures. We describe a new isosurface extraction algorithm for this kind of implicit representation. In contrast to related algorithms for octrees, it generates 2-manifold meshes even for kd-trees with cells containing multiple surface components. The algorithm retains all the good properties of the Dual Contouring approach by Ju et al. [ACM Trans. Graphics 21 (2002) 339–346] like feature preservation, computational efficiency, etc. In addition, we present a simplification framework for the surfaces represented by the kd-tree based on quadric error metrics. We adapt this framework to quantify the influence of topological changes, thereby allowing controlled topological simplification of the object. The advantages of the new algorithm are demonstrated by several examples.     

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.     

Sliver-free perturbation for the Delaunay tetrahedrization

This paper studies symbolic perturbation schemes in the context of Delaunay meshing in the three-dimensional space. Symbolic perturbation is a general and powerful technique for removing geometric degeneracy. However, a straightforward application of this technique to Delaunay meshing does not work well, because the perturbation generates volume-zero tetrahedra, called slivers, which should not appear in meshes for the finite element method.First we characterize the set of directions in which a point can be perturbed without generating slivers. Next, as an application of this characterization, we construct a graph-theoretic method for finding a sliver-free perturbation. We also show that an ordinary symbolic perturbation cannot avoid slivers for integer-grid points, and point out that there is a generalized type of perturbation that can avoid slivers completely.     

二维复杂限定Delaunay三角化算法

针对包括曲线边界和内部带有曲线限定条件的二维Delaunay三角化问题,提出了一种细化算法.首先给出了曲线段的逼近边定义,以保证限定曲线在网格中的存在;然后证明了该算法的收敛性和最终曲线的逼近边集合与原曲线的拓扑一致性,并且生成的网格符合Delaunay优化准则;最后给出了算法的应用实例,验证了其有效性.     

On generating topologically consistent isosurfaces from uniform samples

A set of sample points of a function of three variables may be visualized by defining an interpolating functionf of the samples and examining isosurfaces of the formf(x, y, z)=t for various values oft. To display the isosurfaces on a graphics device, it is desirable to approximate them with piecewise triangular surfaces that (a) are geometrically good approximations, (b) are topologically consistent, and (c) consist of a small number of triangles. By topologically consistent we mean that the topology of the piecewise triangular surface matches that of the surfacef(x, y, z)=t, i.e., the interpolantf determines both the geometry and the topology of the piecewise triangular surface. In this paper we provide an efficient algorithm for the case in whichf is the piecewise trilinear interpolant; for this case existing methods fail to satisfy all three of the above conditions simultaneously.     

Two and three-quarter dimensional meshing facilitators

This paper presents generated enhancements for robust two and three-quarter dimensional meshing, including: (1) automated interval assignment by integer programming for submapped surfaces and volumes, (2) surface submapping, and (3) volume submapping. An introduction to the simplex method, an optimization technique of integer programming, is presented. Simplification of complex geometry is required for the formulation of the integer programming problem. A method of i-j unfolding is defined which explains how irregular geometry can be realigned into a simplified form that is suitable for submap interval assignment solutions. Also presented is the processes by which submapping eliminates the decomposition of surface geometry, through a pseudodecomposition process, producing suitable mapped meshes. The process of submapping involves the creation of interpolated virtual edges, user defined vertex types and i-j-k space traversals. The creation of interpolated virtual edges is the method by which submapping automatically subdivides surface geometry. The interpolated virtual edge is formulated according to an interpolation scheme using the node discretization of curves on the surface. User defined vertex types allow direct user control of surface decomposition and interval assignment by modifying i-j-k space traversals. Volume submapping takes the geometry decomposition to a higher level by using mapped virtual surfaces to eliminate decomposition of complex volumes.     

A multigrain Delaunay mesh generation method for multicore SMT-based architectures

Given the proliferation of layered, multicore- and SMT-based architectures, it is imperative to deploy and evaluate important, multi-level, scientific computing codes, such as meshing algorithms, on these systems. We focus on Parallel Constrained Delaunay Mesh (PCDM) generation. We exploit coarse-grain parallelism at the subdomain level, medium-grain at the cavity level and fine-grain at the element level. This multi-grain data parallel approach targets clusters built from commercially available SMTs and multicore processors. The exploitation of the coarser degree of granularity facilitates scalability both in terms of execution time and problem size on loosely-coupled clusters. The exploitation of medium-grain parallelism allows performance improvement at the single node level. Our experimental evaluation shows that the first generation of SMT cores is not capable of taking advantage of fine-grain parallelism in PCDM. Many of our experimental findings with PCDM extend to other adaptive and irregular multigrain parallel algorithms as well.     

High-order curvilinear meshing using a thermo-elastic analogy

With high-order methods becoming increasingly popular in both academia and industry, generating curvilinear meshes that align with the boundaries of complex geometries continues to present a significant challenge. Whereas traditional low-order methods use planar-faced elements, high-order methods introduce curvature into elements that may, if added naively, cause the element to self-intersect. Over the last few years, several curvilinear mesh generation techniques have been designed to tackle this issue, utilizing mesh deformation to move the interior nodes of the mesh in order to accommodate curvature at the boundary. Many of these are based on elastic models, where the mesh is treated as a solid body and deformed according to a linear or non-linear stress tensor. However, such methods typically have no explicit control over the validity of the elements in the resulting mesh. In this article, we present an extension of this elastic formulation, whereby a thermal stress term is introduced to ‘heat’ or ‘cool’ elements as they deform. We outline a proof-of-concept implementation and show that the adoption of a thermo-elastic analogy leads to an additional degree of robustness, by considering examples in both two and three dimensions.     

Topology design of three-dimensional continuum structures using isosurfaces

Isolines Topology Design (ITD) is an iterative algorithm for the topological design of two-dimensional continuum structures using isolines. This paper presents an extension to this algorithm for topology design of three-dimensional continuum structures. The topology and the shape of the design depend on an iterative algorithm, which continually adds and removes material depending on the shape and distribution of the contour isosurfaces for the required structural behaviour. In this study the von Mises stress was investigated. Several examples are presented to show the effectiveness of the algorithm, which produces final designs with very detailed surfaces without the need for interpretation. The results demonstrate how the ITD algorithm can produce realistic designs by using the design criteria contour isosurface.     

Certified meshing of Radial Basis Function based isosurfaces

Radial Basis Functions are widely used in scattered data interpolation. The surface-reconstruction method using radial basis functions consists of two steps: (i) computing an interpolating implicit function the zero set of which contains the points in the data set, followed by (ii) extraction of isocurves or isosurfaces. In this paper we focus on the second step, generalizing the work on certified meshing of implicit surfaces based on interval arithmetic (Plantinga and Vegter in Visual Comput. 23:45–58, 2007). It turns out that interval arithmetic, and even the usually faster affine arithmetic, are far too slow in the context of RBF-based implicit surface meshing. We present optimized strategies giving acceptable running times and better space complexity, exploiting special properties of RBF-interpolants. We present pictures and timing results confirming the improved quality of these optimized strategies.     

Complex conforming Delaunay triangulation

A novel algorithm of conforming Delaunay triangulation for curved geometry is presented in the paper.A progress has been made for the problem puzzled Delaunay refinement where curved constraints cannot be accepted as input directly.The algorithm is based on a new sufficient condition for the existence of constraints in triangulation.It requires computing only the intersection between constraints and Voronoi edges or faces instead of the circum-sphere of curved constraint.For the termination of the algorithm...     

构造最优Delaunay三角剖分的拓扑优化方法

最优Delaunay三角剖分(ODT)是生成区域网格剖分的一种优化方法.从数值优化的角度来看,现有的ODT优化方法属于局部方法,对于任意给定初值容易陷入较差的局部极小值点,从而不能产生高质量网格.为此提出一种简单的拓扑优化方法,使得ODT方法能有效地从局部极小值点中跳出,进一步提高网格的质量.该方法只涉及到局部的边翻转操作,实现简单;而且具有显式的目标函数,能在理论上保证算法的收敛性.实验结果表明,文中算法运行速度快,不论是在拓扑连接关系还是在三角形的形状上都显著地提高了ODT方法生成的网格质量.     

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.     

Parallel divide‐and‐conquer scheme for 2D Delaunay triangulation

This work describes a parallel divide‐and‐conquer Delaunay triangulation scheme. This algorithm finds the affected zone, which covers the triangulation and may be modified when two sub‐block triangulations are merged. Finding the affected zone can reduce the amount of data required to be transmitted between processors. The time complexity of the divide‐and‐conquer scheme remains O(n log n), and the affected region can be located in O(n) time steps, where n denotes the number of points. The code was implemented with C, FORTRAN and MPI, making it portable to many computer systems. Experimental results on an IBM SP2 show that a parallel efficiency of 44–95% for general distributions can be attained on a 16‐node distributed memory system. Copyright © 2006 John Wiley & Sons, Ltd.     

面向共享内存结构的并行Delaunay网格生成算法

针对目前大多数并行Delaunay网格生成算法对共享内存结构利用不充分,不能够利用超级计算机多层次体系结构优势的情况,提出了一种充分利用共享内存结构的基于算法并行模式的并行Delaunay网格生成算法。通过对候选点集进行高效划分来实现插点操作的并行,增大了一次选择之后进行并行插点的点集规模。使用OpenMP并行模型对所提出算法进行并行实现,并和串行开源软件Triangle进行了对比。实验结果表明算法能够将候选点集划分成互不冲突的子集进行并行处理,在保证网格质量的同时具有较好的并行效率。     

Generalizing the advancing front method to composite surfaces in the context of meshing constraints topology

Being able to automatically mesh composite geometry is an important issue in the context of CAD–FEA integration. In some specific contexts of this integration, such as using virtual topology or meshing constraints topology (MCT), it is even a key requirement. In this paper, we present a new approach to automatic mesh generation over composite geometry. The proposed mesh generation approach is based on a generalization of the advancing front method (AFM) over curved surfaces. The adaptation of the AFM to composite faces (composed of multiple boundary representation (B-Rep) faces) involves the computation of complex paths along these B-Rep faces, on which progression of the advancing front is based. Each mesh segment or mesh triangle generated through this progression on composite geometry is likely to lie on multiple B-Rep faces and consequently, it is likely to be associated with a composite definition across multiple parametric spaces. Collision tests between new front segments and existing mesh elements also require specific and significant adaptations of the AFM, since a given front segment is also likely to lie on multiple B-Rep faces. This new mesh generation approach is presented in the context of MCT, which requires being able to handle composite geometry along with non-manifold boundary configurations, such as edges and vertices lying in the interior domain of B-Rep faces.     

Point placement algorithms for Delaunay triangulation of polygonal domains

In some applications of triangulation, such as finite-element mesh generation, the aim is to triangulate a given domain, not just a set of points. One approach to meeting this requirement, while maintaining the desirable properties of Delaunay triangulation, has been to enforce the empty circumcircle property of Delaunay triangulation, subject to the additional constraint that the edges of a polygon be covered by edges of the triangulation. In finite-element mesh generation it is usually necessary to include additional points besides the vertices of the domain boundary. This motivates us to ask whether it is possible to trinagulate a domain by introducing additional points in such a manner that the Delaunay triangulation of the points includes the edges of the domain boundary. We present algorithms that given a multiply connected polygonal domain withN vertices, placeK additional points on the boundary inO(N logN + K) time such that the polygon is covered by the edges of the Delaunay triangulation of theN + K points. Furthermore,K is the minimum number of additional points such that a circle, passing through the endpoints of each boundary edge segment, exists that does not contain in its interior any other part of the domain boundary. We also show that by adding only one more point per edge, certain degeneracies that may otherwise arise can be avoided.     

基于可见性约束的自动表面重构算法研究

提出了一种基于可见性约束的自动表面重构算法.此算法首先介绍了一种通过插入法实现的3维Delaunay三角网自动重构算法,然后利用给定的离散点,构建包围所有点的凸包.在完成初始的Delaunay三角剖分基础上,提出了利用特征点在影像中的可见性信息,对初始的3维模型进行修正,从而得到物体的实际表面模型.实验结果表明,该方法是有效的.     

三维约束Delaunay三角化的实现

分析了约束Delaunay三角化中存在的边界一致性问题,给出了约束Delaunay三角化的理论依据,重点探讨了三维约束Delaunay三角化的可行性条件和范围,同时,给出了三维有限域约束Delaunay三角化的实现方法及其在石油地质勘探数据和机械零件方面的网格剖分实例.这种算法在复杂对象的科学计算和工程分析中发挥了重要作用.     

KMAS网格自动生成系统

KMAS网格自动生成系统采用超限插值法和Delaunay三角剖分法,可对一般复杂覆盖件自动快速生成三角形或混合型有限元网格,网格质量较好,速度较快,还可根据用户需要消除孔洞,适合冲压分析的需要。