[Kstars-devel] Interesting HTM timing results

[Jason Harris]

Hi James,

I'm pressed for time this week (and next), so just a quick reply:

On Wednesday 31 May 2006 22:24, James Bowlin wrote:
> 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:
>
Yes, the code resets offscreen points to -10000000.  As I recall, it's only 
supposed to do this for points that are *far* offscreen; points that are just 
a bit outside the SkyMap rect should still have valid (but offscreen) 
coordinates.

> 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.
>
I sometimes do interpolation in this case, I think for the horizon, maybe for 
Constellation liens too.  So, it basically truncates the line, creating a new 
endpoint at the screen edge.

> 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
Uh, I guess you're using the 3.5 codebase?  moveTo() and lineTo() no longer 
exist.  everything is drawLine() now.  You should move to trunk before you 
get too deep into modifying the codebase...

> 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
>
As I recall, there are actually three visibility states in HTM: not visible, 
visible, and partially visible...right?

> 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.
>
Sounds good.  The Milky Way is currently split into 11 pieces, precisely 
because I needed to do partial visibility calculations.  We could easily 
split it up into many more small pieces, to put it into the HTM framework.

> 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).

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