Search

The surface network is an application of the Morse-Smale complex to digital terrain models connecting ridges and thalwegs of the terrain in a planar, undirected graph. Although it provides a topological structure embedding critical elements of the terrain, its application to morphological analysis and hydrology remains limited mainly because the drainage network is the most relevant structure for analysis and it cannot be derived from the surface network. The drainage network is a directed, hierarchical graph formed by streams. Ridges of the surface network are not equivalent to drainage divides, which are not contained in the drainage network, and there is no direct association between thalwegs and streams. Therefore, this paper proposes to extend the surface network into a new structure that also embeds the drainage network. This is done by (1) revising the definition of ridges so that they include drainage divides and (2) assigning a flow direction to each thalweg, taking into account spurious depressions to avoid flow interruption. We show that this extended surface network can be used to compute the flow accumulation and different hydrographic features such as drainage basins and the Strahler order. The drainage network extracted from the extended surface network is compared to drainage networks computed with the traditional D8 approach in three case studies. Differences remain minor and are mainly due to the elevation inaccuracy in flat or slightly convex areas. Hence, the extended surface network provides a richer data structure allowing the use of a common topological data structure in both terrain analysis and hydrology. [ABSTRACT FROM AUTHOR]

Data quality problems may occur in various forms in structured and semi-structured data sources. This paper details an unsupervised method of analyzing data quality that is agnostic to the semantics of the data, the format of the encoding, or the internal structure of the dataset. A distance function is used to transform each record of a dataset into an n-dimensional vector of real numbers, which effectively transforms the original data into a high-dimensional point cloud. The shape of the point cloud is then efficiently examined via topological data analysis to find high-dimensional anomalies that may signal quality issues. The specific quality faults examined in this paper are the detection of records that, while not exactly the same, refer to the same entity. Our algorithm, based on topological data analysis, provides similar accuracy for both higher and lower quality data and performs better than a baseline approach for data with poor quality.

A surface network is a topological data structure formed by a set of thalwegs and ridges on a digital terrain model. Its computation relies on the detection of saddles on the terrain. Hence, computation methods must guarantee enough saddles are detected but also that no improper conflicts between ridges and thalwegs are created, leading to an inconsistent network. This paper presents a new approach that maximizes the number of saddles and ensures this topological consistency for high-resolution terrain models represented by a raster grid. The grid is triangulated in order to preserve saddles and to facilitate thalweg and ridge computation. It does not require any user parameter and lines remain aligned with triangulation edges, avoiding numerical errors. The method also includes a coherent partitioning of the terrain into hills and dales. A case study shows that the surface network computation can be achieved in reasonable time and hence can be applied to the analysis of large terrain models.

This article presents a robust Morse theory-based framework for segmenting 3D X-ray computed tomography image (CT) and computing the fabric, relative arrangement of particles, of granular ensembles. The framework includes an algorithm for computing the segmentation, a data structure for storing the segmentation and representing both individual particles and the connectivity network, and visualizations of topological descriptors of the CT image that enable interactive exploration. The Morse theory-based framework produces superior quality segmentation of a granular ensemble as compared to prior approaches based on the watershed transform. The accuracy of the connectivity network also improves. Further, the framework supports the efficient computation of various distribution statistics on the segmentation and the connectivity network. Such a comprehensive characterization and quantification of the fabric of granular ensembles is the first step towards a multiple length scale understanding of the behavior. [ABSTRACT FROM AUTHOR]

