Dynamically refining animated triangle meshes for rendering

We present a method to dynamically apply local refinements to an irregular triangle mesh as it deforms in real time. The method increases surface smoothness in regions of high deformation by splitting triangles in a fashion similar to one or two steps of Loop subdivision. The refinement is computed for an arbitrary triangle mesh, and the subdivided triangles are simply passed to the rendering engine, leaving the mesh itself unchanged. The algorithm can thus be easily plugged into existing systems to enhance the visual appearance of animated meshes. The refinement step has very low computational overhead and is easy to implement. We demonstrate the use of the algorithm in a physics-based facial animation system.     

High order compact scheme with multigrid local mesh refinement procedure for convection diffusion problems

We derive a new fourth order compact finite difference scheme which allows different meshsize in different coordinate directions for the two-dimensional convection diffusion equation. A multilevel local mesh refinement strategy is used to deal with the local singularity problem. A corresponding multilevel multigrid method is designed to solve the resulting sparse linear system. Numerical experiments are conducted to show that the local mesh refinement strategy works well with the high order compact discretization scheme to recover high order accuracy for the computed solution. Our solution method is also shown to be effective and robust with respect to the level of mesh refinement and the anisotropy of the problems.     

A control approach for pore size distribution in the bone scaffold based on the hexahedral mesh refinement

Tissue engineering is the application of that knowledge to the building or repairing of tissues. Generally, engineered tissue is a combination of living cells and a support structure called scaffolds. Modeling, design and fabrication of tissue scaffold with intricate architecture, porosity and pore size for desired tissue properties presents a challenge in tissue engineering. In this paper, a control approach for pore size distribution in the bone scaffold based on the hexahedral mesh refinement is presented. Firstly, the bone scaffold modeling approach based on the shape function in the finite element method is provided. The resulting various macroporous morphologies can be obtained. Then conformal refinement algorithm for all-hexahedral element mesh is illustrated. Finally, a modeling approach for constructing tissue engineering (TE) bone scaffold with defined pore size distribution is presented. Before the conformal refinement of all-hexahedral element mesh, a 3D mesh with various hexahedral elements must be provided. If all the pores in the bone scaffold need to be reduced, that means that the whole hexahedral mesh needs to be refined. Then the solid entity can be re-divided with altered subdivision parameters. If the pores in the local regions of bone need to be reduced, that means that 3D hexahedral mesh in the local regions needs to be refined. Based on SEM images, the pore size distribution in the normal bone can be obtained. Then, according to the conformal refinement of all-hexahedral element meshes, defined hexahedral size distribution can be gained, which leads to generate defined pore size distribution in the bone scaffold, for the pore morphology and size are controlled by various subdivided hexahedral elements. Compared to other methods such as varying processing parameters in supercritical fluid processing and multi-interior architecture design, the method proposed in this paper enjoys easy-controllability and higher accuracy.     

Capturing expert knowledge of mesh refinement in numerical methods of impact analysis by means of genetic programming

The mesh refinement decisions of an experienced user of high-velocity impact numerical approximation finite differences computations are discovered as a set of comprehensible rules by means of Genetic Programming. These rules that could automatically trigger adaptive mesh refinement to mimic the expert user, detect mesh cells that require refinement by evolving a formula involving cell quantities such as material densities. Various cell variable combinations are investigated in order to identify the optimal ones for indicating mesh refinement. A high-velocity impact phenomena example of a tungsten ball that strikes a steel plate illustrates this methodology.     

Error bounds for Loop subdivision surfaces

In this paper, we obtain the error bounds on the distance between a Loop subdivision surface and its control mesh. Both local and global bounds are derived by means of computing and analysing the control meshes with two rounds of refinement directly. The bounds can be expressed with the maximum edge length of all triangles in the initial control mesh. Our results can be used as posterior estimates and also can be used to predict the subdivision depth for any given tolerance.     

医学体数据中基于局部特征尺寸的Delaunay四面体化算法*

为了从医学体数据构建面向虚拟手术仿真系统的器官实体模型,提出一种基于局部特征尺寸的Delaunay四面体化算法。首先采用Marching Cubes算法和外存模型简化技术从体数据中得到器官等值面简化模型,提出重心射线法去除内部冗余网格,获得器官多面体表面;然后基于局部特征尺寸构建表面顶点保护球,结合Delaunay细分算法生成边界一致的初始四面体网格;最后提出基于随机扰动的空间分解法快速生成内部节点,并逐点插入到四面体网格中优化单元质量。该算法克服了Delaunay细分算法无法处理锐角输入的缺点,并从理论     

Structured mesh generation by kriging with local refinement with a new elliptic scheme

Accurate results in finite element analysis are strongly related to mesh quality. In this paper, an automatic quadrilateral mesh generation methodology using kriging interpolation is described, a quality mesh study is conducted, and the development of a new local refinement scheme, called the elliptic scheme, is presented. The new elliptic refinement scheme is evaluated using four standard structural cases, and it is shown that it compares very well with octree-based refinement schemes and other local refinement methods.     

