[Kstars-devel] Interesting HTM timing results

[James Bowlin]

I can't count.  The interesting results were due to a mistake I made counting
stars.  I was assuming that there are 126,000 stars in the sky (roughly the
number of stars in the HIP files).  The "size" column in my chart was half
the opening angle of the circular region, the angle from the center to the
edge.  So the results for 100 degrees should have contained more than half
of all the stars.  I fixed the bug and the results are not as interesting.

It still looks like a single mesh at level 4 or 5 is our sweet spot. They
can select half the sphere in about 5 to 10 milliseconds.  When we are
fully zoomed out, only half the celestial sphere is visible so I think the
HTM would give us a factor of 2 speed-up when the display is zoomed out
(unless there is another fast clipping algorithm being used for this case
that I am not aware of).

Speaking of mistakes, my drawUserLines() routine would make a mess when
one end of a line was on-screen and the other was off-screen.  It looked
like off-screen points were flagged with an x or y value like -10000000.
So i added the following if statement to the make sure all coordinates
are on-screen before drawing:

    if ( ( o1.x() | o1.y() | o2.x() | o2.y() ) > 0) {
        psky.drawLine( o1.x(), o1.y(), o2.x(), o2.y() );
    }

Any negative value will make the result negative and the line won't be
drawn.  It would be nice to partially draw lines that have one point
on and one off but I haven't figured out how to do that yet.

This got me to thinking about how to use an HTM to clip things like
constellation lines.  One simple approach would be to break up every
constellation into a series of line segments, each specified by two
endpoints.  Right now a segment is only drawn if both endpoints are
visible.  So every triangle can have a list of line segments.  We store
each line segment once in one triangle that contains either end point.
When we get the list of triangles, we only plot the line segments that
are listed inside the visible triangles, just like with the stars.
If we are able to draw partial lines then we need to use the technique
for extended objects described below.  In a nutshell, every triangle
that a line passes through points back to that line.  If any of those
triangles is visible then the line gets drawn (once).

Since we are currently using the the moveTo(x, y) and lineTo(y, y) it is
possible that the drawLine(x1, y1, x2, y2) is slower.  Worst case slower
by a factor of 2 I would think.  We would get that factor of 2 back for
the full screen since only half of the sky is visible at one time.
The same trick can be used for anything that can be broken down into
line segments, such as the constellation boundaries.

This also made me realize that even though the HTM is good at giving us
a list of possibly visible stars, it is not so good at answering the
question "is this particular star visible?".   If we need to answer
questions like that, one way to do it is to flag every triangle in our
list as not-visible then mark every triangle in the list of visible
triangles as visible.  I guess we can get a little speed up by just
marking all visible triangles as not-visible (instead of the entire
list) before computing the new list of visibles.  The point is, if
we are going to want to ask questions like that then there is a a
bit of a speed penalty for having more triangles.  Anyway, once you
have the visible triangles marked, each star can point to its triangle
so if you ask if a star is visible it just answers:

     star->triangle->is_visible

Finally, I don't like the idea I put out earlier about a generalized clipper.
I like the current structure of having lists of different kinds of objects.
I think the best way to implement an HTM index is to replicate this structure
for each triangle in the index.  If there are things that we can't index,
either because they are too extended (perhaps the Milky Way) or because they
move too fast or something then they will need to be in global (celestial?)
lists outside of the HTM index.  If we need to implement a version of KStars
without HTM support then everything is in big global lists and we don't have
to loop over visible triangles.  I'm not claiming this is a new idea, I think
this is what Jason has been envisioning for a while.

One way to index extended objects is to enclose them in a polygon.  If any
vertex of the polygon is in a visible triangle then we try drawing the object.
This will breakdown if the user can zoom in on the object so closely that all
the vertices of the surrounding polygon are off-screen.  That can be fixed
by choosing a region that contains the object.  If any of the triangles that
cover that region are visible then we try to draw the object.  That intersection
only needs to be done once, when we are building the index (unless it is a
moving object).


-- 
Peace, James