I wanted to do this for a long time. This improves the performance and
quality of the Shape rasterizer (that is used for rendering shapes and
text in the Escher peers for example).
Basically, the coverage information of the anti-aliasing rasterizer is
now no more stored in an array, but in a much more efficient data
structure. This makes the rasterizer code more concise, better
performing and it allows to rasterize with and without anti-aliasing
without penalty (non-AA is then only a special case of AA rasterization,
where the scanline resolution is 1 (2^0), rather than 2^N).
2007-05-18 Roman Kennke <[EMAIL PROTECTED]>
* gnu/java/awt/java2d/AbstractGraphics2D.java
(fillScanlineAA): Removed. Replaced by renderScanline().
(fillScanline): Dito.
(renderScanline): New method. Renders a scanline according to
the coverage information from the scanline converter.
* gnu/java/awt/java2d/Pixelizer.java: New interface. Describes
the targets of the rasterizer.
* gnu/java/awt/java2d/ScanlineConverter.java
(alphaRes): Removed.
(ONE): Removed.
(scanlineCoverage): New field. Manages the coverage information.
(scanlinesPerPixel): Removed.
(scanlineXCov): Removed.
(scanlineYCov): Removed.
(slPix0): Removed.
(ScanlineConverter): Initialize scanline coverage data
structure.
(clear): Also clear the scanline coverage.
(doScanline): Work with Pixelizer objects.
Use the ScanlineCoverage datastructure.
(main): New method. Performs some tests.
(renderShape): Work with pixelizer objects rather than directly
on AbstractGraphic2D. Adjust to use ScanlineCoverage
datastructure.
(setResolution): Set resolution on ScanlineCoverage data too.
* gnu/java/awt/java2d/ScanlineCoverage.java: New class. Stores
and manages scanline coverage information.
/Roman
--
Dipl.-Inf. Roman Kennke, Software Engineer, http://kennke.org
aicas Allerton Interworks Computer Automated Systems GmbH
Haid-und-Neu-Straße 18 * D-76131 Karlsruhe * Germany
http://www.aicas.com * Tel: +49-721-663 968-0
USt-Id: DE216375633, Handelsregister HRB 109481, AG Karlsruhe
Geschäftsführer: Dr. James J. Hunt
Index: gnu/java/awt/java2d/AbstractGraphics2D.java
===================================================================
RCS file: /cvsroot/classpath/classpath/gnu/java/awt/java2d/AbstractGraphics2D.java,v
retrieving revision 1.15
diff -u -1 -5 -r1.15 AbstractGraphics2D.java
--- gnu/java/awt/java2d/AbstractGraphics2D.java 8 May 2007 13:27:30 -0000 1.15
+++ gnu/java/awt/java2d/AbstractGraphics2D.java 18 May 2007 16:22:00 -0000
@@ -39,54 +39,56 @@
import java.awt.AWTError;
import java.awt.AlphaComposite;
import java.awt.AWTPermission;
import java.awt.BasicStroke;
import java.awt.Color;
import java.awt.Composite;
import java.awt.CompositeContext;
import java.awt.Font;
import java.awt.FontMetrics;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.Image;
import java.awt.Paint;
import java.awt.PaintContext;
+import java.awt.Point;
import java.awt.Polygon;
import java.awt.Rectangle;
import java.awt.RenderingHints;
import java.awt.Shape;
import java.awt.Stroke;
import java.awt.Toolkit;
import java.awt.RenderingHints.Key;
import java.awt.font.FontRenderContext;
import java.awt.font.GlyphVector;
import java.awt.geom.AffineTransform;
import java.awt.geom.Arc2D;
import java.awt.geom.Area;
import java.awt.geom.Ellipse2D;
import java.awt.geom.GeneralPath;
import java.awt.geom.Line2D;
import java.awt.geom.NoninvertibleTransformException;
import java.awt.geom.RoundRectangle2D;
import java.awt.image.BufferedImage;
import java.awt.image.BufferedImageOp;
import java.awt.image.ColorModel;
import java.awt.image.DataBuffer;
import java.awt.image.ImageObserver;
import java.awt.image.Raster;
import java.awt.image.RenderedImage;
+import java.awt.image.SampleModel;
import java.awt.image.WritableRaster;
import java.awt.image.renderable.RenderableImage;
import java.text.AttributedCharacterIterator;
import java.util.HashMap;
import java.util.Map;
/**
* This is a 100% Java implementation of the Java2D rendering pipeline. It is
* meant as a base class for Graphics2D implementations.
*
* <h2>Backend interface</h2>
* <p>
* The backend must at the very least provide a Raster which the the rendering
* pipeline can paint into. This must be implemented in
* [EMAIL PROTECTED] #getDestinationRaster()}. For some backends that might be enough, like
@@ -134,31 +136,31 @@
* using native code. These have proved to two of the most performance
* critical points in the rendering pipeline and cannot really be done quickly
* in plain Java because they involve lots of shuffling around with large
* arrays. In fact, you really would want to let the graphics card to the
* work, they are made for this.</li>
* <li>Provide an accelerated implementation for fillShape(). For instance,
* OpenGL can fill shapes very efficiently. There are some considerations
* to be made though, see above for details.</li>
* </ol>
* </p>
*
* @author Roman Kennke ([EMAIL PROTECTED])
*/
public abstract class AbstractGraphics2D
extends Graphics2D
- implements Cloneable
+ implements Cloneable, Pixelizer
{
/**
* The default font to use on the graphics object.
*/
private static final Font FONT = new Font("SansSerif", Font.PLAIN, 12);
/**
* Caches certain shapes to avoid massive creation of such Shapes in
* the various draw* and fill* methods.
*/
private static final ThreadLocal<ShapeCache> shapeCache =
new ThreadLocal<ShapeCache>();
/**
@@ -1708,34 +1710,66 @@
*/
private void copyAreaImpl(int x, int y, int w, int h, int dx, int dy)
{
// FIXME: Implement this properly.
throw new UnsupportedOperationException("Not implemented yet.");
}
/**
* Paints a scanline between x0 and x1. Override this when your backend
* can efficiently draw/fill horizontal lines.
*
* @param x0 the left offset
* @param x1 the right offset
* @param y the scanline
*/
- protected void fillScanline(int x0, int x1, int y)
+ public void renderScanline(int y, ScanlineCoverage c)
{
PaintContext pCtx = paintContext;
+ int x0 = c.getMinX();
+ int x1 = c.getMaxX();
Raster paintRaster = pCtx.getRaster(x0, y, x1 - x0, 1);
+
+ // Do the anti aliasing thing.
+ float coverageAlpha = 0;
+ float maxCoverage = c.getMaxCoverage();
+ ColorModel cm = pCtx.getColorModel();
+ DataBuffer db = paintRaster.getDataBuffer();
+ Point loc = new Point(paintRaster.getMinX(), paintRaster.getMinY());
+ SampleModel sm = paintRaster.getSampleModel();
+ WritableRaster writeRaster = Raster.createWritableRaster(sm, db, loc);
+ WritableRaster alphaRaster = cm.getAlphaRaster(writeRaster);
+ int pixel;
+ ScanlineCoverage.Coverage start = c.iterate();
+ ScanlineCoverage.Coverage end = c.next();
+ assert (start != null);
+ assert (end != null);
+ do
+ {
+ coverageAlpha = coverageAlpha + (start.getCoverageDelta() / maxCoverage);
+ if (coverageAlpha < 1.0)
+ {
+ for (int x = start.getXPos(); x < end.getXPos(); x++)
+ {
+ pixel = alphaRaster.getSample(x, y, 0);
+ pixel = (int) (pixel * coverageAlpha);
+ alphaRaster.setSample(x, y, 0, pixel);
+ }
+ }
+ start = end;
+ end = c.next();
+ } while (end != null);
ColorModel paintColorModel = pCtx.getColorModel();
CompositeContext cCtx = composite.createContext(paintColorModel,
getColorModel(),
renderingHints);
WritableRaster targetChild = destinationRaster.createWritableTranslatedChild(-x0,- y);
cCtx.compose(paintRaster, targetChild, targetChild);
updateRaster(destinationRaster, x0, y, x1 - x0, 1);
cCtx.dispose();
}
/**
* Initializes this graphics object. This must be called by subclasses in
* order to correctly initialize the state of this object.
*/
@@ -1902,20 +1936,16 @@
* Returns the scanline converter for this thread.
*
* @return the scanline converter for this thread
*/
private ScanlineConverter getScanlineConverter()
{
ScanlineConverter sc = scanlineConverters.get();
if (sc == null)
{
sc = new ScanlineConverter();
scanlineConverters.set(sc);
}
return sc;
}
- protected void fillScanlineAA(int x0, int x1, int y, int alpha2)
- {
- System.err.println("override!");
- }
}
Index: gnu/java/awt/java2d/Pixelizer.java
===================================================================
RCS file: gnu/java/awt/java2d/Pixelizer.java
diff -N gnu/java/awt/java2d/Pixelizer.java
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ gnu/java/awt/java2d/Pixelizer.java 18 May 2007 16:22:00 -0000
@@ -0,0 +1,56 @@
+/* Pixelizer.java -- Interface for the target of the rasterizer
+ Copyright (C) 2007 Free Software Foundation, Inc.
+
+This file is part of GNU Classpath.
+
+GNU Classpath is free software; you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 2, or (at your option)
+any later version.
+
+GNU Classpath is distributed in the hope that it will be useful, but
+WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GNU Classpath; see the file COPYING. If not, write to the
+Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
+02110-1301 USA.
+
+Linking this library statically or dynamically with other modules is
+making a combined work based on this library. Thus, the terms and
+conditions of the GNU General Public License cover the whole
+combination.
+
+As a special exception, the copyright holders of this library give you
+permission to link this library with independent modules to produce an
+executable, regardless of the license terms of these independent
+modules, and to copy and distribute the resulting executable under
+terms of your choice, provided that you also meet, for each linked
+independent module, the terms and conditions of the license of that
+module. An independent module is a module which is not derived from
+or based on this library. If you modify this library, you may extend
+this exception to your version of the library, but you are not
+obligated to do so. If you do not wish to do so, delete this
+exception statement from your version. */
+
+package gnu.java.awt.java2d;
+
+/**
+ * A pixelizer is responsible for actually manipulating the pixel of a drawing
+ * surface after the scanline conversion process. It receives coverage
+ * information for a scanline and adjusts the surface pixels accordingly.
+ */
+public interface Pixelizer
+{
+
+ /**
+ * Renders the pixel for one scanline at the Y location <code>y</code>
+ * and using the coverage information in <code>sc</code>.
+ *
+ * @param y the scanline Y coordinate
+ * @param sc the coverage information
+ */
+ void renderScanline(int y, ScanlineCoverage sc);
+}
Index: gnu/java/awt/java2d/ScanlineConverter.java
===================================================================
RCS file: /cvsroot/classpath/classpath/gnu/java/awt/java2d/ScanlineConverter.java,v
retrieving revision 1.2
diff -u -1 -5 -r1.2 ScanlineConverter.java
--- gnu/java/awt/java2d/ScanlineConverter.java 8 May 2007 13:27:30 -0000 1.2
+++ gnu/java/awt/java2d/ScanlineConverter.java 18 May 2007 16:22:00 -0000
@@ -1,17 +1,17 @@
/* ScanlineConverter.java -- Rasterizes Shapes
- Copyright (C) 2006 Free Software Foundation, Inc.
+ Copyright (C) 2006, 2007 Free Software Foundation, Inc.
This file is part of GNU Classpath.
GNU Classpath is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2, or (at your option)
any later version.
GNU Classpath is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
General Public License for more details.
You should have received a copy of the GNU General Public License
along with GNU Classpath; see the file COPYING. If not, write to the
@@ -35,323 +35,277 @@
obligated to do so. If you do not wish to do so, delete this
exception statement from your version. */
package gnu.java.awt.java2d;
import gnu.java.math.Fixed;
import java.awt.Shape;
import java.awt.geom.AffineTransform;
import java.awt.geom.PathIterator;
/**
* Rasterizes [EMAIL PROTECTED] Shape} objects on an AbstractGraphics2D.
*/
-final class ScanlineConverter
+public final class ScanlineConverter
{
/**
* The number of digits to use for fixed point arithmetics.
*/
private static int FIXED_DIGITS = 6;
/**
- * The fixed value for the number 1.
- */
- private static int ONE = Fixed.fixedValue(FIXED_DIGITS, 1);
-
- /**
* The actual number of scanlines.
*/
private int numScanlines;
/**
* The number of scanlines. This can contain more elements than we have
* scanlines. The real number of scanlines is stored in
* [EMAIL PROTECTED] #numScanlines}. This can also contain null values for empty
* scanlines.
*/
private Scanline[] scanlines;
/**
* The upper bounds which correspond to the index 0 in the scanline array.
*
* This is a fixed point value.
*/
private int upperBounds;
/**
* The resolution of the scanline converter.
*
* This is a fixed point value.
*/
private int resolution;
- private int scanlinesPerPixel;
-
/**
* One half step according to the resolution. This is stored to avoid
* unnecessary operations during rendering.
*/
private int halfStep;
/**
* This is used in [EMAIL PROTECTED] #addShape(PathIterator, boolean)} to
* receive the coordinates of the path.
*/
private float[] coords;
/**
* The active edges.
*/
private ActiveEdges activeEdges;
private PolyEdge edgePool;
private PolyEdge edgePoolLast;
private int minY;
private int maxY;
private int minX;
private int maxX;
- private int[] scanlineYCov;
- private int[] scanlineXCov;
- private int slPix0;
- private int alphaRes;
+ /**
+ * Holds and manages information about the pixel coverage.
+ */
+ private ScanlineCoverage scanlineCoverage;
/**
* Create a new ScanlineConverter.
*/
ScanlineConverter()
{
scanlines = new Scanline[10];
coords = new float[6];
activeEdges = new ActiveEdges();
edgePool = new PolyEdge();
edgePoolLast = edgePool;
+ scanlineCoverage = new ScanlineCoverage();
}
/**
* Renders the specified shape using the specified clip and transform.
*
+ * @param p the pixelizer that receives the coverage information
* @param shape the shape to render
* @param clip the clip
* @param trans the transform
*/
- void renderShape(AbstractGraphics2D g, Shape shape, Shape clip,
+ void renderShape(Pixelizer p, Shape shape, Shape clip,
AffineTransform trans, int res)
{
// Prepare resolution and upper bounds.
clear();
setResolution(res);
boolean haveClip = clip != null;
// Add shapes.
float flatness = Fixed.floatValue(FIXED_DIGITS, resolution / 2);
PathIterator path = shape.getPathIterator(trans, flatness);
addShape(path, false);
if (haveClip)
{
path= clip.getPathIterator(trans, flatness);
addShape(path, true);
}
setUpperBounds(minY);
PolyEdge edge = edgePool;
while (edge != edgePoolLast)
{
addEdge(edge);
edge = edge.poolNext;
}
- // For AA: Prepare the scanline pixels array.
- if (resolution < ONE)
- {
- int x0 = Fixed.intValue(FIXED_DIGITS, minX);
- int x1 = Fixed.intValue(FIXED_DIGITS, maxX) + 1;
- int span = x1 - x0;
- if (scanlineYCov == null || span >= scanlineYCov.length)
- {
- scanlineYCov = new int[span];
- scanlineXCov = new int[span];
- }
- slPix0 = x0;
- }
-
int y = upperBounds;
int index;
activeEdges.clear();
// The render loop...
Scanline scanline = null;
int lastRealY = Fixed.intValue(FIXED_DIGITS, y);
while (y <= maxY)
{
// First we put together our list of active edges.
index = scanlineIndex(y);
// If we go outside the scanline array we still need to render the
// remaining edges until they end.
scanline = index < scanlines.length ? scanlines[index] : null;
if (scanline != null)
{
edge = scanline.getEdges();
while (edge != null)
{
activeEdges.add(edge);
edge = edge.scanlineNext;
}
}
// Then we intersect all active edges with the current scanline
// and sort them according to their intersection points.
activeEdges.intersectSortAndPack(FIXED_DIGITS, y + halfStep);
// Ok, now we can perform the actual scanlining.
int realY = Fixed.intValue(FIXED_DIGITS, y + resolution);
boolean push = lastRealY != realY;
- doScanline(g, y, push, haveClip);
+ doScanline(p, y, push, haveClip);
// Remove obsolete active edges.
//activeEdges.remove(y + halfStep);
// Go on with the next line...
y += resolution;
lastRealY = realY;
}
}
/**
* Clears all scanlines.
*/
private void clear()
{
// Reset edge pool.
edgePoolLast = edgePool;
// Reset scanlines.
for (int i = scanlines.length - 1; i >= 0 ; i--)
{
Scanline sl = scanlines[i];
if (sl != null)
sl.clear();
}
+ // Reset scanline coverage.
+ scanlineCoverage.clear();
+
// Reset bounds.
minY = Integer.MAX_VALUE;
maxY = Integer.MIN_VALUE;
minX = Integer.MAX_VALUE;
maxX = Integer.MIN_VALUE;
}
/**
* Performs the scanlining on the current set of active edges.
+ *
+ * @param p the pixelizer to receive the pixel coverage data
+ * @param y the Y coordinate
+ * @param push true when the scanline is ready to be pushed to the
+ * pixelizer
+ * @param haveClip true when there's a clip, false otherwise
*/
- private void doScanline(AbstractGraphics2D g, int y, boolean push,
+ private void doScanline(Pixelizer p, int y, boolean push,
boolean haveClip)
{
-
+ // First, rewind the scanline coverage.
+ scanlineCoverage.rewind();
// We begin outside the clip and outside the shape. We only draw when
// we are inside the clip AND inside the shape.
boolean inClip = ! haveClip;
boolean inShape = false;
PolyEdge lastEdge = null;
int numEdges = activeEdges.getNumActiveEdges();
for (int i = 0; i < numEdges; i++)
{
PolyEdge edge = activeEdges.getActiveEdge(i);
if (inClip && inShape)
{
assert lastEdge != null;
int x0 = lastEdge.xIntersection;
int x1 = edge.xIntersection;
assert x0 <= x1;
- if (resolution == ONE)
- {
- // Non-AA rendering.
- g.fillScanline(Fixed.intValue(FIXED_DIGITS, x0 + resolution / 2),
- Fixed.intValue(FIXED_DIGITS, x1 - resolution / 2),
- Fixed.intValue(FIXED_DIGITS, y));
- }
- else
- {
- int pix0 = Fixed.intValue(FIXED_DIGITS, x0);
- int frac0 = ONE - (x0 - Fixed.floor(FIXED_DIGITS, x0));
- int pix1 = Fixed.intValue(FIXED_DIGITS, x1);
- int frac1 = ONE - (x1 - Fixed.floor(FIXED_DIGITS, x1));
- //System.err.println("render scanline AA: " + Fixed.floatValue(FIXED_DIGITS, y) + ", " + pix0 + ", " + pix1 + "(" + Fixed.floatValue(FIXED_DIGITS, x0) + ", " + Fixed.floatValue(FIXED_DIGITS, x1) +")");
- scanlineYCov[pix0 - slPix0] += alphaRes;
- scanlineYCov[pix1 - slPix0] -= alphaRes;
- scanlineXCov[pix0 - slPix0] += frac0;
- scanlineXCov[pix1 - slPix0] += frac1;
- }
+
+ int pix0 = Fixed.intValue(FIXED_DIGITS, x0);
+ int pix1 = Fixed.intValue(FIXED_DIGITS, x1);
+ //System.err.println("render scanline AA: " + Fixed.floatValue(FIXED_DIGITS, y) + ", " + pix0 + ", " + pix1 + "(" + Fixed.floatValue(FIXED_DIGITS, x0) + ", " + Fixed.floatValue(FIXED_DIGITS, x1) +")")
+ scanlineCoverage.add(pix0, 1);
+ scanlineCoverage.add(pix1, -1);
}
if (edge.isClip)
inClip = ! inClip;
else
inShape = ! inShape;
lastEdge = edge;
}
- // For AA we push out the scanline when necessary.
- if (push && ONE > resolution)
+ // Push out the whole scanline to the pixelizer.
+ if (push && ! scanlineCoverage.isEmpty())
{
- // Push out AA'ed scanline.
- int rx1 = 0;
- int alpha = 0;
- for (int idx = 0; idx < scanlineYCov.length; idx++)
- {
- rx1 = slPix0 + idx;
- if (scanlineYCov[idx] != 0)
- {
- // Render transitioning pixel with x coverage included.
- int transAlpha = alpha + (scanlineYCov[idx] * scanlineXCov[idx]) / (scanlinesPerPixel * 64);
- //System.err.println("pixel: " + rx1 + " old alpha: " + alpha + " ycov:" + scanlineYCov[idx] + " xcov: " + scanlineXCov[idx] + " tAlpha: " + transAlpha);
- g.fillScanlineAA(rx1, rx1,
- Fixed.intValue(FIXED_DIGITS, y),
- Math.max(Math.min(transAlpha, 255), 0));
- alpha = alpha + scanlineYCov[idx];
- }
- else if (alpha > 0)
- {
- //System.err.println("pixel: " + rx1 + " alpha: " + alpha);
- g.fillScanlineAA(rx1, rx1,
- Fixed.intValue(FIXED_DIGITS, y),
- Math.min(alpha, 255));
- }
- scanlineYCov[idx] = 0;
- scanlineXCov[idx] = 0;
- }
+ p.renderScanline(Fixed.intValue(FIXED_DIGITS, y), scanlineCoverage);
+ scanlineCoverage.clear();
}
}
/**
* Sets the resolution. A value of 0 rasterizes the shape normally without
* anti-aliasing. Greater values renders with a resolution of 2 ^ res.
*
* @param res the resolution
*/
private void setResolution(int res)
{
- scanlinesPerPixel = 1 << res;
+ int scanlinesPerPixel = 1 << res;
int one = Fixed.fixedValue(FIXED_DIGITS, 1);
- resolution = one / (1 << res);
+ resolution = one / (scanlinesPerPixel);
halfStep = resolution / 2;
- alphaRes = 256 >> res;
+ scanlineCoverage.setMaxCoverage(scanlinesPerPixel);
}
/**
* Sets the vertical bounds of that shape that is beeing rendered.
*
* @param y0 the upper bounds
*/
private void setUpperBounds(int y0)
{
upperBounds = fit(y0);
}
/**
* Add a shape to the scanline converter.
*
@@ -458,16 +412,26 @@
}
private void edgePoolAdd(int x0, int y0, int x1, int y1, boolean clip)
{
// Don't need no horizontal edges.
if (y0 != y1)
{
edgePoolLast.init(FIXED_DIGITS, x0, y0, x1, y1, clip);
if (edgePoolLast.poolNext == null)
{
edgePoolLast.poolNext = new PolyEdge();
}
edgePoolLast = edgePoolLast.poolNext;
}
}
+
+ /**
+ * Performs some tests.
+ *
+ * @param args
+ */
+ public static void main(String[] args)
+ {
+ ScanlineCoverage.test();
+ }
}
Index: gnu/java/awt/java2d/ScanlineCoverage.java
===================================================================
RCS file: gnu/java/awt/java2d/ScanlineCoverage.java
diff -N gnu/java/awt/java2d/ScanlineCoverage.java
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ gnu/java/awt/java2d/ScanlineCoverage.java 18 May 2007 16:22:00 -0000
@@ -0,0 +1,514 @@
+/* ScanlineCoverage.java -- Manages coverage information for a scanline
+ Copyright (C) 2007 Free Software Foundation, Inc.
+
+This file is part of GNU Classpath.
+
+GNU Classpath is free software; you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 2, or (at your option)
+any later version.
+
+GNU Classpath is distributed in the hope that it will be useful, but
+WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GNU Classpath; see the file COPYING. If not, write to the
+Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
+02110-1301 USA.
+
+Linking this library statically or dynamically with other modules is
+making a combined work based on this library. Thus, the terms and
+conditions of the GNU General Public License cover the whole
+combination.
+
+As a special exception, the copyright holders of this library give you
+permission to link this library with independent modules to produce an
+executable, regardless of the license terms of these independent
+modules, and to copy and distribute the resulting executable under
+terms of your choice, provided that you also meet, for each linked
+independent module, the terms and conditions of the license of that
+module. An independent module is a module which is not derived from
+or based on this library. If you modify this library, you may extend
+this exception to your version of the library, but you are not
+obligated to do so. If you do not wish to do so, delete this
+exception statement from your version. */
+
+package gnu.java.awt.java2d;
+
+/**
+ * Stores and handles the pixel converage for a scanline. The pixel coverage
+ * is stored as sorted list of [EMAIL PROTECTED] Covergage} entries, each of which holds
+ * information about the coverage for the X and Y axis. This is utilized to
+ * compute the actual coverage for each pixel on the scanline and finding
+ * chunks of pixels with equal coverage quickly.
+ */
+public final class ScanlineCoverage
+{
+
+ /**
+ * One bucket in the list.
+ */
+ public static final class Coverage
+ {
+ /**
+ * The X coordinate on the scanline to which this bucket belongs.
+ */
+ private int xPos;
+
+ /**
+ * The X coverage delta.
+ */
+ private int covDelta;
+
+ /**
+ * Implements a linked list. This points to the next element of the list.
+ */
+ Coverage next;
+
+ /**
+ * Returns the X coordinate for this entry.
+ *
+ * @return the X coordinate for this entry
+ */
+ public int getXPos()
+ {
+ return xPos;
+ }
+
+ /**
+ * Returns the coverage delta for this entry.
+ *
+ * @return the coverage delta for this entry
+ */
+ public int getCoverageDelta()
+ {
+ return covDelta;
+ }
+
+ /**
+ * Returns a string representation.
+ *
+ * @return a string representation
+ */
+ public String toString()
+ {
+ return "Coverage: xPos: " + xPos + ", covDelta: " + covDelta;
+ }
+
+ /**
+ * Returns a string representation of this entry and all the following
+ * in the linked list.
+ *
+ * @return a string representation of this entry and all the following
+ * in the linked list
+ */
+ public String list()
+ {
+ String str = toString();
+ if (next != null)
+ str = str + " --> " + next.list();
+ return str;
+ }
+ }
+
+ /**
+ * The head of the sorted list of buckets.
+ */
+ private Coverage head;
+
+ /**
+ * The current bucket. We make use of the fact that the scanline converter
+ * always scans the scanline (and thus this list) from left to right to
+ * quickly find buckets or insertion points.
+ */
+ private Coverage current;
+
+ /**
+ * The item that is before current in the list.
+ */
+ private Coverage currentPrev;
+
+ /**
+ * The bucket after the last valid bucket. Unused buckets are not thrown
+ * away and garbage collected. Instead, we keep them at the tail of the list
+ * and reuse them when necessary.
+ */
+ private Coverage last;
+
+ /**
+ * The last valid entry.
+ */
+ private Coverage lastPrev;
+
+ /**
+ * The minimum X coordinate of this scanline.
+ */
+ private int minX;
+
+ /**
+ * The maximum X coordinate of this scanline.
+ */
+ private int maxX;
+
+ /**
+ * The maximum coverage value.
+ */
+ private int maxCoverage;
+
+ /**
+ * Indicates the the next scan of the scanline begins and that the next
+ * request will be at the beginning of this list. This makes searching and
+ * sorting of this list very quick.
+ */
+ public void rewind()
+ {
+ current = head;
+ currentPrev = null;
+ }
+
+ /**
+ * Clears the list. This does not throw away the old buckets but only
+ * resets the end-pointer of the list to the first element. All buckets are
+ * then unused and are reused when the list is filled again.
+ */
+ public void clear()
+ {
+ last = head;
+ lastPrev = null;
+ current = head;
+ currentPrev = null;
+ minX = Integer.MAX_VALUE;
+ maxX = Integer.MIN_VALUE;
+ }
+
+ /**
+ * This adds the specified coverage to the pixel at the specified
+ * X position.
+ *
+ * @param x the X position
+ * @param xc the x coverage
+ * @param yc the y coverage
+ */
+ public void add(int x, int xc)
+ {
+ Coverage bucket = findOrInsert(x);
+ bucket.covDelta += xc;
+ minX = Math.min(minX, x);
+ maxX = Math.max(maxX, x);
+ }
+
+ /**
+ * Returns the maximum coverage value for the scanline.
+ *
+ * @return the maximum coverage value for the scanline
+ */
+ public int getMaxCoverage()
+ {
+ return maxCoverage;
+ }
+
+ /**
+ * Sets the maximum coverage value for the scanline.
+ *
+ * @param maxCov the maximum coverage value for the scanline
+ */
+ void setMaxCoverage(int maxCov)
+ {
+ maxCoverage = maxCov;
+ }
+
+ /**
+ * Returns the maximum X coordinate of the current scanline.
+ *
+ * @return the maximum X coordinate of the current scanline
+ */
+ public int getMaxX()
+ {
+ return maxX;
+ }
+
+ /**
+ * Returns the minimum X coordinate of the current scanline.
+ *
+ * @return the minimum X coordinate of the current scanline
+ */
+ public int getMinX()
+ {
+ return minX;
+ }
+
+ /**
+ * Finds the bucket in the list with the specified X coordinate.
+ * If no such bucket is found, then a new one is fetched (either a cached
+ * bucket from the end of the list or a newly allocated one) inserted at the
+ * correct position and returned.
+ *
+ * @param x the X coordinate
+ *
+ * @return a bucket to hold the coverage data
+ */
+ private Coverage findOrInsert(int x)
+ {
+ // First search for a matching bucket.
+ if (head == null)
+ {
+ // Special case: the list is still empty.
+ // Testpoint 1.
+ head = new Coverage();
+ head.xPos = x;
+ current = head;
+ currentPrev = null;
+ return head;
+ }
+
+ // This performs a linear search, starting from the current bucket.
+ // This is reasonably efficient because access to this list is always done
+ // in a linear fashion and we are usually not more then 1 or 2 buckets away
+ // from the one we're looking for.
+ Coverage match = current;
+ Coverage prev = currentPrev;
+ while (match != last && match.xPos < x)
+ {
+ prev = match;
+ match = match.next;
+ }
+
+ // At this point we have either found an entry with xPos >= x, or reached
+ // the end of the list (match == last || match == null).
+ if (match == null)
+ {
+ // End of the list. No cached items to reuse.
+ // Testpoint 2.
+ match = new Coverage();
+ match.xPos = x;
+ if (prev != null)
+ prev.next = match;
+ current = match;
+ currentPrev = prev;
+ return match;
+ }
+ else if (match == last)
+ {
+ // End of the list. Reuse this item. Expand list.
+ // Testpoint 3.
+ last = match.next;
+ lastPrev = match;
+ match.xPos = x;
+ match.covDelta = 0;
+ // Keep link to last element or null, indicating the end of the list.
+ current = match;
+ currentPrev = prev;
+ return match;
+ }
+
+ if (x == match.xPos)
+ {
+ // Special case: We have another coverage entry at the same location
+ // as an already existing entry. Return this.
+ // Testpoint 4.
+ current = match;
+ currentPrev = prev;
+ return match;
+ }
+ else // x <= match.xPos
+ {
+ assert (x <= match.xPos);
+ assert (prev == null ||x > prev.xPos);
+
+ // Create new entry, or reuse existing one.
+ Coverage cov;
+ if (last != null)
+ {
+ // Testpoint 5.
+ cov = last;
+ last = cov.next;
+ lastPrev.next = last;
+ }
+ else
+ {
+ // Testpoint 6.
+ cov = new Coverage();
+ }
+
+ cov.xPos = x;
+ cov.covDelta = 0;
+
+ // Insert this item in the list.
+ if (prev != null)
+ {
+ // Testpoint 5 & 6.
+ prev.next = cov;
+ cov.next = match;
+ current = cov;
+ currentPrev = prev;
+ }
+ else
+ {
+ // Testpoint 7.
+ assert (match == head);
+ // Insert at head.
+ head = cov;
+ head.next = match;
+ current = head;
+ currentPrev = null;
+ }
+ return cov;
+ }
+ }
+
+ /**
+ * (Re-)Starts iterating the coverage entries by returning the first Coverage
+ * item in the list. Pixels left to that entry have a zero coverage.
+ *
+ * @return the first coverage item
+ */
+ public Coverage iterate()
+ {
+ if (head == last)
+ current = null;
+ else
+ current = head;
+ currentPrev = null;
+ return current;
+ }
+
+ /**
+ * Returns the next coverage item in the list, according to the current
+ * iteration state.
+ *
+ * @return the next coverage item in the list or {@ null} if the end has
+ * been reached
+ */
+ public Coverage next()
+ {
+ currentPrev = current;
+ if (current == null || current.next == last)
+ current = null;
+ else
+ current = current.next;
+ return current;
+ }
+
+ /**
+ * Returns {@ true} if this object has no entries for the current scanline,
+ * {@ false} otherwise.
+ *
+ * @return {@ true} if this object has no entries for the current scanline,
+ * {@ false} otherwise
+ */
+ public boolean isEmpty()
+ {
+ return head == null || head == last;
+ }
+
+ /**
+ * Performs some tests to check if this class is working correctly.
+ * There are comments about a bunch of test points in this method, which
+ * correspond to other points in this class as commented.
+ */
+ static void test()
+ {
+ System.out.println("ScanlineCoverage test 1");
+ // Test testpoint 1 & 2.
+ ScanlineCoverage c = new ScanlineCoverage();
+ c.add(2, 3);
+ c.add(3, 4);
+ c.add(4, 5);
+
+ Coverage cov = c.iterate();
+ assertion(cov.xPos == 2);
+ assertion(cov.covDelta == 3);
+ cov = c.next();
+ assertion(cov.xPos == 3);
+ assertion(cov.covDelta == 4);
+ cov = c.next();
+ assertion(cov.xPos == 4);
+ assertion(cov.covDelta == 5);
+ assertion(c.next() == null);
+
+ System.out.println("ScanlineCoverage test 2");
+ // Test testpoint 3 and 4.
+ c.clear();
+ c.add(5, 4);
+ c.add(7, 5);
+ c.add(7, 10);
+ cov = c.iterate();
+ assertion(cov.xPos == 5);
+ assertion(cov.covDelta == 4);
+ cov = c.next();
+ assertion(cov.xPos == 7);
+ assertion(cov.covDelta == 15);
+ assertion(c.next() == null);
+
+ System.out.println("ScanlineCoverage test 3");
+ // Test testpoint 5.
+ c.rewind();
+ c.add(6, 20);
+ cov = c.iterate();
+ assertion(cov.xPos == 5);
+ assertion(cov.covDelta == 4);
+ cov = c.next();
+ assertion(cov.xPos == 6);
+ assertion(cov.covDelta == 20);
+ cov = c.next();
+ assertion(cov.xPos == 7);
+ assertion(cov.covDelta == 15);
+ assertion(c.next() == null);
+
+ System.out.println("ScanlineCoverage test 4");
+ // Test testpoint 6.
+ c.rewind();
+ c.add(8, 21);
+ cov = c.iterate();
+ assertion(cov.xPos == 5);
+ assertion(cov.covDelta == 4);
+ cov = c.next();
+ assertion(cov.xPos == 6);
+ assertion(cov.covDelta == 20);
+ cov = c.next();
+ assertion(cov.xPos == 7);
+ assertion(cov.covDelta == 15);
+ cov = c.next();
+ assertion(cov.xPos == 8);
+ assertion(cov.covDelta == 21);
+ assertion(c.next() == null);
+
+ System.out.println("ScanlineCoverage test 5");
+ // Test testpoint 6.
+ c.rewind();
+ c.add(2, 100);
+ cov = c.iterate();
+ assertion(cov.xPos == 2);
+ assertion(cov.covDelta == 100);
+ cov = c.next();
+ assertion(cov.xPos == 5);
+ assertion(cov.covDelta == 4);
+ cov = c.next();
+ assertion(cov.xPos == 6);
+ assertion(cov.covDelta == 20);
+ cov = c.next();
+ assertion(cov.xPos == 7);
+ assertion(cov.covDelta == 15);
+ cov = c.next();
+ assertion(cov.xPos == 8);
+ assertion(cov.covDelta == 21);
+ assertion(c.next() == null);
+
+ }
+
+ /**
+ * Checks a condition and throws and AssertionError if this condition
+ * fails.
+ *
+ * @param b the condition
+ */
+ private static void assertion(boolean b)
+ {
+ if (! b)
+ {
+ throw new AssertionError();
+ }
+ }
+}
