Computational continuum physics is fast becoming an important part of biomedical research. Typically, the geometries for biomedical problems are derived from medical imaging modalities such as magnetic resonance imaging (MRI), and are geometrically complex compared to many engineering problems. Efficient unstructured mesh generation of these geometries remains challenging. Several excellent isotropic unstructured tetrahedral grid generation algorithms exist for creating finite-element or finite-volume grids from imaging-derived closed triangulated manifolds [1-3]. Isotropic algorithms, i.e. approaches that attempt to construct tetrahedral elements with nearly equal internal angles and approximately equal edge lengths, may be well suited to a large class of biomedical problems. However, for certain classes of problems such as computational fluid dynamics (CFD), isotropic elements may be neither necessary nor particularly appropriate. In boundary layer regions of the flow field, for example, derivatives normal to the wall can be much greater - even orders of magnitude greater for some Reynolds numbers - than they are parallel to the flow. Anisotropic grids can better resolve these features of the flow by concentrating computational grid at the wall while keeping the overall computational cost of the problem tractable. That efficiency applies to problems beyond CFD as well. Forecasts for petascale computing of plasma physics envision that a fourfold increase in speedup will come from adaptive gridding, while only a one-and-a-half-fold speedup will come from increased parallelism [4]. These forecasts apply just as forcefully to large-scale biomedical problems. Clearly the need for innovative algorithms that make efficient use of available resources still exists.

A layered anisotropic approach – whether advancing front or Delaunay - has the advantages of creating elements that are mostly orthogonal to the wall while essentially decoupling the grid density in the normal and tangential directions. That decoupling raises the issue of what criterion to adopt for the tangential density. With surfaces derived from imaging data, the organization and density of the original surface triangles are functions of the resolution of the digital data rather than the numerical problem to be solved. Simply generating a volume grid from the original surface spacing could result in grossly under-resolving of the computed field where the surface density is close to that of the local feature size or conversely over-resolving the computed field where the surface density is much finer than that of the local feature size. These observations lead to a consideration of the local feature size as an important criterion for sizing and gradation control of the surface that is complimentary to criteria that attempt to preserve surface features, topology and curvature.

In large part, previous attempts to base grid density on a concept of local feature-size or scale have either been based on the definition of “throw-away” background grids onto which a local feature-size field was computed, or have been based on point-insertion techniques to locally refine – but not derefine – coarse tetrahedral grids, or have been based on advancing fronts. As an example of an approach based on a pre-computed feature-size field, Persson recently defined a local feature-size field on a background grid. The feature field was defined locally as the sum of the distance of a given point to the boundary and to the medial axis. Element sizes were determined by gradient limiting competing local element size fields based on the feature field and the curvature field. The disadvantage of this and related approaches are twofold. First, the medial axis of a triangulated manifold is inherently unstable in the sense that small perturbations in the surface triangulation can lead to large perturbations in the medial axis and thus also in the definition of local feature size. Second, the construction and computation of a feature-size field on a ‘throw-away’ background grid is computationally expensive.

In contrast, we scale-invariant-mesh.ppt define a feature-size field on an input triangulated surface mesh without a background grid and without referencing the medial axis. Thus, determination of the feature-size field is not only computationally efficient, but also robust in the sense that it is continuous and does not change unreasonably under perturbation of the surface mesh. Field values at a point on the surface are generated by shooting a ray from the point in the direction of an inwards "synthetic" normal that is well-defined even where the surface is not smooth and measuring the distance until the surface is re-intersected by the ray. We then perform a gradient-limiting operation on the field to enforce continuity. Layered, conforming, anisotropic volume mesh generation is accomplished directly with this surface field. Prior to volume mesh generation, we modify the surface mesh so that edge length is proportional to the feature size field, with the constraint that refinement/de-refinement preserves topology and curvature. Surface modification is iterated with a volume-conserving smoothing, with the result that surface triangles are well-shaped, well-organized and graded. Following surface modification, layers of points are strategically placed along the rays normal to the surface to form layers of "virtual prisms" and connected into orthogonal layers with a constrained Delaunay algorithm. The resulting mesh is scale-invariant in that it is possible to obtain a desired number of layers across cross-sections in the domain, independent of scale.

  1. Si, H., On Refinement of Constrained Delaunay Tetrahedralizations. 2006, Weierstrass Institute for Applied Analysis and Stochastics: Berlin.
  2. Si, H., Adaptive tetrahedral mesh generation by constrained Delaunay refinement. 2006, Weierstrass Institute for Applied Analysis and Stochastics: Berlin.
  3. Baker, T.J. and J.C. Vassberg. Tetrahedral Mesh Generation and Optimization. in 6th International Conference on Numerical Grid Generation in Computational Field Simulation. 1998: International Society of Grid Generation.
  4. Sopics, M., Taking on the ITER Challenge, Scientists Look to Innovative Algorithms, Petascale Computers, in SIAM News. 2006.
Table sorting checkbox