Hypergraphs provide a natural way to represent polyadic relationships in network data. For large hypergraphs, it is often difficult to visually detect structures within the data. Recently, a scalable polygon-based visualization approach was developed allowing hypergraphs with thousands of hyperedges to be simplified and examined at different levels of detail. However, this approach is not guaranteed to eliminate all of the visual clutter caused by unavoidable overlaps. Furthermore, meaningful structures can be lost at simplified scales, making their interpretation unreliable. In this paper, we define hypergraph structures using the bipartite graph representation, allowing us to decompose the hypergraph into a union of structures including topological blocks, bridges, and branches, and to identify exactly where unavoidable overlaps must occur. We also introduce a set of topology preserving and topology altering atomic operations, enabling the preservation of important structures while reducing unavoidable overlaps to improve visual clarity and interpretability in simplified scales. We demonstrate our approach in several real-world applications.

There have been recent advances in the analysis and visualization of 3D symmetric tensor fields, with a focus on the robust extraction of tensor field topology. However, topological features such as degenerate curves and neutral surfaces do not live in isolation. Instead, they intriguingly interact with each other. In this paper, we introduce the notion of topological graph for 3D symmetric tensor fields to facilitate global topological analysis of such fields. The nodes of the graph include degenerate curves and regions bounded by neutral surfaces in the domain. The edges in the graph denote the adjacency information between the regions and degenerate curves. In addition, we observe that a degenerate curve can be a loop and even a knot and that two degenerate curves (whether in the same region or not) can form a link. We provide a definition and theoretical analysis of individual degenerate curves in order to help understand why knots and links may occur. Moreover, we differentiate between wedges and trisectors, thus making the analysis more detailed about degenerate curves. We incorporate this information into the topological graph. Such a graph can not only reveal the global structure in a 3D symmetric tensor field but also allow two symmetric tensor fields to be compared. We demonstrate our approach by applying it to solid mechanics and material science data sets.

Hypergraph visualization has many applications in network data analysis. Recently, a polygon-based representation for hypergraphs has been proposed with demonstrated benefits. However, the polygon-based layout often suffers from excessive self-intersections when the input dataset is relatively large. In this paper, we propose a framework in which the hypergraph is iteratively simplified through a set of atomic operations. Then, the layout of the simplest hypergraph is optimized and used as the foundation for a reverse process that brings the simplest hypergraph back to the original one, but with an improved layout. At the core of our approach is the set of atomic simplification operations and an operation priority measure to guide the simplification process. In addition, we introduce necessary definitions and conditions for hypergraph planarity within the polygon representation. We extend our approach to handle simultaneous simplification and layout optimization for both the hypergraph and its dual. We demonstrate the utility of our approach with datasets from a number of real-world applications.

Orbifolds are a modern mathematical concept that arises in the research of hyperbolic geometry with applications in computer graphics and visualization. In this paper, we make use of rooms with mirrors as the visual metaphor for orbifolds. Given any arbitrary two-dimensional kaleidoscopic orbifold, we provide an algorithm to construct a Euclidean, spherical, or hyperbolic polygon to match the orbifold. This polygon is then used to create a room for which the polygon serves as the floor and the ceiling. With our system that implements Möbius transformations, the user can interactively edit the scene and see the reflections of the edited objects. To correctly visualize non-Euclidean orbifolds, we adapt the rendering algorithms to account for the geodesics in these spaces, which light rays follow. Our interactive orbifold design system allows the user to create arbitrary two-dimensional kaleidoscopic orbifolds. In addition, our mirror-based orbifold visualization approach has the potential of helping our users gain insight on the orbifold, including its orbifold notation as well as its universal cover, which can also be the spherical space and the hyperbolic space.

3D asymmetric tensor fields have found many applications in science and engineering domains, such as fluid dynamics and solid mechanics. 3D asymmetric tensors can have complex eigenvalues, which makes their analysis and visualization more challenging than 3D symmetric tensors. Existing research in tensor field visualization focuses on 2D asymmetric tensor fields and 3D symmetric tensor fields. In this paper, we address the analysis and visualization of 3D asymmetric tensor fields. We introduce six topological surfaces and one topological curve, which lead to an eigenvalue space based on the tensor mode that we define. In addition, we identify several non-topological feature surfaces that are nonetheless physically important. Included in our analysis are the realizations that triple degenerate tensors are structurally stable and form curves, unlike the case for 3D symmetric tensors fields. Furthermore, there are two different ways of measuring the relative strengths of rotation and angular deformation in the tensor fields, unlike the case for 2D asymmetric tensor fields. We extract these feature surfaces using the A-patches algorithm. However, since three of our feature surfaces are quadratic, we develop a method to extract quadratic surfaces at any given accuracy. To facilitate the analysis of eigenvector fields, we visualize a hyperstreamline as a tree stem with the other two eigenvectors represented as thorns in the real domain or the dual-eigenvectors as leaves in the complex domain. To demonstrate the effectiveness of our analysis and visualization, we apply our approach to datasets from solid mechanics and fluid dynamics.

