research-article

Multivariate topology simplification

Authors:

Amit Chattopadhyay,

Osamu SaekiAuthors Info & Claims

Computational Geometry: Theory and Applications, Volume 58, Issue C

Pages 1 - 24

https://doi.org/10.1016/j.comgeo.2016.05.006

Published: 01 October 2016 Publication History

Abstract

Topological simplification of scalar and vector fields is well-established as an effective method for analysing and visualising complex data sets. For multivariate (alternatively, multi-field) data, topological analysis requires simultaneous advances both mathematically and computationally. We propose a robust multivariate topology simplification method based on "lip"-pruning from the Reeb space. Mathematically, we show that the projection of the Jacobi set of multivariate data into the Reeb space produces a Jacobi structure that separates the Reeb space into simple components. We also show that the dual graph of these components gives rise to a Reeb skeleton that has properties similar to the scalar contour tree and Reeb graph, for topologically simple domains. We then introduce a range measure to give a scaling-invariant total ordering of the components or features that can be used for simplification. Computationally, we show how to compute Jacobi structure, Reeb skeleton, range and geometric measures in the Joint Contour Net (an approximation of the Reeb space) and that these can be used for visualisation similar to the contour tree or Reeb graph.

References

[1]

Y.-J. Chiang, X. Lu, Progressive simplification of tetrahedral meshes preserving all isosurface topologies, Comput. Graph. Forum, 22 (2003) 493-504.

[2]

H. Carr, J. Snoeyink, M. van de Panne, Simplifying flexible isosurfaces using local geometric measures, IEEE Vis. (2004) 497-504.

Digital Library

[3]

J. Tierny, V. Pascucci, Generalized topological simplification of scalar fields on surfaces, IEEE Trans. Vis. Comput. Graph., 18 (2012) 2005-2013.

Digital Library

[4]

O. Saeki, Topology of Singular Fibers of Differentiable Maps, Springer, 2004.

[5]

H. Edelsbrunner, J. Harer, A.K. Patel, Reeb spaces of piecewise linear mappings, in: SoCG, 2008, pp. 242-250.

Digital Library

[6]

H. Carr, D. Duke, Joint contour net, IEEE Trans. Vis. Comput. Graph., 20 (2014) 1100-1113.

Digital Library

[7]

Z. Wood, H. Hoppe, M. Desbrun, P. Schröder, Removing excess topology from isosurfaces, ACM Trans. Graph., 23 (2004) 190-208.

Digital Library

[8]

A. Gyulassy, V. Natarajan, V. Pascucci, P.-T. Bremer, B. Hamann, A topological approach to simplification of three-dimensional scalar functions, IEEE Trans. Vis. Comput. Graph., 12 (2006) 474-484.

Digital Library

[9]

C. Luo, I. Safa, Y. Wang, Approximating gradients for meshes and point cloud via diffusion metric, in: Proceedings Symposium on Geometry Processing, Eurographics Association, Aire-La-Ville, Switzerland, 2009, pp. 1497-1508.

Digital Library

[10]

H. Edelsbrunner, D. Letscher, A. Zomorodian, Topological persistence and simplification, Discrete Comput. Geom., 28 (2002) 511-533.

Digital Library

[11]

D. Cohen-Steiner, H. Edelsbrunner, J. Harer, Stability of persistence diagrams, Discrete Comput. Geom., 37 (2007) 103-120.

Digital Library

[12]

B.D. Fabio, C. Landi, The edit distance for Reeb graphs of surfaces, Discrete Comput. Geom., 55 (2016) 423-461.

Digital Library

[13]

V. de Silva, E. Munch, A. Patel, Categorified Reeb graphs. arXiv:1501.04147 cs.CG

[14]

U. Bauer, E. Munch, Y. Wang, Strong equivalence of the interleaving and functional distortion metrics for Reeb graphs. arXiv:1412.6646 math.AT

[15]

I. Guskov, Z.J. Wood, Topological Noise Removal, 2001.

[16]

F.S. Nooruddin, G. Turk, Simplification and repair of polygonal models using volumetric techniques, IEEE Trans. Vis. Comput. Graph., 9 (2003) 191-205.

Digital Library

[17]

X. Ni, M. Garland, J.C. Hart, Fair Morse functions for extracting the topological structure of a surface mesh, ACM Trans. Graph. (TOG) - Proc. ACM SIGGRAPH, 23 (2004) 613-622.

