Specification - Network visualization with WebGL
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.
- 1 Battle Plan
- 2 Brainstorm
- 3 Library
- 4 State of the art
- 5 Third party libraries that could be used
- 6 GPU Computing
- 7 WebWorker Computing
- 8 Random
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.
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.
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
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
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).
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.
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
- 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
- How to change rendering of lines (eg.. dotted, straight..) in X3D/X3DOM - shape.html#LineProperties
HTML Canvas and SVG-based libraries
- Julian: "I think it has a good API structure, with a library dedicated to Graph data:"
- 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
- 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)
- 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
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