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 number of significant bits for the Y resolution.
  66:    */
  67:   private static int Y_RESOLUTION = 4;
  68: 
  69:   /**
  70:    * The actual number of scanlines.
  71:    */
  72:   private int numScanlines;
  73: 
  74:   /**
  75:    * The number of scanlines. This can contain more elements than we have
  76:    * scanlines. The real number of scanlines is stored in
  77:    * {@link #numScanlines}. This can also contain null values for empty
  78:    * scanlines.
  79:    */
  80:   private Scanline[] scanlines;
  81: 
  82:   /**
  83:    * The upper bounds which correspond to the index 0 in the scanline array.
  84:    *
  85:    * This is a fixed point value.
  86:    */
  87:   private int upperBounds;
  88: 
  89:   /**
  90:    * The resolution of the scanline converter.
  91:    *
  92:    * This is a fixed point value.
  93:    */
  94:   private int resolution;
  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, RenderingHints hints)
 149:   {
 150:     // TODO: Do something useful with the rendering hints. Like, adjusting
 151:     // the resolution.
 152: 
 153:     // Prepare resolution and upper bounds.
 154:     clear();
 155:     setResolution(res);
 156: 
 157:     boolean haveClip = clip != null;
 158: 
 159:     // Add shapes.
 160:     float flatness = Fixed.floatValue(FIXED_DIGITS, resolution / 2);
 161:     PathIterator path = shape.getPathIterator(trans, flatness);
 162:     addShape(path, false);
 163:     if (haveClip)
 164:       {
 165:         path= clip.getPathIterator(trans, flatness);
 166:         addShape(path, true);
 167:       }
 168: 
 169:     setUpperBounds(minY);
 170: 
 171:     PolyEdge edge = edgePool;
 172:     while (edge != edgePoolLast)
 173:       {
 174:         addEdge(edge);
 175:         edge = edge.poolNext;
 176:       }
 177: 
 178:     int y = upperBounds;
 179:     int index;
 180:     activeEdges.clear();
 181:     // The render loop...
 182:     Scanline scanline = null;
 183:     int lastRealY = Fixed.intValue(FIXED_DIGITS, y);
 184:     while (y <= maxY)
 185:       {
 186:         // First we put together our list of active edges.
 187:         index = scanlineIndex(y);
 188:         // If we go outside the scanline array we still need to render the
 189:         // remaining edges until they end.
 190:         scanline = index < scanlines.length ? scanlines[index] : null;
 191:         if (scanline != null)
 192:           {
 193:             edge = scanline.getEdges();
 194:             while (edge != null)
 195:               {
 196:                 activeEdges.add(edge);
 197:                 edge = edge.scanlineNext;
 198:               }
 199:           }
 200: 
 201:         // Then we intersect all active edges with the current scanline
 202:         // and sort them according to their intersection points.
 203:         activeEdges.intersectSortAndPack(FIXED_DIGITS, y + halfStep);
 204: 
 205:         // Ok, now we can perform the actual scanlining.
 206:         int realY = Fixed.intValue(FIXED_DIGITS, y + resolution);
 207:         boolean push = lastRealY != realY;
 208:         doScanline(p, y, push, haveClip);
 209: 
 210:         // Remove obsolete active edges.
 211:         //activeEdges.remove(y + halfStep);
 212:         // Go on with the next line...
 213:         y += resolution;
 214:         lastRealY = realY;
 215: 
 216:       }
 217:   }
 218: 
 219:   /**
 220:    * Clears all scanlines.
 221:    */
 222:   private void clear()
 223:   {
 224:     // Reset edge pool.
 225:     edgePoolLast = edgePool;
 226: 
 227:     // Reset scanlines.
 228:     for (int i = scanlines.length - 1; i >= 0 ; i--)
 229:       {
 230:         Scanline sl = scanlines[i];
 231:         if (sl != null)
 232:           sl.clear();
 233:       }
 234: 
 235:     // Reset scanline coverage.
 236:     scanlineCoverage.clear();
 237: 
 238:     // Reset bounds.
 239:     minY = Integer.MAX_VALUE;
 240:     maxY = Integer.MIN_VALUE;
 241:     minX = Integer.MAX_VALUE;
 242:     maxX = Integer.MIN_VALUE;
 243:   }
 244: 
 245:   /**
 246:    * Performs the scanlining on the current set of active edges.
 247:    *
 248:    * @param p the pixelizer to receive the pixel coverage data
 249:    * @param y the Y coordinate
 250:    * @param push true when the scanline is ready to be pushed to the
 251:    *        pixelizer
 252:    * @param haveClip true when there's a clip, false otherwise
 253:    */
 254:   private void doScanline(Pixelizer p, int y, boolean push,
 255:                           boolean haveClip)
 256:   {
 257:     // First, rewind the scanline coverage.
 258:     scanlineCoverage.rewind();
 259: 
 260:     // We begin outside the clip and outside the shape. We only draw when
 261:     // we are inside the clip AND inside the shape.
 262:     boolean inClip = ! haveClip;
 263:     boolean inShape = false;
 264:     PolyEdge lastEdge = null;
 265:     int numEdges = activeEdges.getNumActiveEdges();
 266:     for (int i = 0; i < numEdges; i++)
 267:       {
 268:         PolyEdge edge = activeEdges.getActiveEdge(i);
 269:         if (inClip && inShape)
 270:           {
 271:             assert lastEdge != null;
 272:             int x0 = lastEdge.xIntersection;
 273:             int x1 = edge.xIntersection;
 274:             assert x0 <= x1;
 275: 
 276:             int pix0 = Fixed.intValue(FIXED_DIGITS, x0);
 277:             int pix1 = Fixed.intValue(FIXED_DIGITS, x1);
 278:             int frac0 = ONE - Fixed.trunc(FIXED_DIGITS, x0);
 279:             int frac1 = ONE - Fixed.trunc(FIXED_DIGITS, x1);
 280:             // Only keep the first 4 digits after the point.
 281:             frac0 = frac0 >> (FIXED_DIGITS - Y_RESOLUTION);
 282:             frac1 = frac1 >> (FIXED_DIGITS - Y_RESOLUTION);
 283:             scanlineCoverage.add(pix0, 1 * (1 << Y_RESOLUTION), frac0);
 284:             scanlineCoverage.add(pix1, -1 * (1 << Y_RESOLUTION), -frac1);
 285:           }
 286:         if (edge.isClip)
 287:           inClip = ! inClip;
 288:         else
 289:           inShape = ! inShape;
 290: 
 291:         lastEdge = edge;
 292:       }
 293: 
 294:     // Push out the whole scanline to the pixelizer.
 295:     if (push && ! scanlineCoverage.isEmpty())
 296:       {
 297:         p.renderScanline(Fixed.intValue(FIXED_DIGITS, y), scanlineCoverage);
 298:         scanlineCoverage.clear();
 299:       }
 300:   } 
 301: 
 302: 
 303:   /**
 304:    * Sets the resolution. A value of 0 rasterizes the shape normally without
 305:    * anti-aliasing. Greater values renders with a resolution of 2 ^ res.
 306:    *
 307:    * @param res the resolution
 308:    */
 309:   private void setResolution(int res)
 310:   {
 311:     int scanlinesPerPixel = 1 << res;
 312:     int one = Fixed.fixedValue(FIXED_DIGITS, 1);
 313:     resolution = one / (scanlinesPerPixel);
 314:     halfStep = resolution / 2;
 315: 
 316:     scanlineCoverage.setMaxCoverage(scanlinesPerPixel << Y_RESOLUTION);
 317:   }
 318: 
 319:   /**
 320:    * Sets the vertical bounds of that shape that is beeing rendered.
 321:    *
 322:    * @param y0 the upper bounds
 323:    */
 324:   private void setUpperBounds(int y0)
 325:   {
 326:     upperBounds = fit(y0);
 327:   }
 328: 
 329:   /**
 330:    * Add a shape to the scanline converter.
 331:    *
 332:    * @param path
 333:    * @param clip
 334:    */
 335:   private void addShape(PathIterator path, boolean clip)
 336:   {
 337:     int startX = 0;
 338:     int startY = 0;
 339:     int lastX = 0;
 340:     int lastY = 0;
 341:     while (! path.isDone())
 342:       {
 343:         int type = path.currentSegment(coords);
 344:         switch (type)
 345:           {
 346:             case PathIterator.SEG_MOVETO:
 347:               startX = lastX = Fixed.fixedValue(FIXED_DIGITS, coords[0]);
 348:               startY = lastY = Fixed.fixedValue(FIXED_DIGITS, coords[1]);
 349:               minY = Math.min(startY, minY);
 350:               maxY = Math.max(startY, maxY);
 351:               minX = Math.min(startX, minX);
 352:               maxX = Math.max(startX, maxX);
 353:               break;
 354:             case PathIterator.SEG_LINETO:
 355:               int x = Fixed.fixedValue(FIXED_DIGITS, coords[0]);
 356:               int y = Fixed.fixedValue(FIXED_DIGITS, coords[1]);
 357:               edgePoolAdd(lastX, lastY, x, y, clip);
 358:               lastX = x;
 359:               lastY = y;
 360:               minY = Math.min(lastY, minY);
 361:               maxY = Math.max(lastY, maxY);
 362:               minX = Math.min(lastX, minX);
 363:               maxX = Math.max(lastX, maxX);
 364:               break;
 365:             case PathIterator.SEG_CLOSE:
 366:               edgePoolAdd(lastX, lastY, startX, startY, clip);
 367:               lastX = startX;
 368:               lastY = startY;
 369:               break;
 370:             case PathIterator.SEG_CUBICTO:
 371:             case PathIterator.SEG_QUADTO:
 372:             default:
 373:               assert false;
 374:           }
 375:         path.next();
 376:       }
 377:   }
 378: 
 379:   /**
 380:    * Adds an edge into the scanline array.
 381:    */
 382:   private void addEdge(PolyEdge edge)
 383:   {
 384:     // Determine index.
 385:     int upper = Math.min(edge.y0, edge.y1);
 386:     // Fit to raster.
 387:     int index = scanlineIndex(upper);
 388:     // Grow array when necessary.
 389:     if (index >= scanlines.length)
 390:       {
 391:         int oldSize = scanlines.length;
 392:         int newSize = Math.max(oldSize + oldSize / 2 + 1, index + 10);
 393:         Scanline[] newScanlines = new Scanline[newSize];
 394:         System.arraycopy(scanlines, 0, newScanlines, 0, oldSize);
 395:         scanlines = newScanlines;
 396:       }
 397: 
 398:     // Add edge.
 399:     if (scanlines[index] == null)
 400:       {
 401:         scanlines[index] = new Scanline();
 402:       }
 403:     scanlines[index].addEdge(edge);
 404:   }
 405: 
 406:   /**
 407:    * Fits an Y coordinate to the grid.
 408:    *
 409:    * @param y the Y coordinate to fit
 410:    *
 411:    * @return the fitted Y coordinate
 412:    */
 413:   private int fit(int y)
 414:   {
 415:     int val1 = Fixed.div(FIXED_DIGITS, y, resolution);
 416:     int rounded = Fixed.round(FIXED_DIGITS, val1);
 417:     return Fixed.mul(FIXED_DIGITS, rounded, resolution);
 418:   }
 419: 
 420:   /**
 421:    * Calculates the scanline index for the specified y coordinate.
 422:    *
 423:    * @param y the y coordinate as fixed point value
 424:    *
 425:    * @return the scanline index
 426:    */
 427:   private int scanlineIndex(int y)
 428:   {
 429:     int fitted = fit(y);
 430:     // Cleverly skip the fixed point conversions here.
 431:     return (fitted - upperBounds)/ resolution;
 432:   }
 433: 
 434:   private void edgePoolAdd(int x0, int y0, int x1, int y1, boolean clip)
 435:   {
 436:     // Don't need no horizontal edges.
 437:     if (y0 != y1)
 438:       {
 439:         edgePoolLast.init(FIXED_DIGITS, x0, y0, x1, y1, clip);
 440:         if (edgePoolLast.poolNext == null)
 441:           {
 442:             edgePoolLast.poolNext = new PolyEdge();
 443:           }
 444:         edgePoolLast = edgePoolLast.poolNext;
 445:       }
 446:   }
 447: }