Re: Release of gui libraries

[Nicola Pero]

> Ok, I this bug is most probably caused by the fact that the 
> height is rounded up from 187.942856 --> 188.
> The following patch will always round the size of the 
> rectangle down.

No - this patch is not correct - I'm sorry we don't have a regression
testsuite, but this patch would reintroduce many subtle bugs in drawing
which I thought I had fixed forever ... garbage appearing on multiple
resizing of windows etc ... bugs which were fixed precisely by fixing the
code to floor the extreme points of each rectangle, and compute the size
as the result.

That was time ago, when I debugged the resizing/autoresizing of views ...
so I gave the matter quite a good deal of reflection.

There is the 'abstract' space where the gui draws ... a perfect ideal
postscript-like space where everything can be drawn with arbitrary
precision, and all coordinates are real numbers.

There is the 'device' space which is the actual screen ... an imperfect
device which only supports integer coordinates.

We need to map geometrical figures from the abstract space into the device
space.  So we need a function mapping each point in the abstract space to
a point in the device space.  We use floor on the coordinates of each
point to map it from the abstract space to the device space - this is not
a chance, in my understanding, this is the only reasonable thing to do.

Consider the problem on a line.  The abstract space is the set of real
numbers R.  The device space is the set of signed integers Z.  The mapping
we look for is a function f: R --> Z.  Here is my reasoning -

 For each n \in Z, f(n) = n.  This simply means that if you draw points
   in the abstract space using integer coordinates, then these
   drawings are reproduces without changes in device space.

 For M \in Z and x \in R, f(x + M) = f(x) + M.  This just means that the
   mapping is homogeneous: the mapping does locally work the same,
   regardless on the position.  (please note that I require that only
   for M \in Z, so it is not completely true! If you require it to work
   for arbitrary M \in R, then there is no f satisfying the requirements).
   It follows easily that once we determine the value of f(x) for each
   x in the interval [0 to 1), we have determined f.

 For x \in R and y \in R, x < y implies that f(x) <= f(y).  This is pretty
   important - it means that if points have a certain order in the abstract
   space, they should be mapped to points in device space which are in the
   same order.  It's an obvious requirement, but very powerful.  We 
   immediately infer that for each x in the interval [0 to 1], f(x) is either
   0 or 1 (0 <= x <= y implies 0 = f(0) <= f(x) <= f(1) = 1 and because 
   f(x) is integer, it can only be 0 or 1).  Now consider the set of x 
   in that interval such that f(x) = 0.  This set has a sup (basic properties
   of real numbers), let's call it A.  Now it's obvious that for each x
   inside (0, 1] such that x > A, f(x) = 1, because A is the sup of the x
   so that f(x) = 0, which means all x such that f(x)=0 are < A.  It's also 
   quite trivial that for each x in the same interval such that x < A, f(x) = 0 
   (follows trivially from the definition of sup).  f(A) might either be 0
   or 1.

Our conclusion is that

 there exists a number A \in (0, 1] such that f(x) is

  f(x) = floor (x + 1 - A);

(considering f(A) = 1; if f(A) = 0 you get similar functions which
differ only on some points).

These functions are all equivalent, so choosing A is just a matter of
taste.  Because our boundary conditions normally are that in a window the
abstract space starts at 0, and so does the device space, and if the
window has size 15 pixels, the abstract space is [0, 15) and the device
space is pixels from 0 to 14, to be sure that all points inside the
available abstract space are mapped to points inside the available device
space, we just choose A = 1, and f(x) = floor (x).  I suppose if the
origin of the window lies on a non-integer coordinate, you might want to
make a difference choice, but I never investigated seriously this issue,
since we always put windows at integer coordinates.

I hope I demonstrated enough clearly that the only way to map the abstract
space into device space which fulfills some basic geometrical requirements
is to map each point by flooring its coordinates.  To map a segment, you
need to map all the points in the segment.  This wouldn't be very easy,
since there are uncountable points in a segment.  But the properties of
the mapping help you. Suppose the segment starts at x (abstract space) and
ends at y (abstract space).  If you map x into device space, and y into
device space, and draw a segment in device space from x to y, then because
for each p in abstract space such that x <= p <= y, then f(x) <= f(p) <=
f(y), then this segment contains all the f(p) for each p in the segment in
abstract space.  So this trick does the job - you floor each endpoint,
then draw a segment between the floored endpoints.  The lenght of the
segment in device space is floor(y) - floor(x), which is not necessarily
obtained by rounding the lenght of the segment in abstract space - that
operation would give floor(y - x) [according to you - I'm not sure why
floor and not another rounding function], but because floor is non-linear,
this is *not* the right length floor(y) - floor(x), even if the difference
should be little.  It is quite obvious that, due to the fact that device
space has so few points compared to abstract space, some sort of uneveness
of drawing happens, depending on exactly where the segment starts and
ends.  Nothing we can do about it - we must stick to what the theory
suggests, because if you don't, then you implicitly break some of the
basic requirements above ... and will soon get into geometrical
absurdities when drawing.

