Progressive Simplification of Tetrahedral Meshes Preserving All Isosurface Topologies

In this paper, we propose a novel technique for constructing multiple levels of a tetrahedral volume dataset whilepreserving the topologies of all isosurfaces embedded in the data. Our simplification technique has two majorphases. In the segmentation phase, we segment the volume data into topological‐equivalence regions, that is, thesub‐volumes within each of which all isosurfaces have the same topology. In the simplification phase, we simplifyeach topological‐equivalence region independently, one by one, by collapsing edges from the smallest to the largesterrors (within the user‐specified error tolerance, for a given error metrics), and ensure that we do not collapseedges that may cause an isosurface‐topology change. We also avoid creating a tetrahedral cell of negative volume(i.e., avoid the fold‐over problem). In this way, we guarantee to preserve all isosurface topologies in the entiresimplification process, with a controlled geometric error bound. Our method also involves several additionalnovel ideas, including using the Morse theory and the implicit fully augmented contour tree, identifying typesof edges that are not allowed to be collapsed, and developing efficient techniques to avoid many unnecessary orexpensive checkings, all in an integrated manner. The experiments show that all the resulting isosurfaces preservethe topologies, and have good accuracies in their geometric shapes. Moreover, we obtain nice data‐reductionrates, with competitively fast running times.     

Asynchronous Consensus in Continuous-Time Multi-Agent Systems With Switching Topology and Time-Varying Delays

The paper studies asynchronous consensus problems of continuous-time multi-agent systems with discontinuous information transmission. The proposed consensus control strategy is implemented based on the state information of each agent's neighbors at some discrete times. The asynchrony means that each agent's update times, at which the agent adjusts its dynamics, are independent of others'. Furthermore, it is assumed that the communication topology among agents is time-dependent and the information transmission is with bounded time-varying delays. If the union of the communication topology across any time interval with some given length contains a spanning tree, the consensus problem is shown to be solvable. The analysis tool developed in this paper is based on nonnegative matrix theory and graph theory. The main contribution of this paper is to provide a valid distributed consensus algorithm that overcomes the difficulties caused by unreliable communication channels, such as intermittent information transmission, switching communication topology, and time-varying communication delays, and therefore has its obvious practical applications. Simulation examples are provided to demonstrate the effectiveness of the theoretical results.     

Topology correction of segmented medical images using a fast marching algorithm

We present here a new method for correcting the topology of objects segmented from medical images. Whereas previous techniques alter a surface obtained from a binary segmentation of the object, our technique can be applied directly to the image intensities of a probabilistic or fuzzy segmentation, thereby propagating the topology for all isosurfaces of the object. From an analysis of topological changes and critical points in implicit surfaces, we derive a topology propagation algorithm that enforces any desired topology using a fast marching technique. The method has been applied successfully to the correction of the cortical gray matter/white matter interface in segmented brain images and is publicly released as a software plug-in for the MIPAV package.     

SmallWorlds: Visualizing Social Recommendations

We present SmallWorlds, a visual interactive graph‐based interface that allows users to specify, refine and build item‐preference profiles in a variety of domains. The interface facilitates expressions of taste through simple graph interactions and these preferences are used to compute personalized, fully transparent item recommendations for a target user. Predictions are based on a collaborative analysis of preference data from a user's direct peer group on a social network. We find that in addition to receiving transparent and accurate item recommendations, users also learn a wealth of information about the preferences of their peers through interaction with our visualization. Such information is not easily discoverable in traditional text based interfaces. A detailed analysis of our design choices for visual layout, interaction and prediction techniques is presented. Our evaluations discuss results from a user study in which SmallWorlds was deployed as an interactive recommender system on Facebook.     

Structural approach to design user interface

The analysis of the interactive relations among interface elements using a structuralized method can help user interface designers to satisfy the different requirements of design and improve design efficiency. This study develops a three-stage structured user interface design approach for complex information systems consisting of multiple components. First, the Quality Function Development (QFD) approach is used to confirm the user's design demand and its mapping components. Next, the Interpretive Structural Model (ISM) technique is adopted to construct a clear model of a hierarchical structure. Finally, the Impact Matrix Cross-Reference Multiplication Applied to a Classification (MICMAC) approach is employed to analyze the effect and dependence among the overall design components, and to consider the relationship network graph of distribution of components in the system. The research approach applies the Web mail system as its case study. Through the empirical study of web-based system, interface designers can effectively grasp a user's differentiated demand that changes rapidly and reflect it in the combination of designed components. This study establishes a strategy for creating an information system design pattern with multiple components is by building a hierarchical structure and analyzing the component distribution.     

Topological Zone Organization of Scalar Volume Data

We present a new method for preprocessing and organizing discrete scalar volume data of any dimension on external storage. We describe our implementation of a visual navigation system using our method. The techniques have important applications for out-of-core visualization of volume data sets and image understanding. The applications include extracting isosurfaces in a manner that helps reduce both I/O and disk seek time, a priori topologically correct isosurface simplification (prior to extraction), and producing a visual atlas of all topologically distinct objects in the data set. The preprocessing algorithm computes regions of space that we call topological zone components, so that any isosurface component (contour) is completely contained in a zone component and all contours contained in a zone component are topologically equivalent. The algorithm also constructs a criticality tree that is related to the recently studied contour tree. However, unlike the contour tree, the zones and the criticality tree hierarchically organize the data set. We demonstrate that the techniques work on both irregularly and regularly gridded data, and can be extended to data sets with nonunique values, by the mathematical analysis we call Digital Morse Theory (DMT), so that perturbation of the data set is not required. We present the results of our initial experiments with three dimensional volume data (CT) and describe future extensions of our DMT organizing technology.     

Topology-controlled volume rendering

Topology provides a foundation for the development of mathematically sound tools for processing and exploration of scalar fields. Existing topology-based methods can be used to identify interesting features in volumetric data sets, to find seed sets for accelerated isosurface extraction, or to treat individual connected components as distinct entities for isosurfacing or interval volume rendering. We describe a framework for direct volume rendering based on segmenting a volume into regions of equivalent contour topology and applying separate transfer functions to each region. Each region corresponds to a branch of a hierarchical contour tree decomposition, and a separate transfer function can be defined for it. The novel contributions of our work are: 1) a volume rendering framework and interface where a unique transfer function can be assigned to each subvolume corresponding to a branch of the contour tree, 2) a runtime method for adjusting data values to reflect contour tree simplifications, 3) an efficient way of mapping a spatial location into the contour tree to determine the applicable transfer function, and 4) an algorithm for hardware-accelerated direct volume rendering that visualizes the contour tree-based segmentation at interactive frame rates using graphics processing units (GPUs) that support loops and conditional branches in fragment programs     

Computing Contour Trees for 2D Piecewise Polynomial Functions

Contour trees are extensively used in scalar field analysis. The contour tree is a data structure that tracks the evolution of level set topology in a scalar field. Scalar fields are typically available as samples at vertices of a mesh and are linearly interpolated within each cell of the mesh. A more suitable way of representing scalar fields, especially when a smoother function needs to be modeled, is via higher order interpolants. We propose an algorithm to compute the contour tree for such functions. The algorithm computes a local structure by connecting critical points using a numerically stable monotone path tracing procedure. Such structures are computed for each cell and are stitched together to obtain the contour tree of the function. The algorithm is scalable to higher degree interpolants whereas previous methods were restricted to quadratic or linear interpolants. The algorithm is intrinsically parallelizable and has potential applications to isosurface extraction.     

Parallel Computation of the Topology of Level Sets

This paper introduces two efficient algorithms that compute the Contour Tree of a three-dimensional scalar field F and its augmented version with the Betti numbers of each isosurface. The Contour Tree is a fundamental data structure in scientific visualization that is used to pre-process the domain mesh to allow optimal computation of isosurfaces with minimal overhead storage. The Contour Tree can also be used to build user interfaces reporting the complete topological characterization of a scalar field, as shown in Figure~\ref{fig:top}. Data exploration time is reduced since the user understands the evolution of level set components with changing isovalue. The Augmented Contour Tree provides even more accurate information segmenting the range space of the scalar field into regions of invariant topology. The exploration time for a single isosurface is also improved since its genus is known in advance. Our first new algorithm augments any given Contour Tree with the Betti numbers of all possible corresponding isocontours in linear time with the size of the tree. Moreover, we show how to extend the scheme introduced in [3] with the Betti number computation without increasing its complexity. Thus, we improve on the time complexity in our previous approach from O(m log m) to O(n log n + m), where m is the number of cells and n is the number of vertices in the domain of F. Our second contribution is a new divide-and-conquer algorithm that computes the Augmented Contour Tree with improved efficiency. The approach computes the output Contour Tree by merging two intermediate Contour Trees and is independent of the interpolant. In this way we confine any knowledge regarding a specific interpolant to an independent function that computes the tree for a single cell. We have implemented this function for the trilinear interpolant and plan to replace it with higher-order interpolants when needed. The time complexity is O(n + t log n), where t is the number of critical points of F. For the first time we can compute the Contour Tree in linear time in many practical cases where t = O(n^1–). We report the running times for a parallel implementation, showing good scalability with the number of processors.     

Parallel Computation of the Topology of Level Sets

This paper introduces two efficient algorithms that compute the Contour Tree of a three-dimensional scalar field F and its augmented version with the Betti numbers of each isosurface. The Contour Tree is a fundamental data structure in scientific visualization that is used to pre-process the domain mesh to allow optimal computation of isosurfaces with minimal overhead storage. The Contour Tree can also be used to build user interfaces reporting the complete topological characterization of a scalar field, as shown in Figure~\ref{fig:top}. Data exploration time is reduced since the user understands the evolution of level set components with changing isovalue. The Augmented Contour Tree provides even more accurate information segmenting the range space of the scalar field into regions of invariant topology. The exploration time for a single isosurface is also improved since its genus is known in advance. Our first new algorithm augments any given Contour Tree with the Betti numbers of all possible corresponding isocontours in linear time with the size of the tree. Moreover, we show how to extend the scheme introduced in [3] with the Betti number computation without increasing its complexity. Thus, we improve on the time complexity in our previous approach from O(m log m) to O(n log n + m), where m is the number of cells and n is the number of vertices in the domain of F. Our second contribution is a new divide-and-conquer algorithm that computes the Augmented Contour Tree with improved efficiency. The approach computes the output Contour Tree by merging two intermediate Contour Trees and is independent of the interpolant. In this way we confine any knowledge regarding a specific interpolant to an independent function that computes the tree for a single cell. We have implemented this function for the trilinear interpolant and plan to replace it with higher-order interpolants when needed. The time complexity is O(n + t log n), where t is the number of critical points of F. For the first time we can compute the Contour Tree in linear time in many practical cases where t = O(n ^1–ε). We report the running times for a parallel implementation, showing good scalability with the number of processors.     

链路层网络拓扑发现及其Web表现方法

文中介绍了一种基于SNMP协议和CDP协议的链路层网络拓扑发现方法，这种方法不仅能够发现主干网络的拓扑结构，同时也能够发现接入网络的各种终端设备，所构造的网络拓扑图是一个JavaScript脚本，可以方便地在Web界面中显示、操作和网络节点导航，也可以作为基于Web的综合网管系统的用户接口，挂接其他的管理功能。     

Interactive rendering of dynamic geometry

Fluid simulations typically produce complex three-dimensional (3D) isosurfaces whose geometry and topology change over time. The standard way of representing such "dynamic geometry" is by a set of isosurfaces that are extracted individually at certain time steps. An alternative strategy is to represent the whole sequence as a four-dimensional (4D) tetrahedral mesh. The iso-surface at a specific time step can then be computed by intersecting the tetrahedral mesh with a 3D hyperplane. This not only allows the animation of the surface continuously over time without having to worry about the topological changes, but also enables simplification algorithms to exploit temporal coherence. We show how to interactively render such 4D tetrahedral meshes by improving previous GPU-accelerated techniques and building an out-of-core multi-resolution structure based on quadric error simplification. As a second application, we apply our framework to time-varying surfaces that result from morphing one triangle mesh into another.     

Graph-Based Transfer Function for Volume Rendering

A good transfer function in volume rendering requires careful consideration of the materials present in a volume. A manual creation is tedious and prone to errors. Furthermore, the user interaction to design a higher dimensional transfer function gets complicated. In this work, we present a graph-based approach to design a transfer function that takes volumetric structures into account. Our novel contribution is in proposing an algorithm for robust deduction of a material graph from a set of disconnected edges. We incorporate stable graph creation under varying noise levels in the volume. We show that the deduced material graph can be used to automatically create a transfer function using the occlusion spectrum of the input volume. Since we compute material topology of the objects, an enhanced rendering is possible with our method. This also allows us to selectively render objects and depict adjacent materials in a volume. Our method considerably reduces manual effort required in designing a transfer function and provides an easy interface for interaction with the volume.     

基于采矿CAD的硐室参数绘图系统设计及实现

CAD系统因其本身具有许多长处,得到了工程设计人员的广泛使用。但它只能处理图形的几何信息,真正具有工程实际意义的图形拓扑信息和参数约束信息均被抛弃了。为了保留更多的图形信息以及让工程设计人员更方便地进行硐室图形的绘制,文中根据采矿CAD图形的特点,把要绘制的硐室图形进行参数化分析,并通过编程调用采矿CAD的接口实现了硐室图形的自动绘制系统。此系统能根据用户输入的参数自动生成硐室的二维和三维图形,这大大减少了设计人员的工作量,提高了设计效率,也有利于计算机辅助设计的进一步发展。     

Internal structure of coalitions in competitive and altruistic graphical coalitional games

This paper introduces a certain graphical coalitional game where the internal topology of the coalition depends on a prescribed communication graph structure among the agents. The game Value Function is required to satisfy four Axioms of Value. These axioms make it possible to provide a refined study of coalition structures on graphs by defining a formal graphical game and by assigning a Positional Advantage, based on the Shapley value, to each agent in a coalition based on its connectivity properties within the graph. Using the Axioms of Value the graphical coalitional game can be shown to satisfy properties such as convexity, fairness, cohesiveness, and full cooperativeness. Three measures of the contributions of agents to a coalition are introduced: marginal contribution, competitive contribution, and altruistic contribution. The mathematical framework given here is used to establish results regarding the dependence of these three types of contributions on the graph topology, and changes in these contributions due to changes in graph topology. Based on these different contributions, three online sequential decision games are defined on top of the graphical coalitional game, and the stable graphs under each of these sequential decision games are studied. It is shown that the stable graphs under the objective of maximizing the marginal contribution are any connected graph. The stable graphs under the objective of maximizing the competitive contribution are the complete graph. The stable graphs under the objective of maximizing the altruistic contribution are any tree.     

Distributed fault tolerant computation of weakly connected dominating set in ad hoc networks

Our purpose in this paper is to propose a self-stabilizing protocol for weakly connected dominating set (WCDS) set in a given ad hoc network graph. WCDS is a particular variant of graph domination predicates which play an important role in routing in ad hoc networks. There are many variants of domination problems in bidirectional networks; WCDS is also useful in forming clusters in ad hoc networks. There are many heuristic and distributed algorithms to compute WCDS in network graphs while almost all of them will need complete information about the network topology and most of them are not fault tolerant or mobility tolerant. Self-stabilization is a protocol design paradigm that is especially useful in resource constrained infrastructure-less networks since nodes can make moves based on local knowledge only and yet a global task is accomplished in a fault tolerant manner; it also facilitates for nodes to enter and exit the network freely. There exist self-stabilizing protocols for minimal spanning tree, total domination, and others. We have shown that the paradigm is capable of designing a protocol for WCDS. Our objective is to mathematically prove the correctness and the convergence of the protocol in any worst-case scenario, as is usually done for self-stabilizing protocols for other graph predicates used for ad hoc networks.     

Stereo correspondence through feature grouping and maximal cliques

The authors propose a method for solving the stereo correspondence problem. The method consists of extracting local image structures and matching similar such structures between two images. Linear edge segments are extracted from both the left and right images. Each segment is characterized by its position and orientation in the image as well as its relationships with the nearby segments. A relational graph is thus built from each image. For each segment in one image as set of potential assignments is represented as a set of nodes in a correspondence graph. Arcs in the graph represent compatible assignments established on the basis of segment relationships. Stereo matching becomes equivalent to searching for sets of mutually compatible nodes in this graph. Sets are found by looking for maximal cliques. The maximal clique best suited to represent a stereo correspondence is selected using a benefit function. Numerous results obtained with this method are shown     

Information flow and cooperative control of vehicle formations

We consider the problem of cooperation among a collection of vehicles performing a shared task using intervehicle communication to coordinate their actions. Tools from algebraic graph theory prove useful in modeling the communication network and relating its topology to formation stability. We prove a Nyquist criterion that uses the eigenvalues of the graph Laplacian matrix to determine the effect of the communication topology on formation stability. We also propose a method for decentralized information exchange between vehicles. This approach realizes a dynamical system that supplies each vehicle with a common reference to be used for cooperative motion. We prove a separation principle that decomposes formation stability into two components: Stability of this is achieved information flow for the given graph and stability of an individual vehicle for the given controller. The information flow can thus be rendered highly robust to changes in the graph, enabling tight formation control despite limitations in intervehicle communication capability.     

基于要素分离的用户界面安全性设计

提出了一种分离用户界面要素的方法来提高用户界面设计的有效性和可靠性。分析了用户界面设计中使用该方法的优点和如何对用户界面要素进行分离。重点讨论基于该方法的用户界面安全性设计。     

Output consensus for multiple non-holonomic systems under directed communication topology

In this paper, the problem of output consensus for multiple non-holonomic systems in chained form has been investigated. First, an output consensus controller under the strongly connected communication topology is devised by two steps, where a time-varying control strategy and the backstepping design technique are employed. Then, the results are extended to the general directed topology case via graph decomposition, in which the input-to-state stability theory plays a critical role. We prove that the proposed controller can achieve the semi-global output consensus among multiple non-holonomic systems, provided that the interaction graph contains a spanning tree. Finally, numerical examples are provided to illustrate the effectiveness of the designed controller.