Visualization of Large Unstructured Grids. Efficient Point and Cell Location (PDF)

Seminar paper from the year 2013 in the subject Engineering - Computer Engineering, grade: 1.0, University of Heidelberg (Computer Graphics and Visualization), course: Seminar Computer Vision, language: English, abstract: 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.