Generation of finite element mesh with variable size over an unbounded 2D domain

With the advance of the finite element, general fluid dynamic and traffic flow problems with arbitrary boundary definition over an unbounded domain are tackled. This paper describes an algorithm for the generation of finite element mesh of variable element size over an unbounded 2D domain by using the advancing front circle packing technique. Unlike the conventional frontal method, the procedure does not start from the object boundary but starts from a convenient point within an open domain. The sequence of construction of the packing circles is determined by the shortest distance from the fictitious centre in such a way that the generation front is more or less a circular loop with occasional minor concave parts due to element size variation. As soon as a circle is added to the generation front, finite elements are directly generated by properly connecting frontal segments with the centre of the new circle. In contrast to other mesh generation schemes, the domain boundary is not considered in the process of circle packing, this reduces a lot of geometrical checks for intersection with frontal segments, and a linear time complexity for mesh generation can be achieved. In case the boundary of the domain is needed, simply generate an unbounded mesh to cover the entire object. As the element adjacency relationship of the mesh has already been established in the circle packing process, insertion of boundary segments by neighbour tracing is fast and robust. Details of such a boundary recovery procedure are described, and practical meshing problems are given to demonstrate how physical objects are meshed by the unbounded meshing scheme followed by the insertion of domain boundaries.     

Reconstructing high-order surfaces for meshing

We consider the problem of reconstructing a high-order surface from a given surface mesh. This problem is important for many meshing operations, such as generating high-order finite elements, mesh refinement, mesh smoothing, and mesh adaptation. We introduce two methods called Weighted Averaging of Local Fittings and Continuous Moving Frames. These methods are both based on weighted least squares polynomial fittings and guarantee C ⁰ continuity. Unlike existing methods for reconstructing surfaces, our methods are applicable to surface meshes composed of triangles and/or quadrilaterals, can achieve third and even higher order accuracy, and have integrated treatments for sharp features. We present the theoretical framework of our methods, their accuracy, continuity, experimental comparisons against other methods, and applications in a number of meshing operations.     

Generation of anisotropic mesh by ellipse packing over an unbounded domain

With the advance of the finite element method, general fluid dynamic and traffic flow problems with arbitrary boundary definition over an unbounded domain are tackled. This paper describes an algorithm for the generation of anisotropic mesh of variable element size over an unbounded 2D domain by using the advancing front ellipse packing technique. Unlike the conventional frontal method, the procedure does not start from the object boundary but starts from a convenient point within an open domain. The sequence of construction of the packing ellipses is determined by the shortest distance from the fictitious centre in such a way that the generation front is more or less a circular loop with occasional minor concave parts due to element size variation. As soon as an ellipse is added to the generation front, finite elements are directly generated by properly connecting frontal segments with the centre of the new ellipse. Ellipses are packed closely and in contact with the existing ellipses by an iterative procedure according to the specified anisotropic metric tensor. The anisotropic meshes generated by ellipse packing can also be used through a mapping process to produce parametric surface meshes of various characteristics. The size and the orientation of the ellipses in the pack are controlled by the metric tensor as derived from the principal surface curvatures. In contrast to other mesh generation schemes, the domain boundary is not considered in the process of ellipse packing, this reduces a lot of geometrical checks for intersection between frontal segments. Five examples are given to show the effectiveness and robustness of anisotropic mesh generation and the application of ellipse packing to mesh generation over various curved surfaces.     

Fitting Sharp Features with Loop Subdivision Surfaces

Various methods have been proposed for fitting subdivision surfaces to different forms of shape data (e.g., dense meshes or point clouds), but none of these methods effectively deals with shapes with sharp features, that is, creases, darts and corners. We present an effective method for fitting a Loop subdivision surface to a dense triangle mesh with sharp features. Our contribution is a new exact evaluation scheme for the Loop subdivision with all types of sharp features, which enables us to compute a fitting Loop subdivision surface for shapes with sharp features in an optimization framework. With an initial control mesh obtained from simplifying the input dense mesh using QEM, our fitting algorithm employs an iterative method to solve a nonlinear least squares problem based on the squared distances from the input mesh vertices to the fitting subdivision surface. This optimization framework depends critically on the ability to express these distances as quadratic functions of control mesh vertices using our exact evaluation scheme near sharp features. Experimental results are presented to demonstrate the effectiveness of the method.     

Bilateral normal filtering for mesh denoising

Decoupling local geometric features from the spatial location of a mesh is crucial for feature-preserving mesh denoising. This paper focuses on first order features, i.e., facet normals, and presents a simple yet effective anisotropic mesh denoising framework via normal field denoising. Unlike previous denoising methods based on normal filtering, which process normals defined on the Gauss sphere, our method considers normals as a surface signal defined over the original mesh. This allows the design of a novel bilateral normal filter that depends on both spatial distance and signal distance. Our bilateral filter is a more natural extension of the elegant bilateral filter for image denoising than those used in previous bilateral mesh denoising methods. Besides applying this bilateral normal filter in a local, iterative scheme, as common in most of previous works, we present for the first time a global, noniterative scheme for an isotropic denoising. We show that the former scheme is faster and more effective for denoising extremely noisy meshes while the latter scheme is more robust to irregular surface sampling. We demonstrate that both our feature-preserving schemes generally produce visually and numerically better denoising results than previous methods, especially at challenging regions with sharp features or irregular sampling.     