A new scheme for mesh generation and mesh refinement using graph theory

There are an extensive number of algorithms available from graph theory, some of which, for problems with geometric content, make graphs an attractive framework in which to model an object from its geometry to its discretization into a finite element mesh. This paper presents a new scheme for finite element mesh generation and mesh refinement using concepts from graph theory. This new technique, which is suitable for an interactive graphical environment, can also be used efficiently for fully automatic remeshing in association with self-adaptive schemes. Problems of mesh refinement around holes and local mesh refinement are treated. The suitability of the algorithms presented in this paper is demonstrated by some examples.     

Refinement and coarsening of surface meshes

This paper presents an adaptation scheme for surface meshes. Both refinement and coarsening tools are based upon local retriangulation. They can maintain the geometric features of the given surface mesh and its quality as well. A mesh gradation tool to smooth out large size differences between neighboring (in space) mesh faces and a procedure to detect and resolve self-intersections in the mesh are also presented. Both are driven by an octree structure and make use of the presented refinement tool.     

Progressive Lossless Mesh Compression Via Incremental Parametric Refinement

In this paper, we propose a novel progressive lossless mesh compression algorithm based on Incremental Parametric Refinement, where the connectivity is uncontrolled in a first step, yielding visually pleasing meshes at each resolution level while saving connectivity information compared to previous approaches. The algorithm starts with a coarse version of the original mesh, which is further refined by means of a novel refinement scheme. The mesh refinement is driven by a geometric criterion, in spirit with surface reconstruction algorithms, aiming at generating uniform meshes. The vertices coordinates are also quantized and transmitted in a progressive way, following a geometric criterion, efficiently allocating the bit budget. With this assumption, the generated intermediate meshes tend to exhibit a uniform sampling. The potential discrepancy between the resulting connectivity and the original one is corrected at the end of the algorithm. We provide a proof-of-concept implementation, yielding very competitive results compared to previous works in terms of rate/distortion trade-off.     

Local refinement based on the 7-triangle longest-edge partition

The triangle longest-edge bisection constitutes an efficient scheme for refining a mesh by reducing the obtuse triangles, since the largest interior angles are subdivided. In this paper we specifically introduce a new local refinement for triangulations based on the longest-edge trisection, the 7-triangle longest-edge (7T-LE) local refinement algorithm. Each triangle to be refined is subdivided in seven sub-triangles by determining its longest edge. The conformity of the new mesh is assured by an automatic point insertion criterion using the oriented 1-skeleton graph of the triangulation and three partial division patterns.     

Approximate Shape Quality Mesh Generation

We present two techniques for simplifying the list processing required in standard iterative refinement approaches to shape quality mesh generation. The goal of these techniques is to gain simplicity of programming, efficiency in execution, and robustness of termination. ‘Shape quality’ for a mesh generation method usually means that, under suitable conditions, a mesh with all angles exceeding a prescribed tolerance is generated. The methods introduced in this paper are truncated versions of such methods. They depend on the shape improvement properties of the terminal-edge LEPP-Delaunay refinement technique; we refer to them as approximate shape quality methods. They are intended for geometry-based preconditioning of coarse initial meshes for subsequent refinement to meet data representation needs. One technique is an algorithm re-organization to avoid maintaining a global list of triangles to be refined. The re-organization uses a recursive triangle processing strategy. Truncating the recursion depth results in an approximate method. Based on this, we argue that the refinement process can be carried out using a static list of the triangles to be refined that can be identified in the initial mesh. Comparisons of approximate to full shape quality meshes are provided.     

A posteriori error estimation in sensitivity analysis

We present a posteriori error estimators suitable for automatic mesh refinement in the numerical evaluation of sensitivity by means of the finite element method. Both diffusion (Poisson-type) and elasticity problems are considered, and the equivalence between the true error and the proposed error estimator is proved. Application to shape sensitivity is briefly addressed.     

Numerical simulation of multiple 3D fracture propagation using arbitrary meshes

This paper describes a mesh-independent finite element based method for propagating fractures in three dimensions. The iterative algorithm automatically grows fractures in a 3D brittle medium represented by an isotropic linear elastic matrix. Growth is controlled by an input failure and propagation criterion. The geometry and mesh are stored separately, and mesh refinement is topologically guided. Propagation results in the modification of crack geometry, as opposed to changes in the mesh, as the arbitrary tetrahedral mesh adapts to the evolving geometry. Stress intensity factors are computed using the volumetric J Integral on a virtual piecewise cylinder. Modal stress intensity factors are computed using the decomposition method. Mesh and cylinder size effects are studied, as is computational efficiency. A through-going crack embedded in a thick slab, and a horizontal and inclined penny-shape crack, are used to validate the accuracy of the method. The predicted stress intensity factors are in good agreement with analytical solutions. For six integration points per tip segment, integration local to single tips, and a cylinder radius that adapts to the local geometric conditions, results agree with analytical solutions with less than 5% deviation from experimental results.     

