1627corrupted symbols: analysis and solution
- Oct 2, 2005Back in July, I reported a problem with corrupted symbols in scatterplots on
this list (http://groups.yahoo.com/group/ploticus/message/1581). An
example can be seen in, for example, the y=7 and y=7.4 rows at
http://home.comcast.net/~andrex/bugz/ploticus.png (created by the script at
http://home.comcast.net/~andrex/bugz/ploticus.plo). Those are rows of
diamonds that got corrupted in the plot.
Steve answered my query as follows:
> Ploticus generates vector graphics, which must be rasterized to get themOK. The remainder of the thread concerned using GD's new anti-aliasing
> into PNG/GIF. Then when PNG/GIF are rendered by the browser there may be
> another round of rasterization that might not sync with the first round.
facilities to mitigate the aliasing.
I still have the corrupted symbols problem, and ploticus is so good in every
other respect that I'd really like to see it get fixed. Here are my
thoughts, please tell me what you think.
First, this isn't a browser effect. It persists in any viewer at any
magnification. So it's a ploticus and/or libgd problem.
Second, the problem doesn't seem to be in GD. I don't know much about GD;
all I've done is to browse the documentation online. But AFAICT, GD deals
only in pixels. All calls to GD functions pass arguments in pixel units.
Therefore, the pixelization or aliasing is happening in ploticus. In my
mind this is good news, because it means the problem must be solvable in
Third, anti-aliasing isn't a solution. AA just amounts (as I understand
it anyway; please correct me if I'm wrong in the context of GD) to blurring
the plot lines in order to soften jagged edges. This is, IMO, undesirable
in most cases, since it reduces the sharpness of the plot; and it doesn't
solve the underlying problem. Aliasing in ploticus is often bad enough to
make the interior color of a symbol spill outside the symbol boundary. You
can see this, for example, in every diamond in the y=7 row in the plot
cited above (expand the row and look at the lower right edge of each
diamond). AA may partly obscure this effect, but it can't solve it. (It
may be a good idea for shapes other than vertical, horizontal, and diagonal
lines, however, since it can reduce jaggedness.)
Here's how I see the problem and its solution. In order to draw, say,
a diamond, ploticus uses the following algorithm:
(0) Start with coordinates (x,y) of the diamond's center, and a radius r.
(1) Compute offsets from the center to the vertices in a standard (r=1)
diamond, e.g. (1,0), (0,1), (-1,0), and (0,-1).
(2) Compute the vertex coordinates: e.g. for the right vertex they're
(x,y) + r * (0,1) = (x, y+r).
(3) Convert the vertex coordinates from plot units to pixel units.
(4) Call GD to draw lines between the vertices.
This algorithm is implemented in PLG_mark() in mark.c. But the conversion
to pixel units happens at a lower level-- PLG_mark calls Emov() and Epath()
to plot the points and lines, and these eventually call PLG_xsca() and
PLG_ysca() in winscale.c, which multiply x and y by global scaling factors
to convert to pixel units.
The aliasing, or rounding error, occurs in step 3. And the problem with
this algorithm is that the vertex coordinates are all computed in plot
units, and then independently rasterized, so the rounding error on each
coordinate can go in a separate direction. This is what causes the diamond
shape to distort in a random way.
The solution is simple in principle: convert the center coordinates and
radius to pixel units _before_ computing the vertex coordinates. That is,
remove step 3 and add
(1.5) Convert x, y, and r from plot units to pixel units.
The distortion problem will be solved, because the rounding error will
happen just one time on r, and then be applied uniformly in finding all of
the vertices. The shape will be a perfect diamond (or square or whatever).
(This is "less accurate" for the individual vertices, since they can't
independently find their closest pixels. But with plot symbols the
accuracy of the vertices isn't the point; drawing a clean, recognizable
shape is the point.)
In practice this would take some work to implement, because as I said above,
the conversion to pixel units currently happens at a low level in
ploticus-- just before the GD plotting routines are called. This approach
simplifies the higher-level code, which doesn't have to worry about any unit
conversions. In order to perform the pixel conversion at a higher level,
points will now have to implicitly carry units with them, and those units
will have to be passed down through all of the drawing routines. So for
example in PLG_mark(), the calls to Emov() and Epath will have to include a
new "already in pixel units" flag, to tell the lower-level routines not to
convert them again.
Specifying the symbol radius in pixels would have the added benefit of
providing a natural sequence of symbol sizes for users to choose from.
If it would be useful, I could try to create a proof-of-concept patch. I'm
not sure how long it would take, but the ploticus code seems to be pretty
clearly laid out, so it might not be too bad.
- Next post in topic >>