[Kstars-devel] Some HTM progress

[James Bowlin]

I've gotten the C++ code working.  It passed the tests in the makefile so I 
think it is working properly.  With the aid of the new doc pages I've been
able to piece things together.  To index our HIP data (126K stars) would 
take roughly:

Levels Triangles Resolution   Indexes/sec  Time for HIP catalog
------ --------- ------------ -----------  --------------------
  14     500 Meg  30 arc-secs  20K          6 seconds
  20    2000 Gig .01 arc-secs  17K          7 seconds

The timing was done on a 1.6 GHz P4 processor.  It was done by repeatedly
looking up the same point.  It is possible some points will be much quicker
or slower than others.

Let's look at the number of stars/triangle as a function of level:

Level   triangles stars/triangle
-----   --------- --------------
   1       8         16k
   2      32          4k
   3     128          1k
   4     512        250
   5       2k        64
   6       8k        16
   7       32k        4
   8       128k       1
   9       512k       1/4
  10      2,048k      1/16


I was also able to get a sample program working that returns a list of
triangles that cover a "rectangle" specified by 4 input points.

I am not sure what to do next.  My inclination would be to cobble together
a little app that would read in the HIP files, index them and then be able
to return a list of stars within any given rectangle.  I think we would 
want to tell this app the average or approximate number of stars per 
rectangle we want given back so when we zoom out, only the brightest N
stars are shown.  With one big list this is trivial.  With multiple lists
(one per triangle) the best strategy is not clear to me.  I don't think
we want to sort them all together because we don't want to pay N log N
at this point.  It would probably be better to go through the lists in
a round robin fashion starting with the brightest from each triangle.

This then brings up the question: how many triangles per screen do we
want to use?   More triangles per screen means the triangles are a closer
approximation to the shape of the screen and hence there will be fewer
outliers but this comes at the cost of having to deal with more lists
at once.  Also, we probably don't want to populate every level with
pointers to stars unless we can truncate the lists at the courser levels.

If we populate X different levels then if we have to move an object, it
will need to be moved X times, once for each level that is populated.
This leads me to think that the HTM should be used for "fixed" stars
and objects.  Closer things that move should be treated separately.
It could be that an HTM is used for fast moving objects as well but
it would probably not be optimized in the same was as the one for the
stars.  So I will concentrate on thinking about an HTM for the "fixed"
stars for now.

This is an interesting problem.  There are a lot of trade-offs, like
designing a sailboat.


-- 
Peace, James