Warning, /education/kstars/kstars/skycomponents/stars.dox is written in an unsupported language. File is not indexed.

0001 /*! \page Stars Stars    
0002   \tableofcontents
0003   Design document for the implementation of star catalog support in KStars.
0004   \section StarsClassInheritance Class Inheritance
0005   + StarComponent - Manages all stars
0006       - struct starName - Holds a star's names (defined within StarComponent)
0007   + DeepStarComponent - Manages unnamed stars (instances managed by StarComponent)
0008   + StarBlock - A block of many (usually 100) stars
0009   + StarBlockList - A list of StarBlocks; machinery to load data dynamically from catalog files
0010   + StarBlockFactory - Maintains a cache of recently used StarBlocks
0011   + BinFileHelper - A generic helper class used to deal with binary data files (See ../binfilehelper.h)
0012   + StarData - holds 32 bits of data describing a star (See ../skyobjects/stardata.h)
0013   + DeepStarData - holds 16 bits of data describing a (faint) star (See ../skyobjects/deepstardata.h)
0015   \section Categorization Categorization of Stars
0016   Stars could be either named or unnamed. Named stars and unnamed stars
0017   are treated differently in KStars. Stars having names are handled by
0018   the methods defined in class StarComponent. Unnamed stars are handled
0019   by the methods defined in class DeepStarComponent, which are invoked
0020   via the methods of StarComponent.
0022   A second categorization is "static" and "dynamic" stars. The
0023   StarObjects for "static" stars are always kept in memory. They are
0024   loaded into memory when KStars initializes. "Dynamic" stars are loaded
0025   into memory from the disk when required. When the sky map is slewed to
0026   a new region, or zoomed to a greater depth, dynamic stars are loaded
0027   "on-demand" into memory from the disk and drawn. Named stars are
0028   always static. Unnamed stars could be either static or
0029   dynamic. Naturally, StarComponent deals only with static stars whereas
0030   DeepStarComponent deals with both static and dynamic stars.
0032   A third categorization is "shallow" and "deep" stars. Shallow stars
0033   are the brighter stars, which have enough catalog data to require a
0034   32-byte data structure (StarData) to hold them. Deep stars are the
0035   fainter ones, data for which can be fit into a 16-byte structure
0036   (DeepStarData). All named stars and all static stars are shallow. All
0037   deep stars are dynamic and unnamed. StarComponent manages only shallow
0038   stars. DeepStarComponent manages both shallow and deep stars.
0040   Stars are indexed using \subpage HTMIndexing "multi-level Hierarchical Triangular Mesh" to speed
0041   up drawing and searching for stars in the skymap.
0043   Stars are stored in a custom \ref BinaryFormat Binary Format to speed up reading and loading of data into memory.
0045   \section Catalogs Catalogs
0046   As of this writing, KStars supports the following catalogs:
0047   1. Default named stars catalog ("namedstars.dat" in the data directory)
0048      [Together with default unnamed stars catalog, makes up all stars to mag 8]
0049        + Named
0050        + Static
0051        + Shallow
0052        + Managed by StarComponent's methods
0053        + Names of stars stored in "starnames.dat" in the data directory,
0054          in order of appearance in namedstars.dat
0056   2. Default unnamed stars catalog ("unnamedstars.dat" in the data directory)
0057      [Together with default named stars catalog, makes up all stars to mag 8]
0058        + Unnamed
0059        + Static
0060        + Shallow
0061        + Managed by DeepStarComponent
0063   3. Tycho-2 catalog (Downloadable add-on)
0064      Prerequisite: Default catalogs (namedstars.dat, unnamedstars.dat and starnames.dat)
0065        + Unnamed
0066        + Dynamic
0067        + Shallow
0068        + Managed by DeepStarComponent
0069        + Reside on a level-3 \subpage HTMIndexing HTMesh
0070        + Down to mag ~12
0072   4. USNO NOMAD (part) 100 million star catalog (Downloadable add-on)
0073      Prerequisite: Tycho-2 catalog
0074        + Unnamed
0075        + Dynamic
0076        + Deep
0077        + Managed by DeepStarComponent
0078        + Reside on a level-6 \subpage HTMIndexing HTMesh
0079        + Down to mag ~16
0081   \section NamedStars Named Stars
0082   Named Stars are dealt with by StarComponent. Their case is very simple
0083   because they are all static stars. The star names are stored in a
0084   separate file (starnames.dat), in which the names are maintained in
0085   the same order in which stars appear in the named star catalog
0086   (namedstars.dat). Both files are opened while reading (See
0087   StarComponent::loadStaticData()) and data is read off from the two
0088   files sequentially, side-by-side.
0090   Each record in starnames.dat is 40 bytes long, containing a long name
0091   (32 bytes) and a Bayer designation (8 bytes).
0093   Each record in namedstars.dat is 32 bytes long, and holds a direct
0094   memory dump of struct StarData, made on a little-endian system. (On
0095   big endian systems, byte order inversion is done at runtime)
0097   Named stars are read off the disk at initialization time by
0098   StarComponent::loadStaticStars() and are drawn by the loops in
0099   StarComponent::draw(). All of them reside in the memory throughout
0100   KStars' life.
0102   \section UnnamedStars Unnamed Stars
0103   Much of the machinery listed out above go into maintenance of unnamed
0104   stars.
0106   Unnamed stars are dealt with by DeepStarComponent.
0108   StarComponent has a QVector of DeepStarComponent objects, which are
0109   created for each unnamed-star catalog loaded. (See
0110   StarComponent::loadDeepStarCatalogs().) StarComponent takes
0111   responsibility to call methods of the DeepStarComponents when
0112   required. For instance, StarComponent::draw() calls
0113   DeepStarComponent::draw() on each catalog, after drawing the named
0114   stars. (StarComponent, on the other hand, is managed by
0115   SkyMapComposite)
0117   \subsection MemoryMap Memory map
0118   Memory map of unnamed stars:
0119   + StarComponent
0120   + One DeepStarComponent for every catalog
0121   + One StarBlockList for each trixel
0122   + StarBlockFactory churns out StarBlocks
0123   + Several StarBlocks are attached / detached dynamically to a StarBlockList
0124   + Several StarObjects (usu. 100) in a StarBlock
0125   \subsection Loading Loading unnamed stars
0126   As mentioned earlier, unnamed stars may be both static and dynamic,
0127   and could be both deep and shallow.
0128   \subsubsection Creation Creation of unnamed StarObjects
0129   TODO: This is outdated. Stars are now created differently.
0131   IMPORTANT: Unnamed stars, for fast loading, are not constructed!!!
0132              They are allocated in memory (using malloc) and data is
0133              copied directly (using memcpy) onto them.
0134              This can lead to very strange segfaults with misleading
0135              backtraces if not understood carefully.
0137   For each record read off the data file, a StarObject instance
0138   (plainStarTemplate) is loaded with the data using
0139   StarObject::init(...) and then memcpy()'d and held in a StarBlock
0140   \subsubsection LoadingStatic Loading unnamed, static stars
0141   The method DeepStarComponent::loadStaticStars() (invoked from
0142   StarComponent) loads all static stars in an unnamed-star catalog.
0144   The star data files are organized trixel by trixel. The method enters
0145   each trixel, creates a StarBlock of variable size, enough to hold all
0146   the unnamed stars in the current trixel, and then reads star-by-star
0147   into memory.
0149   Static stars always occupy the first StarBlock in a StarBlockList.
0150   \subsubsection LoadingDynamic Loading unnamed, dynamic stars
0151   Dynamic stars are loaded on-demand (during the draw() call) in
0152   StarBlockList::fillToMag().
0154   NOTE: This can be a problem for objectNearest(). objectNearest() calls
0155   work correctly only when the sky map is centred on the required
0156   trixel(s). For extending this when required, one must call
0157   StarBlockList::fillToMag() from objectNearest()
0159   fillToMag() is invoked by DeepStarComponent::draw(), for every trixel
0160   present on-screen, with the current magnitude limit (calculated from
0161   the zoom level) as an argument. fillToMag()'s job is to ensure that
0162   the StarBlockList is filled with stars up to that magnitude by loading
0163   more stars from disk if required.
0165   An important point to note is that StarBlockList maintains stars
0166   sorted by magnitude - brightest first - to match the data
0167   file. StarBlocks at the "tail end" of the StarBlockList are the
0168   faintest. fillToMag() quickly checks the magnitude of the last star in
0169   the last StarBlock of the StarBlockList and starts filling into the
0170   last StarBlock.
0172   Each StarBlockList maintains the current read offset in the data file,
0173   so that it can quickly seek to the point where it last loaded and
0174   continue loading fainter stars. When stars are removed from a
0175   StarBlockList, the read offset is decremented.
0177   StarBlocks holding dynamic stars are always of fixed size
0178   (default=100). There could be half-filled StarBlocks. (We save
0179   allocation overhead by recycling StarBlocks using
0180   StarBlockFactory. More about this later.) StarBlockList::fillToMag()
0181   is aware of this fact and continues to fill half-filled StarBlocks
0182   when required.
0184   \subsection Recycling Recycling of StarBlocks
0185   StarBlockFactory maintains a Least-Recently-Used cache of "dynamic"
0186   StarBlocks (which hold dynamic stars).
0188   When StarBlockList::fillToMag() asks for new star blocks,
0189   StarBlockFactory sees if there are unused (trixel not-on-screen)
0190   StarBlocks lying around. If there are none, it allocates a new
0191   StarBlock and hands it over to StarBlockList. But if there are unused
0192   StarBlocks lying around, StarBlockFactory recycles them.
0194   Imagine a situation where the map is panned. A trixel that was
0195   on-screen till now might no longer displayed on the screen, but a new
0196   trixel might come into focus. In this case, StarBlockFactory detaches
0197   the StarBlocks attached to the StarBlockList of the old trixel and
0198   gives them to the StarBlockList of the new trixel. The new data read
0199   off the disk is then StarObject::init()'ed into the StarBlock.
0201   Each draw cycle in KStars has a drawID that is incremented upon every
0202   draw. This makes the drawID almost unique, since it has a very large
0203   period. StarBlockFactory has a local copy of this drawID that is
0204   maintained in sync with KStars' drawID. When stars are drawn in
0205   StarComponent::draw(), every dynamic StarBlock that's drawn is
0206   "touched" by calling StarBlockFactory::mark*().
0208   When drawing a trixel, markFirst() is called on the first StarBlock in
0209   every StarBlockList and markNext() is called on subsequent ones. The
0210   freshest StarBlocks are maintained at the beginning of the linked list
0211   inside StarBlockFactory and equally-fresh StarBlocks are ordered in
0212   the same order as they appear in StarBlockList. Thus, StarBlockFactory
0213   can safely pluck out the last StarBlock in the linked list and recycle
0214   it (provided it was last touched in an older draw) without affecting
0215   the ordering of stars in StarBlockList (i.e. we ensure that we don't
0216   pluck out a StarBlock from in-between a StarBlockList. Only the last
0217   StarBlock of a StarBlockList can be released at any time). Thus, the
0218   ordering of StarBlocks in the linked-list of StarBlockFactory, is:
0219    + First, by drawID
0220    + Then, by catalog (i.e. unnamedstars.dat / Tycho-2 / USNO-NOMAD-1e8)
0221    + Then, by trixel (only those trixels that are on-screen are considered)
0222    + Finally, by magnitude
0224   When StarBlockFactory wants to re-use a StarBlock, it first verifies
0225   that the drawID is outdated. Then, it calls
0226   StarBlockList::releaseBlock() on the parent StarBlockList and thus
0227   orphans the StarBlock. The orphaned StarBlock is handed over to the
0228   new StarBlockList which adopts it.
0230   Thus, KStars initially allocates new StarBlocks until a saturation
0231   point is reached, where there are enough StarBlocks to keep
0232   recycling. Sagittarius has the maximum number of stars, and setting
0233   the focus on Sagittarius will usually lead to saturation (where KStars
0234   consumes 200-odd MB of memory with USNO-NOMAD-1e8), and this memory is
0235   not freed till KStars exits. A possible extension would be to free
0236   StarBlocks lazily after their drawID's get really outdated, so that
0237   the memory surge is temporary.
0239   \subsection Files Star Catalog Files
0240   Star catalogs are stored in the format described in \ref BinaryFormat Binary Format section.
0242   Star catalog files were created by first taking ASCII data and putting
0243   them into MySQL database tables and then dumped in a sorted manner
0244   into the catalog files. The tools used are in ../data/tools. The ASCII
0245   originals from public domain sources are available with Akarsh Simha
0246   and Jason Harris, or with the US Naval Observatory itself.
0248   Stars in the catalog files are first ordered by trixel (the "Index"
0249   parameter in binary file format) and then ordered by magnitude (brightest first) within each trixel.
0251   KStars uses two HTM levels:
0252    + Level 3: 512 <a href="http://www.skyserver.org/htm/">trixels</a> are used for the following data files:
0253         -# default namedstars.dat
0254         -# default unnnamedstar.dat: Togeather with #1, they make up all stars up to ~8th magnitude
0255         -# Downloadable Tycho-2 deepstars.dat, all stars up to magnitude ~12th
0256    + Level 6: 8192 trixels
0257         -# Downloadable USNO Nomad USNO-NOMAD-1e8.dat, all stars up to magnitude ~16th
0259   \subsection ProperMotion Proper Motion
0260   All star data in KStars has first order proper motion rates (called
0261   "dRA" and "dDec" or "pmRA" and "pmDec"), which are used to correct for
0262   proper motion.
0264   This leads to a problem in the case of dynamic stars, as a star may
0265   cross over from one trixel to another trixel due to proper motion, in
0266   which case it might not be drawn despite its corrected coordinates
0267   being on-screen.
0269   To solve this, stars are duplicated in all trixels that they will pass
0270   through in a span of +/-10,000 years from the epoch. StarObject has
0271   some commented code that can be used to track the position of a
0272   star. [Maybe this should be turned into a feature in future]
0274   TODO: Describe details like the 25 arcminute "safety" margin.
0276   \section HDCatalog Henry-Draper Catalog Numbers
0277   StarObject allows for a Henry-Draper catalog number to be associated
0278   with a star. KStars allows for both static and dynamic stars to have
0279   an associated catalog number. This is currently used for the
0280   Henry-Draper number, although it could be extended to other catalogs.
0282   Both static and dynamic stars from Tycho-2 appear in the HD
0283   catalog. To find dynamic stars by HD number, a downloadable add-on
0284   "Henry Draper Index" is available. This file contains a list of 4-byte
0285   offsets in sequential order of HD number. These offsets tell KStars
0286   where to find the star in the Tycho-2 catalog binary data file. See
0287   StarComponent::findByHDIndex() for details. See \ref HDIndex HDIndex section for details about the format followed
0288   by the Henry-Draper index file.
0290   FIXME: The information above is not entirely correct. Star catalogs also include 4-byte HD parameters. Needs update.
0292   \section BinaryFormat Binary Format
0294   Stars data are stored in binary format to speed up reading and loading data into memory. There are a number of tools in the data/tools directory that parses the original ASCII data files and convert them to a KStars compatible binary format.
0296   \subsection Header The Header
0297   \subsubsection Preamble Preamble
0298   The preamble consists of the following:
0300  * A 124 byte-long string containing human-readable information about
0301    the file
0303  * A 2 byte-long endinanness indicator field, preinitialized to 'KS'
0304    (0x4B53) on the host machine
0306  The purpose of the endianness indicator is to make the file portable
0307  across machines of different endianness. A machine on which the
0308  endianness indicator field is read as 'SK' instead of 'KS' is of
0309  different endinanness from the machine on which the file was
0310  generated, and hence byteswapping must be performed.
0312  * A 1 byte-long unsigned integer for the version of the binary format structure.
0314  The header section is therefore 127 bytes long. The header range in the binary file is from address 0x0000 to 0x007E
0316  \subsubsection FieldDescriptor Field Descriptor
0317  The field descriptor describes the various fields used in the latter
0318  half of the data region. The field descriptor consists of the
0319  following:
0321  * A 2 byte-long unsigned integer, indicating the number of fields per
0322    record
0324  * A set of entries describing the fields, amounting to the number
0325    previously mentioned, each consisting of:
0327      - A 10 byte-long character array, providing a human-readable name
0328        for the field
0330      - A 1 byte-long integer carrying the size of the field in bytes
0332      - A 1 byte-long unsigned integer carrying the data type (see
0333        Appendix A)
0335      - A 4 byte-long integer storing a scale factor to divide the
0336        contents of the associated field by, to interpret it
0337        correctly. This is used for storing fixed-point fields. (Eg: A
0338        fixed-point number with 2 decimal places would have a scale
0339        factor of 100)
0341   The set of entries is read directly into dataElement structure and byte swapping is performed if needed.
0343   Most of KStars star binary files use 11 fields (0x0B), each is 16 bytes long (0x10). Therefore, the field descriptor
0344   total bytes count is 2 + 11 * 16 = 178 bytes. The field descriptor range in the binary file is 0x007F to 0x0130
0346   \subsubsection IndexTable Index Table
0347    The format permits an index on one parameter. This index is the trixel ID.
0348    The parameter is to be represented by 4-bytes (eg: A running index from 0 to 4,294,967,295). The index table consists of the following:
0350  * A 4 byte unsigned integer indicating the number of index entries: Usually 512 (0x0200) or 8192 (0x2000)
0352  * Index table entries, each consisting of:
0354      - A 4 byte-long unsigned integer parameter, which is the index: 0 to 511 for HTM level 3, and 0 to 8191 for HTM Level 6
0356      - A 4 byte-long unsigned integer, storing the offset of the first record with this index parameter in the file
0358      - A 4 byte-long unsigned integer, storing the number of records under this index parameter.
0360   Since multiple stars can share the same trixel ID, the number of records refer to the number of the stars enclosed within the trixel.
0362   The index table total byte count depends on the index entries:
0363   + HTM Level 3: Total bytes = 4 bytes + (512 indexes * 12 bytes) = 6148 bytes (0x1804)
0364     The index table range in the binary file is 0x0131 to 0x1934
0365   + HTM Level 6: Total bytes = 4 bytes + (8192 indexes * 12 bytes) = 98308 bytes (0x18004)
0366     The index table range in the binary file is 0x0131 to 0x18134
0368   \subsection TheData The Data
0370   \subsubsection ExpansionFields Expansion Fields
0371    Certain specific information about the contents of the field may be
0372  added here. The contents could be specific to each application, and
0373  could be empty. For KStars star data files, the entries in this
0374  region are:
0376    + Faint magnitude limit * 100, stored as a 16-bit integer
0378    + HTM Level for this file, stored as a 8-bit integer. The
0379      convention followed is that "N0000" would belong to a HTMesh of
0380      level 3.
0382    + Maximum Stars per Trixel, stored as a 2-byte unsigned integer.
0384    The expansion field total bytes are (2 + 1 + 2) 5 bytes long.
0386    + HTM Level 3: The range is from 0x1935 to (0x1935 + 0x5) = 0x1939
0387    + HTM Level 3: The range is from 0x18135 to (0x18135 + 0x5) = 0x18139
0389    \subsubsection DataRecords Data Records
0390    This region starts at the offset pointed out in the first entry of
0391  the index table. The data consists of a series of records, the
0392  details of whose fields (assumed to be placed continuously, without
0393  any gaps) are as described in the field descriptor in the header.
0395   + HTM Level 3: Data starts at 0x193A
0396   + HTM Level 6: Data starts at 0x1813A
0398  NOTE: KStars _overrides_ the above defined convention for performance
0399  gains and ease of programming in the star names file, where records
0400  are stored as single blocks of the 40 bytes long StarComponent::starName structure.
0402  \section HDIndex Henry Draper Indexing
0403 The index file used to store the Henry Draper catalog indexes for KStars is just a list of 4-byte long offsets (to be treated as signed 32-bit
0404 integers ) describing the position of the Henry Draper stars' records in order, in the binary data files.
0406 If the offset is negative, it indicates that the star is in the shallow star file and not in the Tycho-2 deep star add on. The actual
0407 offset in this case is just the absolute value of the offset. The first four bytes in the index file correspond to the offset of the
0408 star HD000001 in the data files, and so on.
0410 \section Credits Credits
0411   Most of the memory layout and machinery outline described above was
0412   the brainchild of James Bowlin and it was implemented in code by
0413   Akarsh Simha. Jason Harris helped with the catalog data and also
0414   mentored Akarsh along with James. Some of the parsing tools in the
0415   kstars/data/tools directory have code due to James.
0417 \author Akarsh Simha
0418 \author Jasem Mutlaq
0419 */