Closed Bug 63336 Opened 24 years ago Closed 17 years ago

Pixel roundoff problems [gfx]

Categories

(Core :: Layout, defect)

defect
Not set
normal

Tracking

()

RESOLVED FIXED
Future

People

(Reporter: dcone, Assigned: dcone)

References

(Blocks 3 open bugs)

Details

(Keywords: meta, Whiteboard: (py8ieh:dups/deps?))

Attachments

(1 file)

Because we use TWIPs.. and we do not round our starting and ending positions to 
the devices pixel locations.. we have a variety of roundoff problems.  This bug 
report is for encapsulation of all the various bugs due to this problem.
*** Bug 16200 has been marked as a duplicate of this bug. ***
*** Bug 55340 has been marked as a duplicate of this bug. ***
*** Bug 55492 has been marked as a duplicate of this bug. ***
Suggest OS=All (my doublicating bug is on Linux), probably Platfrom=All

Testcase from bug 55492:
http://bugzilla.mozilla.org/showattachment.cgi?attach_id=16506

Keywords from 55492: correctness, css1, polish, testcase

As always, check all doubly marked as doublicate, especially in this case where
the problem is rather broad. (I would have maked it as depend, but since dcone
owns all these bugs ...). CC=<me>
Status: NEW → ASSIGNED
OS: Windows NT → All
Hardware: PC → All
There is no guarantee that a pixel is an integral number of twips.  I've made
that point repeatedly in bug 16200, and it's the cause of the remaining problems
there.  It would make much more sense to use as the basic unit in the layout
engine some fraction (an 8th? a 10th? a 16th?) of a pixel -- it also won't make
computations overflow when given, say, the correct measurements of a huge screen.
Pavlov has some code that removes twips altogether and switches to using 
floating point pixels (aka, GFX2). cc'ing him.

dcone: should we mark the dupes as dependenants instead of dupes?
Keywords: meta
Whiteboard: (py8ieh:dups/deps?)
I don't think using fractional amount will help.  The closer these fractions are 
to pixels will reduce the effects.. but not wipe them out.  Let say you have a 
width on a rectangle 24.6 pixels.  A starting point of .4 pixels will give you a 
rect of 0 to 25.  A starting point of .6 will give you 1 to 25.  This will round 
off incorectly (make your rectangle smaller from 25 to 24 pixels). This is a 
simple example.. but is the cause of our problems. The widths of our graphics 
have to be rounded to the destination platforms native pixel if the destination 
has a lower resolution.
What you describe isn't a problem at all as long as we scroll by integral
numbers of pixels and our coordinates are a fraction of a pixel.  It doesn't
matter if it rounds differently from different starting positions.  It does
matter if it rounds differently as you scroll (at least, for bug 16200 -- I
haven't looked at all the other dups here).  Rounding differently as you scroll 
*will* happen with the current system if a pixel is not an integral number of
twips.
This happens without even scrolling.  The scrolling would help to be on this 
boundary.. and the y direction would be ok.. but if you resize the document this 
happens in the x direction.. not just on scrolling.  For your particular problem 
there are solutions that minimize this.. but the core problem is still there.. 
The problem I described is an example also.. there are other cases were this 
kind of rounding creeps in (hence all the other bug reports)  Widths of bounding 
boxes, bezier curves, etc all suffer from this problem.  The thinking of the 
oringal author was "as long as  everything is rounded the same even if 
it is a little off, everthing will be fine.. and this does not work.
Summary: Pixel roundoff problems → Pixel roundoff problems [gfx]
Target Milestone: --- → Future
Aren't all of 80530, 109296 (?),112673, 118687 (?), 120918, 121920, 122577,
131107, 132164 (?) dupes of this problem?
Blocks: 134942
So is there no workaround?  I basically can't use Mozilla as my normal browser
until this bug is fixed or I have a workaround.
As a workaround, you could try setting Mozilla's DPI to an integer divisor of
1440 (such as 60, 72, 80, 90, 96, 120, 144, or 160.)  For instance, my display
has a DPI of 100 which corresponds to 1440/100=14.4 twips/pixel.  Changing it to
96 DPI (under Appearance/Fonts), I get exactly 15 twips/pixel.  This seems to
eliminate the problem for me.
OK, that's a good workaround.
Here is the problem.. I will create an example.
this shows with different starting and ending points.. but the same with, after 
conversion to pixels and rounding.. you end up with different pixel widths.  You
need to have all things that go to the screen.. put on pixel boundaries.

             1st coord                                   2nd coord
         start     width      end            start       width            end

TWIPS    40       17          57              36         17               53
Pixels   2.66     1.13        3.8             2.4        1.13             3.5
Rounded  3.0      1           4.0             2          2                4

There may be values that minimize this.. but nothing guarentees it will always work.
That doesn't imply that everything needs to be on pixel boundaries, as long as
we always scroll by round pixel amounts (which we do).  See bug 16200.
(Bug 152671 does discuss problems when things are exactly at a half-pixel
boundary, but one would think that could be solvable by better rounding behavior.)
This isn't just about scrolling.  I've had rounding bugs show up during a page's
initial drawing, depending on the timing of image fetches.  For example, on
http://perlmonks.org, the text navigation menu at the top has had the bottom
half of letters shifted a pixel over when the image to the left of the text
comes in.
My comments in 14 show that this is not just a scrolling problem.. if you want
this to go away.. totally.. we have to control what twips values we use (methods
that control which values are used) .. or go to a different core value that
guarentee that rounding works consistenly with pixels.
If this isn't a scrolling problem, then you shouldn't have marked bug 16200 a
duplicate of this bug.  Bug 16200 is a scrolling problem, and still exists, and
can be fixed.

Comment 14 alone doesn't demonstrate any problems that can't be fixed by
ensuring p2t is an integer, scrolling by integral numbers of pixels, and
ensuring consistent rounding.  Could you explain where such bugs exist?
14 does demonstrate this  The right side is case 1, left side case 2.

1.)  Row one is in twips.  Those number are converted to pixels in the second 
     row.  Not rounded yet to show the widths are the same in case 1 and case 
     2.
