Difference between revisions of "Projects/Edu/KStars/MillionStars Design"

< Projects‎ | Edu‎ | KStars
Jump to: navigation, search
(New page: ===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...)
 
(Classes needed for this project:)
Line 16: Line 16:
 
'''StarBlock''': Contains an array of N(=100?) stars (i.e., StarObjects), from a single HTM trixel.
 
'''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 all of the stars that exist in that 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 LRU cache containing the currently active, and recently-used StarBlocks.
+
  
 +
'''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.
  
 
Globally, we will have a single array of StarBlockLists, indexed by trixel ID.  This will probably be a member of StarComponent.
 
Globally, we will have a single array of StarBlockLists, indexed by trixel ID.  This will probably be a member of StarComponent.

Revision as of 02:08, 9 June 2008

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.

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


KDE® and the K Desktop Environment® logo are registered trademarks of KDE e.V.Legal