src/third_party/WebKit/Source/platform/geometry/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 "platform/geometry/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 blink {
  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.spansBegin(), end = m_shape.spansEnd(); 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.segmentsBegin(span), end = m_shape.segmentsEnd(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.spansBegin(), end = m_shape.spansEnd(); 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.segmentsBegin(span), end = m_shape.segmentsEnd(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.spansBegin();
 132     Shape::SpanIterator aSpanEnd = aShape.spansEnd();
 133     Shape::SpanIterator bSpan = bShape.spansBegin();
 134     Shape::SpanIterator bSpanEnd = bShape.spansEnd();
 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.segmentsBegin(aSpan);
 145         Shape::SegmentIterator aSegmentEnd = aShape.segmentsEnd(aSpan);
 146         Shape::SegmentIterator bSegment = bShape.segmentsBegin(bSpan);
 147         Shape::SegmentIterator bSegmentEnd = bShape.segmentsEnd(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 void Region::Shape::trimCapacities()
 211 {
 212     m_segments.shrinkToReasonableCapacity();
 213     m_spans.shrinkToReasonableCapacity();
 214 }
 215
 216 struct Region::Shape::CompareContainsOperation {
 217     const static bool defaultResult = true;
 218     inline static bool aOutsideB(bool& /* result */) { return false; }
 219     inline static bool bOutsideA(bool& result) { result = false; return true; }
 220     inline static bool aOverlapsB(bool& /* result */) { return false; }
 221 };
 222
 223 struct Region::Shape::CompareIntersectsOperation {
 224     const static bool defaultResult = false;
 225     inline static bool aOutsideB(bool& /* result */) { return false; }
 226     inline static bool bOutsideA(bool& /* result */) { return false; }
 227     inline static bool aOverlapsB(bool& result) { result = true; return true; }
 228 };
 229
 230 Region::Shape::Shape()
 231 {
 232 }
 233
 234 Region::Shape::Shape(const IntRect& rect)
 235 {
 236     appendSpan(rect.y());
 237     appendSegment(rect.x());
 238     appendSegment(rect.maxX());
 239     appendSpan(rect.maxY());
 240 }
 241
 242 Region::Shape::Shape(size_t segmentsCapacity, size_t spansCapacity)
 243 {
 244     m_segments.reserveCapacity(segmentsCapacity);
 245     m_spans.reserveCapacity(spansCapacity);
 246 }
 247
 248 void Region::Shape::appendSpan(int y)
 249 {
 250     m_spans.append(Span(y, m_segments.size()));
 251 }
 252
 253 bool Region::Shape::canCoalesce(SegmentIterator begin, SegmentIterator end)
 254 {
 255     if (m_spans.isEmpty())
 256         return false;
 257
 258     SegmentIterator lastSpanBegin = m_segments.data() + m_spans.last().segmentIndex;
 259     SegmentIterator lastSpanEnd = m_segments.data() + m_segments.size();
 260
 261     // Check if both spans have an equal number of segments.
 262     if (lastSpanEnd - lastSpanBegin != end - begin)
 263         return false;
 264
 265     // Check if both spans are equal.
 266     if (!std::equal(begin, end, lastSpanBegin))
 267         return false;
 268
 269     // Since the segments are equal the second segment can just be ignored.
 270     return true;
 271 }
 272
 273 void Region::Shape::appendSpan(int y, SegmentIterator begin, SegmentIterator end)
 274 {
 275     if (canCoalesce(begin, end))
 276         return;
 277
 278     appendSpan(y);
 279     m_segments.appendRange(begin, end);
 280 }
 281
 282 void Region::Shape::appendSpans(const Shape& shape, SpanIterator begin, SpanIterator end)
 283 {
 284     for (SpanIterator it = begin; it != end; ++it)
 285         appendSpan(it->y, shape.segmentsBegin(it), shape.segmentsEnd(it));
 286 }
 287
 288 void Region::Shape::appendSegment(int x)
 289 {
 290     m_segments.append(x);
 291 }
 292
 293 Region::Shape::SpanIterator Region::Shape::spansBegin() const
 294 {
 295     return m_spans.data();
 296 }
 297
 298 Region::Shape::SpanIterator Region::Shape::spansEnd() const
 299 {
 300     return m_spans.data() + m_spans.size();
 301 }
 302
 303 Region::Shape::SegmentIterator Region::Shape::segmentsBegin(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     return &m_segments[it->segmentIndex];
 313 }
 314
 315 Region::Shape::SegmentIterator Region::Shape::segmentsEnd(SpanIterator it) const
 316 {
 317     ASSERT(it >= m_spans.data());
 318     ASSERT(it < m_spans.data() + m_spans.size());
 319
 320     // Check if this span has any segments.
 321     if (it->segmentIndex == m_segments.size())
 322         return 0;
 323
 324     ASSERT(it + 1 < m_spans.data() + m_spans.size());
 325     size_t segmentIndex = (it + 1)->segmentIndex;
 326
 327     ASSERT_WITH_SECURITY_IMPLICATION(segmentIndex <= m_segments.size());
 328     return m_segments.data() + segmentIndex;
 329 }
 330
 331 #ifndef NDEBUG
 332 void Region::Shape::dump() const
 333 {
 334     for (Shape::SpanIterator span = spansBegin(), end = spansEnd(); span != end; ++span) {
 335         printf("%6d: (", span->y);
 336
 337         for (Shape::SegmentIterator segment = segmentsBegin(span), end = segmentsEnd(span); segment != end; ++segment)
 338             printf("%d ", *segment);
 339         printf(")\n");
 340     }
 341
 342     printf("\n");
 343 }
 344 #endif
 345
 346 IntRect Region::Shape::bounds() const
 347 {
 348     if (isEmpty())
 349         return IntRect();
 350
 351     SpanIterator span = spansBegin();
 352     int minY = span->y;
 353
 354     SpanIterator lastSpan = spansEnd() - 1;
 355     int maxY = lastSpan->y;
 356
 357     int minX = std::numeric_limits<int>::max();
 358     int maxX = std::numeric_limits<int>::min();
 359
 360     while (span != lastSpan) {
 361         SegmentIterator firstSegment = segmentsBegin(span);
 362         SegmentIterator lastSegment = segmentsEnd(span) - 1;
 363
 364         if (firstSegment && lastSegment) {
 365             ASSERT(firstSegment != lastSegment);
 366
 367             if (*firstSegment < minX)
 368                 minX = *firstSegment;
 369
 370             if (*lastSegment > maxX)
 371                 maxX = *lastSegment;
 372         }
 373
 374         ++span;
 375     }
 376
 377     ASSERT(minX <= maxX);
 378     ASSERT(minY <= maxY);
 379
 380     return IntRect(minX, minY, maxX - minX, maxY - minY);
 381 }
 382
 383 void Region::Shape::translate(const IntSize& offset)
 384 {
 385     for (size_t i = 0; i < m_segments.size(); ++i)
 386         m_segments[i] += offset.width();
 387     for (size_t i = 0; i < m_spans.size(); ++i)
 388         m_spans[i].y += offset.height();
 389 }
 390
 391 void Region::Shape::swap(Shape& other)
 392 {
 393     m_segments.swap(other.m_segments);
 394     m_spans.swap(other.m_spans);
 395 }
 396
 397 enum {
 398     Shape1,
 399     Shape2,
 400 };
 401
 402 template<typename Operation>
 403 Region::Shape Region::Shape::shapeOperation(const Shape& shape1, const Shape& shape2)
 404 {
 405     COMPILE_ASSERT(!(!Operation::shouldAddRemainingSegmentsFromSpan1 && Operation::shouldAddRemainingSegmentsFromSpan2), invalid_segment_combination);
 406     COMPILE_ASSERT(!(!Operation::shouldAddRemainingSpansFromShape1 && Operation::shouldAddRemainingSpansFromShape2), invalid_span_combination);
 407
 408     size_t segmentsCapacity = shape1.segmentsSize() + shape2.segmentsSize();
 409     size_t spansCapacity = shape1.spansSize() + shape2.spansSize();
 410     Shape result(segmentsCapacity, spansCapacity);
 411     if (Operation::trySimpleOperation(shape1, shape2, result))
 412         return result;
 413
 414     SpanIterator spans1 = shape1.spansBegin();
 415     SpanIterator spans1End = shape1.spansEnd();
 416
 417     SpanIterator spans2 = shape2.spansBegin();
 418     SpanIterator spans2End = shape2.spansEnd();
 419
 420     SegmentIterator segments1 = 0;
 421     SegmentIterator segments1End = 0;
 422
 423     SegmentIterator segments2 = 0;
 424     SegmentIterator segments2End = 0;
 425
 426     Vector<int, 32> segments;
 427     segments.reserveCapacity(std::max(shape1.segmentsSize(), shape2.segmentsSize()));
 428
 429     // Iterate over all spans.
 430     while (spans1 != spans1End && spans2 != spans2End) {
 431         int y = 0;
 432         int test = spans1->y - spans2->y;
 433
 434         if (test <= 0) {
 435             y = spans1->y;
 436
 437             segments1 = shape1.segmentsBegin(spans1);
 438             segments1End = shape1.segmentsEnd(spans1);
 439             ++spans1;
 440         }
 441         if (test >= 0) {
 442             y = spans2->y;
 443
 444             segments2 = shape2.segmentsBegin(spans2);
 445             segments2End = shape2.segmentsEnd(spans2);
 446             ++spans2;
 447         }
 448
 449         int flag = 0;
 450         int oldFlag = 0;
 451
 452         SegmentIterator s1 = segments1;
 453         SegmentIterator s2 = segments2;
 454
 455         // Clear vector without dropping capacity.
 456         segments.resize(0);
 457         ASSERT(segments.capacity());
 458
 459         // Now iterate over the segments in each span and construct a new vector of segments.
 460         while (s1 != segments1End && s2 != segments2End) {
 461             int test = *s1 - *s2;
 462             int x;
 463
 464             if (test <= 0) {
 465                 x = *s1;
 466                 flag = flag ^ 1;
 467                 ++s1;
 468             }
 469             if (test >= 0) {
 470                 x = *s2;
 471                 flag = flag ^ 2;
 472                 ++s2;
 473             }
 474
 475             if (flag == Operation::opCode || oldFlag == Operation::opCode)
 476                 segments.append(x);
 477
 478             oldFlag = flag;
 479         }
 480
 481         // Add any remaining segments.
 482         if (Operation::shouldAddRemainingSegmentsFromSpan1 && s1 != segments1End)
 483             segments.appendRange(s1, segments1End);
 484         else if (Operation::shouldAddRemainingSegmentsFromSpan2 && s2 != segments2End)
 485             segments.appendRange(s2, segments2End);
 486
 487         // Add the span.
 488         if (!segments.isEmpty() || !result.isEmpty())
 489             result.appendSpan(y, segments.data(), segments.data() + segments.size());
 490     }
 491
 492     // Add any remaining spans.
 493     if (Operation::shouldAddRemainingSpansFromShape1 && spans1 != spans1End)
 494         result.appendSpans(shape1, spans1, spans1End);
 495     else if (Operation::shouldAddRemainingSpansFromShape2 && spans2 != spans2End)
 496         result.appendSpans(shape2, spans2, spans2End);
 497
 498     result.trimCapacities();
 499
 500     return result;
 501 }
 502
 503 struct Region::Shape::UnionOperation {
 504     static bool trySimpleOperation(const Shape& shape1, const Shape& shape2, Shape& result)
 505     {
 506         if (shape1.isEmpty()) {
 507             result = shape2;
 508             return true;
 509         }
 510
 511         return false;
 512     }
 513
 514     static const int opCode = 0;
 515
 516     static const bool shouldAddRemainingSegmentsFromSpan1 = true;
 517     static const bool shouldAddRemainingSegmentsFromSpan2 = true;
 518     static const bool shouldAddRemainingSpansFromShape1 = true;
 519     static const bool shouldAddRemainingSpansFromShape2 = true;
 520 };
 521
 522 Region::Shape Region::Shape::unionShapes(const Shape& shape1, const Shape& shape2)
 523 {
 524     return shapeOperation<UnionOperation>(shape1, shape2);
 525 }
 526
 527 struct Region::Shape::IntersectOperation {
 528     static bool trySimpleOperation(const Shape&, const Shape&, Shape&)
 529     {
 530         return false;
 531     }
 532
 533     static const int opCode = 3;
 534
 535     static const bool shouldAddRemainingSegmentsFromSpan1 = false;
 536     static const bool shouldAddRemainingSegmentsFromSpan2 = false;
 537     static const bool shouldAddRemainingSpansFromShape1 = false;
 538     static const bool shouldAddRemainingSpansFromShape2 = false;
 539 };
 540
 541 Region::Shape Region::Shape::intersectShapes(const Shape& shape1, const Shape& shape2)
 542 {
 543     return shapeOperation<IntersectOperation>(shape1, shape2);
 544 }
 545
 546 struct Region::Shape::SubtractOperation {
 547     static bool trySimpleOperation(const Shape&, const Shape&, Region::Shape&)
 548     {
 549         return false;
 550     }
 551
 552     static const int opCode = 1;
 553
 554     static const bool shouldAddRemainingSegmentsFromSpan1 = true;
 555     static const bool shouldAddRemainingSegmentsFromSpan2 = false;
 556     static const bool shouldAddRemainingSpansFromShape1 = true;
 557     static const bool shouldAddRemainingSpansFromShape2 = false;
 558 };
 559
 560 Region::Shape Region::Shape::subtractShapes(const Shape& shape1, const Shape& shape2)
 561 {
 562     return shapeOperation<SubtractOperation>(shape1, shape2);
 563 }
 564
 565 #ifndef NDEBUG
 566 void Region::dump() const
 567 {
 568     printf("Bounds: (%d, %d, %d, %d)\n", m_bounds.x(), m_bounds.y(), m_bounds.width(), m_bounds.height());
 569     m_shape.dump();
 570 }
 571 #endif
 572
 573 void Region::intersect(const Region& region)
 574 {
 575     if (m_bounds.isEmpty())
 576         return;
 577     if (!m_bounds.intersects(region.m_bounds)) {
 578         m_shape = Shape();
 579         m_bounds = IntRect();
 580         return;
 581     }
 582
 583     Shape intersectedShape = Shape::intersectShapes(m_shape, region.m_shape);
 584
 585     m_shape.swap(intersectedShape);
 586     m_bounds = m_shape.bounds();
 587 }
 588
 589 void Region::unite(const Region& region)
 590 {
 591     if (region.isEmpty())
 592         return;
 593     if (isRect() && m_bounds.contains(region.m_bounds))
 594         return;
 595     if (region.isRect() && region.m_bounds.contains(m_bounds)) {
 596         m_shape = region.m_shape;
 597         m_bounds = region.m_bounds;
 598         return;
 599     }
 600     // FIXME: We may want another way to construct a Region without doing this test when we expect it to be false.
 601     if (!isRect() && contains(region))
 602         return;
 603
 604     Shape unitedShape = Shape::unionShapes(m_shape, region.m_shape);
 605
 606     m_shape.swap(unitedShape);
 607     m_bounds.unite(region.m_bounds);
 608 }
 609
 610 void Region::subtract(const Region& region)
 611 {
 612     if (m_bounds.isEmpty())
 613         return;
 614     if (region.isEmpty())
 615         return;
 616     if (!m_bounds.intersects(region.m_bounds))
 617         return;
 618
 619     Shape subtractedShape = Shape::subtractShapes(m_shape, region.m_shape);
 620
 621     m_shape.swap(subtractedShape);
 622     m_bounds = m_shape.bounds();
 623 }
 624
 625 void Region::translate(const IntSize& offset)
 626 {
 627     m_bounds.move(offset);
 628     m_shape.translate(offset);
 629 }
 630
 631 } // namespace blink