[Freeciv-Dev] Re: [PATCH] cleanup to canvas_pos_to_map_pos (PR#1183)

["Ross W. Wetmore" <rwetmore@xxxxxxxxxxxx>]

At 10:39 PM 01/12/31 -0500, Jason Short wrote:
>Ross W. Wetmore wrote:
>
>> At 02:54 PM 01/12/31 -0500, Jason Short wrote:
>> 
>>>Ross W. Wetmore wrote:
>> I think it might have something to do with the way the tiles are drawn,
>> in that they overlap one or two pixels and thus near the edges you have
>> lost almost a full tile. Try locating the edges tile by tile out from 
>> the center rather than just doing one at the edge to get a better handle 
>> on the issue. I think tiles are really (NORMAL_HEIGHT-1) in size :-).
>
>Well, I'll take another look at this.
>
>> The roundoff parameter I use allows one to fine-tune the mouse clicks
>> so you get them more or less centered, and yes in part this fixes the
>> integer scaling truncation issue at a single point, but much more 
>> flexibly. I experimented a lot with this until I gave up and set it to
>> a best compromise. It is really a two parameter origin shift as the 
>> sign and multiplicative factors are the real twiddle elements.
>
>Your code still suffers from the error.  The only way to fix it is to 
>fix division, either by manually correcting the error for negative 
>remainders or by adding on a sufficient quantity to assure the value is 
>positive.

There may be a negative division issue, but I don't see the discontinuous
shift effect it should produce in practice, and I believe you may need to
think harder about your conclusions here (see below :-).

If you think of doing mouse clicks in a region of the canvas, and then
based on the origin point for this region determine an (integral) tile
value, it might be clearer what the roundoff issue is.

But the scaling issue arises from the initial (multi-tile) difference where
for every tile out the region is a little more offset in a given direction
or alternatively the center-point is a little more off. You should have the
same problem.

>>>(4) Your math is one line, whereas I separate each step.  This is a 
>>>matter of preference.  Your way gives fewer lines of code; mine allows a 
>>>more thorough explanation of the steps involved.
>>>
>> 
>> The operation is a rotation and the formula for rotation by 45 degrees is 
>>   x' =  x + y;
>>   y' = -x + y; 
>>      or 
>>   y' =  x - y; going the other way
>> 
>> which are done on two lines. Adding 18 more doesn't really improve the
>> conceptual understanding IMHO, nor does manufacturing extra steps :-).
>
>But the additional calculations are necessary, because you must scale 
>both before and after the rotation.  The only question is to add this 
>into the two-line code or split the operations.
[...]
>You must first scale because the iso-tiles aren't squares (or 
>diamond-shaped squares); they are rhombii.  
[...]
>We must instead first scale the above 
>by multiplying the y value by 2 (assuming 
>NORMAL_TILE_WIDTH==2*NORMAL_TILE_HEIGHT). 

Correct. I have not been calling this scaling, which I think of as the
canvas to tile conversion. The canvas to square is just implementation
tricks to make things more tractable in my view. So we are saying the
same things here, and the dispute is from semantic flipflops :-).

> Then we can do the rotation, 
>then scale again to reduce it to an integer value.  The only integer 
>truncation is in the final scaling, and the only trick is to make sure 
>it's truncated properly there.
[...]
>You do this initial scaling, just as I do.  But my patch takes it a step 
>further by not assuming N_T_W==2*N_T_H. 

I think the usefulness of general squaring at this point is still debatable 
but I'm not adamant about it.

>> Just rotate and do a final scaling, especially since things are nice whole
>> integers in canvas coordinates all the way.
>> 
>> You may be hung up on the current implementation, and not really thinking
>> about the real problem. Think out-of-the-box and see if that helps.
>
>I hardly even understand how the current implementation works, so 
>there's no fear on that one :-).  To achieve my algorithm, I just came 
>up with the inverse of what was used by map_pos_to_canvas_pos().  Then I 
>looked at your code, and found out your algorithm was (approximately) 
>equivalent.

Actually, if you pay attention to the +/- on the diff and sort through a
lot of the variable rename and commentary noise, ours are the same except
for the square scaling and the division() vs roundoff.

