Discrete multiscale vector field decomposition

ABSTRACT

While 2D and 3D vector fields are ubiquitous in computational sciences, their use in graphics is often limited to regular grids, where computations are easily handled through finite-difference methods. In this paper, we propose a set of simple and accurate tools for the analysis of 3D discrete vector fields on arbitrary tetrahedral grids. We introduce a variational, multiscale decomposition of vector fields into three intuitive components: a divergence-free part, a curl-free part, and a harmonic part. We show how our discrete approach matches its well-known smooth analog, called the Helmotz-Hodge decomposition, and that the resulting computational tools have very intuitive geometric interpretation. We demonstrate the versatility of these tools in a series of applications, ranging from data visualization to fluid and deformable object simulation.

REFERENCES

• 1: R. Abraham , J. E. Marsden , R. Ratiu, Manifolds, tensor analysis, and applications: 2nd edition, Springer-Verlag New York, Inc., New York, NY, 1988
• 2: ABRAHAM, R., AND SHAW, C., Eds. Dynamics: The Geometry of Behavior. Ariel Press (Santa Cruz, CA), 1984.
• 3: AMROUCHE, C., BERNARDI, C., DAUGE, M., AND GIRAULT, V. Vector Potentials in Three-Dimensional Non-smooth Domains. Math. Meth. Appl. Sci. 21 (1998), pp.823--864.
• 4: Dirk Bauer , Ronald Peikert, Vortex tracking in scale-space, Proceedings of the symposium on Data Visualisation 2002, May 27-29, 2002, Barcelona, Spain
• 5: Brian Cabral , Leith Casey Leedom, Imaging vector fields using line integral convolution, Proceedings of the 20th annual conference on Computer graphics and interactive techniques, p.263-270, September 1993 [doi>10.1145/166117.166151]
• 6: Gilles Debunne , Mathieu Desbrun , Marie-Paule Cani , Alan H. Barr, Dynamic real-time deformations using space & time adaptive sampling, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.31-36, August 2001 [doi>10.1145/383259.383262]
• 7: Mathieu Desbrun , Mark Meyer , Peter Schröder , Alan H. Barr, Implicit fairing of irregular meshes using diffusion and curvature flow, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.317-324, July 1999 [doi>10.1145/311535.311576]
• 8: DESBRUN, M., MEYER, M., SCHRÖDER, P., AND BARR, A. H. Anisotropic Feature-Preserving Denoising of Height Fields and Bivariate Data. In Graphics Interface (2000), pp. 145--152.
• 9: Udo Diewald , Tobias Preuβer , Martin Rumpf, Anisotropic Diffusion in Vector Field Visualization on Euclidean Domains and Surfaces, IEEE Transactions on Visualization and Computer Graphics, v.6 n.2, p.139-149, April 2000 [doi>10.1109/2945.856995]
• 10: Ronald Fedkiw , Jos Stam , Henrik Wann Jensen, Visual simulation of smoke, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.15-22, August 2001 [doi>10.1145/383259.383260]
• 11: A. Globus , C. Levit , T. Lasinski, A tool for visualizing the topology of three-dimensional vector fields, Proceedings of the 2nd conference on Visualization '91, October 22-25, 1991, San Diego, California
• 12: Igor Guskov , Wim Sweldens , Peter Schröder, Multiresolution signal processing for meshes, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.325-334, July 1999 [doi>10.1145/311535.311577]
• 13: Anil Nirmal Hirani , Jerrold E. Marsden, Discrete exterior calculus, 2003
• 14: Wim de Leeuw , Robert van Liere, Collapsing flow topology using area metrics, Proceedings of the conference on Visualization '99: celebrating ten years, p.349-354, October 1999, San Francisco, California, United States
• 15: LINDEBERG, T. Scale-Space Theory: A Basic Tool for Analysing Structures at Different Scales. Journal of Applied Statistics 21, 2 (1994), pp. 225--270.
• 16: Stephen Mann , Alyn Rockwood, Computing singularities of 3D vector fields with Geometric Algebra, Proceedings of the conference on Visualization '02, October 27-November 01, 2002, Boston, Massachusetts
• 17: MCCORMICK, S. F. Multilevel Adaptive Methods for Partial Differential Equations --- Chapter 2: The Finite Volume Method, vol. 6. SIAM, 1989.
• 18: MEYER, M., DESBRUN, M., SCHRÖDER, P., AND BARR, A. H. Discrete Differential-Geometry Operators for Triangulated 2-Manifolds. In Proceedings of VisMath (2002).
• 19: P. Perona , J. Malik, Scale-Space and Edge Detection Using Anisotropic Diffusion, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.12 n.7, p.629-639, July 1990 [doi>10.1109/34.56205]
• 20: PINKALL, U., AND POLTHIER, K. Computing Discrete Minimal Surfaces. Experimental Mathematics 2, 1 (1993), pp. 15--36.
• 21: POLTHIER, K. Computational Aspects of Discrete Minimal Surfaces. Proceedings of the Clay Summer School on Global Theory of Minimal Surfaces (Hass, Hoffman, Jaffe, Rosenberg, Schoen, and Wolf Editors) (2002).
• 22: POLTHIER, K., AND PREUSS, E. Variational Approach to Vector Field Decomposition. Scientific Visualization, Springer Verlag (Proc. of Eurographics Workshop on Scientific Visualization) (2000).
• 23: POLTHIER, K., AND PREUSS, E. Identifying Vector Fields Singularities using a Discrete Hodge Decomposition. Visualization and Mathematics III, Eds: H. C. Hege, K. Polthier, Springer Verlag (2002).
• 24: T. Preußer , M. Rumpf, Anisotropic nonlinear diffusion in flow visualization, Proceedings of the conference on Visualization '99: celebrating ten years, p.325-332, October 1999, San Francisco, California, United States
• 25: Jos Stam, Stable fluids, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.121-128, July 1999 [doi>10.1145/311535.311548]
• 26: TAUBIN, G. Linear Anisotropic Mesh Filtering. Tech. Rep. IBM Reserach Report RC2213, 2001.
• 27: Xavier Tricoche , Gerik Scheuermann , Hans Hagen, A topology simplification method for 2D vector fields, Proceedings of the conference on Visualization '00, p.359-366, October 2000, Salt Lake City, Utah, United States
• 28: Jarke J. van Wijk, Image based flow visualization, Proceedings of the 29th annual conference on Computer graphics and interactive techniques, July 23-26, 2002, San Antonio, Texas
• 29: Rüdiger Westermann , Christopher Johnson , Thomas Ertl, A level-set method for flow visualization, Proceedings of the conference on Visualization '00, p.147-154, October 2000, Salt Lake City, Utah, United States

INDEX TERMS

Keywords:
Hodge decomposition, animation, scale-space description, variational approaches, vector fields, visualization