N-ary relationships, which relate $N$ entities where $N$ is not necessarily two, can be visually represented as polygons whose vertices are the entities of the relationships. Manually generating a high-quality layout using this representation is labor-intensive. In this paper, we provide an automatic polygon layout generation algorithm for the visualization of N-ary relationships. At the core of our algorithm is a set of objective functions motivated by a number of design principles that we have identified. These objective functions are then used in an optimization framework that we develop to achieve high-quality layouts. Recognizing the duality between entities and relationships in the data, we provide a second visualization in which the roles of entities and relationships in the original data are reversed. This can lead to additional insight about the data. Furthermore, we enhance our framework for a joint optimization on the primal layout (original data) and the dual layout (where the roles of entities and relationships are reversed). This allows users to inspect their data using two complementary views. We apply our visualization approach to a number of datasets that include co-authorship data and social contact pattern data.

Hypnotic line art is a modern form in which white narrow curved ribbons, with the width and direction varying along each path over a black background, provide a keen sense of 3D objects regarding surface shapes and topological contours. However, the procedure of manually creating such line art work can be quite tedious and time-consuming. In this article, we present an interactive system that offers a What-You-See-Is-What-You-Get (WYSIWYG) scheme for producing hypnotic line art images by integrating and placing evenly-spaced streamlines in tensor fields. With an input picture segmented, the user just needs to sketch a few illustrative strokes to guide the construction of a tensor field for each part of the objects therein. Specifically, we propose a new method which controls, with great precision, the aesthetic layout and artistic drawing of an array of streamlines in each tensor field to emulate the style of hypnotic line art. Given several parameters for streamlines such as density, thickness, and sharpness, our system is capable of generating professional-level hypnotic line art work. With great ease of use, it allows art designers to explore a wide variety of possibilities to obtain hypnotic line art results of their own preferences.

Mode surfaces are the generalization of degenerate curves and neutral surfaces, which constitute 3D symmetric tensor field topology. Efficient analysis and visualization of mode surfaces can provide additional insight into not only degenerate curves and neutral surfaces, but also how these features transition into each other. Moreover, the geometry and topology of mode surfaces can help domain scientists better understand the tensor fields in their applications. Existing mode surface extraction methods can miss features in the surfaces. Moreover, the mode surfaces extracted from neighboring cells have gaps, which make their subsequent analysis difficult. In this paper, we provide novel analysis on the topological structures of mode surfaces, including a common parameterization of all mode surfaces of a tensor field using 2D asymmetric tensors. This allows us to not only better understand the structures in mode surfaces and their interactions with degenerate curves and neutral surfaces, but also develop an efficient algorithm to seamlessly extract mode surfaces, including neutral surfaces. The seamless mode surfaces enable efficient analysis of their geometric structures, such as the principal curvature directions. We apply our analysis and visualization to a number of solid mechanics data sets.

We introduce an approach for the visual analysis of eye movement data from two people playing competitive virtual board games. Our approach provides methods to temporally synchronize and spatially register gaze and mouse recordings from two eye tracking devices. Analysts can examine such fused data visually with a combination of techniques: attention maps and gaze plots as well as a temporal summary of the distance between gaze positions and mouse events of the two players. We show different game scenarios from the competitive game Go, which is especially complex for analyzing strategies of individual players, to demonstrate our methods. In general, our visual analysis approach can provide analysts with insights into strategies, learning processes, and means of communication between people.

Asymmetric tensor fields have found applications in many science and engineering domains, such as fluid dynamics. Recent advances in the visualization and analysis of 2D asymmetric tensor fields focus on pointwise analysis of the tensor field and effective visualization metaphors such as colors, glyphs, and hyperstreamlines. In this paper, we provide a novel multi-scale topological analysis framework for asymmetric tensor fields on surfaces. Our multi-scale framework is based on the notions of eigenvalue and eigenvector graphs. At the core of our framework are the identification of atomic operations that modify the graphs and the scale definition that guides the order in which the graphs are simplified to enable clarity and focus for the visualization of topological analysis on data of different sizes. We also provide efficient algorithms to realize these operations. Furthermore, we provide physical interpretation of these graphs. To demonstrate the utility of our system, we apply our multi-scale analysis to data in computational fluid dynamics.

3D symmetric tensor fields appear in many science and engineering fields, and topology-driven analysis is important in many of these application domains, such as solid mechanics and fluid dynamics. Degenerate curves and neutral surfaces are important topological features in 3D symmetric tensor fields. Existing methods to extract degenerate curves and neutral surfaces often miss parts of the curves and surfaces, respectively. Moreover, these methods are computationally expensive due to the lack of knowledge of structures of degenerate curves and neutral surfaces. In this paper, we provide theoretical analysis on the geometric and topological structures of degenerate curves and neutral surfaces of 3D linear tensor fields. These structures lead to parameterizations for degenerate curves and neutral surfaces that can not only provide more robust extraction of these features but also incur less computational cost. We demonstrate the benefits of our approach by applying our degenerate curve and neutral surface detection techniques to solid mechanics simulation data sets.

