[Freeciv-Dev] Re: [PATCH] cleanup to canvas_pos_to_map_pos (PR#1183)
[Top] [All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index] [Thread Index]
Ross W. Wetmore wrote:
At 02:54 PM 01/12/31 -0500, Jason Short wrote:
Ross W. Wetmore wrote:
This is the simpler version of what you do. Note, these are basically
equivalent functions in virtually all respects.
[...]
(2) You add the "roundoff" offset, the effects of which I'm not sure of.
I think this is intended to fix the rounding problem, but it fails -
try clicking on a tile in the upper right of the mapview. If it serves
some other purpose, can you explain?
This is not the roundoff problem that you assume. If it were there would
be a discontinuous shift at some point. Instead, it is a scaling failure
that grows in as you move away from the x==y line, as the comments explain.
The effect I get _is_ a discontinuous shift at some point. When I fix
this using divide(), there is no problem.
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.
(3) I instead use the divide() function. I agree, this is unacceptably
clumsy. What alternative do you suggest?
Did you look at the map.h macros?
How about choosing an algorithm that removes or minimizes integer
truncation?
If all else fails ...
#define div(x,y) (x%y < 0 ? (x/y-1) : x/y)
Sounds fine to me.
(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 really need to look at the clumsiness of doing things piecemeal and
fixing up the integer roundoff problems. Just do the rotational
transformation (equivalent to your moving things to different translated
offsets in tiny steps), then scale. Don't try to fix up individual integer
truncation of each small scaling step after the fact :-).
I don't quite understand what you're suggesting. We need to first
scale, then rotate, then un-scale. Both our functions do exactly that.
Why do you need to first scale :-?
This is clearly explained in the comments in the patch :-). To
elaborate even further:
You must first scale because the iso-tiles aren't squares (or
diamond-shaped squares); they are rhombii. Or, to draw it out, a tile
looks like this:
x
xxxxx
xxxxxxxxx
xxxxx
x
If we just rotate by 45 degrees we'll get some bizarre shape, certainly
not the rectangle/square we want. We must instead first scale the above
by multiplying the y value by 2 (assuming
NORMAL_TILE_WIDTH==2*NORMAL_TILE_HEIGHT). 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. We therefore need to scale to
some larger factor than NORMAL_TILE_WIDTH; preferably LCM(N_T_W,N_T_H).
But unless we calculate the LCM in advance, it's faster/easier to just
scale to N_T_W * N_T_H. This is what my patch does.
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.
2. It can now handle isometric tilesets where the
NORMAL_TILE_WIDTH!=2*NORMAL_TILE_HEIGHT.
The fix below is indicated and trivial to implement. It uses the same
philosophy. Probably isn't worth doing until neeeded though.
* Note: use of y*2 and NORMAL_TILE_WIDTH is the optimized form of
* (canvas_y*N_T_H + canvas_x*N_T_W)/(N_T_H*N_T_W) which insures
* that arbitrary points are correctly assigned to the right tile.
* There are four half tiles in the isometric rectangle of dimension
* NORMAL_TILE_HEIGHT*NORMAL_TILE_WIDTH at the topleft origin.
I would change the following lines
That is what the comments say to do, except get rid of the divide().
But it adds 3-4 more multiplications and isn't currently needed. It is
also trivial to do when the rest of the codebase is updated to handle
this. But it is a nitfix.
It certainly is needed, otherwise you'll keep seeing the off-by-one
error. It's unfortunate how slow it is, but such concerns are
insignificant compared to the overall speed of the GUI drawing.
assert(NORMAL_TILE_WIDTH == NORMAL_TILE_HEIGHT);
*map_y = (canvas_y*2 - canvas_x + roundoff) / NORMAL_TILE_WIDTH;
*map_x = (canvas_y*2 + canvas_x + roundoff) / NORMAL_TILE_WIDTH;
to
*map_y = divide(canvas_y * NORMAL_TILE_WIDTH -
canvas_x * NORMAL_TILE_HEIGHT,
NORMAL_TILE_WIDTH * NORMAL_TILE_HEIGHT);
*map_x = divide(canvas_y * NORMAL_TILE_WIDTH -
canvas_x * NORMAL_TILE_HEIGHT,
NORMAL_TILE_WIDTH * NORMAL_TILE_HEIGHT);
This way you avoid the off-by-one error and also allow for when
N_T_W!=2*N_T_H. (Except, of course, that I'd replace "divide" by the
appropriate division, which has yet to be determined.)
The off by one is simply fixed by choosing the origin point (aka using
the roundoff factors) appropriately so there is no problem. The rotation
is a continuous operation, and you just need to pick the line where you
fall over from one tile to the next.
The roundoff factors don't choose the origin, they just hope to get the
rounding correct. I would much rather see the correct solution.
We could choose the origin correctly; i.e.
canvas_y *= 2;
*map_y = canvas_y - canvas_x;
*map_x = canvas_y + canvas_x;
*map_y = (*map_y + A_LARGE_NUMBER * NORMAL_TILE_WIDTH)
/ NORMAL_TILE_WIDTH - A_LARGE_NUMBER;
*map_x = (*map_x + A_LARGE_NUMBER * NORMAL_TILE_WIDTH)
/ NORMAL_TILE_WIDTH - A_LARGE_NUMBER;
but I think the divide() macro you suggest is much cleaner. (Note
stdlib already has a div() function, so that's a bad name.)
Either one of these functions is an improvement to the current code, so
I suggest we propose them both and let the list decide.
No problem ... but I really don't understand what you are missing. It
really shouldn't be that difficult to understand both algorithms, and
if you do it is clear that something that takes 20 lines to handle is
really beating about the bush instead of going straight for it :-).
By "both algorithms", do you mean yours and mine? They're the same :-).
And for the record, I do understand Thue's algorithm also. I just have
trouble visualizing the splitting-a-square-into-triangles part, and find
that I need to draw out the grid to understand the details of it.
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
:-).
jason
|
|
