Specification - Network visualization with WebGL
From Gephi:Wiki
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.
Contents |
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).
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
- I think it is done using simple arc of circle, with a large radius? Would make sense, since it is both easy and fast to draw. Bezier is more for things like edge bundling (Julian)
- Drawing aliased arc of circle using Shaders (so it works with WebGL) http://stackoverflow.com/questions/4300959/opengl-glsl-shader-draw-a-circle-on-a-flat-polygon/4326537#4326537
- Drawing anti-aliased ellipses using only shaders http://my.opera.com/Vorlath/blog/2008/10/29/gpu-antialiased-circle-drawing
Complex rendering using Bezier or Quadratic curves
- First, a basic, easy to understand Bezier HTML5 example
- Introduction to splines, WebGL examples
- How to draw curves using OpenGL shaders and Bezier
- Rendering curves and surfaces on GPU (Microsoft Research)
- Rendering Vectors on the GPU (GPU Gems Book)
- Evaluate a cubic bezier on GPU (short example)
- We can take lesson from how it is done in O3D-WebGL - o3d-webgl/curve.js
WebGL tips
- Typical low-level WebGL workflow http://www.ibiblio.org/e-notes/webgl/gpu/make_cone.htm
- Low-level WebGL demos http://www.ibiblio.org/e-notes/webgl/webgl.htm
X3DOM related tips
- How to change rendering of lines (eg.. dotted, straight..) in X3D/X3DOM - shape.html#LineProperties
HTML Canvas and SVG-based libraries
- JavaScript InfoVis Toolkit - JIT, an interactive, multi-purpose graph drawing and layout framework
- Julian: "I think it has a good API structure, with a library dedicated to Graph data:"
- http://thejit.org/static/v20/Docs/files/Graph/Graph-js.html
- http://thejit.org/static/v20/Docs/files/Graph/Graph-Op-js.html
- Protovis - Graphical Toolkit for Visualization (JavaScript).
- Julian: "I think it has a nice approach to data processing, very high level and generic (any kind of data). it is not really specialized in Graph processing"
- arbor.js - Sophisticated graphing with nice physics and eyecandy.
- Canviz - JS renderer for Graphviz graphs
- Graph - JavaScript framework, version 0.0.1 Basic graph layout
- JavaScript Canvas Hyperbolic Tree - Small and flexible script
- JS Graph - It Promising project using HTML5
- jsPlumb - jQuery plug-in for creating interactive connected graphs
- jssvggraph - Lightweight yet nice graph layouter
- Moo Wheel - Interactive JS representation for connections and relations (not a force vector layout, but a circle one)
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
- DOM/XML walking can't be done in a WebWorker, it seems. But we might be able to do it using a pure-js XML library like "xmljs"
- See this example: http://xmljs.sourceforge.net/sampleApplications/sax/saxSampleApplication1/saxSampleApplication1.html