Branched covering spaces are a mathematical concept which originates from complex analysis and topology and has applications in tensor field topology and geometry remeshing. Given a manifold surface and an -way rotational symmetry field, a branched covering space is a manifold surface that has an -to-1 map to the original surface except at the ramification points, which correspond to the singularities in the rotational symmetry field. Understanding the notion and mathematical properties of branched covering spaces is important to researchers in tensor field visualization and geometry processing, and their application areas. In this paper, we provide a framework to interactively design and visualize the branched covering space (BCS) of an input mesh surface and a rotational symmetry field defined on it. In our framework, the user can visualize not only the BCSs but also their construction process. In addition, our system allows the user to design the geometric realization of the BCS using mesh deformation techniques as well as connecting tubes. This enables the user to verify important facts about BCSs such as that they are manifold surfaces around singularities, as well as the Riemann-Hurwitz formula which relates the Euler characteristic of the BCS to that of the original mesh. Our system is evaluated by student researchers in scientific visualization and geometry processing as well as faculty members in mathematics at our university who teach topology. We include their evaluations and feedback in the paper.

This paper introduces a force-directed layout method for creating origin-destination flow maps. Design principles derived from manual cartography and automated graph drawing to increase readability of flow maps and graph layouts are taken into account. The origin-destination flow maps produced with our algorithm show flows with quadratic Bézier curves that reduce flow-on-flow and flow-on-node overlaps, and avoid sharp or irregular bends in flow lines. A survey of expert cartographers found that flow maps created with our automated method are similar in quality to manually produced flow maps.

Autonomous reconstruction of unknown scenes by a mobile robot inherently poses the question of balancing between exploration efficacy and reconstruction quality. We present a navigation-by-reconstruction approach to address this question, where moving paths of the robot are planned to account for both global efficiency for fast exploration and local smoothness to obtain high-quality scans. An RGB-D camera, attached to the robot arm, is dictated by the desired reconstruction quality as well as the movement of the robot itself. Our key idea is to harness a time-varying tensor field to guide robot movement, and then solve for 3D camera control under the constraint of the 2D robot moving path. The tensor field is updated in real time, conforming to the progressively reconstructed scene. We show that tensor fields are well suited for guiding autonomous scanning for two reasons: first, they contain sparse and controllable singularities that allow generating a locally smooth robot path, and second, their topological structure can be used for globally efficient path routing within a partially reconstructed scene. We have conducted numerous tests with a mobile robot, and demonstrate that our method leads to a smooth exploration and high-quality reconstruction of unknown indoor scenes.

3D tensor field design is important in several graphics applications such as procedural noise, solid texturing, and geometry synthesis. Different fields can lead to different visual effects. The topology of a tensor field, such as degenerate tensors, can cause artifacts in these applications. Existing 2D tensor field design systems cannot be used to handle the topology of a 3D tensor field. In this paper, we present to our knowledge the first 3D tensor field design system. At the core of our system is the ability to edit the topology of tensor fields. We demonstrate the power of our design system with applications in solid texturing and geometry synthesis.

Introducing motion into existing static paintings is becoming a field that is gaining momentum. This effort facilitates keeping artworks current and translating them to different forms for diverse audiences. Chinese ink paintings and Japanese Sumies are well recognized in Western cultures, yet not easily practiced due to the years of training required. We are motivated to develop an interactive system for artists, non-artists, Asians, and non-Asians to enjoy the unique style of Chinese paintings. In this paper, our focus is on replacing static water flow scenes with animations. We include flow patterns, surface ripples, and water wakes which are challenging not only artistically but also algorithmically. We develop a data-driven system that procedurally computes a flow field based on stroke properties extracted from the painting, and animate water flows artistically and stylishly. Technically, our system first extracts water-flow-portraying strokes using their locations, oscillation frequencies, brush patterns, and ink densities. We construct an initial flow pattern by analyzing stroke structures, ink dispersion densities, and placement densities. We cluster extracted strokes as stroke pattern groups to further convey the spirit of the original painting. Then, the system automatically computes a flow field according to the initial flow patterns, water boundaries, and flow obstacles. Finally, our system dynamically generates and animates extracted stroke pattern groups with the constructed field for controllable smoothness and temporal coherence. The users can interactively place the extracted stroke patterns through our adapted Poisson-based composition onto other paintings for water flow animation. In conclusion, our system can visually transform a static Chinese painting to an interactive walk-through with seamless and vivid stroke-based flow animations in its original dynamic spirits without flickering artifacts.

Three-dimensional symmetric tensor fields have a wide range of applications in solid and fluid mechanics. Recent advances in the (topological) analysis of 3D symmetric tensor fields focus on degenerate tensors which form curves. In this paper, we introduce a number of feature surfaces, such as neutral surfaces and traceless surfaces, into tensor field analysis, based on the notion of eigenvalue manifold. Neutral surfaces are the boundary between linear tensors and planar tensors, and the traceless surfaces are the boundary between tensors of positive traces and those of negative traces. Degenerate curves, neutral surfaces, and traceless surfaces together form a partition of the eigenvalue manifold, which provides a more complete tensor field analysis than degenerate curves alone. We also extract and visualize the isosurfaces of tensor modes, tensor isotropy, and tensor magnitude, which we have found useful for domain applications in fluid and solid mechanics. Extracting neutral and traceless surfaces using the Marching Tetrahedra method can cause the loss of geometric and topological details, which can lead to false physical interpretation. To robustly extract neutral surfaces and traceless surfaces, we develop a polynomial description of them which enables us to borrow techniques from algebraic surface extraction, a topic well-researched by the computer-aided design (CAD) community as well as the algebraic geometry community. In addition, we adapt the surface extraction technique, called A-patches, to improve the speed of finding degenerate curves. Finally, we apply our analysis to data from solid and fluid mechanics as well as scalar field analysis.

