More Web Proxy on the site http://driver.im/

research-article

Parallel Computation of Piecewise Linear Morse-Smale Segmentations

Authors:

Robin G. C. Maack,

Jonas Lukasczyk,

Ross Maciejewski,

Christoph GarthAuthors Info & Claims

IEEE Transactions on Visualization and Computer Graphics, Volume 30, Issue 4

Pages 1942 - 1955

https://doi.org/10.1109/TVCG.2023.3261981

Published: 27 March 2023 Publication History

Abstract

This article presents a well-scaling parallel algorithm for the computation of Morse-Smale (MS) segmentations, including the region separators and region boundaries. The segmentation of the domain into ascending and descending manifolds, solely defined on the vertices, improves the computational time using path compression and fully segments the border region. Region boundaries and region separators are generated using a multi-label marching tetrahedra algorithm. This enables a fast and simple solution to find optimal parameter settings in preliminary exploration steps by generating an MS complex preview. It also poses a rapid option to generate a fast visual representation of the region geometries for immediate utilization. Two experiments demonstrate the performance of our approach with speedups of over an order of magnitude in comparison to two publicly available implementations. The example section shows the similarity to the MS complex, the useability of the approach, and the benefits of this method with respect to the presented datasets. We provide our implementation with the paper.

References

[1]

M. Olejniczak, A. S. P. Gomes, and J. Tierny, “A topological data analysis perspective on noncovalent interactions in relativistic calculations,” Int. J. Quantum Chem., vol. 120, no. 8, 2020, Art. no.

[2]

H. Bhatia, A. G. Gyulassy, V. Lordi, J. E. Pask, V. Pascucci, and P.-T. Bremer, “TopoMS: Comprehensive topological exploration for molecular and condensed-matter systems,” J. Comput. Chem., vol. 39, no. 16, pp. 936–952, 2018.

[3]

A. Venkat et al., “Towards replacing physical testing of granular materials with a topology-based model,” IEEE Trans. Vis. Comput. Graph., no. 1, pp. 76–85, Jan. 2022.

[4]

U. Homberg, D. Baum, A. Wiebel, S. Prohaska, and H.-C. Hege, “Definition, extraction, and validation of pore structures in porous materials,” in Topological Methods in Data Analysis and Visualization III. Berlin, Germany: Springer, 2014, pp. 235–248.

[5]

D. Laney, A. Mascarenhas, P. Miller, and V. Pascucci, “Understanding the structure of the turbulent mixing layer in hydrodynamic instabilities,” IEEE Trans. Vis. Comput. Graph., vol. 12, no. 5, pp. 1053–1060, Sep./Oct. 2006.

Digital Library

[6]

A. Gyulassy et al., “Interstitial and interlayer ion diffusion geometry extraction in graphitic nanosphere battery materials,” IEEE Trans. Vis. Comput. Graph., vol. 22, no. 1, pp. 916–925, Jan. 2016.

Digital Library

[7]

T. Sousbie, “The persistent cosmic web and its filamentary structure–I. theory and implementation,” Monthly Notices Roy. Astronomical Soc., vol. 414, no. 1, pp. 350–383, 2011.

[8]

T. B. Masood et al., “An overview of the topology ToolKit,” in Topological Methods in Data Analysis and Visualization VI: Theory, Applications, and Software, 2021.

[9]

A. Gyulassy, P. Bremer, and V. Pascucci, “Shared-memory parallel computation of Morse-Smale complexes with improved accuracy,” IEEE Trans. Vis. Comput. Graph., vol. 25, no. 1, pp. 1183–1192, Jan. 2019. https://github.com/sci-visus/MSCEER

Digital Library

[10]

J. Milnor, Morse Theory. Princeton, NJ, USA: Princeton Univ. Press, 1963.

[11]

R. Forman, “Morse theory for cell complexes,” Adv. Math., vol. 134, no. 1, pp. 90–145, 1998.

[12]

T. Banchoff, “Critical points and curvature for embedded polyhedra,” J. Differ. Geometry, vol. 1, no. 3/4, pp. 245–256, 1967.

[13]

T. F. Banchoff, “Critical points and curvature for embedded polyhedral surfaces,” Amer. Math. Monthly, vol. 77, no. 5, pp. 475–485, 1970.

