Specification - GSoC New Visualization Engine

From Gephi:Wiki

Jump to: navigation, search
This article is work in progress.



Contents

Specification

This page introduces a proposal for the New Visualization API that consists of three main interfaces: EventManager, SelectionManager and ConfigurationManager.

New Visualization API

Current visualization module contains three main components: Viewer, Controller and DataManager. The only class handling events is Controller. I propose to create a new EventManager class that will be a part of API and will allow to register custom listeners. The events from the controller will however not go directly to the EventManager, but a new abstract class MotionManager will be created to handle all events that are related to selection and movement. The abstract class will implement all selection related handlers and will notify Viewer of any running selection patterns that have to be drawn.

It will first be subclassed by a user-friendly 3D movement capable class. First proposal is to create a 2-axis movement (pitch and yaw), using the scrolling wheel for moving in the current direction. ModelView and Projection matrices will be created manually by a simple use of linear algebra. This design will allow adding a fast pure 2D implementation later in the process.

Event Manager

One of the most important parts of new API will be the EventManager interface. It is important that it allows adding complex listeners that listen to many events. To add a listenter through API, the VizEventListener interface will be implemented and its implementation will also provide the collection of all events that it listens to. Inside the EventManager, this listener will be then added to every related handler. An example could be a gesture tool that would run after clicking the mouse and moving it along a given shape - this would require two events: mouseLeftClick and mouseMove.

File:eventlistener.jpg
Figure 1. Event listener

Selection

Currently Gephi uses the octree and OpenGL selection buffer to retrieve all selected nodes. Nodes that are in octant that is in selected region are picked. The Octree and Octant classes will be rewritten completely and the new octree's interface will provide a method for getting all nodes that are contained in a given frustum. This will be done by simple frustum/octree intersection method, where every child of an octant is tested for inclusion or partial inclusion in the frustum. If proper optimizations (such as using spherical or conical bounding objects) are used, this method can be very fast. This method also allows using other selection shapes as ellipse or polygon selection.

Selection Manager

The SelectionManager interface will provide basic methods for determining the currrently selected nodes. First implementation will work with the 3D environment. For a static graph, finding the selected nodes is simply a matter of finding the intersection of a frustum and a selection object as will be shown later. If the graph layout algorihm is in progress however, and nodes are moving, the spatial structure can be in some cases useless as nodes can be changing their positions so actively that it is too expensive to make updates on every single node. In such cases I propose to ignore the data structure and rebuild it every time when required. This may cause somewhat slow selection, but selecting a moving group of nodes is from user's point of view probably not a priority. This also requires that there is a method for finding the current node movement status.

Since the getSelectedNodes() is a very expensive method, the SelectionManager will only allow one query thread to be in progress. All requests will have to wait until the current query is finished. Due to the constant frequency of graph updates, there can be an inconsistency in selected nodes in case of running layouts. Again, standard way of operation of selection tools is on a static graph, so this may not be a problem.

The selection queries will be later used for optimization as visibility queries. This can make the displaying of graph in 3D much faster, but there is again a problem with node motion in case of layouts. Again I propose that the visibility queries are simply disabled during layout.

Later a 2D implementation will be created. If octrees prove to be fast enough, quadtrees will be used for 2D. This will allow users to switch betweeen fast and transparent 2D view and possibly slower, but much more insightful 3D.


Frustum

Deciding whether point lies in a frustum requires to keep all six walls that make up the frustum. Then let n = (n1,n2,n3) be the normal vector of a plane, p = (p1,p2,p3) coordinates of a point and d distance of plane from origin along its normal vector. Then depending on whether distance = < n | p > + d > 0 or distance < 0 the point is behind or in front of the plane. Doing this for all eight vertices of an octant tell us whether octant is in the frustum, outside the frustum or intersects the frustum. We can optimize this easily by bounding the octant with a sphere and instead of doing eight computations, we can do only one (in case the sphere is inside the frustum). It is also possible to bound frustum by a cone, which makes testing even faster.

Polygon

To enable better selection tools such as a polygon, all we have to do for every tested point, is to cast a ray from camera to the point of interest and check whe ther the intersection of the ray and near plane lies inside the polygon. Let p = (p1,p2) be a point of interest, y = ax + b be the standard equation for a line representing a polygon's edge. A new ray (in 2D) is casted in any direction, for example to the right, let y = p2 be the equation for this ray. If ray intersects the polygon even number of times, it is outside and it is inside otherwise. We can compute the intersecting point by solving two equations for ray and line: x_1 = \frac{p_2 - b}{a} and y1 = p2 are the coordinates of the intersection point. Having the intersection point, it is easy to find out whether it lies on the polygon's edge. I propose the following interface:

File:octree.jpg
Figure 2. Octree

This proposal focuses on octrees, but other structures will be also studied and Octree interface will be abstracted to allow implementation of other (eventually more optimal) structures.

Configuration Manager

We have to separate two ways of modifying the settings. One through a public visualization configuration API and other induced by the user. The first one will enable easier and more transparent work with the way graph is displayed and the second one will allow user to customize and fine tune the current view. The configuration API will take a form of a singleton class and can be built on the current VizConfig class. The ConfigurationManager will provide methods for Viewer to display graph according to the configuration. I propose creating a VisualizationCreator class that can be implemented for custom visualization of components.

File:VisualizationProperties.jpg
Figure 3. VisualizationProperties

StandardVisualizationCreator will be subclassed and its methods will be overriden to access the scene objects attributes. User induced modification will be handled through context menus.

Context Menu

Context menu should be fairly easy to implement using basic Swing (or AWT) components. It is important that the controller stops listening at the menu creation time. I will assume that we do not want modularity at the view level (as with menus this would not have much sense), but there is a need for modularity of menu contents and actions.

First we can define a context. We want different menus for nodes, edges or the background. So we can define Context as class representing a type of context and all data (Node, Edge, etc.). I propose to create a class ContextMenuManager that will create all menus for every possible context at startup. Event manager will then ask for the menu and displays it. Menu will consist of ContextMenuComponents that will be registered to ServiceProvider. At first we will support only simple menu items, but menu items with text fields, checkboxes, etc. can be added as abstract subclasses.

File:context_menu.jpg
Figure 4. Context menu manager

Context subclass will be defined for every required context and along with its type it will contain the context object.

File:context_menu2.jpg
Figure 5. Context menu

In case of node or edge context menus, it is important that the Context not only contains information about the underlying graph node or edge, but also their visual representation.

Schedule

This is an approximated schedule that I would like to follow:

  • May 23 - May 29 - Create a mock API with as many interface methods as possible. Link Controller to MotionManager and EventManager.
  • May 30 - June 5 - Implement selection in MotionManager and sublass with 3D motion - implement creation of modelview and projection matrices.
  • June 5 - June 12 - Implement EventManager, reuse as much code as possible from the old visualization module.
  • June 13 - June 22 - Implement the octree and node selection.
  • June 23 - June 29 - Test the solution and optimize where possible.
  • June 29 - July 5 - Enable modification of settings.
  • July 6 - July 12 - Implement context menus.
  • July 13 - July 16 - Add 2D support - SelectionManager subclass
  • July 17 - July 20 - Add 2D support - MotionManager subclass.
  • July 21 - July 27 - Add 2D support - data structures.
  • July 28 - August 3 - Test the 2D implementation.
  • August 3 - August 15 - Clean up code, finalize API, implement addiontal features that have been proposed during past weeks.
  • August 16 - August 22 - Pencils down week, finalize documentation.

References

Retrieved from "http://wiki.gephi.org/index.php/Specification_-_GSoC_New_Visualization_Engine"
Personal tools