Topological Methods in Data Analysis and Visualization

Ambient isotopic approximations are fundamental for correct representation of the embedding of geometric objects in R ³, with a detailed geometric construction given here. Using that geometry, an algorithm is presented for efficient update of these isotopic approximations for dynamic visualization with a molecular simulation.

We present a novel algorithm for automatic parameterization oftube-like surfaces of arbitrarygenus such as the surfaces of knots, trees, blood vessels, neurons, or any tubular graph with a globally consistentstripe texture. Mathematically these surfaces can be described as thickened graphs, and the calculatedparameterizationstripe will follow either around thetube, along the underlying graph, a spiraling combination of both, or obey an arbitrary texture map whosecharts have a 180 degree symmetry.We use the principalcurvature frame field of the underlyingtube-like surface to guide the creation of a global, topologically consistentstripeparameterization of the surface. Our algorithm extends the QuadCover algorithm and is based, first, on the use of so-called projectivevector fields instead of frame fields, and second, on different types ofbranch points. That does not only simplify the mathematical theory, but also reduces computation time by the decomposition of the underlying stiffness matrices.

The (apparent) contour of a smooth mapping from a 2-manifold to the plane, f :𝕄→ℝ ², is the set of critical values, that is, the image of the points at which the gradients of the two component functions are linearly dependent. Assuming 𝕄 is compact and orientable and measuring difference with the erosion distance, we prove that the contour is stable.

Many interesting segmentations take the form of cell complexes. We present a method to infer a 3D cell complex from of a series of 2D cross-sections. We restrict our attention to the class of complexes whose duals resemble triangulations. This class includes microstructures of polycrystalline materials, as well as other cellular structures found in nature. Given a prescribed matching of 2D cells in adjacent cross-sections we produce a 3D complex spanning these sections such that matched 2-cells are contained in the interior of the same 3-cell. The reconstruction method considers only the topological structure of the input. After an initial 3D complex is recovered, the structure is altered to accommodate geometric properties of the dataset. We evaluate the method using ideal, synthetic datasets as well as serial-sectioned micrographs from a sample oftantalum metal.

Interdisciplinary efforts in modeling and simulating phenomena have led to complex multi-physics models involving different physical properties and materials in the same system. Within a 3d domain, substructures of lower dimensions appear at the interface between different materials. Correspondingly, an unstructuredtetrahedral mesh used for such a simulation includes 2d and 1d substructures embedded in the vertices, edges and faces of the mesh.The simplification of suchtetrahedral meshes must preserve (1) the geometry and the topology of the 3d domain, (2) the simulated data and (3) the geometry and topology of the embedded substructures. Although intensive research has been conducted on the first two goals, the third objective has received little attention.This paper focuses on the preservation of the topology of 1d and 2d substructures embedded in an unstructuredtetrahedral mesh, during edge collapse simplification. We define these substructures as simplicial sub-complexes of the mesh, which is modeled as an extended simplicial complex. We derive a robust algorithm, based on combinatorial topology results, in order to determine if an edge can be collapsed without changing the topology of both the mesh and all embedded substructures. Based on this algorithm we have developed a system for simplifying scientific datasets defined on irregular tetrahedral meshes with substructures. The implementation of our system is discussed in detail. We demonstrate the power of our system with real world scientific datasets from electromagnetism simulations.

The Morse-Smale complex is an effective topology-based representation for identifying, ordering, and selectively removing features in scalar-valued data. Several algorithms are known for its effective computation, however, common problems pose practical challenges for any feature-finding approach using the Morse-Smale complex. We identify these problems and present practical solutions: (1) we identify the cause of spurious critical points due to simulation of simplicity, and present a general technique for solving it; (2) we improve simplification performance by reordering critical point cancellation operations and introducing an efficient data structure for storing the arcs of the complex; (3) we present a practical approach for handling boundary conditions.

Ascending and descending Morse complexes, defined by a scalar function f over a manifold domain M, decompose M into regions of influence of the critical points of f, thus representing themorphology of the scalar function f over M in a compact way. Here, we introduce two simplification operators on Morse complexes which work in arbitrary dimensions and we discuss their interpretation as n-dimensional Euler operators. We consider a dual representation of the two Morse complexes in terms of an incidence graph and we describe how our simplification operators affect the graph representation. This provides the basis for defining a multi-scale graph-based model of Morse complexes in arbitrary dimensions.

