Visualization of Large Unstructured Grids. Efficient Point and Cell Location

Abstract

Visualization of large datasets, 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 memory- efficient 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.

1 Introduction

While grids can oftentimes be visualized quite easily when assuming preconditions for their structure, in practice large un- structured grids are prevalent in many scientific fields and industrial applications such as wind flow analysis or structural me- chanics. Being able to perform visualiza- tion tasks in reasonable time is crucial for these applications, yet the transition from a structured grid to an unstructured one is far from trivial. The visualization of un- structured grids is a challenging endeavor that is based on a variety of spatial sub- division techniques and methods for point localization. Therefore I will introduce the underlying data structures and localization methods first to establish a solid foundation for the large field of point and cell location methods.

Afterwards I will present the works of Max Langbein, Gerik Scheuermann and Xavier Trichoche on point location in large unstructured grids (⁴ ) and the work of Christoph Garth and Kenneth I. Joy on cell location in unstructured grids (³ ). The approach of Langbein et al. was presented in 2003 and provided a remarkable gain in performance both in regards to memory overhead as well as performance. Garth and Joy base some of their ideas on the work of Langbein et al., however they use a different approach to storing data in order to increase performance even further and reduce memory overhead even more.

2 Foundations

In order to understand how and, more im- portantly, why the approaches introduced in this paper work efficiently, it is necessary to understand the underlying data struc- tures and concepts. The point location method of Langbein et al. uses the proper- ties of an adaptive k -d tree whereas the the cell location method of Garth and Joy uti- lizes the advantages of a bounding interval hierarchy data structure, both of which are introduced in the following chapter.

2.1 k-d trees

The idea of utilizing the structure of mul- tidimensional binary search trees for stor- ing information in order to perform asso- ciative searches on that data structure was first introduced by Jon Louis Bentley at Stanford University in 1975 with his def- inition of the k -d tree. A k -d tree is es- sentially a k-dimensional binary tree. That means it is a binary tree, in which every node has the dimension k. Speaking in a more graphical way it is a tree, in which every node is a hyperplane that subdivides a k+1-dimensional space. The children of each node represent splitting planes that further subdivide space on both sides of the hyperplane. For further information on k -d trees see the work of J.L. Bentley⁵.

When used for point visualization, k -d trees are usually constructed by placing splitting planes through the points contained in the structure to visualize. An illustration of the concept is shown in figure 1. It shows a 2-dimensional plane that contains points. In order to store the points a 1-dimensional k -d tree is created by using 1-dimensional splitting planes to subdivide the plane, i.e. straight lines that subdivide the space of the plane. Note that the k -d tree subdi- vides space, not the grid itself. Therefore cells of a grid can intersect with more than one leaf of a tree that partitions space over the grid, however every leaf does only con- tain one vertex of the grid. For further de- liberations on construction and usage of k - d trees see¹.

2.2 Bounding Volume Hierarchy

A common problem with ray-tracing is that the objects in a given space have com- plex shapes. An approach to better per- formance both in regards to memory us- age as well as computational speed is to construct bounding boxes around objects. These bounding boxes can be stored eas- ier since they need only the six bound- ing planes (in the simplest case). Due to the simplification of the object shapes, ray tracing can be performed faster since rays only have to be tested for whether they intersect with the object’s bounding box. Only if a ray does intersect with a bound- ing box, the more geometrically complex objects within the bounding box are tested for intersection with the ray. To further increase performance, bounding boxes are stored in tree structures that allow more ef- ficient ray traversal. For more on bounding volume hierarchies see⁶.

2.3 Bounding Interval Hierarchy

The Bounding Interval Hierarchy data structure combines concepts of the Bound- ing Volume Hierarchy for storing objects and concepts of k -d trees for traversing the data structure. A big step in utilizing the Bounding Interval Hierarchy for fast ray tracing was achieved in 2006 by Carsten Wächter and Alexander Keller at the Uni- versity of Ulm (see² ). The Bounding In- terval Hierarchy itself was first introduced by Beng Chin Ooi, Ron Sacks-Davis and K. J. McDonell in 1987 (see⁷ ).