[14]

T. Lewiner, “Critical sets in discrete Morse theories: Relating forman and piecewise-linear approaches,” Comput. Aided Geometric Des., vol. 30, no. 6, pp. 609–621, 2013.

[15]

H. Edelsbrunner, J. Harer, and A. Zomorodian, “Hierarchical morse complexes for piecewise linear 2-manifolds,” in Proc. 17th Annu. Symp. Comput. Geometry, 2001, pp. 70–79.

[16]

H. Edelsbrunner, J. Harer, V. Natarajan, and V. Pascucci, “Morse-smale complexes for piecewise linear 3-manifolds,” in Proc. 19th Annu. Symp. Comput. Geometry, 2003, pp. 361–370.

[17]

P.-T. Bremer, B. Hamann, H. Edelsbrunner, and V. Pascucci, “A topological hierarchy for functions on triangulated surfaces,” IEEE Trans. Vis. Comput. Graph., vol. 10, no. 4, pp. 385–396, Jul./Aug. 2004.

Digital Library

[18]

E. Danovaro, L. D. Floriani, and M. M. Mesmoudi, “Topological analysis and characterization of discrete scalar fields,” in Geometry, Morphology, and Computational Imaging. Berlin, Germany: Springer, 2003, pp. 386–402.

[19]

E. Danovaro, L. De Floriani, P. Magillo, M. M. Mesmoudi, and E. Puppo, “Morphology-driven simplification and multiresolution modeling of terrains,” in Proc. 11th ACM Int. Symp. Adv. Geographic Inf. Syst., 2003, pp. 63–70.

[20]

A. Gyulassy, V. Natarajan, V. Pascucci, and B. Hamann, “Efficient computation of Morse-Smale complexes for three-dimensional scalar functions,” IEEE Trans. Vis. Comput. Graph., vol. 13, no. 6, pp. 1440–1447, Nov./Dec. 2007.

Digital Library

[21]

R. Forman, “A user's guide to discrete morse theory,” Séminaire Lotharingien De Combinatoire Electron. Only, vol. 48, pp. B48c–35, 2002.

[22]

D. Günther, J. Reininghaus, H. Wagner, and I. Hotz, “Efficient computation of 3D Morse–Smale complexes and persistent homology using discrete Morse theory,” Vis. Comput., vol. 28, no. 10, pp. 959–969, 2012.

[23]

V. Robins, P. J. Wood, and A. P. Sheppard, “Theory and algorithms for constructing discrete morse complexes from grayscale digital images,” IEEE Trans. Pattern Anal. Mach. Intell., vol. 33, no. 8, pp. 1646–1658, Aug. 2011.

Digital Library

[24]

H. King, K. Knudson, and N. Mramor, “Generating discrete morse functions from point data,” Exp. Math., vol. 14, no. 4, pp. 435–444, 2005.

[25]

A. Gyulassy, P.-T. Bremer, B. Hamann, and V. Pascucci, “A practical approach to Morse-Smale complex computation: Scalability and generality,” IEEE Trans. Vis. Comput. Graph., vol. 14, no. 6, pp. 1619–1626, Nov./Dec. 2008.

Digital Library

[26]

A. Gyulassy, V. Pascucci, T. Peterka, and R. Ross, “The parallel computation of Morse-Smale complexes,” in Proc. IEEE 26th Int. Parallel Distrib. Process. Symp., 2012, pp. 484–495.

[27]

T. Peterka et al., “Scalable parallel building blocks for custom data analysis,” in Proc. IEEE Symp. Large Data Anal. Vis., 2011, pp. 105–112.

[28]

N. Shivashankar, M. Senthilnathan, and V. Natarajan, “Parallel computation of 2D Morse-Smale complexes,” IEEE Trans. Vis. Comput. Graph., vol. 18, no. 10, pp. 1757–1770, Oct. 2012.

Digital Library

[29]

N. Shivashankar and V. Natarajan, “Parallel computation of 3D Morse-Smale complexes,” Comput. Graph. Forum, vol. 31, pp. 965–974, 2012.

Digital Library

[30]

V. Subhash, K. Pandey, and V. Natarajan, “GPU parallel computation of Morse-Smale complexes,” in Proc. IEEE Vis. Conf., 2020, pp. 36–40.