2.)  Row three is Rounded using a consistent rounding algorithm (basic
rounding).    
     This shows case 1 has a 1 pixel width, case 2 has a 2 pixel width.

This table 
shows exaclty what you wanted.  Converting from twips to pixels consistently
rounding the result.

So I respectivly disagree, comment 14 shows that the problem can not be fixed by
ensuring p2t is an integer and ensuring consistent rounding.  Scrolling integral
numbers of pixels... can help.. but in cases of certain widths (buttons, borders
that need to match from one side of a table to another, it will still not work.
 Also resizing the window, scrolling, moving objects around the screen..
anything that positions elements at different places can cause problems (or is
appears the sizes change). Also for things like drawing borders.. rounded
borders to be exact.. the start and stop of going into the rounded parts can be
slightly off and make the button/element look odd.  We have cases where radio
buttons look a little odd for example on the screen but printed out look
perfect.  Its because of this reason that happens.
So the bug you want to fix is that 'width: 50pt' might equal a different number
of pixels at different places on the page?  I don't think that bug is worth
fixing, considering that your proposed fix would introduce serious problems with
cumulative percentage widths (e.g., 4 floats with width of 25% might force the
4th onto the next "line" or would leave a gap at the left of the page).

You can also do appropriate rounding to pixel edges before computing the rounded
borders (at whatever pixel offset we happened to round the edge to).  It doesn't
require layout to have frame boundaries at pixel edges.  So that's not an issue.

Are there any bugs that using fractions of pixels causes that (1) we actually
need to fix (unlike my first paragraph above) and (2) can't easily be fixed in
other ways (like the second paragraph above)?
batch: adding topembed per Gecko2 document
http://rocknroll.mcom.com/users/marek/publish/Gecko/Gecko2Tasks.html
Keywords: topembed
Depends on: 171282
Keywords: topembed
So is the use of TWIPs what causes a 13cm line to appear 14cm long on my display
set to 103 DPI in Mozilla, an error of ~7.7%?
Partly, since we force the pixels-to-twips conversion to be an integer to avoid
rounding problems (see bug 16200, which was for some reason marked a duplicate
of this bug).
The problems lies.. in the use of Twips.. and allowing these twips values (for
anything going to the screen) to fall inbetween pixels.  This might be ok..
except for the error is cumalitive and we dont keep track of that error.  So if
lengths are being calculated.. the starting point of that length is critical..
because depending on where it starts.. it can effect the end point.. causing the
length to  be rounded up or down based on this starting point.  eg.. the length
will always be 10.4 pixels.. but when added to a starting point that can vary..
the fractional portion of that endpoint might be .4 or point .5, these values
will round to different integer values.. and thats where we get the pixel
difference problems.  Solving this requires either we always make sure we are on
pixels boundaries or we keep the error for all the calculations.
Blocks: grouper
Bulk adding topembed keyword.  Gecko/embedding needed.
Keywords: topembed
Keywords: topembed
> So is the use of TWIPs what causes a 13cm line to appear 14cm long on my display
> set to 103 DPI in Mozilla, an error of ~7.7%?

This bug would be fixed by my proposal in bug 177805. We would measure
everything in pixels (CSS pixels, to be precise) instead of twips, and the
103dpi value would only be used by the style system to convert 13cm into the
appropriate number of CSS pixels.
Depends on: pixels
We can't put everything on pixel boundaries. Consider the following document:

<div style="height:0.2px; background-color:red"></div>
<div style="height:0.2px; background-color:gren"></div>
<div style="height:0.2px; background-color:blue"></div>
<div style="height:0.2px; background-color:black"></div>
<div style="height:0.2px; background-color:white"></div>

We simply can't render this thing in a reasonable way at 1:1 scale. We are going
to have to make some approximations and something is going to be lost.
Our basic problem here is that the canvas is conceptually a continuous plane,
but we need to map that plane onto discrete pixels. We need to choose the color
to draw for each pixel (x,y) where x and y are integers.

Here are some options:
A) the color of pixel (x,y) is the color of the point in the plane at (x,y)
B) the color of pixel (x,y) is the average color of the region in the plane
(x,y)-(x+1,y+1)