This paper proposes a vector field visualization, which mimics a sketch-like representation. The visualization combines two major perspectives: Large scale trends based on a strongly simplified field as background visualization and a local visualization highlighting strongly expressed features at their exact position. Each component considers the vector field itself and its spatial derivatives. The derivate is an asymmetric tensor field, which allows the deduction of scalar quantities reflecting distinctive field properties like strength of rotation or shear. The basis of the background visualization is a vector and scalar clustering approach. The local features are defined as the extrema of the respective scalar fields. Applying scalar field topology provides a profound mathematical basis for the feature extraction. All design decisions are guided by the goal of generating a simple to read visualization. To demonstrate the effectiveness of our approach, we show results for three different data sets with different complexity and characteristics.

Illusory motions refer to the phenomena in which static images composed of certain colors and patterns lead to the illusion of motions. This paper presents a first approach to generating illusory motions on 3D surfaces which can be used for shape illustration as well as artistic visualization of line fields on surfaces. Our method extends previous work on generating illusory motions in the plane, which we adapt to 3D surfaces. In addition, we propose novel Repeated Asymmetric Patterns (RAPs) to visualize bidirectional flows, thus enabling the visualization of line fields in the plane and on surfaces. We demonstrate the effectiveness of our method with applications in shape illustration as well as line field visualization on surfaces.

This paper introduces a simple yet effective shape analysis mechanism for geometry processing. Unlike traditional shape analysis techniques which compute descriptors per surface point up to certain neighborhoods, we introduce a shape analysis framework in which the descriptors are based on pairs of surface points. Such a pairwise analysis approach leads to a new class of shape descriptors that are more global, discriminative, and can effectively capture the variations in the underlying geometry. Specifically, we introduce new shape descriptors based on the isocurves of harmonic functions whose global maximum and minimum occur at the point pair. We show that these shape descriptors can infer shape structures and consistently lead to simpler and more efficient algorithms than the state-of-the-art methods for three applications: intrinsic reflectional symmetry axis computation, matching shape extremities, and simultaneous surface segmentation and skeletonization.

Abstract The ability to capture and visualize information within the flow poses challenges for visualizing 3D flow fields. Stream surfaces are one of many useful integration based techniques for visualizing 3D flow. However seeding integral surfaces can be challenging. Previous research generally focuses on manual placement of stream surfaces. Little attention has been given to the problem of automatic stream surface seeding. This paper introduces a novel automatic stream surface seeding strategy based on vector field clustering. It is important that the user can define and target particular characteristics of the flow. Our framework provides this ability. The user is able to specify different vector clustering parameters enabling a range of abstraction for the density and placement of seeding curves and their associated stream surfaces. We demonstrate the effectiveness of this automatic stream surface approach on a range of flow simulations and incorporate illustrative visualization techniques. Domain expert evaluation of the results provides valuable insight into the users requirements and effectiveness of our approach.

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.

Design of time-varying vector fields, i.e., vector fields that can change over time, has a wide variety of important applications in computer graphics. Existing vector field design techniques do not address time-varying vector fields. In this paper, we present a framework for the design of time-varying vector fields, both for planar domains as well as manifold surfaces. Our system supports the creation and modification of various time-varying vector fields with desired spatial and temporal characteristics through several design metaphors, including streamlines, pathlines, singularity paths, and bifurcations. These design metaphors are integrated into an element-based design to generate the time-varying vector fields via a sequence of basis field summations or spatial constrained optimizations at the sampled times. The key-frame design and field deformation are also introduced to support other user design scenarios. Accordingly, a spatial-temporal constrained optimization and the time-varying transformation are employed to generate the desired fields for these two design scenarios, respectively. We apply the time-varying vector fields generated using our design system to a number of important computer graphics applications that require controllable dynamic effects, such as evolving surface appearance, dynamic scene design, steerable crowd movement, and painterly animation. Many of these are difficult or impossible to achieve via prior simulation-based methods. In these applications, the time-varying vector fields have been applied as either orientation fields or advection fields to control the instantaneous appearance or evolving trajectories of the dynamic effects.

