Source/WebCore/platform/graphics/Region.cpp

   1 /*
   2  * Copyright (C) 2010, 2011 Apple Inc. All rights reserved.
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions
   6  * are met:
   7  * 1. Redistributions of source code must retain the above copyright
   8  *    notice, this list of conditions and the following disclaimer.
   9  * 2. Redistributions in binary form must reproduce the above copyright
  10  *    notice, this list of conditions and the following disclaimer in the
  11  *    documentation and/or other materials provided with the distribution.
  12  *
  13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
  14  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
  15  * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  16  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
  17  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  18  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  19  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  20  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  21  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  22  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
  23  * THE POSSIBILITY OF SUCH DAMAGE.
  24  */
  25
  26 #include "config.h"
  27 #include "Region.h"
  28
  29 #include <stdio.h>
  30
  31 // A region class based on the paper "Scanline Coherent Shape Algebra"
  32 // by Jonathan E. Steinhart from the book "Graphics Gems II".
  33 //
  34 // This implementation uses two vectors instead of linked list, and
  35 // also compresses regions when possible.
  36
  37 namespace WebCore {
  38
  39 Region::Region()
  40 {
  41 }
  42
  43 Region::Region(const IntRect& rect)
  44     : m_bounds(rect)
  45     , m_shape(rect)
  46 {
  47 }
  48
  49 Vector<IntRect> Region::rects() const
  50 {
  51     Vector<IntRect> rects;
  52
  53     for (Shape::SpanIterator span = m_shape.spans_begin(), end = m_shape.spans_end(); span != end && span + 1 != end; ++span) {
  54         int y = span->y;
  55         int height = (span + 1)->y - y;
  56
  57         for (Shape::SegmentIterator segment = m_shape.segments_begin(span), end = m_shape.segments_end(span); segment != end && segment + 1 != end; segment += 2) {
  58             int x = *segment;
  59             int width = *(segment + 1) - x;
  60
  61             rects.append(IntRect(x, y, width, height));
  62         }
  63     }
  64
  65     return rects;
  66 }
  67
  68 bool Region::contains(const Region& region) const
  69 {
  70     if (!m_bounds.contains(region.m_bounds))
  71         return false;
  72
  73     return Shape::compareShapes<Shape::CompareContainsOperation>(m_shape, region.m_shape);
  74 }
  75
  76 bool Region::contains(const IntPoint& point) const
  77 {
  78     if (!m_bounds.contains(point))
  79         return false;
  80
  81     for (Shape::SpanIterator span = m_shape.spans_begin(), end = m_shape.spans_end(); span != end && span + 1 != end; ++span) {
  82         int y = span->y;
  83         int maxY = (span + 1)->y;
  84
  85         if (y > point.y())
  86             break;
  87         if (maxY <= point.y())
  88             continue;
  89
  90         for (Shape::SegmentIterator segment = m_shape.segments_begin(span), end = m_shape.segments_end(span); segment != end && segment + 1 != end; segment += 2) {
  91             int x = *segment;
  92             int maxX = *(segment + 1);
  93
  94             if (x > point.x())
  95                 break;
  96             if (maxX > point.x())
  97                 return true;
  98         }
  99     }
 100
 101     return false;
 102 }
 103
 104 bool Region::intersects(const Region& region) const
 105 {
 106     if (!m_bounds.intersects(region.m_bounds))
 107         return false;
 108
 109     return Shape::compareShapes<Shape::CompareIntersectsOperation>(m_shape, region.m_shape);
 110 }
 111
 112 unsigned Region::totalArea() const
 113 {
 114     Vector<IntRect> rects = this->rects();
 115     size_t size = rects.size();
 116     unsigned totalArea = 0;
 117
 118     for (size_t i = 0; i < size; ++i) {
 119         IntRect rect = rects[i];
 120         totalArea += (rect.width() * rect.height());
 121     }
 122
 123     return totalArea;
 124 }
 125
 126 template<typename CompareOperation>
 127 bool Region::Shape::compareShapes(const Shape& aShape, const Shape& bShape)
 128 {
 129     bool result = CompareOperation::defaultResult;
 130
 131     Shape::SpanIterator aSpan = aShape.spans_begin();
 132     Shape::SpanIterator aSpanEnd = aShape.spans_end();
 133     Shape::SpanIterator bSpan = bShape.spans_begin();
 134     Shape::SpanIterator bSpanEnd = bShape.spans_end();
 135
 136     bool aHadSegmentInPreviousSpan = false;
 137     bool bHadSegmentInPreviousSpan = false;
 138     while (aSpan != aSpanEnd && aSpan + 1 != aSpanEnd && bSpan != bSpanEnd && bSpan + 1 != bSpanEnd) {
 139         int aY = aSpan->y;
 140         int aMaxY = (aSpan + 1)->y;
 141         int bY = bSpan->y;
 142         int bMaxY = (bSpan + 1)->y;
 143
 144         Shape::SegmentIterator aSegment = aShape.segments_begin(aSpan);
 145         Shape::SegmentIterator aSegmentEnd = aShape.segments_end(aSpan);
 146         Shape::SegmentIterator bSegment = bShape.segments_begin(bSpan);
 147         Shape::SegmentIterator bSegmentEnd = bShape.segments_end(bSpan);
 148
 149         // Look for a non-overlapping part of the spans. If B had a segment in its previous span, then we already tested A against B within that span.
 150         bool aHasSegmentInSpan = aSegment != aSegmentEnd;
 151         bool bHasSegmentInSpan = bSegment != bSegmentEnd;
 152         if (aY < bY && !bHadSegmentInPreviousSpan && aHasSegmentInSpan && CompareOperation::aOutsideB(result))
 153             return result;
 154         if (bY < aY && !aHadSegmentInPreviousSpan && bHasSegmentInSpan && CompareOperation::bOutsideA(result))
 155             return result;
 156
 157         aHadSegmentInPreviousSpan = aHasSegmentInSpan;
 158         bHadSegmentInPreviousSpan = bHasSegmentInSpan;
 159
 160         bool spansOverlap = bMaxY > aY && bY < aMaxY;
 161         if (spansOverlap) {
 162             while (aSegment != aSegmentEnd && bSegment != bSegmentEnd) {
 163                 int aX = *aSegment;
 164                 int aMaxX = *(aSegment + 1);
 165                 int bX = *bSegment;
 166                 int bMaxX = *(bSegment + 1);
 167
 168                 bool segmentsOverlap = bMaxX > aX && bX < aMaxX;
 169                 if (segmentsOverlap && CompareOperation::aOverlapsB(result))
 170                     return result;
 171                 if (aX < bX && CompareOperation::aOutsideB(result))
 172                     return result;
 173                 if (bX < aX && CompareOperation::bOutsideA(result))
 174                     return result;
 175
 176                 if (aMaxX < bMaxX)
 177                     aSegment += 2;
 178                 else if (bMaxX < aMaxX)
 179                     bSegment += 2;
 180                 else {
 181                     aSegment += 2;
 182                     bSegment += 2;
 183                 }
 184             }
 185
 186             if (aSegment != aSegmentEnd && CompareOperation::aOutsideB(result))
 187                 return result;
 188             if (bSegment != bSegmentEnd && CompareOperation::bOutsideA(result))
 189                 return result;
 190         }
 191
 192         if (aMaxY < bMaxY)
 193             aSpan += 1;
 194         else if (bMaxY < aMaxY)
 195             bSpan += 1;
 196         else {
 197             aSpan += 1;
 198             bSpan += 1;
 199         }
 200     }
 201
 202     if (aSpan != aSpanEnd && aSpan + 1 != aSpanEnd && CompareOperation::aOutsideB(result))
 203         return result;
 204     if (bSpan != bSpanEnd && bSpan + 1 != bSpanEnd && CompareOperation::bOutsideA(result))
 205         return result;
 206
 207     return result;
 208 }
 209
 210 struct Region::Shape::CompareContainsOperation {
 211     const static bool defaultResult = true;
 212     inline static bool aOutsideB(bool& /* result */) { return false; }
 213     inline static bool bOutsideA(bool& result) { result = false; return true; }
 214     inline static bool aOverlapsB(bool& /* result */) { return false; }
 215 };
 216
 217 struct Region::Shape::CompareIntersectsOperation {
 218     const static bool defaultResult = false;
 219     inline static bool aOutsideB(bool& /* result */) { return false; }
 220     inline static bool bOutsideA(bool& /* result */) { return false; }
 221     inline static bool aOverlapsB(bool& result) { result = true; return true; }
 222 };
 223
 224 Region::Shape::Shape()
 225 {
 226 }
 227
 228 Region::Shape::Shape(const IntRect& rect)
 229 {
 230     appendSpan(rect.y());
 231     appendSegment(rect.x());
 232     appendSegment(rect.maxX());
 233     appendSpan(rect.maxY());
 234 }
 235
 236 void Region::Shape::appendSpan(int y)
 237 {
 238     m_spans.append(Span(y, m_segments.size()));
 239 }
 240
 241 bool Region::Shape::canCoalesce(SegmentIterator begin, SegmentIterator end)
 242 {
 243     if (m_spans.isEmpty())
 244         return false;
 245
 246     SegmentIterator lastSpanBegin = m_segments.data() + m_spans.last().segmentIndex;
 247     SegmentIterator lastSpanEnd = m_segments.data() + m_segments.size();
 248
 249     // Check if both spans have an equal number of segments.
 250     if (lastSpanEnd - lastSpanBegin != end - begin)
 251         return false;
 252
 253     // Check if both spans are equal.
 254     if (!std::equal(begin, end, lastSpanBegin))
 255         return false;
 256
 257     // Since the segments are equal the second segment can just be ignored.
 258     return true;
 259 }
 260
 261 void Region::Shape::appendSpan(int y, SegmentIterator begin, SegmentIterator end)
 262 {
 263     if (canCoalesce(begin, end))
 264         return;
 265
 266     appendSpan(y);
 267     m_segments.appendRange(begin, end);
 268 }
 269
 270 void Region::Shape::appendSpans(const Shape& shape, SpanIterator begin, SpanIterator end)
 271 {
 272     for (SpanIterator it = begin; it != end; ++it)
 273         appendSpan(it->y, shape.segments_begin(it), shape.segments_end(it));
 274 }
 275
 276 void Region::Shape::appendSegment(int x)
 277 {
 278     m_segments.append(x);
 279 }
 280
 281 Region::Shape::SpanIterator Region::Shape::spans_begin() const
 282 {
 283     return m_spans.data();
 284 }
 285
 286 Region::Shape::SpanIterator Region::Shape::spans_end() const
 287 {
 288     return m_spans.data() + m_spans.size();
 289 }
 290
 291 Region::Shape::SegmentIterator Region::Shape::segments_begin(SpanIterator it) const
 292 {
 293     ASSERT(it >= m_spans.data());
 294     ASSERT(it < m_spans.data() + m_spans.size());
 295
 296     // Check if this span has any segments.
 297     if (it->segmentIndex == m_segments.size())
 298         return 0;
 299
 300     return &m_segments[it->segmentIndex];
 301 }
 302
 303 Region::Shape::SegmentIterator Region::Shape::segments_end(SpanIterator it) const
 304 {
 305     ASSERT(it >= m_spans.data());
 306     ASSERT(it < m_spans.data() + m_spans.size());
 307
 308     // Check if this span has any segments.
 309     if (it->segmentIndex == m_segments.size())
 310         return 0;
 311
 312     ASSERT(it + 1 < m_spans.data() + m_spans.size());
 313     size_t segmentIndex = (it + 1)->segmentIndex;
 314
 315     ASSERT(segmentIndex <= m_segments.size());
 316     return m_segments.data() + segmentIndex;
 317 }
 318
 319 #ifndef NDEBUG
 320 void Region::Shape::dump() const
 321 {
 322     for (Shape::SpanIterator span = spans_begin(), end = spans_end(); span != end; ++span) {
 323         printf("%6d: (", span->y);
 324
 325         for (Shape::SegmentIterator segment = segments_begin(span), end = segments_end(span); segment != end; ++segment)
 326             printf("%d ", *segment);
 327         printf(")\n");
 328     }
 329
 330     printf("\n");
 331 }
 332 #endif
 333
 334 IntRect Region::Shape::bounds() const
 335 {
 336     if (isEmpty())
 337         return IntRect();
 338
 339     SpanIterator span = spans_begin();
 340     int minY = span->y;
 341
 342     SpanIterator lastSpan = spans_end() - 1;
 343     int maxY = lastSpan->y;
 344
 345     int minX = std::numeric_limits<int>::max();
 346     int maxX = std::numeric_limits<int>::min();
 347
 348     while (span != lastSpan) {
 349         SegmentIterator firstSegment = segments_begin(span);
 350         SegmentIterator lastSegment = segments_end(span) - 1;
 351
 352         if (firstSegment && lastSegment) {
 353             ASSERT(firstSegment != lastSegment);
 354
 355             if (*firstSegment < minX)
 356                 minX = *firstSegment;
 357
 358             if (*lastSegment > maxX)
 359                 maxX = *lastSegment;
 360         }
 361
 362         ++span;
 363     }
 364
 365     ASSERT(minX <= maxX);
 366     ASSERT(minY <= maxY);
 367
 368     return IntRect(minX, minY, maxX - minX, maxY - minY);
 369 }
 370
 371 void Region::Shape::translate(const IntSize& offset)
 372 {
 373     for (size_t i = 0; i < m_segments.size(); ++i)
 374         m_segments[i] += offset.width();
 375     for (size_t i = 0; i < m_spans.size(); ++i)
 376         m_spans[i].y += offset.height();
 377 }
 378
 379 void Region::Shape::swap(Shape& other)
 380 {
 381     m_segments.swap(other.m_segments);
 382     m_spans.swap(other.m_spans);
 383 }
 384
 385 enum {
 386     Shape1,
 387     Shape2,
 388 };
 389
 390 template<typename Operation>
 391 Region::Shape Region::Shape::shapeOperation(const Shape& shape1, const Shape& shape2)
 392 {
 393     COMPILE_ASSERT(!(!Operation::shouldAddRemainingSegmentsFromSpan1 && Operation::shouldAddRemainingSegmentsFromSpan2), invalid_segment_combination);
 394     COMPILE_ASSERT(!(!Operation::shouldAddRemainingSpansFromShape1 && Operation::shouldAddRemainingSpansFromShape2), invalid_span_combination);
 395
 396     Shape result;
 397     if (Operation::trySimpleOperation(shape1, shape2, result))
 398         return result;
 399
 400     SpanIterator spans1 = shape1.spans_begin();
 401     SpanIterator spans1End = shape1.spans_end();
 402
 403     SpanIterator spans2 = shape2.spans_begin();
 404     SpanIterator spans2End = shape2.spans_end();
 405
 406     SegmentIterator segments1 = 0;
 407     SegmentIterator segments1End = 0;
 408
 409     SegmentIterator segments2 = 0;
 410     SegmentIterator segments2End = 0;
 411
 412     // Iterate over all spans.
 413     while (spans1 != spans1End && spans2 != spans2End) {
 414         int y = 0;
 415         int test = spans1->y - spans2->y;
 416
 417         if (test <= 0) {
 418             y = spans1->y;
 419
 420             segments1 = shape1.segments_begin(spans1);
 421             segments1End = shape1.segments_end(spans1);
 422             ++spans1;
 423         }
 424         if (test >= 0) {
 425             y = spans2->y;
 426
 427             segments2 = shape2.segments_begin(spans2);
 428             segments2End = shape2.segments_end(spans2);
 429             ++spans2;
 430         }
 431
 432         int flag = 0;
 433         int oldFlag = 0;
 434
 435         SegmentIterator s1 = segments1;
 436         SegmentIterator s2 = segments2;
 437
 438         Vector<int, 32> segments;
 439
 440         // Now iterate over the segments in each span and construct a new vector of segments.
 441         while (s1 != segments1End && s2 != segments2End) {
 442             int test = *s1 - *s2;
 443             int x;
 444
 445             if (test <= 0) {
 446                 x = *s1;
 447                 flag = flag ^ 1;
 448                 ++s1;
 449             }
 450             if (test >= 0) {
 451                 x = *s2;
 452                 flag = flag ^ 2;
 453                 ++s2;
 454             }
 455
 456             if (flag == Operation::opCode || oldFlag == Operation::opCode)
 457                 segments.append(x);
 458
 459             oldFlag = flag;
 460         }
 461
 462         // Add any remaining segments.
 463         if (Operation::shouldAddRemainingSegmentsFromSpan1 && s1 != segments1End)
 464             segments.appendRange(s1, segments1End);
 465         else if (Operation::shouldAddRemainingSegmentsFromSpan2 && s2 != segments2End)
 466             segments.appendRange(s2, segments2End);
 467
 468         // Add the span.
 469         if (!segments.isEmpty() || !result.isEmpty())
 470             result.appendSpan(y, segments.data(), segments.data() + segments.size());
 471     }
 472
 473     // Add any remaining spans.
 474     if (Operation::shouldAddRemainingSpansFromShape1 && spans1 != spans1End)
 475         result.appendSpans(shape1, spans1, spans1End);
 476     else if (Operation::shouldAddRemainingSpansFromShape2 && spans2 != spans2End)
 477         result.appendSpans(shape2, spans2, spans2End);
 478
 479     return result;
 480 }
 481
 482 struct Region::Shape::UnionOperation {
 483     static bool trySimpleOperation(const Shape& shape1, const Shape& shape2, Shape& result)
 484     {
 485         if (shape1.isEmpty()) {
 486             result = shape2;
 487             return true;
 488         }
 489
 490         return false;
 491     }
 492
 493     static const int opCode = 0;
 494
 495     static const bool shouldAddRemainingSegmentsFromSpan1 = true;
 496     static const bool shouldAddRemainingSegmentsFromSpan2 = true;
 497     static const bool shouldAddRemainingSpansFromShape1 = true;
 498     static const bool shouldAddRemainingSpansFromShape2 = true;
 499 };
 500
 501 Region::Shape Region::Shape::unionShapes(const Shape& shape1, const Shape& shape2)
 502 {
 503     return shapeOperation<UnionOperation>(shape1, shape2);
 504 }
 505
 506 struct Region::Shape::IntersectOperation {
 507     static bool trySimpleOperation(const Shape&, const Shape&, Shape&)
 508     {
 509         return false;
 510     }
 511
 512     static const int opCode = 3;
 513
 514     static const bool shouldAddRemainingSegmentsFromSpan1 = false;
 515     static const bool shouldAddRemainingSegmentsFromSpan2 = false;
 516     static const bool shouldAddRemainingSpansFromShape1 = false;
 517     static const bool shouldAddRemainingSpansFromShape2 = false;
 518 };
 519
 520 Region::Shape Region::Shape::intersectShapes(const Shape& shape1, const Shape& shape2)
 521 {
 522     return shapeOperation<IntersectOperation>(shape1, shape2);
 523 }
 524
 525 struct Region::Shape::SubtractOperation {
 526     static bool trySimpleOperation(const Shape&, const Shape&, Region::Shape&)
 527     {
 528         return false;
 529     }
 530
 531     static const int opCode = 1;
 532
 533     static const bool shouldAddRemainingSegmentsFromSpan1 = true;
 534     static const bool shouldAddRemainingSegmentsFromSpan2 = false;
 535     static const bool shouldAddRemainingSpansFromShape1 = true;
 536     static const bool shouldAddRemainingSpansFromShape2 = false;
 537 };
 538
 539 Region::Shape Region::Shape::subtractShapes(const Shape& shape1, const Shape& shape2)
 540 {
 541     return shapeOperation<SubtractOperation>(shape1, shape2);
 542 }
 543
 544 #ifndef NDEBUG
 545 void Region::dump() const
 546 {
 547     printf("Bounds: (%d, %d, %d, %d)\n",
 548            m_bounds.x(), m_bounds.y(), m_bounds.width(), m_bounds.height());
 549     m_shape.dump();
 550 }
 551 #endif
 552
 553 void Region::intersect(const Region& region)
 554 {
 555     if (m_bounds.isEmpty())
 556         return;
 557     if (!m_bounds.intersects(region.m_bounds)) {
 558         m_shape = Shape();
 559         m_bounds = IntRect();
 560         return;
 561     }
 562
 563     Shape intersectedShape = Shape::intersectShapes(m_shape, region.m_shape);
 564
 565     m_shape.swap(intersectedShape);
 566     m_bounds = m_shape.bounds();
 567 }
 568
 569 void Region::unite(const Region& region)
 570 {
 571     if (region.isEmpty())
 572         return;
 573     if (isRect() && m_bounds.contains(region.m_bounds))
 574         return;
 575     if (region.isRect() && region.m_bounds.contains(m_bounds)) {
 576         m_shape = region.m_shape;
 577         m_bounds = region.m_bounds;
 578         return;
 579     }
 580     // FIXME: We may want another way to construct a Region without doing this test when we expect it to be false.
 581     if (!isRect() && contains(region))
 582         return;
 583
 584     Shape unitedShape = Shape::unionShapes(m_shape, region.m_shape);
 585
 586     m_shape.swap(unitedShape);
 587     m_bounds.unite(region.m_bounds);
 588 }
 589
 590 void Region::subtract(const Region& region)
 591 {
 592     if (m_bounds.isEmpty())
 593         return;
 594     if (region.isEmpty())
 595         return;
 596     if (!m_bounds.intersects(region.m_bounds))
 597         return;
 598
 599     Shape subtractedShape = Shape::subtractShapes(m_shape, region.m_shape);
 600
 601     m_shape.swap(subtractedShape);
 602     m_bounds = m_shape.bounds();
 603 }
 604
 605 void Region::translate(const IntSize& offset)
 606 {
 607     m_bounds.move(offset);
 608     m_shape.translate(offset);
 609 }
 610
 611 } // namespace WebCore