Online Mesh Refinement for Parallel Atmospheric Models

Forecast precisions of climatological models are limited by computing power and time available for the executions. As more and faster processors are used in the computation, the resolution of the mesh adopted to represent the Earth’s atmosphere can be increased, and consequently the numerical forecast is more accurate. However, a finer mesh resolution, able to include local phenomena in a global atmosphere integration, is still not possible due to the large number of data elements to compute in this case. To overcome this situation, different mesh refinement levels can be used at the same time for different areas of the domain. Thus, our paper evaluates how mesh refinement at run time (online) can improve performance for climatological models.The online mesh refinement (OMR) increases dynamically mesh resolution in parts of a domain,when special atmosphere conditions are registered during the execution. Experimental results show that the execution of a model improved by OMR provides better resolution for the meshes, without any significant increase of execution time. The parallel performance of the simulations is also increased through the creation of threads in order to explore different levels of parallelism.     

An algorithm for adaptive mesh refinement inn dimensions

The author describes a fast algorithm for local adaptive mesh refinement inn dimensions based on simplex bisection. A ready-to-use implementation of the algorithm in C++ pseudocode is given. It is proven that the scheme satisfies all conditions one usually places on grid refinement in the context of finite-element calculations. Bisection refinement also offers an interesting additional feature over the usual, regular, refinement scheme: all linear finite-element basis functions of one generation are of disjoint support. In the way the scheme is presented here, all generated simplex meshes satisfy a ‘structural condition’ which is exploited to simplify bookkeeping of the neighbour graph. However, bisection refinement places certain restrictions on the initial, coarsest grid. For a simply connected domain, a precise and useful criterion for the applicability of the described refinement scheme is formulated and proven.     

An augmented Lagrangian approach to Bingham fluid flows in a lid-driven square cavity with piecewise linear equal-order finite elements

We study an augmented Lagrangian approach to Bingham fluid flows in a lid-driven square cavity. The piecewise linear equal-order finite element spaces for both the velocity and the pressure approximations, proposed and analyzed by Latché and Vola [18], are applied. Based on the resulting regularity of the numerical solutions, a mesh adaptive strategy is proposed to render the yield surfaces of desired resolution. The corresponding numerical scheme is formulated for general Herschel–Bulkley models, and its validity is verified on the benchmark model: Bingham fluid flows in a lid-driven square cavity.     

Can local NURBS refinement be achieved by modifying only the user interface?

NURBS patches have a serious restriction: they are constrained to a strict rectangular topology. This means that a request to insert a single new control point will cause a row of control points to appear across the NURBS patch, a global refinement of control. We investigate a method that can hide unwanted control points from the user so that the user’s interaction is with local, rather than global, refinement. Our method requires only straightforward modification of the user interface and the data structures that represent the control mesh, making it simpler than alternatives that use hierarchical or T-constructions. Our results show that our method is effective in many cases but has limitations where inserting a single new control point in certain cases will still cause a cascade of new control points to appear across the NURBS patch.     

Massively parallel adaptive mesh refinement and coarsening for dynamic fracture simulations

We use the graphical processing unit (GPU) to perform dynamic fracture simulation using adaptively refined and coarsened finite elements and the inter-element cohesive zone model. Due to the limited memory available on the GPU, we created a specialized data structure for efficient representation of the evolving mesh given. To achieve maximum efficiency, we perform finite element calculation on a nodal basis (i.e., by launching one thread per node and collecting contributions from neighboring elements) rather than by launching threads per element, which requires expensive graph coloring schemes to avoid concurrency issues. These developments made possible the parallel adaptive mesh refinement and coarsening schemes to systematically change the topology of the mesh. We investigate aspects of the parallel implementation through microbranching examples, which has been explored experimentally and numerically in the literature. First, we use a reduced-scale version of the experimental specimen to demonstrate the impact of variation in floating point operations on the final fracture pattern. Interestingly, the parallel approach adds some randomness into the finite element simulation on the structured mesh in a similar way as would be expected from a random mesh. Next, we take advantage of the speedup of the implementation over a similar serial implementation to simulate a specimen whose size matches that of the actual experiment. At this scale, we are able to make more direct comparisons to the original experiment and find excellent agreement with those results.     

一种网格和节点同步生成的二维Delaunay网格划分算法

应用Lawson算法对网格的Delaunay性质进行维护,利用单元尺度场控制生成网格的疏密分布;找到任一不满足尺度场要求的单元,在其可插度最大的边上按一定法则插入新节点,加密网格,实现内节点的生成与网格划分同步进行.该算法避免了搜寻包含三角形的过程,提高了效率.通过多次划分实验表明,该算法的时间复杂度约为O(N1.2).同时,由于在不满足单元尺寸要求的单元边上插入新节点,直接对单元的边长进行控制,使得网格的质量和自适性更加良好.