Efficient Generation of High-Quality Unstructured Surface and Volume Grids

Procedures are presented for efficient generation of high-quality unstructured surface and volume grids. The overall procedure is based on the well proven Advancing Front/Local-Reconnection (AFLR) method. The AFLR triangular/tetrahedral grid generation procedure is a combination of automatic point creation, advancing type ideal point placement, and connectivity optimization schemes. A valid grid is maintained throughout the grid generation process. This provides a framework for implementing efficient local search operations using a simple data structure. It also provides a means for smoothly distributing the desired point spacing in the field using a point distribution function. This function is propagated through the field by interpolation from the boundary point spacing or by specified growth normal to the boundaries. Points are generated using either advancing- front type point placement for isotropic elements, advancing-point type point placement for isotropic right angle elements, or advancing-normal type point placement for high-aspect-ratio elements. The connectivity for new points is initially obtained by direct subdivision of the elements that contain them. Local-reconnection with a min-max type (minimize the maximum angle) type criterion is then used to optimize the connectivity. The overall procedure is applied repetitively until a complete field grid is obtained. An advancing-normal procedure is coupled with AFLR for anisotropic tetrahedral and pentahedral element grids. Advancing along prescribed normals from solid boundaries generates layers of anisotropic elements. The points are generated such that either pentahedral or tetrahedral elements with an implied connectivity can be directly recovered. The AFLR surface grid procedure uses an approximate physical space grid to define the surface during grid generation. The mapped space coordinates are mapped back to the actual surface at completion. Multiple surface definition patches are grouped into a single surface. A global mapping transformation is generated for the single surface using the grouped surface connectivity. The mapping coordinates are obtained by solving a coupled set of Laplacian equations. The overall procedure has been applied to a wide variety of configurations. Selected results are presented which demonstrate that high-quality unstructured grids can be efficiently and consistently generated for complex configurations.     

基于虚拟格网的建筑物点云轮廓线自动提取

在分析现有轮廓线提取方法不足的基础上，提出基于虚拟格网的建筑物轮廓线自动提取方法。该方法利用建筑物点云生成虚拟格网并进行二值填充；采用邻域分析方法进行边界格网的标记与追踪；为了避免边界追踪错误，设计了基于方向的单边缘格网抑制方法及基于距离的连接关系调整方法以改善提取结果质量；根据格网追踪结果，从原始建筑物点云中提取真实轮廓点以保持原始建筑物轮廓形态；采用随机抽样一致性估计及最小二乘拟合方法进行轮廓线规则化处理，实现建筑物轮廓线的自动提取。实验结果表明，该方法能快速从建筑物点云中提取轮廓线，可为建筑物轮廓线的自动提取提供一种可行的解决方案。     

一种快速三维散乱点云的三角剖分算法

改进了一种三维散乱点云三角剖分算法。三角剖分是点云数据曲面重构的主要算法之一,但针对三维散乱点云的三角剖分存在剖分效率不高,剖分得到的三角曲面形状无法控制,细节特征表现不足的问题。提出了基于空间栅格划分的三角剖分算法,并提出了一个新的评价函数,以控制三角网格曲面的生长。实验证明,改进后的算法极大的提高了剖分效率,而且能保证最终生成的三角网格曲面平滑而保有丰富的细节特征,适用于在虚拟现实、曲面重构等领域推广使用。     

A second-order curvilinear to Cartesian transformation of immersed interfaces and boundaries. Application to fictitious domains and multiphase flows

A global methodology dealing with fictitious domains of all kinds on curvilinear grids is presented. The main idea is to transform the curvilinear framework and its associated elements (velocity, immersed interfaces…) into a Cartesian grid. On such grids, many operations can be performed much faster than on curvilinear grids. The method is coupled with a Thread Ray-casting algorithm which works on Cartesian grids only. This algorithm computes quickly the Heaviside function related to the interior of an object on an Eulerian grid. The approach is also coupled with an immersed boundary method (L²-penalty) or with phase advection methods such as VOF–PLIC, VOF–TVD, Front-tracking or Level-set approaches. Applications, convergence and speed tests are performed for shape initializations, immersed boundary methods, and interface tracking.     

The Mesh Propagation Algorithm for Isosurface Construction

A new algorithm, Mesh Propagation, is presented for the generation of isosurfaces from three-dimensional discrete data sets. While producing the same surface mesh as that generated by a corrected Marching Cubes algorithm, its characteristic is that it constructs an isosurface using connected strips of dynamically triangulated polygons. This compact data structure speeds up surface construction and reduces surface storage requirements. The surface can also be displayed more quickly, particularly where there is hardware support for rendering triangle strips. With engineering as well as medical imaging applications in mind, the algorithm can be used with both irregular and rectilinear grids of data, the primitive volume elements need not be hexahedral only, and volumes of heterogeneous polyhedral elements are supported without traversal complications. The algorithm propagates through the cells in the grid and uses the same lookup table topologies as Marching Cubes to determine patches of surface-element intersection; additional tables are used for non-hexahedral elements. The surface patches are dynamically coded into triangle strips which are then concatenated and linked to construct the surface. The data structures used for propagating through the volume overcome the topological ambiguities associated with table-based methods of surface construction and no holes are generated in the final mesh.     