基于棱边约束的曲面体矩形片划分

对于带有特征的网格给出了一种将它们划分为一系列矩形片的算法．首先基于给定的一些特征，在网格上建立一个优化的三角剖分，在得到一系列的三角片或多边形片后，利用固定角保留的方法进行预处理；然后对这些三角片及多边形片之间的连接关系进行分类；最后针对不同的连接关系，定义相应的规则来提取矩形片．     

Automatic unstructured all-hexahedral mesh generation from B-Reps for non-manifold CAD assemblies

This paper describes an automatic and robust approach to convert non-manifold CAD assemblies into unstructured all-hexahedral meshes conformal to the given B-Reps (boundary-representations) and with sharp feature preservation. In previous works, we developed an octree-based isocontouring method to construct unstructured hexahedral meshes for arbitrary non-manifold and manifold domains. However, sharp feature preservation still remains a challenge, especially for non-manifold CAD assemblies. In this paper, boundary features such as NURBS (non-uniform rational B-Splines) curves and surface patches are first extracted from the given B-Reps. Features shared by multiple components are identified and distinguished. To preserve these non-manifold features, one given surface patch may need to be split into several small ones. An octree-based algorithm is then carried out to create an unstructured all-hexahedral base mesh, detecting and preserving all the sharp features via a curve and surface parametrization. Two sets of local refinement templates are provided for adaptive mesh generation, along with a novel 2-refinement implementation. Vertices in the base mesh are categorized into four groups based on the given non-manifold topology, and each group is relocated using various methods with all sharp features preserved. After this stage, a novel two-step pillowing technique is developed for such complicated non-manifold domains to eliminate triangle-shaped quadrilateral elements along the curves and “doublets”, handling non-manifold and manifold features in different ways. Finally, a combination of smoothing and optimization is used to further improve the mesh quality. Our algorithm is automatic and robust for non-manifold and manifold domains. We have applied our algorithm to several complicated CAD assemblies.     

Monocular 3D tracking of deformable surfaces using sequential second order cone programming

Reconstructing structures of deformable objects from monocular image sequences is important for applications like visual servoing and augmented reality. In this paper, we propose a method to recover 3D shapes of deformable surfaces using sequential second order cone programming (SOCP). The key of our approach is to represent the surface as a triangulated mesh and introduce two sets of constraints, one for model-to-image keypoint correspondences which are SOCP constraints, another for retaining the original lengths of the mesh edges which are non-convex constraints. In the process of tracking, the surface structure is iteratively updated by solving sequential SOCP feasibility problems in which the non-convex constraints are replaced by a set of convex constraints over a local convex region. The shape constraints used in our approach is more generic than previous methods, that enables us to reliably recover surface shapes with smooth, sharp and other complex deformations. The capability and efficiency of our approach are evaluated quantitatively with synthetic image sequences and qualitatively with real image sequences.     

从明暗恢复形状（SFS）的几类典型算法分析与评价

从明暗恢复形状（shape from shading,简称SFS）是计算机视觉中三维形状恢复问题的关键技术之一,其任务是利用单幅图象中物体表面的明暗变化来恢复其表面三维形状。为了使人们对SFC研究现状及求解SFS问题的各种算法的优缺点有个概略了解,首先介绍了求解传统SFS问题的4类方法中几个典型算法的基本原理及求解方法,并给出了实验结果,然后从算法解的唯一性、对真解的逼近程度、求解效率及适用范围等方面对这4类算法进行了比较和评价。     

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.     

A mesh generation method based on set theory

A method is proposed to study automatic generation of input data to finite element programs by the computer with minimal human involvement. Based on a set of objective criteria, a consistent procedure is developed to scan through the geometric idealization of a boundary to form regions for mesh generation. This procedure is supported by a rigorously built mathematical model. A cyclic set is defined according to the ordering of segments on a boundary. Corresponding to this is a quadrilateral set whose elements represent the partitioning of the geometry into regions for mesh generation. Theorems are proven establishing the uniqueness and completeness of this procedure. By means of this mathematical model, a computer program is written for automatic mesh generation together with evaluation of results by a given set of objective criteria.Examples are presented with simply connected and with multiply connected geometry.     

Feature-preserving surface mesh smoothing via suboptimal Delaunay triangulation

A method of triangular surface mesh smoothing is presented to improve angle quality by extending the original optimal Delaunay triangulation (ODT) to surface meshes. The mesh quality is improved by solving a quadratic optimization problem that minimizes the approximated interpolation error between a parabolic function and its piecewise linear interpolation defined on the mesh. A suboptimal problem is derived to guarantee a unique, analytic solution that is significantly faster with little loss in accuracy as compared to the optimal one. In addition to the quality-improving capability, the proposed method has been adapted to remove noise while faithfully preserving sharp features such as edges and corners of a mesh. Numerous experiments are included to demonstrate the performance of the method.     

