Global balancing of a triangular mesh

Authors

  • Denis D. Vasilkov Belarusian State University, Niezaliežnasci Avenue, 4, 220030, Minsk, Belarus

Keywords:

triangulation, mesh generation, mesh refinement, Steiner points, triangular mesh topology, least squares method, interpolation error

Abstract

New algorithm for Steiner triangular mesh balancing is proposed. The algorithm is based on the least squares method and minimizes the standart deviation of triangulation angles cosines from the optimal value of 0.5. The algorithm has no limitations and therefore can be applied to any triangulations obtained by triangular mesh refinement algorithms, for example Ruppert or Erten and Üngör algorithms, without increasing the resulting number of points and without breaking the edge connections. Experiments indicate that the proposed algorithm significantly increases the number of angles in range from 50 to 70° and doesnʼt lead to create triangles with significantly smaller minimum angles. The algorithm can be effectively implemented using specialized software packages for quick solving sparse linear systems using the leastsquares method, for example SuiteSparse. Therefore the algorithm is easy to implement.

Author Biography

  • Denis D. Vasilkov, Belarusian State University, Niezaliežnasci Avenue, 4, 220030, Minsk, Belarus

    assistant at the department of discrete mathematics and algorithms, faculty of applied mathematics and computer science

References

  1. Farin G. Curves and surfaces for CAGD. 4th ed. San Diego : Acad. Press, 1997.
  2. Shewchuk J. R. What is a good linear finite element? In: 11th International Meshing Roundtable (New York, 15–18 Sept., 2002). New York : Ithaca, 2002. P. 115–126.
  3. Paul Chew L. Guaranteed-quality mesh generation for curved surfaces. In: Proceedings of the Ninth Annual Symposium on Computational Geometry (San Diego, 18–21 May, 1993). New York : ACM, 1993. P. 274 –280.
  4. Ruppert J. A Delaunay refinement algorithm for quality 2-dimensional mesh generation. J. Algorithms. 1995. Vol. 18, issue 3. P. 548–585. DOI: 10.1006/jagm.1995.1021.
  5. Erten H., Üngör A. Triangulations with locally optimal steiner points. In: Eurographics Symposium on Geometry Processing (Barcelona, 4 – 6 July, 2007). Barcelona, 2007. P. 1–10.
  6. Paige C. C., Saunders M. A. LSQR: An algorithm for sparse linear equations and sparse least squares. ACM Trans. Math. Soft. 1982. Vol. 8, issue 1. P. 43–71. DOI: 10.1145/355984.355989.
  7. Rennich S., Stosic D., Davis T. A. Accelerating sparse cholesky factorization on GPUs. Architectures and Algorithms : IA3 Seventh Workshop on Irregul. Appl. (Denver, 13 Novemb., 2017). New Orleans, 2014.

Downloads

Published

2018-05-05

Issue

No. 1 (2018): Journal of the Belarusian State University. Mathematics and Informatics

Section

Discrete Mathematics and Mathematical Cybernetics

License

The authors who are published in this journal agree to the following:

  1. The authors retain copyright on the work and provide the journal with the right of first publication of the work on condition of license Creative Commons Attribution-NonCommercial. 4.0 International (CC BY-NC 4.0).
  2. The authors retain the right to enter into certain contractual agreements relating to the non-exclusive distribution of the published version of the work (e.g. post it on the institutional repository, publication in the book), with the reference to its original publication in this journal.
  3. The authors have the right to post their work on the Internet (e.g. on the institutional store or personal website) prior to and during the review process, conducted by the journal, as this may lead to a productive discussion and a large number of references to this work. (See The Effect of Open Access.)

How to Cite

[1]
Vasilkov, D.D. 2018. Global balancing of a triangular mesh. Journal of the Belarusian State University. Mathematics and Informatics. 1 (May 2018), 88–94.