2
$\begingroup$

I have been reading about Tetrahedral Mesh Refinement algorithms, but the literature covering this is very wide. My work involves implementation of different 3D computational geometry algorithms, and I have often experienced that an algorithm with very good theoretical complexity may be an implementational nightmare. Apart from the most cited articles (e.g. Shewchuk et al, and Si), what algorithms (with references please) are implemented in the open source mesh refinement libraries?

Ideally, the dynamical refinement algorithm should be Delaunay, because this allows tetrahedral cell agglomeration into polyhedral cells which then remain convex.

$\endgroup$
  • 1
    $\begingroup$ Have you looked at the implementation in the Computation Geometry Algorithms Library? You can also check this fairly comprehensive list of mesh generation software and see what references each of them cite for their underlying algorithms. $\endgroup$ – Daniel Shapero Jun 11 '13 at 10:58
  • 1
    $\begingroup$ Thanks. I am browsing through that all, but what I am interested is how can I filter out older/newer algorithms, that are more/less efficient? Are there review-papers comparing mesh quality, efficiency, etc? $\endgroup$ – tmaric Jun 11 '13 at 11:24
1
$\begingroup$

In the finite element community, many of us have come to the conclusion that it is easiest to just refine cells by bisection (which in the context of tetrahedra would mean subdividing each tetrahedron into 5 congruent ones) and then deal with the fact that there are vertices of the child cells that are not vertices of the neighboring cells if they happen not to be refined as well (these vertices are called "hanging nodes"). I don't know if that could apply to your problem as well, but it's proven to be simpler than the myriad ways of doing local mesh refinement while trying to guarantee shape regularity of cells.

Of course, in 2d, the algorithm to choose is red-green refinement. I imagine that there is an analogue for tetrahedra as well, but I don't know for sure.

$\endgroup$
  • 1
    $\begingroup$ In the finite volume context, the hanging node is taken care of easily when the mesh is hexahedral and the property is intensive: the adjacent cell is usually virtually split in the direction of the face split just for interpolation purposes. But for tetrahedra... I'm not sure if we can do that without introducing interpolation errors: non-orthogonality and aspect ratio increase (at least they do on my drawing :) ). $\endgroup$ – tmaric Jun 13 '13 at 7:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.