Generation of Tetrahedral Meshes with Multiple Elements through Thin Sections

Finite element simulations in domains with strong gradients across thin sections typically require meshes with multiple elements through these sections to accurately capture the solution. Most of the published techniques for isotropic mesh generation are not suited for the creation of such meshes in general, arbitrarily complex, non-manifold domains. In this paper, an automatic method is described for identification of thin sections of a domain and anisotropic refinement of an initial mesh to introduce a user-requested number of elements through the thin sections. The method uses local mesh modification operations to effect the refinement and subsequent realignment of edges along the thickness direction and perpendicular to it. Results are presented for a number of general models to illustrate the capability of the mesh generator.     

Extracting objects from range and radiance images

In this paper, we present a pipeline and several key techniques necessary for editing a real scene captured with both cameras and laser range scanners. We develop automatic algorithms to segment the geometry from range images into distinct surfaces, register texture from radiance images with the geometry, and synthesize compact high-quality texture maps. The result is an object-level representation of the scene which can be rendered with modifications to structure via traditional rendering methods. The segmentation algorithm for geometry operates directly on the point cloud from multiple registered 3D range images instead of a reconstructed mesh. It is a top-down algorithm which recursively partitions a point set into two subsets using a pairwise similarity measure. The result is a binary tree with individual surfaces as leaves. Our image registration technique performs a very efficient search to automatically find the camera poses for arbitrary position and orientation relative to the geometry. Thus, we can take photographs from any location without precalibration between the scanner and the camera. The algorithms have been applied to large-scale real data. We demonstrate our ability to edit a captured scene by moving, inserting, and deleting objects     

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.     

几何自适应参数曲面网格生成

为满足有限元分析的需要,针对参数曲面提出一种几何自适应的网格生成方法.通过黎曼度量控制下的曲面约束Delaunay三角化获得曲面中轴,将其用于自动识别曲面邻近特征,并通过曲率计算自动识别曲率特征;根据邻近特征和曲率特征,融合传统网格尺寸控制技术控制边界曲线离散,并创建密度场;结合映射法和前沿推进技术对组合参数曲面生成几何自适应的网格.实验结果表明,该方法能够处理复杂的几何外形,生成的网格具有很好的自适应效果和质量.     

High-Resolution Volumetric Computation of Offset Surfaces with Feature Preservation

We present a new algorithm for the efficient and reliable generation of offset surfaces for polygonal meshes. The algorithm is robust with respect to degenerate configurations and computes (self‐)intersection free offsets that do not miss small and thin components. The results are correct within a prescribed ε‐tolerance. This is achieved by using a volumetric approach where the offset surface is defined as the union of a set of spheres, cylinders, and prisms instead of surface‐based approaches that generally construct an offset surface by shifting the input mesh in normal direction. Since we are using the unsigned distance field, we can handle any type of topological inconsistencies including non‐manifold configurations and degenerate triangles. A simple but effective mesh operation allows us to detect and include sharp features (shocks) into the output mesh and to preserve them during post‐processing (decimation and smoothing). We discretize the distance function by an efficient multi‐level scheme on an adaptive octree data structure. The problem of limited voxel resolutions inherent to every volumetric approach is avoided by breaking the bounding volume into smaller tiles and processing them independently. This allows for almost arbitrarily high voxel resolutions on a commodity PC while keeping the output mesh complexity low. The quality and performance of our algorithm is demonstrated for a number of challenging examples.     

Multi-view Performance Capture of Surface Details

This paper presents a novel approach to recover true fine surface detail of deforming meshes reconstructed from multi-view video. Template-based methods for performance capture usually produce a coarse-to-medium scale detail 4D surface reconstruction which does not contain the real high-frequency geometric detail present in the original video footage. Fine scale deformation is often incorporated in a second pass by using stereo constraints, features, or shading-based refinement. In this paper, we propose an alternative solution to this second stage by formulating dense dynamic surface reconstruction as a global optimization problem of the densely deforming surface. Our main contribution is an implicit representation of a deformable mesh that uses a set of Gaussian functions on the surface to represent the initial coarse mesh, and a set of Gaussians for the images to represent the original captured multi-view images. We effectively find the fine scale deformations for all mesh vertices, which maximize photo-temporal-consistency, by densely optimizing our model-to-image consistency energy on all vertex positions. Our formulation yields a smooth closed form energy with implicit occlusion handling and analytic derivatives. Furthermore, it does not require error-prone correspondence finding or discrete sampling of surface displacement values. We demonstrate our approach on a variety of datasets of human subjects wearing loose clothing and performing different motions. We qualitatively and quantitatively demonstrate that our technique successfully reproduces finer detail than the input baseline geometry.     

Anisotropic finite element modeling for patient-specific mandible

This paper presents an ad hoc modular software tool to quasi-automatically generate patient-specific three-dimensional (3D) finite element (FE) model of the human mandible. The main task is taking into account the complex geometry of the individual mandible, as well as the inherent highly anisotropic material law. At first, by computed tomography data (CT), the individual geometry of the complete range of mandible was well reproduced, also the separation between cortical and cancellous bone. Then, taking advantage of the inherent shape nature as ‘curve’ long bone, the algorithm employed a pair of B-spline curves running along the entire upper and lower mandible borders as auxiliary baselines, whose directions are also compatible with that of the trajectory of maximum material stiffness throughout the cortical bone of the mandible. And under the guidance of this pair of auxiliary baselines, a sequence of B-spline surfaces were interpolated adaptively as curve cross-sections to cut the original geometry. Following, based on the produced curve contours and the corresponding curve cross-section surfaces, quite well structured FE volume meshes were constructed, as well as the inherent trajectory vector fields of the anisotropic material (orthotropic for cortical bone and transversely isotropic for cancellous bone). Finally, a sensitivity analysis comprising various 3D FE simulations was carried out to reveal the relevance of elastic anisotropy for the load carrying behavior of the mandible.     

A new method for analyzing local shape in three-dimensional images based on medial axis transformation

In this paper, we propose a new approach based on three-dimensional (3-D) medial axis transformation for describing geometrical shapes in three-dimensional images. For 3-D-images, the medial axis, which is composed of both curves and medial surfaces, provides a simplified and reversible representation of structures. The purpose of this new method is to classify each voxel of the three-dimensional images in four classes: boundary, branching, regular and arc points. The classification is first performed on the voxels of the medial axis. It relies on the topological properties of a local region of interest around each voxel. The size of this region of interest is chosen as a function of the local thickness of the structure. Then, the reversibility of the medial axis is used to deduce a labeling of the whole object. The proposed method is evaluated on simulated images. Finally, we present an application of the method to the identification of bone structures from 3-D very high-resolution tomographic images.     

Computer-based extraction of the inferior alveolar nerve canal in 3-D space

Computed tomography (CT) is increasingly employed in orthodontic treatment. One of the most successful applications is in dental implantology, in which an artificial root is surgically inserted into the jawbone to provide anchorage for a dental prosthesis. For successful implant surgery, it is crucial to locate internal structures such as the inferior alveolar nerve canal (IAC). This paper presents a computerized technique for extracting the IAC. To facilitate the extraction, we first generate panoramic CT images (panoramics) by reformatting the original CT images. The panoramics are a series of cross-sectional images along curved planes through the mandible (lower jawbone). Hollow canals are subsequently detected by analyzing the voxel intensities and 3-D gradient orientations in the panoramics. The axis of the IAC is then traced out by a novel 3-D line-tracking technique. The method is effective for extracting the IAC despite the open structure of the surrounding bone.     

Non-rigid isometric ICP: A practical registration method for the analysis and compensation of form errors in production engineering

The unprecedented success of the iterative closest point (ICP) method for registration in geometry processing and related fields can be attributed to its efficiency, robustness, and wide spectrum of applications. Its use is however quite limited as soon as the objects to be registered arise from each other by a transformation significantly different from a Euclidean motion. We present a novel variant of ICP, tailored for the specific needs of production engineering, which registers a triangle mesh with a second surface model of arbitrary digital representation. Our method inherits most of ICP’s practical advantages but is capable of detecting medium-strength bendings i.e. isometric deformations. Initially, the algorithm assigns to all vertices in the source their closest point on the target mesh and then iteratively establishes isometry, a process which, very similar to ICP, requires intermediate re-projections. A NURBS-based technique for applying the resulting deformation to arbitrary instances of the source geometry, other than the very mesh used for correspondence estimation, is described before we present numerical results on synthetic and real data to underline the viability of our approach in comparison with others.     

Adaptive hexahedral mesh generation and quality optimization for solid models with thin features using a grid-based method

This paper presented an automatic inside-out grid-based hexahedral element mesh generation algorithm for various types of solid models. For the thin features with small thickness of the geometric model, corresponding treatment methods were given for successfully implementing each meshing step, containing the techniques for adaptive refinement, boundary match, topological optimization and local refinement. In order to realize the reasonable identification of refinement regions and resolve the expansion problem of refinement information fields, a thin-feature criterion and a supplementary criterion were proposed aiming at thin features of the geometry. To implement accurate boundary match for thin features, ten basic types and five complementary types of facet configurations were established, and a priority-node identification method was proposed additionally. Three topological optimization modes were newly proposed to improve the topological connections of the boundary mesh in thin features. Local refinement techniques were also built to refine the thin features of solid models. Finally, several examples were provided to demonstrate the effectiveness and reliability of the proposed algorithms.     

A 3D model perceptual feature metric based on global height field

Human visual attention system tends to be attracted to perceptual feature points on 3D model surfaces. However, purely geometric-based feature metrics may be insufficient to extract perceptual features, because they tend to detect local structure details. Intuitively, the perceptual importance degree of vertex is associated with the height of its geometry position between original model and a datum plane. So, we propose a novel and straightforward method to extract perceptually important points based on global height field. Firstly, we construct spectral domain using Laplace–Beltrami operator, and we perform spectral synthesis to reconstruct a rough approximation of the original model by adopting low-frequency coefficients, and make it as the 3D datum plane. Then, to build global height field, we calculate the Euclidean distance between vertex geometry position on original surface and the one on 3D datum plane. Finally, we set a threshold to extract perceptual feature vertices. We implement our technique on several 3D mesh models and compare our algorithm to six state-of-the-art interest points detection approaches. Experimental results demonstrate that our algorithm can accurately capture perceptually important points on arbitrary topology 3D model.     

System for reconstruction of three-dimensional micro objects from multiple photographic images

We introduce a system to reconstruct a three-dimensiojnal (3D) polygonal model of 3D micro objects with outer dimensions ranging from several hundred microns to several millimeters from multiple two-dimensional (2D) images of an object taken from different views. The data acquisition system consists of a digital microscope that captures still images at a resolution of 1600 × 1200 pixels and a computer-controlled turntable. We employ the shape-from-silhouette (SFS) method to construct a voxel-based 3D model from silhouette images. The concave shapes are further carved by using the space carving technique. In order to make the resulting model compatible with a commercial CAD/CAM system, the voxel model is converted into a triangular mesh using the marching cubes algorithm. Because the mesh generated from the voxel model by using the marching cubes algorithm inherits the staircase effect, the mesh is adjusted to recover the object precisely by using silhouette images. Finally, we evaluate the accuracy of the proposed method. The reconstructed models of complex micro objects indicate the effectiveness of the 3D shape reconstruction system for micro objects.     

Surface Reconstruction and Display from Range and Color Data

This paper addresses the problem of scanning both the color and geometry of real objects and displaying realistic images of the scanned objects from arbitrary viewpoints. We describe a complete system that uses a stereo camera setup with active lighting to scan the object surface geometry and color. Scans expressed in sensor coordinates are registered into a single object-centered coordinate system by aligning both the color and geometry where the scans overlap. The range data are integrated into a surface model using a robust hierarchical space carving method. The fit of the resulting approximate mesh to data is improved and the mesh structure is simplified using mesh optimization methods. In addition, a method for view-dependent texturing of the reconstructed surfaces is described. The method projects the color data from the input images onto the surface model and blends the various images depending on the location of the viewpoint and other factors such as surface orientation.     

Semiautomated finite element mesh generation methods for a long bone

