[Freeciv-Dev] Re: different iso drawing algorithms

[Raimar Falke <rf13@xxxxxxxxxxxxxxxxx>]

On Fri, Dec 13, 2002 at 02:28:14AM -0500, Jason Short wrote:
> 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 

If we are assuming that drawing with masks is slow this is also
bad. But it may be better than the current situation.

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

Everybody repeats this. Lets get some facts. If I run the attached
patch I get this:

2: gdk_draw_pixmap of 30x30: mask=0,109843s/0,085068s (1,291238) 
nomask=0,156966s factor=0,699788
2: gdk_draw_pixmap of 30x30: mask=0,328607s/0,350387s (0,937840) 
nomask=0,175968s factor=1,867425
2: gdk_draw_pixmap of 30x30: mask=0,091894s/0,044015s (2,087788) 
nomask=0,133944s factor=0,686063
2: gdk_draw_pixmap of 30x30: mask=0,145595s/0,128822s (1,130203) 
nomask=0,162402s factor=0,896510
2: gdk_draw_pixmap of 30x30: mask=0,221726s/0,250396s (0,885501) 
nomask=0,180720s factor=1,226903
2: gdk_draw_pixmap of 30x30: mask=0,064431s/0,046642s (1,381394) 
nomask=0,141706s factor=0,454681
2: gdk_draw_pixmap of 30x30: mask=0,089405s/0,104459s (0,855886) 
nomask=0,159876s factor=0,559215
2: gdk_draw_pixmap of 30x30: mask=0,215491s/0,245619s (0,877338) 
nomask=0,176472s factor=1,221106
2: gdk_draw_pixmap of 30x30: mask=0,078879s/0,041863s (1,884218) 
nomask=0,139037s factor=0,567324
2: gdk_draw_pixmap of 30x30: mask=0,096037s/0,111998s (0,857489) 
nomask=0,137040s factor=0,700795
2: gdk_draw_pixmap of 30x30: mask=0,256533s/0,259987s (0,986715) 
nomask=0,196170s factor=1,307708
2: gdk_draw_pixmap of 30x30: mask=0,071293s/0,038085s (1,871944) 
nomask=0,153227s factor=0,465277
2: gdk_draw_pixmap of 30x30: mask=0,143425s/0,103198s (1,389804) 
nomask=0,162376s factor=0,883289
2: gdk_draw_pixmap of 30x30: mask=0,405839s/0,271432s (1,495177) 
nomask=0,208848s factor=1,943227
2: gdk_draw_pixmap of 30x30: mask=0,072874s/0,036880s (1,975976) 
nomask=0,144693s factor=0,503646
2: gdk_draw_pixmap of 30x30: mask=0,140034s/0,098000s (1,428918) 
nomask=0,154884s factor=0,904122
2: gdk_draw_pixmap of 30x30: mask=0,251315s/0,211571s (1,187852) 
nomask=0,183251s factor=1,371425
2: gdk_draw_pixmap of 30x30: mask=0,077498s/0,047031s (1,647807) 
nomask=0,128152s factor=0,604735
2: gdk_draw_pixmap of 30x30: mask=0,142329s/0,118321s (1,202906) 
nomask=0,136285s factor=1,044348
2: gdk_draw_pixmap of 30x30: mask=0,328938s/0,327105s (1,005604) 
nomask=0,165641s factor=1,985849
2: gdk_draw_pixmap of 30x30: mask=0,082073s/0,046333s (1,771372) 
nomask=0,122281s factor=0,671184

The last number is time_for_mask/time_for_nomask. This factor should
>1 if drawing with mask is slower. As you can see it is around 1 (the
average is 0.979). This looks a bit odd. So I added another mask run
and indeed the two mask runs also differ a bit. I have no idea what is
causing this but

    Using a mask with gdk_draw_pixmap doesn't slow gdk_draw_pixmap down.

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

Ack.

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

gcc-2.96, gcc-3.2:

        movl    %ebx, %edx
        shrl    $31, %edx
        addl    %edx, %ebx
        sarl    %ebx

Intel 6.0, 7.0:

        addl      $-2147483648, %esi                            #3.9
        adcl      $-2147483648, %esi                            #3.9
        sarl      $1, %esi                                      #3.9

You have an odd compiler.

So dividing by 2 is a non-issue.

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

Ack.

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

As much as possible common. Maintainability.

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

I disagree. There should only be one flush function which flushes all
objects which are dirtied before. No flush_map_canvas(canvas_x,
canvas_y, pixel_width, pixel_height). The flush function can calculate
all this by itself.

> 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:

Yes that is in interesting question.

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

It will work if there is only one layer?!

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
 Windows: Where do you want to go today?
 Linux: Where do you want to go tomorrow?
 BSD: Are you guys coming or what?

diff
Description: Text document