But, let me see if I can explain the two (ours/original) in one spot to 
help the general enlightenment process.

First, what one really *wants* to do is a simple pi/4 rotation. Which 
mathematically looks like ...

  | 1 1 |  |x|    |x`|
  |     |  | | -> |  |
  |-1 1 |  |y|    |y`|

 ... plus a scaling operation because canvas coordinates are a finer
granularity than tile (plus a coordinate origin translation). 

But the latter is complicated if the x and y scaling factors are not the 
same, or conversely the rotation would not be a simple pi/4 but something 
like (note these are the mathematically correct sin/cos values) ...

  | N_T_H/(N_T_H*N_T_W) N_T_W/(N_T_H*N_T_W) |  |x|    |x`|
  |                                         |  | | -> |  |
  |-N_T_H/(N_T_H*N_T_W) N_T_W/(N_T_H*N_T_W) |  |y|    |y`|

You can do this in two ways. 

First, you can factor out the denominator, do the rotation steps to get
x", y" by the appropriate linear combination and then divide by the 
denominator. Note this does leave the numerator square scaling or its
optimized factor in. But this is not really canvas scaling, rather square
scaling as you recognize. (Be fair in your comments and recognize when
you have changed the context to justify a statement or contradict mine. 
We aren't fighting a dirty political campaign, just trying to make things 
mutually clear, I hope :-). When you do the denominator division you need
to account for the tile center to tile origin shift to get the roundoff
right. 

The other way, you can convert each x and y individually to tile 
coordinates by evaluating each element of the linear combination 
separately. But this ignores partial elements, i.e. integer truncation.
If you are more than halfway into the next tile (complicated by the
fact that four separate tiles touch at the center of the N_T_H*N_T_W
rectangle that lies off the truncated tile origin point, i.e. 2-D
halfway), you need to possibly bump one or both of the tile values.
Thus the current implementation does a lot of if-clause fixups after
the fact. You can get rid of these fixups with a simple origin shift
up front (aka the roundoff shift).

Does this make things clearer vs the original?

Now a little bit of speculation. 

In the canvas_to_city case, the canvas coordinates are always +ve.
Thus the divide problem never occurs in scaling to tile values. I think
this means that there is nothing to be done here in either code case.

In the canvas_to_map case, again canvas coordinates are always +ve. The
EXTRA_BOTTOM_ROW shifts are handled explicitly (in my world anyway) and
the map_view_x0,y0 values take this into account, so even though one
might think that the canvas origin point is inside the canvas borders
and thus there could be negative canvas coordinates, there really can't.
At least not when coordinates come from mouse clicks on the map which is 
what really uses this code.

Now, for the tricky spot. When you defer the scaling to after the linear
combination, it still doesn't result in a divide issue. In the x coordinate
case, everything is still always +ve. Only in the y-case can there be a 
negative issue. But the two roundoff effects are in opposite directions,
and if you expanded the y-case, I think you will find they exactly cancel
in all instances that matter (the borderline pixels may go the otherway).

Thus the divide isssue is really a red herring and not affecting anything,
except that you probably introduce a bug with yours when it does kick in,
and I suspect that you really haven't got a (0,0) tile center/origin 
roundoff in your case, but that depends on how you defined map_view_x0,y0 
to some extent.

>> I'd really like to see the functions return proper status values when they
>> go in. Then other places that use them can be cleaned up to deal with the
>> failure modes properly. This is for me a far more important concept to
>> get right.
>
>I agree it is important, but it's also a much bigger change.  This 
>change is non-intrusive, only affecting this one function (and possibly 
>introducing a new macro).  And it's easier to push such a change if we 
>first put the function into a form the maintainers can easily understand 
>:-).

Actually, fixing these functions to return a proper condition doesn't
affect anything more than the header definition at the moment since they
currently return void.

If you look in map.h, you will see that nearest_real_pos actually is
just normalize, with fixups when this fails but still returns a FALSE.
Thus it is perfectly consistent with both the correct and the void-tile
style hacks. This means that the followup changes can be done as they
are found.

But the remaining fixups to *use* the condition are more intrusive, I
agree. 

I think it is worth doing the work here right now in preparation.

>jason

Cheers,
RossW
=====