Tiago Etiene, Luis Gustavo Nonato, Carlos Scheidegger, Julien Tierny, Thomas Peters, Valerio Pascucci, Mike Kirby, Claudio Silva. IEEE TVCG, Accepted.

The broad goals of verifiable visualization rely on correct algorithmic implementations. We extend a framework for verification of isosurfacing implementations to check topological properties. Specifically, we use stratified Morse theory and digital topology to design algorithms which verify topological invariants. Our extended framework reveals unexpected behavior and coding mistakes in popular publicly-available isosurface codes.

Emden Gansner, Yifan Hu, Carlos Scheidegger, Stephen North. Pacific Vis, 2011.

Graphs are often used to encapsulate relationships between objects. Node-link diagrams, commonly used to visualize graphs, suffer from visual clutter on large graphs. Edge bundling is an effective technique for alleviating clutter and revealing high-level edge patterns. Previous methods for general graph layouts either require a control mesh to guide the bundling process, which can introduce high variation in curvature along the bundles, or all-to-all force and compatibility calculations, which is not scalable. We propose a multilevel agglomerative edge bundling method based on a principled approach of minimizing ink needed to represent edges, with additional constraints on the curvature of the resulting splines. The proposed method is much faster than previous ones, able to bundle hundreds of thousands of edges in seconds, and one million edges in a few minutes.

David Koop, Carlos E. Scheidegger, Juliana Freire, Claudio Silva. IPAW 2010.

Provenance has become an increasingly important part of documenting, verifying, and reproducing scientific research, but as users seek to extend or share results, it may be impractical to start from the exact original steps due to system configuration differ- ences, library updates, or new algorithms. Although there have been several approaches for capturing workflow provenance, the problem of managing upgrades of the underly- ing tools and libraries orchestrated by workflows has been largely overlooked. In this paper we consider the problem of maintaining and re-using the provenance of work- flow upgrades. We propose different kinds of upgrades that can be applied, including automatic mechanisms, developer-specified, and user-defined. We show how to cap- ture provenance from such upgrades and suggest how this provenance might be used to influence future upgrades. We also describe our implementation of these upgrade techniques.

Tiago Etiene, Carlos Scheidegger, L. Gustavo Nonato, Robert M. Kirby, Claudio Silva. IEEE TVCG, 15(6):1227–1234, 2009.

Visual representations of isosurfaces are ubiquitous in the scientific and engineering literature. In this paper, we present techniques to assess the behavior of isosurface extraction codes. Where applicable, these techniques allow us to distinguish whether anomalies in isosurface features can be attributed to the underlying physical process or to artifacts from the extraction process. Such scientific scrutiny is at the heart of verifiable visualization - subjecting visualization algorithms to the same verification process that is used in other components of the scientific pipeline. More concretely, we derive formulas for the expected order of accuracy (or convergence rate) of several isosurface features, and compare them to experimentally observed results in the selected codes. This technique is practical: in two cases, it exposed actual problems in implementations. We provide the reader with the range of responses they can expect to encounter with isosurface techniques, both under “normal operating conditions” and also under adverse conditions. With the results of the verification process, practitioners can judiciously select the isosurface extraction technique appropriate for their problem of interest, and have confidence in its behavior.

Hao Wang, Carlos Scheidegger, Claudio Silva. IEEE TVCG, 15(4):572–582, 2009.

We investigate the influence of bandwidth selection in the reconstruction quality of point-based surfaces. While the problem has received relatively little attention in the literature, we show that appropriate selection plays a significant role in the quality of reconstructed surfaces. We show how to compute optimal bandwidths for one class of moving-least squares surfaces by formulating the polynomial fitting step as a kernel regression problem for both noiseless and noisy data. In the context of Levin’s projection, we also discuss the implications of the two-step projection for bandwidth selection. We show experimental comparisons of our method, which outperforms heuristically chosen functions and weights previously proposed. We also show the influence of bandwidth on the reconstruction quality of different formulations of point-based surfaces. We provide, to the best of our knowledge, the first quantitative comparisons between different MLS surface formulations and their optimal bandwidths. Using these experiments, we investigate the choice of effective bandwidths for these alternative formulations. We conclude with a discussion of how to effectively compare the different MLS formulations in the literature.

Carlos Scheidegger, John Schreiner, Brian Duffy, Hamish Carr, Claudio Silva. IEEE TVCG, 14(6):1659-1666, 2008. (Vis 2008)

Recent results have shown a link between geometric properties of isosurfaces and statistical properties of the underlying sampled data. However, this has two defects: not all of the properties described converge to the same solution, and the statistics computed are not always invariant under isosurface-preserving transformations. We apply Federer’s Coarea Formula from geometric measure theory to explain these discrepancies. We describe an improved substitute for histograms based on weighting with the inverse gradient magnitude, develop a statistical model that is invariant under isosurface-preserving transformations, and argue that this provides a consistent method for algorithm evaluation across multiple datasets based on histogram equalization. We use our corrected formulation to reevaluate recent results on average isosurface complexity, and show evidence that noise is one cause of the discrepancy between the expected figure and the observed one.

David Koop, Carlos E. Scheidegger, Steven P. Callahan, Juliana Freire, Claudio T. Silva. IEEE TVCG 14(6):1691-1698, 2008 (Vis 2008).

Building visualization and analysis pipelines is a large hurdle in the adoption of visualization and workflow systems by domain scientists. In this paper, we propose techniques to help users construct pipelines by consensus, automatically suggesting completions based on a database of previously created pipelines. In particular, we compute correspondences between existing pipeline subgraphs from the database, and use these to predict sets of likely pipeline additions to a given partial pipeline. By presenting these predictions in a carefully designed interface, users can create visualizations and other data products more efficiently because they can augment their normal work patterns with the suggested completions. We present an implementation of our technique in a publicly-available, open-source scientific workflow system and demonstrate efficiency gains in real-world situations.

Carlos A. Dietrich, Carlos Scheidegger, Joao Comba, Luciana Nedel, Claudio T. Silva. IEEE TVCG 14(6):1651-1658, 2008.

Marching Cubes is the most popular isosurface extraction algorithm due to its simplicity, efficiency and robustness. It has been widely studied, improved, and extended. While a lot of early work was concerned with efficiency and correctness issues, lately there is a push to improve the quality of Marching Cubes meshes so that they can be used for computational experiments. In this work we present a new classification of MC cases that we call Edge Groups, which helps elucidate the issues that impact the triangle quality of the meshes that the method generates. This formulation allows a more systematic way to bound the triangle quality, and is general enough to extend to other polyhedral cell shapes used in other polygonization algorithms. Using this analysis, we also discuss ways to improve the quality of the resulting triangle mesh, including some that require only minor modifications of the original algorithm.