Source for gnu.java.awt.java2d.ScanlineConverter

   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: }