Goal of Immersive Edge Path Bundling

The main goal of this project was to port the existing Edge Path Bundling algorithm to virtual/augmented reality. In order to achieve this, we first had to adopt the algorithm to work in 3D space. There were two main challenges to overcome:

3D space The original paper was designed for 2D space. To render our 3D scene we use Three.js and A-Frame for VR/AR support. The edge path bundling algorithm only uses references to nodes for bundling and never coordinates directly. This allowed us to easily port the algorithm to 3D space.

3D Layout algorithm The original paper uses datasets with a fixed layout e.g. airline routes. Due to our approach of extending the algorithm to 3D space, we loose the ability to use a fixed layout as such datasets usually only have 2D coordinates (latitude/longitude).
We therefore had to implement a 3D layout algorithm. We used the force-directed layout algorithm from vasturiano/three-forcegraph.

Development Process

The original graph in the 3D scenes with basic force based layout and no edge path bundling looked like this:

Original Graph

Basic Implementation

After implementing the edge path bundling algorithm, the graph looked like this:

First revision of Edge Path Bundling

Layout Optimization

We can see that the edge bundling works as intended. However, we still have a lot of visual clutter due to the force based layout. Markus Wallinger, the author of the original paper, suggested to only use a minimal spanning tree for the force based layout. Afterward, render all nodes as usual for the edge path bundling algorithm. This resulted in the following graph:

Second revision of Edge Path Bundling with an optimized layout.

Rendering Optimization

While the visual clutter is better than in the first revision, there is still room for improvement. We tried to clean this up by not rendering all edges at once, but only the ones where the start and end node is in the field of view of the camera. This resulted in the following graph:

Final result of Edge Path Bundling for orbit camera example.

Final result of Edge Path Bundling for VR example.

Implementation Details

General

Examples folder: Contains the demos as well as this documentation you read right now.

three-forcegraph-edge-path-bundling: This is a git subrepo that is forked from vasturiano/three-forcegraph and extended with the layout algorithm and edge path algorithm.

aframe-forcegraph-component: This is a git subrepo that is forked from vasturiano/aframe-forcegraph-component and contains a npm link to the three-forcegraph-edge-path-bundling to drive the VR/AR demos.

Docker: A simple dockerfile that packs the locally built static html/css/js files generated by npm in a default nginx image for deployment. The docker images are uploaded here

Layout

After loading the JSON containing all the nodes and links. We apply the prim algorithm to each connected component of the graph. This results in a minimal spanning tree (MST) for each connected component. The link strength of all edges that are not required for the MST is set to 0. This results in a Tree like structure.

Afterward, we apply the force based layout algorithm to the graph. The forces are the default forces of the used library.

Finally, we apply the edge path bundling algorithm to the graph. Currently, we did not manage to calculate in the background. Therefore, the visualization freezes until the bundling is finished.

Rendering

For rendering we used an orbit camera for the 3D example and an first person camera for the VR/AR example. However, this is just defined in the examples as this is not part of our extended library.

To further reduce the visual clutter, we only render bundled edges if the start and end node are in the field of view. This is done by calculating the view frustum of the active camera and enabling/disabling the visibility of the edges accordingly.

Results and Future Work

Visual Clutter: Using a MST for the layout algorithm only improved the clarity of the graph by a bit. We still have a lot of visual clutter. One way to further improve this could be to only render edges where the start and end node are in the field of view. This would reduce the visual clutter by a lot. Another could be to consider the layout for the edge path bundling algorithm or just implement filtering by the user (select certain nodes and edges to be rendered).

Benchmark results: A comparison to other edge bundling algorithms would be interesting in the future.

Implementation: While we use state-of-the-art libraries for rendering and VR/AR technology. Currently, there is no way to use our implementation in a production environment. A code cleanup, introducing flags to turn on/off our edge path bundling algorithm would allow us to create a pull request to the original library. This would ensure that our implementation is maintained and can be used by others. Another way would be to create a npm package ourselves.