**GraphVR: A Virtual Reality Tool for the Exploration of Graphs with HTC Vive System**
				_Graph exploring using Virtual Reality and UE4_
				
![Les Miserables standard Gephi Graph](UE1.png width="100%" border="1")						   

Abstract
===============================================================================
_This work examines the use of the VR in order to visualize and interact with a 3D Graph. 
The design has been developed to be the most natural and intuitive as possibile through
analysis, study and use of several layout's algorithms which allows to position
the graph's nodes in order to reduce entropy level. The idea to use a schematic visualization
through the Graph is due to the fact that it is able to describe synthetically the data and the
relative links between them and represent them in visual format.
The application has been entirely developed using UE-4.15.2 and the visualisation 
has been performed using the HMD called HTC Vive._   

Features
===============================================================================
![Controllers and CableComponents](17.gif width="46.77%" border="1")
The Interaction with the components in the scene is possible through the HTC vive's controllers. In order to 
query the scene we use a technique called Ray Casting. One ray start from each controller along the direction
of their respective _forward vector_ up to _end location_ previously set. The Ray is constantly shown through a
_CableComponent_. A viewfinder is used to aim and to interact with the objects in the scene. 
Moving the Controllers in the scene results also in the motion of the ray attached to it. The scene is constantly queried and
when the ray comes hits an _Actor_, the system checks if it is an element with whom is possible to
interact, in order to activate eventual further features.
</br></br></br>
![Controller description](27.png width="46.75%" border="1")
_1. Menu button (Shoulder)_
</br></br>
_2. Trackpad_
</br></br>
_3. System Button (Unused)_
</br></br>
_4. Trigger (Trigger and Trigger Axis)_
</br></br>
_5. Grip Button_
</br></br>
_6. Trackpad Press (Thumbstick)_

Left HTC vive's controller
-------------------------------------------------------------------------------
![Zoom +/-](6.gif width="95%" border="1") ![Graph movement](9.gif width="99%" border="1")
When one of the controllers's _Grip Button_ is pressed, each _RootComponent_ of each node is attached to one _Actor_.
Whenever the controller is moved, the distance between its initial and final position is computed as a vector just before the rendering of each frame.
This vector is applied to the _Actor_'s location, which will start to follow the controller's movements and it will move all actors attached to it.
When one _Grip Button_ of both controllers is pressed, then the graph is scaled up or down showing a zoom effect, increasing or
decreasing the distance between two controllers. 

![Trackpad usage](16.gif width="50%" border="1")
Point number two, shown in the _Controller's description_ image points to the trackpad.
_Character_'s movements are associated to the trackpad along four directions in which is possible to move (Up, Down, Right and Left). 
Although it is possible to move into the scene by simply walking, it is unthinkable to do it for long distances because of the size difference 
between virtual environment and real environment. Through this feature it is possible to move without taking any step. 
Another interesting feature is the one that allows to visualize a node's details using the _Trigger_ button.
Data are shown through a pop-up placed on the right controller and will be closed at the release of the button;
on button's release, the node is placed back in its original position.   

![Menu Button](1.gif width="50%" border="1")
For a better user experience, it has been implemented a menu that groups a set of features. 
Pressing the _Menu Button_, placed above trackpad, it is possible to retrieve this menu. It is compoesed by 6 labels,
placed all around the controller, each one for every implemented feature. It is possible to select any of these labels by pointing
the right controller on one of them.

- Select Layout
- Reset graph
- Unselected nodes
- Node Clustering
- Node Declustering
- Fly Up/Down

Right HTC vive's controller
-------------------------------------------------------------------------------  
![Graph rotation](5.gif width="97%" border="1") ![Selecting a Node](2.gif width="97%" border="1")
Each Controller's _Grip Button_ allows to move the whole graph . It's possible to rotate the graph along two axes. 
_Trakpad Up_ and _Down_ buttons allows to rotate the graph along _x_ axis,  the _Trackpad Left_ e _Right_ apply a rotation to the graph along _y_ axis of our reference system.
When the ray hits a node along its direction, its color changes from red to green and its length is modified in order to avoid crossing of the selected node.
Using _Trigger_ button, the node's name is visualized through a label positioned on the controller. This feature also allows to move the node by placing
it in a position of choiche. When the button is released, the node will remain in its new position and the label is resetted.

![Multiple selection](10.gif width="97%" border="1") ![Clustering and Declustering](11.gif width="97%" border="1")
This button on the left controller allows to select or deselect the nodes in order to move more than one at a time. When a node is selected, it changes its color 
becoming black, returning back to its original color when instead it is deselected.
By selecting multiple nodes it is possible to create a cluster, which is represented by one big node. The cluster's nodes and their attributes are stored in a data structure.
In this way, when the declustering is performed, the cluster is removed and the nodes are repositioned in their original positions. The application allows to make more clusters
and subsequently allows to select which one to remove or to remove them all together.

![Fly Up/Down](10.gif width="50%" border="1")
It has been implemented a feature which allows to the avatar to ignore gravity and to simulate flight. 
This allows to the user to examine the graph from above or from any point of view he prefers. 
When the gravity is disabled, the user can move in the scene just by looking toward the desired direction and by pressing the directional buttons.

Layouts
-------------------------------------------------------------------------------
![2D Base Layout](3.gif width="97%" border="1") ![3D Force Directed](4.gif width="97%" border="1")
Two type of layouts have been implemented, which can be selected by the user. The first layout is called Base Layout and is similar to the Gephi's 2D layout.
The second layout is called Force-Directed and it is implemented in 3D.

Video
===============================================================================  
![](GraphVR.mp4 width="100%" border="1")  

<!--
Future Works
===============================================================================

Layout algorithms
-------------------------------------------------------------------------------
![Future Layout Optimization](clustering width="100%" border="1")-->
<!-- Il disegno del grafo è stato effettuato attraverso un approccio a _Modelli fisici_. Tale approccio si basa sull'idea di vedere il grafo come un insieme di corpi che 
seguono leggi fisiche se doverle per forza rispettare alla lettera e lasciare che siano esse, agendo, a portare il sistema in una disposizione valida. Il grafo in questo
caso, viene visto come un insieme di anelli elettricamente carichi sui nodi connessi da molle ai lati. In questo modo, si crea nel modello una foraz repulsiva tra ogni nodo,
mentre le molle creano una forza di attrazione che avvicina i nodi adiacenti.

Un possibile sviluppo futuro si incentra sulla risoluzione di uno dei grandi problemi degli algoritmi a modelli fisici che emerge in maniera più drastica con la dimensione
dei grafi: Essendo algoritmi basati unicamente sull'ottimizzazione iterativa del disegno, la disposizione iniziale dei nodi è assolutamente casuale. La soluzione potrebbe essere
una fase di pre-processing che suggerisca all'algoritmo un posizionamento iniziale dei nodi. L'idea è quella di utilizzare dei cluster di nodi che definiscono delle macroaree di
posizionamento. A questo punto sarebbe possibile utilizzare un algoritmo a modello fisico in maniera più efficiente poiché il numero di nodi si è ridotto. Successivamente basterebbe
sostituire al cluster il gruppo di nodi che esso rappresenta a riapplicare iterativamente l'algoritmo di posizionamento ai nodi del cluster. In questo modo si dovrebbero ottimizzare i
tempi di calcolo del posizionamento dei nodi rispetto ad un posizionamento casuale. -->
<!--
Drawing
-------------------------------------------------------------------------------
-->
<!-- Uno dei problemi principali riscontrati nello sviluppo di quest'applicazione è il numero di nodi che è possibile visualizzare. Maggiore il grafo è complesso, maggiori saranno le difficoltà
di visualizzazione e di interazione. Un idea che è possibile prendere in considerazione è quella di utilizzare dei volumi concentrici nella scena -->
<!--
Oriented Graph
-------------------------------------------------------------------------------
-->
Conclusions
===============================================================================
GraphVR only supports graphs of small-medium dimension, typically with a maximum value of around 300 nodes. This limit is due to the management of the number of _Actors_ , in fact there is one for each node. 
It is also necessary to consider all actors that represent the arcs, the lights, the avatar, the billboard and everything that is part of the scene. Being the compute complexity very high, it has become necessary to find 
a compromise between rendering quality and system fluidity by reducing the _Level of Details_ of the actors. The idea in the future is to continue to develop this application using: different type of layout algorithms, 
simplifying and improving interaction with the user, improve the level of details and the number of visualizable nodes .

BibTex references
===============================================================================
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
@article{8564202,
	author		=	"Nicola Capece and Ugo Erra and Jari Grippa",
	booktitle	=	"2018 22nd International Conference Information Visualisation (IV)", 
	title		=	"GraphVR: A Virtual Reality Tool for the Exploration of Graphs with HTC Vive System", 
	year		=	"2018", 
	pages		=	"448-453",
	keywords	=	"data visualisation;entropy;graph theory;helmet mounted displays;virtual reality;schematic visualization;graphical data;visual format;Unreal Engine version 4;entropy levels;layout algorithms;three-dimensional graphs;HTC Vive system;virtual reality tool;GraphVR;head-mounted display HTC Vive;Three-dimensional displays;Data visualization;Visualization;Layout;Engines;Virtual environments;Tools;Virtual Reality;Graph Exploration;Human Computer Interaction", 
	doi			=	"10.1109/iV.2018.00084", 
	ISSN		=	"2375-0138", 
	month		=	"July",
}
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

<!-- Markdeep: --><style class="fallback">body{visibility:hidden;white-space:pre;font-family:monospace}</style><script src="markdeep.min.js"></script><script src="https://casual-effects.com/markdeep/latest/markdeep.min.js?"></script><script>window.alreadyProcessedMarkdeep||(document.body.style.visibility="visible")</script>
<style>

	.hljs-comment, .hljs-keyword {
		color: black;
	}
	
	.md div.imagecaption {
		text-align : center; !important
	}
	
	.shortTOC {
		display : none;
	}
	
</style>