[Freeciv-Dev] Re: (PR#4648) how to do wrapping in map_to_canvas_pos?

["rwetmore@xxxxxxxxxxxx" <rwetmore@xxxxxxxxxxxx>]

I'm not sure what the problem with unnnormalize_map_pos() really is,
but let me try and relate all the normalize/unnormalize/map_distance
algorithms and how they reflect special case/optimizations of the
general case reflected by unnormalize_map_pos() as a primer.


This code does the map_distance vector operations you allude to. That
code is basically an optimized hack that avoids a full unnormalize, i.e.
does just this core part, but it will probably need to be upgraded for
truly general topologies at some point as commented somewhere.

Note, map_distance uses a centerpoint origin for positive and negative
displacements within a "map.*size/2" range. Most other operations want
an origin with only positive offsets reflecting array and window position
access standards.

   /* pre-unnormalize: vv will have +ve offsets wrt v0 in native coordinates */
   if (topo_hasFlag(TFLAG_WRAPX)) {
     vv[0] -= v0[0];
     vv[0] = WRAP(vv[0], map.xsize);
     vv[0] += v0[0];
   }
   if (topo_hasFlag(TFLAG_WRAPY)) {
     vv[1] -= v0[1];
     vv[1] = WRAP(vv[1], map.ysize);
     vv[1] += v0[1];
   }

Note too, this is just the standard normalize_map_pos(), but done with an
offset/origin point. The difference between normalize and unnormalize is
just this offset flexibility, i.e. the offset v0 is (0,0) when one wants
the single defined "normal set" case, and the pre/post adds are optimized
away.

   It is the wrapping that is tricky.  The obvious logic is something like:
    if (map_x < map_view_x0) {
      map_x += map.xsize;
    }

Your "obvious logic" makes assumptions about the map coordinate being within
a particular range, which actually has led to a number of bugs in the past.
The WRAP or while loop constructs in (un)normalize_map_pos() fix this. The
latter are actually so incredibly efficient for your special case that there
is never a reason to use the buggy "obvious logic" form.

BTW: map_adjust*() seems to be undergoing a revival. Remember the reasons
for deprecating this, partly at least to force the choice back to the caller
as to whether a WRAP or CLIP operation is required, and partly to avoid 1-D
optimizations. The goal should be to remove all these locally hardcoded ways
of dealing with the core topology operations, and *never* reintroduce them.

Full unnormalize just adds the final generalization as a last fixup to the
above first core approximation for the special case of mixed/rotated
conversions. In most cases this code is not executed, so you pay a single
branch test penalty when things are structured this way.


Something else, is that in replacing the original Freeciv while loops in
normalize_map_pos() with WRAP macros, one obscures the relationship
with the vector form of these loops done in the special case code here.
It might be fun to see if one could come up with a vector WRAP macro
as a final reflection of the symmetries in all these implementations.

Anyway, I am always amazed that people complain about the complexity of
vector math used in unnormalize_map_pos() that is practically tag-for-tag
the original scalar code from Freeciv pre-history. When you compare some
of the "obvious" alternatives presented or some of the other original
iso-code, it just leaves me shaking my head in wonderment at the workings
of the human brain :-).

Cheers,
RossW
=====


