Geodesic
Topology-preserving triangulation simplification algorithm by edge contraction
Fundamentalʹnaâ i prikladnaâ matematika, Tome 24 (2023) no. 3, pp. 153-169.

Voir la notice de l'article provenant de la source Math-Net.Ru

Triangulation is widely used to represent models of real objects in digital form, and often, in order to get the desired model, we need to triangulate it from data of another kind, for example, from a voxel model. There are methods that allow one to do it, but the resulting triangulation does not always have the desired quality. One way to solve this problem is triangulation simplification algorithms. However, they have disadvantages; in particular, in some cases they can destroy the model topology during the simplification process, which leads to the rejection of the simplification of the tetrahedral mesh in some local area. In this paper, we will consider the naive method of triangulation simplification using edge contraction, its shortcomings, and propose its modification that allows us to contract any edges without topology violations. 
@article{FPM_2023_24_3_a8,
     author = {Ya. S. Pepko and V. V. Borisenko},
     title = {Topology-preserving triangulation simplification algorithm by edge contraction},
     journal = {Fundamentalʹna\^a i prikladna\^a matematika},
     pages = {153--169},
     publisher = {mathdoc},
     volume = {24},
     number = {3},
     year = {2023},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/FPM_2023_24_3_a8/}
}
TY  - JOUR
AU  - Ya. S. Pepko
AU  - V. V. Borisenko
TI  - Topology-preserving triangulation simplification algorithm by edge contraction
JO  - Fundamentalʹnaâ i prikladnaâ matematika
PY  - 2023
SP  - 153
EP  - 169
VL  - 24
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/FPM_2023_24_3_a8/
LA  - ru
ID  - FPM_2023_24_3_a8
ER  - 
%0 Journal Article
%A Ya. S. Pepko
%A V. V. Borisenko
%T Topology-preserving triangulation simplification algorithm by edge contraction
%J Fundamentalʹnaâ i prikladnaâ matematika
%D 2023
%P 153-169
%V 24
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/FPM_2023_24_3_a8/
%G ru
%F FPM_2023_24_3_a8
Ya. S. Pepko; V. V. Borisenko. Topology-preserving triangulation simplification algorithm by edge contraction. Fundamentalʹnaâ i prikladnaâ matematika, Tome 24 (2023) no. 3, pp. 153-169. http://geodesic.mathdoc.fr/item/FPM_2023_24_3_a8/

[1] Botsch M., Kobbelt L., Pauly M., Alliez P., Levy B., Polygon Mesh Processing, Peters, 2010, 85–130

[2] Chan S. L., Purisima E. O., “A new tetrahedral tesselation scheme for isosurface generation”, Computers Graphics, 22:1 (1998), 83–90 | DOI

[3] Ciarlet P., Lamour F., “Does contraction preserve triangular meshes?”, Numerical Algorithms, 13 (1996), 201–223 | DOI | MR | Zbl

[4] Dey T. K., Edelsbrunner H., Guha S., Nekhayev D. V., “Topology preserving edge contraction”, Publ. Inst. Math., Nouv. Sér., 66(80) (1999), 23–45 | MR

[5] Doi A., Koide A., “An efficient method of triangulating equi-valued surfaces by using tetrahedral cells”, IEICE Trans. Inform. Systems, E74-D:1 (1991), 214–224

[6] Garland M., Quadric-Based Polygonal Surface Simplification, Carnegie Mellon Univ., 1998

[7] Garland M., “Multiresolution Modeling: Survey and Future Opportunities”, Eurographics 1999

[8] Garland M., Heckbert P. S., “Surface simplification using quadric error metrics”, Proc. of the 24th Annual Conf. on Computer Graphics and Interactive Techniques, SIGGRAPH'97, 1997, 209–216 | MR

[9] Heckbert P. S., Garland M., “Survey of Polygonal Surface Simplification Algorithms”, SIGGRAPH'97, Course Notes, 25, ACM Press, New York, 1997, 97 pp.

[10] Hoppe H., DeRose T., Duchamp T., McDonald J., Stuetzle W., “Mesh optimization”, Proc. of the 20th Annual Conf. on Computer Graphics and Interactive Techniques, SIGGRAPH'93, 1993, 19–26 | MR

[11] Munz T., Curvature-Adaptive Remeshing with Feature Preservation of Manifold Triangle Meshes with Boundary, Bournemouth Univ., 2015

[12] Skala V., “Precision of iso-surface extraction from volume data and visualization”, ALGORITHMY 2000: 15th Conf. on Scientific Computing, 2000, 368–378

[13] Song Y., Fellegara R., Iuricich F., De Floriani L., “Efficient topology-aware simplification of large triangulated terrains”, Proc. of the 29th Int. Conf. on Advances in Geographic Information Systems, SIGSPATIAL'21, 2021, 576–587

[14] Talton J. O., A Short Survey of Mesh Simplification Algorithms, Univ. Illinois at Urbana-Champaign, 2004

[15] Treece G. M., Prager R. W., Gee A. H., “Regularised marching tetrahedra: improved iso-surface extraction”, Computers Graphics, 23:4 (1999), 583–598 | DOI