Ideally we'd implement B), which is essentially anti-aliasing. Some GFX
implementations might be able to implement B) but with most APIs only A) is
implementable.

Here's how A) works out if properly implemented, in dcone's example:
             1st coord                                   2nd coord
         start     width      end            start       width            end
Pixels   2.66     1.13        3.8             2.4        1.13             3.5
A)       3         1          4               3          1                4
Both line segements cover exactly one integer pixel, '3'. So we turn pixel 3 on.
This corresponds to always rounding 'start' and 'end' *up* to the nearest pixel.

Other rounding schemes correspond to sampling the plane point (x+0.5,y+0.5),
etc. As long as we round consistently, all the rounding schemes have basically
the same properties. In particular, there is *no way* to have an area with
fractional length L displayed using the same number of pixels no matter what the
fractional offset --- not without breaking the actual layout of the areas. See
my example. To reiterate: forcibly positioning elements on pixel boundaries
breaks layout.

If we avoid that, but we have consistent rounding, and layout is in fixed
fractions of CSS pixels with integer arithmetic and no roundoff errors, then
objects that are aligned by layout constraints *will* be aligned visually. The
main problem I can see is that objects with non-integral length that are moved
by a non-integral offset may change visual size by one pixel. I think that's the
very best we can do, short of full anti-aliasing.

If we agree that layout should not be broken to position elements at pixel
boundaries, then the problem of how we sample a continuous scene is fairly
independent of the units we use to layout the scene, as long as layout doesn't
introduce any roundoff errors of its own.
Apparently some authors (and maybe browser implementors) want us to round
everything to pixel boundaries before we do layout. See bug 178330.
I'm trying to think of a situation where rounding all frame boundaries to pixel
units would be bad. I'm a bit worried about subpixel positioning of text, which
would then make
<p>HelloKitty
<p>Hello<span>Kitty</span>
lay out differently. We don't support subpixel text measurement and positioning
yet (I think) but it's something we might want to support before too long.

dbaron's example of a number of %-width elements failing to add up to the widget
of the parent box is valid but it's important to note that there's really no way
we can avoid that in general (except by using exact rational numbers for layout
coordinates, which is implausible).