The Bounding Interval Hierarchy enhances the capacities of the Bounding Volume Hi- erarchy by reducing the number of stored splitting planes from six to two and at the same time increases flexibility compared to k -d trees as well as the Bounding Volume Hierarchy by allowing overlapping children and splitting planes that do not form an ex- act split of the parent box. This is accom- plished by subdividing each stored bound- ing box along a split plane that is perpen- dicular to a chosen axis. Afterwards all objects are either sorted to the left or to the right side of that splitting plane. Addi- tional to that, since there are two splitting planes for every subdivision there can be empty spaces between the resulting bound- ing boxes. This results in a further gain in performance when it comes to ray tracing because rays can now move through empty space where they are guaranteed not to in- tersect with any bounding planes (see fig- ure 2). In order to choose the best splitting planes, the planes are chosen by a heuristic which results in more optimal trees. For more on the Bounding Interval Hierarchy see the work of Wächter and Keller².

2.4 Annotations

Notice that we assumed for all subdivision planes that they are axis-aligned. While it is generally possible to use non-axis aligned splitting planes in spatial subdivision data structures, throughout this paper when k - d trees or other similar data structures are used, the nodes stored will represent axis- aligned splitting planes.

Abbildung in dieser Leseprobe nicht enthalten

Figure 1: Partitioned Space and the resulting 1-dimensional k -d tree. The first splitting plane l1 is put through p5. The left and right children are the splitting planes through p2 and p7, l2 and l3. In this k -d tree not all points are intersecting a splitting plane, however they are still uniquely assigned to a leaf of the k -d tree. For the purpose of grid visualization, usually all points are stored as splitting planes. Source:¹

Abbildung in dieser Leseprobe nicht enthalten

Figure 2: Three stages of constructing a Bounding Interval Hierarchy. In a) all possible split plane candidates are shown. In this case the candidates are determined by subdividing along the longest side of the axis-aligned bounding box. b) shows the split plane candidates that will actually be used. c) shows the resulting bounding interval hierarchy in which a heuristic chose the final splitting planes. In the image a red splitting plane implies a left child, a blue splitting plane implies a right child. Source:² )

[...]

¹ M. de Berg, O. Cheong, M. van Kreveld,M. Overmars: Computational Ge-ometry: Algorithms and Applications.3rd edition, Springer, 2008.

² C. Wachter, A. Keller: Instant Ray Tracing: The Bounding Interval Hierarchy. In Eurographics Symposium on Rendering, 2006.

³ C. Garth, K.I. Joy: Fast, Memory Ecient Cell Location in Unstructured Grids for Visualization. In Visualizationand Computer Graphics, IEEE Transactions on, vol.16, no.6, pp.1541-1550, Nov.-Dec. 2010.

⁴ M. Langbein, G. Scheuermann, X. Tricoche:An ecient point location method for visualization in large unstructured grids. In Proceedings of Vision, Modeling, Visualization, 2003

⁵ J. L. Bentley: Multidimensional bi-nary search trees used for associative searching. Communications of the ACM, 18(9):509-517, 1975.

⁶ H. J. Haverkort: Results on Geometric Networks and Data Structures. Ph.D.thesis, Utrecht University, 2004, pp.5-21.

⁷ B. C. Ooi, K. J. McDonell, R. Sacks-Davis: Spatial kd-tree: An index-ing mechanism for spatial databases.In Proceedings of IEEE Int. Comp.Software & Applications Conf., Japan,1987.

⁸ Christopher P. Stone, Earl P. N. Duque,Yao Zhang, David Car, John D. Owens,Roger L. Davis: GPGPU parallel algorithms for structured-grid CFD codes.In Proceedings of the 20th AIAA ComputationalFluid Dynamics Conference,no. 2011-3221, 2011.