In the study of packed granular materials, the performance of a sample (e.g., the detonation of a high-energy explosive) often correlates to measurements of a fluid flowing through it. The "effective surface area," the surface area accessible to the airflow, is typically measured using a permeametry apparatus that relates the flow conductance to the permeable surface area via the Carman-Kozeny equation. This equation allows calculating the flow rate of a fluid flowing through the granules packed in the sample for a given pressure drop. However, Carman-Kozeny makes inherent assumptions about tunnel shapes and flow paths that may not accurately hold in situations where the particles possess a wide distribution in shapes, sizes, and aspect ratios, as is true with many powdered systems of technological and commercial interest. To address this challenge, we replicate these measurements virtually on micro-CT images of the powdered material, introducing a new Pore Network Model based on the skeleton of the Morse-Smale complex. Pores are identified as basins of the complex, their incidence encodes adjacency, and the conductivity of the capillary between them is computed from the cross-section at their interface. We build and solve a resistive network to compute an approximate laminar fluid flow through the pore structure. We provide two means of estimating flow-permeable surface area: (i) by direct computation of conductivity, and (ii) by identifying dead-ends in the flow coupled with isosurface extraction and the application of the Carman-Kozeny equation, with the aim of establishing consistency over a range of particle shapes, sizes, porosity levels, and void distribution patterns. [ABSTRACT FROM AUTHOR]

[Display omitted] Topological and geometric segmentation methods provide powerful concepts for detailed field analysis and visualization. However, when it comes to a quantitative analysis that requires highly accurate geometric segmentation, there is a large discrepancy between the promising theory and the available computational approaches. In this paper, we compare and evaluate various segmentation methods with the aim to identify and quantify the extent of these discrepancies. Thereby, we focus on an application from quantum chemistry: the analysis of electron density fields. It is a scalar quantity that can be experimentally measured or theoretically computed. In the evaluation we consider methods originating from the domain of quantum chemistry and computational topology. We apply the methods to the charge density of a set of crystals and molecules. Therefore, we segment the volumes into atomic regions and derive and compare quantitative measures such as total charge and dipole moments from these regions. As a result, we conclude that an accurate geometry determination can be crucial for correctly segmenting and analyzing a scalar field, here demonstrated on the electron density field. [ABSTRACT FROM AUTHOR]

Researchers in the field of connectomics are working to reconstruct a map of neural connections in the brain in order to understand at a fundamental level how the brain processes information. Constructing this wiring diagram is done by tracing neurons through high-resolution image stacks acquired with fluorescence microscopy imaging techniques. While a large number of automatic tracing algorithms have been proposed, these frequently rely on local features in the data and fail on noisy data or ambiguous cases, requiring time-consuming manual correction. As a result, manual and semi-automatic tracing methods remain the state-of-the-art for creating accurate neuron reconstructions. We propose a new semi-automatic method that uses topological features to guide users in tracing neurons and integrate this method within a virtual reality (VR) framework previously used for manual tracing. Our approach augments both visualization and interaction with topological elements, allowing rapid understanding and tracing of complex morphologies. In our pilot study, neuroscientists demonstrated a strong preference for using our tool over prior approaches, reported less fatigue during tracing, and commended the ability to better understand possible paths and alternatives. Quantitative evaluation of the traces reveals that users' tracing speed increased, while retaining similar accuracy compared to a fully manual approach. [ABSTRACT FROM AUTHOR]

A surface network is a topological data structure formed by a set of thalwegs and ridges on a digital terrain model. Its computation relies on the detection of saddles on the terrain. Hence, computation methods must guarantee enough saddles are detected but also that no improper conflicts between ridges and thalwegs are created, leading to an inconsistent network. This paper presents a new approach that maximizes the number of saddles and ensures this topological consistency for high-resolution terrain models represented by a raster grid. The grid is triangulated in order to preserve saddles and to facilitate thalweg and ridge computation. It does not require any user parameter and lines remain aligned with triangulation edges, avoiding numerical errors. The method also includes a coherent partitioning of the terrain into hills and dales. A case study shows that the surface network computation can be achieved in reasonable time and hence can be applied to the analysis of large terrain models. [ABSTRACT FROM AUTHOR]

