Spatial Indexing Part 3

By
Dave
Project
Published
20 Aug 2011 00:20
Last Modified
13 Jan 2013 17:38

In part 1 and part 2 I discussed a basic approach to indexing stars, deep-sky objects and their corresponding labels.

I've now changed the spatial indexing algorithm from an approach based on right-ascension and declination to a Hierarchical Triangular Mesh (HTM). This has a far more even distribution of index cells for a given field of view, as can be seen by figures 1-3. Each image has a 50° field of view and a declination of 90°, 60°, and 0° respectively. In each case the number of index cells is the same. Compare this to the images in part 1, where the number of index cell varied singificantly with declination.

Spatial Grid

Spatial Grid

Spatial Grid

Figures 1-3. Spatial indexing using Hierachical Triangular Mesh.

As before, the images are shown with highlighted index cells for a reduced field of view based on the central reticle, rather than the entire view frustum. I've also included a right-ascension and declination grid in the background, and the cell ids for reference.

I needed to calculate the HTM trixels overlapped by the current field of view. This can be done recursively by using intersection tests between HTM trixels and the view frustum. The previous approach, based on right-ascension and declination, calculated cells based on an circle intersection, with the circle centered on the field of view. However, with increasing widescreen aspect ratios, this leads to cell selection outside of the field of view. While view-frustum culling is a slower algorithm, rendering less cells should be more performant overall.

Add Comment

*
*
*
Captcha
*
*Required