1 /* ScanlineCoverage.java -- Manages coverage information for a scanline
2 Copyright (C) 2007 Free Software Foundation, Inc.
4 This file is part of GNU Classpath.
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)
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.
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
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
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. */
38 package gnu
.java
.awt
.java2d
;
41 * Stores and handles the pixel converage for a scanline. The pixel coverage
42 * is stored as sorted list of {@linke Covergage} entries, each of which holds
43 * information about the coverage for the X and Y axis. This is utilized to
44 * compute the actual coverage for each pixel on the scanline and finding
45 * chunks of pixels with equal coverage quickly.
47 public final class ScanlineCoverage
51 * Iterates over the coverage list and calculates the actual coverage
52 * ranges on a scanline.
54 public final class Iterator
57 * This instance is reused in the iteration.
62 * The pointer to the current item in the iteration.
64 private Coverage currentItem
;
67 * The current coverage value.
69 private int currentCoverage
;
72 * True when the current pixel coverage has already been handled, false
75 private boolean handledPixelCoverage
;
78 * Creates a new CoverageIterator.
86 * Returns the next coverage range on the scanline. The returned object
87 * will always be the same object, but with different values. Keep that
88 * in mind when dealing with this object.
90 * @return the next coverage range on the scanline
94 // TODO: Lump together the single-pixel coverage and the
95 // between-pixel coverage when the pixel coverage delta is 0.
96 if (handledPixelCoverage
== false)
98 // Handle single pixel coverage.
99 range
.setXPos(currentItem
.xPos
);
101 range
.setCoverage(currentCoverage
+ currentItem
.pixelCoverage
);
102 handledPixelCoverage
= true;
106 // Handle pixel span coverage.
107 currentCoverage
+= currentItem
.covDelta
;
108 range
.setCoverage(currentCoverage
);
109 range
.setXPos(currentItem
.xPos
+ 1);
110 currentItem
= currentItem
.next
;
111 range
.setLength(currentItem
.xPos
- range
.xPos
);
112 handledPixelCoverage
= false;
118 * Returns {@ true} when there are more coverage ranges to iterate,
119 * {@ false} otherwise.
121 * @return {@ true} when there are more coverage ranges to iterate,
122 * {@ false} otherwise
124 public boolean hasNext()
127 if (currentItem
!= null && handledPixelCoverage
== false)
129 // We have at least one more coverage item when there's a pixel
130 // coverage piece left.
133 else if (currentItem
== null || currentItem
.next
== null
134 || currentItem
.next
== last
)
146 * Resets this iterator to the start of the list.
152 handledPixelCoverage
= false;
157 * A data object that carries information about pixel coverage on a scanline.
158 * The data consists of a starting X position on the scanline, the
159 * length of the range in pixels and the actual coverage value.
161 public static final class Range
164 * The X position on the scanline, in pixels.
169 * The length of the range, in pixels.
174 * The actual coverage. The relation depends on
175 * {@link ScanlineCoverage#maxCoverage}.
177 private int coverage
;
180 * Creates a new CoverageRange object.
184 // Nothing to do. The values get initialized in the corresponding
189 * Sets the X start position (left) on the scanline. This value is
190 * considered to be in pixels and device space.
192 * @param x the x position
200 * Returns the X start position (left) on the scanline. This value
201 * is considered to be in pixels and device space.
203 * @return the X position on the scanline
211 * Sets the length of the pixel range. This is in pixel units.
213 * @param l the length of the range
215 void setLength(int l
)
221 * Returns the length of the range in pixel units.
223 * @return the length of the range in pixel units
225 public int getLength()
231 * Returns the first X position after the range.
233 * @return the first X position after the range
235 public int getXPosEnd()
237 return xPos
+ length
;
241 * Sets the coverage of the pixel range. The relation of that value
242 * depends on {@link ScanlineCoverage#maxCoverage}.
244 * @param cov the coverage value for the pixel range
246 void setCoverage(int cov
)
252 * Returns the coverage of the pixel range. The relation of this value
253 * depends on {@link ScanlineCoverage#getMaxCoverage()}.
255 * @return the coverage of the pixel range
257 public int getCoverage()
263 * Returns a string representation.
265 public String
toString()
267 return "Coverage range: xPos=" + xPos
+ ", length=" + length
268 + ", coverage: " + coverage
;
273 * One bucket in the list.
275 private static final class Coverage
278 * The X coordinate on the scanline to which this bucket belongs.
283 * The coverage delta from the pixel at xPos to xPos + 1.
288 * The delta for the pixel at xPos. This is added to the pixel at xPos,
289 * but not to the following pixel.
294 * Implements a linked list. This points to the next element of the list.
299 * Returns the X coordinate for this entry.
301 * @return the X coordinate for this entry
309 * Returns the coverage delta for this entry.
311 * @return the coverage delta for this entry
313 public int getCoverageDelta()
319 * Returns a string representation.
321 * @return a string representation
323 public String
toString()
325 return "Coverage: xPos: " + xPos
+ ", covDelta: " + covDelta
;
329 * Returns a string representation of this entry and all the following
330 * in the linked list.
332 * @return a string representation of this entry and all the following
337 String str
= toString();
339 str
= str
+ " --> " + next
.list();
345 * The head of the sorted list of buckets.
347 private Coverage head
;
350 * The current bucket. We make use of the fact that the scanline converter
351 * always scans the scanline (and thus this list) from left to right to
352 * quickly find buckets or insertion points.
354 private Coverage current
;
357 * The item that is before current in the list.
359 private Coverage currentPrev
;
362 * The bucket after the last valid bucket. Unused buckets are not thrown
363 * away and garbage collected. Instead, we keep them at the tail of the list
364 * and reuse them when necessary.
366 private Coverage last
;
369 * The last valid entry.
371 private Coverage lastPrev
;
374 * The minimum X coordinate of this scanline.
379 * The maximum X coordinate of this scanline.
384 * The maximum coverage value.
386 private int maxCoverage
;
389 * The iterator over the ranges of this scanline.
391 private Iterator iterator
;
394 * Creates a new ScanlineCoverage instance.
396 public ScanlineCoverage()
398 iterator
= new Iterator();
402 * Indicates the the next scan of the scanline begins and that the next
403 * request will be at the beginning of this list. This makes searching and
404 * sorting of this list very quick.
413 * Clears the list. This does not throw away the old buckets but only
414 * resets the end-pointer of the list to the first element. All buckets are
415 * then unused and are reused when the list is filled again.
423 minX
= Integer
.MAX_VALUE
;
424 maxX
= Integer
.MIN_VALUE
;
428 * This adds the specified coverage to the pixel at the specified
431 * @param x the X position
432 * @param xc the x coverage
433 * @param yc the y coverage
435 public void add(int x
, int xc
, int yc
)
437 Coverage bucket
= findOrInsert(x
);
438 bucket
.covDelta
+= xc
;
439 bucket
.pixelCoverage
+= yc
;
440 minX
= Math
.min(minX
, x
);
441 maxX
= Math
.max(maxX
, x
);
445 * Returns the maximum coverage value for the scanline.
447 * @return the maximum coverage value for the scanline
449 public int getMaxCoverage()
455 * Sets the maximum coverage value for the scanline.
457 * @param maxCov the maximum coverage value for the scanline
459 void setMaxCoverage(int maxCov
)
461 maxCoverage
= maxCov
;
465 * Returns the maximum X coordinate of the current scanline.
467 * @return the maximum X coordinate of the current scanline
475 * Returns the minimum X coordinate of the current scanline.
477 * @return the minimum X coordinate of the current scanline
485 * Finds the bucket in the list with the specified X coordinate.
486 * If no such bucket is found, then a new one is fetched (either a cached
487 * bucket from the end of the list or a newly allocated one) inserted at the
488 * correct position and returned.
490 * @param x the X coordinate
492 * @return a bucket to hold the coverage data
494 private Coverage
findOrInsert(int x
)
496 // First search for a matching bucket.
499 // Special case: the list is still empty.
501 head
= new Coverage();
508 // This performs a linear search, starting from the current bucket.
509 // This is reasonably efficient because access to this list is always done
510 // in a linear fashion and we are usually not more then 1 or 2 buckets away
511 // from the one we're looking for.
512 Coverage match
= current
;
513 Coverage prev
= currentPrev
;
514 while (match
!= last
&& match
.xPos
< x
)
520 // At this point we have either found an entry with xPos >= x, or reached
521 // the end of the list (match == last || match == null).
524 // End of the list. No cached items to reuse.
526 match
= new Coverage();
534 else if (match
== last
)
536 // End of the list. Reuse this item. Expand list.
542 match
.pixelCoverage
= 0;
543 // Keep link to last element or null, indicating the end of the list.
551 // Special case: We have another coverage entry at the same location
552 // as an already existing entry. Return this.
558 else // x <= match.xPos
560 assert (x
<= match
.xPos
);
561 assert (prev
== null ||x
> prev
.xPos
);
563 // Create new entry, or reuse existing one.
570 lastPrev
.next
= last
;
575 cov
= new Coverage();
580 cov
.pixelCoverage
= 0;
582 // Insert this item in the list.
594 assert (match
== head
);
606 * (Re-)Starts iterating the coverage values for the scanline.
607 * Use the returned iterator to get the consecutive coverage ranges.
609 * @return the iterator
611 public Iterator
iterate()
618 * Returns {@ true} if this object has no entries for the current scanline,
619 * {@ false} otherwise.
621 * @return {@ true} if this object has no entries for the current scanline,
622 * {@ false} otherwise
624 public boolean isEmpty()
626 return head
== null || head
== last
627 || head
.next
== null || head
.next
== last
;