[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Log in

From numerics to combinatorics: a survey of topological methods for vector field visualization

  • Regular Paper
  • Published:
Journal of Visualization Aims and scope Submit manuscript

Abstract

Topological methods are important tools for data analysis, and recently receiving more and more attention in vector field visualization. In this paper, we give an introductory description to some important topological methods in vector field visualization. Besides traditional methods of vector field topology, space-time method and finite-time Lyapunov exponent, we also include in this survey Hodge decomposition, combinatorial vector field topology, Morse decomposition, and robustness, etc. In addition to familiar numerical techniques, more and more combinatorial tools emerge in vector field visualization. The numerical methods often rely on error-prone interpolations and interpolations, while combinatorial techniques produce robust but coarse features. In this survey, we clarify the relevant concepts and hope to guide future topological research in vector field visualization.

Graphical abstract

This is a preview of subscription content, log in via an institution to check access.

Access this article

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14
Fig. 15
Fig. 16
Fig. 17
Fig. 18
Fig. 19
Fig. 20
Fig. 21
Fig. 22
Fig. 23

Similar content being viewed by others

Notes

  1. Actually \(H_i\simeq T_i\times \underbrace{\mathbb {Z}\times \cdots \times \mathbb {Z}}_{\beta _i}\), where \(T_i\) is the torsion subgroup and usually assumed trivial.

References

  • Abraham R, Marsden JE, Ratiu T (2002) Manifolds, tensor analysis, and applications, 3rd edn. Springer, New York

    MATH  Google Scholar 

  • Alexander S (2003) Combinatorial optimization: polyhedra and efficiency, vol 24. Springer, New York

  • Ali S, Shah M (2007) A Lagrangian particle dynamics approach for crowd flow segmentation and stability analysis. In: IEEE conference on computer vision and pattern recognition (CVPR’07). IEEE, pp 1–6

  • Asimov D (1993) Notes on the topology of vector fields and flows. Tech. rep., Technical report, NASA Ames Research Center. RNR-93-003 (1993)

  • Batra R, Hesselink L (1999) Feature comparisons of 3-d vector fields using earth mover’s distance. In: Proceedings of the conference on visualization’99: celebrating ten years. IEEE Computer Society Press, pp 105–114

  • Berson A, Michard M, Blanc-Benon P (2009) Vortex identification and tracking in unsteady flows. Comptes Rendus Mcanique 337(2):61–67. doi:10.1016/j.crme.2009.03.006

    Article  MATH  Google Scholar 

  • Bhatia H, Norgard G, Pascucci V, Bremer PT (2013) The Helmholtz-Hodge decomposition: a survey. IEEE Trans Vis Comput Graph 19(8):1386–1404

    Article  Google Scholar 

  • Bhatia H, Gyulassy A, Wang H, Bremer PT, Pascucci V (2014a) Robust detection of singularities in vector fields. In: Topological methods in data analysis and visualization III. Springer, New York, pp 3–18

  • Bhatia H, Pascucci V, Bremer PT (2014b) The natural Helmholtz-Hodge decomposition for open-boundary flow analysis. IEEE Trans Vis Comput Graph 20(11):1566–1578. doi:10.1109/TVCG.2014.2312012

  • Bhatia H, Pascucci V, Kirby RM, Bremer PT (2014c) Extracting features from time-dependent vector fields using internal reference frames. In: Computer graphics forum, vol 33. Wiley Online Library, pp 21–30

  • Caraballo T, Jara JC, Langa JA, Liu Z (2013) Morse decomposition of attractors for non-autonomous dynamical systems. Adv Nonlinear Stud 13(2):309–329

    Article  MathSciNet  MATH  Google Scholar 

  • Carlsson G (2009) Topology and data. Bull Am Math Soc 46(2):255–308

    Article  MathSciNet  MATH  Google Scholar 

  • Chen CM, Shen HW (2013) Graph-based seed scheduling for out-of-core FTLE and pathline computation. In: 2013 IEEE symposium on large-scale data analysis and visualization (LDAV), pp 15–23. doi:10.1109/LDAV.2013.6675154

  • Chen G, Mischaikow K, Laramee RS, Pilarczyk P, Zhang E (2007) Vector field editing and periodic orbit extraction using morse decomposition. IEEE Trans Vis Comput Graph 13(4):769–785

    Article  Google Scholar 

  • Chen G, Mischaikow K, Laramee RS, Zhang E (2008) Efficient morse decompositions of vector fields. IEEE Trans Vis Comput Graph 14(4):848–862

    Article  Google Scholar 

  • Chen X, Xie C, Wei Z (2009) Feature detection and visualization of ocean flow field sources, sinks based on vector field decomposition. In: International conference on image analysis and signal processing (IASP’09), pp 260–264. doi:10.1109/IASP.2009.5054628

  • Chen G, Deng Q, Szymczak A, Laramee RS, Zhang E (2012) Morse set classification and hierarchical refinement using conley index. IEEE Trans Vis Comput Graph 18(5):767–782

    Article  Google Scholar 

  • Chorin AJ, Marsden JE (2000) A mathematical introduction to fluid mechanics, 3rd edn. Springer, New York

    MATH  Google Scholar 

  • Conley C (1978) Isolated invariant sets and the Morse index, vol 38. American Mathematical Soc., Providence

  • Darmofal DL, Haimes R (1996) An analysis of 3d particle path integration algorithms. J Comput Phys 123(1):182–195. doi:10.1006/jcph.1996.0015

    Article  MATH  Google Scholar 

  • De Leeuw W, Van Liere R (1999a) Collapsing flow topology using area metrics. In: Proceedings of the conference on visualization’99: celebrating ten years, pp 349–354. IEEE Computer Society Press

  • De Leeuw W, Van Liere R (1999b) Visualization of global flow structures using multiple levels of topology. In: Data visualization 99. Springer, New York, , pp 45–52

  • de Leeuw W, van Liere R (2000) Multi-level topology for flow visualization. Comput Graph 24(3):325–331

    Article  Google Scholar 

  • Edelsbrunner H, Mcke EP (1990) Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms. ACM Trans Graph (TOG) 9(1):66–104

    Article  MATH  Google Scholar 

  • Effenberger F, Weiskopf D (2010) Finding and classifying critical points of 2d vector fields: a cell-oriented approach using group theory. Comput Vis Sci 13(8):377–396. doi:10.1007/s00791-011-0152-x

    Article  MathSciNet  MATH  Google Scholar 

  • Edelsbrunner H, Letscher D, Zomorodian A (2002) Topological persistence and simplification. Discret Comput Geom 28:511–533

    Article  MathSciNet  MATH  Google Scholar 

  • Edelsbrunner H, Morozov D, Patel A (2011) Quantifying transversality by measuring the robustness of intersections. Found Comput Math 11(3):345–361

    Article  MathSciNet  MATH  Google Scholar 

  • Firby PA, Gardiner CF (2001) Surface topology, 3rd edn. Elsevier, Amsterdam

  • Fisher M, Schrder P, Desbrun M, Hoppe H (2007) Design of tangent vector fields. In: ACM transactions on graphics (TOG), vol 26. ACM, p 56

  • Forman R (1998) Combinatorial vector fields and dynamical systems. Math Z 228(4):629–681

    Article  MathSciNet  MATH  Google Scholar 

  • Forman R (2002) A user’s guide to discrete Morse theory. Sém. Lothar. Combin 48:35. http://www.emis.ams.org/journals/SLC/wpapers/s48forman.html

  • Garth C, Tricoche X, Scheuermann G (2004) Tracking of vector field singularities in unstructured 3d time-dependent datasets. In: Proceedings of the conference on visualization’04. IEEE Computer Society, pp 329–336

  • Globus A, Levit C, Lasinski T (1991) A tool for visualizing the topology of three-dimensional vector fields. In: Proceedings of the 2nd conference on visualization’91 (VIS’91). IEEE Computer Society Press, Los Alamitos, pp 33–40

  • Green MA, Rowley CW, Haller G (2007) Detection of lagrangian coherent structures in three-dimensional turbulence. J Fluid Mech 572:111–120

    Article  MathSciNet  MATH  Google Scholar 

  • Guckenheimer J, Holmes P (1983) Nonlinear oscillations, dynamical systems, and bifurcations of vector fields, vol 42. Springer, New York

  • Guo Q, Mandal MK, Li MY (2005) Efficient Hodge-Helmholtz decomposition of motion fields. Pattern Recognit Lett 26(4):493–501

    Article  Google Scholar 

  • Haller G (2001) Distinguished material surfaces and coherent structures in three-dimensional fluid flows. Phys D Nonlinear Phenom 149(4):248–277

    Article  MathSciNet  MATH  Google Scholar 

  • Helman J, Hesselink L (1989) Representation and display of vector field topology in fluid flow data sets. Computer 22(8):27–36

    Article  Google Scholar 

  • Helman JL, Hesselink L (1990) Surface representations of two- and three-dimensional fluid flow topology. In: Proceedings of the 1st conference on visualization’90 (VIS’90). IEEE Computer Society Press, Los Alamitos, pp 6–13

  • Henle M (1979) A combinatorial introduction to topology. Courier Corporation

  • Hougardy S, Drake D (2004) Approximation algorithms for the weighted matching problem. Tech. Rep. 28, Oberwolfach

  • Jiang M, Machiraju R, Thompson D (2002) A novel approach to vortex core region detection. In: Data visualization 2002. Proc. VisSym02, vol 15, p 16

  • Jiang M, Machiraju R, Thompson D (2005) Detection and visualization of vortices. In: The visualization handbook, p 295

  • Johnson C (2004) Top scientific visualization research problems. Comput Graph Appl IEEE 24(4):13–17

    Article  Google Scholar 

  • Kalies W, Ban H (2006) A computational approach to Conley’s decomposition theorem. J Comput Nonlinear Dyn 1(4):312–319

    Article  Google Scholar 

  • Kalies WD, Mischaikow K, VanderVorst RCAM (2005) An algorithmic approach to chain recurrence. Found Comput Math 5(4):409–449

    Article  MathSciNet  MATH  Google Scholar 

  • Kasten J, Reininghaus J, Reich W, Scheuermann G (2014) Toward the extraction of saddle periodic orbits. In: Bremer PT, Hotz I, Pascucci V, Peikert R (eds) Topological methods in data analysis and visualization III, mathematics and visualization. Springer International Publishing, New York, pp 55–69

  • Klein T, Ertl T (2007) Scale-space tracking of critical points in 3d vector fields. In: Topology-based methods in visualization. Springer, New York, pp 35–49

  • Kuhn A, Rssl C, Weinkauf T, Theisel H (2012) A benchmark for evaluating FTLE computations. In: Pacific visualization symposium (PacificVis), 2012 IEEE. IEEE, pp 121–128

  • Laramee RS, Hauser H, Doleisch H, Vrolijk B, Post FH, Weiskopf D (2004) The state of the art in flow visualization: dense and texture-based techniques. In: Computer graphics forum, vol 23. Wiley Online Library, pp 203–221

  • Laramee RS, Hauser H, Zhao L, Post FH (2007) Topology-based flow visualization, the state of the art. In: Hauser H, Hagen H, Theisel H (eds) Topology-based methods in visualization, mathematics and visualization. Springer, Berlin, pp 1–19

    Chapter  Google Scholar 

  • Lavin Y, Batra R, Hesselink L (1998) Feature comparisons of vector fields using earth mover’s distance. In: Visualization’98. Proceedings. IEEE, pp 103–109

  • Li WC, Vallet B, Ray N, Lvy B (2006) Representing higher-order singularities in vector fields on piecewise linear surfaces. IEEE Trans Vis Comput Graph 12(5):1315–1322

    Article  Google Scholar 

  • Mann S, Rockwood A (2002) Computing singularities of 3d vector fields with geometric algebra. In: Proceedings of the conference on visualization’02. IEEE Computer Society, pp 283–290

  • Mase GT, Mase GE (2010) Continuum mechanics for engineers. CRC Press, Boca Raton

  • Milnor JW (1963) Morse theory, vol 51. Princeton University Press, Princeton

  • Mischaikow K (1999) The Conley index theory: a brief introduction. Banach Center Publ 47(1):9–19

    MathSciNet  MATH  Google Scholar 

  • Mischaikow K, Mrozek M (2002) Conley index. Handb Dyn Syst 2:393–460

    Article  MathSciNet  MATH  Google Scholar 

  • Peikert R, Sadlo F (2007) Topology-guided visualization of constrained vector fields. In: Topology-based methods in visualization. Springer, New York, pp 21–33

  • Peikert R, Sadlo F (2009) Topologically relevant stream surfaces for flow visualization. In: Proceedings of the 25th spring conference on computer graphics (SCCG’09). ACM, New York, pp 35–42. doi:10.1145/1980462.1980472

  • Petronetto F, Paiva A, Lage M, Tavares G, Lopes H, Lewiner T (2010) Meshless Helmholtz-Hodge decomposition. IEEE Trans Vis Comput Graph 16(2):338–349. doi:10.1109/TVCG.2009.61

    Article  Google Scholar 

  • Pobitzer A, Peikert R, Fuchs R, Schindler B, Kuhn A, Theisel H, Matkovic K, Hauser H (2010) On the way towards topology-based visualization of unsteady flow-the state of the art. H. und E. Reinhard (Hrsg.), Eurographics

  • Polthier K, Preu E (2000) Variational approach to vector field decomposition. In: de Leeuw WC, van Liere R (eds) Data visualization 2000, Eurographics. Springer, New York, pp 147–155

    Chapter  Google Scholar 

  • Polthier K, Preuss E (2003) Identifying vector field singularities using a discrete hodge decomposition. In: Visualization and mathematics III. Springer, New York, pp 113–134

  • Post FH, Vrolijk B, Hauser H, Laramee RS, Doleisch H (2003) The state of the art in flow visualisation: feature extraction and tracking. In: Computer graphics forum, vol 22. Wiley Online Library, New York, pp 775–792

  • Reich W, Schneider D, Heine C, Wiebel A, Chen G, Scheuermann G (2011) Combinatorial vector field topology in 3 dimensions. In: 4th workshop on topology-based methods in data analysis and visualization (TopoInVis2011)

  • Reininghaus J, Hotz I (2011) Combinatorial 2d vector field topology extraction and simplification. In: Topological methods in data analysis and visualization. Springer, New York, pp 103–114

  • Reininghaus J, Kasten J, Weinkauf T, Hotz I (2011) Combinatorial feature flow fields: tracking critical points in discrete scalar fields. Tech. rep., Technical Report 11–02, Zuse Institute Berlin

  • Rosen KH (2000) Handbook of discrete and combinatorial mathematics. CRC Press, Boca Raton

  • Sadlo F, Peikert R (2007) Efficient visualization of Lagrangian coherent structures by filtered AMR ridge extraction. IEEE Trans Vis Comput Graph 13(6):1456–1463

    Article  Google Scholar 

  • Sadlo F, Peikert R (2009) Visualizing Lagrangian coherent structures and comparison to vector field topology. In: Topology-based methods in visualization II. Springer, New York, pp 15–29

  • Sadlo F, Rigazzi A, Peikert R (2011) Time-dependent visualization of Lagrangian coherent structures by grid advection. In: Topological methods in data analysis and visualization. Springer, New York, pp 151–165

  • Salzbrunn T, Jnicke H, Wischgoll T, Scheuermann G (2008) The state of the art in flow visualization: partition-based techniques. In: SimVis, pp 75–92

  • Scheuermann G, Kruger H, Menzel M, Rockwood AP (1998) Visualizing nonlinear vector field topology. IEEE Trans Vis Comput Graph 4(2):109–116

    Article  Google Scholar 

  • Shadden SC (2006) A dynamical systems approach to unsteady systems. Ph.D. thesis, California Institute of Technology, Pasadena

  • Shadden SC, Dabiri JO, Marsden JE (2006) Lagrangian analysis of fluid transport in empirical vortex ring flows. Phys Fluids (1994-present) 18(4):047,105

  • Sipeki L, Szymczak A (2013) Simplification of Morse decompositions using Morse set mergers. Topo-In-Vis 2013

  • Skraba P, Wang B (2014) Interpreting feature tracking through the lens of robustness. In: Topological methods in data analysis and visualization III. Springer, New York, pp 19–37

  • Skraba P, Wang B, Chen G, Rosen P (2014) 2D vector field simplification based on robustness. In: 2014 IEEE pacific visualization symposium (PacificVis), pp 49–56. doi:10.1109/PacificVis.2014.17

  • Spanier EH (1982) Algebraic topology. McGraw-Hill, Maidenheach, 1966. Springer, New York

  • Stter T, Weinkauf T, Seidel HP, Theisel H (2012) Implicit integral surfaces. In: Vision, modeling, and visualization

  • Szymczak A (2011) Stable morse decompositions for piecewise constant vector fields on surfaces. Comput Graph Forum 30(3):851–860

    Article  Google Scholar 

  • Szymczak A (2013) Hierarchy of stable morse decompositions. IEEE Trans Vis Comput Graph 19(5):799–810

    Article  Google Scholar 

  • Szymczak A, Brunhart-Lupo N (2012) Nearly recurrent components in 3d piecewise constant vector fields. Comput Graph Forum 31(3pt3):1115–1124

  • Theisel H, Seidel HP (2003) Feature flow fields. In: Proceedings of the symposium on data visualisation 2003. Eurographics Association, pp 141–148

  • Theisel H, Weinkauf T, Hege HC, Seidel HP (2003) Saddle connectors-an approach to visualizing the topological skeleton of complex 3d vector fields. In: Visualization, 2003 (VIS’03). IEEE, pp 225–232

  • Theisel H, Weinkauf T, Hege HC, Seidel HP (2004) Grid-independent detection of closed stream lines in 2d vector fields. In: VMV, pp 421–428

  • Thomas W, Scheuermann G (2002) Locating closed streamlines in 3d vector fields. Methods 16:19

    Google Scholar 

  • Tong Y, Lombeyda S, Hirani AN, Desbrun M (2003) Discrete multiscale vector field decomposition. In: ACM transactions on graphics (TOG), vol 22. ACM, pp 445–452

  • Tricoche X (2002) Vector and tensor field topology simplification, tracking, and visualization. Ph.D. thesis, University of Kaiserslautern, Kaiserslautern

  • Tricoche X, Scheuermann G, Hagen H (2000a) Higher order singularities in piecewise linear vector fields. In: The mathematics of surfaces IX. Springer, New York, pp 99–113

  • Tricoche X, Scheuermann G, Hagen H (2000b) A topology simplification method for 2d vector fields. In: Visualization 2000. Proceedings. IEEE, pp 359–366

  • Tricoche X, Scheuermann G, Hagen H (2001a) Continuous topology simplification of planar vector fields. In: Proceedings of the conference on visualization’01. IEEE Computer Society, pp 159–166

  • Tricoche X, Scheuermann G, Hagen H (2001b) Topology-based visualization of time-dependent 2d vector fields. In: Proceedings of the 3rd joint Eurographics-IEEE TCVG conference on visualization. Eurographics Association, pp 117–126

  • Tricoche X, Scheuermann G, Hagen H, Clauss S (2001c) Vector and tensor field topology simplification on irregular grids. In: Data visualization 2001 (joint Eurographics-IEEE TCVG symposium on visualization proceedings). Springer, New York, pp 101–116

  • Tricoche X, Wischgoll T, Scheuermann G, Hagen H (2002) Topology tracking for the visualization of time-dependent two-dimensional flows. Comput Graph 26(2):249–257

    Article  Google Scholar 

  • Tricoche X, Garth C, Sanderson A (2011) Visualization of topological structures in area-preserving maps. IEEE Trans Vis Comput Graph 17(12):1765–1774. doi:10.1109/TVCG.2011.254

    Article  Google Scholar 

  • Tricoche X, Garth C, Sanderson A, Joy KI (2012) Visualizing invariant manifolds in area-preserving maps. In: Topological methods in data analysis and visualization II. Springer, New York, pp 109–124

  • Trotts I, Kenwright D, Haimes R (2000) Critical points at infinity: a missing link in vector field topology. In: Proc. NSF/DoE Lake Tahoe workshop on hierarchical approximation and geometrical methods for scientific visualization, vol 1. Citeseer

  • Wang B, Rosen P, Skraba P, Bhatia H, Pascucci V (2013) Visualizing robustness of critical points for 2d time-varying vector fields. Comput Graph Forum 32(3pt2):221–230

  • Weinkauf T (2008) Extraction of topological structures in 2d and 3d vector fields. Ph.D. thesis, University Magdeburg, Magdeburg. http://tinoweinkauf.net/publications/absweinkauf08phd.html

  • Weinkauf T, Theisel H (2010) Streak lines as tangent curves of a derived vector field. IEEE Trans Vis Comput Graph 16(6):1225–1234

    Article  Google Scholar 

  • Weinkauf T, Theisel H, Hege HC, Seidel HP (2004) Boundary switch connectors for topological visualization of complex 3d vector fields. In: Proceedings of the sixth joint Eurographics-IEEE TCVG conference on visualization. Eurographics Association, pp 183–192

  • Weinkauf T, Theisel H, Shi K, Hege HC, Seidel HP (2005) Extracting higher order critical points and topological simplification of 3d vector fields. In: Visualization, 2005 (VIS’05). IEEE, pp 559–566

  • Weinkauf T, Theisel H, Van Gelder A, Pang A (2011) Stable feature flow fields. IEEE Trans Vis Comput Graph 17(6):770–780

    Article  Google Scholar 

  • Weinkauf T, Hege HC, Theisel H (2012) Advected tangent curves: a general scheme for characteristic curves of flow fields. Comput Graph Forum 31:825–834

    Article  Google Scholar 

  • Wiebel A (2003) Feature detection in vector fields using the Helmholtz-Hodge decomposition. Ph.D. thesis, University of Kaiserslautern, Kaiserslautern

  • Wiebel A (2008) Localized flow, particle tracing, and topological separation analysis for flow visualization. Ph.D. thesis, Shaker Verlag, Bremen

  • Wiebel A, Garth C, Scheuermann G (2007) Computation of localized flow for steady and unsteady vector fields and its applications. IEEE Trans Vis Comput Graph 13(4):641–651. doi:10.1109/TVCG.2007.4293009

    Article  Google Scholar 

  • Wischgoll T, Scheuermann G (2001) Detection and visualization of closed streamlines in planar flows. IEEE Trans Vis Comput Graph 7(2):165–172. doi:10.1109/2945.928168

    Article  Google Scholar 

  • Wischgoll T, Scheuermann G, Hagen H (2001) Tracking closed streamlines in time dependent planar flows. In: VMV. Citeseer, pp 447–454

  • Zhang E, Mischaikow K, Turk G (2006) Vector field design on surfaces. ACM Trans Graph (TOG) 25(4):1294–1326

    Article  Google Scholar 

  • Zomorodian A (2012) Topological data analysis. In: Proceedings of symposia in applied mathematics

Download references

Acknowledgments

This work is supported by Chinese 973 Program (2015CB755604), the National Science Foundation of China (61202335, 61170157). We would like to thank Dr. He Ou-Yang for his guidance and John Lucynski for his generous advices.

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to Wenke Wang.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Wang, W., Wang, W. & Li, S. From numerics to combinatorics: a survey of topological methods for vector field visualization. J Vis 19, 727–752 (2016). https://doi.org/10.1007/s12650-016-0348-8

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s12650-016-0348-8

Keywords

Navigation