GPU Edge Bundling
Description
The code in this repo is inspired from
d3.ForceBundle
Edge Bundling Algorithms (What Do They Do)
Node-link graphs with many edges and nodes suffer from visual clutter, edge-bundling algorithms transform and group
the edges of a node-link graph in such a way as to improve the readability of the diagram. The process is for example
analogous to bundling network cable wires along their route in order have a clear understanding of the links between
entities and structural patterns of the network. There are several algorithms in this class, from ones that use hidden
user-defined meshes to control the bundling [1], to case specific ones such as for hierarchical data [2] and
finally to self-organizing methods based on physical force interaction simulations [3].
Force Edge Bundling
Force edge bundling [3] works by modelling edges between nodes as flexible springs which can attract each other if
certain geometrical compatibility criterions are met.
The input for the algorithm is a simple node-link diagram of a graph with nodes and edges. In order to change the
shape of the basic straight line edges between nodes, the algorithm proceeds by subdividing edges into segments.
Attraction *spring* forces are simulated between each pair of consecutive subdivision points on the same graph-edge.
Moreover, attraction *electrostatic* forces are computed between subpoints of different edges which are geometrically
compatible. The combined force acting on each subdivision point is computed and the points are moved a certain step
size in the direction of the force. The force-simulation on these sub-points is repeted a certain amout of iterations.
After the end of a cycle of iterations the resulting graph-edges are divided again in smaller segements and the whole
process repeats itself until the end cycle is reached. It's important to note that the position of original node-points
are fixed throughout the simulation.
This repo contains 2 implementations of the FEB algorithm:
1. A 2X speed-up version of the CPU-based edge bundling implementation found in
d3.ForceBundle.
2. A WebGL-based implementation based on the Jieting Wu et.al. publication [4].
Examples
US Air lines
References
[1] Cui, Weiwei, et al. "Geometry-based edge clustering for graph visualization." Visualization and Computer
Graphics, IEEE Transactions on 14.6 (2008): 1277-1284.
[2] Holten, Danny. "Hierarchical edge bundles: Visualization of adjacency relations in hierarchical data."
Visualization and Computer Graphics, IEEE Transactions 12, no. 5 (2006): 741-748.
[3] Holten, Danny, and Jarke J. Van Wijk. "Force‐Directed Edge Bundling for Graph Visualization." Computer
Graphics Forum (Blackwell Publishing Ltd) 28, no. 3 (2009): 983-990.
[4] Wu, Jieting, Lina Yu, and Hongfeng Yu. "Texture-based edge bundling: A web-based approach for interactively
visualizing large graphs." In Big Data (Big Data), 2015 IEEE International Conference on, pp. 2501-2508. IEEE, 2015.