Digital Library

[18]

H. Hoppe, T. DeRose, T. Duchamp, J. McDonald, W. Stuetzle, Mesh optimization, in: Proceedings of the 20th Annual Conference on Computer Graphics and Interactive Techniques, ACM, New York, NY, USA, 1993, pp. 19-26.

Digital Library

[19]

H. Hoppe, Progressive meshes, in: ACM SIGGRAPH 1996 Proceedings, ACM, New York, NY, USA, 1996, pp. 99-108.

Digital Library

[20]

J. Popović, H. Hoppe, Progressive simplicial complexes, in: ACM SIGGRAPH 1997 Proceedings, ACM, New York, NY, USA, 1997, pp. 217-224.

Digital Library

[21]

T.K. Dey, H. Edelsbrunner, S. Guha, D.V. Nekhayev, Topology preserving edge contraction, Publ. Inst. Math. (Belgr.), 66 (1998) 23-45.

[22]

P. Lindstrom, G. Turk, Fast and memory efficient polygonal simplification, in: IEEE Visualization, 1998, pp. 279-286.

Digital Library

[23]

P. Lindstrom, G. Turk, Evaluation of memoryless simplification, IEEE Trans. Vis. Comput. Graph., 5 (1999) 98-115.

Digital Library

[24]

M. Garland, P.S. Heckbert, Surface simplification using quadric error metrics, in: SIGGRAPH, 1997, pp. 209-216.

Digital Library

[25]

X. Tricoche, G. Scheuermann, H. Hagen, Continuous topology simplification of planar vector fields, in: Proceedings of the Conference on Visualization '01, IEEE Computer Society, Washington, DC, USA, 2001, pp. 159-166.

Digital Library

[26]

E. Zhang, K. Mischaikow, G. Turk, Vector field design on surfaces, ACM Trans. Graph., 25 (2006) 1294-1326.

Digital Library

[27]

J. Reininghaus, I. Hotz, Combinatorial 2D vector field topology extraction and simplification, Topol. Methods Data Anal. Vis. (2011) 103-114.

[28]

K. Polthier, E. Preuß, Identifying vector field singularities using a discrete Hodge decomposition, in: Mathematical Visualization, Springer-Verlag, New York, 2003, pp. 113-134.

[29]

Y. Tong, S. Lombeyda, A.N. Hirani, M. Desbrun, Discrete multiscale vector field decomposition, ACM Trans. Graphics (TOG), 22 (2003) 445-452.

Digital Library

[30]

H. Edelsbrunner, J. Harer, V. Natarajan, V. Pascucci, Local and global comparison of continuous functions, in: Proceedings of the Conference on Visualization, 2004, pp. 275-280.

Digital Library

[31]

G. Carlsson, A. Zomorodian, The theory of multidimensional persistence, in: 23rd Annual Symposium on Computational Geometry, vol. 42(1), 2009, pp. 71-93.

[32]

G. Singh, F. Mémoli, G. Carlsson, Topological methods for the analysis of high dimensional data sets and 3D object recognition, in: Eurographics Symposium on Point-Based Graphics, 2007, pp. 1-11.

[33]

D.F. Snyder, Topological persistence in Jacobi sets, 2004.

[34]

P.-T. Bremer, E.M. Bringa, M. Duchaineau, D. Laney, A. Mascarenhas, V. Pascucci, Topological feature extraction and tracking, J. Phys.: Conf. Ser., 78 (2007).

[35]

N. Suthambhara, V. Natarajan, Simplification of Jacobi sets, in: TopoInVis, 2009, pp. 91-102.

[36]

L. Huettenberger, C. Heine, H. Carr, G. Scheuermann, C. Garth, Towards multifield scalar topology based on pareto optimality, Comput. Graph. Forum, 32 (2013) 341-350.

Digital Library

[37]

L. Huettenberger, C. Heine, C. Garth, Decomposition and simplification of multivariate data using pareto sets, IEEE Trans. Vis. Comput. Graph., 20 (2014) 2684-2693.

[38]

H. Bhatia, B. Wang, G. Norgard, V. Pascucci, P.-T. Bremer, Local, smooth, and consistent Jacobi set simplification, Comput. Geom.: Theor. Appl., 48 (2015) 311-332.

Digital Library

[39]

