算法演示系统研究与应用

软件可视化可分为程序可视化和算法可视化,算法演示(Algorithm Animation)是算法可视化中的动态方式.除了作为一种教学工具,算法演示也可以作为算法分析与设计的一种辅助手段.当前的算法演示系统一般包括算法实现、动画显示以及映射这三个部分.通过一些典型的算法演示系统介绍算法演示方面的主要技术,根据这些技术指出当前的算法演示系统中普遍存在的问题,即算法实现部分与动画显示部分的分离问题,并提出用面向方面技术予以解决的思想,最后对该领域研究的发展前景进行展望.     

A comprehensive taxonomy of algorithm animation languages

In this paper, we present a taxonomy of algorithm animation languages that augments Price's well-known taxonomy of software visualization. Whereas Price's taxonomy is directed to classifying features and characteristics of visualization systems, the new taxonomy focuses on evaluating current animation languages. The taxonomy can be used by algorithm visualization system designers as a tool to compare visualization system languages with each other as well as for designing and implementing new systems and language features. In addition, the taxonomy provides guidelines to the features that are needed for transferring animations between systems. This is an ongoing project that elaborates upon the work reported on in a briefer version of the taxonomy.     

Algorithm visualization for distributed environments

This paper investigates the visualization of distributed algorithms. We present a conceptual model and a system, VADE, that realizes this model. Since in asynchronous distributed systems there is no way of knowing (let alone, visualizing) the “real” execution, we show how to generate a visualization which is consistent with the execution of the distributed algorithm. We also present the design and implementation of our system. VADE is designed so that the algorithm runs on the server's machines while the visualization is executed on a web page on the client's machine. Programmers can write animations quickly and easily with the assistance of VADE's libraries. End-users can experiment with the animation and change its visual properties.     

A framework to visualize equivalences between computational models of regular languages

We discuss how to increase and simplify the understanding of the equivalence relations between machine models and/or language representations of formal languages by means of the animation tool SAGEMoLiC. Our new educational tool permits the simulation of the execution of models of computation, as many other animation systems do, but its philosophy goes further than these of the usual systems since it allows for a true visualization of the key notions involved in the formal proofs of these equivalences. In contrast with the proposal of previous systems, our approach to visualize equivalence theorems is not a simple “step by step animation” of specific conversion algorithms between computational models and/or grammatical representations of formal languages, because we make emphasis on the key theoretical notions involved in the formal proofs of these equivalences.     

A stable graph layout algorithm for processes

Process mining enables organizations to analyze data about their (business) processes. Visualization is key to gaining insight into these processes and the associated data. Process visualization requires a high‐quality graph layout that intuitively represents the semantics of the process. Process analysis additionally requires interactive filtering to explore the process data and process graph. The ideal process visualization therefore provides a high‐quality, intuitive layout and preserves the mental map of the user during the visual exploration. The current industry standard used for process visualization does not satisfy either of these requirements. In this paper, we propose a novel layout algorithm for processes based on the Sugiyama framework. Our approach consists of novel ranking and order constraint algorithms and a novel crossing minimization algorithm. These algorithms make use of the process data to compute stable, high‐quality layouts. In addition, we use phased animation to further improve mental map preservation. Quantitative and qualitative evaluations show that our approach computes layouts of higher quality and preserves the mental map better than the industry standard. Additionally, our approach is substantially faster, especially for graphs with more than 250 edges.     

Efficient level of detail for texture‐based flow visualization

