[Kstars-devel] Clipped Mikly Way polygons ported to 4.0

[James Bowlin]

I've ported the polygon clipping code to 4.0.  This was much more
complicated than porting the constellation line clipping.  The polygon
clipping code has a more complicated inner loop that needs more than
a simple if (Options::useAntialias ) { ... } else { ... } in order to
switch between aliased and anti-aliased code.

Here is what the inner loop looks like:

    {
        if ( !clipped && !clippedLast ) {
           polyMW << oThis;
        }
        else if ( !clippedLast ) {
            oMid = map->clipLineI(pLast, pThis, scale);
            polyMW << oMid;
        } 
        else if ( !clipped ){
            oMid = map->clipLineI(pThis, pLast, scale);
            polyMW << oMid;
            polyMW << oThis;
        }
        pLast = pThis;
        oLast = oThis;
        clippedLast = clipped;
    }
    if ( polyMW.size() && partVisible ) psky.drawPolygon( polyMW );

There are at least 4 places that would require the extra if ... else
statements and then another 3 more places in the inner loop for drawing
the outline of the Milky Way.  I decided to break it up into two different
routines called drawInt() and drawFloat() instead.  This was the cleanest
solution I could come up with.

I also added two convenience routines to SkyMap:  toScreenI() and clipLine(I)
both of which just call their non-I counterpart and convert the returned
QPointF into a Qpoint.

The code here works pretty well.  Drawing in integer mode takes between
12 ms and 35 ms.  But drawing in anti-aliased mode takes almost one second.
The integer and float code is almost identical so I don't think there is
something I am doing that is causing the long time.  I see a similar
increase in drawing speed (from integer to anti-aliased) when drawing
the coordinate grid.  They  both draw a lot of little lines and I think
this is what is causing the longer anti-aliased draws.

The code does not work for all projections though.  The filled mode
seems to work in every projection except Gnomonic, and Equirectangular.
In the Gnomonic projection the filled Milky Way covers the entire screen.
I don't know what the problem is.  In the Equirectangular projection,
no points are ever "clipped" (i.e. "past the celestial horizon").  In this
projection, some polygons that start on the left hand side of the screen
wrap over to the right hand side of the screen.  I think I could write
a special set of clipping routines for dealing with this projection.
This would double again the number of routines needed for drawing the
filled Milky Way so we would end up with 4 filled routines and 2 outline
routines.

There were also problems with drawing the Milky Way outline in some of
the projections.  The problem is that we currently use an heuristic
algorithm that uses the distance on the screen to decide whether to draw
a line or not:

   int imwmax =  5 * int( scale * Options::zoomFactor()/100.);
   ...
       if ( ( abs( oThis.x() - oLast.x() ) + 
              abs( oThis.y() - oLast.y() ) ) < imwmax ) {
            ...

The screen distance changes (sometimes a lot) in the different projections.
This problem is further exacerbated because I needed to create smaller
polygons and I also want to cull out some of the outline points that are
close together.

Since we know beforehand which lines should be drawn and which shouldn't,
I'd like to add another single character flag to milkyway.dat that would
indicate this information.  We might even be able to incorporate this info
in the existing flag (M or D) and use M or D or I (for ignore in outline
mode).

The only real question is: how do we store this information in the program?
The cleanest solution might be to have two sets of points: one for polygons
and another for outlines, but this basically doubles the amount of storage
needed.   The solution that would take the least space (I think) would be
to have in each MilkyWayComponent a QHash of the indices of the points that
should be skipped.  An array or QList of all the indices to skip might be
a bit faster but would take up more memory.

I really think would should implement one of these solutions.  Right now
the code for drawing the outlines is very complicated because it requires
an explicit toScreen() in order to get the screen coordinates so they can
be subtracted and compared as in the code above.  This caused me to copy
the drawClippedLine() code here to avoid having to redo the toScreen()
calls for every point.


Action items:

  1) I am going to go ahead and implement the "ignore points" feature using
     a QHash.  This will fix a lot of problems and make the code simpler and
     more robust.  

  2) I need some guidance for dealing with clipping polygons in the Gnomonic
     and Equirectangular projections.  I suggest we just leave these broken
     for now while we get the rest of it working.

  3) I've attached a patch file and will email the data files to Jason.
     I haven't updated to the KStars version that requires DBus yet
     because I've been working on porting the Milky Way code and it has
     been a much bigger job than I originally expected.  I already use
     DBus on my Gentoo system but it is not the more recent version
     required by KStars.  I hope they will play nice with each other.

     Jason, if you want to apply the patch and finally see the clipped Milky
     Way, that would be great.  For an even better effect, you can uncomment
     lines 69 and 70 in milkywaycomponent.cpp which will draw the polygons in
     green and red with a 1 pixel thickness.  But if you would prefer to wait,
     that's cool.  

I welcome any comments and suggestions.  This is my first foray into C++.
I'm sure there is a lot I still need to learn.


-- 
Peace, James
-------------- next part --------------
A non-text attachment was scrubbed...
Name: kstars-4-clipping-1.patch
Type: text/x-diff
Size: 6552 bytes
Desc: not available
Url : http://mail.kde.org/pipermail/kstars-devel/attachments/20060618/5cec86c5/attachment.bin