基于相交划分的动态网格聚类算法*

为了解决相交网格划分技术中聚类结果对数据输入顺序的依赖性和聚类结果精度不高的问题,提出了一种基于相交划分的动态网格聚类算法(DGBO)。该算法利用相交网格划分技术和移动网格技术来解决上述问题,通过连接相交的高密度网格单元形成聚类,只需一个参数,运行速度快。实验表明,DGBO算法能够快速有效地对任意形状、大小的数据集进行聚类,并能很好地识别出孤立点和噪声。     

A Procedure for Tetrahedral Boundary Layer Mesh Generation

. We develop a methodology for introducing regions of high anisotropy in existing isotropic unstructured grids in complex, curved, three-dimensional domains. The new procedures are here applied to the capturing of solution features in the proximity of model boundaries (e.g. boundary layers). Suitable voids are created in an existing grid in the regions of localization using a mesh motion algorithm that solves a fictitious elasticity problem. The voids are then filled with stacks of prisms that are subsequently tetrahedronized to yield a simplicial mesh. The mesh motion algorithm allows us to deal in a simple and effective manner with the problem of self-intersection of elements in concave regions of the model boundaries, and in the case of closely spaced model faces, avoiding the need for cross-over checks and complex grid correction procedures. The capabilities and performance of the proposed methodology are illustrated with the help of practical examples.     

Robust uniform triangulation algorithm for computer aided design

This paper presents a new robust uniform triangulation algorithm that can be used in CAD/CAM systems to generate and visualize geometry of 3D models. Typically, in CAD/CAM systems 3D geometry consists of 3D surfaces presented by the parametric equations (e.g. surface of revolution, NURBS surfaces) which are defined on a two dimensional domain. Conventional triangulation algorithms (e.g. ear clipping, Voronoi-Delaunay triangulation) do not provide desired quality and high level of accuracy (challenging tasks) for 3D geometry. The approach developed in this paper combines lattice tessellation and conventional triangulation techniques and allows CAD/CAM systems to obtain the required surface quality and accuracy. The algorithm uses a Cartesian lattice to divide the parametric domain into adjacent rectangular cells. These cells are used to generate polygons that are further triangulated to obtain accurate surface representation. The algorithm allows users to control the triangle distribution intensity by adjusting the lattice density. Once triangulated, the 3D model can be used not only for rendering but also in various manufacturing and design applications. The approach presented in this paper can be used to triangulate any parametric surface given in S(u,v) form, e.g. NURBS surfaces, surfaces of revolution, and produces good quality triangulation which can be used in CAD/CAM and computer graphics applications.     

Newton-Krylov-FAC methods for problems discretized on locally refined grids

Many problems in computational science and engineering are nonlinear and time-dependent. The solutions to these problems may include spatially localized features, such as boundary layers or sharp fronts, that require very fine grids to resolve. In many cases, it is impractical or prohibitively expensive to resolve these features with a globally fine grid, especially in three dimensions. Adaptive mesh refinement (AMR) is a dynamic gridding approach that employs a fine grid only where necessary to resolve such features. Numerous AMR codes exist for solving hyperbolic problems with explicit time stepping and some classes of linear elliptic problems. Researchers have paid much less attention to the development of AMR algorithms for the implicit solution of systems of nonlinear equations. Recent efforts encompassing a variety of applications demonstrate that Newton-Krylov methods are effective when combined with multigrid preconditioners. This suggests that hierarchical methods, such as the Fast Adaptive Composite grid (FAC) method of McCormick and Thomas, can provide effective preconditioning for problems discretized on locally refined grids. In this paper, we address algorithm and implementation issues for the use of Newton-Krylov-FAC methods on structured AMR grids. In our software infrastructure, we combine nonlinear solvers from KINSOL and PETSc with the SAMRAI AMR library, and include capabilities for implicit time stepping. We have obtained convergence rates independent of the number of grid refinement levels for simple, nonlinear, Poisson-like, problems. Additional efforts to employ this infrastructure in new applications are underway. Communicated by: G. Wittum     

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.     

一种去除机载LiDAR航带重叠区冗余点云的方法

机载LiDAR系统在获取高密度地表点云的同时,也带来了数据冗余的问题,特别是在航带重叠区中尤为突出。旨在研究无完整航迹信息辅助下去除航带重叠点,提出了基于点云GPS时间直方图的去除航带重叠点的方法。该方法包括三个步骤:(1)建立点云的GPS时间直方图,并根据GPS时间直方图特点获取航带重叠区外包矩形以及外包矩形中的所有点云;(2)考虑到城市中高密度点云有助于建筑物的三维重建,通过滤波分类处理获取建筑物点并予以全部保留;(3)对重叠区中除建筑物点外的其他所有点进行格网数据组织并根据GPS时间直方图逐格网去除航带冗余点。实验结果表明,该方法能较好地保留建筑物点的同时高效去除航带重叠点且不依赖于航迹信息,提高了后续数据分析处理的效率。     

