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

[James Bowlin]

Hi Thomas, I'm glad you're interested in this.

On Tuesday 20 June 2006 15:19, Thomas Kabelmann wrote:
> first of all I let me say, that I don't know much about your idea, due to
> lack of time, so perhaps I'm wrong. But it's a good idea of speeding up kstars.

> As far as I understand, you want to put all objects of 1 region into 1 
> SkyRegion. So we have a lot of SkyRegions with a lot of lists. The SkyIndex 
> class is used to determine the right region.

Very close.  Often there will be many regions visible on the screen so in
the general case we are dealing with lists of SkyRegions.  The current plan
is to use a level-4 or level-5 Hierarchical Triangular Mesh, hopefully using
the code from here:  http://www.skyserver.org/htm/  The triangles look like
a giant geodesic dome.

A level-4 HTM would break the sky up into 2,048 regions and a level-5 would
break it up into 8,192 regions.  When the user is full zoomed out, slightly
more than half the total number of regions will be visible.

level regions
----- -------
 0         8
 1        32
 2       128
 3       512
 4     2,048
 5     8,192

> I dislike the idea of breaking the current composite/component model and I 
> dislike the idea of having all data in 1 centralized class for maintainance 
> and complexity reasons.

I think these are two different things.  I very much like the current scheme
where, for example, the Milky Way data and code is totally separate from all
the other things that are drawn on the sky.  I am not at all suggesting we
have one centralized class for all of these different types of things.  I
fully agree with you that that would be a step in the wrong direction.

But I am suggesting that we will no longer need the composite classes.
I will try to give you a more detailed explanation of my reasoning below.

> My idea would be, to combine the SkyIndex and the SkyRegion classes. So it 
> could look like this:
> 
> class SkyRegion
> {
> 	public:
> 		// add a point to the right region
> 		addPoint(SkyPoint *p);
> 		// return the list for the region
> 		QList<..> getRegionList(double ra, double dec);
> 		...
> 	private:
> 		// List of regions
> 		QList <Objects> regions;
> }
> 
> The list of "Objects" is abstract. We could subclass from SkyRegion for the 
> right type (StarObject, etc).
> 
> So every component could use an own SkyRegion object which just handles the 
> objects of the component. There is a slight overhead, as every component has 
> to determine the region, but I think it's worth. Perhaps the index can be 
> delegated through the components, so there is no overhead anymore.
> 
> What do you think?

I see two separate ideas here: 

  1) combine SkyIndex and SkyRegion
  2) give every component its own subclassed SkyRegion class

Let me give you a little background.  The cost of determining which regions
are at least partially visible can be significant.  In my tests, when the
user is full zoomed out it takes between 1 and 10 milliseconds to get the
list of regions. I don't think we want to do that calculation more than
once if we don't have to.

But that's okay, I think we can still implement your idea (2) above if we
are willing to keep the SkyIndex and SkyRegion classes separate.  Better
yet, we could get rid of the SkyRegion class entirely!  The idea here is
that the SkyIndex class would return lists of actual indices instead of
lists of SkyRegions.  Each SkyComponent would need to keep its own array
of "regions", which would just be an array of QLists.  I would imagine
that this array would be a static class member.

When it is time to add a component to the index, that component would ask
the SkyIndex for the index (indices) of the region (or list of regions) it
belongs to.  Then the component would be added to the QList or QLists that
correspond to the indices returned by the SkyIndex.

Likewise for drawing, the component will ask the SkyIndex, not for a list
of regions but for a list of the indices of the regions that are visible.
It will then dereference these indices in its own internal array of QLists
to find out what objects need to be drawn.

This is interesting.  When there is only one type of SkyComponent indexed
then the two solutions are almost identical, except one has the array of
"regions" in the SkyIndex and the other has the array in the SkyComponent.
When there is more than one SkyComponent indexed, the original idea still
has just one array but the elements in the array are more complex while
with the new idea, there is a separate array for each different type of
SkyComponent but each array element is simpler.

The code for getting all the stars to draw would become:

    QList<int> indices = skyIndex->getView();
    foreach ( int index, indices ) {
        foreach ( StarObject *curStar, region[index] ) {
            ...
        }
    }

Here "region" is a static member in the StarObject class that is an array
of QList<StarObject *>.

I hope this is clear to you but I fear it is as clear as mud.

I think both solutions are viable.  It's not clear to me that one would
necessarily be better or faster than the other.  I'll have to think about
it.

I'll try to explain why I think we will no longer need the SkyComposites
when we use the index/region model in a separate message.


-- 
Peace, James