Spin image is a powerful shape descriptor, useful in a point set or surface registration. However, the usage of spin images is hampered by issues such as sensitivity to noise and sampling rate and time-consuming matching process. We propose a novel spin-image-based local surface descriptor named spin contour to alleviate these problems. This descriptor is not an image but a 2-D point set. Comparisons show that the spin contour is robust to noise and sampling differences. The matching time is also improved over spin images.

We introduce an algorithm for construction of the Morse hierarchy, i.e., a hierarchy of Morse decompositions of a piecewise constant vector field on a surface driven by stability of the Morse sets with respect to perturbation of the vector field. Our approach builds upon earlier work on stable Morse decompositions, which can be used to obtain Morse sets of user-prescribed stability. More stable Morse decompositions are coarser, i.e., they consist of larger Morse sets. In this work, we develop an algorithm for tracking the growth of Morse sets and topological events (mergers) that they undergo as their stability is gradually increased. The resulting Morse hierarchy can be explored interactively. We provide examples demonstrating that it can provide a useful coarse overview of the vector field topology.

Recent advances in vector field topologymake it possible to compute its multi-scale graph representations for autonomous 2D vector fields in a robust and efficient manner. One of these representations is a Morse Connection Graph (MCG), a directed graph whose nodes correspond to Morse sets, generalizing stationary points and periodic trajectories, and arcs - to trajectories connecting them. While being useful for simple vector fields, the MCG can be hard to comprehend for topologically rich vector fields, containing a large number of features. This paper describes a visual representation of the MCG, inspired by previous work on graph visualization. Our approach aims to preserve the spatial relationships between the MCG arcs and nodes and highlight the coherent behavior of connecting trajectories. Using simulations of ocean flow, we show that it can provide useful information on the flow structure. This paper focuses specifically on MCGs computed for piecewise constant (PC) vector fields. In particular, we describe extensions of the PC framework that make it more flexible and better suited for analysis of data on complex shaped domains with a boundary. We also describe a topology simplification scheme that makes our MCG visualizations less ambiguous. Despite the focus on the PC framework, our approach could also be applied to graph representations or topological skeletons computed using different methods.

Abstract We present an algorithm for computing nearly recurrent components, that represent areas of close to circulating or stagnant flow, for 3D piecewise constant (PC) vector fields defined on regular grids. Using a number of analytical and simulated data sets, we demonstrate that nearly recurrent components can provide interesting insight into the topological structure of 3D vector fields. Our approach is based on prior work on Morse decompositions for PC vector fields on surfaces and extends concepts previously developed with this goal in mind to the case of 3D vector fields defined on regular grids. Our contributions include a description of trajectories of 3D piecewise constant vector fields and an extension of the transition graph, a finite directed graph that represents all trajectories, to the 3D case. Nearly recurrent components are defined by strongly connected components of the transition graph.

Morse decomposition provides a numerically stable topological representation of vector fields that is crucial for their rigorous interpretation. However, Morse decomposition is not unique, and its granularity directly impacts its computational cost. In this paper, we propose an automatic refinement scheme to construct the Morse Connection Graph (MCG) of a given vector field in a hierarchical fashion. Our framework allows a Morse set to be refined through a local update of the flow combinatorialization graph, as well as the connection regions between Morse sets. The computation is fast because the most expensive computation is concentrated on a small portion of the domain. Furthermore, the present work allows the generation of a topologically consistent hierarchy of MCGs, which cannot be obtained using a global method. The classification of the extracted Morse sets is a crucial step for the construction of the MCG, for which the Poincare´ index is inadequate. We make use of an upper bound for the Conley index, provided by the Betti numbers of an index pair for a translation along the flow, to classify the Morse sets. This upper bound is sufficiently accurate for Morse set classification and provides supportive information for the automatic refinement process. An improved visualization technique for MCG is developed to incorporate the Conley indices. Finally, we apply the proposed techniques to a number of synthetic and realworld simulation data to demonstrate their utility.

In this paper, we introduce a new approach to computing a Morse decomposition of a vector field on a triangulated manifold surface. The basic idea is to convert the input vector field to a piecewise constant (PC) vector field, whose trajectories can be computed using simple geometric rules. To overcome the intrinsic difficulty in PC vector fields (in particular, discontinuity along mesh edges), we borrow results from the theory of differential inclusions. The input vector field and its PC variant have similar Morse decompositions. We introduce a robust and efficient algorithm to compute Morse decompositions of a PC vector field. Our approach provides subtriangle precision for Morse sets. In addition, we describe a Morse set classification framework which we use to color code the Morse sets in order to enhance the visualization. We demonstrate the benefits of our approach with three well-known simulation data sets, for which our method has produced Morse decompositions that are similar to or finer than those obtained using existing techniques, and is over an order of magnitude faster.

Abstract Numerical simulations and experimental observations are inherently imprecise. Therefore, most vector fields of interest in scientific visualization are known only up to an error. In such cases, some topological features, especially those not stable enough, may be artifacts of the imprecision of the input. This paper introduces a technique to compute topological features of user‐prescribed stability with respect to perturbation of the input vector field. In order to make our approach simple and efficient, we develop our algorithms for the case of piecewise constant (PC) vector fields. Our approach is based on a super‐transition graph, a common graph representation of all PC vector fields whose vector value in a mesh triangle is contained in a convex set of vectors associated with that triangle. The graph is used to compute a Morse decomposition that is coarse enough to be correct for all vector fields satisfying the constraint. Apart from computing stable Morse decompositions, our technique can also be used to estimate the stability of Morse sets with respect to perturbation of the vector field or to compute topological features of continuous vector fields using the PC framework.

Computing correspondence between time frames of a time-dependent 3D surface is essential for the understanding of its motion and deformation. In particular, it can be a useful tool in compression, editing, texturing, or analysis of the physical or structural properties of deforming objects. However, correspondence information is not trivial to obtain for experimentally acquired 3D animations, such as time-dependent visual hulls (typically represented as either a binary occupancy grid or as a sequence of meshes of varying connectivity). In this article we present a new nonrigid fitting method that can compute such correspondence information for objects that do not undergo large volume or topological changes, such as living creatures. Experimental results show that it is robust enough to handle visual hull data, allowing to convert it into a constant connectivity mesh with vertices moving in time. Our procedure first creates a rest-state mesh from one of the input frames. This rest-state mesh is then fitted to the consecutive frames. We do this by iteratively displacing its vertices so that a combination of surface distance and elastic potential energy is minimized. A novel rotation compensation method enables us to obtain high-quality results with linear elasticity, even in presence of significant bending.

We present a new method of fitting an element-free volumetric model to a sequence of deforming surfaces of a moving object. Given a sequence of visual hulls, we iteratively fit an element-free elastic model to the visual hull in order to extract the optimal pose of the captured volume. The fitting of the volumetric model is acheived by minimizing a combination of elastic potential energy, a surface distance measure, and a self-intersection penalty for each frame. A unique aspect of our work is that the model is mesh free - since the model is represented as a point cloud, it is easy to construct, manipulate and update the model as needed. Additionally, linear elasicity with rotation compensation makes it possible to handle local deformations and large rotations of body parts much more efficiently than other volume fitting approaches. Our experimental results for volume fitting and capture in a multi-view camera setting demonstrate the robustness of element-free elastic models against noise and self-occlusions.

For time-dependent scalar fields, one is often interested in topology changes of contours in time. In this paper, we focus on describing how contours split and merge over a certain time interval. Rather than attempting to describe all individual contour splitting and merging events, we focus on the simpler and therefore more tractable in practice problem: describing and querying the cumulative effect of the splitting and merging events over a user-specified time interval. Using our system one can, for example, find all contours at time t/sub 0/ that continue to two contours at time t/sub 1/ without hitting the boundary of the domain. For any such contour, there has to be a bifurcation happening to it somewhere between the two times, but, in addition to that, many other events may possibly happen without changing the cumulative outcome (e.g. merging with several contours born after t/sub 0/ or splitting off several contours that disappear before t/sub 1/). Our approach is flexible enough to enable other types of queries, if they can be cast as counting queries for numbers of connected components of intersections of contours with certain simply connected domains. Examples of such queries include finding contours with large life spans, contours avoiding certain subset of the domain over a given time interval or contours that continue to two at a later time and then merge back to one some time later. Experimental results show that our method can handle large 3D (2 space dimensions plus time) and 4D (3D+time) datasets. Both preprocessing and query algorithms can easily be parallelized.

There are numerous algorithms in graphics and visualization whose performance is known to decay as the topological complexity of the input increases. On the other hand, the standard pipeline for 3D geometry acquisition often produces 3D models that are topologically more complex than their real forms. We present a simple and efficient algorithm that allows us to simplify the topology of an isosurface by alternating the values of some number of voxels. Its utility and performance are demonstrated on several examples, including signed distance functions from polygonal models and CT scans.

Abstract We present a simple method for compressing very large and regularly sampled scalar fields. Our method is particularlyattractive when the entire data set does not fit in memory and when the sampling rate is high relative to thefeature size of the scalar field in all dimensions. Although we report results for and data sets, the proposedapproach may be applied to higher dimensions. The method is based on the new Lorenzo predictor, introducedhere, which estimates the value of the scalar field at each sample from the values at processed neighbors. The predictedvalues are exact when the n‐dimensional scalar field is an implicit polynomial of degree n − 1 . Surprisingly,when the residuals (differences between the actual and predicted values) are encoded using arithmetic coding,the proposed method often outperforms wavelet compression in an L ∞ sense. The proposed approach may beused both for lossy and lossless compression and is well suited for out‐of‐core compression and decompression,because a trivial implementation, which sweeps through the data set reading it once, requires maintaining only asmall buffer in core memory, whose size barely exceeds a single ( n −1)‐ dimensional slice of the data. Categories and Subject Descriptors (according to ACM CCS): I.3.5 [Computer Graphics]: Compression, scalar fields,out‐of‐core.

Summary form only given. The connectivity of a typical triangle mesh representing a 3D object for a graphics or geometric modeling application exhibits a lot of regularity. While a lot of aspects of triangle mesh regularity have not been formally described, the simplest regularity measure is the compactness of the distribution of vertex degrees. In a regular mesh, most of the vertices have degree 6 or close to 6. Algorithms that can effectively take advantage of mesh regularity to decrease the size of the connectivity code will perform better in most practical cases. The Edgebreaker algorithm converts a manifold triangle mesh into a string of symbols in {C,L,E,R,S} (called the CLERS string), each of them corresponding to a triangle of the encoded mesh. The CLERS string can be turned into a binary string using an entropy coding algorithm.

Irregular tetrahedral meshes, which are popular in many engineering and scientific applications, often contain a large number of vertices. A mesh of V vertices and T tetrahedra requires 48 V bits or less to store the vertex coordinates, 4/spl middot/T/spl middot/log/sub 2/(V) bits to store the tetrahedra-vertex incidence relations, also called connectivity information, and kV bits to store the k-bit value samples associated with the vertices. Given that T is 5 to 7 times larger than V and that V often exceeds 32/sup 3/, the storage space required for the connectivity is larger than 300 V bits and thus dominates the overall storage cost. Our "implants spray" compression approach introduced in the paper reduces this cost to about 30 V bits or less-a 10:1 compression ratio. Furthermore, implant spray supports the progressive refinement of a crude model through a series of vertex-splits operations.