Graph Animation and Labeling on a Large Scale
Cody Robson cjrobson AT cs.ubc.ca
Presenting an explorable view of any undirected graph at a large scale on a radial layout. Animated recentering should support many nodes and possibly dynamic text label display depending on priority and available space. For the animations to be coherant, a high and constant framerate must be sustained as the amount of data scales up.
Any tree or undirected graph would be a suitable candidate for this type of visualization. A dense filesystem could be a good choice to stress the upper limits of both the program's ability to render and animate as well as a human's ability to perceive the data. This solution is not very dataset-driven so it should be flexable enough to handle a variety of things.
I have a background in computer graphics, specifically using OpenGL and the GLSL shading language. I have done some small projects using General Purpose GPU Programming before, though they were implemented at the lowest level with custom pixel shaders. If needed for this project I'd like to try a GPGPU library like CUDA or something equivelant.
The idea is to implement Yee et al's Animated Exploration of Dynamic Graphs with Radial Layout algorithm with a similar interface and try to scale it up as far as possible. Given the power of todays graphics cards it's difficult to judge how far that solution can be scaled simply by naively pushing as much work at the GPU as possible with no thought of optimising computation or rendering time. I hope to make use of techniques presented in Fekete et al's Interactive Information Visualization of a Million Items. There are two possibilities this project could move towards. First, scaling up the animated transitions from Yee's algorithm on very large datasets might be a very difficult task. In this case I'd like to explore doing as many calculations as possible on the GPU and cut down on rendering time by using shaders traditionally. Second, it could be possible to reach a human or screen-sized limit on the number of nodes displayed at a time simply by using a modern graphics card and giving no consideration to any speedup techniques, the GPUs might just be that fast. In that case I'd like to explore trying to improve 2D text label placement given a priority value to each node. Doing label placement dynamically as well as aethstetically pleasing is a nontrivial task and could certainly extend this project in the event that the scaling aspect alone becomes trivialized by today's graphics hardware.
Scenario of Use
The interface should be lightweight and intuitive. The user should be able to load a dataset which initially displays a graph with an intelligent choice for a default center. There should be sliders for zoom and panning, (or possibly a focus+context style fish-eye zoom in addition to traditional scaling zoom) but idealy both of these tasks should be supported by mouse drags (perhaps left-drag pans and right-drag rotates about the center) and scroll wheeling. Once the dataset is loaded the user should be able to recenter to visualization by selecting another node of interest. The graph should animate nicely a la Yee et al's algorithm such that the user isn't completely disoriented by all the traveling most of the graph has to do. It should support both cartesian and polar transitions, as having one implemented causes the other to be trivial. At large scales, it might be possible that even their nicely animated transitions become too much for the user to digest, so perhaps automatic zooming and unzooming should be built into the animation process, but it is hard to estimate if that situation will arise and if that solution would even help.
I would like to program this solution in C++ using OpenGL for performance reasons alone. (My Direct3D skills are limited.) For a shading language, GLSL is a native match as opposed to more general languages like Cg. I have not yet decided on a windowing library, I might default to something like FLTK simply because I'm already familiar with it, and it is (in theory) cross-platform.
On the left is an example from Lee et al's paper. The idea is to try to scale up something like this to the limits of the GPU, the monitor size, and/or human perception. My solution may try to take advantage of focus+context layouts by decreasing the size of the circles that the nodes are positioned on as they get further away from the center, if it proves to be visually useful as scale increases. A quick mock-up of this is on the right. It becomes obvious that as rings get denser, text labeling would become more and more difficult to implement on something like the image on the right. The user interface (not shown) should be simple and intuitive, as it itself is not the focus of this project but should be of a sufficient level of visual and usable quality to correctly assess the real core of this project, that is graph visualization at large scales.
Week One: Basic graph drawing infrastructure in OpenGL
Week Two and Three: Implement Animated Exploration of Dynamic Graphs with Radial Layout
Week Four: Push scalability, determine whether it be the focus of the project or if text labeling should be explored instead.
Week Five and Six: Complete either scalability or label placement, begin working on presentation and final writeup.
Week Seven: Present final presentation and complete writeup.
Animated Exploration of Graphs with Radial Layout Ka-Ping Yee, Danyel Fisher, Rachna Dhamija, and Marti Hearst, Proc InfoVis 2001.
Interactive Information Visualization of a Million Items Jean-Daniel Fekete and Catherine Plaisant, Proc InfoVis 2002.