Loading ...
Sorry, an error occurred while loading the content.

1627corrupted symbols: analysis and solution

Expand Messages
  • Andrew Schulman
    Oct 2, 2005
    • 0 Attachment
      Back 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
      > 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.

      OK. The remainder of the thread concerned using GD's new anti-aliasing
      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.
    • Show all 12 messages in this topic