Spatial Indexing

4 Oct 2010 00:11
Last Modified
13 Jan 2013 17:43

As the number of potentially visible items increases, it becomes less feasible to simply draw all items, and more important to select which items are actually drawn.

In order to avoid checking every object to determine if it should be drawn, an O(n) operation, it is necessary to assign each object with some type of spatial index. In this way, it is possible to determine only which indexes should be drawn and therefore eliminate large "buckets" of objects at once.

Many approaches for spatial indexing exist, and I initially set up a simple project to give me a test framework for different methods. The first approach was to use a simple regular grid based on right-asension and declination. I used an established algorithm1 for determining which grid cells are visible in a given field-of-view, and used labels for star names as the objects to index (Bayer and Common names are used, with Hipparcos designations added for other bright stars).

Some initial screenshots are shown below in Figures 1-3. The centered circle indicates the reduced field-of-view which is used to calculate which cells to draw (since using the entire viewport would not demonstrate that surrounding objects are culled). The green area indicates the grid cells which are calculated as overlapping the reduced field-of-view, and only labels within this area are drawn.

Spatial Grid

Spatial Grid

Spatial Grid

Figures 1-3. Spatial indexing using a right-ascension/declination grid

One of the drawbacks of using a regular grid based on right-ascension and declination (or any projection involving a singularity at the poles) is that the number of grid cells increases dramatcally around the poles. Other spatial indexing approaches such as a Hierarchical Triangular Mesh2 give more consistent areas per cell, and will be explored at a later date now that I have a test framework in place.

1 "The Zones Algorithm for Finding Points-Near-a-Point or Cross-Matching Spatial Datasets", Jim Gray, MarĂ­a A. Nieto-Santisteban, Alexander S. Szalay, April 2006
2 "Indexing the Sphere with the Hierarchical Triangular Mesh", Alexander S. Szalay, Jim Gray, George Fekete, Peter Z. Kunszt, Peter Kukol, and Ani Thakar, August 2005

Add Comment