[Kstars-devel] Interesting HTM timing results

[James Bowlin]

These results are so interesting that I suspect I have made a mistake
somewhere in counting stars.  I wanted to find the effect that changing
the mesh level had on the intersection speed.  The courser meshes were
significantly faster as expected.  I then counted the number of stars
returned by each intersection.  The finer meshes should return fewer
stars for each intersection since they are a better approximation to
an actual circle and the algorithm needs to err on the safe side.

Then I tried to estimate the total time to draw the sky with this
simple formula:

   total_time = intersect_time + time/star * stars_found

This is a gross approximation since the time it takes to clip a star
is going to be less than the time to check the clipping and then
draw the star.  But if graphics hardware is decent, it could well be
that the time to draw is much smaller than the time it takes to
do the manipulations before the clipping check.  In that case, this
is a very good approximation.  I used two different estimates for
the time to clip/draw a star.  Jason said Kstars could draw 200,000
objects per second which comes out to 5 us (micro-seconds) per star.
I used this value for one estimate, but then I estimated again assuming
1 us per star.   This estimate would apply if we get a factor of 5 speed
up from removing the transcendentals from the transformations or if the
drawing took up 80% of the time in the current scheme.

The surprising result is that with either of those estimates, it is almost
always faster to have as fine a mesh as possible, even a level 6 mesh with
only 4 stars per triangle!  Although I think for our problem, a level 4
or 5 mesh is optimal.  Here is the data.  Columns are described below.

 size level  trixels     iter  us/circ    stars  time(5)  time(1)

    1     3        1    10000      101      246     1331      347
    1     4        1    10000      119       61      426      180
    1     5        3     5773      145       46      376      191
    1     6        7     3779      238       26      372      265
   10     3       10     3162      180     2460    12484     2641
   10     4       25     2000      380     1538     8070     1918
   10     5       70     1195     1037     1076     6420     2114
   10     6       92     1042     1822      353     3591     2176
  100     3      131      873     1922    32238   163114    34161
  100     4      264      615     4062    16242    85272    20304
  100     5      520      438    10238     7998    50229    18236
  100     6      620      401    16110     2384    28030    18494

size: the opening angle of the circle in degrees.
level: the mesh level.
trixels: the number of triangles returned by the intersect.
iter: the number of iterations used for timing.  You can ignore it.
us/circ: the time to do one intersection in micro-seconds.
stars: the average number of stars in the returned trixels.
time(5): time to draw the sky assuming 5 us/star.
time(1): time to draw the sky assuming 1 us/star.

I find this result very interesting.  Don't bet the ranch on it because
I could well have made a terrible mistake somewhere, but if it holds up
it implies that even though intersections on the finer meshes are more 
expensive, it turns out to be time well spent since it is saving us time 
in the long run by doing a better job of reducing the number of stars
that need to be clipped manually.   It would also mean that my idea of
saving time by using a courser mesh for the wider views would have
actually slowed things down!  Of course in the wider views, people
generally clip the dimmer stars in which case the benefit of the finer
mesh would be greatly reduced.  AFAIK, the HTM's will at best give us
a factor of 2 speed improvement when it comes to drawing the entire sky
(I think we only draw 1/2 of the sky at a time).  This makes me think
that we also might be able to use the HTM to clip stars that are under
the horizon when we are in the mode of just drawing that area as green.

The chart above was produced by 21 lines of Perl code.  I'd be glad to
post it if anyone wants to check my work.  Please consider these results
to be an alpha release.  

For debugging purposes, I'd really like to try to implement the dcop
drawLine() feature.  Actually, I'd like to implement drawLineRaDec()
so the lines would be somewhat fixed to the sky.  Then we would
just need an eraseLines() for starting over.  The lines could all
be stored on a stack somewhere.   I would draw the triangles
so we can get an image of what is going on with these meshes and
intersections.


-- 
Peace, James