treevis

treevis - Botanical Visualization of Harddiscs

Autoren: Matthias Bauchinger und Paul Pöltner
7. Juni 2004

Hiermit präsentieren wir eine Implementation des Papers "Botanical Visualization of Huge Hierarchies" von Ernst Kleiberg, Huub van de Wetering und Jarke J. van Wijk.
Wir haben uns auf eine Visualisierung von Festplatten-Verzeichnissen mit ihren Inhalten spezialisiert.
"treevis" soll dem Benutzer die Möglichkeit geben

die Struktur seiner Verzeichnisse zu erkennen.
herauszufinden, warum seine Festplatte voll ist.
eine Umstrukturierung vorzunehmen (Dateien und Verzeichnisse verschieben, löschen etc).

Wir verwendeten folgende Werkzeuge und APIs für die Implementierung:

C++
MFC (http://msdn.microsoft.com/)
OpenGL (http://www.opengl.org/)
Microsoft Visual Studio .NET 2003 (http://msdn.microsoft.com/visualc/)
FreeType-Engine (http://www.freetype.org/)
Subversion (http://subversion.tigris.org/)

Das Programm erlaubt dem Benutzer nach dem Start ein einzelnes Verzeichnis mit seinen Unterverzeichnissen, oder eine gesamte Festplatte für die Visualisierung auszuwählen. Das Parsen der Festplatte und der Aufbau des 3D-Baums findet in einem eigenen Thread statt. Dadurch kann das Programm während dieser Berechnungen normal weiterbedient werden. Es ist dem Benutzer ausserdem möglich, diesen Berechnungsschritt jederzeit abzubrechen. Dies ist vorallem dann sinnvoll, wenn man bemerkt, dass das Parsen einer ganzen Festplatte zu lange dauert. Nach dem Abbruch wird der bereits berechnete Baum trotzdem ausgegeben.
Allgemein kann gesagt werden, dass das Parsen der Festplatte im Vergleich zum Aufbau des 3D-Baums wesentlich länger dauert. Zeitlich ausgedrückt kann damit gerechnet werden, dass über 90% der Berechnungzeit für das Parsen aufgewendet wird. Allerdings werden schon einmal geladene Verzeichnisse beim nächsten mal viel schneller geparst - vorausgesetzt das Windows - Indexing - Service ist aktiviert.

Der nach dem Referenzpaper aufgebaute Baum wird intern in einem Szenengraphen gespeichert, der pro Node unter anderem nur ein Mesh und ein Frame relativ zur Parent-Node benötigt. Es war also für die Umsetzung des Papers ein extrem einfacher Scenegraph ausreichend.
Für die OpenGL-Einbindung wurden alle OpenGL-Befehle durch eine GraphicsDevice-Klasse gewrappt. Dies erlaubte eine schöne Trennung des Algorithmus von der Darstellung. Die Meshes der Nodes liegen intern in einer optimierten Version als OpenGL-Displaylists vor. Ausserdem muss angemerkt werden, dass abgesehen von den speziellen Astgabel-Meshes nur 3 weitere Meshinstanzen im Hauptspeicher verweilen: ein Zylinder für alle Äste, eine Kugel und ein Kegel für die Darstellung der Dateien. Die unterschiedliche Darstellung jeder einzelner Mesh-Referenz wird rein durch Transformationsmatrizen und Farbattribute erreicht. Dies hat die positive Auswirkung des geringen Speicherbedarfs von "treevis".
Für die graphische Ausgabe von Texten im Renderwindow verwenden wir die ausgezeichnete Font-Rendering-Engine "freetype". Sie punktet vorallem durch einfache Integration und Antialiasing mit 256 Alphastufen.

Für die eingebaute Datenmanipulation verwenden wir den Windows-Explorer als ActiveX-Element. Dieser ist jedoch stark mit dem 3D-Baum synchronisiert: Wird ein Verzeichnis im 3D-Baum selektiert, so wird dieses auch im Windows-Explorer angezeigt. Ebenso wird bei der Navigation im Windows-Explorer immer das aktuelle Verzeichnis im 3D-Baum selektiert. Dadurch wird gewährleistet, dass man die Übersicht nicht verliert.

Bei Selektion eines Verzeichnisses im 3D-Baum wird am oberen,rechten Fensterrand der Namen des Verzeichnisses angezeigt. Und bei Selektion einer Datei wird zusätzlich noch die Dateigröße mitausgegeben.

Das Programm erlaubt es auch, einige Parameter für den Algorithmus zum Aufbau des 3D-Baumes zu verändern:

Alpha: der Winkel für die Drehung um die Z-Achse einer Astgabel bei der Abspaltung
Beta: der Winkel für die Drehung um die Y-Achse einer Astgabel bei der Abspaltung
Epsilon: ein Prozentsatz der angibt, wieviel Prozent der gesamten Verzeichnisgröße bei jeder Gabelung abgespalten werden.

Für eine genauere Beschreibung dieser Parameter (und des gesamten Algorithmus) verweisen wir hier auf das Referenzpaper.

Um den ganzen Baum etwas bunter zu gestalten, haben wir für die verschiedenen Dateitypen andere Farben bei den Kegeln gewählt. Für dieses Release von "treevis" haben wir die Farben für einige bekannte Dateitypen hardgecodet. Darunter sind z.B. Extensions wie .exe, .dll, .doc, .xls, .cpp, .bmp, .jpg, .xml, .html und noch einige andere.

Ergebnisse:

Das Programm ist sehr gut geeignet, herauszufinden warum die Festplatte voll ist. Ausserdem kann man sich ein sehr gutes (und auch nicht unhübsches) Bild der Struktur seiner Festplatte machen.
Im Bereich der Datenmanipulation könnte man jedoch noch einiges an Arbeit investieren.
Das gleiche gilt auch für die Darstellung der Astgabeln. Hier könnte man noch ein "schöneres" Mesh generieren.

Zu Beginn des Projektes hatten wir auch geplant, die Manipulation des Baums in 3D durchzuführen. Es wurde uns allerdings schnell klar, dass wir hierfür einen erheblichen Aufwand in die 3D-Interaktion stecken müssten, der den Nutzen nicht rechtfertigen würde. Ein weiterer Grund den Windows-Explorer für diese Aufgaben einzubinden, war ausserdem noch der Bekanntheitsgrad in der Verwendung des selbigen.

Ausserdem hatten wir noch ein Feature implementiert, dass je nach Dateityp den einzelnen Kegeln eine andere Textur verleiht, nämlich die bekannten Icons aus dem Windows-Explorer. Nach der Fertigstellung erkannten wir jedoch, dass die Erkennung der einzelnen Dateitypen stark darunter leidet und die Kegeln nur mehr als punkter "Klecks" erkennbar sind. Desswegen haben wir dieses Feature wieder herausgenommen.

Alles in allem sind wir allerdings mit der Usability und der 3D-Darstellung von "treevis" sehr zufrieden, und hoffen das es für so manche andere User auch einen Nutzen bringt. Zumindest um herauszufinden, warum die Festplatte schon wieder voll ist :-)

Der Anblick von treevis nach dem Start. Die 3 farbigen Linien in der Mitte bilden das Root-Referenzframe zur besseren Orientierung.

Die Visualisierung von C:\Windows. Hier ist sehr schön zu erkennen, dass die Unterverzeichnisse "System32" und "ServicePackFiles\i386" den meisten Platz verbrauchen.

Das C:\Windows\System32 - Verzeichnis nach dem Heranzoomen und Selektieren.