[Freeciv-Dev] Re: different iso drawing algorithms

[Jason Short <jdorje@xxxxxxxxxxxxxxxxxxxxx>]

On Thu, 2002-12-12 at 15:14, Raimar Falke wrote:

> I agree that the code has to to more work for the iso case. But this
> be a factor around 3-5 and not 30. So did anybody profiled it? I
> did. Data attached. As usual profiling distort the timing results. But
> is clearly visible that:
>   - get_drawn is called almost the double amount in iso
>   - get_drawn* create a lot of normalize_map_pos calls (Jason are they
>   really necessary?)
>   - fill_tile_sprite_array* are called by the same amount
>   - the amount of calls of pixmap_put_tile_iso and pixmap_put_tile are also
>   equal. Also the execution times are roughly equal.

Vasco and I talked last night about a possible layered drawing system. 
Currently there is only one full layer onto which everything is drawn. 
Additionally some things are drawn directly onto the display: including
animations and city texts.  Some of this is GUI-dependent, and some of
it is hard-coded by the mapview_common code and GUI interface.

There are two priorities here: drawing quality (correctness) and drawing
speed (efficiency).  My priorities put correctness way ahead of
efficiency.  Others may differ.

Drawing city texts only to the display puts a limit on these.  Over
time, we have improved drawing quality by calling
update_city_descriptions more and more often when graphical updates
happen: we call it all the time.  This leads to better quality: it used
to be that if you moved a worker around the city's turns-to-build
wouldn't be updated.  Now it is.  But it decreases efficiency since
update_city_descriptions() must update _all_ city descriptions and must
(for most GUIs) redraw every underlying sprite as well via
update_map_canvas_visible().  We improved on this with the use of
queue_mapview_update(), which waits to make a single update at the end
of the packet set.  (Unfortunately, and foolishly on my and Raimar's
part, this function queues a full update rather than an
update_city_descriptions; the two are currently the same.)  But the fact
that it has to redraw _everything_ is still a big problem for
efficiency.

And it's hard to get around, since we don't know _where_ the city
description goes.  We could assume that a city description falls into
the 3 tiles underneath the current tile.  Except that this may not be
the case - and in the case of iso mode those 3 tiles are really 7 tiles,
which may include the descriptions of other cities.  So even with the
multi-layered idea described below, we'd still have to refresh every
city's description each time we wanted to update a single city's
description.

No, for correctness the current system falls short in several ways. 
City descriptions are overwritten whenever any graphics are updated
without redrawing the entire screen.  (Before going on, you may want to
re-read that last sentence!)  This can be improved on in several ways.

City descriptions could be drawn into the backing store, then written to
the display along with everything else.  This would improve the
situation by about 90% IMO.  Now animations would go over, but not
overwrite, the city descriptions.

Better would be to separate the layers: use two backing stores, one for
the underlying graphics and one for the city descriptions.  Animations
would be drawn in between the two.  This allows for total correctness,
since any time we update_map_canvas with a write_to_screen set we can
write the city names directly over it.

Note that all layers except the bottom layer must use either
transparency or some tricky masking to 

Then we considered a three-layer system: draw the graphics that rarely
change (terrain, specials, improvements, cities - the vast bulk of the
work) on the bottom layer, those that sometimes change (units) in the
second layer, and the city descriptions in the top layer.  This makes
small updates substantially faster, but full updates (recentering, for
instance) slower.

BTW: another reason iso-view is slower than non-iso is that using the
blending mask is slow.

> > >Other key aspects are correctness (the diagonal-road issue is in this
> > >issue),
> > some time ago I send patch that correct some problem with road drawing 
> > but Jason took only mountainus part from this patch.
> > 
> > >maintainability (no code duplication please),
> > sory but with some case it is recomended.
> 
> I don't understand this sentence.

SDL has facilities to increase the efficiency of certain operations.  If
we do these in common code we cannot take advantage of this efficiency. 
But in this case we can provide a gui function do_xxx along with a
common function base_do_xxx which can be used by GUIs that want it.

> > ( see what I say about 
> > unification of draw code to iso and no-iso )
> > 
> > >flexibility (no hard-coded tileset size) and so on.
> > >
> > Here I want say about 2 things.
> > 1) There are in code a lot of this "NORMAL_TILE_WIDTH/2"
> > and "NORMAL_TILE_HEIGHT/2", it will be better that we add new variable :
> > "HALF_NORMAL_TILE_WIDTH" and "HALF_NORMAL_TILE_HEIGHT".
> 
> No. NORMAL_TILE_WIDTH by itself was a hack. First a define, than a
> constant variable and now it can change almost everytime (tileset
> switching). It should be get_normal_tile_width().

I disagree.

The naming is a hack, yes - done for backward compatibility.  But there
isn't much we can do other than change the name.  We can make it a
function - then we would have

  #define get_tile_width() (NORMAL_TILE_WIDTH)

which is prettier but fundamentally the same.  And we might as well have
a

  #define get_half_tile_width() (HALF_TILE_WIDTH)

