基于LEPP递变的四面体网格自适应剖分算法

为了更合理地进行四面体网格剖分,提出了一种根据待剖分对象形态不同进行网格密度自适应调整的四面体网格剖分方法。该方法首先采用BCC(body-centered cubic)网格初始化网格空间,并根据表面曲率的大小以及距离物体表面的远近,采用LEPP(longest edge propagation path)算法由外至内对初始化后的网格空间进行不同尺度的细分;然后对横跨表面的网格进行调整,以形成对象的表面形态;最后采用以质量函数引导的拉普拉斯平滑与棱边收缩(edge collapse)的方法对网格的质量进行优化来最终得到待剖分对象的四面体网格。结果表明,该方法所生成的网格不仅具有自适应的网格密度,而且网格质量比常用的Advancing Front算法也有所提高。对于基于3维断层图像或表面模型进行有限元建模,该方法不失为一种行之有效的好方法。     

BMSweep: Locating Interior Nodes During Sweeping

BMSweep is a new algorithm to determine the location of interior nodes while generating hexahedral meshes using the volume sweeping method. Volume sweeping is performed on two and one half-dimensional volumes by identifying a ‘source’ surface which is meshed with quadrilaterals. These quadrilaterals are then swept through the volume towards a ‘target’ surface generating layers of hexahedra along the way. BMSweep uses background mesh interpolation to locate interior nodes during sweeping. The interpolation method provides for quality element creation, while allowing the volume boundary to vary. The cross-section of the volume can vary along the length of the sweep, the sweep path need not be linear, and the source and target areas need not be flat. Three dimensional volumes can be swept using BMSweep after being decomposed into two and one half-dimensional subvolumes.     

三维颅骨表面模型的复杂孔洞修补

颅骨表面模型的孔洞复杂,很难用目前常用的图形学中某一类算法进行修补。目前基本修补算法（BHRA）可用来修补一般区域孔洞,但对于颅骨上破损较大复杂孔洞和特征区域复杂孔洞还没有较好的修补算法,为此提出了一种颅骨模型复杂孔洞修补算法,该算法首先通过复杂孔洞的位置和复杂孔洞包围盒的面积来对该复杂孔洞进行分类,再选择相应的算法进行孔洞修补。针对颅骨上区域较大复杂孔洞,提出了一种向内递归修补法(IRS),解决了传统孔洞修补方法修补曲面较为平坦的问题;针对颅骨上的特征区域复杂孔洞,提出了特征模型匹配法（TMA）,使用标准模型作为约束并对其进行变形,使修补后的模型更符合人的面部特征。实验结果分析表明,本算法对颅骨上区域较大的复杂孔洞和特征区域孔洞的修补效果令人满意,同时将该修补后的颅骨模型进行颅面复原,颅面复原效果良好。     

3维颅骨表面模型的复杂孔洞修补

颅骨表面模型的孔洞复杂,很难用目前常用的图形学中某一类算法进行修补。目前基本修补算法(BHRA)可用来修补一般区域孔洞,但对于颅骨上破损较大复杂孔洞和特征区域复杂孔洞还没有较好的修补算法,为此提出一种颅骨模型复杂孔洞修补算法,该算法首先通过复杂孔洞的位置和复杂孔洞包围盒的面积来对该复杂孔洞进行分类,再选择相应的算法进行孔洞修补。针对颅骨上区域较大复杂孔洞,提出一种向内递归修补法(IRS),解决了传统孔洞修补方法修补曲面较为平坦的问题;针对颅骨上的特征区域复杂孔洞,提出了特征模型匹配法(TMA),使用标准模型作为约束并对其进行变形,使修补后的模型更符合人的面部特征。实验结果分析表明,该算法对颅骨上区域较大的复杂孔洞和特征区域孔洞的修补效果令人满意,同时将该修补后的颅骨模型进行颅面复原,颅面复原效果良好。     

Medial Axis Construction in Three Dimensions and its Application to Mesh Generation

