- 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 them

OK. 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

ploticus.

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.

Andrew. - Next post in topic >>