Technical note
Merging of intersecting triangulations for finite element modeling

https://doi.org/10.1016/S0021-9290(01)00018-5Get rights and content

Abstract

Surface mesh generation over intersecting triangulations is a problem common to many branches of biomechanics. A new strategy for merging intersecting triangulations is described. The basis of the method is that object surfaces are represented as the zero-level iso-surface of the distance-to-surface function defined on a background grid. Thus, the triangulation of intersecting objects reduces to the extraction of an iso-surface from an unstructured grid. In a first step, a regular background mesh is constructed. For each point of the background grid, the closest distance to the surface of each object is computed. Background points are then classified as external or internal by checking the direction of the surface normal at the closest location and assigned a positive or negative distance, respectively. Finally, the zero-level iso-surface is constructed. This is the final triangulation of the intersecting objects. The overall accuracy is enhanced by adaptive refinement of the background grid elements. The resulting surface models are used as support surfaces to generate three-dimensional grids for finite element analysis. The algorithms are demonstrated by merging arterial branches independently reconstructed from contrast-enhanced magnetic resonance images and by adding extra features such as vascular stents. Although the methodology is presented in the context of finite element analysis of blood flow, the algorithms are general and can be applied in other areas as well.

Introduction

Accurate reconstruction of 3D anatomical surfaces is essential for image-based, patient-specific finite element analysis. Typical problems related to overlapping and intersecting close anatomical structures can be avoided by using semi-automatic deformable models to segment separately different parts of a given structure. However, before generating a finite element grid, it is necessary to merge the resulting triangulations into a single, “water-tight” surface, i.e. with no holes, gaps or self-intersections. This is a problem common to many biomedical engineering disciplines.

The particular case of computational fluid dynamics modeling of blood flow requires an accurate reconstruction of the vessel lumen (Moore et al (1998), Moore et al (1999)). Typically, the finite element grid generation is done either from an analytical representation of the computational domain (Long et al., 2000; Quarteroni et al., 2000; Taylor et al., 1999; Zhao et al., 2000) or directly from a discrete surface representation (Nielsen et al., 1991; Cebral and Löhner, 2001; Ladak et al., 2000). The former approach requires an extra step to fit analytical surface patches after segmentation. The latter approach requires a “water-tight” surface triangulation to define the domain. If objects are defined from overlapping components, it is necessary to generate surface grids over intersecting triangulations prior to the finite element mesh generation. The traditional solution to this non-trivial problem has been to calculate the geometric intersection between the surface triangulations (Lo, 1995; Shostko et al., 1999). The triangulations resulting from this approach tend to have very distorted elements, and cannot account for narrow gaps that should be closed as they are too small for any meaningful fluid simulation.

This paper describes a new algorithm to triangulate intersecting surfaces. It is used in combination with a cylindrical deformable model segmentation technique developed by Yim et al. (2001) to create anatomically realistic surface models of arteries from magnetic resonance angiography (MRA) images. These triangulations are then used as support surfaces to generate finite element grids for hemodynamics calculations (Cebral and Löhner, 2001). Adaptive background grids are used to control the accuracy of the procedure. The main advantage of this fully automatic surface-merging algorithm is that it reduces the problem of intersecting triangulations to the extraction of an iso-surface, therefore it is very simple and straightforward to implement. Moreover, it avoids the problem of badly formed triangles and narrow gaps encountered in traditional approaches.

Section snippets

Methods

The basis of our merging technique is the representation of the object surfaces as iso-surfaces of a scalar function defined on a background grid. The scalar function is the shortest distance to the object surface. Assigning a negative distance to points that lie inside a surface and a positive distance to those outside, the object surface can be recovered by extracting the iso-surface of zero distance. The merging proceeds by first computing the shortest absolute distance to any object and

Results

The methodology was first applied to the merging of surface models representing the internal and external carotid arteries of a normal subject. Each branch was individually reconstructed from contrast-enhanced MRA images of a normal volunteer using a cylindrical deformable model (Figs. 1a and b). A fine background grid with no adaptation was used to generate a surface triangulation over the intersecting arterial branches (Fig. 1c). This merged model was then used to generate a volumetric finite

Discussion

The combination of the present surface-merging algorithm with segmentation procedures based on deformable models can be successfully used to construct anatomically realistic models free of intersections with other close structures. These surface triangulations, which are free of badly formed triangles, can then be used to generate 3D grids for finite element analysis.

Since the surface-merging approach is based on the extraction of the iso-surface of zero distance, the initial object

References (16)

  • H. Hoppe

    Efficient Implementation of progressive meshes

    Computers & Graphics

    (1998)
  • R. Löhner

    Regridding Surface Triangulations

    Journal of Computational Physics

    (1996)
  • S.Z. Zhao et al.

    Blood flow and vessel mechanics in a physiologically realistic model of a human carotid arterial bifurcation

    Journal of Biomechanics

    (2000)
  • Cebral, J.R., Lohner, R., 2001. From medical images to anatomically accurate finite element grids. International...
  • H.M. Ladak et al.

    Rapid 3D segmentation of the carotid bifurcation from serial MR images

    Journal of Biomechanical Engineering

    (2000)
  • H.S. Lo

    Automatic mesh generation over intersecting surfaces

    International Journal for Numerical Methods in Engineering

    (1995)
  • R. Löhner

    Some useful data structures for the generation of unstructured grids

    Communications in Applied Numerical Methods

    (1988)
  • R. Löhner et al.

    Adaptive H-refinement on 3-D unstructured grids for transient problems

    International Journal for Numerical Methods in Fluids

    (1992)
There are more references available in the full text version of this article.

Cited by (71)

  • Virtual interventions for image-based blood flow computation

    2012, CAD Computer Aided Design
    Citation Excerpt :

    In the former approach [25,26], a surface mesh is deformed by internal forces computed from surface features, e.g. curvature, as well as external forces computed from the image, e.g. gradient. This approach has limitations when segmenting large portions of the vasculature because of its inflexibility to handle complex shape and topology changes, although merging of smaller segmentations is possible [27]. The level set method overcomes this difficulty by implicitly representing the surface as the zero level of a higher dimensional function [28] and has been successfully applied to segment vascular images [20,23,29] using variants of forcing terms, e.g. [30].

  • Computational fluid dynamics for evaluating hemodynamics

    2019, Vessel Based Imaging Techniques: Diagnosis, Treatment, and Prevention
  • Dynamic and implicit coupling of non-matching meshes

    2018, 10th International Conference on Computational Fluid Dynamics, ICCFD 2018 - Proceedings
  • Intracranial aneurysms: Imaging, hemodynamics, and remodeling

    2017, Molecular, Genetic, And Cellular Advances In Cerebrovascular Diseases
View all citing articles on Scopus
View full text