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.     

Guaranteed-Quality Simplical Mesh Generation with Cell Size and Grading Control

Unstructured mesh quality, as measured geo-metrically, has long been known to influence solution accuracy and efficiency for finite-element and finite-volume simulations. Recent guaranteed-quality unstructured meshing algorithms are therefore welcome tools. However, these algorithms allow no explicit control over mesh resolution or grading. We define a geometric length scale, similar in principle to the local feature size, which allows automatic global control of mesh resolution and grading. We describe how to compute this length scale efficiently and modify Ruppert’s two-dimensional and Shewchuk’s three-dimensional meshing algorithms to produce meshes matching our length scale. We provide proofs of mesh quality, good grading, and size optimality for both two- and three-dimensions, and present examples, including comparison with existing schemes known to generate good-quality meshes.     

Automatic generation of tetrahedral meshes from medical images

A new tetrahedral meshing algorithm from the series of medical images is proposed. Sectional contours are extracted from medical images, and by the use of correspondence, tiling, and branching process, the side surfaces between sections are triangulated in addition to the triangulation on each section. As for the mesh generation for an object between two sections, an advancing front algorithm is employed to generate tetrahedral elements by using basic operators. Sample meshes are constructed from medical images for finite element analysis of biomechanical models.     

Localized Delaunay Refinement for Sampling and Meshing

The technique of Delaunay refinement has been recognized as a versatile tool to generate Delaunay meshes of a variety of geometries. Despite its usefulness, it suffers from one lacuna that limits its application. It does not scale well with the mesh size. As the sample point set grows, the Delaunay triangulation starts stressing the available memory space which ultimately stalls any effective progress. A natural solution to the problem is to maintain the point set in clusters and run the refinement on each individual cluster. However, this needs a careful point insertion strategy and a balanced coordination among the neighboring clusters to ensure consistency across individual meshes. We design an octtree based localized Delaunay refinement method for meshing surfaces in three dimensions which meets these goals. We prove that the algorithm terminates and provide guarantees about structural properties of the output mesh. Experimental results show that the method can avoid memory thrashing while computing large meshes and thus scales much better than the standard Delaunay refinement method.     

Template-based finite-element mesh generation from medical images

The finite-element (FE) method is commonly used in biomedical engineering to simulate the behaviour of biological structures because of its ability to model complex shapes in a subject-specific manner. However, generating FE meshes from medical images remains a bottleneck. We present a template-based technique for semi-automatically generating FE meshes which is applicable to prospective studies of individual patients in which FE meshes must be generated from scans of the same structure taken at different points in time to study the effects of disease progression/regression. In this "template-based" meshing approach, the baseline FE (tetrahedral) volume mesh is first manually aligned with the follow-up images. The triangulated surface of the mesh is then automatically deformed to fit the imaged organ boundary. The deformed surface nodes are then smoothed using a Laplacian smoothing algorithm to correct triangle (surface nodes) distortion and thus preserve triangle quality. Finally, the internal mesh nodes are smoothed to correct distorted tetrahedral elements and thus preserve tetrahedral element quality. This template-based approach is shown to be as accurate and precise as the previous technique used by our group, while preserving element quality and volume.     

Template-based quadrilateral mesh generation from imaging data

This paper describes a novel template-based meshing approach for generating good quality quadrilateral meshes from 2D digital images. This approach builds upon an existing image-based mesh generation technique called Imeshp, which enables us to create a segmented triangle mesh from an image without the need for an image segmentation step. Our approach generates a quadrilateral mesh using an indirect scheme, which converts the segmented triangle mesh created by the initial steps of the Imesh technique into a quadrilateral one. The triangle-to-quadrilateral conversion makes use of template meshes of triangles. To ensure good element quality, the conversion step is followed by a smoothing step, which is based on a new optimization-based procedure. We show several examples of meshes generated by our approach, and present a thorough experimental evaluation of the quality of the meshes given as examples.     

Reconstructing regular meshes from points

We propose an algorithm for reconstructing regular meshes from unorganized point clouds. At first, a nearly isometric point parameterization is computed using only the location of the points. A mesh, composed of nearly equilateral triangles, is later created using a regular sampling pattern. This approach produces meshes with high visual quality and suitable for use with applications such as finite element analysis, which tend to impose strong constraints on the regularity of the input mesh. Geometric properties, such as local connectivity and surface features, are identified directly from the points and are stored independent of the resulting mesh. This decoupling preserves most details and allows more flexibility for meshing. The resulting parameterization supports several direct applications, such as texturing and bump mapping. In addition, novel boundary identification and cut parameterization algorithms are proposed to overcome the difficulties caused by cuts, non-closed surfaces and possible self-overlapping parameter patches. We demonstrate the effectiveness of our approach by reconstructing regular meshes from real datasets, such as a human colon obtained from CT scan and objects digitized using laser scanners.     