A. Chattopadhyay, H. Carr, D. Duke, Z. Geng, Extracting Jacobi structures in Reeb spaces, in: EuroVis - Short Papers, The Eurographics Association, 2014, pp. 1-4.

[40]

B. Strodthoff, B. Jüttler, Layered Reeb graphs for three-dimensional manifolds in boundary representation, Comput. Graph., 46 (2014).

Digital Library

[41]

M. van Kreveld, R. van Oostrum, C. Bajaj, V. Pascucci, D. Schikore, Contour trees and small seed sets for isosurface traversal, in: Symposium on Computational Geometry, 1997, pp. 212-220.

Digital Library

[42]

H. Carr, J. Snoeyink, U. Axen, Computing contour trees in all dimensions, Comput. Geom.: Theor. Appl., 24 (2003) 75-94.

Digital Library

[43]

M. Hilaga, Y. Shinagawa, T. Kohmura, T.L. Kunii, Topology matching for fully automatic similarity estimation of 3D shapes, in: SIGGRAPH, 2001, pp. 203-212.

Digital Library

[44]

H. Edelsbrunner, J. Harer, A. Mascarenhas, V. Pascucci, Time-varying Reeb graphs for continuous space-time data, in: Symposium on Computational Geometry, 2004, pp. 366-372.

Digital Library

[45]

