[Kstars-devel] Ideas for Adding a Spatial Index to KStars

[James Bowlin]

Here are my ideas on how to add a spatial index to KStars.  This is not
meant to be the last word on the subject, but rather the first.  I hope
this can be a starting point for a discussion on what is the best way to
add a spatial index.

My plan involves creating two new classes: SkyIndex and SkyRegion. It then
requires some changes to our SkyComponent classes.  I've tried to keep the
changes small and simple yet give us the ability to have KStars draw things
as fast as possible.

I first introduce the two new classes and then discuss the changes needed
in our SkyComponent classes.


SkyIndex Class
--------------

SkyIndex is the KStars wrapper for the actual spatial indexing code.  The
underlying indexing code performs one very simple job: it converts [Ra, Dec]
coordinates into integer indices.  It can return a single index given a point
or a list of indices if given a region in the sky.  

The SkyIndex (there will almost always be just one) contains an array (or
QList) of SkyRegions.  Instead of returning integer indices, the SkyIndex
returns lists of (pointers to) SkyRegion's by simply using the indices
returned by the underlying spatial index to index the array of SkyRegions.

The SkyIndex constructor just needs the initialization parameters for
the underlying index and enough information to know the number of SkyRegions
to put in its array.  An HTM index usually just needs a single integer, the
level of the index.  The number of regions is 8 * 4**level.  

The SkyIndex methods generally take [ra, dec] coordinates as input and
return SkyRegions or iterators of SkyRegions:

    SkyRegion* indexPoint( SkyPoint *p );
    SkyRegion* indexPoint( double ra, double dec );
    SkyRegion* indexToRegion( int index );
    SkyRegion* nameToRegion( QString name );

    QList<SkyRegion *> indexCircle( SkyPoint *p, double radius );
    QList<SkyRegion *> indexPolygon( QList<SkyPoint*>& pointList );

    void setView( SkyPoint *p, radius );
    QList<SkyRegion *> getView( );

    QList<SkyRegion *> allRegions(); 

Notes:
 1) I don't know if the QList<> syntax above is correct.  Even if it is
    correct I'm not certain a QList<> is the best structure to use here.
    The key point is that these routines return iterators that return
    SkyRegions.

 2) I've resisted the temptation to have any add() methods in SkyIndex
    that would combine looking up the index of an object and adding that
    object to a SkyRegion in one step.  The SkyIndex doesn't know anything
    about what is in the sky expect for the SkyRegions it returns and the
    SkyPoints it gets sent that contain the [ra, dec] coordinates it needs
    to find the regions.

 3) I don't know if the "index" prefix is the best name for the routines
    above.  Other possibilities are "find", "findIndex", and "intersect".
    I welcome suggestions for what to name things.

 4) The setView() and getView() functions do the same things as the
    indexCircle() function but in two separate steps.  The idea is that
    setView() would be called once to generate a list of all regions
    that are at least partially visible on the screen then the SkyComponents
    would all call getView() to get a list of all the objects they need to
    draw.  


SkyRegion Class
---------------

The SkyRegion class is a simple container for all of the objects that are
in a particular region in the sky.  Objects that move a lot need to be
treated differently from objects that don't move very much.  Here, I will
concentrate on objects that don't move very far.  For the moment, let's
assume the objects in our SkyRegions don't move at all.  We will deal
both slow and fast motion elsewhere.

The SkyRegion doesn't need any code, just public lists of the objects it
contains.  Things that don't move, or move slowly are in QLists and things
that move quickly are in QLinkedLists.

public:
    QList<StarObject> stars;
    QList<MilkywayComponent *> milkyway;
    QList<ConstellationLineComponent *> constellationLines;
    ...

    QLinkedList<SolarSystemComponent *> ????;
    ...

Notes:
 1) I realize it is unusual to have public data members.  If you would
    prefer, we can add public accessors for all of these data members
    but I don't see that we would gain anything by doing that.

 2) The lists don't need to be the same.  In the example above the stars
    member is a list of actual StarObject objects while the others are
    lists of pointers.  The SkyRegion is just a container.  All the lists
    can be different. Each component can use a list that best suits its
    needs.

 3) When we add a new component to the spatial indexing system, the only
    change to the indexing code will be the addition of a new list to the
    SkyRegion class.

One drawback I see with this approach is that it will create a little header
file hell.  The SkyRegion header depends on the SkyComponent headers of all
the SkyComponents it contains.  But all of those SkyComponents will depend
upon the SkyRegion header thus a change to any one of these header files will
cause all of the indexed SkyComponents to need to be recompiled.  We could
get around this by using void* pointers and a lot of type casting but I don't
think that is a good idea here.


Putting it all together
-----------------------

There are two major operations the spatial index is involved with: adding
objects to the index and the drawing of objects.  It could also be useful
for finding objects near the cursor, or all the objects on the screen but
those operations are simpler than drawing (I think) and their implementation
should be obvious.

Every indexed SkyComponent class will need to know about SkyRegions and
also needs to contain a pointer to the SkyIndex.  I think the simplest
thing is to have the SkyIndex pointer be a static class member in the
SkyComponent classes.


Adding objects to the index
---------------------------

The code to add an object to the index, like most of the other code that
uses the index, would reside inside the SkyComponent cpp file for that
particular kind of object.  For example, the current code for creating
a new StarObject is:

    StarObject *o = new StarObject( ... );
    o->EquatorialToHorizontal( data()->lst(), data()->geo()->lat() );
    objectList().append( o );

This would change to something like:

    StarObject *o = new StarObject( ... );
    o->EquatorialToHorizontal( data()->lst(), data()->geo()->lat() );
    SkyRegion *region = skyIndex->indexPoint( o->ra(), o->dec() );
    region->append( o );

We had previously discussed having the index for every star stored directly
in the hipNNN.dat files.  This would just require changing the indexPoint()
call above to an indexToRegion() or nameToRegion() call.  

The changes to add an extended object are a little more complicated but
not too bad.  Here is the existing (single line of) code for adding a 
ConstellationLinesComponent:

    if ( clc ) addComponent( clc );

This would be changed to:

    QList<SkyRegion *> regions;
    ...
    if (clc) {
        regions = skyIndex->indexPolygon( ( clc->pointList() );
        foreach ( SkyRegion *region, regions ) {
            region->constellationLines.append( clc );
            ConstellationLinesComponent::addComponent( clc );
        }
    }

Notes:
 1) addComponent() is actually called in two places so we would need to
    either repeat the code above or put it in a little subroutine that
    is called twice.

 2) Storing the regions that correspond to a polygon is slightly more
    complicated than storing the single region for a star mainly
    because there is not a one-to-one correspondence between the number
    of vertices and the number of regions.  But this is not a fundamental
    or insurmountable problem.

I added a static class method addComponent() to the above implying that
there would be a static class QList that would contain a list of all of
the ConstellationLinesComponents (clc) created.  This would probably be
more appropriately located in the constructor.  I'm not certain we need it.
It would provide us with a single list of all of the clc's created. We
can't quite get this from a list of all the SkyRegions because each clc
can be in more than one SkyRegion.  There is at least one other way
for dealing with this problem that does not require the static class
QList of all the objects created.


Drawing objects with the index
------------------------------

The changes to the current code for adding objects to the index are pretty
simple.  It's just a few extra lines for every type of thing that get
added to the index and one additional list in the SkyRegion class.  But the
changes to the drawing are a bit more fundamental.  I want to implement a
structure that gives us the efficiencies of the current StarComponent code
but otherwise keeps things as object oriented as possible.  The plan for
making things draw as fast as possible is very simple:  move all unneeded
code and control flow out of the innermost drawing loops.

At first I thought this could be done by creating static class methods
preDraw() and postDraw() for each SkyComponent that would deal with
all of the psky.setPen(), etc. calls.  Unfortunately for both the
StarComponent and the MilkyWayComponent this simple change will not suffice.

First of all there are local variables (like QPointF's) that need to be
used for drawing each object.  We want to declare these variables outside
the innermost draw loops instead of declaring them for every object drawn.
Second, both the Milky Way and the stars have more than one kind of drawing
that needs to be done.  The StarComponent needs to draw both the stars and
their labels.  The MilkyWayComponent needs to be able to draw both the
filled and outlined Milky Way.

We certainly don't want to store redundant data just to make our code
more "object oriented" so we have two situations here where a given
component needs to have more than one draw routine.  I think the cleanest
way to solve this problem is to make a static class draw() (or drawAll())
routine for every component.

The biggest "downside" I see to this approach is that it means we will once
again need a list of all the things we need to draw:

  drawEverything() {
      StarComponent::drawAll();
      MilkyWayComponent::drawAll();
      ...
  }

(We may also need a similar looking piece of code to initialize all the
SkyComponents but I'm not sure).

I put downside in quotes above because this is moving complexity out of our
inner loops and into our outer loops which is where we want it.  Of course,
things that aren't in the index would still be drawn the way they are currently
being drawn.

One benefit of this approach is that each component is free to have its
own level of optimization.  For example, every component's draw() method
contains two different drawing calls: an integer one and an anti-aliased
one.  Some components can have two separate draw loops, one for the integer
draws and another for the anti-aliased draw while other components
can have a single draw loop with an if () .., else inside it to switch
between integer and anti-aliased drawing which is less efficient but often
takes less coding.

The SkyComponent code that would change the least when adding the spatial
index is the StarComponent because it already contains the loop over all
stars in its draw() routine.  It actually has two loops, one for drawing
the stars and another for drawing the labels.  The changes to the two
loops would be the same.  The current code is:

    foreach ( SkyObject *o, objectList() ) {
        StarObject *curStar = (StarObject*)o;
        ...
    }

This would be changed to two nested foreach loops, one for the regions
then another for all of the stars in each region:

    foreach ( SkyRegion *region, skyIndex->getView() ) {
        foreach ( StarObject *curStar, region ) {
            ...
        }
    }

The changes to the drawing code for extended objects would be similar to this
but a little bit more complicated. I can describe the details elsewhere.


Conclusion
----------

I could go on and on (I probably already have) but I wanted to lay out
the entire basic structure from beginning to end so everyone can see
how this proposed plan works.  Even though this is long, it is incomplete.
I still need to describe the drawing of extended objects and also how
to deal with slow motions such as precession and proper motion of stars
and also the relatively fast motions of objects in the Solar System.
I think those features can be added to the structure outlined here in a
natural way.

I welcome any comments, questions, or suggestions.


-- 
Peace, James