基于能量最小化的网格优化算法

对网格优化的方法进行研究,提出一种基于能量最小化的网格优化算法.给定一定数量的三维散乱点数据和一个初始三角网格,使用能量最小化算法对网格顶点位置进行优化,使网格顶点更好地逼近三维散乱点数据;网格也更加逼近实际曲面.实验结果表明,使用该算法能够获得形状良好的网格.     

Surface mesh regeneration considering curvatures

This work describes an automatic algorithm for unstructured mesh regeneration on arbitrarily shaped three-dimensional surfaces. The arbitrary surface may be: a triangulated mesh, a set of points, or an analytical surface (such as a collection of NURBS patches). To be generic, the algorithm works directly in Cartesian coordinates, as opposed to generating the mesh in parametric space, which might not be available in all the cases. In addition, the algorithm requires the implementation of three generic functions that abstractly represent the supporting surface. The first, given a point location, returns the desired characteristic size of a triangular element at this position. The second method, given the current edge in the boundary-contraction algorithm, locates the ideal apex point that forms a triangle with this edge. And the third method, given a point in space and a projection direction, returns the closest point on the geometrical supporting surface. This work also describes the implementation of these three methods to re-mesh an existing triangulated mesh that might present regions of high curvature. In this implementation, the only information about the surface geometry is a set of triangles. In order to test the efficiency of the proposed algorithm of surface mesh generation and implementation of the three abstract methods, results of performance and quality of generated triangular element examples are presented.     

Bilateral recovering of sharp edges on feature-insensitive sampled meshes

A variety of computer graphics applications sample surfaces of 3D shapes in a regular grid without making the sampling rate adaptive to the surface curvature or sharp features. Triangular meshes that interpolate or approximate these samples usually exhibit relatively big error around the insensitive sampled sharp features. This paper presents a robust general approach conducting bilateral filters to recover sharp edges on such insensitive sampled triangular meshes. Motivated by the impressive results of bilateral filtering for mesh smoothing and denoising, we adopt it to govern the sharpening of triangular meshes. After recognizing the regions that embed sharp features, we recover the sharpness geometry through bilateral filtering, followed by iteratively modifying the given mesh's connectivity to form single-wide sharp edges that can be easily detected by their dihedral angles. We show that the proposed method can robustly reconstruct sharp edges on feature-insensitive sampled meshes.     

The discontinuous Galerkin finite element method for the 2D shallow water equations

A high-order finite element method, total variational diminishing (TVD) Runge–Kutta discontinuous Galerkin method is investigated to solve free-surface problems in hydraulic dynamics. Some cases of circular dam and rapidly varying two-dimensional flows are presented to show the efficiency and stability of this method. The numerical simulations are given on structured rectangular mesh for regular domain and on unstructured triangular mesh for irregular domain, respectively.     

子分曲面尖锐特征生成

虽然生成光滑曲面是自由曲面造型的一个主要追求目标,但在某些场合却又要求能够产生非光滑的特殊效果,即所谓的尖锐特征(sharp feature).该文研究子分曲面造型中特殊效果的生成,提出一种基于网格拓扑构造的方法,把折痕、角、尖刺和锥等尖锐特征的生成统一到边界处理方法中,从而避免了为各种效果建立特殊子分规则,并在不改变已有子分模式的情况下实现特殊尖锐特征造型.     

基于组合方法对图像的双三次多项式拟合

提出了基于图像数据构造拟合曲面的新方法.假设给定的图像数据所对应的原场景曲面能用分片二次多项式曲面表示,原场景曲面称为原曲面.现有方法通常是用图像数据作为插值数据构造原曲面的拟合曲面,而新方法以图像数据生成公式为约束,通过反向采样过程来构造对图像数据拟合的曲面,从而使拟合曲面具有更好的逼近精度.由于图像边缘处的质量对图像的视觉效果起着关键的作用,我们也把图像边缘做为约束条件用于拟合曲面的构造.对于每一个数据点及其邻近区域,新方法以采样公式和图像边缘作为约束条件局部地构造一张二次多项式曲面片,该曲面片具有二次多项式精度.所有的二次多项式曲面片的加权组合形成逼近原曲面的拟合曲面.对算法比较的实验表明,由新方法生成的放大图像具有较高的精度和较好的视觉效果.     

Parallel computer vision on a reconfigurable multiprocessor network

A novel reconfigurable architecture based on a multiring multiprocessor network is described. The reconfigurability of the architecture is shown to result in a low network diameter and also a low degree of connectivity for each node in the network. The mathematical properties of the network topology and the hardware for the reconfiguration switch are described. Primitive parallel operations on the network topology are described and analyzed. The architecture is shown to contain 2D mesh topologies of varying sizes and also a single one factor of the Boolean hypercube in any given configuration. A large class of algorithms for the 2D mesh and the Boolean n-cube are shown to map efficiently on the proposed architecture without loss of performance. The architecture is shown to be well suited for a number of problems in low and intermediate level computer vision such as the FFT, edge detection, template matching, and the Hough transform. Timing results for typical low and intermediate level vision algorithms on a transputer based prototype are presented