Re: Release of gui libraries

[Pascal Bourguignon]

> From: Nicola Pero <n.pero@mi.flashnet.it>
> Date: Sun, 27 Jan 2002 12:13:49 +0000 (GMT)
> 
> 
> > 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)

Well, you've just  written that comment. Just add  /* at the beginning
and */ and the end and insert it near the corresponding code ;-)


-- 
__Pascal_Bourguignon__              (o_ Software patents are endangering
()  ASCII ribbon against html email //\ the computer industry all around
/\  and Microsoft attachments.      V_/ the world http://lpf.ai.mit.edu/
1962:DO20I=1.100  2001:my($f)=`fortune`;  http://petition.eurolinux.org/

-----BEGIN GEEK CODE BLOCK-----
Version: 3.1
GCS/IT d? s++:++(+++)>++ a C+++  UB+++L++++$S+X++++>$ P- L+++ E++ W++
N++ o-- K- w------ O- M++$ V PS+E++ Y++ PGP++ t+ 5? X+ R !tv b++(+)
DI+++ D++ G++ e+++ h+(++) r? y---? UF++++
------END GEEK CODE BLOCK------