Sorting in space: multidimensional, spatial, and metric data structures for computer graphics applications

The representation of spatial data is an important issue in game programming, computer graphics, visualization, solid modeling, and related areas including computer vision and geographic information systems (GIS). Many representations are currently used. Recently, there has been much interest in hierarchical representations such as quadtrees, octrees, and pyramids which are based on image hierarchies, as well methods that use bounding boxes which are based on object hierarchies. The key advantage of these representations is that they provide a way to index into space. In fact, they are little more than multidimensional sorts. They are compact and depending on the nature of the spatial data they save space as well as time and also facilitate operations such as search. This course provides a brief overview of hierarchical spatial data structures and related algorithms that make use of them. We describe hierarchical representations of points, lines, collections of small rectangles, regions, surfaces, and volumes. For region data, we point out the dimension-reduction property of the region quadtree and octree, as how to navigate between nodes in the same tree, thereby leading to the popularity of these representations in ray tracing applications. We also demonstrate how to use these representations for both raster and vector data. In the case of nonregion data, we show how these data structures can be used to compute nearest objects in an incremental fashion so that the number of objects need not be known in advance. We also review a number of different tessellations and show why hierarchical decomposition into squares instead of triangles or hexagons is preferred. In addition a demonstration of the SAND spatial browser based on the SAND spatial database system and of the VASCO JAVA applet illustrating these methods (found at http://www.cs.umd.edu/~hjs/quadtree/index.html) will be presented.