LayTracks3D: A new approach for meshing general solids using medial axis transform

This paper presents an extension of the all-quad meshing algorithm called LayTracks to generate high quality hex-dominant meshes of general solids. LayTracks3D uses the mapping between the Medial Axis (MA) and the boundary of the 3D domain to decompose complex 3D domains into simpler domains called Tracks. Tracks in 3D have no branches and are symmetric, non-intersecting, orthogonal to the boundary, and the shortest path from the MA to the boundary. These properties of tracks result in desired meshes with near cube shape elements at the boundary, structured mesh along the boundary normal with any irregular nodes restricted to the MA, and sharp boundary feature preservation. The algorithm has been tested on a few industrial CAD models and hex-dominant meshes are shown in the Results section. Work is underway to extend LayTracks3D to generate all-hex meshes.     

Enhanced medial-axis-based block-structured meshing in 2-D

New techniques are presented for using the medial axis to generate decompositions on which high quality block-structured meshes with well-placed mesh singularities can be generated. Established medial-axis-based meshing algorithms are effective for some geometries, but in general, they do not produce the most favourable decompositions, particularly when there are geometric concavities. This new approach uses both the topological and geometric information in the medial axis to establish a valid and effective arrangement of mesh singularities for any 2-D surface. It deals with concavities effectively and finds solutions that are most appropriate to the geometric shapes. Resulting meshes are shown for a number of example models.     

Range Segmentation Using Visibility Constraints

Visibility constraints can aid the segmentation of foreground objects in a scene observed with multiple range imagers. Points may be labeled as foreground if they can be determined to occlude some space in the scene that we expect to be empty. Visibility constraints from a second range view provide evidence of such occlusions. We present an efficient algorithm to estimate foreground points in each range view using explicit epipolar search. In cases where the background pattern is stationary, we show how visibility constraints from other views can generate virtual background values at points with no valid depth in the primary view. We demonstrate the performance of both algorithms for detecting people in indoor office environments with dynamic illumination variation.     

Generation of a finite element MESH from stereolithography (STL) files

The aim of the method proposed here is to show the possibility of generating adaptive surface meshes suitable for the finite element method, directly from an approximated boundary representation of an object created with CAD software. First, we describe the boundary representation, which is composed of a simple triangulation of the surface of the object. Then we will show how to obtain a conforming size-adapted mesh. The size adaptation is made considering geometrical approximation and with respect to an isotropic size map provided by an error estimator. The mesh can be used “as is” for a finite element computation (with shell elements), or can be used as a surface mesh to initiate a volume meshing algorithm (Delaunay or advancing front). The principle used to generate the mesh is based on the Delaunay method, which is associated with refinement algorithms, and smoothing. Finally, we will show that not using the parametric representation of the geometrical model allows us to override some of the limitations of conventional meshing software that is based on an exact representation of the geometry.     

Interpolatory,solid subdivision of unstructured hexahedral meshes

This paper presents a new, volumetric subdivision scheme for interpolation of arbitrary hexahedral meshes. To date, nearly every existing volumetric subdivision scheme is approximating, i.e., with each application of the subdivision algorithm, the geometry shrinks away from its control mesh. Often, an approximating algorithm is undesirable and inappropriate, producing unsatisfactory results for certain applications in solid modeling and engineering design (e.g., finite element meshing). We address this lack of smooth, interpolatory subdivision algorithms by devising a new scheme founded upon the concept of tri-cubic Lagrange interpolating polynomials. We show that our algorithm is a natural generalization of the butterfly subdivision surface scheme to a tri-variate, volumetric setting.     

An effective quad-dominant meshing method for unorganized point clouds

To perform quad meshing on raw point clouds, existing algorithms usually require a time-consuming parameterization or Voronoi space partition process. In this paper, we propose an effective method to generate quad-dominant meshes directly from unorganized point clouds. In the proposed method, we first apply Marinov’s curvature tensor optimization to the input point cloud to reduce the umbilical regions in order to obtain a smooth curvature tensor. We then propose an efficient marching scheme to extract the curvature lines with controllable density from the point cloud. Finally, we apply a specialized K-Dimension (KD) tree structure, which converts the nearest neighbor searching problem into a sorting problem, to efficiently estimate the intersections of curvature lines and recover the topology of the quad-dominant meshes. We have tested the proposed method on different point clouds. Our results show that the proposed method produces good quality meshes with high computational efficiency and low memory requirement.     

Fun sheet matching: towards automatic block decomposition for hexahedral meshes

Depending upon the numerical approximation method that may be implemented, hexahedral meshes are frequently preferred to tetrahedral meshes. Because of the layered structure of hexahedral meshes, the automatic generation of hexahedral meshes for arbitrary geometries is still an open problem. This layered structure usually requires topological modifications to propagate globally, thus preventing the general development of meshing algorithms such as Delaunay??s algorithm for tetrahedral meshes or the advancing-front algorithm based on local decisions. To automatically produce an acceptable hexahedral mesh, we claim that both global geometric and global topological information must be taken into account in the mesh generation process. In this work, we propose a theoretical classification of the layers or sheets participating in the geometry capture procedure. These sheets are called fundamental, or fun-sheets for short, and make the connection between the global layered structure of hexahedral meshes and the geometric surfaces that are captured during the meshing process. Moreover, we propose a first generation algorithm based on fun-sheets to deal with 3D geometries having 3- and 4-valent vertices.     

Reliable Whisker Weaving via Curve Contraction

Whisker Weaving is an advancing front algorithm for all-hexahedral mesh generation. It uses global information derived from grouping the mesh dual into surfaces, the STC, to construct the connectivity of the mesh, then positions the nodes afterwards. Currently, we are able to reliably generate hexahedral meshes for complicated geometries and surface meshes. However, the surface mesh must be modified locally. Also, in large, highly-unstructured meshes, there are usually isolated regions where hex quality is poor. Reliability has been achieved by using new, provable curvecontraction algorithms to sequence the advancing front process. We have also demonstrated that sheet moving can remove certain types of invalid connectivity.     

基于多目标规划的模糊C均值聚类算法

模糊C均值聚类算法(FCM)是一种非常经典的非监督聚类技术,已被广泛地应用到医学图像分割。由于传统的FCM聚类算法在分割图像时仅利用了图像的灰度信息,未利用图像的空间信息,在分割叠加了噪声的磁共振(MR)图像时分割效果不理想。考虑到脑部MR图像真实的灰度值具有分片为常数的特性,按照合理利用图像空间信息的原则,对传统的FCM聚类算法进行了改进,引入多目标规划的概念,提出了一种新的,更加合理的应用图像空间信息的聚类算法。实验结果表明,应用该算法可以有效地分割含有噪声的图像。     

An automatic coarse and fine surface mesh generation scheme based on medial axis transform: Part II implementation

In this paper, we present implementation aspects of a surface finite element (FE) meshing algorithm described in Part I (this volume) [1]. This meshing scheme is based on the medial axis transform (MAT) [2] to interrogate shape and to subdivide it into topologically simple subdomains. The algorithm can be effectively used to create coarse discretization and fine triangular surface meshes. We describe our techniques and methodology used in the implementation of the meshing and MAT algorithms. We also present some running times of our experimental system. We finally report the results we have obtained from several design and analysis applications which include adaptive surface approximations using triangular facets, and adaptiveh- andp-adaptive finite element analysis (FEA) of plane stress problems. These studies demonstrate the potential applicability of our techniques in computer aided design and analysis.     

Spectral 3D mesh segmentation with a novel single segmentation field

We present an automatic mesh segmentation framework that achieves 3D segmentation in two stages, hierarchical spectral analysis and isoline-based boundary detection. During the hierarchical spectral analysis stage, a novel segmentation field is defined to capture a concavity-aware decomposition of eigenvectors from a concavity-aware Laplacian. Specifically, a sufficient number of eigenvectors is first adaptively selected and simultaneously partitioned into sub-eigenvectors through spectral clustering. Next, on the sub-eigenvectors level, we evaluate the confidence of identifying a spectral-sensitive mesh boundary for each sub-eigenvector by two joint measures, namely, inner variations and part oscillations. The selection and combination of sub-eigenvectors are thereby formulated as an optimization problem to generate a single segmentation field. In the isoline-based boundary detection stage, the segmentation boundaries are recognized by a divide-merge algorithm and a cut score, which respectively filters and measures desirable isolines from the concise single segmentation field. Experimental results on the Princeton Segmentation Benchmark and a number of other complex meshes demonstrate the effectiveness of the proposed method, which is comparable to recent state-of-the-art algorithms.     

Parallel fem algorithms based on recursive spatial decomposition—I. Automatic mesh generation

This paper discusses an automatic meshing scheme that is suitable for parallel processing. Meshes derived from solid models through recursive spatial decompositions inherit the hierarchical organization and the spatial addressability of the underlying grid. These two properties are exploited to design a meshing algorithm capable of operating in parallel (concurrent) processing environments. The concept of a meshing operator for parallel processing is defined and algorithms for various stages of the automatic meshing scheme are presented. A systematic simulation of fine- and coarse-grain parallel configurations is used to evaluate the performance of the meshing scheme. A companion paper focuses on parallel processing for the analysis of these automatically derived meshes via hierarchical substructuring.