Strang and Persson [1] suggested simple self-organization Delaunay meshing algorithm in implicit domains based on signed distance function which measures distance from domain boundary. It is based on application of nonlinear elastic repulsive forces along current Delaunay edges acting like nonlinear struts. Projection of vertices which go out outside domain back to its boundary serves as a barrier against this repulsion.
Behaviour of the algorithm resembles filling of a volume by expanding industrial foam. Computational kernel of this algorithm is fully contained in one page of Matlab code.
In Belousova, Garanzha [2] it was suggested modification of this algorithm which is based on general signed implicit function modelling domain bounadry as zero isosurface and which does not require computation of costly precise distance function. Remarkable property of self-organization algorithm is topological regularity of resulting mesh. Connectivity of triangular surface mesh which is constructed simultaneously with tetrahedral one is very close to regular. In [3] Garanzha, Kudryavtseva suggested to combine self-organization algorithm with special edge sharpening technique which gradually orient mesh faces and edges aligning them which sharp edges and conical points on implicit boundary. Additional elastic forces were added in order to prevent appearance of slivers (flat teterahedra). Resulting algorithm was found to be quite powerful tool for general implicit domains which works in a black box mode. Unfortunately indiscriminate application of sharpening forces may lead to larger degree of topological irregularity of resulting mesh. In order to resolve this problem we suggest adaptive version of sharpening forces based on computation of discrete Laplace-Beltrami operator due to Floater [4] on approximate boundary of implicit domain. It provides threshold for robust application of sharpening. This modification of algorithm allowed to retain high quality edge recovery while restoring topological regularity of resulting mesh. Newly developed C/C++ -version of self-organization algorithm was found to be much faster compared to Matlab version from [3] which allowed sharp increase of the target mesh size and complexity of domains.
1) P.-O. Persson, G. Strang, A Simple Mesh Generator in MATLAB. SIAM Review, Vol. 46 (2), pp. 329-345, June 2004.
2) L.N. Belousova, V.A. Garanzha, Compare global optimization algorithm of computational grids. Computational Mathematics: Proceedings of the XIV Baikal International School-Seminar "Optimization Methods and their Applications", Irkutsk, Baikal, July 2-8, 2008. Volume 3: Irkutsk, ESI RAN.-2008.-183 p.
3) V.A. Garanzha, L.N. Kudryavtseva, Generation of three-dimensional delaunay meshes from weakly structured and inconsistent data. Computational Mathematics and Mathematical Physics 52 (3), 427-447
4) Floater M.S., Hormann K. Surface parameterization: a tutorial and survey. In: Advances in multiresolution for geometric modelling. Berlin: Springer; 2005. p. 157–86.