We introduce hexagonal global parameterization, a new type of surface parameterization in which parameter lines respect sixfold rotational symmetries (6-RoSy). Such parameterizations enable the tiling of surfaces with nearly regular hexagonal or triangular patterns, and can be used for triangular remeshing. Our framework to construct a hexagonal parameterization, referred to as HEXCOVER, extends the QUADCOVER algorithm and formulates necessary conditions for hexagonal parameterization. We also provide an algorithm to automatically generate a 6-RoSy field that respects directional and singularity features in the surface. We demonstrate the usefulness of our geometry-aware global parameterization with applications such as surface tiling with nearly regular textures and geometry patterns, as well as triangular and hexagonal remeshing.

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 While hexahedral mesh elements are preferred by a variety of simulation techniques, constructing quality all‐hex meshes of general shapes remains a challenge. An attractive hex‐meshing approach, often referred to as sub‐mapping, uses a low distortion mapping between the input model and a PolyCube (a solid formed from a union of cubes), to transfer a regular hex grid from the PolyCube to the input model. Unfortunately, the construction of suitable PolyCubes and corresponding volumetric maps for arbitrary shapes remains an open problem. Our work introduces a new method for computing low‐distortion volumetric PolyCube deformations of general shapes and for subsequent all‐hex remeshing. For a given input model, our method simultaneously generates an appropriate PolyCube structure and mapping between the input model and the PolyCube. From these we automatically generate good quality all‐hex meshes of complex natural and man‐made shapes.

We propose new connectivity editing operations for quadrilateral meshes with the unique ability to explicitly control the location, orientation, type, and number of the irregular vertices (valence not equal to four) in the mesh while preserving sharp edges. We provide theoretical analysis on what editing operations are possible and impossible and introduce threefundamentaloperations to move and re-orient a pair of irregular vertices. We argue that our editing operations are fundamental, because they only change the quad mesh in the smallest possible region and involve the fewest irregular vertices (i.e., two). The irregular vertex movement operations are supplemented by operations for the splitting, merging, canceling, and aligning of irregular vertices. We explain how the proposed high-level operations are realized through graph-level editing operations such as quad collapses, edge flips, and edge splits. The utility of these mesh editing operations are demonstrated by improving the connectivity of quad meshes generated from state-of-art quadrangulation techniques.

Artists use different means of stylization to control the focus on different objects in the scene. This allows them to portray complex meaning and achieve certain artistic effects. Most prior work on painterly rendering of videos, however, uses only a single painting style, with fixed global parameters, irrespective of objects and their layout in the images. This often leads to inadequate artistic control. Moreover, brush stroke orientation is typically assumed to follow an everywhere continuous directional field. In this paper, we propose a video painting system that accounts for the spatial support of objects in the images or videos, and uses this information to specify style parameters and stroke orientation for painterly rendering. Since objects occupy distinct image locations and move relatively smoothly from one video frame to another, our object-based painterly rendering approach is characterized by style parameters that coherently vary in space and time. Space-time-varying style parameters enable more artistic freedom, such as emphasis/de-emphasis, increase or decrease of contrast, exaggeration or abstraction of different objects in the scene in a temporally coherent fashion.

We show how to model geometric patterns on surfaces. We build on the concept of shape grammars to allow the grammars to be guided by a vector or tensor field. Our approach affords greater artistic freedom in design and enables the use of grammars to create patterns on manifold surfaces. We show several application examples in visualization, anisotropic tiling of mosaics, and geometry synthesis on surfaces. In contrast to previous work, we can create patterns that adapt to the underlying surface rather than distorting the geometry with a texture parameterization. Additionally, we are the first to model patterns with a global structure thanks to the ability to derive field-guided shape grammars on surfaces.

Rotational symmetries (RoSys) have found uses in several computer graphics applications, such as global surface parameterization, geometry remeshing, texture and geometry synthesis, and nonphotorealistic visualization of surfaces. The visualization of N-way rotational symmetry (N-RoSy) fields is a challenging problem due to the ambiguities in the N directions represented by an N-way symmetry. We provide an algorithm that allows faithful and interactive representation of N-RoSy fields in the plane and on surfaces, by adapting the well-known line integral convolution (LIC) technique from vector and second-order tensor fields. Our algorithm captures N directions associated with each point in a given field by decomposing the field into multiple different vector fields, generating LIC images of these fields, and then blending the results. To address the loss of contrast caused by the blending of images, we observe that the pixel values in LIC images closely approximate normally distributed random variables. This allows us to use concepts from probability theory to correct the loss of contrast without the need to perform any image analysis at each frame.

Asymmetric tensor field visualization can provide important insight into fluid flows and solid deformations. Existing techniques for asymmetric tensor fields focus on the analysis, and simply use evenly-spaced hyperstreamlines on surfaces following eigenvectors and dual-eigenvectors in the tensor field. In this paper, we describe a hybrid visualization technique in which hyperstreamlines and elliptical glyphs are used in real and complex domains, respectively. This enables a more faithful representation of flow behaviors inside complex domains. In addition, we encode tensor magnitude, an important quantity in tensor field analysis, using the density of hyperstreamlines and sizes of glyphs. This allows colors to be used to encode other important tensor quantities. To facilitate quick visual exploration of the data from different viewpoints and at different resolutions, we employ an efficient image-space approach in which hyperstreamlines and glyphs are generated quickly in the image plane. The combination of these techniques leads to an efficient tensor field visualization system for domain scientists. We demonstrate the effectiveness of our visualization technique through applications to complex simulated engine fluid flow and earthquake deformation data. Feedback from domain expert scientists, who are also co-authors, is provided.