基于LiDAR点云数据的三角网构建算法

在现有Delaunay三角网生长法的基础上进行改进,提出了一种三角网生长算法.该算法对大规模点云进行等格网分块,自适应确定搜索范围.通过在构建过程中对生成的基线进行分组和排序,动态删除封闭点,提高了构建三角网的速度;通过在整个点集范围内进行搜索,避免了通过插值所产生的误差和模块之间的拼接过程.利用此算法对大规模LiDAR点云数据进行构网,结果表明了该算法的有效性.     

基于均匀网格的Delaunay三角网算法在随机聚合网屏中的应用

Delaunay三角网一直是一个重要而有意义的研究课题，并具有极其广泛的用途。经过20多年来的研究，它的生成算法已趋于成熟。为了满足印刷、印染系统中随机聚合网屏生成的实时性需要，将一种将的算法引处到FM网屏技术中，并首先简要介绍了Delaunay三角网的牧场考及生成算法的分类；然后主要介绍了一种基于均匀网格的Delaunay三角网生成算法在随机聚合网屏中的应用；最后给出了算法的正确性证明。经测试，该算法的运算速度相当快，具有接近于线性的时间复杂性，能够满足排版印刷、印染系统中随机聚合网屏生成的需要。     

Stable free surface flows with the lattice Boltzmann method on adaptively coarsened grids

In this paper we will present an algorithm to perform free surface flow simulations with the lattice Boltzmann method on adaptive grids. This reduces the required computational time by more than a factor of three for simulations with large volumes of fluid. To achieve this, the simulation of large fluid regions is performed with coarser grid resolutions. We have developed a set of rules to dynamically adapt the coarse regions to the movement of the free surface, while ensuring the consistency of all grids. Furthermore, the free surface treatment is combined with a Smagorinsky turbulence model and a technique for adaptive time steps to ensure stable simulations. The method is validated by comparing the position of the free surface with an uncoarsened simulation. It yields speedup factors of up to 3.85 for a simulation with a resolution of 480³ cells and three coarser grid levels, and thus enables efficient and stable simulations of free surface flows, e.g. for highly detailed physically based animations of fluids.     

接地网故障诊断中的拓扑分解及其应用研究

为了对接地网进行故障诊断,通过对接地网支路拓扑结构进行分析,提出了一种以可及节点为裂点的分层拓扑分解方法,将接地网分解为元版块网、可及接地网和本征接地网。根据不同的数据结构,实现了接地网网络拓扑自动分解,明确了由拓扑结构决定的各层支路的关联性,采用结构判断和诊断后判断结合的方法对接地网支路的可测性进行了研究,可以自动识别诊断结果唯一确定的明晰支路,为科学利用诊断结果具有指导意义。对一个60支路的实验接地网采用所提出的算法进行分解和可测性判断,验证了提出的方法的正确性和实用性。     

Invariant image reconstruction from irregular samples and hexagonal grid splines

We present an algorithm for the reconstruction of images from irregularly placed samples, using linear splines with control points on a hexagonal grid. Several spline approximations are computed for different transformations of the control point grid (e.g. translations and rotations). These approximations are then merged together after compensation of the transformations, yielding a high-quality invariant image reconstruction. Evaluations show that the use of hexagonal grids of the “invariance by integration” principle improves reconstruction quality. An application to image coding is also presented.     

平面域Delaunay三角剖分新加密算法

根据Delaunay平面三角剖分的逐点插入法,设计出相应的点、线、三角形的数据结构.描述了从数据的预处理到加密网格生成的全过程.程序简单易实现,且能直接应用到数值计算.     

Adaptive discrete harmonic grid generation

We present a new adaptive-harmonic structured grid generation method. It is based on a functional that shares a common set of minimizers with Ivanenko’s harmonic functional [A.A. Charakhch’yan, S.A. Ivanenko, Curvilinear grids of convex quadrilaterals, Comput. Maths. Math. Phys. 28(2) (1988) 126–133.]. An unconstrained optimization process related to a continuation parameter is used to guarantee the convexity of the grid cells. Several numerical examples of grids generated on quite irregular 2D$2D$regions, show the effective performance of the proposed method and its robustness when preset monitor functions are given.     

曲率约束的隐式曲面三角网格化

提出一种有效的隐式曲面三角网格化算法。从隐式曲面上的一个种子点开始,生成网格的边界作为扩张多边形,且该多边形最小角对应的顶点为扩张点,计算从扩张点处欲生成的三角网格,为了防止新生成的三角网格和已经存在的三角网格重叠,要进行冲突检测。在隐式曲面三角网格化的过程中,扩张多边形是不断变化的,需要重复上述步骤,直至没有扩张多边形时结束。该算法分别应用于解析隐式曲面和变分隐式曲面的三角网格化。实验结果表明,该算法不需要重新网格化的步骤,生成的三角网格具有较高的质量,且三角网格随曲率适应性变化,因此说明了该算法的有效性。