Visualization of large data sets, especially the visualization of unstructured grids, is a challenge due to the unstructured nature of the data which oftentimes causes large overheads in memory as well as performance problems on large grids. Problems emerge because existing solutions generally presuppose properties like uniform point distributions for datasets which are usually not existent in unstructured grids. These issues become particularly problematic on large grids since the existing solutions, if they work at all for unstructured grids, do not scale well.
In this paper I will present two innovative approaches to visualization in large, unstructured grids. The first approach was developed by Max Langbein, Gerik Scheuermann and Xavier Tricoche. It makes use of cell adjacency and a complete adaptive k-d tree and utilizes ray shooting to locate points for visualization. The second approach was developed by Christoph Garth and Kenneth I. Joy. They use an innovative data structure, the celltree which is based on a bounding interval hierarchy, in order to narrow down the number of cells that conceivably contain points for visualization.
Both approaches present memoryecient and performant solutions for visualizing large unstructured grids, the approach of Garth and Joy further focuses on numerical robustness. The main difference between the two papers is that the work of Garth and Joy designs a data structure based on points and attempts to narrow down the number of cell candidates and subsequently performs a simple check for inclusion, whereas in the work of Langbein et al. the data structure design is based on the cells and uses ray tracing after making an educated guess for a cell close to the searched point. In other words, Garth and Joy present an approach to cell location, Langbein et al. present an approach for point location.
Inhaltsverzeichnis (Table of Contents)
- Introduction
- Foundations
- k-d trees
- Bounding Volume Hierarchy
- Bounding Interval Hierarchy
- Annotations
- Point and Cell Location Methods
- Efficient Point Location
- Efficient Cell Location
- Construction of Data Structures
- k-d Tree and Adjacency Information
Zielsetzung und Themenschwerpunkte (Objectives and Key Themes)
This paper explores efficient methods for visualizing large, unstructured grids, a common challenge in scientific and industrial applications. It presents two innovative approaches: one based on a point-based k-d tree and ray shooting, and the other utilizing a celltree structure based on a bounding interval hierarchy. Both methods address the limitations of existing solutions for handling unstructured data and aim to improve performance and memory efficiency.
- Efficient visualization of large, unstructured grids
- Point and cell location methods for unstructured data
- Adaptive k-d tree for point location
- Celltree structure based on bounding interval hierarchy for cell location
- Performance and memory efficiency considerations
Zusammenfassung der Kapitel (Chapter Summaries)
- Introduction: Introduces the challenge of visualizing large, unstructured grids and highlights the need for efficient solutions. It briefly describes the two approaches presented in the paper.
- Foundations: Provides background information on the data structures used in the presented methods, including k-d trees, bounding volume hierarchies, and bounding interval hierarchies.
- Point and Cell Location Methods: Outlines the two main approaches for point and cell location in unstructured grids. The first method, developed by Langbein et al., uses an adaptive k-d tree and ray shooting. The second method, developed by Garth and Joy, employs a celltree structure based on a bounding interval hierarchy.
- Construction of Data Structures: Discusses the construction of the k-d tree and the use of adjacency information for the first approach.
Schlüsselwörter (Keywords)
Visualization, unstructured grids, point location, cell location, k-d tree, bounding interval hierarchy, celltree, ray shooting, performance, memory efficiency, scientific visualization, industrial applications.
- Citation du texte
- Philipp Güth (Auteur), 2013, Visualization of Large Unstructured Grids. Efficient Point and Cell Location, Munich, GRIN Verlag, https://www.grin.com/document/305240