A compromise approach might be to round all non-px CSS lengths to device pixels
in the style system. That would fix bug 178330, because any sensible rounding
scheme for GFX would have the property that a primitive graphic object whose
size is an exact multiple of a device pixel will be displayed with exactly that
many device pixels, no matter what the fractional offset.
Actually, bug 178330 shouldn't be a problem if we have consistent rounding in
GFX, because the border widths are all exactly 1px. If we always round
consistently (so that round(x - I) = round(x) for all real X and integer I) then
anything which is an integral number of pixels wide will be displayed with an
integral number of pixels. It's only em-height rectangles or lines (or
in-height, or fractional px) which can be displayed with different height in
different positions.

So I'm marking 178330 as a duplicate of this.
*** Bug 178330 has been marked as a duplicate of this bug. ***
*** Bug 182670 has been marked as a duplicate of this bug. ***
Another flavor of this problem, highly more visible than just internal
calculation, is the value of the "computed style" you can see in DOM-Inspector.

This is the original comment I submitted in bug 182670:
----
I've got the default font-size of 16px (edit>preferences>appearance>fonts), and
an author stylesheet setting an element to 90%.

Normally, the computed value should be 16px*90% (mathematically that would be
16*0.9) which yelds 14.4px. However, the DOM-Inspector yelds 14.3529.
This bug has previously been about rendering errors, not about style data. 
Marking as a duplicate seems inappropriate, although a dependency may be.
Blocks: 182670
Blocks: 159880
This discussion is way over my head, but I did make a test case to clearly display the rounding problem:
http://users.rraz.net/mc_on_the_rocks/testpage/temp/Round-error.html
It's just a five-by-five matrix, composed of AP boxes, all with percentage sizing. No line-height, no padding, no borders, no margins. It should appear as a solid black box. Rounding errors appear as horizontal/vertical lines thru the box. The test fails in every browser I've tried. Hope this is useful.
The construction is a 5x5 AP box matrix, and should appear as 
a single black box. The AP boxes are percentage sized, and
are not complicated by margins, padding, borders, or line-height.
BTW, if you bring up the Moz sidepanel and drag it, the gaps
will shift 'on the fly'. Very cool.
Okay, since dcone isn't working on Gecko anymore I'm going to make a decision by
fiat. We will not adjust coordinates in layout except in situations where CSS
gives us some flexiblity or where we absolutely have to to avoid poor display of
legacy content. It is the job of each GFX implementation to sample the
continuous display plane in a consistent way.

Since we share code among GFX implementations and we currently don't have any
antialiasing GFX implementations, we should use the same sampling scheme for all
GFX implementations. Right now I'm not sure whether we should use rounding or
truncation (which correspond to sampling at (x+0.5,y+0.5) or (x,y)
respectively). Anyone have any thoughts?

nsTransform2D.cpp currently converts a rectangle (x,y,w,h) by rounding (x,y) and
(w,h) seperately. That's wrong; it should at least round (x,y) and (x+w,y+h) to
make sure we get the right pixel coverage. But I wonder if there are other
places where we're doing truncation instead.
Given that we already use rounding in nsTransform2D, albeit incorrectly, I guess
it's clear we should just stick with that. Let's round all pixel coordinates.
Depends on: 199935
Depends on: 94739
Blocks: 233357
So, if I understand correctly, a first step would be to convert the integer
TWIPs to float's... After that the rounding issue can be addressed. Right?

Well, I tried changing the 'nscoord' datatype from PRInt32 to float (by the way:
it is defined twice. strange?) as an experiment. This *should* work, because
this was explicitly designed so that it could afterwards be changed to another
type...

However, unfortunately many routines assume nscoord to be of the PRInt32 type,
and don't bother to use a cast on it. So this breaks the flexibility, and all
those instances have to be manually corrected.

I did some work on that, and it doesn't seem too hard, but I have no idea how
much work it will be to get everything building again. At first sight I think
that you can at least expect a lot of manual labour.


