Beamtrees

Die Grundlage für unsere Umsetzung bildet das Paper "Beamtrees : Compact Visualization of Large Hierarchies" von Frank van Ham and Jarke J. van Wijk. Beamtrees sind eine Weiterentwicklung der in Fachkreisen recht bekannten Treemaps, die hierarchische Baumstrukturen in einem zweidimensionalen Rechteck unter optimaler Nutzung des zur Verfügung stehenden Platzes darstellt. Symbolisiert beispielsweise ein Rechteck einen Knoten, so teilen dessen Kindknoten das Rechteck verhältnisgetreu in Unter-Rechtecke auf, usw. Explizit sichtbar sind schlussendlich nur die Blattknoten, die darüberliegende Struktur muss aus den Unterteilungen erkannt werden (siehe nächstes Bild).

Diese schlechte Darstellung der Hierarchie führte zur Entwicklung der Beamtrees: Die Rechtecke der Blattknoten werden verkleinert und verschoben, so dass die darunter liegenden Knoten zum Vorschein kommen. Man erhält somit zusätzlich eine Tiefeninformation (siehe Bild).

Da Tiefe nun der dritten Dimension entspricht, erhält man nun im Prinzip einen 3-dimensionalen Baum, dessen Knoten allesamt Röhren ("Beams") sind.

Wir haben beschlossen, bei unserer Implementierung den im Paper vorgeschlagenen 2D-Pseudocode gleich in 3D umzusetzen. Dank der von uns bei der CG23-LU entwickelten 3D-Engine ("Würmer") verfügten wir über ein gewisses Grundgerüst, welches wir um den Beamtree-Algorithmus erweiterten.

Die Implementierung erfolgt in C++ & DirectX 9, außerdem erfordern manche Effekte eine Shader-taugliche Grafikkarte.

Das Programm wird über die Datei "Beamtree.exe" gestartet und erfordert zu Beginn die Auswahl eines zu visualisierenden Ordners auf der Festplatte. Anschließend erfolgt die Darstellung als Beamtree, die per Maus frei dreh- und zoombar ist:

• linke Maustaste: rotieren
• rechte Maustaste: zoomen
• Leertaste: markierten Knoten zentrieren

Fährt man mit der Maus über die angezeigten Knoten, wird die entsprechende Datei- oder Ordnerinformation links oben angezeigt (der entsprechende Picking-Algorithmus stammt von www.geometrictools.com).

Zwei besondere Features können mit den Checkboxen aktiviert werden: Mit einem Klick auf "Ortho" wird die perspektivische Verzerrung abgeschaltet (klickt man dann auf 2D-View, erhält man eine Darstellung wie im ursprünglichen 2D-Algorithmus, siehe Bild unten), und mit einem Klick auf "Fog" wird Nebel aktiviert (für eine verstärkte Tiefenwahrnehmung).