[31]

C. Heine et al., “A survey of topology-based methods in visualization,” in Computer Graphics Forum, vol. 35. Hoboken, NJ, USA: Wiley, 2016, pp. 643–667.

Digital Library

[32]

A. Gyulassy, P.-T. Bremer, and V. Pascucci, “Computing Morse-Smale complexes with accurate geometry,” IEEE Trans. Vis. Comput. Graph., vol. 18, no. 12, pp. 2014–2022, Dec. 2012.

Digital Library

[33]

A. Gyulassy et al., “Topologically clean distance fields,” IEEE Trans. Vis. Comput. Graph., vol. 13, no. 6, pp. 1432–1439, Nov./Dec. 2007.

Digital Library

[34]

D. Günther, R. A. Boto, J. Contreras-Garcia, J.-P. Piquemal, and J. Tierny, “Characterizing molecular interactions in chemical systems,” IEEE Trans. Vis. Comput. Graph., vol. 20, no. 12, pp. 2476–2485, Dec. 2014.

[35]

A. Gyulassy, D. Günther, J. A. Levine, J. Tierny, and V. Pascucci, “Conforming Morse-Smale complexes,” IEEE Trans. Vis. Comput. Graph., vol. 20, no. 12, pp. 2595–2603, Dec. 2014.

[36]

J. Lukasczyk, C. Garth, R. Maciejewski, and J. Tierny, “Localized topological simplification of scalar data,” IEEE Trans. Vis. Comput. Graph., vol. 27, no. 2, pp. 572–582, Feb. 2021.

[37]

R. Fellegara, F. Luricich, L. De Floriani, and K. Weiss, “Efficient computation and simplification of discrete morse decompositions on triangulated terrains,” in Proc. 22nd ACM SIGSPATIAL Int. Conf. Adv. Geographic Inf. Syst., 2014, pp. 223–232.

[38]

T. Weinkauf, Y. Gingold, and O. Sorkine, “Topology-based smoothing of 2D scalar fields with C1-continuity,” in Computer Graphics Forum, vol. 29. Hoboken, NJ, USA: Wiley, 2010, pp. 1221–1230.

[39]

S. Beucher and C. Lantuejoul, “Use of watersheds in contour detection.int,” in Proc. Workshop Image Process., CCETT/IRISA, Rennes, France, 1979, pp. 17–21.

[40]

S. Beucher, “Watersheds of functions and picture segmentation,” in Proc. IEEE Int. Conf. Acoust. Speech Signal Process., 1982, pp. 1928–1931.

[41]

F. Meyer, “Integrals, gradients and watershed lines,” in Proc. Math. Morphol. Appl. Signal Process., 1993, pp. 70–75.

[42]

L. Najman and M. Schmitt, “Definition and some properties of the watershed of a continuous function,” in Proc. Math. Morphol. Appl. Signal Process., 1993, pp. 76–81.

[43]

F. Meyer, “Topographic distance and watershed lines,” Signal Process., vol. 38, no. 1, pp. 113–125, 1994.

Digital Library

[44]

L. Vincent and P. Soille, “Watersheds in digital spaces: An efficient algorithm based on immersion simulations,” IEEE Trans. Pattern Anal. Mach. Intell., vol. 13, no. 06, pp. 583–598, Jun. 1991.

Digital Library

[45]

L. De Floriani, U. Fugacci, F. Iuricich, and P. Magillo, “Morse complexes for shape segmentation and homological analysis: Discrete models and algorithms,” in Computer Graphics Forum, vol. 34. Hoboken, NJ, USA: Wiley, 2015, pp. 761–785.

[46]

F. Meyer and S. Beucher, “Morphological segmentation,” J. Vis. Commun. Image Representation, vol. 1, no. 1, pp. 21–46, 1990.

[47]

Y. Gabrielyan, V. Yeghiazaryan, and I. Voiculescu, “Parallel partitioning: Path reducing and union–find based watershed for the GPU,” in Proc. IEEE Int. Conf. Image Process., 2022, pp. 1501–1505.

[48]

V. Yeghiazaryan and I. Voiculescu, “Path reducing watershed for the GPU,” in Proc. IEEE Winter Conf. Appl. Comput. Vis., 2018, pp. 577–585.

