| Frames | No Frames |
1: /* ScanlineCoverage.java -- Manages coverage information for a scanline 2: Copyright (C) 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: package gnu.java.awt.java2d; 39: 40: /** 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. 46: */ 47: public final class ScanlineCoverage 48: { 49: 50: /** 51: * Iterates over the coverage list and calculates the actual coverage 52: * ranges on a scanline. 53: */ 54: public final class Iterator 55: { 56: /** 57: * This instance is reused in the iteration. 58: */ 59: private Range range; 60: 61: /** 62: * The pointer to the current item in the iteration. 63: */ 64: private Coverage currentItem; 65: 66: /** 67: * The current coverage value. 68: */ 69: private int currentCoverage; 70: 71: /** 72: * True when the current pixel coverage has already been handled, false 73: * otherwise. 74: */ 75: private boolean handledPixelCoverage; 76: 77: /** 78: * Creates a new CoverageIterator. 79: */ 80: Iterator() 81: { 82: range = new Range(); 83: } 84: 85: /** 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. 89: * 90: * @return the next coverage range on the scanline 91: */ 92: public Range next() 93: { 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) 97: { 98: // Handle single pixel coverage. 99: range.setXPos(currentItem.xPos); 100: range.setLength(1); 101: range.setCoverage(currentCoverage + currentItem.pixelCoverage); 102: handledPixelCoverage = true; 103: } 104: else 105: { 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; 113: } 114: return range; 115: } 116: 117: /** 118: * Returns {@ true} when there are more coverage ranges to iterate, 119: * {@ false} otherwise. 120: * 121: * @return {@ true} when there are more coverage ranges to iterate, 122: * {@ false} otherwise 123: */ 124: public boolean hasNext() 125: { 126: boolean hasNext; 127: if (currentItem != null && handledPixelCoverage == false) 128: { 129: // We have at least one more coverage item when there's a pixel 130: // coverage piece left. 131: hasNext = true; 132: } 133: else if (currentItem == null || currentItem.next == null 134: || currentItem.next == last) 135: { 136: hasNext = false; 137: } 138: else 139: { 140: hasNext = true; 141: } 142: return hasNext; 143: } 144: 145: /** 146: * Resets this iterator to the start of the list. 147: */ 148: void reset() 149: { 150: currentItem = head; 151: currentCoverage = 0; 152: handledPixelCoverage = false; 153: } 154: } 155: 156: /** 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. 160: **/ 161: public static final class Range 162: { 163: /** 164: * The X position on the scanline, in pixels. 165: */ 166: private int xPos; 167: 168: /** 169: * The length of the range, in pixels. 170: */ 171: private int length; 172: 173: /** 174: * The actual coverage. The relation depends on 175: * {@link ScanlineCoverage#maxCoverage}. 176: */ 177: private int coverage; 178: 179: /** 180: * Creates a new CoverageRange object. 181: */ 182: Range() 183: { 184: // Nothing to do. The values get initialized in the corresponding 185: // setters. 186: } 187: 188: /** 189: * Sets the X start position (left) on the scanline. This value is 190: * considered to be in pixels and device space. 191: * 192: * @param x the x position 193: */ 194: void setXPos(int x) 195: { 196: xPos = x; 197: } 198: 199: /** 200: * Returns the X start position (left) on the scanline. This value 201: * is considered to be in pixels and device space. 202: * 203: * @return the X position on the scanline 204: */ 205: public int getXPos() 206: { 207: return xPos; 208: } 209: 210: /** 211: * Sets the length of the pixel range. This is in pixel units. 212: * 213: * @param l the length of the range 214: */ 215: void setLength(int l) 216: { 217: length = l; 218: } 219: 220: /** 221: * Returns the length of the range in pixel units. 222: * 223: * @return the length of the range in pixel units 224: */ 225: public int getLength() 226: { 227: return length; 228: } 229: 230: /** 231: * Returns the first X position after the range. 232: * 233: * @return the first X position after the range 234: */ 235: public int getXPosEnd() 236: { 237: return xPos + length; 238: } 239: 240: /** 241: * Sets the coverage of the pixel range. The relation of that value 242: * depends on {@link ScanlineCoverage#maxCoverage}. 243: * 244: * @param cov the coverage value for the pixel range 245: */ 246: void setCoverage(int cov) 247: { 248: coverage = cov; 249: } 250: 251: /** 252: * Returns the coverage of the pixel range. The relation of this value 253: * depends on {@link ScanlineCoverage#getMaxCoverage()}. 254: * 255: * @return the coverage of the pixel range 256: */ 257: public int getCoverage() 258: { 259: return coverage; 260: } 261: 262: /** 263: * Returns a string representation. 264: */ 265: public String toString() 266: { 267: return "Coverage range: xPos=" + xPos + ", length=" + length 268: + ", coverage: " + coverage; 269: } 270: } 271: 272: /** 273: * One bucket in the list. 274: */ 275: private static final class Coverage 276: { 277: /** 278: * The X coordinate on the scanline to which this bucket belongs. 279: */ 280: int xPos; 281: 282: /** 283: * The coverage delta from the pixel at xPos to xPos + 1. 284: */ 285: int covDelta; 286: 287: /** 288: * The delta for the pixel at xPos. This is added to the pixel at xPos, 289: * but not to the following pixel. 290: */ 291: int pixelCoverage; 292: 293: /** 294: * Implements a linked list. This points to the next element of the list. 295: */ 296: Coverage next; 297: 298: /** 299: * Returns the X coordinate for this entry. 300: * 301: * @return the X coordinate for this entry 302: */ 303: public int getXPos() 304: { 305: return xPos; 306: } 307: 308: /** 309: * Returns the coverage delta for this entry. 310: * 311: * @return the coverage delta for this entry 312: */ 313: public int getCoverageDelta() 314: { 315: return covDelta; 316: } 317: 318: /** 319: * Returns a string representation. 320: * 321: * @return a string representation 322: */ 323: public String toString() 324: { 325: return "Coverage: xPos: " + xPos + ", covDelta: " + covDelta; 326: } 327: 328: /** 329: * Returns a string representation of this entry and all the following 330: * in the linked list. 331: * 332: * @return a string representation of this entry and all the following 333: * in the linked list 334: */ 335: public String list() 336: { 337: String str = toString(); 338: if (next != null) 339: str = str + " --> " + next.list(); 340: return str; 341: } 342: } 343: 344: /** 345: * The head of the sorted list of buckets. 346: */ 347: private Coverage head; 348: 349: /** 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. 353: */ 354: private Coverage current; 355: 356: /** 357: * The item that is before current in the list. 358: */ 359: private Coverage currentPrev; 360: 361: /** 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. 365: */ 366: private Coverage last; 367: 368: /** 369: * The last valid entry. 370: */ 371: private Coverage lastPrev; 372: 373: /** 374: * The minimum X coordinate of this scanline. 375: */ 376: private int minX; 377: 378: /** 379: * The maximum X coordinate of this scanline. 380: */ 381: private int maxX; 382: 383: /** 384: * The maximum coverage value. 385: */ 386: private int maxCoverage; 387: 388: /** 389: * The iterator over the ranges of this scanline. 390: */ 391: private Iterator iterator; 392: 393: /** 394: * Creates a new ScanlineCoverage instance. 395: */ 396: public ScanlineCoverage() 397: { 398: iterator = new Iterator(); 399: } 400: 401: /** 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. 405: */ 406: public void rewind() 407: { 408: current = head; 409: currentPrev = null; 410: } 411: 412: /** 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. 416: */ 417: public void clear() 418: { 419: last = head; 420: lastPrev = null; 421: current = head; 422: currentPrev = null; 423: minX = Integer.MAX_VALUE; 424: maxX = Integer.MIN_VALUE; 425: } 426: 427: /** 428: * This adds the specified coverage to the pixel at the specified 429: * X position. 430: * 431: * @param x the X position 432: * @param xc the x coverage 433: * @param yc the y coverage 434: */ 435: public void add(int x, int xc, int yc) 436: { 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); 442: } 443: 444: /** 445: * Returns the maximum coverage value for the scanline. 446: * 447: * @return the maximum coverage value for the scanline 448: */ 449: public int getMaxCoverage() 450: { 451: return maxCoverage; 452: } 453: 454: /** 455: * Sets the maximum coverage value for the scanline. 456: * 457: * @param maxCov the maximum coverage value for the scanline 458: */ 459: void setMaxCoverage(int maxCov) 460: { 461: maxCoverage = maxCov; 462: } 463: 464: /** 465: * Returns the maximum X coordinate of the current scanline. 466: * 467: * @return the maximum X coordinate of the current scanline 468: */ 469: public int getMaxX() 470: { 471: return maxX; 472: } 473: 474: /** 475: * Returns the minimum X coordinate of the current scanline. 476: * 477: * @return the minimum X coordinate of the current scanline 478: */ 479: public int getMinX() 480: { 481: return minX; 482: } 483: 484: /** 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. 489: * 490: * @param x the X coordinate 491: * 492: * @return a bucket to hold the coverage data 493: */ 494: private Coverage findOrInsert(int x) 495: { 496: // First search for a matching bucket. 497: if (head == null) 498: { 499: // Special case: the list is still empty. 500: // Testpoint 1. 501: head = new Coverage(); 502: head.xPos = x; 503: current = head; 504: currentPrev = null; 505: return head; 506: } 507: 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) 515: { 516: prev = match; 517: match = match.next; 518: } 519: 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). 522: if (match == null) 523: { 524: // End of the list. No cached items to reuse. 525: // Testpoint 2. 526: match = new Coverage(); 527: match.xPos = x; 528: if (prev != null) 529: prev.next = match; 530: current = match; 531: currentPrev = prev; 532: return match; 533: } 534: else if (match == last) 535: { 536: // End of the list. Reuse this item. Expand list. 537: // Testpoint 3. 538: last = match.next; 539: lastPrev = match; 540: match.xPos = x; 541: match.covDelta = 0; 542: match.pixelCoverage = 0; 543: // Keep link to last element or null, indicating the end of the list. 544: current = match; 545: currentPrev = prev; 546: return match; 547: } 548: 549: if (x == match.xPos) 550: { 551: // Special case: We have another coverage entry at the same location 552: // as an already existing entry. Return this. 553: // Testpoint 4. 554: current = match; 555: currentPrev = prev; 556: return match; 557: } 558: else // x <= match.xPos 559: { 560: assert (x <= match.xPos); 561: assert (prev == null ||x > prev.xPos); 562: 563: // Create new entry, or reuse existing one. 564: Coverage cov; 565: if (last != null) 566: { 567: // Testpoint 5. 568: cov = last; 569: last = cov.next; 570: lastPrev.next = last; 571: } 572: else 573: { 574: // Testpoint 6. 575: cov = new Coverage(); 576: } 577: 578: cov.xPos = x; 579: cov.covDelta = 0; 580: cov.pixelCoverage = 0; 581: 582: // Insert this item in the list. 583: if (prev != null) 584: { 585: // Testpoint 5 & 6. 586: prev.next = cov; 587: cov.next = match; 588: current = cov; 589: currentPrev = prev; 590: } 591: else 592: { 593: // Testpoint 7. 594: assert (match == head); 595: // Insert at head. 596: head = cov; 597: head.next = match; 598: current = head; 599: currentPrev = null; 600: } 601: return cov; 602: } 603: } 604: 605: /** 606: * (Re-)Starts iterating the coverage values for the scanline. 607: * Use the returned iterator to get the consecutive coverage ranges. 608: * 609: * @return the iterator 610: */ 611: public Iterator iterate() 612: { 613: iterator.reset(); 614: return iterator; 615: } 616: 617: /** 618: * Returns {@ true} if this object has no entries for the current scanline, 619: * {@ false} otherwise. 620: * 621: * @return {@ true} if this object has no entries for the current scanline, 622: * {@ false} otherwise 623: */ 624: public boolean isEmpty() 625: { 626: return head == null || head == last 627: || head.next == null || head.next == last; 628: } 629: 630: }