[Freeciv-Dev] Re: different iso drawing algorithms

[Raimar Falke <rf13@xxxxxxxxxxxxxxxxx>]

On Thu, Dec 12, 2002 at 03:45:46PM +0100, Rafa³ Bursig wrote:
> >> >> First I speak here about ISO maps.
> >> >
> >> >> Secound :
> >> >
> >> >Do you mean "Second point"?.
> >> >
> >> no "Secoundo point" :)
> >
> >Looks like Secoundo is French?!
> >
> rather Latin :
> Primo , Secoundo, etc.
> 
> >> >> Yes I know that I don't see all aspect of this probleb but I know
> >> >> one key in mapdraw code is speed.
> >> >
> >> >Yes but speed isn't the only key aspect of map drawing.
> >> >
> >> Major key is speed !!!
> >> Resently I saw Civ3 in action and with all nice gfx and animation
> >> speed of this game was poorly.
> >> This was on celeron 333 and what hapend when I run this game on my
> >> P233MMX :)
> >
> >Yes Civ3 is an example where the game was too slow. But we have
> >variety. The non-iso mode is on all three tested clients very fast:
> >4-10ms for a complete redraw. The iso case is slower by an factor of
> >30!!! So you can have a fast freeciv.
> >
> 
> Part of those 30 are const, becouse this is price for ISO tiles. There 
> are about 50% pixels transparent and draw loops ( gtk, SDL, win32 or 
> other )must handle it. In No-iso maps entire sprite is tile.
> ( SDL can reduce it by useing RLE but that is another story ).
> 
> Rest of factor (30) is lose in draw algoritm becouse idea of draw loops 
> still come from no-iso tiles and there must be make lot additional 
> checks to wotk with iso tiles. Look on number of additonal code in iso 
> drawing and no-iso drawing.
> 
> And that is reason why I want dedictated function in draw code.
> Before all unification I have simple redraw screen function that make 
> it in ~70 ms ( with flush )

> , your facrot is reduced to 7 ( I don't include here redraw time of map 

facrot?

> widget becouse only SDL use it ) and this still can be optimised.

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.

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

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

> 2) As I say before I'm not experienced programmer but I know one that 
> "*" and "/" are slow.
> Less "*" and "/" in code that code will be faster.
> 
> I use hard-coded tileset size only in one place. In position code 
> becouse this code is call by draw loops.
> NORMAL_TILE_WIDTH = 64
> x = ... << 5; insted x = ... * NORMAL_TILE_WIDTH/2;
> 
> Finaly we can use spec files to load some accelerators variables or 
> calculate it by code.
> 
> if ( ACC_WIDTH )
>     x = ... << ACC_WIDTH;
> else
>     x = ... * NORMAL_TILE_WIDTH/2;

With this micro optimization you may get 30% or so difference but not
the factor 30 we speak about. This is one example where flexibility is
a lot more important than speed.

> >> >> 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).
> >> >
> >> Yes and No :)
> >> This reduce size of function and in some cases like positionig
> >> system it is better
> >
> >Yes.
> >
> >> becouse we can make them INLINE.
> >
> >You will find that it is hard to convince the people that inline is a
> >good thing.
> >
> I don't want start her new HOLY WAR by inline with SMALL function is 
> good thing.

I agree if you mean "I don't want start a new HOLY WAR but inline
SMALL functions is good thing."