We discuss the model for the evolution of an active region (AR) in which the graph constructed from the singular points of the magnetic field codes the AR magnetic patterns. The AR dynamic scenarios are mapped by the discrete structure of the network formed from the maxima, minima, and saddle points of the magnetic field. The AR dynamics leads to a rearrangement of the graph, graph dynamics. We discuss two graphs. The first of them is the graph of a Morse–Smale complex. It is a cellular gradient model of the magnetic field each cell of which contains a maximum, a minimum, and two saddle points. The Morse–Smale complex admits a simplification (editing) with prescribed detail that preserves the field topology. The second graph codes the AR dynamics simultaneously on different scales, in the so-called scale-space. This space is formed by a sequence of convolutions of the original magnetogram with a Gaussian kernel, so that the blurring scale is its additional coordinate. Non-Morse singular points, with a degenerate Hessian and Laplacian, are considered in each scale-space layer. The curves connecting these points in different scales form the critical paths whose vertices are called top points. The graph constructed from these points codes the structure of the degenerate AR field structures on different scales. We propose an efficient method of calculating the critical paths using a Jacobi set. The pre-flare regimes are believed to be associated with a significant change in the field topology, which controls the graph dynamics. Consequently, they must be accompanied by noticeable variations in the spectrum of eigenvalues for the discrete Laplacian of the graph (Kirchhoff–Laplace matrix). As an example, we present the evolution of the spectra for these graphs constructed from the magnetograms of the flaring AR 12673. The SDO/HMI magnetograms of the AR for the scalar line-of-sight (LOS) component served as the data. The possible connection of large variations in the spectrum with succeeding X flares is discussed. [ABSTRACT FROM AUTHOR]

We develop a new method for segmentation of molecular surfaces. Topological analysis of a scalar function defined on the surface and its associated gradient field reveals the relationship between the features of interest and critical points of the scalar function. The segmentation is obtained by associating segments with local minima/maxima. Controlled simplification of the function merges segments resulting in a hierarchical segmentation of the molecular surface. This segmentation is used to identify rigid components of proteins molecules and to study the role of cavities and protrusions in protein-protein interactions.

We present SurfCut, an algorithm for extracting a smooth, simple surface with an unknown 3D curve boundary from a noisy 3D image and a seed point. Our method is built on the novel observation that ridge curves of the Euclidean length of minimal paths ending on a level set of the solution of the eikonal equation lie on the surface. Our method extracts these ridges and cuts them to form the surface boundary. Our surface extraction algorithm is built on the novel observation that the surface lies in a valley of the eikonal equation solution. The resulting surface is a collection of minimal paths. Using the framework of cubical complexes and Morse theory, we design algorithms to extract ridges and valleys robustly. Experiments on three 3D datasets show the robustness of our method, and that it achieves higher accuracy with lower computational cost than state-of-the-art. [ABSTRACT FROM AUTHOR]

Copyright of Acta Automatica Sinica is the property of Chinese Academy of Sciences, Institute of Automation and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

We introduce an approach to quadrilateral meshing of arbitrary triangulated surfaces that combines the theoretical guarantees of Morse-based approaches with the practical advantages of parameterization methods. We first construct, through an eigensolver followed by a few Gauss-Newton iterations, a periodic four-dimensional vector field that aligns with a user-provided frame field and/or a set of features over the input mesh. A field-aligned parameterization is then greedily computed along a spanning tree based on the Dirichlet energy of the optimal periodic vector field, from which quad elements are efficiently extracted over most of the surface. The few regions not yet covered by elements are then upsampled and the first component of the periodic vector field is used as a Morse function to extract the remaining quadrangles. This hybrid parameterization- and Morse-based quad meshing method is not only fast (the parameterization is greedily constructed, and the Morse function only needs to be upsampled in the few uncovered patches), but is guaranteed to provide a feature-aligned quad mesh with non-degenerate cells that closely matches the input frame field over an arbitrary surface. We show that our approach is much faster than Morse-based techniques since it does not require a densely tessellated input mesh, and is significantly more robust than parameterization-based techniques on models with complex features. [ABSTRACT FROM AUTHOR]