The Jacobi set of two Morse functions defined on a 2-manifold is the collection of points where the gradients of the functions align with each other or where one of the gradients vanish. It describes the relationship between functions defined on the same domain, and hence plays an important role in multi-field visualization. The Jacobi set of twopiecewise linear functions may contain several components indicative of noisy or a feature-rich dataset. We pose the problem of simplification as the extraction oflevel sets and offset contours and describe an algorithm to compute and simplify Jacobi sets in a robust manner.

This paper investigates a combinatorial approach to vector field topology. The theoretical basis is given by Robin Forman’s work on a combinatorial Morse theory for dynamical systems defined on general simplicial complexes. We formulateForman’s theory in a graph theoretic setting and provide a simple algorithm for the construction and topological simplification of combinatorial vector fields on 2D manifolds. Given a combinatorial vector field we are able to extract its topological skeleton including allperiodic orbits. Due to the solid theoretical foundation we know that the resulting structure is always topologically consistent. We explore the applicability and limitations of this combinatorial approach with several examples and determine its robustness with respect to noise.

We present a novel algorithm for the geometric extraction of stream volume segmentation for visualization of grid-less flow simulations. Our goal is the segmentation of different paths through a mixing tube where the flow is represented by scattered point sets approximated with moving least squares. The key challenges are thewatertight construction of boundary representations from separatrices. These are obtained by integrating and intersectingstream surfaces starting at separation and attachment lines at boundaries of flow obstacles. A major challenge is the robust integration of stream lines at boundaries with no-slip condition such that closed volume segments are obtained. Our results show the segmentation of volumes taking consistent paths through a mixing tube with six partitioning blades. Slicing these volumes provides valuable insight into the quality of the mixing process.

We propose a topology-based segmentation of 2D symmetric tensor fields, which results in cells bounded by tensorlines. We are particularly interested in the influence of the interpolation scheme on the topology, considering eigenvector-based and component-wise linear interpolation. When using eigenvector-based interpolation the most significant modification to the standard topology extraction algorithm is the insertion of additional vertices at degenerate points. A subsequent Delaunay re-triangulation leads to connections between close degenerate points. These new connections create degenerate edges and tri angles.When comparing the resulting topology per triangle with the one obtained by component-wise linear interpolation the results are qualitatively similar, but our approach leads to a less “cluttered” segmentation.

Lagrangian coherent structures play an important role in the analysis of unsteady vector fields because they represent the time-dependent analog to vector field topology. Nowadays, they are often obtained as ridges in the finite-time Lyapunov exponent of the vector field. However, one drawback of this quantity is its very high computational cost because a trajectory needs to be computed for every sample in the space-time domain. A focus of this paper are Lagrangian coherent structures that are related to predefined regions such as boundaries, i.e. related to flow attachment and flow separation phenomena. It presents an efficient method for computing the finite-time Lyapunov exponent and its height ridges only in these regions, and in particular,grid advection for the efficient computation of time series of the finite-time Lyapunov exponent, exploiting temporal coherence.

Interfaces between materials with different mechanical properties play an important role in technical applications. Nowadaysmolecular dynamics simulations are used to observe the behavior of such compound materials at the atomic level. Due to different atom crystal sizes,dislocations in the atom crystal structure occur once external forces are applied, and it has been observed that studying the change of thesedislocations can provide further understanding of macroscopic attributes like elasticity and plasticity. Standard visualization techniques such as the rendering of individual atoms work for 2D data or sectional views; however, visualizingdislocations in 3D using such methods usually fail due to occlusion and clutter. In this work we propose to extract and visualize the structure ofdislocations, which summarizes the commonly employed filtered atomistic renderings into a concise representation. The benefits of our approach are clearer images while retaining relevant data and easier visual tracking of topological changes over time.

We present a user-assisted approach to extracting and visualizing structural features from point clouds obtained by terrestrial and airborne laser scanning devices. We apply a multi-scale approach to express the membership of local point environments to corresponding geometric shape classes in terms of probability. This information is filtered and combined to establish feature graphs which can be visualized in combination with the color-encoded feature and structural probability estimates of the measured raw point data. Our method can be used, for example, for exploring geological point data scanned from multiple viewpoints.

