[Kstars-devel] Problem with coordinate grid at high zoom

[James Bowlin]

On Tue September 11 2007, Torsten Rahn wrote: 
> Are you sure about this? Maybe it's just related to the drawing done 
> differently if it exceeds the memory of the graphics card. Or it's
> related to rasterization time increasing with O(n log(n)).

I'm pretty sure. The problem occurs _only_ when we use the antialias
RenderHint.  With this hint off, the drawing takes on the order of
a millisecond whether we clip the lines or not.  With antialiasing on
it was taking hundreds or thousands of milliseconds or more.  Even
when we clip every line, the antialiased drawing of just a few lines
can take hundreds of milliseconds.  Without the clipping it was taking
thousands of milliseconds or more _per_line_.  Another thing I noticed
was that QPainter::drawLine() would bog down with lines that were totally
off-screen so it wasn't even doing trivial rejection well.  Again, this
only happened in antialias mode.  When antialiasing was turned off
everything was fast.

I don't fully understand the problem though because the constellation
lines are generally much longer than the coordinate grid lines but
we only saw the problem with the coordinate grid lines and could not
reproduce it with any other component.  All the line-like components
were using the same code so it is quite puzzling why only the coordinate
grid lines were so awfully slow.

One more thing, the draw time did seem to scale with the off-screen
length of the lines being drawn (in pixels).  So the more we zoomed
in, the slower it got.  

> Anyways, I clip all QPainter::drawPolygon calls using my own QPainter
> class in Marble (it's called "ClipPainter" there and still has some
> issues though). 

We are not currently clipping polygons to the screen boundaries, only
lines.  We are clipping polygons against the celestial horizon though.

> > would be a bit of a mess if we needed to interleave the screen clipping
> > with the horizon clipping.  But we only need to do the screen clipping
> 
> Well, we also do that in Marble already.

We are doing this now as well as part of the solution Jason came up
with.  It seemed to have almost no impact on the speed.  With
antialiasing turned off, the coordinate grid lines still take just
a few milliseconds to draw. ISTM that QPainter::drawLine() has some
serious performance issues in antialiased mode.

> BTW: Do you have any "before"-"after" figures available concerning
> your spatial index introduction in KStars?

No, not really.  There are lots of different variables that affect
the timing:

   o The mesh level (number of triangles on the sphere)
   o The zoom level
   o Which components are being drawn
   o computer system

In theory, the index should give the greatest benefit when one is
zoomed-in on a small portion of the celestial sphere and it should
give the least benefit when one is zoomed-out.  I think this holds
true in practice as well.

There are two extra (draw-time) costs involved in using the index:

  1) creating the "aperture", a list of visible trixels (triangles).

  2) Iterating through the list of visible trixels for each
     component.

Both costs are greater when we are zoomed-out and more trixels are
visible.  Both costs also go up when there are more trixels on the
sphere.  When we are greatly zoomed-in there are only one or two
visible trixels so the costs are almost non-existent and the
benefits are large.

I'm currently using a level-3 mesh (512 trixels cover the sphere)
in order to optimize performance when we are zoomed-out.  Creating
the aperture only takes about 1 or 2 milliseconds.  The iteration
over visible trixels should be much faster than this but we have
to repeat it for each component that is being drawn.  Still, as
long as the number of elements in each component is larger than
the number of visible trixels, this should be a gain.  In fact,
you can still get a gain even if the number of components is
smaller than the number of trixels since iterating over trixels
is faster than mapping components to the screen.

> I'd be interested in introducing a spatial index for Marble as
> well, where/if it makes sense (at least for storing location
> data on the hard disk to save space for the marble distribution
> package).

Take a look at the kstars/kstars/skycomponents/README.indexing file.
It contains the roadmap for applying the index even though the index
library is in the kstars/kstars/htmesh directory.

Also, I think there is a bug in the line indexing routine in my
code in HTMesh.cpp which causes it to fail when a line segment is
much smaller than the dimensions of a trixel.  This showed up in
coordinate grid lines near the poles when I reduced the mesh level
(enlarging the trixels) and then also decreased the size of the
coordinate grid lines.   I think it can be fixed just by tweaking
one or two parameters but  I'm just working around it for now while
I rest and recuperate from the bogus August 1st code freeze.

-- 
Peace, James