We introduce T opoMS, a computational tool enabling detailed topological analysis of molecular and condensed‐matter systems, including the computation of atomic volumes and charges through the quantum theory of atoms in molecules, as well as the complete molecular graph. With roots in techniques from computational topology, and using a shared‐memory parallel approach, T opoMS provides scalable, numerically robust, and topologically consistent analysis. T opoMS can be used as a command‐line tool or with a GUI (graphical user interface), where the latter also enables an interactive exploration of the molecular graph. This paper presents algorithmic details of T opoMS and compares it with state‐of‐the‐art tools: Bader charge analysis v1.0 (Arnaldsson et al., 01/11/17) and molecular graph extraction using Critic2 (Otero‐de‐la‐Roza et al., Comput. Phys. Commun. 2014, 185, 1007). T opoMS not only combines the functionality of these individual codes but also demonstrates up to 4× performance gain on a standard laptop, faster convergence to fine‐grid solution, robustness against lattice bias, and topological consistency. T opoMS is released publicly under BSD License. © 2018 Wiley Periodicals, Inc. [ABSTRACT FROM AUTHOR]

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., 2003a ). However, previous research in this field is incomplete in the case of smooth functions. In the current paper we address the following question: Given an arbitrarily complex Morse–Smale system on a planar domain, is it possible to compute its certified (topologically correct) Morse–Smale complex? Towards this, we develop an algorithm using interval arithmetic to compute certified critical points and separatrices forming the Morse–Smale complexes of smooth functions on bounded planar domain. Our algorithm can also compute geometrically close Morse–Smale complexes. [ABSTRACT FROM AUTHOR]

Three-dimensional convex bodies can be classified in terms of the number and stability types of critical points on which they can balance at rest on a horizontal plane. For typical bodies, these are non-degenerate maxima, minima, and saddle points, the numbers of which provide a primary classification. Secondary and tertiary classifications use graphs to describe orbits connecting these critical points in the gradient vector field associated with each body. In previous work, it was shown that these classifications are complete in that no class is empty. Here, we construct 1- and 2-parameter families of convex bodies connecting members of adjacent primary and secondary classes and show that transitions between them can be realized by codimension 1 saddle-node and saddle-saddle (heteroclinic) bifurcations in the gradient vector fields. Our results indicate that all combinatorially possible transitions can be realized in physical shape evolution processes, e.g., by abrasion of sedimentary particles. [ABSTRACT FROM AUTHOR]

The shape of homogeneous, generic, smooth convex bodies as described by the Euclidean distance with nondegenerate critical points, measured from the center of mass represents a rather restricted class $${\mathcal {M}}_C$$ of Morse-Smale functions on $${\mathbb {S}}^2$$ . Here we show that even $${\mathcal {M}}_C$$ exhibits the complexity known for general Morse-Smale functions on $${\mathbb {S}}^2$$ by exhausting all combinatorial possibilities: every 2-colored quadrangulation of the sphere is isomorphic to a suitably represented Morse-Smale complex associated with a function in $${\mathcal {M}}_C$$ (and vice versa). We prove our claim by an inductive algorithm, starting from the path graph $$P_2$$ and generating convex bodies corresponding to quadrangulations with increasing number of vertices by performing each combinatorially possible vertex splitting by a convexity-preserving local manipulation of the surface. Since convex bodies carrying Morse-Smale complexes isomorphic to $$P_2$$ exist, this algorithm not only proves our claim but also generalizes the known classification scheme in Várkonyi and Domokos (J Nonlinear Sci 16:255-281, 2006). Our expansion algorithm is essentially the dual procedure to the algorithm presented by Edelsbrunner et al. (Discrete Comput Geom 30:87-10, 2003), producing a hierarchy of increasingly coarse Morse-Smale complexes. We point out applications to pebble shapes. [ABSTRACT FROM AUTHOR]