~Grauw
I don't think floats are necessarily the solution.
I'm strongly against using floats for Gfx coordinates. I'm sure I stored a rant
about that in Bugzilla somewhere.
Correct: I'm strongly against using floats in layout. floats in Gfx interfaces
might be OK.
Blocks: 250051
Blocks: 225597
Blocks: 230101
Depends on: 97861
(In reply to comment #39)

> nsTransform2D.cpp currently converts a rectangle (x,y,w,h) by rounding (x,y) and
> (w,h) seperately. That's wrong; it should at least round (x,y) and (x+w,y+h) to
> make sure we get the right pixel coverage. But I wonder if there are other
> places where we're doing truncation instead.

I thought a bit about that, and without correcting everything, it is absolutely
necessary to round x, y, x+w, y+h and not x, y, w, h. Sure we then would have
some objects set to the same length in layout and not having the same pixel
coverage, but it is not as important as one may think : alignment would be
achieved nevertheless correctly, because if two objects start at the same pos
and have the same width, it is OK.

And that would correct at lot of annoying problems (in fact, I think every
problem of adjacent objects getting over each other for one pixel, or being
separated by one pixel, would be solved). In particular, when I create html +
css pages, I use a combination of ex/em (for everything but border-like lengths)
and px (for borders and similar). And my page layout requires a margin to be
exactly 2px, I like to have 2px everywhere (or else it looks very
unprofessionnal...). For such a kind of layout, see http://www.komite.net/pl,
the news block.

Just correcting the choice of values to be rounded would solve this problem with
a lot of other ones, because if the rounding function ensures r(x + i) = r(x) +
i for each integer i, then a integer length constraint in pixels would be
correctly rendered everywhere with the correct nb of pixels...

Everything is not corrected, because if we want .3ex or 2.1px margins, then that
wouldn't be rendered the same everywhere.

But if we round x, y and w, h, then the drawn rect is
r(x),r(y),r(x)+r(w),r(y)+r(w) [usualy drawn left and top inclusive and others
exclusive] The following object's starting point is for instance x + w in
layout, so its drawn starting point is r(x + w) != r(x) + r(w) in general. So we
get adjacency problems.

Sorry I spoke a lot to in fact repeat what was said in comment 39, but I really
think this tiny part of the bug should be corrected now, even if a satisfactory
solution hasn't been found for the rest of it, because whatever solution is
considered, it *should* do as Robert O'Callahan said, to get the right pixel
coverage, without gaps/overlapps.

I wonder, if it is just a matter of changing such really tiny rounding
functions, it may be feasible even by a guy like me that isn't aware of the
subtleness of the code of Gecko, or is the rounding code oddly spread accross a
whole crowd of functions ?

NB: The bug is as visible in Gecko 1.8b1 as in current Firefox one.

_FrnchFrgg_
This seems fixed by Bug 177805. The testcase no longer breaks up when I resize my Window (although the box forgets to resize sometimes).
Apparently it is.
->RESOLVED FIXED
Status: ASSIGNED → RESOLVED
Closed: 17 years ago
Resolution: --- → FIXED
The test case still breaks for me if any page zoom is applied. I don't know enough to know if that is a problem with page zoom or with this.
Page discussing this problem at http://www.positioniseverything.net/round-error.html still shows this problem. FF 2.0.0.7 @ 1280x1024 draws a vertical line through the right side of the box at full screen, but at smaller window sizes the box displays correctly.
(In reply to comment #49)

This bug is fixed on TRUNK, Gecko 1.9. That will be in Firefox 3.0. 

Could you provide a simple solution that implementers of other engines (notably Webkit) could reuse ?

In summary, is the solution adopted all about rounding ONLY the pixel coordinates and NEVER any width (which will just be recomputed from the coordinates) ?

And what happens when zooming is applied ?

I really hope that such fix which is impressive in Firefox or browsers based on Gecko layout engine should be made available to other browsers so that they can fix it, for better interopability of web designs. And the solution should be really explained, as this is the philosophy of open-sourcing, and web designers need to have a clear and simple solution for their webpages.

In fact your solution should even be exposed in the CSS specifications (for inclusion in CSS 3 draft specifications). Could you prepare a paper about this, and submit it to the W3C, or at least publish it on your website and link to the page of your article on some wellknown CSS-discussion sites (W3C mailing lists, positioniseverything, webinars...) ?
See
http://weblogs.mozillazine.org/roc/archives/2007/02/units_patch_lan.html
http://weblogs.mozillazine.org/roc/archives/2007/10/a_tale_of_two_z.html
and others.

I think Dave Hyatt and others in Webkit at least are well aware of what we've done here.

I don't think exactly what we've done needs to be standardized. Probably some of the features of our solution should be standardized.
You need to log in before you can comment on or make changes to this bug.

Attachment

General

Creator:
Created:
Updated:
Size: