Feature Preserving Mesh Generation from 3D Point Clouds

We address the problem of generating quality surface triangle meshes from 3D point clouds sampled on piecewise smooth surfaces. Using a feature detection process based on the covariance matrices of Voronoi cells, we first extract from the point cloud a set of sharp features. Our algorithm also runs on the input point cloud a reconstruction process, such as Poisson reconstruction, providing an implicit surface. A feature preserving variant of a Delaunay refinement process is then used to generate a mesh approximating the implicit surface and containing a faithful representation of the extracted sharp edges. Such a mesh provides an enhanced trade‐off between accuracy and mesh complexity. The whole process is robust to noise and made versatile through a small set of parameters which govern the mesh sizing, approximation error and shape of the elements. We demonstrate the effectiveness of our method on a variety of models including laser scanned datasets ranging from indoor to outdoor scenes.     

Feature preserving Delaunay mesh generation from 3D multi-material images

Generating realistic geometric models from 3D segmented images is an important task in many biomedical applications. Segmented 3D images impose particular challenges for meshing algorithms because they contain multi-material junctions forming features such as surface patches, edges and corners. The resulting meshes should preserve these features to ensure the visual quality and the mechanical soundness of the models. We present a feature preserving Delaunay refinement algorithm which can be used to generate high-quality tetrahedral meshes from segmented images. The idea is to explicitly sample corners and edges from the input image and to constrain the Delaunay refinement algorithm to preserve these features in addition to the surface patches. Our experimental results on segmented medical images have shown that, within a few seconds, the algorithm outputs a tetrahedral mesh in which each material is represented as a consistent submesh without gaps and overlaps. The optimization property of the Delaunay triangulation makes these meshes suitable for the purpose of realistic visualization or finite element simulations.     

Efficient and good Delaunay meshes from random points

We present a Conforming Delaunay Triangulation (CDT) algorithm based on maximal Poisson disk sampling. Points are unbiased, meaning the probability of introducing a vertex in a disk-free subregion is proportional to its area, except in a neighborhood of the domain boundary. In contrast, Delaunay refinement CDT algorithms place points dependent on the geometry of empty circles in intermediate triangulations, usually near the circle centers. Unconstrained angles in our mesh are between 30° and 120°, matching some biased CDT methods. Points are placed on the boundary using a one-dimensional maximal Poisson disk sampling. Any triangulation method producing angles bounded away from 0° and 180° must have some bias near the domain boundary to avoid placing vertices infinitesimally close to the boundary.Random meshes are preferred for some simulations, such as fracture simulations where cracks must follow mesh edges, because deterministic meshes may introduce non-physical phenomena. An ensemble of random meshes aids simulation validation. Poisson-disk triangulations also avoid some graphics rendering artifacts, and have the blue-noise property.We mesh two-dimensional domains that may be non-convex with holes, required points, and multiple regions in contact. Our algorithm is also fast and uses little memory. We have recently developed a method for generating a maximal Poisson distribution of n output points, where n=Θ(Area/r²) and r is the sampling radius. It takes O(n) memory and O(nlogn) expected time; in practice the time is nearly linear. This, or a similar subroutine, generates our random points. Except for this subroutine, we provably use O(n) time and space. The subroutine gives the location of points in a square background mesh. Given this, the neighborhood of each point can be meshed independently in constant time. These features facilitate parallel and GPU implementations. Our implementation works well in practice as illustrated by several examples and comparison to Triangle.     

Localized Delaunay Refinement for Volumes

Delaunay refinement, recognized as a versatile tool for meshing a variety of geometries, has the deficiency that it does not scale well with increasing mesh size. The bottleneck can be traced down to the memory usage of 3D Delaunay triangulations. Recently an approach has been suggested to tackle this problem for the specific case of smooth surfaces by subdividing the sample set in an octree and then refining each subset individually while ensuring termination and consistency. We extend this to localized refinement of volumes, which brings about some new challenges. We show how these challenges can be met with simple steps while retaining provable guarantees, and that our algorithm scales many folds better than a state‐of‐the‐art meshing tool provided by CGAL.     

Splat-based surface reconstruction from defect-laden point sets

We introduce a method for surface reconstruction from point sets that is able to cope with noise and outliers. First, a splat-based representation is computed from the point set. A robust local 3D RANSAC-based procedure is used to filter the point set for outliers, then a local jet surface – a low-degree surface approximation – is fitted to the inliers. Second, we extract the reconstructed surface in the form of a surface triangle mesh through Delaunay refinement. The Delaunay refinement meshing approach requires computing intersections between line segment queries and the surface to be meshed. In the present case, intersection queries are solved from the set of splats through a 1D RANSAC procedure.     

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.     