Your patch does break an even more basic requirement - the requirement
that the mapping maps points in abstract space into points into device
space - that is, that the same point in abstract space is always mapped to
the same point in device space.

As a practical example of why flooring the lenght of a segment will
produce geometrical absurdities, consider the following very realist
example -

we draw a dark grey area from 0.5 to 2.1 (we ignore the y coordinate, and
only work on the x coordinate - you may freely imagine that the area is a
rectangle extending in the y direction as much as you wish). Then we draw
a black area from 2.1 to 4.0.

If you draw this thing in the correct way, you first draw a dark grey area
from floor(0.5) to floor(2.1), which means you draw pixels 0 and 1 and 2
dark grey.  Then you draw the black area from floor(2.1) to floor(4.0),
which means you draw pixels 2, 3 and 4 black.  After all is said and done,
the first area is 2 pixels, the second one is 3 pixels.  It's all a bit
uneven because it's just like trying to fit a hand-free drawing into a
pixelized screen.

If you draw this thing in your way, you first draw a dark grey area
starting from floor(0.5), and with a lenght of floor(2.1 - 0.5)=floor
(1.6)=1 pixels.  Which means, you draw pixel 0 only, because the length in
pixels must be 1.  Then, you draw the black area starting from floor(2.1),
and extending for floor(4.0-2.1)=floor(1.9) pixels, which is 1.  So the
black area will cover pixel 2 only.  Now examine carefully the situation -
this has generated a geometrical absurd - the two areas were touching each
other, they were covering all the space from 0.5 to 4.0 in abstract area!  
In device area instead, now pixel 0 is dark grey, pixel 2 is black, and
pixel 1 is *not* drawn!  A ghost line appeared between the two areas!  
Most likely this line will not be drawn at all, so old garbage will still
be present on the screen in this line - and we'll start getting (again)
bug reports saying that they have filled two rectangles, they are covering
all the area in the code, but on screen if you resize the window a couple
of times (which normally causes the views to autoresize themselves,
generating any sort of floating point coordinates everywhere) what
actually happens is that garbage appears between the two rectangles!

The reason why this problem happens is that in abstract space, the
endpoint of first area is the same point as the startpoint of the second
area.  If you want to preserve basic geometrical characteristics, you need
to make sure that when you map abstract space into device space, the
endpoint of the first area is still the same point as the start point of
the second area in device space - no garbage pixels should appear in
between.  Because the startpoint of the second rectangle is mapped into
device space by using floor on the coordinates, if you want the endpoint
of the first rectangle to be mapped in the same place, the only way you
can do it is by using floor on its coordinates as well.  If you floor the
size, you will *never* be safe that the end point of the first matches the
start point of the second, and that is *critical* to avoiding garbage
appearing on screen - the only way to make sure the endpoint of the first
and the start point of the second match is to map them in the *same* way,
which means you always need to convert all points in the same way, and
only infer lenghts and other geometrical properties as a consequence of
converting points.

You need to map each point in abstract space to a point in device
space in a unique way, you can't map the same point in abstract space
into different points in device space (as your patch does) otherwise
geometrical figures which touch in abstract space won't any longer
touch in device space, void garbage pixels start to appear everywhere
on screen, and you get into any sort of subtle geometrical horror.

Long time ago, the original code did floor the sizes of the rectangle.
That used to produce a huge amount of very complex and baffling bugs, I
remember for example that lines were disappearing from the font panel
after repeated resizings of the panel.  That was all fixed by thinking
carefully at how the mapping from abstract space into device space must be
done, and fixing rectangle conversions to floor endpoints, and not
lengths, as the geometrical reasoning show it must be done.  It's a pity
we don't have a regression test, so I might not remember how to reproduce
all the bugs we used to have - but we can't go back that way.

I also do remember that the image compositing code was doing the
coordinate roundings wrong.  I don't think I fixed that, because when I
tried doing it, drawing of images broke everywhere, and since there was no
bug filed at the moment caused by that wrong rounding, I didn't
investigate it further (as I knew nothing about the image drawing code),
and got caught in development of other stuff and I forgot about it later
on.

I spent some hours writing this explanation - I hope it both explains why
I'd like this patch not to be applied, as it would be simply like
reverting to old buggy code, and hopefully - by explaining in all details
the reasoning behind the way we round coordinates - might help you (or
whoever else) in the task of fixing (in the right way) coordinate
roundings in the image compositing (and any other coordinate roundings we
might need to do), if you want to do that.

I'm very happy that you are working on this area, and please don't
consider this as a 'stopper' for your work in this area ... my intention
in writing this email was to share my experience in this area and not to
stop you from working in it, I'm very happy you're doing that.  I know
it's difficult to work with those libraries because the history is very
complex, so it's never obvious which parts of the code are well-done and
which are not ... you see obvious silly bugs and hackish approximate code
just lines after or before code which has instead received lot of thought
and attention, and there is no sign telling you which part is more likely
wrong.

(between myself and myself - perhaps I should have commented the code more
to make clear it was that way not for a chance)