The objective of this work was to develop and test a semi-automated finite element mesh generation method using computed tomography (CT) image data of a canine radius. The present study employs a direct conversion from CT Hounsfield units to elastic moduli. Our method attempts to minimize user interaction and eliminate the need for mesh smoothing to produce a model suitable for finite element analysis. Validation of the computational model was conducted by loading the CT-imaged canine radius in four-point bending and using strain gages to record resultant strains that were then compared to strains calculated with the computational model. Geometry-based and uniform modulus voxel-based models were also constructed from the same imaging data set and compared. The nonuniform voxel-based model most accurately predicted the axial strain response of the sample bone (R(2)=0.9764).     

Generation of bi-monotone patches from quadrilateral mesh for reverse engineering

Thanks to recent improvements, computational methods can now be used to convert triangular meshes into quadrilateral meshes so that the quadrilateral elements capture well the principal curvature directional fields of surfaces and intrinsically have surface parametric values. In this study, a quadrilateral mesh generated using the mixed integer quadrangulation technique of Bommes et al. is used for input. We first segment a quadrilateral mesh into four-sided patches. The feature curves inside these patches are then detected and are constrained to act as the patch boundaries. Finally, the patch configuration is improved to generate large patches. The proposed method produces bi-monotone patches, which are appropriate for use in reverse engineering to capture the surface details of an object. A shape control parameter that can be adjusted by the user during the patch generation process is also provided to support the creation of patches with good bi-monotone shapes. This study mainly targets shape models of mechanical parts consisting of major smooth surfaces with feature curves between them.     

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.     

Geometry completion and detail generation by texture synthesis

We present a novel method for patching holes in polygonal meshes and synthesizing surfaces with details based on existing geometry. The most novel feature of our proposed method is that we transform the 3D geometry synthesis problem into a 2D domain by parameterizing surfaces and solve this problem in that domain. We then derive local geometry gradient images that encode intrinsic local geometry properties, which are invariant to object translation and rotation. The 3D geometry of holes is then reconstructed from synthesized local gradient images. This method can be extended to execute other mesh editing operations such as geometry detail transfer or synthesis. The resulting major benefits of performing geometry synthesis in 2D are more flexible and robust control, better leveraging of the wealth of current 2D image completion methods, and greater efficiency.     

A coordinate transformation approach for efficient repeated solution of Helmholtz equation pertaining to obstacle scattering by shape deformations

A computational model is developed for efficient solutions of electromagnetic scattering from obstacles having random surface deformations or irregularities (such as roughness or randomly-positioned bump on the surface), by combining the Monte Carlo method with the principles of transformation electromagnetics in the context of finite element method. In conventional implementation of the Monte Carlo technique in such problems, a set of random rough surfaces is defined from a given probability distribution; a mesh is generated anew for each surface realization; and the problem is solved for each surface. Hence, this repeated mesh generation process places a heavy burden on CPU time. In the proposed approach, a single mesh is created assuming smooth surface, and a transformation medium is designed on the smooth surface of the object. Constitutive parameters of the medium are obtained by the coordinate transformation technique combined with the form-invariance property of Maxwell’s equations. At each surface realization, only the material parameters are modified according to the geometry of the deformed surface, thereby avoiding repeated mesh generation process. In this way, a simple, single and uniform mesh is employed; and CPU time is reduced to a great extent. The technique is demonstrated via various finite element simulations for the solution of two-dimensional, Helmholtz-type and transverse magnetic scattering problems.     

Mesh size functions for implicit geometries and PDE-based gradient limiting

Mesh generation and mesh enhancement algorithms often require a mesh size function to specify the desired size of the elements. We present algorithms for automatic generation of a size function, discretized on a background grid, by using distance functions and numerical PDE solvers. The size function is adapted to the geometry, taking into account the local feature size and the boundary curvature. It also obeys a grading constraint that limits the size ratio of neighboring elements. We formulate the feature size in terms of the medial axis transform, and show how to compute it accurately from a distance function. We propose a new Gradient Limiting Equation for the mesh grading requirement, and we show how to solve it numerically with Hamilton–Jacobi solvers. We show examples of the techniques using Cartesian and unstructured background grids in 2D and 3D, and applications with numerical adaptation and mesh generation for images.