> From: Nicola Pero <[EMAIL PROTECTED]> > 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------ _______________________________________________ Bug-gnustep mailing list [EMAIL PROTECTED] http://mail.gnu.org/mailman/listinfo/bug-gnustep