An algorithm for the construction of the medial axis of a three-dimensional body given by a triangulation of its bounding surface is described. The indirect construction is based on the Delaunay-triangulation of a set of sample points on the bounding surface. The point set is refined automatically so as to capture the correct topology of the medial axis. The computed medial axis (or better medial surface) is then used for hex-dominant mesh generation. Quad-dominant meshes are generated on the medial subfaces first and extruded to the boundary of the body at both sides. The resulting single cell layer is subdivided in direction normal to the boundary, yielding columns of hexahedral and three-sided prismatic cells. The resulting volume mesh is orthogonal at the boundary and ‘semi-structured’ between boundary and medial surface. Mixed cell types (tets, pyramids, degenerate hexahedra) may result along the medial surface. An advancing front algorithm (paving) is used for meshing the subfaces of the medial surface. Development of the mesh generator has not been fully completed with respect to degenerate parts of the medial axis. First medium-complexity bodies have been meshed, however, showing moderate meshing times.     

Hole filling of a 3D model by flipping signs of a signed distance field in adaptive resolution

When we use range finders to observe the shape of an object, many occluded areas may occur. These become holes and gaps in the model and make it undesirable for various applications. We propose a novel method to fill holes and gaps to complete this incomplete model. As an intermediate representation, we use a Signed Distance Field (SDF), which stores Euclidean signed distances from a voxel to the nearest point of the mesh model. By using an SDF, we can obtain interpolating surfaces for holes and gaps. The proposed method generates an interpolating surface that becomes smoothly continuous with real surfaces by minimizing the area of the interpolating surface. Since the isosurface of an SDF can be identified as being a real or interpolating surface from the magnitude of signed distances, our method computes the area of an interpolating surface in the neighborhood of a voxel both before and after flipping the sign of the signed distance of the voxel. If the area is reduced by flipping the sign, our method changes the sign for the voxel. Therefore, we minimize the area of the interpolating surface by iterating this computation until convergence. Unlike methods based on Partial Differential Equations (PDE), our method does not require any boundary condition, and the initial state that we use is automatically obtained by computing the distance to the closest point of the real surface. Moreover, because our method can be applied to an SDF of adaptive resolution, our method efficiently interpolates large holes and gaps of high curvature.We tested the proposed method with both synthesized and real objects and evaluated the interpolating surfaces.     

Towards recovery of complex shapes in meshes using digital images for reverse engineering applications

When an object owns complex shapes, or when its outer surfaces are simply inaccessible, some of its parts may not be captured during its reverse engineering. These deficiencies in the point cloud result in a set of holes in the reconstructed mesh. This paper deals with the use of information extracted from digital images to recover missing areas of a physical object. The proposed algorithm fills in these holes by solving an optimization problem that combines two kinds of information: (1) the geometric information available on the surrounding of the holes, (2) the information contained in an image of the real object. The constraints come from the image irradiance equation, a first-order non-linear partial differential equation that links the position of the mesh vertices to the light intensity of the image pixels. The blending conditions are satisfied by using an objective function based on a mechanical model of bar network that simulates the curvature evolution over the mesh. The inherent shortcomings both to the current hole-filling algorithms and the resolution of the image irradiance equations are overcome.     

Image-space visibility ordering for cell projection volume rendering of unstructured data

Projection methods for volume rendering unstructured data work by projecting, in visibility order, the polyhedral cells of the mesh onto the image plane, and incrementally compositing each cell's color and opacity into the final image. Normally, such methods require an algorithm to determine a visibility order of the cells. The meshed polyhedra visibility order (MPVO) algorithm can provide such an order for convex meshes by considering the implications of local ordering relations between cells sharing a common face. However, in nonconvex meshes, one must also consider ordering relations along viewing rays which cross empty space between cells. In order to include these relations, the algorithm described in this paper, the scanning exact meshed polyhedra visibility ordering (SXMPVO) algorithm, scan-converts the exterior faces of the mesh and saves the ray-face intersections in an A-buffer data structure which is then used for retrieving the extra ordering relations. The image which SXMPVO produces is the same as would be produced by ordering the cells exactly, even though SXMPVO does not compute an exact visibility ordering. This is because the image resolution used for computing the visibility ordering relations is the same as that which is used for the actual volume rendering and we choose our A-buffer rays at the same sample points that are used to establish a polygon's pixel coverage during hardware scan conversion. Thus, the algorithm is image-space correct. The SXMPVO algorithm has several desirable features; among them are speed, simplicity of implementation, and no extra (i.e., with respect to MPVO) preprocessing.     

Evolution of T-spline level sets for meshing non-uniformly sampled and incomplete data

