Projects/Edu/KStars/MillionStars Design

Design Document for the "Million Stars" Project in KStars

This is essentially a distilling of email discussions between James and Akarsh. The emails tended to be long and tended to focus on small parts of the design at one time. There was no document describing the entire design, so this is an attempt to provide such a description.

The basic premise of the project is that we are going to increase the number of stars displayed in KStars from 130,000 to about 1 million (and maybe more). To accomplish this without severely impacting on the performance of the program, we will need to dynamically load stars into memory only when they are on-screen, and off-load stars after they have moved offscreen. In addition, we will store the star data on-disk in a binary format that will be much faster to read into memory than parsing 1 million lines of ascii text. Also critical is that faint stars will only be displayed above a threshold zoom level, so that we never need to load a very large number of stars at once.

We are already using some code called a "hierarchical triangular mesh" (HTM) which divides the sphere of the sky into triangular subregions ("trixels"), and allows for very fast determination of which trixels are on-screen. We are using a mesh that divides the sky into 512 trixels.

Note that since bright stars are the only ones drawn at low zoom levels, the bright stars don't need to be split into HTM trixels. We will keep a separate list of the brightest 50,000 stars (to mag=8.0) that are always in memory. These are called the "global stars".

There are complications with named stars, stars with high proper motion, and "extra info" for unnamed stars that I am not dealing with in this document (yet!)

Classes needed for this project:

StarBlock: Contains an array of N(=100?) stars (i.e., StarObjects), from a single HTM trixel.

StarBlockList: A list of StarBlocks. Each trixel has its own StarBlockList, and it contains a dynamic number of StarBlocks (zero if the trixel is off-screen and not cached, up to the number needed to hold all stars in the trixel between mag 8.0 and the current faint limit for stars).

StarBlockCache: a Least-Recently Used (LRU) cache containing pointers to the currently active, and recently-used StarBlocks, in all trixels. We allocate memory for a certain number of StarBlocks, then fill them as needed with "active" StarBlocks (i.e., from on-screen trixels). When the cache is filled, we need to delete a StarBlock for each new one that we need to add. We always delete the least-recently used StarBlock, to minimize the number of disk reads.

Overall Design:

Globally, we will have a single array of StarBlockLists, indexed by trixel ID. This will probably be a member of StarComponent. There will be one StarBlockCache, probably also a member of StarComponent.

StarBlockList will be in charge of reading data from the binary data files. It will need to understand where to seek in the file to begin and end a particular read.

StarBlockCache will have two functions named markFirst() and markNext(), which ...

Outstanding Issues:

These are some things that I (Jason) don't understand from my reading of the emails; James or Akarsh should fill in the answers to these issues.

• Do the bright/named stars go into StarBlocks as well, or are they kept in the current structure of StarIndex/StarList ? I think it's the latter, but I may have old information.

• Are we still considering loading the entire binary data file into memory, and dynamically parsing it as needed, or will we read chunks of the file from disk as the StarBlockLists need them?

• What happens to the last StarBlock in a trixel, which will be partially filled 99% of the time?