[49]

P. Soille, Morphological Image Analysis Principles and Applications. Berlin, Germany: Springer, 2004.

[50]

A. P. Mangan and R. T. Whitaker, “Partitioning 3D surface meshes using watershed segmentation,” IEEE Trans. Vis. Comput. Graph., vol. 5, no. 4, pp. 308–321, Oct./Dec. 1999.

Digital Library

[51]

S. L. Stoev and W. Straßer, “Extracting regions of interest applying a local watershed transformation,” in Proc. IEEE Conf. Vis., 2000, pp. 21–28.

[52]

G. Nielson and R. Franke, “Computing the separating surface for segmented data,” in Proc. IEEE Conf. Vis., 1997, pp. 229–233.

[53]

W. E. Lorensen and H. E. Cline, “Marching cubes: A high resolution 3D surface construction algorithm,” ACM SIGGRAPH Comput. Graph., vol. 21, no. 4, pp. 163–169, 1987.

Digital Library

[54]

G. M. Nielson and B. Hamann, The Asymptotic Decider: Rosolving the Ambiguity in Marching Cubes. Berkeley, CA, USA: University of California, 1991.

[55]

H. Carr, T. Moller, and J. Snoeyink, “Artifacts caused by simplicial subdivision,” IEEE Trans. Vis. Comput. Graph., vol. 12, no. 2, pp. 231–242, Mar./Apr. 2006.

Digital Library

[56]

M. Chouchane, A. Rucci, and A. A. Franco, “A versatile and efficient voxelization-based meshing algorithm of multiple phases,” ACS Omega, vol. 4, no. 6, pp. 11 141–11 144, 2019.

[57]

T. Müller and F. Raether, “3D modelling of ceramic composites and simulation of their electrical, thermal and elastic properties,” Comput. Mater. Sci., vol. 81, pp. 205–211, 2014.

[58]

D. Weinstein, “Scanline surfacing: Building separating surfaces from planar contours,” in Proc. IEEE Conf. Vis., 2000, pp. 283–289.

[59]

N. Zhang, X. Zhou, D. Sha, X. Yuan, K. K. Tamma, and B. Chen, “Integrating mesh and meshfree methods for physics-based fracture and debris cloud simulation,” in Proc. Conf. PBG@ SIGGRAPH, 2006, pp. 145–154.

[60]

J. Tierny, G. Favelier, J. A. Levine, C. Gueunet, and M. Michaux, “The Topology ToolKit,” IEEE Trans. Vis. Comput. Graph., vol. 24, no. 1, pp. 832–842, Jan. 2018. https://topology-tool-kit.github.io/

[61]

H. Edelsbrunner and J. Harer, Computational Topology: An Introduction. Providence, Rhode Island, USA: American Mathematical Society, 2009.

[62]

A. J. Zomorodian, “Topology for computing,” in Algorithms and Theory of Computation Handbook (Second Edition), M. J. Atallah and M. Blanton Eds., Boca Raton, FL, USA: CRC Press, 2010, pp. 82–112.

[63]

G. Pierre, J. Vidal, and J. Tierny, “Discrete Morse sandwich: Fast computation of persistence diagrams for scalar data – An algorithm and a benchmark,” IEEE Trans. Vis. Comput. Graph., 2023.

[64]

H. Edelsbrunner and E. P. Mücke, “Simulation of simplicity: A technique to cope with degenerate cases in geometric algorithms,” ACM Trans. Graph., vol. 9, no. 1, pp. 66–104, 1990.

Digital Library

[65]

R. Seidel and M. Sharir, “Top-down analysis of path compression,” SIAM J. Comput., vol. 34, no. 3, pp. 515–525, 2005.

Digital Library

[66]

A. Doi and A. Koide, “An efficient method of triangulating equi-valued surfaces by using tetrahedral cells,” IEICE Tran. Inf. Syst., vol. 74, no. 1, pp. 214–224, 1991.

[67]

TTK Contributers, “TTK Data Repository,” 2020. [online]. Available: https://github.com/topology-tool-kit/ttk-data

[68]

TTK Contributers, “TTK Tutorial Data,” 2021. [Online]. Available: https://topology-tool-kit.github.io/stuff/ttk_tutorial_data.zip

