Abstract
We propose algorithms to incrementally modify a mesh of a planar domain by interactively inserting and removing elements (points, segments, polygonal lines, etc.) into or from the planar domain, keeping the quality of the mesh during the process. Our algorithms, that combine mesh improvement techniques, achieve quality by deleting, moving or inserting Steiner points from or into the mesh. The changes applied to the mesh are local and the number of Steiner points added during the process remains low. Moreover, our approach can also be applied to the directly generation of refined Delaunay quality meshes.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
1. N. Amenta, M. Bern and D. Epstein. Optimal point placement for mesh smoothing. In SODA:ACM-SIAM Symposium on Discrete Algorithms, 1997.
2. A. Bowyer. Computing Dirichlet Tessellations. Computer Journal, 24:2:162–166, 1981.
3. K. Clarkson and K. Mehlhorn and R. Seidel. Four results on randomized incremental constructions. Computational Geometry: Theory and Applications, 3:185–212, 1993.
4. O. Devillers. On deletion in Delaunay triangulation. 15th Annual ACM Symposium on Computational Geometry, 181–188, 1999.
5. L. Freitag and M. Jones and P. Plassmann. An efficient parallel algorithm for mesh smoothing. In Proceedings of the Fourth International Meshing Roundtable, 47–58, 1995.
6. N. Han-Wen and A.-F. van der Stappen. A Delaunay approach to interactive cutting in triangulated surfaces. In J.D. Boissonnat, J. Burdick, K. Goldbrg & S. Hutchinson (Eds.), Algorithmic Foundations of Robotics V, Springer-Verlag, 113–129, 2004.
7. S. Har-Peled and A. Üng ö r. A Time-Optimal Delaunay Refinement Algorithm in Two Dimensions. 21st Annual ACM Symposium on Computational Geometry (SoCG), 228–229, 2005.
8. M. Kallmann and H. Bieri and D. Thalmann. Fully Dynamic Constrained Delaunay Triangulation. Geometric Modelling For Scientific Visualization - Spring-Verlag, 2003.
9. C.-L. Lawson. Software for C 1 Surface Interpolation. Mathematical Software III(John R.Rice, editor), 161–194, 1977.
10. G.-L. Miller and S.-E. Pav and N.-J. Walkington. Fully incremental 3d Delaunay mesh generation. In Proceedings 11th International Meshing Roundtable, 75–86, 2002.
11. S.-E. Pav. Delaunay Refinement Algorithms. Department of Mathematical Sciences - Carnegie Mellon University - PhD thesis, 2003.
12. J. Ruppert. A Delaunay Refinement Algorithm for Quality 2-Dimensional Mesh Generation. Journal of Algorithms, 18:3:548–585, 1995.
13. J.-R. Shewchuk. Delaunay Refinement Mesh Generation. School of Computer Science - Carnegie Mellon University - PhD thesis, 1997.
14. D.-F. Watson. Computing the n-dimensional Delaunay Tessellation with Application to Voronoi Polytopes. Computer Journal, 24:2:167–172, 1981.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer
About this paper
Cite this paper
Coll, N., Guerrieri, M., Sellarès, J.A. (2006). Mesh Modification Under Local Domain Changes. In: Pébay, P.P. (eds) Proceedings of the 15th International Meshing Roundtable. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-34958-7_3
Download citation
DOI: https://doi.org/10.1007/978-3-540-34958-7_3
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-34957-0
Online ISBN: 978-3-540-34958-7
eBook Packages: EngineeringEngineering (R0)