Sink Insertion for Mesh Improvement
Center for Simulation of Advanced Rockets (CSAR),
Center for Process Simulation and Design (CPSD),
Computational Science and Engineering Program (CSE),
University of Illinois at Urbana-Champaign (UIUC)
Herbert Edelsbrunner (Duke University) and
Damrong Guoy
sink_IJFCS_Vol13_No2_April_2002.pdf (PDF 3.1 MB)
H. Edelsbrunner and D. Guoy.
Sink Insertion for Mesh Improvement.
International Journal of Foundations of Computer Science,
Vol. 13 No. 2, April 2002, 223--242
sinkTalk.ppt (Microsoft PowerPoint 4 MB). Presentation slides. General ideas of sink-insertion.
http://www.cse.uiuc.edu/~guoy/sink/sinkTalk/index.html for html format.
Collaborators :-
Computer Science : Herbert Edelsbrunner, Shang-Hua Teng, Tamal Dey, Damrong Guoy,
Cinda Heeren, Xiangyang Li, Alla Sheffer, Alper Ungor
Mathematics : Daniel Grayson, John Sullivan
Engineering: Robert Haber, Jonathan Dantzig
We propose sink-insertion as a new technique to improve the mesh quality
of Delaunay triangulations.
In three dimensions, sink-insertion can eliminate all kinds of poor-quality
tetrahedral elements except slivers.
After sink-insertion, we can perform
sliver-exudation to
eliminate the remaining small slivers.
The idea of sink-insertion came from analysis of
distant function from a discrete point set in Euclidean space.
One definition of sink is local maximum of square distance
from a discrete point set.
In three dimensions, such a point is Voronoi vertex that lies in its dual
Delaunay tetrahedron.
In otherwords, a sink is the circumcenter z of a Delaunay tetrahedron tau
such that z lies in tau.
usa206.wrl (VRML).
An example in two dimensions of initial triangular mesh with sinks in brown triangles.
usa206_s_1.00_SB.wrl (VRML).
usa206 after sink-insertion with r/l threshold 1.0.
Link (html)
to nine types of poor-quality tetrahedra.
stlf01 model
stlf01.jpg (image).
Full-size image of stlf01 model from professor Jonathan Dantzig.
Short report on Tetrahedral Mesh Improvement of Stlf01
stlf01.ps (postscript)
VRML model of
1,171 tetrahedral elements with r/l greater than 3.5.
VRML model of
171 tetrahedral elements with v/l^3 less than 0.01.
They are what we call slivers.
Prepared by Damrong Guoy
Last modification : Sun May 13, 2007