Data quality problems may occur in various forms in structured and semi-structured data sources. This paper details an unsupervised method of analyzing data quality that is agnostic to the semantics of the data, the format of the encoding, or the internal structure of the dataset. A distance function is used to transform each record of a dataset into an n-dimensional vector of real numbers, which effectively transforms the original data into a high-dimensional point cloud. The shape of the point cloud is then efficiently examined via topological data analysis to find high-dimensional anomalies that may signal quality issues. The specific quality faults examined in this paper are the detection of records that, while not exactly the same, refer to the same entity. Our algorithm, based on topological data analysis, provides similar accuracy for both higher and lower quality data and performs better than a baseline approach for data with poor quality., Competing Interests: The author declares that the research was conducted in the absence of any commercial or financial relationships that could be construed as a potential conflict of interest., (Copyright © 2022 Tudoreanu.)

Given a Morse-Smale function on an effective orientable orbifold, we construct its Morse-Smale-Witten complex. We show that critical points of a certain type have to be discarded to build a complex properly, and that gradient flows should be counted with suitable weights. Its homology is proven to be isomorphic to the singular homology of the quotient space under the self-indexing assumption. For a global quotient orbifold [M/G], such a complex can be understood as the G-invariant part of the Morse complex of M, where the G-action on generators of the Morse complex has to be defined including orientation spaces of unstable manifolds at the critical points. Alternatively in the case of global quotients, we introduce the notion of weak group actions on Morse-Smale-Witten complexes for non-invariant Morse-Smale functions on M, which give rise to genuine group actions on the level of homology. [ABSTRACT FROM AUTHOR]

In many areas, scientists deal with increasingly high-dimensional data sets. An important aspect for these scientists is to gain a qualitative understanding of the process or system from which the data is gathered. Often, both input variables and an outcome are observed and the data can be characterized as a sample from a high-dimensional scalar function. This work presents the R package msr for exploratory data analysis of multivariate scalar functions based on the Morse-Smale complex. The Morse-Smale complex provides a topologically meaningful decomposition of the domain. The msr package implements a discrete approximation of the Morse-Smale complex for data sets. In previous work this approximation has been exploited for visualization and partition-based regression, which are both supported in the msr package. The visualization combines the Morse-Smale complex with dimension-reduction techniques for a visual summary representation that serves as a guide for interactive exploration of the high-dimensional function. In a similar fashion, the regression employs a combination of linear models based on the Morse-Smale decomposition of the domain. This regression approach yields topologically accurate estimates and facilitates interpretation of general trends and statistical comparisons between partitions. In this manner, the msr package supports high-dimensional data understanding and exploration through the Morse-Smale complex.

Abstract: The Morse–Smale (MS) complex has proven to be a useful tool in extracting and visualizing features from scalar-valued data. However, existing algorithms to compute the MS complex are restricted to either piecewise linear or discrete scalar fields. This paper presents a new combinatorial algorithm to compute MS complexes for two-dimensional piecewise bilinear functions defined on quadrilateral meshes. We derive a new invariant of the gradient flow within a bilinear cell and use it to develop a provably correct computation, unaffected by numerical instabilities. This includes a combinatorial algorithm to detect and classify critical points as well as a way to determine the asymptotes of cell-based saddles and their intersection with cell edges. Finally, we introduce a simple data structure to compute and store integral lines on quadrilateral meshes which by construction prevents intersections and allows to enforce constraints on the gradient flow that preserve known invariants. [Copyright &y& Elsevier]

This article introduces a novel partition-based regression approach that incorporates topological information. Partition-based regression typically introduces a quality-of-fit-driven decomposition of the domain. The emphasis in this work is on a topologically meaningful segmentation. Thus, the proposed regression approach is based on a segmentation induced by a discrete approximation of the Morse–Smale complex. This yields a segmentation with partitions corresponding to regions of the function with a single minimum and maximum that are often well approximated by a linear model. This approach yields regression models that are amenable to interpretation and have good predictive capacity. Typically, regression estimates are quantified by their geometrical accuracy. For the proposed regression, an important aspect is the quality of the segmentation itself. Thus, this article introduces a new criterion that measures the topological accuracy of the estimate. The topological accuracy provides a complementary measure to the classical geometrical error measures and is very sensitive to overfitting. The Morse–Smale regression is compared to state-of-the-art approaches in terms of geometry and topology and yields comparable or improved fits in many cases. Finally, a detailed study on climate-simulation data demonstrates the application of the Morse–Smale regression. Supplementary Materials are available online and contain an implementation of the proposed approach in the R packagemsr, an analysis and simulations on the stability of the Morse–Smale complex approximation, and additional tables for the climate-simulation study. [ABSTRACT FROM PUBLISHER]

