[Kstars-devel] HTM clipping of extended objects (long)

[James Bowlin]

I think using an HTM to index and draw fixed stars is understood.  Each
triangle contains a list of stars in that triangle ordered by brightness.
For each visible (or partially visible) triangle, we attempt to display
all the stars on the list down to the minimum brightness.

Extended objects are more complicated unless they can be reduced to the
single point case where we only display the object if that point is visible.
Extended objects need to have an entry in possibly more than one triangle.
They need an entry in every triangle they intersect.  Therefore the display
routines can't be quite as simple as with the stars because we probably don't
want to draw extended objects more than once just because more than one
triangle they are in is visible or partially visible.

BTW: Jason asked if the current HTM code returns partial visibility status
since some triangles are not visible at all, some are fully visible, and
some are partially visible.  I haven't gone digging for it but AFAIK, HTM
just gives a list of totally-visible and partially-visible triangles
without making a distinction.  It is pretty easy to find all the triangles
on the edges of the region by searching for those that have at least one
edge that is not in common with another triangle.  My Perl code does this
already so it can plot just the edge of intersection regions.

For this discussion I use the term "visible triangle" to mean a triangle
that is either totally or partially visible.  Similarly I will say a point
is visible if it is contained in a visible triangle and an extended object
is visible if it intersects at least one visible triangle even though that
point or object may not actually end up appearing on the screen.  I will
use the term "object" to mean an extended object and use "point" or "star"
for a point-like object.  Also, it is clear that we want to break up
extended objects into small pieces.  A constellation becomes a bunch of
line segments and each one of those segments is considered here to be
an extended object in its own right.

Since extended objects must be listed in more than one triangle and since
we only want to draw them once, each object needs at least one bit that
can be used as a memory to keep track of either the fact that it needs to
be drawn or was already drawn.  A simple idea is to have a "was_drawn" flag
for each (extended) object.  Assume that the was_drawn flag is false for
every object.  Then for each visible triangle, for each object it contains:

   if (was_drawn) return
   draw the object
   add the object to the drawn_objects list
   set was_drawn = true

After all objects are drawn, we go through the drawn_objects list and set
was_drawn to false so the object can be drawn again the next time we
refresh the display.  Then we clear the drawn_object list. The drawn_objects
list is what makes this approach a little ugly.  We sure don't want to be
allocating/deallocating memory here so we would need to store the list in
an array that is always large enough to contain the entire list of objects.

We can do away with the drawn_objects list if we are willing to go through
the entire list of objects and clear the was_drawn flag.  But this too seems
non-optimal.  A better approach is to create a draw_id (a bit like a process
id) that is stored in each extended object as an int or a long.  We draw
an object at most once for each draw_id:

  global draw_id++
  for every visible triangle:
      for every extended object it contains:
          if (object.draw_id == draw_id) return
          draw the object
          set object.draw_id = draw_id
      end
  end

If the global draw_id wraps after we increment it, we will then need to go
through the entire list of extended objects and set the draw_id to zero.

   draw_id++
   if (draw_id == 0)
      draw_id++
      for every extended object:
          set object.draw_id = 0
      end
  end

But this happens only once in a blue moon and it is very fast, much faster
than drawing the screen.  [Edit: some considerations below lead me to think
that we should make the draw_id a long so we never have to reset it to zero
in all our objects.  Maybe an int would suffice.  I haven't done the math.]


Ramifications
-------------

The HTM can be used for clipping extended objects, but unlike stars and
points, clipping extended objects will require some more refactoring in
the current code.  Extended objects will need to be broken up into smaller
graphical primitives (such as line-segments and polygons).  For example,
the ConstellationLinesComponent and the ConstellationLinesComposite classes
could be combined into a single ConstellationLine class.  The method
that reads in the data from a file (in ...Composite) could become a static
method in the combined class that spews ConstellationLine objects, one
each for every line segment to be drawn.  Each ConsellationLine would
contain:

  SkyPoint *p1, *p2;
  long drawID;
 
If we need to keep a list of all ConstellationLine's (and I think we might
because of the redundancies in the triangle lists) then that list could be
a static member of the class.

I realize the idea of yet another re-refactoring of the sky components may
not be wildly popular.  Personally, I don't think the Component/Composite
model gains us much (but I haven't looked deeply into the Solar System
components).  The idea of cascading a draw() command down a hierarchy of
composites does not fit well with spatial indexing.  Perhaps some things
would need to use the Component/Composite model and others not.  I think
they can live side by side comfortably.

One more idea.  In looking at the ConstellationLine code I see that it
is able to avoid having to calculate map->toScreen() more than once for
each point by having the SkyPoints for each constellation in one list.
When we break each constellation up into independent line segments, that
calculation will need to be repeated unless we do something to prevent it.
I suggest we add the following data members to the SkyPoint class so we
can cache the results of toScreen():

  QPointF screenPoint;
  long drawID;         // or "toScreenID" ?

  int  triangleIndex;  // Not yet needed in this context but you can see
                       // it coming down the pike.
  
The global drawID can be a static member of SkyMap.  We can make a slight
modification to toScreen() so it only recalculates the screenPoint if the
SkyPoint's drawID is different from the current drawID, otherwise it
returns the cached screenPoint;

Extended objects like line-segments and polygons would still need their
own drawID that serves a slightly different purpose.  The drawID in the
SkyPoint is for caching the toScreen() result.  The drawID in an extended
object is used for "caching" the drawing of the object to the screen so
it only gets drawn once per update.  Since they are doing two different
things we might be better off having two separate ID's, one for caching
toScreen() and the other for caching drawing but I'm not sure.  

I realize this might be a lot to chew on.  I also realize that the decision
to do another refactoring should not be taken lightly.  I'm very focused in
on spatial indexing and I'm still getting up to speed on the current code
base (and C++ for that matter).  I'm reporting back the implications to
the current code base as I see them.
 
--    
Peace, James