Ichitaro Yamazaki, Vijay Natarajan, Zhaojun Bai, and Bernd Hamann.
Proc. IEEE Intl. Conf. Shape Modeling and Applications (SMI), 2006, 4-13. [Paper]
Extracting features from point sets is becoming increasingly important for purposes like model classification, matching, and exploration. We introduce a technique for segmenting a point-sampled surface into distinct features without explicit construction of a mesh or other surface representation. Our approach achieves computational efficiency through a three-phase segmentation process. The first phase of the process uses a topological approach to define features and coarsens the input, resulting in a set of supernodes. A graph cut is employed in the second phase to bisect the set of supernodes. Similarity between supernodes is computed as a weighted combination of geodesic distances and connectivity. Repeated application of the graph cut results in a hierarchical segmentation of the point input. In the last phase, a segmentation of the original point set is constructed by refining the segmentation of the supernodes based on their associated feature sizes. We apply our segmentation algorithm on laser-scanned models to evaluate its ability to capture geometric features in complex data sets.
Vijay Natarajan, Yusu Wang, Peer-Timo Bremer, Valerio Pascucci, and Bernd Hamann.
Computer Aided Geometric Design (special issue on Applications of Geometric Modeling in the Life Sciences), 23(6), 2006, 495-509. [Paper]
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.
Attila Gyulassy, Vijay Natarajan, Valerio Pascucci, Peer-Timo Bremer and Bernd Hamann.
IEEE Conference on Visualization, 2005, 535-542. [Paper]
Invited paper in IEEE Transactions on Visualization and Computer Graphics, 12(4), 2006, 474-484. [Paper]
We describe a topological approach for simplifying continuous functions defined on volumetric domains. The Morse-Smale complex provides a segmentation of the domain into monotonic regions having uniform gradient flow behavior. We present a combinatorial algorithm that simplifies the Morse-Smale complex by repeated application of two atomic operations that removes pairs of critical points. The simplification procedure leaves important critical points untouched, and is therefore useful for extracting features. We present a visualization of the simplified topology.
Vijay Natarajan and Valerio Pascucci.
Intl. Conference on Shape Modeling and Applications (SMI), 2005, 320-325. [Paper][Video]
Invited paper in Computer Graphics and Geometry, 8(1), 2006, 66-76.
The 3D Morse-Smale complex is a fundamental topological construct that partitions the domain of a real-valued function into regions having uniform gradient flow behavior. In this paper, we consider the construction and selective presentation of cells of the Morse-Smale complex and its use in the analysis and visualization of scientific datasets. We take advantage of the fact that cells of different dimension often characterize different types of features present in the data. For example, critical points pinpoint changes in topology by showing where components of the level sets are created, destroyed or modified in genus. The edges of the Morse-Smale complex segment filament-like features that are not explicitly modeled in the original data. Interactive selection and rendering of portions of the Morse-Smale complex introduces fundamental data management challenges due to the unstructured nature of the complex even for structured inputs. We describe a data structure that stores the Morse-Smale complex and allows efficient selective traversal of regions of interest. Finally, we illustrate the practical use of this approach by applying it to cryo-electron microscopy data of protein molecules.
Herbert Edelsbrunner, John Harer, Vijay Natarajan, and Valerio Pascucci.
IEEE Conference on Visualization, 2004, 275-280. [Paper][Video]
We introduce local and global comparison measures for a collection of $k \leq d$ real-valued smooth functions on a common $d$-dimensional Riemannian manifold. For $k = d = 2$ we relate the measures to the set of critical points of one function restricted to the level sets of the other. The definition of the measures extends to piecewise linear functions for which they are easy to compute. The computation of the measures forms the centerpiece of a software tool which we use to study scientific datasets.
Vijay Natarajan and Herbert Edelsbrunner.
IEEE Transactions on Visualization and Computer Graphics, 10(5), 2004, 587-597. [Paper]
We present an algorithm for the simplification of density maps in 3D. We assume that an input function specified at vertices of a triangulation and linearly interpolated within the tetrahedra. The fundamental operation in the simplification procedure is a topology preserving edge contraction. We describe simple and local conditions that can be used to check if an edge contraction preserves topology. These conditions are derived from the generic link conditions for 3-complexes described by Dey et. al. Besides providing a good approximation of the density map, the algorithm also aims to generate a mesh with good quality elements. We achieve this additional goal using a novel extension of the quadric error metric. We visualize isosurfaces extracted from the simplified density maps and use them along with an approximation error computation to evaluate the algorithm. We also develop validation tools to test the correctness of the simplified model and perform statistical measurements on the critical points of the density map to study the relationship between geometric and topological simplification.
Vijay Natarajan.
Ph.D. thesis. Department of Computer Science, Duke Univ., Durham, NC, 2004.
[PDF one-sided][Hyperlinked]
[PDF two-sided][Hyperlinked]
[Video 1][Video 2][Video 3]
Scientists attempt to understand physical phenomena by studying various quantities measured over the region of interest. A majority of these quantities are scalar (real-valued) functions. These functions are typically studied using traditional visualization techniques like isosurface extraction, volume rendering etc. As the data grows in size and becomes increasingly complex, these techniques are no longer effective. State of the art visualization methods attempt to automatically extract features and annotate a display of the data with a visualization of its features. In this thesis, we study and extract the topological features of the data and use them for visualization. We have three results:
- An algorithm that simplifies a scalar function defined over a tetrahedral mesh. In addition to minimizing the error introduced by the approximation of the function, the algorithm improves the mesh quality and preserves the topology of the domain. We perform an extensive set of experiments to study the effect of requiring better mesh quality on the approximation error and the level of simplification possible. We also study the effect of simplification on the topological features of the data.
- An extension of three-dimensional Morse-Smale complexes to piecewise linear 3-manifolds and an efficient algorithm to compute its combinatorial analog. Morse-Smale complexes partition the domain into regions with similar gradient flows. Letting $n$ be the number of vertices in the input mesh, the running time of the algorithm is proportional to $n\log (n)$ plus the total size of the input mesh plus the total size of the output. We develop a visualization tool that displays different substructures of the Morse-Smale complex.
- A new comparison measure between $k$ functions defined on a common $d$-manifold. For the case $d=k=2$, we give alternative formulations of the definition based on a Morse theoretic point of view. We also develop visualization software that performs local comparison between pairs of functions in datasets containing multiple and sometimes time-varying functions.
Kree Cole-MacLaughlin, Herbert Edelsbrunner, John Harer, Vijay Natarajan and Valerio Pascucci.
Proc. ACM Symposium on Computational Geometry, 2003, 344-350. [Paper]
Invited paper in Discrete and Computational Geometry, 32(2), 2004, 231-244
Given a Morse function $f$ over a 2-manifold with or without boundary, the Reeb graph is obtained by contracting the connected components of the level sets to points. We prove tight upper and lower bounds on thenumber of loops in the Reeb graph that depend on the genus, the number of boundary components,and whether or not the 2-manifold is orientable. We also give an algorithm that constructs the Reeb graph in time O($n \log n$), where $n$ is the number of edges in the triangulation used to represent the 2-manifold and the Morse function.
Herbert Edelsbrunner, John Harer, Vijay Natarajan, and Valerio Pascucci.
Proc. ACM Symposium on Computational Geometry, 2003, 361-370. [Paper]
Morse functions are used in differential topology to study the topology of manifolds. We use the results from Morse theory to study the topological features of natural phenomena. For example, we can use the results of this work in x-ray crystallography to reconstruct geometry by following ridges connecting electron density maxima.A Morse-Smale Complex partitions the 3D domain into cells with similar gradient flow characteristics. The objective of this work is to design and implement an algorithm for constructing 3-dimensional Morse-Smale Complexes with a guarantee on structural correctness. We define a piecewise linear analog of the 3D Morse-Smale Complexes following the approach used for 2D Morse-Smale Complexes. The boundary surfaces of the cells are computed by following steepest descending/ascending edges starting from the saddle points (index-2 and index-3 critical points). The challenge is to ensure that the discrete approximation of the data does not lead to intersections between the paths. Our algorithm constructs the Morse-Smale Complex in a consistent manner by merging the surfaces when they come together and making sure that they remain together henceforth.
B.S. Panda, Vijay Natarajan and Sajal K. Das..
Parallel Processing Letters, 12(1), 2002, 51-64.
Conference version: International Parallel and Distributed Processing Symposium, 2001. [Paper]
Visibility graphs of simple polygons have been characterized and there are algorithms that construct these graphs efficiently. I looked at the problem of reconstruction of the polygon given it's visibility graph. Obviously such a polygon will not be unique. This problem was solved for a subclass i.e. Hamiltonian 2-separator chordal graphs. The polygons that were constructed in this case were monotone polygons. We gave parallel algorithms to verify if a given graph was a Hamiltonian 2-separator chordal graph and to reconstruct a polygon from this graph. We gave a characterizations of these graphs in terms of the maximal cliques that naturally lead to parallel algorithms for their recognition. We also give a parallel algorithm to reconstruct the corresponding polygon.