In this paper, we present an efficient level of detail algorithm for texture‐based flow visualization. Our goal is to enhance visual perception and performance and generate smooth animation. To achieve our goal, we first model an adaptive input texture taking into account flow patterns to output view‐dependent high‐quality images. Then, we compute field lines only from sparse sampling points of the input noise texture for outputting volume line integral convolution textures and skip empty space utilizing two quantized binary histograms. To improve image quality, we implement anti‐aliasing through adjusting the line integral convolution step size and thickness of trajectory lines with an opacity function. We further extend our solution to unsteady flow. Flow structures and evolution are clearly shown through smooth animation achieved with coherent evolution of particles, handling of discontinuous flow lines, and spatio‐temporal linear constraint of the underlying noise volume. In the result section, we show high‐quality level of detail of three‐dimensional texture‐based flow visualization with high performance. We also demonstrate that our algorithm can achieve smooth evolution for unsteady flow with spatio‐temporal coherence. Copyright © 2015 John Wiley & Sons, Ltd.     

Smooth Animation of Algorithms in a Declarative Framework

Thanks to the increasing sophistication of modern workstations and display devices, supporting smoothly changing images has nowadays become a valuable feature in software visualization systems, but it seems difficult to achieve in declarative frameworks, as they are basically data (and not event) driven. This paper focuses on the problem of specifying animations of algorithms in a declarative style, addressing both automation and customization issues. We propose a general functional approach to animation modeling where animated behaviors of graphical objects are ‘higher-order’ attributes of the objects themselves expressed in the form of mathematical functions. These functions provide temporal and spatial information for creating smooth transitions between graphical scenes.The paper also describes the practical embodiment of our mathematical framework in the logic-based software visualization system Leonardo. Differently from previous approaches to smooth algorithm animation, detection of visual events and in-betweening scenes are completely automatic with our technique. Moreover, automation is supported without sacrificing customizability: default animated behaviors of graphical objects are automatically provided by the system, and practical solutions for specifying user-defined animation functions are supported as well. The quality of animations can be therefore incrementally improved by overriding the default behaviors as we show in some examples.     

基于个性化定制的交互式蒙版擦除动画设计与实现

随着虚拟现实技术和移动互联网技术的飞速发展,众多商家希望通过移动端实现 交互式蒙版擦除动画。然而目前在个性化实时定制、交互性等方面存在问题。为此,设计了一 种基于个性化定制的交互式蒙版擦除动画方法,包括个性化定制模块和交互式蒙版擦除动画可 视化模块,其中个性化定制模块实现了定制数据的初始化处理,交互式蒙版擦除动画可视化模 块实现了移动端甩动—可视化终端蒙版擦除—后台数据查询编辑的交互式蒙版擦除动画。搭建 了原型系统并进行了实验测试,测试结果表明,该系统可以实现移动端约 2 000 次甩动的实时 同步擦除动画可视化。     

Collaborative Exploration and Sensemaking of Big Environmental Sound Data

Many ecologists are using acoustic monitoring to study animals and the health of ecosystems. Technological advances mean acoustic recording of nature can now be done at a relatively low cost, with minimal disturbance, and over long periods of time. Vast amounts of data are gathered yielding environmental soundscapes which requires new forms of visualization and interpretation of the data. Recently a novel visualization technique has been designed that represents soundscapes using dense visual summaries of acoustic patterns. However, little is known about how this visualization tool can be employed to make sense of soundscapes. Understanding how the technique can be best used and developed requires collaboration between interface, algorithm designers and ecologists. We empirically investigated the practices and needs of ecologists using acoustic monitoring technologies. In particular, we investigated the use of the soundscape visualization tool by teams of ecologists researching endangered species detection, species behaviour, and monitoring of ecological areas using long duration audio recordings. Our findings highlight the opportunities and challenges that ecologists face in making sense of large acoustic datasets through patterns of acoustic events. We reveal the characteristic processes for collaboratively generating situated accounts of natural places from soundscapes using visualization. We also discuss the biases inherent in the approach. Big data from nature has different characteristics from social and informational data sources that comprise much of the World Wide Web. We conclude with design implications for visual interfaces to facilitate collaborative exploration and discovery through soundscapes.     

Visualizing and animating the winged-edge data structure

The winged- and half-edge data structures are commonly used representations for polyhedron models. Due to the complexity, students in an introductory course to computer graphics usually have difficulty in handling these data structures and developing applications. This paper describes the authors’ effort in the development of a visualization and animation tool for teaching and learning these data structures. This tool also includes a simple pseudo-code-like language for algorithm design. Instructors may employ this tool for presentation and demonstration purposes. Students may use the simple language to develop and experiment with new algorithms before their actual implementation. The visualization and animation system may be used to explore and understand the relationship among mesh elements and algorithm execution.     

单链结构实时识别及可视化布局算法研究

数据结构可视化技术是程序理解与调试的一种重要支撑。为解决其中一类应用广泛的数据结构--单链结构的可视化问题，提出一种实时识别与可视化布局算法。首先根据结点入度、主前驱指针和次前驱点集合等结点属性变化对单链结构特征变化的影响，对程序执行过程中的单链结构进行实时识别；然后结合基于图标的静态可视化技术以及动画技术，建立面向单链结构的可视化动作集合及可视化布局方法，形成与程序执行过程步骤实时对应的单链结构可视化表达。最后将该算法应用于新一代集成开发环境AnyviewC的研发与实践中。     

Character navigation in dynamic environments based on optical flow

Steering and navigation are important components of character animation systems to enable them to autonomously move in their environment. In this work, we propose a synthetic vision model that uses visual features to steer agents through dynamic environments. Our agents perceive optical flow resulting from their relative motion with the objects of the environment. The optical flow is then segmented and processed to extract visual features such as the focus of expansion and time‐to‐collision. Then, we establish the relations between these visual features and the agent motion, and use them to design a set of control functions which allow characters to perform object‐dependent tasks, such as following, avoiding and reaching. Control functions are then combined to let characters perform more complex navigation tasks in dynamic environments, such as reaching a goal while avoiding multiple obstacles. Agent's motion is achieved by local minimization of these functions. We demonstrate the efficiency of our approach through a number of scenarios. Our work sets the basis for building a character animation system which imitates human sensorimotor actions. It opens new perspectives to achieve realistic simulation of human characters taking into account perceptual factors, such as the lighting conditions of the environment.     

基于可视化的C语言运行平台的设计

可视化技术给人机界面的开发带来了巨大的变化,程序语言编写及运行的可视化环境使人机界面的实现可以通过可视动画的交互方式进行。文章针对于C语言,采用VC＋＋工具进行可视化编辑环境的设计,实现C语言可视动画化运行及交互方式化运行的全过程。     

High-level user interfaces for transfer function design with semantics

Many sophisticated techniques for the visualization of volumetric data such as medical data have been published. While existing techniques are mature from a technical point of view, managing the complexity of visual parameters is still difficult for non-expert users. To this end, this paper presents new ideas to facilitate the specification of optical properties for direct volume rendering. We introduce an additional level of abstraction for parametric models of transfer functions. The proposed framework allows visualization experts to design high-level transfer function models which can intuitively be used by non-expert users. The results are user interfaces which provide semantic information for specialized visualization problems. The proposed method is based on principal component analysis as well as on concepts borrowed from computer animation.     

GO: A cluster algorithm for graph visualization

As we are in the big data age, graph data such as user networks in Facebook and Flickr becomes large. How to reduce the visual complexity of a graph layout is a challenging problem. Clustering graphs is regarded as one of effective ways to address this problem. Most of current graph visualization systems, however, directly use existing clustering algorithms that are not originally developed for the visualization purpose. For graph visualization, a clustering algorithm should meet specific requirements such as the sufficient size of clusters, and automatic determination of the number of clusters. After identifying the requirements of clustering graphs for visualization, in this paper we present a new clustering algorithm that is particularly designed for visualization so as to reduce the visual complexity of a layout, together with a strategy for improving the scalability of our algorithm. Experiments have demonstrated that our proposed algorithm is capable of detecting clusters in a way that is required in graph visualization.     

Video-based personalized traffic learning

We present a video-based approach to learn the specific driving characteristics of drivers in the video for advanced traffic control. Each vehicle’s specific driving characteristics are calculated with an offline learning process. Given each vehicle’s initial status and the personalized parameters as input, our approach can vividly reproduce the traffic flow in the sample video with a high accuracy. The learned characteristics can also be applied to any agent-based traffic simulation systems. We then introduce a new traffic animation method that attempts to animate each vehicle with its real driving habits and show its adaptation to the surrounding traffic situation. Our results are compared to existing traffic animation methods to demonstrate the effectiveness of our presented approach.     

A Constraint-Based Approach for Visualization and Animation

TRIP systems are tools for visualization and animation. They are based on a constraint-based model of bi-directional translation between abstract data and pictorial data. Using these systems, programmers can visualize abstract data, and animate various algorithms and processes, simply by providing a declarative mapping rule. This paper presents this model for visualization and animation, focusing on the use of constraints, and also presents the TRIP systems with examples of visualization and animation.     

Interactive visual analysis of time-series microarray data

Estimating dynamic regulatory pathways using DNA microarray time-series can provide invaluable information about the dynamic interactions among genes and result in new methods of rational drug design. Even though several purely computational methods have been introduced for DNA pathway analysis, most of these techniques do not provide a fully interactive method to explore and analyze these dynamic interactions in detail, which is necessary to obtain a full understanding. In this paper, we present a unified modeling and visual approach focusing on visual analysis of gene regulatory pathways over time. As a preliminary step in analyzing the gene interactions, the method applies two different techniques, a clustering algorithm and an auto regressive (AR) model. This approach provides a successful prediction of the dynamic pathways involved in the biological process under study. At this level, these pure computational techniques lack the transparency required for analysis and understanding of the gene interactions. To overcome the limitations, we have designed a visual analysis method that applies several visualization techniques, including pixel-based gene representation, animation, and multi-dimensional scaling (MDS), in a new way. This visual analysis framework allows the user to quickly and thoroughly search for and find the dynamic interactions among genes, highlight interesting gene information, show the detailed annotations of the selected genes, compare regulatory behaviors for different genes, and support gene sequence analysis for the interesting genes. In order to enhance these analysis capabilities, several methods are enabled, providing a simple graph display, a pixel-based gene visualization technique, and a relation-displaying technique among gene expressions and gene regulatory pathways.     

Parallel line integral convolution

Line integral convolution (LIC) is a powerful method for computing directional textures from vector data. LIC textures can be animated, yielding the effect of flowing motion. Both, static images and animation sequences are of great significance in scientific visualization. Although an efficient algorithm for computing static LIC textures is known, the generation of animation sequences still requires a considerable amount of computing time. In this paper we propose an algorithm for computing animation sequences on a massively parallel distributed memory computer. With this technique it becomes possible to utilise animated LIC for interactive vector field visualization. To take advantage of the strong temporal coherence between different frames, parallelization is performed in image space rather than in time. Image space coherence is exploited using a flexible update and communication scheme. In addition algorithmic improvements on LIC are proposed that can be applied to parallel and sequential algorithms as well.     

Simulating Gaseous Fluids with Low and High Speeds

Gaseous fluids may move slowly, as smoke does, or at high speed, such as occurs with explosions. High‐speed gas flow is always accompanied by low‐speed gas flow, which produces rich visual details in the fluid motion. Realistic visualization involves a complex dynamic flow field with both low and high speed fluid behavior. In computer graphics, algorithms to simulate gaseous fluids address either the low speed case or the high speed case, but no algorithm handles both efficiently. With the aim of providing visually pleasing results, we present a hybrid algorithm that efficiently captures the essential physics of both low‐ and high‐speed gaseous fluids. We model the low speed gaseous fluids by a grid approach and use a particle approach for the high speed gaseous fluids. In addition, we propose a physically sound method to connect the particle model to the grid model. By exploiting complementary strengths and avoiding weaknesses of the grid and particle approaches, we produce some animation examples and analyze their computational performance to demonstrate the effectiveness of the new hybrid method.