×

Multivariate topology simplification. (English) Zbl 1367.65027

Let \({\mathbb X}\) be a codimension-\(0\) submanifold of \({\mathbb R}^d\), and \(f:{\mathbb X}\rightarrow{\mathbb R}^r\). A point \({\mathbf x}\in{\mathbb X}\) is regular if the differential map of \(f\) at \({\mathbf x}\) has maximal rank, and is singular otherwise. The Jacobi set is the union of the singular points of \(f\) when restricted to the interior and to the boundary of \({\mathbb X}\). The fiber of a point \({\mathbf c}\in{\mathbb R}^r\) is the set \(f^{-1}({\mathbf c})\), and the Reeb space is the quotient space obtained by identifying all points of \({\mathbb X}\) that belong to the same connected component of a fiber. The Jacobi structure is the image the Jacobi set under the quotient map.
In the case when \(d=3\) and \(r=2\), it is shown that if \(f\) is smooth and stable, then the Jacobi structure separates the Reeb space into \(2\)-manifold components. Moreover, a lip – a regular component of the Reeb space that is attached along a singular arc – can be removed without affecting the homotopy type.
The Reeb skeleton is defined to be the graph whose vertices are the regular and singular components of the Reeb space, and with edges between adjacent singular components, and between adjacent singular and regular components (with some multiplicity conditions). The authors discuss how the Reeb space can be discretely approximated to any level of precision by a joint contour net [H. Carr and D. Duke, “Joint Contour Nets”, IEEE Trans. Vis. Comput. Graph. 20, 1100–1113 (2014)]. Algorithms are given for using the joint contour net to extract the Jacobi structure and to construct the Reeb skeleton. It is shown how the Reeb skeleton may be further simplified by removing lips.

MSC:

65D18 Numerical aspects of computer graphics, image analysis, and computational geometry
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)

Software:

OGDF
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Chiang, Y.-J.; Lu, X., Progressive simplification of tetrahedral meshes preserving all isosurface topologies, Comput. Graph. Forum, 22, 493-504 (2003)
[2] Carr, H.; Snoeyink, J.; van de Panne, M., Simplifying flexible isosurfaces using local geometric measures, IEEE Vis., 497-504 (2004)
[3] Tierny, J.; Pascucci, V., Generalized topological simplification of scalar fields on surfaces, IEEE Trans. Vis. Comput. Graph., 18, 12, 2005-2013 (2012)
[4] Saeki, O., Topology of Singular Fibers of Differentiable Maps (2004), Springer · Zbl 1072.57023
[5] Edelsbrunner, H.; Harer, J.; Patel, A. K., Reeb spaces of piecewise linear mappings, (SoCG (2008)), 242-250 · Zbl 1271.57059
[6] Carr, H.; Duke, D., Joint contour net, IEEE Trans. Vis. Comput. Graph., 20, 1100-1113 (2014)
[7] Wood, Z.; Hoppe, H.; Desbrun, M.; Schröder, P., Removing excess topology from isosurfaces, ACM Trans. Graph., 23, 2, 190-208 (2004)
[8] Gyulassy, A.; Natarajan, V.; Pascucci, V.; Bremer, P.-T.; Hamann, B., A topological approach to simplification of three-dimensional scalar functions, IEEE Trans. Vis. Comput. Graph., 12, 4, 474-484 (2006)
[9] Luo, C.; Safa, I.; Wang, Y., Approximating gradients for meshes and point cloud via diffusion metric, (Proceedings Symposium on Geometry Processing (2009), Eurographics Association: Eurographics Association Aire-La-Ville, Switzerland), 1497-1508
[10] Edelsbrunner, H.; Letscher, D.; Zomorodian, A., Topological persistence and simplification, Discrete Comput. Geom., 28, 4, 511-533 (2002) · Zbl 1011.68152
[11] Cohen-Steiner, D.; Edelsbrunner, H.; Harer, J., Stability of persistence diagrams, Discrete Comput. Geom., 37, 1, 103-120 (2007) · Zbl 1117.54027
[12] Fabio, B. D.; Landi, C., The edit distance for Reeb graphs of surfaces, Discrete Comput. Geom., 55, 2, 423-461 (2016) · Zbl 1332.05038
[13] de Silva, V.; Munch, E.; Patel, A., Categorified Reeb graphs · Zbl 1350.68271
[14] Bauer, U.; Munch, E.; Wang, Y., Strong equivalence of the interleaving and functional distortion metrics for Reeb graphs · Zbl 1382.58010
[15] Guskov, I.; Wood, Z. J., Topological Noise Removal (2001)
[16] Nooruddin, F. S.; Turk, G., Simplification and repair of polygonal models using volumetric techniques, IEEE Trans. Vis. Comput. Graph., 9, 2, 191-205 (2003)
[17] Ni, X.; Garland, M.; Hart, J. C., Fair Morse functions for extracting the topological structure of a surface mesh, ACM Trans. Graph. (TOG) - Proc. ACM SIGGRAPH, 23, 3, 613-622 (2004)
[18] Hoppe, H.; DeRose, T.; Duchamp, T.; McDonald, J.; Stuetzle, W., Mesh optimization, (Proceedings of the 20th Annual Conference on Computer Graphics and Interactive Techniques. Proceedings of the 20th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH ’93 (1993), ACM: ACM New York, NY, USA), 19-26
[19] Hoppe, H., Progressive meshes, (ACM SIGGRAPH 1996 Proceedings (1996), ACM: ACM New York, NY, USA), 99-108
[20] Popović, J.; Hoppe, H., Progressive simplicial complexes, (ACM SIGGRAPH 1997 Proceedings (1997), ACM: ACM New York, NY, USA), 217-224
[21] Dey, T. K.; Edelsbrunner, H.; Guha, S.; Nekhayev, D. V., Topology preserving edge contraction, Publ. Inst. Math. (Belgr.), 66, 23-45 (1998)
[22] Lindstrom, P.; Turk, G., Fast and memory efficient polygonal simplification, (IEEE Visualization (1998)), 279-286
[23] Lindstrom, P.; Turk, G., Evaluation of memoryless simplification, IEEE Trans. Vis. Comput. Graph., 5, 2, 98-115 (1999)
[24] Garland, M.; Heckbert, P. S., Surface simplification using quadric error metrics, (SIGGRAPH (1997)), 209-216
[25] Tricoche, X.; Scheuermann, G.; Hagen, H., Continuous topology simplification of planar vector fields, (Proceedings of the Conference on Visualization ’01 (2001), IEEE Computer Society: IEEE Computer Society Washington, DC, USA), 159-166
[26] Zhang, E.; Mischaikow, K.; Turk, G., Vector field design on surfaces, ACM Trans. Graph., 25, 4, 1294-1326 (2006)
[27] Reininghaus, J.; Hotz, I., Combinatorial 2D vector field topology extraction and simplification, Topol. Methods Data Anal. Vis., 103-114 (2011) · Zbl 1217.68238
[28] Polthier, K.; Preuß, E., Identifying vector field singularities using a discrete Hodge decomposition, (Mathematical Visualization (2003), Springer-Verlag: Springer-Verlag New York), 113-134 · Zbl 1065.37018
[29] Tong, Y.; Lombeyda, S.; Hirani, A. N.; Desbrun, M., Discrete multiscale vector field decomposition, ACM Trans. Graphics (TOG), 22, 3, 445-452 (2003)
[30] Edelsbrunner, H.; Harer, J.; Natarajan, V.; Pascucci, V., Local and global comparison of continuous functions, (Proceedings of the Conference on Visualization (2004)), 275-280
[31] Carlsson, G.; Zomorodian, A., The theory of multidimensional persistence, (Discrete and Computational Geometry. Discrete and Computational Geometry, 23rd Annual Symposium on Computational Geometry, vol. 42(1) (2009)), 71-93 · Zbl 1187.55004
[32] Singh, G.; Mémoli, F.; Carlsson, G., Topological methods for the analysis of high dimensional data sets and 3D object recognition, (Eurographics Symposium on Point-Based Graphics (2007)), 1-11
[33] Snyder, D. F., Topological persistence in Jacobi sets, 2004 (2004), Tech. rep., Technical Report July 29
[34] Bremer, P.-T.; Bringa, E. M.; Duchaineau, M.; Laney, D.; Mascarenhas, A.; Pascucci, V., Topological feature extraction and tracking, J. Phys.: Conf. Ser., 78, Article 012007 pp. (2007)
[35] Suthambhara, N.; Natarajan, V., Simplification of Jacobi sets, (TopoInVis (2009)), 91-102 · Zbl 1214.68439
[36] Huettenberger, L.; Heine, C.; Carr, H.; Scheuermann, G.; Garth, C., Towards multifield scalar topology based on pareto optimality, Comput. Graph. Forum, 32, 3.3, 341-350 (2013)
[37] Huettenberger, L.; Heine, C.; Garth, C., Decomposition and simplification of multivariate data using pareto sets, IEEE Trans. Vis. Comput. Graph., 20, 12, 2684-2693 (2014)
[38] Bhatia, H.; Wang, B.; Norgard, G.; Pascucci, V.; Bremer, P.-T., Local, smooth, and consistent Jacobi set simplification, Comput. Geom.: Theor. Appl., 48, 4, 311-332 (2015) · Zbl 1311.65021
[39] Chattopadhyay, A.; Carr, H.; Duke, D.; Geng, Z., Extracting Jacobi structures in Reeb spaces, (Elmqvist, N.; Hlawitschka, M.; Kennedy, J., EuroVis - Short Papers, The Eurographics Association (2014)), 1-4
[40] Strodthoff, B.; Jüttler, B., Layered Reeb graphs for three-dimensional manifolds in boundary representation, Comput. Graph., 46 (2014)
[41] van Kreveld, M.; van Oostrum, R.; Bajaj, C.; Pascucci, V.; Schikore, D., Contour trees and small seed sets for isosurface traversal, (Symposium on Computational Geometry (1997)), 212-220
[42] Carr, H.; Snoeyink, J.; Axen, U., Computing contour trees in all dimensions, Comput. Geom.: Theor. Appl., 24, 2, 75-94 (2003) · Zbl 1052.68098
[43] Hilaga, M.; Shinagawa, Y.; Kohmura, T.; Kunii, T. L., Topology matching for fully automatic similarity estimation of 3D shapes, (SIGGRAPH (2001)), 203-212
[44] Edelsbrunner, H.; Harer, J.; Mascarenhas, A.; Pascucci, V., Time-varying Reeb graphs for continuous space-time data, (Symposium on Computational Geometry (2004)), 366-372 · Zbl 1377.68271
[45] Pascucci, V.; Bremer, P.-T.; Mascarenhas, A.; Scorzelli, G., Robust on-line computation of Reeb graphs, ACM Trans. Graph. (TOG, 26, Article 58 pp. (2007)
[46] Saeki, O.; Takahashi, S.; Sakurai, D.; Wu, H.-Y.; Kikuchi, K.; Carr, H.; Duke, D.; Yamamoto, T., Visualizing multivariate data using singularity theory, (The Impact of Applications on Mathematics. The Impact of Applications on Mathematics, Proceedings of Forum “Math-for-Industry” 2013, Mathematics for Industry, vol. 1 (2014), Springer: Springer Japan), 51-65 · Zbl 1346.68245
[47] Levine, H., Classifying Immersions into \(R^4\) over Stable Maps of 3-manifolds into \(R^2\), Lecture Notes in Mathematics, vol. 1157 (1985), Springer-Verlag: Springer-Verlag Berlin · Zbl 0567.57001
[48] Saeki, O.; Yamamoto, T., Singular fibers of stable maps of 3-manifolds with boundary into surfaces and their applications, Alg. Geom. Topol., to appear · Zbl 1360.57034
[49] Guillemin, V.; Pollack, A., Differential Topology (1974), Prentice-Hall, Inc.: Prentice-Hall, Inc. Englewood Cliffs, New Jersey · Zbl 0361.57001
[50] Edelsbrunner, H.; Harer, J., Jacobi sets of multiple Morse functions, Foundations Comput. Math., 2002, 37-57 (2004), Cambridge Univ. Press, Minneapolis · Zbl 1109.58018
[51] Hatcher, A., Algebraic Topology (2002), Cambridge University Press · Zbl 1044.55001
[52] Kushner, L.; Levine, H.; Porto, P., Mapping three-manifolds into the plane I, Bol. Soc. Mat. Mexicana, 29, 2, 11-33 (1984) · Zbl 0586.57018
[53] Saeki, O.; Yamamoto, T., Cobordism group of Morse functions on surfaces with boundary, (São Carlos. São Carlos, Proceedings of the XIII International Workshop on Real and Complex Singularities (2014)), in press. Preprint
[54] Mata-Lorenzo, L., Polyhedrons and pi-stable homotopies from 3-manifolds into the plane, Bol. Soc. Bras. Mat. (N.S.), 20, 61-85 (1989) · Zbl 0752.57014
[55] Carr, H.; Snoeyink, J.; van de Panne, M., Flexible isosurfaces: simplifying and displaying scalar topology using the contour tree, Comput. Geom.: Theor. Appl., 43, 1, 42-58 (2010) · Zbl 1175.65030
[56] Pascucci, V.; Cole-McLaughlin, K.; Scorzell, G., Multi-resolution computation and presentation of contour trees, (Proceedings of the IASTED Conference on Visualization, Imaging and Image Processing (VIIP 2004) (2004)), 452-290
[57] Duffy, B.; Carr, H.; Möller, T., Integrating isosurface statistics and histograms, IEEE Trans. Vis. Comput. Graph., 19, 2, 263-277 (2012)
[58] Duke, D.; Carr, H.; Schunck, N.; Nam, H. A.; Staszczak, A., Visualizing nuclear scission through a multifield extension of topological analysis, IEEE Trans. Vis. Comput. Graph., 18, 12, 2033-2040 (2012)
[59] Toolkit, Visualization (2013)
[60] Chimani, M.; Gutwenger, C.; Jünger, M.; Klau, G. W.; Klein, K.; Mutzel, P., OGDF - Open Graph Drawing Framework (2012)
[61] Tarjan, R. E., Efficiency of a good but not linear set union algorithm, J. ACM, 22, 215-225 (1975) · Zbl 0307.68029
[62] Ribes, L.; Zalesskii, P., Profinite Groups, Ergebnisse der Mathematik und ihrer Grenzgebiete, 3. Folge, A Series of Modern Surveys in Mathematics, vol. 40 (2010), Springer-Verlag: Springer-Verlag Berlin · Zbl 1197.20022
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.