Anti-aliasing causes gaps between touching shapes

[Martin Owens]

This is a copy from a report on deviantArt for the bug report. I couldn't find the existing report because I think there must be one already, so please merge this bug report if found.

By Azurexiles:

Opaque objects obscure everything underneath, but transparent ones must be blended with underlying objects. That sucks, because it gives the algorithm exponential worst-case complexity in both memory requirements and time. It's asymptotically proportional to n * 2^m, where n is the number of opaque objects and m of overlapping transparent ones.
In reality, especially if the user is reasonable, this shouldn't be a common problem, because heaps of wildly overlapping transparent objects are rare. If the polygons don't overlap, then the algorithm's execution time is asymptotically linear.

The algorithm:
Start with a queue or list containing polygon groups and possibly their properties (the color or color function may be useful). They are sorted by their z coordinate (as understood in the field of 2D graphics), where the topmost is the first to go.

create an empty polygon group, denoted by M; and a polygon group container, possibly with other properties such as a stack of color functions (in case the coloring isn't solid)— let's call it A

LOOP:
dequeue the next topmost polygon group and place it in T
calculate the relative complement of M in T and put the result in T: T = T - M = (T XOR M) AND T
if T is empty, skip everything below and go to LOOP
if T is altogether opaque, merge (OR) M and T and put the result in M: M = M OR T

iterate over A:
select the next element in A; we'll refer to it as S
if the bounding rectangles of T and S don't overlap, skip to the next iteration
W = T AND S
if W is empty, then skip to the next iteration
add W to A with the color function properly composed (T is overlaid with S) via the usual transparency blending (this step can be simplified if the coloring is solid)
S = S XOR W (replace the original element in A with this)
T = T XOR W
go to the next iteration; repeat until all the elements in A have been processed except the newly added Ws (they're already disjoint)

if T's color function contains transparency, add it to A
repeat LOOP until the queue is empty

draw everything that is in A
END

That's it. Let's hope it's not ridden with mistakes. If you find any, please, let me know.

Drawing means calculating the area (value range 0–1 — empty–full) of a particular pixel covered by the polygon and adding (not blending) the value to the bitmap. If color channels are used, then the pixel area value is the scalar factor with which the color vector (usually [A, R, G, B]) is scaled before it is added to the bitmap. Even though all of the final polygons are disjoint in theory, rounding errors in polygon boolean operations can cause overlaps and therefore overflow, so that's something to watch out for (hard saturation can be used here).
Similarly, some segments might end up not fitting tightly together, which can lead to marginal unwanted transparency in some pixels of the resulting bitmap. The latter side effect is not noticeable and can be avoided by proper rounding and sufficient precision.

Anyway, I wouldn't be so hasty with adding this to Inkscape. As I said, it's full of problems and perhaps there's a better way. Perhaps the one Illustrator uses.

[su_v (suv-lp)]

On 2014-05-09 20:26 +0100, Martin Owens wrote:
> This is a copy from a report on deviantArt for the bug report. I
> couldn't find the existing report because I think there must be one
> already (…)

The relevant bug report (with several duplicates) AFAIU is
- Bug #170356 (sf1003049) “Provide per-object antialiasing control (SVG 1.1 shape-rendering property)”
  <https://bugs.launchpad.net/inkscape/+bug/170356>

> (…) so please merge this bug report if found.

There is no merge feature for bug reports at launchpad.net - proposing to link as duplicate to bug #1318009.

[Liam P. White (liampwhite)]

Martin,

I think this would be more useful as a blueprint. By the way, there is no functionality to "merge" bug reports on Launchpad, so I will mark it as a duplicate of Bug #170356 like ~suv previously stated.