> >> In draw loop we ofen use something like that
> >>
> >> for( x .... )
> >>   for( y ... )
> >>    if (get_canvas_xy(x,y, canvas_x , canvas_y )) or if (
> >> map_pos_to_canvas_pos( ... ) )
> >>        {
> >>           draw(...);
> >>        }
> >>
> >> IMO those functions ( get_canvas_xy( ... ) or
> >> map_pos_to_canvas_pos(...) ) should be small and inlined becouse
> >> this will reduce jup outside loop.
> >
> >All this is nice and so but isn't the problem of the factor of 30
> >mentioned above.
> >
> This is part of this factor.
> 
> >> >> 4) BUFFERING, as i say before we need funct. that save updatet
> >> >> rect and then flush those rects.
> >> >> exp.
> >> >>
> >> >> #define MAX_RECT 50;
> >> >> struct rect {
> >> >>   int x, y, w ,h ;
> >> >> }saved_rects[MAX_RECTS];
> >> >> int count_of_rects;
> >> >>
> >> >> void save_rect( int x , int y , int w , int h )
> >> >> {
> >> >>   if ( count_of_rects < MAX_RECTS ) {
> >> >>     saved_rects[count_of_rects].x = x;
> >> >>     saved_rects[count_of_rects].y = y;
> >> >>     saved_rects[count_of_rects].w = w;
> >> >>     saved_rects[count_of_rects++].h = h;
> >> >>   }
> >> >> }
> >> >>
> >> >> flush_rects(void)
> >> >> {
> >> >>   if ( count_of_rects > MAX_RECTS ) {
> >> >>      /* flush fullscreen */
> >> >>   }
> >> >>   else
> >> >>   {
> >> >>      /* flush rect array */
> >> >>   }
> >> >>   count_of_rects = 0;
> >> >> }
> >> >
> >> >I agree we need something to dirty specific regions. While I also
> >> >agree that the implementation may use an array or a list of
> >> >rectangles.
> Now I use list and rather better is array.
> It is better that implementation of this leave in gui side becouse SDL 
> has such rect struct
> typedef struct {
> Sint16 x , y;
> Uint16 w ,h;
> } SDL_Rect;
> When we make it in common side then I must make confersion every time 
> that it will be called.
> 
> >> >I think that the interface should contain these functions:
> 
> 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.

> >> > void mapcanvas_dirty_tile(map_x,map_y);
> >> map_x , map_y - can be tile position on map.
> >
> >These are map positions.
> Yes this funct can make it but should look like:
> 
> void mapcanvas_dirty_tile(map_x,map_y)
> {
>   int canvas_x , canvas_y;
>   if (get_canvas_xy(map_x,map_y, &canvas_x , &canvas_y ))
>   {
>     mapcanvas_dirty_rectangle(canvas_x,canvas_y,
>          NORMAL_TILE_WIDTH,NORMAL_TILE_HEIGHT);
>   }
> }

That is a possible implementation.

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

This is also possible. As I said: I'm not sure what are the users and
what interface the callers want.

> >> > void mapcanvas_dirty_visible();
> >> > void mapcanvas_dirty_all();
> >> This is't needend becouse we can have
> >"mapcanvas_flush_fullscreen(void)"
> >
> >This isn't a good interface design. We have a set of dirty_something
> >functions and _one_ flush function.
> We can have somthing like this (void mapcanvas_dirty_visible() or void 
> mapcanvas_dirty_all() )
> but it should only say to mapcanvas_dirty_flush() to make flush full 
> screen ( not doing any calc )

There is nothing which speaks against a 
  static bool full_flush_requsted;
which is set by mapcanvas_dirty_all and queried as the first test in
mapcanvas_dirty_flush.

> >> >than there is a
> >> > void mapcanvas_dirty_flush();
> >> >which does the updating. The nice thing is that this can be coupled
> >> >with FREEZE_HINT/THAW_HINT to given maximum performance (minimal
> >> >number of refreshes). One problem is that this doesn't work with
> >> >animations. In this case we have to replace gdk_flush with
> >> >mapcanvas_dirty_flush.
> >> >
> >> No we need another funct to do that :
> >> void mapcanvas_flush_rectangle(canvas_x,canvas_y,width,height);
> >> this should be used with animation and make flush of rect.
> >
> >Why? mapcanvas_dirty_flush can quite well calculate for itself which
> >canvas area needs to be refreshed.

> Becouse when you call mapcanvas_dirty_flush(); there can be aonthrer
> rect "saved" on list/array. and sometime you want have "now" flush
> only one rect.

IMHO there shouldn't be such case.

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

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

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
  One nuclear bomb can ruin your whole day.