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 37namespace WebCore { 38 39Region::Region() 40{ 41} 42 43Region::Region(const IntRect& rect) 44 : m_bounds(rect) 45 , m_shape(rect) 46{ 47} 48 49Vector<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 68bool 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 76bool 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 104bool 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 112unsigned 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 126template<typename CompareOperation> 127bool 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 210struct 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 217struct 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 224Region::Shape::Shape() 225{ 226} 227 228Region::Shape::Shape(const IntRect& rect) 229{ 230 appendSpan(rect.y()); 231 appendSegment(rect.x()); 232 appendSegment(rect.maxX()); 233 appendSpan(rect.maxY()); 234} 235 236void Region::Shape::appendSpan(int y) 237{ 238 m_spans.append(Span(y, m_segments.size())); 239} 240 241bool 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 261void 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 270void 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 276void Region::Shape::appendSegment(int x) 277{ 278 m_segments.append(x); 279} 280 281Region::Shape::SpanIterator Region::Shape::spans_begin() const 282{ 283 return m_spans.data(); 284} 285 286Region::Shape::SpanIterator Region::Shape::spans_end() const 287{ 288 return m_spans.data() + m_spans.size(); 289} 290 291Region::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 303Region::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_WITH_SECURITY_IMPLICATION(segmentIndex <= m_segments.size()); 316 return m_segments.data() + segmentIndex; 317} 318 319#ifndef NDEBUG 320void Region::Shape::dump() const 321{ 322 for (auto span = spans_begin(), end = spans_end(); span != end; ++span) { 323 printf("%6d: (", span->y); 324 325 for (auto 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 334bool Region::Shape::isValid() const 335{ 336 for (auto span = spans_begin(), end = spans_end(); span != end && span + 1 != end; ++span) { 337 int y = span->y; 338 int height = (span + 1)->y - y; 339 340 if (height < 0) 341 return false; 342 343 for (auto segment = segments_begin(span), end = segments_end(span); segment != end && segment + 1 != end; segment += 2) { 344 int x = *segment; 345 int width = *(segment + 1) - x; 346 347 if (width < 0) 348 return false; 349 } 350 } 351 352 return true; 353} 354 355IntRect Region::Shape::bounds() const 356{ 357 if (isEmpty()) 358 return IntRect(); 359 360 SpanIterator span = spans_begin(); 361 int minY = span->y; 362 363 SpanIterator lastSpan = spans_end() - 1; 364 int maxY = lastSpan->y; 365 366 int minX = std::numeric_limits<int>::max(); 367 int maxX = std::numeric_limits<int>::min(); 368 369 while (span != lastSpan) { 370 SegmentIterator firstSegment = segments_begin(span); 371 SegmentIterator lastSegment = segments_end(span) - 1; 372 373 if (firstSegment && lastSegment) { 374 ASSERT(firstSegment != lastSegment); 375 376 if (*firstSegment < minX) 377 minX = *firstSegment; 378 379 if (*lastSegment > maxX) 380 maxX = *lastSegment; 381 } 382 383 ++span; 384 } 385 386 ASSERT(minX <= maxX); 387 ASSERT(minY <= maxY); 388 389 return IntRect(minX, minY, maxX - minX, maxY - minY); 390} 391 392void Region::Shape::translate(const IntSize& offset) 393{ 394 for (size_t i = 0; i < m_segments.size(); ++i) 395 m_segments[i] += offset.width(); 396 for (size_t i = 0; i < m_spans.size(); ++i) 397 m_spans[i].y += offset.height(); 398} 399 400void Region::Shape::swap(Shape& other) 401{ 402 m_segments.swap(other.m_segments); 403 m_spans.swap(other.m_spans); 404} 405 406enum { 407 Shape1, 408 Shape2, 409}; 410 411template<typename Operation> 412Region::Shape Region::Shape::shapeOperation(const Shape& shape1, const Shape& shape2) 413{ 414 COMPILE_ASSERT(!(!Operation::shouldAddRemainingSegmentsFromSpan1 && Operation::shouldAddRemainingSegmentsFromSpan2), invalid_segment_combination); 415 COMPILE_ASSERT(!(!Operation::shouldAddRemainingSpansFromShape1 && Operation::shouldAddRemainingSpansFromShape2), invalid_span_combination); 416 417 Shape result; 418 if (Operation::trySimpleOperation(shape1, shape2, result)) 419 return result; 420 421 SpanIterator spans1 = shape1.spans_begin(); 422 SpanIterator spans1End = shape1.spans_end(); 423 424 SpanIterator spans2 = shape2.spans_begin(); 425 SpanIterator spans2End = shape2.spans_end(); 426 427 SegmentIterator segments1 = 0; 428 SegmentIterator segments1End = 0; 429 430 SegmentIterator segments2 = 0; 431 SegmentIterator segments2End = 0; 432 433 // Iterate over all spans. 434 while (spans1 != spans1End && spans2 != spans2End) { 435 int y = 0; 436 int test = spans1->y - spans2->y; 437 438 if (test <= 0) { 439 y = spans1->y; 440 441 segments1 = shape1.segments_begin(spans1); 442 segments1End = shape1.segments_end(spans1); 443 ++spans1; 444 } 445 if (test >= 0) { 446 y = spans2->y; 447 448 segments2 = shape2.segments_begin(spans2); 449 segments2End = shape2.segments_end(spans2); 450 ++spans2; 451 } 452 453 int flag = 0; 454 int oldFlag = 0; 455 456 SegmentIterator s1 = segments1; 457 SegmentIterator s2 = segments2; 458 459 Vector<int, 32> segments; 460 461 // Now iterate over the segments in each span and construct a new vector of segments. 462 while (s1 != segments1End && s2 != segments2End) { 463 int test = *s1 - *s2; 464 int x; 465 466 if (test <= 0) { 467 x = *s1; 468 flag = flag ^ 1; 469 ++s1; 470 } 471 if (test >= 0) { 472 x = *s2; 473 flag = flag ^ 2; 474 ++s2; 475 } 476 477 if (flag == Operation::opCode || oldFlag == Operation::opCode) 478 segments.append(x); 479 480 oldFlag = flag; 481 } 482 483 // Add any remaining segments. 484 if (Operation::shouldAddRemainingSegmentsFromSpan1 && s1 != segments1End) 485 segments.appendRange(s1, segments1End); 486 else if (Operation::shouldAddRemainingSegmentsFromSpan2 && s2 != segments2End) 487 segments.appendRange(s2, segments2End); 488 489 // Add the span. 490 if (!segments.isEmpty() || !result.isEmpty()) 491 result.appendSpan(y, segments.data(), segments.data() + segments.size()); 492 } 493 494 // Add any remaining spans. 495 if (Operation::shouldAddRemainingSpansFromShape1 && spans1 != spans1End) 496 result.appendSpans(shape1, spans1, spans1End); 497 else if (Operation::shouldAddRemainingSpansFromShape2 && spans2 != spans2End) 498 result.appendSpans(shape2, spans2, spans2End); 499 500 return result; 501} 502 503struct 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 522Region::Shape Region::Shape::unionShapes(const Shape& shape1, const Shape& shape2) 523{ 524 return shapeOperation<UnionOperation>(shape1, shape2); 525} 526 527struct 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 541Region::Shape Region::Shape::intersectShapes(const Shape& shape1, const Shape& shape2) 542{ 543 return shapeOperation<IntersectOperation>(shape1, shape2); 544} 545 546struct 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 560Region::Shape Region::Shape::subtractShapes(const Shape& shape1, const Shape& shape2) 561{ 562 return shapeOperation<SubtractOperation>(shape1, shape2); 563} 564 565#ifndef NDEBUG 566void Region::dump() const 567{ 568 printf("Bounds: (%d, %d, %d, %d)\n", 569 m_bounds.x(), m_bounds.y(), m_bounds.width(), m_bounds.height()); 570 m_shape.dump(); 571} 572#endif 573 574void Region::updateBoundsFromShape() 575{ 576 m_bounds = m_shape.bounds(); 577} 578 579void Region::intersect(const Region& region) 580{ 581 if (m_bounds.isEmpty()) 582 return; 583 if (!m_bounds.intersects(region.m_bounds)) { 584 m_shape = Shape(); 585 m_bounds = IntRect(); 586 return; 587 } 588 589 Shape intersectedShape = Shape::intersectShapes(m_shape, region.m_shape); 590 591 m_shape.swap(intersectedShape); 592 m_bounds = m_shape.bounds(); 593} 594 595void Region::unite(const Region& region) 596{ 597 if (region.isEmpty()) 598 return; 599 if (isRect() && m_bounds.contains(region.m_bounds)) 600 return; 601 if (region.isRect() && region.m_bounds.contains(m_bounds)) { 602 m_shape = region.m_shape; 603 m_bounds = region.m_bounds; 604 return; 605 } 606 // FIXME: We may want another way to construct a Region without doing this test when we expect it to be false. 607 if (!isRect() && contains(region)) 608 return; 609 610 Shape unitedShape = Shape::unionShapes(m_shape, region.m_shape); 611 612 m_shape.swap(unitedShape); 613 m_bounds.unite(region.m_bounds); 614} 615 616void Region::subtract(const Region& region) 617{ 618 if (m_bounds.isEmpty()) 619 return; 620 if (region.isEmpty()) 621 return; 622 if (!m_bounds.intersects(region.m_bounds)) 623 return; 624 625 Shape subtractedShape = Shape::subtractShapes(m_shape, region.m_shape); 626 627 m_shape.swap(subtractedShape); 628 m_bounds = m_shape.bounds(); 629} 630 631void Region::translate(const IntSize& offset) 632{ 633 m_bounds.move(offset); 634 m_shape.translate(offset); 635} 636 637} // namespace WebCore 638