juce/source/src/gui/graphics/contexts/juce_EdgeTable.cpp

   1 /*
   2   ==============================================================================
   3
   4    This file is part of the JUCE library - "Jules' Utility Class Extensions"
   5    Copyright 2004-11 by Raw Material Software Ltd.
   6
   7   ------------------------------------------------------------------------------
   8
   9    JUCE can be redistributed and/or modified under the terms of the GNU General
  10    Public License (Version 2), as published by the Free Software Foundation.
  11    A copy of the license is included in the JUCE distribution, or can be found
  12    online at www.gnu.org/licenses.
  13
  14    JUCE is distributed in the hope that it will be useful, but WITHOUT ANY
  15    WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
  16    A PARTICULAR PURPOSE.  See the GNU General Public License for more details.
  17
  18   ------------------------------------------------------------------------------
  19
  20    To release a closed-source product which uses JUCE, commercial licenses are
  21    available: visit www.rawmaterialsoftware.com/juce for more information.
  22
  23   ==============================================================================
  24 */
  25
  26 #include "../../../core/juce_StandardHeader.h"
  27
  28 BEGIN_JUCE_NAMESPACE
  29
  30 #include "juce_EdgeTable.h"
  31 #include "../geometry/juce_PathIterator.h"
  32 #include "../imaging/juce_Image.h"
  33 #include "../geometry/juce_RectangleList.h"
  34
  35 const int juce_edgeTableDefaultEdgesPerLine = 32;
  36
  37 //==============================================================================
  38 EdgeTable::EdgeTable (const Rectangle<int>& bounds_,
  39                       const Path& path, const AffineTransform& transform)
  40    : bounds (bounds_),
  41      maxEdgesPerLine (juce_edgeTableDefaultEdgesPerLine),
  42      lineStrideElements ((juce_edgeTableDefaultEdgesPerLine << 1) + 1),
  43      needToCheckEmptinesss (true)
  44 {
  45     table.malloc ((bounds.getHeight() + 1) * lineStrideElements);
  46     int* t = table;
  47
  48     for (int i = bounds.getHeight(); --i >= 0;)
  49     {
  50         *t = 0;
  51         t += lineStrideElements;
  52     }
  53
  54     const int topLimit = bounds.getY() << 8;
  55     const int heightLimit = bounds.getHeight() << 8;
  56     const int leftLimit = bounds.getX() << 8;
  57     const int rightLimit = bounds.getRight() << 8;
  58
  59     PathFlatteningIterator iter (path, transform);
  60
  61     while (iter.next())
  62     {
  63         int y1 = roundToInt (iter.y1 * 256.0f);
  64         int y2 = roundToInt (iter.y2 * 256.0f);
  65
  66         if (y1 != y2)
  67         {
  68             y1 -= topLimit;
  69             y2 -= topLimit;
  70
  71             const int startY = y1;
  72             int direction = -1;
  73
  74             if (y1 > y2)
  75             {
  76                 std::swap (y1, y2);
  77                 direction = 1;
  78             }
  79
  80             if (y1 < 0)
  81                 y1 = 0;
  82
  83             if (y2 > heightLimit)
  84                 y2 = heightLimit;
  85
  86             if (y1 < y2)
  87             {
  88                 const double startX = 256.0f * iter.x1;
  89                 const double multiplier = (iter.x2 - iter.x1) / (iter.y2 - iter.y1);
  90                 const int stepSize = jlimit (1, 256, 256 / (1 + (int) std::abs (multiplier)));
  91
  92                 do
  93                 {
  94                     const int step = jmin (stepSize, y2 - y1, 256 - (y1 & 255));
  95                     int x = roundToInt (startX + multiplier * ((y1 + (step >> 1)) - startY));
  96
  97                     if (x < leftLimit)
  98                         x = leftLimit;
  99                     else if (x >= rightLimit)
 100                         x = rightLimit - 1;
 101
 102                     addEdgePoint (x, y1 >> 8, direction * step);
 103                     y1 += step;
 104                 }
 105                 while (y1 < y2);
 106             }
 107         }
 108     }
 109
 110     sanitiseLevels (path.isUsingNonZeroWinding());
 111 }
 112
 113 EdgeTable::EdgeTable (const Rectangle<int>& rectangleToAdd)
 114    : bounds (rectangleToAdd),
 115      maxEdgesPerLine (juce_edgeTableDefaultEdgesPerLine),
 116      lineStrideElements ((juce_edgeTableDefaultEdgesPerLine << 1) + 1),
 117      needToCheckEmptinesss (true)
 118 {
 119     table.malloc (jmax (1, bounds.getHeight()) * lineStrideElements);
 120     table[0] = 0;
 121
 122     const int x1 = rectangleToAdd.getX() << 8;
 123     const int x2 = rectangleToAdd.getRight() << 8;
 124
 125     int* t = table;
 126     for (int i = rectangleToAdd.getHeight(); --i >= 0;)
 127     {
 128         t[0] = 2;
 129         t[1] = x1;
 130         t[2] = 255;
 131         t[3] = x2;
 132         t[4] = 0;
 133         t += lineStrideElements;
 134     }
 135 }
 136
 137 EdgeTable::EdgeTable (const RectangleList& rectanglesToAdd)
 138    : bounds (rectanglesToAdd.getBounds()),
 139      maxEdgesPerLine (juce_edgeTableDefaultEdgesPerLine),
 140      lineStrideElements ((juce_edgeTableDefaultEdgesPerLine << 1) + 1),
 141      needToCheckEmptinesss (true)
 142 {
 143     table.malloc (jmax (1, bounds.getHeight()) * lineStrideElements);
 144
 145     int* t = table;
 146     for (int i = bounds.getHeight(); --i >= 0;)
 147     {
 148         *t = 0;
 149         t += lineStrideElements;
 150     }
 151
 152     for (RectangleList::Iterator iter (rectanglesToAdd); iter.next();)
 153     {
 154         const Rectangle<int>* const r = iter.getRectangle();
 155
 156         const int x1 = r->getX() << 8;
 157         const int x2 = r->getRight() << 8;
 158         int y = r->getY() - bounds.getY();
 159
 160         for (int j = r->getHeight(); --j >= 0;)
 161         {
 162             addEdgePoint (x1, y, 255);
 163             addEdgePoint (x2, y, -255);
 164             ++y;
 165         }
 166     }
 167
 168     sanitiseLevels (true);
 169 }
 170
 171 EdgeTable::EdgeTable (const Rectangle<float>& rectangleToAdd)
 172    : bounds (Rectangle<int> ((int) std::floor (rectangleToAdd.getX()),
 173                              roundToInt (rectangleToAdd.getY() * 256.0f) >> 8,
 174                              2 + (int) rectangleToAdd.getWidth(),
 175                              2 + (int) rectangleToAdd.getHeight())),
 176      maxEdgesPerLine (juce_edgeTableDefaultEdgesPerLine),
 177      lineStrideElements ((juce_edgeTableDefaultEdgesPerLine << 1) + 1),
 178      needToCheckEmptinesss (true)
 179 {
 180     jassert (! rectangleToAdd.isEmpty());
 181     table.malloc (jmax (1, bounds.getHeight()) * lineStrideElements);
 182     table[0] = 0;
 183
 184     const int x1 = roundToInt (rectangleToAdd.getX() * 256.0f);
 185     const int x2 = roundToInt (rectangleToAdd.getRight() * 256.0f);
 186
 187     int y1 = roundToInt (rectangleToAdd.getY() * 256.0f) - (bounds.getY() << 8);
 188     jassert (y1 < 256);
 189     int y2 = roundToInt (rectangleToAdd.getBottom() * 256.0f) - (bounds.getY() << 8);
 190
 191     if (x2 <= x1 || y2 <= y1)
 192     {
 193         bounds.setHeight (0);
 194         return;
 195     }
 196
 197     int lineY = 0;
 198     int* t = table;
 199
 200     if ((y1 >> 8) == (y2 >> 8))
 201     {
 202         t[0] = 2;
 203         t[1] = x1;
 204         t[2] = y2 - y1;
 205         t[3] = x2;
 206         t[4] = 0;
 207         ++lineY;
 208         t += lineStrideElements;
 209     }
 210     else
 211     {
 212         t[0] = 2;
 213         t[1] = x1;
 214         t[2] = 255 - (y1 & 255);
 215         t[3] = x2;
 216         t[4] = 0;
 217         ++lineY;
 218         t += lineStrideElements;
 219
 220         while (lineY < (y2 >> 8))
 221         {
 222             t[0] = 2;
 223             t[1] = x1;
 224             t[2] = 255;
 225             t[3] = x2;
 226             t[4] = 0;
 227             ++lineY;
 228             t += lineStrideElements;
 229         }
 230
 231         jassert (lineY < bounds.getHeight());
 232         t[0] = 2;
 233         t[1] = x1;
 234         t[2] = y2 & 255;
 235         t[3] = x2;
 236         t[4] = 0;
 237         ++lineY;
 238         t += lineStrideElements;
 239     }
 240
 241     while (lineY < bounds.getHeight())
 242     {
 243         t[0] = 0;
 244         t += lineStrideElements;
 245         ++lineY;
 246     }
 247 }
 248
 249 EdgeTable::EdgeTable (const EdgeTable& other)
 250 {
 251     operator= (other);
 252 }
 253
 254 EdgeTable& EdgeTable::operator= (const EdgeTable& other)
 255 {
 256     bounds = other.bounds;
 257     maxEdgesPerLine = other.maxEdgesPerLine;
 258     lineStrideElements = other.lineStrideElements;
 259     needToCheckEmptinesss = other.needToCheckEmptinesss;
 260
 261     table.malloc (jmax (1, bounds.getHeight()) * lineStrideElements);
 262     copyEdgeTableData (table, lineStrideElements, other.table, lineStrideElements, bounds.getHeight());
 263     return *this;
 264 }
 265
 266 EdgeTable::~EdgeTable()
 267 {
 268 }
 269
 270 //==============================================================================
 271 void EdgeTable::copyEdgeTableData (int* dest, const int destLineStride, const int* src, const int srcLineStride, int numLines) noexcept
 272 {
 273     while (--numLines >= 0)
 274     {
 275         memcpy (dest, src, (src[0] * 2 + 1) * sizeof (int));
 276         src += srcLineStride;
 277         dest += destLineStride;
 278     }
 279 }
 280
 281 void EdgeTable::sanitiseLevels (const bool useNonZeroWinding) noexcept
 282 {
 283     // Convert the table from relative windings to absolute levels..
 284     int* lineStart = table;
 285
 286     for (int i = bounds.getHeight(); --i >= 0;)
 287     {
 288         int* line = lineStart;
 289         lineStart += lineStrideElements;
 290
 291         int num = *line;
 292         if (num == 0)
 293             continue;
 294
 295         int level = 0;
 296
 297         if (useNonZeroWinding)
 298         {
 299             while (--num > 0)
 300             {
 301                 line += 2;
 302                 level += *line;
 303                 int corrected = abs (level);
 304                 if (corrected >> 8)
 305                     corrected = 255;
 306
 307                 *line = corrected;
 308             }
 309         }
 310         else
 311         {
 312             while (--num > 0)
 313             {
 314                 line += 2;
 315                 level += *line;
 316                 int corrected = abs (level);
 317                 if (corrected >> 8)
 318                 {
 319                     corrected &= 511;
 320                     if (corrected >> 8)
 321                         corrected = 511 - corrected;
 322                 }
 323
 324                 *line = corrected;
 325             }
 326         }
 327
 328         line[2] = 0; // force the last level to 0, just in case something went wrong in creating the table
 329     }
 330 }
 331
 332 void EdgeTable::remapTableForNumEdges (const int newNumEdgesPerLine)
 333 {
 334     if (newNumEdgesPerLine != maxEdgesPerLine)
 335     {
 336         maxEdgesPerLine = newNumEdgesPerLine;
 337
 338         jassert (bounds.getHeight() > 0);
 339         const int newLineStrideElements = maxEdgesPerLine * 2 + 1;
 340
 341         HeapBlock <int> newTable (bounds.getHeight() * newLineStrideElements);
 342
 343         copyEdgeTableData (newTable, newLineStrideElements, table, lineStrideElements, bounds.getHeight());
 344
 345         table.swapWith (newTable);
 346         lineStrideElements = newLineStrideElements;
 347     }
 348 }
 349
 350 void EdgeTable::optimiseTable()
 351 {
 352     int maxLineElements = 0;
 353
 354     for (int i = bounds.getHeight(); --i >= 0;)
 355         maxLineElements = jmax (maxLineElements, table [i * lineStrideElements]);
 356
 357     remapTableForNumEdges (maxLineElements);
 358 }
 359
 360 void EdgeTable::addEdgePoint (const int x, const int y, const int winding)
 361 {
 362     jassert (y >= 0 && y < bounds.getHeight());
 363
 364     int* line = table + lineStrideElements * y;
 365     const int numPoints = line[0];
 366     int n = numPoints << 1;
 367
 368     if (n > 0)
 369     {
 370         while (n > 0)
 371         {
 372             const int cx = line [n - 1];
 373
 374             if (cx <= x)
 375             {
 376                 if (cx == x)
 377                 {
 378                     line [n] += winding;
 379                     return;
 380                 }
 381
 382                 break;
 383             }
 384
 385             n -= 2;
 386         }
 387
 388         if (numPoints >= maxEdgesPerLine)
 389         {
 390             remapTableForNumEdges (maxEdgesPerLine + juce_edgeTableDefaultEdgesPerLine);
 391             jassert (numPoints < maxEdgesPerLine);
 392             line = table + lineStrideElements * y;
 393         }
 394
 395         memmove (line + (n + 3), line + (n + 1), sizeof (int) * ((numPoints << 1) - n));
 396     }
 397
 398     line [n + 1] = x;
 399     line [n + 2] = winding;
 400     line[0]++;
 401 }
 402
 403 void EdgeTable::translate (float dx, const int dy) noexcept
 404 {
 405     bounds.translate ((int) std::floor (dx), dy);
 406
 407     int* lineStart = table;
 408     const int intDx = (int) (dx * 256.0f);
 409
 410     for (int i = bounds.getHeight(); --i >= 0;)
 411     {
 412         int* line = lineStart;
 413         lineStart += lineStrideElements;
 414         int num = *line++;
 415
 416         while (--num >= 0)
 417         {
 418             *line += intDx;
 419             line += 2;
 420         }
 421     }
 422 }
 423
 424 void EdgeTable::intersectWithEdgeTableLine (const int y, const int* otherLine)
 425 {
 426     jassert (y >= 0 && y < bounds.getHeight());
 427
 428     int* dest = table + lineStrideElements * y;
 429     if (dest[0] == 0)
 430         return;
 431
 432     int otherNumPoints = *otherLine;
 433     if (otherNumPoints == 0)
 434     {
 435         *dest = 0;
 436         return;
 437     }
 438
 439     const int right = bounds.getRight() << 8;
 440
 441     // optimise for the common case where our line lies entirely within a
 442     // single pair of points, as happens when clipping to a simple rect.
 443     if (otherNumPoints == 2 && otherLine[2] >= 255)
 444     {
 445         clipEdgeTableLineToRange (dest, otherLine[1], jmin (right, otherLine[3]));
 446         return;
 447     }
 448
 449     ++otherLine;
 450     const size_t lineSizeBytes = (dest[0] * 2 + 1) * sizeof (int);
 451     int* temp = static_cast<int*> (alloca (lineSizeBytes));
 452     memcpy (temp, dest, lineSizeBytes);
 453
 454     const int* src1 = temp;
 455     int srcNum1 = *src1++;
 456     int x1 = *src1++;
 457
 458     const int* src2 = otherLine;
 459     int srcNum2 = otherNumPoints;
 460     int x2 = *src2++;
 461
 462     int destIndex = 0, destTotal = 0;
 463     int level1 = 0, level2 = 0;
 464     int lastX = std::numeric_limits<int>::min(), lastLevel = 0;
 465
 466     while (srcNum1 > 0 && srcNum2 > 0)
 467     {
 468         int nextX;
 469
 470         if (x1 < x2)
 471         {
 472             nextX = x1;
 473             level1 = *src1++;
 474             x1 = *src1++;
 475             --srcNum1;
 476         }
 477         else if (x1 == x2)
 478         {
 479             nextX = x1;
 480             level1 = *src1++;
 481             level2 = *src2++;
 482             x1 = *src1++;
 483             x2 = *src2++;
 484             --srcNum1;
 485             --srcNum2;
 486         }
 487         else
 488         {
 489             nextX = x2;
 490             level2 = *src2++;
 491             x2 = *src2++;
 492             --srcNum2;
 493         }
 494
 495         if (nextX > lastX)
 496         {
 497             if (nextX >= right)
 498                 break;
 499
 500             lastX = nextX;
 501
 502             const int nextLevel = (level1 * (level2 + 1)) >> 8;
 503             jassert (isPositiveAndBelow (nextLevel, (int) 256));
 504
 505             if (nextLevel != lastLevel)
 506             {
 507                 if (destTotal >= maxEdgesPerLine)
 508                 {
 509                     dest[0] = destTotal;
 510                     remapTableForNumEdges (maxEdgesPerLine + juce_edgeTableDefaultEdgesPerLine);
 511                     dest = table + lineStrideElements * y;
 512                 }
 513
 514                 ++destTotal;
 515                 lastLevel = nextLevel;
 516                 dest[++destIndex] = nextX;
 517                 dest[++destIndex] = nextLevel;
 518             }
 519         }
 520     }
 521
 522     if (lastLevel > 0)
 523     {
 524         if (destTotal >= maxEdgesPerLine)
 525         {
 526             dest[0] = destTotal;
 527             remapTableForNumEdges (maxEdgesPerLine + juce_edgeTableDefaultEdgesPerLine);
 528             dest = table + lineStrideElements * y;
 529         }
 530
 531         ++destTotal;
 532         dest[++destIndex] = right;
 533         dest[++destIndex] = 0;
 534     }
 535
 536     dest[0] = destTotal;
 537
 538 #if JUCE_DEBUG
 539     int last = std::numeric_limits<int>::min();
 540     for (int i = 0; i < dest[0]; ++i)
 541     {
 542         jassert (dest[i * 2 + 1] > last);
 543         last = dest[i * 2 + 1];
 544     }
 545
 546     jassert (dest [dest[0] * 2] == 0);
 547 #endif
 548 }
 549
 550 void EdgeTable::clipEdgeTableLineToRange (int* dest, const int x1, const int x2) noexcept
 551 {
 552     int* lastItem = dest + (dest[0] * 2 - 1);
 553
 554     if (x2 < lastItem[0])
 555     {
 556         if (x2 <= dest[1])
 557         {
 558             dest[0] = 0;
 559             return;
 560         }
 561
 562         while (x2 < lastItem[-2])
 563         {
 564             --(dest[0]);
 565             lastItem -= 2;
 566         }
 567
 568         lastItem[0] = x2;
 569         lastItem[1] = 0;
 570     }
 571
 572     if (x1 > dest[1])
 573     {
 574         while (lastItem[0] > x1)
 575             lastItem -= 2;
 576
 577         const int itemsRemoved = (int) (lastItem - (dest + 1)) / 2;
 578
 579         if (itemsRemoved > 0)
 580         {
 581             dest[0] -= itemsRemoved;
 582             memmove (dest + 1, lastItem, dest[0] * (sizeof (int) * 2));
 583         }
 584
 585         dest[1] = x1;
 586     }
 587 }
 588
 589
 590 //==============================================================================
 591 void EdgeTable::clipToRectangle (const Rectangle<int>& r)
 592 {
 593     const Rectangle<int> clipped (r.getIntersection (bounds));
 594
 595     if (clipped.isEmpty())
 596     {
 597         needToCheckEmptinesss = false;
 598         bounds.setHeight (0);
 599     }
 600     else
 601     {
 602         const int top = clipped.getY() - bounds.getY();
 603         const int bottom = clipped.getBottom() - bounds.getY();
 604
 605         if (bottom < bounds.getHeight())
 606             bounds.setHeight (bottom);
 607
 608         if (clipped.getRight() < bounds.getRight())
 609             bounds.setRight (clipped.getRight());
 610
 611         for (int i = top; --i >= 0;)
 612             table [lineStrideElements * i] = 0;
 613
 614         if (clipped.getX() > bounds.getX())
 615         {
 616             const int x1 = clipped.getX() << 8;
 617             const int x2 = jmin (bounds.getRight(), clipped.getRight()) << 8;
 618             int* line = table + lineStrideElements * top;
 619
 620             for (int i = bottom - top; --i >= 0;)
 621             {
 622                 if (line[0] != 0)
 623                     clipEdgeTableLineToRange (line, x1, x2);
 624
 625                 line += lineStrideElements;
 626             }
 627         }
 628
 629         needToCheckEmptinesss = true;
 630     }
 631 }
 632
 633 void EdgeTable::excludeRectangle (const Rectangle<int>& r)
 634 {
 635     const Rectangle<int> clipped (r.getIntersection (bounds));
 636
 637     if (! clipped.isEmpty())
 638     {
 639         const int top = clipped.getY() - bounds.getY();
 640         const int bottom = clipped.getBottom() - bounds.getY();
 641
 642         //XXX optimise here by shortening the table if it fills top or bottom
 643
 644         const int rectLine[] = { 4, std::numeric_limits<int>::min(), 255,
 645                                  clipped.getX() << 8, 0,
 646                                  clipped.getRight() << 8, 255,
 647                                  std::numeric_limits<int>::max(), 0 };
 648
 649         for (int i = top; i < bottom; ++i)
 650             intersectWithEdgeTableLine (i, rectLine);
 651
 652         needToCheckEmptinesss = true;
 653     }
 654 }
 655
 656 void EdgeTable::clipToEdgeTable (const EdgeTable& other)
 657 {
 658     const Rectangle<int> clipped (other.bounds.getIntersection (bounds));
 659
 660     if (clipped.isEmpty())
 661     {
 662         needToCheckEmptinesss = false;
 663         bounds.setHeight (0);
 664     }
 665     else
 666     {
 667         const int top = clipped.getY() - bounds.getY();
 668         const int bottom = clipped.getBottom() - bounds.getY();
 669
 670         if (bottom < bounds.getHeight())
 671             bounds.setHeight (bottom);
 672
 673         if (clipped.getRight() < bounds.getRight())
 674             bounds.setRight (clipped.getRight());
 675
 676         int i = 0;
 677         for (i = top; --i >= 0;)
 678             table [lineStrideElements * i] = 0;
 679
 680         const int* otherLine = other.table + other.lineStrideElements * (clipped.getY() - other.bounds.getY());
 681
 682         for (i = top; i < bottom; ++i)
 683         {
 684             intersectWithEdgeTableLine (i, otherLine);
 685             otherLine += other.lineStrideElements;
 686         }
 687
 688         needToCheckEmptinesss = true;
 689     }
 690 }
 691
 692 void EdgeTable::clipLineToMask (int x, int y, const uint8* mask, int maskStride, int numPixels)
 693 {
 694     y -= bounds.getY();
 695
 696     if (y < 0 || y >= bounds.getHeight())
 697         return;
 698
 699     needToCheckEmptinesss = true;
 700
 701     if (numPixels <= 0)
 702     {
 703         table [lineStrideElements * y] = 0;
 704         return;
 705     }
 706
 707     int* tempLine = static_cast<int*> (alloca ((numPixels * 2 + 4) * sizeof (int)));
 708     int destIndex = 0, lastLevel = 0;
 709
 710     while (--numPixels >= 0)
 711     {
 712         const int alpha = *mask;
 713         mask += maskStride;
 714
 715         if (alpha != lastLevel)
 716         {
 717             tempLine[++destIndex] = (x << 8);
 718             tempLine[++destIndex] = alpha;
 719             lastLevel = alpha;
 720         }
 721
 722         ++x;
 723     }
 724
 725     if (lastLevel > 0)
 726     {
 727         tempLine[++destIndex] = (x << 8);
 728         tempLine[++destIndex] = 0;
 729     }
 730
 731     tempLine[0] = destIndex >> 1;
 732
 733     intersectWithEdgeTableLine (y, tempLine);
 734 }
 735
 736 bool EdgeTable::isEmpty() noexcept
 737 {
 738     if (needToCheckEmptinesss)
 739     {
 740         needToCheckEmptinesss = false;
 741         int* t = table;
 742
 743         for (int i = bounds.getHeight(); --i >= 0;)
 744         {
 745             if (t[0] > 1)
 746                 return false;
 747
 748             t += lineStrideElements;
 749         }
 750
 751         bounds.setHeight (0);
 752     }
 753
 754     return bounds.getHeight() == 0;
 755 }
 756
 757 END_JUCE_NAMESPACE