This sketch introduces hexagonal global parameterization, a new type of periodic global parameterization that is ideal for tiling surfaces with patterns of six-fold rotational symmetries, i.e., 6-RoSy's [Palacios and Zhang 2007]. Being one of the two most fundamental rotational symmetries that are compatible with translational symmetries in the plane, 6-RoSy's appear in many places in nature, such as honeycombs, insect eyes, corals and crystals, as well as man-made objects such as Islamic patterns [Kaplan and Salesin 2004] and tri-axial weaving [Akleman et al. 2009]. Such symmetries can also provide optimal circle packing, which naturally have applications in architectural design [Schiftner et al. 2009]. A hexagonal global parameterization facilitates all of these applications. See Figure 1 for some examples. Furthermore, parameter lines in a hexagonal global parameterization intersect at an angle of π/3, which enables triangular remeshing of a mesh surface with close to ideal aspect ratios in the triangles. The dual mesh of such a triangulation provides a hexagon-dominant tiling of the surface.

We describe an interactive editing framework that provides control over the type, location, and number of irregular vertices in a triangle mesh. We first provide a theoretical analysis to identify the simplest possible operations for editing irregular vertices and then introduce a hierarchy of editing operations to control the type, location, and number of irregular vertices. We demonstrate the power of our editing framework with an example application in pattern design on surfaces.

Designing rotational symmetry fields on surfaces is an important task for a wide range of graphics applications. This work introduces a rigorous and practical approach for automatic N-RoSy field design on arbitrary surfaces with user-defined field topologies. The user has full control of the number, positions, and indexes of the singularities (as long as they are compatible with necessary global constraints), the turning numbers of the loops, and is able to edit the field interactively. We formulate N-RoSy field construction as designing a Riemannian metric such that the holonomy along any loop is compatible with the local symmetry of N-RoSy fields. We prove the compatibility condition using discrete parallel transport. The complexity of N-RoSy field design is caused by curvatures. In our work, we propose to simplify the Riemannian metric to make it flat almost everywhere. This approach greatly simplifies the process and improves the flexibility such that it can design N-RoSy fields with single singularity and mixed-RoSy fields. This approach can also be generalized to construct regular remeshing on surfaces. To demonstrate the effectiveness of our approach, we apply our design system to pen-and-ink sketching and geometry remeshing. Furthermore, based on our remeshing results with high global symmetry, we generate Celtic knots on surfaces directly.

Understanding the diversity of a set of multivariate objects is an important problem in many domains, including ecology, college admissions, investing, machine learning, and others. However, to date, very little work has been done to help users achieve this kind of understanding. Visual representation is especially appealing for this task because it offers the potential to allow users to efficiently observe the objects of interest in a direct and holistic way. Thus, in this paper, we attempt to formalize the problem of visualizing the diversity of a large (more than 1000 objects), multivariate (more than 5 attributes) data set as one worth deeper investigation by the information visualization community. In doing so, we contribute a precise definition of diversity, a set of requirements for diversity visualizations based on this definition, and a formal user study design intended to evaluate the capacity of a visual representation for communicating diversity information. Our primary contribution, however, is a visual representation, called the Diversity Map, for visualizing diversity. An evaluation of the Diversity Map using our study design shows that users can judge elements of diversity consistently and as or more accurately than when using the only other representation specifically designed to visualize diversity.

Despite the clear benefits that stream and path surfaces bring when visualizing 3D vector fields, their use in both industry and for research has not proliferated. This is due, in part, to the complexity of previous construction algorithms. We introduce a novel algorithm for the construction of stream and path surfaces that is fast, simple and does not rely on any complicated data structures or surface parameterization, thus making it suitable for inclusion into any visualization application. We demonstrate the technique on a series of simulation data sets and show that a number of benefits stem naturally from this approach including: easy timelines and timeribbons, easy stream arrows and easy evenly-spaced flow lines. We also introduce a novel interaction tool called a surface painter in order to address the perceptual challenges associated with visualizing 3D flow. The key to our integral surface generation algorithm's simplicity is performing local computations on quad primitives.

We address the problem of tracking points in dense vector fields. Such vector fields may come from computational fluid dynamics simulations, environmental monitoring sensors, or dense point tracking of video data. To track points in vector fields, we capture the distribution of higher-order properties (e.g., properties derived from the gradient of the velocity vector field) in a novel local descriptor called a vector spin-image. Our distribution-based approach has a number of advantages over methods that use topology analysis to track points in vector fields. The local distributions are robust to noise, adaptable to changes in the feature, and can be used to extrapolate the location of features after they have disappeared. We describe the vector spin-image data structure, the higher-order properties we record to track vector field points, and show results of tracking points in the simulated flow through a diesel engine cylinder.

