[Kstars-devel] Some HTM progress

[James Bowlin]

On Friday 26 May 2006 03:24 pm, Jason Harris wrote:
> A question regarding the HTM function that returns the list of triangles
> that satisfies a given constraint: Does it return higher-level
> triangles, or only the bottom level ones?  

You create a SpatialIndex(level) and from then on, it seems only the 
triangles from that level are used so only the bottom level triangles
are returned as the result of any operation.

> I'm not sure of exact numbers, but it's certainly less than 1 second to
> clip, project and draw the entire sky currently.  So that involves
> clipping almost 200,000 objects, and projecting/drawing whatever it's
> decided is "on screen". 

Wow, that is fast.  That means manually clipping is at least 5 times
faster than indexing.  (at level 5 we can index at 40k/second).  Not 
surprising.  I think this means that if we update the screen 5 or more 
times before moving an object, we are better off using the HTM for 
clipping, but if we need to update the position (compared to the fixed
stars) every 5 screen refreshes or faster then we are better off without
using an HTM.

The Sun moves about a degree/day.  I figure the planets probably all
move slower than this but the moon moves about 12 times faster.
Triangles at level 5 should be about 10 arc-minutes in size (assuming
30 arc-seconds at level 14 and that the length scales as 2^level).
BTW: I got the size of the level 20 triangles incorrect in a previous
email.  I was incorrectly assuming the length scaled as 4^level).

So the Sun moves about 2.5 arc-minutes/hour.  This means we need only
re-index the sun and planets every hour if we give ourselves 5 or
10 extra arc-minutes when supplying the screen area to get triangles
for.  The moon would need to be re-indexed every 5 or 10 minutes or so.
This sounds like a big win, even for the moon if we can figure out
how to re-index them all slowly enough.

So the rule is simple.  If we give ourselves a safety margin of 10 
arc-minutes then we need to re-index a moving object before it moves
10 arc-minutes compared to the fixed stars.

Please correct me if I am wrong.

> IIUC, it doesn't need to index objects every time it clips, right?

Correct.  We would only need to re-index moving objects.

> Do you have numbers for the "slicing" operation's speed?

It looked like their intersect program had most of the timing hooks 
built-in so I made some minor changes and found that it can do roughly
500 intersections per second.  But the time did not seem to correlate
with the number of constraints involved, rather it seemed to scale
with the size of the resulting area (i.e. number of returned triangles).

Please take this with a large grain of salt because I'm just mucking about.
For example, it could be there is a significant overhead to creating a
domain with multiple constraints that is not being timed now.  It could
also be that they were using a more complicated algorithm than was needed
to just find the triangles inside of a circle.


> I agree, the array is the way to go.  If you go back to my original HTM
> email, I talked about a way to convert the standard HTM index
> ("S032012") to a signed integer, which may make the array indexing
> easier.

Turns out, they use unsigned, 64-bit ints internally as the ID.  They have
to go out of their way to generate the "S01230123" codes.

This raises the question of what format to use for triangles in the
HIP files.  Their cc_name2ID() code looks very fast.  Therefore I think
we should store the triangle ID as an "S01230123" string, perhaps with a
few more digits than we are planning to use.  Yes, this is the way to go.
It will make things much easier if we want to use more than one level at
the same time.

It sounds like we have a general game plan now for the fixed stars.
We have yet to determine:

 1) whether to use circles or rectangles for getting the visible triangles,
 2) exactly what lowest level to use, and
 3) whether it will be worthwhile to use more than one level.

All of these we can nail down with some simple experiments.


BTW: They expect declination and right ascension in degrees.




-- 
Peace, James