to provide the half-width.  But (1) I would want to see numbers on how
this is faster for someone and (2) if HALF_TILE_WIDTH is encoded then we
must assert that NORMAL_TILE_WIDTH and NORMAL_TILE_HEIGHT are both even
(which shouldn't be required now because of the order of operations).

On my computer, dividing a signed integer by 2 takes 8 instructions.

Where we could get a (slight) advantage here is if we could make it a
compile error to try to change these values.

> > >> >> 3) I'm not much experienced programmer byt have  we any speed up
> > >> >> if we change client API
> > >> >> From :
> > >> >>
> > >> >> int draw(...) {
> > >> >> ...
> > >> >> if (isometric)
> > >> >> do something
> > >> >> else
> > >> >> do something
> > >> >> }
> > >> >>
> > >> >> To
> > >> >>
> > >> >> int (*DRAW)(...);
> > >> >>
> > >> >> int iso_draw(...)
> > >> >> {
> > >> >> do something
> > >> >> }
> > >> >>
> > >> >> int noiso_draw(...)
> > >> >> {
> > >> >> do something
> > >> >> }
> > >> >>
> > >> >> void init()
> > >> >> {
> > >> >> if (isometric)
> > >> >>   DRAW = iso_draw;
> > >> >> else
> > >> >>   DRAW = noiso_draw;
> > >> >> }
> > >> >
> > >> >This won't you buy anything. You trade one branch miss prediction
> > >> >against a function call (just look at the prologue and epilogue of
> > >> >a normal function).

I suspect this method will be slower, since you cannot inline a function
that is called through a variable.  And the current system lets you
improve efficiency for a single build by changing:

  extern bool is_isometric;
  extern int NORMAL_TILE_WIDTH, NORMAL_TILE_HEIGHT;

to

  #define is_isometric (TRUE)
  #define NORMAL_TILE_WIDTH 64
  #define NORMAL_TILE_HEIGHT 32

if you wish to hard-code these values.

> > Before I start...
> > Flush funtctions need pixel cordinate not map cordinate.
> > Better we "save" pixel cordinate than "save" map cordinate and 
> > recalculate them with flush.
> 
> The flush function doesn't take any parameter.

We have the possibility for several different layers of flushing.  You
guys keep saying "we need xxx", but you should also say *where* this
code should go: in GUI or common.

The GUI code should provide at least one function:

  flush_map_canvas(canvas_x, canvas_y, pixel_width, pixel_height);

it may be possible to increase efficiency for some clients by providing
flush_map_canvas_visible() or flush_rects() (but I would like to have
this explained before providing it).  These should all work on canvas
positions.

The common code may wish to track the dirty-ness of individual tiles. 
That way instead of calling update_map_canvas(x, y, 1, 1, FALSE) we just
mark position (x, y) for being redrawn later.  Then when another
function is called we redraw this function and all others.  To make
things clear we probably shouldn't call this "flushing" but should come
up with some other name.

One implementation question is at what point it is faster to discard the
list of rects that need flushing and when we should just flush the whole
mapcanvas.  One such choice would be:

  static int x0 = -1, x1 = -1, y0 = -1, y1 = -1;

  void mark_rect_dirty(int canvas_x, int canvas_y,
                       int width, int height)
  {
    if (x0 == -1) {
      x0 = canvas_x;
      x1 = canvas_x + width;
      y0 = canvas_y;
      y1 = canvas_y + height;
    } else {
      x0 = MIN(x0, canvas_x);
      x1 = MAX(x1, canvas_x + width);
      y0 = MIN(y0, canvas_y);
      y1 = MAX(y1, canvas_y);
    }
  }

thus we keep no "list" of rects that are dirty.  An alternative is to
keep a full list.  This is a tradeoff; both have cases where they do a
lot of unnecessary redrawing.

> > >> > void mapcanvas_dirty_rectangle(map_x,map_y,width,height);
> > >> if this function work like  "save_rect( int x , int y , int w , int
> > >> h )" then map_x , map_y should be pixel tile positon on screen.
> > >> ( canvas_x , canvas_y )
> > >
> > >Since mapcanvas_dirty_tile works on map positions and not canvas
> > >positions mapcanvas_dirty_rectangle should also be. However we can
> > >also add a
> > 
> > >   void 
> > >mapcanvas_dirty_canvas_rectangle(canvas_x,canvas_y,pixel_width,pixel_height);
> > >
> > >Note that I don't know how often these functions will used. It is
> > >quite possible that one function isn't needed at all.
> > >
> > 
> > That all depend where you want call those functuions.
> > exp.
> > 
> > int draw_tile( int map_x , int map_y )
> > {
> >   put_one_tile( map_x , map_y ); /* here you calculate canvas_x , 
> > canvas_y */
> >   mapcanvas_dirty_tile(map_x,map_y);/* here you make secound 
> > calculation canvas_x , canvas_y or make it with flush*/
> > }
> > 
> > better is
> > 
> > void put_one_tile( map_x , map_y );
> > {
> >   int canvas_x , canvas_y;
> >   ...
> >     mapcanvas_dirty_rectangle(canvas_x,canvas_y,
> >          NORMAL_TILE_WIDTH,NORMAL_TILE_HEIGHT);
> > }
> 
> > IMO we need both :)

IMO put_one_tile should be passed in canvas_x, canvas_y.  But it is not
this function that should mark the rect as dirty - it is
update_map_canvas.

> > But majory problem is "where" and "when" call
> > mapcanvas_dirty_flush();
> 
> No this is easy. You call it from handle_processing_finished,
> handle_thaw_hint and everytime you drawn an animation frame (gdk_flush
> now). If we change the view option it may also be nice to have:

Yes.

>  void view_option_changed(void)  
>   // or {update,refresh}_map_canvas if it is needed also by other users
>  {
>    mapcanvas_dirty_all();
>    mapcanvas_dirty_flush();
>  }

No.  You have to actually draw new sprites if a view option has
changed.  For instance if we remove roads/rails we have to redraw
everything below and above it unless we use way too many layers of
backing store.

jason