V. Pascucci, P.-T. Bremer, A. Mascarenhas, G. Scorzelli, Robust on-line computation of Reeb graphs, ACM Trans. Graph. (TOG, 26 (2007).

Digital Library

[46]

O. Saeki, S. Takahashi, D. Sakurai, H.-Y. Wu, K. Kikuchi, H. Carr, D. Duke, T. Yamamoto, Visualizing multivariate data using singularity theory, in: Proceedings of Forum "Math-for-Industry" 2013, Mathematics for Industry, vol. 1, Springer, Japan, 2014, pp. 51-65.

[47]

H. Levine, Classifying Immersions into R 4 over Stable Maps of 3-manifolds into R 2, Springer-Verlag, Berlin, 1985.

[48]

O. Saeki, T. Yamamoto, Singular fibers of stable maps of 3-manifolds with boundary into surfaces and their applications. arXiv:1509.05848 math.GT

[49]

V. Guillemin, A. Pollack, Differential Topology, Prentice-Hall, Inc., Englewood Cliffs, New Jersey, 1974.

[50]

H. Edelsbrunner, J. Harer, Jacobi sets of multiple Morse functions, Foundations Comput. Math., 2002 (2004) 37-57.

[51]

A. Hatcher, Algebraic Topology, Cambridge University Press, 2002.

[52]

L. Kushner, H. Levine, P. Porto, Mapping three-manifolds into the plane I, Bol. Soc. Mat. Mexicana, 29 (1984) 11-33.

[53]

O. Saeki, T. Yamamoto, Cobordism group of Morse functions on surfaces with boundary, in: Proceedings of the XIII International Workshop on Real and Complex Singularities, 2014. http://imi.kyushu-u.ac.jp/~saeki/research.html#03

[54]

L. Mata-Lorenzo, Polyhedrons and pi-stable homotopies from 3-manifolds into the plane, Bol. Soc. Bras. Mat. (N.S.), 20 (1989) 61-85.

[55]

H. Carr, J. Snoeyink, M. van de Panne, Flexible isosurfaces: simplifying and displaying scalar topology using the contour tree, Comput. Geom.: Theor. Appl., 43 (2010) 42-58.

Digital Library

[56]

V. Pascucci, K. Cole-McLaughlin, G. Scorzell, Multi-resolution computation and presentation of contour trees, in: Proceedings of the IASTED Conference on Visualization, Imaging and Image Processing (VIIP 2004), 2004, pp. 452-290.

[57]

B. Duffy, H. Carr, T. Möller, Integrating isosurface statistics and histograms, IEEE Trans. Vis. Comput. Graph., 19 (2012) 263-277.

Digital Library

[58]

D. Duke, H. Carr, N. Schunck, H.A. Nam, A. Staszczak, Visualizing nuclear scission through a multifield extension of topological analysis, IEEE Trans. Vis. Comput. Graph., 18 (2012) 2033-2040.

Digital Library

[59]

Visualization Toolkit, . http://www.vtk.org/

[60]

M. Chimani, C. Gutwenger, M. Jünger, G.W. Klau, K. Klein, P. Mutzel, OGDF - Open Graph Drawing Framework. http://www.ogdf.net/

[61]

R.E. Tarjan, Efficiency of a good but not linear set union algorithm, J. ACM, 22 (1975) 215-225.

Digital Library

[62]

L. Ribes, P. Zalesskii, Profinite Groups, Ergebnisse der Mathematik und ihrer Grenzgebiete, 3. Folge, Springer-Verlag, Berlin, 2010.

Cited By

Ramamurthi YChattopadhyay A(2022)Topological Shape Matching using Multi-Dimensional Reeb GraphsProceedings of the Thirteenth Indian Conference on Computer Vision, Graphics and Image Processing10.1145/3571600.3571606(1-10)Online publication date: 8-Dec-2022
https://dl.acm.org/doi/10.1145/3571600.3571606
Ramamurthi YAgarwal TChattopadhyay A(2022)A Topological Similarity Measure Between Multi-Resolution Reeb SpacesIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2021.308727328:12(4360-4374)Online publication date: 1-Dec-2022
https://dl.acm.org/doi/10.1109/TVCG.2021.3087273
Wang YZheng JWang H(2019)Fast Mesh Simplification Method for Three-Dimensional Geometric Models with Feature-Preserving EfficiencyScientific Programming10.1155/2019/49261902019Online publication date: 3-Feb-2019
https://dl.acm.org/doi/10.1155/2019/4926190
Show More Cited By

Multivariate topology simplification
1. Computing methodologies
  1. Computer graphics
    1. Shape modeling
2. Theory of computation
  1. Randomness, geometry and discrete structures

Recommendations

Homotopy-preserving medial axis simplification
SPM '05: Proceedings of the 2005 ACM symposium on Solid and physical modeling

We present a novel algorithm to compute a simplified medial axis of a polyhedron. Our simplification algorithm tends to remove unstable features of Blum's medial axis. Moreover, our algorithm preserves the topological structure of the original medial ...
Topological simplification of isosurfaces in volumetric data using octrees

Volumetric data, such as output from CT scans or laser range scan processing methods, often have isosurfaces that contain topological noise-small handles and holes that are not present in the original model. Because this noise can significantly degrade ...
Hierarchical topology-preserving simplification of terrains

We present an algorithm for simplifying terrain data that preserves topology. We use a decimation algorithm that simplifies the given data set using hierarchical clustering. Topology constraints, along with local error metrics, are used to ensure ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Computational Geometry: Theory and Applications

Computational Geometry: Theory and Applications Volume 58, Issue C

October 2016

135 pages

ISSN:0925-7721

Issue’s Table of Contents

Copyright © Elsevier B.V.

Publisher

Elsevier Science Publishers B. V.

Netherlands

Publication History

Published: 01 October 2016

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 22 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ramamurthi YChattopadhyay A(2022)Topological Shape Matching using Multi-Dimensional Reeb GraphsProceedings of the Thirteenth Indian Conference on Computer Vision, Graphics and Image Processing10.1145/3571600.3571606(1-10)Online publication date: 8-Dec-2022
https://dl.acm.org/doi/10.1145/3571600.3571606
Ramamurthi YAgarwal TChattopadhyay A(2022)A Topological Similarity Measure Between Multi-Resolution Reeb SpacesIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2021.308727328:12(4360-4374)Online publication date: 1-Dec-2022
https://dl.acm.org/doi/10.1109/TVCG.2021.3087273
Wang YZheng JWang H(2019)Fast Mesh Simplification Method for Three-Dimensional Geometric Models with Feature-Preserving EfficiencyScientific Programming10.1155/2019/49261902019Online publication date: 3-Feb-2019
https://dl.acm.org/doi/10.1155/2019/4926190
Carrière MOudot S(2018)Structure and Stability of the One-Dimensional MapperFoundations of Computational Mathematics10.1007/s10208-017-9370-z18:6(1333-1396)Online publication date: 1-Dec-2018
https://dl.acm.org/doi/10.1007/s10208-017-9370-z
Liu SMaljovec DWang BBremer PPascucci V(2017)Visualizing High-Dimensional DataIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2016.264096023:3(1249-1268)Online publication date: 1-Mar-2017
https://dl.acm.org/doi/10.1109/TVCG.2016.2640960

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents