Dr Dave

I discussed in parts 1 and 2 an approach to allow efficient selection of nearby stars to a reticle. I originally used an index which divided the sphere volume into 50 equal divisions along each axis, giving 25,000 cubes. This gave a distribution of items per key as shown in Figure 1.

Figure 1. Hipparcos Cartesian Spatial Index.

Switching to a Hierarchical Triangular Mesh (HTM), also known as Quaternary Triangular Mesh (QTM), gives a more even distribtion with less cells containing very few stars, as shown for subdisivion level 5 in Figure 2. This results in a more consistent behaviour in selecting nearby stars.

Figure 2. Hipparcos HTM L5 Spatial Index.

Using HTM also makes it easy to index at multiple levels of detail, such that an appropriate index can be used at a given field of view.

I decided to switch from Equirectangular to Tessellated Octahedral Adaptive Subdivision Transform (TOAST) projections. TOAST is an extension of the Hierarchical Triangular Mesh (HTM) proposed by Jonathan Fay, chief architect and developer of Microsoft's WorldWide Telescope (WWT). HTM is a representation of a sphere proposed by astronomers in the Sloan Digital Sky Survey (SDSS), which recursively subdivides an octohedron to approximate a sphere with a highly-tesselated polyhedron. The TOAST projection folds the subdivided octahedron out into a square that is very convenient for use in an image pyramid.

Tesselating an Equirectangular projection into a set of texture tiles corresponds to areas on the surface of a sphere bounded by lines of latitude and longitude. The sphere can therefore be approximated using "Slices and Stacks", as shown below in Figure 1. In order to switch to a TOAST projection, the first thing I needed to do was generate the underlying HTM geometry, as shown below in Figure 2. Note that while the fist level is an octohedron in both cases, subsequent levels of Slices and Stacks begin clustering tiles around the poles whereas HTM levels retain a more even distribution.

Figure 1. Slices & Stacks L1-L4

Figure 2. HTM L1-L4

Once this was done, I needed to add the relevant texture coordinates to each indexed vertex to map the corresponding TOAST texture tile. Each texture tile maps to two triangles, or HTM "trixels". The texture mapping for an Equirectangular projection is shown below in Figure 3, with the underlying geometry smoothed to more closely approximate a sphere. Figure 4 shows the texture mapping for the TOAST projection, again with the underlying geometry smoothed to more closely approximate a sphere.