libjava/classpath/gnu/java/awt/java2d/ScanlineConverter.java

   1 /* ScanlineConverter.java -- Rasterizes Shapes
   2    Copyright (C) 2006, 2007 Free Software Foundation, Inc.
   3
   4 This file is part of GNU Classpath.
   5
   6 GNU Classpath is free software; you can redistribute it and/or modify
   7 it under the terms of the GNU General Public License as published by
   8 the Free Software Foundation; either version 2, or (at your option)
   9 any later version.
  10
  11 GNU Classpath is distributed in the hope that it will be useful, but
  12 WITHOUT ANY WARRANTY; without even the implied warranty of
  13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14 General Public License for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GNU Classpath; see the file COPYING.  If not, write to the
  18 Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  19 02110-1301 USA.
  20
  21 Linking this library statically or dynamically with other modules is
  22 making a combined work based on this library.  Thus, the terms and
  23 conditions of the GNU General Public License cover the whole
  24 combination.
  25
  26 As a special exception, the copyright holders of this library give you
  27 permission to link this library with independent modules to produce an
  28 executable, regardless of the license terms of these independent
  29 modules, and to copy and distribute the resulting executable under
  30 terms of your choice, provided that you also meet, for each linked
  31 independent module, the terms and conditions of the license of that
  32 module.  An independent module is a module which is not derived from
  33 or based on this library.  If you modify this library, you may extend
  34 this exception to your version of the library, but you are not
  35 obligated to do so.  If you do not wish to do so, delete this
  36 exception statement from your version. */
  37
  38
  39 package gnu.java.awt.java2d;
  40
  41 import gnu.java.math.Fixed;
  42
  43 import java.awt.RenderingHints;
  44 import java.awt.Shape;
  45 import java.awt.geom.AffineTransform;
  46 import java.awt.geom.PathIterator;
  47
  48 /**
  49  * Rasterizes {@link Shape} objects on an AbstractGraphics2D.
  50  */
  51 public final class ScanlineConverter
  52 {
  53
  54   /**
  55    * The number of digits to use for fixed point arithmetics.
  56    */
  57   private static int FIXED_DIGITS = 6;
  58
  59   /**
  60    * The fixed point constant for the number one.
  61    */
  62   private static int ONE = Fixed.fixedValue(FIXED_DIGITS, 1);
  63
  64   /**
  65    * The actual number of scanlines.
  66    */
  67   private int numScanlines;
  68
  69   /**
  70    * The number of scanlines. This can contain more elements than we have
  71    * scanlines. The real number of scanlines is stored in
  72    * {@link #numScanlines}. This can also contain null values for empty
  73    * scanlines.
  74    */
  75   private Scanline[] scanlines;
  76
  77   /**
  78    * The upper bounds which correspond to the index 0 in the scanline array.
  79    *
  80    * This is a fixed point value.
  81    */
  82   private int upperBounds;
  83
  84   /**
  85    * The resolution of the scanline converter.
  86    *
  87    * This is a fixed point value.
  88    */
  89   private int resolution;
  90
  91   /**
  92    * The number of significant bits for the 'Y' resolution.
  93    */
  94   private int yResolution;
  95
  96   /**
  97    * One half step according to the resolution. This is stored to avoid
  98    * unnecessary operations during rendering.
  99    */
 100   private int halfStep;
 101
 102   /**
 103    * This is used in {@link #addShape(PathIterator, boolean)} to
 104    * receive the coordinates of the path.
 105    */
 106   private float[] coords;
 107
 108   /**
 109    * The active edges.
 110    */
 111   private ActiveEdges activeEdges;
 112
 113   private PolyEdge edgePool;
 114   private PolyEdge edgePoolLast;
 115
 116   private int minY;
 117   private int maxY;
 118   private int minX;
 119   private int maxX;
 120
 121   /**
 122    * Holds and manages information about the pixel coverage.
 123    */
 124   private ScanlineCoverage scanlineCoverage;
 125
 126   /**
 127    * Create a new ScanlineConverter.
 128    */
 129   ScanlineConverter()
 130   {
 131     scanlines = new Scanline[10];
 132     coords = new float[6];
 133     activeEdges = new ActiveEdges();
 134     edgePool = new PolyEdge();
 135     edgePoolLast = edgePool;
 136     scanlineCoverage = new ScanlineCoverage();
 137   }
 138
 139   /**
 140    * Renders the specified shape using the specified clip and transform.
 141    *
 142    * @param p the pixelizer that receives the coverage information
 143    * @param shape the shape to render
 144    * @param clip the clip
 145    * @param trans the transform
 146    */
 147   public void renderShape(Pixelizer p, Shape shape, Shape clip,
 148                           AffineTransform trans, int res, int yRes,
 149                           RenderingHints hints)
 150   {
 151     // TODO: Do something useful with the rendering hints. Like, adjusting
 152     // the resolution.
 153
 154     // Prepare resolution and upper bounds.
 155     clear();
 156     setResolution(res, yRes);
 157
 158     boolean haveClip = clip != null;
 159
 160     // Add shapes.
 161     float flatness = Fixed.floatValue(FIXED_DIGITS, resolution / 2);
 162     PathIterator path = shape.getPathIterator(trans, flatness);
 163     addShape(path, false);
 164     if (haveClip)
 165       {
 166         path= clip.getPathIterator(trans, flatness);
 167         addShape(path, true);
 168       }
 169
 170     setUpperBounds(minY);
 171
 172     PolyEdge edge = edgePool;
 173     while (edge != edgePoolLast)
 174       {
 175         addEdge(edge);
 176         edge = edge.poolNext;
 177       }
 178
 179     int y = upperBounds;
 180     int index;
 181     activeEdges.clear();
 182     // The render loop...
 183     Scanline scanline = null;
 184     int lastRealY = Fixed.intValue(FIXED_DIGITS, y);
 185     while (y <= maxY)
 186       {
 187         // First we put together our list of active edges.
 188         index = scanlineIndex(y);
 189         // If we go outside the scanline array we still need to render the
 190         // remaining edges until they end.
 191         scanline = index < scanlines.length ? scanlines[index] : null;
 192         if (scanline != null)
 193           {
 194             edge = scanline.getEdges();
 195             while (edge != null)
 196               {
 197                 activeEdges.add(edge);
 198                 edge = edge.scanlineNext;
 199               }
 200           }
 201
 202         // Then we intersect all active edges with the current scanline
 203         // and sort them according to their intersection points.
 204         activeEdges.intersectSortAndPack(FIXED_DIGITS, y + halfStep);
 205
 206         // Ok, now we can perform the actual scanlining.
 207         int realY = Fixed.intValue(FIXED_DIGITS, y + resolution);
 208         boolean push = lastRealY != realY;
 209
 210         doScanline(p, y, push, haveClip);
 211
 212         // Remove obsolete active edges.
 213         //activeEdges.remove(y + halfStep);
 214         // Go on with the next line...
 215         y += resolution;
 216         lastRealY = realY;
 217
 218       }
 219   }
 220
 221   /**
 222    * Clears all scanlines.
 223    */
 224   private void clear()
 225   {
 226     // Reset edge pool.
 227     edgePoolLast = edgePool;
 228
 229     // Reset scanlines.
 230     for (int i = scanlines.length - 1; i >= 0 ; i--)
 231       {
 232         Scanline sl = scanlines[i];
 233         if (sl != null)
 234           sl.clear();
 235       }
 236
 237     // Reset scanline coverage.
 238     scanlineCoverage.clear();
 239
 240     // Reset bounds.
 241     minY = Integer.MAX_VALUE;
 242     maxY = Integer.MIN_VALUE;
 243     minX = Integer.MAX_VALUE;
 244     maxX = Integer.MIN_VALUE;
 245   }
 246
 247   /**
 248    * Performs the scanlining on the current set of active edges.
 249    *
 250    * @param p the pixelizer to receive the pixel coverage data
 251    * @param y the Y coordinate
 252    * @param push true when the scanline is ready to be pushed to the
 253    *        pixelizer
 254    * @param haveClip true when there's a clip, false otherwise
 255    */
 256   private void doScanline(Pixelizer p, int y, boolean push,
 257                           boolean haveClip)
 258   {
 259     // First, rewind the scanline coverage.
 260     scanlineCoverage.rewind();
 261
 262     // We begin outside the clip and outside the shape. We only draw when
 263     // we are inside the clip AND inside the shape.
 264     boolean inClip = ! haveClip;
 265     boolean inShape = false;
 266     PolyEdge lastEdge = null;
 267     int numEdges = activeEdges.getNumActiveEdges();
 268     for (int i = 0; i < numEdges; i++)
 269       {
 270         PolyEdge edge = activeEdges.getActiveEdge(i);
 271         if (inClip && inShape)
 272           {
 273             assert lastEdge != null;
 274             int x0 = lastEdge.xIntersection;
 275             int x1 = edge.xIntersection;
 276             assert x0 <= x1;
 277
 278             int pix0 = Fixed.intValue(FIXED_DIGITS, x0);
 279             int pix1 = Fixed.intValue(FIXED_DIGITS, x1);
 280             int frac0 = ONE - Fixed.trunc(FIXED_DIGITS, x0);
 281             int frac1 = ONE - Fixed.trunc(FIXED_DIGITS, x1);
 282             // Only keep the first 4 digits after the point.
 283             frac0 = frac0 >> (FIXED_DIGITS - yResolution);
 284             frac1 = frac1 >> (FIXED_DIGITS - yResolution);
 285             scanlineCoverage.add(pix0, 1 * (1 << yResolution), frac0);
 286             scanlineCoverage.add(pix1, -1 * (1 << yResolution), -frac1);
 287           }
 288         if (edge.isClip)
 289           inClip = ! inClip;
 290         else
 291           inShape = ! inShape;
 292
 293         lastEdge = edge;
 294       }
 295
 296     // Push out the whole scanline to the pixelizer.
 297     if (push && ! scanlineCoverage.isEmpty())
 298       {
 299         p.renderScanline(Fixed.intValue(FIXED_DIGITS, y), scanlineCoverage);
 300         scanlineCoverage.clear();
 301       }
 302   }
 303
 304
 305   /**
 306    * Sets the resolution. A value of 0 rasterizes the shape normally without
 307    * anti-aliasing. Greater values renders with a resolution of 2 ^ res.
 308    *
 309    * @param res the resolution
 310    */
 311   private void setResolution(int res, int yRes)
 312   {
 313     int scanlinesPerPixel = 1 << res;
 314     int one = Fixed.fixedValue(FIXED_DIGITS, 1);
 315     resolution = one / (scanlinesPerPixel);
 316     halfStep = resolution / 2;
 317
 318     scanlineCoverage.setMaxCoverage(scanlinesPerPixel << yResolution);
 319
 320     yResolution = yRes;
 321   }
 322
 323   /**
 324    * Sets the vertical bounds of that shape that is beeing rendered.
 325    *
 326    * @param y0 the upper bounds
 327    */
 328   private void setUpperBounds(int y0)
 329   {
 330     upperBounds = fit(y0);
 331   }
 332
 333   /**
 334    * Add a shape to the scanline converter.
 335    *
 336    * @param path
 337    * @param clip
 338    */
 339   private void addShape(PathIterator path, boolean clip)
 340   {
 341     int startX = 0;
 342     int startY = 0;
 343     int lastX = 0;
 344     int lastY = 0;
 345     while (! path.isDone())
 346       {
 347         int type = path.currentSegment(coords);
 348         switch (type)
 349           {
 350             case PathIterator.SEG_MOVETO:
 351               startX = lastX = Fixed.fixedValue(FIXED_DIGITS, coords[0]);
 352               startY = lastY = Fixed.fixedValue(FIXED_DIGITS, coords[1]);
 353               minY = Math.min(startY, minY);
 354               maxY = Math.max(startY, maxY);
 355               minX = Math.min(startX, minX);
 356               maxX = Math.max(startX, maxX);
 357               break;
 358             case PathIterator.SEG_LINETO:
 359               int x = Fixed.fixedValue(FIXED_DIGITS, coords[0]);
 360               int y = Fixed.fixedValue(FIXED_DIGITS, coords[1]);
 361               edgePoolAdd(lastX, lastY, x, y, clip);
 362               lastX = x;
 363               lastY = y;
 364               minY = Math.min(lastY, minY);
 365               maxY = Math.max(lastY, maxY);
 366               minX = Math.min(lastX, minX);
 367               maxX = Math.max(lastX, maxX);
 368               break;
 369             case PathIterator.SEG_CLOSE:
 370               edgePoolAdd(lastX, lastY, startX, startY, clip);
 371               lastX = startX;
 372               lastY = startY;
 373               break;
 374             case PathIterator.SEG_CUBICTO:
 375             case PathIterator.SEG_QUADTO:
 376             default:
 377               assert false;
 378           }
 379         path.next();
 380       }
 381   }
 382
 383   /**
 384    * Adds an edge into the scanline array.
 385    */
 386   private void addEdge(PolyEdge edge)
 387   {
 388     // Determine index.
 389     int upper = Math.min(edge.y0, edge.y1);
 390     // Fit to raster.
 391     int index = scanlineIndex(upper);
 392     // Grow array when necessary.
 393     if (index >= scanlines.length)
 394       {
 395         int oldSize = scanlines.length;
 396         int newSize = Math.max(oldSize + oldSize / 2 + 1, index + 10);
 397         Scanline[] newScanlines = new Scanline[newSize];
 398         System.arraycopy(scanlines, 0, newScanlines, 0, oldSize);
 399         scanlines = newScanlines;
 400       }
 401
 402     // Add edge.
 403     if (scanlines[index] == null)
 404       {
 405         scanlines[index] = new Scanline();
 406       }
 407     scanlines[index].addEdge(edge);
 408   }
 409
 410   /**
 411    * Fits an Y coordinate to the grid.
 412    *
 413    * @param y the Y coordinate to fit
 414    *
 415    * @return the fitted Y coordinate
 416    */
 417   private int fit(int y)
 418   {
 419     int val1 = Fixed.div(FIXED_DIGITS, y, resolution);
 420     int rounded = Fixed.round(FIXED_DIGITS, val1);
 421     return Fixed.mul(FIXED_DIGITS, rounded, resolution);
 422   }
 423
 424   /**
 425    * Calculates the scanline index for the specified y coordinate.
 426    *
 427    * @param y the y coordinate as fixed point value
 428    *
 429    * @return the scanline index
 430    */
 431   private int scanlineIndex(int y)
 432   {
 433     int fitted = fit(y);
 434     // Cleverly skip the fixed point conversions here.
 435     return (fitted - upperBounds)/ resolution;
 436   }
 437
 438   private void edgePoolAdd(int x0, int y0, int x1, int y1, boolean clip)
 439   {
 440     // Don't need no horizontal edges.
 441     if (y0 != y1)
 442       {
 443         edgePoolLast.init(FIXED_DIGITS, x0, y0, x1, y1, clip);
 444         if (edgePoolLast.poolNext == null)
 445           {
 446             edgePoolLast.poolNext = new PolyEdge();
 447           }
 448         edgePoolLast = edgePoolLast.poolNext;
 449       }
 450   }
 451 }