[Kstars-devel] Some HTM progress

[Jason Harris]

Hi James,

James Bowlin wrote:
> I've gotten the C++ code working.  
Great!

> 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
> 
Interesting numbers, but I don't understand the "Triangles" column.

> 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 guess there's no point going deper than 8 levels.  Probably 4 or 5 
levels would be fine.

> 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.
> 
Excellent.  Another (perhaps faster) option is to use the HTM primitive
that they call a "Constraint"; i.e., the intersection of a plane with 
the sphere.  This gives a circular cross-section, which we will choose 
to be superscribed on the rectangle of the skymap widget.  For this, all 
we need is the position of the Focus point, and the angular size of the 
Skymap's diagonal.  What do you think?

> 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.
> 
Hmm, even that seems like it would be slow.  In the current code, the 
stars list is sorted by magnitude (bright to faint), and we simply stop 
looping through the stars when we reach the (zoom-dependent) faint 
limit.  We can do the same with the multiple lists, can't we?  Since 
they'll be populated by reading the hip*.dat files (which are sorted by 
magnitude, each triangle's star list will be naturally sorted by 
magnitude.  We can just loop over each until the faint limit is reached.

> 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.
> 
I don't know what you mean by "triangles per screen".  The number of 
triangles is fixed to the sphere; the number on-screen will change with 
zoom level.  I think we should just pick the number of levels that makes 
sense for the number of objects we're dealing with.  The fact that parts 
of triangles will extend beyond the boundaries of the Skymap rectangle 
is not a big deal.  Compared to what we've been doing to this point, 
being able to skip large fractions of the objects is going to be a huge 
leap.

> 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.

Really?  The way I was imagining it, only the "last" level (i.e., the 
smallest triangles) would actually contain lists of objects.  "Parent" 
triangles would simply refer to the lists of their children.  Like this:

class Triangle {
public:
   TriangleBase( int _id );
   ~TriangleBase();
   int id() const { return m_ID; }
   bool isLastLevel();

   virtual QList<StarObject*> starList();
   void addStar( StarObject *s );
};

Triangle::starList() would return the Triangle's list of stars, if it is 
on the last level.  If it is not, then starList() will return the 
starList()'s of all last-level triangles contained within the Triangle.
isLastLevel() should be a trivial matter of parsing the ID number, as 
will determining the last-level triangles that this Triangle contains.

> 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.
> 
Yes, I was thinking about that too.  We'll have to figure out how 
expensive it is to move objects between triangles.  I agree, let's 
concentrate on the fixed stars for now.  There's also the question of 
what to do about objects that will span many triangles (the Mlky Way, 
constellations).

> This is an interesting problem.  There are a lot of trade-offs, like
> designing a sailboat.
> 
Glad you are enjoying it, I am too :)  Now all we need is some code to 
chew on :)

By the way, something we should consider while thinking about all of 
this is the new class QGraphicsView that is going to be introduced with 
Qt 4.2.  It looks like it will be quite useful, and I am planning on 
porting SkyMap to QGraphicsView when the time comes.  It does its own 
bsp-tree based clipping algorithm, but AFAIK, it can't handle spherical 
coordinates, so the HTM will still be needed.  Check it out:

http://blogs.qtdeveloper.net/archives/2006/05/01/a-graphicsview-sneak-peek/

Short version:
* Can easily switch between OpenGL and normal rendering
* Items to be drawn are stored in an internal tree (this might actually 
hurt us, since we'll have to be continuously be repopulating this 
tree...I'm half-hoping that we'll be able to subclass QGraphicsView and 
replace the bsp clipping code with our HTM tree.

regards,
Jason