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

[Jason Harris]

Hello,

Let me see if I can try to summarize where the discussion is leading us.

Thomas's idea is to keep the current Composite/Component hierarchy, but 
instead of each Component storing a QList of some type of object, its objects 
will be stored in a QVector of templated QLists.  Each element in the QVector 
is the list of objects of the given type that occupy a specific HTM region.

At HTM level 5, there are 8192 HTM regions, so each Component's QVector will 
have 8192 elements (and each of these, again, is a QList of the objects in 
that region).

Now, some questions:

+ Would a QHash make more sense than a QVector?  The advantage of a QVector is 
that the elements are stored contiguously in memory, but is this even 
possible since we can't know how much memory each QList will take?  The QHash 
is already templated, and would seem to be a more logical choice since 
there's no guarantee that every region will have a populated QList.

+ It's not clear to me how to determine which objects are visible in this 
scheme.  James proposed a function 'QList<SkyRegion*> indexCircle( SkyPoint 
*p, double radius)', which returns the list of HTM regions that are within 
'radius' of point 'p'.  If 'p' is the focus position, and 'radius' is the 
size of the SkyMap's half-diagonal, then this function tells us which HTM 
regions are onscreen.  

However, James's proposed function returns 'QList<SkyRegion*>', and SkyRegion 
is supposed to contain the list of objects in a particular HTM region.  So, 
how best do we merge this with Thomas's proposal?  One way is to have 
indexCircle() return a QList<int>, with the IDs of the visible triangles, and 
then transmit this list to each of the Components, which will allow each of 
them to construct a list of their objects which are visible.

Alternatively, indexCircle() can be a member function of SkyComponent, and 
each Component can determine for itself which of its objects are visible.  
This involves unnecessary repeating of the HTM visibility calculation, 
however.

So, here's my idea.  Add a function 'QList<int> SkyMap::htmCircle( SkyPoint 
*p, double radius )' which returns the set of HTM region IDs that lie within 
the bounds of the sky-circle defined by p and radius.  Then we add a function 
'void SkyComposite::computeVisibility( QList<int> &visibleIndexes )', which 
takes this list of HTM IDs and uses them to build the list of objects in each 
Component which are visible.  The SkyComposite version will just pass on the 
request to its child Components.  The SkyComponent implementation looks like 
this:

void SkyComponent::computeVisibility( QList<int> &visibleIndexes ) {
    //visibleList() is a QList<SkyObject*> member variable that stores 
    //the currently-visible objects
    //objectHash is the QHash storing all objects of this type, indexed 
    //by the HTM region ID
 
    visibleList().clear();

    foreach( int i, visibleIndexes ) 
        visibleList() << objectHash[ i ];
}

Then, in SkyComponent::update() and SkyComponent::draw() we can simply replace 
all current instances of objectList() with visibleList(), and remove the 
current visibility-checking code.

Is this feasible?

Jason
-- 
-------------------------------
KStars: http://edu.kde.org/kstars
Forums: http://kstars.30doradus.org