Establishing corresponding features on two non-rigidly deformed 3D surfaces is a challenging and well-studied problem in computer graphics. Unlike previous approaches that constrain the matching between feature pairs using isometry-invariant distance metrics, we constrain the matching using a discrete connectivity graph derived from the Morse-Smale complex of the Auto Diffusion Function. We observed that the graph remains stable even for surfaces differing by topology or by significant deformation. This algorithm is simple to implement and efficient to run. When tested on a range of examples, our algorithm produces comparable results with state-of-art methods on surfaces with strong isometry but with greatly improved efficiency, and often gets better correspondences on surfaces with larger shape variances. [ABSTRACT FROM AUTHOR]

Extremal lines and surfaces are features of a 3D scalar field where the scalar function becomes minimal or maximal with respect to a local neighborhood . These features are important in many applications, e.g. computer tomography, fluid dynamics, cell biology . We present a novel topological method to extract these features using discrete Morse theory. In particular, we extend the notion of 'separatrix persistence' from 2D to 3D, which gives us a robust estimation of the feature strength for extremal lines and surfaces. Not only does it allow us to determine the most important (parts of) extremal lines and surfaces, it also serves as a robust filtering measure of noise-induced structures. Our purely combinatorial method does not require derivatives or any other numerical computations . [ABSTRACT FROM AUTHOR]

We propose an efficient algorithm that computes the Morse-Smale complex for 3D gray-scale images. This complex allows for an efficient computation of persistent homology since it is, in general, much smaller than the input data but still contains all necessary information. Our method improves a recently proposed algorithm to extract the Morse-Smale complex in terms of memory consumption and running time. It also allows for a parallel computation of the complex. The computational complexity of the Morse-Smale complex extraction solely depends on the topological complexity of the input data. The persistence is then computed using the Morse-Smale complex by applying an existing algorithm with a good practical running time. We demonstrate that our method allows for the computation of persistent homology for large data on commodity hardware. [ABSTRACT FROM AUTHOR]

Rocking stones, balanced in counter-intuitive positions, have always intrigued geologists. In our paper, we explain this phenomenon based on high-precision scans of pebbles which exhibit similar behavior. We construct their convex hull and the heteroclinic graph carrying their equilibrium points. By systematic simplification of the arising Morse-Smale complex in a one-parameter process, we demonstrate that equilibria occur typically in highly localized groups (flocks), the number of the latter being reliably observed and determined by hand experiments. Both local and global (micro and macro) equilibria can be either stable or unstable. Most commonly, rocks and pebbles are balanced on stable local equilibria belonging to stable flocks. However, it is possible to balance a convex body on a stable local equilibrium belonging to an unstable flock and this is the intriguing mechanical scenario corresponding to rocking stones. Since outside observers can only reliably perceive flocks, the last described situation will appear counter-intuitive. A comparison between computer experiments and hand experiments reveals that the latter are consistent, that is, the flocks can be reliably counted and the pebble classification system proposed in our previous work is robustly applicable. We also find an interesting logarithmic relationship between the flatness of pebbles and the average number of global equilibrium points, indicating a close relationship between classical shape categories and the new classification system. [ABSTRACT FROM AUTHOR]

This work introduces a method to hierarchically segment articulated shapes into meaningful parts and to register these parts across populations of near-isometric shapes (e.g. head, arms, legs and fingers of humans in different body postures). The method exploits the isometry invariance of eigenfunctions of the Laplace-Beltrami operator and uses topological features (level sets at important saddles) for the segmentation. Concepts from persistent homology are employed for a hierarchical representation, for the elimination of topological noise and for the comparison of eigenfunctions. The obtained parts can be registered via their spectral embedding across a population of near isometric shapes. This work also presents the highly accurate computation of eigenfunctions and eigenvalues with cubic finite elements on triangle meshes and discusses the construction of persistence diagrams from the Morse-Smale complex as well as the relation to size functions. [ABSTRACT FROM AUTHOR]