基于Loose r-sample的网格质量保持技术

为保证虚拟手术系统中的网格质量,提出一种基于Loose r-sample理论的快速表面网格重建算法。记录满足Loose r-sample采样定理的点集,用以描述物体的轮廓。通过约束Delaunay方法对该点集进行三角化,标记顶点和Delaunay单元,重构新的网格。实验结果表明,该算法能够保证生成网格的质量,简化仿真复杂度。     

New Bounds on the Size of Optimal Meshes

The theory of optimal size meshes gives a method for analyzing the output size (number of simplices) of a Delaunay refinement mesh in terms of the integral of a sizing function over the input domain. The input points define a maximal such sizing function called the feature size. This paper presents a way to bound the feature size integral in terms of an easy to compute property of a suitable ordering of the point set. The key idea is to consider the pacing of an ordered point set, a measure of the rate of change in the feature size as points are added one at a time. In previous work, Miller et al. showed that if an ordered point set has pacing ?, then the number of vertices in an optimal mesh will be O(?^dn), where d is the input dimension. We give a new analysis of this integral showing that the output size is only θ(n+nlog?). The new analysis tightens bounds from several previous results and provides matching lower bounds. Moreover, it precisely characterizes inputs that yield outputs of size O(n).     

Implicit Hierarchical Quad‐Dominant Meshes

We present a method for producing quad‐dominant subdivided meshes, which supports both adaptive refinement and adaptive coarsening. A hierarchical structure is stored implicitly in a standard half‐edge data structure, while allowing us to efficiently navigate through the different level of subdivision. Subdivided meshes contain a majority of quad elements and a moderate amount of triangles and pentagons in the regions of transition across different levels of detail. Topological LOD editing is controlled with local conforming operators, which support both mesh refinement and mesh coarsening. We show two possible applications of this method: we define an adaptive subdivision surface scheme that is topologically and geometrically consistent with the Catmull–Clark subdivision; and we present a remeshing method that produces semi‐regular adaptive meshes.     

Polygonal surface remeshing with Delaunay refinement

Polygonal meshes are used to model smooth surfaces in many applications. Often these meshes need to be remeshed for improving the quality, density or gradedness. We apply the Delaunay refinement paradigm to design a provable algorithm for isotropic remeshing of a polygonal mesh that approximates a smooth surface. The proofs provide new insights and our experimental results corroborate the theory.     

Generation of 3D mixed element meshes using a flexible refinement approach

This paper describes and discusses the main characteristics and implementation issues of a 3D mixed element mesh generator based on a generalization of the modified octree approach. This mesh generator uses primitive elements of different type as internal nodes, a flexible refinement approach as refinement strategy (primitive elements are not always bisected), and bricks, pyramids, prisms and tetrahedra as final elements. The mesh generation process is divided in several steps: the generation of the initial mesh composed of primitive elements, the refinement of primitive elements until the point density requirements are fulfilled, the generation of a graded mesh between dense and coarse regions, and finally, the recognition of the final elements. The main algorithms and data structures are described in detail for each step of the mesh generation process. As result, examples of meshes that satisfy the Delaunay condition and that can be used with the control volume method are shown.     

Transitive mesh space of a progressive mesh

The paper investigates the set of all selectively refined meshes that can be obtained from a progressive mesh. We call the set the transitive mesh space of a progressive mesh and present a theoretical analysis of the space. We define selective edge collapse and vertex split transformations, which we use to traverse all selectively refined meshes in the transitive mesh space. We propose a complete selective refinement scheme for a progressive mesh based on the transformations and compare the scheme with previous selective refinement schemes in both theoretical and experimental ways. In our comparison, we show that the complete scheme always generates selectively refined meshes with smaller numbers of vertices and faces than previous schemes for a given refinement criterion. The concept of dual pieces of the vertices in the vertex hierarchy plays a central role in the analysis of the transitive mesh space and the design of selective edge collapse and vertex split transformations.     

Uniform remeshing with an adaptive domain: a new scheme for view-dependent level-of-detail rendering of meshes

We present a new algorithm for view-dependent level-of-detail rendering of meshes. Not only can it effectively resolve complex geometry features similar to edge collapse-based schemes, but it also produces meshes that modern graphics hardware can render efficiently. This is accomplished through a novel hybrid approach: for each frame, we view-dependently refine the progressive mesh (PM) representation of the original mesh and use the output as the base domain of uniform regular refinements. The algorithm exploits frame-to-frame coherence and only updates portions of the output mesh corresponding to modified domain triangles. The PM representation is built using a custom volume preservation-based error function. A simple k-d tree enhanced jump-and-walk scheme is used to quickly map from the dynamic base domain to the original mesh during regular refinements. In practice, the PM refinement provides a view-optimized base domain for later regular refinements. The regular refinements ensure almost-everywhere regularity of output meshes, allowing optimization for vertex cache coherence and caching of geometry data in high-performance graphics memory. Combined, they also have the effect of allowing our algorithm to operate on uniform clusters of triangles instead of individual ones, reducing CPU workload.     