Abstract We introduce a novel, automatic streamline seeding algorithm for vector fields defined on surfaces in 3D space. The algorithm generates evenly spaced streamlines fast, simply and efficiently for any general surface‐based vector field. It is general because it handles large, complex, unstructured, adaptive resolution grids with holes and discontinuities, does not require a parametrization, and can generate both sparse and dense representations of the flow. It is efficient because streamlines are only integrated for visible portions of the surface. It is simple because the image‐based approach removes the need to perform streamline tracing on a triangular mesh, a process which is complicated at best. And it is fast because it makes effective, balanced use of both the CPU and the GPU. The key to the algorithm's speed, simplicity and efficiency is its image‐based seeding strategy. We demonstrate our algorithm on complex, real‐world simulation data sets from computational fluid dynamics and compare it with object‐space streamline visualizations.

The gradient of a velocity vector field is an asymmetric tensor field which can provide critical insight that is difficult to infer from traditional trajectory-based vector field visualization techniques. We describe the structures in the eigenvalue and eigenvector fields of the gradient tensor and how these structures can be used to infer the behaviors of the velocity field. To illustrate the structures in asymmetric tensor fields, we introduce the notions of eigenvalue and eigenvector manifolds. These concepts afford a number of theoretical results that clarify the connections between symmetric and antisymmetric components in tensor fields. In addition, these manifolds naturally lead to partitions of tensor fields, which we use to design effective visualization strategies. Both eigenvalue manifold and eigenvector manifold are supported by a tensor reparameterization with physical meaning. This allows us to relate our tensor analysis to physical quantities such as rotation, angular deformation, and dilation, which provide physical interpretation of our tensor-driven vector field analysis in the context of fluid mechanics. To demonstrate the utility of our approach, we have applied our visualization techniques and interpretation to the study of the Sullivan Vortex as well as computational fluid dynamics simulation data.

This paper addresses the problem of interactively modeling large street networks. We introduce an intuitive and flexible modeling framework in which a user can create a street network from scratch or modify an existing street network. This is achieved through designing an underlying tensor field and editing the graph representing the street network. The framework is intuitive because it uses tensor fields to guide the generation of a street network. The framework is flexible because it allows the user to combine various global and local modeling operations such as brush strokes, smoothing, constraints, noise and rotation fields. Our results will show street networks and three-dimensional urban geometry of high visual quality.

Existing topology-based vector field analysis techniques rely on the ability to extract the individual trajectories such as fixed points, periodic orbits, and separatrices that are sensitive to noise and errors introduced by simulation and interpolation. This can make such vector field analysis unsuitable for rigorous interpretations. We advocate the use of Morse decompositions, which are robust with respect to perturbations, to encode the topological structures of a vector field in the form of a directed graph, called a Morse connection graph (MCG). While an MCG exists for every vector field, it need not be unique. Previous techniques for computing MCG's, while fast, are overly conservative and usually results in MCG's that are too coarse to be useful for the applications. To address this issue, we present a new technique for performing Morse decomposition based on the concept of tau-maps, which typically provides finer MCG's than existing techniques. Furthermore, the choice of tau provides a natural tradeoff between the fineness of the MCG's and the computational costs. We provide efficient implementations of Morse decomposition based on tau-maps, which include the use of forward and backward mapping techniques and an adaptive approach in constructing better approximations of the images of the triangles in the meshes used for simulation.. Furthermore, we propose the use of spatial tau-maps in addition to the original temporal tau-maps. These techniques provide additional trade-offs between the quality of the MCGs and the speed of computation. We demonstrate the utility of our technique with various examples in the plane and on surfaces including engine simulation data sets.

In this paper we present an algorithm that operates on a triangular mesh and classifies each face of a triangle as either inside or outside. We present three example applications of this core algorithm: normal orientation, inside removal, and layer-based visualization. The distinguishing feature of our algorithm is its robustness even if a difficult input model that includes holes, coplanar triangles, intersecting triangles, and lost connectivity is given. Our algorithm works with the original triangles of the input model and uses sampling to construct a visibility graph that is then segmented using graph cut.

Designing rotational symmetries on surfaces is a necessary task for a wide variety of graphics applications, such as surface parameterization and remeshing, painterly rendering and pen-and-ink sketching, and texture synthesis. In these applications, thetopologyof a rotational symmetry field such assingularitiesandseparatricescan have a direct impact on the quality of the results. In this paper, we present a design system that provides control over the topology of rotational symmetry fields on surfaces. As the foundation of our system, we provide comprehensive analysis for rotational symmetry fields on surfaces and present efficient algorithms to identify singularities and separatrices. We also describe design operations that allow a rotational symmetry field to be created and modified in an intuitive fashion by using the idea of basis fields and relaxation. In particular, we provide control over the topology of a rotational symmetry field by allowing the user to remove singularities from the field or to move them to more desirable locations. At the core of our analysis and design implementations is the observations thatN-way rotational symmetries can be described by symmetricN-th order tensors, which allows an efficient vector-based representation that not only supports coherent definitions of arithmetic operations on rotational symmetries but also enables many analysis and design operations for vector fields to be adapted to rotational symmetry fields. To demonstrate the effectiveness of our approach, we apply our design system to pen-and-ink sketching and geometry remeshing.