Given a large set of unorganized point sample data, we propose a new framework for computing a triangular mesh representing an approximating piecewise smooth surface. The data may be non-uniformly distributed, noisy, and may contain holes. This framework is based on the combination of two types of surface representations, triangular meshes and T-spline level sets, which are implicit surfaces defined by refinable spline functions allowing T-junctions. Our method contains three main steps. Firstly, we construct an implicit representation of a smooth (C ² in our case) surface, by using an evolution process of T-spline level sets, such that the implicit surface captures the topology and outline of the object to be reconstructed. The initial mesh with high quality is obtained through the marching triangulation of the implicit surface. Secondly, we project each data point to the initial mesh, and get a scalar displacement field. Detailed features will be captured by the displaced mesh. Finally, we present an additional evolution process, which combines data-driven velocities and feature-preserving bilateral filters, in order to reproduce sharp features. We also show that various shape constraints, such as distance field constraints, range constraints and volume constraints can be naturally added to our framework, which is helpful to obtain a desired reconstruction result, especially when the given data contains noise and inaccuracies.     

Turbine blade temperature transfer using the load surface method

Temperature transfer is important to MDA (multidisciplinary analysis) of turbine blades, for the separation of aerodynamics and structure analysis codes. To re-couple these codes, a load surface method is provided here to transfer temperature across the interface of arbitrarily meshed CFD (Computational Fluid Dynamics) and CSM (Computational Structural Mechanics) models. The idea of the method is to transfer temperature by a Bi-cubic B-spline surface, fitted from the CFD temperature results of interfaces in parametric space. The temperature of the CSM nodes of the interface is calculated from the load surface in the same parametric space. An important step in this transfer method is to map the CFD and CSM nodes into the same parametric space. The mapping surface method is detailed for this purpose. In the mapping method, the nodes are mapped onto a structured quad mesh, called a mapping surface, which is additionally generated on the interface surface. Then, the nodes are mapped into the parametric space, which is defined by a parameterization of the mapping surface. To evaluate the accuracy of the method, the temperature of a turbine blade is transferred experimentally. The result indicates that the method is accurate even for coarse meshes.     

Parallel three-dimensional mesh generation on distributed memory MIMD computers

This paper discusses the development of an automatic mesh generation technique designed to operate effectively on multiple instruction multiple data (MIMD) parallel computers. The meshing approach is hierarchical, that is, model entities are meshed after their boundaries have been meshed. Focus is on the region meshing step. An octree is constructed to serve as a localization tool and for efficiency. The tree is also key to the efficient parallelization of the meshing process since it supports the distribution of load to processors. The parallel mesh generation procedure repartitions the domain to be meshed and applies on processor face removals until all face removals with local data have been performed. The portion of the domain to be meshed remaining is dynamically repartitioned at the octant level using an Inertial Recursive Bisection method and local face removals are reperformed. Migration of a terminal octant involves migration of the octant data and the octant's mesh faces and/or mesh regions. Results show relatively good speed-ups for parallel face removals on small numbers of processors. Once the three-dimensional mesh has been generated, mesh regions may be scattered across processors. Therefore, a final dynamic repartitioning step is applied at the region level to produce a partition ready for finite element analysis.     

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.     

Coarse-to-fine surface reconstruction from silhouettes and range data using mesh deformation

We present a coarse-to-fine surface reconstruction method based on mesh deformation to build watertight surface models of complex objects from their silhouettes and range data. The deformable mesh, which initially represents the object visual hull, is iteratively displaced towards the triangulated range surface using the line-of-sight information. Each iteration of the deformation algorithm involves smoothing and restructuring operations to regularize the surface evolution process. We define a non-shrinking and easy-to-compute smoothing operator that fairs the surface separately along its tangential and normal directions. The mesh restructuring operator, which is based on edge split, collapse and flip operations, enables the deformable mesh to adapt its shape to the object geometry without suffering from any geometrical distortions. By imposing appropriate minimum and maximum edge length constraints, the deformable mesh, hence the object surface, can be represented at increasing levels of detail. This coarse-to-fine strategy, that allows high resolution reconstructions even with deficient and irregularly sampled range data, not only provides robustness, but also significantly improves the computational efficiency of the deformation process. We demonstrate the performance of the proposed method on several real objects.     

Completion and Reconstruction with Primitive Shapes

We consider the problem of reconstruction from incomplete point-clouds. To find a closed mesh the reconstruction is guided by a set of primitive shapes which has been detected on the input point-cloud (e.g. planes, cylinders etc.). With this guidance we not only continue the surrounding structure into the holes but also synthesize plausible edges and corners from the primitives' intersections. To this end we give a surface energy functional that incorporates the primitive shapes in a guiding vector field. The discretized functional can be minimized with an efficient graph-cut algorithm. A novel greedy optimization strategy is proposed to minimize the functional under the constraint that surface parts corresponding to a given primitive must be connected. From the primitive shapes our method can also reconstruct an idealized model that is suitable for use in a CAD system.     