二维几何特征自适应有限元网格生成(一)--几何特征识别

发现二维形体边界均匀离散点集Delaunay三角剖分所具有的4个性质．根据这4个性质所描述的Delaunay三角剖分和形体几何特征之间的关系提出几何特征自动识别方法,并建立网格自适应机制,实现三维形体几何特征和部分力学特性自适应有限元网格自动生成．     

三维实体仿真建模的网格自动生成方法

有限元网格模型的生成与几何拓扑特征和力学特性有直接关系。建立网格模型时，为了更真实地反映原几何形体的特征，在小特征尺寸或曲率较大等局部区域网格应加密剖分；为提高有限元分析精度和效率，在待分析的开口、裂纹、几何突变、外载、约束等具有应力集中力学特性的局部区域，网格应加密剖分。为此，该文提出了基于几何特征和物理特性相结合的网格自动生成方法。该方法既能有效地描述几何形体，又能实现应力集中区域的网格局部加密及粗细网格的均匀过渡。实例表明本方法实用性强、效果良好。     

Efficient tetrahedral mesh generation based on sampling optimization

We present a heuristic approach to tetrahedral mesh generation for implicit closed surfaces. It consists of a surface sampling step and a volume sampling step that both work in a unified optimization framework. First, high‐quality isotropic samplings as well as a triangular mesh on the surface are generated. Then uniform volume samplings are determined by optimizing the point distribution inside the closed surface domain. Finally, the tetrahedral mesh is easily obtained by constrained Delaunay triangulation. Experimental results show that the new method can generate ideal tetrahedral meshes for closed implicit surfaces efficiently that are Delaunay based. Our method has the advantage of high efficiency and nice performance at surface boundaries. Copyright © 2015 John Wiley & Sons, Ltd.     

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

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

Generating well-shaped d-dimensional Delaunay Meshes

A d-dimensional simplicial mesh is a Delaunay triangulation if the circumsphere of each of its simplices does not contain any vertices inside. A mesh is well shaped if the maximum aspect ratio of all its simplices is bounded from above by a constant. It is a long-term open problem to generate well-shaped d-dimensional Delaunay meshes for a given polyhedral domain. In this paper, we present a refinement-based method that generates well-shaped d-dimensional Delaunay meshes for any PLC domain with no small input angles. Furthermore, we show that the generated well-shaped mesh has O(n) d-simplices, where n is the smallest number of d-simplices of any almost-good meshes for the same domain. Here a mesh is almost-good if each of its simplices has a bounded circumradius to the shortest edge length ratio.     

A Constrained Resampling Strategy for Mesh Improvement

In many geometry processing applications, it is required to improve an initial mesh in terms of multiple quality objectives. Despite the availability of several mesh generation algorithms with provable guarantees, such generated meshes may only satisfy a subset of the objectives. The conflicting nature of such objectives makes it challenging to establish similar guarantees for each combination, e.g., angle bounds and vertex count. In this paper, we describe a versatile strategy for mesh improvement by interpreting quality objectives as spatial constraints on resampling and develop a toolbox of local operators to improve the mesh while preserving desirable properties. Our strategy judiciously combines smoothing and transformation techniques allowing increased flexibility to practically achieve multiple objectives simultaneously. We apply our strategy to both planar and surface meshes demonstrating how to simplify Delaunay meshes while preserving element quality, eliminate all obtuse angles in a complex mesh, and maximize the shortest edge length in a Voronoi tessellation far better than the state‐of‐the‐art.     

An adaptive learning approach for 3-D surface reconstruction from point clouds.

In this paper, we propose a multiresolution approach for surface reconstruction from clouds of unorganized points representing an object surface in 3-D space. The proposed method uses a set of mesh operators and simple rules for selective mesh refinement, with a strategy based on Kohonen's self-organizing map (SOM). Basically, a self-adaptive scheme is used for iteratively moving vertices of an initial simple mesh in the direction of the set of points, ideally the object boundary. Successive refinement and motion of vertices are applied leading to a more detailed surface, in a multiresolution, iterative scheme. Reconstruction was experimented on with several point sets, including different shapes and sizes. Results show generated meshes very close to object final shapes. We include measures of performance and discuss robustness.