Jason Short wrote:
> map_to_canvas_pos must first wrap the given map position relative to the 
> mapview origin, then convert that to a canvas position.
> 
> It is the wrapping that is tricky.  The obvious logic is something like:
> 
>    if (map_x < map_view_x0) {
>      map_x += map.xsize;
>    }
> 
> and this is basically what is currently used for both iso and non-iso 
> views.  But this isn't quite right for iso-view; for instance 
> (map_view_x0,map_view_y0-2) will wrap to itself and will never be shown, 
> no matter how large you make the window.
> 
> When we allow north-south wrapping and iso-maps this becomes 
> exponentially more complicated.
> 
> One alternative is to do the wrapping explicitly, as is done above. 
> Ross has written a function to do this for gen-topologies, called 
> unnormalize_map_pos.  It is very complicated.  See the attached 
> unnormalize_map_pos.c.
> 
> Another alternative is to use map_distance_vector to find the 
> representative position "closest" to the center of the mapview window, 
> and use that position for the calculations.  This means 
> map_distance_vector must be able to deal with unreal positions, as 
> map_to_canvas_pos does.  See the attached map_to_canvas_pos.diff (this 
> patch fixes the "not quite right" part of the current implementation).
> 
> Which is better?
> 
> jason
> 
> 
> 
> ------------------------------------------------------------------------
> 
> /**************************************************************************
>   Generalized rectangular (un)normalize (in map coordinates)
> 
>   This finds the point in the (iso-)rectangular normalized set at offset
>   (x0, y0). For isometric rectangles, thee wrapping condition test is
>   given by a linear combination of the standard map coordinates.
> 
>   This still assumes a native rectangular map shape with x and/or y
>   wrapping conditions.
> 
>   Note: normalize_map_pos is just this function calleed with (x0,y0) of
>         the standard map origin and is_iso false.
> **************************************************************************/
> bool unnormalize_map_pos(int *un_x, int *un_y, int map_x0, int map_y0,
>                        bool is_iso)
> {
>   static int ij[2][2], uv[2][2], wraptype = 0;
>   int tt[2], vv[2], v0[2], mywraptype;
> 
> #define DOT(u, v)    (u[0] * v[0] + u[1] * v[1])
> #define ADD(t, u, v) (t[0] = u[0] + v[0], t[1] = u[1] + v[1])
> #define SUB(t, u, v) (t[0] = u[0] - v[0], t[1] = u[1] - v[1])
> 
>   if (!is_real_map_pos(*un_x, *un_y)) {
>     return FALSE;
>   }
> 
>   mywraptype = topo_getMask(TFLAG_WRAPX | TFLAG_WRAPY);
>   if (mywraptype == 0) {
>     /* No wrappable coordinates - just return is_real */
>     return TRUE;
>   }
> 
>   if (mywraptype != wraptype) {
>     /* Define the wrapping transformations once, and save them */
>     wraptype = mywraptype;
> 
>     switch (wraptype) {
>     case TFLAG_WRAPX:
>       /* Only wraps in the standard native X direction */
>       uv[0][0] = map.xsize;
>       uv[0][1] = uv[1][0] = uv[1][1] = 0;
>       break;
>     case TFLAG_WRAPY:
>       /* Only wraps in the standard native Y direction */
>       uv[0][0] = uv[0][1] = uv[1][0] = 0;
>       uv[1][1] = map.ysize;
>       break;
>     case TFLAG_WRAPX | TFLAG_WRAPY:
>       /* Wraps in both native X and Y directions */
>       uv[0][0] = map.xsize;
>       uv[0][1] = uv[1][0] = 0;
>       uv[1][1] = map.ysize;
>       break;
>     default:
>       /* No wrap - never used */
>       uv[0][0] = uv[0][1] = uv[1][0] = uv[1][1] = 0;
>       break;
>     }
> 
>     /* set coordinate transformation vectors to standard identity */
>     ij[0][0] = ij[1][1] = 1;
>     ij[0][1] = ij[1][0] = 0;
>   }
> 
>   /* unnormalization is best determined in native coordinates */
>   map_to_native_pos(&vv[0], &vv[1], *un_x, *un_y);
>   map_to_native_pos(&v0[0], &v0[1], map_x0, map_y0);
> 
>   /* pre-unnormalize: vv will have +ve offsets wrt v0 in native coordinates */
>   if (topo_hasFlag(TFLAG_WRAPX)) {  
>     vv[0] -= v0[0];
>     vv[0] = WRAP(vv[0], map.xsize);
>     vv[0] += v0[0];
>   }
>   if (topo_hasFlag(TFLAG_WRAPY)) {
>     vv[1] -= v0[1];
>     vv[1] = WRAP(vv[1], map.ysize);
>     vv[1] += v0[1];
>   }
> 
>   /* This is a mongrel algorithm to deal with final fixes to pi/4 rotated
>    * aka iso rectangluar window in a normal rectangular map or vice versa.
>    *
>    * Warning: this is almost impossible to understand without drawing am
>    *          accurate graph of the two overlayed views and tricky then.
>    *          Each operation effectively moves part of one view bounded
>    *          by the appropriate lines through a wrapping translation.
>    *          For a simple x-wrapping map, it changes a rectangle into a 
>    *          parallelogram in one step.
>    *          For a torus map, not all of the triangular shape above is
>    *          taken, but bits are left for wrap in the other direction
>    *          to clean up. The final shape is an "L" or "N". Note an "L"
>    *          is just an "N" with one leg shrunk and added to the other
>    *          reflecting the constraints imposed by the window origin.
>    *          Because of the pre-normalization above, and carefully 
>    *          chosen operations and order, only one final adjustment is
>    *          needed in each direction.
>    *
>    * When adding new target shapes, only this sort of code should be
>    * required, i.e. code that maps a native normal set into a defined
>    * normal target shape set.
>    */
> 
>   if (!is_iso != !topo_hasFlag(TFLAG_ISO)) {
>     int n0, n1, n2, n3;
> 
>     if (is_iso) {
>       ij[0][1] = -1;
>       ij[1][0] = 1;
> 
>       /* x bounds in target view */
>       n0 = DOT(v0, ij[0]);
>       ADD(tt, v0, uv[0]);
>       n2 = DOT(tt, ij[0]);
> 
>       /* y bounds in target view */
>       n1 = DOT(v0, ij[1]);
>       ADD(tt, v0, uv[1]);
>       n3 = DOT(tt, ij[1]);
> 
>       if (topo_hasFlag(TFLAG_WRAPX)) {
>       while (DOT(vv, ij[0]) < n0
>              && (!topo_hasFlag(TFLAG_WRAPY) || DOT(vv, ij[1]) < n3)) {
>         ADD(vv, vv, uv[0]);
>       }
>       }
> 
>       if (topo_hasFlag(TFLAG_WRAPY)) {
>       while (DOT(vv, ij[1]) >= n3 
>              && (!topo_hasFlag(TFLAG_WRAPX) || DOT(vv, ij[0]) < n2)) {
>         SUB(vv, vv, uv[1]);
>       }
>       }
>     } else {
>       ij[0][1] = 1;
>       ij[1][0] = -1;
> 
>       /* x bounds in target view */
>       n0 = DOT(v0, ij[0]);
>       ADD(tt, v0, uv[0]);
>       n2 = DOT(tt, ij[0]);
> 
>       /* y bounds in target view */
>       n1 = DOT(v0, ij[1]);
>       ADD(tt, v0, uv[1]);
>       n3 = DOT(tt, ij[1]);
> 
>       if (topo_hasFlag(TFLAG_WRAPY)) {
>       while (DOT(vv, ij[1]) < n1 
>              && (!topo_hasFlag(TFLAG_WRAPX) || DOT(vv, ij[0]) < n2)) {
>         ADD(vv, vv, uv[1]);
>       }
>       }
>       if (topo_hasFlag(TFLAG_WRAPX)) {
>       while (DOT(vv, ij[0]) >= n2 
>              && (!topo_hasFlag(TFLAG_WRAPY) || DOT(vv, ij[1]) < n1)) {
>         SUB(vv, vv, uv[0]);
>       }
>       }
>     }
>   }
> 
>   /* put things back to standard map coordinates */
>   native_to_map_pos(un_x, un_y, vv[0], vv[1]);
>   return TRUE;
> #undef DOT
> #undef ADD
> #undef SUB
> }
> 
> 
> ------------------------------------------------------------------------
> 
> Index: client/mapview_common.c
> ===================================================================
> RCS file: /home/freeciv/CVS/freeciv/client/mapview_common.c,v
> retrieving revision 1.52
> diff -u -r1.52 mapview_common.c
> --- client/mapview_common.c   2003/07/21 14:18:49     1.52
> +++ client/mapview_common.c   2003/07/22 19:50:28
> @@ -154,6 +154,9 @@
>    }
>  }
>  
> +static void base_canvas_to_map_pos(int *map_x, int *map_y,
> +                                int canvas_x, int canvas_y);
> +
>  /**************************************************************************
>    Finds the canvas coordinates for a map position. Beside setting the results
>    in canvas_x, canvas_y it returns whether the tile is inside the
> @@ -178,23 +181,26 @@
>  **************************************************************************/
>  bool map_to_canvas_pos(int *canvas_x, int *canvas_y, int map_x, int map_y)
>  {
> +  int center_map_x, center_map_y, dx, dy;
> +
> +  /*
> +   * First we wrap the coordinates to hopefully be within the the mapview
> +   * window.  We do this by finding the position closest to the center
> +   * of the window.
> +   */
> +  base_canvas_to_map_pos(&center_map_x, &center_map_y,
> +                      mapview_canvas.width / 2,
> +                      mapview_canvas.height / 2);
> +  map_distance_vector(&dx, &dy, center_map_x, center_map_y, map_x, map_y);
> +  map_x = center_map_x + dx;
> +  map_y = center_map_y + dy;
> +
>    if (is_isometric) {
>      /* For a simpler example of this math, see
>         city_pos_to_canvas_pos(). */
>      int iso_x, iso_y;
>  
>      /*
> -     * First we wrap the coordinates to hopefully be within the the
> -     * GUI window.  This isn't perfect; notice that when the mapview
> -     * approaches the size of the map some tiles won't be shown at
> -     * all.
> -     */
> -    map_x %= map.xsize;
> -    if (map_x < mapview_canvas.map_x0) {
> -      map_x += map.xsize;
> -    }
> -
> -    /*
>       * Next we convert the flat GUI coordinates to isometric GUI
>       * coordinates.  We'll make tile (x0, y0) be the origin, and
>       * transform like this:
> @@ -230,17 +236,7 @@
>       && (*canvas_y > -NORMAL_TILE_HEIGHT)
>       && *canvas_y < mapview_canvas.height;
>    } else {                   /* is_isometric */
> -    if (mapview_canvas.map_x0 + mapview_canvas.tile_width <= map.xsize) {
> -      *canvas_x = map_x - mapview_canvas.map_x0;
> -    } else if (map_x >= mapview_canvas.map_x0) {
> -      *canvas_x = map_x - mapview_canvas.map_x0;
> -    } else if (map_x < map_adjust_x(mapview_canvas.map_x0
> -                                 + mapview_canvas.tile_width)) {
> -      *canvas_x = map_x + map.xsize - mapview_canvas.map_x0;
> -    } else {
> -      *canvas_x = map_x - mapview_canvas.map_x0;
> -    }
> -
> +    *canvas_x = map_x - mapview_canvas.map_x0;
>      *canvas_y = map_y - mapview_canvas.map_y0;
>  
>      *canvas_x *= NORMAL_TILE_WIDTH;
> @@ -252,12 +248,11 @@
>  }
>  
>  /**************************************************************************
> -  Finds the map coordinates corresponding to pixel coordinates.  Returns
> -  TRUE if the position is real; in this case it will be normalized. Returns
> -  FALSE if the tile is unreal - caller may use nearest_real_pos() if
> -  required.
> +  Finds the map coordinates corresponding to pixel coordinates.  The
> +  resulting position is unwrapped and may be unreal.
>  **************************************************************************/
> -bool canvas_to_map_pos(int *map_x, int *map_y, int canvas_x, int canvas_y)
> +static void base_canvas_to_map_pos(int *map_x, int *map_y,
> +                                int canvas_x, int canvas_y)
>  {
>    const int W = NORMAL_TILE_WIDTH, H = NORMAL_TILE_HEIGHT;
>  
> @@ -298,7 +293,17 @@
>  
>    *map_x += mapview_canvas.map_x0;
>    *map_y += mapview_canvas.map_y0;
> +}
>  
> +/**************************************************************************
> +  Finds the map coordinates corresponding to pixel coordinates.  Returns
> +  TRUE if the position is real; in this case it will be normalized. Returns
> +  FALSE if the tile is unreal - caller may use nearest_real_pos() if
> +  required.
> +**************************************************************************/
> +bool canvas_to_map_pos(int *map_x, int *map_y, int canvas_x, int canvas_y)
> +{
> +  base_canvas_to_map_pos(map_x, map_y, canvas_x, canvas_y);
>    return normalize_map_pos(map_x, map_y);
>  }
>  
> Index: common/map.c
> ===================================================================
> RCS file: /home/freeciv/CVS/freeciv/common/map.c,v
> retrieving revision 1.140
> diff -u -r1.140 map.c
> --- common/map.c      2003/05/15 12:38:11     1.140
> +++ common/map.c      2003/07/22 19:50:29
> @@ -1372,9 +1372,6 @@
>  **************************************************************************/
>  void map_distance_vector(int *dx, int *dy, int x0, int y0, int x1, int y1)
>  {
> -  CHECK_MAP_POS(x0, y0);
> -  CHECK_MAP_POS(x1, y1);
> -
>    *dx = x1 - x0;
>  
>    if (*dx > map.xsize / 2) {