In this paper we applyvector field topology methods to amathematical model for the fluid dynamics of reaggregation processes in tissue engineering. The experimental background are dispersed embryonic retinal cells, which reaggregate in a rotation culture on a gyratory shaker, according to defined rotation and culture conditions. Under optimal conditions, finally complex 3D spheres result. In order to optimize high throughput drug testing systems of biological cell and tissue models, a major aim is to understand the role which the fluid dynamics plays in this process. To allow for a mathematical analysis, an experimental model system was set up, using micro-beads instead of spheres within the culture dish. The qualitative behavior of this artificial model was monitored in time by using a camera. For this experimental setup amathematical model for the bead-fluid dynamics was derived, analyzed and simulated. The simulations showed that the beads form distinctive clusters in a layer close to the bottom of the petri dish. To analyze these patterns further, we perform a topological analysis of thevelocity field within this layer of the fluid. We find that traditional two-dimensional visualization techniques like path lines, streak lines and currenttime-dependent topology approaches are not able to answer the posed questions, for example they do not allow to find the location of clusters. We discuss the problems of these techniques and develop a new approach that measures thedensity of advected particles in the flow to find the moving point of particleaggregation. Using thedensity field the path of the movingaggregation point is extracted.

Contour, split and join trees can be defined as functors acting on the category of scalar fields, whose morphisms are value-preserving functions. The categorical definition provides a natural way to efficiently compute a variety of topological properties of all contours, sublevel or superlevel components in a scalar field. The result is a labeling of the contour, split or join tree and can be used to find all contours, sublevel or superlevel sets with desired properties.

We describe an algorithm for airway segmentation from Computed Tomography (CT) scans based on this paradigm. It computes all sublevel components in thick slices of the input image that have simple topology and branching structure. The output is a connected component of the union of all such sublevel components. This procedure can be viewed as a local thresholding approach, where the local thresholds are determined based on topological analysis of sublevel sets.

Many computational modeling pipelines for geometry processing and visualization focus on topologically and geometrically accurate shape reconstruction of “primal” space, meaning the surface of interest and the volume it contains. Certain features of a surface such as pockets, tunnels, and voids (small, closed components) often represent important properties of the model and yet are difficult to detect or visualize in a model of primal space alone. It is natural, then, to consider what information can be gained from a model and visualization of complementary space, i.e. the space exterior to but still “near” the surface in question. In this paper, we show how complementary space can be used as a tool for both uncertainty and dynamics visualizations and analysis.

We describe a combinatorial streaming algorithm to extract features which identify regions of local intense rates of mixing in twoterascale turbulent combustion simulations. Our algorithm allows simulation data comprised of scalar fields represented on 728x896x512 or 2025x1600x400 grids to be processed on a single relatively lightweight machine. The turbulence-induced mixing governs the rate of reaction and hence is of principal interest in these combustion simulations. We use our feature extraction algorithm to compare two very different simulations and find that in both the thickness of the extracted features grows with decreasing turbulence intensity. Simultaneous consideration of results of applying the algorithm to the HO₂ mass fraction field indicates that autoignition kernels near the base of a lifted flame tend not to overlap with the high mixing rate regions.

Tracking features and exploring their temporal dynamics can aid scientists in identifying interesting time intervals in a simulation and serve as basis for performing quantitative analyses of temporal phenomena. In this paper, we develop a novel approach for tracking subsets of isosurfaces, such as burning regions in simulated flames, which are defined as areas of high fuel consumption on a temperature isosurface. Tracking such regions as they merge and split over time can provide important insights into the impact of turbulence on the combustion process. However, the convoluted nature of the temperature isosurface and its rapid movement make this analysis particularly challenging.

Our approach tracks burning regions by extracting a temperature isovolume from the four-dimensional space-time temperature field. It then obtains isosurfaces for the original simulation time steps and labels individual connected “burning” regions based on the local fuel consumption value. Based on this information, a boundary surface between burning and non-burning regions is constructed. TheReeb graph of this boundary surface is thetracking graph for burning regions.