Design and control of vector fields is critical for many visualization and graphics tasks such as vector field visualization, fluid simulation, and texture synthesis. The fundamental qualitative structures associated with vector fields are fixed points, periodic orbits, and separatrices. In this paper, we provide a new technique that allows for the systematic creation and cancellation of fixed points and periodic orbits. This technique enables vector field design and editing on the plane and surfaces with desired qualitative properties. The technique is based on Conley theory, which provides a unified framework that supports the cancellation of fixed points and periodic orbits. We also introduce a novel periodic orbit extraction and visualization algorithm that detects, for the first time, periodic orbits on surfaces. Furthermore, we describe the application of our periodic orbit detection and vector field simplification algorithms to engine simulation data demonstrating the utility of the approach. We apply our design system to vector field visualization by creating data sets containing periodic orbits. This helps us understand the effectiveness of existing visualization techniques. Finally, we propose a new streamline-based technique that allows vector field topology to be easily identified.

Designing tensor fields in the plane and on surfaces is a necessary task in many graphics applications, such as painterly rendering, pen-and-ink sketching of smooth surfaces, and anisotropic remeshing. In this article, we present an interactive design system that allows a user to create a wide variety of symmetric tensor fields over 3D surfaces either from scratch or by modifying a meaningful input tensor field such as the curvature tensor. Our system converts each user specification into a basis tensor field and combines them with the input field to make an initial tensor field. However, such a field often contains unwanted degenerate points which cannot always be eliminated due to topological constraints of the underlying surface. To reduce the artifacts caused by these degenerate points, our system allows the user to move a degenerate point or to cancel a pair of degenerate points that have opposite tensor indices. These operations provide control over the number and location of the degenerate points in the field. We observe that a tensor field can be locally converted into a vector field so that there is a one-to-one correspondence between the set of degenerate points in the tensor field and the set of singularities in the vector field. This conversion allows us to effectively perform degenerate point pair cancellation and movement by using similar operations for vector fields. In addition, we adapt the image-based flow visualization technique to tensor fields, therefore allowing interactive display of tensor fields on surfaces. We demonstrate the capabilities of our tensor field design system with painterly rendering, pen-and-ink sketching of surfaces, and anisotropic remeshing.

Vector field design on surfaces is necessary for many graphics applications: example-based texture synthesis, nonphotorealistic rendering, and fluid simulation. For these applications, singularities contained in the input vector field often cause visual artifacts. In this article, we present a vector field design system that allows the user to create a wide variety of vector fields with control over vector field topology, such as the number and location of singularities. Our system combines basis vector fields to make an initial vector field that meets user specifications.The initial vector field often contains unwanted singularities. Such singularities cannot always be eliminated due to the Poincaré-Hopf index theorem. To reduce the visual artifacts caused by these singularities, our system allows the user to move a singularity to a more favorable location or to cancel a pair of singularities. These operations offer topological guarantees for the vector field in that they only affect user-specified singularities. We develop efficient implementations of these operations based on Conley index theory . Our system also provides other editing operations so that the user may change the topological and geometric characteristics of the vector field.To create continuous vector fields on curved surfaces represented as meshes, we make use of the ideas of geodesic polar maps and parallel transport to interpolate vector values defined at the vertices of the mesh. We also use geodesic polar maps and parallel transport to create basis vector fields on surfaces that meet the user specifications. These techniques enable our vector field design system to work for both planar domains and curved surfaces.We demonstrate our vector field design system for several applications: example-based texture synthesis, painterly rendering of images, and pencil sketch illustrations of smooth surfaces.

Surface parameterization is necessary for many graphics tasks: texture-preserving simplification, remeshing, surface painting, and precomputation of solid textures. The stretch caused by a given parameterization determines the sampling rate on the surface. In this article, we present an automatic parameterization method for segmenting a surface into patches that are then flattened with little stretch. Many objects consist of regions of relatively simple shapes, each of which has a natural parameterization. Based on this observation, we describe a three-stage feature-based patch creation method for manifold surfaces. The first two stages, genus reduction and feature identification, are performed with the help of distance-based surface functions. In the last stage, we create one or two patches for each feature region based on a covariance matrix of the feature's surface points. To reduce stretch during patch unfolding, we notice that stretch is a 2 × 2 tensor, which in ideal situations is the identity. Therefore, we use the Green-Lagrange tensor to measure and to guide the optimization process. Furthermore, we allow the boundary vertices of a patch to be optimized by adding scaffold triangles. We demonstrate our feature-based patch creation and patch unfolding methods for several textured models. Finally, to evaluate the quality of a given parameterization, we describe an image-based error measure that takes into account stretch, seams, smoothness, packing efficiency, and surface visibility.

For some graphics applications, object interiors and hard-to-see regions contribute little to the final images and need not be processed. In this paper, we define a view-independent visibility measure on mesh surfaces based on the visibility function between the surfaces and a surrounding sphere of cameras. We demonstrate the usefulness of this measure with a visibility-guided simplification algorithm. Mesh simplification reduces the polygon counts of 3D models and speeds up the rendering process. Many mesh simplification algorithms are based on sequences of edge collapses that minimize geometric and attribute errors. By combining the surface visibility measure with a geometric error measure, we obtain simplified models with improvement proportional to the number of low visibility regions in the original models.