Created attachment 3547 [details]
EPS file that exhibits bleed-through when rendered with anti-aliasing

This file exhibits the problem that I described in the associated bug report.

Created attachment 3548 [details]
Output from ghostscript that exhibits the bug

This file is the output of the command listed in the bug report on my machine
(Linux Fedora Core 6).	If you look very closely along the boundary between the
gray and the blue, there is a white line showing through.

Created attachment 3550 [details]
screenshot.png

I don't believe the behaviour is defined.  The left image in the screenshot.png
is Adobe Photoshop CS3, the middle is Apple Preview, and the right is
Ghostscript 8.56 (Apple Preview is rendering at a higher DPI, so looks a bit
less pixelated).  In many ways the Ghostscript result is the most pleasing,
Photoshop has a distinct dark line and Apple Preview a light one.

I am very confident that there should not be any light pixels there. 
Anti-aliasing is supposed to color each pixel as the area-weighted average of
the colors of the constituent vector shapes.  Since the blue and gray shapes
touch, there is no white in any of those pixels.

One way to think of it is that the anti-aliased image should look the same as if
you rendered the image without anti-aliasing at a higher DPI (4x higher in each
dimension, for example), and then down-sampled by averaging each block of 4x4
pixels in the high resolution image to yield a single pixel in the anti-aliased
final result.

From my inspection, the Illustrator image appears to be a perfect blending of
the two colors (blue and gray).

Regardless of whether Adobe gets it right, it is certainly the case that there
should not be any pixels that are lighter than the two neighboring colors, so it
definitely appears to be a bug.

Also, please reference my original command-line (repeated below), as your
ghostscript result appears slightly different from mine (see second attachement).

gs -r72 -dEPSCrop -sDEVICE=pngalpha -sOutputFile=gs.png -dBATCH
-dNOPAUSE gaps.eps

The same problem appears in your Apple Preview result, which is also certainly
wrong behavior.  I have seen the same behavior in CorelDRAW X3 and Xara Xtreme.
 It appears as though there is some standard hack that many of the anti-aliased
rendering codes use to speed things up at the cost of quality.

I'm also curious whether there is any way to change the EPS so as to make sure
that every rendering engine does a passably good job.

Created attachment 3551 [details]
view of anti-aliased edge in profile

I loaded the ghostscript output into matlab and plotted the edge in profile
(red, green, and blue channels independently).	As you can see, the ghostscript
output has a definite overshoot, while the Adobe result clearly blends the two
colors and does not include anything other than some weighted average of the
two colors.  That overshoot in the Ghostscript result means a bug, since
anti-aliasing is defined as a weighted average, and a weighted average must lie
between the two constituents of which it is an average.

Regarding your comment #5: I didn't re-render the file using Ghostscript, I used the png file you 
uploaded in comment #2.

Ok, the difference between your screenshot and my original image must just have
been some alpha issue.  In any case, the Matlab plot (attachment: view of
anti-aliased edge in profile) makes the case very clear.  An overshoot just
doesn't make sense, so there must be a bug here.

When using anti-aliased rendering, the edges of objects are assigned an alpha
(opacity) value according to the amount of coverage in a pixel that is on the
edge. Ghostscript happens to calculate the amount of coverage by rendering to a
higher resolution (e.g. 4x), then counting the number of sub-pixels covered (16
sub-pixels when 4x higher resolution), but the adjacent edge problem occurs no
matter how the coverage (and thus the alpha) is calculated.

Take a simple example of two rectangles that are adjacent along a line that is
half-way across a pixel. When anti-aliasing is used, the first rectangle to
paint covers 50% of the 'edge' line of pixels, so gets blended with an opacity
of .5. If the rectangle was black and the  background was white, the edge row
will be 50% gray.

Now when the second (adjacent) rectangle is painted, it also has a 50% opacity
along the edge row, but the background is no longer white, but is 50% gray.
Blending 50% opacity black with the 50% gray background results in a gray value
of 25% (where black is 0 as in the DeviceGray colorspace). Thus, the 25% value
(rather than 0) could be described as background bleed through (the white is
bleeding through).

This same effect happens with off-axis intersections as well.

Rendering the entire page at the higher (4x) resolution, then doing the
resolution reduction using a simple component by component weighted sum of the
sub-pixels to get the color of the target device pixel would solve this. This
means that anti-aliased rendering would not paint as it processes the file, but
do the conversion all at once at 'showpage' time similarly to the way PDF
transparency works now. Thus, the x11alpha device would not update the display
as the file is processed, but rather would stay blank until the page is
complete. For file formats like JPEG or PNG, this is not a problem.

One difference (downside?) with the 'full page' approach I thought of is that
when anti-aliasing text, the white space will be darker in 'interiors' and
between characters. This may reduce the subjective contrast and reduce legibility.

*** Bug 688243 has been marked as a duplicate of this bug. ***

There are really two cases here, one of which is solvable with only an alpha
accumulator per pixel, and the other which requires at least local over-sampling
(i.e., only for the edge pixels).

Case 1: The image has no overlapping shapes.  In this case, any shape that
appears to be "on top" of another one actually has a cut-out (negative contour)
in the shape that it appears on top of so that it is actually only on top of the
background.  In this case, proper rendering can be done by using the alpha
channel as an accumulator:

a) The RGBA canvas is initialized to be (1,1,1,0) on each pixel.
b) For each shape, any fully interior pixel is assigned its color and given an
alpha of 1.
c) For each edge pixel and for each shape, we compute the fraction of the pixel
covered by the shape in question and call this beta.  The color of the pixel is
updated as the previous color times the previous alpha value plus the color of
the current shape times beta.  The alpha value of the pixel is updated to be
alpha+beta.
d) In the example mentioned in comment #9, this means the first rectangle would
be drawn and the edge pixel would start with alpha=0% and rgb=(1,1,1).  The
update rule would would yield alpha=50% and rgb=(1,1,1)*0% + (0,0,0)*50% =
(0,0,0).  The second one would be drawn and the update rule would yield
alpha=50%+50%=100% and rgb=(0,0,0)*50% + (0,0,0)*50% = (0,0,0).  I am happy to
provide a more detailed description of this using nicer notation if this is not
clear.

This method should yield correct anti-aliasing whenever there is no overlap. 
After rendering, everything that had an explicit shape over it would have
alpha=100% and the background would be white with alpha=0%.  To finish up, you'd
just set all the alpha values to 100%.

Case 2: Some of the shapes overlap, or there are some shapes entirely on top of
other ones.  This is sometimes called "cake stack" drawing.  In this case, there
are no holes in the bottom shapes under the top shapes, and the bottom shapes
are drawn first, so the alpha value for all the pixels on the interior of those
shapes will be set to 100% after rendering those shapes.  This means that
applying the update rules I described in Case 1 would lead to final alpha values
of more than 100%.  It also means that the color of the bottom shape will get
blended in.

A quick fix is to use the update rule described in Comment #9 whenever an edge
is found on a pixel that already has alpha=100%.

Since one can never be sure that all images will be Case 1 images, the update
rules I described are certainly not a complete solution.  It would work better
than the current method, though, since at least it works when there is no cake
stacking.

The only method I can imagine for doing correct anti-aliasing in all cases
without drawing the full 4x image is as follows:

Render just like before, except when you get to an edge pixel, don't bother
coloring it at all (or use whatever update rule you want) and just add a new
over-sampled pixel object to a random access 2d array object (like a vecor< map<
int, OverSampledPixel4x4> > in C++).  If that pixel object already exists, then
just color the over-sampled points according to the latest shape.  Then, after
all the shapes have been drawn, iterate over the elements of the random access
2d array and fix the pixels in the actual image.  This should not be too much
more computationally expensive, but would give correct anti-aliasing without
allocating 16x the memory.

Again, if my description is too brief, or unclear, please let me know.

James

I have read the discussions on the previous bug posts on this subject and I
noticed that those are marked as "resolved," which is a bit confusing since the
problem remains.  I also noted that Ralph Giles indicated that he doesn't think
it should be listed in the Issues.htm because he does not think it is really a
bug.  This is also very confusing, since anti-aliased rendering is a
well-defined concept that most certainly does not include this behavior.  This
behavior is the consequence of a common approximate rendering algorithm that I
do not believe is justified given the efficient alternatives available (sketched
in my previous post).  It is also worth noting that Adobe Illustrator does
implement this properly in recent versions.

Very Best,
James

James,

Thank you for your clear and cogent explanation.

I agree that the 'alpha addition' for edge pixels is the correct approach -- in
fact, this is what the PDF transparency code does.

For anti-aliased rendering from a PS file (where the expected imaging model is
'painters method' it's clear that the 'interior' pixels (which have a beta of
100%) should totally obscure the underlying color (background or otherwise), but
if the beta of an 'edge' pixel plus the alpha of the previously painted pixel
exceed 1.0, what beta value should be applied ? (you may have described this,
but I must have missed it). Example, underlying pixel has RGBA==(1, 0, 0, .6)
and new pixel has RGBA=(0, 1, 0 .8)

(I realize that in this case the result pixel will be clamped at an alpha of 1.0).

BTW, I'm adding Ralph to the cc list so that he can get on board for this.

Thanks for your help on this -- to those of us most familiar with PS or PCL
painting methods, handling of an RGBA model with anti-aliased edges is new
(edge) territory.

Color and AA issues probably should be handled by Michael. If not, after
his review we can determine who this should go to (maybe one of the new
guys?)

The problem of background bleed through when using antialiasing with abutting shapes is a well-known one; many other common graphics packages suffer from exactly the same issue that we do.

The approach suggested in comment 12 is infeasible within Ghostscript's rendering pipeline; notwithstanding the fact we can easily have 1000s of intersecting objects on a page, the interactions with different devices and transparency blending conspire to make it a non-starter.

The simplest way to avoid the problem is to render to a higher resolution and then scale down. We have this implemented with Ghostscript using the "Downscaler" mechanism. Many common devices are implemented on top of the downscaler and so can benefit from this with an additional parameter and a corresponding adjustment to the specified resolution.

For example, instead of:

  gs -r72 -dEPSCrop -sDEVICE=png16m -o gs.png gaps.eps

use:

  gs -r216 -dEPSCrop -sDEVICE=png16m -dDownScaleFactor=3 -o gs.png gaps.eps