CCSweep: automatic decomposition of multi-sweep volumes

CCSweep is a new method to automatically decompose multi-sweepable volumes into many-to-one sweepable volumes. Multi-sweepable volumes contain both multiple source and multiple target faces. In hexahedral mesh generation, most sweeping techniques handle many-to-one sweepable volumes that contain multiple source faces, but they are limited to volumes with only a single target face. Recent proposals to solve the multi-sweep problem have several disadvantages, including: indeterminate edge sizing or interval matching constraints, over-dependence on input mesh discretization, loop Boolean restrictions on creating only loops with even numbers of nodes, and unstable loop imprinting when interior holes exist. These problems are overcome through CCSweep. CCSweep decomposes multi-sweep volumes into many-to-one sweepable sub-volumes by projecting the target faces through the volume onto corresponding source faces. The projected faces are imprinted with the source faces to determine the decomposition of the solid. Interior faces are created to decompose the volume into separate new volumes. The new volumes have only single target faces and are represented in the meshing system as real, solid geometry, enabling them to be automatically meshed using existing many-to-one hexahedral sweeping approaches. The results of successful application of CCSweep to a number of problems are shown in this paper.Contract/grant sponsor: Sandia National Laboratories. Sandia National Laboratories is a multi-program laboratory operated by Sandia Corporation, a Lockheed Martin Company, for the United States Department of Energy under contract DE-AC04-94-AL85000.     

A piecewise hole filling algorithm in reverse engineering

While scanning a complex part in reverse engineering, it is not possible to acquire all part of the scanned surface. Data are inevitably missing due to the complexity of the scanned part or imperfect scanning process. Missing scanned data cause holes in the created triangular mesh, so that a hole-free mesh model is prerequisite for fitting watertight surfaces. Although a number of hole filling algorithms have been investigated, they enable to fill holes only on the smooth regions of a model. They are not always robust in the regions of high curvature. This paper proposes a novel methodology that can automatically fill complex polygonal holes with a piecewise manner. It incrementally splits a complex hole into several simple holes with respect to the 3D shape of the hole boundary, and then it consecutively fills each divided simple hole with planar triangulation method until the entire complex hole is firmly closed. Finally smoothing and subdivision techniques are applied for enhancing the hole triangles. The newly created vertices and triangles are added to their respective lists and the topology information is updated. The method has proven to be robust and effective from the result of test with a variety of complex holes. Examples are given and discussed to validate the methodology.     

从表面重构的体数据实现三维网格剖分

针对有限元分析中网格最优化问题,本文提出一种改进的生成四面体网格的自组织算法。该算法首先应用几何方法将三角形表面模型重新构造成规定大小的分类体数据,同时由该表面模型建立平衡八叉树,计算用以控制网格尺寸的三维数组;然后将体数据转换成邻域内不同等值面的形态一致的边界指示数组;结合改进的自组织算法和相关三维数据的插值函数,达到生成四面体网格的目的。实验对比表明,该方法能够生成更高比例的优质四面体,同时很好地保证了边界的一致。在对封闭的三维表面网格进行有限元建模时,本文算法为其提供了一种有效、可靠的途径。     

A sharpness-dependent filter for recovering sharp features in repaired 3D mesh models

This paper presents a sharpness-based method for hole-filling that can repair a 3D model such that its shape conforms to that of the original model. The method involves two processes: interpolation-based hole-filling, which produces an initial repaired model; and post-processing, which adjusts the shape of the initial repaired model to conform to that of the original model. In the interpolation-based hole-filling process, a surface interpolation algorithm based on the radial basis function creates a smooth implicit surface that fills the hole. Then, a regularized marching tetrahedral algorithm is used to triangulate the implicit surface. Finally a stitching and regulating strategy is applied to the surface patch and its neighboring boundary polygon meshes to produce an initial repaired mesh model, which is a regular mesh model suitable for post-processing. During post-processing, a sharpness dependent filtering algorithm is applied to the initial repaired model. This is an iterative procedure whereby each iteration step adjusts the face normal associated with each meshed polygon to recover the sharp features hidden in the repaired model. The experiment results demonstrate that the method is effective in repairing incomplete 3D mesh models.