[69]

J. Lukasczyk et al., “Viscous fingering: A topological visual analytic approach,” in Applied Mechanics and Materials, vol. 869. Stafa-Zurich, Switzerland: Trans Tech Publ, 2017, pp. 9–19.

[70]

A. W. Cook, W. Cabot, and P. L. Miller, “The mixing transition in Rayleigh-Taylor instability,” J. Fluid Mechanics, vol. 511, pp. 333–362, 2004.

[71]

S. Dong, P. Bremer, M. Garland, V. Pascucci, and J. C. Hart, “Spectral surface quadrangulation,” ACM Trans. Graph., vol. 25, no. 3, 2006.

[72]

A. Gyulassy, V. Natarajan, V. Pascucci, P. Bremer, and B. Hamann, “A topological approach to simplification of three-dimensional scalar functions,” IEEE Trans. Vis. Comput. Graph., vol. 12, no. 4, pp. 474–484, Jul./Aug. 2006.

Digital Library

Cited By

Kissi MPont MLevine JTierny J(2024)A Practical Solver for Scalar Data Topological SimplificationIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2024.345634531:1(97-107)Online publication date: 10-Sep-2024
https://dl.acm.org/doi/10.1109/TVCG.2024.3456345
Li YLiang XWang BQiu YYan LGuo H(2024)MSz: An Efficient Parallel Algorithm for Correcting Morse-Smale Segmentations in Error-Bounded Lossy CompressorsIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2024.345633731:1(130-140)Online publication date: 10-Sep-2024
https://dl.acm.org/doi/10.1109/TVCG.2024.3456337
Le Guillou EWill MGuillou PLukasczyk JFortin PGarth CTierny J(2024)TTK is Getting MPI-ReadyIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2024.339021930:8(5875-5892)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1109/TVCG.2024.3390219

Index Terms

Parallel Computation of Piecewise Linear Morse-Smale Segmentations
1. Computing methodologies
2. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Computational geometry

Index terms have been assigned to the content through auto-classification.

Recommendations

Certified computation of planar Morse-Smale complexes

The Morse-Smale complex is an important tool for global topological analysis in various problems of computational geometry and topology. Algorithms for Morse-Smale complexes have been presented in case of piecewise linear manifolds (Edelsbrunner et al., ...
Morse-smale complexes for piecewise linear 3-manifolds
SCG '03: Proceedings of the nineteenth annual symposium on Computational geometry

We define the Morse-Smale complex of a Morse function over a 3-manifold as the overlay of the descending and ascending manifolds of all critical points. In the generic case, its 3-dimensional cells are shaped like crystals and are separated by ...
Efficient Computation of Morse-Smale Complexes for Three-dimensional Scalar Functions

The Morse-Smale complex is an efficient representation of the gradient behavior of a scalar function, and critical points paired by the complex identify topological features and their importance. We present an algorithm that constructs the Morse-Smale ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Visualization and Computer Graphics

IEEE Transactions on Visualization and Computer Graphics Volume 30, Issue 4

April 2024

170 pages

Issue’s Table of Contents

© 2023 The Authors. This work is licensed under a Creative Commons Attribution 4.0 License. For more information, see https://creativecommons.org/licenses/by/4.0/.

Publisher

IEEE Educational Activities Department

United States

Publication History

Published: 27 March 2023

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 24 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Kissi MPont MLevine JTierny J(2024)A Practical Solver for Scalar Data Topological SimplificationIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2024.345634531:1(97-107)Online publication date: 10-Sep-2024
https://dl.acm.org/doi/10.1109/TVCG.2024.3456345
Li YLiang XWang BQiu YYan LGuo H(2024)MSz: An Efficient Parallel Algorithm for Correcting Morse-Smale Segmentations in Error-Bounded Lossy CompressorsIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2024.345633731:1(130-140)Online publication date: 10-Sep-2024
https://dl.acm.org/doi/10.1109/TVCG.2024.3456337
Le Guillou EWill MGuillou PLukasczyk JFortin PGarth CTierny J(2024)TTK is Getting MPI-ReadyIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2024.339021930:8(5875-5892)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1109/TVCG.2024.3390219

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents