Hierarchical multiresolution data structures for molecular visualization

Abstract

Biomolekulare Datensätze sind nicht nur komplex, sie wachsen auch mit der Entwicklung des Forschungsgebietes. Um ihre Eigenschaften zu erforschen, verwenden Experten unter anderem dreidimensionale Modelle der Datensätze, die aus Millionen individueller Moleküle bestehen. Bei der visuellen Analyse der Modelle kann es außerdem hilfreich sein, durch verschiedene Darstellungsformen strukturelle Eigenschaften zur Geltung zu bringen. Daher gibt es einen Bedarf an flexiblen Datenstrukturen, die es ermöglichten, effizient mit solche Datensätze zu arbeiten.Vorhandene Lösungsansätze im Bereich großer, auf Punktwolken aufbauender Datensätze verwenden in den meisten Fällen rasterbasierte Strukturen in verschiedenen Auflösungen. Andere Publikation konzentrieren sich dagegen auf die Verbesserung der Oberflächendarstellung, oder auf sich wiederholende Strukturen innerhalb großer Datensätze.Wir schlagen eine Octree Datenstruktur vor, die die Daten räumlich so aufteilt, dass jeder Datenblock eine ähnliche Menge Datenpunkte beinhaltet, und mehrere, interpolierbaren Auflösungsstufen zur Verfügung stellt. Die von uns vorgeschlagene Datenstruktur ist für Datensätze optimiert, die mehrere Millionen Punkte in einem einzigen Zeitschritt beinhalten. Der Aufbau der Datenstruktur erfolgt in einem Vorverarbeitungsschritt, dessen Resultat gespeichert wird, und daher nur ein Mal nötig ist. Zusätzlich effektivieren wir die Darstellung durch die Verwendung eines Least Recently Used Cache, der das Laden sichtbarer Datenblöcke verwaltet, und durch perspektivenabhängige Detaildarstellung. In unserer Auswertung zeigen wir, dass insbesondere das Anpassen des dargestellten Detailgrades die Frameraten signifikant erhöht. Die Kombination einer höheren Auflösung im Vordergrund, bei gleichzeitiger Reduktion der Daten im Hintergrund, erhöht die Geschwindigkeit deutlich, ohne, dass die visuelle Qualität beeinträchtig wird. Durch die Optionen, Details zu reduzieren und nur Datenblöcke zu laden, die im Blickfeld der Kamera sind, wird es möglich, Datensätze anzuzeigen, die ansonsten die Kapazität der uns zur Verfügung stehenden Ressourcen überlasten würden. Der Vorteil der auf der Dichte des Datensatzes basierenden räumlichen Aufteilung im Gegensatz zu einer regelmäßigen Aufteilung zeigt sich besonders bei der Verwendung von Algorithmen, die bei der Berechnung Nachbarschaften in Betracht ziehen. Das könnte insbesondere bei der Implementierung eines Solvent Excluded Surface (SES) Oberflächenmodelles, einer der wichtigsten, aber rechnerisch aufwändigen, Darstellungsformen solcher Datensätze, von großem Vorteil sein.

The complexity of biomolecular data sets is both high, and still rising. Three-dimensional models of molecules are used in research to test and investigate their properties. Such models can consist of several millions of atoms. Additionally, visual enhancement methods and molecular surface models are helpful when visualizing molecules. There is therefore a demand for efficient and flexible data structures to accommodate such large point-based data sets.Existing solutions in the field of molecular visualization for large data sets include the use of, in most cases, regular grid-based data structures, as well as levels of detail. Other papers focus on repeating structures or improving the efficiency of surface models.We propose an octree-based data structure that divides space into areas of similar density, and provides several levels of detail. Our approach is optimized for a single time-step, moving much of the computational overhead into a pre-processing step. This allows us to speed up frame rates for interactive visualizations using visibility culling, least recently used caching based on the pre-built octree data structure, and level of detail solutions such as depth-based level of detail rendering.In our evaluation, we show that level of detail rendering significantly improves frame rates, especially in the case of distance-based level of detail selection while keeping the amount of details in the foreground high. Both the possibility to reduce the resolution and the caching strategy that allows us to only upload visible parts of the data set make it possible to render data sets that previously exhausted the capacities of our test set-up. We found the main advantage of a density based octree, instead of a regular division of space, to be in neighbourhood-based calculations, such as the clustering algorithm required to build levels of detail. This could prove particularly useful for the implementation of a Solvent Excluded Surface (SES) representation model, which would be an important feature to include when developing the framework further.