Abstract: This paper proposes the use of the surface-based Laplace–Beltrami and the volumetric Laplace eigenvalues and eigenfunctions as shape descriptors for the comparison and analysis of shapes. These spectral measures are isometry invariant and therefore allow for shape comparisons with minimal shape pre-processing. In particular, no registration, mapping, or remeshing is necessary. The discriminatory power of the 2D surface and 3D solid methods is demonstrated on a population of female caudate nuclei (a subcortical gray matter structure of the brain, involved in memory function, emotion processing, and learning) of normal control subjects and of subjects with schizotypal personality disorder. The behavior and properties of the Laplace–Beltrami eigenvalues and eigenfunctions are discussed extensively for both the Dirichlet and Neumann boundary condition showing advantages of the Neumann vs. the Dirichlet spectra in 3D. Furthermore, topological analyses employing the Morse–Smale complex (on the surfaces) and the Reeb graph (in the solids) are performed on selected eigenfunctions, yielding shape descriptors, that are capable of localizing geometric properties and detecting shape differences by indirectly registering topological features such as critical points, level sets and integral lines of the gradient field across subjects. The use of these topological features of the Laplace–Beltrami eigenfunctions in 2D and 3D for statistical shape analysis is novel. [Copyright &y& Elsevier]

The Morse-Smale (MS) complex has proven to be a useful tool in extracting and visualizing features from scalar-valued data. However, efficient computation of the MS complex for large scale data remains a challenging problem. We describe a new algorithm and easily extensible framework for computing MS complexes for large scale data of any dimension where scalar values are given at the vertices of a closure-finite and weak topology (OW) complex, therefore enabling computation on a wide variety of meshes such as regular grids, simplicial meshes, and adaptive multiresolution (AMR) meshes. A new divide-and-conquer strategy allows for memory-efficient computation of the MS complex and simplification on-the-fly to control the size of the output. In addition to being able to handle various data formats, the framework supports implementation-specific optimizations, for example, for regular data. We present the complete characterization of critical point cancellations in all dimensions. This technique enables the topology based analysis of large data on off-the-shelf computers. In particular we demonstrate the first full computation of the MS complex for a 1 billion/1024³ node grid on a laptop computer with 2Gb memory. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

Resampling raw surface meshes is one of the most fundamental operations used by nearly all digital geometry processing systems. The vast majority of this work has focused on triangular remeshing, yet quadrilateral meshes are preferred for many surface PDE problems, especially fluid dynamics, and are best suited for defining Catmull-Clark subdivision surfaces. We describe a fundamentally new approach to the quadrangulation of manifold polygon meshes using Laplacian eigenfunctions, the natural harmonics of the surface. These surface functions distribute their extrema evenly across a mesh, which connect via gradient flow into a quadrangular base mesh. An iterative relaxation algorithm simultaneously refines this initial complex to produce a globally smooth parameterization of the surface. From this, we can construct a well-shaped quadrilateral mesh with very few extraordinary vertices. The quality of this mesh relies on the initial choice of eigenfunction, for which we describe algorithms and hueristics to efficiently and effectively select the harmonic most appropriate for the intended application. [ABSTRACT FROM AUTHOR]

We combine topological and geometric methods to construct a multiresolution representation for a function over a twodimensional domain. In a preprocessing stage, we create the Morse-Smale complex of the function and progressively simplify its topology by cancelling pairs of critical points. Based on a simple notion of dependency among these cancellations, we construct a hierarchical data structure supporting traversal and reconstruction operations similarly to traditional geometry-based representations. We use this data structure to extract topologically valid approximations that satisfy error bounds provided at runtime. [ABSTRACT FROM AUTHOR]