This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Topologically Clean Distance Fields
November/December 2007 (vol. 13 no. 6)
pp. 1432-1439
Analysis of the results obtained from material simulations is important in the physical sciences. Our research was motivated by the need to investigate the properties of a simulated porous solid as it is hit by a projectile. This paper describes two techniques for the generation of distance fields containing a minimal number of topological features, and we use them to identify features of the material. We focus on distance fields defined on a volumetric domain considering the distance to a given surface embedded within the domain. Topological features of the field are characterized by its critical points. Our first method begins with a distance field that is computed using a standard approach, and simplifies this field using ideas from Morse theory. We present a procedure for identifying and extracting a feature set through analysis of the MS complex, and apply it to find the invariants in the clean distance field. Our second method proceeds by advancing a front, beginning at the surface, and locally controlling the creation of new critical points. We demonstrate the value of topologically clean distance fields for the analysis of filament structures in porous solids. Our methods produce a curved skeleton representation of the filaments that helps material scientists to perform a detailed qualitative and quantitative analysis of pores, and hence infer important material properties. Furthermore, we provide a set of criteria for finding the “difference” between two skeletal structures, and use this to examine how the structure of the porous solid changes over several timesteps in the simulation of the particle impact.

[1] T. F. Banchoff, Critical points and curvature for embedded polyhedral surfaces. Am. Math. Monthly, 77: 475–485, 1970.
[2] P.-T. Bremer, H. Edelsbrunner, B. Hamann, and V. Pascucci, A topological hierarchy for functions on triangulated surfaces. IEEE Transactions on Visualization and Computer Graphics, 10 (4): 385–396, 2004.
[3] E. M. Bringa, J. U. Cazamias, P. Erhart, J. Stolken, N. Tanushev, B. D. Wirth, R. E. Rudd, and M. J. Caturla, Atomistic shock hugoniot simulation of single-crystal copper. Journal of Applied Physics, 96 (7): 3793–3799, 2004.
[4] H. Carr, J. Snoeyink, and M. van de Panne, Simplifying flexible isosurfaces using local geometric measures. In Proc. IEEE Conf. Visualization, pages 497–504, 2004.
[5] F. Cazals, F. Chazal, and T. Lewiner, Molecular shape analysis based upon the morse-smale complex and the connolly function. In SCG '03: Proceedings of the nineteenth annual symposium on Computational geometry, pages 351–360, New York, NY, USA, 2003. ACM Press.
[6] Y. Chiang and X. Lu, Progressive simplification of tetrahedral meshes preserving all isosurface topologies. Computer Graphics Forum, 20 (3): 493–504, 2003.
[7] P. Cignoni, D. Constanza, C. Montani, C. Rocchini, and R. Scopigno, Simplification of tetrahedral meshes with accurate error evaluation. In Proc. IEEE Conf. Visualization, pages 85–92, 2000.
[8] N. D. Cornea, D. Silver, and P. Min, Curve-skeleton applications. IEEE Conf. Visualization, 0: 95–102, 2005.
[9] H. Edelsbrunner, Geometry and Topology for Mesh Generation. Cambridge Univ. Press, England, 2001.
[10] H. Edelsbrunner, J. Harer, V. Natarajan, and V. Pascucci, Morse-Smale complexes for piecewise linear 3-manifolds. In Proc. 19th Ann. Sympos. Comput. Geom., pages 361–370, 2003.
[11] H. Edelsbrunner, J. Harer, and A. Zomorodian, Hierarchical Morse-Smale complexes for piecewise linear 2-manifolds. Discrete and Computational Geometry, 30 (1): 87–107, 2003.
[12] T. Gerstner and R. Pajarola, Topology preserving and controlled topology simplifying multiresolution isosurface extraction. In Proc. IEEE Conf. Visualization, pages 259–266, 2000.
[13] I. Guskov and Z. Wood, Topological noise removal. In Proc. Graphics Interface, pages 19–26, 2001.
[14] A. Gyulassy, V. Natarajan, V. Pascucci, P.-T. Bremer, and B. Hamann, Topology-based simplification for feature extraction from 3d scalar fields. In Proc. IEEE Conf. Visualization, pages 535–542, 2005.
[15] A. Gyulassy, V. Natarajan, V. Pascucci, P. T. Bremer, and B. Hamann, A topological approach to simplification of three-dimensional scalar fields. IEEE Transactions on Visualization and Computer Graphics (special issue IEEE Visualization 2005), pages 474–484, 2006.
[16] F. Horz, R. Bastien, J. Borg, J. P. Bradley, J. C. Bridges, D. E. Brownlee, M. J. Burchell, M. Chi, M. J. Cintala, Z. R. Dai, Z. Djouadi, G. Dominguez, T. E. Economou, S. A. J. Fairey, C. Floss, I. A. Franchi, G. A. Graham, S. F. Green, P. Heck, P. Hoppe, J. Huth, H. Ishii, A. T. Kearsley, J. Kissel, J. Leitner, H. Leroux, K. Marhas, K. Messenger, C. S. Schwandt, T. H. See, C. Snead, I. Stadermann, Frank J., T. Stephan, R. Stroud, N. Teslich, J. M. Trigo-Rodriguez, A. J. Tuzzolino, D. Troadec, P. Tsou, J. Warren, A. Westphal, P. Wozniakiewicz, I. Wright, and E. Zinner, Impact Features on Stardust: Implications for Comet 81P/Wild 2 Dust. Science, 314 (5806): 1716–1719, 2006.
[17] Z. Insepov and I. Yamada, Molecular dynamics simulation of cluster ion bombardment of solid surfaces. Nuclear Instruments and Methods in Physics Research Section B: Beam Interactions with Materials and Atoms, 99: 248–252, May 1995.
[18] D. Laney, M. Bertram, M. Duchaineau, and N. Max, Multiresolution distance volumes for progressive surface compression. Proceedings of 3D Data Processing Visualization and Transmission, 00: 470–479, 2002.
[19] Y. Matsumoto, An Introduction to Morse Theory. Amer. Math. Soc., 2002. Translated from Japanese by K. Hudson and M. Saito.
[20] Y. Mishin, M. J. Mehl, D. A. Papaconstantopoulos, A. F. Voter, and J. D. Kress, Structural stability and lattice defects in copper: Ab initio, tight-binding, and embedded-atom calculations. Phys. Rev. B, 63 (22): 224106, May 2001.
[21] L. E. Murr, S. A. Quinones, E. F. T.,A. Ayala, O. L. Valerio, F. Hrz, and R. P. Bernhard, The low-velocity-to-hypervelocity penetration transition for impact craters in metal targets. Materials Science and Engineering, 256: 166–182, November 1998.
[22] G. Reeb, Sur les points singuliers d'une forme de pfaff complètement intégrable ou d'une fonction numérique. Comptes Rendus de L'Académie ses Séances, Paris, 222: 847–849, 1946.
[23] J. A. Sethian, A fast marching level set method for monotonically advancing fronts. Proc. nat. Acad. Sci, 93 (4): 1591–1595, Sept 1996.
[24] S. Smale, On gradient dynamical systems. Ann. of Math., 74: 199–206, 1961.
[25] A. Szymczak and J. Vanderhyde, Extraction of topologically simple isosurfaces from volume datasets. In Proc. IEEE Conf. Visualization, pages 67–74, 2003.
[26] A. Szymczak and J. Vanderhyde, Simplifying the topology of volume datasets: an opportunistic approach. Technical Report 09, 2005.
[27] S. Takahashi, G. M. Nielson, Y. Takeshima, and I. Fujishiro, Topological volume skeletonization using adaptive tetrahedralization. In GMP '04: Proceedings of the Geometric Modeling and Processing 2004, page 227, Washington, DC, USA, 2004. IEEE Computer Society.
[28] S. Takahashi, Y. Takeshima, and I. Fujishiro, Topological volume skeletonization and its application to transfer function design. Graphical Models, 66 (1): 24–49, 2004.
[29] J. Tsitsiklis, Efficient algorithms for globally optimal trajectories. Automatic Control, IEEE Transactions on, 40 (9): 1528–1538, Sept 1995.
[30] Z. Wood, H. Hoppe, M. Desbrun, and P. Schröder, Removing excess topology from isosurfaces. ACM Transactions on Graphics, 23 (2): 190–208, 2004.
[31] H. Zhao, A fast sweeping method for eikonal equations. Mathematics of Computation, 74: 603–627, Sept 2004.

Index Terms:
Morse theory, Morse-Smale complex, distance field, topological simplification, wavefront, critical point, porous solid, material science
Citation:
Attila Gyulassy, Mark Duchaineau, Vijay Natarajan, Valerio Pascucci, Eduardo Bringa, Andrew Higginbotham, Bernd Hamann, "Topologically Clean Distance Fields," IEEE Transactions on Visualization and Computer Graphics, vol. 13, no. 6, pp. 1432-1439, Nov.-Dec. 2007, doi:10.1109/TVCG.2007.70603
Usage of this product signifies your acceptance of the Terms of Use.