Specification - Network visualization with WebGL

From Gephi:Wiki
Jump to: navigation, search

Note: This specification is complimentary to Specification - Graph Visualization on the web and is meant for better communication and formation of the ideas into final shape.

Battle Plan

Community bonding period

I believe my main task during the bonding period should be getting through LearningWebGL & PhiloGL examples (also based on LearningWebGL, which should mean I can get a good understanding if we benefit from custom WebGL library or if we are much better of with PhiloGL).

Either during bonding period or at the start of coding it will also be beneficial to do some benchmarks and see if X3DOM could be used as well since it would simplify interaction.

That said (and being rather individual thing to do), there are a couple of things I would like to see some help with, namely algorithms.

Although I would like to avoid duplicating functionality of Gephi in WebGL, at this time I don't see how to do this without implementing algorithms also in Javascript.

Brainstorm

Solution to duplicating functionality of Gephi would be to use Streaming API if it can pass to the browser the coordinates/relationships between nodes. This significantly reduces the amount of work required and decouples the technologies. In such a case visualization library can become completely "dumb" and be responsible only for drawing of nodes and edges.

Library

Efficient and fast implementation of library will require usage of several not-yet-finalized technologies that are part of HTML5:

  • Rendering: WebGL
  • Communication: WebSockets
  • Processing: WebWorkers

Rendering

Since rendering a large number of nodes on the screen will present challenges even when using WebGL, Google at I/O conference had some nice tips with which they managed to draw 40k cubes.

At the start edges are going to be made with lines between data points, but since curves can provide added value for users, sooner or later Bezier's curves between data points will be needed. For those times, this optimization method looks very promising: Resolution Independent Curve Rendering using Programmable Graphics Hardware

Possibly interesting - Depixelizing Pixel Art If Three.js (WebGL 3D engine) is used, these tutorials could prove useful: Aerotwist Lab

Blacklisted hardware

For future reference, it is wise to keep in mind which drivers/hardware is blacklisted by the browsers (should also help when receiving user complaints if things won't work).

Chrome Firefox

Communication

While WebSockets will be used at a certain stage in the future, they are currently not a viable option due to serious security issues and are, as such, disabled by default in Firefox 4 and Opera.

When these issues are resolved they are a perfect technology for communication between server and browser.

It is open for discussion if we just implement with WebSockets or if we use another technology for the time being and replace it when WebSockets are safer.

Processing

Since Javascript is executed in a single thread, any operation that takes a while can block interface and prevent interaction until operation completes or browser/user terminates execution of the script. WebWorkers will resolve this issue by moving calculations to a separate thread (or threads; current WebWorkers specification does not provide information about the number of cores/CPUs a user has but we could consider using at least two workers if we will be able to paralelnize calculations) to ensure that any processing takes place in a separate thread to prevent lock down of browser and controls.

State of the art

Rendering of edges in WebGL/Shaders

How it is done in Gephi

Complex rendering using Bezier or Quadratic curves

WebGL tips

X3DOM related tips

HTML Canvas and SVG-based libraries

Not Javascript, but of relevant interest

  • Flare - Beautiful and powerful Flash based graph drawing (maybe some ideas to be taken)
  • Nodebox - Python visualization toolkit (nice GUI concept, but performance issues, need for "compilation" of the graph scene)
  • SIGMA - Flash Graph Visualizer
  • Graphviz - Sophisticated graph visualization language

Third party libraries that could be used

Graph APIs

GPU Computing

WebGL

WebCL

WebWorker Computing

Parsing GEXF/GraphML Files

Random